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