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 4


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)$.
  • $\begingroup$ 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. $\endgroup$
    – Lucia
    Sep 5, 2014 at 21:14
  • $\begingroup$ That's very nice! $\endgroup$
    – Lucia
    Sep 9, 2014 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})^*$.

  • $\begingroup$ 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. $\endgroup$
    – GNiklasch
    Sep 4, 2014 at 18:20
  • $\begingroup$ @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. $\endgroup$
    – Lucia
    Sep 4, 2014 at 18:22
  • $\begingroup$ 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$. $\endgroup$
    – GNiklasch
    Sep 4, 2014 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.

  • $\begingroup$ Certainly missed that! I'm curious how you came across this problem. $\endgroup$
    – Lucia
    Sep 12, 2014 at 16:52
  • $\begingroup$ 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... $\endgroup$
    – GNiklasch
    Sep 12, 2014 at 16:57
  • $\begingroup$ 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. $\endgroup$
    – Pablo
    Sep 12, 2014 at 17:03
  • $\begingroup$ @PeterMueller: OK, I will remove mine, too. $\endgroup$
    – GH from MO
    Jun 28, 2016 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)$.)

  • $\begingroup$ 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$. $\endgroup$
    – GNiklasch
    Sep 4, 2014 at 17:12
  • $\begingroup$ 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$. $\endgroup$ Sep 10, 2014 at 15:03
  • $\begingroup$ @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! $\endgroup$
    – GNiklasch
    Sep 10, 2014 at 17:33

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.