# How small can a sum of a few roots of unity be?

Let $n$ be a large natural number, and let $z_1, \ldots, z_{10}$ be (say) ten $n^{th}$ roots of unity: $z_1^n = \ldots = z_{10}^n = 1$. Suppose that the sum $S = z_1+\ldots+z_{10}$ is non-zero. How small can $|S|$ be?

$S$ is an algebraic integer in the cyclotomic field of order $n$, so the product of all its Galois conjugates has to be a non-zero rational integer. Using the utterly crude estimate that the magnitude of a non-zero rational integer is at least one, this gives an exponential lower bound on $S$. On the other hand, standard probabilistic heuristics suggest that there should be a polynomial lower bound, such as $n^{-100}$, for $|S|$. (Certainly a volume packing argument shows that one can make $S$ as small as, say, $O(n^{-5/2})$, though it is unclear to me whether this should be close to the true bound.) Is such a bound known? Presumably one needs some algebraic number theoretic methods to attack this problem, but the only techniques I know of go through Galois theory and thus give exponentially poor bounds.

Of course, there is nothing special about the number $10$ here; one can phrase the question for any other fixed sum of roots, though the question degenerates when there are four or fewer roots to sum.

-
(In case it's not obvious, I did not actually have any substantive ideas about the question at hand while walking with the kids, though I did buy a cute little drum shaped like a frog.) –  JSE Nov 14 '10 at 23:05
My paper with Tate proves that the p-adic absolute value is bounded below by a constant independent of n. Of course, one can't expect that in the archimedian case. –  Felipe Voloch Nov 15 '10 at 1:54
Having only a very poor grasp of Galois theory (in fact, even that is a rather flattering way of putting it), I'd be interested by an elaboration of your remark that going through Galois theory automatically leads to exponentially poor bounds. –  gowers Nov 15 '10 at 12:04
@Jordan: The set of (all) roots of unity is discrete in the p-adic topology but not in the complex topology, this already shows things will be different. I am not quite sure how to answer your "Why?". –  Felipe Voloch Nov 15 '10 at 15:25
Tim: The Galois group of the cyclotomic field has order phi(n), so unless one is somehow extremely careful not to lose a multiplicative factor for each Galois conjugate, attempting to control the algebraic integer S by analysing all the phi(n) Galois conjugates together would lead to inefficiencies that are exponential in phi(n). Perhaps there is a more "additive" way to exploit the Galois conjugates that would only lose polynomial factors rather than exponential ones, but it's hard to see how additive methods (e.g. moments) can lead to lower bounds on magnitudes, rather than upper bounds. –  Terry Tao Nov 15 '10 at 16:24

http://www.jstor.org/stable/2323469

-
The author of the above paper is a frequent MO commmenter, so I hope we'll have an authoritative answer shortly. Gerry Myerson, I summon thee! –  JSE Nov 14 '10 at 21:35
Regret to say the paper contains all I know about the question. There's a small contribution by Dean Hickerson mentioned on page 967 of Richard Guy's "Monthly Unsolved Problems, 1969-1987," Monthly 94 (Dec. 1987). An earlier reference of which I was unaware in 1986 is Graham and Sloane, Anti-Hadamard matrices, freely available at neilsloane.com/doc/1218anti.ps On p. 11, they ask, "What is the smallest magnitude of any nonvanishing sum of distinct $n$-th roots of unity?" More references next comment: –  Gerry Myerson Nov 14 '10 at 23:34
I D Shkredov, Fourier analysis in combinatorial number theory, Russian Math Surveys 65:3 (2010) 513-567, writes on pp 544-545, "We conclude this section by discussing the question of how small the Fourier coefficient of a characteristic function can be. This problem was first considered in [132]." That's my paper, though I certainly did not use those terms. They give an estimate and source it to V F Lev, Linear equations over ${\bf F}_p$ and moments of exponential sums, Duke Math J 107 (2001) 239-263. –  Gerry Myerson Nov 14 '10 at 23:39
On re-reading my paper, I find that in fact I was aware of the Graham-Sloane paper at the time, as it's in the references. Also I should note that much of the paper is about the general case, not just the case of 5 roots. In particular, for 10 roots, the equation $1^r+5^r+9^r+17^r+18^r=2^r+3^r+11^r+15^r+19^r$, which holds for $0\le r\le4$, leads, by the method explained in the paper, to a non-zero sum of 10 $n$th roots of modulus $Cn^{-5}+O(n^{-6})$ for even $n$. –  Gerry Myerson Nov 15 '10 at 3:35
The OEIS sequence oeis.org/A108380 gives the least number of distinct n-th roots of unity summing to the smallest possible nonzero magnitude. There is also a plot of the least magnitude for n up to 81. –  tdnoe Nov 16 '10 at 18:35
show 1 more comment

From a computational point of view one can probably use the LLL algorithm for getting fairly good solutions: Indeed consider the sublattice of $\mathbb Z^{n+2}$ spanned by integral vectors of the form $(0,\dots,0,1,0,\dots,\lfloor A\cos(2\pi k/n)\rfloor,\lfloor A\sin(2\pi k/n)\rfloor)$. Fine-tuning of the the real number $A$ (which has to be choosen not too small) and searching for a short vector in this lattice yields solutions. Using known bounds for lattice packings yields perhaps some useful upper bounds (but the computations are probably a little tricky).

-
I'd love to see someone implement this and get some numbers out. –  Gerry Myerson Nov 15 '10 at 20:53
In the event that n is even wouldn't you get pairs of vectors whose last two components were antipodal giving a sum of weight 2? –  Aaron Meyerowitz Nov 16 '10 at 3:49
Likewise if 3|n with triples, etc.; and when there are several small factors one can combine dependencies in somewhat less transparent ways – e.g. we have $0 = e(0)+e(1/5)+e(2/5)+e(3/5)+e(4/5)$ $= -e(1/2)+e(1/5)+e(2/5)+e(3/5)+e(4/5)$ $= e(1/6)+e(5/6) + e(1/5)+e(2/5)+e(3/5)+e(4/5)$, giving a vanishing sum of the 5th, 25th, 6th, 12th, 18th, and 24th powers of a primitive 30th root of unity. –  Noam D. Elkies Jul 3 '11 at 14:49

To expand on the Prouhet-Tarry-Escott problem, this is to find (multi)-sets of integers $A$ and $B$ with $\sum_Aa^k=\sum_Bb^k$ for $0 \le k \le m-1$. Then $|A|=|B|$ and perhaps one can always get $|A|=m$ although no-one really knows. This translates into ways to choose $n=2|A|$ Nth roots of unity (at least for even N): take the set $S$ consisting of the $n$ roots $\alpha^a$ and $-\alpha^b$ where $\alpha=e^\frac{2\pi i}{N}$. Note that -1 is a power of $\alpha$. I'm not sure what to do when $n$ and/or $N$ is odd but other people probably do. Fast forwarding over some details, one ends up with a polynomial of the form $(\alpha-1)^kg(\alpha)$ and that first factor gives the whole thing a size $O(\cos(\frac{2\pi}{N})^k)=O(N^{-k})$ The constant is easily computable although kind of large and requiring a fairly large $N$ to be accurate (for n=10 I got multi-digit accuracy by N=1000 although maybe N=100 was ok too). A reference I like is P. Borwein, C. Ingalls, The Prouhet-Tarry-Escott Problem revisited.

The referenced article by G. Myerson says (if my quick read is correct) that an approximately equal spacing around the unit circle can be $O(N^{-1})$ but not better but that no one knows a general construction which is better. It is intriguing that the solution sketched above has no special use of the number theoretic properties of $N$ except parity. Perhaps (some of) the best solutions (for an even number of roots) involve roots from 2 thin wedges which are nearly antipodal. For 4 roots the optimum is to take 1 twice and two other roots one on each side of -1.

-
@Aaron, the article is by this guy, not that Guy. –  Gerry Myerson Nov 15 '10 at 20:58
AHA. respect respect. Well written column. I see now that his name was there as editor of the column. I did say it was a quick read. It is the kind of thing he might like. –  Aaron Meyerowitz Nov 15 '10 at 21:57
G. Myerson's argument can be used recursively to establish bounds for the sum of $N>10$ $n$-th roots of unity. For instance, start from $N=10$. Let us denote $\omega=\exp\frac{2i\pi}{n}$. GM's construction uses only the roots $\omega^k$ for $1\le k\le18$ and $\frac{n}{2}\le k\le\frac{n}{2}+19$ (say that $n$ is even). The corresponding sum is $z_n\ne0$ such that $|z_n|\le Cn^{-5}$. Now, say that $n$ is a multiple of $38$ ($n=38m$) and let us cover the complex plane by $m$ disjoint sectors of angle $\frac{\pi}{m}$. Each sector can be used to construct an other point, and the $m$ points obtained that way form a regular $m$-agon. Here is the induction argument: we may sum $10$ such points in order to obtain a point $z'$ with $z'=z_nz_m$. Now, $z'$ is the sum of $N'=100$ distinct $n$-th roots of unity, and we have $$|z'|\le Cn^{-5}\left(\frac{n}{38}\right)^{-5}=C'n^{-10}.$$ More generally, if $N=10^r$, we obtain a sum of $N$ $n$-th roots of unity ($n$ a multiple of $38^{r-1}$) of the form $Cn^{-\alpha}$ with $\alpha=5r=5\log_{10}N$.
Edit. Alternate description (but this is the same construction). Let $J$ be the set of exponents used by GM when $N=10$, that is $J=\{1,5,9,17,18\}\cup\left(\frac{n}{2}+\{2,3,11,15,19\}\right)$. For $N=100$ and $n$ a multiple of $38$, set $$z':=\sum_{i\in J}\sum_{j\in J}\omega^{i+38j}.$$ If $n$ is large enough, this is a sum of distinct $n$th roots of unity, such that $z'=z_nz_m$.
I'm not sure I understand the construction, but I think it's unnecessarily complicated. Just take a sum of 10 $n$th roots of modulus $O(n^{-5})$ and square it to get a sum of 100 (not necessarily distinct) $n$th roots of modulus $O(n^{-10})$. Or raise it to the power $r$ to get $10^r$ $n$th roots whose sum has modulus $O(n^{-5r})$. But don't the known Tarry-Escott solutions mentioned in my paper do better than that? –  Gerry Myerson Nov 15 '10 at 11:17
@Denis, OP didn't ask for distinct roots of unity so I assume it's no issue. Tarry-Escott just means $\sum^ma_i^r=\sum^mb_i^r$ for $r=1,\dots,k$ with no $a_i=b_j$, preferably with $m$ as small as possible. The paper shows how to go from such an equation to a small sum of $2m$ roots of unity. It's known $m$ can be taken to be something like $k^2$, and the paper indicates how small a sum that leads to. –  Gerry Myerson Nov 15 '10 at 20:51