Para una función de crecimiento arbitrariamente rápido $f$ y una función estrictamente sublineal $g$ puede $g \circ \cdots \circ g \circ f$ ¿crecen siempre polinómicamente?

Question

Dadas dos funciones $f, g: \mathbb{R}_{ 0} \to \mathbb{R}_{ 0}$ que crecen monotónicamente, con $g(x) \in o(x)$ (es decir $g$ crece de forma estrictamente sublineal), ¿existe siempre un $m \in \mathbb{N}$ para que $\underbrace{g \circ \cdots \circ g}_{m \text{ times}} \circ f(x) \in O(x^k)$ (para algunos $k \in \mathbb{N}$ )?

En otras palabras, para cualquier función de crecimiento arbitrariamente rápido $f$ y para alguna función estrictamente creciente de forma sublineal $g$ (que podría crecer un poco más "despacio" que lineal, por ejemplo. $g(x) = x^{1 - \epsilon}$ ), ¿podemos componer siempre $f$ suficientes veces con $g$ de modo que la función resultante crezca (como máximo) tan rápido como un polinomio? (Si no es así, ¿es cierta la afirmación para todas las funciones "sensibles" $f$ es decir, si $f$ es calculable?)

He estado pensando en ello durante un tiempo, pero no he conseguido entenderlo y, posteriormente, tampoco he encontrado la forma de demostrar o refutar la afirmación. El (probablemente mayor) problema aquí es para mí que apenas sé nada sobre cómo el comportamiento asintótico de funciones bajo composición. Me parece claro que $g \circ g(x) \in o(g(x))$ por lo que con cada composición, la función resultante crece asintóticamente de forma estrictamente más lenta, pero eso podría no ser suficiente, ya que $f$ podría explotar literalmente ya para valores pequeños, por ejemplo, si establecemos $f$ para ser la función de Ackermann. Sin embargo, tampoco pude construir un contraejemplo.

Answer 1

Sea $g(x) = \sqrt{x}$ y $f(x)=e^x$ . Entonces

$$ g\circ g\circ \cdots g\circ f(x) = e^{\frac{x}{2^m}} $$ que para cualquier $m$ crece más rápido que polinomialmente.

Answer 2

Si fija cualquier $g$ con $\lim_{x\rightarrow\infty}g(x)=\infty$ se puede construir un $f$ tal que $g^n\circ f$ siempre crece más rápido que cualquier polinomio, donde $$g^n=\underbrace{g\circ g\circ \ldots \circ g\circ g}_{n\text{ times}}.$$ Para ello, defina $h(x)=\min(x,g(x))$ y que $$f(x)=\inf\{y:h^{\lfloor x\rfloor}(y)>e^x\}+1.$$ donde $\lfloor x \rfloor$ es la función suelo. Teniendo en cuenta que $h\leq g$ puntualmente, obtenemos que para enteros $m$ tenemos $$g^m(f(m))\geq h^m(f(m))>e^m,$$ desde $f(x)$ no es por definición un límite inferior para el conjunto $\{y:g^{m}(y)>e^m).$ Además, tenemos que $$g^n(f(m))\geq h^n(f(m)) \geq h^m(f(m))> e^m,$$ lo que significa que $g^n\circ f$ crece al menos exponencialmente para cualquier $n$ .

Answer 3

Sea $g(x)=\frac{x+e}{\ln(x+e)}-e$ . (En comparación con $\frac{x}{\ln(x)}$ los desplazamientos por $e$ garantizar que la función cumple las condiciones OP para $g$ ). Es cierto que $$(\overbrace{g\circ\cdots\circ g}^n)(x)\geq\frac{x+e}{\ln(x+e)^n}-e$$ Esto está claro para $n=1$ y demostrado inductivamente:

$$ \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} $$

Ahora toma $f(x)=e^x-e$ y $(\overbrace{g\circ\cdots\circ g}^n\circ f)(x)=\frac{e^x}{x^n}-e$ que crece de forma superpolinómica.

Answer 4

Para $f = \exp$ y $g = \sqrt x$ cualquier $m _0$ , $$g^m f = \sqrt[2^m] \exp.$$ Pero para todos $k _0$ , $\sqrt[2^m] \exp \notin \mathcal O (x^k)$ .

Answer 5

La gente ha dado la respuesta, se trata de la intuición.

Las funciones que aumentan rápidamente pueden realizarse con una rapidez inimaginable. En particular, puede tomar $g$ como entrada a la construcción y realizar funciones de rápido crecimiento en relación con $g$ e iteraciones de $g$ y Ackermannizaciones de $g$ . Para cualquier cálculo fijo basado en $g$ usted podría diseñar $f$ cuya composición derrota $g$ .

Cualquier lentitud fácil de describir $g$ que anote estará dominado en "lentitud" por algún $G_\alpha^{-1}(x)$ que es inversa a una función a nivel $\alpha$ de una de las jerarquías de funciones de crecimiento rápido (o una interpolación lineal de ésta a una función real en lugar de entera). A continuación, tome $f$ ser cualquier cosa en un nivel superior a $\alpha$ .