How close two sums of square roots come

Which roots refuse to be fractions proved that $\sqrt2 + \sqrt3$ is irrational by finding the polynomial it satisfies, $x^4 - 10x^2 + 1$, and checking that it has no rational root. The same method shows that any sum of square roots of whole numbers that are not perfect squares is irrational, and more: such a sum cannot equal another sum of square roots unless the two are the same sum written differently. This essay is about what happens when two different sums come close.

They can come remarkably close. And the question of how close — how many decimal places must be computed, at worst, to be sure which of two sums is larger — turns out to be open, with consequences for questions that look nothing like it.

Square roots that cannot conspire #

A sum like $\sqrt8 + \sqrt2$ is secretly $3\sqrt2$, because $\sqrt8 = 2\sqrt2$, and so $\sqrt8 + \sqrt2 = \sqrt{18}$: two sums that look different and are equal. Every coincidence of this kind comes from writing each square root as a whole number times the square root of a squarefree number — one not divisible by any square bigger than one. Abram Besicovitch proved in 1940 that nothing else can happen: the square roots of distinct squarefree numbers are linearly independent over the rationals, so a combination $c_1\sqrt{m_1} + \cdots + c_r\sqrt{m_r}$ with rational coefficients and distinct squarefree $m_i$ vanishes only when every $c_i$ is nought.

So the square roots of the whole numbers up to $n$ span a space whose dimension over the rationals is the number of squarefree numbers up to $n$ — 608 of the first thousand, close to the fraction $6/\pi^2$ that holds in the limit. Every relation among square roots of whole numbers is a consequence of pulling squares out from under the root signs, and there are no others. Two sums of square roots are therefore equal exactly when, after every root is written as a multiple of the root of a squarefree number, they agree term by term.

The proof runs by induction on the number of primes involved, and its engine is the sign change used throughout this essay. Suppose some rational combination of square roots of squarefree numbers vanished, using as few primes as possible. Pick a prime $p$ that occurs, and split the combination into the terms whose squarefree number contains $p$ and those that do not: $A + B\sqrt p = 0$, where $A$ and $B$ involve only the other primes. Changing the sign of $\sqrt p$ — a symmetry of the numbers built from these square roots, by the induction — gives $A - B\sqrt p = 0$ as well, so $A = 0$ and $B = 0$, two relations with fewer primes, and by minimality each is trivial. Linear independence is a statement that seven powers in a space of six would recognise: the square roots behave like a basis, and a basis admits no relation but the empty one. The same symmetry, applied to a difference of two sums, is what produces the sixteen conjugates below.

The degree of a sum tells the same story from the other side. Each new square root of a new prime doubles the degree.

The polynomial of $\sqrt2 + \sqrt3 + \sqrt5$ is $x^8 - 40x^6 + 352x^4 - 960x^2 + 576$, and that of $\sqrt2 + \sqrt3 + \sqrt5 + \sqrt7$ has degree sixteen. The figures compute them exactly by a doubling step: if $P(x)$ has the sign patterns of some roots as its roots, then $P(x + \sqrt m)\,P(x - \sqrt m)$ has whole-number coefficients again, because changing the sign of $\sqrt m$ swaps the two factors, and its roots are the old patterns with $\pm\sqrt m$ added. By Besicovitch’s theorem each of these polynomials is irreducible, so the sum of the square roots of the first $k$ primes has degree $2^k$: it lives in a tower whose degrees multiply, doubling at every floor.

Two sums that agree to eight places #

Different sums are never equal, but nothing stops them from being close.

Among all sums $\sqrt a + \sqrt b$ with $a \le b \le 320$ — a little over 51,000 of them — the two closest that are genuinely different are $\sqrt{88} + \sqrt{289}$ and $\sqrt{171} + \sqrt{177}$. Both are $26.38083152\ldots$, and they part company only at the ninth decimal place: the difference is $6.625 \times 10^{-9}$. A calculator showing eight digits would call them equal. The computation behind the figure finds the pair by sorting every sum and comparing neighbours, discards the neighbours that are the same number written differently by checking them against Besicovitch’s criterion, and confirms the winning pair in exact whole-number arithmetic to forty places.

The hero figure follows the closest pair as $n$ grows. For sums of two square roots the smallest difference falls roughly like $n^{-4}$ over the range computed — from about $10^{-3}$ at $n = 10$ to $10^{-8}$ at $n = 320$. For sums of three it falls faster, roughly like $n^{-6}$, reaching $2 \times 10^{-8}$ already at $n = 56$. More terms give more ways to nearly cancel, and the near misses get nearer.

Why near misses must exist #

Before asking how close sums can come, it is worth seeing that they must come close, by counting. There are about $n^2/2$ sums $\sqrt a + \sqrt b$ with $a \le b \le n$, and every one of them lies between $2$ and $2\sqrt n$. Squeeze $n^2/2$ values into an interval of length about $2\sqrt n$ and some two of them are within about $4 n^{-3/2}$ of each other — more things than boxes, with the boxes being little intervals. Some of those close pairs are exact coincidences of the $\sqrt8 + \sqrt2 = \sqrt{18}$ kind, which every comparison here sets aside, and the rest are genuine near misses.

The pigeonhole count gives about $n^{-3/2}$; the measured closest pairs are far closer, about $n^{-4}$. That is the same kind of excess as in the theory of approximating a single irrational number by fractions, where the pigeonhole principle of Dirichlet guarantees approximations within $1/q^2$ and particular numbers do much better. Here the role of the special number is played by special pairs of sums, built from numbers whose square roots happen to nearly satisfy a linear relation — and like the best approximations to an irrational, they are sparse, which is why the gaps figure below shows them only as a thin tail.

For sums of three square roots the count is $n^3/6$ sums in an interval of length about $3\sqrt n$, so the pigeonhole spacing is about $n^{-5/2}$, and the measured closest pairs fall like $n^{-6}$. Each additional root multiplies the number of sums by $n$ and widens the interval only slightly, so near misses become both more numerous and nearer; this is the source of the guess, behind the constructions of Qian and Wang, that the closest pairs for sums of $k$ roots fall like a power of $n$ growing linearly in $k$.

The proof that they differ, and what it costs #

That two different sums are unequal follows from Besicovitch’s theorem. How unequal follows from a sharper argument, and the argument is the same one approached too fast to be algebraic used to show Liouville’s numbers are transcendental: an algebraic integer that is not nought has a norm that is a whole number at least one.

Take the difference $D = \sqrt{88} + \sqrt{289} - \sqrt{171} - \sqrt{177}$ and all sixteen numbers obtained by changing the signs of its four square roots. Changing a sign permutes the sixteen among themselves, so their product is unchanged by every such change and is a whole number — here, computed exactly, $81$. Since $D$ is not nought, neither is the product, so it is at least one. One factor is $D$ itself and one is $-D$, and each of the other fourteen is at most $\sqrt{88} + \sqrt{289} + \sqrt{171} + \sqrt{177} < 53$, so

$$D^2 \ge \frac{81}{53^{14}}, \qquad |D| \ge 10^{-11.1},$$

and in general, for two sums of $k$ square roots of numbers up to $n$, the same reasoning gives

$$|D| \ge (2k\sqrt n)^{\,1 - 4^k}.$$

That is the dashed floor in the hero figure. It is enough to decide any particular comparison — compute to that many digits and the sign of the difference is certain — but the number of digits it demands grows like $4^k$, doubly exponential in the number of terms. For two terms at $n = 320$ the floor sits near $10^{-28}$, twenty orders of magnitude below the closest pair actually found.

Why the floor is so pessimistic #

The norm argument loses because it assumes the worst about the other conjugates: that every one of the fourteen is as large as possible, so that their product leaves the most room for $D$ to be small. In the example they are not all large — several are around 7 or 8 — and the product of all sixteen is only 81, which means $D$ is about as large as the product of the other fourteen allows. The argument is tight only for differences whose conjugates are all simultaneously large, and nothing is known that says such differences exist, or that they do not.

That is the shape of the open problem. Nobody knows how small a non-zero difference of two sums of $k$ square roots of numbers up to $n$ can be. The constructions of Jianbo Qian and Cao An Wang give pairs that are polynomially close, about $n^{-2k + 3/2}$ for sums of $k$ roots, and the computations here find pairs at least that close. The norm floor is doubly exponential in $k$. If the truth is polynomial — some $n^{-ck}$ — then comparing two sums of square roots needs only a polynomial number of digits and can be done quickly. If some families come doubly exponentially close, then the obvious algorithm, computing digits until the sums separate, can take an astronomically long time.

The distribution of the gaps shows where the near misses come from. Most gaps between neighbouring sums are ordinary, near the average spacing of the 5,050 sums, and the smallest is about 24,000 times smaller than the average — of the order a random scattering of that many points would produce, and a few times smaller still. The record pairs are a thin tail, a handful of values among thousands, and nothing about the bulk of the distribution predicts where they will fall. They are not a pattern visible in the bulk; they are particular coincidences of arithmetic, and the question is how extreme those coincidences can become as the numbers grow.

A question that sits under geometry #

This would be a curiosity if sums of square roots were rare, a puzzle about decimals with no consequences beyond the digits themselves. They are not: the length of a path through points with whole-number coordinates is a sum of square roots, one for each segment, since a segment from $(x_1, y_1)$ to $(x_2, y_2)$ has length $\sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}$. Comparing the lengths of two routes through the same points is comparing two sums of square roots of whole numbers.

So the travelling salesman problem in the plane — find the shortest closed route through given points, the problem tours within half again of the best approximated — has a hidden obstacle. Michael Garey, Ronald Graham and David Johnson observed in 1976 that the problem is NP-hard, but that it is not known to be in NP: a proposed route can be checked against a length bound only by comparing a sum of square roots with a number, and nobody knows how to do that in polynomial time. The same obstacle appears in shortest paths among obstacles, in Euclidean minimum spanning trees with exact comparisons, and in many problems in computational geometry, where exact algorithms are stated for a model of computation that compares real numbers for free precisely to avoid it.

The sum-of-square-roots problem — given whole numbers, decide whether $\sum \sqrt{a_i} - \sum \sqrt{b_i}$ is positive — is known to be solvable within a level of the counting hierarchy, by work of Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen and Peter Bro Miltersen in 2009, and is not known to be solvable in polynomial time, nor to be hard for NP in the sense of there is a relation such that; it sits, unclassified, in the space between. It is one of the simplest-sounding questions in computational complexity whose status is open, and it is open because of the gap in the hero figure.

The same difficulty, one level up #

The obstacle is not special to square roots. Any number given by a short formula — a sum of roots, a product of powers, the value of a polynomial at an algebraic point — can be very close to another such number without being equal, and deciding which is larger needs to know how close is possible. For numbers built by a short sequence of additions and multiplications from 1, the problem is called PosSLP, and Allender and his coauthors showed that the sum-of-square-roots problem reduces to it, so that any fast algorithm for PosSLP would settle both. What is known in general is that algebraic numbers cannot be too close to one another relative to their degrees and sizes — the same norm argument, made quantitative as a separation bound — and the separation bounds are the reason the problems are decidable at all.

The irrationality proofs met earlier are separation bounds in disguise. The race that makes ζ(3) irrational showed $\zeta(3)$ is not a fraction by producing fractions that approach it faster than any fraction could approach a different fraction, and the proof that the difference of two sums of square roots is not nought shows it is too far from nought to be nought — at least $(2k\sqrt n)^{1-4^k}$ away. In both, the difficulty is quantitative: knowing that a number is not nought is easy compared with knowing how far from nought it is.

Exhaustive to a few hundred, silent beyond #

The closest pairs are found by an exhaustive sort, checked against Besicovitch’s criterion for exact coincidences, and the winning pair is confirmed to forty digits in whole-number arithmetic. The polynomials and the product of sixteen conjugates are computed exactly, the product being an integer to the last digit. What the figures measure is the closest pair for each $n$ up to a few hundred, and the slopes of $-4$ and $-6$ are fits to that range; they suggest polynomial behaviour, and they cannot rule out much closer pairs among larger numbers or longer sums, where a search of all sums is impossible. There is also a limit of a more mundane kind. The sorting is done in ordinary double-precision arithmetic, which carries about sixteen significant figures, and a sum of three square roots near 20 is stored with an error of a few times $10^{-15}$. A near miss smaller than that would be invisible to the sort, or would be mistaken for an exact tie. At the rate of $n^{-6}$ the closest pairs of three roots would reach that size somewhere around $n = 600$, and the number of sums to sort there, about thirty-six million, is itself a strain; so a search beyond that range has to sort in higher precision from the start — the very difficulty the essay is about, met at the first step of the computation that studies it.

Still open: the right number of digits #

The open question has a precise form. Let $r(n, k)$ be the smallest positive value of $\left|\sum_{i=1}^k \sqrt{a_i} - \sum_{i=1}^k \sqrt{b_i}\right|$ over whole numbers up to $n$. Is $-\log r(n, k)$ bounded by a polynomial in $k$ and $\log n$? The norm argument gives a bound exponential in $k$; the constructions give lower bounds linear in $k \log n$; nothing in between is proved, even for $k = 3$ — where the exhaustive search here can only reach numbers up to a few dozen. A positive answer would put the comparison of sums of square roots, and with it the verification of Euclidean travelling-salesman tours, in polynomial time; a negative one would show that some innocent-looking sums of square roots agree to more digits than any computer could ever print.