# 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
Commented Sep 28, 2011 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? Commented Sep 28, 2011 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. Commented Sep 28, 2011 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. Commented Sep 28, 2011 at 14:38
• @Mateus: I have deleted your inappropriate comment. Commented Sep 28, 2011 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. Commented Sep 28, 2011 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. Commented Sep 28, 2011 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? Commented Sep 29, 2011 at 0:03
• Because a cyclotomic polynomial is irreducible, so it is the minimal polynomial of any of its roots. Commented Sep 29, 2011 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. Commented Sep 28, 2011 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. Commented Sep 30, 2011 at 15:14
• $x+1$ is palindromic, no? :) Commented Sep 30, 2011 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 Commented Sep 30, 2011 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. Commented Sep 30, 2011 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$. Commented Sep 28, 2011 at 13:20