What does MinimalPolynomial do?

Question

suppose $x^5-x-1=0$, $y^7-y-1=0$ and $z=x+y$. I want to find a minimal polynomial expression of $z$, such that $p(z)=0$, and the code can be written like this:

MinimalPolynomial[Root[#^5 - # - 1 &, 1] + Root[#^7 - # - 1 &, 1], z]

What does MinimalPolynomial[] do behind us (in other words, what is the algorithm?)

Answer 1

It uses a resultant computation. The idea is this. We are given algebraic numbers $x$ and $y$, where $p(x)=0$ and $q(y)=0$ are the minimal polynomials. We want to find the defining polynomial for $z=x+y$. We use $p(x)=p(z-y)$ and $q(y)$, and eliminate $y$ using the classical method of resultants.

Here is how it would go for your example.

p[x_] := #^5 - # - 1 &[x]
q[y_] := #^7 - # - 1 &[y]

Resultant[p[z - y], q[y], y]

(* 53 + 116*z - 191*z^2 - 1393*z^3 + 7677*z^4 - 10429*z^5 + 20034*z^6 - 
   34395*z^7 + 36887*z^8 + 32235*z^9 + 11257*z^10 - 77061*z^11 - 
   51163*z^12 + 19040*z^13 + 46835*z^14 + 27874*z^15 + 13792*z^16 + 
   12785*z^17 + 29225*z^18 + 29750*z^19 + 12152*z^20 + 1820*z^21 + 
   85*z^22 + 2300*z^23 + 2030*z^24 + 448*z^25 - 42*z^26 - 21*z^27 + 
   5*z^28 + 5*z^29 + 7*z^30 + 7*z^31 - z^35 *)

Answer 2

Here is a clue

This package introduces functions for computation within finite algebraic extensions of rationals. For more information on the notions and algorithms used, see for instance H. Cohen, A Course In Computational Algebraic Number Theory, Springer-Verlag, 1993.