{VERSION 3 0 "SGI MIPS UNIX" "3.0" } {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 "" 1 18 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 257 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 258 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 259 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 260 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 261 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 262 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 263 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 264 "" 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 265 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 266 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 267 "" 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 268 "" 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 269 "" 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 270 "" 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 271 "" 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 272 "" 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 273 "" 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 274 "" 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 275 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 276 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 277 "" 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 278 "" 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 279 "" 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 280 "" 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 281 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 282 "" 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 283 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 284 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 285 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 286 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 287 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 288 "" 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 }{PSTYLE "Normal " -1 0 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 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 "Courier" 1 10 0 0 255 1 0 0 0 0 0 1 3 0 3 }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 8 4 0 0 0 0 0 0 -1 0 }{PSTYLE "Heading 2" 3 4 1 {CSTYLE "" -1 -1 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 }0 0 0 -1 8 2 0 0 0 0 0 0 -1 0 }{PSTYLE "Warning" 2 7 1 {CSTYLE "" -1 -1 "" 0 1 0 0 255 1 0 0 0 0 0 0 1 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Map le 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 "" 0 256 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } 0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 257 1 {CSTYLE "" -1 -1 " " 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 } {PSTYLE "" 0 258 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } 0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 259 1 {CSTYLE "" -1 -1 " " 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 } {PSTYLE "" 0 260 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } 0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 261 1 {CSTYLE "" -1 -1 " " 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 } {PSTYLE "" 0 262 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } 0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 263 1 {CSTYLE "" -1 -1 " " 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 } {PSTYLE "" 0 264 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 1 0 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 31 "Applications of Groebner \+ basis." }}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 101 "Testing if a polynomi al g is in the ideal, or in the radical ideal generated by polynomials f1,..,fm." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 91 "This is the first application, it is the problem that Groebner \+ basis was designed to solve." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "f1:=x^2+y^2+z^2-3;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#f1G,**$)% \"xG\"\"#\"\"\"\"\"\"*$)%\"yGF)F*F+*$)%\"zGF)F*F+!\"$F+" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "f2:=x*y+y*z+z*x-3;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#f2G,**&%\"xG\"\"\"%\"yGF(F(*&F)\"\"\"%\"zGF(F(* &F,F+F'F+F(!\"$F(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "f3:=x* y*z+x+y+z-4;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#f3G,,*(%\"xG\"\"\"% \"yGF(%\"zGF(F(F'F(F)F(F*F(!\"%F(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "g:=(z-1)*(z^2+4*z+7);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"gG*&,&%\"zG\"\"\"!\"\"F(F(,(*$)F'\"\"#\"\"\"F(F'\"\"%\"\"(F( F(" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 20 "Is g in (f1,f2,f3)? " } {TEXT 287 49 "This can be answered with any admissible ordering" } {TEXT -1 8 ". Note: " }{TEXT 288 58 "if any ordering will do, then tak e a total degree ordering" }{TEXT -1 33 " because these tend to be fas ter." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "with(Groebner):" }} }{EXCHG {PARA 0 "" 0 "" {TEXT -1 72 "Type ?termorder to find out the s yntax of the ordering, let's take tdeg:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "ord:=tdeg(x,y,z);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6# >%$ordG-%%tdegG6%%\"xG%\"yG%\"zG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "F:=\{f1,f2,f3\};" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#> %\"FG<%,**$)%\"xG\"\"#\"\"\"\"\"\"*$)%\"yGF*F+F,*$)%\"zGF*F+F,!\"$F,,* *&F)F,F/F,F,*&F/F+F2F,F,*&F2F+F)F+F,F3F,,,*(F)F+F/F+F2F+F,F)F,F/F,F2F, !\"%F," }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "GB:=gbasis(F,ord) ;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%#GBG7(,**&%\"xG\"\"\"%\"yGF)F)* &F*\"\"\"%\"zGF)F)*&F-F,F(F,F)!\"$F),**$)F(\"\"#F,F)*$)F*F3F,F)*$)F-F3 F,F)F/F),.F(!\"\"F*F9F-!\"%\"\"%F)*&F*F,F7F,F)*&F7F,F(F,F),2*$)F*\"\"$ F,F)*&F-F,F5F,F)F " 0 "" {MPLTEXT 1 0 17 "reduce(g,GB,ord);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,**$)%\"zG\"\"$\"\"\"\"\"\"*$)F&\"\"#F(F'F&F '!\"(F)" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 127 "Not zero, so g is not in the ideal (f1,f2,f3). So g can not be written as a R-linear combin ation of f1,f2,f3, where R=C[x,y,z]." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 159 "Let's consider another question: Is it true or false, that g(alpha1,alpha2,alpha3) is always zero for all so lutions (alpha1,alpha2,alpha3) of f1=0, f2=0, f3=0?" }}{PARA 0 "" 0 " " {TEXT -1 87 "We know that this question is equivalent to: is g in t he radical ideal of (f1,f2,f3) ?" }}{PARA 0 "" 0 "" {TEXT -1 139 "We k now that this is equivalent to: does there exist a positive integer n \+ such that g^n in the ideal (f1,f2,f3)? And this is equivalent to:" }} {PARA 0 "" 0 "" {TEXT -1 70 "does there exist a positive integer n, su ch that reduce(g^n,GB,ord)=0?" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "reduce(g^1,GB,ord);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,**$)%\"z G\"\"$\"\"\"\"\"\"*$)F&\"\"#F(F'F&F'!\"(F)" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 19 "reduce(g^2,GB,ord);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,2*$)%\"zG\"\"$\"\"\"\"\"\"*$)F&\"\"#F(F)F&!\"\"F-F)*&F&F)%\"xGF )!\"#*&%\"yGF)F&F(F0F/F,F2F," }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 " # g^3, g^4, ..." }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 271 "This i s of course not a good method, how can we ever know up to which n to g o with g^n? So it seems we can only do this with Groebner basis once w e can bound the n. This, however, isn't so, we can do this problem wit h Groebner basis even if we don't have any bound for n." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 19 "Namely, as follows: " }}{PARA 0 "" 0 "" {TEXT -1 49 "g in radical ideal of (f1,..,fm), if \+ and only if:" }}{PARA 0 "" 0 "" {TEXT -1 62 "for all solutions of f1,. .,fm we have that g=0, if and only if" }}{PARA 0 "" 0 "" {TEXT -1 70 " there are no solutions of f1=0, f2=0,..,fm=0 and g<>0, if and only if: " }}{PARA 0 "" 0 "" {TEXT -1 110 "there are no solutions of f1=0,.,fm= 0, and t*g-1 = 0 where t is a new variable. And this holds if and only if:" }}{PARA 0 "" 0 "" {TEXT -1 80 "1 is an element of the ideal (f1, f2..,fm, t*g-1). And this holds if and only if:" }}{PARA 0 "" 0 "" {TEXT -1 181 "reduce(1, gbasis(f1,..,fm,t*g-1), ..) =0, which holds if and only if the gbasis has a non-zero constant (this constant will th en always be 1 because it will be reduced by primpart)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 325 "So we see that the \+ inequality g<>0 is translated to an equality by introducing a new vari able, and then we end up with only equalities, and we see now that g i s in the radical, if and only if the new equations are inconsistent, w hich will hold if and only if 1 is in the ideal, but then it will also be in the Groebner basis." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 41 "gbasis(\{f1,f2,f3, t*g-1\}, tdeg(x,y,z,t));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7#\"\"\"" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 49 "So g^n must be in (f1,f2,f3) for some positive n:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "reduce(g^3,GB,ord);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"!" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 182 "So we see that we can not only check if g is in the ideal, we can also check if g is in the radical ideal. Note that it is not so easy to find a Groebner bas is for the radical ideal." }}}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 52 "El iminating variables; Solving polynomial equations." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 101 "Take again the same poly nomials f1,f2,f3 in x,y,z and think of them as equations. Suppose we w ant to " }{TEXT 257 52 "eliminate the variable x from the equations f1 ,f2,f3" }{TEXT -1 117 ", so we want to find all elements of the ideal \+ that do not have the variable x, in other words we want to compute the " }{TEXT 258 49 " intersection of C[y,z] and the ideal (f1,f2,f3)." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 25 "If we tak e the following " }{TEXT 259 21 "elimination ordering:" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "ord:=lexdeg([x],[y,z]);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$ordG-%'lexdegG6$7#%\"xG7$%\"yG%\"zG" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 271 "then x will be larger than any po wer product in [y,z], which means that in the reduction algorithm at f irst all the focus will be on the variable x. The reduction algorithm \+ will do a maximal effort to eliminate the variable x. Now it is not ha rd to prove that if we take:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "F;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#<%,**$)%\"xG\"\"#\"\"\"\"\" \"*$)%\"yGF(F)F**$)%\"zGF(F)F*!\"$F*,**&F'F*F-F*F**&F-F)F0F*F**&F0F)F' F)F*F1F*,,*(F'F)F-F)F0F)F*F'F*F-F*F0F*!\"%F*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "GB:=gbasis(F,ord);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%#GBG7(,0*&)%\"yG\"\"#\"\"\")%\"zGF*F+\"\"\"*$F(F+!\"\"*&F)F.F- F.!\"%*$F,F+F0F)\"\"%F-F4!\"$F.,:!\"#F.F)F*F1F7F-F*F/F.F3F.*&F)F+F,F+F 0*&F-F+F(F+F0*$)F)\"\"$F+F0*$)F-FF+F)F+F.,:*$)F)F 4F+F.*$)F-F4F+F.F:F*F9F*F8F*F=F*F/F7F1F4F3F7F)!#;F-FF\"#AF.,.*$)F-\"\" &F+F.FDF.F=F7F3!#5F-\"# " 0 "" {MPLTEXT 1 0 43 "GB_yz:=[seq(`if`(has(i,x), NULL, i),i=GB)];" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%&GB_yzG7',0*&)%\"yG\"\"#\"\"\")%\"zGF*F+\"\"\"*$F(F+! \"\"*&F)F.F-F.!\"%*$F,F+F0F)\"\"%F-F4!\"$F.,:!\"#F.F)F*F-F*F1F7F/F.F3F .*&F)F+F,F+F0*&F-F+F(F+F0*$)F)\"\"$F+F0*$)F-FF+F) F+F.,:*$)F)F4F+F.*$)F-F4F+F.F:F*F9F*F8F*F=F*F/F7F1F4F3F7F)!#;F-FF\"#AF .,.*$)F-\"\"&F+F.FDF.F=F7F3!#5F-\"# " 0 "" {MPLTEXT 1 0 26 "GB_yz := remove(has,GB,x);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%&GB_yzG7',0*&)%\"yG\"\"#\"\"\")%\"zGF*F+\"\"\"*$F(F+! \"\"*&F)F.F-F.!\"%*$F,F+F0F)\"\"%F-F4!\"$F.,:!\"#F.F)F*F1F7F-F*F/F.F3F .*&F)F+F,F+F0*&F-F+F(F+F0*$)F)\"\"$F+F0*$)F-FF+F) F+F.,:*$)F)F4F+F.*$)F-F4F+F.F:F*F9F*F8F*F=F*F/F7F1F4F3F7F)!#;F-FF\"#AF .,.*$)F-\"\"&F+F.FDF.F=F7F3!#5F-\"# " 0 "" {MPLTEXT 1 0 95 "resultant(f1,f2,x); # Note: this is always in the ideal (f1,f2), hence in I, and hence in I_yz." }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,4*&)%\"yG\"\"#\"\"\")%\"zGF'F(\"\"$ *&F&\"\"\"F*F-!#7\"\"*F-*$)F&\"\"%F(F-*&)F&F+F(F*F(F'*&)F*F+F(F&F(F'*$ )F*F2F(F-*$F%F(!\"$*$F)F(F:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "reduce(%,GB_yz,ord);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"!" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 81 "resultant(f1,f3,x); # This i s in the ideal (f1,f3), hence in I, and hence in I_yz" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,8\"#8\"\"\"%\"yG!\")%\"zGF'*$)F&\"\"#\"\"\"F+*&F& F%F(F%!\"%*$)F(F+F,F+*&)F&\"\"%F,F0F,F%*&)F&\"\"$F,F(F,F+*&)F(F3F,F*F, F%*&)F(F6F,F&F,F+*&F*F,F0F,!\"$" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "reduce(%,GB_yz,ord);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"! " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 35 "resultant(f2,f3,x); # A lso in I_yz." }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,0\"\"$\"\"\"%\"yG!\"% *&F&F%%\"zGF%\"\"%F)F'*$)F&\"\"#\"\"\"F%*$)F)F-F.F%*&F,F.F0F.!\"\"" }} }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "reduce(%,GB_yz,ord);" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"!" }}}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 40 "Computing the image of a polynomial map." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 25 "A polynomial map is a \+ map" }}{PARA 0 "" 0 "" {TEXT -1 15 "F: C^n --> C^m " }}{PARA 0 "" 0 " " {TEXT -1 237 "that is defined by polynomials. So if P is a vector in C^n then Psi(P) in C^m, so it has m entries. So the polynomial map mu st consist of m polynomials, and since these polynomials must be funct ions on C^n they must have n variables. So:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 69 "m polynomials in n variables de fine a polynomial map from C^n to C^m." }}{PARA 0 "" 0 "" {TEXT -1 22 "Example with n=2, m=3." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "restart; with(Groebner);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#75%%fglmG%'gbasisG%'gsolveG%+hilbertdimG%,hi lbertpolyG%.hilbertseriesG%-inter_reduceG%*is_finiteG%,is_solvableG%*l eadcoeffG%(leadmonG%)leadtermG%(normalfG%/pretend_gbasisG%'reduceG%&sp olyG%*termorderG%*testorderG%)univpolyG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 44 "F:=[ x1^2+x1*x2, x1^2*x2+x2^2, x1*x2-x1^2 ];" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"FG7%,&*$)%#x1G\"\"#\"\"\"\"\"\"*&F )F,%#x2GF,F,,&*&F(F+F.F+F,*$)F.F*F+F,,&F-F,F'!\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "P:=[5,6];" }}{PARA 11 "" 1 "" {XPPMATH 20 "6 #>%\"PG7$\"\"&\"\"'" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 22 "Image of P under F is:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 29 "Q:=subs(x1= P[1], x2=P[2], F);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"QG7%\"#b\"$' =\"\"&" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 152 "So the image of P unde r F is Q, and so P is one of the pre-images of Q under F. Are there an y other pre-images? That is, compute all P such that F(P)=Q." }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "F-Q;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7%,(!#b\"\"\"*$)%#x1G\"\"#\"\"\"F&*&F)F&%#x2GF&F&,(!$'= F&*&F(F+F-F+F&*$)F-F*F+F&,(!\"&F&F,F&F'!\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "gbasis(%, plex(x1,x2));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7$,&!\"'\"\"\"%#x2GF&,&%#x1GF&!\"&F&" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 49 "So in this example, P is the only pre-image of \+ Q." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 70 "How can we compute the image of F, the set F(C^2) = \{F(P) | P in C^2\}? " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 64 "That \+ is in general not an easy question. What we compute is the " }{TEXT 260 16 "Zariski-closure " }{TEXT -1 236 "of this set. Recall that when V is a set, then I(V) is the ideal of V, the set of polynomials that \+ vanish on V. And V(I(V)) is the solution set of I(V), which of course \+ includes the set V. Now V(I(V)) is called the Zariski-closure of V." } }{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 285 "What we will compute is the Zariski-closure of F(C^2), which in this example \+ happens to be equal to F(C^2), but this need not always be the case (e xample: (x1,x2) -> (x1,x1*x2), the image is all points in C^2 except t he ones of the form (0, not 0). The Zariski-closure of that is C^2)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 254 "Lets s ay that P=[x1,x2], so F(P) is just the list F above. What are the poin ts Q=F(P) that can be obtained this way, the points Q=[y1, y2, y3] in \+ C^3 that are an image of F? Well Q is in the image of F if and only i f Q = F(P) has a solution x1=.., x2=.." }}{PARA 0 "" 0 "" {TEXT -1 44 "So the equations we have are: F-Q = [0,0,0]." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "Q:=[y1,y2,y3];" }}{PARA 11 "" 1 "" {XPPMATH 20 " 6#>%\"QG7%%#y1G%#y2G%#y3G" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "F-Q;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7%,(%#y1G!\"\"*$)%#x1G\"\"#\" \"\"\"\"\"*&F)F,%#x2GF,F,,(%#y2GF&*&F(F+F.F+F,*$)F.F*F+F,,(%#y3GF&F-F, F'F&" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 368 "Notice that this set F-Q is already a Groebner basis with respect to the ordering lexdeg([y1,y 2,y3], [x1,x2]). We want to eliminate x1 and x2 to get equations in y1 , y2, y3. For this we need an elimination ordering to eliminate x1 and x2, so we need lexdeg([x1,x2], [y1,y2,y3]). The set F-Q is not yet a \+ Groebner basis w.r.t. that ordering, so computation is required." }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 43 "GB:=gbasis(%, lexdeg([x1,x2] , [y1,y2,y3]));" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%#GBG7,,F*&%#y3G\" \"\")%#y1G\"\"$\"\"\"!\")*&F+F))F(F,F-F.*&)F+\"\"#F-)F(F3F-!#7*$)F(\" \"%F-!\"#*$)F+F8F-F9*$)F+\"\"&F-F)*(F+F-)%#y2GF3F-F(F-\"#;*&F0F-F2F-F3 *$)F(F>F-!\"\"*&F2F-F@F-F.*&F0F-FAF)F.*&F4F-F*F-F9*&F7F-F+F-F)*&F@F-F4 F-F.*&FAF-F*F-\"\")*(FAF-F(F-F2F-FM*(F4F-F+F-FAF-F.*&F(F-F;F-FF,.*&%#x 1GF)F+F-F3*&%#x2GF)F(F-F8*&FSF-F(F-F3*&FSF-FAF-!\"%*$F2F-F)*$F4F-FF,.* &FUF-F+F-F8FWFXFRF9FVF9FYF)FZFF,<*(F+F-FSF-F(F-FXFYF3*&F+F-F(F-F8*&FAF -F(F-F8*&F+F-FAF-FXFZF3*(F+F-FSF-FAF-F8*$F*F-FF*&F+F-F4F-F)*&F4F-FSF-F X*(F(F-FSF-FAF-FX*&F(F-F2F-F)*$F0F-FF,0FYF)*&FSF-F2F-F)F_oFFFinF3FjnF3 F[oF9FZF),>*&F@F-F(F-FM*&F+F-F@F-F.*&FAF-F4F-F.F^o!#9F]oF9F1F9Fao!#5*( F+F-FAF-F(F-FBFbo!\"'*&F2F-FAF-FMF6F)*&F0F-FSF-FMF:F)*(F+F-F4F-FSF-FM, LF'F3F/\"\"'F1FapF6F3F?\"#CFDF)*&FAF-F;F-F)FGFM*&FAF-F7F-F)FHF\\pFIF3F JF9*&)FAF,F-F(F-FM*&F+F-FfpF-F.FK!#;FLF9FN!#=*(FAF-F2F-F4F-F9*(F0F-FSF -FAF-FBFO!#AFPFF,*FVF)FAF9*$)FUF3F-F3FRF),(*&FSF-FUF-F3F+FFF(FF,(F(F)* $)FSF3F-F3F+FF" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 72 "GB_Y := r emove(has, GB, \{x1,x2\}); # Throw away things that have x1 or x2" }} {PARA 12 "" 1 "" {XPPMATH 20 "6#>%%GB_YG7#,F*&%#y3G\"\"\")%#y1G\"\"$\" \"\"!\")*&F+F))F(F,F-F.*&)F+\"\"#F-)F(F3F-!#7*$)F(\"\"%F-!\"#*$)F+F8F- F9*$)F+\"\"&F-F)*(F+F-)%#y2GF3F-F(F-\"#;*&F0F-F2F-F3*$)F(F>F-!\"\"*&F2 F-F@F-F.*&F0F-FAF)F.*&F4F-F*F-F9*&F7F-F+F-F)*&F@F-F4F-F.*&FAF-F*F-\"\" )*(FAF-F(F-F2F-FM*(F4F-F+F-FAF-F.*&F(F-F;F-FF" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 76 "So we see that the image of F will be contained in the zero set of GB_Y. So:" }}{PARA 0 "" 0 "" {TEXT -1 22 "F(C^2) subset V (GB_Y)." }}{PARA 0 "" 0 "" {TEXT -1 110 "In fact, with such a computat ion we always find a set GB_Y such that V(GB_Y) is the Zariski-closure of F(C^2)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 69 "When Q is in V(GB_Y), how to compute a pre-image (if it exists) of Q?" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "select(has,GB,x1) ;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#7+,.*&%#x1G\"\"\"%#y1GF'\"\"#*&%# x2GF'%#y3GF'\"\"%*&F&\"\"\"F,F/F)*&F&F/%#y2GF'!\"%*$)F(F)F/F'*$)F,F)F/ !\"\",.*&F+F/F(F/F-F0F2F%!\"#F.F:F3F'F5F7,<*(F(F/F&F/F,F/F2F3F)*&F(F/F ,F/F-*&F1F/F,F/F-*&F(F/F1F/F2F5F)*(F(F/F&F/F1F/F-*$)F(\"\"$F/F7*&F(F/F 6F/F'*&F6F/F&F/F2*(F,F/F&F/F1F/F2*&F,F/F4F/F'*$)F,FCF/F7,0F3F'*&F&F/F4 F/F'FEF7F=F)F>F)F?F:F5F',>*&)F1F)F/F,F/\"\")*&F(F/FNF/!\")*&F1F/F6F/FQ FD!#9FAF:*&F4F/F6F/F:FG!#5*(F(F/F1F/F,F/\"#;FH!\"'*&F4F/F1F/FO*$)F,F-F /F'*&FIF/F&F/FO*$)F(F-F/F'*(F(F/F6F/F&F/FO,L*&F,F/FBF/F)*&F(F/FIF/\"\" 'FTF]oFZF)*(F(F/FNF/F,F/\"#C*$)F,\"\"&F/F'*&F1F/FhnF/F'*&F4F/FNF/FO*&F 1F/FenF/F'*&FIF/F1F/FX*&F6F/FBF/F)*&FenF/F(F/F:*&)F1FCF/F,F/FO*&F(F/Fj oF/FQ*&FNF/F6F/!#;*&F1F/FBF/F:*(F1F/F,F/F4F/!#=*(F1F/F4F/F6F/F:*(FIF/F &F/F1F/FW*(F6F/F(F/F1F/!#A*&F,F/FhnF/F7,*F.F'F1F:*$)F+F)F/F)F%F',(*&F& F/F+F/F)F(F7F,F7,(F,F'*$)F&F)F/F)F(F7" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "remove(has,%,x2);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6# 7',<*(%#y1G\"\"\"%#x1GF'%#y3GF'!\"%*$)F&\"\"#\"\"\"F-*&F&F.F)F.\"\"%*& %#y2GF'F)F.F0*&F&F.F2F.F**$)F)F-F.F-*(F&F.F(F.F2F.F0*$)F&\"\"$F.!\"\"* &F&F.F5F.F'*&F5F.F(F.F**(F)F.F(F.F2F.F**&F)F.F,F.F'*$)F)F9F.F:,0F+F'*& F(F.F,F.F'F*&)F2F-F.F)F.\"\")*&F&F.FFF.!\")*&F2 F.F5F.FIF;!#9F7FC*&F,F.F5F.FCF>!#5*(F&F.F2F.F)F.\"#;F?!\"'*&F,F.F2F.FG *$)F)F0F.F'*&F@F.F(F.FG*$)F&F0F.F'*(F&F.F5F.F(F.FG,L*&F)F.F8F.F-*&F&F. F@F.\"\"'FLFenFRF-*(F&F.FFF.F)F.\"#C*$)F)\"\"&F.F'*&F2F.FVF.F'*&F,F.FF F.FG*&F2F.FSF.F'*&F@F.F2F.FP*&F5F.F8F.F-*&FSF.F&F.FC*&)F2F9F.F)F.FG*&F &F.FboF.FI*&FFF.F5F.!#;*&F2F.F8F.FC*(F2F.F)F.F,F.!#=*(F2F.F,F.F5F.FC*( F@F.F(F.F2F.FO*(F5F.F&F.F2F.!#A*&F)F.FVF.F:,(F)F'*$)F(F-F.F-F&F:" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "remove(has,%,x1^2);" }} {PARA 12 "" 1 "" {XPPMATH 20 "6#7&,<*(%#y1G\"\"\"%#x1GF'%#y3GF'!\"%*$) F&\"\"#\"\"\"F-*&F&F.F)F.\"\"%*&%#y2GF'F)F.F0*&F&F.F2F.F**$)F)F-F.F-*( F&F.F(F.F2F.F0*$)F&\"\"$F.!\"\"*&F&F.F5F.F'*&F5F.F(F.F**(F)F.F(F.F2F.F **&F)F.F,F.F'*$)F)F9F.F:,0F+F'*&F(F.F,F.F'F*&)F 2F-F.F)F.\"\")*&F&F.FFF.!\")*&F2F.F5F.FIF;!#9F7FC*&F,F.F5F.FCF>!#5*(F& F.F2F.F)F.\"#;F?!\"'*&F,F.F2F.FG*$)F)F0F.F'*&F@F.F(F.FG*$)F&F0F.F'*(F& F.F5F.F(F.FG,L*&F)F.F8F.F-*&F&F.F@F.\"\"'FLFenFRF-*(F&F.FFF.F)F.\"#C*$ )F)\"\"&F.F'*&F2F.FVF.F'*&F,F.FFF.FG*&F2F.FSF.F'*&F@F.F2F.FP*&F5F.F8F. F-*&FSF.F&F.FC*&)F2F9F.F)F.FG*&F&F.FboF.FI*&FFF.F5F.!#;*&F2F.F8F.FC*(F 2F.F)F.F,F.!#=*(F2F.F,F.F5F.FC*(F@F.F(F.F2F.FO*(F5F.F&F.F2F.!#A*&F)F.F VF.F:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "sort(%,(i,j) -> ev alb(length(i) < length(j)));" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#7&,0*$ )%#y1G\"\"#\"\"\"\"\"\"*&%#x1GF*F&F)F**&)%#y3GF(F)F,F)!\"\"*&F'F*F/F*F (*&%#y2GF*F/F)F(*&F'F)F3F)!\"#*$F.F)F*,<*(F'F)F,F)F/F)!\"%F%F(F1\"\"%F 2F:F4F9F6F(*(F'F)F,F)F3F)F:*$)F'\"\"$F)F0*&F'F)F.F)F*F-F9*(F/F)F,F)F3F )F9*&F/F)F&F)F**$)F/F>F)F0,>*&)F3F(F)F/F)\"\")*&F'F)FFF)!\")*&F3F)F.F) FIF?!#9FF)F/F)FG*&F'F)Fbo F)FI*&FFF)F.F)!#;*&F3F)F=F)F5*(F3F)F/F)F&F)!#=*(F3F)F&F)F.F)F5*(FCF)F, F)F3F)FO*(F.F)F'F)F3F)!#A*&F/F)FVF)F0" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "%[1];" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,0*$)%#y1G\" \"#\"\"\"\"\"\"*&%#x1GF)F%F(F)*&)%#y3GF'F(F+F(!\"\"*&F&F)F.F)F'*&%#y2G F)F.F(F'*&F&F(F2F(!\"#*$F-F(F)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "P1:=solve(%,x1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#P1G,$*& ,,*$)%#y1G\"\"#\"\"\"\"\"\"*&F*F-%#y3GF-F+*&%#y2GF-F/F,F+*&F*F,F1F,!\" #*$)F/F+F,F-F,,&F(F-F4!\"\"!\"\"F7" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 65 "map(numer@normal,subs(x1=P1,remove(has,select(has,GB, x2),x2^2)));" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#7%,<*$)%#y1G\"\"$\"\" \"!\"#*&%#y3G\"\"\")F'\"\"#F)!\"'*(F'F-%#y2GF-F,F)\"\")*&F.F)F2F)F3*&F 'F))F,F/F)F0*(%#x2GF-F,F)F.F)\"\"%*&F8F))F,F(F)!\"%*$F;F)F**&)F2F/F)F, F)F3*&F'F)F?F)!\")*$)F'F9F)F-*&F.F)F6F)F**$)F,F9F)F-,<*&F8F)F&F)F9*(F8 F)F'F)F6F)FF3F@FA*&F2F)F6F)F3F%F/F+\"\"'F5FKF=F/FBF-FDF*FEF-,4* &F8F)F.F)F**(F8F)F,F)F'F)F<*(F8F)F2F)F,F)F<*(F8F)F'F)F2F)F9*&F8F)F6F)F *F%!\"\"F5F-F+FRF=F-" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "sor t(%,(i,j) -> evalb(length(i) < length(j)));" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#7%,4*&%#x2G\"\"\")%#y1G\"\"#\"\"\"!\"#*(F&F+%#y3GF'F)F' !\"%*(F&F+%#y2GF'F.F+F/*(F&F+F)F+F1F+\"\"%*&F&F+)F.F*F+F,*$)F)\"\"$F+! \"\"*&F)F+F5F+F'*&F.F+F(F+F9*$)F.F8F+F',<*&F&F+F7F+F3*(F&F+F)F+F5F+F/* (F)F+F1F+F.F+\"\")*&)F1F*F+F.F+FB*&F)F+FDF+!\")*&F1F+F5F+FBF6F*F;\"\"' F:FHF " 0 "" {MPLTEXT 1 0 19 "P2:=solve(%[1],x2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#P2G,$*&,**$)%#y1G\"\"$\"\"\"\"\"\"*&F*F-)%#y3G \"\"#F,!\"\"*&F0F-)F*F1F,F-*$)F0F+F,F2F,,,*$F4F,F-*&F*F,F0F,F1*&%#y2GF -F0F,F1*&F*F,F;F,!\"#*$F/F,F-!\"\"#F2F1" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "P:=[P1,P2];" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"PG 7$,$*&,,*$)%#y1G\"\"#\"\"\"\"\"\"*&F+F.%#y3GF.F,*&%#y2GF.F0F-F,*&F+F-F 2F-!\"#*$)F0F,F-F.F-,&F)F.F5!\"\"!\"\"F8,$*&,**$)F+\"\"$F-F.*&F+F-F6F- F8*&F0F-F*F-F.*$)F0F?F-F8F-F(F9#F8F," }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 52 "So the image of P must be Q=[y1,y2,y3]. Let's check:" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 34 "image_P := subs(x1=P1, x2=P2 , F);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%(image_PG7%,&*&*$),,*$)%#y 1G\"\"#\"\"\"\"\"\"*&F-F0%#y3GF0F.*&%#y2GF0F2F/F.*&F-F/F4F/!\"#*$)F2F. F/F0F.F/F/*$),&F+F0F7!\"\"\"\"#F/!\"\"F0*&,**$)F-\"\"$F/F0*&F-F/F8F/F< *&F2F/F,F/F0*$)F2FCF/F#F0F.,&*&*&F*F0F@F0F/*$)F;\"\"#F/F>#F#F0\"\"%,&F?FHF'F<" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "Q;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7%%#y1G%#y2 G%#y3G" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 35 "This doesn't exactly lo ok the same." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 54 "should_be_z ero:=map(numer, map(normal, image_P - Q ));" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%/should_be_zeroG7%,F*&%#y3G\"\"\")%#y1G\"\"$\"\"\"\" \")*&F+F))F(F,F-F.*&)F+\"\"#F-)F(F3F-\"#7*$)F(\"\"%F-F3*$)F+F8F-F3*$)F +\"\"&F-!\"\"*(F+F-)%#y2GF3F-F(F-!#;*&F0F-F2F-!\"#*$)F(F=F-F)*&F2F-F@F -F.*&F0F-FAF)F.*&F4F-F*F-F3*&F7F-F+F-F>*&F@F-F4F-F.*&FAF-F*F-!\")*(FAF -F(F-F2F-FM*(F4F-F+F-FAF-F.*&F(F-F:F-F),R*$)F+\"\"(F-F)*&)F+\"\"'F-F(F -F)*$FVF-FD*&FAF-F*&FFF-F+F-Fgn*(F7F-F+F-FAF-!#C*$)F(FTF-F>*&F@F-F7F-FM*&FFF -FAF-FM*$FhoF-FD,FF'FMF/FMF1FgnF6FDF9FDF;F)F?F_oFCF3FEF>FGFMFHFMFIFDFJ F)FKFMFLF.FNF.FOFMFPF>" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 343 "This s hould be zero, and it isn't. However, note that when we computed the p re-image P of Q, that that was under an assumption, namely that Q was \+ in V(GB_Y). Therefore, we shouldn't expect complete zeros here, but ju st things that become zero under our assumptions (the equations in GB_ Y). So modulo GB_Y, these polynomials should become zero:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 51 "map(normalf, should_be_zero, GB_Y, \+ tdeg(y1,y2,y3));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7%\"\"!F$F$" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 305 "Every element of F(C^2) is in V(G B_Y), but is every element of V(GB_Y) also in F(C^2)? We can find a pr e-image P when the denominators in P don't vanish, so the correspondin g points [y1,y2,y3] in V(GB_Y) are also in F(C^2), and furthermore the y have precisely one pre-image, namely the P we just computed." }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "map(denom,P);" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#7$,&*$)%#y1G\"\"#\"\"\"\"\"\"*$)%#y3GF(F)!\"\",, F%F(*&F'F*F-F*\"\"%*&%#y2GF*F-F)F1*&F'F)F3F)!\"%F+F(" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 46 "What if one of these two denominators is zero? " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 71 "gbasis(\{denom(P[1]), o p(GB), x1*t1-1\}, lexdeg([x1,x2,t1], [y1,y2,y3]));" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#7(%#y2G,&%#y1G\"\"\"%#y3GF',&*&%#t1GF'F(F'F'%#x1GF'%# x2G,&*&F,F'F+\"\"\"F'!\"\"F',&*$)F,\"\"#F0F'F(F'" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 71 "gbasis(\{denom(P[2]), op(GB), x1*t1-1\}, lexd eg([x1,x2,t1], [y1,y2,y3]));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7(%#y2 G,&%#y1G\"\"\"%#y3GF',&*&%#t1GF'F(F'F'%#x1GF'%#x2G,&*&F,F'F+\"\"\"F'! \"\"F',&*$)F,\"\"#F0F'F(F'" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 138 "We see that if we add the extra assumption that x1<>0, then it follows t hat x2=0. So these denominators can only vanish when x1=0 or x2=0." }} }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "subs(x1=0,F);" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#7%\"\"!*$)%#x2G\"\"#\"\"\"F$" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "subs(x2=0,F);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7%*$)%#x1G\"\"#\"\"\"\"\"!,$F$!\"\"" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 118 "Now we see why we get a denominator. Because when x1=0 o r x2=0, the corresponding images have not 1, but 2 pre-images." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 195 "So we se e that all points in V(GB_y) that are not of the form [0, y2, 0] and n ot of the form [y1, 0, -y1] have precisely 1 pre-image, and the remain ing points except [0,0,0] have two pre-images." }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 35 "gbasis(F - [0,0,0],plex(x1,x2,x3));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7%*$)%#x2G\"\"#\"\"\"*&%#x1G\"\"\"F&F+*$)F*F 'F(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "solve(\{op(%)\});" } }{PARA 11 "" 1 "" {XPPMATH 20 "6$<$/%#x1G\"\"!/%#x2GF&F#" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 27 "So [0,0,0] has 1 pre-image." }}}{PARA 0 " " 0 "" {TEXT -1 0 "" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 42 "Computing the inverse of a polynomial map." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 54 "Consider the following polynomial map fro m C^3 to C^3:" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "restart; wi th(Groebner):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 67 "F:=[x2+2*x 3^2-x3*x1+x2*x3^2, x2+x3+2*x3^2-x3*x1+x2*x3^2, x1-x2*x3];" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"FG7%,*%#x2G\"\"\"*$)%#x3G\"\"#\"\"\"F,*&F+F (%#x1GF(!\"\"*&F'F(F*F-F(,,F'F(F+F(F)F,F.F0F1F(,&F/F(*&F'F-F+F-F0" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "Q:=[y1,y2,y3];" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#>%\"QG7%%#y1G%#y2G%#y3G" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 229 "Is F an invertible polynomial map? That means: is F o nto and 1-1? If so, then the inverse is also a polynomial map. We can \+ check if F is invertible, and if so, we can determine the inverse. Of \+ course most maps are not invertible." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "F-Q;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7%,,%#y1G!\"\" %#x2G\"\"\"*$)%#x3G\"\"#\"\"\"F,*&F+F(%#x1GF(F&*&F'F(F*F-F(,.%#y2GF&F' F(F+F(F)F,F.F&F0F(,(%#y3GF&F/F(*&F'F-F+F-F&" }}}{EXCHG {PARA 0 "" 0 " " {TEXT -1 138 "This set is already a Groebner basis in the lexdeg([y1 ,y2,y3],[x1,x2,x3]) ordering. Lets compute a pre-image of Q by elimina ting x1,x2,x3." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 42 "gbasis(%, lexdeg([x1,x2,x3], [y1,y2,y3]));" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#7 %,(%#y1G\"\"\"%#y2G!\"\"%#x3GF&,0F%F(%#x2GF&*$)F%\"\"#\"\"\"F.*&F%F&F' F&!\"%*$)F'F.F/F.*&%#y3GF&F%F/F&*&F5F/F'F/F(,8F5F(%#x1GF&F,F&*$)F%\"\" $F/!\"#*&F-F/F'F/\"\"'*&F%F/F3F/!\"'*&F5F/F-F/F(*(F%F/F5F/F'F/F.F0F(*$ )F'F;F/F.*&F5F/F3F/F(" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 93 "Note: th e equations are of the form: x.i - something only consisting of y's, f or i = 1, 2, 3." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 50 "P := sub s( solve(\{op(%)\},\{x1,x2,x3\}), [x1,x2,x3]);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"PG7%,6%#y3G\"\"\"*$)%#y1G\"\"#\"\"\"!\"\"*$)F+\"\"$ F-F,*&F*F-%#y2GF(!\"'*&F+F()F3F,F-\"\"'*&F'F(F*F-F(*(F+F-F'F-F3F-!\"#* &F+F-F3F-F(*$)F3F1F-F:*&F'F-F6F-F(,.F+F(F)F:F;\"\"%*$F6F-F:*&F'F-F+F-F .*&F'F-F3F-F(,&F+F.F3F(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 41 " expand(subs(x1=P[1],x2=P[2],x3=P[3], F));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7%%#y1G%#y2G%#y3G" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 86 "So we see that this F is 1-1, and the unique pre-image of Q=[y1,y2 ,y3] is the point P." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 258 "" 0 "" {TEXT -1 126 "Let F=[F[1], F[2], .., F[n]] with F[i] in C[x1,..,x n] be a polynomial map from C^n to C^n. Then F is invertible if and on ly if" }}{PARA 259 "" 0 "" {TEXT -1 61 " gbasis( F - [y1,y2,..,yn] , \+ lexdeg([x1,..,xn], [y1,..,yn]))" }}{PARA 260 "" 0 "" {TEXT -1 90 "has \+ n elements, each of which is of the form: x.i - element of C[y1,..,yn] , where i=1..n." }}}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 52 "Computing a n algebraic relation between polynomials." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{SECT 1 {PARA 4 "" 0 "" {TEXT -1 21 "Transcendence degree." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 142 "Let C be a field, let V be a vector space, and let R be a ring or a field tha t contains C, for example R=C[x1,x2.,,.xn], or R=C(x1,x2,..,xn)." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 44 "Let y1,.. ,yk in V. Then y1,..,yk are called " }{TEXT 263 25 "linearly dependent over C" }{TEXT -1 111 " if there exists a non-zero vector (c1,..,ck) \+ in C^k (so not all c.i are zero) such that c1*y1+..+ck*yk=0. The " } {TEXT 262 9 "dimension" }{TEXT -1 84 " of V is the largest number k su ch that there exist y1,..,yk in V that are linearly " }{TEXT 264 2 "in " }{TEXT -1 236 "dependent over C. Note that this depends on C, for ex ample the field C(x) has dimension 1 over C(x) but is infinite dimensi onal over C. And Q(2^(1/4)) has dimension 4 over Q, dimension 2 over Q (2^(1/2)), and dimension 1 over Q(2^(1/4))." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 44 "Let y1,..,yk in R. Then y1,..,y k are called " }{TEXT 265 30 "algebraically dependent over C" }{TEXT -1 91 " if there exists a non-zero polynomial P in k entries such that P(y1,..,yk) is 0 in R. The " }{TEXT 266 20 "transcendence degree" } {TEXT -1 97 " of R over C is the largest number k such that there exis t y1,..,yk in R that are algebraically " }{TEXT 267 2 "in" }{TEXT -1 103 "dependent over C. If R=C[x1,..,xn] or R=C(x1,..,xn) then the tran scendence degree of R over C equals n." }}{PARA 0 "" 0 "" {TEXT -1 0 " " }}{PARA 0 "" 0 "" {TEXT -1 236 "For example: the transcendence degre e of C(t) over C equals 1. So that means if we take >1 elements, say: \+ u=(t^2-1)/t^3, v=t^3-t+3/(t-1), then they are algebraically dependent, which means there must exist a polynomial P(x,y) such that:" }}{PARA 0 "" 0 "" {TEXT -1 54 "P(u,v), which in Maple language is subs(x=u, y =v, P)," }}{PARA 0 "" 0 "" {TEXT -1 71 "equals zero. We've seen before that such P can be computed in Maple by:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 36 "u:=(t^2-1)/t^3; v:=t ^3-t+3/(t-1); " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"uG*&,&*$)%\"tG \"\"#\"\"\"\"\"\"!\"\"F,F+*$)F)\"\"$F+!\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"vG,(*$)%\"tG\"\"$\"\"\"\"\"\"F(!\"\"*&F*F*,&F(F+F,F +!\"\"F)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 42 "P:=resultant( n umer(x-u), numer(y-v) , t);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"PG, >!\"*\"\"\"%\"yG!\"'*&%\"xGF')F(\"\"#\"\"\"F'*&F+F.F(F'\"\"**&)F+\"\"$ F.F,F.F-F+\"#:*$F2F.!#E*$)F+F-F.\"#C*$)F+\"\"%F.!#F*&F8F.F(F.\"#D*&F2F .F(F.!#C*&F;F.)F(F3F.!\"\"*&F;F.F,F.F&*&F;F.F(F.F=" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "subs(x=u, y=v, P);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#,B!\"*\"\"\"*$)%\"tG\"\"$\"\"\"!\"'F(\"\"'*&F*F*,&F(F%! \"\"F%!\"\"!#=*&*&,&*$)F(\"\"#F*F%F/F%F%),(F&F%F(F/F-F)F7F*F**$)F(\"\" $F*F0F%*&*&F4F*F9F%F**$)F(\"\"$F*F0\"\"**&*&)F4F)F*F8F*F**$)F(\"\"*F*F 0F7*&F4F**$)F(\"\"$F*F0\"#:*&*$FEF*F**$)F(\"\"*F*F0!#E*&*$)F4F7F*F**$) F(\"\"'F*F0\"#C*&*$)F4\"\"%F*F**$)F(\"#7F*F0!#F*&*&FVF*F9F*F**$)F(\"\" 'F*F0\"#D*&*&FEF*F9F*F**$)F(\"\"*F*F0!#C*&*&FgnF*)F9F)F*F**$)F(\"#7F*F 0F/*&*&FgnF*F8F*F**$)F(\"#7F*F0F$*&*&FgnF*F9F*F**$)F(\"#7F*F0F\\o" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "normal(%);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"!" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT -1 488 "Likewise, C(x1,x2,x3), the set of all rational fu nctions in x1,x2,x3, has transcendence degree 3 over C. So whenever to take more than three elements in that set, then they will be algebrai cally dependent. In the case C(t) we only had to eliminate 1 variable \+ t, which works best with the resultant, but for the case C(x1,x2,x3) i n order to find an algebraic relation P we would need to eliminate thr ee variables x1,x2,x3, which works best with Groebner basis with an el imination ordering." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "restart;" } }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "u:=x^2+y^3; v:=x^3+y^2; w: =x*y;" }{TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"uG,&*$)%\"xG\"\"#\"\"\"\"\"\"*$)%\"yG\"\"$F*F+" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"vG,&*$)%\"xG\"\"$\"\"\"\"\"\"*$) %\"yG\"\"#F*F+" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"wG*&%\"xG\"\"\"% \"yGF'" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 269 "Now u, v and w are thr ee polynomials in C[x,y], which has only transcendence degree two over C, and so they must be algebraically dependent, i.e. there must exist a polynomial P in three variables such that P(u,v,w)=0. How to find s uch P is the topic of this worksheet." }}{PARA 0 "" 0 "" {TEXT -1 0 " " }}{PARA 0 "" 0 "" {TEXT -1 56 "Let's use the names U,V,W for the var iables of P. So we " }{TEXT 261 56 "want to find: P in C[U,V,W], such \+ that: P(u,v,w) is zero" }{TEXT -1 84 ", where u,v,w are the polynomial s in C[x,y] given above. When P is in C[U,V,W], then" }}{PARA 0 "" 0 " " {TEXT -1 32 "P(u,v,w) is subs(U=u, V=v, W=w)," }}{PARA 0 "" 0 "" {TEXT -1 45 "which is in C[x,y], and which should be zero." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 240 "Now we want to c ompute both with P in C[U,V,W], and also with u,v,w in C[x,y], so we a re dealing with 5 variables. We can do this by computing in the ring R = C[x,y,U,V,W]. Consider the ideal (F) generated by the set F below. We have that:" }}{PARA 0 "" 0 "" {TEXT -1 62 " u, v, and w are equiv alent to U, V, and W modulo (F), hence:" }}{PARA 0 "" 0 "" {TEXT -1 441 "P(U,V,W) is equivalent to P(u,v,w) modulo (F) for every P in C[U, V,W]. Since we want P(u,v,w) to be equal to 0, we want P(U,V,W) to be \+ equivalent with 0 modulo (F), in other words, P must be in the ideal ( F) in R. Furthermore P is in C[U,V,W] which is a subring of R. So P is in the ideal I_UVW of C[U,V,W] which is defined as I_UVW = the inters ection of the ring C[U,V,W] with the ideal (F), which is a subset of a larger ring C[x,y,U,V,W]." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "F:=\{U-u,V-v,W-w\};" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"FG<%,&% \"WG\"\"\"*&%\"xGF(%\"yGF(!\"\",(%\"UGF(*$)F*\"\"#\"\"\"F,*$)F+\"\"$F2 F,,(%\"VGF(*$)F*F5F2F,*$)F+F1F2F," }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "with(Groebner):" }{TEXT -1 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 132 "Now we choose an elimination ordering, in such a wa y that x and y are > than any monomial in U,V,W. Then compute the Groe bner basis." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 203 "Note that we may also take the ordering: plex(x,y,U,V,W), beca use under this ordering we also have that x,y are > anything in [U,V,W ]. However, the elimination ordering lexdeg tends to be more efficient ." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 55 "ordering:=lexdeg([x,y] ,[U,V,W]); G:=gbasis(F,ordering);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#> %)orderingG-%'lexdegG6$7$%\"xG%\"yG7%%\"UG%\"VG%\"WG" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%\"GG77,D*$)%\"WG\"\"'\"\"\"!#5*(%\"UG\"\"\"%\"VGF/ )F)\"\"$F+!\"$*()F)\"\"#F+F0F+F.F+F6*$)F)\"\"%F+!\"\"*(F.F+F0F+F8F+F3* &)F.F6F+)F0F6F+F:*$)F)\"\"(F+\"#5*(F.F+)F)\"\"&F+F0F+FA*$)F.FEF+F/*$)F 0FEF+F/*$FDF+FE*(F1F+F=F+F>F+F2*(F(F+F0F+F.F+F3*(F5F+F>F+F=F+!\"#*&)F0 F2F+)F.F2F+F:*$)F)\"\")F+!\"&*$)F)\"\"*F+F/,0*(F0F+%\"xGF/F.F+F:*$F>F+ F/*&FenF+F1F+F/*(F)F/%\"yGF/F.F+F/*&FenF+F5F+FN*&FinF+F.F+F:*&FenF+F)F +F/,0*&FenF+F=F+F/*&F.F+F0F+F:*&FinF+F>F+F/F7F/*(F)F+F.F+F0F+F:*$F1F+F N*$F5F+F/,0*(F.F+FinF+F0F+F:*$F=F+F/*&FinF+F1F+F/*(F)F+FenF+F0F+F/*&Fi nF+F5F+FN*&FenF+F0F+F:*&FinF+F)F+F/,6*(F=F+FinF+F0F+F/*&FDF+FenF+F/**F 5F+F0F+FenF+F.F+F:*&FenF+F8F+F3FgnF2FZF/FjnF:*&F5F+F>F+F/*$FQF+F:*&F>F +F)F+F:,6F-F6FF+FenF+F1F+F/*(F>F+FenF+F5F+FN*(F>F+F enF+F)F+F/*(F)F+FQF+FenF+F:*&FDF+F.F+F:*(F5F+F=F+F0F+F/*&F8F+F.F+F2*&F 1F+F.F+F3*&FenF+FQF+F/*&F=F+F0F+F:*&F5F+F.F+F/,@FaoF:F'!\"%FboF/F-F2F7 FgqFfpF/F;FN*(FQF+F0F+FenF+F:F?F/*(F=F+FenF+F1F+F/*(F=F+FenF+F5F+FN*(F =F+FenF+F)F+F/*(F)F+F=F+F>F+F/*(F)F+FPF+FenF+F:FJF*,@*&F5F+FQF+F/*(FPF +F.F+F)F+F/*&F>F+F1F+F:*&F>F+F8F+F2*&FGF+FenF+F/*&FQF+F8F+F/*&F=F+FjpF +F/*&F(F+F>F+F/*&FIF+FenF+F:*()F.F9F+F)F+F0F+F:*(F.F+F5F+FPF+F/*&F>F+F DF+F3*&F1F+FQF+FN*&F0F+FirF+F:*(FPF+F1F+F.F+FN,@*(F=F+F>F+FenF+F/*&FPF +F.F+F:**F.F+F0F+FenF+F1F+FNF_pF2*&F(F+FenF+F/F^pFgqF`pF*FgnFgqFarF/*& F)F+FQF+F:FapFNFZF:FjnF/FbpF/FcpF/,<*&FirF+FenF+F:*&F=F+F8F+F:*(FQF+F) F+F0F+F/*&F1F+F=F+F6*&F=F+F5F+F:*(F0F+FDF+FenF+F/**F5F+F>F+FenF+F.F+F: *(F0F+FenF+F8F+F3*(F0F+FenF+F1F+F2*(F>F+FenF+F.F+F/*(F0F+FenF+F5F+F:*& F5F+FPF+F/*&FPF+F)F+F:,@*(F.F+FDF+FenF+F/**F5F+F0F+FenF+F=F+F:*(F.F+Fe nF+F8F+F3*(F.F+FenF+F1F+F2*(F=F+F0F+FenF+F/*(F.F+FenF+F5F+F:*(F5F+F>F+ F.F+F6*$FirF+F:*(F>F+F1F+F.F+FN*&F=F+FPF+F/*&F(F+F0F+F/*&F0F+FDF+F3*&F 0F+F8F+F2*&F0F+F1F+F:*&FjpF+FenF+F:,**&)FinF6F+F)F+F/*&FenF+F.F+F:F0F/ *$FeuF+F:,*FjnF:*&FeuF+F0F+F/F[oF:F\\oF/,,*&F.F+FeuF+F/*&F0F+)FenF6F+F /FboF/F_oF:FcoF:,&F)F:*&FenF+FinF+F/,**&F)F+F]vF+F/*&FinF+F0F+F:F.F/*$ F]vF+F:,*FioF:*&F]vF+F.F+F/FjoF:F[pF/,0FitF/*&FinF+F=F+F/*(F)F+F.F+Fen F+F:*&F>F+F]vF+F/FauF/*&F>F+F.F+F:*&F0F+F5F+F:,(F.F:FcvF/*$)FinF2F+F/, (F0F:*$)FenF2F+F/FguF/" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 992 "Let H \+ be the list of all polynomials in the list G, that do not contain x or y (that have degree 0 in \{x,y\}). It is clear that (H) will be conta ined in the ideal I_UVW, but in fact (H) equals I_UVW. The reason is a s follows: Suppose Q in I_UVW, so Q in C[U,V,W] and Q in (F). Then Q c an be reduced to 0 by G because G is a Groebner basis. However, Q only has monomials in U,V,W. Hence Q can only be reduced by polynomials g \+ in which the leading power product is in [U,V,W]. Now the ordering wa s chosen in such a way that every monomial in which x or y occurs is b igger than any monomial in [U,V,W], so if the leading term of g only h as the variables U,V,W then g must be in C[U,V,W].\nSo the conclusion \+ is that if Q in I_UVW, so Q can be reduced to 0 by G and Q in C[U,V,W] , then Q can also be reduced to 0 by those elements in G that are in C [U,V,W], i.e. Q can be reduced to 0 by the set H. Hence (H)=I_UVW, and in fact H is a Groebner basis for I_UVW with the same ordering as we \+ had on R." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "H:=remove(has, G,\{x,y\});" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%\"HG7#,D*$)%\"WG\"\"' \"\"\"!#5*(%\"UG\"\"\"%\"VGF/)F)\"\"$F+!\"$*()F)\"\"#F+F0F+F.F+F6*$)F) \"\"%F+!\"\"*(F.F+F0F+F8F+F3*&)F.F6F+)F0F6F+F:*$)F)\"\"(F+\"#5*(F.F+)F )\"\"&F+F0F+FA*$)F.FEF+F/*$)F0FEF+F/*$FDF+FE*(F1F+F=F+F>F+F2*(F(F+F0F+ F.F+F3*(F5F+F>F+F=F+!\"#*&)F0F2F+)F.F2F+F:*$)F)\"\")F+!\"&*$)F)\"\"*F+ F/" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "nops(H);" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "P:=factor(H[1]);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%\"PG,D*$)% \"WG\"\"'\"\"\"!#5*(%\"UG\"\"\"%\"VGF.)F(\"\"$F*!\"$*()F(\"\"#F*F/F*F- F*F5*$)F(\"\"%F*!\"\"*(F-F*F/F*F7F*F2*&)F-F5F*)F/F5F*F9*$)F(\"\"(F*\"# 5*(F-F*)F(\"\"&F*F/F*F@*$)F-FDF*F.*$)F/FDF*F.*$FCF*FD*(F0F*F " 0 "" {MPLTEXT 1 0 20 "subs(U=u,V=v ,W=w,P);" }{TEXT -1 0 "" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#,D*&)%\"xG \"\"'\"\"\")%\"yGF'F(!#5**,&*$)F&\"\"#F(\"\"\"*$)F*\"\"$F(F1F1,&*$)F&F 4F(F1*$)F*F0F(F1F1F7F(F3F(!\"$**F/F(F9F(F5F(F-F(F0*&)F&\"\"%F()F*F>F(! \"\"**F-F(F5F(F=F(F?F(F:*&)F-F0F()F5F0F(F@*&)F&\"\"(F()F*FGF(\"#5**F-F ()F&\"\"&F()F*FLF(F5F(FG*$)F-FLF(F1*$)F5FLF(F1*&FKF(FMF(FL**F7F(F3F(FC F(FDF(F4**F%F(F)F(F5F(F-F(F:**F/F(F9F(FDF(FCF(!\"#*&)F5F4F()F-F4F(F@*& )F&\"\")F()F*FfnF(!\"&*&)F&\"\"*F()F*F[oF(F1" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "expand(%);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\" \"!" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 29 " Let's look at some exampl es:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 71 "normalf(x,G,ordering ); # not in C[u,v,w] because not all x,y disappear:" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#%\"xG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 73 "n ormalf(x^2,G,ordering); # not in C[u,v,w] because not all x,y disappea r:" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#*$)%\"xG\"\"#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 69 "normalf(x^3+y^2,G,ordering); # in C [u,v,w] because all x,y disappear:" }}{PARA 11 "" 1 "" {XPPMATH 20 "6# %\"VG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "expand(u^2*v+w^3); # in C[u,v,w]" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,0*$)%\"xG\"\"(\"\" \"\"\"\"*&)F&\"\"%F()%\"yG\"\"#F(F)*&)F&\"\"&F()F.\"\"$F(F/*&)F&F/F()F .F2F(F/*&)F&F4F()F.\"\"'F(F)*$)F.\"\")F(F)*&F9F(F3F(F)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 54 "normalf(%,G,ordering); # hence all \+ x,y must disappear:" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,&*$)%\"WG\"\"$ \"\"\"\"\"\"*&)%\"UG\"\"#F(%\"VGF)F)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "normalf(x^5+y^5,G,ordering);" }}{PARA 0 "" 0 "" {TEXT -1 133 "All x,y disappear, so x^5+y^5 is an element of C[u,v,w]. If we substitute U=u, V=v, W=w in the following, we would get x^5+y^5 again." }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,(*$)%\"WG\"\"$\"\"\"!\"\"* &%\"UG\"\"\"%\"VGF,F,*$)F&\"\"#F(F)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "expand(subs(U=u, V=v, W=w, %));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,&*$)%\"xG\"\"&\"\"\"\"\"\"*$)%\"yGF'F(F)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "normalf(x^6+y^6,G,ordering);" } {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 56 "This implies that x^6+y^6 is not an element of C[u,v,w]." }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,2* &%\"xG\"\"\")%\"WG\"\"#\"\"\"!\"#*$)%\"VGF)F*F&*&%\"yGF&%\"UGF&!\"\"*& F%F*F(F&F&*$)F1F)F*F&*&F0F*F'F*F+*&F%F*F.F&F2*&F0F*F(F*F&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 56 "Testing if a polynomial g is an element of C[f1,f2..,fk]" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 24 "Consider \+ the polynomials" }}{PARA 0 "" 0 "" {TEXT -1 10 "f1 = x^2+y" }}{PARA 0 "" 0 "" {TEXT -1 14 "f2 = x^3 + y^2" }}{PARA 0 "" 0 "" {TEXT -1 8 "f3 \+ = x*y" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 41 " Now R=C[f1,f2,f3] is a subring of C[x,y]." }}{PARA 0 "" 0 "" {TEXT -1 109 "The ring R consists of all polynomials in x,y that can be express ed as a polynomial in f1,f2,f3, for example:" }}{PARA 0 "" 0 "" {TEXT -1 35 "f1^2*f2 +3*f3^4 is an element of R." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 101 "Note that f1, f2, f3 are algeb raically dependent, because C[x,y] only has transcendence degree 2. If :" }}{PARA 0 "" 0 "" {TEXT -1 11 "g = x^2*y^3" }}{PARA 0 "" 0 "" {TEXT -1 40 "how can we find out if g is in R or not?" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 122 "So we have to find ou t the following: does there exist a polynomial G in three variables, s ay G in C[z1,z2,z3], such that:" }}{PARA 0 "" 0 "" {TEXT -1 33 "subs(z 1=f1, z2=f2, z3=f3, G) = g?" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 140 "If yes, then g in R, if no, then g not in R. N otice that: subs(z1=f1, z2=f2, z3=f3, G) is equivalent to G modulo \+ I=(z1-f1, z2-f2, z3-f3)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT -1 114 "So the question reduces to the following: In the \+ ring C[x,y, z1,z2,z3], does there exist a polynomial G such that:" }} {PARA 0 "" 0 "" {TEXT -1 51 "not has(G,\{x,y\}), in other words: G in \+ C[z1,z2,z3]." }}{PARA 0 "" 0 "" {TEXT -1 35 "And: G is equivalent to g modulo I." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 363 "How to find such G, if it exists? Well, we can reduce g modulo I, and we want to do it in such a way that (if it is possible) the va riables x,y completely disappear. So we have to use the lexdeg([x,y], \+ [z1,z2,z3]) ordering, compute a Groebner basis of I, reduce g, and see if the result has an x or y in it. If there's no x,y then g in R, oth erwise g is not in R." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 261 "" 0 "" {TEXT -1 32 "Exercise: find out i f g is in R." }}{PARA 262 "" 0 "" {TEXT -1 48 "Also find out if h=x^6 *y+x^4*y^2+x*y^4 is in R." }}{PARA 263 "" 0 "" {TEXT -1 64 "Furthermor e: determine an algebraic dependence between f1,f2,f3." }}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 72 "Checking if two rings are equal, or if on e ring is a subring of another." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 35 "Let R1 = C[x1^2+x2, x2^2+x1, x1*x2]" }} {PARA 0 "" 0 "" {TEXT -1 49 "and R2 = C[x1^3+x2^3, x2^3+3*x1^4*x2+x1^6 , x1*x2]" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 20 "Are R1 and R2 equal?" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT -1 45 "We split up this question into two questions:" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 25 "1) Is R1 \+ a subring of R2?" }}{PARA 0 "" 0 "" {TEXT -1 25 "2) Is R2 a subring of R1?" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 15 "L et f1:=x1^2+x2" }}{PARA 0 "" 0 "" {TEXT -1 19 " f2:=x2^2+x1" }} {PARA 0 "" 0 "" {TEXT -1 17 " f3:=x1*x2" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 20 " g1:=x1^3+x2^3" }} {PARA 0 "" 0 "" {TEXT -1 30 " g2:=x2^3+3*x1^4*x2+x1^6" }}{PARA 0 "" 0 "" {TEXT -1 16 " g3:=x1*x2" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 103 "So 1) is: are f1,f2,f3 elements of R2, so can f1,f2,f3 be written as polynomial functions in g1,g2,g3?" }}{PARA 0 "" 0 "" {TEXT -1 98 "And 2) is the reverse. We have seen tha t we can answer these questions using the previous section." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 45 "restart; f1:=x1^2+x2; f2:=x2^2+x1; \+ f3:=x1*x2;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#f1G,&*$)%#x1G\"\"#\" \"\"\"\"\"%#x2GF+" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#f2G,&*$)%#x2G \"\"#\"\"\"\"\"\"%#x1GF+" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#f3G*&%# x1G\"\"\"%#x2GF'" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 51 "g1:=x1^ 3+x2^3; g2:= x2^3+3*x1^4*x2+x1^6; g3:=x1*x2;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#g1G,&*$)%#x1G\"\"$\"\"\"\"\"\"*$)%#x2GF)F*F+" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%#g2G,(*$)%#x2G\"\"$\"\"\"\"\"\"*&)%# x1G\"\"%F*F(F+F)*$)F.\"\"'F*F+" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#g 3G*&%#x1G\"\"\"%#x2GF'" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 135 " ideal_for_ring_R2 := \{ G1-g1, G2-g2, G3-g3 \}; # so the variables G1, G2,G3 are equivalent to the polynomials g1,g2,g3 modulo this ideal." } }{PARA 11 "" 1 "" {XPPMATH 20 "6#>%2ideal_for_ring_R2G<%,*%#G2G\"\"\"* $)%#x2G\"\"$\"\"\"!\"\"*&)%#x1G\"\"%F-F+F(!\"$*$)F1\"\"'F-F.,&%#G3GF(* &F1F(F+F-F.,(%#G1GF(*$)F1F,F-F.F)F." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 49 "with(Groebner): ord:=lexdeg([x1,x2],[G1,G2,G3]);" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%$ordG-%'lexdegG6$7$%#x1G%#x2G7%%#G1G %#G2G%#G3G" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 38 "GB_R2:=gbasis (ideal_for_ring_R2, ord):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 36 "map(reduce, [f1,f2,f3], GB_R2, ord);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7%,&*$)%#x1G\"\"#\"\"\"\"\"\"%#x2GF*,&*$)F+F(F)F*F'F*%#G3G" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 58 "So R1 is not a subring of R2, henc e R1 is not equal to R2." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT -1 22 "Is R2 a subring of R1?" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 135 "ideal_for_ring_R1 := \{ F1-f1, F2-f2, F3-f3 \}; # \+ so the variables F1,F2,F3 are equivalent to the polynomials f1,f2,f3 m odulo this ideal." }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%2ideal_for_ring _R1G<%,&%#F3G\"\"\"*&%#x1GF(%#x2GF(!\"\",(%#F1GF(*$)F*\"\"#\"\"\"F,F+F ,,(%#F2GF(*$)F+F1F2F,F*F," }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "ord:=lexdeg([x1,x2],[F1,F2,F3]);" }}{PARA 11 "" 1 "" {XPPMATH 20 " 6#>%$ordG-%'lexdegG6$7$%#x1G%#x2G7%%#F1G%#F2G%#F3G" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 38 "GB_R1:=gbasis(ideal_for_ring_R1, ord):" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 36 "map(reduce, [g1,g2,g3], GB_R 1, ord);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7&,(%#F3G!\"\"*&%#F1G\"\" \"%#F2GF)F)*$)F%\"\"#\"\"\"F&,&F+!\"$*$)F(\"\"$F.F)F%%#x2G" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 111 "So R2 is a subring of R1, and the above \+ list tells you how you can express g1,g2,g3 as polynomials in f1,f2,f3 ." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 29 "subs(F1=f1, F2=f2, F3= f3, %);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7%,(*&%#x1G\"\"\"%#x2GF'!\" \"*&,&*$)F&\"\"#\"\"\"F'F(F'F',&*$)F(F.F/F'F&F'F'F'*&F-F/F2F/F),&F3!\" $*$)F+\"\"$F/F'F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "expand (%);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7%,&*$)%#x1G\"\"$\"\"\"\"\"\"* $)%#x2GF(F)F*,(F+F**&)F'\"\"%F)F-F*F(*$)F'\"\"'F)F**&F'F*F-F)" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "evalb( % = [g1,g2,g3] );" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#%%trueG" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 24 "Is R1 equal to C[x1,x2]?" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "reduce(x1, GB_R1, ord);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%#x1G" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 39 "No, R1 is a proper subring of C[x1,x2]." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 154 "What is the algebraic relation between f1,f2,f3. We k now that a relation must exist, because it's three polynomials in a ri ng with transcendence degree 2." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "remove(has, GB_R1, \{x1,x2\});" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7#,6*$)%#F1G\"\"$\"\"\"!\"\"*&F'\"\"\"%#F2GF,F,*$)F-F(F)F**&)F' \"\"#F))F-F2F)F,*(F-F)F'F))%#F3GF2F)!\"#*$)F6\"\"%F)F,*$)F6F(F)!\"$*$F 5F)F(*(F'F)F-F)F6F,F,F6F*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "nops(%);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "P:=%%[1];" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"PG,6*$)%#F1G\"\"$\"\"\"!\"\"*&F(\"\"\"%#F2GF-F-*$)F.F)F*F+*&)F( \"\"#F*)F.F3F*F-*(F.F*F(F*)%#F3GF3F*!\"#*$)F7\"\"%F*F-*$)F7F)F*!\"$*$F 6F*F)*(F(F*F.F*F7F-F-F7F+" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 29 "subs(F1=f1, F2=f2, F3=f3, %);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#, 6*$),&*$)%#x1G\"\"#\"\"\"\"\"\"%#x2GF,\"\"$F+!\"\"*&F&F,,&*$)F-F*F+F,F )F,F,F,*$)F1F.F+F/*&)F&F*F+)F1F*F+F,**F1F+F&F+F(F+F3F+!\"#*&)F)\"\"%F+ )F-F=F+F,*&)F)F.F+)F-F.F+!\"$*&F(F+F3F+F.**F&F+F1F+F)F,F-F,F,*&F)F+F-F +F/" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "expand(%);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"!" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "factor(P);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,6*$)%#F1G\"\"$ \"\"\"!\"\"*&F&\"\"\"%#F2GF+F+*$)F,F'F(F)*&)F&\"\"#F()F,F1F(F+*(F,F(F& F()%#F3GF1F(!\"#*$)F5\"\"%F(F+*$)F5F'F(!\"$*$F4F(F'*(F&F(F,F(F5F+F+F5F )" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{SECT 1 {PARA 3 " " 0 "" {TEXT -1 64 "Checking if R1 is a subring of R2 when there are s ide relations." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 119 "R = C[x,y,z]/(y^5-x^4, z*x-1). Choose the following elem ents of R:\nu1:=x^2; u2:=y^2*z; u3:=y^4*z^3+y^3*z^2; v:=y^4*z^3;" }} {PARA 0 "" 0 "" {TEXT -1 39 "\nDefine the following two subrings of R " }}{PARA 0 "" 0 "" {TEXT -1 27 "R1=C[u1,u2,u3] and R2=C[v]." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 33 "Are they equal? Two subquestions:" }}{PARA 0 "" 0 "" {TEXT -1 207 "1) are u1,u2,u3 in C[v]? What does it mean if u1 is in C[v]? Well, then we have to find \+ a polynomial P, such that P(v)=u1. But this is an equality in the ring R, where we are working modulo (y^5-x^4, z*x-1)." }}{PARA 0 "" 0 "" {TEXT -1 111 "Therefore, what we are searching is a polynomial P, such that P(v) is equivalent to u1 modulo (y^5-x^4, z*x-1)." }}{PARA 0 "" 0 "" {TEXT -1 136 "If we use the variable V for the polynomial P, then we search for a P in C[V] such that P is equivalent to v modulo (V-v, y^5-x^4,z*x-1)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 77 "restart; with(Groebner): u1:=x^2; u2:=y^2*z; u 3:=y^4*z^3+y^3*z^2; v:=y^4*z^3;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%# u1G*$)%\"xG\"\"#\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#u2G*&)%\" yG\"\"#\"\"\"%\"zG\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#u3G,&*& )%\"yG\"\"%\"\"\")%\"zG\"\"$F*\"\"\"*&)F(F-F*)F,\"\"#F*F." }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"vG*&)%\"yG\"\"%\"\"\")%\"zG\"\"$F)" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "ideal_R2 := \{V-v,y^5-x^4,z* x-1\};" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%)ideal_R2G<%,&*$)%\"yG\"\" &\"\"\"\"\"\"*$)%\"xG\"\"%F+!\"\",&*&%\"zGF,F/F,F,F1F,,&%\"VGF,*&)F)F0 F+)F4\"\"$F+F1" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "ord:=lexd eg([x,y,z],[V]);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$ordG-%'lexdegG6 $7%%\"xG%\"yG%\"zG7#%\"VG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "GB_R2:=gbasis(ideal_R2,ord):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 36 "map(reduce, [u1,u2,u3], GB_R2, ord);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7%*$)%\"VG\"#5\"\"\"*$)F&\"\"$F(,&*$)F&\"\"#F(\"\" \"F&F0" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 263 "So this means that in \+ the ring R, where the following two equations hold: y^5-x^4=0 and z*x- 1=0, we have that u1=v^10. So that means that in R we have u1-v^10=0. \+ Now R is of the form C[x,y,z]/ideal_R, so u1-v^10 must be in ideal_R = (y^5-x^4, z*x-1). Let's check:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "ideal_R := \{y^5-x^4,z*x-1\};" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%(ideal_RG<$,&*$)%\"yG\"\"&\"\"\"\"\"\"*$)%\"xG\"\"%F+!\"\",&*&%\" zGF,F/F,F,F1F," }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 45 "ord:=tdeg (x,y,z); GB_R:=gbasis(ideal_R, ord);" }}{PARA 11 "" 1 "" {XPPMATH 20 " 6#>%$ordG-%%tdegG6%%\"xG%\"yG%\"zG" }}{PARA 11 "" 1 "" {XPPMATH 20 "6# >%%GB_RG7$,&*&%\"zG\"\"\"%\"xGF)F)!\"\"F),&*$)%\"yG\"\"&\"\"\"F)*$)F* \"\"%F1F+" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "expand(u1-v^10 );" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,&*$)%\"xG\"\"#\"\"\"\"\"\"*&)% \"yG\"#SF()%\"zG\"#IF(!\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "reduce(%, GB_R, ord);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"!" }} }{EXCHG {PARA 0 "" 0 "" {TEXT -1 148 "Now lets check if R2 is a subrin g of R1. That means: is v equivalent to some polynomial in u1,u2,u3 mo dulo the side relations y^5-x^4=0 and z*x-1=0?" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 68 "If we use the variables U 1,U2,U3 for u1,u2,u3, then the question is:" }}{PARA 0 "" 0 "" {TEXT -1 91 "is v equivalent to an element of C[U1,U2,U3] modulo (U1-u1, U2- u2, U3-u3, y^5-x^4, z*x-1)?" }}{PARA 0 "" 0 "" {TEXT -1 158 "If it is , then we can find that element of C[U1,U2,U3] by reducing v modulo th at ideal with an ordering that tries it's best to eliminate the variab les x,y,z." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 48 "ideal_R1 := \+ \{U1-u1, U2-u2, U3-u3,y^5-x^4,z*x-1\};" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%)ideal_R1G<',&*$)%\"yG\"\"&\"\"\"\"\"\"*$)%\"xG\"\"%F+!\"\",&* &%\"zGF,F/F,F,F1F,,(%#U3GF,*&)F)F0F+)F4\"\"$F+F1*&)F)F:F+)F4\"\"#F+F1, &%#U1GF,*$)F/F>F+F1,&%#U2GF,*&)F)F>F+F4F+F1" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "ord:=lexdeg([x,y,z],[U1,U2,U3]);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$ordG-%'lexdegG6$7%%\"xG%\"yG%\"zG7%%#U1G%#U2G%#U3 G" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "GB_R1:=gbasis(ideal_R1 ,ord):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "v;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#*&)%\"yG\"\"%\"\"\")%\"zG\"\"$F'" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "reduce(v,GB_R1,ord);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,6%#U1G\"\"\"%#U2G\"\"#*$)%#U3GF'\"\"\"!\"\"F*F%*&)F&F' F+F)F+F,*$)F&\"\"$F+F'*&F.F+F*F%F%*&F&F%F)F+F,*$F.F+F'*&F&F+F*F+F%" }} }{EXCHG {PARA 0 "" 0 "" {TEXT -1 237 "So R2 is also a subring of R1, t herefore R1 equals R2. This may look strange, but keep in mind here th at they are both subrings of R, and R has transcendence degree only 1 \+ over C because there are 3 variables and 2 independent relations." }}} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 45 "Let R=C[x,y,z]/ (y^4+x^4+x^3*y^2+x^5*y,z*x-1)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 130 "Let N,M be positive integers, and let R_ \{N,M\} be the subring of R generated by the equivalence classes of x, y^M and (z*y)^N in R." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 33 "Consider the following statement:" }}{PARA 0 "" 0 " " {TEXT -1 58 "R_\{N,M\} = R_\{1,1\} if and only if N is odd and igcd( N,M)=1." }}{PARA 0 "" 0 "" {TEXT -1 77 "It's just a statement, I'm not claiming that it is true nor that it is false." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 150 "Test if the statement is true or false for small values for N,M. Note: you have to take N,M re ally small otherwise the computation will take too long." }}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 43 "Calculating the intersection of two ideal s." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 283 22 "Th e sum of two ideals:" }{TEXT -1 81 " Let I1 and I2 be ideals in the ri ng R=C[x1,..,xn]. Then the sum of I1 and I2 is:" }}{PARA 0 "" 0 "" {TEXT -1 44 "I1 + I2 =\{i1+i2 with i1 in I1 and i2 in I2\}." }}{PARA 0 "" 0 "" {TEXT -1 119 "If I1 is generated by the set F1, and I2 is ge nerated by the set F2, then F1 union F2 is a set of generators for I1+ I2." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 1 " " }{TEXT 284 31 "The intersection of two ideals:" }{TEXT -1 136 " Let I \+ be the intersection of I1 and I2. It is prove to see that I is also an ideal. How do we compute a Groebner basis for the ideal I?" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 353 "How can we fin d any nonzero elements of I in the first place? Well, take the set I1* I2 which is the set of all products i1*i2 where i1 in I1, i2 in I2. Th is is an ideal, and it is a subset of both I1 and I2. Is it the inters ection? Not always, take for example I1=(x1) and I2=(x1). So we will n eed to use a trick or something to find the intersection I." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 125 "Let f be an el ement of I. Introduce a new variable t, so we will be working in the r ing R[t]=C[x1,..,xn,t]. The trick now is:" }}{PARA 0 "" 0 "" {TEXT -1 20 "f = t*f + (1-t)*f" }}{PARA 0 "" 0 "" {TEXT -1 139 "How does thi s do any good? Well, t*f is an element of the ideal (t)*I1 of R[t], an d (1-t)*f is an element of the ideal (1-t)*I2. Therefore:" }}{PARA 0 " " 0 "" {TEXT -1 55 "t*f+(1-t)*f is an element of the ideal (t)*I1+(1-t )*I2." }}{PARA 0 "" 0 "" {TEXT -1 160 "If I1 is generated by a set F1, and I2 is generated by a set F2, then t*F1 union (1-t)*F2 is a set of generators for the ideal (t)*I1+(1-t)*I2 in the ring R[t]." }}{PARA 0 "" 0 "" {TEXT -1 80 "Now: f in R[t] is in the ideal I, the intersect ion of I1 and I2, if and only if:" }}{PARA 0 "" 0 "" {TEXT -1 27 "f in R (so: degree(f,t)=0)" }}{PARA 0 "" 0 "" {TEXT -1 25 "and f in (t)*I 1+(1-t)*I2." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 287 "So I is the intersection of (t)*I1+(1-t)*I2 and R, and we can \+ compute a Groebner basis for that by using an elimination ordering tha t eliminates t from (t)*I1+(1-t)*I2. So we have to use lexdeg([t],[x1, ..,xn]), compute a Groebner basis, and throw away everything that has \+ the variable t." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 20 "Time for an example:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "restart; with(Groebner):" }} }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 77 "F1:=\{x1^2+x2*x3,x2^2+x3*x1 \}; # generates I1, not necessarily a Groebner basis" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#F1G<$,&*$)%#x2G\"\"#\"\"\"\"\"\"*&%#x3GF,%#x1GF,F ,,&*$)F/F*F+F,*&F)F,F.F+F," }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 75 "F2:=\{x3^2+x1*x2,x1*x2*x3\}; # generates I2, not necessarily a Gro ebner basis" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#F2G<$,&*$)%#x3G\"\"# \"\"\"\"\"\"*&%#x1GF,%#x2GF,F,*(F.F+F/F+F)F," }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 45 "F:=\{seq(t*i1, i1=F1), seq( (1-t)*i2, i2=F2)\}; " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"FG<&**,&\"\"\"F(%\"tG!\"\"F(%# x1GF(%#x2GF(%#x3GF(*&F)F(,&*$)F,\"\"#\"\"\"F(*&F-F3F+F3F(F(*&F)F3,&*$) F+F2F3F(*&F,F3F-F3F(F(*&F'F3,&*$)F-F2F3F(*&F+F3F,F3F(F(" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 165 "Now F generates the ideal ideal (t)*I1+( 1-t)*I2. This set F doesn't have to be a Groebner basis, even if F1 an d F2 are Groebner basis. And with the ordering we need:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "ord:=lexdeg([t],[x1,x2,x3]);" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%$ordG-%'lexdegG6$7#%\"tG7%%#x1G%#x2G %#x3G" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 74 "with that ordering it is in fact very unlikely that F is a Groebner basis." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "GB:=gbasis(F,ord);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%#GBG7/,&*&)%#x3G\"\"$\"\"\"%#x2G\"\"\"!\"\"*()F,\"\"# F+F)F-%#x1GF-F-,&*&F(F+F2F+F.*()F2F1F+F,F+F)F+F-,(*&F0F+)F)F1F+F-*&F2F +)F,F*F+F-F4F1,&*(F,F+F9F+F2F+F.*&F0F+F6F+F-,(*&F6F+F9F+F-*&)F2F*F+F,F +F-F'F1,&*&F(F+F0F+F-*&)F)\"\"%F+F2F+F-,&*&F(F+F6F+F-*&FFF+F,F+F-,&*&% \"tGF-F0F+F-*(FMF+F)F+F2F+F-,**$F9F+F.*&F2F+F,F+F.*&FMF+F9F+F-*(FMF+F2 F+F,F+F-,&*&FMF+F6F+F-*(FMF+F,F+F)F+F-,&*$F(F+F.*&FMF+F(F+F-,(*&F,F+F9 F+F.*&F2F+F0F+F.*(F,F+FMF+F9F+F1,(*&F9F+F2F+F.*&F6F+F,F+F.*(F2F+FMF+F9 F+F1" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "GB:=remove(has,GB,t );" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%#GBG7),&*&)%#x3G\"\"$\"\"\"%#x 2G\"\"\"!\"\"*()F,\"\"#F+F)F-%#x1GF-F-,&*&F(F+F2F+F.*()F2F1F+F,F+F)F+F -,(*&F0F+)F)F1F+F-*&F2F+)F,F*F+F-F4F1,&*(F,F+F9F+F2F+F.*&F0F+F6F+F-,(* &F6F+F9F+F-*&)F2F*F+F,F+F-F'F1,&*&F(F+F0F+F-*&)F)\"\"%F+F2F+F-,&*&F(F+ F6F+F-*&FFF+F,F+F-" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 88 "Now GB is a Groebner basis for the intersection of I1 and I2, where I1=(F1) and I 2=(F2)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 187 "So everything in GB is in I1 as well as in I2. That, of course, w e can check with Groebner basis, because it is the central problem, th e problem that Groebner basis was designed to solve." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "F1:=gbasis(F1,ord);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#F1G7$,&*$)%#x2G\"\"#\"\"\"\"\"\"*&%#x3GF,%#x1GF,F,,& *$)F/F*F+F,*&F)F,F.F+F," }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 " F2:=gbasis(F2,ord);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#F2G7$,&*$)%# x3G\"\"#\"\"\"\"\"\"*&%#x1GF,%#x2GF,F,*$)F)\"\"$F+" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 64 "seq(reduce(i,F1,ord), i=GB ); # check if I= (GB) is subset of I1:" }}{PARA 11 "" 1 "" {XPPMATH 20 "6)\"\"!F#F#F#F# F#F#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 61 "seq(reduce(i,F2,ord ), i=GB ); # check if I is a subset of I2:" }}{PARA 11 "" 1 "" {XPPMATH 20 "6)\"\"!F#F#F#F#F#F#" }}}{PARA 0 "" 0 "" {TEXT -1 19 "OK, \+ we verified it." }}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 34 "Primary decom position of an ideal." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 213 "A subset V of C^n is called an algebraic set when V i s the solution set of polynomial equations, so when there exists a set F of polynomials such that V=V(F). Recall that V(F) stands for the se t of solutions of F." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 " " {TEXT -1 128 "Recall that if I is the ideal generated by F, I=(F), t hen V(F)=V(I). And if J is the radical ideal of I, then V(F) is also V (J)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 268 11 " Definition:" }{TEXT -1 1 " " }}{PARA 0 "" 0 "" {TEXT -1 129 "An algebr aic set V is called reducible if there exist algebraic sets V1, V2 tha t are not equal to V, and such that V=V1 union V2." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 271 14 "Proposition 1:" }}{PARA 0 "" 0 "" {TEXT -1 77 "Every algebraic set V is a union of finitely ma ny irreducible algebraic sets." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT 269 11 "Definition:" }}{PARA 0 "" 0 "" {TEXT -1 176 "An ideal I in a ring R (we take R=C[x1,..,xn]) is called a prime \+ ideal when R/I has no zero-divisors. An ideal I is called primary when the radical ideal of I is a prime ideal." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 270 14 "Proposition 2:" }}{PARA 0 "" 0 " " {TEXT -1 78 "If I is an ideal then V(I) is irreducible if and only i f I is a primary ideal." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 272 53 "Proposition 3: The primary decomposition of an idea l:" }}{PARA 0 "" 0 "" {TEXT -1 93 "Every ideal I can be written as an \+ intersection of finitely many primary ideals I1, I2,..,Ik." }}{PARA 0 "" 0 "" {TEXT -1 104 "Then the algebraic set V(I) equals the union of \+ the irreducible algebraic sets V(I1), V(I2), ..., V(Ik)." }}{PARA 0 " " 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 273 4 "Note" }{TEXT -1 339 ": there exists an algorithm (which of course uses the Groebner ba sis algorithm) that calculates the primary decomposition of an ideal. \+ So given an ideal I, it computes primary ideals I1,..,Ik such that I i s the intersection of those. And it also calculates the corresponding \+ prime ideals J1,..,Jk, which are the radical ideals of I1,..,Ik." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 258 "So if we have an algebraic set V, which we assume is given by an ideal I for w hich we have a set of generators, then we can split up V into irreduci ble parts, and we can write I as an intersection of primary ideals tha t correspond to those irreducible parts." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 274 8 "Example:" }{TEXT -1 318 " I = (x1* x2^2). The solution set is the union of two lines: x1=0 and x2=0, and \+ those are the irreducible components of V. The primary decomposition o f I is I = intersection of (x1) and (x2^2), these are primary ideals, \+ and the corresponding prime ideals (the radical ideals of these primar y ideals) are: (x1) and (x2)." }}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 37 "The coordinate ring of algebraic set." }}{PARA 0 "" 0 "" {TEXT -1 0 " " }}{PARA 0 "" 0 "" {TEXT -1 64 "Think of x1,x2,..,xn as functions on \+ the set C^n, the so-called " }{TEXT 275 21 "coordinate functions." } {TEXT -1 238 " So when P is the point (2,5,3) then x1 is a function th at takes the value 2 at the point P, x2 takes value 5 at P, and x3 tak es value 3. Given these coordinate functions x1,..,xn we can construct more functions on the set C^n as follows:" }}{PARA 0 "" 0 "" {TEXT -1 76 "R = C[x1,..,xn], the set of all polynomials in x1,..,xn. This i s called the " }{TEXT 276 41 "coordinate ring of the algebraic set C^n ." }}{PARA 0 "" 0 "" {TEXT -1 58 "So we think of every element of R as some function on C^n." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 453 "Let V be an algebraic set, and V is a subset of C^n . Suppose that I = I(V), so I is the set of all elements of R (which w e view as functions on C^n) that vanish on V. Since V is a subset of C ^n, and x1,..,xn are functions from C^n to C, by restricting x1,..,xn \+ to the set V we can think of x1,..,xn as functions from V to C. Of cou rse, we can find more functions P: V -> C, namely every element P in R can be viewed as a polynomial function from V to C." }}{PARA 0 "" 0 " " {TEXT -1 442 "But then what is the set of all polynomial functions f rom V to C? Is it R? Not really, you see, the set R has different elem ents that, when restricted to V, take the same values and so restricte d to V they really are the same functions. In particular, everything i n the ideal I, when restricted to V, is the zero function. Therefore, \+ the set of polynomial functions from V to C can not be identified with R, but it can be identified with R/I." }}{PARA 0 "" 0 "" {TEXT -1 0 " " }}{PARA 0 "" 0 "" {TEXT 277 12 "Definition: " }}{PARA 0 "" 0 "" {TEXT -1 48 "If V is an algebraic set and I = I(V), then the " }{TEXT 278 16 "coordinate ring " }{TEXT -1 23 "of V is defined as R/I." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 279 11 "Definiti on:" }}{PARA 0 "" 0 "" {TEXT -1 98 "The dimension of an algebraic set \+ V is defined as the transcendence degree of its coordinate ring." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 280 6 "Note: " } }{PARA 0 "" 0 "" {TEXT -1 100 "When V is reducible, so V is a union of irreducible sets V1,..,Vk, which are called the irreducible " }{TEXT 281 10 "components" }{TEXT -1 167 " of V, then these components V1,.., Vk can have different dimensions. As you would expect, the dimension o f V in that case equals the highest dimension of the V1,..,Vk." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 282 5 "Note:" }} {PARA 0 "" 0 "" {TEXT -1 132 "When I is an ideal, and J is its radical ideal, then the transcendence degree of R/I is the same as the transc endence degree of R/J." }}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 45 "Calcul ating the dimension of an algebraic set" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 513 "To calculate the dimension of an al gebraic set, we have to determine the transcendence degree of its coor dinate ring. If the set is given by the ideal I, then the coordinate r ing is R/J where J is the radical ideal of I. Now J can be determined, we can even determine much more namely a primary decomposition can be calculated. However, we don't need J to determine the dimension of th e algebraic set, which equals transcendence degree of R/J, because thi s number is also equal to the transcendence degree of R/I." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 49 "How to determine \+ the transcendence degree of R/I?" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 156 "Well, R/I is generated by x1,..,xn. But \+ there are relations between this generators. These relations are given by I. Consider the following subrings of R/I:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 210 "Let x_1 stand for the e quivalence of x1 in the ring R/I. So x_1 = x1+I. And the same for x_2, .. , x_n. So R/I is a ring generated over C by x_1,..,x_n. Now we wil l construct a sequence of subrings as follows:" }}{PARA 0 "" 0 "" {TEXT -1 49 "C subset C[x_1] subset C[x_1,x_2] ... subset R/I." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 320 "In this \+ sequence of subrings, the transcendence degree goes up in every step b y either 0 or 1. If it goes up by 0, then x_\{i+1\} is algebraically d ependent on x_1,..,x_i, which means that there exists an algebraic rel ation between x_1,..,x_\{i+1\} in which x_\{i+1\} appears. We can dete rmine such relations, when they exist." }}{PARA 0 "" 0 "" {TEXT -1 0 " " }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "restart; with(Groebner): " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "ord:=plex(x4,x3,x2,x1); " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$ordG-%%plexG6&%#x4G%#x3G%#x2G%# x1G" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 260 "Note that the pure lexico graphic ordering is also an elimination ordering. Namely: x4 larger th an everything in [x3,x2,x1], just like the ordering lexdeg([x4],[x3,x, x1]). But x3 is also larger than everything in [x2,x1], just like lexd eg([x4,x3],[x2,x1]). Etc." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 50 "F:=\{x1^2+x2*x3, x2^2+x3*x4,x3^2+x4*x1,x4^2+x1*x2\};" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#>%\"FG<&,&*$)%#x1G\"\"#\"\"\"\"\"\"*&%#x2GF,%#x3 GF,F,,&*$)F.F*F+F,*&F/F+%#x4GF,F,,&*$)F/F*F+F,*&F4F+F)F,F,,&*$)F4F*F+F ,*&F)F+F.F+F," }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "F:=gbasis( F,ord);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"FG7+,&*$)%#x1G\"\"&\"\" \"\"\"\"*$)%#x2GF*F+F,,&*&)F)\"\"$F+%#x3GF,F,*$)F/\"\"%F+!\"\",&*$)F) \"\"#F+F,*&F/F,F4F+F,,&*$)F/F3F+F,*&F)F,)F4F " 0 "" {MPLTEXT 1 0 32 "GB_x1:=remove(has,F,\{x2,x3,x4\});" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%&GB_x1G7\"" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 29 "Th ere were two possibilities:" }}{PARA 0 "" 0 "" {TEXT -1 319 "x_1 could be algebraically dependent over C, or independent. If it were depende nt (which meant that there existed a relation involving just x_1), the n the above calculation would have shown that. But it didn't so x_1 is algebraically independent over C, so going from C to C[x_1], the tran scendence degree goes up by 1." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "GB_x1_x2:=remove(has,F,\{x3,x4\});" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%)GB_x1_x2G7#,&*$)%#x1G\"\"&\"\"\"\"\"\"*$)%#x2GF*F+F, " }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 134 "So we see that x_2 is algebr aically dependent over C[x_1]. So going from C[x_1] to C[x_1,x_2] the \+ transcendence degree does not go up." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "GB_x1_x2_x3:=remove(has,F,\{x4\});" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#>%,GB_x1_x2_x3G7',&*$)%#x1G\"\"&\"\"\"\"\"\"*$)%#x2GF *F+F,,&*&)F)\"\"$F+%#x3GF,F,*$)F/\"\"%F+!\"\",&*$)F)\"\"#F+F,*&F/F,F4F +F,,&*$)F/F3F+F,*&F)F,)F4F " 0 "" {MPLTEXT 1 0 41 "map(normalf, GB_x1_x2_x3, GB _x1_x2, ord);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7'\"\"!,&*&)%#x1G\"\" $\"\"\"%#x3G\"\"\"F,*$)%#x2G\"\"%F*!\"\",&*$)F(\"\"#F*F,*&F/F,F+F*F,,& *$)F/F)F*F,*&F(F,)F+F5F*F,,&*&F(F*)F/F5F*F1*$)F+F)F*F," }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 260 "The relations in GB_x1_x2_x3 have a non- zero coefficient for x3, because when we reduce modulo GB_x1_x2 the x3 still doesn't vanish (because note that to have a relation that invol ves x3, the coefficient should not just be zero in R, it should be zer o in R/I)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 110 "So x_3 is dependent over C[x_1,x_2], and when we go to C[x_1,x _2,x_3] the transcendence degree does not go up." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "map(normalf,F,GB_x1_x2_x3,ord);" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#7+\"\"!F$F$F$F$,&*$)%#x3G\"\"#\"\"\"\"\"\"*&%#x4 GF+%#x1GF+F+,&*&F-F*)%#x2GF)F*F+*$)F.\"\"$F*F+,&*$F1F*F+*&F(F+F-F*F+,& *$)F-F)F*F+*&F.F*F2F+F+" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 193 "x_4 i s also dependent over C[x_1,x_2,x_3], so when adding x_4, the transcen dence degree does not go up. Therefore, the transcendence degree of R \+ = C[x1,x2,x3,x4/I = C[x_1,x_2,x_3,x_4] equals 1." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 280 "So the solution set of I , which is V(I), is an algebraic set with dimension 1. Note that Maple has a different method of computing this dimension, based on the Hilb ert series. See the help page for a definition. Such Hilbert series ar e very useful when studying polynomial ideals." }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 33 "hilbertdim(F, tdeg(x1,x2,x3,x4));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 108 "Note that hilbertdim works with any ordering. Therefore we take tdeg \+ because in general that is the fastest." }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 32 "Zero dimensional algebraic sets." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 233 "Let I be an ideal, and let V be its set of solutions, and I(V) is ideal of polynomials that vanish on V. \+ We know that I(V) is the radical ideal of I, and that R/I(V) is the co ordinate ring of the algebraic set V, where R=C[x1,..,xn]." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 112 "When is the dime nsion of V equal to zero? It is zero when the transcendence degree of \+ R/I(V) over C equals zero." }}{PARA 0 "" 0 "" {TEXT -1 177 "Note that \+ when V=V(I), then the transcendence degree of R/I equals the transcend ence degree of R/I(V), even though I(V), which is the radical of I, ca n be a larger ideal than I." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 37 "1) So the dimension of V equals zero:" }}{PARA 0 "" 0 "" {TEXT -1 76 "2) if and only if all elements of R/I(V) are al gebraically dependent over C," }}{PARA 0 "" 0 "" {TEXT -1 110 "3) if a nd only if the equivalence classes of x.i in R/I(V) is algebraically d ependent over C for every i=1..n," }}{PARA 0 "" 0 "" {TEXT -1 113 "4) \+ if and only if for each x.i there exists a polynomial P.i(x.i) in C[x. i] such that P.i(x.i) in the ideal I(V)," }}{PARA 0 "" 0 "" {TEXT -1 210 "5) if and only if for each x.i there exists a polynomial Q.i(x.i) in C[x.i] such that Q.i(x.i) in the ideal I (note that if P.i in I(V) , then P.i to some power is in I, so we can take Q.i as some power of \+ P.i)," }}{PARA 0 "" 0 "" {TEXT -1 572 "6) if and only if R/I is finite dimensional as a C-vector space. Note: the set of monomials x1^e1*... *xn^en where e.i < degree(P.i) spans R/I as a C-vector space because w henever e.i >= degree(P.i) then we can reduce the monomial with P.i, a nd so 5) implies 6). Conversely, if R/I is finite dimensional, then th e equivalence classes of x.i^0,x.i^1,x.i^2,...x.i^N in R/I must be lin early dependent over C whenever N is larger than the dimension of R/I \+ as a C-vector space. Writing down such a linear dependence gives you a polynomial Q.i, so we see that 6) also implies 5)." }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 264 "" 0 "" {TEXT 285 168 "Note: If G is a Gro ebner basis for an ideal I, then the set S of all power products in [x 1,..,xn] that can not be reduced by G forms a basis of R/I as a C-vect or space." }}{PARA 0 "" 0 "" {TEXT -1 434 "Why? Well, as long as a pol ynomial has power products that are not in S, we can reduce them with \+ G. So we should not just reduce the leading monomial (which in Maple i s done by the command reduce), but all monomials (which in Maple is ca lled normalf). The normalf command will result in a polynomial in whic h all power products are in the set S, in other words, normalf reduces any polynomial to a linear combination of elements of S." }}{PARA 0 " " 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 164 "We see that this \+ set S is finite if and only if the transcendence degree of R/I equals \+ zero, if and only if the dimension of V is zero. Such an ideal I is ca lled a " }{TEXT 286 23 "zero-dimensional ideal." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 103 "We also see that if G is a Groebner basis for an ordering ord, then the set S is finite if and only if:" }}{PARA 0 "" 0 "" {TEXT -1 287 "7) for each variable x.i th ere is an element g in G such that the leading power product of g is a power of x.i. Note that this is not the same statement as 5) because \+ g is not necessarily an element of C[x.i], like P.i is. All of the abo ve are also equivalent to the following statement:" }}{PARA 0 "" 0 "" {TEXT -1 518 "8) V is a finite set. It is easy to see that 8) implies \+ 4), if alpha1,..,alpha.n are the x.i-coordinates of the points of V, t hen we can take P.i(x.i) equal to (x.i-alpha1)*...*(x.i-alpha.n), this vanishes on V and hence it is in I(V). Conversely, 4) implies 8), be cause when P.i(x.i) is in I(V), then the x.i-coordinates of all elemen ts of V are roots of P.i(x.i), so these points take at most degree(P.i ) different x.i-coordinates. So the number of points in V is bounded b y degree(P.1)*degree(P.2)*...*degree(P.n)." }}{PARA 0 "" 0 "" {TEXT -1 463 "Note that in fact the number of elements of V equals the dimen sion (as C-vector space) of R/I(V), because if P1,..,Pk are the points in V, then for each i we can construct a polynomial function that tak es value 1 on P.i, and value 0 on the other points of V, and it is not hard to see that this is a basis as vector space of R/I(V). The dimen sion of the vector space R/I is in general larger, but is always finit e if and only if the dimension of R/I(V) is finite." }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 236 "So we have 8 different statements, all of which are equivalent. The easiest way to check if \+ they hold is by checking condition 7), because we can use any ordering with that condition, and so we can take a \"fast\" ordering (usually \+ tdeg)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 66 "Checking if an ideal is zero-dimensional ideal is done as follows:" } }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 48 "restart; with(Groebner): or d:=tdeg(x1,x2,x3,x4);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$ordG-%%tde gG6&%#x1G%#x2G%#x3G%#x4G" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 69 "F:=\{x1^2+x2*x3,x2^2+x3*x4,x3^2+x4*x1,x4^2+x1*x2,x1^1+x2^2+x3^3+x4^4 \};" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"FG<',*%#x1G\"\"\"*$)%#x2G\" \"#\"\"\"F(*$)%#x3G\"\"$F-F(*$)%#x4G\"\"%F-F(,&*$)F'F,F-F(*&F+F(F0F(F( ,&F)F(*&F0F-F4F(F(,&*$)F0F,F-F(*&F4F-F'F(F(,&*$)F4F,F-F(*&F'F-F+F-F(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "G:=gbasis(F,ord);" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"GG7(,&*$)%#x3G\"\"#\"\"\"\"\"\"*&% #x4GF,%#x1GF,F,,&*$)%#x2GF*F+F,*&F)F,F.F+F,,&*$)F.F*F+F,*&F/F+F3F,F,,& *$)F/F*F+F,*&F3F+F)F+F,,&*(F/F+F)F+F.F+F,*&F3F+F7F+!\"\",**$)F.\"\"%F+ F,F?F@F4F@F/F," }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "v:=[seq(l eadmon(i,ord)[2],i=G)];" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"vG7(*$) %#x3G\"\"#\"\"\"*$)%#x2GF)F**&%#x1G\"\"\"F-F0*$)F/F)F**(F/F*F(F0%#x4GF 0*$)F4\"\"%F*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "v:=remove( type,v,`*`);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"vG7&*$)%#x3G\"\"# \"\"\"*$)%#x2GF)F**$)%#x1GF)F**$)%#x4G\"\"%F*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "map(i->op(1,i),v);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7&%#x3G%#x2G%#x1G%#x4G" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 138 " So this set F corresponds to a zero-dimensional ideal, hence V(F) is a zero-dimensional algebraic set, in other words: it is a finite set." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "hilbertdim(F,ord);" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"!" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "ord_lex:=plex(x1,x2,x3,x4);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%(ord_lexG-%%plexG6&%#x1G%#x2G%#x3G%#x4G" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 44 "gbasis(F,ord_lex); # this will take a while." }}{PARA 7 "" 1 "" {TEXT -1 32 "Warning, computation interru pted" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 331 "The easiest way to solve a zero-dimensional ideal is by using a pure lexicographic ordering. B ecause then we will find a polynomial consisting of only the variable \+ x4. Such polynomial must be in the ideal because condition 5) for zero -dimensional ideals. But with the ordering we picked, it must then als o be in the Groebner basis." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 342 "By calculating a root of that polynomial, and \+ plugging in x4=that root in the Groebner basis, we only have the varia bles x1,x2,x3 remaining. But then again, because of the ordering, we w ill find a polynomial consisting only of the variable x3. We can conti nue this way, and find a solution of the ideal. We can find all soluti ons in this way." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 309 "But we may wonder now, is there no faster way to find a \+ polynomial P4(x4) in C[x4] in the ideal? By faster we mean: using the \+ faster ordering tdeg instead of plex? One would think so, because with tdeg we were able to decide if V is zero-dimensional or not. So why n ot compute the solutions with tdeg as well?" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 326 "How to do that? Let's see, why again was it true that there is an element P4(x4) in the ideal? Well, we know that R/I is finite dimensional, and so if we take 1,x4,x4^2,. . and we normalf them,then at some point we should get a linearly depe ndent set. By calculating a linear dependence, we find an element P4(x 4) in the ideal." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 227 "Here we take N=17. How do we know to take N=17? We don't , we simply keep on increasing N until the set of linear equations has a solution. This lead me to N=17. Of course that is something we can \+ implement in a more clever way." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "N:=17; " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"NG\"#<" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 45 "expand(add(c[i]*normalf(x4^i ,G,ord),i=0..N));" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#,hx&%\"cG6#\"\"! \"\"\"*&&F%6#\"\"#F()%#x4GF,\"\"\"F(*&&F%6#\"\"$F()F.F3F/F(*&&F%6#\"\" (F(F4F/F(*&&F%6#\"\")F(%#x1GF(!\"#*&&F%6#\"#5F(F-F/F(*&&F%6#\"#6F(F4F/ F(*&FDF/F-F/F(*&&F%6#\"#7F(F4F/F(*&FIF/F=F/!\"$*&&F%6#\"#8F(F=F/FM*&&F %6#\"#9F(F-F/F>*&FSF/F=F/F(*&&F%6#\"#:F(F4F/F>*&FXF/F-F/\"\"'*&&F%6#\" #;F(F4F/Ffn*&&F%6#\"#*(F@F/Fd oF/F4F/F,*(F@F/FeoF/F4F/F(*(F@F/F-F/F=F/F>*(FDF/F4F/F=F/F>*(FDF/FdoF/F 4F/F_p*(FDF/F-F/F=F/F>*(FDF/F=F/FdoF/F>*(FIF/F4F/F=F/F>*(FIF/F-F/F=F/F (*(FIF/FeoF/F-F/F>*(FIF/FdoF/F-F/F_p*(FIF/F=F/FdoF/F(*(FIF/FeoF/FdoF/F M*(FIF/FdoF/F.F/F3*(FOF/F4F/F=F/F(*(FOF/FeoF/F4F/F>*(FOF/FdoF/F4F/F_p* (FOF/FeoF/F-F/Ffn*(FOF/FdoF/F-F/F8*(FOF/FeoF/FdoF/F,*(FOF/F.F/F=F/FM*( FOF/FdoF/F.F/F3*(FSF/FeoF/F4F/Ffn*(FSF/FdoF/F4F/Fhp*(FSF/F-F/F=F/F>*(F SF/FdoF/F-F/F3*(FSF/F=F/FdoF/F(*(FSF/FeoF/FdoF/F(*(FSF/F.F/F=F/FM*(FSF /FdoF/F.F/F_p*(FXF/F4F/F=F/F>*(FXF/FdoF/F4F/FM*(FXF/F-F/F=F/!#7*(FXF/F eoF/F-F/F(*(FXF/FdoF/F-F/F_p*(FXF/F=F/FdoF/!\"**(FXF/F.F/F=F/F(*(FhnF/ F4F/F=F/F^s*(FhnF/FeoF/F4F/F(*(FhnF/FdoF/F4F/F_p*(FhnF/F-F/F=F/\"\"%*( FhnF/FeoF/F-F/!#:*(FhnF/FdoF/F-F/!\"%*(FhnF/F=F/FdoF/F3*(FhnF/FeoF/Fdo F/!\"'*(F\\oF/F4F/F=F/Fhs*(F\\oF/FeoF/F4F/Fjs*(F\\oF/FdoF/F4F/!\"&*(F \\oF/F-F/F=F/F(*(F\\oF/FeoF/F-F/\"#=*(F\\oF/FdoF/F-F/Fhp*(F\\oF/F=F/Fd oF/F(*(F\\oF/FeoF/FdoF/FM*(F\\oF/FdoF/F.F/Fft**F6F/FeoF/F-F/FdoF/F(**F :F/F4F/FeoF/FdoF/F(**FfpF/FdoF/F.F/FeoF/F_p**F@F/FeoF/F-F/FdoF/F_p**F@ F/FdoF/F.F/FeoF/F,**FDF/F4F/FeoF/FdoF/F_p**FDF/FeoF/F-F/FdoF/Fhs**FDF/ FdoF/F.F/FeoF/F(**FIF/F4F/FeoF/FdoF/Fhs**FOF/FdoF/F.F/FeoF/FM**FSF/Feo F/F-F/FdoF/F\\t**FXF/F4F/FeoF/FdoF/F\\t**FXF/FeoF/F-F/FdoF/Fhp**FXF/Fd oF/F.F/FeoF/F8**FhnF/F4F/FeoF/FdoF/Fhp**FhnF/FeoF/F-F/FdoF/Fhs**F\\oF/ F4F/FeoF/FdoF/Fhs**F\\oF/FeoF/F-F/FdoF/F_p**F\\oF/FdoF/F.F/FeoF/Fct*&& F%6#FhsF(F=F/F_p*&FboF/F-F/F(*(F_vF/FeoF/F-F/F(*(F_vF/FdoF/F.F/F(" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "c[N]-1, coeffs(%,\{x1,x2,x3, x4\});" }}{PARA 12 "" 1 "" {XPPMATH 20 "65,&&%\"cG6#\"#<\"\"\"!\"\"F(, .&F%6#\"#7F(&F%6#\"#:!\"*F$F(&F%6#\"#;\"\"$&F%6#\"#6!\"#&F%6#\"#9F(,0F 6F)F2F)&F%6#\"#5\"\"#&F%6#\"#8F)F.!\"$F$!\"&F:\"\"*,.&F%6#\"\"(F(F.F9F 6F(F2\"\"'&F%6#F5F(F+F(,2F$F(&F%6#FLF)F2\"\"%F+F(F6F9F>F9F.!#7F:F9,2F$ FGF.F)F:F5&F%6#FGF5&F%6#\"\"&F(F2!\"%F+F)FBFK,0F2F(F:FLF>F(FBF9F$!#:FW F(FUF(,0FIF)F$FRF+F9F6F9F.F9FBF(F2FS,.F2FGF+FRF6F)F$FRF.FZ&F%6#\"\")F( &F%6#\"\"!,0FUF(F2!\"'F+FEF:F(FBFAF$FEFinF),.FinFAF+F5FBF5&F%6#FRF(F$ \"#=F:F),,FUF9FBFEF.F(FWF)F:FE,.FBFEF$!#=FboF)F:F(F+FEFinF9&F%6#F(,0F$ F(F>F(F:F9F6F(F.FLFPF(&F%6#FAF(,2FBFLF.F(F$FdoFboF(F2FfnFUF(FinF(F+F9, 0FIF(F$F)F.FGF>F)F2FRF6FRF:FZ,0FPF(F.FKF$FFF6F(F>FAFBFEFUF)" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "solve(\{%\});" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#<4/&%\"cG6#\"#<\"\"\"/&F&6#\"\"!F-/&F&6#F)F-/&F& 6#\"\"%F-/&F&6#\"#9F-/&F&6#\"#;F-/&F&6#\"\"$F-/&F&6#\"#:F-/&F&6#\"#5F- /&F&6#\"\")F-/&F&6#\"#6F-/&F&6#\"\"#!\"\"/&F&6#\"\"'F-/&F&6#\"\"(F)/&F &6#\"#8!\"&/&F&6#\"\"*FH/&F&6#\"\"&F\\o/&F&6#\"#7FU" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 34 "P4:=subs(%,add(c[i]*x4^i,i=0..N));" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%#P4G,0*$)%#x4G\"\"#\"\"\"!\"\"*$)F( \"\"&F*!\"&*$)F(\"\"(F*\"\"\"*$)F(\"\"*F*\"#5*$)F(\"#7F*F+*$)F(\"#8F*F /*$)F(\"# " 0 "" {MPLTEXT 1 0 18 "normalf(P 4,G,ord);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"!" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 173 "So P4 is in the ideal. Since N=17 is the smalles t N for which we find a solution, we can conclude that the ideal I int ersected with C[x4] is generated by this polynomial P4." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "factor(P4);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#**)%#x4G\"\"#\"\"\",&F%\"\"\"!\"\"F)F),&*$F$F'F)F)F)F), 4*$)F%\"#7F'F)*$)F%\"#6F'F)*$)F%\"\")F'!\"%*$)F%\"\"(F'!\"&*$)F%\"\"'F 'F**$)F%\"\"%F'F>*$)F%\"\"$F'\"\"&F%F)F)F)F)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "\{solve(%)\};" }}{PARA 11 "" 1 "" {XPPMATH 20 "6 #<'\"\"!\"\"\"%\"IG-%'RootOfG6#,4*$)%#_ZG\"#7\"\"\"F%*$)F-\"#6F/F%*$)F -\"\")F/!\"%*$)F-\"\"(F/!\"&*$)F-\"\"'F/!\"\"*$)F-\"\"%F/F=*$)F-\"\"$F /\"\"&F-F%F%F%,$F&F>" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 173 "We can p lug in each of these values for x4, and then we only have the variable s x1,x2,x3 remaining. We can find the values for those in a similar wa y. For example take x4=1." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "subs(x4=1,F);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#<',&*$)%#x1G\"\"# \"\"\"\"\"\"*&%#x2GF*%#x3GF*F*,&F*F**&F'F*F,F)F*,&*$)F-F(F)F*F'F*,&*$) F,F(F)F*F-F*,*F'F*F4F**$)F-\"\"$F)F*F*F*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "gbasis(%,ord);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7%, &\"\"\"F%%#x3GF%,&%#x2GF%!\"\"F%,&%#x1GF%F%F%" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 199 "so for x4=1 it is easy to determine the values of the remaining variables. In general, however, we should expect that we ne ed to do something similar as what we had to do to find those values f or x4." }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 13 "An assignment" }}{PARA 0 " " 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "resta rt; with(Groebner):" }}}{PARA 0 "" 0 "" {TEXT -1 51 "Let F be a polyno mial map from C^3 to C^5 given by:" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 58 "F:=[x1*x2+x3, x2*x3+x1, x3*x1+x2, x1*x2*x3, x1+2*x2+3 *x3];" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"FG7',&*&%#x1G\"\"\"%#x2GF )F)%#x3GF),&*&F*\"\"\"F+F)F)F(F),&*&F+F.F(F.F)F*F)*(F(F.F*F.F+F.,(F(F) F*\"\"#F+\"\"$" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 37 "Try to answer t he following question:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 15 "Is F a 1-1 map?" }}{PARA 0 "" 0 "" {TEXT -1 28 "If s o, how do you show that?" }}{PARA 0 "" 0 "" {TEXT -1 67 "If not, give \+ to different points P1,P2 in C3 such that F(P1)=F(P2)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 24 "eqn:=F-[y1,y2,y3,y4,y5];" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#>%$eqnG7',(%#y1G!\"\"*&%#x1G\"\"\"%#x2GF+F+%#x3GF+,(% #y2GF(*&F,\"\"\"F-F+F+F*F+,(%#y3GF(*&F-F1F*F1F+F,F+,&%#y4GF(*(F*F1F,F1 F-F1F+,*%#y5GF(F*F+F,\"\"#F-\"\"$" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 41 "ord:=lexdeg([x1,x2,x3],[y1,y2,y3,y4,y5]);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$ordG-%'lexdegG6$7%%#x1G%#x2G%#x3G7'%#y1G% #y2G%#y3G%#y4G%#y5G" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "GB:= gbasis(eqn,ord):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "GB_Y:=r emove(has,GB,[x1,x2,x3]):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 40 "GB_Y:=gbasis(GB_Y,tdeg(y1,y2,y3,y4,y5)):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 38 "hilbertdim(GB_Y,tdeg(y1,y2,y3,y4,y5));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"$" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 91 "So the image is 3-dimensional. This means that it could be 1-1, bu t doesn't have to be 1-1." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "reduce(x1,GB,ord);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%#x1G" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 71 "This means that we are not able to write x1 as a polynomial in y1..,y5." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "reduce(x2,GB,ord);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6 #,0%#y4G!\"$%#x1G\"\"#%#y3G\"\"**&F&\"\"\"%#y5GF+F%*&%#y2GF+F&\"\"\"\" \"$%#y1G\"\"'F,!\"#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "redu ce(x3,GB,ord);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,0*&%#y2G\"\"\"%#x1G F&!\"#*&F'\"\"\"%#y5GF&\"\"#F'!\"$%#y1G!\"%%#y3G!\"'%#y4GF,F+\"\"$" }} }{EXCHG {PARA 0 "" 0 "" {TEXT -1 71 "We see that x2,x3 can be expresse d as polynomials in x1,y1,y2,y3,y4,y5." }}{PARA 0 "" 0 "" {TEXT -1 0 " " }}{PARA 0 "" 0 "" {TEXT -1 95 "But still we do not know at this poin t if F is 1-1 or not. Try to find this out today in class." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 142 "If it's not 1-1, try to add one more coordinate to F (so making it a map from C^3 to C ^6) in such a way that it becomes 1-1. Is that possible?" }}{PARA 0 " " 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 144 "If it is 1-1, the n try to remove one of the entries of F, making it a map from C^3 to C ^5, in such a way that it still is 1-1. Is that possible?" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 52 "Writing \+ an ideal as an intersection of other ideals." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 166 "F:=[-x3^3*x2+x2^2*x3*x1, -x3^3*x1+x1^2*x2*x3,\nx2^2* x3^2+x1*x2^3+2*x3^3*x1, -x2*x3^2*x1+x2^2*x1^2,\nx1^2*x3^2+x1^3*x2+2*x3 ^3*x2, x3^3*x2^2+x3^4*x1, x3^3*x1^2+x3^4*x2]\n;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%\"FG7),&*&)%#x3G\"\"$\"\"\"%#x2G\"\"\"!\"\"*()F,\"\"# F+F)F-%#x1GF-F-,&*&F(F+F2F+F.*()F2F1F+F,F+F)F+F-,(*&F0F+)F)F1F+F-*&F2F +)F,F*F+F-F4F1,&*(F,F+F9F+F2F+F.*&F0F+F6F+F-,(*&F6F+F9F+F-*&)F2F*F+F,F +F-F'F1,&*&F(F+F0F+F-*&)F)\"\"%F+F2F+F-,&*&F(F+F6F+F-*&FFF+F,F+F-" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "with(Groebner);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#75%%fglmG%'gbasisG%'gsolveG%+hilbertdimG%,hilbe rtpolyG%.hilbertseriesG%-inter_reduceG%*is_finiteG%,is_solvableG%*lead coeffG%(leadmonG%)leadtermG%(normalfG%/pretend_gbasisG%'reduceG%&spoly G%*termorderG%*testorderG%)univpolyG" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 151 "The ideal I=(F) is not a primary ideal, which means that V(I) \+ is a reducible algebraic set. How can we write V(I) as a union of irre ducible components?" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "gbas is(F,lexdeg([x1],[x2,x3]));" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#7*,&*&) %#x3G\"\"'\"\"\"%#x2G\"\"\"F+*&)F*\"\"%F))F'\"\"$F)F+,&*&F/F)F*F)!\"\" *()F*\"\"#F)F'F+%#x1GF+F+,(*&F5F))F'F6F)F+*&F7F))F*F0F)F+*&F/F)F7F)F6, &*&F/F)F5F)F+*&)F'F.F)F7F)F+,&F=F3*()F7F6F)F*F)F'F)F+,&*(F*F)F:F)F7F)F 3*&F5F)FDF)F+,&*&F/F)FDF)F+*&FAF)F*F)F+,(*&FDF)F:F)F+*&)F7F0F)F*F)F+F2 F6" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "remove(has,%,x1);" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#7#,&*&)%#x3G\"\"'\"\"\"%#x2G\"\"\"F+*& )F*\"\"%F))F'\"\"$F)F+" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 6 "op (%);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,&*&)%#x3G\"\"'\"\"\"%#x2G\"\" \"F**&)F)\"\"%F()F&\"\"$F(F*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "factors(%);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7$\"\"\"7&7$%#x3G \"\"$7$%#x2GF$7$,&F'F$F*F$F$7$,(*$)F'\"\"#\"\"\"F$*&F*F$F'F$!\"\"*$)F* F1F2F$F$" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "v:=[seq(i[1],i= %[2])];" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"vG7&%#x3G%#x2G,&F&\"\" \"F'F),(*$)F&\"\"#\"\"\"F)*&F'F)F&F)!\"\"*$)F'F-F.F)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 42 "seq(gbasis([op(F),i],tdeg(x1,x2,x3)),i=v) ;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6&7&%#x3G*&%#x1G\"\"\")%#x2G\"\"$\" \"\"*&)F)\"\"#F+)F&F.F+*&)F&F*F+F)F'7%F)*&)F$F*F+F&F+*&F/F+)F$F.F+7&,& F$F'F)F',&F3F'*$)F$\"\"%F+F',&F5F'F:!\"\",&*&F1F+F$F'F'F:F'7(,(*$F6F+F '*&F)F+F$F+F>*$F-F+F',(F3F'F:F>*&F4F+F)F+F',&*(F)F+F6F+F&F+F'F:F>,&F5F 'FGF',(*(F/F+F)F+F$F+F'FGF'F:F>,&F0F'FGF'" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 0 "" }}}}}{MARK "4" 0 }{VIEWOPTS 1 1 0 1 1 1803 }