Number of distinct factors

Question

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?

Answer 1

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.

Answer 2

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.