\documentclass[12pt]{article}
\usepackage{amsfonts, amsthm, amsmath, stmaryrd}

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

\def\CC{\mathbb{C}}
\def\FF{\mathbb{F}}
\def\NN{\mathbb{N}}
\def\PP{\mathbb{P}}
\def\QQ{\mathbb{Q}}
\def\RR{\mathbb{R}}
\def\ZZ{\mathbb{Z}}
\def\gotha{\mathfrak{a}}
\def\gothm{\mathfrak{m}}
\def\gotho{\mathfrak{o}}
\def\gothp{\mathfrak{p}}
\DeclareMathOperator{\Disc}{Disc}
\DeclareMathOperator{\Trace}{Trace}
\DeclareMathOperator{\Norm}{Norm}
\def\bv{\vec{v}}
\def\bw{\vec{w}}

\def\head#1{\medskip \noindent \textbf{#1}.}
\def\fixme#1{\textbf{FIXME! #1}}
\DeclareMathOperator{\Vol}{Vol}

\begin{document}

\begin{center}
\bf
Math 254A, UC Berkeley, Fall 2001 (Kedlaya) \\
Problem Set 6: The $p$-adic Numbers/Completions \\
Due in class Monday, October 8
\end{center}

Please submit \emph{eight} of the following problems. If you took the 1997
Putnam exam, please do not submit More on Valuations 1.

\head{References} Neukirch, Sections 2.1 and 2.2 for valuations
and the $p$-adic numbers; Section 2.4 for completions.

\head{More on Valuations}
\begin{enumerate}
\item
(1997 Putnam competition)
For each positive integer $n$, write the sum $\sum_{m=1}^n
\frac{1}{m}$ in the form $\frac{p_n}{q_n}$,
where $p_n$ and $q_n$ are relatively prime
positive integers.  Determine all $n$ such that 5 does not divide $q_n$.
\item
(Manjul Bhargava)
Let $S$ be an infinite
subset of $\ZZ$ and $p$ a prime number. Pick $a_0 \in S$,
then recursively define $a_n$ as an integer $m \in S$ minimizing
$v_p(m-a_0) + \cdots + v_p(m-a_{n-1})$. Prove that a polynomial with
rational coefficients takes integer values on $S$ if and only if it
is an integer linear combination of the polynomials
$P_n(x) = \prod_{i=0}^{n-1} (x-a_i)/(a_n-a_i)$. Optional
bizarre consequence:
the quantities $v_p(a_n-a_0) + \cdots + v_p(a_n-a_{n-1})$ for
$n=0,1,\dots$ do not depend on any choices made in defining the $a_i$.
\item 
Let $K$ be a number field. Prove that $\alpha \in K$ is an algebraic integer
if and only if $|\alpha|_{\gothp} \leq 1$ for all nonzero prime ideals
$\gothp$ of $\gotho_K$.
\end{enumerate}

\head{The $p$-adic Numbers}

\begin{enumerate}
\item
Neukirch exercise II.1.1:
A $p$-adic number $a$ is a rational number if and only if its sequence
of digits becomes periodic at some point. (Hint: write
$p^m a = b + c p^l/(1-p^n)$ for $0 \leq b < p^l$, $0 \leq c < p^n$.)
\item
Neukirch exercise II.2.4, modified: let $\epsilon \in 1 + p\ZZ_p$.
Show that the function from $\ZZ$ to $\ZZ_p$ defined by
$n \mapsto \epsilon^n$ extends to a function from $\ZZ_p$ to itself
which is continuous with respect to the $p$-adic valuation.
(Hint: one way to do this involves the binomial series
$(1+x)^n = \sum_i \binom{n}{i} x^i$.)
\item
Neukirch exercise II.2.6: The fields $\QQ_p$ and $\QQ_q$ are not
isomorphic unless $p=q$. (Hint: when do elements of $\QQ_p$ have
$p$-th roots?)
\item
Neukirch exercise II.2.9 ($p$-adic Weierstrass Preparation
Theorem): every nonzero power series $f(x) = \sum_{n=0}^\infty
a_n x^n \in \ZZ_p \llbracket x \rrbracket$ admits a unique representation
$f(x) = p^m P(x) U(x)$, where $U(x)$ is a unit in $\ZZ_p \llbracket x
\rrbracket$ and $P(x) \in \ZZ_p[x]$ is a monic polynomial satisfying
$P(x) \equiv x^l$ mod $p$, where $l$ is the degree of $P$.
\item
Here's why not to define the $n$-adic numbers for $n$ not prime.
Let $n$ be a composite positive integer, and define
the ring $\ZZ_n$ as the set of sequences $\{x_i\}_{i=1}^\infty$, where
$x_i \in \ZZ/n^i\ZZ$ and $x_{i+1} \equiv x_i \pmod{n^i}$. Prove that:
\begin{enumerate}
\item[(a)] if $n$ is a power of a prime $p$, then $\ZZ_n \cong \ZZ_p$;
\item[(b)] if $n$ is not a power of a prime, then $\ZZ_n$ has zerodivisors.
\end{enumerate}
Optional: prove that $\ZZ_n \cong \prod_p \ZZ_p$, where the product runs
over all primes dividing $n$.
\end{enumerate}

\head{Completions}

Throughout this section, let $R$ be a complete discrete valuation ring
with maximal ideal $\gothm$. If
you wish, you may take $R$ to be the valuation ring of
a finite extension of $\QQ_p$. You may even take $R = \ZZ_p$ if you wish.

\begin{enumerate}
\item
(Newton's iteration)
Let $P(x)$ be a monic polynomial over $R$
and $r_0 \in R$ an element such that
$|P(r_0)| < |P'(r_0)|^2$.
Prove that the sequence $\{r_n\}_{n=0}^\infty$
given by the iteration $r_{n+1} = r_n - P(r_n)/P'(r_n)$
converges to a root $r$ of $P(x)$, and that $v_p(r_n-p) \geq 2^{n-c}$
for some $c$. This gives a much faster method for computing (approximate)
roots of polynomials than does the proof of Hensel's lemma.
\item
Find a version of Newton's iteration that allows you to compute
the multiplicative inverse of a unit $r \in R$ using only multiplications
and additions, with a similar rate of convergence (i.e., you should need
about $\log n$ steps to compute the inverse modulo $\gothm^n$).
Optional: implement your method in Magma.
\item
(Eisenstein's irreducibility criterion)
Let $P(x) = x^n + a_1 x^{n-1} + \cdots + a_{n-1} x + a_n$ be a polynomial
over $R$ such that $a_1, \dots, a_n \in \gothm$ and $a_n \notin \gothm^2$.
Prove that $P(x)$ is irreducible over $R$. Optional: use this to prove
the polynomial $x^{p-1} + \cdots + x + 1$ is irreducible over $\ZZ$.
\item
Assume $\gothm$ is generated by the prime number $p \in \ZZ$ and that
the map $x \mapsto x^p$ on $R/\gothm$ is a bijection. (In
other words, $R/\gothm$ is \emph{perfect}. For example, this
is true if $R$ is the valuation ring of
a finite \emph{unramified} extension of $\QQ_p$.) Prove that
for each $x \in R/\gothm$, there exists a unique $y \in R$ which reduces
to $x$ modulo $\gothm$, such that $y$ has a $p^n$-th root for $n=1,2,\dots$.
The element $y$ is called the \emph{Teichm\"uller lift} of $x$.
(Hint: prove that $x^{p^n}$ modulo $p^{n+1}$ depends only on $x$
modulo $p$.)
\item
Show that for every automorphism $\tau$ of $R/\gothm$, there exists a unique
automorphism of $R$ inducing $\tau$ on $R/\gothm$. (Hint: every element
of $R$ can be written as a power series $\sum_{n=0}^\infty p^n y_n$,
where each $y_n$ is a Teichm\"uller lift.) If $\tau$ is the map
$x \mapsto x^p$, the resulting automorphism of $R$ is called the
\emph{Frobenius automorphism}.
\end{enumerate}

\end{document}