2
$\begingroup$

Let $p$ be a polynomial with rational coefficients and $\alpha = \sqrt[n]{q}e^{i2k\pi/m}$ for some natural numbers $n,m,k$ and a rational number $q > 0$. Is there an effective algorithm for deciding if $p(\alpha) = 0$?

I assume there should be one, as computer algebra systems can be used for this task. If so, is there a polynomial-time algorithm (in terms of $\max\{n,m\}$)?

Could someone either explain the idea of what has to be done, or give me some references? Thank you in advance.

Improve this question
$\endgroup$
5
  • 6
    $\begingroup$ For $\alpha$ of the indicated type it is straightforward to write down the minimal polynomial $f(x)\in\mathbb{Z}[x]$ in terms of cyclotomic polynomials, then you just have to divide $p(x)$ by $f(x)$ and see if there is a remainder, which is easily done in polynomial time. $\endgroup$
    – Neil Strickland
    Commented Aug 15, 2021 at 16:41
  • $\begingroup$ @NeilStrickland Thank you! Could you, please, elaborate on how the minimal polynomial looks like, or how can it be computed? This is the problem I have been originally motivated by. :) (To me, as a layman, it seems that potential reducibility of cyclotomic polynomials over some number fields may complicate things.) $\endgroup$
    – Jára Cimrman
    Commented Aug 15, 2021 at 16:44
  • 1
    $\begingroup$ It comes down to a question of polynomials of the form $x^r-b$ for $b$ rational. The factorization of such polynomials over the rationals is well-understood. In particular, exceptional cases are dealt with at math.stackexchange.com/questions/133581/… Since $p$ is assumed to have rational coefficients, I don't see how reducibility over fields other than the rationals can be a problem. $\endgroup$
    – Gerry Myerson
    Commented Aug 16, 2021 at 3:35
  • $\begingroup$ @GerryMyerson Your link gives a necessary and sufficient condition for irreducibility of $x^r - b$. For instance, both $x^9 - 8$ and $x^8 - 16$ are reducible: $x^9 - 8 = (x^3-2)(x^6+2x^3+4)$ and $x^8 - 16 = (x^4-4)(x^4+4)$. In this case it can be "detected", to which of the factors the root $\alpha$ corresponds. If $\alpha$ is a root of the first factor, then one can indeed proceed recursively. But what about the remaining case? Above, $x^6+2x^3+4$ is irreducible, but $x^4+4$ is reducible. Can the remaining factor be of the form other than $x^n\pm a$ and still be reducible? $\endgroup$
    – Jára Cimrman
    Commented Aug 16, 2021 at 7:16
  • $\begingroup$ @GerryMyerson When it comes to my comment about reducibility of cyclotomic polynomials over some number fields: the fact that the factorization of $x^4 + 4$ is "finer" than the one of $x^4 + 1$ can be seen as a consequence of the fact that the cyclotomic polynomial $x^4 + 1$ is reducible over $\mathbb{Q}(\sqrt{2})$. Hence my skepticism to the claim that the minimal polynomial can be easily expressed in terms of cyclotomic polynomials. $\endgroup$
    – Jára Cimrman
    Commented Aug 16, 2021 at 7:50

0

Reset to default

You must log in to answer this question.