OctoInformBeta

OpenAI preprint, September 2026 · §4. Entropy enrichment from a forward segment

Lemma 4.3: For a self-avoiding walk with steps at most DD and under explicit hypotheses, fZ(q)≥(1−e)qL*f_Z(q)\ge(1-e)qL^* forces fV(b)≥(1−e/2−20g)bL*f_V(b)\ge(1-e/2-20g)bL^*

Residue entropy enrichment by a difference transition.

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 self-avoiding walk in ℤ[i]\mathbb{Z}[i], its terms distinct, with steps |zt+1−zt|≤D|z_{t+1} - z_t| \le D for a real number D≥1D \ge 1, and let 𝒫\mathcal{P} be a batch of primes p≡1(mod⁡4)p \equiv 1 \pmod 4 in [T,2T][T, 2T] for a real number TT. At a random time τ\tau (defined below) the walk is at the point Z=zτZ = z_\tau, whose residues modulo the Gaussian prime factors of the primes of 𝒫\mathcal{P} have an entropy (defined below) that measures how evenly ZZ spreads over residue classes.

Lemma 4.3 of the paper concerns one difference transition, defined below, with a window of nn steps, which moves ZZ to a point VV of the forward segment zτ,…,zτ+nz_\tau, \dots, z_{\tau+n} chosen through a random difference of that segment. The question is how much residue entropy VV carries on fewer primes than ZZ, given how much ZZ carries.

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.✦ The kk primes of a split prime sieve 𝒫\mathcal{P} are numbered once and for all as p1,…,pkp_1, \dots, p_k, and the mean logarithm of 𝒫\mathcal{P} is the number L*=1k∑i=1klog⁡pi.L^* = \frac{1}{k}\sum_{i=1}^{k} \log p_i .(1)

The residue of z∈ℤ[i]z \in \mathbb{Z}[i] modulo a Gaussian integer π\pi is its class zmod⁡π=z+πℤ[i]z \bmod \pi = z + \pi\mathbb{Z}[i] modulo the multiples of π\pi, which form the lattice spanned by π\pi and iπi\pi.✦ The signed factor πiσ\pi^\sigma_i of index ii under a sign vector σ∈{+,−}k\sigma \in \{+,-\}^k is πpi\pi_{p_i} when σi=+\sigma_i = + and its conjugate π‾pi\bar\pi_{p_i} when σi=−\sigma_i = -.✦ The residue vector of zz with signs σ\sigma is the vector of its residues modulo the signed factors: rσ(z)=(zmod⁡π1σ,…,zmod⁡πkσ).r_\sigma(z) = \bigl(z \bmod \pi^\sigma_1, \dots, z \bmod \pi^\sigma_k\bigr).(2)✦

Random variables are defined on a finite probability space (Ω,P)(\Omega, P): a finite set Ω\Omega with a mass function P≥0P \ge 0 whose values sum to one.✦ The entropy H(A)H(A) of a random variable AA on Ω\Omega is the Shannon entropy of its law, the pushforward of PP along AA✦, and the conditional entropy is H(A∣B)=H(A,B)−H(B)H(A \mid B) = H(A, B) - H(B).✦

For a random vector A=(A1,…,Ak)A = (A_1, \dots, A_k), an ordering λ\lambda of {1,…,k}\{1, \dots, k\} and an integer s≥0s \ge 0, the prefix of AA of length ss in the order λ\lambda is (Aλ(1),…,Aλ(s))(A_{\lambda(1)}, \dots, A_{\lambda(s)})✦, and the random order prefix entropy of AA at ss is the mean of the entropy of this prefix over the k!k! orderings.✦ The averaged signed residue entropy fZ(s)f_Z(s) of a random point ZZ of ℤ[i]\mathbb{Z}[i] at ss is the mean, over the 2k2^k sign vectors σ\sigma, of the random order prefix entropy of rσ(Z)r_\sigma(Z) at ss: fZ(s)=𝔼σ𝔼λH(Zmod⁡πλ(1)σ,…,Zmod⁡πλ(s)σ),f_Z(s) = \mathbb{E}_\sigma\,\mathbb{E}_\lambda\, H\bigl(Z \bmod \pi^\sigma_{\lambda(1)}, \dots, Z \bmod \pi^\sigma_{\lambda(s)}\bigr),(3)✦ with σ\sigma and λ\lambda uniform and independent.

The fresh coordinate entropy Φb(X,Y)\Phi_b(X, Y) of two random points XX and YY of ℤ[i]\mathbb{Z}[i], for an integer 0≤b<k0 \le b < k, is the mean over σ\sigma and λ\lambda of the conditional entropy of the residue of X−YX - Y modulo the next signed factor πλ(b+1)σ\pi^\sigma_{\lambda(b+1)} given the residues of XX and of YY modulo the first bb: Φb(X,Y)=𝔼σ𝔼λH((X−Y)mod⁡πλ(b+1)σ|(Xmod⁡πλ(j)σ,Ymod⁡πλ(j)σ)1≤j≤b).\Phi_b(X, Y) = \mathbb{E}_\sigma\,\mathbb{E}_\lambda\, H\Bigl((X - Y) \bmod \pi^\sigma_{\lambda(b+1)} \mathrel{\Big|} \bigl(X \bmod \pi^\sigma_{\lambda(j)},\, Y \bmod \pi^\sigma_{\lambda(j)}\bigr)_{1 \le j \le b} \Bigr).(4)✦

The Difference Transition

The segment of a walk ww up to time nn is the set E={w0,…,wn}E = \{w_0, \dots, w_n\} of the points it visits at times 0,…,n0, \dots, n✦, and its difference set is E−E={u−v:u,v∈E}E - E = \{u - v : u, v \in E\}.✦ The difference law of ww over nn steps is the law on pairs (i,j)(i, j) of times in {0,…,n}\{0, \dots, n\} obtained by drawing dd uniformly from E−EE - E and returning the pair with wi−wj=dw_i - w_j = d chosen once and for all for dd.✦ For a walk zz and a time aa, write Φb(a)=Φb(za+i,za+j)\Phi_b(a) = \Phi_b(z_{a+i}, z_{a+j}) for a pair (i,j)(i, j) drawn from the difference law of the forward walk t↦za+tt \mapsto z_{a+t} over nn steps.

A random time τ\tau bounded by NN is given by its law on {0,…,N}\{0, \dots, N\}.✦ The step of τ\tau along zz with window nn is the random time τ′\tau' bounded by N+nN + n obtained by drawing a fair coin, independently of τ\tau, and, given τ=a\tau = a, a pair (i,j)(i, j) from the difference law of t↦za+tt \mapsto z_{a+t} over nn steps, and setting τ′=a+i\tau' = a + i on heads and τ′=a+j\tau' = a + j on tails.✦

The Margins

Let 𝒫\mathcal{P} be a split prime sieve with kk primes and mean logarithm L*L^*, and let DD and gg be real numbers. The enrichment margins for 𝒫\mathcal{P}, DD and gg are the following conditions on natural numbers nn, bb and qq, where ℓ=log⁡(n/18)\ell = \log(n/18) and K4DK_{4D} is the number of Gaussian integers uu with |u|≤4D|u| \le 4D, the size of the lattice ball of radius 4D4D: n≥1,0<b<q≤k,b≤gq,2(log⁡36+2log⁡(Dn))≤8gqL*,n \ge 1, \qquad 0 < b < q \le k, \qquad b \le gq, \qquad 2\bigl(\log 36 + 2\log(Dn)\bigr) \le 8gqL^*,(5) and ℓ>0,L*≤gℓ,5120L*≤g4ℓ,bL*≤gℓ,log⁡16+log⁡max⁡(D,K4D)≤gℓ,2(2log⁡n+log⁡16+2log⁡D)≤kL*.\begin{gathered} \ell > 0, \qquad L^* \le g\ell, \qquad 5120\,L^* \le g^4\ell, \qquad bL^* \le g\ell,\\ \log 16 + \log\max(D, K_{4D}) \le g\ell, \qquad 2(2\log n + \log 16 + 2\log D) \le kL^*. \end{gathered}(6)✦

The Claim

Theorem 1. Let 𝒫\mathcal{P} be a nonempty split prime sieve whose primes all lie in [T,2T][T, 2T] for some T≥5T \ge 5 and whose mean logarithm satisfies L*≥1L^* \ge 1. Let zz be a self-avoiding walk with steps at most D≥1D \ge 1, let 0<g≤1/1000 < g \le 1/100, and let the natural numbers nn, bb, qq meet the enrichment margins for 𝒫\mathcal{P}, DD and gg. Let τ\tau be a random time, τ′\tau' its step along zz with window nn, Z=zτZ = z_\tau and V=zτ′V = z_{\tau'}. If ee is a real number with fZ(q)≥(1−e)qL*f_Z(q) \ge (1 - e)\,qL^*, then fV(b)≥(1−e2−20g)bL*.f_V(b) \ge \Bigl(1 - \frac{e}{2} - 20g\Bigr)\, bL^*.(7)✦

In the paper, the result reads: for Z=zτZ = z_\tau and the sampled endpoint VV of the transition on a fixed self-avoiding walk with steps at most DD, with q=⌊U/L*⌋q = \lfloor U/L^*\rfloor and b=⌊g2U/L*⌋b = \lfloor g^2U/L^*\rfloor for a parameter UU, in any family with DD fixed, T→∞T \to \infty, q≤kq \le k and gCU/log⁡T→∞g^CU/\log T \to \infty for every fixed C>0C > 0, uniformly over walks, batches and starting laws, fV(b)/(bL*)≥12(1+fZ(q)/(qL*))−OD(g)f_V(b)/(bL^*) \ge \tfrac12\bigl(1 + f_Z(q)/(qL^*)\bigr) - O_D(g), the batch being ℬT\mathcal{B}_T and kk its number of primes.

What Is Checked

The claim (7) is stated over a split prime sieve and its mean logarithm L*L^*, the residues of Gaussian integers modulo the signed factors, the averaged signed residue entropy fZ(s)f_Z(s) built from Shannon entropy on finite probability spaces, a random time on a self-avoiding walk with steps at most DD and its step through the difference law of a forward segment, and the enrichment margins (5) and (6).

About these constructions the library proves that every element of the difference set of a segment {z0,…,zn}\{z_0, \dots, z_n\} is zi−zjz_i - z_j for some times i,j∈{0,…,n}i, j \in \{0, \dots, n\}.✦

It also proves, for random points XX, YY and ZZ of ℤ[i]\mathbb{Z}[i] on a finite probability space and integers 0<b<q≤k0 < b < q \le k, the entropy accounting b((q−b)Φb(X,Y)+fZ(q)−H(X−Y)−H(X−Z))≤q(fX(b)+fY(b)).b\bigl((q - b)\,\Phi_b(X, Y) + f_Z(q) - H(X - Y) - H(X - Z)\bigr) \le q\bigl(f_X(b) + f_Y(b)\bigr).(8)✦

If moreover FF is a real number with F≤Φb(X,Y)F \le \Phi_b(X, Y) and R≥1R \ge 1 bounds |X−Y||X - Y| and |X−Z||X - Z| at every outcome, then the point VV equal to XX on heads and to YY on tails of a fair coin drawn independently satisfies b((q−b)F+fZ(q)−2(log⁡36+2log⁡R))≤2qfV(b).b\bigl((q - b)F + f_Z(q) - 2(\log 36 + 2\log R)\bigr) \le 2q\, f_V(b).(9)✦

Along any walk zz with steps at most D≥1D \ge 1, let τ\tau be a random time bounded by NN and τ′\tau' its step with window n≥1n \ge 1, let 0<b<q≤k0 < b < q \le k, and let FF be a real number with F≤Φb(a)F \le \Phi_b(a) for every a∈{0,…,N}a \in \{0, \dots, N\}. Then b((q−b)F+fzτ(q)−2(log⁡36+2log⁡(Dn)))≤2qfzτ′(b).b\bigl((q - b)F + f_{z_\tau}(q) - 2(\log 36 + 2\log(Dn))\bigr) \le 2q\, f_{z_{\tau'}}(b).(10)✦

For a nonempty split prime sieve whose primes lie in [T,2T][T, 2T] with T≥5T \ge 5 and whose mean logarithm satisfies L*≥1L^* \ge 1, a self-avoiding walk zz whose first nn steps, with n≥1n \ge 1, are at most D≥1D \ge 1, a real number 0<g≤1/1000 < g \le 1/100 and a natural number bb satisfying (6), one has b<kandΦb(0)≥(1−30g)L*.b < k \qquad\text{and}\qquad \Phi_b(0) \ge (1 - 30g)\,L^*.(11)✦