GCD の利用
現在のオリジナルプログラムや RR6 では,分解体の primitive element A の中間体 K(w,a) 上の定義式が Lagrange resolvents の和となることを利用していますが,http://ehito.hatenablog.com/entry/2019/03/02/163023 で述べたように,A の K(w,a) 上の定義式と a の K(w) 上の定義式は,それぞれ A の K 上の定義式と冪根 a の一次の定義式との A に関する GCD と終結式(を因数分解したもの)なので,代数体での計算が高速なら,これに基づく実装の価値があります.
残念ながら maxima の因数分解は逐次代数拡大に対応していませんが,GCD は対応(algebraic モード)しており,例えば
(%i4) tellrat(a2^3+21*a1+14,a1^2+a1+1)$algebraic:on$gcd:subres$ (%i7) gcd(A^12+4*A^10+24*A^8+48*A^6-560*A^4+3136,485968*a2+A^4*(18236*a1-9524)+A^10*(83*a1-563)+655424*a1+A^8*((-739*a1)-2672)+A^6*((-2012*a1)-12700)+A^2*(474768-28560*a1)+390432,A); Evaluation took 0.0020 seconds (0.0020 elapsed) using 255.969 KB. (%o7) A^2*((12*a1+4)*a2^2+28*a2+28)-28*a2^2+((-84*a1)-28)*a2+21*A^4+392 (%i8) algebraic:off$untellrat(a1,a2)$
といった具合に,tellrat の定義式が monic(つまり,扱えるのは代数的整数のみ)という制約さえクリアすれば,...という訳で,次の RR6m を作りました(m は monic の m).
(%i15) fundef(RR6m); (%o15) RR6m(csGG):=block([],[cs1,cs2,cs3]:csGG,kill(w),DA0:DA,Dws:[[DA,A]],DP:aiA:[], for i thru length(cs3) do (push([DA0,A],DP),w[i]:concat(a,2*i-1),a[i]:concat(a,2*i), Dw:rat((w[i]^(pp:cs3[i])-1)/(w[i]-1)),Dwf:factor2list(factor(Dw,DA))[1], if (degDwf:hipow(Dwf,w[i])) = 1 then (w[i]:rhs(solve(Dwf,w[i])[1]), if pp > 2 then printn(concat("PROU_",pp," is a member."))) else (push([Dwf,w[i]],Dws),push([Dwf,w[i]],DP)),tellrat(DA),algebraic:on, T:cs1[i+1],for g0 in cs1[i] while member(g:g0,T) do 0, LRx:makelist(apply("*",makelist(x-assoc(t,GGRS),t,T:map(lambda([u],mul(g,u)),T))), j,1,pp),printn(LRx),algebraic:off,untellrat(A),ai:0, for cnt while ai = 0 do (CNT:cnt,aix:rrem(sum(w[i]^mod(cnt*j,pp)*LRx[j],j,1,pp),append(Dws,DP)), ai:if aix = 0 then 0 else coeff(aix,x,hipow(aix,x)),printn([[cnt],ai])), printn(Dwf), if degDwf = 1 then w[i]:rrem(w[i],DP) else (pop(DP),push([Dwf:poly_normalize(rrem(Dwf,DP),[w[i]]),w[i]],DP)), printn(Dwf),printn([ai,pp,DP]),aipp:rrem(ai^pp,DP)-a[i]^pp,a1n:num(rat(aipp)), na1n:ifactors(abs(poly_content(subst(a[i] = 0,a1n),map(second,DP)))), na1n:apply("*",map(lambda([s],s[1]^floor(s[2]/cs3[i])),na1n)), da1n:ifactors(abs(coeff(a1n,a[i],cs3[i]))), da1n:apply("*",map(lambda([s],s[1]^ceiling(s[2]/cs3[i])),da1n)), printn("na1n/da1n:"),printn(na1n/da1n), a1n:poly_normalize(subst(a[i] = (na1n*a[i])/da1n,a1n),[a[i]]), DP:delete([DA0,A],DP),push([a1n,a[i]],DP),push([a[i]-(da1n*ai)/na1n,a[i]],aiA), DA0:if hipow(ai,A) = 1 then a[i]-(da1n*ai)/na1n else (DPr:reverse(DP),sDPr:map(second,DPr), for j thru (lDPr:length(DPr)) do DPr:subst((vj2:sDPr[j]) = vj2 /mc[j] :coeff(num(rat(fj1:DPr[j][1])),vj2,hipow(fj1,vj2)), DPr),DPm:map("[",fDPr:map(first,DPr),sDPr), [DA0m,aiaim]:subst(makelist((vj2:sDPr[j]) = vj2/mc[j],j,1,lDPr), [DA0,a[i]-(da1n*ai)/na1n]), print([num(rat(DA0m)),num(rat(aiaim)),A,reverse(DPm)]), map(tellrat,fDPr),algebraic:on, gcdA:subst(makelist((vj2:sDPr[j]) = vj2*mc[j],j,1,lDPr), gcd(aiaim,DA0m,A)),algebraic:off,map(untellrat,sDPr), gcdA),printn([3,DA0,DP])),rr2:[solve(DA0,A)[1],DP], append([[DA0,A]],DP))
実行例 for i:1 thru 15 do print([p:PL[i],mp(p),RR6m(cs(nGG(DA)))]) の timer_info() では,[RR6,0.1656*sec,15,2.484*sec,0] の約 3/4 の処理時間になり,反復除算の簡約 rrem の回数も 210 から 112 になっています.
[[total,0.001120116300199891*sec,5503,6.164*sec,0], [mp,0.2176*sec,15,3.264*sec,0],[RR6m,0.1252*sec,15,1.878*sec,0], [nGG,0.0378*sec,15,0.5670000000000001*sec,0], [rrem,0.002366071428571429*sec,112,0.265*sec,0], [inv,6.372934697088908e-5*sec,1271,0.081*sec,0], [mul,1.597938144329897e-5*sec,3880,0.062*sec,0], [CC,6.486486486486487e-4*sec,37,0.024*sec,0], [mnsg,4.594594594594595e-4*sec,37,0.017*sec,0], [isG,1.351351351351351e-4*sec,37,0.005*sec,0], [factor2list,2.702702702702703e-5*sec,37,0.001*sec,0]]
微調整
http://ehito.hatenablog.com/entry/2019/02/24/234939 の実行例の timer_info() を見ると
[[total,0.001663981382026495*sec,5586,9.295*sec,0], [mp,0.214*sec,15,3.21*sec,0], [nGG,0.1895333333333333*sec,15,2.843*sec,0], [RR6,0.167*sec,15,2.505*sec,0], [rrem,0.002457142857142857*sec,210,0.516*sec,0], [mul,2.216494845360825e-5*sec,3880,0.08600000000000001*sec,0], [inv,6.136900078678206e-5*sec,1271,0.078*sec,0], [CC,8.378378378378379e-4*sec,37,0.031*sec,0], [mnsg,4.054054054054054e-4*sec,37,0.015*sec,0], [isG,2.162162162162163e-4*sec,37,0.008*sec,0], [factor2list,5.405405405405407e-5*sec,37,0.002*sec,0], [cs,6.666666666666667e-5*sec,15,0.001*sec,0]]
のように nGG が重く,その原因は例によって bfloat であろう,という訳で,書き換えてみました.
nGG(DA):=block([i], er:sort(map(lambda([s],abs(s[1]-s[2])),listify(map(listify,powerset(setify(map('rhs,allroots(p))),2)))))[1]/10, nRS:allroots(%i*DA), GG2:nRAS:expand(map(lambda([s],subst(s,RA)),nRS)), i:0,for s in nRAS[1] do ( i:i+1,map(lambda([t],j:1,while(j>0) do if not(integerp(t[j])) and abs(t[j]-s)<er then (t[j]:i,j:0) else j:j+1,t),GG2)), RS:rat(map(lambda([s],KK.s),fullmapl(lambda([s],RA[s]),map(lambda([s],firstn(s,length(KK))),GG2)))), GGRS:map("[",GG2,RS), GG2)$
(なお,こうした root separation の評価は計算機代数の古典的なテーマのひとつで,例えば https://core.ac.uk/download/pdf/82808521.pdf )
結果は,...
[[total,0.001227491531467285*sec,5609,6.885*sec,0], [mp,0.2095333333333333*sec,15,3.143*sec,0], [RR6,0.1656*sec,15,2.484*sec,0], [nGG,0.03653333333333333*sec,15,0.548*sec,0], [rrem,0.002447619047619048*sec,210,0.514*sec,0], [inv,7.002360346184106e-5*sec,1271,0.089*sec,0], [mul,1.314432989690722e-5*sec,3880,0.051*sec,0], [CC,8.378378378378379e-4*sec,37,0.031*sec,0], [mnsg,4.054054054054054e-4*sec,37,0.015*sec,0], [isG,2.432432432432433e-4*sec,37,0.009000000000000001*sec,0], [factor2list,2.702702702702703e-5*sec,37,0.001*sec,0]]
実行例
円分多項式の例です.
(%i9) ROU(x,N):=rat(apply("*",makelist((x^(N/s)-1)^moebius(s),s,listify(divisors(N)))))$ Evaluation took 0.0000 seconds (0.0000 elapsed) using 0 bytes. (%i10) for i:3 thru 22 do print([p:ROU(x,i),mp(p),RR6(cs(nGG(DA)))])$ [x^2+x+1,A^2+3,[[a1+A,A],[a1^2+3,a1]]] [x^2+1,A^2+4,[[2*a1+A,A],[a1^2+1,a1]]] [x^4+x^3+x^2+x+1,A^4+A^3+A^2+A+1, [[(a2+a1+1)/4+A,A],[a2^2-2*a1+10,a2],[a1^2-5,a1]]] [x^2-x+1,A^2+3,[[a1+A,A],[a1^2+3,a1]]] [x^6+x^5+x^4+x^3+x^2+x+1,A^6+A^5+A^4+A^3+A^2+A+1, [[A-(a1*(6*a2^2*w2+2*a2^2-7)-14*a2^2-14*a2-7)/42,A],[a1*(3*w2+2)+a2^3+7,a2], [w2^2+w2+1,w2],[a1^2+7,a1]]] [x^4+1,A^4+1,[[(a2+a1)/2+A,A],[a2^2+2,a2],[a1^2-2,a1]]] [x^6+x^3+1,A^6+A^3+1,[[a2/2+A,A],[a2^3-4*a1-4,a2],[a1^2+3,a1]]] [x^4-x^3+x^2-x+1,A^4-A^3+A^2-A+1, [[(a2+a1-1)/4+A,A],[a2^2+2*a1+10,a2],[a1^2-5,a1]]] [x^10+x^9+x^8+x^7+x^6+x^5+x^4+x^3+x^2+x+1, A^10+A^9+A^8+A^7+A^6+A^5+A^4+A^3+A^2+A+1, [[(a1*((58*a2^4+198*a2^3-11*a2^2)*w2^3+((-322*a2^4)-33*a2^3-121*a2^2)*w2^2 +(240*a2^4+132*a2^3+55*a2^2)*w2 -290*a2^4+99*a2^3-110*a2^2+121) +((-1892*a2^4)-374*a2^3-605*a2^2)*w2^3 +((-462*a2^4)-473*a2^3-121*a2^2)*w2^2+((-880*a2^4)+88*a2^3-363*a2^2)*w2 -1650*a2^4-671*a2^3-484*a2^2+242*a2+121) /1210 +A,A],[a1*(40*w2^3+20*w2^2+30*w2+47)-55*w2^3+55*w2^2-55*w2+a2^5+77,a2], [w2^4+w2^3+w2^2+w2+1,w2],[a1^2+11,a1]]] [x^4-x^2+1,A^4-A^2+1,[[(a2+a1)/2+A,A],[a2^2+1,a2],[a1^2-3,a1]]] [x^12+x^11+x^10+x^9+x^8+x^7+x^6+x^5+x^4+x^3+x^2+x+1, A^12+A^11+A^10+A^9+A^8+A^7+A^6+A^5+A^4+A^3+A^2+A+1, [[(a1*(a2*(4*a3^2*w3-25*a3^2)-26*a3^2*w3-52*a3^2+312) +a2*((-26*a3^2*w3)+65*a3^2+312)+286*a3^2*w3+104*a3^2+624*a3+312) /3744 +A,A],[a2*(18*w3+7)+a1*(a2*((-6*w3)-3)-8)+a3^3+52,a3],[w3^2+w3+1,w3], [a2^2+6*a1+26,a2],[a1^2-13,a1]]] [x^6-x^5+x^4-x^3+x^2-x+1,A^6-A^5+A^4-A^3+A^2-A+1, [[A-(a1*(6*a2^2*w2+2*a2^2-7)+14*a2^2-14*a2+7)/42,A],[a1*(3*w2+2)+a2^3-7,a2], [w2^2+w2+1,w2],[a1^2+7,a1]]] [x^8-x^7+x^5-x^4+x^3-x+1,A^8-A^7+A^5-A^4+A^3-A+1, [[(a3+a2+a1-1)/8+A,A],[a3^2+2*a2+a1*((-2*a2)-4)+28,a3],[a2^2-6*a1-30,a2], [a1^2-5,a1]]] [x^8+1,A^8+1,[[(a3+a2)/2+A,A],[a3^2+a1+2,a3],[a2^2+a1-2,a2],[a1^2-2,a1]]] [x^16+x^15+x^14+x^13+x^12+x^11+x^10+x^9+x^8+x^7+x^6+x^5+x^4+x^3+x^2+x+1, A^16+A^15+A^14+A^13+A^12+A^11+A^10+A^9+A^8+A^7+A^6+A^5+A^4+A^3+A^2+A+1, [[(a4+a3+a2+a1+1)/16+A,A],[a4^2-2*a3+a1*(8-2*a3)+a2*((-2*a3)-8)+136,a4], [a3^2+a1*(2*a2+12)-6*a2-68,a3],[a2^2-2*a1-34,a2],[a1^2-17,a1]]] [x^6-x^3+1,A^6-A^3+1,[[a2/2+A,A],[a2^3-4*a1+4,a2],[a1^2+3,a1]]] [x^18+x^17+x^16+x^15+x^14+x^13+x^12+x^11+x^10+x^9+x^8+x^7+x^6+x^5+x^4+x^3+x^2 +x+1, A^18+A^17+A^16+A^15+A^14+A^13+A^12+A^11+A^10+A^9+A^8+A^7+A^6+A^5+A^4+A^3+A^2 +A+1, [[(a1*(w2*(a2*(3672*a3^2*w3+2112*a3^2)+a2^2*(231*a3^2*w3+448*a3^2+22924944)) +a2*(2340*a3^2*w3+1784*a3^2)+a2^2*((-324*a3^2*w3)-293*a3^2+33113808) +15504*a3^2*w3-10944*a3^2+774353664) +w2*(a2^2*(399*a3^2*w3+266*a3^2-145191312) +a2*((-7296*a3^2*w3)-17632*a3^2)) +a2*(4332*a3^2*w3-3496*a3^2+774353664) +a2^2*((-342*a3^2*w3)+1501*a3^2-48397104)-55632*a3^2*w3-41344*a3^2 +20377728*a3+774353664) /13938365952 +A,A], [a1*(w2*(a2*(1481544*w3-493848)+a2^2*((-136458*w3)-227430)) +11852352*w3+a2^2*((-155952*w3)-12996)-493848*a2+7901568) +w2*(a2*(7407720*w3+6420024)+a2^2*(1111158*w3+370386)) +a2*(2963088*w3-493848)+a2^2*((-740772*w3)-493848)+a3^3+75064896,a3], [w3^2+w3+1,w3],[228*w2+a1*(16-36*w2)+a2^3+152,a2],[w2^2+w2+1,w2], [a1^2+19,a1]]] [x^8-x^6+x^4-x^2+1,A^8-A^6+A^4-A^2+1, [[(a3+a2)/4+A,A],[a3^2+2*a1+6,a3],[a2^2+2*a1-10,a2],[a1^2-5,a1]]] [x^12-x^11+x^9-x^8+x^6-x^4+x^3-x+1,A^12-A^11+A^9-A^8+A^6-A^4+A^3-A+1, [[A-(a1*(3*a2*a3^2+8*a3^2-56)+a2*(7*a3^2-56)+28*a3^2-112*a3+56)/672,A], [a3^3-7*a2+a1*(a2-12)+56,a3],[a2^2+2*a1+10,a2],[a1^2-21,a1]]] [x^10-x^9+x^8-x^7+x^6-x^5+x^4-x^3+x^2-x+1, A^10-A^9+A^8-A^7+A^6-A^5+A^4-A^3+A^2-A+1, [[(a1*((58*a2^4-198*a2^3-11*a2^2)*w2^3+((-322*a2^4)+33*a2^3-121*a2^2)*w2^2 +(240*a2^4-132*a2^3+55*a2^2)*w2 -290*a2^4-99*a2^3-110*a2^2+121) +(1892*a2^4-374*a2^3+605*a2^2)*w2^3+(462*a2^4-473*a2^3+121*a2^2)*w2^2 +(880*a2^4+88*a2^3+363*a2^2)*w2+1650*a2^4-671*a2^3+484*a2^2+242*a2-121) /1210 +A,A],[a1*(40*w2^3+20*w2^2+30*w2+47)+55*w2^3-55*w2^2+55*w2+a2^5-77,a2], [w2^4+w2^3+w2^2+w2+1,w2],[a1^2+11,a1]]] Evaluation took 41.3960 seconds (41.4410 elapsed) using 10160.376 MB.
次は 11 次拡大を含むので時間が掛かります.
(%i12) print([p:ROU(x,23),mp(p),RR6(cs(nGG(DA)))])$ [x^22+x^21+x^20+x^19+x^18+x^17+x^16+x^15+x^14+x^13+x^12+x^11+x^10+x^9+x^8+x^7 +x^6+x^5+x^4+x^3+x^2+x+1, A^22+A^21+A^20+A^19+A^18+A^17+A^16+A^15+A^14+A^13+A^12+A^11+A^10+A^9+A^8+A^7 +A^6+A^5+A^4+A^3+A^2+A+1, [[(a1*((22711467475534198*a2^10+847656939034980*a2^9+328864770731640*a2^8 +19604741278064*a2^7-10713350489280*a2^6 +899469127648*a2^5+655331361792*a2^4 +12250319616*a2^3-6160979456*a2^2) *w2^9 +(39210376235165047*a2^10+2041710859169370*a2^9+733881801397984*a2^8 +14975939529168*a2^7-26094666163296*a2^6 +3085175093696*a2^5+1220699341568*a2^4 +77155521792*a2^3-22064903168*a2^2) *w2^8 +(44258439323364695*a2^10+3203058077583282*a2^9+1086461046496968*a2^8 -12416794104704*a2^7-41260490775696*a2^6 +5863155824672*a2^5+1516563404544*a2^4 +174298407168*a2^3-42697020416*a2^2) *w2^7 +(36252932377559731*a2^10+3962979058122594*a2^9+1274661086788456*a2^8 -53876459982320*a2^7-51395783099968*a2^6 +8351433082784*a2^5+1449040253312*a2^4 +272730799872*a2^3-61179958784*a2^2) *w2^6 +(17735547288835748*a2^10+4080204258656724*a2^9+1238729739093416*a2^8 -96239906925832*a2^7-53282659141264*a2^6 +9759997523200*a2^5+1039568725888*a2^4 +341074688256*a2^3-72069131776*a2^2) *w2^5 +((-5414577014723690*a2^10)+3517515506329206*a2^9+990074952435016*a2^8 -126057041160920*a2^7-46322048846112*a2^6 +9641627602944*a2^5+418118078976*a2^4 +357838283520*a2^3-71925853184*a2^2) *w2^4 +((-25847439637650301*a2^10)+2453562504314970*a2^9+607642864832560*a2^8 -133861132247864*a2^7-32723893820416*a2^6 +8033919936032*a2^5-217984361344*a2^4 +317541179520*a2^3-60177008640*a2^2) *w2^3 +((-37075751068922942*a2^10)+1226142813215268*a2^9+212852962075632*a2^8 -117174436025296*a2^7-16805512936224*a2^6 +5447303727776*a2^5-666801436032*a2^4 +233078449536*a2^3-41264234496*a2^2) *w2^2 +((-35534601764595846*a2^10)+224953512486384*a2^9-68951751229648*a2^8 -81294861335224*a2^7-3620882635952*a2^6 +2703003978208*a2^5-785831683712*a2^4 +131314829568*a2^3-20775395840*a2^2) *w2-21713295739522928*a2^10-232134869059746*a2^9-148300269904712*a2^8 -37613918803656*a2^7+2643970591392*a2^6+672332846240*a2^5 -537243326592*a2^4+44380543872*a2^3-5301307904*a2^2+6590815232) +(23127481912300174*a2^10-4266420106368780*a2^9-1138621329910408*a2^8 +187360039390496*a2^7+56494249686592*a2^6 -12676273242976*a2^5-124724014336*a2^4 -485284591104*a2^3+95566820864*a2^2) *w2^9 +(101470356548088363*a2^10-5657737299806442*a2^9-1243802641976576*a2^8 +395808948442240*a2^7+76242423677632*a2^6 -21008077937344*a2^5+1469393600256*a2^4 -861390895104*a2^3+158179565568*a2^2) *w2^8 +(210155314754852863*a2^10-3732218201923602*a2^9-282149613567896*a2^8 +559165668119584*a2^7+52974608932720*a2^6 -22350123734048*a2^5+4276364496128*a2^4 -1009039484160*a2^3+171361196032*a2^2) *w2^7 +(314675650233351123*a2^10+898798478208330*a2^9+1441019713076728*a2^8 +625565597409600*a2^7-5921818285152*a2^6 -16276263112800*a2^5+7405103289984*a2^4 -882237930240*a2^3+128520897024*a2^2) *w2^6 +(381846894974485910*a2^10+6764997665935512*a2^9+3378611252436072*a2^8 +573927223073160*a2^7-81747656536464*a2^6 -4714980758016*a2^5+9862008765952*a2^4 -520316206848*a2^3+42840299008*a2^2) *w2^5 +(390342653382438482*a2^10+12003902568405402*a2^9+4915453381952560*a2^8 +420645366298040*a2^7-150428730646176*a2^6 +8663142278528*a2^5+10867108088832*a2^4 -38327023360*a2^3-56021929472*a2^2) *w2^4 +(337465582190696883*a2^10+14952197895233958*a2^9+5563609584583344*a2^8 +214385938621864*a2^7-190159286564736*a2^6 +19610665087776*a2^5+10101319834240*a2^4 +410385707136*a2^3-138407119872*a2^2) *w2^3 +(240003777890885208*a2^10+14673820711808060*a2^9+5117294845027984*a2^8 +20634845593008*a2^7-188325170689696*a2^6 +24651756486752*a2^5+7807716133504*a2^4 +683976178560*a2^3-177952011264*a2^2) *w2^2 +(128900674716232452*a2^10+11257153806707688*a2^9+3718210938875040*a2^8 -99093307914712*a2^7-145508697393104*a2^6 +22185977861024*a2^5+4714689528704*a2^4 +694829531904*a2^3-161474973184*a2^2) *w2+39430722907678478*a2^10+5786964780828642*a2^9+1810557120845464*a2^8 -106785679762504*a2^7-75303787322272*a2^6+12996173068448*a2^5 +1804128210816*a2^4+439614539904*a2^3-95566820864*a2^2+6590815232*a2 +6590815232) /144997935104 +A,A], [a1*(981871616*w2^9+573213696*w2^8-345849856*w2^7+1610481664*w2^6 +2609913856*w2^5+2784956416*w2^4+3007206400*w2^3 +863858688*w2^2+549716992*w2+958533632) +3252648960*w2^9+13344021504*w2^8+9279959040*w2^7+3458611200*w2^6 +6119798784*w2^5+2020761600*w2^4+3886339072*w2^3+1821276160*w2^2 -6719032320*w2+a2^11-2574940160,a2], [w2^10+w2^9+w2^8+w2^7+w2^6+w2^5+w2^4+w2^3+w2^2+w2+1,w2],[a1^2+23,a1]]] Evaluation took 691.5360 seconds (692.1830 elapsed) using 92077.766 MB.
その後は,...
(%i13) for i:24 thru 28 do print([p:ROU(x,i),mp(p),RR6(cs(nGG(DA)))])$ [x^8-x^4+1,A^8-A^4+1, [[(a3+a2+a1)/4+A,A],[a3^2-2*a1*a2+8,a3],[a2^2-2,a2],[a1^2-6,a1]]] [x^20+x^15+x^10+x^5+1,A^20+A^15+A^10+A^5+1, [[a3/2+A,A],[a3^5-8*a2-8*a1-8,a3],[a2^2-2*a1+10,a2],[a1^2-5,a1]]] [x^12-x^11+x^10-x^9+x^8-x^7+x^6-x^5+x^4-x^3+x^2-x+1, A^12-A^11+A^10-A^9+A^8-A^7+A^6-A^5+A^4-A^3+A^2-A+1, [[A-(a1*(a2*(4*a3^2*w3-25*a3^2)+26*a3^2*w3+52*a3^2-312) +a2*(26*a3^2*w3-65*a3^2-312)+286*a3^2*w3+104*a3^2-624*a3+312) /3744,A],[a1*(a2*(6*w3+3)-8)+a2*(18*w3+7)+a3^3-52,a3],[w3^2+w3+1,w3], [a2^2-6*a1+26,a2],[a1^2-13,a1]]] [x^18+x^9+1,A^18+A^9+1, [[a3/2+A,A],[a3^3-4*a2,a3],[a2^3-4*a1-4,a2],[a1^2+3,a1]]] [x^12-x^10+x^8-x^6+x^4-x^2+1,A^12-A^10+A^8-A^6+A^4-A^2+1, [[(a1*(6*a3^2*w3+2*a3^2+7)+a2*(7-14*a3^2)+14*a3)/42+A,A], [a1*((-3*w3)-2)+a3^3-7*a2,a3],[w3^2+w3+1,w3],[a2^2+1,a2],[a1^2-7,a1]]] Evaluation took 77.5920 seconds (77.6710 elapsed) using 9047.339 MB.
4.添加する元の定義式,および,5.分解体の相対定義式(解説)
現在のオリジナルプログラムでは,すべての Lagrange Resolvent の冪乗,開冪,和を取って,表題の2つを算出しています.
一方,http://ehito.hatenablog.com/entry/20190123/1548255005 で提案した方法は,分解体の(基礎体 K 上の)定義式 P,新たに添加する冪根 ai の(K に分解体の primitive element A を添加した体 K(A) 上の)定義式 Q,そして,既に添加された元の定義式に対する Groebner 基底から,分解体の(拡大体 K(ai) 上の)定義式 R,冪根 ai の(K 上の)定義式 S を同時に得るもの(数学としては,P,Q を最初の2式,R,Sを終端の2式とする代数体上の互除法により,P=Q=0 ⇔ R=S=0 を保ちつつ,primitive element についての次数を下げる(特に S は 0 次)ことに当たります)ですが,maxima の Groebner 基底ルーチンによる実装 RR5 では
(%i2) for i:1 thru 15 do RR5(cs(nGG(mp(PL[i]))))$ PROU_5 is a member. PROU_5 is a member. PROU_3 is a member. PROU_3 is a member. Evaluation took 298.6010 seconds (299.8230 elapsed) using 29739.980 MB.
となり,Groebner 基底の計算に Risa/Asir の関数を用いる RR5a では
(%i3) for i:1 thru 15 do RR5a(cs(nGG(mp(PL[i]))))$ PROU_5 is a member. PROU_5 is a member. PROU_3 is a member. PROU_3 is a member. Evaluation took 7.3480 seconds (10.5720 elapsed) using 3442.276 MB.
となりました. ただ,今回のお話は maxima プロパーを旨とするもの(?)だと思いますので,前回掲載した RR6 での Groebner 基底の利用は無理のない(と思われる)範囲に留めています.
全体の処理の流れは,オリジナルプログラムと同様に,すべての Lagrange Resolvent の和として,5.を得るものですが,各 Resolvent LR[j] (j=1,...,pp) (pp は拡大次数)に冪根 ai を適当な回数(コードでは pp-1 回)乗じて,冪根の変数の冪乗 a[i]^(j-1) と基礎体上の多項式 ai^(pp-j)*LR[j] との積の形に整理しています.これは https://ikumi.que.jp/blog/wp-content/uploads/2018/09/galois-solution.pdf の 12.(4),https://ikumi.que.jp/blog/archives/717 の【2019, 1/21 追記】で間接,直接に指摘されているもので,コード内の
F:sum(a[i]^(j-1)*ai^(pp-j)*LR[j],j,1,pp)
が相対定義式の 0 でない定数倍 ai^(pp-1)*sum(LR[j],j,1,pp) となる訳ですが,この F の係数を冪根 ai の変数 a[i]と既に添加されているの元の変数で表すと,主係数に変数が残るので,有理化,つまり,代数体での逆元の計算が必要となり,Groebner 基底の出座に至ります(笑).例えば
(%i4) poly_reduced_grobner ([(a^2+b)*x^2+x+1,a^3+a+1,b^2+a*b+a^2],[x,b,a]); Evaluation took 0.0020 seconds (0.0020 elapsed) using 159.969 KB. (%o4) [a^3+a+1,b^2+a*b+a^2,(-x^2)+b*x-a^2*x+a*x+b-a^2+a]
といった感じです.
これに先立つもう1つのポイントが ai の検出です.ai は 0 でない Resolvent の主係数であり,いわゆる代数体での 0 判定が必要となり,その際,定義式の既約性が重要(「代入した値が0⇔定義式による整除」が成立)で,例えば,a^2-2 が定める Q(a) に,その上で既約ではない b^2-2 の根 b を添加するといった暴挙に出ると,a+b=0 か否かの判定が出来ません.実際,1の原始 pp 乗根 w[i] の(Q上の)定義式 Dw は,素数 pp が 2 以外ならば高次なので,基礎体上で既約でない可能性があり,因数分解が必要となり,自然なのは逐次拡大体としての各中間体上の分解ですが,処理時間を比較した結果,RR6 では分解体 Q(A) 上の分解 factor(Dw,DA) を利用しています.具体的には,低次の因数に分解されるならば,pp が素数であることから,それらの次数は全て等しく,1次ならば,w[i] は直接 A で表示し,次数が 2 以上ならば,0 でない ai の検出までは Q(A) 係数のまま用い(コード内の /* w[i] with A */ からの部分),ai^pp の簡約からは,分解体の(基礎体上の)定義式と既に添加された元の定義式により基礎体係数に直した形を用いています(コード内の /* w[i] with a[1],w[1],...,a[i-1],w[i-1] */ からの部分).参考として,2次式に分解される例を記しておきます.
(%i6) [p,Dw,DA]; Evaluation took 0.0000 seconds (0.0000 elapsed) using 0 bytes. (%o6) [x^5-5*x^3+5*x+5,w3^4+w3^3+w3^2+w3+1, A^20-50*A^18+1025*A^16-11250*A^14+72500*A^12-268125*A^10+456875*A^8 +137500*A^6-1578125*A^4+1640625*A^2+1378125] (%i7) Dwf:factor2list(factor(Dw,DA))[1]; Evaluation took 0.5380 seconds (0.5410 elapsed) using 91.638 MB. (%o7) 240295101375*w3^2-54652*A^18*w3+2992335*A^16*w3-67936350*A^14*w3 +830924250*A^12*w3-5985718405*A^10*w3 +25902278250*A^8*w3-65067996000*A^6*w3 +83309465625*A^4*w3-24030550000*A^2*w3-202585732125*w3 +240295101375 (%i8) Dwf:poly_normalize(rrem(Dwf,[[(5*a2)/2-(A*(25*a1-75))/2+(A^3*(5*a1-25))/2+A^5,A],[a2^2-462*a1+1050,a2],[a1^2-5,a1]]),[w[3]]); Evaluation took 0.0050 seconds (0.0050 elapsed) using 862.938 KB. (%o8) w3^2-((a1-1)*w3)/2+1
他にも,RR シリーズでは
・remainder と algebraic モード との使い分け(後者の方が高速だが,tellrat は monic しか受け付けず,その為の変数変換はやや大掛かりになるので)
・元の変数に atom を使用(これも後者の方が高速なので)
・poly_reduced_grobner ではなく poly_grobner を利用(余分な式が含まれるが,やはり後者の方が高速なので)
といった工夫を施しています.
4.添加する元の定義式,および,5.分解体の相対定義式
取り敢えず,コードと例を記します.解説はまた後日.
load("grobner")$ factor2list(f0):=block([f:num(f0)],if op(f)="-" then args(-f) elseif op(f)="*" then args(f) else [f])$ rrem(S,T):=block([U:S],map(lambda([s],U:remainder(U,s[1],s[2])),T),U)$ RR6(csGG):=block([],[cs1,cs2,cs3]:csGG,kill(w),DA0:DA,Dws:[[DA,A]],DP:aiA:[], for i:1 thru length(cs3) do (push([DA0,A],DP), a[i]:concat(a,i),w[i]:concat(w,i), /* w[i] with A */ Dw:rat((w[i]^(pp:cs3[i])-1)/(w[i]-1)), Dwf:factor2list(factor(Dw,DA))[1], if (degDwf:hipow(Dwf,w[i]))=1 then (w[i]:rhs(solve(Dwf,w[i])[1]), if pp>2 then printn(concat("PROU_",pp," is a member."))) else (push([Dwf,w[i]],Dws),push([Dwf,w[i]],DP)), /* non-zero aix and ai */ tellrat(DA),algebraic:on, T:cs1[i+1],for g0 in cs1[i] while member(g:g0,T) do 0, LRx:makelist(apply("*",makelist(x-assoc(t,GGRS),t,T:map(lambda([u],mul(g,u)),T))),j,1,pp), printn(LRx), algebraic:off,untellrat(A), ai:0,for cnt:1 while ai=0 do (CNT:cnt,aix:rrem(sum((w[i]^mod(cnt*j,pp)*LRx[j]),j,1,pp),append(Dws,DP)), ai:if aix=0 then 0 else coeff(aix,x,hipow(aix,x)), printn([[cnt],ai])), /* w[i] with a[1],w[1],...,a[i-1],w[i-1] */ if degDwf=1 then w[i]:rrem(w[i],DP) else (pop(DP),push([Dwf:poly_normalize(rrem(Dwf,DP),[w[i]]),w[i]],DP)), /* Lagrange Resolvent */ LR[1]:aix,for cnt:2 thru pp do (LR[cnt]:rrem(sum(w[i]^mod(CNT*cnt*j,pp)*LRx[j],j,1,pp),DP), printn(concat("LR_",cnt)),printn(LR[cnt])), F:rrem(sum(a[i]^(j-1)*ai^(pp-j)*LR[j],j,1,pp),DP), F:subst(x=A,F),printn("F:"),printn(F), /* def. of a[i] */ aipp:rrem(ai^pp,DP)-a[i]^pp, /* reduction for F */ DP:delete([DA0,A],DP),fDP:map(first,DP),sDP:map(second,DP), GR:poly_grobner(append([F,aipp],fDP),append([A,a[i]],sDP)), printn("GR:"),printn(GR), /* monic rather than primitive */ a1n:num(rat(aipp)), na1n:ifactors(abs(poly_content(subst(a[i]=0,a1n),sDP))), na1n:apply("*",map(lambda([s],s[1]^floor(s[2]/cs3[i])),na1n)), da1n:ifactors(abs(coeff(a1n,a[i],cs3[i]))), da1n:apply("*",map(lambda([s],s[1]^ceiling(s[2]/cs3[i])),da1n)), printn(na1n/da1n), a1n:poly_normalize(subst(a[i]=na1n/da1n*a[i],a1n),[a[i]]), push([a1n,a[i]],DP), push([a[i]-da1n/na1n*ai,a[i]],aiA), DA0:sublist(GR,lambda([s],numberp(coeff(s,A,deg:hipow(s,A))) and deg<hipow(DA0,A)))[1], DA0:poly_normalize(subst(a[i]=na1n/da1n*a[i],DA0),[A]), printn([3,DA0,DP]) ), rr2:[solve(DA0,A)[1],DP], append([[DA0,A]],DP))$
実行例.p の各根のリスト RA は長いのでプリントしていません.
(%i24) for i:1 thru 15 do print([p:PL[i],mp(p),RR6(cs(nGG(DA)))])$ [x^2-2,A^2-8,[[2*a1+A,A],[a1^2-2,a1]]] [x^3-3*x-1,A^3-3*A-1,[[a1^2*w1+a1+A,A],[w1+a1^3+1,a1],[w1^2+w1+1,w1]]] [x^4-2,A^8+28*A^4+2500,[[a3+2*a2+A,A],[a3^2-a1,a3],[a2^2+a1,a2],[a1^2-2,a1]]] [x^4+x^2-1,A^8+10*A^6+47*A^4+110*A^2+841, [[(a3+2*a2)/2+A,A],[a3^2-2*a1+2,a3],[a2^2+2*a1+2,a2],[a1^2-5,a1]]] [x^4-2*x^3+2*x^2+2,A^12+4*A^10+24*A^8+48*A^6-560*A^4+3136, [[a3/21+A,A],[(-126*a1^2*w1)+a3^2+42*a2-84*a1^2+294*a1+294,a3], [(42*a1^2+588*a1)*w1+a2^2-168*a1^2+294*a1+1323,a2],[(-21*w1)+a1^3-7,a1], [w1^2+w1+1,w1]]] [x^4+2*x^3+3*x^2+4*x+5, A^24+24*A^23+336*A^22+3344*A^21+25740*A^20+159984*A^19+820856*A^18 +3519504*A^17+12721926*A^16+39075680*A^15+104485896*A^14+257189424*A^13 +603068156*A^12+1264487184*A^11+1484791560*A^10-3707413456*A^9 -23515353279*A^8-53513746296*A^7-7075256024*A^6+299352120960*A^5 +770653544880*A^4+869309952000*A^3+1145273500800*A^2+1451723788800*A +1818528595200, [[(a4+585)/585+A,A], [a1*(570*a2^2-2100*a2^2*w2)+1620*a2^2*w2+a4^2+2340*a3+2385*a2^2+114075*a2 +1711125,a4], [a1*((30*a2^2-29250*a2)*w2-660*a2^2-40950*a2) +2700*a2^2*w2+a3^2+1440*a2^2+1368900,a3], [4860*w2+a1*((-6300*w2)-8010)+a2^3-2295,a2],[w2^2+w2+1,w2],[a1^2-3,a1]]] [x^4+x+1, A^24-80*A^20+340*A^18+7520*A^16+23120*A^14-973378*A^12-462400*A^10 +50899280*A^8+74190340*A^6+67773664*A^4+2114616240*A^2+266962921, [[a4/624+A,A], [a1*(38*a2^2-140*a2^2*w2)-648*a2^2*w2+a4^2+9984*a3-954*a2^2+64896*a2,a4], [a1*((-65*a2*w2)-91*a2)+(60*a2^2+351*a2)*w2+a3^2+32*a2^2-117*a2+32448,a3], [(-3888*w2)+a1*((-840*w2)-1068)+a2^3+1836,a2],[w2^2+w2+1,w2],[a1^2-229,a1]]] [x^5-2,A^20+2500*A^10+50000, [[a3+A,A],[a3^5-5*a2,a3],[a2^2+22*a1+50,a2],[a1^2-5,a1]]] [x^5-5*x+12,A^10-10*A^8-75*A^6+1500*A^4-5500*A^2+16000, [[A-(a1*((3*a2^4-5*a2^3+25*a2^2)*w2^3+(3*a2^4+15*a2^3+25*a2^2)*w2^2 +10*a2^3*w2+9*a2^4+5*a2^3-50*a2^2) +((-20*a2^4)-25*a2^3)*w2^3+(10*a2^4-25*a2^3-250*a2^2)*w2^2 +((-10*a2^4)-250*a2^2)*w2-5*a2^4-25*a2^3-125*a2^2-625*a2) /3125,A], [a1*(20625*w2^3+20625*w2^2+33750)+90625*w2^3-21875*w2^2+68750*w2+a2^5+34375, a2],[w2^4+w2^3+w2^2+w2+1,w2],[a1^2+10,a1]]] [x^5+20*x+32,A^10-20*A^8+100*A^6+2000*A^4-32000*A^2+128000, [[(a1*((6*a2^4-10*a2^3+100*a2^2)*w2^3+(6*a2^4-70*a2^3+100*a2^2)*w2^2 -80*a2^3*w2-7*a2^4-40*a2^3+50*a2^2) +(10*a2^4+100*a2^3)*w2^3+(20*a2^4+100*a2^3+500*a2^2)*w2^2 +(30*a2^4+500*a2^2)*w2+15*a2^4-50*a2^3+250*a2^2+2500*a2) /12500 +A,A], [a1*(22500*w2^3+22500*w2^2+42500)+87500*w2^3-12500*w2^2+75000*w2+a2^5+37500, a2],[w2^4+w2^3+w2^2+w2+1,w2],[a1^2+5,a1]]] [x^5+11*x+44,A^10-22*A^8+77*A^6+4356*A^4-53724*A^2+189728, [[(a1*((23*a2^4-55*a2^3+605*a2^2)*w2^3+(23*a2^4-935*a2^3+605*a2^2)*w2^2 -990*a2^3*w2-106*a2^4-495*a2^3 +1815*a2^2) +(100*a2^4+715*a2^3)*w2^3+(50*a2^4+715*a2^3+6050*a2^2)*w2^2 +(150*a2^4+6050*a2^2)*w2+75*a2^4-165*a2^3+3025*a2^2+33275*a2) /166375 +A,A], [a1*(74800*w2^3+74800*w2^2+126775)+158125*w2^3-34375*w2^2+123750*w2+a2^5 +61875,a2],[w2^4+w2^3+w2^2+w2+1,w2], [a1^2+2,a1]]] [x^5+x^4-4*x^3-3*x^2+3*x+1,A^5+A^4-4*A^3-3*A^2+3*A+1, [[((10*a1^4+99*a1^3+121*a1^2)*w1^3+((-15*a1^4)+33*a1^3+242*a1^2)*w1^2 +(20*a1^4+77*a1^3-242*a1^2)*w1+26*a1^4 -33*a1^3+1331*a1+1331) /6655 +A,A],[385*w1^3+110*w1^2+220*w1+a1^5-66,a1],[w1^4+w1^3+w1^2+w1+1,w1]]] [x^5+100*x^2+1000, A^20+250000*A^14+20000000*A^12+625000000*A^10-5300000000*A^8+700000000000*A^6 +18750000000000*A^4-598000000000000*A^2+4205000000000000, [[(a1*(a2*(a3^4+2*a3^2)-6*a3^3)+a2*(a3^4+10*a3^2)+10*a3^3+40*a3)/40+A,A], [a3^5-50*a1*a2-110*a2,a3],[a2^2-22*a1+50,a2],[a1^2-5,a1]]] [x^6+x^3+1,A^6+A^3+1,[[a2/2+A,A],[a2^3-4*a1-4,a2],[a1^2+3,a1]]] [x^6-2,A^12-1012*A^6+19307236, [[a3+A,A],[a3^3-18*a2-35*a1,a3],[a2^2+6,a2],[a1^2-2,a1]]] Evaluation took 9.3890 seconds (9.4080 elapsed) using 4571.050 MB.
3.組成列
組成列の計算については,http://ehito.hatenablog.com/entry/2019/02/13/200937 で述べましたが,mnsg に積閉の必要条件などを加え,やや速くなっています.cs の引数は nGG の出力,出力は先述の通りです.
mul(A,B):=map(lambda([s],A[s]),B)$ inv(A):=map(second,sort(map("[",A,sort(A)),lambda([s,t],s[1]<t[1])))$ isG(GG):=is(setify(apply('append,makelist(makelist(mul(i,j),i,GG),j,GG)))=setify(GG))$ CC(GG):=block([g,C:[],G:setify(GG),H], unless G={} do (g:listify(G)[1], H:setify(map(lambda([s],mul(s,mul(g,inv(s)))),GG)), G:setdifference(G,H),push(H,C)),map(listify,C))$ mnsg(GG):=block([S:0,lenGG:length(GG)], C0:sort(CC(GG)),C01:C0[1], PS:map(lambda([s],apply('append,listify(s))),listify(powerset(setify(rest(C0))))), PS:map(lambda([s],append(C0[1],s)),PS), printn(length(PS)), for d in rest(reverse(listify(divisors(lenGG)))) while S=0 do ( PS:sublist(PS,lambda([s],length(s)<=d and member(lst2:mul(lst:last(s),lst),s) and member(mul(lst2,lst),s))), printn(length(PS)), for g in PS unless length(S:g)=d and isG(g) do S:0),S)$ cs(GG):=block([S:[GG],m:GG],unless length(m)=1 do push(m:mnsg(m),S), csGG:[S:reverse(S),S:map(length,S),makelist(S[i-1]/S[i],i,2,length(S))])$
実行例.
(%i7) cs(nGG(mp(x^12-3))); Evaluation took 3.5550 seconds (3.5900 elapsed) using 679.381 MB. (%o7) [[[[1,2,3,4,5,6,7,8,9,10,11,12],[12,9,8,7,5,6,4,3,2,11,10,1], [10,9,7,8,3,4,6,5,11,2,12,1],[11,2,4,3,8,7,6,5,10,9,1,12], [7,5,11,10,12,2,9,1,8,3,4,6],[4,5,10,11,1,9,2,12,3,8,7,6], [3,8,9,1,11,10,2,12,4,5,6,7],[8,3,2,12,10,11,9,1,7,5,6,4], [3,6,11,10,9,1,12,2,4,7,8,5],[8,6,10,11,2,12,1,9,7,4,3,5], [7,4,12,2,11,10,1,9,8,6,5,3],[4,7,1,9,10,11,12,2,3,6,5,8], [2,1,7,8,6,5,3,4,12,10,11,9],[9,12,4,3,6,5,8,7,1,11,10,2], [10,12,3,4,7,8,5,6,11,1,9,2],[11,1,8,7,4,3,5,6,10,12,2,9], [6,3,12,2,1,9,11,10,5,7,8,4],[6,8,1,9,12,2,10,11,5,4,3,7], [1,11,5,6,3,4,8,7,9,12,2,10],[12,10,5,6,8,7,3,4,2,1,9,11], [2,11,6,5,7,8,4,3,12,9,1,10],[9,10,6,5,4,3,7,8,1,2,12,11], [5,7,9,1,2,12,11,10,6,3,4,8],[5,4,2,12,9,1,10,11,6,8,7,3]], [[1,2,3,4,5,6,7,8,9,10,11,12],[1,11,5,6,3,4,8,7,9,12,2,10], [2,1,7,8,6,5,3,4,12,10,11,9],[9,10,6,5,4,3,7,8,1,2,12,11], [10,12,3,4,7,8,5,6,11,1,9,2],[11,2,4,3,8,7,6,5,10,9,1,12], [12,9,8,7,5,6,4,3,2,11,10,1],[2,11,6,5,7,8,4,3,12,9,1,10], [11,1,8,7,4,3,5,6,10,12,2,9],[9,12,4,3,6,5,8,7,1,11,10,2], [10,9,7,8,3,4,6,5,11,2,12,1],[12,10,5,6,8,7,3,4,2,1,9,11]], [[1,2,3,4,5,6,7,8,9,10,11,12],[1,11,5,6,3,4,8,7,9,12,2,10], [2,1,7,8,6,5,3,4,12,10,11,9],[11,2,4,3,8,7,6,5,10,9,1,12], [2,11,6,5,7,8,4,3,12,9,1,10],[11,1,8,7,4,3,5,6,10,12,2,9]], [[1,2,3,4,5,6,7,8,9,10,11,12],[2,11,6,5,7,8,4,3,12,9,1,10], [11,1,8,7,4,3,5,6,10,12,2,9]],[[1,2,3,4,5,6,7,8,9,10,11,12]]], [24,12,6,3,1],[2,2,2,3]]
2.Galois 群
現在のオリジナルプログラムでは,Galois 群の元と分解体の絶対定義式の根との対応の把握に若干の検索を行っています.
これに対して,下記の nGG では,1.で得た RA における A が絶対定義式 DA の任意の根であるという点に着目して,それらの根と「入力 p の根の置換」との対応を直接求めています.すなわち,1.で得た DA の数値根 (絶対誤差は p の根差の半分より小とする)を の A に代入したものは の順列 であり,この が絶対定義式の根 に対応する Galois 群の元,そして, 自体も1.で得た KK により, と表せます.
nGG の引数は DA のみですが,mp が生成した RA,KK も上記のように内部で参照し,出力は Galois 群 GG2,また,その元と DA の根との対応のリスト GGRS も生成します.
nGG(DA):=block([h], n:50,fpprintprec:n,ratepsilon:fpprec:2*n,er:0.1^n, nRS:map('rhs,bfallroots(DA)), nRAS:expand(map(lambda([s],subst(A=s,RA)),nRS)), nRAS1:nRAS[1], GG2:fullmapl(lambda([s],sublist_indices(nRAS1,lambda([t],abs(s-t)<er))[1]),nRAS), RS:rat(map(lambda([s],KK.s),fullmapl(lambda([s],RA[s]),map(lambda([s],makelist(s[i],i,length(KK))),GG2)))), GGRS:map("[",GG2,RS), GG2)$
実行例.
(%i5) nGG(mp(x^5-2)); Evaluation took 0.2930 seconds (0.3980 elapsed) using 148.313 MB. (%o5) [[1,2,3,4,5],[4,2,5,1,3],[2,4,1,5,3],[2,1,4,3,5],[3,5,1,4,2], [5,3,4,1,2],[5,4,3,2,1],[3,1,5,2,4],[1,3,2,5,4],[4,5,2,3,1], [2,5,3,1,4],[2,3,5,4,1],[1,4,5,3,2],[4,1,3,5,2],[3,4,2,1,5], [5,1,2,4,3],[1,5,4,2,3],[4,3,1,2,5],[3,2,4,5,1],[5,2,1,3,4]] (%i6) GGRS; Evaluation took 0.0000 seconds (0.0000 elapsed) using 0 bytes. (%o6) [[[1,2,3,4,5],A],[[4,2,5,1,3],(A^16-5*A^11+2350*A^6-3500*A)/11000], [[2,4,1,5,3],-(A^16-5*A^11+2350*A^6-3500*A)/11000],[[2,1,4,3,5],-A], [[3,5,1,4,2],-(A^16-10*A^11+2900*A^6-18000*A)/22000], [[5,3,4,1,2],(A^16-10*A^11+2900*A^6-18000*A)/22000], [[5,4,3,2,1],(A^16+10*A^11+2900*A^6+18000*A)/22000], [[3,1,5,2,4],(A^16+5*A^11+2350*A^6+3500*A)/11000], [[1,3,2,5,4],-(A^16+5*A^11+2350*A^6+3500*A)/11000], [[4,5,2,3,1],-(A^16+10*A^11+2900*A^6+18000*A)/22000], [[2,5,3,1,4],-(3*A^16+7600*A^6+11000*A)/22000], [[2,3,5,4,1],-(A^16+5*A^11+2350*A^6+14500*A)/11000], [[1,4,5,3,2],-(A^16-5*A^11+2350*A^6-14500*A)/11000], [[4,1,3,5,2],(A^16-5*A^11+2350*A^6-14500*A)/11000], [[3,4,2,1,5],(A^11+1800*A)/1100], [[5,1,2,4,3],(3*A^16+7600*A^6-11000*A)/22000], [[1,5,4,2,3],-(3*A^16+7600*A^6-11000*A)/22000], [[4,3,1,2,5],-(A^11+1800*A)/1100], [[3,2,4,5,1],(A^16+5*A^11+2350*A^6+14500*A)/11000], [[5,2,1,3,4],(3*A^16+7600*A^6+11000*A)/22000]]