[FOM] Fractional Iteration and Rates of Growth

joeshipman@aol.com joeshipman at aol.com
Mon May 1 19:59:02 EDT 2006

By using iteration, we can define natural functions with arbitrarily 
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....
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.

How do you know that the resulting power series have nonzero radii of 
convergence? It's not clear to me that this gives an algorithm 
extending the definition of, say, the "tower function" f(0)=1, 
f(i+1)=2^(f(i)) to all real numbers.

Another route might be to calculate the "square root of the exponential 
function" as a formal power series, this clearly gives a computable 
sequence of coefficients (whatever base you start with, it doesn't have 
to be e) without resorting to analysis; then one can try to prove that 
the resulting series converges. You may have to start with (e^x - 1) 
instead of e^x, and it is then a nontrivial problem to generalize this 
to find the natural extension of the true exponential function (and 
similarly for the functions (2^x - 1) and 2^x, etc.).

-- JS

More information about the FOM mailing list