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 + 36L + 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$):


*[update]: remark: for readability I transposed the original table. But I did not adapt the use of "columns" and "rows" in the surrounding text, so that must be translated in mind (Gottfried Helms)*



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




---



Is there an "elegant" non-recursive formula for these coefficients? Also, how can one get proofs of these patterns?
Let $\beta\_n$ denote the flag $h$-vector (as defined in EC1, Section
3.13) of the partition lattice $\Pi\_n$ (EC1, Example 3.10.4). Then 
 $$ \mathrm{mag}\_{n,{n-1\choose 2}-j} = \sum\_S \beta\_n(S), $$
where $S$ ranges over all subsets of $\lbrace 1,2,\dots,n-2\rbrace$ whose
elements sum to $j$. An explicit formula for $\beta\_n(S)$ is given by 
 $$ \beta\_n(S) = \sum\_{T\subseteq S} (-1)^{|S-T|}
 \alpha\_n(T), $$
where if the elements of $T$ are $t\_1<\cdots < t\_k$, then
 $$ \alpha\_n(T) = S(n,n-t\_1)S(n-t\_1,n-t\_2)
 S(n-t\_2,n-t\_3)\cdots S(n-t\_{k-1},n-t\_k). $$
Here $S(m,j)$ denotes a Stirling number of the second kind.


**Addendum.** A combinatorial description of the mag numbers is
somewhat complicated. Consider all ways to start with the $n$ sets
$\lbrace 1 \rbrace,\dots, \lbrace n \rbrace$. At each step we take two
of our sets and replace them by their union. After $n-1$ steps we will
have the single set $\lbrace 1,2,\dots,n \rbrace$. An example for
$n=6$ is (writing a set like $\lbrace 2,3,5\rbrace$ as 235)
1-2-3-4-5-6, 1-2-36-4-5, 14-36-2-5, 14-356-2, 14356-2, 123456. At the
$i$th step suppose we take the union of two sets $S$ and $T$. Let
$a\_i$ be the least integer $j$ such that $j$ belongs to one of the
sets $S$ or $T$, and some number smaller than $j$ belongs to the other
set. For the example above we get $(a\_1,\dots,a\_5)=(6,4,5,3,2)$. If
$\nu$ denotes this merging process, then let $f(\nu) = \sum i$,
summed over all $i$ for which $a\_i>a\_{i+1}$. For the above example,
$f(\nu) = 1+3+4=8$. (The number $f(\nu)$ is called the *major index*
of the sequence $(a\_1,\dots,a\_{n-1})$.) Then 
$\mathrm{mag}\_{n,{n-1\choose 2}-j}$ is the number
of merging processes $\nu$ for which $f(\nu)=j$. This might look
completely contrived to the uninitiated, but it is very natural within
the theory of flag $h$-vectors.


