7
$\begingroup$

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

  • 0
    This is probably not what you mean, but if the description of your number has bounded length and is expressed using a finite alphabet then there will be a finite procedure.2011-09-28
  • 2
    Necessarily, $|z|=1$... How about taking powers until you reach unity?2011-09-28
  • 0
    @Mark: That is not true in general. An uncomputable number can have a description of bounded length. But OP did say *algebraic* number, so it might be true in this case.2011-09-28
  • 1
    @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?2011-09-28
  • 0
    @TonyK: Thanks for that clarification - I was assuming algebraic.2011-09-28
  • 1
    @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.2011-09-28
  • 4
    @MateusAraújo: Let's stay a bit more civil here; telling people to "rot in hell" has no place in a mathematical discussion.2011-09-28
  • 1
    @Mateus: I have deleted your inappropriate comment.2011-09-28
  • 0
    See also http://mathematica.stackexchange.com/questions/8998/how-does-rootofunityq-work for how Mathematica implements it.2012-11-25

4 Answers 4

12

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.

  • 1
    A root of unity is an algebraic integer, so if $F$ is not monic, then your number is not a root of unity.2011-09-28
  • 0
    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.2011-09-28
  • 0
    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?2011-09-29
  • 0
    Because a cyclotomic polynomial is irreducible, so it is the minimal polynomial of any of its roots.2011-09-29
6

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.

  • 0
    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.2011-09-28
  • 1
    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. http://en.wikipedia.org/wiki/Cyclotomic_polynomial agrres with me.2011-09-30
  • 0
    $x+1$ is palindromic, no? :)2011-09-30
  • 2
    @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 theorem2011-09-30
  • 0
    @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.2011-09-30
  • 0
    @David, you're right, of course. But if my polynomial is irreducible, it certainly does not have $0$ as a root, so you only need to look on the unit circle, not within.2011-09-30
  • 0
    It is true that you only need to look on the unit circle, not within. The reason is that, if your polynomial has leading term $x^n$ and constant term a nonzero integer $a_0$, then the product of the norms of the roots is $|a_0| \geq 1$, so either all the roots are on the unit circle (and $a_0 = \pm 1$) or at least one root is outside it. What I said is still true -- Method 1 looks for a root outside the unit circle; method 2 checks that all the roots are on it.2011-09-30
2

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\:$?

1

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.

  • 0
    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$.2011-09-28