Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

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!

share|cite|improve this question
up vote 2 down vote accepted

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$

share|cite|improve this answer

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.