I've come across this problem in Murty & Carmen, exercise 1.5.3: show that there is a constant $c$ such that
$d(n)=O(\exp(\frac{c\log n}{\log\log n})))$ where $d(n)$ is the number of divisors of $n$
I've gotten most of the way through and have also looked through this article https://terrytao.wordpress.com/2008/09/23/the-divisor-bound/, but I don't understand this one step in their explanation:
$(6)\le O(1/\varepsilon)^{\exp(1/\varepsilon)} = \exp\exp(O(1/\varepsilon))$
Could anyone provide some justification as to why this would be true? I've tried playing around with the equality, but I've been having no luck. Thanks in advance!
Best Answer
By unique factorization theorem, we can write $n$ into
$$ n=p_1^{r_1}p_2^{r_2}\cdots p_k^{r_k}q_1^{s_1}q_2^{s_2}\cdots q_m^{s_m} $$ where $p_i$ denotes some prime $\le t$, and $q_j$ denote some prime $>t$. Thus, we have
$$ d(n)=\prod_i(r_i+1)\prod_j(s_j+1) $$ By definition, we know that $k\le t$ and $r_i<\log_2 n$, so we have
\begin{aligned} d(n) &\le\left(1+\log_2n\right)^k\prod_j(s_j+1)\le(1+\log_2n)^t\prod_j2^{s_j} \\ &=(1+\log_2n)^t\prod_j q_j^{s_j\log2/\log q_j}<(1+\log_2n)^t\prod_jq_j^{s_j\log2/\log t} \\ &\le(1+\log_2n)^tn^{\log2/\log t}=\exp\{t\log(1+\log_2n)+\log2\log n/\log t\} \\ &\le2^{\log n/\log t+O(t\log\log n)} \end{aligned}
Finally, setting $t=\log n/(\log\log n)^3$ gives $d(n)<2^{(1+\varepsilon)\log n/\log\log n}$ for large $n$.
For OP's question on the specific inequality, let $A_1,A_2,\dots$ denote the O constants then \begin{aligned} (A_1\varepsilon^{-1})^{\exp(\varepsilon^{-1})} &=\exp[\exp(\varepsilon^{-1})\log(A_1\varepsilon^{-1})] \\ &<\exp[\exp(\varepsilon^{-1})\exp(A_2\varepsilon^{-1})] \\ &=\exp\{\exp[(1+A_2)\varepsilon^{-1}]\}=\exp\exp O(\varepsilon^{-1}) \end{aligned}