Question

Let $\alpha$ be an irrational number, $n\geq 1$ and

$ X_n=\lbrace (x,y) \in {\mathbb Z}^2 | |y| \leq n, \ x+y\alpha >0 \rbrace$

Now let $(x_n,y_n)$ minimize the quantity $x+y\alpha$ on $X_n$. This pair is unique because $\alpha$ is irrational. Now the problem is to deduce all the "location" of $\alpha$ from the three integers $n,x_n$ and $y_n$ only.

The two simplest cases are :

$x_n=0,y_n=1$. This is equivalent to $0 < \alpha < \frac{1}{n+1}$.

$x_n=1,y_n=-2$. This is equivalent to $\frac{1}{2}-\frac{1}{2m} < \alpha < \frac{1}{2}$ (where $m$ is the smallest odd integer $>n$).

More generally, it seems that for any triple $(n,x,y)$, the set $Y(n,x,y)$ of all irrationals $\alpha$ yielding $x_n=x,y_n=y$, is either empty or an interval $[A(n,x,y),B(n,x,y)] \setminus {\mathbb Q}$. Is that true, and are there recursive formulas to compute $A(n,x,y)$ and $B(n,x,y)$ ?

This problem is certainly related to continued fractions and best approximations in the usual sense, but I don't see how to make the connection effective.

Answer 1

The dots $\{ x+ y \alpha \colon |y|\leq n \}$ move continuously with $\alpha$, so we should consider when $x_n+y_n \alpha$ can stop being the smallest positive dot. First, note that $y_n = 0$ is impossible. We need $x_n+y_n \alpha > 0$, so that $\alpha > - x_n/y_n$ if $y > 0$ and $\alpha < -x_n /y_n$ if $y_n < 0$. At the other extreme, $x_n+y_n\alpha$ can lose its crown if two of the dots are equal $x_n+y_n \alpha = x' + y' \alpha$, i.e., if $\alpha$ is fraction with denominator at most $n-1$. Note that the minimizer really does change when we get equality since the slopes are different.

So, for $y_n > 0$, you get $A(n,x_n,y_n) = -x_n / y_n$ and $B(n,x_n,y_n)$ is the smallest fraction that is both larger than $-x_n/y_n$ and has a denominator less than $n$. If $y_n < 0$, then $B(n,x_n,y_n)= -x_n/y_n$ and $A(n,x_n,y_n)$ is the largest fraction that is both smaller than $-x_n/y_n$ and has denominator less than $n$.

Example: say $n=102, x_n=52, y_n = 37$. This happens if and only if $\alpha$ is in the interval $(-52/37, a/b)$, where $a/b$ is only slightly larger than -52/37 and $0 < b < 102$. To find $a,b$, we first translate -52/37 so that it lies in (0,1): it translates to 22/37. Now from the theory of Farey fractions, we know that the fraction after 22/37 (call it $c/d$) in $F_{101}$ satisfies $22d-37c=\pm 1$, and also $37+d > 101$. Solving this modulo 101 (cleverly chosen to be prime, so that the solutions are unique) gives $c/d=41/69$ or $c/d=82/69$ (which is clearly wrong, since $c/d<1$). Translating back gives $a/b=41/69-2=-97/69$. So the final conclusion is that $\alpha$ is in $(-52/37,-97/69)$.