Tighter bounds on the fast growing hierarchy?

319 Views Asked by At

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$?

1

There are 1 best solutions below

2
On BEST ANSWER

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.