Integral Closures by Fidele Fouogang Ngwane A dissertation submitted to the Graduate Faculty of Auburn University in partial ful llment of the requirements for the Degree of Doctor of Philosophy Auburn, Alabama August 9, 2010 Keywords: Integral closure, Gr obner bases, normalization Copyright 2010 by Fidele Fouogang Ngwane Approved by: Douglas A. Leonard, Chair, Professor of Mathematics Kevin T. Phelps, Professor of Mathematics Overtoun M. Jenda, Professor of Mathematics Geraldo S. De Souza, Professor of Mathematics Abstract The qth-power algorithm from Leonard [3], [4], and Leonard and Pellikaan [1] is a recent and e cient method of computing the integral closure of a ring in its eld of fractions. Previously, the qth-power algorithm has been used to compute integral closures over nite elds. In this dissertation, we use the qth-power algorithm to compute integral closures over the rationals and number elds. ii Acknowledgments First, I am deeply grateful and indebted to my advisor Professor Douglas Leonard for directing the progress of this dissertation. He spent countless hours guiding my research, teaching me how to ask questions, how to answer them, and he introduced me to various computer algebra packages. His time, advice, regular support and encouragement were invaluable and are very much applauded. My sincere appreciation is also extended to Professors Jenda, De Souza, Phelps, and Park, for their kindness in serving on my general and nal examination committees. The faculty, sta , and students at the Auburn University, Mathematics Department provided a very cordial and supportive environment. In particular, my gratitude goes to Professors Abebe, Rodger, Slaminka, Ho man, Harris and Smith for ensuring rounded pro- fessional development. I am also very grateful to my dad Andre Ngwane, to my mum Helen Ngwane, and to my siblings for their nancial, material, family and spiritual support. Many relatives and wellwishers have made a strong impact on my life and I owe them gratitude. My source of inspiration throughout this project has been my wife Axline Sanghapi and my daughter Melissa Ngwane. I thank them for their help, support, kindness and patience. Finally, this work is joyfully dedicated to the Fountain and Source from which all good things and all true knowledge ow. iii Table of Contents Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Polynomial rings and monomial orderings . . . . . . . . . . . . . . . . . . . . 2 1.2 Ideals and Gr obner bases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.3 P-algebras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.4 Order functions and order domains . . . . . . . . . . . . . . . . . . . . . . . 7 1.5 Integral extensions and type I curves . . . . . . . . . . . . . . . . . . . . . . 9 2 Integral Closures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.1 de Jong?s algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3 The qth-power algorithm in positive characteristic . . . . . . . . . . . . . . . . . 17 3.1 qth-power algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.2 Examples of integral closures of tower extensions over nite elds via the qth-power algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 4 The qth-power algorithm over Q . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 4.1 Lifting maps from coe cient rings to polynomial rings . . . . . . . . . . . . 40 4.2 Presentations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 4.3 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 5 Integral closures of maximal order of number elds . . . . . . . . . . . . . . . . 58 5.1 Computation using the qth-power algorithm . . . . . . . . . . . . . . . . . . 58 5.2 Computation using Magma?s built-in function . . . . . . . . . . . . . . . . . 72 5.2.1 Examples using Magma . . . . . . . . . . . . . . . . . . . . . . . . . 73 iv 6 Various implementations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 6.1 Output from Singular . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 6.2 Output from Macaulay2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 6.3 Output from Magma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 6.4 Output from the qth-power algorithm . . . . . . . . . . . . . . . . . . . . . . 93 7 Speed-up techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 7.1 Normal Form, NF(fq;I) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 7.2 Extended Euclidean algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 98 7.2.1 Inverting and eliminating . . . . . . . . . . . . . . . . . . . . . . . . . 99 7.2.2 n n minors of the jacobian and conductor element computations . 102 8 Towers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 8.1 Stichenoth towers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 8.1.1 Example 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 8.1.2 Example 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 8.1.3 Example 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 8.1.4 Example 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 v List of Tables 7.1 Timing normal forms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 7.2 Timing elimination via Magma commands versus EEDXGCD command . . 102 7.3 Timing Magma commands for elimination and computation . . . . . . . 103 7.4 Timing EEGCD to do elimination andMagma commands for computation 103 7.5 Timing EEGCD function for elimination and computation . . . . . . . . . 104 vi Chapter 1 Introduction Since integral closures are important in several areas of mathematics, it is not surprising that there are many implementations of the existing integral closure algorithms. Our main goal is to understand the mathematics necessary to apply the qth-power algorithm to give a highly structured presentation of an integral closure of a ring, and to extend the qth-power algorithm to the rationals and number elds. Chapter 1 gives the basic background for our work, including several key de nitions and useful notation. Chapter two talks about integral closures and existing algorithms. Given a type I curve, say f, an integral closure algorithm produces an R module basis,ffigfor 0 i m, where m is the maximum pole order, and all functions have poles at only one point called P1. Let L(mP1) be the vector space consisting of the ffig for 0 i m. Note that L(mP1) has functions with all possible pole orders 0;:::;m except for g gaps, where g is the genus of the curve, f. Then the generator and/or parity-check functions of a one-point AG code come from the vector spaceL(mP1). Most integral closure algorithms compute the integral closure of a ring by repeatedly enlarging the ring until it stabilizes at the integral closure, as in the approach used by de Jong?s algorithm, [9]. In the next chapter, we present the qth-power algorithm. Unlike many existing al- gorithms, the qth-power algorithm uses a di erent approach, starting with a module that contains the integral closure and repeatedly reducing it to a smaller module until it stabi- lizes at the integral closure. Here we compute the integral closures of several examples of towers of rings over nite elds. 1 The qth-power algorithm is currently written for positive characteristic. Can it be ex- tended to the other elds? The answer is yes. The fourth chapter extends the qth-power algorithm to the rational eld. This is done with the help of the extended Euclidean algo- rithm and the Chinese remainder theorem. Chapter ve extends the qth-power algorithm to number elds, and presents some the- orems and examples. In chapter six we present various implementations. We discuss the outputs from various implementations. Chapter seven presents some speed-up techniques which we use in our computations. Built-in commands in some of the existing computing packages such as Magma, Macaulay2 and Singular are not very e cient. They do unnecessary computations. We have been able write thoughtful and e cient code in place of some of the built-in commands. We end this chapter with some timing illustrations of our techniques compared to built-in commands. The Final chapter focuses on towers. There are many towers that have very good coding theory properties. Unfortunately, most of these towers in their given form do not allow for evaluation at several points at which some of the variables have poles. We de ne new variables and transform these towers into type I curves. 1.1 Polynomial rings and monomial orderings A nite eld of order q, where q = pt; t>1 and p is a prime, will be denoted by Fq; F q will denote the non-zero elements of Fq. Throughout, P := F[xn;:::;x1] (written as F[x] when convenient) will denote a polynomial ring over F in n independent variables xn;:::;x1, and F will be either the rational eld , Q, a nite eld Fq, or the algebraic closure of one of these elds. Let x be shorthand for the monomial x nn x 11 , and let I denote an ideal in F[x]. Then R := F[x]=I is a quotient ring, and S := R[y]=J is a ring extension of R. We are interested in the integral closure ic(S) := R[z]=J of S, and wish to view it as an a ne P-algebra. 2 Given a polynomial ring P, we want a presentation of ic(S) relative to a nite P-module generating set y0 := 1;y1;:::;ys 1, so that J has a minimal, reduced Gr obner basis with elements of the form yiyj X k ci;j;;kyk; ci;j;k2P de ning multiplication, and possibly some elements of the form aj;iyi ai;jyj X k6=i;j bi;j;;kyk; aj;i;ai;j;bi;j;k 2 P if the P module generators are not independent over P. Given a polynomial ring F[x], let Monn := fx : 2Nng be the set of all possible monomials in P in the variable x. A global monomial ordering satis es the conditions that 1. it is a total ordering on Monn 2. it is a well-ordering on Monn 3. x x implies x x x x . The importance of a monomial ordering on P is that any polynomial has a unique represen- tation ( written from highest to lowest terms). De nition 1.1. ( See Cox et al [13] page 61.) Let f = X a x a nonzero polynomial in F[x] and let be a monomial order: 1. The multidegree of f is multidegree(f) = max( 2Zn 0 : a 6= 0) (the maximum is taken with respect to ). 2. The leading coe cient of f is LC(f) = amultideg(f)2F: 3. The leading monomial of f is LM(f) = xmultideg(f). 4. The leading term of f is LT(f) = LC(f) LM(f): We illustrate this with the following; Let f = 5x3+7x2z2+4xy2z+4z2, and let denote the monomial order. Then multideg(f) = (3;0;0); LC(f) = 5; LM(f) = x3; LT(f) = 5x3: De nition 1.2. [13]: Let = ( n;:::; 1) and = ( n;:::; 1) 2 Zn 0. We say that lex if, in the vector di erence 2Zn, the leftmost nonzero entry is positive. We 3 will write x lex x if lex : The variables xn;:::;x1 are ordered by the lex ordering (1;0;:::;0) lex (0;1;0;:::;0) lex lex (0;0;:::;0;1); so xn lex lex x1: Lexicographic order (lex) therefore orders according to the highest power of the most signif- icant indeterminate, using less signi cant indeterminates to break ties. De nition 1.3. [13]: Let = ( n;:::; 1) and = ( n;:::; 1) 2 Zn 0. We say that grevlex if, j j= nX i=1 i >j j= nX i=1 i or j j=j j and the rightmost nonzero entry of 2Zn is negative. The variablesxn;:::;x1 are ordered by the lex ordering (1;0;:::;0) grevlex (0;1;0;:::;0) grevlex ;:::; grevlex (0;0;:::;0;1), so xn grevlex;:::; grevlex x1: Graded reverse lexicographic order (grevlex) orders by total degree rst, then breaks ties using reverse lexicographic order. The most widely used monomial orderings are the lex(xn x1) and the the grevlex(xn x1). We note that lex and grevlex give the same ordering on the variables xn;:::;x1. Let us illustrate both orderings with the following: let f = 4xy2z + 4z2 5x3 + 7x2z2 2 F[x;y;z]: Then with respect to the lex ordering, we have that f = 5x3 + 7x2z2 + 4xy2z + 4z2; and with respect to the grevlex ordering, we have that f = 4xy2z+ 7x2z2 5x3 + 4z2: The following is an example from Cox et al [13]. Consider the monomials xy2z;z2;x3, and x2z2. Using the indeterminate order x y z; here?s how some of the monomial orders above would order these four monomials: Lex : x3 x2z2 xy2z z2 (power of x dominates). Grevlex : xy2z x2z2 x3 z2 (total degree dominates; lower power of z broke tie). But any global monomial ordering has at least one non-singular matrix A (with entries from N) that de nes it in the sense that x x if and only if A t lex A t: 4 1.2 Ideals and Gr obner bases Let I be an ideal of the ring R := P[y]. I is necessarily nitely generated by some f1;f2;:::;fm; so let I := hf1;:::;fmi = nX rifi : ri2R o with f1;:::;fm called genera- tors of I. B := (f1;:::;fm) is an ordered Gr obner basis for I if and only if each r in R has a unique remainder, called the normal form of f modulo I, (written NF(f;I)), after division by elements of B in any order. De nition 1.4. (See page 46 of [15].) Let G denote the set of all nite elements G R. A map NF : R G !R; (f;G)7!NF(f;G); is called a normal form on R if, for all G2G: (1) NF(0;G) = 0; and, for all f2R and G2G, (2) NF(f;G)6= 0 ) LM(NF(f;G)) =2L(G) :=hLM(g)jg2Gnf0gi, (3) If G =fg1;:::;gsg; then r := f NF(f;G) has a standard representation with respect to G, that is, either r = 0, or r = sX i=1 aigi; ai2R; satisfying LM(f) LM(aigi) for all i such that aigi6= 0: NF(f;G) is called a reduced normal form, if, moreover, NF(f;G) is reduced with respect to G. Let L(I) := fLM(f) : f 2Ig be the ideal of leading monomials of I. Any monomial not in L(I) is called a standard monomial, the set of such is often referred to as the footprint or -set, a (vector space) basis for the set of all normal forms NF(f;I). [ One of our speed-up techniques involves e cient computation of NF(fq;G) for large primes q. Such normal forms are used repeatedly in most of our computations.] De nition 1.5. [15]: Let G F[x] be any subset. (1) G is called minimal if 0 =2G and LM(g) - LM(f) for any two elements f6= g in G. We note that G is called interreduced if LM(g) - any monomial of f. (2) f 2R is called reduced with respect to G if no monomial of f is contained in the ideal, 5 L(G), generated by the leading monomials of G. L(G) is called the leading ideal of G. (3) Let I F[x] be an ideal and let be a monomial ordering on Mn(x): A nite set G F[x] is called a Gr obner basis of I if G I; and LM(I) = LM(G): That is, G is a Gr obner basis if the leading monomials of the elements of G generate the leading ideal of I, or, in other words, if for any f2Inf0g there exists a g2G satisfying LM(g)j LM(f). De nition 1.6. [13]: Let f;g2Rnf0g with LM(f) = x and LM(g) = x , respectively. Set := lcm( ; ) := (max( 1; 1);:::;max( n; n)) and let lcm(x ;x ) := x be the least common multiple of x and x . We de ne the s-polynomial of f and g (denoted by spoly(f;g)), to be spoly(f;g) := x f LC(f)LC(g)x g: If LM(g) divides LM(f), say LM(g) = x , LM(f) = x , then the s polynomial is given by spoly(f;g) := f LC(f)LC(g)x g; and LM(spoly(f;g)) LM(f). Buchberger?s algorithm, found in most literature on the subject including [13], [27], is suit- able for computing Gr obner bases and it does the computations via s-polynomials. Many characterization of Gr obner bases can be found in the literature. 1.3 P-algebras De nition 1.7. [14]: A ring R is called a domain if 0 is prime. Let P be a ring. Some authors de ne a P-algebra to be a commutative ring R such that P is a subring of R and the unity of P is also the unity in R. A commutative ring R is called a reduced ring if it has no non-zero nilpotent elements. A reduced, nitely-generated P-algebra is called an a ne P-algebra, or when it is not necessary to refer to the ring P, it is simply called an a ne ring. If the ring is a domain, then it is called an a ne domain. 6 This is the de nition presented in [[14], page 35]. However, we shall consider the following de nitions in this study. De nition 1.8. R := P[y]=I is called a quotient ring. If there are no zero-divisors, it is also called an a ne domain or a ne P-algebra. It is always possible to adjoin new variables so that there is a Gr obner basis in which all the relations induced are of degree at most 2. We call call such quotient rings strictly a ne P-algebras in the sense that all the P-quadratic relations describe a P-algebra multiplication, and any P-linear relations are called P-syzygies amongst the dependent variables. De nition 1.9. [13]: Let K be a eld, and let f1;:::;fs be polynomials in the polynomial ring K[x1;:::;xn]: Then V(f1;:::;fs) :=f(a1;:::;an)2Kn : fi(a;:::;an) = 0; 1 i sg is called the a ne variety de ned by f1;:::;fs. An a ne variety V(f1;:::;fs) Kn is thus the set of all solutions of the system of equations fi(a;:::;an) = = fs(a;:::;an) = 0: An algebraic variety is the set of solutions of a system of polynomial equations. 1.4 Order functions and order domains De nition 1.10. (see Geil and Pellikan, [6].) Let ( ; ) be a well-order, with its minimal element denoted by 0. An order function on an P-algebra R is a surjective function : R ! [f 1g; such that the following conditions hold: 1. (f) = 1 if and only if f = 0; 2. (af) = (f) for all nonzero a2F; 3. (f +g) maxf (f); (g)g; 4. if (f) (g) and h6= 0, then (fh) (gh); 5. if f and g are nonzero and (f) = (g), then there exists a nonzero a 2 F such that (f ag) (g) for all f;g;h2R. 7 De nition 1.11. A P-a ne algebra, R, on which there is de ned an order function is called an order domain over P, or simply an order domain. De nition 1.12. [4]: Let S = R=J be an a ne domain. A function wtS := R !Nn0 [f 1g (with 1 for all 2Nn0) is a weight function on S i : 1: wtS(f) = 1 i f2J; 2: wtS(f) = 0 i f = c+J; c2Fnf0g; 3: wtS(fg) = wtS(f) +wtS(g) for all f;g =2J; 4: wtS( f + g) maxfwtS(f);wtS(g)g for all ; 2F; 5: if wtS(f) = wtS(g) 0; then wtS(f g) wtS(g) for a unique 2F. Let AP be a non-singular n x n weight-over-grevlex matrix over N0 that de nes a global monomial ordering on P, the default here being the grevlex ordering, xn x1. Let APk be a submatrix of AP, consisting of the rst k rows of AP, where k is the number of the free variables in f, with J :=< f >. Then AP de nes a weight function given by wtP(x ) := (APk) t; with distinct monomials obviously having distinct weights. Suppose for example that AR := 0 BB BB @ 7 5 3 1 1 0 1 0 0 1 CC CC A is a weight-over-grevlex matrix that de nes a monomial ordering on R := F[y]. Then wt(y ) = ( 7 5 3 )( )t. Also x Ap x if and only if Ap t lex Ap t. An alternative de nition of a weight function is found in [[1], page 481 ]. The conditions of this de nition can restated in terms of leading monomials (LM) of normal forms (NF) of elements as follows: LM(NF( f)) = LM(NF(f)) for 06= 2F. 8 If LM(NF(g)) LM(NF(f)) and f6= g, then LM(NF(f g)) LM(NF(f)); and if LM(NF(g)) LM(NF(f)); then LM(NF(f g)) = LM(NF(f)): LM(NF(fg)) = LM(NF(LM(f);LM(g))). If LM(NF(f)) = LM(NF(g)); then LM NF(f) LC(NF(f)) NF(g) LC(NF(g)) LM(NF(f)): A weight function, say , can be extended to a function on quotients by de ning (f=g) := (f) (g)2Zr. The qth-power map acts on such elements and thus it is important to have the extended de nition of a weight function, see [1], page 482. Weight functions are very essential in our integral closure computations, as they are used with the earlier-mentioned monomial orderings to produce new monomial orderings. 1.5 Integral extensions and type I curves There are several de nitions of an integral element. We will present some of them here. De nition 1.13. [28]: Let R be a ring and S an R-algebra containing R. An element x2S is said to be integral over R if there exists an integer n and elements r1;:::;rn in R such that xn +r1xn 1 + +rn 1x+rn = 0: The above equation is called an equation of integral dependence of x over R of degree n. It is important to note here that equations of integral dependence are not unique if the function used to de ne the integral extension is reducible. Indeed let S be the ring Z[t]=(t2 t3), where t is a variable over Z: Let R be the subring of S generated over Z by t2: Then t2S is integral over R and it satis es the equations x2 t2 = 0 and x2 xt2 = 0 in x: This is not surprising as the function f(t) = t2 t3 is reducible. In our de nition, we will require f(t) to be irreducible. 9 De nition 1.14. [30]: Suppose R is a subring of the commutative ring S with 1 = 1s2R. 1 An element s2S is integral over R if s is the root of a monic polynomial in R[x]: 2 The ring S is an integral extension of R or just integral over R if every s 2 S is integral over R: 3 The integral closure of R in S is the set of all elements of S that are integral over R: We will consider the integral closure of an integral domain, R, in its eld of fractions, Q(R). We shall consider the following as our de nition of an integral element and integral closure. De nition 1.15. (Integral element) [1]: Let S be a domain and R a subdomain of S. An element y2S is said to be integral over R if and only if there exists a monic polynomial y(T)2R[T] such that y(y) = 0: Feng and Rao introduced type I curves to be curves that satisfy equations of the form xa +yb +g(x;y) = 0; gcd(a;b) = 1; a>b> deg(g(x;y)): We shall consider the follow as our de nition of type I integral extensions. De nition 1.16. [4]: Let f(T) := dX i=0 fiTi 2 P[T] be a monic, absolutely irreducible polynomial of degree d. Let the a ne domain S := P[y]=J be an integral extension for J := hf(y)i: To extend wtP to a weight function wtS on S, de ne wtS(x ) := d wtP(x ); and wtS(y) := maxfwtS(fi)d i : 0 i < dg: If the max is taken on at only one value of i, the value is i = 0; LM(f0) := x , and gcdfd; gcdf i : 0 i is a nitely-generated R-module and (3) s2T for some subring T, that is a nitely-generated R-module. Proof: Suppose rst that (1) holds and let s be a root of the monic polynomial f(x) := xn +an 1xn 1 + +a02R[x]: Then sn = (an 1sn 1 +an 2sn 2 + +a0) and so sn, and hence all higher powers of s, can be expressed as R-linear combinations of sn 1;:::;s;1: So R[s]= < f(s) >:= R1 + Rs + + Rsn 1 is nitely generated as an R-module, which gives (2): 12 If (2) holds then (3) holds with T = R[s]=: Suppose that (3) holds and let v1;v2;:::;vn be a nite generating set for T: Then for i = 1;2;:::;n the element svi is an element of T since T is a ring, and so can be written as an R-linear combination of v1;:::;vn : svi = nX j=1 aijvj; for 1 i n. So 0 = nX j=1 ( ijs aij)vj, where ij is the Kronecker delta. If B is the n n matrix whose i;j entry is ijs aij; and v is the n 1 column vector whose entries are v1;:::;vn, then these equations are simply of the form Bv = 0. It follows from Cramer?s Rule that det(B)vi = 0 for all i. But B = sI A, where A is the matrix (aij). Thus s is a root of the monic polynomial det(xI A)2R[x] ( the characteristic polynomial of A), and so s is a root of a monic polynomial with coe cients in R, which gives (1), completing the proof. Corollary 2.1. Let R S be as in Theorem 2.1 above and let s;t2S (1) if s and t are integral over R then so are s t and st. (2) The integral closure of R in S is a subring of S containing R. (3) Integrality is transitive: let S be a subring of T; if T is integral over S and S is integral over R, then T is integral over R. Proof: Let s and t be integral over R. By Theorem 2.1 both R[s] and R[t] are nitely- generated R-modules, say R[s]=:= (Rs1 +Rs2 + +Rsn) R[t]=:= (Rt1 +Rt2 + +Rtm): Then R[s;t]=:= (Rs1t1 + +Rsitj + +Rsntm) is a ring containing s t and st that is also a nitely-generated R module. Hence s t and st are also integral over R, which proves (1) and also (2). 13 To prove (3), let t2T. Since t is integral over S, it is the root of some monic polynomial p(x) = xn + an 1xn 1 + + a0 2S[x]: Since ai2S is integral over R, each ring R[ai]=< f(ai) > is a nitely-generated R-module and so the ring R1 := R[a0;a1;:::;an 1]= < f(a0;a1;:::;an 1) > is also a nitely-generated R-module. Since the monic polynomial p(x) has its coe cients in R1, t is integral over R1 and it follows that the ring R1[t]=:= R[a0;a1;:::;an 1;t] is a nitely-generated R-module. By Theorem 2.1, this means that t is integral over R, which gives (3). 2.1 de Jong?s algorithm de Jong?s algorithm has been implemented in Magma, Singular and Macaulay2 to compute integral closures. The approach is to produce a nested sequence of rings R := R0 RL = RL+1 = ic(R) with a presentation that is based on elements of the eld of fractions, Q(R), used to de ne the rings involved. Below is a version of de Jong?s algorithm: Algorithm: ( See page 275, [9] for details.) INPUT: A reduced Noetherian ring R. OUTPUT: The normalization eR of R. STEP 1: Determine a non-zero ideal I with NNL V(I). STEP 2: Take a non-zero element f2I; and compute J := Ann(f): If J = 0, GOTO STEP 4. STEP 3: Put R := R=Ann(J) R=J and GOTO STEP 1. STEP 4: Compute the radical pI of I. Put I :=pI. STEP 5: Compute HomR(I;I). If R = HomR(I;I) then put eR := R and STOP. STEP 6: Set R := HomR(I;I) and GOTO STEP 1. In Singular ([15] page 224), the idea to compute ic(R) is to enlarge the ring R to the endomorphism ring R0 = HomR(J;J) for a suitable ideal J such that R0 ic(R), and repeat the process until it stabilizes at the integral closure ic(R). 14 We now present the theory that is used in Singular to produce the increasing sequence of rings that contains the initial ring and is also contained in the integral closure. Theorem 2.2. (See [15], page 192 for details.) Let A;B be rings. (1) If ? : A ! B is a nite extension, then it is integral. More generally, if I A is an ideal and M a nitely-generated B-module then any b2B with bM IM satis es a relation bp +a1bp 1 + +ap = 0; with ai2 A: (2) If B is a nitely-generated A-algebra of the form B = A[b1;:::;bn] with bi2B integral over A then B is nite over A. Theorem 2.3. (See Lemma 3.6.1 of [15].) Let R be a reduced Noetherian ring and J A an ideal containing a non-zerodivisor x of R. Then there are natural inclusions of rings R HomR(J;J) = 1x (xJ : J) ic(R) Proof: For a2R, let ma : J !J denote the multiplication by a. If ma = 0, then ma(x) = ax = 0 and, hence, a = 0, since x is a non-zerodivisor. Thus a7!ma de nes an inclusion R HomR(J;J). It is easy to see that ?2HomR(J;J) the element ?(x)=x2Q(R) is independent of x: for any a2J we have ?(a) = (1=x) ?(xa) = a ?(x)=x; since ? is R-linear. Hence ?7!?(x)=x de nes an inclusion HomR(J;J) Q(R) mapping x HomR(J;J) into xJ : J = fb2RjbJ xJg. The latter map is also surjective, since any b2xJ : J de nes, via multiplication by b=x, an element ?2HomR(J;J) with ?(x) = b. Since x is a non-zerodivisor, we obtain the isomorphism HomR(J : J) = (1=x) (xJ : J): It follows from [Theorem 2.2] that any b2xJ : J satis es an integral relation bp + a1bp 1 + +a0 = 0 with ai2. Hence, b=x is integral over R, showing 1x (xJ : J) ic(R): 15 Example 2.1. ( See example 3.6.8 of [15].) Let R := F[x;y]=hx2 y3i and J := hx;yi: Then x 2 J is a non-zerodivisor in R with xJ : J = xhx;yi : hx;yi = hx;y2i, therefore, HomR(J;J) =h1;y2=xi. Thus we have R h1;y2=xi = 1x (xJ : J) ic(R): 16 Chapter 3 The qth-power algorithm in positive characteristic In this chapter, we present the qth-power algorithm to compute the integral closure of rings over the nite elds. Most of our rings in this section will be from towers. 3.1 qth-power algorithm The qth-power algorithm approach is to begin with a dual module M(0) := 1R and produce a sequence of P-modules 1R := M(0) M(L) = M(L+1) = ic(R) where M(L+1) := 1f2M(L) : ( 1f)q2M(L) qth-power algorithm: Let f(y;x) be a polynomial of degree m in F[y;x], with y being the dependent variable, x the independent variable, weight(y) = r and weight(x) = s. Let I = ideal. (1) ( and weights): (a) Compute the conductor element, , (via computing a Gr obner basis of the ideal gen- erated by minors of the Jacobian matrix of a Gr obner basis of I). [There are other ways to compute .] (b) := (qn) Totaldegree(LT( )) + 1 (c) maxweight := m 1X i=0 wt(yi)(q 1) + (2) (Initialization): Let G be a list from 0 to maxweight with entries all zeros. set nextG := G. Set G[0] := 12 F[x;y], F[0] := 12F[x;y] and H[0] := 02F[x;y]. For i = 1 to m 1, G[i r] := G[(i 1) r] y, F[i r] := NormalForm(F[(i 1) r] yq;I), 17 H[i r] := NormalForm(H[(i 1) r] yq;I). StartG := G While StartG6= nextG (3) ( Reduction): From smallest weight j = 1 to maxweight, do (a) (Element of nextG): If F[j] = 0 then nextG[j] := G[j]. (b) (F[j]=(StartG[i] LT( )); i < j): If F[j] divides (StartG[i] LT( )) with quotient say, quo, then G[j + s] := G[j] x; F[j + s] := F[j] xq ( StartG[i] quo); H[j + s] := H[j] xq + (StartG[i] quo). (c) (LM(F[j]) already exist): If LM(F[i]) = LM(F[j]); i 0 and gcd(a;b) = 1. For any xed modulus M > 0, we de ne QM := na b;b> 0; gcd(a;b) = 1 : gcd(M;b) = 1 o : Let F[x] := F[xm;:::;x1] and x := Y i x ii . We will consider type I a ne domains S := R=I with R := F[x] being a polynomial ring, and I := hGi an ideal of R of relations with Gr obner basis G. Type I a ne domains have the property, among others, that relative to a free polynomial subring P := F[xn;:::;x1], there is a weight function wt : R !Nn such that wt(LM(f)) = wt(LM(NF(f;I))). Given a presentation S := R=I and a presentation of its integral closure S := R=I, there is a map : R !R, necessarily with (I) I, so that can be viewed as an inclusion map : S !S. It is possible to use the extended Euclidean algorithm to move between fractions ab 2 Q; b> 0 and representatives c2ZN. The fraction reconstruction map (see [26] for details) is EN(c) := ab; bc+Nd = a;a2 +b2 min; b min: The mod N map is N a b := c; bc+Nd = a; jcj min: 39 These are almost inverse operations in the sense that for N2 0, produces sequences (ri) and (qi) such that ri 2 = qiri 1 +ri with 0 ri :=PolynomialRing(Integers( ),1); f1 := (x^4-420*x^2+40000); 58 I:=ideal; 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:=PolynomialRing(Q,5); f:=x^4-420*x^2+40000; co:=function(h,i) return Coefficient(h,x,i); end function; n:=function(g) l:=NormalForm(g^2,[f]); return l; end function; del:= 65600000; Factorization(del); ///===================================================; g0:=1; g1:=x; g2:=x^2; g3:=x^3; p:=5; a1:=2*a1+a3; a2:=2*a2; a0:=2*a0; a1:=2*a1; a3:=2*a3; a0:=2*a0; a2:=2*a2; 59 a0:=2*a0; a1:=2*a1+a2+a3; a0:=2*a0; a1:=2*a1+a3; a2:=2*a2; a0:=2*a0; a1:=2*a1+a3; a2:=5*a2; a0:=5*a0+a2; a1:=5*a1+2*a3; a0:=5*a0; a2:=5*a2; a0:=5*a0; a1:=5*a1; a0:=41*a0 - 5*a2; a1:=41*a1 - 5*a3; b3:=a3; b2:=a2; b1:=a1; b0:=a0; h3:=n(b3*g3 + b2*g2 + b1*g1 + b0*g0); i3:=co(h3,3) div co(g3,3); 3, "i3 =",i3; h2:=h3 - i3*g3; "h2 =",h2; i2:=co(h2,2) div co(g2,2); 2, "i2 =",i2; h1:=h2 - i2*g2; "h1 =",h1; i1:=co(h1,1) div co(g1,1); 1, "i1 =",i1; h0:=h1 - i1*g1; "h0 =",h0; i0:=h0 div g0; 0, "i0 =",i0; I:=[i3,i2,i1,i0]; k3:=GCD(Coefficients(i3)); 3, "k3 =",k3; k2:=GCD(Coefficients(i2)); 2, "k2 =",k2; k1:=GCD(Coefficients(i1)); 1, "k1 =",k1; k0:=GCD(Coefficients(i0)); 0, "k0 =",k0; k:=[k3,k2,k1,k0]; k:=[GCD(Coefficients(I[l])):l in [1..4]]; "k =",k; kk:=[del div GCD(k[l],del): l in [1..4]|k[l] ne 0]; "kk =",kk; R:=PolynomialRing(GF(p),4); hPR:=homR|0,a3,a2,a1,a0>; 60 j:=[hPR(I[l] div k[l]): l in [1..4] | (k[l] ne 0) and (((del div GCD(k[l],del)) mod p) eq 0)]; "j=",j; J:=ideal; RR:=Radical(J); G:=GroebnerBasis(RR); "G =",G; h:=b3*g3 + b2*g2 + b1*g1 + b0*g0; "h=",h; "b0 =",b0; "b1 =",b1; "b2 =",b2; "b3 =",b3; ///////////////////////////////// give us the following outputs; p = 41 G = [ a0 + 5*a2, // linear relation a1 + 5*a3, // linear relation a2^41 + 40*a2, a3^41 + 40*a3 ] h = x^3*a3 + x^2*a2 + x*a1 + a0 G = [ a0^41 + 40*a0, a1^41 + 40*a1, a2^41 + 40*a2, a3^41 + 40*a3 ] h = x^3*a3 + x^2*a2 - 5*x*a3 + 41*x*a1 - 5*a2 + 41*a0 p = 5 G = [ a0, // linear relation a1^5 + 4*a1, a2, // linear relation a3^5 + 4*a3 ] h = x^3*a3 + x^2*a2 - 5*x*a3 + 205*x*a1 - 5*a2 + 205*a0 61 G = [ a0 + 4*a2, // linear relation a1 + 3*a3, // linear relation a2^5 + 4*a2, a3^5 + 4*a3 ] h = x^3*a3 + 5*x^2*a2 - 5*x*a3 + 205*x*a1 - 25*a2 + 1025*a0 G = [ a0^5 + 4*a0, a0*a3, a1^5 + 4*a1, a2, // linear relation a3^5 + 4*a3 ] h = x^3*a3 + 5*x^2*a2 + 405*x*a3 + 1025*x*a1 + 1000*a2 + 5125*a0 G = [ a0^5 + 4*a0, a0*a1, a0*a3, a1^2 + a1*a3, a1*a3^4 + 4*a1, a2^5 + 4*a2, a3^5 + 4*a3 ] h = x^3*a3 + 25*x^2*a2 + 405*x*a3 + 1025*x*a1 + 5000*a2 + 5125*a0 p = 2 G = [ a0, // linear relation a1 + a3, // linear relation a2, // linear relation a3^2 + a3 ] h = x^3*a3 + 25*x^2*a2 + 1430*x*a3 + 2050*x*a1 + 5000*a2 + 10250*a0 G = [ a0, a1 + a2 + a3, 62 a2^2 + a2, a3^2 + a3 ] h = x^3*a3 + 50*x^2*a2 + 3480*x*a3 + 4100*x*a1 + 10000*a2 + 20500*a0 G = [ a0, // linear relation a1^2 + a1, a2, // linear relation a3^2 + a3 ] h = x^3*a3 + 50*x^2*a2 + 7580*x*a3 + 4100*x*a2 + 8200*x*a1 + 10000*a2 + 41000*a0 G = [ a0, // linear relation a1, // linear relation a2^2 + a2, a3 ] // linear relation h = x^3*a3 + 100*x^2*a2 + 7580*x*a3 + 8200*x*a2 + 8200*x*a1 + 20000*a2 + 82000*a0 G = [ a0^2 + a0, a1^2 + a1, a2, // linear relation a3^2 + a3 ] h = 2*x^3*a3 + 100*x^2*a2 + 15160*x*a3 + 8200*x*a2 + 16400*x*a1 + 20000*a2 + 164000*a0 G = [ a0^2 + a0, a0*a3, a1 + a3, // linear relation a2^2 + a2, a3^2 + a3 ] h = 2*x^3*a3 + 200*x^2*a2 + 15160*x*a3 + 16400*x*a2 63 + 16400*x*a1 + 40000*a2 + 164000*a0 G = [ a0^2 + a0, a0*a3, a1^2 + a1, a2^2 + a2, a3^2 + a3 ] h = 2*x^3*a3 + 200*x^2*a2 + 31560*x*a3 + 16400*x*a2 + 32800*x*a1 + 40000*a2 + 164000*a0 Let S(j) and M(j) be de ned as in above. Let S(j) be a subset of S(j), obtained from the linear relations in the Gr obner basis computations generating S(j). Let M(j) := ZhS(j)i. Looking at the above example and considering the linear relations in the Gr obner computa- tions we get that S(1) =f164000;32800x;200x2 + 16400x+ 40000;2x3 1240xg, and M(1) := ZhS(1)i. Similarly by repeating the process we get S(2) = f3280000;3280000x;164000x2 + 1640000x;8200x3 5084000xg, and M(2) := ZhS(2)i. S(3) =f32800000;6560000x;1640000x2+16400000x;16400x3 10168000xg, and M(3) := ZhS(3)i. S(4) =f65600000;32800000x;1640000x2 + 16400000x;82000x3 50840000x + 32800000g, and M(4) := ZhS(4)i. S(5) =f65600000;32800000x;1640000x2 + 16400000x;82000x3 50840000x + 32800000g, and M(5) := ZhS(5)i. We compute M(L) until M(L+1) = M(L) for some L 2 N. The above example illustrates how we can get M(1) from M(0). The process is the same to get any other M(L) until M(L+1) = M(L) for some L2N. We want to show that M(L+1) = M(L) for some L2N. 64 Lemma 5.1. Let R; ic(R); S(j); S(j) and M(j); M(j) be as above. Then any sequence 1R = M(0) M(1) M(2) of Z-modules containing ic(R) is nite. That is, M(L+1) = M(L) for some L2N. Proof: Let 1f2S(j) be arbitrary with, LT(f) = xi. It is very important to note here that S(j) is not necessarily closed under linear combinations. However, given any 1f2S(j) then 1f2M(j 1). But as earlier observed, M(j 1) has a Z-module basisf 1gk; 0 k; Hence f2 satis es an integral equation. We want to show that f3 is integral. That is, it satis es an integral equation. Note NF(f23;I) = 1=800x3 + 1=2x2 + 9=20x 97=2; NF(f43;I) = 503=800x3 + 57x2 2873=20x 15393=2; NF(f83;I) = 9790521=800x3 + 508326x2 70459911=20x 147505153=2; and f23 = f3 + 20f2 10f1 49f0; f43 = 503f3 + 2280f2 1510f1 7948f0; f83 = 9790521f3 + 20333040f2 18095250f1 78647837f0; Using row-reduction to eliminate f2 and f1, we get an integral equation f83 21429f43 + 1426254f23 437988f3 21783409 = 0; One can check that setting y := f83 21429f43 + 1426254f23 437988f3 21783409; 68 we get NF(y;I) = 0: Note that y factors into the following minimum polynomials ; Hence f3 satis es an integral equation. Theorem 5.1. Let M(L) be de ned as above such that M(L) = M(L+n); for any n2N. Then every element in M(L) is integral. Proof: The approach here is to show that each element in M(L) satis es an integral equation. Suppose nfn2M(L) for all n. Then any Z-linear combination is as well because M(L) is a Z-module. We can thus produce a Z-dependency satis ed by 1f and then a Z-integral equation satis ed by 1f. Consider the m-tuples LC((fi)n). If M(i) 6= M(l), then their m-tuples are distinct. By construction, LC((fi)n)j , so there are only nitely many such distinct m-tuples to consider. We observed earlier that M(L) has a Z-module basis f( 1fi) 2S(L) : 0 i < mg; with degree (fi) = i. Hence given each fi, we can write ( 1fi)j jNF((fi)j;I) = m 1X k=0 zi;j;k( 1fk); for some integers zi;j;k and for all j. Let fi, 0 ii: Start with n = 1. If LM(gn) = LM(gi) for some i := PolynomialRing(Integers()); // select an example below by deletting th // at the //beginning of the example // K := NumberField(x^4-420*x^2+40000); // Example 1 // K := NumberField(x^6 - 200*x^3 + 1500); // Example 2 // K := NumberField(x^5 + 5*x^4 - 75*x^3 + 250*x^2 + 65625); // Example 3 72 // K := NumberField(x^4 + 5*x^3 - 25*x^2 + 125*x + 625); // Example 4 K := NumberField(x^4-10*x^2+1); // Example 5 E := EquationOrder(K); Round2(E, K); 5.2.1 Examples using Magma Example 5.4. (Same as example 5.1 done di erently). Let f(x) := x4 420x2 + 40000 and R := Z[x]=hf(x)i. >[ <2, 18>, <5, 8>, <41, 2> ] index is 2 index is 4 index is 8 index is 4 index is 2 index is 1 index is 5 index is 25 index is 1 index is 1 index of equation order in maximal order is: 64000 Transformation of E Transformation Matrix: [800 0 0 0] [ 0 400 0 0] [ 0 200 20 0] [400 180 0 1] 73 Denominator: 800 So := 800 and ic(R) = Zh800;400x;20x2 + 200;x3 + 180x+ 400i. Example 5.5. (Same as example 5.3 done di erently). Let f(x) := x6 200x3 + 1500 and R := Z[x]=hf(x)i. [ <2, 16>, <3, 8>, <5, 15>, <17, 3> ] index is 2 index is 2 index is 2 index is 2 index is 2 index is 2 index is 1 index is 3 index is 1 index is 5 index is 25 index is 5 index is 25 index is 1 index is 1 index of equation order in maximal order is: 3000000 Transformation of E Transformation Matrix: [300 0 0 0 0 0] [ 0 300 0 0 0 0] 74 [ 0 0 60 0 0 0] [150 0 0 15 0 0] [ 0 150 0 0 3 0] [ 0 0 30 10 2 1] Denominator: 300 So := 300 and ic(R) = Zh300;300x;60x2;15x3+150;3x4+150x;x5+2x4+10x3+30x2i. Example 5.6. Let f(x) := x5 + 5x4 75x3 + 250x2 + 65625 and R := Z[x]=hf(x)i. [ <2, 2>, <3, 1>, <5, 20>, <7, 1>, <37, 1>, <353263, 1> ] index is 1 index is 1 index is 5 index is 25 index is 125 index is 625 index is 1 index is 1 index is 1 index is 1 index of equation order in maximal order is: 9765625 Transformation of E Transformation Matrix: [625 0 0 0 0] [ 0 125 0 0 0] [ 0 0 25 0 0] [ 0 0 0 5 0] [ 0 0 0 0 1] 75 Denominator: 625 So := 625 and ic(R) = Zh625;125x;25x2;5x3;x4i. Example 5.7. Let f(x) := x4 + 5x3 25x2 + 125x+ 625 and R := Z[x]=hf(x)i. [ <3, 1>, <5, 12>, <13, 2> ] index is 1 index is 5 index is 25 index is 125 index is 1 index is 1 index of equation order in maximal order is: 15625 Transformation of E Transformation Matrix: [125 0 0 0] [ 0 25 0 0] [ 0 0 5 0] [ 0 0 0 1] Denominator: 125 So := 125 and ic(R) = Zh125;25x;5x2;x3i. Example 5.8. Let f(x) := x4 10x2 + 1 and R := Z[x]=hf(x)i. [ <2, 14>, <3, 2> ] index is 2 index is 4 index is 1 index is 1 76 index of equation order in maximal order is: 8 Transformation of E Transformation Matrix: [ 4 0 0 0] [ 0 4 0 0] [-2 0 2 0] [-3 -1 -1 1] Denominator: 4 So := 4 and ic(R) = Zh4;4x;2x2 2;x3 x2 x 3i. 77 Chapter 6 Various implementations In this chapter, we look at the output from various implementations in computing integral closures. This enables us to see the uniqueness and advantages of the qth-power algorithm approach. By example, we see that the output from other implementations have issues with some key concepts such as weight functions, monomial orderings, and the type of presentation produced. Throughout this chapter, our example will be the following: Example 6.1. Let F be the nite eld, GF(23). Let R := F[y;x]; f := (y8 y2x3+2yx6 x9) and I :=. We know from theqth-power algorithm that the weights of theP-module basis generating the integral closure are [0;4;5;10;14;15;19], where F := GF(23) and P := F[x]. We will present outputs from Singular, Macaulay2, Magma and the qth-power algorithm. 6.1 Output from Singular Using the "normal" command: > LIB "normal.lib"; > ring r=23,(y,x),wp(9,8); > ideal i = (y^8 - y^2*x^3 + 2*y*x^6 -x^9); > list nor=normal(i); > nor; [1]: [1]: // characteristic : 23 78 // number of vars : 7 // block 1 : ordering dp // : names T(1) T(2) T(3) T(4) T(5) // block 2 : ordering wp // : names y x // : weights 9 8 // block 3 : ordering C [2]: [1]: _[1]=y5x2 _[2]=y6x _[3]=y3x5-y4x2 _[4]=y8 _[5]=yx8-y2x5 _[6]=yx6-y2x3 > def R=nor[1][1]; > setring R; > normap; normap[1]=y normap[2]=x > norid; norid[1]=T(1)*y-T(2)*x norid[2]=T(4)*y-T(5)*x+y norid[3]=-T(5)+x^2 norid[4]=-T(3)*x+y^2 norid[5]=T(2)*y^2-T(4)*x norid[6]=T(1)*x^3-T(2)*x-T(3)*y^2 79 norid[7]=T(3)*x^3-T(5)*y^2 norid[8]=T(2)*x^4-T(2)*y*x-T(3)*y^3 norid[9]=T(3)*y^5-T(4)*x^5+T(5)*x^3-T(5)*y norid[10]=T(4)*x^8-T(5)*y^7-T(5)*x^6+T(5)*y*x^3 norid[11]=T(1)^2-x norid[12]=T(1)*T(2)-y norid[13]=T(2)^2-T(3) norid[14]=T(1)*T(3)-T(2)*y norid[15]=T(2)*T(3)-T(4) norid[16]=T(3)^2-T(1)*x^2+T(2) norid[17]=T(1)*T(4)-T(3)*y norid[18]=T(2)*T(4)-T(1)*x^2+T(2) norid[19]=T(3)*T(4)+T(3)-y*x^2 norid[20]=T(4)^2-T(1)*y^2*x+T(4) norid[21]=T(1)*T(5)-T(1)*x^2 norid[22]=T(2)*T(5)-T(1)*y*x norid[23]=T(3)*T(5)-y^2*x norid[24]=T(4)*T(5)-T(1)*y^3 norid[25]=T(5)^2-x^4 norid[26]=-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(5)-x^2 j[3]=T(4)*y-x^3+y j[4]=T(4)*x^6-y^7-x^6+y*x^3 j[5]=T(3)*x-y^2 80 j[6]=T(3)*y^5-T(4)*x^5+x^5-y*x^2 j[7]=T(2)*y^2-T(4)*x j[8]=T(2)*x^4-T(2)*y*x-T(3)*y^3 j[9]=T(1)*y-T(2)*x j[10]=T(1)*x^3-T(2)*x-T(3)*y^2 j[11]=T(4)^2-T(2)*y*x^2+T(4) j[12]=T(3)*T(4)+T(3)-y*x^2 j[13]=T(2)*T(4)-T(1)*x^2+T(2) j[14]=T(1)*T(4)-T(3)*y j[15]=T(3)^2-T(1)*x^2+T(2) j[16]=T(2)*T(3)-T(4) j[17]=T(1)*T(3)-T(2)*y j[18]=T(2)^2-T(3) j[19]=T(1)*T(2)-y j[20]=T(1)^2-x The normal command produces an R-module generating set,fT(1);T(2);T(3);T(4);T(5)g. We see thatnor[1][1] gives a block order, grevlex on the new variablesfT(1);T(2);T(3);T(4);T(5)g and the given order on the old variables, fy;xg. The R-module generators are given by T(1) := (y5x2)= ; wt(T(1)) = 4 T(2) := (y6x)= ; wt(T(2)) = 5 T(3) := (y3x5 y4x2)= ; wt(T(3)) = 10 T(4) := (y8)= ; wt(T(4)) = 15 T(5) := (yx8 y2x5)= ; wt(T(5)) = 16 where := yx6 y2x3 is the conductor element used. Looking at the ideal j above, we see that j[2] = T(5) x2. That is T(5) = x2 and T(5) does not show up elsewhere in j. So T(5) is an extra variable. Also, we notice that the weights 14 and 19 corresponding to T(2)y and T(3)y respectively, are missing. These variables do 81 not show up in the presentation because Singular is producing an R-module presenta- tion, instead of producing a P-module presentation. The relations, norid, in the algebra presentation here are linear and quadratic over the input ring. Using the "normalP" with the "withRing" option command: > LIB "normal.lib"; > ring r=23,(y,x),wp(9,8); > ideal i =(y^8-y^2*x^3+2*y*x^6-x^9); > 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]: 82 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) normalP with the "withRing" command does not produce an R-module generating set. The fractions produced are T(1) := (y5x)= ; wt(T(1)) = 4 83 T(2) = (y6)= ; wt(T(2)) = 5 T(3) := (y3x4 y4x)= ; wt(T(3)) = 10 T(4) = (x8 y2x2)= ; wt(T(4)) = 15 where := yx5 y2x2 is the conductor element used. We see that nor[1][1] gives a block order, grevlex on the new variables fT1;T3g. The old variables y and x are replaced with (T(1))6 T(1)T(3) and (T(1))2 respectively. We know the weights that are produced by the qth-power algorithm. Here we have just wt(T(1)) := 4 and wt(T(3)) := 10. This is probably because Singular is getting rid of the variables T(2);T(4);y and x. It thinks these variables are unnecessary. There are no y?s and x?s and the relations do not indicate that R is a subring. A Gr obner basis of the presentation reduces to a relation which is no longer a presenta- tion over R at all. In fact, the relation is in terms of T(1) and T(3), which is neither linear nor quadratic over R. Using the "normalP" with "withRing" and "noRed" command: > LIB "normal.lib"; > ring r=23,(y,x),wp(9,8); > ideal i = (y^8 - y^2*x^3 + 2*y*x^6 -x^9); > 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 84 // : 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(2)*x-T(3)*y^2 norid[6]=T(1)^2-x norid[7]=T(1)*T(2)-y 85 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 86 j[17]=T(2)^2-T(3) j[18]=T(1)*T(2)-y j[19]=T(1)^2-x normalP with "withRing" and "noRed" command produces an R-module generating set, fT(1);T(2);T(3);T(4)g, with fewer variables. We see that nor[1][1] gives a block order, grevlex on the new variablesfT(1);T(2);T(3);T(4)gand the given order on the old variables, fy;xg. The R-module generators are given by T(1) := (y5x)= ; wt(T(1)) = 4 T(2) := (y6)= ; wt(T(2)) = 5 T(3) := (y3x4 y4x)= ; wt(T(3)) = 10 T(4) := (x8 y2x2)= ; wt(T(4)) = 15 where := yx5 y2x2 is the conductor element used. We notice that the weights 14 and 19 corresponding to T(2)y and T(3)y respectively, are missing. These variables do not show up in the presentation because Singular is producing an R-module presentation, instead of producing a P-module presentation. The relations, norid, in the algebra presentation here are linear and quadratic over the input ring, R. Looking at the outputs from Singular, the outputs gotten by using normalP(i,"withRing","noRed") and normal commands are radically di erent from the out- put gotten by using the normalP(i,"withRing") command, which produces a presentation over F23[T(3)], instead of a presentation over F23[T(2)]. Indeed, a presentation using T(2) instead of T(3) would have probably matched the output of MAGMA?s Normalisation. The presentation from normalP(i,"withRing") command, has a Gr obner basis having only one relation j[1] = (T(1))10 2(T(1))5(T(3))2 + 9(T(3))4 T(3). This presentation is not quite type I because gcd(wt(T(1));wt(T(3)))6= 1. It is important to note that the theory in the Singular book (see [15]) is that the pre- sentation is to be a strict a ne R-algebra. But the presentation from normalP(i,"withRing") 87 is contrary to this theory. In fact normalP(i,"withRing") tries to get a minimized presen- tation, suggesting that such an a ne R- algebra presentation may not be the best. The attempt by normalP(i,"withRing") to get a minimized presentation is unsuccessful as T(2) is removed instead of T(3). normalP(i,"withRing","noRed") and normal produce an a ne R-algebra presentation, which matches the theory in the book. In order the salvage the output from Singular, it is vital to process the input so as to identify the free and independent variables in the input ring. We think that the presentation over the input ring, R, is not a good approach. The presentation should be over the ring of free variables, P, as in the case of the qth-power algorithm. In fact using the qth-power algorithm, we produce a strictly P-a ne algebra presentation, with only linear and quadratic relations over the ring of free variable, P. It is also important to note the input ring is no longer important in the output, since the integral closure always contain the input ring. Unfortunately, Singular thinks that the input ring is more important in the output. 6.2 Output from Macaulay2 The integralClosure and icFracP commands in Macaulay2 give 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); o3 : Ideal of R i4 : S=R/I; i5 : time P=presentation(integralClosure(S)) -- used 2.12 seconds o5 = | w_(10,0)^3y-x3+y w_(12,0)x2-w_(10,0)^4-w_(10,0) --------------------------------------------------------------- w_(12,0)w_(10,0)x-yx w_(12,0)y-w_(10,0)x w_(12,0)w_(10,0)-y --------------------------------------------------------------- 88 w_(12,0)^2x-x2 w_(12,0)^2-x | ZZ 1 ZZ 7 o5 : Matrix (--[w , w , y, x]) <--- (--[w , w , y, x]) 23 12,0 10,0 23 12,0 10,0 i6 : time G=gens gb P -- used 0. seconds o6 = | x9-y8-2yx6+y2x3 w_(10,0)y3-x4+yx w_(10,0)x5-w_(10,0)yx2-y5 --------------------------------------------------------------- w_(10,0)^2x-y2 w_(10,0)^3y-x3+y w_(10,0)^5+w_(10,0)^2-yx2 --------------------------------------------------------------- w_(12,0)y-w_(10,0)x w_(12,0)x2-w_(10,0)^4-w_(10,0) --------------------------------------------------------------- w_(12,0)w_(10,0)-y w_(12,0)^2-x | ZZ 1 ZZ 10 o6 : Matrix (--[w , w , y, x]) <--- (--[w , w , y, x]) 23 12,0 10,0 23 12,0 10,0 i7 : time F=icFracP(S) -- used 432.23 seconds 5 2 4 2 3 x - y*x x - y*x y x - 6y o7 = {1, ---------, --------, --, -------} 4 3 x y y y Macaulay2?s integralClosure command produces an R-module generating set, fw (10;0);w (12;0)g, with w (10;0) := x4 yxy3 , having weight wt(w (10;0)) = 5 and w (12;0) := w (10;0)xy = x5 yx2y4 , having weight wt(w (12;0)) = 4. Though integralClosure produces a presentation that is not quadratic-and-linear over R, icFracP does not produce 89 a presentation at all, but only fractions. Though icFracP does not produce weights, we see that the weights of the fractions produced are [0;4;5;10;15]. Again the output here from Macaulay2, using either the integralClosure or the icFracP command, produces fewer variables. The weights 14 and 19 corresponding to y((x4 yx)=y3) and y((y2)=x)) respectively, are missing. These variables do not show up in the presentation because Macaulay2 is producing an R-module presentation over the input ring,R, instead of producing a P-module presentation. 6.3 Output from Magma The IntegralClosure command in Magma gives a module presentation over the function eld Q(x). 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=0 is",Cputime(t23); ================================== [ 1 1 2 Y 90 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 + 18/X^10*Y + 1/X^7 ] which is an F23[x]-module basis. Though Magma does not produce weights, we see that the weights of the fractions are [0;9;10;19;20;29;30;4]. Magma?s IntegralClosure treats the output as a subring of F23(X)[Y], allowing for operations to be performed on elements there, which means producing other elements of F23(X)[Y] not necessarily immediately recognizable in terms of the basis elements produced. The Normalisation command in Magma gives t:=Cputime(); 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); ====== 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:=homFF|[FF.j:j in [1..n]]>; R:=PolynomialRing(FF); ff:=&+[Coefficient(f,P.i,j)@hP*R.1^j: j in [0..Degree(f,P.i)]]; gg:=&+[Coefficient(g,P.i,j)@hP*R.1^j: j in [0..Degree(g,P.i)]]; dd1,aa1,bb1:=XGCD(ff,gg); C:=Lcm([Denominator(x) : x in Eltseq(aa1) cat Eltseq(bb1)]); D:=dd1*C;A:=aa1*C;B:=bb1*C; hR:=homP|homP|[P.j: j in [1..n]]>, P.i>; return D@hR,A@hR,B@hR; end function; /////////////////////////////////////////////////////////////////////// Some of the algebraic packages do not have a direct implementation of the extended Eu- clidean algorithm. And those that do have one, rely on resultant computations, which often turn out to be computationally wasteful. Also, those packages that do have the extended Euclidean algorithm are generally written for a univariate polynomial. The above extended Euclidean algorithm improves the mentioned de ciencies. It is a fast approach in doing elimination of polynomial variables, similar to the Magma built-in resultant command. It is also used for computing a special polynomial called conductor element, denoted , with in the polynomial ring P of free variables. We will compute some timings below to show how e cient this extended Euclidean algorithm function is in eliminating or inverting and in computing . We note that, the computed using the extended Euclidean function may have higher degree than the one computed using the Magma built-in commands. 7.2.1 Inverting and eliminating The extended Euclidean function takes as input a function eld F, the number n, of variables in a polynomial ring P, two polynomials f and g in P and the ith variable in P to 99 be eliminated from g, relative to f. It is very useful in inverting polynomial ring elements. We will show a small example by hand and by using the above code. Consider the the curve f(y) = y3 + yx + x5 2F2[y;x]: Then f0(y) = y2 + x: We want to write 1f0(y) = g(y)D(x), for some g(y);D(x)2F2[y;x]: 1 f0(y) = 1 y2 +x = y y3 +yx = y x5: We have thus inverted y in the denominator of 1y2 +x. Using the extended Euclidean function, EEDXGCD, above we get q := 2; n := 2; P := PolynomialRing(GF(q);2); f := y3 +xy +x5; h := y2 +x; D;b;g := EEDXGCD(GF(q);n;P;f;h;1); D;b;g = x5;1;y which is exactly what we got earlier. Standard techniques for eliminating variables often rely on computing resultants. Consider the above example f := y3 +yx+x52F2[y;x]; h := y2 +x2F2[y;x]: Then standard techniques will invert y in h := y2 +x2F2[y;x] to produce 0 0 0 x5 0 0 0 x5 1 0 x 1 0 x 1 0 x = x10: 100 This is done by computing the resultant of f and h with respect to the variable y, denoted Res(f;h;y). However, this is generally computationally wasteful, when a straightforward extended Euclidean algorithm above gives a much better answer. (y3 +yx+x5) 1 + (y2 +x) y = x5 As mentioned earlier, the extended Euclidean function, EEDXCGD, can be used to eliminate variables. Let us consider the tower example xqi+1 +xi+1 = x q i xq 1i + 1; 1 i n: (7.1) by Stichtenoch et al [16]. Then for q = 2 and n = 3 we get the equations x1(x1 + 1)(x2 + 1) +x22 = 0 x2(x2 + 1)(x4 + 1) +x24 = 0 x4(x4 + 1)(x8 + 1) +x28 = 0 (7.2) Now de ne x12 := x4(x8 + 1); x14 := x2(x4 + 1)(x8 + 1) and x15 := x1(x2 + 1)(x4 + 1)(x8 + 1) (7.3) Using the extended Euclidean function, EEDXGCD, and ( 7.2) to eliminate the variables x1;x2 and x4 from the equation ( 7.3) we get x212 +x12x8 +x12 +x28 +x38 = 0 x214 +x14x12 +x14x8 +x14 +x12x28 = 0 x215 +x15x14 +x15x12 +x15x8 +x15 +x14x12 +x14x28 = 0 (7.4) 101 which does not have x1;x2 and x4 Magma has built-in commands that do elimination of variables. However, these built-in commands are very ine cient. Below are some timings of the above example 7.1, for various q and n, using both the extended Euclidean function, EEDXGCD, and Magma built-in commands. Table 7.2: Timing elimination via Magma commands versus EEDXGCD command values of q and n Timing elimination via Timing elimination Magma commands /sec via EEDXGCD /sec q = 2;n = 2 0:000 0:130 q = 2;n = 3 0:010 0:150 q = 2;n = 4 0:040 0:140 q = 2;n = 5 0:200 0:150 q = 2;n = 6 1:890 0:180 q = 2;n = 7 26:730 0:300 q = 2;n = 8 979:230 1:560 q = 2;n = 9 11:770 q = 3;n = 2 0:020 0:150 q = 3;n = 3 0:080 0:150 q = 3;n = 4 7:630 0:170 q = 3;n = 5 40631:220 0:310 7.2.2 n n minors of the jacobian and conductor element computations A typical approach to compute a suitable from the polynomial ring of free variables will be to compute all n n minors of the a Jacobian matrix and then compute a Gr obner basis. This approach is good for very small prime numbers and it also produces a of smaller degree that works faster with the qth-power algorithm. However, this approach is best for very small primes. Our approach computes by taking products of the nonzero leading diagonal entries of the Jacobian matrix. Our example here will be the tower above in equation 7.1, by Stichtenoch et al [16]. (Details of this tower are found in [16]). 102 Magma commands: Using Magma built-in commands to do the elimination and to compute , we get the following timings. Table 7.3: Timing Magma commands for elimination and computation values of q and n Timing Timing Timing Computed elimination /sec /sec qth power q = 2;n = 2 0:000 0:030 0:030 x24 q = 2;n = 3 0:010 0:000 0:030 x48 q = 2;n = 4 0:040 0:020 0:070 x816 q = 2;n = 5 0:200 0:150 0:340 x1632 q = 2;n = 6 1:890 1:030 2:040 x3264 q = 2;n = 7 26:730 8:320 13:800 x64128 q = 2;n = 8 979:230 84:370 86:870 x128256 q = 3;n = 2 0:020 0:000 0:090 x89 +x69 q = 3;n = 3 0:080 0:100 36:310 x2027 +x1827 q = 3;n = 4 7:630 8:160 131:880 x5681 +x5481 q = 3;n = 5 40631:220 2530:180 7141:200 x164243 +x162243 EEGCD function and Magma commands: Using our extended Euclidean division great- est common divisor function (EEGCD) to do the elimination and using Magma built-in commands to compute , we get the following timings. Table 7.4: Timing EEGCD to do elimination andMagma commands for computation values of q and n Timing Timing Timing Computed elimination /sec /sec qth power q = 2;n = 2 0:130 0:010 0:010 x24 q = 2;n = 3 0:150 0:000 0:030 x48 q = 2;n = 4 0:140 0:020 0:060 x816 q = 2;n = 5 0:150 0:150 0:350 x1632 q = 2;n = 6 0:180 1:060 2:040 x3264 q = 2;n = 7 0:300 8:380 12:800 x64128 q = 2;n = 8 1:560 80:210 85:470 x128256 q = 2;n = 9 11:770 5573:280 640:620 x265512 q = 3;n = 2 0:150 0:000 0:090 x89 +x69 q = 3;n = 3 0:150 0:100 101:640 x2027 +x1827 q = 3;n = 4 0:170 8:510 133:740 x5681 +x5481 q = 3;n = 5 0:310 2120:570 7181:200 x164243 +x162243 EEGCD function: Using our extended Euclidean division greatest common divisor function (EEGCD) to do the elimination and to compute , we get the following timings. 103 Table 7.5: Timing EEGCD function for elimination and computation values of q and n Timing Timing Timing Computed elimination /sec /sec qth power q = 2;n = 2 0:130 0:010 0:010 x34 +x24 q = 2;n = 3 0:130 0:000 0:090 x88 +x68 q = 2;n = 4 0:150 0:010 0:130 x1716 +x1616 +x1516 +x1416 q = 2;n = 5 0:140 0:010 0:880 x3432 +x3032 q = 2;n = 6 0:190 0:010 5:930 x6764 +x6664 +x6364 +x6264 q = 2;n = 7 0:300 0:090 40:770 x132128 +x130128 +x128128 + q = 2;n = 8 1:550 1:740 294:150 x261256 +x260256 +x260256 + q = 2;n = 9 11:860 139:470 2265:610 x518512 +x510512 q = 3;n = 2 0:150 0:000 0:250 x129 +x69 q = 3;n = 3 0:150 0:100 425:050 x5227 + 2x5027 +x4827 + q = 3;n = 4 0:170 0:140 481:460 x20081 +x19881 + 2x19481 + q = 3;n = 5 0:310 53:860 30226:170 x672243 +x654243 104 Chapter 8 Towers In this chapter we will consider some asymptotically good towers by Stichenoth el al, and Noam Elkies. We will transform some of the towers that are not type I form into curves that are type I. This will be done by nding the divisors of the curves. We will also compute a formula for the genus of some of the towers. We begin by de ning what we mean by a tower of function elds and asymptotically good towers. De nition 8.1 ([17], page 439). A tower of function elds over Fq is an in nite sequence F = (F0;F1;F2;:::) of function elds Fi=Fq having the properties: (i)F0 F1 F2 :::; and for each n 1 the extension Fn=Fn 1 is separable of degree [Fn : Fn 1] > 1. (ii)g(Fj) > 1 for some j 0. De nition 8.2 ([17], page 440). The tower F = (Fi)i 0 of functions elds over Fq is said to be asymptotically good, if (F) > 0; where (F) := lim i!1 N(Fi) g(Fi) : Here N(Fi); (respectively g(Fi)) is the number of Fq rational points (respectively the genus) of Fi: Let us now consider some towers and try to put them into type I curves. 8.1 Stichenoth towers 8.1.1 Example 1 Consider the rst tower zqn+1 +zn+1 = xq+1n with xn := znx n 1 ; 1 n m (8.1) 105 (See [21] for more about this tower and see [3] for more details on the one point description of this tower). So we have that xqnxq 1n 1 +xn = xqn 1; 1 n m (8.2) Let P0 be the unique point at which all the xqn have zeros and P1 be the point at which all have poles. Then from Leonard [3] page 2572, we have the divisors of xqn to be given by (xqn) = ( qn):P1 + X 1 i (m+1)=2 X j ( qn):Pi;j + X (m+1)=2 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