classification of cyclotomic fewnomials - MathOverflow

classification of cyclotomic fewnomials

2012-05-25T21:32:43Z

This is inspired by this question. Suppose I give you an integer $k.$ Is there a classification of cyclotomic polynomials with exactly $k$ nonzero terms? For example, if $k=1$ there are not any, if $k=2,$ you get just the standard $x^n-1$ polynomials, if $k=3,$ I assume you only get the squares of the standard polynomials, for $k=4$ presumably you only get the products of distinct standard cyclotomics, but after that it becomes a bit puzzling...

Edit by cyclotomic polynomial I mean one all of whose roots are roots of unity.

Answer by Robert Israel for classification of cyclotomic fewnomials

2012-05-25T22:14:01Z

For $k=2$, you get $t^{2^n}+1 = C_{2^{n+1}}(t)$. For $k=3$, see http://oeis.org/A065119. For $k=5$, see http://oeis.org/A086761 See also http://oeis.org/A051664

Answer by Aaron Meyerowitz for classification of cyclotomic fewnomials

2012-05-26T06:10:08Z

Some of the following is mentioned in the OEIS references given by Robert:

Let $a_n$ be the number of terms in $\phi_n(t)$ , the $n$th cyclotomic polynomial. Then $a_n=a_m$ where $m$ is the product of the prime divisors of $n$ because $$\phi_n(t)=\phi_m(t^{n/m}).$$ So we only need to figure out $a_m$ for $m$ square-free.

For odd $n$ $a_{2n}=a_n.$

For odd prime $p$, $a_p=p$ and, if $q \ne p$ is prime, then $$a_{pq}=\frac{2(p-u)(uq+1)}{p}-1$$ where $1 \le u \le p-1$ and $uq \equiv -1 \mod p.$ This should allow one to determine all cases where $a_n=k$ and $n$ has at most two distinct odd prime factors. Quite a bit more can be said in this special case, the non-zero coefficients are all $\pm 1$ and one can say exactly where they appear.

I'm not sure just how much is known about $a_{pqr}$ for $p,q,r$ distinct odd primes. Perhaps lower bounds can be given. Here are a few cases: $[105, 33], [165, 57], [195, 59], [231, 57], [255, 73], [273, 99], [357, 125], [385, 177], [429, 135]$$ [455, 189], [561, 107], [595, 253], [663, 129], [715, 213], [935, 429], [1001, 321]$ So it would seem that perhaps for up to $30$ terms or so everything can be said, but that is just a guess on my part.