OctoInformBeta

OpenAI preprint, September 2026 · §4. Entropy enrichment from a forward segment

Lemma 4.2: An explicit bound exp⁡(−d3r/5120)\exp(-d^3r/5120) on the probability, over fair independent signs, for rr split primes in [T,2T][T,2T] and half-lengths with RW≤Q1−dRW\le Q^{1-d}

Random signed products rarely divide nonzero points of thin rectangles.

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

A rational prime p≡1(mod⁡4)p\equiv 1\pmod 4 splits in ℤ[i]\mathbb{Z}[i] as p=πpπ‾pp=\pi_p\bar\pi_p, with πp\pi_p a Gaussian prime of norm pp. Take a real number T≥5T\ge 5 and rr distinct such primes, all between TT and 2T2T, choose one of the two factors of each by a fair coin, independently, and multiply the chosen factors. The result is a random Gaussian integer whose norm is the product of the primes. The question is how likely it is to divide a nonzero Gaussian integer in a rectangle centered at the origin, in any orientation, with half-lengths R≥W≥1R\ge W\ge 1 and RWRW at most the (1−d)(1-d)th power of that norm, where dd is a real number with 0<d<1/40<d<1/4.

Sieves, Signs and Rectangles

A split prime sieve 𝒫\mathcal{P} is a finite set 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 period QQ of a split prime sieve 𝒫\mathcal{P} is the product of its primes, Q=∏p∈𝒫pQ=\prod_{p\in\mathcal{P}}p, and rr denotes the number of primes in 𝒫\mathcal{P}.✦

The signed factor of a Gaussian integer π\pi for a sign ϵ∈{+,−}\epsilon\in\{+,-\} is the Gaussian integer π(ϵ)\pi^{(\epsilon)} equal to π\pi when ϵ=+\epsilon=+ and to its conjugate π‾\bar\pi when ϵ=−\epsilon=-.✦ A sign vector σ\sigma on 𝒫\mathcal{P} is a choice of a sign σp\sigma_p for each p∈𝒫p\in\mathcal{P}, and the signed product of σ\sigma is the Gaussian integer Πσ=∏p∈𝒫πp(σp).\Pi_\sigma=\prod_{p\in\mathcal{P}}\pi_p^{(\sigma_p)}.(1)✦

The random sign measure on sign vectors is the law under which the signs σp\sigma_p, p∈𝒫p\in\mathcal{P}, are independent and each follows the fair coin law, which gives ++ and −- probability 12\frac12 each; Pr\Pr denotes probability under it.✦

A sign vector σ\sigma is bad for a set SS of Gaussian integers when Πσ\Pi_\sigma divides some nonzero element of SS.✦

For a complex number ee and real numbers RR and WW, the oriented rectangle ℛ(e;R,W)\mathcal{R}(e;R,W) is the set of Gaussian integers ℛ(e;R,W)={z∈ℤ[i]:|Re⁡(e‾z)|≤R,|Im⁡(e‾z)|≤W};\mathcal{R}(e;R,W)=\bigl\{z\in\mathbb{Z}[i] : |\operatorname{Re}(\bar e z)|\le R,\ |\operatorname{Im}(\bar e z)|\le W\bigr\};(2)✦ when |e|=1|e|=1, RR is the half-length along ee and WW the half-width across it.

The Claim

Theorem 1. Let 𝒫\mathcal{P} be a split prime sieve of rr primes with period QQ, all of them in [T,2T][T,2T] for a real number T≥5T\ge 5. Let ee be a complex number with |e|=1|e|=1, and let RR, WW and dd be real numbers with 1≤W≤R1\le W\le R, 0<d<1/40<d<1/4, RW≤Q1−dRW\le Q^{1-d} and d3r≥1000d^3r\ge 1000. Then Pr⁡(σ is bad for ℛ(e;R,W))≤exp⁡(−d3r5120).\Pr\bigl(\sigma\text{ is bad for }\mathcal{R}(e;R,W)\bigr)\le\exp\Bigl(-\frac{d^3r}{5120}\Bigr).(3)✦

In the paper, the result reads: there are absolute constants c,C,C0>0c,C,C_0>0 such that, for distinct rational primes p1,…,pr≡1(mod⁡4)p_1,\dots,p_r\equiv 1\pmod 4 in [T,2T][T,2T] with T≥5T\ge 5 and product QQ, and an origin-centered rectangle ℛ\mathcal{R} in any orientation with half-lengths R≥W≥1R\ge W\ge 1 and RW≤Q1−dRW\le Q^{1-d}, where 0<d<1/40<d<1/4, independent sign choices give Pr⁡(ℛ∩Πσℤ[i]≠{0})≤Cexp⁡(−cd3r)\Pr\bigl(\mathcal{R}\cap\Pi_\sigma\mathbb{Z}[i]\ne\{0\}\bigr)\le C\exp(-c\,d^3r) whenever d3r≥C0d^3r\ge C_0; the paper writes PP, QQ, R1R_1, W1W_1 and ∏πi\prod\pi_i for the page’s QQ, ℛ\mathcal{R}, RR, WW and Πσ\Pi_\sigma. In (3) the constants are C=1C=1, c=1/5120c=1/5120 and C0=1000C_0=1000.

What Is Checked

The claim is stated over a split prime sieve and its period, the signed product of a sign vector with its signed factors, the random sign measure built from the fair coin law, the bad sign vectors of a set, and the oriented rectangle. Besides the claim, the library has four results on these constructions and on the Boolean cube.

The determinant of two Gaussian integers zz and ww is the integer det⁡(z,w)=Re⁡zIm⁡w−Im⁡zRe⁡w\det(z,w)=\operatorname{Re}z\,\operatorname{Im}w-\operatorname{Im}z\,\operatorname{Re}w, which vanishes exactly when 00, zz and ww lie on one line.✦ The Hamming distance dH(σ,τ)d_H(\sigma,\tau) of two sign vectors σ\sigma and τ\tau is the number of p∈𝒫p\in\mathcal{P} with σp≠τp\sigma_p\ne\tau_p.✦ Let ww and w′w' be Gaussian integers with Πσ∣w\Pi_\sigma\mid w and Πτ∣w′\Pi_\tau\mid w', let U>0U>0 satisfy p≤Up\le U for every p∈𝒫p\in\mathcal{P}, and let BB be a real number with |det⁡(w,w′)|≤B|\det(w,w')|\le B and BUdH(σ,τ)<QBU^{d_H(\sigma,\tau)}<Q. Then det⁡(w,w′)=0.\det(w,w')=0.(4)✦

For a set SS of Gaussian integers and a Gaussian integer vv, the line event ES,vE_{S,v} is the event that Πσ\Pi_\sigma divides some nonzero w∈Sw\in S with det⁡(v,w)=0\det(v,w)=0.✦ A Gaussian integer vv is primitive when its real and imaginary parts are coprime integers.✦ Let vv be primitive, let every w∈Sw\in S have norm N(w)≤MN(w)\le M, and let ε\varepsilon be a real number with 0≤ε≤log⁡Q−12log⁡M0\le\varepsilon\le\log Q-\frac12\log M. Then Pr⁡(ES,v)≤exp⁡(−ε22∑p∈𝒫(12log⁡p)2).\Pr(E_{S,v})\le\exp\Biggl(-\frac{\varepsilon^2}{2\sum_{p\in\mathcal{P}}\bigl(\frac12\log p\bigr)^2}\Biggr).(5)✦

The Boolean cube {0,1}n\{0,1\}^n is the set of nn-tuples of bits.✦ The edges of the Boolean cube {0,1}n\{0,1\}^n are the pairs of tuples in {0,1}n\{0,1\}^n at Hamming distance 11, the Hamming distance of two tuples being the number of coordinates in which they differ. The edge boundary ∂X\partial X of a subset XX of the cube is the set of edges with exactly one end in XX✦, and |X||X| is the number of points of XX✦. For every nn and every subset XX of {0,1}n\{0,1\}^n, the edge isoperimetric inequality of the cube holds: |X|(nlog⁡2−log⁡|X|)≤|∂X|log⁡2.|X|\,\bigl(n\log 2-\log|X|\bigr)\le|\partial X|\log 2.(6)✦

Suppose that 𝒫\mathcal{P} has r≥1r\ge 1 primes, and let SS be any set of Gaussian integers. Let U≥1U\ge 1 satisfy p≤Up\le U for every p∈𝒫p\in\mathcal{P}, let B≥0B\ge 0 satisfy |det⁡(w,w′)|≤B|\det(w,w')|\le B for all w,w′∈Sw,w'\in S, and let hh be a natural number with BU2h<QBU^{2h}<Q. Let every w∈Sw\in S have norm N(w)≤MN(w)\le M, let 0≤ε≤log⁡Q−12log⁡M0\le\varepsilon\le\log Q-\frac12\log M, and write η\eta for the right side of (5). If real numbers a≥0a\ge 0, E>0E>0 and A>0A>0 satisfy log⁡E≤rlog⁡2−a,2rAη≤E,A≤(1+arlog⁡2)h,\log E\le r\log 2-a,\qquad 2^rA\,\eta\le E,\qquad A\le\Bigl(1+\frac{a}{r\log 2}\Bigr)^h,(7) then Pr⁡(σ is bad for S)≤1A.\Pr(\sigma\text{ is bad for }S)\le\frac{1}{A}.(8)✦