[FOM] Fractional Iteration and Rates of Growth

[Dmytro Taranovsky]

By using iteration, we can define natural functions with arbitrarily
high primitive recursive rate of growth, and an interesting question is
whether these functions have natural analogues defined at all positive
real numbers.  Formally, there is no problem:  Any f:N->N has an
analytic extension, and if f is sufficiently fast growing, then we can
arrange for all the coefficients of the power series to be positive.
Instead, the problem is finding the preferred values at non-integral
arguments.  For example, the Gamma function is the preferred extension
of the factorial n->(n-1)!.

To solve the problem, we use fractional iteration.  If for all x,
f(f(x))=g(x), then f is a half-iterate of g, and analogously with other
fractions.  It turns out that if we restrict to analytic functions f
with f(0)=0 and f'(0)>0, then the fractional iterates are unique.  By
taking limits, we can even iterate an irrational number of times.
We now define a family of functions as follows:
f(1, 1, x) = 2*x
f(n, a, x) = ath iterate of f(n, 1, x)
f(n+1, 1, x) = f(n, x, x)

We use analytic continuation (along the real line) to define f for all
positive a and x.  There is no non-uniqueness.  By using f, we can also
define intermediate rates of growth such as a half-exponential growth
rate, f(2, 1/2, x).  Also, f(0, a, x) is best defined as x+a.

However, there are two outstanding problems, which some FOM subscribers
may know how to solve:
1.  Prove that f exists for all positive n, a, and x (n is an integer).
2.  Investigate how the asymptotic rates of growth are affected by the
choice of f(1, 1, x).            For example, another choice might be
f(2, 1, x) = e^x-1.  Such investigations may allow us to confirm that f
has a natural rate of growth.

Dmytro Taranovsky