The True Pattern

The first step is to realize that it was a mistake to normalize the Markov solutions. Here's the structure that we want.

2				5				1
2		29		5		13		1
2	169	29	433	5	194	13	34	1

Here we have solutions where the largest value is always in the center. In the first row we have the solution (2,5,1). In the second row there are two solutions. On the left we have (2,29,5), constructed by flipping the value on the right in (2,5,1) and putting it in the center, and on the right we have (5,13,1), constructed by flipping the value on the left in (2,5,1) and putting it in the center. In the third row we have four solutions, and so on.

Now let's do the same thing with large and small units, which can be either expansions or matrices. (We know from A Nice Correspondence that the two are essentially the same.)

L				LS				S
L		LLS		LS		LSS		S
L	LLLS	LLS	LLSLS	LS	LSLSS	LSS	LSSS	S

Here we have triples where the center is always just the product of the sides. In the first row we have the triple (L,LS,S). In the second row we have two triples, (L,LLS,LS) and (LS,LSS,S). In the third row we have four triples, and so on.

Here are the expansions and matrices for the initial triple, along with the corresponding Markov numbers u.

	L			LS			S
	2			5			1
	22			2211			11
	5	2		12	7		2	1
	2	1		5	3		1	1

For each of those matrices, the trace is 3u and the entry in the lower left corner is u. We can and will prove that the rest of the matrices have the same properties. By the way, a matrix with those properties is called a Cohn matrix. The definition in [Aigner] says that the value u ought to appear in the upper right, but that's not what we want here, so I've transposed everything.

Before we prove anything, though, we'll need to know four interrelated facts about 2×2 matrices with determinant 1. I think of myself as having a pretty good understanding of matrices, but I was very surprised by these facts.

First, suppose we have a matrix G, and suppose we also write down the transposed cofactor matrix.

a	b		d	−b
c	d		−c	a

The product of the two is (ad − bc)I, but ad − bc = det G, and here det G = 1, so the second matrix is actually the inverse of the first.

Second, the matrices have the same trace.

tr G = (a + d) = tr G⁻¹

Third, if we add the matrices together, the off-diagonal entries cancel.

G + G⁻¹ = (a + d)I = (tr G)I

Fourth, we can rearrange that last equation to get a strange result.

G = (tr G)I − G⁻¹

Now we can prove things! We'll use induction over the tree structure, so suppose that we have a triple (L,LS,S) of matrices, that we have a solution (v,u,w), and that the traces of the matrices are equal to three times the corresponding Markov numbers.

tr L	= 3v
tr LS	= 3u
tr S	= 3w

Here we don't assume that v is larger than w or that L is in any sense larger than S.

Now let's look at tr LLS. We can apply the fourth matrix fact with G = LS.

tr LLS = (tr L)(tr LS) − tr L(LS)⁻¹

To simplify that last term, we can use (1) the fact that traces are invariant under rotation and (2) the second matrix fact.

tr L(LS)⁻¹ = tr LS⁻¹L⁻¹ = tr S⁻¹L⁻¹L = tr S⁻¹ = tr S

Here's the result.

tr LLS = (tr L)(tr LS) − tr S

We know the values of everything on the right-hand side.

tr LLS = (3v)(3u) − 3w = 3(3uv − w)

But, we've seen 3uv − w before! It's the value u_w that we get from flipping the value w. That takes care of the left branch of the tree.

tr L	= 3v
tr LLS	= 3uw
tr LS	= 3u

In the same way, we can show that the right branch of the tree contains the value u_v = 3uw − v that we get from flipping the value v.

tr LS	= 3u
tr LSS	= 3uv
tr S	= 3w

What about the entries in the lower left corners of the matrices? Well, first of all, to get a grip on them mathematically we can use the unit vectors e₁ and e₂. Here's one example.

e₂^TLe₁ = v

We can remove the Markov number from that equation by multiplying by 3.

3e₂^TLe₁ = 3v = tr L

Then we can swap the left and right sides to get nice initial conditions for induction.

tr L	= 3e2TLe1
tr LS	= 3e2TLSe1
tr S	= 3e2TSe1

To start the induction, we can take an equation from above …

tr LLS = (tr L)(tr LS) − tr S

… and substitute in the new values.

tr LLS = (3e₂^TLe₁)(3e₂^TLSe₁) − 3e₂^TSe₁

How anyone ever figured out this next part, I have no idea. On the right side of tr L we have Le₁, which is a column vector with components a and c, and on the left side of tr LS we have e₂^TL, which is a row vector with components c and d. Since they're next to each other, we can multiply them together, but we have to remember that matrix multiplication isn't commutative. When we multiply a row vector by a column vector, we get a scalar, the dot product, but when we multiply a column vector by a row vector, we get a matrix.

ac	ad
cc	cd

That matrix looks a lot like the matrix cL (or Lc, same thing).

ac	bc
cc	dc

In fact, the difference is zero except that the entry in the upper right corner is ad − bc = det L = 1.

0	1
0	0

We can write that as e₁e₂^T, then we have the following.

Le₁e₂^TL = cL + e₁e₂^T

We can rewrite the matrix cL by tacking on a factor of 3 and then applying the third matrix fact.

3cL = 3vL = (tr L)L = (L + L⁻¹)L = LL + I

Let's put all the pieces together.

3Le₁e₂^TL = 3cL + 3e₁e₂^T = LL + I + 3e₁e₂^T

When we put that back into context, the third term becomes zero when it meets the e₂^T in front, the second term becomes 3e₂^TSe₁ and cancels with the second term in the context, and the first term becomes the desired result.

tr LLS = 3e₂^TLLSe₁

If we copy and paste the equations for tr L and tr LS, that takes care of the left branch of the tree. And, of course we can handle the right branch of the tree in just the same way.

tr LSS = 3e₂^TLSSe₁

With that, the proof is complete. Unfortunately, it's only a proof, and not, as the Merovingian would say, a reason.

But this is not a reason, this is not a “why”.

Where does that leave us?

• From Group Elements and Matrices we now really know that D = 9u² − 4. The pattern magic has become pattern technology!
• From The Discriminant we now really know that M ≥ (root D)/u (because the entry in the lower left corner of the matrix is also the denominator q_L−1).
• We still don't know how to prove that that inequality is actually an equality.
• We still don't know how to prove that there are no other expansions with M < 3.