Continued fractions

Irrational numbers are typically defined upon constructing the set $\mathbb{R}$ of real numbers from the set $\mathbb{Q}$ of rational numbers via either Cauchy sequences or Dedekind cuts. Decimal expansion has been used as the standard way of representing and approximating irrational numbers. However, it turns out that the best way to approximate irrational numbers is through continued fractions.

Continued Fractions

A continued fraction expansion of a real number $\theta$ is of the form:

for some positive integers $a_0, a_1, \ldots$. We can obtain the continued fraction expression for any $\theta \in \mathbb{R}$ through the following algorithm.

• Set $a_0 = \lfloor \theta \rfloor$, the highest integer less or equal to $\theta$, and $b_0 = {\theta} := \theta - a_0$, the fractional part of $\theta$;
• Inductively, for all $n \in \mathbb{N}$, $a_n = \lfloor \frac{1}{b_{n-1}} \rfloor$ and $b_n = { \frac{1}{b_{n-1}} }$.

If we ever obtain $b_k = 0$ for some $k \in \mathbb{N}$, then $\theta$ has a finite continued fraction expansion $[a_0; a_1, \ldots a_k]$. By the Euclidean algorithm, this happens precisely when $\theta$ is rational. In the rational case, the expansion is not unique because of the following identity:

Every irrational number has an infinite continued fraction expansion uniquely determined by the algorithm. An obvious way of approximating $\theta =[a_0;a_1,a_2,\ldots]$ is by truncating the expansion to obtain rational numbers $\frac{p_n}{q_n} = [a_0; a_1, \ldots a_n]$ where $p_n$ and $q_n$ are coprime integers and $q_n$ is always positive. By straightforward induction, $p_n$ and $q_n$ are determined by the following recurrence relation:

with initial values $q_{-1} = 0, p_{-1} = q_{0} = 1, p_0 = a_0$. Let’s assume without any harm that $a_0=0$. The recurrence relation be rewritten in terms of matrices:

Let’s call the matrix above by $A_n$.

Proposition: The rational numbers $\frac{p_n}{q_n}$ satisfy the following properties:

1. $\frac{p_{n+1}}{q_{n+1}} = \frac{p_n}{q_n} + \frac{(-1)^n}{q_n q_{n+1}}$;
2. $ \theta = a_0 + \sum_{n=0}^\infty \frac{(-1)^n}{q_n q_{n+1}}$.

Property 1 again follows from computing the determinant of $A_n$. Property 2 follows directly from the first. Observe that $\frac{p_n}{q_n}$ for odd $n$ must be a decreasing sequence of rational numbers greater than $\theta$, whereas $\frac{p_n}{q_n}$ for even $n$ must be an increasing sequence of rational numbers smaller than $\theta$:

It turns out that the rational numbers $\frac{p_n}{q_n}$ are best rational approximations (often also called best Diophantine approximations) of $\theta$ in the sense that for any rational number $\frac{p}{q}$, if $q_n \geq q$, then $\vert \theta - \frac{p_n}{q_n} \vert \leq \vert \theta - \frac{p}{q} \vert$. In fact, they satisfy an even stronger inequality.

Theorem: For any rational number $\frac{p}{q}$, if $q_n \geq q$, then $\vert q_n\theta - p_n \vert \leq \vert q\theta - p \vert$.

By triangle inequality, property 2 also yields the following estimate

which immediately implies the inequality $\vert q_n \theta - p_n \vert < \vert q_{n-1} \theta - p_{n-1} \vert$. By induction, it is sufficient to show the theorem under the additional assumption that $q_{n-1} < q \leq q_n$, $\text{hcf}(p,q)=1$, and $\frac{p}{q} \neq \frac{p_n}{q_n}$.

If $q = q_n$, then since $\vert q_n\theta - p_n \vert < \frac{1}{q_{n+1}} < \frac{1}{2} $,

Suppose $q_{n-1} < q < q_n$. By property 1, the simultaneous equations

have a unique non-zero integral solution

Since $ q_{n-1} < a q_n + b q_{n-1} <q_n$, $a$ and $b$ must have opposite signs, so $a(q_n \theta - p_n)$ and $b(q_{n-1} \theta - p_{n-1})$ have the same sign. Therefore, we have our desired inequality:

Preperiodic Continued Fractions

An infinite continued fraction $\theta = [a_0; a_1, a_2, \ldots]$ is preperiodic if there are some $N,s \in \mathbb{N}$ such that $a_{n} = a_{n+s}$ whenever $n \geq N$. The minimum of such $s$ is called the period and the minimum of such $N$ is called the preperiod. Real numbers with preperiodic decimal expansion are precisely rational numbers, but the decimal expansion of irrationals follows no clear pattern. Analogously, we have the following theorem by Lagrange.

Theorem: The continued fraction expansion of an irrational number $\theta$ is preperiodic if and only if $\theta$ is a quadratic irrational, i.e. can be written in the form of $\frac{a + b\sqrt{c}}{d}$ for some $a,b,c,d \in \mathbb{Z}$ where $c$ is square-free.

The proof is slightly more involved and can be found in the book of Hardy and Wright¹. Here is the continued fraction expansion of some of your favorite quadratic irrationals:

• $\frac{1+\sqrt{5}}{2} = [1;1,1,1,\ldots]$ (the golden ratio)
• $\sqrt{2} = [1;2,2,2,\ldots]$
• $\frac{\sqrt{3}}{2} = [0;1,6,2,6,2,6,2 \ldots]$

In comparison, the continued fraction expansion of the following irrationals are not preperiodic:

• $e = [2;1,2,1,1,4,1,1,6,1,1,8,1,1,10,\ldots]$
• $\pi = [3;7,15,1,292,1,1,2, \ldots]$

Let’s assume again that $a_0 = 0$. By induction, we can show that the matrix $A_n$ and the numbers $\theta_n = [0;a_n,a_{n+1},\ldots]$ satisfy the following equation:

In the first coordinate, we have the identity

Suppose the continued fraction expansion of $\theta$ is preperiodic with period $s$ and preperiod $N$. When $n \geq N$, $\theta_n = \theta_{n+s}$. As such, the fractional parts $\vert q_n \theta - p_n \vert$ would converge to zero at a fixed rate.

Proposition: Let $\theta = [a_0;a_1,a_2,\ldots]$ be preperiodic of period $s$ and preperiod $N$. Let $\frac{p_n}{q_n}$ be the $n$-th convergent of $\theta$ and let $r = \prod_{k=N+1}^{N+s} \theta_k$ where $\theta_n = [0;a_n,a_{n+1},\ldots]$. For all $n \geq N$, $\vert q_{n+s} \theta - p_{n+s} \vert = r \vert q_n \theta - p_n \vert$.

In particular, when the period is $s=1$, the fractional parts $\vert q_n \theta - p_n \vert $ eventually form a geometric sequence.

References

1: G. H. Hardy and E. M. Wright. An Introduction to the Theory of Numbers. Oxford University Press, 1979.