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]
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]
References
[edit]- ^ a b c d Gethner, Ellen; Wagon, Stan; Wick, Brian (1998), "A stroll through the Gaussian primes", The American Mathematical Monthly, 105 (4): 327–337, doi:10.2307/2589708, JSTOR 2589708, MR 1614871, Zbl 0946.11002
- ^ Tsuchimura, Nobuyuki (2005), "Computational results for Gaussian moat problem", IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 88 (5): 1267–1273, Bibcode:2005IEITF..88.1267T, doi:10.1093/ietfec/e88-a.5.1267.
Further reading
[edit]- Guy, Richard K. (2004), Unsolved problems in number theory (3rd ed.), Springer-Verlag, pp. 55–57, ISBN 978-0-387-20860-2, Zbl 1058.11001