Growth rates slower than logarithmic?

878 Views Asked by At

So far, I've been able to determine growth rates using the following limit:$$\lim_{x\to\infty}\frac{f(x)}{g(x)}$$Which, if need be, can be solved with calculus.

From this, I deduced that it is very difficult to have a function $f(x)$ that grows slower than a function $g(x)=\ln(x)$.

I noted a few, the Lambert W function, or something simple like $\sqrt{\ln(x)}$. This means we are excluding composite functions.

However, I wondered if there are any "parent" functions that have slower growth rates than a logarithm.

This is excluding non-elementary things like the Lambert W function or the inverse factorial.

And by "parent" function, I mean you cannot combine multiple $x$'s or apply multiple operations to $x$.

That is, we can't try to do something silly like $\ln[\ln(x)]$ or $x-\ln(x)$.

One function, one operation, elementary functions only. By elementary functions, I define an elementary function as being analytic and algebraic, unlike the inverse factorial or Lambert W function or similar things.

Can we have growth slower than logarithmic under these restrictions?

EDIT

One last restriction. The proposed function $g(x)$ must have the following:$$\lim_{x\to\infty}g(x)=\infty$$

Because it has come to my attention that horizontal asymptotes may apply.

1

There are 1 best solutions below

0
On BEST ANSWER

Suppose $f(x)$ is an algebraic function which tends to infinity as $x$ tends to infinity. We can rewrite the algebraic equation which it satisfies to a form $a_n(f(x))x^n+...+a_1(f(x))x+a_0(f(x))=0$, where $a_i$ are polynomials and $a_n$ is nonzero. Let $d$ be the largest of the degrees of $a_i$. I claim $f(x)$ can't grow slower than $x^{1/(d+2)}$, by which I mean $\lim\limits_{x\rightarrow\infty}\frac{f(x)}{x^{1/(d+2)}}=0$. If this were the case, then we would have, for large $x$, $$|a_{n-1}(f(x))x^{n-1}+...+a_1(f(x))x+a_0(f(x))|\leq|a_{n-1}(f(x))|x^{n-1}+...+|a_1(f(x))|x+|a_0(f(x))|\leq x^{(d+1)/(d+2)}x^{n-1}+...+x^{(d+1)/(d+2)}x+x^{(d+1)/(d+2)}<x^n\leq |a_n(f(x))x^n|$$ where second inequality is true because $a_i(f(x))<f(x)^{d+1}<(x^{1/(d+1)})^{d+2}$ for $f(x)$ sufficiently large. If you look closely, this implies that $f(x)$ cannot satisfy assumed inequality for large $x$.

This allows us to answer your question in negative: every algebraic function which tends to infinity isn't slower than some power function, so can't grow slower than logarithmic function.