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

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

2010-09-06T16:05:24Z

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 23^rd prime blue dot barely discernable at spiral coordinates (5,-3); the latter does not reach 5087, the 680^th prime blue dot at spiral coordinates (36,10).

Answer by Gjergji Zaimi for Walking to infinity on the primes: The prime-spiral moat problem

2010-09-06T16:53:58Z

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.

Answer by Richard Borcherds for Walking to infinity on the primes: The prime-spiral moat problem

2010-09-07T00:51:02Z

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.