11
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Ira Gessel Dec 16 '18 at 14:41
8
$\begingroup$

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

enter image description here

  • 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.$
$\endgroup$
  • $\begingroup$ 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". $\endgroup$ – Wolfgang Dec 20 '18 at 8:11

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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