1
$\begingroup$

Suppose that we have $$ n=k^{\frac{1}{\beta}k^22^{k+12}\log\frac 1{\alpha}} $$ where $\alpha,\beta\in(0,1)$. It is claimed that $$ k\sim C\log\log n $$ for some constant $C=C(\alpha,\beta)$. How do one deduce such an estimate?

I am totally lost here, any help is very much appreciated.

$\endgroup$
1
$\begingroup$

I assume logarithms in base $2$. This would not change anything anyway, besides constants.

First, note that $$ n=k^{\frac{1}{\beta}k^22^{k+12}\log\frac{1}{\alpha}} = 2^{\frac{1}{\beta}k^22^{k+12}\log\frac{1}{\alpha} \log k} = 2^{\frac{2^{12}\log\frac{1}{\alpha}}{\beta}k^22 ^{k} \log k} $$ so $$ \log n = \frac{2^{12}\log\frac{1}{\alpha}}{\beta}\cdot k^22 ^{k} \log k = C'\cdot 2 ^{k + 2\log k+\log\log k} $$ setting $C'\stackrel{\rm def}{=} \frac{2^{12}\log\frac{1}{\alpha}}{\beta}$.

Taking the logarithm again, we get $$ \log\log n = k + 2\log k+\log\log k + O(1) $$ and, when $k\to\infty$, the right-hand side satisfies $$k + 2\log k+\log\log k + O(1)\operatorname*{\sim}_{k\to\infty} k$$ which implies $$ \log\log n\operatorname*{\sim}_{k\to\infty} k. $$

$\endgroup$
  • $\begingroup$ Yes you are right, it is actually $\log\frac 1{\alpha}$. $\endgroup$ – BigbearZzz Feb 23 '17 at 21:25
  • $\begingroup$ So $C(\alpha,\beta)$ is really independent of $\alpha$ and $\beta$? At first I arrive at something very similar but I thought I was wrong since I got $C=1$. $\endgroup$ – BigbearZzz Feb 23 '17 at 21:29
  • $\begingroup$ As far as I can tell: you are only looking at the first-order term, so yes. $\endgroup$ – Clement C. Feb 23 '17 at 21:32
  • $\begingroup$ Thank you very much! Anyway, I'm just curious as to what you meant by "first order term". What does it mean to calculate an asymptotic to the, says, second order? $\endgroup$ – BigbearZzz Feb 23 '17 at 21:35
  • $\begingroup$ Think of it as an approximation of the form $f(x) \sim_{x\to\infty} x$. This is the first term; you can also write it $f(x) = x + o(x)$, or $\frac{f(x)-x}{x} \xrightarrow[x\to\infty]{} 0$. But you good tdo an expansion of that sort to lower order terms: e.g., $f(x) = x+\sqrt{x} + o(\log x)$ (meaning $\frac{f(x)-(x+\sqrt{x})}{\log x}\xrightarrow[x\to\infty]{} 0$ "the function $f$ is well-approximated at $\infty$ by the simpler function $x+\sqrt{x}$, and the remaining term is negligible in front of $\log x$". $\endgroup$ – Clement C. Feb 23 '17 at 21:39

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.