Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.)

share|improve this question
    
Using the theory developed by the Frobenius problem (postage stamp problem) and considering how far the points are from the line x=-y, I expect a bound of O((a+b)^2). Gerhard "Ask Me About System Design" Paseman, 2012.02.22 –  Gerhard Paseman Feb 22 '12 at 16:19
    
A bound of the form $O((a+b)^2)$ (for the number of points) is far too optimistic, I believe. –  Roland Bacher Feb 22 '12 at 18:10
    
I was thinking of distance from the origin. For number of points, replace the exponent 2 by 4 for my expectations. Gerhard "Ask Me About System Design" Paseman, 2012.02.22 –  Gerhard Paseman Feb 22 '12 at 19:25
1  
Do you know the answers for any particular examples? Say, $a=1$, $b=2$? –  Gerry Myerson Feb 22 '12 at 22:49
1  
Could you perhaps include the naive bound. –  quid Feb 22 '12 at 23:02
show 1 more comment

1 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:

alt text

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).$

share|improve this answer
    
Beautiful patterns in that plot of the nonexceptional points! –  Joseph O'Rourke Feb 25 '12 at 15:05
    
thanks. That plot is actually the exceptional points. If one starts from any exceptional point and goes backwards in $\mathbb N^2$ using $(\pm a,-b)$ and $(-b, \pm a)$ then one only sees exceptional points. I wonder what the minimal exceptional starting set is. There might be some nice duality as with the set $S$ in $\mathbb N$ –  Aaron Meyerowitz Feb 25 '12 at 16:45
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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