Since \(\omega (n) = \sum _{p\leq n}1_{p\mid n}\), the left-hand side equals, after a change in the order of summation,

Since \(\lfloor x\rfloor =x+O(1)\), this is equal to

using Lemma 2.7 and the trivial estimate \(\pi (X)\ll X\).

Since \(\omega (n) = \sum _{p\leq n}1_{p\mid n}\), the left-hand side is equal to, after expanding the sum and rearranging,

The part of the sum where \(p=q\) is

as in the proof of Lemma 2.1. If \(p\neq q\), then \(p\mid n\) and \(q\mid n\) if and only if \(pq\mid n\), and so the sum over \(n\) is bounded above by

Therefore

By Lemma 2.7 this is \(X(\log \log X+O(1))^2 = X(\log \log X)^2+O(X\log \log X)\). The lemma follows by combining the estimates on the two parts of the sum.

The left-hand side equals

The first summand is at most, by Lemma 2.2,

The second summand is equal to, by Lemma 2.1,

The third summand is equal to

Therefore the main terms cancel, and

as required.

We first show that, for any real \(K\geq 2\),

Write \(n\) as the product of unique prime powers \(n=p_1^{k_1}\cdots p_r^{k_r}\), so that

If \(p_i{\gt}2^K\) then

since \(1+k \leq 2^k\) for all integer \(k\geq 0\) by Bernoulli’s inequality. Therefore

If \(p_i{\lt}2^K\) then, since \(p_i\geq 2\),

using the fact that \(x+1/2\leq 2^x\) for all \(x\geq 0\). Since \(K\geq 2\) the denominator here is \(\geq (1+k_i)/K\), and so \(\frac{k_i+1}{p^{k_i/K}}\leq K\). Therefore

as required.

The second part of the proof is to apply the first part with

(The right-hand side tends to \(\infty \) as \(n\to \infty \), so for sufficiently large \(n\) we have \(K\geq 2\) as required.)

Note that \(2^K= (\log n)^{\frac{2}{2+\epsilon }}\leq (\log n)^{1-\epsilon }\) (since \(1-\epsilon {\gt}\frac{2}{2+\epsilon }\), since \(\epsilon \leq 1\)) and

Taking logarithms of the inequality in the first part,

For any fixed \(\epsilon {\gt}0\), the function \(\frac{(\log \log \log n)(\log \log n)}{(\log 2)(\log n)^{\epsilon }}\to 0\) as \(n\to \infty \), so for sufficiently large \(n\) it is \(\leq \epsilon /2\), and hence

as required.

Let \(P = \prod _{u\leq p\leq v}p\). The left-hand side of the estimate in the lemma can be written as

Using the identity \(\sum _{d\mid m}\mu (d) = 1\) if \(m=1\) and \(0\) otherwise, the fact that \(d\mid (n,P)\) if and only if \(d\mid n\) and \(d\mid P\), and that \(\sum _{n\leq z}1_{d\mid n}=\left\lfloor \frac{z}{d}\right\rfloor \) for any \(z\geq 0\),

Since \(\lfloor X\rfloor = X+O(1)\) for any \(X\), we have

for any \(x,y,d\), and hence

We have \(\sum _{d\mid P}1=\tau (P)=2^k\) where \(k\) is the number of primes in \([u,v]\), which is at most \(v\), so the error term here is \(O(2^v)\). Finally, expanding out the product shows that

Inserting this into the above finishes the proof.