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.
Best Answer
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$.