Equivalence

Now let's go back and look at that held thought one more time.

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

Also, because the approximation quality of the golden mean converges to R, R is the largest number for which that's true. That's a valid statement about numbers in general, but it feels like it ought to be a statement about the golden mean. So, let's make it one! When x is irrational, define the Markov constant M(x) to be the largest number for which there are an infinite number of fractions p/q with Q > M(x). Then the statement we wanted is that when x is the golden mean (R+1)/2, M(x) = R.

It's unfortunate that M(x) is called the Markov constant of x. It depends on x, so it's a function, not a constant!

It's also unfortunate that the definition I gave isn't quite correct. For the golden mean it happens to work because the quality approaches the limit point from above and below, but if the quality only approached the limit point from below, there would be no fractions with Q greater than the limit. What we really need to say is that M(x) is the largest number for which for every ε > 0 there are an infinite number of fractions p/q with Q > M(x) − ε. That's a lot of words, so maybe we'd be better off reusing an existing concept.

M(x) = lim sup Q_n

If you haven't run into it before, “lim sup” stands for “limit supremum” or “limit superior” and means the largest limit point. It has a well-defined value even for sequences that don't converge, although that value might be positive or negative infinity.

Now, remember the equation for Q_n? And how in the limit as n went to infinity, the contribution of a₀ went to zero? Well, the same is true of any finite number of coefficients. As a result, we have M(x) = R not just for the golden mean but also for any other number with an expansion that ends with an infinite number of 1s! Sadly, I don't know any simple way to characterize the other numbers except to say that they're a small subset of numbers of the form r + sR, where r and s are rational. In particular, R = [2,4] is not one of the numbers.

More generally, let's say that two numbers are equivalent if their expansions end with the same thing, i.e., if we can make their expansions identical by removing finite prefixes of possibly different lengths. By the argument above, if x and y are equivalent, then M(x) = M(y).

Here's a fun fact: every equivalence class is dense in the sense that every neighborhood of every point contains a representative. I don't have a source for that, so here's a quick proof. Given a neighborhood, first pick any irrational number x inside, then construct a number y by gluing the first n terms of the expansion of x onto the expansion of any representative of the equivalence class. That number y is also a representative, and we can make it as close to x as necessary by a suitable retroactive choice of n.

|x − y| ≤ |x − p_n/q_n| + |y − p_n/q_n| < 2/q_n²

Because of that, M(x) is about as far from continuous as it's possible to get—it takes on every possible value in every neighborhood of every point.

I find that definition of equivalence vague and unsatisfying, so here's a second approach. Consider the two operations J(z) = 1/z and T(z) = z+1 (“T” for “translate”). In terms of continued fraction expansions, J adds or removes an initial zero and T changes the initial coefficient. Now, what about the group of functions generated by J and T? On the one hand, the generators J and T only connect numbers to equivalent numbers, so the same is true of the generated group. That is, all connected numbers are equivalent. On the other hand, it's easy to write down a sequence of operations that removes one prefix and adds another, so all equivalent numbers are connected. In short, two numbers are equivalent if and only if they're connected by the action of the group, so we can take that to be the definition of equivalence if we want. That group doesn't seem to have a standard name, so let's call it the continued fraction group.

Again, I left out an important detail. For positive numbers J adds or removes an initial zero, but for negative numbers it's not at all clear what it does. It's not even clear that it produces equivalent numbers! Fortunately, there's a way around that obstacle. Consider the operation N(z) = −z. It's not clear what it does, either, but I figured it out by looking at some examples. (Too bad I didn't check item 101A in HAKMEM first.) If the second coefficient of the expansion isn't 1, we can apply the following equation.

−[a₀, a₁, a₂, a₃, … ] = [−a₀−1, 1, a₁−1, a₂, a₃, … ]

And, if the second coefficient of the expansion is 1, we can apply the same equation in reverse. Since a₀ can be positive or negative (or zero), that covers all the possibilities. Then, when faced with a negative argument, we can rewrite J as NJN. It still may not be clear what it does, but at least it's clear that it produces equivalent numbers.

Let's define one more operation, S(z) = −1/z. The group of functions generated by S and T is called the modular group. The advantage of S over J is that if we think of z as a complex number, then S and T both map the upper half H of the complex plane back to itself. The symbol “H” is pleasant because it can stand for both “half” and “hyperbolic”, and the upper half plane is one of the standard models of the hyperbolic plane, a surface of constant negative curvature. The hyperbolic plane can be tiled with many kinds of polygons. If we tile it with 60-60-0 triangles that have one vertex off at infinity, the symmetry group of that tiling (without reflections) is the modular group.

Also, I'm pretty sure that the symmetry group with reflections is the continued fraction group. Granted, the continued fraction group doesn't map H back to itself, but we can get around that by identifying each point with its complex conjugate. That's all I'm going to say about geometry.

So far, the second approach is also pretty vague, but we can fix that. Two numbers are equivalent if and only if they're connected by the action of the group, and the general group element has the form

	az + b
G(z) =	–––––
	cz + d

where a, b, c, and d are integers and ad − bc = ±1. If you recognize that as some kind of determinant, congratulations! To understand exactly what's going on, let's look at some groups of 2×2 matrices over the integers (Z).

GL(2,Z)		PGL(2,Z)
SL(2,Z)		PSL(2,Z)

GL(2,Z) is the general linear group of invertible matrices. A matrix over a field is invertible if its determinant is nonzero, but a matrix over a ring like the integers is invertible if its determinant is invertible (a unit), so GL(2,Z) is the group of matrices with determinant ±1.

SL(2,Z) is the special linear group of matrices with determinant 1. It's a subgroup of GL(2,Z), exactly half the size.

In the names of the other two groups, the “P” stands for “projective”. In the current context, that means “take the quotient by the two-element subgroup {I,−I}” or “consider a matrix and its negative to be the same”. Since I just mentioned the identity matrix I, here's a table of all the matrices I want to talk about, plus the Pauli matrices just for fun.

	G			I			J			N			S			T			U
a	b		1	0		0	1		−1	0		0	−1		1	1		1	0
c	d		0	1		1	0		0	1		1	0		0	1		1	1
							σ1			σ3			σ2
						0	1		1	0		0	−i
						1	0		0	−1		i	0

Now, suppose we define a function f that maps the matrix G to the function G(z). What can we say about it? Well, it's a homomorphism because function composition weirdly has the same effect as matrix multiplication, and it has the property that f(−G) = f(G) because the minus signs in the numerator and denominator cancel. In fact, it's exactly two-to-one. So, we can regard it as a function on PGL(2,Z), and when we do, we find that it's an isomorphism. In other words, PGL(2,Z) and the continued fraction group are essentially the same! They're also both exactly half the size of GL(2,Z).

In the same way, PSL(2,Z) and the modular group are essentially the same, and are both exactly half the size of SL(2,Z). To complete the square in the diagram, note that PSL(2,Z) is also a subgroup of PGL(2,Z), exactly half the size.

I claimed that the continued fraction group consists of all functions with ad − bc = ±1, and I just used the fact that the modular group consists of all functions with ad − bc = 1 without even claiming it first, but how do we know that? The easiest path forward is to prove that the matrices J and T generate GL(2,Z) and that the matrices S and T generate SL(2,Z), then the rest follows. For the latter, the article SL(2,Z) starts with a nice direct proof. For the former, I was stuck until I found the answer in an item on Stack Exchange that referred to the same article. Here's the key fact.

S = T⁻¹UT⁻¹ = T⁻¹JTJT⁻¹

So, the group generated by J and T contains SL(2,Z). However, it's larger than SL(2,Z) because it contains J, and the only larger option is the whole group GL(2,Z).

By the way, the argument above about N(z) didn't require it to be an element of the group, but in fact it is. We know that just from the determinant, but here's an explicit construction with matrices. Note that JS = −N.

N = SJ = T⁻¹JTJT⁻¹J

Here are two other benefits of the second approach.

• It's obvious that the continued fraction group and the equivalence classes are countable. The group is smaller than Z⁴, Q.E.D.
• It's obvious that the rational numbers are a single equivalence class. We don't have to philosophize about whether two finite expansions end with the same thing, we can just immediately write down a group element that connects them.

Sorry that was so long! The trouble is, the modular group is well known, in fact there's a whole chapter about it in [Hua], and the first approach to equivalence is well known, but it took me a while to piece together the exact nature of the relationship between them via the continued fraction group. So, I figured I'd better write down the whole story.