Uniformly bounded components of Gaussian-prime graphs

The explanation

Picture a square grid of points a + bi, where a and b are whole numbers. These points are called Gaussian integers. Some of them are Gaussian primes. They cannot be split as a product of two smaller grid points. For example, 2 + i is a Gaussian prime, because 2² + 1² = 5 is an ordinary prime. But 5 itself is not one, since 5 = (2 + i)(2 − i).

Now walk on the primes. Each hop must land on a new Gaussian prime and be at most 1 unit long. Start at 1 + i. You can reach 2 + i and 1 + 2i, and then you are stuck. Start at 3 + 2i and you cannot move at all. Its four neighbours have a² + b² equal to 20, 8, 18 and 10. None of those four points is a Gaussian prime.

The reason is parity. Apart from the four points ±1 ± i, every Gaussian prime has a + b odd. A hop of length 1 changes a + b by one, so it lands where a + b is even. Those points are all divisible by 1 + i. So with hops of length 1, each cluster of linked primes has at most 3 members. Mathematicians call such a cluster a component.

The Gaussian moat problem asks what happens with longer hops. Fix any step limit D, such as 6 or 100. Can a walk visit new Gaussian primes forever, never hopping farther than D? Gethner and Stark trace the question to Basil Gordon, at the 1962 International Congress of Mathematicians in Stockholm. Erdős later credited Gordon and Motzkin with it.

Large empty regions do not settle it. Gethner, Wagon and Wick built prime-free disks centred on lines through the grid. They also built Gaussian primes on the real axis that sit as isolated as you like. But a walk in the plane can go around a disk. Computers could fence in one starting point. In 2005 Tsuchimura bounded how far steps of at most 6 can reach from the origin. That says nothing about walks that start elsewhere.

The closest earlier idea is a repeating block like the parity rule above. Gethner and Stark found such periodic blocks for step limits √2 and 2. For larger limits they proposed sieving by small Gaussian primes. Sieving means deleting every grid point divisible by one of a chosen set of primes. Vardi studied the repeating graphs that result. The missing piece was a finite sieve that provably works for every step limit.

This paper proves the answer is no, in a strong formSource 1. For each D, it picks a finite list of ordinary primes that leave remainder 1 when divided by 4. Each such prime splits into two Gaussian primes. Delete every grid point divisible by any of them. What remains repeats in a fixed patternSource 2. The paper claims that no endless walk with steps at most D fits inside itSource 3. Repetition then caps every cluster at one sizeSource 4. A cluster can never contain two points that differ by one full repeat of the patternSource 5.

The hard part is the sieve, because the walk can be any path at all. The paper samples moments of one walk at randomSource 6. It measures how spread out the walk's remainders are, using entropy, a standard measure of uncertainty. Dodging every deleted point costs the walk a little information at each block of primes. Summed over all blocks, those costs grow without limit. Yet one bounded hop carries only a fixed amount of informationSource 7. So no such walk exists.

Go back to the example. With hops of length 1, every cluster has at most 3 primes. The theorem says a cap like that exists for every step limit DSource 8. Call it B_D. No walk through distinct Gaussian primes with hops at most D has more than B_D stopsSource 1. This holds wherever the walk starts, including on the two axesSource 9. But the proof gives no formula for B_DSource 10. It does not say how far a walk with hops of 6 can go.

How sure is this? A computer proof checker called Lean has checked a formal version of the main theorem. That version covers every step limit, every starting prime, axis primes and all associates. Associates are the copies of a prime rotated by a quarter, half or three-quarter turn about 0. It also gives no explicit formula for the bound. No specialists have published a review yet.

What it doesn't show. This does not give a formula for the bound. It does not say how far a walk with steps of 6 can go.