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.