5
$\begingroup$

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.

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

2 Answers 2

3

The Schur-Cohn algorithm and the Jury stability criterion answer some of your questions. Specifically, the Schur-Cohn algorithm decides, whether there are any roots inside the (closed) unit circle and the Jury stability test decides whether all the roots are strictly inside the unit circle.

  • 0
    On Jury: the ideas behind it were in fact considered earlier by Morris Marden in his [wonderful book](http://books.google.com/books?id=ZMYIrr97cQUC); I would say calling it "Jury-Marden" (following [Antoniou](http://books.google.com/books?id=tnYeAQAAIAAJ)) would be better...2011-08-25
1

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.