{VERSION 2 3 "SUN SPARC SOLARIS" "2.3" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 }{CSTYLE "2D Output" 2 20 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 256 "terminal" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE " " -1 257 "" 1 24 0 0 0 0 0 0 0 0 0 0 0 0 0 }{PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "Times" 1 14 0 0 0 0 2 2 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Text Output" -1 2 1 {CSTYLE "" -1 -1 "Co urier" 1 10 0 0 255 1 0 0 0 0 0 1 3 0 0 }1 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Heading 1" 0 3 1 {CSTYLE "" -1 -1 "" 1 18 0 0 0 0 0 1 0 0 0 0 0 0 0 }1 0 0 0 6 6 0 0 0 0 0 0 -1 0 }{PSTYLE "" 2 6 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 2 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Maple Output" 0 11 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }3 3 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 11 12 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }1 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 3 256 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }3 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 0" -1 257 1 {CSTYLE "" -1 -1 "Helvetica" 1 14 0 0 0 0 2 1 2 0 0 0 0 0 0 } 0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 2" -1 258 1 {CSTYLE "" -1 -1 "Courier" 1 14 0 0 0 0 2 2 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }} {SECT 0 {EXCHG {PARA 0 "" 0 "" {TEXT 256 48 "/home/m262f99/CHYZAK/work sheetsV.4/gbsample1.mws" }{MPLTEXT 1 0 0 "" }}{PARA 256 "" 0 "" {TEXT 257 139 "Math 262a, Fall 1999, Glenn Tesler\nUsing commutative Grobner bases to solve a system of polynomial equations via elimination ideal s\n12/2/99" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "restart;" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 63 "with(Groebner): with(Mgfun): with(Holonomy): with(Ore_algebra):" }}}{EXCHG {PARA 3 "" 0 "" {TEXT -1 9 "Example 1" }{MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 126 "We want to solve the following system of equations. Rewrite e ach equation A=B as A-B=0, and then form an ideal of the A-B 's." } {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 99 "eqs0 := \{ x+y^2+z^2 = 1 , x^2+y+z^2 = 1 , x^2+y^2+z = 1 \};\neqs := map(eq - > lhs(eq)-rhs(eq), eqs0);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%%eqs0G< %/,(%\"xG\"\"\"*$%\"yG\"\"#F)*$%\"zGF,F)F)/,(*$F(F,F)F+F)F-F)F)/,(F1F) F*F)F.F)F)" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$eqsG<%,**$%\"xG\"\"# \"\"\"%\"yGF**$%\"zGF)F*!\"\"F*,*F'F**$F+F)F*F-F*F.F*,*F(F*F0F*F,F*F.F *" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 1245 "To solve it the traditiona l way, we would try to substitute, say, x in terms of y and z, to get \+ equations only involving y and z; then we would try to substitute, say , y in terms of z, to get equations only involving z. Then we would s olve for z, back substitute this into the yz equations and solve for y 's, and then back substitute this into the full equations and solve fo r x's.\nEach substitution step produces polynomials in x,y,z (or possi bly radicals that can be turned into polynomials).\nWe construct a Gro bner basis GB with lex order x>y>z, called an \"elimination order\". \+ If there exists a polynomial f(z) in only containing z's, its l ead term is divisible by the lead term of some element g of GB; the le ad term of g is a power of z, and all other terms in g are smaller tha n this in lex order, hence also only contain z, so g is purely a funct ion of z. In fact, a Grobner basis of I[z]= intersect k[z], is g iven by GB intersect k[z]. Note this is not true of x or y, because i f the lead term is a power of x, the smaller terms could involve y or \+ z.\nContinuing this way: let I[z], I[y,z], I[x,y,z] be the subset of I = only involving the indicated variables. Then a Grobner basis f or I[z] is GB intersect k[z], etc." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "A := poly_algebra(x,y,z);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"AG%,Ore_algebraG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "T := termorder(A,plex(x,y,z));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"TG%+term_orderG" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 41 "Get the Grobner basis in lex order x>y>z:" }{MPLTEXT 1 0 0 "" } }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "GB := gbasis(eqs,T);" }} {PARA 12 "" 1 "" {XPPMATH 20 "6#>%#GBG7&,.*$%\"zG\"\"%!\"#*$F(\"\"$\"# 6*$F(\"\"#!\"'*$F(\"\"'\"\")*$F(\"\"&!#7F(\"\"\",.F(F7F'F)F.!\"\"*&%\" yGF7F(F/F)*&F;F7F(F7F*F+!\"%,*F;F9F.F9*$F;F/F7F(F7,,%\"xGF7F;F7F.F/F(F 9F9F7" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "map(factor,GB);" } }{PARA 12 "" 1 "" {XPPMATH 20 "6#7&**%\"zG\"\"\",&F%F&!\"\"F&F&,&F%F&F &F&F&,&F%\"\"#F(F&\"\"$*(F%F&F*F&,**$F%F+F+F%F(F(F&%\"yGF+F&*&,(F0F&F( F&F%F&F&,&F0F&F%F(F&,,%\"xGF&F0F&F/F+F%F(F(F&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" } }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 47 "This induces Grobner bases for I [z] and I[y,z]:" }{MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 94 "GBz := select(eq -> not(has(eq,y) or has(eq,x)), GB); \nGByz := select(eq -> not(has(eq,x)),GB);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$GBzG7#,.*$%\"zG\"\"%!\"#*$F(\"\"$\"#6*$F(\"\"#!\"'*$ F(\"\"'\"\")*$F(\"\"&!#7F(\"\"\"" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>% %GByzG7%,.*$%\"zG\"\"%!\"#*$F(\"\"$\"#6*$F(\"\"#!\"'*$F(\"\"'\"\")*$F( \"\"&!#7F(\"\"\",.F(F7F'F)F.!\"\"*&%\"yGF7F(F/F)*&F;F7F(F7F*F+!\"%,*F; F9F.F9*$F;F/F7F(F7" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 23 "Solve for p ossible z's:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "zsols := \{solve(\{ op(GBz)\},z)\};" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%&zsolsG<&<#/%\"zG \"\"\"<#/F(!\"\"<#/F(#F)\"\"#<#/F(\"\"!" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 131 "For each found z, find all possible y's by using the equ ations only involving y and z.\nThen for each potential (y,z), find al l x's." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 421 "sols := NULL:\nfor zsol \+ in zsols do\n lprint(`Trying`,zsol);\n ysols := \{solve(\{op(s ubs(zsol,GByz))\},y)\};\n for ysol in ysols do\n lprint(` \+ Trying`,zsol,ysol);\n xsols := \{solve(\{op(subs(zsol,ysol,G B))\},x)\};\n if xsols<>\{\} then\n print(`Found sol utions:`,zsol,ysol,xsols);\n sols := sols, op(map(xsol -> \{ op(xsol),op(ysol),op(zsol)\},xsols)):\n fi\n od\nod;\nsols ; " }}{PARA 6 "" 1 "" {TEXT -1 16 "Trying \{z = 1\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%&ysolsG<#<#/%\"yG\"\"!" }}{PARA 6 "" 1 "" {TEXT -1 29 " Trying \{z = 1\} \{y = 0\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&%1Found~solutions:G<#/%\"zG\"\"\"<#/%\"yG\"\"!<#<#/%\"xGF+" }} {PARA 6 "" 1 "" {TEXT -1 17 "Trying \{z = -1\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%&ysolsG<#<#/%\"yG!\"\"" }}{PARA 6 "" 1 "" {TEXT -1 31 " Trying \{z = -1\} \{y = -1\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&%1Found~solutions:G<#/%\"zG!\"\"<#/%\"yGF'<#<#/%\"xGF'" }}{PARA 6 "" 1 "" {TEXT -1 18 "Trying \{z = 1/2\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%&ysolsG<#<#/%\"yG#\"\"\"\"\"#" }}{PARA 6 "" 1 "" {TEXT -1 33 " Trying \{z = 1/2\} \{y = 1/2\}" }}{PARA 11 "" 1 " " {XPPMATH 20 "6&%1Found~solutions:G<#/%\"zG#\"\"\"\"\"#<#/%\"yGF'<#<# /%\"xGF'" }}{PARA 6 "" 1 "" {TEXT -1 16 "Trying \{z = 0\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%&ysolsG<$<#/%\"yG\"\"!<#/F(\"\"\"" }} {PARA 6 "" 1 "" {TEXT -1 29 " Trying \{z = 0\} \{y = 0\}" }} {PARA 11 "" 1 "" {XPPMATH 20 "6&%1Found~solutions:G<#/%\"zG\"\"!<#/%\" yGF'<#<#/%\"xG\"\"\"" }}{PARA 6 "" 1 "" {TEXT -1 29 " Trying \{z = 0\} \{y = 1\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&%1Found~solutions: G<#/%\"zG\"\"!<#/%\"yG\"\"\"<#<#/%\"xGF'" }}{PARA 12 "" 1 "" {XPPMATH 20 "6'<%/%\"zG\"\"\"/%\"yG\"\"!/%\"xGF)<%/F%!\"\"/F+F./F(F.<%/F%#F&\" \"#/F(F3/F+F3<%F'/F%F)/F+F&<%F*F8/F(F&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 3 "" 0 "" {TEXT -1 45 "Example 2: eq uations not solvable by radicals" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 57 "We begin with a system of equations similar to Example 1." } {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 123 "eqs := \{ x^5+y^2+z^2-4, x^2+2*y^2-5, x*z-1 \};\nA := poly_algebra(x,y,z);\n T := termorder(A,plex(x,y,z));\nGB := gbasis(eqs,T);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$eqsG<%,&*&%\"xG\"\"\"%\"zGF)F)!\"\"F),**$F(\"\"&F )*$%\"yG\"\"#F)*$F*F1F)!\"%F),(*$F(F1F)F/F1!\"&F)" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"AG%,Ore_algebraG" }}{PARA 11 "" 1 "" {XPPMATH 20 "6 #>%\"TG%+term_orderG" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%#GBG7%,*\"\" #\"\"\"*$%\"zG\"\"(F'*$F*\"\"&!\"$*$F*\"\"$!\"\",,*$%\"yGF'\"\"%F,!\"# F/F0F*F(!#5F(,*%\"xGF'*$F*\"\"'F'*$F*F5F.*$F*F'F1" }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 81 "GByz := select(eq -> not has(eq,x), GB);\nGB z := select(eq -> not has(eq,y),GByz);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%%GByzG7$,*\"\"#\"\"\"*$%\"zG\"\"(F'*$F*\"\"&!\"$*$F*\"\"$!\"\" ,,*$%\"yGF'\"\"%F,!\"#F/F0F*F(!#5F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6 #>%$GBzG7#,*\"\"#\"\"\"*$%\"zG\"\"(F'*$F*\"\"&!\"$*$F*\"\"$!\"\"" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 23 "Solve for possible z's:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "zsols := \{solve(\{op(GBz)\},z)\};" }} {PARA 12 "" 1 "" {XPPMATH 20 "6#>%&zsolsG<$<#/%\"zG-%'RootOfG6#,0*$%#_ ZG\"\"'\"\"#*$F.\"\"&F0*$F.\"\"%!\"\"*$F.\"\"$F5*$F.F0!\"#F.F9F9\"\"\" <#/F(F:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 293 "This can't be solved \+ by radicals! It could be done by numerical approximation, but that's \+ anathema to a symbollic computation system, so Maple is able to work w ith symbollic solutions, i.e., it works in an extension field of the f orm k[_Z]/(2 _Z^6 + 2 _Z^5 - _Z^4 - _Z^3 - 2 _Z^2 - 2 _Z - 2)." } {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 429 "sols : = NULL:\nfor zsol in zsols do\n lprint(`Trying`,zsol);\n ysols := \{solve(\{op(subs(zsol,GByz))\},y)\};\n for ysol in ysols do\n lprint(` Trying`,zsol,ysol);\n xsols := \{solve(\{o p(subs(zsol,ysol,GB))\},x)\};\n if xsols<>\{\} then\n \+ print(`Found solutions:`,zsol,ysol,xsols);\n sols := sols, op(map(xsol -> \{op(xsol),op(ysol),op(zsol)\},xsols)):\n fi\n od\nod;\n'sols' = sols;" }}{PARA 6 "" 1 "" {TEXT -1 60 "Trying \+ \{z = RootOf(2*_Z^6+2*_Z^5-_Z^4-_Z^3-2*_Z^2-2*_Z-2)\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%&ysolsG<#<#/%\"yG,$-%'RootOfG6#,,*$%#_ZG\"\"#\" \"\"*$-F+6#,0*$F/\"\"'F0*$F/\"\"&F0*$F/\"\"%!\"\"*$F/\"\"$FF>F3F1!#5F1#F1F0" }}{PARA 6 "" 1 "" {TEXT -1 237 " Try ing \{z = RootOf(2*_Z^6+2*_Z^5-_Z^4-_Z^3-2*_Z^2-2*_Z-2)\} \{y = 1/ 2*RootOf(_Z^2-2*RootOf(2*_Z^6+2*_Z^5-_Z^4-_Z^3-2*_Z^2-2*_Z-2)^5+3*Root Of(2*_Z^6+2*_Z^5-_Z^4-_Z^3-2*_Z^2-2*_Z-2)^3+RootOf(2*_Z^6+2*_Z^5-_Z^4- _Z^3-2*_Z^2-2*_Z-2)-10)\}" }}{PARA 12 "" 1 "" {XPPMATH 20 "6&%1Found~s olutions:G<#/%\"zG-%'RootOfG6#,0*$%#_ZG\"\"'\"\"#*$F,\"\"&F.*$F,\"\"%! \"\"*$F,\"\"$F3*$F,F.!\"#F,F7F7\"\"\"<#/%\"yG,$-F(6#,,F6F8*$F'F0F7*$F' F5F5F'F8!#5F8#F8F.<#<#/%\"xG,.F3F8F@F8*$F'F2F8FA#F3F.*$F'F.FJF'F3" }} {PARA 6 "" 1 "" {TEXT -1 16 "Trying \{z = 1\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%&ysolsG<#<#/%\"yG-%'RootOfG6#,&*$%#_ZG\"\"#\"\"\"!\"# F0" }}{PARA 6 "" 1 "" {TEXT -1 42 " Trying \{z = 1\} \{y = RootO f(_Z^2-2)\}" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&%1Found~solutions:G<#/% \"zG\"\"\"<#/%\"yG-%'RootOfG6#,&*$%#_ZG\"\"#F'!\"#F'<#<#/%\"xGF'" }} {PARA 12 "" 1 "" {XPPMATH 20 "6#/%%solsG6$<%/%\"zG-%'RootOfG6#,0*$%#_Z G\"\"'\"\"#*$F.\"\"&F0*$F.\"\"%!\"\"*$F.\"\"$F5*$F.F0!\"#F.F9F9\"\"\"/ %\"xG,.F5F:*$F)F2F:*$F)F4F:*$F)F7#F5F0*$F)F0FAF)F5/%\"yG,$-F*6#,,F8F:F >F9F@F7F)F:!#5F:#F:F0<%/F(F:/FD-F*6#,&F8F:F9F:/F