From 8d579d8ac1250a3c4de77dc3da652c9eff947f6e Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Sat, 19 Apr 2008 14:34:18 +0200 Subject: [PATCH] Cleaned up ackermannian notation. --- notation.tex | 31 +++++++++++++++++-------------- 1 file changed, 17 insertions(+), 14 deletions(-) diff --git a/notation.tex b/notation.tex index 8693a5d..5e46fe3 100644 --- a/notation.tex +++ b/notation.tex @@ -89,8 +89,8 @@ \n{$D(m,n)$}{Decision tree complexity of MSF \[decdef]} \n{$A(x,y)$}{The Ackermann's function \[ackerdef]} \n{$A(x)$}{The diagonal Ackermann's function \[ackerdef]} -\n{$a(x,n)$}{The inverse of the $x$-th row of the Ackermann's function \[ackerinv]} -\n{$a(n)$}{The diagonal inverse of the Ackermann's function \[ackerinv]} +\n{$\lambda_i(n)$}{The inverse of the $i$-th row of the Ackermann's function \[ackerinv]} +\n{$\alpha(n)$}{The diagonal inverse of the Ackermann's function \[ackerinv]} \n{$\alpha(m,n)$}{$\alpha(m,n) := \min\{ x\ge 1 \mid A(x,4\lceil m/n\rceil) > \log n \}$ \[ackerinv]} } @@ -163,7 +163,10 @@ related to the topic of our study. Various sources differ in the exact definition of both the Ackermann's function and its inverse, but most of the differences are in factors that -are negligible in the light of the giant asymptotic growth of the function. +are negligible in the light of the giant asymptotic growth of the function.\foot{% +To quote Pettie \cite{pettie:onlineverify}: ``In the field of algorithms \& complexity, +Ackermann's function is rarely defined the same way twice. We would not presume to buck +such a~well-established precedent. Here is a~slight variant.''} We will use the definition by double recursion given by Tarjan \cite{tarjan:setunion}, which is predominant in the literature on graph algorithms: @@ -196,22 +199,22 @@ A(4,3) &= A(3,A(4,2)) = A(3,4) = A(2,A(3,3)) = A(2,A(2,A(3,2))) = \cr Three functions related to the inverse of the function~$A$ are usually considered: \defn\id{ackerinv}% -The \df{row inverse} $a(x,y)$ of the Ackermann's function is defined by: +The \df{$i$-th row inverse} $\lambda_i(n)$ of the Ackermann's function is defined by: $$ -a(x,n) := \min\{ y \mid A(x,y) > \log n \}. +\lambda_i(n) := \min\{ y \mid A(i,y) > \log n \}. $$ -The \df{diagonal inverse} $a(n)$ is defined by: +The \df{diagonal inverse} $\alpha(n)$ is defined by: $$ -a(n) := \min\{ x \mid A(x) > \log n \}. +\alpha(n) := \min\{ x \mid A(x) > \log n \}. $$ -The \df{alpha function} $\alpha(m,n)$ is defined for $m\ge n$ by: +The two-parameter \df{alpha function} $\alpha(m,n)$ is defined for $m\ge n$ by: $$ \alpha(m,n) := \min\{ x\ge 1 \mid A(x,4\lceil m/n\rceil) > \log n \}. $$ \example -$a(1,n) = \O(\log\log n)$, $a(2,n) = \O(\log^* n)$, $a(3,n)$ grows even slower -and $a(n)$ is asymptotically smaller than $a(x,n)$ for any fixed~$x$. +$\lambda_1(n) = \O(\log\log n)$, $\lambda_2(n) = \O(\log^* n)$, $\lambda_3(n)$ grows even slower +and $\alpha(n)$ is asymptotically smaller than $\lambda_i(n)$ for any fixed~$i$. \obs It is easy to verify that all the rows are strictly increasing and so are all @@ -220,7 +223,7 @@ $\alpha(m,n)$ is maximized at $m=n$. So $\alpha(m,n) \le 3$ when $\log n < A(3,4 which covers all values of~$m$ that are likely to occur in practice. \lemma -$\alpha(m,n) \le a(n)+1$. +$\alpha(m,n) \le \alpha(n)+1$. \proof $A(x,4\lceil m/n\rceil) \ge A(x,4) = A(x-1,A(x,3)) \ge A(x-1,x-1)$, so $A(x,4\lceil m/n\rceil)$ @@ -228,11 +231,11 @@ rises above $\log n$ no later than $A(x-1,x-1)$ does. \qed \lemma\id{alphaconst}% -When $k$~is a~fixed constant and $m\ge n\cdot a(k,n)$, then $\alpha(m,n) \le k$. +When $i$~is a~fixed constant and $m\ge n\cdot \lambda_i(n)$, then $\alpha(m,n) \le i$. \proof -The choice of~$m$ guarantees that $A(x,4\lceil m/n\rceil) \ge A(x,a(k,n))$, which -is greater than $\log n$ for all $x \ge k$. +The choice of~$m$ guarantees that $A(x,4\lceil m/n\rceil) \ge A(x,\lambda_i(n))$, which +is greater than $\log n$ for all $x \ge i$. \qed \endpart -- 2.39.5