Chebotarev Sets
Hershy Kisilevsky
\ Michael O. Rubinstein \footnote{Support for work on this paper was provided by the National Science Foundation under awards DMS-0757627 (FRG grant), and NSERC Discovery Grants}
We consider the problem of determining whether a set of primes, or, more generally, prime ideals in a number field, can be realized as a finite union of residue classes, or of Frobenius conjugacy classes. We give criteria for a set to be realized in this manner, and show that the subset of primes consisting of every other prime cannot be expressed in this way, even if we allow a finite number of exceptions.
1112.4945.tex
\documentclass[12pt]{article}
\usepackage{amsmath,amssymb,amstext}

%\textheight=8in
%\topmargin=-1in

\renewcommand{\theequation}{\thesection.\arabic{equation}}

%\newcounter{\theequation}

\newcommand{\eps}{\varepsilon}
\newcommand{\Li}{\mbox{Li}}

\newtheorem{definition}{Definition}
\newtheorem{theorem}{Theorem}
\newtheorem{proposition}{Proposition}
\newtheorem{cor}{Corollary}
\newtheorem{lemma}{Lemma}[section]

\newcommand{\C}{\mathbb{C}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\p}{\mathfrak {p}}
\newcommand{\Pri}{\mathfrak {P}}
\newcommand{\Fr}{\operatorname{Frob}}
\newcommand{\Gal}{\operatorname{Gal}}



\begin{document}
\title{\bf Chebotarev Sets}
\author{Hershy Kisilevsky,\ Michael O. Rubinstein
\footnote{Support for work on this paper was provided by the
National Science Foundation under awards DMS-0757627 (FRG grant),
and NSERC Discovery Grants}}


%\date{November 2011}
\maketitle

\abstract{We consider the problem of determining whether a set of primes, or,
more generally, prime ideals in a number field, can be realized as a finite
union of residue classes, or of Frobenius conjugacy classes. We give
criteria for a set to be realized in this manner, and show that the subset of
primes consisting of every other prime cannot be expressed in this way, even
if we allow a finite number of exceptions.}

\baselineskip=18pt
\parskip=13pt

%\setcounter{equation}{0}
\setcounter{page}{1}


\section{Introduction}

In this paper, we consider the following problem, and its generalizations:

Let $p_n$ denote the $n$-th prime, $\pi$ the set of all primes, and
$P_{\text{odd}}$ the set consisting of every other prime:
\begin{equation}
    \label{eq:P}
    P_{\text{odd}} = \{p_n \in \pi | n \text{ odd}\}
    =\{2,5,11,17,23,\ldots\}.
\end{equation}

Can the set $P_{\text{odd}}$ be realized as a finite union of primes in residue
classes, even if we are willing to allow a finite number of exceptions,
either in excess or deficiency?

More
generally, what about other sets of primes with rational density relative to
the full set of primes? Is there an easy way to tell whether such a union is
possible or not?

And what if, rather than just using, as our building blocks, primes in residue
classes, we are permitted to take subsets of prime ideals that arise in the
Chebotarev density theorem, i.e. of Frobenius conjugacy classes in the
Galois groups of finite Galois extensions of $\Q$.

The natural instinct is that the set $P_{\text{odd}}$ above cannot be realized
in this manner. In fact, the number of subsets of primes with density $1/2$ is
uncountable, for example we can pick subsets by performing a random coinflip at
each prime, yet the number of residue classes (or, more generally, Frobenius
conjugacy classes) is countable. Therefore, most subsets of primes will
fail to arise from residue or conjugacy classes.

However, how can one prove for a specific subset, such as $P_{\text{odd}}$, that it cannot
be realized as a finite union of primes in residue/conjugacy classes,
even if we are willing to allow a finite number of exceptions.

We will show, by contradiction, that the set $P_{\text{odd}}$ is too `quiet' relative to the
set of all primes to arise on its own from genuine arithmetic sets. Primes in
progressions, or in Frobenius conjugacy classes are very noisy and irregular,
as a result of the non-trivial zeros of the $L$-functions that govern them.

More generally, one can ask similar question about subsets of prime ideals in
an algebraic number field with rational density. This leads to our notion of
Chebotarev sets.

\subsection{Chebotarev Sets}
\label{sec:Chebotarev intro}


Let $K$ be a global field, and let $\pi(K)$ denote the set of all non-zero prime
ideals of $K$. Let $L/K$ be a finite Galois extension of global fields with
Galois group $\Gal(L/K)=G$. If $C \subset G$ is a conjugacy class in $G$, let
$P_{L/K,C}$ denote the set of primes $\p \in \pi(K)$ such that $\p$ is unramified
in $L/K$ and such that the conjugacy class $(L/K,\p)$ of Frobenius automorphisms
of primes $\Pri \in \pi(L), \Pri \mid \p$ is equal to $C$.

For two sets $S_1,S_2$ the symmetric difference $S_1 \bigtriangleup S_2$ is the
set $S_1 \setminus S_2 \cup S_2 \setminus S_1$.
\begin{definition}
    Call a set
    of primes $P \subseteq \pi(K)$ a {\it Chebotarev set\/} for $K$ if there are
    finitely many finite Galois extensions $L_i/K$ and conjugacy classes $C_i
    \subset \Gal(L_i/K)$ such that $P= \cup_i P_{L_i/K,C_i}$ up to finite sets.
    That is  $P \bigtriangleup\cup_i P_{L_i/K,C_i}$ is finite. 
\end{definition}

Suppose that $K \subseteq L' \subseteq L$ is a tower of finite extensions with
$L'/K$ and $L/K$ both Galois. Then a conjugacy class in $\Gal(L'/K)$ can be
lifted to a finite union of conjugacy classes in $\Gal(L/K)$. Hence $P$ is a
Chebotarev set for $K$ if and only if there is a finite Galois extension $L/K$
and a finite number of conjugacy classes $C_i \subset \Gal(L/K)$ such that $P=
\cup_i P_{L/K,C_i}$ up to finite sets.

Given a Chebotarev set $P \subseteq \pi(K)$ it follows from the Chebotarev
density theorem that $P$ has positive rational density, either Dirichlet
density or natural density, or else has finitely many elements. Thus, any
subset of $\pi(K)$ with no density or irrational density cannot be a Chebotarev
set.

Our problem is to produce a set $P \subset \pi(K)$ of rational density which is
provably not a Chebotarev set. To this end, we have the following theorem.

\begin{theorem}
\label{thm:1}
Let $a/b \in \Q$, with $0 < a/b < 1$.
Assume that $P$, a subset of prime ideals in $K$, has rational density $a/b$
in the set of all prime ideals $\pi(K)$, i.e.
\begin{equation}
    \label{eq:P(x) C rational density}
    P(x) \sim \frac{a}{b}\pi(x,K),
\end{equation}
where
$P(x)$ is the function which counts the number of elements in $P$ and $\leq x$:
\begin{equation}
    \label{eq:P(x) C}
    P(x)=\#\{\p \in P | N_{K/\Q}(\p) \leq x\}.
\end{equation}
Assume, further, that $P$ is a Chebotarev set, i.e.
there exists sets $P_{L/K,C_j}$ of Frobenius conjugacy classes
such that the symmetric difference
\begin{equation}
    \label{eq:P C as union}
    P \bigtriangleup \bigcup_{j=1}^r P_{L/K,C_j}
\end{equation}
is finite (i.e. the exceptions).
Then,
\begin{equation}
    \label{eq:P(x) K vs pi(x) K}
    P(x) - \frac{a}{b}\pi(x,K) =
    \Omega\left(\frac{x^{1/2}}{\log{x}}\right).
\end{equation}
with the implied constant in the $\Omega$ depending on $P$.
\end{theorem}

Here, we are using the following definition of the $\Omega$ notation.
We say that $$f(x) = \Omega(g(x))$$ if $$\lim\sup|f(x)|/g(x) >0,$$ i.e. if
there exists a sequence ${x_n}$ with $x_n\to\infty$, and a constant $c>0$ such that
$|f(x_n)| > c g(x_n)$.

As we will explain in the proof of this theorem, the same result continues to
hold if we replace the counting function $\frac{a}{b} \pi(x,K)$ with
$\frac{a}{b} \pi(x,F)$, where $F$ is {\em any} algebraic number field, i.e. $F$
can be different than $K$. We can also replace it with $\frac{a}{b} \Li(x)$, or
with the counting function $Q(x)$ of another Chebotarev set $Q$, so long as $Q$
has the same density, $a/b$, as $P$ and is essentially distinct from $P$. By
essentially distinct, we mean that the symmetric difference $P \bigtriangleup
Q$ is infinite.

\begin{theorem}
\label{thm:1b}
Let $P$ and $a/b$ be as in the previous theorem, and
$f(x)$ stand for any of $\frac{a}{b} \Li(x)$, $\frac{a}{b} \pi(x,F)$,
or $Q(x)$, as defined above.
Then
\begin{equation}
    \label{eq:P(x) K vs pi(x) F}
    P(x) - f(x) =
    \Omega\left(\frac{x^{1/2}}{\log{x}}\right),
\end{equation}
with the implied constant depending on $P$ and $f$.
\end{theorem}

A slightly more general form of our theorem allows one to consider a summatory
function on prime ideals of $K$ with complex valued weight function that is
constant on Frobenius conjugacy classes of $G$:
\begin{theorem}
\label{thm:1c}
Define
\begin{equation}
    \label{eq:F}
    F(x) := \sum \pi(x,L/K,C_j) \lambda_j,
\end{equation}
where $\lambda_j \in \C$, and is assumed to satisfy $\sum |\lambda_j| \neq 0$.
The sum is over the distinct conjugacy classes $C_j$ of $G=\Gal(L/K)$, and
$\pi(x,L/K,C_j)$ is defined in~\eqref{eq:pi C}.
Let
\begin{equation}
    \label{eq:lambda}
    \lambda := \frac{1}{|G|}\sum \lambda_j |C_j|.
\end{equation}
Then
\begin{equation}
    \label{eq:F(x) vs Li}
    F(x) - \lambda Li(x) =
    \Omega\left(\frac{x^{1/2}}{\log{x}}\right),
\end{equation}
with the implied constant depending on $F$, and $\lambda_j$.
\end{theorem}
For example, we can recover Theorem~\ref{thm:1} by taking $\lambda_j = 1-a/b$
for $1\leq j \leq r$, and $-a/b$ otherwise. Observe, in this example, that $\lambda =
0$, so that no $Li(x)$ term appears.

The key idea used to prove these theorems is that the functions on the lhs
of~\eqref{eq:P(x) K vs pi(x) K} \eqref{eq:P(x) K vs pi(x) F}, and
\eqref{eq:F(x) vs Li} are discontinous on a positive proportion of
$N_{K/\Q}(\p)\leq x$. Consequently, when expressed as a linear combination of
explicit formulas, infinitely many of the non-trivial zeros of the relevant
$L$-functions must survive.
These zeros are responsible for making these differences large on average,
which we show by considering their mean square on a logarithmic scale.

Note that the statements of Theorems~\ref{thm:1}-~\ref{thm:1c} do not assume
the Generalized Riemann Hypothesis. In fact, if the GRH does not hold, a
stronger $\Omega$ result than~\eqref{eq:P(x) K vs pi(x) K} holds, hence we have
stated these theorems unconditional on the GRH.

The precise statement of the $\Omega$ bound in the case that the GRH fails
requires some discussion concerning the location of the zeros of the relevant
$L$-functions, and how these zeros interact upon taking certain linear
combinations of the logarithmic derivatives of these $L$-functions. This
discussion and corresponding result can be found in Section~\ref{sec:theta >
1/2} and in Theorem~\ref{thm:3} at the end of Section~\ref{sec:proofs in
general}.

Therefore, to rule out a set $P$ as being Chebotarev, one need only show that
either Theorem 1 or 2 is violated. So, for example, the set $P_{\text{odd}}$
specified in the introduction of density $1/2$ in the rational primes,
consisting of every other prime, cannot be realized as a Chebotarev set. We can
prove this by considering the counting function $P_{\text{odd}}(x)$, equal to
the number of elements in $P_{\text{odd}}$ and $\leq x$:
\begin{equation}
    \label{eq:P_odd(x)}
    P_{\text{odd}}(x)=\#\{p \in P_{\text{odd}} | p \leq x\}.
\end{equation}
Because $P_{\text{odd}}$ counts every other prime, we have that
\begin{equation}
    \label{eq:P(x) vs pi(x)}
    P_{\text{odd}}(x) -  \pi(x)/2 =
    \begin{cases}
        1/2,\quad \text{if $p_{2j-1}\leq x< p_{2j}$} \\
        0,\quad \text{if $p_{2j}\leq x< p_{2j+1}$},
    \end{cases}
\end{equation}
which violates Theorem 1. Hence $P_{\text{odd}}$ cannot be realized as a Chebotarev set.

\begin{definition}
    Call a set of primes $P \subseteq \pi(K)$ an {\it almost Chebotarev set\/}
    for $K$ if there is a Chebotarev set $U$ such that $P = U$ up to sets
    of density zero. That is  $P \bigtriangleup U$ has density zero.
\end{definition}

It seems much more difficult to produce a set which is provably not almost
Chebotarev -- although we suspect that our example, $P_{\text{odd}}$, is one such set.

We conclude the introduction by noting that Serre studied `Frobenian' (i.e.
named differently than here) sets and functions in his paper~\cite{S} and
book~\cite{S2} (see his Chapter 3), the latter in relation to the problem of counting the number of
solutions mod $p$ to a system of polynomial equations. Lagarias defined a
similar notion of Chebotarev sets in~\cite{L}, also for studying solutions to
polynomial congruences modulo $p$. See Lemma 3.1 in his paper for the
equivalence of his definition to ours, though without allowing for finitely
many exceptions.


\section{The classical case}
\label{sec:classical}

In this section we consider the more classical situation of sets $P$ of
rational primes that are realized using residue classes. We will essentially
establish Theorem~\ref{thm:1} for the special case of residue classes, rather
than Frobenius conjugacy classes.

The techniques that we develop will serve as a model, in Section~\ref{sec:chebotarev},
where we will modify our approach to the general setting of Chebotarev sets.

Assume that
\begin{equation}
    \label{eq:P as union}
    P = P_0 \cup \bigcup_{j=1}^r P_{a_j,q_j} \setminus P_1
\end{equation}
where $P_0,P_1$ consists of finitely many elements, i.e. the possible exceptions in excess and deficiency,
and
\begin{equation}
    \label{eq:P a,q}
    P_{a,q} = \{p \in \pi | p = a \mod q\}
\end{equation}
consists of primes in the residue class $a$ mod $q$.

We can simplify a bit and assume that all the $q_j$ are equal, since, if not,
we could simply rewrite~\eqref{eq:P as union} in terms of the least common
multiple of the $q_j$ and take additional residue classes as needed. For
example, the set of primes that are $1 \mod 4$ union the primes that are $5
\mod 6$ is equivalent to the set of primes that are $1,5,11\mod 12$.

Thus we are assuming the existence of a single positive integer $q$,
and distinct residue classes $a_j$ mod $q$ such that, after relabelling $r$
as needed,
\begin{equation}
    \label{eq:P as union b}
    P = P_0 \cup \bigcup_{j=1}^r P_{a_j,q} \setminus P_1.
\end{equation}
We can also assume that $\gcd(a_j,q)=1$.

We consider the
counting function $P(x)$ which is equal to the number of elements
in $P$ and $\leq x$:
\begin{equation}
    \label{eq:P(x)}
    P(x)=\#\{p \in P| p \leq x\}.
\end{equation}

Next, we define, as usual,
\begin{equation}
    \pi(x,q,a) = \# \{p \leq x \mid p = a \bmod q\}.
\end{equation}
From equation~\eqref{eq:P as union b}, we
have, for $x$ larger than all of the elements of $P_0$ and $P_1$, that
\begin{equation}
    \label{eq:P from pi}
    P = \lambda + \sum_{j=1}^r \pi(x,q,a_j),
\end{equation}
where
\begin{equation}
    \lambda= |P_0| - |P_1|.
\end{equation}

The prime number theorem which states that
\begin{equation}
    \pi(x) \sim \Li(x),
\end{equation}
where
\begin{equation}
    \Li(x) = \int_2^x dt/\log{t}
    \sim \frac{x}{\log{x}}.
\end{equation}
The prime number theorem for arithmetic progressions, proven
by Hadamard and de la Vall\'{e} Poussin,
asserts, for $\gcd(a,q)=1$, that primes are equidistributed amongst
the residue classes mod $q$ that are relatively prime to $q$:
\begin{equation}
    \label{eq:pnt progressions}
    \pi(x,q,a) \sim \frac{\pi(x)}{\phi(q)},
\end{equation}
where $\phi(q)= \#\{ a \bmod q \mid (a,q)=1 \}$.
Therefore,
\begin{equation}
    \label{eq:P vs pi}
    P(x) \sim \frac{r}{\phi(q)} \pi(x).
\end{equation}
We also make the assumption that
\begin{equation}
    \frac{r}{\phi(q)} < 1,
\end{equation}
so that $P$ omits a positive proportion of the primes.


\subsection{Explicit formula}
\label{sec:xxx}

One can write an explicit formula for $\pi(x,q,a)$ in
terms of the zeros of the Dirichlet $L$-functions, $L(s,\chi)$, where
$\chi$ runs over all Dirichlet characters for the modulus $q$.

For a given $q$, let $\chi$ be a Dirichlet character modulo $q$.
We will denote the principal character
by $\chi_{0}$. Let
\begin{equation}
    \psi(x,\chi) := \sum_{n \leq x} \chi(n) \Lambda(n)
\end{equation}
where $\Lambda(n)= \log p$ if $n=p^{m}$ for some $m \in Z$, and is 0
otherwise.

The explicit formula for $\pi(x,q,a)$ can be derived from that of
\begin{eqnarray}
    \psi(x,q,a) & := & \sum_{{n \leq x}\atop{n \equiv a \bmod q}} \Lambda(n) \notag \\
    & = & \frac{1}{\phi(q)}\sum_{\chi \bmod q} \bar{\chi}(a)
    \sum_{n \leq x}\Lambda(n)\chi(n) \notag \\
     & = &
    \frac{1}{\phi(q)} \sum_{\chi \bmod q} \bar{\chi}(a) \psi(x,\chi).
    \label{eq:psi progressions}
\end{eqnarray}
The main contribution to $\psi(x,q,a)$ comes from the principal character:
\begin{equation}
    \label{eq:principal psi}
    \psi(x,\chi_0) = \sum_{p^k \leq x \atop  p \nmid q} \log(p) = \psi(x) - \sum_{p^k \leq x \atop  p | q} \log(p).
\end{equation}
Therefore
\begin{equation}
    \psi(x,q,a)
    = \frac{1}{\phi(q)}
    \left(
        \psi(x)
        + \sum_{\chi \bmod q \atop \chi\neq\chi_0} \bar{\chi}(a) \psi(x,\chi)
        - \sum_{p^k \leq x \atop  p \mid q} \log(p)
    \right).
    \label{eq:psi progressions b}
\end{equation}

We define
\begin{eqnarray}
    \Pi(x,q,a)
    & := & \sum_{{n \leq x}\atop{n \equiv a \bmod q}} \frac{\Lambda(n)}{\log(n)}
    =  \sum_{{p^k \leq x}\atop{p^k \equiv a \bmod q}} \frac{1}{k} \notag \\
    & = & \pi(x,q,a) + R(x,q,a)
\end{eqnarray}
with
\begin{equation}
    \label{eq:remainder}
    R(x,q,a) =
    \sum_{{p^k \leq x\atop k\geq 2}\atop{p^k \equiv a \bmod q}} \frac{1}{k}.
\end{equation}
Therefore,
\begin{equation}
    \label{eq:pi progressions in terms of Pi}
    \pi(x,q,a) = \Pi(x,q,a) - R(x,q,a).
\end{equation}
Now, summing by parts
\begin{equation}
    \Pi(x,q,a) = \frac{\psi(x,q,a)}{\log(x)} + \int_2^x \frac{\psi(t,q,a)}{t \log(t)^2} dt,
\end{equation}
so that
\begin{equation}
    \label{eq:pi progressions in terms of Pi b}
    \pi(x,q,a) =
     \frac{\psi(x,q,a)}{\log(x)} + \int_2^x \frac{\psi(t,q,a)}{t \log(t)^2} dt
    -R(x,q,a).
\end{equation}
Subsitituting~\eqref{eq:psi progressions} into the above,
we get
\begin{eqnarray}
    \label{eq:pi progressions in terms of Pi c}
    &&\pi(x,q,a) = \notag \\
    &&\frac{1}{\phi(q)}
    \left(
        \frac{\psi(x)}{\log(x)} +
        \int_2^x \frac{\psi(t)}{t \log(t)^2} dt
        - \frac{\sum_{p^k \leq x \atop  p \mid q} \log(p)}{\log(x)}
        -\int_2^x \frac{ \sum_{p^k \leq t \atop  p \mid q} \log(p) }{t \log(t)^2} dt
    \right) \notag \\
    &+&
    \frac{1}{\phi(q)}
    \sum_{\chi \bmod q \atop \chi\neq\chi_0} \bar{\chi}(a)
    \left(
        \frac{\psi(x,\chi)}{\log(x)}
        +\int_2^x \frac{\psi(t,\chi)}{t \log(t)^2} dt
    \right)
     -R(x,q,a). \notag \\
\end{eqnarray}
The special case of $q=1$ (and any value for $a$) of~\eqref{eq:pi progressions in terms of Pi b} is:
\begin{eqnarray}
    \label{eq:pi in terms of Pi}
    \pi(x) =
     \frac{\psi(x)}{\log(x)} + \int_2^x \frac{\psi(t)}{t \log(t)^2} dt
     -R(x,1),
\end{eqnarray}
with
\begin{equation}
    \label{eq:R(x,1)}
    R(x,1) =
    \sum_{k\geq 2} \frac{\pi(x^{1/k})}{k}.
\end{equation}

With these formulas in hand, consider again the difference $P(x) - \frac{r}{\phi(q)}\pi(x)$.
Subtracting $\frac{r}{\phi(q)}\pi(x)$ from~\eqref{eq:P from pi}, and
then substituting~\eqref{eq:pi progressions in terms of Pi c} and \eqref{eq:pi in terms of Pi}
gives:
\begin{eqnarray}
    \label{eq:main formula}
    &&P(x) - \frac{r}{\phi(q)}\pi(x) =
    \lambda + \sum_{j=1}^{r} \pi(x,q,a_j) -\frac{r}{\phi(q)}\pi(x) \notag \\
    &=& \lambda +
    \sum_{\chi \bmod q \atop \chi\neq\chi_0} c_\chi
    \left(
        \frac{\psi(x,\chi)}{\log(x)}
        +\int_2^x \frac{\psi(t,\chi)}{t \log(t)^2} dt
    \right)
    +\frac{r R(x,1)}{\phi(q)}
    -\sum_{j=1}^{r}
    R(x,q,a_j) \notag \\
    &-&\frac{r}{\phi(q)}
    \left(
         \frac{\sum_{p^k \leq x \atop  p \mid q} \log(p)}{\log(x)}
        +\int_2^x \frac{ \sum_{p^k \leq t \atop  p \mid q} \log(p) }{t \log(t)^2} dt
    \right),
\end{eqnarray}
where
\begin{equation}
    \label{eq:c_chi}
    c_\chi = \frac{1}{\phi(q)} \sum_{j=1}^{r} \bar{\chi}(a_j).
\end{equation}
Note above, that, on summing over $r$ values of $a_j$ and
subtracting $r/\phi(q)$ times~\eqref{eq:pi in terms of Pi}, we cancelled the main term
\begin{equation}
    \label{eq:terms that cancel}
    \frac{r}{\phi(q)}\left(
        \frac{\psi(x,\chi)}{\log(x)}
        +\int_2^x \frac{\psi(t,\chi)}{t \log(t)^2} dt
    \right).
\end{equation}

We will show that
the rhs of~\eqref{eq:main formula} can get as large, in absolute value, as
$\gg x^{1/2}/\log(x)$. This will be independent of the GRH.
In fact, if GRH fails, the lower bound that we can prove is at least as large.

The classic explicit formula for $\psi(x,\chi)$, where $\chi\neq \chi_0$
is a primitive character, takes the form, for $x>1$ not a prime power,
\begin{equation}
    \label{eq:explicit formula}
    \psi(x,\chi) = - \sum_{\rho_\chi} \frac{x^{\rho_\chi}}{\rho_\chi}
    -(1-\mathfrak{a}_\chi) \log{x} -b(\chi) + \sum_{m=1}^\infty \frac{x^{\mathfrak{a}_\chi-2m}}{2m-\mathfrak{a}_\chi}, %\notag \\
    %&=& - \sum_{\rho} \frac{x^{\rho}}{\rho} + O(\log{x}),
\end{equation}
where $\rho_\chi$ runs over the non-trivial zeros of $L(s,\chi)$, with the sum over
zeros taken as $\lim_X \to \infty |\Im{\rho_\chi}| < X$. Also, $\mathfrak{a}_\chi=1$ if
$\chi(-1)=-1$ and $0$ otherwise, and $b(\chi)$ is a constant depending on
$\chi$, namely the constant term in the Laurent expansion about $s=0$ of
$L'/L(s,\chi))$ (Taylor expansion if $\chi(-1)=-1$). If $x$ is a prime power,
the rhs above converges to $\psi(x,\chi) - \Lambda(x) \chi(x)/2$, i.e. one
needs to subtract half of the last term in the sum defining $\psi(x,\chi)$. For
a derivation of this explicit formula see, for instance, Davenport \cite[pgs
115-120]{Davenport}.

When $\chi$ is an imprimitive character, say induced by $\chi_1$ mod $q_1$,
then
\begin{equation}
    \label{eq:psi imprimitive}
    \psi(x,\chi) = \psi(x,\chi_1) - \sum_{p^k \leq x \atop  p | q} \log(p) \chi_1(p^k).
\end{equation}
For notational convenience, in the case of imprimitive $\chi$, we set
$\mathfrak{a}_\chi = \mathfrak{a}_{\chi_1}$ and also $b(\chi) = b(\chi_1)$.

Therefore, we can rewrite~\eqref{eq:main formula} in the following form:
\begin{eqnarray}
    \label{eq:main formula zeros}
    &&P(x) - \frac{r}{\phi(q)}\pi(x)
    = \frac{1}{\log{x}} \sum_{\rho} \alpha_\rho \frac{x^{\rho}}{\rho}
    + A(x)
    + B(x),
\end{eqnarray}
where $\alpha_\rho \in \C$ and the sum over $\rho$ is taken over the union over
the non-trivial zeros of all $L(s,\chi)$, $\chi$ mod $q$.
We may assume that the the $\rho$ in the sum are distinct, by grouping equal
$\rho$ under the same $\alpha_\rho$.
In the case of
imprimitive characters, the non-trivial zeros of $L(s,\chi)$ coincide with
those of the Dirichlet $L$-function, $L(s,\chi_1)$, corresponding to the
inducing character $\chi_1$.
Also observe that
\begin{equation}
    \label{eq:alpha_rho bound}
    \alpha_\rho = O_q(1)
\end{equation}
as the $\alpha_\rho$'s are obtained by taking the linear combination
$\sum_{\chi\neq \chi_0} c_\chi \psi(x,\chi)$, and then grouping together equal
$\rho$ (if there are any. Distinct $L(s,\chi)$, for primitive $\chi$,
presumably have distinct non-trivial zeros).

The function $A(x)$ gathers together all the
remaining terms that are discontinuous:
\begin{eqnarray}
    \label{eq:A(x)}
    A(x) &=& \frac{r R(x,1)}{\phi(q)}
    -\sum_{j=1}^{r}
    R(x,q,a_j)
    -\frac{r}{\phi(q)} \frac{\sum_{p^k \leq x \atop  p \mid q} \log(p)}{\log(x)} \notag \\
    &-&\frac{1}{\log{x}} \sum_{ {\chi \mod q\atop \chi \neq \chi_0} \atop \chi \text{imprimitive}}
    c_\chi \sum_{p^k \leq x \atop  p | q} \log(p) \chi_1(p^k),
\end{eqnarray}
and $B(x)$ incorporates the rest:
\begin{eqnarray}
    \label{eq:B(x)}
    B(x) &=& \lambda
    -\frac{r}{\phi(q)} \int_2^x \frac{ \sum_{p^k \leq t \atop  p \mid q} \log(p) }{t \log(t)^2} dt
    +
    \sum_{\chi \bmod q \atop \chi\neq\chi_0}
    c_\chi \Big(\int_2^x \frac{\psi(t,\chi)}{t \log(t)^2} dt \notag \\
    &-&
    (1-\mathfrak{a}_\chi) + \frac{b(\chi)}{\log{x}}
    - \frac{1}{\log{x}}\sum_{m=1}^\infty \frac{x^{\mathfrak{a}_\chi-2m}}{2m-\mathfrak{a}_\chi}
    \Big).
\end{eqnarray}

Notice that $A(x)$ has jump discontinuities at a relatively thin set of prime powers:
$R(x,1)$ and $R(x,q,a_j)$ jump when $x$ is a prime power $p^k$ with $k\geq 2$.
The remaining terms in $A(x)$ jump at prime powers $p^k$ with $p|q$, $k \geq
1$. Hence, overall, $A(x)$ has only finitely many jump discontinuities at the
primes, namely the primes $p$ that divide $q$. Furthermore every term that
appears in $B(x)$ is continuous with respect to $x$. But
$P_(x)-\frac{r}{\phi(q)}\pi(x)$ is discontinuous at all primes (our assumption
that $r/\phi(q)<1$ enters here).

Therefore, the sum over $\rho$ in~\eqref{eq:main formula zeros}
must have infinitely many terms with $\alpha_\rho \neq 0$, otherwise the sum
over $\rho$ would be continuous a function for all $x$.

The fact that at least one $\alpha_\rho$ is non-zero
is a crucial point, and we are now in a position to obtain our
$\Omega$ results.

Let $\Theta$ be the lim sup of the real parts of the zeros $\rho$ such that
$\alpha_\rho \neq 0$, i.e. the zeros that appear in~\eqref{eq:main formula zeros}:
\begin{equation}
    \label{eq:Theta}
    \Theta = \lim\sup \{ \Re{\rho} | \alpha_\rho \neq 0\}.
\end{equation}
Equivalently, from~\eqref{eq:main formula},  $\Theta$ is the lim sup of the poles of the function
\begin{equation}
    \label{eq:generating function a}
    -\sum_{\chi\neq \chi_0} c_\chi \frac{L'(s,\chi)}{L(s,\chi)}
    +\frac{r}{\phi(q)}\frac{\zeta'(s)}{\zeta(s)},
\end{equation}
and also of the singularities of
\begin{equation}
    \label{eq:generating function b}
    \sum_{\chi\neq \chi_0} c_\chi \log(L(s,\chi)) -\frac{r}{\phi(q)}\log(\zeta(s)).
\end{equation}
Notice that $\Theta \geq 1/2$, since the zeros of $L(s,\chi)$ that occur off the half line
(assuming GRH fails) come in pairs, $\rho$ and $1-\overline{\rho}$, symmetric about the line $\Re{s}=1/2$.

\subsection{$\Omega$ bound, assuming $\Theta>1/2$}
\label{sec:theta > 1/2}

We first assume that $\Theta>1/2$, i.e. that the GRH fails and that at least one zero
to the right of $\Re(s)=1/2$ survives in the explicit formula on taking the linear combination
in~\eqref{eq:main formula}.

We will prove that, for every $\delta>0$,
\begin{equation}
    \label{eq:lower bound a}
    P(x)- \frac{r}{\phi(q)} \pi(x) = \Omega (x^{\Theta-\delta}),
\end{equation}
with the implied constant depending on $\delta$ and $q$,
by establishing, assuming $\Theta>1/2$, the estimate
\begin{equation}
    \label{eq:lower bound b}
    \sum_{j=1}^r \Pi(x,q,a_j) -\frac{r}{\phi(q)}\Pi(x) = \Omega (x^{\Theta-\delta}).
\end{equation}
The above is easier to work with than~\eqref{eq:lower bound a}, since
$L$-functions naturally count prime powers rather than just primes. Notice
that, because $\Pi(x,q,a)-\pi(x,q,a)=O_q(x^{1/2}/\log(x))$ and $\Pi(x) -
\pi(x)= O(x^{1/2}/\log(x))$ (see~\eqref{eq:R(x,1) estimate}
and~\eqref{eq:R(x,q,a) estimate} below) so that, by choosing
$0<\delta<\Theta-1/2$, we have that~\eqref{eq:lower bound b}
implies~\eqref{eq:lower bound a} (and then for every $\delta>0$, since taking
$\delta$ larger gives a weaker bound).

Argue by contradiction. Assume that~\eqref{eq:lower bound b} does not hold,
i.e. that there exists a $\delta>0$ such that $|\sum_{j=1}^r \Pi(x,q,a_j) -\frac{r}{\phi(q)}\Pi(x)|
\ll x^{\Theta-\delta}$. Consider the Dirichlet integral (akin to Dirichlet
series, see Chapter 5 of~\cite{I}),
\begin{eqnarray}
    \label{eq:Dirichlet integral}
    &&\int_1^\infty \frac{\sum_{j=1}^r \Pi(x,q,a_j) -\frac{r}{\phi(q)}\Pi(x)}{x^{s+1}} dx
    = \frac{1}{s} \sum_{\chi} c_\chi \log(L(s,\chi)) - \frac{r}{s \phi(q)} \log(\zeta(s)) \notag \\
    &=& \frac{1}{s} \sum_{\chi\neq\chi_0} c_\chi \log(L(s,\chi)) + \frac{r}{s \phi(q)} \sum_{p|q} \log(1-p^{-s}).
\end{eqnarray}
One can prove this identity, when $\Re{s}>1$, by observing that the numerator
of the integrand is a step function with steps at prime powers, and then integrating
termwise the contribution from each prime power. The assumption that $\Re{s}>1$ is used
to rearrange integration and summation and also to identify the resulting Dirichlet series
with the rhs above.

Notice that the rhs above has singularities (branch cuts)
coming from the zeros of $L(s,\chi)$, specifically from the $\rho$ with $\alpha_\rho \neq 0$
(and some additional singularities originating on the line $\Re{s}=0$).

Now, if the numerator of the above integrand  is $ \ll x^{\Theta-\delta}$, then
the lhs of~\eqref{eq:Dirichlet integral} defines an analytic function for
$\Re{s}> \Theta-\delta$. But this contradicts, from the definition of $\Theta$, 
the fact that the rhs has singularities in this half plane. Therefore,
\begin{equation}
    \label{eq:omega result Pi}
    \sum_{j=1}^r \Pi(x,q,a_j) -\frac{r}{\phi(q)}\Pi(x) = \Omega(X^{\Theta-\delta}),
\end{equation}
for all $\delta>0$.

\subsection{$\Omega$ estimate in the classical case, assuming $\Theta=1/2$}

In this subsection, we assume
that $\Theta=1/2$. This can occur in two ways: either if the GRH holds, or if
the only zeros surviving the linear combination of explicit formulae arising
from~\eqref{eq:main formula} are on the half line.

The above result can be improved when $\Theta=1/2$. In that case we will show
that
\begin{equation}
    \label{eq:omega bound on theta=1/2}
    P(x)- \frac{r}{\phi(q)} \pi(x) = \Omega(x^{1/2}/\log(x)).
\end{equation}

While we could modify the approach given in the previous subsection, it is complicated by the
presence of the squares of primes. We could adapt the approach described in
Ingham~\cite{I} for the problem of $\psi(x)-x$, and prove that
\begin{equation}
    \label{eq:Theta 1/2 and Ingham}
    \sum_{j=1}^r \Pi(x,q,a_j) -\frac{r}{\phi(q)}\Pi(x) = \Omega_{\pm}(x^{1/2}/\log{x}),
\end{equation}
i.e. that the difference of these {\ prime power} counting functions gets, in
size, as large as a constant times $x^{1/2}/\log{x}$, and points in {\em both}
positive and negative directions for infinite sequences of $x \to \infty$. Now
the squares of primes contribute an amount to $P(x)-\frac{r}{\phi(q)} \pi(x)$
that is asymptotically a constant times $x^{1/2}/\log(x)$, i.e. of the same
size as~\eqref{eq:Theta 1/2 and Ingham} , but always pointing in one direction.
Hence, estimate~\eqref{eq:Theta 1/2 and Ingham} would establish~\eqref{eq:omega
bound on theta=1/2}.

Instead, however, we will take an alternate approach that yields more
information. We will consider two mean square averages of the remainder term,
each giving a separate proof of~\eqref{eq:omega bound on theta=1/2}. Both
averages are of interest in their own right.

We first bound each term that appears in $A(x)$, $B(x)$.
The prime number theorem and~\eqref{eq:R(x,1)} give
\begin{equation}
    \label{eq:R(x,1) estimate}
    R(x,1) =
    \pi(x^{1/2})/2 + O(x^{1/3}/\log{x})
    = x^{1/2}/\log{x} + O(x^{1/2}/\log(x)^2).
\end{equation}
Similarly, from the prime number theorem for arithmetic progressions, we have
\begin{equation}
    \label{eq:R(x,q,a) estimate}
    \sum_{j=1}^{r}
    R(x,q,a_j)
    = \kappa x^{1/2}/\log{x} + O_q(x^{1/2}/\log(x)^2),
\end{equation}
with the implied constant in the $O$ depending on $q$, and
\begin{equation}
    \label{eq:kappa}
    \kappa =
    \frac{1}{\phi(q)} \sum_{j=1}^{r}
    \sum_{b^2 = a_j \mod q} 1.
\end{equation}
Finally, there are only finitely many $p|q$. Furthermore, $p^k \leq x$ implies
that $k \leq \log(x)/\log(p)$.
Hence $\sum_{p^k \leq x \atop  p \mid q} \log(p) = O_q(\log{x})$, and so
\begin{equation}
    \label{eq:A(x) finite p}
    -\frac{1}{2} \frac{\sum_{p^k \leq x \atop  p \mid q} \log(p)}{\log(x)}
    -\frac{1}{\log{x}} \sum_{ {\chi \mod q\atop \chi \neq \chi_0} \atop \chi \text{imprimitive}}
    c_\chi \sum_{p^k \leq x \atop  p | q} \log(p) \chi_1(p^k) =
    O_q(1).
\end{equation}
Putting these together gives
\begin{equation}
    \label{eq:A(x) estimate}
    A(X) = (r/\phi(q)-\kappa) x^{1/2}/\log{x} + O_q(x^{1/2}/\log(x)^2).
\end{equation}

To estimate $B(x)$, notice that
\begin{equation}
    \label{eq:B(x) estimate 1}
    \int_2^x \frac{ \sum_{p^k \leq t \atop  p \mid q} \log(p) }{t \log(t)^2} dt
    \ll_q
    \int_2^x \frac{dt}{t \log(t)} \ll \log\log{x}.
\end{equation}
Thus, because $\lambda$ and second line of~\eqref{eq:B(x)} are bounded, we have
\begin{eqnarray}
    \label{eq:B(x) estimate 2}
    B(x) \ll_q
    \left|
        \sum_{\chi \neq \chi_{0}} c_\chi
         \int_{2}^{x} \frac{\psi(t,\chi)}{t \log(t)^2} dt
    \right|
    + \log\log{x}.
\end{eqnarray}
Let
\begin{equation}
    G(x,\chi)= \int_{2}^{x} \psi(t,\chi) dt/t.
\end{equation}
Equation (5), page 117,
of Davenport~\cite{Davenport} gives the explicit formula with a rate of
convergence:
\begin{eqnarray}
    \label{eq:explicit formula b}
    \psi(x,\chi) &=& - \sum_{|\Im{\rho_\chi}|<X} \frac{x^{\rho_\chi}}{\rho_\chi}
    %-(1-\mathfrak{a}_\chi) \log{x} -b(\chi) + \sum_{m=1}^\infty \frac{x^{\mathfrak{a}_\chi-2m}}{2m-\mathfrak{a}_\chi} \notag \\
    + O_q(x\log(xX)^2/X + \log{x}),
\end{eqnarray}
valid for $x \geq 2$ (or else for $x>1$ by adding a $1$ to the $O$-term).
Note that this formula, with the $O(\log{x})$ included, is true for both
primitive and imprimitive characters, and whether $x$ is equal to a prime power
or not. We have also absorbed the last three terms of~\eqref{eq:explicit
formula} into the $O$ term above. Thus, integrating and letting $X \rightarrow
\infty$, we have
\begin{equation}
    \label{eq:G}
    G(x,\chi)=- \sum_{\rho_{\chi}}
    \frac{x^{\rho_\chi}}{\rho_\chi^2}
    +O_q(\log(x)^2).
\end{equation}
The above series over $\rho_{\chi}$ converges absolutely
as can be seen from the asymptotic formula for
the number of zeros \cite[pg 101]{Davenport},
\begin{equation}
    \label{eq:N(T)}
    N(T,\chi) := \# \{ |\Im{\rho_{\chi}}| \leq T \} 
    = \frac{T}{\pi}\log\frac{qT}{2\pi} - \frac{T}{\pi} + O(\log T + \log q).
\end{equation}
Summing over $\chi$ we get
\begin{equation}
    \label{eq:G all chi}
    \sum_{\chi \neq \chi_{0}} c_\chi
    \int_{2}^{x} \frac{\psi(t,\chi)}{t} dt
    =- \sum_{\rho}
    \alpha_\rho \frac{x^{\rho}}{\rho^2}
    +O_q(\log(x)^2),
\end{equation}
with the sum over all non-trivial zeros $\rho$ of all $L(s,\chi)$ for the modulus q.
The same coefficients $\alpha_\rho$ appear here as in~\eqref{eq:main formula zeros}
because the same linear combination of the terms involving the zeros $\rho$
appears as in the sum $\sum_{\chi \neq \chi_{0}} c_\chi \psi(x,\chi)$.

It follows, on integrating by parts, that
\begin{equation}
    \label{eq:bound on integral of psi}
    \sum_{\chi \neq \chi_{0}} c_\chi
    \int_{2}^{x} \frac{\psi(t,\chi)}{t \log(t)^2} dt
    \ll_q \frac{x^{1/2}}{\log(x)^2} \sum_{\rho}
    \frac{|\alpha_\rho|}{|\rho|^2} \ll_q \frac{x^{1/2}}{\log(x)^2}.
\end{equation}

Thus, returning to~\eqref{eq:B(x) estimate 2}, we get
\begin{equation}
    \label{eq:B(x) estimate 3}
    B(x)
    \ll_q \frac{x^{1/2}}{\log(x)^2}.
\end{equation}

Thus, our estimates~\eqref{eq:A(x) estimate} and~\eqref{eq:B(x) estimate 3} for $A(x)$ and $B(x)$ give
\begin{equation}
    \label{eq:main estimate on GRH}
    P(x) - \frac{r}{\phi(q)} \pi(x)
    = \frac{1}{\log{x}}
    \left( \sum_{\rho} \alpha_\rho \frac{x^{\rho}}{\rho}
    + (r/\phi(q)-\kappa)x^{1/2} +O\left(x^{1/2}/\log{x}\right)\right),
\end{equation}
By~\eqref{eq:explicit formula b}, for $2 \leq x<X$,
we can write this as a finite sum over $\rho$:
\begin{equation}
    \label{eq:main estimate on GRH, finite sum}
    P(x) -\frac{r}{\phi(q)} \pi(x)
    = \frac{x^{1/2}}{\log{x}}
    \left( \sum_{|\gamma|< X} \alpha_\rho \frac{x^{i\gamma}}{\rho}
    + (r/\phi(q)-\kappa) +O\left(\frac{x^{1/2}\log(X)^2}{X}+\frac{1}{\log{x}}\right)\right),
\end{equation}
where $\rho = 1/2+i\gamma$.
The assumption $x<X$ is simply used here to simplify, in~\eqref{eq:explicit formula b},
$\log(xX)$ by $\log{X}$. We also use it below when estimating the contribution from the
above $O$ term.

Finally, we need to deal with the possibility of non-trivial zeros at $s=1/2$.
Such terms contribute a constant times $x^{1/2}/\log{x}$ to the above, and we may rewrite it
as:
\begin{equation}
    \label{eq:main estimate on GRH, finite sum nu}
    P(x) -\frac{r}{\phi(q)} \pi(x)
    = \frac{x^{1/2}}{\log{x}}
    \left( \sum_{0<|\gamma|< X} \alpha_\rho \frac{x^{i\gamma}}{\rho}
    + \nu +O\left(\frac{x^{1/2}\log(X)^2}{X}+\frac{1}{\log{x}}\right)\right),
\end{equation}
where $\nu$ is equal to $r/\phi(q)-\kappa$ plus, if the term $\rho=1/2$ appears
in the sum, $2\alpha_{1/2}$.

\subsection{A mean square estimate of the average difference}
\label{sec:mean square a}

Let
\begin{equation}
    \label{eq:Delta}
    \Delta(x):= \frac{\log{x}}{x^{1/2}} \left(P(x) - \frac{r}{\phi(q)} \pi(x)\right).
\end{equation}
Rather than work with $\Delta(x)$ directly, it is
technically easier to work with its average:
\begin{equation}
    \label{eq:average Delta}
    M(x) := \frac{1}{x} \int_2^x \Delta(t) dt =
    \sum_{\rho\neq 1/2} \alpha_\rho \frac{x^{i\gamma}}{\rho(i\gamma+1)}
    + \nu +O\left(1/\log{x}\right).
\end{equation}
The latter equality can be derived by integrating the bracketed expression
in~\eqref{eq:main estimate on GRH, finite sum nu} termwise, and letting $X \to \infty$.


Formula~\eqref{eq:N(T)} implies that
$\sum_\rho 1/(\rho(i\gamma+1))$ converges absolutely, and this simplifies
our analysis of the mean square. Indeed, we can truncate the above sum over $\rho$
so that the tail is uniformly small.
More precisely, for any $\epsilon>0$, there exists $T=T(\epsilon)$ such that
\begin{equation}
    \label{eq:average Delta truncated}
    M(x) =
    \sum_{0<|\gamma|<T} \alpha_\rho \frac{x^{i\gamma}}{\rho(i\gamma+1)}
    + \nu + V(x),
\end{equation}
where
\begin{equation}
    \label{eq:V}
    V(x) < \epsilon,
\end{equation}
for all $x$ sufficiently large.

The natural scale at which to analyze the explicit formula is
logarithmic. Set $y=\log{x}$, and consider
\begin{equation}
    \label{eq:mean square a}
    \frac{1}{Y}\int_{\log{2}}^{Y} |M(e^y)|^2 dy
\end{equation}
Substitute the rhs of~\eqref{eq:average Delta truncated} for $M(e^y)$.
Now,
\begin{eqnarray}
    \label{eq:mean square main term}
    &&\lim_{Y \to \infty}
    \frac{1}{Y}\int_{\log{2}}^{Y}
    \left|
    \sum_{0<|\gamma|<T} \alpha_\rho \frac{e^{i\gamma y}}{\rho(i\gamma+1)}
        + \nu
    \right|^2 dy \notag \\
    &=&
    \sum_{0<|\gamma|<T} \frac{|\alpha_\rho|^2}{|\rho(i\gamma+1)|^2}
    +\nu^2,
\end{eqnarray}
which follows by multiplying
\begin{equation}
    \label{eq:sum rho}
    \sum_{0<|\gamma|<T} \alpha_\rho \frac{e^{i\gamma y}}{\rho(i\gamma+1)} + \nu
\end{equation}
by its conjugate, expanding, and noting that only the diagonal terms survive the limit
$Y\to\infty$. Next, the expression in~\eqref{eq:sum rho} is bounded for $y\in
\R$, and combining with~\eqref{eq:V} gives
\begin{eqnarray}
    \label{eq:mean square V}
    &&\frac{1}{Y}\int_{\log{2}}^{Y}
    \left(2\left|
    \sum_{0<|\gamma|<T} \alpha_\rho \frac{e^{i\gamma y}}{\rho(i\gamma+1)}
        + \nu
    \right| |V(e^y)| +
    |V(e^y)|^2\right) dy \notag \\
    &\ll& \epsilon+\epsilon^2,
\end{eqnarray}
for all $Y$ sufficiently large.
Since we may make $\epsilon$ as small as we wish, we have
that~\eqref{eq:mean square a} converges to the rhs of~\eqref{eq:mean square main term}
, and is {\em positive} because at least one $\alpha_\rho$ is non-zero.
Hence,
\begin{equation}
    \label{eq:Omega M}
    M(e^y) = \Omega(1),
\end{equation}
i.e.
\begin{equation}
    \label{eq:Omega M b}
    M(x) = \Omega(1),
\end{equation}
which implies, from~\eqref{eq:average Delta}, that
\begin{equation}
    \label{eq:Omega Delta}
    \Delta(x) = \Omega(1),
\end{equation}
and hence from~\eqref{eq:Delta} we get~\eqref{eq:omega bound on theta=1/2}.


\subsection{Unsmoothed mean square estimate}
\label{sec:mean square b}

In this subsection we give an alternate proof of the Omega
bound~\eqref{eq:omega bound on theta=1/2} by working out an unsmoothed mean
square.

Substituting $y=\log{x}$ and $Y=\log{X}$ in~\eqref{eq:main estimate on GRH,
finite sum nu}, we consider
\begin{equation}
    \label{eq:main estimate on GRH, finite sum a}
    P(e^y) - \frac{r}{\phi(q)} \pi(e^y)
    = \frac{e^{y/2}}{y} \left( \sum_{0<|\gamma|< e^Y} \alpha_\rho \frac{e^{i\gamma y }}{\rho}
    + \nu +O\left(\frac{e^{y/2} Y^2}{e^Y}+\frac{1}{y}\right)\right).
\end{equation}
Unlike $M(x)$ which was uniformly approximated by the finite
sum~\eqref{eq:average Delta truncated}, the above diverges absolutely and
cannot be uniformly approximated. However we can show
that we can approximate the sum with finitely many terms so that
the remainder term is uniformly small in mean square.

Thus, truncate the sum over $\rho$ at some large, but fixed $T$ (i.e. independent
of $y$), and consider, the mean square of the remainder.
This is
essentially Lemma 2.2 of~\cite{RS}, but we provide slightly more detail here.
Thus, for $T \geq 1$, and $\log{2} \leq y$, we have
\begin{equation}
    \label{eq:main estimate on GRH, finite sum b}
    P(e^y) - \frac{r}{\phi(q)} \pi(e^y)
    = \frac{e^{y/2}}{y} \left( \sum_{0<|\gamma|< T} \alpha_\rho \frac{e^{i\gamma y }}{\rho}
    + \nu + r(y,T) \right),
\end{equation}
where, for all $Y$ satisfying $y \leq Y$,
\begin{equation}
    \label{eq:r}
    r(y,T)
    =  \sum_{T \leq |\gamma|<e^Y } \alpha_\rho \frac{e^{i\gamma y }}{\rho}
    + O\left(\frac{e^{y/2} Y^2}{e^Y}+\frac{1}{y}\right).
\end{equation}
%We have broken up the sum over zeros in this way, using the two parameters $T$ and $Y$, for
%the reason that, to get a small remainder term in the explicit formula, we need to take a large
%number of zeros, roughly $|\gamma|<X$. However, it is easier to study the sum
%if we only have a fixed number of terms, hence the choice of cutoff after $T$ terms.
The following lemma gives a bound on the mean square of the remainder $r(y,T)$.
\begin{lemma}
\label{lemma:mean square}
Let  $T > 1$ and $Y>T^{1/2}/\log{T}$. Then,
\begin{equation}
    \frac{1}{Y/2} \int_{Y/2}^{Y} |r(y,T)|^{2} dy
    \ll_{q} \frac{\log(T)^2}{T}.
\end{equation}
\end{lemma}
{\bf {\it Proof:}}
Substitute \eqref{eq:r} into the integrand, and
use the inequality
\begin{equation}
    \label{eq:AGM}
    |a+b|^2 \leq 2(|a|^2 + |b|^2),
\end{equation}
which follows from the arithmetic geometric mean inequality $2|ab| \leq |a|^2 +|b|^2$,
to get
\begin{equation}
    \int_{Y/2}^{Y} | r(y,T) |^{2} dy
    \ll \int_{Y/2}^{Y} 
    \left|
        \sum_{T \leq |\gamma| \leq e^{Y}}
        \alpha_\rho \frac{e^{iy\gamma}}{1/2+i\gamma}
    \right|^{2} dy + 1/Y.
\end{equation}
The term $1/Y$ comes about from integrating the square of the $O$
term in~\eqref{eq:main estimate on GRH, finite sum a}. Multiplying out the
sum above by its conjugate, estimating the resulting integral, and extending the
double sum to infinity, the rhs above becomes
\begin{eqnarray}
    &&
    \sum_{{T \leq |\gamma_1| \leq e^{Y}}\atop{T \leq |\gamma_2| \leq e^{Y}}}
    \frac{\alpha_{\rho_1} \bar{\alpha}_{\rho_2}}{\rho_1 \bar{\rho_2}}
    \int_{Y/2}^{Y} e^{iy(\gamma_1-\gamma_2)}
    dy + 1/Y \notag \\
    &\ll&
    \sum_{{T \leq |\gamma_1| \leq \infty}\atop{T \leq |\gamma_2| \leq \infty}}
    \frac{1}{|\rho_1| |\rho_2|}
    \min\left(Y,\frac{1}{|\gamma_1-\gamma_2|}\right) + 1/Y.
\end{eqnarray}

Breaking up the sum over zeros into unit intervals $|\gamma| \in [n,n+1)$, with $n \in \Z$, $n\geq T-1$,
and using~\eqref{eq:N(T)} to bound the number of such $\gamma$ by $O(\log{m})$, the above sum
is bounded by
\begin{equation}
    \label{eq:bound on double sum}
    \ll
    Y \sum_{n \geq T-1} \frac{\log(n)^2}{n^2}
    +\sum_{{n \geq T-1} \atop {m \geq n+1}} \frac{\log{m}}{m} \frac{\log{n}}{n}\frac{1}{m-n}.
\end{equation}
The first sum accounts for the contribution of the diagonal terms, i.e. where
$|\gamma_1|$ lies in an interval $[n,n+1)$ and $|\gamma_2|$ lies in $[m,m+1)$,
with $|m-n| \leq 1$. For such pairs of zeros, which could potentially be very
close, we use $Y$ as an upper bound for $\min(Y,1/|\gamma_1-\gamma_2|)$. For
all other pairs of zeros the quantity $1/|\gamma_1-\gamma_2| \ll 1/|m-n|$ is
much smaller than $Y$. This gives the second sum above, i.e. the off-diagonal
terms. We have also exploited symmetry in taking half the terms, i.e. we have
dropped $n \geq m+1$.

By comparing with the integral $\int_T^\infty \log(t)^2/t^2 dt$, we get,
on integrating by parts,
\begin{equation}
    \label{eq:bound diagonal}
    \sum_{n \geq T-1} \frac{\log(n)^2}{n^2} \ll \frac{\log(T)^2}{T}.
\end{equation}
To bound the off-diagonal contribution, break up the sum over $m$ into
the terms, $n+1 \leq m \leq 2n$, and the tail $m>2n$.
The first portion can be estimated as follows:
\begin{equation}
    \label{eq:bound off diagonal}
    \sum_{ {n \geq T-1} \atop {n+1 \leq m \leq 2n}} \frac{\log{m}}{m} \frac{\log{n}}{n}\frac{1}{m-n}
     \ll \sum_{n \geq T-1} \frac{\log(n)^2}{n^2} \sum_{n+1 \leq m \leq 2n} \frac{1}{m-n}
     \ll \sum_{n \geq T-1} \frac{\log(n)^3}{n^2} \ll \frac{\log(T)^3}{T}.
\end{equation}
For the contribution from the tail, use $1/|m-n| < 2/m$ when $m > 2n$:
\begin{equation}
    \label{eq:bound off diagonal b}
    \sum_{ {n \geq T-1} \atop {m > 2n}} \frac{\log{m}}{m} \frac{\log{n}}{n}\frac{1}{m-n}
     \ll
     \sum_{ n \geq T-1} \frac{\log{n}}{n} \sum_{m >2n} \frac{\log{m}}{m}\frac{1}{m}
     \ll \sum_{ n \geq T-1} \frac{\log(n)^2}{n^2} \ll \frac{\log(T)^2}{T},
\end{equation}
where we used $\sum_{m >2n} \log(m)/m^2 \ll \log(n)/n$ in passing from the second to third
expression.

Putting these bounds together gives
\begin{equation}
    \int_{Y/2}^{Y} |r(y,T)|^{2} dy
    \ll_{q} Y \frac{\log^{2} T}{T} +\frac{\log(T)^3}{T} + \frac{1}{Y}.
\end{equation}
For given $T$, and all $Y>T^{1/2}/\log{T}$, the first term on the rhs dominates.
Dividing by $\frac{1}{Y/2}$ gives the lemma.


%We have, therefore, shown that, given $\eps >0$, we can fix $T=T(\eps)$ large enough so that
%for all sufficiently large $Y$, depending on $T$, we have:
%\begin{equation}
%    \label{eq:mean square r}
%    \frac{1}{Y/2} \int_{Y/2}^{Y} |r(y,T)|^{2} dy < \eps.
%\end{equation}

Returning to~\eqref{eq:main estimate on GRH, finite sum b}, we consider
the mean square:
\begin{equation}
    \label{eq:main mean square}
    \frac{1}{Y/2} \int_{Y/2}^Y 
    \left|(P(e^y) - \frac{r}{\phi(q)} \pi(e^y)) \frac{y}{e^{y/2}}\right|^2 dy
    =
    \frac{1}{Y/2} \int_{Y/2}^Y
        \left| \sum_{0<|\gamma|< T} \alpha_\rho \frac{e^{i\gamma y }}{\rho}
        + \nu + r(y,T) \right|^2 dy.
\end{equation}
The above equals
\begin{equation}
    \label{eq:main mean square b}
    \frac{1}{Y/2} \int_{Y/2}^Y
        \left| \sum_{0<|\gamma|< T} \alpha_\rho \frac{e^{i\gamma y }}{\rho}
        + \nu \right|^2 dy + E
\end{equation}
where
\begin{equation}
    \label{eq:E}
    |E| \ll
    \frac{1}{Y/2} \int_{Y/2}^Y
        \left| \sum_{0<|\gamma|< T} \alpha_\rho \frac{e^{i\gamma y }}{\rho}
        + \nu \right| |r(y,T)| dy
    + \frac{1}{Y/2} \int_{Y/2}^Y |r(y,T)|^2 dy.
\end{equation}
By multiplying the expression inside the absolute value of~\eqref{eq:main mean square b}
by its conjugate, and integrating termwise, we get
\begin{equation}
    \label{eq:main mean square c}
    \frac{1}{Y/2} \int_{Y/2}^Y
        \left| \sum_{0<|\gamma|< T} \alpha_\rho \frac{e^{i\gamma y }}{\rho}
        + \nu \right|^2 dy = \nu^2 + \sum_{0<|\gamma|< T} \frac{|\alpha_\rho|^2}{|\rho|^2}
        +O_T(1/Y).
\end{equation}
Next we estimate $E$. The bound~\eqref{eq:E} gives
\begin{equation}
    \label{eq:E 2}
    |E| \ll
    \max_{Y/2 \leq y \leq Y} \left| \sum_{0<|\gamma|< T} \alpha_\rho \frac{e^{i\gamma y }}{\rho} 
    + \nu \right|
    \frac{1}{Y/2} \int_{Y/2}^Y
        |r(y,T)| dy
    + \frac{1}{Y/2} \int_{Y/2}^Y |r(y,T)|^2 dy.
\end{equation}
Lemma~\ref{lemma:mean square} gives an estimate for the second integral:
\begin{equation}
     \frac{1}{Y/2} \int_{Y/2}^Y |r(y,T)|^2 dy \ll \frac{\log(T)^2}{T}.
\end{equation}
Now, from~\eqref{eq:N(T)}
\begin{equation}
    \left| \sum_{0<|\gamma|< T} \alpha_\rho \frac{e^{i\gamma y }}{\rho} + \nu \right|
    \ll
    \sum_{|\gamma|< T} \frac{1}{|\rho|} \ll \log(T)^2.
\end{equation}
Furthermore, the Cauchy-Schwarz inequality gives
\begin{equation}
    \frac{1}{Y/2} \int_{Y/2}^Y
        |r(y,T)| dy \ll
    + \frac{1}{Y/2} 
    \left(
        \int_{Y/2}^Y dy
        \int_{Y/2}^Y |r(y,T)|^2 dy
    \right)^{1/2},
\end{equation}
which, by lemma~\ref{lemma:mean square}, is
\begin{equation}
    \ll \frac{\log{T}}{T^{1/2}}.
\end{equation}
Since we may choose $T$ as large as we please, we have
on combining the above estimates, that, as $Y \to \infty$,
\begin{equation}
    \label{eq:main mean square d}
    \frac{1}{Y/2} \int_{Y/2}^Y
    \left|(P(e^y) - \frac{r}{\phi(q)} \pi(e^y)) \frac{y}{e^{y/2}}\right|^2 dy
    \to
    \nu^2 + \sum_{\rho\neq 1/2} \frac{|\alpha_\rho|^2}{|\rho|^2}.
\end{equation}
As in the previous subsection, the rhs above is positive because
at least one of the $\alpha_\rho$ is non-zero. Therefore,
\begin{equation}
    \left(P(e^y) - \frac{r}{\phi(q)} \pi(e^y)\right) \frac{y}{e^{y/2}} =\Omega(1),
\end{equation}
and hence
\begin{equation}
    \label{eq:lower bound diff}
    P(x) - \frac{r}{\phi(q)} \pi(x) = \Omega \left(\frac{x^{1/2}}{\log{x}}\right).
\end{equation}

This establishes Theorem~\ref{thm:1} in the case of residue classes.

Note that it is important that $r/\phi(q)<1$, since if we take $P$ to be the
set of all primes then it {\it can} be realized, in many ways, as a union
of primes in residue classes by taking all residue classes mod $q$, for any
positive integer $q$.
The reason the proof fails in this case is that $P(x)-\pi(x)$ is then
identically zero (and hence continuous),
giving a mean square for $P(x)-\pi(x)$, and more precisely,
of~\eqref{eq:main mean square d}, which is always zero.
The positivity of the rhs of that equation requires there to be at least one
non-zero term appearing on the rhs. However, from the formula analogous
to~\eqref{eq:c_chi}, all the $c_\chi$ and hence $\alpha_\rho$ are 0, and similarly for
the term $r/\phi(q)-\kappa$ which then equals $0$.

\setcounter{equation}{0}
\section{Generalization to Chebotarev sets}
\label{sec:chebotarev}

Here we generalize the problem to prime ideals and Chebotarev sets.

Therefore, let $L$ be a Galois extension of $K$ with Galois group
$G=\Gal(L/K)$. For a prime ideal $\p \in K$, we let the Artin symbol $(L/K,\p)$
denote the conjugacy class of Frobenius automorphisms corresponding to the
prime ideals $\Pri \in L$ that divide $\p$.

Given a conjugacy class $C$ of $G$, we let
\begin{equation}
    \label{eq:P C}
    P_{L/K,C} =
    \left\{\p \in \pi(K) | \p
    \text{ unramified in $L$, $(L/K,\p) = C$}  \right\},
\end{equation}
consist of the unramified prime ideals $\p \in K$, and Frobenius conjugacy
class in $G$ equal to $C$. We define the counting function
\begin{equation}
    \label{eq:pi C}
    \pi(x,L/K,C) := \sum_{{N_{K/\Q}(\p) \leq x}\atop{\p \in P_{L/K,C}}} 1
\end{equation}
to be the number of prime ideals in $P_{L/K,C}$ with norm less than or equal to $x$.
Throughout what follows, we simply write $N\mathfrak{a}$ rather than $N_{K/\Q}(\mathfrak{a})$.

The Chebotarev density theorem states that
\begin{equation}
    \label{eq:chebotarev pnt}
    \pi(x,L/K,C) \sim \frac{|C|}{|G|} \Li(x),
\end{equation}
and the prime number theorem for prime ideals in $K$ states that
\begin{equation}
    \label{eq:pi(x,K)}
    \pi(x,K) := \{\p \in \pi(K)| N\p \leq x\} \sim \Li(x).
\end{equation}
Therefore, say we have a subset $P$ of prime ideals in $\pi(K)$ that is
realized, up to finitely many exceptions, as a finite union of Frobenius
conjugacy classes in the Galois group $G$ of some Galois extension $L$ of $K$.
We can restrict ourselves to the case of a single Galois extension $L$ for
similar reasons that we were able to restrict ourselves to a single modulus $q$
in the previous section. See the comments in the introduction in
Section~\ref{sec:Chebotarev intro}.


\subsection{Proof of Theorem 1 and 2}
\label{sec:proofs in general}

All the formulas used in the classical situation of residue classes in
Section~\ref{sec:classical} have analogues in the case of number fields. In
particular, the explicit formula for our situation has been worked out, with
remainder terms, by Lagarias and Odlyzko~\cite{LO}. We develop and collect
below the needed formulas.

Define
\begin{equation}
    \label{eq:psi C}
    \psi(x,L/K,C) := \sum_{ {{N\p^m \leq x}\atop{\text{$\p$ unramified}}}\atop{(L/K,\p)^m=C}}
                     \log N \p,
\end{equation}
\begin{eqnarray}
    \label{eq:Pi C}
    \Pi(x,L/K,C) &:=& \sum_{ {{N\p^m \leq x}\atop{\text{$\p$ unramified}}}\atop{(L/K,\p)^m=C}}
                      \frac{1}{m} \notag \\
                  &=& \pi(x,L/K,C) + R(x,L/K,C),
\end{eqnarray}
where 
\begin{eqnarray}
    \label{eq:R(x,L/K,C)}
    R(x,L/K,C) :=
               \sum_{ {{N\p^m \leq x}\atop{\text{$\p$ unramified,$m\geq 2$}}}\atop{(L/K,\p)^m=C}}
               \frac{1}{m},
    %R(x,L/K,C) &:=&
    %           \sum_{ {{N\p^m \leq x}\atop{\text{$\p$ unramified,$m\geq 2$}}}\atop{(L/K,\p)^m=C}}
    %           \frac{1}{m} \notag \\
    %           &=&
    %           \sum_{ {{N\p^2 \leq x}\atop{\text{$\p$ unramified}}}\atop{(L/K,\p)^2=C}}
    %           \frac{1}{2}
    %           +
    %           \sum_{ {{N\p^m \leq x}\atop{\text{$\p$ unramified,$m\geq 3$}}}\atop{(L/K,\p)^m=C}}
    %           \frac{1}{m},
\end{eqnarray}
so that
\begin{eqnarray}
    \label{eq:pi C vs Pi C}
    &&\pi(x,L/K,C) = \Pi(x,L/K,C) - R(x,L/K,C) \notag \\
    &=& \frac{\psi(x,L/K,C)}{\log(x)}
        + \int_2^x \frac{\psi(t,L/K,C)}{t \log(t)^2} dt -R(x,L/K,C).
\end{eqnarray}
Likewise, define
\begin{equation}
    \label{eq:Pi K}
    \Pi(x,K) := \sum_{ N\p^m \leq x} \frac{1}{m} = \pi(x,K) + R(x,K),
\end{equation}
where
\begin{eqnarray}
    \label{eq:R(x,K)}
    R(x,K) :=
               \sum_{ N\p^m \leq x \atop m\geq 2}
               \frac{1}{m}.
    %R(x,K) &:=&
    %           \sum_{ N\p^m \leq x \atop m\geq 2}
    %           \frac{1}{m} \notag \\
    %           &=&
    %           \sum_{ N\p^2 \leq x}
    %           \frac{1}{2}
    %           +
    %           \sum_{ N\p^m \leq x \atop m\geq 3}
    %           \frac{1}{m}.
\end{eqnarray}
Thus,
\begin{eqnarray}
    \label{eq:pi K vs Pi K}
    \pi(x,K) &=& \Pi(x,K) - R(x,K) \notag \\
                 &=& \frac{\psi(x,K)}{\log(x)} 
                     + \int_2^x \frac{\psi(t,K)}{t \log(t)^2} dt -R(x,K).
\end{eqnarray}
We will also use
\begin{eqnarray}
    \label{eq:R(x,K) b}
    R(x,K) &=&
    \sum_{ N\p^2 \leq x}
    \frac{1}{2}
    +
    \sum_{ N\p^m \leq x \atop m\geq 3}
    \frac{1}{m} \notag \\
    &=& x^{1/2}/\log{x} + O(x^{1/3}/\log{x}),
\end{eqnarray}
which follows from the prime number theorem for ideals, with the implied
constant in the O depending on $K$. Similarly, from the Chebotarev density
theorem, we have
\begin{equation}
    \label{eq:R C estimate}
    \sum_{j=1}^{r}
    R(x,L/K,C_j)
    = \kappa x^{1/2}/\log{x} + O(x^{1/2}/\log(x)^2),
\end{equation}
with the implied constant in the $O$ depending on $L/K$ and the $C_j$, and,
overriding the notation for $\kappa$ used earlier,
\begin{equation}
    \label{eq:kappa C}
    \kappa =
    \frac{1}{|G|} \sum_{j=1}^{r} |C_j|
    \sum_{b^2 \in C_j} 1,
\end{equation}
the inner sum counting the number of conjugacy class representatives $b \in G$ that,
when squared, lie in $C_j$.

To obtain an explicit formula for $\psi(x,L/K,C)$, Lagarias and Odlyzko mimic
the approach taken in Davenport for primes in arithmetic progression, using
the following linear combination of logarithmic derivatives of Artin $L$-functions
in order to extract primes ideals (and their powers) lying in the conjugacy class $C$:
\begin{eqnarray}
    \label{eq:F_C(s)}
    F_C(s) &:=& -\frac{|C|}{|G|} \sum_{\phi}\bar{\phi}(g) L'/L(s,\phi,L/K) \notag \\
    &=& \sum_{\p^m} \theta(\p^m) \log(N\p) (N\p)^{-ms},
\end{eqnarray}
where $g$ is any element of the conjugacy class $C$, $\phi$ runs over the irreducible
characters of $G$, and,
for unramified $\p$:
\begin{equation}
    \label{eq:theta is}
    \theta(\p^m) =
    \begin{cases}
        1 \quad \text{$(L/K,\p)^m = C$},\\
        0 \quad \text{otherwise},
    \end{cases}
\end{equation}
while, for ramified $\p$, $|\theta(\p^m)| \leq 1$. Notice that, while the rhs
of~\eqref{eq:F_C(s)} resembles the Dirichlet series that gives the counting
function in~\eqref{eq:psi progressions}, there is a minor difference. Above,
and also in~\eqref{eq:F_C(s) b} below, the characters are primitive. The way to
interpret~\eqref{eq:psi progressions} so that it matches with the formula here,
is that each $\chi$ in~\eqref{eq:psi progressions} should be replaced by its
inducing character at a cost of $O(\log(x))$ to $\psi(x,q,a)$ coming from the
primes that ramify.

Brauer~\cite{B} proved that each Artin $L$-function can be written as a ratio
of Hecke $L$-functions, hence the linear combination of logarithmic derivatives
of Artin $L$-functions above can be written in terms of Hecke $L$-functions. In
our situation, the particular linear combination turns out, nicely, to have a
similar form to~\eqref{eq:F_C(s)}. Lagarias and Odlyzko use a construction
(Lemma 4.1 in their paper) of Deuring~\cite{D} to write
\begin{eqnarray}
    \label{eq:F_C(s) b}
    F_C(s) = -\frac{|C|}{|G|} \sum_{\chi}\bar{\chi}(g) L'/L(s,\chi,L/E),
\end{eqnarray}
where $\chi$ runs over the irreducible Hecke characters of $H=<g>$, the cyclic subgroup
generated by $g$, and $E$ is the fixed field of $H$.

The advantage of writing $F_C(s)$ in terms of Hecke characters is that the
analytic properties of Hecke $L$-functions are well established. Lagarias and
Odlyzko carry out a Perron integral in order to extract the Dirichlet
coefficients, with $N\p^m \leq x$, of $F_C(s)$.

Restricting to $2<x<X$, equation (7.4) of~\cite{LO} gives
\begin{equation}
    \label{eq:psi C estimate}
    \psi(x,L/K,C) = \frac{|C|}{|G|}
    \left(
        x - \sum_{\chi}\bar{\chi}(g)\sum_{|\Im \rho_\chi|<X} \frac{x^\rho_\chi}{\rho_\chi}
    \right) + \text{remainder}(x,X,L/K,C),
\end{equation}
where
\begin{equation}
    \text{remainder}(x,X,L/K,C)=
    O\left(\frac{x\log(X)^2}{X}+\log{x}\right),
\end{equation}
with the implied constant depending on $L/K$ and $C$. Here, $\rho$ runs over
all the non-trivial zeros of $L(s,\chi,L/E)$. The main term $\frac{|C|}{|G|} x$
arises from the principal character $\chi_0$ since $L(s,\chi_0,L/E)$ has, up to
finitely many Euler factors, $\zeta(s)$ as one of its factors, and hence a
simple pole at $s=1$.

Our remainder term is simpler than in (7.4) of Lagarias and Odlyzko
because we are taking $L/K$ to be fixed. Furthermore, $\text{remainder}(x,X,L/K,C)$
is a piecewise continuous function, with $O(\log{x})$ discontinuities at the points
$x=N\p^m$, where $\p$ runs over the ramified prime in $K$.

Substitute~\eqref{eq:psi C estimate} into~\eqref{eq:pi C vs Pi C}, apply the
estimate~\eqref{eq:R C estimate}, and then substitute all into
\begin{equation}
    \label{eq:P C from pi}
    P(x) = \lambda + \sum_{j=1}^r \pi(x,L/K,C_j),
\end{equation}
where $\lambda \in \Z$ accounts for finitely many exceptions, and
$x$ is sufficiently large (so that $x$ exceeds the norm of any of these
exceptions).
Assuming that
\begin{equation}
    \label{eq:sum C/G}
    \sum_{j=1}^r |C_j| / |G| = a/b,
\end{equation}
we have, on subtracting the analogous formula for $a/b \pi(x,K)$
and cancelling the main term coming from pole at $s=1$ of the factor 
of $\zeta(s)$ in the Dedekind zeta function $\zeta_K$, that, for $2 \leq x<X$,
and assuming GRH,
\begin{equation}
    \label{eq:main estimate C on GRH, finite sum}
    P(x) - \frac{a}{b} \pi(x,K)
    = \frac{x^{1/2}}{\log{x}} \left( \sum_{|\gamma|< X} \alpha_\rho \frac{x^{i\gamma}}{\rho}
    + (a/b-\kappa) +O\left(\frac{x^{1/2}\log(X)^2}{X}+\frac{1}{\log{x}}\right)\right),
\end{equation}
$\alpha_\rho \in \C$, and where the sum over $\rho$ is over the non-trivial
zeros of all relevant $L$-functions, namely the Hecke $L$-functions, for each
$C_j$ in~\eqref{eq:F_C(s) b}.

As in the classical case, if the term $\rho=1/2$ appears in the sum, we absorb it into the
constant term. Thus, let $\mu=a/b-\kappa$ plus, in the event that $\rho=1/2$ appears
in the sum, $2\alpha_{1/2}$. The above then becomes
\begin{equation}
    \label{eq:main estimate C on GRH, finite sum b}
    P(x) - \frac{a}{b} \pi(x,K)
    = \frac{x^{1/2}}{\log{x}} \left( \sum_{0<|\gamma|< X} \alpha_\rho \frac{x^{i\gamma}}{\rho}
    + \mu +O\left(\frac{x^{1/2}\log(X)^2}{X}+\frac{1}{\log{x}}\right)\right),
\end{equation}

The cancellation of the main term deserves some
elaboration. The $L$-function corresponding to the principal character in
~\eqref{eq:F_C(s) b} factors as product of $\zeta_E(s)$ and Hecke
$L$-functions, and, because $K \subseteq E$, $\zeta_E(s)$ itself has
$\zeta_K(s)$ as a factor. The latter Dedekind zeta function is responsible for
cancellation in~\eqref{eq:main estimate C on GRH, finite sum} not just of the
main term, but also of some additional terms corresponding to the non-trivial
zeros of $\zeta_K(s)$. We therefore see that we could, in the statement of
Theorem 1 replace $\frac{a}{b} \pi(x,K)$ with $\frac{a}{b} \pi(x,F)$, where $F$
is any finite extension of $\Q$, or
even just $\frac{a}{b} \Li(x)$, since these
would have the same effect of cancelling the main term, with no further impact
on the form of the remaining terms. Similarly,
we could replace the counting function by $Q(x)$ where
$Q$ is another Chebotarev set with the same density $a/b$ as $P$.

Next, the jump discontinuities of the lhs of~\eqref{eq:main estimate C on GRH,
finite sum b}, up to given $x$, outnumber those of the $O$ term of the rhs, for
the same reason as in the case of residue classes mod $q$: the discontinuities
of the remainder term occur at $x=N\p^m$, $m\geq 2$, for $\p \in \pi(K)$,
coming from the terms $R(x,L/K,C_j)$ and $R(x,K)$, of which, because $m\geq 2$,
there are $O(x^{1/2}/\log{x})$ many. The other discontinuities come from the
ramified primes of which there are finitely many (and $O(\log{x})$ of their
powers, but these powers are already counted as discontinuities of $R(x,K)$).
On the other hand, the lhs has jump discontinuities at all prime ideals $\pi
\in \pi(K)$ of which there are asymptotically $x/\log{x}$ many. We therefore
conclude, as previously, that infinitely many of the $\alpha_\rho$ must be
non-zero or else the sum over zeros would be a continuous function and the rhs
would not have sufficiently many discontinuities.

Again this holds when we replace
$\frac{a}{b} \pi(x,K)$ with any of $\frac{a}{b} \pi(x,F)$, $\frac{a}{b} \Li(x)$,
or $Q(x)$ as above, though in the latter case we must also ensure that $Q$
does not essentially coincide with $P$, namely that the symmetric difference
$P \bigtriangleup Q$ is infinite. In each case the difference
between $P(x)$ and any of these counting functions has discontinuities
at a positive proportion of $N\p$ for primes ideals $\p \in \pi(K)$,
i.e. at $\gg x/\log{x}$ points.

As in the previous Section, define
\begin{equation}
    \label{eq:Theta K}
    \Theta = \lim\sup \{ \Re{\rho} | \alpha_\rho \neq 0\}.
\end{equation}
Then, $\Theta\geq 1/2$.

If $\Theta=1/2$, we have two mean square estimates analogous to those in
Sections~\ref{sec:mean square a} and~\ref{sec:mean square b}.
In order to carry out these estimates, we
also need a bound, as before, for the number of non-trivial zeros of a
Hecke $L$-function, $N(L,T) = |\{ \rho: L(\rho) = 0, |\Im{\rho}|\leq T, 0<
\Re{\rho}<1\}|$, in intervals of length one. Lagarias and Odlyzko prove, in Lemma 5.4 of~\cite{LO},
that $N(L,T+1)-N(L,T) = O(\log{T})$, with the implied constant depending on the
$L$-function, hence the method used to obtain the mean square estimate in the
case of Dirichlet $L$-functions and residue classes follows through as before
and we summarize the formulas.

Adapting the notation used in Section~\ref{sec:mean square a},
let
\begin{equation}
    \label{eq:Delta K}
    \Delta(x):= \frac{\log{x}}{x^{1/2}} \left(P(x) - \frac{a}{\phi(b)} \pi(x,K)\right).
\end{equation}
and
\begin{equation}
    \label{eq:average Delta K}
    M(x) := \frac{1}{x} \int_2^x \Delta(t) dt.
\end{equation}
Then
\begin{eqnarray}
    \label{eq:mean square main term K}
    &&\lim_{Y \to \infty}
    \frac{1}{Y}\int_{\log{2}}^{Y}
    \left| M(e^y) \right|^2 dy \notag \\
    &=&
    \sum_{0<|\gamma|<T} \frac{|\alpha_\rho|^2}{|\rho(i\gamma+1)|^2}
    +\mu^2,
\end{eqnarray}
and
\begin{eqnarray}
    \label{eq:mean square b K}
    &&\lim_{Y\to \infty}
    \frac{1}{Y/2} \int_{Y/2}^Y
    \left|(P(e^y) - \frac{a}{b} \pi(e^y,K)) \frac{y}{e^{y/2}}\right|^2 dy \notag \\
    &=&
    \mu^2 + \sum_{\rho\neq 1/2} \frac{|\alpha_\rho|^2}{|\rho|^2}.
\end{eqnarray}
And, because at least one $\alpha_\rho$ is non-zero, both mean squares are positive.
From either, we can thus conclude as in Sections~\ref{sec:mean square a} or~\ref{sec:mean square b}
that
\begin{equation}
    P(x) - \frac{a}{b}\pi(x,K) = \Omega\left(\frac{x^{1/2}}{\log{x}} \right).
\end{equation}

This concludes our proof of Theorems~\ref{thm:1} and~\ref{thm:1b}.

We also get the following theorem, depending on the value of $\Theta$:
\begin{theorem}
\label{thm:3}
For every $\delta>0$,
\begin{equation}
    \label{eq:P(x) K Omega Theta>1/2}
    P(x) - \frac{a}{b}\pi(x,K) =
    \Omega(x^{\Theta-\delta}),
\end{equation}
with the implied constant in the $\Omega$ depending on $\delta$, and $P$.
\end{theorem}
\noindent{\bf Proof:}
If $\Theta=1/2$ then Theorem~\ref{thm:1} provides a stronger result and the
above therefore holds. If $\Theta>1/2$, the theorem follows, as in
Section~\ref{sec:theta > 1/2}, from the fact that at least one $\alpha_\rho$ is
non-zero and from the identity, initially derived with the assumption that
$\Re{s}>1$,
\begin{eqnarray}
    \label{eq:Dirichlet integral K}
    &&\int_1^\infty \frac{\sum_{j=1}^r \Pi(x,L/K,C_j) -\frac{a}{b}\Pi(x,K)}{x^{s+1}} dx \notag \\
    &=& \frac{1}{s} \sum_{j=1}^r \sum_{\chi_j} \bar{\chi}(g_j) \log(L(s,\chi_j,L/E_j)) - \frac{a}{b} \log(\zeta_K(s)).
\end{eqnarray}
where, for $1\leq j\leq r$, $\chi_j$ runs over all the irreducible Hecke
characters of $H_j=<g_j>$, and $E_j$ is the fixed field of $H_j$.

Finally, a similar theorem holds for a variety of
counting functions. As before, let $Q$ be a Chebotarev set with the same
density $a/b$ as $P$, such that the symmetric difference $P \bigtriangleup Q$
is infinite, and $F$ any finite extension of $\Q$. Let $f(x)$ stand for any
of $\frac{a}{b}\Li(x)$, $\frac{a}{b}\pi(x,F)$, or $Q(x)$. For each such choice
of $f(x)$, the difference $P(x)-f(x)$ can be expressed as a linear combination of
explicit formulae having the same form as~\eqref{eq:main estimate C on GRH, finite sum}, though with the
constant term $a/b-\kappa$ replaced by $-\kappa$ in the case of
$f(x)=\frac{a}{b}\Li(x)$, and by $\kappa_2-\kappa$, when $f(x)=Q(x)$, where
$\kappa_2$ is the analogue of~\eqref{eq:kappa C} for the Chebotarev set $Q$.
Thus, defining $\Theta_f$ to be the analogue, for a given $f$, of~\eqref{eq:Theta K},
we have the following theorem:

\begin{theorem}
\label{thm:4}
Let $f(x)$ be as in the above paragraph. Then,
for every $\delta>0$,
\begin{equation}
    P(x) - f(x) =
    \Omega(x^{\Theta_f-\delta}),
\end{equation}
with the implied constant in the $\Omega$ depending on $\delta$, $P$, and $f$.
\end{theorem}


{\bf Acknowledgements:} We would like to thank Barry Mazur for raising the problem addressed
in this paper. Jeffrey Lagarias provided some feedback regarding~\cite{LO}.

\begin{thebibliography}{99}

\bibitem{B} Brauer, R. (1947).
{\em On Artin’s $L$-series with general group characters}, Ann. Math. 48, 502–514.

\bibitem{Davenport} Davenport, H. (1980).
{\em Multiplicative Number Theory}, second edition, GTM 74,
Springer-Verlag, Berlin.

\bibitem{D} Deuring, M. (1934)
    {\em \"Uber den Tschebotareffschen Dichtigkeitssatz}, Math. Ann. 110, 414-415.

\bibitem{I} Ingham, A.E. (1932).
{\em The Distribution of Prime Numbers}, Cambridge University Press.

%\bibitem{L} Littlewood, J.E. (1928).
%{\em On the Class-Number of the Corpus $P(\sqrt{-k})$}, Proc.
%London Math. Soc, series 2, 27, 358-72.

\bibitem{L} Lagarias, J. (1983). {\em Sets of primes determined by systems of polynomial congruences},
    Illinois Jour. of Math., 27, 224-239.


\bibitem{LO} Lagarias, J. and Odlyzko, A. (1977). {\em Effective versions of the Chebotarev density theorem},
in Algebraic Number Fields, Frohlich, A. (ed.), Academic Press, 409--464.

\bibitem{RS} Rubinstein, M.O and Sarnak, P. (1994). {\em Chebyshev's Bias},
Experimental Mathematics, Vol. 3, No.3, 173-197.

\bibitem{S} Serre, J.P. (1976). {\em Divisibilit\'e de certaines fonctions arithm\'etiques},
    Enseignement Math. (2), 22, 227--260.

\bibitem{S2} Serre, J.P. (2011). {\em Lectures on $N_X(p)$}, A K Peters/CRC Press.

\end{thebibliography}
\end{document}


1112.4945.extracted_bib
\begin{thebibliography}{99}

\bibitem{B} Brauer, R. (1947).
{\em On Artin’s $L$-series with general group characters}, Ann. Math. 48, 502–514.

\bibitem{Davenport} Davenport, H. (1980).
{\em Multiplicative Number Theory}, second edition, GTM 74,
Springer-Verlag, Berlin.

\bibitem{D} Deuring, M. (1934)
    {\em \"Uber den Tschebotareffschen Dichtigkeitssatz}, Math. Ann. 110, 414-415.

\bibitem{I} Ingham, A.E. (1932).
{\em The Distribution of Prime Numbers}, Cambridge University Press.

%\bibitem{L} Littlewood, J.E. (1928).
%{\em On the Class-Number of the Corpus $P(\sqrt{-k})$}, Proc.
%London Math. Soc, series 2, 27, 358-72.

\bibitem{L} Lagarias, J. (1983). {\em Sets of primes determined by systems of polynomial congruences},
    Illinois Jour. of Math., 27, 224-239.


\bibitem{LO} Lagarias, J. and Odlyzko, A. (1977). {\em Effective versions of the Chebotarev density theorem},
in Algebraic Number Fields, Frohlich, A. (ed.), Academic Press, 409--464.

\bibitem{RS} Rubinstein, M.O and Sarnak, P. (1994). {\em Chebyshev's Bias},
Experimental Mathematics, Vol. 3, No.3, 173-197.

\bibitem{S} Serre, J.P. (1976). {\em Divisibilit\'e de certaines fonctions arithm\'etiques},
    Enseignement Math. (2), 22, 227--260.

\bibitem{S2} Serre, J.P. (2011). {\em Lectures on $N_X(p)$}, A K Peters/CRC Press.

\end{thebibliography}