Gaussian moat

In number theory, the Gaussian moat problem asks whether it is possible to find an infinite sequence of distinct Gaussian prime numbers such that the difference between consecutive numbers in the sequence is bounded. More colorfully, if one imagines the Gaussian primes to be stepping stones in a sea of complex numbers, the question is whether one can walk from the origin to infinity with steps of bounded size, without getting wet. The problem was first posed in 1962 by Basil Gordon (although it has sometimes been erroneously attributed to Paul Erdős) and it remains unsolved.[1]

The Gaussian primes with real and imaginary part at most seven, showing portions of a Gaussian moat of width two separating the origin from infinity

With the usual prime numbers, such a sequence is impossible: the prime number theorem implies that there are arbitrarily large gaps in the sequence of prime numbers, and there is also an elementary direct proof: for any n, the n − 1 consecutive numbers n! + 2, n! + 3, ..., n! + n are all composite.[1]

The problem of finding a path between two Gaussian primes that minimizes the maximum hop size is an instance of the minimax path problem, and the hop size of an optimal path is equal to the width of the widest moat between the two primes, where a moat may be defined by a partition of the primes into two subsets and its width is the distance between the closest pair that has one element in each subset. Thus, the Gaussian moat problem may be phrased in a different but equivalent form: is there a finite bound on the widths of the moats that have finitely many primes on the side of the origin?[1]

Computational searches have shown that the origin is separated from infinity by a moat of width 6.[2] It is known that, for any positive number k, there exist Gaussian primes whose nearest neighbor is at distance k or larger. In fact, these numbers may be constrained to be on the real axis. For instance, the number 20785207 is surrounded by a moat of width 17. Thus, there definitely exist moats of arbitrarily large width, but these moats do not necessarily separate the origin from infinity.[1]