# Fun with inverse Ackermann

The inverse Ackermann function occurs often when analyzing algorithms. A great presentation of it is here: http://www.gabrielnivasch.org/fun/inverse-ackermann. $$\alpha_1(n) = [n/2]$$ $$\alpha_2(n) = [\log_2 n]$$ $$\alpha_3(n) = \log^* n$$ $$...$$ $$\alpha_k(n) = 1 + \alpha_k(\alpha_{k−1}(n))$$ and $$\alpha(n) = \min\{k: \alpha_k(n)\leq 3\}$$ [Notation: [x] means that we round up x to the nearest integer, while log∗ is the iterated log function discussed here: http://en.wikipedia.org/wiki/Iterated_logarithm ]

My question is: What is the function $$k(n) = \min \{k: \alpha_k(n) \leq k\}$$ Clearly $1\ll k(n) \leq \alpha(n)$. What tighter bounds can one give on $k(n)$? Is $k(n) \leq \log\alpha(n)$?

• I know why $k(n) \leq \alpha(n)$, but could you explain why is $k(n) \ll \alpha(n)$? – jbapple Mar 21 '15 at 21:31
• Ok, edited to the uncontroversial $k(n)<\alpha(n)$. – Dana Moshkovitz Mar 21 '15 at 21:37
• @DanaMoshkovitz: I approximated the definitions using the Ackermann hierarchy I'm familiar with: $\alpha(n)=\min\{k: A_k(1)\geq n\}$ and $k(n)=\min\{k:A_k(k)\geq n\}$. With a typical definition of the Ackermann functions, $A_{k+1}(1)=A_k(A_k(1))\geq A_k(k)$. Hence if $A_k(k)\geq n$ then $A_{k+1}(1)\geq n$, i.e., $k(n)\geq\alpha(n)-1$. (I hope I haven't made a mistake in there.) – Sylvain Mar 21 '15 at 23:13
• @DanaMoshkovitz: to clarify, I'm using $A_1(n)=2n$ and $A_{k+1}(n)=A_k^{n+1}(1)$, which grows slightly faster than your definition, e.g., $A_2(n)=2^{n+1}$ instead of $2^n$. It shouldn't have much of a consequence though: $\alpha(n)$ and $k(n)$ are pretty much the same thing. – Sylvain Mar 21 '15 at 23:29
• @DanaMoshkovitz: I don't see why $k(n)<\alpha(n)$. For infinitely many values of $n$ you will have $\alpha(n)=k(n)$, i.e. whenever $A_k(k)<n\leq A_{k+1}(1)<A_{k+1}(k+1)$; because $A_{k+1}(1)-A_k(k)$ grows fast, you have longer and longer such sequences. With your definitions it's even possible to have $\alpha(n)<k(n)$: $\alpha_2(8)=3>2$ hence $\alpha(8)=2$ but $k(8)=3$. – Sylvain Mar 22 '15 at 8:44

Let $A_k$ be the inverse of $\alpha_k$. $A_1(x) = 2x, A_2(x) = 2^x, \dots$. I claim that $k^{-1}(x) = A_x(x)$.

Since $x = \alpha_x(A_x(x))$, and since $\forall z, \alpha_y(z) > \alpha_x(z)$, $\alpha_y(A_x(x)) > \alpha_x(A_x(x)) = x$. As a result $k(A_x(x)) = x$.

Now consider the value of $\alpha(k^{-1}(n)) = \alpha(A_n(n))$. By definition of $\alpha$, this is $\min_z \{\alpha_z(A_n(n)) \leq 3\}$. We know that $\alpha_n(A_n(n)) = n$, so $\alpha(A_n(n)) > n$. I claim that $\alpha(A_n(n)) \leq n+2$. $\alpha_{n+1}(A_n(n)) = 1+\alpha_{n+1}(n)$. Now $\alpha(n) = \min_z\{\alpha_z(n) \leq 3\}$, so $\alpha_{\alpha(n)}(n) \leq 3$. Since $n+1 > \alpha(n)$, $\alpha_{n+1}(n) \leq 3$, so $\alpha_{n+1}(A_n(n)) \leq 4$. Thus, $\alpha_{n+2}(A_n(n)) = 1 + \alpha_{n+2}(\alpha_{n+1}(n)) \leq 1 + \alpha_{n+2}(4) \leq 3$.

So, we have $n < \alpha(k^{-1}(n)) \leq n+2$, so $k$ and $\alpha$ are essentially equal.

• And let me add that all these functions are just different complicated ways of writing the number 4. – Sariel Har-Peled Mar 23 '15 at 4:32

This is incorrect; see the comments.

A function very close to this one was called "$\alpha^*$" and used in Pettie's "Splay Trees, Davenport-Schinzel Sequences, and the Deque Conjecture", in which he showed that "$n$ deque operations [in a splay tree] take only $O(n\alpha^*(n))$ time, where $\alpha^*(n)$ is the minimum number of applications of the inverse-Ackermann function mapping $n$ to a constant."

This function is very slow growing, and is slower growing than $\log \alpha(n)$. Consider the function $f:\mathbb{N} \to \mathbb{N}$

$$f(n) = \cases{1 & n = 0\\2^{f(n-1)} & n > 0}$$

This function is roughly as fast growing as $A(4,n)$, so is more slowly growing than $A'(n) = A(n,n)$. Now I'll evaluate $\log \alpha(n)$ and $\alpha^*(n)$ on $A'(f(n))$:

$$\log \alpha(A'(f(n))) = \log f(n) = f(n-1)$$

$$\alpha^*(A'(f(n))) = 1 + \alpha^*(f(n)) < 1 + \alpha^*(A'(n)) < 2 + \alpha^*(n)$$

Since $f(n-1) \in \omega(2+\alpha^*(n))$, $\log \alpha(n)$ is much faster growing than $\alpha^*(n)$.

• What is the relation between alpha^* and k(n)? (note that in the definition of k(n) I use the notation alpha_k(n) defined in the link I had in the question) – Dana Moshkovitz Mar 21 '15 at 21:14
• Oh, I'm sorry, I read your $\alpha_k$ as $\alpha^k$! – jbapple Mar 21 '15 at 21:29