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
    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.$2012-03-07
  • 1
    @Ragib: The RHS certainly does not become $1$.2012-03-07
  • 1
    @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.2012-03-07
  • 0
    Oh wow, there's a negative sign there.2012-03-07
  • 0
    @RagibZaman I deleted that information accidentally before I posted and forgot to put it back.2012-03-07
  • 0
    I don't know. How did *you* find out that $\tau(n)\lt{\rm\ etc., etc.}$?2012-03-07
  • 0
    It "appears" in a script for number theory after a number of examples and I assumed it was something popular so I didnt add any context. I will add some more context....2012-03-07
  • 0
    I would love to know where you found this. We certainly have $\tau(n) = \prod (ord_p n +1) \le \prod ( \frac{2}{\log 2} \log n ) = ( \frac{2}{\log 2} \log n )^{\omega(n)} \le ( \frac{2}{\log 2} \log n ) ^ {(\log n)/(\log 2)}$. I'd like to see what the author used that inequality for.2012-03-07
  • 0
    After that it is followed by this exercise:http://math.stackexchange.com/questions/117317/how-to-show-that-lim-n-to-infty-frac-log-tau-n-log-n-0 ; I can tell you the author's name if you want (privately by mail). How did you form your chain of inequalities? What does $\omega (n)$ mean ?2012-03-07
  • 2
    I think @Matthew is using $\omega(n)$ for the number of prime divisors of $n$.2012-03-08
  • 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
    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$2012-06-07
  • 0
    Fixed. Thanks, Antonio!2012-06-07