\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}}

\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~2015}\\\vspace{4pt}
\textbf{Problem Set \#7\hspace{220pt}Due: 11/04/2015}
\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 12-14.
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 non-trivial 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 two of problems 1-5 to solve and write up your answers in latex.
Anyone who wishes to do so may earn up to 25 points of extra credit by solving three problems (the extra credit you receive will be the worst of your three scores divided by 2).
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 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[(b)] 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?  Does this work for other number fields?
\item[(c)] 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[(d)] 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 (50 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 that $\disc \O_K = 19\cdot 151$.
By analyzing the norm of the different $\D_{K/\Q}$, show that for both $p=19$ and $p=151$ exactly one of the primes~$\q$ of $K$ lying above $p$ is ramified and that this~$\q$ must have ramification index $e_\q=2$ and residue field degree $f_\q=1$.
Conclude that the extension $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 tamely ramified, and unramified away from $19$ and $151$, and similarly show it has ramification index 2 at both 19 and 151; 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 (50 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}
The upper bound $|D|/3$ is an overestimate, in fact $\# \cl\O_K=O(|D|^{1/2}\log|D|)$; under the generalized Riemann hypothesis one can sharpen this to $O(|D|^{1/2}\log\log|D|)$.
\end{remark}

\begin{enumerate}[{\bf(a)}]
\setcounter{enumi}{5}
\item Compute the class numbers of $\Q(\sqrt{-103})$ and $\Q(\sqrt{-396})$ by enumerating the reduced forms in $F(D)$ and list reduced forms $f=(a,b,c)$ whose ideals $I(f)$ represent each element of the class group (you may wish to write a short Sage or Magma script to automate this task but this is not required).
\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 (50 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$ for all $n\ge 0$, and 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)$, define the sequences $(P_n)$ and $(Q_n)$ as above, and let $\ell=\ell(\sqrt{D})$.
Prove 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 (50 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 (50 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 and there exists a set of representative $|\ |_v$ for $v\in M_K$ and a positive real numbers $m_v$ such that for all $x\in K^\times$ we have
\[
\prod_{v\in M_K}|x|_v^{m_v}=1,
\]
with all but finitely many factors in the product equal to $1$.
Equivalently, if we define \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 of~$K$ at any nontrivial absolute value is a local field.
\end{definition}

We proved in lecture that every finite extension of $\Q$ and $\Fq(t)$ is a global field.  In this problem you will prove the converse (a theorem due to Artin and Whaples).

Let $K$ be a global field and fix a set of normalized absolute values $\|\ \|_v$ for $v\in M_K$.
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^\times$ for which $c_v=\|x\|_v$.
We then define
\[
L(c):=\{x\in K:\|x\|_v\le c_v\text{ for all } v\in M_K\}.
\]

\begin{enumerate}
\item[(\bf a)] Prove that $M_K$ is infinite but contains only finitely many archimedean places.
\item[(\bf b)] Prove that for every $M_K$-divisor $c$ the set $L(c)$ is finite.
\item[(\bf c)] Let $F$ be a field.  Prove that if $K$ is a finite extension of $F$ of if $F$ is a finite extension of $K$ then $F$ is a global field.
\item[(\bf d)] Prove that if $M_K$ contains an archimedean place then $K$ is a finite extension of $\Q$ (hint: show that $K$ contains $\Q$ and use (b) to show that $K/\Q$ is a finite extension).
\item[(\bf e)] 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)$ as in (d)).
\item[(\bf f)] In your proofs of (a)-(e) above, where did you use the fact that the completions of~$K$ are local fields?
\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 & Unit group and regulator & & & & \\\hline 
11/3 & Introduction to zeta functions & & & & \\\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.


\end{document}