MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## Is there an “elegant” non-recursive formula for these coefficients? Also, how can one get proofs of these patterns?

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

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.

1. 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.

1. 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!

2. 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$.

3. 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.

-
+1 for lots of details and interesting write up. – Theo Johnson-Freyd Mar 7 2011 at 4:06
I second Theo Johnson-Freyd, a very well written exposition. Well, Mike (mike3) knows already the following link so it does not add something for the solution of an explicite formula, but for the reader unfamiliar with that question some more detailed examples may be interesting. See go.helms-net.de/math/tetdocs/APT.htm where the mag-coefficients are collected in the coefficients-matrices for the bivariate powerseries of iterates of $b^x - 1$ – Gottfried Helms Mar 7 2011 at 8:45
The sum of one row of mags can be expressed as sort of factorial of binomials: the sequence is 1,1,3,18,180,2700,... and because in the context of that powerseries I often came on something like that. We can write $1,1=1,3=1*3,18=1*3*6,180=1*3*6*10,2700=1*3*5*10*15,...$ where the factors are just the binomials. Clearly this is the same as your factorial expression, but I suppose this notion here leads to more context. – Gottfried Helms Mar 8 2011 at 14:57

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.

-
 Thanks for this response. But what is EC1? – mike3 Jan 26 2012 at 19:39 Never mind, I saw your website. But another question: is this as simple a formula as it can get, or could there be one that sums over less than exponentially many terms? – mike3 Jan 26 2012 at 20:10 Lulz, I just posted my post seconds after you gave an answer! Oops... :) – mike3 Jan 26 2012 at 20:10 @Mike, I don't see how to get less than exponentially many terms. On the other hand, Examples 3.14.4 and 3.14.5 in EC1 apply to $\Pi_n$, allowing combinatorial interpretations of $\beta_n(S)$ showing that these numbers are positive integers. – Richard Stanley Jan 26 2012 at 20:17 Hmm. What kind of combinatorial interpretations do these numbers have? – mike3 Jan 26 2012 at 20:45

Mike, possibly you know this all, but for my own pleasure (and for the reader who's not yet much familiar with this all) I can give an explicite description for the mag-numbers. However, this is simply an explication of the terms of some series/arrays which are in fact recursive, but the recursion is so flat that we can resolve it without too much hazzle to direct references on factorials/binomials and the log of the fixpoint only. I employ the notation of (operator-)matrices which are known as Bell-/Carleman-matrices.

The text became too long for the answer-field here, so I link to a pdf-file on my homepage.
(If you don't like pdf there is also a html-version, but automatically generated by word and not perfect formatted)

Since I describe this using the known procedure of diagonalization of a triangular matrix some of your questions concerning the structure of coefficients may be answered or possibly a rigorous answer lays on the hand.

(P.s.: if it is more convenient for the MO-readers I could upload or possibly reformat the text for mathjax, but the latter would be much unwanted work...)

[update]: updated the pdf-file for readability

-
 However, there doesn't seem to be any "explicit non-recursive formula" for diagnonalizing a matrix... So I'm not sure of how much help this is... And even if there was, that may not necessarily offer the most elegant formula as it'd be applying a very general formula that may not give an easily-simplifiable answer. Note how I mentioned that it seems an explicit formula can already be built, but from very general techniques that result in an inelegant, seemingly too complicated solution. – mike3 Mar 10 2011 at 9:15 Hmm, the values in the eigenvector-matrix (the *w*-values) are finitely composed by stirling-numbers 2'nd kind and can even be expressed by sums of factorials in fractions, so this is "non-recursive" and "explicite". - However the number of involved summands increases nonlinearly with the row-index and include dependencies of the (additive) partition-scheme of the row-index of a *w*-value in the eigenvector-matrix W - so I'd agree, that this it not really elegant. But the example was meant to show that the explicite representation is not too strange. – Gottfried Helms Mar 10 2011 at 13:54 And I take it, there's no explicit non-recursive formula for w? – mike3 Mar 11 2011 at 2:01 Hmm, I seem to have some communication problem here. On page 3, bottom, I have under the header "removing recursion" an explicte expression of four summands for $w_{4,1}$ Each summand is the product of some stirling-numbers and the base-depending u*-constant. The number of factors in the products and the number of summands depend on the rowindex *r in $w_{r,c}$ I think this is -in principle- no more recursive than, say, the definition of the factorial or that of additive partioning of a natural number. But, well, I'm not going to insist, perhaps there is something in it which I don't catch. – Gottfried Helms Mar 11 2011 at 5:14 I see, but it does not seem to yield an elegant general formula. And the powers of u in one thing there look suspiciously like binary bit patterns, suggesting the binary counting (which makes the "hideous" formula I mention in the main post so inelegant and ugly) doesn't want to go away or simplify/minimize itself... :( – mike3 Mar 11 2011 at 7:29
show 1 more comment

This is a comment not an answer. Here are a few apparent patterns:

\begin{align}mag_{n,0} &= (n-1)! \\ mag_{n,1} &= (n-1)! \frac{n-2}{2} \\ mag_{n,{n-1 \choose 2}} &= 1 \\ mag_{n,{n-1 \choose 2}-1} &= {n\choose2}-1 \\ mag_{n,{n-1 \choose 2}-2} &= \frac{(n-2)(n-1)n(3n-5)}{24}-1\end{align}

-
 Thanks, but many of those patterns I already knew. It doesn't seem to help any, and $mag_{n, {n-1 \choose 2}-3}$ does not seem to have a polynomial solution. – mike3 Mar 8 2011 at 2:20