TITLE: How fast do the denominators in Dirichlets approximation for irrationals grow?
QUESTION [4 upvotes]: For any irrations $a$, there are infinitely many $p,q$ in $N$ such that $|a-\frac{p}{q}|<\frac{1}{q^2}$, how fast do those $q$ grow? 
What I mean is if we take the series of $q$ that satisfy the above (there exist p so that...) how fast does the sequence $q_1,q_2..$ grow? I'd like an upper bound.

REPLY [1 votes]: This sequence grows at least exponentially, but in general there is no upper bound.
Let's assume for simplicity that $a\geq 0$. It is well known that any such number has a continued fraction expansion $a=[a_0;a_1,a_2,a_3,...]$ where $a_0\geq 0, a_i>0 \forall i>0$ are integers, and on the other hand, any such sequence of integers $a_i$ define a continued fraction which is a nonnegative real number. The convergents that you're looking at, i.e. the rationals $\frac{p_n}{q_n}$ that give the approximation $|a-\frac {p_n}{q_n}|<\frac{1}{q_n^2}$ satisfy the recursion formulas
$$p_{n+1}=a_{n+1}p_n+p_{n-1} \\
q_{n+1}=a_{n+1}q_n+q_{n-1}
$$
where $p_{-1}=1,q_{-1}=0,p_0=a_0,q_0=1$. It is now easy to show with induction that $q_n\geq 2^{(n-2)/2}$ for $n\geq 0$. If you also know that the $a_i<M$ for all i, then you can also show that $q_n\leq M^n$. The problem is that the set of numbers which have continued fractions with bounded $a_i$ are of measure zero. There are still many such numbers, for example if $f(x)$ is a quadratic polynomial with integer coefficients with an irrational root $a$, then the expansion of $a$ is eventually periodic, so in particular it is bounded.
If you take an arbitrary sequence $a_i$, then of course you can make the sequence $q_n$ grow as fast as you want, so you cannot give a unified bounding function for all of the irrational numbers simultaneously.
{"set_name": "stack_exchange", "score": 4, "question_id": 1990457}