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

| cite | improve this answer | |
$\endgroup$
3
$\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$

| cite | improve this answer | |
$\endgroup$
3
$\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.

| cite | improve this answer | |
$\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.