Take the 2-minute tour ×

Let $x$ be a real number and $N$ a positive integer. Define

$E(N,\delta) = \{(p,q) \in \mathbb{Z}^2: |p - q x| \leq \frac{\delta}{N}, |p|, |q| \leq N \}$,

i.e., the set of solutions to rational approximation of $x$ with accuracy $\frac{\delta}{N}$.

I am interested in the behavior of the cardinality of $E(N,\delta)$. Question:

For which $x$ do we have $|E(N,\delta)| \leq c(\delta) N$ where $c(\delta) \to 0$ as $\delta \to 0$?

Of course $x$ has to be irrational. Is this true for all irrational $x$? I am very unfamiliar with Diophantine approximation. I googled a bit and found that Schmidt proved that $|E(N,\delta)| = O(\log N)$ for a.e. $x$. Lang proved that this holds for all quadratic irrational $x$. But $O(\log N)$ is much stronger than what I asked, which is even weaker than $o(N)$.

(One further question: if we replace $\frac{1}{N}$ by $\frac{1}{N^{1+\epsilon}}$, how does the number of solutions behave?)

share|improve this question

1 Answer 1

up vote 1 down vote accepted

It's usually written $p-qx$. If $\delta\lt1/2$, then $|(p/q)-x|\le(1/2)q^{-2}$, which, if I remember right, implies, by a theorem of Hurwitz, that $p/q$ is a convergent to the continued fraction of $x$. It should not be hard to show that the number of convergents to $x$ with denominator not exceeding $N$ is little-oh of $N$.

share|improve this answer
Thanks Gerry! I have changed edited it accordingly. Can you elaborate a bit on your point or give a reference? I am not familiar with continued fraction and related things... And by Hurwitz's theorem do you mean this one: mathworld.wolfram.com/HurwitzsIrrationalNumberTheorem.html –  mr.gondolier Jan 8 '11 at 0:50
Cassels' book on Diophantine approximation has this stuff. –  Wadim Zudilin Jan 8 '11 at 1:02
Many thanks. Now I understood it. The result you mentioned is Theorem 19 of Khinchin. Given that, it remains to show that $q_k = \omega(k)$, where $q_k$ is the denominator of the $k$th convergent of $x$. But since $q_k = a_k q_{k-1} + q_{k-2}$ and $a_k$ is a positive integer, $q_k$ grows at least as Fibonacci, i.e., exponentially. Therefore number of solutions is $O(\log N)$ for all irrational $x$. –  mr.gondolier Jan 8 '11 at 4:56

Your Answer


