We all know that exponential functions grow faster than polynomials. Let us consider the following function: $f(n) = n^{a_1} \cdot (\log n)^{a_2}\cdot (\log \log n)^{a_3} \cdot (\log \log \log n)^{a_4}\cdots$ where the leading coefficient $a_k$ is positive.

I think anything that is "slowly growing" has this type of asymptotic expansion. In short, this type of representation is "complete": there is nothing between $n$ and $n \log n$ other than a member of the above class, for instance $n \cdot (\log n)^{1/2}\cdot(\log \log \log n)^5 / (\log \log n)^3$.

Is my statement true? How can one make it rigorous, assuming it is correct? Also,

(1) What would be the slowest growing function that grows faster than the fastest growing function in the above class?

(2) Provide an example of function growing faster than the fastest growing function in that class, but more slowly than $\exp n$.

(3) What happens if you allow the coefficients $a_k$ not to be bounded, and the sequence $\{a_k\}$ to be infinite? For instance consider $f(n) = n \cdot (\log n)^2 \cdot (\log \log n)^4 \cdot (\log \log \log n)^8\cdots$

In short, is there some kind of topological framework that handles manipulations over these functions? Indeed, they are not functions, but asymptotic representations or quantities instead. It's a different type of mathematical objects, with its own arithmetic and topology.

  • 2
    $\begingroup$ I am not quite sure how to handle your whole question, but I will point out that the infinite case has a definition problem in that the arbitrarily nested logarithm has an arbitrarily small domain. And taking absolute values everywhere doesn't fix the problem, I think. $\endgroup$ – Ian May 21 at 16:34
  • $\begingroup$ Is $n+\frac1{n!}$ in the above class?Intuitively I would assume not but my intuition may be wrong. $\endgroup$ – kingW3 May 21 at 16:56
  • $\begingroup$ Yes, $n + \frac{1}{n!}$ is equivalent to $n$. $\endgroup$ – Vincent Granville May 21 at 17:12
  • 1
    $\begingroup$ For (1) you can take square-roots (for example) so there are no slowest one. Similarly, for (2) we can have things like $\exp\sqrt{n}$ or $n^{\log\log\dots\log n}$, etc. $\endgroup$ – user10354138 May 21 at 17:38
  • 2
    $\begingroup$ I mean: if $f$ grows faster than your class, then $\sqrt{f}$ also grows faster than your class. But of course $\sqrt{f}$ grows slower than $f$. $\endgroup$ – user10354138 May 21 at 18:20

Your Answer

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

Browse other questions tagged or ask your own question.