Estimates about prime numbers: a lemma in Bourgain's article

Question

For $n\in \mathbb{N}$ with prime decomposition $n=p_1^{r_1}\cdots p_k^{r_k},p_i\neq p_j$, let $A=\{p_1,\cdots,p_k\}$; then the following holds: \begin{equation} |\{q\in \mathbb{N},q<Q: \text{all prime factors of } q\,\in A\}|<Ce^{c\frac{\log Q}{\log \log Q}}d(n,Q) \end{equation} where $d(n,Q):=|\{m\in \mathbb{N},m<Q: m\mid n\}|$.

This lemma appears below (3.46) in Bourgain's article "Fourier transform restriction phenomena for certain lattice subsets and applications to nonlinear evolution equations".

I'm not familiar with number theory; could you please explain how to deduce this conclusion and give some references on number theory?

Answer 1

Let $q<Q$ be such that all its prime divisors are in $A$. We can write $q=q_0\times r_1^{n_1}\cdots r_s^{n_s}$, where all prime factors of $q_0$ are $<\log Q$ and $\log Q\leq r_1<\cdots<r_s\in A$. Clearly, $q$ is uniquely determined once we have fixed a) $q_0$, b) the set $\{r_1,\ldots,r_s\}$, and c) the integer vector $(n_1,\ldots,n_s)$.

The number of possible $q_0$ is at most the number of $q<Q$ which have all prime factors $<\log Q$. This is a well-studied quantity in analytic number theory (counting 'smooth' or 'friable' numbers), and is $\leq \exp(O(\log Q/\log\log Q))$, which can be shown via elementary methods, see any textbook on analytic number theory.

There are clearly at most $d(n,Q)$ choices for the set $\{r_1,\ldots,r_k\}$.

Finally, to estimate the number of choices for (c), note that $$\sum n_i\log r_i < \log Q,$$ and $\log r_i\gg \log \log Q$ by construction, hence it suffices to bound the number of positive integers $n_1,\ldots,n_s\geq 1$ (where $s$ may vary) such that $\sum n_i \ll \log Q/\log\log Q$. This is at most $\exp(O(\log Q/\log\log Q))$, using the elementary fact (simple combinatorics, 'stars and bars') that the the number of sequences of positive integers $n_i$ with $\sum n_i \leq M$ is exactly $2^M$.

Thus combining these three estimates, the number of possible $q$ is at most

$$ (\exp(O(\log Q/\log\log Q)))^2\times d(n,Q) \ll \exp(O(\log Q/\log\log Q))d(n,Q).$$

Answer 2

Here is a proof that its at most $\exp(O(\log Q\log\log\log Q/\log \log Q))d(n,Q)$, which suffices for the paper.

Let $S(n,Q) = \{q<Q: q|n\}$. Clearly $|S(n,Q)| = d(n,Q)$.

Now consider $q<Q$ with prime factors in $A$. We define $q'=f(q)$ to be the maximal $q' \in S(n,Q)$ such that $q'|q$ (clearly $q'$ is well-defined as $q<Q$).

We now claim that $|f^{-1}(q')| \le \exp(O(\log Q/\log\log Q))$ for each $q'\in S(n,Q)$. Let $A'$ be the primes dividing $q'$. Since $$Q> q' \ge \prod_{p \in A'}p,$$ we have $|A'| := k' \le (1+o(1))\log Q/\log\log Q$ by PNT.

We next observe that $|f^{-1}(q')|$ is upper bounded by the number of $q<Q$ with prime factors in $A'$. Letting $P_1,\dots,P_{k'}$ be the $k'$ smallest primes, the number of such $q$ is bounded by the number of $i_1,\dots,i_{k'}\ge 1$ such that$$\sum_j i_j \log P_j < \log Q.$$

But this at most the volume of a $k'$-dimensional unit simplex with the $j$-th axis scaled by $2\log Q/\log P_j$. The volume of the unit simplex is $1/k'!$ and the determinant of our scaling is $$D =\exp(k'(\log(2)+\log \log Q) - \sum_j \log\log P_j)\le \exp(k' +k'\log\log Q) .$$ If $k'<\log Q/(\log\log Q)^2$ we are done since $1/k'!<1$. Otherwise, we have $1/k'!\le \exp(-k'(\log k'-2))$ for all large $k'$ (Stirling's approximation), so here $D/k'! \le \exp(3k' + k'(\log\log Q-\log k')) $. Since $\log\log Q -\log k'\le 2\log\log \log Q$ (for our range of $k'$ we are done.