Sharedwww / lectures / day4.texOpen in CoCalc
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}