Are the vertical sections of the Ackermann function primitive recursive?

Question

The Ackermann function $A(m,n)$ is a binary function on the natural numbers defined by a certain double recursion, famous for exhibiting extremely fast-growing behavior.

One finds various slightly different formulations of the Ackermann function, with slightly different initial conditions. I prefer the following version:

\begin{eqnarray*} A(0,n) &=& n+1 \\ A(m,0) &=& 1, \quad\text{ except for }A(1,0)=2\text{ and }A(2,0)=0\\ A(m+1,n+1) &=& A\bigl(m,A(m+1,n)\bigr). \end{eqnarray*}

I like this version because it has the nice properties that

\begin{eqnarray*} A(0,n) &=& n+1\\ A(1,n) &=& n+2\\ A(2,n) &=& 2n\\ A(3,n) &=& 2^n\\ A(4,n) &=& 2^{2^{\cdot^{\cdot^2}}}{}^{\bigr\}n}\\ \end{eqnarray*}

In this way, the levels of the Ackermann function exhibit increasingly fast-growing behavior.

Each horizontal level of the Ackermann function, the function $A_m(n)=A(m,n)$ considered as a unary function with $m$ fixed, is defined by recursion using the previous level, and consequently all these functions are primitive recursive.

Furthermore, these functions are unbounded in the primitive recursive functions in the sense that every primitive recursive function is eventually bounded by some horizontal level $A_m$ of the Ackermann function. It follows from this that the diagonal of the Ackermann function $n\mapsto A(n,n)$ is not primitive recursive.

My question is about the sections of the Ackermann function taken on the other coordinate, the vertical sections of the Ackerman function, the functions $A^n(m)=A(m,n)$, for fixed $n$.

Question. Are the vertical sections of the Ackermann function $A^n$ each primitive recursive?

I don't expect the answer to depend on which particular version of the Ackermann function one uses, but just in case, let me mention another standard version, which has a smoother definition, which works better in many of the inductive arguments, even though the level functions are not as nice.

\begin{array}{lcl}\operatorname {A} (0,n)&=&n+1\\\operatorname {A} (m+1,0)&=&\operatorname {A} (m,1)\\\operatorname {A} (m+1,n+1)&=&\operatorname {A} (m,\operatorname {A} (m+1,n))\end{array}

Answer 1

No, already $A(n,3)$ is not primitive recursive. Let me use the essentially equivalent up-arrow notation: $A(n,m)=2\uparrow^{n-1}m$, and argue why $f(n)=2\uparrow^n 3$ is not PR. I claim $f(2n-2)\geq 2\uparrow^{n+1}n=A(n,n)$. $n\mapsto A(n,n)$ outgrows all $n\mapsto A(m,n)$, so by a classical argument it eventually outgrows all PR functions, and hence so will $f$ after we justify the claim.

It is enough to show that for $m\geq 3$ we have $2\uparrow^n m\geq 2\uparrow^{n-1}(m+1)$. We show this by induction on $m$. Indeed, $2\uparrow^n m=2\uparrow^{n-1}(2\uparrow^n(m-1))$, so it is enough to show $2\uparrow^n(m-1)\geq m+1$. This holds true for $m=3$ as $2\uparrow^n 2=4$ for all $n$, and for larger $m$ we have $2\uparrow^n(m-1)=2\uparrow^{n-1}(2\uparrow^n(m-2))\geq 2\uparrow^{n-1}m\geq m+1$.

Let me note that the bound $f(2n-2)\geq 2\uparrow^{n+1}n$ is far from optimal, in fact it should hold for $f(n+2)$, at least for large enough $n$.

Answer 2

If you don't mind not getting the best possible result, then the proof is very short. Indeed,

$$A(n,4)=A(n-1,A(n,3))$$

so if you can prove that $A(n,3)\geq n-1$ then $A(n,4)\geq A(n-1,n-1)$, which we know doesn't grow primitive-recursively. But $A(n,3)$ grows much more quickly than $n-1$.