# What does MinimalPolynomial do?

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?)

-
:) ,Thanks. that's that I want,Verbeia, and I also want to find out its implemention . maybe R.M is right , it's not approperate to post it here – yoyowinwin Jul 31 '12 at 2:14
@R.M Mma internals should be on topic. Perhaps not about general CAS algos. – Dr. belisarius Jul 31 '12 at 3:16
@belisarius Oh, I agree that internals is on topic... we even have a tag: implementation-details for it. I got the feeling the OP wanted to know how the CAS algo worked. – R. M. Jul 31 '12 at 3:18

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 *)

-
Thank you, you are so brilliant! – yoyowinwin Jan 22 '13 at 8:25
@yoyowinwin Glad you like this method, but it wasn't me-- it really is classical. – Daniel Lichtblau Jan 22 '13 at 14:31

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.

-