# The Gaussian moat problem and its extension to other rings in $\mathbb{C}$, $\mathbb{H}$ and $\mathbb{O}$

One of my favourite open problems in number theory, an area in which I enjoy only as a hobbyist, is the Gaussian moat problem, namely

"Is it possible to walk to infinity in $\mathbb{C}$, taking steps of bounded length, using the Gaussian primes as stepping stones?"

We can easily show that one cannot accomplish walking to infinity using steps of bounded length on the real line using primes in $\mathbb{R}$. For an arbitrary natural number $k$, consider the $k-1$ consecutive numbers

$$k! + 2, k! + 3, \ldots k! + k,$$ all of which are composite. This is another way of saying there are arbitrarily large gaps in the primes.

For the Gaussian primes, there is computational proof that a moat of length $\sqrt{26}$ exists, so one cannot walk to infinity using steps of length $5$. Erdos is said to have conjectured that it is impossible to complete the walk. Percolation theory also suggests that the walk is impossible, though to my understanding this heuristic assumes the primes are completely independent in some way.

Eisenstein integers are numbers of the form $a+b\omega$, with $a$, $b \in \mathbb{R}$, where $\omega = \mathrm{e}^{\mathrm{i}\pi/3}$. My first and main question is -

What is the current lower bound for step size in the analogous problem for Eisenstein primes?

Quaternions with all integer components are called Lipshitz integers. So let us call primes over this ring Lipshitz primes. A Lipshitz integer is only a Lipshitz prime if its norm is a prime. Is anything known about the moat problem over $\mathbb{H}$? One might think that given the extra dimensions or degrees of freedom walking to infinity should be easier, however I'm not sure how rare Lipshitz primes are.

Responses to this post point out that factorisation over octonions is not unique, so it is difficult to come up with a concept of primes over $\mathbb{O}$.

• Here is a nice article on the Gaussian problem that really sparked this question for me. Commented May 29, 2014 at 13:35
• And here is a discussion of the problem for the Ulam spiral. Commented May 29, 2014 at 13:45
• Jacobi's four-square theorem implies that the density of Lipschitz primes among Lipschitz integers of norm near $x$ is about a constant times $1/x\log x$. en.wikipedia.org/wiki/… Commented Jun 1, 2014 at 0:56
• I did enjoy the appearance of that theorem when I was looking into that! Thanks for the info. Can you say anything about the moat problem using that? Commented Jun 1, 2014 at 4:58
• @BennettGardiner Done! Commented Dec 27, 2014 at 1:13

Consider an imaginary quadratic field $\mathbb{Q}(\sqrt{d})$ with class number $1$. We may estimate the density of primes contained within a region of symmetry bounded by an ellipse defined by the norm being less than some certain radius $R$ using the following:

Consider a quadratic form with fundamental discriminant $\delta$ of class number $1$. A prime is expressible as such a quadratic form if and only if $\left(\frac{p}{\delta}\right)=1$. Then, due to the fact that an element $\pi\in\mathcal{O}_{\mathbb{Q}(\sqrt{d})}$ in the ring of integers of a quadratic field is prime if and only if its norm $N(\pi)$ is prime, we may estimate the number of primes contained within a region of symmetry as $\sum_{(u/p) = 1}\pi_u(R^2)$, where $\pi_u(x)$ is similar to the prime counting function with the additional constraint that $\bar{p}=\bar{u}$ (in $\mathbb{Z}/\delta\mathbb{Z}$).

Using the Prime Number Theorem and Dirichlet's theorem, it turns out that this is asymptotic to $R^2/4\log R$ for all imaginary quadratic fields of class number $1$.

These density estimates can shed light upon how analogs of the Gaussian moat problem in the imaginary quadratic fields with class number 1 should behave. A very general heuristic is that the smaller the discriminant, the further you can get with a fixed moat size, as there are fewer algebraic integers within a fixed distance, so there are also likely to be fewer primes. In my paper (http://arxiv.org/abs/1412.2310) I derive computational results (similar to what Gethner had done) using an efficient graph-theoretic algorithm in certain imaginary quadratic fields, and the data appears to corroborate what is derived above. For example, with a fixed step size $k$, you can jump the farthest out in the Eisenstein primes, $\mathbb{Z}[e^{i\pi/3}]$, the next farthest out in the Gaussian primes $\mathbb{Z}[i]$, and the least farthest in the primes of $\mathbb{Z}[\sqrt{-2}]$. The data for $\mathbb{Z}\left[\tfrac{-1+\sqrt{-7}}{2}\right]$ is slightly weirder in comparison to these other three rings, but maybe comparing it to the remaining IQFs would yield something interesting.

As for your question, I was able to show that with a step size of at most $\sqrt{12}$, the farthest one may travel on the Eisenstein primes is to the point $20973+3518e^{i\pi/3}$, which is at a distance of around $19454.05$ from the origin. However, based on Erdős's conjecture that there exist arbitrarily large moats among the Gaussian primes, I think it is reasonable to guess that the same holds in the other imaginary quadratic fields as well due to the heuristics described above.

An interesting generalization I also pose (but do not examine) does not restrict ourselves to prime elements: If $S$ is some set of positive integers defined by a particular rule (in our case, primes) and $T=\{\alpha\in\mathcal{O}_{\mathbb{Q}(\sqrt{d})}, d<0:N(\alpha)\in S\}$, how do moats in in $T$ behave? There's also no need to restrict ourselves to class number $1$ (or even imaginary quadratic fields; we could consider prime ideals in real imaginary quadratic fields -- but the geometry is stranger in these domains, or more generally look at moats in Dedekind domains, etc.), and one could look how moat results vary across fields with different class numbers.

Well, see THIS for starters. Ellen Gethner got attracted to Gaussian moats quite early in her career. Stark is the same person as Heegner-Stark-Baker.

I will see what might be available on Eisenstein moats. There was a question on quaternion moats on MO.