counting complex roots which are root of unity times a real number

Question

Let $p(x)$ be a monic polynomial over the integers. I want to count the number of roots which have the form $\zeta \cdot r$ where $\zeta$ is a root of unity and $r$ is a real number.

To count the number of real roots, one can use sturm sequence, so my idea is to take the polynomials $p_k(x)=\prod (x-a_i^k)$ where the $a_i$ are the roots of $p(x)$ and then count the real roots. The polynomials $p_k(x)$ can be computed using only the coefficients of $p(x)$. The problem is to bound $k$.

If $\zeta_k$ is a primitive $k$-th root of unity, $r$ is real and $\zeta_k r$ is a root of $p(x)$, then so is $\overline{\zeta_k r}=\zeta_k ^{-1}r$ so they both have algebraic degree at most $deg(p)$. It follows that $[\mathbb{Q}(\zeta_k r,\zeta_k^{-1}r):\mathbb{Q}]$ is at most $deg(p)^2$. The field $\mathbb{Q}(\zeta_k r,\zeta_k^{-1}r)$ contains $\zeta_k^2$, so we can add $\zeta_k$ with a degree 2 extension. We conclude that $[\mathbb{Q}[\zeta_k]:\mathbb{Q}]=\varphi(k)\leq 2deg(p)^2$, which gives an upper bound on $k$ (since $\varphi$ goes to infinity).

My questions are

1. Is there an easier way to count this type of roots?
2. If not, is there a better upper bound for the order of the root of unity $\zeta_k$ than the $2deg(p)^2$? Or maybe with some extra conditions on the polynomial this bound can be improved?
3. Are the formulas for the coefficients of $p_k(x)$ as functions of the coefficients of $p(x)$ known? I know they exist by the fundamental theorem of symmetric polynomials, but I would be happy to see a closed formula. At least one way to compute these polynomials is to take the companion matrix of $p(x)$, take its power, and then compute the characteristic polynomial.

Answer 1

An alternative way would be to work over $\mathbb{Z}[\zeta]$: If $r\zeta$ is a zero of $P$, then $r\zeta^{-1}$ is also a zero of $P$, hence $P(X)$ and $P(\zeta^2 X)$ have a common root. Now compute the gcd of these polynomials, compute the roots of the gcd numerically, and check whether these roots are on the lines $\{t\zeta:t\in\mathbb{R}\}$. Doing so needs only a certain precision depending on the minimal distance of roots of $P$, and most of the time quite rough computations should suffice.

Although this algorithm looks polynomial to me, computing the gcd over $\mathbb{Z}[\zeta]$ is so much effort that for small and medium $k$ your algorithm is probably superior. This depends mostly on how much work the computation of $p_k$ is, which I cannot judge.

Answer 2

Do a high precision computation of all roots, take the continued fraction expansion of the imaginary part of $\frac{1}{\pi}\log \rho$ for all roots $\rho$. This gives you all reasonable candidates together with the relevant powers $k$ which you have to consider and you have to test only them.

Answer 3

If the complex roots are $a_i$, compute $t_i=a_i/|a_i|^2$ with enough precision.

You must check if $t_i$ is root of unity. If a bound is known one might try $t_i^n$ up to certain bound.

Or find good rational approximation to $m/k$ of $\log{t_i}/(2\pi i)$