\chapter{Minkowski bound and class groups}
We now have a neat theory of unique factorization of ideals.
In the case of a PID, this in fact gives us a UFD. Sweet.

We'll define, in a moment, something called the \emph{class group}
which measures how far $\OO_K$ is from being a PID;
the bigger the class group, the farther $\OO_K$ is from being a PID.
In particular, the $\OO_K$ is a PID if it has trivial class group.

Then we will provide some inequalities which let us put restrictions on the class group;
for instance, this will let us show in some cases that the class group must be trivial.
Astonishingly, the proof will use Minkowski's theorem, a result from geometry.

\section{The class group}
\prototype{PID's have trivial class group.}
Let $K$ be a number field,
and let $J_K$ denote the multiplicative group of fractional ideals of $\OO_K$.
Let $P_K$ denote the multiplicative group of \vocab{principal fractional ideals}:
those of the form $(x) = x \OO_K$ for some $x \in K$.
\begin{ques}
Check that $P_K$ is also a multiplicative group.
(This is really easy: name $x\OO_K \cdot y\OO_K$ and $(x\OO_K)\inv$.)
\end{ques}
As $J_K$ is abelian, we can now define the \vocab{class group} to be the quotient
\[ \Cl_K \defeq J_K / P_K. \]
The elements of $\Cl_K$ are called \vocab{classes}.

Equivalently,
\begin{moral}
The class group $\Cl_K$ is the set of nonzero fractional ideals modulo
scaling by a constant in $K$.
\end{moral}
In particular, $\Cl_K$ is trivial if all ideals are principal,
since the nonzero principal ideals are the same up to scaling.

The size of the class group is called the \vocab{class number}.
It's a beautiful theorem that the class number is always finite,
and the bulk of this chapter will build up to this result.
It requires several ingredients.


\section{The discriminant of a number field}
\prototype{Quadratic fields.}
Let's say I have $K = \QQ(\sqrt 2)$.
As we've seen before, this means $\OO_K = \ZZ[\sqrt 2]$, meaning
\[ \OO_K = \left\{ a + b \sqrt 2 \mid a,b \in \ZZ \right\}. \]
The key insight now is that you might think of this as a \emph{lattice}:
geometrically, we want to think about this the same way we think about $\ZZ^2$.

Perversely, we might try to embed this into $\QQ^2$ by sending $a+b\sqrt 2$ to $(a, b)$.
But this is a little stupid, since we're rudely making $K$,
which somehow lives inside $\RR$ and is
``one-dimensional'' in that sense, into a two-dimensional space.
It also depends on a choice of basis, which we don't like.
A better way is to think about the fact that there are two embeddings
$\sigma_1 : K \to \CC$ and $\sigma_2 : K \to \CC$, namely the identity, and conjugation:
\begin{align*}
	\sigma_1(a+b\sqrt2) &= a+b\sqrt 2 \\
	\sigma_2(a+b\sqrt2) &= a-b\sqrt 2.
\end{align*}
Fortunately for us, these embeddings both have real image.
This leads us to consider the set of points
\[ \left( \sigma_1(\alpha), \sigma_2(\alpha) \right) \in \RR^2
\quad\text{as}\quad \alpha \in K. \]
This lets us visualize what $\OO_K$ looks like in $\RR^2$.
The points of $K$ are dense in $\RR^2$, but the points of $\OO_K$ cut out a lattice.

\begin{center}
	\begin{asy}
		size(8cm);
		real T = 1.414;
		int N = 10;
		real M = 5;
		for (int a = -N; a <= N; ++a) {
			for (int b = -N; b <= N; ++b) {
				if ((abs(a+T*b) <= M) && (abs(a-T*b) <= M))
				dot( (a+T*b, a-T*b) );
			}
		}
		draw( (-M,0)--(M,0), dotted);
		draw( (0,-M)--(0,M), dotted);
		label("$-2$", (-2,-2), dir(135));
		label("$-1$", (-1,-1), dir(135));
		label("$0$", (0,0), dir(135));
		label("$1$", (1,1), dir(135));
		label("$2$", (2,2), dir(135));
		label("$-\sqrt 2$", (-T,T), dir(135));
		label("$\sqrt 2$", (T,-T), dir(-45));
		label("$1+\sqrt 2$", (1+T,1-T), dir(-45));

		filldraw((0,0)--(1,1)--(1+T,1-T)--(T,-T)--cycle, heavycyan, blue);
	\end{asy}
\end{center}

To see how big the lattice is, we look at how $\{1, \sqrt2\}$, the generators
of $\OO_K$, behave.
The point corresponding to $a+b\sqrt2$ in the lattice is
\[ a \cdot (1,1) + b \cdot (\sqrt 2, -\sqrt 2). \]
The \vocab{mesh} of the lattice\footnote{Most authors call this the volume, but I
think this is not the right word to use -- lattices have ``volume'' zero since they
are just a bunch of points! In contrast, the English word ``mesh'' really
does refer to the width of a ``gap''.}
is defined as the hypervolume of the ``fundamental parallelepiped'' I've colored blue above.
For this particular case, it ought to be equal to the
area of that parallelogram, which is
\[
	\det
	\begin{bmatrix}
		1 & -\sqrt 2 \\
		1 & \sqrt 2
	\end{bmatrix}
	= 2\sqrt 2.
\]
The definition of the discriminant is precisely this, except with an extra square factor
(since permutation of rows could lead to changes in sign in the matrix above).
\Cref{prob:trace_discriminant} shows that the squaring makes $\Delta_K$ an integer.

To make the next definition, we invoke:
\begin{theorem}[The $n$ embeddings of a number field]
	Let $K$ be a number field of degree $n$.
	Then there are exactly $n$ field homomorphisms $K \injto \CC$,
	say $\sigma_1, \dots, \sigma_n$, which fix $\QQ$.
\end{theorem}
\begin{proof}
	Deferred to \Cref{thm:n_embeddings}, once we have the tools of Galois theory.
\end{proof}
In fact, in \Cref{thm:conj_distrb} we see that
for $\alpha \in K$, we have that $\sigma_i(\alpha)$
runs over the conjugates of $\alpha$ as $i=1,\dots,n$.
It follows that
\[
	\Tr_{K/\QQ}(\alpha) = \sum_{i=1}^n \sigma_i(\alpha)
	\quad\text{and}\quad
	\Norm_{K/\QQ}(\alpha) = \prod_{i=1}^n \sigma_i(\alpha).
\]

This allows us to define:
\begin{definition}
	Suppose $\alpha_1, \dots, \alpha_n$ is a $\ZZ$-basis of $\OO_K$.
	The \vocab{discriminant} of the number field $K$ is defined by
	\[
	\Delta_K \defeq \det
	\begin{bmatrix}
		\sigma_1(\alpha_1) & \dots & \sigma_n(\alpha_1) \\
		\vdots & \ddots & \vdots \\
		\sigma_1(\alpha_n) & \dots & \sigma_n(\alpha_n) \\
	\end{bmatrix}^2.
	\]
\end{definition}
This does not depend on the choice of the $\{\alpha_i\}$;
we will not prove this here.
\begin{example}[Discriminant of $K = \QQ(\sqrt2)$]
	We have $\OO_K = \ZZ[\sqrt 2]$
	and as discussed above the discriminant is
	\[
		\Delta_K =
		(-2 \sqrt 2)^2 = 8.
	\]
\end{example}
\begin{example}[Discriminant of $\QQ(i)$]
	Let $K = \QQ(i)$.
	We have $\OO_K = \ZZ[i] = \ZZ \oplus i \ZZ$.
	The embeddings are the identity and complex conjugation
	which take $1$ to $(1,1)$ and $i$ to $(i, -i)$.
	So
	\[
		\Delta_K =
		\det
		\begin{bmatrix}
			1 & 1 \\
			i & -i
		\end{bmatrix}^2
		=
		(-2i)^2 = -4.
	\]
	This example illustrates that the discriminant need not be positive
	for number fields which wander into the complex plane
	(the lattice picture is a less perfect analogy).
	But again, as we'll prove in the problems the discriminant is always
	an integer.
\end{example}
\begin{example}
	[Discriminant of $\QQ(\sqrt 5)$]
	Let $K = \QQ(\sqrt5)$.
	This time, $\OO_K = \ZZ \oplus \frac{1+\sqrt5}{2} \ZZ$, and so the discriminant
	is going to look a little bit different.
	The embeddings are still $a+b\sqrt 5 \mapsto a+b\sqrt5, a-b\sqrt5$.

	Applying this to the $\ZZ$-basis $\left\{ 1, \frac{1+\sqrt5}{2} \right\}$, we get
	\[
		\Delta_K
		=
		\det
		\begin{bmatrix}
			1 & 1 \\
			\frac{1+\sqrt5}{2} & \frac{1-\sqrt5}{2}
		\end{bmatrix}^2
		= (-\sqrt 5)^2 = 5.
	\]
\end{example}
\begin{exercise}
	Extend all this to show that
	if $K = \QQ(\sqrt d)$ for $d \neq 1$ squarefree, we have
	\[
		\Delta_K =
		\begin{cases}
			d & \text{if } d \equiv 1 \pmod 4 \\
			4d & \text{if } d \equiv 2, 3 \pmod 4.
		\end{cases}
	\]
\end{exercise}

Actually, let me point out something curious: recall that the polynomial discriminant of $Ax^2+Bx+C$ is $B^2-4AC$. Then:
\begin{itemize}
	\ii In the $d \equiv 1 \pmod 4$ case,
	$\Delta_K$ is the discriminant of $x^2 - x - \frac{d-1}{4}$,
	which is the minimal polynomial of $\half(1+\sqrt d)$.
	Of course, $\OO_K = \ZZ[\half(1+\sqrt d)]$.
	\ii In the $d \equiv 2,3 \pmod 4$ case,
	$\Delta_K$ is the discriminant of $x^2 - d$
	which is the minimal polynomial of $\sqrt d$. Once again, $\OO_K = \ZZ[\sqrt d]$.
\end{itemize}
This is not a coincidence! \Cref{prob:root_discriminant} asserts that this is true in general;
hence the name ``discriminant''.

\section{The signature of a number field}
\prototype{$\QQ(\sqrt[100]{2})$ has signature $(2, 49)$.}
In the example of $K = \QQ(i)$,
we more or less embedded $K$ into the space $\CC$.
However, $K$ is a degree two extension,
so what we'd really like to do is embed it into $\RR^2$.
To do so, we're going to take advantage of complex conjugation.

Let $K$ be a number field and $\sigma_1, \dots, \sigma_n$ be its embeddings.
We distinguish between the \vocab{real embeddings}
(which map all of $K$ into $\RR$)
and the \vocab{complex embeddings}
(which map some part of $K$ outside $\RR$).
Notice that if $\sigma$ is a complex embedding,
then so is the conjugate $\ol{\sigma} \ne \sigma$;
hence complex embeddings come in pairs.

\begin{definition}
	Let $K$ be a number field of degree $n$, and set
	\begin{align*}
		r_1 &= \text{number of real embeddings} \\
		r_2 &= \text{number of pairs of complex embeddings}.
	\end{align*}
	The \vocab{signature} of $K$ is the pair $(r_1, r_2)$.
	Observe that $r_1 + 2r_2 = n$.
\end{definition}
\begin{example}[Basic examples of signatures]
	\listhack
	\begin{enumerate}[(a)]
		\ii $\QQ$ has signature $(1,0)$.
		\ii $\QQ(\sqrt 2)$ has signature $(2,0)$.
		\ii $\QQ(i)$ has signature $(0,1)$.
		\ii Let $K = \QQ(\sqrt[3]{2})$, and let $\omega$ be a cube root of unity.
		The elements of $K$ are
		\[ K = \left\{ a + b\cbrt2 + c\cbrt4 \mid a,b,c \in \QQ  \right\}. \]
		Then the signature is $(1,1)$, because the three embeddings are
		\[ \sigma_1 : \cbrt 2 \mapsto \cbrt 2,
			\quad
			\sigma_2 : \cbrt 2 \mapsto \cbrt 2 \omega,
			\quad
			\sigma_3 : \cbrt 2 \mapsto \cbrt 2 \omega^2. \]
		The first of these is real and the latter two are conjugate pairs.
	\end{enumerate}
\end{example}
\begin{example}[Even more signatures]
	In the same vein $\QQ(\sqrt[99]{2})$ and $\QQ(\sqrt[100]{2})$
	have signatures $(1,49)$ and $(2,49)$.
\end{example}
\begin{ques}
	Verify the signatures of the above two number fields.
\end{ques}

From now on, we will number the embeddings of $K$ in such a way that
\[ \sigma_1, \sigma_2, \dots, \sigma_{r_1}  \]are the real embeddings,
while
\[
	\sigma_{r_1+1} = \ol{\sigma_{r_1+r_2+1}}, \quad
	\sigma_{r_1+2} = \ol{\sigma_{r_1+r_2+2}}, \quad
	\dots, \quad
	\sigma_{r_1+r_2} = \ol{\sigma_{r_1+2r_2}}.
\]
are the $r_2$ pairs of complex embeddings.
We define the \vocab{canonical embedding} of $K$ as
\[
	K \overset\iota\injto \RR^{r_1} \times \CC^{r_2} \
	\quad\text{by}\quad
	\alpha \mapsto  \left( \sigma_1(\alpha), \dots, \sigma_{r_1}(\alpha),
	\sigma_{r_1+1}(\alpha), \dots, \sigma_{r_1+r_2}(\alpha) \right).
\]
All we've done is omit, for the complex case, the second of the embeddings in each conjugate pair.
This is no big deal, since they are just conjugates;
the above tuple is all the information we need.

For reasons that will become obvious in a moment, I'll let $\tau$ denote the isomorphism
\[
	\tau : \RR^{r_1} \times \CC^{r_2} \taking{\sim} \RR^{r_1+2r_2} = \RR^n
\]
by breaking each complex number into its real and imaginary part, as
\begin{align*}
\alpha \mapsto  \big(& \sigma_1(\alpha), \dots, \sigma_{r_1}(\alpha), \\
& \Re \sigma_{r_1+1}(\alpha), \;\; \Im \sigma_{r_1+1}(\alpha), \\
& \Re \sigma_{r_1+2}(\alpha), \;\; \Im \sigma_{r_1+2}(\alpha), \\
& \dots, \\
& \Re \sigma_{r_1+r_2}(\alpha), \;\; \Im \sigma_{r_1+r_2}(\alpha) \big).
\end{align*}
\begin{example}[Example of canonical embedding]
	As before let $K = \QQ(\sqrt[3]{2})$ and set
	\[ \sigma_1 : \cbrt 2 \mapsto \cbrt 2,
		\quad
		\sigma_2 : \cbrt 2 \mapsto \cbrt 2 \omega,
		\quad
		\sigma_3 : \cbrt 2 \mapsto \cbrt 2 \omega^2 \]
	where $\omega = - \half + \frac{\sqrt3}{2} i$,
	noting that we've already arranged indices so $\sigma_1 = \id$ is real
	while $\sigma_2$ and $\sigma_3$ are a conjugate pair.
	So the embeddings $K \overset\iota\injto \RR \times \CC \taking\sim \RR^3$ are given by
	\[
		\alpha \overset\iota\longmapsto \left( \sigma_1(\alpha), \sigma_2(\alpha) \right)
		\overset\tau\longmapsto \left( \sigma_1(\alpha), \; \Re\sigma_2(\alpha), \; \Im\sigma_2(\alpha)  \right). \]
	For concreteness, taking $\alpha = 9 + \cbrt 2$ gives
	\begin{align*}
		9 + \cbrt 2 &\overset\iota\mapsto
		\left( 9 + \cbrt 2, \;\; 9 + \cbrt2\omega \right) \\
		&= \left( 9 + \cbrt 2, \;\;
		9 - \half\cbrt2 + \frac{\sqrt[6]{108}}{2} i  \right) \in \RR \times \CC \\
		&\overset\tau\mapsto \left( 9 + \cbrt 2, \;\; 9 - \half \cbrt 2,
		\;\; \frac{\sqrt[6]{108}}{2}  \right) \in \RR^3.
	\end{align*}
\end{example}

Now, the whole point of this is that we want to consider the resulting lattice
when we take $\OO_K$. In fact, we have:
\begin{lemma}
	\label{lem:vol_OK_mesh}
	Consider the composition of the embeddings $K \injto \RR^{r_1} \times \CC^{r_2} \taking\sim \RR^n$.
	Then as before, $\OO_K$ becomes a lattice $L$ in $\RR^n$, with mesh equal to
	\[ \frac{1}{2^{r_2}} \sqrt{\left\lvert \Delta_K \right\rvert}. \]
\end{lemma}
\begin{proof}
	Fun linear algebra problem (you just need to manipulate determinants).
	Left as \Cref{prob:OK_linalg}.
\end{proof}
From this we can deduce:
\begin{lemma}
	Consider the composition of the embeddings $K \injto \RR^{r_1} \times \CC^{r_2} \taking\sim \RR^n$.
	Let $\ka$ be an ideal in $\OO_K$.
	Then the image of $\ka$ is a lattice $L_\ka$ in $\RR^n$ with mesh equal to
	\[ \frac{\Norm(\ka)}{2^{r_2}} \sqrt{\left\lvert \Delta_K \right\rvert}. \]
\end{lemma}
\begin{proof}[Sketch of Proof]
	Let \[ d = \Norm(\ka) \defeq [\OO_K : \ka]. \]
	Then in the lattice $L_\ka$, we somehow only take $\frac 1d$th of the points
	which appear in the lattice $L$, which is why the area increases by a factor of $\Norm(\ka)$.
	To make this all precise I would need to do a lot more with lattices and geometry
	than I have space for in this chapter, so I will omit the details.
	But I hope you can see why this is intuitively true.
\end{proof}

\section{Minkowski's theorem}
Now I can tell you why I insisted we move from $\RR^{r_1} \times \CC^{r_2}$ to $\RR^n$.
In geometry, there's a really cool theorem of Minkowski's that goes as follows.
\begin{theorem}
	[Minkowski]
	Let $S \subseteq \RR^n$ be a convex set containing $0$
	which is centrally symmetric (meaning that $x \in S \iff -x \in S$).
	Let $L$ be a lattice with mesh $d$.
	If either
	\begin{enumerate}[(a)]
		\ii The volume of $S$ exceeds $2^n d$, or
		\ii The volume of $S$ equals $2^n d$ and $S$ is compact,
	\end{enumerate}
	then $S$ contains a nonzero lattice point of $L$.
\end{theorem}
\begin{ques}
	Show that the condition $0 \in S$ is actually extraneous
	in the sense that any nonempty, convex, centrally symmetric set contains the origin.
\end{ques}

\begin{proof}[Sketch of Proof]
	Part (a) is surprisingly simple and has a very olympiad-esque solution:
	it's basically Pigeonhole on areas.
	We'll prove part (a) in the special case $n=2$,
	$L = \ZZ^2$ for simplicity as the proof
	can easily be generalized to any lattice and any $n$.
	Thus we want to show that any such convex set $S$
	with area more than $4$ contains a lattice point.

	Dissect the plane into $2 \times 2$ squares
	\[ [2a-1, 2a+1] \times [2b-1, 2b+1] \]
	and overlay all these squares on top of each other.
	By the Pigeonhole Principle, we find there exist two points $p \neq q \in S$ which map to the same point.
	Since $S$ is symmetric, $-q \in S$. Then $\half (p-q) \in S$ (convexity) and is a nonzero lattice point.

	I'll briefly sketch part (b): the idea is to consider $(1+\eps) S$ for $\eps > 0$
	(this is ``$S$ magnified by a small factor $1+\eps$'').
	This satisfies condition (a). So for each $\eps > 0$ the set of nonzero lattice points in $(1+\eps) S$,
	say $S_\eps$, is a \emph{finite nonempty set} of (discrete) points
	(the ``finite'' part follows from the fact that $(1+\eps)S$ is bounded).
	So there has to be some point that's in $S_\eps$ for every $\eps > 0$ (why?), which implies it's in $S$.
\end{proof}

\section{The trap box}
The last ingredient we need is a set to apply Minkowski's theorem to.  I propose:
\begin{definition}
	Let $M$ be a positive real.
	In $\RR^{r_1} \times \CC^{r_2}$, define the box $S$ to be the
	set of points $(x_1, \dots, x_{r_1}, z_1, \dots, z_{r_2})$ such that
	\[
		\sum_{i=1}^{r_1} \left\lvert x_i \right\rvert
		+ 2 \sum_{j=1}^{r_2} \left\lvert z_j \right\rvert
		\le M.
	\]
	Note that this depends on the value of $M$.
\end{definition}

Think of this box as a \emph{mousetrap}: anything that falls in it is going to have a small norm,
and our goal is to use Minkowski to lure some nonzero element into it.

\begin{center}
	\begin{asy}
		size(6cm);
		real T = 1.414;
		int N = 10;
		real M = 3;

		real K = 2.4;
		filldraw( (K,0)--(0,K)--(-K,0)--(0,-K)--cycle, palered, darkred);
		label("$S$", (2*K/3,K/3), dir(45));

		for (int a = -N; a <= N; ++a) {
			for (int b = -N; b <= N; ++b) {
				if ((abs(a+T*b) <= M) && (abs(a-T*b) <= M))
				dot( (a+T*b, a-T*b) );
			}
		}
		draw( (-M,0)--(M,0), dotted);
		draw( (0,-M)--(0,M), dotted);
		label("$-2$", (-2,-2), dir(135));
		label("$-1$", (-1,-1), dir(135));
		label("$0$", (0,0), dir(135));
		label("$1$", (1,1), dir(135));
		label("$2$", (2,2), dir(135));
		label("$-\sqrt 2$", (-T,T), dir(135));
		label("$\sqrt 2$", (T,-T), dir(-45));
		label("$1+\sqrt 2$", (1+T,1-T), dir(-45));
	\end{asy}
\end{center}

That is, suppose $\alpha \in \ka$ falls into the box I've defined above, which means
\[
	M \ge
	\sum_{i=1}^{r_1} \left\lvert \sigma_i(\alpha) \right\rvert
	+ 2 \sum_{i=r_1+1}^{r_1+r_2} \left\lvert \sigma_i(\alpha) \right\rvert
	= \sum_{i=1}^{n} \left\lvert \sigma_i(\alpha) \right\rvert,
\]
where we are remembering that the last few $\sigma$'s come in conjugate pairs.
This looks like the trace, but the absolute values are in the way.
So instead, we apply AM-GM to obtain:
\begin{lemma}[Effect of the mousetrap]
	Let $\alpha \in \OO_K$, and suppose $\iota(\alpha)$ is in $S$
	(where $\iota : K \injto \RR^{r_1} \times \CC^{r_2}$ as usual).
	Then
	\[ \Norm_{K/\QQ}(\alpha)
		= \prod_{i=1}^n \left\lvert \sigma_i(\alpha) \right\rvert
		\le \left( \frac Mn \right)^n. \]
\end{lemma}
The last step we need to do is compute the volume of the box.
This is again some geometry I won't do, but take my word for it:
\begin{lemma}[Size of the mousetrap]
	Let $\tau : \RR^{r_1} \times \CC^{r_2} \taking\sim \RR^n$ as before.
	Then the image of $S$ under $\tau$ is a convex, compact, centrally symmetric set with volume
	\[ 2^{r_1} \cdot \left( \frac{\pi}{2} \right)^{r_2} \cdot \frac{M^n}{n!}. \]
\end{lemma}
\begin{ques}
	(Sanity check)
	Verify that the above is correct for the signatures $(r_1, r_2) = (2,0)$ and $(r_1,r_2) = (0,1)$,
	which are the possible signatures when $n=2$.
\end{ques}


\section{The Minkowski bound}
We can now put everything we have together to obtain the great Minkowski bound.
\begin{theorem}
	[Minkowski bound]
	Let $\ka \subseteq \OO_K$ be any nonzero ideal.
	Then there exists $0 \neq \alpha \in \ka$ such that
	\[ \Norm_{K/\QQ}(\alpha) \le \left( \frac 4\pi \right)^{r_2} \frac{n!}{n^n} \sqrt{\left\lvert \Delta_K \right\rvert}
	\cdot \Norm(\ka). \]
\end{theorem}
\begin{proof}
	This is a matter of putting all our ingredients together.
	Let's see what things we've defined already:
	\begin{center}
	\begin{tikzcd}
		K \ar[r, "\iota", hook]
			& \RR^{r_1} \times \CC^{r_2} \ar[r, "\tau"]
			& \RR^n \\
		& \text{box } S \ar[r, mapsto]
			& \tau\im(S)
			& \quad\text{with volume }
			2^{r_1} \left( \frac\pi2 \right)^{r_2} \frac{M^n}{n!} \\
		\OO_K \ar[rr, mapsto]
			&& \text{Lattice } L
			& \quad\text{with mesh }
			2^{-r_2} \sqrt{\left\lvert \Delta_K \right\rvert} \\
		\ka \ar[rr, mapsto]
			&& \text{Lattice } L_\ka
			& \quad\text{with mesh }
			2^{-r_2} \sqrt{\left\lvert \Delta_K \right\rvert} \Norm(\ka)
	\end{tikzcd}
	\end{center}
	Pick a value of $M$ such that the mesh of $L_\ka$
	equals $2^{-n}$ of the volume of the box.
	Then Minkowski's theorem gives that some $0 \neq \alpha \in \ka$ lands inside the box ---
	the mousetrap is configured to force $\Norm_{K/\QQ}(\alpha) \le \frac{1}{n^n} M^n$.
	The correct choice of $M$ is
	\[
		M^n
		= M^n \cdot 2^n \cdot \frac{\text{mesh}}{\text{vol box}}
		= 2^n \cdot \frac{n!}{2^{r_1} \cdot \left( \frac \pi 2 \right)^{r_2}}
		\cdot 2^{-r_2} \sqrt{\left\lvert \Delta_K \right\rvert} \Norm(\ka)
	\]
	which gives the bound after some arithmetic.
\end{proof}

\section{The class group is finite}
\begin{definition}
	Let
	$M_K = \left( \frac 4\pi \right)^{r_2} \frac{n!}{n^n} \sqrt{\left\lvert \Delta_K \right\rvert}$
	for brevity.
	Note that it is a constant depending on $K$.
\end{definition}
So that's cool and all, but what we really wanted was to show that
the class group is finite.
How can the Minkowski bound help?
Well, you might notice that we can rewrite it to say
\[ \Norm\left( (\alpha) \cdot \ka\inv \right) \le M_K \]
where $M_K$ is some constant depending on $K$, and $\alpha \in \ka$.
\begin{ques}
	Show that $(\alpha) \cdot \ka\inv$ is an integral ideal.
	(Unwind definitions.)
\end{ques}
But in the class group we \emph{mod out} by principal ideals like $(\alpha)$.
If we shut our eyes for a moment and mod out, the above statement becomes ``$\Norm(\ka\inv)\le M_K$''.
The precise statement of this is
\begin{corollary}
	\label{cor:class_rep_minkowski}
	Let $K$ be a number field, and pick a fractional ideal $J$.
	Then we can find $\alpha$ such that $\kb = (\alpha) \cdot J$ is integral
	and $\Norm(\kb) \le M_K$.
\end{corollary}
\begin{proof}
	For fractional ideals $I$ and $J$ write $I \sim J$ to mean
	that $I = (\alpha)J$ for some $\alpha$; then $\Cl_K$ is just modding out by $\sim$.
	Let $J$ be a fractional ideal.
	Then $J\inv$ is some other fractional ideal.
	By definition, for some $\alpha \in \OO_K$ we have that $\alpha J\inv$ is an integral ideal $\ka$.
	The Minkowski bound tells us that for some $x \in \ka$, we have $\Norm(x\ka\inv) \le M_K$.
	But $x\ka\inv \sim \ka\inv = (\alpha J\inv)\inv \sim J$.
\end{proof}

\begin{corollary}[Finiteness of class group]
	Class groups are always finite.
\end{corollary}
\begin{proof}
	For every class in $\Cl_K$,
	we can identify an integral ideal $\ka$ with norm less than $M_K$.
	We just have to show there are finitely many such integral ideals;
	this will mean there are finitely many classes.

	Suppose we want to build such an ideal $\ka = \kp_1^{e_1} \dots \kp_m^{e_m}$.
	Recall that a prime ideal $\kp_i$ must have some rational prime $p$ inside it,
	meaning $\kp_i$ divides $(p)$ and $p$ divides $\Norm(\kp_i)$.
	So let's group all the $\kp_i$ we want to build $\ka$ with based on which $(p)$ they came from.
	\begin{center}
		\begin{asy}
			size(4cm);
			label("$(2)$", (1,0), dir(90));
			for (int i=1; i <= 4; ++i) dot( (1, -i/4) );
			label("$(3)$", (2,0), dir(90));
			for (int i=1; i <= 6; ++i) dot( (2, -i/4) );
			label("$(5)$", (3,0), dir(90));
			for (int i=1; i <= 2; ++i) dot( (3, -i/4) );
			label("$\dots$", (4,0), dir(90));
		\end{asy}
	\end{center}
	To be more dramatic: imagine you have a \emph{cherry tree};
	each branch corresponds to a prime $(p)$
	and contains as cherries (prime ideals) the factors of $(p)$ (finitely many).
	Your bucket (the ideal $\ka$ you're building) can only hold a total weight
	(norm) of $M_K$.  So you can't even touch the branches higher than $M_K$.
	You can repeat cherries (oops),
	but the weight of a cherry on branch $(p)$ is definitely $\ge p$;
	all this means that the number of ways to build $\ka$ is finite.
\end{proof}

\section{Computation of class numbers}
\begin{definition}
The order of $\Cl_K$ is called the \vocab{class number} of $K$.
\end{definition}
\begin{remark}
	If $\Cl_K = 1$, then $\OO_K$ is a PID, hence a UFD.
\end{remark}

By computing the actual value of $M_K$,
we can quite literally build the entire ``cherry tree'' mentioned in the previous proof.
Let's give an example how!
\begin{proposition}
	The field $\QQ(\sqrt{-67})$ has class number $1$.
\end{proposition}
\begin{proof}
	Since $K = \QQ(\sqrt{-67})$ has signature $(0,1)$
	and discriminant $\Delta_K = -67$ (since $-67 \equiv 1 \pmod 4$)
	we can compute
	\[ M_K = \left( \frac 4\pi \right)^{1} \cdot \frac{2!}{2^2} \sqrt{67} \approx 5.2. \]
	That means we can cut off the cherry tree after $(2)$, $(3)$, $(5)$, since any
	cherries on these branches will necessarily have norm $\ge M_K$.
	We now want to factor each of these in $\OO_K = \ZZ[\theta]$, where $\theta = \frac{1+\sqrt{-67}}{2}$
	has minimal polynomial $x^2 - x + 17$.
	But something miraculous happens:
	\begin{itemize}
		\ii When we try to reduce $x^2-x+17 \pmod 2$, we get an irreducible polynomial $x^2-x+1$.
		By the factoring algorithm (\Cref{thm:factor_alg}) this means $(2)$ is prime.
		\ii Similarly, reducing mod $3$ gives $x^2-x+2$, which is irreducible.
		This means $(3)$ is prime.
		\ii Finally, for the same reason, $(5)$ is prime.
	\end{itemize}
	It's our lucky day;
	all of the ideals $(2)$, $(3)$, $(5)$ are prime (already principal).
	To put it another way,
	each of the three branches has only one (large) cherry on it.
	That means any time we put together an integral ideal with norm $\le M_K$,
	it is actually principal.
	In fact, these guys have norm $4$, $9$, $25$ respectively\dots
	so we can't even touch $(3)$ and $(5)$,
	and the only ideals we can get are $(1)$ and $(2)$ (with norms $1$ and $4$).

	Now we claim that's all.
	Pick a fractional ideal $J$.
	By \Cref{cor:class_rep_minkowski},
	we can find an integral ideal $\kb \sim J$ with $\Norm(\kb) \le M_K$.
	But by the above, either $\kb = (1)$ or $\kb = (2)$, both of which are principal,
	and hence trivial in $\Cl_K$.
	So $J$ is trivial in $\Cl_K$ too, as needed.
\end{proof}
Let's do a couple more.
\begin{theorem}[Gaussian integers {$\ZZ[i]$} form a UFD]
	The field $\QQ(i)$ has class number $1$.
\end{theorem}
\begin{proof}
	This is $\OO_K$ where $K = \QQ(i)$, so we just want $\Cl_K$ to be trivial.
	We have $M_K = \frac{2}{\pi}\sqrt{4} < 2$.
	So every class
	has an integral ideal of norm $\kb$ satisfying
	\[
		\Norm(\kb)
		\le \left( \frac4\pi \right)^{1} \cdot \frac{2!}{2^2} \cdot \sqrt{4}
		= \frac4\pi < 2.
	\]
	Well, that's silly: we don't have any branches to pick from at all.
	In other words, we can only have $\kb = (1)$.
\end{proof}

Here's another example of something that still turns out to be unique factorization,
but this time our cherry tree will actually have cherries that can be picked.
\begin{proposition}[{$\ZZ[\sqrt7]$} is a UFD]
	The field $\QQ(\sqrt7)$ has class number $1$.
\end{proposition}
\begin{proof}
	First we compute the Minkowski bound.
	\begin{ques}
		Check that $M_K \approx 2.646$.
	\end{ques}
	So this time, the only branch is $(2)$. Let's factor $(2)$ as usual: the polynomial $x^2+7$
	reduces as $(x-1)(x+1) \pmod 2$, and hence
	\[ (2) = \left( 2, \sqrt7-1 \right) \left( 2, \sqrt7+1 \right). \]
	Oops! We now have two cherries, and they both seem reasonable.
	But actually, I claim that
	\[ \left( 2, \sqrt7-1 \right) = \left( 3 - \sqrt 7 \right). \]
	\begin{ques}
		Prove this.
	\end{ques}
	So both the cherries are principal ideals, and as before we conclude that $\Cl_K$ is trivial.
	But note that this time, the prime ideal $(2)$ actually splits; we got lucky
	that the two cherries were principal but this won't always work.
\end{proof}

How about some nontrivial class groups?
First, we use a lemma that will help us with
narrowing down the work in our cherry tree.
\begin{lemma}[Ideals divide their norms]
	Let $\kb$ be an integral ideal with $\Norm(\kb) = n$.
	Then $\kb$ divides the ideal $(n)$.
\end{lemma}
\begin{proof}
	By definition, $n = \left\lvert \OO_K / \kb \right\rvert$.
	Treating $\OO_K/\kb$ as an (additive) abelian group and using Lagrange's theorem, we find
	\[ 0 \equiv
		\underbrace{\alpha + \dots + \alpha}_{n\text{ times}} = n\alpha
		\pmod \kb \qquad\text{for all } \alpha \in \OO_K. \]
	Thus $(n) \subseteq \kb$, done.
\end{proof}

Now we can give such an example.
\begin{proposition}[Class group of $\QQ(\sqrt{-17})$]
	The number field $K = \QQ(\sqrt{-17})$ has class group $\Zc 4$.
\end{proposition}
You are not obliged to read the entire proof in detail,
as it is somewhat gory.
The idea is just that there are some cherries which are not trivial in the class group.
\begin{proof}
Since $\Delta_K = -68$, we compute
the Minkowski bound
\[ M_K = \frac{4}{\pi} \sqrt{17} < 6. \]

Now, it suffices to factor with $(2)$, $(3)$, $(5)$.
The minimal polynomial of $\sqrt{-17}$ is $x^2+17$, so as usual
\begin{align*}
	(2) &= (2, \sqrt{-17}+1)^2 \\
	(3) &= (3, \sqrt{-17}-1)(3,\sqrt{-17}+1) \\
	(5) &= (5)
\end{align*}
corresponding to the factorizations of $x^2+17$ modulo each of $2$, $3$, $5$.
Set $\kp = (2, \sqrt{-17}+1)$ and $\kq_1 = (3, \sqrt{-17}-1)$, $\kq_2 = (3, \sqrt{-17}+1)$.
We can compute
\[ \Norm(\kp) = 2 \quad\text{and}\quad \Norm(\kq_1) = \Norm(\kq_2) = 3. \]
In particular, they are not principal.
The ideal $(5)$ is out the window; it has norm $25$.
Hence, the three cherries are $\kp$, $\kq_1$, $\kq_2$.

The possible ways to arrange these cherries into ideals with norm $\le 5$ are
\[ \left\{ (1), \kp, \kq_1, \kq_2, \kp^2 \right\}. \]
However, you can compute \[ \kp^2 = (2) \] so $\kp^2$ and $(1)$ are in the same class group;
that is, they are trivial.
In particular, the class group has order at most $4$.

From now on, let $[\ka]$ denote the class (member of the class group) that $\ka$ is in.
Since $\kp$ isn't principal (so $[\kp] \neq [(1)]$), it follows that $\kp$ has order two.
So Lagrange's theorem says that $\Cl_K$ has order either $2$ or $4$.

Now we claim $[\kq_1]^2 \neq [(1)]$, which implies that $\kq_1$ has order greater than $2$.
If not, $\kq_1^2$ is principal.
We know $\Norm(\kq_1) = 3$,
so this can only occur if $\kq_1^2 = (3)$;
this would force $\kq_1 = \kq_2$.
This is impossible since $\kq_1 + \kq_2 = (1)$.

Thus, $\kq_1$ has even order greater than $2$.
So it has to have order $4$.
From this we deduce \[ \Cl_K \cong \Zc 4. \qedhere \]
\end{proof}




\begin{remark}
	When we did this at Harvard during Math 129,
	there was a five-minute interruption in which students (jokingly) complained
	about the difficulty of evaluating $\frac{4}{\pi} \sqrt{17}$. Excerpt:
	\begin{quote}
		``Will we be allowed to bring a small calculator on the exam?'' -- Student 1 \\
		``What does the size have to do with anything?  You could have an Apple Watch'' -- Professor \\
		``Just use the fact that $\pi \ge 3$'' -- me \\
		``Even [other professor] doesn't know that, how are we supposed to?'' -- Student 2 \\
		``You have to do this yourself!'' -- Professor \\
		``This is an outrage.'' -- Student 1
	\end{quote}
\end{remark}
\section\problemhead
\begin{problem}
	Show that $K = \QQ(\sqrt{-163})$ has trivial class group,
	and hence $\OO_K = \ZZ\left[ \frac{1+\sqrt{-163}}{2} \right]$
	is a UFD.\footnote{In fact,
		$n = 163$ is the largest number
		for which $\QQ(\sqrt{-n})$ has trivial class group.
		The complete list is $1, 2, 3, 7, 11, 19, 43, 67, 163$,
		the \vocab{Heegner numbers}.
		You might notice Euler's prime-generating polynomial $t^2+t+41$
		when doing the above problem.  Not a coincidence!}
	\begin{hint}
		Repeat the previous procedure.
	\end{hint}
\end{problem}

\begin{problem}
	Determine the class group of $\QQ(\sqrt{-31})$.
	\begin{hint}
		You should get a group of order three.
	\end{hint}
\end{problem}

\begin{problem}[China TST 1998]
	Let $n$ be a positive integer.
	A polygon in the plane (not necessarily convex) has area greater than $n$.
	Prove that one can translate it so that it contains at least $n+1$ lattice points.
	\begin{hint}
		Mimic the proof of part (a) of Minkowski's theorem.
	\end{hint}
\end{problem}

\begin{problem}
	[\Cref{lem:vol_OK_mesh}]
	\label{prob:OK_linalg}
	Consider the composition of the embeddings $K \injto \RR^{r_1} \times \CC^{r_2} \taking\sim \RR^n$.
	Show that the image of $\OO_K \subseteq K$ has mesh equal to
	\[ \frac{1}{2^{r_2}} \sqrt{\left\lvert \Delta_K \right\rvert}. \]
	\begin{hint}
		Linear algebra.
	\end{hint}
\end{problem}

\begin{problem}
	Let $p \equiv 1 \pmod 4$ be a prime.
	Show that there are unique integers $a > b > 0$ such that $a^2+b^2=p$.
	\begin{hint}
		Factor in $\QQ(i)$.
	\end{hint}
%	\begin{sol}
%		Let's factor $(p)$ in $\QQ(i)$, which has ring of integers $\ZZ[i]$.
%		Using \Cref{thm:factor_alg}, we get $\ZZ[x] / (p,x^2+1) \cong \FF_p[x] / (x^2+1)$.
%		Since $p \equiv 1 \pmod 4$, $x^2+1 \equiv (x+t)(x-t) \pmod p$ for some $t$.
%		Thus $(p) = (p, t+i)(p, t-i)$ is the full decomposition into prime factors.
%	\end{sol}
\end{problem}


\begin{problem}
	[Korea national olympiad 2014]
	Let $p$ be an odd prime and $k$ a positive integer such that $p \mid k^2+5$.
	Prove that there exist positive integers $m$, $n$ such that $p^2 = m^2+5n^2$.
	\begin{hint}
		Factor $p$, show that the class group of $\QQ(\sqrt{-5})$ has order two.
	\end{hint}
	\begin{sol}
		Let $K = \QQ(\sqrt{-5})$. Check that $\Cl_K$ has order two using the Minkowski bound;
		moreover $\Delta_K = 20$.
		Now note that $\OO_K = \ZZ[\sqrt{-5}]$, and $x^2+5$ factors mod $p$ as $(x+k)(x-k)$;
		hence in $\OO_K$ we have $(p) = (p, \sqrt{-5}+k)(p, \sqrt{-5}-k) = \kp_1 \kp_2$, say.
		For $p > 5$ the prime $p$ does not ramify and we have $\kp_1 \neq \kp_2$, since $\Delta_K = 20$.

		Then $(p^2) = \kp_1^2 \cdot \kp_2^2$. Because the class group has order two,
		both $\kp_1^2$ and $\kp_2^2$ are principal, and because $\kp_1 \neq \kp_2$ they are distinct.
		Thus $p^2$ is a nontrivial product of two elements of $\OO_K$; from this we can extract the desired factorization.
	\end{sol}
\end{problem}
