[Math] Computation of a minimal polynomial

computational-number-theorycomputer-algebrasage

It is relatively easy (but sometimes quite cumbersome) to compute the minimal polynomial of an algebraic number $\alpha$ when $\alpha$ is expressible in radicals. For example, the simple query

"minimal polynomial 2^(1/5)*(1-exp(2*pi*i/5))"

to Wolfram Alpha will compute the minimal polynomial of $\sqrt[5]{2}\left(1-\exp\left(\frac{2\pi i}{5}\right)\right)$. However, I do not know how to compute a minimal polynomial of an algebraic number that is not expressible in radicals. Moreover, I want to compute a minimal polynomial of linear combinations of algebraic numbers.

For example, take $f(x) = x^5 – x + 1$. This polynomial is irreducible, has Galois group $S_5$, which is not solvable, so by Abel-Ruffini Theorem the roots of $f(x)$ are not expressible in radicals. I want to take two distinct roots of $f(x)$, say $\alpha_1$ and $\alpha_2$, and compute the minimal polynomial $g(x)$ of $\alpha_1 – \alpha_2$. I know how to do this algebraically, because

$$g(x) = \prod\limits_{\substack{1 \leq i, j \leq 5,\\i\neq j}}\left(x – (\alpha_i – \alpha_j)\right),$$

but the computation just seems too painful. Is there a function in Sage, or Mathematica, or Maple, or PARI/GP, that allows to find $g(x)$?

Best Answer

To compute the minimal polynomial of integer multiple of an algebraic integer is easy, so the only thing you need for linear combinations is the minimal polynomials of sums. Now, note that if $A$ is the companion matrix of $\alpha$ and $B$ is the companion matrix of $\beta,$ then $A\otimes I + I\otimes B$ a companion matrix of $\alpha + \beta.$ (Of course, $A\otimes B$ is a companion matrix of $\alpha \beta.$)

Mathematica code:

frobeniusCompanion[poly_, x_] /; PolynomialQ[poly, x] := 
 Module[{n = Exponent[poly, x], coef}, 
  coef = CoefficientList[poly, x]; coef = -Most[coef]/Last[coef];
  SparseArray[{{1, j_} :> coef[[-j]], Band[{2, 1}] -> 1}, {n, n}]]


AA= frobeniusCompanion[x^5 -x -1, x]
CC = KroneckerProduct[AA, IdentityMatrix[5]] + KroneckerProduct[IdentityMatrix[5], AA]
 cp = CharacteristicPolynomial[Normal[CC], x]
 Factor[cp]

gives $$-\left(x^5-16 x-32\right) \left(x^{10}+3 x^6+11 x^5-4 x^2+4 x-1\right)^2$$

Related Question