This should be a fairly trivial question, to which I have nevertheless found no satisfactory answer.

I am interested in effective algorithmic computation of minimal polynomials of some particularly simple algebraic numbers, especially the complex $n$-th roots of rational numbers: $$\alpha = \sqrt[n]{q}e^{i2k\pi/n}.$$ Each such $\alpha$ is a root of the polynomial $x^n - q$, but the trouble is that this polynomial might not be irreducible over $\mathbb{Q}$. I know that the irreducible factors can be found in polynomial time, e.g., using the LLL algorithm. But how to determine the correct factor? This can usually be done easily by hand, but what about algorithmic computation? The only way of evaluating a polynomial at $\alpha$ that I am aware of already assumes that the minimal polynomial of $\alpha$ is known. Or should I use a completely different approach?

Moreover, since $q$ can be assumed to be an integer, an algorithm for computing minimal polynomials of algebraic integers would be sufficient. This MathOverflow answer suggest that computing minimal polynomials of algebraic integers is easy, but I was unable to find out why. Any reference would be helpful here.

Thank you in advance.

  • 2
    $\begingroup$ See this post. $x^n-q$ is irreducible, except for the case where $q=p^m$ for some prime $p$ dividing $n$. $\endgroup$ Aug 15, 2021 at 8:08
  • $\begingroup$ If you have the irreducible factors, you can determine the correct factor simply by inserting the given algebraic number. That is an algorithm. Whether it is "easy" to determine the minimal polynomial of an algebraic number in general, depends what is meant with "easy". $\endgroup$
    – Peter
    Aug 15, 2021 at 8:20
  • 1
    $\begingroup$ Hmm. There is a subtlety I overlooked... $\endgroup$ Aug 15, 2021 at 9:25
  • 1
    $\begingroup$ @JyrkiLahtonen Nevertheless, thanks for your comments. I seem to understand how the problem could be solved for positive real algebraic numbers, but I am still quite unsure about the complex numbers... $\endgroup$ Aug 15, 2021 at 9:28
  • 1
    $\begingroup$ With the aid of the minimal polynomial of $|q|^{1/n}$ and the roots of unity you get a field where you can work. Galois theory then tells us how to find the conjugates of $\alpha$. There are subtleties when $q$ is negative (see the second exceptional case). $\endgroup$ Aug 15, 2021 at 10:10


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.