OctoInformBeta

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

Theorem 5.2: When later steps cover well and YiY_i keeps nearly full entropy given nn shared draws, few coordinates of Yi+hiY_i + h_i have many low residues

Coverage passes one step back through shared continuation data.

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 𝒫\mathcal{P} be a finite set of rational primes p≡1(mod⁡4)p \equiv 1 \pmod 4, each with a chosen Gaussian prime πp\pi_p of norm pp. From a time aa the walk advances a random number NN of steps, and the displacement za+N−zaz_{a+N} - z_a is reduced modulo πp\pi_p or π‾p\bar\pi_p, landing in one of pp residue classes. For a threshold τ\tau, a class is low when its probability is below τ/p\tau/p, and the displacement covers the classes well when few of them are low.

Theorem 5.2 asks how coverage passes back in time. A first random advance is followed by a second, drawn afresh at the time where the first one ends. If the second covers well for most moduli, what must hold of the first for the combined advance to cover well? The answer is phrased through the entropy of the residues of the point that the first advance reaches.

The claim also has an abstract form, in which finite abelian groups GiG_i, for coordinates ii of a finite set II weighted by a law ww, stand for the residue rings. A random state AA has a value Yi(A)Y_i(A) in each GiG_i; a random step γ\gamma, drawn from a law qAq_A that depends on AA, has an image hi(γ)h_i(\gamma) in each GiG_i; and nn further steps γ1,…,γn\gamma_1, \dots, \gamma_n, drawn independently from qAq_A, are continuation data shared by all coordinates. Coverage is asked of Yi(A)+hi(γ)Y_i(A) + h_i(\gamma), knowing coverage of hi(γ)h_i(\gamma) and how little the entropy of Yi(A)Y_i(A) given the shared data falls below log⁡|Gi|\log|G_i|.

Laws, Entropy and Low Residues

A finite probability law μ\mu on a finite set XX is a function μ:X→ℝ\mu \colon X \to \mathbb{R} with nonnegative values that sum to 11✦; it gives a subset SS of XX the probability μ(S)=∑x∈Sμ(x)\mu(S) = \sum_{x \in S} \mu(x)✦. The uniform law on a nonempty finite set XX gives every point the mass 1/|X|1/|X|, and the proportion of a subset of XX is its probability under the uniform law.✦ The pushforward f*μf_*\mu of μ\mu along a map f:X→X′f \colon X \to X' to a finite set X′X' is the law of f(x)f(x) for xx drawn from μ\mu: it gives x′x' the mass μ(f−1(x′))\mu(f^{-1}(x')).✦

The joint law of a law λ\lambda on a finite set Ω\Omega and laws qωq_\omega on a finite set Γ\Gamma, one for each ω∈Ω\omega \in \Omega, is the law on Ω×Γ\Omega \times \Gamma with mass λ(ω)qω(γ)\lambda(\omega)\, q_\omega(\gamma) at (ω,γ)(\omega, \gamma), the law of (A,γ)(A, \gamma) when AA is drawn from λ\lambda and then γ\gamma from qAq_A.✦ The nn-fold independent repetition q⊗nq^{\otimes n} of a law qq on Γ\Gamma is the law on Γn\Gamma^n with mass q(γ1)⋯q(γn)q(\gamma_1) \cdots q(\gamma_n) at (γ1,…,γn)(\gamma_1, \dots, \gamma_n).✦

The entropy of a random variable XX on a finite set carrying a law is H(X)=−∑xℙ(X=x)log⁡ℙ(X=x)H(X) = -\sum_x \mathbb{P}(X = x) \log \mathbb{P}(X = x), the sum running over the values of XX and ℙ\mathbb{P} denoting probability under that law.✦ The conditional entropy of XX given a second random variable YY on the same set is H(X∣Y)=H(X,Y)−H(Y)H(X \mid Y) = H(X, Y) - H(Y).✦

The set of low residues of a law μ\mu on a finite set GG at threshold τ\tau is Lowτ(μ)={x∈G:μ(x)<τ/|G|}.\mathrm{Low}_\tau(\mu) = \{x \in G : \mu(x) < \tau/|G|\}.(1)✦ A law μ\mu on a residue ring of pp classes has (τ,β)(\tau, \beta) coverage when it has fewer than p1−βp^{1-\beta} low residues. The claim counts low residues against a threshold uu in place of p1−βp^{1-\beta}.

For a finite abelian group GG, a subset KK of GG, reals τ\tau and δ\delta, and elements g1,…,gng_1, \dots, g_n of GG, the coverage list of g1,…,gng_1, \dots, g_n is the set of x∈Gx \in G for which few of the shifts x+gjx + g_j land in KK: CK(g1,…,gn)={x∈G:#{j≤n:x+gj∈K}≤n(τ+δ)|K||G|}.C_K(g_1, \dots, g_n) = \Bigl\{x \in G : \#\{j \le n : x + g_j \in K\} \le \frac{n(\tau + \delta)|K|}{|G|}\Bigr\}.(2)✦

Residues Along a Walk

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 listed once and for all as p1,…,pkp_1, \dots, p_k, and the mean of their logarithms is L*=1k∑j=1klog⁡pjL^* = \frac{1}{k} \sum_{j=1}^{k} \log p_j.

A signed prime index of 𝒫\mathcal{P} is a pair ι=(σ,j)\iota = (\sigma, j) of a sign vector σ∈{+,−}k\sigma \in \{+, -\}^k and a position j∈{1,…,k}j \in \{1, \dots, k\}; there are 2kk2^k k of them.✦ For a sign vector σ\sigma, πjσ\pi^\sigma_j is πpj\pi_{p_j} when σj=+\sigma_j = + and its conjugate π‾pj\bar\pi_{p_j} when σj=−\sigma_j = -.✦ The prime of ι=(σ,j)\iota = (\sigma, j) is pι=pjp_\iota = p_j✦, and its signed factor is πι=πjσ\pi_\iota = \pi^\sigma_j✦. The residue ring at ι\iota is the quotient ℤ[i]/(πι)\mathbb{Z}[i]/(\pi_\iota) of ℤ[i]\mathbb{Z}[i] by the multiples of πι\pi_\iota✦, and rι(z)r_\iota(z) is the class of z∈ℤ[i]z \in \mathbb{Z}[i] in it✦.

For a random Gaussian integer ZZ on a finite set carrying a law, and s∈ℕs \in \mathbb{N}, the averaged signed residue entropy fZ(s)f_Z(s) is the mean, over sign vectors σ\sigma and orderings ρ\rho of the positions, all taken uniformly, of the entropy of the residues of ZZ modulo the signed factors at the first ss positions in the order ρ\rho, all kk of them when s≥ks \ge k.✦ For s≤ks \le k, fZ(s)=12kk!∑σ∑ρH(r(σ,ρ(1))(Z),…,r(σ,ρ(s))(Z)).f_Z(s) = \frac{1}{2^k\, k!} \sum_{\sigma} \sum_{\rho} H\bigl(r_{(\sigma, \rho(1))}(Z), \dots, r_{(\sigma, \rho(s))}(Z)\bigr).(3)✦

A forward kernel 𝒦\mathcal{K} consists of a bound M𝒦∈ℕM_{\mathcal{K}} \in \mathbb{N} and, for each time a∈ℕa \in \mathbb{N}, a law 𝒦a\mathcal{K}_a on the advances 0,1,…,M𝒦0, 1, \dots, M_{\mathcal{K}}.✦ The composite 𝒦ℛ\mathcal{K}\mathcal{R} of forward kernels 𝒦\mathcal{K} and ℛ\mathcal{R} is the forward kernel with bound M𝒦+MℛM_{\mathcal{K}} + M_{\mathcal{R}} whose law at time aa is the law of N+N′N + N', where NN is drawn from 𝒦a\mathcal{K}_a and then N′N' from ℛa+N\mathcal{R}_{a+N}.✦ For a walk zz, a forward kernel 𝒦\mathcal{K}, a time aa and a signed index ι\iota, the relative residue law νa,ι𝒦\nu^{\mathcal{K}}_{a,\iota} is the law of rι(za+N−za)r_\iota(z_{a+N} - z_a) for NN drawn from 𝒦a\mathcal{K}_a.✦

The Claim

Theorem 1. Let n≥1n \ge 1, 0≤τ≤3/80 \le \tau \le 3/8, 0<δ≤1/640 < \delta \le 1/64 and ε≥0\varepsilon \ge 0; in (a), (b) and (d), let also η>0\eta > 0, η′\eta' and vv be reals with η′+ε≤ηδ/2\eta' + \varepsilon \le \eta\delta/2 and 2(1−log⁡(ηδ/2))≤v2(1 - \log(\eta\delta/2)) \le v. In (a), (b) and (c), λ\lambda is a law on a finite set Ω\Omega and qωq_\omega a law on a finite set Γ\Gamma for each ω∈Ω\omega \in \Omega; probabilities ℙ\mathbb{P} are taken with AA drawn from λ\lambda and then a step γ\gamma from qAq_A, and conditional entropies with AA drawn from λ\lambda and then γ1,…,γn\gamma_1, \dots, \gamma_n independently from qAq_A. In (a) and (b), ww is a law on a finite set II, each i∈Ii \in I has a finite abelian group GiG_i and maps Yi:Ω→GiY_i \colon \Omega \to G_i and hi:Γ→Gih_i \colon \Gamma \to G_i, and e<ηδv/4e < \eta\delta v/4 is a real with ∑i∈Iw(i)(log⁡|Gi|−H(Yi(A)∣γ1,…,γn))≤e.\sum_{i \in I} w(i) \bigl(\log|G_i| - H(Y_i(A) \mid \gamma_1, \dots, \gamma_n)\bigr) \le e.(4)

  1. Let B⊆IB \subseteq I, and let Ωi⊆Ω\Omega_i \subseteq \Omega for i∈Ii \in I with ∑iw(i)λ(Ωi)≤η′\sum_i w(i)\, \lambda(\Omega_i) \le \eta'. Suppose that each i∈Bi \in B has a nonempty set Ki⊆GiK_i \subseteq G_i with ℙ(Yi(A)+hi(γ)∈Ki)≤τ|Ki|/|Gi|\mathbb{P}(Y_i(A) + h_i(\gamma) \in K_i) \le \tau|K_i|/|G_i| and |Gi|exp⁡(−nδ2|Ki|/(2|Gi|))≤ε|G_i| \exp(-n\delta^2|K_i|/(2|G_i|)) \le \varepsilon, a real bi≥1b_i \ge 1 with v≤log⁡|Gi|−log⁡biv \le \log|G_i| - \log b_i, and, for each ω∉Ωi\omega \notin \Omega_i, a set Ei(ω)⊆GiE_i(\omega) \subseteq G_i with |Ei(ω)|/δ≤bi|E_i(\omega)|/\delta \le b_i off which hi*qωh_{i*}q_\omega gives every element probability at least (τ+4δ)/|Gi|(\tau + 4\delta)/|G_i|. Then w(B)≤η.w(B) \le \eta.(5)✦

  2. Let μi\mu_i be the law of Yi(A)+hi(γ)Y_i(A) + h_i(\gamma), and let ui>0u_i > 0, ui′u'_i and bi≥1b_i \ge 1 be reals with v≤log⁡|Gi|−log⁡biv \le \log|G_i| - \log b_i, ui′/δ≤biu'_i/\delta \le b_i and |Gi|exp⁡(−nδ2ui/(2|Gi|))≤ε|G_i| \exp(-n\delta^2 u_i/(2|G_i|)) \le \varepsilon for every i∈Ii \in I. If ∑iw(i)λ({ω:|Lowτ+4δ(hi*qω)|≥ui′})≤η′\sum_i w(i)\, \lambda\bigl(\{\omega : |\mathrm{Low}_{\tau+4\delta}(h_{i*}q_\omega)| \ge u'_i\}\bigr) \le \eta', then w({i∈I:|Lowτ(μi)|≥ui})≤η.w\bigl(\{i \in I : |\mathrm{Low}_\tau(\mu_i)| \ge u_i\}\bigr) \le \eta.(6)✦

  3. Let GG be a finite abelian group with maps Y:Ω→GY \colon \Omega \to G and h:Γ→Gh \colon \Gamma \to G, let K⊆GK \subseteq G be a nonempty set with |G|exp⁡(−nδ2|K|/(2|G|))≤ε|G| \exp(-n\delta^2|K|/(2|G|)) \le \varepsilon, b≥1b \ge 1 a real and Ω0⊆Ω\Omega_0 \subseteq \Omega, and for each ω∉Ω0\omega \notin \Omega_0 let E(ω)⊆GE(\omega) \subseteq G be a set with |E(ω)|/δ≤b|E(\omega)|/\delta \le b off which h*qωh_*q_\omega gives every element probability at least (τ+4δ)/|G|(\tau + 4\delta)/|G|. If ℙ(Y(A)+h(γ)∈K)≤τ|K||G|,\mathbb{P}\bigl(Y(A) + h(\gamma) \in K\bigr) \le \frac{\tau|K|}{|G|},(7)✦ then the shared steps force a deficit log⁡|G|−H(Y(A)∣γ1,…,γn)\log|G| - H(Y(A) \mid \gamma_1, \dots, \gamma_n), bounded below through the probability that Y(A)Y(A) lies in the coverage list (2) of h(γ1),…,h(γn)h(\gamma_1), \dots, h(\gamma_n).

  4. Let 𝒫\mathcal{P} be a split prime sieve with k≥1k \ge 1 primes, zz a walk with steps at most D≥1D \ge 1, 𝒦\mathcal{K} and ℛ\mathcal{R} forward kernels with Mℛ≥1M_{\mathcal{R}} \ge 1, aa a time, bb an integer with 1≤b≤k1 \le b \le k, and ee a real with eL*+n(log⁡36+2log⁡(DMℛ))/b<ηδv/4eL^* + n(\log 36 + 2\log(D M_{\mathcal{R}}))/b < \eta\delta v/4. For each signed index ι\iota let uι>0u_\iota > 0, uι′u'_\iota and cι≥1c_\iota \ge 1 be reals with v≤log⁡pι−log⁡cιv \le \log p_\iota - \log c_\iota, uι′/δ≤cιu'_\iota/\delta \le c_\iota and pιexp⁡(−nδ2uι/(2pι))≤εp_\iota \exp(-n\delta^2 u_\iota/(2p_\iota)) \le \varepsilon. Suppose that the point Z=za+NZ = z_{a+N}, with NN drawn from 𝒦a\mathcal{K}_a, has fZ(b)≥(1−e)bL*f_Z(b) \ge (1 - e)bL^*, and that at every time tt the signed indices ι\iota with |Lowτ+4δ(νt,ιℛ)|≥uι′|\mathrm{Low}_{\tau+4\delta}(\nu^{\mathcal{R}}_{t,\iota})| \ge u'_\iota form a proportion at most η′\eta'. Then 12kk#{ι:|Lowτ(νa,ι𝒦ℛ)|≥uι}≤η.\frac{1}{2^k k}\, \#\bigl\{\iota : |\mathrm{Low}_\tau(\nu^{\mathcal{K}\mathcal{R}}_{a,\iota})| \ge u_\iota\bigr\} \le \eta.(8)✦

In the paper, the result reads: in the experiment with Y=y(A)Y = y(A), ℋ=(h1,…,hn)\mathcal{H} = (h_1, \dots, h_n) drawn independently from νA\nu_A and Z=Y+h1Z = Y + h_1, where 0<τ≤3/80 < \tau \le 3/8, 0<δ≤1/640 < \delta \le 1/64, τ′=τ+4δ\tau' = \tau + 4\delta, 0<β′≤β<10 < \beta' \le \beta < 1, 0<η≤10 < \eta \le 1 and 0≤η′≤10 \le \eta' \le 1, if at every aa all but a fraction η′\eta' of the coordinates have (τ′,β′)(\tau', \beta') coverage for φc(y(a)+h1)\varphi_c(y(a) + h_1) given A=aA = a, and 𝔼SH(FS(Y))≥(1−ε)sL‾\mathbb{E}_S H(F_S(Y)) \ge (1 - \varepsilon)s\bar{L}, H(ℋ)≤κsL‾H(\mathcal{H}) \le \kappa s\bar{L}, η′≤ηδ/100\eta' \le \eta\delta/100, ε+κ≤ηδβ′/16\varepsilon + \kappa \le \eta\delta\beta'/16, pexp⁡(−δ2np−β/2)≤δ/100p\exp(-\delta^2 n p^{-\beta}/2) \le \delta/100, δ−1<pβ′/2\delta^{-1} < p^{\beta'/2} and log⁡(2e/δ)≤(β′/4)log⁡T\log(2\mathrm{e}/\delta) \le (\beta'/4)\log T, then all but a fraction η\eta of the coordinates have (τ,β)(\tau, \beta) coverage for φc(Z)\varphi_c(Z). The symbols yy, νA\nu_A, φc\varphi_c, cc, FSF_S, SS, ss, L‾\bar{L}, κ\kappa, TT and β′\beta' are the paper’s own.

What Is Checked

The claim is stated over finite probability laws with their probabilities, uniform laws, pushforwards, joint laws and independent repetitions, over entropy and conditional entropy, the low residues (1) and the coverage list (2), and, for the walk, over split prime sieves with their signed prime indices, signed factors, residue rings and mean L*L^*, the averaged signed residue entropy (3), forward kernels, their composites and their relative residue laws. The library also shows that a split prime sieve with at least one prime has a signed prime index.✦