OctoInformBeta

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

Proof of Theorem 1.2: For every D≥1D\ge 1 there is a sieve certificate, and no self-avoiding walk with steps at most DD stays in all its avoiding sets

Sieve certificates on dyadic batches and the walks they exclude.

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

Fix a real number D≥1D\ge 1. A walk z0,z1,…z_0,z_1,\dots in ℤ[i]\mathbb{Z}[i] has steps at most DD when |zt+1−zt|≤D|z_{t+1}-z_t|\le D for every tt, the distance being taken in ℂ\mathbb{C}, and it is self-avoiding when its terms are distinct. A split prime sieve is a finite set 𝒫\mathcal{P} of rational primes p≡1(mod⁡4)p\equiv 1\pmod 4 together with a Gaussian prime πp\pi_p of norm pp for each p∈𝒫p\in\mathcal{P}.✦ The avoiding set A(𝒫)A(\mathcal{P}) of a split prime sieve 𝒫\mathcal{P}, where π‾p\bar\pi_p is the conjugate of πp\pi_p, is A(𝒫)={z∈ℤ[i]:πp∤zandπ‾p∤zfor everyp∈𝒫}.A(\mathcal{P})=\{z\in\mathbb{Z}[i] : \pi_p\nmid z\ \text{and}\ \bar\pi_p\nmid z\ \text{for every}\ p\in\mathcal{P}\}.(1)✦

In the proof of Theorem 1.2 of the paper, the question is which families of such sieves, one on each of several batches of primes, leave no self-avoiding walk with steps at most DD inside all their avoiding sets. The library’s answer is the sieve certificate for DD, a system of dyadic batches, word lengths, rates and an error tied together by explicit inequalities.

Batches, Factors and Weights

For a prime p≡1(mod⁡4)p\equiv 1\pmod 4, the chosen split factor πp\pi_p is one fixed Gaussian prime of norm pp✦, and the sieve of a finite set of such primes pairs each of them with its chosen split factor.✦ The dyadic batch of index kk is the set of primes Bk={p:p≡1(mod⁡4),2k≤p<2k+1},B_k=\{p : p\equiv 1\pmod 4,\ 2^k\le p<2^{k+1}\},(2)✦ and the dyadic sieve of index kk is the sieve of BkB_k.✦

Let 𝒫\mathcal{P} be a split prime sieve. The signed factor of a Gaussian integer π\pi with sign ++ is π\pi, and with sign −- it is π‾\bar\pi.✦ The available factors of 𝒫\mathcal{P} form the set {πp,π‾p:p∈𝒫}\{\pi_p,\bar\pi_p : p\in\mathcal{P}\}.✦ The enumeration of 𝒫\mathcal{P} numbers its primes once and for all as p0,…,p|𝒫|−1p_0,\dots,p_{|\mathcal{P}|-1}.✦ A signed index of 𝒫\mathcal{P} is a pair ι=(σ,q)\iota=(\sigma,q) of a sign pattern σ\sigma, which gives each position 0,…,|𝒫|−10,\dots,|\mathcal{P}|-1 a sign ++ or −-, and a position qq✦; the prime of ι\iota is pι=pqp_\iota=p_q✦. The mean log of 𝒫\mathcal{P} is L*=|𝒫|−1∑p∈𝒫log⁡pL^*=|\mathcal{P}|^{-1}\sum_{p\in\mathcal{P}}\log p.✦

The residue weight of a finite set FF of Gaussian integers is ρ(F)=∑f∈Flog⁡(ff‾),\rho(F)=\sum_{f\in F}\log(f\bar f),(3)✦ where the norm ff‾f\bar f of a nonzero ff is the number of residues modulo ff. For a sequence of split prime sieves 𝒫0,𝒫1,…\mathcal{P}_0,\mathcal{P}_1,\dots, the factors preceding index jj form the set Π<j\Pi_{<j} of all available factors of 𝒫0,…,𝒫j−1\mathcal{P}_0,\dots,\mathcal{P}_{j-1}.✦

The lattice ball of radius DD is the set of u∈ℤ[i]u\in\mathbb{Z}[i] with |u|≤D|u|\le D, and KDK_D is its number of elements.✦ Logarithms are natural, and h(x)=−xlog⁡x−(1−x)log⁡(1−x)h(x)=-x\log x-(1-x)\log(1-x) is the binary entropy.

Certificates and Parameters

A low residue of a law on ℤ[i]/(π)\mathbb{Z}[i]/(\pi), a group of pp elements, is a class of probability below τ/p\tau/p, for a floor τ\tau.

A schedule ν\nu is a list of phase lengths, and a smoothing length NN is a number attached to it. An entropy band for a split prime sieve 𝒫\mathcal{P}, a schedule ν\nu, a smoothing length NN, a number bb of primes and a deficit δ\delta consists of a ratio 0<g≤1/2000<g\le 1/200, a scale U>0U>0, a number ℓ\ell of bands and a cost rate μ\mu, such that ν\nu is a prefix, followed by the band lengths ⌊egSi⌋\lfloor e^{gS_i}\rfloor for 0≤i<ℓ0\le i<\ell, where Si=g2iUS_i=g^{2i}U is the band scale, followed by a suffix of sum Σ\Sigma, and such that b=⌊Sℓ/L*⌋b=\lfloor S_\ell/L^*\rfloor is the band size.✦ Moreover, with S=SℓS=S_\ell and MM the larger of DD and the number of points of the lattice ball of radius 4D4D, one has 2(1+log⁡18)≤gS2(1+\log 18)\le gS, 640L*≤g5S640L^*\le g^5S, log⁡16+log⁡M≤g2S\log 16+\log M\le g^2S, 4log⁡D+2log⁡36≤4gS4\log D+2\log 36\le 4gS, 2log⁡16+4log⁡D≤S/42\log 16+4\log D\le S/4, ⌊U/L*⌋≤|𝒫|\lfloor U/L^*\rfloor\le|\mathcal{P}|, log⁡36+2log⁡(D(Σ+N+1))≤μbL*\log 36+2\log(D(\Sigma+N+1))\le\mu\,b\,L^* and 2−ℓ+80g+μ≤δ2^{-\ell}+80g+\mu\le\delta.✦

A coverage derivation for a split prime sieve 𝒫\mathcal{P}, a step bound DD and a smoothing length NN is a relation between a list ν\nu of phase lengths, a floor τ\tau, thresholds u(ι)u(\iota) for the counts of low residues at the signed indices ι\iota and an exception rate η\eta, defined by two rules.✦ By the base rule it holds when there are a number bb of primes with 0<b≤|𝒫|0<b\le|\mathcal{P}|, an entropy band on ν\nu with smoothing length NN, bb primes and deficit ee, and a constant c>0c>0, such that τ≤3/8\tau\le 3/8, 8cpι≤u(ι)8c\,p_\iota\le u(\iota) for every ι\iota and eL*/c≤ηeL^*/c\le\eta.✦ By the step rule it holds for ν\nu followed by a list 𝑟𝑒𝑠𝑡\mathit{rest} of sum Σ\Sigma, at floor τ\tau with thresholds uu and rate η\eta, when there are numbers bb and nn, reals δ\delta, ε\varepsilon, η′\eta', ee, vv, and thresholds u′u' and cc at the signed indices, with an entropy band on ν\nu with smoothing length 00, bb primes and deficit ee, and a coverage derivation of 𝑟𝑒𝑠𝑡\mathit{rest} at floor τ+4δ\tau+4\delta with thresholds u′u' and rate η′\eta', such that 1≤Σ+N1\le\Sigma+N, n>0n>0, 0<b≤|𝒫|0<b\le|\mathcal{P}|, 0≤τ≤3/80\le\tau\le 3/8, 0<δ≤1/640<\delta\le 1/64, ε≥0\varepsilon\ge 0, η>0\eta>0, η′+ε≤ηδ/2\eta'+\varepsilon\le\eta\delta/2, 2(1−log⁡(ηδ/2))≤v2(1-\log(\eta\delta/2))\le v and eL*+n(log⁡36+2log⁡(D(Σ+N)))/b<ηδv/4eL^*+n(\log 36+2\log(D(\Sigma+N)))/b<\eta\delta v/4, and such that every signed index ι\iota has u(ι)>0u(\iota)>0, c(ι)≥1c(\iota)\ge 1, 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.✦

A word length LL is the length of the increment words (zt+1−zt,…,zt+L−zt+L−1)(z_{t+1}-z_t,\dots,z_{t+L}-z_{t+L-1}) of a walk. A batch certificate for DD, a schedule ν\nu, a smoothing length NN, a split prime sieve 𝒫\mathcal{P}, a word length LL, an error EE and a rate rr consists of: a splitting of ν\nu, a list of phase lengths, into a prefix followed by a remainder of sum Σ\Sigma; a scale T≥5T\ge 5 such that 𝒫\mathcal{P} is nonempty, lies in [T,2T][T,2T] and has L*≥1L^*\ge 1; natural numbers b≤|𝒫|b\le|\mathcal{P}| and n>0n>0, a floor τ≥0\tau\ge 0, a gain γ≥0\gamma\ge 0, an exception rate η\eta, a deficit δ\delta and thresholds u(ι)≥0u(\iota)\ge 0 for the counts of low residues at the signed indices ι\iota; an entropy band on the prefix with smoothing length 00, bb primes and deficit δ\delta; and a coverage derivation of the remainder at floor τ\tau with thresholds uu and exception rate η\eta.✦ These are subject to 0<L≤N0<L\le N, to (DL)2<pι(DL)^2<p_\iota, L/(N+1)≤τ/(2pι)L/(N+1)\le\tau/(2p_\iota) and the list bound log⁡(4u(ι)+pιe−nLτ/(8pι))≤log⁡pι−γ\log\bigl(4u(\iota)+p_\iota\,e^{-nL\tau/(8p_\iota)}\bigr)\le\log p_\iota-\gamma(4) at every signed index ι\iota, and to the rate bound n(Lr+2log⁡36+4log⁡(D(Σ+N)))≤b(γ(1−2η)−δL*)−E.n\bigl(Lr+2\log 36+4\log(D(\Sigma+N))\bigr)\le b\bigl(\gamma(1-2\eta)-\delta L^*\bigr)-E.(5)

A sieve certificate for DD consists of a schedule ν\nu, a smoothing length NN, a last index mm, batch indices k0,k1,…k_0,k_1,\dots, word lengths L0,L1,…L_0,L_1,\dots, rates r0,r1,…r_0,r_1,\dots and an error ε≥0\varepsilon\ge 0 such that, with 𝒫j\mathcal{P}_j the dyadic sieve of index kjk_j, every j≤mj\le m has a batch certificate for DD, ν\nu, NN, 𝒫j\mathcal{P}_j, word length LjL_j, error ρ(Π<j)\rho(\Pi_{<j}) and rate rjr_j, every j<mj<m has Lj∣Lj+1L_j\mid L_{j+1} and the smoothing bound 2h(sN+1)+sN+1(Ljlog⁡KD+2ρ(Π<m+1))≤ε(0≤s<Lj+1),2h\Bigl(\frac{s}{N+1}\Bigr)+\frac{s}{N+1}\bigl(L_j\log K_D+2\rho(\Pi_{<m+1})\bigr)\le\varepsilon \qquad(0\le s<L_{j+1}),(6) and the excess bound log⁡KD+mε<∑j=0mrj\log K_D+m\varepsilon<\sum_{j=0}^{m}r_j(7)✦ holds. We write 𝒞(D)\mathcal{C}(D) for the set of sieve certificates for DD.

The top coefficient of a real number aa is κ(a)=(g02)20a\kappa(a)=(g_0^2)^{20}a✦, where g0=10−6g_0=10^{-6} is the top parameter✦ and 2020 the top iteration count.✦

The Claim

Theorem 1.

  1. Let D≥1D\ge 1, and let ν\nu, NN, mm, L0,L1,…L_0,L_1,\dots, r0,r1,…r_0,r_1,\dots and ε≥0\varepsilon\ge 0 meet the conditions of a sieve certificate for DD with arbitrary split prime sieves 𝒫0,𝒫1,…\mathcal{P}_0,\mathcal{P}_1,\dots in place of the dyadic sieves. Then every self-avoiding walk z0,z1,…z_0,z_1,\dots with steps at most DD satisfies zt∉A(𝒫0)∩…∩A(𝒫m)for some t.z_t\notin A(\mathcal{P}_0)\cap\dots\cap A(\mathcal{P}_m)\quad\text{for some } t.(8)✦

  2. Let Y0⊆Y1⊆⋯Y_0\subseteq Y_1\subseteq\cdots be finite sets of Gaussian integers, mm a natural number and R0,R1,…R_0,R_1,\dots relations between finite sets of Gaussian integers, such that for every j≤mj\le m each F⊆YjF\subseteq Y_j is contained in some G⊆Yj+1G\subseteq Y_{j+1} with Rj(F,G)R_j(F,G). Then there are finite sets F0⊆F1⊆⋯F_0\subseteq F_1\subseteq\cdots with Fj⊆Yjfor every jandRj(Fj,Fj+1)for every j≤m.F_j\subseteq Y_j\ \text{for every } j\quad\text{and}\quad R_j(F_j,F_{j+1})\ \text{for every } j\le m.(9)✦

  3. For every real D≥1D\ge 1, 𝒞(D)≠∅.\mathcal{C}(D)\ne\emptyset.(10)✦

  4. There are reals aa, θ\theta, λ\lambda and a natural number KK with 0<a≤10<a\le 1, 2a≤θ2a\le\theta, λ>0\lambda>0, K>0K>0, a≤2Kκ(a)a\le 2^K\kappa(a) and 4log⁡4/(2K−1)≤κ(a)/400004\log 4/(2^K-1)\le\kappa(a)/40000 such that every sufficiently large real XX has a finite set JJ of natural numbers with |J|≥λX|J|\ge\lambda X, with i+K≤ji+K\le j whenever i<ji<j lie in JJ, and with X≤jlog⁡2≤2120Xand|Bj|≥θ2jlog⁡2j+1(j∈J).X\le j\log 2\le\tfrac{21}{20}X\quad\text{and}\quad|B_j|\ge\frac{\theta\,2^j}{\log 2^{j+1}} \qquad(j\in J).(11)✦

  5. Let X>0X>0, c>0c>0 and λ\lambda be reals, WW a natural number and J0,J1,…J_0,J_1,\dots finite sets of natural numbers such that, for every w<Ww<W, every j∈Jwj\in J_w has 100wX≤jlog⁡2≤2120100wX100^wX\le j\log 2\le\frac{21}{20}100^wX and |Jw|≥λ100wX|J_w|\ge\lambda\,100^wX. Then the union J0∪…∪JW−1J_0\cup\dots\cup J_{W-1} of the first WW sets JwJ_w satisfies Wcλ10500000≤∑j∈J0∪…∪JW−1c107log⁡2j.\frac{Wc\lambda}{10\,500\,000}\le\sum_{j\in J_0\cup\dots\cup J_{W-1}}\frac{c}{10^{7}\log 2^{j}}.(12)✦

In the paper, the result reads: averaging Lemma 8.1 and applying Proposition 7.1 gives c1∑T1/log⁡T≤log⁡KD+o(1)c_1\sum_T 1/\log T\le\log K_D+o(1) for a constant c1c_1, while the batches ℬT\mathcal{B}_T, consisting of the primes p≡1(mod⁡4)p\equiv 1\pmod 4 in [T,2T][T,2T], make the left side diverge, and this proves Theorem 1.2.

What Is Checked

The claim is stated over walks in ℤ[i]\mathbb{Z}[i] with distances in ℂ\mathbb{C}, split prime sieves and their avoiding sets, the dyadic batches and dyadic sieves, residue weights of preceding factors, the lattice ball and its KDK_D points, the binary entropy, batch certificates with their entropy bands and coverage derivations, sieve certificates and the top coefficient κ\kappa. About these constructions the library proves that every prime p≡1(mod⁡4)p\equiv 1\pmod 4 is the norm of a Gaussian prime, so that the chosen split factors exist and every dyadic sieve is a split prime sieve.