One of the remarkable abilities of the simple continued fraction expansion is to provide us with the “best” rational approximations for any given number. Lets try to understand what this statement means.
Good rational approximations
There are many rational numbers, and they are distributed quite nicely along the real line. In particular, given any real number \(\alpha \in \mathbb{R}\) and any error margin \( \varepsilon >0\), we can always find a rational number which is \( \varepsilon \) close to \( \alpha \), or more recisely
\( |\alpha – \frac{p}{q}| < \varepsilon \).
As \(\varepsilon>0\) becomes smaller, the denominator \(q\) will become larger and larger (and the numerator as well, since \(p\sim q\cdot\alpha\)). But, can we find better and better approximations without increasing the denominator too much?
If we fix some denominator \(q>0\), we can always find a numerator \(p\) such that
\( |\alpha – \frac{p}{q}| < \frac{1}{|q|} \),
or alternatively for an error \(\varepsilon>0\), we can find an approximation with denominator at most \(\frac{1}{\varepsilon}\).
A remarkable and elementary result in Diophantine approximations, called Dirichlet’s theorem, states that we can actually do much better. By selecting \(q\) intelligently (and it can be as large as we want), there is a corresponding \(p\) such that
\( |\alpha – \frac{p}{q}| < \frac{1}{q^2} \).
Hence, we improved from linear to a quadratic error (in \(\frac{1}{q}\)). In general, this bound cannot be improved, and it depends on the number \(\alpha\). However, what we want to know is what happens when \(\alpha\) is rational.
Approximating rational numbers
When \(\alpha\) is rational, Dirichlet’s theorem is trivial. Indeed, letting \(\alpha = \frac{n}{m}\) we can always take the approximation \(\frac{kn}{km} \) with denominator as large as we want, and get
\(|\alpha-\frac{kn}{km}|=0<\frac{1}{km}.\)
Of course, this is a bit of cheating… All the rational approximations are the same! What happens if we also require the approximations to be distinct, or alternatively always write them in their reduced form (with denominator still goes to infinity)? This means that the difference above will be strictly positive for almost all the approximations, and therefore
\(|\alpha – \frac{p}{q}|=|\frac{n}{m} – \frac{p}{q}| = \frac{|nq-mp|}{|mq|}\geq \frac{1}{|m|}\cdot \frac{1}{|q|}\).
Hence, up to the constant \(\frac{1}{|m|}\) , the error is bounded from below by \(\frac{1}{|q|}\) ! Dirichlet’s theorem still works for irrational numbers, leading us to the following result:
Irrationality testing:
For \(\alpha\) irrational, there are rational approximations \(\frac{p_k}{q_k}\) in reduced form, with \(q_k\to \infty\) such that
\(|\alpha – \frac{p_k}{q_k}| < \frac{1}{q_k^2}\) .
For \(\alpha\) rational, there is a positive constant \(C:=C(\alpha)>0\) such that for any rational approximation \(\frac{p}{q}\neq \alpha\) in reduced form we have
\(|\alpha – \frac{p}{q}| \geq \frac{C}{|q|}\).
In particular, to show that \(\alpha\) is irrational, it is enough to find a sequence \(p_k,q_k\) of coprime integers which go to infinity such that
\(\displaystyle{\lim_{k\to \infty}}|\alpha q_k – p_k | = 0\)
Why continued fractions?
As mentioned in the beginning, the simple continued fraction provides in a sense the best rational approximations. More precisely, given an expansion
\(\alpha = \frac{1}{a_1 + \frac{1}{a_2 + \frac{1}{a_3 + \frac{1}{a_4 + \frac{1}{a_5 + \ddots}}}}}\),
we call the finite expansion up to the \(n\)-term the \(n\)-th convergent of \(\alpha\), namely
\(\frac{p_n}{q_n} = \frac{1}{a_1 + \frac{1}{a_2 + \frac{1}{a_3 + \frac{1}{a_4 + \frac{1}{\ddots+\frac{1}{a_n}}}}}}\).
These convergents (in their reduced form) satisfy the condition in Dirichlet’s theorem, namely
\(|\alpha – \frac{p_n}{q_n}|<\frac{1}{q_n^2}\).
We already saw that for rational numbers, the expansion stops after finitely many steps, giving us only finitely many convergents above, hence using our irrationality testing method from above and this fact, we already get that :
Corollary: A number is irrational if and only if its simple continued fraction is infinite.
These convergent are also the best rational approximations in the sense that if \(q\leq q_n\), then for any \(p\) we have
\( |q_n \alpha – p_n | \leq |q \alpha – p| \)
and in particular
\( |\alpha – \frac{p_n}{q_n} | \leq |\alpha – \frac{p}{q}| \).
These are very powerful results, however to actually find the convergent we need to run the Euclidean division algorithm for infinitely many steps in order to find the infinitely many convergents, leading us to the following question:
Question: Can we use polynomial continued fractions to prove irrationality?
While the “convergents” for the polynomial continued fractions are not the best, and in general not even a solution to Dirichlet’s inequality above, they are however much easier to compute, because we only need their defining polynomials. Can we construct good enough polynomials, so on the one hand they are easy to work with, and on the other good enough to show irrationality?
This is one of the main questions that we try to answer in this research.