Two numbers approximated at once

How close a fraction can get dropped the multiples of one irrational number into boxes and caught two in the same box. Eight points in seven boxes, applied to the fractional parts of $\alpha, 2\alpha, \ldots$, proves that every irrational $\alpha$ has infinitely many fractions $p/q$ with $|\alpha - p/q| < 1/q^2$ — equivalently, that $q\,\|q\alpha\| < 1$ for infinitely many $q$, where $\|x\|$ is the distance from $x$ to the nearest whole number. That essay noted in passing that the same argument works in more dimensions, for several numbers at once, and moved on.

This essay takes the step it postponed. Two irrational numbers, $\sqrt 2$ and $\sqrt 3$, are to be approximated by fractions with one common denominator: a single $q$ that makes $q\sqrt 2$ and $q\sqrt 3$ both nearly whole. The pigeonhole principle settles how well that can always be done, and it does so in one line. Asking whether it can be done much better leads to one of the oldest open problems about real numbers, stated by John Edensor Littlewood around 1930, which no one has proved for these two numbers or for any pair like them.

Thirty-seven points in thirty-six boxes #

Each multiple $q$ gives a point in the unit square: the fractional part of $q\sqrt 2$ across, the fractional part of $q\sqrt 3$ up. Cut the square into a six-by-six grid of boxes, each of side $1/6$, and take the 37 points for $q = 0, 1, \ldots, 36$. There are more points than boxes, so some box holds two. In the hero the shaded box holds the points for $q = 8$ and $q = 15$.

Two points in one box are less than $1/6$ apart in each coordinate. Their difference is the point for $q = 15 - 8 = 7$, up to whole numbers, so $7\sqrt 2$ and $7\sqrt 3$ are each within $1/6$ of a whole number: $7\sqrt 2 = 9.8995$ is $0.1005$ short of 10, and $7\sqrt 3 = 12.1244$ is $0.1244$ past 12. One denominator, 7, serves both numbers, with errors $0.1005/7$ and $0.1244/7$ in the fractions $10/7$ and $12/7$.

Nothing about six was special. With $N^2$ boxes of side $1/N$ and the $N^2 + 1$ points for $q = 0$ to $N^2$, two points share a box and their difference $q$, somewhere between 1 and $N^2$, has

$$\|q\sqrt 2\| < \frac1N, \qquad \|q\sqrt 3\| < \frac1N.$$

Since $q \le N^2$, each distance is below $1/\sqrt q$, and the product $q\,\|q\sqrt 2\|\,\|q\sqrt 3\|$ is below $q/N^2 \le 1$. This is Dirichlet’s simultaneous approximation theorem, proved by exactly this counting in 1842, and the price of approximating two numbers at once is visible in the exponent: one number alone can be brought within $1/q$ with denominator $q$, two together only within about $1/\sqrt q$ each, because the boxes now fill a square instead of a line.

The argument does not say which box, which pair, or which $q$; it says only that the boxes cannot all be singly occupied. That is its strength — it applies to every pair of numbers at once, including all the ones nobody can compute with — and its weakness, because it gives no hint of whether a cleverer choice of $q$ could do much better.

A floor for each number, and none for the product #

For one number at a time the question “can it be done much better?” has a complete answer, and for these numbers the answer is no. $\sqrt 2$ has the continued fraction $[1; 2, 2, 2, \ldots]$ and $\sqrt 3$ has $[1; 1, 2, 1, 2, \ldots]$, both periodic, both with bounded partial quotients, and a fraction that never closes explained what that means: their best approximations are only as good as Dirichlet’s theorem forces and never much better. The figure confirms it. As $q$ runs through every whole number up to twenty million, the smallest value of $q\|q\sqrt 2\|$ ever seen is $0.3431$, reached at $q = 2$, and of $q\|q\sqrt 3\|$ it is $0.2679$, at $q = 1$. Neither ever improves. These are badly approximable numbers, the class the numbers that come after the golden ratio ranked by how badly.

The product behaves differently. It starts at $0.111$ for $q = 1$ and finds a new record eight times below twenty million: $0.0985$ at 4, $0.0875$ at 7, $0.0761$ at 12, $0.0615$ at 15, $0.00996$ at 41, $0.00466$ at 10,864 and $0.00185$ at 4,628,523. Each factor is bounded below on its own — $\|q\sqrt 2\| \ge 0.34/q$ and $\|q\sqrt 3\| \ge 0.27/q$ for every $q$ — but nothing stops the two from being small together at the same $q$, beyond what each forces separately. The red staircase steps down rarely and far, the intervals between records growing by factors of hundreds.

Littlewood’s conjecture is that the staircase never stops. For every pair of real numbers $\alpha, \beta$,

$$\liminf_{q \to \infty}\; q\,\|q\alpha\|\,\|q\beta\| = 0.$$

If either number is well approximable on its own — has unbounded partial quotients — the conjecture is immediate, because one factor alone can be made smaller than any multiple of $1/q$. The whole difficulty lies with pairs of badly approximable numbers, like $\sqrt 2$ and $\sqrt 3$, where each factor separately is held at its floor and only their cooperation can push the product down. For this pair the conjecture is open.

Why one number alone has a floor #

The floors in the figure are not accidents of the range searched, and seeing why they exist explains why the product is the interesting quantity. For a single number the multiples $q\alpha$ modulo 1 are a rotation of the circle by $\alpha$, the system three gaps and no more studied: after $q$ steps the points cut the circle into gaps of at most three lengths, and the shortest gap is exactly the smallest $\|k\alpha\|$ for $k < q$. For a badly approximable number the three lengths stay comparable at every stage — none of them ever becomes much smaller than $1/q$ — and that is the floor. For $\sqrt 2$, whose continued fraction is all 2s, the gaps at each stage are in a fixed ratio, and the best approximations $1/1, 3/2, 7/5, 17/12, 41/29, \ldots$ each come within a constant multiple of $1/q^2$, with the constant tending to $1/(2\sqrt 2) = 0.3536$. The minimum $0.3431$ in the figure is the first one, at $q = 2$, a little below that limit.

So for one number the question is closed by an algorithm. The continued fraction lists the best approximations, the size of its partial quotients measures how good they are, and the floor is the reciprocal of a bound on those quotients — Hurwitz’s $\sqrt 5$ for the golden ratio, $2\sqrt 2$ for $\sqrt 2$. Two numbers have no continued fraction, and the floors of the two coordinates say nothing about how the two sets of good denominators interleave. The product $q\|q\alpha\|\|q\beta\|$ is small exactly when a good denominator for one number is, by luck or by structure, also fairly good for the other, and Littlewood’s question is whether that luck is guaranteed.

There is a clean way to see that it is not guaranteed by size alone. The denominators where $\sqrt 2$ is unusually well approximated are the Pell numbers $1, 2, 5, 12, 29, 70, \ldots$, growing by a factor of about $2.414$; those where $\sqrt 3$ is are $1, 3, 4, 11, 15, 41, 56, \ldots$, growing by about $3.732$ every two steps. The two sequences grow at rates whose logarithms are rationally independent, so they almost never coincide, and the product’s records come not from coincidences of best approximations but from denominators that are excellent for one number and merely decent for the other — the lopsided records of the table below. Both sequences are recorded in the records, at $q = 12$ and $q = 41$, where one factor is small for exactly this reason.

Three pairs and a rate #

The figure sets three pairs side by side. For $\sqrt[3]2$ and $\sqrt[3]4$ the conjecture is a theorem. J. W. S. Cassels and Peter Swinnerton-Dyer proved in 1955 that it holds whenever $1, \alpha, \beta$ span a cubic field — here $\mathbb{Q}(\sqrt[3]2)$ — by a geometric argument about the norm form of the field, which is a product of three linear forms and takes whole-number values on the integer lattice. Their records fall in the figure in the same irregular staircase, reaching $0.00198$ at $q = 12{,}096{,}754$.

For $\sqrt 2$ and $\sqrt 5$ the records fall faster, to $4.5 \times 10^{-4}$ at $q = 196{,}418$, and the denominator gives the game away: 196,418 is the 27th Fibonacci number. Since $\sqrt 5 = 2\varphi - 1$, every Fibonacci number brings $q\sqrt 5$ exceptionally close to a whole number, and the product inherits the closeness. Even so, $\sqrt 5$ alone is badly approximable — the golden ratio is the most badly approximable number of all — and the product’s decline needs $\sqrt 2$ to cooperate at the same Fibonacci denominators, which it occasionally does.

The dashed curve is $1/(\ln q)^2$. Patrick Gallagher proved in 1962 that for almost every pair of real numbers — all but a set of area nought — the product $q\|q\alpha\|\|q\beta\|$ comes below $c/(\ln q)^2$ infinitely often, and not much below. A random pair satisfies Littlewood’s conjecture at that rate. All three pairs in the figure sit on or below the curve, so these special algebraic pairs behave, as far as twenty million, like typical ones. That is evidence — the same kind of evidence the fractions that beat every smaller one collected for a single number’s best approximations — and a measure of how slowly the product has to fall: at $q$ = twenty million, $1/(\ln q)^2$ is still only $0.0035$.

What the boxes guarantee, and no more #

Littlewood’s product is one way of measuring simultaneous approximation. The more direct one asks for both distances to be small at once, the larger of the two below some target, and the record-setters are the best simultaneous approximations: the $q$ at which $\max(\|q\sqrt2\|, \|q\sqrt3\|)$ reaches a new low. Up to twenty million there are 16 of them — 3, 7, 22, 34, 41, 1,183, 1,463 and onward to 2,151,016 — and the figure plots each at $\sqrt q$ times its distance. Dirichlet promises infinitely many below 1, and all sixteen are, scattered between $0.11$ and $0.64$ with no drift up or down.

For a single number the best approximations come from the continued fraction, each computed from the last, and the gaps between their denominators grow geometrically. For two numbers there is no comparable algorithm. Many have been proposed — Jacobi’s and Perron’s generalised continued fractions, Brun’s algorithm — and none is known to produce all the best simultaneous approximations, or to detect when a pair is badly approximable in the joint sense. The search in the figure simply tries every $q$. That is why the denominators look erratic, jumping from 41 to 1,183 and from 20,586 to 134,421: there is no known recursion that predicts the next.

The records, factor by factor #

Splitting each record into its factors shows how the product gets small. The early records are balanced: at $q = 7$ the distances are $0.1005$ and $0.1244$, nearly equal, the kind of approximation the boxes produce. The deep ones are not. At $q = 10{,}864$, $q\sqrt 3$ is within $2.7 \times 10^{-5}$ of a whole number while $q\sqrt 2$ is a relatively distant $0.016$ away, a factor of six hundred between them. At $q = 4{,}628{,}523$ the distances are $3.6 \times 10^{-4}$ and $1.1 \times 10^{-6}$.

So the small products come from one factor being driven unusually low — far below the $1/\sqrt q$ the boxes give — while the other stays respectable. That is the shape Littlewood’s conjecture is about, and the boxes cannot see it, because they cut the square into squares and treat the two directions alike. Cutting it instead into long thin rectangles, $1/N$ wide and $N/q$ tall in varying proportions, gives the same count of boxes with a different shape, and every shape gives a guarantee; the conjecture is that, among all these shapes, some are always eventually beaten. The same reasoning with rectangles instead of squares is how Minkowski’s theorem in the geometry of numbers works, and it is why the problem moved, in the second half of the twentieth century, from number theory into geometry.

The conjecture as a statement about flows #

The modern approach turns the pair $(\alpha, \beta)$ into a lattice in three-dimensional space and watches what happens to it under stretching. Write the points $(q, q\alpha - m, q\beta - n)$ for whole numbers $q, m, n$; they form a lattice $\Lambda$. A product $q\|q\alpha\|\|q\beta\|$ that is small is a lattice point whose three coordinates have a small product. Now stretch space by a diagonal map that multiplies the coordinates by $e^{s+t}$, $e^{-s}$ and $e^{-t}$, which preserves volumes and products of coordinates. Littlewood’s conjecture becomes the statement that the stretched lattices, over all $s$ and $t$, come arbitrarily close to having a point near the origin — that the orbit of $\Lambda$ under the diagonal group, in the space of all lattices, is not trapped in a compact region.

That reformulation connects the problem to a conjecture of Grigory Margulis about orbits of diagonal groups, and it is how the strongest result was obtained. Manfred Einsiedler, Anatole Katok and Elon Lindenstrauss proved in 2006, by an analysis of measures invariant under the diagonal flow, that the set of pairs violating Littlewood’s conjecture has Hausdorff dimension nought. It is vanishingly thin — thinner than any Cantor set of positive dimension — but the proof cannot show it is empty, and it says nothing about any particular pair such as $\sqrt 2$ and $\sqrt 3$.

The same kind of shift appeared in the orbit that must come back: a statement about one number’s multiples becomes a statement about a dynamical system, and recurrence theorems for the system give approximation theorems for the number. Here the system is the space of three-dimensional lattices, and the recurrence needed is of a kind nobody can yet prove for a single orbit.

Lattices that see almost nothing #

Simultaneous approximation is not only a curiosity. Points on a lattice that see almost nothing built rules for numerical integration from the points $(q/N, \{qg/N\})$, the multiples of a well-chosen fraction, and found that their error falls like a power of $1/N$ when the generator $g/N$ is badly approximable in a precise sense. A good integration lattice in two dimensions is a pair of numbers that no small denominator approximates well together, and the best ones are built from the Fibonacci numbers, exactly because $\varphi$ is badly approximable. In more dimensions, the lattice rules used for high-dimensional integration need generators whose multiples avoid the boxes as long as possible, and the quality measure they are judged by is a product of distances — Littlewood’s product, read in reverse, as something to keep large.

The two problems pull in opposite directions. Integration wants pairs for which the product stays large for as long as possible; Littlewood’s conjecture says that, sooner or later, it never stays large. A proof of the conjecture would put a limit on how good any integration lattice can be, uniformly, and its failure for some pair would hand numerical analysis a generator better than any now known. Neither has happened.

What the search can and cannot show #

Every distance is computed in double-double arithmetic: each fractional part is carried as a sum of two floating-point numbers, adding $\sqrt 2$ or $\sqrt 3$ to it at every step, so that after twenty million additions the accumulated error is around $10^{-25}$ — far below the $10^{-6}$ distances at the deepest record. The square roots and cube roots are themselves computed to double-double precision. The records are therefore exact for every $q$ searched, and the floors of $0.3431$ and $0.2679$ are the true minima over that range; that they are the minima over all $q$ follows from the continued fractions, not from the search.

No search can say anything about Littlewood’s conjecture for this pair. A product that keeps falling for twenty million steps might stop falling at a hundred million; the conjecture is a statement about the infinite tail, and the eight records are consistent with it and with its failure. The search also cannot distinguish the rates. Whether the records for $\sqrt 2$ and $\sqrt 3$ fall like $1/(\ln q)^2$, like Gallagher’s typical pair, or like $1/\ln q$, or at some other rate, would need records at denominators far beyond reach, since each record sits hundreds of times further out than the last.

Still open: a single explicit pair #

Littlewood’s conjecture is open, and so is every weaker form of it for an explicit pair of badly approximable numbers outside one cubic field. It is not known for $\sqrt 2$ and $\sqrt 3$, nor for $\sqrt 2$ and $\sqrt 5$, nor for any two quadratic irrationals from different fields. A $p$-adic version, proposed by Bernard de Mathan and Olivier Teulié in 2004 with $\|q\alpha\|$ replaced by a power of a prime dividing $q$, is open too, and for it Einsiedler and Dmitry Kleinbock proved the same measure-zero result.

The obstruction is the one the figures show. Each factor is bounded below by a theorem about its own continued fraction, and the conjecture needs the two continued fractions to conspire infinitely often — to have denominators where both are good at once, beyond what independence would give. For numbers in one cubic field the conspiracy is forced by the field’s arithmetic, which is what Cassels and Swinnerton-Dyer exploited. For two square roots from different fields there is no common algebraic structure to force it, and every attempt to show that their approximations must eventually line up has needed information about the joint distribution of two continued fractions that nobody knows how to obtain.

Two numbers, one denominator, an open floor #

Thirty-seven points in thirty-six boxes give one denominator that brings $\sqrt 2$ and $\sqrt 3$ within $1/6$ of whole numbers together, and the same count with $N^2$ boxes makes $q\|q\sqrt 2\|\|q\sqrt 3\| < 1$ infinitely often. Each number alone has a floor it never goes below — $0.3431$ and $0.2679$ — but the product keeps setting records, eight below twenty million, down to $1.85 \times 10^{-3}$, the deep ones lopsided with one distance hundreds of times smaller than the other. Littlewood conjectured that the product can always be made as small as wanted; it is proved for pairs from one cubic field and for all pairs outside a set of dimension nought, and for $\sqrt 2$ and $\sqrt 3$, after ninety years, it is still a guess.