How much of an infinite board can a N-mover reach?

This question is inspired by the question on codegolf.SE: N-movers: How much of the infinite board can I reach?

A N-mover is a knight-like piece that can move to any square that has a Euclidean distance of $\sqrt{N}$ from its current square. That is, it can move from $(0, 0)$ to $(x, y)$ if and only if $x^2 + y^2 = N$ (And of course $x$ and $y$ need to be integers). For example, a 1-mover can move to any of the four adjacent grids, and a 5-mover is a regular chess knight.

Consider an infinite board. Starting from a given grid, what proportion of the infinite grid can a N-mover reach? For clarity, let's say the answer is defined as $$\lim_{n \to \infty} \frac{\text{The number of grids }(x,y)\text{ with }|x|,|y|<=n\text{ and reachable from }(0,0)}{(2n+1)^2}$$

Some thoughts:

• If we treat each grid and possible move as a Gaussian integer, the reachable grids are sums of Gaussian integer multiples of the moves (we can multiply by $i$ because our set of moves is 4-fold rotational symmetric). Using Bezout's identity, they are the multiples of the GCD. Therefore, the answer should be $1/|d|^2$ where $d$ is the GCD of the moves if there are possible moves, or 0 otherwise.
• Let's call the answer $f(N)$. Some experimenting shows that $f$ is multiplicative, with $$f(p^n) = \begin{cases}1/2^n, & \text{if } p = 2 \\ 1, & \text{if } p = 4k+1 \\ 0, & \text{if } p = 4k+3, n\text{ is odd} \\ 1/p^n, & \text{if } p = 4k+3, n\text{ is even}\end{cases}$$

I've been trying to prove the above result for some time. I think it is closely related to the two-squares theorem but I'm not very familiar with this area.

Solution 1:

For a positive integer $N$, write $N=2^k\left(\prod_ip_i^{l_i}\right)\left( \prod_jq_j^{m_j}\right)$, where the $p_i$ and $q_j$ are primes with $p_i\equiv1\pmod{4}$ and $q_j\equiv3\pmod{4}$. The proportion of the grid that an $N$-mover can reach is $$f(N)=\left\{\begin{array}{ll} 0&\text{ if } m_j\ \text{ odd for some } j\\ 2^{-k}\prod_jq_j^{-m_j}&\text{ otherwise} \end{array}\right.,$$ so your conjecture is correct. The proof below is by induction on the prime factors of $N$

In the base case $N=1$ clearly $f(N)=1$ as the $N$-mover can make the moves $(1,0)$ and $(0,1)$.

If the $N$-mover can make the move $(u,v)$ then clearly the $4N$-mover can make the move $(2u,2v)$. Conversely, if the $4N$-mover can make the move $(r,s)$ then $$4N=r^2+s^2,$$ and reducing mod $4$ shows that both $r$ and $s$ are even, say $r=2u$ and $s=2v$. Then $$u^2+v^2=\frac{r^2+s^2}{4}=N,$$ so the $4N$-mover can make the move $(r,s)$ if and only if the $N$-mover can make the move $(u,v)$, which shows that $f(4N)=\frac{1}{4}f(N)$. To prove that $f(2^kN)=2^{-k}f(N)$ for all $N$ and $k\geq0$ it now suffices to verify that $f(2N)=\frac{1}{2}f(N)$ for odd $N$.

If $N$ is odd and the $N$-mover can make the move $(u,v)$ then $$(u+v)^2+(u-v)^2=2u^2+2v^2=2N,$$ so the $2N$-mover can make the move $(u+v,u-v)$. Conversely, if the $2N$-mover can make the move $(r,s)$, then $$2N=r^2+s^2,$$ which implies that both $r$ and $s$ are odd, so in particular $\frac{r+s}{2}$ and $\frac{r-s}{2}$ are integers. Note that $$\left(\frac{r+s}{2}\right)^2+\left(\frac{r-s}{2}\right)^2=\frac{r^2+s^2}{2}=N,$$ so the $N$-mover can make the move $\left(\tfrac{r+s}{2},\tfrac{r-s}{2}\right)$. This yields a bijection between the points the $N$-mover can reach and the points the $2N$-mover can reach. It is in fact a linear transformation with determinant $-2$ and so $f(2N)=\frac{1}{2}f(N)$, as desired.

Primes $q\equiv3\pmod{4}$ allow a similar argument. If the $qN$-mover can make the move $(r,s)$ then $$qN=r^2+s^2,$$ and reducing mod $q$ shows that $r^2+s^2\equiv0\pmod{q}$. Because $q\equiv3\pmod{4}$ it follows that $r\equiv s\equiv0\pmod{q}$, say $r=qu$ and $s=qv$, and hence we have $$u^2+v^2=\frac{r^2+s^2}{q^2}=\frac{N}{q},$$ so in particular $q\mid N$. This shows that $f(qN)=0$ if $q\nmid N$. Of course, if the $\frac{N}{q}$-mover can make the move $(u,v)$ then the $qN$-mover can make the move $(qu,qv)=(r,s)$, which proves that $f(q^2N)=q^{-2}f(N)$, and hence also that $f(N)=0$ if the highest power of $q$ dividing $N$ is odd.

It remains to show that $f(N)=1$ for integers $N$ that are a product of primes congruent to $1\pmod{4}$. For this the following lemma is convenient:

Lemma: Let $a,b\in\Bbb{Z}$ with $a$ even and $b$ odd and let $d:=\gcd(a,b)$. If the $N$-mover can make the move $(a,b)$, then it can reach $(d,0)$.

Proof. Let $a':=\frac{a}{2}$ and $b':=\frac{b-1}{2}$. Then the $N$-mover can reach \begin{eqnarray*} a'(a,b)+a'(-a,b)&=&a'(0,2b)=(0,ab)\\ b'(b,a)+b'(-b,a)&=&b'(0,2a)=(0,a(b-1)), \end{eqnarray*} and hence also $(0,ab)-(0,a(b-1))=(0,a)$. By symmetry it can also reach $(a,0)$ and so it can reach $(a,0)+(-a,b)=(0,b)$ from which the conclusion follows.$\hspace{10pt}\square$

Let $N$ be a product of primes congruent to $1$ mod $4$ and let $p$ be a prime with $p\equiv1\pmod{4}$. Then $p=x^2+y^2$ for coprime integers $x$ and $y$. If the $N$-mover can make the move $(u,v)$ then $u^2+v^2=N\equiv1\pmod{4}$. Without loss of generality $x$ and $u$ are even and $y$ and $v$ are odd. Then $$pN=(x^2+y^2)(u^2+v^2)=(xu\pm yv)^2+(yu\mp xv)^2,$$ for both choices of opposite signs. Hence the $pN$-mover can make the moves $(xu\pm yv,yu\mp xv)$, where $xu\pm yv$ is odd and $yu\mp xv$ is even. Then by the lemma, the $pN$-mover can reach $(z_{\pm},0)$ where $z_{\pm}:=\gcd(xu\pm yv,yu\mp xv)$, and hence it can reach $(z,0)$ where $$z:=\gcd(z_+,z_-)=\gcd(xu+yv,yu-xv,xu-yv,yu+xv).$$ [Thanks to Ørjan Johansens comments:] Clearly $z$ is odd, and $z\mid2\gcd(u,v)$ because $$(xu+yv)+(xu-yv)=2xu \qquad\text{ and }\qquad (yu+xv)+(yu-xv)=2yu,$$ $$(xu+yv)-(xu-yv)=2yv \qquad\text{ and }\qquad (yu+xv)-(yu-xv)=2xv,$$ where $\gcd(x,y)=1$. It follows that $z\mid\gcd(u,v)$ and hence that the $pN$-mover can reach $(u,v)$. This shows that $f(pN)\geq f(N)$, and so by induction that $f(N)=1$ for every integer $N$ that is a product of primes congruent to $1$ mod $4$, completing the proof.