My New Favorite Function
My new favorite function
Have you ever wanted a function that grows faster than a polynomial but slower than an exponential? It’s a fun challenge to try for yourself. Here’s an example (but be warned, this is the last time I’ll spoiler tag something).
Example
\[e^{\ln(x)^2}\]
It’s clear that this grows sub-exponentially, as \(\ln(x) < x\), but after some thought, it still wasn’t clear to me that this would grow faster than a polynomial (based on intuition alone). The related function \(e^{\ln(x)}\) grows linearly, so a priori couldn’t this one grow quadratically? If the brackets were another way (\((e^{\ln(x)})^2\)) then it would. A good rule of thumb for exponentials is that brackets starting from the right grow faster, so intuitively we can argue super-quadratic growth - but super-polynomial? That needs more justification.
To see why it is super-polynomial, note the following:
\[e^{\ln(x)^2} = e^{\ln(x)\ln(x)} = x^{\ln(x)}\]
So obviously the exponent of \(\ln(x)\) eventually surpasses any constant exponent \(c\). Didn’t expect that, did you? Well, maybe you did, but I didn’t!
I like this function for a few reasons:
- It’s a cool example of what are called Quasi-Polynomial Functions, i.e. those of the form \(\exp(\mathrm{polynomial}(\log x))\), which as super-polynomial but sub-exponential.
- It shows why such functions, despite being sub-exponential, are intractable (in the algorithmic runtime sense).
I’ll elaborate on the second point. When does our quasi-polynomial surpass a polynomial of degree \(c\)? Well, \(x^{\ln(x)} > x^c \iff \ln(x) > 2 \iff x > e^c\). At first glance, this seems good - it takes exponentially large \(x\) to surpass a polynomial of fixed size. However, polynomials start becoming intractable in practice for a low value of \(c\) - let’s say \(c=5\), since every time I’ve used an algorithm with a quintic runtime I’ve regretted it. This just requires \(x=149\) for our quasi-polynomial to surpass it, quite a low value!
Despite this, it’s clearly only “on the edge of intractable”. If we instead claimed \(c=10\) was the limit of tractability, we are tractable until \(x=22027\). Its tractability is really only held back by the fact that polynomials become intractable at low exponents.
My favorite function
\(e^{\ln(x)^2}\) was very briefly my favorite function, but it is not currently my favorite function. Rather, that is this:
\[x^{\ln\ln(x)}\]
It’s still super-polynomial/sub-exponential (and is also “sub-quasi-polynomial”). It is also quite tractable as far as runtimes go - a \(c=5\) tractability cutoff only occurs when \(x=e^{e^5} > 10^{64}\). This is more than the number of atoms in the Earth (\(\sim 10^{50}\)), so if you have to deal with a problem that large, you’re already in trouble even with a linear-time algorithm. You need a doubly exponentially large input before things become intractable!
That’s certainly part of the reason why I like it; it is a “natural technically intractable tractable function” (which is a very fun phrase to say!). However, there’s another reason, which connects it with my childhood love of tetration:
\[x^{\ln\ln(x)} = e^{\ln(x)\ln\ln(x)} = \ln(x)^{\ln(x)} = \ln(x)\uparrow\uparrow 2\]
Not only is the identity \(x^{\ln\ln(x)} = \ln(x)^{\ln(x)}\) pleasing, but its slow growth is quite surprising in light of its tetrational nature. Intuitively, I’d have thought through the growth rate of \(\ln(x)\uparrow\uparrow 2\) as follows:
- \(x\uparrow\uparrow 2\) grows very very fast; it’s the beginning stage of tetration, after all!
- \(\ln(x)\) grows exponentially slow, so \(\ln(x)\uparrow\uparrow 2\) will be slower than \(x\uparrow\uparrow 2\), but still fast-growing (because tetration >> exponentiation, exponential slowness can’t bring it down that much.
However, this intuition is wrong - the exponential slowness of \(\ln(x)\) is enough to bring it down to something effectively polynomial.
Other functions
Both functions considered so far have been of the form \(x^{\ln^n(x)}\). Technically, \(x^{\ln^n(x)}\) grows faster than any polynomial, but we’ve already seen that (when restricting to human scales) for \(n\geq 2\) it in practice does not. If \(n=3\), this function will not beat even a quadratic until about \(x=10^{703}\). In fact, it’s easy to see that, as \(n\) increases, the intractability threshold recedes away from us tetrationally.
We also have the generalized identity, which is sadly only interesting for \(n=2\):
\[x^{\ln^n(x)} = e^{\ln(x)\ln^n(x)} = \left(\ln^{n-1}(x)\right)^{\ln(x)}\]
In general, any function \(x^{f(x)} = e^{\ln(x)f(x)}\), for unbounded \(f\), is super-polynomial. If \(f(x) << \frac{x}{\ln(x)}\) then it will also be sub-exponential. We saw that \(x^{\ln(x)}\) was close-to-tractable; if we want a definitively intractable sub-exponential function, all we need to consider is \(x^{\sqrt{x}}\).
One last word
What about \(\ln(x)\uparrow\uparrow n\) for some constant \(n\)? This is much faster growing; for \(n=3\), this passes our \(c=5\) threshold when \(x=15\). As \(n\) increases, we still get that extremely rapid tetrational growth. It is no longer sub-exponential:
\[\ln(x)\uparrow\uparrow 3 > e^{\ln(x)\uparrow\uparrow 2}\text{ (for large enough }x\text{)}\]
As we already established that \(\ln(x)\uparrow\uparrow 2\) grows super-polynomially, we must have that \(\ln(x)\uparrow\uparrow 3\) is super-exponential!