\documentclass{article} \usepackage{amssymb} \usepackage{amsmath} \usepackage{url} \urlstyle{same} \def\ul{\underline} \def\ov{\overline} \begin{document} \begin{center}{\Large Annotated Examples 1}\end{center} \begin{center}{\large Disguised Hermitian curve}\end{center} The Hermitian curve in one-point form (used for coding over $\mathbf{F}_{16}$ because it has $64$ other rational points there) is usually given in a form such as $y^4+y=x^5$, which emphasizes it {\em trace-norm form}, since the left-hand side is the {\em trace} of $y$ from $\mathbf{F}_{16}$ to $\mathbf{F}_4$ and the right hand side is the {\em norm} $x^4\cdot x$ of $x$ from $\mathbf{F}_{16}$ to $\mathbf{F}_4$. At the one-point $P_{\infty}$, the rational functions $x$ and $y$ have pole orders $4$ and $5$ respectively; so rename them $f_4$ and $f_5$, and use a grevlex-over-weight monomial order to get the curve \[\ov{\mathbf{F}}_2[f_5;f_4]/\langle f_5^4+f_5-f_4^5\rangle.\] As an $\ov{\mathbf{F}}_2[f_4]$-{\em module}, this has a {\em basis} $(f_0:=1,f_5,f_{10}:=f_5^2,f_{15}:=f_5^3)$; so as an {\em algebra} over $\ov{\mathbf{F}}_2[f_4]$, it has a presentation as \[\ov{\mathbf{F}}_2[f_{15},f_{10},f_5;f_4]/\langle I\rangle\] with $I$ having a Gr\"obner basis \[f_{15}^2-(-f_{15}+f_{10}f_4^5)\] \[f_{15}f_{10}-(-f_{10}+f_5f_4^5)\] \[f_{10}^2-(-f_5+f_4^5)\] \[f_{15}f_5-(-f_5+f_4^5)\] \[f_{10}f_5-f_{15}\] \[f_5^2-f_{10}\] which describes the (non-trivial part of the) multiplication of module basis elements. Now disguise this using $f_9:=f_5f_4$ and $f_8:=f_4^2$ and arbitrary characteristic to get \[ \mathbf{F}[f_9;f_8]/\langle f_9^8-f_8^9+2f_9f_8^6-f_9^2f_8^3\rangle\] I used this example to show that the normal function in SINGULAR 3-0-4 and the integralClosure function in Macaulay2 version 1.1 both terminated prematurely. (Also it shows that MAGMA's IntegralClosure function uses a much too restrictive separability condition.) \newpage In SINGULAR 3-1-0, now \begin{verbatim} SINGULAR / A Computer Algebra System for Polynomial Computations / version 3-1-0 0< by: G.-M. Greuel, G. Pfister, H. Schoenemann \ Mar 2009 FB Mathematik der Universitaet, D-67653 Kaiserslautern \ > LIB "normal.lib"; > intmat A[2][2]=1,0,9,8; > ring r=0,(f9,f8),M(A); > ideal i=f9^8-f8^9+2*f9*f8^6-f9^2*f8^3; > list nor=normal(i); > nor; [1]: [1]: // characteristic : 0 // number of vars : 7 // block 1 : ordering dp // : names T(1) T(2) T(3) T(4) T(5) // block 2 : ordering M // : names f9 f8 // : weights 1 0 // : weights 9 8 // block 3 : ordering C [2]: [1]: _[1]=f9^5*f8^2 _[2]=f9^6*f8 _[3]=-f9^4*f8^2+f9^3*f8^5 _[4]=f9^8 _[5]=-f9^2*f8^5+f9*f8^8 _[6]=-f9^2*f8^3+f9*f8^6 > def R=nor[1][1]; > setring R; > normap; normap[1]=f9 normap[2]=f8 > norid; norid[1]=T(1)*f9-T(2)*f8 norid[2]=T(4)*f9-T(5)*f8+f9 norid[3]=-T(5)+f8^2 norid[4]=-T(3)*f8+f9^2 norid[5]=T(2)*f9^2-T(4)*f8 norid[6]=T(1)*f8^3-T(2)*f8-T(3)*f9^2 norid[7]=T(3)*f8^3-T(5)*f9^2 norid[8]=-T(2)*f9*f8+T(2)*f8^4-T(3)*f9^3 norid[9]=T(3)*f9^5-T(4)*f8^5-T(5)*f9+T(5)*f8^3 norid[10]=T(4)*f8^8-T(5)*f9^7+T(5)*f9*f8^3-T(5)*f8^6 norid[11]=T(1)^2-f8 norid[12]=T(1)*T(2)-f9 norid[13]=T(2)^2-T(3) norid[14]=T(1)*T(3)-T(2)*f9 norid[15]=T(2)*T(3)-T(4) norid[16]=T(3)^2-T(1)*f8^2+T(2) norid[17]=T(1)*T(4)-T(3)*f9 norid[18]=T(2)*T(4)-T(1)*f8^2+T(2) norid[19]=T(3)*T(4)+T(3)-f9*f8^2 norid[20]=T(4)^2-T(1)*f9^2*f8+T(4) norid[21]=T(1)*T(5)-T(1)*f8^2 norid[22]=T(2)*T(5)-T(1)*f9*f8 norid[23]=T(3)*T(5)-f9^2*f8 norid[24]=T(4)*T(5)-T(1)*f9^3 norid[25]=T(5)^2-f8^4 norid[26]=-f9^8+f9^2*f8^3-2*f9*f8^6+f8^9 \end{verbatim} At least, \begin{verbatim} > list l=interred(norid);l; [1]: _[1]=T(5)-f8^2 _[2]=T(4)*f8^8-T(5)*f9^7+T(5)*f9*f8^3-T(5)*f8^6 _[3]=T(4)*f9-T(5)*f8+f9 _[4]=T(3)*f8-f9^2 _[5]=T(3)*f9^5-T(4)*f8^5-T(5)*f9+T(5)*f8^3 _[6]=T(2)*f9*f8-T(2)*f8^4+T(3)*f9^3 _[7]=T(2)*f9^2-T(4)*f8 _[8]=T(1)*f8^3-T(2)*f8-T(3)*f9^2 _[9]=T(1)*f9-T(2)*f8 _[10]=T(4)^2-T(1)*f9^2*f8+T(4) _[11]=T(3)*T(4)+T(3)-f9*f8^2 _[12]=T(2)*T(4)-T(1)*f8^2+T(2) _[13]=T(1)*T(4)-T(3)*f9 _[14]=T(3)^2-T(1)*f8^2+T(2) _[15]=T(2)*T(3)-T(4) _[16]=T(1)*T(3)-T(2)*f9 _[17]=T(2)^2-T(3) _[18]=T(1)*T(2)-f9 _[19]=T(1)^2-f8 _[20]=f9^8-f9^2*f8^3+2*f9*f8^6-f8^9 \end{verbatim} makes it easier to see that $T(5)$ is redundant by any standards, and that $T(4)$,$T(3)$, $T(2)$, and $T(1)$, should have weights $15$, $10$, $5$, and $4$ respectively. So I would choose to edit this as follows, to get a $\mathbf{Q}[f_4]$ algebra presentation with module basis $(f_0:=1,f_5,f_{10},f_{15})$. \begin{verbatim} >intmat B[4][4]= 1, 1,1,0, 1, 1,0,0, 1, 0,0,0, 15,10,5,4; > ring ic0=0,(f15,f10,f5,f4),M(B); > map phi=R0,f4,f5,f10,f15,f4^4,f5*f4,f4^2; > ideal j0=std(phi(norid));j0; j0[1]=f5^2-f10 j0[2]=f10*f5-f15 j0[3]=f15*f5+f5-f4^5 j0[4]=f10^2+f5-f4^5 j0[5]=f15*f10+f10-f5*f4^5 j0[6]=f15^2+f15-f10*f4^5 \end{verbatim} \newpage This should be almost independent of characteristic, so try this in some relatively small generic (not 2,3,5) characteristic, say $23$, using both normal and normalP: \begin{verbatim} > ring r23=23,(f9,f8),M(A); > ideal i23=f9^8=f8^9+2*f9*f8^6-f9^2*f8^3; > list nor23=normal(i23); > nor23;[1]:[1]: // characteristic : 23 // number of vars : 7 // block 1 : ordering dp // : names T(1) T(2) T(3) T(4) T(5) // block 2 : ordering M // : names f9 f8 // : weights 0 1 // : weights 9 8 // block 3 : ordering C [2]:[1]: _[1]=f9^5*f8^2 _[2]=f9^6*f8 _[3]=f9^3*f8^5-f9^4*f8^2 _[4]=f9^8 _[5]=f9*f8^8-f9^2*f8^5 _[6]=f9*f8^6-f9^2*f8^3 > def R23=nor23[1][1]; > setring R23; > normap; normap[1]=f9 normap[2]=f8 > norid; norid[1]=T(1)*f9-T(2)*f8 norid[2]=T(4)*f9-T(5)*f8+f9 norid[3]=-T(5)+f8^2 norid[4]=-T(3)*f8+f9^2 norid[5]=T(2)*f9^2-T(4)*f8 norid[6]=T(1)*f8^3-T(2)*f8-T(3)*f9^2 norid[7]=T(3)*f8^3-T(5)*f9^2 norid[8]=T(2)*f8^4-T(2)*f9*f8-T(3)*f9^3 norid[9]=T(3)*f9^5-T(4)*f8^5+T(5)*f8^3-T(5)*f9 norid[10]=T(4)*f8^8-T(5)*f8^6+T(5)*f9*f8^3-T(5)*f9^7 norid[11]=T(1)^2-f8 norid[12]=T(1)*T(2)-f9 norid[13]=T(2)^2-T(3) norid[14]=T(1)*T(3)-T(2)*f9 norid[15]=T(2)*T(3)-T(4) norid[16]=T(3)^2-T(1)*f8^2+T(2) norid[17]=T(1)*T(4)-T(3)*f9 norid[18]=T(2)*T(4)-T(1)*f8^2+T(2) norid[19]=T(3)*T(4)+T(3)-f9*f8^2 norid[20]=T(4)^2-T(1)*f9^2*f8+T(4) norid[21]=T(1)*T(5)-T(1)*f8^2 norid[22]=T(2)*T(5)-T(1)*f9*f8 norid[23]=T(3)*T(5)-f9^2*f8 norid[24]=T(4)*T(5)-T(1)*f9^3 norid[25]=T(5)^2-f8^4 norid[26]=f8^9-2*f9*f8^6+f9^2*f8^3-f9^8 > list l=interred(norid);l; [1]: _[1]=T(5)-f8^2 _[2]=T(4)*f8^8-T(5)*f9^7+T(5)*f9*f8^3-T(5)*f8^6 _[3]=T(4)*f9-T(5)*f8+f9 _[4]=T(3)*f8-f9^2 _[5]=T(3)*f9^5-T(4)*f8^5-T(5)*f9+T(5)*f8^3 _[6]=T(2)*f9*f8-T(2)*f8^4+T(3)*f9^3 _[7]=T(2)*f9^2-T(4)*f8 _[8]=T(1)*f8^3-T(2)*f8-T(3)*f9^2 _[9]=T(1)*f9-T(2)*f8 _[10]=T(4)^2-T(1)*f9^2*f8+T(4) _[11]=T(3)*T(4)+T(3)-f9*f8^2 _[12]=T(2)*T(4)-T(1)*f8^2+T(2) _[13]=T(1)*T(4)-T(3)*f9 _[14]=T(3)^2-T(1)*f8^2+T(2) _[15]=T(2)*T(3)-T(4) _[16]=T(1)*T(3)-T(2)*f9 _[17]=T(2)^2-T(3) _[18]=T(1)*T(2)-f9 _[19]=T(1)^2-f8 _[20]=f9^8-f9^2*f8^3+2*f9*f8^6-f8^9 \end{verbatim} The new normalP function in SINGULAR 3-1-0, together with the "withring" option: \begin{verbatim} SINGULAR / A Computer Algebra System for Polynomial Computations / version 3-1-0 0< by: G.-M. Greuel, G. Pfister, H. Schoenemann \ Mar 2009 FB Mathematik der Universitaet, D-67653 Kaiserslautern \ > LIB "normal.lib"; > ring r=23,(y,x),wp(9,8); > ideal i=y8-y2x3+2yx6-x9; > list norp=normalP(i,"withring"); > norp; [1]: [1]: // characteristic : 23 // number of vars : 2 // block 1 : ordering dp // : names T(1) T(3) // block 2 : ordering C [2]: [1]: _[1]=y5x _[2]=y6 _[3]=y3x4-y4x _[4]=x8-y2x2 _[5]=yx5-y2x2 [3]: [1]: 22 [2]: 22 > def R=norp[1][1]; > setring R; > normap; normap[1]=T(1)^6-T(1)*T(3)^2 normap[2]=T(1)^2 > norid; norid[1]=T(1)^17-3*T(1)^12*T(3)^2+3*T(1)^7*T(3)^4-T(1)^7*T(3)-T(1)^2*T(3)^6+T(1)^2*T(3)^3 norid[2]=T(1)^11*T(3)-2*T(1)^6*T(3)^3+T(1)*T(3)^5-T(1)*T(3)^2 norid[3]=T(1)^10-2*T(1)^5*T(3)^2+T(3)^4-T(3) norid[4]=T(1)^10*T(3)-2*T(1)^5*T(3)^3+T(3)^5-T(3)^2 norid[5]=T(1)^15-3*T(1)^10*T(3)^2+3*T(1)^5*T(3)^4-T(1)^5*T(3)-T(3)^6+T(3)^3 norid[6]=T(1)^12-2*T(1)^7*T(3)^2+T(1)^2*T(3)^4-T(1)^2*T(3) norid[7]=T(1)^12*T(3)-2*T(1)^7*T(3)^3+T(1)^2*T(3)^5-T(1)^2*T(3)^2 norid[8]=T(1)^11-2*T(1)^6*T(3)^2+T(1)*T(3)^4-T(1)*T(3) norid[9]=T(1)^48-8*T(1)^43*T(3)^2+5*T(1)^38*T(3)^4-10*T(1)^33*T(3)^6+T(1)^28*T(3)^8-10*T(1)^23*T(3)^10+5*T(1)^18*T(3)^12-8*T(1)^13*T(3)^14+T(1)^8*T(3)^16-T(1)^8*T(3)^4 > option(redSB); > ideal j=std(norid);j; j[1]=T(1)^10-2*T(1)^5*T(3)^2+T(3)^4-T(3) \end{verbatim} So its answer is a grevlex one on T(1) and T(3), of implicit weights 4 and 10. Using the slightly newer normalP option "withRing" with or without the additonal "noRed" option: \begin{verbatim} SINGULAR / A Computer Algebra System for Polynomial Computations / version 3-1-0 0< by: G.-M. Greuel, G. Pfister, H. Schoenemann \ Mar 2009 FB Mathematik der Universitaet, D-67653 Kaiserslautern \ > LIB "presolve.lib"; > LIB "normal.lib"; > ring r=23,(y,x),wp(9,8); > ideal i=y8-y2x3+2yx6-x9; > list norp=normalP(i,"withRing","noRed"); > norp; [1]: [1]: // characteristic : 23 // number of vars : 6 // block 1 : ordering dp // : names T(1) T(2) T(3) T(4) // block 2 : ordering wp // : names y x // : weights 9 8 // block 3 : ordering C [2]: [1]: _[1]=y5x _[2]=y6 _[3]=y3x4-y4x _[4]=x8-y2x2 _[5]=yx5-y2x2 [3]: [1]: 22 [2]: 22 > def R=norp[1][1]; > setring R; > normap; normap[1]=y normap[2]=x > norid; norid[1]=T(1)*y-T(2)*x norid[2]=-T(3)*x+y^2 norid[3]=T(2)*y^2-T(4)*x+2*x norid[4]=-T(4)*y+x^3+y norid[5]=T(1)*x^3-T(1)*y-T(3)*y^2 norid[6]=T(1)^2-x norid[7]=T(1)*T(2)-y norid[8]=T(2)^2-T(3) norid[9]=T(1)*T(3)-T(2)*y norid[10]=T(2)*T(3)-T(4)+2 norid[11]=T(3)^2-T(1)*x^2+T(2) norid[12]=T(1)*T(4)-2*T(1)-T(3)*y norid[13]=T(2)*T(4)-T(1)*x^2-T(2) norid[14]=T(3)*T(4)-T(3)-y*x^2 norid[15]=T(4)^2-T(2)*y*x^2-3*T(4)+2 norid[16]=y^8-x^9+2*y*x^6-y^2*x^3 > option(redSB); > ideal j=std(norid);j; j[1]=y^8-x^9+2*y*x^6-y^2*x^3 j[2]=T(4)*y-x^3-y j[3]=T(4)*x^6-y^7-3*x^6+y*x^3 j[4]=T(3)*x-y^2 j[5]=T(3)*y^5-T(4)*x^5+3*x^5-y*x^2 j[6]=T(2)*y^2-T(4)*x+2*x j[7]=T(2)*x^4-T(2)*y*x-T(3)*y^3 j[8]=T(1)*y-T(2)*x j[9]=T(1)*x^3-T(2)*x-T(3)*y^2 j[10]=T(4)^2-T(2)*y*x^2-3*T(4)+2 j[11]=T(3)*T(4)-T(3)-y*x^2 j[12]=T(2)*T(4)-T(1)*x^2-T(2) j[13]=T(1)*T(4)-2*T(1)-T(3)*y j[14]=T(3)^2-T(1)*x^2+T(2) j[15]=T(2)*T(3)-T(4)+2 j[16]=T(1)*T(3)-T(2)*y j[17]=T(2)^2-T(3) j[18]=T(1)*T(2)-y j[19]=T(1)^2-x \end{verbatim} which gives an answer grevlex in 4 new variables T(1), T(2), T(3), T(4) of implicit weights 4,5,10,15, over the original ring with variables y and x of weights 9 and 8, without realizing that the varibales y and x are no longer of any use. \newpage For Macaulay2's integralClosure function (March 15, 2009 version ?), the following in characteristic 23 which used to take me about 57 seconds now seems to take between one and two second: \begin{verbatim} Macaulay 2, version 1.2 with packages: Elimination, IntegralClosure, LLLBases, PrimaryDecomposition, ReesAlgebra, SchurRings, TangentCone i1 : load "IntegralClosure.m2"; i2 : R=ZZ/23[y,x,MonomialOrder=>{Weights=>{9,8}}]; i3 : I=ideal(y^8-y^2*x^3+2*y*x^6-x^9); i4 : S=R/I; i5 : time P=presentation(integralClosure(S)) -- used 1.34 seconds o5 = | -w_(12,0)^6w_(7,0)+w_(12,0)^2w_(10,0)^3+w_(10,0)^2w_(7,0)^2 -w_(12,0)^6w_(10,0)+w_(10,0)^3w_(7,0)+w_(7,0) w_(12,0)^5-w_(10,0)^4-w_(10,0) w_(12,0)^3w_(10,0)^2-w_(12,0)^2w_(7,0) -w_(12,0)^6+w_(12,0)w_(10,0)+w_(10,0)^2w_(7,0) | i6 : time G=gens gb P -- used 0. seconds o6 = | w_(10,0)^14+w_(10,0)^11-w_(7,0)^5 w_(12,0)w_(7,0)^4-w_(10,0)^12-w_(10,0)^9 w_(12,0)w_(10,0)^2-w_(7,0) w_(12,0)^2w_(7,0)^3-w_(10,0)^10-w_(10,0)^7 w_(12,0)^3w_(7,0)^2-w_(10,0)^8-w_(10,0)^5 w_(12,0)^4w_(7,0)-w_(10,0)^6-w_(10,0)^3 w_(12,0)^5-w_(10,0)^4-w_(10,0) | \end{verbatim} The speed is vastly improved, but the output is in terms of functions that would have weights 4,5, and 14! I don't see any theoretical reasoning that would justify answers other than either 4,5 or 4,5,10,15. M2 seems to try to produce a minimal number of generators, but misses here despite one of the relations being \begin{verbatim} w_(12,0)w_(10,0)^2-w_(7,0)\end{verbatim} which shows that $f_{14}=f_5^2f_4$. The charactersitic 0 version is: \begin{verbatim} i8 : R=QQ[y,x,MonomialOrder=>{Weights=>{9,8}}] i9 : I=ideal(y^8-y^2*x^3+2*y*x^6-x^9) i10 : S=R/I i11 : time P=presentation(integralClosure(S)) -- used 1.54 seconds o11 = | -w_(12,0)^6w_(7,0)+w_(12,0)^2w_(10,0)^3+w_(10,0)^2w_(7,0)^2 -w_(12,0)^6w_(10,0)+w_(10,0)^3w_(7,0)+w_(7,0) w_(12,0)^5-w_(10,0)^4-w_(10,0) w_(12,0)^3w_(10,0)^2-w_(12,0)^2w_(7,0) -w_(12,0)^6+w_(12,0)w_(10,0)+w_(10,0)^2w_(7,0) | i12 : time G=gens gb P -- used 0. seconds o12 = | w_(10,0)^14+w_(10,0)^11-w_(7,0)^5 w_(12,0)w_(7,0)^4-w_(10,0)^12-w_(10,0)^9 w_(12,0)w_(10,0)^2-w_(7,0) w_(12,0)^2w_(7,0)^3-w_(10,0)^10-w_(10,0)^7 w_(12,0)^3w_(7,0)^2-w_(10,0)^8-w_(10,0)^5 w_(12,0)^4w_(7,0)-w_(10,0)^6-w_(10,0)^3 w_(12,0)^5-w_(10,0)^4-w_(10,0) | \end{verbatim} which is consistent with the char 23 result. This is vastly superior to the segmentation faults and silly output that used to be produced. \newpage Let's try MAGMA. There is no way to use weights; and we know it would complain about separability in char 2. \begin{verbatim} t:=Cputime(); Q:=Rationals(); F:=FunctionField(Q); P:=PolynomialRing(F); f:=y^8-y^2*x^3+2*y*x^6-x^9; Ff:=RationalExtensionRepresentation(FunctionField(f)); C:=CoefficientRing(Ff); INT:=Integers(C); IC:=IntegralClosure(INT,Ff); B:=Basis(IC); for i in [1..#B] do i,B[i]; end for; "time for char=0 is",Cputime(t); -------------------------------------------------------------------- 1 1 2 Y 3 1/X*Y^2 4 1/X*Y^3 5 1/X^2*Y^4 6 1/X^2*Y^5 7 1/X^3*Y^6 8 1/X^13*Y^7 + 1/X^10*Y^6 + 1/X^7*Y^5 + 1/X^4*Y^4 - 1/X^10*Y + 1/X^7 time for char=0 is 0.080 \end{verbatim} \begin{verbatim} t23:=Cputime(); Q:=GF(23); F:=FunctionField(Q); P:=PolynomialRing(F); f:=y^8-y^2*x^3+2*y*x^6-x^9; Ff:=RationalExtensionRepresentation(FunctionField(f)); C:=CoefficientRing(Ff); INT:=Integers(C); IC:=IntegralClosure(INT,Ff); B:=Basis(IC); for i in [1..#B] do i,B[i]; end for; "time for char=23 is",Cputime(t23); ------------------------------------------------------------------------ 1 1 2 Y 3 1/X*Y^2 4 1/X*Y^3 5 1/X^2*Y^4 6 1/X^2*Y^5 7 1/X^3*Y^6 8 1/X^13*Y^7 + 1/X^10*Y^6 + 1/X^7*Y^5 + 1/X^4*Y^4 + 22/X^10*Y + 1/X^7 time for char=23 is 0.090 \end{verbatim} In both cases, it gives an $\mathbf{F}[f_8]$-module basis with elements of weights $0,9,10,19,20,29,30,4$, again obscuring the function of weight 5. And the integral closure is treated a subset of, maybe, $\mathbf{F}(X)[Y]/\langle f\rangle$, with no explicit version given. Try MAGMA's Normalisation function instead. \begin{verbatim} t:=Cputime(); SetLogFile("may2609"); F:=Rationals(); P:=PolynomialRing(F,2,"weight",[1,0,9,8]); f:=y^8-y^2*x^3+2*y*x^6-x^9; I:=ideal; N:=Normalisation(I); J:=N[1][1];J; "Normalisation time=",Cputime(t); G:=GroebnerBasis(J);G; "total time=",Cputime(t); \end{verbatim} The output ideal (in a ring with lex!!! monomial ordering) is generated by: \begin{verbatim} -J.1^21+J.1^16*J.2^4+J.1^11*J.2^5+J.1^6*J.2^6+J.1^6+J.1*J.2^7-J.1*J.2, -J.1^7+J.1^2*J.2^4+J.1^2*J.2, -J.1^10+2*J.1^5*J.2+J.2^8-J.2^2, -J.1^11+J.1^6*J.2^4+J.1*J.2^5+J.1*J.2^2, -J.1^12+2*J.1^7*J.2+J.1^2*J.2^8-J.1^2*J.2^2, -J.1^11*J.2+2*J.1^6*J.2^2+J.1*J.2^9-J.1*J.2^3, -J.1^17+J.1^12*J.2^4+J.1^7*J.2^5+J.1^2*J.2^6+J.1^2*J.2^3, -J.1^10*J.2^2+2*J.1^5*J.2^3+J.2^10-J.2^4, -J.1^6+J.1*J.2^4+J.1*J.2, -J.1^12*J.2^2+2*J.1^7*J.2^3+J.1^2*J.2^10-J.1^2*J.2^4, -J.1^11*J.2^3+2*J.1^6*J.2^4+J.1*J.2^11-J.1*J.2^5, -J.1^7*J.2+J.1^2*J.2^5+J.1^2*J.2^2, -J.1^10*J.2^4+2*J.1^5*J.2^5+J.2^12-J.2^6, -J.1^6*J.2^2+J.1*J.2^6+J.1*J.2^3, -J.1^5+J.2^4+J.2 Normalisation time= 0.840 seconds \end{verbatim} which then has Gr\"obner basis: \begin{verbatim} J.1^5-J.2^4-J.2 total time= 0.840 \end{verbatim} \newpage The author's qth-power algorithm produces \begin{verbatim} Magma V2.15-5 Loading file "qchar051109.mag" Loading "closure_func040909.mag" 1111111111111111111111111111111111111111111111111111111111 q= 3 Delta= S.2^27 WT_MATRIX_T= [ [ 10, 9, 7, 6, 5, 4, 3, 8 ] ] time for q= 3 is 0.050 seconds modulus= 3 1111111111111111111111111111111111111111111111111111111111 q= 5 1111111111111111111111111111111111111111111111111111111111 q= 7 Delta= S.2^24 WT_MATRIX_T= [ [ 19, 15, 14, 10, 9, 5, 4, 8 ] ] time for q= 7 is 0.030 seconds 1111111111111111111111111111111111111111111111111111111111 q= 11 Delta= S.2^24 WT_MATRIX_T= [ [ 19, 15, 14, 10, 9, 5, 4, 8 ] ] time for q= 11 is 0.040 seconds modulus= 77 [ f_15^2*f_8^12, f_15*f_8^13, f_15^7*f_8^6 + f_15^5*f_8^7 + f_15^6*f_8^4 - f_15^2*f_8^11 + f_15^7*f_8 + f_8^12 - f_15*f_8^9 + f_8^7 - f_15*f_8^4, f_15^6*f_8^7 + f_15^7*f_8^4 + f_15*f_8^12 + f_8^10 - f_15*f_8^7, f_15^5*f_8^8 + f_15^6*f_8^5 + f_15^7*f_8^2 + f_8^8 - f_15*f_8^5, f_15^4*f_8^9 + f_15^5*f_8^6 + f_15^6*f_8^3 + f_15^7 + f_8^6 - f_15*f_8^3, -f_15^6*f_8^6 - f_15^7*f_8^3 + f_15^3*f_8^10 + f_15*f_8^11 - f_8^9 + f_15*f_8^6, f_8^14, f_8^13 ] 1111111111111111111111111111111111111111111111111111111111 q= 13 Delta= S.2^24 WT_MATRIX_T= [ [ 19, 15, 14, 10, 9, 5, 4, 8 ] ] time for q= 13 is 0.040 seconds modulus= 1001 [ f_9^3*f_8^12, f_9^7*f_8^7 - f_9*f_8^10, f_9^6*f_8^8 + f_9^7*f_8^5 + f_8^11 - f_9*f_8^8, f_9^2*f_8^12, f_9*f_8^13, f_9^5*f_8^8 + f_9^6*f_8^5 + f_9^7*f_8^2 + f_8^8 - f_9*f_8^5, f_9^4*f_8^9 + f_9^5*f_8^6 + f_9^6*f_8^3 + f_9^7 + f_8^6 - f_9*f_8^3, f_8^14, f_8^13 ] 1 f_9^3*f_8^12 2 f_9^7*f_8^7 - f_9*f_8^10 3 f_9^6*f_8^8 + f_9^7*f_8^5 + f_8^11 - f_9*f_8^8 4 f_9^2*f_8^12 5 f_9*f_8^13 6 f_9^5*f_8^8 + f_9^6*f_8^5 + f_9^7*f_8^2 + f_8^8 - f_9*f_8^5 7 f_9^4*f_8^9 + f_9^5*f_8^6 + f_9^6*f_8^3 + f_9^7 + f_8^6 - f_9*f_8^3 8 f_8^14 9 f_8^13 newrelations= [ f_4^2 - f_8, f_5^2 - f_10, f_5*f_4 - f_9, f_9^2 - f_10*f_8, f_9*f_5 - f_14, f_9*f_4 - f_5*f_8, f_10^2 - f_4*f_8^2 + f_5, f_10*f_9 - f_19, f_10*f_5 - f_15 - 1, f_10*f_4 - f_14, f_14^2 - f_4*f_8^3 + f_5*f_8, f_14*f_10 - f_8^3 + f_9, f_14*f_9 - f_15*f_8 - f_8, f_14*f_5 - f_19, f_14*f_4 - f_10*f_8, f_15^2 - f_14*f_8^2 + 3*f_15 + 2, f_15*f_14 - f_5*f_8^3 + 2*f_14, f_15*f_10 - f_9*f_8^2 + 2*f_10, f_15*f_9 - f_8^3 + 2*f_9, f_15*f_5 - f_4*f_8^2 + 2*f_5, f_15*f_4 - f_19 + f_4, f_19^2 - f_14*f_8^3 + f_15*f_8 + f_8, f_19*f_15 - f_10*f_8^3 + 2*f_19, f_19*f_14 - f_9*f_8^3 + f_10*f_8, f_19*f_10 - f_5*f_8^3 + f_14, f_19*f_9 - f_4*f_8^3 + f_5*f_8, f_19*f_5 - f_8^3 + f_9, f_19*f_4 - f_15*f_8 - f_8 ] totaltime= 0.160 seconds \end{verbatim} in terms of a $\mathbf{Q}[f_8]$ module basis $f_0:=1,f_9,f_{10},f_{19},f_4,f_5,f_{14},f_{15}$. Minimization gives: \begin{verbatim} > load "closure_interchange.mag"; [15,10,5,4] [ v_15^2+3*v_15-v_10*v_4^5+2, v_15*v_10+2*v_10-v_5*v_4^5, v_10^2+v_5-v_4^5, v_15*v_5+2*v_5-v_4^5, v_10*v_5-v_15-1, v_5^2-v_10 ] time5= 0.210 \end{verbatim} Note that 5 was considered a bad prime in the input, whereas 3 is also a bad prime in that the integral closure is clearly larger than the reduction mod 3 would imply. \end{document} The option ``withring'' of normalP has serious flaws (as of May 19). \begin{verbatim} SINGULAR / A Computer Algebra System for Polynomial Computations / version 3-1-0 0< by: G.-M. Greuel, G. Pfister, H. Schoenemann \ Mar 2009 FB Mathematik der Universitaet, D-67653 Kaiserslautern \ > LIB "normal.lib"; > intmat A[2][2]=1,0,9,8; > ring r=23,(f9,f8),M(A); > ideal i=f9^8-f8^9+2*f9*f8^6-f9^2*f8^3; > list nor=normalP(i,"withring"); ? wrong range[7] in ideal/module(6) ? error occurred in normal.lib::substpartSpecial line 3683: ` kk=kk+1;` ? leaving normal.lib::substpartSpecial ? wrong range[8] in ideal/module(6) ? error occurred in normal.lib::substpartSpecial line 3683: ` kk=kk+1;` ? leaving normal.lib::substpartSpecial > nor; [1]: [1]: // characteristic : 23 // number of vars : 1 // block 1 : ordering dp // : names T(2) // block 2 : ordering C [2]: [1]: _[1]=f9^2*f8^12 _[2]=f9^4*f8^11 _[3]=f9^6*f8^10 _[4]=f9^7+f9^6*f8^3+f9^5*f8^6+f9^4*f8^9-f9*f8^3+f8^6 _[5]=f8^13 [3]: [1]: 22 [2]: 22 > def R=nor[1][1]; > setring R; > normap; normap[1]=0 normap[2]=0 > norid; norid[1]=T(2)^4-T(2) norid[2]=T(2)^5-T(2)^2 norid[3]=T(2)^6-T(2)^3 \end{verbatim} would seem to have produced four elements of implicit weights 10,20,30, and 4 respectively, but the presentation is garbage. However, by simply changing around a few terms, \begin{verbatim} > ring r23=23,(f9,f8),M(A); > ideal i23=f9^8-f9^2*f8^3+2*f9*f8^6-f8^9; > list nor23=normalP(i23,"withring"); ? wrong range[7] in ideal/module(6) ? error occurred in normal.lib::substpartSpecial line 3683: `kk=kk+1;` ? leaving normal.lib::substpartSpecial ? wrong range[8] in ideal/module(6) ? error occurred in normal.lib::substpartSpecial line 3683: `kk=kk+1;` ? leaving normal.lib::substpartSpecial > nor23;[1]:[1]: // characteristic : 23 // number of vars : 2 // block 1 : ordering dp // : names T(3) T(4) // block 2 : ordering C [2]:[1]: _[1]=f9^5*f8^3 _[2]=f9^3*f8^4-f9^4*f8 _[3]=f9^2*f8^5-f9^3*f8^2 _[4]=f8^8-2*f9*f8^5+f9^2*f8^2 _[5]=f9^6 [3]:[1]:22 [2]:22 > def R23=nor23[1][1]; > setring R23; > normap; normap[1]=T(3)^6-T(3)*T(4)^2 normap[2]=T(3)^2 > norid; norid[1]=T(3)^17-3*T(3)^12*T(4)^2+3*T(3)^7*T(4)^4-T(3)^7*T(4) -T(3)^2*T(4)^6+T(3)^2*T(4)^3 norid[2]=T(3)^15-3*T(3)^10*T(4)^2+3*T(3)^5*T(4)^4-T(3)^5*T(4) -T(4)^6+T(4)^3 norid[3]=T(3)^10-2*T(3)^5*T(4)^2+T(4)^4-T(4) norid[4]=T(3)^12-2*T(3)^7*T(4)^2+T(3)^2*T(4)^4-T(3)^2*T(4) norid[5]=T(3)^11*T(4)-2*T(3)^6*T(4)^3+T(3)*T(4)^5-T(3)*T(4)^2 norid[6]=T(3)^12*T(4)-2*T(3)^7*T(4)^3+T(3)^2*T(4)^5-T(3)^2*T(4)^2 norid[7]=T(3)^10*T(4)-2*T(3)^5*T(4)^3+T(4)^5-T(4)^2 norid[8]=T(3)^11-2*T(3)^6*T(4)^2+T(3)*T(4)^4-T(3)*T(4) norid[9]=T(3)^48-8*T(3)^43*T(4)^2+5*T(3)^38*T(4)^4-10*T(3)^33*T(4)^6 +T(3)^28*T(4)^8-10*T(3)^23*T(4)^10+5*T(3)^18*T(4)^12 -8*T(3)^13*T(4)^14+T(3)^8*T(4)^16-T(3)^8*T(4)^4 \end{verbatim} Edit this to get at least: \begin{verbatim} > ideal j23=interred(norid);j23; j23[1]=T(3)^10-2*T(3)^5*T(4)^2+T(4)^4-T(4) \end{verbatim} While not technically wrong, this is not type I, using functions of weights 4 and 10, obscuring the function \begin{verbatim}T(3)^5-T(4)^2\end{verbatim} of weight 5, recoverable by hand from normap and the origianl weights. This also took several (7 seconds ?) as compared to almost 0 for normal. \newpage For Macaulay2's integralClosure function, the following in characteristic 23 took about 57 seconds: \begin{verbatim} Macaulay 2, version 1.2 with packages: Elimination, IntegralClosure, LLLBases, PrimaryDecomposition, ReesAlgebra, SchurRings, TangentCone i1 : R=ZZ/23[y,x,MonomialOrder=>{Weights=>{9,8}}] o1 = R o1 : PolynomialRing i2 : I=ideal(y^8-x^9+2*y*x^6-y^2*x^3) 9 8 6 2 3 o2 = ideal(- x + y + 2y*x - y x ) o2 : Ideal of R i3 : S=R/I o3 = S o3 : QuotientRing i4 : P=presentation(integralClosure(S)) o4 = | -8w_21^18-10w_21^13w_19-5w_21^8w_19^2-3w_21^3w_19^3-5w_21^3w_13+8w_21^3 -6w_21^36+7w_21^31w_19-5w_21^26w_19^2+3w_21^21w_19^3+w_21^16w_19^4-8w_21^ 11w_19^5-4w_21^6w_19^6-8w_21^6w_13-9w_21^6+4w_21w_19w_13-4w_21w_19 -w_21^20-3w_21^15w_19+9w_21^10w_19^2+4w_21^5w_19^3+6w_21^5-3w_19w_13+3w_19 -10w_21^24-5w_21^19w_19-11w_21^14w_19^2+w_21^9w_19^3-9w_21^9-5w_21^4w_19^4+ 5w_21^4w_19 -w_21^30-10w_21^25w_19-7w_21^20w_19^2-3w_21^10w_19^4-9w_21^10w_ 19+w_21^5w_19^5-4w_21^5w_19^2+10w_13^2-3w_13-7 4w_21^16+6w_21^11w_19+2w_21^6w_19^2+w_21w_13^2+2w_21w_13-3w_21 -3w_21^16+2w_21^11w_19+w_21^6w_19^2-4w_21w_19^3+w_21w_13+3w_21 -7w_21^30+5w_21^25w_19+2w_21^15w_19^3+6w_21^10w_19^4+10w_21^5w_19^5+w_19^3+ 8w_13^2+10w_13+4 | ZZ 1 ZZ 8 o4 : Matrix (--[w , w , w ]) <--- (--[w , w , w ]) 23 21 19 13 23 21 19 13 \end{verbatim} I don't have a clue what $w_{21}$, $w_{19}$, and $w_{13}$ are. (Well actually I do, but it takes a while to realize what the underlying variables of weights 5 and 4 are given that these seem to have weights 4,20,30, respectively.) Over the rationals, we get a segmentation fault without explanation: \begin{verbatim} i5 : R=QQ[y,x,MonomialOrder=>{Weights=>{9,8}}] o5 = R o5 : PolynomialRing i6 : I=ideal(y^8-x^9+2*y*x^6-y^2*x^3) 9 8 6 2 3 o6 = ideal(- x + y + 2y*x - y x ) o6 : Ideal of R i7 : S=R/I o7 = S o7 : QuotientRing i8 : P=presentation(integralClosure(S)) Segmentation fault \end{verbatim} \newpage However, a slightly different weighted ordering gave functions $w_{12}$ and $w_{21}$, which seem to have weights $10$ and $214$ respectively. Is it technically correct? Who cares, it's unuseable. \begin{verbatim} Macaulay 2, version 1.2 i1 : R=QQ[y,x,MonomialOrder=>{Weights=>{1,0},Weights=>{9,8}}] i2 : I=ideal(y^8-y^2*x^3+2*y*x^6-x^9) i3 : S=R/I i4 : P=presentation(integralClosure(S)) o4 = | w_12x+y2 w_12^4+w_12+2yx2-x5 w_21y-w_21x3-1081344y7x20-170879609y7x5-131072y6x23-121595564y6x8 -82185824y5x11-52162688y4x14-30607616y3x17-16237568y2x20-6447104yx23 +170879609yx8-4915200x26-242543225x11 w_21w_12+w_21x5+1212416y7x22+292475173y7x7+131072y6x25+203781388y6x10 +134348512y5x13+82770304y4x16+46845184y3x19+23766016y2x22+9199616yx25 -270095602yx10+5996544x28+413422834x13 1/16w_21x10-4478976w_12^3y+75776y7x27+485031173/16y7x12+8192y6x30 +785378914y6x15+4478976y6+12034750y5x18+4478976y5x3+6898136y4x21 +4478976y4x6+3637968y3x24+4478976y3x9+1724992y2x27+4478976y2x12 +634368yx30-41336755716yx15-4478976y+382976x33+363787199/8x18+4478976x3 w_21^2+915068146w_21x8+5135673858195456w_12^2y2-14897094066176y7x40 -34882274382381056y7x25+105478940990177280y7x10-2457795035136y6x43 -17257712991469568y6x28+47830470225138383y6x13-283467841536y5x46 -7921828254711808y5x31+10788557782417768y5x16+10271347716390912y5x -17179869184y4x49-3379096102895616y4x34-10047629647321680y4x19 +15407021574586368y4x4-1333755302117376y3x37-19074611143191040y3x22 +20542695432781824y3x7-480288593412096y2x40-20366017330041344y2x25 +25678369290977280y2x10-139939295526912yx43+17496468923039744yx28 -74664897841004544yx13-70864544464896x46-65287053192339456x31 +199077128762584369x16-5135673858195456x | 1 6 o4 : Matrix (QQ[w , w , y, x]) <--- (QQ[w , w , y, x] 21 12 21 12 \end{verbatim} I'm not even going to waste my time trying to figure out what $w_{21}$ and $w_{12}$ are supposed to be.