# Products of Cyclotomic Polynomials with Nonnegative Coefficients

I'm curious if there are any results that allow us to determine if a product of cyclotomic polynomials (not necessarily all distinct) results in a polynomial having nonnegative coefficients.

Some things that I do know: $$\Phi_{p^k}(x)$$ always has nonnegative coefficients for any prime $$p$$, and so any product of $$\Phi_{p^k}(x)$$'s will have positive coefficients. Whereas, if $$m$$ is not a power of a prime $$\Phi_{m}(1) = 1$$ despite having terms $$x^{\phi(m)}$$ and $$1$$ thus requiring at least one negative coefficient.

By computer I know some interesting examples like, $$\Phi_3(x)\Phi_6(x) = 1x^0 + 1x^2 + 1x^4$$ but $$\Phi_3(x)\Phi_6(x)^2 = 1x^0 + -1x^1 + 2x^2 + -1x^3 + 2x^4 + -1x^5 + 1x^6$$.

Adding a $$\Phi_2(x)$$ helps for a bit, $$\Phi_2(x)\Phi_3(x)\Phi_6(x) = 1x^0 + 1x^1 + 1x^2 + 1x^3 + 1x^4 + 1x^5$$ and $$\Phi_2(x)\Phi_3(x)\Phi_6(x)^2 = 1x^0 + 1x^2 + 1x^3 + 1x^4 + 1x^5 + 1x^7$$ both have nonnegative coefficients, but $$\Phi_2(x)\Phi_3(x)\Phi_6(x)^3 = 1x^0 + -1x^1 + 2x^2 + 1x^4 + 1x^5 + 2x^7 + -1x^8 + 1x^9$$ does not. However, I can't find any sort of rhyme or reason to the appearance of negative coefficients.

I've skimmed papers like http://math.ucsd.edu/~revans/PolynomialsGreene.pdf but can't find any sort of "if and only if" conditions. Being pointed even in a somewhat right direction would help me a lot.

• You might find of some interest my paper at arxiv.org/abs/1807.09290 which gives an application of products of cyclotomic polynomials with all coefficients 0 or 1. – Ira Gessel Dec 16 '18 at 14:41

## 1 Answer

You might do well to try more specific cases. I'll give you a result on the case you end with and a few more showing why I think the general case might be unmanageable.

Claim: $$\Phi_2^i\Phi_3^j\Phi_6^k$$ has all coefficients non-negative if and only if $$i+j \geq k.$$

The if part is easy consequence of

$$\Phi_2(x)\Phi_6(x)=\Phi_2(x^3)=x^3+1$$ and $$\Phi_3(x)\Phi_6(x)=\Phi_3(x^2)=x^4+x^2+1.$$

We can see that $$\Phi_2^i\Phi_3^j\Phi_6^{i+j}$$ has all coefficients non-negative and leading terms $$x^q+x^{q-2}$$ where $$q=3i+4j.$$ In case $$j=0,$$ replace that with $$x^q+x^{q-3}.$$

Since $$\Phi_6^m=(x^2-x+1)^m$$ has leading terms $$x^{2m}-mx^{2m-1},$$ $$\Phi_2^i\Phi_3^j\Phi_6^{i+j+m}$$ begins $$x^r-mx^{r-1}$$ for $$r=q+2m.$$

There seems potential for generalizations.

I'll introduce $$\alpha_m=\frac{x^m-1}{x-1}$$ which is a product of cyclotomic polynomials. $$\alpha_m=\Phi_m$$ when $$m$$ is prime.

$$\Phi_n$$ is pretty easy to understand when $$n$$ has two or less distinct odd prime factors. The terms alternate $$\pm 1$$ or, for a prime power, are all $$1.$$

For example $$\Phi_{35}={x}^{24}-{x}^{23}+{x}^{19}-{x}^{18}+{x}^{17}-{x}^{16}+{x}^{14}-{x}^{13 }+{x}^{12}-{x}^{11}+{x}^{10}-{x}^{8}+{x}^{7}-{x}^{6}+{x}^{5}-x+1$$

Then $$\alpha_m\Phi_{35}$$ has all non-zero coefficients $$1$$ and $$-1.$$ To avoid $$-1,$$ use $$m \geq 24$$ or $$m=5,7,10,12,14,15,17,19,20,21,22 .$$

For such $$n$$ one could describe a necessary and sufficient condition based on the interval lengths of $$\Phi_n$$ starting and ending with a $$-1.$$ But this is amounts to saying that it works for large enough $$m$$ and some smaller ones, but not others.

The first case with three distinct odd prime factors is

$$\Phi_{105}(x)={x}^{48}+{x}^{47}+{x}^{46}-{x}^{43}-{x}^{42}-2\,{x}^{41}-{x}^{40}-{x}^ {39}+{x}^{36}+\cdots$$

The sum of the terms is $$1$$ but $$\alpha_m\Phi_{105}$$ always has negative coefficients. For $$m \leq n,$$ $$\alpha_m \alpha_{n}\Phi_{105}$$ sometimes has only non-negative coefficients and sometimes not.

Here is a plot of all the pairs $$m,n$$ with $$m,n \leq 53$$ and $$\alpha_m \alpha_{n}\Phi_{105}$$ having non-negative coefficients

• There are negative coefficients no matter what $$n$$ is if $$m \leq 14$$ or $$22 \leq m \leq 29.$$
• $$\alpha_m \alpha_{n}\Phi_{105}$$ has all coefficients non-negative if $$47 \leq m \leq n.$$
• $$\alpha_{16}\alpha_n$$ works for $$n=41,42,43$$ but not any smaller or larger $$n.$$
• Did you notice that the regions with negative coefficients can be described as four stripes ($m \leq 14$, $22 \leq m \leq 29$ + likewise for $n$), overlaid by several pineapple-shaped holes? It is similar (with more stripes) for 3*5*11, 3*5*13, 3*7*11, 3*7*13, 5*7*13, but from 3*5*17 and 3*7*17 on, the shapes of the holes become more sophisticated, less "convex". – Wolfgang Dec 20 '18 at 8:11