4
$\begingroup$

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?

  • 0
    Yes, $\omega(n)$ is the number of prime divisors of $n$. Since primes are $\ge 2$, $\omega(n) \le (\log n)/(\log 2)$.2012-03-08

1 Answers 1

1

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.

  • 0
    Fixed. Thanks, Antonio!2012-06-07