\documentclass[12pt]{article}
\usepackage{amsmath, amsthm, amsfonts}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{0in}
\setlength{\textheight}{8.5in}
\setlength{\topmargin}{0in}
\setlength{\headheight}{0in}
\setlength{\headsep}{0in}
\setlength{\parskip}{0pt}
\setlength{\parindent}{20pt}


\newtheorem{theorem}{Theorem}
\newtheorem{cor}{Corollary}

\def\ssym{\sum_{\mathrm{sym}}}
\def\QQ{\mathbb{Q}}
\def\ZZ{\mathbb{Z}}

\begin{document}

\begin{center}
  \textbf{\large Number Theory II: What is an algebraic number \\ 
and why should I care?} \\
\medskip
  \textbf{Kiran Kedlaya} \\
\textbf{Berkeley Math Circle, December 10, 2000}
\end{center}

\section{Basic facts}

I'll answer half of the title question immediately. For the purposes of
this talk, an \emph{algebraic number} is a complex number which is the root
of a polynomial with integer coefficients. An \emph{algebraic integer} is
an algebraic number which is the root of a monic polynomial with integer
coefficients.

I'll say more about why you should care later. For now, let me just give a
bunch of examples to convince you that algebraic numbers crop up all over
the place.
\begin{itemize}
\item
A rational number is an algebraic number; a rational number is an algebraic
integer if and only if it is an integer. For clarity, I'll refer to the usual
integers as the \emph{rational integers}.
\item
For any rational number $p/q$, the root of unity $e^{2\pi i p/q}$ satisfies the
polynomial $x^q - 1 = 0$, and so is an algebraic integer.
\item
A \emph{Gaussian integer}, a number of the form $a+bi$, is an algebraic
integer.
\item
For any rational number $p/q$, the numbers $\cos (2\pi p/q)$ and $\sin (2\pi p/q)$ are algebraic integers, and $\tan (2\pi p/q)$ is an algebraic number.
Can you explicitly write down polynomials that these are roots of? (These
polynomials turn out to have lots of interesting properties.)
\item
Given a recurrence relation $x_{n+k} = a_1 x_{n+k-1} + \cdots + a_k x_n$ with
(rational) integer coefficients, all solutions can be expressed in terms of some algebraic
integers. For example, the $n$-th Fibonacci number can be written as
\[
\frac{1}{\sqrt{5}} \left[ \left( \frac{1+\sqrt{-5}}{2} \right)^n
- \left( \frac{1 - \sqrt{-5}}{2} \right)^n \right].
\]
\item
The eigenvalues of a matrix with (rational)
integer entries are algebraic integers.
This is one way algebraic numbers come up in topology, group theory, algebraic
geometry, combinatorics, etc.
\end{itemize}

Here are some basic facts about algebraic numbers. These may not be obvious
at first; I'll mention two ways to prove them in a moment.
\begin{enumerate}
\item
The set of algebraic numbers is closed under addition, subtraction,
multiplication and division. The set of algebraic integers is closed under
addition, subtraction and multiplication, but not division.
\item
The root
of a polynomial whose coefficients are algebraic numbers (resp., algebraic
integers) is one also.
\end{enumerate}

The first method involves symmetric polynomials, which are interesting enough
in their own right that I'll discuss them in some detail.
\begin{theorem}
Let $P$ be a symmetric polynomial (with integer coefficients)
in $x_1, \dots, x_n$. Then $P$ can be expressed as a polynomial 
(with integer coefficients) in
the elementary symmetric functions $\sigma_1, \dots, \sigma_n$ given
by
\[
t^n + \sigma_1 t^{n-1} + \cdots + \sigma_n = 
(t+x_1)\cdots (t+x_n).
\]
\end{theorem}
For example, $\sigma_1 = x_1 + \cdots + x_n$,
$\sigma_2 = \sum_{i<j} x_ix_j$, and so on.

The proof of this is a successive elimination argument of a form quite common
in computational algebraic geometry. It's related to something called a
``Gr\"obner basis''.
\begin{proof}
The idea is to deal with the terms of $P$ ``from the outside in''. That is,
we first deal with terms which are as ``unbalanced'' as possible.

We can write
\[
P = \sum_{a_1\geq \cdots \geq a_n}
\ssym c_{a_1,\dots,a_n} x_1^{a_1}\cdots x_n^{a_n}.
\]
We put an ordering on $n$-tuples by saying that $(a_1, \dots, a_n)
> (b_1, \dots, b_n)$ if and only if $na_1 + (n-1)a_2 + \cdots + a_n
> nb_1 + (n-1)b_2 + \cdots + b_n$.
Now sort the terms in decreasing order by $na_1+(n-1)a_2+\cdots+a_n$.
Choose the biggest term $(a_1, \dots, a_n)$ and notice that the polynomial
\[
\sigma_1^{a_1-a_2} \cdots \sigma_{n-1}^{a_{n-1}-a_n} \sigma_n^{a_n}
\]
has the same largest term, and the coefficient of that term is 1.
So subtract off $c_{a_1,\dots,a_n}$ times this product, and repeat.
\end{proof}

I'll demonstrate why this is a useful fact by showing that the product of two
algebraic integers is an algebraic integer. Given two algebraic integers
which are the roots of the monic polynomials $P$ and $Q$ with rational
integer coefficients, let $\alpha_1, \dots, \alpha_m$ and
$\beta_1, \dots, \beta_n$ be the roots of $P$ and $Q$, respectively.
Now consider the polynomial
\[
\prod_{i=1}^m \prod_{j=1}^n (x - \alpha_i \beta_j).
\]
Now $\prod_{j=1}^n (x - \alpha_i \beta_j)$ can be viewed as a symmetric
polynomial in $\beta_1, \dots, \beta_n$, if I treat $x$ and $\alpha_i$
as constant. (More precisely, if I look at all terms with a fixed power of
$x$ and $\alpha_i$, these together form a symmetric polynomial in the $\beta_i$). By the theorem, this polynomial is a polynomial in the elementary symmetric
functions of the $\beta_i$, which by assumption are integers. So we now have
a polynomial in $x$ and $\alpha_i$ with integer coefficients; we now take
the product over the $\alpha_i$ and repeat the argument.

The second, more modern method, uses some linear algebra. The main idea is
that $\alpha$ is an algebraic number if and only if $1, \alpha, \alpha^2,
\dots$ lie in a finite dimensional vector space over $\QQ$. So to show that
$\alpha \beta$ is algebraic given that $\alpha$ and $\beta$ are, suppose
$\alpha$ satisfies a polynomial of degree $m$ and $\beta$ satisfies a
polynomial of degree $n$ over $\QQ$. Then all of the products
$\alpha^i \beta^j$ lie in the vector space spanned by $\alpha^k \beta^l$
for $k < m, l < n$. In particular, all of the $(\alpha \beta)^i$ lie in
a finite dimensional vector space, so $\alpha \beta$ is algebraic.

\section{Unique and nonunique factorization}

It's easier to study algebraic numbers as part of a larger structure than
on their own. So we define a \emph{number field} to be the smallest set
containing $\QQ$ plus some finite set $\alpha_1, \dots, \alpha_n$ of algebraic
numbers, which is also closed under addition, subtraction, multiplication
and division.
We'll usually denote this number field $\QQ(\alpha_1, \dots, \alpha_n)$.
We define a \emph{ring of integers} to be the set of algebraic
integers in a number field.

WARNING: it's not always obvious what the ring of integers in a number
field is. Take the example $\QQ(\sqrt{D})$ ($D$ positive or negative).
If $D \equiv 1 \pmod{4}$, then
$(1 + \sqrt{-D})/2$ is an algebraic integer; more generally, the integers
in the number field are $(a + b\sqrt{-D})/2$ for $a,b$ rational integers of the
same parity. If $D \equiv 2, 3 \pmod{4}$, then the only integers in
the number field are the obvious ones $a + b \sqrt{-D}$ for $a,b$
rational integers.

One nice property about the rational integers is unique factorization.
Is unique factorization true for other rings of integers? Sometimes yes,
sometimes no.

To make that precise, we'll need some more definitions.
define a \emph{unit} to be an algebraic integer whose reciprocal is
also an algebraic integer. (For example, roots of unity are units, but there
are other units too; we'll see some later.)
We call an element $\alpha$ of a ring of integers \emph{irreducible} if 
whenever you write $\alpha = \beta \gamma$ as the product of two elements
of the ring, one of $\beta$ or $\gamma$ is a unit. (I didn't say ``prime''
because I'm saving that word for later).
We say a ring of integers has \emph{unique factorization} if whenever
an element of a ring of integers is expressed as a product of irreducible
elements, that expression is unique up to changing the order and multiplying
by units.

For example, the Gaussian integers have unique factorization,
because they admit an analogue of the Euclidean division algorithm.
\begin{theorem}
Given Gaussian integers $p$ and $q$ with $q \neq 0$,
there exist Gaussian integers $r$ and $s$ with $p = qr+s$ and $|s| < |q|$.
\end{theorem}
\begin{proof}
Draw the square with vertices $0, q, iq, (1+i)q$. Then $p$
is congruent to a Gaussian integer $z$
inside (or on the boundary of) the square.
Also, the open discs of radius $|q|$ centered at $0, q, iq, (1+i)q$ cover
the square completely, so $z$ is within $|q|$ of one corner of the square,
say $w$. Now take $s=z-w$; then $|s| < |q|$ and $s \equiv p \pmod{q}$,
so we can set $r = (p-s)/q$ and we're done.
\end{proof}
\begin{cor}
Every (rational) prime congruent to 1 modulo 4 is the sum of two squares;
moreover, this expression is unique up to order and signs.
\end{cor}
\begin{proof}
If $p \equiv 1 \pmod{4}$, then there exist $x$ and $y$ such that
$x^2+y^2$ is divisible by $p$ but not by $p^2$. Apply the Euclidean algorithm
in the Gaussian integers (left for you to write down!) to $x+iy$ and $p$;
the result will be a Gaussian integer $r+si$ with $r^2+s^2=p$. Uniqueness
is also left to you.
\end{proof}

EXERCISE: Find some other rings of integers which have unique factorization.
(For starters, try $\ZZ[\sqrt{-2}]$ and $\ZZ[(1+\sqrt{-3})/2]$.

On the other hand, consider this example in $\ZZ[\sqrt{-5}]$:
\[
6 = 2 \cdot 3 = (1 + \sqrt{-5})(1 - \sqrt{-5}).
\]
None of 2, 3, or $1 \pm \sqrt{-5}$ can be written as a nontrivial
product of two elements of $\ZZ[\sqrt{-5}]$, so this ring doesn't have
unique factorization. What to do?

Kummer realized that one could find an algebraic integer in a bigger ring
that would allow you to break up such problem factorizations. (For example,
if we toss in $\sqrt{2}$, then it divides both $1+\sqrt{-5}$ and $2$.)
However, it turns out that it's a little better to work not
with these ``ideal numbers'', as Kummer called them, but with the collection
of their multiples.

Definition: an \emph{ideal} in a ring of integers $R$ is a subset
$S$ such that
\begin{enumerate}
\item
for $x,y \in S$, $x+y \in S$;
\item
if $x \in S$ and $r \in r$, then $xr \in S$.
\end{enumerate}
Example: If $R = \ZZ$, then an ideal is an arithmetic progression containing 0.
More general example: the \emph{principal ideal} generated by $r \in R$ consists
of all multiples of $r$. But not all ideals have this form!

Because of the way an ideal is defined, we can work ``modulo'' an ideal, that is,
it makes sense to write $a \equiv b \pmod{I}$ because this equivalence respects
addition and multiplication. If $I$ is nonzero, then the number of equivalence
classes modulo $I$ is finite; we call this number the \emph{norm} of the ideal.

An ideal $I$ is \emph{prime} if $xy \in I$ implies $x \in I$ or $y \in I$. For
example, if $R = \ZZ$ and $I = (n)$, then $I$ is prime if and only if $n$ is prime. In general, if $I$ has prime norm, it is a prime ideal, but the converse
is not true; we only know that $I$ has prime power norm. For example, the
ideal $(3)$ in $\ZZ[i]$ is prime, but its norm is 9.

The arithmetic on $\ZZ[i]/(3)$ is not the same as on $\ZZ/(9)$, though! 
The main distinction is that in $\ZZ[i]/(3)$,
everything not congruent to 0 mod $(3)$
has a multiplicative inverse. (Thus $\ZZ[i]/(3)$ is an example of a
\emph{finite field}.)

The big theorem about prime ideals is the recovery of unique
factorization.
\begin{theorem}
Every nonzero ideal in a ring of integers has a unique prime factorization.
\end{theorem}
\begin{cor}
If every ideal of a ring of integers $R$ is principal, then $R$ has unique 
factorization. (Note: the converse is also true.)
\end{cor}

Two ideals $I$ and $J$ in the ring of integers $R$ of a number field $K$
are \emph{equivalent}
if there exists $k \in K$ such 
that $kI = J$. (Note that $k$ need not lie in $R$. If you prefer a definition
within $R$: $I$ and $J$ are equivalent if there exist nonzero $i,j \in R$
such that $iI = jJ$.)
This equivalence is respected by multiplication.
\begin{theorem}[Minkowski]
The number of equivalence classes of ideals in a ring of integers is finite.
\end{theorem}
This number is called the \emph{class number} of the number field.

\begin{theorem}[Gauss]
For $n > 3$ not divisible by 4,
the number of primitive (having no common factor)
triples $(x,y,z)$ of integers such that $x^2+y^2+z^2=n$ is equal to
12 times the class number of $\QQ(\sqrt{-n})$ if $n \equiv 1, 2 \pmod{4}$,
or 24 times the class number of $\QQ(\sqrt{-n})$ if $n \equiv 3 \pmod{4}$.
\end{theorem}
Note: Gauss didn't express this theorem in terms of number fields,
but in terms of binary quadratic forms $ax^2+bxy+cy^2$ whose discriminant
$b^2-4ac$ equals $-4n$, if $n \equiv 1, 2 \pmod{4}$,
or $-n$, if $n \equiv 3 \pmod{4}$. Two forms are equivalent if you can get
from one to the other by making a variable substitution of the form
$u = px+qy, v=rx+sy$ where $p,q,r,s$ are integers with $ps-qr=1$.

EXERCISE: Prove that
the number of equivalence classes of forms equals the class number
of $\QQ(\sqrt{-n})$.

\section{Diophantine equations}
One important use of algebraic numbers is to answer questions about Diophantine
equations. We have already seen one example of this (representing an integer
as the sum of two squares); let's consider a few more examples.

The equation $x^2 - Dy^2=1$ is (mis)named ``Pell's equation''. Over $\QQ(\sqrt{-D})$,
we can factor the left side and rewrite the equation as
\[
(x+y\sqrt{D})(x - y \sqrt{D}) = 1.
\]
This makes clear the multiplicative structure of the set of solutions: if
$(a,b)$ and $(c,d)$ are solutions, then
\begin{align*}
1 &= (a+b\sqrt{D})(c+d\sqrt{D})(a-b\sqrt{D})(c-d\sqrt{D}) \\
&= [(ac+bdD)+(ad+bc)\sqrt{D}][(ac+bdD)-(ad+bc)\sqrt{D}] \\
&= (ac+bdD)^2 - D(ad+bc)^2.
\end{align*}
Moreover, we can sort all solutions into increasing order by
$x+y\sqrt{D}$ (which is an increasing function of $x$ for $x\geq 0$,
given that $x^2-Dy^2=1$). Now it's easy to see that all solutions
in positive integers are ``powers'' of the smallest solution, assuming
that any solutions exist.

There are several ways to show that solutions exist. One method uses continued
fractions and has been known at least for 1000 years (it occurs in an old
Indian text); it is probably the best method for explicitly computing
solutions.

ASIDE: What does this have to do with algebraic numbers? What we've done is
to classify the algebraic integers in the field $\QQ(\sqrt{D})$ whose products
with their conjugates equal 1. An analogous classification can be made for
an arbitrary number field, which solves the Pell equation along the way.

What about the equation $x^2-Dy^2=n$ when $n \neq 1$? The situation is
more complicated, so one needs to know a bit more to make progress.
For example,
given that $\QQ(\sqrt{2})$ has unique factorization, one can prove the
following.
(Note the resemblance to the proof that a prime $p \equiv 1 \pmod{4}$ is the
sum of two squares.)
\begin{theorem}
For $n$ a squarefree integer, the equation $x^2-2y^2=n$ has a solution
in integers if and only if it has a solution modulo $n$.
\end{theorem}
\begin{proof}
By multiplicativity, it suffices to show that $x^2-2y^2=n$ has a solution
for $n=-1$, $n=2$, and $n=p$ for $p$ an odd prime such that $2$ is congruent
to a square modulo $p$. For $n=-1$, use $1^2-2\cdot 1^2=-1$; for $n=2$,
use $2^2 - 2\cdot 1^2 = 2$.

Now suppose $p$ is an odd prime such that $2$ is congruent to a square
modulo $p$. Find $x,y$ such that $x^2-2y^2$ is divisible by $p$ but not
by $p^2$ (if it is divisible by $p^2$, fix that by replacing $x$ with
$x+p$). Now form the ideal $(x+y\sqrt{D}, p)$. Its norm divides $p^2$
and $x^2-2y^2$, so it must be $p$.
\end{proof}
Incidentally, one can replace 2 by any integer $D$ such that $\QQ(\sqrt{D})$
has unique factorization, provided that $x^2-Dy^2=-1$ has a solution. It turns
out (but is by no means obvious!) that unique factorization implies that $D$
is prime, and it is believed (but not proved) that $\QQ(\sqrt{D})$ has
unique factorization for about $75\%$ of the primes $D$.
Moreover, existence of a solution of $x^2-Dy^2=1$
then implies $D \equiv 1 \pmod{4}$, but not every prime congruent to 1 modulo
4 will work (try $D=5$).

For an example of a different flavor,
let us find the solutions of the equation $x^2+2=y^3$.
In the ring $\ZZ[\sqrt{-2}]$, which has unique factorization, this factors as
\[
(x+\sqrt{-2})(x - \sqrt{-2}) = y^3.
\]
Note that $x$ must be odd: if $x$ were even, then $x^2+2$ would be divisible
by 2 but not by 4, so could not be a perfect cube. Therefore
the ideals $(x+\sqrt{-2})$ and $(x-\sqrt{-2})$ are relatively prime,
and each must be the cube of an ideal. That is, $x + \sqrt{-2}$
and $x - \sqrt{-2}$ are equal to a unit (which can only be $\pm 1$) times
a a cube. In particular, we have
\[
x + \sqrt{-2} = (a+b\sqrt{-2})^3
= (a^3-6ab^2) + (3a^2 b - 2b^3) \sqrt{-2}.
\]
In particular, $3a^2 b - b^3 = 1$. Since this is a multiple of $b$, we
must have $b = \pm 1$. If $b=1$, then $3a^2-2 = 1$, so $a=1$ and $x= 5$.
If $b=-1$, then $-3a^2+2=1$, which is impossible.

ASIDE: We didn't actually need unique factorization: the argument still
would go through if we just knew that the number field had class number
not divisible by 3.

Additional examples:
\begin{enumerate}
\item 
One can prove the law of quadratic reciprocity by working with number fields
containing roots of unity. (Quadratic reciprocity will be described in Oaz's talk.)
\item
Lam\'e gave a proof of Fermat's Last Theorem for $p$-th powers assuming that the
number field $\QQ(e^{2\pi i/p})$ has unique factorization. Unfortunately, this only
holds for finitely many primes $p$. Fortunately, Kummer gave a proof that also works
if the class number of $\QQ(e^{2 \pi i/p})$ is not divisible by $p$. Unfortunately,
no one has proved that there are infinitely many such $p$. Fortunately, numerical
evidence and heuristics suggest that about $60\%$ of primes have this property.
(More fortunately, Fermat's Last Theorem has now been proved by Wiles et al.)
\end{enumerate}

\section{Read all about it!}

There are tons of books on algebraic number theory out there (some of
which don't assume very much from classical number theory). Some titles
that come to mind (with commentary):
\begin{itemize}
\item
Esmonde and Murty, \emph{Problems in Algebraic Number Theory} (beware of
the many small errors, hopefully to be corrected in a future edition)
\item
Ireland and Rosen, \emph{A Classical Introduction to Modern Number
Theory} (a pretty good read, I'm told)
\item
Lang, \emph{Algebraic Number Theory} (not an easy read, assumes undergraduate
algebra)
\item
Marcus, \emph{Number Fields} (mostly does examples)
\item
Neukirch, \emph{Algebraic Number Theory} (not to be confused with his
other books, which are very difficult reading)
\item
Pollard and Diamond, \emph{The Theory of Algebraic Numbers} (the avoidance
of abstract algebra makes this an easy read but obscures certain points)
\end{itemize}

\end{document}








