4
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ :) ,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 $\endgroup$
    – wayne wang
    Jul 31 '12 at 2:14
  • $\begingroup$ @R.M Mma internals should be on topic. Perhaps not about general CAS algos. $\endgroup$ Jul 31 '12 at 3:16
  • 1
    $\begingroup$ @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. $\endgroup$
    – rm -rf
    Jul 31 '12 at 3:18
11
$\begingroup$

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 *)
$\endgroup$
2
  • $\begingroup$ Thank you, you are so brilliant! $\endgroup$
    – wayne wang
    Jan 22 '13 at 8:25
  • 2
    $\begingroup$ @yoyowinwin Glad you like this method, but it wasn't me-- it really is classical. $\endgroup$ Jan 22 '13 at 14:31
5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.