WIXLIB

1.3. SOME APPLICATIONS OF ALGEBRAIC NUMBER THEORY11sage : rsa768 1 2 3 0 1 8 6 6 8 4 5 3 0 1 1 7 7 5 5 1 3 0 4 9 4 9 5 8 3 8 4 9 6 2 7 2 0 7 7 2 8 5 3 5 6 9 5 9 5 3 3 4 7 9 4080665351419597459856902143413sage : n 3 3 4 7 8 0 7 1 6 9 8 9 5 6 8 9 8 7 8 6 0 4 4 1 6 9 8 4 8 2 1 2 6 9 0 8 1 7 7 0 4 7 9 4 9 8 3 7 1 3 7 6 8 5 6 8 9 1 2 67999489sage : m 3 6 7 4 6 0 4 3 6 6 6 7 9 9 5 9 0 4 2 8 2 4 4 6 3 3 7 9 9 6 2 7 9 5 2 6 3 2 2 7 9 1 5 8 1 6 4 3 4 3 0 8 7 6 4 2 6 7 6 36308917sage : n * m rsa768TrueThis record integer factorization cracked a certain 768-bit public key cryptosystem (see http://eprint.iacr.org/2010/006), thus establishing a lowerbound on one’s choice of key size: man ssh-keygen# in ubuntu-12.04.-b bitsSpecifies the number of bits in the key to create.For RSA keys, the minimum size is 768 bits .2. Primality testing: Agrawal and his students Saxena and Kayal from Indiafound in 2002 the first ever deterministic polynomial-time (in the numberof digits) primality test. There methods involve arithmetic in quotients of(Z/nZ)[x], which are best understood in the context of algebraic numbertheory.3. Deeper point of view on questions in number theory:(a) Pell’s Equation x2 dy 2 1 can be reinterpreted in terms of units in realquadratic fields, which leads to a study of unit groups of number fields.(b) Integer factorization leads to factorization of nonzero ideals in rings ofintegers of number fields.(c) The Riemann hypothesis about the zeros of ζ(s) generalizes to zeta functions of number fields.(d) Reinterpreting Gauss’s quadratic reciprocity law in terms of the arithmetic of cyclotomic fields Q(e2πi/n ) leads to class field theory, which inturn leads to the Langlands program.4. Wiles’s proof of Fermat’s Last Theorem, i.e., that the equation xn y n z nhas no solutions with x, y, z, n all positive integers and n 3, uses methodsfrom algebraic number theory extensively, in addition to many other deep techniques. Attempts to prove Fermat’s Last Theorem long ago were hugely influential in the development of algebraic number theory by Dedekind, Hilbert,Kummer, Kronecker, and others.

12CHAPTER 1. INTRODUCTION5. Arithmetic geometry: This is a huge field that studies solutions to polynomial equations that lie in arithmetically interesting rings, such as the integersor number fields. A famous major triumph of arithmetic geometry is Faltings’sproof of Mordell’s Conjecture.Theorem 1.3.1 (Faltings). Let X be a nonsingular plane algebraic curve overa number field K. Assume that the manifold X(C) of complex solutions to Xhas genus at least 2 (i.e., X(C) is topologically a donut with two holes). Thenthe set X(K) of points on X with coordinates in K is finite.For example, Theorem 1.3.1 implies that for any n 4 and any numberfield K, there are only finitely many solutions in K to xn y n 1.A major open problem in arithmetic geometry is the Birch and SwinnertonDyer conjecture. An elliptic curves E is an algebraic curve with at least onepoint with coordinates in K such that the set of complex points E(C) is atopological torus. The Birch and Swinnerton-Dyer conjecture gives a criterionfor whether or not E(K) is infinite in terms of analytic properties of the Lfunction L(E, s). See http://www.claymath.org/millennium/Birch andSwinnerton-Dyer Conjecture/.

Part IAlgebraic Number Fields13

Chapter 2Basic Commutative AlgebraThe commutative algebra in this chapter provides a foundation for understandingthe more refined number-theoretic structures associated to number fields.First we prove the structure theorem for finitely generated abelian groups. Thenwe establish the standard properties of Noetherian rings and modules, including aproof of the Hilbert basis theorem. We also observe that finitely generated abeliangroups are Noetherian Z-modules. After establishing properties of Noetherian rings,we consider rings of algebraic integers and discuss some of their properties.2.1Finitely Generated Abelian GroupsFinitely generated abelian groups arise all over algebraic number theory. For example, they will appear in this book as class groups, unit groups, and the underlyingadditive groups of rings of integers, and as Mordell-Weil groups of elliptic curves.In this section, we prove the structure theorem for finitely generated abeliangroups, since it will be crucial for much of what we will do later.Let Z {0, 1, 2, . . .} denote the ring of (rational) integers, and for eachpositive integer n, let Z/nZ denote the ring of integers modulo n, which is a cyclicabelian group of order n under addition.Definition 2.1.1 (Finitely Generated). A group G is finitely generated if thereexists g1 , . . . , gn G such that every element of G can be expressed as a finiteproduct (or sum, if we write G additively) of positive or negative powers of the gi .For example, the group Z is finitely generated, since it is generated by 1.Theorem 2.1.2 (Structure Theorem for Finitely Generated Abelian Groups). LetG be a finitely generated abelian group. Then there is an isomorphismG (Z/n1 Z) (Z/n2 Z) · · · (Z/ns Z) Zr ,where r, s 0, n1 1 and n1 n2 · · · ns . Furthermore, the ni and r are uniquelydetermined by G.15

16CHAPTER 2. BASIC COMMUTATIVE ALGEBRAWe will prove the theorem as follows. We first remark that any subgroup ofa finitely generated free abelian group is finitely generated. Then we see how torepresent finitely generated abelian groups as quotients of finite rank free abeliangroups, and how to reinterpret such a presentation in terms of matrices over theintegers. Next we describe how to use row and column operations over the integersto show that every matrix over the integers is equivalent to one in a canonicaldiagonal form, called the Smith normal form. We obtain a proof of the theorem byreinterpreting Smith normal form in terms of groups. Finally, we observe that therepresentation in the theorem is necessarily unique.Proposition 2.1.3. If H is a subgroup of a finitely generated abelian group, thenH is finitely generated.The key reason that this is true is that G is a finitely generated module over theprincipal ideal domain Z. We defer the proof of Proposition 2.1.3 to Section 2.2,where we will give a complete proof of a beautiful generalization in the context ofNoetherian rings (the Hilbert basis theorem).Corollary 2.1.4. Suppose G is a finitely generated abelian group. Then thereare finitely generated free abelian groups F1 and F2 and there is a homomorphismψ : F2 F1 such that G F1 /ψ(F2 ).Proof. Let x1 , . . . , xm be generators for G. Let F1 Zm and let ϕ : F1 G be thehomomorphism that sends the ith generator (0, 0, . . . , 1, . . . , 0) of Zm to xi . Then ϕis surjective, and by Proposition 2.1.3 the kernel ker(ϕ) of ϕ is a finitely generatedabelian group. Suppose there are n generators for ker(ϕ), let F2 Zn and fix asurjective homomorphism ψ : F2 ker(ϕ). Then F1 /ψ(F2 ) is isomorphic to G.An sequence of homomorphisms of abelian groupsfgH G Kis exact if im(f ) ker(g). Given a finitely generated abelian group G, Corollary 2.1.4 provides an exact sequenceψF2 F1 G 0.Suppose G is a nonzero finitely generated abelian group. By the corollary, thereare free abelian groups F1 and F2 and there is a homomorphism ψ : F2 F1 suchthat G F1 /ψ(F2 ). Upon choosing a basis for F1 and F2 , we obtain isomorphismsF1 Zn and F2 Zm for integers n and m. Just as in linear algebra, we viewψ : F2 F1 as being given by left multiplication by the n m matrix A whosecolumns are the images of the generators of F2 in Zn . We visualize this as follows:[TODO: add a commutative diagram]The cokernel of the homomorphism defined by A is the quotient of Zn by theimage of A (i.e., the Z-span of the columns of A), and this cokernel is isomorphicto G.

2.1. FINITELY GENERATED ABELIAN GROUPS17The following proposition implies that we may choose a bases for F1 and F2such that the matrix of A only has nonzero entries along the diagonal, so that thestructure of the cokernel of A is trivial to understand.Proposition 2.1.5 (Smith normal form). Suppose A is an n m integer matrix.Then there exist invertible integer matrices P and Q such that A0 P AQ onlyhas nonzero entries along the diagonal, and these entries are n1 , n2 , . . . , ns , 0, . . . , 0,where s 0, n1 1 and n1 n2 · · · ns . Here P and Q are invertible as integermatrices, so det(P ) and det(Q) are 1. The matrix A0 is called the Smith normalform of A.We will see in the proof of Theorem 2.1.2 that A0 is uniquely determined by A.An example of a matrix in Smith normal form is 2 0 0 0A 0 6 0 0 .0 0 0 0Proof. The matrix P will be a product of matrices that define elementary rowoperations and Q will be a product corresponding to elementary column operations.The elementary row and column operations over Z are as follows:1. [Add multiple] Add an integer multiple of one row to another (or a multipleof one column to another).2. [Swap] Interchange two rows or two columns.3. [Rescale] Multiply a row by 1.Each of these operations is given by left or right multiplying by an invertible matrix E with integer entries, where E is the result of applying the given operationto the identity matrix, and E is invertible because each operation can be reversedusing another row or column operation over the integers.To see that the proposition must be true, assume A 6 0 and perform the following steps (compare [Art91, pg. 459]):1. By permuting rows and columns, move a nonzero entry of A with smallestabsolute value to the upper left corner of A. Now “attempt” (as explained indetail below) to make all other entries in the first row and column 0 by addingmultiples of the top row or first column to other rows or columns, as follows:Suppose ai1 is a nonzero entry in the first column, with i 1. Usingthe division algorithm, write ai1 a11 q r, with 0 r a11 . Nowadd q times the first row to the ith row. If r 0, then go tostep 1 (so that an entry with absolute value at most r is the upperleft corner).

18CHAPTER 2. BASIC COMMUTATIVE ALGEBRAIf at any point this operation produces a nonzero entry in the matrix withabsolute value smaller than a11 , start the process over by permuting rowsand columns to move that entry to the upper left corner of A. Since theintegers a11 are a decreasing sequence of positive integers, we will not haveto move an entry to the upper left corner infinitely often, so when this step isdone the upper left entry of the matrix is nonzero, and all entries in the firstrow and column are 0.2. We may now assume that a11 is the only nonzero entry in the first row andcolumn. If some entry aij of A is not divisible by a11 , add the column of Acontaining aij to the first column, thus producing an entry in the first columnthat is nonzero. When we perform step 2, the remainder r will be greaterthan 0. Permuting rows and columns results in a smaller a11 . Since a11 canonly shrink finitely many times, eventually we will get to a point where everyaij is divisible by a11 . If a11 is negative, multiple the first row by 1.After performing the above operations, the first row and column of A are zero exceptfor a11 which is positive and divides all other entries of A. We repeat the abovesteps for the matrix B obtained from A by deleting the first row and column. Theupper left entry of the resulting matrix will be divisible by a11 , since every entry ofB is. Repeating the argument inductively proves the proposition. 1 0 1 2, and thehas Smith normal formExample 2.1.6. The matrix 3 40 2 1 4 91 0 0 matrix 16 25 36 has Smith normal form 0 3 0 . As a double check,49 64 810 0 72note that the determinants of a matrix and its Smith normal form match, up tosign. This is becausedet(P AQ) det(P ) det(A) det(Q) det(A).We compute each of the above Smith forms using Sage, along with the corresponding transformation matrices. First the 2 2 matrix.

2.1. FINITELY GENERATED ABELIAN GROUPS19sage: A matrix(ZZ, 2, [-1,2, -3,4])sage: S, U, V A.smith form(); S[1 0][0 2]sage: U*A*V[1 0][0 2]sage: U[ 0 1][ 1 -1]sage: V[1 4][1 3]The Sage matrix command takes as input the base ring, the number of rows, andthe entries. Next we compute with a 3 3 matrix.sage: A matrix(ZZ, 3, [1,4,9, 16,25,36, 49,64,81])sage: S, U, V A.smith form(); S[ 1 0 0][ 0 3 0][ 0 0 72]sage: U*A*V[ 1 0 0][ 0 3 0][ 0 0 72]sage: U[ 001][ 01 -1][ 1 -20 -17]sage: V[ 477493][ -79 -125 -156][ 345467]Finally we compute the Smith form of a matrix of rank 2:sage: m matrix(ZZ, 3, [2.10]); m[ 2 3 4][ 5 6 7][ 8 9 10]sage: m.smith form()[0][1 0 0][0 3 0][0 0 0]

20CHAPTER 2. BASIC COMMUTATIVE ALGEBRATheorem 2.1.2. Suppose G is a finitely generated abelian group, which we mayassume is nonzero. As in the paragraph before Proposition 2.1.5, we use Corollary 2.1.4 to write G as a the cokernel of an n m integer matrix A. By Proposition 2.1.5 there are isomorphisms Q : Zm Zm and P : Zn Zn such thatA0 P AQ has diagonal entries n1 , n2 , . . . , ns , 0, . . . , 0, where n1 1 and n1 n2 . . . ns . Then G is isomorphic to the cokernel of the diagonal matrix A0 , soG (Z/n1 Z) (Z/n2 Z) · · · (Z/ns Z) Zr ,(2.1.1)as claimed. The ni are determined by G, because ni is the smallest positive integer nsuch that nG requires at most s r i generators. We see from the representation(2.1.1) of G as a product that ni has this property and that no smaller positiveinteger does.2.2Noetherian Rings and ModulesA module M over a commutative ring R with unit element is much like a vectorspace, but with more subtle structure. In this book, most of the modules we encounter will be noetherian, which is a generalization of the “finite dimensional”property of vector spaces. This section is about properties of noetherian modules(and rings), which are crucial to much of this book. We thus give complete proofsof these properties, so you will have a solid foundation on which to learn algebraicnumber theory.We first define noetherian rings and modules, then introduce several equivalentcharacterizations of them. We prove that when the base ring is noetherian, a moduleis finitely generated if and only if it is noetherian. Next we define short exactsequences, and prove that the middle module in a sequence is noetherian if andonly if the first and last modules are noetherian. Finally, we prove the Hilbert basistheorem, which asserts that adjoining finitely many elements to a noetherian ringresults in a noetherian ring.Let R be a commutative ring with unity. An R-module is an additive abeliangroup M equipped with a map R M M such that for all r, r0 R and allm, m0 M we have (rr0 )m r(r0 m), (r r0 )m rm r0 m, r(m m0 ) rm rm0 ,and 1m m. A submodule of M is a subgroup of M that is preserved by the actionof R. For example, R is a module over itself, and any ideal I in R is an R-submoduleof R.Example 2.2.1. Abelian groups are the same as Z-modules, and vector spaces overa field K are the same as K-modules.An R-module M is finitely generated if there are elements m1 , . . . , mn Msuch that every element of M is an R-linear combination of the mi . The noetherianproperty is stronger than just being finitely generated:

2.2. NOETHERIAN RINGS AND MODULES21Definition 2.2.2 (Noetherian). An R-module M is noetherian if every submoduleof M is finitely generated. A ring R is noetherian if R is noetherian as a moduleover itself, i.e., if every ideal of R is finitely generated.Any submodule M 0 of a noetherian module M is also noetherian. Indeed, ifevery submodule of M is finitely generated then so is every submodule of M 0 , sincesubmodules of M 0 are also submodules of M .Example 2.2.3. Let R M Q[x1 , x2 , . . .] be a polynomial ring over Q in infinitelymany indeterminants xi . Then M is finitely generated as an R-module (!), since itis generated by 1. Consider the submodule I (x1 , x2 , . . .) of polynomials with 0constant term, and suppose it is generated by polynomials f1 , . . . , fn . Let xi be anindeterminantthat does not appear in any fj , and suppose there are hk R suchPthat nk 1 hk fk xi . Setting xi 1 and all other xj 0 on both sides of thisequation and using that the fk all vanish (they have 0 constant term), yields 0 1,a contradiction. We conclude that the ideal I is not finitely generated, hence M isnot a noetherian R-module, despite being finitely generated.Definition 2.2.4 (Ascending chain condition). An R-module M satisfies the ascending chain condition if every sequence M1 M2 M3 · · · of submodules of Meventually stabilizes, i.e., there is some n such that Mn Mn 1 Mn 2 · · · .We will use the notion of maximal element below. If X is a set of subsets of aset S, ordered by inclusion, then a maximal element A X is a set such that nosuperset of A is contained in X . Note that X may contain many different maximalelements.Proposition 2.2.5. If M is an R-module, then the following are equivalent:1. M is noetherian,2. M satisfies the ascending chain condition, and3. Every nonempty set of submodules of M contains at least one maximal element.Proof. 1 2: Suppose M1 M2 · · · is a sequence of submodules of M .Then M n 1 Mn is a submodule of M . Since M is noetherian and M isa submodule of M , there is a finite set a1 , . . . , am of generators for M . Each aimust be contained in some Mj , so there is an n such that a1 , . . . , am Mn . Butthen Mk Mn for all k n, which proves that the chain of Mi stabilizes, so theascending chain condition holds for M .2 3: Suppose 3 were false, so there exists a nonempty set S of submodulesof M that does not contain a maximal element. We will use S to construct aninfinite ascending chain of submodules of M that does not stabilize. Note that S isinfinite, otherwise it would contain a maximal element. Let M1 be any element of S.Then there is an M2 in S that cont

10 CHAPTER 1. INTRODUCTION can be represented as the set of all polynomials of degree at most d [K: Q] dim Q Kin a single root of some polynomial with coe cients in Q: K Q( ) (Xm n 0 a n n: a n2Q Algebraic number theory involves using techniques from (mostly commutative)