# Elementary lower bounds for the number of primes in arithmetic progressions

Some version of the Prime Number Theorem provides the asymptotic behavior of the number of primes in arithmetic progression $$qn+a$$ with $$(q,a)=1$$, $$n \ge 1$$. I was wondering there are Chebyshev-type arguments (using the binomial coefficients or variants thereof) that establish the existence of at least $$c x/\log x$$ primes in such arithmetic progressions up to $$x$$ for some even small $$c>0$$ and some values of $$a, q>1$$. For instance, is there such an argument for primes of the form $$4k \pm 1$$? This is mostly a curiosity triggered by thinking about a number theory course I will teach soon.

• Comparing the factorizations of $n!$ and $\prod_{k^2+l^2<n} (k^2+l^2)$ may give something non-trivial, on the first glance. – Fedor Petrov Aug 28 at 10:31
• In this paper mathscinet.ams.org/mathscinet-getitem?mr=1220462 Granville explores how far the Erdos-Selberg elementary proof of the PNT can be pushed without having to deal with the theory of class numbers or Siegel zeroes. Roughly speaking he can get the expected lower bound for primes in a primitive residue classes $a \hbox{ mod } q$ as long as $a$ is not a quadratic residue (or more precisely, lies outside of every index two multiplicative subgroup of $({\bf Z}/q{\bf Z})^\times$). So for instance $4k-1$ would work but not $4k+1$! But the arguments aren't of Chebyshev type. – Terry Tao Aug 28 at 16:53
• Sorry, perhaps I’ve missed this, but why have we ruled out Selberg’s elementary proofs? See his papers “An elementary proof of the prime number theorem for arithmetic progressions” and “An elementary proof of Dirichlet’s theorem about primes in an arithmetic progression”. Presumably they don’t fit the “Chebyshev-style” restriction, but anyway they’re worth mentioning. – alpoge Sep 6 at 15:58

In Section 9 of

Diamond, Harold G., Elementary methods in the study of the distribution of prime numbers, Bull. Am. Math. Soc., New Ser. 7, 553-589 (1982). ZBL0505.10021.

an argument from

Diamond, Harold G.; Erdős, Paul, On sharp elementary prime number estimates, Enseign. Math., II. Sér. 26, 313-321 (1980). ZBL0453.10007.

is sketched, where it is shown that for every $$\varepsilon > 0$$ there is a Chebyshev style argument that shows that

$$(1-\varepsilon) x \leq \psi(x) \leq (1+\varepsilon) x$$

for all sufficiently large $$x$$. The idea is to compare $$\Lambda(n) = \mu * \log(n)$$ with a truncated version $$\Lambda_T(n) = \mu_T * \log(n)$$ where $$\mu_T$$ is $$\mu$$ truncated to a large interval $$[1,T]$$ (and modified at $$T$$ to ensure the normalisation $$\sum_n \mu_T(n)/n=0$$). Elementary methods can show that $$|\sum_{n \leq x} \Lambda_T(n) - m_1(T) x| \leq o(x)$$ for an explicitly computable quantity $$m_1(T)$$ (in fact $$m_1(T) = \sum_{n) that can be easily demonstrated to converge to one as $$T \to \infty$$ in a suitably averaged sense. In particular $$|\sum_{n \leq x} \Lambda_T(n) - x| \leq |m_1(T)-1| x + o(x)$$. The Dirichlet hyperbola method can also be used to produce an upper bound $$|\sum_{n \leq x} \Lambda_T(n) - \psi(x)| \leq \delta_T x + o(x)$$ for some explicitly computable quantity $$\delta_T$$ depending on $$T$$; with the aid of the PNT (in the form $$\sum_{n \leq x} \mu(n) = o(x)$$) one can show that $$\delta_T \to 0$$ as $$T \to \infty$$, and this is enough to conclude the claim. Amusingly, this gives a circular proof of the PNT assuming the PNT; however if one only wishes to get the PNT up to a given error $$\varepsilon$$ then this argument does not require the PNT, one simply has to locate a concrete value of $$T$$ for which the upper bounds $$|m_1(T)-1|, \delta_T$$ in the above inequalities (which can be explicitly computed by Chebyshev type methods) are small enough.

It looks very likely that one can twist this argument by characters and conclude that for every $$\varepsilon > 0$$ and primitive residue class $$a \hbox{ mod } q$$ there is a Chebyshev style argument that shows that

$$(1-\varepsilon) \frac{x}{\phi(q)} \leq \psi(x,q,a) \leq (1+\varepsilon) \frac{x}{\phi(q)}$$

for all sufficiently large $$x$$, where one again needs the prime number theorem in arithmetic progressions (presumably this time in the form $$\sum_{n \leq x} \mu(n) \chi(n) = o(x)$$) to guarantee that the elementary upper bounds for the error are indeed small. It seems plausible though that for specific residue classes like $$1 \hbox{ mod } 4$$ or $$-1 \hbox{ mod } 4$$ one could actually produce explicit numerical choices of the $$T$$ parameter that obey all the required properties and in particular produce non-trivial lower bounds of Chebyshev type.

• Thanks a lot! This looks quite interesting. I will go through the arguments to see if it can be made to work for arithmetic progressions. – Keivan Karai Aug 28 at 19:36
• If you get a chance, I'd love to see this spelled out. I'm not following the sketch, but I'm probably just missing something basic. – David E Speyer Sep 1 at 0:48
• To show that I am not being completely lazy, here is how I understand Chebyshev style arguments: The identity $\sum_{d|n} \Lambda(d) = \log n$ implies that $\sum_d \Lambda(d) \lfloor N/d \rfloor = \sum_{n \leq N} \log n = N \log N - N + O(\log N)$. We then take a linear combination of both sides evaluated at $N/j$ for various $j$ to get $\sum_d \Lambda(d) \sum_j \mu_T(j) \lfloor N/(jd) \rfloor = c N + O(\log N)$ for an explicit constant $c$. By choosing $\mu_T$ carefully, one arranges that $\sum_j \mu_T(j) \lfloor x/j \rfloor$ is close to $1$. – David E Speyer Sep 1 at 1:06
• But $\sum_{d|n} \chi(d) \Lambda(d)$ does not seem to be tractable, so I don't know how to get a handle on $\sum_d \chi(d) \Lambda(d) \lfloor N/d \rfloor$, and thus can't get the argument off the ground. – David E Speyer Sep 1 at 1:08
• One should think of the identity $\sum_{d|n} \Lambda(d) = \log n$ as $\sum_{d|n} \Lambda(d) 1(n/d) = \log n$, where $1$ is the constant function. The twist of this identity by $\chi$ is $\sum_{d|n} \chi(d) \Lambda(d) \chi(n/d) 1(n/d) = \chi(n) \log n$. The function $\lfloor x \rfloor = \sum_{n < x} 1$ would now be replaced by the summatory function $\sum_{n < x} \chi(n)$. – Terry Tao Sep 1 at 1:26

The following might make you happy: I claim that there are elementary proofs that $$\sum_{p \leq N} \frac{\log p}{p} = \log N + O(1)\ \mbox{and}$$ $$\sum_{p \leq N,\ p \equiv 1 \bmod 4} \frac{\log p}{p} = \frac{1}{2} \log N + O(1).$$ That's not strong enough to imply the PNT, but it does show that "half the primes are $$1 \bmod 4$$" with a certain weighting. I learned this from an answer of Vesselin Dmitrov, which I'll try to add a few details to. I don't know if or where this argument appears in print.

Let $$F = \sum_{0< n \leq N} \log n\ \mbox{and}\ G = \sum_{0 < u^2+v^2 \leq N} \log (u^2+v^2).$$ So $$F$$ is $$\log N!$$ and $$G$$ is a Gaussian analog of $$F$$.

We can estimate each of these by converting a sum to an integral. The corresponding integrals are $$\int_{t=0}^N \log t dt = N \log N - N \ \mbox{and} \ \int_{r=0}^{\sqrt{N}} 2 \pi r \log(r^2) dr = \pi N \log N - \pi N.$$ The conversion to an integral introduces error of $$O(\log N)$$ in the first case and $$O(\sqrt{N} \log N)$$ in the second, but we only need the leading term, so $$F = N \log N + O(N) \ \mbox{and}\ G = \pi N \log N + O(N).$$

As usual, we write $$\lfloor x \rfloor$$ for $$x$$ rounded down to the nearest integer, which we think of as the number of integers in the interval $$(0,x]$$. Inspired by this, let $$\lfloor x \rfloor_2$$ be the number of lattice points $$(u,v)$$ with $$0 < u^2+v^2 \leq x$$. Clearly, $$\lfloor x \rfloor_2 = \pi x + O(\sqrt{x})$$.

The usual argument tells us that $$F = \sum_p \sum_{k \geq 1} \left\lfloor \frac{N}{p^k} \right\rfloor \log p = \sum_{p \leq N} \frac{N}{p} \log p + O(N).$$ So $$\sum_{p \leq N} \frac{N}{p} \log p + O(N) = N \log N + O(N)$$ and dividing by $$N$$, the claim follows.

Mimicing the usual arguments but using unique factorization in $$\mathbb{Z}[i]$$, we get $$G = \sum_{\pi} \sum_{k \geq 1} \left\lfloor \frac{N}{N(\pi)^k} \right\rfloor_2 \log N(\pi)$$ where the sum runs over Gaussian primes $$\pi$$. We can rewrite this as $$G = 2 \sum_{p \equiv 1 \bmod 4} \sum_{k \geq 1} \left\lfloor \frac{N}{p^k} \right\rfloor_2 \log p + \sum_{p \equiv 3 \bmod 4} \sum_{k \geq 1} \left\lfloor \frac{N}{p^{2k}} \right\rfloor_2 \log p^2 + \sum_{k \geq 1} \left\lfloor \frac{N}{2^k} \right\rfloor_2 \log 2.$$ The latter sums are negligible, and approximating $$\lfloor x \rfloor_2$$ by $$\pi x$$ gives $$G = 2 \sum_{p \equiv 1 \bmod 4,\ p \leq N} \frac{\pi N}{p} \log p + O(N).$$ Comparing our formulas for $$G$$ and dividing both sides by $$\pi N$$ gives $$2 \sum_{p \equiv 1 \bmod 4,\ p \leq N} \frac{\log p}{p} = \log N +O(1)$$ as promised.

If I get a chance later, I might comment on other moduli besides $$4$$.

• Thanks, this is quite nice, and similar to what had expected. So now using the standard Chebyshev's trick one can even get the lower bound of right order for the number of primes in the arithmetic progression without the weighting them. – Keivan Karai Aug 30 at 9:43
• I don't think this will work? Choose an integer $b>1$. Let $Q$ be the set of primes that have an even number of digits in base $b$. Then I get that $\sum_{q \in Q,\ q \leq N} \tfrac{\log q}{q} = \tfrac{1}{2} \log N + O(N)$. But $\sum_{q \in Q, q \leq N} 1$ can be as small as $\tfrac{N}{b \log N}$. – David E Speyer Aug 30 at 11:35
• I tried to mimic an argument in Apostol's ANT. Let me try to reproduce it here. Set $$A(N) = \sum_{ p \equiv 1 \bmod{4} , \ p \le N} \frac{\log p}{p}.$$ Your argument shows that $A(N)= \frac{1}{2} \log N + G(N)$, where $|G(N)| \le M$. This implies that for $\epsilon>0$ and $N \gg_{ \epsilon} 1$ we have $$A(N)- A( \epsilon N) = -\frac{1}{2} \log \epsilon +G(N)- G( \epsilon N) \ge - \frac{1}{2}\log \epsilon -2M.$$ Continued below. – Keivan Karai Aug 30 at 12:09
• By choosing an appropriate $\epsilon$ so that the right hand side of the above inequality is 1, we can guarantee that $A(N)- A( \epsilon N) \ge 1$ as long as $N \ge \epsilon^{-1}$. This now gives for $N \gg 1$ $$1 \le A( N) - A( \epsilon N) = \sum_{ p \equiv 1 \bmod{4} , \ \epsilon N < p \le N} \frac{\log p}{p} \le \frac{1}{\epsilon N} \sum_{ p \equiv 1 \bmod{4} , \ p \le N} {\log p} \le \frac{\log N }{ \epsilon N} \# \{p \equiv 1 \bmod{4} , \ p \le N \}.$$ Does this work? – Keivan Karai Aug 30 at 12:09
• I found three papers where this kind of argument appears (apparently, independently of the previous). 1. H. Poincare: Extension aux nombres preimers complexes des theoremes de M. Tchebicheff (1892) sites.mathdoc.fr/JMPA/PDF/JMPA_1892_4_8_A2_0.pdf 2. A. Selberg: pages 71-72 of An elementary proof o the prime number theorem for arithmetic progressions (1950). 3. R. Breusch: An asymptotic formula for primes of the form 4n+1. (Michigan Math. J, 1964) projecteuclid.org/euclid.mmj/1028999182 – Vesselin Dimitrov Sep 1 at 2:53

Here is another, more Chebyshev like, approach. It is possible that this is the proof Terry was sketching and I just didn't understand it. I think this should generalize to AP's for any modulus, but I'll stick to $$4$$. Let $$\chi$$ be the quadratic character modulo $$4$$. To prove PNT in AP's mod 4, we must show $$\sum_{n \leq N} \Lambda(n) = N + o(N),\ \sum_{n \leq N} \chi(n) \Lambda(n) = o(N).$$ Chebyshev style arguments prove bounds of the form $$a N < \sum_{n \leq N} \Lambda(n) < b N$$; I will analogously prove bounds of the form $$\left| \sum_{n \leq N} \chi(n) \Lambda(n) \right| < cN$$. This will only be interesting if I manage to get $$c<1$$.

For any positive real number $$x$$, define $$\langle x \rangle = \sum_{1 \leq k \leq x} \chi(k).$$ So $$\langle x \rangle$$ is $$1$$ if $$\lfloor x \rfloor \equiv 1,2 \bmod 4$$ and $$0$$ if $$\lfloor x \rfloor \equiv 3,4 \bmod 4$$.

Put $$S = \sum_{n \leq N} \chi(n) \log n.$$ Start by noticing that $$\left| S \right| \leq \log N$$ because each term switches the sign of the partial sum.

Expand the sum as $$S = \sum_{n \leq N} \sum_{d|n} \chi(d) \chi(n/d) \Lambda(d) = \sum_d \chi(d) \Lambda(d) \sum_{m \leq N/d} \chi(m) = \sum_d \chi(d) \Lambda(d) \ \langle\! N/d \rangle. \quad (\ast)$$

Now, $$\langle N/d \rangle$$ is $$1$$ for $$N/3 < d \leq N$$, is $$0$$ for $$N/5 < d \leq N/3$$ and is between $$0$$ and $$1$$ for all $$d$$, so $$\left|\sum_{N/3< d \leq N} \chi(d) \Lambda(d) \right| \leq |S| + \sum_{d \leq N/5} \Lambda(d).$$ Invoking Chebyshev's bound $$\sum_{d \leq M} \Lambda(d) \leq 1.11 M$$, we have $$\left|\sum_{N/3< d \leq N} \chi(d) \Lambda(d) \right| \leq \log N + 1.11 \times \frac{1}{5} N .$$ Summing up this equation for $$N$$, $$N/3$$, $$N/9$$, ..., we get $$\left|\sum_{d \leq N} \chi(d) \Lambda(d) \right| \leq \frac{(\log N)^2}{\log 3} + 1.11 \times \frac{3}{10} N.$$ Since $$0.333<1$$, we win.

I think there is substantial room to improve this argument. If we sum up equation $$(\ast)$$ at $$N$$ and $$N/3$$, we get $$\sum_d \chi(d) \Lambda(d) {\Big(} \langle N/d \rangle + \langle N/(3d) \rangle {\Big)} = O(\log N).$$ We have $${\Big(} \langle N/d \rangle + \langle N/(3d) \rangle {\Big)} = 1$$ for $$N/7 < d \leq N$$, then $$=0$$ for $$N/9 < d \leq N/7$$, and is always at most $$2$$. So similar arguments give $$\left| \sum_{N/7 < d \leq N} \chi(d) \Lambda(d) \right| \leq 1.11 \times \frac{2}{9} N + O(\log N)$$ and thus replace $$1.11 \times \tfrac{3}{10}$$ with $$1.11 \times \frac{16}{63}$$ in the final analysis. I think this constant could be chased much lower if we took smarter linear combinations.

More precisely, we have $$\sum_{t=1}^T \chi(t) \mu(t) \langle x/t \rangle = 1$$ for $$x \geq T$$. So, for fixed $$T$$, we have $$\sum_{t=1}^T \mu(t) \chi(t) \sum_d \chi(d) \Lambda(d) \ \langle\! N/(td) \rangle =$$ $$\sum_{N/T < d \leq N} \chi(d) \Lambda(d) + \sum_{d \leq N/T} \chi(d) \Lambda(d) \left( \sum_{t=1}^T \mu(t) \chi(t) \langle\! N/(td) \rangle \right) = O(\log N).$$ If we could get the parenthesized quantity to be $$o(T)$$, independent of $$N$$, we would win.

• Thanks for the detailed answer. Just to clarify a small point: to win (using only Chebyshev's bounds), one needs the factor 0.333 to be less than Chebyshev's lower bound which (about 0.9) rather than 1, right? Of course, this also holds. – Keivan Karai Sep 1 at 10:55
• Yes, that's right. – David E Speyer Sep 1 at 11:53