How near nought a sum of roots can come

The sums of roots of unity that add to nothing asked which loops of unit arrows pointing at roots of unity close exactly, and found the answer in the prime factors of $n$: whole polygons, unions of them, and the surprising six thirtieths that close without containing any polygon at all. It ended with the question on the other side of that line. A sum of $k$ of the $n$-th roots of unity that does not vanish cannot be arbitrarily small for a fixed $n$, because there are only finitely many such sums. But as $n$ grows there are more and more of them packed into the same disc, and how close to nought can a non-zero one come?

Gerald Myerson put the question in 1986 and gave it a name, $f(k, n)$: the smallest non-zero value of $|\zeta^{a_1} + \zeta^{a_2} + \cdots + \zeta^{a_k}|$, where $\zeta = e^{2\pi i/n}$ and the exponents may repeat. It is a question about near-misses — about how nearly a sum of algebraic numbers can achieve an identity without achieving it — and it is easy to state, easy to compute for small cases, and for five terms still not understood.

How the search works #

Every figure here is an exhaustive search. Rotating every arrow by the same root of unity does not change the length of a sum, so one exponent can be fixed at nought, and the others run over every non-decreasing list of exponents from $0$ to $n - 1$. For five terms and $n = 122$ that is about nine million sums, each a few additions of precomputed sines and cosines.

The delicate part is telling a tiny sum from a zero one. Floating-point arithmetic reports a vanishing sum as something like $10^{-16}$, and a genuinely non-zero sum could in principle be smaller still. So every sum below $10^{-7}$ is checked exactly: the exponents become a polynomial $x^{a_1} + \cdots + x^{a_k}$ with whole-number coefficients, and the sum of roots vanishes precisely when that polynomial is divisible by the cyclotomic polynomial $\Phi_n$, which a long division in whole numbers decides. Every sum the search reports as a minimum has been certified non-zero that way, and every minimum is far above rounding error — the smallest anywhere in these figures is $1.48 \times 10^{-5}$.

For $n = 122$ the search finds exponents $0, 32, 50, 77, 104$. The arrows in the figure are drawn in an order that keeps the walk compact, and they come back to within $1.484 \times 10^{-5}$ of the start; the inset magnifies the neighbourhood of the origin forty thousand times to show the miss. What makes 122 special is not visible in the arrows, which point in no pattern a reader would recognise — no polygon, no symmetry — and the figure on records below shows that neighbouring $n$ do hundreds of times worse.

Two, three and four arrows #

For up to four terms the minimum has a geometric explanation, and the search confirms it. Two arrows can only nearly cancel by pointing nearly opposite. When $n$ is even, exact opposites exist and cancel, so the best non-zero pair is off by one step of $2\pi/n$, giving $2\sin(\pi/n)$; when $n$ is odd there is no exact opposite and the best pair misses by half a step, giving $2\sin(\pi/2n)$, about $\pi/n$. Either way $f(2, n)$ shrinks like $1/n$, and at $n = 31$ the search finds $0.1013$, which is $2\sin(\pi/62)$ to every digit.

Three arrows nearly cancel by nearly forming an equilateral triangle, and the best triangle is again off by an angle of order $1/n$, so $f(3, n)$ is also of order $1/n$ — at $n = 31$ it is $0.1192$, about $3.70/n$, and across every $n$ from 10 to 150 the product $n \cdot f(3, n)$ stays between 3.4 and $2\pi$, the top of that range reached when $n$ is a multiple of 3 and an exact triangle is available to be spoiled by one step. Ben Barber’s account of Myerson’s arguments gives the exact value for every $n$, with one of Myerson’s original values corrected; it is a case analysis of which near-triangles are available, and it never improves on $1/n$.

Why three cannot beat two is worth seeing, because it is the argument that fails at four. Put the first arrow at angle nought. For the sum to be small, the other two must point roughly at $\pm 120^\circ$, and their sum must be a vector of length nearly 1 pointing nearly backwards. Two unit arrows at angles $\alpha$ and $\beta$ add to a vector of length $2\cos\big((\alpha - \beta)/2\big)$ pointing along $(\alpha + \beta)/2$. Cancelling the first arrow exactly needs two conditions — the length must be 1 and the direction must be $180^\circ$ — and there are two free angles, so exact cancellation is possible only when both conditions land on multiples of $2\pi/n$. When they do not, each condition misses by up to half a step, and nothing is left over to absorb the miss: the error is first order in the step, of order $1/n$. When $n$ is a multiple of 3 the exact triangle exists, and the closest non-zero sum must spoil it by a whole step rather than half of one, which is why those $n$ do worst.

Four arrows have four free angles against the same two conditions, and the two spare angles are what allow the error of one pair to be steered against the error of the other.

Four arrows are where the first surprise comes. The best four are two nearly opposite pairs, and each pair, on its own, misses by an amount of order $1/n$. But the two misses can be turned against each other: the pair at exponents $1$ and $16$ misses one way and the pair $0, 16$ — sharing an arrow, here $16$ appears twice — misses in almost exactly the reverse direction, and the first-order parts of the two misses cancel. What survives is second order. The search finds $f(4, n) = 4\sin^2(\pi/2n)$ for every odd $n$ and $4\sin^2(\pi/n)$ for every even $n$ from 10 to 150, which is the square of the two-term answer and of order $1/n^2$.

That is the pattern the question invites: each extra arrow is a further degree of freedom with which to cancel a further order of the error, and one might guess $f(k, n)$ of order $n^{-(k-2)}$ or so. Three arrows already break the pattern — they do no better than two — and five break it in a different way.

Five terms obey no law #

Plotted on logarithmic scales, the first three cases are straight lines: slopes $-1$, $-1$ and $-2$, with the even and odd $n$ on two parallel lines that the figure keeps apart by drawing only the odd ones. The five-term values are a cloud. They fall overall — at $n = 10$ the smallest non-vanishing five-term sum is $0.24$, at $n = 150$ it is about $10^{-4}$ — but they scatter over four powers of ten, and neighbouring $n$ can differ by a factor of a hundred: $n = 122$ gives $1.48 \times 10^{-5}$, while $n = 123$ manages only about $1.5 \times 10^{-3}$.

The reason is that five arrows have enough freedom to cancel several orders of error at once, but only when the arithmetic of $n$ supplies exponents in the right relation. A near-pentagon is one source: perturbing the corners of a regular pentagon by single steps produces sums whose error cancels to second order. Barber proved in 2021 that this gives $f(5, n) = O(n^{-4/3})$ for every $n$, and $O(n^{-7/3})$ for infinitely many. The record at 122 sits at about $n^{-2.31}$, close to that second rate. Barber also computed $f(5, n)$ exactly for every $n$ up to 221,000, several weeks of computing and some $2^{47}$ sums, and the values on his plot lie between lines of slope $-2$ and $-3$ — near enough to both that he declined to conjecture which, if either, is the truth.

The cloud is the same kind of picture how close a fraction can get drew for rational approximations to an irrational number: most denominators do ordinarily well and a few do spectacularly well, because their arithmetic happens to line up. For fractions the spectacular ones are governed by continued fractions, which give a complete account. For sums of five roots of unity nothing comparable is known, and the records are found only by looking.

The guarantee from crowding #

The best general upper bound is a pigeonhole argument. Take $k$ even and $n$ even. Every sum of $k/2$ roots of unity lies in the disc of radius $k/2$, and there are about $n^{k/2}$ of them, counted as multisets of exponents. Crowd that many points into a fixed disc and two of them must lie within about $n^{-k/4}$ of each other — the disc has room for only so many points at any given spacing. Because $n$ is even, $-\zeta^a$ is itself a root of unity, so the difference of two sums of $k/2$ roots is a sum of $k$ roots. Unless the two sums were equal, that difference is non-zero, and it shows $f(k, n) \le n^{-k/4 + o(1)}$.

The figure draws the argument at $k = 6$ and $n = 24$. The 2,600 sums of three 24th roots fill the disc of radius 3 in a pattern of rings, the closest distinct pair lies $0.0353$ apart, and the search over all sums of six finds exactly that value as $f(6, 24)$ — here the pigeonhole pair is the true minimum. In general the pigeonhole bound is weak: it guarantees only $n^{-1}$ for four terms, where the truth is $n^{-2}$, and $n^{-5/4}$ for five, where Barber’s construction already does better. It is the right kind of argument for proving existence and the wrong kind for finding the best case, which is the usual fate of counting arguments.

Why a sum cannot be tiny everywhere #

The lower bound comes from a different kind of fact, about algebraic integers. A sum of roots of unity $s = \zeta^{a_1} + \cdots + \zeta^{a_k}$ is an algebraic integer of the field generated by $\zeta$, and it has conjugates: the sums $\zeta^{j a_1} + \cdots + \zeta^{j a_k}$ for every $j$ sharing no factor with $n$, which are what $s$ becomes under each symmetry of the field. The product of all of them, the norm of $s$, is a whole number, and if $s$ is not zero the norm is not zero, so its size is at least 1.

For the record at $n = 122$ there are $\varphi(122) = 60$ conjugates, and the figure sorts them by size. The sum itself and its complex conjugate are tiny, $1.48 \times 10^{-5}$ each. A handful of others are a few tenths. The largest approach 5, the most a sum of five unit arrows can be. And their product is exactly 1 — the smallest norm a non-zero algebraic integer can have. The two tiny factors are paid for, to the last digit, by the large ones.

That bookkeeping is Myerson’s lower bound. If every conjugate is at most $k$ and the product is at least 1, then the smallest conjugate is at least $k^{-(\varphi(n) - 1)}$, which is roughly $k^{-n}$. For five terms at $n = 122$ that bound is about $10^{-41}$, and the true value beats it by thirty-six powers of ten. The bound is honest, but it uses nothing except the size of the conjugates, and the truth is evidently far from it. Sergei Konyagin and Vsevolod Lev improved the exponent to about $k^{-n/4}$ for prime $n$ and distinct exponents; between that and the polynomial upper bounds lies an exponential gap, and closing it is Myerson’s question.

The norm argument is the same one that sank Lehmer’s question into difficulty: a product of conjugates that must be a whole number, one factor that wants to be extreme, and no way to say how the remaining factors share the compensation. That essay asked how close an algebraic integer’s conjugates can crowd the unit circle without lying on it; this one asks how close a particular kind of algebraic integer can come to nought without reaching it, and both are stuck at the same step.

Record lows #

Listing the records shows how irregular the progress is. From $n = 5$ to $150$ the record falls eleven times, at $n = 5, 7, 11, 13, 17, 29, 31, 47, 69, 74$ and $122$, and the exponent of $n$ it represents climbs from about 1 to 2.31 in jumps. Several records reuse an exponent: at $n = 31$ the best five are $0, 0, 9, 18, 18$, two doubled arrows and a single one, a configuration with more symmetry than its neighbours. Others, like $0, 13, 29, 40, 56$ at $n = 69$, have no visible structure at all.

Nothing in the search predicts which $n$ will set the next record. The configurations that work are those whose exponents satisfy, approximately, the relations a vanishing sum would satisfy exactly — and the vanishing sums were themselves decided by the prime factors of $n$. A near-vanishing sum is a vanishing sum for some nearby, larger $n'$, squeezed into $n$; which squeezes lose little is a question about how well fractions with denominator $n'$ are approximated by fractions with denominator $n$, and it does not reduce to anything simpler.

Where the question matters #

Small sums of roots of unity are not a curiosity of the circle. A sum $\sum_j \zeta^{a_j}$ is a value of a discrete Fourier transform, and the smallest non-zero value of such sums bounds how well a transform can separate signals that are nearly but not exactly alike. In sparse recovery — reconstructing a signal known to have only $k$ non-zero frequencies from a few of its Fourier samples — the stability of the reconstruction depends on how small certain $k$-term sums of roots of unity can be, so $f(k, n)$ is, roughly, a condition number for the problem. The same quantity bounds how close two different trigonometric sums with whole-number frequencies can come, and how many digits must be carried to decide reliably whether a sum of roots of unity is zero — which is the practical form of the exact test in the search above.

There is a musical version of the question as well. Equal temperament divides the octave into $n$ equal steps, and a chord that nearly closes a cycle of intervals — twelve fifths nearly returning to the starting note — is a near-vanishing combination of the same kind; the Pythagorean comma is how far that particular loop fails to close. Myerson’s $f(k, n)$ asks how small the comma of any $k$-step loop can be on an $n$-step circle.

What the search shows and cannot show #

The minima here are exact: every candidate is enumerated, and every reported minimum is certified non-zero by division by the cyclotomic polynomial in whole numbers. The formulas for two and four terms are checked against the search at every $n$ from 10 to 150, and the norm of 1 in the conjugate figure is the product of sixty floating-point values rounding to a whole number — a check, not a proof, of a fact the algebra guarantees.

What a search to $n = 150$ cannot show is the law for five terms. Barber’s search to 221,000 could not decide between slopes $-2$ and $-3$, and a search one more power of ten further would not settle it either, because the records are rare events governed by arithmetic, and their rate is the question. The figures also show nothing about six or more terms beyond $n = 24$, where exhaustive search becomes expensive: the number of candidates grows like $n^{k-1}$.

Still open: the exponent for five, and the gap for many #

What is the true order of $f(5, n)$? The upper bounds are $n^{-4/3}$ for every $n$ and $n^{-7/3}$ for infinitely many; the lower bound is exponential in $n$. The computations suggest a polynomial rate somewhere between $n^{-2}$ and $n^{-3}$ for the records, and nobody has a heuristic that convincingly picks one.

For general $k$ the gap is wider still. Is $f(k, n)$, for fixed $k$, always at least some fixed negative power of $n$ — polynomially small rather than exponentially? Myerson asked this, and it is open for every $k \ge 5$. A positive answer would mean that sums of roots of unity, like the periods that obey a smaller equation, are tied to the circle tightly enough that no clever arrangement can approach zero faster than a power of the number of roots; a negative one would mean that for some $k$ the arithmetic of $n$ can be exploited without limit.

A near-miss as a measurement #

The smallest non-zero sum of $k$ of the $n$-th roots of unity shrinks like $1/n$ for two and three terms and exactly as $4\sin^2(\pi/2n)$ for four, and for five it follows no law anyone has found: its values scatter over powers of ten, and the record at $n = 122$, at $1.48 \times 10^{-5}$, is a hundred times smaller than its neighbour’s. A pigeonhole on crowded half-sums guarantees small sums from above, the norm of an algebraic integer forbids them from being too small from below, and between those two arguments — one polynomial, one exponential — the truth for five arrows has not been located.