Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

 
discard

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.