OctoInformBeta

OpenAI preprint, September 2026 ยท ยง1. The Gaussian moat problem

Theorem 1.2: Each such DD has a sieve certificate qq, and no such walk stays in the sieved set A(๐’ซq)A(\mathcal{P}_q) of the primes of qq

Finite sieves block self-avoiding walks with steps at most Dโ‰ฅ1D \ge 1..

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

The Gaussian moat problem asks whether one can walk to infinity on the Gaussian primes, the irreducible elements of โ„ค[i]\mathbb{Z}[i] (primes on the coordinate axes included), with steps of bounded length. 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, for a real number DD, when |zt+1โˆ’zt|โ‰คD|z_{t+1} - z_t| \le D for every tt, distances being taken in โ„‚\mathbb{C}. For a set SโІโ„ค[i]S \subseteq \mathbb{Z}[i] and a real DD, ๐’ฒD(S)\mathcal{W}_D(S) denotes the set of self-avoiding walks with steps at most DD whose terms all lie in SS.

The sieve form of the problem replaces the Gaussian primes by the Gaussian integers that survive a finite sieve. A split 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}; ฯ€โ€พp\bar\pi_p denotes the conjugate of ฯ€p\pi_p.โœฆ The sieved set A(๐’ซ)A(\mathcal{P}) of a split sieve ๐’ซ\mathcal{P} is the set of Gaussian integers divisible by neither ฯ€p\pi_p nor ฯ€โ€พp\bar\pi_p for any pโˆˆ๐’ซp \in \mathcal{P}: A(๐’ซ)={zโˆˆโ„ค[i]:ฯ€pโˆคz and ฯ€โ€พpโˆคz for every pโˆˆ๐’ซ}.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)โœฆ It contains every Gaussian prime other than the associates of the ฯ€p\pi_p and ฯ€โ€พp\bar\pi_p. The question is whether, for each real Dโ‰ฅ1D \ge 1, some split sieve ๐’ซ\mathcal{P} leaves no self-avoiding walk with steps at most DD in A(๐’ซ)A(\mathcal{P}).โœฆ

Dyadic Batches and Weights

The chosen split factor of a prime pโ‰ก1(mod⁡4)p \equiv 1 \pmod 4 is a Gaussian prime ฯ€p\pi_p of norm pp, fixed once for each such ppโœฆ, and the split sieve of a finite set SS of primes pโ‰ก1(mod⁡4)p \equiv 1 \pmod 4 is SS with the chosen split factors of its elements.โœฆ The dyadic batch of index jโˆˆโ„•j \in \mathbb{N} is the set Bj={p prime:pโ‰ก1(mod⁡4),2jโ‰คp<2j+1},B_j = \{ p \text{ prime} : p \equiv 1 \pmod 4,\ 2^j \le p < 2^{j+1} \},(2)โœฆ and the dyadic sieve of index jj is the split sieve of BjB_j.โœฆ

Let ๐’ซ\mathcal{P} be a split sieve, enumerated once and for all as p1,โ€ฆ,p|๐’ซ|p_1, \dots, p_{|\mathcal{P}|}. The signed factor of a Gaussian integer ฯ€\pi with sign +1+1 is ฯ€\pi, and with sign โˆ’1-1 it is ฯ€โ€พ\bar\piโœฆ; the available factors of ๐’ซ\mathcal{P} form the set F(๐’ซ)={ฯ€p,ฯ€โ€พp:pโˆˆ๐’ซ}F(\mathcal{P}) = \{ \pi_p, \bar\pi_p : p \in \mathcal{P} \} of signed factors of the ฯ€p\pi_p.โœฆ A signed index of ๐’ซ\mathcal{P} is a pair i=(ฯƒ,m)i = (\sigma, m) of a sign vector ฯƒโˆˆ{ยฑ1}|๐’ซ|\sigma \in \{\pm 1\}^{|\mathcal{P}|} and an index 1โ‰คmโ‰ค|๐’ซ|1 \le m \le |\mathcal{P}|โœฆ, and its prime is pi=pmp_i = p_m.โœฆ The mean logarithm of ๐’ซ\mathcal{P} is L*(๐’ซ)=|๐’ซ|โˆ’1โˆ‘mlog⁡pmL^*(\mathcal{P}) = |\mathcal{P}|^{-1} \sum_{m} \log p_m.โœฆ

The residue weight of a finite set FโŠ‚โ„ค[i]F \subset \mathbb{Z}[i] is R(F)=โˆ‘fโˆˆFlog⁡N(f)R(F) = \sum_{f \in F} \log \mathrm{N}(f), with N\mathrm{N} the norm.โœฆ For split sieves ๐’ซ0,๐’ซ1,โ€ฆ\mathcal{P}_0, \mathcal{P}_1, \dots, the preceding factors at index kk form the set F<k=F(๐’ซ0)โˆชโ€ฆโˆชF(๐’ซkโˆ’1)F_{<k} = F(\mathcal{P}_0) \cup \dots \cup F(\mathcal{P}_{k-1}).โœฆ

For a real number DD, 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 the number of elements of this set.โœฆ

Sieve Certificates

Fix a real DD and a split sieve ๐’ซ\mathcal{P}, and write L*=L*(๐’ซ)L^* = L^*(\mathcal{P}). A schedule is a finite sequence ฮฝ\nu of natural numbers; โˆฅฮฝโˆฅ1\|\nu\|_1 is the sum of its entries, and ฮฝฮฝโ€ฒ\nu\nu' is the concatenation of ฮฝ\nu and ฮฝโ€ฒ\nu'. For reals gg and UU, the band scales SjS_j, band lengths โ„“j\ell_j and band sizes bjb_j, jโˆˆโ„•j \in \mathbb{N}, are Sj=g2jU,โ„“j=โŒŠexp⁡(gSj)โŒ‹,bj=โŒŠSj/L*โŒ‹.S_j = g^{2j} U, \qquad \ell_j = \lfloor \exp(g S_j) \rfloor, \qquad b_j = \lfloor S_j / L^* \rfloor.(3)

An entropy band for ๐’ซ\mathcal{P} on a schedule ฮฝ\nu, with smoothing length Mโˆˆโ„•M \in \mathbb{N}, size bโˆˆโ„•b \in \mathbb{N} and deficit ฮด\delta, consists of reals gg, UU, ฮบ\kappa, a natural number ll and a splitting ฮฝ=ฮฝโˆ’(โ„“0,โ€ฆ,โ„“lโˆ’1)ฮฝ+\nu = \nu^- (\ell_0, \dots, \ell_{l-1}) \nu^+ of the schedule, such that b=blb = b_l, 0<gโ‰ค1/2000 < g \le 1/200, U>0U > 0, โŒŠU/L*โŒ‹โ‰ค|๐’ซ|\lfloor U / L^* \rfloor \le |\mathcal{P}| and 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,log⁡36+2log⁡(D(โˆฅฮฝ+โˆฅ1+M+1))โ‰คฮบbL*,2โˆ’l+80g+ฮบโ‰คฮด.\begin{gathered} 2(1 + \log 18) \le g S_l, \qquad 640 L^* \le g^5 S_l, \qquad \log 16 + \log \max(D, K_{4D}) \le g^2 S_l, \\ 4 \log D + 2 \log 36 \le 4 g S_l, \qquad 2 \log 16 + 4 \log D \le S_l / 4, \\ \log 36 + 2 \log\bigl(D(\|\nu^+\|_1 + M + 1)\bigr) \le \kappa\, b L^*, \qquad 2^{-l} + 80 g + \kappa \le \delta. \end{gathered}(4)โœฆ

Coverage derivations for ๐’ซ\mathcal{P} with smoothing length MM are defined by two rules, each giving a schedule a coverage derivation with a floor ฯ„\tau, thresholds uiu_i indexed by the signed indices ii, and a parameter ฮท\eta. By the base rule, a schedule ฮฝ\nu has a coverage derivation with floor ฯ„\tau, thresholds uiu_i and parameter ฮท\eta when ฮฝ\nu carries an entropy band with smoothing length MM, size bb and deficit ฮธ\theta, and some real c>0c > 0 satisfies 0<bโ‰ค|๐’ซ|,ฯ„โ‰ค3/8,uiโ‰ฅ8cpi for every i,ฮธL*/cโ‰คฮท.0 < b \le |\mathcal{P}|, \qquad \tau \le 3/8, \qquad u_i \ge 8 c\, p_i \text{ for every } i, \qquad \theta L^* / c \le \eta.(5)โœฆ By the step rule, a schedule ฮฝฮฝโ€ณ\nu\nu'' has a coverage derivation with floor ฯ„\tau, thresholds uiu_i and parameter ฮท\eta when ฮฝ\nu carries an entropy band with smoothing length 00, size bb and deficit ฮธ\theta, for some real ฮด\delta, the schedule ฮฝโ€ณ\nu'' has one with floor ฯ„+4ฮด\tau + 4\delta, thresholds uiโ€ฒu'_i and parameter ฮทโ€ฒ\eta', and there are nโˆˆโ„•n \in \mathbb{N} and reals ฮป\lambda, vv, cic_i with nโ‰ฅ1n \ge 1, 0<bโ‰ค|๐’ซ|0 < b \le |\mathcal{P}|, 0โ‰คฯ„โ‰ค3/80 \le \tau \le 3/8, 0<ฮดโ‰ค1/640 < \delta \le 1/64, ฮปโ‰ฅ0\lambda \ge 0, ฮท>0\eta > 0, โˆฅฮฝโ€ณโˆฅ1+Mโ‰ฅ1\|\nu''\|_1 + M \ge 1, ui>0u_i > 0 for every ii, and ฮทโ€ฒ+ฮปโ‰คฮทฮด/2,2(1โˆ’log⁡(ฮทฮด/2))โ‰คv,ฮธL*+n(log⁡36+2log⁡(D(โˆฅฮฝโ€ณโˆฅ1+M)))/b<ฮทฮดv/4,1โ‰คci,vโ‰คlog⁡piโˆ’log⁡ci,uiโ€ฒ/ฮดโ‰คci,piexp⁡(โˆ’nฮด2ui/(2pi))โ‰คฮป(every i).\begin{gathered} \eta' + \lambda \le \eta\delta/2, \qquad 2\bigl(1 - \log(\eta\delta/2)\bigr) \le v, \\ \theta L^* + n\bigl(\log 36 + 2\log(D(\|\nu''\|_1 + M))\bigr)/b < \eta\delta v/4, \\ 1 \le c_i, \qquad v \le \log p_i - \log c_i, \qquad u'_i/\delta \le c_i, \qquad p_i \exp\bigl(-n\delta^2 u_i/(2p_i)\bigr) \le \lambda \qquad (\text{every } i). \end{gathered}(6)

A batch certificate for ๐’ซ\mathcal{P} with schedule ฮฝ\nu, smoothing length MM, length Lโˆˆโ„•L \in \mathbb{N}, weight EE and rate rr consists of a splitting ฮฝ=ฮฝโ€ฒฮฝโ€ณ\nu = \nu'\nu'' of the schedule, a scale TT, natural numbers bb and nn, reals ฯ„\tau, AA, ฮท\eta, ฮด\delta, thresholds uiโ‰ฅ0u_i \ge 0 for the signed indices, an entropy band on ฮฝโ€ฒ\nu' with smoothing length 00, size bb and deficit ฮด\delta, and a coverage derivation of ฮฝโ€ณ\nu'' with smoothing length MM, floor ฯ„\tau, thresholds uiu_i and parameter ฮท\eta.โœฆ Its conditions are that ๐’ซ\mathcal{P} is nonempty with Tโ‰คpโ‰ค2TT \le p \le 2T for every pโˆˆ๐’ซp \in \mathcal{P}, that Tโ‰ฅ5T \ge 5, L*โ‰ฅ1L^* \ge 1, bโ‰ค|๐’ซ|b \le |\mathcal{P}|, nโ‰ฅ1n \ge 1, 1โ‰คLโ‰คM1 \le L \le M, ฯ„โ‰ฅ0\tau \ge 0 and Aโ‰ฅ0A \ge 0, that for every signed index ii (DL)2<pi,LM+1โ‰คฯ„2pi,log⁡(4ui+piexp⁡(โˆ’nLฯ„8pi))โ‰คlog⁡piโˆ’A,(DL)^2 < p_i, \qquad \frac{L}{M + 1} \le \frac{\tau}{2 p_i}, \qquad \log\Bigl(4 u_i + p_i \exp\Bigl(-\frac{n L \tau}{8 p_i}\Bigr)\Bigr) \le \log p_i - A,(7) and that n(Lr+2(log⁡36+2log⁡(D(โˆฅฮฝโ€ณโˆฅ1+M))))โ‰คb(A(1โˆ’2ฮท)โˆ’ฮดL*)โˆ’E.n\Bigl(L r + 2\bigl(\log 36 + 2 \log(D(\|\nu''\|_1 + M))\bigr)\Bigr) \le b\bigl(A(1 - 2\eta) - \delta L^*\bigr) - E.(8)โœฆ

A sieve certificate qq for DD consists of a schedule ฮฝ\nu, a smoothing length MM, an index mโˆˆโ„•m \in \mathbb{N}, batch indices j0,โ€ฆ,jmj_0, \dots, j_m, lengths L0,โ€ฆ,Lmโˆˆโ„•L_0, \dots, L_m \in \mathbb{N}, rates r0,โ€ฆ,rmr_0, \dots, r_m, an error ฮตโ‰ฅ0\varepsilon \ge 0 and, for each kโ‰คmk \le m, a batch certificate for the dyadic sieve of index jkj_k with schedule ฮฝ\nu, smoothing length MM, length LkL_k, rate rkr_k and weight Ek=R(F<k)E_k = R(F_{<k}), where F<kF_{<k} is the set of preceding factors of the dyadic sieves of indices j0,j1,โ€ฆj_0, j_1, \dots, and Em+1=R(F<m+1)E_{m+1} = R(F_{<m+1}) likewise.โœฆ Write hh for the binary entropy. Its conditions are that LkL_k divides Lk+1L_{k+1} for k<mk < m, that 2h(aM+1)+aM+1(Lklog⁡KD+2Em+1)โ‰คฮต(k<m,0โ‰คa<Lk+1),2 h\Bigl(\frac{a}{M + 1}\Bigr) + \frac{a}{M + 1}\bigl(L_k \log K_D + 2 E_{m+1}\bigr) \le \varepsilon \qquad (k < m,\ 0 \le a < L_{k+1}),(9) and that log⁡KD+mฮต<r0+r1+โ€ฆ+rm.\log K_D + m \varepsilon < r_0 + r_1 + \dots + r_m.(10)โœฆ The prime set of a sieve certificate qq is ๐’ซq=Bj0โˆชโ€ฆโˆชBjm\mathcal{P}_q = B_{j_0} \cup \dots \cup B_{j_m}โœฆ, its sieve is the split sieve of ๐’ซq\mathcal{P}_qโœฆ, with sieved set A(๐’ซq)A(\mathcal{P}_q), and ๐’ฌ(D)\mathcal{Q}(D) is the set of sieve certificates for DD.

The Claim

Theorem 1.

  1. (Sieve form of the problem.) For every real Dโ‰ฅ1D \ge 1 there is a split sieve ๐’ซD\mathcal{P}_D with ๐’ฒD(A(๐’ซD))=โˆ….\mathcal{W}_D\bigl(A(\mathcal{P}_D)\bigr) = \emptyset.(11)โœฆ

  2. Suppose every real Dโ‰ฅ1D \ge 1 has a sieve certificate. Then for every real Dโ‰ฅ1D \ge 1 some split sieve ๐’ซ\mathcal{P} satisfies ๐’ฒD(A(๐’ซ))=โˆ….\mathcal{W}_D\bigl(A(\mathcal{P})\bigr) = \emptyset.(12)โœฆ

  3. For every real Dโ‰ฅ1D \ge 1, ๐’ฌ(D)โ‰ โˆ….\mathcal{Q}(D) \neq \emptyset.(13)โœฆ

  4. Let Dโ‰ฅ1D \ge 1 be real and qq a sieve certificate for DD. Then ๐’ฒD(A(๐’ซq))=โˆ….\mathcal{W}_D\bigl(A(\mathcal{P}_q)\bigr) = \emptyset.(14)โœฆ

What Is Checked

The four statements are stated over self-avoiding walks in โ„ค[i]\mathbb{Z}[i] with steps measured in โ„‚\mathbb{C}, split sieves ๐’ซ\mathcal{P} whose factors ฯ€p\pi_p are Gaussian primes of norm pp, their sieved sets A(๐’ซ)A(\mathcal{P}), and sieve certificates, whose prime sets ๐’ซq\mathcal{P}_q are finite unions of dyadic batches BjB_j sieved by the chosen split factors.

Of these constructions, the library proves that every element of the prime set ๐’ซq\mathcal{P}_q of a sieve certificate is a prime congruent to 11 modulo 44.โœฆ