107
$\begingroup$

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.

$\endgroup$
19
  • 3
    $\begingroup$ If we get a good answer to this one, I'm going to ask: if G is a finite group and rho: G -> M_n(C) an irreducible representation, how close can a nonzero sum rho(g_1) + ... rho(g_10) be to the zero matrix? Terry's question is the case G = Z/nZ. $\endgroup$
    – JSE
    Nov 14, 2010 at 23:04
  • 27
    $\begingroup$ (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.) $\endgroup$
    – JSE
    Nov 14, 2010 at 23:05
  • 4
    $\begingroup$ 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. $\endgroup$ Nov 15, 2010 at 1:54
  • 4
    $\begingroup$ @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?". $\endgroup$ Nov 15, 2010 at 15:25
  • 5
    $\begingroup$ 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. $\endgroup$
    – Terry Tao
    Nov 15, 2010 at 16:24

6 Answers 6

62
$\begingroup$

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

$\endgroup$
9
  • 17
    $\begingroup$ 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! $\endgroup$
    – JSE
    Nov 14, 2010 at 21:35
  • 29
    $\begingroup$ 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: $\endgroup$ Nov 14, 2010 at 23:34
  • 6
    $\begingroup$ 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. $\endgroup$ Nov 14, 2010 at 23:39
  • 9
    $\begingroup$ 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$. $\endgroup$ Nov 15, 2010 at 3:35
  • 5
    $\begingroup$ 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. $\endgroup$
    – tdnoe
    Nov 16, 2010 at 18:35
20
$\begingroup$

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

log-log plot of f(5,n)

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

working out the structure of these examples

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/

$\endgroup$
12
$\begingroup$

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

$\endgroup$
5
  • 2
    $\begingroup$ I'd love to see someone implement this and get some numbers out. $\endgroup$ Nov 15, 2010 at 20:53
  • $\begingroup$ 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? $\endgroup$ Nov 16, 2010 at 3:49
  • 1
    $\begingroup$ 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. $\endgroup$ Jul 3, 2011 at 14:49
  • $\begingroup$ @GerryMyerson, I have a moderate amount of data (computed by other means) that I'd be happy to share with you but can't sensibly post as an answer. $\endgroup$
    – Ben Barber
    Aug 1, 2019 at 19:21
  • $\begingroup$ @Ben, I'm always happy to see work on this problem. $\endgroup$ Aug 1, 2019 at 22:51
6
$\begingroup$

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.

$\endgroup$
2
  • 10
    $\begingroup$ @Aaron, the article is by this guy, not that Guy. $\endgroup$ Nov 15, 2010 at 20:58
  • $\begingroup$ 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. $\endgroup$ Nov 15, 2010 at 21:57
5
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$ Nov 15, 2010 at 11:17
  • $\begingroup$ @Gerry. My purpose was to sum distinct roots of unity. Isn't it an issue ? Bwt, I did not-find the term Tarry-Escott in your paper. $\endgroup$ Nov 15, 2010 at 11:53
  • 1
    $\begingroup$ @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. $\endgroup$ Nov 15, 2010 at 20:51
4
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.