Proving that the limit of a composite function is larger than 1

Question

Let $k>1$. Assume that $f(x)$ a function such that \begin{equation} \liminf_{x\rightarrow \infty}\frac{f(x)\bigg(1+x+\frac{x^2}{2!}+\dots+\frac{x^{K-1}}{(K-1)!}\bigg)}{e^x} \geq 1. \end{equation} Let \begin{equation} g(y) = \log y + (K-1)\log\log y +o(\log\log y) \end{equation} where $o(\cdot)$ is defined as here http://mathworld.wolfram.com/Little-ONotation.html. I am trying to show that \begin{equation} \liminf_{y\rightarrow \infty}\frac{f(g(y))}{y} \geq 1. \end{equation} This is a result I found and was written without sufficient explanation. Also, if someone could provide an intuition as to how to come up with the $g(y)$ that satisfies the last inequality (assuming that that the $g(y)$ was not given) that would be really helpful! Thanks!

Answer 1

Let $a_k(x)=\sum_{j=0}^{k-1}\frac{x^j}{j!}$ denote the sum in the numerator. The assumption becomes

$$\liminf_{x\rightarrow\infty}\frac{f(x)a_k(x)}{e^x}\geq 1$$

This immediately gives the definition of Knuth $\Omega$ order notation:

$$\liminf_{x\rightarrow\infty}\frac{f(x)a_k(x)}{e^x}>0 \iff f(x)a_k(x) = \Omega(e^x)$$

Since $a_k(x)$ is a polynomial by definition, the order of $f(x)$ must be at least exponential:

$$\implies f(x) = \Omega(e^x) $$

The order of $g(y)$ is the order of its maximum term, which is $\log y$:

$$ g(y) = \log y + \log\log y + o(\log\log y)= \Theta(\log y)$$

From the previous two equations we see the order of $f(g(y))$ is at least $e^{\log y}$, the identity function, which is linear.

$$ f(g(y)) = \Omega(e^{\log(y)})$$

$$ \implies f(g(y)) = \Omega(y) $$

By definition of $\Omega$, this gives

$$\liminf_{y\rightarrow\infty}\frac{f(g(y))}{y}> 0$$

However, as the other answer shows, this limit is not necessarily greater than or equal to $1$, so OP's claim is false.

Answer 2

I believe that the result is false.

Choose $K=2$, $g(y) = \log(y) + \log\log y -1$, and $f(x) = g^{-1}(x)/2$.

Then

$$\liminf_{x\rightarrow\infty} \frac{f(x)(1+x)}{\exp(x)}=\liminf_{y\rightarrow\infty} \frac{f(g(y))(1+g(y))}{\exp(g(y))}$$ $$=\liminf_{y\rightarrow\infty} \frac{\frac{y}{2}(1+g(y))}{(y \log y)/e}=\liminf_{y\rightarrow\infty} \frac{1+g(y)}{\log y}\cdot\frac{e}{2}$$ $$\geq \liminf_{y\rightarrow\infty} \frac{1+\log y}{\log y}\cdot\frac{e}{2} = e/2\geq 1.$$

So, $f(x)$ satisfies the condition. But, $$ \liminf_{y\rightarrow\infty} \frac{f(g(y))}{y} = \frac{y/2}{y} = 1/2 < 1. $$