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

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

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

$$\prod_{p

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

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

• If I'm not mistaken, one can deduce from Mertens' theorem that $c=e^{-\gamma}$, right? – Sylvain JULIEN Jul 6 '20 at 11:13
• @SylvainJULIEN Yes, the way I derived the asymptotics was with Merten's theorems. I decided to use $c$ instead of $e^{-\gamma}$ since the exact value of the constant doesn't really matter to me. – Milo Moses Jul 6 '20 at 14:06

## 1 Answer

As pointed out in the question, we have that

$$\prod_{p

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

Treating the LHS with simple manipulation we get that

\begin{align*} \prod_{p

We now note that

$$\sum_{p

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

By Merten's theorem, we have that

\begin{align*} \sum_{p

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

For simplicity's sake, we now define

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

and thus

$$\begin{equation} \prod_{p

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

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

We also see that

\begin{align*} \left.\frac{d^k}{dx^k}\prod_{p

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