Continued Fractions and Diophantine Approximation

What is the most efficient way to approximate an irrational number, like $\pi$ or $\sqrt{2}$, using a simple fraction? While decimal expansions are familiar, they are often inefficient for finding the best rational approximations. This is where the elegant and powerful theory of continued fractions becomes indispensable, providing a systematic framework that lies at the heart of Diophantine approximation—the study of how closely irrational numbers can be approximated by rationals. This framework not only yields optimal approximations but also unlocks solutions to classical equations like Pell's equation and deepens our understanding of number theoretical constants.

Foundations: Continued Fraction Expansion

A (simple) continued fraction is an expression of the form:

$$a_0+\frac{1}{a_1+\frac{1}{a_2+\frac{1}{a_3+\ddots }}}$$

where $a_0$ is an integer and $a_1,a_2,a_3,\dots$ are positive integers. This is compactly denoted as $[a_0;a_1,a_2,a_3,\dots ]$. Every real number has a continued fraction expansion. For rational numbers, the expansion is finite. For irrational numbers, it is infinite and unique. The integers $a_i$ are called partial quotients, and they are generated by a simple iterative algorithm. Starting with a real number $x_0=x$, we set $a_0=\lfloor x_0\rfloor$ (the integer part). Then, for $i\ge 1$, we compute the reciprocal of the fractional part: $x_i=1/(x_{i-1}-a_{i-1})$, and set $a_i=\lfloor x_i\rfloor$. This process continues indefinitely for irrational $x$.

For example, the expansion for $\sqrt{2}$ begins: $\sqrt{2}=1+(\sqrt{2}-1)$. Since $\sqrt{2}-1\approx 0.414$, we compute $x_1=1/(\sqrt{2}-1)=\sqrt{2}+1\approx 2.414$. Thus, $a_0=1,a_1=2$. The process repeats, yielding the famous periodic expansion $\sqrt{2}=[1;2,2,2,\dots ]=[1;\overline{2}]$.

Convergents and Best Approximation

The true power of continued fractions emerges when we truncate the infinite expansion. The $n$-th convergent of the continued fraction is the finite fraction obtained by stopping at $a_n$: $C_n=[a_0;a_1,a_2,\dots ,a_n]$. These convergents $C_n=p_n/q_n$ provide a sequence of rational approximations to the original number $x$.

The numerators $p_n$ and denominators $q_n$ are efficiently computed via recurrence relations, crucial for both theory and computation: $$\begin{array}{rlrlrl}{p}_{-1}& =1,& p_0& =a_0,& p_n& =a_n{p}_{n-1}+p_{n-2},\\ q_{-1}& =0,& q_0& =1,& q_n& =a_n{q}_{n-1}+q_{n-2}.\end{array}$$ For $\sqrt{2}=[1;2,2,2,\dots ]$, this yields convergents: $C_0=1/1$, $C_1=3/2$, $C_2=7/5$, $C_3=17/12$, and so on.

The convergents are not just any approximations; they are best rational approximations in a very strong sense. For any convergent $p_n/q_n$, no rational number with a denominator smaller than $q_n$ is closer to $x$. Formally, if $|x-p/q|<|x-p_n/q_n|$, then necessarily $q>q_n$. Furthermore, convergents alternate between being under- and over-estimates, and they satisfy the elegant error bound: $$\left|x-\frac{p_n}{q_n}\right|<\frac{1}{q_n{q}_{n+1}}<\frac{1}{q_n^2}.$$ This inequality is the cornerstone of the connection to Diophantine approximation, demonstrating the exceptional accuracy of convergents.

Periodic Continued Fractions and Quadratic Irrationals

A fascinating and complete classification exists for a special class of irrationals. A quadratic irrational is an irrational number that is a root of a quadratic equation with integer coefficients, such as $\sqrt{d}$ or $(1+\sqrt{5})/2$. Lagrange proved that the continued fraction expansion of a real number is periodic (i.e., eventually repeats a block of partial quotients) if and only if it is a quadratic irrational.

The periodic structure is denoted as $[a_0;a_1,\dots ,a_m,\overline{b_1,\dots ,b_k}]$. This periodicity is not a curiosity; it provides an algorithmic way to work with these numbers. For instance, the golden ratio $\varphi =(1+\sqrt{5})/2$ has the simplest periodic expansion: $\varphi =[1;\overline{1}]$. Its convergents are ratios of successive Fibonacci numbers, which are the best approximations to $\varphi$.

Solving Pell's Equation via Continued Fractions

The periodicity of quadratic irrationals directly solves one of the oldest problems in number theory: Pell's equation, which has the form $x^2-d{y}^2=\pm 1$, where $d$ is a non-square positive integer. The fundamental solution $(x_1,y_1)$—the smallest positive integer solution—is found among the convergents of $\sqrt{d}$.

Specifically, let $\sqrt{d}=[a_0;\overline{a_1,a_2,\dots ,a_{l-1},2a_0}]$, where the period length is $l$. If $l$ is even, the convergents $p_{l-1}/q_{l-1}$ give the fundamental solution to $x^2-d{y}^2=-1$. The fundamental solution to $x^2-d{y}^2=+1$ is always given by $p_{l-1}/q_{l-1}$ if $l$ is odd, or by $p_{2l-1}/q_{2l-1}$ if $l$ is even. All other positive solutions are powers of this fundamental one.

For $d=2$, we have $\sqrt{2}=[1;\overline{2}]$, so $l=1$ (odd). The convergent $p_0/q_0=1/1$ solves $1^2-2\ast 1^2=-1$. The next convergent, $p_1/q_1=3/2$, solves $3^2-2\ast 2^2=+1$, giving the fundamental solution to the positive Pell equation. This method transforms an infinite search into a finite, algorithmic computation.

Badly Approximable Numbers and the Approximation Constant

Diophantine approximation seeks to understand how "well" a number can be approximated. The convergents show that for any irrational $x$, the inequality $|x-p/q|<1/q^2$ has infinitely many rational solutions $p/q$ (this is Dirichlet's approximation theorem). But some numbers resist even this level of approximation.

A real number $x$ is called badly approximable if there exists a constant $c(x)>0$ such that $|x-p/q|>c(x)/q^2$ for all rationals $p/q$. Which numbers have this property? The answer is beautifully tied to continued fractions: a number is badly approximable if and only if the sequence of its partial quotients $a_i$ is bounded. Numbers like the golden ratio $\varphi$ (all $a_i=1$) and $\sqrt{2}$ (all $a_i=2$) are classic examples.

The constant $c(x)$ is related to the largest partial quotient. This concept leads to the approximation constant $\mu (x)={\mathrm{liminf}}_{q\to \infty }q\cdot ||qx||$, where $||\cdot ||$ denotes distance to the nearest integer. For badly approximable numbers, $\mu (x)>0$. The study of these numbers and their approximation constants forms a rich area at the intersection of number theory and dynamical systems.

Common Pitfalls

1. Confusing finite and infinite expansions: It's crucial to remember that rational numbers have finite continued fraction expansions, while irrationals have infinite ones. When performing the expansion algorithm for a rational, the process terminates when you reach a fractional part of zero.
2. Misapplying the recurrence relations: A common error is to mis-index the recurrence formulas for $p_n$ and $q_n$. Always verify your base cases: $p_{-1}=1,q_{-1}=0,p_0=a_0,q_0=1$. For $n\ge 1$, the formula $p_n=a_n{p}_{n-1}+p_{n-2}$ depends on the previous two convergents, not just the last one.
3. Overlooking the alternating property: Convergents alternate between being less than and greater than the target irrational $x$. This property is vital for understanding why they are best approximations. Assuming all convergents are on one side of $x$ is a mistake.
4. Misidentifying the solution to Pell's equation: The fundamental solution is not simply the first convergent that yields a square difference of $\pm 1$. You must identify the period length $l$ of $\sqrt{d}$ and then correctly apply the rule based on whether $l$ is odd or even to find the minimal solution to $x^2-d{y}^2=+1$.

Summary

• Continued fractions $[a_0;a_1,a_2,\dots ]$ provide a unique and computationally useful representation for any real number, with the partial quotients $a_i$ generated by a recursive algorithm.
• The convergents $p_n/q_n$, computed via efficient recurrences, are best rational approximations. They satisfy the key error bound $|x-p_n/q_n|<1/q_n^2$, making them optimal for Diophantine approximation.
• An irrational number is a quadratic irrational if and only if its continued fraction expansion is periodic. This periodicity is algorithmically exploitable.
• The periodic expansion of $\sqrt{d}$ directly yields the fundamental solution to Pell's equation $x^2-d{y}^2=\pm 1$ from specific convergents.
• A number is badly approximable (resisting approximation better than $O(1/q^2)$) precisely when the sequence of its partial quotients is bounded. This defines a set of numbers with a positive approximation constant.