I just learned how useful the Gaussian integers $\mathbb Z[\mathrm i]$ are for solving problems in $\mathbb Z$ (much like $\mathbb C$ is useful for solving problems in $\mathbb R$), and I was a bit surprised that I hadn’t come across them more often on this site. So I thought I’d ask a fun question about them that might get others interested in them. If you want to learn more about the Gaussian integers, I’d recommend these notes by Keith Conrad.
Here are the first few Gaussian integers (“first” in the sense of the norm $N(a+b\mathrm i)=a^2+b^2)$:
\begin{array}{cc} && \bbox[2pt,color:blue;border-radius:32px;box-shadow:4px 4px 4px blue]{-1+3\mathrm i} & \bbox[2pt,color:green;box-shadow:4px 4px 4px green]{3\mathrm i} & \bbox[2pt,color:blue;border-radius:32px;box-shadow:4px 4px 4px blue]{1+3\mathrm i} \\ & \bbox[2pt,color:blue;border-radius:32px;box-shadow:4px 4px 4px blue]{-2+2\mathrm i} & \bbox[2pt,color:green;box-shadow:4px 4px 4px green]{-1+2\mathrm i} & \bbox[2pt,color:blue;border-radius:32px;box-shadow: 3px 3px 3px blue]{2\mathrm i} & \bbox[2pt,color:green;box-shadow:4px 4px 4px green]{1+2\mathrm i} & \bbox[2pt,color:blue;border-radius:32px;box-shadow: 3px 3px 3px blue]{2+2\mathrm i} \\ \bbox[2pt,color:blue;border-radius:32px;box-shadow:4px 4px 4px blue]{-3+\mathrm i} & \bbox[2pt,color:green;box-shadow:4px 4px 4px green]{-2+\mathrm i} & \bbox[2pt,color:green;box-shadow:4px 4px 4px green]{-1+\mathrm i} & \bbox[2pt,color:red;border-radius:32px;box-shadow:4px 4px 4px red]{\mathrm i} & \bbox[2pt,color:green;box-shadow:4px 4px 4px green]{1+\mathrm i} & \bbox[2pt,color:green;box-shadow:4px 4px 4px green]{2+\mathrm i} & \bbox[2pt,color:blue;border-radius:32px;box-shadow:4px 4px 4px blue]{3+\mathrm i} \\ \bbox[2pt,color:green;box-shadow:4px 4px 4px green]{-3} & \bbox[2pt,color:blue;border-radius:32px;box-shadow:4px 4px 4px blue]{-2} & \bbox[2pt,color:red;border-radius:32px;box-shadow:4px 4px 4px red]{-1} & \bbox[2pt,color:black;box-shadow:4px 4px 4px black]{0} & \bbox[2pt,color:red;border-radius:32px;box-shadow:4px 4px 4px red]{1} & \bbox[2pt,color:blue;border-radius:32px;box-shadow:4px 4px 4px blue]{2} & \bbox[2pt,color:green;box-shadow:4px 4px 4px green]{3} \\ \bbox[2pt,color:blue;border-radius:32px;box-shadow:4px 4px 4px blue]{-3-\mathrm i} & \bbox[2pt,color:green;box-shadow:4px 4px 4px green]{-2-\mathrm i} & \bbox[2pt,color:green;box-shadow:4px 4px 4px green]{-1-\mathrm i} & \bbox[2pt,color:red;border-radius:32px;box-shadow:4px 4px 4px red]{-\mathrm i} & \bbox[2pt,color:green;box-shadow:4px 4px 4px green]{1-\mathrm i} & \bbox[2pt,color:green;box-shadow:4px 4px 4px green]{2-\mathrm i} & \bbox[2pt,color:blue;border-radius:32px;box-shadow:4px 4px 4px blue]{3-\mathrm i} \\ & \bbox[2pt,color:blue;border-radius:32px;box-shadow:4px 4px 4px blue]{-2-2\mathrm i} & \bbox[2pt,color:green;box-shadow:4px 4px 4px green]{-1-2\mathrm i} & \bbox[2pt,color:blue;border-radius:32px;box-shadow: 3px 3px 3px blue]{-2\mathrm i} & \bbox[2pt,color:green;box-shadow:4px 4px 4px green]{1-2\mathrm i} & \bbox[2pt,color:blue;border-radius:32px;box-shadow: 3px 3px 3px blue]{2-2\mathrm i} \\ && \bbox[2pt,color:blue;border-radius:32px;box-shadow:4px 4px 4px blue]{-1-3\mathrm i} & \bbox[2pt,color:green;box-shadow:4px 4px 4px green]{-3\mathrm i} & \bbox[2pt,color:blue;border-radius:32px;box-shadow:4px 4px 4px blue]{1-3\mathrm i} \end{array}
Zero is black, units are red, primes are green and composites are blue. (Fun fact: The first prime in $\mathbb Z$, $2$, is the first composite in $\mathbb Z[\mathrm i]$.)
Consider a simple symmetric random walk on the Gaussian integers, starting at zero.
a) What’s the probability that it reaches a prime before it reaches a composite?
b) What’s the expected time to reach a prime?
c) What’s the expected time to reach a composite?
(Note that only the Gaussian integers depicted above are needed to answers these questions.)
a) This one’s straightforward: Each unit has two prime neighbours and one composite neighbour, so the probability to reach a prime first is $\frac23$.
b) There are three possible states before a prime is reached: The associates of $0$, $1$ and $2$, respectively. The expected times $E_k$ for reaching a prime from state $k$ satisfy
\begin{eqnarray} E_0&=&1+E_1\;,\\ E_1&=&1+\frac14E_0+\frac14E_2\;,\\ E_2&=&1+\frac14E_1\;. \end{eqnarray}
Substituting the first and third equations into the second yields $E_1=\frac{24}{11}$, and substituting that into the first equation yields $E_0=\frac{35}{11}=3.\overline{18}$.
c) This one’s a bit more complicated. There are $4$ possible states before a composite is reached: the associates of $0$, $1$, $1+\mathrm i$ and $2+\mathrm i$, respectively. The expected times $E_k$ for reaching a prime from state $k$ satisfy
\begin{eqnarray} E_0&=&1+E_1\;,\\ E_1&=&1+\frac14E_0+\frac12E_{1+\mathrm i}\;,\\ E_{1+\mathrm i}&=&1+\frac12E_1+\frac12E_{2+\mathrm i}\;,\\ E_{2+\mathrm i}&=&1+\frac14E_{1+\mathrm i}\;. \end{eqnarray}
Substituting from the bottom up yields $E_{1+\mathrm i}=\frac{12}7+\frac47E_1$, then $E_1=\frac{13}5+\frac7{20}E_0$, and then $E_0=\frac{72}{13}\approx5.54$, nearly twice as long as it takes to reach a prime.