5
$\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, 2012 at 2:14
  • $\begingroup$ @R.M Mma internals should be on topic. Perhaps not about general CAS algos. $\endgroup$ Jul 31, 2012 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, 2012 at 3:18

2 Answers 2

12
$\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$
4
  • $\begingroup$ Thank you, you are so brilliant! $\endgroup$
    – wayne wang
    Jan 22, 2013 at 8:25
  • 2
    $\begingroup$ @yoyowinwin Glad you like this method, but it wasn't me-- it really is classical. $\endgroup$ Jan 22, 2013 at 14:31
  • $\begingroup$ Nice, Resultant[5 - x + x^3 /. (x -> b/y), 8 - y + y^4, y] also seems to work for the product although the first argument is not a polynomial in y. This method also allows reducing Root objects with parameters to reduce combinations of algebraic functions. I do not see why RootReduce and MinimalPolynomial do not implement this for roots with parameters, it's rather powerful being able to reduce algebraic functions in this way. $\endgroup$ Dec 26, 2022 at 14:21
  • $\begingroup$ With the caveat that continuity is not guaranteed when reducing products and sums and so all roots need to be followed. $\endgroup$ Dec 26, 2022 at 14:36
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 and acknowledge you have read our privacy policy.

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