# How does one find the inequality $\tau(n) < (\frac{2}{\log 2}\log n)^{2^x}n^{\frac{1}{x}}$?

Context (Though I don't see how this might help deriving the final inequality):

Example : For $p$ prime, $x$ greater than $0$ a real number, $n$ greater or equal to $2$ an integer: for $p< 2^{x}$ it holds that $$1+\text{ord}_{p}(n)\le 1+ \frac{\log n}{\log p} \le 1+ \frac{\log n}{\log 2} \le \frac{2}{\log 2}\log n$$ and for $p \ge 2^{x}$ it holds that: $$1+\text{ord}_{p}(n)\le 2^{\text{ord}_{p}(n)}\le p^{\text{ord}_{p}(n)/x}.$$

(no proof supplied from the original author, so I will try to do one myself.)

For $p<2^{x}$:

$$1+\text{ord}_{p}(n)\le 1+ \frac{\log n}{\log p} \tag{1}$$

$$1+ \frac{\log n}{\log p} \le 1+ \frac{\log n}{\log 2} \tag{2}$$

$$1+ \frac{\log n}{\log 2} \le \frac{2}{\log 2}\log n \tag{3}$$

(2) holds because $2$ is the smallest prime. (3) because the derivative of $\log(2x)$ is $\frac{1}{x}$ and $\frac{2}{x}$ (the derivative of $2\log(x)$) is greater for every $x$. I have trouble showing (1) because I don't understand how to handle the $\text{ord}_{p}(n)$ (which also appears in the second inequality). ($\text{ord}_{p}(n)$ is the highest natural exponent $k$ such that $p^{k}$ divides $n$).

For $p>2^{x}$: $$1+\text{ord}_{p}(n)\le 2^{\text{ord}_{p}(n)} \tag{1}$$

$$2^{\text{ord}_{p}(n)}\le p^{\text{ord}_{p}(n)/x} \tag{2}$$

Right after this example, the author mentions an inequality and this is what I am really interested in:

For $n\ge 2$ an integer, $x\in \mathbb{R_{>0}}$ , how does one find out that $$\tau (n) < \left(\frac{2}{\log 2}\log n \right)^{2^x}n^{\frac{1}{x}}\ ?$$ It looks like a popular inequality, does it have a name?

-
Is there any other condition on $x$? As $x\to –\infty$ the inequality becomes $\tau(n) \leq 1$ which is not true for all $n.$ –  Ragib Zaman Mar 7 '12 at 0:15
@Ragib: The RHS certainly does not become $1$. –  anon Mar 7 '12 at 0:19
@anon It certainly looks to me like it does, since as $x\to (-\infty)$ the exponent $2^x\to 0$ and $n^{1/x}\to 1$, with appropriate rates of convergence. –  Alex Becker Mar 7 '12 at 0:29
Oh wow, there's a negative sign there. –  anon Mar 7 '12 at 0:43
I think @Matthew is using $\omega(n)$ for the number of prime divisors of $n$. –  Gerry Myerson Mar 8 '12 at 5:42

I think this might work. Given a real $x > 0$ partition the prime divisors of $n$ into two classes, those which are bounded from above by $2^{x}$ and those bounded from below by $2^x$. We have \begin{align} \tau(n) = \prod_{2^{x} \geqslant p \mid n}( \text{ord}_{p}(n) + 1) \prod_{2^{x} < p \mid n}( \text{ord}_{p}(n) + 1). \end{align} Writing $n = \prod_{p \mid n} p^{\text{ord}_{p}(n)}$, \begin{align} \log n = \sum_{p \mid n} \text{ord}_p(n) \log p \quad \Longrightarrow \quad \frac{\log n}{\log p} = \text{ord}_{p}(n) + \sum_{p \neq p^{\prime} \mid n} \text{ord}_{p^{\prime}}(n) \ \log_{p} \, p^{\prime}, \end{align} so the inequality $\text{ord}_{p}(n) \leqslant \frac{\log n}{\log p}$ holds for any prime divisor of $n$. The bounds which you claim are sufficient to prove the upper bound on the number-of-divisors function. Observe that for $p \leqslant 2^{x}$ (actually, for any prime divisor of $n$), then \begin{align} \text{ord}_{p}(n) + 1 \leqslant \frac{\log n}{\log p} + 1 \leqslant \frac{ \log n}{\log 2} + 1 \leqslant \frac{2 \log n}{\log 2}, \end{align} provided that $n \geqslant 2$ and, if $p > 2^{x}$, one has $\text{ord}_{p}(n) + 1 \leqslant 2^{\text{ord}_p(n)} \leqslant p^{\text{ord}_{p}(n)/x}$. Thus, \begin{align} \tau(n) & \leqslant \prod_{2^{x} \geqslant p \mid n} \frac{2 \log n}{\log 2} \, \prod_{2^{x} < p \mid n} p^{\text{ord}_{p}(n)/x} \\ & = \prod_{2^{x} \geqslant p \mid n} \frac{2 \log n}{\log 2} \, \left( \prod_{2^{x} < p \mid n} p^{\text{ord}_{p}(n)} \right)^{1/x}. \end{align} The first product has at most $2^{x}$ terms, while the second product has at most $\omega(n)$ terms. Hence, \begin{align} \tau(n) & \leqslant \left( \frac{2 \log n}{\log 2} \right)^{2^{x}} \left( \prod_{p \mid n} p^{\text{ord}_{p}(n)} \right)^{1/x} \\ & \leqslant \left( \frac{2 \log n}{\log 2} \right)^{2^{x}} n^{1/x}. \end{align}
It should now be clear how one might sharpen the bound: \begin{align} \tau(n) \leqslant \left( \frac{2 \log n}{\log 2} \right)^{\omega(n)} n^{1/x}, \end{align} where $\omega$ is the number-of-prime-divisors function.
In any event, taking the original inequality, we see \begin{align} \frac{\log \tau(n)}{\log n} \leqslant \frac{2^x \log(\frac{2\log n}{\log 2})+\frac{1}{x} \log n}{\log n} =\frac{2^x \log ( \frac{2 \log n}{\log 2})}{\log n}+\frac{1}{x}. \end{align} For any $x > 0$ there is an integer $n_0 = n_{0}(x)$ such that for any $n > n_0$, $\frac{\log \tau(n)}{\log n}$ is bounded from above by $\frac{2}{x}$, and so the limit must vanish.
Nice work. One typo in your second displayed equation: the terms in the sum should be $\text{ord}_{p^{\prime}}(n) \log p^{\prime}/\log p$ –  Antonio Vargas Jun 7 '12 at 2:41