Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated


Source. Equation (9), printed p. 87 (PDF p. 3), is attributed there to Hardy–Ramanujan. This page supplies a complete proof of the needed special case; it does not reconstruct the general theorem in the cited collected papers.

Put

θ=1110,I=θlog⁡θ−θ+1>0,c=I4.\theta=\frac{11}{10},\qquad I=\theta\log\theta-\theta+1>0,\qquad c=\frac I4.

Statement. As x→∞x\to\infty,

#{n≤x:Ω(n)≥θlog⁡log⁡x}≤x(log⁡x)−I+o(1)=o ⁣(x(log⁡x)c).\#\{n\le x:\Omega(n)\ge\theta\log\log x\} \le x(\log x)^{-I+o(1)} =o\!\left(\frac{x}{(\log x)^c}\right).

Here Ω\Omega counts prime factors with multiplicity. The same fixed c>0c>0 is used in the ensuing upper bound; optimizing it is not a claim of this compilation.

Full proof

For fixed 1<z<21<z<2, define a nonnegative multiplicative function gg by g(1)=1g(1)=1 and

g(pa)=(z−1)za−1(a≥1).g(p^a)=(z-1)z^{a-1}\qquad(a\ge1).

At a prime power, 1+∑b=1ag(pb)=za1+\sum_{b=1}^a g(p^b)=z^a. Multiplication over the prime factors proves zΩ(n)=∑d∣ng(d)z^{\Omega(n)}=\sum_{d\mid n}g(d). Therefore

∑n≤xzΩ(n)=∑d≤xg(d)⌊xd⌋≤x∏p≤x(1+∑a≥1g(pa)pa)=x∏p≤x(1+z−1p−z).\begin{aligned} \sum_{n\le x}z^{\Omega(n)} &=\sum_{d\le x}g(d)\left\lfloor\frac xd\right\rfloor\\ &\le x\prod_{p\le x}\left(1+\sum_{a\ge1}\frac{g(p^a)}{p^a}\right) =x\prod_{p\le x}\left(1+\frac{z-1}{p-z}\right). \end{aligned}

The geometric series converge because z<2≤pz<2\le p. Moreover

log⁡(1+z−1p−z)≤z−1p−z=z−1p+Oz(p−2).\log\left(1+\frac{z-1}{p-z}\right) \le\frac{z-1}{p-z} =\frac{z-1}{p}+O_z(p^{-2}).

The reciprocal-prime estimate obtained from the prime number theorem and convergence of ∑pp−2\sum_p p^{-2} show that the product is at most (log⁡x)z−1+o(1)(\log x)^{z-1+o(1)}. On the set in the statement, zΩ(n)≥exp⁡(θlog⁡zlog⁡log⁡x)z^{\Omega(n)}\ge\exp(\theta\log z\log\log x). Division by this threshold gives the bound

x(log⁡x)z−1−θlog⁡z+o(1).x(\log x)^{z-1-\theta\log z+o(1)}.

Set z=θz=\theta. The exponent is −I+o(1)-I+o(1), and I>0I>0 because I=∫1θlog⁡t dtI=\int_1^\theta\log t\,dt. Since c<Ic<I, the asserted little-oh estimate follows.

Scope. The source requires only a sufficiently small positive exponent in the exceptional-set bound. This elementary expansion gives one explicit admissible choice relative to the classical prime number theorem; no additional normal-order theorem is implicitly imported into the later proof.