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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ – J. M. ain't a mathematician Sep 1 '11 at 18:04
  • $\begingroup$ @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. $\endgroup$ – Charles Sep 1 '11 at 18:42
  • $\begingroup$ 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. $\endgroup$ – J. M. ain't a mathematician Sep 1 '11 at 18:44
3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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... $\endgroup$ – J. M. ain't a mathematician Aug 25 '11 at 17:16
  • $\begingroup$ 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... $\endgroup$ – J. M. ain't a mathematician Aug 25 '11 at 17:19
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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