A walk on Gaussian primes stopped by a moat

Which way a prime’s two squares point drew every prime $p = a^2 + b^2$ as the point $(a, b)$ and found the points spread evenly in angle, as Hecke proved. Those points are the Gaussian primes: the primes of the ring of Gaussian integers $a + bi$, which factoring uniquely with no way to divide showed has unique factorisation. A Gaussian integer with both $a$ and $b$ nonzero is prime exactly when $a^2 + b^2$ is an ordinary prime, and one lying on an axis is prime exactly when its size is an ordinary prime of the form $4k + 3$. Plotted in the plane, they form a pattern with the eightfold symmetry of the square and a density that thins slowly outward.

This essay asks a question about that pattern that has the flavour of a children’s puzzle and the status of a famous open problem. Can a walker start near the origin and walk to infinity stepping only on Gaussian primes, if every step has length at most some fixed bound? Basil Gordon asked it in 1962, and nobody knows the answer for any bound — although every bound that has been tried has turned out to be too small. The figures carry out the walk for small step lengths, find the moats that stop it, and measure why moats should be expected and why they are so hard to find for larger steps.

The walk and its moat #

Fix a step length $s$ and join two Gaussian primes when their distance is at most $s$. The primes a walker can reach from $1 + i$ are the component of $1 + i$ in this graph. The question is whether that component is finite or infinite. If it is finite, there is a ring round it — a moat of width $s$ — containing no Gaussian prime within $s$ of the component, and the walker is trapped inside.

The figure’s walk uses $s = 2$. From $1 + i$ the walker can reach $2 + i$ and $1 + 2i$ and their neighbours, and the component spreads through the dense pattern near the origin, where small Gaussian primes are crowded together. It reaches 720 Gaussian primes in all, the farthest of them $17 + 42i$ at distance $45.3$, and then stops: every Gaussian prime within 2 of the component is already in it. The search that establishes this is a breadth-first search over the Gaussian primes in a disc large enough to contain the component with room to spare, here of radius two hundred, and its correctness rests on one check: the search never reaches the disc’s edge, so no route out was cut off by the edge of the computation.

The Gaussian primes beyond the moat are no sparser than those inside it in any noticeable way. The component is not stopped by a desert, only by a ring that happens to have no prime within reach of the component’s outermost members. That is why the problem is hard: a moat is a coincidence of local arithmetic, a ring of composite Gaussian integers of a particular width at a particular place, and nothing predicts where one will be.

Only some step lengths exist #

Not every distance can separate two Gaussian primes, and working out which can tells the search which cases are genuinely different. Apart from $1 + i$ and its three companions $\pm1 \pm i$, every Gaussian prime has an odd norm $a^2 + b^2$, so exactly one of $a$ and $b$ is odd. Call a prime upright when its real part is odd and sideways when its imaginary part is odd: $2 + i$ is upright, $1 + 2i$ is sideways, and multiplying by $i$ turns each kind into the other.

The difference of two upright primes has both parts even, so its squared length is a multiple of 4: one of 4, 8, 16, 20, 32, 36 and so on. The difference of an upright and a sideways prime has both parts odd, so its squared length is a sum of two odd squares, which leaves remainder 2 on division by 8: one of 2, 10, 18, 26, 34 and so on. A squared length that is odd — 1, 5, 9, 13 — never separates two odd-norm Gaussian primes at all. So a walk allowed steps of $\sqrt5$ is the same walk as one allowed steps of 2, since no step of exactly $\sqrt5$ ever lands on a prime, and the genuinely different cases are the squared lengths 2, 4, 8, 10, 16, 18, 20, 26 and so on. That is why the next figure’s five walks, for $k = 2, 4, 8, 10$ and $16$, are consecutive rather than a selection.

The rule also says how a walk moves. A step of squared length 2, 10 or 18 always changes the prime’s kind; a step of squared length 4, 8 or 16 never does. A walker restricted to steps of $\sqrt2$ alternates kinds at every step, which is the plane’s version of the rule that consecutive odd primes on the line are at an even distance. The starting point is the one exception: $1 + i$ has norm 2, the only even norm a Gaussian prime can have, and it sits at distance 1 from both $2 + i$ and $1 + 2i$, so the walk’s first step is the only one that can be shorter than $\sqrt2$. This is the same arithmetic that the patterns primes are allowed to make applies on the line: a congruence decides which configurations can occur at all before any question of how often they occur.

Longer steps reach enormously farther #

The next figure repeats the walk for five step lengths and records how far each gets.

With steps of $\sqrt2$ — only to diagonal neighbours — the walk reaches a hundred primes and stops at distance $11.7$. With steps of 2 it reaches 720 and stops at $45.3$. With $\sqrt8$, 2,996 primes and $93.5$. With $\sqrt{10}$ the component explodes: a quarter of a million primes, the farthest at $1{,}024.4$. With steps of 4, 2,780,476 primes, the farthest $-3{,}297 - 2{,}780i$ at $4{,}312.6$. With steps of $\sqrt{18}$ the walk reaches the edge of a disc of radius 4,500, the largest searched here, still going. The only possible step lengths are square roots of sums of two squares, so these are consecutive cases, and each one reaches dramatically farther than the last. Ellen Gethner, Stan Wagon and Brian Wick proved in 1998, by a far larger computation of the same kind, that a moat of width $\sqrt{26}$ exists, so the walk with steps that long is stopped too; Nobuyuki Tsuchimura’s searches later pushed the proven width further. Each such proof is a search, never an argument.

A quarter of a million primes, then nothing #

The $\sqrt{10}$ component is large enough to have a shape.

It fills most of the disc it reaches. Over large stretches of that region the squares are warm — most of the Gaussian primes in them belong to the component — because at these densities a step of $\sqrt{10}$ usually finds a neighbouring prime. The component’s edge is ragged, with tongues pushing out and bays cut in, and beyond it lies a region in which the Gaussian primes are just as numerous but no longer connected to the component. The farthest prime reached, $-311 + 976i$, sits at the tip of one of the tongues. The picture is the one that percolation produces when a random set of sites is close to its critical density: large clusters with fractal edges, which the moment a giant appears met for random graphs. Here the density is not fixed but falls slowly with the distance, so a cluster that is supercritical near the origin must eventually reach a region where it is subcritical, and stop.

Why moats should exist #

That last thought is the heuristic argument that moats exist for every step length, and the next figure makes it quantitative.

The prime number theorem for Gaussian integers says that the Gaussian primes near distance $r$ occupy a share about $4/(\pi \ln r^2)$ of the Gaussian integers there. The counts in the figure agree: the measured density in rings round radius 30, 100, 300, 1,000 and 3,000 is $0.190$, $0.132$, $0.111$, $0.092$ and $0.079$, against predictions of $0.187$, $0.138$, $0.112$, $0.092$ and $0.080$. So the expected number of Gaussian primes within a step of length $\sqrt k$ of a given point falls like $4k/\ln r^2$ — slowly, but without limit. If the primes were scattered at random with that density, a percolation argument would show that every cluster is finite for every fixed step, because eventually the expected number of neighbours drops below the critical value and the cluster dies out. The decline is only logarithmic, which is why the moats are so far away: for a step of $\sqrt{26}$ the expected number of neighbours at distance a million is still nearly four, and the cluster survives that long because four neighbours on average is enough to keep most of a dense pattern connected.

Where that density comes from is worth seeing, because it is the sieve working in two dimensions. Crossing out the composites built the ordinary primes by removing multiples of each prime in turn. The Gaussian version removes the multiples of each Gaussian prime $\pi$, which form a square lattice rotated and scaled so that it contains one point in every $N(\pi)$, where $N(\pi) = a^2 + b^2$ is the norm. A Gaussian integer survives the sieve when it avoids every one of those lattices. Each surviving point is counted in eight orientations by the symmetries of the square, and an ordinary prime $p = a^2 + b^2$ accounts for eight Gaussian primes with norm $p$; counting them by norm turns the prime number theorem’s $x/\ln x$ primes below $x$ into $4r^2/\ln r^2$ Gaussian primes in a disc of radius $r$, which is the density in the figure. The primes on a spiral showed what sieving does to the appearance of the ordinary primes laid out in the plane: diagonal streaks where a quadratic polynomial avoids small factors. The Gaussian primes carry the same kind of structure: along a horizontal line $b = c$, the values $a^2 + c^2$ form a quadratic polynomial in $a$, and some such lines avoid small prime factors far more often than others, so the Gaussian primes are denser along them. A ring that crosses mostly unfavourable lines is where a moat is more likely to be found, and that local unevenness is exactly what a random model leaves out.

The heuristic is convincing and is not a proof, because Gaussian primes are not random. They have arithmetic correlations — they avoid certain residues, they come in symmetric sets of eight — and a proof that moats exist would have to show that those correlations cannot conspire to keep a path open for ever.

On the line, every walk is stopped #

The one-dimensional version of the question has an easy answer, and seeing why makes the planar version’s difficulty clear.

On the line, a walker on the primes with steps of at most $s$ is stopped at the first gap longer than $s$: steps of 2 stop at 7, since the next prime is 11; steps of 4 stop at 23; steps of 6 at 89; steps of 14 at 523, before the gap of eighteen to 541. Every walk is stopped, because gaps between primes are unbounded: the hundred numbers $101! + 2$ to $101! + 101$ are all composite, the first divisible by 2, the next by 3, and so on, and the same construction gives a gap of any length. That is a moat, built to order. The moats a walker meets first are much smaller than the factorial’s. The longest wait for a prime described Harald Cramér’s model, in which the longest gap below $x$ is about $(\ln x)^2$. By that measure a walk with step $s$ on the line should be stopped near $e^{\sqrt s}$, and the figure’s numbers show the actual gaps running somewhat short of Cramér’s scale: the walk with steps of 112 is stopped at 492,113, where the next prime is 114 further on and $(\ln x)^2$ is about 172. The record gaps sit at roughly two-thirds of the model’s value through this range. Either way, the stopping point grows like an exponential of a power of the step, which is the one-dimensional echo of the explosive growth in the plane.

In the plane no such construction is known. A Gaussian prime has many neighbours within any step length, in every direction, and building a ring of composite Gaussian integers round the origin of a given width would require making every Gaussian integer in an annulus composite at once — a set whose size grows with its radius, unlike the line’s interval of fixed length. The factorial trick produces composites along a line; nothing produces them round a circle. The wait for the next sum of two squares measured the gaps between sums of two squares on the line, which are bounded in a far more irregular way, and the planar arrangement of those same numbers is what the moat problem is about.

What the searches cannot show #

Each search is exhaustive within its disc and decisive when the walk stops inside it: the component for steps up to 4 is finite, its farthest member is the one found, and the moat round it exists. For steps of $\sqrt{18}$ the search reaches its edge, and the figure can say only that the walk goes at least that far; the published searches that found its moat used different methods and far larger computations, which this essay reports and does not repeat. Nothing in any finite search can show that a walk with some step goes on for ever, since that is a statement about the infinite pattern.

The heuristic figure, likewise, shows that the density of Gaussian primes follows the prime number theorem closely over the radii measured, and that the expected number of neighbours falls like a logarithm. It does not show that the actual Gaussian primes behave like a random scatter of that density in the respects that matter for connectivity, which is the gap a proof would have to cross.

Still open: Gordon’s question #

Is there a step length that lets a walker reach infinity on Gaussian primes? Everything suggests not: every step length tried has been stopped, the stopping distances grow in a way the percolation heuristic explains, and the analogous question on the line has the answer no for a simple reason. But the problem has resisted proof for sixty years, and the reason is the one the line makes visible — there is no known way to force a ring of composites in the plane. Even the weaker statement that the walk with some particular step, say $\sqrt{26}$, is finite needed a substantial computation to establish rather than an argument.

Variants are equally open. In the Eisenstein integers, the hexagonal lattice of numbers $a + b\omega$ with $\omega$ a cube root of unity, the same question can be asked and the same pattern of moats found by search. In higher dimensions, using the Hurwitz quaternions that the integers among the quaternions described, the primes are denser around each point, and whether moats exist there at all is unclear.

A coincidence repeated without end #

A moat is a coincidence: a ring round the origin of a particular width in which no Gaussian integer happens to be prime close enough to the walker’s territory. The searches find one for every step tried, at distances that grow explosively with the step — 11.7, 45.3, 93.5, 1,024, 4,313 — and the prime number theorem explains why they should keep appearing, since the primes thin out without limit. But a coincidence that must happen eventually is not one that can be guaranteed to happen, and the gap between the two is the Gaussian moat problem. On the line, where a factorial builds a moat to order, the problem is trivial; in the plane, with the same primes arranged by their two squares, it is open.