Pretty much the most interesting blog on the Internet.— Prof. Steven Landsburg

Once you get past the title, and the subtitle, and the equations, and the foreign quotes, and the computer code, and the various hapax legomena, a solid 50% English content!—The Proprietor

Wednesday, September 23, 2015

Continued Fractions Are Interesting

Farey Diagram

Continued fractions can be readily understood using only elementary mathematics, but they have many applications in solving problems in higher mathematics, such as Pell's equation. Yet, even many with more advanced mathematical training are only vaguely familiar with them.

A continued fraction is a number of the following form:

$$a_0+\frac{1}{a_1+\frac{1}{a_2+\ldots\frac{1}{a_n}}}$$

Each of the \(a_k\) is an integer and is called—for reasons that will become clear—a digit of the continued fraction. In order to avoid ever smaller and illegible font sizes, the same fraction is also often written in this form:

$$[a_0;a_1,a_2,\ldots,a_n]$$

Obviously, every integer \(a_0\) can be written as the continued fraction \([a_0]\). But so can every rational number (or fraction). For example:

$$\frac{11}{7}=1+\frac{1}{1+\frac{1}{1+\frac{1}{3}}}=[1,1,1,3]$$

This representation as a continued fraction is almost unique because:

$$\begin{aligned} a_0+\frac{1}{a_1+\ldots \frac{1}{a_{n-1}+\frac{1}{1}}} & = & a_0+\frac{1}{a_1+\ldots \frac{1}{a_{n-1}+1}} & \Rightarrow \\ [a_0;a_1,\ldots a_{n-1},1] & = & [a_0;a_1,\ldots, a_{n-1}+1] \end{aligned}$$

So, to use the above example:

$$[1,1,1,3]=\frac{11}{7}=1+\frac{1}{1+\frac{1}{1+\frac{1}{2+\frac{1}{1}}}}=[1,1,1,2,1]$$

If one requires that the final digit of the continued fraction not be one and that all but the first digit be strictly positive, the continued fraction representation is unique. Moreover, one notes that the continued fractions \([a_0;a_1,a_2,\ldots,a_n]\) and \([0;a_0,a_1,a_2,\ldots,a_n]\) are the reciprocals of each other when \(a_0>0\).

The use of digit for the \(a_k\) can be understood from parallel between the continued fraction representation and the decimal representation of a number:

To see the integral part of a number in decimal representation, one need only at the digits left of the period. Similarly, to see the integral part of a number in continued fraction representation one need only look at \(a_0\) for all of the \(a_1 \ldots a_n\) must contribute less than \(1\), but at least \(0\).The contribution will be exactly \(0\) if and only if there are no further continued fraction digits; if there is at least one more such digit, the contribution must be strictly larger than 0.

If one requires a more precise estimate of a number, one looks at further digits, in decimal just as in continued fraction representation. And in both representations, each digit is less significant (i.e., has a smaller effect on the number) than the one before it. If one only requires an estimate of the number, then one can always stop looking at the digits at some point, no matter how fine an estimate one requires.

In that sense the continued fraction representation is really just a superior version of the decimal representation which is tainted by the biological accident of using basis 10.It is an unfortunate accident. If one wanted the simplest basis, one would use binary, just as computers do (perhaps writing the numbers more compactly in equivalent octal or hexadecimal form). If one wanted a basis in which as many small fractions as possible terminate—a metric on which binary does admittedly badly—one would choose basis 6. In basis 6, 20% of all fraction with a reduced denominator of up to 100 terminate. In basis 10, only 15% do. Even if one insisted that ⅕ must terminate, as it does in basis 10, but not basis 6, basis 30 (readily writable by using letters as digits, hex-style) would serve better; in basis 30, 34% of such fractions terminate. And if one wished to transition to \(p\)-adic numbers, any prime basis would have been better. In short, there is no good reason to pick basis 10, except habit.

This analogy extends further. For example, if one wishes to obtain the best decimal approximation to a number with a fixed number of digits, one just chops off all digits in the decimal representation after that point (rounding, if necessary). Similarly, if one wishes to obtain the best rational approximation to a number with a denominator up to a given size, one just chops off the continued fraction at some point and computes it. The resulting ratios, called the continued fraction's convergents, are guaranteed to be better rational approximations to the number than any ratio with a smaller denominator.

Take, for example, the following continued fraction:

$$\pi = [3; 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 2, 1, 1, 2, 2, 2, 2, \ldots]$$

If one terminated this continued fraction representation at any point, one would obtain:

$$\begin{alignat*}{3} &{[}3] && = 3 & \approx \overline{3.}\strut{000000000000000}\\ &[3;7] && = \frac{22}{7} & \approx \overline{3.14}\strut{2857142857143}\\ &[3;7,15] && = \frac{333}{106} & \approx \overline{3.1415}\strut{09433962264}\\ &[3;7,15,1] && = \frac{355}{113} & \approx \overline{3.141592}\strut{920353983}\\ & && \ldots \\ &[3;7,15,1,292,\ldots] && = \pi & \approx \overline{3.141592653589793} \end{alignat*}$$

One immediately recognizes, for example, \(\frac{22}{7}\) or \(\frac{355}{113}\) as the commonly used and accurate rational approximations for \(\pi\).

An alert reader might object at this point that previously continued fraction representations were given only for rational numbers, which \(\pi\) is not. It is true that if one requires a continued fraction to terminate (i.e., have only a finite number of digits), then one can only represent rational numbers.

But there is no reason to require that a continued fraction only have a finite number of digits. Much as decimal representations with infinite digits (such as those of most fractions) are useful, so are infinite continued fraction representations of irrational numbers.In decimal representation, all fractions are either finite or periodic (i.e., the same list of digits repeats indefinitely). In continued fraction representation, all fractions terminate. Continued fraction representations of algebraics (i.e., the irrational roots of rational polynomial) are infinite, but periodic. Continued fraction representations of transcendentals (i.e., non-algebraic irrationals) are infinite and aperiodic, but may still exhibit predictable patterns. In both cases, each digit is well-defined and one can perform all sorts of useful, approximate arithmetic by only considering a finite number of them.