Not a dupe of this question, as I'm searching for tighter bounds.


We define the fast growing hierarchy for finite values as follows:

$$f_k(n)=\begin{cases}n+1,&k=0\\f_{k-1}^n(n),&k>0\end{cases}$$

where

$$f_k^a(n)=\underbrace{f_k(\dots f_k(}_an)\dots)$$

For example,

$$f_2(2)=f_1(f_1(2))=f_1(f_0(f_0(2)))=f_1(f_0(3))=f_1(4)\\=f_0(f_0(f_0(f_0(4))))=8$$

For $k=0,1,2$, we have known closed forms:

$$f_0(n)=n+1\\f_1(n)=2n\\f_2(n)=2^nn$$

And for $k=3$, I've derived tight bounds:

$$((2^n)\uparrow\uparrow n)n\le f_3(n)\le(2^nn)\uparrow\uparrow n$$

These bounds were obtained from the more general case:

$$((2^n)\uparrow\uparrow k)n\le f_2^k(n)\le(2^nn)\uparrow\uparrow k$$

Which can be seen by induction. Note that:

$$f_2(((2^n)\uparrow\uparrow k)n)>2^{((2^n)\uparrow\uparrow k)n}n=((2^n)\uparrow\uparrow(k+1))n$$

Likewise, induction is doable on the upper bound.

We also have known lower bounds (trivial ones)

$$2\uparrow^{k-1}n\le f_k(n)$$

And the slightly less trivial upper bound (though it is far from a tight bound I'd imagine)

$$f_k(n)\le2\uparrow^{k-1}(2n)$$


Note that I have used Knuth's up-arrow notation, which is the natural extension past exponentiation. It more or less goes as follows:

$$a\times b=\underbrace{a+\dots+a}_b\\a^b=a\uparrow b=\underbrace{a\times\dots\times a}_b\\a\uparrow\uparrow b=a\uparrow^2b=\underbrace{a\uparrow\dots\uparrow a}_b\\a\uparrow^3b=\underbrace{a\uparrow^2\dots\uparrow^2a}_b\\\vdots$$

Where the operation is expanded right to left:

$$3\uparrow3\uparrow3=3\uparrow(3\uparrow3)=3\uparrow27=7625597484987$$

$$3\uparrow3\uparrow3\ne(3\uparrow3)\uparrow3=27\uparrow3=19683$$


Using Knuth's up-arrow notation, is it possible to obtain even tighter bounds on $f_3(n)$? What about $f_k(n)$ for $k>3$?

  • Here you are again with the big numbers! :D – Frpzzd Jul 6 '17 at 22:10
  • Not that big by my standards :D – Simply Beautiful Art Jul 6 '17 at 22:13
  • Well. By other people's standards... out of curiosity, did you create the "big numbers" tag? – Frpzzd Jul 6 '17 at 22:18
  • 3
    @SimplyBeautifulArt you've simply tripled the number of posts in it. I can see you earning a Gold badge in "big-numbers" before I die. The beautiful thing about this post is that everything grows slow enough I can actually understand everything XD – Brevan Ellefsen Jul 6 '17 at 22:26
  • 1
    Perhaps you should create the tag (small-numbers (by SBA's standards)) ? – Donald Splutterwit Jul 6 '17 at 23:10
up vote 3 down vote accepted
+50

Your bounds are quite good given their simplicity. To get stronger bounds, we can use a lower tetration exponent - for example,

$$f_2^k(n) \ge \left(2^{2^n n} \uparrow\uparrow (k-1)\right)(2^n n)$$

One can verify it for $k = 1,2$, and then observe the inductive step

$$f_2^{k+1}(n) \ge f_2 \left( \left(2^{2^n n} \uparrow\uparrow (k-1)\right)(2^n n) \right) = 2^{\left(2^{2^n n} \uparrow\uparrow (k-1)\right)(2^n n)} \left(2^{2^n n} \uparrow\uparrow (k-1)\right)(2^n n) > \left( 2^{2^n n}\right)^{\left(2^{2^n n} \uparrow\uparrow (k-1)\right)} (2^n n) = \left(2^{2^n n} \uparrow\uparrow k\right)(2^n n)$$

To see that this is a tighter bound, note that $2^{2^n n} = 2^n \uparrow\uparrow 2$, and by induction $$(2^{2^n n}) \uparrow\uparrow k = (2^{2^n n})^{(2^{2^n n} \uparrow\uparrow (k-1))} > (2^n)^{2^n \uparrow\uparrow k} = 2^n \uparrow\uparrow (k+1)$$

For an upper bound, we can use

$$f_2^k(n) \le (2^{2^n n + n}n) \uparrow\uparrow (k-1) \qquad \text{ for } k \ge 2$$

We have equality at $k=2$, and

$$f_2^{k+1}(n) \le f_2((2^{2^n n + n}n) \uparrow\uparrow (k-1) ) = 2^{(2^{2^n n + n}n) \uparrow\uparrow (k-1) }((2^{2^n n + n}n) \uparrow\uparrow (k-1) ) < 2^{2((2^{2^n n + n}n) \uparrow\uparrow (k-1) )} < (2^{2^n n + n}n)^{(2^{2^n n + n}n) \uparrow\uparrow (k-1) } = (2^{2^n n + n}n) \uparrow\uparrow k$$

To see that this is a tighter bound, set $m = 2^n n$. We must show that $2^m m \uparrow \uparrow (k-1) < m\uparrow\uparrow k$; to do this, we will prove that $(2^m m \uparrow\uparrow (k-1))m < m\uparrow\uparrow k$.

Observe that for $k=2$ we have $(2^m m)m < m^m$. ($m > 4$, so $m^m = m^2 m^{m-2} > m^2 2^{2m-4} > m^2 2^m$.) Then for the inductive step, $$m\uparrow\uparrow(k+1) = m^{m\uparrow\uparrow k} > m^{(2^m m \uparrow\uparrow (k-1))m} = (m^m)^{2^m m \uparrow\uparrow (k-1)} > (2^m m^2)^{2^m m \uparrow\uparrow (k-1)} >(2^m m)^{2^m m \uparrow\uparrow (k-1)}m = (2^m m \uparrow\uparrow k)m $$

For higher levels of the fast-growing hierarchy, observe that

$f_k(n) > n \uparrow^{k-1} n$ for $k \ge 3, n \ge 2$

Hence if $f_{k+1}(n) \ge X$, then $f_{k+1}^m(n) \ge X \uparrow^k m$ by induction.

In particular, since we have $f_3(n) \ge (2^n \uparrow\uparrow n)n$, we then have

$$f_4(n) \ge ((2^n \uparrow^2 n)n) \uparrow^3 n$$

$$f_5(n) \ge (((2^n \uparrow^2 n)n) \uparrow^3 n) \uparrow^4 n$$

$$f_6(n) \ge ((((2^n \uparrow^2 n)n) \uparrow^3 n) \uparrow^4 n) \uparrow^5 n$$

and so on. To keep the length of the bound from growing too large, we can replace an inner expression with a simpler bound like $f_k(n) \ge n \uparrow^{k-1} (n+1)$. So for example

$$f_k(n) \ge ((n \uparrow^{k-3} (n+1))\uparrow^{k-2} n) \uparrow^{k-1} n$$ for $k \ge 6$

Upper bounds are more troublesome. It seems clear that if we replace $(2^n \uparrow^2 n)n$ with $2^n n \uparrow^2 n$ across the board we will get upper bounds, but I imagine the proof for this will be rather intricate.

  • About time you answered :P Appears my suspicions were right about the lower bounds on $f_k(n)$. I suppose if you wanted it to look cooler, you could've done $$f_4(n)\ge(n\uparrow^0((2\uparrow^1n)\uparrow^2n))\uparrow^3n$$ Anyways, nice job as always. – Simply Beautiful Art Jul 15 '17 at 11:02
  • I recently managed to prove the weak-ish upper bounds of $$f_k(n)\le2\uparrow^{k-1}2\uparrow^{k-1}n$$but can't do much better. – Simply Beautiful Art Jul 20 at 13:34

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.