Prove an equivalence of asymptotic formulas

20 Views Asked by At

I have the following:

$$\Omega\left(\frac{\log N}{\log\log N}\right)\leq n.$$

The claim is that this implies $$N\leq n^{O(n)}.$$

I have made no progress on proving that this is true. Does anybody have an idea of where to start? Thanks in advance.

1

There are 1 best solutions below

1
On BEST ANSWER

$$\log N \ll n \log\log N \tag{1}$$ $$ N \leq \exp(C n \log\log N) = (\log N)^{Cn}\ll(n\log\log N)^{Cn} \tag{2}$$ $$ \log\log N \ll \log(n)+\log\log\log N \tag{3}$$ If we keep using $\log N\ll n\log\log N$ in the RHS of $(3)$ we end up with $$ \log\log N \ll \log(n)+\log\log(n)+\log\log\log(n)+\ldots \ll \log^2(n) \tag{4}$$ which plugged into $(2)$ gives $$ N \ll (n \log^2(n) )^{Cn} \ll n^{(C+\varepsilon)n}.\tag{5} $$