4
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Per Alexandersson Jun 17 '15 at 14:29
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Ofir Jun 20 '15 at 6:48
  • $\begingroup$ 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$. $\endgroup$ – Jan-Christoph Schlage-Puchta Jun 20 '15 at 13:55
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Ofir Jun 20 '15 at 5:44

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.