\documentclass[11pt]{article}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{hyperref}
\hypersetup{colorlinks=true,urlcolor=blue,citecolor=blue,linkcolor=blue}
\usepackage{courier}
\usepackage{tikz}
\usetikzlibrary{calc,matrix,arrows,decorations.markings}
\usepackage{array}
\usepackage{color}
\usepackage{enumerate}
\usepackage{nicefrac}
\usepackage{listings}
\lstset{
	basicstyle=\small\ttfamily,
	keywordstyle=\color{blue},
	language=python,
	xleftmargin=16pt,
}

\textwidth=5.8in
\textheight=9in
\topmargin=-0.5in
\headheight=0in
\headsep=.5in
\hoffset  -.4in
\pagestyle{empty}

% growing list of useful macros, use these where appropriate and add to this list as needed
\newcommand{\kbar}{\bar{k}}
\newcommand{\Fp}{\mathbb{F}_p}
\newcommand{\Fpbar}{\overline{\mathbb{F}}_p}
\newcommand{\Fq}{\mathbb{F}_q}
\newcommand{\Fqbar}{\overline{\mathbb{F}}_q}
\newcommand{\Fqm}{\mathbb{F}_{q^m}}
\newcommand{\Fqn}{\mathbb{F}_{q^n}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\Qbar}{\overline{\Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\renewcommand{\H}{\mathbb{H}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Zhat}{\widehat\Z}
\newcommand{\Zbar}{\overline\Z}
\newcommand{\Kbar}{\overline K}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\Aut}{{\rm Aut}}
\newcommand{\Gal}{{\rm Gal}}
\newcommand{\SL}{{\rm SL}}
\newcommand{\GL}{{\rm GL}}
\newcommand{\PGL}{{\rm PGL}}
\newcommand{\dy}{\,dy}
\newcommand{\dx}{\,dx}
\newcommand{\tr}{\operatorname{tr}}
\newcommand{\kron}[2]{\bigl(\frac{#1}{#2}\bigr)}
\newcommand{\lcm}{\operatorname{lcm}}
\newcommand{\ceil}[1]{\lceil{#1}\frac{1}eil}
\newcommand{\Exp}{{\rm E}}
\renewcommand{\O}{\mathcal{O}}
\newcommand{\OK}{\O_K}
\newcommand{\T}{{\rm T}}
\newcommand{\N}{{\rm N}}
\newcommand{\re}{\operatorname{re}}
\newcommand{\im}{\operatorname{im}}
\newcommand{\ord}{\operatorname{ord}}
\newcommand{\cl}{\operatorname{cl}}
\newcommand{\disc}{\operatorname{disc}}
\newcommand{\p}{\mathfrak{p}}
\newcommand{\q}{\mathfrak{q}}
\newcommand{\m}{{\mathfrak m}}
\renewcommand{\c}{{\mathfrak c}}
\renewcommand{\a}{{\mathfrak a}}
\newcommand{\Frob}{{\rm Frob}}
\newcommand{\Hom}{\operatorname{Hom}}
\newcommand{\tor}{{\rm tors}}
\newcommand{\I}{\mathcal{I}}
\newcommand{\D}{\mathcal{D}}
\newcommand{\Div}{\operatorname{Div}}

\newtheorem*{theorem}{Theorem}
\theoremstyle{definition}
\newtheorem*{definition}{Definition}
\newtheorem*{remark}{Remark}

\begin{document}
\setlength{\unitlength}{1in}
\begin{center}
\large
\textbf{18.785 Number Theory\hspace{228pt}Fall~2016}\\\vspace{4pt}
\textbf{Problem Set \#7\hspace{220pt}Due: 11/04/2016}
\normalsize
\begin{picture}(5.8,.1) 
\put(0,0) {\line(1,0){5.8}}
\end{picture}
\end{center}

\subsection*{Description}

These problems are related to the material covered in Lectures 13-15.
Your solutions are to be written up in latex (you can use the latex source for the problem set as a template) and submitted as a pdf-file with a filename of the form \texttt{SurnamePset7.pdf} via e-mail to \texttt{drew@math.mit.edu} by {\bf 5pm} on the date due.
Collaboration is permitted/encouraged, but you must identify your collaborators, and any references you consulted.
If there are none, write ``\textbf{Sources consulted:\ none}" at the top of your problem set.
The first person to spot each nontrivial typo/error in any of the problem sets or lecture notes will receive 1-5 points of extra credit.
\medskip

\noindent
\textbf{Instructions:} First do the warm up problems, then pick a set of problems 1-5 that sum to 99 points to solve.
Finally, complete the survey problem 6.

\subsection*{Problem 0.}
These are warm up problems that do not need to be turned in.
\begin{enumerate}
\setlength\itemsep{0pt}
\item[(a)] Prove that our two definitions of a lattice $\Lambda$ in $V\simeq \R^n$ are equivalent: $\Lambda$ is a free $\Z$-module with $\R$-span $V$ if and only if it is a discrete cocompact subgroup of $V$.
\item[(b)] Prove that the imaginary quadratic fields $\Q(i)$, $\Q(\sqrt{-2})$, $\Q(\sqrt{-3})$, $\Q(\sqrt{-7})$ all have class number $1$ because the Minkowski bound is less than $2$.
\item[(c)] Prove that the imaginary quadratic fields $\Q(\sqrt{-11})$, $\Q(\sqrt{-19})$, $\Q(\sqrt{-43})$, $\Q(\sqrt{-67})$, $\Q(\sqrt{-163})$ all have class number $1$ because they have no ideals of prime norm below the Minkowski bound.  Why is it enough to check only ideals of prime norm?
\item[(d)] Prove that there are no real cubic fields of absolute discriminant less than 20 and that every real cubic field of absolute discriminant at most $M$ is generated by an algebraic integer with minimal polynomial $x^3+ax^2+bx+c\in \Z[x]$ with $|a|<\sqrt{M}+2$, $|b|<2\sqrt{M}+1$, and $|c|<\sqrt{M}$.
\item[(e)] Let $n\in\Z_{>0}$ and assume $n^2-1$ is squarefree.  Prove $n+\sqrt{n^2-1}$ is the fundamental unit of $\Q(\sqrt{n^2-1})$.
\end{enumerate}


\subsection*{Problem 1. A non-solvable quintic extension (33 points)}

Let $f(x):=x^5-x+1$, let $K:=\Q[x]/(f)=:\Q[\alpha]$ and let $L$ be the splitting field of $f$.

\begin{enumerate}
\item[(\bf a)] Prove that $f$ is irreducible in $\Q[x]$, thus $K$ is number field.
Determine the number of real and complex places of $K$, and the structure of $\O_K^\times$ as a finitely generated abelian group (both torsion and free parts).
\item[(\bf b)] Prove that the ring of integers of $K$ is $\O_K:=\Z[\alpha]$ and compute $\disc\O_K$, which you should find is squarefree.
Use this to prove that for each prime $p$ dividing $\disc\O_K$ exactly one of $\q|p$ is ramified, and it has ramification index $e_\q=2$ and residue field degree $f_\q=1$.  Conclude that $K/\Q$ is tamely ramified.
\item[(\bf c)] Using the fact that any extension of local fields has a unique maximal unramified subextension, prove that for any monic irreducible polynomial $g\in \Z[x]$ the splitting field of~$g$ is unramified at all primes that do not divide the discriminant of~$g$.
Conclude that $L/\Q$ is unramified away from primes dividing $\disc\O_K$ and tamely ramified everywhere, and show that every prime dividing $\disc \O_K$ has ramification index 2.  Use this to compute $\disc \O_L$.
\item[(\bf d)] Show that $\O_K$ has no ideals of norm 2 or 3 and use this to prove that the class group of $\O_K$ is trivial and therefore $\O_K$ is a PID.

\item[(\bf e)] Prove that $\Gal(L/\Q)\simeq S_5$, and that it is generated by the Frobenius elements $\sigma_2$ and $\sigma_5$ ($\Gal(L/\Q)$ is nonabelian, so these are conjugacy class representatives).
\end{enumerate}


\subsection*{Problem 2. Binary quadratic forms (33 points)}

A \emph{binary quadratic form} is a homogeneous polynomial of degree 2 in two variables:
\[
f(x,y)=ax^2+bxy+cy^2,
\]
which we identify by the triple $(a,b,c)$.
We are interested in a specific set of binary quadratic forms, namely, those that are
\emph{integral} ($a,b,c\in\Z$), \emph{primitive} ($\gcd(a,b,c)=1$), and \emph{positive definite} ($b^2-4ac<0$ and $a>0$).
To simplify matters, in this problem we shall use the word $\emph{form}$ to refer to an integral, primitive, positive definite, binary quadratic form.

The \emph{discriminant} of a form is the integer $D:=b^2-4ac<0$; although this is not necessary, for the sake of simplicity we restrict our attention to \emph{fundamental discriminants}~$D$, those for which $D$ is the discriminant of $\Q[x]/(f(x,1))=\Q(\sqrt{D})$.

We define the (principal) \emph{root} $\tau:=\tau(f)$ of a form $f=(a,b,c)$ to be the unique root of $f(x,1)$ in the upper half plane $\H:=\{z\in \C:\im z >0\}$:
\[
\tau=\frac{-b+\sqrt{D}}{2a}.
\]
Let $F(D)$ denote the set of forms with fundamental discriminant $D$, let $K=\Q(\sqrt{D})$, and let $\O_K$ be the ring of integers of $K$.

\begin{enumerate}[{\bf(a)}]
\item
For each form $f=(a,b,c)\in F(D)$ with root $\tau$, define $I(f):=a\Z+ a\tau\Z$.
Prove that $\O_K=\Z+a\tau\Z$ and that $I(f)$ is a nonzero $\O_K$-ideal of norm~$a$.
Show that every nonzero fractional ideal $J$ lies in the ideal class of $I(f)$ for some $f=(a,b,c)\in F(D)$.
\item For each $\gamma = \left(\begin{smallmatrix}s&t\\u&v\end{smallmatrix}\right)\in \SL_2(\Z)$ and $f(x,y)\in F(D)$ define
\[
f^\gamma(x,y) := f(sx+ty,\,ux+vy).
\]
Show that $f^\gamma\in F(D)$, and that this defines a right group action of $\SL_2(\Z)$ on the set $F(D)$ (this means $\left(\begin{smallmatrix}1&0\\0&1\end{smallmatrix}\right)$ acts trivially and $f^{(\gamma_1\gamma_2)}=(f^{\gamma_1})^{\gamma_2}$ for all $\gamma_1,\gamma_2\in \SL_2(\Z)$).
\end{enumerate}

\noindent
Call two forms $f,g\in F(D)$ \emph{equivalent} if $g=f^\gamma$ for some $\gamma\in\SL_2(\Z)$.

\begin{enumerate}[{\bf(a)}]
\setcounter{enumi}{2}
\item Prove that two forms $f,g\in F(D)$ are equivalent if and only if $I(f)$ and $I(g)$ represent the same ideal class in $\cl(\O_K)$.
\end{enumerate}

\noindent
Recall that $\SL_2(\Z)$ acts on the upper half plane $\H$ (on the left) via
\[
\begin{pmatrix}a&b\\c&d\end{pmatrix}\tau:= \frac{a\tau+b}{c\tau+d},
\]
and that the set
\[
\mathcal{F}=\bigl\{\tau\in\H: \re(\tau)\in[-1/2,0] \text{ and } |\tau|\ge 1\bigr\} \\\cup \bigl\{\tau\in\H: \re(\tau)\in(0,1/2) \text{ and } |\tau|> 1\bigr\}
\]
is a fundamental region for $\H$ modulo the $\SL_2(\Z)$-action.
A form $f=(a,b,c)$ is said to be \emph{reduced} if
\[
-a<b\le a< c\qquad\text{or}\qquad0\le b \le a = c.
\]
\begin{enumerate}[{\bf(a)}]
\setcounter{enumi}{3}
\item
Prove that two forms are equivalent if and only if their roots lie in the same $\SL_2(\Z)$-orbit, and that a form is reduced if and only if its root lies in $\mathcal{F}$.
Conclude that each equivalence class in $F(D)$ contains exactly one reduced form.
\item
Prove that if $f$ is reduced then $a\le \sqrt{|D|/3}$; conclude that $\# \cl(\O_K) \le |D|/3$.
\end{enumerate}

\begin{remark}
One can define (as Gauss did) a composition law for forms corresponding to multiplication of ideals; the product of reduced forms need not be reduced, so one also needs an algorithm to reduce a given form, but this is easy.  One can then compute the group operation in $\cl(\O_K)$ using composition and reduction of forms, and this process is quite efficient.
Using the group operation one can compute $\#\cl(\O_K)$ much more efficiently than by enumerating reduced forms, and one can also compute the structure of $\cl(\O_K)$ as a finite abelian group.
\end{remark}

\subsection*{Problem 3. Unit groups of real quadratic fields (66 points)}

A (simple) \emph{continued fraction} is a (possibly infinite) expression of the form
\[
a_0+\cfrac{1}{a_1+\cfrac{1}{a_2+\cdots}}
\]
with $a_i\in \Z$ and $a_i>0$ for $i>0$.
They are more compactly written as $(a_0;a_1,a_2,\ldots)$.
For any $t\in \R_{> 0}$ the \emph{continued fraction expansion} of $t$ is defined recursively via
\[
t_0:=t,\qquad a_n :=\lfloor t_n\rfloor,\qquad  t_{n+1}:=1/(t_n-a_n),
\]
where the sequence $a(t):=(a_0;a_1,a_2,\ldots)$ terminates at $a_n$ if $t_n=a_n$, in which case we say that $a(t)=(a_0;a_1,\ldots,a_n)$ is \emph{finite}, and otherwise call $a(t)=(a_0;a_1,a_2,\ldots)$ \emph{infinite}.
If $a(t)$ is infinite and there exists $\ell\in \Z_{>0}$ such that $a_{n+\ell}=a_n$ for all sufficiently large $n$,
we say that $a(t)$ is \emph{periodic} and call the least such integer $\ell:=\ell(t)$ the \emph{period} of $a(t)$.

Given a continued fraction $a(t):=(a_0;a_1,a_2,\ldots)$ define the sequences of integers $(P_n)$ and $(Q_n)$ by
\begin{align*}
P_{-2}&=0,\qquad\, P_{-1}=1,\qquad\, P_n=a_nP_{n-1}+P_{n-2};\\
Q_{-2}&=1,\qquad Q_{-1}=0,\qquad Q_n=a_nQ_{n-1}+Q_{n-2}.
\end{align*}

\begin{enumerate}[(\bf a)]
\item Prove that $a(t)$ is finite if and only if $t\in\Q$, in which case $t=a(t)$.
\item Prove that if $a(t)=(a_0;a_1,a_2,\ldots)$ is infinite then $(a_0;a_1,\ldots,a_n)=P_n/Q_n$ and $t_n=(a_n;a_{n+1},a_{n+2},\ldots)$ for all $n\ge 0$; conclude that $t=\lim_{n\to\infty} P_n/Q_n = a(t)$.
\item Prove that $a(t)$ is periodic if and only if $\Q(t)$ is a real quadratic field.
\end{enumerate}

Now let $D>0$ be a squarefree integer that is not congruent to $1\bmod 4$ and let $K=\Q(\sqrt{D})$.
As shown on previous problem sets, $\O_K=\Z[\sqrt{D}]$, and it is clear that $(\O_K^\times)_{\rm tors}=\{\pm 1\}$.
Every $\alpha=x+y\sqrt{D}\in\O_K^\times$ has $N(\alpha)=\pm 1$, and $(x,y)$ is thus an (integer) solution to the \emph{Pell equation}
\begin{equation}\label{eq:pell}
X^2-DY^2=\pm 1
\end{equation}
\begin{enumerate}[(\bf a)]
\setcounter{enumi}{3}
\item Prove that if $(x_1,y_1)$ and $(x_2,y_2)$ are solutions to \eqref{eq:pell} with $x_1,y_1,x_2,y_2\in\Z_{>0}$ then $x_1+y_1\sqrt{D} < x_2+y_2\sqrt{D}$ if and only if $x_1<x_2$ and $y_1\le y_2$, and show that $(x_1+y_1\sqrt{D})^n > x_1+y_1\sqrt{D}$ for all $n>1$.  Conclude that the fundamental unit $\epsilon=x+y\sqrt{D}$ of $\O_K^\times$ is the unique solution $(x,y)$ to \eqref{eq:pell} with $x,y>0$ and $x$ minimal.
\item Let $a(\sqrt{D})=(a_0;a_1,a_2,\ldots)$, and define $t_n,P_n,Q_n$ as above.
Prove that 
\[
P_{n-1}Q_{n-2}-P_{n-2}Q_{n-1}=\pm 1\qquad\text{and}\qquad\frac{t_nP_{n-1}+P_{n-2}}{t_n Q_{n-1}+Q_{n-2}}=\sqrt{D}
\]
for all $n\ge 0$.
Use this to show that $(P_{kl-1},Q_{kl-1})$ is a solution to \eqref{eq:pell} for all $k\ge 0$, where $\ell:=\ell(\sqrt{D})$.
Conclude that $\epsilon=P_{\ell-1}+Q_{\ell-1}\sqrt{D}$.
\item Compute the fundamental unit $\epsilon$ for each of the real quadratic fields $\Q(\sqrt{19})$, $\Q(\sqrt{570})$, and $\Q(\sqrt{571})$; in each case give the period $\ell(\sqrt{D})$ as well as $\epsilon$.
\end{enumerate}


\subsection*{Problem 4. $S$-class groups and $S$-unit groups (33 points)}
Let $K$ be a number field with ring of integers $\O_K$, and let $S$ be a finite set of places of~$K$ including all archimedean places.
Define the \emph{ring of $S$-integers} $\O_{K,S}$ as the set
\[
\O_{K,S}:=\{x\in K:v_\p(x)\ge 0\text{ for all }\p\not\in S\}.
\]
\begin{enumerate}
\item[(\bf a)] Prove that $\O_{K,S}$ is a Dedekind domain containing $\O_K$ with the same fraction field.
\item[(\bf b)] Define a natural homomorphism between $\cl\O_{K,S}$ and $\cl\O_K$ (it is up to you to determine which direction it should go) and use it to prove that $\cl \O_{K,S}$ is finite.
\item[(\bf c)] Prove that there is a finite set $S$ for which $\O_{K,S}$ is a PID and give an explicit upper bound on $\#S$ that depends only on $n=[K:\Q]$ and $|\disc \O_K|$.
\item[(\bf d)] Prove the \emph{$S$-unit theorem}: $\O_{K,S}^\times$ is a finitely generated abelian group of rank $\#S-1$.
\end{enumerate}

\subsection*{Problem 5. Classification of global fields (66 points)}
Let $K$ be a field and let $M_K$ be the set of places of $K$ (equivalence classes of nontrivial absolute values).
We say that $K$ has a (strong) \emph{product formula} if $M_K$ is nonempty for each $v\in M_K$ there is an absolute value $|\ |_v$ in its equivalence class and a positive real number $m_v$ such that for all $x\in K^\times$ we have
\[
\prod_{v\in M_K}|x|_v^{m_v}=1,
\]
where all but finitely many factors in the product are equal to $1$.
Equivalently, if we fix \emph{normalized absolute values} $\|\ \|_v:=|x|_v^{m_v}$ for each $v\in M_K$, then for all $x\in K^\times$ we have
\[
\prod_{v\in M_K}\|x\|_v=1,
\]
with $\|x\|_v=1$ for all but finitely many $v\in M_K$.

\begin{definition}
A field $K$ is a \emph{global field} if it has a product formula and the completion $K_v$ of~$K$ at each place $v\in M_K$ is a local field.
\end{definition}

In Lectures 10 and 13 we proved every finite extension of $\Q$ and $\Fq(t)$ is a global field.  In this problem you will prove the converse, a result due to Artin and Whaples \cite{AW45}.
\smallskip

Let $K$ be a global field with normalized absolute values $\|\ \|_v$ for $v\in M_K$ that satisfy the product formula.
As we defined in lecture, an $M_K$-\emph{divisor} is a sequence of positive real numbers $c=(c_v)$ indexed by $v\in M_K$ with all but finitely many $c_v=1$ such that for each $v\in M_K$ there is an $x\in K_v^\times$ for which $c_v=\|x\|_v$.
For each $M_K$-divisor $c$ we define the set
\[
L(c):=\{x\in K:\|x\|_v\le c_v\text{ for all } v\in M_K\}.
\]

\begin{enumerate}
\item[(\bf a)] Let $E/F$ be a finite Galois extension. Prove $E$ is a global field if and only if $F$~is.
\item[(\bf b)] Extend your proof of (a) to all finite extensions $E/F$.
\item[(\bf c)] Prove that $M_K$ is infinite but contains only finitely many archimedean places.
\item[(\bf d)] Assume $K$ has an archimedean place.  Prove that $L(c)$ is finite for every $M_K$-divisor~$c$ (we proved this in class for number fields, but here $K$ is a global field as defined above).
\item[(\bf e)] Extend your proof of (e) to the case where $K$ has no archimedean places.
\item[(\bf f)] Prove that if $M_K$ contains an archimedean place then $K$ is a finite extension of~$\Q$ (hint: show $\Q\subseteq K$ and use (b) to show that $K/\Q$ is a finite extension).
\item[(\bf g)] Prove that if $M_K$ does not contain an archimedean place then $K$ is a finite extension of $\Fq(t)$ for some finite field $\Fq$ (hint: by choosing an appropriate $M_K$-divisor $c$, show that $L(c)$ is a finite field $k\subseteq K$ and that every $t\in K-k$ is transcendental over $k$; then show that $K$ is a finite extension of $k(t)$).
\item[(\bf h)] In your proofs of (a)-(g) above, where did you use the fact that the completions of~$K$ are local fields?
Show that if $K$ has a product formula and $K_v$ is a local field for any place $v\in M_K$ then $K_v$ is a local field for every place $v\in M_K$ (so we could weaken our definition of a global field to only require one $K_v$ to be a local field).
Are there fields with a product formula for which no completion is a local field?
\end{enumerate}


\subsection*{Problem 6. Survey}
Complete the following survey by rating each problem you attempted on a scale of 1 to~10 according to how interesting you found it (1 = ``mind-numbing," 10 = ``mind-blowing"), and how difficult you found it (1 = ``trivial," 10 = ``brutal").  Also estimate the amount of time you spent on each problem to the nearest half hour.

\begin{center}
\begin{tabular}{l|r|r|r|}
& Interest & Difficulty & Time Spent\\\hline
Problem 1 & & & \\\hline
Problem 2 & & & \\\hline
Problem 3 & & & \\\hline
Problem 4 & & & \\\hline
Problem 5 & & & \\\hline
\end{tabular}
\end{center}
\noindent
Please rate each of the following lectures that you attended, according to the quality of the material (1=``useless", 10=``fascinating"), the quality of the presentation (1=``epic fail", 10=``perfection"), the pace (1=``way too slow", 10=``way too fast", 5=``just right") and the novelty of the material to you (1=``old hat", 10=``all new").

\begin{center}
\begin{tabular}{l|l|r|r|r|r|r}
Date & Lecture Topic & Material & Presentation & Pace & Novelty\\\hline
10/29 & Dirichlet's unit theorem & & & & \\\hline 
11/3 & The prime number theorem & & & & \\\hline 
\end{tabular}
\end{center}

\noindent
Please feel free to record any additional comments you have on the problem sets and the lectures, in particular, ways in which they might be improved.

\begin{thebibliography}{99}
\bibitem{AW45}
Emil Artin and George Whaples, \href{http://www.ams.org/journals/bull/1945-51-07/S0002-9904-1945-08383-9/S0002-9904-1945-08383-9.pdf}{\textit{Axiomatic characterization of fields by the product formula for valuations}}, Bull. Amer. Math. Soc. \textbf{51} (1945), 469--492.
\end{thebibliography}

\end{document}