# Roots of polynomials on the unit circle

Given an integer polynomial, how can I detect if its roots in $\mathbb{C}$ are on the unit circle, that is, of absolute value 1?

I'm not sure what the best formulation for this problem is; that may depend on what can be efficiently solved. Here are some thoughts, given $\mathrm{P}\in\mathbb{Z}[x]$:

1. Does P have any roots $r$ with $|r|\neq1$?
2. Does P have roots, respectively, on the unit circle, outside the unit circle, and inside the unit circle?
3. How many roots (with multiplicity) are on the unit circle?
4. How many roots (with multiplicity) are, respectively, on the unit circle, outside the unit circle, and inside the unit circle?

I feel for some reason that there should be nice criteria for some problem along the lines of the above. Feel free to tell me I'm wrong (in which case attack whichever problems you can with whatever methods work).

The degree of the polynomial can be assumed to be greater than or equal to 5 (else I suppose I could use one of the nasty closed-forms for the roots) and not of any special form. I know how to approximate roots, of course; you can suppose (if you must) that the roots are close to the unit circle. (See below -- in this application there's a huge difference between 1 and $1+10^{-100}$.)

My interest is in the asymptotic behavior of the sequence with characteristic polynomial $P$, so answers relevant to that case are most welcome. But no good answer will be turned away on the basis of race, color, creed, or problem applicability.

-
Charles, would you be interested in an implementation of Schur-Cohn? I could write up an answer since I can't seem to find a readily accessible implementation on the Internet, and I suppose posting one might be helpful not only for you. –  Ｊ. Ｍ. Sep 1 '11 at 18:04
@J.M.: I would! I've been reading through Irene Gargantini's article on Schur-Cohn which is excellent but has many subroutines which must be implemented carefully. –  Charles Sep 1 '11 at 18:42
The elaboration is needed by Gargantini since she works in inexact arithmetic. As I seem to understand, you can do rational arithmetic, so Henrici's simpler implementation might be good enough for your needs. I'll get back to it in a few hours. –  Ｊ. Ｍ. Sep 1 '11 at 18:44

Let $P(x) = a_0 + \cdots + a_n x^n \in \mathbb{Z}[x]$. If you care about roots exactly on the unit circle, consider the transformation $x = e^{i\theta}$, so $x^k = \cos k\theta + i\sin k\theta$. Then the real and imaginary parts of $P(x)$ are trigonometric polynomials. Using Chebyshev polynomials, rewrite these as polynomials in $\cos\theta$ (more or less -- there may be an extra factor of $\sin\theta$ in the imaginary part). Then use Sturm's theorem to count roots.