%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                                                                        %
%                     Homework 1:                                        %
%                     Analytic Number Theory                             %
%                                                       GM   18/03/2015  %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% begin: AMS-package.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[11pt,a4paper]{amsart}
\usepackage{amsmath,amsthm}
\usepackage[psamsfonts]{amssymb}
\pagestyle{plain}

\DeclareMathOperator{\odd}{odd}
\DeclareMathOperator{\even}{even}

\DeclareMathOperator{\Ree}{Re}
\DeclareMathOperator{\Imm}{Im}
\renewcommand{\Re}{{\Ree}}
\renewcommand{\Im}{{\Imm}}
\newcommand{\Res}{Res}
\DeclareMathOperator{\eul}{\varphi}
\DeclareMathOperator{\ceb}{\vartheta}
\DeclareMathOperator{\GCD}{GCD}
\DeclareMathOperator{\sgn}{sgn}
\newcommand{\Li}{\text{{\sl li}}}

\newcommand{\field}[1]{\mathbb{{#1}}}
\newcommand{\intpart}[1]{\left\lfloor#1\right\rfloor}
\newcommand{\fracpart}[1]{\left\{#1\right\}}
\newcommand{\intpartup}[1]{\left\lceil#1\right\rceil}

\newcommand{\R}{\field{R}}
\newcommand{\C}{\field{C}}
\newcommand{\N}{\field{{N}}}
\newcommand{\Z}{\field{{Z}}}
\newcommand{\Q}{\field{{Q}}}

\newcommand{\Id}{\mathbb{{I}}}
\newcommand{\CC}{\mathcal{{C}}}

\newcommand{\bs}[1]{{\boldsymbol{#1}}}
\newcommand{\e}{\bs{e}}
\newcommand{\V}{\bs{v}}

\newcommand{\A}{\mathcal{A}}
\newcommand{\B}{\mathcal{B}}

%\newcommand{\aLpha}{\mb{\alpha}}
%\newcommand{\bEta}{\mb{\beta}}

%\newcommand{\pSi}{\mb{\psi}}
%\newcommand{\PSi}{\mb{\Psi}}
%\newcommand{\pHi}{\mb{\phi}}
%\newcommand{\PHi}{\mb{\Phi}}

%\newcommand{\nU}{\mb{\nu}}
%\newcommand{\tAu}{\mb{\tau}}

\newcommand{\Uno}{{\bs 1}}

\newenvironment{Lista}{\begin{list}{$\bullet$}{
\setlength{\labelwidth}{.5cm}
\setlength{\leftmargin}{.2cm}
\setlength{\itemsep}{.1cm}
}
}{\end{list}}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% changes to the layout
\setlength{\oddsidemargin}{0cm}
\setlength{\evensidemargin}{0cm}
\setlength{\topmargin}{0cm}
\setlength{\textwidth}{16cm}
\setlength{\textheight}{23cm}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\thispagestyle{empty}

\begin{document}
\begin{center}
{\bf\LARGE{Analytic Number Theory:} Homework 1%\\[.3cm]
%    \large{sheet 1}
    } (2015)
\end{center}
\vspace{1cm}

\begin{enumerate}
\item (Exercise 1.4 in Notes) Prove that:
      \begin{align*}
      \sum_{\substack{k=1\\ k\even}}^N \frac{1}{k} = \frac{1}{2}\,\ln(N/2) + \frac{\gamma}{2} + O(1/N),\qquad
      \sum_{\substack{k=1\\ k\odd}}^N  \frac{1}{k} = \frac{1}{2}\,\ln(2N)  + \frac{\gamma}{2} + O(1/N).
      \end{align*}
      Use this result to prove that for every $m,n\geq 1$ one has
      \begin{align*}
      &\underbrace{1+\tfrac{1}{3}+\cdots +\tfrac{1}{2m-1}}_{m\ \text{terms}}
      -(\underbrace{\tfrac{1}{2}+\tfrac{1}{4}+\cdots +\tfrac{1}{2n}}_{n\ \text{terms}})\\
      +&
      \underbrace{\tfrac{1}{2m+1}+\tfrac{1}{2m+3}+\!\cdots\!+\tfrac{1}{4m-1}}_{m\ \text{terms}}
      -(\underbrace{\tfrac{1}{2n+2}+\tfrac{1}{2n+4}+\!\cdots\!+\tfrac{1}{4n}}_{n\ \text{terms}})
      +\cdots
      = \frac{1}{2}\ln(4m/n).
      \end{align*}
      Note that these sums are different reordering of the series $\sum_{n=1}^\infty \frac{(-1)^{n-1}}{n}$.
      \bigskip

\item Prove that if $\ell\in\N$ and $\Re(s)>1$, then
      \[
       \int_1^{+\infty} \frac{(\log x)^\ell}{x^s}dx = \frac{\ell!}{(s-1)^{\ell+1}}
      \]
      by proving the claim for $\ell=0$, i.e. that
      \[
       \int_1^{+\infty} \frac{dx}{x^s} = \frac{1}{s-1},
      \]
      and then applying the derivative operator $\frac{d}{ds}$ recursively.\\
      {\bf Warning:} The argument proving that
      $\frac{d}{ds}\int_1^{+\infty} \frac{(\log x)^\ell}{x^s}dx
         = \int_1^{+\infty} \frac{d}{ds}\frac{(\log x)^\ell}{x^s}dx$
       is required!
      \bigskip

\item Let $\mu^{*k}$ be the $*$-product of $k$ copies of $\mu$ (so that $\mu^{*2} = \mu*\mu$, $\mu^{*3} =
      \mu*\mu*\mu$), with $\mu^{*0}:=\Uno$. Prove that $\mu^{*k}$ is multiplicative and that
      \[
       \mu^{*k}(p^a) =
       \begin{cases}
        (-1)^a\binom{k}{a}  & \text{when } 0\leq a\leq k\\
        0                   & \text{otherwise}.
       \end{cases}
      \]
      \bigskip

\item Let $F$ be the Dirichlet series associated with the arithmetical function $f$, so that
      $F(s)= \sum_{n=1}^\infty f(n)/n^s$.
      \begin{Lista}
      \item[a)] Prove that the series defining $F(s)$ converges somewhere if and only if there exists $\theta\in\R$ such that
                $f(n)\ll n^\theta$ when $n\to\infty$.
      \item[b)] Assume that $F(s)$ converges somewhere; prove that there exists $\sigma_0$ such that
                $F(s)\neq 0$ when $\Re(s)>\sigma_0$.
      \end{Lista}
      \noindent%
      {\bf Hint:} for the second part, prove that $F(s)$ is dominated by its first non zero term when $\Re(s)$ is large enough.
      \bigskip

\item Let $g\colon\N\to\C$ be the arithmetical function giving the Dirichlet coefficients of the Dirichlet series
      $1/\zeta(2s)$.
      \begin{Lista}
      \item[a)] Prove that $g(k^2)=\mu(k)$ for every integer $k$, and that $g(k)=0$ when $k$ is not a square.
      \item[b)] Prove that $|\mu(n)|=\sum_{d|n}g(d)$. Deduce that
                \[
                  \sum_{n\leq x}|\mu(n)| = \sum_{\substack{n,m\\ nm\leq x}}g(m)
                                         = \sum_{\substack{n,k\\ nk^2\leq x}}\mu(k)
                                         = \sum_{k\leq \sqrt{x}}\mu(k)\sum_{n\leq x/k^2} 1
                                         = \sum_{k\leq \sqrt{x}}\mu(k)\intpart{\frac{x}{k^2}}.
                \]
      \item[c)] Use the previous equality to deduce that
                \[
                  \sharp\{n\in\N\colon n\leq x,\ n\text{ is squarefree}\}
                      = \sum_{n\leq x}|\mu(n)|
                      = \frac{x}{\zeta(2)} + O(\sqrt{x}).
                \]
      \item[d)] Deduce that for every $\theta>1/2$ there exists $x_0=x_0(\theta)$ such that
                \[
                  \{n\in\N\colon n\in[x,x+x^\theta],\ n\text{ is squarefree}\} \neq \emptyset
                  \qquad \forall x\geq x_0.
                \]
      \end{Lista}
      \bigskip

\item Imitating the previous exercise, prove that
                \[
                  \sharp\{n\in\N\colon n\leq x,\ n\text{ is cubefree}\}
                      = \frac{x}{\zeta(3)} + O(x^{1/3}).
                \]
      \noindent%
      {\bf Hint:} recall that $n$ is called \emph{cubefree} when $p|n$ $\implies$ $p^3\nmid n$. Let
      $g\colon\N\to \C$ be the arithmetic function giving the Dirichlet coefficients of $1/\zeta(3s)$.
      Prove that $g(k^3)=\mu(k)$ and that $g(k)=0$ when $n$ is not a cube. Prove that the characteristic
      function of cubefree numbers $\delta_3$ is related to $g$ by: $\delta_3(n) = \sum_{d|n}g(d)$.
      \bigskip


\item For every positive integer $n$ let $f(n):=\sharp\{x\in\Z/n\Z\colon x^2=1\pmod{n}\}$, i.e. the
      number of solutions of the equation $x^2=1$ in the ring $\Z/n\Z$.
      \begin{Lista}
      \item[a)] Prove that $f$ is multiplicative.
      \item[b)] Prove that $f(2)=1$, $f(2^2)=2$, $f(2^k)=4$ for every $k\geq 3$.
      \item[c)] Prove that $f(p^k)=2$ when $p$ is odd, for every $k$.
      \item[d)] Let $F(s):=\sum_{n=1}^{\infty} f(n)/n^s$ be the Dirichlet series associated with $f(n)$,
                and let $H(s)$ be the complex function defined in such a way that
                \[
                 F(s) = H(s)\zeta^2(s).
                \]
                Prove that
                \[
                  H(s) = \prod_p \Big(1+\sum_{k=1}^\infty \frac{f(p^k)}{p^{ks}}\Big)\Big(1-\frac{1}{p^s}\Big)^2
                \]
                so that $H(s)$ may be written as Euler product and as Dirichlet series.
      \item[e)] Working out an explicit expression for the Euler product of $H(s)$, prove that
                it converges absolutely for $\Re(s)> 1/2$.
      \item[f)] Let $h(n)$ be the sequence of numbers such that $H(s)=\sum_{n=1}^\infty h(n)/n^s$;
                imitating the proof of the previous step, prove that this series converges absolutely
                for $\Re(s)>1/2$.
      \item[g)] Recall that $d(n)$ is the sequence of Dirichlet's coefficients of $\zeta^2(s)$, so that from
                Step d) one gets that
                \[
                 f(n) = \sum_{m|n} h(m)d(\frac{n}{m}).
                \]
                Deduce that
                \[
                 \sum_{n\leq x} f(n)
                   = \sum_{\substack{m,n\\ mn\leq x}} h(m)d(n)
                   = \sum_{m\leq x} h(m) \sum_{n\leq \frac{x}{m}}d(n).
                \]
      \item[h)] Use Dirichlet's result on the mean value of the divisor function (i.e., the fact
                that $\sum_{n\leq y}d(n) = y\log y + O(y)$) to deduce that
                \[
                 \sum_{n\leq x} f(n)
                   = \Big(\sum_{m\leq x} \frac{h(m)}{m}\Big) x\log x
                     - x\sum_{m\leq x} \frac{h(m)\log m}{m}
                     + O\Big(x\sum_{m\leq x} \frac{|h(m)|}{m}\Big).
                \]
      \item[i)] Use Step e) to deduce that
                \[
                 \sum_{n\leq x} f(n)
                   = \Big(\sum_{m\leq x} \frac{h(m)}{m}\Big) x\log x
                     + O(x)
                   = \Big(H(1) - \sum_{m > x} \frac{h(m)}{m}\Big) x\log x
                     + O(x).
                \]
      \item[l)] Use Step e) to deduce that for every $\eta>0$,
                \[
                 \Big|\sum_{m > x} \frac{h(m)}{m}\Big|
                   \leq \sum_{m > x} \frac{|h(m)|}{m}
%                   \leq \frac{1}{x^{1/2-\eta}}\sum_{m > x} \frac{|h(m)|}{m^{1/2+\eta}}
                   \ll_\eta \frac{x^\eta}{x^{1/2}}
                \]
                so that Step i) gives
                \[
                 \sum_{n\leq x} f(n)
                   = H(1)x\log x
                     + O(x).
                \]
      \item[m)] From the representation of $H(s)$ as Euler product deduce that $H(1)
                 = \prod_p(1-\frac{1}{p^2}) = \frac{1}{\zeta(2)} = \frac{6}{\pi^2}$,
                 and conclude that
                \[
                 \sum_{n\leq x} f(n)
                   = \frac{6}{\pi^2} x\log x
                     + O(x).
                \]
      \end{Lista}
      \noindent {\bf Hint:} For Steps b) and c) recall that $(\Z/p^k\Z)^*$ is cyclic when $p$ is odd, for
      every $k$ and that its order is always even, while $(\Z/2^k\Z)^*$ for $k\geq 3$ is the product of
      two cyclic groups of order respectively $2$ and $2^{k-2}$.\\
      %
      {\bf Remark:} Using the full strength of Dirichlet's bound (i.e. $\sum_{n\leq y}d(n) = y\log y +
      (2\gamma-1)y + O(\sqrt{y})$), the previous argument gives
                \[
                 \sum_{n\leq x} f(n)
                   = H(1) x\log x
                     +((2\gamma-1)H(1) + H'(1))x
                     + O_\eta(x^{1/2+\eta}).
                \]
      \bigskip

\item Let $\alpha\in(0,1)$ and $q$ be any positive integer. Prove that
      \[
      \sum_{p|q} (\log p)^\alpha
      \leq (\omega(q))^{1-\alpha} (\log q)^\alpha,
      \]
      where $p$ always denotes a prime number.\\
      %
      Let $p_j$ be the sequence of primes and let $q_n:=\prod_{j\leq n}p_j$. Prove that
      \[
      \sum_{p|q_n} (\log p)^\alpha
      \sim n(\log n)^\alpha
      \qquad n\to\infty,
      \]
      and that (by PNT)
      \[
      \omega(q_n)^{1-\alpha}(\log q_n)^{\alpha}
      \sim n(\log n)^{\alpha}
      \qquad n\to\infty,
      \]
      so that the inequality is essentially optimal.\\
      %
      {\bf Hint:} For the first part recall H\"{o}lder's inequality:
      \[
      \sum_{n\in\mathcal{I}} |a_nb_n|\leq (\sum_{n\in\mathcal{I}} |a_n|^r)^{1/r} (\sum_{n\in\mathcal{I}} |b_n|^s)^{1/s}
      \]
      for every set of indexes $\mathcal{I}$ and whenever $r,s>0$, $1/r+1/s=1$. The conclusion follows
      with a suitable choice of $r$ and $s$ in terms of $\alpha$.
\end{enumerate}
\end{document}
