CoCalc Public Fileswww / lectures / day4.tex
Author: William A. Stein
1\documentclass[12pt]{article}
2\usepackage[active]{srcltx}
3\usepackage{graphicx}
4\input{macros}
5\hoffset=-0.05\textwidth
6\textwidth=1.1\textwidth
7\voffset=-0.08\textheight
8\textheight=1.16\textheight
9
10\title{Math 129: Algebraic Number Theory\\
11{\bf Lecture 4}}
12\author{William Stein}
13\date{Tuesday, February 17, 2004}
14\begin{document}
15\maketitle
16
17Note: There's a book called {\em Algebraic Number Theory and Fermat's
18Last Theorem} by Stewart and Tall, which appears to have a detailed
19introduction to algebraic number theory and assumes little background
20on the part of the reader. There is a discussion of the definition of
21module, and proofs of basic facts about number fields, and many
22exercises.  If you find Swinnerton-Dyer's book difficult, you might
23want to try to get your hands on Stewart and Tall, which costs about
24\$38 new. (Hand around a copy.) 25 26Today we will deduce, with complete proofs, the most important basic 27property of the ring of integers$\O_K$of an algebraic number, namely 28that every nonzero ideals can be written uniquely as products of prime 29ideals. After proving this fundamental theorem, we will compute some 30examples using MAGMA. On Thursday the lecture will consist mostly of 31examples illustrating the substantial theory we will have already 32developed, so hang in there! 33 34\section{Dedekind Domains} 35\begin{corollary}\label{prop:intnoetherian} 36The ring of integers$\O_K$of a number field is Noetherian. 37\end{corollary} 38\begin{proof} 39As we saw before using norms, the ring$\O_K$is finitely generated as 40a module over~$\Z$, so it is certainly finitely generated as a ring 41over~$\Z$. By the Hilbert Basis Theorem,$\O_K$is Noetherian. 42\end{proof} 43 44If$R$is an integral domain, the {\em field of fractions} of$R$is 45the field of all elements$a/b$, where$a,b \in R$. The field of 46fractions of$R$is the smallest field that contains~$R$. For 47example, the field of fractions of$\Z$is$\Q$and of 48$\Z[(1+\sqrt{5})/2]$is$\Q(\sqrt{5})$. 49 50\begin{definition}[Integrally Closed] 51An integral domain$R$is {\em integrally closed in its field of 52fractions} if whenever$\alpha$is in the field of fractions of$R$53and$\alpha$satisfies a monic polynomial$f\in R[x]$, then$\alpha
54\in R$. 55\end{definition} 56 57\begin{proposition}\label{prop:integrallyclosed} 58If$K$is any number field, then$\O_K$is integrally closed. Also, 59the ring$\Zbar$of all algebraic integers is integrally closed. 60\end{proposition} 61\begin{proof} 62We first prove that~$\Zbar$is integrally closed. Suppose$c\in\Qbar$63is integral over~$\Zbar$, so there is a monic polynomial$f(x)=x^n +
64a_{n-1}x^{n-1} + \cdots + a_1 x + a_0$with$a_i\in\Zbar$and 65$f(c)=0$. The$a_i$all lie in the ring of integers$\O_K$of the 66number field$K=\Q(a_0,a_1,\ldots a_{n-1})$, and$\O_K$is finitely 67generated as a$\Z$-module, so$\Z[a_0,\ldots, a_{n-1}]$is finitely 68generated as a$\Z$-module. Since$f(c)=0$, we can write$c^n$as a 69$\Z[a_0,\ldots, a_{n-1}]$-linear combination of$c^i$for$i<n$, so 70the ring$\Z[a_0,\ldots, a_{n-1},c]$is also finitely generated as a 71$\Z$-module. Thus$\Z[c]$is finitely generated as$\Z$-module 72because it is a submodule of a finitely generated$\Z$-module, which 73implies that~$c$is integral over~$\Z$. 74 75Suppose$c\in K$is integral over$\O_K$. Then since$\Zbar$is 76integrally closed,~$c$is an element of$\Zbar$, so$c\in K \cap
77\Zbar=\O_K$, as required. 78\end{proof} 79 80\begin{definition}[Dedekind Domain] 81An integral domain~$R$is a {\em Dedekind domain} if it is Noetherian, 82integrally closed in its field of fractions, and every nonzero prime 83ideal of$R$is maximal. 84\end{definition} 85The ring$\Q\oplus \Q$is Noetherian, integrally closed in its field 86of fractions, and the two prime ideals are maximal. However, it is 87not a Dedekind domain because it is not an integral domain. The ring 88$\Z[\sqrt{5}]$is not a Dedekind domain because it is not integrally 89closed in its field of fractions, as$(1+\sqrt{5})/2$is integrally 90over$\Z$and lies in$\Q(\sqrt{5})$, but not in$\Z[\sqrt{5}]$. The 91ring$\Z$is a Dedekind domain, as is any ring of integers$\O_K$of a 92number field, as we will see below. Also, any field$K$is a Dedekind 93domain, since it is a domain, it is trivially integrally closed in 94itself, and there are no nonzero prime ideals so that condition that 95they be maximal is empty. 96 97\begin{proposition} 98The ring of integers$\O_K$of a number field is a Dedekind domain. 99\end{proposition} 100\begin{proof} 101By Proposition~\ref{prop:integrallyclosed}, the ring$\O_K$is 102integrally closed, and by Proposition~\ref{prop:intnoetherian} it is 103Noetherian. Suppose that~$\p$is a nonzero prime ideal of$\O_K$. 104Let$\alpha\in \p$be a nonzero element, and let$f(x)\in\Z[x]$be the 105minimal polynomial of~$\alpha$. Then 106$$f(\alpha)=\alpha^n+a_{n-1}\alpha^{n-1}+\cdots+a_1\alpha+a_0=0,$$ so 107$a_0 = -(\alpha^n+a_{n-1}\alpha^{n-1}+\cdots+a_1\alpha)\in \p$. Since 108$f$is irreducible,$a_0$is a nonzero element of$\Z$that lies 109in~$\p$. Every element of the finitely generated abelian group 110$\O_K/\p$is killed by~$a_0$, so$\O_K/\p$is a finite set. 111Since~$\p$is prime,$\O_K/\p$is an integral domain. Every finite 112integral domain is a field, so$\p$is maximal, which 113completes the proof. 114\end{proof} 115 116If$I$and$J$are ideals in a ring$R$, the product$IJ$is the ideal 117generated by all products of elements in$I$with elements in$J$: 118$$119 IJ = (ab : a\in I, b\in J) \subset R. 120$$ 121Note that the set of all products$ab$, with$a\in I$and$b\in J$, 122need not be an ideal, so it is important to take the ideal generated 123by that set. (See the homework problems for examples.) 124 125\begin{definition}[Fractional Ideal]\label{def:fracideal} 126A {\em fractional ideal} is an$\O_K$-submodule of$I\subset K$that 127is finitely generated as an$\O_K$-module. 128\end{definition} 129To avoid confusion, we will sometimes call a genuine ideal$I\subset
130\O_K$an {\em integral ideal}. Also, since fractional ideals are 131finitely generated, we can clear denominators of a generating set to 132see that every fractional ideal is of the form$a I = \{a b : b \in
133I\}$for some$a\in K$and ideal$I\subset \O_K$. 134 135For example, the collection$\frac{1}{2}\Z$of rational numbers with 136denominator$1$or$2$is a fractional ideal of$\Z$. 137 138\begin{theorem}\label{thm:ddabgrp} 139The set of nonzero fractional ideals of a Dedekind domain~$R$is an 140abelian group under ideal multiplication. 141\end{theorem} 142Before proving Theorem~\ref{thm:ddabgrp} we prove a lemma. For the 143rest of this section$\O_K$is the ring of integers of a number 144field~$K$. 145 146 147\begin{definition}[Divides for Ideals] 148Suppose that$I,J$are ideals of$\O_K$. 149Then~$I${\em divides}~$J$if$I\supset J$. 150\end{definition} 151To see that this notion of divides is sensible, suppose$K=\Q$, so 152$\O_K=\Z$. Then$I=(n)$and$J=(m)$for some integer$n$and$m$, and 153$I$divides$J$means that$(n)\supset (m)$, i.e., that there exists 154an integer~$c$such that$m=cn$, which exactly means that$n$divides 155$m$, as expected. 156 157\begin{lemma}\label{lem:divprod} 158Suppose~$I$is an ideal of$\O_K$. Then there exist prime ideals 159$\p_1,\ldots, \p_n$such that$\p_1\cdot \p_2\cdots \p_n \subset{}I$. 160In other words,~$I$divides a product of prime ideals. (By convention 161the empty product is the unit ideal. Also, if$I=0$, then we take 162$\p_1=(0)$, which is a prime ideal.) 163\end{lemma} 164\begin{proof} 165The key idea is to use that$\O_K$is Noetherian to deduce that the 166set~$S$of ideals that do not satisfy the lemma is empty. If~$S$is 167nonempty, then because$\O_K$is Noetherian, there is an ideal$I\in
168S$that is maximal as an element of~$S$. If~$I$were prime, then~$I$169would trivially contain a product of primes, so~$I$is not prime. By 170definition of prime ideal, there exists$a,b\in \O_K$such that$ab\in
171I$but$a\not\in I$and$b\not\in I$. Let$J_1 = I+(a)$and 172$J_2=I+(b)$. Then neither$J_1$nor$J_2$is in$S$, since$I$is 173maximal, so both$J_1$and$J_2$contain a product of prime ideals. 174Thus so does$I$, since 175$$J_1 J_2 = I^2 + I(b)+ (a)I+ (ab) \subset I,$$ 176which is a contradiction. Thus~$S$is empty, which completes the proof. 177\end{proof} 178 179We are now ready to prove the theorem. 180 181\begin{proof}[Proof of Theorem~\ref{thm:ddabgrp}] 182The product of two fractional ideals is again finitely generated, so 183it is a fractional ideal, and$I\O_K=\O_K$for any nonzero ideal~$I$, 184so to prove that the set of fractional ideals under multiplication is 185a group it suffices to show the existence of inverses. We will first 186prove that if$\p$is a prime ideal, then$\p$has an inverse, then we 187will prove that nonzero integral ideals have inverses, and finally 188observe that every fractional ideal has an inverse. 189 190Suppose$\p$is a nonzero prime ideal of$\O_K$. We will show that 191the$\O_K$-module 192$$193 I = \{a \in K : a\p \subset \O_K \} 194$$ 195is a fractional ideal of$\O_K$such that$I\p = \O_K$, so that 196$I$is an inverse of$\p$. 197 198For the rest of the proof, fix a nonzero element$b\in \p$. Since~$I$199is an$\O_K$-module,$bI\subset \O_K$is an$\O_K$ideal, hence~$I$is 200a fractional ideal. Since$\O_K \subset I$we have$\p \subset I \p
201\subset \O_K$, hence either$\p = I\p$or$I\p = \O_K$. If 202$I\p=\O_K$, we are done since then~$I$is an inverse of~$\p$. Thus 203suppose that$I\p=\p$. Our strategy is to show that there is some 204$d\in I$not in$\O_K$; such a~$d$would leave~$\p$invariant (i.e., 205$d \p \subset \p$), so since$\p$is an$\O_K$-module it will follow 206that$d\in \O_K$, a contradiction. 207 208By Lemma~\ref{lem:divprod}, we can choose a product$\p_1,\ldots, \p_m$, 209with~$m$minimal, such that 210$$211\p_1\p_2\cdots \p_m \subset (b) \subset \p. 212$$ If no$\p_i$is contained in$\p$, then we can choose for each$i$213an$a_i \in \p_i$with$a_i\not\in \p$; but then$\prod a_i\in \p$, 214which contradicts that$\p$is a prime ideal. Thus some$\p_i$, say 215$\p_1$, is contained in$\p$, which implies that$\p_1 = \p$since 216every nonzero prime ideal is maximal. Because~$m$is minimal, 217$\p_2\cdots \p_m$is not a subset of$(b)$, so there exists$c\in
218\p_2\cdots \p_m$that does not lie in$(b)$. Then$\p(c) \subset (b)$, 219so by definition of$I$we have$d=c/b\in I$. However,$d\not\in
220\O_K$, since if it were then$c$would be in$(b)$. We have thus 221found our element$d\in I$that does not lie in$\O_K$. To finish the 222proof that$\p$has an inverse, we observe that$d$preserves the 223$\O_K$-module$\p$, and is hence in$\O_K$, a contradiction. More 224precisely, if$b_1,\ldots, b_n$is a basis for$\p$as a$\Z$-module, 225then the action of~$d$on~$\p$is given by a matrix with entries in 226$\Z$, so the minimal polynomial of$d$has coefficients in$\Z$. This 227implies that$d$is integral over$\Z$, so$d\in \O_K$, since$\O_K$228is integrally closed by Proposition~\ref{prop:integrallyclosed}. 229(Note how this argument depends strongly on the fact that$\O_K$is 230integrally closed!) 231 232So far we have proved that if$\p$is a prime ideal of$\O_K$, then 233$\p^{-1} = \{a \in \K : a\p \subset \O_K\}$is the inverse of$\p$in 234the monoid of nonzero fractional ideals of$\O_K$. As mentioned after 235Definition~\ref{def:fracideal}, every nonzero fractional ideal is of 236the form$aI$for$a\in K$and$I$an integral ideal, so since$(a)$237has inverse$(1/a)$, it suffices to show that every integral ideal~$I$238has an inverse. If not, then there is a nonzero integral ideal~$I$239that is maximal among all nonzero integral ideals that do not have an 240inverse. Every ideal is contained in a maximal ideal, so there is a 241nonzero prime ideal$\p$such that$I\subset \p$. Then$I \subset
242\p^{-1} I \subset \O_K$. If$I = \p^{-1} I$, then (arguing as in the 243previous paragraph) each element of$\p^{-1}$preserves that 244$\O_K$-ideal~$I$and is hence integral, so$\p^{-1}\subset \O_K$, 245which implies that$\O_K = \p \p^{-1} \subset \p$, a contradiction. 246Thus$I \neq \p^{-1} I$. Because$I$is maximal among ideals that do 247not have an inverse, the ideal$\p^{-1} I$does have an inverse, call 248it~$J$. Then$\p{}J$is the inverse of$I$, since$\O_K =
249(\p{}J)(\p^{-1}I) = JI$. 250\end{proof} 251 252We can finally deduce the crucial Theorem~\ref{thm:intuniqfac}, which 253will allow us to show that any nonzero ideal of a Dedekind domain can 254be expressed uniquely as a product of primes (up to order). Thus 255unique factorization holds for ideals in a Dedekind domain, and it is 256this unique factorization that initially motivated the introduction of 257rings of integers of number fields over a century ago. 258 259\begin{theorem}\label{thm:uniqfac} 260Suppose$I$is an integral ideal of$\O_K$. Then$I$can 261be written as a product 262$$263 I = \p_1\cdots \p_n 264$$ of prime ideals of$\O_K$, and this representation is unique up to 265order. (Exception: If$I=0$, then the representation is not unique.) 266\end{theorem} 267\begin{proof} 268Suppose$I$is an ideal that is maximal among the set of all ideals in 269$\O_K$that can not be written as a product of primes. Every ideal is 270contained in a maximal ideal, so$I$is contained in a nonzero prime 271ideal$\p$. If$I\p^{-1} = I$, then by Theorem~\ref{thm:ddabgrp} we 272can cancel$I$from both sides of this equation to see that 273$\p^{-1}=\O_K$, a contradiction. Thus$I$is strictly contained in 274$I\p^{-1}$, so by our maximality assumption on$I$there are maximal 275ideals$\p_1,\ldots, \p_n$such that$I\p^{-1} = \p_1\cdots \p_n$. 276Then$I=\p\cdot \p_1\cdots \p_n$, a contradiction. Thus every ideal 277can be written as a product of primes. 278 279Suppose$\p_1\cdots \p_n=\q_1\cdots \q_m$. If no$\q_i$is contained in 280$\p_1$, then for each$i$there is an$a_i\in \q_i$such that 281$a_i\not\in\p_1$. But the product of the$a_i$is in the$\p_1\cdots
282\p_n$, which is a subset of$\p_1$, which contradicts the fact that 283$\p_1$is a prime ideal. Thus$\q_i=\p_1$for some~$i$. We can thus 284cancel$\q_i$and$\p_1$from both sides of the equation. Repeating 285this argument finishes the proof of uniqueness. 286\end{proof} 287 288\begin{corollary}\label{thm:intuniqfac} 289If$I$is a fractional ideal of$\O_K$then there exists 290prime ideals$\p_1,\ldots, \p_n$and$\q_1,\ldots, \q_m$, 291unique up to order, such that 292$$293 I = (\p_1\cdots \p_n)(\q_1\cdots \q_m)^{-1}. 294$$ 295\end{corollary} 296\begin{proof} 297We have$I=(a/b)J$for some$a,b\in\O_K$and integral ideal$J$. 298Applying Theorem~\ref{thm:intuniqfac} to$(a)$,$(b)$, and$J$gives 299an expression as claimed. For uniqueness, if one has two such product 300expressions, multiply through by the denominators and use the 301uniqueness part of Theorem~\ref{thm:intuniqfac} 302\end{proof} 303 304\section{Using MAGMA} 305This section is a first introduction to MAGMA, which is an excellent 306package for doing algebraic number theory computations. You can use 307it via the web page \verb|http://modular.fas.harvard.edu/calc|. MAGMA 308is not free, but if you would like a copy for your personal computer, 309send me an email, and I can arrange for you to obtain a legal copy for 310free. (Say something about my visiting MAGMA in Sydney three times, 311and how MAGMA compares to Maple, Mathematica, and PARI.) 312 313\begin{enumerate} 314\item MAGMA web page 315%\item Pictures of some people who work for MAGMA 316%\item Claus Fieker is responsible for much of the algebraic number 317%theory code in MAGMA. 318\item Example code to illustrate things so far in course, and relevant 319to each homework problems. Experiment with students suggesting what 320examples to try. 321\end{enumerate} 322 323 324\section{Algorithms for Algebraic Number Theory} 325The best overall reference for algorithms for doing basic algebraic 326number theory computations is Henri Cohen's book {\em A Course in 327Computational Algebraic Number Theory}, Springer, GTM 138. 328 329Our main long-term algorithmic goals for this course are to understand 330good algorithms for solving the following problems in particular 331cases: 332\begin{itemize} 333\item {\bf Ring of integers:} Given a number field$K$(by giving a 334polynomial), compute the full ring$\O_K$of integers. 335\item {\bf Decomposition of primes:} Given a prime number$p\in\Z$, find the 336decomposition of the ideal$p\O_K$as a product 337of prime ideals of$\O_K$. 338\item {\bf Class group:} Compute the group of equivalence classes 339of nonzero ideals of$\O_K$, where$I$and$J$340are equivalent if there exists$\alpha \in \O_K$341such that$IJ^{-1}=(\alpha)$. 342\item {\bf Units:} Compute generators for the group of 343units of$\O_K$. 344\end{itemize} 345 346As we will see, somewhat surprisingly it turns out that 347algorithmically by far the most time-consuming step in computing the 348ring of integers$\O_K$is to factor the discriminant of a polynomial 349whose root generates the field~$K$. The algorithm(s) for computing 350$\O_K\$ are quite complicated to describe, but the first step is to
351factor this discriminant, and it takes much longer in practice than
352all the other complicated steps.
353
354\end{document}