OctoInformBeta

OpenAI preprint, September 2026 · §3. Arithmetic, walks, and entropy

Lemma 3.1: Steps at most DD and lags at most mm, with D,m≥1D, m \ge 1, keep displacement entropy at most log⁡36+2log⁡(Dm)\log 36 + 2\log(Dm) from a fixed or random start

Displacements of a walk over bounded lags have bounded entropy.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

Let z0,z1,…z_0, z_1, \dots be a walk in ℤ[i]\mathbb Z[i] with steps at most DD, a sequence of Gaussian integers with |zt+1−zt|≤D|z_{t+1} - z_t| \le D for every tt. Watch it at a random time and again at a random later time, at most mm steps on. How much entropy can the displacement between the two positions carry, in terms of DD and mm alone? And given Gaussian primes πp\pi_p of norm pp for finitely many primes p≡1(mod⁡4)p \equiv 1 \pmod 4, by how much can the entropy of the residues of the position modulo πp\pi_p or π‾p\bar\pi_p fall across such a displacement?

The library answers the first question with explicit constants, from a fixed start and from a random one, and the second for the residue entropy averaged over the choice of πp\pi_p or π‾p\bar\pi_p and over the order of the primes. It also bounds the number of Gaussian integers in a disc and the entropy of a Gaussian integer confined to one.

Lattice Balls, Laws and Random Lags

For a real number RR, the lattice ball BRB_R of radius RR is the finite set of Gaussian integers uu with |u|≤R|u| \le R; the ball BDB_D has KDK_D elements.✦

A finite probability law pp on a finite set Ω\Omega is a function p:Ω→ℝp \colon \Omega \to \mathbb R that is nonnegative at every point and sums to 11 over Ω\Omega.✦ A random variable on the finite probability space (Ω,p)(\Omega, p) is a function XX from Ω\Omega to a set, and its entropy, in natural logarithms, is the Shannon entropy of its law, H(X)=−∑xp(X=x)log⁡p(X=x),H(X) = -\sum_{x} p(X = x) \log p(X = x),(1)✦ the sum running over the finitely many values xx that XX takes.

Given a finite probability law μ\mu on a finite set AA and, for each a∈Aa \in A, a finite probability law qaq_a on a finite set Ω\Omega, the joint law μ⊗q\mu \otimes q is the finite probability law on A×ΩA \times \Omega with (μ⊗q)(a,ω)=μ(a)qa(ω),(\mu \otimes q)(a, \omega) = \mu(a)\, q_a(\omega),(2)✦

A time law (N,μ)(N, \mu) is a natural number NN, its last time, together with a finite probability law μ\mu on {0,…,N}\{0, \dots, N\}, the law of a random time TT.✦ A forward kernel κ\kappa of bound m∈ℕm \in \mathbb N is a family of finite probability laws κa\kappa_a on {0,…,m}\{0, \dots, m\}, one for each a∈ℕa \in \mathbb N: κa\kappa_a is the law of the lag II by which the walk moves on from time aa.✦

Residues and Their Entropy

A split prime sieve is a finite set 𝒫\mathcal P of rational primes p≡1(mod⁡4)p \equiv 1 \pmod 4 together with, for each p∈𝒫p \in \mathcal P, a Gaussian prime πp\pi_p of norm pp.✦ Its primes are numbered once and for all as p0,…,pk−1p_0, \dots, p_{k-1}, where k=|𝒫|k = |\mathcal P|.✦

For a Gaussian integer π\pi and a sign ε∈{+,−}\varepsilon \in \{+, -\}, the signed factor πε\pi^{\varepsilon} is π\pi itself when ε=+\varepsilon = + and its conjugate π‾\bar\pi when ε=−\varepsilon = -.✦ The multiples of π\pi form the sublattice of ℤ[i]\mathbb Z[i] spanned over ℤ\mathbb Z by π\pi and iπi\pi.✦ The residue of z∈ℤ[i]z \in \mathbb Z[i] modulo π\pi is its class in the quotient ℤ[i]/(π)\mathbb Z[i]/(\pi) by this sublattice✦; cπ(z)c_\pi(z) denotes this class.

For signs σ=(σ0,…,σk−1)∈{+,−}k\sigma = (\sigma_0, \dots, \sigma_{k-1}) \in \{+, -\}^k, the residue vector of z∈ℤ[i]z \in \mathbb Z[i] is rσ(z)=(r0σ(z),…,rk−1σ(z))r^\sigma(z) = (r^\sigma_0(z), \dots, r^\sigma_{k-1}(z)), with entries rjσ(z)=cπpjσj(z),0≤j<k.r^\sigma_j(z) = c_{\pi_{p_j}^{\sigma_j}}(z), \qquad 0 \le j < k.(3)✦

Let V=(V0,…,Vk−1)V = (V_0, \dots, V_{k-1}) be a random vector on (Ω,p)(\Omega, p), ρ\rho a permutation of {0,…,k−1}\{0, \dots, k-1\} and s∈ℕs \in \mathbb N. The prefix of VV of length ss in the order ρ\rho is the random vector whose entry of index ii is Vρ(i)V_{\rho(i)} for i<si < s and a fixed constant value for i≥si \ge s, so that only the first ss entries carry information.✦ The random-order prefix entropy of VV at ss is the mean of the entropy of this prefix over the k!k! permutations ρ\rho.✦ For a random vector VσV^\sigma that depends on signs σ∈{+,−}k\sigma \in \{+, -\}^k, the sign-averaged entropy at ss is the mean of its random-order prefix entropy over the 2k2^k choices of σ\sigma.✦

For a split prime sieve and a random variable ZZ on (Ω,p)(\Omega, p) with values in ℤ[i]\mathbb Z[i], the averaged signed residue entropy fZ(s)f_Z(s) is the sign-averaged entropy of the residue vectors rσ(Z)r^\sigma(Z) at ss: fZ(s)=12k∑σ∈{+,−}k1k!∑ρH((rρ(i)σ(Z))i<s).f_Z(s) = \frac{1}{2^k} \sum_{\sigma \in \{+,-\}^k} \frac{1}{k!} \sum_{\rho} H\bigl( (r^\sigma_{\rho(i)}(Z))_{i < s} \bigr).(4)✦

The Claim

Theorem 1. For every real R≥1R \ge 1, the lattice ball of radius RR satisfies |BR|≤36R2,|B_R| \le 36R^2,(5)✦ and every random variable ZZ with values in ℤ[i]\mathbb Z[i] on a finite probability space, with |Z|≤R|Z| \le R at every point, satisfies H(Z)≤log⁡36+2log⁡R.H(Z) \le \log 36 + 2\log R.(6)✦ Let D≥1D \ge 1 be real, let z0,z1,…z_0, z_1, \dots be a walk in ℤ[i]\mathbb Z[i] with steps at most DD, and let κ\kappa be a forward kernel of bound m≥1m \ge 1. For every time a∈ℕa \in \mathbb N, with the lag II drawn from κa\kappa_a, H(za+I−za)≤log⁡36+2log⁡(Dm),H(z_{a+I} - z_a) \le \log 36 + 2\log(Dm),(7)✦ and for every time law (N,μ)(N, \mu), under the joint law μ⊗κ\mu \otimes \kappa of a time TT drawn from μ\mu and a lag II drawn from κT\kappa_T, H(zT+I−zT)≤log⁡36+2log⁡(Dm).H(z_{T+I} - z_T) \le \log 36 + 2\log(Dm).(8)✦ For every split prime sieve, all random variables XX and YY with values in ℤ[i]\mathbb Z[i] on one finite probability space, and every s∈ℕs \in \mathbb N, fX(s)≤fY(s)+H(Y−X).f_X(s) \le f_Y(s) + H(Y - X).(9)✦

In the paper, the result reads: if T0T_0 and T1T_1 are jointly distributed finite random times with |T1−T0|≤n|T_1 - T_0| \le n almost surely, then H(zT1−zT0)≤2log⁡(n+1)+OD(1)H(z_{T_1} - z_{T_0}) \le 2\log(n+1) + O_D(1), also conditionally, and H(F(zT1))≥H(F(zT0))−H(zT1−zT0)H(F(z_{T_1})) \ge H(F(z_{T_0})) - H(z_{T_1} - z_{T_0}) for every finite vector FF of residue maps.

In the box, T0T_0 is TT and T1T_1 is T+IT + I, so that n=mn = m, and the vectors FF are the prefixes of the residue vectors rσr^\sigma, with XX and YY in place of zT0z_{T_0} and zT1z_{T_1} and the entropies averaged into ff.

What Is Checked

The claim is stated over the lattice balls BRB_R, finite probability laws and the entropy (1), walks in ℤ[i]\mathbb Z[i] with steps at most DD, forward kernels, time laws and the joint law (2), and split prime sieves, with the residues modulo their signed factors and the averaged signed residue entropy (4).

The library shows that the joint law (2) is again a finite probability law, and that z↦(Re⁡z,Im⁡z)z \mapsto (\operatorname{Re} z, \operatorname{Im} z) is a ℤ\mathbb Z-linear isomorphism of ℤ[i]\mathbb Z[i] onto ℤ2\mathbb Z^2✦, with 11 and ii the corresponding basis of ℤ[i]\mathbb Z[i] over ℤ\mathbb Z.✦