Is $\Phi_5(z) \Phi_6(z) = 1 + z^2 + z^3 + z^4 + z^6$ the only product of cyclotomic polynomials that has nonnegative coefficients and satisfies $p(\zeta)=0$, $p(\zeta^2)=2$, $p(\zeta^3)=3$, and $p(1)=5$ where $\zeta$ is a primitive 6th root of unity?

This question arises from my continuing efforts to understand the cyclic sieving phenomenon (see Evaluating products of cyclotomic polynomials at roots of unity). Orbit-size data come nowhere close to determining the sieving polynomial $p(z)$, but I suspect that imposing extra constraints on the polynomial (specifically that $p(z)$ is a product of cyclotomic polynomials and that all coefficients are nonnegative) might do the trick (or at least reduce the set of candidates to a finite set).

This special case seems like a good place to start (though I'd be interested in other cases as well).

There are plenty of cyclotomic polynomials $q(z)$ that take the value 1 at $\zeta^2$ and $\zeta^3$ and 1, and any polynomial obtained by multiplying $\Phi_5(z) \Phi_6(z)$ by a product of such polynomials will evaluate to 0, 2, 3, and 5 at $\zeta$, $\zeta^2$, $\zeta^3$, and 1, respectively. But none of the combinations I've tried gives rise to a polynomial with nonnegative coefficients.


1 Answer 1


Try $x^{30}+x^{20}+x^{15}+x^{10}+1=\Phi_6\Phi_{30}\Phi_{25}$. For more general solutions see the extended comment below.

One way to search for such examples is to solve for the set of polynomials with positive integer coefficients satisfying all the given conditions except being products of cyclotomic polynomials. Then, by studying which roots of unity could possibly be roots of such polynomials, you can start limiting your search. In this case, you get as your set of possible polynomials things of the form $p(x)=x^{n_1}+x^{n_2}+x^{n_3}+x^{n_4}+x^{n_5}$, with $n_1\equiv n_2\equiv 0\pmod{6}$, $n_3\equiv 2\pmod{6}$, $n_4\equiv 3\pmod{6}$ and $n_5\equiv 4\pmod{6}$ (where we might have $n_1=n_2$).

Now from the fact that cyclotomic polynomials (besides $x-1$) have leading and constant coefficients which are $1$, we get that $n_1=0$ and $n_1\neq n_2$. From their palindromic nature, we see that $p(x)=1+x^{a}+x^{a+b}+x^{a+2b}+x^{2(a+b)}$. From our previous work we see that $a\equiv 2,4\pmod{6}$ and $a+b\equiv 3\pmod{6}$.

Next, we see that the only sums of 5 (possibly non-distinct) roots of unity which sum to 0 are sums of 5th and 6th roots of unity (using the spacing given by $p(x)$, where one of the roots of unity is $1$, and the others are spaced accordingly).

Let's deal with the 5th roots of unity first. Suppose when we plug in $\zeta_{m}$, the five terms of $p(\zeta_m)$ are the five distinct 5th roots of unity. This is only possible when $m=5m'$, $m'|n_i$ for each $i$, and $n_i/m$ runs through all of the classes modulo 5.

Similarly if we plug in $\zeta_m$, and the five terms of $p(x)$ are 6th roots of unity, we achieve a similar divisibility criterion.

So now let $\ell$ be the gcd of all the $n_i$ (or just $\gcd(a,b)$). If $\ell=1$, we get the solution $\Phi_5\Phi_6$ (and no others, since taking powers of $\Phi_5$ or $\Phi_6$ doesn't help).

If $p(x)$ is a polynomial with only roots of unity as its roots, and all monomials are divisible by $\ell>1$, then $p(x^{1/\ell})$ has the same property. Further, since $\gcd(\ell,6)=1$, this new polynomial should still satisfy the other criteria. So you can reduce to $\ell=1$. So, a general solution should be $\Phi_5(x^{\ell})\Phi_6(x^{\ell})$ for any $\ell$ relatively prime to $6$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.