Gabriel Nivasch - Inverse Ackermann (original) (raw)

We have α2(n) = [log2 _n_], and α3(n) is the iterated logarithm function, denoted log* n.

Claim 1: If n ≥ 4 then α_k_(n) ≤ n − 2.

Proof: By induction on k. The case k = 1 is clear. So assume k ≥ 2.

If n = 4, then α_k_(n) = 2; and if n = 5 or 6, then α_k_(n) = 3. So let n ≥ 7. Then, by induction on k and n,

α_k_(n) = 1 + α_k_(α_k_−1(n)) ≤ 1 + α_k_(n − 2) ≤ 1 + n − 4 < n − 2. QED

Claim 2: We have α_k_+1(n) ≤ α_k_(n) for all k and n. Moreover, for k ≥ 2 the inequality is strict if and only if α_k_(n) ≥ 4.

Proof: The claim is easily established for α_k_(n) ≤ 3, so suppose α_k_(n) ≥ 4. By Claim 1,

α_k_+1(n) = 1 + α_k_+1(α_k_(n)) ≤ 1 + α_k_(n) − 2 < α_k_(n). QED

Corollary 3: We have α_k_(n) = o(n) for all k ≥ 2.

Proof: By Claim 2, since α2(n) = Θ(log n) = o(n). QED

**Claim 4:**We have α_k_+1(n) = o(α_k_(n)) for all k ≥ 1.

Proof: By Corollary 3 we have

α_k_+1(n) = 1 + α_k_+1(α_k_(n)) = 1 + o(α_k_(n)). QED

In fact, Claim 4 can be strengthened. Given an integer r ≥ 1, let f(r) denote the _r_-th-fold composition of the function f. Then,

Claim 5: α_k_+1(n) = o(α_k_(r)(n)) for all fixed k and r.

Proof: Iterating r times the definition of α_k_+1(n), and applying Corollary 3,

α_k_+1(n) = r + α_k_+1(α_k_(r)(n)) = r + o(α_k_(r)(n)). QED

Thus, we have log* n = o(log log log n), α4(n) = o(log* log* log* log* n), etc.

The inverse Ackermann function

By Claim 2, for every fixed n ≥ 5, the sequence

α1(n), α2(n), α3(n), ...

decreases strictly until it settles at 3. For example, for n = 9876! we obtain the sequence

3.06×1035163, 116812, 6, 4, 3, 3, 3, ...

The inverse Ackermann function α(n) assigns to each integer n the smallest k for which α_k_(n) ≤ 3:

α(n) = min { k : α_k_(n) ≤ 3 }.

Thus, α(9876!) = 5.

Claim 6: We have α(n) = o(α_k_(n)) for every fixed k.

Proof: Let m = α_k_+1(n). Then the (m − 2)-nd term of the sequence

α_k_+1(n), α_k_+2(n), α_k_+3(n), ...,

namely α_k_+_m_−2(n), already equals 3. Thus,

α(n) ≤ k + m − 2 = k − 2 + α_k_+1(n) = o(α_k_(n)). QED

The two-parameter version of the inverse Ackermann function

There is also a two-parameter version of the inverse Ackermann function that sometimes comes up (for example, in the running time of the Union-Find algorithm mentioned above). This two-parameter function can be defined as:

α(m, n) = min { k : α_k_(n) ≤ 3 + m / n }.

This definition differs by at most a small additive constant from the "usual" definition of α(m, n) found in the literature. And as before, we defined it directly, without making mention of the rapidly-growing Ackermann function.

The function α(m, n) satisfies the following properties:

• • α(m, n) ≤ α(n) for every m and n.
  • α(m, n) is nonincreasing in m.
  • If m = n_α_k(n) then α(m, n) ≤ k.

R. Seidel, Understanding the inverse Ackermann function (PDF presentation).