# On the partial categorification of some Hopf algebras using the representation theory of towers of J-trivial monoids and semilattices.

1 Introduction

Since Frobenius it has been known that the self-dual Hopf algebra of symmetric functions encodes the representation theory of the tower of symmetric groups Sym through the Frobenius character map. Namely, Sym is isomorphic to the Grothendieck group of the category of simple modules of the symmetric groups, and the product and the coproduct of Schur functions encode respectively the induction and the restriction rule for simple modules (see e.g. [Gei77]). In [KT97], Krob and Thibon discovered that the same construction for the tower of Hecke algebras at q = 0 gives rise to the pair of dual Hopf algebras NCSF and QSym (since the algebras are not semisimple, one needs to consider both the categories of simple and projective modules, which gives two Grothendieck rings [G.sub.0](A) and [K.sub.0](A). This sparked a keen interest in studying Grothendieck rings arising from towers of algebras ([HNT06], [Kho99], [SY13] ...).

A natural but long running open question is that of categorification:

Problem 1.1 Which (pairs of dual) combinatorial Hopf algebras can be recovered as Grothendieck groups of some tower of algebras?

In particular, is it possible to categorify the combinatorial Hopf algebras of Free Quasi Symmetric Functions, or the Planar Binary Tree algebra of Loday Ronco.

In [BL09], Bergeron and Li propose an axiomatic definition of towers of algebras which guarantees that the associated Grothendieck rings are Hopf algebras. In [BLL12] Bergeron, Lam, and Li proves further that those axioms are very strong: namely the tower of algebras is necessarily of graded dimension [r.sup.n]n!.

In order to explore a larger setting which includes our favorite examples, we drop axioms (4) and (5), and weaken axiom (3) not to be necessarily two sided. On the other hand we focus on towers of algebras of J-trivial monoids in order to take advantage of recent progress in the representation theory of those monoids which is very combinatorial (see e.g. [[DHS.sup.+]11]).

In Section 2, we specify the axiomatic definition of towers of algebras we will be working with, and recall some results on the representation theory of J-trivial monoids and semilattices, and in particular the description of simple and projective modules.

We proceed in Section 3 with a general formula for inducing a quotient of an idempotent-generated module from an algebra to a super algebra, and specialize it in Section 4 to derive a combinatorial description of the induction rule of simple modules for a tower A of J-trivial monoids, that is the product in [G.sub.0](A). Similarly, we give a combinatorial description of the product in [K.sub.0](A) and of the coproduct in [G.sub.0](A). As an example, we recover Krob-Thibon's theorem: for the tower A: = [([H.sub.n](0)).sub.n] of 0-Hecke algebras, [G.sub.0](A)/[K.sub.0](A) forms the pair of dual Hopf algebras of Quasi Symmetric Functions and Non Commutative Symmetric Functions. Note however that, in most other cases, the coproduct is not compatible with the product, so that we do not get Hopf algebras.

In Section 4.3, we further specialize those results to towers of join-semilattices (that is commutative and idempotent J-trivial monoids). The theory is particularly simple in this case since semilattices are semisimple--so that [G.sub.0](A) and [K.sub.0](A) coincide--and the induction rule admits a purely order-theoretical description.

Despite the apparent simplicity of this setting, we show in Section 5 that the towers of semilattices given respectively by the permutohedrons, the Tamari, and the Boolean lattices can be used to partially categorify the Hopf algebras of Free Quasi Symmetric Functions (FQSym), Planar Binary Trees (PBT), and Non Commutative Symmetric Functions (NCSF). Namely, in each case the induction and restriction rules are described respectively by the product and the coproduct in one of the natural bases of those Hopf algebras. However the basis for the product does not coincide with the basis for the coproduct, and hence does not give a full categorification of the dual Hopf algebra structure. It is to be noted that adding some radical to the semilattices has the effect, on G0, of deforming the product without altering the coproduct; a work in progress is to try to use this trick to recover the full categorification.

Finally, in Section 6, we give a complete combinatorial description of the Grothendieck rings for the tower of the monoids of Non Decreasing Parking Functions. We obtain two copies of NCSF on different bases, including the well known ribbon basis [R.sub.I].

2 Preliminaries

2.1 Towers of algebras

In [BL09], Bergeron and Li propose an axiomatic definition of towers of algebras which guarantees that the Grothendieck rings of their categories of simple and projective modules give a pair of dual Hopf algebras. They further prove in [BLL12] that those axioms are very strong, implying that the tower of algebras is of graded dimension [r.sup.n]n!. We recall here the axioms of [BL09]:

Definition 2.1 Let [([A.sub.i]).sub.i [greater than or equal to] 0] be a family of associative algebras endowed with a collection of algebra morphisms [([[rho].sub.m,n]: [A.sub.m] [cross product] [A.sub.n] [??] [A.sub.m+n]).sub.m,n [greater than or equal to] 0] satisfying the following axioms:

(1) For i [greater than or equal to] 0, [A.sub.i] is a finite dimensional algebra with unit [1.sub.i], and [A.sub.0] [approximately equal to] K.

(2) The multiplication homomorphisms [[rho].sub.m,n] are injective and associative (in the sense that the external multiplication morphism they implement on the direct sum [[direct sum].sub.i [greater than or equal to] 0] [A.sub.i] is associative).

(3) For m, n [greater than or equal to] 0 the algebra [A.sub.m+n] is a two-sided projective [A.sub.m] [cross product] [A.sub.n]-module.

(4) A relation between the decomposition of [A.sub.m+n] as a left [A.sub.m] [cross product]] [A.sub.n]-module and as a right [A.sub.m] [cross product] [A.sub.n]-module holds.

(5) An analogue of Mackey's formula relating induction and restriction holds.

Bergeron and Li then define a tower of algebras as a family of algebras as stated above verifying the five previous axioms.

In order to explore a larger setting which includes our favorite examples, we drop axioms 4 and 5 and weaken axiom 3 into the following:

(3') for m, n [greater than or equal to] 0, the algebra [A.sub.m+n] is a right (resp. left) projective [A.sub.m] [cross product] [A.sub.n]-module.

Definition 2.2 A right (resp. left) tower of algebra A is a family [([A.sub.i]).sub.i [greater than or equal to] 0] of algebras as above satisfying axioms (1), (2) and (3').

For any field K of characteristic 0, the K-algebra KM of a monoid (M, x), is the K-algebra with basis [{[[epsilon].sub.m]}.sub.m [member of] M], and multiplication obtained by linearization of the product of M:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

A tower of monoids is a family of monoids [([M.sub.i]).sub.i [greater than or equal to] 0] together with a collection of morphisms such that [([KM.sub.i]).sub.i [greater than or equal to] 0] is a tower of algebras for the corresponding embedding.

We recall the definition of the Grothendieck groups [G.sub.0] and [K.sub.0] of an associative finite dimensional algebra F (see [CR90]). For a category F of finitely generated left F-modules, the Grothendieck group G(F) is the abelian group generated by symbols [M], one for every isomorphism class of modules M in F and relations [M] = [L] + [N] for any short exact sequence 0 [right arrow] L [right arrow] M [right arrow] N [right arrow] 0 in F. We let [G.sub.0](F) be the Grothendieck group of the category of finitely generated simple F-modules and [K.sub.0](F) the Grothendieck group of the category of finitely generated projective F-modules. More combinatorially, it is easy to prove that [G.sub.0](F) is the free Z-module with basis [{[[S.sub.i]]}.sub.i [member of] I], where [([S.sub.i]).sub.i [member of] I] is a complete set of non pairwise isomorphic simple F-modules. For an F-module M, we can decompose [M] = [[summation].sub.i [member of] I] [c.sub.i] [[S.sub.i]] where [c.sub.i] is the multiplicity of [S.sub.i] in M. Continuing the same way, the set {[Pi]}ie/ of projective covers of the simple modules form a basis of the Z-module [K.sub.0](F).

Let A be a tower of algebras. Axiom (1) ensures that the Grothendieck groups

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

are graded connected. Axioms (2) and (3) allows us to define induction and restriction functors on [G.sub.0] and [K.sub.0], endowing them with a multiplication and a comultiplication. For M and [A.sub.m]-module and N an [A.sub.n]-module, the product and coproduct of their classes [M] and [N] in [G.sub.0] (or in [K.sub.0]) are given respectively by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The two Grothendieck rings are closely related thanks to the natural pairing <,> defined on P [member of] [K.sub.0] ([A.sub.m]) and M [member of] [G.sub.0]([A.sub.n]) by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

In particular, for {[P.sub.1], ..., [P.sub.n]} a complete set of indecomposable projective modules and {[S.sub.1], ..., [S.sub.n]} their associated simple irreducible module, we have <[[P.sub.i]]>, [[S.sub.j]]> = [[delta].sub.i,j]. With the three axioms given above, [G.sub.0] and [K.sub.0] are dual graded free Z-modules with product and coproduct.

Induction on [K.sub.0] and restriction on [G.sub.0] are related thanks to Frobenius reciprocity.

Theorem 2.3 (Frobenius reciprocity) Ind is left adjoint for Res.

The right adjoint of Res is called coinduction and is noted Coind. We have an equality between Res and Coind for groups and this equality also holds in the semilattice case. However, these functors are not equal in the general case, for example for the tower of NDPF that we introduce in Section 6.

2.2 Categorification

We will use the definition of naive categorification as defined in [Sav14].

2.3 J-trivial monoids, semilattices, and their representation theory

We recall here some facts about J-trivial monoids and their representations. For details, see for example [Pin11] and [[DHS.sup.+]11] respectively. Let M be a monoid, and write E(M) for the set of idempotents of M. In the sequel, we always assume M to be finite. Define the J preorder [[less than or equal to].sub.J] on M by x [[less than or equal to].sub.J] y if x [member of] MyM. This preorder induces an equivalence relation, namely xJy if and only if MxM = MyM. The equivalence classes are called J-classes.

Definition 2.4 A monoid M is J-trivial if all its J-classes are of cardinality 1.

Equivalently, M is J-trivial if j is a partial order. In this case, we write [J.sub.<] (x) the set of all elements strictly smaller than x for the J-order. We define similarly the right preorder [[less than or equal to].sub.R] by x [[less than or equal to].sub.R] y if x [member of] yM. This preorder gives R-classes and we call R-trivial a monoid for which [[less than or equal to].sub.r] is a partial order. The symmetric definition on the left side leads to L-trivial monoids. A monoid is J-trivial if it is both L-trivial and R-trivial. For an element x [member of] M, we denote by [R.sub.<] (x) the set of all elements of M strictly smaller than x for the R-order. For a tower of monoids ([A.sub.i]) = ([KM.sub.i]) and x [member of] [M.sub.i], we will note [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] the subspace of [A.sub.i] generated by [R.sub.<](x).

The representation theory of J-trivial monoids is essentially independent of the ground field K. The simple modules admit an easy description. Namely, for x [member of] M, define [S.sub.x] = K (xM/[R.sub.<](x)). It's a right module of dimension 1 where, denoting the single basis element by ex, the action is given by [[epsilon].sub.x] x m = [[epsilon].sub.x] if [x.sub.m] = x and [[epsilon].sub.x] x m = 0 otherwise.

Theorem 2.5 Let M be J-trivial monoid. The set [([S.sub.e]).sub.e [member of] E{M)] is a complete set of pairwise non-isomorphic simple KM-modules.

We now turn to the description of the indecomposable projective modules. For x [member of] M, set:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

For e an idempotent, one can define the module [P.sub.e] = K(eM/{m [member of] M: lfix(m) [<.sub.J] (e)}). Its basis is indexed by the family {x: lfix(= e}.

Theorem 2.6 ([[DHS.sup.+]11], Corollary 3.22) Let M be a J-trivial monoid. The set (Pe)eeE(M) is a complete set of pairwise non-isomorphic indecomposable projective KM-modules.

The radical of the algebra of an J-trivial monoid viewed as a module on itself is given by its non idempotent elements. It is thus natural to consider the semisimple case, when all the elements of M are idempotent. It turns out that M is then necessarily commutative thanks to the following theorem.

Theorem 2.7 ([Pin11]) The class of idempotent (or equivalently semisimple) J-trivial monoids coincide with the class of finite semilattices (L, [disjunction]).

In particular, a good source of examples is to take one's favorite finite lattice, and consider the monoid given by its join (resp. its meet) operation, together with its smallest (resp. largest) element as identity.

3 Induction lemma

We now introduce our key lemma.

Lemma 3.1 Let B [subset or equal to] A two K-algebras, f [member of] B an idempotent and U [subset or equal to] fB a right B-modul[member of]. We have the following A-mod isomorphism:

[Ind.sup.A.sub.B](fB)/U [approximately equal to] (fA)/(UA).

4 Representation theory of towers of J-trivial monoids

4.1 General case

In the following section, we fix a tower of monoids [([M.sub.i]).sub.i [greater than or equal to] 0] with A = [([A.sub.i]).sub.i [greater than or equal to] 0] the associated tower of algebras. Thanks to J-triviality, the representation theory of such a monoid is combinatorial. In order to describe the general rules, we need to expand the previous definitions of rfix and lfix to tensorial algebras. For x [member of] [M.sub.m+n] set

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

and define similarly [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. We can therefore state the following proposition:

Proposition 4.1 Let [([A.sub.i]).sub.i [greater than or equal to] 0] = [([KM.sub.i]).sub.i [greater than or equal to] 0] be a tower of monoid algebras. Take x [member of] [M.sub.m+n], and let [S.sub.x] be the associated [A.sub.m+n]-simple module, then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. [S.sub.x] = [S.sub.e] where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Thanks to Frobenius Reciprocity (Theorem 2.3) we directly get the product rule in [K.sub.0].

Proposition 4.2 Let e be an idempotent of [M.sub.m] [cross product] [M.sub.n] and [P.sub.e] be the projective module associated to e. Then,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

We can now study how this lemma applies in the case of a tower of J -trivial monoids. Each simple module M can be interpreted as an element x of a graded component [A.sub.n] of the tower, and the action is characterized by the partial ordering. Indeed, [A.sub.n] acts by 1 on M for all elements {z [[greater than or equal to].sub.R] x} and by 0 otherwise. Given two simple modules [S.sub.f] and [S.sub.g] of [A.sub.m] and [A.sub.n], the tensor product [S.sub.f] [cross product] [S.sub.g] is a simple two sided ([A.sub.m] [cross product] [A.sub.n])-module. Thanks to lemma 3.1, the induced module on [A.sub.m+n] is the quotient K(f x g)[A.sub.m+n]/([R.sub.<] (f) x [R.sub.<] (g) [A.sub.m+n]).

Let [S.sub.e] and [S.sub.f] be two simple modules of respectively [A.sub.m] and [A.sub.n]. Let X(e,f) denote the subset of [M.sub.m+n] containing all elements in [[rho].sub.m,n]{e, 1) [[rho].sub.m,n] (1, f)[M.sub.m+n] which are not in [[rho].sub.m,n]{[R.sub.<] (e), 1) [[rho].sub.m,n] (1, [R.sub.<](f)). Namely, by identifying [M.sub.m] and [M.sub.n] with their copies embedded in [M.sub.m+n] we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The following theorem describes combinatorially the induction rule for simple modules:

Theorem 4.3 (Induction rule for J-trivial monoids) Let M = ([M.sub.i]) be a tower of J-trivial monoids and A = ([A.sub.i]) the related tower of algebras. With the above notations, the induction rule for two simple modules [S.sub.e] and [S.sub.f] is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Proof: Straightforward application of Lemma 3.1 on the construction of the simple modules given in Theorem 2.5.

4.2 Categorification of the pair of Hopf Algebras QSym/NCSF

We recover Krob-Thibon's Theorem [KT97] using Theorem 4.3. It is well known that the 0-Hecke algebra [H.sub.n] at q = 0 is the algebra of the 0-Hecke monoid [H.sub.n](0) which is J-trivial. The idempotents are naturally indexed by the subsets I of {1, ..., n - 1}, with lfix([[pi].sub.[sigma]]) and rfix([[pi].sub.[sigma]]) given respectively by the left and right descent sets [D.sub.L]([sigma]) and [D.sub.R]([sigma]) of [sigma].

Let us first recover the product rule in [G.sub.0]. Each simple module [S.sub.I] can be constructed as [[pi].sub.[sigma]][H.sub.n](0)/[R.sub.<]([[pi].sub.[sigma]]), where [sigma] is any permutation with left descent set I. Here we choose [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where [[sigma].sub.I] is the maximal element of the parabolic subgroup [G.sub.I].

Consider a simple ([H.sub.m] [cross product] [H.sub.n])-module [S.sub.I] [cross product] [S.sub.J]. It can be written as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Using Lemma 3.1, the induced module on [H.sub.m+n] is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Note that Q = {[[pi].sub.[mu]][[pi].sub.i][[pi].sub.v]: i [not member of] [Des.sub.R] [mu], i [not equal to] m, [[pi].sub.v] [member of] [[rho].sub.m,n]([H.sub.m](0) x [H.sub.n](0))}. Therefore,

Q[H.sub.m+n] = {[[pi].sub.[mu]][[pi].sub.i][[pi].sub.v]: i [not member of] [Des.sub.R] [mu], i [not equal to] m, [[pi].sub.v] [member of] [H.sub.m+n]}.

and it follows that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

It is well known that the permutations v with [Des.sub.R](v) [subset or equal to] {m} are the permutations appearing in the shuffle product [id.sub.m] [??] [id.sub.n]. At the level of descents we recover the shuffle product of NCSF.

For the coproduct in G0, we need to study the restrictions of each simple module [S.sub.I] of [H.sub.m+n] on [H.sub.m] [cross product] [H.sub.n]. In terms of descent sets, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] amounts to removing m from I and shifting the entries greater than m by -m; this is exactly the shifted deconcatenation rule of the fundamental basis of NCSF.

Altogether we proved that G0 is isomorphic to NCSF in the fundamental basis. By adjunction, we get the product in K0, then we use our knowledge of the pair QSym/NCSF and the Z-module duality to conclude.

4.3 Representation theory of towers of semilattices

For a tower of semilattices 0, each Li is semisimple. Then we have [G.sub.0](KL) = [K.sub.0](KL).

Because we combinatorially described the induction and restriction in [G.sub.0](A) for any algebra tower of J-trivial monoids, we have a complete combinatorial description of both Grothendieck rings of any tower of semilattices.

5 Partial categorification of FQSym, PBT, and NCSF

In the section, we assume that the reader is familiar with both Malvenuto-Reutenauer algebra FQSym ([MR95], [DHT02]) and the Loday-Ronco Planar Binary Tree Hopf algebra ([LR98]) and how it relates with FQSym ([HT09]).

5.1 The tower of permutohedron lattices

We first consider the tower of permutohedrons. Namely, for each n, take the left weak order <L on the n-th symmetric group [G.sub.n]. A potential definition for the weak order on permutation is that [sigma] [less than or equal to] [mu] if and only if inv([sigma]) [subset or equal to] inv([mu]). It is well known that it endows [G.sub.n] with a lattice structure, and we consider the semilattice [P.sub.n] = ([G.sub.n], [disjunction]), with the trivial representation as identity element. Remind that the J-order on [P.sub.n] is the reverse order of [<.sub.L]; the identity is the largest element.

Let [[rho].sub.m,n]: K[P.sub.m] [cross product] K[P.sub.n] [right arrow] K[P.sub.m+n] be the linear extension of the shifted concatenation on [P.sub.m] x [P.sub.n]. The morphism p is obviously injective. Thus we obtain a tower of semilattices KP = [[direct sum].sub.n [greater than or equal to] 0] K[P.sub.n]. It follows that inv([[rho].sub.m,n]{[sigma], [mu])) = inv([sigma]) [bar.[union]] inv([mu]) where [bar.[union]] is the shifted union.

We start by describing the product rule in [G.sub.0](P), that is the induction rule of simple modules. Let us fix a simple K([P.sub.m] [cross product] [P.sub.n])-module [S.sub.[sigma] [cross product] [mu]]. This simple module is the quotient

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

by definition of the product order. By Lemma 3.1, we have:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

This quotient is a subalgebra of K[R.sub.<]([sigma][bar.x] [mu]) and is quite easy to describe. The submonoid [R.sub.<]([sigma] [cross product] [mu]) [P.sub.m+n] is exactly the set of all permutations w [member of] [P.sub.m+n] such that inv(w) [subset] inv([sigma]) [bar.[union]] inv([mu]). Since [R.sub.<]([sigma] [bar.x] [mu]) consists of all permutations v such that inv(v) [subset or equal to] inv([sigma]) [bar.x] inv([mu]), we can state the following proposition:

Proposition 5.1 In the permutohedron tower, the induction rule for the simple modules is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

This gives the following product rule in [G.sub.0](P):

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Example 5.2 [[S.sub.(21)]] x [[S.sub.(231)]] = [[S.sub.(21453)]] + [[S.sub.(31452)]] + [[S.sub.(32451)]] + [[S.sub.(41352)]] + [[S.sub.(42351)]] + [[S.sub.(52341)]] + [[S.sub.(43251)]] + [[S.sub.(51342)]] + [[S.sub.(53241)]] + [[S.sub.(54231)]].

Using Frobenius formula, we directly obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Example 5.3 [DELTA]([[S.sub.(2413)]]) = [1] [cross product] [[S.sub.(2413)]] + [[S.sub.1]] [cross product] [[S.sub.(312)]] + [[S.sub.(12)]] [cross product] [[S.sub.(12)]] + [[S.sub.(312)]] [cross product] [[S.sub.1]] + [[S.sub.(2413)]] [cross product] [1].

Corollary 5.4 The map [[S.sub.[sigma]]] [right arrow] [G.sub.[sigma]] is an algebra isomorphism between [G.sub.0](V) and FQSym. The map [[S.sub.[sigma]]] [right arrow] [F.sub.[sigma]] is a coalgebra isomorphism between [G.sub.0](V) and FQSym.

Each [F.sub.[sigma]] or [G.sub.[sigma]] induced a FQSym-module morphism by left-multiplication. We obtain a categorification of the algebra (FQSym, [G.sub.[sigma]]) and a categorification of the coalgebra (FQSym, [F.sub.[sigma]]).

Note that the product and the coproduct are not compatible as bialgebras, so in particular we did not categorify FQSym as an auto-dual Hopf algebra.

5.2 The tower of Tamari lattices

We now turn to the tower of the Tamari lattice. The Tamari lattice is the lattice of binary trees ordered by tree rotations. We note [T.sub.n] the Tamari lattice of binary trees with n edges; [T.sub.n] has cardinality [C.sub.n] the nth Catalan number. In this paper, we will note the elements of the Tamari lattice as 132-avoiding permutations.

We construct a tower of semilattices by the embedding *: [T.sub.m] x [T.sub.n] [??] [T.sub.m+n] which consist in taking the Sylvester class of the shifted concatenation.

Example 5.5 (312) * (21) = (53214).

The product and the coproduct in the Grothendieck rings of KT can be computed from our previous construction on FQSym. Therefore, the maps [[T.sub.[sigma]]] [right arrow] [P.sub.[sigma]] and [[T.sub.[sigma]]] [right arrow] [Q.sub.[sigma]] are respectively algebra and coalgebra isomorphisms from [G.sub.0](T) to PBT making both diagrams of the definition of naive categorification commute.

Once again, we constructed categorifications of (PBT, [P.sub.T]) and (PBT, [Q.sub.T]). But we do not get a full Hopf categorification of the pair (PBT, [PBT.sup.*]).

5.3 The tower of Boolean lattices

Finally, let [B.sub.n] be the Boolean lattice of subsets of [1, n]. We write the elements of [B.sub.n] as binary words of size n. The concatenation embedding is an injective morphism making a tower B = [[direct sum].sub.m [greater than or equal to] 0] [B.sub.n] of semilattices. The product in [G.sub.0](B) easily follows from the remark [R.sub.<](u).

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

By duality, or using that [B.sub.n] is the semisimple quotient of [H.sub.n](0), the coalgebra structure on [G.sub.0](B) is isomorphic to QSym on the fundamental basis:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Unsurprisingly, the product and coproduct are again not compatible.

6 Non Decreasing Parking Functions

Definition 6.1 For n [greater than or equal to] 1, let [NDPF.sub.n] be the monoid of the non decreasing and regressive functions from [1, n] onto itself, endowed with the composition product. Denote a function f: i [??] [a.sub.i] [member of] NDPF, by the sequence ([a.sub.1], [a.sub.2], ..., [a.sub.n]); it satisfies 1 = [a.sub.1] [less than or equal to] [a.sub.2] [less than or equal to] ... [less than or equal to] [a.sub.n] and [a.sub.i] [less than or equal to] i.

This monoid and its representation theory, were studied in [HT09, [DHS.sup.+]11]. It's cardinality is the n-th Catalan number, and it is minimally generated by the idempotents n = (1, 2, ..., i, i, i + 2, ..., n - 1) for i [member of] [1, n - 1].

The exterior product [[rho].sub.m,n]: ([a.sub.1], ..., [a.sub.m]) x ([b.sub.1], ..., [b.sub.n]) [right arrow] ([a.sub.1], ..., [a.sub.m], [b.sub.1] + m, ..., [b.sub.m] + n) defines an associative and injective embedding from [NDPF.sub.m] [cross product] [NDPF.sub.n] to [NDPF.sub.m+n]. Thus we note NDPF = [[direct sum].sub.n [greater than or equal to] 0] [NDPF.sub.n], and the tower KNDPF satisfy Axioms (1) and (2). Verifying the third axiom is more tricky.

Proposition 6.2 [NDPF.sub.m+n] is a left projective ([NDPF.sub.m] [cross product] [NDPF.sub.n])-module.

Proof: We construct an explicit decomposition of [NDPF.sub.m+n] as [NDPF.sub.m] [cross product] [NDPF.sub.n]-module, and prove bijectively that each piece is isomorphic to a projective [NDPF.sub.m] [direct sum] [NDPF.sub.n] module.

Proposition 6.3 ([[DHS.sup.+]11]) The monoid [NDPF.sub.n] is J-trivial for all n. In particular its simple modules are all one dimensional.

The irreducible left [KNDPF.sub.n]-modules are thus entirely characterized by the action of the idempotent generators of K[NDPF.sub.n]. The eigenvalues of S on [[pi].sub.i] is 0 or 1 so we have [2.sup.n-1] simple K[NDPF.sub.n]-modules indexed by compositions. From now on, we will identify a simple [NDPF.sub.n]-module by the sequence ([b.sub.1], ..., [b.sub.n]) of his ordered eigenvalues on the generators ([[pi].sub.i]). We will note () = ([1.sup.0]) the unique irreducible [NDPF.sub.1]-module. Note that an irreducible [NDPF.sub.n]-module is described by n - 1 eigenvalues.

Proposition 6.4 The J-order on E([NDPF.sub.n]) is the Boolean lattice of [2.sup.n] elements.

The product in [K.sub.0](NDPF) is quite general thanks to [[DHS.sup.+]11]. We again use Lemma 3.1.

Thanks to Theorem 2.6 we can explicit the product in [K.sub.0](NDPF). Let [e.sub.I] and [e.sub.J] be two idempotents in respectively [NDPF.sub.m] and [NDPF.sub.n] indexed with compositions I of m - 1 and J of n - 1. We note [P.sub.I] = NDPFel the projective module associated with Se. By applying Lemma 3.1 we have:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

By Theorem 2.6 the projective module we obtain is:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

We deduce that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. We just proved:

Proposition 6.5 The map [K.sub.0](NDPF) [right arrow] NCSF defined by [[P.sub.I]] [right arrow] [R.sub.I] is an algebra isomorphism.

The product in [G.sub.0](NDPF) is quite tedious to write. To avoid a straightforward but technical proof, we use our knowledge of the algebra structure of [K.sub.0](NDPF), and take advantage of the fact that the Cartan operator C: [K.sub.0](NDPF) [right arrow] [G.sub.0](NDPF) is an isomorphism in our case. The Cartan operator is the Z-module morphism defined by the Cartan matrix. More precisely, for P a projective module, C[P] = [[summation].sub.i][c.sub.i][[S.sub.i]] where [c.sub.i] = dim(hom([P.sub.i], P)); that is C([P]) gives the composition factors of P, with multiplicities. Thanks to Theorem 2.6, it admits an explicit description for J-trivial monoids: [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Lemma 6.6 For k [greater than or equal to] 0 and l [greater than or equal to] 0 we have:

[([1.sup.k])][([0.sup.l])] = {[([c.sub.1], [c.sub.2], ..., [c.sub.k+l+1])]: [summation over (i)] [c.sub.i] [member of] {k, k + 1}}.

Theorem 6.7 Let [S.sub.a] = ([a.sub.1], [a.sub.2], ..., [a.sub.i], [1.sup.k]) [member of] [G.sub.0]([NDPF.sub.m]) and [S.sub.b] = ([0.sup.l], [b.sub.j], [b.sub.j+1], ..., [b.sub.n-1]) [member of] [G.sub.0]([NDPF.sub.n]), then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Theorem 6.8 The algebra G^NDPF is the free graded algebra with generators (), (0), (00), ....

Acknowledgements

The author would like to thank Florent Hivert and Nicolas M. Thiery for enlightening discussions and advise about this work. The author also thanks the anonymous referees for their excellent suggestions and remarks on the first draft of the current article. This research was driven by computer exploration using the open-source mathematical software Sage [Tea13] and its algebraic combinatorics features developed by the Sage-Combinat community [SCc08]

References

[BL09] Nantel Bergeron and Huilan Li. Algebraic structures on Grothendieck groups of a tower of algebras. Journal of Algebra, 321(8):2068-2084, 2009.

[BLL12] Nantel Bergeron, Thomas Lam, and Huilan Li. Combinatorial Hopf algebras and towers of algebras-dimension, quantization and functorality. Algebras and representation theory, 15(4):675-696, 2012.

[CR90] C.W. Curtis and I. Reiner. Methods of Representation Theory. Number vol. 1 in Methods of Representation Theory. Wiley, 1990.

[DHS+11] T. Denton, F. Hivert, A. Schilling, N.M. Thiery, et al. On the representation theory of finite J-trivial monoids. Seminaire Lotharingien de Combinatoire, 64:44, 2011.

[DHT02] Gerard Duchamp, Florent Hivert, and Jean-Yves Thibon. Noncommutative symmetric functions vi: free quasi-symmetric functions and related algebras. International Journal of Algebra and Computation, 12(05):671-717, 2002.

[Gei77] Ladnor Geissinger. Hopf algebras of symmetric functions and class functions. In Combinatoire et representation du groupe symetrique, pages 168-181. Springer, 1977.

[HNT05] Florent Hivert, J-C Novelli, and J-Y Thibon. The algebra of binary search trees. Theoretical Computer Science, 339(1):129-165, 2005.

[HNT06] Florent Hivert, Jean-Christophe Novelli, and Jean-Yves Thibon. Yang-Baxter bases of 0-Hecke algebras and representation theory of 0-Ariki-Koike-Shoji algebras. Advances in Mathematics, 205(2):504-548, 2006.

[HT09] Florent Hivert and Nicolas M. Thiery. The Hecke group algebra of a Coxeter group and its representation theory. J. Algebra, 321(8):2230-2258, 2009. arXiv:0711.1561.

[Kho99] Mikhail Khovanov. Nilcoxeter algebras categorify the Weyl algebra. arXiv:math/9906166, 1999.

[KT97] Daniel Krob and Jean-Yves Thibon. Noncommutative symmetric functions iv: Quantum linear groups and Hecke algebras at q= 0. Journal of Algebraic Combinatorics, 6(4):339-376, 1997.

[LR98] Jean-Louis Loday and Maria O Ronco. Hopf algebra of the planar binary trees. Advances in Mathematics, 139(2):293-309, 1998.

[MR95] Clauda Malvenuto and Christophe Reutenauer. Duality between quasi-symmetrical functions and the solomon descent algebra. Journal of Algebra, 177(3):967-982, 1995.

[Pin11] Jean-Eric Pin. Mathematical foundations of automata theory. Lecture notes, 2011.

[Sav14] Alistair Savage. Introduction to categorification. arXiv:1401.6037, 2014.

[SCc08] The Sage-Combinat community. Sage-Combinat: enhancing Sage as a toolbox for computer exploration in algebraic combinatorics, 2008. http://combinat.sagemath.org.

[SY13] Alistair Savage and Oded Yacobi. Categorification and Heisenberg doubles arising from towers of algebras. arXiv:1309.2513, 2013.

[Tea13] The Sage Team. Sage Mathematics Software (Version 5.12), 2013. http://www.sagemath.org.

Aladin Virmaux *

Laboratoire de Recherche en Informatique, Orsay, France

* Email: aladin.virmaux@lri.fr.

Since Frobenius it has been known that the self-dual Hopf algebra of symmetric functions encodes the representation theory of the tower of symmetric groups Sym through the Frobenius character map. Namely, Sym is isomorphic to the Grothendieck group of the category of simple modules of the symmetric groups, and the product and the coproduct of Schur functions encode respectively the induction and the restriction rule for simple modules (see e.g. [Gei77]). In [KT97], Krob and Thibon discovered that the same construction for the tower of Hecke algebras at q = 0 gives rise to the pair of dual Hopf algebras NCSF and QSym (since the algebras are not semisimple, one needs to consider both the categories of simple and projective modules, which gives two Grothendieck rings [G.sub.0](A) and [K.sub.0](A). This sparked a keen interest in studying Grothendieck rings arising from towers of algebras ([HNT06], [Kho99], [SY13] ...).

A natural but long running open question is that of categorification:

Problem 1.1 Which (pairs of dual) combinatorial Hopf algebras can be recovered as Grothendieck groups of some tower of algebras?

In particular, is it possible to categorify the combinatorial Hopf algebras of Free Quasi Symmetric Functions, or the Planar Binary Tree algebra of Loday Ronco.

In [BL09], Bergeron and Li propose an axiomatic definition of towers of algebras which guarantees that the associated Grothendieck rings are Hopf algebras. In [BLL12] Bergeron, Lam, and Li proves further that those axioms are very strong: namely the tower of algebras is necessarily of graded dimension [r.sup.n]n!.

In order to explore a larger setting which includes our favorite examples, we drop axioms (4) and (5), and weaken axiom (3) not to be necessarily two sided. On the other hand we focus on towers of algebras of J-trivial monoids in order to take advantage of recent progress in the representation theory of those monoids which is very combinatorial (see e.g. [[DHS.sup.+]11]).

In Section 2, we specify the axiomatic definition of towers of algebras we will be working with, and recall some results on the representation theory of J-trivial monoids and semilattices, and in particular the description of simple and projective modules.

We proceed in Section 3 with a general formula for inducing a quotient of an idempotent-generated module from an algebra to a super algebra, and specialize it in Section 4 to derive a combinatorial description of the induction rule of simple modules for a tower A of J-trivial monoids, that is the product in [G.sub.0](A). Similarly, we give a combinatorial description of the product in [K.sub.0](A) and of the coproduct in [G.sub.0](A). As an example, we recover Krob-Thibon's theorem: for the tower A: = [([H.sub.n](0)).sub.n] of 0-Hecke algebras, [G.sub.0](A)/[K.sub.0](A) forms the pair of dual Hopf algebras of Quasi Symmetric Functions and Non Commutative Symmetric Functions. Note however that, in most other cases, the coproduct is not compatible with the product, so that we do not get Hopf algebras.

In Section 4.3, we further specialize those results to towers of join-semilattices (that is commutative and idempotent J-trivial monoids). The theory is particularly simple in this case since semilattices are semisimple--so that [G.sub.0](A) and [K.sub.0](A) coincide--and the induction rule admits a purely order-theoretical description.

Despite the apparent simplicity of this setting, we show in Section 5 that the towers of semilattices given respectively by the permutohedrons, the Tamari, and the Boolean lattices can be used to partially categorify the Hopf algebras of Free Quasi Symmetric Functions (FQSym), Planar Binary Trees (PBT), and Non Commutative Symmetric Functions (NCSF). Namely, in each case the induction and restriction rules are described respectively by the product and the coproduct in one of the natural bases of those Hopf algebras. However the basis for the product does not coincide with the basis for the coproduct, and hence does not give a full categorification of the dual Hopf algebra structure. It is to be noted that adding some radical to the semilattices has the effect, on G0, of deforming the product without altering the coproduct; a work in progress is to try to use this trick to recover the full categorification.

Finally, in Section 6, we give a complete combinatorial description of the Grothendieck rings for the tower of the monoids of Non Decreasing Parking Functions. We obtain two copies of NCSF on different bases, including the well known ribbon basis [R.sub.I].

2 Preliminaries

2.1 Towers of algebras

In [BL09], Bergeron and Li propose an axiomatic definition of towers of algebras which guarantees that the Grothendieck rings of their categories of simple and projective modules give a pair of dual Hopf algebras. They further prove in [BLL12] that those axioms are very strong, implying that the tower of algebras is of graded dimension [r.sup.n]n!. We recall here the axioms of [BL09]:

Definition 2.1 Let [([A.sub.i]).sub.i [greater than or equal to] 0] be a family of associative algebras endowed with a collection of algebra morphisms [([[rho].sub.m,n]: [A.sub.m] [cross product] [A.sub.n] [??] [A.sub.m+n]).sub.m,n [greater than or equal to] 0] satisfying the following axioms:

(1) For i [greater than or equal to] 0, [A.sub.i] is a finite dimensional algebra with unit [1.sub.i], and [A.sub.0] [approximately equal to] K.

(2) The multiplication homomorphisms [[rho].sub.m,n] are injective and associative (in the sense that the external multiplication morphism they implement on the direct sum [[direct sum].sub.i [greater than or equal to] 0] [A.sub.i] is associative).

(3) For m, n [greater than or equal to] 0 the algebra [A.sub.m+n] is a two-sided projective [A.sub.m] [cross product] [A.sub.n]-module.

(4) A relation between the decomposition of [A.sub.m+n] as a left [A.sub.m] [cross product]] [A.sub.n]-module and as a right [A.sub.m] [cross product] [A.sub.n]-module holds.

(5) An analogue of Mackey's formula relating induction and restriction holds.

Bergeron and Li then define a tower of algebras as a family of algebras as stated above verifying the five previous axioms.

In order to explore a larger setting which includes our favorite examples, we drop axioms 4 and 5 and weaken axiom 3 into the following:

(3') for m, n [greater than or equal to] 0, the algebra [A.sub.m+n] is a right (resp. left) projective [A.sub.m] [cross product] [A.sub.n]-module.

Definition 2.2 A right (resp. left) tower of algebra A is a family [([A.sub.i]).sub.i [greater than or equal to] 0] of algebras as above satisfying axioms (1), (2) and (3').

For any field K of characteristic 0, the K-algebra KM of a monoid (M, x), is the K-algebra with basis [{[[epsilon].sub.m]}.sub.m [member of] M], and multiplication obtained by linearization of the product of M:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

A tower of monoids is a family of monoids [([M.sub.i]).sub.i [greater than or equal to] 0] together with a collection of morphisms such that [([KM.sub.i]).sub.i [greater than or equal to] 0] is a tower of algebras for the corresponding embedding.

We recall the definition of the Grothendieck groups [G.sub.0] and [K.sub.0] of an associative finite dimensional algebra F (see [CR90]). For a category F of finitely generated left F-modules, the Grothendieck group G(F) is the abelian group generated by symbols [M], one for every isomorphism class of modules M in F and relations [M] = [L] + [N] for any short exact sequence 0 [right arrow] L [right arrow] M [right arrow] N [right arrow] 0 in F. We let [G.sub.0](F) be the Grothendieck group of the category of finitely generated simple F-modules and [K.sub.0](F) the Grothendieck group of the category of finitely generated projective F-modules. More combinatorially, it is easy to prove that [G.sub.0](F) is the free Z-module with basis [{[[S.sub.i]]}.sub.i [member of] I], where [([S.sub.i]).sub.i [member of] I] is a complete set of non pairwise isomorphic simple F-modules. For an F-module M, we can decompose [M] = [[summation].sub.i [member of] I] [c.sub.i] [[S.sub.i]] where [c.sub.i] is the multiplicity of [S.sub.i] in M. Continuing the same way, the set {[Pi]}ie/ of projective covers of the simple modules form a basis of the Z-module [K.sub.0](F).

Let A be a tower of algebras. Axiom (1) ensures that the Grothendieck groups

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

are graded connected. Axioms (2) and (3) allows us to define induction and restriction functors on [G.sub.0] and [K.sub.0], endowing them with a multiplication and a comultiplication. For M and [A.sub.m]-module and N an [A.sub.n]-module, the product and coproduct of their classes [M] and [N] in [G.sub.0] (or in [K.sub.0]) are given respectively by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The two Grothendieck rings are closely related thanks to the natural pairing <,> defined on P [member of] [K.sub.0] ([A.sub.m]) and M [member of] [G.sub.0]([A.sub.n]) by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

In particular, for {[P.sub.1], ..., [P.sub.n]} a complete set of indecomposable projective modules and {[S.sub.1], ..., [S.sub.n]} their associated simple irreducible module, we have <[[P.sub.i]]>, [[S.sub.j]]> = [[delta].sub.i,j]. With the three axioms given above, [G.sub.0] and [K.sub.0] are dual graded free Z-modules with product and coproduct.

Induction on [K.sub.0] and restriction on [G.sub.0] are related thanks to Frobenius reciprocity.

Theorem 2.3 (Frobenius reciprocity) Ind is left adjoint for Res.

The right adjoint of Res is called coinduction and is noted Coind. We have an equality between Res and Coind for groups and this equality also holds in the semilattice case. However, these functors are not equal in the general case, for example for the tower of NDPF that we introduce in Section 6.

2.2 Categorification

We will use the definition of naive categorification as defined in [Sav14].

2.3 J-trivial monoids, semilattices, and their representation theory

We recall here some facts about J-trivial monoids and their representations. For details, see for example [Pin11] and [[DHS.sup.+]11] respectively. Let M be a monoid, and write E(M) for the set of idempotents of M. In the sequel, we always assume M to be finite. Define the J preorder [[less than or equal to].sub.J] on M by x [[less than or equal to].sub.J] y if x [member of] MyM. This preorder induces an equivalence relation, namely xJy if and only if MxM = MyM. The equivalence classes are called J-classes.

Definition 2.4 A monoid M is J-trivial if all its J-classes are of cardinality 1.

Equivalently, M is J-trivial if j is a partial order. In this case, we write [J.sub.<] (x) the set of all elements strictly smaller than x for the J-order. We define similarly the right preorder [[less than or equal to].sub.R] by x [[less than or equal to].sub.R] y if x [member of] yM. This preorder gives R-classes and we call R-trivial a monoid for which [[less than or equal to].sub.r] is a partial order. The symmetric definition on the left side leads to L-trivial monoids. A monoid is J-trivial if it is both L-trivial and R-trivial. For an element x [member of] M, we denote by [R.sub.<] (x) the set of all elements of M strictly smaller than x for the R-order. For a tower of monoids ([A.sub.i]) = ([KM.sub.i]) and x [member of] [M.sub.i], we will note [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] the subspace of [A.sub.i] generated by [R.sub.<](x).

The representation theory of J-trivial monoids is essentially independent of the ground field K. The simple modules admit an easy description. Namely, for x [member of] M, define [S.sub.x] = K (xM/[R.sub.<](x)). It's a right module of dimension 1 where, denoting the single basis element by ex, the action is given by [[epsilon].sub.x] x m = [[epsilon].sub.x] if [x.sub.m] = x and [[epsilon].sub.x] x m = 0 otherwise.

Theorem 2.5 Let M be J-trivial monoid. The set [([S.sub.e]).sub.e [member of] E{M)] is a complete set of pairwise non-isomorphic simple KM-modules.

We now turn to the description of the indecomposable projective modules. For x [member of] M, set:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

For e an idempotent, one can define the module [P.sub.e] = K(eM/{m [member of] M: lfix(m) [<.sub.J] (e)}). Its basis is indexed by the family {x: lfix(= e}.

Theorem 2.6 ([[DHS.sup.+]11], Corollary 3.22) Let M be a J-trivial monoid. The set (Pe)eeE(M) is a complete set of pairwise non-isomorphic indecomposable projective KM-modules.

The radical of the algebra of an J-trivial monoid viewed as a module on itself is given by its non idempotent elements. It is thus natural to consider the semisimple case, when all the elements of M are idempotent. It turns out that M is then necessarily commutative thanks to the following theorem.

Theorem 2.7 ([Pin11]) The class of idempotent (or equivalently semisimple) J-trivial monoids coincide with the class of finite semilattices (L, [disjunction]).

In particular, a good source of examples is to take one's favorite finite lattice, and consider the monoid given by its join (resp. its meet) operation, together with its smallest (resp. largest) element as identity.

3 Induction lemma

We now introduce our key lemma.

Lemma 3.1 Let B [subset or equal to] A two K-algebras, f [member of] B an idempotent and U [subset or equal to] fB a right B-modul[member of]. We have the following A-mod isomorphism:

[Ind.sup.A.sub.B](fB)/U [approximately equal to] (fA)/(UA).

4 Representation theory of towers of J-trivial monoids

4.1 General case

In the following section, we fix a tower of monoids [([M.sub.i]).sub.i [greater than or equal to] 0] with A = [([A.sub.i]).sub.i [greater than or equal to] 0] the associated tower of algebras. Thanks to J-triviality, the representation theory of such a monoid is combinatorial. In order to describe the general rules, we need to expand the previous definitions of rfix and lfix to tensorial algebras. For x [member of] [M.sub.m+n] set

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

and define similarly [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. We can therefore state the following proposition:

Proposition 4.1 Let [([A.sub.i]).sub.i [greater than or equal to] 0] = [([KM.sub.i]).sub.i [greater than or equal to] 0] be a tower of monoid algebras. Take x [member of] [M.sub.m+n], and let [S.sub.x] be the associated [A.sub.m+n]-simple module, then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. [S.sub.x] = [S.sub.e] where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Thanks to Frobenius Reciprocity (Theorem 2.3) we directly get the product rule in [K.sub.0].

Proposition 4.2 Let e be an idempotent of [M.sub.m] [cross product] [M.sub.n] and [P.sub.e] be the projective module associated to e. Then,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

We can now study how this lemma applies in the case of a tower of J -trivial monoids. Each simple module M can be interpreted as an element x of a graded component [A.sub.n] of the tower, and the action is characterized by the partial ordering. Indeed, [A.sub.n] acts by 1 on M for all elements {z [[greater than or equal to].sub.R] x} and by 0 otherwise. Given two simple modules [S.sub.f] and [S.sub.g] of [A.sub.m] and [A.sub.n], the tensor product [S.sub.f] [cross product] [S.sub.g] is a simple two sided ([A.sub.m] [cross product] [A.sub.n])-module. Thanks to lemma 3.1, the induced module on [A.sub.m+n] is the quotient K(f x g)[A.sub.m+n]/([R.sub.<] (f) x [R.sub.<] (g) [A.sub.m+n]).

Let [S.sub.e] and [S.sub.f] be two simple modules of respectively [A.sub.m] and [A.sub.n]. Let X(e,f) denote the subset of [M.sub.m+n] containing all elements in [[rho].sub.m,n]{e, 1) [[rho].sub.m,n] (1, f)[M.sub.m+n] which are not in [[rho].sub.m,n]{[R.sub.<] (e), 1) [[rho].sub.m,n] (1, [R.sub.<](f)). Namely, by identifying [M.sub.m] and [M.sub.n] with their copies embedded in [M.sub.m+n] we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The following theorem describes combinatorially the induction rule for simple modules:

Theorem 4.3 (Induction rule for J-trivial monoids) Let M = ([M.sub.i]) be a tower of J-trivial monoids and A = ([A.sub.i]) the related tower of algebras. With the above notations, the induction rule for two simple modules [S.sub.e] and [S.sub.f] is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Proof: Straightforward application of Lemma 3.1 on the construction of the simple modules given in Theorem 2.5.

4.2 Categorification of the pair of Hopf Algebras QSym/NCSF

We recover Krob-Thibon's Theorem [KT97] using Theorem 4.3. It is well known that the 0-Hecke algebra [H.sub.n] at q = 0 is the algebra of the 0-Hecke monoid [H.sub.n](0) which is J-trivial. The idempotents are naturally indexed by the subsets I of {1, ..., n - 1}, with lfix([[pi].sub.[sigma]]) and rfix([[pi].sub.[sigma]]) given respectively by the left and right descent sets [D.sub.L]([sigma]) and [D.sub.R]([sigma]) of [sigma].

Let us first recover the product rule in [G.sub.0]. Each simple module [S.sub.I] can be constructed as [[pi].sub.[sigma]][H.sub.n](0)/[R.sub.<]([[pi].sub.[sigma]]), where [sigma] is any permutation with left descent set I. Here we choose [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where [[sigma].sub.I] is the maximal element of the parabolic subgroup [G.sub.I].

Consider a simple ([H.sub.m] [cross product] [H.sub.n])-module [S.sub.I] [cross product] [S.sub.J]. It can be written as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Using Lemma 3.1, the induced module on [H.sub.m+n] is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Note that Q = {[[pi].sub.[mu]][[pi].sub.i][[pi].sub.v]: i [not member of] [Des.sub.R] [mu], i [not equal to] m, [[pi].sub.v] [member of] [[rho].sub.m,n]([H.sub.m](0) x [H.sub.n](0))}. Therefore,

Q[H.sub.m+n] = {[[pi].sub.[mu]][[pi].sub.i][[pi].sub.v]: i [not member of] [Des.sub.R] [mu], i [not equal to] m, [[pi].sub.v] [member of] [H.sub.m+n]}.

and it follows that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

It is well known that the permutations v with [Des.sub.R](v) [subset or equal to] {m} are the permutations appearing in the shuffle product [id.sub.m] [??] [id.sub.n]. At the level of descents we recover the shuffle product of NCSF.

For the coproduct in G0, we need to study the restrictions of each simple module [S.sub.I] of [H.sub.m+n] on [H.sub.m] [cross product] [H.sub.n]. In terms of descent sets, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] amounts to removing m from I and shifting the entries greater than m by -m; this is exactly the shifted deconcatenation rule of the fundamental basis of NCSF.

Altogether we proved that G0 is isomorphic to NCSF in the fundamental basis. By adjunction, we get the product in K0, then we use our knowledge of the pair QSym/NCSF and the Z-module duality to conclude.

4.3 Representation theory of towers of semilattices

For a tower of semilattices 0, each Li is semisimple. Then we have [G.sub.0](KL) = [K.sub.0](KL).

Because we combinatorially described the induction and restriction in [G.sub.0](A) for any algebra tower of J-trivial monoids, we have a complete combinatorial description of both Grothendieck rings of any tower of semilattices.

5 Partial categorification of FQSym, PBT, and NCSF

In the section, we assume that the reader is familiar with both Malvenuto-Reutenauer algebra FQSym ([MR95], [DHT02]) and the Loday-Ronco Planar Binary Tree Hopf algebra ([LR98]) and how it relates with FQSym ([HT09]).

5.1 The tower of permutohedron lattices

We first consider the tower of permutohedrons. Namely, for each n, take the left weak order <L on the n-th symmetric group [G.sub.n]. A potential definition for the weak order on permutation is that [sigma] [less than or equal to] [mu] if and only if inv([sigma]) [subset or equal to] inv([mu]). It is well known that it endows [G.sub.n] with a lattice structure, and we consider the semilattice [P.sub.n] = ([G.sub.n], [disjunction]), with the trivial representation as identity element. Remind that the J-order on [P.sub.n] is the reverse order of [<.sub.L]; the identity is the largest element.

Let [[rho].sub.m,n]: K[P.sub.m] [cross product] K[P.sub.n] [right arrow] K[P.sub.m+n] be the linear extension of the shifted concatenation on [P.sub.m] x [P.sub.n]. The morphism p is obviously injective. Thus we obtain a tower of semilattices KP = [[direct sum].sub.n [greater than or equal to] 0] K[P.sub.n]. It follows that inv([[rho].sub.m,n]{[sigma], [mu])) = inv([sigma]) [bar.[union]] inv([mu]) where [bar.[union]] is the shifted union.

We start by describing the product rule in [G.sub.0](P), that is the induction rule of simple modules. Let us fix a simple K([P.sub.m] [cross product] [P.sub.n])-module [S.sub.[sigma] [cross product] [mu]]. This simple module is the quotient

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

by definition of the product order. By Lemma 3.1, we have:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

This quotient is a subalgebra of K[R.sub.<]([sigma][bar.x] [mu]) and is quite easy to describe. The submonoid [R.sub.<]([sigma] [cross product] [mu]) [P.sub.m+n] is exactly the set of all permutations w [member of] [P.sub.m+n] such that inv(w) [subset] inv([sigma]) [bar.[union]] inv([mu]). Since [R.sub.<]([sigma] [bar.x] [mu]) consists of all permutations v such that inv(v) [subset or equal to] inv([sigma]) [bar.x] inv([mu]), we can state the following proposition:

Proposition 5.1 In the permutohedron tower, the induction rule for the simple modules is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

This gives the following product rule in [G.sub.0](P):

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Example 5.2 [[S.sub.(21)]] x [[S.sub.(231)]] = [[S.sub.(21453)]] + [[S.sub.(31452)]] + [[S.sub.(32451)]] + [[S.sub.(41352)]] + [[S.sub.(42351)]] + [[S.sub.(52341)]] + [[S.sub.(43251)]] + [[S.sub.(51342)]] + [[S.sub.(53241)]] + [[S.sub.(54231)]].

Using Frobenius formula, we directly obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Example 5.3 [DELTA]([[S.sub.(2413)]]) = [1] [cross product] [[S.sub.(2413)]] + [[S.sub.1]] [cross product] [[S.sub.(312)]] + [[S.sub.(12)]] [cross product] [[S.sub.(12)]] + [[S.sub.(312)]] [cross product] [[S.sub.1]] + [[S.sub.(2413)]] [cross product] [1].

Corollary 5.4 The map [[S.sub.[sigma]]] [right arrow] [G.sub.[sigma]] is an algebra isomorphism between [G.sub.0](V) and FQSym. The map [[S.sub.[sigma]]] [right arrow] [F.sub.[sigma]] is a coalgebra isomorphism between [G.sub.0](V) and FQSym.

Each [F.sub.[sigma]] or [G.sub.[sigma]] induced a FQSym-module morphism by left-multiplication. We obtain a categorification of the algebra (FQSym, [G.sub.[sigma]]) and a categorification of the coalgebra (FQSym, [F.sub.[sigma]]).

Note that the product and the coproduct are not compatible as bialgebras, so in particular we did not categorify FQSym as an auto-dual Hopf algebra.

5.2 The tower of Tamari lattices

We now turn to the tower of the Tamari lattice. The Tamari lattice is the lattice of binary trees ordered by tree rotations. We note [T.sub.n] the Tamari lattice of binary trees with n edges; [T.sub.n] has cardinality [C.sub.n] the nth Catalan number. In this paper, we will note the elements of the Tamari lattice as 132-avoiding permutations.

We construct a tower of semilattices by the embedding *: [T.sub.m] x [T.sub.n] [??] [T.sub.m+n] which consist in taking the Sylvester class of the shifted concatenation.

Example 5.5 (312) * (21) = (53214).

The product and the coproduct in the Grothendieck rings of KT can be computed from our previous construction on FQSym. Therefore, the maps [[T.sub.[sigma]]] [right arrow] [P.sub.[sigma]] and [[T.sub.[sigma]]] [right arrow] [Q.sub.[sigma]] are respectively algebra and coalgebra isomorphisms from [G.sub.0](T) to PBT making both diagrams of the definition of naive categorification commute.

Once again, we constructed categorifications of (PBT, [P.sub.T]) and (PBT, [Q.sub.T]). But we do not get a full Hopf categorification of the pair (PBT, [PBT.sup.*]).

5.3 The tower of Boolean lattices

Finally, let [B.sub.n] be the Boolean lattice of subsets of [1, n]. We write the elements of [B.sub.n] as binary words of size n. The concatenation embedding is an injective morphism making a tower B = [[direct sum].sub.m [greater than or equal to] 0] [B.sub.n] of semilattices. The product in [G.sub.0](B) easily follows from the remark [R.sub.<](u).

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

By duality, or using that [B.sub.n] is the semisimple quotient of [H.sub.n](0), the coalgebra structure on [G.sub.0](B) is isomorphic to QSym on the fundamental basis:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Unsurprisingly, the product and coproduct are again not compatible.

6 Non Decreasing Parking Functions

Definition 6.1 For n [greater than or equal to] 1, let [NDPF.sub.n] be the monoid of the non decreasing and regressive functions from [1, n] onto itself, endowed with the composition product. Denote a function f: i [??] [a.sub.i] [member of] NDPF, by the sequence ([a.sub.1], [a.sub.2], ..., [a.sub.n]); it satisfies 1 = [a.sub.1] [less than or equal to] [a.sub.2] [less than or equal to] ... [less than or equal to] [a.sub.n] and [a.sub.i] [less than or equal to] i.

This monoid and its representation theory, were studied in [HT09, [DHS.sup.+]11]. It's cardinality is the n-th Catalan number, and it is minimally generated by the idempotents n = (1, 2, ..., i, i, i + 2, ..., n - 1) for i [member of] [1, n - 1].

The exterior product [[rho].sub.m,n]: ([a.sub.1], ..., [a.sub.m]) x ([b.sub.1], ..., [b.sub.n]) [right arrow] ([a.sub.1], ..., [a.sub.m], [b.sub.1] + m, ..., [b.sub.m] + n) defines an associative and injective embedding from [NDPF.sub.m] [cross product] [NDPF.sub.n] to [NDPF.sub.m+n]. Thus we note NDPF = [[direct sum].sub.n [greater than or equal to] 0] [NDPF.sub.n], and the tower KNDPF satisfy Axioms (1) and (2). Verifying the third axiom is more tricky.

Proposition 6.2 [NDPF.sub.m+n] is a left projective ([NDPF.sub.m] [cross product] [NDPF.sub.n])-module.

Proof: We construct an explicit decomposition of [NDPF.sub.m+n] as [NDPF.sub.m] [cross product] [NDPF.sub.n]-module, and prove bijectively that each piece is isomorphic to a projective [NDPF.sub.m] [direct sum] [NDPF.sub.n] module.

Proposition 6.3 ([[DHS.sup.+]11]) The monoid [NDPF.sub.n] is J-trivial for all n. In particular its simple modules are all one dimensional.

The irreducible left [KNDPF.sub.n]-modules are thus entirely characterized by the action of the idempotent generators of K[NDPF.sub.n]. The eigenvalues of S on [[pi].sub.i] is 0 or 1 so we have [2.sup.n-1] simple K[NDPF.sub.n]-modules indexed by compositions. From now on, we will identify a simple [NDPF.sub.n]-module by the sequence ([b.sub.1], ..., [b.sub.n]) of his ordered eigenvalues on the generators ([[pi].sub.i]). We will note () = ([1.sup.0]) the unique irreducible [NDPF.sub.1]-module. Note that an irreducible [NDPF.sub.n]-module is described by n - 1 eigenvalues.

Proposition 6.4 The J-order on E([NDPF.sub.n]) is the Boolean lattice of [2.sup.n] elements.

The product in [K.sub.0](NDPF) is quite general thanks to [[DHS.sup.+]11]. We again use Lemma 3.1.

Thanks to Theorem 2.6 we can explicit the product in [K.sub.0](NDPF). Let [e.sub.I] and [e.sub.J] be two idempotents in respectively [NDPF.sub.m] and [NDPF.sub.n] indexed with compositions I of m - 1 and J of n - 1. We note [P.sub.I] = NDPFel the projective module associated with Se. By applying Lemma 3.1 we have:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

By Theorem 2.6 the projective module we obtain is:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

We deduce that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. We just proved:

Proposition 6.5 The map [K.sub.0](NDPF) [right arrow] NCSF defined by [[P.sub.I]] [right arrow] [R.sub.I] is an algebra isomorphism.

The product in [G.sub.0](NDPF) is quite tedious to write. To avoid a straightforward but technical proof, we use our knowledge of the algebra structure of [K.sub.0](NDPF), and take advantage of the fact that the Cartan operator C: [K.sub.0](NDPF) [right arrow] [G.sub.0](NDPF) is an isomorphism in our case. The Cartan operator is the Z-module morphism defined by the Cartan matrix. More precisely, for P a projective module, C[P] = [[summation].sub.i][c.sub.i][[S.sub.i]] where [c.sub.i] = dim(hom([P.sub.i], P)); that is C([P]) gives the composition factors of P, with multiplicities. Thanks to Theorem 2.6, it admits an explicit description for J-trivial monoids: [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Lemma 6.6 For k [greater than or equal to] 0 and l [greater than or equal to] 0 we have:

[([1.sup.k])][([0.sup.l])] = {[([c.sub.1], [c.sub.2], ..., [c.sub.k+l+1])]: [summation over (i)] [c.sub.i] [member of] {k, k + 1}}.

Theorem 6.7 Let [S.sub.a] = ([a.sub.1], [a.sub.2], ..., [a.sub.i], [1.sup.k]) [member of] [G.sub.0]([NDPF.sub.m]) and [S.sub.b] = ([0.sup.l], [b.sub.j], [b.sub.j+1], ..., [b.sub.n-1]) [member of] [G.sub.0]([NDPF.sub.n]), then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Theorem 6.8 The algebra G^NDPF is the free graded algebra with generators (), (0), (00), ....

Acknowledgements

The author would like to thank Florent Hivert and Nicolas M. Thiery for enlightening discussions and advise about this work. The author also thanks the anonymous referees for their excellent suggestions and remarks on the first draft of the current article. This research was driven by computer exploration using the open-source mathematical software Sage [Tea13] and its algebraic combinatorics features developed by the Sage-Combinat community [SCc08]

References

[BL09] Nantel Bergeron and Huilan Li. Algebraic structures on Grothendieck groups of a tower of algebras. Journal of Algebra, 321(8):2068-2084, 2009.

[BLL12] Nantel Bergeron, Thomas Lam, and Huilan Li. Combinatorial Hopf algebras and towers of algebras-dimension, quantization and functorality. Algebras and representation theory, 15(4):675-696, 2012.

[CR90] C.W. Curtis and I. Reiner. Methods of Representation Theory. Number vol. 1 in Methods of Representation Theory. Wiley, 1990.

[DHS+11] T. Denton, F. Hivert, A. Schilling, N.M. Thiery, et al. On the representation theory of finite J-trivial monoids. Seminaire Lotharingien de Combinatoire, 64:44, 2011.

[DHT02] Gerard Duchamp, Florent Hivert, and Jean-Yves Thibon. Noncommutative symmetric functions vi: free quasi-symmetric functions and related algebras. International Journal of Algebra and Computation, 12(05):671-717, 2002.

[Gei77] Ladnor Geissinger. Hopf algebras of symmetric functions and class functions. In Combinatoire et representation du groupe symetrique, pages 168-181. Springer, 1977.

[HNT05] Florent Hivert, J-C Novelli, and J-Y Thibon. The algebra of binary search trees. Theoretical Computer Science, 339(1):129-165, 2005.

[HNT06] Florent Hivert, Jean-Christophe Novelli, and Jean-Yves Thibon. Yang-Baxter bases of 0-Hecke algebras and representation theory of 0-Ariki-Koike-Shoji algebras. Advances in Mathematics, 205(2):504-548, 2006.

[HT09] Florent Hivert and Nicolas M. Thiery. The Hecke group algebra of a Coxeter group and its representation theory. J. Algebra, 321(8):2230-2258, 2009. arXiv:0711.1561.

[Kho99] Mikhail Khovanov. Nilcoxeter algebras categorify the Weyl algebra. arXiv:math/9906166, 1999.

[KT97] Daniel Krob and Jean-Yves Thibon. Noncommutative symmetric functions iv: Quantum linear groups and Hecke algebras at q= 0. Journal of Algebraic Combinatorics, 6(4):339-376, 1997.

[LR98] Jean-Louis Loday and Maria O Ronco. Hopf algebra of the planar binary trees. Advances in Mathematics, 139(2):293-309, 1998.

[MR95] Clauda Malvenuto and Christophe Reutenauer. Duality between quasi-symmetrical functions and the solomon descent algebra. Journal of Algebra, 177(3):967-982, 1995.

[Pin11] Jean-Eric Pin. Mathematical foundations of automata theory. Lecture notes, 2011.

[Sav14] Alistair Savage. Introduction to categorification. arXiv:1401.6037, 2014.

[SCc08] The Sage-Combinat community. Sage-Combinat: enhancing Sage as a toolbox for computer exploration in algebraic combinatorics, 2008. http://combinat.sagemath.org.

[SY13] Alistair Savage and Oded Yacobi. Categorification and Heisenberg doubles arising from towers of algebras. arXiv:1309.2513, 2013.

[Tea13] The Sage Team. Sage Mathematics Software (Version 5.12), 2013. http://www.sagemath.org.

Aladin Virmaux *

Laboratoire de Recherche en Informatique, Orsay, France

* Email: aladin.virmaux@lri.fr.

Printer friendly Cite/link Email Feedback | |

Author: | Virmaux, Aladin |
---|---|

Publication: | DMTCS Proceedings |

Article Type: | Report |

Date: | Jan 1, 2014 |

Words: | 5787 |

Previous Article: | Expanding Hall-Littlewood and related polynomials as sums over Yamanouchi words. |

Next Article: | The order of birational rowmotion. |

Topics: |