Number of integers at most $x$ with exactly two distinct prime factors

488 Views Asked by At

I wish to find an asymptotic for the number of integers not exceeding $x$ with exactly two distinct prime factors. Here is a starting point:

Throughout $p$ and $q$ are primes. We are interested in $\frac{1}{2}\#\{(p,q,\alpha,\beta): p^{\alpha}q^{\beta} < x\}$. (The factor $\frac{1}{2}$ arises since e.g. for $x=10^4$ we get $2^{3}\cdot 5^4$ once from $p=2$, $q=5$, $\alpha = 3$, $\beta = 4$ and once from $p=5$, $q=2$, $\alpha = 4$, $\beta = 3$.) Another way to write it is $\frac{1}{2}\#\{(p,q,\alpha,\beta): q<x, p<(x/q^{\beta})^{1/\alpha} \} = \frac{1}{2}\sum_{q<x}\sum_{\alpha, \beta \geq 1}\sum_{p<(x/q^{\beta})^{1/\alpha}}1$. Taking care of the inner sum with the Prime Number Theorem, the count becomes $$\frac{1}{2}\sum_{q<x}\sum_{\substack{\alpha, \beta \geq 1}} \bigg(\frac{x^{1/\alpha}}{q^{\beta/\alpha}\log \frac{x^{1/\alpha}}{q^{\beta/\alpha}}} + O\bigg(\frac{x^{1/\alpha}}{q^{\beta/\alpha}\log^2 \frac{x^{1/\alpha}}{q^{\beta/\alpha}}}\bigg)\bigg)$$

Any idea how to conviently proceed with the latter nasty sums (or perhaps another approach)? Any help appreciated!

1

There are 1 best solutions below

0
On BEST ANSWER

The asymptotic is $$\frac{x\log \log x}{\log x}\,.$$ More generally, a result of Landau (1900) is that $$\pi_k(x) \sim \rho_k(x) \sim \sigma_k(x) \sim \frac{x(\log \log x)^{k-1}}{(k-1)!\log x}\,,$$ where \begin{align} \pi_k(x) &= \# \{ n \leqslant x : \omega(n) = \Omega(n) = k\}\,,\\ \rho_k(x) &= \#\{ n \leqslant x : \omega(n) = k\}\,,\\ \sigma_k(x) &= \#\{ n \leqslant x : \Omega(n) = k\}\,, \end{align} and $\omega(n)$ is the number of distinct prime factors of $n$, while $\Omega(n)$ is the number of prime factors of $n$ counted with multiplicity,.

You are specifically asking for the asymptotics of $\rho_2$.

If we only want to show that, not Landau's result in full generality, the IMO easiest way is to obtain the asymptotics for $\pi_2(x)$, and then show that the numbers $p^{\alpha} q^{\beta}$ with $\alpha > 1$ or $\beta > 1$ are asymptotically negligible.

By symmetry, we can assume $\alpha > 1$, and we can ignore the condition $q \neq p$ (that can only make us overestimate the count, so if it still remains negligible, a fortiori the true count is negligible).

Given a prime $p$ and an exponent $\alpha > 1$, the count of numbers $p^{\alpha} q^{\beta} \leqslant x$, where $q$ is a prime (possibly equal to $p$) is the number of prime powers (including primes) not exceeding $x/p^{\alpha}$. Splitting into two parts according as $p^{\alpha} > \sqrt{x}$, for the part with $p^{\alpha} > \sqrt{x}$ we obtain the upper bound $$\sum_{\substack{\sqrt{x} < p^{\alpha} \leqslant x/2 \\ \alpha \geqslant 2}} \sqrt{x} \leqslant \sqrt{x}\cdot \pi(\sqrt{x}) \leqslant C_1\cdot \frac{x}{\log x}$$ and for the part with $p^{\alpha} \leqslant \sqrt{x}$, since there are only $O(\sqrt{y})$ perfect powers not exceeding $y$ we obtain an upper bound of $$C_2\cdot\sum_{\substack{p^{\alpha} \leqslant \sqrt{x} \\ \alpha \geqslant 2}} \pi\biggl(\frac{x}{p^{\alpha}}\biggr) \leqslant C_3\cdot \sum_{\substack{p^{\alpha} \leqslant \sqrt{x} \\ \alpha \geqslant 2}} \frac{x}{p^{\alpha}\log \frac{x}{p^{\alpha}}} \leqslant 2C_3\frac{x}{\log x} \sum_{\substack{p^{\alpha} \leqslant \sqrt{x} \\ \alpha \geqslant 2}} \frac{1}{p^{\alpha}} \leqslant C_4\frac{x}{\log x}\,.$$ Altogether, $$\rho_2(x) - \pi_2(x) \in O\biggl(\frac{x}{\log x}\biggr)\,,$$ which is of smaller order than $\frac{x\log \log x}{\log x}$.

It remains to prove the assertion about $\pi_2$. It is easy to see $$\pi_2(x) = \sum_{p \leqslant \sqrt{x}} \Biggl(\pi\biggl(\frac{x}{p}\biggr) - \pi(p)\Biggr)\,,$$ and $$\sum_{p \leqslant \sqrt{x}} \pi(p) = \frac{\pi(\sqrt{x})\bigl(\pi(\sqrt{x}) + 1\bigr)}{2} \in O\biggl(\frac{x}{(\log x)^2}\biggr)\,,$$ whence we obtain \begin{align} \pi_2(x) &\sim \sum_{p \leqslant \sqrt{x}} \pi\biggl(\frac{x}{p}\biggr) \\ &\sim \int_2^{\sqrt{x}} \frac{\pi(x/u)}{\log u}\,du \\ &\sim \int_2^{\sqrt{x}} \frac{x}{u\log u(\log x - \log u)}\,du \\ &= x\int_{\log 2}^{\log \sqrt{x}} \frac{dv}{v(\log x - v)} \\ &= \frac{x}{\log x}\int_{\log 2}^{\log \sqrt{x}}\frac{1}{v} + \frac{1}{\log x - v}\,dv \\ &= \frac{x}{\log x} \int_{\log 2}^{\log \frac{x}{2}} \frac{dw}{w} \\ &= \frac{x}{\log x}\biggl(\log \log \frac{x}{2} - \log \log 2\biggr)\\ &\sim \frac{x\log \log x}{\log x}\,. \end{align} In that, the second asymptotic equality is admittedly not obvious, it is using a lemma by Landau. We can avoid using that, at the cost of a messier calculation, for example \begin{align} \sum_{p \leqslant \sqrt{x}} \pi\biggl(\frac{x}{p}\biggr) &\sim \sum_{p \leqslant \sqrt{x}} \frac{x}{p(\log x - \log p)} \\ &= \int_{2-\varepsilon}^{\sqrt{x}} \frac{x}{u(\log x - \log u)}\,d\pi(u) \\ &= \pi(\sqrt{x})\frac{\sqrt{x}}{\log \sqrt{x}} - \int_{2}^{\sqrt{x}} \pi(u) \frac{d}{du}\biggl(\frac{x}{u(\log x - \log u)}\biggr)\,du \\ &\sim -\int_{2}^{\sqrt{x}} \operatorname{Li}(u)\frac{d}{du}\biggl(\frac{x}{u(\log x - \log u)}\biggr)\,du \\ &= -\operatorname{Li}(\sqrt{x})\frac{\sqrt{x}}{\log \sqrt{x}} + \int_2^{\sqrt{x}} \frac{x}{u\log u(\log x - \log u)}\,du \end{align} using the asymptotics of $\pi(x)$ and Riemann-Stieltjes integrals. The asymptotic equalities here are fairly straightforward to establish.