By infmagic2047

2019-02-11 04:25:50 8 Comments

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.

Related Questions

Sponsored Content

0 Answered Questions

Number of spaces a knight may reach within $n$ moves (chess)

2 Answered Questions

[SOLVED] Number of ways to go from $d_1$ to $d_8$ using only 7 King moves

  • 2018-10-30 18:20:35
  • Karan Abrol
  • 36 View
  • 1 Score
  • 2 Answer
  • Tags:   combinatorics

2 Answered Questions

[SOLVED] King and knight moving on an infinite chess board

1 Answered Questions

[SOLVED] Number of ways for a knight to move to a certain square on a chessboard

  • 2017-07-25 03:37:22
  • Elk Chu
  • 142 View
  • 2 Score
  • 1 Answer
  • Tags:   combinatorics

1 Answered Questions

[SOLVED] Three knights on a 3x3 chess board

1 Answered Questions

[SOLVED] minimum number of steps for knight in chess

  • 2015-02-05 23:45:24
  • user157835
  • 4359 View
  • 7 Score
  • 1 Answer
  • Tags:   combinatorics

1 Answered Questions

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

  • 2015-01-11 10:15:59
  • Deddy
  • 146 View
  • 2 Score
  • 1 Answer
  • Tags:   combinatorics

1 Answered Questions

3 Answered Questions

[SOLVED] Knight move variant: Can it move from $A$ to $B$

1 Answered Questions

[SOLVED] Sliding blocks puzzle

Sponsored Content