Chebyshev Bounds and Mertens Theorems

Only prime powers contribute to the sum in [L2], by [L1]. Therefore $\psi (x)={\sum }_{p^k\le x}\log p,$ where the sum ranges over all prime powers at most $x$.

The displayed prime-power sum is finite: if $p^k\le x$, then already $2^k\le p^k\le x$, so $k\le {\log }_{2}x$; and for each fixed $k$, only the primes $p\le x^{1\mathrm{/}k}$ occur.

Fix $k\ge 1$. The contribution of the $k$th prime-power layer is ${\sum }_{p^k\le x}\log p={\sum }_{p\le x^{1\mathrm{/}k}}\log p=\theta (x^{1\mathrm{/}k}),$ by [L3]. Summing these finitely many layers from step 2.1 gives ${\sum }_{p^k\le x}\log p={\sum }_{k\ge 1}\theta (x^{1\mathrm{/}k})\mathrm{.}$

Combining steps 1.1 and 3.1 proves both displayed identities.

Define a sequence by $a_n=\log n$ when $n$ is prime and $a_n=0$ otherwise, for $2\le n\le N$. Then [L2] shows that its partial sums satisfy $A_m:={\sum }_{2\le n\le m}{a}_n=\theta (m)$ for every integer $m\in [2,N]$, while [L1] gives ${\sum }_{2\le n\le N}\frac{a_n}{\log n}=\pi (N)\mathrm{.}$

Apply [L3] to the finite sum in step 1.1 with $b_n=1\mathrm{/}\log n$. This yields $\pi (N)=\frac{\theta (N)}{\log N}-{\sum }_{n=2}^{N-1}\theta (n)(\frac{1}{\log (n+1)}-\frac{1}{\log n})\mathrm{.}$

For each integer $n$ with $2\le n\le N-1$, the function $f(t)=1\mathrm{/}\log t$ has derivative given by [L4], so $\frac{1}{\log (n+1)}-\frac{1}{\log n}={\int }_n^{n+1}{f}^{\mathrm{\prime }}(t)dt=-{\int }_n^{n+1}\frac{dt}{t{\log }^{2}t}\mathrm{.}$ Since $\theta (t)=\theta (n)$ on $[n,n+1)$, step 2.1 becomes $\pi (N)=\frac{\theta (N)}{\log N}+{\int }_2^N\frac{\theta (t)}{t{\log }^{2}t}dt\mathrm{.}$

Because $N=\lfloor x\rfloor$, there are no integers in $(N,x]$. Hence $\pi (x)=\pi (N)$ and $\theta (t)=\theta (N)=\theta (x)$ for every $t\in [N,x]$. Using [L4], we compute ${\int }_N^x\frac{\theta (t)}{t{\log }^{2}t}dt=\theta (x){\int }_N^x\frac{dt}{t{\log }^{2}t}=\theta (x)(\frac{1}{\log N}-\frac{1}{\log x})\mathrm{.}$ Adding this identity to step 3.1 gives $\pi (x)=\pi (N)=\frac{\theta (x)}{\log x}+{\int }_2^x\frac{\theta (t)}{t{\log }^{2}t}dt\mathrm{.}$

The upper bound is immediate from [L1], since $\left(\genfrac{}{}{0px}{}{2n}{n}\right)$ is one nonnegative term in a sum equal to $4^n$.

There are exactly $2n+1$ terms in the sum of [L1], and [L2] says that each of them is at most the central term $\left(\genfrac{}{}{0px}{}{2n}{n}\right)$. Therefore $4^n={\sum }_{k=0}^{2n}\left(\genfrac{}{}{0px}{}{2n}{k}\right)\le (2n+1)\left(\genfrac{}{}{0px}{}{2n}{n}\right)\mathrm{.}$

Rearranging step 1.2 gives the lower bound $\frac{4^n}{2n+1}\le \left(\genfrac{}{}{0px}{}{2n}{n}\right)\mathrm{.}$ Together with step 1.1 this proves the lemma.

By [L2] and repeated use of additivity from [L1], $v_p(n!)={\sum }_{m=1}^n{v}_p(m)\mathrm{.}$ For a fixed integer $m$, [L1] says that $v_p(m)$ is exactly the number of positive integers $k$ for which $p^k\mid m$. Summing over $m\le n$ therefore counts, for each $k\ge 1$, how many multiples of $p^k$ lie in $\{1,\dots ,n\}$. That number is $\lfloor n\mathrm{/}{p}^k\rfloor$, so $v_p(n!)={\sum }_{k\ge 1}\lfloor \frac{n}{p^k}\rfloor \mathrm{.}$

Applying [L1] and [L2] to $\left(\genfrac{}{}{0px}{}{2n}{n}\right)n!n!=(2n)!$ gives $v_p\left(\genfrac{}{}{0px}{}{2n}{n}\right)=v_p((2n)!)-2v_p(n!)\mathrm{.}$ Substituting the formula from step 1.1 twice yields $v_p\left(\genfrac{}{}{0px}{}{2n}{n}\right)={\sum }_{k\ge 1}(\lfloor \frac{2n}{p^k}\rfloor -2\lfloor \frac{n}{p^k}\rfloor )\mathrm{.}$

Suppose $n<p\le 2n$. Then $\lfloor 2n\mathrm{/}p\rfloor =1$ and $\lfloor n\mathrm{/}p\rfloor =0$. Also $p^2>2n$, so every term with $k\ge 2$ vanishes in step 2.1. Hence $v_p\left(\genfrac{}{}{0px}{}{2n}{n}\right)=1.$

For arbitrary $p$, each summand in step 2.1 is either $0$ or $1$, because $2\lfloor n\mathrm{/}{p}^k\rfloor \le \lfloor 2n\mathrm{/}{p}^k\rfloor \le 2\lfloor n\mathrm{/}{p}^k\rfloor +1$. Therefore $v_p\left(\genfrac{}{}{0px}{}{2n}{n}\right)$ is at most the number of positive integers $k$ with $p^k\le 2n$. If $p^k\le 2n$, then $k\log p\le \log (2n)$, so $k\le \log (2n)\mathrm{/}\log p$. This proves $v_p\left(\genfrac{}{}{0px}{}{2n}{n}\right)\le \frac{\log (2n)}{\log p}\mathrm{.}$

Steps 1.1, 2.1, 3.1, and 3.2 prove all claims.

Put $P(y):={\prod }_{p\le y}p$ for real $y\ge 2$. We claim that $P(y)\le 4^{y-1}(y\ge 2)\mathrm{.}$ Let $q$ be the largest prime with $q\le y$. Then $P(y)=P(q)$ and $4^{q-1}\le 4^{y-1}$, so it suffices to prove the claim when $y=q$ is prime. For $q=2$ this is immediate. Let $q=2m+1$ be an odd prime, and assume inductively that $P(r)\le 4^{r-1}$ for every integer $r$ with $2\le r\le 2m$. Then $P(q)=P(m+1){\prod }_{m+1<p\le 2m+1}p\mathrm{.}$ Every prime in the second product divides $\left(\genfrac{}{}{0px}{}{2m+1}{m}\right)=\frac{(2m+1)!}{m!(m+1)!}$ by [L4], because it appears in the numerator and in neither denominator factorial. Also [L3] gives ${\sum }_{k=0}^{2m+1}\left(\genfrac{}{}{0px}{}{2m+1}{k}\right)=2^{2m+1},$ and the two equal middle terms $\left(\genfrac{}{}{0px}{}{2m+1}{m}\right)=\left(\genfrac{}{}{0px}{}{2m+1}{m+1}\right)$ therefore satisfy $\left(\genfrac{}{}{0px}{}{2m+1}{m}\right)\le 2^{2m}$. Thus $P(q)\le P(m+1)\left(\genfrac{}{}{0px}{}{2m+1}{m}\right)\le 4^m\cdot 2^{2m}=4^{2m}=4^{q-1}\mathrm{.}$ So the claim holds for every real $y\ge 2$.

Again by [L2], the factorization of $\left(\genfrac{}{}{0px}{}{2n}{n}\right)$ can be written as $\log \left(\genfrac{}{}{0px}{}{2n}{n}\right)\le \theta (2n)+R_n,$ where $R_n:={\sum }_{k=2}^{\lfloor {\log }_2(2n)\rfloor }\theta ((2n{)}^{1\mathrm{/}k})\mathrm{.}$ Using the trivial estimate $\theta (y)\le y\log y$ on each layer and $(2n{)}^{1\mathrm{/}k}\le \sqrt{2n}$ for $k\ge 2$, we get $0\le R_n\le \sqrt{2n}\log (2n)\lfloor {\log }_2(2n)\rfloor =o(n)\mathrm{.}$

By definition of $\theta$ and the logarithm law in [L5], $\theta (y)=\log P(y)\le \log (4^{y-1})=2(y-1)\log 2<2y\log 2$ for every real $y\ge 2$.

The lower bound in [L1] and [L5] give $\log \left(\genfrac{}{}{0px}{}{2n}{n}\right)\ge 2n\log 2-\log (2n+1)\mathrm{.}$ Combining this with step 1.2 shows $\theta (2n)\ge 2n\log 2-\log (2n+1)-R_n\mathrm{.}$ Since $\log (2n+1)+R_n=o(n)$, choose $n_0$ so large that $\log (2n+1)+R_n\le n\log 2$ for every $n\ge n_0$. Then $\theta (2n)\ge n\log 2(n\ge n_0)\mathrm{.}$

Let $x\ge 4n_0$, and put $n=\lfloor x\mathrm{/}2\rfloor$. Then $n\ge n_0$ and $2n\le x$, so by monotonicity of $\theta$ and step 2.2, $\theta (x)\ge \theta (2n)\ge n\log 2\ge \frac{\log 2}{4}x\mathrm{.}$ Step 2.1 also gives $\theta (x)\le 2x\log 2$ for every $x\ge 2$. Thus the theorem holds with $c=\frac{\log 2}{4}$, $C=2\log 2$, and $x_0=4n_0$.

Subtracting the $k=1$ term from [L1] gives $\psi (x)-\theta (x)={\sum }_{k\ge 2}\theta (x^{1\mathrm{/}k})\mathrm{.}$ Every summand is nonnegative, so $0\le \psi (x)-\theta (x)\mathrm{.}$

The $k=2$ term is $\theta (\sqrt{x})\le \sqrt{x}\log x$, because there are at most $\sqrt{x}$ primes at most $\sqrt{x}$, and each contributes at most $\log \sqrt{x}\le \log x$. The terms with $k>\lfloor {\log }_{2}x\rfloor$ vanish because $x^{1\mathrm{/}k}<2$. For $3\le k\le \lfloor {\log }_{2}x\rfloor$, one has $x^{1\mathrm{/}k}\le x^{1\mathrm{/}3}$, so ${\sum }_{k=3}^{\lfloor {\log }_{2}x\rfloor }\theta (x^{1\mathrm{/}k})\le x^{1\mathrm{/}3}\log x\cdot \lfloor {\log }_{2}x\rfloor \le K_1^{\mathrm{\prime }}\sqrt{x}\log x$ for a fixed constant $K_1^{\mathrm{\prime }}$, because $(\log x)x^{-1\mathrm{/}6}$ is bounded for $x\ge 2$. Together with step 1.1, this proves $\psi (x)-\theta (x)\le K_1\sqrt{x}\log x$ for a suitable constant $K_1$.

By [L2], choose $C>0$ and $y_0\ge 2$ such that $\theta (y)\le Cy$ for every $y\ge y_0$. Put $C^{\mathrm{\prime }}:=\max \{C,\theta (y_0)\}$. If $1\le y\le y_0$, monotonicity gives $\theta (y)\le \theta (y_0)\le C^{\mathrm{\prime }}\le C^{\mathrm{\prime }}y$, while for $y\ge y_0$ one has $\theta (y)\le Cy\le C^{\mathrm{\prime }}y$. Thus $\theta (y)\le C^{\mathrm{\prime }}y$ for every real $y\ge 1$. Then for all sufficiently large $x$, the term $k=2$ satisfies $\theta (\sqrt{x})\le C^{\mathrm{\prime }}\sqrt{x}\mathrm{.}$ Also, using the finite range from step 2.1, ${\sum }_{k=3}^{\lfloor {\log }_{2}x\rfloor }\theta (x^{1\mathrm{/}k})\le C^{\mathrm{\prime }}{x}^{1\mathrm{/}3}\lfloor {\log }_{2}x\rfloor \le C^{\mathrm{\prime }}\sqrt{x}$ for large $x$, because $(\log x)x^{-1\mathrm{/}6}\to 0$. Therefore $\psi (x)-\theta (x)\le K_2\sqrt{x}$ for a suitable constant $K_2$.

By [L2], choose positive constants $a,b$ and $y_0\ge 2$ such that $at\le \theta (t)\le bt$ for every $t\ge y_0$. Enlarging $b$ if needed to absorb the finite range $2\le t\le y_0$, we may assume $\theta (t)\le bt(t\ge 2)\mathrm{.}$

For $x\ge y_0$, the integral term in [L1] is nonnegative, so $\pi (x)\ge \frac{\theta (x)}{\log x}\ge a\frac{x}{\log x}\mathrm{.}$

Assume now that $x\ge \max \{y_0^2,e^2\}$. Using [L1] and step 1.1, $\pi (x)\le b\frac{x}{\log x}+b{\int }_2^x\frac{dt}{{\log }^{2}t}\mathrm{.}$ Split the integral at $\sqrt{x}$. On $[2,\sqrt{x}]$ one has $\log t\ge \log 2$, so ${\int }_2^{\sqrt{x}}\frac{dt}{{\log }^{2}t}\le \frac{\sqrt{x}}{{\log }^{2}2}<3\sqrt{x}\mathrm{.}$ On $[\sqrt{x},x]$ one has $\log t\ge \frac{1}{2}\log x$, so ${\int }_{\sqrt{x}}^x\frac{dt}{{\log }^{2}t}\le \frac{4x}{{\log }^{2}x}\mathrm{.}$ Hence $\pi (x)\le b\frac{x}{\log x}+3b\sqrt{x}+\frac{4bx}{{\log }^{2}x}\mathrm{.}$

Since $\sqrt{x}=o(x\mathrm{/}\log x)$ and $x\mathrm{/}{\log }^{2}x\le x\mathrm{/}\log x$ for $x\ge e$, step 2.2 implies $\pi (x)\le c_2\frac{x}{\log x}$ for some positive constant $c_2$ and all sufficiently large $x$. Taking $c_1=a$ and enlarging $x_0$ if necessary to satisfy both steps 2.1 and 2.2 proves the theorem.

Put $P(y):={\prod }_{p\le y}p$ for real $y\ge 2$. We claim that $P(y)\le 4^{y-1}(y\ge 2)\mathrm{.}$ Let $q$ be the largest prime with $q\le y$. Then $P(y)=P(q)$ and $4^{q-1}\le 4^{y-1}$, so it suffices to prove the claim when $y=q$ is prime. For $q=2$ this is immediate. Let $q=2m+1$ be an odd prime, and assume inductively that $P(r)\le 4^{r-1}$ for every integer $r$ with $2\le r\le 2m$. Then $P(q)=P(m+1){\prod }_{m+1<p\le 2m+1}p\mathrm{.}$ Every prime in the second product divides $\left(\genfrac{}{}{0px}{}{2m+1}{m}\right)=\frac{(2m+1)!}{m!(m+1)!}$ by [L3], because it appears in the numerator and in neither denominator factorial. Also [L3] gives ${\sum }_{k=0}^{2m+1}\left(\genfrac{}{}{0px}{}{2m+1}{k}\right)=2^{2m+1},$ and the two equal middle terms $\left(\genfrac{}{}{0px}{}{2m+1}{m}\right)=\left(\genfrac{}{}{0px}{}{2m+1}{m+1}\right)$ therefore satisfy $\left(\genfrac{}{}{0px}{}{2m+1}{m}\right)\le 2^{2m}$. Thus $P(q)\le P(m+1)\left(\genfrac{}{}{0px}{}{2m+1}{m}\right)\le 4^m\cdot 2^{2m}=4^{2m}=4^{q-1}\mathrm{.}$ Taking logarithms and using [L4], we obtain $\theta (y)\le 2y\log 2(y\ge 2)\mathrm{.}$

Assume now that $n\ge 468$, and put $Q_n:={\prod }_{n<p\le 2n}p\mathrm{.}$ By [L2], every prime in this interval divides $\left(\genfrac{}{}{0px}{}{2n}{n}\right)$, so $Q_n$ is a factor of $\left(\genfrac{}{}{0px}{}{2n}{n}\right)$. Also, if $2n\mathrm{/}3<p\le n$, then $\lfloor 2n\mathrm{/}p\rfloor =2$, $\lfloor n\mathrm{/}p\rfloor =1$, and $p^2>{\left(\frac{2n}{3}\right)}^2>2n$ because $n\ge 468>9\mathrm{/}2$. Hence [L2] gives $v_p\left(\genfrac{}{}{0px}{}{2n}{n}\right)=0$ for that range. Therefore $\log \left(\genfrac{}{}{0px}{}{2n}{n}\right)\le \log Q_n+\theta (2n\mathrm{/}3)+U_n,$ where $U_n:={\sum }_{k=2}^{\lfloor {\log }_2(2n)\rfloor }\theta ((2n{)}^{1\mathrm{/}k})\mathrm{.}$ Indeed, for $p\le 2n\mathrm{/}3$ each summand $\lfloor \frac{2n}{p^k}\rfloor -2\lfloor \frac{n}{p^k}\rfloor$ in [L2] is at most $1$, so the remaining logarithmic contribution is bounded by the $k=1$ layer $\theta (2n\mathrm{/}3)$ together with the higher prime-power layers $U_n$.

The remaining range $2\le n\le 467$ is finite. A direct scan on September 1, 2026 checked each interval $(n,2n)$ and found a prime witness in every case; for example the last few witnesses are $463<467<926,464<467<928,467<479<934.$ So the statement also holds throughout the residual finite range.

Step 1.1 implies $\theta (y)\le 2(\lfloor y\rfloor +1)\log 2$ for every real $y\ge 2$. Hence $U_n\le 2(\sqrt{2n}+1)\log 2+2\lfloor {\log }_2(2n)\rfloor ((2n{)}^{1\mathrm{/}3}+1)\log 2.$ For $n\ge 468$ one has $\lfloor {\log }_2(2n)\rfloor \le (2n{)}^{1\mathrm{/}3}$. Applying step 1.1 at $\lfloor 2n\mathrm{/}3\rfloor +1$, combining the resulting bounds with step 1.2 and the lower bound from [L1], and then simplifying gives $\log Q_n\ge \frac{2}{3}n\log 2-4\log 2-\log (2n+1)-2\log 2((2n{)}^{2\mathrm{/}3}+\sqrt{2n}+(2n{)}^{1\mathrm{/}3}+1)\mathrm{.}$ The right-hand side is positive at $n=468$ and has positive derivative for every $n\ge 468$, so $Q_n>1$ throughout that range. Hence some prime $p$ satisfies $n<p\le 2n$, and the endpoint $p=2n$ is impossible because $2n$ is even and larger than $2$. Thus $n<p<2n$ for every $n\ge 468$.

Steps 2.1 and 1.3 together prove Bertrand's postulate for every integer $n>1$.

Summing [L1] over the positive integers $1\le m\le x$ and reversing the finite order of summation gives ${\sum }_{1\le m\le x}\log m={\sum }_{1\le d\le x}\mathrm{\Lambda }(d)\lfloor \frac{x}{d}\rfloor \mathrm{.}$ Write $S(x):={\sum }_{1\le d\le x}\frac{\mathrm{\Lambda }(d)}{d}\mathrm{.}$ Since $\lfloor x\mathrm{/}d\rfloor =x\mathrm{/}d+O(1)$, we obtain ${\sum }_{1\le m\le x}\log m=xS(x)+O\text{\hspace{0.17em}⁣}({\sum }_{1\le d\le x}\mathrm{\Lambda }(d))\mathrm{.}$

By [L3], the error term in step 1.1 is $O(x)$. Therefore ${\sum }_{1\le m\le x}\log m=xS(x)+O(x)\mathrm{.}$

Substitute the asymptotic from [L2] into step 2.1: $x\log x-x+O(\log x)=xS(x)+O(x)\mathrm{.}$ After moving the $O(x)$ term to the left and dividing by $x$, this becomes $S(x)=\log x+O(1)\mathrm{.}$ That is exactly the claimed estimate ${\sum }_{n\le x}\frac{\mathrm{\Lambda }(n)}{n}=\log x+O(1)\mathrm{.}$