Asymptotic for the probability that a number has $k$ prime factors less than $Q$

Question

If we let $\omega_Q(n)$ denote the number of distinct prime factors of $n$ less than a bound $Q$, then what asymptotic formulas exist for $\Pr_{n\in\mathbb{N}}[\omega_Q(n)=k]$ as $Q\to\infty$ if $k$ remains fixed (or perhaps very small with respect to n)?

I am asking this question since my study led me to want to bound the quantity

$$\mathbf{E}_{n\in\mathbb{N}}\left[\frac{2^{\omega_Q(n)}}{\sqrt{\omega_Q(n)}}\right]$$

as $Q\to\infty$. Since

$$\mathbf{E}_{n\in\mathbb{N}}\left[\frac{2^{\omega_Q(n)}}{\sqrt{\omega_Q(n)}}\right]=\sum_{n=1}^{\pi(Q)}\left(\Pr_{n\in\mathbb{N}}[\omega_Q(n)=k]\right)\left(\frac{2^{\omega_Q(n)}}{\sqrt{\omega_Q(n)}}\right)$$

and

$$\sum_{n=1}^{\pi(Q)}\Pr_{n\in\mathbb{N}}[\omega_Q(n)=k]2^{\omega_Q(n)}\sim_{Q\to\infty} c\log(Q)$$

is well understood, good (upper) bounds on $\Pr_{n\in\mathbb{N}}[\omega_Q(n)=k]$ could help me in my effort.

For small values of $k$ computations can be done directly, like

$$\Pr_{n\in\mathbb{N}}[\omega_Q(n)=0]\sim\frac{c}{\log(Q)}$$

and

$$\Pr_{n\in\mathbb{N}}[\omega_Q(n)=1]\sim c\frac{\log(\log(Q))}{\log(Q)}$$

The main approach I have been using is noting that $\Pr_{n\in\mathbb{N}}[\omega_Q(n)=k]$ is exactly the coefficient of $x^k$ in the polynomial

$$\prod_{p<Q}\left(\frac{x}{p}+1-\frac{1}{p}\right)$$

Asymptotics of this full polynomial are easy to come by, for instance as $Q\to\infty$ we have that

$$\prod_{p<Q}\left(\frac{x}{p}+1-\frac{1}{p}\right)\sim c \log^{x-1}(Q)$$

Heuristically this would suggest that

\begin{align*} \Pr_{n\in\mathbb{N}}[\omega_Q(n)=k]&=\frac{1}{k!}\left.\frac{d^k}{dx^k}\prod_{p<Q}\left(\frac{x}{p}+1-\frac{1}{p}\right)\right|_{x=0}\\ &\sim \frac{c}{k!}\left.\frac{d^k}{dx^k}\log^{x-1}(Q)\right|_{x=0}\\ &=\frac{c}{k!}\frac{\log^k(\log(Q))}{\log(Q)} \end{align*}

This argument is however by no means rigorous so I would appreciate true asymptotics.

Answer 1

As pointed out in the question, we have that

$$\prod_{p<Q}\left(\frac{x-1}{p}+1\right)=\sum_{k=0}^{\pi(Q)}\Pr_{n\in\mathbb{N}}[\omega_Q(n)=k]x^k$$

which can be derived by showing that on both the RHS and the LHS the coefficient of $x^k$ is equal to

$$\sum_{\substack{S\subseteq \{p<Q\} \\ |S|=k}} \left(\prod_{p\in S}\frac{1}{p}\right)\left(\prod_{p\not\in S}\left(1-\frac{1}{p}\right) \right)$$

Treating the LHS with simple manipulation we get that

\begin{align*} \prod_{p<Q}\left(\frac{x}{p}+1-\frac{1}{p}\right)&=\exp\left(\log\prod_{p<Q}\left(\frac{x}{p}+1-\frac{1}{p}\right)\right)\\ &=\exp\left(\sum_{p<Q}\log\left(\frac{x-1}{p}+1\right)\right)\\ &=\exp\left(\sum_{p<Q}\frac{x-1}{p}+\sum_{p<Q}\left(\log\left(\frac{x-1}{p}+1\right)-\frac{x-1}{p}\right)\right)\tag{1} \end{align*}

We now note that

$$\sum_{p<Q}\left(\log\left(\frac{x-1}{p}+1\right)-\frac{x-1}{p}\right)=\sum_{p}\left(\log\left(\frac{x-1}{p}+1\right)-\frac{x-1}{p}\right)-\sum_{p\geq Q}\left(\log\left(\frac{x-1}{p}+1\right)-\frac{x-1}{p}\right)$$

and thus we can set

$$f_1(x)=\sum_{p}\left(\log\left(\frac{x-1}{p}+1\right)-\frac{x-1}{p}\right)$$

and

$$g(x)=\sum_{p\geq Q}\left(\log\left(\frac{x-1}{p}+1\right)-\frac{x-1}{p}\right)$$

Morally, we can think of $g(x)$ as the "error" as $Q\to\infty$ which we must show is inconsequential. We thus get that

\begin{equation} \sum_{p<Q}\left(\log\left(\frac{x-1}{p}+1\right)-\frac{x-1}{p}\right)=f_1(x)-g(x)\tag{2} \end{equation}

By Merten's theorem, we have that

\begin{align*} \sum_{p<Q}\frac{x-1}{p}&=(x-1)\left(\log(\log(Q))+M+\epsilon_Q\right)\\ &=(x-1)\log(\log(Q))+Mx+\epsilon_Q x-M-\epsilon_Q\tag{3} \end{align*}

where $\epsilon_Q\to 0$ and $M$ is the Meissel-Mertens constant. Substituting (2) and (3) into (1) we get that

\begin{align*} \prod_{p<Q}\left(\frac{x}{p}+1-\frac{1}{p}\right)&=\exp\left((x-1)\log(\log(Q))+Mx+\epsilon_Q x-M-\epsilon_Q+f_1(x)-g(x)\right)\\ &=e^{-M-\epsilon_Q}\log^{x-1}(Q)e^{Mx}e^{f_1(x)}e^{\epsilon_Qx}e^{-g(x)} \end{align*}

For simplicity's sake, we now define

$$f_2(x)=e^{Mx}e^{f_1(x)}$$

and thus

\begin{equation} \prod_{p<Q}\left(\frac{x}{p}+1-\frac{1}{p}\right)=e^{-M-\epsilon_Q}\log^{x-1}(Q)f_2(x)e^{\epsilon_Qx}e^{-g(x)}\tag{4} \end{equation}

Taking the derivative $k$ times yields

$$\frac{d^k}{dx^k}e^{-M-\epsilon_Q}\log^{x-1}(Q)f_2(x)e^{\epsilon_Qx}e^{-g(x)}$$

As $Q\to\infty$, the only term that will matter in a product rule decomposition of this equation is the one that grows the fastest. It is easy to show that

$$g^{(n)}(x)=O\left(\frac{1}{x}\right)$$

for any order derivative $(n)$, and so the fastest growing term is the one where $\log^{(x-1)}(Q)$ is differentiated the full $k$ times. Since there are finitely many terms the others are inconsequential in terms of growth and so

\begin{align*} \frac{d^k}{dx^k}e^{-M-\epsilon_Q}\log^{x-1}(Q)f_2(x)e^{\epsilon_Qx}e^{-g(x)}&\sim_{Q\to\infty}e^{-M-\epsilon_Q}f_2(x)e^{\epsilon_Qx}e^{-g(x)}\frac{d^k}{dx^k}\log^{x-1}(Q)\\ &=e^{-M-\epsilon_Q}f_2(x)e^{\epsilon_Qx}e^{-g(x)}\log^k(\log(Q))\log^{x-1}(Q) \end{align*}

evaluating at $x=0$ and substituting into (4) yields that

\begin{equation} \left.\frac{d^k}{dx^k}\prod_{p<Q}\left(\frac{x}{p}+1-\frac{1}{p}\right)\right|_{x=0}\sim e^{-M-\epsilon_Q}f_2(0)e^{-g(0)}\frac{\log^k(\log(Q))}{\log(Q)} \end{equation}

As $Q\to\infty$ we have that $g(0)\to0$ and $f_2(0)=e^{M-\gamma}$ and so

\begin{equation} \left.\frac{d^k}{dx^k}\prod_{p<Q}\left(\frac{x}{p}+1-\frac{1}{p}\right)\right|_{x=0}\sim e^{-\gamma}\frac{\log^k(\log(Q))}{\log(Q)}\tag{5} \end{equation}

We also see that

\begin{align*} \left.\frac{d^k}{dx^k}\prod_{p<Q}\left(\frac{x}{p}+1-\frac{1}{p}\right)\right|_{x=0}&=\left.\frac{d^k}{dx^k}\sum_{j=0}^{\pi(Q)} \mathrm{Pr}_{n\in\mathbb{N}}[\omega_Q(n)=j]x^j\right|_{x=0}\\ &=k!\mathrm{Pr}_{n\in\mathbb{N}}[\omega_Q(n)=k] \end{align*}

and thus we conclude from (5) that

$$\mathrm{Pr}_{n\in\mathbb{N}}[\omega_Q(n)=k]\sim e^{-\gamma}\frac{\log^k(\log(Q))}{\log(Q) k!}$$

which is the desired result