; G:=GroebnerBasis(I);G; JM:=JacobianMatrix(G);JM; M:=Minors(JM,1);M; J:=ideal

;
B:=GroebnerBasis(J);
delta:=B[#B];
"delta =",delta;
factors_of_delta:= Factorization(delta); factors_of_delta;
///=====================================================================;
Q:=Integers();
P ;
N:=Normalisation(I);
J:=N[1][1];J;
"Normalisation time=",Cputime(t);
G:=GroebnerBasis(J);G;
"total time=",Cputime(t);
======
Ideal of Polynomial ring of rank 2 over Rational Field
Order: Lexicographical
Variables: $.1, $.2
Basis:
91
[
-$.1^21 + $.1^16*$.2^4 + $.1^11*$.2^5 + $.1^6*$.2^6 + $.1^6
+ $.1*$.2^7 - $.1*$.2,
-$.1^7 + $.1^2*$.2^4 + $.1^2*$.2,
-$.1^10 + 2*$.1^5*$.2 + $.2^8 - $.2^2,
-$.1^11 + $.1^6*$.2^4 + $.1*$.2^5 + $.1*$.2^2,
-$.1^12 + 2*$.1^7*$.2 + $.1^2*$.2^8 - $.1^2*$.2^2,
-$.1^11*$.2 + 2*$.1^6*$.2^2 + $.1*$.2^9 - $.1*$.2^3,
-$.1^17 + $.1^12*$.2^4 + $.1^7*$.2^5 + $.1^2*$.2^6 +
$.1^2*$.2^3,
-$.1^10*$.2^2 + 2*$.1^5*$.2^3 + $.2^10 - $.2^4,
-$.1^6 + $.1*$.2^4 + $.1*$.2,
-$.1^12*$.2^2 + 2*$.1^7*$.2^3 + $.1^2*$.2^10 - $.1^2*$.2^4,
-$.1^11*$.2^3 + 2*$.1^6*$.2^4 + $.1*$.2^11 - $.1*$.2^5,
-$.1^7*$.2 + $.1^2*$.2^5 + $.1^2*$.2^2,
-$.1^10*$.2^4 + 2*$.1^5*$.2^5 + $.2^12 - $.2^6,
-$.1^6*$.2^2 + $.1*$.2^6 + $.1*$.2^3,
-$.1^5 + $.2^4 + $.2 ]
> "Normalisation time=",Cputime(t);
Normalisation time= 0.770
> G:=GroebnerBasis(J);G;
[ $.1^5 - $.2^4 - $.2 ]
> "total time=",Cputime(t);
A Gr obner basis of Magma?s Normalisation produces a single relation (J:1)5 (J:2)4 J:2,
which is what which is what normalP with the "withRing" command should have produced.
92
6.4 Output from the qth-power algorithm
The qth-power algorithm gives a F23[x]-module presentation with the following F23[x]-
module basis, and := x13.
1 y3x12;
2 y7x7 yx10;
3 y6x8 +y7x5 +x11 yx8;
4 y2x12;
5 yx13;
6 y5x8 +y6x5 +y7x2 +x8 yx5;
7 y4x9 +y5x6 +y6x3 +y7 +x6 yx3;
8 x13
with weights [19;15;14;10;9;5;4;0]
and the following strictly F23[x]-a ne algebra presentation
[ f24 f8;
f25 f10;
f5f4 f9;
f29 f10f8;
f9f5 f14;
f9f4 f5f8;
f210 f4f28 +f5;
f10f9 f19;
f10f5 f15 1;
f10f4 f14;
f214 f4f38 +f5f8;
f14f10 f38 +f9;
f14f9 f15f8 f8;
f14f5 f19;
93
f14f4 f10f8;
f215 f14f28 + 3f15 + 2;
f15f14 f5f38 + 2f14;
f15f10 f9f28 + 2f10;
f15f9 f38 + 2f9;
f15f5 f4f28 + 2f5;
f15f4 f19 +f4;
f219 f14f38 +f15f8 +f8;
f19f15 f10f38 + 2f19;
f19f14 f9f38 +f10f8;
f19f10 f5f38 +f14;
f19f9 f4f38 +f5f8;
f19f5 f38 +f9;
f19f4 f15f8 f8 ]
where f4 := (1=x13)y4x9;f5 := (1=x13)y5x8;f9 := y;f10 := (1=x13)y2x12;f14 := (1=x13)y6x8;
f15 := (1=x13)y7x7;f19 := (1=x13)y3x12;f8 := x.
It is important to note here that if we look at the weights, [19;15;14;10;9;5;4;0], it is
possible to extract a minimized answer using f4;f5;f10, and f15, a weighted F23[f4]-module
version of what Normalisation produced, what normalP(i,"withRing") and icFracP should
have produced.
94
Chapter 7
Speed-up techniques
In this chapter, we present some approaches in doing computations that are very time
e cient. It is not standard for computer algebra systems to have code to compute NF(fq;I)
e ciently. So while computing fq in characteristic q may be easy, reducing it mod I may be
very dense and costly in terms of time and/or storage.
Therefore it is wise to write code for repeatedly squaring and reducing mod I, a well-known
strategy for dealing with exponentiating and reducing large objects in general. The following
code and examples show the computational necessity of this approach. The rst technique
speeds up some necessary normal form computations in some existing computational algebra
packages.
7.1 Normal Form, NF(fq;I)
Let f be an element in a polynomial ring P. Let I be an ideal in P, and q be a prime.
We want to compute the normal form of fq modulo the ideal I . That is, we want to compute
NF(fq;I), using the built-in Magma command.
(a) Less e cient approach: An ine cient approach to compute NF(fq;I) is to mind-
lessly raise f to the q and then take its normal form modulo I. The approach is very slow
and very ine cient, since we may be taking the normal form of a polynomial of very large
degree.
(b) E cient approach and why it works: We note that the normal form operation is
very dense and takes much time for polynomials of very large degree. A more e cient ap-
proach considered here is to start with the normal form of f modulo the ideal I and then
repeatedly square and reduce the resulting normal form modulo the ideal I. This means we
95
are only taking the normal form of a polynomial of very small degree every time.
Below are two pieces of code that implement the above approaches.
Code for approach (a).
METHOD ONE
//////////// normal form function ///////////////
slow_normal_form:=function(q,f,I)
nf_time:=Cputime();
b:= NormalForm(f^q,I);
bb:= Cputime(nf_time);
return q,b,f,I, bb; /////////////
end function;
/////////////////////////////////////////////////////
Code for approach (b).
METHOD TWO
//////////////////////////////////////////////
fast_normal_form:=function(q,f,I)
nfg_time:=Cputime();
if g eq 0 then
return 0;
else
t:=q;
prd:=1;
temp:=NormalForm(f,I);
repeat
rem:=t mod 2;
t div:=2;
96
if rem eq 1 then
prd *:=temp;
end if;
if t ne 0 then
temp:=NormalForm(temp^2,I);
end if;
until t eq 0;
a:= NormalForm(prd,I);
aa:=Cputime(nfg_time);
return q, a, f, I, aa;
end if;
end function;
///////////////////////////////////////////////////
Here are timings for the two di erent approaches over a polynomial ring Fq[y;x]; y grevlex
x, and a polynomial f = y5, for various primes q, and ideals Iq generated by the polynomial
gq(y;x) = q1y6 + q2x11 + q3y3x4 + q4y5 + q5y4x + q6y2x4 + q7y4 + q8yx5 + q9y3x + q10y2x2 +
q11y3 +q12y2x+q13yx2 +q14x3 with each qi2Fq. The timings clearly indicate that approach
(b) is more e cient.
97
Table 7.1: Timing normal forms
prime, q Method#2 Method#1
5 0.000 0.000
7 0.000 0.000
11 0.000 0.010
13 0.010 0.020
17 0.020 0.040
19 0.030 0.060
23 0.080 0.110
29 0.130 0.260
31 0.210 0.330
37 0.140 0.560
41 0.180 0.780
43 0.280 0.920
47 0.450 1.210
53 0.430 1.790
59 0.770 2.540
61 0.840 2.840
73 0.540 5.040
79 1.180 6.490
83 1.010 7.560
89 1.210 9.460
97 0.900 12.350
101 1.500 13.850
113 1.930 19.340
193 3.600 102.280
257 5.140 245.670
307 17.800 395.830
353 17.680 600.370
541 53.160 2194.400
547 39.020 2275.170
7.2 Extended Euclidean algorithm
Below is our extended Euclidean division algorithm code.
/////////////////// EXTENDED DIVISION FUNCTION ///////
//////////////////////////////////////////////////////////////
EEDXGCD:= function(F,n,P,f,g,i)
98
FF:=FunctionField(F,n);
hP:=hom* 0 as follows;
P1 P2 P3 P4
div(x2 1) = 2 0 1 1
div(x2 + 1) = 2 2 0 0
div(x1 1) = 1 1 2 0
div(x1 + 1) = 1 1 0 2
For the second level the divisors are
div(x3 1) = 4 0 2 1 1
div(x3 + 1) = 4 4 0 0 0
div(x2 1) = 2 2 0 2 2
div(x2 + 1) = 2 2 4 0 0
div(x1 1) = 1 1 2 4 0
div(x1 + 1) = 1 2 1 0 4
117
We now generalize the above for any level, n, of the tower.
P1 P2 P3 P4 ::: Pn Pn+1 Pn+2 Pn+3
(xn+1 1) = 2n 0 2n 1 2n 2 ::: 4 2 1 1
(xn+1 + 1) = 2n 2n 0 0 ::: 0 0 0 0
(xn 1) = 2n 1 2n 1 0 2n 1 ::: 8 4 2 2
(xn + 1) = 2n 1 2n 1 2n 0 ::: 0 0 0 0
(xn 1 1) = 2n 2 2n 2 2n 1 0 ::: 16 8 4 4
(xn 1 + 1) = 2n 2 2n 2 2n 1 2n ::: 0 0 0 0
... = ... ... ... ... ... ... ... ... ...
(x3 1) = 4 4 8 16 ::: 2n 0 0 0
(x3 + 1) = 4 4 8 16 ::: 0 2n 1 2n 2 2n 2
(x2 1) = 2 2 4 8 ::: 2n 1 2n 0 0
(x2 + 1) = 2 2 4 8 ::: 2n 1 0 2n 1 2n 1
(x1 1) = 1 1 2 4 ::: 2n 2 2n 1 2n 0
(x1 + 1) = 1 1 2 4 ::: 2n 2 2n 1 0 2n
The following change of variables
x2qm+Pmj=i 2(j 1) = (xm+1 + 1)
m 1Y
j=i
(xj + 1); 1 i m; (8.24)
puts equation ( 8.23) into type I form. Let GF[3] represent the nite eld of characteristic
3.
Take m = 2; and with respect to the pole orders, de ne
y4 := x3 + 1; y6 := x2 + 1(x1 + 1); y7 := (x1 + 1)(x2 + 1)(x3 + 1):
118
From equation ( 8.23) we have the following type I integral equations.
y26 +y6y4 +y34 + 2y24 +y4 = 0
y27 +y7y6 + 2y6y24 +y6y4 + 2y6 + 2y34 +y24 + 2y4 = 0
Take m = 3; and with respect to the pole orders, de ne y8 := x4 + 1; y12 := (x3 + 1)(x4 +
1); y14 := (x2 + 1)(x3 + 1)(x4 + 1);
y15 := (x1 + 1)(x2 + 1)(x3 + 1)(x4 + 1): From equation ( 8.23) we have the following type I
integral equations.
y212 +y12y8 +y38 + 2y28 +y8 = 0
y214 +y14y12 + 2y12y28 +y12y8 + 2y12 + 2y38 +y28 + 2y8 = 0
y215 +y15y14 + 2y14y12 +y14y28 +y14y8 +y14 +y12y28 + 2y12y8 +y12 +y38 + 2y28 +y8 = 0
119
Bibliography
[1] D. A. Leonard and R. Pellikaan, \Integral Closures and weight functions over nite
Fields", Finite Fields and Their Applications, 9:479-504, 2003.
[2] A. Taylor, \Methods for Computing Normalisations of A ne Rings", Advances in al-
gebra and geometry, (Hyderabad, 2001), 279-295, Hindustan Book Agency, New Delhi,
2003.
[3] D. A. Leonard, \Finding the de ning functions for one-point algebraic-geometry codes",
IEEE Transactions on information theory, VOL.47, NO.6, 2566-2573, 2001.
[4] D. A. Leonard, \A weighted module view of integral closures of a ne domians of type
I", Advances in mathematics of communications, volume 3, No.1, 1-11, 2009.
[5] D. A. Leonard, \ Addentum to A weighted module view of integral clo-
sures of a ne domians of type I", http://www.dms.auburn.edu/ leon-
ada/downloads/addendum02102009.pdf.
[6] P. Olav, and R. Pellikan, \On the structure of order domains", Finite Fields and Their
Applications, 8:369-396, 2002.
[7] G-M. Greuel, S. Laplagne, and F. Seelisch, \Normalization of Rings",
arXiv:0904.3561v1 [math.AC], Submitted on 22 Apr 2009.
[8] A. K. Singh, and I. Swanson, \An algorithm for computing the integral closure",
Commutative Algebra (math.AC) arXiv:0901.0871v1 [math.AC] Submitted on 7 Jan
2009
[9] T. De Jong, \An Algorithm for computing the integral closure", J. Symbolic compu-
tation, 26: 273-277, 1998.
[10] \The MAGMA Computational Algebra System for Algebra, Number The-
ory and Geometry", The University of Sydney Computational Algebra Group,
http://magma.maths.usyd.edu.au/magma.
[11] D. R. Grayson, and M. E. Stillman, \MACAULAY 2, a software system for research
in algebraic geometry", Available at http://www.math.uiuc.edu/Macaulay2/.
[12] G. M. Greuel, G. P ster, and H. Sch onemann, \ SINGULAR 3-1-0. A computer
algebra system for polynomial computations", Center for computer algebra, University
of Kaiserslautern, (2009), http://www.singular.uni-kl.de.
120
[13] D. Cox, J. Little, and D. O?Shea, \Ideals, varieties, and algorithms. An introduction
to computational algebraic geometry and commutative algebra", Springer, third edition
(2007).
[14] D. Eisenbud, \Commutative algebra with a view toward algebraic geometry", Springer-
Verlag, (1995).
[15] G. M. Greuel, and G. P ster, \A Singular Introduction to commutative algebra",
Springer-Verlag Berlin Heidelberg New York, (2002).
[16] P. Beelen, A. Garcia, and H. Stichenoth, \Towrads a classi cation of recursive towers of
function elds over nite elds", Finite Fields and Their Applications, 12: 56-77, 2006.
[17] A. Garcia, and H. Stichenoth, \Asymtotics for the genus and the number of rational
places in towers of function elds over a nite eld", Finite Fields and Their Applica-
tions, 11: 434-450, 2005.
[18] P. Beelen, A. Garcia, and H. Stichenoth \On towers of elds of Artin-Schreier type",
Bull Braz Math Soc, new series 35(2) : 151-164, 2004.
[19] S. Ling, H. Stichenoth, and S. Yang, \A class of Artin-Schreier towers with nite
genus", Bull Braz Math Soc, new series 36(3) : 393-401, 2005.
[20] A. Bassa, and H. Stichenoth, \A simpli ed proof for the limit of a tower over a cubic
nite led", Journal of number theory, vol 123, : 154-169, 2007.
[21] A. Garcia, and H. Stichenoth, \On the asymptotic behaviour of some towers of function
elds over nite leds", Journal of number theory, vol 61, : 248-273, 1996.
[22] A. Garcia, H. Stichenoth, and M. Thomas, \On towers and composita of towers of
function elds over nite elds", Finite Fields and Their Applications, 3: 257-274,
1997.
[23] G.L. Feng, T.R.N. Rao, \A simple approach for the construction of algebraic-geometric
codes from a ne plane curves", IEEE Trans. Inform. Theory, 40 (3): 1003-1012, 1994.
[24] K. Saints, C. Heegard, \Algebraic-Geometric codes and multidimensional cyclic codes:
a uni ed theory and algorithms for decoding using Gr obner bases", IEEE Trans. Inform.
Theory, 41 (6): 1753-1761, 1995.
[25] N. Elkies, \Explicit modular towers", Proceedings of the Thirty-Fifth [1997] Annual
Allerton Conference on Communication, Control and Computing, math/0103107v1
[math.NT] 16 Mar 2001.
[26] J. V. Z. Gathen, J. Gerhard, \Introduction to nite elds and their applications",
Cambridge University Press, 2 edition, 2003.
[27] B. Buchberger, F. Winkler, \Gr obner bases and Applicationsociety", London Mathe-
matical Society. Lecture Note Series 251, Cambridge University Press, 1st edition, 1998.
121
[28] C. Huneke, I. Swanson, \Integral closure of ideals, rings, and modules", London
Mathematical Society. Lecture Note Series 336, Cambridge University Press, 2006.
[29] H. Niederreiter, C. Xing, \Rational points on curves over nite elds. Theory and
applications", London Mathematical Society. Lecture Note Series 285, Cambridge Uni-
versity Press, 1st edition, 2001.
[30] D. Dummit, R. M. Foote, \Abstract Algebra" John Wiley and Sons, Inc, 3rd edition,
2004.
[31] R. Lidl, H. Niederreiter, \Introduction to nite elds and their applications", Cambridge
University Press, 1986.
[32] M. Nagata, \Theory commutative elds", Translations Mathematical monographs, vol-
ume 125, 1993.
[33] H. Stichtenoth, \Algebraic function elds and codes", Springer-Verlag Berlinn Heidel-
berg, 1993.
[34] R. Lidl, H. Niederreiter, \Finite elds", Encyclopedia of Mathematics and its applica-
tion, Addison-Wesley Publishing Company, 20, Algebra, 1986.
122
*