Let $\star$ be any operation in the sequence of hyperoperations $(\text{Succ},+,\times,\uparrow,\uparrow\uparrow,\ldots)$, and consider the $\star$-factorial function defined as follows on the positive integers:

$$\begin{align}f_\star(n) &:= n\star(n-1)\star(n-2)\ldots \star 1\quad (n\text{ operands}) \end{align}$$

where a right-to-left order of evaluation is assumed; e.g. $f_\uparrow(3) = 3\uparrow 2\uparrow 1 = 3\uparrow (2\uparrow 1)$.

(With appropriate treatment for an argument of $n=0$, the definition could be extended to the nonnegative integers, but it would not be useful to do so in the present context.)

For each $\star$ operation, we want to compare the growth-rate of $f_\star$ to the following function $g_\star$: $$\begin{align}g_\star(n) &:= b\star' n\\ &= b\star b\star b\ldots \star b\quad (n+1\text{ operands})\quad\text{ if }\star =\text{Succ}\\ &= b\star b\star b\ldots \star b\quad (n\text{ operands})\quad\text{ if }\star \in(+,\times,\uparrow,\uparrow\uparrow,\ldots) \end{align}$$ where $\star'$ is the hyperoperation just after $\star$, and $b\ge 2$ is some given fixed integer. We use the concept of eventual domination; i.e., for two functions $f,g$ on the positive integers, the notation $f<^*g$ (resp. $f>^*g$) means that $f(n)<g(n)$ (resp. $f(n)>g(n)$) for all sufficiently large $n$.

Examples

$$\begin{align} f_\text{Succ}(n)&=n & \color{blue}{<^*} \ \ g_\text{Succ}(n)=b+n\quad\quad\quad\quad\text{ if }b\ge 2\\ f_+(n)&=\frac{n(n+1)}{2} & \color{red}{>^*} \ \ g_+(n)=b\times n\quad\quad\quad\quad\text{ if }b\ge 2\\ f_\times(n)&=n! & \color{red}{>^*} \ \ g_\times(n)=b\uparrow n\quad\quad\quad\quad\text{ if }b\ge 2\\ f_\uparrow(n)&=n^{(n - 1)^{(n - 2)^{\cdots^1}}} & \color{blue}{<^*} \ \ g_\uparrow(n)=b\uparrow\uparrow n\quad\quad\quad\quad\text{ if }b\ge 3 \end{align}$$

The first two examples above are easily worked out, while the third example is a well-known result for the standard factorial function. The fourth example follows from properties of the exponential factorial function proved by @Deedlit. (Note that in the fourth example, domination would occur in the reverse order if $b=2$; i.e., $f_\uparrow(n) \color{red}{>^*} 2\uparrow\uparrow n$.)

Question 1: Is it the case that if $b=3$ then $f_\star \color{blue}{<^*} g_\star$ for all $\star\in(\uparrow,\uparrow\uparrow,\ldots)$? I.e., in terms of Knuth's uparrows, do we have $f_{\uparrow^k}(.)\color{blue}{<^*}3\uparrow^{k+1}(.)$ for all $k\ge 1$?

Question 2: If Question 1 has a negative answer, then is it the case that for each $\star\in(\uparrow,\uparrow\uparrow,\ldots)$ there exists a $b$ (depending on $\star$) such that $f_\star \color{blue}{<^*} g_\star$? I.e., is there, for each $k\ge 1$, a $b_k$ such that $f_{\uparrow^k}(.)\color{blue}{<^*}b_k\uparrow^{k+1}(.)$?

  • You could just use \ll and \gg for $\ll$ and $\gg$. – Simply Beautiful Art Mar 8 '17 at 23:07
  • Base case: Assume that $f_\star(1)<g_\star(2)$. Inductive step: $$f_\star(n+1)=(n+1)\star f_\star(n)<(n+1)\star g_\star(n)<(n+1)\star g_\star(n+1)<g_\star(n+2)$$ So this proof shows that $f_\star(n)\ll g_\star(n+1)$, though it's not as immediate for the actual question... – Simply Beautiful Art Mar 8 '17 at 23:08
  • Taking a guess, I'd bet that for question 1, the answer is yes. – Simply Beautiful Art Mar 8 '17 at 23:17
up vote 3 down vote accepted
+50

For convenience, we will let $a \uparrow^b 0 = 1$ and $a\uparrow^0 b = ab$.

As in the proof for the exponential case, we can prove that $3 \uparrow^{k+1} (n-2) < f_{\uparrow^k}(n) < 3 \uparrow^{k+1} (n-1)$ for $n \ge 2$. The left inequality is trivial, so we will prove the right hand side.

First, we need a lemma:

Lemma. $(n+1) \uparrow^k m > n\uparrow^k m + n$ for $n, k \ge 1, m\ge 2$.

Case $k = 1$: $(n+1)^m > n^m + m\cdot n^{m-1} > n^m +n$.

Inductive step:

$$(n+1)\uparrow^k m = (n+1) \uparrow^{k-1} [(n+1)\uparrow^k (m-1)] > (n+1)\uparrow^{k-1}(n \uparrow^k (m-1)) $$ $$> n \uparrow^{k-1}(n \uparrow^k (m-1)) + n \text{ (by inductive hypothesis)} = n \uparrow^k m + n$$

Now for the main proof:

Statement. $(n+2) \uparrow^k f_{\uparrow^k}(n) \le 3 \uparrow^{k+1} n$ for $n \ge 1$.

Base case: $3 \uparrow^k f_{\uparrow^k}(1) = 3 \uparrow^k 1 = 3 = 3\uparrow^{k+1} 1$.

Inductive step: $$ 3 \uparrow^{k+1} (n+1) = 3\uparrow^k (3\uparrow^{k+1} n)$$ $$ \ge 3\uparrow^k ((n+2) \uparrow^k f_{\uparrow^k}(n)) > 3 \uparrow^k ((n+1)\uparrow^k f_{\uparrow^k}(n) + n+1) \text{(by the lemma)} > (3\uparrow^k (n+1)) \uparrow^k [(n+1)\uparrow^k f_{\uparrow^k}(n)]$$ (by the Knuth Arrow theorem) $$> (n+3) \uparrow^k ((n+1) \uparrow^k f_{\uparrow^k}(n)) = (n+3) \uparrow^k f_{\uparrow^k}(n+1).$$

This proves the statement. But then,

$$3 \uparrow^{k+1}(n-1) \ge (n+1) \uparrow^k f_{\uparrow^k}(n-1) > n \uparrow^k f_{\uparrow^k}(n-1) = f_{\uparrow^k}(n).$$

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.