The Markov Equation

In the rest of this thread I'd like to present some additional information that appeals to me but has no practical value at all.

First I have to tell you about the Markov equation.

u² + v² + w² = 3uvw

A solution is a triple (u,v,w) of positive integers, normalized to have u ≥ v ≥ w.

Given one solution, we can pick one of the positions in the triple and do what's called a flip to get another solution. To do a w-flip, for example, we replace whatever value w is in the third position with 3uv − w and get the unnormalized solution (u,v,3uv − w). If we then do a second w-flip, we replace 3uv − w with

3uv − (3uv − w) = w

and get the original solution back, hence the name “flip”.

But how do we get a solution to start with? We just observe that (1,1,1) works. From there, because the values are all the same, the flips all lead to the same solution, (2,1,1). From there, the u-flip leads backward, while the other two flips lead forward to (5,2,1). For that solution and all subsequent solutions, the u-flip leads backward, while the other two flips lead forward to different solutions. As a result, the solutions form an infinite binary tree! (And there aren't any other solutions.)

Here's a picture of the solutions with u < 10⁶. The horizontal lines represent v-flips and the diagonal lines represent w-flips.

The values of u below 10³ are as shown. For the rest, and for the values of v and w, please wait, there will be a table later on that lists the same solutions in the order that you'd read them in, which because of how the tree is laid out is also preorder.

Does it really work to use u as a label? That is, is the projection from (u,v,w) to u one-to-one? The answer doesn't affect the tree structure or anything else here, but it's an interesting question. According to an isolated sentence in the Wikipedia article Markov number, the answer is unknown, even today. Just for fun, I wrote a little search program in Java using PriorityQueue (as in Other Identities) and BigInteger. It ran for about 15 seconds, found no collisions below 10⁶⁰⁰, then ran out of memory. Since Markov solutions are much sparser than powers, it seems likely that there are never any collisions.

Speaking of trees, I just learned that Pythagorean triples form a very similar tree (Wikipedia). How had I never heard of this lovely fact?