2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ You wrote "from the two integers $x_n$ and $y_n$ only", but I think from your examples that you meant "from the three integers $n,x_n,y_n$". $\endgroup$ Mar 20, 2011 at 13:36

1 Answer 1

3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Excuse me, 101 being prime has nothing whatsoever to do with the uniqueness. For each n and 0<a/b<1, there is a unique c/d satisfying $ad-bc=\pm 1$, $b+d > n$, $0 < c\leq d$. $\endgroup$ Mar 20, 2011 at 20:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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