# Can a sum of roots of unity be an integer?

Let $n \geq 2$, $H \lneq (\mathbb{Z}/n\mathbb{Z})^*$, $\zeta_k$ a primitive $k$-th root of unity. Is it possible that $$\sum_{h \in H} \zeta_k^{h} \in \mathbb{Z}$$ for every $k$ dividing $n$ such that $n/k \leq |H|$?

I do not know the answer even if $k=n$. That is, can it be that $$\sum_{h \in H} \zeta_n^{h} \in \mathbb{Z}$$

## 4 Answers

Below is the original and accepted proof, but see the by a factor of $100$ simpler later proof in the OP's answer!
The answer is yes for the second question, with $n=8$, since $\zeta_8+\zeta_8^5=0$.

The answer is no for the first question. Let $\gamma_k=\sum_{h \in H} \zeta_k^{h}$ be the sum from the question, a so-called Gaussian period. For a positive integer $m$ let $\nu(m)=\epsilon\prod_{p|m}p$ ($p$ primes), where $\epsilon=2$ or $1$ if $m$ is divisible by $8$ or not, respectively. Set $G=(\mathbb Z/n\mathbb Z)^\star$, where we identify $G$ also with $\text{Gal}(\mathbb Q(\zeta_n)/\mathbb Q)$. For a divisor $m$ of $n$ and a subgroup $U$ of $G$ set $U_m=\{u\in U\;|\;u\equiv 1\pmod{m}\}$. Note that $U_m$ is a subgroup of $U$. Theorems 5 and $6$ in this paper by Evans yield the following:

• If $\gamma_k=0$, then $H_{\nu(k)}$ contains an element which is not contained in $H_k$.
• If $0\ne\gamma_k\in\mathbb Q$, then $H$ restricted to $\mathbb Q(\zeta_k)$ is the full automorphism group. Hence $\lvert H/H_k\rvert=\varphi(k)$.

From now on set $r=\nu(n)$. Clearly, $G_r$ has order $n/r$. As $H_r$ is a subgroup of $G_r$, we get that $\lvert H_r\rvert$ divides $n/r$. So $r$ divides $n/\lvert H_r\rvert$, hence $H_{n/\lvert H_r\rvert}\le H_r$. Our proof is based on the fact that actually \begin{equation}\tag{1} H_{n/\lvert H_r\rvert}=H_r. \end{equation} To see this, let $p^e$ be the highest power of a prime $p$ dividing $n$, and let $h\in H_r$ have order $m$. As $h\equiv 1\pmod{p}$, the order of $h$ modulo $p^e$ is a power $p^f\mid m$. Suppose that $p\ne2$. As the group of units modulo $p^e$ is cyclic of order $p^{e-1}$, we see that $h$ is a $p^{e-f-1}$-th power modulo $p^e$, so $h\equiv1\pmod{p^{e-f}}$. Handling similarly the case $p=2$ and applying the Chinese remainder theorem yields $h\equiv1\pmod{n/m}$. The claim follows, as $m$ divides $\lvert H_r\rvert$.

In the proof that the answer is no for the first equation, we distinguish two cases:

1. $8$ does not divide $n$, or $8$ divides $n/\lvert H_r\rvert$: Set $k=n/\lvert H_r\rvert$. So $n/k\le\lvert H\rvert$, thus $\gamma_k\in\mathbb Q$ by the assumption.
Recall that $H_k=H_r$ by (1). Furthermore, either $8$ does not divide $n$, or $8$ divides $k$. Hence $r=\nu(k)$ and therefore \begin{equation} H_k=H_r=H_{\nu(k)}. \end{equation} We see that the first alternative $\gamma_k=0$ cannot hold.
So the second alternative holds, that is, $\varphi(k)=\lvert H/H_k\rvert=\lvert H/H_r\rvert$. But $\lvert H/H_r\rvert$ divides $\varphi(r)$, so $\varphi(k)$ divides $\varphi(r)$, and therefore $k=r$. So $\lvert H_r\rvert=n/k=n/r=\lvert G_r\rvert$. We obtain $\lvert H\rvert=\varphi(r)n/r=\varphi(n)$, a contradiction.
2. $8$ divides $n$, but $8$ does not divide $n/\lvert H_r\rvert$: Again set $k=n/\lvert H_r\rvert$. Then $r=2\nu(k)$. As above \begin{equation} H_k=H_r=H_{2\nu(k)}, \end{equation} and we finish as above provided that $H_k=H_{\nu(k)}$.
So from now on we assume that $H_{2\nu(k)}\ne H_{\nu(k)}$. As $[H_{\nu(k)}:H_{2\nu(k)}]\le2$ we obtain \begin{equation} [H_{\nu(k)}:H_k]=2. \end{equation} We now show that $k'=k/2$ will work. Note that $4\mid r\mid k$, so $k'$ is even and still divides $n$. Furthermore, $n/k'=\lvert H_r\rvert/2=\lvert H_{\nu(k)}\rvert\le\lvert H\rvert$, so $\gamma_{k'}\in\mathbb Q$ by the assumption. As $k'$ is even, and $8\not\mid k$, we have $\nu(k)=\nu(k')$. Also, $\nu(k)$ divides $k/2=k'$. So \begin{equation} H_k \le H_{k'} \le H_{\nu(k)}=H_{\nu(k')}. \end{equation} But $2$ divides $k'$, while $4$ does not, so each element from $H_{\nu(k)}$ is contained in $H_{k'}$, hence $H_{k'}=H_{\nu(k')}$ and therefore the first alternative $\gamma_{k'}=0$ does not hold.
Thus $\lvert H/H_{k'}\rvert=\varphi(k')$. Recall that $[H_{k'}:H_r]=2$. As in the first case, we obtain \begin{equation} \lvert H/H_r\rvert=2\lvert H/H_{k'}\rvert=2\varphi(k')=\varphi(k), \end{equation} so $\varphi(k)$ divides $\varphi(r)$, and as above we obtain the contradiction $\lvert H\rvert=\varphi(n)$.
• The Evans paper is interesting, but I haven's studied it fully yet. I also found a simple proof for all prime powers, and will write this up maybe later today. – Lucia Sep 5 '14 at 21:14
• That's very nice! – Lucia Sep 9 '14 at 13:56

If $n$ is square-free this cannot happen (even just for the case $k=n$), and if $n$ is not square-free (and in the case $k=n$) one must have the sum being zero if it is an integer (as seen in Peter Mueller's answer). To see this, note that when $\zeta_n$ runs over all primitive $n$-th roots of unity the corresponding sums $\sum_{h \in H} \zeta_n^h$ are Galois conjugates. So if one of these sums is an integer, they all are and equal the same integer $a$ say. Thus summing over all the primitive $n$-th roots of unity, we get (with $*$ indicating a sum over primitive $n$-th roots) $$\phi(n) a = \sum_{\zeta_n}^*\sum_{h\in H} \zeta_n^h = \sum_{h\in H} \sum_{\zeta_n }^*\zeta_n^h.$$ The inner sum is a Ramanujan sum and equals $\mu(n)$. Thus $$\phi(n) a = \mu(n) |H|.$$ Since $|H|<\phi(n)$ it follows that if $\mu(n)\neq 0$ then $a$ cannot be an integer, and if $n$ is not square-free then the only possibility is for $a=0$ (and this can arise).

Additional comments: The argument above settles the second problem, but resolves the first only when $n$ is square-free. In general, it shows that if $k$ is the largest squarefree divisor of $n$ then we must have either $\phi(k)$ divides $|H|$, or we must have $|H|< n/k$. These conditions are restrictive, but not enough to settle the problem. A modification to the argument does resolve the problem completely when $n$ is a prime power: an argument for prime squares was given by Peter Mueller (based on a result of Diamond, Gerth and Vaaler).

Suppose now that $n=p^a$ is a prime power, and suppose $p^b \le |H| <p^{b+1}$ with $0\le b\le a-1$. Parseval's identity gives $$p^a |H| = \sum_{\zeta^{n}=1} \Big| \sum_{h\in H} \zeta^h\Big|^2 = \sum_{k|n} \sum_{\zeta_k}^{*} \Big|\sum_{h \in H} \zeta_k^h \Big|^2.$$ Now above split into the cases when $k < n/|H|$ (which is equivalent to $k$ being a power of $p$ at most $p^{a-b-1}$) and when $k\ge n/|H|$ (the remaining powers of $p$ up to $p^a$). In the first case use the trivial bound that $\Big|\sum_{h\in H} \zeta_k^h \Big| \le |H|$. In the second case use the hypothesis of the problem, and our work above which shows that $\sum_{h\in H} \zeta_k^h = \mu(k)|H|/\phi(k)$. Thus we obtain $$p^a |H| \le \sum_{k=p^{c}, 0\le c\le a-b-1} |H|^2 \phi(p^c) + \sum_{c=a-b}^{a} \frac{|H|^2 \mu(p^c)^2 }{\phi(p^c)}.$$ If $a-b\ge 2$, this inequality cannot hold (the second term in the RHS is zero, and the first is $\le |H|^2 p^{a-b-1} < p^a |H|$). If $a-b=1$, then the inequality above gives $p^a |H| \le |H|^2 (p/(p-1))$, or in other words forces $H$ to be all of $({\Bbb Z}/p^a{\Bbb Z})^*$.

• This neatly deals with $k=n$. When $k$ is a proper divisor of $n$, we need to sum over primitive $k$-th roots of unity, and get $\phi(k)a=\mu(k)|H|$, and now we can have $\phi(k)\le|H|$ - and the trace $a$ can be a nonzero integer. Example: $n=45$, $|H|=8$, and $n/k=3$ with trace $1$. This is not yet a counterexample to the original question since $n/k=5<|H|$ still gives an irrational trace. – GNiklasch Sep 4 '14 at 18:20
• @GNiklasch: The question is a bit unclear to me. It seems to want integrality for every $k$ dividing $n$ in a certain range (but maybe this is just an unclear formulation). And, $k=n$ is permitted and seems to impose already a very strong restriction. – Lucia Sep 4 '14 at 18:22
• Right. I'm just clarifying that we can conclude that $0$ is the only possible rational integer trace when $k=n$, but we can't automatically conclude this for the $k<n$. – GNiklasch Sep 4 '14 at 18:33

We suppose towards a contradiction that all the sums in the first question are integers. Set $$f(x) = \prod_{h \in H}(x - \zeta_n^h)$$

We claim that all symmetric polynomials in the roots of $f$ are integers, for which it is enough to show that for each $1 \leq d \leq |H|$ $$\sum_{h \in H} \zeta_n^{dh} \in \mathbb{Z}$$ but this is true by our assumption since $\zeta_n^d = \zeta_k$ for some $k$ dividing $n$ with $n/k \leq |H|$ from the inequality for $d$. This shows that $f \in \mathbb{Z}[x]$ is of degree smaller than $\phi(n)$ (since $H$ is proper) having $\zeta_n$ as a root, contradiction.

• Certainly missed that! I'm curious how you came across this problem. – Lucia Sep 12 '14 at 16:52
• Ah, that's the trick I had been missing. When I passed from divisors $k$ of $n$ to $d=n/k$ dividing $n$, I failed to see that conversely we can take any $d$ in the size range and return to a divisor $k = n/\mathrm{gcd}(n,d)$ of $n$ of the right size. So we do have constraints on all the power sums and therefore on all the coefficients of $f$. Neat. And a curious mental block on my part... – GNiklasch Sep 12 '14 at 16:57
• I tried to find a new proof for the irreducibility of the cyclotomic polynomials and found that this is equivalent to these character sums being integral, and hoped for a simple argument for this. – Pablo Sep 12 '14 at 17:03
• @PeterMueller: OK, I will remove mine, too. – GH from MO Jun 28 '16 at 21:33

EDITED Despite the upvotes, the first version of this answer was mostly wrong, and I cannot delete it since it has been accepted. Let me see what can be salvaged.

Fix $\zeta_n$, identify $(\mathbb{Z}/n\mathbb{Z})^*$ in the usual way with the Galois group of $\mathbb{Q}(\zeta_n)$ over $\mathbb{Q}$, let $K$ be the fixed field corresponding to $H$, with ring of integers $\mathcal{O}_K$, and replace $n/k$ with $d$. Then you are asking whether the traces $$\sum_{h\in H} (\zeta_n^d)^h = \sum_{h\in H} (\zeta_n^h)^d$$ as $d$ ranges over the divisors of $n$ up to the degree of $\mathbb{Q}(\zeta_n)$ over $K$ (which equals $\left|H\right|$) can all be rational integers. These are the second-highest coefficients of the characteristic polynomials of the $\zeta_n^d$ over $K$. They're obviously algebraic integers so the question is whether they can all be rational.

If we didn't have the restriction that $d$ has to divide $n$, and were instead looking at all the $d$ up to $\left|H\right|$, then we could express all the coefficients of the minimal polynomial of $\zeta_n$ over $K$ in terms of them, and we'd be done: that minimal polynomial lives in $\mathcal{O}_K[X]$ and divides, in this ring, the cyclotomic polynomial $\Phi_n$, so if it were also in $\mathbb{Q}[X]$ then it would be in $\mathbb{Z}[X]$, and so would be the quotient of $\Phi_n$ by it. But $\Phi_n$ is irreducible in $\mathbb{Z}[X]$, so this could only happen when the quotient is $1$, i.e. when $K=\mathbb{Q}$ and thus $H=(\mathbb{Z}/n\mathbb{Z})^*$.

I'm not sure offhand what can happen in the original situation where we consider only the $d$ dividing $n$.

LATE EDIT (In fact, the remaining $d$ take care of themselves: see Pablo's own answer.) /LATE EDIT

For $d=1$, we can certainly have a rational integer trace - in fact, it can be zero. (Consider $n=12$ and $K=\mathbb{Q}(\zeta_{12}^2)$.)

• In fact, when we're allowed to consider $d=|H|$, the trace for this $d$ can't be rational because it is an integer multiple of $\zeta_n^d\in K$, and $\zeta_n^d$ cannot be $\pm1$ under the stated conditions. But in general $|H|$ won't divide $n$. – GNiklasch Sep 4 '14 at 17:12
• I don't understand your comment. With $n=8$ and $H=\{1,3\}$ you get $\zeta_4+\zeta_4^3=0$. Also nonzero rational traces are possible: $n=12$, $H=\{1,11\}$. Then $\zeta_6+\zeta_6^{11}=1$. – Peter Mueller Sep 10 '14 at 15:03
• @PeterMueller - I don't understand it anymore either. I had extra conditions on $H$ on my mind (conditions which also ensured that the $d=1$ trace summed to zero), but my brain wasn't connected to my fingers. I hope OP will yet return and unaccept this answer and accept your complete answer instead! – GNiklasch Sep 10 '14 at 17:33