23
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Quick comment: I think your conjecture is correct! $\endgroup$ – Greg Martin Feb 11 at 4:44
12
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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$. $\endgroup$ – Empy2 Feb 11 at 14:32
  • 1
    $\begingroup$ 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)$, $\endgroup$ – Hagen von Eitzen Feb 11 at 23:46
  • 1
    $\begingroup$ The gap is not always correct, e.g. if p=N, x=u, y=v. $\endgroup$ – Ørjan Johansen Feb 12 at 5:12
  • 2
    $\begingroup$ 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)$. $\endgroup$ – Ørjan Johansen Feb 12 at 7:28
  • 1
    $\begingroup$ 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$. $\endgroup$ – Ørjan Johansen Feb 12 at 18:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.