= Solution
For an <additive arithmetic function> $f$, one standard form of the <Turán-Kubilius inequality> uses
$$
A_f(N)=\sum_{p^k\le N}\frac{f(p^k)}{p^k}\left(1-\frac1p\right),\qquad B_f(N)^2=\sum_{p^k\le N}\frac{|f(p^k)|^2}{p^k}.
$$
It states, with an absolute constant,
$$
\frac1N\sum_{n\le N}|f(n)-A_f(N)|^2\ll B_f(N)^2.
$$
For real $f$, this also bounds the <variance> under the <discrete uniform distribution>, because centering at the actual <expectation> minimizes the mean square.
For the <prime omega function>, $f(p^k)=1$. The <Mertens theorem for reciprocal primes> states $\sum_{p\le N}1/p=\log\log N+O(1)$. The contribution of higher <prime powers> is bounded by $\sum_p1/(p(p-1))\le1$, as proved in 1(a). It follows that $A_\omega(N)=\log\log N+O(1)$ and $B_\omega(N)^2\ll\log\log N$. Writing $L=\log\log N$, the <Turán-Kubilius inequality> and <Chebyshev inequality> therefore yield
$$
\boxed{\mathbb P_N(|\omega-L|\ge0.01L)\ll L^{-1}.}
$$
The bounded error in $A_\omega-L$ is absorbed by, for example, using the threshold $0.005L$ around $A_\omega$ for sufficiently large $N$.
For the <multiplication table problem>, call a pair $(a,b)\in[N]^2$ good when $\omega(a),\omega(b)\ge0.99L$ and $\omega(\gcd(a,b))\le0.1L$. The preceding <Chebyshev inequality> excludes only $O(N^2/L)$ pairs by either of the first two conditions. For the <greatest common divisor> condition, <linearity of expectation> under uniform sampling of the two coordinates gives
$$
\frac1{N^2}\sum_{a,b\le N}\omega(\gcd(a,b))=\sum_{p\le N}\left(\frac{\lfloor N/p\rfloor}{N}\right)^2\le\sum_{m=2}^\infty\frac1{m^2}<\infty.
$$
<Markov inequality> therefore excludes only another $O(N^2/L)$ pairs.
The <prime factors> of a product form the union of those of its factors. Consequently, for every good pair,
$$
\omega(ab)=\omega(a)+\omega(b)-\omega(\gcd(a,b))\ge1.88L.
$$
On the other hand, apply the proved concentration estimate at $N^2$. Since $\log\log(N^2)=L+\log2$, for large $N$ every integer $m\le N^2$ with $\omega(m)\ge1.88L$ is exceptional there. There are only $O(N^2/L)$ such integers. Products of good pairs lie in this exceptional set; products having only bad representations are at most as numerous as the bad pairs. This proves \b[the multiplication-table upper bound, using distinct prime factors alone]:
$$
\boxed{\#\{ab:1\le a,b\le N\}\ll\frac{N^2}{\log\log N}=o(N^2).}
$$
Back to article page
