\newif\ifOCW
%\OCWtrue
\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}
\ifOCW\usepackage{soul}\let\oldhref\href\renewcommand{\href}[2]{\oldhref{#1}{\ul{#2}}}\fi
\ifOCW\newcommand{\due}[1]{\hfill\phantom{Due: #1}}\else\newcommand{\due}[1]{\hfill{Due: #1}}\fi
\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{plain}

% 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}}
\renewcommand{\Re}{\operatorname{Re}}
\renewcommand{\Im}{\operatorname{Im}}
\newcommand{\Li}{\operatorname{Li}}
\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{\id}{\operatorname{id}}
\newcommand{\A}{\mathcal A}
\newcommand{\Div}{\operatorname{Div}}
\renewcommand{\div}{\operatorname{div}}
\newcommand{\Pic}{\operatorname{Pic}}

\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~2025}\\\vspace{4pt}
\textbf{Problem Set \#9\due{11/19/2025}}\\\vspace{-6pt}
\normalsize
\begin{picture}(5.8,.1) 
\put(0,0) {\line(1,0){5.8}}
\end{picture}
\end{center}

% add k-divisor function 1^{*k} to problem 4

\subsection*{Description}

These problems are related to Lectures 16--17.
Your solutions should be written up in latex and submitted as a pdf-file \ifOCW\else to \href{https://www.gradescope.com/courses/1110057}{Gradescope} \fi by midnight on the date due.
\medskip

\noindent
\textbf{Instructions:} Solve Problem 0, then pick any combination of problems that sum to 100 points. Collaboration is permitted/encouraged, but you must identify your collaborators (including any LLMs you consulted) and any references you consulted outside the course \ifOCW syllabus \else\href{https://math.mit.edu/classes/18.785/2025/syllabus.html}{syllabus}\fi.
Include this information after the \textbf{Collaborators/Sources} prompt at the end of the problem set  (if there are none, you should enter ``none'', do not leave it blank).
Note that each student is expected to write their own solutions; it is fine to discuss problems with others, but your writing must be your own.


\subsection*{Problem 0.}
These are warm-up problems that do not need to be turned in.
\begin{enumerate}
\setlength\itemsep{0pt}
\item[(a)] In class we gave an elementary proof that $\vartheta(x)=O(x)$.  Give a similarly elementary proof that $x=O(\vartheta(x))$ (both bounds were proved by Chebyshev before the PNT).
\item[(b)] Prove the M\"obius inversion formula, which states that if $f$ and $g$ are functions $\Z_{\ge 1}\to \C$ that satisfy $g(n)=\sum_{d|n}f(d)$ then $f(n)=\sum_{d|n}\mu(d)g(n/d)$, where $\mu(n):=(-1)^{\#\{p|n\}}$ if $n$ is squarefree and $\mu(n)=0$ otherwise.
\end{enumerate}

\subsection*{Problem 1. The zeta function of $\Fq[t]$ (49 points)}

Recall that for a number field $K$, the Dedekind zeta function $\zeta_K(s)$ is defined by
\[
\zeta_K(s):=\sum_I \N(I)^{-s},
\]
where $I$ ranges over nonzero ideals of $\O_K$ and $\N(I)$ is the absolute norm, which is just the cardinality of the residue field $\O_K/\p$ when $I$ is a prime ideal $\p$.

The definition of $\N(\p):=\#\O_K/\p$ as the cardinality of the residue field makes sense in any global field and extends  multiplicatively to all $\O_K$-ideals.
In this problem you will investigate the zeta function $\zeta_q(s):=\sum_I \N(I)^{-s}$, where $I$ ranges over nonzero ideals of the ring of integers $\O_K:=\Fq[t]$ of the rational function field $K=\Fq(t)$.

\begin{remark}
The zeta function $\zeta_K$ of a global function field $K$ defined in Problem 4 differs from the zeta function of its ring of integers $\O_K$, which is what we are considering here.
\end{remark}

\begin{enumerate}[{\bf(a)}]
\item Show that every nonzero $\O_K$-ideal has the form $I=(f)$, with $f\in \Fq[t]$ monic, and then $\N(I)=\#(\O_K/f\O_K)=q^{\deg f}$.
Then prove that $\zeta_q(s)=\frac{1}{1-q^{1-s}}$ for $\Re(s)>1$.
\item Prove that $\zeta_q(s)$ has the Euler product
\[
\zeta_q(s)=\prod_\p(1-\N(\p)^{-s})^{-1},
\]
valid for $\Re(s)>1$.
\item Prove that $\zeta_q(s)$ extends to a meromorphic function on $\C$ with a simple pole at $s=1$ and no zeros.  Give the residue of the pole at $s=1$.
\item Define a completed zeta function $Z(s)=G(s)\zeta_q(s)$, where $G(s)$ is a suitably chosen meromorphic function, so that $Z(s)$ satisfies the functional equation
\[
Z(s)=Z(1-s)
\]
with simple poles at $s=0,1$ and no other poles.
\item Let $a_d$ denote the number of irreducible monic polynomials in $\Fq[t]$ of degree $d$.  Using (a) and~(b), prove that 
\[
\sum_{d|n}da_d=q^n.
\]
and use this to derive an explicit formula for $a_n$.
\item Prove the prime number theorem for $\Fq[t]$, which states that
\[
a_n=\frac{q^n}{n}+O\left(\frac{1}{n}q^{n/2}\right).
\]
\end{enumerate}
\begin{remark}
The error term in (f) is comparable to the error term in the PNT under the Riemann hypothesis (replace $q^n$ with $x$); note that the analog of the Riemann hypothesis for $\zeta_q(s)$ is (vacuously) true, by (c).
\end{remark}
\begin{enumerate}[{\bf(a)}]
\setcounter{enumi}{6}
\item Let $S(n)$ be the set of monic polynomials of degree $n$ in $\Fq[t]$, and let $I(n)$ be the subset of polynomials in $S(n)$ that are irreducible. Show that $\#I(n)/\#S(n)\sim \frac{1}{n}$.
Now let $R(n)$ be the subset of polynomials in $S(n)$ that have no roots in $\Fq$.  Give an asymptotic estimate for $\#R(n)/\#S(n)$.
\item Let $Q(n)$ denote the subset of $S(n)$ consisting of squarefree polynomials.  Prove $\lim_{n\to\infty}\#Q(n)/\#S(n)=1/\zeta_q(2)$ and derive an asymptotic estimate for this limit.
\item For nonzero $f\in \O_K$ define $\Phi$ via $\Phi(f):=\#(\O_K/f\O_K)^\times$.  Prove the following
\begin{enumerate}[1.]
\item $\Phi(f)=\N(f)\prod_{p|f}(1-\N(p)^{-1})$, where $p$ ranges over the irreducible factors of $f$.
\item For all $f,g\in \O_K$ with $(f,g)=1$ we have $g^{\Phi(f)}\equiv 1\bmod f$.
\end{enumerate}
\end{enumerate}

\subsection*{Problem 2. Bernoulli numbers (49 points)}

For integers $n\ge 0$, the \emph{Bernoulli polynomials} $B_n(x)\in \Q[x]$ are defined as the coefficients of the exponential generating function
\[
E(t,x):=\frac{te^{tx}}{e^t-1} = \sum_{n\ge 0}\frac{B_n(x)}{n!}t^n.
\]
The \emph{Bernoulli numbers} $B_n\in \Q$ are defined by $B_n=B_n(0)$.

\begin{enumerate}[{\bf(a)}]
\item Prove that $B_0(x)=1$, $B_n'(x)=nB_{n-1}(x)$, and $B_n(1)=B_n(0)$ for $n\ne 1$, and that these properties uniquely determine the Bernoulli polynomials.
\item Prove that $B_n(x+1)-B_n(x)=nx^{n-1}$ and
\[
B_n(x+y)=\sum_{k=0}^n\binom{n}{k}B_k(x)y^{n-k}.
\]
Use this to show that $B_k$ can alternatively be defined by the recurrence $B_0=1$ and
\[
B_n = -\frac{1}{n+1}\sum_{k=0}^{n-1}\binom{n+1}{k}B_k
\]
for all $n>0$, and show that $B_n=0$ for all odd $n>1$.
\item Recall the hyperbolic cotangent function $\coth z := \frac{e^z+e^{-z}}{e^z-e^{-z}}$.
Prove that
\[
z\coth z = \sum_{n\ge 0} B_{2n}\frac{(2z)^{2n}}{(2n)!}.
\]
\item Show that $\cot z = i \coth iz$ and then derive (as Euler did) the identity
\[
z\cot z = 1-2\sum_{k\ge1}\frac{z^2}{k^2\pi^2-z^2}.
\]
\item Use (c) and (d) to prove that for all $n\ge 1$ we have
\[
\zeta(2n) = (-1)^{n-1}\frac{(2\pi)^{2n}B_{2n}}{2\cdot(2n)!},
\]
and then use the functional equation to prove that for all $n\ge 1$ we have
\[
\zeta(-n) = - \frac{B_{n+1}}{n+1}.
\]
\item Prove (rigorously!) that for any integer $n>1$ the asymptotic density of integers that are $n$-\emph{power free} (not divisible by $p^n$ for any prime $p$) is $1/\zeta(n)$ and compute this density explicitly for $n=2,4,6$.
\item Prove that for all integer $n,N > 1$ we have
\[
\sum_{m=0}^{N-1}(m+x)^{n-1} = \frac{B_n(N+x)-B_n(x)}{n}.
\]
Use this to deduce Faulhaber's formula
\[
P_n(N):=\sum_{m=1}^{N-1} m^n = \frac{1}{n+1}\sum_{k=0}^n\binom{n+1}{k}B_kN^{n+1-k}
\]
for summing $n$th powers.  Compute the polynomials $P_n(N)$ explicitly for $n=2,3,4$.
\end{enumerate}

\subsection*{Problem 3. Arithmetic functions and Dirichlet series (49 points)}

Recall that an \emph{arithmetic function} is a function $a\colon \Z_{\ge 1}\to \C$; we say that $a\ne 0$ is \emph{multiplicative} if $a(mn)=a(m)a(n)$ holds for all relatively prime $m,n$, and \emph{totally multiplicative} if this holds for all $m,n$.
Below are some examples; as usual,~$p$ denotes a prime, $p^e$ denotes a (nontrivial) prime power, and $d|n$ indicates that~$d$ is a positive divisor of $n$.
\begin{itemize}
\setlength{\itemsep}{0pt}
\item $0(n)=0$,\ \ $1(n)=1$,\ \ $\id(n):=n$, \ \ $e(n):=0^{n-1}$;
\item $\tau(n):=\#\{d|n\}$, \ \ $\sigma(n):=\sum_{d|n}d$;
\item $\omega(n):=\#\{p|n\}$,\ \  $\Omega(n):=\#\{p^e|n\}$, \  $\phi(n):=\#(\Z/n\Z)^\times$;
\item $\lambda(n):=(-1)^{\Omega(n)}$,\ \ $\mu(n):=(-1)^{\omega(n)}\cdot 0^{\Omega(n)-\omega(n)}$, \ \  $\mu^2(n):=\mu(n)^2$.
\end{itemize}
The set of all arithmetic functions forms a $\C$-vector space that we denote $\A$.
Associated to each arithmetic function is a \emph{Dirichlet series} $\sum_{n\ge 1}a_nn^{-s}$ defined by
\[
D_a(s):=\sum_{n\ge 1}a(n)n^{-s}
\]
The \emph{Dirichlet convolution} $a*b$ of arithmetic functions $a$ and $b$ is defined by
\[
(a*b)(n) := \sum_{d|n}a(d)b(n/d),
\]
For $k\in\Z_{\ge 0}$ we use $f^{*k}$ to denote the $k$-fold convolution $f*\cdots *f$, with $f^{*0}:=e$.

\begin{enumerate}[{\bf(a)}]
\item For arithmetic functions $a$ and $b$ prove that $D_{a*b}=D_aD_b$, and show that endowing~$\A$ with a multiplication defined by Dirichlet convolution makes $\A$ a $\C$-algebra that is isomorphic to the $\C$-algebra of Dirichlet series (with the usual multiplication).
\item Show that $\A$ is a local ring with unit group $\A^\times=\{f\in \A:f(1)\ne 0\}$ and maximal ideal $\A_0=\{f\in \mathcal A:f(1)=0\}$.  Prove that the set of multiplicative functions $\mathcal M$ forms a subgroup of $\mathcal A_1:=\{f\in \A:f(1)=1\}\subseteq \A^\times$. Is this also true of the set of totally multiplicative functions?
\item Prove the following identities $\mu*1=e$, $\phi*1=\id$, $\mu*\id=\phi$, $1*1=\tau$, $\id*1=\sigma$.
Use $\mu*1=e$ to give a one-line proof of the M\"obius inversion formula.
\item For $k\in\Z_{\ge 1}$ define $\tau_k(n):= \sum_{n_1n_2\cdots n_k=n}1$, so $\tau_1=1$ and $\tau_2=\tau=1*1$.
Prove that $\tau_k = 1^{*k}$, and $D_{\tau_k}(s)=\zeta(s)^k$, where $\zeta(s)=\sum_{n\ge 1} n^{-s}$ is the Riemann zeta function.
\item  Define the exponential map $\exp\colon\A\to \A$ by
\[
\exp(f):=\sum_{n=0}^\infty \frac{f^{*n}}{n!} = e + f + \frac{f*f}{2} + \cdots
\]
Prove that $\exp$ defines a group isomorphism from $(\A_0,+)$ to $(\A_1,*)$ with inverse
\[
\log(f):=\sum_{n=1}^\infty \frac{(-1)^{n-1}(f-e)^{*n}}{n}.
\]
\item Define $\kappa(n)$ to be $1/k$ if $n=p^k$ is a prime power and $0$ otherwise (for us $1$ is not a prime power).
Prove that $\exp\kappa=1$, and deduce that $\exp(-\kappa)=\mu$ and $\exp(2\kappa)=\tau$.
\item Prove that each $f\in \A_1$ has a unique square-root $g\in \A_1$ for which $g^{*2}=f$ that we denote $f^{*1/2}$.
Prove that $1^{*1/2}=\exp(\kappa/2)$ and compute $\exp(\kappa/2)(n)$ for $n$ up to $10$.
\end{enumerate}

\subsection*{Problem 4. The Weil conjectures for global function fields (49 points)}

Let $K/\Fq(t)$ be a global function field, with $\Fq$ algebraically closed in $K$.
The \emph{divisor group} $\Div K$ is the free abelian group generated by the places of $K$; it consists of formal sums $\sum_P n_PP$ over $P\in M_K$ in which only finitely many $n_P\in\Z$ are nonzero.
This is the same as the group of $M_K$-divisors we defined in Lecture 15, but here we view $\Div K$ as an additive group and use $P$ to denote a place rather than $v$.

Corresponding to each $f\in K^\times$ we have a \emph{principal divisor}
\[
\div(f) := \sum_P \ord_P(f)P,
\]
where $\ord_P\colon K^\times\to \Z$ is the discrete valuation corresponding to $P$, which we extend to $\Div K$ by defining $\ord_P(\sum_Q n_Q Q)=n_P$.  Two divisors $D_1$ and $D_2$ are \emph{linearly equivalent} if $D_1-D_2$ is a principal divisor, and we write $D_1\sim D_2$ to indicate this; this defines an equivalence relation on $\Div K$ and we use $[D]$ to denote the equivalence class of $D$.

The \emph{degree} of a place $P$ is the dimension of the residue field of the local field $K_P$ as an $\Fq$-vector space; it extends to a group homomorphism $\deg\colon \Div K\to \Z$ whose kernel contains the subgroup of principal divisors (by the product formula); the corresponding quotient is denoted $\Pic^0 K$.
The \emph{norm} of a divisor $D$ is defined by $\N(D):=q^{\deg D}$; when $D=P$ this is the cardinality of the residue field and if $D$ is supported only on finite places this agrees with the absolute norm defined in Problem 1.

We partially order divisors by defining
\[
D_1\le D_2 \qquad\Longleftrightarrow\qquad \ord_P(D_1)\le \ord_P(D_2)\text{ for all } P\in M_K.
\]
A divisor $D\ge 0$ is said to be \emph{effective}.
The \emph{zeta function} of $K$ is defined as a sum over effective divisors
\[
\zeta_K(s):=\sum_{D\ge 0}\N(D)^{-s}=\sum_{D\ge 0}q^{-s\deg(D)}
\]
The \emph{Weil conjectures} (for global function fields) concern three properties of $\zeta_K(s)$:
\begin{itemize}
\item $\zeta_K(s)$ is a rational function of $q^{-s}$.
\item There is a functional equation that relates $\zeta_K(1-s)$ and $\zeta_K(s)$.
\item The zeros of $\zeta_K(s)$ all lie on the line $\Re(s)=1/2$.
\end{itemize}
In this problem you will prove the first two; Weil proved the third in the 1940s, and a generalization to algebraic varieties of higher dimension conjectured by Weil was proved by Deligne in the 1970s.
\smallskip

Associated to each divisor $D\in \Div K$ is a \emph{Riemann-Roch space}
\[
L(D) := \{f\in K^\times:\div(f)\ge -D\} \cup \{0\},
\]
which is an $\Fq$-vector space whose finite dimension we denote $\ell(D)\in\Z_{\ge 0}$.
The degree $\deg D$ and dimension $\ell(D)$ of a divisor $D$ depend only on the divisor class $[D]$ and are related by the following theorem (which you are not asked to prove).

\begin{theorem}[Riemann-Roch]
Let $K$ be a global function field.
There is an integer $g\ge 0$ and divisor $C\in \Div K$ such that for all divisors $D\in \Div K$ we have
\[
\ell(D)=\deg(D)-g+1+\ell(C-D).
\]
\end{theorem}

\begin{enumerate}[{\bf(a)}]
\item Prove that $\ell(C)=g$ and $\deg(C)=2g-2$, and that for $\deg(D)\ge 2g-2$ we have $\ell(D)=\deg(D)-g+1$ unless $D\sim C$.  Conclude that both the integer $g$ (the \emph{genus}) and the divisor class $[C]$ (the \emph{canonical class}) are uniquely determined.
\item Prove that for any $n\ge 0$ the number of effective divisors of degree $n$ is finite, and the number of divisor classes of degree $n$ is finite (so in particular, the group $\Pic^0 K$ of divisor classes of degree $0$, is finite).
\item Prove that for any divisor $D$ the number of effective divisors in $[D]$ is $\frac{q^{\ell(D)}-1}{q-1}$.
\item Prove that the sum defining $\zeta_K(s)$ converges on $\Re(s)>1$ and we have an Euler product
\[
\zeta_K(s)=\prod_P(1-\N(P)^{-s})^{-1}.
\]
\item Let $a_n$ be the number of effective divisors of degree $n$.  Prove that
\[
a_n=\sum_{\deg([D])=n}\frac{q^{\ell(D)}-1}{q-1},
\]
where the sum is over the divisor classes of degree $n$, and show that if we define $Z_K(u):=\sum_{n\ge 0}a_nu^n$ then $\zeta_K(s)=Z_K(q^{-s})$ for $\Re s>1$.
\item Let $e\Z=\deg(\Pic K)$. Prove there is a polynomial $L_K\in\Z[u]$ of degree $2g$ for which
\[
Z_K(u)=\frac{L_K(u^e)}{(1-u^e)(1-(qu)^e)},
\]
and show that $L_K(0)=1$ and $L_K(1)=\#\Pic^0 K $.
\item For $n\ge 1$ let $K_n:=K\otimes_{\Fq}\F_{q^n}$.  Show that $Z_{K_n}(u^n)=\prod_{i=1}^n Z_K(\zeta_n^iu)$, where $\zeta_n:= e^{2\pi i/n}$, and use this to prove that we must have $e=1$ in part (f).
\item Prove that $Z_K(q^{-s})$ is meromorphic on $\C$ and thus provides an analytic continuation of $\zeta_K(s)$ to $\C$ with simple poles at $s=0,1$.  Are these the only poles?
\item Let $\xi_K(s):=q^{(g-1)s}\zeta_K(s)$.  Prove that $\xi_K(s)$ satisfies the functional equation
\[
\xi_K(1-s)=\xi_K(s).
\]
\end{enumerate}

\subsection*{Problem 5. Survey (2 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 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.
\medskip

\noindent
\textbf{Collaborators/Sources}

\end{document}