The [Ackermann function](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/Primitive_recursive_function).


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}



Are the vertical sections of the Ackermann function primitive recursive?
No, already $A(n,3)$ is not primitive recursive. Let me use the essentially equivalent [up-arrow notation](https://en.wikipedia.org/wiki/Knuth%27s_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$.


