The fractions that beat every smaller one

The tree contains every positive fraction, so it contains every fraction near any given number. Walking down it towards a target — left when the current node is too big, right when it is too small — produces a sequence of fractions closing in.

Most of them are unremarkable. A few are the best there are.

What a record is, and how it is checked #

A fraction $\tfrac{p}{q}$ is a best approximation to $x$ when no fraction with a denominator below $q$ is closer. That is a claim about every smaller denominator, and the figures establish it the only honest way: by trying them.

For each fraction on the path, every $q' < q$ is taken in turn, the nearest numerator to $x q'$ is computed, and the resulting distance compared. If none beats the candidate, it is a record.

That is $O(q)$ work per fraction and the denominators grow quickly, so the check is the expensive part of the figure and it is worth the cost. A drawing of a curve with some points marked “best” is indistinguishable from a drawing with the wrong points marked, and the only difference is whether the marking was computed.

Where the records are #

The records are not evenly spread. They sit at the ends of the runs of identical turns, and the reason is what the runs are.

The matrix reading says a run of $k$ identical turns is a single matrix $L^k$ or $R^k$, and that the run lengths are the continued fraction’s quotients. So the fractions at the ends of runs are exactly the convergents of the continued fraction, which are the classical best approximations.

Inside a run the fractions are the semiconvergents — obtained by taking part of a quotient rather than all of it. Some of those are records too, which is why thirteen of twenty-six are marked rather than the six or seven the convergents alone would give.

That distinction is the reason the figures check the records rather than assuming them. A semiconvergent may or may not beat everything smaller, depending on the quotients, and there is no way to tell without the comparison.

The rule, when it is written down, is a comparison of one quotient against a half. A semiconvergent obtained by taking $j$ of a quotient $a$ is a best approximation of the first kind when $j > a/2$, is not when $j < a/2$, and needs a further comparison when $j = a/2$ exactly. So a long run contributes about half its length in records — which is why $\pi$’s descent, with its quotient of $292$, produces a great many records in one stretch, and why the golden ratio’s, with every quotient one, produces one per turn.

The half is where the picture’s shape comes from. A run of turns is a stretch in which the denominator grows and the error falls slowly; the second half of that stretch is where the fractions start beating everything before them, and the first half is the tree passing through fractions that are on the way and not yet worth having.

Counting confirms it. Of $\pi$’s twenty-six drawn turns, thirteen are records — almost exactly half, which is what a mixture of runs each contributing half its length produces.

Two extremes #

The two figures above are the two ends of a spectrum and the spectrum is the whole subject.

The golden ratio has all quotients equal to one. Every run has length one, the descent alternates left and right, and the denominators grow as slowly as they can — like the Fibonacci numbers, which is the slowest growth any continued fraction produces. Slow denominator growth means the approximations are weak: the error at a given denominator is as large as it can be, and Hurwitz’s theorem says the constant cannot be improved for this number.

A number with a large quotient is approximated exceptionally well. $\pi$’s continued fraction is $[3; 7, 15, 1, 292, \ldots]$, and the $292$ is why $\tfrac{355}{113}$ is so good: a large quotient means a long run, and the fraction at the run’s start is very close to the target for its size. That one is out by $2.7 \times 10^{-7}$ with a three-digit denominator.

So the quotients measure how approximable a number is, and the descent’s shape shows it directly: a long run in the word is a long horizontal stretch in the picture where the denominator grows and the error barely moves, ending in a fraction that is much better than its size suggests.

That reading extends past irrationals in a way worth naming, because it is where the subject meets transcendence. A number whose quotients grow extremely fast is approximable extremely well — Liouville built the first numbers proved transcendental exactly that way, by choosing quotients large enough that the approximations beat any bound an algebraic number could satisfy. And Roth’s theorem is the other end: an algebraic irrational admits no approximation better than $1/q^{2+\varepsilon}$ for any positive $\varepsilon$, so its quotients cannot grow too fast.

The continued fraction is therefore a measurement of arithmetic nature, not merely of approximability. Approached too fast to be algebraic is that observation used as a proof technique, and the descent on this page is the picture of the quantity it measures.

$e$’s quotients grow, slowly and regularly, which is why $e$ is transcendental and why the pattern in its descent is visible; $\sqrt2$’s are constant, which is Lagrange’s theorem saying a continued fraction is eventually periodic exactly for the quadratic irrationals.

Why the descent finds them at all #

The descent looks like a search and it is not. At every step there is exactly one direction to go, determined by comparing the current node with the target, so nothing is being tried and rejected.

The reason it lands on the good fractions is the ordering. Each node’s two bounding fractions confine the target to an interval, and the mediant is the fraction with the smallest denominator in that interval — which is the property the rung below identified as the tree’s practical value. So the descent is, at every step, taking the simplest available fraction in the range still under consideration.

A procedure that always takes the simplest fraction in the current range cannot miss a best approximation, because a best approximation is simple by definition: nothing smaller is closer, so nothing smaller lies in the interval it would have to lie in.

That is the whole argument and it explains why the tree is the right object. A search through all fractions in order of denominator would find the same records and take exponentially longer.

There is a converse worth stating, because it is what makes the descent complete rather than merely productive. Every best approximation lies on the path. Suppose one did not: it would be a fraction closer to the target than everything smaller, sitting outside every interval the descent passed through — and the descent’s intervals shrink to the target, so at some step the fraction lies outside the current interval while the target lies inside. Both of its bounding fractions then have smaller denominators, one of them is at least as close, and the fraction was not a record after all.

So the descent misses nothing, and the sequence of records it produces is the complete list. That is the statement that turns the picture from an illustration into a method, and it is the reason the exhaustive check in the figures is a check on the implementation rather than a search for records the walk failed to find.

What it costs to find one #

The two ways of finding the best approximation with denominator below a bound differ enormously, and the difference is the reason anybody uses the tree.

By search, take every denominator up to the bound, compute the nearest numerator, and keep the best. That is one division per denominator, so a bound of a million costs a million operations and finding the record among denominators up to $10^{12}$ is out of reach.

By descent, take one step per turn, and the number of turns to reach a denominator of size $Q$ is at most about $\log Q$ divided by the logarithm of the golden ratio — because the denominators grow at least as fast as the Fibonacci numbers, which is the slowest they can grow. A bound of $10^{12}$ is about sixty turns.

Running the turns in runs makes it faster still. Each run is a single matrix with the run length in it, so a run of length $292$ is one operation rather than two hundred and ninety-two, and the cost becomes the number of quotients rather than of turns — which is the continued-fraction algorithm and is a handful of divisions.

So the three descriptions on this ladder are three costs for one answer: a search is linear in the bound, the tree walk is logarithmic, and the algorithm is logarithmic with a much smaller constant. The picture is the tree and the method is the algorithm, which is the division of labour the rung below already recorded and which the approximation question makes sharpest.

What the bound is #

Every record satisfies a bound and the bound is where the subject’s constants come from.

Dirichlet’s theorem guarantees infinitely many fractions with $|x - p/q| < 1/q^2$, for every irrational $x$, and a pigeonhole argument is the whole of its proof. The descent finds them: the figures check that at least three of the records satisfy it, and for a longer descent nearly all of them do.

Hurwitz’s theorem sharpens the constant: infinitely many with $|x - p/q| < 1/(\sqrt5\, q^2)$, and $\sqrt5$ cannot be replaced by anything larger — because the golden ratio does not admit it. That single number is the reason the golden ratio is called the most irrational number, and it is a statement about its continued fraction being all ones.

And the converse direction matters too. A fraction beating $1/(2q^2)$ is necessarily a convergent, so the very good approximations are all found by the descent and none is missed by it. That is Legendre’s theorem, and it closes the loop: the descent finds all the records, and everything unusually good is a record.

Where it needs care #

A best approximation is not the same as a convergent. Every convergent is one; some semiconvergents are too, and which depends on the quotients. There are two standard definitions — “of the first kind” comparing $|x - p/q|$ and “of the second kind” comparing $|qx - p|$ — and the convergents are exactly the second kind, while the figures compute the first.

The comparison is over denominators, not over fractions. A record beats everything with a smaller denominator and may be beaten by something with a larger one, which is why the records improve rather than terminate.

The arithmetic has a floor. The descent is computed in floating point and the error saturates around $10^{-16}$; the figures stop the descent before that, because past it two different fractions have the same computed distance and every comparison becomes a statement about rounding rather than about approximation.

And the exhaustive check is over the denominators below the candidate’s. That is the definition, and it makes the last few fractions of a long descent expensive to certify — the figures cap the descent’s length for that reason and say so.

Ties disqualify the later fraction. Two fractions equidistant from the target both look like records under a strict comparison, and the check marks only the first. That is a decision rather than a theorem: the second is equally good and is not better, and calling both records would break the statement that the records improve. It also removes an artefact — at fine scales the computed distances of two nearby fractions can coincide to the last bit, and a strict comparison then reports a record that is a fact about rounding.

What this ladder has been about #

Four rungs and one construction, and the four readings are worth putting side by side.

The mediant is an operation on pairs of counts, and it produces every fraction once and in lowest terms.

The matrices are that operation written so that its invariant is a determinant, and they identify the tree as a free monoid in $\mathrm{SL}(2,\mathbb{Z})$.

The sequence is the tree flattened by encoding the path in a binary index, and its terms count hyperbinary representations.

And the descent is the tree used for the purpose Brocot had — finding the simplest fraction that will do — which turns out to be the same as finding the best approximations there are.

Nothing was added between the rungs. Every one of them is the same tree looked at with a different question in hand, and the questions came from arithmetic, from algebra, from combinatorics and from a clockmaker’s workshop.

Where the practical version came from #

Brocot’s problem was gear ratios: a required ratio, a tolerance, and tooth counts that have to be small enough to cut. That is exactly “find the simplest fraction in an interval”, and the descent answers it by stopping as soon as the current node lands inside.

The approximation theory is older and came from elsewhere. Continued fractions were used by Huygens in the 1680s for the same reason — he was building a planetarium and needed gear ratios approximating the planets’ periods — and the convergents were understood as the good approximations long before anybody connected them to a tree.

Lagrange proved in 1770 that the convergents are the best approximations of the second kind, and the theory was essentially complete a century before Stern and Brocot wrote. The tree did not produce the approximation theory; it produced a picture of it, and the picture is what makes the semiconvergents visible as the fractions between the good ones rather than as an algebraic artefact.

That order — the theory first, the construction that displays it later — is worth noticing because it is the reverse of the usual telling, in which a construction is introduced and its properties derived.

What the pictures cannot show #

Each figure draws a descent of twenty-six or thirty turns, and the descent is infinite. The records go on forever and the drawn ones stop where the arithmetic does.

The check is over the denominators below each candidate’s, which for the largest drawn fraction is tens of thousands of comparisons. That is a complete check of the claim for the fractions drawn, and it is not a proof of any general statement — that the convergents are always best approximations is Lagrange’s theorem, quoted here.

And the picture cannot show what a record is competing against. The marked points are the winners and the field they beat is not drawn, because the field is every fraction with a smaller denominator and there are a great many.

The ladder from here #

Rungs above: the Markov spectrum, which classifies exactly how well each number can be approximated and whose smallest values are attained by the golden ratio and its relatives. Continued fractions of algebraic numbers, where Liouville’s and Roth’s theorems bound how well an algebraic number can be approximated and produce the first transcendental numbers. The Gauss–Kuzmin distribution, which says how often each quotient appears in a random number’s continued fraction. The three-distance theorem, which is what the same descent says about points on a circle. And the Minkowski question-mark function, which turns the descent’s word into a binary expansion and sends the quadratic irrationals to the rationals.

Simplest, and nearest, and the same answer #

The habit is about two questions that look different and are not.

Simplest in a range is a question about denominators: which fraction in this interval has the smallest one. Nearest with a bounded denominator is a question about distances: which fraction with denominator below $q$ is closest to this number.

They are the same question read from opposite ends. A fraction is a best approximation exactly when it is the simplest fraction in some interval around the target, and the interval is the one whose endpoints are the previous two records. So a procedure answering one answers the other, and the descent answers both because it is doing the only thing it can at each step.

The general shape is worth carrying: when two questions have the same answer, one of them usually has a procedure attached and the other has the theory. Here the simplicity question has the procedure — descend until inside — and the approximation question has the theorems, and the identification is what makes the theorems computable.