The numbers that come after the golden ratio

The rectangle that eats itself found the golden ratio’s continued fraction, $1 + 1/(1 + 1/(1 + \cdots))$, all ones, and drew from it the fact that makes the golden ratio special among irrationals: it is the hardest number to approximate by fractions. The fractions that beat every smaller one made that precise as Hurwitz’s theorem. Every irrational number $\alpha$ has infinitely many fractions $p/q$ with

$$\left|\alpha - \frac pq\right| < \frac{1}{\sqrt5\, q^2},$$

and for the golden ratio the constant $\sqrt5$ cannot be replaced by anything larger. That essay ended by naming the question this one answers: what happens when the golden ratio is set aside? The answer is a list of numbers — $\sqrt5$, then $\sqrt8$, then $\sqrt{221}/5$, and on, crowding towards 3 — which Andrey Markov found in 1879, and the surprising part is where the list comes from. Each entry belongs to a whole-number solution of one equation, $x^2 + y^2 + z^2 = 3xyz$, and the solutions form a tree.

The approximation constant of a number #

For each irrational $\alpha$, measure how well it is approximated by asking for the largest constant that still works for it: the supremum of all $c$ such that $|\alpha - p/q| < 1/(c\,q^2)$ for infinitely many fractions. Call it the Lagrange value of $\alpha$. Hurwitz’s theorem says every Lagrange value is at least $\sqrt5$, and the golden ratio’s is exactly $\sqrt5$. For a number with large terms in its continued fraction, like $e$, the Lagrange value is infinite: arbitrarily large constants work, because the fractions come extraordinarily close at every large term. The set of all Lagrange values of all irrationals is the Lagrange spectrum.

The continued fraction decides everything. The convergents $p_n/q_n$ of $\alpha$ are its best approximations, and for each of them $q_n^2\,|\alpha - p_n/q_n|$ is a number between nought and one that is small when the next term of the continued fraction is large. Oskar Perron’s formula expresses the Lagrange value through the terms: it is the largest limit, along the sequence, of $a_{n+1}$ plus the continued fraction of the terms after it plus the continued fraction of the terms before it, read backwards. A number whose terms are all 1s gets $1 + 2/\varphi = \sqrt5$; a number whose terms are all 2s gets $2 + 2(\sqrt2 - 1) = \sqrt8$.

The figure shows the measurement for four numbers. The golden ratio’s convergents, ratios of consecutive Fibonacci numbers, settle at $q^2|\varphi - p/q| = 0.4472$, which is $1/\sqrt5$, and never come closer. The convergents of $\sqrt2$ settle at $0.3536$, which is $1/\sqrt8$. The third number, whose continued fraction is $[2; 2, 1, 1, 2, 2, 1, 1, \ldots]$, settles at $0.3364$, which is $5/\sqrt{221}$. And $e$, whose continued fraction contains every even number as a term, has convergents that dip lower each time a large term arrives — $0.077$ already at a denominator below a million — and would go on dipping for ever. Most numbers behave like $e$, in the sense that almost every number has unbounded terms; how close a fraction can get used the pigeonhole principle to show every irrational can be approached within $1/q^2$, and the numbers that cannot be approached within much less are rare and special.

Why the golden ratio gives the square root of five #

The golden ratio’s constant can be computed exactly, because its convergents are ratios of Fibonacci numbers and the Fibonacci numbers satisfy an identity that measures the error. With $F_n$ the Fibonacci numbers and $\varphi = (1 + \sqrt5)/2$,

$$\left|\varphi - \frac{F_{n+1}}{F_n}\right| = \frac{1}{F_n\,(F_n\varphi + F_{n-1})},$$

so the scaled error $F_n^2\,|\varphi - F_{n+1}/F_n|$ is $1/(\varphi + F_{n-1}/F_n)$, and as $F_{n-1}/F_n$ approaches $1/\varphi$ it approaches $1/(\varphi + 1/\varphi) = 1/\sqrt5$. The figure’s measured $0.4472$ is that limit. The reason it is the worst possible is visible in the formula: the denominator is $\varphi$ plus the ratio of the previous two Fibonacci numbers, and for any other number the corresponding quantity is a term of the continued fraction plus two tails, which some term will make larger than $\sqrt5$ unless every term is one. The terms are what the diagonal no unit measures found by subtracting a pentagon’s side from its diagonal again and again; all ones means that each subtraction leaves the smallest possible remainder, and that is the same as being approximable as badly as possible.

The same reasoning explains $e$. Its continued fraction has the term $2k$ at every third place, so at those places the denominator in the corresponding formula is about $2k$, the scaled error about $1/(2k)$, and the approximations get better without limit. Numbers whose terms grow very fast are approximated so well that they cannot be algebraic, which is how Liouville built the first known transcendental numbers, as approached too fast to be algebraic described; the Markov numbers sit at the opposite extreme, approximated as badly as anything can be.

Markov’s list #

The golden ratio and every number whose continued fraction ends in 1s forever share the Lagrange value $\sqrt5$. Remove them, and the next smallest value is $\sqrt8$, for $\sqrt2$ and the numbers ending in 2s. Remove those, and the next is $\sqrt{221}/5$. Markov proved that the values below 3 are exactly

$$\frac{\sqrt{9m^2 - 4}}{m}$$

for the numbers $m$ that appear in some solution of $x^2 + y^2 + z^2 = 3xyz$ in positive integers: $m = 1, 2, 5, 13, 29, 34, 89, 169, 194, 233, 433, \ldots$, now called Markov numbers. For $m = 1$ the formula gives $\sqrt5$; for $m = 2$, $\sqrt{32}/2 = \sqrt8$; for $m = 5$, $\sqrt{221}/5$.

As $m$ grows the values approach 3 from below, since $\sqrt{9m^2 - 4}/m = 3\sqrt{1 - 4/(9m^2)}$. So the spectrum below 3 is a discrete list accumulating only at 3: every value is isolated, with a gap round it in which no number’s Lagrange value falls. Above 3 the picture is completely different, and the next figure shows the change.

Markov’s route through quadratic forms #

Markov did not reach the list through continued fractions but through binary quadratic forms, expressions $f(x, y) = ax^2 + bxy + cy^2$ with whole-number coefficients, the objects counting the classes that break factorisation sorted by reduction. A form with positive discriminant $D = b^2 - 4ac$, not a square, factors over the reals as a product of two lines, and the slopes of those lines are quadratic irrationals. The question he asked was how small $|f(x, y)|$ can be made at whole-number points other than the origin, measured against $\sqrt D$.

For $x^2 - xy - y^2$, discriminant 5, the smallest nonzero value is 1, giving the ratio $\sqrt5/1$, and its lines have slopes $\varphi$ and $-1/\varphi$. For $x^2 - 2y^2$, discriminant 8 and smallest value 1, the ratio is $\sqrt8$ — this is the form of Pell’s equation for 2, whose solutions sixty needs two digits and sixty-one ten studied. Markov’s theorem says that the forms whose ratio is below 3 are, up to equivalence, exactly one for each Markov number $m$, with ratio $\sqrt{9m^2 - 4}/m$, and that the coefficients of these forms can be written down from the Markov triples. The approximation constant of a number and the minimum of a form are two readings of one quantity, because a fraction $p/q$ close to a slope of the form’s lines makes $f(p, q)$ small.

The change at 3 #

Perron’s formula can be applied to every number whose continued fraction repeats a fixed block, and the next figure applies it to all of them with blocks of 1s, 2s and 3s up to length ten — 9,503 distinct repeating patterns, counting rotations of a block as the same.

Below 3 the 9,503 patterns produce only eleven distinct values, and every one of them is $\sqrt{9m^2 - 4}/m$ for a Markov number $m$: thirty patterns land there, all on Markov values, and no pattern lands between them. Above 3 the values crowd into bands separated by gaps, the gaps narrowing as the values rise; beyond about $4.53$ there are none at all. Marshall Hall proved in 1947 that the spectrum contains a whole half-line from some point on, and Gregory Freiman found in 1975 that the half-line begins exactly at $4.5278\ldots$, now called Freiman’s constant. Between 3 and Freiman’s constant the spectrum is a complicated set, with gaps and pieces of positive length, whose fine structure was only recently described: Carlos Gustavo Moreira and, with Carlos Matheus, later work showed that the part of the spectrum below a level $t$ just above 3 has a fractal dimension that rises continuously from nought at 3 and reaches one a little above $3.33$.

So the first part of the spectrum is arithmetic and discrete, and it ends exactly where the equation’s solutions crowd. Above 3, the spectrum is the continuum of analysis.

The tree of solutions #

The equation $x^2 + y^2 + z^2 = 3xyz$ is quadratic in each variable separately, and that is what makes its solutions a tree. Fix $x$ and $y$; then $z$ satisfies $z^2 - 3xy\,z + (x^2 + y^2) = 0$, whose two roots add to $3xy$. So from any solution $(x, y, z)$ a new one is $(x, y, 3xy - z)$, the other root. Starting from $(1, 1, 1)$ and applying this move to each coordinate in turn generates every solution, and after the first two, $(1, 1, 1)$ and $(1, 1, 2)$, each triple has exactly two children that are larger, as the hero figure draws: $(1, 2, 5)$ has $(1, 5, 13)$ and $(2, 5, 29)$, which have $(1, 13, 34)$, $(5, 13, 194)$, $(2, 29, 169)$ and $(5, 29, 433)$.

The move that builds the tree, replacing a root of a quadratic by its partner, is known to competition mathematicians as Vieta jumping, after the relation between a quadratic’s roots and its coefficients. Run backwards it is a descent: from any solution, replacing the largest coordinate by the other root gives a smaller solution, and repeating must end, since positive integers cannot decrease for ever. The only place it can end is $(1, 1, 1)$, which is the proof that the tree contains every solution — there is no second tree of solutions hiding somewhere, because every solution descends to the same root. The tree grows quickly in value but its branching is slow, and the Markov numbers are sparse. Walking it in exact arithmetic to a largest member of $10^{30}$ finds 893 triples, against Don Zagier’s 1982 asymptotic count of about $0.1807(\ln 3x)^2$ Markov numbers up to $x$, which predicts 890. The count grows like the square of the logarithm: there are only about two hundred Markov numbers below $10^{15}$, and a little under four times that many below $10^{30}$ — doubling the number of digits roughly quadruples the count, because each step down the tree roughly multiplies the size of the largest entry, so the depth of the tree grows like the logarithm and the number of branches at a given size like its square.

Blocks of 1, 1 and 2, 2 #

The numbers with these Lagrange values are quadratic irrationals, and their continued fractions have a structure of their own.

The search behind the figure tries every block of 1s and 2s up to fourteen long and finds, for each of the first nine Markov numbers, the shortest that produces its value. Apart from $m = 1$, all ones, and $m = 2$, all twos, every block is built from pairs: $2211$ for $m = 5$, $221111$ for $13$, $222211$ for $29$, $22111111$ for $34$, and $2211221111$ for $194$. The pairs are arranged in a pattern that is the cutting word of a straight line, the balanced arrangement the word a straight line spells found in the bounces of a billiard ball — Harvey Cohn and later Enrico Bombieri made the correspondence precise, matching each Markov triple to a word in two letters built like the Christoffel words of a line’s slope.

The same words have appeared in an unrelated place: the fraction written on every bulb found the Mandelbrot set’s bulbs, and their external rays, labelled by the cutting words of straight lines. Balanced words turn up wherever a rotation is being encoded in two symbols, and a Markov number’s continued fraction is, in a precise sense, a rotation by an angle that the tree’s branch encodes.

One triple for each number #

The hero figure’s tree contains each Markov number many times — 5 appears in $(1, 2, 5)$, $(1, 5, 13)$, $(2, 5, 29)$ and every triple below — but as the largest member of a triple each number appears, so far, exactly once.

Georg Frobenius conjectured in 1913 that this always holds: every Markov number is the largest member of exactly one Markov triple. If true, each value $\sqrt{9m^2 - 4}/m$ in the spectrum belongs to a single number up to the obvious equivalences, and the bottom of the spectrum is labelled one-to-one by the tree. The conjecture has been checked for every Markov number below $10^{30}$ here and far beyond in published searches, and proved for Markov numbers that are primes or prime powers, and for some other families; in general it is open, more than a century after it was stated.

What the figures cannot show #

The computations confirm Markov’s theorem only where they reach. The spectrum figure lists the Markov values; it does not show that nothing else lies below 3. The periodic-pattern figure shows that among 9,503 numbers with repeating blocks, none falls below 3 except at a Markov value, which is strong evidence and a small part of the theorem: Markov’s statement covers every irrational, not just those with periodic continued fractions, and the proof that nothing else can be worse approximable than 3 needs an argument about arbitrary sequences of terms, which Markov gave through the theory of binary quadratic forms. Nor do the figures show the uniqueness conjecture beyond the bound reached.

The figures also simplify the geometry. The Lagrange spectrum has a twin, the Markov spectrum, defined through the minima of binary quadratic forms rather than through approximation, and the two agree below 3 and differ above it — Freiman showed in 1968 that the Markov spectrum is strictly larger. The pictures here are all of the Lagrange spectrum, computed through continued fractions.

Still open: one triple per number #

Frobenius’s conjecture is the central open question, and it has resisted a century of attempts because it asks for a property of a recursively defined set of integers that has no obvious algebraic handle. The known partial results go through the arithmetic of the Markov number itself: when $m$ is a prime power, the triple is determined by a square root of $-1$ modulo $m$, and there is only one suitable root. When $m$ has several prime factors there are several square roots and the argument fails. Reformulations connect the conjecture to the combinatorics of Christoffel words, to the geometry of the punctured torus — where Markov triples correspond to simple closed geodesics and the conjecture says that geodesics of the same length are related by a symmetry — and to the representation theory of certain algebras, and none has yet produced a proof.

There is a second, quantitative question. Zagier’s count is an asymptotic formula with a constant, and the error in it — the figure finds 893 against 890 at $10^{30}$ — is not known to be smaller than any particular power of the main term.

A list below 3 #

The golden ratio is the worst-approximable number, and the theorem that says so has a second sentence, and a third, and an infinite list of them. Each sentence names a number — $\sqrt2$, then the number whose continued fraction repeats 2, 2, 1, 1, then one repeating 2, 2, 1, 1, 1, 1 — and a constant, $\sqrt8$, $\sqrt{221}/5$, $\sqrt{1517}/13$, and the constants climb towards 3 without reaching it. The list is indexed by the solutions of a single Diophantine equation, which form a tree in which each solution has two children, and the indexing is one-to-one for every case anybody has checked. Above 3 the list dissolves into the continuum, and the golden ratio, the first entry, is no longer special: it is simply where the arithmetic of approximation is most extreme, at the bottom of a spectrum whose lower end is a theorem of 1879 and whose labelling is still a conjecture.