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