Vanishing sums of roots of unity

The Accidental Mathematician 2023-03-01

A root of unity is a complex number $z$ such that $z^n=1$ for some positive integer $n$ . This means that $z=e^{2\pi i k/n}$ for some integer $k$ ; if $k$ is relatively prime to $n$ , we say that $z$ is a primitive $n$ -th root of unity, meaning that $z$ is not a $m$ -th root of unity for any $1\leq m<n$ .

Here’s a question: when can we have

$(1) \ \ z_1+\dots +z_\ell=0$

if $z_1,\dots,z_\ell$ are roots of unity?

This is a little bit vague, in that I did not say what kind of tentative characterization we are looking for. If you were inclined to play devil’s advocate, you could say that equation (1) provides a good enough description. There are, however, less obvious answers that have come in handy in various parts of my research, so let’s look at some of them.

The Rédei-de Bruijn-Schoenberg structure theorem. The first thing to notice is that if $z_1,\dots,z_n$ is the complete set of $n$ -th roots of unity (so that $z_j=e^{2\pi i j/n}$ for all $j=1,\dots,n$ ), then $z_1+\dots+z_n=0$ . Geometrically, $z_1,\dots,z_n$ form the vertices of a regular $n$ -gon in the complex plane with the center at 0. The picture¹ at the top of this post illustrates this with $n=5$ .

If I rotate the pentagon (or more generally, an $n$ -gon) around the origin, then the center of the rotated $n$ -gon will still be at 0. Since I want the rotated vertices to be roots of unity, I’m only going to allow rotations by rational multiples of $\pi$ . Furthermore, if I add several rotated polygons like that, then the resulting sum of vanishing sums of roots of unity is, again, a vanishing sum of roots of unity.

Does this exhaust all possibilities? Yes, but with a twist: we need to be able not only to add rotated polygons, but also subtract them. Here’s an example. We start with the same pentagon as above: $1+e^{2\pi i/5}+e^{4\pi i/5}+e^{6\pi i/5}+e^{8\pi i /5}=0$ . Then we subtract a regular triangle with one vertex at 1, removing the point 1 and introducing two new points $e^{2\pi i/3}, e^{4\pi i/3}$ with negative weights. But I do not want any negative weights in my final sum, so I’m going to add two line segments (“rotated 2-gons”), or, equivalently, write $-e^{2\pi i/3}=e^{5\pi i/6}$ and $-e^{4\pi i/3}=e^{\pi i/6}$ . I’m left with 6 roots of unity that add up to 0:

$0= (1+e^{2\pi i/5}+e^{4\pi i/5}+e^{6\pi i/5}+e^{8\pi i /5})- (1+ e^{2\pi i/3}+ e^{4\pi i/3})$

$+ (e^{2\pi i/3}+e^{5\pi i/6})+(e^{4\pi i/3}+e^{\pi i/6})$

$=e^{\pi i/6}+e^{2\pi i/5}+e^{4\pi i/5}+e^{6\pi i/5}+e^{8\pi i /5}+e^{5\pi i/6}$ .

In the picture above, the circled points were added and removed. The final configuration consists of the 6 points marked solid blue. This sum is minimal, meaning that if I remove any of the 6 roots in the final sum, the rest of them cannot add up to 0. This also means that I cannot write the final sum as a combination of rotated polygons with only positive signs (without subtraction).

An additional simplification is that it suffices to use “prime polygons”, regular $p$ -gons whose number of vertices is prime. Any other regular polygon can be written as a combination of these: for example, a regular hexagon (6 is not prime) can be written as the sum of two triangles (3 is prime), one of them as above with one vertex at 1, and the other rotated by 60 degrees. Putting everything together, we have the following basic structure theorem.

Theorem (Rédei-de Bruijn-Schoenberg). Any vanishing sum of roots of unity can be written as a linear combination of rotated “prime polygons”, with integer (but not necessarily positive) coefficients.

The Chinese Remainder Theorem and its consequences. The Rédei-de Bruijn-Schoenberg theorem is a good start, but we can do more. For example, I like to use pictures and physical models. Since it’s a bit difficult to draw overlapping rotated $n$ -gons (they all look like a circle once $n$ is greater than 9 or so), I prefer to use a different geometric representation, as follows.

First, we choose $n$ so that all $z_j$ in (1) are $n$ -th roots of unity: if $z_1=e^{2\pi i k_1/n_1},\dots, z_\ell=e^{2\pi i k_\ell/n_\ell}$ , let $n$ be a common multiple of $n_1,\dots,n_\ell$ . Rewrite $z_j$ as $e^{2\pi i k_j(n/n_j)/n}$ etc., relabel the numerators $a_j=k_jn/n_j$ , and now (1) looks like this:

$(2) \ z_1+\dots+z_\ell=0$ , where $z_j=e^{2\pi i a_j/n},\ j=1,\dots,\ell$ .

With $n$ fixed, we may rewrite our conditions on $z_1,\dots,z_\ell$ in terms of the numbers $a_1,\dots,a_\ell\in\{1,2,\dots,n\}$ . Since $e^{2\pi i a_j/n}$ and $e^{2\pi i (a_j+n)/n}$ represent the same root of unity, we will consider $a_j$ as elements of the cyclic group² $\mathbb{Z}_n$ .

Assume for the moment that $n$ is square-free, meaning that $n=p_1\dots p_k$ , where $p_1,\dots,p_k$ are distinct primes. The Chinese Remainder Theorem³ says that, in this case, we can represent $\mathbb{Z}_n$ as a direct sum $\mathbb{Z}_{p_1}\oplus \dots\oplus \mathbb{Z}_{p_k}$ . In plain language, this means that a number in $\{1,2,\dots,n\}$ can be identified uniquely based on its residues mod $p_1,\dots,p_k$ . Moreover, those residues can serve as a $k$ -dimensional system of coordinates on $\mathbb{Z}_n$ . Here is a picture of how it works for $n=6=2\cdot 3$ . For example, $6\equiv 0$ modulo both 2 and 3, $4\equiv 1$ mod 3 and 0 mod 2, and so on.

Remember regular polygons? Previously, we represented the sum

$0= 1+ e^{2\pi i/3}+ e^{4\pi i/3}$

as a regular triangle. Let’s now rewrite it as a sum of 6-th roots of unity:

$0 = e^{2\pi i\cdot 6/6}+e^{2\pi i\cdot 2/6}+ e^{2\pi i\cdot 4/6}.$

(For just this triangle, I could have used $n=3$ . I’m setting up $n=6$ instead so that I can also encode a rotated triangle and rotated 2-gons, aka line segments, in the same picture. We’ll see in a moment.) This corresponds to the numerators $\{a_1,a_2,a_3\}=\{6,2,4\}$ ; these are the numbers that constitute the first row in the table above. If I rotate the triangle by 60 degrees, I get the sum

$0 = e^{2\pi i\cdot 1/6}+e^{2\pi i\cdot 3/6}+ e^{2\pi i\cdot 5/6},$

with the numerators $1,3,5$ from the second row in the table. Vanishing sums of two 6-th roots of unity, such as

$0 = e^{2\pi i\cdot 1/6}+e^{2\pi i\cdot 4/6},$

correspond to the columns in the table.

This is a special case of a general rule. If we set up $n=p_1\dots p_k$ , where $p_1,\dots,p_k$ are distinct primes, then the Chinese Remainder Theorem represents $\mathbb{Z}_n$ as a $k$ -dimensional table with one direction for each prime. Prime $p_j$ -gons, possibly rotated, correspond to columns in the $p_j$ direction in that table; we will refer to such columns as $p_j$ –fibers.

For the purpose of drawing pictures, it is more convenient to represent the elements of $\mathbb{Z}_n$ as lattice points instead of entries in a multidimensional table. The picture below shows a 3-fiber and a 2-fiber (in the polygonal representation, a triangle and a line segment) in two separate copies of $\mathbb{Z}_6$ . The numbers that these points represent can be recovered from the coordinate system.

In the next picture, we set $n=30=2\cdot 3\cdot 5$ , and draw a 5-fiber and two 2-fibers (next to each other) in $\mathbb{Z}_{30}$ .

Notice that three of the indicated points – one from the 5-fiber and two from the 2-fibers – happen to form a 3-fiber, circled in the picture below.

If we now subtract (remove) that 3-fiber, we get a new configuration of 6 points, shown below, that does not contain any fibers at all. This is the same “pentagon minus triangle plus two line segments” configuration that we looked at previously.

Here are some additional pictures from this paper with Itay Londner.

Cyclotomic polynomials. Why would vanishing sums of roots of unity appear in a paper about integer tilings? In my earlier post, I wrote about the connection between integer tilings and cyclotomic polynomials. (I also provided a short introduction to both subjects there, so I’m not going to repeat it here.) But cyclotomic polynomials are also very closely related to vanishing sums of roots of unity. Let’s go back to equation (2),

$(2) \ z_1+\dots+z_\ell=0$ , where $z_j=e^{2\pi i a_j/n},\ j=1,\dots,\ell$ ,

with $a_j\in\{1,2,\dots,n-1\}$ , and set up the polynomial $A(X)=X^{a_1}+\dots+X^{a_\ell}$ . Then (2) says that $A(e^{2\pi i/n})=0$ . The magic of algebra tells us that $A(X)$ must in fact be divisible by the whole minimal polynomial of $e^{2\pi i /n}$ , that is, the cyclotomic polynomial $\Phi_n(X)$ !

In a tiling $A\oplus B=\mathbb{Z}_M$ , each $\Phi_n(X)$ with $n|M$ and $n\neq 1$ has to divide at least one of $A(X)$ and $B(X)$ . This means many vanishing sums of roots of unity, on all intermediate scales between 1 and $M$ , associated with the projections of $A$ and/or $B$ on those scales. On the other hand, there are many vanishing sums of roots of unity that do not correspond to any tiling at all. For example, the set pictured below (consisting of three fibers in $\mathbb{Z}_{p_1p_2p_3}$ , one in each direction) represents a vanishing sum of roots of unity, but we can prove that it cannot tile $\mathbb{Z}_{p_1p_2p_3}$ .

Cuboids. How can we tell whether a set $A=\{a_1,\dots,a_\ell\}\subset \mathbb{Z}^n$ represented in this manner corresponds to a vanishing sum or roots of unity as in (2)? If the set is given explicitly, we can of course use a calculator to add up the roots of unity and see if we get 0. But there is also a nice geometric way to do it, and it still works well when we want to prove various properties of vanishing sums (or cyclotomic polynomials) without restricting to specific numerical values.

We will work again in the square-free setting, with $n=p_1\dots p_k$ , where $p_1,\dots,p_k$ are distinct primes. For the purpose of drawing pictures, we will assume that $k=3$ , but the general theory does not require that. We will also continue to use the lattice representation above.

A cuboid is a $k$ -dimensional rectangular box $\Delta$ with all edges in the cardinal direction, vertices at lattice points, and with alternating + and – signs attached to its vertices. (It can be placed anywhere in $\mathbb{Z}_n$ .)

If $A\subset \mathbb{Z}^n$ , the $\Delta$ -evaluation of $A$ is

$\mathbb{A}[\Delta]=\sum_{v}\pm \mathbf{1}_A(v),$

where $v$ ranges over all vertices of the cuboid, and the + or – signs are chosen according to the sign placed at each vertex. In other words, $\mathbb{A}[\Delta]$ = (the number of points of $A$ placed at the vertices with + sign) – (the number of points of $A$ placed at the vertices with – sign). In the example below, $A$ is the set of indicated points in $\mathbb{Z}_{30}$ (we assume that there are no points “hiding” in the back), and $\Delta$ is the cuboid in the top right corner with signs as indicated. Then $A$ includes 1 vertex of $\Delta$ with + sign, and 3 vertices with – sign. We get that $\mathbb{A}[\Delta] = 1-3=-2$ .

But look what happens when our set is a fiber $F$ (in any direction). Then any cuboid meets $F$ in exactly two points, one with + sign and the other with – sign, so that all cuboid evaluations of $F$ are zero.

Since cuboid evaluations are additive, if a set can be represented as a linear combination of fibers (possibly with cancellations), then all of its cuboid evaluations should be 0. This means that the set $A$ in the example above is not a linear combination of fibers, therefore does not correspond to a vanishing sum of roots of unity. (And yes, this can be strengthened to an “if and only if” statement.)

There’s more! With applications to questions in other areas of mathematics! But this is a bit long already, so we’ll stop here for today and come back to the subject in a future post.

¹ I’m not using alt-text for the images because the image description is already provided, to the best of my ability, in the main text. I have also tried to make the images legible if rendered without colour. But please let me know if there’s anything I missed.

² Also denoted by $\mathbb{Z}/n\mathbb{Z}$ in the literature. In some research areas, including those where I usually hang out, the shorter notation $\mathbb{Z}_n$ is preferred. However, $\mathbb{Z}_p$ with $p$ prime can also mean p-adic numbers, so that in any situation where these might come up, the preferred notation for cyclic groups is $\mathbb{Z}/n\mathbb{Z}$ .

³ There is some controversy as to whether this theorem should be named after a specific Chinese scholar instead, and if so, then how the name of that scholar should be transliterated in English. See, for example, this MathOverflow thread or this article. I would be happy to hear from anyone here, especially of Chinese descent, who might be more knowledgeable about it.