# Uniqueness of sums of roots of unity

Let $\zeta:=e^{\frac{2\pi i}{n}}$, with $n\geq4$, and let $2\leq k\leq n-2$.

Let us suppose that the prime factorization of $n$ is $n=p_1^{\alpha_1}\cdot\dots\cdot p_s^{\alpha_s}$, with $\alpha_i>0$ and $p_1<p_2<\dots<p_s$.

Suppose moreover that $k<p_1$, and that $1\leq i_1<\dots<i_k\leq n$ and $1\leq j_1<\dots<j_k\leq n$ are such that $$\zeta^{i_1}+\dots+\zeta^{i_k}=\zeta^{j_1}+\dots+\zeta^{j_k}.$$

How to prove that $i_h=j_h$ for all $h=1,\dots, k$? This should be a generalization of

Are all sums of subsets of roots of unity unique?

• if $n = p$, then $\zeta^{i_1}+\dots+\zeta^{i_k}=\zeta^{j_1}+\dots+\zeta^{j_k}$ can be re-written as $P(x) = \sum_{h=0}^{p-1} a_h x^h, a_h \in \{-1,0,1\}$ vanishes at $\zeta$. But it means $P(x) = Q(x) \Phi_p(x)$ and since $P, \Phi_p$ are of degree $p-1$ it means $Q = 0$ or $1$ so that $k = 0$ or $k=p-1$ and $i_h = j_h$ – reuns Jul 22 '16 at 16:35
• Yes, indeed this is the proof for the case $n=p$. To what extent is this argument generalizable to generic $n$? – itotcg Jul 22 '16 at 17:01
• with $n = \prod p_s$ you can say the same : that $P$ is divisible by one of the $\Phi_{p_s}$, and since $k < p_1$... ? – reuns Jul 22 '16 at 17:06
• The argument under discussion gives that $P$ is divisible by $\Phi_n$ itself, not some $\Phi_p$. But the key obstacle seems to be to use the fact that $k$ is small, even when $i_k,j_k$ (hence $\deg P$) can be large. (To add some context, presumably known to the OP: if $k=p_1$ then we get counterexamples like $\sum_{j=1}^{p_1} \zeta^{jn/p_1} = 0 = \sum_{j=1}^{p_1} \zeta^{1+(j-1)n/p_1}$.) – Greg Martin Jul 22 '16 at 17:10
• For the case $n$ squarefree I've found the answer hidden in literature. By a straightforward specialization of Theorem 4.1 of the paper arxiv.org/pdf/math/9511209v1.pdf (I will adopt its notations) to the case in which $x$ and $y$ have the same number of non-zero coefficients, i.e. we have $\varepsilon_0(x)=\varepsilon_0(y)$, we necessarily conclude to be in the CASE A. But now the rôle of $x$ and $y$ is symmetric, so we deduce $x=y$. – itotcg Jul 23 '16 at 8:24

You can prove this by using a result of H. B. Mann to reduce to the case that $n$ is squarefree, and then applying the Lam-Leung result mentioned in one of the comments above.
Theorem 1 of Mann's paper "On linear relations between roots of unity" (Mathematika 12 (1965), 107-117) says the following. Let $\zeta_1,\dots,\zeta_r$ be roots of unity and let $a_1,\dots,a_r$ be nonzero integers. Suppose that $\sum_{i=1}^r a_i \zeta_i = 0$ but that there is no nonempty proper subset $S$ of $\{1,2,\dots,r\}$ for which $\sum_{i\in S} a_i \zeta_i = 0$. Then for each $i$ and $j$ we have $(\zeta_i/\zeta_j)^m=1$ where $m$ is the product of the primes which are $\le r$.
To deduce what you want, start with your equality $$\zeta^{i_1}+\dots+\zeta^{i_k}=\zeta^{j_1}+\dots+\zeta^{j_k}.$$ First remove any terms which appear on both sides of the equation, to get a similar equation but possibly with a smaller value of $k$; I will assume that the resulting equation still contains some roots of unity (which will lead to a contradiction). Next multiply both sides of this last equation by the reciprocal of one of the roots of unity appearing in the equation, in order to obtain a similar equation in which one of the roots of unity equals $1$. As noted in one of the comments above, if every root of unity appearing in this last equation has squarefree order then we get a contradiction from Theorem 4.1 of Lam-Leung's paper "On vanishing sums of roots of unity" (J.Algebra 224 (2000), 91-109). So assume that some root of unity in the equation does not have squarefree order. Subtract the right side of the equation from the left to get $\sum_{i=1}^r a_i\zeta_i=0$ where $r\le 2k$, each $a_i$ is in $\{1,-1\}$, and $\zeta_1,\dots,\zeta_r$ are distinct $n$-th roots of unity. If there exists a nonempty proper subset $S$ of $\{1,2,\dots,r\}$ for which $\sum_{i\in S} a_i \zeta_i = 0$ then the smallest such $S$ has size at most $r/2$ which is at most $k$, whence by Mann's theorem any distinct $i,j\in S$ satisfy $(\zeta_i/\zeta_j)^m=1$ where $m$ is the product of the primes which are $\le k$. But also $(\zeta_i/\zeta_j)^n=1$ where $n$ is coprime to $m$, so that $\zeta_i/\zeta_j=1$, contrary to our hypothesis that $i,j$ are distinct. Hence there is no such subset $S$, so by Mann's theorem there is a squarefree positive integer $m$ such that all $i,j$ with $1\le i,j\le r$ satisfy $(\zeta_i/\zeta_j)^m=1$. Since some $\zeta_j$ equals $1$, it follows that $\zeta_i^m=1$ for each $i$, contradicting our assumption that some root of unity in the equation does not have squarefree order.
Incidentally, the proof of Mann's theorem is beautiful. Let me just give the first step to convey the flavor. Let $\zeta_1,\dots,\zeta_r$ be roots of unity and let $a_1,\dots,a_r$ be nonzero integers such that $\sum_{i=1}^r a_i \zeta_i = 0$. Let $n$ be the least common multiple of the orders of the $\zeta_i$'s. Suppose that $n$ is divisible by the square of some prime $p$. Let $\zeta$ be a primitive $n$-th root of unity, and write $\zeta_i=\zeta^{c_i}$ for some integer $c_i$. Then write $c_i=pd_i+e_i$ with $d_i,e_i\in\mathbf{Z}$ and $0\le e_i\le p-1$. This yields $\sum_{i=1}^r a_i (\zeta^p)^{d_i} \zeta^{e_i} = 0$, which is a vanishing linear combination of $\zeta^0,\zeta^1,\dots,\zeta^{p-1}$ having coefficients in the field $\mathbf{Q}(\zeta^p)$. But $$[\mathbf{Q}(\zeta):\mathbf{Q}(\zeta^p)]=\frac{[\mathbf{Q}(\zeta):\mathbf{Q}]}{[\mathbf{Q}(\zeta^p):\mathbf{Q}]}=\frac{\varphi(n)}{\varphi(n/p)}=p,$$ so that every coefficient in this linear combination must be zero. (!!!) Hence for each $t$ with $0\le t\le p-1$, the sum of the values $a_i (\zeta^p)^{d_i}$ over all $i$'s with $e_i=t$ must be zero. And so on. The whole proof takes less than a page.
• @Michael Zieve. After reducing to the case of square free n, given hypothesis states we are considering sums of various distinct $\zeta ^r$ with $r$ relatively prime to $n$. But by normal basis theorem they form a basis and should be linearly independent. Is this argument ok? – P Vanchinathan Jul 23 '16 at 11:44
• @P Vanchinathan. I don't see how the hypotheses force $r$ to be relatively prime to $n$. It was never assumed that the $\zeta_i$ are primitive $n$-th roots of unity, only that they are $n$-th roots of unity. – Michael Zieve Jul 23 '16 at 13:52
• My mistake. I read the hypothesis $k\leq p_1$ and thought powers themselves are less than $p_1$. It is simply the count of powers that is less than $p_1$. – P Vanchinathan Jul 24 '16 at 0:32