Skip to main content
2 of 4
added 714 characters in body
Terry Tao
  • 114.1k
  • 33
  • 462
  • 539

This question is related to the results in

Bergelson, Vitaly; Richter, Florian K., Dynamical generalizations of the prime number theorem and disjointness of additive and multiplicative semigroup actions, Duke Math. J. 171, No. 15, 3133-3200 (2022). ZBL1514.37018.

Given a finite set $B$ of natural numbers, they introduce the quantity $$ {\mathbb E}_{n \in B}^{\log} {\mathbb E}_{m \in B}^{\log} \Phi(n,m) \tag{1}$$ where $\Phi(n,m) := \mathrm{gcd}(n,m)-1$ and ${\mathbb E}_{n \in B}^{\log}$ denotes the logarithmic averaging operator $$ {\mathbb E}_{n \in B}^{\log} f(n) := \frac{\sum_{n \in B} f(n)/n}{\sum_{n \in B} 1/n}.$$ In Proposition 2.1 of that paper, they establish the Turan-Kubilius type inequality $$ |{\mathbb E}_{n \in [N]} a_n - {\mathbb E}_{q \in B}^{\log} {\mathbb E}_{n \in [N]: q|n} a_{n}| \leq ({\mathbb E}_{n \in B}^{\log} {\mathbb E}_{m \in B}^{\log} \Phi(n,m))^{1/2} + o(1)$$ in the limit as $N \to \infty$ (one can be more precise about the $o(1)$ term if desired). In fact their proof shows the stronger bound $$ {\mathbb E}_{q \in B}^{\log} |{\mathbb E}_{n \in [N]} a_n - {\mathbb E}_{n \in [N]: q|n} a_{n}| \leq ({\mathbb E}_{n \in B}^{\log} {\mathbb E}_{m \in B}^{\log} \Phi(n,m))^{1/2} + o(1);$$ this is not quite the dual of Lemma 2.4 of that paper, but can be proven by a similar method. This gives the type of bound you seek as long as the quantity (1) is small.

In that paper it was noted that examples of sets of $B$ with small (1) include the sets of numbers with at most $k$ prime factors, for a fixed $k$. In a recent paper of mine, I worked out what the maximal size of $B$ could be while still keeping (1) small (this also answered a question of Erdős and Graham); see Proposition 2.2 of my paper. The optimal example is essentially the same as the one worked out by you and Will, namely the numbers with at most $o(\sqrt{\log\log n})$ prime factors. (One has to be more careful with this construction if one wants a single set $B$ which works at all scales $N$, rather than working with a single large scale $N$ and permitting $B$ to vary with $N$, but this is a technical detail.)

p.s. the asymptotic formula for counting the number of numbers up to $N$ with exactly $k$ prime factors is sometimes referred to as the Sathé-Selberg formula, see

Sathe, L. G., On a problem of Hardy on the distribution of integers having a given number of prime factors. II, J. Indian Math. Soc., New Ser. 17, 83-141 (1953). ZBL0051.28008.

and

Selberg, Atle, Note on a paper by L. G. Sathe, J. Indian Math. Soc., N. Ser. 18, 83-87 (1954). ZBL0057.28502.

Terry Tao
  • 114.1k
  • 33
  • 462
  • 539