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