# Is there an efficient algorithm to compute a minimal polynomial for the root of a polynomial with algebraic coefficients?

An algebraic number is defined as a root of a polynomial with rational coefficients.

It is known that every algebraic number $\alpha$ has a unique minimal polynomial, the monic polynomial with rational coefficients of smallest degree of which $\alpha$ is a root.

It is also known that the algebraic numbers are algebraically closed, meaning that any polynomial with algebraic numbers as coefficients has algebraic roots.

My question is:

Given the root of a degree $d$ uni-variate polynomial with $n$ terms with algebraic coefficients, is there an efficient (i.e. polynomial time in $d$ and $n$) algorithm to generate its minimal polynomial?

I have searched the literature, but found very little work on algebraic number theory concerned with computational complexity. The closest result I found is:

Theorem 1.4.7 in Lovasz's book:

but I don't think this (quite) answers my question.

-
If there is no algorithm for computing the minimal polynomial, an efficient algorithm for finding any polynomial with rational coefficients for which this number is a root, will suffice. – dan8394 Jun 22 '12 at 16:32
One generally finds the minimal polynomial of an algebraic number, not of a polynomial. Could you please clarify your question? – Ragib Zaman Jun 22 '12 at 16:33
I have done so. Thanks for your careful reading! – dan8394 Jun 22 '12 at 16:35
Thanks, and no problem. – Ragib Zaman Jun 22 '12 at 16:35

Suppose you have a finite field extension $\mathbb Q \subset K$ and an irreducible polynomial $P \in K[X]$.

Let $L$ be the Galois closure of $K$, $G$ be the Galois group of $\mathbb Q \subset L$, and $H$ be the subgroup of $G$ fixing $K$. Then $G$ acts on $L[X]$ by $\sigma(\sum a_i X^i) = \sum \sigma(a_i)X^i$, and $H$ is still the subgroup of $G$ fixing $K[X]$.

Then define $\tilde{P} = \prod_{\sigma \in G/H} \sigma(P)$. For any $\sigma$ in $G$, $\sigma(\tilde{P}) = \tilde P$, thus $\tilde P \in \mathbb Q[X]$, and I think it should be irreducible over $\mathbb Q$ if $K$ is the extension generated by the coefficients of $P$. And so far, the computation is polynomial in the degree of the extension $\mathbb Q \subset L$ (which may be exponential in the degree of $K$) and in the degree of $P$.

If you don't know exactly what $L$ and $G$ are but you know the set of conjugates $C_i$ of each coefficient $a_i$ of $P$, define $$\tilde P = \prod_{(b_0, \ldots, b_n) \in C_0 \times \ldots \times C_n} (b_0 + b_1 X + \ldots b_n X^n)$$ This will produce a polynomial in $\mathbb Q[X]$, but can be extremely larger than the minimal polynomial.

Here you pick one conjugate for each coefficient, and you do the product for all possible simultaneous choices of those conjugates. If you have one coefficient with 2 conjugates and another one with 3, and all the other coefficients are rationals, then you have 6 polynomials to multiply.

Finally, if you don't know the conjugates of the coefficients but you know some annihilating polynomial for each coefficient, let $C_i$ be a set of formal roots of those polynomials, and formally expand that product. You will get an expression involving the formal roots symmetrically so you can write it using the elementary symmetric polynomials of those roots, and then use the Viete relations and replace those with the corresponding coefficients of your annihilating polynomials.

However, these two methods can be exponential in the degree of $P$, so you should avoid them if possible.

In the worst case scenario, the Galois group of $\mathbb Q \subset K$ will be $S_n$, meaning that we have to do calculations in a very big field extension.

suppose $K$ is of degree $n$ and $P$ is of degree $d$. We can estimate of the generic formula you need to use to transform $P$ into a polynomial with rational coefficients.

Pick $L = \mathbb Q(Y_1, \ldots, Y_n)$, let $Z_1, \ldots, Z_n$ be the elementary symmetric polynomials in $Y_i$, pick $K_0 = L^{S_n} = \mathbb Q(Z_1, \ldots, Z_n)$, and $K = K_0(Y_1)$ So the extension $K_0 \subset K$ is the "generic" extension of degree $n$ over $\mathbb Q$. Then say $P = \sum a_i X^i$, where $a_i \in K = K_0[Y_1]$ and are of degree $< n$. So you can write $P = \sum b_{i,j} X^i Y_1^j$ where $b_{i,j} \in K_0$, and $(i,j) \in \{0 \ldots d \} \times \{0 \ldots n \}$. Add indeterminates $B_{i,j}$, so that now $P$ is an element of $K[B_{i,j},X]$. We can compute the product $\prod_{k=1}^n P(Y_k,B_{i,j},X)$ in $L[B_{i,j},X]$, then since it is symmetric, write it as an element of $K_0[B_{i,j},X]$. In fact since the coefficients of $P$ are polynomials in $Y_1$ with integer coefficients, this will be a polynomial in $\mathbb Z[Z_i, B_{i,j},X]$ of degree $dn$ in $X$, homogeneous of degree $n$ in the $B_{i,j}$.

For any choice of $n$ indeterminates among the $B_{i,j}$, $B_{i(1),j(1)} \ldots B_{i(n),j(n)}$ will appear accompanied with $X^{i(1)+\ldots i(n)}$ and a polynomial in $Z_k$ of degree $j(1)+\ldots j(n) \le n^2$ in $Y_k$. So we obtain less than about $(n+d)!/n!d! * n^{2n}/n!$ terms in the final polynomial. Though there may be a better bound on the complexity of polynomials in $Z_k$ that are of a given degree less than $n^2$ than $n^{2n}/n!$ (in particular, not all of them should be able to appear).

Well the good thing it that this is polynomial in $d$ when $n$ is fixed, and is probably exponential in $n$ when $d$ is fixed. And when both of them vary, it's exponential in $d$ and $n$.

-
Thank you. These are some promising ideas. Can you clarify your notation in the equation? Is $\times$ a Cartesian product? What fixes the order of conjugates in that expression? – dan8394 Jun 23 '12 at 8:04
To clarify, I am interested in worst case complexity. Your answer seems to imply that the best-known algorithms are exponential in run time. Is there a rigorous way to prove this? My investigations in Mathematica also support this conclusion. – dan8394 Jun 23 '12 at 8:58