Two Examples

Now let me show you something about the continued fraction expansion of π. (Careful, the expansion in [Hua] contains several mistakes.)

[3,7,15,1,292,1,1,1,2,1,3,1,14, … ]

Here are the first few convergents.

		3	7	15	1	292
0	1	3	22	333	355	103993
1	0	1	7	106	113	33102

At the end, the large coefficient 292 makes the numerator and denominator jump way up, and that makes it seem like 355/113 must be an exceptionally good approximation. And sure enough, it is! The difference |π − 355/113| is only about 3×10⁻⁷. And what quality does that correspond to? Well, let's see … we just multiply by 113², take the reciprocal, and voilà … 293.57 and a bit?!

That can't be a coincidence, and it isn't. Part of the explanation is that the fundamental result is exceptionally slack. In the derivation, we used the fact that q_n+1 > q_n, but a better fact is right there in the definition of q_n+1:

qn+1	=	an+1qn + qn−1
	>	an+1qn,

with equality when n = 0. When we plug that into the derivation, naturally we get a better result:

|x − p_n/q_n| < 1/a_n+1q_n²,

or equivalently

Q_n > a_n+1,

with equality in both of the equations when n = 0 and n_max = 1.

That better result is another one of my contributions. We'll have even better results in a moment, but it's also nice to have a result that's easy to understand.

Anyway, now we know why the quality is greater than 292, but why is it only slightly greater? That's what the other part of the explanation needs to, uh, explain. I had no idea, and I didn't see anything in [Hua] or [CF], but I did find a couple of clues in [MC]. The first clue suggested that

Q_n < a_n+1 + 2,

which seemed mysterious and unlikely but turned out to be entirely true. The second clue suggested an exact equation for the value of Q_n, which seemed promising but turned out to be wrong in the fifth decimal place in the current case and more obviously wrong in other cases. Once I knew what I was looking for, though, I was able to find the correct exact equation in [Hua] after all. It was just a few lines of algebra in another proof, not even presented as a result!

Qn	=		[an+1, an+2, an+3, … ]
		+	[0, an, an−1, an−2, … , a3, a2, a1]

Just so everything is perfectly clear, here's how to construct the equation for Q_n: cut the continued fraction expansion after a_n, fold the front half around underneath, add 0 on the left, and remove a₀ on the right. The equation in [MC] just left out that last step. And, technically, it's not wrong. In context, the equation is only considered in the limit as n goes to infinity, and in that limit, the contribution of a₀ goes to zero. Still, why wouldn't one use the correct equation?

Reverse digression! Every irrational number has a unique continued fraction expansion, but every rational number has two, the proper one (my terminology) produced by the first algorithm and the improper one produced by replacing the final coefficient “a” with “a−1,1”. How can you tell whether an expansion is improper? The only proper expansion that ends in 1 is [1]. Now, normally we have

a₀ ≤ x < a₀ + 1

with no caveats, but if we consider improper expansions, then we get equality on the right when the expansion is [a₀,1]. (The same expansion also causes equality in the fundamental result. Also, for completeness, note that the expansion [a₀,1,1] has two consecutive convergents with Q = 2.)

Now let's apply that result to the two terms in the equation for Q_n.

a_n+1 = a_n+1 + 0 ≤ Q_n < (a_n+1 + 1) + (0 + 1) = a_n+1 + 2

The second term in Q_n is produced in an unusual way, so we do need to consider improper expansions, but not for long. If the original expansion is proper, then so is the first term, therefore the inequality is strict. For the record, though, we get equality on the right when n = 1 and the original expansion is [a₀,1,a₂,1].

Note to myself and others: if you're tempted to require that a₀ ≥ 0, remember there's some tension with the fact that the improper form of [0] is [−1,1].

So, now we know all about why the quality of 355/113 has the value that it does.

Q3	=		[292,1,1,1,2,1,3,1,14, … ]
		+	[0,1,15,7]

The second term is 106/113. The first term is harder to evaluate, but the same number shows up during the execution of the first algorithm, so we can get the exact value by doing the calculation symbolically up to that point. Then, when we add the terms together, an amazing cancellation occurs!

Q3	= (106π − 333)/(355 − 113π) + 106/113
	= 1/113(355 − 113π)
	= 1/1132|π − 355/113|

That's just the definition of approximation quality, of course. So, that was fun, but the original expression was better because we could see at a glance that the value was just over 292.

Next let's look at the continued fraction expansion of the golden mean (R+1)/2. The first algorithm repeats immediately, …

	ai	rest
(R+1)/2	1	(R−1)/2
(R+1)/2	1	(R−1)/2

… so the expansion is simply [1,1,1, … ]. However, we're going to be seeing a lot of repeating expansions soon, so let's use the same convention for continued fraction expansions as for decimal expansions and draw a line under the repeating part. Then we can say that the expansion is simply [1]!

The convergents are quotients of consecutive Fibonacci numbers. (See On Rectangular Tilings, about halfway down, for a nice formula for Fibonacci numbers in terms of R.)

		1	1	1	1	1	1	1	1
0	1	1	2	3	5	8	13	21	34
1	0	1	1	2	3	5	8	13	21

What about the approximation quality? In the equation for Q_n, the first term is always [1], while the second contains zero followed by a string of n 1s, so in the limit as n goes to infinity, the quality converges to

[1] + [0,1] = (R+1)/2 + (R−1)/2 = R.

Now we can return to that held thought.

When x is irrational, there are an infinite number of fractions p/q with Q > R.

That's true for R, but it's not true for any larger number, because for the golden mean there would only be a finite number of suitable fractions.

That sounds so plausible, but I left out an important detail. So far, all we know is that there would only be a finite number of suitable convergents. Could there also be an infinite number of suitable fractions that aren't convergents? It turns out there can't, because of the following surprising result from [Hua]: if a fraction has Q > 2, then it has to appear as a convergent! In other words, the continued fraction expansion of x has to start with either the proper or the improper expansion of p/q.

The condition Q > 2 is sufficient for a fraction to be a convergent, but it's not necessary—convergents can approach arbitrarily close to Q = 1, or even reach it if the expansion is [a₀,1]. Are there any necessary and sufficient conditions? Yes. There's one in [Hua] that I'll skip because it's technical and hard to remember, and there's one in [CF] that I'll tell you about because it's nice. Ironically, it also shows up as an intermediate step in [Hua]. Given a fraction, write down the proper and improper forms and add 1 to the final coefficients. The fraction is a convergent of precisely the numbers between those endpoints. For example, 1/3 is a convergent of the numbers between 1/4 and 2/5.

1/4	[0,4]
1/3	[0,3]
1/3	[0,2,1]
2/5	[0,2,2]

Whether the endpoints are included or excluded is a matter of taste, because the fraction is only a convergent of the improper forms of the endpoints.