1
$\begingroup$

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}}$.

$\endgroup$
1
$\begingroup$

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}}$$

$\endgroup$
  • 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$ – Dr. Lutz Lehmann May 13 '14 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 '14 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 '14 at 10:59
  • $\begingroup$ This would correspond to the Hadamard transform of the coefficient sequence. en.wikipedia.org/wiki/Hadamard_transform $\endgroup$ – Dr. Lutz Lehmann May 15 '14 at 8:49

Your Answer

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