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

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.
• To answer 3: This is closely related to plethystic substitutions, and is a quite hot topic in combinatorial aspects of representation theory. Long story short - don't expect a nice closed form formula, it is very likely that there is none, since the coefficients that appear in plethystic substitutions "behave" a bit like Littlewood-Richardson coefficients, and there is no polynomial-time algorithm to compute these. – Per Alexandersson Jun 17 '15 at 14:29

## 3 Answers

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.

• This seems interesting. Is there a way to bound the degree of $gcd(P(x),P(\zeta^2 X))$ as a function of the number of roots of the form $r\zeta$? Clearly, if all the $\zeta^i$ are roots, then the answer is no, but if $P$ has low degree, then it cannot have $\zeta_n$ as a root for $n$ very large. – Ofir Jun 20 '15 at 6:48
• I don't think so. The problem is that there might exist many pairs of roots $x_1, x_2$ with $x_1=\zeta^2 x_2$, although not a single one is of the form $r\zeta$. – Jan-Christoph Schlage-Puchta Jun 20 '15 at 13:55

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.

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

• Actually, this is what I first tried. The problem is that it still takes a lot of time (since n is much larger than the degree), and there is still a problem with the approximation. – Ofir Jun 20 '15 at 5:44