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}$$
 A: 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)$.)
A: 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})^*$.
A: 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:


*

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


* $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)$.
 
A: 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.
