Question

Given two coprime integers $a < b$ of different parities, only a finite number of points in $\mathbb N^2$ cannot be reached by a walk in $\mathbb N^2$, starting at the origin and using only steps of the form $(b,\pm a),(\pm a,b)$ (and thus making an acute angle with the north-eastern vector $(1,1)$).

Is there a good upper bound on the number of such exceptional points? Is there a good upper bound on the coordinate sum $x+y$ of such an exceptional point $(x,y)$?

(Remark: A naive proof that almost all points can be reached gives an upper bound which is probably very far from the true value.)

Answer 1

I would like to see a solution. Below are a few comments which were obvious once I thought of them. I guess they do allow a naive argument that the number of exceptional points is finite, but I wonder if the OP has a nicer one.

I'll start with the (to me)

non-obvious observation: It appears that the exceptional points are all nicely contained in a non-convex quadrilateral with two sides on the axes (of course) and the other two lines of slopes $-b/a$ and $-a/b$. For example $a=4,b=7$ gives 2032 exceptional points. We can reach all points $(0,z)$ and $(z,0).$ for $z \ge 110$ as well as for for $42$ smaller values of $z$

0, 14, 28, 41, 42, 47, 49, 55, 56, 57, 61, 63, 65, 69, 70, 71, 74, 75, 77, 79, 80, 82, 83, 84, 85, 88, 89, 90, 91, 93, 94, 96, 97, 98, 99, 102, 103, 104, 105, 106, 107, 108

Hence there are 68 exceptional points on each axis.

The points $(3+4j,112-7j)$ and $(112-7j,3+4j)$ for $0 \le j \le 16$ are also exceptional and they lie on two lines which cross between $(43,44)$ and $(44,43)$. Here are the $\mathbf{2032}$ exceptional points:

more obvious observations

Recall that given positive co-prime integers $u \lt v$, the set $S=\{su+tv \mid s,t \ge 0\}$ contains exactly one member of each pair $\{m,uv-u-v+m\}$ so neither $uv-2u-v$ nor $uv-u-v$ is in $S$ but everything between them or larger is (because $0$ and $u$ are in $S$ but anything between them or smaller is not).

• Let the rank of point $(x,y)$ be $x+y$ so that there are $r+1$ points of rank $r$ in $\mathbb N^2.$ Then each move increases the rank by either $b+a$ or $b-a$. Hence half the ranks up to $(b+a)(b-a)-(b+a)-(b-a)=b^2-2b+a^2$ are completely empty. This allows some lower bound. Those comments stay true even if we are allowed to venture outside $\mathbb N^2$ and then come back in. So it might be worthwhile bounding the number of exceptional points in $\mathbb N^2$ under those relaxed rules (which allow us to reach the otherwise exceptional points such as $(b-a,b-a)$ ).

• Under the strict rules we may assume that we reach the non-exceptional points by first using only the two vectors $(a,b)$ and $(b,a)$ followed by later use of only $(-a,b)$ and $(b,-a).$

• Using just the vectors $(a,b)$ and $(b,a)$ gives only points which both have a rank $k(a+b)$ and are inside the cone $C$ between the lines $ax=by$ and $bx=ay.$ The first time that the entire rank is filled (using only those two vectors) is for $k_0=s+t$ obtained from the unique positive solution to $sa+tv=(a-1)(b-1)$. So $k_0 \le b-1-\frac {b-1}a.$

• Once we have a full rank between $(ka,kb)$ to $(kb,ka)$ for each $k \ge k_0$ (if not sooner) we can shift using the other two vectors to get full ranks from $(ka+jb,kb-ja)$ to $(kb-ja,ka+jb)$ (choosing ($1 \le j \le kb/a$). With a bit of work we could describe an $r_0$ so that we are sure to have every rank for $r \ge r_0$ full from $(r,0)$ to $(0,r).$