# Asymptotics for the divisor function

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!

## 1 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$