# Walking to infinity on the primes: The prime-spiral moat problem

It is an unsolved problem to decide if it is possible to "walk to infinity" from the origin with bounded-length steps, each touching a Gaussian prime as a stepping stone. The paper by Ellen Gethner, Stan Wagon, and Brian Wick, "A Stroll through the Gaussian Primes" (American Mathematical Monthly, 105: 327-337 (1998)) discusses this Gaussian moat problem and proves that steps of length $< \sqrt{26}$ are insufficient. Their result was improved to $\sqrt{36}$ in 2005.

My question is:

Is the analogous question easier for the prime spiral (a.k.a. Ulam spiral)—Can one walk to infinity using bounded-length steps touching only the spiral coordinates of primes?

What little I know of prime gaps suggest that should be easier to walk to infinity. For example, the first gap of 500 does not occur until about $10^{12}$ (more precisely, 499 and 303,371,455,241).

I ask this primarily out of curiosity, and have tagged it 'recreational.'

Edit1. In light of Gjergji's remarks below, I have tagged this as an open problem.

Edit2'. Just for fun, I computed which primes are reachable on a small portion of the spiral, for step distances $d \le 3$ (left below) and $d \le 4$ (right below); red=reached, blue=not reached. The former does not reach 83, the 23rd prime blue dot barely discernable at spiral coordinates (5,-3); the latter does not reach 5087, the 680th prime blue dot at spiral coordinates (36,10).

-
quick question: stepping back is not allowed? –  sleepless in beantown Sep 8 '10 at 3:14
@sleepless: I consider "stepping back" as permitted. And I allowed that in the above computation. But because I only looked at a portion of the spiral, it turns out that 2357 is reachable with $d=4$ but that requires backward steps from portions of the spiral further out. I'll recompute... –  Joseph O'Rourke Sep 8 '10 at 12:37
An interesting generalization: Consider a d-island to be a set of those primes that are reachable from one another by a set of steps of length at most d. How many 3-islands are at distance r from the origin? How many 4-islands? The pictures suggest sublinear growth, a.k.a less than r such islands for either value of d. Gerhard "Ask Me About System Design" Paseman, 2010.09.08 –  Gerhard Paseman Sep 8 '10 at 15:09
@Gerhard: Interesting question! Incidentally, to gauge $r$ in the images: the left image coordinates run $\pm 75$, the right image coordinates $\pm 100$. –  Joseph O'Rourke Sep 8 '10 at 17:00

I don't know if any of the probabilistic or percolation models related to the Gaussian (Eisenstein etc.) prime walks have analogues for the problem you suggest. However note that if such an infinite walk was possible it would imply that the gap between successive primes would be $O(\sqrt{p})$, i.e. it is a (slightly weaker) form of Legendre's conjecture. Also note that this is stronger than the bound on prime gaps implied by the Riemann hypothesis which is $O(\sqrt{p}\log p)$, so no, the problem you suggest is not any easier than the other conjectures about patterns of primes.

-
Thanks, Gjergji! That article you cite ends with this: "Legendre's conjecture implies that at least one prime can be found in every revolution of the Ulam spiral." –  Joseph O'Rourke Sep 6 '10 at 18:06
While your conjecture implies that there is a prime every $d$ revolution, where $d$ is the bounded distance. This is weaker but not any easier as I describe above. –  Gjergji Zaimi Sep 6 '10 at 18:17
Yes, I see; nice analysis! I wonder now what is the largest width of a known spiral moat, the analog of the $\sqrt{26}$ and $\sqrt{36}$ bounds for Gaussian primes... –  Joseph O'Rourke Sep 6 '10 at 18:29
I don't know because I don't think the problem as stated has been investigated before. –  Gjergji Zaimi Sep 6 '10 at 19:08

Percolation theory suggests that the probability one can one can walk to infinity is 1 if the density of randomly chosen stepping stones is at least a certain critical number, and is 0 if the density is less than this number. Since the density of primes in the Ulam spiral and the density of Gaussian primes in the plane both tend to zero, the density of stepping stones is 0. This suggests that one cannot walk to infinity on either primes in the Ulam sprial or Gaussian primes, for any bounded size of step.

-
It is an interesting heurestic, but I have two reservations: (1) This situation corresponds to "long-range" percolation (not sure whether this is a completely standard term). Is it presumed to behave in the same way (i.e. non-zero critical density)? (2) Primes are not entirely uncorrelated due to the usual business with reductions mod n, so it furthermore appears to be a "dependent" percolation. How does that affect the anticipated outcome? –  Victor Protsak Sep 7 '10 at 3:32
To add to what Victor said, in the case of the Ulam spiral, doesn't Bateman-Horn predict that the distribution is not really uniform? i.e. there are different densities on different diagonals. –  Gjergji Zaimi Sep 7 '10 at 4:16