How evenly the fractions spread

Every fraction, exactly once built the rationals by mediants, and one of the things it produced along the way was the Farey sequence: every fraction between nought and one whose denominator is at most $n$, reduced, in increasing order. For $n = 5$ it is $\tfrac15, \tfrac14, \tfrac13, \tfrac25, \tfrac12, \tfrac35, \tfrac23, \tfrac34, \tfrac45, \tfrac11$. Neighbours in it have the property the Stern–Brocot tree is built on — $bc - ad = 1$ for consecutive $\tfrac ab < \tfrac cd$ — and every later essay on the tree has used that property.

This essay asks a question the tree cannot see, because it is about all the fractions of one order at once: how evenly do they spread? There are $N$ of them in the interval, so if they were perfectly even the $k$-th would sit at $k/N$. The figure below draws the forty-six fractions of order twelve beside forty-six evenly spaced points, and the bar under each is its misfit.

The fractions are nearly even. The misfits are largest near the ends, where fractions are sparse — the smallest is $\tfrac1{12}$, nowhere near $\tfrac1{46}$ — and they change sign around the simple fractions in the middle. That picture has a remarkable property. How fast the total misfit shrinks as the order grows is not just related to the Riemann hypothesis, the most famous open problem in mathematics; it is equivalent to it. Jérôme Franel and Edmund Landau proved as much in 1924.

How many fractions there are #

Before the unevenness, the count. A fraction $a/b$ with $b \le n$ is in the Farey sequence exactly when it is in lowest terms, so the fractions with denominator $b$ number $\varphi(b)$ — the count of numerators below $b$ sharing no factor with it. The Farey sequence of order $n$ therefore has $\varphi(1) + \varphi(2) + \cdots + \varphi(n)$ terms.

The count grows like $3n^2/\pi^2$, and π turns up for a reason with nothing circular about it. Of all pairs $(a, b)$ with $b \le n$, about half have $a < b$, and a pair gives a reduced fraction when $a$ and $b$ share no prime factor. For each prime $p$, the chance that both are divisible by $p$ is $1/p^2$, so the chance that they share none is the product over primes of $1 - 1/p^2$, which is $1/\zeta(2) = 6/\pi^2$. Half of $n^2$ pairs, times $6/\pi^2$, is $3n^2/\pi^2$. The zeta function has entered the counting of fractions already, through its value at two; the Riemann hypothesis concerns where it vanishes, and the rest of this essay is about how that too is written into the fractions.

Franel’s sum #

The total misfit is the sum of the bars’ lengths, $\sum_k |f_k - k/N|$, where $f_k$ is the $k$-th Farey fraction.

At order five the sum can be done by hand. The ten fractions $\tfrac15, \tfrac14, \tfrac13, \tfrac25, \tfrac12, \tfrac35, \tfrac23, \tfrac34, \tfrac45, \tfrac11$ are compared with $0.1, 0.2, \ldots, 1.0$, and the misfits are $0.1$, $0.05$, $0.033$, three noughts, then $-0.033$, $-0.05$, $-0.1$ and a final nought. They are symmetric — the Farey sequence is its own mirror image about one half — and they total $0.367$. Everything about the sum is visible already: large near the ends, nought in the middle stretch, and changing sign across the hole around $\tfrac12$.

As the order doubles, the number of fractions roughly quadruples and each misfit shrinks, and the total grows — at the rate of $\sqrt n$, since the points on the log–log plot lie on a line of slope close to one half. Franel’s theorem says exactly what that slope is worth. The Riemann hypothesis is true if and only if the total misfit grows no faster than $n^{1/2 + \varepsilon}$ for every $\varepsilon > 0$. A slope of one half, continued for ever, is the hypothesis; a slope that ever crept above one half, by any amount, at any scale, would refute it.

The figure shows the slope over orders up to 1,280, where the Farey sequence has about half a million terms. It says nothing about orders beyond that, and the hypothesis is a claim about all of them. But it shows the shape of the claim: an entirely elementary quantity, the unevenness of a list of fractions, measured with a ruler.

Landau’s sum #

Landau gave a second version, with squares in place of absolute values.

Squaring the misfits weights the large ones, near the ends and around the simple fractions, more heavily. The sum of squares shrinks roughly like $1/n$, and Landau’s form of the equivalence is that the Riemann hypothesis holds exactly when this sum is at most $n^{-1+\varepsilon}$ for every $\varepsilon$ — when the product in the figure grows more slowly than any power of $n$. It wanders, and stays below one throughout the range drawn.

The two forms say the same thing in different norms. What neither says is why unevenness of fractions should know about the zeros of a function of a complex variable. For that, a circle.

Holes around the simple fractions #

The bars in the hero change sign around $\tfrac12$ and $\tfrac13$, and the reason is a gap that the Stern–Brocot tree explains exactly.

Next to $\tfrac12$ in the Farey sequence of order $n$ sit the fractions whose mediant construction reaches it first: $\tfrac{k}{2k+1}$ and $\tfrac{k+1}{2k+1}$ with $2k + 1 \le n$. Their distance from $\tfrac12$ is $\tfrac1{2(2k+1)}$, about $\tfrac1{2n}$. In general the nearest neighbours of $a/b$ are at distance about $1/(bn)$ — the neighbour property, $bc - ad = 1$, fixes it — while the average gap between Farey fractions is $1/N$, about $\pi^2/(3n^2)$. So around every fraction with a small denominator there is a hole about $n/b$ times wider than an average gap. The fractions with small denominators repel their neighbours, and the simplest fractions repel them most.

That is why the misfits change sign there. Approaching $\tfrac12$ from below, the fractions crowd up against the hole and fall behind even spacing; the hole itself is a jump, and past it the fractions are ahead. The largest holes of all are around $\tfrac01$ and $\tfrac11$, the simplest fractions there are, which is why the bars are longest at the ends. The same holes are where good approximations live: a number just inside the hole around $a/b$ is approximated by $a/b$ better than by any fraction with a denominator up to $n$.

Proved without the hypothesis #

Not everything about the evenness waits on the Riemann hypothesis. The Farey fractions do become evenly spread as the order grows — the total misfit, divided by the number of fractions, tends to nought — and that is a theorem.

The Mertens function gives the measure of how much is known. Edmund Landau showed in 1899 that $M(x)/x \to 0$ is equivalent to the prime number theorem, the statement that the primes up to $x$ number about $x/\log x$. Through the circle identity, that is a statement that the Farey arrows cancel to a smaller and smaller fraction of their number. The prime number theorem was proved in 1896, so this much evenness is certain. The Riemann hypothesis is the claim that the cancellation is as good as a coin’s — to within the square root — and every improvement in what is known about the zeros of $\zeta$ has been reflected as a slightly better bound on $M(x)$, none of them anywhere near $\sqrt x$.

Even at one level, uneven at another #

Minkowski’s question-mark function shows the opposite behaviour in the same fractions. The function that sends fractions to binary matches the Stern–Brocot tree’s fractions to the dyadic fractions level by level, and it turned out to be singular: its rise happens on a set of length nought, because the tree places its fractions very unevenly — the mediants of a level crowd toward the simple fractions of the level above.

That is not a contradiction. The Stern–Brocot tree lists fractions by how many mediant steps they take to reach, and the fractions reached in $k$ steps have denominators ranging from $k + 1$ up to Fibonacci numbers — wildly different sizes, bunched unevenly. The Farey sequence lists them by the size of the denominator, and fractions of bounded denominator are nearly even. The same set of numbers is uneven when ordered by construction depth and even when ordered by size of denominator. Which evenness a question sees depends on which list it counts along, and the Riemann hypothesis is about the second.

Farey, Haros and Cauchy #

John Farey was a geologist, and in 1816 he sent a short letter to the Philosophical Magazine observing that in these lists every fraction is the mediant of its neighbours. He did not prove it. Augustin-Louis Cauchy read the letter and proved it the same year, and the lists have carried Farey’s name since, although Charles Haros had published both the lists and the property in 1802, as a way of building tables of fractions for converting decimals.

The link with the zeta function came more than a century later. Franel’s and Landau’s papers appeared together in 1924, Franel’s giving the equivalence with the sum of absolute misfits and Landau’s, in the same issue, a sharper form with squares. Between Haros’s tables of fractions for practical arithmetic and the equivalence with the most famous open problem in mathematics, nothing about the lists changed. What changed was the question asked of them.

The fractions on a circle #

Place each Farey fraction $f$ on the unit circle at angle $2\pi f$, and add the points as arrows from the centre. Forty-six arrows, spread nearly evenly round the circle, nearly cancel. What is left over is not small and irregular. It is a whole number.

The leftover is $-2$ at order twelve, and at every order the figure checks it is the value of the Mertens function, $M(n) = \mu(1) + \mu(2) + \cdots + \mu(n)$, where $\mu(k)$ is $+1$ if $k$ is a product of an even number of distinct primes, $-1$ for an odd number, and $0$ if a prime divides it twice.

The reason is short. The fractions with denominator exactly $b$ are the $a/b$ with $a$ coprime to $b$, and their points on the circle are the primitive $b$-th roots of unity. The sum of the primitive $b$-th roots of unity is $\mu(b)$ — the sums of roots of unity that add to nothing do so unless $b$ has a special shape, and the exceptions are exactly what the Möbius function records. Adding over all denominators up to $n$ gives $M(n)$.

That is the surprising connection this essay turns on. How evenly the Farey fractions spread round a circle is the same question as how evenly the Möbius function balances its values $+1$ and $-1$, and the second question is the Riemann hypothesis in its most arithmetical form.

The Mertens function #

The Möbius function looks like a coin toss: square-free numbers with an even number of prime factors are about as common as those with an odd number, and they alternate with no evident pattern.

If the values were independent coin tosses, their running sum would wander about as far as $\sqrt x$, like a random walk. The Mertens function does wander like that, as far as it has been computed. John Littlewood proved in 1912 that the Riemann hypothesis is equivalent to $M(x) = O(x^{1/2+\varepsilon})$ for every $\varepsilon$ — the Möbius function behaving, in the size of its running sum, like a fair coin.

In 1897 Franz Mertens conjectured more: that $|M(x)| < \sqrt x$ for every $x > 1$, which is what the figure shows as far as it goes. That stronger statement is false. Andrew Odlyzko and Herman te Riele proved in 1985 that $|M(x)|/\sqrt x$ exceeds $1.06$ for some $x$, using the zeros of the zeta function; nobody knows any such $x$ explicitly, only that the first is below $e^{1.59 \times 10^{40}}$, a number with more digits than there are particles in the observable universe. The picture of a function staying inside $\pm\sqrt x$ is true for every $x$ anyone could ever draw and false in the end — which is exactly why a figure cannot be evidence for the Riemann hypothesis, only an illustration of what it says.

Why a list of fractions knows about zeros #

The chain from Franel’s sum to the zeros of $\zeta$ has three links, and each is a genuine theorem.

The first is the circle identity above, and its refinements: the Farey fractions’ misfits can be written, by Fourier analysis on the interval, as sums of exponentials $e^{2\pi i m f}$ over the fractions, and each such sum is a sum of Mertens-like functions with Möbius weights. So bounds on the Mertens function give bounds on the misfits, and a clever converse gives the reverse.

The second is that the Mertens function’s growth is controlled by the zeros of $\zeta$: the Dirichlet series $\sum \mu(k)/k^s$ equals $1/\zeta(s)$, and the growth of the partial sums of its coefficients is governed by how far to the right the poles of $1/\zeta$ — the zeros of $\zeta$ — can lie. If every non-trivial zero has real part one half, the sums grow like $x^{1/2}$ up to small factors; a zero with real part $\sigma > 1/2$ would make them grow like $x^\sigma$.

The third is the Riemann hypothesis itself: that every non-trivial zero has real part exactly one half. So the list of fractions the tree builds, the counting function of the primes, and the random-looking signs of the Möbius function are three faces of one question.

What the measurements cannot say #

Every quantity in these figures is computed exactly or to many digits: the Farey sequences by the next-term rule, checked neighbour by neighbour; the circle sums checked against the integer Mertens function; the Möbius function by a sieve. The measurements are sound. What they measure is the behaviour up to orders of a thousand or so and arguments of twenty thousand, and the equivalences are statements about behaviour for ever.

The Mertens conjecture is the warning. A bound that holds in every computed range and fails beyond it is not a hypothetical danger in this subject; it is the documented history of the Möbius function. A slope of one half on the Franel plot is consistent with the Riemann hypothesis; a slope of $0.5001$ that set in only at orders with a billion digits would refute it and look identical on any drawable scale.

Still open: the Riemann hypothesis, as an evenness #

Whether the Farey fractions of order $n$ misfit even spacing by a total of at most $n^{1/2+\varepsilon}$, for every $\varepsilon > 0$ and every large $n$, is not known, and by Franel’s theorem it is the Riemann hypothesis. It has been checked in the sense that the first ten trillion zeros of the zeta function have been computed and all have real part one half; it has not been proved.

The Mertens function has other disguises of the same kind. Ray Redheffer noticed in 1977 that the $n \times n$ matrix of noughts and ones with a one wherever the row number divides the column number, and a column of ones down the left, has determinant exactly $M(n)$. So the Riemann hypothesis is also a statement about how large the determinant of a very simple matrix of zeros and ones can be — no larger than $n^{1/2+\varepsilon}$ — and its eigenvalues have been studied for exactly that reason. None of these reformulations has made the problem easier; each has made it visible from somewhere new.

What makes this form of the question worth stating is how little it needs. No complex analysis, no analytic continuation, no infinite series: a list of fractions with bounded denominators, in order, compared with a list of evenly spaced points. Anyone who can reduce a fraction can compute every term of Franel’s sum. The difficulty is entirely in the “for every $n$”.