2
$\begingroup$

Let $$f(n)\ :=\ n \uparrow^n n$$

and $$g(n)\ :=f(f(n))\ =\ f(n)\uparrow ^{f(n)} f(n)=n\uparrow^n n \uparrow^ {n \uparrow ^n n} n\uparrow ^n n$$

So, $g(n)$ is $f(n)$ applied twice.

  • What is the growth rate of $g(n)$ ?
  • How can I estimate $g(n)$ (I search an upper and a lower bound in terms of conway-chain-notation and entries not much larger than n) ?

    $f(n)$ is simply $n\rightarrow n \rightarrow n$ and $g(n)$ should be upperbounded by a conway chain with $4$ moderate entries and perhaps even a chain with $3$ moderate entries. But it is very difficult to compare the values of conway chains in general.

    I tried to manipulate $(n \rightarrow n\rightarrow n)\rightarrow (n\rightarrow n\rightarrow n)\rightarrow (n\rightarrow n\rightarrow n)$, but the first entry is very large, and I do not know how to compare this with a chain with a moderate first entry.

$\endgroup$
2
$\begingroup$

A simple upper bound which is easy to prove (for $n>2$) would be: $$U=(n→2→3→2)$$

Using the definition of Conway arrow notation, we get: $$U = n↑^{{n↑^{n↑2}}2}2 = n↑^{{n↑^{(n↑2-1)}}n}2= n↑^{{n↑^{(n↑2-1)}}n-1}n$$

Since ${{n↑^{(n↑2-1)}}n-1}$ is clearly bigger than $n↑^{n}n$, we get that $U>g(n)$.

But we can tighten the bound even further.

Let us pick some $k$, such that $k^2-3>n$. I propose that the number $$V=(k→2→3→2)$$ is larger than $g(n)$.

Proving it formally is tricky, but I can show you why this has to be so. We calculate $V$:

$$V = k↑^{{k↑^{k↑2}}2}k = k↑^{{k↑^{(k↑2-1)}}k}k > k↑^{{k↑^{(n+2)}}k}k$$.

With numbers of such magnitudes, the first and final $k$ are irrelevant (as long as k>2). Only the number of arrows matters, when comparing thw two numbers. The number of arrows in $V$ is:

$${k↑^{(n+2)}}k$$

While the number of arrows in $g(n)$ is:

$${n↑^{n}}n$$

Using the same argument again, we find the number of arrows in "the number of arrows of $V$" is $n+2$ while we the number of arrows in "the number of arrows of $g(x)$" is $n$. And since $n+2>n$ we get that $V>g(x)$

In conclusion, a reasonable upper bound for $g(n)$ is:

$$V(n)=(1+[\sqrt{n+3}])→2→3→2$$

For example:

$$g(10)<(4→2→3→2)$$ $$g(100)<(11→2→3→2)$$

BTW, while the above anlysis works only for $n>2$, the inequality $V(n)>g(n)$ happens to hold for $n=2$ as well:

$$V(2)=3→2→3→2 = 3↑^{3↑^{8}2}2 > 4↑↑↑↑4 = g(2)$$

$\endgroup$

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.