5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I'm having some trouble understanding your question. Are you asking whether there exists a sublinear function $g$, such that for every function $f$, $f$ composed with some finite number of $g$-s is bounded by polynomial? $\endgroup$ – xyzzyz May 28 '16 at 0:01
  • $\begingroup$ @xyzzyz No, I have both $f$ and $g$ given. If only $f$ was given and I would ask if there always exists any sublinearly growing function $g$ so that $g \circ ... g \circ f$ is bounded by a polynomial, then the answer would trivially be yes (I believe), since we can just set $g ≤ min\{f^{-1}, x\}$ (i.e. the minimum of the inverse function and $x$). $\endgroup$ – moran May 28 '16 at 0:09
3
$\begingroup$

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$.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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)$.

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$

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.