\documentclass[12pt]{article} \usepackage[active]{srcltx} \usepackage{graphicx} \input{macros} \hoffset=-0.05\textwidth \textwidth=1.1\textwidth \voffset=-0.08\textheight \textheight=1.16\textheight \title{Math 129: Algebraic Number Theory\\ {\bf Lecture 4}} \author{William Stein} \date{Tuesday, February 17, 2004} \begin{document} \maketitle Note: There's a book called {\em Algebraic Number Theory and Fermat's Last Theorem} by Stewart and Tall, which appears to have a detailed introduction to algebraic number theory and assumes little background on the part of the reader. There is a discussion of the definition of module, and proofs of basic facts about number fields, and many exercises. If you find Swinnerton-Dyer's book difficult, you might want to try to get your hands on Stewart and Tall, which costs about \$38 new. (Hand around a copy.) Today we will deduce, with complete proofs, the most important basic property of the ring of integers $\O_K$ of an algebraic number, namely that every nonzero ideals can be written uniquely as products of prime ideals. After proving this fundamental theorem, we will compute some examples using MAGMA. On Thursday the lecture will consist mostly of examples illustrating the substantial theory we will have already developed, so hang in there! \section{Dedekind Domains} \begin{corollary}\label{prop:intnoetherian} The ring of integers $\O_K$ of a number field is Noetherian. \end{corollary} \begin{proof} As we saw before using norms, the ring $\O_K$ is finitely generated as a module over~$\Z$, so it is certainly finitely generated as a ring over~$\Z$. By the Hilbert Basis Theorem, $\O_K$ is Noetherian. \end{proof} If $R$ is an integral domain, the {\em field of fractions} of $R$ is the field of all elements $a/b$, where $a,b \in R$. The field of fractions of $R$ is the smallest field that contains~$R$. For example, the field of fractions of $\Z$ is $\Q$ and of $\Z[(1+\sqrt{5})/2]$ is $\Q(\sqrt{5})$. \begin{definition}[Integrally Closed] An integral domain $R$ is {\em integrally closed in its field of fractions} if whenever $\alpha$ is in the field of fractions of $R$ and $\alpha$ satisfies a monic polynomial $f\in R[x]$, then $\alpha \in R$. \end{definition} \begin{proposition}\label{prop:integrallyclosed} If $K$ is any number field, then $\O_K$ is integrally closed. Also, the ring $\Zbar$ of all algebraic integers is integrally closed. \end{proposition} \begin{proof} We first prove that~$\Zbar$ is integrally closed. Suppose $c\in\Qbar$ is integral over~$\Zbar$, so there is a monic polynomial $f(x)=x^n + a_{n-1}x^{n-1} + \cdots + a_1 x + a_0$ with $a_i\in\Zbar$ and $f(c)=0$. The $a_i$ all lie in the ring of integers $\O_K$ of the number field $K=\Q(a_0,a_1,\ldots a_{n-1})$, and $\O_K$ is finitely generated as a $\Z$-module, so $\Z[a_0,\ldots, a_{n-1}]$ is finitely generated as a $\Z$-module. Since $f(c)=0$, we can write $c^n$ as a $\Z[a_0,\ldots, a_{n-1}]$-linear combination of $c^i$ for $i<n$, so the ring $\Z[a_0,\ldots, a_{n-1},c]$ is also finitely generated as a $\Z$-module. Thus $\Z[c]$ is finitely generated as $\Z$-module because it is a submodule of a finitely generated $\Z$-module, which implies that~$c$ is integral over~$\Z$. Suppose $c\in K$ is integral over $\O_K$. Then since $\Zbar$ is integrally closed,~$c$ is an element of $\Zbar$, so $c\in K \cap \Zbar=\O_K$, as required. \end{proof} \begin{definition}[Dedekind Domain] An integral domain~$R$ is a {\em Dedekind domain} if it is Noetherian, integrally closed in its field of fractions, and every nonzero prime ideal of $R$ is maximal. \end{definition} The ring $\Q\oplus \Q$ is Noetherian, integrally closed in its field of fractions, and the two prime ideals are maximal. However, it is not a Dedekind domain because it is not an integral domain. The ring $\Z[\sqrt{5}]$ is not a Dedekind domain because it is not integrally closed in its field of fractions, as $(1+\sqrt{5})/2$ is integrally over $\Z$ and lies in $\Q(\sqrt{5})$, but not in $\Z[\sqrt{5}]$. The ring $\Z$ is a Dedekind domain, as is any ring of integers $\O_K$ of a number field, as we will see below. Also, any field $K$ is a Dedekind domain, since it is a domain, it is trivially integrally closed in itself, and there are no nonzero prime ideals so that condition that they be maximal is empty. \begin{proposition} The ring of integers $\O_K$ of a number field is a Dedekind domain. \end{proposition} \begin{proof} By Proposition~\ref{prop:integrallyclosed}, the ring $\O_K$ is integrally closed, and by Proposition~\ref{prop:intnoetherian} it is Noetherian. Suppose that~$\p$ is a nonzero prime ideal of $\O_K$. Let $\alpha\in \p$ be a nonzero element, and let $f(x)\in\Z[x]$ be the minimal polynomial of~$\alpha$. Then $$f(\alpha)=\alpha^n+a_{n-1}\alpha^{n-1}+\cdots+a_1\alpha+a_0=0,$$ so $a_0 = -(\alpha^n+a_{n-1}\alpha^{n-1}+\cdots+a_1\alpha)\in \p$. Since $f$ is irreducible, $a_0$ is a nonzero element of $\Z$ that lies in~$\p$. Every element of the finitely generated abelian group $\O_K/\p$ is killed by~$a_0$, so $\O_K/\p$ is a finite set. Since~$\p$ is prime, $\O_K/\p$ is an integral domain. Every finite integral domain is a field, so $\p$ is maximal, which completes the proof. \end{proof} If $I$ and $J$ are ideals in a ring $R$, the product $IJ$ is the ideal generated by all products of elements in $I$ with elements in $J$: $$ IJ = (ab : a\in I, b\in J) \subset R. $$ Note that the set of all products $ab$, with $a\in I$ and $b\in J$, need not be an ideal, so it is important to take the ideal generated by that set. (See the homework problems for examples.) \begin{definition}[Fractional Ideal]\label{def:fracideal} A {\em fractional ideal} is an $\O_K$-submodule of $I\subset K$ that is finitely generated as an $\O_K$-module. \end{definition} To avoid confusion, we will sometimes call a genuine ideal $I\subset \O_K$ an {\em integral ideal}. Also, since fractional ideals are finitely generated, we can clear denominators of a generating set to see that every fractional ideal is of the form $a I = \{a b : b \in I\}$ for some $a\in K$ and ideal $I\subset \O_K$. For example, the collection $\frac{1}{2}\Z$ of rational numbers with denominator $1$ or $2$ is a fractional ideal of $\Z$. \begin{theorem}\label{thm:ddabgrp} The set of nonzero fractional ideals of a Dedekind domain~$R$ is an abelian group under ideal multiplication. \end{theorem} Before proving Theorem~\ref{thm:ddabgrp} we prove a lemma. For the rest of this section $\O_K$ is the ring of integers of a number field~$K$. \begin{definition}[Divides for Ideals] Suppose that $I,J$ are ideals of $\O_K$. Then~$I$ {\em divides}~$J$ if $I\supset J$. \end{definition} To see that this notion of divides is sensible, suppose $K=\Q$, so $\O_K=\Z$. Then $I=(n)$ and $J=(m)$ for some integer $n$ and $m$, and $I$ divides $J$ means that $(n)\supset (m)$, i.e., that there exists an integer~$c$ such that $m=cn$, which exactly means that $n$ divides $m$, as expected. \begin{lemma}\label{lem:divprod} Suppose~$I$ is an ideal of $\O_K$. Then there exist prime ideals $\p_1,\ldots, \p_n$ such that $\p_1\cdot \p_2\cdots \p_n \subset{}I$. In other words,~$I$ divides a product of prime ideals. (By convention the empty product is the unit ideal. Also, if $I=0$, then we take $\p_1=(0)$, which is a prime ideal.) \end{lemma} \begin{proof} The key idea is to use that $\O_K$ is Noetherian to deduce that the set~$S$ of ideals that do not satisfy the lemma is empty. If~$S$ is nonempty, then because $\O_K$ is Noetherian, there is an ideal $I\in S$ that is maximal as an element of~$S$. If~$I$ were prime, then~$I$ would trivially contain a product of primes, so~$I$ is not prime. By definition of prime ideal, there exists $a,b\in \O_K$ such that $ab\in I$ but $a\not\in I$ and $b\not\in I$. Let $J_1 = I+(a)$ and $J_2=I+(b)$. Then neither $J_1$ nor $J_2$ is in $S$, since $I$ is maximal, so both $J_1$ and $J_2$ contain a product of prime ideals. Thus so does $I$, since $$J_1 J_2 = I^2 + I(b)+ (a)I+ (ab) \subset I,$$ which is a contradiction. Thus~$S$ is empty, which completes the proof. \end{proof} We are now ready to prove the theorem. \begin{proof}[Proof of Theorem~\ref{thm:ddabgrp}] The product of two fractional ideals is again finitely generated, so it is a fractional ideal, and $I\O_K=\O_K$ for any nonzero ideal~$I$, so to prove that the set of fractional ideals under multiplication is a group it suffices to show the existence of inverses. We will first prove that if $\p$ is a prime ideal, then $\p$ has an inverse, then we will prove that nonzero integral ideals have inverses, and finally observe that every fractional ideal has an inverse. Suppose $\p$ is a nonzero prime ideal of $\O_K$. We will show that the $\O_K$-module $$ I = \{a \in K : a\p \subset \O_K \} $$ is a fractional ideal of $\O_K$ such that $I\p = \O_K$, so that $I$ is an inverse of $\p$. For the rest of the proof, fix a nonzero element $b\in \p$. Since~$I$ is an $\O_K$-module, $bI\subset \O_K$ is an $\O_K$ ideal, hence~$I$ is a fractional ideal. Since $\O_K \subset I$ we have $\p \subset I \p \subset \O_K$, hence either $\p = I\p$ or $I\p = \O_K$. If $I\p=\O_K$, we are done since then~$I$ is an inverse of~$\p$. Thus suppose that $I\p=\p$. Our strategy is to show that there is some $d\in I$ not in $\O_K$; such a~$d$ would leave~$\p$ invariant (i.e., $d \p \subset \p$), so since $\p$ is an $\O_K$-module it will follow that $d\in \O_K$, a contradiction. By Lemma~\ref{lem:divprod}, we can choose a product $\p_1,\ldots, \p_m$, with~$m$ minimal, such that $$ \p_1\p_2\cdots \p_m \subset (b) \subset \p. $$ If no $\p_i$ is contained in $\p$, then we can choose for each $i$ an $a_i \in \p_i$ with $a_i\not\in \p$; but then $\prod a_i\in \p$, which contradicts that $\p$ is a prime ideal. Thus some $\p_i$, say $\p_1$, is contained in $\p$, which implies that $\p_1 = \p$ since every nonzero prime ideal is maximal. Because~$m$ is minimal, $\p_2\cdots \p_m$ is not a subset of $(b)$, so there exists $c\in \p_2\cdots \p_m$ that does not lie in $(b)$. Then $\p(c) \subset (b)$, so by definition of $I$ we have $d=c/b\in I$. However, $d\not\in \O_K$, since if it were then $c$ would be in $(b)$. We have thus found our element $d\in I$ that does not lie in $\O_K$. To finish the proof that $\p$ has an inverse, we observe that $d$ preserves the $\O_K$-module $\p$, and is hence in $\O_K$, a contradiction. More precisely, if $b_1,\ldots, b_n$ is a basis for $\p$ as a $\Z$-module, then the action of~$d$ on~$\p$ is given by a matrix with entries in $\Z$, so the minimal polynomial of $d$ has coefficients in $\Z$. This implies that $d$ is integral over $\Z$, so $d\in \O_K$, since $\O_K$ is integrally closed by Proposition~\ref{prop:integrallyclosed}. (Note how this argument depends strongly on the fact that $\O_K$ is integrally closed!) So far we have proved that if $\p$ is a prime ideal of $\O_K$, then $\p^{-1} = \{a \in \K : a\p \subset \O_K\}$ is the inverse of $\p$ in the monoid of nonzero fractional ideals of $\O_K$. As mentioned after Definition~\ref{def:fracideal}, every nonzero fractional ideal is of the form $aI$ for $a\in K$ and $I$ an integral ideal, so since $(a)$ has inverse $(1/a)$, it suffices to show that every integral ideal~$I$ has an inverse. If not, then there is a nonzero integral ideal~$I$ that is maximal among all nonzero integral ideals that do not have an inverse. Every ideal is contained in a maximal ideal, so there is a nonzero prime ideal $\p$ such that $I\subset \p$. Then $I \subset \p^{-1} I \subset \O_K$. If $I = \p^{-1} I$, then (arguing as in the previous paragraph) each element of $\p^{-1}$ preserves that $\O_K$-ideal~$I$ and is hence integral, so $\p^{-1}\subset \O_K$, which implies that $\O_K = \p \p^{-1} \subset \p$, a contradiction. Thus $I \neq \p^{-1} I$. Because $I$ is maximal among ideals that do not have an inverse, the ideal $\p^{-1} I$ does have an inverse, call it~$J$. Then $\p{}J$ is the inverse of $I$, since $\O_K = (\p{}J)(\p^{-1}I) = JI$. \end{proof} We can finally deduce the crucial Theorem~\ref{thm:intuniqfac}, which will allow us to show that any nonzero ideal of a Dedekind domain can be expressed uniquely as a product of primes (up to order). Thus unique factorization holds for ideals in a Dedekind domain, and it is this unique factorization that initially motivated the introduction of rings of integers of number fields over a century ago. \begin{theorem}\label{thm:uniqfac} Suppose $I$ is an integral ideal of $\O_K$. Then $I$ can be written as a product $$ I = \p_1\cdots \p_n $$ of prime ideals of $\O_K$, and this representation is unique up to order. (Exception: If $I=0$, then the representation is not unique.) \end{theorem} \begin{proof} Suppose $I$ is an ideal that is maximal among the set of all ideals in $\O_K$ that can not be written as a product of primes. Every ideal is contained in a maximal ideal, so $I$ is contained in a nonzero prime ideal $\p$. If $I\p^{-1} = I$, then by Theorem~\ref{thm:ddabgrp} we can cancel $I$ from both sides of this equation to see that $\p^{-1}=\O_K$, a contradiction. Thus $I$ is strictly contained in $I\p^{-1}$, so by our maximality assumption on $I$ there are maximal ideals $\p_1,\ldots, \p_n$ such that $I\p^{-1} = \p_1\cdots \p_n$. Then $I=\p\cdot \p_1\cdots \p_n$, a contradiction. Thus every ideal can be written as a product of primes. Suppose $\p_1\cdots \p_n=\q_1\cdots \q_m$. If no $\q_i$ is contained in $\p_1$, then for each $i$ there is an $a_i\in \q_i$ such that $a_i\not\in\p_1$. But the product of the $a_i$ is in the $\p_1\cdots \p_n$, which is a subset of $\p_1$, which contradicts the fact that $\p_1$ is a prime ideal. Thus $\q_i=\p_1$ for some~$i$. We can thus cancel $\q_i$ and $\p_1$ from both sides of the equation. Repeating this argument finishes the proof of uniqueness. \end{proof} \begin{corollary}\label{thm:intuniqfac} If $I$ is a fractional ideal of $\O_K$ then there exists prime ideals $\p_1,\ldots, \p_n$ and $\q_1,\ldots, \q_m$, unique up to order, such that $$ I = (\p_1\cdots \p_n)(\q_1\cdots \q_m)^{-1}. $$ \end{corollary} \begin{proof} We have $I=(a/b)J$ for some $a,b\in\O_K$ and integral ideal $J$. Applying Theorem~\ref{thm:intuniqfac} to $(a)$, $(b)$, and $J$ gives an expression as claimed. For uniqueness, if one has two such product expressions, multiply through by the denominators and use the uniqueness part of Theorem~\ref{thm:intuniqfac} \end{proof} \section{Using MAGMA} This section is a first introduction to MAGMA, which is an excellent package for doing algebraic number theory computations. You can use it via the web page \verb|http://modular.fas.harvard.edu/calc|. MAGMA is not free, but if you would like a copy for your personal computer, send me an email, and I can arrange for you to obtain a legal copy for free. (Say something about my visiting MAGMA in Sydney three times, and how MAGMA compares to Maple, Mathematica, and PARI.) \begin{enumerate} \item MAGMA web page %\item Pictures of some people who work for MAGMA %\item Claus Fieker is responsible for much of the algebraic number %theory code in MAGMA. \item Example code to illustrate things so far in course, and relevant to each homework problems. Experiment with students suggesting what examples to try. \end{enumerate} \section{Algorithms for Algebraic Number Theory} The best overall reference for algorithms for doing basic algebraic number theory computations is Henri Cohen's book {\em A Course in Computational Algebraic Number Theory}, Springer, GTM 138. Our main long-term algorithmic goals for this course are to understand good algorithms for solving the following problems in particular cases: \begin{itemize} \item {\bf Ring of integers:} Given a number field $K$ (by giving a polynomial), compute the full ring $\O_K$ of integers. \item {\bf Decomposition of primes:} Given a prime number $p\in\Z$, find the decomposition of the ideal $p\O_K$ as a product of prime ideals of $\O_K$. \item {\bf Class group:} Compute the group of equivalence classes of nonzero ideals of $\O_K$, where $I$ and $J$ are equivalent if there exists $\alpha \in \O_K$ such that $IJ^{-1}=(\alpha)$. \item {\bf Units:} Compute generators for the group of units of $\O_K$. \end{itemize} As we will see, somewhat surprisingly it turns out that algorithmically by far the most time-consuming step in computing the ring of integers $\O_K$ is to factor the discriminant of a polynomial whose root generates the field~$K$. The algorithm(s) for computing $\O_K$ are quite complicated to describe, but the first step is to factor this discriminant, and it takes much longer in practice than all the other complicated steps. \end{document}