The sums of roots of unity that add to nothing

The polygon an equation forces began with the most quoted fact about the roots of unity: the $n$ solutions of $z^n = 1$ add to zero, because they are the corners of a regular polygon centred on the origin. It follows at once that any regular polygon among them adds to zero too — the three cube roots sit inside the twelfth roots, and turning them by any twelfth of a turn keeps them a triangle. And a union of such polygons adds to zero, because each piece does.

That raises the question the opening essay only named. Is every vanishing sum of roots of unity built that way? Is there a collection of points on the circle, all of them roots of unity, whose arrows close into a loop although no regular polygon can be picked out of them? And if the answer depends on $n$, how exactly?

The answers are: sometimes, and it depends on how many prime factors $n$ has. With one or two there are no surprises; with three there are, and the smallest takes six thirtieths of a turn.

Six arrows and no polygon #

Take the four fifth roots of unity other than 1. The five fifth roots add to zero, so these four add to $-1$. Now take the two sixth roots of unity at $\pm 60°$: they are $\tfrac12 \pm \tfrac{\sqrt3}{2}i$, and they add to $+1$. Put the six together and the total is zero.

All six are thirtieth roots of unity, since both 5 and 6 divide 30: the pentagon’s corners are 6, 12, 18 and 24 thirtieths of a turn, and the two hexagon corners are 5 and 25. The figure draws them twice — as points on the circle, coloured by where they came from, and as arrows laid head to tail, which leave the origin and return to it.

No regular polygon can be picked out of them. A regular polygon among the thirtieths has 2, 3 or 5 corners, or a number made from those, and a check of every way of removing turned 2-gons, 3-gons and 5-gons from the six finds that none empties them. No smaller part of the six vanishes either. The sum is minimal — nothing can be taken away — and it is not a union of polygons. It is the smallest example of its kind: Conway and Jones’s classification of short vanishing sums, from 1976, shows that none with fewer than six terms escapes being a polygon, and the theorem below shows that $n$ needs three different prime factors.

The mechanism is visible in its construction. The pentagon, missing its corner at 1, sums to $-1$; the hexagon, reduced to two corners, sums to $+1$; and the two deficits cancel. There is a second way to say it: the two hexagon corners are $-\omega$ and $-\omega^2$, where $\omega$ is a cube root of unity, so the six terms are the whole pentagon minus the whole triangle $1 + \omega + \omega^2$. Two polygons, one of them subtracted, close into a loop — and subtraction is exactly what a sum of roots, each used a whole number of times, is not supposed to allow. The polygon is still the atom; it has been smuggled in with a minus sign.

Why a prime number of roots cannot surprise #

Everything above can be decided exactly rather than by drawing, and the method shows why prime numbers matter. A sum of $n$-th roots of unity is a polynomial in $\zeta = e^{2\pi i/n}$ with whole-number coefficients — the coefficient of $\zeta^k$ is how many times the root $\zeta^k$ is used. That polynomial vanishes at $\zeta$ exactly when it is a multiple of the cyclotomic polynomial $\Phi_n$, the minimal polynomial of $\zeta$ that the opening essay factored out of $z^n - 1$. So a sum is zero exactly when its remainder on division by $\Phi_n$ is zero, and that remainder is a list of whole numbers that can be computed without rounding anything.

For a prime $p$, $\Phi_p = 1 + z + z^2 + \cdots + z^{p-1}$, and a polynomial of degree less than $p$ is a multiple of it only if all its coefficients are equal. So a vanishing sum of $p$-th roots uses every root equally often: it is the whole $p$-gon, repeated. A prime number of equally spaced points admits no cleverness at all.

For a prime power the same argument gives turned $p$-gons, since $\Phi_{p^a}(z) = \Phi_p(z^{p^{a-1}})$. And for two primes, $n = p^a q^b$, Lam and Leung proved in 2000 that every vanishing sum with non-negative coefficients is a union of turned $p$-gons and $q$-gons. The six-term sum needs a third prime because two are not enough.

The twelfths show the two-prime case working. Seven of them — 1, 5 and 9 twelfths, a triangle, and 2, 5, 8 and 11, a square — close into a loop, and the loop is visibly two loops: the triangle’s three arrows and the square’s four. The root at 5 twelfths is used twice, once by each. Any vanishing sum of twelfths, however long, can be split this way, because 12 = 4 × 3 has only the primes 2 and 3; the square is itself two opposite pairs, turned 2-gons. The figure’s check found such a split, and for the six thirtieths it found none.

How many terms can close #

A cleaner question has a cleaner answer. Forget which roots; ask only how many. For which $m$ is there some collection of $m$ $n$-th roots of unity, repeats allowed, whose sum is zero?

Unions of polygons give an obvious supply. Every prime $p$ dividing $n$ gives a $p$-gon, and polygons can be combined, so any $m$ that is a sum of prime factors of $n$ — with repeats — is achievable. For $n = 15$ that is $3a + 5b$: 3, 5, 6, 8, 9, 10 and every number from 8 on. It misses 1, 2, 4 and 7.

The theorem is that nothing else is possible, and it is the one Lam and Leung proved: the numbers of terms that can vanish are exactly the sums of prime factors of $n$. The six-term sum of thirtieths is not a union of polygons, but 6 is still $3 + 3$ or $2 + 2 + 2$. No sum of seven fifteenths is zero, whatever roots are chosen, although sums of three and of five are. For $n = 10$, the tenths, no three vanish: $3$ is not $2a + 5b$.

Why nothing else is possible has a short idea behind a long proof. Reduce a vanishing sum modulo one prime $p$ dividing $n$: grouping the roots by their $p$-th powers splits the sum into $p$ smaller sums of roots of lower order, each of which must vanish or be matched by the others in a rigid way, and an induction on the number of primes finishes it. What makes the count a sum of primes is that each step of the induction peels off whole $p$-gons or leaves a problem with one prime fewer — the same bookkeeping of turned copies that necklaces that prove a theorem uses when it groups a necklace’s rotations by their period.

The figure checks the claim by brute force. For each $n$ and each $m$ up to ten it builds every possible sum of $m$ roots, reduced exactly modulo $\Phi_n$, and asks whether zero is among them. The filled cells are the $m$ for which it is, and in every row they are exactly the sums of that row’s primes. For $n = 21$ the search stops at seven, because the number of distinct partial sums passes two million, but seven is the interesting case: 7 twenty-firsts can vanish, as a turned heptagon, and 8 cannot.

Balancing a centrifuge #

The question has a practical form that laboratories meet daily. A centrifuge has $n$ equally spaced slots round its rotor, and $k$ identical tubes must be placed so that the rotor stays balanced — so that the tubes’ centre of mass is the centre of the rotor. Positions are $n$-th roots of unity, a tube’s contribution is its position times its mass, and a loading is balanced exactly when the chosen roots add to zero. Each slot takes at most one tube, so this is the vanishing-sum question with every root used at most once.

That restriction adds one condition and no others. The empty slots of a balanced loading are balanced too, because all $n$ roots add to zero and the tubes’ share does; so $n - k$ must be achievable if $k$ is. Gary Sivek proved in 2010, building on Lam and Leung, that this is the whole answer: $k$ tubes can be balanced in $n$ slots exactly when both $k$ and $n - k$ are sums of prime factors of $n$.

For a twelve-slot rotor every $k$ from 2 to 10 works, and 1 and 11 do not — a single tube, or a single gap, cannot be balanced by anything. For fifteen slots, 7 and 8 fail: 7 is not $3a + 5b$, and 8 fails because its complement, 7, does. Seven tubes in a fifteen-slot rotor cannot be balanced however cleverly they are arranged, and the reason is the row of the table above. A rotor with a prime number of slots, $p$, can be balanced only when it is empty or full, because the only vanishing sums of $p$-th roots use every root — the fact that made primes admit no cleverness, arriving as a warning printed on a machine.

The arrows here are the ones multiplying is turning draws: each slot is a turn by a fixed fraction of a circle, and balancing is the same closing of a loop the figures above show. The arithmetic is numbers that wrap — which multiples of $1/n$ of a turn, added as angles, can bring every direction back into balance.

Where diagonals cross #

The question turns up somewhere it has no business being. Draw every diagonal of a regular polygon and count the points where they cross.

Any four corners of the polygon determine exactly one crossing — the two diagonals joining them alternately — so if no three diagonals ever met at a point, the count would be $\binom{n}{4}$. For the 11-gon it is: $\binom{11}{4} = 330$ corners-of-four, and 330 distinct crossings. For an odd number of sides, no three diagonals of a regular polygon are ever concurrent.

For even $n$ they are. Every diameter passes through the centre, so the 12-gon’s six diameters meet there, and many other points carry three or four diagonals at once. The 495 crossings of pairs collapse to 301 distinct points, 73 of them shared by three or more diagonals.

The connection is through Ceva’s theorem. Three chords of a circle meet at a point exactly when a product of sines of the arcs they cut equals another such product, and a sine is a difference of two roots of unity divided by $2i$. Multiplied out, the condition becomes a vanishing sum of roots of unity. Bjorn Poonen and Michael Rubinstein used exactly that in 1998: they classified the short vanishing sums the condition can produce, and from the classification they wrote down the exact number of crossing points for every $n$ — a polynomial in $n$ with corrections depending on whether $n$ is divisible by 2, 4, 6, 12, 18, 24, 30, 42, 60, 84, 90, 120 and 210. Those are the $n$ whose roots of unity admit the particular sums that concurrences produce, and 30, 42 and 210, with their three prime factors, are among them for the reason the six thirtieths exist.

One consequence of their analysis is the one the 11-gon shows: a concurrence needs $n$ to be even, so every odd polygon has exactly $\binom{n}{4}$ crossings. The 12-gon, with the primes 2 and 3 and many ways for its sines to cancel, is at the other extreme.

What the loops and the tables cannot show #

The table is a finite search. It checks sums of up to ten terms for five values of $n$, and Lam and Leung’s theorem covers every $m$ and every $n$. The figure confirms the theorem where it looked; the proof, which is an induction on the number of prime factors, is not drawn.

The diagonal counts come from coordinates. The crossing points were computed in floating point and merged when they agreed to seven places; a point where two crossings are distinct but closer than that would have been merged wrongly. For odd $n$ the result was required to equal $\binom{n}{4}$, which the theorem guarantees, and for the 12-gon the count of 301 matches Poonen and Rubinstein’s formula; nothing in the figure proves that 301 is right independently.

And negative coefficients change the question. With subtraction allowed, every vanishing sum is an integer combination of turned $p$-gons for primes $p$ dividing $n$ — the theorem of Rédei, de Bruijn and Schoenberg — and the six thirtieths are a pentagon minus a triangle. The surprise lives entirely in the requirement that each root be used a non-negative number of times, which is the version that counts crossings and closes loops.

Still open: how small a non-vanishing sum can be #

A sum of $m$ roots of unity that is not zero is not zero by some margin, and the margin cannot be arbitrarily small for fixed $n$, because there are only finitely many sums. But as $n$ grows, how close to zero can a non-zero sum of $m$ roots of unity get? For two, three and four terms the answer is known, and the smallest non-zero sums shrink like a fixed power of $1/n$. Beyond that, the lower bounds anyone can prove are far smaller than the smallest sums anyone has found, and which of the two is nearer the truth is not known — a question Gerald Myerson raised in the 1980s and that is still being worked on.

The question matters beyond the circle. It controls how well-conditioned the discrete Fourier transform is on sparse signals, how close two different sums of cosines can come, and how accurately one can compute with the roots of unity in floating point. On the circle and never home met a cousin of it — how far the roots of an integer polynomial must stray from the circle — and like Lehmer’s question it is a statement about algebraic numbers that are almost, but not quite, what they would need to be for an identity to hold.

A loop made of polygons, and one that is not #

A vanishing sum of roots of unity is a closed loop of unit arrows pointing in rational directions. With one or two primes in play, every such loop is a union of regular polygons, and the number of arrows is always a sum of those primes; the six thirtieths show that a third prime lets incomplete polygons cancel each other, without changing which counts are possible. The same sums decide whether three diagonals of a polygon meet, which is why the count of crossing points is a clean $\binom{n}{4}$ for every odd polygon and an intricate formula for even ones.

The same distinction between primes and the rest runs through the whole subject. Which polygons can be drawn with ruler and compass is decided by the prime factors of $n$ too, and where the coefficients come from rests on the plainest vanishing sum of all, the full polygon, which is what makes the harmonics of a Fourier series independent of one another.

When a sum of symmetric pieces is zero, ask whether it is zero piece by piece. Usually it is, and the exceptions are few enough to classify — which is exactly what every third coefficient relied on when it averaged over the roots of unity and trusted the cancellations to be the obvious ones.