Past exam of the mathematics course of the University of Cambridge / 2016 / iii / Paper 124 / 3

Use the convention that a z-sieved number is a positive integer with no prime factor strictly below $z$; $1$ is included. Such integers are also called rough numbers. Using instead exclusion of primes at most $z$ changes an endpoint convention, not the following fixed-$u$ asymptotic.

The Buchstab function is the continuous function $w:[1,\infty )\to \mathbb{R}$ determined bySuccessive integration over intervals of length one determines the Buchstab function uniquely from its initial values.

A standard fixed-$u$ form of Buchstab theorem states that, for each fixed $u>1$, as $z\to \infty$,For $1<u\le 2$, this agrees with the Prime number theorem, since apart from an immaterial endpoint the z-sieved numbers in this range are $1$ and the primes from $z$ to $z^u$. The restriction $u>1$ matters: at $u=1$ the count is bounded, so the displayed asymptotic does not hold there.

Put $c=e^{-\gamma }$, where $\gamma$ is the Euler--Mascheroni constant, and let $f(u)=w(u)-c$. The Buchstab function equation becomesThe given Gamma function bound implies $uf(u)\to 0$. Indeed,so $u/\Gamma (u+1)\to 0$.

Suppose first that $f\ge 0$ throughout an interval $[u,u+1]$, with $u\ge 1$. The delay differential equation and integration successively on $[u+1,u+2]$, $[u+2,u+3]$, and so on propagate nonnegativity to the entire tail $[u,\infty )$. In particular, $vf(v)$ is nonnegative and nondecreasing for $v\ge u+1$. Its limit is zero, so it is identically zero there. Thus $f=0$ on that tail.

The delay differential equation then propagates this equality backwards: if $f=0$ for $v\ge a$, then $f(v-1)=0$ for $v>\max (a,2)$. Repeating finitely many times would give $f=0$ on $(1,2)$, contradicting $f(v)=1/v-c$ there. Hence every interval $[u,u+1]$ contains a point where $f<0$.

If instead $f\le 0$ on $[u,u+1]$, the same propagation makes $vf(v)$ nonpositive and nonincreasing on the tail. Its limit zero again forces it to vanish, giving the same contradiction. Thus every such interval also contains a point where $f>0$. The oscillation of the Buchstab function is therefore strict on every unit interval:

For an additive arithmetic function $f$, one standard form of the Turán-Kubilius inequality usesIt states, with an absolute constant,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 }_{p}1/(p(p-1))\le 1$, 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 yieldThe 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)\ge 0.99L$ and $\omega (\gcd (a,b))\le 0.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 givesMarkov 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,On the other hand, apply the proved concentration estimate at $N^2$. Since $\log \log (N^2)=L+\log 2$, for large $N$ every integer $m\le N^2$ with $\omega (m)\ge 1.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 the multiplication-table upper bound, using distinct prime factors alone: