Hi.

Not sure if this is a "good" question for this forum or if it'll get panned, but here goes anyway...

Consider this problem. I've been trying to find a formula to expand the "regular iteration" of "exp". Regular iteration is a special kind of complex function that is a solution of the equation

$$f(z+1) = \exp(f(z))$$

(or more generally for functions other than $\exp$. It is called "regular" because as a solution it is characterized by the fact the the functional iterates $F^t(z) = f(t + f^{-1}(z))$, with $F$ being the function that is $\exp$ in this case, are "regular", or analytic, at a chosen fixed point of $F$, for all non-integer $t$. There are regular iterations for every fixed point.)

This regular iteration in particular is an entire function. To get it, we take a fixed point $L$ of $\exp$ and expand a solution in powers of $L^z$. The result is to obtain a Fourier series

$$f(z) = \sum_{n=0}^{\infty} a_n L^{nz}$$

where

$$a_0 = L$$ $$a_1 = 1$$ $$a_n = \frac{B_n(1! a_1, 2! a_2, ..., (n-1)! a_{n-1}, 0)}{n!(L^{n-1} - 1)}$$

with $B_n$ being the nth "complete" Bell polynomial. This recursive formula yields the following expansions:

$$a_2 = \frac{1}{2L - 2}$$ $$a_3 = \frac{L + 2}{6L^3 - 6L^2 - 6L + 6}$$ $$a_4 = \frac{L^3 + 5L^2 + 6L + 6}{24L^6 - 24L^5 - 24L^4 + 24L^2 + 24L - 24}$$ $$a_5 = \frac{L^6 + 9L^5 + 24L^4 + 40L^3 + 46L^2 + 35L + 24}{120L^{10} - 120L^9 - 120L^8 + 240L^5 - 120L^2 - 120L + 120}$$ ...

It appears that, by pattern recognition and factoring the denominators,

$$a_n = \frac{\sum_{j=0}^{\frac{(n-1)(n-2)}{2}} mag_{n,j} L^j}{\prod_{j=2}^{n} j(L^{j-1} - 1)}$$

where $\mathrm{mag}_{n,j}$ is a sequence of "magic" numbers (integers) that looks like this (with the leftmost column being $j = 0$):

n = 1: 1
n = 2: 1
n = 3: 2, 1
n = 4: 6, 6, 5, 1
n = 5: 24, 36, 46, 40, 24, 9, 1
n = 6: 120, 240, 390, 480, 514, 416, 301, 160, 64, 14, 1
n = 7: 720, 1800, 3480, 5250, 7028, 8056, 8252, 7426, 5979, 4208, 2542, 1295, 504, 139, 20, 1
n = 8: 5040, 15120, 33600, 58800, 91014, 124250, 155994, 177220, 186810, 181076, 163149, 134665, 102745, 71070, 44605, 24550, 11712, 4543, 1344, 265, 27, 1
n = 9: 40320, 141120, 352800, 695520, 1204056, 1855728, 2640832, 3473156, 4277156, 4942428, 5395818, 5561296, 5433412, 5021790, 4391304, 3625896, 2820686, 2056845, 1398299, 879339, 504762, 260613, 117748, 45178, 13845, 3156, 461, 35, 1
n = 10: 362880, 1451520, 4021920, 8769600, 16664760, 28264320, 44216040, 64324680, 88189476, 114342744, 141184014, 166279080, 187614312, 202901634, 210825718, 210403826, 201934358, 186191430, 164980407, 140216446, 114231817, 88934355, 66047166, 46576620, 31071602, 19460271, 11365652, 6112650, 2987358, 1298181, 488878, 153094, 37692, 6705, 749, 44, 1
...

But what is the simplest (or at least "reasonably" simple) non-recursive formula for these numbers, or perhaps the numerators in general? Like a sum formula, or something like that. Is there some kind of "combinatorical"-like formula here (sums/products, perhaps nested, of factorials and powers and stuff like that, binomial coefficients, special numbers, etc.)? I notice that the first column is factorials... (how can one prove that?)

And regardless of the formula for the "mag", can one prove from the recurrence formula that the $a_n$ have the form given, and if so, how? Especially, how can one prove the numerator has degree $\frac{(n-1)(n-2)}{2}$? Perhaps that might provide insight into how to find the formula for the "mag".

The ultimate goal here is to try and obtain a series expansion for the "tetration" function $^z e$, more specifically, Kneser's tetrational function, described in Kneser's papers on solutions of $f(f(x)) = \exp(x)$ and related equations (paper is in German, I only saw the translations.). Though this may not be the best way to go, since after constructing this regular iteration function, we then need a special mapping derived from a Riemann mapping to "distort" it so it becomes real-valued at the real axis, and I don't know if there's any good way to construct Riemann mappings even as "non-closed" infinite expansions. But I'm still curious to see if at least a formula for this function is possible.

EDIT: Oh, and for all its worth, apparently

$$\sum_{j=0}^{\frac{(n-1)(n-2)}{2}} \mathrm{mag}_{n,j} = \frac{n!(n-1)!}{2^{n-1}}$$

if that helps any (don't see how it would, and this is not proven, I just got it by looking up the sums on the integer sequences dictionary site.). Perhaps maybe some hints as to why it has that value could help in finding the formula, though...

Justification for thinking a formula exists

Why do I think this even exists, when there's no guarantee that this kind of really non-trivial recurrence relation should even have a non-recursive solution in the first place? Well, for one, the fact that so much of it could be put in simple form as given, and also I did manage to come up with an explicit formula from a very roundabout way but this formula is excessively complicated and based on very general techniques.

It is difficult to describe that formula here, but the outline of the process to construct it is this, for all its worth:

1. A general recurrence of the form

$$A_1 = r_{1, 1}$$ $$A_n = \sum_{m=1}^{n-1} r_{n,m} A_m$$

has a non-recursive solution formula. This I found myself, but it is hideous and involves binary bit operations. This kind of recurrence is very general, and it also includes the recurrence for the Bernoulli numbers and other kinds of recurrences.

2. The "regular Schroder function" of $F(z) = e^{uz} - 1$, i.e. the function satisfying $\mathrm{RSF}(F(z)) = K \mathrm{RSF}(z)$ (sometimes called the Schroder functional equation, hence the name) which is "regular" in that it can be turned into the regular iteration of $F$ (as we do next), can be given as a Taylor series

$$\mathrm{RSF}(z) = \sum_{n=1}^{\infty} A_n z^n$$

where $A_n$ is given by the recurrence-solving formula with $r_{1,1} = 1$ and $r_{n, m} = \frac{u^{n-1}}{1 - u^{n-1}} \frac{m!}{n!} S(n, m)$ (here, $S(n, m)$ is a Stirling number of the 2nd kind). This is hideous, involving lots of "binary bit manipulation" stuff such as counting 1 bits and positions of 1 bits, which have not-so-nice formulas (the latter involves a set indicator function, at least in the formulation I found myself...). Not sure at all how this could be simplified. The formulas just don't seem to lend themselves to simplification, at least not any that I know of.

3. Invert the regular Schroder function using the Lagrange inversion theorem. This can be expanded in an explicit "non-recursive" form, but it needs so-called "potential polynomials" and other complexity. Plug the huge $A_n$ formula into this. Horrific!

4. Now $U(z) = \mathrm{RSF}^{-1}(u^z)$ is a "regular iteration" of $e^{uz} - 1$, giveable as a Fourier series, or Taylor series in $u^z$.

5. Apply the topological conjugation to conjugate it to iteration of $e^{vz}$ by taking $v = ue^{-u}$ thus $u = -W(-v)$ (Lambert's W-function). Take $H(z) = e^{-u} z - 1$ then find $H^{-1} o U o H$. This gives a regular iteration of $e^{vz}$, thus set $v = 1$ ($u = -W(-1) = \mathrm{fixed\ point\ of\ exponential}$). Though, there may be a constant displacement of some kind offsetting this regular from the one given by the $a_n$-formula. EDIT: Oops!!!! That should be $H^{-1}(U(U^{-1}(H(U(0))) + z))$, but wait, that's just a constant-shift of $H^{-1} o U$, so just take $H^{-1} o U$ as the regular iteration of $e^{vz}$, probably displaced (in $z$) from the one we're trying to solve for by a constant, but should be structurally identical (and you can try and compute $U^{-1}(H(U(0)))$. Perhaps that is the shift required, but I don't know.).

(EDIT: Apparently the step-numbering above isn't working right for some reason.)

So by this, I think an explicit formula exists (though that constant-shift at the end may be a little problem, but not much, since it is immaterial to the structure of the function). I'm just interested in something simpler than this, preferably something to "fill out" the "mag" formula I gave...

EDIT: Now I'm pratically sure explicit non-recursive solution is possible. Using some numerical tests, I figured the constant shift should be (for $v = 1$, i.e. $u = L$) simply -1, that is, take $H^{-1}(U(z - 1))$ and the coefficients of the Fourier expansion will be equal to $a_n$ in explicit non-recursive form (but atrocious, hence my question, to find something more elegant. This at least evidences that an explicit non-recursive solution is possible, addressing any skeptics' concerns that it isn't and so an elegant one wouldn't exist either. And it is a good bet that if an atrocious formula exists derived from very general principles (note Step 1 above), there may be a more elegant one derived from more specific principles.). So, almost a proof. It could probably be turned into one with a little more work, though that would be much too long to post here.