OctoInformBeta

OpenAI preprint, September 2026 · §5. Coverage from shared continuation data

Lemma 5.1: A random Gaussian integer whose signed residues have nearly full joint entropy keeps them nearly uniform on average, given any data of small entropy

Conditioning on data of small entropy costs signed residues little.

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 p≡1(mod⁡4)p \equiv 1 \pmod 4 be a rational prime. It splits in ℤ[i]\mathbb{Z}[i] as p=πpπ‾pp = \pi_p\bar\pi_p with πp\pi_p a Gaussian prime and π‾p\bar\pi_p its complex conjugate, and a Gaussian integer has two residues at pp, one modulo πp\pi_p and one modulo π‾p\bar\pi_p, each in a ring of pp elements. For a random Gaussian integer ZZ with a finite law, each of these residues has entropy at most log⁡p\log p, the entropy of the uniform law on pp points.

Take a finite set of such primes. Suppose that the residues of ZZ modulo one factor of each of many of these primes, the factor being chosen by a sign (these are the signed residues of ZZ), together carry nearly the largest entropy they can, and that one knows data CC of small entropy, correlated with ZZ. How far can the residue of ZZ modulo a single factor, given CC, fall short of log⁡p\log p, on average over the prime and over the choice between πp\pi_p and π‾p\bar\pi_p? The library states a bound on that average, alongside a general inequality comparing the entropy of a random prefix of a random vector with the entropies of its coordinates given CC.

Entropy of Finite Laws

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 whose values sum to one.✦ The uniform law on a nonempty finite set Ω\Omega is the law that gives each element the mass 1/|Ω|1/|\Omega|.✦ Throughout, a mean 𝔼x\mathbb{E}_x over a finite set of values of xx is the mean under the uniform law on that set.

The entropy of a random variable XX on Ω\Omega, with values in any set, 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. The conditional entropy of XX given a random variable YY on Ω\Omega is H(X∣Y)=H(X,Y)−H(Y),H(X \mid Y) = H(X, Y) - H(Y),(2)✦ where (X,Y)(X, Y) is the random variable ω↦(X(ω),Y(ω))\omega \mapsto (X(\omega), Y(\omega)).

A random vector on Ω\Omega with kk coordinates in a set α\alpha is a random variable X=(X0,…,Xk−1)X = (X_0, \dots, X_{k-1}) with values in αk\alpha^k. For a permutation τ\tau of {0,…,k−1}\{0, \dots, k-1\} and a natural number ss, the prefix X[τ,s]X[\tau, s] of XX of length ss in the order τ\tau is the random vector with entries in α\alpha together with a blank symbol *\ast whose entry in position jj is Xτ(j)X_{\tau(j)} if j<sj < s and *\ast otherwise.✦ The random-order prefix entropy of XX at ss is the mean of the entropy of this prefix over the permutations τ\tau: OX(s)=𝔼τH(X[τ,s]).O_X(s) = \mathbb{E}_\tau\, H(X[\tau, s]).(3)✦

A sign vector of length kk is a choice σ=(σ0,…,σk−1)\sigma = (\sigma_0, \dots, \sigma_{k-1}) of a sign ++ or −- in each position, and {±}k\{\pm\}^k is the set of them. For a family X=(Xσ)σ∈{±}kX = (X^\sigma)_{\sigma \in \{\pm\}^k} of random vectors on Ω\Omega with kk coordinates in α\alpha, the sign-averaged entropy of XX at ss is SX(s)=𝔼σOXσ(s).S_X(s) = \mathbb{E}_\sigma\, O_{X^\sigma}(s).(4)✦

Split Prime Sieves and Residues

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 prime enumeration of 𝒫\mathcal{P} is a fixed listing p0,…,pn−1p_0, \dots, p_{n-1} of its n=|𝒫|n = |\mathcal{P}| primes✦, and the mean log of its primes is L*=1n∑i=0n−1log⁡pi.L^* = \frac{1}{n}\sum_{i=0}^{n-1} \log p_i.(5)✦

The signed factor of a Gaussian integer π\pi with a sign is π+=π\pi^{+} = \pi for the sign ++ and π−=π‾\pi^{-} = \bar\pi for the sign −-.✦ A signed index of 𝒫\mathcal{P} is a pair ι=(σ,k)\iota = (\sigma, k) of a sign vector σ∈{±}n\sigma \in \{\pm\}^n and a position k∈{0,…,n−1}k \in \{0, \dots, n-1\}.✦ The prime of ι\iota is pι=pkp_\iota = p_k, whatever σ\sigma✦, and the signed factor at ι\iota is πι=πpkσk\pi_\iota = \pi_{p_k}^{\sigma_k}.

The multiples of a Gaussian integer π\pi form the subgroup πℤ[i]\pi\mathbb{Z}[i] of ℤ[i]\mathbb{Z}[i], the lattice spanned by π\pi and iπi\pi.✦ The residue class of a Gaussian integer zz modulo π\pi is its class z+πℤ[i]z + \pi\mathbb{Z}[i] in the quotient ℤ[i]/πℤ[i]\mathbb{Z}[i]/\pi\mathbb{Z}[i].✦ For a signed index ι\iota, the residue ring at ι\iota is Rι=ℤ[i]/πιℤ[i]R_\iota = \mathbb{Z}[i]/\pi_\iota\mathbb{Z}[i]✦, and the residue map ρι:ℤ[i]→Rι\rho_\iota\colon \mathbb{Z}[i] \to R_\iota sends each Gaussian integer to its residue class modulo πι\pi_\iota.✦

The residue code cπ(z)c_\pi(z) of zz modulo π\pi is the natural number that labels the residue class of zz in a fixed numbering of the classes modulo π\pi.✦ For a sign vector σ∈{±}n\sigma \in \{\pm\}^n, the residue vector of a Gaussian integer zz with signs σ\sigma is the vector of codes rσ(z)=(cπp0σ0(z),…,cπpn−1σn−1(z)).r_\sigma(z) = \big(c_{\pi_{p_0}^{\sigma_0}}(z), \dots, c_{\pi_{p_{n-1}}^{\sigma_{n-1}}}(z)\big).(6)✦

A point variable is a random variable ZZ on Ω\Omega with values in ℤ[i]\mathbb{Z}[i]. The averaged signed residue entropy fZ(s)f_Z(s) of a point variable ZZ at a natural number ss, for a split prime sieve 𝒫\mathcal{P}, is the sign-averaged entropy at ss of the family σ↦rσ(Z)\sigma \mapsto r_\sigma(Z) of the residue vectors of ZZ: fZ(s)=𝔼σOrσ(Z)(s)=𝔼σ𝔼τH(rσ(Z)[τ,s]).f_Z(s) = \mathbb{E}_\sigma\, O_{r_\sigma(Z)}(s) = \mathbb{E}_\sigma\,\mathbb{E}_\tau\, H\big(r_\sigma(Z)[\tau, s]\big).(7)✦

The Claim

Theorem 1. Let PP be a finite probability law on a finite set Ω\Omega, let CC be a random variable on Ω\Omega with values in any set, and let bb be a natural number.

(a) Let 𝒫\mathcal{P} be a split prime sieve with nn primes and 1≤b≤n1 \le b \le n, let ZZ be a point variable, aa a Gaussian integer, and ee, EE real numbers. If fZ(b)≥(1−e)bL*f_Z(b) \ge (1 - e)\,b\,L^* and H(C)≤EH(C) \le E, then, with 𝔼ι\mathbb{E}_\iota the mean over the signed indices ι\iota of 𝒫\mathcal{P}, 𝔼ι[log⁡pι−H(ρι(Z−a)∣C)]≤eL*+Eb.\mathbb{E}_\iota\big[\log p_\iota - H\big(\rho_\iota(Z - a) \mid C\big)\big] \le e L^* + \frac{E}{b}.(8)✦

(b) Let 𝒫\mathcal{P} be a split prime sieve with nn primes and b≤nb \le n, and let YY be a point variable. Then, with the means over σ∈{±}n\sigma \in \{\pm\}^n and i∈{0,…,n−1}i \in \{0, \dots, n-1\}, fY(b)−H(C)≤b𝔼σ𝔼iH(rσ(Y)i∣C).f_Y(b) - H(C) \le b\,\mathbb{E}_\sigma\,\mathbb{E}_i\, H\big(r_\sigma(Y)_i \mid C\big).(9)✦

(c) Let X=(Xσ)σ∈{±}kX = (X^\sigma)_{\sigma \in \{\pm\}^k} be a family of random vectors on Ω\Omega with kk coordinates, and b≤kb \le k. Then, with the means over σ∈{±}k\sigma \in \{\pm\}^k and i∈{0,…,k−1}i \in \{0, \dots, k-1\}, SX(b)−H(C)≤b𝔼σ𝔼iH(Xiσ∣C).S_X(b) - H(C) \le b\,\mathbb{E}_\sigma\,\mathbb{E}_i\, H\big(X^\sigma_i \mid C\big).(10)✦

(d) Let XX be a random vector on Ω\Omega with kk coordinates, and b≤kb \le k. Then, with the mean over i∈{0,…,k−1}i \in \{0, \dots, k-1\}, OX(b)−H(C)≤b𝔼iH(Xi∣C).O_X(b) - H(C) \le b\,\mathbb{E}_i\, H(X_i \mid C).(11)✦

In the paper, the result reads: for a point variable ZZ and data CC with a finite joint law, the selection SS of signs and ordering being made independently of them, if fZ(b)≥(1−e)bL*f_Z(b) \ge (1 - e)\,b\,L^* and H(C)≤κbL*H(C) \le \kappa\, b\, L^* for a number κ\kappa, then the mean over signed indices ι\iota of log⁡pι−H(ρι(Z)∣C)\log p_\iota - H(\rho_\iota(Z) \mid C) is at most (e+κ)L*(e + \kappa)L^*, with ZZ, CC, ee, bb, L*L^*, ι\iota, ρι\rho_\iota and fZ(b)f_Z(b) standing for the paper’s YY, ℋ\mathcal{H}, ε\varepsilon, ss, L‾\bar L, cc, φc\varphi_c and 𝔼SH(FS(Y))\mathbb{E}_S H(F_S(Y)).

What Is Checked

The four inequalities are stated over finite probability laws, the entropy and conditional entropy of random variables, and the random-order and sign-averaged prefix entropies of random vectors. Parts (a) and (b) are stated also over a split prime sieve with its prime enumeration, mean log L*L^* and signed indices, the uniform law on those indices, the residue maps and residue vectors modulo the signed factors, and the averaged signed residue entropy fZf_Z of a point variable.

Beyond the claim, the library proves that a split prime sieve with at least one prime has a signed index.✦