Prove that $\omega(n) \ll \frac{ \log n} {\log \log n}$

Question

Let $\omega(n)$ the number of distinct prime divisors of an integer n, so for instance $\omega(12) = 2$. Show that $\omega(n) \ll \frac{ \log n} {\log \log n}$.

This question is from assignment 2 of this course:http://www.math.tau.ac.il/~rudnick/courses/sieves2015.html

I am self studying this course. This will involve things studied in 4th lecture.

Well results available are that for almost all n,$\omega(n)= \log \log n(1+o(1))$ and 1 result that there always exists a density 1 subsequence {$n_j$} of positive integers such that $\omega(n_j) =\log \log(n_j) (1+o(1) ) $ as j tends to $\infty$ and theorem of Turan that $\sum_{n\leq x} (\omega(n) - \log \log x)^2 =O( x\log \log x)$

I tried using the subsequence result but I am not even close to what has been asked.

So, please tell how should I prove this.

Answer 1

Another trick is by partitioning $\omega(n)$ into two parts:

$$ \omega(n)=\sum_{\substack{p|n\\p\le t}}1+\omega(n,t) $$

where $\omega(n,t)$ here denotes the number of prime divisors of $n$ that are greater than $t$. By the property of factorization, we know trivially that $t^{\omega(n,t)}<n$, so we have

$$ \omega(n)<\pi(t)+{\log n\over\log t} $$

Now, apply Chebyshev's estimate we obtain

$$ \omega(n)\ll{t\over\log t}+{\log n\over\log t} $$

Finally, setting $t=\log n$ gives the desired result.

Answer 2

Write $\omega(n)=k$, and write $$n=q_1^{e_1}\cdots q_k^{e_k}$$ with $e_1,\dots,e_k\geq 1$ and $q_1<q_2<\cdots<q_k$ prime. Then $$n\geq (1)(2)\cdots(k)=k!.$$ We find $$\frac{\log k!}{\log\log k!}\geq \frac{\log\left((k/2)^{k/2}\right)}{\log\log k^k}\geq \frac{\frac k2\log(k/2)}{\log k+\log\log k}\geq \frac{k}{8}.$$ This means that, for large enough $n$, $$\omega(n)=k\leq \frac{8\log k!}{\log \log k!}\leq \frac{8\log n}{\log\log n}.$$

Answer 3

Let $d(n)$ denote the number of positive divisors of $n$. Then we know that $\omega(n)\le\log d(n)/\log2$, with equality iff $n$ is squarefree. Now, it suffices to show that

$$ \log d(n)\ll{\log n\over\log\log n} $$

In this answer, we are going to prove an even stronger result that

Proposition: The maximal order of $\log d(n)$ is $\log2\log n/\log\log n$. That is $$ \limsup_{n\to\infty}{\log d(n)\log\log n\over\log2\log n}=1\tag1 $$

Proof. By the multiplicative property of $d(n)$, we know that

$$ d(n)=\prod_{p^k\|n}(k+1)=\prod_{p^k\|n,p\le t}(k+1)\prod_{p^k\|n,p>t}(k+1)\tag2 $$

where the parameter $t>0$ will be chosen later. Because $p^k\|n$ indicates that $k\le\log n/\log2$ with equality iff $p=2$, we can bound the first product by

$$ \prod_{p^k\|n,p\le t}(k+1)\le\left(1+{\log n\over\log2}\right)^t\tag3 $$

For the second product, we can apply $k+1\le2^k$ to get

$$ \prod_{p^k\|n,p>t}(k+1)\le\prod_{p^k\|n,p>t}2^k\tag4 $$

To continue, we apply Rankin's trick on $p>t$. Since $\log p/\log t>1$ iff $p>1$, we plug this into (4) to get

$$ \prod_{p^k\|n,p>t}(k+1)\le\prod_{p^k\|n}2^{k\log p/\log t}=\left(\prod_{p\|n}p^k\right)^{\log2/\log t}=\exp\left(\log2\log n\over\log t\right)\tag5 $$

Now, plugging (3) and (5) into (2), we have

\begin{aligned} \log d(n) &\le t\log\left(1+{\log n\over\log2}\right)+{\log2\log n\over\log t} \\ &\le{\log2\log n\over\log t}+\mathcal O(t\log\log n) \end{aligned}

For convenience, we wish to set $t=u\log n$ so that

$$ \log d(n)\le{\log2\log n\over\log\log n+\log u}+\mathcal O(u\log n\log\log n)\tag6 $$

To ensure that the O term does not assimilate the main term, we set $u=(\log\log n)^{-3}$ so that

$$ \log d(n)\le{\log2\log n\over\log\log n}\left[1+\mathcal O\left(\log\log\log n\over\log\log n\right)\right]\tag7 $$

This indicates that the limit in (1) is $\le1$. To establish equality, it suffices to find a sequence $n_k$ such that $\log d(n_k)\sim{\log2\log n_k/\log\log n_k}$ as $k\to+\infty$. Indeed, if we let $n_k$ be the product of first $k$ primes then $d(n)=2^k$. Then we have

$$ \log n_k=\sum_{p\le p_k}\log p=\vartheta(p_k)\tag8 $$

Since Chebyshev's theorem asserts $c_1x\le\vartheta(x)\le c_2x$ for some absolute $c_2>c_1>0$, we take logarithm on (8) to obtain

$$ \log\log n_k=\log p_k+\mathcal O(1)\tag9 $$

Moreover, because $\vartheta(x)\le\pi(x)\log x$, we have $\log n_k\le k\log p_k$. This, together with (9), implies

$$ \begin{aligned} k &={k\log p_k\over\log p_k}\ge{\log n_k\over\log p_k} \\ &={\log n_k\over\log\log n_k+\mathcal O(1)} \\ &={\log n_k\over\log\log n_k}\left[1+\mathcal O\left(1\over\log\log n\right)\right] \end{aligned}\tag{10} $$

Combining (10) and (7), we deduce (1).