Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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.

share|cite|improve this answer
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
Fixed. Thanks, Antonio! – user02138 Jun 7 '12 at 2:47

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.