betaFeedback

WorksMathematics

The missing Lin(ni)k

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.

Introduction

The purpose of this note is to give a simple proof of a celebrated 1944 theorem of Linnik [16, 17].

Theorem 1. There is an absolute, effectively computable constant LL such that, for every q≥2q \ge2 and every aa coprime to qq, some prime p≡a(modq)p \equiv a \pmod{q} satisfies p≤qLp \le q^{L}.

The traditional proofs of Theorem 1 go through zero-free regions, log-free zero-density estimates, and zero-repulsion phenomena; see, e.g., Iwaniec–Kowalski [12 Chapter 18]. Beginning with work of Elliott [3, 4], 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 [15 Chapter 27] (cf. [14, 21]), Friedlander and Iwaniec [6, 7, 8], and Matomäki, Merikoski, and Teräväinen [18]. Our new proof of Linnik’s theorem is short, elementary (no zeros of LL-functions were harmed in the course of the argument), and “unpretentious.”

This argument comes out of recent breakthrough work announced by OpenAI [20]. Specifically, we need the following arithmetic encoding of the nonexistence of Siegel zeros.

Proposition 2 (Anti-concentration on ψ=−1\psi=-1). For every ε>0\varepsilon>0 there is an effectively computable AεA_{\varepsilon} such that, for every primitive nonprincipal real character ψ\psi of conductor ff,

∑p≤xψ(p)=−1log⁡pp≤(12+ε)log⁡x(x≥fAε).\sum_{\substack{p \le x \\ \psi(p)=-1}} \frac{\log p}{p} \le\left(\frac{1}{2}+\varepsilon\right)\log x \qquad(x \ge f^{A_{\varepsilon}}).

For many decades, Proposition 2 was thought to lie very deep. However, Green [11] has recently propounded a proof of (a slightly stronger version of) Proposition 2 that fits in under 5 pages.1 A technically simpler approach, using only undergraduate mathematics, has been presented by van Dijk [26]. We include a version of his argument in Appendix 1. See also Banks [1], Barreto [2], Kerr [13], and Tao [25].

In addition to Proposition 2, we require certain variants of Selberg’s symmetry formula [22]. Let BB be a sufficiently large integer, and put

Y:=qB,Z:=qB2.Y := q^{B}, \qquad Z := q^{B^{2}}.

2020 Mathematics Subject Classification. Primary 11N13; Secondary 11N36.

Key words and phrases. Linnik’s theorem, least prime in an arithmetic progression, Selberg’s symmetry formula, sieve methods, Landau–Siegel zeros.

Below, o(1)o(1) indicates a quantity that tends (effectively!) to zero as B→∞B \to\infty, uniformly in q≥2q \ge2 and in the choice of reduced residue class. In sums and products, pp, rr, ss, ℓ\ell denote primes unless otherwise indicated.

Proposition 3 (Two- and three-prime symmetry formulas). Uniformly for (c,q)=1(c,q)=1 and x≥Zx \ge Z,

∑Y<p≤xp≡c (q)log⁡2pp+∑p,r>Y, pr≤xpr≡c (q)log⁡plog⁡rpr=(1+o(1))log⁡2xφ(q).(1)\sum_{\substack{Y<p\le x\\ p\equiv c\ (q)}} \frac{\log^2 p}{p} +\sum_{\substack{p,r>Y,\ pr\le x\\ pr\equiv c\ (q)}} \frac{\log p\log r}{pr} =\frac{(1+o(1))\log^2 x}{\varphi(q)}. \tag*{(1)}
2∑p,r,s>Y, prs≤xprs≡c (q)log⁡plog⁡rlog⁡sprs=∑Y<p≤xp≡c (q)log⁡3pp+o(log⁡3xφ(q)).(2)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^3 p}{p} +o\left(\frac{\log^3 x}{\varphi(q)}\right). \tag*{(2)}

For fixed modulus, corresponding formulas without the restrictions pp, rr, s>Ys>Y appear in Selberg [22 (3.4) and (3.6)]. A related uniform two-prime symmetry formula was given by Friedlander [5, §2]. To keep the paper reasonably self-contained, we prove both formulas (1) and (2) in § 3 below.

The overarching strategy of the proof goes back to Selberg [22, §§5–6] (see also [23 §3]): 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 [9] and [10 §2].) 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 [22], this is his Lemma 1, while in ours, it is Proposition 2. Selberg’s regime of uniformity is different from ours (the paper [22] considers only fixed qq) but the philosophy is the same!

Use of Super Intelligence

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 https://github.com/twonth/missing-linnik-lean. The formalized results use only Lean’s standard axioms of propositional extensionality (propext), classical choice (Classical.choice), and quotient soundness (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.

Not from concentrate: Proof of Theorem 1 modulo the symmetry formulas

The case q=2q=2 is immediate, so assume q≥3q \ge3. We suppose that there is no prime p≤Z3p \le Z^3 with p≡a(modq)p \equiv a \pmod q and derive a contradiction once BB is sufficiently large.

For each character χ\chi modulo qq, put

bχ=1log⁡Z∑Y<p≤Zχ(p)log⁡pp;b_\chi=\frac{1}{\log Z}\sum_{Y<p\le Z}\frac{\chi(p)\log p}{p};

ends_mid=1 this is essentially a weighted average of χ\chi along the primes in (Y,Z](Y,Z]. Note that by the choice of YY, every prime pp appearing in the sum is larger than qq, and so each χ(p)≠0\chi(p) \ne0. We have

bχ0=1+o(1),∣bχ∣≤bχ0.b_{\chi_0}=1+o(1), \qquad|b_\chi|\le b_{\chi_0}.

Here is how the proof will go. Using the three-prime symmetry formula, we show that a residue class containing no small primes forces ∑χ≠χ0∣bχ∣3\sum_{\chi\ne\chi_0}|b_\chi|^3 to be large. Comparing this with the bound for ∑χ≠χ0∣bχ∣2\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χ=±(1+o(1))b_\chi=\pm(1+o(1)). The two-prime symmetry formula rules out the plus sign, forcing bχ=−(1+o(1))b_\chi=-(1+o(1)), contrary to the anti-concentration estimate of Proposition 2.

Down to business. Apply the three-prime symmetry formula (2) with c=ac=a and x=Z3x=Z^3. On the one hand, our assumption that there are no small primes aa mod qq implies that the single-prime sum there vanishes, so that

∑p,r,s>Y, prs≤Z3prs≡a (q)log⁡plog⁡rlog⁡sprs=o(log⁡3Zφ(q)).\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}{\varphi(q)}\right).

On the other hand, orthogonality gives

∑χmodqχ(a)‾bχ3=1log⁡3Z∑Y<p,r,s≤Zlog⁡plog⁡rlog⁡sprs∑χmodqχ(a)‾χ(prs)=φ(q)log⁡3Z∑Y<p,r,s≤Zprs≡a (q)log⁡plog⁡rlog⁡sprs≤φ(q)log⁡3Z∑p,r,s>Y, prs≤Z3prs≡a (q)log⁡plog⁡rlog⁡sprs.\begin{aligned} \sum_{\chi\mathbin{\mathrm{mod}} q}\overline{\chi(a)}b_\chi^3 =\frac{1}{\log^3 Z}\sum_{Y<p,r,s\le Z}\frac{\log p\log r\log s}{prs}\sum_{\chi\mathbin{\mathrm{mod}} q}\overline{\chi(a)}\chi(prs) \\ &=\frac{\varphi(q)}{\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{\varphi(q)}{\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{aligned}

The middle expression is nonnegative, so

∑χmodqχ(a)‾bχ3=o(1).\sum_{\chi\mathbin{\mathrm{mod}} q}\overline{\chi(a)}b_\chi^3=o(1).

By the reverse triangle inequality,

∑χ≠χ0∣bχ∣3≥1−o(1).(3)\sum_{\chi\ne\chi_0}|b_\chi|^3\ge1-o(1). \tag*{(3)}

We compare (3) with what comes out of Parseval’s formula. Setting wc:=1log⁡Z∑Y<p≤Zp≡c (q)log⁡ppw_c:=\frac{1}{\log Z}\sum_{\substack{Y<p\le Z\\p\equiv c\ (q)}}\frac{\log p}{p},

∑χ∣bχ∣2=φ(q)∑(c,q)=1wc2≤(2+o(1))∑(c,q)=1wc=(2+o(1))bχ0,\sum_\chi|b_\chi|^2=\varphi(q)\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 (14)). Hence E:=∑χ≠χ0∣bχ∣2≤1+o(1)E:=\sum_{\chi\ne\chi_0}|b_\chi|^2\le1+o(1). But

1−o(1)≤∑χ≠χ0∣bχ∣3≤(max⁡χ≠χ0∣bχ∣)E.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χ∣=1+o(1)|b_\chi|=1+o(1) for some nonprincipal χ\chi. Moreover, χ\chi must be real: Otherwise E≥∣bχ∣2+∣bχ‾∣2=2∣bχ∣2≥2−o(1)E\ge|b_\chi|^2+|b_{\overline{\chi}}|^2=2|b_\chi|^2\ge2-o(1).

There are two possibilities: Either bχ=−1+o(1)b_\chi=-1+o(1) or bχ=1+o(1)b_\chi=1+o(1). We now rule out the latter. Since exactly half the reduced residue classes satisfy χ(c)=−1\chi(c)=-1, the two-prime symmetry formula (1) implies that

∑Y<p≤Zχ(p)=−1log⁡2pp+∑p,r>Ypr≤Zχ(pr)=−1log⁡plog⁡rpr=(12+o(1))log⁡2Z.(4)\sum_{\substack{Y<p\le Z\\ \chi(p)=-1}} \frac{\log^2 p}{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. \tag*{(4)}

If bχ=1+o(1)b_\chi=1+o(1), then

M−:=∑Y<p≤Zχ(p)=−1log⁡pp=bχ0−bχ2log⁡Z=o(log⁡Z).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 (4) is at most M−log⁡Z+2M−∑Y<r≤Zlog⁡rr=o(log⁡2Z)M_-\log Z+2M_-\sum_{Y<r\le Z}\frac{\log r}{r}=o(\log^2 Z), contradicting (4) for large BB. We use here that χ(pr)=−1\chi(pr)=-1 implies χ(p)=−1\chi(p)=-1 or χ(r)=−1\chi(r)=-1.

We conclude that bχ=−1+o(1)b_\chi=-1+o(1), and therefore

∑Y<p≤Zχ(p)=−1log⁡pp=(1−o(1))log⁡Z.(5)\sum_{\substack{Y<p\le Z\\ \chi(p)=-1}}\frac{\log p}{p}=(1-o(1))\log Z. \tag*{(5)}

Let ψ\psi be the primitive nonprincipal real character inducing χ\chi, of conductor f∣qf\mid q. Then ψ(p)=χ(p)\psi(p)=\chi(p) for all primes p>Yp>Y. Choose BB so large that the 1−o(1)1-o(1) coefficient in (5) exceeds 3/43/4 and so that, in the notation of Proposition 2, B2≥A1/4B^2\ge A_{1/4}. Then

34log⁡Z≥∑p≤Zψ(p)=−1log⁡pp≥∑Y<p≤Zχ(p)=−1log⁡pp=(1−o(1))log⁡Z>34log⁡Z.\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≡a(modq)p\equiv a\pmod q with p≤Z3=q3B2p\le Z^3=q^{3B^2}. We have shown Theorem 1 with L=3B2L=3B^2. □

Unbreaking symmetry: Proof of Proposition 3

Once we know that YY-rough numbers (numbers all of whose prime factors exceed YY) 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., [15 Theorem 18.11(a)]). Write P−(n)P^-(n) for the least prime factor of nn, with P−(1)=∞P^-(1)=\infty, and let

V(z):=∏p≤z(1−1/p).V(z):=\prod_{p\le z}(1-1/p).

Lemma 4 (Estimate for the count of rough numbers in progressions). For (b,q)=1(b,q)=1, z≥max⁡(2,q)z\ge\max(2,q), t>0t>0, and all sufficiently large real hh,

#{n≤t:n≡b(modq), P−(n)>z}=tV(z)φ(q){1+O(e−h)}+O(z3h).(6)\#\{n\le t:n\equiv b\pmod q,\ P^-(n)>z\}=\frac{tV(z)}{\varphi(q)}\{1+O(e^{-h})\}+O(z^{3h}). \tag*{(6)}

All constants are absolute and effective.

A proof of Lemma 4 is given in Appendix § 2.

Below, we shall make free use of the elementary Chebyshev–Mertens estimates

∑p≤tlog⁡p≪t,∑p≤tlog⁡pp=log⁡t+O(1),V(t)≍1log⁡t(t≥2).\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\frac{1}{\log t}\quad(t\ge2).

(See, e.g., [12 Chapter 2].)

For (b,q)=1(b,q)=1, let Ab(t)A_b(t) count the YY-rough integers n≤tn\le t with n≡b(modq)n\equiv b\pmod q, and let A(t)A(t) count all YY-rough integers n≤tn\le t. Applying Lemma 4 with hh a sufficiently large, fixed constant, and z=Y1/(6h)z=Y^{1/(6h)}, we deduce that

Ab(t)≪tφ(q)log⁡Y,A(t)≪tlog⁡Y(t≥Y).(7)A_b(t)\ll\frac{t}{\varphi(q)\log Y},\qquad A(t)\ll\frac{t}{\log Y}\quad(t\ge Y). \tag*{(7)}

(Here the O(Y1/2)O(Y^{1/2}) error term gets absorbed, since t≥Y=qBt\ge Y=q^B and φ(q)log⁡Y≪Y1/2\varphi(q)\log Y\ll Y^{1/2} for sufficiently large BB. The condition z≥qz\ge q required by Lemma 4 is satisfied once B≥6hB\ge6h, which we may assume.)

Moreover, we have the uniform distribution estimate

Ab(t)−A(t)φ(q)≪tφ(q)log⁡Yexp⁡(−log⁡t6log⁡Y)(t≥Y).(8)A_b(t)-\frac{A(t)}{\varphi(q)}\ll\frac{t}{\varphi(q)\log Y}\exp\left(-\frac{\log t}{6\log Y}\right)\quad(t\ge Y). \tag*{(8)}

When log⁡t/log⁡Y\log t/\log Y is sufficiently large, (8) follows from (6) with z=Yz=Y and h=log⁡t6log⁡Yh=\frac{\log t}{6\log Y}. (The O(t1/2)O(t^{1/2}) error is again easily absorbed.) When log⁡t/log⁡Y\log t/\log Y is bounded, (8) is immediate from (7).

The two-prime symmetry formula

We turn now to the proof of (1). Put

Qc(x)=∑Y<p≤xp≡c (q)log⁡2pp+∑p,r>Y, pr≤xpr≡c (q)log⁡plog⁡rpr.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

Qc(x)=log⁡2x+O(log⁡Ylog⁡x)φ(q)(x≥Y).(9)Q_c(x)=\frac{\log^2x+O(\log Y\log x)}{\varphi(q)}\quad(x\ge Y). \tag*{(9)}

The extra uniformity in xx will be needed when establishing the three-prime formula (2).

Taking inspiration from H. N. Shapiro [24 §10.4, pp. 417–418], we start from the classical identity log⁡n=∑d∣nΛ(d)\log n=\sum_{d\mid n}\Lambda(d). Multiplying by log⁡n\log n and splitting log⁡n=log⁡d+log⁡(n/d)\log n=\log d+\log(n/d) gives

log⁡2n=∑d∣nΛ(d)log⁡d+∑d∣nΛ(d)log⁡(n/d)=∑d∣nΛ(d)log⁡d+∑d∣nΛ(d)∑v∣n/dΛ(v).\begin{aligned} \log^2n=\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{aligned}

In the double sum on d,vd,v, group terms according to the value of m=dvm=dv; this yields

log⁡2n=∑m∣n(Λ(m)log⁡m+∑uv=mΛ(u)Λ(v)),\log^2n=\sum_{m\mid n}\left(\Lambda(m)\log m+\sum_{uv=m}\Lambda(u)\Lambda(v)\right),

so that by Möbius inversion,

∑d∣nμ(d)log⁡2(n/d)=Λ(n)log⁡n+∑uv=nΛ(u)Λ(v).(10)\sum_{d\mid n}\mu(d)\log^2(n/d)=\Lambda(n)\log n+\sum_{uv=n}\Lambda(u)\Lambda(v). \tag*{(10)}

We use (8) to compare the average of (10), taken over YY-rough numbers in a given residue class mod qq, with the corresponding average over unrestricted YY-rough numbers. First we argue that, uniformly for v≥1v \ge1 and (b,q)=1(b,q)=1,

∑m≤v, P−(m)>Ym≡b (q)log⁡2mm−1φ(q)∑m≤vP−(m)>Ylog⁡2mm≪log⁡2Yφ(q).(11)\sum_{\substack{m\le v,\ P^{-}(m)>Y\\m\equiv b\ (q)}}\frac{\log^{2}m}{m}-\frac{1}{\varphi(q)}\sum_{\substack{m\le v\\P^{-}(m)>Y}}\frac{\log^{2}m}{m}\ll\frac{\log^{2}Y}{\varphi(q)}. \tag*{(11)}

To prove (11), we note that 1tlog⁡2t\frac{1}{t}\log^{2}t vanishes at t=1t=1, so that the left-hand side is unchanged upon adding the restriction m>Ym>Y. For v≤Yv\le Y, the left-hand side is zero. For v>Yv>Y, we evaluate by integrating 1tlog⁡2t\frac{1}{t}\log^{2}t against d(Ab(t)−φ(q)−1A(t))d(A_b(t)-\varphi(q)^{-1}A(t)), from t=Yt=Y to t=vt=v. Proceeding by parts, the t=Yt=Y and t=vt=v contributions fit comfortably inside the claimed error in (11), while the remaining integral contributes

≪1φ(q)log⁡Y∫Y∞log⁡2tte−log⁡t/(6log⁡Y) dt=log⁡2Yφ(q)∫1∞u2e−u/6 du≪log⁡2Yφ(q).\ll\frac{1}{\varphi(q)\log Y}\int_Y^\infty\frac{\log^{2}t}{t}e^{-\log t/(6\log Y)}\,dt=\frac{\log^{2}Y}{\varphi(q)}\int_1^\infty u^2e^{-u/6}\,du\ll\frac{\log^{2}Y}{\varphi(q)}.

Letting dd run over YY-rough numbers not exceeding xx (so that (d,q)=1(d,q)=1), we apply (11) with v=x/dv=x/d and b≡cd−1(modq)b\equiv cd^{-1}\pmod q, multiply by μ(d)/d\mu(d)/d, and sum on dd. We find that

∑dm≤x, P−(dm)>Ydm≡c (q)μ(d)log⁡2mdm=1φ(q)∑dm≤xP−(dm)>Yμ(d)log⁡2mdm+O(log⁡Ylog⁡xφ(q)).(12)\sum_{\substack{dm\le x,\ P^{-}(dm)>Y\\dm\equiv c\ (q)}}\frac{\mu(d)\log^{2}m}{dm} =\frac{1}{\varphi(q)}\sum_{\substack{dm\le x\\P^{-}(dm)>Y}}\frac{\mu(d)\log^{2}m}{dm} +O\left(\frac{\log Y\log x}{\varphi(q)}\right). \tag*{(12)}

where the contributions from the right-hand side in (11) are estimated using

log⁡2Yφ(q)∑d≤xP−(d)>Y1d≪log⁡2Yφ(q)∏Y<p≤x(1−1p)−1≪log⁡Ylog⁡xφ(q).\frac{\log^{2}Y}{\varphi(q)}\sum_{\substack{d\le x\\P^{-}(d)>Y}}\frac{1}{d} \ll\frac{\log^{2}Y}{\varphi(q)}\prod_{Y<p\le x}\left(1-\frac{1}{p}\right)^{-1} \ll\frac{\log Y\log x}{\varphi(q)}.

From (10) and (12),

∑n≤x, P−(n)>Yn≡c (q)Λ(n)log⁡nn+∑uv≤x, P−(uv)>Yuv≡c (q)Λ(u)Λ(v)uv=1φ(q)(∑n≤xP−(n)>YΛ(n)log⁡nn+∑uv≤xP−(uv)>YΛ(u)Λ(v)uv)+O(log⁡Ylog⁡xφ(q)).(13)\begin{aligned} \sum_{\substack{n\le x,\ P^{-}(n)>Y\\n\equiv c\ (q)}}\frac{\Lambda(n)\log n}{n} &+\sum_{\substack{uv\le x,\ P^{-}(uv)>Y\\uv\equiv c\ (q)}}\frac{\Lambda(u)\Lambda(v)}{uv}\\ &=\frac{1}{\varphi(q)}\left(\sum_{\substack{n\le x\\P^{-}(n)>Y}}\frac{\Lambda(n)\log n}{n} +\sum_{\substack{uv\le x\\P^{-}(uv)>Y}}\frac{\Lambda(u)\Lambda(v)}{uv}\right) +O\left(\frac{\log Y\log x}{\varphi(q)}\right). \tag*{(13)} \end{aligned}

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 ≪log⁡x∑p>Y, j≥2log⁡p/pj≪log⁡x/Y\ll\log x\sum_{p>Y,\ j\ge2}\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 (13), with n,u,vn,u,v restricted to primes. By partial summation and Mertens’ estimate for the partial sums of log⁡p/p\log p/p,

∑p≤xlog⁡2pp=12log⁡2x+O(log⁡x).\sum_{p\le x}\frac{\log^{2}p}{p}=\frac{1}{2}\log^{2}x+O(\log x).

Furthermore,

∑pr≤xlog⁡plog⁡rpr=∑p≤xlog⁡pp{log⁡xp+O(1)}=log⁡x∑p≤xlog⁡pp−∑p≤xlog⁡2pp+O(log⁡x)=12log⁡2x+O(log⁡x).\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^2 p}{p} + O(\log x) \\ &= \frac{1}{2}\log^2 x+O(\log x). \end{aligned}

These are almost the sums we want; we still have to impose p,r>Yp,r>Y. This is no trouble at all: Removing the primes at most YY from either sum costs only O(log⁡Ylog⁡x)O(\log Y\log x). This proves (9) and hence (1).

Remark 5 (a crude Brun–Titchmarsh inequality). The two-prime symmetry formula also yields log⁡p/p\log p/p-weighted estimates for primes in progressions (cf. [22 §3, eqns. (3.4) and (3.7)]). For example, forget about the (nonnegative) contribution of prime pairs and use partial summation to introduce a weight of 1/log⁡t1/\log t. This gives

∑Y<p≤Zp≡c (q)log⁡pp≤Qc(Z)log⁡Z+∫YZQc(t)tlog⁡2t dt\sum_{\substack{Y<p\le Z\\p\equiv c\ (q)}}\frac{\log p}{p} \le \frac{Q_c(Z)}{\log Z} + \int_Y^Z\frac{Q_c(t)}{t\log^2 t}\,\mathrm{d}t
{#eq:14} \le \frac{2\log Z+O(\log Y(1+\log B))}{\varphi(q)} = \frac{(2+o(1))\log Z}{\varphi(q)}.

The three-prime symmetry formula

Again, we follow Shapiro (compare the derivation of equation (10.4.23) in [24 §10.4, pp. 421–422]; see also Exercise 7, p. 424). Let x≥Zx\ge Z. Introducing a weight of log⁡t\log t into (9) gives

∑Y<p≤xp≡c (q)log⁡3pp+∑p,r>Y, pr≤xpr≡c (q)log⁡plog⁡rlog⁡(pr)pr=2log⁡3x3φ(q)+O(log⁡Ylog⁡2xφ(q)).(14)\sum_{\substack{Y<p\le x\\p\equiv c\ (q)}}\frac{\log^3 p}{p} + \sum_{\substack{p,r>Y,\ pr\le x\\pr\equiv c\ (q)}}\frac{\log p\log r\log(pr)}{pr} = \frac{2\log^3 x}{3\varphi(q)} + O\left(\frac{\log Y\log^2 x}{\varphi(q)}\right). \tag*{(14)}

Now multiply (9), in the residue class cp−1 mod qcp^{-1}\bmod q and at x/px/p, by log⁡p/p\log p/p, and sum over Y<p≤x/YY<p\le x/Y. We obtain

∑p,r>Y, pr≤xpr≡c (q)log⁡plog⁡2rpr+∑p,r,s>Y, prs≤xprs≡c (q)log⁡plog⁡rlog⁡sprs=1φ(q)∑Y<p≤x/Ylog⁡pplog⁡2(x/p)+O(log⁡Ylog⁡2xφ(q))=log⁡3x3φ(q)+O(log⁡Ylog⁡2xφ(q)).(15)\begin{aligned} \sum_{\substack{p,r>Y,\ pr\le x\\pr\equiv c\ (q)}}\frac{\log p\log^2 r}{pr} + \sum_{\substack{p,r,s>Y,\ prs\le x\\prs\equiv c\ (q)}}\frac{\log p\log r\log s}{prs} \\ &= \frac{1}{\varphi(q)} \sum_{Y<p\le x/Y}\frac{\log p}{p}\log^2(x/p) + O\left(\frac{\log Y\log^2 x}{\varphi(q)}\right) = \frac{\log^3 x}{3\varphi(q)} + O\left(\frac{\log Y\log^2 x}{\varphi(q)}\right). \tag*{(15)} \end{aligned}

(The final equality follows from Mertens’ theorem for the partial sums of log⁡p/p\log p/p, after introducing a weight of log⁡2(x/t)\log^2(x/t). Swapping pp and rr shows that twice the pair sum in (15) is the pair sum in (14). We subtract twice (15) from (14). The pair terms and main terms both cancel, completing the proof of (2).

Proof of Proposition 2

Following van Dijk [26], we prove the following slightly more precise version of Proposition 2.

Proposition 6. For every integer t≥3t \ge3 and every primitive real Dirichlet character ψ\psi of conductor f≥2f \ge2,

∑p≤xψ(p)=−1log⁡pp≤(12+O(1/t))log⁡x(x≥ft2),(16)\sum_{\substack{p \le x \\ \psi(p)=-1}} \frac{\log p}{p} \le\left(\frac{1}{2}+O(1/t)\right)\log x \qquad(x \ge f^{t^2}), \tag*{(16)}

with an absolute, effective implied constant.

First, a little groundwork. All implied constants below are absolute and effective.

Let t≥3t \ge3 be an integer, and let x≥ft2x \ge f^{t^2}, as in the proposition. We may assume there is a prime p∈(8t,x]p \in(8t,x] with ψ(p)=−1\psi(p)=-1; otherwise,

∑p≤xψ(p)=−1log⁡pp≤∑p≤8tlog⁡pp≪log⁡t≪log⁡xt,\sum_{\substack{p \le x \\ \psi(p)=-1}} \frac{\log p}{p} \le\sum_{p \le8t} \frac{\log p}{p} \ll\log t \ll\frac{\log x}{t},

which already implies (16). Below, we take

L:=max⁡{p≤x:ψ(p)=−1},L := \max\{p \le x:\psi(p)=-1\},

so that

L>8t.L>8t.

By the classification of primitive real characters, we can identify ψ\psi with a Kronecker symbol: ψ(⋅)=(d⋅)\psi(\cdot)=\left(\frac{d}{\cdot}\right), where d:=ψ(−1)fd:=\psi(-1)f is a fundamental discriminant. See, for instance, [19 Theorem 9.13]. In particular, ψ(p)=−1\psi(p)=-1 for an odd prime pp precisely when dd is a nonsquare modulo pp.

Our proof of Proposition 6 proceeds in three steps:

  1. Construct a matrix over Z[d]\mathbb{Z}[\sqrt{d}] having a nonzero minor.

  2. Show that small primes pp having ψ(p)=−1\psi(p)=-1 divide this minor to large powers.

  3. Bound the absolute value of this minor under each embedding of Q(d)\mathbb{Q}(\sqrt{d}).

If the left-hand side of (16) is too large, the size bounds of Step 3 will contradict the divisibility obtained in Step 2.

Step 1. A matrix with a nonzero minor

We take our matrix to have rows indexed by the formal monomials ZrWsZ^rW^s, where r,sr,s are nonnegative integers with r+ts<Lr+ts<L, and columns indexed by integers j,u,vj,u,v with 0≤j≤L/t0\le j\le L/t and 0≤u,v≤L0\le u,v\le\sqrt{L}. Here the (j,u,v)(j,u,v)-th entry of the ZrWsZ^rW^s-th row is the jjth ZZ-derivative of ZrWsZ^rW^s evaluated at

(Z,W)=(u+vd,u−vd),(17)(Z,W)=(u+v\sqrt{d},u-v\sqrt{d}), \tag*{(17)}

that is, r!(r−j)!(u+vd)r−j(u−vd)s\frac{r!}{(r-j)!}(u+v\sqrt{d})^{r-j}(u-v\sqrt{d})^s if j≤rj\le r, and 0 otherwise.

We let

N:=number of rows of our matrix,N:=\text{number of rows of our matrix},
E:=sum of the Z-degrees of the monomials indexing the rows.E:=\text{sum of the }Z\text{-degrees of the monomials indexing the rows}.

Suppose pp is an odd prime for which (dp)=−1\left(\frac{d}{p}\right)=-1. Then working in Z[d]\mathbb{Z}[\sqrt{d}] mod pp amounts to working in the field of p2p^2 elements. Indeed,

Z[d]/(p)≃Z[T]/(T2−d,p)≃(Z/pZ)[T]/(T2−d)≃Fp2.\mathbb{Z}[\sqrt{d}]/(p)\simeq\mathbb{Z}[T]/(T^2-d,p)\simeq(\mathbb{Z}/p\mathbb{Z})[T]/(T^2-d)\simeq\mathbb{F}_{p^2}.

The argument below makes essential use of the fact, familiar to students of algebraic number theory, that the ppth power map on Fp2\mathbb{F}_{p^2} is induced by conjugation on Z[d]\mathbb{Z}[\sqrt{d}]. The “freshman’s binomial theorem” yields a down-to-earth proof: For all u+vd∈Z[d]u+v\sqrt{d}\in\mathbb{Z}[\sqrt{d}],

(u+vd)p=up+vp(d)p≡u+vd(p−1)/2d≡u−vd(modpZ[d]),(18)(u+v\sqrt{d})^p=u^p+v^p(\sqrt{d})^p\equiv u+v d^{(p-1)/2}\sqrt{d}\equiv u-v\sqrt{d}\pmod{p\mathbb{Z}[\sqrt{d}]}, \tag*{(18)}

where the second step uses Fermat’s little theorem and the last uses Euler’s congruence d(p−1)/2≡(dp)(modp)d^{(p-1)/2}\equiv\left(\frac{d}{p}\right)\pmod p.

Reduce the matrix modulo LL. We claim that its rows are linearly independent over FL2\mathbb{F}_{L^2}. Supposing otherwise, we choose coefficients cr,s∈FL2c_{r,s}\in\mathbb{F}_{L^2}, not all zero, giving a zero linear combination of the rows. Put

C(Z):=∑r+ts<Lcr,sZr+Ls∈FL2[Z].C(Z):=\sum_{r+ts<L}c_{r,s}Z^{r+Ls}\in\mathbb{F}_{L^2}[Z].

Since 0≤r<L0\le r<L, the exponents r+Lsr+Ls are distinct, and so C(Z)≠0C(Z)\ne0.

In characteristic LL, differentiation treats ZLZ^L as a constant. Thus, taking the jjth derivative of Zr+LsZ^{r+Ls} gives the same result as differentiating ZrWsZ^rW^s jj times with respect to ZZ and then setting W=ZLW=Z^L. By (18), (u+vd)L=u−vd(u+v\sqrt{d})^L=u-v\sqrt{d} in FL2\mathbb{F}_{L^2}, so the assumed linear dependence gives

C(j)(u+vd)=0C^{(j)}(u+v\sqrt{d})=0

for all 0≤j≤L/t0\le j\le L/t and all 0≤u,v≤L0\le u,v\le\sqrt{L}. Since ⌊L/t⌋<L\lfloor L/t\rfloor<L, the factorials j!j! for 0≤j≤L/t0\le j\le L/t are invertible in FL2\mathbb{F}_{L^2}. It follows that CC vanishes to order at least ⌊L/t⌋+1>L/t\lfloor L/t\rfloor+1>L/t at each of the (1+⌊L⌋)2>L(1+\lfloor\sqrt{L}\rfloor)^2>L distinct elements u+vdu+v\sqrt{d}. (These are distinct because 1,d1,\sqrt{d} are linearly independent over FL\mathbb{F}_L and 0≤u,v<L0\le u,v<L.) As C≠0C\ne0, this forces deg⁡C>L2/t\deg C>L^2/t. On the other hand, every exponent appearing in CC satisfies

r+Ls≤Lt(r+ts)<L2/t,r+Ls\le\frac{L}{t}(r+ts)<L^2/t,

so that deg⁡C<L2/t\deg C<L^2/t. Contradiction.

Hence, the rows are independent modulo LL, and there is a minor Δ\Delta of order NN which is nonzero modulo LL and hence also nonzero in Z[d]\mathbb{Z}[\sqrt{d}].

Step 2. Divisibility by small primes

Fix a prime pp with t≤p≤Lt\le p\le L and ψ(p)=−1\psi(p)=-1. We determine a power of pp dividing Δ\Delta. For the row indexed by (r,s)(r,s), put h=⌊r/p⌋h=\lfloor r/p\rfloor, and replace its monomial ZrWsZ^rW^s by

Zr−phWs(Zp−Wp)h.Z^{r-ph}W^s\left(\frac{Z^p-W}{p}\right)^h.

As before, the new entries are obtained by taking ZZ-derivatives and evaluating at the conjugate pairs in (17).

We first check that all the new entries belong to Z[d]\mathbb{Z}[\sqrt{d}]. By (18),

Zp−Wp∈Z[d]when(Z,W)=(u+vd,u−vd).\frac{Z^p-W}{p}\in\mathbb{Z}[\sqrt{d}] \qquad\text{when}\qquad (Z,W)=(u+v\sqrt{d},u-v\sqrt{d}).

Moreover, its first ZZ-derivative is Zp−1Z^{p-1}, so all its positive-order ZZ-derivatives have integer coefficients. The product rule now shows that every ZZ-derivative of the replacement polynomial takes values in Z[d]\mathbb{Z}[\sqrt{d}] at these pairs, as desired.

To see what these replacements do to the determinant, expand:

Zr−phWs(Zp−Wp)h=p−hZrWs+p−h∑k=1h(−1)k(hk)Zr−pkWs+k.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{h}{k}Z^{r-pk}W^{s+k}.

Every monomial on the right indexes an original row. Indeed, r−pk≥0r-pk\ge0, and

(r−pk)+t(s+k)=r+ts−k(p−t)≤r+ts<L.(r-pk)+t(s+k)=r+ts-k(p-t)\le r+ts<L.

Furthermore, every term in the sum has ZZ-degree less than rr.

Order the rows by increasing rr, breaking ties arbitrarily, and make the replacements from last to first. Each replacement multiplies the current row by p−hp^{-h} and adds a linear combination of earlier, unchanged rows. Thus, on the columns defining our minor Δ\Delta, the new determinant is

Δp∑r+ts<L⌊r/p⌋.\frac{\Delta}{p^{\sum_{r+ts<L}\lfloor r/p\rfloor}}.

Since all its entries belong to Z[d]\mathbb{Z}[\sqrt{d}], so does this determinant. Hence p∑r+ts<L⌊r/p⌋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:=∏t≤p≤Lψ(p)=−1p∑r+ts<L⌊r/p⌋D:=\prod_{\substack{t\le p\le L\\ \psi(p)=-1}}p^{\sum_{r+ts<L}\lfloor r/p\rfloor}

divides Δ\Delta.

Let us estimate the size of DD. Since ⌊r/p⌋≥r/p−1\lfloor r/p\rfloor\ge r/p-1, we have ∑r+ts<L⌊r/p⌋≥E/p−N\sum_{r+ts<L}\lfloor r/p\rfloor\ge E/p-N, and so

log⁡D≥E∑t≤p≤Lψ(p)=−1log⁡pp−N∑p≤Llog⁡p.(19)\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. \tag*{(19)}

Bounds under both embeddings

We begin with a few estimates for the rows of our matrix. Since 0≤r<L0\le r<L and 0≤s<L/t0\le s<L/t, we have N≪L2/tN\ll L^2/t. For a lower bound on EE, consider the rows with L/4≤r<L/2L/4\le r<L/2 and 0≤s<L/(4t)0\le s<L/(4t). All these pairs satisfy r+ts<Lr+ts<L. There are ≫L2/t\gg L^2/t of them, each contributing at least L/4L/4 to EE. Thus E≫L3/tE\gg L^3/t, and so N≪E/LN\ll E/L. Also, the sum of the WW-degrees of the monomials indexing the rows is at most LN/t≪E/tLN/t\ll E/t.

We now bound the entries of our matrix in either embedding of Q(d)\mathbb{Q}(\sqrt{d}) into C\mathbb{C}. Since ∣d∣=f|d|=f, the grid coordinates u±vdu\pm v\sqrt{d} have absolute value at most L(1+f)≤4Lf\sqrt{L}(1+\sqrt{f})\le4\sqrt{Lf}. The entry in row ZrWsZ^rW^s and column (j,u,v)(j,u,v) is zero if j>rj>r; otherwise, its absolute value is at most

r!(r−j)!(4Lf)r+s−j≤Lj(4Lf)r+s≤LL/t(4Lf)r+s.\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!N! terms. Writing Δ~\widetilde{\Delta} for the conjugate of Δ\Delta, we obtain

max⁡{∣Δ∣,∣Δ~∣}≤N!LLN/t(4Lf)E+LN/t.\max\{|\Delta|,|\widetilde{\Delta}|\}\le N!L^{LN/t}(4\sqrt{Lf})^{E+LN/t}.

Taking logarithms,

max⁡{log⁡∣Δ∣,log⁡∣Δ~∣}≤log⁡(N!)+LNtlog⁡L+(E+LNt)log⁡(4Lf).\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≪L2/tN\ll L^2/t and N≪E/LN\ll E/L, we have

log⁡(N!)≤Nlog⁡N≪Nlog⁡L≪Elog⁡LL≪Elog⁡Lt,\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≪E/tLN/t\ll E/t. Thus the first two terms contribute O(Elog⁡L/t)O(E\log L/t), while the last is

(E+O(E/t))(12log⁡L+12log⁡f+log⁡4)=12Elog⁡L+O(E(log⁡Lt+log⁡f+1)).\left(E+O(E/t)\right)\left(\frac{1}{2}\log L+\frac{1}{2}\log f+\log4\right)=\frac{1}{2}E\log L+O\left(E\left(\frac{\log L}{t}+\log f+1\right)\right).

Consequently,

max⁡{log⁡∣Δ∣,log⁡∣Δ~∣}≤E{12log⁡L+O(log⁡Lt+log⁡f+1)}.(20)\max\{\log|\Delta|,\log|\widetilde{\Delta}|\}\le E\left\{\frac{1}{2}\log L+O\left(\frac{\log L}{t}+\log f+1\right)\right\}. \tag*{(20)}

Wrap-up

Wrap-up. Now for the big finish. We compare (19) and (20), noting that N∑p≤Llog⁡p≪NL≪EN\sum_{p\le L}\log p \ll NL \ll E. If

∑t≤p≤Lψ(p)=−1log⁡pp>12log⁡L+C(log⁡Lt+log⁡f+1)\sum_{\substack{t\le p\le L\\ \psi(p)=-1}}\frac{\log p}{p}>\frac{1}{2}\log L+C\left(\frac{\log L}{t}+\log f+1\right)

for a sufficiently large absolute effective CC, both conjugates of Δ/D\Delta/D have absolute value less than 1. But Δ/D\Delta/D is a nonzero element of Z[d]\mathbb{Z}[\sqrt{d}], so its norm is a nonzero integer of absolute value less than 1, a contradiction.

Adding the contribution of primes below tt, keeping in mind the definition of LL, we obtain

∑p≤xψ(p)=−1log⁡pp≤12log⁡x+O(log⁡xt+log⁡f+t).\sum_{\substack{p\le x\\ \psi(p)=-1}}\frac{\log p}{p}\le\frac{1}{2}\log x+O\left(\frac{\log x}{t}+\log f+t\right).

Since x≥ft2x\ge ft^2 and f≥2f\ge2, both log⁡f\log f and tt are O(log⁡x/t)O(\log x/t). This gives (16) and completes the proof of Proposition 6. □

Remark 7. The strategy may be compared with Selberg’s proof of Lemma 1 in [22 §4], where he compares the size of a product of norms u2−dv2u^2-dv^2 over a rectangular grid with its prime factorization. Such products are closely connected with Vandermonde determinants on grid points u+vdu+v\sqrt{d}. But the two arguments run in opposite directions. Selberg bounds his product from below and observes that an odd prime pp with (dp)=−1\left(\frac{d}{p}\right)=-1 divides u2−dv2u^2-dv^2 only when it divides both uu and vv, 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 (18) to force the primes with ψ(p)=−1\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.

Appendix 2. Proof of Lemma 4

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.

Proposition 8 (Sieving progressions, à la Selberg). Let qq be a positive integer, let PP be a product of distinct primes, none dividing qq, let R≥1R\ge1, and put

H:=∑m∣Pm≤R1φ(m).H:=\sum_{\substack{m\mid P\\m\le R}}\frac{1}{\varphi(m)}.

Then, for every v>0v>0 and integer aa,

#{n≤v:n≡a(modq), (n,P)=1}≤vqH+R2.(21)\#\{n\le v:n\equiv a\pmod q,\ (n,P)=1\}\le\frac{v}{qH}+R^2. \tag*{(21)}

Proof. For d∣Pd\mid P, choose

ρd:=μ(d)dφ(d)H∑k∣P(k,d)=1dk≤R1φ(k).\rho_d:=\frac{\mu(d)d}{\varphi(d)H}\sum_{\substack{k\mid P\\(k,d)=1\\dk\le R}}\frac{1}{\varphi(k)}.

and put ρd=0\rho_d=0 otherwise. Thus ρ1=1\rho_1=1 and ρd=0\rho_d=0 for d>Rd>R. (This initially strange-seeming choice of coefficients arises naturally from a minimization problem; see [6, §7.1, pp. 90–92].) If (n,P)=1(n,P)=1, then ∑d∣nρd=ρ1=1\sum_{d\mid n}\rho_d=\rho_1=1. Consequently,

#{n≤v:n≡a(modq), (n,P)=1}≤∑n≤vn≡a (q)(∑d∣nρd)2≤vq∑d,e∣Pρdρe[d,e]+(∑d∣P∣ρd∣)2.(22)\begin{aligned} \#\{n\le v:n\equiv a\pmod q,\ (n,P)=1\} &\le\sum_{\substack{n\le v\\ n\equiv a\ (q)}}\left(\sum_{d\mid n}\rho_d\right)^2\\ &\le\frac{v}{q}\sum_{d,e\mid P}\frac{\rho_d\rho_e}{[d,e]}+\left(\sum_{d\mid P}|\rho_d|\right)^2. \tag*{(22)} \end{aligned}

In the last line, we use that [d,e][d,e] is coprime to qq, so that the number of multiples of [d,e][d,e] in our progression is v/(q[d,e])v/(q[d,e]), up to an error at most 1.

Continuing, observe that the products jkjk with j∣dj\mid d, (k,d)=1(k,d)=1, and dk≤Rdk\le R are distinct divisors of PP at most RR. Hence,

H≥∑j∣d1φ(j)∑k∣P(k,d)=1dk≤R1φ(k)=dφ(d)∑k∣P(k,d)=1dk≤R1φ(k).H\ge\sum_{j\mid d}\frac{1}{\varphi(j)} \sum_{\substack{k\mid P\\(k,d)=1\\dk\le R}}\frac{1}{\varphi(k)} =\frac{d}{\varphi(d)} \sum_{\substack{k\mid P\\(k,d)=1\\dk\le R}}\frac{1}{\varphi(k)}.

Comparing with the definition of ρd\rho_d shows that each ∣ρd∣≤1|\rho_d|\le1. In particular, (∑d∣P∣ρd∣)2≤R2\left(\sum_{d\mid P}|\rho_d|\right)^2\le R^2. Hence, Proposition 8 will be proved once we show that the double sum over d,ed,e in (22) is 1/H1/H.

For m∣Pm\mid P, expanding the definition of ρd\rho_d gives

∑d∣Pm∣dρdd=1H∑d∣Pm∣d∑k∣Pm∣dk(k,d)=1dk≤Rμ(d)φ(d)φ(k).\sum_{\substack{d\mid P\\m\mid d}}\frac{\rho_d}{d} =\frac{1}{H}\sum_{\substack{d\mid P\\m\mid d}}\sum_{\substack{k\mid P\\m\mid dk\\(k,d)=1\\dk\le R}}\frac{\mu(d)}{\varphi(d)\varphi(k)}.

Put b=dkb=dk. Since (d,k)=1(d,k)=1, we have b∣Pb\mid P and φ(d)φ(k)=φ(b)\varphi(d)\varphi(k)=\varphi(b). Conversely, for each b∣Pb\mid P, every divisor dd of bb gives a coprime factorization b=d(b/d)b=d(b/d), since bb is squarefree. Hence

∑d∣Pm∣dρdd=1H∑b∣Pb<Rm∣b1φ(b)∑d∣bm∣dμ(d).\sum_{\substack{d\mid P\\m\mid d}}\frac{\rho_d}{d} =\frac{1}{H}\sum_{\substack{b\mid P\\b<R\\m\mid b}}\frac{1}{\varphi(b)} \sum_{\substack{d\mid b\\m\mid d}}\mu(d).

Writing d=med=me, the inner sum is

∑d∣bm∣dμ(d)=μ(m)∑e∣b/mμ(e),\sum_{\substack{d\mid b\\m\mid d}}\mu(d)=\mu(m)\sum_{e\mid b/m}\mu(e),

which vanishes unless b=mb=m, when it equals μ(m)\mu(m). Thus

∑d∣Pm∣dρdd={μ(m)φ(m)H,m≤R,0,m>R.\sum_{\substack{d\mid P\\m\mid d}}\frac{\rho_d}{d} = \begin{cases} \dfrac{\mu(m)}{\varphi(m)H}, & m\le R,\\ 0, & m>R. \end{cases}

Using [d,e]=de/(d,e)[d,e]=de/(d,e) and (d,e)=∑m∣(d,e)φ(m)=∑m∣dm∣eφ(m)(d,e)=\sum_{m\mid(d,e)}\varphi(m)=\sum_{\substack{m\mid d\\m\mid e}}\varphi(m), we obtain

∑d,e∣Pρdρe[d,e]=∑m∣Pφ(m)(∑d∣Pm∣dρdd)2=1H,\sum_{d,e\mid P}\frac{\rho_d\rho_e}{[d,e]} =\sum_{m\mid P}\varphi(m)\left(\sum_{\substack{d\mid P\\m\mid d}}\frac{\rho_d}{d}\right)^2 =\frac{1}{H},

as desired. □\square

Proof of the upper bound in (6)

Proof of the upper bound in (6). We apply Proposition 8 with

v=t,P:=∏ℓ≤zℓ∤qℓ,R=zh.v=t,\qquad P:=\prod_{\substack{\ell\le z\\ \ell\nmid q}}\ell,\qquad R=z^h.

Comparing the statement of Proposition 8 with that of (6), it suffices to show that

1H=V(z)qφ(q)(1+O(e−h)).(23)\frac{1}{H}=V(z)\frac{q}{\varphi(q)}(1+O(e^{-h})). \tag*{(23)}

Let H0H_0 be defined the same way as HH but without the requirement that m≤Rm\le R, i.e.,

H0:=∑m∣P1φ(m).H_0:=\sum_{m\mid P}\frac{1}{\varphi(m)}.

Clearly, H≤H0H\le H_0. The difference H0−HH_0-H can be estimated with Rankin’s trick: Since every prime divisor of PP is at most zz,

H0−H≤R−1/log⁡z∑m∣Pm1/log⁡zφ(m)=e−log⁡R/log⁡zH0∏p∣P(1+p1/log⁡z−1p).\begin{aligned} H_0-H\le R^{-1/\log z}\sum_{m\mid P}\frac{m^{1/\log z}}{\varphi(m)} \\ &=e^{-\log R/\log z}H_0\prod_{p\mid P}\left(1+\frac{p^{1/\log z}-1}{p}\right). \end{aligned}

For p≤zp\le z, the mean value theorem gives p1/log⁡z−1≤elog⁡p/log⁡zp^{1/\log z}-1\le e\log p/\log z, so that

∏p∣P(1+p1/log⁡z−1p)≤exp⁡(∑p∣Pp1/log⁡z−1p)≤exp⁡(elog⁡z∑p≤zlog⁡pp)≪1.\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{e}{\log z}\sum_{p\le z}\frac{\log p}{p}\right)\ll1.

Hence, H0−H≪H0e−log⁡R/log⁡zH_0-H\ll H_0e^{-\log R/\log z}, and H=H0{1+O(e−log⁡R/log⁡z)}H=H_0\{1+O(e^{-\log R/\log z})\}. So, once h=log⁡R/log⁡zh=\log R/\log z is sufficiently large,

1H=1H0{1+O(e−log⁡R/log⁡z)}.\frac{1}{H}=\frac{1}{H_0}\{1+O(e^{-\log R/\log z})\}.

But

H0−1=∏p∣P(1−1p)=∏p≤zp∤q(1−1p)=V(z)qφ(q)H_0^{-1}=\prod_{p\mid P}\left(1-\frac{1}{p}\right) =\prod_{\substack{p\le z\\p\nmid q}}\left(1-\frac{1}{p}\right) =V(z)\frac{q}{\varphi(q)}

(using in the last step that z≥qz\ge q), and (24) follows.

Proof of the lower bound in (6)

Proof of the lower bound in (6). An integer n≡b(modq)n\equiv b\pmod q removed by the sieve has least prime factor p≤zp\le z, where necessarily p∤qp\nmid q. Write n=pmn=pm, where m≤t/pm\le t/p, m≡bp−1(modq)m\equiv bp^{-1}\pmod q, and mm is not divisible by any primes ℓ<p\ell<p not dividing qq. For each p≤zp\le z with p∤qp\nmid q, we use Proposition 8 to bound the number of removed integers with least prime factor pp, by taking

v=t/p,P:=∏ℓ<pℓ∤qℓ,R=zh.v=t/p,\qquad P:=\prod_{\substack{\ell<p\\\ell\nmid q}}\ell,\qquad R=z^h.

(So the choice of RR is unchanged from before.) Write

Vq:=∏p≤zp∤q(1−1p),Wp:=∏ℓ<pℓ∤q(1−1ℓ).V_q:=\prod_{\substack{p\le z\\p\nmid q}}\left(1-\frac{1}{p}\right),\qquad W_p:=\prod_{\substack{\ell<p\\\ell\nmid q}}\left(1-\frac{1}{\ell}\right).

Arguing as in the proof of the upper bound, we find that the number of removed integers corresponding to a given p≤zp \le z is at most

tWppq{1+O(e−log⁡R/log⁡p)}+R2.\frac{tW_p}{pq}\{1+O(e^{-\log R/\log p})\}+R^2.

Subtracting these counts from the total number t/q+O(1)t/q+O(1) of integers in our progression yields a main term of

(1−∑p≤zp∤qWpp)tq.\left(1-\sum_{\substack{p\le z\\p\nmid q}}\frac{W_p}{p}\right)\frac{t}{q}.

The parenthesized expression on the left simplifies to VqV_q (Buchstab’s identity): Indeed, VqV_q can be viewed as the density of integers not divisible by any prime p≤zp\le z, p∤qp\nmid q. The set of such integers is obtained by removing, for each p≤zp\le z, p∤qp\nmid q, those whose least prime factor not dividing qq is pp. (This is the same observation we made above, wearing a mustache and wig.) Each such set has density Wp/pW_p/p.

We therefore obtain

#{n≤t:n≡b(modq), P−(n)>z}≥tVqq−O(tq∑p≤zp∤qWppe−log⁡R/log⁡p)−O(zR2).\#\{n\le t:n\equiv b\pmod q,\ P^-(n)>z\}\ge\frac{tV_q}{q}-O\left(\frac{t}{q}\sum_{\substack{p\le z\\p\nmid q}}\frac{W_p}{p}e^{-\log R/\log p}\right)-O(zR^2).

Since Vq/q=V(z)/φ(q)V_q/q=V(z)/\varphi(q), the main term here is precisely tV(z)/φ(q)tV(z)/\varphi(q). Also, zR2=z2h+1≤z3hzR^2=z^{2h+1}\le z^{3h}. Thus, we will have our lower bound once we check that the sum in the first OO-error is ≪e−hVq\ll e^{-h}V_q.

Uniformly for primes p≤zp\le z, we have

WpVq=∏p≤ℓ≤zℓ∤q(1−1ℓ)−1≪log⁡zlog⁡p.\frac{W_p}{V_q}=\prod_{\substack{p\le\ell\le z\\\ell\nmid q}}\left(1-\frac{1}{\ell}\right)^{-1}\ll\frac{\log z}{\log p}.

Put u=log⁡z/log⁡p≥1u=\log z/\log p\ge1. For h≥2h\ge2, the function u2e−huu^2e^{-hu} is decreasing on [1,∞)[1,\infty), so u2e−hu≤e−hu^2e^{-hu}\le e^{-h}. Since log⁡R=hlog⁡z\log R=h\log z,

∑p≤zp∤qWppVqe−log⁡R/log⁡p≪∑p≤zp∤q1plog⁡zlog⁡pe−log⁡R/log⁡p≤e−hlog⁡z∑p≤zlog⁡pp≪e−h.\sum_{\substack{p\le z\\p\nmid q}}\frac{W_p}{pV_q}e^{-\log R/\log p} \ll\sum_{\substack{p\le z\\p\nmid q}}\frac{1}{p}\frac{\log z}{\log p}e^{-\log R/\log p} \le\frac{e^{-h}}{\log z}\sum_{p\le z}\frac{\log p}{p} \ll e^{-h}.

This finishes the proof of Lemma 4. □ Department of Mathematics, University of Georgia, Athens GA 30602

Email address: [email protected]

References

  1. [1]W. D. Banks, *On the OpenAI proof that Landau–Siegel zeros do not exist*, 2026, [arXiv:2610.15483](https://arxiv.org/abs/2610.15483).
  2. [2]Barreto, K. (n.d.). An elementary proof of the non-existence of Landau–Siegel zeros.
  3. [3]P. D. T. A. Elliott, *Multiplicative functions on arithmetic progressions. VII. Large moduli*, J. London Math. Soc. (2) 66 (2002), 14–28.DOI
  4. [4]Elliott, P. D. T. A. (2002). The least prime primitive root and Linnik’s theorem. In Number Theory for the Millennium, I (pp. 393–418).
  5. [6]J. Friedlander and H. Iwaniec, *Opera de Cribro*, Amer. Math. Soc. Colloq. Publ., vol. 57, American Mathematical Society, Providence, RI, 2010.DOI
  6. [7]———, *Sifting for small primes from an arithmetic progression*, Sci. China Math. 66 (2023), 2715–2730; [arXiv:2303.06122](https://arxiv.org/abs/2303.06122).
  7. [8]———, *Selberg’s sieve of irregular density*, Acta Arith. 209 (2023), 385–396.arxiv.org/abs/2206.03479
  8. [9]A. Granville, *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à di Salerno, Salerno, 1992, 157–194.
  9. [10]———, *Different approaches to the distribution of primes*, Milan J. Math. 78 (2010), 65–84; author’s version.DOI
  10. [11]Green, B. (2026). On Landau–Siegel zeros. <a href="https://doi.org/https://hexagonmath.com/" rel="noopener noreferrer" target="_blank">https://doi.org/https://hexagonmath.com/</a>
  11. [12]Iwaniec, H., & Kowalski, E. (2004). Analytic Number Theory. In Amer. Math. Soc. Colloq. Publ. (Vol. 53).
  12. [13]B. Kerr, *A simpler proof that there are no Landau–Siegel zeros*, 2026, arXiv:2610.21099v1.arXiv
  13. [14]D. Koukoulopoulos, *Pretentious multiplicative functions and the prime number theorem for arithmetic progressions*, Compos. Math. 149 (2013), 1129–1149.DOI
  14. [15]D. Koukoulopoulos, *The Distribution of Prime Numbers*, Grad. Stud. Math., vol. 203, American Mathematical Society, Providence, RI, 2019.DOI
  15. [16]Linnik, U. V. (1944). On the least prime in an arithmetic progression. I. The basic theorem. Rec. Math. [Mat. Sbornik], 15(57)(2), 139–178.
  16. [17]Linnik, U. V. (1944). On the least prime in an arithmetic progression. II. The Deuring–Heilbronn phenomenon. Rec. Math. [Mat. Sbornik], 15(57)(3), 347–368.
  17. [18]K. Matomäki, J. Merikoski, and J. Teräväinen, *Primes in arithmetic progressions and short intervals without L-functions*, 2024, arXiv:2401.17570.arXiv
  18. [19]H. L. Montgomery and R. C. Vaughan, *Multiplicative Number Theory I. Classical Theory*, Cambridge Studies in Advanced Mathematics, vol. 97, Cambridge University Press, Cambridge, 2007.
  19. [20]OpenAI, *Uniform exclusion of Landau–Siegel zeros*, OpenAI Math Release, October 1, 2026, online preprint.hub.valency.io/works/W_6sm4yjzs
  20. [21]S. Sachpazis, *A pretentious proof of Linnik’s estimate for primes in arithmetic progressions*, Mathematika 69 (2023), no. 3, 879–902; doi:10.1112/mtk.12211.DOI
  21. [22]A. Selberg, *An elementary proof of Dirichlet’s theorem about primes in an arithmetic progression*, Ann. of Math. (2) 50 (1949), 297–304.DOI
  22. [23]—, *An elementary proof of the prime number theorem for arithmetic progressions*, Canad. J. Math. 2 (1950), 66–78.DOI
  23. [24]H. N. Shapiro, *Introduction to the Theory of Numbers*, Wiley, New York, 1983.
  24. [25]Tao, T. (2026). A sketch of the proof of non-existence of Siegel zeroes. What’s New.
  25. [26]van Dijk, R. (2026). A Frobenius determinant proof of the non-existence of Landau–Siegel zeros. hexagon:2610.00409v2

Paper details

vlnc:W_r6768wnh
Version
v1 · latest
Published
Fresh — published within the last 30 days
License
CC BY 4.0
Usage

views · 13

downloads · 2

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Anthropic Claude Opus, OpenAI Codex

View statement
Looking for related papers…
Contents