OctoInformBeta

OpenAI preprint, September 2026 · §6. A common sampling schedule

Proposition 6.2: For a self-avoiding walk with steps at most DD, coverage derivations built from entropy bands cap the exceptional share at η\eta

Few low residues at the terminal time for most signed primes.

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] with steps at most D≥1D\ge 1, and let 𝒫\mathcal{P} be a batch of primes p≡1(mod⁡4)p\equiv 1\pmod 4, all in an interval [T,2T][T,2T]. Start at a time aa, move forward a random number tt of steps drawn by a fixed sampling schedule, and reduce the displacement za+t−zaz_{a+t}-z_a modulo a signed prime, πp\pi_p or its conjugate π‾p\bar\pi_p, where πp\pi_p is a Gaussian prime of norm pp for p∈𝒫p\in\mathcal{P}. The residue ring has pp classes, and a class is low when the terminal residue falls in it with probability below τ/p\tau/p, for a floor τ\tau such as 1/41/4. The item shows that, from every start aa, all but a share η\eta of the signed primes have few low classes, through a certificate built from lower bounds on the entropy of the terminal 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 mean log L*L^* of a split prime sieve 𝒫\mathcal{P} with m=|𝒫|m=|\mathcal{P}| primes, listed in a fixed enumeration p0,…,pm−1p_0,\dots,p_{m-1}, is the average of log⁡p\log p over them: L*=1m∑j=0m−1log⁡pj.L^*=\frac{1}{m}\sum_{j=0}^{m-1}\log p_j .(1)✦

A signed index of 𝒫\mathcal{P} is a pair ι=(σ,j)\iota=(\sigma,j) of a sign vector σ∈{+,−}m\sigma\in\{+,-\}^m and a position j<mj<m.✦ Its prime is pι=pjp_\iota=p_j✦, and its signed factor πι\pi_\iota is πpj\pi_{p_j} when σj=+\sigma_j=+ and the conjugate π‾pj\bar\pi_{p_j} when σj=−\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, its products with Gaussian integers✦, and the residue map sends a Gaussian integer to its class there.✦

Laws and Entropy

A finite probability law PP on a finite set Ω\Omega is a function Ω→ℝ\Omega\to\mathbb{R} with nonnegative values that sum to one.✦ The uniform law gives each point of Ω\Omega the mass 1/|Ω|1/|\Omega|✦, and the probability of an event is the total mass of the outcomes at which it holds.✦ The pushforward of a law PP on Ω\Omega along a map ff from Ω\Omega is the law that gives each point the mass of its preimage under ff.✦ Given a law PP on Ω\Omega and a law Q(⋅∣ω)Q(\cdot\mid\omega) on Ω′\Omega' for each ω∈Ω\omega\in\Omega, the joint law on Ω×Ω′\Omega\times\Omega' gives (ω,ω′)(\omega,\omega') the mass P(ω)Q(ω′∣ω)P(\omega)\,Q(\omega'\mid\omega).✦ The entropy H(X)H(X) of a random variable XX on Ω\Omega is the Shannon entropy of its law.✦

For a random point ZZ of ℤ[i]\mathbb{Z}[i] on Ω\Omega and a sign vector σ\sigma, the residue vector of ZZ has the entries rjσ(Z)r^\sigma_j(Z), j<mj<m, where rjσ(Z)r^\sigma_j(Z) is the class of ZZ modulo πpj\pi_{p_j} when σj=+\sigma_j=+ and modulo π‾pj\bar\pi_{p_j} when σj=−\sigma_j=-.✦ The point entropy of ZZ at s∈ℕs\in\mathbb{N} is the sign-averaged entropy of the residue vector: the mean, over the sign vectors σ\sigma, of its random-order prefix entropy, which is the mean, over the orderings θ\theta of the positions, of the entropy of the prefix revealing its first ss entries in the order θ\theta (all of them when s≥ms\ge m): fZ(s)=12mm!∑σ∈{+,−}m∑θ∈SmH(rθ(0)σ(Z),…,rθ(s−1)σ(Z)).f_Z(s)=\frac{1}{2^m\,m!}\sum_{\sigma\in\{+,-\}^m}\ \sum_{\theta\in S_m} H\bigl(r^\sigma_{\theta(0)}(Z),\dots,r^\sigma_{\theta(s-1)}(Z)\bigr).(2)✦

Sampling Schedules

A forward kernel κ\kappa consists of a bound Mκ∈ℕM_\kappa\in\mathbb{N} and, for every time a∈ℕa\in\mathbb{N}, a finite probability law κa\kappa_a on the advances 0,1,…,Mκ0,1,\dots,M_\kappa.✦ For forward kernels κ\kappa and ρ\rho, the composed kernel κ*ρ\kappa\ast\rho is the forward kernel that runs κ\kappa and then ρ\rho: its bound is Mκ+MρM_\kappa+M_\rho, and its law at aa is the pushforward, under the sum of offsets (t1,t2)↦t1+t2(t_1,t_2)\mapsto t_1+t_2, of the joint law that draws t1t_1 from κa\kappa_a and then t2t_2 from ρa+t1\rho_{a+t_1}, (κ*ρ)a(t)=∑t1+t2=tκa(t1)ρa+t1(t2).(\kappa\ast\rho)_a(t)=\sum_{t_1+t_2=t}\kappa_a(t_1)\,\rho_{a+t_1}(t_2).(3)✦

The smoothing kernel 𝒰N\mathcal{U}_N has bound NN and, at every time, the uniform law on {0,…,N}\{0,\dots,N\}.✦ The difference kernel Δn\Delta_n of the walk has bound nn. At a time aa it looks at the walk segment Ea={za,…,za+n}E_a=\{z_a,\dots,z_{a+n}\} and its difference set Ea−Ea={w−w′:w,w′∈Ea}E_a-E_a=\{w-w' : w,w'\in E_a\}, with a pair of times (td,td′)(t_d,t'_d) in {0,…,n}\{0,\dots,n\} chosen once for each d∈Ea−Ead\in E_a-E_a so that za+td−za+td′=dz_{a+t_d}-z_{a+t'_d}=d. The difference pair law draws dd uniformly and returns (td,td′)(t_d,t'_d)✦; the difference kernel tosses a fair coin besides and returns tdt_d on heads and td′t'_d on tails: (Δn)a(t)=#{d:td=t}+#{d:td′=t}2|Ea−Ea|.(\Delta_n)_a(t)=\frac{\#\{d : t_d=t\}+\#\{d : t'_d=t\}}{2\,|E_a-E_a|}.(4)✦

For a sequence 𝒏=(n1,…,nk)\mathbf{n}=(n_1,\dots,n_k) of phase lengths and a smoothing length NN, the common sampling schedule runs the difference kernels with these lengths in order and ends with the smoothing kernel: 𝒮(𝒏,N)=Δn1*(Δn2*⋯*(Δnk*𝒰N)).\mathcal{S}(\mathbf{n},N)=\Delta_{n_1}\ast\bigl(\Delta_{n_2}\ast\cdots\ast (\Delta_{n_k}\ast\mathcal{U}_N)\bigr).(5)✦ We write 𝒏𝒓\mathbf{n}\mathbf{r} for the sequence 𝒏\mathbf{n} followed by 𝒓\mathbf{r}, and Σ(𝒓)\Sigma(\mathbf{r}) for the sum of the entries of 𝒓\mathbf{r}.

For a forward kernel κ\kappa, a sequence zz of Gaussian integers, a time aa and a signed index ι\iota, the relative residue law μa,ικ\mu^\kappa_{a,\iota} is the law on ℤ[i]/(πι)\mathbb{Z}[i]/(\pi_\iota) of the class of za+t−zaz_{a+t}-z_a when tt is drawn from κa\kappa_a. With tt drawn from κa\kappa_a in the same way, faκ(s)f^\kappa_a(s) is the point entropy at ss of za+tz_{a+t}. For the schedule 𝒮(𝒏,N)\mathcal{S}(\mathbf{n},N), the terminal residue law at a time aa and a signed index ι\iota is the relative residue law μa,ι𝒮(𝒏,N)\mu^{\mathcal{S}(\mathbf{n},N)}_{a,\iota}.

The low residues of a finite probability law μ\mu on a finite set GG at a floor τ\tau form the set Lowτ(μ)={x∈G:μ(x)<τ/|G|},\mathrm{Low}_\tau(\mu)=\{x\in G : \mu(x)<\tau/|G|\},(6)✦ and on ℤ[i]/(πι)\mathbb{Z}[i]/(\pi_\iota), a group of pιp_\iota elements, the bound is τ/pι\tau/p_\iota.

For a forward kernel κ\kappa, a time aa, a floor τ\tau and thresholds u(ι)u(\iota) at the signed indices, the bad share Badaκ(τ,u)\mathrm{Bad}^\kappa_a(\tau,u) is the share of signed indices with at least u(ι)u(\iota) low residues: Badaκ(τ,u)=Prι[|Lowτ(μa,ικ)|≥u(ι)],\mathrm{Bad}^\kappa_a(\tau,u)=\Pr_\iota\bigl[\,|\mathrm{Low}_\tau(\mu^\kappa_{a,\iota})| \ge u(\iota)\,\bigr],(7) with ι\iota drawn from the uniform law on the 2mm2^m m signed indices.

Entropy Bands

For a ratio gg, an initial scale UU and an index j∈ℕj\in\mathbb{N}, the band scale, the band length and the band size are Sj=g2jU,Bj=⌊exp⁡(gSj)⌋,bj=⌊Sj/L*⌋.S_j=g^{2j}U,\qquad B_j=\bigl\lfloor \exp(gS_j)\bigr\rfloor,\qquad b_j=\lfloor S_j/L^*\rfloor .(8) The lattice ball of radius rr is the set of the KrK_r Gaussian integers ww with |w|≤r|w|\le r.✦

An entropy band for 𝒫\mathcal{P}, a step bound DD, a sequence 𝒏\mathbf{n} of phase lengths, a smoothing length NN, a number bb of primes and a deficit δ\delta consists of a ratio gg with 0<g≤1/2000<g\le 1/200, an initial scale U>0U>0, a number ll of bands and a cost rate γ\gamma such that, for some sequences 𝒙\mathbf{x} and 𝒚\mathbf{y}, the sequence 𝒏\mathbf{n} is 𝒙\mathbf{x}, then B0,…,Bl−1B_0,\dots,B_{l-1}, then 𝒚\mathbf{y}, with b=blb=b_l, 2(1+log⁡18)≤gSl,640L*≤g5Sl,log⁡16+log⁡max⁡(D,K4D)≤g2Sl,4log⁡D+2log⁡36≤4gSl,2log⁡16+4log⁡D≤Sl/4,⌊U/L*⌋≤m,log⁡36+2log⁡(D(Σ(𝒚)+N+1))≤γblL*,\begin{aligned} &2(1+\log 18)\le gS_l,\qquad 640L^*\le g^5S_l,\qquad \log 16+\log\max(D,K_{4D})\le g^2S_l,\\ &4\log D+2\log 36\le 4gS_l,\qquad 2\log 16+4\log D\le S_l/4,\qquad \lfloor U/L^*\rfloor\le m,\\ &\log 36+2\log\bigl(D(\Sigma(\mathbf{y})+N+1)\bigr)\le \gamma\,b_l\,L^*, \end{aligned}(9) and 2−l+80g+γ≤δ.2^{-l}+80g+\gamma\le\delta .(10)✦

Coverage Derivations

A coverage derivation for 𝒫\mathcal{P}, a step bound DD and a smoothing length NN is a relation Cov(𝒏;τ,u,η)\mathrm{Cov}(\mathbf{n};\tau,u,\eta) between a sequence 𝒏\mathbf{n} of phase lengths, a floor τ\tau, thresholds u(ι)u(\iota) at the signed indices and a rate η\eta, defined inductively by a base rule and a step rule.

By the base rule, Cov(𝒏;τ,u,η)\mathrm{Cov}(\mathbf{n};\tau,u,\eta) holds when, for some bb with 0<b≤m0<b\le m, some ee and some c>0c>0, there is an entropy band for 𝒏\mathbf{n} with smoothing length NN, bb primes and deficit ee, and τ≤38,8cpι≤u(ι)at every ι,eL*/c≤η.\tau\le\tfrac38,\qquad 8c\,p_\iota\le u(\iota)\ \text{at every }\iota,\qquad eL^*/c\le\eta .(11)✦

By the step rule, Cov(𝒏𝒓;τ,u,η)\mathrm{Cov}(\mathbf{n}\mathbf{r};\tau,u,\eta) holds when there are an integer bb with 0<b≤m0<b\le m, an integer R≥1R\ge 1, reals δ,ε,η′,e,v\delta,\varepsilon,\eta',e,v and thresholds u′(ι)u'(\iota), c(ι)c(\iota) such that Cov(𝒓;τ+4δ,u′,η′)\mathrm{Cov}(\mathbf{r};\tau+4\delta,u',\eta') holds, there is an entropy band for 𝒏\mathbf{n} with smoothing length 00, bb primes and deficit ee, and they satisfy 0≤τ≤38,0<δ≤164,ε≥0,η>0,η′+ε≤ηδ2,1≤Σ(𝒓)+N,2(1−log⁡ηδ2)≤v,eL*+R(log⁡36+2log⁡(D(Σ(𝒓)+N)))b<ηδv4,\begin{gathered} 0\le\tau\le\tfrac38,\quad 0<\delta\le\tfrac{1}{64},\quad \varepsilon\ge 0,\quad \eta>0,\quad \eta'+\varepsilon\le\tfrac{\eta\delta}{2},\quad 1\le\Sigma(\mathbf{r})+N,\\ 2\bigl(1-\log\tfrac{\eta\delta}{2}\bigr)\le v,\qquad eL^*+\frac{R\bigl(\log 36+2\log(D(\Sigma(\mathbf{r})+N))\bigr)}{b}<\frac{\eta\delta v}{4}, \end{gathered}(12) and, at every signed index ι\iota, u(ι)>0,c(ι)≥1,v≤log⁡pι−log⁡c(ι),u′(ι)δ≤c(ι),pιexp⁡(−Rδ2u(ι)2pι)≤ε.u(\iota)>0,\quad c(\iota)\ge 1,\quad v\le\log p_\iota-\log c(\iota),\quad \frac{u'(\iota)}{\delta}\le c(\iota),\quad p_\iota\exp\Bigl(-\frac{R\,\delta^2u(\iota)}{2p_\iota}\Bigr)\le\varepsilon .(13)

The coverage repetition count of a real number XX is R(X)=⌈exp⁡(X/100)⌉R(X)=\lceil\exp(X/100)\rceil.✦

The Claim

Theorem 1. Let 𝒫\mathcal{P} be a split prime sieve, DD a real number and NN a natural number, with Cov\mathrm{Cov} taken for 𝒫\mathcal{P}, DD and NN. Parts (i) to (iii) assume that 𝒫\mathcal{P} is nonempty with its primes in [T,2T][T,2T] for some T≥5T\ge 5, that L*≥1L^*\ge 1, and that zz is a self-avoiding walk in ℤ[i]\mathbb{Z}[i] with steps at most D≥1D\ge 1.

(i) If Cov(𝒏;τ,u,η)\mathrm{Cov}(\mathbf{n};\tau,u,\eta) holds, then for every start a≥0a\ge 0 Bada𝒮(𝒏,N)(τ,u)≤η.\mathrm{Bad}^{\mathcal{S}(\mathbf{n},N)}_a(\tau,u)\le\eta .(14)✦

(ii) If there is an entropy band for 𝒏\mathbf{n} with smoothing length NN, bb primes and deficit δ\delta, then at every time aa (1−δ)bL*≤fa𝒮(𝒏,N)(b).(1-\delta)\,b\,L^*\le f^{\mathcal{S}(\mathbf{n},N)}_a(b).(15)✦

(iii) If 0<g≤1/2000<g\le 1/200, U>0U>0, l∈ℕl\in\mathbb{N}, γ∈ℝ\gamma\in\mathbb{R} and sequences 𝒙\mathbf{x}, 𝒚\mathbf{y} satisfy (9), then for the sequence 𝒏\mathbf{n} made of 𝒙\mathbf{x}, then B0,…,Bl−1B_0,\dots,B_{l-1}, then 𝒚\mathbf{y}, at every time aa (1−2−l−80g−γ)blL*≤fa𝒮(𝒏,N)(bl).\bigl(1-2^{-l}-80g-\gamma\bigr)\,b_l\,L^*\le f^{\mathcal{S}(\mathbf{n},N)}_a(b_l).(16)✦

(iv) Let κ\kappa be a forward kernel, 𝒫\mathcal{P} nonempty, zz any sequence of Gaussian integers and aa a time. If 0<b≤m0<b\le m, τ≤3/8\tau\le 3/8, c>0c>0, 8cpι≤u(ι)8c\,p_\iota\le u(\iota) at every signed index ι\iota, and (1−e)bL*≤faκ(b)(1-e)\,b\,L^*\le f^\kappa_a(b), then Badaκ(τ,u)≤eL*/c.\mathrm{Bad}^\kappa_a(\tau,u)\le eL^*/c .(17)✦

(v) Suppose there are an entropy band for 𝒏\mathbf{n} with smoothing length 00, bb primes and deficit ee and one for 𝒓\mathbf{r} with smoothing length NN, qq primes and deficit e0e_0, where 0<b≤m0<b\le m, 0<q≤m0<q\le m and 1≤Σ(𝒓)+N1\le\Sigma(\mathbf{r})+N, and let R≥1R\ge 1 be an integer. If every signed index has pι≥exp⁡(100)p_\iota\ge\exp(100) and u(ι)>0u(\iota)>0, and e0L*≤exp⁡(−100)512⋅640000,eL*+R(log⁡36+2log⁡(D(Σ(𝒓)+N)))b<1256,pιexp⁡(−R(1/64)2u(ι)2pι)≤1640000at every ι,\begin{gathered} e_0L^*\le\frac{\exp(-100)}{512\cdot 640000},\qquad eL^*+\frac{R\bigl(\log 36+2\log(D(\Sigma(\mathbf{r})+N))\bigr)}{b}<\frac{1}{256},\\ p_\iota\exp\Bigl(-\frac{R\,(1/64)^2\,u(\iota)}{2p_\iota}\Bigr)\le\frac{1}{640000} \ \text{at every }\iota, \end{gathered}(18) then Cov(𝒏𝒓;14,u,1100).\mathrm{Cov}\bigl(\mathbf{n}\mathbf{r};\tfrac14,u,\tfrac{1}{100}\bigr).(19)✦

(vi) Suppose there are an entropy band for 𝒏\mathbf{n} with smoothing length 00, bb primes and deficit ee and one for 𝒓\mathbf{r} with smoothing length NN, qq primes and the same deficit ee, that L*>0L^*>0 and 1≤Σ(𝒓)+N1\le\Sigma(\mathbf{r})+N, and that X≥100X\ge 100 with exp⁡(X)≤pι≤2exp⁡(21X/20)\exp(X)\le p_\iota\le 2\exp(21X/20) at every signed index ι\iota. If eL*≤exp⁡(−100)512⋅640000,eL*≤11024,R(X)(log⁡36+2log⁡(D(Σ(𝒓)+N)))b≤11024,pιexp⁡(−R(X)(1/64)2pιexp⁡(−X/200)2pι)≤1640000at every ι,\begin{gathered} eL^*\le\frac{\exp(-100)}{512\cdot 640000},\qquad eL^*\le\frac{1}{1024},\qquad \frac{R(X)\bigl(\log 36+2\log(D(\Sigma(\mathbf{r})+N))\bigr)}{b}\le\frac{1}{1024},\\ p_\iota\exp\Bigl(-\frac{R(X)\,(1/64)^2\,p_\iota\exp(-X/200)}{2p_\iota}\Bigr) \le\frac{1}{640000}\ \text{at every }\iota, \end{gathered}(20) then Cov(𝒏𝒓;14,ι↦pιexp⁡(−X/200),1100).\mathrm{Cov}\bigl(\mathbf{n}\mathbf{r};\tfrac14,\ \iota\mapsto p_\iota\exp(-X/200),\ \tfrac{1}{100}\bigr).(21)✦

In the paper, the result reads: for all sufficiently large MM, uniformly over the batches, over 0≤i≤J0\le i\le J and over all exact start times a≥0a\ge 0 at AiA_i, all but a fraction at most ηi\eta_i of the signed primes π\pi satisfy #{x∈ℤ[i]/(π):bi,a,π(x)<τi/p}<p1−βi\#\{x\in\mathbb{Z}[i]/(\pi) : b_{i,a,\pi}(x)<\tau_i/p\}<p^{1-\beta_i}, where bi,a,πb_{i,a,\pi} is the terminal residue law modulo π\pi from the start aa.

The box counts the low residues against a threshold u(ι)u(\iota) in place of p1−βip^{1-\beta_i}, and (19) and (21) give the floor τ=1/4\tau=1/4 with the rate η=1/100\eta=1/100.

What Is Checked

The claims are stated over a split prime sieve with its signed indices, residue rings and mean log L*L^*; over a sequence of Gaussian integers, a self-avoiding walk with steps at most DD in (14), (15) and (16); and over forward kernels, the common sampling schedule (5), the relative residue laws and their low residues, the point entropy (2), entropy bands and coverage derivations.

Beyond the claims, the library proves that a nonempty sieve has a signed index✦, and that every element of the difference set of a walk segment {z0,…,zn}\{z_0,\dots,z_n\} is zt−zt′z_t-z_{t'} for some times t,t′≤nt,t'\le n.✦