I am reading a claim that the following two statements are equivalent.

  • One of the roots of a polynomial $v(t)$ is a $2^j$-th root of unity, for some $j$.
  • The polynomial $v(t)$ is divisible either by $1-t$ or by $1+t^{2^{j-1}}$, for some $j$.

We know that the coefficients of $v(t)$ are from $\{-1,0,1\}$.

I am not sure exactly how to interpret this. For which $j$ is this true?

Should $j$ be a positive integer such that $2^j$ is at most the degree of $v(t)$ for example or should there be some other restriction on $j$ or is it really true with no restriction on $j$?

Erratum: Fixed exponent in $1+t^{2^{j-1}}$.


1 Answer 1


A $2^j$-th root of unity is a root of a polynomial $P$ if and only if the minimal polynomial of that root is a factor of $P$. The minimal polynomials of roots of unity are called cyclotomic polynomials, and it's easy to see that for $j=0$, this is $1-t$, and for $j > 0$, it is $1 + t^{2^{j-1}}$ :

$$\Phi_{2^j} = \prod_{\zeta^{2^j} = 1, \zeta^{2^{j-1}} \neq 1} (\zeta - t) = \frac{\prod_{\zeta^{2^j} = 1} (\zeta - t) }{\prod_{\zeta^{2^{j-1}} = 1} (\zeta - t) } = \frac{1-t^{2^j} }{ 1-t^{2^{j-1}}} = 1+t^{2^{j-1}}$$

  • 1
    $\begingroup$ This strict connection is true for minimal $2^j$-th roots of unity. It is not clear from the OP if these minimal roots are intended. If not, then a $2^j$-th root of unity can also be minimal for some smaller degree $2^{j-k}$, which then determines the cyclotomic polynomial. $\endgroup$ May 13, 2014 at 10:17
  • $\begingroup$ If you were given such a polynomial $v(t)$, how would you test the condition in practice? $\endgroup$
    – user66307
    May 13, 2014 at 10:55
  • $\begingroup$ @Lembik : I would check divisibility by the cyclotomic polynomials of degree not greater than that of $v$. In this case ($2^j$-th roots of unity), due to the shape of those cyclotomic polynomials, doing the division is very fast. $\endgroup$
    – mercio
    May 13, 2014 at 10:59
  • $\begingroup$ This would correspond to the Hadamard transform of the coefficient sequence. en.wikipedia.org/wiki/Hadamard_transform $\endgroup$ May 15, 2014 at 8:49

You must log in to answer this question.