3/28/03 About a week ago, Ian, Andy, and I were discussing the connection between the Ptolemy recurrence and the Markov recurrence. Since none of us was particularly familiar with hyperbolic geometry, we disregarded that approach to the problem for the moment and instead worked purely combinatorially. The basic connection is as follows: We first tile the lattice plane with an infinite triangular grid such as the following - \| \| \| \| \| -+---+---+---+---+- |\ |\ |\ |\ |\ | \ | \ | \ | \ | \| \| \| \| \| -+---+---+---+---+- |\ |\ |\ |\ |\ | \ | \ | \ | \ | \| \| \| \| \| -+---+---+---+---+- |\ |\ |\ |\ |\ | \ | \ | \ | \ | \| \| \| \| \| -+---+---+---+---+- |\ |\ |\ |\ |\ - so that each unit square contains two triangles. Now, we can assign one variable to all horizontal edges, one variable to all vertical edges, and one variable to all diagonal edges. If v is an integer vector whose coordinates are relatively prime, consider the line segment passing from the origin to v; the triangles through which it passes form some triangular strip, i.e. a triangulation of a polygon whose edges (including diagonals) have all been labeled. Therefore, we can apply the Ptolemy recurrence and obtain a Laurent polynomial in our initial three edge variables, which we shall call Q(v). Notice that, because our edge labels are invariant under translation, we get the same polynomial by applying the Ptolemy recurrence to the strip between w and v+w, for any vector w. Now, these strips are invariant under 180-degree rotation. It follows that if the strips from the origin to v and to w are both contained in the strip to v+w, then the Ptolemy recurrence applies to the points 0, v, v+w, w, giving Q(v)^2 + Q(w)^2 = Q(v-w)Q(v+w). This looks a lot like the Markov recurrence. However, we must remember that we cannot apply it to arbitrary v and w - it only works when their strips align properly. If the strip to v is not contained in the strip to v+w, then when we apply the Ptolemy recurrence to the strip from the origin to v+w, we obtain (as an intermediate step) a polynomial between 0 and v, but it will not necessarily coincide with Q(v), so the above relation among values of Q will not ensue. However, Ian worked out cases where we do obtain the Markov recurrence and found that we do indeed get all Markov numbers - corresponding precisely to those vectors whose coordinates are relatively prime positive integers. In fact, when a < b, c < d, we get Q(a+c,b+d) from Q(a,b) and Q(c,d) exactlywhen a/b, c/d are consecutive Farey fractions. Thus (and here I assume x, y, z = 1 in order to use numeric values, which are probably more recognizable than polynomials): Q(0,1) = 1 \----\ \----\ \----\ \----\ \----\ \----\ Q(1,1) = 2 /--/ /--/ Q(1,2) = 5 / \ / \ / \ Q(1,3) = 13 Q(2,3) = 29 / | | \ / \ / \ / | | \ Q(1,4) = 34 Q(2,5) = 194 Q(3,5) = 433 Q(3,4) = 169 We see, then, that we get an identification of something like the Markov tree - where instead of writing a triplet at each node, we only write its largest member - with the Farey tree. I'm not sure this is the ideal indexing system, so we may wish to revise it later; at any rate, this gives the basic indications of what is going on. As far as I'm aware, we don't yet have a written proof of this, but that should be easy to take care of; the main issue is settling details of notation. The final blow demonstrating that this is the correct way to look at Markov numbers comes when we actually apply our interpretation of the Ptolemy polynomials to these triangular strips. Recall (cf. my emails from March 18) that the Ptolemy polynomials count matchings of certain graphs whose faces are all squares. When we construct these graphs from Markov strips, it looks like we obtain the original snake graphs. Again, we don't have a proof of this written up, but it looks like the work should be straightforward. This now elicits lots of observations and questions. For one thing, it remedies our frustration with the asymmetry of the earlier construction for Markov snake graphs, since addding and subtracting vectors are inverse operations. I recall Jim saying something about the correspondence between the Markov tree and Conway's topograph of superbases in _The Sensual (Quadratic) Form_, and in fact, the above shows us exactly how to biject between superbases and Markov triples, by sending each vector within a superbase to the corresponding Markov number. (In fact, the vectors appearing in a superbase are precisely those whose coordinates are relatively prime.) Notice that (in Conway's terminology) we are really dealing with lax superbases, because Q(v) = Q(-v). This picture also explains why the snake graphs associated with the Dana-Scott numbers have slope approaching the golden ratio - the corresponding Farey fractions are in fact successive convergents to the golden ratio. (A similar observation appears at http://www.qnet.com/~crux/markov.html , regarding the green line in the picture there; however, the green line is labeled as 2/3, because Tom Ace identifies the tree with the fractions in Z[1/2] rather than with all fractions. It's pretty clear from the above, though, that the Farey tree interpretation is more fruitful.) A major question is how to take advantage of this picture to split up the Markov polynomials into more variables. We can't immediately just assign every edge its own variable, because that destroys the crucial translational symmetry. So: Problem, vaguely: How do we give (at least some) different weights to different edges of the same orientation and still make this model work? More important, I think, is the fact that the picture gives us a correspondence between Markov numbers, positive integer vectors, and positive rational numbers. One thing I tried doing early on was writing the Markov number corresponding to v at the point v in the plane and seeing if any patterns emerged. It appears that, when a < b < c, the Markov number at (b,c) is less than that at (b+a,c-a). The numbers Q(1,n) are alternate Fibonacci numbers, and the numbers Q(n-1,n) are alternate Pell numbers (see the qnet.com site mentioned above ). This information might be useful, say, as an order-of-magnitude estimate that could come up in a Markov uniqueness proof. An estimate of the densities of the Markov numbers is mentioned Guy's _Unsolved Problems in Number Theory_ D12 (page 94 of the 1981 edition), although I haven't tracked down Zagier's original AMS paper in which he proved this. In any case, I'm wondering if the above observations - essentially that the Pell and Fibonacci numbers give upper and lower bounds for each row of Markov numbers - could give another proof of this same estimate: Conjecture: Q(b,c) < Q(b+a,c-a) for a < b < c. Problem: If this result is true, what sorts of information does it give about the distribution of Markov numbers? [Note: this conjecture was proven - see below.] I haven't made further observations about these numbers, but I'll post a table of them at some point and see if we notice anything else interesting. Another promising direction of investigation is the connection between snake graphs and continued fractions - cf. David Speyer's emails of April 21, 2002. This points out that if we take "partial subsnakes" of a snake graph and successively compute their numbers of matchings, we get the same recurrence as that used to compute convergents of a continued fraction. So the number of matchings of any given snake graph is really the numerator of a rational number that depends on the shape of the snake. My empirical findings suggest that the denominators of these rational numbers satisfy another quadratic recurrence: if Q(v)/R(v) is the rational number associated to the Markov snake at vector v, then if v, w are successive vectors on the Farey tree, Q(v)^2 + Q(w)^2 = Q(v-w)Q(v+w) as before, and Q(v)R(v) + Q(w)R(w) = Q(v-w)R(v+w). Again, I don't have a proof of the second relation written out, but it should be straightforward to derive. I briefly checked Sloane's database for the values of the denominators R(v) and didn't find any match in there, although I haven't yet tried SuperSeeker. [Postscript: A later run through SuperSeeker still found no matches.] Thus: Experiment: What sorts of values do we get for the R(v)'s? The fractions Q(v)/R(v) might be of interest. It appears that, as a/b increases over rational numbers between 0 and 1, Q(a,b)/R(a,b) also increases. This should be easy to prove, using the continued-fraction expansion - it basically reflects the way the shape of the snake graphs changes. I'm also curious as to what numbers these snake-fractions are the convergents of. (I believe Jim raised a question similar to this last spring, although we didn't have the Farey connection at that time.) For example, the numbers Q(n,n+1)/R(n,n+1) seem to be the convergents to 1 + sqrt(2)/2 (explaining the Pell numerators), and Q(1,n)/R(1,n) are the convergents to the golden ratio. More generally, any rational number a/b seems to give rise to a finite family of quadratic irrationals {lim as k -> infty of Q(ak+p)/R(bk+q) | p, q integers}. Is there a canonical way of choosing p and q here so as to obtain a nice map from rationals to quadratic irrationals? In any case, what characterizes the quadratic irrationals that we obtain? More generally, we can take any positive real number x and take the limit of Q(a,b)/R(a,b) as a/b -> x (or something like that). The image of this map is no longer restricted to quadratic irrationals; what is it? What nice properties does the map have? I'm also thinking we can use the continued-fraction approach to prove results such as the inequality conjectured above. For one more direction of investigation, the Conway and Coxeter article on friezes and the Ptolemy recurrence (which I have not read) might give us an alternative combinatorial interpretation to explore. I've done a little library research on Markov numbers, but there doesn't seem to be a whole lot of it out there, and I haven't found any mention of Farey fractions, so this connection may well be an entirely new finding. It looks like the main significance of Markov numbers is via another connection with continued fractions and quadratic forms: they seem to be related to various values of min{q^2 * |x - p/q| | p, q integers} for quadratic irrationals x (quadratic irrationals being the hardest numbers to approximate by rationals). I'm intending to do more reading in this direction. I've at least glanced at most of the articles and books references in Guy's section on the Markov number problem, as well as those listed in Sloane's online encyclopedia for the Markov numbers, although I haven't checked many of the references on Tom Ace's qnet.com page. Anyhow, if anyone is interested in learning about this stuff and wants to be saved an hour or two of ambling around libraries, I can tell you about what I've learned so far. It looks like there's a lot of interesting stuff to investigate here. Let me know if you're interested in working on any of this. 3/29/03 Following the continued-fraction approach a bit: All the continued fractions corresponding to snakes have the following property: the number of terms is even (if we write a final 2 as 1 + 1/1), and for every i, the (2i-1)th and (2i)th terms are both 1 or both 2. I conjectured that all continued fractions with this property would yield distinct numerators; if this were true, the uniqueness of Markov numbers would immediately follow. However, it is false. What sets the Markov snakes off from other snakes is that the 2's and 1's are in some sense "evenly distributed" among the terms of the continued fraction, but I have no idea as of yet how to make use of this property. 4/5/03 Harvey Cohn's article "Markoff Forms and Primitive Words" (Math. Ann. 196, 8-22) contains some of our earlier findings (thanks to Jim for the reference). In particular, Cohn expresses Markov numbers as emerging from products of matrices determined by rational words. If we consider the relations between numerators and denominators in successive convergents to continued fractions, we can express these via products of matrices that are again ordered according to rational words, although the matrices I found do not appear to be the same as those in Cohn's article (though presumably they are closely related, e.g. possibly interchanged by some conjugation). Cohn also lists explicitly the Markov numbers corresponding to a few sample pairs of relatively prime positive integers. So, although I haven't read through the whole article (either Ian or Andy is currently in possession of it), it appears that the connection between the Markov tree and the Farey tree is already known, at least implicitly. Of course, the combinatorial side of the picture is still news. Also, Ian and Andy were fairly easily able to prove the conjecture above concerning the ordering of Markov numbers along diagonals, using the continued-fraction method. They also used this result to obtain explicit asymptotics for the Dana-Scott sequence, although I haven't seen the formula myself.