Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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. –  J. M. 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. –  J. M. Sep 1 '11 at 18:44

2 Answers 2

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.

share|improve this answer
    
Schur-Cohn proper checks for "inside". If you want to determine points "on" the circle; you will have to (in inexact arithmetic, carefully!) monitor certain quantities that turn up during the Schur-Cohn recursions. I'll post Peter Henrici's implementation if anyone is interested... –  J. M. Aug 25 '11 at 17:16
    
On Jury: the ideas behind it were in fact considered earlier by Morris Marden in his wonderful book; I would say calling it "Jury-Marden" (following Antoniou) would be better... –  J. M. Aug 25 '11 at 17:19

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.