\documentclass[11pt]{amsart}
    \usepackage{parskip}
    \usepackage[margin=1in]{geometry}
    \usepackage{amsmath,amssymb,amsthm}
    \usepackage[expansion=false]{microtype}
    \usepackage[colorlinks=true,linkcolor=blue,citecolor=blue,urlcolor=blue]{hyperref}
    \newtheorem{theorem}{Theorem}
    \newtheorem{proposition}[theorem]{Proposition}
    \newtheorem{lemma}[theorem]{Lemma}
    \theoremstyle{remark}
    \newtheorem{rmk}[theorem]{Remark}
     
    \newcommand{\ph}{\varphi(q)}
    \newcommand{\rough}{P^{-}}
    \newcommand{\eps}{\varepsilon}
    \newcommand{\Q}{\mathbf{Q}}
    \newcommand{\Z}{\mathbf{Z}}
    \newcommand{\F}{\mathbf{F}}
    \newcommand{\leg}[2]{\genfrac{(}{)}{}{}{#1}{#2}}
     
    \title{THE MISSING LIN(NI)K}
    \author{Paul Pollack}
    \address{Department of Mathematics, University of Georgia, Athens GA 30602}
    \email{pollack@uga.edu}
    \subjclass[2020]{Primary 11N13; Secondary 11N36}
    \keywords{Linnik's theorem, least prime in an arithmetic progression, Selberg's symmetry formula, sieve methods, Landau--Siegel zeros}
    \date{}
    \begin{document}
    \begin{abstract} We show how Selberg's symmetry formulas and the recent finding that there are no Landau--Siegel zeros connect to give a radically elementary proof of Linnik's theorem on the least prime in an arithmetic progression.
    \end{abstract}
    \maketitle
    \vspace{-0.2in}
    \section{Introduction}
    The purpose of this note is to give a simple proof of a celebrated 1944 theorem of Linnik \cite{linnik1,linnik2}.
    \begin{theorem}\label{thm:linnik}
    There is an absolute, effectively computable constant $L$ such that, for every $q\ge2$ and every $a$ coprime to $q$, some prime $p\equiv a\pmod q$ satisfies $p\le q^L$.
    \end{theorem}
     
    The traditional proofs of Theorem \ref{thm:linnik} go through zero-free regions, log-free zero-density estimates, and zero-repulsion phenomena; see, e.g., Iwaniec--Kowalski \cite[Chapter~18]{ik}. Beginning with work of Elliott \cite{elliott,elliott2}, several authors have given proofs where the analytic burden is shifted onto sieve methods and the theory of mean values of multiplicative functions. See, for instance, the treatments of Koukoulopoulos \cite[Chapter~27]{koubook} (cf. \cite{kou,sach}), Friedlander and Iwaniec \cite{opera,fi23,fiirr}, and Matom\"aki, Merikoski, and Ter\"av\"ainen \cite{mmt}. Our new proof of Linnik's theorem is short, elementary (no zeros of $L$-functions were harmed in the course of the argument), and ``unpretentious.''
     
    This argument comes out of recent breakthrough work announced by OpenAI \cite{openai}. Specifically, we need the following arithmetic encoding of the nonexistence of Siegel zeros.
     
    \begin{proposition}[Anti-concentration on $\psi=-1$]\label{prop:bias}
    For every $\eps>0$ there is an effectively computable $A_\eps$ such that, for every primitive nonprincipal real character $\psi$ of conductor $f$,
    \begin{equation*}
    \sum_{\substack{p\le x\\\psi(p)=-1}}\frac{\log p}{p}
    \le\left(\frac12+\eps\right)\log x\qquad(x\ge f^{A_\eps}).
    \end{equation*}
    \end{proposition}
    
    For many decades, Proposition \ref{prop:bias} was thought to lie very deep. However, Green \cite{green} has recently propounded a proof of (a slightly stronger version of) Proposition \ref{prop:bias} that fits in under 5 pages.\footnote{The theorem in \cite{green} is stated with $X=f^C$, but the proof
    works equally well for $X\ge f^C$, with $C$ fixed.} A technically simpler approach, using only undergraduate mathematics, has been presented by van Dijk \cite{vandijk}. We include a version of his argument in Appendix~\ref{sec:determinant}.
    See also Banks \cite{banks}, Barreto \cite{barreto}, Kerr \cite{kerr}, and Tao \cite{tao}.
     
    In addition to Proposition \ref{prop:bias}, we require certain variants of Selberg's symmetry formula \cite{selberg49}. Let $B$ be a sufficiently large integer, and put
    \[
    Y:=q^B,\qquad Z:=q^{B^2}.
    \]
    Below, $o(1)$ indicates a quantity that tends (effectively!) to zero as $B\to\infty$, uniformly in $q\ge2$ and in the choice of reduced residue class.
    In sums and products, $p,r,s,\ell$ denote primes unless otherwise indicated.
    \begin{proposition}[Two- and three-prime symmetry formulas]\label{prop:sym}
    Uniformly for $(c,q)=1$ and $x\ge Z$,
    \begin{align}
    \sum_{\substack{Y<p\le x\\p\equiv c\ (q)}}\frac{\log^2p}{p}
    +\sum_{\substack{p,r>Y,\ pr\le x\\pr\equiv c\ (q)}}\frac{\log p\log r}{pr}
    &=\frac{(1+o(1))\log^2x}{\ph},\label{eq:two}\\
    2\sum_{\substack{p,r,s>Y,\ prs\le x\\prs\equiv c\ (q)}}\frac{\log p\log r\log s}{prs}
    &=\sum_{\substack{Y<p\le x\\p\equiv c\ (q)}}\frac{\log^3p}{p}
    +o\left(\frac{\log^3x}{\ph}\right).
    \label{eq:three}
    \end{align}
    \end{proposition}

    For fixed modulus,  corresponding formulas without the
restrictions $p,r,s>Y$ appear in Selberg
\cite[(3.4) and (3.6)]{selberg49}. A related uniform two-prime
symmetry formula was given by Friedlander \cite[\S2]{fried}.
To keep the paper reasonably self-contained, we prove both
formulas \eqref{eq:two} and \eqref{eq:three} in
\S\ref{sec:sym} below.
     
        The overarching strategy of the proof goes back to Selberg \cite[\S\S5--6]{selberg49} (see also \cite[\S3]{selberg}): The two-prime symmetry formula suggests that primes are either well distributed in progressions or concentrated in the nontrivial coset of an index-two subgroup. (This connection is also explained and extensively developed by Granville in \cite{granville92} and \cite[\S2]{granville}.) Using also the three-prime formula, one shows such concentration is forced by the existence of a coprime progression with no small primes (or with few small primes). This is then ruled out by an anti-concentration estimate---in Selberg's paper \cite{selberg49}, this is his Lemma~1, while in ours, it is Proposition~\ref{prop:bias}. Selberg's regime of uniformity is different from ours (the paper \cite{selberg49} considers only fixed $q$) but the philosophy is the same!
     \subsection*{\texorpdfstring
    {Use of Super Intelligence$^{\text{\textregistered}}$}
    {Use of Super Intelligence}} \emph{This is intended as a work of exposition rather than (traditional) research.} All of the novel mathematics emerged from dialogues with ChatGPT Astra,
with prompting from the human author (P.\,P.) to nudge the proof in the direction of his own mathematical aesthetic. Astra also drafted the first version
of the paper, with the human author revising the text for the benefit of fellow Earth persons. P.\,P.~claims no credit for the underlying mathematics but takes responsibility for the final manuscript.
    
    Lean formalizations of the main results and the arguments in the appendices, together with verification records and instructions for reproducing the checks, are available at \url{https://github.com/twonth/missing-linnik-lean}. The formalized results use only Lean's standard axioms of propositional extensionality (\texttt{propext}), classical choice (\texttt{Classical.choice}), and quotient soundness (\texttt{Quot.sound}).
    
    P.\,P.~thanks OpenAI and Anthropic for providing complimentary
    access through the ChatGPT for Academic Researchers program and
    the Claude Team plan for scientists, respectively.
    
    \section{Not from concentrate: Proof of Theorem \ref{thm:linnik} modulo the symmetry formulas}\label{sec:break}
    The case $q=2$ is immediate, so assume $q\ge3$. We suppose that there is no prime $p\le Z^3$ with $p\equiv a\pmod q$ and derive a contradiction once $B$ is sufficiently large.
     
    For each character $\chi$ modulo $q$, put
    \[
    b_\chi=\frac1{\log Z}\sum_{Y<p\le Z}\frac{\chi(p)\log p}{p};
    \]
    this is essentially a weighted average of $\chi$ along the primes in $(Y,Z]$. Note that by the choice of $Y$, every prime $p$ appearing in the sum is larger than $q$, and so each $\chi(p) \ne 0$. We have
    \begin{equation*}
    b_{\chi_0}=1+o(1),\qquad |b_\chi|\le b_{\chi_0}.
    \end{equation*}
    
Here is how the proof will go. Using the three-prime symmetry formula, we show that a residue class containing no small primes forces $\sum_{\chi\ne\chi_0}|b_\chi|^3$ to be large. Comparing this with the bound for $\sum_{\chi\ne\chi_0}|b_\chi|^2$ obtained from Parseval's identity and the Brun--Titchmarsh inequality, we find that there must be a nonprincipal real character $\chi$ with $b_\chi=\pm(1+o(1))$. The two-prime symmetry formula rules out the plus sign, forcing  $b_\chi=-(1+o(1))$, contrary to the anti-concentration estimate of Proposition~\ref{prop:bias}.

    Down to business. Apply the three-prime symmetry formula \eqref{eq:three} with $c=a$ and $x=Z^3$. On the one hand, our assumption that there are no small primes $a\bmod{q}$ implies that the single-prime sum there vanishes, so that
    \[
    \sum_{\substack{p,r,s>Y,\ prs\le Z^3\\prs\equiv a\ (q)}}
    \frac{\log p\log r\log s}{prs}
    =o\left(\frac{\log^3 Z}{\ph}\right).
    \]
    On the other hand, orthogonality gives
    \begin{align*}
    \sum_{\chi\bmod q}\overline{\chi(a)}\,b_\chi^3
    &=\frac1{\log^3 Z}\sum_{Y<p,r,s\le Z}
    \frac{\log p\log r\log s}{prs}
    \sum_{\chi\bmod q}\overline{\chi(a)}\chi(prs)\\
    &=\frac{\ph}{\log^3 Z}
    \sum_{\substack{Y<p,r,s\le Z\\prs\equiv a\ (q)}}
    \frac{\log p\log r\log s}{prs} \\
    &\le \frac{\ph}{\log^3 Z}\sum_{\substack{p,r,s>Y,\ prs\le Z^3\\prs\equiv a\ (q)}}
    \frac{\log p\log r\log s}{prs}.
    \end{align*}
    The middle expression is nonnegative, so
    \[ 
    \sum_{\chi\bmod q}\overline{\chi(a)}\,b_\chi^3 = o(1).
    \]
    By the reverse triangle inequality,
    \begin{equation}\label{eq:cube}
    \sum_{\chi\ne\chi_0}|b_\chi|^3 \ge 1-o(1). 
    \end{equation}
    
    We compare \eqref{eq:cube} with what comes out of Parseval's formula. Setting
    $w_c:= \frac{1}{\log{Z}} \sum_{Y<p\le Z,\,p\equiv c\ (q)} \frac{\log{p}}{p}$,
    \[
    \sum_\chi|b_\chi|^2=\ph\sum_{(c,q)=1}w_c^2
    \le(2+o(1))\sum_{(c,q)=1} w_c=(2+o(1))b_{\chi_0},
    \]
    where the middle inequality uses a weak consequence of the Brun--Titchmarsh theorem (we prove what we need below, in \eqref{eq:upper}). Hence $E:=\sum_{\chi\ne\chi_0}|b_\chi|^2\le1+o(1)$. But 
   \[
    1-o(1)\le\sum_{\chi\ne\chi_0}|b_\chi|^3
    \le\left(\max_{\chi\ne\chi_0}|b_\chi|\right)E.
    \]
    It follows that $|b_\chi|=1+o(1)$ for some nonprincipal $\chi$. Moreover, $\chi$ must be real: Otherwise $E \ge |b_{\chi}|^2 + |b_{\bar{\chi}}|^2 = 2|b_{\chi}|^2 \ge 2-o(1)$. 
    
    There are two possibilities: Either $b_{\chi}=-1+o(1)$ or $b_{\chi}=1+o(1)$. We now rule out the latter. Since exactly half the reduced residue classes satisfy \(\chi(c)=-1\), the two-prime symmetry formula \eqref{eq:two} implies that 
\begin{equation}\label{eq:sign}
    \sum_{\substack{Y<p\le Z \\ \chi(p)=-1}}\frac{\log^2p}{p}
    +\sum_{\substack{p,r>Y\\pr\le Z \\ \chi(pr)=-1}}\frac{\log p\log r}{pr}
    =\left(\frac{1}{2}+o(1)\right)\log^2{Z}.
    \end{equation}
    If $b_\chi=1+o(1)$, then
    \[
    M_-:=\sum_{\substack{Y<p\le Z\\\chi(p)=-1}}\frac{\log p}{p}
    =\frac{b_{\chi_0}-b_\chi}{2}\log Z=o(\log Z).
    \]
But then the left-hand side of \eqref{eq:sign} is at most $M_{-}\log{Z}+2M_{-}\sum_{Y<r\le Z}\frac{\log{r}}{r} =o(\log^2{Z})$, contradicting \eqref{eq:sign} for large $B$. We use here that $\chi(pr)=-1$ implies $\chi(p)=-1$ or $\chi(r)=-1$. 
     
    We conclude that $b_\chi=-1+o(1)$, and therefore
    \begin{equation}\label{eq:concentration}
    \sum_{\substack{Y<p\le Z\\\chi(p)=-1}}\frac{\log p}{p}=(1-o(1))\log Z.
    \end{equation}
    Let $\psi$ be the primitive nonprincipal real character inducing $\chi$, of conductor $f\mid q$. Then $\psi(p)=\chi(p)$ for all primes $p>Y$. Choose $B$ so large that the $1-o(1)$ coefficient in \eqref{eq:concentration} exceeds $3/4$ and so that, in the notation of Proposition \ref{prop:bias}, $B^2 \ge A_{1/4}$. Then
    \[
    \frac{3}{4}\log{Z} \ge 
    \sum_{\substack{p\le Z\\\psi(p)=-1}}\frac{\log p}{p} \ge \sum_{\substack{Y<p\le Z\\\chi(p)=-1}}\frac{\log p}{p}
    = (1-o(1))\log{Z} > \frac{3}{4}\log{Z}.
    \]
    Absurd! Thus, there must be some prime $p\equiv a\pmod{q}$ with $p \le Z^3 = q^{3B^2}$. We have shown Theorem~\ref{thm:linnik} with $L=3B^2$.\qed
     
    \section{Unbreaking symmetry: Proof of Proposition \ref{prop:sym}}\label{sec:sym}
    Once we know that $Y$-rough numbers (numbers all of whose prime factors exceed $Y$) are sufficiently equidistributed in progressions, elementary divisor-sum manipulations give the symmetry formulas. To establish this latter fact, we use the following consequence of the Fundamental Lemma of the Sieve (for which see, e.g., \cite[Theorem~18.11(a)]{koubook}). Write $\rough(n)$ for the least prime factor of $n$, with $\rough(1)=\infty$, and let  
    \[ V(z):=\prod_{p\le z}(1-1/p). \]
    \begin{lemma}[Estimate for the count of rough numbers in progressions]\label{lem:sieve}
    For $(b,q)=1$, $z\ge\max(2,q)$, $t>0$, and all sufficiently large real $h$,
    \begin{equation}\label{eq:sieve}
    \#\{n\le t:n\equiv b\pmod q,\ \rough(n)>z\}
    =\frac{tV(z)}{\ph}\{1+O(\mathrm{e}^{-h})\}+O(z^{3h}).
    \end{equation}
    All constants are absolute and effective. \end{lemma}
    A proof of Lemma \ref{lem:sieve} is given in Appendix~\ref{sec:sieveproof}.
     
    Below, we shall make free use of the elementary Chebyshev--Mertens estimates
    \begin{equation*}
    \sum_{p\le t}\log p\ll t,\qquad
    \sum_{p\le t}\frac{\log p}{p}=\log t+O(1),\qquad V(t)\asymp\frac1{\log t}\quad(t\ge2).
    \end{equation*} 
    (See, e.g., \cite[Chapter~2]{ik}.)  
     
    For $(b,q)=1$, let $A_b(t)$ count the $Y$-rough integers $n\le t$ with $n\equiv b\pmod q$, and let $A(t)$ count all $Y$-rough integers $n\le t$. Applying Lemma~\ref{lem:sieve} with $h$ a sufficiently large, fixed constant, and $z = Y^{1/(6h)}$, we deduce that
    \begin{equation}\label{eq:roughupper}
    A_b(t)\ll\frac{t}{\ph\log Y},\qquad A(t)\ll\frac{t}{\log Y}\qquad(t\ge Y).
    \end{equation}
    (Here the $O(Y^{1/2})$ error term gets absorbed, since $t\ge Y=q^B$ and
    $\ph\log Y\ll Y^{1/2}$ for sufficiently large $B$. The condition $z\ge q$ required by Lemma \ref{lem:sieve} is satisfied once $B\ge 6h$, which we may assume.) 
    
    Moreover, we have the uniform distribution estimate
    \begin{equation}\label{eq:discrep}
    A_b(t)-\frac{A(t)}{\ph}\ll
    \frac{t}{\ph\log Y}\exp\left(-\frac{\log t}{6\log Y}\right)\qquad(t\ge Y).
    \end{equation}
    When $\log{t}/\log{Y}$ is sufficiently large, \eqref{eq:discrep} follows from \eqref{eq:sieve} with $z=Y$ and $h = \frac{\log{t}}{6\log{Y}}$. (The $O(t^{1/2})$ error is again easily absorbed.) When $\log{t}/\log{Y}$ is bounded, \eqref{eq:discrep} is immediate from \eqref{eq:roughupper}.
     
     
    \subsection*{The two-prime symmetry formula} We turn now to the proof of \eqref{eq:two}.
    Put
    \[
    Q_c(x)=\sum_{\substack{Y<p\le x\\p\equiv c\ (q)}}\frac{\log^2p}{p}
    +\sum_{\substack{p,r>Y,\ pr\le x\\pr\equiv c\ (q)}}\frac{\log p\log r}{pr}.
    \]
    We will prove the slightly stronger statement
    \begin{equation}\label{eq:Q}
    Q_c(x)=\frac{\log^2x+O(\log Y\log x)}{\ph}\qquad(x\ge Y).
    \end{equation}
    The extra uniformity in $x$ will be needed when establishing the three-prime formula \eqref{eq:three}.
     
    Taking inspiration from {H.\,N.} Shapiro \cite[\S10.4, pp.~417--418]{shapiro}, we start from the classical identity $\log n=\sum_{d\mid n}\Lambda(d)$. Multiplying by $\log n$ and splitting $\log n=\log d+\log(n/d)$ gives
    \begin{align*}
    \log^2 n
    &=\sum_{d\mid n}\Lambda(d)\log d
     +\sum_{d\mid n}\Lambda(d)\log(n/d)\\
    &=\sum_{d\mid n}\Lambda(d)\log d
     +\sum_{d\mid n}\Lambda(d)\sum_{v\mid n/d}\Lambda(v).
    \end{align*}
    In the double sum on $d,v$, group terms according to the value of $m=dv$; this yields
    \[
    \log^2 n=\sum_{m\mid n}\left(\Lambda(m)\log m+\sum_{uv=m}\Lambda(u)\Lambda(v)\right),
    \]
    so that by M\"obius inversion,
    \begin{equation}\label{eq:identity}
    \sum_{d\mid n}\mu(d)\log^2(n/d)=\Lambda(n)\log n+\sum_{uv=n}\Lambda(u)\Lambda(v).
    \end{equation}
     
    We use \eqref{eq:discrep} to compare the average of \eqref{eq:identity}, taken over $Y$-rough numbers in a given residue class mod $q$, with the corresponding average over unrestricted $Y$-rough numbers. First we argue that, uniformly for $v\ge1$ and $(b,q)=1$,
    \begin{equation}\label{eq:weighted}
    \sum_{\substack{m\le v,\ \rough(m)>Y\\m\equiv b\ (q)}}\frac{\log^2m}{m}
    -\frac1{\ph}\sum_{\substack{m\le v\\\rough(m)>Y}}\frac{\log^2m}{m}
    \ll\frac{\log^2Y}{\ph}.
    \end{equation}
    To prove \eqref{eq:weighted}, we note that $\frac{1}{t}\log^2{t}$ vanishes at $t=1$, so that the left-hand side is unchanged upon adding the restriction $m>Y$. For $v\le Y$, the left-hand side is zero. For $v>Y$, we evaluate by integrating $\frac{1}{t}\log^2{t}$ against $\mathrm{d}(A_b(t) - \ph^{-1} A(t))$, from $t=Y$ to $t=v$. Proceeding by parts, the $t=Y$ and $t=v$ contributions fit comfortably inside the claimed error in \eqref{eq:weighted}, while the remaining integral contributes
    \[
    \ll \frac1{\ph\log Y}\int_Y^\infty\frac{\log^2t}{t}
     \mathrm{e}^{-\log t/(6\log Y)}\,\mathrm{d}t
    =\frac{\log^2Y}{\ph}\int_1^\infty u^2\mathrm{e}^{-u/6}\,\mathrm{d}u \ll \frac{\log^2{Y}}{\ph}.
    \]
     
    Letting $d$ run over $Y$-rough numbers not exceeding $x$ (so that $(d,q)=1$), we apply \eqref{eq:weighted} with $v=x/d$ and $b\equiv cd^{-1}\pmod q$, multiply by $\mu(d)/d$, and sum on $d$. We find that
    \begin{equation}\label{eq:comparison}
    \sum_{\substack{dm\le x,\ \rough(dm)>Y\\dm\equiv c\ (q)}}\frac{\mu(d)\log^2m}{dm}
    =\frac1{\ph}\sum_{\substack{dm\le x\\\rough(dm)>Y}}\frac{\mu(d)\log^2m}{dm}
    +O\left(\frac{\log Y\log x}{\ph}\right),
    \end{equation}
    where the contributions from the right-hand side in \eqref{eq:weighted} are estimated using 
    \[ \frac{\log^2{Y}}{\ph} \sum_{\substack{d \le x \\ P^{-}(d) >Y}}\frac{1}{d} \ll \frac{\log^2{Y}}{\ph} \prod_{Y< p \le x}\left(1-\frac{1}{p}\right)^{-1} \ll \frac{\log{Y}\log{x}}{\ph}.\]
     
     
    From \eqref{eq:identity} and \eqref{eq:comparison},
    \begin{multline}\label{eq:symmetry}
    \sum_{\substack{n\le x,\ \rough(n)>Y\\n\equiv c\ (q)}}\frac{\Lambda(n)\log n}{n}
    +\sum_{\substack{uv\le x,\ \rough(uv)>Y\\uv\equiv c\ (q)}}\frac{\Lambda(u)\Lambda(v)}{uv}\\
    =\frac1{\ph}\left(
    \sum_{\substack{n\le x\\\rough(n)>Y}}\frac{\Lambda(n)\log n}{n}
    +\sum_{\substack{uv\le x\\\rough(uv)>Y}}\frac{\Lambda(u)\Lambda(v)}{uv}
    \right)
    +O\left(\frac{\log Y\log x}{\ph}\right).
    \end{multline}
    The same estimate holds if we remove the contributions to the $\Lambda$-terms from proper prime powers. Indeed, the total contribution of such terms is $\ll\log x\sum_{p>Y,\,j\ge 2} \log{p}/p^j \ll \log{x}/Y$, which fits comfortably inside the existing error.
     
    It remains to evaluate the parenthesized main term on the right-hand side of \eqref{eq:symmetry}, with $n,u,v$ restricted to primes. By partial summation and Mertens' estimate for the partial sums of $\log{p}/p$,
    \[
    \sum_{p\le x}\frac{\log^2p}{p}=\frac12\log^2x+O(\log x). 
    \]
    Furthermore,
    \[
    \begin{aligned}
    \sum_{pr\le x}\frac{\log p\log r}{pr}
    &=\sum_{p\le x}\frac{\log p}{p}
      \left\{\log\frac{x}{p}+O(1)\right\}\\
    &=\log x\sum_{p\le x}\frac{\log p}{p}
      -\sum_{p\le x}\frac{\log^2p}{p}+O(\log x)\\
    &=\frac12\log^2x+O(\log x).
    \end{aligned}
    \]
    These are almost the sums we want; we still have to impose $p,r>Y$. This is no trouble at all: Removing the primes at most $Y$ from either sum costs only $O(\log{Y}\log{x})$. This proves \eqref{eq:Q} and hence \eqref{eq:two}.
     
    \begin{rmk}[a crude Brun--Titchmarsh inequality] The two-prime symmetry formula also yields $\log{p}/p$-weighted estimates for primes in progressions 
   (cf.~\cite[\S3, eqns.~(3.4) and~(3.7)]{selberg49}). For example, forget about the (nonnegative) contribution of prime pairs and use partial summation to introduce a weight of $1/\log{t}$. This gives
    \begin{align}
    \sum_{\substack{Y<p\le Z\\p\equiv c\ (q)}}\frac{\log p}{p}\notag
    &\le\frac{Q_c(Z)}{\log Z}+\int_Y^Z\frac{Q_c(t)}{t\log^2t}\,\mathrm{d}t\notag\\
    &\le\frac{2\log Z+O(\log Y(1+\log B))}{\ph}
    =\frac{(2+o(1))\log Z}{\ph}.\label{eq:upper}
    \end{align}
    \end{rmk}
     
    \subsection*{The three-prime symmetry formula} Again, we follow Shapiro (compare the derivation of equation~(10.4.23) in \cite[\S10.4, pp.~421--422]{shapiro}; see also Exercise~7, p.~424). Let $x\ge Z$. Introducing a weight of $\log{t}$ into \eqref{eq:Q} gives
\begin{equation}\label{eq:logQ}
\sum_{\substack{Y<p\le x\\p\equiv c\ (q)}}\frac{\log^3p}{p}
    +\sum_{\substack{p,r>Y,\ pr\le x\\pr\equiv c\ (q)}}\frac{\log p\log r\log(pr)}{pr}
    =\frac{2\log^3x}{3\ph}+O\left(\frac{\log Y\log^2x}{\ph}\right).
    \end{equation}
    Now multiply \eqref{eq:Q}, in the residue class $cp^{-1} \bmod{q}$ and at $x/p$, by $\log p/p$, and sum over $Y<p\le x/Y$. We obtain
    \begin{multline}\label{eq:pQ}
    \sum_{\substack{p,r>Y,\ pr\le x\\pr\equiv c\ (q)}}\frac{\log p\log^2r}{pr}
    +\sum_{\substack{p,r,s>Y,\ prs\le x\\prs\equiv c\ (q)}}\frac{\log p\log r\log s}{prs}\\
    =\frac1{\ph}\sum_{Y<p\le x/Y}\frac{\log p}{p}\log^2(x/p)
    +O\left(\frac{\log Y\log^2x}{\ph}\right)
    =\frac{\log^3x}{3\ph}+O\left(\frac{\log Y\log^2x}{\ph}\right).
    \end{multline}
    (The final equality follows from Mertens' theorem for the partial sums of $\log{p}/p$, after introducing a weight of $\log^2(x/t)$.) Swapping $p$ and $r$ shows that twice the pair sum in \eqref{eq:pQ} is the pair sum in \eqref{eq:logQ}. We subtract twice \eqref{eq:pQ} from \eqref{eq:logQ}. The pair terms and main terms both cancel, completing the proof of \eqref{eq:three}.
     
    \appendix
    \renewcommand{\thesection}{\arabic{section}}
    \section{Proof of Proposition \ref{prop:bias}}\label{sec:determinant}
    Following van Dijk~\cite{vandijk}, we prove the following slightly more precise version of Proposition~\ref{prop:bias}.
    
    \begingroup
    \renewcommand{\thesubsection}{Step \arabic{subsection}}
    \begin{proposition}\label{prop:nosiegel}
    For every integer $t\ge3$ and every primitive real Dirichlet character $\psi$
    of conductor $f\ge 2$,
    \begin{equation}\label{eq:antic}
    \sum_{\substack{p\le x\\\psi(p)=-1}}\frac{\log p}{p}
    \le \left(\tfrac12+O(1/t)\right)\log x
    \qquad(x\ge f^{t^2}),
    \end{equation}
    with an absolute, effective implied constant.
    \end{proposition}
    
    First, a little groundwork. All implied constants below are absolute and effective.
    
    Let $t\ge 3$ be an integer, and let $x\ge f^{t^2}$, as in the
    proposition. We may assume there is a prime $p\in(8t,x]$ with
    $\psi(p)=-1$; otherwise,
    \[
    \sum_{\substack{p\le x\\\psi(p)=-1}}\frac{\log p}{p}
    \le \sum_{p\le 8t}\frac{\log p}{p}
    \ll \log t \ll \frac{\log x}{t},
    \]
    which already implies \eqref{eq:antic}. Below, we take
    \[
    L:=\max\{p\le x:\psi(p)=-1\},
    \]
    so that
    \[
    L>8t.
    \]
    
    By the classification of primitive real characters, we can identify
    $\psi$ with a Kronecker symbol: $\psi(\cdot)=\leg{d}{\cdot}$, where
    $d:=\psi(-1)f$ is a fundamental discriminant. See, for instance,
    \cite[Theorem 9.13]{MV}. In particular, $\psi(p)=-1$ for an odd
    prime $p$ precisely when $d$ is a nonsquare modulo $p$.
    
    Our proof of Proposition \ref{prop:nosiegel} proceeds in three steps:
    \begin{enumerate}
    \item Construct a matrix over $\Z[\sqrt d]$ having a nonzero minor.
    \item Show that small primes $p$ having $\psi(p)=-1$ divide this minor to large powers.
    \item Bound the absolute value of this minor under each embedding of $\Q(\sqrt d)$.
    \end{enumerate}
    If the left-hand side of \eqref{eq:antic} is too large, the size
    bounds of Step 3 will contradict the divisibility obtained in Step 2.
    
    \subsection{A matrix with a nonzero minor}
    We take our matrix to have rows indexed by the formal monomials
    $Z^rW^s$, where $r,s$ are nonnegative integers with $r+ts<L$,
    and columns indexed by integers $j,u,v$ with $0\le j\le L/t$
    and $0\le u,v\le\sqrt L$.
    Here the $(j,u,v)$-th entry of the $Z^rW^s$-th row is the $j$th
    $Z$-derivative of $Z^rW^s$ evaluated at
    \begin{equation}\label{eq:grid}
    (Z,W)=(u+v\sqrt d,u-v\sqrt d),
    \end{equation}
    that is, $\frac{r!}{(r-j)!}
    (u+v\sqrt d)^{r-j}(u-v\sqrt d)^s$ if $j\le r$, and $0$ otherwise.
    
    We let
    \begin{align*}
    N&:=\text{number of rows of our matrix},\\
    E&:=\text{sum of the $Z$-degrees of the monomials indexing the rows}.
    \end{align*}
    Suppose $p$ is an odd prime for which $\leg{d}{p}=-1$. Then working
    in $\Z[\sqrt{d}]$ mod $p$ amounts to working in the field of $p^2$
    elements. Indeed,
    \[
    \Z[\sqrt{d}]/(p)
    \simeq \Z[T]/(T^2-d,p)
    \simeq (\Z/p\Z)[T]/(T^2-d)
    \simeq \F_{p^2}.
    \]
    The argument below makes essential use of the fact, familiar to
    students of algebraic number theory, that the $p$th power map on
    $\F_{p^2}$ is induced by conjugation on $\Z[\sqrt{d}]$.
    The ``freshman's binomial theorem'' yields a down-to-earth proof:
    For all $u+v\sqrt{d}\in\Z[\sqrt{d}]$,
    \begin{equation}\label{eq:pth-power}
    (u+v\sqrt d)^p
    \equiv u^p+v^p(\sqrt d)^p
    \equiv u+v\,d^{(p-1)/2}\sqrt d
    \equiv u-v\sqrt d
    \pmod{p\Z[\sqrt d]},
    \end{equation}
    where the second step uses Fermat's little theorem and the last uses Euler's congruence
    $d^{(p-1)/2}\equiv\leg{d}{p}\pmod{p}$.
    
    Reduce the matrix modulo $L$. We claim that its rows are linearly
    independent over $\F_{L^2}$. Supposing otherwise, we choose
    coefficients $c_{r,s}\in\F_{L^2}$, not all zero, giving a zero
    linear combination of the rows. Put
    \[
    C(Z):=\sum_{r+ts<L}c_{r,s}Z^{r+Ls}\in\F_{L^2}[Z].
    \]
    Since $0\le r<L$, the exponents $r+Ls$ are distinct, and so
    $C(Z)\ne 0$.
    
    In characteristic $L$, differentiation treats $Z^{Ls}$ as a
    constant. Thus, taking the $j$th derivative of $Z^{r+Ls}$ gives
    the same result as differentiating $Z^rW^s$ $j$ times with respect
    to $Z$ and then setting $W=Z^L$. By \eqref{eq:pth-power},
    $(u+v\sqrt d)^L=u-v\sqrt d$ in $\F_{L^2}$, so the assumed linear
    dependence gives
    \[
    C^{(j)}(u+v\sqrt d)=0
    \]
    for all $0\le j\le L/t$ and all $0\le u,v\le\sqrt L$.
    Since $\lfloor L/t\rfloor<L$, the factorials $j!$ for
    $0\le j\le L/t$ are invertible in $\F_{L^2}$. It follows that
    $C$ vanishes to order at least
    $\lfloor L/t\rfloor+1>L/t$ at each of the
    $(1+\lfloor\sqrt L\rfloor)^2>L$ distinct elements $u+v\sqrt d$.
    (These are distinct because $1,\sqrt d$ are linearly independent over $\F_L$ and $0\le u,v<L$.)
    As $C\ne 0$, this forces $\deg C>L^2/t$. On the other hand,
    every exponent appearing in $C$ satisfies
    \[
    r+Ls\le \frac{L}{t}(r+ts)<L^2/t,
    \]
    so that $\deg C<L^2/t$. Contradiction.
    
    Hence, the rows are independent modulo $L$, and there is a minor
    $\Delta$ of order $N$ which is nonzero modulo $L$ and hence also
    nonzero in $\Z[\sqrt{d}]$.
    
    \subsection{Divisibility by small primes}
    Fix a prime $p$ with $t\le p\le L$ and $\psi(p)=-1$. We determine a power of $p$ dividing $\Delta$. 
    For the row indexed by $(r,s)$, put $h=\lfloor r/p\rfloor$,
    and replace its monomial $Z^rW^s$ by
    \[
    Z^{r-ph}W^s\left(\frac{Z^p-W}{p}\right)^h.
    \]
    As before, the new entries are obtained by taking $Z$-derivatives
    and evaluating at the conjugate pairs in \eqref{eq:grid}.
    
    We first check that all the new entries belong to $\Z[\sqrt d]$.
    By \eqref{eq:pth-power},
    \[
    \frac{Z^p-W}{p}\in\Z[\sqrt d]
    \qquad\text{when}\qquad
    (Z,W)=(u+v\sqrt d,u-v\sqrt d).
    \]
    Moreover, its first $Z$-derivative is $Z^{p-1}$, so all its
    positive-order $Z$-derivatives have integer coefficients.
    The product rule now shows that every $Z$-derivative of the
    replacement polynomial takes values in $\Z[\sqrt d]$ at
    these pairs, as desired.
    
    To see what these replacements do to the determinant, expand:
    \[
    Z^{r-ph}W^s\left(\frac{Z^p-W}{p}\right)^h
    =
    p^{-h}Z^rW^s+
    p^{-h}\sum_{k=1}^h(-1)^k\binom hk Z^{r-pk}W^{s+k}.
    \]
    Every monomial on the right indexes an original row. Indeed,
    $r-pk\ge0$, and
    \[
    (r-pk)+t(s+k)=r+ts-k(p-t)\le r+ts<L.
    \]
    Furthermore, every term in the sum has $Z$-degree less than $r$.
    
    Order the rows by increasing $r$, breaking ties arbitrarily,
    and make the replacements from last to first. Each replacement
    multiplies the current row by $p^{-h}$ and adds a linear
    combination of earlier, unchanged rows. Thus, on the columns
    defining our minor $\Delta$, the new determinant is
    $\Delta/p^{\sum_{r+ts<L}\lfloor r/p\rfloor}$.
    Since all its entries belong to $\Z[\sqrt d]$, so does this
    determinant. Hence $p^{\sum_{r+ts<L}\lfloor r/p\rfloor}$ divides
    $\Delta$. Since these prime powers are pairwise coprime, their product also divides $\Delta$. Thus
    \[
    D:=\prod_{\substack{t\le p\le L\\\psi(p)=-1}}
    p^{\sum_{r+ts<L}\lfloor r/p\rfloor} \qquad\text{divides}\qquad \Delta.
    \]
    
    Let us estimate the size of $D$. Since
    $\lfloor r/p\rfloor\ge r/p-1$, we have
    $\sum_{r+ts<L}\lfloor r/p\rfloor\ge \frac{E}{p}-N$,
    and so
    \begin{equation}\label{eq:divisor}
    \log D
    \ge E\sum_{\substack{t\le p\le L\\\psi(p)=-1}}\frac{\log p}{p}
    -N\sum_{p\le L}\log p.
    \end{equation}
    
    \subsection{Bounds under both embeddings}
    We begin with a few estimates for the rows of our matrix.
    Since $0\le r<L$ and $0\le s<L/t$, we have $N\ll L^2/t$.
    For a lower bound on $E$, consider the rows with
    $L/4\le r<L/2$ and $0\le s<L/(4t)$. All these pairs satisfy
    $r+ts<L$. There are $\gg L^2/t$ of them, each contributing
    at least $L/4$ to $E$. Thus $E\gg L^3/t$, and so $N\ll E/L$.
    Also, the sum of the $W$-degrees of the monomials indexing
    the rows is at most $LN/t\ll E/t$.
    
    We now bound the entries of our matrix in either embedding
    of $\Q(\sqrt d)$ into $\mathbf C$. Since $|d|=f$, the grid
    coordinates $u\pm v\sqrt{d}$ have absolute value at most
    $\sqrt L(1+\sqrt f)\le 4\sqrt{Lf}$. The entry in row $Z^rW^s$
    and column $(j,u,v)$ is zero if $j>r$; otherwise, its absolute
    value is at most
    \[
    \frac{r!}{(r-j)!}(4\sqrt{Lf})^{r+s-j}
    \le L^j(4\sqrt{Lf})^{r+s}
    \le L^{L/t}(4\sqrt{Lf})^{r+s}.
    \]
    Each term in the determinant expansion contains one entry
    from each row and each column, and there are $N!$ terms. Writing
    $\widetilde\Delta$ for the conjugate of $\Delta$, we obtain
    \[
    \max\{|\Delta|,|\widetilde\Delta|\}
    \le N!L^{LN/t}(4\sqrt{Lf})^{E+LN/t}.
    \]
    Taking logarithms, 
    \[
    \max\{\log|\Delta|,\log|\widetilde\Delta|\}
    \le \log(N!)+\frac{LN}{t}\log L
    +\left(E+\frac{LN}{t}\right)\log(4\sqrt{Lf}).
    \]
    Since $N\ll L^2/t$ and $N\ll E/L$, we have
    \[
    \log(N!)\le N\log N\ll N\log L
    \ll \frac{E\log L}{L}\ll \frac{E\log L}{t},
    \]
    and $LN/t\ll E/t$. Thus the first two terms contribute
    $O(E\log L/t)$, while the last is
    \[
    \left(E+O(E/t)\right)
    \left(\tfrac12\log L+\tfrac12\log f+\log 4\right)
    =
    \tfrac12 E\log L+
    O\!\left(E\left(\frac{\log L}{t}+\log f+1\right)\right).
    \]
    Consequently,
    \begin{equation}\label{eq:size}
    \max\{\log|\Delta|,\log|\widetilde\Delta|\}
    \le E\left\{\tfrac12\log L+
    O\!\left(\frac{\log L}{t}+\log f+1\right)\right\}.
    \end{equation}
    
    \subsection*{Wrap-up} Now for the big finish.
    We compare \eqref{eq:divisor} and \eqref{eq:size}, noting that
    $N\sum_{p\le L}\log p\ll NL\ll E$. If
    \[
    \sum_{\substack{t\le p\le L\\\psi(p)=-1}}\frac{\log p}{p}
    >\tfrac12\log L+
    C\left(\frac{\log L}{t}+\log f+1\right)
    \]
    for a sufficiently large absolute effective $C$, both conjugates
    of $\Delta/D$ have absolute value less than $1$. But $\Delta/D$ is a nonzero element of $\Z[\sqrt d]$, so its norm is a nonzero integer of absolute value less than $1$, a
    contradiction. 
    
    Adding the contribution of primes below $t$, keeping in mind the definition of $L$, we obtain
    \[
    \sum_{\substack{p\le x\\\psi(p)=-1}}\frac{\log p}{p}
    \le\tfrac12\log x+
    O\!\left(\frac{\log x}{t}+\log f+t\right).
    \]
    Since $x\ge f^{t^2}$ and $f\ge2$, both $\log f$ and $t$ are
    $O(\log x/t)$. This gives \eqref{eq:antic} and completes
    the proof of Proposition \ref{prop:nosiegel}.\hfill$\square$
       \endgroup

\begin{rmk}
The strategy may be compared with Selberg's proof of Lemma~1 in
\cite[\S4]{selberg49}, where he compares the size of a product of norms
$u^2-dv^2$ over a rectangular grid with its prime factorization. Such
products are closely connected with Vandermonde determinants on grid
points $u+v\sqrt d$. But the two arguments run in opposite directions.
Selberg bounds his product from below and observes that an odd prime $p$ 
with $\leg{d}{p}=-1$ divides $u^2-dv^2$ only when it divides both $u$
and $v$, so such primes barely show up in the factorization; the split
primes are left to pick up the slack. We instead use the Frobenius
congruence \eqref{eq:pth-power} to force the primes with $\psi(p)=-1$
to divide $\Delta$ many times over, and then let the size bound on
$\Delta$ tell us there cannot be too many of them.
\end{rmk}
    
    \section{Proof of Lemma \ref{lem:sieve}}\label{sec:sieveproof}
    We give a proof using Selberg's upper bound sieve. Although we make no claim of human originality for any part of this paper, this deserves particular emphasis here: All ingredients are standard.
     
    \begin{proposition}[Sieving progressions, \`a la Selberg]\label{prop:selberg-sieve}
    Let $q$ be a positive integer, let $P$ be a product of distinct primes, none dividing $q$, let $R\ge 1$, and put
    \[
    H:=\sum_{\substack{m\mid P\\m\le R}}\frac1{\varphi(m)}.
    \]
    Then, for every $v>0$ and integer $a$,
    \begin{equation}\label{eq:app-square}
    \#\{n\le v:n\equiv a\pmod q,\ (n,P)=1\}
    \le\frac{v}{qH}+R^2.
    \end{equation}
    \end{proposition}
    \begin{proof}
    For $d\mid P$, choose
    \[
    \rho_d:=\frac{\mu(d)d}{\varphi(d)H}
    \sum_{\substack{k\mid P\\(k,d)=1\\dk\le R}}\frac1{\varphi(k)},
    \]
    and put $\rho_d=0$ otherwise. Thus $\rho_1=1$ and $\rho_d=0$ for $d>R$. (This initially strange-seeming choice of coefficients arises naturally from a minimization problem; see \cite[\S7.1, pp.~90--92]{opera}.)
     
    If $(n,P)=1$, then $\sum_{d\mid n}\rho_d=\rho_1 = 1$. Consequently,
    \begin{align}
    \#\{n\le v:n\equiv a\pmod q,\ (n,P)=1\}
    &\le\sum_{\substack{n\le v\\n\equiv a\ (q)}}\notag
    \Bigg(\sum_{d\mid n}\rho_d\Bigg)^2\\
    &\le\frac vq\sum_{d,e\mid P}\frac{\rho_d\rho_e}{[d,e]}
    +\Bigg(\sum_{d\mid P}|\rho_d|\Bigg)^2.\label{eq:selbergupper}
    \end{align}
    In the last line, we use that $[d,e]$ is coprime to $q$, so that the number of multiples of $[d,e]$ in our progression is $v/(q[d,e])$, up to an error at most $1$.
     
    Continuing, observe that the products $jk$ with $j\mid d$, $(k,d)=1$, and $dk\le R$ are distinct divisors of $P$ at most $R$. Hence,
    \[
    H\ge\sum_{j\mid d}\frac1{\varphi(j)}
    \sum_{\substack{k\mid P\\(k,d)=1\\dk\le R}}\frac1{\varphi(k)}
    =\frac{d}{\varphi(d)}
    \sum_{\substack{k\mid P\\(k,d)=1\\dk\le R}}\frac1{\varphi(k)}.
    \]
    Comparing with the definition of $\rho_d$ shows that each $|\rho_d|\le 1$. In particular, $(\sum_{d\mid P} |\rho_d|)^2 \le R^2$. Hence, Proposition \ref{prop:selberg-sieve} will be proved once we show that the double sum over $d,e$ in \eqref{eq:selbergupper} is $1/H$.
     
     
    For $m\mid P$, expanding the definition of $\rho_d$ gives
    \[
    \sum_{\substack{d\mid P\\m\mid d}}\frac{\rho_d}{d}
    =\frac1H
    \sum_{\substack{d\mid P\\m\mid d}}
    \sum_{\substack{k\mid P\\(k,d)=1\\dk\le R}}
    \frac{\mu(d)}{\varphi(d)\varphi(k)}.
    \]
    Put $b=dk$. Since $(d,k)=1$, we have $b\mid P$ and
    $\varphi(d)\varphi(k)=\varphi(b)$. Conversely, for each $b\mid P$,
    every divisor $d$ of $b$ gives a coprime factorization $b=d(b/d)$,
    since $b$ is squarefree. Hence
    \[
    \sum_{\substack{d\mid P\\m\mid d}}\frac{\rho_d}{d}
    =\frac1H\sum_{\substack{b\mid P\\b\le R\\m\mid b}}
    \frac1{\varphi(b)}\sum_{m\mid d\mid b}\mu(d).
    \]
    Writing $d=me$, the inner sum is
    \[
    \sum_{m\mid d\mid b}\mu(d)
    =\mu(m)\sum_{e\mid b/m}\mu(e),
    \]
    which vanishes unless $b=m$, when it equals $\mu(m)$. Thus
    \[
    \sum_{\substack{d\mid P\\m\mid d}}\frac{\rho_d}{d}
    =\begin{cases}
    \displaystyle\frac{\mu(m)}{\varphi(m)H},&m\le R,\\
    0,&m>R.
    \end{cases}
    \] Using $[d,e] = de/(d,e)$ and $(d,e)=\sum_{m\mid (d,e)} \varphi(m) = \sum_{m\mid d,\,m\mid e}\varphi(m)$, we obtain
    \[
    \sum_{d,e\mid P}\frac{\rho_d\rho_e}{[d,e]}
    =\sum_{m\mid P}\varphi(m)
    \Bigg(\sum_{\substack{d\mid P\\m\mid d}}\frac{\rho_d}{d}\Bigg)^2
    =\frac1H,
    \]
    as desired.
    \end{proof}
     
     
    \subsection*{Proof of the upper bound in \texorpdfstring{\eqref{eq:sieve}}{the sieve estimate}}
    We apply Proposition \ref{prop:selberg-sieve} with
    \[ v=t, \qquad P:= \prod_{\substack{\ell \le z,\\ \ell\nmid q}} \ell, \qquad R = z^h. \] Comparing the statement of Proposition \ref{prop:selberg-sieve} with that of \eqref{eq:sieve}, it suffices to show that
    \begin{equation}\label{eq:1overHbound} \frac{1}{H} = V(z) \frac{q}{\ph} (1+O(\mathrm{e}^{-h})).\end{equation}
     
    Let $H_0$ be defined the same way as $H$ but without the requirement that $m\le R$, i.e.,
    \[
    H_0:=\sum_{m\mid P}\frac1{\varphi(m)}.
    \]
    Clearly, $H \le H_0$. The difference $H_0-H$ can be estimated with Rankin's trick: Since every prime divisor of $P$ is at most $z$, 
    \begin{align*}
    H_0-H
    &\le R^{-1/\log z}\sum_{m\mid P}\frac{m^{1/\log z}}{\varphi(m)}\\
    &=\mathrm{e}^{-\log R/\log z}H_0
    \prod_{p\mid P}\left(1+\frac{p^{1/\log z}-1}{p}\right).
    \end{align*}
    For $p\le z$, the mean value theorem gives  
    $p^{1/\log z}-1 \le \mathrm{e}\log p/\log z$, so that
    \[ \prod_{p\mid P}\left(1+\frac{p^{1/\log z}-1}{p}\right) \le \exp\left(\sum_{p\mid P}\frac{p^{1/\log z}-1}{p}\right)\le \exp\left(\frac{\mathrm{e}}{\log{z}} \sum_{p \le z}\frac{\log{p}}{p}\right) \ll 1.\]
    Hence, $H_0-H \ll H_0 \mathrm{e}^{-\log{R}/\log{z}}$, and $H = H_0 \{1+O(\mathrm{e}^{-\log{R}/\log{z}})\}$. So, once $h= \log{R}/\log{z}$ is sufficiently large,
    \[
    \frac1H=\frac{1}{H_0}\{1+O(\mathrm{e}^{-\log{R}/\log{z}})\}.
    \]
    But \[ H_0^{-1} = \prod_{p \mid P} \left(1-\frac1p\right) = \prod_{\substack{p \le z \\p\nmid q}} \left(1-\frac1p\right) = V(z) \frac{q}{\ph} \] (using in the last step that $z \ge q$), and \eqref{eq:1overHbound} follows.
     
    \subsection*{Proof of the lower bound in \texorpdfstring{\eqref{eq:sieve}}{the sieve estimate}} An integer $n\equiv b\pmod{q}$ removed by the sieve has least prime factor $p\le z$, where necessarily $p\nmid q$. Write $n=pm$, where $m\le t/p$, $m\equiv bp^{-1}\bmod{q}$, and $m$ is not divisible by any primes $\ell <p$ not dividing $q$. For each $p\le z$ with $p\nmid q$, we use Proposition \ref{prop:selberg-sieve} to bound the number of removed integers with least prime factor $p$, by taking 
    \[ v= t/p, \qquad P:=\prod_{\ell < p,~\ell \nmid q}\ell, \qquad R = z^h. \]
    (So the choice of $R$ is unchanged from before.) Write
    \[
    V_q:=\prod_{\substack{p\le z\\p\nmid q}}(1-1/p),
    \qquad
    W_p:=\prod_{\substack{\ell<p\\\ell\nmid q}}(1-1/\ell).
    \]
    Arguing as in the proof of the upper bound, we find that the number of removed integers corresponding to a given $p\le z$ is at most
    \[
    \frac{tW_p}{pq}\{1+O(\mathrm{e}^{-\log R/\log p})\}+R^2.
    \]
     
    Subtracting these counts from the total number $t/q+O(1)$ of integers in our progression yields a main term of
    \[
    \Bigg(1-\sum_{\substack{p\le z\\p\nmid q}}\frac{W_p}{p}\Bigg) \frac{t}{q}.
    \]
    The parenthesized expression on the left simplifies to $V_q$ (Buchstab's identity): Indeed, $V_q$ can be viewed as the density of integers not divisible by any prime $p\le z, p\nmid q$. The set of such integers is obtained by removing, for each $p\le z, p\nmid q$, those whose least prime factor not dividing $q$ is $p$. (This is the same observation we made above, wearing a mustache and wig.) Each such set has density $W_p/p$.
     
    We therefore obtain
    \[
    \#\{n\le t:n\equiv b\pmod q,\ \rough(n)>z\}
    \ge\frac{tV_q}{q}-O\Biggl(\frac tq\sum_{\substack{p\le z\\p\nmid q}}
    \frac{W_p}{p}\mathrm{e}^{-\log R/\log p}\Biggr)-O(zR^2).
    \]
    Since $V_q/q = V(z)/\ph$, the main term here is precisely $t V(z)/\ph$. Also, $zR^2 = z^{2h+1} \le z^{3h}$. Thus, we will have our lower bound once we check that the sum in the first $O$-error is $\ll \mathrm{e}^{-h}V_q$.
     
    Uniformly for primes $p\le z$, we have $W_p/V_q =\prod_{\substack{p\le\ell\le z,\,\ell\nmid q}}(1-1/\ell)^{-1}\ll\log{z}/\log{p}$. Put $u=\log z/\log p\ge1$. For $h\ge2$, the function $u^2\mathrm{e}^{-hu}$ is decreasing on $[1,\infty)$, so $u^2\mathrm{e}^{-hu}\le \mathrm{e}^{-h}$. Since $\log R=h\log z$, 
    \[
    \sum_{\substack{p\le z\\p\nmid q}}\frac{W_p}{pV_q}
     \mathrm{e}^{-\log R/\log p} \ll \sum_{\substack{p\le z\\p\nmid q}}\frac{1}{p}\frac{\log{z}}{\log{p}} \mathrm{e}^{-\log{R}/\log{p}} 
    \le\frac{\mathrm{e}^{-h}}{\log z}\sum_{p\le z}\frac{\log p}{p}
    \ll \mathrm{e}^{-h}. 
    \]
    This finishes the proof of Lemma~\ref{lem:sieve}.\qed
     
     
     
    \begin{thebibliography}{99}
    \bibitem{banks} {W.\,D.} Banks, \emph{On the OpenAI proof that Landau--Siegel zeros do not exist}, 2026, \href{https://arxiv.org/abs/2610.15483}{arXiv:2610.15483}.
    \bibitem{barreto} K. Barreto, \emph{An elementary proof of the non-existence of Landau--Siegel zeros}, manuscript, cited in \cite{vandijk}.
    \bibitem{elliott} {P.\,D.\,T.\,A.} Elliott, \emph{Multiplicative functions on arithmetic progressions. VII. Large moduli}, J. London Math. Soc. (2) \textbf{66} (2002), 14--28.
    \bibitem{elliott2} \bysame, \emph{The least prime primitive root and Linnik's theorem}, Number Theory for the Millennium, I, A K Peters, Natick, MA, 2002, 393--418.
    \bibitem{fried} {J.\,B.} Friedlander, \emph{Selberg's formula and Siegel's zero}, Recent Progress in Analytic Number Theory, Vol.~1 (H. Halberstam and C. Hooley, eds.), Academic Press, London--New York, 1981, 15--23.
    \bibitem{opera} J. Friedlander and H. Iwaniec, \emph{Opera de Cribro}, Amer. Math. Soc. Colloq. Publ., vol.~57, American Mathematical Society, Providence, RI, 2010.
    \bibitem{fi23} \bysame, \emph{Sifting for small primes from an arithmetic progression}, Sci. China Math. \textbf{66} (2023), 2715--2730; \href{https://arxiv.org/abs/2303.06122}{arXiv:2303.06122}.
    \bibitem{fiirr} \bysame, \emph{Selberg's sieve of irregular density}, Acta Arith. \textbf{209} (2023), 385--396.
     
    \bibitem{granville92}
    A. Granville, \emph{On elementary proofs of the prime number theorem
    for arithmetic progressions, without characters},
    Proceedings of the Amalfi Conference on Analytic Number Theory
    (Maiori, 1989), Universit\`a di Salerno, Salerno, 1992, 157--194.
    \bibitem{granville} \bysame, \emph{Different approaches to the distribution of primes}, Milan J. Math. \textbf{78} (2010), 65--84; \href{https://dms.umontreal.ca/~andrew/PDF/ItalySurvey.pdf}{author's version}.
    \bibitem{green} B. Green, \emph{On Landau--Siegel zeros}, 2026, \href{https://hexagonmath.org/pdf/2610.00311v2}{hexagon:2610.00311v2}.
    \bibitem{ik} H. Iwaniec and E. Kowalski, \emph{Analytic Number Theory}, Amer. Math. Soc. Colloq. Publ., vol.~53, American Mathematical Society, Providence, RI, 2004.
    \bibitem{kerr} B. Kerr, \emph{A simpler proof that there are no Landau--Siegel zeros}, 2026, \href{https://arxiv.org/abs/2610.21099v1}{arXiv:2610.21099v1}.
    \bibitem{kou} D. Koukoulopoulos, \emph{Pretentious multiplicative functions and the prime number theorem for arithmetic progressions}, Compos. Math. \textbf{149} (2013), 1129--1149.
    \bibitem{koubook} \bysame, \emph{The Distribution of Prime Numbers}, Grad. Stud. Math., vol.~203, American Mathematical Society, Providence, RI, 2019.
    \bibitem{linnik1} {U.\,V.} Linnik, \emph{On the least prime in an arithmetic progression. I. The basic theorem}, Rec. Math. [Mat. Sbornik] N.S. \textbf{15(57)} (1944), no.~2, 139--178.
    \bibitem{linnik2} \bysame, \emph{On the least prime in an arithmetic progression. II. The Deuring--Heilbronn phenomenon}, Rec. Math. [Mat. Sbornik] N.S. \textbf{15(57)} (1944), no.~3, 347--368.
    \bibitem{mmt} K. Matom\"aki, J. Merikoski, and J. Ter\"av\"ainen, \emph{Primes in arithmetic progressions and short intervals without $L$-functions}, 2024, \href{https://arxiv.org/abs/2401.17570}{arXiv:2401.17570}.
    \bibitem{MV}
    {H.\,L.} Montgomery and {R.\,C.} Vaughan,
    \emph{Multiplicative Number Theory I. Classical Theory},
    Cambridge Studies in Advanced Mathematics, vol.~97,
    Cambridge University Press, Cambridge, 2007.
    \bibitem{openai} OpenAI, \emph{Uniform exclusion of Landau--Siegel zeros}, OpenAI Math Release, October 1, 2026, \href{https://github.com/openai/math/blob/main/preprints/Uniform-exclusion-of-Landau-Siegel-zeros-October-1-2026/paper.pdf}{online preprint}.
    \bibitem{sach} S. Sachpazis, \emph{A pretentious proof of Linnik's estimate for primes in arithmetic progressions}, Mathematika \textbf{69} (2023), no.~3, 879--902; \href{https://doi.org/10.1112/mtk.12211}{doi:10.1112/mtk.12211}.
    \bibitem{selberg49} A. Selberg, \emph{An elementary proof of Dirichlet's theorem about primes in an arithmetic progression}, Ann. of Math. (2) \textbf{50} (1949), 297--304.
     
    \bibitem{selberg} \bysame, \emph{An elementary proof of the prime number theorem for arithmetic progressions}, Canad. J. Math. \textbf{2} (1950), 66--78.
    \bibitem{shapiro} {H.\,N.} Shapiro, \emph{Introduction to the Theory of Numbers}, Wiley, New York, 1983.
    \bibitem{tao} T. Tao, \emph{A sketch of the proof of non-existence of Siegel zeroes}, What's new, October 19, 2026, \href{https://terrytao.wordpress.com/2026/10/19/a-sketch-of-the-proof-of-non-existence-of-siegel-zeroes/}{online exposition}.
    \bibitem{vandijk} R. van Dijk, \emph{A Frobenius determinant proof of the non-existence of Landau--Siegel zeros}, 2026, \href{https://hexagonmath.org/pdf/2610.00409v2}{hexagon:2610.00409v2}.
    \end{thebibliography}
    \end{document}