Gaussian moat: is there an infinite bounded-step walk on Gaussian primes? (Erdős #952)
Statement
Work in the Gaussian integers $\mathbb{Z}[i]$. Is there an infinite sequence of distinct Gaussian primes $x_1,x_2,\ldots$ such that $$\lvert x_{n+1}-x_n\rvert \ll 1,$$ i.e. with all consecutive gaps $\lvert x_{n+1}-x_n\rvert$ bounded by an absolute constant? Equivalently — the Gaussian moat problem — can one 'walk to infinity' in the complex plane, stepping only on Gaussian primes, using steps of uniformly bounded length?
Acceptance. FULLY RESOLVES: a proof that NO infinite bounded-step sequence of distinct Gaussian primes exists — equivalently that for every $k$ a k-moat surrounds the origin — as a complete written or machine-checked proof; OR a construction/proof that an infinite Gaussian-prime walk with bounded steps DOES exist. ADVANCES: certify, by reproducible computation, a moat blocking all steps of length $\leq k$ for some $k$ strictly larger than the best value stated in the background ($\sqrt{26}$) — deliver the search program, the exact region searched, and a machine-checkable certificate that the connected component of Gaussian primes containing the origin (with edges of length $\leq k$) is finite and enclosed by composites; OR a rigorous conditional result (e.g. under a made-rigorous Hardy–Littlewood-type prime-constellation heuristic, clearly flagged) bounding the length of any bounded-step prime walk. Deliver the code plus the certified record moat parameter $k$, or the proof.
Background
Universally known as the Gaussian moat problem, and NOT actually due to Erdős. Per [Er77c], the conjecture was told to Erdős by Motzkin at the 1963 Pasadena number-theory meeting and was apparently raised by Basil Gordon and Motzkin; it was later mis-attributed to Erdős, a mis-attribution the erdosproblems.com/952 entry (fetched 2026-07-21, status 'open') explicitly corrects. Erdős [Er80] wrote the answer is 'almost certainly negative' — one cannot walk to infinity with bounded steps. The rational primes settle their 1-D analogue trivially (arbitrarily long prime gaps block any bounded-step walk along $\mathbb{Z}$), but the 2-D distribution of Gaussian primes leaves the question open. Progress is computational and organised around moats: a 'k-moat' is a ring of Gaussian composites wide enough that no step of length $\leq k$ crosses it, and a k-moat enclosing the origin blocks every bounded-step walk with step size $\leq k$. Gethner, Wagon and Wick (1998, 'A stroll through the Gaussian primes') computed moats blocking small step sizes and Tsuchimura (2005) extended the searches; the widest verified moat blocks all steps of length $\leq\sqrt{26}$. Whether a moat exists for every $k$ (equivalently, whether the walk is impossible) is unknown. A Lean formalisation exists in the DeepMind formal-conjectures project. Attacker's tool: a large-scale breadth-first / connected-component search over Gaussian primes in an expanding region, joining primes within distance $k$, to certify a moat for a new record $k$ (or, if Erdős is wrong, to exhibit an unbounded prime walk).
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #952 (T. F. Bloom) | website |
| REF-02 | Gaussian moat problem (Wikipedia) | website |
| REF-03 | Lean formalisation of Erdős #952 (DeepMind formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.