PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (200)
Orphanage
Unclass'd
Unproven (490)
Corrections (6)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: High Entry average rating: No information on entry rating
$2^{\omega(n)} \le \tau(n) \le 2^{\Omega(n)}$ (Theorem)

Throughout this entry, $ \omega$, $ \tau$, and $ \Omega$ denote the number of distinct prime factors function, the divisor function, and the number of (nondistinct) prime factors function, respectively.

Theorem   For any positive integer $ n$, $ 2^{\omega(n)} \le \tau(n) \le 2^{\Omega(n)}$.
Proof. Note that $ 2^{\omega(n)}$, $ \tau(n)$, and $ 2^{\Omega(n)}$ are multiplicative. Also note that, for any positive integer $ n$, the numbers $ 2^{\omega(n)}$, $ \tau(n)$, and $ 2^{\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:

\begin{displaymath}\begin{array}{rl} \displaystyle 2^{\omega(p^k)} & =2 \ \ ... ... =k+1 \ \ \displaystyle 2^{\Omega(p^k)} & = 2^k \end{array}\end{displaymath}

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

This theorem has an obvious corollary.

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



"$2^{\omega(n)} \le \tau(n) \le 2^{\Omega(n)}$" is owned by Wkbj79.
(view preamble)

View style:

See Also: number of distinct prime factors function, $\tau$ function, number of (nondistinct) prime factors function, $\displaystyle \sum_{n \le x} y^{\Omega(n)}=O\left( \frac{x(\log x)^{y-1}}{2-y} \right)$ for $1 \le y<2$
Log in to rate this entry.
(view current ratings)

Cross-references: squarefree, obvious, prime, inequality, numbers, multiplicative, integer, positive, divisor function, number of distinct prime factors function

This is version 11 of $2^{\omega(n)} \le \tau(n) \le 2^{\Omega(n)}$, born on 2006-07-29, modified 2008-01-01.
Object id is 8194, canonical name is 2omeganLeTaunLe2Omegan.
Accessed 1058 times total.

Classification:
AMS MSC: 11A25 (Number theory :: Elementary number theory :: Arithmetic functions; related numbers; inversion formulas)
Pending Errata and Addenda
None.
[ View all 1 ]
Discussion
Style: Expand: Order:
forum policy
Avoiding ambiguity by hv on 2007-12-31 12:17:02
The proof starts: "Note that the three functions involved in the inequality are multiplicative." I would suggest replacing "functions" with "expressions" - on first reading, my automatic assumption was that the "functions" were \omega(n), \tau(n) and \Omega(n).

Hugo van der Sanden
[ reply | up ]
Unproven? by Mravinci on 2006-10-09 18:00:41
Why is this theorem classified as unproven? The proof provided convinces me well enough, I don't know about the rest of you.
[ reply | up ]
Interact
post | correct | update request | prove | add result | add corollary | add example | add (any)