Combinatoire autour des groupes de permutations généralisées

Combinatoire autour des groupes de permutations généralisées Riccardo Biagioli To cite this version: Riccardo Biagioli. Combinatoire autour des groupes de permutations généralisées . Combinatorics [math.CO]. Université Claude Bernard Lyon 1, 2015. <tel-01277661> HAL Id: tel-01277661 https://tel.archives-ouvertes.fr/tel-01277661 Submitted on 23 Feb 2016 HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers. L’archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d’enseignement et de recherche français ou étrangers, des laboratoires publics ou privés. Institut Camille Jordan UMR 5208 du CNRS Combinatoire autour des groupes de permutations généralisées Riccardo BIAGIOLI Habilitation à Diriger des Recherches Université Claude Bernard Lyon 1 École doctorale InfoMath, ED 512 Spécialité : Mathématiques N. d’ordre 48–2015 Combinatoire autour des groupes de permutations généralisées Habilitation à Diriger des Recherches Soutenue publiquement le 25 novembre 2015 par Riccardo BIAGIOLI devant le Jury composé de : Mme. Mireille BOUSQUET-MÉLOU Directrice de Recherche au CNRS M. Francesco BRENTI Professeur à l’Université de Roma Tor Vergata M. Christian KRATTENTHALER Professeur à l’Université de Vienne (Président) M. Jean-Christophe NOVELLI Professeur à l’Université Paris-Est M. Yuval ROICHMAN Professeur à l’Université Bar-Ilan M. Jiang ZENG Professeur à l’Université Lyon 1 après avis des rapporteurs : M. François BERGERON M. Jean-Christophe NOVELLI M. Yuval ROICHMAN Professeur à l’Université du Québec à Montréal Professeur à l’Université Paris-Est Professeur à l’Université de Bar-Ilan Contents Remerciements iii Introduction v 1 Group actions and statistics 1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.1 Reflection group actions . . . . . . . . . . . . . . . . . . . 1.1.2 Diagonal and tensorial context . . . . . . . . . . . . . . . 1.1.3 Permutation statistics . . . . . . . . . . . . . . . . . . . . 1.1.4 Combinatorial interpretation of G(r, p, n) . . . . . . . . . 1.2 Colored-Descent representations of G(r, p, n). . . . . . . . . . . . 1.2.1 Colored Descent Basis . . . . . . . . . . . . . . . . . . . . 1.2.2 Colored-descent representations of G(r, p, n) . . . . . . . . 1.2.3 Carlitz identity . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Tensorial square of the Hyperoctahedral group Coinvariant Space 1.3.1 The trivial component of C[x, y]Bn ⇥Bn . . . . . . . . . . . 1.3.2 The alternating component of C[x, y]Bn ⇥Bn . . . . . . . . 1.4 Generalizations to other permutation groups . . . . . . . . . . . . 1.4.1 Generalizations to type B , type D , and wreath products 1.4.2 Projective reflection groups . . . . . . . . . . . . . . . . . 1.4.3 One-dimensional characters and flag major index . . . . . 1.4.4 Carlitz identities . . . . . . . . . . . . . . . . . . . . . . . 1.4.5 Multivariate generating functions . . . . . . . . . . . . . . 2 Fully commutative elements 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Fully commutative elements, heaps and walks . . . . . 2.3 Alternating heaps and walks . . . . . . . . . . . . . . . e . . . . . . . . . . . . . . . . . . . . . 2.4 Types A and A 2.4.1 Type A . . . . . . . . . . . . . . . . . . . . . . e . . . . . . . . . . . . . . . . . . . . . . 2.4.2 Type A 2.5 Closed formulas for the generating functions . . . . . . 2.6 Other classical affine and exceptional types . . . . . . 2.7 Involutions . . . . . . . . . . . . . . . . . . . . . . . . 2.7.1 Bijective encoding of alternating self-dual heaps 2.7.2 Enumeration with respect to the major index . i . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1 2 3 4 6 6 7 8 10 11 11 15 16 17 18 19 21 22 . . . . . . . . . . . 25 25 26 27 28 29 30 32 34 36 36 37 2.8 Applications and further questions . . . . . 2.8.1 Growth of Temperley–Lieb algebras e . . 2.8.2 Cells for FC elements in type A 2.8.3 Further questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Depth in classical Coxeter groups 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Type B . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Type D . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Coincidences of depth, length, and absolute length . . . . 3.4.1 Coincidence of length and depth . . . . . . . . . . 3.4.2 Coincidence of depth, length and reflection length . 3.5 Open questions and further remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Schur-positive symmetric functions 4.1 A conjecture of Fomin, Fulton, Li, and Poon . . . . . . . . . . 4.2 Combinatorial properties of the ⇤-operation and implications 4.3 Main results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4 Multiplicity-free cases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 39 40 42 . . . . . . . 45 45 47 48 49 49 50 51 . . . . 55 55 57 60 61 Remerciements Tout d’abord j’exprime ma gratitude envers Francesco Brenti, qui m’a fait découvrir le monde palpitant de la recherche. Je le remercie pour tous ses conseils toujours judicieux. Je suis heureux de le compter parmi les membres du jury. Merci à François Bergeron d’avoir accepté d’être rapporteur de ce mémoire. Source perpétuelle d’idées, avec son enthousiasme communicatif, il m’a fait découvrir de nombreux sujets intéressants. J’espère que nous aurons encore l’occasion de collaborer. Merci à Jean-Christophe Novelli d’être rapporteur et membre du jury. Il a été l’un des premiers à m’encourager à passer mon habilitation. J’espère qu’on aura bientôt l’opportunité de travailler ensemble. Les travaux de Yuval Roichman ont été et sont encore une grande source d’inspiration pour mes recherches. Ça me fait vraiment plaisir de l’avoir comme rapporteur et membre du jury. Je suis honoré de compter parmi le membres du jury Mireille Bousquet-Mélou. Je suis très content de notre récente collaboration et la remercie pour les belles formules qu’elle m’a fait découvrir. Merci à Christian Krattenthaler, qui a accepté de participer au jury. C’est aussi grâce à lui que je suis finalement venu à l’Institut Camille Jordan. Je lui en suis très reconnaissant. Merci à Jiang Zeng pour m’avoir accueilli à Lyon avec la plus grande disponibilité, et pour tout ce qu’il m’a fait connaître lors de nos nombreux échanges et collaborations. Je souhaite exprimer toute ma gratitude envers mes collaborateurs et amis Fabrizio Caselli, Frédéric Jouhet et Philippe Nadeau. Nous avons énormément travaillé ensemble pendant ces dernières années. J’ai beaucoup appris de nos discussions et une partie non négligeable de ce mémoire est aussi la leur. Un grand merci à mes autres collaborateurs Eli Bagno, Frédéric Chapoton, Sara Faridi, Mercedes Rosas et Alex Woo. Je remercie également tous mes collègues de l’Institut Camille Jordan, qui forment une communauté très accueillante et stimulante. En particulier, je pense à Rouchdi Bahloul, Lorenzo Brandolese, Philippe Caldero, Alessandra Frabetti, et Elie Mosaki pour les agréables moments passés ensemble. Le support de ma famille ne m’a jamais fait défaut pendant toutes ces années. Mes parents, bien que loin physiquement, sont toujours présents et ils représentent des piliers très importants sur qui je peux compter. Je n’aurais pas pu accomplir ce travail sans le soutien et la sérénité que me donne ma femme Simona et l’énergie débordante et la joie de vivre que me transmettent chaque jour mes enfants Matilde et Lorenzo. iii iv REMERCIEMENTS Introduction Ce mémoire constitue un travail de synthèse de mes travaux dans le domaine de la combinatoire énumérative et algébrique autour des groupes de permutations généralisées : ce terme désignera ici les groupes de Coxeter classiques et certains groupes de réflexions complexes. La plupart des résultats présentés dans ce mémoire peuvent être classifiés en deux catégories. Il s’agit soit de résultats algébriques dont nous donnons des descriptions combinatoires explicites, soit de résultats énumératifs qui ont une signification dans un contexte algébrique particulier. Pour faire cela, on s’appuie souvent sur des fonctions particulières à valeurs entières positives qui sont usuellement appelées statistiques de permutations. Plus précisément, la première partie est consacrée à la généralisation de certains résultats connus pour le groupe symétrique à d’autres groupes de permutations. De nombreux collègues se sont intéressés à ce sujet et dans la littérature plus ou moins récente on trouve une abondance de papiers de cette nature. Le premier but de nos recherches sur ce thème était d’uniformiser tous ces résultats disséminés, en trouvant un contexte unificateur. Pour cela une idée naturelle est l’utilisation des groupes de réflexions complexes comme cadre commun. Un groupe de réflexions complexes sur un espace vectoriel V est un groupe engendré par des pseudo-réflexions, c’est-à-dire des transformations linéaires de V d’ordre fini qui stabilisent un hyperplan. Il est connu que un groupe W est engendré par des pseudo-réflexions si et seulement si l’algèbre des invariants C[V ]W est un anneau polynomial. Ces groupes ont été classifiés par Chevalley : il y a une seule famille infinie et exactement 34 groupes de réflexions complexes exceptionnels. L’unique famille infinie est notée G(r, p, n) où r, p, n sont des entiers positifs et p | r . Les éléments de G(r, p, n) ont une jolie interprétation combinatoire en termes de permutations colorées, c’est-à-dire que ces éléments peuvent être représentés comme des permutations, où chaque lettre est associée à une couleur. Cela permet d’utiliser des techniques combinatoires pour travailler sur ces groupes. Les groupes de Weyl classiques apparaissent tous comme des cas particuliers de cette famille: le groupe symétrique Sn est isomorphe à G(1, 1, n), le groupe hyperoctahédral Bn à G(2, 1, n) et son sous groupe Dn à G(2, 2, n). Le processus généralisateur mentionné ci-dessus s’est accéléré suite au papier fondamental [1] de Adin et Roichman, dans lequel une extension de l’indice majeur aux groupes G(r, 1, n) a été introduite. Cette statistique est appelée flag major index. Dans le Chapitre 1, nous donnons une extension du flag major index aux groupes de réflexions complexes G(r, p, n). Ceci nous permet de définir une nouvelle base explicite pour l’algèbre coinvariante de type G(r, p, n), de laquelle découle une nouvelle famille de représentations du groupe G(r, p, n). Nous donnons la décomposition de ces représentations en composantes irréductibles à l’aide d’une famille de tableaux standards dits orbitaux, et d’une nouvelle statistique sur ces tableaux analogue au flag major index. Par ailleurs dans le cas du groupe Bn , nous étudions les composantes isotypiques de l’algèbre coinvariante du groupe Bn ⇥ Bn considéré comme un Bn -module, c’est-à-dire que le groupe Bn agit de manière diagonale sur l’anneau des polynômes en deux jeux de variables C[x1 , . . . , xn , y1 , . . . , yn ]. Nous déterminons une base explicite pour la composante triviale à l’aide de nouveaux objets combinatoires appelés diagrammes compacts. v vi INTRODUCTION Le chapitre se termine par une liste de formules de séries génératrices multivariées de statistiques comme l’indice majeur, la longueur, le nombre de descentes, etc., qui généralisent aux groupes de Coxeter de types B , D , et aux produits en couronne G(r, 1, n) des résultats connus en type A. Le passage au groupe de Coxeter de type D et aux groupes de réflexions complexes G(r, p, n) est en général plus compliqué, et donne souvent des fonctions génératrices peu satisfaisantes. En partant d’une série génératrice particulière en type D , Caselli [36] est parvenu à simplifier son expression en introduisant une nouvelle famille de groupes, appelés groupes de réflexions projectifs. Parmi ces groupes, une sous famille notée G(r, p, q, n) se spécialise pour q = 1 aux groupes de réflexions complexes G(r, p, n). Ceci donne un cadre encore plus général dans lequel les fonctions génératrices traitées précédemment peuvent être étudiées. Nous présentons quelques-uns de nos résultats dans ce contexte plus large. Dans le deuxième chapitre nous analysons une famille particulière d’éléments dans les groupes de Coxeter, appelés éléments pleinement commutatifs. Un élément w est pleinement commutatif (PC) si étant données deux expressions réduites pour w , il existe toujours une suite de commutations de générateurs adjacents pour passer de l’une à l’autre. Ces éléments sont importants car ils indexent une base de l’algèbre de Temperley–Lieb généralisée; ils interviennent également en connexion avec les représentations de l’algèbre de Hecke grâce les polynômes de Kazhdan–Lusztig. Les éléments PC ont été largement étudiés par Stembridge qui a classifié les groupes de Coxeter en ayant un nombre fini. Il a aussi compté le nombre d’éléments PC dans chacun de ces cas, et il en a donné plusieurs interprétations combinatoires. Par exemple, on sait que les permutations PC dans le groupe symétrique sont celles qui évitent le motif 321. Motivés par l’étude d’une conjecture récente de Hanusa et Jones, nous nous sommes intéressés à ce domaine. Ces deux auteurs que quand W est le groupe P ont montré `( ) est périodique à partir d’un affine de type à la série génératrice W P C (q) = q 2W P C certain rang, qu’ils n’arrivèrent à déterminer que conjecturalement. Nos contributions principales dans ce domaine sont les suivantes. Nous donnons tout d’abord une classification complète des éléments PC pour tous les groupes de Coxeter de types finis et affines. Nos caractérisations sont données en termes d’empilements de Viennot. Cette approche est totalement différente de celle de Hanusa et Jones, et nous permet de démontrer que la propriété de périodicité de la série W P C (q) est vraie pour tout groupe W affine, et pas seulement en type Ã. Ceci nous permet au passage de donner une preuve plus simple du résultat de Hanusa et Jones et de prouver leur conjecture sur le début de périodicité. Notre outil principal est donné par l’interprétation de certains de nos empilements (correspondant à une sous famille d’éléments PC) en termes de chemins de type Motzkin dans le plan. En décomposant de manière classique de tels chemins, nous obtenons des expressions pour les séries W P C (q) desquelles découle la périodicité. Ces formules ne sont pas très explicites mais permettent néanmoins de calculer les coefficients de W P C (q) grâce à des récurrences et à des équations fonctionnelles. Par ailleurs, dans un travail en cours, nous montrons qu’il existe des jolies formules (en terme de q -analogues de séries de type Bessel) pour les séries W P C (q), dans tous les cas finis et affines. Nous examinons ensuite parmi les éléments PC ceux qui sont involutifs. La propriété de périodicité de la série correspondante est préservée dans les cas affines. De plus, toujours à l’aide de nos interprétations en termes de chemins, nous pouvons aussi énumérer ces involutions PC par rapport à un certain indice majeur dans les groupes finis de types A, B et D , généralisant ainsi un résultat récent de Barnabei et al. La série W P C (q) a une signification algébrique : elle peut être interprétée comme la série de Hilbert de l’algèbre de nil Temperley–Lieb associée au groupe W . Nous terminons ce chapitre avec une application de nos caractérisations des éléments PC en termes d’empilements aux algèbres de Temperley–Lieb de type Ã, et avec une liste de questions ouvertes sur ce domaine. vii Dans le Chapitre 3, nous étudions une nouvelle statistique définie récemment par Petersen et Tenner sur les groupes de Coxeter, appelée profondeur et notée dp. Il ne s’agit pas de la fonction profondeur classique définie sur l’ensemble des racines positives d’un groupe de Coxeter, mais les deux notions sont très liées. La profondeur d’un élément w 2 W est égale au coût minimal d’un chemin valué partant de l’identité et finissant à w sur le graphe de Bruhat, où les arêtes (qui sont étiquetées par des réflexions) ont un poids donné par la fonction profondeur de la racine positive correspondante. Petersen et Tenner ont montré que la profondeur est toujours bornée par la longueur absolue ab et la longueur `, plus précisément on a ab(w)  dp(w)  `(w) pour tout w 2 W . Nous donnons des formules closes explicites pour la profondeur dans les groupes de Coxeter de types B et D . Nos algorithmes montrent que même dans le cas du type A, on peut toujours obtenir une factorisation w = t1 · · · tk qui réalise la profondeur de w et qui est réduite. Ceci nous permet de dire que le chemin valué qui donne la profondeur est toujours un chemin orienté de façon croissante dans le graphe de Bruhat. L’autre résultat principal est la classification des éléments w tels que dp(w) = `(w). Nous montrons que dans les groupes de Coxeter où la profondeur peut toujours être réalisée par une factorisation réduite, ces éléments sont ceux dont les expressions réduites évitent tous les motifs de tresse sts, où s et t sont des réflexions simples. Nous montrons aussi que les éléments pour lesquels dp(w) = ab(w) sont les éléments dit booléens, c’est-à-dire ceux dont les expressions réduites contiennent au plus une fois chaque générateur. Ce chapitre se termine par une section donnant quelques pistes pour des recherches futures sur ce thème. Dans le chapitre final, nous analysons une conjecture intéressante de Fomin-Fulton-LiPoon sur la Schur-positivité d’une différence de produits de fonctions de Schur. Nous rappelons qu’une fonction symétrique est Schur-positive si son développement linéaire dans la base des fonctions de Schur a des coefficients qui sont tous positifs ou nuls. Cette conjecture provient de l’étude de certaines inégalités entre valeurs propres de matrices complexes, liées au célèbre problème de Horn. Plus précisément, les auteurs ci-dessus définissent une application, appelée ⇤, qui associe une paire ordonnée de partitions d’entiers ( , ⇢) à une autre paire de partitions (µ, ⌫) avec le même nombre total de parts, et ils conjecturent que la fonction s s⇢ sµ s⌫ est Schur-positive. On sait bien que grâce à la caractéristique de Frobenius toute fonction Schur-positive correspond à une représentation du groupe symétrique, c’est pourquoi de telles fonctions sont particulièrement importantes. Cette conjecture semble être très compliquée à aborder y compris via la théorie des représentations; la description de l’application ⇤ est elle-même assez laborieuse. Le premier résultat que nous avons obtenu est une description récursive plus accessible de l’application ⇤, nous permettant de prouver plusieurs cas particuliers de la conjecture. P ✓ Bien plus récemment, nous nous sommes intéressés au cas où le produit sµ s⌫ = ✓ cµ⌫ s✓ est sans multiplicité, c’est-à-dire que les coefficients de Littlewood–Richardson c✓µ⌫ qui interviennent dans son développement sont tous égaux à 0 ou 1. Les couples de partitions (µ, ⌫) donnant des produits sans multiplicité ont été classifiés par Stembridge et regroupés en quatre familles. Dans cette situation, montrer la conjecture revient à prouver que c✓ ⇢ > 0, pour toute ✓ telle que s✓ apparaît dans le développement de sµ s⌫ . En utilisant une interprétation classique des coefficients de Littlewood-Richardson nous arrivons à confirmer la conjecture pour trois des quatre familles précédentes. viii INTRODUCTION Chapter 1 Groups actions and statistics The relations between the combinatorics and the representation theory of the symmetric group are many and find new connections is a fascinating task from both a combinatorial and algebraic point of view. The problem of generalizing these type of results to all reflection groups has been approached in many ways and by many people. Besides several results that hold in the fully generality of reflection groups, many others have been obtained only for some special families. In this chapter we present our contribution in this area, that concerns mostly the families of classical Weyl groups, wreath products, complex reflection groups, and projective reflection groups. We present either algebraic results for which we give explicit combinatorial descriptions, or enumerative results, like computations of specific generating functions, that can be interpreted in an algebraic context. Both share a similar property, namely they are obtained with the help of some particular integers valued functions, usually called permutation statistics. We start by collecting some definitions, and known results that we will use, and by setting up some notation. 1.1 Introduction Let V be a real or complex vector space of dimension n. A reflection is a linear transformation of V of finite order, which fixes a hyperplane in V pointwise. A finite reflection group on V is a finite subgroup W  GL(V ) generated by reflections. If V is a R-vector space then all reflections have order 2, and from here the name reflection. If K = C (or R), then W is a finite complex (or real) reflection group The finite real reflection groups are the finite Coxeter groups. They are classified and the Dynkin diagrams of the irreducible families are the following t1 4 s1 s2 An sn 1 t s1 s2 1 m 4 I2 (m) F4 E6 sn Bn t2 5 H3 E7 s1 s2 1 Dn+1 sn 1 5 H4 E8 Figure 1.1: Dynkin diagrams for all irreducible finite types. To any group W < GL(V ) of complex matrices corresponds a natural action on the 1 2 CHAPTER 1. GROUP ACTIONS AND STATISTICS polynomial ring C[x] = C[x1 , . . . , xn ]. As usual we denote (1.1) w · p(x) := p(w · x), this action and by C[x]W := { p(x) | w · p(x) = p(x)} the ring of invariants. Shephard–Todd and Chevalley proved that W is a complex reflection group if and only if the ring of invariants C[x]W is a polynomial ring. They classified the irreducible finite complex reflection groups: there is a single infinite family of groups and exactly 34 other exceptional complex reflection groups. The infinite family G(r, p, n) where r, p, n are positive integers numbers with p|r , consists of the groups of n ⇥ n matrices such that 1. the entries are either 0 or rth roots of unity; 2. there is exactly one nonzero entry in each row and each column; 3. the (r/p)th power of the product of the nonzero entries is 1. As we will see in this chapter the groups of the form G(r, p, n) behave like much as Coxeter groups from both an algebraic and a combinatorial point of view. They have presentations in terms of generators and relations that can be visualized by Dynkin type diagrams (see e.g., [34]). Since the generators are not necessary involutions, the order of any generator is usually depicted inside the corresponding node, below an example. 2 d 2 2 2 2 Figure 1.2: A Dynkin-type diagram of G(r, p, n), d = r/p. 1.1.1 Reflection group actions The space C[x] is graded by degree so for each subspace S of C[x] it makes sense to consider the Hilbert series of S : X Hq (S) := dim(Sd ) q d , m 0 which condenses in a efficient and compact form the information for the dimensions of each homogeneous component Sd . To illustrate, it is not hard to show that the Hilbert series of C[x] is simply 1 Hq (C[x]) = . (1.2) (1 q)n We will be particularly interested in invariant subspaces S of C[x], namely those for which w · S ✓ S , for all w in W . Clearly whenever S is homogeneous, on top of being invariant, then each of these homogeneous components, Sd , is also a W -invariant subspace. We have already introduced an important example of homogeneous invariant subspace, the set C[x]W of invariant polynomials. Here, not only the subspace C[x]W is invariant, but all of its elements are. As stated before, whenever W is a complex reflection group, C[x]W is in fact a subring of C[x] for which one can find generator sets of n homogeneous algebraically independent elements, say f1 , . . . , fn , whose respective degrees will be denoted d1 , . . . , dn . Although the fi ’s are not uniquely characterized, the di ’s are basic numerical invariants of the group, called the degrees of W . Any n-set {f1 , . . . , fn } of invariants with these properties 1.1. INTRODUCTION 3 is called a set of basic invariants for W . It follows that the Hilbert series of C[x]W takes the form: n Y 1 Hq (C[x]W ) = . (1.3) 1 q di i=1 Now, let IW be the ideal of C[x] generated by constant term free elements of C[x]W . The coinvariant space of W is defined to be (1.4) C[x]W := C[x]/IW . Observe that, since IW is an homogeneous subspace of C[x], it follows that the ring C[x]W is naturally graded by degree. Moreover, IW being W -invariant, the group W acts naturally on C[x]W . In fact, it can be shown that C[x]W is actually isomorphic to the left regular representation of W (For more on this see [69]). It follows that the dimension of C[x]W is exactly the order of the group W . We can get a finer description of this fact using a theorem of Chevalley (see [69, Section 3.5]) that can be stated as follows. There exists a natural isomorphism of W -modules C[x] ' C[x]W ⌦ C[x]W . (1.5) In other words, there is a unique decomposition of any polynomial p(x) of the form X p(x) = fw (x) bw (x), w2W for any given basis {bw (x) | w 2 W } of C[x]W , with the fw (x)’s invariant polynomials. One immediate consequence, in view of (1.2) and (1.3), is that Hq (QW ) = n Y 1 i=1 1.1.2 q di = (1 + · · · + q d1 1 q 1 ) · · · (1 + · · · + q dn 1 ). Diagonal and tensorial context We now extend our discussion to the ring C[x, y] := C[x1 , . . . , xn , y1 , . . . , yn ], of polynomials in two sets of n variables, on which we consider the diagonal action of W , namely such that: w · p(x, y) = p(w · x, w · y), (1.6) for w 2 W . In this case, W does not act as a reflection group on C[x, y], so that we are truly in front of a new situation, as we will see in more details below. By comparison, the results of Section 1.1.1 would still apply to C[x, y] if we would rather consider the action of W ⇥ W , for which (w, ⌧ ) · p(x, y) = p(w · x, ⌧ · y), (1.7) when (w, ⌧ ) 2 W ⇥ W , and p(x, y) 2 C[x, y]. Indeed, this does correspond to an action of W ⇥ W as a reflection group on C[x, y]. Each of these two contexts gives rise to a notion of invariant polynomials in the same space C[x, y]. Notation wise, we naturally distinguish these two notions as follows. On one hand we have the subring C[x, y]W of diagonally invariant polynomials, namely those for which p(w · x, w · y) = p(x, y); (1.8) and, on the other hand, we get the subring C[x, y]W ⇥W , of invariants polynomials of the tensor action (1.7), as a special case of the results described in Section 1.1.1. Observe that C[x, y]W ⇥W ' C[x]W ⌦ C[y]W . (1.9) 4 CHAPTER 1. GROUP ACTIONS AND STATISTICS In view of this observation, we will call C[x, y]W ⇥W the tensor invariant algebra. It is easy to see that C[x, y]W ⇥W is a subring of C[x, y]W . Since C[x, y] ' C[x] ⌦ C[y], from (1.2) we easily get 1 1 Hq,t (C[x, y]) = . (1.10) n (1 q) (1 t)n Furthermore, in view of (1.9) and (1.3), the bigraded Hilbert series of C[x, y]W ⇥W is simply Hq,t (C[x, y] W ⇥W )= n Y i=1 (1 1 q di )(1 td i ) . (1.11) Let C[x, y]W ⇥W be the spaces of coinvariants of W ⇥ W , defined in (1.4). From (1.10) and (1.11), we conclude that Hq,t (C[x, y]W ⇥W ) = n Y 1 i=1 n q d i Y 1 td i . 1 q 1 t (1.12) i=1 In fact, we have (W ⇥ W )-module isomorphisms of bigraded spaces C[x, y]W ⇥W ' C[x]W ⌦ C[x]W . Summing up, and considering W as a diagonal subgroup of W ⇥ W (i.e.: w 7! (w, w)) we get an isomorphism of W -modules C[x, y] ' C[x]W ⌦ C[y]W ⌦ C[x, y]W ⇥W , (1.13) from which we deduce, in particular, that C[x, y]V ' C[x]W ⌦ C[y]W ⌦ C[x, y]VW ⇥W , (1.14) where C[x, y]V and C[x, y]VW ⇥W are the isotypic components associated to the irreducible representation V of W . 1.1.3 Permutation statistics Here we collect some well-known results about permutation statistics over the symmetric group Sn , that motivate many of the generalizations we show in the following sections. In order to give such extensions we will use or define new statistics. It seems now clear that there are two types of statistics on generalized permutation groups. Those having an intrinsic algebraic meaning that we call flag, and those allowing nice generalizations of generating functions that we call negative. It has to be pointed out that many of the extensions in the literature and in the following section have been possible thanks to the introduction by Adin and Roichman in [1] of a fundamental statistic called flag major index on wreath products, that will be used several times in this work. A well-known theorem of MacMahon [80] shows that the length function and the major index are equidistributed over the symmetric group Sn . We recall that the length of a permutation 2 Sn is given by the number of inversions, denoted inv( ) := |{(i, j) | i < j, (i) > P (j)}|, and the major index of is the sum of all its descents. More precisely, maj( ) := i2Des( ) i, where Des( ) := {i 2 [n 1] | (i) > (i + 1)}. Foata gave a bijective proof of this equidistribution theorem in [49]. He studied further his bijection together with Schützenberger and derived the two following results [50]. The first one is a refinement of MacMahon’s theorem, asserting the equidistribution of major index and number of inversions over inverse descent classes. 1.1. INTRODUCTION 5 Theorem 1.1 (Foata–Schützenberger). Let M = {m1 , . . . , mt } ✓ {1, . . . , n X X q maj( ) = q inv( ) . 1 )=M } { 2Sn |Des( { 2Sn |Des( 1}. Then 1 )=M } The second one concerns the symmetry of the distribution of the major index and the inversion number over the symmetric group. Theorem 1.2 (Foata–Schützenberger). The pairs of statistics (maj, inv) and (inv, maj) have the same distribution on Sn , namely X X Sn (p, q) := pmaj( ) q inv( ) = pinv( ) q maj( ) . 2Sn 2Sn Theorem 1.1 has been extensively studied and generalized in many ways in the last three decades. Nevertheless, it still receives a lot of attention as shown by two relatively recent papers of Hivert, Novelli, and Thibon [68], and of Adin, Brenti, and Roichman [3], where a multivariate generalization, and an extension to the hyperoctahedral group of it are provided. We recall also some other classical results. The first one, due to Roselle [87], is the generating function of the inversion number and major index over the symmetric group: for undefined notation see at the end of this subsection. Theorem 1.3 (Roselle). X Sn (p, q) n 0 un 1 = , (p; p)n (q; q)n (u; p, q)1,1 (S0 (p, q) = 1). The second is the bivariate distribution of major index and number of descents over Sn , due to Carlitz [35]. Theorem 1.4 (Carlitz identity). Let n 2 N. Then P des( ) q maj( ) X 2Sn t n k [k + 1]q t = . (t; q)n+1 (1.15) k 0 This is a well-known q -analogue of the classical Eulerian polynomial the rational generating function P des( ) X 2Sn t n k (k + 1) t = . (1 t)n+1 P 2Sn tdes( ) , which has (1.16) k 0 The third one is the trivariate distribution of inversion number, major index, and number of descents, due to Gessel [57, Theorem 8.4], (see also [55]). Theorem 1.5 (Gessel). P X un [n]p ! n 0 2Sn tdes( ) q maj( ) pinv( (t; q)n+1 ) = X k 0 tk e[u]p e[qu]p · · · e[q k u]p . This result gives also an extension of the bivariate generating function of (des, inv) computed by Stanley, and then generalized to many other Coxeter groups (see e.g. [30, Section 7.2]). Finally, we state the following result of Garsia and Gessel, to whom we refer many times in this chapter. 6 CHAPTER 1. GROUP ACTIONS AND STATISTICS Theorem 1.6 (Garsia–Gessel). X n 0 X des( ) des( un t1 t2 (t1 ; q1 )n+1 (t2 ; q2 )n+1 2Sn = X k1 ,k2 0 1) maj( ) maj( q2 q1 tk11 tk22 . (u; q1 , q2 )k1 +1,k2 +1 1) (1.17) We recall the usual notation appearing in the previous formulas. For n 2 N we let [n]q := 1Q+ q + q 2 + . . . + q n 1 and [n] let also (a; q)0 := 1, (a; q)n := q · · · [2]q [1]q . WeQ Qq ! := [n]q [n n 1] n n Qm i 1 ), (a; q) 1 ), (a; t, q) (1 aq := (1 aq := ati 1 q j 1 ), and 1 n,m i=1 n 1 i=1 j=1 (1 Q Q P n u (a; t, q)1,1 := i 1 j 1 (1 ati 1 q j 1 ). Finally, e[u]q := n 0 [n] , is the q -analogue of q! the exponential function. 1.1.4 Combinatorial interpretation of G(r, p, n) As explained in the introduction, in order to show some generalizations of known results, as those listed in Section 1.1.3, and many others to some other class of groups, we decided to use the global setting of the complex reflection groups of type G(r, p, n). So when this is possible, we will present our results within this larger family. For our exposition it will be convenient to consider the elements of G(r, p, n) not as complex matrices, but as colored permutations. For any n 2 P := {1, 2, . . .} we let [n] := {1, 2, . . . , n}, and for any a, b 2 N we let [a, b] := {a, a + 1, . . . , b}. Let Sn be the symmetric group on [n]. A permutation 2 Sn will be denoted by = (1) · · · (n). Let r, n 2 P. The wreath product G(r, n) is defined by G(r, n) := {((c1 , . . . , cn ), ) | ci 2 [0, r 1], 2 Sn }. (1.18) Any ci can be considered as the color of the corresponding entry (i). This explains the fact that this group is also called the group of r-colored permutations. Sometimes we will represent its elements in window notation as g = g(1) · · · g(n) = (1)c1 · · · (n)cn . When it is not clear from the context, we will denote ci by ci (g). P Moreover, if ci = 0, it will be omitted in the window notation of g . We denote by col(g) := ni=1 ci . Now let p 2 P such that p|r . The complex reflection group G(r, p, n) is the subgroup of G(r, n) defined by G(r, p, n) := {g 2 G(r, n) | col(g) ⌘ 0 mod p}. (1.19) Note that G(r, p, n) is the kernel of the map G(r, n) ! Zp , sending g to its color weight col(g), and so it is a normal subgroup of index p. It is clear from the definition that G(r, 1, n) = G(r, n) the wreath product, G(1, 1, n) = Sn the symmetric group, G(2, 1, n) = Bn the Weyl group of type B , G(2, 2, n) = Dn the Weyl group of type D , and G(r, r, 2) = Ir is the dihedral group of order 2r . 1.2 Colored-Descent representations of G(r, p, n). In the paper [9] E. Bagno and R. Biagioli. Colored-descent representations of complex reflection groups G(r, p, n). Israel J. Math., 160 (2007), 317-348. 1.2. COLORED-DESCENT REPRESENTATIONS OF G(R, P, N ). 7 we define a new set of G(r, p, n)-modules, that we call colored-descent representations. They are generalizations of the descent representations introduced by Adin, Brenti, and Roichman in [4] for the symmetric and hyperoctahedral group, (see also [22] for Weyl groups of type D ). The decomposition into irreducibles of the colored-descent representations is provided. It turns out that the multiplicity of any irreducible representation is counted by the cardinality of a particular class of standard Young tableaux. The main combinatorial tool is the introduction of a new statistic that generalizes the major and flag-major index to all complex reflection groups. 1.2.1 Colored Descent Basis As first result we show a new explicit basis for the coinvariant algebra, see (1.4), when the acting group is G(r, p, n). In order to lighten the notation, we let G := G(r, n), H := G(r, p, n), and d := r/p. The wreath product G acts on the ring of polynomials C[x] as follows (1)c1 · · · (n)cn · p(x1 , . . . , xn ) = p(⇣ c (1) x (1) , . . . , ⇣ c (n) x (n) ), (1.20) where ⇣ denotes a primitive rth root of unity. A set of fundamental invariants under this action is given by the elementary symmetric functions ej (xr1 , . . . , xrn ), 1  j  n. Now, consider the restriction of the previous action on C[x] to H . A set of fundamental invariants is given by ⇢ ej (xr1 , . . . , xrn ) for j = 1, . . . , n 1 fj (x1 , . . . , xn ) := xd1 · · · xdn for j = n. It follows that the degrees of H are r, 2r, . . . , (n 1)r, nd. Let IH := (f1 , . . . , fn ), the module of coinvariants C[x]H := C[x]/IH has dimension equal n to |H|, that is n!rp . In what follows we will associate any element h 2 H with an ad-hoc monomial in C[x]. Those monomials will form a linear basis for the module of coinvariants. For any r, p, n 2 P, with p|r and d := r/p we define the following subset of G(r, n), (1.21) (r, p, n) := { = ((c1 , . . . , cn ), ) 2 G(r, n) | cn < d}. Note that := (r, p, n) it is not a subgroup of G but is in bijection with H . We specify a bijection, in such a way that some of the definitions we introduce, coincide with the usual ones, once we specialize H to any classical Weyl group. Indeed, one can easily check that the mapping cn ((c1 , . . . , cn ), ) 7! ((c1 , . . . , b c), ) (1.22) p is a bijection between H and . As usual for any a 2 Q, bac denotes the greatest integer  a. In order to make our definitions more natural and clear, from now on, we will work with instead of H . Clearly, via the above bijection every function on can be considered as a function on H and viceversa. We fix the following order 1r 1 2r 1 ... nr on colored integer numbers 1 ... 11 21 n1 ... The descent set of an colored integer sequence 2 = ((c1 , . . . , cn ), ) 2 i i+1 }. Moreover for any 1 2 ... is defined by Des( ) := {i 2 [n we let di ( ) := |{j 2 Des( ) | j ⌫ i}| and mi ( ) := r · di ( ) + ci ( ). For every 2 we define the G(r, p, n)-major index of m( ) := n X i=1 n. mi ( ). (1.23) 1] | (1.24) by (1.25) 8 CHAPTER 1. GROUP ACTIONS AND STATISTICS The parameter “ m” specializes to the major index in type A, to the flag-major index in type B ([1]), and type D ([21]). Also for 2 G(r, n), we get m( ) = r · maj( ) + col( ) = fmaj( ) as defined in [1]. Let = ((c1 , . . . , cn ), ) 2 . We define x := n Y x mi ( ) (i) . (1.26) i=1 A straightening algorithm shows that the x ’s form a set of generators for C[x]H , from which we deduce the following theorem. Theorem 1.7. The set {x + IH | is a basis for C[x]H . 2 } Note that, when H specializes to one of the classical Weyl groups, our basis coincides with the descent basis defined by Garsia-Stanton for Sn [56], by Adin-Brenti-Roichman for Bn [4], and by Biagioli-Caselli for Dn [22]. Another basis for C[x]H has been given by Allen [6]. Although both our and Allen’s basis coincide with the Garsia-Stanton basis in the case of Sn , in general they are different as can be checked already in the small case of G(2, 2, 2). It would be interesting to see if Allen basis leads to an analogous definition of descent representations. 1.2.2 Colored-descent representations of G(r, p, n) The module of coinvariants C[x]H has a natural grading induced from that of C[x]. If we denote by Rk its k th homogeneous component, we have: M C[x]H = Rk . k 0 Since the action (1.20) preserves the degree, every homogeneous component Rk is itself a H module. In this section we introduce a set of H -modules RD,C which decompose Rk . The representations RD,C , called colored-descent representations, generalize to all groups G(r, p, n), the descent representations introduced for Sn and Bn by Adin, Brenti and Roichman in [4]. See also [22] for the case of Dn . In the case of G(r, n), a Solomon’s descent algebra approach to these representations has been done by Baumann and Hohlweg [14]. Since their study is restricted to wreath products, it will be interesting to extend their results to all complex reflection groups, thus getting characters of all our modules as images of a particular class of elements of the group algebra. We associate to each monomial M of C[x] the partition obtained reordering in a nonincreasing order the exponents of its variables. We call such a partition the exponent partition of M , denoted by (M ). Let be a partition such that | | = k , and denote by C the dominance order on partitions, then J E := spanC {x + IH | J C := spanC {x + IH | 2 , (x ) E } and 2 , (x ) C } are two submodules of Rk . Their quotient is still an H -module, denoted by JE R := C . J For any D ✓ [n 1] we define the partition D := ( 1 , . . . , For D ✓ [n 1] and C 2 [0, r 1]n , we define the vector D,C := r · D + C, n 1 ), where i := |D\[i, n 1]|. 1.2. COLORED-DESCENT REPRESENTATIONS OF G(R, P, N ). 9 where sum stands for sum of vectors. From now on we denote RD,C := R D,C , and by x̄ the image of the colored-descent basis element x 2 J ED,C in the quotient RD,C . The H -modules RD,C are called colored-descent representation in analogy with [4, Section 3.5]. They decompose the k th component of C[x]H as follows. Theorem 1.8. For every 0  k  r n 2 + n(d 1), M Rk ' RD,C D,C as P H -modules, where the sum is over all D ✓ [n j2C j = k. Moreover the set {x̄ | is a basis of RD,C . 1], C 2 [0, r 1]n such that r · 2 , Des( ) = D and Col( ) = C} P i2D i+ Our next target is a simple combinatorial description of the multiplicities of the irreducible representations of H in RD,C . It is well-known that irreducible representations of G are indexed by r -tuples of partitions ~ := ( 0 , . . . , r 1 ) with Pr 1 | i | = n. On the other hand, irreducible representations of H i=0 are parametrized by ordered pairs ([~ ], ), where [~ ] is the orbit of ~ through a d-cyclic shift of its parts i , and 2 C~ the stabilizer of ~ . More precisely, by a cyclic shift we mean the operation (~ ) 1 := ( r 1 , 0 , . . . , r 2 ), hence the orbit is defined by ~ ⇠µ ~ if and only if ~ = µ ~ i·d for i = 0, . . . , p 1. We now define a new family of tableaux and a major index on such tableaux. These two tools will allow us to describe the decomposition into irreducible components of the descent representations. Let [~ ] be the orbit of ~ = ( 0 , . . . , r 1 ). An orbital standard Young tableau T = 0 (T , . . . , T r 1 ) of type [~ ] is a standard Young r -tableau having one of the shapes in [~ ]. Namely each T i is a standard Young tableau of shape i in the usual sense. An n-orbital standard Young tableau of type [~ ] is an orbital tableau of type [~ ] such that n 2 T 0 [ . . . [ T d 1 . We denote the set of such tableaux by OSYTn [~ ]. The flag major index of an r -tableau is defined as one expect by fmaj(T ) := r · maj(T ) + col(T ). (1.27) Here maj(T ) is the sum of the descents in a r -standard Young tableau, namely of the entries i such that i + 1 is strictly below i in T . The color of a tableau is col(T ) := ✏1 + · · · + ✏n where ✏i = k if i 2 T k . Example 1.9. Let r = 6 and n = 17. If p = 3, and so d = 2, then the two tableaux T1 and T2 in Figure 1.3 are of the same type [~ ] = [(1), (2), (2, 1), (1, 1), (3, 1), (2)]: T1 is n-orbital, while T2 is not. Differently, for p = 2, and d = 3 the two tableaux T1 and T2 are not in the same orbit [~ ]. Nervertheless, T2 is an n-orbital tableau of type [(3, 1), (2), (1), (2), (2, 1), (1, 1)]. Theorem 1.10. For every D ✓ [n 1] and C ✓ [0, r 1]n 1 ⇥ [d], ~ 2 Pr,n and 2 C~ , the multiplicity of the irreducible representation of G(r, p, n) corresponding to the pair ([~ ], ) in RD,C is |{T 2 OSYTn [~ ] | Des(T ) = D, Col(T ) = C}|. Corollary 1.11. For 0  k  r direct sum mk,( ([~ ], ), and , )V ([~ ], ) , n 2 + n(d 1), the representation Rk is isomorphic to the ([~ ], ) is the irreducible representation of H labeled by where V mk,([~ ], ) :=| {T 2 OSYTn [~ ] | fmaj(T ) = k} | . 10 CHAPTER 1. GROUP ACTIONS AND STATISTICS 6 8 12 13 8 1 14 3 11 5 T1 = 4 11 14 T2 = 2 7 1 2 3 9 5 4 6 12 13 7 10 9 10 Figure 1.3: A 4-tableau and its 2-shift 1.2.3 Carlitz identity As a corollary of our approach we obtain a particular bijective encoding of the monomial of C[x] which proves the following lemma. Lemma 1.12. Let n 2 P. Then X ✓ `( )n n m0 ( ), m1 ( ), . . . ◆Y n P nQ1 2 qi i = i=1 i=1 q1d · · · qnd ) (1 rdi ( )+ci ( ) qi in C[[q1 , . . . , qn ]]. nQ1 i=1 (1.28) , (1 q1r · · · qir ) n Note that m0 ( ),m is the number of monomials in C[x] with exponent partition , 1 ( ),... and so the LHS below is the multi graded Hilbert series of C[x]. Now the specialization q1 = qt, q2 = · · · = qn = q in (1.28) gives us the Carlitz identity below. Note that the degrees r, 2r, . . . , (n 1)r, nd of G(r, p, n), appear as powers of the q ’s in the denominators of the formula. Here we set for any g 2 the flag descent number equal to d( ) := r · des( ) + c1 ( ). (1.29) Theorem 1.13 (Carlitz identity for H ). Let n 2 N. Then P d(h) q m(h) X h2G(r,n,p) t n k [k + 1]q t = (1 t)(1 tr q r )(1 tr q 2r ) · · · (1 tr q (n k 0 1)r )(1 td q nd ) . This identity for adequate specializations of r and p gives a generalizations of all known Carlitz identities for type A (see Theorem 1.4), B , and D . Differently, if we plug q1 = . . . = qn = q in (1.28), we get the following identity 1 (1 q)n P 2 = (1 q nd ) q m( nQ1 ) . (1 q ri ) i=1 Here, the left-hand side is the Hilbert series of the ring of polynomials (simply graded) (see (1.2), while the right-hand side is the product of the Hilbert series of the module of coinvariants of G(r, p, n) by the Hilbert series of the invariants of G(r, p, n) (on the denominator, see (1.3)). Clearly, this equality reflects the isomorphism between graded H -modules (1.5) C[x] ' C[x]H ⌦ C[x]H , which holds if and only if H is a complex reflection groups. 1.3. TENSORIAL SQUARE OF THE HYPEROCTAHEDRAL GROUP COINVARIANT SPACE11 1.3 Tensorial square of the Hyperoctahedral group Coinvariant Space In this section we restrict G(r, p, n) to the hyperoctahedral group Bn , and we consider the tensor product decomposition (1.13), which is, as we already remarked, an isomorphism of Bn -modules, since both C[x]Bn and C[y]Bn are Bn -invariant. Here we are in the diagonal context and the group acts on the polynomial ring in two sets of variables explicitly as follows (xi , yj ) = (±x| |(i) , ±y| |(j) ), where ± denotes some appropriate sign, and | | is the unsigned permutations corresponding to . We recall that irreducible Bn -representations are naturally parametrized by ordered pairs ( , ⇢) of partitions such that the total sum of their parts is equal to n. In the paper [15] F. Bergeron and R. Biagioli. Tensorial square of the hyperoctahedral group coinvariant space. Elect. J. Combin., 13 (2006), R38. we consider a restriction of (1.13) to the isotypic components (see also (1.14)) obtaining C[x, y]( ,⇢) ' C[x]W C[y]W ( ,⇢) (1.30) C[x, y]Bn ⇥Bn . ( ,⇢) The goal is to give explicit descriptions of the isotypic components C[x, y]Bn ⇥Bn of the coinvariant space with respect to the action of Bn rather then that of Bn ⇥ Bn . In fact, in the latter case this would just be the regular representation for which everything is known. Now, we present characterizations for two of such components, the trivial and the alternating. In order to do this, we introduce two new classes of combinatorial objects called compact e-diagrams and compact o-diagrams. This work extends some of the results of [17] to type B. By a computation of the Frobenius characteristic of the representation C[x, y]Bn ⇥Bn one gets that each irreducible representation V ( ,⇢) of Bn , appears in C[x, y]Bn ⇥Bn with multiplicity equal to ✓ ◆ n n 2 n! f f⇢ , (1.31) | | where the value of f is given by the well-known hook length formula. 1.3.1 The trivial component of C[x, y]Bn ⇥Bn The trivial isotypic component C[x, y]Bn of C[x, y] is made of diagonally invariant polynomials. Without surprise, it develops that a linear basis for C[x, y]Bn is naturally indexed by even bipartite partitions. These are bipartite vectors ✓ ◆ a 1 a 2 . . . an (a, b) = , (1.32) b1 b2 . . . b n whose parts, (ai , bi ), are ordered in increasing lexicographic order, and such that each ai +bi is even. In the sequel we will use the term e-diagram rather then that “even bipartite partition”. The announced homogeneous basis for C[x, y]Bn is simply given by the set {M (a, b) | (a, b) is an e-diagram with n parts}, of monomial diagonal invariants, defined as: X M (a, b) := { · xa y b | 2 Sn }, 12 CHAPTER 1. GROUP ACTIONS AND STATISTICS where we sum over the set of (hence distinct) monomials obtained by permuting the variables. For example, with n = 3, M ( 00 04 22 ) = y24 x23 y32 + x22 y22 y34 + y14 x23 y32 + y14 x22 y22 + x21 y12 y34 + x21 y12 y24 . Observe that the leading monomial of M (a, b) is xa yb . Clearly, each M (a, b) is a bihomogeneous polynomial of bidegree (|a|, |b|). We will also say that |D| := (|a|, |b|), is the weight of the e-diagram D . In view of (1.31), the dimension of trivial isotypic component of C[x, y]Bn ⇥Bn , (which corresponds to the pair (n, 0)) is equal to the order of Bn . It is thus natural to expect the n existence of a basis Mn = {M | 2 Bn } of C[x, y]B Bn ⇥Bn indexed naturally by elements of Bn . Moreover thanks to the decomposition (1.30) we know that for every e-diagram there are unique u (x, y)’s in C[x]Bn ⇥ C[y]Bn such that X M (a, b) = u (x, y) M . (1.33) 2Bn n To construct of such a basis for C[x, y]B Bn ⇥Bn we follow the steps listed here. (1) First we associate to each e-diagram D a classifying signed permutation The figure below gives a graphical representation of the e-diagram ✓ ◆ 0 0 1 2 2 6 8 9 9 D= . 0 0 5 6 6 4 0 5 9 (D) 2 Bn . (1.34) Integers in the cells represent multiplicity. The associated classifying signed permutations is (D) = 1̄2̄57̄8̄4̄3̄69 2 B9 . It is obtained by first numbering the cells of the diagram from left to right and from bottom to top by the entries from 1 to n, and giving them a negative sign if are in odd columns, and then by reading such labeled cells from bottom to top and from left to right. i 2y i 1y i 2y i 1y i 1y i 1y i 1y (2) Then we introduce an equivalence relation on the set of e-diagrams saying that D and D̃ are equivalent if and only if they have the same classifying signed permutation. In symbols, e () (D) = (D). e D'D (3) We define the notion of compacting moves for a diagram. These moves are characterized in a simple geometric manner and are designed to preserve the underlying classified signed permutation. A cell of a diagram can be moved down or to the left if the highlighted areas in Figure 1.4 are empty. If D̃ is obtained by compacting the diagram D , then the two diagrams are equivalent. 1.3. TENSORIAL SQUARE OF THE HYPEROCTAHEDRAL GROUP COINVARIANT SPACE13 x ? x x x Figure 1.4: Constraints on compacting moves. (4) Finally we call a diagram for which no compacting move is possible compact. Observe that, starting with any given e-diagram D , if one keeps applying compacting moves (in whatever order) until no such move is possible, then the final result will always be the same compact diagram, denoted D . Hence in each class there is a unique compact diagram D , which we can label with its classifying signed permutation. We can finally define the set Mn := {M (D ) | D is the compact diagram labeled by }. (1.35) n Now, we show that this set forms a basis for C[x, y]B Bn ⇥Bn . The proof is based on the following theorem, which reflects, in combinatorial terms, the bigraded module isomorphism (1.30). Theorem 1.14. There is a natural bijection, ', between n-cell e-diagrams and triplets D $ (D, , µ), where D is the compact diagram associated with D , and and µ are two partitions with parts smaller or equal to n. Moreover, these partitions are such that (1.36) |D| = |D| + 2(| |, |µ|). Here a pictorial example of the bijection is given in Figure 1.5. i 0 1y 1 1 i 1 2y i y i 3 1 1y y i 5 1 6 6 6 y i 6 2i 1y 7 6 4 4 4 4 3 3 2 0 0 0 0 0 i 0 1y i y 1 2 i i 3 1y 1y y i 5 1 6 y i 6 2i 1y 7 6 4 4 3 3 2 0 0 0 Figure 1.5: Differences of marginal partitions of D and D : = 4 and µ = 61. We are ready to describe a straightening algorithm for the expansion of any diagonally invariant polynomial in terms of the elements in the set Mn , with coefficients in the ring 14 CHAPTER 1. GROUP ACTIONS AND STATISTICS C[x]Bn ⌦ C[y]Bn . Let D = (a, b) an e-diagram, and consider the effect on D of the bijection ' of Theorem 1.14: '(a, b) = ((a, b), , µ), where we have (a, b) = D . Then we can show that X M (a, b) = m 0 (x2 )mµ0 (y2 )M (a, b) M0 M 0, (1.37) lex M (a,b) where m 0 (x2 ) is the usual monomial symmetric function in the squares of the x variables, and 0 is the transpose partition of . Repeating this process on the remaining terms, we get the desired expansion. For example, if n = 2 and D = ( 13 44 ); then D = ( 11 22 ), = 1 and µ = 2. Then we calculate that M ( 13 44 ) = m1 (x2 )m11 (y2 )M ( 11 22 ) M ( 24 33 ). In a similar manner we also get, M ( 24 33 ) = m11 (x2 )m11 (y2 )M ( 02 11 ) hence M ( 13 44 ) = m1 (x2 )m11 (y2 )M12 m11 (x2 )m11 (y2 )M21 . It follows that the M ’s are indeed a set of generators for the trivial component of n C[x, y]Bn ⇥Bn . Since the dimension of C[x, y]B Bn ⇥Bn is |Bn |, as we pointed out at the beginning of Section 1.3.1, we have Proposition 1.15. The set {M (D ) + IBn ⇥Bn | 2 Bn }, is a bihomogeneous basis for the trivial component of C[x, y]Bn ⇥Bn . In particular, the recursive procedure (1.37) give us also expressions for the invariant polynomials u (x, y) in C[x]Bn ⌦ C[y]Bn in (1.33) Now, another interesting property of such basic monomials is that for any 2 Bn , the total degrees in x and y of M (D ) can be expressed in terms of fmaj( ) and fmaj( 1 ). n More precisely, we have that the bigraded Hilbert series of C[x, y]B Bn ⇥Bn is X n Hq,t (C[x, y]B Bn ⇥Bn ) = q fmaj( ) tfmaj( 1) (1.38) . 2Bn From this and (1.30), it follows the graded Hilbert series of the diagonally invariant polynomials is given by Hq,t (C[x, y] Bn )= X 2Bn q fmaj( ) fmaj( t 1) n Y i=1 1 1 q 2i n Y i=1 1 1 t2i . (1.39) This was already been computed by Adin and Roichman in [1] and by the author and Caselli in [21], by using different methods. 1.3. TENSORIAL SQUARE OF THE HYPEROCTAHEDRAL GROUP COINVARIANT SPACE15 i 2y 12 i 1y i 1y i 1y i y 1 i 1y 1̄2 12̄ i 1y i 1y i 1y 21 i 2y i 1y i 1y i 1y 21̄ 2̄1 1̄2̄ i 1y 2̄1̄ Figure 1.6: Compact e-diagrams for n = 2. 1.3.2 The alternating component of C[x, y]Bn ⇥Bn Recall that a polynomial p(x, y) is said to Bn -diagonally alternating if · p(x, y) = sign( )p(x, y), for all 2 Bn . Recall also that the sign of an element sign( ) = · of Bn can be computed as (x) , (x) Q with (x) = x1 · · · xn 1i<jn (x2i x2j ). It is easy to see that a basis of the space C[x, y]± of diagonally Bn -alternating polynomials is obtained as follows. An o-diagram (“ o” for odd) D = (a, b), as in (1.32), is any n-element subset of N ⇥ N, with all cells of odd parity. This is to say all the ai + bi ’s are odd. As is now our custom, the cells of D are ordered lexicographically. We emphasize that in the present context the cells of an o-diagram are all distinct. We then consider the determinant xa11 y1b1 .. D (x, y) := . xa12 y1b2 .. . xan1 ynb1 xan2 ynb2 . . . xa1n y1bn .. .. , . . . . . xann ynbn (1.40) which is easily seen to be diagonally Bn -alternating. It is not hard to see that a linear basis for C[x, y]± is given by the set { D | D ✓ (N ⇥ N)1 , |D| = n}. (1.41) Here (N ⇥ N)1 := {(a, b) 2 N ⇥ N | a + b ⌘ 1 (mod 2)}. Thus an n element subset of (N ⇥ N)1 is just an o-diagram. As for the trivial component, (1.31) tells us that the dimension of the alternating component is equal to the order of Bn . As we have seen previously, the bijection ' of Theorem 1.14 is a combinatorial “shadow” of the bigraded module isomorphism (1.14) for the diagonally invariant polynomials. In the same manner, we can translate in combinatorial terms the isomorphism (1.14) for diagonally alternating polynomials. This involves a similar bijection, but a different notion of compact diagrams. Just as in the e-diagram case, there is a classification of o-diagrams in terms of elements of Bn . The construction is very similar, with only a change in the labeling order. Just as in our previous case, we say that two o-diagrams e , if they have the same classifying signed permutation. Following the are equivalent D ' D same thread as for e-diagrams, we can define the compactification of o-diagrams, and the corresponding family of |Bn | o-compact diagrams. For n = 2, the 8 compact o-diagrams are illustrated in Figure 1.7. Through an argument close to that of Theorem 1.14, we then get a bijection with properties similar to those of '. Namely, 16 CHAPTER 1. GROUP ACTIONS AND STATISTICS x x x 12 x 21 x x 1̄2 x x x x x 12̄ x x 2̄1 1̄2̄ x x 21̄ x 2̄1̄ Figure 1.7: All 8 compact o-diagrams with 2 cells. Theorem 1.16. There is a natural bijection, 's , between n-cell o-diagrams and triplets s D $ (D , , µ), s where D is the compactification of D , and and µ are two partitions with parts smaller or equal to n. Moreover, these partitions are such that |D| = |D| + 2(| |, |µ|). As for e-compact diagrams, the x and y degrees of the o-compact diagrams can be expressed by using the flag major index. We obtain that Hq,t (C[x, y]± ) = X 2Bn q fmaj( ) tn 2 fmaj( 1) n Y i=1 1 1 q 2i n Y i=1 1 1 t2i . (1.42) Unfortunately, in this case we were unable to show that the monomials associated to compact o-diagrams form a linear basis for C[x, y]± Bn ⇥Bn . They are the right number and have the correct q, t degrees as (1.42) shows, hence they are a good candidate. There are similar identities for the Hilbert series associated to each irreducible character of Bn , taking the form   n Y n n 1 ( ,⇢) Hq,t (C[x, y]) = , ,µ (q, t) 2i | | q2 |µ| t2 (1 q )(1 t2i ) i=1 with expressions in bracket (in the right hand side) standing for q 2 -binomial coefficients (or t2 binomial coefficients), and ,µ (q, t) a positive integer coefficient polynomial. These identities should also be explained through bijections similar to those that we have considered above. This remains an open problem also in the case of the symmetric group. Some progress was made by F. Lamontagne [77] in his Ph.D. thesis, and there are some conjectural answers by F. Bergeron (personal communication). For example, in the case of the symmetric group, there should be a notion of compact diagrams indexed by pairs ( , T ) where is a permutation and T is a Young standard tableau, where the charge statistic plays a natural role. 1.4 Generalizations to other permutation groups In this section we generalized to the Coxeter groups of type B and D , to the wreath products G(r, n), and to a new family of projective reflection groups some of the results showed in Section 1.1.3. The results of this section are taken from the papers : 1.4. GENERALIZATIONS TO OTHER PERMUTATION GROUPS 17 [23] R. Biagioli and F. Caselli. Enumerating Projective Reflexion Groups. Adv. in Appl. Math., 48 (2012), 249-268. [28] R. Biagioli and J. Zeng. Enumerating Wreath Products Via Garsia-Gessel Bijections. Europ. J. Combin. 32 (2011), pp. 538-553. [27] R. Biagioli and J. Zeng. On some analogues of Carlitz’s identity for the hyperoctahedral group. Sém. Lothar. Combin., Article B61Ak (2010), 13 pages. [19] R. Biagioli. Equidistribution of negative statistics and quotients of Coxeter groups of type B and D. Adv in Appl. Math., 41 (2008), 378-394. [18] R. Biagioli. Signed Mahonian polynomials for classical Weyl groups. Europ. J. Combin., 27 (2006), 207-217 1.4.1 Generalizations to type B , type D , and wreath products We start by giving analogs of Foata-Schützenberger Theorems 1.1, 1.2 for the Coxeter groups of type D . This was an open problem proposed in [3, Problem 5.6], where the case B was studied. Actually, we show that the negative statistics, introduced in [2] on Coxeter groups of type B , and in [33] on Coxeter groups of type D , give generalizations of the first and second Foata-Schützenberger identities to Bn and Dn . The proofs are based on detailed descriptions of the quotients, or sets of minimal coset representatives, of Bn and Dn that are interesting in their own. Here the relevant definitions of the negative statistics and the main results. For any 2 Bn we set nmaj( ) = maj( ) + neg( ) + nsp( ), ndes( ) = des( ) + neg( ), dmaj( ) = maj( ) + nsp( ), ddes( ) = des( ) + neg( ) + ✏( ), where neg( ) is the number of negative entries of , nsp( ) is the number of pairs 1  i < j  n such that (i) + (j) < 0, and ✏( ) is a corrective terms equal to 0 if 1 is a positive entry of , and 1 otherwise. Theorem 1.17. Let n 2 P and M ✓ [0, n 1]. Then X X q nmaj( ) = q `B ( { 2Bn |DesB ( X { 2Dn |DesD ( 1 )=M } { 2Bn |DesB ( q dmaj( ) 1 )=M } X = { 2Dn |DesD ( ) = 1 )=M } X { 2Bn |DesB ( q `D ( ) . q fmaj( ) 1 )=M } (1.43) 1 )=M } Note that the equidistribution over inverse descent classes does not hold for the flag-major index of type D . Here the descent sets DesB and DesD are the usual descent sets in Coxeter theory. Proposition 1.18. The distributions of (nmaj, `B ) over Bn and of (dmaj, `D ) over Dn are symmetric, namely X X Bn (p, q) := pnmaj( ) q `B ( ) = p`B ( ) q nmaj( ) 2Bn Dn (p, q) := X 2Dn p dmaj( ) `D ( ) q 2Bn = X 2Dn p`D ( ) q dmaj( ) . 18 CHAPTER 1. GROUP ACTIONS AND STATISTICS Note that the flag major indices over both Bn and Dn (defined as in (1.25)) do not share this property of symmetry with the length. In is well-known that every w in a Coxeter group W has a unique factorization w = wJ wJ , where wJ 2 W J , and wJ belongs to a parabolic subgroup WJ , and wJ to its associated quotient W J . By using this decomposition and the analogous statements for Sn we obtain easily the two following results. Proposition 1.19 (Roselle identities for Bn and Dn ). X Bn (p, q) n 0 1+ X Dn (p, q) n 1 un (p; p)n (q; q)n ( pq; pq)n un (p; p)n (q; q)n ( pq; pq)n = 1 , (B0 (p, q) := 0); (u; p, q)1,1 = 1 . (u; p, q)1,1 1 Proposition 1.20 (Gessel identities for Bn and Dn ). P ndes( ) q nmaj( ) p`B ( ) X un X 2Bn t = tk e[u]p e[tu]p · · · e[tk u]p ; [n]p ! ( tqp; tq)n (t; q)n+1 n 0 k 0 P ddes( ) dmaj( ) ` ( ) X un X q pD 1 2Dn t + = tk e[u]p e[tu]p · · · e[tk u]p . 1 t [n]p ! ( tqp; tq)n 1 (t; q)n+1 n 1 k 0 The next step is to obtain similar results for flag statistics. Things becomes more complicated, and the previous proofs do not work. We remarked already that Foata–Schützenberger results do not hold for flag statistics. Nevertheless, we were able to find generalizations for the two results of Garsia and Gessel (Theorems 1.5 and 1.6) for the whole family of groups G(r, n). We do not present these results here since they will obtained as special cases of generating series given in the next section. To introduce the new section we state the analogous result for the Hilbert series (1.38) in type D (see [21]). We use the variables q1 , q2 , since later we will connect this identity with Theorem 1.6. X m( ) m(↵( )) n Hq1 ,q2 (C[x, y]D ) = q1 q2 . (1.44) Dn ⇥Dn 2Dn 1 but one depending on another element The term q2 does not have an exponent involving ↵( ) 2 Dn , which is not always the inverse of , as one would like to have. 1.4.2 Projective reflection groups Motivated by the problem to understand why this function ↵ appears in such an expression, Caselli defined in [36] a new class of groups, the projective reflection groups, which are generalizations of reflection groups. Among them, there is a family denoted G(r, p, s, n) of projective reflection groups, which includes all the groups G(r, p, n) (in fact G(r, p, 1, n) = G(r, p, n)). Fundamental in the theory of these groups is the following notion of duality: if G = G(r, p, s, n) then we denote by G⇤ = G(r, s, p, n) (where the roles of p and s have been interchanged). We note in particular that reflection groups G satisfying G = G⇤ are exactly the wreath products G(r, n) = G(r, 1, 1, n) and that in general if G is a reflection group then G⇤ is not. Caselli showed that much of the theory of reflection groups can be extended to projective reflection groups and that the combinatorics of a projective reflection group G of the form G(r, p, s, n) is strictly related to the (invariant) representation theory of G⇤ , generalizing several known results for wreath products in a very natural way. Among 1.4. GENERALIZATIONS TO OTHER PERMUTATION GROUPS 19 these, we mention the extension of the concept of descent representations (see Section 1.2.2) to G(r, p, s, n), and the generalization of the definition of flag major index. This might be considered the good extension of the major index to all these generalized permutations groups. We used this unifying definition of major index to generalize to the whole class of projective reflection some of the results presented in the previous section, and some others. A projective reflection group is a quotient of a reflection group by a scalar subgroup (see [36]). Observe that a scalar subgroup of G(r, n) is necessarily a cyclic group Cs of order s, generated by ⇣s I , for some s|r , where I denotes the identity matrix. It is also easy to characterize all possible scalar subgroups of the groups G(r, p, n): in fact the scalar matrix ⇣s I belongs to G(r, p, n) if and only if s|r and ps|rn. In this case we let (1.45) G(r, p, s, n) := G(r, p, n)/Cs . If G = G(r, p, s, n) then the projective reflection group G⇤ := G(r, s, p, n), where the roles of the parameters p and s are interchanged, is always well-defined. We say that G⇤ is the dual of G and we refer the reader to [36] for the main properties of this duality. Now, we introduce analogous definitions for descents and flag descents for projective reflection groups. Following [36, §5], for g = (c1 , . . . , cn ; ) 2 G(r, p, s, n) we let HDes(g) := {i 2 [n 1] | ci = ci+1 , and (i) > (i + 1)}, hi (g) := |{j i | j 2 HDes(g)}|, ⇢ Rr/s (cn ) if i = n ki (g) := ki+1 + Rr (ci ci+1 ) if i 2 [n (1.46) 1]. We call the elements in HDes(g) the homogeneous descents of g . Note that the sequence (k1 (g), . . . , kn (g)) is a partition such that g = (Rr (k1 (g)), . . . , Rr (kn (g)); ), where Rr : Z ! [0, r 1] the map residue module r . For g 2 G(r, p, s, n), we let i (g) := r·hi (g)+ki (g). The sequence (g) := ( 1 (g), . . . , n (g)) is a partition. The flag-major index for g 2 G(r, p, s, n) is defined by fmaj(g) := | (g)| = n X i (g). (1.47) i=0 We define the descent number and the flag descent number of g 2 G(r, p, s, n) respectively by j s (g) + r s k 1 des(g) := and (1.48) r fdes(g) := 1 (g). (1.49) Pn Finally, for g = (c1 , . . . , cn ; ) 2 G(r, p, s, n) we define the color of g by col(g) := i=1 Rr/s (ci ). Note that the previous definitions do not depend on the particular representative of g 2 G(r, p, s, n) chosen among its s lifts in G(r, n). Moreover the flag major index on G(r, p, s, n) coincides with with the flag major index of Adin and Roichman for wreath products G(r, n), and is equidistributed with the flag major index m defined in (1.25) for G(r, p, n). Similarly, des(g) in (1.48) coincides with the usual descent number (i.e. the number of simple reflections that lower the length) when g belongs to Bn , Dn , or to G(r, n). The definition of fdes in (1.49) is consistent with the usual of flag descents in G(r, n) that was given in (1.29). These equalities give motivations to the definitions of the previous statistics. 1.4.3 One-dimensional characters and flag major index Sums of the form X w2W (w)q des(w) , 20 CHAPTER 1. GROUP ACTIONS AND STATISTICS where W is a classical Weyl group, is a one-dimensional character of W , and des(w) is the number of descents of w as Coxeter group element, have been investigated by Reiner [85]. In the case of the symmetric group, when is the trivial character this sum is the well known Eulerian polynomial [35], and when is the sign character then it is the signed Eulerian polynomial studied by Désarménien and Foata [40], and Wachs [103]. Analogously, consider the sum X (w)q majW (w) , (1.50) w2W where majW denotes a suitable Mahonian statistic on the corresponding group W . In the case of the symmetric group, if is the trivial character, the sum in (1.50) is nothing but the Poincaré polynomial of Sn , which, as is well known, admits a nice product formula for every finite Coxeter group (see e.g., [69]): X X q maj( ) = q `( ) = [1]q [2]q · · · [n]q . 2Sn 2Sn Otherwise, if is the sign character, this sum corresponds to the signed Mahonian polynomial studied by Gessel and Simion [103], who found the elegant product formula Theorem 1.21 (Gessel-Simion). Let n 2 P. Then X ( 1)`( ) q maj( ) = [1]q [2] q 2Sn · · · [n]( 1)n 1q . Several extensions of this result have been given by Adin, Gessel, and Roichman in [5]. In particular, they provided nice formulas for the polynomial in (1.50) in the case of the hyperoctahedral group Bn equipped with the flag-major index, which is a Mahonian statistic on Bn (see [1, Theorem 2]). The group Bn has four one-dimensional characters: the trivial, the sign character, the character ( 1)neg( ) , and the sign of (| 1 |, . . . , | n |). In each case the corresponding generating functions has been computed and has a nice product expansion [5]. In [18], we provide a factorial-type formula for the signed Mahonian polynomial for the Weyl group Dn by completing a picture for classical Weyl groups. We used the flag major index of type D (see (1.25) or [21]) which is a Mahonian statistic on Dn . To prove our result we define a natural sign-reversing involution on Bn , in the style of Wachs (see [103]), that is fmaj preserving. We use this involution, first to give an easy proof of the Adin-Gessel-Roichman formula for the signed Mahonian polynomial for B2n , and then to derive from the latter formula the analogue for Dn . Now we want to give a unified statement of this result in the context of the projective reflection groups. The irreducible representations of G(r, p, s, n) are classified in [36, §6]. In particular, for n > 2, the one-dimensional characters of G(r, p, s, n) are all of the form ✏,k (g) = ✏inv(|g|) ⇣rk·c(g) , where ✏ = ±1, ⇣r is the primitive r -root of unity e2⇡i/r , k 2 [0, pr 1] with the further condition that s divides kn, and c(g) is the sum of the colors of any element in G(r, p, n) representing the class of g (in particular c(g) = col(g) if s = 1). As usual for 2 Sn , we denote by inv( ) the number of its inversions, and by sign( ) := ( 1)inv( ) its sign. Our main result is the following one. Theorem 1.22. Let X g2G(r,p,s,n) ✏,k (g)q fmaj(g) ✏,k be a one dimensional character of G(r, p, s, n). Then  r = p (⇣ k q)p  2r p (✏⇣ k q)p ···  (n 1)r p (✏n 2 ⇣ k q)p  nr ps (✏n 1 ⇣ k q)p n [p]n⇣ k qm [p]m ✏⇣ k q where m = bn/2c, and {F }qp is the polynomial obtained from F discarding all the homogeneous components in the variable q of degree not divisible by p. o qp 1.4. GENERALIZATIONS TO OTHER PERMUTATION GROUPS 21 Hence for r = 2 and p = s = 1 in Theorem 1.22, we obtain [5, Theorems 5.1, 6.1, 6.2]; for r = s = 2 and p = 1 [18, Theorem 4.8]. 1.4.4 Carlitz identities In this section we give a general method to compute the trivariate distribution of des (or fdes), fmaj and col over G(r, p, s, n). This unifies and generalizes all related results cited in Section 1.1.3, and provides two different generalizations of Carlitz identity for the group G(r, p, s, n). Before showing our results, we open an historical parenthesis to explain where come from the two identities. In answering a question posed by Foata, on the extension of the Euler-Mahonian distribution to type B , Adin, Brenti, and Roichman [2] came up with two pairs of statistics, the negative statistics (ndes, nmaj) and the flag statistics (fdes, fmaj). Both have the same bi-distribution and satisfy the generalized Carlitz identity P stat1 ( ) q stat2 ( ) X 2Bn t [k + 1]nq tk = , (1.51) (1 t)(t2 ; q 2 )n+1 k 0 where (stat1 , stat2 ) can be any of the two previous pairs. Chow and Gessel observed in [38] that comparing the left-hand sides of (1.16) and (1.15), the latter seems to be a natural q analogue of the former. In contrast, a comparison of the left-hand sides of (1.51) and of the following rational function for the type B Eulerian polynomial P desB ( ) X 2Bn t n k (2k + 1) t = , (1 t)n+1 k 0 does not enjoy such a property. This is why they proposed an alternative solution, by computing the joint distribution of the pair (desB , fmaj), where desB is the usual type B descent number (see (1.48)). This yields the following q -analogue having a q -version of the multiplicative factor (2k + 1)n , P desB ( ) q fmaj( ) X 2Bn t n k [2k + 1]q t = . (1.52) (t; q 2 )n+1 k 0 Now, we can state our generalizations. Without giving too many details, the main tool we use is an extension of a classical correspondence that goes back to Garsia and Gessel, between sequences and pairs made of a permutation and a partition. Here we need an extended version that encodes integer sequences f = (f1 , . . . , fn ) 2 Nn having a modular condition on the sum of their parts, i.e. such that f1 + · · · + fn ⌘ 0 mod p, with triplets f $ (g, , h), made of an element g 2 G(r, p, s, n), an integer partition with at most n parts, and an integer h in [0, s 1]. This bijection allows to express statistics on the sequence, like the maximum or module of f , in terms of statistics as descent number or flag major index on the corresponding group element. By using this bijection and some other technical computations to prove that main result of this section. Theorem 1.23. ( hr X ✓ tk [k + 1]qr/s + aq[k]qr/s s k 0 1 ) i ◆n aq = qp (1 P t)(1 des(g) q fmaj(g) acol(g) g2G(r,p,s,n) t . ts q r ) · · · (1 ts q (n 1)r )(1 tq nr/s ) Letting s = p = 1 in the previous result we h obtain i [28, Equation (8.1)]. Moreover, for r r a = 1 we have [k + 1]qr/s + q[k]qr/s [ s 1]q = s k + 1 and hence we obtain the following result. q 22 CHAPTER 1. GROUP ACTIONS AND STATISTICS Corollary 1.24 (Carlitz’s identity for G(r, p, s, n) with des). ( ) P des(g) q fmaj(g) in X hr g2G(r,p,s,n) t k t k+1 = s q (1 t)(1 ts q r ) · · · (1 ts q (n 1)r )(1 k 0 p tq nr/s ) . The special case with r = 2, p = s = 1 of Corollary 1.24 is the equation (1.52) of Chow–Gessel, and for p = s = 1 we obtain [39, Theorem 10 (iv)]. A simple modification of the same ideas lead to the generalization of other identities that use different flag-descents. Theorem 1.25. X ⇣ tk [Qr/s (k) + 1]qr/s + aq[r/s 1]aq · [Qr/s (k)]qr/s + aq mr/s+1) [Rr/s (k)]aq k 0 = (1 t)(1 P g2G(r,p,s,n) t ts q r ) · · · (1 fdes(g) q fmaj(g) acol(g) ts q (n 1)r/s ) · · · (1 ⌘n (1.53) , (1.54) tq nr/s ) where Qr/s (k) is determined by k = r/s · Qr/s (k) + Rr/s (k). A proof of this result can be done by paralleling that of Theorem 1.23. By letting a = 1 in Equation 1.53, one obtain a second Carlitz’s identity type, with flag-descents. Theorem 1.26 (Carlitz’s identity of G(r, p, s, n) with fdes). ⇢X k 0 k t [k + 1]nq = qp (1 t)(1 P g2G(r,p,s,n) t tr q r )(1 fdes(g) q fmaj(g) tr q 2r ) · · · (1 tr q (n 1)r )(1 r ts q nr s ) . For r = 2 and p = s = 1 we obtain the equation (1.51) from [2, Theorem 4.2], for r = s = 2 and p = 1 [21, Theorem 4.3], and for p = 1 [9, Theorem 11.2]. Note that in the case of G(r, n) we can show a stronger result that takes into account also the length function see [27, Theorem 5.1]. This can be obtained by following the same ideas. In G(r, p, n) and G(r, p, s, n) a good definition of length is still missing. 1.4.5 Multivariate generating functions In this section we use an extension of another classical bijection of Garsia and Gessel (see also [36, Theorem 8.3]) to compute new multivariate distributions for the groups G(r, p, s, n). Here we need to encode a particular subset of B(n), the set bipartite partitions having n ! (1) (1) (1) f1 f2 . . . fn parts (see Section 1.3.1). More precisely let f = be in B(n). We (2) (2) (2) f1 f2 . . . fn set B(r, s, 1, n) := {f 2 B(n) | 9 l 2 [s (1) 1] such that fi (2) + fi ⌘ lr/s mod r for all i 2 [n]}. There exists a bijection between B(r, s, 1, n) and the set of the 5-tuples (g, , µ, h, k), where g 2 G(r, 1, s, n), , µ 2 Pn , and h, k 2 [0, s 1]. As the bijection of the previous section, this map allows us to express some values on the bipartite partitions, using statistics of the corresponding group element. This allows us to find an analogous of Theorem 1.6 for the the full class of projective reflection groups G(r, p, s, n). We remind that G(r, p, s, n) is defined if and only if p|r , s|r , and sp|rn. In particular if r, p, s are fixed then G(r, p, s, n) is defined only if sp/GCD(sp, r) divides n. 1.4. GENERALIZATIONS TO OTHER PERMUTATION GROUPS ( 23 Theorem 1.27. Let r, p, s 2 N, such that s and p divide r . Let d = sp/GCD(sp, r). Then ◆) s 1✓ X X Y 1 k1 k2 t1 t2 = Rr/s (i) Rr/s (j) i j p r r 1 ua a q q d k1 ,k2 0 l=0 i2[0,k1 s ], j2[0,k2 s ]: u q1 1 2 1 2 i+j⌘l rs = X u n (1 n 0 : d|n mod r P des(g) des(g 1 ) fmaj(g) fmaj(g 1 ) col(g) col(g t2 q1 q2 a1 a2 g2G(r,p,s,n) t1 r r Q n n t1 )(1 t2 )(1 t1 q1 s )(1 t2 q2 s ) nj=11 (1 ts1 q1jr )(1 1) ts2 q2jr ) . We can now consider a specialization of this result. We set a1 = a2 = 1 in Theorem 1.27 ( ◆) s 1✓ X X Y 1 k1 k2 t1 t2 = 1 uq1i q2j k1 ,k2 0 l=0 i2[0,k r ], j2[0,k r ]: ud q p 1s i+j⌘l rs = X n 0 : d|n un (1 t1 )(1 2s mod r 1 P des(g) des(g 1 ) fmaj(g) fmaj(g 1 ) t2 q1 q2 g2G(r,p,s,n) t1 n rs n rs Qn 1 t2 )(1 t1 q1 )(1 t2 q2 ) j=1 (1 q1jr ts1 )(1 q2jr ts2 ) . Multiplying both sides of the previous identity by (1 t1 )(1 t2 ) and then taking the limit as t1 , t2 ! 1 we obtain (s 1 ) P fmaj(g) fmaj(g 1 ) X Y X q2 1 g2G(r,p,s,n) q1 n = u . r r Q j ns ns iq jr jr n 1 1 uq p (1 q )(1 q ) (1 q )(1 q ) d 1 2 u q l=0 i+j⌘lr/s n 0 : d|n 1 2 1 2 j=1 1 mod r (1.55) There is a nice algebraic interpretation of the previous identity that goes back to the work of Adin and Roichman [1]. We let Cp [x, y] be the subalgebra of the algebra of polynomials in 2n variables C[x, y] generated by 1 and the monomials whose total degrees in both the x’s and the y ’s variables is divided by p. Then we can observe that the factor 1 n rs n rs Qn 1 (1 q1 )(1 q2 ) j=1 (1 q1jr )(1 q2jr ) is the bivariate Hilbert series of the invariant algebra of the tensorial action of the group G(r, s, p, n) ⇥ G(r, s, p, n) (note the interchanging of the roles of p and s) on the ring of polynomials Cp [x, y]. Furthermore by [36, Corollary 8.6] we can deduce that P fmaj(g) fmaj(g 1 ) q2 g2G(r,p,s,n) q1 p G(r,s,p,n) Hq1 ,q2 (C [x, y] )= , (1.56) n rs n rs Qn 1 (1 q1 )(1 q2 ) j=1 (1 q1jr )(1 q2jr ) where Cp [x, y]G(r,s,p,n) denotes the diagonal invariant polynomials. We remark also that in all the expressions that can be obtained when r, p, s take particular values, the terms in the right-hand side always depend on the pair g and g 1 , (differently from (1.44) in case D ). We recall that this was the original motivation for the introduction of this flag major index (1.47). From Equations (1.55) and (1.56) we obtain the following generating function of the Hilbert series of the diagonal invariant algebras of the groups G(r, p, s, n). Corollary 1.28. Let r, p, s 2 N, such that s and p divide r . Let d = sp/GCD(sp, r). Then (p 1 ) X X Y 1 n p G(r,p,s,n) u Hq1 ,q2 C [x, y] = . i qj 1 uq s d 1 2 u q l=0 i+j⌘lr/s n 0 : d|n mod r 1 This identity was apparently known only in the case of the symmetric group, see Theorem 1.6. 24 CHAPTER 1. GROUP ACTIONS AND STATISTICS Chapter 2 Fully commutative elements in finite and affine Coxeter groups 2.1 Introduction Let W be a Coxeter group. An element w 2 W is said to be fully commutative if any reduced expression for w can be obtained from any other by transposing adjacent pairs of commuting generators. These elements were extensively studied by Stembridge in the series of papers [95]-[97]. He classified in [95] the irreducible Coxeter groups having a finite number of fully commutative elements; this was independently done by Graham in [58], and by Fan in [46] in the simply laced case. Stembridge also gives in [95] a useful characterizing property of full commutativity, by showing that reduced words for such an element can be viewed as the linear extensions of a heap, which is a certain kind of poset, originally defined by Viennot in [101], whose vertices are labeled by generators of W . In [97], Stembridge enumerates fully commutative elements for each of the previous finite cases, while connections with enriched P -partitions (the letter P stands here for “Poset”) and Schur’s Q-functions are studied in [96] in types B and D . The original context for the appearance of full commutativity is algebraic and relates to the generalized Temperley–Lieb algebras. The (type A) Temperley–Lieb algebra was first defined in [99], in the context of statistical mechanics. Later, it was realized by Jones in [70] that it is a quotient of the Iwahori–Hecke algebra of type A. This point of view was used by Fan in [46] in the simply laced case, and by Graham in [58] in general, to define a generalized Temperley–Lieb algebra for each Coxeter group. They proved that for any W , the associated generalized Temperley–Lieb algebra admits a linear basis indexed by the fully commutative elements of W . The set of fully commutative elements was also studied in connection to Kazhdan–Lusztig cells, which form a partition of the Coxeter group W . In [64], Green and Losonczy characterize when the set of fully commutative elements of a finite W is a union of double-sided cells. This was extended to affine types in the works [89, 90] of Shi. Other cells were defined and studied by Fan [47], and Fan and Green [48]. In this chapter we present results taken from three papers : [20] R. Biagioli, M. Bousquet-Mélou, F. Jouhet, and P. Nadeau. Length enumeration of fully commutative elements in Coxeter groups. In preparation, 2015. [25] R. Biagioli, F. Jouhet, and P. Nadeau. Fully commutative elements in finite and affine Coxeter groups. Monatsh. Math., 178 (2105), 1-37. 25 26 CHAPTER 2. FULLY COMMUTATIVE ELEMENTS [26] R. Biagioli, F. Jouhet, and P. Nadeau. Combinatorics of fully commutative involutions in classical Coxeter groups. Discrete Math., 338 (2015), 2242–2259. We will give a complete description, in terms of heaps, of fully commutative elements for each irreducible affine Coxeter group. From Psuch characterizations we will derive expressions for the generating functions W F C (q) := w2W F C q `(w) of the fully commutative elements according to the length, for all irreducible finite and affine Coxeter groups. The fundametal tool is a bijective encoding of a special class of fully commutatve elements, called alternating, by lattice walks. The main result shows that for any affine Coxeter group W , the growth sequence of W F C (the sequence of coefficients of W F C (q)) is ultimately periodic. 4 en 1 (n A 3) 4 6 e2 G 2.2 Fe4 4 4 en (n C en+1 (n B 2) e6 E e7 E 2) e n+2 (n D 2) e8 E Figure 2.1: Dynkin diagrams for all irreducible affine types. Fully commutative elements, heaps and walks Let (W, S) be a Coxeter system with Coxeter matrix M = (mst )s,t2S . We recall that the finite set of generators S is subject only to relations of the form (st)mst = 1, where mss = 1, and mst = mts 2, for s 6= t 2 S . If st has infinite order we set mst = 1. These relations can be rewritten more explicitly as s2 = 1 for all s 2 S , and sts | {z· ·}· = tst | {z· ·}·, mst mts where mst < 1. They are the so-called braid relations. When mst = 2, they are simply named commutation relations, st = ts. According to the well-known Matsumoto-Tits word property, any reduced expression of w can be obtained from any other using only braid relations (see for instance [30, Section 3.3]). The notion of full commutativity is a strengthening of this property. Definition 2.1. An element w is fully commutative (FC) if any reduced expression for w can be obtained from any other one by using only commutation relations. The following characterization of FC elements, originally due to Stembridge, is particularly useful in order to test wheter a given element is FC or not. Proposition 2.2 (Stembridge [95], Prop. 2.1). An element w 2 W is fully commutative if and only if for all s, t such that 3  mst < 1, there is no reduced expression for w that contains the factor sts | {z· ·}· . mst We let S ⇤ be the free monoid generated by S . The equivalence classes of the congruence on S ⇤ generated by the commutation relations are usually called commutation classes. By definition the set R(w) of reduced expressions of w forms a single commutation class; we will see that the concept of heap helps to capture the notion of full commutativity. 2.3. ALTERNATING HEAPS AND WALKS 27 Fix a word w = sa1 · · · sal in S ⇤ , and let be a finite graph with vertex set S . Define a partial ordering of the index set {1, . . . , l} as follows: set i j if i < j and {sai , saj } is an edge of , and extend by transitivity. We denote by Heap(w) this poset together with a labeling map ✏ : i 7! sai . Proposition 2.3 (Viennot, [101]). Let be a finite graph. The map w ! Heap(w) induces a bijection between -commutation classes of words and isomorphism classes of finite heaps on . When w is a fully commutative element, the heaps of its reduced words are all isomorphic by Proposition 2.3, so we can define Heap(w) := Heap(w). Heaps of this form are called FC heaps, and in this case the linear extensions of Heap(w) are in bijection with reduced words for w . Say that a chain i1 · · · im in a poset H is convex if the only elements u satisfying i1 u im are the elements ij of the chain. The next result gives an intrinsic characterization of FC heaps. Proposition 2.4 (Stembridge, [95], Proposition 3.3). Let be a Coxeter graph. A H is FC if and only if the following two conditions are verified: -heap (a) there is no convex chain i1 ··· imst in H such that ✏(i1 ) = ✏(i3 ) = · · · = s and ✏(i2 ) = ✏(i4 ) = · · · = t where 3  mst < 1; (b) there is no covering relation i j in H such that si = sj . In the figure below, we fix a (Coxeter) graph on the left, and we give two examples of words with the corresponding heaps. In the Hasse diagram of Heap(w), elements with the same labels will be drawn in the same column. The heap on the right is a FC heap, whereas the one on the left is not since it contains the convex chain with labels (s2 , s1 , s2 ) while ms1 s2 = 3. w1 = s 1 s 2 s 3 s 2 s 0 s 1 s 2 s 0 s 1 w2 = s 1 s 2 s 3 s 2 s 0 s 3 s 1 s 2 s 0 s 1 s1 s0 4 s0 5 s1 s2 s3 s0 s1 s2 s1 s1 s1 s2 s2 s0 s3 s0 s1 s2 s3 2.3 s2 s0 s1 s2 s2 s3 s3 s0 s1 s2 s3 Alternating heaps and walks Now we introduced a class of heaps which plays an important role for our enumeration purposes. In fact we will be able to encode them by lattice walks. The size |H| of a heap H is its cardinality. Given any subset I ⇢ S , we will note HI the subposet induced by all elements of H with labels in I . Definition 2.5. Consider a graph , and a -heap H . We say that H is alternating if for each edge {s, t} of , the chain H{s,t} has alternating labels s and t from bottom to top. A word w 2 S ⇤ is alternating if, for each edge {s, t}, the occurrences of s alternate with those of t. Clearly w is alternating if and only if Heap(w) is. In the rest of this section, we fix mv0 v1 , mv1 v2 , . . . , mvn 1 vn in the set {3, 4, . . .} [ {1} and we consider the Coxeter system (W, S) corresponding to the linear Dynkin diagram n of Figure 2.2. 28 CHAPTER 2. FULLY COMMUTATIVE ELEMENTS mvn mv0 v1 mv1 v2 v0 v1 v2 vn 1 1 vn vn Figure 2.2: The linear Dynkin diagram n. The advantage of having alternating heaps in the case of linear diagrams is that they have a nice encoding by walks as we explain now. We first need to introduce some notation about lattice paths. Definition 2.6 (Walks). A walk of length n is a sequence P = (P0 , P1 , . . . , Pn ) of points in N2 with its n steps in the set {(1, 1), (1, 1), (1, 0)}, such that P0 has abscissa 0 and all horizontal steps (1, 0) are labeled either by L or R. A walk is said to satisfy condition (⇤) if all horizontal steps of the form (i, 0) ! (i + 1, 0) have label L. The set of all walks of length n will be denoted by Gn , and the subset of walks starting and ending on the x-axis by Mn . To each family Fn ✓ Gn corresponds subfamilies Fn⇤ ✓ Fn consisting of those walks in Fn which satisfy the condition (⇤), and Fˇn ✓ Fn consisting of those walks which hit the x-axis at some point. The total Pn height ht of a walk is the sum of the heights of its points: if Pi = (i, hi ) then ht(P ) = i=0 hi . To each family Fn ✓ Gn we associate the series Fn (q) = X P 2Fn q ht(P ) , and F (x) = X Fn (q)xn . n 0 We now define a bijective encoding of alternating heaps by walks, which will be especially handy to compute generating functions in the next sections. The idea of the bijection is easy. If the number of labels vi in H increase (resp. decrease) by one with respect to the number of vi+1 , we draw an up (resp. down) step. If these numbers are equal we need to distinguished how the chain Hvi is situated with respect to Hvi+1 . There are two possible relative positions among those chains, hence we need to use two labels for the horizontal steps. This is not anymore needed if both vi and vi+1 don’t appear in H . This is the meaning of condition (*) for horizontal steps at level 0. An example is illustrated in Figure 2.3. Here the formal definition. Definition 2.7 (Map '). Let H be an alternating heap of type n . To each vertex vi of n we associate the point Pi = (i, |Hvi |). If |Hvi | = |Hvi+1 | > 0, we label the corresponding step by L (resp. R) if the lowest element of the chain H{vi ,vi+1 } has label vi+1 (resp. vi ). If |Hvi+1 | = |Hvi | = 0, we label the ith step by L. We define '(H) as the walk (P0 , P1 , . . . , Pn ) with its possible labels. Theorem 2.8. The map H 7! '(H) is a bijection between alternating heaps of type Gn⇤ . The size |H| of the heap is the total height of '(H). 2.4 e Types A and A n and en 1 . These In this section we study the case of FC elements in W of type An 1 and A correspond to the symmetric group and affine symmetric group, respectively. As such, FC elements were studied as they correspond to the so-called 321-avoiding permutations in both cases, and the length function corresponds to the number of (affine) inversions. e 2.4. TYPES A AND A 29 '(H) H := Heap(w) L R L 0 1 2 3 4 5 6 7 8 v0 v1 v2 v3 v4 v5 v6 v7 v8 Figure 2.3: The heap H corresponding to v8 v5 v1 v0 v7 v8 v6 v2 v7 v1 v0 v8 and its encoding by a walk. 2.4.1 the alternating word w = Type A As a consequence of Proposition 2.4 in type An 1, FC heaps are characterized by : (a) There is at most one occurrence of s1 (resp. sn 1 ). (b) For all i, the elements with labels si , si+1 form an alternating chain. In other words, irreducible FC heaps in type A are alternating and starts at ends with a single elements. The bijection in Theorem 2.8 gives us the following result. Theorem 2.9. FC elements of type An 1 are in bijection with walks in M⇤n . Consider the path '(H) 2 Gn⇤ image of any alternating heap. By adding to '(H) the unique initial step from (0, 0) to P1 and the unique last step from Pn 1 to (n, 0) we obtain a path in M⇤n . An example in figure below. H L R '(H) L L s1 s2 s10 s13 0 13 extra steps (initial and final) Since the size of the heap is equal an interpretation for P to the area of the path, we have P the generating function AF C (x) := n 1 xn AFn C1 (q), with AFn C1 (q) := w2An 1 q `(w) . Corollary 2.10. We have AFn C1 (q) = Mn⇤ (q), and equivalently AF C (x) = M ⇤ (x) 1. It is well known and easy to prove that there is a bijection from M⇤n to length 2n Dyck walks. It follows the well-known fact that AFn C1 has cardinality the nth Catalan number 2n 1 n+1 n . We also recall that Billey, Jockush and Stanley showed in [29] that FC elements are exactly the 321 avoiding permutations. By using that characterization, Barcucci et al. also proved an expression for AF C (x) as a quotient of q -Bessel type functions, which can be derived from the following proposition. Proposition 2.11. The generating function AF C (x) satisfies the following functional equation AF C (x) = x + xAF C (x) + qxAF C (x)(AF C (qx) + 1). (2.1) We can easily obtain this result by decomposing our Motzkin-type path at the first intersection with the x-axis as shown in the following pictures (with the corresponding equations). 30 CHAPTER 2. FULLY COMMUTATIVE ELEMENTS * = * + R M (x) = M ⇤ (x) + xM ⇤ (x)M (x), * = + L * + (2.2) * M ⇤ (x) = 1 + xM ⇤ (x) + qx2 M ⇤ (x)M (qx). 2.4.2 (2.3) e Type A en 1 has a well-known realization as group of affine permutations, The Coxeter system of type A i.e. bijective transformationsP : Z ! Z P such that (i + n) = (i) + n for all i 2 Z, with n n the normalization condition i=1 (i) = i=1 i. Under this characterization, Green in [59] showed that FC elements correspond to 321-avoiding permutations, which are the affine permutations with no i < j < k in Z satisfying (i) > (j) > (k). s0 s1 en A en A 1 sn 1 Hanusa and Jones in [67] used this characterization to compute the generating functions 1 (q). Here are the first ones: e2 (q) = 1 + 3q + 6q2 + 6q3 + 6q4 + · · · A e3 (q) = 1 + 4q + 10q 2 + 16q3 + 18q4 + 16q5 + 18q6 + · · · A e4 (q) = 1 + 5q + 15q 2 + 30q 3 + 45q 4 + 50q5 + 50q6 + 50q7 + 50q8 + 50q9 + · · · A e5 (q) = 1 + 6q + 21q 2 + 50q 3 + 90q 4 + 126q 5 + 146q 6 + +150q7 + 156q8 + 152q9 + 156q10 A + 150q11 + 158q12 + 150q13 + 156q14 + 152q15 + 156q16 + 150q17 + 158q18 + · · · en 1 (q) are ultimately periodic of period n, and derived They showed that the coefficients of A e a complicated expression for An 1 (q). FC permutations are classified and counted by dividing them first into long and short ones. Long permutations are easily counted and have a pleasing generating function, while the enumeration of short ones requires several pages resulting in a rather complicated generating function. Moreover they conjectured that the periodicity starts at 1 + d(n 1)/2eb(n + 1)/2c. We give now a new approach that allows us to give a much easier expression for the generating function, and from which the beginning the periodicity will automatically follow, confirming their conjecture. In Green’s paper [59] it is essentially proved that en 1 is fully commutative if and only if, in any Proposition 2.12. An element w of type A reduced decomposition of w , the occurrences of si and si+1 alternate for all i 2 {0, . . . , n 1}, where we set sn = s0 . We use this proposition to encode these elements as certain lattice paths. We represent en 1 by depicting all (alternating) chains H{s ,s } for i = 0, . . . , n 1. To be heaps of type A i i+1 able to represent these chains in a planar fashion, we duplicate the set of s0 -elements and use e 2.4. TYPES A AND A 31 s0 s1 s2 s3 s4 s5 s6 s7 s0 e7 . Figure 2.4: Representation of a FC heap of type A one copy for the depiction of the chain H{s0 ,s1 } and one copy for H{sn 1 ,s0 } . This can be seen in Figure 2.4, where the “drawn on a cylinder” representation on the right is a deformation of the first one which makes more visible its poset structure. We are not exactly in the case of Section 2.3 since the Coxeter graph is not linear. One can nonetheless define walks from the alternating heaps described in Proposition 2.12, as follows: en 1 and i = 0, . . . , n 1, draw a step from Pi = (i, |Hs |) given a FC heap H of type A i to Pi+1 = (i + 1, |Hsi+1 |) as in Definition 2.7 for '; here we set sn = s0 . This forms a eF C , we can set path '0 (H) of length n, with both P0 and Pn at height |Hs0 |. If w 2 A n 1 0 0 ' (w) := ' (Heap(w)) since we showed that all FC heaps are alternating. L R '0 (H) R H L s11 s0 s0 s1 s2 n 0 Define accordingly On⇤ as the P paths in Gn⇤ whose starting and ending points are at the 0 same height. Define also ht (P ) = ni=01 ht(Pi ), which corresponds to the area under P , and let On⇤ (q) be the generating functions with respect to ht0 of On⇤ . Finally, denote by En ✓ On⇤ the set of walks with all vertices at the same positive height, and all n steps with the same label (either L or R). Theorem 2.13. The map '0 : W F C ! On⇤ \ En is a bijection such that `(w) = ht0 ('0 (w)). eF C (q) = O⇤ (q) 2q n /(1 q n ). Now we have to Theorem 2.13 directly implies that A n n 1 ⇤ count walks in On , and to this end we decompose them according to the lowest height they reach as follows: * = >0 This gives the equation On⇤ (q) = q n Ǒn (q)/(1 + * q n ) + Ǒn⇤ (q), and therefore we obtain en Corollary 2.14. The generating function of FC elements of type A eFn C1 (q) = On⇤ (q) A 1 is 2q n q n (Ǒn (q) 2) = + Ǒn⇤ (q). 1 qn 1 qn (2.4) 32 CHAPTER 2. FULLY COMMUTATIVE ELEMENTS By looking at this expression we have already the periodicity. Let give now a much en 1 and of length `. By nicer proof. Let an` denote the number of FC elements of type A n ⇤ Theorem 2.13, a` is the number of walks in On \ En with area `. Assume ` is large enough so that paths of area ` will not have any horizontal step at height 0. In this case S : On⇤ (`) ! On⇤ (` + n) which shifts every vertex up by one unit (and preserves labels L, R) is a bijection. A simple calculation shows that `0 is the largest area for which there exists such a path in On⇤ with a horizontal step at height 0 (see illustration below). It is easy to show that an`0 = an`0 +n n when n is odd and an`0 = an`0 +n 2n when n is even. This gives an alternative proof of the periodicity and confirms the conjecture Hanusa and Jones regarding the exact beginning of periodicity. en 1 , the growth sequence (an )` 0 is ultimately periodic Theorem 2.15. Fix n > 0. In type A ` of period n. Moreover periodicity starts at length `0 + 1, where `0 = b n 2 1 cd n 2 1 e. (n odd) (n even) L/R L L n 0 n 0 We conclude by an evaluation of the mean value µAen 1 of the growth sequence, which is the arithmetic mean of the k first values of the growth sequence when k tends to infinity. Proposition 2.16. The mean value µAen 2.5 1 of (an` )` 0 is equal to 1 n 2n n 2 . Closed formulas for the generating functions The series given in Propositions 2.10 and 2.14 can be recursively computed thanks to some functional equations that can be obtained by decomposing the paths, see [25, Corollary 2.4]. The aim of this section is to show that there exist nice exact expressions for such generating series. We already know that Barcucci et al. found a nice q -Bessel type expression in type A. Actually there are several different approaches to obtain such formulas. For example in case A one can view heaps as parallelogram polyominoes and count them by area. In a work still in progress see [20], we found three counting techniques all based on our path encoding that can be generalized also to the other classical Coxeter types, and involutions. We show one of those, which is based on a classical “Inversion Lemma” due to Viennot (see e.g. [32, Theorem 2.1], [101]) that gives a general method to count heaps of segments. The explicit formulas are the following ones. Proposition 2.17. AF C (x) = 1 1 J(xq) xq J(x) and where J(x) is the following series J(x) = X n 0 We briefly explain the steps of the proof. eF C (x) = A x n ( x)n q ( 2 ) . (q; q)n (xq; q)n J 0 (x) J(x) X xn q n , 1 qn n 1 2.5. CLOSED FORMULAS FOR THE GENERATING FUNCTIONS 33 (1) By Theorem 2.9, FC elements in An 1 are in bijection with paths in M⇤n . We recall that under this bijection the length of the permutation becomes the total height of the path. (2) These paths are themselves in bijection with weighted half-pyramids of monomers and dimers (i.e. heaps having a unique maximal element that touches the y -axis). Instead of giving the precise definition of the bijection, we show the picture below, that should make clear how the bijection works. The monomers located at abscissa i have weight xq i , and dimers at abscissa [i, i + 1] a weight x2 q 2i+1 . The monomers come in two colors L and R, except those at abscissa 0, which come in only one color L, this is the translation of condition (*) on the paths. By using this weight assignment the length of a permutation is equal to the weight of the associated half-pyramid. L R R L L R (3) To compute the generating series of such half-pyramids we use a classical InversionLemma due to Viennot [101]. It states that this series is equal to the quotient between h0 (x), the signed generating function of trivial heaps of monomers and dimers that have no monomers or dimers at abscissa 0, and j(x), the signed generating function of all trivial heaps of monomers and dimers satisfying condition (*). Since heaps counted by h0 (x) are obtained by translating one step to the right any trivial heap, we have h0 (x) = h(xq), here h(x) is the signed generating function of trivial heaps of monomers and dimers. Then by observing that j(x) = h(xq) xj(xq) we conclude that 1 + AF C (x) = M ⇤ (x) = h0 (x) h(xq) j(xq) = =1+ . j(x) j(x) j(x) (4) So we have translated the problem to a computation of a generating series of trivial heaps of monomers and dimers satisfying the condition (*). There are analytic or bijective methods to show that j(x) = (xq; q)1 J(x) (2.5) from which the result in type A follows. e case. Indeed, we first have Now, we are able to adapt the same tools to the affine type A the following result concerning our walk generating functions O(x) and O⇤ (x). Recall that O(x) is the generating function for nonempty walks starting and ending at the same height 0, and O⇤ (x) corresponds to these walks with the (*) condition as above. From (2.4) we have X xn q n eF C (x) = O⇤ (x) 2 A . (2.6) 1 qn n 1 Following Viennot [101], all these walks are in bijection with marked pyramids of monomers and dimers (with or without the condition (*)), see Figure 2.5. We can prove that O(x) = x h0 (x) h(x) and O⇤ (x) = x j 0 (x) . j(x) (2.7) 34 CHAPTER 2. FULLY COMMUTATIVE ELEMENTS R L L R R L Figure 2.5: Bijection between walks and marked pyramids. Both formulas are proved in the same way, therefore we only give the details for the first one. First, recall the weights of monomers and dimers used in type A above; all our generating functions of heaps will be considered with these weights. Denote by P (x) the generating function of pyramids marked on their (unique) maximum (which can be either a marked monomer, labelled L or R, or a dimer marked in two ways). We also denote by E(x) the generating function of heaps of monomers labelled L or R and dimers, and by Em (x) the same generating function for marked heaps. By our choice of weights, we immediately have Em (x) = xE 0 (x). Moreover, thanks to Viennot [101], we also have on the one hand E(x) = 1/h(x), and on the other hand, by pushing down the marked piece (see Figure 2.6): P (x) Em (x) = P (x) ⇥ E(x) = . h(x) ! Figure 2.6: Decomposition of a marked heap. Now we can use the correspondence between our walks counted by O(x) and pyramids of monomers L, R and dimers, with the necessary condition that the unique maximal piece has to be marked, in order to take into account the starting (and ending) height of the initial walk. Summarizing one gets O(x) = P (x) = xE 0 (x)h(x), which is equivalent to our claimed expression in (2.7). Now, the result follows by (2.5) and (2.6). 2.6 e C, e D e Classical affine types B, en , B en+1 , and D e n+2 thanks to their heaps. As We are able to classify FC elements in types C en 1 and in particular could be perhaps expected, the problem is much subtler than in type A 2.6. OTHER CLASSICAL AFFINE AND EXCEPTIONAL TYPES 35 sk sj sj en in families (ALT), (ZZ), (LP), (LRP). Figure 2.7: Examples of heaps of type C several kinds of elements appear. The pleasant part about our point of view is that we are able to formulate our proof so that the same one essentially works for all three cases. Without giving the precise formal definition, let briefly describe the five families that en into disjoint sets. There are two infinite families : partition the set FC elements of type C the alternating heaps (ALT) which are alternating heaps in the sense of Definition 2.5, and the set (ZZ) of zigzags heaps whose associated word is a finite factor of the infinite word (ts1 s2 · · · sn 1 usn 1 · · · s2 s1 )1 . Then there are three finite families of heaps (RP), (LP), (LRP), called respectively, right, left, or left-right peaks, which start, end, or start and end with a “peak” and whose “interior” is made by an alternating heap. The pictures in Figure 2.7 should give an idea of what we mean by peak and alternating interior part. We can now state the main theorem of this section. en ). A heap of type C en is fully commuTheorem 2.18 (Classification of FC heaps of type C tative if and only if it belongs to one of the five families (ALT), (ZZ), (LP), (RP), (LRP). en+1 and D e n+2 starting from It is possible to obtain a classification of FC heaps in type B e that in type Cn , through certain operations of substitution. The result can be summarized en+1 always comes from a FC heap of type C en in which tas follows: a FC heap of type B e n+2 always elements are replaced by elements labeled t1 , t2 or t1 t2 , while a FC heap of type D en in which additionally u-elements are replaced by elements comes from a FC heap of type C labeled u1 , u2 or u1 u2 . In both cases, we also obtain 5 disjoint families of FC elements. t1 t2 s1 en+1 B t1 4 sn 1 u t2 s1 e n+2 D u1 sn 1 u2 en , B en+1 and We can use the previous descriptions of FC heaps in classical affine types C F C e Dn+2 to compute explicit expressions for the generating functions W (q) in each case, and to obtain information about their growth sequences. Similar results can be obtained for the exceptional families. Without giving the precise statements of the corresponding generating functions, we state our main result here. Theorem 2.19. Let W be a Coxeter group of irreducible affine type. Then the growth sequence of W F C is ultimately periodic. The periods are summarized in the following table e F C are finite sets): ( Fe4F C , E 8 Affine Type Periodicity en A n 1 en en+1 e n+2 E e6 E e7 G e 2 Fe4 , E e8 C B D n + 1 (n + 1)(2n + 1) n + 1 4 9 5 1 The periods in the above table are not always the minimal periods. For instance, for type en 1 , it was shown by Hanusa and Jones in [67] that, when n is prime, the corresponding A growth sequence (an` )` 0 is eventually constant. In the work [71] the minimal periods for all en 1 , it is shown that the minimal period of cases are determined. In particular, in type A n m (a` )` 0 is n unless n is a prime power p , in which case the minimal period is pm 1 . This generalizes the aforementioned result. 36 2.7 CHAPTER 2. FULLY COMMUTATIVE ELEMENTS Involutions In this section we focus on FC involutions for all classical Coxeter groups. As explained by Stembridge in [97], a FC element w is an involution if and only if its commutation class R(w) is palindromic, meaning that it includes the mirror image of some (equivalently, all) of its members. Now let us reformulate this property on the language of heaps. Let us point out a simple operation on heaps: if (H, , ✏) is a heap, then its dual is (H, , ✏), which is the heap with the inverse order and where the labels are kept the same. We will say that a heap is self-dual if it is isomorphic to its dual. We have the following characterization. Lemma 2.20. Let W be a Coxeter group with Dynkin diagram . A fully commutative element w 2 W is an involution if and only if Heap(w) is self-dual. We label the Dynkin diagram in type B and D in the opposite usual way, to take into account the definition of major index introduced by Reiner in [86] in our computations. sn+1 4 s1 s2 An sn 1 1 s1 s2 sn 1 Bn sn s1 Dn+1 sn 1 sn Figure 2.8: Different indexation for classical irreducible finite types. en+1 and D e n+2 to the By restricting the classification Theorem 2.18 and its analogue for B involutions in finite classical types An 1 , Bn and Dn+1 we have the following result. We just need to note that due to the different indexation of the Dynkin diagrams, left-peaks become now right-peaks. Proposition 2.21 (Classification of FC involutions in classical types). A FC element w 2 An 1 is an involution if and only if Heap(w) is a self-dual alternating heap. Moreover, a FC element w 2 Bn ( resp. w 2 Dn+1 ) is an involution if and only if Heap(w) is either a self-dual alternating heap of type Bn ( resp. Dn+1 ) or a self-dual right-peak of type Bn ( resp. Dn+1 ). sj sn Figure 2.9: A self-dual right-peak of type Bn . 2.7.1 Bijective encoding of alternating self-dual heaps As in the previous sections, we want to use lattice walks to enumerate FC involutions, so the idea is to use the same encoding for alternating heaps. We need to understand how the bijection ' defined in Definition 2.7 restricts to self-dual alternating heaps. It is easy to see that in each of such heaps the number of occurrences of labels si is equal to ±1 the number of labels si+1 , unless there are no labels si . This means that the paths we obtain are not Motzkin type paths, but actually Dyck type paths where are allowed horizontal steps at height 0. To be precise we define Ḡn⇤ the set of walks P = (P0 , P1 , . . . , Pn ) of length n with steps in 2.7. INVOLUTIONS 37 the set {(1, 1), (1, 1), (1, 0)}, such that P0 has abscissa 0 and all horizontal steps (1, 0) can only occur between points on the x-axis. We also denote M̄n the subset of paths starting and ending on the x-axes. As usual if denotes the linear Dynkin diagram in Figure 2.2 we have that the map H 7! '(H) is a bijection between self-dual alternating heaps of type n and Ḡn⇤ . The size |H| of the heap is the total height of '(H). H '(H) s10 s11 u11 s1 s2 11 0 e11 and its associated walk. Figure 2.10: The heap of a FC involution in C There are not surprises about the enumeration with respect to the length function. As for the case of whole FC elements, by using the same techniques of path encoding, we are able to express the generating functions and to compute them usingP functional equations (obtained by decomposing the paths). For example if we set ĀF C (x) = n 1 ĀFn C1 (q)xn then it is easy to see that M̄ (x) ĀF C (x) = 1. 1 M̄ (x) Moreover generalizing our methods in Section 2.5 we obtain the following exact expressions e for it and also for its analogue in affine type A. Proposition 2.22. ĀF C (x) = J (xq) + xqJ (xq 2 ) J (x) xJ (xq) and where J (x) is the following series J (x) := ïF C (x) = X ( x2 )n q n(2n (q 2 ; q 2 )n x J 0 (x) xqJ 0 (xq) J (xq) , J (x) xJ (xq) 1) . n 0 In all classical affine cases, we computed the generating functions W̄ F C (q), and deduced that the corresponding growth sequences are ultimately periodic. More precisely, we have Theorem 2.23. Let W be a Coxeter group of classical affine type. Then the growth sequence of W̄ F C is ultimately periodic. The periods are summarized in the following table : Affine Type Periodicity en A 1 en en+1 e n+2 (n even) C B D n 2n + 2 (2n + 1)(2n + 2) 2n + 2 en (if n is odd, the number of fully commutative involutions in A 2.7.2 1 is finite.) Enumeration with respect to the major index What is more interesting for FC involutions is their enumeration with respect to the major index in the classical finite types. Recently Barnabei et al. [13] obtained this nice q -analogue  X n q maj(w) = , (2.8) bn/2c q FC w2Ān 1 38 CHAPTER 2. FULLY COMMUTATIVE ELEMENTS by using the 321-avoiding characterization of such elements, the Robinson-Schensted correspondence, and a connection to integer partitions. A non-bijective proof of this result, using the principal specialization of Schur functions, has also been given by Stanley, and a third one has been found by Dahlberg and Sagan (see [13, §6]). As a consequence of our approach in terms of lattice paths, we are able to enumerate, in types A, B , and D , FC involutions according to the major index. We will recover the result of Barnabei et al.. The advantage of our point of view is that it naturally extends to types B and D for which major indices can be defined, whereas the use of Stembridge’s pattern-avoiding characterizations [97, Theorems 5.1 and 10.1] seems hard to handle. In type B , our result can for instance be written as follows X q maj(w) = n X h=1 FC w2B̄n q h h 1 X h i=0 1 i + q  n , bn/2c q (2.9) where B̄nF CPis the set of FC involutions in Bn , and maj is the major index defined as maj(w) := si 2Des(w) i. This notion of major index was used by Reiner in [86], and this is why we used a different indexation of the Dynkin diagrams of Bn and Dn+1 . It will be an interesting problem to compute the generating function with respect to the flag major index of Adin and Roichman [1]. We give just an idea of the proof in type A, and explain how it generalizes to the other types. Recall from Proposition 2.21 that each FC involution w 2 ĀFn C1 corresponds bijectively to a self-dual alternating heap H = Heap(w), which is itself in one-to-one correspondence with a walk in M̄⇤n . Note that i 2 DesR (w) (the right descent set of w ) if and only if there exists in the poset H a maximum element labeled si . In the path encoding this corresponds to a peak (i.e. an ascending step followed by a descending one) at coordinates (i, |Hsi |). Therefore the position i of such a descent is equal to the number of steps from the origin to this peak. Now, we use first a known bijection that transform this walk in a sort of Dyck type walk, which is itself in bijection with an integer partition fitting inside a rectangle [0, bk/2c] ⇥ [0 ⇥ dk/2e]. From this the result follows by using the well-known interpretation of the q -binomial coefficient. A pictorial illustration of these bijections is given in Figure 2.11. 8 2 10 2 8 10 2 M⇤13 (4, 6) (3, 5) (0, 2) ¯ 2 ⇧13 Figure 2.11: An example of the walk-to-partition bijection. The proofs in type B and D are based on analogous computations. For example FC involutions in Bn are either self-dual alternating heap or right-peaks. The latter can bijectively encoded by walks in M̄⇤n with less than n horizontal steps, so the An 1 argument can be applied. The remaining heaps are the self-dual alternating ones, which are in one-to-one correspondence with walks in Ḡn⇤ , starting on the x-axes and ending at positive heigh. These 2.8. APPLICATIONS AND FURTHER QUESTIONS 39 are in bijection with integers partitions whose first hook length is smaller or equal than n, from which the generating function (2.9) can be obtained. 2.8 Applications and further questions In this section we first give a direct application of our results to the growth of Temperley–Lieb algebras. Then we show in Section 2.8.2 how to simplify, by using our approach in terms of heaps, a result of Fan–Green about cells in Temperley–Lieb algebras in type Ã. Finally a few questions which we believe deserve further study are listed in Section 2.8.3. 2.8.1 Growth of Temperley–Lieb algebras In this section we give a direct application of our results to the growth of Temperley–Lieb algebras. Consider the ring A = Z[q, q 1 ]; here we use q instead of q to avoid confusion with the variable in our generating functions. For W a Coxeter group with Coxeter matrix M = (mst )s,t2S , the associated Hecke algebra H(W ) is given by generators Ts and relations Ts2 = (q 1)Ts + q1 Ts Tt Ts · · · = Tt Ts Tt · · · | {z } | {z } mst mst for s 2 S; for s 6= t 2 S. For any w 2 W , define Tw 2 H(W ) by picking any reduced decomposition si1 · · · sim for w and setting Tw := Tsi1 · · · Tsim , and Te = 1. These elements Tw then form a basis of H(W ) (see for instance [69]). The generalized Temperley–Lieb algebra TL(W ) is defined as the quotient of H(W ) by the ideal generated by the elements X Tw , if mst 3, w2Ws,t where Ws,t is the (dihedral) subgroup generated by s and t. For instance if mst = 3 the element is Ts Tt Ts + Ts Tt + Tt Ts + Tt + Ts + 1. Let bw be the image of Tw in TL(W ). Then the elements bw , for w 2 W F C , form a basis of TL(W ) (see [58, Theorem 6.2]). Consider now the natural filtration TL(W )0 ⇢ TL(W )1 ⇢ · · · of TL(W ), where TL(W )` is the linear span in TL(W ) of all products bsi1 · · · bsik with k  `. A linear basis for TL(W )` is clearly given by (bw )w , where w lies in the set of all FC elements of length at most `. Let the growth of TL(W ) be GW : ` 7! dim TL(W )` , so that GW (`) is the number of FC elements of length at most ` in W . Now let W be an irreducible affine group with infinitely many FC elements. Recall that by definition the mean value µW is the arithmetic mean of the values over a period. We have the following result. Theorem 2.24. For any affine Coxeter group W with infinitely many FC elements, the algebra TL(W ) has linear growth: one has the asymptotic equivalent GW (`) ⇠ µW ` when ` tends to infinity. In the simply laced case, it was also already noticed in [102] that the growth is linear. Define the nil Temperley–Lieb algebra nTL(W ) as the graded algebra associated to TL(W ): by definition, its `th grade component is given by TL(W )` / TL(W )` 1 , and the multiplication is inherited from TL(W ). It is easily seen to have the presentation with generators us 40 CHAPTER 2. FULLY COMMUTATIVE ELEMENTS and relations 8 > u2 = 0; > > s < us ut us · · · = 0 if mst 3; | {z } > mst > > : us ut = ut us if mst = 2. This algebra seems to have been studied only for type An 1 by Fomin and Greene in [52] en 1 by Postnikov in [84]. Either from its definition or the presentation, one and for type A sees that the `th graded component of nTL(W ) has a basis (uw ) indexed by FC element of length `, and we have the following consequence. Corollary 2.25. The Hilbert series of nTL(W ) is equal to W F C (q). Now for any W , nTL(W ) is a finitely presented, graded algebra: for any affine or finite type, we used the GAP package GBNP to compute, for any length `, a basis of all components of nTL(W ) up to dimension `; equivalently, it gives us access to all FC elements up to Coxeter length `. 2.8.2 e Cells for FC elements in type A The aim of this section is to illustrate how the representation of FC elements as heaps can be en 1 ). useful in other ways. Here we focus on the generalized Temperley–Lieb algebra TL(A We will use our representation of heaps drawn on a cylinder corresponding to FC elements of en 1 , see Figure 2.4. type A Fan and Green [48] gave a presentation for such algebra, with generators Esi for i 2 {0, 1, . . . , n 1} and relations: 8 2 > < Esi = Esi , Esi Esj Esi = Esi if i = j ± 1 modulo n, > : Esi Esj = Esj Esi if i 6= j ± 1 modulo n. Note that the first relation involves usually an extra parameter ↵, but this has no incidence en 1 ) on the results we will describe. As remarked in the previous section the algebra TL(A en 1 : one can define unambiguously has a linear basis (Ew ) indexed by FC elements in A Ew = Esi1 · · · Esik where si1 · · · sik is any reduced expression of the FC element w . Using this algebra, there are natural relations on the set of FC elements. en Definition 2.26. Let w, w0 be FC elements of type A R 1. R One writes w 6 w0 if there exists R R a FC element x such that Ew0 = Ew Ex , and w ⇠ w0 if w 6 w0 and w0 6 w . R R Since 6 is a preorder, ⇠ is an equivalence relation whose classes are called right cells. These are analogues of the famous Kazhdan–Lusztig cells which give representations of the en 1 ). Hecke algebras, in the arguably simpler context of the Temperley–Lieb algebra TL(A Theorem 2.27. Each right cell contains at most one involution. Right cells with no involution occur only when n is even. In the sequel we wish to show how the use of heaps can illustrate this result and make it more precise. To this aim we first describe in terms of heaps the so-called reduction of FC elements used in [48]. en 1 , and si 2 DesR (w). Definition 2.28 (Reduction). Let w be a FC element of type A Then w can be reduced to wsi if at least one of si 1 , si+1 belongs to DesR (wsi ). We will R write w ! wsi . 2.8. APPLICATIONS AND FURTHER QUESTIONS 41 R Reduction is easy to illustrate on heaps: w ! wsi if si labels a maximal element in Heap(w) and if either si 1 or si+1 labels a maximal element in Heap(wsi ) := Heap(w) \ top {stop is the maximal element of the chain Hsi . We refer the reader to Figure 2.12 i }, where si for a chain of successive reductions. Figure 2.12: Successive reductions. Reduction is useful to investigate right cells. In fact is not hard to see that if w reduces R R to wsi , then both belong to the same right cell,in symbols, w ! wsi implies w ⇠ wsi . A FC element w is called irreducible if it can not be reduced to wsi for any i. It is relatively easy to give a characterization of the heaps of such elements. Recall that the support of the FC element w is the set of si , i 2 {0, . . . , n 1}, which occur in a reduced decomposition of w . Proposition 2.29. A FC element w is irreducible if and only if its heap satisfies stop > i top top top top stop < s > s < . . . s < s for all i, m satisfying: i+1 i+2 i+3 i+2m 1 i+2m • if w has full support, then n is even, m = n/2 and i = 0 or 1, • otherwise {i, i + 1, . . . , i + 2m} is any maximal (cyclic) interval of the support of w . For w irreducible, we now define a particular subset of elements in Heap(w): this will allow us to connect irreducible heaps with FC involutions. If the support of w is not full, then we select all maximal elements in the heap. This is illustrated in Figure 2.13, left. Figure 2.13: Heaps of irreducible elements. Otherwise, n is even by the proposition. Define R0 := s0 s2 · · · sn 2 and R1 := s1 s3 · · · sn 1 . Then select in Heap(w) the upper ideal isomorphic to the heap of R✏ R1 ✏ R✏ R1 ✏ · · · R R1 with the maximal number of factors, where ✏, 2 {0, 1}. Two such examples are illustrated in Figure 2.13, middle and right, the one in the middle (resp. right) having an odd (resp. even) number of such factors. In each case, denote by H top the subset of selected elements and H bottom the complement in Heap(w). 42 CHAPTER 2. FULLY COMMUTATIVE ELEMENTS Proposition 2.30 ([48]). Distinct irreducible elements belong to different right cells. We will not prove this proposition which is arguably the crucial part of the argument in [48]. An immediate consequence is that each right cell contains precisely one irreducible element. To obtain Theorem 2.27, we need to relate irreducible elements to involutions. One easily constructs an irreducible element from a FC involution by reducing it repeatedly. It can be seen in this case that the process is reversible: given such an irreducible element with heap H , take the dual of H bottom and add it as an upper ideal to H , as illustrated in Figure 2.14. Figure 2.14: Heaps of FC involutions corresponding to irreducible elements. Right cells with no involution are now easy to characterize: those are the ones whose unique irreducible element has full support and a top part H top with an even number of factors R0 , R1 : see for example the right heap in Figure 2.13. Indeed the inverse process does not produce a FC heap in this case. 2.8.3 Further questions We end this chapter by listing some questions. • Minuscule elements An interesting subset of FC elements that deserves to be studied is the set of minuscule elements, which are linked to representation theory. These elements were also studied by Stembridge in [98] who characterized their heaps by local conditions extending Proposition 2.4. By using our description of FC heaps in the affine types, one can recognize among them which ones correspond to minuscule heaps and then study their enumerative properties. •Other statistics It would be interesting to explore other statistics on the sets W F C which can be studied naturally on heaps. An example would be the sets of left and right descents, which are defined for any Coxeter group: for a FC element w , these descents correspond to the minimal and maximal elements of Heap(w). 2.8. APPLICATIONS AND FURTHER QUESTIONS 43 • Diagram representations of Temperley–Lieb algebras We recall that for a given Coxeter group W , the FC elements index naturally a basis of the (generalized) Temperley–Lieb algebra TL(W ). On the other hand the usual Temperley– Lieb algebra of type A is known to have a faithful representation as a diagram algebra. Such representations have since been extended to other types: B and D in [63], H in [61], E e in [48], C e in [43, 44], which are infinite in [62], which are finite dimensional algebras; A dimensional algebras. The procedure to obtain such a faithful representation is more or less always the same in the previously cited works: (1) Define a set D of (decorated) diagrams and a way to multiply them e concatenation procedure; (2) determine a subset in D of elementary diagrams indexed by some Type G 2 by S , which satisfy the relations of TL(W ); (3) Determine explicitly the subspace generated by the elementary diagrams, say D0 ; (4) Prove that the surjective morphism TL(W ) ! D0 thus obtained is injective. It is these steps (3) and (4) that can be greatly simplified thanks to our global approach to fully commutative elements. We plan to extend such diagram algebras to the remaining e and D e. classical affine types B •Alcoves Affine Coxeter groups get their name from the geometric representation of Coxeter groups; we refer to [69] for details. In brief, elements of W correspond bijectively to the regions (called alcoves) of a certain regular tiling of Rn . If C0 is the alcove of the identity of W and is fixed, then the length of w corresponds to the distance from C0 to C (here the distance is measured in the minimum number of pairs of adjacent alcoves that one must encounter between C0 and C , where two alcoves are adjacent if they are separated by a single hyperplane). e 2 are depicted in Figure 2.15, the colored ones correThe alcoves for the affine group G sponding to FC elements. It is easy to give a geometric criterion for the location of alcoves for FC elements. It should be possible to use these geometric representations to obtain alternative proofs of our results. For instance, understanding the periodicity of the growth sequence from this point of view would be very interesting, especially if this can be done in a uniform manner. C0 e2 . Figure 2.15: Fully commutative alcoves in type G 44 CHAPTER 2. FULLY COMMUTATIVE ELEMENTS Chapter 3 Depth in classical Coxeter groups 3.1 Introduction There is a simple recursive algorithm to sort permutations due to Knuth, called straight selection sort. Given a permutation, the algorithm finds its largest misplaced entry and moves it to its correct final position using a single transposition, and then repeats until the permutation is entirely sorted. For example if w = 2537146, we have (47) (46) (25) (12) 2537146 ! 2536147 ! 2534167 ! 2134567 ! 1234567 This algorithm gives the minimal length of an expression for a permutation as a product of transpositions, known as the absolute length and denoted ab. In the previous example, we obtain w = 2537146 = (12)(25)(46)(47), and so ab(w) = 4. The cost of this algorithm is the sum of the distances between the positions transposed at each step. So in the example above, this would be (7 4) + (6 4) + (5 2) + (2 1) = 9. This cost function was studied by Petersen [82], who called it the sorting index, and showed that is a Mahonian statistic on the symmetric group. While straight selection sort optimizes the number of transpositions needed to sort a permutation, it does not necessarily optimize the cost. Petersen and Tenner characterize in [83] the minimum cost to sort a permutation using transpositions, and they call it depth, denoted dp. They show that the depth is equal to the sum of the sizes of exceedances. One optimal algorithm is to always swap the largest exceedance with the smallest value to its right (see Section 3.2). For w = 2537146, we have (45) (56) (67) (24) (45) (12) 2537146 ! 2531746 ! 2531476 ! 2531467 ! 2135467 ! 2134567 ! 1234567 So dp(w) = 7, as the sum of sizes of exceedances of w which is 1 + 3 + 0 + 3 + 0 + 0 + 0 = 7. It is natural to study depth in the general context of Coxeter groups. In fact, the depth of w 2 W can be interpreted as the minimum cost of a weighted path going from the identity to w , in the unordered Bruhat graph of W where the edges have prescribed weights. In this chapter we study the depth statistic as introduced by Petersen and Tenner in [83], with the purpose to characterize this kind of minimum sorting measure in the general context of Coxeter groups. The presented results resume those of the preprint: [9] E. Bagno, R. Biagioli, M. Novick, and A. Woo. Depth in classical Coxeter groups. arXiv:1507.01180, preprint july 2015. 45 46 CHAPTER 3. DEPTH IN CLASSICAL COXETER GROUPS The set T := {wsw 1 | s 2 S, w 2 W } is known as the set of reflections of W . We recall that the absolute length ab(w) is the minimal number of reflections t 2 T needed to express w , so ab(w) := min{r 2 N | w = t1 · · · tr for some t1 , . . . , tr 2 T }. (3.1) Let = + [ be the root system for (W, S), with ⇧ ⇢ dp( ) of a positive root 2 + is defined as dp( ) := min{r | s1 · · · sr ( ) 2 the simple roots. The depth , sj 2 S}. It is easy to see that dp( ) = 1 if and only if 2 ⇧. As a function on the set of roots, depth is also the rank function for the root poset of a Coxeter group, as developed in [30, §4]. Now, if we denote by t the reflection corresponding to the positive root , Petersen and Tenner introduced [83] a new statistic, also called depth and denoted dp(w) for any w 2 W , by defining ( r ) X dp(w) := min dp( i ) | w = t 1 · · · t r , t i 2 T . i=1 Petersen and Tenner further observe that depth always lies between length and absolute length. For each positive root , one has dp(t ) = dp( ) = Hence, by definition, ab(w)  `(t ) + 1 . 2 (3.2) ab(w) + `(w)  dp(w)  `(w). 2 Petersen and Tenner focus mainly on the case where (W, S) is the symmetric group (with S being the adjacent transpositions). In particular, they provide the following: • A formula for depth in terms of the sizes of exceedances. To be specific, they show X dp(w) = (w(i) i). (3.3) w(i)>i • The maximum depth for an element in Sn (for each fixed n) and a characterization of the permutations that achieve this depth. (Both were also previously found by Diaconis and Graham [41] starting from the above formula, which they called the total displacement of a permutation.) • An algorithm that, given w 2 W , finds an expression w = t1 · · · tr that realizes the depth of w . • Characterizations both of the permutations w such that dp(w) = `(w) and of the permutations such that dp(w) = ab(w). In the next sections we provide analogous results for the other infinite families of finite Coxeter groups, namely the group Bn of signed permutations and its subgroup Dn of even signed permutations. (The dihedral groups were also treated in [83].) In each case, we give a formula for depth that, like those in (3.3), is in terms of sizes of exceedances, except we need to introduce a small adjustment factor that can be explicitly calculated from the interaction of the signs and the sum decomposition of the underlying unsigned permutation. Using our formulas, we can find the maximum depth for any element in Bn or Dn for a given n and describe the signed permutations that achieve this maximum. 3.2. TYPE B 47 Furthermore, we give algorithms P that, given an element w , produce reflections t1 , . . . , tr such that w = t1 · · · tr and dp(w) = ri=1 dp(tr ). Our algorithms differ from that of Petersen and Tenner in several respects that are worth mentioning. First, their algorithm produces an expression with r = ab(w) reflections. This turns out to be impossible in types B and D ; indeed there are elements w in both Bn and Dn where no factorization of w into ab(w) reflections realizes the depth. Second, both their algorithm and ours always produce an expression that is realized by a strictly increasing path in Bruhat order. To be precise, if we let wi = t1 · · · ti for all i with 1  i  r , then `(wi ) `(wi 1 ) for all i, 2  i  r . However, our algorithms have a stronger property; we always produce a factorization for which P `(wi ) = `(wi 1 ) + `(ti ), and hence `(w) = ri=1 `(ti ). In other words, our factorization of w into reflections is reduced. Finally, the algorithm of Petersen and Tenner relies on both left and right multiplication. Given a permutation w , their algorithm produces either the reflection t1 or the reflection tr , and then their algorithm recursively finds a decomposition for either t1 w or wtr respectively. Our algorithms use only right multiplication. Given w , we always produce the reflection tr and then recursively apply our algorithm to wtr . In particular, this implies that the depth can be realized by a strictly increasing path in the right weak order, which, as we recall, is the partial order on W that is the transitive closure of the relation where, for any w 2 W and s 2 S , w <R ws if `(w) + 1 = `(ws). (See [30, §3.1] for further details). Using the property that depth is always realized by a reduced factorization into reflections, it is easy to characterize the elements w with `(w) = dp(w) and those with ab(w) = dp(w). 3.2 Type B To state our formula for depth, we need the notion of an indecomposable element and some associated definitions. These are standard definitions for permutations, but as far as we are aware, they have not been previously extended to signed permutations. Definition 3.1. Let u 2 Bk , v 2 Bn k . Define the direct sum of u and v by: ⇢ u(i) i 2 {1, . . . , k}; (u v)(i) := sign(v(i k))(|v(i k)| + k) i 2 {k + 1, . . . , k + l}. A signed permutation w 2 Bn is decomposable if it can be expressed as a nontrivial (meaning 1  k  n 1) direct sum of signed permutations and indecomposable otherwise. Every signed permutation has a unique expression as the direct sum of indecomposable signed permutations w = w1 · · · wk . This expression is called the type B decomposition of w . The indecomposable pieces are called the type B blocks (or simply blocks). Definition 3.2. Given a signed permutation w = w1 · · · wk 2 Bn , we define the Boddness of w , denoted by oB (w), as the number of blocks in the sum decomposition with an odd number of negative entries. For example, if we let w = [4, 3̄, 1, 2̄, 7, 5, 6̄, 9, 8̄], then w is decomposable with w = w2 w3 , where the blocks are w1 = [4, 3̄, 1, 2̄], w2 = [3, 1, 2̄], and w3 = [2, 1̄]; moreover B o (w) = 2. On the other hand, w0 = [8̄, 1, 9, 3, 5, 2, 6̄, 4, 7] is indecomposable with oB (w0 ) = 0. The negative identity [1̄, . . . , n̄] is the oddest element in Bn , with oddness n. w1 Theorem 3.3. Let w 2 Bn . Then dp(w) = X {i2[n]|w(i)>i} (w(i) i) + X i2Neg(w) |w(i)| + oB (w) neg(w) 2 . (3.4) 48 CHAPTER 3. DEPTH IN CLASSICAL COXETER GROUPS Using our formula, we can easily show: Corollary 3.4. For each w 2 Bn we have dp(w)  w = [1̄, 2̄, . . . , n̄]. n+1 2 , with equality if and only if Petersen and Tenner ask if dp(w) can always be realized by a product of ab(w) reflections. The following example shows that this is impossible in type B . Example 3.5. Let w = [4̄, 2̄, 3̄, 1̄] 2 B4 . Then dp(w) = 8, since w is indecomposable and oB (w) = 0. However, ab(w) = 3, and there are essentially only two ways to write w as the product of 3 reflections. One is to write w as the product of t1̄4 = [4̄, 2, 3, 1̄], t2̄2 = [1, 2̄, 3, 4], and t3̄3 = [1, 2, 3̄, 4] in some order. (These reflections pairwise commute.) The sum of the depths of these reflections is 9 > 8. One can also write w as the product of t1̄4 = [4̄, 2, 3, 1̄], t2̄3 = [1, 3̄, 2̄, 4], and t23 = [1, 3, 2, 4] in some order. The sum of the depths of these reflections is also 9 > 8. However, our algorithm always produces a factorization of w with the following property. TheoremP3.6. Let w 2 Bn . Then Pthere exist reflections t1 , . . . , tr such that w = t1 · · · tr , dp(w) = ri=1 dp(ti ), and `(w) = ri=1 `(ti ). When w 2 W enjoys such a property, we will say that the depth of w is realized by a reduced factorization into transpositions. Note that we can consider Sn as the subgroup of Bn consisting of permutations with no negative signs or equivalently as the Coxeter subgroup generated by s1 , . . . , sn 1 . Hence this theorem holds for Sn , and it is new even in that case. We conclude this section by giving an idea to how our algorithm works. We recall that reflections in Bn either swap a pair of entries (as in Sn ), or swap and change the sign to both entries, or change the sign of a single entry. We say that an entry x is in its natural position in w if x = w(x). Our algorithm begins by shuffling each positive entry w(i) which appears to the left of its natural position into its natural position, starting from the largest and continuing in descending order. Once this is completed, an unsigning move is performed. If there is more than one negative entry in w , we unsign a pair, thus obtaining two new positive entries. The process restarts, and the entries may be further shuffled. Unsigning and shuffling moves continue to alternate until neither type of move can be performed. The last unsigning move will be a single one if the number of negative entries in w is odd. At the end of the algorithm, there are no negative entries, and no positive entry is to the left of its natural position. Hence we must have the identity signed permutation. 3.3 Type D To state our formula in type D , we first need to be more careful about our notion of decomposibility. Given a signed permutation w 2 Dn , we can give a decomposition of w as w = w1 · · · wk , where we insist that each wi 2 Dm , m  n and, furthermore, no wi is a direct sum of elements of Dp , p < m. We call this decomposition of w a type D decomposition and the blocks of this decomposition type D blocks. We can also look at w 2 Dn as an element of Bn and consider its type B decomposition. Note that a type D block wi may split into bi smaller B blocks, which we denote wi = w1i · · · wbi i , where possibly bi = 1. Note that, whenever bi > 1, w1i and wbi i must have an odd number of negative entries and the remaining central B blocks w2i , . . . , wbi i 1 must have an even number of negative entries. 3.4. COINCIDENCES OF DEPTH, LENGTH, AND ABSOLUTE LENGTH 49 Definition 3.7. For each w 2 Dn , we define the D-oddness of w , denoted by oD (w), to be the difference between the number P of type B blocks and the number of type D blocks, or, D equivalently, we define o (w) := i (bi 1). Now we can state our formula for depth in type D . Note that depth depends on the Coxeter system, so w 2 Dn will have different depth considered as an element of Dn compared to considering it as an element of Bn . Theorem 3.8. Let w 2 Dn . Then 0 1 0 X X dp(w) = @ (w(i) i)A + @ {i2[n]|w(i)>i} i2Neg(w) Using our formula, we can show the following: 1 |w(i)|A + (oD (w) Corollary 3.9. For each w 2 Dn we have dp(w)  n+1 elements if n is even and 2 2 elements if n is odd. n 2 + ⌅n⇧ 2 neg(w)). (3.5) . Equality occurs for 2 n 2 2 The example in type B showing that dp(w) cannot always be realized by a product of ab(w) reflections also works in type D (though the depths are different). Nevertheless as in type B , our algorithm shows that the depth can always be realized by a reduced factorization. 3.4 3.4.1 Coincidences of depth, length, and absolute length Coincidence of length and depth Since our considerations apply to any Coxeter group, we begin with a general definition. We say that depth is universally realized by reduced factorizations in (W, S), if the depth of every element of (W, S) is realized by a reduced factorization. w 2 W there P This means that for any P exist t1 , . . . , tr 2 T such that w = t1 · · · tr , dp(w) = ri=1 dp(ti ), and `S (w) = ri=1 `S (ti ). In the previous sections, we showed that in Sn , Bn , and Dn the depth is universally realized by reduced factorizations. We do not know of any examples where depth is not realized by a reduced factorization. Following Fan [46], we say that w 2 W is short-braid-avoiding if there does not exist a consecutive subexpression si sj si , where si , sj 2 S , in any reduced expression for w . Note that, if si sj si appears in a reduced expression, then si and sj cannot commute. As Fan remarks, for elements of a simply-laced Coxeter group, being short-braid-avoiding is equivalent to being fully commutative, and for non-simply-laced groups, the short-braid-avoiding elements form a subset of the fully commutative ones. Our characterization of elements for which length and depth coincide is as follows. Theorem 3.10. Let (W, S) be any Coxeter group. For any w 2 W , dp(w) = `(w) if and only if w is short-braid-avoiding and the depth of w is realized by a reduced factorization. Hence, for a Coxeter group (W, S) in which depth is universally realized by reduced factorizations, an element w 2 W satisfies the equality dp(w) = `(w) if and only if w is short-braid-avoiding. Since depth is universally realized by reduced factorizations in the classical Coxeter groups, we have the following corollary. Corollary 3.11. Let w be an element of Sn , Bn , or Dn . Then dp(w) = `(w) if and only if w is short-braid-avoiding. 50 CHAPTER 3. DEPTH IN CLASSICAL COXETER GROUPS In Sn and Dn the short-braid-avoiding elements are the fully commutative elements. In Bn , they are precisely the top-and-bottom fully commutative elements defined by Stembridge [96, §5], so we confirm a conjecture of Petersen and Tenner [83, §5]. Our characterization of when dp(w) = `(w) can also be stated using pattern avoidance by using Corollaries 5.6, 5.7, and 10.1 in [96]. Theorem 3.12. Let w 2 Bn . Then dp(w) = `(w) if and only if w avoids the following list of patterns: [1̄, 2̄], [2̄, 1̄], [1, 2̄], [3, 2, 1], [3, 2, 1̄], [3, 1, 2̄]. Theorem 3.13. Let w 2 Dn . Then dp(w) = `(w) if and only if w avoids the following list of patterns: [1̄, 2̄, 3̄], [1, 2̄, 3̄], [2̄, 1̄, 3̄], [2, 1̄, 3̄], [2̄, 1, 3̄], [2, 1, 3̄], [3̄, 1̄, 2̄], [3, 1̄, 2̄], [3̄, 1, 2̄], [3, 1, 2̄], [3̄, 2, 1], [3, 2, 1], [3̄, 2, 1̄], [3, 2, 1̄], [1̄, 3̄, 2̄], [1, 3̄, 2̄], [2̄, 3̄, 1̄], [2̄, 3̄, 1], [2, 3̄, 1̄], [2, 3̄, 1]. These lead to the following enumerative results. Corollary 3.14. 1. The number of elements w 2 Bn satisfying dp(w) = `(w) is the Catalan number Cn+1 . 2. The number of elements w 2 Dn satisfying dp(w) = `(w) is 3.4.2 1 2 (n + 3)Cn 1. Coincidence of depth, length and reflection length In this section we characterize the elements in a Coxeter group that satisfy ab(w) = dp(w). By [83, Observation 2.3], this is equivalent to having ab(w) = `(w). Actually, this characterization easily follows from results in [42], [83], and [100], all of which predate our work. Nevertheless, we present it here for the sake of completeness. Let W be a Coxeter group. Following Tenner [100], we say an element w 2 W is boolean if the principal order ideal of w in W , B(w) := {x 2 W | x  w} is a boolean poset, where  refers to the strong Bruhat order. Recall that a poset is boolean if it is isomorphic to the poset of subsets of [k], ordered by inclusion, for some k . Theorem 7.3 of [100] states that an element w 2 W is boolean if and only if some (and hence any) reduced decomposition of w has no repeated letters. Furthermore, a result of Dyer [42, Theorem 1.1] states that for any w = s1 · · · sn reduced decomposition of w 2 W , ab(w) is equal to the minimum natural number k for which there exist 1  i1 < · · · < ik  n such that e = s1 · · · ŝi1 · · · ŝi2 · · · ŝik · · · sn , where ŝ indicates the omission of s. From these two results one can easily conclude that, Theorem 3.15. Let W be any Coxeter group and w 2 W . Then dp(w) = ab(w) if and only if w is boolean. Moreover by [100, Theorem 7.4] we get the following results. Theorem 3.16. Let w 2 Bn . Then ab(w) = dp(w) = `(w) if and only if w avoids the following list of patterns: [1̄, 2̄], [2̄, 1̄], [1, 2̄], [3, 2, 1], [3, 2, 1̄], [3̄, 2, 1], [3, 2̄, 1], [3, 4, 1, 2], [3, 4, 1̄, 2], [3̄, 4, 1, 2]. 3.5. OPEN QUESTIONS AND FURTHER REMARKS 51 Theorem 3.17. Let w 2 Dn . Then ab(w) = dp(w) = `(w) if and only if w avoids the following list of patterns: [1̄, 2̄, 3̄], [1̄, 3̄, 2̄], [2̄, 1̄, 3̄], [2̄, 3̄, 1̄], [3̄, 1̄, 2̄], [3̄, 2̄, 1̄], [3, 2, 1], [3, 4, 1, 2], [3, 2, 1̄], [3, 1̄, 2̄], [3, 4, 1̄, 2̄], [3, 4, 2̄, 1̄], [3̄, 2, 1], [2̄, 3̄, 1], [3̄, 4, 1, 2], [4̄, 3̄, 1, 2], [1, 2̄], [3, 2̄, 1], [3̄, 2, 1̄], [3̄, 4, 1̄, 2]. Corollary 3.18. 1. The number of elements w 2 Bn satisfying `T (w) = dp(w) = `(w) is the Fibonacci number F2n+1 . 2. The number of elements w 2 Bn satisfying `T (w) = dp(w) = `(w) = k is k ✓ X n+1 i=1 i i k+1 ◆✓ k i ◆ 1 , 1 where for k = 0 the sum is defined to be 1. Corollary 3.19. 1. For n 4, the number of elements w 2 Dn satisfying ab(w) = dp(w) = `(w) is 13 4b n 13 4a n a + 2 b , a2 (a b) b (b a) p p where a = (3 + 5)/2 and b = (3 5)/2. 2. For n > 1, the number of elements w 2 Dn satisfying ab(w) = dp(w) = `(w) = k is LD (n, k) = L(n, k) + 2L(n, k where L(n, k) = k P i=1 n i k+1 i k 1 i 1 1) L(n 2, k 1) L(n 2, k 2), , L(n, k) is 0 for any (n, k) on which it is undefined, and LD (1, 0) = 1 and LD (1, 1) = 0. 3.5 Open questions and further remarks There remain many possible further directions for the further study of depth. First, we have analogues of the questions asked in [83, Section 5] for the symmetric group. While we have enumerated the elements of maximal depth in Bn and Dn , the number of elements of other, non-maximal depths remains unknown. Question 3.20. How many elements of Bn or Dn have depth k ? For the symmetric group Sn , Guay-Paquet and Petersen found a continued fraction formula for the generating function for depth [65]. Petersen and Tenner also asked the following question, which we now extend to Bn and Dn : Question 3.21. Which elements of Bn or Dn have dp(w) = (ab(w) + `(w))/2? Furthermore, it seems possible that variations of our techniques can be extended to the infinite families of affine Coxeter groups, for which combinatorial models as groups of permutations on Z are given in [30, Chapter 8]. 52 CHAPTER 3. DEPTH IN CLASSICAL COXETER GROUPS Question 3.22. What are the analogues of Theorems 3.3 and 3.8 for the infinite families of affine Coxeter groups? Given Example 3.5, we can ask the following: Question 3.23. For which elements w of Bn and Dn can depth be realized by a product of ab(w) reflections? We also ask some questions relating to Theorem 3.6. Question 3.24. Is depth universally realized by reduced factorizations for all Coxeter groups? If so, is there a uniform proof ? If not, can one characterize the elements of Coxeter groups whose depth is realized by a reduced factorization? It would be interesting to know the answer even for various specific Coxeter groups. For example, one might answer this question for the infinite families of affine Coxeter groups. The question is interesting even for the finite exceptional Coxeter groups. One can attempt to use a computer to find the answer in this case, but finding a feasible method for computing the answer seems nontrivial for E8 or even E7 . Furthermore, there is another perspective on Theorem 3.6 that leads to further questions. Given a Coxeter group (W, S) and an element w 2 W , define the reduced absolute length abR (w) by abR (w) := min{r 2 N | w = t1 · · · tr for t1 , . . . , tr 2 T and `(w) = r X `(ti )}. (3.6) i=1 Note that, by definition ab(w)  abR (w)  `(w). For example, w = [4, 2, 5, 1, 3] 2 S5 has a reduced expression w = s3 s4 s1 s2 s1 s3 = s3 s4 (s1 s2 s1 )s3 . Hence `(w) = 6, and one can check that abR (w) = 4. However, its absolute length is equal to 2 since w = (s3 s4 s3 )(s3 s1 s2 s1 s3 ) = t35 t14 . Hence in this case ab(w) < abR (w) < `(w). Reduced absolute length is related to depth as follows. Proposition 3.25. Let (W, S) be a Coxeter group and w 2 W . Then dp(w)  abR (w) + `(w) . 2 If the depth of w is realized by a reduced factorization, then we have equality. In particular, for w in a classical finite Coxeter group, dp(w) = (abR (w) + `(w))/2. One can give an alternate definition of reduced absolute length as follows. We have `(wt) = `(w) + `(t) if and only if w <R wt in right weak order. Hence, abR (w) is the length of the shortest chain e = w0 <R · · · <R wr = w in right weak order where, for all i 2 [r], wi = wi 1 t for some reflection t. Given a partial order on W , define ` (w) to be the length of the shortest chain e = w0 ··· wr = w where, for all i 2 [r], wi = wi 1 t for some reflection t. If is Bruhat order, then ` = ab, and if is right (or left) weak order, ` = abR , a formula for which (for Sn , Bn , and Dn ) is given above. Hence, for any partial order on W (or at least partial orders whose relations are a subset of the relations of Bruhat order), we can ask the following. Question 3.26. Find formulas for ` for which elements ` = `. for other partial orders on Coxeter groups. Determine 3.5. OPEN QUESTIONS AND FURTHER REMARKS 53 We also have the following generalization of Question 3.21. Question 3.27. Which elements of W have ` (w) = ab(w)? A particularly interesting family of partial orders are the sorting orders of Armstrong [7], which were further studied by Armstrong and Hersh [8]. These partial orders contain all the relations of weak order but are contained in Bruhat order. 54 CHAPTER 3. DEPTH IN CLASSICAL COXETER GROUPS Chapter 4 Schur-positive symmetric functions 4.1 A conjecture of Fomin, Fulton, Li, and Poon The Schur functions form the most important basis of the ring of symmetric functions. They play an important role in representation theory and algebraic geometry, among others. A symmetric function is Schur-positive if when written as a linear combination of Schur functions has all nonnegative coefficients. A classical example is given by the product sµ s⌫ which can be written as X sµ s⌫ = c✓µ⌫ s✓ , (4.1) ✓ where the c✓µ⌫ are nonnegative integers called Littlewood–Richardson coefficients. In recent years there has been increasing interest in understanding the Schur-positivity of expressions of the form sA sB , where A and B are skew shapes (see e.g. [81] and references therein). A special case is obtained when one considers a difference s s⇢ sµ s⌫ , (4.2) where (µ, ⌫) and ( , ⇢) are pairs of partitions with same total number of parts, see e.g [11], [76]. Thanks to the Littlewood–Richardson rule this problem can be translated into a set of inequalities between the corresponding Littlewood–Richardson coefficients, namely c✓µ⌫  c✓ ⇢ . (4.3) In this chapter, we focus on particular differences of products of Schur functions of the previous form where the partitions and ⇢ are constructed from an ordered pair of partitions µ and ⌫ thought a transformation, called ⇤-operation, defined by Fomin, Fulton, Li, and Poon [51]. Their original interest in the conjecture is related to the study of Horn type inequalities for eigenvalues and singular values of complex matrices. In our presentation, their transformation (µ, ⌫) 7! (µ⇤ , ⌫ ⇤ ) on ordered pairs of partitions, will rather be denoted (µ, ⌫) 7 ! (µ, ⌫)⇤ = ( (µ, ⌫), ⇢(µ, ⌫)) (4.4) and will be called the ⇤-operation. As we shall see, this change of notation is essential in order to simplify the presentation of the many nice combinatorial properties of this operation. On the other hand, it underlines that both entries, and ⇢ of the image (µ, ⌫)⇤ of (µ, ⌫), actually depend on both µ and ⌫ . With this slight change of notation, the original definition of the ⇤-operation is as follows. Let µ = (µ1 , µ2 , . . . , µn ) and ⌫ = (⌫1 , ⌫2 , . . . , ⌫n ) two partitions with the same number of 55 56 CHAPTER 4. SCHUR-POSITIVE SYMMETRIC FUNCTIONS parts, allowing zero parts. From these, two new partitions ⇢(µ, ⌫) = (⇢1 , ⇢2 , . . . , ⇢n ) are constructed as follows k ⇢j := µk := ⌫j k + #{j | 1  j  n, ⌫j j j + 1 + #{k | 1  k  n, µk (µ, ⌫) = ( 1, 2, . . . , n) µk k}; k > ⌫j j}. Although this definition does not make it immediately clear, both truly partitions, and they are such that and (4.5) (µ, ⌫) and ⇢(µ, ⌫) are | (µ, ⌫)| + |⇢(µ, ⌫)| = |µ| + |⌫|, where as usual |µ| denotes the sum of the parts of µ. We can then state the following: Conjecture 4.1 (Fomin-Fulton-Li-Poon). For any pair of partitions (µ, ⌫), if (µ, ⌫)⇤ = ( , ⇢), then the symmetric function s s⇢ (4.6) sµ s⌫ is Schur-positive. In other words, this says that c✓µ ⌫  c✓ ⇢ , for all ✓ such that s✓ appears in the expansion of sµ s⌫ . For an example of one of the simplest cases of the ⇤-operation, let µ = (a) and ⌫ = (b), with a > b, be two one-part partitions. In this case, we get ((a), (b))⇤ = (a 1, b + 1), so that Conjecture 4.1 corresponds exactly to an instance of the classical Jacobi-Trudi identity: sa 1 sb+1 sa sb ✓ sa 1 sa = det sb sb+1 = sa 1,b+1 . ◆ In the paper [16] F. Bergeron, R. Biagioli, and M. H. Rosas. Inequalities between Littlewood-Richardson coefficients. J. Combin. Theory Ser. A, 113(4):567-590, 2006. we give a new recursive combinatorial description of the ⇤-operation and derive several consequences. This recursive description allows us to prove many instances of Conjecture 4.1 and to show that it reduces to checking a finite number of instances for any fixed ⌫ , if we bound the number of parts of µ. Moreover we show how to naturally generalize the conjecture to pairs of skew partitions. Then in the successive paper [24] R. Biagioli, V. Guerrini, and S. Rinaldi. On a Schur positivity conjecture in multiplicity-free cases. In preparation, 2015. we study the Conjecture 4.1 when the product sµ s⌫ is multiplicity-free. Stembridge classified the pairs of partitions (µ, ⌫) having such a property in four families. For three of those we are able to prove the conjecture. 4.2. COMBINATORIAL PROPERTIES OF THE ⇤-OPERATION AND IMPLICATIONS57 4.2 Combinatorial properties of the ⇤-operation and implications We first derive some nice combinatorial properties of the transformation ⇤. To help in the presentation of these properties, let us introduce some further notation. For any undefined notation we refer to [79]. We often identify a partition with its (Ferrers) diagram. Diagrams are drawn here using the “French” convention of ordering parts in decreasing order from bottom to top. i We write µ = ! ↵ , if the partition µ is obtained from the partition ↵ by adding one cell in line i; and µ = ↵"k , if µ is obtained from ↵ by adding one cell in column k . In other ` words, µ = ! ↵ means that µi = ↵i for all i 6= `, and µ` = ↵` + 1. Below are illustrated the 2 partitions ↵ ! ! ↵ , and ↵ ! ↵"2 in term of diagrams. We can now state our recursive description of the ⇤-operation. Proposition 4.2 (Recursive formula). For any partitions ↵ and ⌫ , let µ = ! ↵ and ( , ⇢) = (↵, ⌫)⇤ , then we have 8 > > <( , ⇢"µi ) if there exists j such that ⌫j j = ↵i i, i (µ, ⌫)⇤ = Similarly, when ⌫ = !i ⇤ (µ, ⌫) = > > :(!i , ⇢) (4.7) otherwise. and ( , ⇢) = (µ, )⇤ , we have 8 > <( "⌫i , ⇢) > : i ( ,! ⇢ ) if there exists j such that µj j = ⌫i i, (4.8) otherwise. We can clearly use Proposition 4.2 to recursively compute (µ, ⌫) and ⇢(µ, ⌫). The actual computation of the ⇤-operation can be simplified in view of the following property. For any pair of partitions (µ, ⌫), we have (µ, ⌫)⇤ = ( , ⇢) i↵ ⇤ (⌫ 0 , µ0 ) = ( 0 , ⇢0 ), (4.9) where, as usual, µ0 stands from the conjugate of µ. An example of such property is depicted below. Using the fact that the involution ! (which is the linear operator that maps sµ to sµ0 ) is multiplicative, it easily follows that Proposition 4.3. Conjecture 4.1 holds for the pair (µ, ⌫) if and only if it holds for the pair (⌫ 0 , µ0 ). 58 CHAPTER 4. SCHUR-POSITIVE SYMMETRIC FUNCTIONS In practice, there are many ways to describe the ⇤-operation recursively, since we can freely choose how to make partitions grow. It is sometimes convenient to start from the pair (0, ⌫), with 0 standing for the empty partition, whose image under the ⇤-operation has a simple description. Lemma 4.4. Let ⌫ be any partition. Then ⇢(0, ⌫) = (⌫1 , ⌫2 0 where k = max{i | ⌫i (0, ⌫) = (⌫10 1, . . . , ⌫k 1, ⌫20 (k 2, . . . , ⌫k0 1)) k), i}. We will sometimes use respectively ⌫ and ⌫ to denote the partitions (0, ⌫) and ⇢(0, ⌫). For example if ⌫ = 866554421, then ⌫ = 44432211 and ⌫ = 85421 as is illustrated in Figure 4.1. Figure 4.1: (0, ⌫) !⇤ (⌫, ⌫) In Figure 4.2 we illustrate our computation method. We first compute the image of (0, ⌫), and then we recursively construct µ adding one cell at a time, and compute the corresponding image. Figure 4.2: Recursive computation of ((7, 4), ⌫)⇤ . Another remarkable property of the ⇤-operation is that its image behaves nicely under the dominance order, denoted . More precisely: 4.2. COMBINATORIAL PROPERTIES OF THE ⇤-OPERATION AND IMPLICATIONS59 Lemma 4.5. For any pair of partitions (µ, ⌫), if ( , ⇢) = (µ, ⌫)⇤ , then we have µ[⌫ ⌫ µ+⌫ [ ⇢, (4.10) and equivalently (4.11) + ⇢. As is usual (See [79]), hµ denotes the complete homogeneous symmetric function: hµ := hµ1 hµ2 · · · hµk , with ha := sa . Recall that hµ h⌫ = hµ[⌫ , and that the difference of two homogeneous symmetric functions h↵ h is Schur-positive, if and only if ↵ (see [88, Chapter 2]). Then Lemma 4.5 immediately implies the following statement very similar to that of Conjecture 4.1. Proposition 4.6. For any pair of partitions (µ, ⌫), if ( , ⇢) = (µ, ⌫)⇤ , then h h⇢ (4.12) hµ h⌫ is Schur-positive. It follows directly from Proposition 4.2 that the ⇤-operation is compatible with “inclusion” of partitions. Here, we say that ↵ is included in µ, if the diagram of ↵ is included in the diagram of µ. We will simply write (↵, ) ✓ (µ, ⌫), whenever ↵ ✓ µ and ✓ ⌫, and we have: Lemma 4.7. For ↵, hold , µ and ⌫ partitions such that (↵, ) ✓ (µ, ⌫), the following inclusions (↵, ) ✓ (µ, ⌫), and ⇢(↵, ) ✓ ⇢(µ, ⌫). An immediate, but interesting, consequence of this lemma is the following observation. Observation 4.8. Let (↵, ) and ( , ) be two fixed points of the ⇤-operation such that (↵, ) ✓ ( , ). Writing simply for (µ, ⌫) and ⇢ for ⇢(µ, ⌫), we see (using Lemma 4.7) that (↵, ) ✓ (µ, ⌫) ✓ ( , ), implies (↵, ) ✓ ( , ⇢) ✓ ( , ). As is underlined in [51], a pair of partitions (↵, ) is a fixed point of the ⇤-operation if and only if ↵1 ↵2 · · · ↵n . (4.13) 1 2 n Let us underline here that, for any (µ, ⌫), it is easy to characterize the “largest” (resp. “smallest”) fixed point contained in (resp. containing) the pair (µ, ⌫). We will see below how this observation can be used to link properties of and ⇢ to properties of µ and ⌫ . Recall that a hook is a shape of the form (a, 1b ) with a, b 0, a n-line partition is a shape contained in a rectangle (an ) with a, n 0, a horizontal strip is a skew shape µ/↵ with no two squares in the same column, and that a ribbon is a connected skew shape with no 2 ⇥ 2 squares (see [92, Chapter 7], for more details). If we drop the condition of being connected in this last definition, we say that we have a weak ribbon. 60 CHAPTER 4. SCHUR-POSITIVE SYMMETRIC FUNCTIONS Another striking consequence of Lemma 4.7 is that it allows a natural extension of the ⇤-operation to skew partitions. Denoting by (µ, ⌫)/(↵, ) the pair of skew shapes (µ/↵, ⌫/ ), we can simply define (µ/↵, ⌫/ )⇤ := (µ, ⌫)⇤ /(↵, )⇤ . (4.14) In other words, we have (µ/↵, ⌫/ ) := (µ, ⌫)/ (↵, ), (4.15) ⇢(µ/↵, ⌫/ ) := ⇢(µ, ⌫)/⇢(↵, ). (4.16) and The ⇤-operation, or its extension as above, preserves (among others) the following families of pairs of (skew) shapes. Proposition 4.9. The ⇤-operation preserves the families of (1) pairs of hooks; (2) pairs of n-line partitions; (3) pairs of horizontal strips; (4) pairs of weak ribbons. Note that (1) and (2) follow directly from Observation 4.8, and that the statements (3) and (4) are made possible in view of our extension of the ⇤-operation. Figure 4.3: The effect of the ⇤-operation on hooks. Extensive computer experimentation suggests that we have the following extension of Conjecture 4.1. Conjecture 4.10. For any skew partitions µ/↵ and ⌫/ , if ( , ⇢) = (µ/↵, ⌫/ )⇤ , then the symmetric function s s⇢ sµ/↵ s⌫/ (4.17) is Schur-positive. This has yet to be understood in geometrical terms. One should point out that there are many skew shapes giving the same expression for the symmetric function sµ/↵ s⌫/ . The result of the ⇤-operation is dependent on the particular choice of the skew shape, so that there are many identities encoded in (4.17). On the other hand, it is clear that Proposition 4.3 extends to skew partitions. 4.3 Main results In this section we state our results concerning the validity of Conjecture 4.1 for certain families of pairs, as well as its reduction to a finite number of tests for other families. The following is the explicit formulation of the Littlewood-Richardson rule that we are going to use to compute the c✓µ ⌫ ’s. In order to state it, let us recall some terminology. A lattice permutation is a sequence of positive integers a1 a2 · · · an such that in any initial factor 4.4. MULTIPLICITY-FREE CASES 61 a1 a2 · · · aj the number of i’s is at least as great as the number of i + 1’s, for all i. The type of a lattice permutation is (naturally) the sequence of multiplicities of the integers 1, 2, . . . that appear in it. The reverse reading word of a tableau, is the reading word of a tableau, read backwards. Then it is well-known that the Littlewood-Richardson coefficient c✓µ ⌫ is equal to the number of semistandard tableaux of shape ✓/⌫ and type µ whose reverse reading word is a lattice permutation. When a semistandard tableau of shape ✓/⌫ has a lattice permutation as its reverse reading word, we say that it is a LR-filling of shape ✓/⌫ . Theorem 4.11. Conjecture 4.1 (or 4.10) holds (1) For any pair (µ, ⌫) of hook shapes. (2) For skew pairs of the form (µ/↵, ⌫/ ), where µ, ⌫ , ↵, (3) For skew pairs of the form (0, ⌫/ ), with ⌫/ are hooks, with ↵ = . a weak ribbon. Theorem 4.11 is proved by defining case-by-case injections between the two corresponding sets of LR-fillings, counted respectively by c✓µ ⌫ and c✓ ⇢ . On another note, a careful study of the recursive construction of (µ, ⌫) and ⇢(µ, ⌫) shows that, in a sense, Conjecture 4.1 follows, under some conditions, from a finite number of cases when ⌫ is fixed and µ becomes large. More precisely, we obtain the result below. As usual, the number of nonzero parts of µ is denoted by `(µ) and called the length of µ. Theorem 4.12. For any positive integer p, let ⌫ be a fixed partition with at most p parts, i.e. `(⌫)  p. Then, the validity of Conjecture 4.1 for the infinite set of all pairs (µ, ⌫), with `(µ)  p, reduces to checking the validity of the conjecture for the finite set of pairs (↵, ⌫), with ↵ having at most p parts, and largest part bounded as follows ↵1  p (⌫1 + p). (4.18) Theorem 4.12 can also be generalized in a straightforward manner to the set of skew shapes pairs (µ/↵, ⌫/ ) of bounded height, with ⌫ and ↵ fixed. The proof is based in the following observation. We say that µ has a k -full column in ✓ , if there is a j such that the j th column of µ and ✓ are both of height k . An example of a 6-full column is depicted below. When this is the case, setting := ✓ 1k and := µ 1k , we remark that c✓µ⌫ = c ⌫ . Theorem 4.12 follows from this observation, by induction on the number of columns of µ. 4.4 Multiplicity-free cases In this section we study Conjecture 4.1 for the interesting class of pairs of partitions (µ, ⌫) for which sµ s⌫ is multiplicity-free, namely for which any coefficient appearing in (4.1) is equal to 0 or 1. Stembridge classified such pairs in [93] and used the following notions for his presentation. A rectangle is a partition with at most one part size, i.e., empty, or of the form (cr ) for suitable c, r > 0; a fat hook is a partition with exactly two parts sizes, i.e., of the form (br cs ) 62 CHAPTER 4. SCHUR-POSITIVE SYMMETRIC FUNCTIONS for suitable b > c > 0; and a near-rectangle is a fat hook such that it is possible to obtain a rectangle from it by deleting a single row or column. For example (4, 4, 4) is a rectangle, (6, 4, 4, 4) a near-rectangle, and (5, 5, 3, 3, 3) a fat-hook. He shows that the product sµ s⌫ is multiplicity-free if and only if (a) µ or ⌫ is a one-line rectangle, or (b) µ is a two-line rectangle and ⌫ is a fat hook or vice-versa, or (c) µ and ⌫ are both rectangles, or (d) µ is rectangle and ⌫ is a near rectangle or vice-versa. Theorem 4.13. Conjecture 4.1 holds for cases (a),(b) and (c) of Stembridge classification. In this section we illustrate the outline of the proof of this result. The structure of the demonstrations is the same in all the three cases but each situation requires an ad-hoc procedure. In the case (d) we have only partial results. Our algorithms apply also in this case, but several sub-cases need to be analyzed separately, and we do not have for now a general method that encloses all of them. The starting point is to prove that Conjecture 4.1 holds when one of the partitions is empty. The proof of this simple case is important since it allows us to define the natural filling. Proposition 4.14. For any partition ⌫ the difference s⌫ s⌫ s⌫ is Schur-positive. Thus, recalling that s0 = 1, Conjecture 4.1 holds for pairs of the form (0, ⌫). To prove this result, we construct an explicit LR-filling of ⌫/⌫ of type ⌫ . To this end, we proceed as follows. We “slide” the natural filling of ⌫ up the columns of ⌫ . This gives a partial filling of ⌫ with empty cells for the portion of ⌫ that corresponds to ⌫ . We will suppose that these empty cells are filled with zeros. We then sort each row in increasing order to get a filling of the skew shape ⌫/⌫ . By construction, we obtain a filling of ⌫/⌫ whose reverse reading word a the lattice permutation. We call such a filling the natural filling of ⌫/⌫ . An example is given in Figure 4.4. 8 7 6 5 4 3 2 1 6 5 4 3 2 1 8 7 6 5 4 3 4 3 3 2 2 1 1 6 5 4 3 2 2 1 1 4 3 3 2 2 1 1 8 6 7 3 4 5 6 2 3 4 5 1 2 3 4 1 2 3 1 2 1 Figure 4.4: The natural filling of ⌫/⌫ . We can now define briefly our “type-algorithm” to construct an explicit LR-filling of shape ✓/⇢ of type , when (µ, ⌫) belongs to one of the Stembridge families, and c✓µ⌫ = 1. Definition 4.15 (Hook insertion). • Initial tableau. 4.4. MULTIPLICITY-FREE CASES 63 (1) Fill the cells in ⌫/⌫ with the natural filling and those in ✓/⌫ with its unique LR-filling of type µ. (2) Remove the cells of ⇢/⌫ . Obtain a tableau of shape ✓/⇢, called initial tableau and denoted T I . • Adjusted tableau. (3) If the type of T I is we move to the next step. Otherwise we modify the entries of T I in a way to obtain the correct type. The associate tableau will be denoted T (0) . • Insertion method and final tableau. (4) Consider the cells c1 , . . . , cm of ✓/⇢ that by definition are filled with entries given by the LR-filling. These cells “identify” a sequence of hooks H1 , . . . , Hm . Now we define a procedure to move the entries of the cells c1 , . . . , cm inside the associated hooks. In most of the cases this procedure consists in sequentially rearranging the entries in the hooks in increasing order. (5) The tableau T F obtained at the end of the procedure will be called the final tableau. The proof will consist in showing that the final tableau T F obtained in each case is a LRfilling of the correct type. In each case an ad-hoc specific insertion method will be defined. To get an idea of this procedure (that in some case is quite involved), we show in the example below the easiest case, namely when µ = (n) is a one-line rectangle, and ⌫ is any partition with ⌫1 n. In this case the insertion method is the following. Example 4.16. Figure 4.5 below shows the application of the insertion method to a tableau of shape ✓/⇢, where ✓ = (8, 8, 8, 6, 5, 5, 3, 2, 2), ⌫ = (8, 8, 7, 6, 5, 3, 2, 2, 1), and ⇢ = (8, 7, 5, 4, 2). The cells c1 , c2 , c3 , c4 and c5 of the horizontal strip ✓/⌫ are enlightened in the initial tableau T I in (a). In this case T I has the good type, so we do not need Step (3). The hooks associated to cells c1 , . . . , c5 are sequentially enlighten and their entries are reordered in increasing way, see figures (b)–(f). The recursive rearrangement of the hooks H1 , . . . , H5 produces the final tableau T F depicted in Figure 4.5(f). This is a LR-filling of the right shape and type. c1 8 6 5 3 1 7 c2 6 1 c3 c4 4 5 1 1 2 3 4 c5 2 3 1 2 1 1 (a) 6 5 3 1 8 7 c2 6 1 c3 c4 4 5 1 1 2 3 4 c5 2 3 1 2 1 1 (b) 6 5 3 1 8 7 c2 4 6 c3 c4 1 5 1 1 2 3 4 c5 2 3 1 2 1 1 (c) 6 5 3 1 8 7 4 6 c3 c4 1 2 5 1 1 3 4 c5 2 3 1 2 1 1 (d) 6 5 3 1 8 7 c4 4 6 1 2 3 5 1 1 4 c5 2 3 1 2 1 1 (e) Figure 4.5: The insertion method when µ = (5), a one-line rectangle. 6 5 3 1 8 7 4 6 1 2 3 5 1 1 4 c5 2 3 1 1 2 1 (f) 64 CHAPTER 4. SCHUR-POSITIVE SYMMETRIC FUNCTIONS Bibliography [1] R. M. Adin and Y. Roichman. The Flag Major Index and Group Actions on Polynomial Rings. Europ. J. Combinatorics, 22 (2001), 431-446. [2] R. M. Adin, F. Brenti, and Y. Roichman. Descent Numbers and Major Indices for the Hyperoctahedral Group. Adv. in Appl. Math., 27 (2001), 210–224. [3] R. M. Adin, F. Brenti, and Y. Roichman. Equi-distribution over descent classes of the Hyperoctahedral Group. J. Combin. Theory Ser. A, 113 (2006), 917-933. [4] R. M. Adin, F. Brenti, and Y. Roichman. Descent representations and multivariate statistics. Trans. Amer. Math. Soc., 357 (2005), 3051–3082. [5] R. M. Adin, I. Gessel, and Y. Roichman. Signed Mahonians. J. Combin. Theory Ser. A, 109 (2005), 25–43. [6] E. E. Allen. Descent monomials, P-partitions and dense Garsia-Haiman modules. J. Alg. Combin., 20 (2004), 173-193. [7] D. Armstrong. The sorting order on a Coxeter group. J. Combin. Theory Ser. A, 116(8):1285–1305, 2009. [8] D. Armstrong and P. Hersh. Sorting orders, subword complexes, Bruhat order and total positivity. Adv. in Appl. Math., 46(1–4):46–53, 2011. [9] E. Bagno, R. Biagioli. Colored-Descent Representations of Complex Reflection Groups G(r, p, n). Israel J. Math. 160 (2007), 317–348. [10] E. Bagno, R. Biagioli, M. Novick and A. Woo. Depth in classical Coxeter groups. arXiv:1507.01180. [11] C. Ballantine and R. Orellana. Schur positivity in a square. Elect. J. Combin. 21 (3) (2014), #P3.46 [12] E. Barcucci, A. Del Lungo, E. Pergola, and R. Pinzani. Some permutations with forbidden subsequences and their inversion number. Discrete Math., 234(1-3):1–15, 2001. [13] M. Barnabei, F. Bonetti, S. Elizalde, and M. Silimbani. Descent sets on 321-avoiding involutions and hook decompositions of partitions. J. Combin. Theory Ser. A, 128 (2014), 132–148. [14] P. Baumann and C. Hohlweg. A Solomon descent theory for the wreath products G o Sn . Trans. Amer. Math. Soc., 360 (2008), 1475–1538. [15] F. Bergeron and R. Biagioli. Tensorial square of the hyperoctahedral group coinvariant space. Elect. J. Combin., 13 (2006), R38. 65 66 BIBLIOGRAPHY [16] F. Bergeron, R. Biagioli, and M. Rosas. Inequalities between Littlewood-Richardson coefficients. J. Combin. Theory, Series A, 113 (2006), 567–590. [17] F. Bergeron and F. Lamontagne. Decomposition of the diagonal action of Sn on the coinvariant space of Sn ⇥ Sn . Lascoux TestSchrift, Sém. Lothar. Combin., [B52e] (2004). [18] R. Biagioli. Signed Mahonian polynomials for classical Weyl groups. Europ. J. Combin., 27 (2006), 207–217. [19] R. Biagioli. Equidistribution of negative statistics and quotients of Coxeter groups of type B and D. Adv in Appl. Math., 41 (2008), 378–394. [20] R. Biagioli, M. Bousquet-Mélou, F. Jouhet, and P. Nadeau. Length enumeration of fully commutative elements in Coxeter groups. In preparation, 2015. [21] R. Biagioli and F. Caselli. Invariant algebras and major indices for classical Weyl groups. Proc. Lond. Math. Soc. 88 (2004), 603–631. [22] R. Biagioli and F. Caselli. A descent basis for the coivariant algebra of type D . J. Algebra, 275 (2004), 517–539. [23] R. Biagioli and F. Caselli. Enumerating Projective reflexion groups. Adv. Appl. Math., 48 (2012), 249–268. [24] R. Biagioli, V. Guerrini, and S. Rinaldi. On a Schur positivity conjecture in multiplicityfree cases. In preparation, 2015. [25] R. Biagioli, F. Jouhet, and P. Nadeau. Fully commutative elements in finite and affine Coxeter groups. Monatsh. Math., 178 (2015), 1–37. [26] R. Biagioli, F. Jouhet, and P. Nadeau. Combinatorics of fully commutative involutions in classical Coxeter groups. Discrete Math., 338 (2015), 2242–2259. [27] R. Biagioli and J. Zeng. On some analogues of descent numbers and major index for the hyperoctahedral group. Sém. Loth. Combin. 61A (2010), article [B61Ak]. [28] R. Biagioli and J. Zeng. Enumerating wreath products via Garsia-Gessel bijections. Europ. J. Combin. 32 (2011), 538–553. [29] S. C. Billey, W. Jockusch, and R. P. Stanley. Some combinatorial properties of Schubert polynomials. J. Algebraic Combin., 2(4):345–374, 1993. [30] A. Björner and F. Brenti. Combinatorics of Coxeter groups, volume 231 of Graduate Texts in Mathematics. Springer, New York, 2005. [31] M. Bousquet-Mélou. A method for the enumeration of various classes of column-convex polygons. Discrete Math, 154(1-3) (1996), 1–25. [32] M. Bousquet-Mélou and X. G. Viennot. Empilement de segments et q -énumeration de polyominos convexes dirigés. J. Combin. Theory Ser. A, 160(1992), 196–224. [33] M. Broué. Reflection groups, braid groups, Hecke algebras, finite reductive groups. Current developments in mathematics, Int. Press, Somerville, (2001), 1–107. [34] M. Broué, G. Malle, and R. Rouquier. Complex reflection groups, braid groups, Hecke algebras. J. Reine Angew. Math., 500 (1998), 127–190. BIBLIOGRAPHY 67 [35] L. Carlitz, A combinatorial property of q-Eulerian numbers. Amer. Math. Montly, 82 (1975), 51–54. [36] F. Caselli. Projective reflection groups. Israel J. Math., 185 (2011), 155–187. [37] C. Chevalley. Invariants of finite groups generated by reflections. Amer. J. Math., 77 (1955), 778–782. [38] C.-O. Chow and I. M. Gessel. On the descent numbers and major indices for the hyperoctahedral group. Adv. in Appl. Math. 38 (2007), 275–301. [39] C.-O. Chow and T. Mansour. A Carlitz identity for the wreath product Cr o Sn . Adv. in Appl. Math. 47 (2011), 199–215. [40] J. Désarménien and D. Foata. The signed Eulerian numbers. Discrete Math. 99 (1992), 49–58. [41] P. Diaconis and R. L. Graham. Spearman’s footrule as a measure of disarray. J. Roy. Statist. Soc. Ser. B, 39(2):262–268, 1977. [42] M. J. Dyer. On minimal lengths of expressions of Coxeter group elements as products of reflections. Proc. Amer. Math. Soc., 129(9):2591–2595, 2001. [43] D. C. Ernst. Diagram calculus for a type affine C Temperley-Lieb algebra, I. J. Pure Appl. Algebra, 216(11):2467–2488, 2012. [44] D. C. Ernst. Diagram calculus for a type affine C Temperley-Lieb algebra. II. arXiv:1101.4215, 2011. [45] C. K. Fan. Schubert varieties and short braidedness. Transformation Groups, 3(1):51–56, 1998. [46] C. K. Fan. A Hecke algebra quotient and properties of commutative elements of a Weyl group. Phd thesis, M.I.T., 1995. [47] C. K. Fan. Structure of a Hecke algebra quotient. J. Amer. Math. Soc., 10(1):139–167, 1997. [48] C. K. Fan and R. M. Green. On the affine Temperley-Lieb algebras. J. London Math. Soc. (2), 60(2):366–380, 1999. [49] D. Foata. On the Netto inversion number of a sequence. Proc. Amer. Math. Soc., 19 (1968), 236–240. [50] D. Foata and M. P. Schützenberger. Major index and inversion number of permutations. Math. Nachr., 83 (1978), 143–159. [51] S. Fomin, W. Fulton, C.-K. Li, and Y.-T. Poon. Eigenvalues, singular values, and Littlewood-Richardson coefficients. Amer. J. Math., 127(1):101–127, 2005. [52] S. Fomin and C. Greene. Noncommutative Schur functions and their applications. Discrete Math., 193(1-3):179–200, 1998. Selected papers in honor of Adriano Garsia (Taormina, 1994). [53] S. Fomin, D. Stanton. Rim hook lattices, St. Petersburg Math. J. 9 (1998), no. 5, 1007– 101. [54] The GAP Group. GAP – Groups, Algorithms, and Programming, Version 4.7.2, 2013 68 BIBLIOGRAPHY [55] A. Garsia and I. Gessel. Permutation statistics and partitions. Adv. Math., 31 (1979), 288–305. [56] A. Garsia and D. Stanton. Group actions of Stanley-Reisner rings and invariant of permutation groups. Adv. Math., 51 (1984), 107–201. [57] I. M. Gessel. Generating functions and enumeration of sequences. Ph.D. Thesis, M.I.T., 1977. [58] J. Graham. Modular Representations of Hecke Algebras and Related Algebras. PhD thesis, University of Sydney, 1995 [59] R. M. Green. On 321-avoiding permutations in affine Weyl groups. J. Algebraic Combin., 15(3):241–252, 2002. [60] R. M. Green. Combinatorics of Minuscule Representations. Cambridge Tracts in Mathematics. Cambridge University Press, 2013. [61] R. M. Green. Cellular algebras arising from Hecke algebras of type Hn . Math. Z., 229(2):365–383, 1998. [62] R. M. Green. On the Markov trace for Temperley-Lieb algebras of type En . J. Knot Theory Ramifications, 18(2):237–264, 2009. [63] R. M. Green. Generalized Temperley-Lieb algebras and decorated tangles. J. Knot Theory Ramifications, 7(2):155–171, 1998. [64] R. M. Green and J. Losonczy. Fully commutative Kazhdan-Lusztig cells. Ann. Inst. Fourier (Grenoble), 51(4):1025–1045, 2001. [65] M. Guay-Paquet and T. K. Petersen. The Generating Function for Total Displacement. Electon. J. Combin., 21(3) : 2014, Paper P3.37 e Electron. J. Combin., [66] M. Hagiwara. Minuscule heaps over Dynkin diagrams of type A. 11(1):Research Paper 3, 20, 2004. [67] C. R. H. Hanusa and B. C. Jones. The enumeration of fully commutative affine permutations. European J. Combin., 31(5):1342–1359, 2010. [68] F. Hivert, J.C. Novelli, and J.Y. Thibon. Multivariate generalizations of the FoataSchützenberger equidistribution, Discr. Math. Theo. Comp. Sci. Proc. of Fourth Colloquium on Mathematics and Computer Science, Nancy, 2006. [69] J. E. Humphreys. Reflection groups and Coxeter groups, volume 29 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1990. [70] V. F. R. Jones. Hecke algebra representations of braid groups and link polynomials. Ann. of Math. (2), 126(2):335–388, 1987. [71] F. Jouhet and P. Nadeau. Long fully commutative elements in Coxeter groups. Integers, 15 (2015) paper n. A36. [72] D. E. Knuth. The art of computer programming. Vol. 3. Addison-Wesley, Reading, MA, 1998. Sorting and searching, Second edition. [73] W. Kraskiewicz and Weymann. Algebra of coinvariants and the action of Coxeter elements, Bayreuth. Math. Schr., 63 (2001), 265–284. BIBLIOGRAPHY 69 [74] C. Krattenthaler. The theory of heaps and the Cartier Foata monoid. Appendix of the electronic edition of “Problèmes combinatoires de commutation et réarrangements”, 2006. [75] G. R. Krause and T. H. Lenagan. Growth of algebras and Gelfand-Kirillov dimension, volume 22 of Graduate Studies in Mathematics. American Mathematical Society, Providence, RI, revised edition. [76] T. Lam, A. Postnikov, and P. Pylyavskyy. Schur positivity and Schur log- concavity. Amer. J. Math., 129 (2007), 1611-1622 [77] F. Lamontagne. Étude d’espaces de polynômes harmoniques généralisés. Ph. D. Thesis, UQAM, 2003. [78] G. Lusztig. Some examples of square integrable representations of semisimple p-adic groups. Trans. Amer. Math. Soc., 277(2):623–653, 1983. [79] I. G. Macdonald, Symmetric functions and Hall polynomials, second edition, Oxford Math. Monographs, Oxford Univ. Press, Oxford 1995. [80] P. A. MacMahon, Combinatorial Analysis, Chelsea, 1960. Originally published in two volumes by Cambridge Univ. Press, 1915-16. [81] P. McNamara. Comparing skew Schur functions: a quasisymmetric perspective. Journal of Combinatorics, 5 (1) (2014), 51–85. [82] T. K. Petersen. The sorting index. Adv. in Appl. Math., 46 (2011), 615–630. [83] T. K. Petersen and B. E. Tenner. The depth of a permutation. J. Comb., 6(1–2):145–178, 2015. [84] A. Postnikov. Affine approach to quantum Schubert calculus. Duke Math. J., 128(3):473– 509, 2005. [85] V. Reiner. Descents and one-dimensional characters for classical Weyl groups. Discrete Math. 140 (1995), 129–140. [86] V. Reiner. Signed permutation statistics. European J. Combin. 14 (1993), 553–567. [87] D. P. Roselle, Coefficients associated with the expansion of certain products, Proc. Amer. Math. Soc., 45 (1974), 144-150. [88] B. E. Sagan, The Symmetric Group, Representations, Combinatorial Algorithms, and Symmetric Functions, GTM 203, Springer, 2000. [89] J.-Y. Shi. Fully commutative elements and Kazhdan-Lusztig cells in the finite and affine Coxeter groups. Proc. Amer. Math. Soc., 131(11):3371–3378 (electronic), 2003. [90] J.-Y. Shi. Fully commutative elements and Kazhdan-Lusztig cells in the finite and affine Coxeter groups. II. Proc. Amer. Math. Soc., 133(9):2525–2531, 2005. [91] G, C. Shephard and J. A. Todd. Finite unitary reflection groups, Canad. J. Math., 6 (1954), 274–304. [92] R. P. Stanley. Enumerative combinatorics. Vol. 2, volume 62 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1999. [93] J. R. Stembridge. Multiplicity-Free Products of Schur Functions. Ann. Comb. 5 (2001), no. 2, 113–121. 70 BIBLIOGRAPHY [94] J. R. Stembridge. On the eigenvalues of representations of reflection groups and wreath products, Pacific J. Math., 140 (1989), 359–396. [95] J. R. Stembridge. On the fully commutative elements of Coxeter groups. J. Algebraic Combin., 5(4):353–385, 1996. [96] J. R. Stembridge. Some combinatorial aspects of reduced words in finite Coxeter groups. Trans. Amer. Math. Soc., 349(4):1285–1332, 1997. [97] J. R. Stembridge. The enumeration of fully commutative elements of Coxeter groups. J. Algebraic Combin., 7(3):291–320, 1998. [98] J. R. Stembridge. Minuscule elements of Weyl groups. J. Algebra, 235(2):722–743, 2001. [99] H. N. V. Temperley and E. H. Lieb. Relations between the “percolation” and “colouring” problem and other graph-theoretical problems associated with regular planar lattices: some exact results for the “percolation” problem. Proc. Roy. Soc. London Ser. A, 322(1549):251– 280, 1971. [100] B. E. Tenner. Pattern avoidance and the Bruhat order. J. Combin. Theory Ser. A, 114(5):888–905, 2007. [101] G. X. Viennot. Heaps of pieces. I. Basic definitions and combinatorial lemmas. In Combinatoire énumérative (Montreal, Que., 1985/Quebec, Que., 1985), volume 1234 of Lecture Notes in Math., pages 321–350. Springer, Berlin, 1986. [102] M. V. Zavodovskii and Yu. S. Samoilenko. Growth generalized Temperley-Lieb algebras connected with simple graphs. Ukrainian Math. J., 61(11):1858–1864, 2009. [103] M. L. Wachs. An involution for signed Eulerian numbers. Discrete Math. 99 (1992), 59–62. Combinatoire autour des groupes de permutations généralisées Image en couverture : Hexadécachore régulier. Crédit image : https ://fr.wikipedia.org/wiki/Hexadécachore.