1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ If I'm not mistaken, one can deduce from Mertens' theorem that $c=e^{-\gamma}$, right? $\endgroup$ – Sylvain JULIEN Jul 6 '20 at 11:13
  • $\begingroup$ @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. $\endgroup$ – Milo Moses Jul 6 '20 at 14:06
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.