8
$\begingroup$

Notation: ${^n}x = x^{x^{\cdots^x}}$ is tetration, i.e. $x$ to the power of itself $n$ times. $\mathrm{srt}_n(x)$ is the super $n$-th root, or the inverse function of ${^n}x$, which is well defined for $x\ge 1$. I can prove that $$ \lim\limits_{n\rightarrow\infty} \mathrm{srt}_n\left({^{n+1}}2\right) $$ converges to some value between about $\mathrm{srt}_3(256)\approx 2.2915$ and about $2.6$, but it is computationally intractable even for relatively small $n$. For example $^5 2\approx 2\times 10^{19728}$.

For ease of notation, we let $s_n = \mathrm{srt}_n(^{n+1}2)$. I would be very surprised if there's a nice closed form of $\lim\limits_{n\rightarrow\infty} s_n$, so I'm mostly interested here in how to approximate it other than a direct computation of the definition, which really isn't all that viable. As noted above, even computing $s_4$ is tough to do from the formula, though taking some logarithms can get you a bit further, it doesn't help much since tetration is much faster than exponentiation. Is there some trick that convert the formula to $s_n$ into something more tractable?

I can see how you could use the same approach as the one I used (see below) to get better lower bounds than $2.29$, but I suspect that would also become extremely difficult to use if you wanted any sort of precision (even one decimal place might be hard).


Proof of convergence: Clearly $s_n > 2$ for all $n$, so it suffices to show $s_n$ is decreasing. Observe:\begin{eqnarray} ^n s_n &=& 2^{\left(^n2\right)} = 2^{\left(^{n-1}s_{n-1}\right)}<(s_{n-1})^{\left(^{n-1}s_{n-1}\right)} = {^n}(s_{n-1}) \end{eqnarray} since $x\to {^n}x$ is increasing, this implies $s_n$ decreases.

Proof of lower bound: We prove that $s_n > c = \mathrm{srt}_3(256)$ for all $n$ by proving inductively ${^n} c \le\frac{\ln 2}{2\ln(c)} \left({^{n+1}}2\right)$. Since $\frac{\ln 2}{2\ln(c)} <1$, this means ${^n}c<{^{n+1}}2$. Taking $\mathrm{srt}_n$ of both sides shows $s_n>c$.

For the base case, we take $n=2$:\begin{eqnarray} c^{c^c} &=& 256 = 2^8\\ c^c \ln c &=& 8(\ln 2)\\ c^c \ln c &=& \frac12 (\ln 2) 16\\ c^c&=&\frac{\ln 2}{2\ln(c)} \left({^{3}}2\right) \end{eqnarray}

Now, for the inductive step. Suppose ${^n} c \le\frac{\ln 2}{2\ln(c)} \left({^{n+1}}2\right)$ for some $n\ge 2$. Observe that for $x > 4$ (this is not a tight bound):$$ \frac{\ln 2}{2\ln(c)} x < \frac1{\ln c}\ln\left(\frac{\ln 2}{2\ln(c)}\right) + \frac{\ln 2}{\ln c}x $$ Since ${^{n+1}2} > 4$, we therefore have \begin{eqnarray} {^n} c &\le&\frac{\ln 2}{2\ln(c)} \left({^{n+1}}2\right)\\ &<&\frac1{\ln c}\ln\left(\frac{\ln 2}{2\ln(c)}\right) + \frac{\ln 2}{\ln c}\left({^{n+1}2}\right) \end{eqnarray} Taking the $c$th power of both sides yields $$ {^{n+1}} c < \frac{\ln 2}{2\ln(c)} \left(^{n+2}2\right) $$ as desired. Hence we have inductively $$ {^{n}} c < \frac{\ln 2}{2\ln(c)} \left(^{n+1}2\right) $$ for all $n\ge 2$. Therefore $s_n > c$ for all $n$.


Computed with WolframAlpha, the first three terms of $s$ are \begin{eqnarray} s_1 &=& 4\\ s_2 &\approx& 2.74537...\\ s_3 &\approx& 2.58611...\\ s_4 &\approx& 2.57406... \end{eqnarray} Search query used for $s_2$, $s_3$, and $s_4$.

$\endgroup$
3
  • 1
    $\begingroup$ Small note: Bounds can more easily be derived from the more general theorem:$$^n({}^ka)\le{}^{n+k}a\le{}^n({}^{k+1}a)$$which in this case directly gives $2\le s_n\le4$ $\endgroup$ – Simply Beautiful Art Mar 11 '20 at 2:27
  • 1
    $\begingroup$ Related: USAMTS 2/3/11. $\endgroup$ – Simply Beautiful Art Mar 19 '20 at 15:21
  • $\begingroup$ BTW that theorem is easier, but I did the more complicated approach here because a priori one might expect the limit to be 2, so the fact that it's strictly larger is interesting. $\endgroup$ – Dark Malthorp Sep 22 '20 at 16:44
4
$\begingroup$

First we discuss the convergence rate and then evaluate the result to 16 significant figures:


Convergence Rate:


Let us define $f_n(x)={}^nx\ln(x)=\ln({}^{n+1}x)$ and $g_n(x)=\ln(f_n(x))$.

$${}^{n+2}2={}^{n+1}(s_{n+1})$$

$${}^{n+1}2\ln(2)={}^n(s_{n+1})\ln(s_{n+1})$$

$$f_{n+1}(2)=f_n(s_{n+1})$$

We should be able to use $s_n$ as an estimate of $s_{n+1}$. Using a linear approximation we get:

$$f_n(s_{n+1})=f_n(s_n)(1+g_n'(s_n^\star)(s_{n+1}-s_n))$$

for some $s_n^\star\in(s_{n+1},s_n)$ via the mean value theorem. We also have $g_n'(s_n^\star)\ge g_n(s_n)$ for large $n$, which can be verified by log differentiating, which is very large. Substituting this in leaves us with

$$^{n+1}2\ln(2)={}^n(s_n)\ln(s_n)(1+g_n'(s_n^\star)(s_{n+1}-s_n))$$

Since we know that $^{n+1}2={}^n(s_n)$, this reduces to:

$$\ln(2)=\ln(s_n)(1+g_n'(s_n^\star)(s_{n+1}-s_n))$$

Solving for $s_{n+1}$ yields

$$s_{n+1}=s_n+\frac1{g_n'(s_n^\star)}\left(\frac{\ln(2)}{\ln(s_n)}-1\right)$$

Since $2<s_n$, we can see this is decreasing. Since $g_n'(s_n^\star)\to\infty$ tetrationally fast, we have $|s_{n+1}-s_n|\to0$ inversely tetrationally fast i.e. the digits accurate grows tetrationally. This means that we simply need to compute $s_n$ for sufficiently large $n$ and we should have all the digits we'll ever reasonably get.


Results


The general idea for comparing these giant power towers is to repeated apply logarithms and use logarithmic identities to make the problem tractable. From your links, we can already see that you attempted to apply the logarithm once, which yields:

$${}^3(s_4)\ln(s_4)=2^{2^{2^2}}\ln(2)$$

This is numerically evaluated by WolframAlpha to get:

$$s_4=2.574063140898349\dots$$

We can get $s_5$ by applying one more natural logarithm to get

$$^3(s_5)\ln(s_5)+\ln(\ln(s_5))=2^{2^{2^2}}\ln(2)+\ln(\ln(2))\tag{$\star$}$$

which can be numerically solved to give

$$s_5=2.574062876128519\dots$$

As it turns out, the computation of $s_6$ is also reasonably doable, by first applying the base 2 logarithm and then two natural logarithms:

\begin{align}^42\ln(2)+\ln(\ln(2))&=\ln(\ln(\log_2({}^72)))\\&=\ln(\ln(\log_2({}^6(s_6))))\\&=\ln({}^4(s_6)\ln(s_6)+\ln(\log_2(s_6)))\tag{$\star$}\end{align}

which is numerically solved, yielding:

$$s_6=2.574062876128519\dots$$

Side by side, this is:

\begin{align}s_4&=2.574063140898349\dots\\s_5&=2.574062876128519\dots\\s_6&=2.574062876128519\dots\tag{$\star\star$}\end{align}

That is, we can expect the answer to be accurate to the shown digits of $s_5$ and significantly many more digits accurate for $s_6$.

($\star$): One could alternatively just apply base 2 logarithms to get the equivalent expressions:

$$^42={}^3(s_5)\log_2(s_5)+\log_2(\log_2(s_5))$$ $$^42=\log_2({}^4(s_6)\log_2(s_6)+\log_2(\log_2(s_6)))$$

($\star\star$): Extrapolating with a secant approximation of $(\star)$ several times, we can get $s_5$ and $s_6$ to some more figures, assuming WolframAlpha is accurate, yielding:

$$s_5=2.5740628761285190463365497969711386694499537952\dots$$ $$s_6=2.5740628761285190463365497969711386694499537952\dots$$

though one must take care to note that WolframAlpha's precision may not be able to handle so many digits and a lot of cancellation occurs. If they are accurate though, then this will approximate the limit to the shown places.

From the shown convergence rates, we can be expect $s_4,s_5,$ and $s_6$ to be within roughly

$4:~{}^2(s_4)\log_{10}(s_4)\simeq4.7$

$5:~{}^3(s_5)\log_{10}(s_5)\simeq19727$

$6:~{}^4(s_6)\log_{10}(s_6)\simeq10^{19727}$

digits accurate of the limit respectively.

$\endgroup$
4
  • $\begingroup$ This is very clever! I will have to read through it more carefully before I accept. $\endgroup$ – Dark Malthorp Mar 11 '20 at 17:12
  • $\begingroup$ It's unclear to me how you used linear approximation to get the first equation you have relating $s_{n+1}$ to $s_n$. $\endgroup$ – Dark Malthorp Mar 12 '20 at 14:40
  • 1
    $\begingroup$ If you solve for $f_ng_n'$ you will get:$$f_n(s_n)g_n'(s_n^\star)=\frac{f_n(s_{n+1})-f_n(s_n)}{s_{n+1}-s_n}$$which should make sense since $g'=f'/f$. You can prove it more rigorously with an application of the mean value theorem, though for our purposes here, we have $|s_{n+1}-s_n|\to0$ fast enough that you may as well think of it as $g_n'(s_n^\star)=g_n'(s_n)=f_n'(s_n)/f_n(s_n)$. $\endgroup$ – Simply Beautiful Art Mar 12 '20 at 15:15
  • $\begingroup$ OK I see. That rearrangement makes it quite clear. $\endgroup$ – Dark Malthorp Mar 12 '20 at 15:23

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.