ERDŐS/DAILY ▸

← back to the ledger

ERDőS #952 · PARTIAL

Erdős problem #952 — Gaussian moat

Accessed 2026-07-28. This report uses the following claim labels throughout:

0. Mandatory live-page check

(b: live-page record) I fetched https://www.erdosproblems.com/952 and its discussion thread through the Bright Data browser path, not datacenter curl. The page was last edited 2026-04-08 and showed:

Thus none of the requested skip conditions was present.

Verbatim current statement

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? > \]

(b: live-page record) The page calls this the Gaussian moat problem. It says the problem was apparently raised by Basil Gordon and Motzkin and was later misattributed to Erdős. It cites:

The page records Erdős's belief that the answer is negative.

All five current comments

(b: live-page record; comments themselves are explicitly unverified by the site)

  1. BorisAlexeev (2025-12-05) points to Nobuyuki Tsuchimura's 2005 computation and the statement that the origin is separated from infinity by a moat of width \(6\). The same comment says the data agree with a random model predicting a negative answer.
  2. Alfaiz (edited after correction, 2025-12-05) writes the bounded-walk formulation and says Jordan–Rabung only show that, if such a walk exists, its bound must be at least \(4\).
  3. Vjeko_Kovac (2025-12-05) corrects the suggestion that Jordan–Rabung solved the problem: they only report a conditional lower bound and computational evidence.
  4. Alfaiz explains that the mistaken “solved” reading came from a statement in a paper of Tuza.
  5. Vjeko_Kovac explains that an earlier displayed condition \(\lvert\gamma_j\rvert<M\) contradicted \(\lvert\gamma_j\rvert\to\infty\); the intended condition was \(\lvert\gamma_1\rvert<M\), which is just the original problem.

1. Primary-source literature audit

(b) J. H. Jordan and J. R. Rabung, A Conjecture of Paul Erdős Concerning Gaussian Primes, Math. Comp. 24 (1970), 221–223, exists and does not solve the problem. Its abstract says a step of length \(4\) is required, and the body states the conditional conclusion \(M>4\). This verifies the correction in the live-page comments.

(b) E. Gethner and H. M. Stark, Periodic Gaussian Moats, Experimental Mathematics 6 (1997), 289–292, proves plane-filling periodic submoats for step bounds \(\sqrt2\) and \(2\). In particular, every start-anywhere walk with steps at most \(2\) is finite. The paper also reports that Jordan–Rabung's 1976 local-distribution result gives at most \(48\) steps when the step bound is \(\sqrt2\). Its period for the \(2\)-step construction is \(7{,}113{,}990\).

(b) E. Gethner, S. Wagon, and B. Wick, A Stroll Through the Gaussian Primes, Amer. Math. Monthly 105 (1998), 327–337, gives the finite rooted component for step bound \(\sqrt{26}\) and explicitly says arbitrary-width separating moats were not proved.

(b) N. Tsuchimura, Computational Results for Gaussian Moat Problem, METR 2004-13; journal version IEICE Trans. Fundamentals E88-A (2005), 1267–1273, extends the rooted computation to \(k=\sqrt{36}=6\). It proves that the component is finite and gives the upper bound

\[ |\xi(6)|<80{,}015{,}782. \]

This is a bound, not an exact farthest point. The reported computation used 38 Pentium III CPUs; the paper reports 26 hours for the \(k=6\) run.

(b) E. Magness, B. Nugent, and L. Robertson, Walking to Infinity Along Gaussian Lines, Integers 21 (2021), A16, describes the unrestricted Gaussian moat problem as still open and distinguishes it from the solved problem of walking along one fixed Gaussian line.

(b) Two apparent arXiv solution claims are withdrawn:

(b: search result) Searches by exact problem name, title, and arXiv/DOI through 2026-07-28 found no nonwithdrawn primary source claiming a resolution. This is a search report, not a proof that no obscure source exists.

2. Exact graph reduction

(a) For an integer \(D\geq 0\), let \(G_D\) be the graph whose vertices are all Gaussian primes and in which \(z,w\) are adjacent when

\[ |z-w|^2\leq D. \]

Because squared distances of lattice points are integers, allowing any real bounded step is equivalent to using \(G_D\) for some integer \(D\).

(a) The problem has a positive answer if and only if some \(G_D\) has an infinite connected component:

(a) Fix \(\rho=1+i\). The problem has a negative answer if and only if the component of \(\rho\) is finite in every \(G_D\). Indeed, if \(C\) is an infinite component of \(G_D\) and \(z\in C\), then \(\rho\) belongs to an infinite component of

\[ G_{\max(D,\,|\rho-z|^2)}. \]

This explains both the relevance and the limitation of rooted moat computations: closing the rooted component for finitely many \(D\)'s cannot settle the quantifier “for every \(D\)”.

(a) The checker uses the elementary Gaussian-prime criterion:

3. Exact global computation for step bound \(\sqrt2\)

Result

(d) The exact maximum cardinality of a connected component of \(G_2\) is

\[ \boxed{100}. \]

There is exactly one component of size \(100\); it contains \(1+i\), has 120 edges, degree histogram

\[ \{1:16,\ 2:40,\ 3:32,\ 4:12\}, \]

and maximum squared norm \(137\). In particular, no infinite sequence can have every step at most \(\sqrt2\).

This is weaker than the named Jordan–Rabung bound of 48 steps in a simple walk, because a 100-vertex component can branch and need not have a simple path through all its vertices. It is nevertheless a completely independent, start-anywhere component certificate.

Finite certificate

(a) Let \(\mathcal P\) contain the following nine Gaussian-prime classes, one representative per associate class:

\[ 1+i,\quad 3,\quad 2\pm i,\quad 3\pm2i,\quad 4\pm i,\quad 5+2i. \]

Every Gaussian prime is either an associate of an element of \(\mathcal P\), or is coprime to their product.

(d) First sieve by

\[ Q_0=(1+i)\,3\,(2+i)(2-i)(3+2i)(3-2i), \]

which is associated to \(195(1+i)\) and has norm \(76{,}050\). With

\[ u=a+b,\qquad v=b-a, \]

residues modulo \(Q_0\) are represented by \(u,v\bmod390\) with equal parity. Exact enumeration gives:

| finite-quotient statistic | exact value | |---|---:| | residue classes | 76,050 | | classes coprime to \(Q_0\) | 18,432 | | quotient-graph components | 3,618 | | largest quotient component | 71 | | cycles with nonzero translational winding | 0 |

(a) The zero-winding condition is the key finiteness certificate. During BFS, assign to every quotient vertex the actual displacement \((x,y)\) from its root. If a quotient cycle returned with a different displacement, its lift would repeat under a nonzero period and could be infinite. No such conflict occurs, so every lifted \(Q_0\)-coprime component is a finite copy of one of the 3,618 quotient components.

(d) The remaining factors are added by Chinese-remainder layers rather than by allocating their full product:

| factor | image of \(i\) in the residue field | |---|---:| | \(4+i\), norm 17 | 13 mod 17 | | \(4-i\), norm 17 | 4 mod 17 | | \(5+2i\), norm 29 | 12 mod 29 |

If a base vertex has displacement \((x,y)\) and root residue \(r\), it survives a layer \((p,c)\) exactly when

\[ r+x+cy\not\equiv0\pmod p. \]

The checker enumerates every relevant nonzero root residue. The nominal combined modulus has \(637{,}375{,}050\) classes and \(132{,}120{,}576\) coprime classes, but zero winding lets the checker inspect only 100,352 relevant residue/component cases. The largest surviving generic component has exactly 49 vertices.

(d) There are 36 exceptional Gaussian primes (all associates of the nine displayed representatives). A separate exact Gaussian-primality BFS from all 36 closes after exactly 100 vertices. All 36 lie in that one component. Therefore:

4. Independently reproduced rooted table through \(D=10\)

(d) The second part of the checker starts with the \(D_4\)-orbit of \(1+i\), canonicalises each point to \(a\ge b\ge0\), enumerates every displacement of squared norm at most \(D\), and runs BFS to exhaustion. The following values reproduce the early rows of Tsuchimura's table.

| \(D\) | step bound | orbit representatives | union of represented orbits | farthest representative | farthest norm squared | |---:|---:|---:|---:|---:|---:| | 1 | \(1\) | 2 | 12 | \(2+i\) | 5 | | 2–3 | \(\sqrt2\)–\(\sqrt3\) | 14 | 100 | \(11+4i\) | 137 | | 4–7 | \(2\)–\(\sqrt7\) | 92 | 720 | \(42+17i\) | 2,053 | | 8–9 | \(\sqrt8\)–\(3\) | 380 | 2,996 | \(84+41i\) | 8,737 | | 10 | \(\sqrt{10}\) | 31,221 | 249,508 | \(976+311i\) | 1,049,297 |

For \(D=1\), the orbit union consists of four symmetric 3-vertex components; it is not one 12-vertex component. From \(D=2\) onward in this table, the reported orbit union agrees with the corresponding full symmetric component.

(d) SHA-256 checksums of the sorted canonical point pairs are:

| \(D\) | SHA-256 | |---:|---| | 1 | 7947e1d77ff6ab5221eb30e5263111cc84b6bd38ecadda9dcfed4403b747ae5e | | 2–3 | f1b9cfd0ae4d8cb5a435549d41cf1785b014854afa7c14f3890c3957d13faa65 | | 4–7 | f2933265c372207a319da3b0ace5ee3b817a768ae8e7685b7854ea30237513f5 | | 8–9 | f448db56f6b4a9146054a463811ceb00e866f15688ef8a1060cf8ce22532b3e2 | | 10 | 0306196f9e4b5cb31b4c656d6ff86aaf8c6f4ba411f7efce00583c648b11954b |

(d) With coordinate limit 1,100, the largest coordinate whose primality is queried in the \(D=10\) closure check is 988, leaving a margin of 112. Ordinary primality is supplied by a literal Eratosthenes sieve through 2,420,000. Thus no untested point can be an omitted neighbor of these finite components.

5. Reproduction

The standalone checker is runs/erdos952_wavew024_verify.py (482 lines, no nonstandard packages).

python3 runs/erdos952_wavew024_verify.py

(d) On this VM it completed in 7.80 seconds. Its file SHA-256 at report time is:

e558480b48810d96d833cf5f92abe9b16e8bb2c3b5b18b05e453606e91681dd7

(d) A second run with a larger coordinate limit and reversed thresholds,

python3 runs/erdos952_wavew024_verify.py --limit 1200 --D 10 8 4 2 1

again returned global bound 100 and all five point-set hashes above. python3 -m py_compile also succeeded.

The checker makes the following assertions internally:

base domain                         76050
base eligible residues             18432
base components                     3618
base maximum component                71
nonzero winding conflicts               0
generic maximum after CRT layers       49
exceptional prime classes              36
exceptional actual component size     100
exceptional actual edges              120
global G_2 component maximum          100

6. What remains, and the exact wall

(b) Existing rigorous computations/theorems cover two different finite regimes:

Neither statement handles arbitrary \(D\).

(a) The exact missing assertion is:

For every integer \(D\), the component of \(1+i\) in \(G_D\) is finite.

By Section 2, this statement is equivalent to a negative answer to the live problem. No uniform numerical bound on the component sizes is needed, but the quantifier over every \(D\) cannot be replaced by any finite computation.

(a) A sufficient finite lemma, modelled on the successful \(D=2\) certificate, would be:

For every \(D\), there is a finite set \(S_D\) of Gaussian-prime divisors such that the graph of residue classes coprime to \(\prod_{\pi\in S_D}\pi\), with edge offsets of squared norm at most \(D\), has no component with nonzero translational winding; the finitely many exceptional divisor-primes also have finite components.

Proving this periodic-sieve lemma for all \(D\) would settle the problem negatively. The present computation proves it only for \(D=2\); Gethner–Stark give a different large periodic construction for \(D=4\).

(a) A naive full-torus verification of the published \(D=4\) scalar period \(7{,}113{,}990\) would touch

\[ 7{,}113{,}990^2=50{,}608{,}853{,}720{,}100 \]

lattice classes. Even one byte per class would require about 50.6 TB, and eight neighbor tests per class would be about \(4.0\times10^{14}\) edge tests. At an optimistic \(10^8\) tests/second this is roughly 1,125 core-hours, before memory and I/O. The 1997 paper avoids this naive cost by tracing a periodic moat; I did not rerun that heavier construction here.

(c) Prime-density/percolation heuristics predict that fixed-radius components should eventually be subcritical, hence finite. They do not control the exceptional zero-density path whose existence is at issue.

(a) Chinese-remainder constructions can create arbitrarily large finite composite patches or isolated Gaussian primes, but a patch at an uncontrolled location does not give a closed separator around the rooted component. The missing ingredient is global placement/topology of separators, not the ability to manufacture local compositeness.

(a) Average equidistribution of Gaussian primes in sectors likewise cannot exclude a single sparse infinite connected component. This is the precise reason standard density estimates do not close the finiteness quantifier.

PARTIAL: exact start-anywhere computation gives maximum \(G_2\)-component size 100 and reproduces rooted moat data through \(D=10\); arbitrary bounded step remains open.

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger