%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                                                                        %
%                     Homework 2:                                        %
%                     Analytic Number Theory                             %
%                                                       GM   10/05/2017  %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

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

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

\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{\F}{\field{F}}
\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}{.7cm}
\setlength{\itemsep}{.3cm}
}
}{\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 2%\\[.3cm]
%    \large{sheet 1}
    }
\end{center}
\vspace{.5cm}

%\bigskip
\begin{enumerate}
\item Let $p$ be a prime, and $\F_p$ be the finite field with $p$ elements. Let $N(n)$ be the number
      of \emph{monic} and \emph{irreducible} polynomials in $\F_p[x]$ with degree $n$. The following
      steps will prove that $N(n)\geq 1$ for every $n$, i.e. that for every $n$ there is at least one
      polynomial which is irreducible, monic and which has degree $n$ (standard tools in commutative
      algebra show that the existence of such a polynomial implies the existence of at least one finite
      field $\mathbb{K}_{n}$ with $[\mathbb{K}_{n}:\F_p]=n$).
      \begin{Lista}
       \item[a)] Let $\F_p[x]^*$ denote the set of monic polynomials in $\F_p[x]$. Prove that
             \[
              \sum_{f\in \F_p[x]^*}T^{\deg(f)} = \prod_{\substack{g\in \F_p[x]^*\\g\ \text{irred.}}}(1-T^{\deg(g)})^{-1}
             \]
             as formal identity between power series in the $T$ variable (if you prefer, you can prove
             that both LHS and RHS converge absolutely for $|T|<1/p$, so that here the equality is an
             identity for analytic functions).
       \item[b)] Prove that
             \[
              \sum_{f\in \F_p[x]^*}T^{\deg(f)} = \sum_{n=0}^{\infty} p^nT^n = (1-pT)^{-1},
             \]
             and that
             \[
              \prod_{\substack{g\in \F_p[x]^*\\g\ \text{irred.}}}(1-T^{\deg(g)})^{-1}
              = \prod_{n=1}^{\infty} (1-T^{n})^{-N(n)}.
             \]
       \item[c)] Use Step b to rephrase the equality in a, apply $\log$ to the resulting identity, and
            compare the power series to deduce that $p^n = \sum_{k|n}kN(k)$.
       \item[d)] Apply the M\"{o}bius inversion formula to deduce that
            \[
             n N(n) = \sum_{k|n}\mu(n/k)p^k.
            \]
       \item[e)] The quantity $N(n)$ is an integer. Thus, to prove $N(n)\geq 1$ it is sufficient to prove that
            $N(n)>0$. By Step c this happens if and only if $\sum_{k|n}\mu(n/k)p^k>0$. Prove that
            \[
             \sum_{k|n}\mu(n/k)p^k \geq p^n - (n-1)p^{n/2}
            \]
            and then that $p^n - (n-1)p^{n/2} > 0$ holds for every $p\geq 2$, $n\geq 1$.
      \end{Lista}
      \noindent%
      {\bf Hint:} For Step a recall that $\F_p[x]$ is a Unique Factorization Domain, i.e. that each monic
      polynomial may be written in a unique way (up to the order) as product of monic and irreducible
      polynomials.
      \bigskip

\item Let $\chi$ be a real character modulo $q$, $\chi\neq \chi_0$. The following steps give an alternative
      proof of the fact that $L(1,\chi)\neq 0$.
      \begin{Lista}
       \item[a)] Let $f(n):= (1\ast \chi)(n) = \sum_{d|n}\chi(d)$. Prove that $f$ is multiplicative,
                 that $f(n)\geq 0$ for every $n$, and that $f(n^2)\geq 1$ for every $n$.
       \item[b)] Let $F(z) := \sum_{n=1}^{\infty} f(n)e^{-n/z}$. Prove that $F$ is well defined for all
                 $z\geq 1$, and that
                 \[
                  F(z) \geq \sum_{n\leq z/2} f(n)e^{-n/z}
                       \gg  \sum_{n\leq z/2} f(n)
                       \gg  \sqrt{z}
                  \qquad \text{as $z\to\infty$.}
                 \]
       \item[c)] Show that
                 \[
                  F(z) = \sum_{n=1}^{+\infty} \sum_{m=1}^{+\infty} \chi(n)e^{-mn/z}
                       = \sum_{n=1}^{+\infty} \frac{\chi(n)}{e^{n/z}-1}
                       = z\sum_{n=1}^{+\infty} \frac{\chi(n)}{n} + \sum_{n=1}^{\infty} \chi(n)\Big[\frac{1}{e^{n/z}-1} - \frac{z}{n}\Big].
                 \]
       \item[d)] Apply the partial summation formula to conclude that
                 \[
                  \Big|\sum_{n=1}^{+\infty} \chi(n)\Big[\frac{1}{e^{n/z}-1} - \frac{z}{n}\Big]\Big|
                   \ll_q \int_1^{+\infty}\Big|\Big(\frac{1}{e^{x/z}-1} - \frac{z}{x}\Big)'\Big|dx
                   \ll_q 1
                  \qquad \text{as $z\to\infty$.}
                 \]
       \item[e)] From Steps b), c) and d) deduce that
                 \[
                  \sqrt{z} \ll F(z) = zL(1,\chi) + O_q(1)
                  \qquad \text{as $z\to\infty$,}
                 \]
                 and conclude that $L(1,\chi)\neq 0$.
      \end{Lista}
      \noindent%
      {\bf Hint:} For Step~d recall that $A(x):=\sum_{n\leq x}\chi(n)$ is a bounded function, and prove
      that $\frac{1}{e^{y}-1} - \frac{1}{y}$ is a negative and increasing function in $y\geq 0$. Thus
      $\int_1^{+\infty}|(\frac{1}{e^{x/z}-1} - \frac{z}{x})'|dx = \int_1^{+\infty}(\frac{1}{e^{x/z}-1}
      - \frac{z}{x})'dx = z - \frac{1}{e^{1/z}-1}$ which stays bounded as $z\to\infty$ (Prove it!).
      \bigskip

\item Let $G$ be a finite group with $n$ elements.
      \begin{Lista}
       \item[a)] Suppose $G$ cyclic, and let $g$ be a generator. Let $\zeta$ be any primitive $n$th
                 root of the unity.
                 For every $j=1,\ldots,n$ let $\chi_j(g) := \zeta^j$ and extend $\chi_j$ multiplicatively
                 to $G$ (i.e. set $\chi_j(g^2):=\chi_j(g)^2$,$\chi_j(g^3):=\chi_j(g)^3$,\ldots). Prove that
                 each $\chi_j$ is a character and that $\{\chi_j\}_{j=1}^{n}$ is the full set of
                 characters.
       \item[b)] Let $G$ be as in Step~a. Show that $\hat{G}$ is cyclic, and that $\chi_j$ is a generator
                 of $\hat{G}$ if and only if $j$ is coprime with $n$.
       \item[c)] Let $G_1,G_2$ be finite abelian group. Prove that $\widehat{G_1\times G_2}$ and $\hat{G_1}
                 \times\hat{G_2}$ are (canonically) isomorphic. Deduce that $\hat{G}$ is (not
                 canonically) isomorphic to $G$, for every finite abelian group $G$.
      \end{Lista}
      \bigskip

\item Let $\chi$ be any Dirichlet character modulo $q$.
      \begin{Lista}
       \item[a)] Assume that $x\to\infty$. Prove that
             \[
        \sum_{k=1}^{q} \frac{\chi(k)}{k + x}
           = \frac{\sum_{k=1}^{q} \chi(k)}{x}
            - \frac{\sum_{k=1}^{q} \chi(k)k}{x^2}
            + \frac{\sum_{k=1}^{q} \chi(k)k^2}{x^3}
            + O\Big(\frac{1}{x^4}\Big).
      \]
       \item[b)] Deduce that $\sum_{n=1}^{+\infty} \chi(n)/n$ converges when $\chi \neq \chi_0$.
      \end{Lista}
      \noindent%
      {\bf Hint:} For Step~b note that $\sum_{n=1}^{N} \frac{\chi(n)}{n} = \sum_{\ell=0}^{\intpart{N/q}}\sum_{k=1}^{q}
      \frac{\chi(k)}{k + q\ell} + o(1)$ for every $N\in\N$.
      \bigskip


\item Let $q$ be an odd prime. Let $G:= (\Z/q\Z)^*$.
      \begin{Lista}
       \item[a)] Prove that every finite group which is contained in the multiplicative group of a field
                 is always cyclic. Deduce that $G$ is cyclic.
       \item[b)] Prove that there are only two real Dirichlet characters modulo $q$, i.e. characters $\chi$
                 such that $\chi^2 = \chi_0$.
       \item[c)] Let $\chi_{_{2,q}}$ be the real character modulo $q$ which is not $\chi_0$: compute the values
                 of $\chi_{_{2,q}}(n)$ for $n=1,\ldots,q$ when $q=3,5,7,11,13,17$.
       \item[d)] Using the results in Step~c show that
                 \[
                   L(1,\chi_{_{2,q}}) = \sum_{n=1}^{+\infty} \frac{\chi_{_{2,q}}(n)}{n} > 0
                 \]
                 for $q=3,5,7,11,13,17$.
      \end{Lista}
      \noindent%
      {\bf Hint:} For Step~d, use Step~c to deduce that $\sum_{k=1}^{q} \frac{\chi_{_{2,q}}(k)}{k + q\ell}>0$
      for every $\ell\in\N$, then deduce the claim.
      \bigskip


\item Let $q$ be an odd prime. This exercise gives two classical formulas for $L(1,\chi_{_{2,q}})$, which are due
      to Dirichlet.
      \begin{Lista}
       \item[a)] Prove that
                 \[\frac{1}{q}\sum_{\ell=0}^{q-1} e^{\frac{2\pi i k}{q}\ell} =
                   \begin{cases}
                    1 & \text{when $k = 0\pmod{q}$}\\
                    0 & \text{otherwise}
                   \end{cases}
                 \]
                 This identity is a special case of the orthogonal relation for the characters of the group $\Z/q\Z$,
                 but a direct proof is probably easier.
       \item[b)] Let $z\in \C$, with $|z|=1$ and $z\neq 1$. Prove that
                  \[
                    \lim_{N\to\infty} \sum_{n=1}^{N} \frac{z^n}{n} = -\log(1-z)
                  \]
                  where $\log$ is the holomorphic extension to $\C\backslash\{(-\infty,0]\}$ of the real logarithm.\\
                  (If you are not familiar with complex analysis, note that actually we will need this equality only
                  for the case where $z$ is a $q$th roots of $1$, and that in this case the conclusion follows from
                  an application of the summation by parts formula).

       \item[c)] Let $\chi_{_{2,q}}$ be the real and non trivial character modulo $q$.
                 Note that
                 \begin{align*}
                  L(1,\chi_{_{2,q}})
                   &= \lim_{N\to\infty} \sum_{n=1}^{N} \frac{\chi_{_{2,q}}(n)}{n}
                    = \lim_{N\to\infty} \sum_{a=1}^q \chi_{_{2,q}}(a)\sum_{\substack{n=1\\ n=a\,(q)}}^{N} \frac{1}{n}\\
                   &= \frac{1}{q}\lim_{N\to\infty} \sum_{\ell=0}^{q-1}
                                                   \sum_{a=1}^q \chi_{_{2,q}}(a)
                                                   \sum_{n=1}^{N} \frac{e^{\frac{2\pi i(n-a)}{q}\ell}}{n}.
                 \end{align*}
       \item[d)] Prove that the term with $\ell=0$ does not contribute in the previous sum (here the condition
                 $\chi_{_{2,q}}\neq \chi_0$ is used). Deduce that
                 \begin{align*}
                  L(1,\chi_{_{2,q}})
                   &= \frac{-1}{q}\sum_{\ell=1}^{q-1}\sum_{a=1}^q \chi_{_{2,q}}(a)e^{\frac{-2\pi ia}{q}\ell}
                                 \log(1- e^{\frac{2\pi i}{q}\ell}).
                 \end{align*}
       \item[e)] Let $\tau_q := \sum_{a=1}^q \chi_{_{2,q}}(a)e^{\frac{2\pi ia}{q}}$. Then, for every $\ell$ which is
                 coprime to $q$, prove that
                 \[
                   \sum_{a=1}^q \chi_{_{2,q}}(a)e^{\frac{-2\pi ia}{q}\ell} = \chi_{_{2,q}}(-\ell)\tau_q.
                 \]
                 Thus,
                 \begin{align*}
                  L(1,\chi_{_{2,q}})
                   &= \frac{-\tau_q}{q}\sum_{\ell=1}^{q-1}\chi_{_{2,q}}(-\ell)
                                 \log(1- e^{\frac{2\pi i}{q}\ell}).
                 \end{align*}
                 This is already a formula giving $L(1,\chi_{_{2,q}})$ as a finite sum of explicitly computable
                 numbers, but it can be further simplified.
       \item[f)] Using the standard properties of the logarithm, deduce that
                 \begin{align*}
                  L(1,\chi_{_{2,q}})
                   &= \frac{-\tau_q}{q}\sum_{\ell=1}^{q-1}\chi_{_{2,q}}(-\ell)
                                 \Big[\log\Big(\sin\Big(\frac{\pi\ell}{q}\Big)\Big) + \log(-2ie^{\frac{\pi i}{q}\ell})\Big]
                 \end{align*}

       \item[g)] Use the identity $\sum_{\ell=1}^{q-1}\chi_{_{2,q}}(-\ell) = 0$ to deduce that
                 \begin{align*}
                  L(1,\chi_{_{2,q}})
                   &= \frac{-\tau_q}{q}\sum_{\ell=1}^{q-1}\chi_{_{2,q}}(-\ell)
                                 \Big[\log\Big(\sin\Big(\frac{\pi\ell}{q}\Big)\Big) + \frac{\pi i}{q}\ell \Big].
                 \end{align*}
       \item[h)] Suppose that $\chi_{_{2,q}}$ is an even character, i.e. that $\chi_{_{2,q}}(-1) = 1$: prove that
                 \[
                   \sum_{\ell=1}^{q-1}\chi_{_{2,q}}(-\ell)\ell = 0
                 \]
                 so that in this case
                 \begin{align*}
                  L(1,\chi_{_{2,q}})
                   &= \frac{-\tau_q}{q}\sum_{\ell=1}^{q-1}\chi_{_{2,q}}(\ell)\log\Big(\sin\Big(\frac{\pi\ell}{q}\Big)\Big).
                 \end{align*}
       \item[i)] Suppose that $\chi_{_{2,q}}$ is an odd character, i.e. that $\chi_{_{2,q}}(-1) = -1$: prove that
                 \[
                   \sum_{\ell=1}^{q-1}\chi_{_{2,q}}(-\ell)\log\Big(\sin\Big(\frac{\pi\ell}{q}\Big)\Big) = 0
                 \]
                 so that in this case
                 \begin{align*}
                  L(1,\chi_{_{2,q}})
                   &= \frac{i\pi \tau_q}{q^2}\sum_{\ell=1}^{q-1}\chi_{_{2,q}}(\ell) \ell.
                 \end{align*}
       \item[j)] Test the formulas with $q=5$ and $q=7$.\\
                 (The value of $L(1,\chi_{_{2,q}})$ approximated within two decimal digits may be computed following
                 Step~d, and using a software package for the computations).
      \end{Lista}
      \bigskip

\item Let $q$ be an odd prime. Prove that $\chi_{_{2,q}}$ is even when $q=1\pmod{4}$ and is odd when $q=3\pmod{4}$.
      \bigskip

\item Let $q$ be an odd prime. Let $\tau_q$ as in the previous exercise; it is called the \emph{Gauss quadratic
      sum} for the prime $q$. Prove that $|\tau_q| = \sqrt{q}$.\\
      {\bf Remark:} This is a standard but not elementary computation. You can find it in every text on
      number theory. A more complicated result states that $\tau_q = \sqrt{q}$ when $\chi_{_{2,q}}$ is
      even, and $\tau_q = i\sqrt{q}$ when $\chi_{_{2,q}}$ is odd, but needs deeper tools. (A proof of
      Dirichlet based on Poisson formula is in Davenport \emph{Multiplicative number theory} GTM 74,
      Springer 2000 pp. 12--16. The original Gauss' argument is reproduced in Berndt Evans and Williams
      \emph{Gauss and Jacobi sums}, John Wiley \& Sons Inc. 1998 pp.~18--24, and a different proof of
      Schur based on the matrix theory is reproduced in the same book in exercises 26--29 pp. 47--48).
      \bigskip

\item Let $q$ be a prime. Let $S_q := \sum_{\ell=1}^{q-1}\chi_{_{2,q}}(\ell) \ell$. Note that $S_q$ is an integer.
      Prove that $S_q$ is always divisible by $q$ when $q>3$.%\\
%      {\bf Hint:} let $g$ be a generator for $(\Z/q\Z)^*$, then $S_q = \sum_{j=0}^{q-2}(-g)^j\pmod{q}$ (why?), thus
%      $(1+g) S_q = 1 - g^{q-1}$ which is divisible by $q$ (why?). Then conclude, because $g\neq -1\pmod{q}$ for $q>3$.
      \bigskip

\item Let $q$ be an odd prime. We know that $L(1,\chi_{_{2,q}})\neq 0$; deduce that $L(1,\chi_{_{2,q}})>0$.
      Collecting the previous exercises conclude that
      \begin{align*}
       L(1,\chi_{_{2,q}})
       &\geq  \frac{\pi}{\sqrt{q}}
      \end{align*}
      when $\chi_{_{2,q}}(-1) = -1$ and $q>3$.\\
      %
      {\bf Remark:} This bound is called the \emph{trivial lower bound} for $L(1,\chi_{_{2,q}})$, but
      actually it is not trivial at all. Any similar lower bound in terms of $q$ for the case of an even
      real character would be rich of important consequences, but its search has been essentially
      fruitless up to now.
      \bigskip

\item Let $q>3$ be a prime which is congruent to $3$ modulo $4$. Let $S_q=\sum_{\ell=1}^{q-1}\chi_{_{2,q}}(\ell)\ell$.
      Compute $S_q$ for $q=7,11,19,23,31$. Computations show that $S_q <0$; collecting the results in the
      previous exercises (and the remark in Ex.~8), prove that this is true in general.\\
      %
      {\bf Remark:} The celebrated Dirichlet's class number formula says that $-S_q/q$ is the class
      number of the quadratic field $\Q[\sqrt{-q}]$ for every prime $q=3\pmod{4}$, $q>3$.
      \bigskip

\item Let $a_n$ be any real sequence. Let $A_1(x):=\sum_{n\leq x} a_n$ (with $A_1(x)=0$ for $x<1$).
      \begin{Lista}
      \item[a)] Using the partial summation formula prove that
                \[
                 \sum_{n=1}^{L} \frac{a_n}{n^s} = \frac{A_1(L)}{L^s} - \sum_{n=1}^{L-1} A_1(n)\Big(\frac{1}{(n+1)^s}-\frac{1}{n^s}\Big)
                \]
                for every integer $L$.
      \item[b)] Set $A_2(x):=\sum_{n\leq x}A_1(x)$. Iterating the previous formula prove that
                \[
                 \sum_{n=1}^{L} \frac{a_n}{n^s}
                  = \frac{A_1(L)}{L^s} - A_2(L-1)\Big(\frac{1}{L^s}-\frac{1}{(L-1)^s}\Big)
                   + \sum_{n=1}^{L-2} A_2(n)\Big(\frac{1}{(n+2)^s}-\frac{2}{(n+1)^s}+\frac{1}{n^s}\Big)
                \]
      \item[c)] Suppose $A_1(x)$ bounded. From the previous formulas deduce that
                \begin{align*}
                 \sum_{n=1}^{\infty} \frac{a_n}{n^s} &= s\int_1^{+\infty}\frac{A_1(x)}{x^{s+1}}dx
                 \qquad \forall s\in\C,\ \Re s>0; \\
%
                 \sum_{n=1}^{\infty} \frac{a_n}{n^s} &= s(s+1)\int_{1}^{+\infty}\int_x^{x+1}\frac{A_2(x)}{u^{s+2}}du\,dx
                 \qquad \forall s\in\C,\ \Re s>0.
                \end{align*}
      \item[d)] Let $q$ be an odd prime and $\chi_{2,q}$ be the nontrivial quadratic character modulo $q$.
                For each $q\leq 41$ prove that $L(s,\chi_{2,q})>0$ when $s\in\R$, $s>0$.
      \end{Lista}
      %
      {\bf Hint:} For Step d apply formulas in Step c with $a_n=\chi_{2,q}(n)$ and show that for all $q$
      in the list the sequence $A_1(n)$ (or at least the sequence $A_2(n)$) is non negative.\\
      {\bf Remark:} Chowla conjectured that $L(s,\chi_{2,q})>0$ in $(0,+\infty)$ for every $q$ (so that,
      in particular, $L(1/2,\chi_{2,q})>0$). If proved, this conjecture would have extraordinary
      consequences (for example it rules out the Siegel zero). The approach illustrated in the exercise
      can be generalized introducing sequences $A_3(x):=\sum_{n\leq x}A_2(n)$, $A_4(x):=\sum_{n\leq
      x}A_3(n)$ and so on, but it is not at all evident that for every given $q$ there is some index $k$
      for which $A_k$ is nonnegative. The conjecture is wildly open.
\end{enumerate}
\end{document}
