For some arbitrarily fast growing function $f$ and a strictly sublinear function $g$, can $g \circ \cdots \circ g \circ f$ always grow polynomially?

Question

Given two functions $f, g: \mathbb{R}_{≥ 0} \to \mathbb{R}_{≥ 0}$ that are monotonically growing, with $g(x) \in o(x)$ (i.e. $g$ grows strictly sublinear), does there always exist an $m \in \mathbb{N}$ so that $\underbrace{g \circ \cdots \circ g}_{m \text{ times}} \circ f(x) \in O(x^k)$ (for some $k \in \mathbb{N}$)?

In other words, for any arbitrarily fast growing function $f$ and for some strictly sublinearly growing function $g$ (that might just grow a little bit "slower" than linear, e.g. $g(x) = x^{1 - \epsilon}$), can we always compose $f$ sufficiently many times with $g$ so that the resulting function grows (at most) as fast as a polynomial? (If that's not the case, is the statement true for all "sensible" functions $f$, i.e. if $f$ is calculable?)

I've been thinking about it for a while but couldn't really figure it out, and subsequently couldn't find a way to prove or disprove the statement either. The (probably biggest) problem here is for me that I barely know anything about how the asymptotic behaviour of functions under composition. It seems clear to me that $g \circ g(x) \in o(g(x))$, so with each composition, the resulting function grows asymptotically strictly slower, but that might not be enough, seeing as $f$ might literally explode for small values already, e.g. if we set $f$ to be the Ackermann function. I couldn't really construct a counter-example either, though.

Answer 1

If you fix any non-decreasing $g$ with $\lim_{x\rightarrow\infty}g(x)=\infty$, you can construct an $f$ such that $g^n\circ f$ always grows faster than any polynomial, where $$g^n=\underbrace{g\circ g\circ \ldots \circ g\circ g}_{n\text{ times}}.$$ To do so, define $h(x)=\min(x,g(x))$ and let $$f(x)=\inf\{y:h^{\lfloor x\rfloor}(y)>e^x\}+1.$$ where $\lfloor x \rfloor$ is the floor function. Noting that $h\leq g$ pointwise, we get that for integer $m$ we have $$g^m(f(m))\geq h^m(f(m))>e^m,$$ since $f(x)$ is by definition not a lower bound for the set $\{y:g^{m}(y)>e^m).$ Moreover, we have that $$g^n(f(m))\geq h^n(f(m)) \geq h^m(f(m))> e^m,$$ meaning that $g^n\circ f$ grows at least exponentially for any $n$.

Answer 2

Let $g(x) = \sqrt{x}$ and $f(x)=e^x$. Then

$$ g\circ g\circ \cdots g\circ f(x) = e^{\frac{x}{2^m}} $$ which for any finite $m$ grows fater than polynomially.

Answer 3

For $f = \exp$ and $g = \sqrt x$ any $m ∈ ℕ_0$, $$g^m ∘ f = \sqrt[2^m] \exp.$$ But for all $k ∈ ℕ_0$, $\sqrt[2^m] \exp \notin \mathcal O (x^k)$.

Answer 4

Let $g(x)=\frac{x+e}{\ln(x+e)}-e$. (Compared to $\frac{x}{\ln(x)}$, the shifts by $e$ guarantee that the function meets OP conditions for $g$). It's true that $$(\overbrace{g\circ\cdots\circ g}^n)(x)\geq\frac{x+e}{\ln(x+e)^n}-e$$ This is clear for $n=1$ and proven inductively:

$$ \begin{align} (\overbrace{g\circ\cdots\circ g}^n)(x) =g\left((\overbrace{g\circ\cdots\circ g}^{n-1})(x)\right) &\geq g\left(\frac{x+e}{\ln(x+e)^{n-1}}-e\right)\\ &=\frac{\frac{x+e}{\ln(x+e)^{n-1}}-e+e}{\ln\left(\frac{x+e}{\ln(x+e)^{n-1}}-e+e\right)}\\ &=\frac{\frac{x+e}{\ln(x+e)^{n-1}}}{\ln\left(\frac{x+e}{\ln(x+e)^{n-1}}\right)}\\ &>\frac{\frac{x+e}{\ln(x+e)^{n-1}}}{\ln\left(\frac{\color{blue}{x\ln(x+e)^{n-1}}}{\ln(x+e)^{n-1}}+\color{blue}{e}\right)}\\ &=\frac{\frac{x+e}{\ln(x+e)^{n-1}}}{\ln\left(x+e\right)}=\frac{x+e}{\ln(x+e)^n}>\frac{x+e}{\ln(x+e)^n}-e\\ \end{align} $$

Now take $f(x)=e^x-e$, and $(\overbrace{g\circ\cdots\circ g}^n\circ f)(x)=\frac{e^x}{x^n}-e$, which grows super polynomially.

Answer 5

People have given the answer, this is about the intuition.

Rapidly increasing functions can be made unimaginably fast. In particular you can take $g$ as an input to the construction and make functions that are fast-growing relative to $g$ and iterations of $g$ and Ackermannizations of $g$. For any fixed computation based on $g$ you could engineer fast growing $f$ whose composition defeats $g$.

Any easily described slow $g$ that you write down will be dominated in "slowness" by some $G_\alpha^{-1}(x)$ that is inverse to a function at level $\alpha$ of one of the rapid growing function hierarchies (or a linear interpolation of that to a real function instead of integer). Then take $f$ to be anything at a level higher than $\alpha$.