7
$\begingroup$

I have seen here and there discussions about what is the "correct" way of extending the Ackermann function to the reals (the same way the Gamma function extends the factorial function to the reals). For example, there is this previous question here at MathOverflow. However, I don't know whether any satisfactory conclusion has been reached in this regard.

Here is a slightly unusual idea of how perhaps one could "smooth out" the functions $\log^* n$, $\log^{**} n$, $\log^{***} n$, $\ldots$.

Let's consider for concreteness $\log^* n$. Recall that $\log^* n$ is defined as the number of times one must apply $\log$ (say $\log_2$), starting from $n$, until we reach a number not larger than $1$. Hence, $\log^* n$ is by definition integer-valued (even if $n$ is not an integer). We would like to "smooth out" this function so that, for example, $\log^* 20$ gives a real number between $3$ and $4$.

Take a combinatorial problem whose solution involves $\log^*$. For example, let $f(n)$ be the minimum size of a family $\mathcal F$ of subsets of $\{1,\ldots,n\}$ such that each interval $\{a,\ldots b\}$ (with $1\le a\le b\le n$) can be written as the union of at most $4$ elements of $\mathcal F$. Then $f(n) = \Theta(n\log^* n)$ (see e.g. Alon and Schieber).

Now define $\log^* n$ as the limit of the sequence $\frac{f(n)}{n}$, $\frac{f(2^n)}{2^{n}}-1$, $\frac{f(2^{2^n})}{2^{2^n}} - 2$, $\ldots$.

Questions:

  • Has this approach been considered before?
  • Does this sequence converge for all $n$?
  • If so, is it as smooth as desired?
  • Will we get the same result if start with a different combinatorial problem instead?

[Background on the above problem: If we generalize the problem by replacing $4$ by $k$, then $f_k(n)$ satisfies: $f_1(n) = \binom{n+1}{2}$, $f_2(n) = \Theta(n\log n)$, $f_3(n) = \Theta(n\log\log n)$, and then, for $k\ge 4$, $f_k(n) = \Theta(n\log^{*\cdots*} n)$ with $\lfloor k/2\rfloor-1$ stars.

However, I don't know whether the constants are known even for the case $k=2$. The argument of Alon and Schieber gives $(1/2) n \log_2 n \le f_2(n)\le n\log_2n$.]

$\endgroup$
3
  • 2
    $\begingroup$ Your "smooth" $\log^*(n)$ is known as the super logarithm, written $slog_b$ for base $b$. It is the abel function of $b^x$, where in $slog(b^x) = slog(x) + 1$. There are loads of uniqueness issues with these functions, many solutions exist. Analytic solutions are hard to come by but there still exists a plethora of them. Interestingly it is the inverse function to $F(x) = ^x b$ which is tetration. It being $F(0) = 1$ and $b^{F(x)} = F(x+1)$. Therefore $slog(x) = y$ satisfies $^yb = x$. $\endgroup$
    – user78249
    Apr 21, 2016 at 20:52
  • $\begingroup$ Why the computability-theory tag? $\endgroup$ Apr 22, 2016 at 0:17
  • 1
    $\begingroup$ Because the Ackermann function is not primitive recursive. Other Ackermann function questions have this tag... $\endgroup$ Apr 22, 2016 at 2:03

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.