\documentclass{article} \usepackage{amssymb} \usepackage{amsmath} \usepackage{url} \urlstyle{same} \def\ul{\underline} \def\ov{\overline} \begin{document} \begin{center}{\Large Annotated Examples 4}\end{center} \begin{center}{\large Generic example similar to example 3\\ but with rational numbers to reconstruct}\end{center} This is almost like example 3, except that there are non-trivial rational numbers occurring as coefficients. So my algorithm must reconstruct these. Clearly one can't even read these in characteristic 2 or 17 because some denomiators vanish there. But there are a handful of characteristics, including 3 and 5, to avoid, mostly because the integral closure is slightly larger than what ones gets by specializing the result from characteristic 0. \[ \mathbf{F}[y;x]/\langle (y^2-\frac{3}{4}y-\frac{15}{17}x)^3-9yx^4(y^2-\frac{3}{4}y-\frac{15}{17}x)-27x^{11}\rangle\] My qth-power algorithm reconstructs the answer over the rationals from answers in characteristics 7,11,13,19,23,29, and 31, with this whole ``wasteful'' process still taking only about 3 seconds: \begin{verbatim} Loading file "qchar051109.mag" Loading "closure_func040909.mag" 1111111111111111111111111111111111111111111111111111111111 q= 3 Delta= 0 bad prime= 3 1111111111111111111111111111111111111111111111111111111111 q= 5 Delta= S.2^11 WT_MATRIX_T= [ [ 20, 15, 13, 11, 10, 6 ] ] time for q= 5 is 0.030 seconds modulus= 5 1111111111111111111111111111111111111111111111111111111111 q= 7 Delta= S.2^9 WT_MATRIX_T= [ [ 25, 21, 20, 11, 10, 6 ] ] time for q= 7 is 0.100 seconds 1111111111111111111111111111111111111111111111111111111111 q= 11 Delta= S.2^9 WT_MATRIX_T= [ [ 25, 21, 20, 11, 10, 6 ] ] time for q= 11 is 0.190 seconds modulus= 77 [ f_11^4*f_6^3 + f_11^3*f_6^3 - f_11^2*f_6^3, f_11^3*f_6^4 + f_11^2*f_6^4 - f_11*f_6^4, f_11^5 + f_11^2*f_6^4 - f_11^4 - 2*f_11*f_6^4 + 2*f_11^3 + 2*f_11^2, f_11*f_6^7, f_11^2*f_6^5 - 2*f_11*f_6^5, f_6^8, f_6^7 ] 1111111111111111111111111111111111111111111111111111111111 q= 13 Delta= S.2^9 WT_MATRIX_T= [ [ 25, 21, 20, 11, 10, 6 ] ] time for q= 13 is 0.200 seconds modulus= 1001 [ f_11^5 - 1/9*f_11^4 + 1/2*f_11^3*f_6 - 6/5*f_11^3 - 3/4*f_11^2*f_6 + 5/3*f_11*f_6^2 + 8*f_11^2 - 1/5*f_11*f_6 - 5/4*f_6^2, f_11^3*f_6^3 + 1/4*f_11*f_6^4 + 2/5*f_11*f_6^3 + 5*f_6^4, f_11^4*f_6 - 3/2*f_11^3*f_6 + 1/2*f_11^2*f_6^2 - 2/5*f_11^2*f_6 - 3/8*f_11*f_6^2 + 5/3*f_6^3, f_11*f_6^5, f_11^2*f_6^3 - 3/4*f_11*f_6^3 + 1/4*f_6^4, f_6^6, f_6^5 ] 1111111111111111111111111111111111111111111111111111111111 q= 17 1111111111111111111111111111111111111111111111111111111111 q= 19 Delta= S.2^9 WT_MATRIX_T= [ [ 25, 21, 20, 11, 10, 6 ] ] time for q= 19 is 0.310 seconds modulus= 19019 [ f_11^5 - 9/4*f_11^4 - 30/17*f_11^3*f_6 + 27/16*f_11^3 + 2/23*f_11^2*f_6 + 16/25*f_11*f_6^2 - 82/9*f_11^2 + 10/27*f_11*f_6 - 12/25*f_6^2, f_11^3*f_6^3 - 15/17*f_11*f_6^4 - 9/16*f_11*f_6^3 - 1/46*f_6^4, f_11^4*f_6 - 3/2*f_11^3*f_6 - 30/17*f_11^2*f_6^2 + 9/16*f_11^2*f_6 + 1/23*f_11*f_6^2 + 16/25*f_6^3, f_11*f_6^5, f_11^2*f_6^3 - 3/4*f_11*f_6^3 - 15/17*f_6^4, f_6^6, f_6^5 ] 1111111111111111111111111111111111111111111111111111111111 q= 23 Delta= S.2^9 WT_MATRIX_T= [ [ 25, 21, 20, 11, 10, 6 ] ] time for q= 23 is 0.450 seconds modulus= 437437 [ f_11^5 - 9/4*f_11^4 - 30/17*f_11^3*f_6 + 27/16*f_11^3 + 45/17*f_11^2*f_6 - 67/83*f_11*f_6^2 - 27/64*f_11^2 - 16/157*f_11*f_6 - 9/269*f_6^2, f_11^3*f_6^3 - 15/17*f_11*f_6^4 - 9/16*f_11*f_6^3 - 45/68*f_6^4, f_11^4*f_6 - 3/2*f_11^3*f_6 - 30/17*f_11^2*f_6^2 + 9/16*f_11^2*f_6 + 45/34*f_11*f_6^2 - 67/83*f_6^3, f_11*f_6^5, f_11^2*f_6^3 - 3/4*f_11*f_6^3 - 15/17*f_6^4, f_6^6, f_6^5 ] 1111111111111111111111111111111111111111111111111111111111 q= 29 Delta= S.2^9 WT_MATRIX_T= [ [ 25, 21, 20, 11, 10, 6 ] ] time for q= 29 is 0.680 seconds modulus= 12685673 [ f_11^5 - 9/4*f_11^4 - 30/17*f_11^3*f_6 + 27/16*f_11^3 + 45/17*f_11^2*f_6 + 225/289*f_11*f_6^2 - 27/64*f_11^2 - 135/136*f_11*f_6 - 51/7864*f_6^2, f_11^3*f_6^3 - 15/17*f_11*f_6^4 - 9/16*f_11*f_6^3 - 45/68*f_6^4, f_11^4*f_6 - 3/2*f_11^3*f_6 - 30/17*f_11^2*f_6^2 + 9/16*f_11^2*f_6 + 45/34*f_11*f_6^2 + 225/289*f_6^3, f_11*f_6^5, f_11^2*f_6^3 - 3/4*f_11*f_6^3 - 15/17*f_6^4, f_6^6, f_6^5 ] 1111111111111111111111111111111111111111111111111111111111 q= 31 Delta= S.2^9 WT_MATRIX_T= [ [ 25, 21, 20, 11, 10, 6 ] ] time for q= 31 is 0.880 seconds modulus= 393255863 [ f_11^5 - 9/4*f_11^4 - 30/17*f_11^3*f_6 + 27/16*f_11^3 + 45/17*f_11^2*f_6 + 225/289*f_11*f_6^2 - 27/64*f_11^2 - 135/136*f_11*f_6 - 675/1156*f_6^2, f_11^3*f_6^3 - 15/17*f_11*f_6^4 - 9/16*f_11*f_6^3 - 45/68*f_6^4, f_11^4*f_6 - 3/2*f_11^3*f_6 - 30/17*f_11^2*f_6^2 + 9/16*f_11^2*f_6 + 45/34*f_11*f_6^2 + 225/289*f_6^3, f_11*f_6^5, f_11^2*f_6^3 - 3/4*f_11*f_6^3 - 15/17*f_6^4, f_6^6, f_6^5 ] 1 f_11^5 - 9/4*f_11^4 - 30/17*f_11^3*f_6 + 27/16*f_11^3 + 45/17*f_11^2*f_6 + 225/289*f_11*f_6^2 - 27/64*f_11^2 - 135/136*f_11*f_6 - 675/1156*f_6^2 2 f_11^3*f_6^3 - 15/17*f_11*f_6^4 - 9/16*f_11*f_6^3 - 45/68*f_6^4 3 f_11^4*f_6 - 3/2*f_11^3*f_6 - 30/17*f_11^2*f_6^2 + 9/16*f_11^2*f_6 + 45/34*f_11*f_6^2 + 225/289*f_6^3 4 f_11*f_6^5 5 f_11^2*f_6^3 - 3/4*f_11*f_6^3 - 15/17*f_6^4 6 f_6^6 7 f_6^5 newrelations= [ f_10^2 - f_20, f_11^2 - f_10*f_6^2 - 3/4*f_11 - 15/17*f_6, f_11*f_10 - f_21 + 3/4*f_10, f_20^2 - 27*f_10*f_6^5 - 9*f_25*f_6 - 27/4*f_20 + 616/17751*f_11*f_6, f_20*f_11 - f_25*f_6 - 3/4*f_20 + 19712/5069*f_11*f_6, f_20*f_10 - 27*f_6^5 - 9*f_21 + 27/4*f_10, f_21^2 - 27*f_6^7 - 9*f_21*f_6^2 - 9/4*f_25*f_6 - 15/17*f_20*f_6 + 27/4*f_10*f_6^2 - 9/4*f_20 + 154/17751*f_11*f_6, f_21*f_20 - 27*f_11*f_6^5 - 9*f_20*f_6^2 - 81/4*f_6^5 - 27/2*f_21 - 135/17*f_10*f_6 + 81/8*f_10, f_21*f_11 - f_20*f_6^2 - 3/2*f_21 - 15/17*f_10*f_6 + 9/8*f_10, f_21*f_10 - f_25*f_6 - 3/2*f_20 + 19712/5069*f_11*f_6, f_25^2 - 27*f_20*f_6^5 - 243*f_11*f_6^5 + 81/4*f_21*f_6^3 - 1232/5917*f_6^6 - 405/17*f_10*f_6^4 - 81*f_20*f_6^2 + 729/4*f_6^5 - 243/8*f_10*f_6^3 - 22561/5864*f_21*f_6 - 135/17*f_25 + 20251/10908*f_10*f_6^2 + 2541/73445*f_20 + 12521/13291*f_10*f_6 - 1617/40844*f_11 - 9163/2174*f_6, f_25*f_21 - 27*f_10*f_6^6 - 9*f_25*f_6^2 - 81/4*f_11*f_6^4 - 19712/5069*f_20*f_6^2 - 405/17*f_6^5 - 27/2*f_20*f_6 + 243/16*f_6^4 + 616/17751*f_11*f_6^2 + 5717/61540*f_21 + 2541/146890*f_10*f_6 + 22176/5069*f_10, f_25*f_20 - 27*f_21*f_6^4 - 243*f_6^6 + 81/2*f_10*f_6^4 - 19712/5069*f_25*f_6 - 81*f_21*f_6 + 5953/20467*f_20 - 20251/10908*f_11*f_6 + 243/4*f_10*f_6, f_25*f_11 - 27*f_6^6 - 9*f_21*f_6 - 19712/5069*f_10*f_6^2 - 15/17*f_20 + 27/4*f_10*f_6 - 14784/5069*f_11 + 2541/146890*f_6, f_25*f_10 - 27*f_11*f_6^4 - 9*f_20*f_6 + 81/4*f_6^4 - 19712/5069*f_21 + 5007/42599*f_10 ] totaltime= 2.900 seconds \end{verbatim} \newpage MAGMA gives $\mathbf{F}[f_6]$-module bases: \begin{verbatim} Loading file "116" 1 1 2 Y 3 1/X^2*Y^2 - 3/4/X^2*Y - 15/17/X 4 1/X^2*Y^3 + (-15/17*X - 9/16)/X^2*Y - 45/68/X 5 1/X^4*Y^4 - 3/2/X^4*Y^3 + (-30/17*X + 9/16)/X^4*Y^2 + 45/34/X^3*Y + 225/289/X^2 6 1/X^5*Y^5 - 9/4/X^5*Y^4 + (-30/17*X + 27/16)/X^5*Y^3 + (45/17*X - 27/64)/X^5*Y^2 + (225/289*X - 135/136)/X^4*Y - 675/1156/X^3 time for char=0 is 0.040 1 1 2 Y 3 1/X^2*Y^2 + 5/X^2*Y + 14/X 4 1/X^2*Y^3 + (14*X + 21)/X^2*Y + 22/X 5 1/X^4*Y^4 + 10/X^4*Y^3 + (5*X + 2)/X^4*Y^2 + 2/X^3*Y + 12/X^2 6 1/X^5*Y^5 + 15/X^5*Y^4 + (5*X + 6)/X^5*Y^3 + (4*X + 10)/X^5*Y^2 + (12*X + 10)/X^4*Y + 14/X^3 time for char=23 is 0.030 \end{verbatim} Both have implicit weights (0,11,10,21,20,25), as for the qth-power algorithm above. \newpage SINGULAR's normal function, while getting this technically correct, allows large integers to creep into the answer. \begin{verbatim} > ring r0=0,(y,x),dp; > ideal i0=(y^2-3/4*y-15/17*x)^3-9*y*x^4*(y^2-3/4*y-15/17*x)-27*x^11; > list nor0=normal(i0); > nor0; [1]:[1]: // characteristic : 0 // number of vars : 5 // block 1 : ordering dp // : names T(1) T(2) T(3) // block 2 : ordering dp // : names y x // block 3 : ordering C [2]:[1]: _[1]=68y2x3-51yx3-60x4 _[2]=4624y4x-6936y3x-8160y2x2+2601y2x+6120yx2+3600x3 _[3]=18496y5-41616y4-32640y3x+31212y3+48960y2x+14400yx2 -7803y2-18360yx-10800x2 _[4]=x5 > def R0=nor0[1][1]; > setring R0; > normap; normap[1]=y normap[2]=x > norid; norid[1]=4*T(2)*y-3*T(2)-T(3)*x norid[2]=-T(1)*x^2+68*y^2-51*y-60*x norid[3]=68*T(1)*y^2-51*T(1)*y-60*T(1)*x-T(2)*x^2 norid[4]=41616*T(1)*y*x+60*T(2)-17*T(3)*y+8489664*x^6 norid[5]=8489664*T(1)*x^8+31212*T(2)*x^3-3600*T(2)*x+10404*T(3)*x^4 -1156*T(3)*y^3+867*T(3)*y^2+2040*T(3)*y*x norid[6]=8489664*T(2)*x^10-1872720*T(2)*x^4+216000*T(2)*x^2 +707472*T(3)*y^2*x^4-78608*T(3)*y^5-624240*T(3)*x^5 +117912*T(3)*y^4+208080*T(3)*y^3*x-44217*T(3)*y^3 -156060*T(3)*y^2*x-183600*T(3)*y*x^2 norid[7]=T(1)^2-T(2) norid[8]=T(1)*T(2)-13872*T(1)*y*x^3+10404*T(1)*x^3-41616*T(1)*y -8489664*x^5+943296*y^3*x-1414944*y^2*x-832320*y*x^2 +530604*y*x+624240*x^2 norid[9]=T(2)^2-8489664*T(1)*x^5-31212*T(2)-10404*T(3)*x norid[10]=T(1)*T(3)-146880*T(1)-2448*T(2)*x-33958656*y*x^4+25468992*x^4 norid[11]=T(2)*T(3)-33958656*T(1)*y*x^4-41616*T(3)*y+1731891456*y^2*x^2 -1298918592*y*x^2-1528139520*x^3 norid[12]=T(3)^2-135834624*T(1)*y^2*x^3+203751936*T(1)*y*x^3 -119854080*T(1)*x^4-76406976*T(1)*x^3-407503872*T(1)*y^2 +305627904*T(1)*y-146880*T(3)-83130789888*y*x^5+62348092416*x^5 +8150077440*y^2*x^2-6112558080*y*x^2-7191244800*x^3 norid[13]=8489664*x^11+2829888*y^3*x^4-314432*y^6-2122416*y^2*x^4 -2496960*y*x^5+707472*y^5+832320*y^4*x-530604*y^4-1248480*y^3*x -734400*y^2*x^2+132651*y^3+468180*y^2*x+550800*y*x^2+216000*x^3 \end{verbatim} as well as being one variable (T(1)y) short of a module basis. SINGULAR's normalP takes far too long to even produce fractions in this problem. (Remember that the qth-power algorithm above had to produce said fractions for $q=7,11,13,19,23,29,31$, and did that in less than 3 seconds, whereas normalp runs for who knows how long. Macaulay2's integralClosure used not to be up to this at all. But now: \begin{verbatim} i31 : R=QQ[y,x] i33 : I=ideal((y^2-3/4*y-15/17*x)^3-9*y*x^4*(y^2-3/4*y-15/17*x)-27*x^11) i34 : S=R/I i35 : time P=presentation(integralClosure(S)) -- used 0.48 seconds o35 = | w_(3,0)x2-68y2+51y+60x w_(3,0)^3-41616w_(3,0)y-8489664x5 w_(4,0)x-4w_(3,0)^2y+3w_(3,0)^2 17w_(4,0)y-60w_(3,0)^2-41616w_(3,0)yx-8489664x6 w_(4,0)w_(3,0)-2448w_(3,0)^2x-146880w_(3,0)-33958656yx4+25468992x4 w_(4,0)^2-146880w_(4,0)-407503872w_(3,0)y2+305627904w_(3,0)y -83130789888yx5-9236754432y4x+62348092416x5+20782697472y3x +8150077440y2x2-15587023104y2x-12225116160yx2+3896755776yx +4584418560x2 | \end{verbatim} This shows a prediliction away from fractions, but is at least a reasonable result otherwise. In moderate positive characteristic: \begin{verbatim} i1 : R=ZZ/23[y,x]; i2 : I=ideal((y^2-3/4*y-15/17*x)^3-9*y*x^4*(y^2-3/4*y-15/17*x)-27*x^11); i3 : S=R/I; i4 : time P=presentation(integralClosure(S)) -- used 0.4 seconds o4 = | w_(3,0)x2-y2-5y+9x w_(3,0)^3-9w_(3,0)y-4x5 w_(4,0)x-w_(3,0)^2y-5w_(3,0)^2 w_(4,0)y-9w_(3,0)^2-9w_(3,0)yx-4x6 w_(4,0)w_(3,0)-9w_(3,0)^2x+11w_(3,0)-4yx4+3x4 w_(4,0)^2+11w_(4,0)+11w_(3,0)y2+9w_(3,0)y+10yx5-4y4x +4x5+9y3x-10y2x2-y2x-8yx2+6yx+3x2 | i5 : time F=icFracP(S) \end{verbatim} the standard result is consistent with that in char 0, but icFracP is still amazingly slow. \newpage MAGMA's Normalisation gives: \begin{verbatim} -J.1^2*J.2-15/17*J.1+J.3^2-3/4*J.3, -J.1^2*J.2^2-15/17*J.1*J.2+J.2*J.3^2-3/4*J.2*J.3, -J.1*J.4+J.2^2*J.3-3/4*J.2^2, -27*J.1^6-9*J.1*J.2*J.3-15/17*J.2^2+J.3*J.4, -27*J.1^5+J.2^3-9*J.2*J.3, -27*J.1^4*J.3+81/4*J.1^4-9*J.1*J.2^2+J.2*J.4-135/17*J.2, -27*J.1^7-9*J.1^2*J.2*J.3-15/17*J.1*J.2^2-9/4*J.1*J.4+J.2^2*J.3^2 +3/2*J.2^2*J.3-27/16*J.2^2, -27*J.1^5*J.3-81/4*J.1^5-9*J.1^2*J.2^2-135/17*J.1*J.2+J.2^3*J.3 +3/4*J.2^3-27/2*J.2*J.3, -27*J.1^6*J.2-405/17*J.1^5-81/4*J.1^4*J.3+243/16*J.1^4-9*J.1^2*J.4 -27/2*J.1*J.2^2+J.2*J.3*J.4-135/17*J.2*J.3+3/4*J.2*J.4-405/68*J.2, -27*J.1^5*J.2-9*J.1*J.4+J.2^4-27/4*J.2^2, -243*J.1^6-27*J.1^4*J.2*J.3+81/4*J.1^4*J.2-81*J.1*J.2*J.3+J.2^2*J.4-135/17*J.2^2, -27*J.1^5*J.2^2-243*J.1^5*J.3+729/4*J.1^5-405/17*J.1^4*J.2+81/4*J.1^3*J.2*J.3 -243/16*J.1^3*J.2-81*J.1^2*J.2^2-1215/17*J.1*J.2+J.4^2-135/17*J.4 \end{verbatim} My editor doesn't really even want to open the 155MB output file containing the lex Gr\"obner basis. But again, an inspired choice: \begin{verbatim} t:=Cputime(); F:=Rationals(); P:=PolynomialRing(F,4,"grevlexw",[25,11,10,6]); f1:=-a^2*b-15/17*a+c^2-3/4*c; f2:=-a^2*b^2-15/17*a*b+b*c^2-3/4*b*c; f3:=-a*d+b^2*c-3/4*b^2; f4:=-27*a^6-9*a*b*c-15/17*b^2+c*d; f5:=-27*a^5+b^3-9*b*c; f6:=-27*a^4*c+81/4*a^4-9*a*b^2+b*d-135/17*b; f7:=-27*a^7-9*a^2*b*c-15/17*a*b^2-9/4*a*d+b^2*c^2+3/2*b^2*c-27/16*b^2; f8:=-27*a^5*c-81/4*a^5-9*a^2*b^2-135/17*a*b+b^3*c+3/4*b^3-27/2*b*c; f9:=-27*a^6*b-405/17*a^5-81/4*a^4*c+243/16*a^4-9*a^2*d-27/2*a*b^2+b*c*d-135/17*b*c+3/4*b*d-405/68*b; f10:=-27*a^5*b-9*a*d+b^4-27/4*b^2; f11:=-243*a^6-27*a^4*b*c+81/4*a^4*b-81*a*b*c+b^2*d-135/17*b^2; f12:=-27*a^5*b^2-243*a^5*c+729/4*a^5-405/17*a^4*b+81/4*a^3*b*c-243/16*a^3*b-81*a^2*b^2-1215/17*a*b+d^2-135/17*d; I:=ideal; G:=GroebnerBasis(I);G;#G; \end{verbatim} gives a readable output \begin{verbatim} d^2-27*b^2*a^5-243*c*a^5+81/4*c*b*a^3-405/17*b*a^4-81*b^2*a^2+729/4*a^5-243/16*b*a^3-135/17*d-1215/17*b*a, d*c-27*a^6-9*c*b*a-15/17*b^2, d*b-27*c*a^4-9*b^2*a+81/4*a^4-135/17*b, c*b^2-d*a-3/4*b^2, b^3-27*a^5-9*c*b, c^2-b*a^2-3/4*c-15/17*a \end{verbatim} though missing module generators $cb$ and $b^2$ of weights 21 and 20 respectively. Even reversing the order of the variables before producing a lex answer would have given: \begin{verbatim} d^2-135/17*d-b^5+9/4*b^3*a^3+27/4*b^3-405/17*b*a^4-243/16*b*a^3-243/4*a^8, d*c-b^3*a-15/17*b^2, d*b-27*c*a^4-9*b^2*a-135/17*b+81/4*a^4, d*a-1/9*b^4+3/4*b^2+3*b*a^5, c^2-3/4*c-b*a^2-15/17*a, c*b-1/9*b^3+3*a^5, c*a^5-1/243*b^5+1/36*b^3+1/9*b^2*a^5+1/3*b^2*a^2+5/17*b*a-3/4*a^5, b^6-27/4*b^4-54*b^3*a^5-81*b^3*a^2-1215/17*b^2*a+729/4*b*a^5+729*a^10 \end{verbatim} which tells me that no thought was given whatsoever as to what might constitute a reasonable monomial ordering in such problems. In particular, one should try to get inspiration from the monomial ordering of the original ring, given that the integral closure lives in its quotient ring. \end{document}