# How to calculate generalized Puiseux series?

I recently posted this, post containing a series of questions concerning the integration of ${x^{x^{x^x}}}$. In order to do so, I wrote ${x^{x^{x^x}}}$ as the following infinite summation: $$1 + \sum_{n=0}^{\infty}\sum_{k=0}^{n}\bigg(\frac{x^{n+1} \log^{n+1+k}(x)C_{kn}}{\Gamma(n+2)}\bigg)$$ I got to this summation using a "generalized Puiseux series". I mention in the post that I am unsure of how to calculate such a series, but it seemed like more of a side-note and I decided that the question deserved its own post. I am trying to determine the mysteries coefficents in the series (written as $C_{kn}$), but I am unsure how to derive them by calculating the generalized Puiseux series by hand. I have looked up literature on standard Puiseux series, and I can somewhat follow it... however, I can find nearly nothing on generalized Puiseux series, especially literature I am capable of following. While $x^x$ can be written as a standard Puiseux series, $x^{x^x}$ also requires the generalized form, so understanding the derivation of that series might work as well if it is simpler.$\\$

In short, how do we calculate a generalized Puiseux series, specifically for $x^{x^x}$ or for ${x^{x^{x^x}}}$?

The way to do this, is to calculate the coefficients of the iterates ${^2}(e^x)$, ${^3}(e^x)$, ${^4}(e^x)$, etc. first. The coefficients of the corresponding Piseaux for ${^n}z$ are going to be the same.

The problem then becomes:

Let a series $s$ with coefficients $a_n$ be given, as $s=\sum\limits_{n=0}^\infty a_n$. Determine the coefficients $b_n$ of the series expansion for the series $s_1=\exp(s\cdot x)$, where $s_1=\sum\limits_{n=0}^\infty b_n$.

There were two solutions given, one by Leroy Quet, as:

If $B(x)=\exp(A(x))$ then $B'(x)=B(x)\cdot A'(x)$, which provides a recursive relation for the solution and one by Robert Israel, as:

$$b_n=\sum\left(\prod\frac{a_{k-1}^{s_k}}{s_k!}\right)$$

where the sum is over all sequences $s=[s_1,s_2,s_3,...]$ of nonnegative integers, with:

$$n=\sum\limits_{k=1}^\infty k\cdot s_k$$

and the product is over those $k$ for which $s_k>0$ (a finite set).

(Quoting RI:) For example, the partitions of 4 correspond to $s=[4,0...]$, $[2,1,0...]$, $[0,2,0...]$, $[1,0,1,0...]$ and $[0,0,0,1,0...]$, so:

$$b_4 = \frac{a_0^4}{4!} + \frac{a_0^2 a_1}{2!1!} + \frac{a_1^2}{2!} + a_0\cdot a_2 + a_3$$

Robert then gives the following Maple code for the coefficients:

b:=(n::nonnegint)->add( mul(a[q[1]-1]^q[2]/q[2]!,
q = map(j -> [j, numboccur(j,P)], convert(P,set))),
P = combinat[partition](n));


Note OP: The method I used was Leroy Quet's, to whom I give the credits on my PhD thesis.

Note GH: If you use either method, you will end up with the coefficients of your "Pascal" Matrices.

In view of your comment, a clarification: The notation for the problem was probably a bit unfortunate. What you have, to start with, are the coefficients $a_n$ of:

$${^1}(e^x)=s=\sum\limits_{n=0}^\infty a_n\cdot x^n=\sum\limits_{n=0}^\infty \frac{x^n}{n!}$$.

The process is now inductive: You are looking for the $b_n$ such that:

$${^2}(e^x)=s=\sum\limits_{n=0}^\infty b_n\cdot x^n$$.

These $b_n$ can be gotten using either of the two solutions above. I.e. either using:

$$B(x)=\exp(A(x))\Rightarrow B'(x)=B(x)\cdot A'(x)$$

by writing down what you see and adjusting the indexes, or using Robert Israel's argument for the $b_n$.

Then you continue. You have the new $a_n$ (now as coefficients of ${^2}(e^x)$) and you are looking for new $b_n$ such that:

$${^3}(e^x)=s=\sum\limits_{n=0}^\infty b_n\cdot x^n$$.

and you continue in a similar spirit, using either method.

Here is some Maple code using R.I.'s routine, illustrating the above iteration:

restart;
N:=5;
a := Array(0 .. N, [seq(1/factorial(n), n = 0 .. N)]);# start with exp()
b := Array(0 .. N);#store coefficients of new iterate.
c := proc (n::nonnegint) options operator, arrow;
add(mul(a[q[1]-1]^q[2]/factorial(q[2]), q = map(proc (j) options operator,
arrow; [j, numboccur(j, P)] end proc, convert(P, set))),
P = combinat[partition](n)) end proc;#R.I.'s routine


Calculate coefficients of ${^2}(e^x)$:

for n from 0 to N do b[n] := c(n) end do;


Print coefficients of ${^2}(e^x)$:

for n from 0 to N do print(b[n]) end do


$$1,1,\frac{3}{2},\frac{5}{3},\frac{41}{24},\frac{49}{30}$$

Load new coefficients into array a again:

for n from 0 to N do a[n] := b[n] end do


Calculate coefficients of ${^3}(e^x)$:

for n from 0 to N do b[n] := c(n) end do


Print coefficients of ${^3}(e^x)$:

for n from 0 to N do print(b[n]) end do


$$1,1,\frac{3}{2},\frac{8}{3},\frac{101}{24},\frac{63}{10}$$

etc.

In other words:

\begin{align} {^1}(e^x)&=1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\cdots\\ {^2}(e^x)&=1+x+\frac{3}{2}\cdot x^2+\frac{5}{3}\cdot x^3+\frac{41}{24}\cdot x^4+\cdots\\ {^3}(e^x)&=1+x+\frac{3}{2}\cdot x^2+\frac{8}{3}\cdot x^3+\frac{101}{24}\cdot x^4+\cdots\\ \ldots \end{align}

Now, once you have the iterates of $\exp$, the corresponding Puiseux series can be gotten through the substitution $x\to \ln(z)$ by choosing the principal branch of $\ln$:

\begin{align} {^1}z&=1+\ln(z)+\frac{1}{2!}\cdot \ln(z)^2+\frac{1}{3!}\cdot \ln(z)^3+\frac{1}{4!}\cdot \ln(z)^4+\cdots\\ {^2}z&=1+\ln(z)+\frac{3}{2}\cdot \ln(z)^2+\frac{5}{3}\cdot \ln(z)^3+\frac{41}{24}\cdot \ln(z)^4+\cdots\\ {^3}z&=1+\ln(z)+\frac{3}{2}\cdot \ln(z)^2+\frac{8}{3}\cdot \ln(z)^3+\frac{101}{24}\cdot \ln(z)^4+\cdots\\ \ldots \end{align}

• I'll be honest here, I don't understand much of what is happening in this post (I've only taken Calc 1 in school... everything else mathematical I have studied far ahead on my own). I get the idea of what you are doing here, but I am getting greatly confused by some of the notation. I believe you initially define a series $s$ that will be composed entirely out of coefficients $a_n$. How you derive the next line concerning $b_n$ I cannot tell. – Brevan Ellefsen Sep 23 '15 at 6:43
• I greatly appreciate the help, and this seems like a good solution, but I cannot understand what you are doing. I don't mean to bother you with these likely elementary questions, but an explanation would be greatly appreciated! – Brevan Ellefsen Sep 23 '15 at 6:43
• See the addendum for a brief explanation. – Yiannis Galidakis Sep 23 '15 at 8:43
• See second addendum for actual calculation of coefficients. – Yiannis Galidakis Sep 23 '15 at 11:17
• Hmm, the last addendum gives a series in terms of $\ln(z)$. W/A gives its Puisieux-series in terms of "$z \ln(z)$" (or "$u e^u$" ) *plus* a set of polynomials in "$\ln(z)$" only - and also the same pattern for all $m$ in $^m z$. That makes Brevan's question a bit more difficult – Gottfried Helms Sep 23 '15 at 16:00

Note: this is not yet an answer, but only an ansatz to find a promising key for the pattern-detection

To find patterns I would seriously try to simplify formulae, such that constants move out of loops/sums/products and repeatedly occuring functions with same parameter get a shorter symbol. So for instance $$\; ^4 x= \sum_{n=0}^{\infty} \frac{(x \log(x))^n}{n!} \sum_{k=0}^{n-1} \bigg( \log(x)^k C_{n-1,k}\bigg)$$ where, however, I have moved the constant $1$ into the loop, but only to standardize the bounds for the sums to usual values (here the lower bound $0$).
Moreover I' written $u$ for $\log(x)$ and for scalars stay with small letters ($c$) then $$\; ^4 x= \sum_{n=0}^{\infty} \bigg( \frac{(u \cdot e^u )^n}{n!} \sum_{k=0}^{n-1} c_{n-1,k}\cdot u^k \bigg)$$

To detect patterns I make it more general, so I would finally write: $$\; ^m x= \sum_{n=0}^{\infty} \frac{(u \cdot e^u )^n}{n!} P_m(u,n-1)$$ $\qquad \qquad$ where the polynomials $$P_m(u,n) = \sum_{k=0}^n c_{m:n,k} \cdot u^k$$ $\qquad \qquad \qquad \qquad$ have the coefficients $c_{m:n,k}$from the lower triangular matrices $C_m$.

Empirically (by the W/A-solutions) we must also insert a correction: for the odd $m$ the rhs must have one additional factor $x$: $$\; ^m x= \sum_{n=0}^{\infty} \frac{(u \cdot e^u )^n}{n!} P_m(u,n) \qquad \text{ for m even } \\ \; ^m x= x \sum_{n=0}^{\infty} \frac{(u \cdot e^u )^n}{n!} P_m(u,n) \qquad \text{ for m odd } \tag 1$$

I don't really see why the attempt is at W/A, to extract powers of the product $u \cdot e^u$ as standard entities; in the view that we deal here in the framework of iteration one might rather consider to use for instance $u$, $ue^u$ , $u e^{ue^u}$, ... instead for the various m'th $\; ^m x$ and have then likely smoother matrices $C_m$.

But well, Wolfram-alpha gives us that structure of solutions, and what I've got so far are the following matrices $C_m$ : $$\begin{array}{ll} \begin{matrix} \; ^2x : & C_2=& \small \begin{bmatrix} 1 & . & . & . & . & . \\ 1 & 0 & . & . & . & . \\ 1 & 0 & 0 & . & . & . \\ 1 & 0 & 0 & 0 & . & . \\ 1 & 0 & 0 & 0 & 0 & . \\ 1 & 0 & 0 & 0 & 0 & 0 \end{bmatrix} \end{matrix} & \begin{matrix} \; ^3x : & C_3=& \small \begin{bmatrix} 1 & . & . & . & . & . \\ 0 & 1 & . & . & . & . \\ 0 & 1 & 1 & . & . & . \\ 0 & 1 & 3 & 1 & . & . \\ 0 & 1 & 7 & 6 & 1 & . \\ 0 & 1 & 15 & 25 & 10 & 1 \end{bmatrix} \end{matrix} \\ \begin{matrix} \; ^4x : & C_4=& \small \begin{bmatrix} 1 & . & . & . & . \\ 1 & 0 & . & . & . \\ 1 & 2 & 0 & . & . \\ 1 & 9 & 3 & 0 & . \\ 1 & 28 & 36 & 4 & 0 \\ 1 & 75 & 245 & 110 & 5 \end{bmatrix} \end{matrix} & \begin{matrix} \; ^5x : & C_5=& \small \begin{bmatrix} 1 & . & . & . & . & . \\ 0 & 1 & . & . & . & . \\ 0 & 1 & 3 & . & . & . \\ 0 & 1 & 12 & 10 & . & . \\ 0 & 1 & 35 & 90 & 41 & . \\ 0 & 1 & 90 & 520 & 660 & 196 \end{bmatrix} \end{matrix} \\ \begin{matrix} \; ^6x : & C_6=& \small \begin{bmatrix} 1 & . & . & . & . & . \\ 1 & 0 & . & . & . & . \\ 1 & 2 & 0 & . & . & . \\ 1 & 9 & 9 & 0 & . & . \\ 1 & 28 & 96 & 40 & 0 & . \\ 1 & 75 & 625 & 830 & 205 & 0 \\ 1 & 186 & 3240 & 9600 & 7200 & 1176 \end{bmatrix} \end{matrix} & \\ \begin{matrix} \; ^8x : & C_8= & \small \begin{bmatrix} 1 &. &. &. &. &. &. \\ 1 &0 &. &. &. &. &. \\ 1 &2 &0 &. &. &. &. \\ 1 &9 &9 &0 &. &. & \\ 1 &28 &96 &64 &0 &. &. \\ 1 &75 &625 &1250 &505 &0 &. \\ 1 &186 &3240 &14040 &16200 &4536 &0 \\ 1 &441 &14749 &120050 &284900 &219387 &46249 \end{bmatrix} \end{matrix} \end{array}$$

[update] I've just found a partial pattern. For $C_8$ I find $$\begin{matrix} \; ^8x : & C_8= & \small \begin{bmatrix} \begin{array} {r} 1 & & & & & & \\ 1 & 0 & & & & & \\ 1 & 2\cdot1 & 0 & & & & \\ 1 & 3\cdot3 & 3^2\cdot1 & 0 & & & \\ 1 & 4\cdot7 & 4^2\cdot6 & 4^3\cdot1 & 0 & & \\ 1 & 5\cdot15 & 5^2\cdot25 & 5^3\cdot10 & 5^4\cdot1 -5! & 0 & \\ 1 & 6\cdot31 & 6^2\cdot90 & 6^3\cdot65 & 6^4\cdot15 -3240 & 4536 & 0\\ 1 & 7\cdot63 & 7^2\cdot301 & 7^3\cdot350 & 7^4\cdot140 -51240 & 219387 & 46249\\ \end{array} \end{bmatrix} \end{matrix}$$ What we see is, that the leading columns are perfect multiples of the Stirling numbers 2nd kind of the same column-index; and in the trailing columns we have defects. From the examples for $^2x, ^4x, ^6x, ^8x$ we see that with each increasing $m$ one more column becomes "correct", with that simple pattern. And it is easy to hypothesize the form of the matrix for $m \to \infty$ .
I've however not yet found a pattern for the defects.

• This is a very interesting post... thank you for sharing! You bring up some good points, and I will definitely further investigate using the methods you mention. However, for the first equation you get $^4 x= \sum_{n=0}^{\infty} \frac{(x \log(x))^n}{n!} \sum_{k=0}^{n} \bigg( \log(x)^k C_{kn}\bigg)$. I calculated that it is $\sum_{n=0}^{\infty} \bigg[\frac{x^n \log^n(x)}{n!}\sum_{k=0}^{n-1}\bigg(C_{kn}\log^k(x)\bigg)\bigg]$ in my other post on this subject... Am I missing something? Why are you replacing the upper limit of $n-1$ by $n$? – Brevan Ellefsen Sep 22 '15 at 22:30
• I should note that I accidentally stumbled upon your paper when looking through coefficient tables for iterates of $^nexp(x)$ on the OEIS. The paper has been very useful for referencing when I get similar results, in order to compare methodologies for reaching the same conclusions in hopes that using different methods will enlighten me on my problems concerning $^nx$. – Brevan Ellefsen Sep 23 '15 at 6:46
• Hmm, modulo some error... I'll see what I might have been done wrong. I replaced n by n+1 and pulled the $1+$ into the loop which can be understood to have index zero (exponent zero) - I'll see later what was going on – Gottfried Helms Sep 23 '15 at 6:51
• Gottfried, sorry to interject, I've seen these coefficients as a diagonal on some or other (I can't recall) method of iterates, where you called your matrices Pascal. I am pretty sure they match. I made a silent comment on my original answer, but you probably didn't see it. – Yiannis Galidakis Sep 23 '15 at 8:49
• @Yiannis: hey, thank you for that reminder. I was also redirected to my treatize on "pascalmatrix tetrated" (where the pascalmatrix is just the matrix of binomialcoefficients) by the remark of Brevan. Well I think that the computation scheme is very similar, but while I'm implicitely work with $^m(ue^u)$ as you have also pointed to in your answer, the tables here should have slightly differences to that; in the OP's /W-A's notation for the puisieux-series for each $m$ the same powers of $ue^u$ are extracted and not the iterates. – Gottfried Helms Sep 23 '15 at 9:03

This answer is just to reproduce my derivation for my modified notation in my other answer.

The original equation: $$1 + \sum_{n=0}^{\infty}\sum_{k=0}^{n}\bigg(\frac{x^{n+1} \log^{n+1+k}(x)C_{kn}}{\Gamma(n+2)}\bigg)$$

My notational modification: (indeed I had an error with the n at the inner loop): $$\displaystyle{ \begin{array} {lll} ^4 x &=& \displaystyle 1 + \sum_{n=0}^{\infty} \frac{x^{n+1} \log^{n+1}(x)}{\Gamma(n+2)} \sum_{k=0}^{n}\bigg( \log^k(x)c_{n,k}\bigg) \\ &=& \displaystyle 1 + \sum_{n=0}^{\infty} \left( \frac{x^{n+1} u^{n+1}}{(n+1)!} \sum_{k=0}^{n} u^kc_{n,k} \right)\\ &=& \displaystyle 1 + \sum_{n=1}^{\infty} \left( \frac{(ux)^n }{n!} \sum_{k=0}^{n-1} u^k c_{n-1,k} \right)\\ \end{array}}$$ Then I inserted the $1$ as the element at $n=0$, but in the light of the $n-1$ in the inner loop it is possibly better to leave the equation in this form.