2
$\begingroup$

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!

$\endgroup$
2
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.