How close a fraction can get

Any number can be approximated by a fraction as closely as anybody likes, by taking enough decimal places. That observation is true and worthless: the fraction $\tfrac{31415926}{10000000}$ is not an approximation to $\pi$ so much as a restatement of it, and its denominator is doing all the work.

The question with content in it is about the exchange rate. Given a denominator of a certain size, how close can the best fraction get — and are there denominators that do unreasonably well?

The answer is Dirichlet’s, from 1842, and its proof is the pigeonhole principle applied once.

Before the argument, it is worth being clear about what a good answer would look like. A fraction $p/q$ approximating $\alpha$ has two numbers attached to it: how wrong it is, and how big its denominator is. Neither alone means anything — the error can be made as small as desired by enlarging the denominator, and the denominator can be kept small by accepting a bad answer. The question is entirely about the trade, and every result below is a statement about an exponent: the error behaves like $1/q$, or $1/q^2$, or $1/q^{2+\varepsilon}$, and which of those is achievable turns out to say a great deal about what kind of number $\alpha$ is.

The argument in full #

Take an irrational $\alpha$ and a whole number $N$. Consider the $N+1$ numbers

$$\{0\cdot\alpha\},\ \{1\cdot\alpha\},\ \{2\cdot\alpha\},\ \ldots,\ \{N\cdot\alpha\},$$

where $\{x\}$ is the fractional part. They all lie in $[0, 1)$. Cut that interval into $N$ boxes of width $1/N$. There are $N+1$ numbers and $N$ boxes, so two of them share a box.

Say $\{j\alpha\}$ and $\{k\alpha\}$ share, with $j < k$. Their difference is less than $1/N$ in size. Write $q = k - j$ and let $p$ be the whole number nearest $q\alpha$. Then

$$|q\alpha - p| < \frac{1}{N},$$

and dividing by $q$, which is at most $N$,

$$\left|\alpha - \frac{p}{q}\right| < \frac{1}{qN} \le \frac{1}{q^2}.$$

That is the theorem. Every irrational number has a fraction within $1/q^2$ of it — and since $N$ can be taken as large as anybody likes and $\alpha$ is irrational, so that no fraction is ever exactly right, there are infinitely many such fractions.

Why $1/q^2$ is the surprising part #

A bound of $1/q$ would be nothing at all. Every real number is within $1/2q$ of some fraction with denominator $q$ — round $q\alpha$ to the nearest whole number and divide — so a bound of that shape is available by construction and says nothing.

$1/q^2$ is a different kind of statement. It says the error is not merely small but small compared with the denominator, and by an amount that grows: doubling the denominator buys four times the accuracy rather than twice. Approximations like that are rare, and the pigeonhole argument proves infinitely many of them exist without exhibiting a single one.

The economy of the proof is worth dwelling on. It uses no property of $\alpha$ beyond irrationality: not its size, not how it is defined, not whether it is algebraic. It needs no calculation. And it produces its conclusion by counting boxes, which is the same move that makes more things than boxes a theorem about infinity rather than an observation about socks.

Which fractions the argument finds #

The proof says a good fraction exists, and refuses to say which. Running the search directly settles it.

The record-holders are the Fibonacci numbers, which for $\varphi$ is the same as saying they are the continued fraction convergents. That is not a coincidence about the golden ratio; it is a theorem about all numbers.

So the two essays either side of this one meet here. Euclid’s algorithm produces the convergents by a deterministic peeling with no notion of approximation in it; Dirichlet’s pigeonhole proves good approximations exist with no algorithm in it at all. The two constructions have nothing in common and produce the same list of fractions, which is the strongest possible sign that the list is the natural one.

The tree of every fraction exactly once is the third route to the same place: descending it towards a target and taking the nodes passed through gives the convergents again, one run of turns at a time.

The floor, and the number that sits on it #

Dirichlet’s bound is $1/q^2$. It can be improved, and only so far.

Hurwitz proved in 1891 that every irrational has infinitely many fractions with

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

and that the constant $\sqrt5$ cannot be replaced by anything larger. The number that stops it is the golden ratio: for $\varphi$, the inequality fails for every constant above $\sqrt5$ from some point onward.

This is where “the golden ratio is the most irrational number” comes from, and the phrase is worth handling carefully. Irrationality is not a quantity and there is no scale of it. What is true, and is precise, is that $\varphi$ is the worst approximable number: the constant in Hurwitz’s theorem is attained at $\varphi$ and at numbers equivalent to it, and no number does worse. Its continued fraction is all ones, which is exactly the statement that no quotient ever announces an unusually good approximation.

What the picture cannot show #

Every figure here stops at a denominator small enough to draw, and what happens at large denominators is where the subject actually lives.

Consider a number defined to be approximable absurdly well: Liouville’s constant,

$$\sum_{k=1}^{\infty} 10^{-k!} = 0.110001000000000000000001\ldots,$$

whose decimal expansion has ones at positions $1, 2, 6, 24, 120$ and zeros everywhere else. Truncating it after the $k$th one gives a fraction whose denominator is $10^{k!}$ and whose error is about $10^{-(k+1)!}$ — an approximation better than $1/q^n$ for every $n$.

Liouville showed in 1844 that an algebraic number of degree $n$ cannot be approximated better than about $1/q^n$, so his constant cannot be algebraic. That was the first proof that any specific number is transcendental, and it arrived thirty years before the proof for $e$ and forty before $\pi$. The strategy is worth noticing: rather than analysing a famous constant, Liouville built a number designed to be too well approximated to be algebraic. A property that no picture can show — behaviour at astronomically large denominators — was turned into a construction.

The figures also cannot show how sharp the algebraic bound became. Thue, Siegel and finally Roth in 1955 improved Liouville’s exponent all the way down to $2 + \varepsilon$: an algebraic irrational admits only finitely many fractions with $|\alpha - p/q| < 1/q^{2+\varepsilon}$. Since Dirichlet’s theorem gives infinitely many at exponent $2$, the true exponent for every algebraic irrational is exactly $2$ and there is no room left. Roth’s theorem is famously ineffective — it says only finitely many exceptions exist and gives no way to find them or bound their size — so the picture of a sharp result which cannot be used is the accurate one.

Where it shows up outside arithmetic #

Well and badly approximable numbers are not an internal curiosity. They decide the behaviour of anything that repeats at two incommensurable rates.

Take a rotation of a circle by an angle $\alpha$ turns, repeated. If $\alpha$ is a good approximation to $p/q$, then $q$ steps nearly return to the start, and the orbit clumps: it visits $q$ tight clusters before drifting. If $\alpha$ is badly approximable, no small number of steps nearly closes, and the points spread as evenly as they can. The three-distance theorem makes this exact — after $n$ steps, the gaps between successive points on the circle take at most three distinct values, and the values are determined by the continued fraction.

The same statement governs orbital resonance, where two periods in a near-rational ratio lock together and one in a badly approximable ratio does not, and it governs the arrangement of seeds in a sunflower head, where the golden angle is the choice that avoids every resonance at once. A number that resists approximation is a number whose multiples never nearly repeat, and that is a useful property to have when the goal is to fill space without a pattern.

It shows up in engineering under a different name. A sampling scheme, a dithering pattern, a quasi-random sequence for numerical integration — all of them want points that spread out rather than clump, and all of them get there by stepping through a badly approximable rotation. The low-discrepancy sequences used for high-dimensional integration are built from irrationals chosen precisely so that no small denominator nearly works, and the quality of such a sequence is measured by a bound that is Dirichlet’s theorem with the inequality pointing the other way.

There is an audible version, too. Two tones whose frequencies are in a near-rational ratio beat against each other at the rate of the near-miss, and the beating is slow when the approximation is good. Tuning a musical instrument is the practical business of choosing which near-misses to accept, and the comma that will not close is a statement that $2^{19}$ and $3^{12}$ are close and not equal — a rational approximation problem being settled by ear.

What the proof does not hand over #

Dirichlet’s argument is non-constructive in a specific and instructive way. It proves a collision occurs among $N+1$ points in $N$ boxes without saying which points collide; finding them means computing the fractional parts and looking, which is more work than running Euclid’s algorithm would have been.

So the theorem is not an algorithm and was never competing with one. What it provides is a guarantee that holds for every irrational simultaneously, including all the ones nobody can compute, and a bound that no algorithm was going to establish by running. That division of labour — existence by counting, construction by algorithm — is the same one that separates Euclid’s proof that primes never stop from any method of finding the next one.

There is a further consequence worth stating. Because the argument needs only $N+1$ points in $N$ boxes, it works unchanged for simultaneous approximation of several numbers at once, and in higher dimensions, and for approximating by things other than fractions. Nearly all of the modern subject — Diophantine approximation, the geometry of numbers, Minkowski’s theorem on lattice points in convex bodies — is this one counting argument, made in more elaborate boxes.

The drawer principle, and the man it is named after #

Dirichlet called it the Schubfachprinzip — the drawer principle — and it is not clear that he thought of it as a principle at all. It appears in his work as a step, unnamed and unremarked, in exactly the way an obvious observation appears in a proof that needs it.

What makes the attribution worth keeping is what else he did with the same habit of mind. In 1837 Dirichlet proved that every arithmetic progression $a, a+d, a+2d, \ldots$ with $a$ and $d$ coprime contains infinitely many primes — the first serious theorem about the distribution of primes in residue classes, and one that needed machinery so far beyond its statement that it effectively founded analytic number theory. The 1842 approximation theorem, by contrast, is four lines and needs nothing.

Both results have the same shape underneath: a statement that something must exist, established without producing it. The progression theorem does it with $L$-functions and the approximation theorem with drawers, and Dirichlet appears to have regarded neither method as more legitimate than the other.

There is a small irony in the naming. The pigeonhole principle is the most elementary tool in the subject and it is attached to the person who wrote its least elementary results, while the theorem it proves here — that good approximations exist for every irrational — is attached to nobody in particular and is usually just called Dirichlet’s theorem, which is ambiguous between the two.

More than one number at a time #

The proof used $N+1$ points in $N$ boxes along a line. Nothing about the argument cares that the boxes are intervals.

Take two irrationals $\alpha$ and $\beta$ and cut the unit square into $N^2$ boxes. The $N^2 + 1$ points $(\{k\alpha\}, \{k\beta\})$ must share a box, and the same subtraction gives a single denominator $q$ that works for both numbers at once:

$$\left|\alpha - \frac{p}{q}\right| < \frac{1}{q^{3/2}}, \qquad \left|\beta - \frac{r}{q}\right| < \frac{1}{q^{3/2}}.$$

The exponent is worse than $2$, which is the price of asking one denominator to serve two purposes, and it is the right price: with $n$ numbers the exponent is $1 + 1/n$, and that cannot be improved.

Pushing the same idea further gives Minkowski’s theorem, which replaces the boxes with an arbitrary convex region symmetric about the origin and says that a large enough region must contain a lattice point other than the origin. Every result in this essay is a special case, and so is the fact that certain primes are sums of two squares — a statement about circles that turns out to be a statement about a region being too big to avoid the lattice. The counting argument that started with eight socks in seven drawers ends up deciding which numbers are which shape.

Where the ladder goes next #

The pigeonhole principle has now done two jobs in this collection: proving that a shared box must exist among finitely many things, and proving that a good fraction must exist among infinitely many. Both times the conclusion is an existence claim and both times the proof is a count.

The next question is what the good fractions are made of, and that leads back to the continued fraction and forward to the geometry of the lattice — because a fraction $p/q$ near $\alpha$ is a lattice point near the line $y = \alpha x$, and asking how close a lattice point can come to a line is the question the two-squares problem asks about a circle instead.