Appell polynomials, cumulants, noncrossing partitions, Dyck lattice paths, and inversion

The raising op for any Appell sequence is determined by the derivative of the log of the e.g.f. of the basic number sequence, connecting the op to the combinatorics of the cumulant expansion OEIS-127671 of the moment generating function and its inverse relation A036040 for the general Bell polynomials of the Faa di Bruno formula for composition of functions. Diagrammatics of the partitions for the combinatorics of these entries can be found in the statistical physics references of A036040, but are by no means unique.

Furthermore, the combinatorics of the classical cumulants are, at a combinatorial level, intimately allied to that of the free cumulants of free probability theory and, consequently, to noncrossing partitions, as discussed by Jonathan Novak in “Three lectures on free probability”, Roland Speicher in “Free probability theory and non-crossing partitions”, Franz Lehner and coauthors in papers noted in the Bernoulli Appells entry, and by Ardila, Rincon, and Williams in “Positroids and noncrossing partitions”.

To see how the noncrossing partitions can be paired with partitions of integers compare the drawings in the Wikipedia article on noncrossing partitions with the formula for inversions of A134264, or, equivalently, compare the depictions of Dyck paths for the Catalan numbers at Robert Dickau’s website with A125181 and the inversion formula. Each summand in the formula may be associated with one unique type of noncrossing partition (or Dyck path according to ascents for A125181). The number of particles/vertices (ascent length in the Dyck paths for Catalans displayed at Robert Dickau’s) in a connected configuration of each partition is the subscript of the indeterminates in the summand while the number of such configurations in a partition is the superscript or power of the indeterminate. The coefficients of the inversion enumerate these partitions.

For example, consider the noncrossing partitions for {1,2,3,4}, the four element set depicted in the Wiki article. The two orange die correspond to the summand 2 (0')^3 (2')^2 = 2 h_0^3 h_2^2 of the partition polynomial for t^5 for g(t) in A134264, the compositional inverse of f(t) in terms of the indeterminate power series coefficients of its shifted reciprocal h(t)=t/f(t)=h_0+h_1 \;t+ h_2\; t^2+ \cdots . This corresponds to the 5th path on the first row and the 1st path on the second row of the 4-by-4 grids for the Dyck paths for the Catalan numbers of Robert Dickau’s illustrations.

One way noncrossing partitions enter the picture is in my entry on the Hirzebruch criterion through the compositional inversion in terms of reciprocal e.g.f.s A248120 and its relation to that for o.g.f.s A1344264 and the mutinomials A036038. The arguments above and my entries on the Hirzebruch theory of genus classes show how multiplicative and regular and umbral compositional inversions are inextricably linked, so it is not surprising that noncrossing partitions (and their associated Dyck lattice paths) make an appearance.

Let’s look at the relations in more detail. The following is based on the formalism of Appell sequences discussed in earlier entries, particularly in Bernoulli Appells, and that of Anshelevich in “Appell polynomials and their relatives”, where he presents moments and cumulants for Appell sequences, and R. Speicher’s general discussion in “Multiplicative functions on the non-crossing partitions and free convolution”.

First, let’s look at the e.g.f. of an Appell sequence of polynomials as Anshelevich presents it,

\displaystyle e^{A.(x)t} = \frac{1}{M(t)} \; e^{xt} = e^{A.(0)t}e^{xt} \; ,

with the associated moments

\displaystyle M(t)=e^{m.t} = \frac{1}{e^{A.(0)t}}= e^{\bar{A}.(0)t} \; ,

where I’ve identified the moments as the basis \bar{A}_n(0) for the umbral inverse Appell sequence

\displaystyle e^{\bar{A}.(x)t} = e^{\bar{A}.(0)t}e^{xt} = \frac{1}{e^{A.(0)t}} \; e^{xt} .

The associated classical cumulants c_n are then defined by

\displaystyle e^{c.t} = \ln(e^{m.t}) .

Anshelevich presents also a recursion relation for the Appell polynomials (pg. 2, eqn. 2). This can be rewritten as the raising op R_A for the Appell sequence as

\displaystyle A_{n+1}(x) = x A_n(x) - \sum_{k=0}^{n} \binom{n}{k} c_{n+1-k} A_k(x) = x A_n(x) - c. (c. + A.(x))^n

\displaystyle = x A_n(x) - c. A_n(c. + x) = (x - c. e^{c. D_x}) A_n(x) = R_A A_n(x) \; .

In the entry Bernoulli Appells, the raising op for an Appell sequence is expressed several ways. In terms of the base number sequences for the Appell sequence or its umbral compositional inverse

\displaystyle R_A = - \frac{d}{dt} \ln(e^{\bar{A}.(-x)t})|_{t=D_x} = x - \frac{d}{dD_x} \ln(e^{\bar{A}.(0)D_x})

\displaystyle = x + \frac{d}{dD_x} \ln(e^{A.(0)D_x})= \frac{d}{dt} \ln(e^{A.(x)t})|_{t=D_x} \; ,

so comparing the expressions for the raising ops gives

\displaystyle \frac{d}{dt} e^{c.t} = \frac{d}{dt} \ln(e^{\bar{A}.(0)t}) ,

which is consistent with the first definition of the classical cumulants above.

For the Bernoulli polynomials,

\displaystyle e^{B.(x)t} = e^{B.(0)t} e^{xt}= \frac{t}{e^t-1} \; e^{xt}

with the e.g.f. of the Appell umbral inverse sequence given by

\displaystyle e^{\bar{B}.(x)t}= e^{\bar{B}.(0)t}e^{xt} = \frac{e^t-1}{t} \; e^{xt}.

Then \displaystyle \bar{B}_n(x) = \frac{(x+1)^{n+1}-x^{n+1}}{n+1}=m_n(x) with the associated base moments for the Bernoulli sequence \displaystyle\bar{B}_n(0)=m_n=m_n(0)= \frac {1}{n+1} .

The base classical cumulants then, as read off from the raising op given in the Bernoulli Appells entry, are \displaystyle c_n = r_n(0) = \frac{B_n(1)}{n} = \frac{(-1)^{n}B_n(0)}{n}=-\zeta(1-n) for n \ge 1 .

The characteristic function for the moments from a probability measure is determined by

\displaystyle e^{m. \; z} = \frac{e^z-1}{z} = \int_{\mathbb R} e^{x \; z} d\mu(x) = < e^{x\; z} > = \int_0^1 e^{xz} dx ,

which corresponds to a uniform pdf over the unit interval.

Let’s look at a formalism for the free cumulants r_n and moments using o.g.f.s for the Appell sequence and its umbral inverse sequence. Essentially, we are transforming everything with the formal Borel-Laplace transform, so we are looking at the problem in a “Fourier-Laplace” space. In fact, a key function in the development of the theory is the introduction of the Cauchy (Stieltjes) transform for the moments G(z) , which is related to the Laplace transform in the Bernoulli example:

\displaystyle \int_{0}^{\infty} e^{-z \; \omega} e^{m.\omega} \; d\omega = \frac{1}{z-m.} = \sum_{n \ge 0} m_n z^{-(n+1)} =G(z)

\displaystyle = \int_{0}^{\infty} \int_{0}^{\infty} e^{-(z-x)\omega} d\omega \; d\mu(x) = \int_{0}^{\infty} \frac{1}{z-x} \; d\mu(x) ,

which reduces to

\displaystyle G(z) = \int_{0}^{1} \frac{1}{z-x} \; dx = -\ln(1-1/z) = \sum_{n \ge 0} \frac{1}{n+1} z^{-(n+1)} for the Bernoulli uniform pdf.

Similarly, the o.g.f. for an Appell sequence can be written in several equivalent ways:

\displaystyle \hat{O}_A(x,z) = \frac{z}{1-zA.(x)} = \frac{z}{1-z(A.(0)+x)} = \sum_{n \ge 0} (A.(0)+x)^nz^{n+1} = \sum_{n \ge 0} A_n(x) z^{n+1}

\displaystyle = z ( 1 + \sum_{n \ge 1} A_n(x) z^n) ,


\displaystyle \hat{O}_A(x,z) = \int_0^{\infty} z \; e^{-(1-z \; A.(x))t} dt = \int_0^{\infty} e^{-t} z \; e^{A.(x)zt} \; dt .

Then in parallel with the discussions on pages 2 and 17 of Anshelevich and page 626 of Speicher, the extended moment and free cumulant o.g.f.s are

\displaystyle \hat{O}_m(x,z) = \frac{z}{1-z \; m.(x)} = \frac{z}{1-z(m. + x)}

and similarly for the extended cumulants with m. replaced by r. .

The reduced o.g.f.s in the papers are just these with x=0. For easy comparison,

\displaystyle \hat{O}_m(0,z) = \frac{z}{1-zm.} = O_m(z) = z B_{Sp}(z)


\displaystyle \hat{O}_r(0,z) = \frac{z}{1-z \;r.} = O_r(z) = z A_{Sp}(z)

\displaystyle = z (1 + \sum_{n \ge 1} r_n z^n ) = z (1 + RT(z)) ,

where the subscript Sp denotes the functions labelled on page 626 of Speicher.

The critical connection to free convolution and free probability theory is through the inversion of a series G(z) , what Speicher calls the Cauchy transform of the probability measure of the moments and Anshelevich, the Laurent series for the moments, through the R transform or series RT above of the cumulants developed by Voiculescu :

\displaystyle G(z) = O_m(\frac{1}{z})


\displaystyle G(\frac{1+RT(z)}{z}) =z = O_m(\frac{z}{1+RT(z)}) = O_m(\frac{z^2}{O_r(z)}) = O_m(O_m^{(-1)}(z)) .

We can identify the compositional inverse of the moment o.g.f. as the shifted reciprocal of the RT, or free cumulant series, i.e.,

\displaystyle O_m^{(-1)}(z) = \frac{z}{1+RT(z)} =\frac{z^2}{O_r(z)}= \frac{1}{G^{(-1)}(z)} , or

\displaystyle \frac{z}{O_r(z)} = \frac{O_m^{(-1)}(z)}{z}  .

These reciprocals can serve as the bases for an Appell umbral compositional inverse pair, as discussed in the Bernoulli Appells and other entries. The regular compositional inverse relation also implies that the moments and free cumulants are related through the noncrossing partition transform for regular functional compositional inversion of o.g.f.s given by OEIS-A134264 applied to

\displaystyle h(z) = \frac{z}{O_m(z) }= \sum_{n \ge 0} h_n z^n \;    to obtain    \displaystyle \; O_m^{(-1)}(z) ,

or (more directly bringing out the relations among the moments,  free cumulants, and noncrossing partitions / Dyck paths), applied to

\displaystyle h(z) = \frac{z}{O_m^{(-1)}(z)}= 1+RT(z)\;    to obtain    \displaystyle \; O_m(z) .

This last formula gives the weightings as the free cumulants h_n = r_n with h_0=1 of the noncrossing partitions associated to partitions of integers as described above for A134264 to obtain the moments.

As a check, let’s derive some of the other relations in Speicher from those above.

\displaystyle O_m(O_m^{(-1)}(z))=z gives

\displaystyle O_m(O_{m}^{(-1)}(z)) \frac {1}{O_{m}^{(-1)}(z)} = z \frac{1}{O_m^{(-1)}(z)} or

\displaystyle O_m(\frac{z^2}{O_r(z)}) \frac{O_r(z)}{z^2}= \frac{O_r(z)}{z} which translates into

\displaystyle B_{Sp}(\frac{z}{A_{Sp}(z)}) = A_{Sp}(z) \; \; .

And, the reciprocal relation

\displaystyle \frac{O_r(z)}{z} = \frac{z}{O_m^{(-1)}(z)} gives

\displaystyle \frac{O_r(O_m(z))}{O_m(z)} = \frac{O_m(z)}{z} or

z \displaystyle \frac{O_r(O_m(z))}{O_m(z)} = O_m(z) \; \; , which tranlates into

z \displaystyle \; A_{Sp}(z \; B_{Sp}(z)) = z \; B_{Sp}(z) and also into

\displaystyle \frac{O_r(O_m(1/z))}{(O_m(1/z))^2} = z = \frac{A_{Sp}(G(z))}{G(z)} = \frac{1+RT(G(z))}{G(z)} .

For the Bernoulli polynomials with the moments m_n= \frac{1}{n+1} given above by the reciprocal Appell sequence,

\displaystyle O_m(z) = -\ln(1-z) and, therefore,

\displaystyle O_m^{(-1)}(z) = 1-e^{-z} = z \frac{e^z-1}{z} \; e^{-z} = z \; e^{\bar{B}.(-1)z} = \frac{z}{1+RT(z)} , so

\displaystyle RT(z)= \frac{z}{e^z-1} \; e^{z}-1 = e^{B.(1)z}-1 = \frac{z}{1-e^{-z}}-1= -z \; e^{\zeta. z} ,

where \displaystyle \zeta_n= \zeta(-n)  of the Riemann zeta function, and

\displaystyle O_r(z) =z(1+RT(z)) = z \; e^{B.(1)z} = z \; e^{-B.(0)z} = z (1-z \; e^{\zeta. \; z}) .

So, we can identify the free cumulants associated with the moments \displaystyle m_n = \frac{1}{n+1} as \displaystyle r_n = \frac{ B_n(1)}{n!} = (-1)^n \frac{B_n(0)}{n!} .

For the Bernoulli polynomials we have the extended moment o.g.f.

\displaystyle \hat{O}_m(x,z) = \ln(\frac{1-xz}{1-(1+x)z})

as discussed in the other entries on the Bernoullis and the Todd / Hirzebruch series. We can also use the translation properties of the Appells to obtain other identities with the extended o.g.f.s,  such as

\displaystyle G( \frac{1+ RT(z)}{z}) = \hat{O}_{\bar{A}}(-\frac{1}{z}, \frac{z}{RT(z)})=O_{\bar{A}}(\frac{z}{1+ RT(z)})= z .

For the extended moments m_n(x)=(m.+x)^n of \hat{O}_m (x,z) , the free cumulants can be computed by first using the refined Eulerian numbers of A145271 to obtain the inverse of the moment series and then taking the shifted reciprocal of that inverse as above. This reduces to taking the shifted reciprocal of the bivariate generating function for the Eulerian numbers of A008292 and evaluating it with x=z there and a=-x and b=-(1+x). This approach introduces the Eulerian numbers, which are the h-vectors for the simplicial duals of the permutohedra, into the analysis and geometry. As noted in the other entries here, there are associations also with Lie-Sheffers dynamical systems, the Ricatti equation, and solitons.

For an Appell umbral inverse / reciprocal pair, the moments are associated with either of the Appell sequences and the cumulants with the other. The way the formulas are written for the Bernoullis, I’ve chosen to associate the moments with \displaystyle\bar{A}.(x) and the cumulants with \displaystyle A.(x) . But note that we can dispense with probability distributions and convergence and deal with formal power series, defining the relations combinatorially between the “moments” and classical cumulants using the cumulant expansion A127671 and associated diagrammatics or between the moments and free cumulants using A134264 and diagrammatics associated with noncossing partitions. The physical interpretations are as diverse as those for the heat and wave equations.

The boolean cumulants are related to the reciprocal of O_{m}(x) and, therefore, to the reciprocal of the e.g.f. e^{m. \; x}   (determined by the combinatorics of permutohedra and surjections, A133314) for the Appell umbral compositional inverse sequence.

The partition polynomials of the inversion formula A134264 can be derived from those of A133437 for the inversion of o.g.f.s, governed by the combinatorics of the Stasheff associahedra, or their simplicial duals, by replacing the indeterminates in those polynomials with the partition polynomials associated to reciprocals of e.g.f.s, A133314, governed by the combinatorics of permutohedra, or their duals, with the indeterminates of the initial o.g.f. to be inverted appropriately scaled to suit those for an e.g.f., so in some sense the final inversion formula is a composition of the associahedra with the permutohedra, i.e., NCpart= Assoc(Permut(factorial)).

Let’s look at some relations among the Catalan and Fuss-Catalan numbers and associated moments and free cumulants. Choose

O_m^{(-1)}(x,t;n) = x - t \cdot x^{n+1} .

Then n=1 gives the o.g.f. for the associated moments as that for the Catalan numbers, i.e.,

O_m(x,t;1) = [\; 1 - \sqrt{1-4tx} \; ] / 2t = x + t x^2 + 2 \; t^2 x^3 + 5 \;t^3 x^4 + \cdots , and

1+ RT(x,t;1) = x / O_m^{(-1)}(x) = 1 / (1 - tx) = 1 + tx + (tx)^2+ \cdots ,

so the free cumulants and weights for the noncrossing partitions to generate the moments are

r_k(t;1) = t^k= h_k .

For n > 1 ,  the o.g.f.s for the moments are those for the Fuss-Catalan numbers with associated free cumulants and weights for the noncrossing partitions given by

1 +RT(x,t;n) = 1 / (1 - tx^n) = h(x) .

See the notes “Discriminating deltas, depressed equations, and generalized Catalan numbers” in the previous entry “Depressed equations, … ” for more info on the Fuss-Catalan numbers.

References, links, and related stuff:

“Multiplicative functions on the lattice of non-crossing partitions and free convolution” by R. Speicher

“Free probability theory and non-crossing partitions” by R. Speicher

“Appell polynomials and their relatives” by M. Anshelevich

“Combinatorics of free probability theory” by R. Speicher

“Formal groups, Witt vectors and free probability” by Friedrich and McKay

“The Fuss-Catalan numbers in noncommutative probability” by Mlotkowski

“Free probability theory: random matrices and von Neumann algebras” by Voiculescu

The Semicircle Law, Free Random Variables, and Entropy by Hiai and Petz

“Modular matrix models” by Yang-hui He and Vishnu Jejjala

“Modular matrix models and monstrous moonshine” by Yang-hui He

“From Boltzmann to random matrices and beyond” by Chafai

“Mastering the master field” by Gopakumar and Gross

“Stochastic master fields” and “Large N-gauge theory — expansions and transitions” by M. Douglas

“Motives from diffraction” by Stienstra

This entry was posted in Math and tagged , , , , , , , , , , , , , , , , . Bookmark the permalink.

2 Responses to Appell polynomials, cumulants, noncrossing partitions, Dyck lattice paths, and inversion

  1. Tom Copeland says:

    Also “On the large N limit of the Itzykson-Zuber Integral” by Matytsin.

    The derivation of the compositional inverse relation between the moment generating function M(z) and the resolvent on page 14 of “Mastering the master field” in terms of complex contour integrals provides a rationale for the introduction of a 1/z term to M(z) and the expansion of the resolvent in the reciprocal powers of 1/z.

  2. Tom Copeland says:

    See also “Free probability, random matrices, and the
    enumeration of maps” by Guionnet, “Free Probability and Random Matrices” by Mingo and Speicher, and “Complete diagrammatics of the single ring theorem” by Nowak and Tarnowski.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s