The True Formula

It's fairly easy to prove that the values u, v, and w in a Markov solution are pairwise relatively prime. The proof uses a type of induction that moves upward through the tree instead of downward. If a number d is a divisor of two values in the (normalized) solution (u,v,w), then it's a divisor of the same two values in the (unnormalized) parent solution (3vw − u,v,w), so by induction it must be a divisor of two values in the root solution (1,1,1). You can say that's a contradiction, or you can say that therefore d = 1, as you like.

In particular, v and w are relatively prime to u. That means we can think of them as elements of the group U_u of integers relatively prime to u under multiplication mod u, and that means we can run the following little algorithm that I learned about from [Aigner].

1. Compute the inverses v⁻¹ and w⁻¹. (Using continued fractions!)
2. Multiply to get vw⁻¹ and wv⁻¹.
3. Normalize them into the range (0,u).
4. Select the numerically smaller one.

The result, called the characteristic number of the solution, is exactly the number t from the previous essay!

Doing modular arithmetic here is bizarre, and doing modular arithmetic and then asking which number is smaller is super fishy, so how can that algorithm possibly work? Part of the answer is that we chose the origin of t correctly, but most of the answer is that I don't know because I haven't gotten to that part of the book yet. However, I suspect the answer will be too complicated for me to summarize effectively. Sorry!

Now let's use the little algorithm to have some fun. Given a solution, we can write down the matrix T(u) directly, without working our way down from the root of the tree.

2u + t		b
u		u − t

We can compute the expansion from the matrix, as discussed at the end of Six Operations.

We can write down the rational value (again).

value(T(u)) = 2 + t/u

We can even write down the irrational value that we get when we let the expansion repeat, as discussed in Group Elements and Matrices.

(1/2u) [ u + 2t + root D ]

The definitions of D and M ought to be familiar by now.

D	= 9u2 − 4
M	= (root D)/u = root(9 − 4/u2)

The number above is a representative of the equivalence class with Markov number M. In fact, it's the best representative, because the non-repeating part is empty and the repeating part is the true pattern, not some rotation.

The formula above is remarkably similar to the two incorrect formulas that we saw at the start of The Pattern. Let's take a look at where those formulas went wrong.

The first formula, from [Hua], can be corrected with only two small adjustments.

(1/2u) [ u + (2v/w) + root D ]

First, we need to reinterpret v/w, a quotient of integers, as vw⁻¹, a quotient mod u followed by normalization. Second, we need one new fact. Remember how the solutions of the true pattern look like (v,u,w)? And how v and w are in a definite order that alternates between v > w and v < w? (See the end of Mutations.) Well, if we have a solution in that order, then vw⁻¹ is smaller than wv⁻¹, so that t = vw⁻¹. I haven't seen a proof of that yet, but I've verified it by experiment.

The second formula, from Wikipedia ([MC]), can also be corrected with only two small adjustments.

(1/2u) [ 2t − 3u + root D ]

First, we need to add 2 to turn negative 3u into positive u. I guess someone didn't like the natural range (2 1/3,2 1/2)? Second, in that formula, t was defined to be the smallest positive integer such that t² + 1 is divisible by u, but we need to redefine it to be the characteristic number. That sounds like a large adjustment, but let me point out a few things.

On the one hand, the matrix T(u) contains integers. On the other hand, we know that the entry in the upper right corner looks like this.

b = 2u − t − (t² + 1)/u

Therefore, for the characteristic number, t² + 1 must be divisible by u.

That last sentence is super awkward and doesn't give me any intuition. We can do better! For any number j, if j² + 1 is divisible by u, then j² + 1 ≡ 0 mod u, or equivalently, j² ≡ −1. In other words, j is a square root of −1! As a result, it shares some properties with the complex number i.

• (+j)(−j) = −j² ≡ +1, so −j is the inverse of j.
• (−j)(−j) = +j² ≡ −1, so −j is also a square root of −1.

Now let's look back at the two numbers vw⁻¹ and wv⁻¹ from the little algorithm. One became the characteristic number t, so it's a square root of −1, but then the other is the inverse, …

(vw⁻¹)(wv⁻¹) = v(w⁻¹w)v⁻¹ ≡ vv⁻¹ ≡ 1

… so it's equal to −t, so it's also a square root of −1.

With that information, we can rephrase the second adjustment so that it's obviously small.

… t was defined to be the smallest square root of −1, but we need to redefine it to be the smaller of two numbers that are both square roots of −1.

Is that even an adjustment at all? It is, but only because for some values of u, the group U_u contains more than two square roots of −1. The first such value is u = 610, where there are two pairs of square roots, and the smallest happens to be one of the wrong pair. The details are fascinating, but I'll hide them in a big footnote.

I also hid an important fact in the middle of a sentence above: “the other is … equal to −t”. To be more precise, as a group element we know that the other is equal to −t, but as a number we only know that it's congruent to −t. But, we also know that it lies in the range (0,u), and that's enough to pin it down: u − t.

That fact gives us two more ways to approach the formula from [Hua].

For reference, here's the current approach: make sure that the solution (v,u,w) is in the right order, then compute vw⁻¹ and use it.

New approach #1: just compute vw⁻¹ and use it.

• If vw⁻¹ happens to be t, great! The formula will produce the number determined by T(u), as above.
• If vw⁻¹ happens to be u − t, well, with parameter u − t instead of t, the formula will produce the number determined by B(u). That's a different number, but it has the same Markov constant, so it accomplishes the purpose of the formula. We don't actually know yet that it has the same Markov constant, but the future essay about B(u) will explain that.

We can do better by understanding why vw⁻¹ happens to have one value or the other, but first we'll need to know one little fact that's almost too obvious to mention. Since vw⁻¹ and wv⁻¹ are equal to t and u − t in some order, we know what they add up to.

vw⁻¹ + wv⁻¹ = t + (u − t) = u

New approach #2: compute vw⁻¹, then compute t and use that in place of vw⁻¹.

• If vw⁻¹ < u/2, then vw⁻¹ is smaller than wv⁻¹, so t = vw⁻¹, great!
• If vw⁻¹ > u/2, then vw⁻¹ is larger than wv⁻¹, so t = wv⁻¹ = u − vw⁻¹.

Or, we can avoid the cases, reduce code complexity, and maybe even speed things up by using the following equation instead.

t = min(vw⁻¹,u − vw⁻¹)

Of course, as soon as we use t in place of vw⁻¹, we don't really have the formula from [Hua] any more, we have the true formula plus two nearly identical ways to speed up the little algorithm by a factor of two.

That's the end of the long and convoluted story of the incorrect formulas.

What about the special cases u = 1 and u = 2? There are four points I'd like to make.

1. Remember this table?

   u	t	T(u)	value(T(u))
   1	0	11	2
   2	1	22	2 1/2

   Those values of t produce the correct matrices T(u), therefore they also produce the correct irrational values in the true formula.

2. On the one hand, it's no accident that those values of t exist. T(1) and T(2) are Cohn matrices, so the matrix parametrization applies. On the other hand, we shouldn't use the little algorithm to calculate those values of t. For u = 1, the group U₁ doesn't even exist! For u = 2, the group U₂ does exist, but it's trivial, and there's no reason to expect that the calculation would work (although in fact it does). Even the pattern doesn't work for the solution (2,1,1).

   22 ≠ 11 & 11

3. In the original pattern the role of the special cases wasn't clear, but in the true pattern it is. We start with T(2) on the left and T(1) on the right, then compute T(5) and the rest of the tree using the rule

   T(u) = T(v) & T(w).

   We start with T(1) and T(2)—they are initial conditions. We already know everything about them, so we shouldn't be concerned with whether equations and formulas apply.

4. What about B(u)? Well, we compute B(u) from T(u). We can retroactively come up with a rule that it obeys,

   B(u) = B(w) & B(v),

   but we can't use that rule to compute B(u) from initial conditions because it doesn't work when B(1) is involved. That seems like a great reason to say we shouldn't even define B(1) and B(2).

That's the last word about special cases.