Are there functions $f$ and $g$ such that $f \circ g$ is exponential even though neither $f$ nor $g$ is?

Question

To be precise, call a function $f$ exponential if $f(n) = \Omega\bigl(2^{n^c}\bigr)$ for some constant $c > 0$.

Some motivation: composing two exponential functions yields a doubly exponential function even though neither of the original functions was doubly exponential. I'm wondering if the same can be done "one level lower". Is there a class of functions not containing the exponentials but where composing two members produces an exponential? Note that neither the polynomials nor the quasipolynomials will do as both classes are closed under composition.

Answer 1

We can find $f$ such that $f\circ f=\exp$ (namely, define $f(x)=x+\frac12$ for $0\le x\le \frac12$, $f(x)=e^{x-\frac12}$ for $\frac12\le x\le 1$, and so on, i.e., extend $f$ recursively by letting $f(x)=e^{f^{-1}(x)}$ interval by interval). As you already know that the composition of exponentials cannot yield $\exp$, this seems to be what you are looking for.

More explicitly, we recursively define $a_n\in\Bbb R$ by $$ a_0=0,\qquad a_1=\frac12,\qquad a_n=e^{a_{n-1}}\text{ for }n\ge2.$$ Then $a_0<a_1<a_2<\ldots$ and $a_n\to \infty$. Now we define $f_n\colon[a_0,a_n]\to [a_1,a_{n+1}]$ for $n\in\Bbb N_{0}$ with the following properties:

1. $f_n$ is a homeomorphism and maps $a_n\mapsto a_{n+1}$
2. $f_{n+1}|_{[a_0,a_{n}]}=f_{n}$
3. $f_{n+1}( f_{n}(x))=e^x$ for $a_0\le x\le a_n$.

We start with $f_0(0)=\frac12$ and $f_1(x)=x+\frac12$ and verify the three properties for these. Assume we already have a homeomorphism $f_n\colon [a_0,a_n]\to[a_1,a_{n+1}]$ that maps $a_n\mapsto a_{n+1}$. Then $\exp\circ f_n^{-1}$ is a homeomorphism $[a_1,a_{n+1}]\to [a_0,a_n]\to [a_2,a_{n+2}]$ such that on $[a_1,a_n]$, we have $\exp\circ f_n^{-1}=\exp\circ f_{n-1}^{-1}=f_n\circ f_{n-1}\circ f_{n-1}^{-1}=f_n$. Thus we can define $f_{n+1}\colon[a_0,a_{n+1}]\to[a_1,a_{n+2}]$ by $$f_{n+1}(x)=\begin{cases}f_n(x)&a_0\le x\le a_n\\ e^{f_n^{-1}(x)}&a_1\le x\le a_{n+1} \end{cases}$$ and automatically obtain the three properties.

Now define $f\colon[0,\infty)\to\Bbb R$ by letting $f(x)=f_n(x)$ for any $n$ with $a_n>x$. This is well-defined by property (2), is a homeomorphism $[0,\infty)\to[\frac12,\infty)$ by (1) and $a_n\to\infty$, and $f(f(x))=e^x$ for all $x\ge 0$.

Answer 2

Consider $f(x)=2^{\ln^2{x}}$, $g(x)=2^{2^{\frac{\ln{x}}{\ln{\ln{x}}}}}$.