OctoInformBeta

OpenAI preprint, September 2026 Β· Β§7. Zero avoidance costs information

Proposition 7.1: A batch certificate gives WL(t*)W_L(t^*) information at least rLrL on residues modulo the batch given those modulo FF; window schedules supply certificates

Avoiding a certified batch costs information.

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 𝒫\mathcal P be a finite set of rational primes p≑1(mod⁡4)p\equiv1\pmod4, with a chosen Gaussian prime Ο€p\pi_p of norm pp for each, and let z0,z1,…z_0,z_1,\dots be a self-avoiding walk in β„€[i]\mathbb Z[i] with steps at most DD that stays in A(𝒫)A(\mathcal P): none of its points is divisible by Ο€p\pi_p or by Ο€β€Ύp\bar\pi_p for pβˆˆπ’«p\in\mathcal P. Stop the walk at a random time t*t^* given by a sampling schedule and record two things there: the residues of zt*z_{t^*} modulo the factors Ο€p\pi_p and Ο€β€Ύp\bar\pi_p, and the word WL(t*)W_L(t^*) of the next LL steps. The question is how much the word must tell about these residues, measured by their conditional mutual information per letter, given the residues of zt*z_{t^*} modulo a finite set FF of nonzero Gaussian integers whose norms have a small sum of logarithms. A walk is a sequence z0,z1,…z_0,z_1,\dots of Gaussian integers; it is self-avoiding when its terms are distinct, and it has steps at most DD when |zt+1βˆ’zt|≀D|z_{t+1}-z_t|\le D for every tt.

A batch certificate records the numerical conditions on the finite set 𝒫\mathcal P of primes, called the batch, on the schedule and on the word length LL, for an error EE and a rate rr: the error bounds the sum of the logarithms of the norms in FF, and the rate is the information per letter that the certificate gives.

Batches and Residues

A split prime sieve, or batch, 𝒫\mathcal P is a finite set of rational primes p≑1(mod⁡4)p\equiv1\pmod4 together with, for each pβˆˆπ’«p\in\mathcal P, a Gaussian prime Ο€p\pi_p of norm pp.✦ The primes of a batch 𝒫\mathcal P are numbered once and for all as p1,…,p|𝒫|p_1,\dots,p_{|\mathcal P|}, the prime enumeration of 𝒫\mathcal P✦, and the mean log of 𝒫\mathcal P is L*=1|𝒫|βˆ‘klog⁡pkL^*=\frac1{|\mathcal P|}\sum_k\log p_k.✦ The avoiding set A(𝒫)A(\mathcal P) is the set of zβˆˆβ„€[i]z\in\mathbb Z[i] divisible by neither Ο€p\pi_p nor Ο€β€Ύp\bar\pi_p for any pβˆˆπ’«p\in\mathcal P✦, and the available factors of 𝒫\mathcal P are the Gaussian integers Ο€p\pi_p and Ο€β€Ύp\bar\pi_p for pβˆˆπ’«p\in\mathcal P.✦

A sign pattern Οƒβˆˆ{+,βˆ’}|𝒫|\sigma\in\{+,-\}^{|\mathcal P|} gives a sign to each position, and an ordering Ξ»\lambda is a permutation of the positions 1,…,|𝒫|1,\dots,|\mathcal P|. A signed index of 𝒫\mathcal P is a pair ΞΉ=(Οƒ,k)\iota=(\sigma,k) of a sign pattern and a position.✦ The prime of a signed index ΞΉ=(Οƒ,k)\iota=(\sigma,k) of 𝒫\mathcal P is pΞΉ=pkp_\iota=p_k, and its signed factor πι\pi_\iota is Ο€pk\pi_{p_k} if Οƒk=+\sigma_k=+ and Ο€β€Ύpk\bar\pi_{p_k} if Οƒk=βˆ’\sigma_k=-✦. For sβˆˆβ„•s\in\mathbb N, the selected factors Ξ s(Οƒ,Ξ»)\Pi_s(\sigma,\lambda) are the signed factors Ο€(Οƒ,Ξ»(1)),Ο€(Οƒ,Ξ»(2)),…\pi_{(\sigma,\lambda(1))}, \pi_{(\sigma,\lambda(2))},\dots of the first ss primes in the order Ξ»\lambda, all of them when sβ‰₯|𝒫|s\ge|\mathcal P|.

For a Gaussian integer Ο€\pi, the multiples of Ο€\pi form the subgroup Ο€β„€[i]\pi\,\mathbb Z[i]✦, and the residue of zβˆˆβ„€[i]z\in\mathbb Z[i] modulo Ο€\pi is its class zmod⁡Ο€z\bmod\pi in the quotient β„€[i]/(Ο€)\mathbb Z[i]/(\pi) by that subgroup✦. The residue ring of a signed index ΞΉ\iota is β„€[i]/(πι)\mathbb Z[i]/(\pi_\iota), a ring with pΞΉp_\iota elements.✦ For a finite set or family SS of Gaussian integers, zmod⁡Sz\bmod S is the vector of the residues of zz modulo the members of SS. The residue weight of a finite set FF of Gaussian integers is βˆ‘f∈Flog⁡N(f)\sum_{f\in F}\log N(f).✦

The dyadic batch of index jj is the set of primes p≑1(mod⁡4)p\equiv1\pmod4 with 2j≀p<2j+12^j\le p<2^{j+1}.✦ The chosen split factor of such a prime pp is one fixed choice Ο€p\pi_p among the Gaussian primes of norm pp.✦ The sieve of a finite set of primes p≑1(mod⁡4)p\equiv1\pmod4 is the batch on that set with the chosen split factors✦, and the dyadic sieve 𝒫j\mathcal P_j is the sieve of the dyadic batch of index jj✦.

Walks and Laws

For Dβ‰₯0D\ge0, the lattice ball BDB_D is the set of uβˆˆβ„€[i]u\in\mathbb Z[i] with |u|≀D|u|\le D; it has KDK_D elements.✦ The increment word of length LL at time tt of a walk zz is 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})✦; when the steps are at most DD it is a word of LL letters in BDB_D, the bounded increment word✦. The walk segment of length nn is the set {z0,…,zn}\{z_0,\dots,z_n\}✦, and the difference set of a finite set EβŠ‚β„€[i]E\subset\mathbb Z[i] is Eβˆ’E={wβˆ’wβ€²:w,wβ€²βˆˆE}E-E=\{w-w':w,w'\in E\}✦.

A finite probability law on a finite set Ξ©\Omega gives each point a nonnegative mass, the masses summing to 11.✦ The uniform law on Ξ©\Omega is the law that gives all points the same mass✦, and the point mass at Ο‰\omega is the law that gives Ο‰\omega the mass 11✦. The probability of an event is the total mass of the points where it holds✦, and the pushforward of a law along a map gives each value the mass of its preimage✦. The joint law of a law pp on Ξ©\Omega and laws q(Ο‰)q(\omega) on Ξ©β€²\Omega' is the law on Ω×Ω′\Omega\times\Omega' with mass p(Ο‰)q(Ο‰)(Ο‰β€²)p(\omega)\,q(\omega)(\omega') at (Ο‰,Ο‰β€²)(\omega,\omega'): draw Ο‰\omega from pp, then Ο‰β€²\omega' from q(Ο‰)q(\omega).✦

A random time on Ξ©\Omega is a map from Ξ©\Omega to β„•\mathbb N. For random variables XX, YY, OO on Ξ©\Omega, H(X)H(X) is the Shannon entropy of the law of XX✦, H(X∣O)=H(X,O)βˆ’H(O)H(X\mid O)=H(X,O)-H(O) is the conditional entropy✦, and the conditional mutual information is I(X;Y∣O)=H(X∣O)βˆ’H(X∣O,Y).I(X;Y\mid O)=H(X\mid O)-H(X\mid O,Y).(1)✦

For a sign pattern Οƒ\sigma, the residue vector of zβˆˆβ„€[i]z\in\mathbb Z[i] is (zmod⁡Ο€(Οƒ,k))k≀|𝒫|(z\bmod\pi_{(\sigma,k)})_{k\le|\mathcal P|}.✦ Under a law on Ξ©\Omega, the random-order prefix entropy at ss of a random vector with coordinates indexed by the positions is the mean, over the orderings Ξ»\lambda, of the entropy of its coordinates at Ξ»(1),…,Ξ»(s)\lambda(1),\dots,\lambda(s)✦, and the sign-averaged entropy of a family of random vectors indexed by sign patterns is the mean over Οƒ\sigma of their random-order prefix entropies.✦ The point entropy at ss of a random Gaussian integer ZZ is the sign-averaged entropy of its residue vectors: fZ(s)=𝔼σ𝔼λH(Zmod⁡Ξ s(Οƒ,Ξ»)),f_Z(s)=\mathbb E_\sigma\,\mathbb E_\lambda\,H\bigl(Z\bmod\Pi_s(\sigma,\lambda)\bigr),(2)✦

Schedules

A forward kernel RR of bound MM is a family of laws RaR_a, one for each time aβˆˆβ„•a\in\mathbb N, on the advances 0,…,M0,\dots,M.✦ The composite RRβ€²RR' of forward kernels of bounds MM and Mβ€²M' is the forward kernel of bound M+Mβ€²M+M' that advances from aa by uu drawn from RaR_a and then by vv drawn from Ra+uβ€²R'_{a+u}: its law at aa is the pushforward of the joint law along (u,v)↦u+v(u,v)\mapsto u+v.✦ The smoothing kernel UNU_N is the forward kernel of bound NN whose law at every time is the uniform law on 0,…,N0,\dots,N.✦

Let zz be a walk, nβˆˆβ„•n\in\mathbb N and aa a time, and let E={za,…,za+n}E=\{z_a,\dots,z_{a+n}\}. For d∈Eβˆ’Ed\in E-E, the chosen difference pair (ud,vd)(u_d,v_d) is a pair of advances in {0,…,n}\{0,\dots,n\} with za+udβˆ’za+vd=dz_{a+u_d}-z_{a+v_d}=d, fixed once and for all✦, and the difference law is the law of (ud,vd)(u_d,v_d) for dd uniform on Eβˆ’EE-E✦. The difference kernel Ξ”n\Delta_n is the forward kernel of bound nn whose law at aa is the law of udu_d or vdv_d, chosen by an independent fair coin.✦ The common sampling schedule of a sequence 𝒏=(n1,…,nk)\mathbf n=(n_1,\dots,n_k) of phase lengths with smoothing length NN is the composite C(𝒏;N)=Ξ”n1Ξ”n2β‹―Ξ”nkUN,C(\mathbf n;N)=\Delta_{n_1}\Delta_{n_2}\cdots\Delta_{n_k}U_N,(3)✦ which is UNU_N for the empty sequence; 𝒏𝒏′\mathbf n\mathbf n' denotes the concatenation of two sequences, and Ξ£(𝒏)=n1+…+nk\Sigma(\mathbf n)=n_1+\dots+n_k.

A time law is a law on {0,…,T0}\{0,\dots,T_0\} for some T0βˆˆβ„•T_0\in\mathbb N, the law of a random time.✦ The advance of a time law ΞΌ\mu by a forward kernel RR is the time law of b+tb+t with bb drawn from ΞΌ\mu and then tt from RbR_b, and Ξ΄a\delta_a is the time law with point mass at aa✦. The terminal time t𝒏,N*t^*_{\mathbf n,N} is the random time with the law of Ξ΄0\delta_0 advanced by C(𝒏;N)C(\mathbf n;N). The information of a time law about functions XX, YY, OO of time is I(X(t);Y(t)∣O(t))I(X(t);Y(t)\mid O(t)) for tt drawn from it.✦

Let KK be a forward kernel of bound MM, aa a time and Lβˆˆβ„•L\in\mathbb N, and let the walk have steps at most DD. The walk package at an advance uu is the pair Y=(za+uβˆ’za,WL(a+u))Y=(z_{a+u}-z_a,\,W_L(a+u)) of a displacement in BDMB_{DM} and a word of LL letters in BDB_D✦, and the package law of KK at aa is the law of YY for uu drawn from KaK_a✦. The relative residue law ρa,ΞΉK\rho^K_{a,\iota} is the law on β„€[i]/(πι)\mathbb Z[i]/(\pi_\iota) of the class of za+tβˆ’zaz_{a+t}-z_a for tt drawn from KaK_a.✦ The low residues of a law ΞΌ\mu on a finite set GG at a level Ο„\tau are the elements of probability less than Ο„/|G|\tau/|G|; on β„€[i]/(πι)\mathbb Z[i]/(\pi_\iota) they are the classes of probability below Ο„/pΞΉ\tau/p_\iota, and #LowΟ„(ΞΌ)\#\mathrm{Low}_\tau(\mu) is their number.✦

Certificates

For reals gg, xx and jβˆˆβ„•j\in\mathbb N, the band scale is Sj(g,x)=g2jxS_j(g,x)=g^{2j}x✦ and the band length is β„“j(g,x)=⌊exp⁡(gSj(g,x))βŒ‹\ell_j(g,x)=\lfloor\exp(g\,S_j(g,x))\rfloor✦; the band size of index jj for a batch is ⌊Sj(g,x)/L*βŒ‹\lfloor S_j(g,x)/L^*\rfloor✦.

Let 𝒫\mathcal P be a batch, DD a step bound, 𝒏\mathbf n a schedule, NN a smoothing length, bb a number of primes and Ξ΄\delta a deficit. An entropy band for these data consists of a ratio gg with 0<g≀1/2000<g\le1/200, a scale x>0x>0, a number ll of bands and a cost rate ee such that 𝒏\mathbf n is a prefix followed by β„“0(g,x),…,β„“lβˆ’1(g,x)\ell_0(g,x),\dots,\ell_{l-1}(g,x) and then a suffix 𝒔\mathbf s, bb is the band size ⌊S/L*βŒ‹\lfloor S/L^*\rfloor for S=Sl(g,x)S=S_l(g,x), ⌊x/L*βŒ‹β‰€|𝒫|\lfloor x/L^*\rfloor\le|\mathcal P|, and 2(1+log⁡18)≀gS,640L*≀g5S,log⁡16+log⁡max⁡(D,K4D)≀g2S,4log⁡D+2log⁡36≀4gS,2log⁡16+4log⁡D≀S/4,log⁡36+2log⁡(D(Ξ£(𝒔)+N+1))≀ebL*,2βˆ’l+80g+e≀δ.\begin{gathered} 2(1+\log18)\le gS,\qquad 640L^*\le g^5S,\qquad \log16+\log\max(D,K_{4D})\le g^2S,\\ 4\log D+2\log36\le4gS,\qquad 2\log16+4\log D\le S/4,\\ \log36+2\log\bigl(D(\Sigma(\mathbf s)+N+1)\bigr)\le e\,b\,L^*,\qquad 2^{-l}+80g+e\le\delta. \end{gathered}(4)✦

Fix a batch 𝒫\mathcal P, a step bound DD and a smoothing length NN. A threshold function uu gives a real number u(ΞΉ)u(\iota) to each signed index ΞΉ\iota. The coverage derivation relation Cov(𝒏,Ο„,u,Ξ·)\mathrm{Cov}(\mathbf n,\tau,u,\eta), between a schedule 𝒏\mathbf n, a floor Ο„\tau, a threshold function uu and an exception rate Ξ·\eta, is defined inductively by two rules. By the base rule, it holds when there are bβˆˆβ„•b\in\mathbb N with 0<b≀|𝒫|0<b\le|\mathcal P|, a real ee with an entropy band for 𝒏\mathbf n, NN, bb and ee, and a real c>0c>0 such that τ≀38,8cpι≀u(ΞΉ)for every signed index ΞΉ,eL*/c≀η.\tau\le\tfrac38,\qquad 8c\,p_\iota\le u(\iota)\ \text{for every signed index }\iota,\qquad eL^*/c\le\eta.(5)✦ By the step rule, Cov(𝒏𝒏′,Ο„,u,Ξ·)\mathrm{Cov}(\mathbf n\mathbf n',\tau,u,\eta) holds when there are n,bβˆˆβ„•n,b\in\mathbb N, reals Ξ΄,Ξ΅,Ξ·β€²,e,v\delta,\varepsilon,\eta',e,v and threshold functions uβ€²u' and cc with the following properties: there is an entropy band for 𝒏\mathbf n, smoothing length 00, bb and ee; Cov(𝒏′,Ο„+4Ξ΄,uβ€²,Ξ·β€²)\mathrm{Cov}(\mathbf n',\tau+4\delta,u',\eta') holds; n>0n>0, 0<b≀|𝒫|0<b\le|\mathcal P|, 0≀τ≀3/80\le\tau\le3/8, 0<δ≀1/640<\delta\le1/64, Ξ΅β‰₯0\varepsilon\ge0, Ξ·>0\eta>0 and 1≀Σ(𝒏′)+N1\le\Sigma(\mathbf n')+N; Ξ·β€²+Ρ≀ηδ/2,2(1βˆ’log⁡(Ξ·Ξ΄/2))≀v,eL*+n(log⁡36+2log⁡(D(Ξ£(𝒏′)+N)))/b<Ξ·Ξ΄v/4,\begin{gathered} \eta'+\varepsilon\le\eta\delta/2,\qquad 2\bigl(1-\log(\eta\delta/2)\bigr)\le v,\\ eL^*+n\bigl(\log36+2\log(D(\Sigma(\mathbf n')+N))\bigr)/b<\eta\delta v/4, \end{gathered}(6) and every signed index ΞΉ\iota has u(ΞΉ)>0u(\iota)>0, c(ΞΉ)β‰₯1c(\iota)\ge1, 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^2u(\iota)/(2p_\iota))\le\varepsilon.

Let DD be a step bound, 𝒏\mathbf n a schedule, NN a smoothing length, 𝒫\mathcal P a batch, LL a word length, EE an error and rr a rate. A batch certificate for (D,𝒏,N,𝒫,L,E,r)(D,\mathbf n,N,\mathcal P,L,E,r) consists of a splitting 𝒏=𝒏′𝒏″\mathbf n=\mathbf n'\mathbf n'', a scale Tβ‰₯5T\ge5, a number bb of primes, a number nn of repetitions, a floor Ο„\tau, a gain Ξ³\gamma, an exception rate Ξ·\eta, a deficit Ξ΄\delta and a threshold function uβ‰₯0u\ge0 with the following properties: 𝒫\mathcal P is nonempty, T≀p≀2TT\le p\le2T for every pβˆˆπ’«p\in\mathcal P, L*β‰₯1L^*\ge1, b≀|𝒫|b\le|\mathcal P|, n>0n>0, Ο„β‰₯0\tau\ge0, Ξ³β‰₯0\gamma\ge0 and L>0L>0; there are an entropy band for 𝒏′\mathbf n', smoothing length 00, bb and Ξ΄\delta, and a coverage derivation Cov(𝒏″,Ο„,u,Ξ·)\mathrm{Cov}(\mathbf n'',\tau,u,\eta); every signed index ΞΉ\iota satisfies the smoothing conditions L≀N,(DL)2<pΞΉ,LN+1≀τ2pΞΉL\le N,\qquad (DL)^2<p_\iota,\qquad \frac{L}{N+1}\le\frac{\tau}{2p_\iota}(7) and the list bound log⁡(4u(ΞΉ)+pΞΉexp⁡(βˆ’nLΟ„8pΞΉ))≀log⁡pΞΉβˆ’Ξ³;\log\Bigl(4u(\iota)+p_\iota\exp\Bigl(-\frac{nL\tau}{8p_\iota}\Bigr)\Bigr)\le\log p_\iota-\gamma;(8) and the rate bound n(Lr+2log⁡36+4log⁡(D(Ξ£+N)))≀b(Ξ³(1βˆ’2Ξ·)βˆ’Ξ΄L*)βˆ’En\bigl(Lr+2\log36+4\log(D(\Sigma+N))\bigr)\le b\bigl(\gamma(1-2\eta)-\delta L^*\bigr)-E(9)✦ holds with Ξ£=Ξ£(𝒏″)\Sigma=\Sigma(\mathbf n''). The set of batch certificates for (D,𝒏,N,𝒫,L,E,r)(D,\mathbf n,N,\mathcal P,L,E,r) is denoted Cert(D,𝒏,N,𝒫,L,E,r)\mathrm{Cert}(D,\mathbf n,N,\mathcal P,L,E,r).

The Window Schedule

The top parameter is g0=10βˆ’6g_0=10^{-6}.✦ For Ξ±>0\alpha>0 and jβˆˆβ„•j\in\mathbb N, the top block 𝒯α(j)\mathcal T_\alpha(j) is the sequence of the band lengths β„“0(g0,2jΞ±),…,β„“19(g0,2jΞ±)\ell_0(g_0,2^j\alpha),\dots,\ell_{19}(g_0,2^j\alpha)✦, twenty being the top iteration count✦, and for a finite set JβŠ‚β„•J\subset\mathbb N the top blocks 𝒯α(J)\mathcal T_\alpha(J) are the concatenation of the 𝒯α(j)\mathcal T_\alpha(j), j∈Jj\in J, in decreasing order of jj✦. For mβˆˆβ„•m\in\mathbb N the accurate grid is gm=exp⁡(βˆ’m2)g_m=\exp(-m^2)✦, and for a real number cc the accurate block π’œm(c)\mathcal A_m(c) is the sequence of the band lengths β„“i(gm,exp⁡(cem))\ell_i(g_m,\exp(c\,\mathrm e^m)) for 0≀i<4m20\le i<4m^2✦, the accurate iteration count being 4m24m^2✦. For Vβˆˆβ„•V\in\mathbb N and finite sets J(0),…,J(Vβˆ’1)βŠ‚β„•J(0),\dots,J(V-1)\subset\mathbb N, the window blocks are 𝒯α(J(w))\mathcal T_\alpha(J(w)) followed by π’œm(100w/4)\mathcal A_m(100^w/4), for ww from Vβˆ’1V-1 down to 00✦, and the common block list is the window blocks followed by π’œm(1/20)\mathcal A_m(1/20): 𝒏α(m,V,J)=𝒯α(J(Vβˆ’1))π’œm(100Vβˆ’1/4)⋯𝒯α(J(0))π’œm(1/4)π’œm(1/20).\mathbf n_\alpha(m,V,J)=\mathcal T_\alpha(J(V-1))\,\mathcal A_m(100^{V-1}/4)\cdots \mathcal T_\alpha(J(0))\,\mathcal A_m(1/4)\,\mathcal A_m(1/20).(10)✦ The window smoothing length is NV,m=⌈exp⁡(20β‹…100Vem)βŒ‰N_{V,m}=\lceil\exp(20\cdot100^V\mathrm e^m)\rceil✦, the word length of the dyadic batch of index jj is Lj=2⌊2j/5βŒ‹L_j=2^{\lfloor2j/5\rfloor}✦, and the top coefficient of Ξ±\alpha is cΞ±=(g02)20Ξ±=10βˆ’240Ξ±c_\alpha=(g_0^2)^{20}\alpha=10^{-240}\alpha✦.

The Claim

Theorem 1. In (a) to (e), 𝒫\mathcal P is a batch and z0,z1,…z_0,z_1,\dots is a self-avoiding walk with steps at most DD whose points all lie in A(𝒫)A(\mathcal P), with Dβ‰₯1D\ge1 in (a) to (c) and Dβ‰₯0D\ge0 in (d) and (e).

(a) Suppose a batch certificate for (D,𝒏,N,𝒫,L,E,r)(D,\mathbf n,N,\mathcal P,L,E,r) exists, and let FF be a finite set of nonzero Gaussian integers of residue weight at most EE. Then there is a finite set GG of Gaussian integers with FβŠ†GβŠ†Fβˆͺ{Ο€p,Ο€β€Ύp:pβˆˆπ’«}F\subseteq G\subseteq F\cup\{\pi_p,\bar\pi_p:p\in\mathcal P\} such that, for the terminal time t=t𝒏,N*t=t^*_{\mathbf n,N}, r≀1LI(ztmod⁡G;WL(t)|ztmod⁡F).r\le\frac1L\,I\bigl(z_t\bmod G;\,W_L(t)\mathrel{\big|}z_t\bmod F\bigr).(11)✦

(b) Suppose the splitting 𝒏′𝒏″\mathbf n'\mathbf n'' together with TT, bb, nn, Ο„\tau, Ξ³\gamma, Ξ·\eta, Ξ΄\delta and uu forms a batch certificate for (D,𝒏′𝒏″,N,𝒫,L,E,r)(D,\mathbf n'\mathbf n'',N,\mathcal P,L,E,r), and let 𝒇\mathbf f be a family of Gaussian integers with H(ztβ€²mod⁡𝒇)≀EH(z_{t'}\bmod\mathbf f)\le E for the terminal time tβ€²=t𝒏′,0*t'=t^*_{\mathbf n',0}. Then there are a sign pattern Οƒ\sigma and an ordering Ξ»\lambda such that, for t=t𝒏′𝒏″,N*t=t^*_{\mathbf n'\mathbf n'',N}, r≀1LI(ztmod⁡Ξ b(Οƒ,Ξ»);WL(t)|ztmod⁡𝒇).r\le\frac1L\,I\bigl(z_t\bmod\Pi_b(\sigma,\lambda);\,W_L(t)\mathrel{\big|}z_t\bmod\mathbf f\bigr).(12)✦

(c) Let 𝒫\mathcal P be nonempty, pp a law on a finite set Ξ©\Omega, aa a random time on Ξ©\Omega, 𝒇\mathbf f a family of Gaussian integers and RR a forward kernel of bound MM, and write zaz_a for za(Ο‰)z_{a(\omega)}. Let b≀|𝒫|b\le|\mathcal P|, n>0n>0, L>0L>0, NN, Ο„β‰₯0\tau\ge0, Ξ³β‰₯0\gamma\ge0, Ξ·\eta, Ξ΄\delta, EE, rr and a threshold function uβ‰₯0u\ge0 satisfy (7) and (8) at every signed index and (9) with Ξ£=M\Sigma=M. Suppose that, under pp, fza(b)β‰₯(1βˆ’Ξ΄)bL*f_{z_a}(b)\ge(1-\delta)\,b\,L^*, H(zamod⁡𝒇)≀EH(z_a\bmod\mathbf f)\le E, and the mean over the signed indices ΞΉ\iota of Pr⁡(#LowΟ„(ρa,ΞΉRUN)β‰₯u(ΞΉ))\Pr\bigl(\#\mathrm{Low}_\tau(\rho^{RU_N}_{a,\iota})\ge u(\iota)\bigr) is at most Ξ·\eta. Then there are Οƒ\sigma and Ξ»\lambda such that r≀1LI(za+tmod⁡Ξ b(Οƒ,Ξ»);WL(a+t)|za+tmod⁡𝒇),r\le\frac1L\,I\bigl(z_{a+t}\bmod\Pi_b(\sigma,\lambda);\,W_L(a+t)\mathrel{\big|} z_{a+t}\bmod\mathbf f\bigr),(13)✦ where Ο‰\omega is drawn from pp, then tt from (RUN)a(Ο‰)(RU_N)_{a(\omega)}, and a=a(Ο‰)a=a(\omega).

(d) Let 𝒫\mathcal P, pp, aa and RR be as in (c) and OO a random variable on Ξ©\Omega with values in a finite set, and let b≀|𝒫|b\le|\mathcal P|, L,N,nβˆˆβ„•L,N,n\in\mathbb N, Ο„β‰₯0\tau\ge0, Ξ³β‰₯0\gamma\ge0, Ξ·\eta, Ξ΄\delta, EE and a threshold function uβ‰₯0u\ge0 satisfy (7) and (8) at every signed index. Suppose that, under pp, fza(b)β‰₯(1βˆ’Ξ΄)bL*f_{z_a}(b)\ge(1-\delta)\,b\,L^*, H(O)≀EH(O)\le E, and the mean over the signed indices ΞΉ\iota of Pr⁡(#LowΟ„(ρa,ΞΉRUN)β‰₯u(ΞΉ))\Pr\bigl(\#\mathrm{Low}_\tau(\rho^{RU_N}_{a,\iota})\ge u(\iota)\bigr) is at most Ξ·\eta. Then b(Ξ³(1βˆ’2Ξ·)βˆ’Ξ΄L*)βˆ’E≀n𝔼σ𝔼λI(zamod⁡Ξ b(Οƒ,Ξ»);Y|O),b\bigl(\gamma(1-2\eta)-\delta L^*\bigr)-E\le n\,\mathbb E_\sigma\,\mathbb E_\lambda\, I\bigl(z_a\bmod\Pi_b(\sigma,\lambda);\,Y\mathrel{\big|}O\bigr),(14)✦ where Ο‰\omega is drawn from pp, then YY from the package law of RUNRU_N at a(Ο‰)a(\omega) for words of length LL, a=a(Ο‰)a=a(\omega), and Οƒ\sigma and Ξ»\lambda are uniform.

(e) Let pp be a law on a finite set Ξ©\Omega, aa a random time on Ξ©\Omega, RR a forward kernel and OO a random variable on Ξ©\Omega with values in a finite set, and let ΞΉ1,…,ΞΉs\iota_1,\dots,\iota_s be signed indices with factors Ξ =(πι1,…,πιs)\Pi=(\pi_{\iota_1},\dots,\pi_{\iota_s}). Let L,N,nβˆˆβ„•L,N,n\in\mathbb N, Ο„β‰₯0\tau\ge0, Ξ³β‰₯0\gamma\ge0, reals H0H_0 and Ξ·\eta and thresholds u1,…,usβ‰₯0u_1,\dots,u_s\ge0 satisfy (7) and (8) at each ΞΉq\iota_q with u(ΞΉq)=uqu(\iota_q)=u_q. Suppose that, under pp, H(zamod⁡Π∣O)β‰₯βˆ‘qlog⁡pΞΉqβˆ’H0H(z_a\bmod\Pi\mid O)\ge\sum_q\log p_{\iota_q}-H_0 and βˆ‘qPr⁡(#LowΟ„(ρa,ΞΉqRUN)β‰₯uq)≀η\sum_q\Pr\bigl(\#\mathrm{Low}_\tau(\rho^{RU_N}_{a,\iota_q})\ge u_q\bigr)\le\eta. Then, with Ο‰\omega, YY and aa as in (d), Ξ³(sβˆ’2Ξ·)βˆ’H0≀nI(zamod⁡Ξ ;Y|O).\gamma(s-2\eta)-H_0\le n\,I\bigl(z_a\bmod\Pi;\,Y\mathrel{\big|}O\bigr).(15)✦

(f) Let Dβ‰₯1D\ge1, 0<α≀10<\alpha\le1, ΞΈβ‰₯2Ξ±\theta\ge2\alpha and ΞΊβˆˆβ„•\kappa\in\mathbb N with α≀2ΞΊcΞ±\alpha\le2^\kappa c_\alpha, and let w<Vw<V be natural numbers. Then for all sufficiently large mm the following holds. If J(0),…,J(Vβˆ’1)J(0),\dots,J(V-1) are finite sets of natural numbers such that every j∈J(i)j\in J(i), for every i<Vi<V, satisfies 100iem≀jlog⁡2≀2120100iem100^i\mathrm e^m\le j\log2\le\frac{21}{20}\,100^i\mathrm e^m and |𝒫j|β‰₯ΞΈ2j/log⁡2j+1|\mathcal P_j|\ge\theta\,2^j/\log2^{j+1}, and any two distinct elements of J(w)J(w) differ by at least ΞΊ\kappa, then for every j∈J(w)j\in J(w) and every E≀cΞ±2j/(4β‹…104)E\le c_\alpha2^j/(4\cdot10^4) Cert(D,𝒏α(m,V,J),NV,m,𝒫j,Lj,E,cΞ±4β‹…107log⁡2j)β‰ βŒ€.\mathrm{Cert}\Bigl(D,\ \mathbf n_\alpha(m,V,J),\ N_{V,m},\ \mathcal P_j,\ L_j,\ E,\ \frac{c_\alpha}{4\cdot10^7\log2^j}\Bigr)\neq\varnothing.(16)✦

In the paper, the batch ℬT\mathcal B_T consists of the primes p≑1(mod⁡4)p\equiv1\pmod4 in [T,2T][T,2T]. In the paper, the result reads: there is c1>0c_1>0, depending only on the fixed schedule parameters, such that for all sufficiently large MM and every batch ℬT\mathcal B_T, 1LTπ”Όπ’žI(XTβ€²;WLT(t*)∣OTβ€²)β‰₯c1/log⁡T\frac1{L_T}\mathbb E_{\mathcal C}\,I(X'_T;W_{L_T}(t^*)\mid O'_T)\ge c_1/\log T, uniformly over all infinite self-avoiding walks with steps at most DD in A(𝒫M)A(\mathcal P_M).

The library states the bound in existential form, for one set GG of factors, and on the dyadic sieves 𝒫j\mathcal P_j in place of the batches ℬT\mathcal B_T.

What Is Checked

The claim is stated over batches of split primes with their signed factors, residues and avoiding set, self-avoiding walks with steps at most DD in that set and their increment words, the entropy and conditional mutual information of finite probability laws, forward kernels with the common sampling schedules and terminal times built from them, entropy bands, coverage derivations and batch certificates, and, in (16), the dyadic sieves and the window schedule (10).

Of these constructions the library also proves that every element of the difference set of a walk segment {z0,…,zn}\{z_0,\dots,z_n\} is zuβˆ’zvz_u-z_v for some times u,v≀nu,v\le n.✦