MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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$". – Kevin O'Bryant Mar 20 '11 at 13:36
@Kevin : corrected, thanks. – Ewan Delanoy Mar 20 '11 at 13:43
up vote 3 down vote accepted

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

share|cite|improve this answer
Thanks Kevin! Nice solution. – Ewan Delanoy Mar 20 '11 at 15:37
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$. – Kevin O'Bryant Mar 20 '11 at 20:11

Your Answer


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.