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

Question

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.

Answer 1

In this paper they talk about this problem for 5 instead of 10 roots.

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

EDIT: In view of Todd Trimble's comment, here's a summary of what's in the paper.

Let $f(k,N)$ be the least absolute value of a nonzero sum of $k$ (not necessarily distinct) $N$-th roots of unity. Then

$f(2,N)$ is asymptotic to $cN^{-1}$, where $c$ is $2\pi$ for even $N$, $\pi$ for odd $N$,

$f(3,N)$ is asymptotic to $cN^{-1}$, where $c$ is $2\pi\sqrt3$ for $N$ divisible by 3, $2\pi\sqrt3/3$ otherwise,

$f(4,N)$ is asymptotic to $cN^{-2}$, where $c$ is $4\pi^2$ for even $N$, $\pi^2$ for $N$ odd,

$f(k,N)>k^{-N}$ for all $k,N$,

$f(2s,N)<c_sN^{-s}$ for $N$ even and $s\le10$,

$f(k,N)<c_kN^{-[\sqrt{k-6}]-1}$ for $N$ even and $k>5$, and

If $N$ is twice a prime, and $k<N/2$, then there exists $k'<2k$ such that $f(k',N)\le2k2^{k/2}\sqrt{k!}N^{-k/2}$.

The only result in the paper for 5 roots of unity is (the trivial) $f(5,N)>5^{-N}$, but it is suggested that maybe $f(5,N)>cN^{-d}$ for some $d$, $2\le d\le3$, and some $c>0$.

Answer 2

This question grabbed my attention a couple of years ago and I've just put a paper on the arXiv with new upper bounds for $k=5$. I began by computing lots of data, then teased out the structure of particularly well-performing configurations. The headline is that $f(5,n) = O(n^{-4/3})$, improving to $O(n^{-7/3})$ infinitely often.

The first picture that really caught my eye was this one, which shows a large dip in the minimum length for $n \approx 10 000$ (log-log scales) when we only look at $n \equiv 11 \mod 12$.

Looking at the points in the dip led to me scribbling this page.

These small sums arise from two ideas: that $1 + \omega + \omega^2 + i + (-i) = 0$ (writing $\omega$ for the primitive third root), and that perturbations of this configuration can also be small when they are related to close rational approximations of $\sqrt 3$.

There are also places with dips corresponding to perturbations of the set of fifth roots of unity, relying on close rational approximations to the golden ratio $\phi$. This is easier to work with than $\sqrt 3$, so most of the arguments in the paper are in that setting. (It's easier to work in prescribed congruence classes, for example, because the convergents to $\phi$ have a very simple structure.) I also mention perturbing other configurations which sum to zero, with no concrete improvements but greater possibilities for analysis by more sophisticated means.

My code and data aren't anywhere online right now, but that's only because I haven't decided on a good stable place to post them. I'll happily share them with anyone who's interested.

e: The perfect is the enemy of the good, so my code and data are at least temporarily available at https://babarber.uk/583/small-sums-of-five-roots-of-unity/

Answer 3

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).

Answer 4

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.

Answer 5

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$.

Answer 6

This is not an answer to the question, but I think it is somewhat related, and while the question deals with cyclic groups, this result deals with generalized characters of arbitrary finite groups. After several attempts, I managed to prove a few years ago that if $G$ is a finite group with its largest irreducible character degree $d$, then we always have $\sum_{ 1 \neq x \in G} |\theta(x)|^{2} \geq \frac{|G|}{d} - 1$ whenever $\theta$ is a generalized character (ie $\mathbb{Z}$-combination of irreducible characters) other than a multiple of the regular character of $G$ (the regular character takes value $|G|$ on $1_{G}$ and $0$ on all non-identity elements). I've always hoped, but never really succeeded to date, to find a good application of this.

Note that when $G$ is Abelian, this gives (without Galois theory) that the mean squared (absolute) value of a generalized character (excluding the regular character and its multiples) on non-identity elements is at least one. But when $G$ is non-Abelian, the result gives that the mean-square (absolute) value of a generalized character $\theta$ (other than a multiple of the regular character) might be closer to $\frac{1}{d}$, where $d$ is the maximal degree of a complex irreducible character of $G$ (note however that $\theta$ may vanish on some elements). Equality in the the bound does occur when $G$ is Abelian, or when $G$ is a Frobenius group with Abelian Frobenius kernel of index $d$ for a suitable generalized character $\theta.$