Mutations

Let's go back and think about that tree structure a little more. At each point, remember, we have a triple (L,LS,S) of matrices where the center is the product of the sides. OK? Now suppose that at a single point in the tree we introduce a mutation by taking the product in the wrong order, and that afterward we let the mutation propagate downward in the usual way. Here's a before-and-after view of the mutated subtree.

L				LS				S
L				SL				S
L		LLS		LS		LSS		S
L		LSL		SL		SLS		S
L	LLLS	LLS	LLSLS	LS	LSLSS	LSS	LSSS	S
L	LLSL	LSL	LSLSL	SL	SLSLS	SLS	SLSS	S

Can we still prove that the traces are equal to 3u? Yes! All we need to know is that traces are invariant under rotation. So, in the first row we have

tr SL = tr LS,

and in the second row we have

tr LSL = tr LLS
tr SLS = tr LSS.

Then, since the products in the second row are back in the correct order, we can let induction take care of the rest.

Can we still prove that the entries in the lower left corners are equal to u? No, because it's not true! The very first example is a counterexample. If we choose to introduce the mutation at the top of the tree, and choose to examine the top of the mutated subtree, here's what we find.

	LS			SL
	5			5
	2211			1122
	12	7		12	5
	5	3		7	3

Don't be fooled! In that example, the expansion gets reversed and the matrix gets transposed, but in all other possible examples, neither of those things happens. That's pretty easy to prove, but it's not important, so let's skip it.

Although that example isn't typical in that way, it's typical in another way: all other possible examples are also counterexamples. That's difficult to prove, and it's not important, so, again, let's skip it.

To get back to the tree structure, here are four observations.

1. Every unmutated form starts with L except for the S on the right. That's easy to prove, because S can never be the left factor in a product.
2. In the same way, every unmutated form ends with S except for the L on the left.
3. In the left half of the tree, from L to LS inclusive, every unmutated form starts with L, and mutation moves that L to the end. That's easy to prove, because in a product, the Ls move in tandem. The L in the left factor moves from the start to the center and the L in the right factor moves from the center to the end.
4. In the same way, in the right half of the tree, from LS to S inclusive, every unmutated form ends with S, and mutation moves that S to the start.

Have I managed to preserve the surprise? When a chunk is moved from the start to the end of an expansion, or vice versa, that's a rotation. Every mutated form is a rotation!

Now that we understand single mutations, we can use multiple mutations to convert the true pattern into the original pattern. All we have to do is walk down through the tree in breadth-first order and at each point make the right decision about whether to mutate.

In the original pattern, remember, we had solutions (u,v,w) that were normalized to have u > v > w (for u ≥ 5) and expansions that were defined as follows.

expansion(u) = expansion(v) & expansion(w)

Later, in Symmetries, we added the idea of large and small units, …

expansion(v)	= L
expansion(w)	= S

… and could write expansion(u) as simply LS.

In the true pattern, on the other hand, we have solutions (v,u,w) that may or may not have v > w. To reproduce the original pattern, we want the larger factor to come first, so if v > w, we should pick the unmutated form LS, while if v < w, we should pick the mutated form SL. And that does it! It really is that simple.

Here's what that means in practice.

• At depth 0, there's only one solution, (2,5,1), and we shouldn't mutate it.
• At every other depth, the solutions come in pairs with the same parent (v,u,w), so they look like (v,?,u) and (u,?,w), and we should mutate the first but not the second.

Anyway, since every mutated form is a rotation, we've now proved that the expansions of the original pattern are rotations of the expansions of the true pattern (and vice versa). We can then use that fact to draw the same conclusions about the original pattern as about the true pattern.

• Rotation doesn't change the trace, and that gives us a cleaner way to prove that the traces are equal to 3u. And, either way, we know that D = 9u² − 4.
• Rotation does change the entry in the lower left corner, but it doesn't change the Markov constant. That's almost by definition, but if you'd like something more tangible, there's a detailed example in the second half of The Discriminant. So, we know that M ≥ (root D)/u.

That's still not a proof that the pattern holds, but it's pretty close!