# A cyclotomic polynomial whose index has a large prime divisor cannot be too sparse

Working on this recent MSE question, I was led to the following conjecture :

Suppose that $n$ is an integer with at least one prime divisor $\geq 7$. Then $\Phi_n$ has at least seven non-zero coefficients.

I have checked this conjecture up to $n\leq 10^5$. It is not hard to treat the case when $n$ is of the form $p^a$ with $p\geq 7$. In the general case $n$ will be of the form $n=p^a m$ with $m$ coprime to $p$, and $\Phi_n=\Phi_{p^{a}}\Phi_m$. What is unclear to me is how non-zero coefficients are somewhat "preserved" when we multiply by $\Phi_m$ where $m$ is coprime to $p$.

UPDATE (10/18/2014) : One can assume without loss of generality that $n$ is square-free. Indeed, let $n=\prod_{k=1}^r {p_k}^{a_k}$ be the prime factorization of $n$, with prime $p_k$ and $a_k\geq 1$. Let $m=\prod_{k=1}^r p_k$ be the square-free part of $n$. If $\zeta$ is a $n$-th root of unity, then it is a primitive $n$-th root of unity iff $\zeta^\frac{n}{m}$ is a primitive $m$-th root of unity. It follows that $\Phi_{n}(X)=\Phi_{m}(X^\frac{n}{m})$, so that $\Phi_n$ and $\Phi_m$ share the same number of non-zero coefficients.

• Are you sure this is what you want? For MSE question 962636 it seems like you'd need to classify all the ways that $w$ roots of unity can sum to zero for some small $w$ (I guess all $w \leq 6$ from your question); such a sum might come not from $\Phi_n$ itself but from some multiple. For example, $\Phi_{15}(x) = x^8 - x^7 + x^5 - x^4 + x^3 - x + 1$ has seven nonzero coefficients, but $(x+1) \Phi_{15}(x) = x^9 - x^7 + x^6 + x^3 - x^2 + 1$ has only six. (Fortunately for you, $15$ has no prime factors $\geq 7$.) – Noam D. Elkies Oct 22 '14 at 4:28
• @NoamD.Elkies "Are you sure this is what you want?" Yes. And all you state after your question is correct (in fact, I only need $w=6$ not $w<6$). I am aware that the conjecture in itself does not solve question 962636, but I hope that methods useful to prove this conjecture could be re-used or extended. – Ewan Delanoy Oct 22 '14 at 4:38
• Well there are known results that describe, for small $w$, all the ways that $\;w$ roots of unity can sum to zero; but your conjecture concerns the number of nonzero coefficients, not the sum of their absolute values, so it seems to call for a different approach. – Noam D. Elkies Oct 22 '14 at 4:48
• @NoamD.Elkies What known results are you alluding to ? Forgive my ignorance. Also, I conjecture separately that no solution $n$ to question 962636 can have a divisor $\geq 7$, but I'll ask about that here only if I solve my conjecture first. – Ewan Delanoy Oct 22 '14 at 4:49
• See the paper www-math.mit.edu/~poonen/papers/ngon.pdf = "The number of intersection points made by the diagonals of a regular polygon" by B.Poonen and M.Rubinstein (motivated by another geometric problem of very similar flavor). The table on page 7 (backed up by Theorem 3 on the same page) goes up to $w = 12$; the text credits to Mann 1965  for $w \leq 7$, and Conway-Jones 1976  for $w \leq 9$. In fact the earlier papers allowed arbitrary integer coefficients, so Mann's 1965 paper should already contain a proof of your present conjecture too. – Noam D. Elkies Oct 22 '14 at 5:45

Here is my proof for the conjecture. As you mentioned, we can assume that $n=pm$ so that $p$ does not divide $m$.

Suppose that the conjecture is false and $\Phi_n(x)$ has at most $p-1$ nonzero coefficients: $$\Phi_n(x) = \sum_{\ell=1}^{p-1} a_{d_\ell} x^{d_\ell}$$ with some exponents $d_1,\ldots,d_{p-1}$ and integer coefficients $a_{d_1},\ldots,a_{d_{p-1}}$.

By the pigeonhole principle, there is some integer $u$ such that none of $d_1+u$, ..., $d_{p-1}+u$ is divisible by $p$. Take such a $u$. Let $\varepsilon=e^{2\pi i/n}$ and $\varrho=e^{2\pi i/p}=\varepsilon^m$, and consider the following expression: $$S = \sum_{j=1}^p \varepsilon^{jum} \Phi_n(\varepsilon^{jm+1}).$$ Among the numbers $m+1,2m+1,\ldots,pm+1$ precisely one is divisible by $p$; the other ones are co-prime with $n=mp$. So, among $\varepsilon^{m+1},\ldots,\varepsilon^{pm+1}$ there are $p-1$ primitive $n$th roots of unity and one number that has lower order, namely $m$. Therefore, the numbers $\Phi_n(\varepsilon^{m+1}),\Phi_n(\varepsilon^{2m+1}),\ldots,\Phi_n(\varepsilon^{pm+1})$ are all zeros except for exactly one. Hence, $S\ne0$.

On the other hand, $$S = \sum_{j=1}^{p} \varepsilon^{jum} \sum_{\ell} a_{d_\ell} \varepsilon^{(jm+1)d_\ell} = \sum_{\ell} a_{d_\ell} \varepsilon^{d_\ell} \sum_{j=1}^{p} \varepsilon^{jm(d_\ell+u)} = \sum_{\ell} a_{d_\ell} \varepsilon^{d_\ell} \sum_{j=1}^{p} \varrho^{j(d_\ell+u)}.$$

It is well-known that $\sum\limits_{j=1}^p \varrho^{jK}=0$ for all integers $K$ that are not divisible by $p$. Applying this to $K=d_1+u,\ldots,d_{p-1}+u$, we can see that $$S = \sum_{\ell} a_{d_\ell} \varepsilon^{d_\ell} \sum_{j=1}^p \varrho^{j(d_\ell+u)} = \sum_{\ell} a_{d_\ell} \varepsilon^{d_\ell} \cdot 0 = 0.$$

We have proved both $S\ne0$ and $S=0$, the conjecture must be true.

In fact we proved that the exponents that occur in $\Phi_n$ form a complete residue system modulo $p$.

• This is nice! May I ask how the idea of defining this $S$ came to you ? – Ewan Delanoy Oct 24 '14 at 11:56
• My first idea was to substitute a $p$th root of unity and then use that $1+x+\ldots+x^{p-1}$ is irreducible. If the value was 'nice' then this could prove that we have exponents in every remainder class. But expressing the value of $\Phi_n(e^{2\pi i/p})$ was too ugly. The next thing is to substitute all $p$th roots and take the sum or a linear combination in order to cancel out most of the terms except for an arithmetic progression. Next is rotating the $p$th roots by a common angle, which is substituting $\varepsilon^{jm+c}$ for every $j$. Of course there were more things that did not work... – user141614 Oct 24 '14 at 12:41