# Are the vertical sections of the Ackermann function primitive recursive?

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

• No, already $A^3$ is not PR. Dec 12, 2020 at 11:01
• Great! But can you post a proof? But also, in that case, why do we talk about the diagonal, rather than just $A^3$? Dec 12, 2020 at 11:02
• And do you mean $A^3$ for my preferred version, or for the Ackermann–Péter function? Dec 12, 2020 at 11:03
• I will try to write up the proof. I suppose we use the diagonal simply because it is easier to see it is not PR. And I mean your version, in the Ackermann-Peter version already $A^1$ would be not PR. Dec 12, 2020 at 11:03
• We have $A^2(m+1) = A(m+1,2) = A(m,A(m+1,1))$, and $A(m+1,1)\geq m$ is pretty obvious, as is the fact that $A_m$ is increasing, so $A^2(m+1) \geq A(m,m)$, and since $m\mapsto A(m,m)$ outgrows every PR function, so does $A^2$. Did I get something wrong? Dec 12, 2020 at 11:22

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

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