Counting primes by elementary means: Chebyshev and Mertens

Written by GPT-6.1 Sol (OpenAI) in Codex, Ultra setting, October 2026. Self-checked by the writing AI, GPT-6.1 Sol, Ultra. Public domain (CC0).

How much can we learn about primes before locating any zeros of zeta? A factorial already contains enough information to determine the scale of prime counting. A second use of the same information determines averages over primes, including the precise constant in Mertens's product. These elementary estimates will later control the errors in complex integration.

We use unique factorization, Möbius inversion and elementary real analysis, together with summation by parts and the pole of zeta proved in Dirichlet series and Euler products. The free comparison source is Koukoulopoulos’s author preliminary version listed below. All the prime-counting results needed here are proved below. The prime number theorem itself belongs to the later lesson The prime number theorem; here we prove the equivalence of its different formulations.

Throughout, $p$ denotes a prime, and all logarithms are natural. For real $x\ge1$, put

The function $\Lambda$ equals $\log p$ at $p^k$, $k\ge1$, and is zero elsewhere. Thus $\theta$ counts primes with a logarithmic weight, while $\psi$ also counts their powers. We write $f\asymp g$ when positive constant multiples of $g$ bound $f$ above and below for all sufficiently large arguments. The notation $f\sim g$ means $f/g\to1$.

The integration and complex-analysis tools used in this lesson are proved in Dirichlet series and Euler products, Appendix A, Lemmas A.1–A.4.

1. From discrete weights to integrals

The cumulative sum is often easier to estimate than individual coefficients. Summation by parts lets us change the weight without losing that information.

Lemma 1.1 (partial summation). Let $a(n)$ be complex numbers and $A(t)=\sum_{n\le t}a(n)$. For real $1\le y\le x$ and $f\in C^1([y,x])$,

Equivalently, the sum is the Riemann--Stieltjes integral $\int_{(y,x]}f\,dA$. The half-open interval specifies the endpoint convention, even when $y$ or $x$ is an integer.

Proof. Apply the finite summation-by-parts argument of the preceding lesson to the integers in $(y,x]$. Explicitly, write $f(n)=f(x)-\int_n^x f'(t)\,dt$. The coefficient of $f(x)$ is $A(x)-A(y)$, and the inner sum in the integral is $A(t)-A(y)$. Expanding and using $\int_y^x f'=f(x)-f(y)$ gives the formula. The Stieltjes measure $dA$ has mass $a(n)$ at each integer, so its integral over $(y,x]$ is precisely the finite sum. $\square$

We can also include the mass at the left endpoint by using $A(y^-)$ instead of $A(y)$. For primes this gives, for $x\ge2$,

and

Indeed, take respectively $a(p)=\log p$, $f(t)=1/\log t$, and $a(p)=1$, $f(t)=\log t$, with zero coefficients at composites. In both cases the cumulative sum is zero at $2^-$, so there is no lower boundary term.

Lemma 1.2 (the size of a factorial). For real $x\ge2$,

Proof. Write $N=\lfloor x\rfloor$. Since $\log t$ is increasing,

The integral is $N\log N-N+1$. The derivative of $t\log t-t$ is $\log t$, so replacing $N$ by $x$ costs at most $\log x$. This proves (3). $\square$

This is the precision of Stirling's estimate we need for elementary prime counting. The later lesson on the Gamma function gives the sharper formula and its constant.

2. A binomial coefficient measures primes

Consider the integer $\binom{2n}{n}$. Every prime between $n$ and $2n$ divides it. Conversely, no prime contributes more than the largest power of that prime below $2n$. These two observations give opposite counting bounds.

Theorem 2.1 (Chebyshev's bounds). For $x\ge1$,

For $x\ge2$ there is an absolute constant $C$ such that

Moreover,

Proof. We first prove a bound for the product $P(N)=\prod_{p\le N}p$ by strong induction on the positive integer $N$. The bound is $P(N)<4^N$; it holds at $N=1,2$. If $N=2m\ge4$, this even integer is composite, so $P(2m)=P(2m-1)<4^{2m-1}<4^{2m}$. If $N=2m+1$, every prime in $(m+1,2m+1]$ divides $\binom{2m+1}{m}$: it occurs in the numerator $(m+2)\cdots(2m+1)$ and not in $m!$. The two equal central entries of row $2m+1$ of Pascal's triangle have sum strictly less than the sum of the whole row. Therefore

and

This closes the induction. Taking logarithms and putting $N=\lfloor x\rfloor$ proves (4).

For a prime $p$, counting the multiples of $p^k$ in a factorial gives

Consequently,

Each summand is $0$ or $1$, and vanishes if $p^k>2n$. Multiplying by $\log p$ and summing over primes gives

The central entry is the largest of the $2n+1$ binomial coefficients, whose sum is $4^n$. Hence

For arbitrary real $x\ge2$, take $n=\lfloor x/2\rfloor$ and use monotonicity of $\psi$. Since $0\le x-2n<2$, this proves (5).

Now regroup the prime powers:

Terms with $x^{1/k}<2$ are zero. Set $c=2\log2$. The term with $k=2$ is at most $c\sqrt x$. Every term with $k\ge3$ is at most $cx^{1/3}$, and there are at most $\log x/\log2$ such terms. Thus

Because $x^{-1/6}\log x$ is bounded on $[2,\infty)$, the right side is $O(\sqrt x)$. Equations (4), (5) and (8) imply upper and lower bounds proportional to $x$ for both $\theta$ and $\psi$, after increasing a fixed threshold if necessary.

For the lower bound on $\pi$, use $\theta(x)\le\pi(x)\log x$. For the upper bound, there are at most $\sqrt x$ primes up to $\sqrt x$, and every larger prime contributes at least $\tfrac12\log x$ to $\theta(x)$. Therefore

Together these inequalities prove (6). The constants can be enlarged to include all $x\ge2$. $\square$

The theorem determines the scale of prime counting. It does not show that the ratio $\psi(x)/x$ tends to a limit. In particular, a two-sided comparison cannot be replaced by an asymptotic equality.

Worked example: the prime product induction

For $N\le20$, the product in the induction changes only at a prime:

For example, at $N=7$, the induction uses $P(4)=6$ and $\binom73=35$, whose product is $210$. At $N=8$, no new prime is introduced. The proof controls the whole product, without requiring an estimate for the number of primes in each individual interval.

3. Factorials determine reciprocal prime averages

The convolution identity $\log n=\sum_{d\mid n}\Lambda(d)$ from the preceding lesson gives an exact factorial identity:

The error in replacing a floor by its argument is small here because Chebyshev's theorem already bounds the total weight $\psi(x)$.

Theorem 3.1 (Mertens's weighted estimates). For $x\ge2$,

There is a real constant $M$ such that

Proof. In (9), $|\lfloor x/n\rfloor-x/n|<1$ and $\Lambda(n)\ge0$. Thus

Apply (3) and divide by $x$ to get (10). The contribution from higher prime powers is bounded independently of $x$, since

Subtracting it proves (11).

Write $E(x)=A(x)-\log x$, which is bounded for $x\ge2$. Partial summation, including the prime $2$, yields

The integral with $E$ converges absolutely at infinity. Define

The difference from this limiting constant is bounded by

This proves (12). $\square$

The definition of $M$ by a bounded-error integral proves its existence. To identify it in terms of primes and Euler's constant, we must connect a sharp cutoff to the smoothed sum encoded by zeta. That connection requires keeping a constant which disappears if both sums are estimated only up to $O(1)$.

4. Exponential smoothing and Euler's constant

We need one real integral. It will also explain why Euler's constant, rather than an arbitrary constant, appears in a prime product.

Lemma 4.1. With $\gamma=\lim_{N\to\infty}(H_N-\log N)$ and $H_N=\sum_{j=1}^N1/j$,

Proof. For every positive integer $N$, integration by parts gives

For the integration by parts, use the primitive $[1-(1-v)^{N+1}]/(N+1)$, which is zero at $v=0$. Its product with $\log v$ tends to zero there. For the last equality put $w=1-v$ and use $1+w+\cdots+w^N$.

Changing variables $u=Nv$ now gives

Extend the integrand by zero for $u>N$. Its absolute value is bounded by $e^{-u}|\log u|$, because $(1-u/N)^N\le e^{-u}$ on $[0,N]$. This bound is integrable on $(0,\infty)$: $|\log u|$ is integrable at zero and exponential decay controls infinity. Pointwise convergence and dominated convergence show that the left side tends to the integral in (13). The right side tends to $-\gamma$. $\square$

Theorem 4.2 (Mertens's product and its constant). The constant in (12) is

where the series is absolutely convergent. Moreover, for $x\ge2$,

Proof. For $\delta>0$, partial summation and $B(t)\ll1+\log\log t$ give

The boundary term at infinity vanishes, and $B(1)=0$. Put $a=\log2$. For $v\ge a$, (12) says $B(e^v)=\log v+M+O(1/v)$. For $0<v<a$, $B(e^v)=0$. Thus the difference between the last integral in (16) and

tends to zero as $\delta\downarrow0$. To verify this explicitly, the integral over $(0,a)$ is $O(\delta)$, since $|\log v|+|M|$ is integrable there. For $\delta<1/a$, the remaining error is at most a constant times

Use $u=\delta v$ and (13) in the main integral. We obtain

Let

This converges absolutely, because $\sum_{k\ge2}1/(kp^k)\le1/[p(p-1)]$. The logarithmic Euler product proved in the preceding lesson, together with dominated convergence for the terms with $k\ge2$, gives

On the other hand, the residue-one Laurent expansion of zeta at $1$ gives $\log\zeta(1+\delta)=\log(1/\delta)+O(\delta)$. Therefore

The power series for the logarithm gives

so (18) is exactly (14), including absolute convergence.

Finally,

Here the omitted tail of the higher powers is $O(1/x)$, by comparison with $\sum_{n>x}1/[n(n-1)]$. Exponentiation, using $e^r=1+O(r)$ for $r\to0$, proves (15). The bound extends to $2\le x$ below any fixed threshold by changing its constant. $\square$

The smoothing uses the variable $v=\log t$. At $\delta=1/\log x$, its effective scale agrees with the cutoff $t\le x$, but its constant term differs by $-\gamma$. Matching scales alone would not identify the product constant.

5. The different forms of the prime number theorem

For $x>1$, we use

The principal value uses symmetric cutoffs around $t=1$. The difference is the fixed constant $\operatorname{li}(2)$, approximately $1.045164$. The two functions therefore have the same asymptotic expansions at infinity, but are different functions.

Proposition 5.1. As $x\to\infty$,

Proof. For each fixed positive integer $m$, put $I_m(x)=\int_2^x dt/\log^m t$. The derivative of $t/\log^m t$ is $1/\log^m t-m/\log^{m+1}t$, hence

Apply this with $m=1,2,3$. It gives the three displayed terms, a fixed constant, and $6I_4(x)$. Splitting this last integral at $\sqrt x$ shows it is $O(x/\log^4x)$: the lower portion is $O(\sqrt x)$, and $\log t\ge\tfrac12\log x$ on the upper portion. The fixed constants, including $\operatorname{li}(2)$, are absorbed by the same error. $\square$

Theorem 5.2 (equivalent prime number theorems). The following four assertions are equivalent:

Proof. Equation (8) shows that $\psi(x)-\theta(x)=o(x)$, so the first two assertions are equivalent. If $\theta(x)\sim x$, equation (1) gives

For the error estimate, use $\theta(t)\ll t$ and split $\int_2^x dt/\log^2t$ at $\sqrt x$ as in the preceding proof.

Conversely, if $\pi(x)\sim x/\log x$, equation (2) yields

Indeed, $\pi(t)\ll t/\log t$ implies $\int_2^x\pi(t)\,dt/t\ll x/\log x$, again by splitting at $\sqrt x$. Finally, (19) implies $\operatorname{li}(x)\sim x/\log x$, so the last two assertions are equivalent. $\square$

The extra terms of (19) explain why $\operatorname{li}$ is a more refined candidate than $x/\log x$. This proposition does not prove that those extra terms approximate $\pi$ with a particular error. That requires the stronger analytic prime number theorem developed later.

Worked example: three ways to count the same primes

The table uses the principal-value $\operatorname{li}$ defined above. The values of $\theta$ and $\psi$ are rounded to three decimal places, and the two approximations to two places.

For example, $\psi(100)-\theta(100)$ adds $\log2$ at $4,8,16,32,64$, $\log3$ at $9,27,81$, $\log5$ at $25$, and $\log7$ at $49$. The difference is $5\log2+3\log3+\log5+\log7$. The table illustrates the different weights; three finite rows do not establish an asymptotic theorem.

6. Exercises

1. Easy: separating prime powers. Prove the explicit bound (8) directly from (4) and (7), including the range $2\le x<8$. Explain why it implies an error $O(\sqrt x)$ even though its second displayed term contains a logarithm.

2. Medium: a prime between $n$ and $2n$. Prove Bertrand's postulate: for every positive integer $n$ there is a prime $p$ with $n<p\le2n$. Use a central binomial coefficient for large $n$, and give an explicit finite verification for the remaining integers. You may use (4), but not the prime number theorem.

3. Medium: a bounded Möbius average. Prove $|\sum_{n\le x}\mu(n)/n|\le1$ for every real $x\ge1$.

4. Medium: locating a possible limit. Deduce from (10) that

   $$\liminf_{x\to\infty}\frac{\psi(x)}x\le1 \le\limsup_{x\to\infty}\frac{\psi(x)}x.$$

   Explain why this is compatible with failure of the prime number theorem.

5. Hard: comparing the smoothed and sharp cutoffs. Put $\delta=1/\log x$. Prove directly from (12), before identifying $M$, that

   $$\log\zeta(1+\delta) -\sum_{p\le x}\log(1-1/p)^{-1}\longrightarrow-\gamma.$$

   Identify the constant in Mertens's product from this limit and the Laurent expansion of zeta. Control the region near zero after rescaling the logarithmic variable; pointwise convergence alone is insufficient.

6. Medium: counting lattice points below a hyperbola. Let $d(n)$ count the positive divisors of $n$. Prove Dirichlet's estimate

   $$\sum_{n\le x}d(n)=x\log x+(2\gamma-1)x+O(\sqrt x).$$

   Explain geometrically why using a square-root cutoff improves the error obtained from $\sum_{a\le x}\lfloor x/a\rfloor$. Evaluate the exact count at $x=16$.

7. Solutions

Solution 1. In (7), the $k=1$ term is $\theta(x)$. If $k=2$ occurs, (4) bounds it by $(2\log2)\sqrt x$. For each $k\ge3$ occurring, $x^{1/k}\le x^{1/3}$, and there are at most $\log x/\log2$ terms. Their total is at most $2x^{1/3}\log x$. If $2\le x<8$, none of the latter terms occurs, so the same nonnegative upper bound remains valid. The difference itself is nonnegative by definition. Finally $x^{1/3}\log x=\sqrt x(x^{-1/6}\log x)$, and the factor in parentheses is bounded: differentiation puts its maximum at $x=e^6$, apart from endpoints. This proves both claims.

Solution 2. Suppose $n\ge512$ and there is no prime in $(n,2n]$. For each prime $p\le\sqrt{2n}$, the valuation argument in Theorem 2.1 shows that the power of $p$ dividing $\binom{2n}{n}$ is at most $2n$. There are at most $\sqrt{2n}$ such primes, so their combined contribution is at most $(2n)^{\sqrt{2n}}$.

For $p>\sqrt{2n}$, the valuation has only its $k=1$ summand and is at most one. Primes in $(2n/3,n]$ have valuation zero, since $\lfloor2n/p\rfloor=2$ and $\lfloor n/p\rfloor=1$. Primes above $n$ do not exist by the supposition. Thus the remaining contribution is at most $\prod_{p\le2n/3}p<4^{2n/3}$, by (4). Combining this with the central-coefficient lower bound gives

It would follow that

Both terms on the right decrease for $n\ge512$. For the first, differentiation gives $\sqrt2 n^{-3/2}(1-\tfrac12\log(2n))<0$. For the second, the numerator of the derivative is $2n/(2n+1)-\log(2n+1)<0$. At $n=512$, the right side is less than $(320+11)\log2/512$, because $\sqrt{1024}=32$, $\log1024=10\log2$, and $\log1025<11\log2$. This is smaller than $\log4/3$, since $331/512<2/3$. Equation (20) is impossible.

For $1\le n<512$, use the following increasing chain of primes:

Each member after the first is less than twice its predecessor. Every integer $2\le n<512$ lies between consecutive members, say $q\le n<r$; then $n<r<2q\le2n$. For $n=1$ take $p=2$. For completeness, trial division verifies primality of the larger members: the relevant odd-prime remainders, excluding $3$ and $5$ which are handled by digit sum and last digit, are

They are odd, and their digit sums are not divisible by $3$; the smaller members are checked in the same way. Thus the finite verification uses only proved prime identities and elementary division.

Solution 3. Put $N=\lfloor x\rfloor$. Möbius inversion and a finite rearrangement give

It follows that

The term with $n=1$ in the last sum is zero. The remaining $N-1$ terms each have absolute value less than or equal to one. The triangle inequality therefore bounds the right side in absolute value by $N$. Divide by $N\ge1$. The sum at real $x$ is the same as at $N$, proving the stated bound.

Solution 4. Partial summation gives

If the liminf of $\psi(t)/t$ were greater than $1$, there would be $\varepsilon>0$ and $X$ such that $\psi(t)/t\ge1+\varepsilon$ for all $t\ge X$. Since the boundary term is nonnegative, (21) would imply a lower bound $(1+\varepsilon)\log x+O(1)$, contradicting (10). If the limsup were less than $1$, then $\psi(t)/t\le1-\varepsilon$ eventually. In this case the boundary term is bounded, and (21) gives an upper bound $(1-\varepsilon)\log x+O(1)$, again a contradiction. Therefore $1$ lies between the liminf and limsup. This does not force those two quantities to agree.

Solution 5. Let $X=\log x=1/\delta$ and use (16). Substituting $u=\delta v$ and noting $\int_0^\infty e^{-u}du=1$ gives the exact identity

Write $B(e^v)=\log v+M+R(v)$ for $v\ge a=\log2$, with $|R(v)|\le C/v$. On $u\ge a\delta$, the integrand in parentheses equals $\log u+R(u/\delta)-R(1/\delta)$. The integral of the error is at most

On $0<u<a\delta$, $B(e^{u/\delta})=0$ and $B(e^{1/\delta})=\log(1/\delta)+M+O(\delta)$. The absolute integral over this interval is $O(\delta\log(1/\delta))$. The omitted integral of $|\log u|$ over the same interval is also $O(\delta\log(1/\delta))$. Hence the difference tends to $\int_0^\infty e^{-u}\log u\,du=-\gamma$.

The difference between the higher-prime-power sums $\sum_{p,k\ge2}p^{-k(1+\delta)}/k$ and $\sum_{p\le x,k\ge2}p^{-k}/k$ tends to zero by absolute convergence and dominated convergence. Adding these sums proves the requested logarithmic comparison. Since $\log\zeta(1+\delta)=\log X+o(1)$, the sharp logarithmic sum equals $\log\log x+\gamma+o(1)$. The error estimate and existence argument of Theorem 3.1 give its form $\log\log x+K+O(1/\log x)$, so $K=\gamma$. Taking the negative exponential recovers the constant $e^{-\gamma}$ in (15).

Solution 6. The divisor sum counts ordered lattice points $(a,b)$ with positive integer coordinates and $ab\le x$. Put $m=\lfloor\sqrt x\rfloor$. Every such point has $a\le m$ or $b\le m$: if both coordinates were at least $m+1$, their product would exceed $x$. The intersection of these two sets is the whole $m$ by $m$ square, because $m^2\le x$. Inclusion--exclusion gives the exact identity

The definition of $\gamma$ also gives $H_m=\log m+\gamma+O(1/m)$. To see the error, subtract successive values of $H_j-\log j$: their positive differences are $\log(1+1/j)-1/(j+1)=O(1/j^2)$, whose tail is $O(1/m)$. For $x\ge4$, $m=\sqrt x+O(1)$, so $2\log m=\log x+O(x^{-1/2})$ and $m^2=x+O(\sqrt x)$. Substitute these into (22); the terms $x/m$ and $m$ are both $O(\sqrt x)$. Enlarging the constant covers $1\le x<4$ and proves the result.

Figure 1. The exact decomposition used in (22), at $x=16$. The vertical part and horizontal part each contain $33$ lattice points. Their square overlap contains $16$, giving $33+33-16=50$. Points and boundary are shown at their actual coordinates.

Summing floors all the way to $a=x$ introduces $O(x)$ unit errors. The two short sums in (22) each have only $m$ terms, so their total floor error is $O(\sqrt x)$. At $x=16$, the short floor sum is $16+8+5+4=33$, and the exact answer is $2\cdot33-16=50$.

Freely readable sources

• D. Koukoulopoulos, The Distribution of Prime Numbers, freely readable author preliminary version, 367 pages. Chapters 2–3: Chebyshev, the hyperbola method and Mertens estimates.