Denote $\omega(m)$ to be number of distinct factors of $m$ as defined in http://mathworld.wolfram.com/DistinctPrimeFactors.html.

At every $c>0$, given $n\in\Bbb N$ define $$S(n,c)=\big\{m\in\Bbb N:\mbox{ }m<n,\mbox{ }\omega(m)<(\log\log m)^c\big\}.$$

What is known about cardinality $|S(n,c)|$?

What probabilistic model has a good fit for $\omega(m)$?

I am looking for finer information such as:

How does $\frac{\large\partial\big(\big|S(n,c)\big|\big)}{\large\partial c}$ behave?

For a given $a>1$, is there a $c$ as a function of $m$ where $1-\frac 1a$ fraction of numbers less than $m$ lie in?

  • 2
    $\begingroup$ As you may already know, the Erdős–Kac theorem gives some clue, but I don't know of more precise results in the ranges you're interested in. $\endgroup$ – Emanuele Tron Aug 31 '15 at 19:42
  • 2
    $\begingroup$ For your new edit, I think my answer is sufficient for what you need. $\endgroup$ – i707107 Sep 1 '15 at 0:08

Let me supplement the answer of i707107 for $c<1$, i.e. when we count integers with very few prime factors. Writing $$ \pi_k(n):=|\{m\in\Bbb N:\mbox{ }m\leq n,\mbox{ }\omega(m)=k\}|,$$ the cardinality $|S(n,c)|$ can be well approximated with the sum of $\pi_k(n)$ for $k<(\log\log n)^c$. Now, we have very precise information for $\pi_k(n)$ in this range, in fact even in the wider range $1\leq k\leq A\log\log n$ with $A>0$ fixed. Namely, Selberg (1954) proved that $$\pi_k(n)=\frac{n}{\log n}\frac{(\log\log n)^{k-1}}{(k-1)!} \left\{\lambda\left(\frac{k-1}{\log\log n}\right)+O_A\left(\frac{k}{(\log\log n)^2}\right)\right\}, $$ where $$ \lambda(z):=\frac{1}{\Gamma(z+1)}\prod_p\left(1+\frac{z}{p-1}\right)\left(1-\frac{1}{p}\right)^z.$$ You can read the proof in Chapter II.6 of Tenenbaum: Introduction to analytic and probabilistic number theory. The notes to this chapter contain further information, e.g. an extension of the above result valid for $k\ll(\log\log n)^2$. This extension, with a slightly different looking asymptotic, is due to Hildebrand-Tenenbaum (1988), and it corresponds to $c\leq 2$ in your notation.


Let $T(n,c)=\{m\in \mathbb{N} \ : \ m<n, \ \omega(m)<(\log\log n)^c\}$. Then we have

$S(n,c)\subset T(n,c)$ and $|S(n,c)|\leq |T(n,c)|$. Also, if

$T'(n,c)=\{ m\in \mathbb{N} \ : \ m<n, \ \omega(m)<(\log\log (\sqrt n))^c\}$, we have

$ |T'(n,c)|+O(\sqrt n) \leq |S(n,c)| \leq |T(n,c)|$.

Thus, we see that if $\lim_{n\rightarrow\infty} |T'(n,c)|/n$ and $\lim_{n\rightarrow \infty} |T(n,c)|/n$ exists and equal,

then the limit $\lim_{n\rightarrow\infty} |S(n,c)|/n$ must exist and equal to

that of $\lim_{n\rightarrow \infty} |T(n,c)|/n=\lim_{n\rightarrow \infty} |T(n,c)|/n$.

As commented above, we use Erdos-Kac Theorem, then we see that $$\lim_{n\rightarrow\infty} |T'(n,c)|/n=\lim_{n\rightarrow \infty} |T(n,c)|/n,$$

and the value of the limit depends on $c$.

For $0<c<1$, the value is $0$,

For $c=1$, the value is $1/2$,

For $1<c$, the value is $1$.

Therefore, we obtain that

If $0<c<1$, $$\lim_{n\rightarrow\infty} |S(n,c)|/n = 0,$$

If $c=1$, $$\lim_{n\rightarrow\infty} |S(n,c)|/n = \frac12,$$

If $c>1$, $$\lim_{n\rightarrow\infty} |S(n,c)|/n = 1,$$

To obtain a finer result, we use Renyi-Turan (1957) in the form $$ \sup_{x\in\mathbb{R}} \left|\frac1n |\{ m < n : \frac{\omega(m)-\log\log n}{\sqrt{\log\log n}}\leq x\} | - \Phi(x) \right| =O\left( (\log\log n)^{-\frac12}\right). $$

Then we have $$ \left||T(n,c)|/n - \Phi\left( \frac{(\log\log n)^c - \log\log n}{\sqrt{\log\log n}}\right)\right|=O\left( (\log\log n)^{-\frac12}\right).$$

Then we have the following asymptotic formula $$|T(n,c)|/n = \Phi\left( \frac{(\log\log n)^c - \log\log n}{\sqrt{\log\log n}}\right) + O\left( (\log\log n)^{-\frac12}\right).$$

To treat the $\Phi$ term, we use Chernoff bound :

If $X$ is standard normal distribution, then $$ P(X\geq a) \leq \exp\{\frac{-a^2}2\}.$$

Now, let $\chi(c)$ be $0$, $1/2$, $1$ when $0<c<1$, $c=1$, and $c>1$ respectively.

Then we see that $$ |T(n,c)|/n = \chi(c) + O(\exp\{ \frac{-f_c(n)^2}{2} \}) + O\left( (\log\log n)^{-\frac12}\right) $$ where $$f_c(n) = \left|\frac{(\log\log n)^c - \log\log n}{\sqrt{\log\log n}}\right|.$$

The first error term does not appear when $c=1$. For fixed $c\neq 1$, the first error term is consumed in the second error term.

We can treat $T'(n,c)$ the similarly.

  • $\begingroup$ Thank you but I am looking for a finer estimate for any $c\in\Bbb R$? $\endgroup$ – user76479 Aug 31 '15 at 20:35
  • 2
    $\begingroup$ That will also be possible if we use finer version of Erdos-Kac, e. g. Renyi-Turan. This is a Berry-Esseen estimate version of Erdos-Kac. $\endgroup$ – i707107 Aug 31 '15 at 20:38
  • $\begingroup$ Could you please post this as well? $\endgroup$ – user76479 Aug 31 '15 at 20:38

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.