# Is there a procedure to determine whether a given number is a root of unity?

Let $z$ be an algebraic number of modulus one. Is there a finite procedure that tells us whether $z$ is a root of unity?

EDIT: As TonyK and David asked, what I had in my mind is $z$ such that I have a polynomial $F \in \mathbf{Q}[x]$ such that $F(z)=0$.

-
Necessarily, $|z|=1$... How about taking powers until you reach unity? –  Dirk Sep 28 '11 at 7:23
@Mateus: When you say that $z$ is algebraic, do you mean that you possess a polynomial with integer coefficients that is satisfied by $z$? If so, how do you specify which root you are interested in? –  TonyK Sep 28 '11 at 8:23
@MateusAraújo: I wasn't being that technical - it's just that if you have a finite search space you can, in theory, create a complete dictionary of (large) finite size of all the roots of unity within the search space - or alternatively bound the possible order of such a root and test until you get up to that order. i.e. you can complete the task with finite resources. I trust that clarifies what I meant. And it helps to know that we have a polynomial with $z$ as a root. –  Mark Bennet Sep 28 '11 at 13:56
@MateusAraújo: Let's stay a bit more civil here; telling people to "rot in hell" has no place in a mathematical discussion. –  David Loeffler Sep 28 '11 at 14:38
@Mateus: I have deleted your inappropriate comment. –  Zev Chonoles Sep 28 '11 at 15:11

I'm going to suppose that we know some polynomial $F \in \mathbf{Q}[x]$ such that $F(z)=0$. (This is somehow the only reasonable "certificate" for a number being algebraic -- I suppose it's possible that we might have a finite description of $z$ and some argument that shows $z$ is algebraic without actually producing a polynomial $F$, but I can't imagine a case where this might come up in practice.)

First check whether $F$ is irreducible -- there are good algorithms for this based on LLL reduction. If $F$ is not irreducible, factorise $F$, find which factor has $z$ as a root, and start again with this new smaller degree $F$. If $F$ is irreducible, let $N$ be its degree; there are obviously only finitely many integers $M$ such that $\phi(M) = N$, where $\phi$ is Euler's phi function, and just check whether $F$ coincides with the $M$-th cyclotomic polynomial for any $M$ in this set.

-
A root of unity is an algebraic integer, so if $F$ is not monic, then your number is not a root of unity. –  Mark Bennet Sep 28 '11 at 12:27
Yes, it is very reasonable to assume we have a polynomial $F(z) = 0$, and is certainly my case. But you made an interesting remark; I'll search for an example of such a "non-constructive" proof of algebraicness. –  Mateus Araújo Sep 28 '11 at 13:25
Your answer assumes that given $F(z) = 0$, if $F$ is irreducible and $z$ a root of unity, then $F$ is a cyclotomic polynomial. Why is it so? –  Mateus Araújo Sep 29 '11 at 0:03
Because a cyclotomic polynomial is irreducible, so it is the minimal polynomial of any of its roots. –  David Loeffler Sep 29 '11 at 7:23

As discussed in other answers, Let $f(x)$ be the irreducible polynomial with rational coefficients which your number satisfies. Normalize $f$ to have leading term $x^n$.

Are all the coefficients of $f$ integers? If not, it isn't a cyclotomic polynomial. Return NO.

Suppose that the coefficients of $f$ are all integers. By a theorem of Kronecker, $f$ is cyclotomic if and only if all its roots lie within the unit circle, if and only if all of the roots lie on the unit circle. (Remember that we have normalized $f$ to have leading coefficient $1$, and all the coefficients of $f$ are integers.)

We'll check whether all the roots of $f$ are within the unit circle in method 1, and whether they are on it in method 2.

I'll now break this into what I think is probably the most efficient method in practice, and what is a method guaranteed to give the right answer.

Method 1: We'll search numerically for the largest root of $f$. Let $f(x) = x^n + f_{n-1} x^{n-1} + \cdots + f_0$. Let $M$ be the matrix $$\begin{pmatrix} & 1 & & & \\ & & 1 & & \\ & & & 1 & \\ & & & & \ddots \\ -f_0 & -f_1 & -f_2 & \cdots & -f_{n-1} \\ \end{pmatrix}.$$ The eigenvalues of $M$ are the roots of $f$, and most computer algebra systems have highly optimized routines to find the largest eigenvalue of a matrix. I don't know of a command for "find me the largest root of this polynomial" but, if your CAS has it, obviously you can just directly ask for that.

Method 2 First, check if $f(x) = x \pm 1$. If so, your number is a root of unity, namely $\mp 1$. I'm going to assume we are not in this case from now on.

Check if your $f$ is palindromic and of even degree. With the exception of $x \pm 1$, every cyclotomic polynomial is, so if your $f$ isn't then reject it.

If $f$ is palindromic of degree $2m$, write $f(x) = x^m g((x+x^{-1})/2)$, for a polynomial $g$ of degree $m$. Note that $g$ also has rational coefficients, and can be computed exactly.

Now, if $e^{i \theta}$ is a root of $f$, then $\cos \theta$ is a root of $g$ and, conversely, if $\cos \theta$ is a root of $g$ then $e^{\pm i \theta}$ is a root of $f$. So $f$ has $2m$ roots on the unit circle if and only if $g$ has $m$ roots between $-1$ and $1$.

Sturm's method can counts the roots of $g$ between $-1$ and $1$. The polynomial $f$ is cyclotomic if it has passed the proceeding tests and $g$ has $m$ roots in this interval.

-
Your answer could use some copyediting; also I don't think you need this theorem of Kronecker. According to wikipedia, the fact that all of its roots lie on the unit circle is the definition of a cyclotomic polynomial. –  Mateus Araújo Sep 28 '11 at 23:59
I'll look into the copy editing when I get a chance. It is not true that a polynomial all of whose roots are on the unit circle is cyclotomic; e.g. $5 x^2 - 6x +5$ has roots $(3 \pm 4i)/5$ and is not cyclotomic. en.wikipedia.org/wiki/Cyclotomic_polynomial agrres with me. –  David Speyer Sep 30 '11 at 15:14
$x+1$ is palindromic, no? :) –  Mariano Suárez-Alvarez Sep 30 '11 at 15:28
@Mateus, you should try to maintain a more civil tone. It is not exactly nice to start a comment on someone who's just generously answered your question with «Your answer could use some copyediting...». Regarding the rest of your first comment: you do not know that the polynomial $f$ is cyclotomic (in fact, that is precisely what you are trying to prove!), so you cannot use that fact to sidestep Kronecker's theorem –  Mariano Suárez-Alvarez Sep 30 '11 at 15:32
@Mariano, if David didn't find my comment uncivil, I don't think it's your role to look for unciviliness in it. The answer had a half-sentence at the top, so it did need copyediting. –  Mateus Araújo Sep 30 '11 at 17:21

Yes, see the references to the more general algorithms given in my answer to the related question When does a polynomial divide $\rm\:x^k-1\:$ for some $\rm\:k\:$?

-

If its argument is a rational multiple of 2$\pi$, then yes.

Solving $e^{in\theta}=1$ gives $\theta=2k\pi/n$ for $k\in\mathbb{Z^+}$, and a number with such an argument is clearly a root of unity.

-
That is true, but useless; if I have the number in the polar form I can certainly do that. But I only have $z$, or, more precisely, a polynomial $F(z) = 0$. So the best I can do is $\theta = -i \log z$, which does not help me to test whether $\theta = 2k\pi/n$. –  Mateus Araújo Sep 28 '11 at 13:20