Université de PARIS 7 - Denis Diderot

HAUTEUR SUR LE TREILLIS DES

PARTITIONS

Thèse de doctorat

Membres du Jury :

Daniel BARSKY Michel BROUÉ Alain LASCOUX Pierre-André PICON Giuseppe PIRILLO Novembre 1995

présentée par

Sungsoon KIM

A la mémoire de mon père. 1

Remerciements

Je souhaite tout d’abord exprimer ma gratitude envers mon directeur de thèse Alain Lascoux qui m’a accueillie dans son équipe de recherche, qui m’a successivement enseigné la théorie combinatoire et qui a bien voulu me guider avec patience jusqu’à l’accomplissement du présent travail.

Je suis tout particulièrement reconnaissante envers Marcel-Paul Schützenberger qui m’a toujours reçue avec le sourire, pour son aide et ses encouragements constants.

Je suis également très reconnaissante envers Michel Broué de m’avoir toujours offert une place pour me permettre de travailler et dont la présence comme membre du jury de ma thèse est un honneur.

J’adresse aussi mes remerciements à tous les membres de l’équipe Combinatoires Algébriques de Paris 7, de Marne la Vallée, et de l’Université de Rouen : Jacques Désarmenien, Daniel Krob, Alain Lascoux, Bernard Leclerc, Pierre-André Picon, Claude Precetti, Jean-Yves Thibon et plus particulièrement Gérard Duchamp avec qui j’ai eu l’honneur de publier un article, Bernard Leclerc qui m’a aidé, a su repondre à mes questions combinatoires , et m’a proposé des améliorations de mon résumé. Leur amitiés et encouragements m’ont aidée tout au long de ces années de travail sur ma thèse.

Je remercie chaleureusement les membres de l’équipe de Michel Broué (à Paris 7 maintenant) ; Raphaël Rouquier, Jean Michel, Marc Cabanes, Michel Enguehard pour leur hospitalité et leur gentillesse constante, plus particulièrement Raphaël Rouquier pour avoir essayé de trouver des travaux en commun avec notre équipe ( celle de Lascoux) et pour m’avoir aidé avec patience et sans hésitation même pour des petits problèmes. Je remercie aussi Jean Michel qui a corrigé des fautes de français et de mathématiques et s’est intéressé à mon travail en combinatoire, et aussi Alexandre Zimmermann pour son amitié. Je remercie cordialement Audrey Provost pour ses conseils sur la rédaction de la grammaire française de mon résumé avec gentillesse et pour son amitié constante.

Je suis cordialement reconnaissante envers mes amis de l’ENS qui continuent à m’inviter et avec qui je partage de bons moments depuis mon année de DEA ; Jacques Garrigues, Plume, Max, Isillions, Jacob, Markus Junker, etc. Je remercie Jacques Beigbeder qui a toujours répondu gentiment à toutes mes questions sur les machines. J’aimerais bien profiter de cette occasion pour exprimer ma sincère reconnaissance à Michel Broué (qui était le Directeur du DMI à l’ENS) qui m’a accueillie et m’a donné la chance de travailler dans une ambiance très amicale à l’ENS.

J’aimerais enfin exprimer ma profonde gratitude envers les membres du jury :

• le président Daniel BARSKY pour honneur qu’il me fait de présider mon jury;

• les rapporteurs Pierre-André Picon et Guiseppe Pirillo pour leurs corrections de mon résumé.

• Michel Broué pour sa participation sympathique;

• et bien sûr Alain Lascoux pour son soutien.

Je remercie infiniment mes Bleau-mates francais, X.-X. X., M. Moustache et RR de tout de mon cœur qui me proposaient d’aller à Bleau tous les dimanches et partagaient les moments de bonne humeur et les sourires, traduisaient mes questions sur l’argot français, qui m’ont donné enfin les plus beaux et inoubliables souvenirs pendant toutes ces années de ma résidence en France. jE REMERcie sincèrement Josiane et Jean-Pierre Serre et la famille de Broue pour leur amitié cordiale.

Je remercie ma mère et ma famille qui m’ont toujours soutenue avec patience et qui m’ont aidée de tous leurs moyens. Je remercie toute les personnes qui m’ont aidée de quelque manière possible ; Prof. Kyung-Tae Chung, Prof. Jung-hwan Oh pour leur soutien, et également mes amies Seyoung Hong, Bok-Young In, Hisako Koguré, et Minho Lee pour leur amitié constante.

KIM Sungsoon.

Contents

Remerciements 2

Résumé en Français 2

1 Introduction 13

2 Basis : definition and generating function for the size of basis 16 2.1 Basis : definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.2 Generating Function for the size of basis . . . . . . . . . . . . . . . . . . . 20

3 Basis: Classification 23 3.1 Classification of B(n) according to the value λ(P) + λ(P ) . . . . . . . . . 23 3.2 The criteria for comparing basis elements . . . . . . . . . . . . . . . . . . . 25

4 Relations between λ(P) and μ(P) for basis element P 26 4.1 Basis elements in the class E . . . . . . . . . . . . . . . . . . . . . . . . . 26 4.2 Basis elements in the class L . . . . . . . . . . . . . . . . . . . . . . . . . 29 4.3 Basis elements in the class G . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.4 Heights of the basis elements 1^{k}c in L . . . . . . . . . . . . . . . . . . . . . 35 4.5 Table of Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

5 Evaluating Heights for general partitions 39 5.1 Relations between λ(P) and μ(P) for general P . . . . . . . . . . . . . . . 39 5.2 Main results for deciding heights for general partitions . . . . . . . . . . . 40

6 Maximal basis elements below a partition 49

7 The local intervals C_{k}^{(1)} in P (n) 55

7.1 Cœurs {C_{k}^{(r)}} . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

7.1.1 The generating function for c_{k} . . . . . . . . . . . . . . . . . . . . 61 7.2 Modular sublattices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

8 The Lattice of Pieri 68 8.1 Two operations ⊗r and \r on partitions . . . . . . . . . . . . . . . . . . . 68

BIBLIOGRAPHY 74

Abstract

The lattice of partitions is not a rank poset, i.e. the maximal chains between two comparable partitions do not have the same length in general, and thus it is not straightforward to define a height (or rank) function on this lattice.

We propose a notion of height, not by using maximal chains, but by comparing partitions to special partitions in the lattice of partitions.

Our basic set of partitions, called basis, will be the set of those partitions which have only one successor. Any partition is determined by all its comparisons with the basis elements, comparisons that we can code as a boolean vector. The height is defined using this vector, but not maximal chains.

We first characterize explicitly basis elements, and enumerate them (Chapters 2 and 3). We then compute height for basis elements(results are summarized in Table 4.5). Next we give heights for general partitions (proposition 5.2.2, proposition 5.2.3 and theorem 5.2.4).

Each partition can be characterized by the maximal basis elements which are below it. We characterize them in chapter 6.

In chapter 7, we describe some special interesting intervals in the lattice of partitions and we prove that all modular sublattices are distributive.

We finish by the study of some distributive sublattices related to a formula (called Pieri’s formula) which is widely used in representation theory and in geometry.

Résumé en Français

0. Introduction

Les treillis des partitions n’est pas étagé, i.e. les chaînes maximales entre deux partitions n’ont pas la même longueur en général.

Nous proposons une hauteur en comparant les partitions aux partitions particulières qui n’ont qu’un seul successeur, que nous prenons comme ensemble de base.

Nous caractérisons tout d’abord la base (chapitres 2 et 3), donnons la hauteur des éléments de la base (tables in section 4.5), puis enfin celle des partitions générales (proposition 5.2.2, proposition 5.2.3 et theorem 5.2.4).

Dans le chapitre 6, nous donnons les éléments maximaux de la base en dessous d’une partition, ce qui caractérise cette dernière.

Au chapitre 7, nous décrivons certains intervalles particuliers et montrons que tout sous treillis modulaire du treillis des partitions est distributif.

Nous terminons par une étude des sous-treillis distributifs liés à la formule de Pieri.

1. Notations

Soit P = {p_{r} ≤ p_{r−1} ≤ … ≤ p_{1}} et Q = {q_{r} ≤ q_{r−1} ≤ … q_{1}} des partitions d’un entier positif n. L’ordre sur les partitions est défini par “P ≥ Q” ssi p_{r} ≥ q_{r}, p_{r} + p_{r−1} ≥ q_{r} + q_{r−1}, …, p_{r} + ⋯ + p_{r−i} ≥ q_{r} + ⋯ + q_{r−i}, etc... On notera également P comme un vecteur, i.e. P = (..., p_{i+1}, p_{i}, p_{i−1}...) := … p_{i+1}p_{i}p_{i−1}, ou comme un diagramme de Ferrers.

La longueur d’une partition P sera notée par l(P) et sa conjuguée est la partition P ˜ telle que le diagramme de P ˜ est le transposé du diagramme de P.([Macd]).

La somme cumulée P^{Σ} d’une partition P est définie comme le vecteur infini J = … J_{3}J_{2}J_{1} avec J_{k} = ∑_{i≥k} p_{i}. L’ordre sur les partitions peut également se définir par P ≥ Q ssi la somme cumulée P^{Σ} domine Q^{Σ} composante à composante. On définit MAX(V, W) de deux vecteurs V,W par le maximum des V et W composante à composante.

On dit que P couvre Q ssi P > Q et il n’y a aucune partition R (≠ P, Q) qui satisfait P > R > Q.

Le supremum SUP(P, Q) des deux partitions P et Q est la partition R telle que R^{Σ} = MAX(P^{Σ}, Q^{Σ}). INF(P, Q) est défini par ( SUP (P , Q )) .

Soit n un entier positif fixé et P(n) l’ensemble ordonné (qui s’appelle poset: “partially ordered set”) des partitions de n. On peut construire une structure de treillis sur l’ensemble P(n) grâce aux opérations SUP(P, Q) et INF(P, Q). Voir un exemple de treillis des partitions avec n=7. (figure 1.1)

Néanmoins, le treillis des partitions n’est pas un ensemble étagé (“ranked poset”) pour n ≥ 7. Un “ranked poset” est un ensemble ordonné tel que x ≤ y implique que tous les chemins maximaux de x à y soient de même longueur. Donc, il n’y a pas de manière évidente pour disposer planairement, par étage, les partitions de n.

2. Base : définition et sa série génératrice.

Dans le chapitre suivant, nous introduisons une notion de hauteur. On définit d’abord l’ensemble B(n) comme l’ensemble des partitions (de n) qui n’ont qu’un seul successeur et on l’appelle la “base” de P(n). On note B_{n} pour le nombre des éléments dans B(n).

On a

Lemme 0.0.1 La base B(n) de P(n) est l’ensemble des partitions d’un des types suivants:

ab^{k}c, ab^{k}, b^{k}c, b^{k} or ab

(k ≥ 2 et 1 ≤ a < b < c ∈ IN).

La série génératrice B(q) de B_{n} est

B(q) = ∑_{n≥0} B_{n}q^{n} = \frac{q^{2}(1 + q^{2} − q^{3})}{(1 − q)^{2}(1 − q^{3})} = \frac{q^{4}}{(1 − q)^{2}(1 − q^{3})} + \frac{q^{2}}{(1 − q)^{2}} .

= q^{2} + 2q^{3} + 4q^{4} + 6q^{5} + 8q^{6} + 11q^{7} + 14q^{8} + ….

qui est obtenue par la formule de récurrence

B_{n+1} − B_{n} = ([n/3] + 1)(n ≥ 3).

Maintenant, on met un ordre total sur la base (ordre anti-lexicographique). On compare chaque partition P de P(n) avec les éléments de base B(n) et on associe à P le vecteur booléen ϵ(P) qui est défini comme suit:

Soit P ∈ P(n), β ∈ B(n) et j l’indice de β dans l’ordre anti-lexicographique pour B(n).

1. si P ≥ β, on met 1 à la j-ième position de ϵ(P).

2. sinon, on met 0 à la j-ième position de ϵ(P).

On note λ(P) pour la somme des composantes de ϵ(P). (Voir figure 2.1 pour un exemple de ϵ(P) et λ(P))

Mais, la valeur λ(P) + λ(P ) n’est pas constante. Par exemple, pour n=12, B_{n}=29, λ(1344) + λ(2334)=14+16=30 > B_{n}, λ(255) + λ(22233)=9+20=29 = B_{n}, λ(11127) + λ(1111125)=10+18=28 < B_{n}. Donc, la fonction λ(P) ne respecte pas la symétrie fondamentale P → P ˜ du treillis

des partitions. On peut retrouver cette symétrie en définissant la hauteur comme suit:

Définition 0.0.2 Soit P une partition de P(n).

La hauteur h(P) de P est définie par

h(P) = λ(P) + \frac{B_{n} − λ(P) − λ(P )}{2} = \frac{B_{n} + λ(P) − λ(P )}{2}.

Remarques

1. La définition ci-dessus revient à distribuer le “défaut” (B_{n} + λ(P) − λ(P ))/2 (i.e. la valeur moyenne de B_{n} − λ(P) − λ(P )) entre P et P pour rétablir la symétrie. (Voir figure 2.2 pour la visualisation de cette idée).

2. Les hauteurs appartiennent à l’ensemble \{0, \frac{1}{2}, 1, \frac{3}{2}, ...\} = IN/2.

3. Comme P ≥ P′ implique λ(P) > λ(P′), on sait que la hauteur est compatible avec la structure “ ≥ ” sur P(n).

Définition 0.0.3 Soit P = (..., p_{i}, x, y, p_{i−3}, ...) (x < y) une partition telle que P′ = (..., p_{i}, x − 1, y + 1, p_{i−3}, ...) soit aussi une partition. On dit que P → P′ est un “pas horizontal” (noté par “h-step”)

Soit Q = (..., q_{i}, x^{k}, q_{i−k−1}...) (k ≥ 2) une partition telle que Q′ = (..., q_{i}, (x−1), x^{k−2}, (x+ 1), q_{i−k−1}...) soit une partition. Alors Q → Q′ est appelé un “pas vertical” (notée par “vstep”).

Quand on a k=2, alors P′ = Q′ ; le pas horizontal est aussi un pas vertical. Ces pas sont mis dans une troisième catégorie (notée par “hv-step”).

Définition 0.0.4 Le poids horizontal μ(P) d’une partition P = p_{l}p_{l−1}...p_{1} (l = l(P)) est la somme μ(P) = (l − 1)p_{l} + (l − 2)p_{l−1} + (l − 3)p_{l−2} + ⋯ + (1)p_{2} + (0)p_{1}.

Le poids vertical ν(P) est défini par μ(P ), i.e. le poids horizontal de la conjuguée P . (Voir figure 2.3 avec le diagramme de Ferrers)

3. Base : Classification selon la valeur λ(P)+λ(P ).

Selon la valeur λ(P)+λ(P ), pour P ∈ B(n), nous avons la classification suivante des éléments de la base:

1. L’ensemble des éléments de base avec la propriété λ(P) + λ(P ) > B_{n} est

{b^{k}(b > 3, k > 3), b^{k}c(b > 2), ab^{k}(b > 3), abbc(b > 2), ab^{k}c(b > 2)}.

On note cet ensemble par G.

2. L’ensemble des éléments de base avec la propriété λ(P) + λ(P ) = B_{n} est

{bb, ab, abb, bbc, 2^{k}, 1^{k}2, 2^{k}c, 12^{k}, a3^{k}, 12^{k}c, 122c}.

On note cet ensemble par E.

3. L’ensemble des éléments de base avec la propriété λ(P) + λ(P ) < B_{n} est

{bbb, 3^{k}, 1^{k}c}. (b > 2, c > 2)

On note cet ensemble par L.

4. Relations entre λ(P) et μ(P) pour les éléments de base P.

Nous montrons dans la suite de ce travail comment évaluer la hauteur d’une partition sans avoir à calculer le vecteur ϵ(P) (i.e. sans avoir à calculer λ(P) et λ(P )).

Pour cela, nous sommes amenés à décomposer l’ensemble des partitions en de nombreuses sous-familles: les résultats concernant les éléments de base sont rassemblés dans les tables 4.10 et 4.11.

Il y a cependant des familles de partitions pour lesquelles le calcul direct de λ(P) et λ(P ) est aisé.

Pour certaines partitions, on a besoin d’un definition suivant :

Définition 0.0.5 On définit une injection ϕ de P(n) à P(n+1) qui associe une partition dans P(n + 1) par augmentation de plus grande part de P ∈ P(n) par un.

Soit P = p_{l} … p_{2}p_{1}. On définit Orb_{ϕ}(P) comme un ensemble des partitons Q tel que Q = ϕ^{i}(P) ( i ∈ ZZ) où le plus grande part de Q, q_{1}, est ≥ p_{2} (i.e. i ∈ ZZ pour que Q soit encore une partition).

On remarque que il y a unique partition P_{s} dans cet ensemble Orb_{ϕ}(P) qui satisfait la propriété suivante :

soit n_{0} = |P_{s}| et P_{s} = p_{l} … p_{2}c (i.e. sa plus grande part est égale à c et l = l(P)). B_{n_{0}+1} − B_{n_{0}} = B_{n_{0}} − B_{n_{0}−1} = c. On appelle cette unique partition partition critique (“critical partition”) et sa plus

grande part valeur critique (“critical value”).

5. Les hauteurs pour les partitions générales dans P(n).

Dans ce chapitre, nous déterminons les hauteurs des partitions générales. On les calcule par récurrence en comparant une partition et ses successeurs, selon que l’on a un h-step, v-step, ou hv-step.

Soit P une partition dans P(n).

1. Si il y a au moins un hv-steps à partir de P : soit S_{1}, ..., S_{m} l’ensemble des successeurs de P par hv-step.

Alors on a iλ(S_{1}) = λ(S_{2}) = … = λ(S_{m}) and λ(P) = λ(S_{i}) + 1 pour tout i. On a aussi h(P) = h(S_{i}) + 1 pour tout i.

2. Si il n’y a que des v-steps entre P et ses successeurs, on a

h(P) = B_{n} − μ(P ).

On remarque aussi que , en général, si S_{v} est un successeur de P par v-step ou hv-step, on a

λ(P) = λ(S_{v}) + 1.

3. Si il n’y a que des h-steps entre P et ses successeurs, alors P = p_{l}.p_{l−1}....p_{2}.p_{1} (i.e. sa plus grande part est égale a p_{1}) où tous les p_{i} sont distincts et

• si l=3, h(P) = μ(P) = λ(P).

• si l ≥ 4,

(a) Si p_{1} < B_{n_{0}+1} − B_{n_{0}}, alors

λ(P) = B_{n} − μ(P ) et h(P) = \frac{B_{n} + μ(P) − μ(P )}{2}

ou n = |P |.
(b) Si p_{1} ≥ B_{n_{0}+1} − B_{n_{0}}, alors

λ(P) = λ(P_{s}) = B_{n_{0}} − μ((P_{s}) ) et

h(P) = h(P_{s}) = \frac{B_{n_{0}} + μ(P_{s}) − μ(P_{s} )}{2}.

où P_{s} est la partition critique unique (i.e. B_{n_{0}+1} −B_{n_{0}} = B_{n_{0}} −B_{n_{0}−1}) dans

l’orbite Orb_{ϕ}(P) et n_{0} = |P_{s}|.

4. Maintenant, on sait calculer λ(P) pour toutes les partitions dans P(n). Donc, on peut trouver la hauteur par la définition.

5. On a aussi un resultat comme suit : Si il y a des h-steps et v-steps, mais pas de hv-step, entre P et ses successeurs, soit P une partition de n et soit P_{h_{1}}, P_{h_{2}}, ..., P_{h_{l}} des successeurs de P par h-steps seulement. Alors, pour tout i : 1 ≤ i ≤ l,

• Si d = λ(P) − λ(P_{h_{i}}) est pair,

h(P) = h(P_{h_{i}}) + d/2 + 1/2.

• Si d = λ(P) − λ(P_{h_{i}}) est impair,

h(P) = h(P_{h_{i}}) + [d/2] + 1.

( où [x] est le plus grand entier ≤ x)

6. Rectrices d’une partition P ∈ P(n).

Chaque partition P est caractérisée par la liste des éléments de la base qui lui sont inférieurs (pour l’ordre “ ≥ ”). Parmi les éléments de cet ensemble, il suffit de ne considérer que les éléments maximaux (sous la partition P) qui sont appelés “les rectrices de P ”.

Dans ce chapitre, nos décrivons une méthode pour obtenir l’ensemble des rectrices d’une partition P sans être obligé de calculer ϵ(P). Pour cela, on utilise seulement le diagramme de Ferrers de la partition.

Soit P := p_{l} ≤ p_{l−1} ≤ p_{l−2} … ≤ p_{1} une partition avec l = l(P) et P := … ≤ λ_{3} ≤ λ_{2} ≤ λ_{1} sa conjuguée, considérée comme une suite infinie n’ayant qu’un nombre fini de termes non nuls.

On considère la projection ψ_{k} qui est définie comme suit:

Soit k un entier positif et P ∈ P(n) avec λ_{1} + λ_{2} + … + λ_{k}= mk + x. Alors ψ_{k} est le morphisme P → ψ_{k}(P) tel que

1. si k > l(P ), alors ψ_{k}(P) := xk^{m}.

2. si k ≤ l(P ), alors ψ_{k}(P) := xk^{m−1}y avec y = |P | − (m − 1)k − x.

Comparant {ψ_{k}(P)} avec tous les éléments de base plus petits que la partition P, on peut déduire que les rectrices de P appartiennent à l’ensemble C(P) := {ψ_{k}(P)}_{1≤k≤l(P )}. D’après le lemme 6.0.9, on sait que les rectrices de P appartiennent à l’ensemble {ψ_{k}(P) ∈ B(n); p_{l} ≤ k ≤ p_{2}}. (Voir l’algorithme avec un exemple P =23445 dans le figure 6.1)

Dans l’exemple 6.0.13, on donne les rectrices pour toutes les partitions pour n=15.

7. Les intervalles locaux Cœurs {C_{k}^{(r)}} dans P(n).

7-1. Les Cœurs Cœurs {C_{k}^{(r)}}.

Le treillis des partitions P(n) est “stable” pour n croissant au voisinage des deux sommets. La partie la plus intéressante de ce treillis se situe donc au voisinage de l’axe de symétrie médian.

C’est pourquoi nous étudions dans cette partie certains intervalles locaux dans P(n), que M.-P. Schützenberger a appelé “Cœurs”. L’intervalle local T(P) de P ∈ P(n) est l’intervalle [P, S] où S est le SUP des toutes les partitions qui couvrent P.

Lemme 0.0.6 (Clivage)

Soit P une partition, de plus grande part c, et soit T(P) l’intervalle local qu’elle détermine. Alors T(P) est l’union disjointe des deux sous-intervalles T_{1} et T_{2}, où T_{1} est l’ensemble des partitions dans T(P) dont la plus grande part est égale à c, et T_{2} est l’ensemble des partitions dans T(P) avec plus grande part égale à c-1.

Définition 0.0.7 (Cœurs {C_{k}^{(r)}})

Soit k,n des entiers positifs tel que ( \begin{matrix}k \\ 2 \end{matrix} ) ≤ n < ( \begin{matrix}k + 1 \\ 2 \end{matrix} )

Le Cœur C_{k}^{(r)} est l’intervalle local avec élément minimal la partition 123 … (k −1)(k +

r), où r = n − k − ( \begin{matrix}k \\ 2 \end{matrix} ).

Voir la table dans le figure 7.1 pour des exemples de Cœurs avec r=0 et r=1.

Nous avons restreint notre étude aux Cœurs C_{k}^{(1)} (r=1), notés plus simplement par C(k), le cardinal de C(k) étant c_{k}.

Nous montrons comment construire C(k) à partir des Cœurs précédents, i.e. C(k′) ( k′ < k). (Voir cette construction dans la section 7.1 et le figure 7.1.2). Cette construction nous permet d’avoir la formule de récurrence sur c_{k}:

c_{k+3} − c_{k+2} − (c_{k+2} − c_{k+1}) − c_{k} = 0 (k ≥ 1).

La série génératrice pour c_{k} est donc

F (x) = ∑_{k≥1} c_{k}x^{k} = (x^{3} − x^{2} + 2x)/(1 − 2x + x^{2} − x^{3}).

(Voir les premiers valeurs de c_{k} dans les figures 7.8 et figure 7.9.)

7-2. Treillis Modulaires dans P(n).

Dans la section suivante, on étudie les sous-treillis modulaires dans P(n). Ici, on utilise les notations P + Q pour SUP(P, Q) (i.e. P ∨ Q ) et P · Q pour INF(P, Q) (i.e. P ∧ Q).

Définition 0.0.8 (Treillis modulaire)

Un treillis modulaire est un treillis tel que x·(y+x·z) = x·y + x·z ( i.e. x∧(y∨(x∧z)) = (x·y) ∨ (x∧z).) pour tout x,y,z dans le treillis.

Définition 0.0.9 (Treillis distributif)

Un treillis distributif est un treillis tel que x·(y+z) = x·y + x·z ( or x+(y·z) = (x+y)·(x+z) ) (i.e. x∧(y∨z) = x∧y + x∧z or x∨(y∧z) = (x∨y)∧(x∨z) ) pour tout x,y,z dans le treillis.

On a

Théorème 0.0.10 Soit T un sous-treillis modulaire de P(n) et a,b,c des éléments distincts de T. Alors on n’a jamais a+b=b+c=a+c. (C’est à dire qu’on n’a jamais le soustreillis

a  b  c ab=ac=bc a+b=a+c=b+c

contenue dans P(n).)

Corollaire 0.0.11 Tous les sous-treillis modulaires de P(n) sont distributifs.

8. Le treillis de Pieri.

Nous terminons notre travail par l’étude de sous-treillis distributifs remarquables associés à la formule de Pieri (c’est à dire, à la multiplication d’une fonction Schur par une fonction symétrique complète ou élémentaire).

Pour P ∈ P(n), on note P ∪ r la partition obtenue en ajoutant à P un part supplémentaire égale à r.

Inversement, on définit aussi Q\r = INF {P ∈ P(n − r)|Q ≤ P ∪ r}.

Plus explicitement, la partition Q\r s’obtient comme suit: Soit Q ∈ P(n) et k,r des entiers positifs tel que q_{k+1} < r ≤ q_{k}. Alors l’opération Q\r est la partition obtenue en remplaçant les deux parts consécutives q_{k} et q_{k+1} par une part unique égale à q_{k} +q_{k+1} −r. (Voir figure 8.1 pour des exemple).

On remarque que le morphisme P → P ∪ r est une injection de P(n) à P(n + r). On a aussi un morphisme (P(n) → P(n − r)) qui associe Q\r pour chaque Q ∈ P(n). On en déduit que (P ∪ r)\r = P.

Soit r un entier positif. On introduit l’opération ⊗r sur le treillis des partitions comme suit:

Soit P une partition dans P(n). {P ⊗ r} est l’ensemble des partitions Q telles que

… ≤ p_{j} ≤ q_{j} ≤ p_{j−1} ≤ … ≤ p_{2} ≤ q_{2} ≤ p_{1} ≤ q_{1}.

où |Q| = n+r.

Autrement dit, {P ⊗ r} est l’ensemble des partitions obtenues en ajoutant r boîtes au diagramme de P horizontalement, i.e. jamais deux boîtes dans une même colonne (voir figure 8.2 pour un exemple de cette opération).

On montre que {P ⊗ r} est un sous-treillis distributif avec l’élément maximal P \r et l’élément minimal Q := (… p_{3}p_{2}(p_{1} + r)), i.e. la partition obtenue en ajoutant r à la plus grande part de P.

Par conjugaison, on peut définir aussi l’ensemble P × {1^{r}} := {Q |Q ∈ {P ⊗ r}}. (Voir la figure 8.4 pour un exemple).

L’opération “⊗r” s’interprète comme la multiplication des fonctions de Schur par la fonction complète S_{r}. En d’autres termes, on a

S_{P} · S_{r} = ∑_{Q∈{P ⊗r}} S_{Q}.

L’opération “⊗1^{r}” correspond à la multiplication par la fonction élémentaire de degré r.

Il faut noter que ces deux opérations peuvent aussi s’interpréter au niveau des représentations du groupe symétrique et du groupe linéaire, ou bien encore, en géométrie (intersection d’un cycle de Schubert par un cycle spécial).

Chapter 1

Introduction

We use the same definitions as in [Greene1].

Let P = {p_{r} ≤ p_{r−1} ≤ … ≤ p_{1}} and Q = {q_{r} ≤ q_{r−1} ≤ … q_{1}} be partitions of a positive integer n. We say that P majorizes Q, being denoted by “P ≥ Q”, if p_{r} ≥ q_{r}, p_{r} + p_{r−1} ≥ q_{r} + q_{r−1}, …, p_{r} + ⋯ + p_{r−i} ≥ q_{r} + ⋯ + q_{r−i}, etc... We also use vector notation for convenience, i.e. P = (..., p_{i+1}, p_{i}, p_{i−1}...) := … p_{i+1}p_{i}p_{i−1} as well as Ferrers diagram.

The length of the partition P will be denoted by l(P). The conjugate of a partition P is the partition P ˜ whose diagram is the transpose of the diagram of P, i.e. the diagram obtained by reflection by the main diagonal([Macd]).

For a fixed positive integer n, let P(n) be the partially ordered set ( ordered by the majorization defined above) consisting of all the partitions of n. This set has many interesting combinatorial properties. It is a lattice with top element 1^{n} and bottom element n. It is self-dual under the map which sends each partition P to its conjugate P ˜ . (See below and [Greene1] for some more explanations and see also figure 1.1 for an example of P(n).)

The “cumulated sum” P^{Σ} of P is the infinite vector J = … J_{3}J_{2}J_{1} with J_{k} = ∑_{i≥k} p_{i}. Note that the order of majorization defined above “≥” in P(n) can be written equivalently as follows: P ≥ Q iff the cumulated sum P^{Σ} of P dominate Q^{Σ} componentwisely.

Let MAX(V, W) (resp. MIN(V, W)) be the componentwise maximum (resp. minimum) of two infinite vectors V and W. The fact that the MAX of two cumulated sums is a cumulated sum of a partition can be verified by the fact that a vector V is the cumulated sum of a partition iff V_{i} − V_{i−1} ≤ V_{i+1} − V_{i} (i ≥ 2). (i.e. 2V_{i} ≤ V_{i+1} + V_{i−2} ; this is a convexity condition) Both vectors P^{Σ} and Q^{Σ} satisfies this condition: Since 2y ≤ z + x and 2y′ ≤ z′ + x′ implies 2MAX(y, y′) ≤ MAX(z, z′) + MAX(x, x′), MAX(P^{Σ}, Q^{Σ}) satisfies the condition of convexity. Thus there exists a partition K in P(n) such that K^{Σ} = MAX(P^{Σ}, Q^{Σ}).

Now one can recover a lattice structure of the set P(n): for each pair P, Q of P(n), SUP(P, Q) as the partition K such that its cumulated sum K^{Σ} is the MAX (componentwisely) of P^{Σ} and Q^{Σ}. One defines a second operation, INF, as the image of the SUP operation under conjugation of partitions: INF (P, Q) = K ⟺ SUP (P , Q )) = K . In other words, INF (P, Q) = ( SUP (P , Q )) .

1111111 111112 11122 11113  1222 1123 7 16 25  34 115  124 1114  223 133 01234 11 10 98765 5.5

Figure 1.1: an example of a lattice P(n) with n= 7

Notice that the componentwise MIN of P^{Σ} and Q^{Σ} is not necessarily the cumulated sum of a partition. Take for example, suppose P = 11226 and Q=1344. Their cumulated sums are P^{Σ}=1246 12 and Q^{Σ}=148 12. The MIN of those cumulated sums is 1146 12. This is the cumulated sum of 0326 which is not a partition. This is why INF(P, Q) should be defined by using SUP of P and Q .

It has many applications to combinatorics, statistics, algebra, group theory. For example, it is an essential tool in the theory of symmetric functions and Hall polynomials as shown by the book of Macdonald([Macd]).

On the other hand, it is not a ranked poset. A ranked poset is defined as a poset such that x ≤ y implies that all maximal chains from x to y contain the same number of elements. Having no rank, there was no evident way to decide levels to place partitions in a graphical representation of the lattice P(n). Following Greene([Greene1]), one could use lengths of maximal chains, but this works only in the neighborhoods of the top and bottom elements of P(n).

Basis : definition and generating function for the size of basis

2.1 Basis : definition

Here we introduce a notion of height by comparing partitions to some special partitions.

Given x, y in a poset P, we say that “y covers x” (or x is a successor of y) if y > x and there is no z (≠ x, y) such that y > z > x. An element is called a basis element if it covers one and only one element. [L&S] have shown that the same type of constructions applies to finite ordered sets, and define basis elements in more general case (but basis elements are not the one which covers only one element).

The set of basis elements will be called the basis of the poset. We denote this set by B(n) for P(n) and B_{n} for its cardinality.

Let P = (..., p_{i}, x, y, p_{i−3}, ...) (x < y) be a partition such that P′ = (..., p_{i}, x − 1, y + 1, p_{i−3}, ...) is a partition. Following Greene([Greene1]), we say that P → P′ is an horizontal step.

Similarly, we define vertical steps. Let Q = (..., q_{i}, x^{k}, q_{i−k−1}, ...) (k ≥ 3) be a partition such that Q′ = (..., q_{i}, (x − 1), x^{k−2}, (x + 1), q_{i−k−1}, ...) is a partition. Then Q → Q′ will be called a vertical step.

Note that if k=2, P′ = Q′, i.e. horizontal step coincides with vertical step ; we put these steps in a third category (denoted by hv − steps) and call h − step (resp. v − step) a step which is horizontal and not vertical (resp. vertical and not horizontal).

Lemma 2.1.1 The basis B(n) of P(n) is the set of partitions having one of the following types:

ab^{k}c, ab^{k}, b^{k}c, b^{k} (k ≥ 2), or ab.

with 1 ≤ a < b < c ∈ IN.

Proof

It is immediate that the above partitions cover only one element (due to the vertical step (*, b^{k},*) → (*, b − 1, b^{k−2}, b + 1,*) , except for the type ab which covers (a − 1, b + 1) only (by horizontal step). The fact that there is no other type of basic elements is also straightforward.

Take for convenience the anti-lexicographic order on B(n).

To each partition P, one associates the Boolean vector in {0, 1}^{B_{n}} of its comparison with the element β of B(n). In other words, suppose that β_{j} is the j-th basis element in the anti-lexicographic order arrangement of B(n). Then we put 1 on the j-th position of the Boolean vector if P ≥ β_{j}and 0 on the j-th position otherwise.

We denote this vector by \underline{ϵ(P)} and the sum of its components by \underline{λ(P)}.

example : Suppose n = 7, P =124. B_{7} = 11. The anti-lexicographic order on B(7) is (16, 25, 115, 34, 114, 133, 223, 11113, 1222, 111112, 1111111). So ϵ(124) = (1,1,1,1,0, ... , 0) since the first four basis elements under the partition 124 and λ(124) = 4. The following is the table of ϵ(P) and λ(P) for all the partitions P in P (7).

Basis  elements  16,25,115,34,1114,133,223,11113,1222,111112,1111111

34, 115, 25, 16, Partitions 716 25 115 34 124  1114, 133, 223, 11113, 1222,111112, 1111111 1  1 1  1 1  1 1  1 1  1 1  1 1  1 1  1 1  1 1  1  1 1  1 1  1 1 1  1 1  1 1  1 1 1  1 1  1 1  1 1 1  1 1  1 1  1 1 1  1  1  1 1  1 1  1 1 1  1  1 1  1 1  1 1 1  1  1  1 1 -  - -  - -  -  -  -  -  -  - - -  - -  -  -  -  -  -  - -  - -  -  -  -  -  -  - - -  -  -  -  -  -  - -  -  -  -  -  -  -  - -  - -  -  -  -  - - -  -  -  -  - --  -  ----  ----  ------  ------- 1 1114 133 1123 11113 1222 11122 111112 1111111  Basis 1  1  1  1  1  1 λ(P) 02334556788910 11 1 * 1* 1* 1* 1*  *  * 1*  *  *  * 223  1

For the basis elements which are below each P, we put the number 1 in each position of the basis elements. Otherwise, we have replaced the number 0 by the mark - . The elements of the basis are marked with a star.

Figure 2.1: the ϵ(P) for all P in P (7)

However λ(P) + λ(P ) is not constant. As an example, for n=12, B_{n}=29, λ(1344) + λ(2334)=14+16=30 > B_{n}, λ(255) + λ(22233)=9+20=29 = B_{n}, λ(11127) + λ(1111125)=10+18=28 < B_{n}, So λ(P) does not have the fundamental symmetry of the lattice of partitions P → P ˜ .

One can recover symmetry by defining height as follows. We shall define a height using λ(P).

Definition 2.1.2 The height h(P) of a partition P is defined as

h(P) = λ(P) + \frac{B_{n} − λ(P) − λ(P )}{2}.

Remark

• The idea of the definition above is to distribute the same value to both side P and P so that they be placed symmetrically. As an example, if P =11127 , P = 1111125 , λ(P) = 10 and λ(P ) = 18. (note that n=12, B_{n} = 29) See figure 2.2 for convenience. The value to be distributed to both side is the average value of the difference between B_{n} and λ(P) + λ(P ), which is 0.5 in the example above.

• The height function takes values in \{0, \frac{1}{2}, 1, \frac{3}{2}, ...\} = IN/2.

• We also note that if P ≥ P′, then λ(P) > λ(P′), so that the height is compatible with the order structure of P(n).

Definition 2.1.3 The horizontal weight μ(P) for each partition P = p_{l}p_{l−1}...p_{1} (l = l(P)) is the sum μ(P) = (l − 1)p_{l} + (l − 2)p_{l−1} + (l − 3)p_{l−2} + ⋯ + (1)p_{2} + (0)p_{1}. The vertical weight ν(P) for each partition P is μ(P ).

One can see directly those two weights by filling the Ferrers diagram of the partition as in the figure 2.3. (for horizontal weight, fill out the Ferrers diagram with the number k-1 for k-th row and for vertical weight, fill out with the number k-1 for k-th column. k ≥ 1)

Our aim from now on is to show how to evaluate the height of a partition, without having to compute λ(P).

We shall first do it for the elements of B(n) and then for the general partitions as the next step.

n = 12  Bn = 29 P˜ P symmetric axis  symmetric axis 14.5  29 0 :1018 3.5 4.5  p ˜ P44 : : h(P)=10.5 h(P˜ )=18.5 :

Figure 2.2: How to visualize height

For P = 223,

μ(P) = μ ( \begin{matrix}2 & 2 \\ 1 & 1 \\ 0 & 0 & 0 \end{matrix} ) = 6,

ν(P) = μ(P ) = ν ( \begin{matrix}0 & 1 \\ 0 & 1 \\ 0 & 1 & 2 \end{matrix} ) = 5.

Figure 2.3: example of horizontal and vertical weight of P =223.

2.2 Generating Function for the size of basis

We shall give the value of B_{n}, by describing an injection ϕ : B(n − 1) ↪ B(n) and computing the cardinality of B(n) \ ϕ(B(n − 1)). For x ∈ IR, note [x] is the greatest integer not bigger than x.

Lemma 2.2.1 For n ≥ 3 one has

B_{n+1} − B_{n} = ([n/3] + 1).

Proof

There exists a canonical natural injection P(n − 1) ↪ P(n) defined by increasing the last part of a partition in P(n − 1) by one.

It sends the elements of B(n − 1) of the type ab^{k} (k ≥ 3), b^{k}, b^{k}c, ab, ... to an element ab^{k−1}(b + 1), ... of B(n).

We choose to send the remaining elements of the basis abb = (a, b, b) ∈ B(n − 1) onto ϕ(abb) := (a-1,b+1,b+1) ∈ B(n) and define ϕ to be the restriction of the canonical injection to B(n − 1) otherwise.

It is clear that the difference set B(n) \ ϕ(B(n − 1)) contains elements of only the following four types:

1^{n}, 1b^{k}, (a + 1)b^{k}, (r − 1)(r + 1)^{2}.

Taking into account that the weight of such partitions must be n, we find the recursion formula involving the integral part of n/3.

Example to lemma 2.2.1:

B_{2} = 1; B_{3} − B_{2} = 2 − 1 = 1

———————————–

B_{4} − B_{3} = [\frac{3}{3}] + 1 = 1 + 1; B_{5} − B_{4} = [\frac{4}{3}] + 1 = 1 + 1; B_{6} − B_{5} = [\frac{5}{3}] + 1 = 1 + 1

—————————————

B_{7} − B_{6} = [\frac{6}{3}] + 1 = 2 + 1; B_{8} − B_{7} = [\frac{7}{3}] + 1 = 2 + 1; B_{9} − B_{8} = [\frac{8}{3}] + 1 = 2 + 1

—————————————

The recursion formula can also be put as follows:

Depending on n=3r(i.e.≡ 0 mod 3), 3r+1(i.e.≡ 1mod3), 3r+2(i.e. ≡ 2mod3),

B_{n} = \frac{3r(r + 1)}{2} − 1, B_{n} = \frac{r(3r + 5)}{2}, B_{n} = \frac{r(3r + 7)}{2} + 1, respectively.

Corollary 2.2.2 The generating function for the cardinality of the basis elements of the partition lattice is

B(q) = ∑_{n≥0} B_{n}q^{n} = \frac{q^{2}(1 + q^{2} − q^{3})}{(1 − q)^{2}(1 − q^{3})} = \frac{q^{4}}{(1 − q)^{2}(1 − q^{3})} + \frac{q^{2}}{(1 − q)^{2}} .

= q^{2} + 2q^{3} + 4q^{4} + 6q^{5} + 8q^{6} + 11q^{7} + 14q^{8} + ….

Remark

It is easy to check that ∑(B_{n+1} − B_{n})q^{n} = B(q) − qB(q) = q^{4}/(1 − q)(1 − q^{3}) + q^{2}/(1 − q).

q^{2}/(1 − q) comes from the partition of type 1^{n}. The term q^{4}/(1 − q)(1 − q^{3}), which is equal to the sum \frac{q^{4}}{1−q} + \frac{q^{7}}{1−q} + …, involves rectangular partitions. It can be visualized with Ferrers’ diagrams as follows: (figure 2.4).

The following figure shows how to obtain the elements of B(10)\ϕ(B(9)) except for 1^{10}.

P = 333, ⟶ P′ = 1333,

(showing b^{k} gives 1b^{k})

P = 12222, ⟶ P′ = 22222,

(showing ab^{k} gives (a + 1)b^{k})

P = 144, ⟶ P′ = 244,

(showing (r − 1)(r + 1)^{2} when n = 10 ≡ 1 (mod 3))

Figure 2.4: Elements of B(10)\ϕ(B(9)) shown by Ferrers’ diagram.

So, as we could see from the examples above, the way to create new basis element is to put one new box to the Ferrers diagram of the old basis elemenent in the following way : if the top row is strictly less than the next top row, then just put the new box next vacant place of the top row. When the top row has the same number of boxes as the next top row, i.e. which is the case of type b^{k}, then creating one row above the top row and put the new box on the leftmost place, making the new basis element of type 1b^{k}. The fraction q^{4}/(1 − q)(1 − q^{3}) gives the information how many there are such process for each step.

Basis: Classification

In this section, we classify the basis elements into three classes according to the property the given basis element satisfies among the following three cases: λ(P) + λ(P ) < B_{n}, λ(P) + λ(P ) = B_{n}, or λ(P) + λ(P ) > B_{n}.

If the basis element P satisfies the property λ(P) + λ(P ) = B_{n}, that means that P and P are situated symmetrically already and thus we take λ(P) as the height for P. Of course, this value λ(P) coincides with the value obtained in definition 2.1.2. If the given partition P satisfies one of the remaining properties, that means that P and P are not placed symmetrically and that is why we needed to modify the value λ(P) so that we decide the height for P as in the definition 2.1.2.

In the next section we check which basis elements satisfy which property among the three listed above and then give the exact heights in the following section.

3.1 Classification of B(n) according to the value λ(P)+ λ(P )

In the introduction, we have defined already the height for P to be

h(P) = λ(P) + \frac{B_{n} − \{λ(P) + λ(P )\}}{2}.

But it is not straightforward to figure out λ(P) for each P by first looking at the type itself of the given P. On the contrary, we can directly find μ(P) or μ(P ) from its type itself. So what we are going to do is to approach by using the number μ(P) (or μ(P ) if it is necessary), i.e. find the relations between λ(P) (or λ(P )) and μ(P)( or μ(P )) and express h(P) in terms of μ(P) or μ(P ).

We first give the list of basis elements for each property they satisfy respectively and also for each basic element P, we give a method to recognize the property it satisfies by just checking the value μ(P) itself.

We assume in the following three lemmas that 0 < a < b < c positive integers and k > 2 except for the cases specially mentioned.

Lemma 3.1.1 The set of basis elements with the property λ(P) + λ(P ) < B_{n} is

{bbb, 3^{k}, 1^{k}c}. (b > 2, c > 2)

Lemma 3.1.2 The set of basis elements with the property λ(P) + λ(P ) = B_{n} is

{bb, ab, abb, bbc, 2^{k}, 1^{k}2, 2^{k}c, 12^{k}, a3^{k}, 12^{k}c, 122c}.

Lemma 3.1.3 The set of basis elements with the property λ(P) + λ(P ) > B_{n} is

{b^{k}(b > 3, k > 3), b^{k}c(b > 2), ab^{k}(b > 3), abbc(b > 2), ab^{k}c(b > 2)}.

Definition 3.1.4 We call class L for the set of partitions satisfying the property λ(P) + λ(P ) < B_{n}, class E for the set of partitions satisfying the property λ(P) + λ(P ) = B_{n}, and class G for the set of partitions satisfying λ(P) + λ(P ) > B_{n}.

Remark

i) The first thing to note from the above lemmas is that the basis elements P containing 1234 have the property λ(P) + λ(P ) > B_{n}. But this fact is not true for general partitions (i.e. those which are not basis elements).

ii) The second thing to remark is that the basis elements with the property λ(P) + λ(P ) < B_{n} are either of rectangular type(bbb, or 3^{k}) or of hook type(1^{k}c).

iii) The last thing to remark is that a3^{k}(k > 2) is the type which is conjugate to the types abb or bbc. So, once we prove the property that abb and bbc satisfy, the same is true for a3^{k}(k > 2) automatically.

3.2 The criteria for comparing basis elements

In this section we give some criteria for comparing the basis elements in B(n). Lemma 3.2.1 Let x_{1}k_{1}^{m_{1}}y_{1} and x_{2}k_{2}^{m_{2}}y_{2} be basis elements.

Then they are comparable if and only if

• either y_{1} = y_{2}

• or x_{1} = x_{2} and m_{1} = m_{2}. Lemma 3.2.2 • Suppose we have basis elements xk_{1}^{m}y_{1}, xk_{2}^{m}y_{2}, …, xk_{l}^{m}y_{l} and let

k_{j} = max{k_{1}, k_{2}, …, k_{l}}.

Then xk_{i}^{m}y_{i} ≤ xk_{j}^{m}y_{j} for all i = 1, 2, …, l.

• Suppose we have basis elements x_{1}k_{1}^{m_{1}}y, x_{2}k_{2}^{m_{2}}y, …, x_{l}k_{l}^{m_{l}}y and let k_{j} = min{k_{1}, k_{2}, …, k_{l}}. Then x_{i}k_{i}^{m_{i}}y ≤ x_{j}k_{j}^{m_{j}}y for all i = 1, 2, …, l.

Relations between λ(P) and μ(P) for basis element P

4.1 Basis elements in the class E

Lemma 4.1.1 The basis elements of type bb, ab , abb( especially for n=3r+1, it is of type (r − 1)(r + 1)^{2} ), bbc, or 122c in the class E satisfy

λ(P) = μ(P) = h(P).

Example to lemma 4.1.1: λ(22) = μ(22) = 2. λ(45) = μ(45) = 4. λ(78) = μ(78) = 7. μ(1229) = 9 = λ(1229) = h(1229). and h(233) = λ(233) = μ(233) = 7. h(799) = λ(799) = μ(799) = 33. h(229) = λ(229) = μ(229) = 6.

Proof We prove by counting the number of basis elements among the descendents of each

given partition P to find λ(P) and by checking if this numbers coincides μ(P).

1)For a basis element P of type bb(i.e.n=2b=even), its descendents are (b − 1)(b + 1), (b − 2)(b + 2), ..., 1(n − 1), n which are basis elements

at the same time except n. So, it gives us the number b(including itself bb) for λ(P) and it is μ(P) at the same time.

2)For a basis element P of type ab, The descendents of P are {(a − 1)(b + 1), (a − 2)(b + 2), ..., 1(n − 1), n} and except

n, those are all basis elements. So, we get λ(P)=a including ab itself, and this is also μ(P). Exactly the same reason will do for P = a(b + 1) (The only change here is that the number b is replaced by the number b+1).

3)For the basis element of type abb,

Since there is a slight difference in forms depending on n=even and n=odd. We do it separately here.

3-i)First when n=a+b+b is even( hence a=even),

those are of types {11(n−2), 22(n−4), ....., aa(n−2a)}(which counts up to a), {1(n− 1), 2(n − 2), ....., \frac{n}{2} \frac{n}{2}\} (which counts up to \frac{n}{2}), \{2cc, 4(c − 2)(c − 2), ....., abb\} with c = \frac{n}{2} (which counts up to \frac{a}{2}). So, altogether there are \frac{n}{2} + \frac{a}{2} + a=2a+b which is λ(P) and h(P) at the same time.

3-ii) Next when n=odd (hence a=odd as well),

those are of types {11(n−2), 22(n−4), ....., aa(n−2a)}(which counts up to a), {1(n− 1), 2(n−2), ....., c(c+1)\} with c = \frac{n−1}{2} (which counts up to \frac{n−1}{2}), \{1cc, 3(c−2)(c−2), 5(c− 2)(c − 2), ..., abb\} (which counts up to \frac{a+1}{2}). So, altogether there are \frac{n−1}{2} + \frac{a+1}{2} + a=2a+b which is λ(P) and h(P) at the same time.

4)For the basis element P of type b^{k}c (k=1 or 2), it is easy to prove using the same method. When k=1, b^{k}c = bc and it is considered already in the case 2). When k=2, b^{k}c = bbc. Since it is the same proof for P = bbc or bb(c + 1), we do with P = bbc only here.

The partitions which are basis elements among its descendents are of type either {2bc, (2b−1)(c+1), ..., 1(n−1)} or {(b−1)(b−1)(c+2), (b−2)(b−2)(c+4), ..., 11(n−2)}. The first set counts up to 2b and the second b. So, we get λ(P) = 3b which is μ(P) at the same time.

5)For the basis element P of type (r − 1)(r + 1)^{2} with n=3r+1, this type is abb where a=r-1 and b=r+1. This case was proved already.

Now we need to consider the rest which are of type b^{k}, ab^{k}, or ab^{k}c. But depending on the value of a or b, we have different relation between μ(P) and λ(P).

Lemma 4.1.2 Suppose that k > 2. The basis element P of type 2^{k}, 1^{k}2, or ab^{k}(b = 2 or 3) in the class E satisfy

λ(P) = B_{n} − μ(P ) = h(P).

Example to lemma 4.1.2:

For P = 2^{6}, P =66, we have λ(P ) = μ(P ) = 6. and λ(P) = λ(2^{6}) = B_{12} − μ(P ) = 29 − 6 = 23 ≠ μ(P) = 30.

For P = 2^{7}, h(2^{7}) = λ(2^{7}) = 32 = B_{14} − μ(77) = 39 − 7.

In the same way, we get the following table.

Remark

Note especially from the above example that for the partition P of type a3^{k}(i.e. a=1 or 2), we always have λ(P) = B_{n} − μ(P ) = μ(P) = h(P) at the same time.

Proof partitionP μ(P) B_{n} − μ(P ) λ(P) height ——————————————————————

2^{6}  30  23  23 23
2^{7}  42  32  32 32
13^{3}  12  12  12 12
13^{4}  22  22  22 22
13^{5}  35  35  35 35
13^{6}  51  51  51 51
13^{7}  70  70  70 70
23^{3}  15  15  15 15
23^{4}  26  26  26 26
23^{5}  40  40  40 40
23^{6}  57  57  57 57
23^{7}  77  77  77 77
Figure 4.1: type of 2^{k} and ab^{k}(b = 2 or 3)

For the case P of type 2^{k} is easy cause its conjugate is of type kk. Since we had λ(kk) = μ(kk) in Proposition 4.1.1, by using the Corollary 4.1.7 we can conclude that λ(P) = B_{n} − μ(P ) = B_{n} − μ(kk).

For the case of P of type 1^{k}2, since its conjugate 1(k + 1) is of type bc which we considered in Proposition 4.1.1, and hence λ(P ) = μ(P ) = 1. Since B_{n} = λ(P) + λ(P ), we get λ(P) = B_{n} − μ(P ) = B_{n} − μ1(k + 1).

For the type a3^{k} for P, when a=1, P = 13^{k} and its conjugate is of kk(k+1) which is of type bbc we studied in Proposition 4.1.1. Then λ(P ) = μ(P ) = k + 2k = 3k and since B_{n} = λ(P) + λ(P ), we get λ(P) = B_{n} − λ(P ) = B_{n} − μ(P ).

When a=2, P = 23^{k} and P = k(k + 1)(k + 1) which is of type abb. So λ(P ) = μ(P ) = k + 1 + 2k = 3k + 1. Now again B_{n} = λ(P) + λ(P ) implies λ(P) = B_{n} − μ(P ) = B_{n} − μ(c(c + 1)) = B_{n} − c.

We recall the injection ϕ which was defined before: if P = x … z, then ϕ(P) = x … (z + 1).

Definition 4.1.3 We define Orb_{ϕ}(P) as the set of all the partitions Q such that Q = ϕ^{i}(P) (i ∈ ZZ) so that Q is still a partition (i.e. the biggest part of Q = q_{1} ≥ p_{2} when P = p_{l} … p_{2}p_{1}).

Definition 4.1.4 For each given partition P, there is only one orbit Orb_{ϕ}(P) containing this given P and also there is a unique basis element P_{s} := p_{l} … p_{2}c (l = l(P)) in this orbit satisfying the condition:

B_{n_{0}+1} − B_{n_{0}} = B_{n_{0}} − B_{n_{0}−1} = c where n = |P_{s}| and its biggest part equal to c.

We call this particular partition P_{s} “critical partition” for λ(P) and its last part c “critical value” for λ(P).

We will also say that a partition Q in Orb_{ϕ}(P) is “after the critical value” when Q = ϕ^{i}(P_{s}) for some i ≥ 0.

In the same way, a partition Q in Orb_{ϕ}(P) will be called “before the critical value” if Q = ϕ^{j}(P_{s}) for some negative integer j, (i.e. a successive inverse image of P_{s} by ϕ).

Lemma 4.1.5 The basis element P of type 2^{k}c, 12^{k}c(k > 2) in the class E satisfy 1. λ(P) = B_{n} − μ(P ) and λ(P ) = μ(P ) for all P ≤ P_{s} in Orb_{ϕ}(P).

2. λ(P) = μ(P) and λ(P ) = B_{n} − μ(P) for all P ≥ P_{s} in Orb_{ϕ}(P).

Example to lemma 4.1.5:

Thus from the above results on the basis elements in the class E, we can conclude as follows.

Lemma 4.1.6 Suppose that P is a basis element in the class E of P(n).

Then we have 1.λ(P) = μ(P). or 2.λ(P) = B_{n} − μ(P ). (Note that of course both 1. and 2. can hold at the same time.)

Corollary 4.1.7 Suppose that P is in the class E.

Then we have

1. λ(P) = μ(P) iff λ(P ) = B_{n} − μ(P).

2. λ(P) = B_{n} − μ(P ) iff λ(P ) = μ(P ).

3. λ(P) = μ(P) = B_{n} − μ(P ) iff λ(P ) = μ(P ) = B_{n} − μ(P). (Note that P is an element of the basis, but not necessarily P .)

4.2 Basis elements in the class L

Lemma 4.2.1 Suppose that k > 2. For the basis element P of type bbb, or 3^{k} (b > 2) in the class L, we have

λ(P) = B_{n} − μ(P ) and λ(P ) = B_{n} − μ(P).

Example to lemma 4.2.1: See figure 4.2 Proof For the type bbb for P: If b is even(=2s), those are {11(n−2), 22(n−4), ⋯, (b−1)(b−1)(n−2b+2)}, bbb (which

counts up to b elements), \{(n−2b−2)(b+1)(b+1), (n−2b−4)(b+2)(b+2), ⋯, 2(\frac{n−2}{2})(\frac{n−2}{2})\} (which counts up to s-1 elements), \{1(n − 1), 2(n − 2), ⋯, (\frac{n}{2})(\frac{n}{2})\} (which counts up to \frac{n}{2} elements). Now altogether, we get λ(P) = λ(bbb) = b+(s−1)+ \frac{n}{2} = b+ \frac{b}{2} −1+ \frac{3b}{2} = 3b−1.

If b is odd(=2s-1), those are {11(n − 2), 22(n − 4), ⋯, (b − 1)(b − 1)(n − 2b + 2), bbb} (which counts up to b elements), {(n − 2b − 2)(b + 1)(b + 1), (n − 2b − 4)(b + 2)(b + 2), ⋯, 1(\frac{n−1}{2})(\frac{n−1}{2})\} (which counts up to s-1 elements), \{1(n−1), 2(n−2), ⋯, (\frac{n−1}{2})(\frac{n+1}{2})\} partitionP μ(P) B_{n} − μ(P ) λ(P) height ——————————————————————

555  15  14  14  14+1/2
666  18  17  17  17+1/2
777  21  20  20  20+1/2
888  24  23  23  23+1/2
999  27  26  26  26+1/2
333  9  8  8  8+1/2
3333  18  17  17  17+1/2
33333  30  29  29  29+1/2
333333  45  44  44  44+1/2
3333333  63  62  62  62+1/2

Figure 4.2: Type of b^{k}.

(which counts up to \frac{n−1}{2} elements). Now altogether, we get λ(P) = λ(bbb) = b + (s − 1) + \frac{n−1}{2} = b + \frac{b−1}{2} − 1 + \frac{3b−1}{2} = 3b − 1.

Now since n=3b, we know that B_{n} = \frac{3b(b+1)}{2} − 1 and μ(P ) = 3\{1 + 2 + ⋯ + (b − 1)\} = 3\frac{b(b−1)}{2}. So, B_{n} − μ(P ) = 3b − 1 which is the same as λ(P) we found above in both cases.

Now we examine the type 3^{k}:

The partition 3^{k} has kkk as its conjugate and as one of its descendents also. So, it is enough to enumerate the basis elements below 3^{k} which are not the descendents of kkk. There is a direct method to count this number and this is explained in figure 4.3.

0 0 0 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 6 6  0000000 1111111 2222222 –  ==  0 0 0 -1 -2 -1 123456 12345 1234 3 k ( k-1) 2  – ( k-1) ( 1+2) == 32 (k-1) (k-2)

which shows λ(3^{k}) − λ(kkk) = μ(3^{k}) − μ(kkk).

Figure 4.3: method to find λ(3^{k}) − λ(kkk).

Corollary 4.2.2 Suppose that k > 2. For the basis element P of type bbb, or 3^{k} (b > 2) in the class L, we have

h(P) = \frac{B_{n} + λ(P) − λ(P )}{2} = \frac{B_{n} + μ(P) − μ(P )}{2}.

Lemma 4.2.3 Suppose that k > 2. For the basis element P of type 1^{k}c (c > 2) in the class L, we have

1. λ(P) = B_{n} − μ(P ) for all P ≤ P_{s} in Orb_{ϕ}(P).

2. λ(P) = B_{n} − μ(P_{s} ) for all P ≥ P_{s} in Orb_{ϕ}(P).

Example to lemma 4.2.3:

*e.g.* partitionP μ(P) λ(P) B_{n} height λ(P ) ——————————————————————

1^{5}2  15  10  11 11  1
1^{5}3  same 11  14 11  3

1^{5}4 same same 17 11+1/2 5 1^{5}5 same same 21 12 8 1^{5}6 same same 25 12+1/2 11 1^{5}7 same same 29 12+1/2 15

1^{5}8  same same 34 13  19
1^{5}9  same same 39 same  24

1^{5}X same same 44 same

Figure 4.4: type of 1^{k}c

The height for the type 1^{k}c will be treated specially in the section 4.4.

4.3 Basis elements in the class G

Lemma 4.3.1 For the basis element P of type b^{k}(b > 3, k > 3) or ab^{k}(b > 3, k > 2) in the class G, we have

λ(P) = B_{n} − μ(P ).
λ(P ) = B_{n} − μ(P).

Example 4.3.2 See figure 4.5 and figure 4.6

λ(55555) = λ(55555) = 66 = B_{20} − μ(55555) = 116 − 50. But h(55555) = 58 = (μ(55555) + λ(55555))/2 = (50 + 66)/2.

Proof

For the type b^{k}(b > 3) for P, note first that its conjugate k^{b} is also of the same type. In this case, we need only to consider the case k < b since h(P ˜ ) is determined once partitionP μ(P) μ(P ) B_{n} height ——————————————————————

22222  20  5  21 16
222222  30  6  29 23

Figure 4.5: type of b^{k}.

*e.g.* partitionP μ(P) μ(P ) B_{n} height ——————————————————————

1222  9  3  11 8
12222  16 4  17 13
2333  15 10  25 15
4555  27 36  69 30

Figure 4.6: type of ab^{k}.

h(P) is found. When k = b, P is self-dual, i.e. P = P ˜ and in this case obviously, h(P) = h(P ) = B_{n}/2.

Let us count the number of basis members among the descendents of P = b^{k}. depending on the size n=bk.

• when n = bk = 3r + 2 and b = 3s + m,

the basis elements among its descendents are {1(n − 1), …, 2b(n − 2b)}(which counts up to 2b elements), {11(n − 2), 22(n − 4), …, rr(n − 2r)}(which counts up to r elements), {2xx, 4yy, …, rzz}(which counts up to r/2 elements), {111(n − 3), 122(n−5), …, 1bb(n−2b−1)}, {222(n−6), 233(n−8), …, 2bb(n−2b−2)}, …, {(b − 1)(b − 1)(b − 1)(n − 3b + 3), (b − 1)bb(n − 3b + 1)}, {bbbb} (which counts up altogether to b + (b − 1) + ⋯ + 2 + 1 = \frac{b(b+1)}{2}, and finally there are also 3\{1 + 2 + … + (s − 1)\} + sm basis elements which is equal to 3\frac{k(k−1)}{2} + sm = \frac{b^{2}−3b−m(m−3)}{6} = \frac{b^{2}−3b+2}{6}(note that m=2 always here in this case).

So, putting them altogether, λ(P) is \frac{2b^{2}+12b−2}{3}.

Since B_{n}=\frac{r(3r+7)}{2} + 1 and μ(P ) = \frac{4b(b−1)}{2}, we get the conclusion B_{n} − μ(P ) = \frac{2b^{2}+12b−2}{3}.

• when n = bk = 3r + 1 and b = 3s + m,

the basis elements among its descendents are {1(n−1), …, 2b(n−2b)}(which counts up to 2b elements), {11(n − 2), 22(n − 4), …, rr(n − 2r)}(which counts up to r elements), {2xx, 4yy, …, (r−1)zz}(which counts up to (r−1)/2 elements), {111(n− 3), 122(n − 5), …, 1bb(n − 2b − 1)}, {222(n − 6), 233(n − 8), …, 2bb(n − 2b − 2)}, …, {(b − 1)(b − 1)(b − 1)(n − 3b + 3), (b − 1)bb(n − 3b + 1)}, {bbbb} (which counts up altogether to b + (b − 1) + ⋯ + 2 + 1 = \frac{b(b+1)}{2}, and finally there are also 3\{1 + 2 + … + (s − 1)\} + sm basis elements which is equal to 3\frac{k(k−1)}{2} + sm = \frac{b^{2}−3b+2}{6}(note that m=1 always in this case).

So, putting them altogether, λ(P) is \frac{2b^{2}+12b−2}{3}.

Since B_{n}=\frac{r(3r+5)}{2} and μ(P ) = \frac{4b(b−1)}{2}, we get the conclusion B_{n} − μ(P ) = \frac{2b^{2}+12b−2}{3}.

• when n = bk = 3r and b = 3s + m,

the basis elements among its descendents are {1(n−1), …, 2b(n−2b)}(which counts up to 2b elements), {11(n − 2), 22(n − 4), …, rr(n − 2r)}(which counts up to r elements), {2xx, 4yy, …, (r −2)zz}(which counts up to (r-2)/2 elements), {111(n− 3), 122(n − 5), …, 1bb(n − 2b − 1)}, {222(n − 6), 233(n − 8), …, 2bb(n − 2b − 2)}, …, {(b − 1)(b − 1)(b − 1)(n − 3b + 3), (b − 1)bb(n − 3b + 1)}, {bbbb} (which counts up altogether to b + (b − 1) + ⋯ + 2 + 1 = \frac{b(b+1)}{2}, and finally there are also 3\{1 + 2 + … + (s − 1)\} + sm basis elements which is equal to 3\frac{k(k−1)}{2} + sm = \frac{b^{2}−3b}{6}(note that m=0 always in this case).

So, putting them altogether, λ(P) is \frac{2b^{2}+12b−3}{3}.

Since B_{n}=\frac{3r(r+1)}{2} − 1 and μ(P ) = \frac{4b(b−1)}{2}, we get the conclusion B_{n} − μ(P ) = \frac{2b^{2}+12b−3}{3}.

Now for the proof of P = ab^{k}, we do with the same method.

Corollary 4.3.3 Suppose that k > 2. For the basis element P of type b^{k}(b > 3) or ab^{k}(b > 3) in the class G, we have

h(P) = \frac{B_{n} + λ(P) − λ(P )}{2} = \frac{B_{n} + μ(P) − μ(P )}{2} = \frac{λ(P) + μ(P)}{2}.

Lemma 4.3.4 Suppose that k > 2. For the basis element P of type b^{k}c, abbc, ab^{k}c (b > 2) in the class G, we have

1. λ(P) = B_{n} − μ(P ) and λ(P ) = B_{n} − μ(P). for all P ≤ P_{s} in Orb_{ϕ}(P).

2. λ(P) = B_{n} − μ(P_{s} ) and λ(P ) = B_{n} − μ(P_{s}) = λ(P ) = B_{n} − μ(P). for all P ≥ P_{s} in Orb_{ϕ}(P).

Example 4.3.5 See figure 4.7 and figure 4.8.

Corollary 4.3.6 Suppose that k > 2. For the basis element P of type b^{k}c, abbc, ab^{k}c (b > 2) in the class G, we have

h(P) = \frac{λ(P)+μ(P)}{2} = \frac{B_{n}+μ(P)−μ(P )}{2}. for all P ≤ P_{s} in Orb_{ϕ}(P). h(P) = \frac{λ(P_{s})+μ(P_{s})}{2} = h(P_{s}) for all P ≥ P_{s} in Orb_{ϕ}(P).

*e.g.* partitionP μ(P) μ(P ) B_{n} height —————————————————————— 33333 30 15 44 29+1/2 33334 same 18 50 31 33335 same 22 56 32 33336 same 27 62 32+1/2 33337 same 33 69 33 33338 same 40 76 33 33339 same 48 83 33

Figure 4.7: type of b^{k}c

partitionP μ(P) B_{n} − μ(P ) λ(P) height ——————————————————————

3446  21  26  26  23+1/2
3447  same  26  26  23+1/2
3448  same  26  26  23+1/2

——————————————————————

4556  27  35  35  31
4557  27  36  36  31+1/2
4558  27  37  37  32
4559  27  37  37  32

——————————————————————

5667  33  46  46  39+1/2
5668  33  48  48  40+1/2
5669  33  49  49  41

—————————————————————–

34446  36  47  47  41+1/2
34447  same  49  49  42+1/2
34448  same  50  50  43
34449  same  50  50  43
3444X  same  50  50  43

Figure 4.8: type of ab^{k}c and abbc.

4.4 Heights of the basis elements 1^{k}c in L

There remains to treat the special case 1^{k}c(c > 2).

For the basis elements P we treated so far, like ab^{k} and ab^{k}c, once the condition for the critical value for λ(P) is satisfied, then the value for λ(P) and height become fixed for all the images by ϕ. But for this type 1^{k}c(c > 2), even though the value for λ(P) be fixed with the condition for critical value for λ(P), the height still varies until another condition is satisfied. We are going to give this condition which makes the height fixed.

Definition 4.4.1 We say that we are at the critical value for height h(P) when the followiong condition is satisfied:

There is a unique partition P_{c} in the orbit Orb_{ϕ}(P) such that B_{n}−B_{n−1} = k and B_{n−1}− B_{n−2} = k − 1 where P_{c} = 1^{k}s and n = |P_{c}|.

We call the partition P_{c} satisfying this condition the critical partition for height.

Note that the critical value for height h(P) in case of type 1^{k}c(c > 2) is not depending on the last part of the partition P_{c}. We also note that the critical value for height occurs always after the critical value for λ(P).

Finding the value λ(P) is given in the former section. Here we concentrate only on how to find the h(P) using the given informations for each given P of this type.

Example: See figure 4.4

Remark

Meanwhile, there are basis elements which were not images of the injection ϕ.

Those are the partitions of type 1^{n+1} (from 1^{n} in B(n)), 1b^{k} from b^{k} in B(n),(a + 1)b^{k} (from ab^{k} in B(n)).

For the basis elements of type (a + 1)b^{k} (from ab^{k} in B(n)), since it is the same type as ab^{k} which we treated before in the Proposition 4.3.1, we are done for this case.

For the basis element of type (r − 1)(r + 1)^{2} with n=3r+1 (i.e. 1 mod 3) which shows up as new basis member with 3 steps, since its type is of abb we can refer Proposition 4.1.1 for this case.

Lemma 4.4.2 For the basis element P of type 1b^{k}, 1. If b=2 or 3,h(P) = B_{n} − μ(P ).

2. If b > 3, then, h(P) = \frac{B_{n}+μ(P)−μ(P )}{2}.

Proof

For the partition of type 1b^{k}, we use the induction on k.

For k=3, with P = 1bbb, the basis elements among its descendents are {1bbb, 1(b − 1)(b − 1)(b + 2), 1(b − 2)(b − 2)(b + 4), ⋯, 111(3b − 2)} (which counts up to b elements) and λ(bb(b+1)) we found in the previous lemma, which is μ(bb(b+1)) = 3b. So altogether, λ(1bb) = 4b. Now B_{n} − μ(P ) = \frac{b(3b+5)}{2} − 3\{1 + 2 + ⋯ + (b − 1)\} = \frac{8b}{2} = 4b which concides with λ(1bb).

Assume that this formula is true up to k-1. For k, with P = 1b^{k}, the basis elements among its descendents are {1b^{k}, 1(b−1)^{k−1}(b+k−1), 1(b−2)^{k−2}(b+2k−2), ⋯, 1^{k}(n−k)} (which counts up to b elements) and λ(b^{k−1}(b + 1)) we found in the previous proposition, which is B_{n} − μ(1k^{b}) = B_{n} − (k − 1)\{1 + 2 + ⋯ + (b − 1)\} − \frac{b(b+1)}{2} = B_{n} − \frac{b(kb−k+2)}{2}. So altogether, we have λ(P) = b + B_{n} − \frac{b(kb−k+2)}{2} = B_{n} − \frac{kb(b−1)}{2}.

Now, for B_{n} − μ(P).

B_{n} − μ(P) = B_{n} − k\{1 + 2 + ⋯ + (b − 1)\} = B_{n} − \frac{kb(b−1)}{2}. So we are done for the case 1b^{k}.

Note also that its conjugate k^{b−1}(k + 1) is of type b^{k}(b + 1). So, since we get the right formula for 1b^{k}, the formula for b^{k}(b + 1) will be obtained automatically.

Example to lemma 4.4.2:

See figure 4.9 below and figure 4.6.

partitionP μ(P) μ(P ) B_{n} height ——————————————————————

1222  9  3  11 8
12222  16  4  17 13
122222  25  5  25 20
133333  35  15  50 35
14444  28  24  56 30

Figure 4.9: type of 1b^{k}.

Note that evidently, for the last case that we did not treat yet in B(n), which is of type 1^{n}, we have

h(1^{n}) = B_{n}.

4.5 Table of Summary

We give the table of summary of all the results mentioned in the previous sections for the basis elements.

partition P  relation of λ(P) and μ(P)  height  sign(P)
bb  λ(P) = μ(P)  h(P) = μ(P)  0
ab  λ(P) = μ(P)  h(P) = μ(P)  0
abb  λ(P) = μ(P)  h(P) = μ(P)  0
bbc  λ(P) = μ(P)  h(P) = μ(P)  0
122c  λ(P) = μ(P)  h(P) = μ(P)  0
12^{k}, 13^{k}, 23^{k}  λ(P) = B_{n} − μ(P )  h(P) = B_{n} − μ(P )  0
2^{k}  λ(P) = B_{n} − μ(P )  h(P) = B_{n} − μ(P )  0
1^{k}2, 1^{k}3  λ(P) = B_{n} − μ(P )  h(P) = B_{n} − μ(P )  0
2^{k}c  λ(P ) = μ(P)  figure 4.11  0
12^{k}c  λ(P ) = μ(P)  figure 4.11  0
bbb  λ(P) = B_{n} − μ(P )  2h(P) = B_{n} + μ(P) − μ(P )  -
3^{k}  λ(P) = B_{n} − μ(P )  2h(P) = B_{n} + μ(P) − μ(P )  -
1^{k}c(c > 3)  figure 4.11  figure 4.11  -
b^{k}(b > 3, k > 3)  λ(P) = B_{n} − μ(P )  2h(P) = B_{n} + μ(P) − μ(P )  +
ab^{k}(b > 3)  λ(P) = B_{n} − μ(P )  2h(P) = B_{n} + μ(P) − μ(P )  +
b^{k}(b + 1)(b > 2)  λ(P ) = B_{n} − μ(P)  2h(P) = B_{n} + μ(P) − μ(P )  +
ab^{k}(b + 1)(b > 2)  λ(P ) = B_{n} − μ(P)  2h(P) = B_{n} + μ(P) − μ(P )  +
b^{k}c(c > b + 1)  λ(P ) = B_{n} − μ(P)  figure 4.11  +
abbc  λ(P ) = B_{n} − μ(P)  figure 4.11  +
ab^{k}c(c > b + 1)  λ(P ) = B_{n} − μ(P)  figure 4.11  +

Here k > 2, b > 2, a < b < c, sign(P) = B_{n} − λ(P) − λ(P ) unless otherwise mentioned. Figure 4.10: Table of Summary for the basis elements

partition P relation of λ(P) and μ(P)  height
2^{k}c(before P_{s})  λ(P) = B_{n} − μ(P )  2h(P) = B_{n} + μ(P) − μ(P )
at P_{s}  λ(P) = B_{n} − μ(P_{s} )  2h(P_{s}) = B_{n} + μ(P_{s}) − μ(P_{s} )
after P_{s}  λ(P) = λ(P_{s})  h(P) = h(P_{s})
12^{k}c(before P_{s})  λ(P) = B_{n} − μ(P )  2h(P) = B_{n} + μ(P) − μ(P )
at P_{s}  λ(P_{s}) = B_{n} − μ(P_{s} )  2h(P_{s}) = B_{n} + μ(P_{s}) − μ(P_{s} )
after P_{s}  λ(P) = λ(P_{s})  h(P) = h(P_{s})
1^{k}c(before P_{s})  λ(P) = B_{n} − μ(P )  h(P) = λ(P) = B_{n} − μ(P )
at P_{s}  λ(P_{s}) = B_{n} − μ(P_{s} )  2h(P_{s}) = B_{n} + λ(P_{s}) − λ(P_{s} )
after P_{s}  λ(P) = λ(P_{s})(before P_{c}) 2h(P) = B_{n} + λ(P_{s}) − λ(P )
λ(P) = λ(P_{s})(at P_{c})  2h(P_{c}) = B_{n} + λ(P_{s}) − λ(P_{c} )
λ(P) = λ(P_{s})(after P_{c})  h(P) = h(P_{c})

see below (∗)

b^{k}c(before P_{s})  λ(P) = B_{n} − μ(P )  2h(P) = B_{n} + μ(P) − μ(P )
at P_{s}  λ(P_{s}) = B_{n} − μ(P_{s} )  2h(P_{s}) = B_{n} + μ(P_{s}) − μ(P_{s} )
after P_{s}  λ(P) = λ(P_{s})  h(P) = h(P_{s})
ab^{k}c(before P_{s})  λ(P) = B_{n} − μ(P )  2h(P) = B_{n} + μ(P) − μ(P )
at P_{s}  λ(P_{s}) = B_{n} − μ(P_{s} )  2h(P_{s}) = B_{n} + μ(P_{s}) − μ(P_{s} )
after P_{s}  λ(P) = λ(P_{s})  h(P) = h(P_{s})

P_{s} is for the partition at the critical value for λ(P). (i.e. for P_{s} = … c, B_{n+1} − B_{n} = c and B_{n} − B_{n−1} = c > c − 1). P_{c} is for the partition at the critical value for height with its type 1^{k}c. (i.e. for P_{c} = 1^{k}c, B_{n} − B_{n−1} = k and B_{n−1} − B_{n−2} = k − 1). (∗) P = x … zc → λ(P ) = coeff[1/((1 − x)^{2}) + x/((1 − x^{2})(1 − x)^{2}); x^{c−2}]

Figure 4.11: Table for the basis element depending on the critical value

Evaluating Heights for general partitions

5.1 Relations between λ(P) and μ(P) for general P

Suppose P = x_{1}x_{2} … x_{k}z and Orb_{ϕ}(P) the orbit of P as we defined before. There is a unique partition P_{s} in this Orb_{ϕ}(P), having the property that B_{n+1} −B_{n} = B_{n} −B_{n−1} = c where P_{s} was written P_{s} = x_{1}x_{2} … c.

Lemma 5.1.1 1. For any partition Q ≤ P_{s} in Orb_{ϕ}(P), we have

λ(Q) = B_{m} − μ(Q ). (m = |Q|)

2. For any partition Q ≥ P_{s} in Orb_{ϕ}(P), we have

λ(P) = λ(P_{s}).

Lemma 5.1.2 Suppose P = p_{1}p_{2}...p_{l} with all p_{i}’s distinct (i.e. P has only horizontal steps to his successors).

1. If l ≤ 3, then

λ(P) = μ(P) = h(P).

2.If l > 3, then there is no regular relation between λ(P) and μ(P), but we can find the height h(P)

by using the λ(P), λ(P^{i}) , and h(P^{i}) for P^{i} a successor by h-step (i = 1, …, l − 1). The formula for h(P) is in the proposition 5.2.2.

Example to lemma 5.1.2: h(236) = λ(236) = μ(236) =7. h(246) = λ(246) = μ(246) = 8. h(347) = λ(347) = μ(347) = 10. Proof When l = 3, P is of type abc. It is easy to prove for this case.

Lemma 5.1.3 For the partition P of type x_{1}a^{k}x_{2} … y_{1}b^{m}y_{2} with k ≥ 3 and x_{i}, y_{j} mutually distinct (i.e. P has only vertical steps to his successors),

λ(P) = B_{n} − μ(P ) = h(P).

Example to lemma 5.1.3: h(11112222) = λ(11112222) = B_{12} − μ(48) = 29-4 = 25. h(1112224) = λ(1112224) = B_{13} − μ(1147) = 34-9 = 25. h(11122223) = λ(11122223) = B_{14} − μ(158) = 39-7 = 32.

Remark

• If a partition P does not contain 1234, one can decide to which set E, L it belongs.(It cannot belong to G)

1. If P is of type bbb(b ≥ 3) or its conjugates, then P is in the class L.

2. If P is a image of 1^{k}(k − 1)(k + 2)(k ≥ 2) or its conjugates, then P is in the class L.

3. Otherwise, P is in the class E.

• If a partition P contains 1234, it can be in any one of the sets E, L, G.

5.2 Main results for deciding heights for general partitions

In general, it is enough to consider only the lower half part of the lattice. (Lower half here consists of the partitions P satisfying the property μ(P) ≤ B_{n}/2.) That is because the partitions of the other half part are the conjugated partitions of this lower part and once we can decide(or approximate) the height of P, then the height of its conjugate P ˜ can be decided automatically cause we want to put these partitions symmetrically.

But, here in fact, the following properties will be true for any partition p of the lattice no matter what the given P is in upper or lower part of the lattice.

We first mention that self-conjugate partitions have by definition height B_{n}/2. So, from now on we consider only the partitions which are not self-conjugate.

We recall the notations we had in introduction: μ(P) : the horizontal weight of the partition P μ(P ) : its conjugate’s horizontal weight = vertical weight of P . h(P) : the height of the partition P ϵ(P) : the vector associated to the basis element P (we sometimes will call it the

basis-vector of P).

λ(P) : the sum of nonzero numbers(= 1) in ϵ(P).

Sometimes, steps between the given partition and his successors will be denoted by h−step(for horizontal edge), v −step(for vertical edge), and hv −step(for both horizontal and vertical steps at the same time).

Note: If one wants to see the main formula directly, see Proposition 5.2.2, proposition 5.2.3 and Theorem 5.2.4.

Remark max{h(p_{i})} + 1 <= h(P). (i=1,2,...m)

Lemma 5.2.1 When there is at least one hv-step between the given P and his successors; suppose S_{1}, ..., S_{m} are the successors from P by hv-steps, then we have h(S_{1}) = h(S_{2}) = … = h(S_{m}) and h(P) = h(S_{i}) + 1 for any i. (This result holds also for the value λ)

Example to lemma 5.2.1: h(11246) = 16 = 15 + 1 = h(2246) + 1. h(1337) = 12 + \frac{1}{2} and h(1247) = 11 + \frac{1}{2}. h(1112234) = 27 + 1/2 and h(1111334) = 26 + 1/2.

The general method to find (or approximate) the height of the given partition is as follows;

There are three kinds of P according to the type of steps joining it to its successors. Since we consider only elements here which are not basis members, each P has at least two steps(i.e. at least two successors). Note also that we get rid of the case when there is at least one step which is both horizontal and vertical since we know how to handle with it from the lemma 5.2.1 above.

So the three cases are:

1. p has only horizontal steps.

2. p has only vertical steps.

3. p has horizontal and vertical steps, but not hv-steps. (Let us call this case “mixed”)

The formula for the first two cases are simple.

Proposition 5.2.2 (For the case 1.)

This is the case when P in P(n) has successors only through the h-steps. Then P is of the form P = p_{l}.p_{l−1}....p_{2}.p_{1} with all p_{i}’s distinct and l = l(P). We have

• If l = 3, h(P) = μ(P) = λ(P).

• If l ≥ 4, we need to compare the values p_{1} and B_{n_{0}+1} − B_{n_{0}}.

1. if p_{1} < B_{n_{0}+1} − B_{n_{0}}, then P is before P_{s} in the orbit Orb_{ϕ}(P) and its height is

h(P) = \frac{B_{n} + μ(P) − μ(P )}{2} where n = |P |.

2. if p_{1} ≥ B_{n_{0}+1} − B_{n_{0}}, then P is after P_{s} in the orbit Orb_{ϕ}(P) and its height is

h(P) = h(P_{s}) = \frac{B_{n_{0}} + μ(P_{s}) − μ(P_{s} )}{2}.

Here, P_{s} is the unique partition in the orbit Orb_{ϕ}(P) which satisfies the property B_{n_{0}+1} − B_{n_{0}} = B_{n_{0}} − B_{n_{0}−1} = c where P_{s} was written as P_{s} = p_{l} … p_{2}c and n_{0} = |P_{s}|.

Example to proposition 5.2.2: h(11246) = 16 and h(2246) = 15.

h(1337) = 12+\frac{1}{2} and h(1247) = 11+\frac{1}{2}.

h(1112234) = 27 + 1/2 and h(1111334) = 26 + 1/2.

and see also figure 5.1.

*e.g.* partitionP μ(P) λ(P) B_{n} real height ——————————————————————

23456  30  41 76 35+1/2
23457  30  42 83 36
23458  30  43 91 36+1/2
23459  30  43 99 36+1/2
2345 10  30  43 107 36+1/2
2345 11  30  43 116 36+1/2

Figure 5.1: example of partitions having only horizontal steps to his successors.

Proposition 5.2.3 (For the case 2.)

If P has only v-steps to his successors, then we have

h(P) = B_{n} − μ(P ).

Remark In general, when P has at least one successor through v-step or hv-step, then we have

λ(P) = λ(v_{p}) + 1.

where v_{p} is a successor of P by v-step or by hv-step. (this holds for any P of the lattice.)

Example to proposition 5.2.3: h(11112222) = λ(11112222) = B_{12} − μ(48) = 29-4 = 25.

h(1112224) = λ(1112224) = B_{13} − μ(1147) = 34-9 = 25.

h(11122223) = λ(11122223) = B_{14} − μ(158) = 39-7 = 32.

For the most general case 3, there are two ways to get the heights of the given partition P.

1. First Method:

Now we know how to get the λ(P) for all P at this state, Then by definition, we get h(P) = \frac{B_{n}+λ(P)−λ(P )}{2}.

2. Second Method: we also have the following fact.

Theorem 5.2.4 Let P is a partition of n. Suppose that P_{h_{1}}, P_{h_{2}}, ..., P_{h_{l}} are successors of P through h-steps (here, we put the successors through v-steps aside).

Then, for any i in {1, ..., l},

• if d = λ(P) − λ(P_{h_{i}}) is even,

h(P) = h(P_{h_{i}}) + d/2 + 1/2.

• if d = λ(P) − λ(P_{h_{i}}) is odd,

h(P) = h(P_{h_{i}}) + [d/2] + 1.

(here, [x] is the greatest integer number ≤ x)

Examples: See figure 5.2.

*e.g.* partitionP P_{h_{i}} λ(P) λ(h_{i}) h(P_{h_{i}}) h(P) ——————————————————————————–

111245  111155  22  19 19  21
111245  111236  22  20 19+1/2  21
111236  111227  20  17 17+1/2  19+1/2
111236  111146  20  18 18  19+1/2
11111126  11111117 23  19 21+1/2  24

Figure 5.2: example of the most general case 3.

Since we know how to find the λ(P) for the given P, we can practice with example in figure 5.3.

Method to find the values λ(P) for each P in this example is as follows:

1. First find for the basis elements which are inside rectangles following the results in the table of summary figure 4.10.

So, we have λ(1...15) = 34 − 10 = 24, λ(1...16) = λ(1^{7}4) = 25 − (1 + 2 + 3) = 19, λ(1...17) = λ(1^{6}4) = 21 − (1 + 2 + 3) = 15, λ(1..18) = λ(1^{5}3) = 14 − (1 + 2) = 11, λ(1..19) = λ(1^{4}3) = 11 − (1 + 2) = 8, λ(1228) = μ(1228) = 9, λ(337) = μ(337) = 9, λ(2227) = λ(2224) = 21 − 9 = 21, λ(355) = μ(355) = 11, λ(1336) = λ(1334) = 25 − (1 + 1 + 1 + 2 + +2 + 2 + 3 + 3 + 3) = 13, λ(12226) = μ(12226) = B_{13} − μ(111145) = 16, λ(445) = μ(445) = 12, λ(1444) = 34 − 3(1 + 2 + 3) = 16, λ(2335) = 34 − (1 + 1 + 1 + 1 + 2 + 2 + 2 + 3 + 4) = 17, λ(2..25) = 34 − 14 = 20, λ(3334) = 34 − (1 + 1 + 1 + 1 + 2 + 2 + 2 + 2 + 3) = 19, λ(13333) = 34 − (4 + 8) = 22, λ(122224) = 34 − 10 = 24.

2. Now we go for the remaining partitions which are not basis elements.

First, since for any two partitions connected by a v-step or hv-step their difference in λ(P) values is one, we can find for all the remaining partitions except for 1156, 1147, 256. But since λ(256) = μ(256) = 5 + 4 = 9, we can get λ(1156) = 9 + 1. For 1147, since its successor by hv-step is 247 with λ(247) = μ(247) = 8, we get λ(1147) = 8 + 1.

Finally, we introduce a method to get the boolean vector ϵ(P) of a given P from the boolean vectors of his successors.

Definition 5.2.5 ϵ(P) recalled:

To each partition P, one associates the Boolean vector in {0, 1}^{B_{n}} obtained by its comparison with the element β of B(n), i.e. putting 1 in the position if P ≥ β, 0 otherwise. This boolean vector is called the basis-vector for P, being denoted by ϵ(P).

Lemma 5.2.6 Suppose P has successors P^{l} and P^{2}. Let {u_{1}, ..., u_{i}} and {v_{1}, ..., v_{j}} be indices of non zero(=1) elements from the basis-vectors of P^{1} and P^{2} respectively.

Then the basis-vector of P has nonzero components exactly for the indices on {u_{1}, ...u_{i}}∪ {v_{1}, v_{2}, ...v_{j}}.

1...15  122233 1...134  1111333 1...125  1...1234  122224 1...144 1111225  112234  22333 112333 1...135  112225  111334  22234  13333 12334 111244 111235 1...126  2...25  12244  3334 12235 111145 111226 1...17 111136  12226  111245 11335 2335  1444 2245 11236 111127  11155 2236  1345  445 1255 11146 11227  1336 1246  355 2227 11137 1...16 1...18  11128  1237  1156  346256 337 1147 1...19  11344  2344 1112224 1228  25 24 23 22 21 20 19 18 17 16 15 13 12 10 98 (v-step)  (h-step)  (hv - step)

T he partitions inside the rectangles are basis elements. Figure 5.3: example of a lattice (part) : n=13, B_{n}=34.

Here, collecting the whole results listed above, we finally get the values of heights for all the partitions. We practice again with an example of a lattice in figure 5.3.

• First, we decide the heights for basis elements according to the tables figure 4.10 and figure 4.11. So we get : h(1...15) = 25. h(122224)= 24. h(13333)=22. h(2...25)=20. h(1...16)=21. h(3334)=18.5. h(2335)=16. h(1444)=15.5. h(1...17)=17. h(1336)=12.5. h(445)=12. h(2227)=12. h(355)=5+6=11. h(1...18)=13. h(1228)=λ(1228)=μ(1228)=9. h(337)=3(1+2)=9. h(1...19)=9. h(12226) = 16.

• Now, among the partitions which are not in the basis, the followings are easily checked using the result in lemma 5.2.1 , seeing that those partitions have successors through hv-steps. h(11227)=h(2227)+1=13. h(1156)=h(256)+1=10. h(2236)=h(1336)+1=13.5. h(11236)=h(2236)+1=14.5. h(11335)=h(2335)+1=17. h(2344)=h(2335)+1=17. h(11344)=h(11335)+1=h(2344)+1=18. h(12235)=h(11335)+1=18. h(12244)=h(12235)+1=h(11344)+1=19. h(12334)=h(12244)+1=20. h(112225)=h(2...25)+1=21. h(22333)=h(13333)+1=23. h(112333)=h(22333)+1=24. h(122233)=h(122224)+1=25.

• Following results are obtained according to the proposition 5.2.3 since those are the partitions which have successors only through v-steps. h(1112224)=25. h(1111333)=25.

• The following heights are obtained by using the formula in proposition 5.2.2, i.e. for the partitions which have successors only through h-steps. h(346)=10, h(1237)=10.5 (note that in the orbit of 1237, P_{s}=1234. So h(1237)=h(1234)=(21+10-10)/2=10.5 with B_{9}=17, B_{10}=21, and B_{11}=25.) h(1345)=14 (note that in the orbit of 1345, P_{s}=1345. So h(1345)=(34+13-19)/2=14 with B_{12}=29, B_{13}=34, and B_{14}=39.) h(1246)=11.5 (note that in the orbit of 1246, P_{s}=1244. So h(1246)=(25+11-13)/2=11.5 with B_{10}=21, B_{11}=25, and B_{12}=29.)

• For the rest which are the partitions whose successors are through either h-step or v-step, but not hv-step, we use the formula in the theorem 5.2.4 or the method explained just above the theorem. So, we get the following complete list: h(11128)=10.5, h(11137)=12, h(11146)=13, h(1...127)=15, h(1...136)=16.5, h(1...145)=18, h(1...126)=19, h(111235)=19.5, h(1...135)=21, h(22234)=21.5, h(1...125)=23.5, h(1...1234)=23.5, h(1...134)=25.

• The only left-over partitions are 1147,256,1156,and 1255. 1147 has a successor 247 through hv-step. h(247)=λ(247)=μ(247)=8. So from the lemma 5.2.1, we get h(1147)=8+1=9. By the proposition 5.2.2, we get h(256)=λ(256)=μ(256)=9. By the lemma 5.2.1, we get h(1156)=h(256)+1=10. By the lemma 5.2.1, we get h(1255)=h(1246)+1=12.5

Maximal basis elements below a partition

Each partition P is characterized by the list of basis elements which are smaller than P itself. We denoted this list by ϵ(P) in the previous sections. Of course, it is enough to know the maximal elements in this list. Following [L&S], we shall call such elements the rectrices of P. From the rectrices of P and the restriction of the order “≥” on the subset of basis elements, we immediately get the vector ϵ(P).

In this section, we give a method to determine the set of rectrices of P without computing ϵ(P).

Let P be a partition P : p_{l} ≤ p_{l−1} ≤ p_{l−2} … ≤ p_{1} where l = l(P), the length of P. We recall that the weight of P is denoted by |P |. Let … ≤ λ_{3} ≤ λ_{2} ≤ λ_{1} be the conjugate partition P considered as an infinite sequence which is zero after a finite number of steps. For each k, we shall consider the quotient and remainder of λ_{1} + λ_{2} + … + λ_{k} modulo k.

Definition 6.0.7 Canonical Projection ψ_{k}: For any positive integer k and for any partition P, write λ_{1} + λ_{2} + … + λ_{k}= mk + x.

Then the Canonical Projection is the morphism P → ψ_{k}(P) such that

1. if k > l(P ), then ψ_{k}(P) := xk^{m}.

2. if k ≤ l(P ), then ψ_{k}(P) := xk^{m−1}y with y = |P | − (m − 1)k − x.

See figure 6.1 for an illustration with Ferrers diagram.

Note that ψ_{k}(P) belongs to the basis B(n), except when m=2 and x≠ 0 ( for k ≤ l(P )), or when |P | ≤ k. When m=2 ( for k ≤ l(P )), ψ_{k}(P) has the form xky which is not a basis element when x ≠ 0. When |P | ≤ k, m=0 and thus |P | = x ≤ k.

Since we know that all the basis elements smaller than P is of the form xk^{i}y (k ≥ 1), we compare with ψ_{k}(P) for each k.

For k > l(P ), it is clear that ψ_{k}(P) cannot be maximal.

The following lemma shows that the rectrices of P belong to the set {ψ_{k}(P)}_{1≤k≤l(P )}.

Lemma 6.0.8 Let x′k^{m}y′ be a basis element which is smaller than P. Then ψ_{k}(P) is a basis element which is between x′k^{m}y′ and P (i.e. x′k^{m}y′ ≤ ψ_{k}(P) ≤ P ).

Proof Let μ_{1} ≥ μ_{2} ≥ μ_{3} ≥ … be the conjugate partition of ψ_{k}(P). If x′k^{m}y′ ≤ P then x′ + (m + 1)k ≤ λ_{1} + λ_{2} + … + λ_{k} = μ_{1} + μ_{2} + … + μ_{k}. On the other hand, it is clear that two elements x′k^{m′}y′ and xk^{m}y of the same weight

are comparable iff m′ < m, or m′ = m and x′ ≤ x.

Now we can determine the maximal elements from the set {ψ_{k}(P)}_{1≤k≤l(P )} ⋂ B(n). We denote the set by C(P):= {ψ_{k}(P) ∈ B(n); 1 ≤ k ≤ l(P ) }.

Lemma 6.0.9 Let P be a partition with l = l(P), the length of P.

Let Q be any partition in the list C(P) such that Q = ψ_{i}(P) for some i < p_{l}. Then Q ≤ ψ_{k}(P) with k = p_{l}.

Let R be any partition in the list C(P) such that R = ψ_{j}(P) for some j > p_{2}. Then R ≤ ψ_{k}(P) with k = p_{2}.

Proof

1. Suppose Q = ψ_{i}(P) for some i < p_{l}.

Then it has the form i^{l}y_{1}. For k = p_{l}, ψ_{k} = k^{m_{0}}y_{2}. Since for any j (j ≤ k) k^{m′}y_{2} ≥ j^{m′}y_{3}, Q = ψ_{i}(P) ≤ ψ_{k}(P) = ψ_{p_{l}}(P).

2. Suppose R = ψ_{j}(P) for some j > p_{2}. Then it has the form xj^{m}y with j > p_{2}. For k = p_{2}, ψ_{k} = x_{1}k^{m_{1}}y. Note that both ψ_{j}(P) and ψ_{k}(P) has the same last part. Since x′j^{m′}y ≤ x_{1}k^{m_{1}}y for any j > k, the claim follows immediately.

From this lemma, we can see that the maximal elements belong to the set E(P) = {ψ_{k}(P) ∈ B(n); p_{l} ≤ k ≤ p_{2}}.

Lemma 6.0.10 Let k be an integer.

Let P^{1}, P^{2} …, P^{j} be the partitions in the list E(P) having the same length as ψ_{k}(P) and same smallest part x ≠ 0. Write each P^{i} in the form x(k_{i})^{m}y_{i} (1 ≤ i ≤ j).

Then

ψ_{k}(P) ≥ P^{1}, …, ψ_{k}(P) ≥ P^{j}
iff k ≥ k_{1}, …, k ≥ k_{j}.

Proof Suppose P^{i} := x(k_{i})^{m}y_{i} = ψ_{k_{i}}(P) with k_{i} ≤ k for all i (1 ≤ i ≤ j). Let ψ_{k}(P) = xk^{m}y.

Then clearly for any i(x ≤ k), x(k − i)^{m}(y + mi) ≤ ψ_{k}(P). Thus for each k_{i} above, we have x(k − i)^{m}(y + mi) ≤ ψ_{k_{i}}(P) = P^{i} with k_{i} = k − i. Since all the partitions here have the same weigth |P |, we must have y + mi = y_{i} for all i(1 ≤ i ≤ j). Hence, ψ_{k}(P) ≥ P^{i} for all i(1 ≤ i ≤ j). The proof of the converse is similar.

We also need a straightforward technical lemma to compare two basis elements.

=  1 2 3 4 5 k = P 234457  7 6 k = 1  k = 2  k = 3  k = 4 k = 5  k=7 k=6  4777 6667 35557 144448 144448,  35557] rectrix  rectrix rectrix 23333 11 22222 15 11111 20RECTRICES := [ 23333 10, C(P)  R(P)  (rejected) (rejected) (rejected) (rejected)

Figure 6.1: The canonical projections ψ_{k} of a partition.

Lemma 6.0.11 Suppose that s < t and y′ < y, positive integers.

Let xs^{m}y and x′t^{m′}y′ be two basis elements of same weight.

Then they are not comparable iff

μ_{1} + μ_{2} + … + μ_{s} > λ_{1} + λ_{2} + … + λ_{s}.

where μ_{1} ≥ μ_{2} ≥ … is the conjugate of xs^{m}y and λ_{1} ≥ λ_{2} ≥ … is the conjugate of x′t^{m′}y′.

Using the previous lemmas, we conclude as follows.

Proposition 6.0.12 Let P := p_{l} ≤ p_{l−1} ≤ … ≤ p_{1} be a partition. The rectrices of P, the set of which we denote by R(P), are the partitions ψ_{k}(P) in C(P) which satisfy the following conditions:

1. p_{l} ≤ k ≤ p_{2}.

2. ψ_{k}(P) is maximal (in the sense of lemma 6.0.10) among the elements in C(P) having the same length and the same first part.

Moreover, for any pair of partitions xs^{m}y and x′k^{m′}y′ in R(P), we have the following property:

• Either y ≠ y′,

• Or m = m′ and x ≠ x′.

Proof

Since the claims 1. and 2. are proved in the previous lemmas, we prove for the claim 3 only. From the list C(P), we eliminated all the ψ_{k}(P) such that 1 ≤ k < p_{1} or p_{l−1} < k by using the lemma 6.0.9. After this elimination, the remaining partitions ψ_{k}(P) in the list have distinct last part. So this is the first property of the claim 3. Now by using the lemma 6.0.10, we eliminate all the partitions with same number of parts and same first part. So this is the second property of the claim 3.

Now collecting all the claims, we give the algorithm to find the rectrices of the partition P directly from the form of P itself.

Algorithm to find the maximal basis elements below a given P

• First, we compute the ψ_{k}(P) for k=p_{l}, …, p_{2} where l = l(P). (lemma 6.0.9)

example: If P =234457, as in the figure 6.1, the projections for k=1 and k=6,7 are not necessary because these are outside the interval [p_{l} = 2, p_{2} = 5].

So by computing {ψ_{k}(P)}_{2≤k≤5}, we know that the rectrices belong to the list

[22222 15, 23333 11, 144448, 35557].

• Keep the maximal elements in each subset of C(P) having the same length and the same first part. (lemma 6.0.10)

example: If P =234457, from the above list [22222 15, 23333 11, 144448, 35557],

2222 15 must be eliminated (it is smaller than 2333 11).

Thus the set of rectrices is R(P) ={23333 11, 144448, 35557}.

The following is an example for rectrices of partitions of 15.

Example 6.0.13 The partitions inside the parenthesis are the rectrices of the partition on left. (notation : A=10, B=11, C=12,...etc.)

1E : (1E), 2D : (2D), 11D : (11D), 3C : (3C), 12C : (3C, 11D), 1..1C : (1..1C), 4B : (4B), 13B : (4B, 11D), 22B : (22B), 112B : (22B, 1..1C), 1..1B : (1..1B), 5A : (5A), 14A : (5A, 11D), 23A : (5A, 22B), 113A : (5A, 22B, 1..1C), 122A : (122A), 1..12A : (122A, 1..1B), 1..1A : (1..1A), 69 : (69), 159 : (69, 11D), 249 : (69, 22B), 1149 : (69, 22B, 1..1C), 339 : (339), 1239 : (339, 122A), 1..139 : (339, 122A, 1..1B), 2229 : (2229), 11229 : (2229, 1..1B), 1..129 : (2229, 1..1A), 1..19 : (1..19), 78 : (78), 168 : (78, 11D), 258 : (78, 22B), 1158 : (78, 22B, 1..1C), 348 : (78, 339), 1248 : (78, 339, 122A), 1..148 : (78, 339, 122A, 1..1B), 1338 : (1338), 2238 : (1338, 2229), 11238 : (1338, 2229, 1..1B), 1..138 : (1338, 2229, 1..1A), 12228 : (12228), 1..1228 : (12228, 1..1A), 1..128 : (12228, 1..19), 1..18 : (1..18), 177 : (177), 267 : (177, 22B), 1167 : (177, 22B, 1..1C), 357 : (177, 339), 1257 : (177, 339, 122A), 1..157 : (177, 339, 122A, 1..1B), 447 : (447), 1347 : (447, 1338), 2247 : (447, 1338, 2229), 11247 : (447, 1338, 2229, 1..1B), 1..147 : (447, 1338, 2229, 1..1A), 2337 : (2337), 11337 : (2337, 1..1B), 12237 : (2337, 12228), 1..1237 : (2337, 12228, 1..1A), 1..137 : (2337, 12228, 1..19), 22227 : (22227), 112227 : (22227, 1..1A), 1..1227 : (22227, 1..19), 1..127 : (22227, 1..18), 1..17 : (1..17), 366 : (366), 1266 : (366, 122A), 1..166 : (366, 122A, 1..1B), 456 : (366, 447), 1356 : (366, 447, 1338), 2256 : (366, 447, 1338, 2229), 11256 : (366, 447, 1338, 2229, 1..1B), 1..156 : (366, 447, 1338, 2229, 1..1A), 1446 : (1446), 2346 : (1446, 2337), 11346 : (1446, 2337, 1..1B), 12246 : (1446, 2337, 12228), 1..1246 : (1446, 2337, 12228, 1..1A), 1..146 : (1446, 2337, 12228, 1..19), 3336 : (3336), 12336 : (3336, 12228), 1..1336 : (3336, 12228, 1..1A), 22236 : (3336, 22227), 112236 : (3336, 22227, 1..1A), 1..1236 : (3336, 22227, 1..19), 1..136 : (3336, 22227, 1..18), 122226 : (122226), 1..12226 : (122226, 1..19), 1..1226 : (122226, 1..18), 1..126 : (122226, 1..17), 1..16 : (1..16), 555 : (555), 1455 : (555, 1446), 2355 : (555, 1446, 2337), 11355 : (555, 1446, 2337, 1..1B), 12255 : (555, 1446, 2337, 12228), 1..1255 : (555, 1446, 2337, 12228, 1..1A), 1..155 : (555, 1446, 2337, 12228, 1..19), 2445 : (2445), 11445 : (2445, 1..1B), 3345 : (2445, 3336), 12345 : (2445, 3336, 12228), 1..1345 : (2445, 3336, 12228, 1..1A), 22245 : (2445, 3336, 22227), 112245 : (2445, 3336, 22227, 1..1A), 1..1245 : (2445, 3336, 22227, 1..19), 1..145 : (2445, 3336, 22227, 1..18), 13335 : (13335), 22335 : (13335, 22227), 112335 : (13335, 22227, 1..1A), 1..1335 : (13335, 22227, 1..19), 122235 : (13335, 122226), 1..12235 : (13335, 122226, 1..19), 1..1235 : (13335, 122226, 1..18), 1..135 : (13335, 122226, 1..17), 222225 : (222225), 1122225 : (222225, 1..19), 1..12225 : (222225, 1..18), 1..1225 : (222225, 1..17), 1..125 : (222225, 1..16), 1..15 : (1..15), 3444 : (3444), 12444 : (3444, 12228), 1..1444 : (3444, 12228, 1..1A), 13344 : (3444, 13335), 22344 : (3444, 13335, 22227), 112344 : (3444, 13335, 22227, 1..1A), 1..1344 : (3444, 13335, 22227, 1..19), 122244 : (3444, 13335, 122226), 1..12244 : (3444, 13335, 122226, 1..19), 1..1244 : (3444, 13335, 122226, 1..18), 1..144 : (l3444, 13335, 122226, 1..17), 23334 : (23334), 113334 : (23334, 1..1A), 122334 : (23334, 122226), 1..12334 : (23334, 122226, 1..19), 1..1334 : (23334, 122226, 1..18), 222234 : (23334, 222225), 1122234 : (23334, 222225, 1..19), 1..12234 : (23334, 222225, 1..18), 1..1234 : (23334, 222225, 1..17), 1..134 : (23334, 222225, 1..16), 1222224 : (1222224), 1..122224 : (1222224, 1..18), 1..12224 : (1222224, 1..17), 1..1224 : (1222224, 1..16), 1..124 : (1222224, 1..15), 1..14 : (1..14), 33333 : (33333), 123333 : (33333, 122226), 1..13333 : (33333, 122226, 1..19), 222333 : (33333, 222225), 1122333 : (33333, 222225, 1..19), 1..12333 : (33333, 222225, 1..18), 1..1333 : (33333, 222225, 1..17), 1222233 : (33333, 1222224), 1..122233 : (33333, 1222224, 1..18), 1..12233 : (33333, 1222224, 1..17), 1..1233 : (33333, 1222224, 1..16), 1..133 : (33333, 1222224, 1..15), 2222223 : (2222223), 11222223 : (2222223, 1..18), 1..122223 : (2222223, 1..17), 1..12223 : (2222223, 1..16), 1..1223 : (2222223, 1..15), 1..123 : (2222223, 1..14), 1..13 : (1..13), 12222222 : (12222222), 1..1222222 : (12222222, 1..17), 1..122222 : (12222222, 1..16), 1..12222 : (12222222, 1..15), 1..1222 : (12222222, 1..14), 1..122 : (12222222, 1..13), 1..12 : (1..12), 1..1 : (1..1) Thus, each element of the lattice of partitions of 15 is characterized by a set of card

≤ 4.

The local intervals C_{k}^{(1)} in P(n)

We are interested in describing some special intervals inside the lattice of partitions.

Let P(n) be the set of the partitions of n. In this section we write each partition P ∈ P(n) in the following way: P = ...p_{3} ≤ p_{2} ≤ p_{1}

Using this notation, we first recall the definition of the SUP and INF of two partitions.

The “cumulated sum” P^{Σ} of P is the infinite vector J = 000 … J_{3}J_{2}J_{1} with J_{k} = ∑_{i≥k} p_{i}. Recall that the normal order “≥” in P(n) can be defined as follows: P ≥ Q iff the cumulated sum P^{Σ} of P dominate Q^{Σ} componentwisely.

Now one could get a lattice structure of the set P(n) by defining the SUP(P, Q) and INF(P, Q) as follows: for each pair P, Q of P(n), SUP(P, Q) as the partition K such that its cumulated sum K^{Σ} is the MAX (componentwisely) of P^{Σ} and Q^{Σ}. One defines a second operation, INF, as the image of the SUP operation under conjugation of partitions: INF (P, Q) = K ⟺ SUP (P , Q )) = K . In other words, INF (P, Q) = ( SUP (P , Q )) .

Following M.P.Schützenberger, we define local interval as follows.

Definition 7.0.14 Given a partition P, we define the \underline{local interval} T(P) of P to be the interval [ P, S ], where S is the SUP of the set of partitions which cover P.

See figure 7 for an example of a local interval. Note that the local interval T(P) is itself a lattice as well as a sublattice of P(n). The local intervals that we will consider are the ones whose bottom partition P has the maximal number of corners in P_{n}. Before we head to these special local intervals, we observe some properties the local intervals satisfy.

Remark: algorithm for finding the top element in T(P).

Here we describe how to find the top of the local interval with bottom partition P from the diagram of P. Let … λ_{3} ≤ λ_{2} ≤ λ_{1} be the conjugate partition P considered as an infinite sequence which is zero after a finite number of steps. We decompose the diagram of P into blocks of columns according to the following rule:

1. we cut between the i-th and (i+1)-th column if

K=11244 I=11226  1344 H= 11135,  H˜ = I˜ =  2334 111234 ( I , H ) ( =  =1236 (I ˜ , H ˜ ) ) ˜ INF  SUP SUP(I˜ ,H˜ )= J = the cumulated sum of I and H is= 1248 12 the cumulated sum of I= 1246 12  148 12 the cumulated sum of H =

Figure 7.1: SUP and INF of the two partitions 11226 and 1344.

11236 11146 11227  1246 11137  12372227  1336 2236

Figure 7.2: a local interval in P(13) with bottom=1237 and top=11236 • Either λ_{i−1} ≠ λ_{i} ≠ λ_{i+1} and λ_{i+1} = λ_{i+2}.

• Or λ_{i−1} = λ_{i} and λ_{i} ≠ λ_{i+1}.

2. In each block increase the left-most column by one and decrease the right-most column by one.

3. Pack horizontally to the left the new boxes which were created on the top of left-most column of each block at step 2.

See the figure 7 for an illustration with Ferrers diagram.

P = 112223335559 10 Block 1Block 2 Block 3  starting with P is (13 11 8)(5 5 )  (14 11 7)(64) (3221) (1) The sommet of the local interval (2222) (1) top element = (11122223)(445)(68 10)

Figure 7.3: example of how to find the top of the local interval starting with P

The proof that the partition obtained is the top element of the local interval T(P) is a consequence of the following observation: a partition Q which covers P if and only if the blocks of P and Q are identical except only one.

The next observation allows to express each local interval(T) as a disjoint union of two sublattices T_{1} and T_{2} of T.

Lemma 7.0.15 \underline{Clivage}

Let T be a local interval with bottom partition P and let c = p_{1}. Let T_{1} ( resp. T_{2}) be the subset of partitions with biggest part c ( resp. c-1).

Then T_{1} and T_{2} are sublattices, and T is the disjoint union of T_{1} and T_{2}.

In the following, for later use, we introduce a different method to represent T into disjoint union of T_{1} and T_{2}.

• Let P be the given partition for start and compute P^{Σ}, the cumulated sum of P.

• For each partition Q in the interval I=[P, S], compute its cumulated sum Q^{Σ}.

• Compute the difference of the cumulated sums D_{Q} = Q^{Σ} − P^{Σ}.

• If D_{Q} ends with two zeros (i.e. D_{Q} = … 00), Q is in the part T_{1} and if D_{Q} ends with 10(i.e. D_{Q} = … 10), Q is in the part T_{2}. (See figure 7.4)

sommet: start: T1  T2 The given local interval T starting with 1237, sommet=11236, being cut into two parts T  . 0000 1100 1237 11137 11227  11236 11146  2236 1336 1246 2227  1110 0110 0010 (11110)  ( ) ( ) ) ( (11100)  (11010) (11000)  ( )( )  2 1 and T

Figure 7.4: clivage of a local interval T starting with s=1237 and sommet=11236

In the following, give two partitions P, Q, we denote SUP(P, Q) by P + Q and INF(P, Q) by P Q.

Theorem 7.0.16 Let T be a local lattice with bottom partition P and top partition S. Let b be the INF of T_{2} and b̄ be the SUP of T_{1} Equivalently, b is the only partition belonging to T_{2} which covers the bottom partition of T and similarly, b̄ is the only partition in T_{1} which is covered by the top of T.

1. For each x ∈ T_{1}, one of the following properties is satisfied:

• x+b covers x.

• there exists x′ ∈ T_{1} such that x′ + b = x + b.

2. For each y ∈ T_{2}, one of the followings is satisfied:

• y covers yb̄.

• there exists y′ ∈ T_{2} such that y′b̄=yb̄.

Proof We consider the interval [x ≤ x + b]. The intersection T_{2} ∩ [x ≤ x + b] is x+b because

x+b is the smallest element z such that x ≤ z and b ≤ z, which yields z∈ T_{2}.

Thus, if the cardinality |[x ≤ x + b]| ≥ 3, it contains at least one x′ ∈ T_{1}. and we have x ≤ x′ ≤ x + b. Hence, x′ + b = x + b.

If |[x ≤ x + b]| =2, then x + b covers x. The part 2 is proved exactly in the same way.

7.1 Cœurs {C_{k}^{(r)}}

In this section, we shall describe some special local intervals with bottom element having a diagram with a maximal number of corners in P(n).

Following M. P. Schtzenberger, we shall call “Cœurs” the special local intervals.

Definition 7.1.1 “CœurC_{k}^{(r)}”:

Let k and n be positive integers such that ( \begin{matrix}k \\ 2 \end{matrix} ) ≤ n < ( \begin{matrix}k + 1 \\ 2 \end{matrix} )

The Cœur, noted “C_{k}^{(r)}”,is the local interval with bottom element 123 … (k − 1)(k + r)

where r = n − k − ( \begin{matrix}k \\ 2 \end{matrix} ).

See the table in figure 7.1 for the list of Cœurs for r=0 (with bottom elements = 1, 12, 123, 1234, 12345,.....) and for r=1 (with bottom elements =2, 13, 124, 1235, 12346,.....).

For simplicity, we denote C_{k}^{(1)} by C(k). We also denote c_{k} for the number of elements in C_{k}^{(1)}.

Method for constructing C(k) from the previous C(k′), k′ < k

The following is an algorithm to construct new C(k) from the previous C(k′) with k′ < k. Note that C(k) has bottom partition S = 1234 … (k − 1)(k + 1) and top= 11234 … (k − 1)k. Here, T_{1}, T_{2} denotes the sublattices obtained by decomposing C(k) according to the lemma 7.0.15.

k 12  11 2112 22 13 3  1123 223 133 124 1114 4  11234  2234 11144  1334 1244 11225 11135 2225 1235 5  112345 112336 112246  12346  22345 13345 112255  111445 22255 22336 22246 111346  13336111355 12445 12355 13 12 1122 1113  222 123 11233 11224  2233 1333 2224 11134  1234 112344  22344 13344 111444 112335 112245  22335 111345 22245 13335 12444 12345 n=1 n=3 n=6 n=10 n=15  n=2 n=4 n=7 n=11 n=16 (0)  (1) C (k)  C (k)

Figure 7.5: examples of Cœurs with different number of corners.

• For the subset T_{2} in C(k), it is obtained by making a copy of C(k − 1) first and then by adding to each partition copied a last part equal to ′k′.

• For the subset T_{1}, this can be cut into two subsets as follows; one subset is the set of partitions copied from C(k − 3) with extra ′(k − 2)(k − 2)(k + 1)′ being put at the end (i.e.on the right as the biggest part).

• For the remaining subset of T_{1}, make copy of the subset T_{1} of C(k-1) replacing the last part of each partition there by (k − 2)(k + 1). (See example 7.1.2 )

The following is an algorithm for recovering the previous three Cœurs by just looking at the given Cœur C(k).

• From the T_{2} part of C(k) first, by removing the biggest part we can recover C(k−1).

• From the T_{1} part of C(k), collect all the partitions P such that P^{Σ} − S^{Σ} ends with 000. Then replace their last two biggest parts p_{2}p_{1} by (p_{2} + p_{1})/2. Then those are the partitions for the T_{1} part of C(k − 1). Of course, this part could be obtained from the recursive resulf of the above rule.

• For the remaining partitions in T_{1} part of C(k), those are the partitions Q with Q^{Σ} − S^{Σ} ending with 100. By removing the last three biggest parts, we can recover C(k − 3). (See example 7.1.2 )

Example 7.1.2 See figure 7.6.

Remark So, by the construction above, we can see that the elementary forms for each parts

T_{1}, T_{2} consists of the forms as in the figure 7.7. ( Reference : [Grätzer], chapter 4,5.)

7.1.1 The generating function for c_{k}

The construction method for C(k) in the preceeding section implies the recursion formula

c_{k+3} − c_{k+2} − (c_{k+2} − c_{k+1}) − c_{k} = 0 (k ≥ 1)

which is displayed in figure 7.8 with d_{k+1} − d_{k} = c_{k−1}.

Taking into account the initial values for c_{k}, we get the following generating function:

Proposition 7.1.3 The generating function for C_{k} is

F (x) = ∑_{k≥1} C_{k}x^{k}

= (x^{3} − x^{2} + 2x)/(1 − 2x + x^{2} − x^{3}).

Remark The recursive formula is displayed in another form in figure 7.9.

k=3  k = 4 1123 223 133 124 1114  11234  2234 1334 1244 11144 11225 11135  2225 1235  2234(5) 112(336) 1113(46)  222(46)  1334(5) 1122(46)  11225(5) 22(336)  1244(5) 123(46) k = 5  1235(5) 13(336)  C(k-1) C(k-1) C(k-2)  C(k-3) 2225(5) 11135(5) 11144(5) 11234(5)

Figure 7.6: Constructing C(k) from the previous C(k′), k′ < k.

2 3  4  5  7 ** ***  * *  * *  * * * * *  * * * * *  * *

Figure 7.7: The elementary forms for T_{1}, T_{2} inside C^{(1)}(k).

dk  265 151 86 49 28 16 9 5 3 2 Ck  1  2  4  7  12  21  37  65  114 k  3  4  5  6  7  8  9  10 1  2  3  5  9  16 1  2  . . . . . .

Figure 7.8: the sequence of C_{k} with k the maximal number of corners.

0  1 1  2 2  3 = 2 + 1 3  5 = 3 + (3-2)+1 4  9 = 5 + (5-3) + 2 16 = 9 + (9-5) + 3 56  28 = 16 + (16-9)+5 7  49 = 28 + (28-16)+ 9 8  86 = 49 + (49-28) + 16 9  151 = 86 + (86-49) + 28 10  265 = 151 +(151-86) + 49 11  465 12  816 = 465 + 351 k  c k
Figure 7.9: c_{k+3} = c_{k+2} + (c_{k+2} − c_{k+1}) + c_{k} for the Cœurs C_{k}.

7.2 Modular sublattices

In this section, following M.P.Schützenberger, we consider modular sublattices of P(n) and we observe if the equality a(ab + ac + bc) = ab + ac holds for any elements a,b and c in the modular sublattices.

Definition 7.2.1 Modular lattices : A modular lattice is a lattice satisfying x(y+xz) = xy + xz for any element x,y and z of the lattice.

Definition 7.2.2 Distributive lattices : A distributive lattice is a lattice satisfying x(y+z) = xy + xz ( or x+(yz) = (x+y)(x+z) ) for any element x, y and z of the lattice.

We use the notation P + Q for the SUP(P, Q) (i.e. P ∨ Q) and P Q for INF(P, Q) (i.e. P ∧ Q).

Theorem 7.2.3 1. If a sublattice T of P(n) is modular and a,b,c are distinct elements in T such that ab=bc=ca, then we cannot have a+b=a+c=b+c. (i.e., we never have the sublattice in figure 7.10 inside P(n).)

2. All the modular sublattices of P(n) are distributive.

a  b  c ab=ac=bc a+b=a+c=b+c

Figure 7.10: modular, but not distributive

Proof

We give the proof of the claim 1 only here. The claim 2. is the immediate consequence from the claim1.

We prove this theorem by comparing the length of partition l(P) for each P = a, b, c, a + b, a + c, b + c, ab, ac, bc case by case.

First Part of the proof:

If we have l(a) = l(b) = l(c), there exists at least two of them which have the same value on their first part and also there exists at least two of them which have the same value on their last part.

In other words,

• b_{1} = c_{1} = (ab)_{1} = (bc)_{1} = (ac)_{1}. or • a_{k} = b_{k} = (ab)_{k} = (ac)_{k} = (bc)_{k}.

Case 1: If a_{1} = b_{1} = c_{1} and a_{k} = b_{k} ≠ c_{k}( c_{k} = b_{k} − 1 in fact), we have (a + b)_{k} = a_{k} = b_{k},

but (b + c)_{k} = c_{k} ≠ b_{k}. Thus, a + b ≠ b + c.(See figure 7.11 for eample with a=14479, b=13669, c=13588)

Case 2: If a_{k} = b_{k} = c_{k} and a_{1} ≠ b_{1} = c_{1}( c_{1} = a_{1} − 1 in fact), we have (a + b)_{1} = a_{1} = b_{1} + 1,

but (b + c)_{1} = b_{1} = c_{1} ≠ a_{1}. Thus, a + b ≠ b + c.((See figure 7.11 for example with a=22579, b=14479, c=13669)

Case 3: If a_{1} ≠ b_{1} = c_{1} and a_{k} = b_{k} ≠ c_{k}( a_{1} = b_{1} + 1, b_{k} = c_{k} + 1 in this case), we have

(a + b)_{1} = a_{1} ≠ (b + c)_{1} = b_{1} = c_{1}. Thus, a + b ≠ b + c.((See figure 7.11 for example with a=22245, b=13335, c=12444)

Case 4: If a_{1} = b_{1} = c_{1} and a_{k} = b_{k} = c_{k}, we have (a + b)_{1} = (a + c)_{1} = (b + c)_{1} = a_{1} =

b_{1} = c_{1} = (ab)_{1} = (ac)_{1} = (bc)_{1}, and (a + b)_{k} = (a + c)_{k} = (b + c)_{k} = a_{k} = b_{k} = c_{k} = (ab)_{k} = (ac)_{k} = (bc)_{k}. In this case, we use the induction on the number of parts of a’=a_{2}a_{3} … a_{k−1}, b’=b_{2}b_{3} … b_{k−1}, and c’=c_{2}c_{3} … c_{k−1}.

See figure 7.11. Second Part of the proof: From the discussion of the first part, we can now assume, without loss of generality,

that

l(a) ≠ l(b) = l(c) = k and l(a) = l(b) + 1 = k + 1.(Of course, we have also that l(ab) = l(ac) = l(bc) = l(b) = l(c) ≠ l(a))

So, we can see that ab is a successor of a by a v-step(if a_{1} = a_{2} = … = a_{j} for j > 2), by a h-step(if a_{1} = 1, a_{2} > 1), or by hv-step(if a_{1} = a_{2} = 1, a_{2} > 1).

Case 1: If a_{1} = a_{2} = … = a_{j} = 1 (j > 2) and a_{j+1} > 1, we have

• (a + b)_{1} = (a + b)_{2} = … = (a + b)_{j−1} = 1, (a + b)_{j} = a_{j} + 1, (a + b)_{j+1} = a_{j+1} − 1, and (a + b)_{i} = a_{i} (i=j+2,...,k+1).

• or, there is a corner l (l > 1) such that (a + b)_{1} = (a + b)_{2} = … = (a + b)_{j} = 1, (a + b)_{l−1} = a_{l−1} + 1, (a + b)_{l} = a_{l} − 1, (a + b)_{i} = a_{i} (i ≠ l, l + 1)

In both cases, we have l(a + b) = l(a) = k + 1, but l(b + c) = l(a + c) = k still. So, a + b ≠ b + c. (See figure 7.11 for example with a=111345, b=13335, c=22245).

Case 2: If a_{1} = 1 and a_{2} > 1, we have

• (a + b)_{1} = 2, (a + b)_{2} = a_{2} − 1, (a + b)_{i} = a_{i}(i = 3, ..., k + 1).

• or, there is a corner l (l > 1) such that (a + b)_{l−1} = a_{l−1} + 1, (a + b)_{l} = a_{l} − 1, (a + b)_{i} = a_{i} (i ≠ l, l + 1)

In both cases, we have l(a + b) = l(a) = k + 1, but l(b + c) = k still. So, a + b ≠ b + c. Case 3: If a_{1} = a_{2} = 1 and a_{3} > 1, we have

112335 112245  22335  13344 111345  22245  13335  12444 12345  23479  14569  13678 22579  14479  13669  13588 13579 14569XI  14488XI  13678XI 14479XI  13669XI  13588XI 13579XI

Here, XI denotes the number 11. Figure 7.11: examples for the proof of theorem • (a + b)_{1} = 1, (a + b)_{2} = 2, (a + b)_{3} = a_{3} − 1, (a + b)_{i} = a_{i}(i = 4, ..., k).

• or, there is a corner l (l > 1) such that (a + b)_{l−1} = a_{l−1} + 1, (a + b)_{l} = a_{l} − 1, (a + b)_{i} = a_{i} (i ≠ l, l + 1)

In both cases, we have l(a + b) = k + 1, but l(b + c) = k still. So, a + b ≠ b + c. Up to now, it was for the case with a_{1} = 1 = (ab)_{1}. For the case a_{1} ≠ 1, we prove in

exactly the same way.

The Lattice of Pieri

8.1 Two operations ⊗r and \r on partitions

Many properties of symmetric functions are related to properties of the set of partitions, as a lattice.

In this section we shall consider the lattice associated to “Pieri’s formula” (i.e. the multiplication of a Schur function by a complete or elementary symmetric function).

The ring of symmetric functions admits a linear basis consisting of Schur functions. The multiplicative structure of this ring can be recovered from Pieri formula.

Instead of symmetric functions, one can take as well the Grothendieck ring of classes of representations of the linear group over C : Pieri’s formula now expresses the decomposition into irreducible of the tensor product of an irreducible representation with a fundamental representation. The important fact is that there is no multiplicities in this decomposition.

Finally, the same formula occurs in geometry. In fact, Pieri was a geometer who found in 1873 that the intersection of a Schubert variety with a special Schubert variety (i.e. corresponding to a partition n or 1^{n}) is linearly equivalent to a sum of Schubert variety.

Thus figure 8.2 can be considered as expressing the product of Schur functions :

S_{134}S_{2} = S_{136} + S_{145} + S_{235} + S_{244} + S_{1135} + S_{1144} + S_{334} + S_{1234}.

or the decomposition of the tensor product of representations of Gl(C^{n}), n ≥ 4 :

S_{134} ⊗ S_{2} ≅ S_{136} ⊕ S_{145} ⊕ S_{235} ⊕ S_{244} ⊕ S_{1135} ⊕ S_{1144} ⊕ S_{334} ⊕ S_{1234}.

or the intersection of Schubert varieties (evaluated in the cohomology ring of a Grassmaniann variety) :

S_{134} ∩ S_{2} ≡ S_{136} + S_{145} + S_{235} + S_{244} + S_{1135} + S_{1144} + S_{334} + S_{1234}.

Indeed many combinatorial properties related to Pieri’s formula are a consequence of the fact that the partitions appearing in this formula constitute a sublattice. We shall develop such properties in this section.

Definition 8.1.1 For each partition P we define P ∪r as the partition obtained by adding to P one supplementary part equal to r. Conversely, we define Q\r = INF {P ∈ P(n − r)|Q ≤ P ∪ r} for each partition Q in P(n). (See figure 8.1)

Note that the morphism P → P ∪ r is an injection of P(n) into P(n + r).

We also can define morphism (P(n) → P(n − r)) which sends each Q in P(n) to the partition Q\r = INF {P ∈ P(n − r)|Q ≤ P ∪ r}. From this, we have (P ∪ r)\r = P.

example: See figure 8.1.

1144  334 1135  244 235 145 136 1234  1234  1(2+3-2)4=134 1144  1(1+4-2)4=134 K  K\2 334  (0+3-2)34=134 1135  1(1+3-2)5=125 244  (0+2-2)44=44 235  (0+2-2)35=35 145  (1+4-2)5=35 136  (1+3-2)6=36 = 134 U 2

Figure 8.1: P ∪ r, {P ⊗ r}, and K\r

Let us mention that the operations P → P ∪r and P → P \r occur in the combinatorics of Hall-Littlewood polynomials (which are a q-generalisation of Schur functions.)

Lemma 8.1.2 Let Q ∈ P(n) and k,r the positive integers such that q_{k+1} < r ≤ q_{k}. Then Q\r is the partition obtained by replacing the two consecutive parts q_{k} and q_{k+1} such that q_{k+1} < r ≤ q_{k} by a unique part equal to q_{k} + q_{k+1} − r (=s).

Proof Since q_{k+1} ≤ q_{k}, the replacement of the two parts q_{k} and q_{k+1} by a part s gives a partition P. Then by construction, P ∪ r is the partition obtained by replacing in Q the parts q_{k} and q_{k+1} by s and r (or resp. r and s) if r ≤ s (resp. if r > s)). Now since the morphism Q → Q ∪ r is bijective, it is enough to show that P ∪ r = INF {Q′ ∈ P(n)^{(r)}|Q ≤ Q′}. Since P ∪ r ≥ Q with equality iff q_{k} = r (i.e. Q ∈ P(n)^{(r)}), we just need to prove that Q′ > Q implies P′ ∪ r ≥ P ∪ r(with equality iff q′_{i} = q_{i} for all i ≠ k, k + 1 where q′ is denoted by the i-th part of Q′). We prove this by comparing the cumulated sums Q^{′Σ} and Q^{Σ} for each Q′ > Q which are different only on the two indices i, j > i with three possible cases for such indices; j ≥ i ≥ k + 1, j ≥ k + 1 and k ≥ i, k ≥ i, j.

Definition 8.1.3 The operation “⊗r”.

Let r ≥ 0 and P a partition of n. We define {P ⊗ r} to be the set of partitions Q such that

… ≤ p_{j} ≤ q_{j} ≤ p_{j−1} ≤ … ≤ p_{2} ≤ q_{2} ≤ p_{1} ≤ q_{1}.

where |Q| = n+r.

In other words, the partitions in {P ⊗ r} are all the partitions obtained by adding r boxes to the diagram of P horizontally, i.e. with no two boxes in the same column.([Macd])

Example: {134 ⊗ 2}

1234 1144  334 244 1135  235 145 136

Figure 8.2: {134 ⊗ 2} with Ferrers diagram

Theorem 8.1.4 Let P ∈ P(n) be a partition and r a positive integer. Then the set {P ⊗ r} is a distributive sub-lattice of the lattice P(n + r). Its maximum element is P ∪ r and its minimum element is the partition (… p_{3}p_{2}(p_{1} + r)), i.e. the partition obtained from P adding the r boxes to the bottom row of the Ferrers diagram of P.

Proof Let Q be a partition in P ⊗r and let D := Q−P = (… q_{3} −p_{3}, q_{2} −p_{2}, q_{1} −p_{1}). Let us denote the i-th part of D by D_{i}.

The condition in the definition 8.1.3 translate into Pieri’s conditions:

D_{j} ≥ 0; ∑ D_{j} = r; p_{j} − p_{j+1} ≥ D_{j+1}(j ≥ 1).

1144  334 1135  244  1010  0200 1001  0110 0002 235 145 136  0011 0101  0002 0012 0112  0122 1112 1122  0222 1100  1222 1234

Figure 8.3: {134 ⊗ 2}, { D }, { D^{Σ} } from left to right

By considering the cumulated sum F=D^{Σ} = Q^{Σ} − P^{Σ}, these conditions are equivalent to say that

F_{1} = r; F_{j+1} ≤ F_{j}; F_{j+1} ≤ p_{j}(j ≥ 1).

with the convention that p_{j} = 0 for big enough j in the last inequality of the condition.

We consider the set F = F(P, r) of sequences F satisfying the above conditions. We claim that F is a distributive lattice with the distributive operations SUP and INF. First, we see that its minimal element is F such that F_{1} = r and F_{j} = 0 for j ≥ 2. Its maximal element is F’ such that F′_{j} = p_{j} if p_{j} ≤ r and F′_{j} = r otherwise.

Associating to each F∈ F the unique sequence D such that F=D^{Σ}, we have a morphism F → P +D from the lattice of F to P(n). It sends MAX to SUP and MIN to INF. Hence, we see that P ⊗ r is a distributive sub-lattice of P(n).

To find the supremum of {P ⊗ r}, we have to find the MAX of F. So we just need to check if D = (P ∪r)−P satisfies the following conditions; D_{j} = p_{j} −p_{j+1}(p_{j} ≤ r); D_{j+1} = r − D_{j}^{Σ} for the biggest part j such that p_{j} > r and D_{j} = 0 otherwise. This condition shows that F=D^{Σ} is the MAX in F. To find INF(P ⊗ r), it is immediate.

By conjugation, one defines also the set P ⊗ {1^{r}} to be {Q |Q ∈ {P ⊗ r}}.

example:See figure 8.4

Algorithm for Q\r

• Find the first index j such that q_{j} ≤ r and q_{j+1} ≥ r.

• Delete the two parts q_{j}, q_{j+1} and replace them by a part equal to q_{j} + q_{j+1} − r.

So the new partition Q\r is the partition N , denoting the i-th part of N by N_{i}, such that N_{i} = q_{i}(i ≤ j), N_{j} = q_{j} + q_{j+1} − r, N_{i} = q_{i+1}(i ≥ j + 1). (See figure 8.5 and figure 8.1 for an example).

1234  334 1144 1135  244 235 145 136  1333 12223 111223 2224 11224  1234  2233 11233

Figure 8.4: {P ⊗ r} and {P ⊗ 1^{r}} Proposition 8.1.5 Let n,r be two positive integers, and φ the restriction of the operation \r to P(n + r) → P(n). Let P ∈ P(n) and F(P) be the set of partitions Q ∈ P(n + r) such that q_{j} = p_{j} except for some two consecutive components.

Then the set φ^{−1}(P) ∩ {P ⊗ r} is equal to {(P ∪ r)} ∪ F(P).

(See figure 8.5 for an example).

Example: 12579\5,

3579 2679  3489  356X  11589  1166X  12399  1247X  1255XI(XI=11) (12399\5=1279) 3579\5=379, 1256X\5=126X, 2679\5=379, 3489\5=379, 356X\5=36X, 11589\5=1189, 1166X\5=126X,1247X\5=126X, 1255X\5=125X, 1256X(X=10) 12579(12579\5=1279) 12489(12489\5=1279), 11679(11679\5=1279),

Figure 8.5: Fiber of P =1279 in {1279 ⊗ 5}.

Bibliography

[Aigner] M. Aigner, Combinatorial Theory, a Series of comprehensive studies in Mathematics, Springer-Verlag, 234(1942)

[Andrews] G. Andrews, The Theory of Partitions, Encyclopedia for Mathematics, Addison Wesley, 2(1979)

[Brylawski] T. Brylawski, On the Lattice of the integer partition, Discrete Math. 6(1973), 201

[Grätzer] G. Gr^{}ätzer, General Lattice Theory, Mathematische Reiche Band 52, Birkkhauser Verlag Basel und Stuttgart, 52(1978)

[Greene1] C.Greene and D.Kleitman, Longest chains in the Lattice of Integer Partitions ordered by Majorization , Europ. J . Combinatorics 7(1986), 1-10

[Greene2] C.Greene, A Class of Lattices with Möbius Function +- 1,0, Europ. J. Combinatorics 9(1988), 225 1 (1992), 7-22

[Jónsson] B. J^{}ónsson, Equational Classes of Lattices, Math. Scand. 22(1968), 187-196.

[Jónsson] B. J^{}ónsson and J.E.Kiefer, Finite sublattices of a free lattice, Europ. J. Combinatorics 9(1988), 225 1 (1992), 7-22

[L&S] A. Lascoux, M-P. Sch^{}ützenberger, Treillis et bases des groupes de Coxeter, Rapport de recherche au LITP, Paris 7, LIPT 95/23(1995)

[MacM] P.A.MacMahon, Divisors of Numbers and their continuations in the theory of Partitions, Proceedings of London Math. Soc. No. 17, pp75-113(1919)

[Macd] Ian G. Macdonald, Symmetric Functions and Hall Polynomials, Clarendon Press, Oxford 1(1979)

[Sch1] M-P. Sch^{}ützenberger, Sur certains axiomes de la théorie des structures, C.R.Acad. Sci Paris, tome 221 (1945) : 218-220.

[Sch2] M-P. Sch^{}ützenberger, Sur certains treillis gauches., C.R.Acad. Sci Paris Séance du 6janvier 1947 : 776-778, tome 224(No 1).

[Sch3] M-P. Sch^{}ützenberger, Remarques sur la notion de clivage dans les structures algébriques et son application aux treillis, C.R.Acad. Sci Paris Séance du 20 janvier 1947 : 512-514, tome 224(No 3).

[Sch3] M-P. Sch^{}ützenberger, Sur certaines applications remarquables des treillis dans eux-mêmes, C.R.Acad. Sci Paris Séance du 3 novembre 1948 : 1008-1010, tome 227(No 18).