9
$\begingroup$

Given a polynomial $f$ of degree $d$ with integer coefficients, I am interested in an effective algorithm to determine whether or not $f$ has all its roots on the unit circle. (So the output should be a YES or NO, no further information required.)

In this context the maximum integer $m$ such that $\phi(m)$ (Euler totient) does not exceed $d$ is of some importance. One could take greatest common divisors of $f$ and the consecutive cyclotomic polynomials $\Phi_d(x)$ up to $\Phi_m(x)$.

$\endgroup$
6
  • 3
    $\begingroup$ Are you assuming that $f$ is monic? $\endgroup$
    – Lucia
    Sep 13 '15 at 5:49
  • 5
    $\begingroup$ It might be easier to take $\gcd(f,x^n-1)$. $\endgroup$ Sep 13 '15 at 7:02
  • $\begingroup$ Regarding the greatest $m$ such that $\phi(m) \leq d$ : mathoverflow.net/questions/180423/… $\endgroup$
    – user40023
    Sep 13 '15 at 8:16
  • 3
    $\begingroup$ See math.uconn.edu/~kconrad/blurbs/galoistheory/numbersoncircle.pdf. $\endgroup$
    – KConrad
    Sep 13 '15 at 14:59
  • 1
    $\begingroup$ If one allows non-monic polynomials, then there exist polynomials having all their roots on the unit circle, yet are not, up to a multiplicative constant, a product of cyclotomics. For example, take the minimal polynomial of $(3+4i)/5$. $\endgroup$ Aug 13 at 6:31
11
$\begingroup$

As pointed out by @kconrad in the comment, the Cayley transformation $z\rightarrow i\frac{z+1}{z-1}$ maps the unit circle to the real axis, which reduces your question to counting real zeros of a polynomial polynomial which is the gcd of the real and imaginary part of the composition of your polynomial with the inverse of the Cayley tranform. Counting the real zeros of a polynomial can be done using Sturm's algorithm, as described in the Wikipedia article.

$\endgroup$
5
$\begingroup$

The Mahler measure of the polynomial $P(x)=a\prod_{j=1}^d(x-\alpha_j)$ is $$ \exp\biggl(\int_0^1\log|P(e^{2\pi it})|\,d t\biggr) $$ or, with the help of Jensen's formula, $$ |a|\prod_{j=1}^d\max\{1,|\alpha_j|\}. $$ The latter is equal to 1 if and only if the polynomial $P(x)$ is cyclotomic, so computing the former integral answers the question. In fact, Lehmer's problem (believed to be true but still open) suggests that the value $1.176280\dots$ is least possible for the Mahler measure of non-cyclotomic polynomial (there are bounds proven that depend on $d$), so that computing the integral approximately already gives you an algorithm to conclude about cyclotomicity.

$\endgroup$
4
$\begingroup$

This is more a comment but I don't have enough points.

Maybe it helps to reduce to the more familiar case of polynomials with all roots real via the map $w=(z-i)/(z+i)$ which map real $z$ to $|w|=1$. Given $g(w)$ , we test if $f(z)=g((z-i)/(z+i))(z+i)^d$ has all roots real. One necessary and sufficient condition I know to test for real and distinct roots of $f(z)$ is that $f'(z)$ should also have real and distinct roots and that $f(r)/f''(r)<0$ for all roots $r$ of $f'(z)$ which can be applied by taking derivative. In any case testing for real root seems simpler by looking for sign change. Applying to the nth cyclotomic polynomial $g_n(w)$, gives $f_n(z)=\prod_{1 \le k <n/2,gcd(k,n)=1}z^2-cot(k\pi /n)^2$

$\endgroup$
2
$\begingroup$

As explained in the answers, applying a Möbius transform and then using Sturm's theorem on the number of real roots gives an algorithm which solves the problem.

A natural question is what is an efficient implementation of this algorithm. There are some improvements on implementing the above method literally. For example, if $P$ is of degree $d$ and $P(0)\neq 0$, then every root $x$ of $P$ on the unit circle is also a root of $P^*(x) = x^d P(1/x)$ (this is because $\overline{x} = 1/x$). So the condition of $P$ having all the roots on the unit circle implies that $P$ is reciprocal or anti-reciprocal, that is, $P^* = \pm P$. It may be good to check that first.

Furthermore, there are several variants of the above method where one applies Sturm's theorem to other polynomials. One reference is Cerlienco, Mignotte, Piras, Computing the Measure of a Polynomial, J. Symbolic Computation (1987) 4, 21-33 (the article is old and I would be grateful if someone knows more recent references). The last section of this article also investigates the cost of these algorithms.

$\endgroup$
1
$\begingroup$

Given any real monic polynomial $p(x)$ with only real zeros, there is a finite algebraic (no root finding) algorithm to construct a real symmetric and tri-diagonal matrix $A$ so that $p(x)$ is the characteristic polynomial of $A$. This proves $p(x)$ has only real roots and $A$ gives a certificate. Interestingly this also solves the finite version of Hilbert-Polya problem, given real rooted $p(x)$ find a Hermitian operator whose eigenvalues gives the roots of $p(x)$.

If $p,q$ are two real polynomials with $deg(p)=deg(q)+1$ and only real and simple roots which interlace , then applying Euclidean algorithm (divide out and flip, and this is the same as the usual Strum computation), we get a recursion. If we write $p/q=x+a-b/(q/q_1),$ where $a,b$ are real and $q_1$ is a monic polynomial with $deg(q_1)=deg(q)-1$ which we can, we will have $b>0$ and the roots of $q_1$ are all real and simple and interlaces those of $q$. By induction, we get a continued fraction expansion applying this to $(p,p'/n)$,

$\frac{p(x)}{p'(x)/n}=x+a_1-\cfrac{b_1}{x+a_2-\cfrac{b_2}{...-\cfrac{...}{x+a_{n-1}-\cfrac{b_{n-1}}{x+a_n}}}},$

with $a_j$ real and $b_j>0.$ But a generic continued fraction is a Cauchy interlacing ratio of a symmetric tri-diagonal matrix which can be made symmetric, so we have

$\frac{p(x)}{p'(x)/n}=\frac{\det(xI-A)}{\det(xI-A_1)},$ where $A$ is the tridiagonal matrix

$A=\begin{pmatrix} -a_1 & \sqrt{b_1} & 0 & ... & 0\cr \sqrt{b_1} & -a_2 & \sqrt{b_2} & 0 & 0\cr 0 & \sqrt{b_2} & -a_3 & \sqrt{b_3} & 0 \cr ... & ... &.... & .... &... \cr 0 &...& \sqrt{b_{n-2}} & -a_{n-1} & \sqrt{b_{n-1}} \cr 0 & ... & 0 & \sqrt{b_{n-1}} & -a_n \end{pmatrix},$

and $A_1$ is $A$ with the first row and column deleted. This in fact gives $2^{n-1}$ solutions as we can replace each $\sqrt{b_j}$ by $-\sqrt{b_j}$ independently. We can also replace $p'(x)/n$ by any polynomial $q(x)$ with roots interlacing those of $p$. If we start with a $p$ with non real roots, either the algorithm fail or we have some $b_j \le 0$. If $p$ has multiple root, it will be cancelled out by $p'(x)$. To certify that a given $g(z)$ has all roots on the unit circle, we apply the above to $p(x)=(x+i)^{deg(g)}g(\frac{x-i}{x+i})$.

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