Approximation Quality

What were my sources? The basic framework came from this old favorite, which has a chapter about continued fractions.

[Hua] Introduction to Number Theory

I reviewed the following two Wikipedia articles to make sure I hadn't missed any major points.

[CF] Continued fraction
[MC] Markov constant

In the process, I found some fun minor points that I wanted to add; I'll be sure to give credit to the appropriate article when the time comes. There are also a few other articles that are relevant, but I'll just link to them directly.

I also added a few missing pieces that must be so obvious to people who think seriously about these things that they never even bother to mention them. Naturally I'll be sure to give myself credit when the time comes.

Now let's get started! The first thing we need to do is set up some better notation than in the essay Continued Fractions. Given a number x, we can run the first algorithm to obtain the continued fraction expansion, as before, …

[a₀, a₁, a₂, a₃, … ]

… and then we can run the second algorithm to obtain the convergents p_n/q_n.

		a0	a1	a2	a3	…
p−2 = 0	p−1 = 1	p0	p1	p2	p3	…
q−2 = 1	q−1 = 0	q0	q1	q2	q3	…

Last time, I used that YXZ schema to explain how to fill in the table, but now we can just write down the actual definitions.

p_n+1 = a_n+1p_n + p_n−1
q_n+1 = a_n+1q_n + q_n−1

One point I haven't mentioned yet is that the convergents alternate—the even-numbered ones approach x from below while the odd-numbered ones approach x from above. Even the initial values follow the same pattern, more or less: p₋₂/q₋₂ is zero, which is below x in the normal case when x is positive, and of course p₋₁/q₋₁ is infinite. We still don't consider those values to be convergents, though.

For some reason, the theory of continued fractions is full of inequalities that are almost strict. For example, we have q_n+1 > q_n, with equality when n = 0 and a₁ = 1. The other caveat that I'm generally not even going to mention is that the subscripts have to be in range. In the example, that means n ≥ 0, and also n+1 ≤ n_max if the expansion terminates (i.e., if x is rational).

Next, let's derive a result that's fundamental not because it's strong but because it's the theme on which we'll construct many variations. The starting point is an identity that's easy to prove using induction and the definitions of p_n+1 and q_n+1. It holds all the way down to n = −2.

p_n+1q_n − p_nq_n+1 = (−1)ⁿ

If you like, you can think of the identity in terms of 2×2 matrices. The left-hand side is a determinant (negated), and determinants stay the same when you add a multiple of one column to another and change sign when you swap columns.

Dividing by q_nq_n+1 gives us an equation about convergents.

p_n+1/q_n+1 − p_n/q_n = (−1)ⁿ/q_nq_n+1

Taking the absolute value and using the fact that q_n+1 > q_n gives us a simpler equation (with equality when n = 0 and a₁ = 1).

|p_n+1/q_n+1 − p_n/q_n| < 1/q_n²

Then, because the convergents alternate, we know that x has to lie in between (with equality when n+1 = n_max).

|x − p_n/q_n| < 1/q_n²

As it happens, the two caveats can't both apply at the same time, so the inequality is always strict. However, there's another complication. Since n+1 no longer appears as a subscript, it looks like the equation ought to apply when n = n_max, even though the derivation didn't cover that case. Fortunately, we can cover it now by observing that the left-hand side is zero.

And that's the result! When x is irrational, it tells us that there are an infinite number of fractions p/q such that |x − p/q| < 1/q². It's closely related to Dirichlet's approximation theorem.

A fraction like that is an unusually good approximation to x, but I shouldn't put it that way because I already used the phrase “good approximation” to mean something else near the end of the essay Continued Fractions. We'll have better words available soon.

Can we increase the exponent and find an infinite number of fractions such that |x − p/q| < 1/q^2+ε? Almost surely not. In any unit interval, there are q fractions with denominator q, and each covers an interval of size 2/q^2+ε, so the total covered size is 2/q^1+ε. Call that set of intervals A_q, and define B_q to be the union of all A_i with i ≥ q. The set C of numbers that have an infinite number of suitable approximations is a subset of every B_q, and in fact is exactly the intersection of all of them. But, when ε > 0, the sum over q of 2/q^1+ε converges, so that as q becomes large, the size of B_q becomes arbitrarily small. Therefore, C has measure zero. That was an exam problem in the measure theory class I took in college!

That result is related to Roth's theorem.

Roth's theorem states that every irrational algebraic number α has approximation exponent equal to 2.

In those terms, C is the set of numbers with approximation exponent at least 2+ε, plus the rationals because I didn't bother to exclude them.

Now let's return from the infinite and think about individual numbers again. Since we can't increase the exponent, let's add a multiplier, the approximation quality Q, that tells how good an approximation the fraction p/q is to the number x.

|x − p/q| = 1/Qq²

We can easily rearrange that to get the definition of Q.

Q = 1/q²|x − p/q|

The name “approximation quality” is one of my contributions. The concept is definitely present in the other sources, but there's no name, and names are important.

Here are three nice little results about approximation quality.

• Every convergent has Q > 1. That's just a restatement of the fundamental result, of course.
• Of every two consecutive convergents, at least one has Q > 2. The proof is easy if you remember that the distance between convergents is exactly 1/q_nq_n+1.
• Of every three consecutive convergents, at least one has Q > R, where R is the square root of 5, approximately 2.236. The proof is more complicated, but it's still just algebra, less than a page in [Hua].

That last result has the same kind of corollary as the fundamental result: when x is irrational, there are an infinite number of fractions p/q with Q > R. Hold that thought, we'll come back to it in a minute.

We're going to see a lot more of R, so let me mention a couple of things. First, here and in On Rectangular Tilings R means the square root of 5, but in the essay Continued Fractions it means the square root of 3. Sorry about that! Second, why am I giving you a decimal expansion in an essay about continued fractions? Surely what you really want to know is that R is approximately 161/72.

		2	4	4	4	4	4
0	1	2	9	38	161	682	2889
1	0	1	4	17	72	305	1292