The inverse Ackermann function is defined over the natural numbers as follows: ($[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) $$\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\}$$ The question is what is $\beta(n)=\min\{k:\alpha_k(n)\leq \alpha(n)\}$? In particular, is $\beta(n)\ll \log\alpha(n)$?
2
-
2$\begingroup$ It is worth mentioning you are (probably) getting this from gabrielnivasch.org/fun/inverse-ackermann $\endgroup$– David Roberts ♦Mar 21, 2015 at 23:10
-
$\begingroup$ Also posted here: cstheory.stackexchange.com/questions/30888/… $\endgroup$– Christian RemlingMar 21, 2015 at 23:15
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Sorry, only noticed your question right now.
The function $\beta$ you define satisfies $\alpha(n)-2\le \beta(n) \le \alpha(n)$, since $\alpha_{\alpha(n)-3}(n)$ grows much faster than $\alpha(n)$ (though obviously slower than $\alpha_k(n)$ for any fixed $k$). Indeed, $\alpha_{\alpha(n)-3}(n) > A(\alpha(n)-2)$ where $A$ is the Ackermann function.
The five-line proof of this latter inequality is given on page 3 of my PhD thesis, and on page 11 of the arXiv version of my paper with Bukh and Matoušek "Lower bounds for weak epsilon-nets and stair-convexity" (Israel J. Math. 182:199-228, 2011). (In these two references you can also find an application of the fact that $\alpha_{\alpha(n)-3}(n)\to\infty$.)
