Bounded-step walks on Gaussian primes

Source and verification

This article explains family 028 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

🏷️ A graph on Gaussian primes

Identify the Gaussian integer $a+bi$ with $(a,b)\in {\mathbb{Z}}^2$. Its norm is $a^2+b^2$, and Euclidean distance is the usual planar distance. A Gaussian prime is an irreducible nonunit in this integer lattice.

The elementary classification gives a concrete picture. If both coordinates are nonzero, $a+bi$ is prime exactly when $a^2+b^2$ is a rational prime. On an axis, the nonzero coordinate must have absolute value a rational prime congruent to three modulo four. All rotations by the units $1,-1,i,-i$ are included.

For fixed finite real $D$, join distinct Gaussian primes when their distance is at most $D$. Call this graph $G_D$. The Gaussian moat question asks whether it has an infinite path with no repeated vertex.

Claimed uniform component bound

For every finite $D$, the manuscript asserts a finite $B_D$ such that every connected component of $G_D$ has at most $B_D$ vertices. The bound includes axis primes and is independent of the starting point. (OpenAI, 2026)

The bound is nonexplicit. For $D<1$, distinct integer lattice points cannot be adjacent, so $B_D=1$ works.

An infinite walk allowing repeated vertices is a different notion: traversing one edge back and forth would already suffice. The injectivity condition is essential.

🏷️ A finite periodic sieve

For a rational prime $p\equiv 1(\mathrm{mod}4)$, choose Gaussian factors $p={\pi }_p{\bar{\pi }}_p$. For a finite set $\mathcal{P}$ of such primes, define

$$\mathcal{A}(\mathcal{P})=\left\{z\in \mathbb{Z}[i]:\begin{array}{c}{\pi }_p\nmid z,{\bar{\pi }}_p\nmid z\\ \text{for every }p\in \mathcal{P}\end{array}\right\}.$$

This set is periodic under $Q{\mathbb{Z}}^2$, where $Q={\prod }_{p\in \mathcal{P}}p$.

The source’s main construction claims that, for each $D\ge 1$, one can choose a finite ${\mathcal{P}}_D$ whose avoiding set has no infinite injective $D$-step walk.

This is stronger than producing large prime-free disks. A planar path can go around a disk; the periodic sieve must obstruct every possible route.

🏷️ Why periodicity gives a uniform bound

The following deduction from the finite obstruction is elementary and is proved explicitly in the source.

The bounded-step graph on $\mathcal{A}({\mathcal{P}}_D)$ is locally finite. If a component were infinite, the tree of finite simple paths from one vertex would have arbitrarily large depth and finite branching. Repeatedly choosing a branch with arbitrarily deep descendants would produce an infinite simple path. Hence every component is finite.

Now suppose a component $C$ contains distinct $x,y$ with the same residue modulo $Q{\mathbb{Z}}^2$. Translation by $v=y-x$ maps components to components and sends $x$ to $y$. Thus $C+v=C$. Iterating a nonzero translation would give infinitely many points in $C$, a contradiction.

Consequently every avoiding component injects into the $Q^2$ residue classes and has size at most $Q^2$.

Some Gaussian primes are removed by the sieve: precisely the associates of its selected factors. Let this finite exceptional set be $E$, and put

$$K_D=\#\{v\in {\mathbb{Z}}^2:|v|\le D\}.$$

After deleting $E$, the Gaussian-prime graph is a subgraph of the avoiding graph. A component meeting $E$ can attach to at most $(K_D-1)|E|$ components outside it. Therefore

$$\begin{array}{c}{B}_D\le \max \{Q^2,C_D\},\\ C_D=|E|+(K_D-1)|E|Q^2.\end{array}$$

The resulting bound on $B_D$ is valid once the finite obstruction is supplied.

Absence of infinite paths alone would not give this conclusion for a general locally finite graph: a disjoint union of increasingly long finite paths is a counterexample. Periodicity supplies the missing uniformity.

🏷️ Entropy from geometric sampling

For a finite-valued random variable $Z$, Shannon entropy is $H(Z)=-{\sum }_z\mathbb{P}(Z=z)\log \mathbb{P}(Z=z)$. A bounded lattice increment has at most $K_D-1$ possible nonzero values, so its entropy is at most $\log (K_D-1)$.

The source fixes a deterministic candidate walk. Randomness enters only through sampled times and auxiliary choices of one Gaussian factor over each split prime.

A long walk segment has many distinct differences. Sampling a difference and one of its endpoints, together with separation by selected prime factors, forces increased joint residue entropy. Determinant divisibility estimates control when different geometric displacements can share residue data.

Joint entropy alone is insufficient. The proof needs lower bounds on the probability of most individual residues, outside a small exceptional set. A separate coverage-transfer argument uses repeated continuations from a common checkpoint. If coverage failed, a single shared displacement would place the true residue on too short a list in too many coordinates.

🏷️ A common information budget

All prime batches must use the same terminal time law. Otherwise lower bounds for information could concern incompatible samples and could not be added.

The source constructs this common law through a schedule of geometric operations and an auxiliary uniform time offset. Short words of successive increments then test possible starting residues. Avoidance of the selected zero classes makes these tests informative.

Each chosen batch incurs a conditional-information cost. Nested residue vectors and block subadditivity permit these costs to be summed, while bounded increments provide a finite entropy budget per step. A finite collection of sufficiently many batches exceeds that budget, contradicting the putative avoiding walk.

This is the difficult finite-obstruction theorem. The periodic reduction above explains its consequence without independently verifying the geometric and information estimates.

🏷️ Key steps and proof outlines

The periodicity argument above is the final conversion. The difficult input is a finite collection of congruences that excludes every infinite self-avoiding walk with step bound $D$. The source proves that input by comparing information forced by zero avoidance with the finite information capacity of an increment word. The walk itself is deterministic; all randomness comes from auxiliary sampling (OpenAI, 2026).

Geometric differences supply residue entropy

For a segment of $n$ steps, let $E$ be its vertices, $R$ its diameter, and $W$ the larger of one and the maximum distance of a vertex from the chosen diameter line. Put $A=RW$. The geometric lemma establishes

$$cn\le A\le D^2{n}^2,|E-E|\ge c_{D}A.$$

The first bound is a packing argument: disjoint small disks around the distinct lattice vertices fit inside an enlarged rectangle of area $O(A)$. The difference-set bound has a useful topological proof when $W>1$. Choose two diameter endpoints and a third vertex realizing the width. Their displacement vectors $a,b$ span a lattice of determinant $A$. Two interpolated subpaths to these vertices define a map from a parameter torus to ${\mathbb{R}}^2/(\mathbb{Z}a+\mathbb{Z}b)$ by subtracting their positions. It is homotopic to the linear map with degree $-1$, so it is onto. Every interpolated difference lies within $2D$ of a vertex difference. Hence disks centered at $E-E$ cover a torus of area $A$, giving $A\le 4\pi D^2|E-E|$. The thin case $W=1$ follows directly from the number of vertices and $R\le Dn$.

Reduction modulo randomly selected Gaussian prime factors must preserve enough of these differences. For split rational primes $p\in [T,2T]$, choose one of the two conjugate factors independently. The source’s rectangle lemma says that a product ideal of norm $P$ usually has no nonzero point in a rectangle of area scale at most $P^{1-d}$, with failure probability $O(e^{-c{d}^{3}r})$ for $r$ factors.

Its key arithmetic observation is exact: witnesses for nearby sign choices share a large factor $c_{\ast }$, so

$$\det (c_{\ast }u,c_{\ast }v)=N(c_{\ast })\det (u,v).$$

The determinant is an integer multiple of a large norm, while the rectangle bounds its absolute value by a smaller number. It must vanish. Nearby bad sign choices therefore have collinear witnesses. A bound for each possible line, combined with expansion in the discrete cube of sign choices, controls all bad choices without summing over every line.

Choose a distinct difference uniformly, choose one representing pair of endpoints, and then choose either endpoint with probability $1/2$. Injectivity of residue reduction on the difference set supplies entropy; the entropy chain rule also retains part of the starting point’s entropy. If $f_Y(s)$ denotes the average joint residue entropy of a random signed subset of $s$ primes, and $L_{\ast }$ is the average $\log p$ in the batch, the resulting enrichment has the form

$$\frac{f_V(b)}{b{L}_{\ast }}\ge \frac{1}{2}\left(1+\frac{f_Z(q)}{q{L}_{\ast }}\right)-O_D(g).$$

Here $Z$ is the starting position, $V$ the sampled endpoint, and $b\approx g^{2}q$. Repetition halves the entropy deficit up to controlled errors.

Coverage requires more than a large entropy

A distribution can have entropy close to $\log p$ and still omit particular residues. The proof needs a stronger statement: at least $99\%$ of the selected signed primes have probability at least $1/(4p)$ at every residue except fewer than $p^{199/200}$ exceptions, from each exact checkpoint start.

The “Coverage from shared continuation data” argument supplies this upgrade. At a checkpoint with position $Y$, sample repeated future displacements $h_1,\dots ,h_n$, independently conditional on the exact checkpoint time. Use the same data vector $\mathcal{H}$ for all residue coordinates. For a random coordinate subset $S$, the chain rule gives

$$H(F_S(Y))-H(\mathcal{H})\le H(F_S(Y)\mid \mathcal{H})\le \sum _{c\in S}H(Y_c\mid \mathcal{H}).$$

Thus the shared data cost is paid once before averaging over coordinates. If a terminal distribution has too many low-probability residues, test candidate starting residues against that deficient set using the repeated displacements. Markov’s inequality says the true starting residue passes often. Conditional coverage at the next checkpoint and a binomial lower-tail estimate say that only a short list of candidates passes. Frequent membership in a short list forces a conditional entropy deficit, contradicting the displayed budget. Backward induction through the source’s sampling schedule transfers strong coverage to the required checkpoints. Independence is used after fixing an exact time; the proof does not assume it survives unconditioned mixing.

Zero avoidance forces information into short words

Let $W_L(t)$ be the next $L$ increments of the walk, and take a dyadic length $L\asymp T^{2/5}$. A nonzero multiple of a Gaussian prime factor of norm $p$ has length at least $\sqrt{p}$. Since $DL<\sqrt{p}$ for large $T$, distinct positions in such a word cannot coincide modulo that factor. Therefore the $L$ opportunities to hit a specified residue are disjoint.

Coverage supplies probability $\gg 1/p$ at each offset. A sampled package consisting of the checkpoint-to-terminal displacement and the next word rejects a false candidate starting residue with probability $\gg L/p$. With

$$m\asymp (T/L)\log T$$

conditionally independent packages, the survival probability is at most $e^{-cmL/p}$. Except for the coverage exceptions, the candidate list shrinks by a fixed power of $p$. This reveals a fixed fraction of the starting residue entropy.

Let $X$ be the current batch’s residue vector and $O$ the smaller batches’ vector at the checkpoint; use primes for their counterparts at the common terminal time. If $s$ is the physical displacement, residue addition is a bijection when $s$ is known, and

$$I(X;s,W\mid O)\le I(X^{\prime };W\mid O^{\prime })+2H(s).$$

One $H(s)$ pays for revealing the displacement; the other pays for removing it from the conditioning after translation. The schedule gives $H(s)=O_D(T^{1/4})$, negligible compared with $L/\log T$. Consequently each batch forces the following bound, where ${\mathbb{E}}_{\mathcal{C}}$ averages over the auxiliary signed-prime selections $\mathcal{C}$:

$$\frac{1}{L}{\mathbb{E}}_{\mathcal{C}}I(X^{\prime };W_L(t_{\ast })\mid O^{\prime })\ge \frac{c_1}{\log T}.$$

A common sampling law makes the charges add

The same terminal time $t_{\ast }$ is used for every batch. Its law is nearly invariant under the short shifts needed below, because the schedule ends with an independent uniform time offset. This concerns the sampling law, not stationarity of the deterministic walk.

Order the batches and write $Q_j$ for all residue data through batch $j$. The information charge is the drop between the conditional entropy rates of a word given $Q_{j-1}$ and given $Q_j$. Since the word lengths are powers of two, partition a longer word into shorter blocks. Earlier increments update $Q_j$ to the next block’s starting residue; the chain rule and approximate translation invariance then bound the next initial entropy rate by the preceding remaining rate. These inequalities telescope:

$$\sum _T\frac{I(X_T^{\prime };W_{L_T}(t_{\ast })\mid O_T^{\prime })}{L_T}\le \log K_D+o(1),$$

where $K_D$ is the finite number of allowed increments. This upper bound holds for every fixed $\mathcal{C}$; average it over $\mathcal{C}$ before combining it with the lower bounds. The schedule selects finite collections with ${\sum }_{T}1/\log T$ arbitrarily large. Their lower information charges contradict this fixed capacity. All thresholds are uniform in the hypothetical walk, so one finite prime collection works for every such walk; the periodicity argument then gives the stated uniform component bound.

🏷️ Connections

Jacobsthal covering studies one-dimensional congruence obstacles. Prime-gap frequency explains why a large vacant region alone does not establish the desired global counting conclusion.

🏷️ Manuscripts and verification scope

• Bounded-Step Walks on Gaussian Primes — pinned manuscript and companion source.

The family scope page describes selected formalization coverage. The page selects a uniform finite component and injective-walk bound, including axis primes and associates, without an explicit bound. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026. Bounded-Step Walks on Gaussian Primes.