\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{\F}{\mathbb{F}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Qbar}{\overline{\mathbb{Q}}} \newcommand{\R}{\mathbb{R}} \newcommand{\C}{\mathbb{C}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Aut}{{\rm Aut}} \newcommand{\Gal}{{\rm Gal}} \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}{{\rm ord}} \newcommand{\cl}{{\rm cl}} \newcommand{\disc}{{\rm disc}} \newcommand{\p}{\mathfrak{p}} \newcommand{\m}{{\mathfrak m}} \renewcommand{\a}{\mathfrak{a}} \renewcommand{\b}{\mathfrak{b}} \newcommand{\Frob}{{\rm Frob}} \newtheorem*{theorem}{Theorem} \begin{document} \setlength{\unitlength}{1in} \begin{center} \large \textbf{18.785 Number Theory\hspace{228pt}Fall~2019}\\\vspace{4pt} \textbf{Problem Set \#1\hspace{220pt}Due: 09/11/2019} \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 material covered in Lectures 1--2. 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 named \texttt{SurnamePset1.pdf} (replace ``\texttt{Surname}'' with your surname) via e-mail to \texttt{drew@math.mit.edu} before \textbf{noon} on the date due (late problem sets will not be graded, but early submissions are welcome). Collaboration is permitted/encouraged, but you must identify your collaborators and any references you consult that are not listed in the syllabus; if this does not apply to you, write \textbf{Sources consulted:\ none} at the top of your problem set. The first person to spot each typo/error in any of the problem sets or lecture notes will receive 1--5 points of extra credit, depending on the severity of the error (please do report any errors you spot, even trivial typos -- future students will thank you). \medskip \noindent \textbf{Instructions:} First solve the warm up problems; these do not need to be formally written up or turned in. Then pick any three of Problems 1--4 to solve and write up your answers in latex. Finally, complete Problem 5, which is a short survey whose answers will help shape future problem sets and lectures. \subsection*{Problem 0. Warm up (0 points)} These warm up exercises do not need to be written up or turned in, they are provided simply to help you check your understanding. \begin{enumerate} \item[\textbf{(a)}] Prove the nonarchimedean ``triangle equality": if $|\cdot|$ is a nonarchimedean absolute value on a field $k$ and $|x|\ne |y|$ then $|x+y|=\max(|x|,|y|)$. \item[\textbf{(b)}] Let $K$ be a global field (a finite extension of $\Q$ or $\Fp(t)$). Show that if $K$ has characteristic zero then there is only one way to embed $\Q$ in $K$ but when $K$ has positive characteristic there are infinitely many different ways of embedding $\Fp(t)$ in $K$. In particular, show that the field $K:=\mathrm{Frac}( \Fp[x,y]/(y^2-x^3-x-1))$ can be viewed as both a degree 2 extension of $\Fq(x)$ and a degree 3 extension of $\Fq(y)$, but that the isomorphism $\Fq(y)\simeq \Fq(x)$ does not commute with the inclusions. \item[\textbf{(c)}] Write down a monic polynomial $f\in \Z[x]$ with $\sqrt{2}+\sqrt{3}$ as a root. \end{enumerate} \subsection*{Problem 1. Absolute values on $\Q$ (32 points)} \begin{enumerate} \item[\textbf{(a)}] Prove that an absolute value $|\cdot|$ on a field $k$ is nonarchimedean if and only if $|n|\le 1$ for all $n\in \Z_{>0}$ (here $n:=1+\cdots+1\in k$ for all fields $k$). \item[\textbf{(b)}] Prove Ostrowski's Theorem: every nontrivial absolute value on $\Q$ is equivalent to~$|\cdot|_p$ for some prime $p\le \infty$. \item[\textbf{(c)}] Prove the product formula for $\Q$: show that $\prod_{p\le\infty}|x|_p=1$ for all $x\in \Q^\times$. \end{enumerate} \subsection*{Problem 2. Absolute values on $\Fq(t)$ (32 points)} For each prime $\pi\in\Fq[t]$ and any nonzero $f\in \Fq[t]$, let $v_\pi(f)$ be the largest integer for which $\pi^n|f$, equivalently, the largest $n$ for which $f\in(\pi^n)$. For each $f/g\in\Fq(t)^\times$ define \[ v_\pi(f/g):=v_\pi(f)-v_\pi(g), \] and let $v_\pi(0):=\infty$; also define $\deg 0 := -\infty$ and $\deg(f/g) := \deg f -\deg g$. \begin{enumerate} \item[\textbf{(a)}] For each prime $\pi\in \Fq[t]$, define $|r|_\pi = (q^{\deg\pi})^{-v_\pi(r)}$ for all $r\in \Fq(t)$. Show that $|\cdot |_\pi$ is a nonarchimedean absolute value on $\Fq(t)$. \item[\textbf{(b)}] Define $|r|_\infty := q^{\deg r}$, for all $r\in\Fq(t)$. Prove that $|\cdot|_\infty$ is a nonarchimedean absolute value on $\Fq(t)$. \item[\textbf{(c)}] Determine the residue field of $\Fq(t)$ with respect to $|\cdot|_\pi$; the residue field is the quotient of the valuation ring $\{x\in \Fq(t):|x|_\pi \le 1\}$ by its unique maximal ideal. \item[\textbf{(d)}] Describe the valuation ring $R:=\{x\in \Fq(t):|x|_\infty \le 1\}$ and its unique maximal ideal~$\m$. Then determine the residue field of $\Fq(t)$ with respect to $|\cdot|_\infty$. \item[\textbf{(e)}] Prove Ostrowski's theorem for $\Fq(t)$: every nontrivial absolute value on $\Fq(t)$ is equivalent to $|\cdot|_\infty$ or $|\cdot |_\pi$ for some prime $\pi\in \Fq[t]$. More precisely, show that if $\Vert\cdot\Vert$ is a nontrivial absolute value on $\Fq(t)$, either $\Vert t\Vert >1$ and $\Vert\cdot\Vert\sim | \cdot |_\infty$, or $\Vert t \Vert\le 1$ and $\Vert\cdot \Vert\sim|\cdot |_\pi$ for some prime $\pi\in\Fq[t]$. \end{enumerate} \noindent In view of (e), we regard $\infty$ as a ``prime" of $\Fq(t)$ and let $\pi$ range over both monic irreducible polynomials in $\Fq[t]$ and $\infty$. \begin{enumerate} \item[\textbf{(f)}] Prove the product formula for $\Fq(t)$: show that $\prod_{\pi}|r|_\pi = 1$ for every $r\in\Fq(t)^\times$ . \end{enumerate} \subsection*{Problem 3. Quadratic fields (32 points)} Let $K=\Q(\sqrt{d})$ with $d\ne 0,1$ a squarefree integer, and let $\p$ be a nonzero prime ideal of the ring of integers $\O_K$ that does not divide $(2d)$. \begin{enumerate} \item[\textbf{(a)}] Give explicit generators for $\O_K$ as a $\Z$-module. \item[\textbf{(b)}] Determine the index of $\Z[\sqrt{d}]$ in $\O_K$ as a function of $d$. \item[\textbf{(c)}] Show that $\p$ can be written in the form $(p,\alpha)$, with $(p)=\p\cap \Z$ and $\alpha\in \O_K$. \item[\textbf{(d)}] Show that $\O_K/\p\simeq \F_{q}$ where $q=[\O_K:\p]$ is either $p$ or $p^2$, with $\p=(p,\alpha)$. Give an explicit criterion in terms of $p$ and $d$ for when the two cases occur. \item[\textbf{(e)}] Determine the number of equivalence classes of archimedean absolute values of $\Q(\sqrt{d})$ as a function of $d$. \end{enumerate} \subsection*{Problem 4. The Euler $\phi$-function. (32 points)} Let $A$ denote $\Z$ or $\Fp[t]$, and let $|\cdot|$ denote $|\cdot |_\infty$ (the standard archimedean absolute value on $\Q$ or the nonarchimedean absolute value of $\Fp(t)$ defined in Problem 2). Recall that $a\perp b$ means $(a,b)=A$. Throughout this problem, we assume $a,b\in A$ are nonzero, and understand ``$a\bmod b$'' to mean the image of $a$ under the quotient map $A\to A/(b)$. \begin{enumerate} \item[\textbf{(a)}] Prove that $A/(a)$ is a ring with $|a|$ elements. \end{enumerate} Define the Euler $\phi$-function $\phi\colon A_{\ne 0}\to \Z_{>0}$ by $\phi(a):=\#(A/(a))^\times$. \begin{enumerate} \item[\textbf{(b)}] Prove $\phi(ab)=\phi(a)\phi(b)$ if $a\perp b$ and $\phi(a^n)= |a|^{n-1}(|a|-1)$ for $a$ prime and $n\ge 1$. \item[\textbf{(c)}] Prove that $\phi(a)=|a|\prod_{q|a}(1-|q|^{-1})$, where $q$ ranges over primes. \item[\textbf{(d)}] Prove that for $a\perp b$ we have $a^{\phi(b)}\equiv 1\bmod b$. \item[\textbf{(e)}] Prove that if $b$ is prime then $ \prod_{0 < |a| < |b|} a \equiv \begin{cases}+1\bmod b & \text{if }A=\Z;\\-1\bmod b &\text{if }A=\Fp[t].\end{cases} $ \item[\textbf{(f)}] Let $a\perp b$ with $b$ prime and let $r\ge 2$ divide $|b|-1$. Show that $a\bmod b$ is an $r$th power if and only if $a^{(|b|-1)/r}\equiv 1\bmod b$, and $\#\{c^r:c\in (A/(b^n))^\times\}=\phi(b^n)/r$. \end{enumerate} \subsection*{Problem 5. Survey (4 points)} 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 \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 9/4 & Absolute values, discrete valuations & & & & \\\hline 9/9 & Localizations, Dedekind domains & & & & \\\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}