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


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

  • $\begingroup$ 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 $\endgroup$ – gondolier Jan 8 '11 at 0:50
  • $\begingroup$ Cassels' book on Diophantine approximation has this stuff. $\endgroup$ – Wadim Zudilin Jan 8 '11 at 1:02
  • $\begingroup$ 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$. $\endgroup$ – gondolier Jan 8 '11 at 4:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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