OctoInformBeta

OpenAI preprint, September 2026 · §8. The common-law entropy budget

Lemma 8.1: At a random time with a uniform offset, the per-letter information of increment words about finer residues sums to at most log⁡KD+nε\log K_D + n\varepsilon

A telescoping bound on residue information along a walk.

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, and let F0⊆F1⊆⋯F_0 \subseteq F_1 \subseteq \cdots be finite sets of nonzero Gaussian integers. Observed at a random time tt, the walk shows the residues of ztz_t modulo the elements of each FjF_j, and the word of its next LjL_j steps, where L0,L1,…L_0, L_1, \dots are positive lengths. How much does the word tell, per step, about the residues modulo Fj+1F_{j+1} once those modulo FjF_j are known, and how do these amounts add up along the chain? The item answers this for any random time followed by a uniform offset, among them the terminal time of the common schedule, a random time built from the differences of the walk itself.

Residues and Words

The residue class zmod⁡πz \bmod \pi of a Gaussian integer zz modulo a Gaussian integer π\pi is the coset z+πℤ[i]z + \pi\mathbb{Z}[i] of zz in the quotient of ℤ[i]\mathbb{Z}[i] by the subgroup πℤ[i]\pi\mathbb{Z}[i] of multiples of π\pi.✦ For a walk zz, a finite set FF of Gaussian integers and a time tt, the residue vector RF(t)=(ztmod⁡f)f∈FR_F(t) = (z_t \bmod f)_{f \in F} lists the residue classes of ztz_t modulo the elements of FF; along the chain F0⊆F1⊆⋯F_0 \subseteq F_1 \subseteq \cdots we write Rj(t)=RFj(t)R_j(t) = R_{F_j}(t).

The increment word WL(t)W_L(t) of length LL at time tt of a walk zz is the word of its next LL steps, WL(t)=(zt+1−zt,…,zt+L−zt+L−1).W_L(t) = (z_{t+1} - z_t, \dots, z_{t+L} - z_{t+L-1}).(1)✦

The lattice ball BDB_D of radius DD is the finite set of Gaussian integers uu with |u|≤D|u| \le D, and KDK_D is its number of elements.✦ The norm of a Gaussian integer f=x+yif = x + yi, with x,y∈ℤx, y \in \mathbb{Z}, is the integer N(f)=x2+y2\mathrm{N}(f) = x^2 + y^2.

Laws and Information

A finite probability law pp on a finite set Ω\Omega is a function from Ω\Omega to the nonnegative reals whose values, the masses, sum to 11; a random variable on Ω\Omega is a map from Ω\Omega to any set.✦ The uniform law on a nonempty finite set Ω\Omega gives every point the mass 1/|Ω|1/|\Omega|✦, and the point mass at ω∈Ω\omega \in \Omega gives ω\omega the mass 11 and every other point the mass 00✦. The pushforward of a law pp on Ω\Omega along a map gg to a finite set Ω′\Omega' is the law on Ω′\Omega' that gives each yy the mass ∑g(x)=yp(x)\sum_{g(x) = y} p(x).✦ The joint law of a law pp on a finite set II and laws qiq_i on Ω\Omega, one for each i∈Ii \in I, is the law on I×ΩI \times \Omega with mass p(i)qi(ω)p(i)\,q_i(\omega) at (i,ω)(i, \omega): the law of drawing ii from pp and then ω\omega from qiq_i.✦

For a finite probability law pp on Ω\Omega and random variables XX, YY, OO on Ω\Omega, with log\log the natural logarithm and H(X,Y)H(X, Y) the entropy of the pair (X,Y)(X, Y), the entropy of XX, the conditional entropy of XX given YY and the conditional mutual information of XX and YY given OO are H(X)=−∑xp(X=x)log⁡p(X=x),H(X∣Y)=H(X,Y)−H(Y),I(X;Y∣O)=H(X∣O)−H(X∣O,Y),\begin{aligned} H(X) &= -\sum_{x} p(X = x)\log p(X = x),\\ H(X \mid Y) &= H(X, Y) - H(Y),\\ I(X; Y \mid O) &= H(X \mid O) - H(X \mid O, Y), \end{aligned}(2) the sum running over the finitely many values xx of XX. The binary entropy of x∈[0,1]x \in [0, 1] is h(x)=−xlog⁡x−(1−x)log⁡(1−x)h(x) = -x\log x - (1 - x)\log(1 - x).

Random Times

A time law PP of last time ℓ∈ℕ\ell \in \mathbb{N} is a finite probability law on {0,1,…,ℓ}\{0, 1, \dots, \ell\}, the law of a random time at most ℓ\ell.✦ The exact start δa\delta_a at a time a∈ℕa \in \mathbb{N} is the time law of last time aa that is the point mass at aa.✦

The information IP(X;Y∣O)I_P(X; Y \mid O) of a time law PP, for maps XX, YY, OO on ℕ\mathbb{N} with values in any sets, is the conditional mutual information of XtX_t, YtY_t and OtO_t at a random time tt of law PP: IP(X;Y∣O)=I(Xt;Yt∣Ot).I_P(X; Y \mid O) = I(X_t; Y_t \mid O_t).(3)✦

A forward kernel KK of bound B∈ℕB \in \mathbb{N} is a family of finite probability laws KaK_a, one for each time a∈ℕa \in \mathbb{N}, on the advances 0,1,…,B0, 1, \dots, B.✦ The advance PKPK of a time law PP of last time ℓ\ell by KK is the time law of last time ℓ+B\ell + B that is the pushforward, under (b,u)↦b+u(b, u) \mapsto b + u, of the joint law of PP and the laws KbK_b.✦ The composite KRKR of KK with a forward kernel RR of bound B′B' is the forward kernel of bound B+B′B + B' whose law at a time aa is the pushforward, under (u,v)↦u+v(u, v) \mapsto u + v, of the joint law of KaK_a and the laws Ra+uR_{a+u}.✦ The smoothing kernel UNU_N is the forward kernel of bound NN whose law at every time is the uniform law on {0,…,N}\{0, \dots, N\}.✦

Common Schedules

The difference set E−EE - E of a finite set EE of Gaussian integers is the set of differences w−w′w - w' with w,w′∈Ew, w' \in E.✦ The walk segment of length nn of a walk zz is the set E={z0,…,zn}E = \{z_0, \dots, z_n\} of its points at the times 0,…,n0, \dots, n.✦ For each d∈E−Ed \in E - E, a chosen difference pair (ud,vd)(u_d, v_d) is a pair of times in {0,…,n}\{0, \dots, n\} with zud−zvd=dz_{u_d} - z_{v_d} = d, fixed once and for all✦, and the difference law of zz on its segment of length nn is the law of (ud,vd)(u_d, v_d) with dd drawn uniformly from E−EE - E✦.

The difference kernel Δn\Delta_n of a walk zz is the forward kernel of bound nn whose law at a time aa is that of the following advance: flip a fair coin, draw (ud,vd)(u_d, v_d) independently of it from the difference law of the walk za,za+1,…z_a, z_{a+1}, \dots on its segment of length nn, and advance by udu_d on heads and by vdv_d on tails.✦ The common schedule of segment lengths n1,…,nkn_1, \dots, n_k and offset NN is the forward kernel C(n1,…,nk;N)=Δn1(Δn2(⋯(ΔnkUN)⋯)).C(n_1, \dots, n_k; N) = \Delta_{n_1}\bigl(\Delta_{n_2}\bigl(\cdots(\Delta_{n_k} U_N)\cdots\bigr)\bigr).(4)✦ The terminal time t*t^* of the common schedule C(n1,…,nk;N)C(n_1, \dots, n_k; N) is the random time of law δ0C(n1,…,nk;N)\delta_0\, C(n_1, \dots, n_k; N).

The Claim

Theorem 1.

  1. Let z0,z1,…z_0, z_1, \dots be a walk in ℤ[i]\mathbb{Z}[i] with steps at most DD, and let F0⊆F1⊆⋯F_0 \subseteq F_1 \subseteq \cdots be finite sets of nonzero Gaussian integers. Let nn and NN be natural numbers, let L0,L1,…L_0, L_1, \dots be natural numbers with 0<Lj≤N0 < L_j \le N for j≤nj \le n and Lj∣Lj+1L_j \mid L_{j+1} for j<nj < n, and let ε≥0\varepsilon \ge 0 satisfy 2h(mN+1)+mN+1(Ljlog⁡KD+2∑f∈Fj+1log⁡N(f))≤ε2h\Bigl(\frac{m}{N+1}\Bigr) + \frac{m}{N+1}\Bigl(L_j \log K_D + 2\sum_{f \in F_{j+1}} \log \mathrm{N}(f)\Bigr) \le \varepsilon(5) for every j<nj < n and every integer mm with 0≤m<Lj+10 \le m < L_{j+1}. Let τ\tau be a random time on a finite probability space, with law PP, and let tt be the random time of law PUNPU_N, the time τ\tau followed by an independent uniform offset on {0,…,N}\{0, \dots, N\}. Then ∑j=0n1LjI(Rj+1(t);WLj(t)|Rj(t))≤log⁡KD+nε.\sum_{j=0}^{n} \frac{1}{L_j}\, I\bigl(R_{j+1}(t); W_{L_j}(t) \mathrel{\big|} R_j(t)\bigr) \le \log K_D + n\varepsilon.(6)✦

  2. Under the hypotheses of (a) on zz, the sets FjF_j, the lengths LjL_j, nn, NN and ε\varepsilon, for all segment lengths n1,…,nkn_1, \dots, n_k the terminal time t*t^* of the common schedule C(n1,…,nk;N)C(n_1, \dots, n_k; N) satisfies ∑j=0n1LjI(Rj+1(t*);WLj(t*)|Rj(t*))≤log⁡KD+nε.\sum_{j=0}^{n} \frac{1}{L_j}\, I\bigl(R_{j+1}(t^*); W_{L_j}(t^*) \mathrel{\big|} R_j(t^*)\bigr) \le \log K_D + n\varepsilon.(7)✦

  3. Let nn be a natural number and let ε\varepsilon, x0,…,xnx_0, \dots, x_n and y0,…,yny_0, \dots, y_n be real numbers with xj+1≤yj+εx_{j+1} \le y_j + \varepsilon for every j<nj < n and yn≥0y_n \ge 0. Then ∑j=0n(xj−yj)≤x0+nε.\sum_{j=0}^{n} (x_j - y_j) \le x_0 + n\varepsilon.(8)✦

In the paper, the result reads: for every fixed collection 𝒞\mathcal{C} of prime choices, ∑TI(XT′;WLT(t*)∣OT′)/LT≤log⁡KD+o(1)\sum_T I(X'_T; W_{L_T}(t^*) \mid O'_T)/L_T \le \log K_D + o(1), with the paper’s variables XT′X'_T and OT′O'_T, the sum running over the batches ℬT\mathcal{B}_T of the primes p≡1(mod⁡4)p \equiv 1 \pmod 4 in [T,2T][T, 2T] and the error tending to 00 uniformly over the choices and the walks as the paper’s parameter MM tends to infinity.

What Is Checked

Parts (a) and (b) are stated over the residue classes of the walk modulo the multiples of nonzero Gaussian integers, its increment words (1) and the lattice ball of radius DD, and over the information (3) of a time law, the conditional mutual information (2) of a finite probability law at a random time. The time law is the advance of a law by the smoothing kernel in (a), and in (b) the advance of the exact start δ0\delta_0 by the common schedule (4), built from difference kernels, difference laws and chosen difference pairs on the difference sets of walk segments. Part (c) is stated over real numbers alone.

The library also proves that every element dd of the difference set of a walk segment {z0,…,zn}\{z_0, \dots, z_n\} is a difference zu−zvz_u - z_v with uu and vv in {0,…,n}\{0, \dots, n\}.✦