Gaussian prime spirals

Imagine a particle in the complex plane, starting at $c_0$, a Gaussian integer, moving initially $\pm$ in the horizontal or vertical directions. When it hits a Gaussian prime, it turns left $90^\circ$. For example, starting at $12 - 7 i$, moving initially $+x$, this closed circuit results:

Instead, starting at $3+5 i$, again $+x$, this (pleasingly symmetric!) closed cycle results:

Here's another (added later), starting at $5+23 i$:

(Gaussian primes $a+bi$ off-axes have $a^2+b^2$ prime; on axis, $\pm(4n+3)$ prime.)
My question is,

Q0.What's going on?

More specifically,

Q1. Does the spiral always form a cycle?

Q2. Have these spirals been investigated previously?

(I am about to step on a plane; apologies for not acknowledging responses!) ...Later:

Q3. Under what conditions is the spiral (assuming it closes) symmetric w.r.t. reflection in a horizontal (as is $12-7 i$), or reflection in a vertical (as is $5 + 23 i$), or reflection in both (as is $3 + 5i$)?

-
Nice spirals ! Regarding Q1, it will be probably hard to prove this is always the case, given that it's unknown whether there are infinitely many Gaussian primes of the form $n+i$ with $n \in \mathbf{Z}$. So starting at $N+i$ and moving $+x$, we cannot exclude the possibility of hitting no prime. –  François Brunault Mar 16 '12 at 22:54
+1 for "step on a plane". Will you meet gaussian primes ? –  BS. Mar 16 '12 at 23:43
Is there something similar for Eisenstein primes? This plot shows some patterns: mathworld.wolfram.com/EisensteinPrime.html –  joro Mar 17 '12 at 6:20
Hi Joseph! If you fix your closed cycle (the shape, not the location), it would correspond to a fixed pattern of prime and composite Gaussian integers along that fixed path. Perhaps heuristics might give the conjectural asymptotics for the number of such cycles with that shape in a disk of radius $M$ centered at the origin. –  user22202 Mar 18 '12 at 1:10
Typo on the first line (Guassian). (I don't have edit privileges.) –  Pierre-Yves Gaillard Mar 18 '12 at 9:48

5 Answers

Expanding slightly on Greg Martin's answer, the symmetry applies across the imaginary axis as well as the real axis, so the only way a path can avoid closing up is if it crosses at most one axis at most once (and if it does cross an axis, the path -- if extended in the backward as well as forward direction -- will be mirror symmetric with respect to the axis it crosses). Note that within a quadrant the horizontal (respectively vertical) steps are alternately toward and away from the imaginary (respectively real) axis.

Intuitively the steps, on average, get larger the further you are from the axes. So if you're in the first quadrant and take a step to the right and then a step up, you expect your next step, to the left, to be somewhat larger than your previous step to the right (and similarly with the next step down, assuming you're still in the first quadrant). So in a sense the axes are exerting kind of a gravitational tug on sort of a random walk. Of course, nothing of the sort is literally going on. Still, it seems hard to imagine the stars (I mean Gaussian primes) aligning to keep a random walk going in perpetuity.

It seems more likely one might encounter closed paths that don't have any nice symmetry, such as $$(a,b) \rightarrow (a+4,b) \rightarrow (a+4,b+8) \rightarrow (a-2,b+8) \rightarrow$$ $$(a-2,b+4) \rightarrow (a+2,b+4) \rightarrow (a+2,b+6) \rightarrow (a,b+6) \rightarrow (a,b)$$

(Sorry, if someone could replace that with a picture, that would be helpful.) As "unknown" pointed out, there are certainly closed square paths that stay in the first quadrant. There are also rectangles, such as the $2\times4$ rectangle with $8+13i$ for its lower left hand corner and the $2\times6$ one starting at $14+19i$. (I spotted these in a picture of Gaussian primes of norm less than 1000 in the paper "A Stroll Through the Gaussian Primes" by Gethner, Wagon, and Wick.) One might expect a souped-up (supped-up?) $k$-tuple conjecture to predict the existence of any closed-path pattern that isn't forbidden by the usual suspects. (Part of the souping up, though, is that not only are there primes at the specified corners, but everything else along the edges is composite.)

All in all, a nice problem -- and the spirals, reminiscient of Celtic knots, are really lovely!

-
Very insightful, Barry! (I added a picture of your 8-cycle.) –  Joseph O'Rourke Mar 18 '12 at 16:35
Suppose the Gaussian prime $k$-tuples conjecture were true with the expected order of magnitude; in your example, suppose that $a+bi$, $(a+4)+bi$, $(a+4)+(b+8)i$, ..., $a+(b+6)i$ were all Gaussian primes for $\gg X/(log X)^k$ values $1\le a,b\le X$. Then the "$(k+1)$-tuples conjecture" (i.e., the same conjecture with one additional required prime value) would also imply that most of the time there were no other intervening Gaussian primes - those examples would be $\ll X/(log X)^{k+1}$ in number). –  Greg Martin Mar 22 '12 at 22:33

Stan Wagon, coauthor of the award-winning article "A Stroll through the Gaussian Primes," became intrigued, and sent me these two stunning images. The first is a different rendering of the 2,956-cycle I posted earlier:

The second is a Rorschach-like cycle of 316,268 primes he found:

(seed: $232+277 i$). [Apologies for the loss of resolution converting for this forum.]

Soon there will be a Mathematica Demonstration Project on this topic; it currently awaits approval.

Update. The Mathematica Demo is available at this link:

Using a modification of this code, Stan has found a cycle of length 3,900,404. Seed: $107 + 992 i$.

(16Feb13): Stan Wagon worked with Walter Stromquist, the editor of Mathematics Magazine, on the cover of the February 2013 issue, which displays the spiral immediately above:

-

Just for your amusement, here is a spiral of length 2,956 primes that crosses just one axis, and hits no prime on that axis. I encountered it twice, once in a horizontal orientation (seed: $12+28 i$) and once in a vertical orientation (seed: $43 + 55 i$). That it should occur twice is a consequence of the symmetry of the conditions that render a Gaussian integer prime.

-

Agreed, nice spirals. This is not meant as a complete answer. Heuristically and experimentally, it is very likely that there are infinitely many $x,y\in\mathbb{Z}$ such that $x^2+y^2$, $(x+2)^2+y^2$, $x^2+(y+2)^2$ and $(x+2)^2+(y+2)^2$ are simultaneously prime. (For example, PARI gave $136$ such $(x,y)$ with $1\leq x,y\leq 1000$ and $1330$ such $(x,y)$ with $1\leq x,y \leq 5000$.) Such a result will give Gaussian primes at the corners of a square of side length two and hence infinitely many of the simplest type of cycle. Though it may not directly solve your question, it should be noted that you do get infinitely many squares with Gaussian primes at the corners if you allow the lengths of the sides of the squares to vary, due to the following result:

T. Tao, The Gaussian primes contain arbitrarily shaped constellations, J. d.Analyse Mathematique 99 (2006), 109--176.

Also, heuristically, if you believe the kind of heuristics behind the Hardy-Littlewood $k$-tuple conjecture, the same kind of reasoning should give you the conjectural asymptotics for

$$\sum_{\substack{x,y\in \mathbb{Z}\\1 \leq x,y\leq N}}\Lambda(x^2+y^2)\Lambda((x+2)^2+y^2)\Lambda(x^2+(y+2)^2)\Lambda((x+2)^2+(y+2)^2).$$

-
Beautiful observation that there are an infinite number of square cycles via Tao's result! –  Joseph O'Rourke Mar 17 '12 at 16:05
Actually, my result unfortunately does not quite produce square cycles, because I cannot preclude the existence of primes on the edges of the square with prime corners. I can probably adapt the argument to exclude primes from a bounded number of places (by using a sieve to upper bound the exceptions), but the squares generated by the argument are quite large (the length of the square is comparable to the magnitude of the corners) and so it is actually rather likely that there are intervening primes somewhere along the edges. –  Terry Tao Mar 18 '12 at 17:29

Note that if you start above the real axis, and then one of the steps takes you below the real axis, then the subsequent path will be the mirror image (complex conjugate) of the start of the path. In your second picture, this accounts for the whole left half of the spiral (starting at $3+5i$ and pausing at $3-5i$). Then, if the continuation happens to cross the real axis again, the rest of the path will close up into a closed loop. (This ignores the case where the point on the real axis itself is a Gaussian prime.)

So your question has to do with the (equally mysterious) question of when such paths will hit Gaussian primes of the form $m+ni$ where none of $m$, $m+i$, ..., $m+(n-1)i$ are prime.

-
Nice, Greg, you've addressed several of the symmetry issues that I now added as Q3. –  Joseph O'Rourke Mar 17 '12 at 16:33
Just a remark regarding Greg Martin's nice question (although I know this wasn't really the question): Ignoring the case of whether $M$ is itself a rational prime or not, one way to construct a sequence $M^2+i^2$ all composite for $1\leq i \leq n-1$ is as follows: Consider $m^2+i^2$, $1\leq i \leq n-1$ for any $m\not=0$. Let $P$ be the product of all primes dividing these numbers and $m^{\prime}=m+P$. Then $(m^{\prime})^2 + i^2$ are all composite for $1\leq i \leq n-1$. In this case $m^{\prime}$ is the distance from one of the axes, so it is in line with what Barry Cipra pointed out. –  user22202 Mar 19 '12 at 10:00