[Math] Asymptotics for the divisor function

analytic-number-theoryasymptoticsnumber theory

I am attempting to understand Tao's post of 23 September 2008 given here concerning the divisor bound.

My troubles are when he uses the big-O notation in proving what he lists as bound (4)
$$
d(n) \leq \exp(O(\frac{\log n}{\log\log n})).
$$

First, after showing that
$$ d(n) \leq O(\frac{1}{\epsilon})^{\exp (1/\epsilon)} $$
he declares that
$$ O(\frac{1}{\epsilon})^{\exp(1/\epsilon)}=\exp(\exp(O(1/\epsilon))). $$
I do not know how to see this.
A tiny bit later he uses the above to write
$$
d(n)\leq\exp(\exp(O(1/\epsilon)))n^\epsilon.
$$
We plug in $C/\log\log n$ and he declares that the second term in the right hand side dominates which can be seen by taking logarithms. I am also not seeing this. Any insights would be greatly appreciated. Thank you!

Best Answer

Let's look at them in turn.

  1. We want to show that $$ O\left(\frac{1}{\epsilon}\right)^{\exp(1/\epsilon)}=\exp(\exp(O(1/\epsilon))). $$

    For ease of notation, I drop most $O(\cdot)$ constants. Then note that $$ \left( \frac{1}{e} \right) ^{ \exp(1/\epsilon) } = e^{\log(1/\epsilon)\cdot \exp(1/\epsilon)}$$

    and in general, $\log x \cdot e^x = O(e^{x +\delta})$ for any $\delta > 0$. Thus $$ \left( \frac{1}{e} \right) ^{ \exp(1/\epsilon) } = e^{\log(1/\epsilon)\cdot \exp(1/\epsilon)} = \exp (\, \exp ( \, O (1/\epsilon )\, )\, )$$

  2. Let's follow his suggestion. So set $\epsilon = C/\log\log n$ for some large $C$. Then we want to compare the growth of $\exp ( \exp ( O(1/\epsilon)))$ and $n^\epsilon$. I again drop most $O(\cdot)$ constants for ease. The first one:

    $$ \exp( \exp ( 1/\epsilon)) = \exp ( \exp ( \log \log n / C) ) = \exp \exp (\log (\log n)^{1/C} ) = \exp ( (\log n)^{1/C}).$$

    The second one stays:

    $$ n^{C/\log \log n}$$

    Now take logs. Then we compare

    $$ (\log n)^{1/C} \quad \text{and} \quad \frac{C}{\log \log n} \log n$$

    Similar to the fact above, $\frac{x}{\log x} > x^{1 - \delta}$ for any $\delta > 0$. So for large $C$, the left side is like a small power (much less than $1$, say) of $\log n$ and the right side is like a larger power (pretty close to $1$) of $\log n$.

So that's one way of getting his two results. $\diamondsuit$

Related Question