# Kronecker polynomial or not?

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

• Are you assuming that $f$ is monic? – Lucia Sep 13 '15 at 5:49
• It might be easier to take $\gcd(f,x^n-1)$. – Anthony Quas Sep 13 '15 at 7:02
• Regarding the greatest $m$ such that $\phi(m) \leq d$ : mathoverflow.net/questions/180423/… – user40023 Sep 13 '15 at 8:16
• – KConrad Sep 13 '15 at 14:59

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