$2^{\omega (n)}\le \tau (n)\le 2^{\mathrm{\Omega }(n)}$

Throughout this entry, $\omega$, $\tau$, and $\mathrm{\Omega }$ denote the number of distinct prime factors function, the divisor function, and the number of (nondistinct) prime factors function (http://planetmath.org/NumberOfNondistinctPrimeFactorsFunction), respectively.

Theorem.

For any positive integer $n$, ${\mathrm{2}}^{\omega \mathit{}\mathrm{(}n\mathrm{)}}\mathrm{\le }\tau \mathit{}\mathrm{(}n\mathrm{)}\mathrm{\le }{\mathrm{2}}^{\mathrm{\Omega }\mathit{}\mathrm{(}n\mathrm{)}}$.

Proof.

Note that $2^{\omega (n)}$, $\tau (n)$, and $2^{\mathrm{\Omega }(n)}$ are multiplicative. Also note that, for any positive integer $n$, the numbers $2^{\omega (n)}$, $\tau (n)$, and $2^{\mathrm{\Omega }(n)}$ are positive integers. Therefore, it will suffice to prove the inequality for prime powers.

Let $p$ be a prime and $k$ be a positive integer. Thus:

Hence, $2^{\omega (p^k)}\le \tau (p^k)\le 2^{\mathrm{\Omega }(p^k)}$. It follows that $2^{\omega (n)}\le \tau (n)\le 2^{\mathrm{\Omega }(n)}$. ∎

This theorem has an obvious corollary.

Corollary.

For any squarefree positive integer $n$, ${\mathrm{2}}^{\omega \mathit{}\mathrm{(}n\mathrm{)}}\mathrm{=}\tau \mathit{}\mathrm{(}n\mathrm{)}\mathrm{=}{\mathrm{2}}^{\mathrm{\Omega }\mathit{}\mathrm{(}n\mathrm{)}}$.

Title	$2^{\omega (n)}\le \tau (n)\le 2^{\mathrm{\Omega }(n)}$
Canonical name	2omeganletaunle2Omegan
Date of creation	2013-03-22 16:07:28
Last modified on	2013-03-22 16:07:28
Owner	Wkbj79 (1863)
Last modified by	Wkbj79 (1863)
Numerical id	14
Author	Wkbj79 (1863)
Entry type	Theorem
Classification	msc 11A25
Related topic	NumberOfDistinctPrimeFactorsFunction
Related topic	TauFunction
Related topic	NumberOfNondistinctPrimeFactorsFunction
Related topic	DisplaystyleYOmeganOleftFracxlogXy12YRightFor1LeY2