A small quotient for every denominator

Every fraction, exactly once built the Stern–Brocot tree, in which every positive fraction appears once and the path from the root to it is a sequence of left and right turns. The arcs a line crosses on its way to a number read that path as a continued fraction: the lengths of the runs of turns in one direction are the quotients $a_1, a_2, \ldots$ in $p/q = [0; a_1, a_2, \ldots, a_n]$. A fraction with small quotients is one whose path keeps changing direction, and that essay recorded, as an open question, a conjecture of Stanisław Zaremba: every whole number $q$ is the denominator of some fraction $p/q$, in lowest terms, whose quotients are all at most 5.

This essay checks the conjecture for every denominator up to a hundred thousand, measures what makes it plausible, and explains why it is a question about sampling.

Listing the fractions that keep turning #

Testing a denominator directly means trying every numerator and expanding each fraction, which is slow. The figures go the other way: they list every fraction whose quotients are bounded and record the denominators that appear. A continued fraction $[0; a_1, \ldots, a_n]$ has denominator given by the recurrence

$$q_k = a_k\, q_{k-1} + q_{k-2},$$

starting from $q_0 = 1$ and $q_{-1} = 0$, so a walk that chooses each $a_k$ from $1$ to $A$ and stops when the denominator exceeds the limit visits every bounded fraction exactly once — provided the last quotient is taken to be at least 2, since $[\ldots, a, 1]$ and $[\ldots, a + 1]$ are the same fraction and the second form is the one whose largest quotient counts. The walk is a depth-first search of the Stern–Brocot tree that never runs more than $A$ steps the same way.

With $A = 5$ and denominators up to a hundred thousand, the walk visits about a quarter of a billion fractions and finishes in a few seconds. Every denominator up to a hundred thousand is hit. For denominators up to 3,000 the hero figure shows the smallest bound each one needs: most need only 2 or 3; thirty-two need 4; three — 6, 54 and 150 — need 5.

The smallest case is easy to check by hand. The fractions with denominator 6 in lowest terms are $\tfrac16 = [0; 6]$ and $\tfrac56 = [0; 1, 5]$, so the best bound for 6 is 5. For 54 and 150 the same holds by longer arithmetic, and those are the only denominators up to a hundred thousand that need 5.

Which bounds miss which denominators #

The conjecture is sharp in the sense that 5 cannot be replaced by 4, since 6 needs 5; the question is how much worse the smaller bounds do.

With quotients at most 2, more than half of all denominators are missed — 52,950 of the first hundred thousand — and the count grows in proportion to $Q$. With quotients at most 3, only 38 denominators are missed, and none larger than 6,234: the list stops growing well before the search ends. With at most 4, only 6, 54 and 150. With at most 5, none. The figure suggests a pattern that is believed and not proved: that for 3 and 4 the exceptions are finite lists, all found, and that for 5 there are none at all. The jump from 2 to 3 is sharp, and it has a reason, which the dimension of the next section supplies.

The exceptions, close up #

The three denominators that need 5 are worth looking at. The best fractions with denominator 54 are $\tfrac{17}{54} = [0; 3, 5, 1, 2]$ and its relatives $\tfrac{19}{54} = [0; 2, 1, 5, 3]$, $\tfrac{35}{54}$ and $\tfrac{37}{54}$, each with a single quotient of 5 and nothing larger; no fraction with denominator 54 avoids a 5. For 150 the best include $\tfrac{29}{150} = [0; 5, 5, 1, 4]$ and $\tfrac{47}{150} = [0; 3, 5, 4, 2]$. The fractions come in groups of four because of two symmetries of the problem: $p/q$ and $(q - p)/q$ have essentially the same quotients, and so do $p/q$ and $p'/q$ where $p p' \equiv \pm 1$ modulo $q$, which reverses the order of the quotients. Any denominator’s good fractions are closed under both.

The longer list of exceptions for the bound 3 has a visible bias. Of its 38 members, all but one are even — the exception is $1155 = 3 \cdot 5 \cdot 7 \cdot 11$ — and 26 are divisible by 3. Denominators with many small prime factors have fewer fractions in lowest terms to choose from, since every numerator sharing a factor with $q$ is excluded, and the exceptions are concentrated among them. That is the kind of arithmetic bias a pure counting argument ignores and a proof has to handle: the surplus of bounded fractions is an average over all denominators, and denominators with many small factors receive less than their share.

Why there should be enough: a dimension #

The reals between nought and one whose continued fraction quotients are all at most $A$ form a Cantor-like set $E_A$: the golden ratio’s reciprocal is in every one of them, and most numbers are in none. These sets have Hausdorff dimensions, the measure of fractal size that a dimension that is not a whole number introduced, and they have been computed to many places by Oliver Jenkinson and Mark Pollicott: $\delta_2 = 0.5313$, $\delta_3 = 0.7057$, $\delta_4 = 0.7889$, $\delta_5 = 0.8368$.

The dimension controls how many bounded fractions there are. The number of fractions with quotients at most $A$ and denominator at most $Q$ grows like $Q^{2\delta_A}$, and the figure measures that growth directly from the walk.

The measured exponents — 1.072, 1.412, 1.578 and 1.674 at the largest $Q$ — agree with $2\delta_A$ to two or three decimal places. That makes the heuristic plain. There are $Q$ denominators up to $Q$ and about $Q^{2\delta_A}$ bounded fractions to share among them. If $2\delta_A$ is barely above 1, as for $A = 2$, there is about one fraction per denominator, and many denominators get none. If $2\delta_A$ is well above 1, each denominator gets on average about $Q^{2\delta_A - 1}$ fractions, a growing number, and it would take a conspiracy for any particular denominator to get none. For $A = 5$ the average is $Q^{0.674}$, which at $Q = 100{,}000$ is in the thousands.

The counts grow with an exponent of 0.62 over the range measured, approaching the limiting $0.674$ slowly from below, and they are remarkably steady: no denominator above a thousand has fewer than 29 good fractions. The conjecture is that this steadiness never fails.

Why five, and not four #

The heuristic does not single out 5. For the bound 4 the surplus is already large — the average number of good fractions grows like $q^{2\delta_4 - 1} = q^{0.578}$ — and the counting argument would predict that every large denominator is covered by fractions with quotients at most 4. The search agrees: past 150, none is missed. The 5 in Zaremba’s conjecture is forced by three small denominators, 6, 54 and 150, not by anything about large ones; it is the smallest bound that works for every $q$ including the small, and a statement about all large $q$ would take 4, or by the same reasoning 3, past 6,234.

The bound 2 is the opposite case. Its surplus is so thin — the average number of good fractions grows like $q^{0.063}$, which is about two at a hundred thousand — that a large share of denominators get none by chance alone, and the counting heuristic itself predicts that misses never stop. The dimension $\delta_2 = 0.531$ is above a half, so in the limit the surplus does grow, but at a rate no computation could see. Between 2 and 3 the dimension jumps from 0.53 to 0.71, and that jump is the jump in the figure of misses.

Rare, and never absent #

From the point of view of a single denominator, good fractions are a vanishing minority.

For a prime denominator near 94,000, about one fraction in twenty-nine has all its quotients at most 5, and the share keeps falling, roughly like $q^{2\delta - 2}$, because the bounded fractions form a set of dimension less than one inside an interval of dimension one. A fraction picked at random almost always has some large quotient. Zaremba’s conjecture is the statement that the vanishing minority never vanishes completely: a thinning set that, at every denominator, still has members.

That combination — rare in proportion, plentiful in number — is what makes the problem hard. A counting argument shows the average is large; it cannot show the minimum is positive, because a positive average is compatible with zeros scattered among the denominators. The proofs that exist control how the good fractions are distributed among the residues of $q$, which is where zeros could hide.

What is proved #

Harald Niederreiter proved in 1986 that the conjecture holds for every power of 2, 3 and 5, by an explicit construction that builds good fractions for $q$ from good fractions for a smaller power. Jean Bourgain and Alex Kontorovich proved in 2014 that it holds for almost every denominator — all but a set of density nought — with the bound 50 in place of 5, using the surplus of fractions measured above together with deep results on how evenly a group generated by the matrices of two matrices that generate the tree spreads its elements among residues. ShinnYih Huang brought the bound down to 5 for almost every $q$ in 2015. Since then the exceptional set has been shown to be smaller and smaller, but not empty.

The matrices are the bridge between the counting and the arithmetic. A bounded continued fraction corresponds to a product of matrices $\begin{pmatrix} a & 1 \\ 1 & 0 \end{pmatrix}$ with $a \le A$, and the denominator is an entry of the product. Asking whether every $q$ is an entry of some such product is asking how completely a semigroup of matrices covers the whole numbers, and the methods that answer it are those of expanders and the spectral theory of thin groups — subjects that grew up long after Zaremba asked his question.

Where the question came from #

Zaremba asked it because of a problem in numerical integration that points on a lattice that see almost nothing described. To integrate a smooth periodic function over the unit square, one can sample it at the $q$ points $(k/q, \{kp/q\})$ for $k = 0, \ldots, q - 1$: a lattice rule. How well the rule works depends on how evenly the points spread, and in two dimensions the points spread well exactly when $p/q$ has small continued-fraction quotients, since a large quotient means the points line up along a few lines with large gaps between them. A good lattice rule with $q$ points exists for every $q$ if and only if every $q$ has a good $p$ — which is Zaremba’s conjecture, with “good” made precise by the bound on quotients.

The same evenness appeared in three gaps and no more, where the points $\{k\alpha\}$ for irrational $\alpha$ leave at most three different gap lengths, with the gaps most even when $\alpha$’s quotients are small — the golden ratio, all of whose quotients are 1, being the best of all. A rational $p/q$ with small quotients is the finite version of that: its multiples spread around the circle as evenly as $q$ points can, and Zaremba’s conjecture says such a spreading exists for every number of points.

Depth in the tree #

The Stern–Brocot tree gives a second way to see what bounded quotients cost. A fraction’s depth in the tree — the number of turns on its path from the root — is the sum of its quotients, $a_1 + a_2 + \cdots + a_n$ less one. A fraction with denominator $q$ and all quotients small has many quotients, about $\log q$ of them divided by the logarithm of their typical size, and so it sits deep in the tree; a fraction with one huge quotient sits shallow, reached by a long straight run. The denominator alone does not decide the depth. The fractions $\tfrac{1}{q}$ and $\tfrac{q-1}{q}$ are reached by a single straight run of length $q$, the deepest possible, while the bounded fractions with the same denominator are reached in a few dozen turns.

The fractions that beat every smaller one found that the best rational approximations to a number are the stopping points of its path, and every rational in one sequence listed the tree level by level. In those terms Zaremba’s conjecture says that every level of the tree’s denominators — every $q$ — is reached by some path that never runs straight for long, and the computations here say that for $q$ up to a hundred thousand the shortest such path, measured by its longest straight run, never needs a run of six.

A path that never runs long #

The figure below shows what a good fraction’s path looks like for one large prime.

For the prime 9,973 the best fraction is $7216/9973 = [0; 1, 2, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2]$, with no quotient larger than 2 — far better than the conjecture asks. Its path zigzags down the tree, never running more than two steps the same way, which is as close to the golden ratio’s perfect alternation as a fraction with this denominator gets. Most of the other 9,971 fractions with denominator 9,973 have paths with long straight runs, and they are the ones a random choice of numerator would produce.

What the search does and does not show #

The search is exhaustive up to a hundred thousand: every bounded fraction with denominator in range is visited, and every denominator is checked. The walk itself is cheap because it never wastes a step: each move appends one quotient and computes one new denominator, and the walk abandons a branch the moment the denominator passes the limit, so the work is proportional to the number of bounded fractions, about a quarter of a billion for the bound 5. Checking each denominator separately, by expanding all of its fractions, would cost about half the square of the range instead, five billion expansions for the same answer, and the comparison is a small instance of the subject’s general habit of counting the objects that exist rather than testing every candidate. That establishes the conjecture up to a hundred thousand, which is a small range — computer searches have checked it far beyond, and the result is unconditional only up to their limit. It also establishes, for these sizes, the lists of exceptions for the bounds 3 and 4. It does not establish that those lists are complete. For 3, the last exception found is 6,234, and nothing between there and a hundred thousand, but a denominator in the billions could still fail; the counting heuristic says this is very unlikely, because the average number of good fractions grows like $q^{0.41}$, and the theorem that would make it certain does not exist.

The dimensions used in the comparisons are taken from the literature rather than computed here; what the figures compute is the growth exponent of the counts, which agrees with them.

Still open: every denominator #

Zaremba’s conjecture is open: no proof covers every denominator, even with a bound larger than 5. What is proved is that the exceptions, for the bound 5, have density nought, and quantitative versions bound how many there can be up to $Q$ by a power of $Q$ less than one. Closing the gap requires controlling every single denominator, which means ruling out conspiracies among residues that the averaging methods are blind to. A stronger form, that the bound 4 works for every denominator beyond 150, and the bound 3 for every denominator beyond 6,234, is suggested by the computations and was proposed by researchers who ran them; it is further out of reach still, since the surplus of fractions for those bounds is smaller.