Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Operads of (noncrossing) partitions, interacting bialgebras, and moment-cumulant relations

Operads of (noncrossing) partitions, interacting bialgebras, and moment-cumulant relations We establish and explore a relationship between two approaches to moment-cumulant relations in free probability theory: on one side the main approach, due to Speicher, given in terms of Möbius inversion on the lattice of noncrossing partitions, and on the other side the more recent non-commutative shuffle-algebra approach, where the moment-cumulant rela- tions take the form of certain exponential-logarithm relations. We achieve this by exhibiting two operad structures on (noncrossing) partitions, different in nature: one is an ordinary, non-symmetric operad whose composition law is given by insertion into gaps between ele- ments, the other is a coloured, symmetric operad with composition law expressing refinement of blocks. We show that these operad structures interact so as to make the corresponding incidence bialgebra of the former a comodule bialgebra for the latter. Furthermore, this interaction is compatible with the shuffle structure and thus unveils how the two approaches are intertwined. Moreover, the constructions and results are general enough to extend to ordinary set partitions. Contents 1 Introduction 2 2 Partitions and noncrossing partitions — notation and conventions 5 2.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 arXiv:1907.01190v4 [math.CO] 16 Apr 2020 3 Gap-insertion operad and associated structures 7 3.1 A non-symmetric single-colour operad of partitions . . . . . . . . . . . . . . . . . 8 3.2 Induced brace algebra structures . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.3 Induced bialgebras and Hopf algebras . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.4 Unshuffling coproducts on partitions . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.5 Moments and cumulants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 4 Block-substitution operad and associated structures 19 4.1 A coloured symmetric operad of compositions . . . . . . . . . . . . . . . . . . . . 19 4.2 Induced bialgebras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 4.3 Comparison with the lattice approach and Möbius inversion . . . . . . . . . . . . 24 5 Comodule bialgebra, half-shuffle exponentials and Möbius inversion 27 5.1 Comodule bialgebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 5.2 Four bijections from infinitesimal characters to characters . . . . . . . . . . . . . 30 5.3 Description of the universal maps ψ , ψ and ψ . . . . . . . . . . . . . . . . . . 34 ≺ ≻ ⋆ 5.4 On the inverses of the universal maps . . . . . . . . . . . . . . . . . . . . . . . . . 36 5.5 On the inverse of the “free” universal map ψ . . . . . . . . . . . . . . . . . . . . 38 Keywords: operads; set partitions; noncrossing partitions; Möbius inversion; free probability; moment-cumulant relations; combinatorial Hopf algebra; unshuffle bialgebra; interacting bialgebras; shuffle algebra. MSC Classification: 16T05; 16T10; 16T30; 18M60; 46L53; 46L54. 1 Introduction One of Rota’s main motivations for developing the now ubiquitous machinery of incidence alge- bras and Möbius inversion [35] was to provide a clean combinatorial explanation of the moment- cumulant relations in classical probability, known already to involve the Bell numbers (see for example [25]). The idea is that both moments m and cumulants c (of a fixed random variable) are considered as linear forms on the incidence coalgebra of the lattice of set partitions, and that the relationships amount to convolution with the zeta function and its inverse, the Möbius function of the lattice (see also Speed [39]): m = ζ ∗ c c = µ ∗ m. More generally, Rota’s seminal paper with Wallstrom [36] showed that many of the basic aspects of stochastic analysis can be rendered combinatorially in terms of the lattice of set partitions. A beautiful extension of Rota’s ideas was found by Speicher [40, 41] to account for the relationship between moments and free cumulants in the setting of Voiculescu’s theory of free probability [42]. Speicher showed that the free moment-cumulant formulae follow the same pattern as the classical case if just the lattice of set partitions is replaced by the lattice of noncrossing partitions [34]. Beyond the importance of this in the context of free probability (see also Biane [3, 4]), it is as well a striking new application of the combinatorial topic of noncrossing partitions , which is also important in exploring the interface between algebraic geometry and representation theory (see for example the recent survey [2]), and which comes up in numerous other contexts [33, 38]. Recently, two of the present authors proposed a different approach to moment-cumulant rela- tions [11, 12, 14, 13], which is not based on the lattice of noncrossing partitions, incidence algebras or Möbius inversion. Instead, it employs a certain non-commutative shuffle algebra and consid- ers moments and free cumulants as images of a particular Hopf algebra character, respectively Kreweras’ 1972 paper “Sur les partitions non croisées d’un cycle” [27] initiated the study of noncrossing partitions in combinatorics. 2 infinitesimal character. Moment-cumulant relations are encoded through exponential-logarithm correspondences implied by fixpoint equations involving so-called half-shuffle products ≺ and ≻. For instance, in the free case the moment character φ and the free cumulant infinitesimal char- acter κ are related through a half-shuffle fixpoint equation in non-commutative shuffle algebra φ = ε + κ ≺ φ, where ε is the counit. The shuffle-algebra approach supports a Lie theoretic perspective, which is augmented by the notions of pre-Lie and, more generally, brace algebra [7]. The motivation for the present work was to uncover the relationship, hitherto completely mysterious, between the two approaches to moment-cumulant formulae. The general framework found to accommodate the two disparate approaches is the theory of operads and their incidence bialgebras. In a nutshell we show that the two approaches are governed each by their particular operad of noncrossing partitions; we then show how these two operads interact at the level of the corresponding bialgebras, and derive comparisons between the two settings in terms of this interaction. Somewhat surprisingly, the framework turns out to be general enough to cover also the case of ordinary set partitions. Here, too, there exists a pair of interacting operads. As a consequence we obtain in this case as well a close connection between the Möbius-theoretic moment-cumulant relations à la Rota, and the (little studied) shuffle-algebraic approach in that context. In the following summary we concentrate on the case of noncrossing partitions, since this was our original motivation and central aim. The first operad is an ordinary nonsymmetric operad of noncrossing partitions, where each noncrossing partition of degree n is considered an (n + 1)-ary operation. The composition law for this operad consists in inserting n + 1 noncrossing partitions into the gaps of a noncrossing partition of degree n. This includes the “outer gaps”, i.e., in front of the whole partition and at the end of it. To any operad is associated a bialgebra (see [16] and [21]), sometimes called its incidence bialgebra, which always has the feature of being “right-sided”, meaning that the coproduct is linear in the left-hand tensor factor but gives monomials in the right-hand tensor factor. We show that this bialgebra is an unshuffle bialgebra (also called codendriform bialgebra), and that the resulting fixpoint equations in the graded dual of the bialgebra are analogous to those of [11]. The second operad is a coloured symmetric operad, whose colours are the positive integers. If a noncrossing partition has k blocks, then it is considered a k-ary operation. The colour of each input slot is the number of elements in the block, and the output colour of the operation is the total number of elements. The composition law for this operad works by substituting a noncrossing partition for a block with the same number of elements. The resulting effect is thus to refine partitions. The incidence bialgebra corresponding to this operad is shown to be closely related to the incidence coalgebra of the lattice of noncrossing partitions in an interesting way: there is a canonical coalgebra homomorphism Φ : B → B from the incidence coalgebra of lat opd the lattice of noncrossing partitions to the incidence bialgebra of the operad. Intervals in the lattice are type equivalent (in the sense of Speicher [40]) precisely when they have the same image under Φ. Möbius inversion in B is induced from that in B , but the latter is closer to what is lat opd actually used in free probability, since it works with the noncrossing partitions themselves instead of intervals of noncrossing partitions. Because of this we can now forget about the lattice, and work directly with the incidence bialgebra of the (block-substitution) operad. The two bialgebras of noncrossing partitions induced by the two operad structures have essentially the same multiplicative basis, both being free on the set of noncrossing partitions. The key point of this work, which allows for the comparison envisaged, is that these two bialgebra structures together form a comodule bialgebra. This is an intricate structure of two interacting bialgebras which recently has appeared in numerical analysis [6], local dynamical systems [10], and stochastic integration and renormalization [5]. Precisely, in Theorem 5.1.1 we establish 3 that the gap-insertion bialgebra is an unshuffle-type bialgebra object in the symmetric monoidal category of comodules for the block-substitution bialgebra. In particular, the block-substitution bialgebra coacts on the gap-insertion bialgebra by bialgebra homomorphisms. An immediate consequence of this is that the convolution algebra of the block-substitution bialgebra acts on the shuffle algebra, i.e., the convolution algebra of the gap-insertion bialgebra. An attractive feature is now that this action is compatible with the splitting of the shuffle product into half- shuffles (Theorem 5.1.2), and therefore with the fixpoint equations mentioned above. Finally the distinguished character (solution to a fixpoint equation) can be convolution-inverted (to provide shuffle logarithms). These can be computed by Möbius-inversion style formulae. Throughout we emphasize noncrossing partitions, since this was our original motivation, but in fact the theory we develop is general enough to cover also the case of ordinary set partitions, so as to get analogous formulae also for classical cumulants. A subtle point for this to work is the Galois connection between the lattice of set partitions and the lattice of noncrossing partitions, which is used to transfer certain noncrossing features to the setting of ordinary partitions, and which also leads to some direct comparisons between classical and free cumulants. In particular this involves the nesting preorder of a partition, and the notions of lowersets and uppersets for partitions. Impetus for this project came from more abstract work by two of the present authors, con- cerned with general relationships between operads and combinatorial Hopf algebras (and bialge- bras). Foissy [17] developed a theoretical framework allowing to understand how quite generally operads equipped with certain B -actions induce comodule bialgebras. In a different line of investigation, Gálvez, Kock and Tonks, in a series of papers starting with [20], developed the notion of decomposition spaces, a general homotopical framework for incidence algebras and Möbius inversion, revealing many classical combinatorial Hopf algebras to be incidence algebras (but not of posets). (This framework covers also operads, via their two-sided bar constructions.) The use of comultiplications to describe convolution products (in combinatorics) goes back to Rota [35]. The importance of Hopf algebra structure rather than just coalgebra structure was stressed by Schmitt [37]. In the more specific context of non-commutative probability theory, various authors have recently exploited Hopf algebras from different perspectives. We briefly mention the works of Friedrich–McKay [18], Hasebe–Lehner [23], Mastnak–Nica [32], Gabriel [19], and Manzel–Schürmann [31]. The precise relations to [11, 12, 14, 13] are not yet fully understood. Operadic approaches to moment-cumulant formulae have been exploited in other ways in recent years. Josuat-Vergès, Menous, Novelli, and Thibon [24] studied the (free) operad of Schröder trees to obtain an operadic version of the half-shuffle equations of Ebrahimi-Fard and Patras [11], and also related this to Speicher’s original formulae [40]. They do not, however, consider operad structures directly on noncrossing partitions. Proposition 3.1.4 below gives an explicit presentation of our gap-insertion operad in terms of generators (corolla trees) and relations, premonished by the way Schröder trees are shown to encode noncrossing partitions in [24]. Their encoding becomes an operad map from the Schröder operad to our gap-insertion operad of noncrossing partitions. A different operadic viewpoint on free moment-cumulant relations was taken by Drummond- Cole [8, 9], who gave an operadic interpretation of Speicher’s multiplicativity [40], and exhibited the free moment-cumulant relations in terms of convolution of maps from a cooperad to an endo- morphism operad. Again, the operads and cooperads considered are not directly on noncrossing partitions, but rather on auxiliary classes of decorated trees. Finally we mention the traffic spaces of Male [29]; these are defined as algebras for a cer- tain operad of graph operations. While this is a very general framework, the operad of graph operations does not seem to specialize directly to any of the main constructions of the present work. Acknowledgments: We would like to thank G. Drummond-Cole, F. Lehner, and R. Speicher for fruitful discussions. This research project received financial support from the CNRS Program 4 PICS 07376: «Algèbres de Hopf combinatoires et probabilités non commutatives». We also thank the Centre de Recerca Matemàtica (CRM) in Barcelona for its hospitality. J.K. was supported by grants MTM2016-80439-P (AEI/FEDER, UE) of Spain and 2017-SGR-1725 of Catalonia. This work was partially supported by the project Pure Mathematics in Norway, funded by Bergen Research Foundation and Tromsø Research Foundation and by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation program (grant agreement No.670624). 2 Partitions and noncrossing partitions — notation and conven- tions This section introduces notation and conventions and briefly recalls some basic notions related to set partitions. 2.1 Definitions 1. We denote by K a commutative base field of characteristic zero. All algebraic objects in this work, such as vector spaces, algebras, coalgebras, pre-Lie algebras, etc., will be defined over K. For algebras with an augmentation ε : A → K, we write A := Ker ε for the augmentation ideal. 2. By N we denote the linearly ordered set of non-negative integers, and by N the set of positive integers. For n ∈N , we denote by [n] the set {1, 2, 3, . . . , n} = J1, nK. For a finite subset X = {x , . . . , x } ⊂ N, we write ♯X = k for its cardinality, and we write 1 k X + n for the n-shifted subset {x + n, . . . , x + n}. Let X be a finite, linearly ordered set. A partition of X into disjoint subsets π , i = 1, . . . , k (called blocks) is written P = {π , . . . , π }. If the order on the set of blocks matters we will write 1 k it as a sequence, (π , . . . , π ), and call it a composition instead of a partition. The degree of the 1 k partition or the composition is the cardinality of X. Except when otherwise stated, partitions are ordered by coarsening: P ≤ Q means that P is finer than Q. For the purposes of this paper, it is important to require a linear order on all underlying sets that are partitioned. Many notions (in particular the notion of noncrossing partition) depend crucially on this linear order, but do not depend on the specific underlying set. This is to say we are only interested in set partitions up to isomorphism. An isomorphism between two partitions is a monotone bijection of the underlying linearly ordered sets compatible with the block structure (and for compositions also with the order on the set of blocks). It is clear that every partition (or composition) is uniquely isomorphic to one with underlying linearly ordered set [n] = {1, 2, . . . , n}, for some n ∈ N. These are called standard partitions, and the process of replacing a partition with this standard representative of its isomorphism class (iso- class) is often called standardization. It is convenient most of the time to work with the standard representatives of each class. When non-standard representatives arise in the constructions (such as when considering subsets of [n]), it must be remembered that it is only the isomorphism class that matters. Working with iso-classes rather than restricting to standardized partitions gets us closer to the combinatorial intuition conveyed by the common pictorial representation of set partitions by block diagrams exploited throughout. (Standardization could always be performed as desired for convenience, but does not affect the validity of the constructions.) The terminology is by analogy with integer compositions: a composition of an integer n is a sequence of non-zero integers (n , . . . , n ) such that n = n + · · · + n . 1 k 1 k 5 ∗ For k, n ∈ N , we denote by SP(k, n) the set of iso-classes of partitions of n-element sets into k blocks. The set SP(0, 0) contains only the empty partition. We put: G G SP = SP(k, n), SP(n) = SP(k, n), SP = SP(0, 0)⊔ SP . 1≤k≤n k≤n When referring to a member of any of these sets, we shall always pick the standard representative, having underlying set [n]. Given a monotone inclusion of linearly orderd sets X ⊂ Y , and given a partition P = {π , . . . , π } of Y , we write P for the induced partition of X (whose blocks are the non-empty 1 k |X intersections π ∩ X). Definition 2.1.1. Let X be a non-empty, finite subset of N (or of an arbitrary linearly ordered set Y ). The convex hull of X is by definition Conv(X) = Jmin(X), max(X)K. We shall say that X is convex if Conv(X) = X. Any finite subset X ⊂ N decomposes uniquely as X = X ⊔···⊔ X 1 k with each X convex and each X ⊔X not convex for i 6= j. The X , . . . , X are called the convex i i j 1 k components of X. Definition 2.1.2 (Noncrossing partitions). A partition P = {π , . . . , π } is called noncross- 1 k ing when there are no a, b ∈ π , c, d ∈ π with i 6= j such that a < c < b < d. For example, i j {{1},{2, 4},{3}} = is noncrossing, whereas {{1, 3},{2, 4}} = is crossing. For k, n ∈ N , we denote by NCP(k, n) the set of iso-classes of noncrossing partitions of an n-element set into k blocks. The set NCP(0, 0) contains only the empty partition. We put: G G NCP = NCP(k, n), NCP(n) = NCP(k, n), NCP = NCP(0, 0)⊔ NCP . 1≤k≤n k≤n Note that if X ⊂ [n] and P is a noncrossing partition of [n] then P is a noncrossing partition |X of X. Definition 2.1.3 (Noncrossing closure). The noncrossing closure of a set partition P = {π , . . . , π } of degree n, written nc(P ), is the noncrossing partition defined by 1 k nc(P ) := min{Q ∈ NCP(n) | P ≤ Q}. Here P ≤ Q means that P is finer than Q. In plain words, nc joins any two blocks that cross. For example, nc( ) = . Anticipating the two operads that we will define on partitions, we note that nc preserves the degree of a partition. It will therefore be useful in connection with the gap-insertion operad. In contrast, it does not preserve the number of blocks, and for this reason will not play any role for the block-substitution operads. Remark 2.1.4. Throughout this paper we work with “naked” partitions, like the ones intro- duced above. However, we wish to stress that all the constructions and results go through with partitions decorated by elements from an alphabet A. By this we mean that each partition — with underlying linearly ordered set X, say — is equipped with a map a : X → A (not required to be injective), pictured as a a 2 3 a a 1 4 6 These decorations do not interfere with any of the operations we shall perform on partitions. For example, a decoration transfers canonically along monotone bijections (such as standardization): if X → A is a decoration, and [n] → X is the unique monotone bijection performing the standardization, then the decoration of the standardized partition is simply the composite map [n] → X → A. The decorated situation is relevant in probability theory where the a will be random variables. Since such decorations do not interfere with the theory we develop, for the sake of simplicity we prefer to stick with “naked” partitions, which can be regarded the univariate case, that is, of a single random variable. The only place where we shall need to refer to decorations is in Proposition 5.2.6 where we comment on relations with the double tensor algebra (over a probability space A). 3 Gap-insertion operad and associated structures We describe here a series of algebraic structures on set partitions arising from the idea of “inserting a partition into another partition”. We start with the basic insertion operation, naturally encoded by an operad structure, and then turn to the definition of further associated algebraic structures on partitions, such as unshuffle coproducts and Hopf algebras. In order to give an explicit combinatorial description of the bialgebra structure resulting from the operad, we exploit a preorder on the set of blocks of a given partition, and the attendant notions of lowerset and upperset. These notions are quite standard in the context of noncrossing partitions, but less so for general partitions — it is indeed tailored to study the relations between the two settings. Before presenting the gap-insertion operad, we briefly recall that a non-symmetric, single- coloured set operad P is a sequence of sets P(n), n ∈ N, equipped with a unit operation I ∈ P(1) and a composition law: P(r) × (P(n )×···×P(n )) → P(n +··· + n ) 1 r 1 r (p, (q , . . . , q )) 7→ p◦ (q , . . . , q ), 1 r 1 r for r ∈ N and n , . . . , n ∈N, satisfying the axioms 1 r I ◦ (q) = q, p◦ (I, . . . , I) = p, and 1 1 r r 1 1 r r p◦ (q , . . . , q ) ◦ (h , . . . , h , . . . , h , . . . , h ) = p◦ q ◦ (h , . . . , h ), . . . , q ◦ (h , . . . , h ) . 1 r 1 r 1 n 1 n 1 n 1 n 1 r 1 r An operad P is reduced if P(0) = ∅, that is, it has no nullary operations. Equivalently, an operad can be defined using the notion of “partial composition law” ◦ : P(m)×P(n) → P(m + n− 1), i = 1, . . . , m, where p◦ q := p◦ (I, . . . , I, q, I, . . . , I), with q located in position i. A set operad gives rise to an operad in the category of vector spaces by replacing sets by the vector spaces they span, and cartesian products of sets by tensor products of vector spaces. The term positive operad is also used [1]. 7 3.1 A non-symmetric single-colour operad of partitions The idea of the notion of gap-insertion operad on partitions, which we proceed to define, is easy (when displaying a partition pictorially): each partition P ∈ SP(n) (or noncrossing partition P ∈ NCP(n)) is considered an operation of arity n + 1, its input slots being the n + 1 gaps between the elements, including the “gap” before 1 and the “gap” after n. It can thus receive n + 1 other partitions (or noncrossing partitions) Q , . . . , Q , which are simply inserted into 1 n+1 the gaps. For example, inserting the partition {{1, 2}} between 2 and 3 into {{1, 2, 3}} gives the partition {{1, 2, 5},{3, 4}} and reads pictorially: ⋄ = where ⋄ denotes the partial composition law. Conceptually it is clear that this defines an operad. Formalising it just requires appropriate reindexing of the elements in the underlying sets. If P is noncrossing and Q , . . . , Q are all noncrossing, then it is clear that the result is again 1 n+1 noncrossing (as in the example just given). It is simpler to describe the operad structure from the partial composition law viewpoint: Definition 3.1.1 (The gap-insertion operad). We set SP(n) := SP(n − 1), in particular, SP(0) = ∅ (so that the operad will be reduced) and SP(1) = {∅}; the empty partition will be the operad unit. This sequence of sets is given a unital non-symmetric operadic structure as follows: for P = {π , . . . , π } ∈ SP(m) and Q = {ρ , . . . , ρ } ∈ SP(n), we define the partial 1 k 1 l composition law (for i = 1, . . . , m) by: P ⋄ Q := {χ(π ), . . . , χ(π ), ρ + i− 1, . . . , ρ + i− 1}, i 1 k 1 l where χ(p) := p if p < i, χ(p) := p + n − 1 else. Equivalently: given a sequence of partitions P ∈ SP(m), Q ∈ SP(n ), . . . , Q ∈ SP(n ), the composition law is 1 1 m m P ⋄ Q := γ(P )∪ Q ∪ Q + n ∪···∪ Q + n +··· + n , (1) 1 2 1 m 1 m−1 where γ(i) := n +··· + n . 1 i Example. 1) {1, 2, 3} ⋄ {1};{2} = {1, 2, 5};{3};{4} . Pictorially: ⋄ = 2) {1, 2, 3} ⋄ {1};{2, 3} , {1, 2} , {1};{2} , {1, 2, 3, 4} = {1};{2, 3};{4, 7, 10};{5, 6};{8};{9};{11, 12, 13, 14} . Pictorially: ⋄ ( , , , ) = As already observed, the set of noncrossing partitions is stable under the composition law of the operad SP: Lemma 3.1.2. The sequence NCP(n) := NCP(n− 1), equipped with the composition law ⋄, defines a set operad called the noncrossing gap-insertion operad. 8 Since the composition laws ⋄ of the two operads SP and NCP work by insertion into gaps, and since neither the inclusion nor the noncrossing closure operator (see 2.1.3) changes those gaps, the following is straightforward to check: nc Lemma 3.1.3. Both maps NCP SP induce morphisms of operads, nc NCP SP, exhibiting NCP as a retract of SP. The noncrossing gap-insertion operad admits the following simple presentation in terms of generators and relations. Proposition 3.1.4. For any n ≥ 2, we put p = {[n − 1]} ∈ NCP(n). Then the operad (NCP,⋄) is generated by the elements p , n ≥ 2, with the relations: ∀m, n ≥ 2, p ⋄ p = p ⋄ p . m m n n 1 m This result (and its corollary below) is not essential for later developments in this article, and we therefore limit ourselves to a short proof assuming some familiarity with the theory of operads. Proof. Firstly, for any m, n ≥ 2, p ⋄ p = {[m− 1], [n− 1]} = p ⋄ p . (2) m m n n 1 m We denote by (Q,◦) the non-symmetric operad generated by the elements q , m ≥ 2, with these relations. Classically, one represents an m-ary operation q by a corolla with m leaves, and elements of the non-symmetric operad freely generated by these elements by planar rooted trees. Since (2) holds in NCP, there exists a unique operad morphism Θ : Q −→ NCP sending q to p , for m ≥ 2. Let us prove that Θ is surjective. Let π = {π , . . . , π } ∈ NCP(k, n − 1), we prove that it 1 k belongs to Θ(Q(n)) using induction on k. If k = 1, we have π = Θ(q ). Otherwise, assume that the block containing 1 is π and that it is of cardinality l− 1. Then there exist noncrossing (2) (l) partitions π , . . . , π such that (2) (l) π = p ⋄ (I, π , . . . , π ). (i) (i) The number of blocks of π is strictly smaller than k, so for any i there exist q ∈ Q such that (i) (i) π = Θ(q ). Hence: (2) (l) (2) (l) π = Θ(q )⋄ (I, Θ(q ), . . . , Θ(q )) = Θ(q ◦ (I, q , . . . , q )). l l Since for any n, the nth component of the free non-symmetric operad generated by the elements q identifies with the set of planar rooted trees with n leaves, to obtain Q, one has to quotient by the relations m n m-1 n-1 = , so (by a simple recursion) the quotient Q(n) identifies with the set of planar rooted trees with n leaves such that for any internal vertex v, the leftmost child of v is a leaf. The number of such 1 2n−2 trees is the Catalan number cat = , so ♯(Q(n)) ≤ cat = ♯(NCP(n)). Therefore, Θ is n n n n−1 bijective. Corollary 3.1.5. NCP-algebras are vector spaces V carrying for any n ≥ 2 an n-multilinear map h−, . . . ,−i such that for any m, n ≥ 2, and x , . . . , x ∈ V : 1 m+n−1 hx , . . . , x ,hx , . . . , x ii = hhx , . . . , x i, x , . . . , x i. 1 m−1 m m+n−1 1 m m+1 m+n−1 9 3.2 Induced brace algebra structures The operad structure on SP and NCP induces various algebraic structures on the free vector spaces. The ones in this section are not directly used in this paper, but we mention them briefly, for the sake of completeness, and since a brace algebra structure on fundamental objects such as partitions or noncrossing partitions can be expected to have meaningful applications (recall that brace algebras are useful in the study of algebraic structures up to homotopy, for example on the Hochschild complex [22]). The reader is referred to [17] for details, proofs and further references. L L ⊗n + ⊗n Denote by T (V ) := V the tensor algebra over V , and by T (V ) := V its n∈N n∈N augmentation ideal. We use word notation v . . . v for the tensors v ⊗··· ⊗ v in T (V ), and 1 n 1 n ⊗0 write 1 ∈ V for the empty word. Definition 3.2.1. A brace algebra is a vector space V equipped with a linear map: {−,−} from V ⊗ T (V ) to V such that: • ∀v ∈ V, {v,1} = v. • ∀v, y , . . . , y ∈ V,∀w ∈ T (V ) : 1 k {{v, y . . . y }, w} = {v, w {y , w }w . . . w {y , w }w }, 1 k 1 1 2 3 2k−1 k 2k 2k+1 w=w ...w 2k+1 where the sum on the right runs over all decompositions of the word w as a concatenation product of (possibly empty) subwords. Brace algebras were introduced to encode the properties of composition laws in operads. In particular (see [17, Chap. 3] for a proof): Lemma 3.2.2. The vector spaces SP and NCP spanned by partitions respectively noncross- ing partitions, carry a brace algebra structure by the following operations: ∀p ∈ SP(n), p , . . . , p ∈ 1 k SP: {p, p . . . p } := p◦ (I, . . . , I, p , I, . . . , I, p , I, . . . , I), 1 k 1 k 1≤i <···<i ≤n 1 k where on the right-hand side p is located in position i . l l For example, for p = {{1, 2}}, p = {{1}}, p = {{1, 2, 3}}, we get 1 2 {p, p p } = {{2, 6},{1},{3, 4, 5}} +{{2, 3},{1},{4, 5, 6}} +{{1, 3},{2},{4, 5, 6}}. 1 2 The deconcatenation coproduct of a word n−1 Δ(v . . . v ) := v . . . v ⊗ 1 + 1⊗ v . . . v + v . . . v ⊗ v . . . v 1 n 1 n 1 n 1 i i+1 n i=1 equips T (V ) with the structure of a connected graded coalgebra. If an associative product ∗ : T (V )⊗ T (V ) → T (V ) with unit 1 equips (T (V ),∗, Δ) with the ⊗n ⊗m structure of a bialgebra and the restrictions of ∗ (on the image) to maps { , } : V ⊗V → n,m ⊗m V are null when n > 1 and m > 0, then the maps { , } : V ⊗ V → V define a brace 1,m algebra structure on V . The converse assertion is also true. Indeed, a brace algebra structure on V defines uniquely a bialgebra structure on T (V ) with these properties (the two categories are equivalent, as follows from the fact that (T (V ), Δ) is the cofree (coaugmented conilpotent) coassociative coalgebra over V in the category of connected graded coalgebras). 10 Proposition 3.2.3. The product ∗ on T (SP) (and, by restriction, on T (NCP)) is obtained from the brace operations as follows. Given a non-empty sequence of set partitions Q , . . . , Q 1 n written in word notation W = Q . . . Q , then for all P , . . . , P ∈ SP: 1 n 1 k P . . . P ∗ W := W {P , W }W . . . W {P , W }W . 1 k 1 1 2 3 2k−1 k 2k 2k+1 W =W ...W 2k+1 Remark 3.2.4. The product ∗ is a non-commutative shuffle product (also called dendriform product), meaning that it splits into two half-shuffle products (∗ =≺ + ≻): P . . . P ≺ W := {P , W }W . . . W {P , W }W , 1 k 1 1 2 2k−2 k 2k−1 2k W =W ...W 2k P . . . P ≻ W := W {P , W }W . . . W {P , W }W 1 k 1 1 2 3 2k−1 k 2k 2k+1 W =W ...W 1 2k+1 W 6=∅ that satisfy the Eilenberg–Mac Lane shuffle relations: (U ≺ V ) ≺ W = U ≺ (V ∗ W ) (3) U ≻ (V ≺ W ) = (U ≻ V ) ≺ W (4) U ≻ (V ≻ W ) = (U ∗ V ) ≻ W. (5) These constructions are functorial. In particular, the embedding of NCP into SP and its left inverse, the noncrossing closure, induce homomorphisms of brace algebras (and of the associated algebraic structures). 3.3 Induced bialgebras and Hopf algebras To any (non-symmetric) operad P (subject to suitable finiteness conditions), there is associated a canonical bialgebra, whose algebra structure is the free algebra on the set of all operations. (This is sometimes called the incidence bialgebra of the operad.) The coproduct of an operation R is defined as Δ(R) = P ⊗ Q ··· Q . 1 k R=P◦(Q ,...,Q ) In plain words, the coproduct is given by summing over all the ways R could have arisen from the composition law, and then putting the receiving operation P on the left and the monomial of all the operations fed into P on the right. This bialgebra is graded (by arity-minus-one), but is never connected, and hence not Hopf. Indeed, degree zero contains all monomials in the operad unit. But one can obtain a Hopf algebra by passing to the quotient defined by dividing out by the coideal generated by u−1 for all unary operations u. (In the cases of interest here, the only unary operation is the empty partition.) These constructions can be described in various formal ways, for example following from a general process described in [17], applied to the symmetrization of P (the constructions are ∗ ∗ denoted D and B in that article), or via the so-called two-sided bar construction, as exploited P P in [26]. There will thus be four bialgebras, of which two are Hopf: • For general set partitions: we shall denote by S the bialgebra induced by the operad SP, and by S its connected quotient. • For noncrossing partitions: we shall denote by N the sub-bialgebra of S induced by the 0 0 sub-operad NCP ⊂ SP, and by N its connected quotient (a sub Hopf algebra of S). 11 Altogether these four bialgebras fit together by bialgebra homomorphisms like this: N S 0 0 N S The Hopf algebra N associated to NCP was introduced in [12]. The arguments given there could be adapted to establish the bialgebra axioms also for the other three cases. Our aim here is to describe these bialgebras and Hopf algebras in purely elementary and combinatorial terms for the particular cases of the set-partitions operad SP and the noncrossing partitions operad NCP (in both cases with the gap-insertion composition law). As an algebra, S is the free associative algebra generated by SP : it is spanned linearly by 0 0 sequences of partitions, some of which are possibly empty. The algebra S is the free associative algebra generated by SP, identified with the quotient of S by the ideal generated by ∅− 1. As an algebra, N is the free associative algebra generated by NCP : it is spanned linearly by 0 0 sequences of noncrossing partitions, some of which are possibly empty. The algebra N is the free associative algebra generated by NCP, identified with the quotient of N by the ideal generated by ∅− 1. The products on S , N , N and S are denoted by ·. In order to describe the coproducts Δ 0 0 0 and Δ of S respectively S (they restrict to the coproducts on the bialgebra N and the Hopf 0 0 algebra N associated to NCP), we need some further preliminaries regarding partitions. Let P = {π , . . . , π } be a partition of a linearly ordered set X. The set of blocks of P carries 1 k a reflexive relation defined by declaring π→ρ to mean that Conv(π) ∩ ρ 6= ∅. In plain words, π ρ means that either ρ is nested inside π or that the two blocks cross. In the latter case we have also ρ→ π, which shows that in general the relation → is not antisymmetric. We also write P P abusively → for the transitive closure of the relation (which does not always define a poset). This preorder will play an essential role for allowing the noncrossing and general partitions to be treated on equal footing in the following algebraic constructions. Note immediately that Lemma 3.3.1. A partition P is noncrossing if and only if the associated preorder → is actually a poset (i.e. is an antisymmetric relation). The standard notions of lowerset and upperset for a preorder will be important for → , so let us recall: Definition 3.3.2 (Upperset and lowerset). An upperset of a partition P is a subset U of the set of blocks such that if π ∈ U and π ρ in P then also ρ ∈ U. In plain words, if a block is in U then all nested blocks and all blocks crossing it are also in U. Similarly, a lowerset of P is a subset L of the set of blocks such that if π ∈ U and σ→ π in P then also σ ∈ U. In plain words, if a block is in L then all englobing blocks and all blocks crossing it are also in L. Remark 3.3.3. If a partition P is noncrossing, then all its lowersets and uppersets are again noncrossing. The following is obvious (and holds in any preorder). Lemma 3.3.4. If U is an upperset of P then the complement set of blocks U is a lowerset. If L is a lowerset of P then the complement set of blocks L is an upperset. 12 Definition 3.3.5 (Cut). A cut of a partition P is a splitting of the set of blocks into a lowerset L and an upperset U. We write (L, U) ∈ cut(P ) to express this situation. Note that by Lemma 3.3.4 a cut is completely determined by specifying either a lowerset or an upperset. The following picture illustrates the notion of cut: 1 2 3 4 5 6 7 8 9 Remark 3.3.6. If P is a partition with a cut (L, U), and if π and π are two crossing blocks, then either they both belong to L or they both belong to U. Corollary 3.3.7. If two partitions have the same noncrossing closure (as in 2.1.3), then there is a natural bijection between their sets of cuts. The following more refined version of the complement L is specific to partitions, and is the key to giving a direct combinatorial description of the coproduct Δ . Lemma 3.3.8. A lowerset L of P defines canonically a list of uppersets U , . . . , U whose union is L . (Here k is the cardinality of the underlying set of ∪ π.) π∈L For the picture above, the resulting list of uppersets is ∅ · · ∅ · ∅ · · ∅ 2 3 4 8 (with monomial “dot” notation, as will be used later). Proof. Let {x , . . . , x } denote the underlying set of the lowerset L. Since the underlying set [n] 1 k of P is linearly ordered, these k points define k + 1 (possibly empty) intervals in [n], denoted D , . . . , D , where D := {y ∈ [n] | y < x } and D := {y ∈ [n] | y > x }. The intervening 0 k 0 1 k k intervals are D := {y ∈ [n] | x < y < x }. The promised uppersets are simply the restrictions i i i+1 U := P , for i = 0, . . . , k. To see that this is meaningful, note first that each D is a union i i |D of blocks of P , because the lowerset condition on L prevents the blocks in the complement from straddling any of the points x . Second, since we are inside the complement U := L , we have U = P = U , and the restriction of an upperset is an upperset. i |D |D i i Remark 3.3.9. Note that the U are either empty or are the convex components of the underlying set of U in the sense of Definition 2.1.1. Definition 3.3.10 (Gap monomial). For U an upperset, we define the gap monomial to be the monomial in S given by U := U ··· U 0 k Here, U , . . . , U is the list of uppersets defined by the lowerset U as in Lemma 3.3.8. ... We also define the reduced gap monomial U to be the class of U in S, that is, the monomial obtained from U by omitting those entries in the list that are empty partitions. This can also be characterized as the monomial of the convex components of the underlying set of U. With the concepts and notations just introduced, we can now give the following interpretation of the operadic composition law: P ⋄ (Q , . . . , Q ) = R 0 k if and only if P is a lowerset of R with complement list of uppersets Q , . . . , Q 0 k 13 This leads to a description of the coproduct in explicit combinatorial terms: Proposition 3.3.11. The coproduct of the incidence bialgebra S of the gap-insertion operad is given by Δ (P ) = L⊗ U. (L,U)∈cut(P ) Here the right-hand tensor factor is the gap monomial of Definition 3.3.10. Corollary 3.3.12. The partitions J := {{1}, . . . ,{n}} ∈ SP(n, n) generate the sub-bialgebra S in S . We refer to the finest partitions J colloquially as “forests of sticks”. Proof. This is clear, as the lowerset and upperset corresponding to a cut in a partition J are again such a partition, respectively a monomial of such partitions. Hence, the coproduct can be written Δ (J ) = J ⊗ J · ···· J . 0 n ♯L n n 0 ♯L L⊆[n] Here J is identified with the empty set. As an illustration: 1 2 3 4 5 corresponds to the tensor product ∅ · ∅ · · ∅ 1 2 5 3 4 in the coproduct Δ (J ). 0 5 Recall that the Hopf algebra S is obtained from S by quotiening by the ideal generated by ∅− 1. Proposition 3.3.13. The coproduct of the reduced incidence Hopf algebra S of the gap- insertion operad is given (for P a nonempty partition) by: ... Δ(P ) = L⊗ U. (L,U)∈cut(P ) The forest of sticks, S , form a sub Hopf algebra in S. ... Here the right-hand tensor factor U is the reduced gap monomial of Definition 3.3.10. The exact same formulae hold for the bialgebras N and N of noncrossing partitions. The sub bi- and Hopf algebras of forests of sticks are denoted N respectively N . Remark 3.3.14. With the cut formulation of the coproduct, a tight analogy with the Butcher–Connes–Kreimer Hopf algebra of rooted trees becomes clear: the way the upperset is split into a monomial is analogous to the way the crown of a tree with a cut is interpreted as a forest. In fact this is more than just an analogy: the underlying poset of a noncrossing partition is actually a forest (in the sense that for any block π, the set {σ | σ π} is a linear order), and the notion of cut is the same as that for forests. In fact: Proposition 3.3.15. The assignment sending a noncrossing partition to its underlying forest defines a bialgebra homomorphism from N to the Butcher–Connes–Kreimer Hopf algebra. 14 In fact, this bialgebra homomorphism factors through the non-commutative Hopf algebra of planar forests of [15]. These four bialgebras are N -graded: the bidegree of a partition P of [n] with k blocks is (k, n). (Note that the arity of a degree-n partition is n + 1, but that the bialgebra construction lowers the degree by 1.) Note that the bialgebras S and N are not connected: the degree zero 0 0 component is spanned by all the monomials in ∅. The coarsest partitions are ‘skew-primitive’, meaning for example Δ ( ) = ⊗∅·∅·∅·∅ + ∅⊗ . On the other hand, S and N are connected by construction (and therefore automatically Hopf algebras). For each of the four bialgebras, the counit is given by ε(P ) = 0 for any nonempty partition (or noncrossing partition). Applications in free probability of the theory of partitions and noncrossing partitions suggest to introduce another Hopf algebra map from N to S than the obvious embedding. Proposition 3.3.16. The linear map NCP −→ SP nc : P 7−→ P nc(P )=P defines a bialgebra homomorphism from N to S (and from N to S). 0 0 Proof. This follows since partitions with common noncrossing closure have isomorphic sets of cuts, cf. Corollary 3.3.7. 3.4 Unshuffling coproducts on partitions A (non-commutative) monomial of partitions will also be called a multipartition (resp. noncross- ing multipartition): these are the elements P = P ··· P ∈ S (resp. in N), where for each i ∈ [k], 1 k P is a partition (resp. a noncrossing partition) in SP(n ) (resp. in NCP(n )), n 6= 0. i i i i The set of multipartitions (resp. noncrossing multipartitions) is denoted by SMP (resp. NMP). These elements form a linear basis of S (resp. N). By multiplicativity, we define bigradings SMP(k, n) (NMP(k, n)) for all k, n ≥ 0, where k stands for the total number of blocks. The notions of upperset, lowerset, and cut defined in Subsection 3.3, extend multiplicatively to multi- partitions in a straightforward manner. For example, a lowerset of a multipartition P = P ··· P 1 k is a sequence of lowersets L of each P , written as a monomial L ··· L . i i 1 Moreover, shifting the elements of P by deg(P ), . . ., the elements of P by deg(P ) +··· + 2 1 k 1 deg(P ), such a P can be seen as a family of sets of subsets of [n + ··· + n ] = [n], these k−1 1 k subsets forming a partition of [n]. With these conventions and this identification, which will be used systematically in this section, for any P ∈ SMP or P ∈ NMP as above, the coproducts can be written Δ (P ) = L⊗ U (L,U)∈cut(P ) ... Δ(P ) = L⊗ U. (6) (L,U)∈cut(P ) Here Δ and Δ are extended multiplicatively from single partitions to multipartitions (monomials in partitions) in the usual way. As a result, since P is a multipartition (i.e. a monomial), also L is a monomial. In the right-hand tensor factors, U is itself a monomial for the same reason, and U ... (resp. U) are furthermore “monomials of monomials”, namely the product of the gap monomials (resp. reduced gap monomials), as in Definition 3.3.10. In the following we work only with Δ. 15 Definition 3.4.1 (Unshuffle structure). For any non-empty P ∈ SMP we put: ... Δ (P ) = L⊗ U, (L,U)∈cut(P ) 1∈L X ... Δ (P ) = L⊗ U. (L,U)∈cut(P ) 1∈U ... Here the L are the lowerset monomials of the multipartition P , whereas the U are the reduced gap monomials of each cut, as in Definition 3.3.10. These definitions restrict to (non-empty) noncrossing partitions. Remark 3.4.2. It follows from Remark 3.3.6 that the multiplicative extension to a map from NCP to SMP of the map nc from Proposition 3.3.16 commutes with these three operations. Proposition 3.4.3 (Unshuffle Hopf algebra structures). The two coproducts just defined, on the augmentation ideals S ⊂ S and N ⊂ N, turn S and N into unshuffle Hopf algebras (also + + called codendriform Hopf algebras [16]). In detail, these coproducts satisfy the dual of the shuffle relations (3)–(5): (Δ ⊗ Id)◦ Δ = (Id⊗Δ)◦ Δ , (7) ≺ ≺ ≺ (Δ ⊗ Id)◦ Δ = (Id⊗Δ )◦ Δ , ≻ ≺ ≺ ≻ (Δ⊗ Id)◦ Δ = (Id⊗Δ )◦ Δ . ≻ ≻ ≻ Moreover, for any x, y ∈ S , introducing Sweedler-like notation for these three coproducts: ′ ′′ Δ (x) = x⊗ 1 + x ⊗ x ≺ ≺ ′ ′′ Δ (x) = 1⊗ x + x ⊗ x ≻ ≻ ′ ′′ Δ(y) = y ⊗ 1 + 1⊗ y + y ⊗ y , we have ′ ′′ ′ ′′ ′ ′′ ′ ′ ′′ ′′ Δ (x· y) = x· y ⊗ 1 + x⊗ y + x· y ⊗ y + x · y ⊗ x + x ⊗ x · y + x · y ⊗ x · y , ≺ ≺ ≺ ≺ ≺ ≺ ′ ′′ ′ ′′ ′ ′′ ′ ′ ′′ ′′ Δ (x· y) = 1⊗ x· y + y ⊗ x + y ⊗ x· y + x · y ⊗ x + x ⊗ x · y + x · y ⊗ x · y . ≻ ≻ ≻ ≻ ≻ ≻ ′ ′ ′′ We have used Sweedler-type notations for the reduced coproducts, i.e., Δ (x) := x ⊗ x , ≺ ≺ ≺ ′ ′ ′′ ′ ′ ′′ Δ (x) := x ⊗ x and Δ (x) := x ⊗ x . ≻ ≻ ≻ Proof. We briefly comment on the coproduct (6) and its splitting, Δ = Δ + Δ , satisfying the ≺ ≻ shuffle relations. For more details the reader is referred to [12]. Starting from P ∈ SMP(k, n), with k ≥ 1 each cut (L, U) ∈ cut(P ) in the definition of the coproduct (6) corresponds to a decomposition of P into a lowerset L and an upperset U, which are the complements of each other. Recall that U and L are partitions themselves. We shall need compatible pairs of cuts, writing (L, M, U) ∈ cut (P ) for the situation where L is a lowerset of P and U is an upperset c c of P , with complements L = M ⊔ U and U = L⊔ M. (Coassociativity amounts to saying that the last two conditions are equivalent.) The shuffle identities are then checked by keeping track of the first element 1 ∈ P : ... ... (Δ ⊗ Id)◦ Δ (P ) = L⊗ M ⊗ U = (Id⊗Δ)◦ Δ (P ), ≺ ≺ ≺ (U,M,L)∈cut (P ) 1∈L X ... ... (Δ ⊗ Id)◦ Δ (P ) = L⊗ M ⊗ U = (Id⊗Δ )◦ Δ (P ), ≻ ≺ ≺ ≻ (U,M,L)∈cut (P ) 1∈M 16 X ... ... (Δ⊗ Id)◦ Δ (P ) = L⊗ M ⊗ U = (Id⊗Δ )◦ Δ (P ). ≻ ≻ ≻ (U,M,L)∈cut (P ) 1∈U ... ... (Here L is a monomial just because P is, whereas M and U are reduced gap monomials, as in Definition 3.3.10.) The compatibility between Δ , Δ and the product · follows by the ≺ ≻ multiplicative extension of Δ , Δ implied by Definition 3.4.1. ≺ ≻ Notice that the three coproducts Δ, Δ , Δ dualize respectively to the products denoted ≺ ≻ ∗ ∗ ∗,≺,≻ on S and N . It follows from Proposition 3.4.3 that the latter satisfy the shuffle + + identities (3)–(5). 3.5 Moments and cumulants In this subsection we briefly revisit the relations between classical cumulants and free cumulants in the context of free probability, a point usually addressed using the properties of the inclusion of the lattice of noncrossing partitions into the one of partitions [28]. We use freely the results of [12] and restrict the study to the case of a single free random variable; this allows us to consider solely computations with formal power series. The multivariate case can be addressed with exactly the same tools using the techniques in [12]. Recall that a classical probability space is a pair (A, ϕ) where A is a commutative ring of random variables and ϕ a unital linear form on it called the expectation. The moments of a n ∗ random variable a ∈ A are defined as m := ϕ(a ), n ∈ N . The moment-generating function is the associated exponential series E(z) := 1 + m , and the classical cumulants {c } n n n≥1 n≥1 n! are defined as the coefficients of the cumulant-generating function C(z) = c given by n≥1 n! the formulae C(z) := log(E(z)), E(z) = exp(C(z)). In free probability [34], the ring A is not necessarily commutative, and an element a ∈ A is interpreted as a non-commutative random variable. The moments are defined as in the classical case, but the free cumulants {k } are defined instead using the ordinary generating series n n≥1 X X n n M(z) := 1 + m z and K(z) := k z , n n n≥1 n≥1 related through the fixpoint formula M(z) = 1 + K(zM(z)). For various reasons (see for example [34]), it is fruitful to lift these relations to the framework of set partitions. As far as classical cumulants are concerned, the moment-cumulant relations translate into m = c , (8) n P P∈SP(n) where, for P := {π , . . . , π } ∈ SP(n), 1 k c := c . P ♯π i≤k For free cumulants, Speicher showed that one has instead m = k , (9) n Q Q∈NCP(n) where, for Q = {τ , . . . , τ } ∈ NCP(n), 1 k k := k . Q ♯τ i≤k 17 From the properties of the embedding NCP ⊂ SP, one can derive (see [28]) that k = c . Q P nc(P )=Q In other words, if k and c are extended to linear functions on NCP, respectively SP, we arrive at the following fundamental relation between free and classical cumulants k = c◦ nc , (10) where nc was defined in Proposition 3.3.16. As mentioned in the introduction, the papers [11, 13, 14] proposed an approach to the re- lations between moments and free cumulants, which is based on a non-commutative shuffle bialgebra structure [16] on the dual of a particular connected, graded, non-commutative, non- cocommutative Hopf algebra H of words constructed as the double tensor algebra from (A, ϕ). The group of characters and the corresponding Lie algebra of infinitesimal characters over this Hopf algebra can then be shown to be related by three naturally defined exponential-type maps and the corresponding logarithms. The unital linear map ϕ, which is part of the data of a non-commutative probability space (A, ϕ), induces a particular Hopf algebra character on H. One can show that the three logarithms applied to this character encode the three families of monotone, free, and boolean cumulants as infinitesimal Hopf algebra characters. This algebraic setting allows to recover many of the results and formulas in Speicher’s approach, although the lattice of noncrossing partitions plays a rather marginal role. Indeed, noncrossing partitions appear only after evaluating the Hopf algebra character corresponding to ϕ on elements of H. In [12] these results were transferred to the Hopf algebra N defined on noncrossing partitions in the following way. Define the linear form κ on N to be zero on all noncrossing multipartitions in NMP(k, n) for k > 1 and by κ([n]) := k else. Solving the half-shuffle fixpoint equation in the graded dual N : φ = ε + κ ≺ φ, (11) where ε is the counit of N (it is essentially the Kronecker delta ε (P ) := δ ), one obtains N N P,∅ a character which evaluates any noncrossing partition Q to φ(Q) = k , i.e., it maps Q to the product of cumulants for each block in Q. Therefore, the nth moment is obtained as m = φ(Q). We shall see in Proposition 5.2.5 that (11) and the sum formula for m find Q∈NCP(n) a more natural expression in terms of the bialgebra interaction we introduce in this paper. We can thus interpret Equation (11) as an algebraic lift of (9). Define now a linear form γ on S by γ(Q) := c if Q is a partition of [n] such that nc(Q) = [n], and to be zero on all other partitions and multipartitions. Since k = c , n P P ∈SP(n) nc(P )=[n] we obtain that κ = γ ◦ nc . Proposition 3.5.1. With γ defined as above, the solution ψ to the half-shuffle fixpoint equa- tion in the graded dual S ψ = 1 + γ ≺ ψ (12) is such that φ = ψ ◦ nc . (13) In particular, m = ψ(P ) and equations (12) and (13) can be interpreted as alge- P∈SP(n) braic and operadic lifts of the classical moment-cumulant formula, respectively formula (10). ∗ ∗ Proof. The proposition follows from the identity κ = γ ◦ nc and the fact that nc commutes with Δ defined in Proposition 3.4.3. 18 4 Block-substitution operad and associated structures We introduce now a second family of operads and algebraic structures on partitions and non- crossing partitions. We shall see that they are closely related to the lattice properties of the two families of partitions. Before presenting the block-substitution operad, we briefly recall that a coloured symmetric set operad P is given by: • A set of colours C; n+1 • For each n ∈ N, and each (n + 1)-tuple of colours (c , . . . , c ; c) ∈ C , a set of n-ary 1 n operations P(c , . . . , c ; c); 1 n • For each colour c ∈ C, an identity operation id ∈ P(c; c); • An operadic composition law P(c , . . . , c ; c) × P(d , . . . , d ; c )×···×P(d , . . . , d ; c ) 1 k 1,1 1,i 1 k,1 k,i k 1 k P(d , . . . , d , . . . , d , . . . , d ; c) 1,1 1,i k,1 k,i 1 k denoted (p, (q , . . . , q )) 7−→ p◦ (q , . . . , q ), 1 k 1 k n+1 • For each n ∈ N, for each (c , . . . , c ; c) ∈ C , and for each permutation σ ∈ S , a map 1 n n P(c , . . . , c ; c) → P(c , . . . , c ; c) 1 n σ(1) σ(n) denoted P 7→ P . This data is subject to axioms completely analogous to the ordinary operad axioms: there is an associative axiom, a unit axiom (for each identity operation), and a symmetry axiom. It is simply a typed version of the notion of operad, where the composition law requires strict type-checking in terms of colours: an operation can be substituted into an input slot of another operation if and only if its output colour matches the colour of the receiving input slot. A coloured operad P is reduced if it has no nullary operations. Example 4.0.1. A small category is the same thing as a coloured operad with only unary operations. The objects are then the colours, and the arrows are the operations (with domain as input colour and codomain as output colour). 4.1 A coloured symmetric operad of compositions Central objects in this work are the block-substitution operads SC of set partitions and NCC of noncrossing partitions, which we define in this subsection. They are both coloured symmetric operads with colour setN . We concentrate here on the ordinary partitions, since the noncrossing condition is orthogonal to the constructions, cf. Proposition 4.1.2 below. The idea is simple: a (non-empty) partition P = {π , . . . , π } with k blocks is considered a k- 1 k ary operation. Its output colour is the number of elements of the underlying set [n]. Each block π is considered to be an input slot of arity n = ♯π , and into it one can substitute any partition Q i i i of [n ] by replacing the block with the partition Q (under the unique order-preserving bijection i i between [n ] and the underlying set of π ). The effect of the substitution is thus to refine the i i partition, while leaving fixed the total number of elements n. The identity operations are clearly the single-block partitions I , since substituting such a partition into a block of size n does not refine it further. 19 To actually implement this idea and make it fit the formal definition, it is necessary to number the blocks, so as to know in which order the input slots come, and where to substitute given inputs. For this reason, the operations will have to be set compositions rather than set partitions, and the actions of the symmetric groups required for symmetric operads will then simply be renumbering of the blocks. This is a standard procedure in the construction of symmetric operads. Definition 4.1.1. A set composition is a set partition equipped with a numbering of its blocks. Equivalently, it is given by a list of blocks P = (π , . . . π ) rather than a set of blocks. 1 k We denote by SC(k, n) the set of iso-classes of compositions of an n-element set into k blocks, that is, sequences C = (π , . . . , π ) such that P = {π , . . . , π } is a partition. This includes the 1 k 1 k case SC(0, 0) = {∅}, consisting only of the empty composition. We also put: G G SC = SC(k, n), SC(n) = SC(k, n), SC = SC(0, 0)⊔ SC. 1≤k≤n k≤n Similarly, a noncrossing composition is a noncrossing partition with a numbering of its blocks. We denote by NCC(k, n) the set of iso-classes of noncrossing compositions of an n-element set into k blocks, that is, sequences C = (π , . . . , π ) such that P = {π , . . . , π } is a noncrossing 1 k 1 k partition. We put: G G NCC = NCC(k, n), NCC(n) = NCC(k, n), NCC = NCC(0, 0)⊔ NCC. 1≤k≤n k≤n We can now specify the data of the operad SC of set partitions (which should more precisely be called of set compositions): • The set of colours is the set of positive integers N ; • For fixed n , . . . , n , n ∈ N , we denote by SC(n , . . . , n ; n) the set of set compositions of 1 k 1 k [n], say C = (π , . . . , π ), such that ♯π = n for each i ∈ [k]. (Note that if n 6= n +···+n , 1 k i i 1 k then SC(n , . . . , n ; n) = ∅.) A given composition P = (π , . . . , π ) of [n] is thus regarded as a k-ary operation of output colour n, and input colour-list (♯π , . . . , ♯π ). 1 k • The identity operations are by definition the coarsest compositions, i.e., single blocks of n elements, I ∈ SC(n; n), for each n ≥ 1. • The actions of the symmetric groups S are given by permutation of blocks: for P = (π , . . . , π ) ∈ SC(n , . . . , n ; n) and σ ∈ S : 1 k 1 k k P = (π , . . . , π ) ∈ SC(n , . . . , n ; n). σ(1) σ(k) σ(1) σ(k) (That is, σ acts by renumbering blocks.) • The composition law onSC is given as follows. For any P = (π , . . . , π ) ∈ SC(n , . . . , n ; n) 1 k 1 k and a list of compositions (Q , . . . , Q ) with Q = (τ , . . . , τ ) ∈ SC(m , . . . , m ; n ), 1 i i,1 i,1 i k i,l i,l i i we define: P ◦ (Q , . . . , Q ) := (τ , . . . , τ , . . . , τ , . . . , τ ). 1 k 1,1 1,l k,1 k,l This requires reindexing: implicitly we are transporting the set-composition structure of each Q on [n ] along the unique monotone bijection [n ] π ⊂ [n]. i i i i Checking that these data constitute indeed a coloured symmetric operad SC is a straightforward, but rather cumbersome, routine exercise. The only difficulty is index bookkeeping. 20 Proposition 4.1.2. The composition law preserves noncrossing compositions. In particu- lar, the same definitions as above, but using only noncrossing compositions, defines a (coloured symmetric) operad NCC of noncrossing compositions. Proof. For any application of the composition law, say P ◦ (Q , . . . , Q ), assume that all of P 1 k and Q are noncrossing. We assume the notation from above. Consider two blocks τ and τ of P ◦ (Q , . . . , Q ). These blocks τ and τ are essentially blocks of some of the Q , but shifted 1 k i around according to the identifications made. If τ and τ originate in the same Q , then they were noncrossing in Q , and since the shifting into block π is effectuated by a monotone bijection i i [n ] → π ⊂ [n], this clearly preserves the noncrossing condition. If the two blocks τ and τ i i originate in distinct compositions Q and Q , then they are mapped into distinct blocks π and i j i π of P , and since π and π do not cross in P , a block of a refinement of π cannot cross a block j i j i of a refinement of π . In either case we see that τ and τ do not cross in P ◦ (Q , . . . , Q ). j 1 k Example. {1, 5, 6};{2, 3, 4};{7, 8, 9, 10, 11} ◦ ({{1};{2, 3}), ({1, 3};{2}), ({1, 2, 5};{3, 4}) = ({1};{5, 6};{2, 4};{3};{7, 8, 11};{9, 10}). Graphically: 2 2 3 6 4 6 1 3 1 2 1 1 2 5 1 3 2 5 ◦ , , = = . Here the numbers indicate the block numbering that makes a partition into a composition. Remark 4.1.3. The axioms force us to exclude the colour 0 and the empty composition. The only composition of ∅ is of course the empty composition, and it has arity 0, not 1. Were we to insist on including the empty composition (as a nullary operation) we would have to give up the unit axiom. We shall return to this issue when we come to comodule bialgebras in Section 5. In particular, since every non-empty composition has at least one block, there are no nullary operations, which is to say that the operad is reduced. The following is a general construction of an ordinary operad from a coloured one, but it re- quires the setting of linear operads, i.e., operads in the symmetric monoidal category (Vect,⊗,K) instead of the category of sets. Proposition 4.1.4. Let C be a set and let P be a C-coloured linear operad. For any n ≥ 1, we put: P(n) = P(c , . . . , c ; c). 1 n c ,...,cn,c∈C Let us assume that for any (c , . . . , c ) ∈ C , the set ind(c , . . . , c ) = {c ∈ C | P(c , . . . , c ; c) 6= 1 n 1 n 1 n 0} is finite. We define a composition law on P in the following way: we consider elements b b p ∈ P(n), q ∈ P(k ) for any i ∈ [n] and put: i i Y Y p = p , q = q . c ,...,c ;c i c ,...,c ;c 1 n i,1 i,k i c ,...,c ,c∈C c ,...,c ,c ∈C 1 n i,1 i,k i Then: Y X p• (q , . . . , q ) = p ◦ (q , . . . , q ) . 1 n c ,...,c ;c c ,...,c ;c c ,...,c ;c 1 n 1,1 1,k 1 n,1 n,k n c ,...,c ,c∈C 1,1 c ∈ind(c ,...,c ), n,k 1 1,1 1,k c ∈ind(c ,...,c ) n n,1 n,k 21 b The unit of P is: Y Y I = I ∈ P(c; c) ⊆ P(1). c∈C c∈C Proof. By hypothesis on ind(c , . . . , c ), the sum defining p• (q , . . . , q ) is finite, so 1 n 1 n c ,...,c ;c 1,1 n,k the law • is well-defined. The associativity of ◦ and its compatibility with the action of the symmetric groups imply that • is associative and compatible with the action of the symmetric groups. For any p ∈ P(n): Y Y I • p = (I ◦ p + 0) = p = p, c c ,...,c ;c c ,...,c ;c 1 n 1 n c ,...,c ,c∈C c ,...,c ,c∈C 1 n 1 n Y Y p• (I, . . . , I) = p ◦ (I , . . . , I ) = p = p. c ,...,c ;c c c c ,...,c ;c n n n 1 1 1 c ,...,c ,c∈C c ,...,c ,c∈C 1 n 1 n So I is a unit of P. (Notice that in all the above constructions, products could be replaced by direct sums except for the fact that then the operad P would not have a unit since I ∈/ I .) c∈C Definition 4.1.5 (Operads of compositions). Let P be the linearization of SC or NCC, with set of colours C = N . Then, for any c , . . . , c ∈ C: 1 n ind(c , . . . , c ) = {c +··· + c }. 1 n 1 n The construction of the previous proposition can thus be applied to SC and NCC to obtain two c [ ordinary (linear) operads SC and NCC. 4.2 Induced bialgebras The general construction of a bialgebra from an operad (already invoked in Subsection 3.3) applies equally well to coloured symmetric operads P (subject to suitable finiteness conditions). As an algebra, the associated bialgebra is free on the set of all operations. The coproduct of an operation R is defined as Δ(R) = P ⊗ Q ··· Q . 1 k R=P◦(Q ,...,Q ) 1 k In plain words, the coproduct is given by summing over all the ways R could have arisen from the composition law, and then putting the receiving operation P on the left and the monomial of all the operations fed into P on the right. Like in the one-colour case, this bialgebra is graded (by arity-minus-one), but is never connected. In the present case, degree zero is spanned by the identity operations I , the single-block partitions, and for most purposes it is too drastic to divide out by those. We shall therefore mostly accept that the resulting bialgebras are not Hopf. Another “drawback” is that the general bialgebra construction yields a bialgebra spanned by compositions rather than partitions. This is an artifact of having introduced the numbering of blocks, and it is corrected easily by passing to coinvariants, meaning dividing out by the actions of the symmetric groups. Since these actions are free (because the numberings were introduced freely), this quotiening is well behaved. Although it is possible to describe these construction by hand, it is usually better to in- voke general theorems to the effect that the construction works. One general framework for the construction is described in [17], applied to single-coloured operads SC and NCC. (The construction is denoted D in that article.) With the previous notation for coloured linear operads, P(c , . . . , c ; c) is the linear dual of ⊕ P(c , . . . , c ; c) . These 1 n c ,...,c ,c∈C 1 n c ,...,c ,c∈C 1 n 22 comp comp constructions allow to define bialgebras C and B of set compositions and noncrossing compositions, and pass to coinvariants to get bialgebras C and B of set partitions and noncrossing partitions. (This composite construction is denoted D in [17].) Another general construction goes via the so-called two-sided bar construction, as exploited in [26]: to any (coloured) operad one can first assign its two-sided bar construction, which is a simplicial groupoid (see [26]). This simplicial groupoid is in fact a symmetric monoidal decomposition space in the sense of [20], and therefore admits an incidence bialgebra, which in comp comp the present two cases are C and B directly (C and B cannot be obtained in this way). (Incidence coalgebras of posets and categories are also special cases of this, and the setting allows for precise comparison results. We shall briefly touch upon this below when we compare the operad approach with the classical lattice approach (see Remark 4.3.12).) We summarize the outcome of these constructions in the following proposition, and proceed to give explicit descriptions of the structures. Proposition 4.2.1. The coloured symmetric operads SC and NCC induce four bialgebra structures and bialgebra homomorphisms: noncrossing general comp comp compositions B C partitions B C comp comp The bialgebra C is freely generated as an algebra by SC, and B is freely generated by NCC. It is the coproduct, denoted δ , which is the most interesting structure. We proceed to describe it in elementary terms. For any P , Q ∈ SC(n), recall that P ≤ Q if there exist R , . . . , R ∈ SC such that: 1 k P = Q◦ (R , . . . , R ). 1 k This is an adaptation to compositions of the usual ordering by coarsening of partitions (P ≤ Q when Q is coarser than P ). For fixed P and Q, such R , . . . , R are unique if they exist; in that 1 k comp comp comp case we put P/Q := R ··· R . We can now describe the coproduct δ : C → C ⊗C 1 k 0 explicitly. For P ∈ SC we have SC ∋ P 7→ δ (P ) = Q⊗ P/Q. P≤Q The space of invariants under the action of the symmetric groups of Vect(SC) is naturally identified with Vect(SP). Accordingly, C is the free commutative algebra generated by SP, and similarly B is the free commutative algebra generated by NCP. The coproduct δ on C is induced from δ . To describe it, further notation is required: For P , Q ∈ SP(n), we shall say that P ≤ Q if each block of Q is the union of the blocks of P it contains. This is the usual poset of partitions of degree n. Its minimal element is the finest partition J = {{1}, . . . ,{n}}, the unique element of SP(n, n), and its maximal element is the coarsest partition I = {[n]}, the unique element of SP(1, n). Denoting Q = {τ , . . . , τ }, we put 1 l P/Q = P ··· P ∈ C. |τ |τ Finally we can describe the coproduct explicitly. We have δ : C → C⊗ C, and: SP ∋ P 7→ δ(P ) = Q⊗ P/Q. (14) P≤Q The counit of C is denoted by ε ; for P ∈ SP(k, n), we have ε (P ) = δ . C C k,1 23 Remark 4.2.2. For the noncrossing case the description is exactly the same. The sum runs over noncrossing partitions Q coarser than P . This is meaningful because if P is noncrossing then for any coarser noncrossing partition Q, the restrictions P forming the monomial are |τ noncrossing as well. Example 4.2.3. We give some example computation in the case of noncrossing partitions. Since the sum defining δ is over all coarser noncrossing partitions, the coarsest partitions I are all group-like: δ( ) = ⊗ δ( ) = ⊗ δ( ) = ⊗ and the finest partitions J have the longest formulas for coproduct: δ( ) = ⊗ + ⊗ · δ( ) = ⊗ + + + ⊗ · + ⊗ · · δ( ) = ⊗ + ⊗ · + ⊗ · + ⊗ · · + ⊗ · · + ⊗ · · + ⊗ · · + ⊗ · · + ⊗ · · + ⊗ · + ⊗ · + ⊗ · + ⊗ · + ⊗ · · · . Here are a few other examples, which will be referenced later: δ( ) = ⊗ · + ⊗ δ( ) = ⊗ · + ⊗ δ( ) = ⊗ · + ⊗ δ( ) = ⊗ · · + ⊗ · + + ⊗ · + ⊗ δ( ) = ⊗ · · + ⊗ · + ⊗ · + ⊗ . 4.3 Comparison with the lattice approach and Möbius inversion The monomial P/Q appearing on the right-hand side in the coproduct formula (14) plays an important role in relating the bialgebras C and B with the incidence coalgebras of the lattices of partitions and noncrossing partitions. In this subsection, for simplicity we treat only the case of noncrossing partitions, but the whole discussion (though not the example computations) carries over to the case of general set partitions. We shall see, for example, that Speicher’s basic moment-cumulant formula given in terms of Möbius inversion in the incidence algebra of the lattice of noncrossing partitions can be rendered elegantly in the bialgebra B. Definition 4.3.1 (Fibre). Given two (noncrossing) partitions, P, Q ∈ NCP, one finer than the other, P ≤ Q, the fibre map is defined by: Φ(P, Q) := P/Q. Example: Φ , = · · . The linear dual B is an algebra under the corresponding convolution product: for two linear maps φ, ψ : B → K, the convolution product is given by (φ∗ ψ)(P ) = φ(Q)ψ(P/Q). P≤Q The neutral element for the convolution product is the bialgebra counit ε , which takes value 1 on all I (as well as on monomials in the I ) and value 0 on all other noncrossing (multi)partitions. n n 24 Recall that for any bialgebra T , the characters (algebra homomorphisms T → K) form a monoid for the convolution product: the product of two characters φ, ψ is given by φ ∗ ψ := m ◦ (φ⊗ ψ)◦ Δ . For the case of B, a character ψ is thus multiplicative, in the sense that if P K T is a commutative monomial of partitions, P = P ··· P , then ψ(P ) = ψ(P )··· ψ(P ) (and we 1 r 1 r also have ψ(1) = 1, where the argument 1 denotes the empty product, the unit element in the algebra). A basic character on B is the zeta function B −→ K ζ : P 7−→ 1. It is a general fact that the zeta function is convolution invertible; its inverse is by definition the Möbius function µ , which is again a character, determined by the following recursive formula: µ (I ) = 1 for all n > 0, µ (P ) = − µ (Q) for P 6= I . P<Q The sum is over all strictly coarser partitions or noncrossing partitions. Lemma 4.3.2. In the dual B , given a character κ, define φ := ζ ∗ κ. Then: φ(J ) = κ(J )··· κ(J ). (15) n ♯π ♯π P ={π ,...,π }∈NCP(n) Corollary 4.3.3. With k := κ(J ) = κ( ··· ) and m := φ(J ) = φ( ··· ), n n n n Equation (15) recovers the familiar free moment-cumulant relation m = k from (9). n Q Q∈NCP(n) Remark 4.3.4. Note that the moments and cumulants here are defined using the finest partitions, not the coarsest, which may surprise readers familiar with the work of Speicher [40, 34]. The contrast will be fully resolved below. Example 4.3.5. Using the above coproduct formulae and the monomial multiplicativity, we calculate for instance the second, third and fourth moments in the noncrossing case: m = φ( ) = (ζ ∗ κ)( ) = κ( · ) + κ( ) = k k + k , 1 1 2 m = φ( ) = (ζ ∗ κ)( ) = κ( · · ) + 3κ( · ) + κ( ) = k k k + 3k k + k , 1 1 1 1 2 3 m = κ( · · · ) + 6κ( · · ) + 4κ( · ) + 2κ( · ) + κ( ) = k k k k + 6k k k + 4k k + 2k k + k . 1 1 1 1 1 1 2 1 3 2 2 4 (Note that the coefficient 2 in front of k k is the first that distinguishes the case of noncrossing 2 2 partitions from the case of general set partitions, where this coefficient would be 3.) Conversely, using the recursive formula for µ , one finds quickly that µ ( ) = µ ( ) = µ ( ) = µ ( ) = 1 µ ( ) = µ ( ) = µ ( ) = µ ( ) = µ ( ) = µ ( ) = µ ( ) = µ ( ) = −1, 25 µ ( ) = µ ( ) = µ ( ) = µ ( ) = 2, but µ ( ) = µ ( ) = 1, µ ( ) = −5. Combining with the basic comultiplication table (see computations in Example 4.2.3), we get for the second, third and fourth cumulants k = κ( ) = (µ ∗ φ)( ) = µ ( )φ( · ) + µ ( )φ( ) = −m m + m , 1 1 2 k = κ( ) = (µ ∗ φ)( ) = µ ( )φ( ) + 3µ ( )φ( · ) + µ ( )φ( · · ) = m − 3m m + 2m , 3 1 2 2 2 4 k = m − 2m + 10m m − 4m m + m . 4 4 2 1 3 2 1 1 These computations are completely analogous to the calculations usually done to relate mo- ments and free cumulants in the lattice of noncrossing partitions (see for instance [34]), but they are simpler in the present framework since one can work with noncrossing partitions directly instead of working with intervals of noncrossing partitions. As observed above, it may seem disturbing that we put k := κ( ), whereas Speicher [40] puts k := κ( ), which is really n n shorthand for κ(JJ , I K) in that context (the one of the incidence algebra of the lattice). The n n reason for this is that the relationship between the noncrossing partition lattice and the bialgebra B is actually given by the assignment Φ introduced in Definition 4.3.1, which to any interval associates its fibre. Recall, e.g., from [34] that the incidence coalgebra of a lattice is the free vector space spanned by the intervals JP, QK in the lattice, and that the coproduct is given by δ (JP, QK) = JP, M K⊗ JM, QK. lat M∈JP,QK We shall actually use the opposite coalgebra, meaning that the order of the tensor factors is reversed. This opposite coalgebra we call B . For contrast, the operad bialgebra will be lat denoted B in the following discussion. opd Remark 4.3.6. We emphasize that the “opposite” occurring here is unrelated to the question we are addressing, i.e., “finer vs. coarser”. Indeed, working with the opposite coalgebra is purely a matter of convention of order of the tensor factors in the coproducts. The following result resolves the relation between the two coalgebras B and B . lat opd Proposition 4.3.7. The assignment Φ constitutes a coalgebra homomorphism B → B . lat opd Proof. This follows from the next two lemmas. The first is a standard property of noncrossing partitions, the second follows from the definition of Φ. Lemma 4.3.8. Every interval JP, QK is isomorphic as a poset to a product of intervals ending in a coarsest partition I . Precisely, JP, QK ≃ JP , I K×···× JP , I K, 1 n k n 1 k where k is the number of blocks in Q, the ith block of Q is of size n , and P is the corresponding i i partition of [n ]. Lemma 4.3.9. For any interval JP, QK, we have Φ(JP, QK) = Φ(JP , I K)··· Φ(JP , I K), 1 n k n 1 k where again k is the number of blocks in Q, and the ith block of Q is of size n , and P is the i i corresponding finer partition. 26 ∗ ∗ Corollary 4.3.10. The dual map B → B is a homomorphism of convolution algebras. opd lat Remark 4.3.11. Characters on B , say κ : B → K, induce linear forms on B , say opd opd opd lat κ : B → K such that lat lat κ (JP, QK) = κ (Φ(JP, QK)) = κ (P/Q). lat opd opd These linear forms have the special property (actually desired) that their value on an interval only depends on its canonical product splitting (i.e. its type, in the sense of Speicher). This correspondence explains the apparent discrepancy we noticed: when in the lattice setting one writes κ(I ) it is really shorthand for κ(JJ , I K), and the fibre of the interval JJ , I K is n n n n n clearly the partition J , so that κ (I ) = κ (J ), and both can be called k without conflict. n lat n opd n n Remark 4.3.12. The coalgebra homomorphism Φ should not be considered as something strange or ad hoc. In fact, it is an instance of a general phenomenon, visible in the simplicial viewpoints hinted at in the preliminary discussion in Subsection 4.2. There it was mentioned that B is the incidence bialgebra of a certain simplicial groupoid X (more precisely a monoidal opd decomposition space), obtained as the two-sided bar construction of the operad NCP. In this simplicial viewpoint, one can take upper decalage of X to find essentially the nerve of the noncrossing partitions lattice, and then the dec map Dec X → X induces precisely Φ. It is a coalgebra homomorphism for general reasons. Many examples of coalgebra homomorphisms from incidence coalgebras of posets to incidence bialgebras of operads which fit this pattern are given in [21]. Remark 4.3.13. We stress again that all the discussion in this subsection applies equally to the case of general set partitions, and in particular: the assignment Φ constitutes a coalgebra homomorphism C → C , lat opd from the –opposite– incidence coalgebra of the lattice of partitions to the incidence bialgebra of the (block substitution) operad of set partitions. 5 Comodule bialgebra, half-shuffle exponentials and Möbius in- version In the previous sections we have shown how the gap-insertion operad encodes the shuffle Hopf algebra approach to moment-cumulants relations, and that the block-substitution operad encodes the lattice viewpoint, reproducing the Möbius inversion. In this section we address the relationship between the two operads, at the level of their bialgebras. We show that these constitute a pair of interacting bialgebras in the sense of [6], and more precisely a comodule bialgebra (see [30] for a review). In fact we show that N is a comodule shuffle Hopf algebra over B. We shall then explore this relationship to establish formulae for the half-shuffle exponentials in terms of universal characters, which are analogues of zeta functions in the three cases of free, monotone, and boolean moment-cumulant relations. The comodule-bialgebra viewpoint also allows to understand the inverses of these universal characters, and relate them to Möbius inversion. 5.1 Comodule bialgebra Briefly, the notion of comodule bialgebra is the following: for any coalgebra B one has the notion of right-B-comodule. If B is furthermore a bialgebra, the category CoMod(B) of right-B- comodules is naturally monoidal, and if B is a commutative bialgebra, this monoidal structure acquires a braiding. It hence makes sense to talk about bialgebras in CoMod(B). These are the 27 comodule bialgebras. In a nutshell a comodule bialgebra is a bialgebra with a coaction by B, compatible with the bialgebra structure. In the case at hand, the promised right coaction ρ : N → N ⊗B is essentially the coproduct 0 0 δ of the commutative bialgebra B, but extended to include the empty partition, which is an element in N . N −→ N ⊗ B 0 0 ρ : P 7−→ Q⊗ P/Q. P≤Q Note in particular that ρ(∅) = ∅⊗ 1 (because there are no other coarser partitions of ∅ than ∅ itself, and this has no blocks, so the fibre monomial is just the algebra unit). Coassociativity of this coaction ρ is clear from the fact that it is essentially the coproduct δ. Theorem 5.1.1. The coaction ρ : N → N ⊗ B makes N into a comodule bialgebra over 0 0 0 B. That is, the following relations hold for all P, Q ∈ N : ρ(1 ) = 1 ⊗ 1 , N N B 0 0 ρ(P · Q) = ρ(P )ρ(Q), (ε ⊗ Id)◦ ρ(P ) = ε (P )1, N N 0 0 (Δ ⊗ Id)◦ ρ(P ) = (Id⊗ Id⊗m )◦ (Id⊗τ ⊗ Id)◦ (ρ⊗ ρ)◦ Δ (P ), (16) 0 B 0 where τ : B⊗ N −→ N ⊗ B is the swap map Q⊗ P 7→ P ⊗ Q. 0 0 This theorem can be proved using the general machinery of operads and brace algebras from [17]. Here we wish to present an elementary argument, exhibiting the main ingredients that make it work. Proof. The most interesting part is the fourth statement, which states that Δ is a B-comodule homomorphism. Diagrammatically, this looks as follows N N ⊗ N 0 0 0 ρ⊗ρ N ⊗ B⊗ N ⊗ B 0 0 Id ⊗τ⊗Id N ⊗ N ⊗ B⊗ B 0 0 Id ⊗ Id ⊗m N ⊗ B N ⊗ N ⊗ B 0 0 0 Δ ⊗Id The two sides of the equation (16) are both elements in the tensor product N ⊗ N ⊗ B, that 0 0 is, sums of tensors. To establish the equation (for each fixed partition P ), we first establish a bijection between the indexing sets for the two sums, and then show that under this bijection, the three corresponding tensor terms agree. Step 1: the left-hand side of (16) (corresponding to the down-right path in the diagram) sends P to a sum over the set of ways of first coarsening P and then cutting the coarsened partition. The right-hand side of the equation (given by the right-down path in the diagram) sends a partition P to a sum indexed by the set of all ways to cut P into upper- and lowersets and then coarsen each layer. The natural bijection between these to sets is most easily given by establishing for each set a natural bijection with the set of possible compatible cuts and coarsenings, or coarse-cuts, as we shall say for short. A coarse-cut on a partition P consists of both a cut and a coarsening, required to be compatible in the sense that the cut is not allowed to separate two blocks that are joined in the coarsening. Here is a picture to illustrate this: 28 1 2 3 4 5 6 7 8 9 The blue dotted lines indicate which blocks are joined in the coarsening. Graphically, the com- patibility condition says simply that the red line expressing the cut is not allowed to cross the blue lines expressing the coarsening. The required bijections are clear. Step 2: for each fixed partition P , and each fixed coarse-cut, we must identify the corre- sponding two terms in the triple tensor product N ⊗ N ⊗ B. For the example given above, 0 0 these three tensor factors are O O ∅ · · ∅ · ∅ · · ∅ · · · 1 5 6 7 9 2 3 4 8 1 6 7 9 2 3 4 5 8 as we shall now see. The first tensor factor (in N ) is simply the coarsening of the lower layer. Indeed, this is obtained via the left-hand side by first coarsening, and then cutting the coarse partition. It is obtained via the right-hand side by first cutting, and then coarsening the lower layer. So the first tensor factor matches up as required. The second tensor factor (also in N ) is described as the upperset monomial of the coarse version of the cut. This immediately matches the description obtained from the left-hand side. Via the composite map of the right-hand side, the second tensor factor arises from looking first in the upper layer (that’s a monomial, not a single partition), and then coarsening each of the factors in the monomial. Since the lowerset partition and its coarsening have precisely the same elements in [n], the factors in the uppersets also have the same elements. On the left-hand side the coarsening of them takes place before cutting, and in the right-hand side the coarsening takes place after cutting, and clearly the order of these two steps does not affect the result, so also the second tensor factor matches up as required. Finally the third factor (which belongs to B) has nothing to do with the cut: it is simply the fibre of the total coarsening (as in Subsection 4.3, i.e. for each block in the coarse partition, list the corresponding finer partition). What the equation says for this tensor factor (and which is clearly true) is that to compute the fibre of the whole coarsening (without even taking the cut into account) can be done in two steps: first compute fibres of the blocks in the bottom layer, then compute fibres of the blocks in the upper layer, and then join the result (concatenation, multiplication of monomials). (A subtlety to note here is that the monomial in the right-hand tensor factor of N ⊗ N may contain empty partitions. But we have ρ(∅) = ∅⊗ 1 (where 1 is 0 0 the algebra unit). This is just to say that the fibre of the trivial coarsening of ∅ is the trivial monomial. Put in another way, since the empty partition has no blocks, there are no fibres. The ∅-factors therefore disappear (what the third tensor factor B is concerned).) Theorem 5.1.2. The right coaction ρ : N → N ⊗ B makes N an unshuffle (also called codendriform) Hopf algebra in the category of right comodules over B. That is, the comodule Hopf algebra structure and the unshuffle Hopf algebra structure are compatible, meaning that for all P ∈ N we have (Δ ⊗ Id)◦ ρ(P ) = (Id⊗ Id⊗m )◦ (Id⊗τ ⊗ Id)◦ (ρ⊗ ρ)◦ Δ (P ), ≺ B ≺ (Δ ⊗ Id)◦ ρ(P ) = (Id⊗ Id⊗m )◦ (Id⊗τ ⊗ Id)◦ (ρ⊗ ρ)◦ Δ (P ), ≻ B ≻ where τ : B⊗ N −→ N⊗ B is the swap map Q⊗ P 7→ P ⊗ Q. Proof. It is clear that the coaction ρ : N → N ⊗ B restricts to a coaction ρ : N → N ⊗ B, 0 0 and that this makes N a comodule Hopf algebra. To check the compatibility with the splitting of the unshuffle coproduct into half-unshuffles, it remains to notice that the coaction works by refinement of blocks, and that this does not interfere with whether or not the block containing the element 1 belongs to the lowerset of a cut. 29 5.2 Four bijections from infinitesimal characters to characters We focus in this subsection on the structure of noncrossing partitions and relations between moments and free cumulants, having in mind applications of the previous results to free, boolean and monotone probabilities (on the latter two in the context of the present article, see [13]). We show indeed that the comodule bialgebra structure of N over B leads to a new approach to these phenomena. Recall first from [14] that groups of characters on unshuffle (also called codendriform) Hopf algebras H have a rather rich structure with, in particular, three exponentials and logarithms putting in bijection the Lie algebra of infinitesimal characters of H and the group of characters. When applied in the context of free probability, these maps together with associated properties of the group and Lie algebras lead to a new understanding of the three natural families of cumulants in this context (free, monotone and boolean), of their relationships, and of related notions such as additive convolution of free distributions (see also [13]). In the present section we explore these bijections using the action of the monoid M of characters of B, and relate the resulting formulae with the Möbius function of the lattice of noncrossing partitions. The product in M , induced by the coproduct δ, is denoted by ∗. We denote by G the B B group of invertible elements of M . Lemma 5.2.1. Let φ ∈ M . Then φ ∈ G if and only if φ(I ) 6= 0 for all n ≥ 1. B B n Proof. Let φ ∈ G and ψ be the inverse of φ for the convolution ∗. For any n ≥ 1, since I is a B n group-like element, we have 1 = φ∗ ψ(I ) = φ(I )ψ(I ), and hence φ(I ) 6= 0. n n n n Conversely, the bialgebra B is graded by the number of blocks (minus one), and its com- ponent of degree zero has a basis of group-like elements, namely the products of I ’s. Hence, ′ −1 −1 ′ B = B[I , . . . , I , . . . ] is a Hopf algebra, with the extension δ of the coproduct δ defined 1 n ′ −1 −1 −1 by δ (I ) = I ⊗ I . If φ ∈ M satisfies φ(I ) 6= 0 for all n ≥ 1, it can be extended as a B n n n n ′ ′ ′ ′ ′ character φ to B . Denote by ψ the inverse of φ in the group of characters of B and by ψ its restriction to B. For any P ∈ B: ′ ′ ′ (φ∗ ψ)(P ) = (φ⊗ ψ)◦ δ(P ) = (φ ⊗ ψ )◦ δ (P ) = ε ′(P ) = ε (P ). B B Similarly, (ψ ∗ φ)(P ) = ε (P ), so φ ∈ G . B B We also write g for the Lie algebra of infinitesimal characters of N (linear forms that vanish on (N ) ; the Lie bracket is induced by the associative convolution product of linear forms). We furthermore write G for the group of characters of N. Its product, induced by Δ, is denoted by ⋆. As already observed, the coproducts Δ and Δ induce a shuffle (also called dendriform) ≺ ≻ ∗ ∗ algebra structure on the dual N . It is extended to products of elements of N with the unit ε of the convolution product as follows: for any f ∈ N , f ≺ ε = f, f ≻ ε = 0, N N ε ≺ f = 0, ε ≻ f = f. N N The coaction ρ induces a right action of M on linear forms on N, denoted by x: for α an arbitrary linear form on N and φ ∈ M , it is given by α x φ := (α⊗ φ)◦ ρ. It restricts to an action by group endomorphisms on G and by Lie algebra endomorphisms on g . Note that as an algebra B is the abelianization of N, so, as sets, M and G can be iden- B N tified. Through this identification, we see that the action x coincides with the product ∗. In the following, to avoid ambiguities, when φ ∈ G , we write φ for the corresponding element of 30 b M . Conversely, when ψ ∈ M , we write ψ for the corresponding element of G (so that in B B N particular for φ ∈ G and γ ∈ M , we have φ x γ = φ∗ γ). N B First, since N is freely generated by NCP as an algebra, characters and infinitesimal char- acters on N are entirely determined by their restriction to NCP, and the following maps are bijections: ∗ ∗ g −→ Vect(NCP) G −→ Vect(NCP) N N θ : θ : g G κ 7−→ κ , φ 7−→ φ . |Vect(NCP) |Vect(NCP) −1 The composite bijection Θ = θ ◦ θ : g −→ G sends any κ ∈ g to the unique character g N N N Θ(κ) : N → K such that it agrees with κ on degree-1 monomials. That is, κ(P ) = Θ(κ)(P ) (for any P ∈ NCP). What cumulants are concerned we shall be especially interested in those elements in g that −1 vanish on NCP(k, n) for k ≥ 2. In particular, we shall consider e = Θ (εb ). In other words, e is the unique infinitesimal character of N such that for any P ∈ NCP(k, n), we have e(P ) = δ . k,1 As a consequence, for all P ∈ NMP(k, n): e(P ) = δ . k,1 The first natural bijection Θ : g → G rewrites as follows, in terms of the coaction of B on N N N: Proposition 5.2.2. For any κ ∈ g , put K := Θ(κ) ∈ M . Then we have N B κ = e x K. Proof. For any P ∈ NCP we have e x K(P ) = e(Q)K(P/Q) = K(P ) = κ(P ). P≤Q Since κ and e x K therefore agree on all noncrossing partitions, and are both infinitesimal characters over N, they must be equal. Proposition 5.2.3 (Left half-shuffle exponential isomorphism). Let κ ∈ g . There exists a unique φ ∈ N , such that φ = ε + κ ≺ φ; moreover, φ ∈ G . Conversely, let φ ∈ G . There N N N exists a unique κ ∈ N , such that φ = ε +κ ≺ φ; moreover, κ ∈ g . In particular, the following N N map is a bijection: g −→ G N N E : κ 7−→ φ such that φ = ε + κ ≺ φ. Proof. Let us define φ(P ) for any P ∈ NMP(k, n) by induction on n. If n = 0, then P = 1 and ′ ′′ φ(1) = 1. If n ≥ 1, we put φ(P ) = κ(P ) +κ(P )φ(P ) (with Sweedler-like notation for Δ as in ≺ ≺ (7)). We obtain in this way a map φ ∈ N , such that φ = ε + κ ≺ φ. Let x ∈ NMP(k, m) and y ∈ NMP(l, n); let us prove that φ(xy) = φ(x)φ(y) by induction on m + n. If m = 0 or n = 0, then x = 1 or y = 1 and the result is immediate. We now assume that m, n ≥ 1. Then, as κ is an infinitesimal character, and by the induction hypothesis: ′ ′′ ′ ′′ φ(PQ) = κ(PQ)φ(1) + κ(P )φ(Q) + κ(PQ )φ(Q ) + κ(P Q)φ(P ) ≺ ≺ ′ ′′ ′ ′ ′′ ′′ + κ(P )φ(P Q) + κ(P Q )φ(P Q ) ≺ ≺ ≺ ≺ ′ ′′ = κ(P )φ(Q) + κ(P )φ(P )φ(Q) ≺ ≺ = φ(P )φ(Q). So φ ∈ G . The proof of the second statement is similar and the last is an easy consequence of the first two points. 31 The following character on N plays a special role: ψ := E (e). We shall see in Theorem 5.3.2 ≺ ≺ that it corresponds to the zeta function, ψ = ζ: we have ψ (P ) = 1 for every noncrossing ≺ ≺ partition P . The left half-shuffle exponential isomorphism rewrites as follows. Theorem 5.2.4. For any κ ∈ g , put K := Θ(κ) ∈ M as usual. For φ ∈ G we have N B N φ = ε + κ ≺ φ ⇐⇒ φ = ψ x K. N ≺ In other words, we have E (κ) = ψ x K. ≺ ≺ Proof. By definition, ψ = ε + e ≺ ψ . Since N is an unshuffle bialgebra in the category of ≺ N ≺ right B-comodules, we have: ψ x K = (ε + e ≺ ψ ) x K ≺ N ≺ = ε x K + (e x K) ≺ (ψ x K) N ≺ = ε + (e x K) ≺ (ψ x K) N ≺ = ε + κ ≺ (ψ x K) (by 5.2.2). N ≺ This shows that ψ x K satisfies the equation characterizing φ, and hence establishes the bi- implication. To establish the last equation, note that the character E (κ) is by definition the unique solution φ to the equation φ = ε + κ ≺ φ. But we have just seen that ψ x K satisfies N ≺ this equation. Proposition 5.2.5. Let us consider a family of scalars (k ) . We define the infinitesimal n n≥1 character κ on N by: k if P = I , n ≥ 1, n n κ(P ) = 0 otherwise. Then Theorem 5.2.4 gives, for any P ∈ NCP, that E (κ)(P ) = k and the moments ≺ ♯π π∈P X Y (E (κ) x ζ)(J ) = k . ≺ n ♯π π∈Q Q∈NCP(n) Proof. For any κ ∈ g , put K := Θ(κ) ∈ M . For P ∈ NCP we compute, by Theorem 5.2.4: N B X Y E (κ)(P ) = (ψ x Θ(κ))(P ) = Θ(κ)(P/Q) = Θ(κ)(P ) + 0 = k . ≺ ≺ ♯π P≤Q π∈P From this it follows that E (κ) x ζ = (ψ x Θ(κ)) x ζ = ψ x (Θ(κ)∗ ζ) ≺ ≺ ≺ (by associativity of the action), and therefore (E (κ) x ζ)(J ) = ψ (Q)(Θ(κ)∗ ζ)(J /Q) ≺ n ≺ n Q∈NCP(n) = (Θ(κ)∗ ζ)(J ··· J ) ♯π ♯π 1 k P ={π ,...,π }∈NCP(n) 1 k = (Θ(κ)∗ ζ)(J )··· (Θ(κ)∗ ζ)(J ) ♯π ♯π P ={π ,...,π }∈NCP(n) X Y = k . ♯π π∈P P∈NCP(n) 32 Proposition 5.2.6. Let us consider a family of scalars (k ) . We define the infinitesimal n n≥1 character κ on N by: k if P = J = {{1}, . . . ,{n}}, n ≥ 1, n n κ(P ) = 0 otherwise. Then for any P ∈ NCP(k, n): 0 if k < n, X Y E (κ)(P ) = (ψ x Θ(κ))(P ) = Θ(κ)(P/Q) = ≺ ≺ k if k = n. ♯π P≤Q Q∈NCP(n) π∈Q Proof. For any P ∈ NCP(k, n), k < n, it is clear that P/Q contains blocks of size bigger than one, i.e., P/Q is not a monomial of forests of sticks. This implies that Θ(κ)(P/Q) = 0. For P = J ∈ NCP(n, n) E (κ)(J ) = ψ (Q)Θ(κ)(J /Q) ≺ n ≺ n Q∈NCP(n) = Θ(κ)(J ··· J ) ♯π ♯π 1 k P ={π ,...,π }∈NCP(n) 1 k = Θ(κ)(J )··· Θ(κ)(J ) ♯π ♯π P ={π ,...,π }∈NCP(n) X Y = k . ♯π π∈P P∈NCP(n) Remark 5.2.7. Proposition 5.2.6 reveals a nice connection to the approach to free moment- cumulant relations presented in [11]. Indeed, let (A, ϕ) be a noncommutative probability space |A and consider the sub Hopf algebra N of forests of sticks, as in Corollary 3.3.12 but decorated by elements from A. Since a monomial of A-decorated forests of sticks is the same thing as a |A list of A-words, it is easy to see that the Hopf algebra N is isomorphic to the double tensor algebra over A (with the coproduct defined in [11]). Proposition 5.2.6 gives another proof of the free moment-cumulant relations deduced from a shuffle fixpoint equation. We now consider instead the right half shuffle: Proposition 5.2.8 (Right half-shuffle exponential isomorphism). Let κ ∈ g . There exists a unique φ ∈ N , such that φ = ε + φ ≻ κ; moreover, φ ∈ G . Conversely, let φ ∈ G . There N N N exists a unique κ ∈ N , such that φ = ε + φ ≻ κ; moreover, κ ∈ g . The following map is N N therefore a bijection: g −→ G N N E : κ −→ φ such that φ = ε + φ ≻ κ. The right half-shuffle exponential isomorphism rewrites as follows. Let us put ψ := E (e). ≻ ≻ Theorem 5.2.9. For any κ ∈ g , put K := Θ(κ) ∈ M as usual. Then for φ ∈ G we N B N have: φ = ε + φ ≻ κ ⇐⇒ φ = ψ x K. N ≻ 33 Let us finally consider the classical exponential bijection from the Lie algebra g to the group G : g −→ G N N ⋆n exp : κ 7−→ exp (κ) = . n! k=0 Put ψ := exp (e). Proposition 5.2.10 (Exponential isomorphism). For any κ ∈ g , put K := Θ(κ) ∈ M as N B usual. Then for φ ∈ G we have: φ = exp (κ) ⇐⇒ φ = ψ x K. Proof. Indeed: ψ x K = exp (e) x K = exp (e x K) = exp (κ) = ψ (κ), ∗ ⋆ ⋆ ⋆ ⋆ the third equality by Proposition 5.2.2. 5.3 Description of the universal maps ψ , ψ and ψ ≺ ≻ ⋆ In the previous subsection, we have seen that the maps ψ = E (e), ψ = E (e) and ψ = ≺ ≺ ≻ ≻ ⋆ exp (e) encode the three shuffle exponentials from g to G . In this subsection, we compute N N them explicitly. The set of partitions (or noncrossing partitions) forms a monoid under ordinal sum, denoted ⊎, with neutral element the empty partition. On the underlying linear orders it is just ordinal sum, [n]⊎ [m] = [n+m], and the partition structure on [n+m] is induced via the sum injections [n] → [n+m] ← [m] in the canonical way. A partition is called irreducible if it cannot be written as the ordinal sum of two non-empty partitions. A noncrossing partition P ∈ NCP(n) is irreducible if and only if 1 and n belong to the same block. In general, the block containing the element 1 we call the base block and denote it π . Let k denote the biggest element belonging to π , then J1, kK = Conv(π ) is a union of 1 1 1 blocks of P , and P is an irreducible partition, which we call E . Now we have |J1,kK 1 P = E ⊎ P, ˜ ˜ where P = E . Proceeding now the same way with P and iterating, it is clear that every noncrossing partition P splits uniquely into an (iterated) ordinal sum of irreducible noncrossing partitions, called irreducible components P = E ⊎···⊎ E . 1 r (For general partitions, the notion of irreducible is slightly more complicated, as, for example, also the partition with crossing is clearly irreducible. In general a partition is irreducible precisely when its noncrossing closure is irreducible. The unique splitting of an arbitrary partition into irreducible components is similar, but will not be needed here.) We shall say that a noncrossing partition is boolean if its irreducible components are precisely its blocks. In other words, it is an (iterated) ordinal sum of single-block partitions. In particular, in a boolean partition there is no nesting of blocks. 34 Definition 5.3.1 (Monotone compositions). Recall that a noncrossing composition is a non- crossing partition P equipped with a numbering of its blocks. Such a numbering is called a heap ordering if it preserves the order → (that is, the numbering map (P, → ) −→ [k] is monotone P P (k is the number of blocks)), meaning that if one block is nested inside another then it has a higher number. We denote by ho(P ) the cardinality of the set of heap orderings of a noncrossing partition P . A monotone composition is by definition a noncrossing partition with a chosen heap ordering. Theorem 5.3.2. 1. For any P ∈ NCP, we have ψ (P ) = 1. That is, ψ corresponds to ≺ ≺ the zeta function ζ ∈ B. 1 if P is boolean, 2. For any P ∈ NCP, we have ψ (P ) = 0 otherwise. ho(P ) 3. Let P ∈ NCP(k, n). Then ψ (P ) = . k! ... Recall from Definition 3.3.10 that if (L, U) is a cut of P , then U denotes the reduced gap monomial of the cut, the monomial obtained as the partitions belonging to U that appear in the gaps of L. Proof. Let P ∈ NCP(k, n). If π is base block of P , write P := P c as in the preliminary | Conv(π ) ˜ ˜ discussion above. In particular, if k = 1, then P = ∅, and ψ (P ) = ψ (P ) = ψ(P ) = 1. ≺ ≻ 1. If (L, U) is a cut of P such that e L 6= 0, then U contains all the blocks of P but one. By definition of ψ : ... ψ (P ) = e L ψ U = ψ (P ). ≺ ≺ ≺ (L,U)∈cut(P ), 1∈L The result follows by an easy induction on k. ... 2. If U is an upperset of P such that e U 6= 0, then, by definition of e, U contains only one block of P . The block π of P containing 1 is an upperset of P if and only if it is a irreducible component of P . Hence: X ˜ ... ψ (P ) if π is irreducible, ≻ 1 ψ (P ) = ψ (L)e(U) = ≻ ≻ 0 otherwise. (L,U)∈cut(P ), 1∈L The result follows by an easy induction on k. 3. An upper-block is a block which is also an upperset; in other words, it is a maximal element in the poset (P, → ) (that is, a block that has no nested blocks inside it). We write (L, U) ∈ cut (P ) for the situation where the upperset U consists of a single block (which is −1 hence an upper-block). If σ : (P, → ) −→ [k] is a heap ordering of P , then the block σ (k) is necessarily an upper-block. This yields a recursive calculation of the heap-order numbers: ho(P ) = ho(L), (17) (L,π)∈cut (P ) which is used in the following proof of Item 3 by induction on k. If k = 1, then ψ (P ) = e(P ) + 0 = 1 and we are done. Assume the result at rank k− 1, and consider a partition P with (1) (l) k blocks. With Sweedler notation for the iterated coproducts (P 7−→ P ⊗···⊗ P ): (1) (l) ψ (P ) = e(P )··· e(P ) l! l=1 35 1 (1) (k) = e(P )··· e(P ) + 0 k! (1) (k−1) = e(L )··· e(L )e(U) k! (L,U)∈cut (P ) (1) (k−1) = e(L )··· e((L) ) k! (L,U)∈cut (P ) = ψ (L) (L,U)∈cut (P ) 1 ho(L) = (by induction hyp.) k (k − 1)! (L,U)∈cut (P ) ho(P ) = (by (17)) k! as required. 5.4 On the inverses of the universal maps By Lemma 5.2.1, ψ , ψ and ψ are invertible elements of the monoid (M ,∗). In this subsection, ≺ ≻ ⋆ B we investigate the behaviour of these inverses. The following proposition emphasizes once again the boolean character of ψ (recall indeed from [13] that the right half-shuffle exponential is associated to boolean cumulants in free probability). Proposition 5.4.1. For any P ∈ NCP(k, n): k+1 (−1) if P is boolean, ∗−1 ψ (P ) = 0 otherwise; 1 if P is irreducible, ∗−1 ψ ∗ ψ (P ) = 0 otherwise, k+1 (−1) if P is irreducible, ∗−1 ψ ∗ ψ (P ) = 0 otherwise. ∗−1 Proof. Let us assume that P is not boolean and let us prove that ψ (P ) = 0 by induction on k. If k = 1, there is nothing to prove. If k ≥ 2, then for any Q > P , either Q is not boolean with ∗−1 l < k blocks, and hence vanishes under ψ , or one of the components of P/Q is not boolean, and hence vanishes under ψ . This shows that ∗−1 ∗−1 ∗−1 ψ ∗ ψ (P ) = ψ (P )ψ (P/P ) + 0 = ψ (P ) = ε (P ) = 0. ≻ ≻ B ≻ ≻ ≻ ∗−1 k+1 Let us assume that P is boolean and let us show that ψ (P ) = (−1) by induction on ∗−1 −1 k. If k = 1, then ψ (P ) = ψ (P ) = 1. If k ≥ 2: ∗−1 ∗−1 ψ ∗ ψ (P ) = ψ (Q)ψ (P/Q) ≻ ≻ ≻ ≻ Q≥P ∗−1 = ψ (Q) Q≥P k−1 ∗−1 l+1 l = ψ (P ) + (−1) ♯{(c , . . . , c ) ∈ N | c +··· + c = k} 1 l 1 l ≻ >0 l=1 k−1 k− 1 ∗−1 l+1 = ψ (P ) + (−1) k − l l=1 k−1 k− 1 ∗−1 k+1 l = ψ (P ) + (−1) (−1) l=1 ∗−1 k+1 = ψ (P )− (−1) = ε (P ) = 0. Let E , . . . , E be the irreducible components of P , n their respective cardinality, and P the 1 i noncrossing partition whose blocks are Jn +··· + n + 1, n +··· + n K, 1 ≤ i ≤ k. Then: 1 i−1 1 i ∗−1 ∗−1 ψ ∗ ψ (P ) = ψ (Q) ≻ ≻ P≤Q ∗−1 = ψ (Q) + 0 P≤Q l+1 l = (−1) ♯{(c , . . . , c ) ∈ N | c +··· + c = k} 1 l 1 l >0 l=1 k−1 k− 1 k+1 l = (−1) (−1) l=0 1 if k = 1, 0 otherwise. ∗−1 Let α = ψ ∗ ψ , and define β ∈ M by: ≺ B k+1 (−1) if P is irreducible, β(P ) = for P ∈ NCP(k, n). 0 otherwise For any Q ∈ NCP we denote by bl(Q) the number of blocks of Q. Let P ∈ NCP(k, n). bl(Q)+1 β ∗ α(P ) = (−1) . Q≥P, Q irreducible, the factors of P/Q irreducible If P is not irreducible, then for any Q ≥ P , either Q is not irreducible or one of the factors of P/Q is not irreducible. Hence, in this case, β∗ α(P ) = 0 = ε (P ). Let us now assume that P is irreducible. If P ∈ NCP(1, n), then β ∗ α(P ) = 1 = ε (P ). Let us assume that P ∈ NCP(k, n), with n ≥ 2. As P is irreducible, it can be written as: P = I ⋄ (∅, P , . . . , P ,∅), n 1 n−1 where P , . . . , P ∈ NCP . We denote by E the irreducible components of P . If some P 1 n−1 0 i,j i i is the empty partition, then of course it has no irreducible components, so there are no E for i,j this index i. But since k ≥ 2, at least one of the P is non-empty. We denote by J the set of pairs (i, j) such that 1 ≤ i ≤ n− 1 and such that P has at least j irreducible components. The set J thus indexes the meaningful P . There is a bijection i,j  Y  {Q ∈ NCP | Q ≥ P} −→ {Q ∈ NCP | Q ≥ P }×{0, 1} i,j i,j i,j (i,j)∈J Q 7−→ (Q , ǫ ) , i,j i,j i,j∈J where for any (i, j) ∈ J, Q is the noncrossing partition formed by the blocks of Q included in i,j Q , and ǫ = 0 if the base block of P and the base block of P are included in the same block i,j i,j i,j 37 of Q, and 1 otherwise. Hence: Y X bl(Q )+1 bl(Q ) i,j i,j β ∗ α(P ) = (−1) + (−1) = 0 = ε (P ). Q ≥P , (i,j)∈J i,j i,j Q irreducible, i,j the factors of P /Q irreducible i,j i,j ∗−1 ∗−1 This shows that β ∗ α(P ) = 0 = ε (P ), and therefore β = α = ψ ∗ ψ . B ≻ 5.5 On the inverse of the “free” universal map ψ Lastly we investigate the behaviour of ψ , the universal map associated to the left half-shuffle exponential — the one relating free cumulants and moments in free probability. Not surprisingly, 1 2n its combinatorics involves the Catalan numbers cat = . In fact the following lemma n+1 n+1 n characterizes the Catalan number, as it allows to compute them inductively. Lemma 5.5.1. For any n ≥ 1: ⌊ ⌋ n− k n−k+1 (−1) cat = δ . n−k n,1 k=0 Proof. We denote by P the free non-symmetric operad on one binary generator: for any n ≥ 1, P(n) is the vector space generated by the set of plane binary trees with n leaves (so has dimension cat ), and the operad composition law is given by grafting on leaves. For any p ∈ P(n), q , . . . , q ∈ P, we put: 1 k p ◭ (q . . . q ) = p◦ (I, . . . , I, p , I, . . . , I, p , I, . . . , I). 1 k 1 k | {z } 1≤i <...<i ≤n p is position i j j In particular, p ◭ (1) = p and, if k > n then p ◭ (q . . . q ) = 0. We denote by I the unique 1 k plane binary tree with one leaf and by Y the unique plane binary tree with two leaves. For all n ≥ 1, we define inductively X ∈ P(n) by X = 1 and: n 1 ⌊ ⌋ k+1 k ∀n ≥ 2, X = (−1) X ◭ Y . n n−k k=1 P Q We also put X = X . Then X is the unique solution in P(n) of the equation: n≥1 k+1 k X = I + (−1) X ◭ Y , k=1 or equivalently: k k (−1) X ◭ Y = I. k=0 Let us consider X = I +X∨X, where ∨ is the operator that grafts two binary trees onto a new common root. Then: ∞ ∞ X X k ′ k k (−1) X ◭ Y = I − Y + 0 + (X ∨ X) ◭ Y k=0 k=0 X X i j = I − Y + (X ◭ Y )∨ (X ◭ Y ) k=0 i+j=k 38   ∞ ∞ X X i i j j   = I − Y + (−1) X ◭ Y ∨ (−1) X ◭ Y i=0 j=0 = I − Y + I ∨ I = I. Hence, X = X, so X = I + X ∨ X. An easy induction on n implies that X is the sum of all plane binary trees with n leaves. Sending any plane binary tree to 1, we get, for any n ≥ 2: n n ⌊ ⌋   ⌊ ⌋ 2 2 X X k k k+1 k+1 X (1) = cat = (−1) X (1) = (−1) cat , n n n−k n−k n− k n− k k=1 k=1 which gives the announced formula. For the following proposition, recall that J denote the finest partitions and I denote the n n coarsest partitions, for n ≥ 1. ∗−1 n+1 Proposition 5.5.2. For any n ≥ 1, we have ψ (J ) = (−1) cat . n n ∗−1 −1 Proof. We put κ = Θ (ψ ). Since ψ x Θ(κ) = ε , we see that ε = ε + κ ≺ ε . Hence, ≺ B B Δ B for all n ≥ 1: δ = (κ⊗ ε )◦ Δ (J ). n,1 B ≺ n A study of uppersets of J proves that: X X n− a −···− a + 1 1 l Δ(J ) = J ⊗ J ··· J , n n−a −···−a a a 1 1 l l l=0 a +···+a ≤n 1 l X X n− a −···− a 1 l Δ (J ) = J ⊗ J ··· J . ≺ n n−a −···−a a a 1 l 1 l a +···+a ≤n l=0 1 l For any k ≥ 1, we have ε (J ) = δ , so: B k k,1 X X n− a −···− a 1 l (κ⊗ ε )◦ Δ (J ) = κ(J )⊗ δ ··· δ B ≺ n n−a −···−a a ,1 a ,1 1 1 l l l=0 a +···+a ≤n 1 l n− l ∗−1 = E (J ) n−l l=0 = δ . n,1 ∗−1 Hence, the sequence (ψ (J )) is the unique sequence (a ) such that for all n ≥ 1: n n≥1 n n≥1 n− l a = δ . n−l n,1 l=0 n+1 By Lemma 5.5.1, a = (−1) cat for all n. n n For any P ∈ NCP(k, n): ∗−1 ∗−1 ψ ∗ ψ (P ) = ψ (P ) = δ . ≺ P,I ≺ ≺ n Q≥P 39 ∗−1 So ψ (P ) = µ (P, I ), where µ is the Möbius function of the poset NCP(n). Proposition 5.5.2 shows that the Euler characteristic of NCP(n) is: n+1 µ (J , I ) = (−1) cat . n n n For any m , . . . , m ≥ 1, we put: 1 k I = {J1, m K, Jm + 1, m + m K, . . . , Jm +··· + m + 1, m +··· + m K}. m ,...,m 1 1 1 2 1 k−1 1 k 1 k Let P ∈ NCP. Then P can be uniquely written as: P = I ⋄ (∅, P , . . . , P ,∅, . . . ,∅, P , . . . , P ,∅), n +1,...,n +1 1,1 1,n 1 1 k,1 k,n k k where k ≥ 1, n , . . . , n ≥ 0 and for all i, j, P is a noncrossing partition, maybe empty. Note 1 k i,j that the irreducible components of P are the noncrossing partitions I ⋄ (∅, P , . . . , P ,∅). n +1 i,1 i,n i i For any Q ∈ NCP, we denote Q = I ⋄ (∅, Q). We have a poset isomorphism: {Q ∈ NCP | Q ≥ P} −→ NCP(k)× {Q ∈ NCP | Q ≥ P }. i,j i,j The bijection sends Q to (Q , (Q ) ), where Q is determined by identifying the base blocks 0 i,j i,j 0 of the irreducible components of P with the k blocks of J , and Q is obtained by identifying k i,j the base block of the ith irreducible component of P with the block of P , the blocks of P i,j i,j being conserved. Hence: ∗−1 k+1 ∗−1 ψ (Q) = (−1) cat . ψ ( P ). k i,j ≺ ≺ i,j ∗−1 This allows to compute ψ (P ) by induction on the number of blocks of cardinality ≥ 2. For example: ∗−1 ∗−1 ψ = −cat .ψ = −cat .cat , 2 2 3 ≺ ≺ ∗−1 ∗−1 3 ψ = −cat .ψ = −cat . ≺ ≺ 2 References [1] M. Aguiar, S. Mahajan, Monoidal functors, species and Hopf algebras, vol. 29 of CRM Monograph Series. American Mathematical Society, Providence, RI, 2010. With forewords by K. Brown, S. Chase and A. Joyal. [2] B. Baumeister, K.-U. Bux, F. Götze, D. Kielak, H. Krause, Non-crossing partitions, arXiv:1903.01146. [3] P. Biane, Some properties of crossings and partitions, Discrete Math. 175 (1997), 41. [4] P. Biane, Free probability and combinatorics, Proceedings of the International Congress of Mathematicians, Vol. II (Beijing, 2002), 765. [5] Y. Bruned, M. Hairer, L. Zambotti, Algebraic renormalisation of regularity structures, Invent. Math. 215 (2019), 1039. [6] D. Calaque, K. Ebrahimi-Fard, D. Manchon, Two interacting Hopf algebras of trees: A Hopf-algebraic ap- proach to composition and substitution of B-series, Adv. Appl. Math. 47 (2011), 282. [7] F. Chapoton, Un théorème de Cartier–Milnor–Moore–Quillen pour les bigèbres dendriformes et les algèbres braces, J. Pure Appl. Algebra 168 (2002), 1. [8] G. C. Drummond-Cole, An operadic approach to operator-valued free cumulants, Higher Structures 2 (2018), [9] G. C. Drummond-Cole, A non-crossing word cooperad for free homotopy probability theory, MATRIX Book Series 1 (2018), 77. 40 [10] K. Ebrahimi-Fard, F. Fauvet, D. Manchon, A comodule-bialgebra structure for word-series substitution and mould composition, J. Algebra 489 (2017), 552. [11] K. Ebrahimi-Fard, F. Patras, Cumulants, free cumulants and half-shuffles, Proc. Royal Soc. A 471 2176, (2015). [12] K. Ebrahimi-Fard, F. Patras, The splitting process in free probability theory, Int. Math. Res. Notices 9 (2016), [13] K. Ebrahimi-Fard, F. Patras, Monotone, free, and boolean cumulants from a Hopf algebraic point of view, Adv. Math. 328 (2018), 112. [14] K. Ebrahimi-Fard, F. Patras, Shuffle group laws. Applications in free probability, Proc. London Math. Soc. 119 (2019), 814. [15] L. Foissy, Les algèbres de Hopf des arbres enracinés décorés. I, Bull. Sci. Math. 126 (2002), 193. [16] L. Foissy, Bidendriform bialgebras, trees, and free quasi-symmetric functions, J. Pure Appl. Algebra 209 (2007), 439. [17] L. Foissy, Algebraic structures associated to operads, arXiv:1702.05344. [18] R. M. Friedrich, J. McKay, Homogeneous Lie Groups and Quantum Probability, arXiv:1506.07089. [19] F. Gabriel, Combinatorial theory of permutation-invariant random matrices I: partitions, geometry and renor- malization, arXiv:1503.02792. [20] I. Gálvez-Carrillo, J. Kock, A. Tonks, Decomposition spaces, incidence algebras and Möbius inversion I: basic theory, Adv. Math. 331 (2018), 952. [21] I. Gálvez-Carrillo, J. Kock, A. Tonks, Decomposition spaces in combinatorics, arXiv:1612.09225. [22] M. Gerstenhaber, A. A. Voronov, Homotopy G-algebras and moduli space operads, Int. Math. Res. Notices 3 (1995), 141. [23] T. Hasebe, F. Lehner, Cumulants, Spreadability and the Campbell–Baker–Hausdorff Series, arXiv:1711.00219. [24] M. Josuat-Vergès, F. Menous, J.-C. Novelli, J.-Y. Thibon, Free cumulants, Schröder trees, and operads, Adv. Appl. Math. 88 (2017), 92. [25] M. G. Kendall. The Advanced Theory of Statistics. Vol. I. J. B. Lippincott Co., Philadelphia, 1944. [26] J. Kock, M. Weber, Faà di Bruno for operads and internal algebras, J. London Math. Soc. 99 (2019), 919. [27] G. Kreweras, Sur les partitions non croisees d’un cycle, Discrete Math. 1 (1972), 333. [28] F. Lehner, Free cumulants and enumeration of connected partitions, Europ. J. Combinatorics 23 (2002), [29] C. Male, Traffic distributions and independence: permutation invariant random matrices and the three notions of independence. To appear in Mem. Amer. Math. Soc. arXiv:1111.4662. [30] D. Manchon, A review on comodule-bialgebras, in the proceedings of the 2016 Abel Symposium “Computation and Combinatorics in Dynamics, Stochastics and Control”, Springer’s Abel Symposia vol. 13, 2018. [31] S. Manzel, M. Schürmann, Non-Commutative Stochastic Independence and Cumulants, Infin. Dimensional Anal. Quantum Probab. Relat. Top. 20 (2017), 1750010. [32] M. Mastnak, A. Nica, Hopf algebras and the logarithm of the S-transform in free probability, Trans. Amer. Math. Soc. 362 (2010), 3705. [33] J. McCammond, Noncrossing Partitions in Surprising Locations, Am. Math. Mon. 113 (2006), 598. [34] A. Nica, R. Speicher, Lectures on the combinatorics of free probability, London Mathematical Society Lecture Note Series, 335 Cambridge University Press, 2006. [35] G.-C. Rota, On the Foundations of Combinatorial Theory I. Theory of Möbius Functions, Z. Wahrschein- lichkeitstheorie 2 (1964), 340. [36] G.-C. Rota, T. C. Wallstrom, Stochastic Integrals: A Combinatorial Approach, Ann. Probab. 25 (1997), [37] W. R. Schmitt, Incidence Hopf algebras, J. Pure Appl. Algebra 96 (1994), 299. [38] R. Simion, Noncrossing partitions, Discrete Math. 217 (2000), 367. [39] T. P. Speed, Cumulants and Partition Lattices, Austral. J. Statist. 25 (1983), 378. [40] R. Speicher, Multiplicative functions on the lattice of non-crossing partitions and free convolution, Math. Ann. 298 (1994), 611. [41] R. Speicher, Combinatorial theory of the free product with amalgamation and operator-valued free probability theory, Memoirs of the AMS 627 (1998). [42] D. Voiculescu, Free Probability Theory: Random Matrices and von Neumann Algebras, Proceedings of the International Congress of Mathematicians, Zürich, Switzerland 1994. Birkhäuser Verlag, Basel, Switzerland, http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png Mathematics arXiv (Cornell University)

Operads of (noncrossing) partitions, interacting bialgebras, and moment-cumulant relations

Download PDF
41 pages

Loading next page...
 
/lp/arxiv-cornell-university/operads-of-noncrossing-partitions-interacting-bialgebras-and-moment-eJNttSy0ng

References

References for this paper are not available at this time. We will be adding them shortly, thank you for your patience.

ISSN
0001-8708
eISSN
ARCH-3343
DOI
10.1016/j.aim.2020.107170
Publisher site
See Article on Publisher Site

Abstract

We establish and explore a relationship between two approaches to moment-cumulant relations in free probability theory: on one side the main approach, due to Speicher, given in terms of Möbius inversion on the lattice of noncrossing partitions, and on the other side the more recent non-commutative shuffle-algebra approach, where the moment-cumulant rela- tions take the form of certain exponential-logarithm relations. We achieve this by exhibiting two operad structures on (noncrossing) partitions, different in nature: one is an ordinary, non-symmetric operad whose composition law is given by insertion into gaps between ele- ments, the other is a coloured, symmetric operad with composition law expressing refinement of blocks. We show that these operad structures interact so as to make the corresponding incidence bialgebra of the former a comodule bialgebra for the latter. Furthermore, this interaction is compatible with the shuffle structure and thus unveils how the two approaches are intertwined. Moreover, the constructions and results are general enough to extend to ordinary set partitions. Contents 1 Introduction 2 2 Partitions and noncrossing partitions — notation and conventions 5 2.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 arXiv:1907.01190v4 [math.CO] 16 Apr 2020 3 Gap-insertion operad and associated structures 7 3.1 A non-symmetric single-colour operad of partitions . . . . . . . . . . . . . . . . . 8 3.2 Induced brace algebra structures . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.3 Induced bialgebras and Hopf algebras . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.4 Unshuffling coproducts on partitions . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.5 Moments and cumulants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 4 Block-substitution operad and associated structures 19 4.1 A coloured symmetric operad of compositions . . . . . . . . . . . . . . . . . . . . 19 4.2 Induced bialgebras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 4.3 Comparison with the lattice approach and Möbius inversion . . . . . . . . . . . . 24 5 Comodule bialgebra, half-shuffle exponentials and Möbius inversion 27 5.1 Comodule bialgebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 5.2 Four bijections from infinitesimal characters to characters . . . . . . . . . . . . . 30 5.3 Description of the universal maps ψ , ψ and ψ . . . . . . . . . . . . . . . . . . 34 ≺ ≻ ⋆ 5.4 On the inverses of the universal maps . . . . . . . . . . . . . . . . . . . . . . . . . 36 5.5 On the inverse of the “free” universal map ψ . . . . . . . . . . . . . . . . . . . . 38 Keywords: operads; set partitions; noncrossing partitions; Möbius inversion; free probability; moment-cumulant relations; combinatorial Hopf algebra; unshuffle bialgebra; interacting bialgebras; shuffle algebra. MSC Classification: 16T05; 16T10; 16T30; 18M60; 46L53; 46L54. 1 Introduction One of Rota’s main motivations for developing the now ubiquitous machinery of incidence alge- bras and Möbius inversion [35] was to provide a clean combinatorial explanation of the moment- cumulant relations in classical probability, known already to involve the Bell numbers (see for example [25]). The idea is that both moments m and cumulants c (of a fixed random variable) are considered as linear forms on the incidence coalgebra of the lattice of set partitions, and that the relationships amount to convolution with the zeta function and its inverse, the Möbius function of the lattice (see also Speed [39]): m = ζ ∗ c c = µ ∗ m. More generally, Rota’s seminal paper with Wallstrom [36] showed that many of the basic aspects of stochastic analysis can be rendered combinatorially in terms of the lattice of set partitions. A beautiful extension of Rota’s ideas was found by Speicher [40, 41] to account for the relationship between moments and free cumulants in the setting of Voiculescu’s theory of free probability [42]. Speicher showed that the free moment-cumulant formulae follow the same pattern as the classical case if just the lattice of set partitions is replaced by the lattice of noncrossing partitions [34]. Beyond the importance of this in the context of free probability (see also Biane [3, 4]), it is as well a striking new application of the combinatorial topic of noncrossing partitions , which is also important in exploring the interface between algebraic geometry and representation theory (see for example the recent survey [2]), and which comes up in numerous other contexts [33, 38]. Recently, two of the present authors proposed a different approach to moment-cumulant rela- tions [11, 12, 14, 13], which is not based on the lattice of noncrossing partitions, incidence algebras or Möbius inversion. Instead, it employs a certain non-commutative shuffle algebra and consid- ers moments and free cumulants as images of a particular Hopf algebra character, respectively Kreweras’ 1972 paper “Sur les partitions non croisées d’un cycle” [27] initiated the study of noncrossing partitions in combinatorics. 2 infinitesimal character. Moment-cumulant relations are encoded through exponential-logarithm correspondences implied by fixpoint equations involving so-called half-shuffle products ≺ and ≻. For instance, in the free case the moment character φ and the free cumulant infinitesimal char- acter κ are related through a half-shuffle fixpoint equation in non-commutative shuffle algebra φ = ε + κ ≺ φ, where ε is the counit. The shuffle-algebra approach supports a Lie theoretic perspective, which is augmented by the notions of pre-Lie and, more generally, brace algebra [7]. The motivation for the present work was to uncover the relationship, hitherto completely mysterious, between the two approaches to moment-cumulant formulae. The general framework found to accommodate the two disparate approaches is the theory of operads and their incidence bialgebras. In a nutshell we show that the two approaches are governed each by their particular operad of noncrossing partitions; we then show how these two operads interact at the level of the corresponding bialgebras, and derive comparisons between the two settings in terms of this interaction. Somewhat surprisingly, the framework turns out to be general enough to cover also the case of ordinary set partitions. Here, too, there exists a pair of interacting operads. As a consequence we obtain in this case as well a close connection between the Möbius-theoretic moment-cumulant relations à la Rota, and the (little studied) shuffle-algebraic approach in that context. In the following summary we concentrate on the case of noncrossing partitions, since this was our original motivation and central aim. The first operad is an ordinary nonsymmetric operad of noncrossing partitions, where each noncrossing partition of degree n is considered an (n + 1)-ary operation. The composition law for this operad consists in inserting n + 1 noncrossing partitions into the gaps of a noncrossing partition of degree n. This includes the “outer gaps”, i.e., in front of the whole partition and at the end of it. To any operad is associated a bialgebra (see [16] and [21]), sometimes called its incidence bialgebra, which always has the feature of being “right-sided”, meaning that the coproduct is linear in the left-hand tensor factor but gives monomials in the right-hand tensor factor. We show that this bialgebra is an unshuffle bialgebra (also called codendriform bialgebra), and that the resulting fixpoint equations in the graded dual of the bialgebra are analogous to those of [11]. The second operad is a coloured symmetric operad, whose colours are the positive integers. If a noncrossing partition has k blocks, then it is considered a k-ary operation. The colour of each input slot is the number of elements in the block, and the output colour of the operation is the total number of elements. The composition law for this operad works by substituting a noncrossing partition for a block with the same number of elements. The resulting effect is thus to refine partitions. The incidence bialgebra corresponding to this operad is shown to be closely related to the incidence coalgebra of the lattice of noncrossing partitions in an interesting way: there is a canonical coalgebra homomorphism Φ : B → B from the incidence coalgebra of lat opd the lattice of noncrossing partitions to the incidence bialgebra of the operad. Intervals in the lattice are type equivalent (in the sense of Speicher [40]) precisely when they have the same image under Φ. Möbius inversion in B is induced from that in B , but the latter is closer to what is lat opd actually used in free probability, since it works with the noncrossing partitions themselves instead of intervals of noncrossing partitions. Because of this we can now forget about the lattice, and work directly with the incidence bialgebra of the (block-substitution) operad. The two bialgebras of noncrossing partitions induced by the two operad structures have essentially the same multiplicative basis, both being free on the set of noncrossing partitions. The key point of this work, which allows for the comparison envisaged, is that these two bialgebra structures together form a comodule bialgebra. This is an intricate structure of two interacting bialgebras which recently has appeared in numerical analysis [6], local dynamical systems [10], and stochastic integration and renormalization [5]. Precisely, in Theorem 5.1.1 we establish 3 that the gap-insertion bialgebra is an unshuffle-type bialgebra object in the symmetric monoidal category of comodules for the block-substitution bialgebra. In particular, the block-substitution bialgebra coacts on the gap-insertion bialgebra by bialgebra homomorphisms. An immediate consequence of this is that the convolution algebra of the block-substitution bialgebra acts on the shuffle algebra, i.e., the convolution algebra of the gap-insertion bialgebra. An attractive feature is now that this action is compatible with the splitting of the shuffle product into half- shuffles (Theorem 5.1.2), and therefore with the fixpoint equations mentioned above. Finally the distinguished character (solution to a fixpoint equation) can be convolution-inverted (to provide shuffle logarithms). These can be computed by Möbius-inversion style formulae. Throughout we emphasize noncrossing partitions, since this was our original motivation, but in fact the theory we develop is general enough to cover also the case of ordinary set partitions, so as to get analogous formulae also for classical cumulants. A subtle point for this to work is the Galois connection between the lattice of set partitions and the lattice of noncrossing partitions, which is used to transfer certain noncrossing features to the setting of ordinary partitions, and which also leads to some direct comparisons between classical and free cumulants. In particular this involves the nesting preorder of a partition, and the notions of lowersets and uppersets for partitions. Impetus for this project came from more abstract work by two of the present authors, con- cerned with general relationships between operads and combinatorial Hopf algebras (and bialge- bras). Foissy [17] developed a theoretical framework allowing to understand how quite generally operads equipped with certain B -actions induce comodule bialgebras. In a different line of investigation, Gálvez, Kock and Tonks, in a series of papers starting with [20], developed the notion of decomposition spaces, a general homotopical framework for incidence algebras and Möbius inversion, revealing many classical combinatorial Hopf algebras to be incidence algebras (but not of posets). (This framework covers also operads, via their two-sided bar constructions.) The use of comultiplications to describe convolution products (in combinatorics) goes back to Rota [35]. The importance of Hopf algebra structure rather than just coalgebra structure was stressed by Schmitt [37]. In the more specific context of non-commutative probability theory, various authors have recently exploited Hopf algebras from different perspectives. We briefly mention the works of Friedrich–McKay [18], Hasebe–Lehner [23], Mastnak–Nica [32], Gabriel [19], and Manzel–Schürmann [31]. The precise relations to [11, 12, 14, 13] are not yet fully understood. Operadic approaches to moment-cumulant formulae have been exploited in other ways in recent years. Josuat-Vergès, Menous, Novelli, and Thibon [24] studied the (free) operad of Schröder trees to obtain an operadic version of the half-shuffle equations of Ebrahimi-Fard and Patras [11], and also related this to Speicher’s original formulae [40]. They do not, however, consider operad structures directly on noncrossing partitions. Proposition 3.1.4 below gives an explicit presentation of our gap-insertion operad in terms of generators (corolla trees) and relations, premonished by the way Schröder trees are shown to encode noncrossing partitions in [24]. Their encoding becomes an operad map from the Schröder operad to our gap-insertion operad of noncrossing partitions. A different operadic viewpoint on free moment-cumulant relations was taken by Drummond- Cole [8, 9], who gave an operadic interpretation of Speicher’s multiplicativity [40], and exhibited the free moment-cumulant relations in terms of convolution of maps from a cooperad to an endo- morphism operad. Again, the operads and cooperads considered are not directly on noncrossing partitions, but rather on auxiliary classes of decorated trees. Finally we mention the traffic spaces of Male [29]; these are defined as algebras for a cer- tain operad of graph operations. While this is a very general framework, the operad of graph operations does not seem to specialize directly to any of the main constructions of the present work. Acknowledgments: We would like to thank G. Drummond-Cole, F. Lehner, and R. Speicher for fruitful discussions. This research project received financial support from the CNRS Program 4 PICS 07376: «Algèbres de Hopf combinatoires et probabilités non commutatives». We also thank the Centre de Recerca Matemàtica (CRM) in Barcelona for its hospitality. J.K. was supported by grants MTM2016-80439-P (AEI/FEDER, UE) of Spain and 2017-SGR-1725 of Catalonia. This work was partially supported by the project Pure Mathematics in Norway, funded by Bergen Research Foundation and Tromsø Research Foundation and by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation program (grant agreement No.670624). 2 Partitions and noncrossing partitions — notation and conven- tions This section introduces notation and conventions and briefly recalls some basic notions related to set partitions. 2.1 Definitions 1. We denote by K a commutative base field of characteristic zero. All algebraic objects in this work, such as vector spaces, algebras, coalgebras, pre-Lie algebras, etc., will be defined over K. For algebras with an augmentation ε : A → K, we write A := Ker ε for the augmentation ideal. 2. By N we denote the linearly ordered set of non-negative integers, and by N the set of positive integers. For n ∈N , we denote by [n] the set {1, 2, 3, . . . , n} = J1, nK. For a finite subset X = {x , . . . , x } ⊂ N, we write ♯X = k for its cardinality, and we write 1 k X + n for the n-shifted subset {x + n, . . . , x + n}. Let X be a finite, linearly ordered set. A partition of X into disjoint subsets π , i = 1, . . . , k (called blocks) is written P = {π , . . . , π }. If the order on the set of blocks matters we will write 1 k it as a sequence, (π , . . . , π ), and call it a composition instead of a partition. The degree of the 1 k partition or the composition is the cardinality of X. Except when otherwise stated, partitions are ordered by coarsening: P ≤ Q means that P is finer than Q. For the purposes of this paper, it is important to require a linear order on all underlying sets that are partitioned. Many notions (in particular the notion of noncrossing partition) depend crucially on this linear order, but do not depend on the specific underlying set. This is to say we are only interested in set partitions up to isomorphism. An isomorphism between two partitions is a monotone bijection of the underlying linearly ordered sets compatible with the block structure (and for compositions also with the order on the set of blocks). It is clear that every partition (or composition) is uniquely isomorphic to one with underlying linearly ordered set [n] = {1, 2, . . . , n}, for some n ∈ N. These are called standard partitions, and the process of replacing a partition with this standard representative of its isomorphism class (iso- class) is often called standardization. It is convenient most of the time to work with the standard representatives of each class. When non-standard representatives arise in the constructions (such as when considering subsets of [n]), it must be remembered that it is only the isomorphism class that matters. Working with iso-classes rather than restricting to standardized partitions gets us closer to the combinatorial intuition conveyed by the common pictorial representation of set partitions by block diagrams exploited throughout. (Standardization could always be performed as desired for convenience, but does not affect the validity of the constructions.) The terminology is by analogy with integer compositions: a composition of an integer n is a sequence of non-zero integers (n , . . . , n ) such that n = n + · · · + n . 1 k 1 k 5 ∗ For k, n ∈ N , we denote by SP(k, n) the set of iso-classes of partitions of n-element sets into k blocks. The set SP(0, 0) contains only the empty partition. We put: G G SP = SP(k, n), SP(n) = SP(k, n), SP = SP(0, 0)⊔ SP . 1≤k≤n k≤n When referring to a member of any of these sets, we shall always pick the standard representative, having underlying set [n]. Given a monotone inclusion of linearly orderd sets X ⊂ Y , and given a partition P = {π , . . . , π } of Y , we write P for the induced partition of X (whose blocks are the non-empty 1 k |X intersections π ∩ X). Definition 2.1.1. Let X be a non-empty, finite subset of N (or of an arbitrary linearly ordered set Y ). The convex hull of X is by definition Conv(X) = Jmin(X), max(X)K. We shall say that X is convex if Conv(X) = X. Any finite subset X ⊂ N decomposes uniquely as X = X ⊔···⊔ X 1 k with each X convex and each X ⊔X not convex for i 6= j. The X , . . . , X are called the convex i i j 1 k components of X. Definition 2.1.2 (Noncrossing partitions). A partition P = {π , . . . , π } is called noncross- 1 k ing when there are no a, b ∈ π , c, d ∈ π with i 6= j such that a < c < b < d. For example, i j {{1},{2, 4},{3}} = is noncrossing, whereas {{1, 3},{2, 4}} = is crossing. For k, n ∈ N , we denote by NCP(k, n) the set of iso-classes of noncrossing partitions of an n-element set into k blocks. The set NCP(0, 0) contains only the empty partition. We put: G G NCP = NCP(k, n), NCP(n) = NCP(k, n), NCP = NCP(0, 0)⊔ NCP . 1≤k≤n k≤n Note that if X ⊂ [n] and P is a noncrossing partition of [n] then P is a noncrossing partition |X of X. Definition 2.1.3 (Noncrossing closure). The noncrossing closure of a set partition P = {π , . . . , π } of degree n, written nc(P ), is the noncrossing partition defined by 1 k nc(P ) := min{Q ∈ NCP(n) | P ≤ Q}. Here P ≤ Q means that P is finer than Q. In plain words, nc joins any two blocks that cross. For example, nc( ) = . Anticipating the two operads that we will define on partitions, we note that nc preserves the degree of a partition. It will therefore be useful in connection with the gap-insertion operad. In contrast, it does not preserve the number of blocks, and for this reason will not play any role for the block-substitution operads. Remark 2.1.4. Throughout this paper we work with “naked” partitions, like the ones intro- duced above. However, we wish to stress that all the constructions and results go through with partitions decorated by elements from an alphabet A. By this we mean that each partition — with underlying linearly ordered set X, say — is equipped with a map a : X → A (not required to be injective), pictured as a a 2 3 a a 1 4 6 These decorations do not interfere with any of the operations we shall perform on partitions. For example, a decoration transfers canonically along monotone bijections (such as standardization): if X → A is a decoration, and [n] → X is the unique monotone bijection performing the standardization, then the decoration of the standardized partition is simply the composite map [n] → X → A. The decorated situation is relevant in probability theory where the a will be random variables. Since such decorations do not interfere with the theory we develop, for the sake of simplicity we prefer to stick with “naked” partitions, which can be regarded the univariate case, that is, of a single random variable. The only place where we shall need to refer to decorations is in Proposition 5.2.6 where we comment on relations with the double tensor algebra (over a probability space A). 3 Gap-insertion operad and associated structures We describe here a series of algebraic structures on set partitions arising from the idea of “inserting a partition into another partition”. We start with the basic insertion operation, naturally encoded by an operad structure, and then turn to the definition of further associated algebraic structures on partitions, such as unshuffle coproducts and Hopf algebras. In order to give an explicit combinatorial description of the bialgebra structure resulting from the operad, we exploit a preorder on the set of blocks of a given partition, and the attendant notions of lowerset and upperset. These notions are quite standard in the context of noncrossing partitions, but less so for general partitions — it is indeed tailored to study the relations between the two settings. Before presenting the gap-insertion operad, we briefly recall that a non-symmetric, single- coloured set operad P is a sequence of sets P(n), n ∈ N, equipped with a unit operation I ∈ P(1) and a composition law: P(r) × (P(n )×···×P(n )) → P(n +··· + n ) 1 r 1 r (p, (q , . . . , q )) 7→ p◦ (q , . . . , q ), 1 r 1 r for r ∈ N and n , . . . , n ∈N, satisfying the axioms 1 r I ◦ (q) = q, p◦ (I, . . . , I) = p, and 1 1 r r 1 1 r r p◦ (q , . . . , q ) ◦ (h , . . . , h , . . . , h , . . . , h ) = p◦ q ◦ (h , . . . , h ), . . . , q ◦ (h , . . . , h ) . 1 r 1 r 1 n 1 n 1 n 1 n 1 r 1 r An operad P is reduced if P(0) = ∅, that is, it has no nullary operations. Equivalently, an operad can be defined using the notion of “partial composition law” ◦ : P(m)×P(n) → P(m + n− 1), i = 1, . . . , m, where p◦ q := p◦ (I, . . . , I, q, I, . . . , I), with q located in position i. A set operad gives rise to an operad in the category of vector spaces by replacing sets by the vector spaces they span, and cartesian products of sets by tensor products of vector spaces. The term positive operad is also used [1]. 7 3.1 A non-symmetric single-colour operad of partitions The idea of the notion of gap-insertion operad on partitions, which we proceed to define, is easy (when displaying a partition pictorially): each partition P ∈ SP(n) (or noncrossing partition P ∈ NCP(n)) is considered an operation of arity n + 1, its input slots being the n + 1 gaps between the elements, including the “gap” before 1 and the “gap” after n. It can thus receive n + 1 other partitions (or noncrossing partitions) Q , . . . , Q , which are simply inserted into 1 n+1 the gaps. For example, inserting the partition {{1, 2}} between 2 and 3 into {{1, 2, 3}} gives the partition {{1, 2, 5},{3, 4}} and reads pictorially: ⋄ = where ⋄ denotes the partial composition law. Conceptually it is clear that this defines an operad. Formalising it just requires appropriate reindexing of the elements in the underlying sets. If P is noncrossing and Q , . . . , Q are all noncrossing, then it is clear that the result is again 1 n+1 noncrossing (as in the example just given). It is simpler to describe the operad structure from the partial composition law viewpoint: Definition 3.1.1 (The gap-insertion operad). We set SP(n) := SP(n − 1), in particular, SP(0) = ∅ (so that the operad will be reduced) and SP(1) = {∅}; the empty partition will be the operad unit. This sequence of sets is given a unital non-symmetric operadic structure as follows: for P = {π , . . . , π } ∈ SP(m) and Q = {ρ , . . . , ρ } ∈ SP(n), we define the partial 1 k 1 l composition law (for i = 1, . . . , m) by: P ⋄ Q := {χ(π ), . . . , χ(π ), ρ + i− 1, . . . , ρ + i− 1}, i 1 k 1 l where χ(p) := p if p < i, χ(p) := p + n − 1 else. Equivalently: given a sequence of partitions P ∈ SP(m), Q ∈ SP(n ), . . . , Q ∈ SP(n ), the composition law is 1 1 m m P ⋄ Q := γ(P )∪ Q ∪ Q + n ∪···∪ Q + n +··· + n , (1) 1 2 1 m 1 m−1 where γ(i) := n +··· + n . 1 i Example. 1) {1, 2, 3} ⋄ {1};{2} = {1, 2, 5};{3};{4} . Pictorially: ⋄ = 2) {1, 2, 3} ⋄ {1};{2, 3} , {1, 2} , {1};{2} , {1, 2, 3, 4} = {1};{2, 3};{4, 7, 10};{5, 6};{8};{9};{11, 12, 13, 14} . Pictorially: ⋄ ( , , , ) = As already observed, the set of noncrossing partitions is stable under the composition law of the operad SP: Lemma 3.1.2. The sequence NCP(n) := NCP(n− 1), equipped with the composition law ⋄, defines a set operad called the noncrossing gap-insertion operad. 8 Since the composition laws ⋄ of the two operads SP and NCP work by insertion into gaps, and since neither the inclusion nor the noncrossing closure operator (see 2.1.3) changes those gaps, the following is straightforward to check: nc Lemma 3.1.3. Both maps NCP SP induce morphisms of operads, nc NCP SP, exhibiting NCP as a retract of SP. The noncrossing gap-insertion operad admits the following simple presentation in terms of generators and relations. Proposition 3.1.4. For any n ≥ 2, we put p = {[n − 1]} ∈ NCP(n). Then the operad (NCP,⋄) is generated by the elements p , n ≥ 2, with the relations: ∀m, n ≥ 2, p ⋄ p = p ⋄ p . m m n n 1 m This result (and its corollary below) is not essential for later developments in this article, and we therefore limit ourselves to a short proof assuming some familiarity with the theory of operads. Proof. Firstly, for any m, n ≥ 2, p ⋄ p = {[m− 1], [n− 1]} = p ⋄ p . (2) m m n n 1 m We denote by (Q,◦) the non-symmetric operad generated by the elements q , m ≥ 2, with these relations. Classically, one represents an m-ary operation q by a corolla with m leaves, and elements of the non-symmetric operad freely generated by these elements by planar rooted trees. Since (2) holds in NCP, there exists a unique operad morphism Θ : Q −→ NCP sending q to p , for m ≥ 2. Let us prove that Θ is surjective. Let π = {π , . . . , π } ∈ NCP(k, n − 1), we prove that it 1 k belongs to Θ(Q(n)) using induction on k. If k = 1, we have π = Θ(q ). Otherwise, assume that the block containing 1 is π and that it is of cardinality l− 1. Then there exist noncrossing (2) (l) partitions π , . . . , π such that (2) (l) π = p ⋄ (I, π , . . . , π ). (i) (i) The number of blocks of π is strictly smaller than k, so for any i there exist q ∈ Q such that (i) (i) π = Θ(q ). Hence: (2) (l) (2) (l) π = Θ(q )⋄ (I, Θ(q ), . . . , Θ(q )) = Θ(q ◦ (I, q , . . . , q )). l l Since for any n, the nth component of the free non-symmetric operad generated by the elements q identifies with the set of planar rooted trees with n leaves, to obtain Q, one has to quotient by the relations m n m-1 n-1 = , so (by a simple recursion) the quotient Q(n) identifies with the set of planar rooted trees with n leaves such that for any internal vertex v, the leftmost child of v is a leaf. The number of such 1 2n−2 trees is the Catalan number cat = , so ♯(Q(n)) ≤ cat = ♯(NCP(n)). Therefore, Θ is n n n n−1 bijective. Corollary 3.1.5. NCP-algebras are vector spaces V carrying for any n ≥ 2 an n-multilinear map h−, . . . ,−i such that for any m, n ≥ 2, and x , . . . , x ∈ V : 1 m+n−1 hx , . . . , x ,hx , . . . , x ii = hhx , . . . , x i, x , . . . , x i. 1 m−1 m m+n−1 1 m m+1 m+n−1 9 3.2 Induced brace algebra structures The operad structure on SP and NCP induces various algebraic structures on the free vector spaces. The ones in this section are not directly used in this paper, but we mention them briefly, for the sake of completeness, and since a brace algebra structure on fundamental objects such as partitions or noncrossing partitions can be expected to have meaningful applications (recall that brace algebras are useful in the study of algebraic structures up to homotopy, for example on the Hochschild complex [22]). The reader is referred to [17] for details, proofs and further references. L L ⊗n + ⊗n Denote by T (V ) := V the tensor algebra over V , and by T (V ) := V its n∈N n∈N augmentation ideal. We use word notation v . . . v for the tensors v ⊗··· ⊗ v in T (V ), and 1 n 1 n ⊗0 write 1 ∈ V for the empty word. Definition 3.2.1. A brace algebra is a vector space V equipped with a linear map: {−,−} from V ⊗ T (V ) to V such that: • ∀v ∈ V, {v,1} = v. • ∀v, y , . . . , y ∈ V,∀w ∈ T (V ) : 1 k {{v, y . . . y }, w} = {v, w {y , w }w . . . w {y , w }w }, 1 k 1 1 2 3 2k−1 k 2k 2k+1 w=w ...w 2k+1 where the sum on the right runs over all decompositions of the word w as a concatenation product of (possibly empty) subwords. Brace algebras were introduced to encode the properties of composition laws in operads. In particular (see [17, Chap. 3] for a proof): Lemma 3.2.2. The vector spaces SP and NCP spanned by partitions respectively noncross- ing partitions, carry a brace algebra structure by the following operations: ∀p ∈ SP(n), p , . . . , p ∈ 1 k SP: {p, p . . . p } := p◦ (I, . . . , I, p , I, . . . , I, p , I, . . . , I), 1 k 1 k 1≤i <···<i ≤n 1 k where on the right-hand side p is located in position i . l l For example, for p = {{1, 2}}, p = {{1}}, p = {{1, 2, 3}}, we get 1 2 {p, p p } = {{2, 6},{1},{3, 4, 5}} +{{2, 3},{1},{4, 5, 6}} +{{1, 3},{2},{4, 5, 6}}. 1 2 The deconcatenation coproduct of a word n−1 Δ(v . . . v ) := v . . . v ⊗ 1 + 1⊗ v . . . v + v . . . v ⊗ v . . . v 1 n 1 n 1 n 1 i i+1 n i=1 equips T (V ) with the structure of a connected graded coalgebra. If an associative product ∗ : T (V )⊗ T (V ) → T (V ) with unit 1 equips (T (V ),∗, Δ) with the ⊗n ⊗m structure of a bialgebra and the restrictions of ∗ (on the image) to maps { , } : V ⊗V → n,m ⊗m V are null when n > 1 and m > 0, then the maps { , } : V ⊗ V → V define a brace 1,m algebra structure on V . The converse assertion is also true. Indeed, a brace algebra structure on V defines uniquely a bialgebra structure on T (V ) with these properties (the two categories are equivalent, as follows from the fact that (T (V ), Δ) is the cofree (coaugmented conilpotent) coassociative coalgebra over V in the category of connected graded coalgebras). 10 Proposition 3.2.3. The product ∗ on T (SP) (and, by restriction, on T (NCP)) is obtained from the brace operations as follows. Given a non-empty sequence of set partitions Q , . . . , Q 1 n written in word notation W = Q . . . Q , then for all P , . . . , P ∈ SP: 1 n 1 k P . . . P ∗ W := W {P , W }W . . . W {P , W }W . 1 k 1 1 2 3 2k−1 k 2k 2k+1 W =W ...W 2k+1 Remark 3.2.4. The product ∗ is a non-commutative shuffle product (also called dendriform product), meaning that it splits into two half-shuffle products (∗ =≺ + ≻): P . . . P ≺ W := {P , W }W . . . W {P , W }W , 1 k 1 1 2 2k−2 k 2k−1 2k W =W ...W 2k P . . . P ≻ W := W {P , W }W . . . W {P , W }W 1 k 1 1 2 3 2k−1 k 2k 2k+1 W =W ...W 1 2k+1 W 6=∅ that satisfy the Eilenberg–Mac Lane shuffle relations: (U ≺ V ) ≺ W = U ≺ (V ∗ W ) (3) U ≻ (V ≺ W ) = (U ≻ V ) ≺ W (4) U ≻ (V ≻ W ) = (U ∗ V ) ≻ W. (5) These constructions are functorial. In particular, the embedding of NCP into SP and its left inverse, the noncrossing closure, induce homomorphisms of brace algebras (and of the associated algebraic structures). 3.3 Induced bialgebras and Hopf algebras To any (non-symmetric) operad P (subject to suitable finiteness conditions), there is associated a canonical bialgebra, whose algebra structure is the free algebra on the set of all operations. (This is sometimes called the incidence bialgebra of the operad.) The coproduct of an operation R is defined as Δ(R) = P ⊗ Q ··· Q . 1 k R=P◦(Q ,...,Q ) In plain words, the coproduct is given by summing over all the ways R could have arisen from the composition law, and then putting the receiving operation P on the left and the monomial of all the operations fed into P on the right. This bialgebra is graded (by arity-minus-one), but is never connected, and hence not Hopf. Indeed, degree zero contains all monomials in the operad unit. But one can obtain a Hopf algebra by passing to the quotient defined by dividing out by the coideal generated by u−1 for all unary operations u. (In the cases of interest here, the only unary operation is the empty partition.) These constructions can be described in various formal ways, for example following from a general process described in [17], applied to the symmetrization of P (the constructions are ∗ ∗ denoted D and B in that article), or via the so-called two-sided bar construction, as exploited P P in [26]. There will thus be four bialgebras, of which two are Hopf: • For general set partitions: we shall denote by S the bialgebra induced by the operad SP, and by S its connected quotient. • For noncrossing partitions: we shall denote by N the sub-bialgebra of S induced by the 0 0 sub-operad NCP ⊂ SP, and by N its connected quotient (a sub Hopf algebra of S). 11 Altogether these four bialgebras fit together by bialgebra homomorphisms like this: N S 0 0 N S The Hopf algebra N associated to NCP was introduced in [12]. The arguments given there could be adapted to establish the bialgebra axioms also for the other three cases. Our aim here is to describe these bialgebras and Hopf algebras in purely elementary and combinatorial terms for the particular cases of the set-partitions operad SP and the noncrossing partitions operad NCP (in both cases with the gap-insertion composition law). As an algebra, S is the free associative algebra generated by SP : it is spanned linearly by 0 0 sequences of partitions, some of which are possibly empty. The algebra S is the free associative algebra generated by SP, identified with the quotient of S by the ideal generated by ∅− 1. As an algebra, N is the free associative algebra generated by NCP : it is spanned linearly by 0 0 sequences of noncrossing partitions, some of which are possibly empty. The algebra N is the free associative algebra generated by NCP, identified with the quotient of N by the ideal generated by ∅− 1. The products on S , N , N and S are denoted by ·. In order to describe the coproducts Δ 0 0 0 and Δ of S respectively S (they restrict to the coproducts on the bialgebra N and the Hopf 0 0 algebra N associated to NCP), we need some further preliminaries regarding partitions. Let P = {π , . . . , π } be a partition of a linearly ordered set X. The set of blocks of P carries 1 k a reflexive relation defined by declaring π→ρ to mean that Conv(π) ∩ ρ 6= ∅. In plain words, π ρ means that either ρ is nested inside π or that the two blocks cross. In the latter case we have also ρ→ π, which shows that in general the relation → is not antisymmetric. We also write P P abusively → for the transitive closure of the relation (which does not always define a poset). This preorder will play an essential role for allowing the noncrossing and general partitions to be treated on equal footing in the following algebraic constructions. Note immediately that Lemma 3.3.1. A partition P is noncrossing if and only if the associated preorder → is actually a poset (i.e. is an antisymmetric relation). The standard notions of lowerset and upperset for a preorder will be important for → , so let us recall: Definition 3.3.2 (Upperset and lowerset). An upperset of a partition P is a subset U of the set of blocks such that if π ∈ U and π ρ in P then also ρ ∈ U. In plain words, if a block is in U then all nested blocks and all blocks crossing it are also in U. Similarly, a lowerset of P is a subset L of the set of blocks such that if π ∈ U and σ→ π in P then also σ ∈ U. In plain words, if a block is in L then all englobing blocks and all blocks crossing it are also in L. Remark 3.3.3. If a partition P is noncrossing, then all its lowersets and uppersets are again noncrossing. The following is obvious (and holds in any preorder). Lemma 3.3.4. If U is an upperset of P then the complement set of blocks U is a lowerset. If L is a lowerset of P then the complement set of blocks L is an upperset. 12 Definition 3.3.5 (Cut). A cut of a partition P is a splitting of the set of blocks into a lowerset L and an upperset U. We write (L, U) ∈ cut(P ) to express this situation. Note that by Lemma 3.3.4 a cut is completely determined by specifying either a lowerset or an upperset. The following picture illustrates the notion of cut: 1 2 3 4 5 6 7 8 9 Remark 3.3.6. If P is a partition with a cut (L, U), and if π and π are two crossing blocks, then either they both belong to L or they both belong to U. Corollary 3.3.7. If two partitions have the same noncrossing closure (as in 2.1.3), then there is a natural bijection between their sets of cuts. The following more refined version of the complement L is specific to partitions, and is the key to giving a direct combinatorial description of the coproduct Δ . Lemma 3.3.8. A lowerset L of P defines canonically a list of uppersets U , . . . , U whose union is L . (Here k is the cardinality of the underlying set of ∪ π.) π∈L For the picture above, the resulting list of uppersets is ∅ · · ∅ · ∅ · · ∅ 2 3 4 8 (with monomial “dot” notation, as will be used later). Proof. Let {x , . . . , x } denote the underlying set of the lowerset L. Since the underlying set [n] 1 k of P is linearly ordered, these k points define k + 1 (possibly empty) intervals in [n], denoted D , . . . , D , where D := {y ∈ [n] | y < x } and D := {y ∈ [n] | y > x }. The intervening 0 k 0 1 k k intervals are D := {y ∈ [n] | x < y < x }. The promised uppersets are simply the restrictions i i i+1 U := P , for i = 0, . . . , k. To see that this is meaningful, note first that each D is a union i i |D of blocks of P , because the lowerset condition on L prevents the blocks in the complement from straddling any of the points x . Second, since we are inside the complement U := L , we have U = P = U , and the restriction of an upperset is an upperset. i |D |D i i Remark 3.3.9. Note that the U are either empty or are the convex components of the underlying set of U in the sense of Definition 2.1.1. Definition 3.3.10 (Gap monomial). For U an upperset, we define the gap monomial to be the monomial in S given by U := U ··· U 0 k Here, U , . . . , U is the list of uppersets defined by the lowerset U as in Lemma 3.3.8. ... We also define the reduced gap monomial U to be the class of U in S, that is, the monomial obtained from U by omitting those entries in the list that are empty partitions. This can also be characterized as the monomial of the convex components of the underlying set of U. With the concepts and notations just introduced, we can now give the following interpretation of the operadic composition law: P ⋄ (Q , . . . , Q ) = R 0 k if and only if P is a lowerset of R with complement list of uppersets Q , . . . , Q 0 k 13 This leads to a description of the coproduct in explicit combinatorial terms: Proposition 3.3.11. The coproduct of the incidence bialgebra S of the gap-insertion operad is given by Δ (P ) = L⊗ U. (L,U)∈cut(P ) Here the right-hand tensor factor is the gap monomial of Definition 3.3.10. Corollary 3.3.12. The partitions J := {{1}, . . . ,{n}} ∈ SP(n, n) generate the sub-bialgebra S in S . We refer to the finest partitions J colloquially as “forests of sticks”. Proof. This is clear, as the lowerset and upperset corresponding to a cut in a partition J are again such a partition, respectively a monomial of such partitions. Hence, the coproduct can be written Δ (J ) = J ⊗ J · ···· J . 0 n ♯L n n 0 ♯L L⊆[n] Here J is identified with the empty set. As an illustration: 1 2 3 4 5 corresponds to the tensor product ∅ · ∅ · · ∅ 1 2 5 3 4 in the coproduct Δ (J ). 0 5 Recall that the Hopf algebra S is obtained from S by quotiening by the ideal generated by ∅− 1. Proposition 3.3.13. The coproduct of the reduced incidence Hopf algebra S of the gap- insertion operad is given (for P a nonempty partition) by: ... Δ(P ) = L⊗ U. (L,U)∈cut(P ) The forest of sticks, S , form a sub Hopf algebra in S. ... Here the right-hand tensor factor U is the reduced gap monomial of Definition 3.3.10. The exact same formulae hold for the bialgebras N and N of noncrossing partitions. The sub bi- and Hopf algebras of forests of sticks are denoted N respectively N . Remark 3.3.14. With the cut formulation of the coproduct, a tight analogy with the Butcher–Connes–Kreimer Hopf algebra of rooted trees becomes clear: the way the upperset is split into a monomial is analogous to the way the crown of a tree with a cut is interpreted as a forest. In fact this is more than just an analogy: the underlying poset of a noncrossing partition is actually a forest (in the sense that for any block π, the set {σ | σ π} is a linear order), and the notion of cut is the same as that for forests. In fact: Proposition 3.3.15. The assignment sending a noncrossing partition to its underlying forest defines a bialgebra homomorphism from N to the Butcher–Connes–Kreimer Hopf algebra. 14 In fact, this bialgebra homomorphism factors through the non-commutative Hopf algebra of planar forests of [15]. These four bialgebras are N -graded: the bidegree of a partition P of [n] with k blocks is (k, n). (Note that the arity of a degree-n partition is n + 1, but that the bialgebra construction lowers the degree by 1.) Note that the bialgebras S and N are not connected: the degree zero 0 0 component is spanned by all the monomials in ∅. The coarsest partitions are ‘skew-primitive’, meaning for example Δ ( ) = ⊗∅·∅·∅·∅ + ∅⊗ . On the other hand, S and N are connected by construction (and therefore automatically Hopf algebras). For each of the four bialgebras, the counit is given by ε(P ) = 0 for any nonempty partition (or noncrossing partition). Applications in free probability of the theory of partitions and noncrossing partitions suggest to introduce another Hopf algebra map from N to S than the obvious embedding. Proposition 3.3.16. The linear map NCP −→ SP nc : P 7−→ P nc(P )=P defines a bialgebra homomorphism from N to S (and from N to S). 0 0 Proof. This follows since partitions with common noncrossing closure have isomorphic sets of cuts, cf. Corollary 3.3.7. 3.4 Unshuffling coproducts on partitions A (non-commutative) monomial of partitions will also be called a multipartition (resp. noncross- ing multipartition): these are the elements P = P ··· P ∈ S (resp. in N), where for each i ∈ [k], 1 k P is a partition (resp. a noncrossing partition) in SP(n ) (resp. in NCP(n )), n 6= 0. i i i i The set of multipartitions (resp. noncrossing multipartitions) is denoted by SMP (resp. NMP). These elements form a linear basis of S (resp. N). By multiplicativity, we define bigradings SMP(k, n) (NMP(k, n)) for all k, n ≥ 0, where k stands for the total number of blocks. The notions of upperset, lowerset, and cut defined in Subsection 3.3, extend multiplicatively to multi- partitions in a straightforward manner. For example, a lowerset of a multipartition P = P ··· P 1 k is a sequence of lowersets L of each P , written as a monomial L ··· L . i i 1 Moreover, shifting the elements of P by deg(P ), . . ., the elements of P by deg(P ) +··· + 2 1 k 1 deg(P ), such a P can be seen as a family of sets of subsets of [n + ··· + n ] = [n], these k−1 1 k subsets forming a partition of [n]. With these conventions and this identification, which will be used systematically in this section, for any P ∈ SMP or P ∈ NMP as above, the coproducts can be written Δ (P ) = L⊗ U (L,U)∈cut(P ) ... Δ(P ) = L⊗ U. (6) (L,U)∈cut(P ) Here Δ and Δ are extended multiplicatively from single partitions to multipartitions (monomials in partitions) in the usual way. As a result, since P is a multipartition (i.e. a monomial), also L is a monomial. In the right-hand tensor factors, U is itself a monomial for the same reason, and U ... (resp. U) are furthermore “monomials of monomials”, namely the product of the gap monomials (resp. reduced gap monomials), as in Definition 3.3.10. In the following we work only with Δ. 15 Definition 3.4.1 (Unshuffle structure). For any non-empty P ∈ SMP we put: ... Δ (P ) = L⊗ U, (L,U)∈cut(P ) 1∈L X ... Δ (P ) = L⊗ U. (L,U)∈cut(P ) 1∈U ... Here the L are the lowerset monomials of the multipartition P , whereas the U are the reduced gap monomials of each cut, as in Definition 3.3.10. These definitions restrict to (non-empty) noncrossing partitions. Remark 3.4.2. It follows from Remark 3.3.6 that the multiplicative extension to a map from NCP to SMP of the map nc from Proposition 3.3.16 commutes with these three operations. Proposition 3.4.3 (Unshuffle Hopf algebra structures). The two coproducts just defined, on the augmentation ideals S ⊂ S and N ⊂ N, turn S and N into unshuffle Hopf algebras (also + + called codendriform Hopf algebras [16]). In detail, these coproducts satisfy the dual of the shuffle relations (3)–(5): (Δ ⊗ Id)◦ Δ = (Id⊗Δ)◦ Δ , (7) ≺ ≺ ≺ (Δ ⊗ Id)◦ Δ = (Id⊗Δ )◦ Δ , ≻ ≺ ≺ ≻ (Δ⊗ Id)◦ Δ = (Id⊗Δ )◦ Δ . ≻ ≻ ≻ Moreover, for any x, y ∈ S , introducing Sweedler-like notation for these three coproducts: ′ ′′ Δ (x) = x⊗ 1 + x ⊗ x ≺ ≺ ′ ′′ Δ (x) = 1⊗ x + x ⊗ x ≻ ≻ ′ ′′ Δ(y) = y ⊗ 1 + 1⊗ y + y ⊗ y , we have ′ ′′ ′ ′′ ′ ′′ ′ ′ ′′ ′′ Δ (x· y) = x· y ⊗ 1 + x⊗ y + x· y ⊗ y + x · y ⊗ x + x ⊗ x · y + x · y ⊗ x · y , ≺ ≺ ≺ ≺ ≺ ≺ ′ ′′ ′ ′′ ′ ′′ ′ ′ ′′ ′′ Δ (x· y) = 1⊗ x· y + y ⊗ x + y ⊗ x· y + x · y ⊗ x + x ⊗ x · y + x · y ⊗ x · y . ≻ ≻ ≻ ≻ ≻ ≻ ′ ′ ′′ We have used Sweedler-type notations for the reduced coproducts, i.e., Δ (x) := x ⊗ x , ≺ ≺ ≺ ′ ′ ′′ ′ ′ ′′ Δ (x) := x ⊗ x and Δ (x) := x ⊗ x . ≻ ≻ ≻ Proof. We briefly comment on the coproduct (6) and its splitting, Δ = Δ + Δ , satisfying the ≺ ≻ shuffle relations. For more details the reader is referred to [12]. Starting from P ∈ SMP(k, n), with k ≥ 1 each cut (L, U) ∈ cut(P ) in the definition of the coproduct (6) corresponds to a decomposition of P into a lowerset L and an upperset U, which are the complements of each other. Recall that U and L are partitions themselves. We shall need compatible pairs of cuts, writing (L, M, U) ∈ cut (P ) for the situation where L is a lowerset of P and U is an upperset c c of P , with complements L = M ⊔ U and U = L⊔ M. (Coassociativity amounts to saying that the last two conditions are equivalent.) The shuffle identities are then checked by keeping track of the first element 1 ∈ P : ... ... (Δ ⊗ Id)◦ Δ (P ) = L⊗ M ⊗ U = (Id⊗Δ)◦ Δ (P ), ≺ ≺ ≺ (U,M,L)∈cut (P ) 1∈L X ... ... (Δ ⊗ Id)◦ Δ (P ) = L⊗ M ⊗ U = (Id⊗Δ )◦ Δ (P ), ≻ ≺ ≺ ≻ (U,M,L)∈cut (P ) 1∈M 16 X ... ... (Δ⊗ Id)◦ Δ (P ) = L⊗ M ⊗ U = (Id⊗Δ )◦ Δ (P ). ≻ ≻ ≻ (U,M,L)∈cut (P ) 1∈U ... ... (Here L is a monomial just because P is, whereas M and U are reduced gap monomials, as in Definition 3.3.10.) The compatibility between Δ , Δ and the product · follows by the ≺ ≻ multiplicative extension of Δ , Δ implied by Definition 3.4.1. ≺ ≻ Notice that the three coproducts Δ, Δ , Δ dualize respectively to the products denoted ≺ ≻ ∗ ∗ ∗,≺,≻ on S and N . It follows from Proposition 3.4.3 that the latter satisfy the shuffle + + identities (3)–(5). 3.5 Moments and cumulants In this subsection we briefly revisit the relations between classical cumulants and free cumulants in the context of free probability, a point usually addressed using the properties of the inclusion of the lattice of noncrossing partitions into the one of partitions [28]. We use freely the results of [12] and restrict the study to the case of a single free random variable; this allows us to consider solely computations with formal power series. The multivariate case can be addressed with exactly the same tools using the techniques in [12]. Recall that a classical probability space is a pair (A, ϕ) where A is a commutative ring of random variables and ϕ a unital linear form on it called the expectation. The moments of a n ∗ random variable a ∈ A are defined as m := ϕ(a ), n ∈ N . The moment-generating function is the associated exponential series E(z) := 1 + m , and the classical cumulants {c } n n n≥1 n≥1 n! are defined as the coefficients of the cumulant-generating function C(z) = c given by n≥1 n! the formulae C(z) := log(E(z)), E(z) = exp(C(z)). In free probability [34], the ring A is not necessarily commutative, and an element a ∈ A is interpreted as a non-commutative random variable. The moments are defined as in the classical case, but the free cumulants {k } are defined instead using the ordinary generating series n n≥1 X X n n M(z) := 1 + m z and K(z) := k z , n n n≥1 n≥1 related through the fixpoint formula M(z) = 1 + K(zM(z)). For various reasons (see for example [34]), it is fruitful to lift these relations to the framework of set partitions. As far as classical cumulants are concerned, the moment-cumulant relations translate into m = c , (8) n P P∈SP(n) where, for P := {π , . . . , π } ∈ SP(n), 1 k c := c . P ♯π i≤k For free cumulants, Speicher showed that one has instead m = k , (9) n Q Q∈NCP(n) where, for Q = {τ , . . . , τ } ∈ NCP(n), 1 k k := k . Q ♯τ i≤k 17 From the properties of the embedding NCP ⊂ SP, one can derive (see [28]) that k = c . Q P nc(P )=Q In other words, if k and c are extended to linear functions on NCP, respectively SP, we arrive at the following fundamental relation between free and classical cumulants k = c◦ nc , (10) where nc was defined in Proposition 3.3.16. As mentioned in the introduction, the papers [11, 13, 14] proposed an approach to the re- lations between moments and free cumulants, which is based on a non-commutative shuffle bialgebra structure [16] on the dual of a particular connected, graded, non-commutative, non- cocommutative Hopf algebra H of words constructed as the double tensor algebra from (A, ϕ). The group of characters and the corresponding Lie algebra of infinitesimal characters over this Hopf algebra can then be shown to be related by three naturally defined exponential-type maps and the corresponding logarithms. The unital linear map ϕ, which is part of the data of a non-commutative probability space (A, ϕ), induces a particular Hopf algebra character on H. One can show that the three logarithms applied to this character encode the three families of monotone, free, and boolean cumulants as infinitesimal Hopf algebra characters. This algebraic setting allows to recover many of the results and formulas in Speicher’s approach, although the lattice of noncrossing partitions plays a rather marginal role. Indeed, noncrossing partitions appear only after evaluating the Hopf algebra character corresponding to ϕ on elements of H. In [12] these results were transferred to the Hopf algebra N defined on noncrossing partitions in the following way. Define the linear form κ on N to be zero on all noncrossing multipartitions in NMP(k, n) for k > 1 and by κ([n]) := k else. Solving the half-shuffle fixpoint equation in the graded dual N : φ = ε + κ ≺ φ, (11) where ε is the counit of N (it is essentially the Kronecker delta ε (P ) := δ ), one obtains N N P,∅ a character which evaluates any noncrossing partition Q to φ(Q) = k , i.e., it maps Q to the product of cumulants for each block in Q. Therefore, the nth moment is obtained as m = φ(Q). We shall see in Proposition 5.2.5 that (11) and the sum formula for m find Q∈NCP(n) a more natural expression in terms of the bialgebra interaction we introduce in this paper. We can thus interpret Equation (11) as an algebraic lift of (9). Define now a linear form γ on S by γ(Q) := c if Q is a partition of [n] such that nc(Q) = [n], and to be zero on all other partitions and multipartitions. Since k = c , n P P ∈SP(n) nc(P )=[n] we obtain that κ = γ ◦ nc . Proposition 3.5.1. With γ defined as above, the solution ψ to the half-shuffle fixpoint equa- tion in the graded dual S ψ = 1 + γ ≺ ψ (12) is such that φ = ψ ◦ nc . (13) In particular, m = ψ(P ) and equations (12) and (13) can be interpreted as alge- P∈SP(n) braic and operadic lifts of the classical moment-cumulant formula, respectively formula (10). ∗ ∗ Proof. The proposition follows from the identity κ = γ ◦ nc and the fact that nc commutes with Δ defined in Proposition 3.4.3. 18 4 Block-substitution operad and associated structures We introduce now a second family of operads and algebraic structures on partitions and non- crossing partitions. We shall see that they are closely related to the lattice properties of the two families of partitions. Before presenting the block-substitution operad, we briefly recall that a coloured symmetric set operad P is given by: • A set of colours C; n+1 • For each n ∈ N, and each (n + 1)-tuple of colours (c , . . . , c ; c) ∈ C , a set of n-ary 1 n operations P(c , . . . , c ; c); 1 n • For each colour c ∈ C, an identity operation id ∈ P(c; c); • An operadic composition law P(c , . . . , c ; c) × P(d , . . . , d ; c )×···×P(d , . . . , d ; c ) 1 k 1,1 1,i 1 k,1 k,i k 1 k P(d , . . . , d , . . . , d , . . . , d ; c) 1,1 1,i k,1 k,i 1 k denoted (p, (q , . . . , q )) 7−→ p◦ (q , . . . , q ), 1 k 1 k n+1 • For each n ∈ N, for each (c , . . . , c ; c) ∈ C , and for each permutation σ ∈ S , a map 1 n n P(c , . . . , c ; c) → P(c , . . . , c ; c) 1 n σ(1) σ(n) denoted P 7→ P . This data is subject to axioms completely analogous to the ordinary operad axioms: there is an associative axiom, a unit axiom (for each identity operation), and a symmetry axiom. It is simply a typed version of the notion of operad, where the composition law requires strict type-checking in terms of colours: an operation can be substituted into an input slot of another operation if and only if its output colour matches the colour of the receiving input slot. A coloured operad P is reduced if it has no nullary operations. Example 4.0.1. A small category is the same thing as a coloured operad with only unary operations. The objects are then the colours, and the arrows are the operations (with domain as input colour and codomain as output colour). 4.1 A coloured symmetric operad of compositions Central objects in this work are the block-substitution operads SC of set partitions and NCC of noncrossing partitions, which we define in this subsection. They are both coloured symmetric operads with colour setN . We concentrate here on the ordinary partitions, since the noncrossing condition is orthogonal to the constructions, cf. Proposition 4.1.2 below. The idea is simple: a (non-empty) partition P = {π , . . . , π } with k blocks is considered a k- 1 k ary operation. Its output colour is the number of elements of the underlying set [n]. Each block π is considered to be an input slot of arity n = ♯π , and into it one can substitute any partition Q i i i of [n ] by replacing the block with the partition Q (under the unique order-preserving bijection i i between [n ] and the underlying set of π ). The effect of the substitution is thus to refine the i i partition, while leaving fixed the total number of elements n. The identity operations are clearly the single-block partitions I , since substituting such a partition into a block of size n does not refine it further. 19 To actually implement this idea and make it fit the formal definition, it is necessary to number the blocks, so as to know in which order the input slots come, and where to substitute given inputs. For this reason, the operations will have to be set compositions rather than set partitions, and the actions of the symmetric groups required for symmetric operads will then simply be renumbering of the blocks. This is a standard procedure in the construction of symmetric operads. Definition 4.1.1. A set composition is a set partition equipped with a numbering of its blocks. Equivalently, it is given by a list of blocks P = (π , . . . π ) rather than a set of blocks. 1 k We denote by SC(k, n) the set of iso-classes of compositions of an n-element set into k blocks, that is, sequences C = (π , . . . , π ) such that P = {π , . . . , π } is a partition. This includes the 1 k 1 k case SC(0, 0) = {∅}, consisting only of the empty composition. We also put: G G SC = SC(k, n), SC(n) = SC(k, n), SC = SC(0, 0)⊔ SC. 1≤k≤n k≤n Similarly, a noncrossing composition is a noncrossing partition with a numbering of its blocks. We denote by NCC(k, n) the set of iso-classes of noncrossing compositions of an n-element set into k blocks, that is, sequences C = (π , . . . , π ) such that P = {π , . . . , π } is a noncrossing 1 k 1 k partition. We put: G G NCC = NCC(k, n), NCC(n) = NCC(k, n), NCC = NCC(0, 0)⊔ NCC. 1≤k≤n k≤n We can now specify the data of the operad SC of set partitions (which should more precisely be called of set compositions): • The set of colours is the set of positive integers N ; • For fixed n , . . . , n , n ∈ N , we denote by SC(n , . . . , n ; n) the set of set compositions of 1 k 1 k [n], say C = (π , . . . , π ), such that ♯π = n for each i ∈ [k]. (Note that if n 6= n +···+n , 1 k i i 1 k then SC(n , . . . , n ; n) = ∅.) A given composition P = (π , . . . , π ) of [n] is thus regarded as a k-ary operation of output colour n, and input colour-list (♯π , . . . , ♯π ). 1 k • The identity operations are by definition the coarsest compositions, i.e., single blocks of n elements, I ∈ SC(n; n), for each n ≥ 1. • The actions of the symmetric groups S are given by permutation of blocks: for P = (π , . . . , π ) ∈ SC(n , . . . , n ; n) and σ ∈ S : 1 k 1 k k P = (π , . . . , π ) ∈ SC(n , . . . , n ; n). σ(1) σ(k) σ(1) σ(k) (That is, σ acts by renumbering blocks.) • The composition law onSC is given as follows. For any P = (π , . . . , π ) ∈ SC(n , . . . , n ; n) 1 k 1 k and a list of compositions (Q , . . . , Q ) with Q = (τ , . . . , τ ) ∈ SC(m , . . . , m ; n ), 1 i i,1 i,1 i k i,l i,l i i we define: P ◦ (Q , . . . , Q ) := (τ , . . . , τ , . . . , τ , . . . , τ ). 1 k 1,1 1,l k,1 k,l This requires reindexing: implicitly we are transporting the set-composition structure of each Q on [n ] along the unique monotone bijection [n ] π ⊂ [n]. i i i i Checking that these data constitute indeed a coloured symmetric operad SC is a straightforward, but rather cumbersome, routine exercise. The only difficulty is index bookkeeping. 20 Proposition 4.1.2. The composition law preserves noncrossing compositions. In particu- lar, the same definitions as above, but using only noncrossing compositions, defines a (coloured symmetric) operad NCC of noncrossing compositions. Proof. For any application of the composition law, say P ◦ (Q , . . . , Q ), assume that all of P 1 k and Q are noncrossing. We assume the notation from above. Consider two blocks τ and τ of P ◦ (Q , . . . , Q ). These blocks τ and τ are essentially blocks of some of the Q , but shifted 1 k i around according to the identifications made. If τ and τ originate in the same Q , then they were noncrossing in Q , and since the shifting into block π is effectuated by a monotone bijection i i [n ] → π ⊂ [n], this clearly preserves the noncrossing condition. If the two blocks τ and τ i i originate in distinct compositions Q and Q , then they are mapped into distinct blocks π and i j i π of P , and since π and π do not cross in P , a block of a refinement of π cannot cross a block j i j i of a refinement of π . In either case we see that τ and τ do not cross in P ◦ (Q , . . . , Q ). j 1 k Example. {1, 5, 6};{2, 3, 4};{7, 8, 9, 10, 11} ◦ ({{1};{2, 3}), ({1, 3};{2}), ({1, 2, 5};{3, 4}) = ({1};{5, 6};{2, 4};{3};{7, 8, 11};{9, 10}). Graphically: 2 2 3 6 4 6 1 3 1 2 1 1 2 5 1 3 2 5 ◦ , , = = . Here the numbers indicate the block numbering that makes a partition into a composition. Remark 4.1.3. The axioms force us to exclude the colour 0 and the empty composition. The only composition of ∅ is of course the empty composition, and it has arity 0, not 1. Were we to insist on including the empty composition (as a nullary operation) we would have to give up the unit axiom. We shall return to this issue when we come to comodule bialgebras in Section 5. In particular, since every non-empty composition has at least one block, there are no nullary operations, which is to say that the operad is reduced. The following is a general construction of an ordinary operad from a coloured one, but it re- quires the setting of linear operads, i.e., operads in the symmetric monoidal category (Vect,⊗,K) instead of the category of sets. Proposition 4.1.4. Let C be a set and let P be a C-coloured linear operad. For any n ≥ 1, we put: P(n) = P(c , . . . , c ; c). 1 n c ,...,cn,c∈C Let us assume that for any (c , . . . , c ) ∈ C , the set ind(c , . . . , c ) = {c ∈ C | P(c , . . . , c ; c) 6= 1 n 1 n 1 n 0} is finite. We define a composition law on P in the following way: we consider elements b b p ∈ P(n), q ∈ P(k ) for any i ∈ [n] and put: i i Y Y p = p , q = q . c ,...,c ;c i c ,...,c ;c 1 n i,1 i,k i c ,...,c ,c∈C c ,...,c ,c ∈C 1 n i,1 i,k i Then: Y X p• (q , . . . , q ) = p ◦ (q , . . . , q ) . 1 n c ,...,c ;c c ,...,c ;c c ,...,c ;c 1 n 1,1 1,k 1 n,1 n,k n c ,...,c ,c∈C 1,1 c ∈ind(c ,...,c ), n,k 1 1,1 1,k c ∈ind(c ,...,c ) n n,1 n,k 21 b The unit of P is: Y Y I = I ∈ P(c; c) ⊆ P(1). c∈C c∈C Proof. By hypothesis on ind(c , . . . , c ), the sum defining p• (q , . . . , q ) is finite, so 1 n 1 n c ,...,c ;c 1,1 n,k the law • is well-defined. The associativity of ◦ and its compatibility with the action of the symmetric groups imply that • is associative and compatible with the action of the symmetric groups. For any p ∈ P(n): Y Y I • p = (I ◦ p + 0) = p = p, c c ,...,c ;c c ,...,c ;c 1 n 1 n c ,...,c ,c∈C c ,...,c ,c∈C 1 n 1 n Y Y p• (I, . . . , I) = p ◦ (I , . . . , I ) = p = p. c ,...,c ;c c c c ,...,c ;c n n n 1 1 1 c ,...,c ,c∈C c ,...,c ,c∈C 1 n 1 n So I is a unit of P. (Notice that in all the above constructions, products could be replaced by direct sums except for the fact that then the operad P would not have a unit since I ∈/ I .) c∈C Definition 4.1.5 (Operads of compositions). Let P be the linearization of SC or NCC, with set of colours C = N . Then, for any c , . . . , c ∈ C: 1 n ind(c , . . . , c ) = {c +··· + c }. 1 n 1 n The construction of the previous proposition can thus be applied to SC and NCC to obtain two c [ ordinary (linear) operads SC and NCC. 4.2 Induced bialgebras The general construction of a bialgebra from an operad (already invoked in Subsection 3.3) applies equally well to coloured symmetric operads P (subject to suitable finiteness conditions). As an algebra, the associated bialgebra is free on the set of all operations. The coproduct of an operation R is defined as Δ(R) = P ⊗ Q ··· Q . 1 k R=P◦(Q ,...,Q ) 1 k In plain words, the coproduct is given by summing over all the ways R could have arisen from the composition law, and then putting the receiving operation P on the left and the monomial of all the operations fed into P on the right. Like in the one-colour case, this bialgebra is graded (by arity-minus-one), but is never connected. In the present case, degree zero is spanned by the identity operations I , the single-block partitions, and for most purposes it is too drastic to divide out by those. We shall therefore mostly accept that the resulting bialgebras are not Hopf. Another “drawback” is that the general bialgebra construction yields a bialgebra spanned by compositions rather than partitions. This is an artifact of having introduced the numbering of blocks, and it is corrected easily by passing to coinvariants, meaning dividing out by the actions of the symmetric groups. Since these actions are free (because the numberings were introduced freely), this quotiening is well behaved. Although it is possible to describe these construction by hand, it is usually better to in- voke general theorems to the effect that the construction works. One general framework for the construction is described in [17], applied to single-coloured operads SC and NCC. (The construction is denoted D in that article.) With the previous notation for coloured linear operads, P(c , . . . , c ; c) is the linear dual of ⊕ P(c , . . . , c ; c) . These 1 n c ,...,c ,c∈C 1 n c ,...,c ,c∈C 1 n 22 comp comp constructions allow to define bialgebras C and B of set compositions and noncrossing compositions, and pass to coinvariants to get bialgebras C and B of set partitions and noncrossing partitions. (This composite construction is denoted D in [17].) Another general construction goes via the so-called two-sided bar construction, as exploited in [26]: to any (coloured) operad one can first assign its two-sided bar construction, which is a simplicial groupoid (see [26]). This simplicial groupoid is in fact a symmetric monoidal decomposition space in the sense of [20], and therefore admits an incidence bialgebra, which in comp comp the present two cases are C and B directly (C and B cannot be obtained in this way). (Incidence coalgebras of posets and categories are also special cases of this, and the setting allows for precise comparison results. We shall briefly touch upon this below when we compare the operad approach with the classical lattice approach (see Remark 4.3.12).) We summarize the outcome of these constructions in the following proposition, and proceed to give explicit descriptions of the structures. Proposition 4.2.1. The coloured symmetric operads SC and NCC induce four bialgebra structures and bialgebra homomorphisms: noncrossing general comp comp compositions B C partitions B C comp comp The bialgebra C is freely generated as an algebra by SC, and B is freely generated by NCC. It is the coproduct, denoted δ , which is the most interesting structure. We proceed to describe it in elementary terms. For any P , Q ∈ SC(n), recall that P ≤ Q if there exist R , . . . , R ∈ SC such that: 1 k P = Q◦ (R , . . . , R ). 1 k This is an adaptation to compositions of the usual ordering by coarsening of partitions (P ≤ Q when Q is coarser than P ). For fixed P and Q, such R , . . . , R are unique if they exist; in that 1 k comp comp comp case we put P/Q := R ··· R . We can now describe the coproduct δ : C → C ⊗C 1 k 0 explicitly. For P ∈ SC we have SC ∋ P 7→ δ (P ) = Q⊗ P/Q. P≤Q The space of invariants under the action of the symmetric groups of Vect(SC) is naturally identified with Vect(SP). Accordingly, C is the free commutative algebra generated by SP, and similarly B is the free commutative algebra generated by NCP. The coproduct δ on C is induced from δ . To describe it, further notation is required: For P , Q ∈ SP(n), we shall say that P ≤ Q if each block of Q is the union of the blocks of P it contains. This is the usual poset of partitions of degree n. Its minimal element is the finest partition J = {{1}, . . . ,{n}}, the unique element of SP(n, n), and its maximal element is the coarsest partition I = {[n]}, the unique element of SP(1, n). Denoting Q = {τ , . . . , τ }, we put 1 l P/Q = P ··· P ∈ C. |τ |τ Finally we can describe the coproduct explicitly. We have δ : C → C⊗ C, and: SP ∋ P 7→ δ(P ) = Q⊗ P/Q. (14) P≤Q The counit of C is denoted by ε ; for P ∈ SP(k, n), we have ε (P ) = δ . C C k,1 23 Remark 4.2.2. For the noncrossing case the description is exactly the same. The sum runs over noncrossing partitions Q coarser than P . This is meaningful because if P is noncrossing then for any coarser noncrossing partition Q, the restrictions P forming the monomial are |τ noncrossing as well. Example 4.2.3. We give some example computation in the case of noncrossing partitions. Since the sum defining δ is over all coarser noncrossing partitions, the coarsest partitions I are all group-like: δ( ) = ⊗ δ( ) = ⊗ δ( ) = ⊗ and the finest partitions J have the longest formulas for coproduct: δ( ) = ⊗ + ⊗ · δ( ) = ⊗ + + + ⊗ · + ⊗ · · δ( ) = ⊗ + ⊗ · + ⊗ · + ⊗ · · + ⊗ · · + ⊗ · · + ⊗ · · + ⊗ · · + ⊗ · · + ⊗ · + ⊗ · + ⊗ · + ⊗ · + ⊗ · · · . Here are a few other examples, which will be referenced later: δ( ) = ⊗ · + ⊗ δ( ) = ⊗ · + ⊗ δ( ) = ⊗ · + ⊗ δ( ) = ⊗ · · + ⊗ · + + ⊗ · + ⊗ δ( ) = ⊗ · · + ⊗ · + ⊗ · + ⊗ . 4.3 Comparison with the lattice approach and Möbius inversion The monomial P/Q appearing on the right-hand side in the coproduct formula (14) plays an important role in relating the bialgebras C and B with the incidence coalgebras of the lattices of partitions and noncrossing partitions. In this subsection, for simplicity we treat only the case of noncrossing partitions, but the whole discussion (though not the example computations) carries over to the case of general set partitions. We shall see, for example, that Speicher’s basic moment-cumulant formula given in terms of Möbius inversion in the incidence algebra of the lattice of noncrossing partitions can be rendered elegantly in the bialgebra B. Definition 4.3.1 (Fibre). Given two (noncrossing) partitions, P, Q ∈ NCP, one finer than the other, P ≤ Q, the fibre map is defined by: Φ(P, Q) := P/Q. Example: Φ , = · · . The linear dual B is an algebra under the corresponding convolution product: for two linear maps φ, ψ : B → K, the convolution product is given by (φ∗ ψ)(P ) = φ(Q)ψ(P/Q). P≤Q The neutral element for the convolution product is the bialgebra counit ε , which takes value 1 on all I (as well as on monomials in the I ) and value 0 on all other noncrossing (multi)partitions. n n 24 Recall that for any bialgebra T , the characters (algebra homomorphisms T → K) form a monoid for the convolution product: the product of two characters φ, ψ is given by φ ∗ ψ := m ◦ (φ⊗ ψ)◦ Δ . For the case of B, a character ψ is thus multiplicative, in the sense that if P K T is a commutative monomial of partitions, P = P ··· P , then ψ(P ) = ψ(P )··· ψ(P ) (and we 1 r 1 r also have ψ(1) = 1, where the argument 1 denotes the empty product, the unit element in the algebra). A basic character on B is the zeta function B −→ K ζ : P 7−→ 1. It is a general fact that the zeta function is convolution invertible; its inverse is by definition the Möbius function µ , which is again a character, determined by the following recursive formula: µ (I ) = 1 for all n > 0, µ (P ) = − µ (Q) for P 6= I . P<Q The sum is over all strictly coarser partitions or noncrossing partitions. Lemma 4.3.2. In the dual B , given a character κ, define φ := ζ ∗ κ. Then: φ(J ) = κ(J )··· κ(J ). (15) n ♯π ♯π P ={π ,...,π }∈NCP(n) Corollary 4.3.3. With k := κ(J ) = κ( ··· ) and m := φ(J ) = φ( ··· ), n n n n Equation (15) recovers the familiar free moment-cumulant relation m = k from (9). n Q Q∈NCP(n) Remark 4.3.4. Note that the moments and cumulants here are defined using the finest partitions, not the coarsest, which may surprise readers familiar with the work of Speicher [40, 34]. The contrast will be fully resolved below. Example 4.3.5. Using the above coproduct formulae and the monomial multiplicativity, we calculate for instance the second, third and fourth moments in the noncrossing case: m = φ( ) = (ζ ∗ κ)( ) = κ( · ) + κ( ) = k k + k , 1 1 2 m = φ( ) = (ζ ∗ κ)( ) = κ( · · ) + 3κ( · ) + κ( ) = k k k + 3k k + k , 1 1 1 1 2 3 m = κ( · · · ) + 6κ( · · ) + 4κ( · ) + 2κ( · ) + κ( ) = k k k k + 6k k k + 4k k + 2k k + k . 1 1 1 1 1 1 2 1 3 2 2 4 (Note that the coefficient 2 in front of k k is the first that distinguishes the case of noncrossing 2 2 partitions from the case of general set partitions, where this coefficient would be 3.) Conversely, using the recursive formula for µ , one finds quickly that µ ( ) = µ ( ) = µ ( ) = µ ( ) = 1 µ ( ) = µ ( ) = µ ( ) = µ ( ) = µ ( ) = µ ( ) = µ ( ) = µ ( ) = −1, 25 µ ( ) = µ ( ) = µ ( ) = µ ( ) = 2, but µ ( ) = µ ( ) = 1, µ ( ) = −5. Combining with the basic comultiplication table (see computations in Example 4.2.3), we get for the second, third and fourth cumulants k = κ( ) = (µ ∗ φ)( ) = µ ( )φ( · ) + µ ( )φ( ) = −m m + m , 1 1 2 k = κ( ) = (µ ∗ φ)( ) = µ ( )φ( ) + 3µ ( )φ( · ) + µ ( )φ( · · ) = m − 3m m + 2m , 3 1 2 2 2 4 k = m − 2m + 10m m − 4m m + m . 4 4 2 1 3 2 1 1 These computations are completely analogous to the calculations usually done to relate mo- ments and free cumulants in the lattice of noncrossing partitions (see for instance [34]), but they are simpler in the present framework since one can work with noncrossing partitions directly instead of working with intervals of noncrossing partitions. As observed above, it may seem disturbing that we put k := κ( ), whereas Speicher [40] puts k := κ( ), which is really n n shorthand for κ(JJ , I K) in that context (the one of the incidence algebra of the lattice). The n n reason for this is that the relationship between the noncrossing partition lattice and the bialgebra B is actually given by the assignment Φ introduced in Definition 4.3.1, which to any interval associates its fibre. Recall, e.g., from [34] that the incidence coalgebra of a lattice is the free vector space spanned by the intervals JP, QK in the lattice, and that the coproduct is given by δ (JP, QK) = JP, M K⊗ JM, QK. lat M∈JP,QK We shall actually use the opposite coalgebra, meaning that the order of the tensor factors is reversed. This opposite coalgebra we call B . For contrast, the operad bialgebra will be lat denoted B in the following discussion. opd Remark 4.3.6. We emphasize that the “opposite” occurring here is unrelated to the question we are addressing, i.e., “finer vs. coarser”. Indeed, working with the opposite coalgebra is purely a matter of convention of order of the tensor factors in the coproducts. The following result resolves the relation between the two coalgebras B and B . lat opd Proposition 4.3.7. The assignment Φ constitutes a coalgebra homomorphism B → B . lat opd Proof. This follows from the next two lemmas. The first is a standard property of noncrossing partitions, the second follows from the definition of Φ. Lemma 4.3.8. Every interval JP, QK is isomorphic as a poset to a product of intervals ending in a coarsest partition I . Precisely, JP, QK ≃ JP , I K×···× JP , I K, 1 n k n 1 k where k is the number of blocks in Q, the ith block of Q is of size n , and P is the corresponding i i partition of [n ]. Lemma 4.3.9. For any interval JP, QK, we have Φ(JP, QK) = Φ(JP , I K)··· Φ(JP , I K), 1 n k n 1 k where again k is the number of blocks in Q, and the ith block of Q is of size n , and P is the i i corresponding finer partition. 26 ∗ ∗ Corollary 4.3.10. The dual map B → B is a homomorphism of convolution algebras. opd lat Remark 4.3.11. Characters on B , say κ : B → K, induce linear forms on B , say opd opd opd lat κ : B → K such that lat lat κ (JP, QK) = κ (Φ(JP, QK)) = κ (P/Q). lat opd opd These linear forms have the special property (actually desired) that their value on an interval only depends on its canonical product splitting (i.e. its type, in the sense of Speicher). This correspondence explains the apparent discrepancy we noticed: when in the lattice setting one writes κ(I ) it is really shorthand for κ(JJ , I K), and the fibre of the interval JJ , I K is n n n n n clearly the partition J , so that κ (I ) = κ (J ), and both can be called k without conflict. n lat n opd n n Remark 4.3.12. The coalgebra homomorphism Φ should not be considered as something strange or ad hoc. In fact, it is an instance of a general phenomenon, visible in the simplicial viewpoints hinted at in the preliminary discussion in Subsection 4.2. There it was mentioned that B is the incidence bialgebra of a certain simplicial groupoid X (more precisely a monoidal opd decomposition space), obtained as the two-sided bar construction of the operad NCP. In this simplicial viewpoint, one can take upper decalage of X to find essentially the nerve of the noncrossing partitions lattice, and then the dec map Dec X → X induces precisely Φ. It is a coalgebra homomorphism for general reasons. Many examples of coalgebra homomorphisms from incidence coalgebras of posets to incidence bialgebras of operads which fit this pattern are given in [21]. Remark 4.3.13. We stress again that all the discussion in this subsection applies equally to the case of general set partitions, and in particular: the assignment Φ constitutes a coalgebra homomorphism C → C , lat opd from the –opposite– incidence coalgebra of the lattice of partitions to the incidence bialgebra of the (block substitution) operad of set partitions. 5 Comodule bialgebra, half-shuffle exponentials and Möbius in- version In the previous sections we have shown how the gap-insertion operad encodes the shuffle Hopf algebra approach to moment-cumulants relations, and that the block-substitution operad encodes the lattice viewpoint, reproducing the Möbius inversion. In this section we address the relationship between the two operads, at the level of their bialgebras. We show that these constitute a pair of interacting bialgebras in the sense of [6], and more precisely a comodule bialgebra (see [30] for a review). In fact we show that N is a comodule shuffle Hopf algebra over B. We shall then explore this relationship to establish formulae for the half-shuffle exponentials in terms of universal characters, which are analogues of zeta functions in the three cases of free, monotone, and boolean moment-cumulant relations. The comodule-bialgebra viewpoint also allows to understand the inverses of these universal characters, and relate them to Möbius inversion. 5.1 Comodule bialgebra Briefly, the notion of comodule bialgebra is the following: for any coalgebra B one has the notion of right-B-comodule. If B is furthermore a bialgebra, the category CoMod(B) of right-B- comodules is naturally monoidal, and if B is a commutative bialgebra, this monoidal structure acquires a braiding. It hence makes sense to talk about bialgebras in CoMod(B). These are the 27 comodule bialgebras. In a nutshell a comodule bialgebra is a bialgebra with a coaction by B, compatible with the bialgebra structure. In the case at hand, the promised right coaction ρ : N → N ⊗B is essentially the coproduct 0 0 δ of the commutative bialgebra B, but extended to include the empty partition, which is an element in N . N −→ N ⊗ B 0 0 ρ : P 7−→ Q⊗ P/Q. P≤Q Note in particular that ρ(∅) = ∅⊗ 1 (because there are no other coarser partitions of ∅ than ∅ itself, and this has no blocks, so the fibre monomial is just the algebra unit). Coassociativity of this coaction ρ is clear from the fact that it is essentially the coproduct δ. Theorem 5.1.1. The coaction ρ : N → N ⊗ B makes N into a comodule bialgebra over 0 0 0 B. That is, the following relations hold for all P, Q ∈ N : ρ(1 ) = 1 ⊗ 1 , N N B 0 0 ρ(P · Q) = ρ(P )ρ(Q), (ε ⊗ Id)◦ ρ(P ) = ε (P )1, N N 0 0 (Δ ⊗ Id)◦ ρ(P ) = (Id⊗ Id⊗m )◦ (Id⊗τ ⊗ Id)◦ (ρ⊗ ρ)◦ Δ (P ), (16) 0 B 0 where τ : B⊗ N −→ N ⊗ B is the swap map Q⊗ P 7→ P ⊗ Q. 0 0 This theorem can be proved using the general machinery of operads and brace algebras from [17]. Here we wish to present an elementary argument, exhibiting the main ingredients that make it work. Proof. The most interesting part is the fourth statement, which states that Δ is a B-comodule homomorphism. Diagrammatically, this looks as follows N N ⊗ N 0 0 0 ρ⊗ρ N ⊗ B⊗ N ⊗ B 0 0 Id ⊗τ⊗Id N ⊗ N ⊗ B⊗ B 0 0 Id ⊗ Id ⊗m N ⊗ B N ⊗ N ⊗ B 0 0 0 Δ ⊗Id The two sides of the equation (16) are both elements in the tensor product N ⊗ N ⊗ B, that 0 0 is, sums of tensors. To establish the equation (for each fixed partition P ), we first establish a bijection between the indexing sets for the two sums, and then show that under this bijection, the three corresponding tensor terms agree. Step 1: the left-hand side of (16) (corresponding to the down-right path in the diagram) sends P to a sum over the set of ways of first coarsening P and then cutting the coarsened partition. The right-hand side of the equation (given by the right-down path in the diagram) sends a partition P to a sum indexed by the set of all ways to cut P into upper- and lowersets and then coarsen each layer. The natural bijection between these to sets is most easily given by establishing for each set a natural bijection with the set of possible compatible cuts and coarsenings, or coarse-cuts, as we shall say for short. A coarse-cut on a partition P consists of both a cut and a coarsening, required to be compatible in the sense that the cut is not allowed to separate two blocks that are joined in the coarsening. Here is a picture to illustrate this: 28 1 2 3 4 5 6 7 8 9 The blue dotted lines indicate which blocks are joined in the coarsening. Graphically, the com- patibility condition says simply that the red line expressing the cut is not allowed to cross the blue lines expressing the coarsening. The required bijections are clear. Step 2: for each fixed partition P , and each fixed coarse-cut, we must identify the corre- sponding two terms in the triple tensor product N ⊗ N ⊗ B. For the example given above, 0 0 these three tensor factors are O O ∅ · · ∅ · ∅ · · ∅ · · · 1 5 6 7 9 2 3 4 8 1 6 7 9 2 3 4 5 8 as we shall now see. The first tensor factor (in N ) is simply the coarsening of the lower layer. Indeed, this is obtained via the left-hand side by first coarsening, and then cutting the coarse partition. It is obtained via the right-hand side by first cutting, and then coarsening the lower layer. So the first tensor factor matches up as required. The second tensor factor (also in N ) is described as the upperset monomial of the coarse version of the cut. This immediately matches the description obtained from the left-hand side. Via the composite map of the right-hand side, the second tensor factor arises from looking first in the upper layer (that’s a monomial, not a single partition), and then coarsening each of the factors in the monomial. Since the lowerset partition and its coarsening have precisely the same elements in [n], the factors in the uppersets also have the same elements. On the left-hand side the coarsening of them takes place before cutting, and in the right-hand side the coarsening takes place after cutting, and clearly the order of these two steps does not affect the result, so also the second tensor factor matches up as required. Finally the third factor (which belongs to B) has nothing to do with the cut: it is simply the fibre of the total coarsening (as in Subsection 4.3, i.e. for each block in the coarse partition, list the corresponding finer partition). What the equation says for this tensor factor (and which is clearly true) is that to compute the fibre of the whole coarsening (without even taking the cut into account) can be done in two steps: first compute fibres of the blocks in the bottom layer, then compute fibres of the blocks in the upper layer, and then join the result (concatenation, multiplication of monomials). (A subtlety to note here is that the monomial in the right-hand tensor factor of N ⊗ N may contain empty partitions. But we have ρ(∅) = ∅⊗ 1 (where 1 is 0 0 the algebra unit). This is just to say that the fibre of the trivial coarsening of ∅ is the trivial monomial. Put in another way, since the empty partition has no blocks, there are no fibres. The ∅-factors therefore disappear (what the third tensor factor B is concerned).) Theorem 5.1.2. The right coaction ρ : N → N ⊗ B makes N an unshuffle (also called codendriform) Hopf algebra in the category of right comodules over B. That is, the comodule Hopf algebra structure and the unshuffle Hopf algebra structure are compatible, meaning that for all P ∈ N we have (Δ ⊗ Id)◦ ρ(P ) = (Id⊗ Id⊗m )◦ (Id⊗τ ⊗ Id)◦ (ρ⊗ ρ)◦ Δ (P ), ≺ B ≺ (Δ ⊗ Id)◦ ρ(P ) = (Id⊗ Id⊗m )◦ (Id⊗τ ⊗ Id)◦ (ρ⊗ ρ)◦ Δ (P ), ≻ B ≻ where τ : B⊗ N −→ N⊗ B is the swap map Q⊗ P 7→ P ⊗ Q. Proof. It is clear that the coaction ρ : N → N ⊗ B restricts to a coaction ρ : N → N ⊗ B, 0 0 and that this makes N a comodule Hopf algebra. To check the compatibility with the splitting of the unshuffle coproduct into half-unshuffles, it remains to notice that the coaction works by refinement of blocks, and that this does not interfere with whether or not the block containing the element 1 belongs to the lowerset of a cut. 29 5.2 Four bijections from infinitesimal characters to characters We focus in this subsection on the structure of noncrossing partitions and relations between moments and free cumulants, having in mind applications of the previous results to free, boolean and monotone probabilities (on the latter two in the context of the present article, see [13]). We show indeed that the comodule bialgebra structure of N over B leads to a new approach to these phenomena. Recall first from [14] that groups of characters on unshuffle (also called codendriform) Hopf algebras H have a rather rich structure with, in particular, three exponentials and logarithms putting in bijection the Lie algebra of infinitesimal characters of H and the group of characters. When applied in the context of free probability, these maps together with associated properties of the group and Lie algebras lead to a new understanding of the three natural families of cumulants in this context (free, monotone and boolean), of their relationships, and of related notions such as additive convolution of free distributions (see also [13]). In the present section we explore these bijections using the action of the monoid M of characters of B, and relate the resulting formulae with the Möbius function of the lattice of noncrossing partitions. The product in M , induced by the coproduct δ, is denoted by ∗. We denote by G the B B group of invertible elements of M . Lemma 5.2.1. Let φ ∈ M . Then φ ∈ G if and only if φ(I ) 6= 0 for all n ≥ 1. B B n Proof. Let φ ∈ G and ψ be the inverse of φ for the convolution ∗. For any n ≥ 1, since I is a B n group-like element, we have 1 = φ∗ ψ(I ) = φ(I )ψ(I ), and hence φ(I ) 6= 0. n n n n Conversely, the bialgebra B is graded by the number of blocks (minus one), and its com- ponent of degree zero has a basis of group-like elements, namely the products of I ’s. Hence, ′ −1 −1 ′ B = B[I , . . . , I , . . . ] is a Hopf algebra, with the extension δ of the coproduct δ defined 1 n ′ −1 −1 −1 by δ (I ) = I ⊗ I . If φ ∈ M satisfies φ(I ) 6= 0 for all n ≥ 1, it can be extended as a B n n n n ′ ′ ′ ′ ′ character φ to B . Denote by ψ the inverse of φ in the group of characters of B and by ψ its restriction to B. For any P ∈ B: ′ ′ ′ (φ∗ ψ)(P ) = (φ⊗ ψ)◦ δ(P ) = (φ ⊗ ψ )◦ δ (P ) = ε ′(P ) = ε (P ). B B Similarly, (ψ ∗ φ)(P ) = ε (P ), so φ ∈ G . B B We also write g for the Lie algebra of infinitesimal characters of N (linear forms that vanish on (N ) ; the Lie bracket is induced by the associative convolution product of linear forms). We furthermore write G for the group of characters of N. Its product, induced by Δ, is denoted by ⋆. As already observed, the coproducts Δ and Δ induce a shuffle (also called dendriform) ≺ ≻ ∗ ∗ algebra structure on the dual N . It is extended to products of elements of N with the unit ε of the convolution product as follows: for any f ∈ N , f ≺ ε = f, f ≻ ε = 0, N N ε ≺ f = 0, ε ≻ f = f. N N The coaction ρ induces a right action of M on linear forms on N, denoted by x: for α an arbitrary linear form on N and φ ∈ M , it is given by α x φ := (α⊗ φ)◦ ρ. It restricts to an action by group endomorphisms on G and by Lie algebra endomorphisms on g . Note that as an algebra B is the abelianization of N, so, as sets, M and G can be iden- B N tified. Through this identification, we see that the action x coincides with the product ∗. In the following, to avoid ambiguities, when φ ∈ G , we write φ for the corresponding element of 30 b M . Conversely, when ψ ∈ M , we write ψ for the corresponding element of G (so that in B B N particular for φ ∈ G and γ ∈ M , we have φ x γ = φ∗ γ). N B First, since N is freely generated by NCP as an algebra, characters and infinitesimal char- acters on N are entirely determined by their restriction to NCP, and the following maps are bijections: ∗ ∗ g −→ Vect(NCP) G −→ Vect(NCP) N N θ : θ : g G κ 7−→ κ , φ 7−→ φ . |Vect(NCP) |Vect(NCP) −1 The composite bijection Θ = θ ◦ θ : g −→ G sends any κ ∈ g to the unique character g N N N Θ(κ) : N → K such that it agrees with κ on degree-1 monomials. That is, κ(P ) = Θ(κ)(P ) (for any P ∈ NCP). What cumulants are concerned we shall be especially interested in those elements in g that −1 vanish on NCP(k, n) for k ≥ 2. In particular, we shall consider e = Θ (εb ). In other words, e is the unique infinitesimal character of N such that for any P ∈ NCP(k, n), we have e(P ) = δ . k,1 As a consequence, for all P ∈ NMP(k, n): e(P ) = δ . k,1 The first natural bijection Θ : g → G rewrites as follows, in terms of the coaction of B on N N N: Proposition 5.2.2. For any κ ∈ g , put K := Θ(κ) ∈ M . Then we have N B κ = e x K. Proof. For any P ∈ NCP we have e x K(P ) = e(Q)K(P/Q) = K(P ) = κ(P ). P≤Q Since κ and e x K therefore agree on all noncrossing partitions, and are both infinitesimal characters over N, they must be equal. Proposition 5.2.3 (Left half-shuffle exponential isomorphism). Let κ ∈ g . There exists a unique φ ∈ N , such that φ = ε + κ ≺ φ; moreover, φ ∈ G . Conversely, let φ ∈ G . There N N N exists a unique κ ∈ N , such that φ = ε +κ ≺ φ; moreover, κ ∈ g . In particular, the following N N map is a bijection: g −→ G N N E : κ 7−→ φ such that φ = ε + κ ≺ φ. Proof. Let us define φ(P ) for any P ∈ NMP(k, n) by induction on n. If n = 0, then P = 1 and ′ ′′ φ(1) = 1. If n ≥ 1, we put φ(P ) = κ(P ) +κ(P )φ(P ) (with Sweedler-like notation for Δ as in ≺ ≺ (7)). We obtain in this way a map φ ∈ N , such that φ = ε + κ ≺ φ. Let x ∈ NMP(k, m) and y ∈ NMP(l, n); let us prove that φ(xy) = φ(x)φ(y) by induction on m + n. If m = 0 or n = 0, then x = 1 or y = 1 and the result is immediate. We now assume that m, n ≥ 1. Then, as κ is an infinitesimal character, and by the induction hypothesis: ′ ′′ ′ ′′ φ(PQ) = κ(PQ)φ(1) + κ(P )φ(Q) + κ(PQ )φ(Q ) + κ(P Q)φ(P ) ≺ ≺ ′ ′′ ′ ′ ′′ ′′ + κ(P )φ(P Q) + κ(P Q )φ(P Q ) ≺ ≺ ≺ ≺ ′ ′′ = κ(P )φ(Q) + κ(P )φ(P )φ(Q) ≺ ≺ = φ(P )φ(Q). So φ ∈ G . The proof of the second statement is similar and the last is an easy consequence of the first two points. 31 The following character on N plays a special role: ψ := E (e). We shall see in Theorem 5.3.2 ≺ ≺ that it corresponds to the zeta function, ψ = ζ: we have ψ (P ) = 1 for every noncrossing ≺ ≺ partition P . The left half-shuffle exponential isomorphism rewrites as follows. Theorem 5.2.4. For any κ ∈ g , put K := Θ(κ) ∈ M as usual. For φ ∈ G we have N B N φ = ε + κ ≺ φ ⇐⇒ φ = ψ x K. N ≺ In other words, we have E (κ) = ψ x K. ≺ ≺ Proof. By definition, ψ = ε + e ≺ ψ . Since N is an unshuffle bialgebra in the category of ≺ N ≺ right B-comodules, we have: ψ x K = (ε + e ≺ ψ ) x K ≺ N ≺ = ε x K + (e x K) ≺ (ψ x K) N ≺ = ε + (e x K) ≺ (ψ x K) N ≺ = ε + κ ≺ (ψ x K) (by 5.2.2). N ≺ This shows that ψ x K satisfies the equation characterizing φ, and hence establishes the bi- implication. To establish the last equation, note that the character E (κ) is by definition the unique solution φ to the equation φ = ε + κ ≺ φ. But we have just seen that ψ x K satisfies N ≺ this equation. Proposition 5.2.5. Let us consider a family of scalars (k ) . We define the infinitesimal n n≥1 character κ on N by: k if P = I , n ≥ 1, n n κ(P ) = 0 otherwise. Then Theorem 5.2.4 gives, for any P ∈ NCP, that E (κ)(P ) = k and the moments ≺ ♯π π∈P X Y (E (κ) x ζ)(J ) = k . ≺ n ♯π π∈Q Q∈NCP(n) Proof. For any κ ∈ g , put K := Θ(κ) ∈ M . For P ∈ NCP we compute, by Theorem 5.2.4: N B X Y E (κ)(P ) = (ψ x Θ(κ))(P ) = Θ(κ)(P/Q) = Θ(κ)(P ) + 0 = k . ≺ ≺ ♯π P≤Q π∈P From this it follows that E (κ) x ζ = (ψ x Θ(κ)) x ζ = ψ x (Θ(κ)∗ ζ) ≺ ≺ ≺ (by associativity of the action), and therefore (E (κ) x ζ)(J ) = ψ (Q)(Θ(κ)∗ ζ)(J /Q) ≺ n ≺ n Q∈NCP(n) = (Θ(κ)∗ ζ)(J ··· J ) ♯π ♯π 1 k P ={π ,...,π }∈NCP(n) 1 k = (Θ(κ)∗ ζ)(J )··· (Θ(κ)∗ ζ)(J ) ♯π ♯π P ={π ,...,π }∈NCP(n) X Y = k . ♯π π∈P P∈NCP(n) 32 Proposition 5.2.6. Let us consider a family of scalars (k ) . We define the infinitesimal n n≥1 character κ on N by: k if P = J = {{1}, . . . ,{n}}, n ≥ 1, n n κ(P ) = 0 otherwise. Then for any P ∈ NCP(k, n): 0 if k < n, X Y E (κ)(P ) = (ψ x Θ(κ))(P ) = Θ(κ)(P/Q) = ≺ ≺ k if k = n. ♯π P≤Q Q∈NCP(n) π∈Q Proof. For any P ∈ NCP(k, n), k < n, it is clear that P/Q contains blocks of size bigger than one, i.e., P/Q is not a monomial of forests of sticks. This implies that Θ(κ)(P/Q) = 0. For P = J ∈ NCP(n, n) E (κ)(J ) = ψ (Q)Θ(κ)(J /Q) ≺ n ≺ n Q∈NCP(n) = Θ(κ)(J ··· J ) ♯π ♯π 1 k P ={π ,...,π }∈NCP(n) 1 k = Θ(κ)(J )··· Θ(κ)(J ) ♯π ♯π P ={π ,...,π }∈NCP(n) X Y = k . ♯π π∈P P∈NCP(n) Remark 5.2.7. Proposition 5.2.6 reveals a nice connection to the approach to free moment- cumulant relations presented in [11]. Indeed, let (A, ϕ) be a noncommutative probability space |A and consider the sub Hopf algebra N of forests of sticks, as in Corollary 3.3.12 but decorated by elements from A. Since a monomial of A-decorated forests of sticks is the same thing as a |A list of A-words, it is easy to see that the Hopf algebra N is isomorphic to the double tensor algebra over A (with the coproduct defined in [11]). Proposition 5.2.6 gives another proof of the free moment-cumulant relations deduced from a shuffle fixpoint equation. We now consider instead the right half shuffle: Proposition 5.2.8 (Right half-shuffle exponential isomorphism). Let κ ∈ g . There exists a unique φ ∈ N , such that φ = ε + φ ≻ κ; moreover, φ ∈ G . Conversely, let φ ∈ G . There N N N exists a unique κ ∈ N , such that φ = ε + φ ≻ κ; moreover, κ ∈ g . The following map is N N therefore a bijection: g −→ G N N E : κ −→ φ such that φ = ε + φ ≻ κ. The right half-shuffle exponential isomorphism rewrites as follows. Let us put ψ := E (e). ≻ ≻ Theorem 5.2.9. For any κ ∈ g , put K := Θ(κ) ∈ M as usual. Then for φ ∈ G we N B N have: φ = ε + φ ≻ κ ⇐⇒ φ = ψ x K. N ≻ 33 Let us finally consider the classical exponential bijection from the Lie algebra g to the group G : g −→ G N N ⋆n exp : κ 7−→ exp (κ) = . n! k=0 Put ψ := exp (e). Proposition 5.2.10 (Exponential isomorphism). For any κ ∈ g , put K := Θ(κ) ∈ M as N B usual. Then for φ ∈ G we have: φ = exp (κ) ⇐⇒ φ = ψ x K. Proof. Indeed: ψ x K = exp (e) x K = exp (e x K) = exp (κ) = ψ (κ), ∗ ⋆ ⋆ ⋆ ⋆ the third equality by Proposition 5.2.2. 5.3 Description of the universal maps ψ , ψ and ψ ≺ ≻ ⋆ In the previous subsection, we have seen that the maps ψ = E (e), ψ = E (e) and ψ = ≺ ≺ ≻ ≻ ⋆ exp (e) encode the three shuffle exponentials from g to G . In this subsection, we compute N N them explicitly. The set of partitions (or noncrossing partitions) forms a monoid under ordinal sum, denoted ⊎, with neutral element the empty partition. On the underlying linear orders it is just ordinal sum, [n]⊎ [m] = [n+m], and the partition structure on [n+m] is induced via the sum injections [n] → [n+m] ← [m] in the canonical way. A partition is called irreducible if it cannot be written as the ordinal sum of two non-empty partitions. A noncrossing partition P ∈ NCP(n) is irreducible if and only if 1 and n belong to the same block. In general, the block containing the element 1 we call the base block and denote it π . Let k denote the biggest element belonging to π , then J1, kK = Conv(π ) is a union of 1 1 1 blocks of P , and P is an irreducible partition, which we call E . Now we have |J1,kK 1 P = E ⊎ P, ˜ ˜ where P = E . Proceeding now the same way with P and iterating, it is clear that every noncrossing partition P splits uniquely into an (iterated) ordinal sum of irreducible noncrossing partitions, called irreducible components P = E ⊎···⊎ E . 1 r (For general partitions, the notion of irreducible is slightly more complicated, as, for example, also the partition with crossing is clearly irreducible. In general a partition is irreducible precisely when its noncrossing closure is irreducible. The unique splitting of an arbitrary partition into irreducible components is similar, but will not be needed here.) We shall say that a noncrossing partition is boolean if its irreducible components are precisely its blocks. In other words, it is an (iterated) ordinal sum of single-block partitions. In particular, in a boolean partition there is no nesting of blocks. 34 Definition 5.3.1 (Monotone compositions). Recall that a noncrossing composition is a non- crossing partition P equipped with a numbering of its blocks. Such a numbering is called a heap ordering if it preserves the order → (that is, the numbering map (P, → ) −→ [k] is monotone P P (k is the number of blocks)), meaning that if one block is nested inside another then it has a higher number. We denote by ho(P ) the cardinality of the set of heap orderings of a noncrossing partition P . A monotone composition is by definition a noncrossing partition with a chosen heap ordering. Theorem 5.3.2. 1. For any P ∈ NCP, we have ψ (P ) = 1. That is, ψ corresponds to ≺ ≺ the zeta function ζ ∈ B. 1 if P is boolean, 2. For any P ∈ NCP, we have ψ (P ) = 0 otherwise. ho(P ) 3. Let P ∈ NCP(k, n). Then ψ (P ) = . k! ... Recall from Definition 3.3.10 that if (L, U) is a cut of P , then U denotes the reduced gap monomial of the cut, the monomial obtained as the partitions belonging to U that appear in the gaps of L. Proof. Let P ∈ NCP(k, n). If π is base block of P , write P := P c as in the preliminary | Conv(π ) ˜ ˜ discussion above. In particular, if k = 1, then P = ∅, and ψ (P ) = ψ (P ) = ψ(P ) = 1. ≺ ≻ 1. If (L, U) is a cut of P such that e L 6= 0, then U contains all the blocks of P but one. By definition of ψ : ... ψ (P ) = e L ψ U = ψ (P ). ≺ ≺ ≺ (L,U)∈cut(P ), 1∈L The result follows by an easy induction on k. ... 2. If U is an upperset of P such that e U 6= 0, then, by definition of e, U contains only one block of P . The block π of P containing 1 is an upperset of P if and only if it is a irreducible component of P . Hence: X ˜ ... ψ (P ) if π is irreducible, ≻ 1 ψ (P ) = ψ (L)e(U) = ≻ ≻ 0 otherwise. (L,U)∈cut(P ), 1∈L The result follows by an easy induction on k. 3. An upper-block is a block which is also an upperset; in other words, it is a maximal element in the poset (P, → ) (that is, a block that has no nested blocks inside it). We write (L, U) ∈ cut (P ) for the situation where the upperset U consists of a single block (which is −1 hence an upper-block). If σ : (P, → ) −→ [k] is a heap ordering of P , then the block σ (k) is necessarily an upper-block. This yields a recursive calculation of the heap-order numbers: ho(P ) = ho(L), (17) (L,π)∈cut (P ) which is used in the following proof of Item 3 by induction on k. If k = 1, then ψ (P ) = e(P ) + 0 = 1 and we are done. Assume the result at rank k− 1, and consider a partition P with (1) (l) k blocks. With Sweedler notation for the iterated coproducts (P 7−→ P ⊗···⊗ P ): (1) (l) ψ (P ) = e(P )··· e(P ) l! l=1 35 1 (1) (k) = e(P )··· e(P ) + 0 k! (1) (k−1) = e(L )··· e(L )e(U) k! (L,U)∈cut (P ) (1) (k−1) = e(L )··· e((L) ) k! (L,U)∈cut (P ) = ψ (L) (L,U)∈cut (P ) 1 ho(L) = (by induction hyp.) k (k − 1)! (L,U)∈cut (P ) ho(P ) = (by (17)) k! as required. 5.4 On the inverses of the universal maps By Lemma 5.2.1, ψ , ψ and ψ are invertible elements of the monoid (M ,∗). In this subsection, ≺ ≻ ⋆ B we investigate the behaviour of these inverses. The following proposition emphasizes once again the boolean character of ψ (recall indeed from [13] that the right half-shuffle exponential is associated to boolean cumulants in free probability). Proposition 5.4.1. For any P ∈ NCP(k, n): k+1 (−1) if P is boolean, ∗−1 ψ (P ) = 0 otherwise; 1 if P is irreducible, ∗−1 ψ ∗ ψ (P ) = 0 otherwise, k+1 (−1) if P is irreducible, ∗−1 ψ ∗ ψ (P ) = 0 otherwise. ∗−1 Proof. Let us assume that P is not boolean and let us prove that ψ (P ) = 0 by induction on k. If k = 1, there is nothing to prove. If k ≥ 2, then for any Q > P , either Q is not boolean with ∗−1 l < k blocks, and hence vanishes under ψ , or one of the components of P/Q is not boolean, and hence vanishes under ψ . This shows that ∗−1 ∗−1 ∗−1 ψ ∗ ψ (P ) = ψ (P )ψ (P/P ) + 0 = ψ (P ) = ε (P ) = 0. ≻ ≻ B ≻ ≻ ≻ ∗−1 k+1 Let us assume that P is boolean and let us show that ψ (P ) = (−1) by induction on ∗−1 −1 k. If k = 1, then ψ (P ) = ψ (P ) = 1. If k ≥ 2: ∗−1 ∗−1 ψ ∗ ψ (P ) = ψ (Q)ψ (P/Q) ≻ ≻ ≻ ≻ Q≥P ∗−1 = ψ (Q) Q≥P k−1 ∗−1 l+1 l = ψ (P ) + (−1) ♯{(c , . . . , c ) ∈ N | c +··· + c = k} 1 l 1 l ≻ >0 l=1 k−1 k− 1 ∗−1 l+1 = ψ (P ) + (−1) k − l l=1 k−1 k− 1 ∗−1 k+1 l = ψ (P ) + (−1) (−1) l=1 ∗−1 k+1 = ψ (P )− (−1) = ε (P ) = 0. Let E , . . . , E be the irreducible components of P , n their respective cardinality, and P the 1 i noncrossing partition whose blocks are Jn +··· + n + 1, n +··· + n K, 1 ≤ i ≤ k. Then: 1 i−1 1 i ∗−1 ∗−1 ψ ∗ ψ (P ) = ψ (Q) ≻ ≻ P≤Q ∗−1 = ψ (Q) + 0 P≤Q l+1 l = (−1) ♯{(c , . . . , c ) ∈ N | c +··· + c = k} 1 l 1 l >0 l=1 k−1 k− 1 k+1 l = (−1) (−1) l=0 1 if k = 1, 0 otherwise. ∗−1 Let α = ψ ∗ ψ , and define β ∈ M by: ≺ B k+1 (−1) if P is irreducible, β(P ) = for P ∈ NCP(k, n). 0 otherwise For any Q ∈ NCP we denote by bl(Q) the number of blocks of Q. Let P ∈ NCP(k, n). bl(Q)+1 β ∗ α(P ) = (−1) . Q≥P, Q irreducible, the factors of P/Q irreducible If P is not irreducible, then for any Q ≥ P , either Q is not irreducible or one of the factors of P/Q is not irreducible. Hence, in this case, β∗ α(P ) = 0 = ε (P ). Let us now assume that P is irreducible. If P ∈ NCP(1, n), then β ∗ α(P ) = 1 = ε (P ). Let us assume that P ∈ NCP(k, n), with n ≥ 2. As P is irreducible, it can be written as: P = I ⋄ (∅, P , . . . , P ,∅), n 1 n−1 where P , . . . , P ∈ NCP . We denote by E the irreducible components of P . If some P 1 n−1 0 i,j i i is the empty partition, then of course it has no irreducible components, so there are no E for i,j this index i. But since k ≥ 2, at least one of the P is non-empty. We denote by J the set of pairs (i, j) such that 1 ≤ i ≤ n− 1 and such that P has at least j irreducible components. The set J thus indexes the meaningful P . There is a bijection i,j  Y  {Q ∈ NCP | Q ≥ P} −→ {Q ∈ NCP | Q ≥ P }×{0, 1} i,j i,j i,j (i,j)∈J Q 7−→ (Q , ǫ ) , i,j i,j i,j∈J where for any (i, j) ∈ J, Q is the noncrossing partition formed by the blocks of Q included in i,j Q , and ǫ = 0 if the base block of P and the base block of P are included in the same block i,j i,j i,j 37 of Q, and 1 otherwise. Hence: Y X bl(Q )+1 bl(Q ) i,j i,j β ∗ α(P ) = (−1) + (−1) = 0 = ε (P ). Q ≥P , (i,j)∈J i,j i,j Q irreducible, i,j the factors of P /Q irreducible i,j i,j ∗−1 ∗−1 This shows that β ∗ α(P ) = 0 = ε (P ), and therefore β = α = ψ ∗ ψ . B ≻ 5.5 On the inverse of the “free” universal map ψ Lastly we investigate the behaviour of ψ , the universal map associated to the left half-shuffle exponential — the one relating free cumulants and moments in free probability. Not surprisingly, 1 2n its combinatorics involves the Catalan numbers cat = . In fact the following lemma n+1 n+1 n characterizes the Catalan number, as it allows to compute them inductively. Lemma 5.5.1. For any n ≥ 1: ⌊ ⌋ n− k n−k+1 (−1) cat = δ . n−k n,1 k=0 Proof. We denote by P the free non-symmetric operad on one binary generator: for any n ≥ 1, P(n) is the vector space generated by the set of plane binary trees with n leaves (so has dimension cat ), and the operad composition law is given by grafting on leaves. For any p ∈ P(n), q , . . . , q ∈ P, we put: 1 k p ◭ (q . . . q ) = p◦ (I, . . . , I, p , I, . . . , I, p , I, . . . , I). 1 k 1 k | {z } 1≤i <...<i ≤n p is position i j j In particular, p ◭ (1) = p and, if k > n then p ◭ (q . . . q ) = 0. We denote by I the unique 1 k plane binary tree with one leaf and by Y the unique plane binary tree with two leaves. For all n ≥ 1, we define inductively X ∈ P(n) by X = 1 and: n 1 ⌊ ⌋ k+1 k ∀n ≥ 2, X = (−1) X ◭ Y . n n−k k=1 P Q We also put X = X . Then X is the unique solution in P(n) of the equation: n≥1 k+1 k X = I + (−1) X ◭ Y , k=1 or equivalently: k k (−1) X ◭ Y = I. k=0 Let us consider X = I +X∨X, where ∨ is the operator that grafts two binary trees onto a new common root. Then: ∞ ∞ X X k ′ k k (−1) X ◭ Y = I − Y + 0 + (X ∨ X) ◭ Y k=0 k=0 X X i j = I − Y + (X ◭ Y )∨ (X ◭ Y ) k=0 i+j=k 38   ∞ ∞ X X i i j j   = I − Y + (−1) X ◭ Y ∨ (−1) X ◭ Y i=0 j=0 = I − Y + I ∨ I = I. Hence, X = X, so X = I + X ∨ X. An easy induction on n implies that X is the sum of all plane binary trees with n leaves. Sending any plane binary tree to 1, we get, for any n ≥ 2: n n ⌊ ⌋   ⌊ ⌋ 2 2 X X k k k+1 k+1 X (1) = cat = (−1) X (1) = (−1) cat , n n n−k n−k n− k n− k k=1 k=1 which gives the announced formula. For the following proposition, recall that J denote the finest partitions and I denote the n n coarsest partitions, for n ≥ 1. ∗−1 n+1 Proposition 5.5.2. For any n ≥ 1, we have ψ (J ) = (−1) cat . n n ∗−1 −1 Proof. We put κ = Θ (ψ ). Since ψ x Θ(κ) = ε , we see that ε = ε + κ ≺ ε . Hence, ≺ B B Δ B for all n ≥ 1: δ = (κ⊗ ε )◦ Δ (J ). n,1 B ≺ n A study of uppersets of J proves that: X X n− a −···− a + 1 1 l Δ(J ) = J ⊗ J ··· J , n n−a −···−a a a 1 1 l l l=0 a +···+a ≤n 1 l X X n− a −···− a 1 l Δ (J ) = J ⊗ J ··· J . ≺ n n−a −···−a a a 1 l 1 l a +···+a ≤n l=0 1 l For any k ≥ 1, we have ε (J ) = δ , so: B k k,1 X X n− a −···− a 1 l (κ⊗ ε )◦ Δ (J ) = κ(J )⊗ δ ··· δ B ≺ n n−a −···−a a ,1 a ,1 1 1 l l l=0 a +···+a ≤n 1 l n− l ∗−1 = E (J ) n−l l=0 = δ . n,1 ∗−1 Hence, the sequence (ψ (J )) is the unique sequence (a ) such that for all n ≥ 1: n n≥1 n n≥1 n− l a = δ . n−l n,1 l=0 n+1 By Lemma 5.5.1, a = (−1) cat for all n. n n For any P ∈ NCP(k, n): ∗−1 ∗−1 ψ ∗ ψ (P ) = ψ (P ) = δ . ≺ P,I ≺ ≺ n Q≥P 39 ∗−1 So ψ (P ) = µ (P, I ), where µ is the Möbius function of the poset NCP(n). Proposition 5.5.2 shows that the Euler characteristic of NCP(n) is: n+1 µ (J , I ) = (−1) cat . n n n For any m , . . . , m ≥ 1, we put: 1 k I = {J1, m K, Jm + 1, m + m K, . . . , Jm +··· + m + 1, m +··· + m K}. m ,...,m 1 1 1 2 1 k−1 1 k 1 k Let P ∈ NCP. Then P can be uniquely written as: P = I ⋄ (∅, P , . . . , P ,∅, . . . ,∅, P , . . . , P ,∅), n +1,...,n +1 1,1 1,n 1 1 k,1 k,n k k where k ≥ 1, n , . . . , n ≥ 0 and for all i, j, P is a noncrossing partition, maybe empty. Note 1 k i,j that the irreducible components of P are the noncrossing partitions I ⋄ (∅, P , . . . , P ,∅). n +1 i,1 i,n i i For any Q ∈ NCP, we denote Q = I ⋄ (∅, Q). We have a poset isomorphism: {Q ∈ NCP | Q ≥ P} −→ NCP(k)× {Q ∈ NCP | Q ≥ P }. i,j i,j The bijection sends Q to (Q , (Q ) ), where Q is determined by identifying the base blocks 0 i,j i,j 0 of the irreducible components of P with the k blocks of J , and Q is obtained by identifying k i,j the base block of the ith irreducible component of P with the block of P , the blocks of P i,j i,j being conserved. Hence: ∗−1 k+1 ∗−1 ψ (Q) = (−1) cat . ψ ( P ). k i,j ≺ ≺ i,j ∗−1 This allows to compute ψ (P ) by induction on the number of blocks of cardinality ≥ 2. For example: ∗−1 ∗−1 ψ = −cat .ψ = −cat .cat , 2 2 3 ≺ ≺ ∗−1 ∗−1 3 ψ = −cat .ψ = −cat . ≺ ≺ 2 References [1] M. Aguiar, S. Mahajan, Monoidal functors, species and Hopf algebras, vol. 29 of CRM Monograph Series. American Mathematical Society, Providence, RI, 2010. With forewords by K. Brown, S. Chase and A. Joyal. [2] B. Baumeister, K.-U. Bux, F. Götze, D. Kielak, H. Krause, Non-crossing partitions, arXiv:1903.01146. [3] P. Biane, Some properties of crossings and partitions, Discrete Math. 175 (1997), 41. [4] P. Biane, Free probability and combinatorics, Proceedings of the International Congress of Mathematicians, Vol. II (Beijing, 2002), 765. [5] Y. Bruned, M. Hairer, L. Zambotti, Algebraic renormalisation of regularity structures, Invent. Math. 215 (2019), 1039. [6] D. Calaque, K. Ebrahimi-Fard, D. Manchon, Two interacting Hopf algebras of trees: A Hopf-algebraic ap- proach to composition and substitution of B-series, Adv. Appl. Math. 47 (2011), 282. [7] F. Chapoton, Un théorème de Cartier–Milnor–Moore–Quillen pour les bigèbres dendriformes et les algèbres braces, J. Pure Appl. Algebra 168 (2002), 1. [8] G. C. Drummond-Cole, An operadic approach to operator-valued free cumulants, Higher Structures 2 (2018), [9] G. C. Drummond-Cole, A non-crossing word cooperad for free homotopy probability theory, MATRIX Book Series 1 (2018), 77. 40 [10] K. Ebrahimi-Fard, F. Fauvet, D. Manchon, A comodule-bialgebra structure for word-series substitution and mould composition, J. Algebra 489 (2017), 552. [11] K. Ebrahimi-Fard, F. Patras, Cumulants, free cumulants and half-shuffles, Proc. Royal Soc. A 471 2176, (2015). [12] K. Ebrahimi-Fard, F. Patras, The splitting process in free probability theory, Int. Math. Res. Notices 9 (2016), [13] K. Ebrahimi-Fard, F. Patras, Monotone, free, and boolean cumulants from a Hopf algebraic point of view, Adv. Math. 328 (2018), 112. [14] K. Ebrahimi-Fard, F. Patras, Shuffle group laws. Applications in free probability, Proc. London Math. Soc. 119 (2019), 814. [15] L. Foissy, Les algèbres de Hopf des arbres enracinés décorés. I, Bull. Sci. Math. 126 (2002), 193. [16] L. Foissy, Bidendriform bialgebras, trees, and free quasi-symmetric functions, J. Pure Appl. Algebra 209 (2007), 439. [17] L. Foissy, Algebraic structures associated to operads, arXiv:1702.05344. [18] R. M. Friedrich, J. McKay, Homogeneous Lie Groups and Quantum Probability, arXiv:1506.07089. [19] F. Gabriel, Combinatorial theory of permutation-invariant random matrices I: partitions, geometry and renor- malization, arXiv:1503.02792. [20] I. Gálvez-Carrillo, J. Kock, A. Tonks, Decomposition spaces, incidence algebras and Möbius inversion I: basic theory, Adv. Math. 331 (2018), 952. [21] I. Gálvez-Carrillo, J. Kock, A. Tonks, Decomposition spaces in combinatorics, arXiv:1612.09225. [22] M. Gerstenhaber, A. A. Voronov, Homotopy G-algebras and moduli space operads, Int. Math. Res. Notices 3 (1995), 141. [23] T. Hasebe, F. Lehner, Cumulants, Spreadability and the Campbell–Baker–Hausdorff Series, arXiv:1711.00219. [24] M. Josuat-Vergès, F. Menous, J.-C. Novelli, J.-Y. Thibon, Free cumulants, Schröder trees, and operads, Adv. Appl. Math. 88 (2017), 92. [25] M. G. Kendall. The Advanced Theory of Statistics. Vol. I. J. B. Lippincott Co., Philadelphia, 1944. [26] J. Kock, M. Weber, Faà di Bruno for operads and internal algebras, J. London Math. Soc. 99 (2019), 919. [27] G. Kreweras, Sur les partitions non croisees d’un cycle, Discrete Math. 1 (1972), 333. [28] F. Lehner, Free cumulants and enumeration of connected partitions, Europ. J. Combinatorics 23 (2002), [29] C. Male, Traffic distributions and independence: permutation invariant random matrices and the three notions of independence. To appear in Mem. Amer. Math. Soc. arXiv:1111.4662. [30] D. Manchon, A review on comodule-bialgebras, in the proceedings of the 2016 Abel Symposium “Computation and Combinatorics in Dynamics, Stochastics and Control”, Springer’s Abel Symposia vol. 13, 2018. [31] S. Manzel, M. Schürmann, Non-Commutative Stochastic Independence and Cumulants, Infin. Dimensional Anal. Quantum Probab. Relat. Top. 20 (2017), 1750010. [32] M. Mastnak, A. Nica, Hopf algebras and the logarithm of the S-transform in free probability, Trans. Amer. Math. Soc. 362 (2010), 3705. [33] J. McCammond, Noncrossing Partitions in Surprising Locations, Am. Math. Mon. 113 (2006), 598. [34] A. Nica, R. Speicher, Lectures on the combinatorics of free probability, London Mathematical Society Lecture Note Series, 335 Cambridge University Press, 2006. [35] G.-C. Rota, On the Foundations of Combinatorial Theory I. Theory of Möbius Functions, Z. Wahrschein- lichkeitstheorie 2 (1964), 340. [36] G.-C. Rota, T. C. Wallstrom, Stochastic Integrals: A Combinatorial Approach, Ann. Probab. 25 (1997), [37] W. R. Schmitt, Incidence Hopf algebras, J. Pure Appl. Algebra 96 (1994), 299. [38] R. Simion, Noncrossing partitions, Discrete Math. 217 (2000), 367. [39] T. P. Speed, Cumulants and Partition Lattices, Austral. J. Statist. 25 (1983), 378. [40] R. Speicher, Multiplicative functions on the lattice of non-crossing partitions and free convolution, Math. Ann. 298 (1994), 611. [41] R. Speicher, Combinatorial theory of the free product with amalgamation and operator-valued free probability theory, Memoirs of the AMS 627 (1998). [42] D. Voiculescu, Free Probability Theory: Random Matrices and von Neumann Algebras, Proceedings of the International Congress of Mathematicians, Zürich, Switzerland 1994. Birkhäuser Verlag, Basel, Switzerland,

Journal

Mathematics – arXiv (Cornell University)

Published: Jul 2, 2019

References

  • Monoidal Functors, Species and Hopf Algebras
    Aguiar
  • Non-crossing partitions
    Baumeister
  • Some properties of crossings and partitions
    Biane
  • Free probability and combinatorics
    Biane
  • Algebraic renormalisation of regularity structures
    Bruned
  • Two interacting Hopf algebras of trees: a Hopf-algebraic approach to composition and substitution of B-series
    Calaque
  • Un théorème de Cartier–Milnor–Moore–Quillen pour les bigèbres dendriformes et les algèbres braces
    Chapoton
  • An operadic approach to operator-valued free cumulants
    Drummond-Cole
  • A non-crossing word cooperad for free homotopy probability theory
    Drummond-Cole
  • A comodule-bialgebra structure for word-series substitution and mould composition
    Ebrahimi-Fard
  • Cumulants, free cumulants and half-shuffles
    Ebrahimi-Fard
  • The splitting process in free probability theory
    Ebrahimi-Fard
  • Monotone, free, and Boolean cumulants from a Hopf algebraic point of view
    Ebrahimi-Fard
  • Shuffle group laws. Applications in free probability
    Ebrahimi-Fard
  • Les algèbres de Hopf des arbres enracinés décorés. I
    Foissy
  • Bidendriform bialgebras, trees, and free quasi-symmetric functions
    Foissy