{VERSION 2 3 "SUN SPARC SOLARIS" "2.3" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 }{CSTYLE "2D Output" 2 20 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 256 "terminal" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE " " -1 257 "" 1 24 0 0 0 0 0 0 0 0 0 0 0 0 0 }{PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "Times" 1 14 0 0 0 0 2 2 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Text Output" -1 2 1 {CSTYLE "" -1 -1 "Co urier" 1 10 0 0 255 1 0 0 0 0 0 1 3 0 0 }1 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Heading 1" 0 3 1 {CSTYLE "" -1 -1 "" 1 18 0 0 0 0 0 1 0 0 0 0 0 0 0 }1 0 0 0 6 6 0 0 0 0 0 0 -1 0 }{PSTYLE "" 2 6 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 2 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "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 "Maple Output" 0 11 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }3 3 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 11 12 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }1 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 3 256 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }3 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 0" -1 257 1 {CSTYLE "" -1 -1 "He lvetica" 1 14 0 0 0 0 2 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 2" -1 258 1 {CSTYLE "" -1 -1 "Courier" 1 14 0 0 0 0 2 2 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }} {SECT 0 {EXCHG {PARA 0 "" 0 "" {TEXT 256 17 "resultant_lcm.mws" } {MPLTEXT 1 0 0 "" }}{PARA 256 "" 0 "" {TEXT 257 115 "Math 262a, Fall 1 999, Glenn Tesler\nLCM, GCD of commutative and noncommutative polynomi als using resultants\n11/11/99" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 104 "restart;\nwith(linalg): # maple linear algebra package\nwith (Ore_algebra): # Chyzak's Ore algebra package" }}{PARA 7 "" 1 "" {TEXT -1 32 "Warning, new definition for norm" }}{PARA 7 "" 1 "" {TEXT -1 33 "Warning, new definition for trace" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 26 "(Misc. routines -- hidden)" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 283 "# vectopol(vector,x):\n# coef vector of poly i n x ----> the polynomial\nvectopol := (vv,x) -> sum('vv[i,1]*x^(i-1)' ,'i'=1..rowdim(vv)):\n\n# subvec(vector,i..j) --> components i..j as \+ col. vec.\nsubvec := proc(vv,r)\n local i;\n matrix(op(2,r)-op (1,r)+1,1, [ vv[i]$i=r ]);\nend:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 875 "# sylv(p,q,x,s,A) \n# variation of Sylvester matri x of the polynomials p,q in x\n# The columns represent\n# x^0*p ,...,x^(dq+s)*p\n# x^0*q,...,x^0*q\n# (dp=degree(p)). The rows \+ represent the coefficient of\n# 1, x, x^2, ..., x^(dp+dq+s-1)\n # A optional. If given, it's the Ore algebra we're in.\n# If omitted, it's ordinary commutative multiplication.\nsylv := proc(p,q,x,s)\n \+ local dp, dq, dpq, S, i, A; \n if nargs>4 then A := args[5] else A := poly_algebra(x) fi;\n dp := degree(p,x); dq := degree(q,x); dpq := dp+dq+s;\n S := matrix( [\n seq(poltolist(skew_product( x^i,p,A),x,dpq),i=0..dq+s),\n seq(poltolist(skew_pro duct(x^i,q,A),x,dpq),i=0..dp+s)]);\n S := transpose(S);\n RETURN (evalm(S))\nend:\n\n# poltolist(p,x,n)\npoltolist := proc(p,x,n)\n \+ local i, ep;\n ep := expand(p);\n [ seq(coeff(ep,x,i),i=0..n) ]\nend:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 563 "# illsylv(p,q, x,s,A): illustrated version of sylvester matrix\nillsylv := proc(p,q,x ,s)\n local S0,dp,dq,dpq,ctitles,rtitles,i,cofx;\n S0 := sylv(ar gs);\n dp := degree(p,x); dq := degree(q,x); dpq := dp+dq+s;\n c titles := [seq(x^i*P,i=0..dq+s),\n seq(x^i*Q,i=0..dp+s) ];\n cofx := cat(`coef. of `,x);\n rtitles := [` `,'illpow(cof x,i)'$'i'=0..dpq];\n augment(transpose(matrix([rtitles])),stack(cti tles,S))\nend:\nillpow := proc(x,i)\n if i=0 or i=1 then x^convert( i,string) else x^i fi\n # if i=0 or i=1 then x^``[i] else x^i fi\ne nd:" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 64 "Compute the LCM of two polynomials by using the Sylvester matri x" }{MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 103 "p \+ := expand(((x-1)*(x-2))^2); degp := degree(p,x);\nq := expand(((x^2-1) *(x-3))^2); degq := degree(q,x);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>% \"pG,,*$%\"xG\"\"%\"\"\"*$F'\"\"$!\"'*$F'\"\"#\"#8F'!#7F(F)" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%%degpG\"\"%" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"qG,0*$%\"xG\"\"'\"\"\"*$F'\"\"&!\"'*$F'\"\"%\"\"(*$F'\"\"$\" #7*$F'\"\"#!#%%degqG \"\"'" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 27 "Ordinary computation fir st:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 53 "lcm(p,q),factor(lcm(p,q)); g cd(p,q),factor(gcd(p,q));" }}{PARA 12 "" 1 "" {XPPMATH 20 "6$,4*$%\"xG \"\")\"\"\"*$F%\"\"(!#5*$F%\"\"'\"#N*$F%\"\"&!#S*$F%\"\"%!#P*$F%\"\"$ \"$5\"*$F%\"\"#!#NF%!#g\"#OF'**,&F%F'!\"\"F'F8,&F%F'!\"#F'F8,&F%F'!\"$ F'F8,&F%F'F'F'F8" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$,(*$%\"xG\"\"#\"\" \"F%!\"#F'F'*$,&F%F'!\"\"F'F&" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 24 " Form a Sylvester matrix." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 187 "s := -1; pcols := 1..(degq+s+1); qcols := (degq+s+2)..(degp+degq+ 2*s+2);\nmaxrow := degp+degq+s+1; pqrows := 1..maxrow;\nS := sylv(p,q, x,s): 'S' = illsylv(p,q,x,s); # show row/column titles" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"sG!\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%& pcolsG;\"\"\"\"\"'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%&qcolsG;\"\"( \"#5" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%'maxrowG\"#5" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%'pqrowsG;\"\"\"\"#5" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/%\"SG-%'MATRIXG6#7-7-%\"~G%\"PG*&%\"xG\"\"\"F+F.*&F-\" \"#F+F.*&F-\"\"$F+F.*&F-\"\"%F+F.*&F-\"\"&F+F.%\"QG*&F-F.F7F.*&F-F0F7F .*&F-F2F7F.7-)%-coef.~of~~~xG%\"0GF4\"\"!F?F?F?F?\"\"*F?F?F?7-)F=%\"1G !#7F4F?F?F?F?!\"'F@F?F?7-*$F=F0\"#8FDF4F?F?F?!#%#S0G-%'MATRIXG 6#7-7.\"\"%\"\"!F+F+F+F+F+\"\"*F+F+F+F+7.!#7F*F+F+F+F+F+!\"'F,F+F+F+7. \"#8F.F*F+F+F+F+!# " 0 "" {MPLTEXT 1 0 22 "Nul _S := nullspace(S);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%&Nul_SG<$-%'V ECTORG6#7,!\"*!#7\"\"#\"\"%!\"\"\"\"!F-!\"%\"\"\"F/-F'6#7,!#O!#dF0\"#= F/F.\"#;F+F/F1" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 380 "Any vector in \+ the nullspace has two parts,\n v = [ a b ]^transpose,\nwhere the f irst deg(p) columns of S &* a\n = - last deg(q) columns \+ of S &* b\n = coefficient vector of a common multiple of p and \+ q.\nBecause we have arranged the columns of S in the order we did, the vector v with the most trailing 0's is the one producing the least de gree common multiple." }}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 51 "(functi on to find the vector with most leading 0's)" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 386 "num0 := proc(v)\n local i;\n i := vectdim(v );\n while i>=1 and evalb(v[i]=0) do i := i-1 od;\n RETURN(vectd im(v)-i+1);\nend:\n\ngetbestv := proc(Nul_S)\n local bestv,bestv0,v ec,vec0;\n bestv := NULL: bestv0 := 0:\n for vec in Nul_S do\n \+ vec0 := num0(vec);\n if vec0>bestv0 then bestv := copy(ve c); bestv0 := vec0; fi;\n od:\n RETURN(evalm(bestv),bestv0);\nen d:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 143 "bestv := getbestv(Nul_S):\nbestv0 := bestv[2]: bes tv := bestv[1]:\nprint(`nullspace vector giving LCM is`,bestv,` with`, bestv0-1,`trailing 0's`);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6'%?nullspa ce~vector~giving~LCM~isG-%'VECTORG6#7,!\"*!#7\"\"#\"\"%!\"\"\"\"!F+!\" %\"\"\"F-%&~withGF/%-trailing~0'sG" }}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 145 "(function to take selected columns of S * same selected compon ents of vector, and then express the resulting vector as the polynomia l it encodes)" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 271 "halfcombo \+ := proc(S,vec,cols,x)\n local rows,eqn,ev_eqn,pol;\n rows := 1..ro wdim(S);\n eqn := submatrix(S,rows,cols) &* subvec(vec,cols);\n ev _eqn := evalm(eqn); pol := vectopol(ev_eqn,x);\n userinfo(1,halfcomb o,print(eqn=evalm(ev_eqn),`--->`));\n RETURN(pol);\nend:" }}}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 51 "Compute the LCM using the first pa rt of the vector:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 64 "infolevel[half combo] := 1;\nlcm_pq := halfcombo(S,bestv,pcols,x);" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#>&%*infolevelG6#%*halfcomboG\"\"\"" }}{PARA 6 "" 1 " " {TEXT -1 10 "halfcombo:" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$/-%#&*G6$ -%'MATRIXG6#7,7(\"\"%\"\"!F-F-F-F-7(!#7F,F-F-F-F-7(\"#8F/F,F-F-F-7(!\" 'F1F/F,F-F-7(\"\"\"F3F1F/F,F-7(F-F5F3F1F/F,7(F-F-F5F3F1F/7(F-F-F-F5F3F 17(F-F-F-F-F5F37(F-F-F-F-F-F5-F(6#7(7#!\"*7#F/7#\"\"#7#F,7#!\"\"7#F--F (6#7,7#!#O7#\"#g7#\"#N7#!$5\"7#\"#P7#\"#S7#!#N7#\"#5FDFF%%--->G" }} {PARA 12 "" 1 "" {XPPMATH 20 "6#>%'lcm_pqG,4!#O\"\"\"%\"xG\"#g*$F(\"\" #\"#N*$F(\"\"$!$5\"*$F(\"\"%\"#P*$F(\"\"&\"#S*$F(\"\"'!#N*$F(\"\"(\"#5 *$F(\"\")!\"\"" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 20 "and the second \+ part:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "halfcombo(S,bestv,qcols,x) ;" }}{PARA 6 "" 1 "" {TEXT -1 10 "halfcombo:" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$/-%#&*G6$-%'MATRIXG6#7,7&\"\"*\"\"!F-F-7&!\"'F,F-F-7&!# G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,4*$%\"xG\"\")\"\"\"*$F%\"\"(!#5*$F%\"\"'\"#N*$F%\"\"&!#S*$F%\" \"%!#P*$F%\"\"$\"$5\"*$F%\"\"#!#NF%!#g\"#OF'" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "factor(\");" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#* *,&%\"xG\"\"\"!\"\"F&\"\"#,&F%F&!\"#F&F(,&F%F&!\"$F&F(,&F%F&F&F&F(" }} }{EXCHG {PARA 0 "" 0 "" {TEXT -1 281 "To compute a GCD, we want a line ar combination a(x)*p(x) + b(x)*q(x) = g(x) <> 0\nwith as many high po wers of x having 0 coefficient as possible.\nSpecifically, deg(p) + d eg(q) = deg(lcm) + deg(gcd)\ngives the required degree of the gcd, an d all higher powers should be annihilated." }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 82 "S_top := submatrix(S, bestv0+1-s..maxrow,\n \+ 1..(degp+degq+2*s+2));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>% &S_topG-%'MATRIXG6#7)7,!\"'\"#8!#7\"\"%\"\"!F.\"#7!# " 0 "" {MPLTEXT 1 0 30 "Nul_S_top := nullspace(S_top);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%*Nul_S_topG <%-%'VECTORG6#7,#!#F\"\"%!\"*#!#:\"\"#!\"\"#\"\"&F,\"\"!F4\"\"\"#!\"&F ,F4-F'6#7,F+F+!#=!\"'F5F5F4F4F1F1-F'6#7,F-!#7!\"(F4F5F4F5F4F1F4" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 378 "Note Nul_S_top contains Nul_S as \+ a subspace, and is one dimension higher.\nAll vectors v in Nul_S_top g ive rise to linear combinations a(x)*p(x) + b(x)*q(x)\nthat annihilate the necessary high degree coefficients of x. If v is in Nul_S as wel l, this linear combination is 0; otherwise it is a nonzero scalar mult iple of the gcd. So we just need one vector in Nul_S_top \\ Nul_S." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 160 "infolevel[halfcombo] :=0 :\nfor vec in Nul_S_top do\n g := halfcombo(S,vec,pcols,x)+halfcombo (S,vec,qcols,x):\n print(evalm(vec),`--->`,expand(g)=factor(g))\nod: " }}{PARA 12 "" 1 "" {XPPMATH 20 "6%-%'VECTORG6#7,!\"*!#7!\"(\"\"!\"\" \"F*F+F*!\"\"F*%%--->G/,(!#FF+%\"xG\"#a*$F1\"\"#F0,$*$,&F1F+F,F+F4F0" }}{PARA 12 "" 1 "" {XPPMATH 20 "6%-%'VECTORG6#7,!#FF'!#=!\"'\"\"\"F*\" \"!F+!\"\"F,%%--->G/,(!$3\"F*%\"xG\"$;#*$F1\"\"#F0,$*$,&F1F*F,F*F4F0" }}{PARA 12 "" 1 "" {XPPMATH 20 "6%-%'VECTORG6#7,#!#F\"\"%!\"*#!#:\"\"# !\"\"#\"\"&F)\"\"!F1\"\"\"#!\"&F)F1%%--->G/,(F(F2%\"xG\"#a*$F8F-F(,$*$ ,&F8F2F.F2F-F(" }}}{EXCHG {PARA 3 "" 0 "" {TEXT -1 86 "Now do the same thing to find the left LCM or right GCD of noncommutative polynomials ." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 69 "A := shift_algebra([Sn,n]); # \+ Chyzak's Sn = our En: Sn f(n) = f(n+1)" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"AG%,Ore_algebraG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 119 "p := skew_product( n*Sn^2,n*Sn-1,A); degp := degree(p,Sn);\nq := skew_product(n*Sn^3+1,n*Sn-1,A); degq := degree(q,Sn);" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#>%\"pG,&*&,&*$%\"nG\"\"#\"\"\"F)F*F+%#SnG\"\"$F+ *&F)F+F,F*!\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%%degpG\"\"$" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"qG,*!\"\"\"\"\"*&%\"nGF'%#SnG\"\"$ F&*&,&*$F)\"\"#F'F)F+F'F*\"\"%F'*&F)F'F*F'F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%%degqG\"\"%" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 23 "F orm a Sylvester matrix" }{MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 193 "s := -1: pcols := 1..(degq+s+1); qcols := (degq+s+ 2)..(degp+degq+2*s+2);\nmaxrow := degp+degq+s+1; pqrows := 1..maxrow; \nS := sylv(p,q,Sn,s,A): 'S' = illsylv(p,q,Sn,s,A); # show row/column \+ titles" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%&pcolsG;\"\"\"\"\"%" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%&qcolsG;\"\"&\"\"(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%'maxrowG\"\"(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#> %'pqrowsG;\"\"\"\"\"(" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#/%\"SG-%'MATR IXG6#7*7*%\"~G%\"PG*&%#SnG\"\"\"F+F.*&F-\"\"#F+F.*&F-\"\"$F+F.%\"QG*&F -F.F3F.*&F-F0F3F.7*)%.coef.~of~~~SnG%\"0G\"\"!F:F:F:!\"\"F:F:7*)F8%\"1 GF:F:F:F:%\"nGF;F:7**$F8F0,$F?F;F:F:F:F:,&F?F.F.F.F;7**$F8F2,&*$F?F0F. F?F0,&F;F.F?F;F:F:FBF:,&F?F.F0F.7**$F8\"\"%F:,(F?FLF2F.FGF.,&!\"#F.F?F ;F:,&FGF.F?F2FHF:7**$F8\"\"&F:F:,(F?\"\"'\"\")F.FGF.,&F?F;!\"$F.F:,(F? FSFLF.FGF.FN7**$F8FUF:F:F:,(FGF.F?FV\"#:F.F:F:,(FGF.F?\"\"(\"#5F." }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "Nul_S := nullspace(S);" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%&Nul_SG<#-%'VECTORG6#7)\"\"\"\"\"!F+ *(%\"nGF*,&F-F*\"\"#F*F*,&F-F*\"\"$F*!\"\"F+F+,$F-F2" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 143 "bestv := getbestv(Nul_S):\nbestv0 := bes tv[2]: bestv := bestv[1]:\nprint(`nullspace vector giving LCM is`,best v,` with`,bestv0-1,`trailing 0's`);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6 '%?nullspace~vector~giving~LCM~isG-%'VECTORG6#7)\"\"\"\"\"!F)*(%\"nGF( ,&F+F(\"\"#F(F(,&F+F(\"\"$F(!\"\"F)F),$F+F0%&~withGF)%-trailing~0'sG" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 51 "Compute the LCM using the first part of the vector:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 65 "infolevel[h alfcombo] := 1;\nlcm_pq := halfcombo(S,bestv,pcols,Sn);" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#>&%*infolevelG6#%*halfcomboG\"\"\"" }}{PARA 6 " " 1 "" {TEXT -1 10 "halfcombo:" }}{PARA 12 "" 1 "" {XPPMATH 20 "6$/-%# &*G6$-%'MATRIXG6#7)7&\"\"!F,F,F,F+7&,$%\"nG!\"\"F,F,F,7&,&*$F/\"\"#\" \"\"F/F4,&F0F5F/F0F,F,7&F,,(F/\"\"%\"\"$F5F3F5,&!\"#F5F/F0F,7&F,F,,(F/ \"\"'\"\")F5F3F5,&F/F0!\"$F57&F,F,F,,(F3F5F/F@\"#:F5-F(6#7&7#F57#F,FJ7 #*(F/F5,&F/F5F4F5F5,&F/F5F:F5F0-F(6#7)FJFJ7#F.7#F2FJ7#**FAF5F/F5FMF5FN F07#**FDF5F/F5FMF5FNF0%%--->G" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%'lc m_pqG,**&%\"nG\"\"\"%#SnG\"\"#!\"\"*&,&*$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'\"\")\"#:F(F(F' F(F3F(F4F+F)\"\"'F(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 134 "# T he expressions get quite messy, clean them up.\ncleanpol := f -> sort( collect(expand(f),Sn,factor),Sn):\n\nlcm_pq := cleanpol(lcm_pq);" }} {PARA 12 "" 1 "" {XPPMATH 20 "6#>%'lcm_pqG,***,&%\"nG\"\"\"\"\"&F)F),& F(F)\"\"#F)F)F(F)%#SnG\"\"'F)*(F(F)F+F)F-F*!\"\"*(F(F)F+F)F-\"\"$F)*&F (F)F-F,F0" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 20 "and the second part: " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 38 "cleanpol(halfcombo(S,bestv,qcol s,Sn));" }}{PARA 6 "" 1 "" {TEXT -1 10 "halfcombo:" }}{PARA 12 "" 1 " " {XPPMATH 20 "6$/-%#&*G6$-%'MATRIXG6#7)7%!\"\"\"\"!F-7%%\"nGF,F-7%F-, &F/\"\"\"F2F2F,7%,$F/F,F-,&F/F2\"\"#F27%,&*$F/F6F2F/\"\"$,&F,F2F/F,F-7 %F-,(F/\"\"&\"\"%F2F9F2,&!\"#F2F/F,7%F-F-,(F9F2F/\"\"(\"#5F2-F(6#7%7#F -FI7#F4-F(6#7)FIFI7#F/7#,$*&F/F2F5F2F,FI7#,$*&F/F2F@F2F,7#,$*&FCF2F/F2 F,%%--->G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,***,&%\"nG\"\"\"\"\"&F'F ',&F&F'\"\"#F'F'F&F'%#SnG\"\"'!\"\"*(F&F'F)F'F+F(F'*(F&F'F)F'F+\"\"$F- *&F&F'F+F*F'" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 106 "Chyzak's LCM com putation by Euclidean algorithm: annihilators(p,q,A) ---> [U,V] s. t. U*p = -V*q = LCM" }{MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 61 "UV := annihilators(p,q,A): cleanpol(skew_product(UV[1 ],p,A));" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#,**,%\"nG\"\"\",&F%F&\"\"& F&F&,&F%F&\"\"$F&F&,&F%F&\"\"#F&F&%#SnG\"\"'F&**F%F&F)F&F+F&F-F(!\"\"* *F%F&F)F&F+F&F-F*F&*(F%F&F)F&F-F,F0" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 77 "It returned (n+3) * our LCM. n+3 is in the ground field Q(n), \+ so that's O.K." }{MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 3 "" 0 "" {TEXT -1 12 "Compute GCD:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 82 "S_top : = submatrix(S, bestv0+1-s..maxrow,\n 1..(degp+degq+2* s+2));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%&S_topG-%'MATRIXG6#7'7),$% \"nG!\"\"\"\"!F-F-F-,&F+\"\"\"F/F/F,7),&*$F+\"\"#F/F+F3,&F,F/F+F,F-F-F *F-,&F+F/F3F/7)F-,(F+\"\"%\"\"$F/F2F/,&!\"#F/F+F,F-,&F2F/F+F9F4F-7)F-F -,(F+\"\"'\"\")F/F2F/,&F+F,!\"$F/F-,(F+\"\"&F8F/F2F/F:7)F-F-F-,(F2F/F+ F@\"#:F/F-F-,(F2F/F+\"\"(\"#5F/" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 65 "These vectors will kill the coefficients of the top powers of Sn: " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "Nul_S_top := nullspace(S_top); " }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%*Nul_S_topG<$-%'VECTORG6#7)\"\"! \"\"\"F*F*,$*&%\"nG!\"\",&F.F+F+F+F+F/F*F*-F'6#7),$*$F.F/F/F*F*,$*&,&F .F+\"\"$F+F/,&F.F+\"\"#F+F+F/F*F*F+" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 212 "infolevel[halfcombo] :=0:\ng0 := 0:\nfor vec in Nul_ S_top do\n g := halfcombo(S,vec,pcols,Sn)+halfcombo(S,vec,qcols,Sn): \n g := cleanpol(g):\n if g<>0 then g0 := g fi:\n print(evalm(ve c),`--->`,cleanpol(g))\nod:" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%-%'VECT ORG6#7)\"\"!\"\"\"F'F',$*&%\"nG!\"\",&F+F(F(F(F(F,F'F'%%--->G,&*&,&F,F (F+F,F(%#SnGF(F(F*F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%-%'VECTORG6#7) ,$*$%\"nG!\"\"F*\"\"!F+,$*&,&F)\"\"\"\"\"$F/F*,&F)F/\"\"#F/F/F*F+F+F/% %--->GF+" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 133 "It's hard to tell fr om the above that it's just a \"scalar\" (independent of Sn, so it's r ational in n) multiple of n*Sn-1. But it is:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "factor(g0);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,$*(,& %\"nG\"\"\"F'F'F',&*&F&F'%#SnGF'F'!\"\"F'F'F&F+F+" }}}{EXCHG {PARA 0 " " 0 "" {TEXT -1 49 "Chyzaak's GCD computation by Euclidean algorithm: " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "skew_gcdex(p,q,Sn,A)[1];" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#,*!\"\"\"\"\"%\"nGF$*&F&\"\"#%#SnGF%F% *&F&F%F)F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "factor(\"); " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#*&,&%\"nG\"\"\"F&F&F&,&*&F%F&%#SnG F&F&!\"\"F&F&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{MARK "15" 0 } {VIEWOPTS 1 1 0 1 1 1803 }