[SOLVED] 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.

@Servaes 2019-02-11 12:01:24

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.

@Empy2 2019-02-11 14:32:00

Nice explanation. But in the final case, $f(65)=1$ because $4(1,8)+4(1,-8)-(8,-1)=(0,1)$. I think $f(pN)=f(N)$ when $p=1\pmod4$.

@Servaes 2019-02-11 23:36:44

@Empy2 You are right. I had another look at the argument, and changed it up a bit. It is still incomplete; I am missing a small intermediate step that might turn out to be problematic, and the case of multiplying by a prime $p\equiv3\pmod{4}$. Perhaps I will continue this tomorrow.

@Hagen von Eitzen 2019-02-11 23:46:04

If $p\equiv 3\pmod 4$ and $p$ divides $N$ to an odd power, then clearly $f(N)=0$. On the other hand, $f(p^2N)=\frac1{p^2}f(N)$,

@Servaes 2019-02-11 23:47:54

@HagenvonEitzen The former statement is indeed clear, in the latter statement only the inequality '$\geq$' is immediately clear to me, but I haven't given it any thought yet and it is time for bed here :)

@Ørjan Johansen 2019-02-12 05:12:33

The gap is not always correct, e.g. if p=N, x=u, y=v.

@Ørjan Johansen 2019-02-12 07:28:40

However, you can also construct the alternative $z' := \gcd(xu-yv,yu+xv)$, and that together with $z$ and the fact they are odd gives you $\gcd(z,z') | \gcd(xu,yv,yu,xv) | \gcd(u,v)$.

@Servaes 2019-02-12 13:25:49

@ØrjanJohansen Thank you for that observation, and the smooth fix! I have incorporated it into my answer, which is now finally a complete proof :)

@infmagic2047 2019-02-12 13:40:12

I think the base cases for 2 and q=4k+3 should be f(2N) and f(qN) for appropriate choices of N respectively. Otherwise, this is a very good answer!

@Servaes 2019-02-12 13:59:34

Thank you. I have added a proof that $f(2N)=2^{-1}f(N)$. Perhaps I will add a bit for $f(qN)$ later.

@Ørjan Johansen 2019-02-12 18:04:23

The missing $f(qN)$ case @infmagic2047 points out can be absorbed into the $f(q^2N)$ case by noting that $qN=r^2+s^2$ already implies $r\equiv s\equiv 0\pmod q$ and therefore that $q|N$.

@Ørjan Johansen 2019-02-12 18:19:15

Given $z\mid2\gcd(u,v)$, the claim $z\mid p\gcd(u,v)$ is now redundant, you only need that $z$ is odd.

@Ørjan Johansen 2019-02-13 00:32:27

Now the $3\pmod 4$ part is confusing $qN$ with $q^2N$. Maybe use $qN'$ and $N=N'/q$ when $q\mid N'$?

@Servaes 2019-02-13 09:49:51

@ØrjanJohansen You are right, I mixed up two different approaches. I shouldn't try to improve an answer at such an hour ;) It should be clear and correct now.

[SOLVED] minimum number of steps for knight in chess

• 2015-02-05 23:45:24
• user157835
• 4617 View
• 7 Score
• Tags:   combinatorics

[SOLVED] The track of the chess knight at $n\times n$ board

• 2015-01-11 10:15:59
• Deddy
• 151 View
• 2 Score