Show that $2^{\nu(n)} \leq d(n) \leq 2^{\omega(n)}$

Question

I trying to prove $2^{\nu(n)} \leq d(n) \leq 2^{\omega(n)}$, where $n \geq 1$, $\nu(n) =$ number of distinct prime factors of $n$, $d(n)=$ total number of divisors of $n$ and $\omega(n)=$ number of prime factors counted with multiplicity.

$\textbf{My attempt:}$ Let $P$ be the set of all distinct prime factors of $n$. Then each divisor $m$ of $n$ can be identified with the subset of $P$ containing the primes in $m$. So, for each subset of $P$, there exists at least one divisor of $n$. So, the number of subsets of $P\leq d(n)$. That is, $2^{\nu(n)} \leq d(n)$. On the other hand, let $Q$ be the set of all prime factors of $n$ counted with proper multiplicities. (in fact, the repeated primes can be labelled differently to form the set $Q$). Then each divisor of $n$ corresponds to a subset of $Q$. Thus $d(n) \leq 2^{\omega(n)}$.

However, I think this proof is more of intuitive in nature and not so rigorous. Also, may be I am unable to put it in proper form. Is there a simpler or more rigorous way of proving this?

Answer 1

Hint: Consider the prime factorization of $n$, $n = {p_1}^{k_1}$${p_2}^{k_2}$...${p_j}^{k_j}$, where $p_1$, $p_2$,...$p_j$ are the distinct prime factors of $n$ & $k_i$ $\geq 1$ for all $i=1,2,...,j$

Can you figure out $ω(n)$, $d(n)$ & $ν(n)$ ? (hint: use the fact that these are multiplicative functions).

Answer 2

I'm sorry in advance that I don't know how to make certain things look neat such as subscripts and exponents. Can somebody please comment and let me know and how to. Thank you.

Let $n=({p_1}^{k_1})({p_2}^{k_2})\dots ({p_x}^{k_x})$ where $p_1,p_2,p_3\dots$ are primes. Clearly, $k_1,k_2 \dots$ are greater than or equal to $1$.

$d(n)=(k_1+1)(k_2+2)...(k_x+1)$

$v(n)=x$

$w(n)=k_1+k_2+k_3...k_x$

Also, it is helpful to realize that if the inequality is expanded then each part has the same number of terms.

Now we can look at the first part of the inequality.

$\underbrace{2 \cdot 2 \cdots 2 }_\text {x times} \leq (k_1+1)(k_2+2)...(k_x+1)$

Since each $k_a$ is equal to or greater than $1$ every term on the second part of the inequality is greater than or equal to two, and since there are $x$ terms on both sides the second part of the inequality must be equal to or greater than the first part.

Before we look at the second inequality it is worth realizing that $2^k \geq k+1$ for all $k$.

Now lets look at the second part of the inequality.

$(k_1+1)(k_2+2)\dots (k_x+1) \leq (2^k_1)(2^k_2)\dots(2^k_x)$

If you compare both sides term by term and use the fact that $2^k>=k+1$ for all k then it is evident that each term on the right side is greater than the left side.

The original inequality is now proven.