# Smooth Elementary Function that Outgrows All Tower Functions?

This started off with me goofing off on Twitter and quickly led to this question to which I didn't know the answer.

Let $$T_2(x) = x^x$$, $$T_3(x) = x^{x{^x}}$$, $$T_4(x) = x^{x^{x^x}}$$, and so forth.

Is there a $$C^{\infty}$$ elementary function $$f(x)$$ (it can be piecewise-defined) with $$\displaystyle \lim\limits_{x \to \infty} \frac{f(x)}{T_k(x)} = \infty$$ for all $$k$$? If so, what is a (possibly piecewise-defined) formula for such an $$f$$?

• (I tried $f(x) = T_k(x)$ on [k+(1/4), k+(3/4)] and linearly interpolating between endpoints, but I couldn't find a way to make that both smooth (convoluting with Gaussians would do that, but it wouldn't be elementary then) and elementary (it's already elementary but not smooth.) – Jeffrey Rolland Jan 4 '19 at 9:03
• Possibly related: math.stackexchange.com/questions/1892870/… – Martin R Jan 4 '19 at 9:03
• (The Smooth Approximation Theorem from differential topology also does not guarantee an elementary solution.) – Jeffrey Rolland Jan 4 '19 at 9:04
• @Martin R. Mmm, the second answer in that question in close, but doesn't allow piecewise-defined functions; I already found an elementary piecewise-defined function that contradicts the second answer. – Jeffrey Rolland Jan 4 '19 at 9:09
• I am no expert on this topic at all. My guess would be that a similar approach as in this comment might work: Define $f$ on the positive integers as $f(k) = T_k(k)$, and smoothly interpolate between the integers. – Martin R Jan 4 '19 at 9:22

Disclaimer:

There are no such elementary functions, the below constructions are non-elementary but still interesting.

For starters, one can construct a simple $$C^k$$ function for any $$k\in\mathbb N$$ simply by integrating as follows:

$$\int_1^x\int_1^{x_1}\dots\int_1^{x_k}T_{\lfloor x_{k+1}\rfloor}(\lfloor x_{k+1}\rfloor)~\mathrm dx_{k+1}~\mathrm dx_k\dots\mathrm dx_2~\mathrm dx_1$$

which is trivially $$k$$ times continuously differentiable and grows faster than $$T_m(x)$$ for all $$m\in\mathbb N$$.

For $$C^\infty$$ functions, I give special mentions to Wojowu a.k.a. LittlePeng9 for fast growing analytic functions. I will give a slightly simplified construction here.

Let $$f:\mathbb C\mapsto\mathbb C$$ satisfy the following properties:

1. $$f$$ is entire.

2. $$|f(z)|\le z$$ for all $$|z|<1$$.

Consider the following function:

$$g(z):=\sum_{n=1}^\infty f^n\left(\frac z{2^n}\right)$$

where $$f^n$$ denotes function iteration i.e. $$f^2(x)=f(f(x)),f^3(x)=f(f(f(x))),$$ etc.

For $$|z|<1$$ we have

$$|f^n(z)|=|f(f^{n-1}(z))|\le|f^{n-1}(z)|\le\dots\le|z|$$

it follows that $$|g(z)|\le|z|$$ when $$|z|<1$$ by the geometric series.

Likewise, since $$\lim_{n\to\infty}z/2^n=0$$ for all $$z$$, from the Weierstrass M-test, it follows that $$\sum_{n=1}^\infty f^n\left(\frac z{2^n}\right)$$ converges uniformly everywhere and hence is entire.

Now, on the other hand, if $$f$$ is increasing on $$\mathbb R^+$$ (and hence positive on $$\mathbb R^+$$), then for all $$N\in\mathbb N$$ and $$x\in\mathbb R^+$$, we have $$g(x)\ge f^N(x/2^N)$$.

And since $$g$$ satisfies all the conditions that $$f$$ required, this can be repeatedly applied to generate increasingly faster growing analytic functions.

Take, for example $$f(z)=\frac12(e^z-1)$$, which satisfies all of the requirements. The corresponding $$g$$ defined above hence grows faster than $$f^N(x/2^N)$$ for all $$N$$, and hence faster than your functions, namely since:

$$\lim_{x\to\infty}\frac{g(x)}{T_k(x)}\ge\lim_{x\to\infty}\frac{f^{k+1}(x/2^{k+1})}{T_k(x)}=+\infty$$

For justification of the last limit, one can easily see that $$f(x)$$ is eventually greater than $$2^x$$, and that $$x<2^x\le x^x\le(2^x)^x=2^{x^2}\le2^{2^x}\le x^{x^x}\le\dots$$