The Hardy--Ramanujan inequality for sifted sets and its applications

Abstract

The well-known Hardy--Ramanujan inequality states that if $\omega (n)$ denotes the number of distinct prime factors of a positive integer $n$, then there is an absolute constant $C>0$ such that uniformly for $x\ge 2$ and $k\in \mathbb{N}$, \[\#\{n\le x\colonω(n)=k\}\ll\frac{x(\log\log x+C)^{k-1}}{(k-1)!\log x}.\] A myriad of generalizations and variations of this inequality have been discovered. In this paper, we establish a weighted version of this inequality for sifted sets, which generalizes an earlier result of Halász and implies Timofeev's theorems on shifted primes. We then explore its applications to a variety of intriguing problems, such as large deviations of $\omega$ on subsets of integers, the Erdős multiplication table problem, divisors of shifted primes, and the image of the Carmichael $\lambda$-function. Building on the same circle of ideas, we also generalize Troupe's result on the normal order of $\omega (s(n))$ for the sum-of-proper-divisors function $s(n)$, confirming for the first time the weighted version of a special case of a 1992 conjecture by Erdős, Granville, Pomerance, and Spiro.

44 pages