Actions of the symmetric group on sets generated by Yamanouchi words

Olga Azenhas,^{1} Departamento de Matemática, Universidade de Coimbra 3001-454 Coimbra, Portugal Ricardo Mamede^{2} Departamento de Matemática, Universidade de Coimbra 3001-454 Coimbra, Portugal

Abstract

In this paper, we consider words in a finite totally ordered alphabet which, restricted to a two consecutive letters subalphabet, are either Yamanouchi or dual Yamanouchi. We introduce the concept of sequence of indexing sets of a word, and we use it to identify, through a monoid isomorphism, words with classes of sequences of finite sets in ℕ. Under this identification, we describe actions of the symmetric group on sets of sequences of finite sets in ℕ, generated by indexing sets of Yamanouchi words. The indexing sets of Yamanouchi and dual Yamanouchi words, in a two letters alphabet, are dual comparable pairs under convenient ordering in the power-set of {1, …, n}. Thereby we define operations on comparable pairs of indexing sets which, by fixing a longest subword, both Yamanouchi and dual Yamanouchi, transform a comparable pair into its dual. Under these operations, each triple of indexing sets of a Yamanouchi word, in a three-letters alphabet, generates a set of indexing sets such that we have an action of the symmetric group S_{3}. This generation is equivalent to an explicit decomposition of indexing sets of Yamanouchi words, in a three-letters alphabet. A special case of this decomposition turns out the action of the symmetric group, described by A. Lascoux and M. P. Schutzenberger in the platic monoid, [10] and [12], when restricted to words generated by Yamanouchi words. Our analysis does not use properties of the platic monoid, but they do rely on properties of the sets generated by indexing sets of a Yamanouchi word. In the case of the action of S_{3}, σ-Yamanouchi words are characterized.

The action of the symmetric group S_{3}, on words or Young tableaux, has a natural matrix translation afforded by the obvious permutation action on a sequence of matrices, over a local principal ideal domain. This permutation action gives rise to the mentioned decomposition of the indexing sets of a Yamanouchi word, in a three-letters alphabet. This is the content of a subsequent paper.

1Work supported by CMUC/FCT.

2Work supported by CMUC/FCT.

1 Introduction

Let M be the set of all rearrangements of a sequence of t fixed integers in {1, ..., n}. We consider those Young tableaux T , of weight (m_{1}, ..., m_{t}) in M, arising from a sequence of products of matrices, over a local principal ideal domain with maximal ideal (p),

(Δ_{a}, Δ_{a}U(pI_{m_{1}} ⊕ I_{n−m_{1}}), Δ_{a}U ∏_{k=1}^{2}(pI_{m_{k}} ⊕ I_{n−m_{k}}), ..., Δ_{a}U ∏_{k=1}^{t}(pI_{m_{k}} ⊕ I_{n−m_{k}})),

where Δ_{a} is an n × n diagonal matrix with invariant partition a, and U is an n × n unimodular matrix. When (m_{1}, ..., m_{t}) is by decreasing order, T is a Littlewood-Richardson tableau [1], [2]. Now, for each partition a and n × n unimodular matrix U, let T_{(a,M)}(U) be the set of all sequences of matrices, as above, with (m_{1}, ..., m_{t}) running over M. The symmetric group S_{t} acts on M and on T_{(a,M)}(U) in the obvious way. The action of the symmetric group on T_{(a,M)}(U) is equivalent to an action of the symmetric group on the set of Young tableaux, realized by the sequences of matrices in T_{(a,M)}(U). When t = 3, the action of S_{3}, on T_{(a,M)}(U), is described by an explicit decomposition of the indexing sets of the Littlewood-Richardson tableau in T_{(a,M)}(U). This decomposition generates the remaining indexing sets of the Young tableaux in T_{(a,M)}(U). The corresponding words, restricted to a two consecutive letters subalphabet, are either Yamanouchi or dual Yamanouchi. This is analyzed in a subsequent paper.

A. Lascoux and M. P. Schutzenberger, [10], [12], have described an action of the symmetric group on Young tableaux by defining operators σ_{k}, k = 1, …, t−1, acting on words in a totally ordered alphabet {1, …, t}. Here we look at the action of the operator σ_{k}, on a word w, as follows: first extract from w a subword w′ that contains the letters k and k + 1 only; second, in the word w′ remove a longest subword, both Yamanouchi and dual Yamanouchi, in the two-letters subalphabet {k, k +1}. As a result, we obtain a subword of the type k^{r} (k+1)^{s}. Then, we replace it with the word k^{s} (k+1)^{r} and, after this, we recover all the removed letters of w, including the ones different from k and k + 1. In [10] and [12], the determination of a longest subword of w′, both Yamanouchi and dual Yamanouchi, in a two-letters subalphabet {k, k + 1}, is done by bracketing, consecutively, in w′ every factor k + 1 k. The bracketed letters, in w′, constitute a desired both Yamanouchi and dual Yamanouchi subword. The proof that the operators σ_{k} satisfy the relations of the symmetric group is done by using properties of the plactic monoid.

The motivation of our analysis is the decomposition of the indexing sets of a Littlewood-Richardson tableau, achieved in the matrix problem, described above, in the cases t = 2 ([3], [5]), and t = 3. Introducing the notion of sequence of indexing sets of a word, and establishing a monoid isomorphism between words and classes of sequences of finite sets in ℕ, we rediscover, in theorem 4.4, the aforesaid decomposition in the matrix setting. We define a lattice on the power-set of {1, …, n}, and consider its dual as well. In this lattice and its dual, comparable pairs (A, B) are, respectively, indexing sets of Yamanouchi and dual Yamanouchi words, in a two-letters alphabet. We describe operations on comparable pairs (A, B), afforded by their witnesses, such that the corresponding Yamanouchi or dual Yamanouchi words are mapped into a dual word. These operations have the property of fixing a pair (A′, B′), simultaneously comparable in the lattice and its dual, with A′ ⊆ A, B′ ⊆ B such that |A′| = |B′| = min{|A|, |B|}. These operations, on comparable pairs, are equivalent to put brackets on the letters of the corresponding words, in a two-letters alphabet, such that the bracketed letters define a longest subword, both Yamanouchi and dual Yamanouchi. Given indexing sets of a Yamanouchi word in a three-letters alphabet, we generate, under those operations, a set of indexing sets (see definition 4.2 and theorem 4.2), in order to have an action of the symmetric group S_{3}. The generation of this set is equivalent to a decomposition of the given indexing sets as in the matrix setting.

Witnesses, of a comparable pair (A, B), are ordered by their images, as subsets of {1, …, n}. Minimal witnesses as well as their dual, afford the same involution Θ^{∗}, on the set of the pairs of indexing sets of all Yamanouchi and dual Yamanouchi words of length ≤ n, in a two-letters alphabet. The action of the involution Θ^{∗}, on a comparable pair, can be described indeed in several ways, according to the chosen minimal witness or its dual. In particular, there is one minimal witness (and its dual) whose translation to words is the operator σ_{1}, restricted to Yamanouchi and dual Ysamanouchi words, defined in the plactic monoid, [10], [12]. Nevertheless, it turns out that, if (A, B) are indexing sets of a word w, in a two-letters alphabet {1, 2}, then Θ^{∗}(A, B) are indexing sets of σ_{1}(w). Considering sequences of finite sets (J_{1}, …, J_{t}), such that (J_{k}, J_{k+1}) is a comparable pair, for k = 1, …, t − 1, we put Θ_{k}^{∗}(J_{1}, …, J_{t}) =: (J_{1}, …, Θ^{∗}(J_{k}, J_{k+1})^{∗}, …, J_{t}), for k = 1, …, t − 1. The involutions Θ_{k}^{∗}, k = 1, …, t − 1, satisfy the relations of the symmetric group. We prove it using properties of a set generated by indexing sets of a Yamanouchi word.

The paper is organized as follows. In the section 2, the power-set of {1, …, n} is equipped with the structure of lattice, and its dual is considered. We introduce the notion of witness of a comparable pair (A, B), and give procedures to calculate minimal witnesses of such pairs as well for their dual. In particular, we give a procedure which gives rise to the operator σ_{1} in the platic monoid. A series of results, concerning minimal witnesses, are proved in order to support the last section.

In section 3, we define sequence of indexing sets of words and Young tableaux, and transfer to words those operations on indexing sets, defined in section 2. In particular, we recover the operators σ_{k} described in the platic monoid.

In section 4, we define actions of the symmetric group S_{3} on sets generated by indexing sets of Yamanouchi words, in a tree-letters alphabet. The generation of these sets is equivalent to a decomposition of the given indexing sets of a Yamanouchi word. Properties of these generated sets are derived. When the operators Θ_{k}^{∗}, k = 1, …, t − 1, are used to decompose indexing sets of a Yamanouchi word in a t-letters alphabet, we obtain the action of symmetric group S_{t}, described by A. Lascoux and M. P. Schutzenberger in [10], [12], restricted to words under consideration. The proof that the the involutions Θ_{k}^{∗}, k = 1, …, t−1, satisfy the conditions of the symmetric group S_{t} is not based on properties of the platic monoid, but instead on properties of the generated sets, by indexing sets of a Yamanouchi word. Finally, we generalize the Littlewood-Richardson rule to triples (a, σ b, c) where a, b and c are partitions, and σ is any permutation. This generalization is accomplished through the action of the symmetric group S_{t}.

2 The lattice of the power-set of [n] and its dual

2.1 The lattice P[n] and witnesses

Let ℕ be the set of non-negative integers with the usual order ” ≥ ”. Given n ∈ ℕ, [n] denotes the set {1, …, n}, and 2^{[n]} the power-set of [n].

Definition 2.1 Let A, B ⊆ [n]. We write A ≥ B if there exists an injection i : B → A such that b ≤ i(b), for all b ∈ B. We call such an injection a witness for A ≥ B.

The relation ≥ defined by A ≥ B is a partial order on 2^{[n]}, and we denote it by P[n], that is, given (A, B) ∈ 2^{[n]} × 2^{[n]}, (A, B) ∈ P[n] iff A ≥ B. This relation can be characterized in a number of ways as seen in the following proposition.

Given a finite set A, let |A| denote the cardinality of A.

Proposition 2.1 Given A, B ⊆ [n], the following statements are equivalent: (a) There exists an injection i : B → A such that b ≤ i(b), for all b ∈ B. (b)If a = (a_{1}, a_{2}, ..., a_{|A|}, 0, ...) and b = (b_{1}, ..., b_{|B|}, 0, ...) are the decreasing rearrange-

ment of the elements of A and B as embedded into ℕ^{ℕ}, then a ≥ b in the componentwise order.

(c)For any k ∈ ℕ, it holds |{a ∈ A : a ≥ k}| ≥ |{b ∈ B : b ≥ k}|.

(d) There exists an injection i : B → A as in (a), and satisfying additionally A ∩ B ⊆ i(B). In particular, i_{|_{A∩B}} = id_{|_{A∩B}}. (id stands for the identity map.)

Proof: It is a routine exercise to show that (a) ⇒ (c) ⇒ (b) ⇒ (a).

(a) ⇒ (d) Suppose condition (a) holds. Since we have already proved the equivalence of conditions (a) and (c), we have |{a ∈ A : a ≥ k}| ≥ |{b ∈ B : b ≥ k}|, for all k ∈ ℕ. Then, we must have |{a ∈ A \ B : a ≥ k}| ≥ |{b ∈ B \ A : b ≥ k}|, k ∈ ℕ. Thus, there exists an injection j : B \ A → A \ B such that j(b) ≥ b, b ∈ B \ A. Define \overline{j} : B → A by \overline{j}(b) = b if b ∈ A ∩ B, and \overline{j}(b) = j(b) if b ∉ A ∩ B. Clearly, \overline{j} is a witness for A ≥ B and \overline{j}_{|_{A∩B}} = id_{|_{A∩B}}.

(d) ⇒ (a) Trivial. □

Note that (b) characterizes P[n] as the component ordering. For simplicity, we shall write A = {a_{1} > … > a_{|A|}} to mean A = {a_{1}, …, a_{|A|}} with a_{1} > … > a_{|A|}.

Proposition 2.2 P[n] is a lattice in which the family of all subsets of a given cardinality forms a sublattice. The family of all finite subsets of ℕ, ⋃_{n∈ℕ} P[n], is a lattice.

Proof: It is a direct consequence of proposition 2.1, (b), and the observation that the family of all integral sequences with finite support defines a lattice with respect to the componentwise order: if a = (a_{i})_{i=1}^{∞} and b = (b_{i})_{i=1}^{∞} are two such sequences, we define a ∧ b = (min{a_{i}, b_{i}}) and a ∨ b = (max{a_{i}, b_{i}}). □

Next proposition stresses the property that P[n] is an extension of any lattice of the family of all subsets of a given cardinality.

Proposition 2.3 Given A, B ⊆ [n], the following statements are equivalent: (a) A ≥ B. (b)There exits X ⊆ A such that |X| = |B| and X ≥ B. (c)There exits X ⊆ A such that |X| = |B|, A ∩ B ⊆ X and X ≥ B.

(d) A \ Z ≥ B \ Z, with Z ⊆ A ∩ B.

Proof: It is a direct consequence of proposition 2.1, (a) and (d) . □

Proposition 2.4 P[n] has the following properties (a) If B ⊆ A then A ≥ B.

(b) Let A ≥ B and C ≥ D such that A ∩ C = ∅ and B ∩ D = ∅. Then A ∪ C ≥ B ∪ D.

(c) If A ≥ B and B = B_{1} ∪ B_{2}, with |A| = |B| and B_{1} ∩ B_{2} = ∅, there exist A_{1}, A_{2} ⊆ A such that A_{1} ∪ A_{2} = A, A_{1} ∩ A_{2} = A_{1} ∩ B_{2} = A_{2} ∩ B_{1} = ∅ and A_{i} ≥ B_{i}, i = 1, 2.

Proof: (a) and (b) are a direct consequence of proposition 2.3.

(c) Let i : B → A be a witness of A ≥ B such that i_{|_{A∩B}} = id_{|_{A∩B}}. Define A_{i} := i(B_{i}), i = 1, 2. □

Let A ≥ B and i, j witnesses of A ≥ B. We write i ≥ j if i(B) ≥ j(B). Given A ≥ B, the relation ≥ defined by i ≥ j is a partial order on the set of witnesses of A ≥ B.

Considering proposition 2.3 and since P[n] is a lattice, given A ≥ B we may define the least upper bound of B in 2^{A}.

Definition 2.2 Let A ≥ B. We write

min_{B}A = min{X ⊆ A : |X| = |B| and X ≥ B}

as the least upper bound of B contained in A.

Note that min_{B}A = min{i(B) : i is a witness of A ≥ B}; Y ∈ P(A), Y ≥ B only if Y ≥ min_{B}A; and A ∩ B ⊆ min_{B}A. In particular, if |A| = |B|, min_{B}A = A, and if B ⊆ A, min_{B}A = B.

Definition 2.3 Let i be a witness of A ≥ B. We say that i is a minimal witness of A ≥ B if i(B) = min_{B}A.

In the sublattice of all subsets of [n] of a given cardinality every witness is minimal.

Given A ≥ B, min_{B}A may be computed in several ways, and, therefore, this leads to different minimal witnesses. The next algorithm exhibits a minimal witness of A ≥ B.

Theorem 2.5 Let A ≥ B with B = {b_{1} > ... > b_{m}}. Let

y_{m} = min{a ∈ A : a ≥ b_{m}}, and  (1)
y_{m−i} = min{a ∈ A \ {y_{m}, ..., y_{m−i+1}} : a ≥ b_{m−i}}, for i = 1, ..., m − 1.  (2)

Then, min_{B}A = {y_{1} > ... > y_{m}}.

Proof: By induction on m. If m = 1, min_{B}A = {y_{1}}. Let m > 1 and (z_{1}^{j}, ..., z_{m}^{j}, 0, ...), for j = 1, ..., k, the decreasing rearrangement of all subsets of A of cardinal m such that (z_{1}^{j}, ..., z_{m}^{j}, 0, ...) ≥ (b_{1}, ..., b_{m}, 0, ...). Let (x_{1}, ..., x_{m}, 0, …) = ∧_{j=1}^{k}(z_{1}^{j}, ..., z_{m}^{j}, 0, ...) be the decreasing rearrangement of min_{B}A. Clearly {y_{1}, ..., y_{m}} ⊆ A and (y_{1}, ..., y_{m}, 0, ...) ≥ (b_{1}, ..., b_{m}, 0, ...). Therefore, y_{i} ≥ x_{i}, i = 1, ..., m. On the other hand, by (1), y_{m} = min_{{b_{m}}}A ≤ x_{m}. Hence y_{m} = x_{m} = min_{{b_{m}}}A. Now, notice that if (q_{1}, ..., q_{m−1}, 0, ...) is the decreasing rearrangement of a subset of cardinal m − 1 of A \ {y_{m}} such that (q_{1}, ..., q_{m−1}, 0, ...) ≥ (b_{1}, ..., b_{m−1}, 0, ...), then the array (q_{1}, ..., q_{m−1}, y_{m}, 0, ...) is the decreasing rearrangement of a subset of A of cardinal m such that (q_{1}, ..., q_{m−1}, y_{m}, 0, ...) ≥ (b_{1}, ..., b_{m−1}, b_{m}, 0, ...). Therefore, (z_{1}^{j}, ..., z_{m−1}^{j}, 0, ...), j = 1, ..., k, are the decreasing rearrangement of all subsets of cardinal m − 1 of A \ {y_{m}} such that (z_{1}^{j}, ..., z_{m−1}^{j}, 0, ...) ≥ (b_{1}, ..., b_{m−1}, 0, ...). Hence, (x_{1}, ..., x_{m−1}, …) = ∧_{j=1}^{k}(z_{1}^{j}, ..., z_{m−1}^{j}, 0, ...) is the decreasing rearrangement of min_{(B\{b_{m}})}(A \ {y_{m}}), and

min_{B}A = min_{{b_{m}}}A ∪ min_{(B\{b_{m}})}(A \ {y_{m}}).  (3)

By induction and from (2), we have min_{(B\{b_{m}})}(A \ {y_{m}}) = {y_{1}, ..., y_{m−1}}, and consequently, by (3), min_{B}A = {y_{1}, ..., y_{m}}. □

Corollary 2.6 Let A′ ≥ B with |A′| = |B|, A′ = {a_{1} > ... > a_{m}} and B = {b_{1} > ... > b_{m}}. Let A, F ⊆ {1, …, n} with A′ ⊆ A. Then

(I) the following conditions are equivalent

(a) A′ = min_{B}(A′ ∪ F).

(b) F ⊆ {a ∈ {1, …, n} : ∃i ∈ {0, 1, ..., m}, b_{i} > a > a_{i+1}}.

(We convention b_{0} := +∞ and a_{m+1} := −∞.)

(II) if A′ = min_{B}A, it holds

(a) min_{B}A = min_{{b_{m},...,b_{i+1}}}A ∪ min_{{b_{i},...,b_{1}}}(A \ {a_{m}, ..., a_{i+1}}), for 1 ≤ i ≤ m.

(b) min_{B}A = min_{{b_{m},...,b_{i+1}}}A ∪ min_{{b_{i},...,b_{1}}}A, if there exists i ∈ {1, ..., m − 1} such that b_{i} > a_{i+1}.

Proof: Straightforward from (1) and (2). □

Corollary 2.7 Let A, B and C ⊆ [n] such that A ≥ B. Let G, A′ ⊆ A such that A′∩G = ∅ and A′ ≥ B with |A′| = |B|, B = {b_{1} > ... > b_{m}} and A′ = {a_{1} > ... > a_{m}}. Then

(a) if g ∈ G only if b_{i} > g > a_{i+1}, for some i ∈ {0, 1, ..., m}, it holds

min_{B}A = min_{B}(A \ G).

(b) min_{B}(A ∪ C) = min_{B}[(min_{B}A) ∪ C].

Proof: (a) Let min_{B}A = Y with Y = {y_{1} > ... > y_{m}}. Then, a_{i} ≥ y_{i} ≥ b_{i} for each i ∈ {1, ..., m}, and g ∈ G only if b_{i} > g > a_{i+1} ≥ y_{i+1}. By corollary 2.6, min_{B}A = min_{B}Y = min_{B}(Y ∪ (A \ G)).

(b) Consequence of (a). □

The significance of the next two theorems will be clear in the last section.

Theorem 2.8 Let A, B, C ⊆ [n] such that A ≥ B and A ∩ C = ∅. Let A′ = min_{B}A. Then, min_{B}(A ∪ C) = X ∪ Y with X ⊆ A′, Y ⊆ C, and A′ = X ∪ Z such that Z ≥ Y.

Proof: By induction on |C|. Let |C| = 1 and C = {c}. Let B = {b_{1} > ... > b_{m}} and A′ = {a_{1} > ... > a_{m}}. By previous corollary, if b_{k} > c > a_{k+1}, for some k ∈ {0, 1, ..., m}, then Y = ∅ = Z. Otherwise, a_{k} > c > a_{k+1} and a_{k} > c ≥ b_{k}, for some k ∈ {1, …, m}. Since A′ ∩ {c} = {a_{1} > … > a_{k} > c > a_{k+1} > … > a_{m}} and using corollary 2.6, (II), we may write

min_{B}(A ∪ {c}) = min_{B}(A′ ∪ {c})
= {a_{m}, …, a_{k+1}} ∪ min_{{b_{k}}}[(A \ {a_{m}, …, a_{k+1}}) ∪ {c}]
∪min_{{b_{k−1},...,b_{1}}}[A \ {a_{m}, …, a_{k+1}}], and
min_{B}A = {a_{m}, …, a_{k+1}} ∪ min_{{b_{k}}}[A \ {a_{m}, …, a_{k+1}}]
∪min_{{b_{k−1},...,b_{1}}}[A \ {a_{m}, …, a_{k+1}, a_{k}}],

where min_{{b_{k−1},...,b_{1}}}(A \ {a_{m}, …, a_{k+1}}) = {a_{k}, …, a_{f+1}, a_{f−1}, …, a_{1}}, with 1 ≤ f ≤ k.

Define X := A′ \ {a_{f}}, with 1 ≤ f ≤ k, Y := C, Z := {a_{f}}. Thus, A′ = X ∪ Z and min_{B}(A ∪ C) = X ∪ Y with Z > Y.

Let |C| > 1 and C = C′∪{c}. By induction min_{B}(A∪C′) = X′∪Y′ with X′ ⊆ A′, Y′ ⊆ C′, and A′ = X′ ∪Z′ such that Z′ ≥ Y′. Now, either min_{B}(A∪C) = X′ ∪Y′ with X′ ⊆ A′, Y′ ⊆ C, and A′ = X′ ∪ Z′ such that Z′ ≥ Y′, or min_{B}(A ∪ C) = [(X′ ∪ Y′) \ {x}] ∪ {c}, with x ∈ X′ ∪ Y′ and x > c. In the last case, either we get min_{B}(A ∪ C) = X′ ∪ Y with Y = (Y′ \{x})∪{c}, and A′ = X′ ∪Z with Z = Z′, or we get min_{B}(A∪C) = (X′ \{x})∪Y with Y = Y′ ∪ {c}, and A′ = (X′ \ {x}) ∪ Z with Z = Z′ ∪ {x}. □

Lemma 2.9 Let A, B ⊆ [n] where B = {b_{1} > … > b_{m}} and min_{B}A = {a_{1} > … > a_{m}}. Let Y = {y_{1} > … > y_{s}} such that ∃i_{k} ∈ {1, ..., m}, b_{i_{k}} > y_{k} > a_{i_{k}+1}, for k = 1, …, s. Let X = B \ {b_{i_{1}}, …, b_{i_{s}}}. Then, min_{B}A = min_{(X∪Y)}{a_{1}, …, a_{m}}.

Proof: Straightforward from theorem 2.5 and corollary 2.6, (II), (b). □

Theorem 2.10 Let G, F_{2}, F_{3} be subsets of [n] such that G ≥ F_{2} ≥ F_{3}. Let D ⊆ [n] such that D ∩ G = D ∩ F_{2} = ∅, and min_{F_{2}}(G ∪ D) = G. Let F′ = min_{F_{3}}F_{2}. Then, if min_{F_{3}}(F_{2} ∪ D) = F, we have min_{F} G = min_{F′}G.

Proof: Let F_{2} = {a_{1} > … > a_{t}}, F′ = {a_{s_{1}} > … > a_{s_{m}}} where {s_{1} > … > s_{m}} ⊆ {1, …, t}, and F_{3} = {b_{1} > … > b_{m}}. Using corollary 2.7 and theorem 2.8, we may write

min_{F_{3}}(F_{2} ∪ D) = min_{F_{3}}(F′ ∪ D) = X ∪ Y,

with X ⊆ F′ and Y ⊆ D. Now, corollary 2.6 implies y ∈ Y only if

∃i ∈ {1, …, m} : a_{s_{i}} > y > a_{s_{i+1}}, a_{s_{i}} > y ≥ b_{i}, and
a_{s_{i}} > α ≥ b_{i} ⇒ α ∉ F_{2}.  (4)

On the other hand, since min_{F_{2}}(G ∪ D) = G, putting G = {g_{1} > … > g_{t}}, we have, from corollary 2.6,

y ∈ Y ⇒ ∃j ∈ {1, …, t} : a_{j} > y > g_{j+1}.

Hence j ∈ {s_{1}, …, s_{m}}. Otherwise, a_{s_{i}} > a_{j} > y ≥ b_{i}, with a_{j} ∈ F_{2}. A contradiction with (4). Hence, from previous lemma, min_{X∪Y} G = min_{F} G. □

Next we show that the output of the algorithm given in theorem 2.5 does not depend on the order in which the elements of B are considered. In particular, next algorithm leads to minimal witnesses of A ≥ B with different properties which shall be important in the sequel.

Theorem 2.11 Let A ≥ B and B = {b_{1} > ... > b_{m}}. Let σ ∈ S_{m} and

z_{m} = min{a ∈ A : a ≥ b_{σ(m)}},
z_{m−i} = min{a ∈ A \ {z_{m}, ..., z_{m−i+1}} : a ≥ b_{σ(m−i)}}, i = 1, ..., m − 1.

Then, min_{B}A = {z_{1}, ...., z_{m}}.

Proof: By induction on m. If m = 1, it is trivial, min_{{b_{1}}}A = {z_{1}}. Let m > 1 and min_{B}A = {y_{1} > ... > y_{m}}.

Let σ(m) = j, for some j ∈ {1, ..., m}, and min_{{b_{j}}}A = {z_{m}}. Then, by theorem 2.5, since {y_{j}} = min_{{b_{j}}}(A \ {y_{m}, ..., y_{j+1}}), either z_{m} = y_{j} or y_{j} > z_{m} > b_{j}. In the last case, by corollary 2.6,(I), z_{m} = y_{k} with k > j and y_{m}, ..., y_{k+1} < b_{j} and y_{k−1}, ..., y_{j}, ..., y_{1} > b_{j}. From (1) and (2), we conclude that A \ {y_{k}} ≥ B \ {b_{j}} and min_{{b_{m},...,b_{k},...,b_{j+1}}}(A \ {y_{k}}) = {y_{m}, ..., y_{k+1}, y_{k−1}, ..., y_{j}}, and by corollary 2.6, (II),

min_{(B\{b_{j}})}(A \ {y_{k}}) = min_{{b_{m},...,b_{j+1}}}(A \ {y_{k}}) ∪ min_{{b_{j−1},...,b_{1}}}[A \ {y_{j}, ..., y_{m}}]

and, therefore, min_{(B\{b_{σ(m)}})}(A \ {y_{k}}) = {y_{m}, ..., y_{1}} \ {y_{k}}. That is, since {z_{m}} = min_{{b_{σ(m)}}}A,

min_{B}A = min_{{b_{σ(m)}}}A ∪ min_{(B\{b_{σ(m)}})}(A \ {y_{k}}).

By induction, min_{(B\{b_{σ(m)}})}(A \ {y_{k}}) = {z_{m−1}, ..., z_{1}}. So, the claim follows. □

Remark 1 For each σ ∈ S_{m}, this theorem defines the minimal witness z_{σ} : B ⟶ A such that z_{σ}(b_{σ(m−i)}) = z_{m−i}, for i = 0, 1, …, m − 1. When σ = id we have the minimal witness given by theorem 2.5. In particular, if σ ∈ S_{m} is such that A ∩ B = {b_{σ(m)}, …, b_{σ(t)}}, then min_{B}A = (A ∩ B) ∪ min_{(B\A)}(A \ B).

Corollary 2.12 Let A ≥ B and C ⊆ B. Let min_{C}A = A′. Then,

min_{B}A = min_{C}A ∪ min_{(B\C)}(A \ A′).

In particular, A \ A′ ≥ B \ C and A ∩ C ⊆ A′.

Proof: If C = ∅, min_{C}A = ∅ and it is done. Otherwise, let B = {b_{1} > ... > b_{m}}, m > 1, and C = {b_{j_{1}} > ... > b_{j_{r}}}, r ≥ 1. Let σ ∈ S_{m} such that σ(m − i + 1) = j_{i}, for i = 1, ..., r. The result now follows from theorem 2.11. □

Note that min_{(B\C)}(A \ A′) = min_{B}A \ min_{C}A, with A′ = min_{B}A.

As a consequence of choosing a particular σ ∈ S_{m} in the previous theorem and corollary, we have the following algorithms which will have a significant translation to words in the next section:

Algorithm I: Given A ≥ B and B = {b_{1} > ... > b_{m}}, let {k, j, …, l} := {i ∈ {1, …, m} : ∃x ∈ A, b_{i−1} > x ≥ b_{i}} and V_{0} := {b_{k}, b_{j}, …, b_{l}} ⊆ B. For α ∈ {k, j, …, l}, define

z_{α} := min{x ∈ A : b_{α−1} > x ≥ b_{α}},  (5)

and put Z_{0} := {z_{k}, z_{j}, …, z_{l}} ⊆ A. Let A_{1} := A \ Z_{0} and B_{1} := B \ V_{0}. Then repeat the procedure with A_{1} ≥ B_{1} defining V_{1} := {b_{l}, b_{p}, …, b_{q}} ⊆ B_{1}, z_{α} := min{x ∈ A_{1} : b_{α−1} > x ≥ b_{α}}, for α ∈ {l, p, …, q}, and Z_{1} := {z_{l}, z_{p}, …, z_{q}} ⊆ A_{1}. There remains A_{2} := A_{1} \ Z_{1} and B_{2} := B_{1} \ V_{1}. Continue this procedure with A_{2} ≥ B_{2} until it stops, giving sets A_{k} := A_{k−1} \ Z_{k−1} and B_{k} := B_{k−1} \ V_{k−1} = ∅. Then, A = Z_{0} ∪ … ∪ Z_{k−1} ∪ A_{k}, B = V_{0} ∪ … ∪ V_{k−1}, and

min_{B}A = min_{V_{0}}A ∪ min_{V_{1}}A_{1} ∪ … ∪ min_{V_{k−1}}A_{k−1}
= Z_{0} ∪ Z_{1} ∪ … ∪ Z_{k−1}.

( We convention b_{0} := +∞.)

This defines the minimal witness z^{I} : B ⟶ A such that z^{I} = z_{0}^{I} ∪ … ∪ z_{k−1}^{I} with z_{i}^{I} : V_{i} ⟶ A_{i}, i = 0, 1, … k − 1, given according to (5).

Algorithm II: Given A ≥ B and A = {a_{1} > ... > a_{n}}, let {f, g, …, h} := {i ∈ {1, …, n} : ∃y ∈ B, a_{i} ≥ y > a_{i+1}} and Q_{0} := {a_{f}, a_{g}, …, a_{h}} ⊆ A. For α ∈ {f, g, …, h}, define

u_{α} := max{y ∈ B : a_{α} ≥ y > a_{α+1}},  (6)

and put U_{0} := {u_{f}, u_{g}, …, u_{h}} ⊆ B. Let B_{1} := B \ U_{0} and A_{1} := A \ Q_{0}. Then repeat the procedure with A_{1} ≥ B_{1} defining Q_{1} := {a_{l}, a_{p}, …, a_{q}} ⊆ A_{1}, u_{α} := max{y ∈ B_{1} : b_{α−1} ≥ y > b_{α}}, for α ∈ {l, p, …, q}, and U_{1} := {u_{l}, u_{p}, …, u_{q}} ⊆ B_{1}. There remains B_{2} := B_{1} \ U_{1} and A_{2} := A_{1} \ Q_{1}. Continue this procedure with A_{2} ≥ B_{2} until it stops, giving sets A_{k} := A_{k−1} \ Q_{k−1} and B_{k} := B_{k−1} \ U_{k−1} = ∅. Then, A = Q_{0} ∪ … ∪ Q_{k−1} ∪ A_{k}, B = U_{0} ∪ … ∪ U_{k−1}, and

min_{B}A = Q_{0} ∪ Q_{1} ∪ … ∪ Q_{k−1}.

(We convention a_{n+1} := −∞.)

This defines the minimal witness z^{II} : B ⟶ A such that z^{II} = z_{0}^{II} ∪ … ∪ z_{k−1}^{II} with z_{i}^{II} : U_{i} ⟶ A_{i}, i = 0, 1, … k − 1, given according to (6).

The next result will be used in the last section.

Lemma 2.13 Let F, C and D subsets of [n] such that C ≥ D. Assume C = {g_{1} > … > g_{r}} and D = {s_{1} > … > s_{r}}. Let n ≥ t ≥ x ≥ 1 such that x, t ∉ C ∪ D, min_{{x}}({t} ∪ F) = {t} and s_{u} > x > g_{u+1} for some u ∈ {0, 1, …, r}. Then,

min_{(D∪{x})}(F ∪ C ∪ {t}) = {t} ∪ min_{D}(F ∪ C).

Proof: Suppose that g_{u−l} > t > g_{u−l+1}, for some l ∈ {0, 1, …, u}. Then, by corollary corollary 2.6, (II),

min_{(D∪{x})}(F ∪ C ∪ {t})
= min_{{s_{r},...,s_{u+1}}}(F ∪ C ∪ {t}) ∪ min_{({s_{u},...,s_{1}}∪{x})}(F ∪ C ∪ {t})
= min_{{s_{r},...,s_{u+1}}}(F ∪ C) ∪ min_{({s_{u},...,s_{1}}∪{x})}(F ∪ C ∪ {t}).  (7)

Now, by corollary 2.6, (II), since

min_{{s_{u},...,s_{u−l+1}}}(F ∪ C ∪ {t}) = {g_{u}, …, g_{u−l+1}} = min_{{s_{u},...,s_{u−l+1}}}(F ∪ C),

it holds,

min_{({s_{u},...,s_{1}}∪{x})}(F ∪ C ∪ {t})
= min_{{s_{u},...,s_{u−l+1}}}(F ∪ C) ∪ min_{({x}∪{s_{u−l},...,s_{1}})}[F ∪ (C\{g_{u}, …, g_{u−l+1}}) ∪ {t}]. (8)

Again, by corollary 3, since min_{{x}}[F ∪ (C\{g_{u}, …, g_{u−l+1}}) ∪ {t}] = {t}, we have

min_{({x}∪{s_{u−l},...,s_{1}})}[F ∪ (C\{g_{u}, …, g_{u−l+1}}) ∪ {t}]
= {t} ∪ min_{{s_{u−l},...,s_{1}}}[F ∪ (C\{g_{u}, …, g_{u−l+1}})].  (9)

Therefore, by (7), (8), and (9),

min_{(D∪{x})}(C ∪ {t})
= min_{{s_{r},...,s_{u+1}}}(F ∪ C) ∪ min_{{s_{u},...,s_{u−l+1}}}(F ∪ C) ∪ {t}
∪min_{{s_{u−l},...,s_{1}}}[F ∪ (C\{g_{u}, …, g_{u−l+1}})]
= {t} ∪ min_{D}(F ∪ C).

Notice that, min_{D}(F ∪ C) = min_{{s_{r},...,s_{u+1}}}(F ∪ C) ∪ min_{{s_{u−l},...,s_{1}}}(F ∪ C), and

min_{{s_{u},...,s_{1}}}(F ∪ C) = min_{{s_{u},...,s_{u−l+1}}}(F ∪ C)
∪min_{{s_{u−l},...,s_{1}}}[F ∪ (C\{g_{u}, …, g_{u−l+1}})].  (10)
□

Theorem 2.14 Let A, B, C, D, F ⊆ [n] with |A| = |B|, |C| = |D|, A ∩ C = B ∩ D = ∅. Assume C = {g_{1} > … > g_{r}} and D = {s_{1} > … > s_{r}} and suppose A ≥ B and C ≥ D are such that min_{B}(A ∪ F) = A and x ∈ B only if s_{i} > x > g_{i+1}, for some i ∈ {0, 1, …, r}. Then,

min_{(B∪D)}(A ∪ C ∪ F) = A ∪ min_{D}(C ∪ F).

Proof: Let A = {t_{1} > … > t_{k}} and B = {x_{1} > … > x_{k}}. The proof will be handled by induction on k = |A|. The previous lemma proves the case k = 1.

Let k > 1, and suppose that s_{u} > x_{k} > g_{u+1} for some u ∈ {0, 1, …, r}, and g_{u−l} > t_{k} > g_{u−l+1}, with l ∈ {1, …, u}.

By corollary 2.6, (II), we may write

min_{(B∪D)}(A ∪ C ∪ F) = min_{{s_{r},...,s_{u+1}}}(A ∪ C ∪ F) ∪ min_{(B∪{s_{u},...,s_{1}})}(A ∪ C ∪ F). (11)

But

min_{(B∪{s_{u},...,s_{1}})}(A ∪ C ∪ F) = min_{({s_{u},...,s_{u−l+1}}∪{x_{k}})}(A ∪ C ∪ F)
∪min_{[(B\{x_{k}})∪{s_{u−l},...,s_{1}}]}[(A\{t_{k}}) ∪ (C\{g_{u}, …, g_{u−l+1}}) ∪ F].  (12)

Since, min_{{s_{r},...,s_{u+1}}}(A ∪ C ∪ F) = min_{{s_{r},...,s_{u+1}}}((A\{t_{k}}) ∪ C ∪ F), it follows, from (11) and (12),

min_{B∪D}(A ∪ C ∪ F)
= min_{((D\{s_{u},...,s_{u−l+1}})∪(B\{x_{k}}))}[(A\{t_{k}}) ∪ (C\{g_{u}, …, g_{u−l+1}}) ∪ F]
∪min_{({s_{u},...,s_{u−l+1}}∪{x_{k}})}[(A ∪ C ∪ F].  (13)

On the other hand, attending to k = 1, we have

min_{({s_{u},...,s_{u−l+1}}∪{x_{k}})}[(A ∪ C ∪ F]
= min_{{s_{u},...,s_{u−l+1}}}(A ∪ C ∪ F) ∪ min_{{x_{k}}}[A ∪ (C\{g_{u}, …, g_{u−l+1}}) ∪ F]
= min_{{s_{u},...,s_{u−l+1}}}[(A\{t_{k}}) ∪ C ∪ F] ∪ {t_{k}}.  (14)

Hence, from (13) and (14),

min_{(B∪D)}(A ∪ C ∪ F) = min_{{s_{u},...,s_{u−l+1}}}[(A\{t_{k}}) ∪ C ∪ F]
∪min_{[(D\{s_{u},...,s_{u−l+1}})∪(B\{x_{k}})]}[(A\{t_{k}}) ∪ (C\{g_{u}, …, g_{u−l+1}}) ∪ F] ∪ {t_{k}}
= min_{(D∪(B\{x_{k}}))}[(A\{t_{k}}) ∪ C ∪ F] ∪ {t_{k}}.

By induction,

\begin{matrix}min_{(B∪D)}(A ∪ C ∪ F) = min_{[(D∪(B\\{x_{k}\})]}[(A\\{t_{k}\}) ∪ C ∪ F] ∪ \{t_{k}\} \\ = (A\\{t_{k}\}) ∪ min_{D}(C ∪ F) ∪ \{t_{k}\} = A ∪ min_{D}(C ∪ F). \end{matrix}

□

2.2 The dual lattice of P[n]

Considering proposition 2.3, we start with the following

Definition 2.4 Let A, B ⊆ [n]. We write A ≥_{op} B if A ≥ X, for some X ⊆ B with |X| = |A|.

The relation ≥_{op} is a partial order on 2^{[n]}, and we denote it by P^{op}[n]. Clearly, P^{op}[n] is also a lattice in which the family of all subsets of a given cardinality is a sublattice. Furthermore, ⋃_{n∈ℕ} P^{op}[n], the family of all finite subsets of ℕ, is a lattice with the relation defined by A ≥_{op} B.

Note that if A ≥_{op} B then |A| ≤ |B|. On the other hand, if |A| = |B|, A ≥ B iff A ≥_{op} B. This means that the sublattice of the family of all subsets of a given cardinality of P[n] and P^{op}[n] respectively, are isomorphic under the identity map.

The relation ≥_{op} has also many characterizations: A ≥_{op} B iff there exists an injection j : A ⟶ B with a ≥ j(a), for all a ∈ A. Such an injection j is called a witness of A ≥_{op} B.

Let A ≥_{op} B and i, j witnesses of A ≥_{op} B. We write i ≥ j if i(A) ≥ j(A). Given A ≥_{op} B, the relation ≥ defined by i ≥ j is a partial order on the set of all witnesses of A ≥_{op} B.

Since P^{op}[n] is a lattice, given A ≥_{op} B we may define the greatest lower bound of A in 2^{B}. We write

max_{A}B := max{X ⊆ B : |X| = |A| and A ≥ X}

as the greatest lower bound of A contained in B. Note that max_{A}B = max{i(A) : i is a witness of A ≥_{op} B} and A ∩ B ⊆ max_{A}B. In particular, if |A| = |B|, max_{A}B = B.

Let i be a witness of A ≥_{op} B. We say that i is a maximal witness of A ≥_{op} B if i(A) = max_{A}B. In the sublattice of all subsets of [n] of a given cardinality every witness is both minimal and maximal.

Given n ∈ ℕ, let op denotes the reverse permutation of [n], op(k) = n − k + 1. The map op is an involution in 2^{[n]} and it is an anti-automorphism on the sublattice of P[n] defined by the family of all subsets of a given cardinality, that is, A ≥ B iff op(B) ≥ op(A).

Now, we will look at the relation ≥_{op} in 2^{[n]} as a partial order in 2^{[n]}, with respect to the order induced in 2^{[n]} by the involution op.

Proposition 2.15 Given A, B ⊆ [n], the following assertions are equivalent (a) A ≥_{op} B.

(b) op(B) ≥ op(A).

Proof: A ≥ X, with X ⊆ B and |X| = |A| iff op(X) ≥ op(A), with op(X) ⊆ op(B). □

Since A ≥ B iff op(B) ≥_{op} op(A), the operation op is an anti-automorphism between the posets P[n] and P^{op}[n]. We have op(A∧B) = op(A)∨op(B) and op(A∨B) = op(A)∧op(B). Thus, P^{op}[n] is the dual lattice of P[n].

Let A ≥_{op} B. Note that ĩ is a witness of op(B) ≥ op(A) iff there exists an injection j : A ⟶ B with a ≥ j(a) and such that op.ĩ.op = j. That is, j is a witness of A ≥_{op} B iff op.j.op is a witness op(B) ≥ op(A). Hence, op(Y) = min_{(op(A))}op(B) iff Y = max_{A}B. In other words, j is a maximal witness of A ≥_{op} B iff opjop is a minimal witness of op(B) ≥ op(A).

Let A ≥_{op} B and A = {a_{1} > … > a_{m}}. By the principle of duality [8], we have the following dual statements.

The dual of theorem 2.5: max_{A}B = {x_{1}, …, x_{m}} where

x_{1} = max{b ∈ B : a_{1} ≥ b}, and
x_{i} = max{b ∈ B \ {x_{1}, ..., x_{i−1}} : a_{i} ≥ b}, for i = 1, ..., m − 1.  (15)

The dual of Algorithm I : let {k, j, …, l} := {i ∈ {1, …, m} : ∃y ∈ B, a_{i} ≥ y > a_{i+1}} and U_{0} := {a_{k}, a_{j}, …, a_{l}} ⊆ A. For α ∈ {k, j, …, l}, define

z_{α} := max{y ∈ B : a_{α−1} ≥ y > a_{α}},

and put Z_{0} := {z_{k}, z_{j}, …, z_{l}} ⊆ B. Let A_{1} := A \ U_{0} and B_{1} := B \ Z_{0}. Then, repeat the procedure with A_{1} ≥_{op} B_{1} until it stops, giving sets A_{k} := A_{k−1} \ V_{k−1} = ∅, and B_{k} := B_{k−1} \ Z_{k−1}, and we get

max_{A}B = max_{U_{0}}B ∪ max_{U_{1}}B_{1} ∪ … ∪ max_{U_{k−1}}B_{k−1}
= Z_{0} ∪ Z_{1} ∪ … ∪ Z_{k−1}.  (16)

The dual of Algorithm II is: let B = {b_{1} > … > b_{n}} and {k, j, …, l} := {i ∈ {1, …, n} : ∃x ∈ A, b_{i−1} > x ≥ b_{i}} and V_{0} := {b_{k}, b_{j}, …, b_{l}} ⊆ B. For α ∈ {k, j, …, l}, define

q_{α} := min{x ∈ A : b_{α−1} > x ≥ b_{α}},

and put Q_{0} := {q_{k}, q_{j}, …, q_{l}} ⊆ A. Let A_{1} := A \ Q_{0} and B_{1} := B \ V_{0}. Then, repeat the procedure with A_{1} ≥_{op} B_{1} until it stops, giving sets A_{k} := A_{k−1} \ Q_{k−1} = ∅, and B_{k} := B_{k−1} \ V_{k−1}, and we get

max_{A}B = max_{Q_{0}}B ∪ max_{Q_{1}}B_{1} ∪ … ∪ max_{Q_{k−1}}B_{k−1}
= V_{0} ∪ V_{1} ∪ … ∪ V_{k−1}.  (17)

These procedures describe maximal witnesses of A ≥_{op} B.

If A ≥ B is a chain in P[n] then op(B) ≥_{op} op(A) is a chain in P^{op}[n]. Clearly, A ≥ B ⟶ op(B) ≥_{op} op(A) defines a bijection between chains of length 2 in the lattice P[n], and chains in the dual lattice P^{op}[n]. On the other hand, A ≥ B iff X ≥ B for some X ⊆ A with |X| = |B|, and F ≥_{op} G iff F ≥ Y, for some Y ⊆ G with |Y | = |F |. Our aim now is to set a bijection between chains in P[n] and chains in P^{op}[n] avoiding the lattice anti-automorphism op but instead stressing the ideas of the last characterization.

According to proposition 2.3, for each F_{1} ≥ F_{2}, we may choose G_{1}, G_{2} ⊆ [n], such that

|G_{1}| = |F_{2}|, G_{1} ⊆ F_{1}, G_{1} ≥ F_{2}, F_{1} ∩ F_{2} ⊆ G_{1}, and G_{2} = F_{2} ∪ (F_{1} \ G_{1}).  (18)

Clearly G_{1} ≥_{op} G_{2}, and if |F_{1}| = |F_{2}|, G_{i} = F_{i}, i = 1, 2.

That is, given F_{1} ≥ F_{2}, there is a witness s with F_{1} ∩F_{2} ⊆ s(F_{2}), such that (F_{1}, F_{2}) and (s(F_{2}), F_{2} ∪ (F_{1} \ s(F_{2})) satisfy (18). Clearly, an injection g : s(F_{2}) ⟶ F_{2} ∪ (F_{1} \ s(F_{2})) such that gs = id is a witness of s(F_{2}) ≥_{op} F_{2} ∪ (F_{1} \ s(F_{2})). If s_{∗} is a minimal witness and gs_{∗} = id then g is a maximal witness.

On the other hand, given G_{1} ≥_{op} G_{2}, there exist F_{1} ≥ F_{2} and a witness s with F_{1} ∩F_{2} ⊆ s(F_{2}), such that (G_{1}, G_{2}) = (s(F_{2}), (F_{1} \ s(F_{2})) ∪ F_{2}). For, if j is a witness of G_{1} ≥_{op} G_{2} with G_{1} ∩ G_{2} ⊆ j(G_{1}), then an injection g : j(G_{1}) ⟶ (G_{2} \ j(G_{1})) ∪ G_{1} such that jg = id will do the claim. If j^{∗} is a maximal witness and j^{∗}g = id then g is a minimal witness.

Let H := {(F_{1}, F_{2}) : F_{1} ≥ F_{2}} be the set of comparable elements in P[n], and let H^{op} := {(G_{1}, G_{2}) : G_{1} ≥_{op} G_{2}} be the set of comparable elements in P^{op}[n].

For each F_{1} ≥ F_{2} in H, let s be a witness of F_{1} ≥ F_{2} such that F_{1} ∩ F_{2} ⊆ s(F_{2}), and define the map

s : H ⟶ H^{op},  (19)

where s(F_{1}, F_{2}) = (s(F_{2}), F_{2} ∪ (F_{1} \ s(F_{2})).

In particular, for each F_{1} ≥ F_{2}, we may choose a minimal witness s_{∗}, that is, s(F_{1}) = min_{F_{2}}F_{1}. According to (19), any collection of minimal witnesses of H induces a same bijection s_{∗} : H ⟶ H^{op}. Any collection of maximal witnesses of H^{op} induces a same bijection s^{∗} : H^{op} ⟶ H such that s_{∗}^{−1} = s^{∗}. The map s in (19) is a bijection iff s = s_{∗}.

Let Θ^{∗} := s_{∗} ∪ s_{∗}^{−1}, that is, Θ^{∗}_{|H} = s_{∗} and Θ^{∗}_{|H^{op}} = s_{∗}^{−1}. Therefore, Θ^{∗} : H ∪ H^{op} ⟶ H ∪ H^{op} is an involution which fixes the elements of H ∩ H^{op}, that is, the pairs (F_{1}, F_{2}) such that |F_{1}| = |F_{2}|.

3 Words, indexing sets and Young tableaux

3.1 Words and indexing sets

Let t ∈ ℕ and M([t]) be the free monoid of all words in the totally ordered alphabet [t]. Let [ℕ]_{t} be the set of all t-sequences of finite subsets of ℕ. The elements of [ℕ]_{t} may be represented by words in a grid as with matrices: the first coordinate, the row index, increases as one goes downwards, and the second coordinate, the column index, increases as one goes from left to right. Each sequence (J_{1}, …, J_{t}) of finite subsets of ℕ gives rise to a word w(J_{1}, …, J_{t}) in M([t]) called the word generated by (J_{1}, …, J_{t}), obtained reading the grid from top to down, along each row, from right to left, by assigning a label i to each dot in column i, for i = 1, …, t. The empty word Λ is generated by (∅, …, ∅).

For instance, let J_{1} = {2, 3, 6, 9}, J_{2} = {4, 5}, and J_{3} = {1, 7, 8}, then w(J_{1}, J_{2}, J_{3}) = 311221331. Also, if F_{1} = {1, 2, 4, 6}, F_{2} = {3, 4}, and F_{3} = {1, 5, 6}, we have w(F_{1}, F_{2}, F_{3}) = 311221331.

We identify the elements of [ℕ]_{t} which generate the same word,

(J_{1}, …, J_{t}) ∼ (J′_{1}, …, J′_{t}) if w(J_{1}, …, J_{t}) = w(J′_{1}, …, J′_{t}).

The relation ”∼” is an equivalence relation in [ℕ]_{t}, and we write M([ℕ]_{t}) := [ℕ]_{t}/ ∼.

Given m ≥ 0 and a finite set F = {x_{1}, …, x_{n}} ⊆ ℕ, we write m + F := {m + x_{1}, …, m + x_{n}}. Clearly, F ∼ m + F, for any m ≥ 0. ( We have m + ∅ = ∅.)

M([ℕ]_{t}) is a monoid with the operation ∪ defined as

[(J_{1}, …, J_{t})] ∪ [(F_{1}, …, F_{t})] = [(J_{1} ∪ (m + F_{1}), …, J_{t} ∪ (m + F_{t}))],

such that J_{i} ⊆ [m], for i = 1, …, t.

As usual we denote the length of a word w by |w|. Let w be a word in M([t]), we write |w|_{k}, k ∈ [t], to mean the multiplicity of the letter k in the word w.

Proposition 3.1 M([ℕ]_{t}) and M([t]) are isomorphic monoids.

Proof: The map ϕ : M([ℕ]_{t}) ⟶ M([t]) defined by ϕ([(J_{1}, …, J_{t})]) = w(J_{1}, …, J_{t}) is a monoid isomorphism. Let w in M([t]) and define J_{k} = {i ∈ {1, …, |w|} : i − th letter of w is k}, for k = 1, …, t. Then, w(J_{1}, …, J_{t}) = w. That is, every word w in M([t]) arises from M([ℕ]_{t}), and ϕ is a bijection. Clearly, ϕ([(J_{1}, …, J_{t})] ∪ [(F_{1}, …, F_{t})]) = w(J_{1}, …, J_{t})w(F_{1}, …, F_{t}). □

For instance, the word w = 311221331 is generated by J_{1} = {2, 3, 6, 9}, J_{2} = {4, 5}, and J_{3} = {1, 7, 8}.

Given w ∈ M([t]) and (J_{1}, …, J_{t}) ∈ [ℕ]_{t} such that w = w(J_{1}, …, J_{t}), we call (J_{1}, …, J_{t}) the indexing sets of w, and [(J_{1}, …, J_{t})] the class of indexing sets of w.

A word w in M([t]) is a Yamanouchi word if any right factor v of w satisfies |v|_{1} ≥ |v|_{2} ≥ … ≥ |v|_{t}. Recalling proposition 2.1, this is equivalent to say that if (J_{1}, …, J_{t}) are indexing sets of w, then every pair (J_{i}, J_{i+1}), i = 1, …, t − 1, satisfy condition (c) of that proposition. Henceforth, w(J_{1}, …, J_{t}) is a Yamanouchi word in the alphabet [t] iff J_{1} ≥ … ≥ J_{t}.

The dual word of w = x_{1} … x_{k} ∈ M([t]) is w_{op} := op(x_{k}) … op(x_{1}), a word in the alphabet [t], with op(i) = t − i + 1. Clearly, w(J_{1}, …, J_{t}) = w iff w(op(J_{t}), …, op(J_{1})) = w_{op}. Hence, w(J_{1}, …, J_{t}) is a dual Yamanouchi word iff J_{1} ≥_{op} … ≥_{op} J_{t}. The map w ⟶ w_{op} determines an anti-isomorphism in M([t]): (w_{1}w_{2})_{op} = (w_{2})_{op}(w_{1})_{op}. Now we search for a bijection between Yamanouchi words and their dual avoiding this antiautomorphism.

Given w ∈ M([t]), w′ is a subword of w iff (J_{1}, …, J_{t}) are indexing sets of w then w′ = w(F_{1}, …, F_{t}), for some F_{i} ⊆ J_{i}, i = 1, …, t.

A word w, in a two letters subalphabet, is both Yamanouchi and dual Yamanouchi iff the indexing sets (A, B) ∈ H∩H^{op}. Thus, according to the witnesses of (A, B), this means that w may be decomposed into |A| = |B| self-dual Yamanouchi subwords i + 1 i.

Either theorem 2.5, algorithms I or the the dual of theorem 2.5, algorithm II may be used in the calculation of a longest subword in H ∩ H^{op} of any word in a two letters alphabet.

For example, let w = 112121122122112 with indexing sets A = {1, 2, 4, 6, 7, 10, 13, 14} and B = {3, 5, 8, 9, 11, 12, 15}:

(a) (Applying the dual of theorem 2.5.) Extract from the word a subword w′ containing letters i and i + 1 only. Remove the right most subword i + 1 i of w′: put a bracket in the right most letter i, and then a bracket in the right most letter i + 1, to the left of the just brackted i. The remaining letters, the ones which are not brackted, constitute a subword v_{1} of w′. Then remove the right most subword i + 1 i of v_{1}. There remains a subword v_{2}. Continue this procedure until it stops, giving a word v_{q} of type v_{q} = i^{r} (i + 1)^{s}, with |w|_{i} −q = r and |w|_{i+1} −q = s. A longest subword in H∩H^{op}, in the subalphabet {i, i+1}, is the subword constituted by the bracketed letters. In our example, we have

11(21(21)1)2(21)(2(21)1)2,

X = {6, 7, 10, 13, 14} ≥ Y = {3, 5, 9, 11, 12},

w(X, Y) = 2211212211, and w(A \ X, B \ Y) = 11122.

Note that max_{B}X = Y.

(b) (Applying theorem 2.5.) Do the procedure above with the leftmost subword i + 1 i of w: put a bracket in the left most letter i + 1, and then a bracket in the left most letter i, to the right of the just brackted i + 1. When the procedure stops we get a subword u_{q} of type u_{q} = i^{r} (i + 1)^{s}, with |w|_{i} − q = r and |w|_{i+1} − q = s. A longest subword in H ∩ H^{op}, in the subalphabet {i, i + 1}, is the subword constituted by the bracketed letters. In our example, we have

11(21)(21)1(2(21)(221)1)2,

X′ = {4, 6, 10, 13, 14} ≥ Y′ = {3, 5, 8, 9, 11},

w(X′, Y′) = 2121221211, and w(A \ X′, B \ Y′) = 11122.

Note that min_{Y′}A = X′.

(c)[10], [12] (Applying either algorithms I or II.) Extract from the word a subword w′ containing letters i and i + 1 only. Bracket every factor i + 1 i of w. The letters which are not bracketed constitute a subword w_{1} of w. Then bracket every factor i + 1 i of w_{1}. There remains a subword w_{2}. Continue this procedure until it stops, giving a word w_{k} of type w_{k} = i^{r} (i + 1)^{s}. A longest subword in H ∩ H^{op}, in the subalphabet {i, i + 1}, is the subword constituted by the bracketed letters. In our example, we have

11(21)(21)12(21)(2(21)1)2,

X′′ = {4, 6, 10, 13, 14} ≥ Y′′ = {3, 5, 9, 11, 12},

w(X′′, Y′′) = 2121212211, and w(A \ X′′, B \ Y′′) = 11122.

Note that min_{Y′′}A = X′′, max_{B}X′′ = Y′′, and X′′ = X′ and Y′′ = Y.

If w is a Yamanouchi ( dual Yamanouchi), X = X′ = X′′ ⊆ A and Y = Y′ = Y′′ = B (and X = X′ = X′′ = A and Y = Y′ = Y′′ ⊆ B) and both procedures (b) and (c) ((a) and (c)) coincide as was shown in theorem 2.11.

The procedure (c) is the transformation given by M. P. Schutzenberger and A. Lascoux in [10] and [12], and its translation to indexing sets, in the case of Yamanouchi and dual Yamanouchi words in a two-letters alphabet, is given either by algorithm I or II, as well as their dual algorithms, respectively. Moreover, given a Yamanouchi (dual Yamanouchi) word w = w(A, B), the procedure (c) on w is equivalent to putting brackets in the subword w(min_{B}A, B) (w(A, max_{B}A)). There remains a word i^{r} ((i + 1)^{s}), with r = |A| − |B| (s = |B| − |A|). That is, according to theorem 2.11, bracketing every factor i + 1 i on a Yamanouchi (dual Yamanouchi) word, as in (c), is an instance of a minimal (maximal) witness of A ≥ B (A ≥_{op} B).

The next proposition gives a representative of each class [(A, B)].

Let s_{∗} : H ⟶ H^{op} be the bijection induced by any collection of minimal witnesses of H, defined by s_{∗}(A, B) = (min_{B}A, B ∪ (A \ min_{B}A)); and s_{∗}^{−1} : H^{op} ⟶ H be the bijection induced by any collection of maximal witnesses of H^{op}, s_{∗}^{−1}(C, D) = (C ∪ (D \ max_{C}D), max_{C}D). Recall that min_{B}A and max_{C}D may be achieved by any minimal witness and maximal witness respectively. For instance, as mentioned above, the procedure (c), when restricted to Yamanouchi words and their dual, is the translation of algorithms I, II to words:

w_{1} = w(V_{0}, z^{I}(V_{0})) = w(U_{0}, z^{II}(U_{0}))
⋮
w_{k} = w(V_{k−1}, z^{I}(V_{k−1})) = w(U_{k−1}, z^{II}(U_{k−1})).

For k = 1, …, t − 1, let σ_{k} be the involutions, defined in [10] and [12], acting on ℤ([t]), the free algebra on [t]. Then,

w(s_{∗}(A, B)) = σ_{1}(w(A, B)), w(s_{∗}^{−1}(C, D)) = σ_{1}(w(C, D)).

In the last section, we have introduced the involution Θ^{∗} : H ∪ H^{op} ⟶ H ∪ H^{op}. Now we extend it to (J_{1}, …, J_{t}) ∈ [ℕ]_{t} such that either J_{i} ≥ J_{i+1} or J_{i} ≥_{op} J_{i+1}, for i = 1, …, t−1, as follows

Θ_{k}^{∗}(J_{1}, …, J_{t}) = (J_{1}, …, Θ^{∗}(J_{k}, J_{k+1}), …, J_{t}) k = 1, …, t − 1.

The translation of the involutions Θ_{k}^{∗}, k = 1, …, t, on indexing sets to words, are the involutions σ_{k}, k = 1, …, t − 1, restricted to words which with respect to the subalphabet {k, k + 1} are either Yamanouchi words or dual Yamanouchi words.

Let Θ^{∗}(J_{k}, J_{k+1}) = (J_{k}^{∗}, J_{k+1}^{∗}), then

σ_{k}(w(J_{1}, …, J_{t})) = w(J_{1}, …, J_{k}^{∗}, J_{k+1}^{∗}, …, J_{t}).

For instance, let w = 122111211 be the two-letter word. Using the involution h_{1},

w = 1(2(21)1)1(21)1 ⟶ σ_{1}(w) = 222112212.

On the other hand, let J_{1} = {1, 4, 5, 6, 8, 9} and J_{2} = {2, 3, 7} be indexing sets of the word w. We have min_{J_{2}}J_{1} = {4, 5, 8},

Θ^{∗}(J_{1}, J_{2}) = ({4, 5, 8}, {1, 2, 3, 6, 7, 9})

and the word generated by Θ^{∗}(J_{1}, J_{2}) is 222112212 = σ_{1}(w).

3.2 Young tableaux

A partition is a sequence of non negative integers, a = (a_{1}, a_{2}, ...), all but a finite number of which are non zero, such that a_{1} ≥ a_{2} ≥ ... The number |a| := ∑_{i} a_{i} is called the weight of a; the maximum value of i for which a_{i} > 0 is called the length of a and is denoted by l(a). If l(a) = 0 we have the null partition a = (0, 0, ...). If l(a) = k, we shall often write a = (a_{1}, ..., a_{k}).

Sometimes it is convenient to use the notation

a = (a_{1}^{m_{1}}, a_{2}^{m_{2}}, ..., a_{k}^{m_{k}}),

where a_{1} > a_{2} > ... > a_{k} and a_{i}^{m_{i}}, with m_{i} ≥ 0, means that a_{i} appears m_{i} times as a part of a.

We say that a is an elementary partition if there is an m ∈ {1, ..., n} such that a = (1^{m}). Suppose a = (a_{1}, ..., a_{k}) is a partition of length k with |a| = n. The Young diagram

of a is an array of n boxes having k left-justified rows with row i containing a_{i} boxes for 1 ≤ i ≤ k. We shall identify a partition with its Young diagram.

Given two partitions a and c, we write a ⊆ c to mean a_{i} ≤ c_{i}, for all i. Graphically, this means that the Young diagram of a is contained in the Young diagram of c.

Let a and c be partitions such that a ⊆ c. We define

c/a := {(i, j) ∈ c : (i, j) ∉ a},

called a skew-diagram. We write |c/a| := |c| − |a|.

A skew-diagram is called a vertical [horizontal] m-strip, where m > 0, if it has m boxes and at most one box in each row [column].

Let a and c be partitions such that a ⊆ c and (m_{1}, ..., m_{t}) a sequence of positive integers. A Young tableau T of type (a, (m_{1}, ..., m_{t}), c) is a sequence of partitions

T = (a^{0}, a^{1}, ..., a^{t})

such that a = a^{0} ⊆ a^{1} ⊆ ... ⊆ a^{t} = c and, for each k = 1, ..., t, the skew-diagram a^{k}/a^{k−1} is a vertical strip labeled by k with m_{k} = |a^{k}/a^{k−1}|.

The indexing sets J_{1}, ..., J_{t} of T are the subsets of {1, ..., n} given by

J_{k} = {i : a_{i}^{k} − a_{i}^{k−1} ≠ 0}, 1 ≤ k ≤ t.

That is, J_{k} is defined by the row indices of the boxes of c/a labeled by k, 1 ≤ k ≤ t. Notice that (|J_{1}|, ..., |J_{t}|) = (m_{1}, ..., m_{t}).

The skew-diagram c/a is called the shape of the tableau T and (m_{1}, ..., m_{t}) the weight of T .

For example,

x x x 1 4
x x 1 3 4
x 1

2 is a Young tableau of type ((3, 2, 1), (3, 1, 1, 2), (5, 5, 2, 1)), with indexing sets J_{1} = {1, 2, 3}, J_{2} = {4}, J_{3} = {2} and J_{4} = {1, 2}.

We will introduce now the notion of Littlewood-Richardson sequence, following the terminology in [1, 2, 3].

Definition 3.1 [1] Let T be a Young tableau of type (a, (m_{1}, ..., m_{t}), c). We say that T is a Littlewood-Richardson (LR for short) sequence if its indexing sets satisfy J_{1} ≥ J_{2} ≥ ... ≥ J_{t}.

Proposition 2.1 (c) shows that this definition is equivalent to the one given in [9].

If a = (a_{1}, …, a_{n}) and c = (c_{1}, …, c_{n}) with a ⊆ c (the diagram of a is contained in the diagram of c), we put \overline{a} := (c_{1} − a_{n}, …, c_{1} − a_{2}, c_{1} − a_{1}) and \overline{c} = (c_{1} − c_{n}, c_{1} − c_{n−1}, …, c_{1} − c_{2}, 0). Note that \overline{a} and \overline{c} are respectively the complements of a and c in the n×c_{1} rectangle.

Given a tableau T of type (a, (m_{1}, …, m_{t}), c) and indexing sets J_{1}, …, J_{t}, its complement, denoted by \overline{T} , is the tableau of type (\overline{c}, (m_{t}, …, m_{1}), \overline{a}) with indexing sets op(J_{t}), …, op(J_{1}). When T is an LR tableau, we have op(J_{t}) ≥_{op} … ≥_{op} op(J_{1}).

Geometrically, \overline{T} , the complement tableau of T , is obtained by reflecting T once about the horizontal axis, then once about the vertical axis and then substituting labels i ∈ {1, …, t} by op(i) = t − i + 1, with op ∈ S_{t}, i.e., J_{i} by op(J_{t−i+1}), with op ∈ S_{n}, for i = 1, …, t. As usual if T is of type (a, (m_{1}, …, m_{t}), c) we say that c/a is the skew-shape of T . We define the complement of the skew-shape of T , as being the skew-shape of \overline{T} , \overline{a}/\overline{c}.

Definition 3.2 The word of a tableau T , denoted by ω(T ) on the alphabet [t], is the word generated by the indexing sets of T .

This definition agrees with the one given in [6]: the word of a tableau may be obtained by listing the labels from right to left in each row, starting in the top and moving to bottom. We may also characterize LR tableaux and complement tableaux, using the language of words. Clearly, T is an LR tableau iff its word is a Yamanouchi word. Let T be a tableau of type (a, (m_{1}, …, m_{t}), c) with word x_{1} … x_{r}, and H a tableau of type (\overline{c}, (m_{t}, …, m_{1}), \overline{a}). H is the complement of T iff ω(H) = op(x_{r}) … op(x_{1}) the dual word of T .

In previous example, ω(T ) = 4143112 and ω(\overline{T} ) = 3442141.

There is a bijection between LR tableaux and complement LR tableaux given by the bijection between chains and dual chains, that is,

J_{1} ≥ … ≥ J_{t} ⟶ op(J_{t}) ≥ … ≥ op(J_{1}).

Definition 3.3 We say that a tableau T of type (a, (m_{1}, …, m_{t}), c) is an op-LR (reversing LR tableau) if its indexing sets are such that J_{1} ≥_{op} … ≥_{op} J_{t}.

Therefore, T is an op-LR tableau iff its word is the dual of a Yamanouchi word.

Hence, T is an op-LR tableau iff its complement is an LR tableau. This means that our definition of reversing LR tableau is based on the notion of complementation. Our aim now is twice-fold: avoid duality and to interpret an op-LR as a consequence of the action of the symmetric group S_{t} on a family of indexing sets in order to introduce σ-LR tableaux where σ is any permutation; and exhibit a bijection between LR tableaux and σ-LR tableaux of a given type.

In [5] we have interpreted the LR reverse filling as a permutation of the LR rule and we have exhibited a bijection between op-LR tableaux and LR tableaux. In this way we have also established a bijection between LR tableaux and their conjugate.

4 Actions of the symmetric group

Let t ≥ 2, and consider the transpositions of consecutive positive integers s_{i} = (i i + 1), 1 ≤ i ≤ t − 1. Denote the identity by s_{0}. The symmetric group S_{t}, t ≥ 1, is generated by these involutions s_{i}, i = 1, …, t − 1, written S_{t} =< s_{1}, …, s_{t−1} >, which satisfy the Moore-Coxeter relations: s_{i}^{2} = s_{0}, s_{i}s_{j} = s_{j}s_{i}, if |i − j| ≠ 1, and s_{i}s_{i+1}s_{i} = s_{i+1}s_{i}s_{i+1}.

The elements of S_{t}, t ≥ 1, may be written as words on the alphabet {s_{1}, ..., s_{t−1}}, defined recursively as follows:

S_{1} = {s_{0}},

S_{t} = { ω ; s_{t−1}ω ; s_{t−2}s_{t−1}ω , ω ∈ S_{t−1} ; ⋮ ; s_{1}s_{2}...s_{t−1}ω } , if t ≥ 2.  (20)

We call these words, canonical words of S_{t}.

Definition 4.1 Let F_{1} ≥ F_{2} and 𝔽 = {(F_{1}^{σ}, F_{2}^{σ}) : σ ∈< s_{1} >} ⊆ H ∪ H^{op}. We say that 𝔽 is generated by (F_{1}, F_{2}), if (F_{1}^{s_{0}}, F_{2}^{s_{0}}) = (F_{1}, F_{2}), and there exists a map s : H → H^{op} such that s(F_{1}, F_{2}) = (F_{1}^{s_{1}}, F_{2}^{s_{1}}).

Given 𝔽 = {(F_{1}^{σ}, F_{2}^{σ}) : σ ∈< s_{1} >} ⊆ H ∪ H^{op} generated by (F_{1}, F_{2}), we may define the involutions on 𝔽, ψ_{s_{i}}(F_{1}^{σ}, F_{2}^{σ}) = (F_{1}^{s_{i}σ}, F_{2}^{s_{i}σ}), i = 0, 1, with σ ∈ {s_{0}, s_{1}}. Thus, the map ψ : S_{2} → S_{F} defined by ψ(s_{0}) = ψ_{s_{0}} and ψ(s_{1}) = ψ_{s_{1}}, is an isomorphism if |F_{1}| > |F_{2}|, and an homomorphism if |F_{1}| = |F_{2}|. Therefore, ψ defines an action of the symmetric group S_{2} on 𝔽.

As Θ^{∗} : H ∪ H^{op} → H ∪ H^{op} is an involution, if we put ψ(s_{1}) = Θ^{∗} and ψ(s_{0}) = id, ψ defines an action of the symmetric group S_{2} on H ∪ H^{op}.

Recall that s_{0}, s_{1}, s_{2}, s_{2}s_{1}, s_{1}s_{2}, s_{1}s_{2}s_{1} are the canonical words of S_{3}.

Definition 4.2 Given F_{1} ≥ F_{2} ≥ F_{3} and 𝔽 = {(F_{1}^{σ}, F_{2}^{σ}, F_{3}^{σ}) ∈ P(n)^{3} : σ ∈< s_{1}, s_{2} >}, with (F_{1}^{s_{0}}, F_{2}^{s_{0}}, F_{3}^{s_{0}}) = (F_{1}, F_{2}, F_{3}), we say that 𝔽 is generated by (F_{1}, F_{2}, F_{3}) if (I) (a) F_{3}^{s_{1}} = F_{3} and {(F_{1}^{σ}, F_{2}^{σ}) : σ ∈< s_{1} >} is generated by (F_{1}, F_{2}).

(b) F_{1}^{s_{2}} = F_{1} and {(F_{2}^{σ}, F_{3}^{σ}) : σ ∈< s_{2} >} is generated by (F_{2}, F_{3}).

(II) (a) F_{1}^{s_{2}s_{1}} = F_{1}^{s_{1}} and {(F_{2}^{σs_{1}}, F_{3}^{σs_{1}}) : σ ∈< s_{2} >} is generated by (F_{2}^{s_{1}}, F_{3}^{s_{1}}) and s(F_{2}^{s_{1}}, F_{3}^{s_{1}}) = (F_{2}^{s_{2}s_{1}}, F_{3}^{s_{2}s_{1}}) such that F_{2}^{s_{2}s_{1}} = X ∪ Y with X ⊆ F_{2}^{s_{2}} and Y ⊆

F_{1} \ F_{1}^{s_{1}} only if F_{2}^{s_{2}} = X ∪ Z with Z ≥ Y.

(b) F_{3}^{s_{1}s_{2}} = F_{3}^{s_{2}} and {(F_{1}^{σs_{2}}, F_{2}^{σs_{2}}) : σ ∈< s_{1} >} is generated by (F_{1}^{s_{2}}, F_{2}^{s_{2}}) and s(F_{1}^{s_{2}}, F_{2}^{s_{2}}) = (F_{1}^{s_{1}s_{2}}, F_{2}^{s_{1}s_{2}}) such that F_{1}^{s_{1}s_{2}} ⊆ F_{1}^{s_{1}} and F_{1}^{s_{1}} \ F_{1}^{s_{1}s_{2}} ≥ F_{2} \ F_{2}^{s_{2}}.

(III) F_{3}^{s_{1}s_{2}s_{1}} = F_{3}^{s_{2}s_{1}} and {(F_{1}^{σs_{2}s_{1}}, F_{2}^{σs_{2}s_{1}}) : σ ∈< s_{1} >} is generated by (F_{1}^{s_{2}s_{1}}, F_{2}^{s_{2}s_{1}}) and s(F_{1}^{s_{2}s_{1}}, F_{2}^{s_{2}s_{1}}) = (F_{1}^{s_{1}s_{2}s_{1}}, F_{2}^{s_{1}s_{2}s_{1}}) such that F_{1}^{s_{1}s_{2}s_{1}} = F_{1}^{s_{1}s_{2}}.

Proposition 4.1 Let F_{1} ≥ F_{2} ≥ F_{3}.

(a) There exists always a set 𝔽 generated by (F_{1}, F_{2}, F_{3}).

(b) If 𝔽 is generated by (F_{1}, F_{2}, F_{3}), then F_{2}^{s_{1}s_{2}} ≥ F_{2}^{s_{1}} and F_{2}^{s_{2}} ≥ F_{2}^{s_{2}s_{1}}.

(c) If 𝔽 is generated by (F_{1}, F_{2}, F_{3}), then, for each σ ∈< s_{1}, s_{2} >,

(i) either F_{i}^{σ} ≥ F_{i+1}^{σ} or F_{i}^{σ} ≥_{op} F_{i+1}^{σ}, 1 ≤ i ≤ 2;

(ii) F_{3} ⊆ F_{3}^{σ};

(iii) there exist G_{i}^{σ} ⊆ F_{i}^{σ} for i = 1, 2, 3, with |G_{i}^{σ}| = |F_{3}| such that G_{3}^{σ} = F_{3} and G_{1}^{σ} ≥ G_{2}^{σ} ≥ F_{3}.

Proof: Since F_{1} ≥ F_{2} and F_{2} ≥ F_{3}, let {(F_{1}^{σ}, F_{2}^{σ}) : σ ∈< s_{1} >} be generated by (F_{1}, F_{2}), and let {(F_{2}^{σ}, F_{3}^{σ}) : σ ∈< s_{2} >} be generated by (F_{2}, F_{3}). Clearly F_{2}^{s_{1}} ≥ F_{3}^{s_{1}} and F_{1}^{s_{2}} ≥ F_{2}^{s_{2}}.

We may choose a witness s of F_{2}^{s_{1}} ≥ F_{3}^{s_{1}} with F_{2}^{s_{1}}∩F_{3}^{s_{1}} ⊆ s(F_{3}^{s_{1}}), such that s(F_{2}^{s_{1}}, F_{3}^{s_{1}}) = (F_{2}^{s_{2}s_{1}}, F_{3}^{s_{2}s_{1}}) satisfies

F_{2}^{s_{2}s_{1}} = X ∪ Y, with X ⊆ F_{2}^{s_{2}}, Y ⊆ F_{1} \ F_{1}^{s_{1}}, only if
F_{2}^{s_{2}} = X ∪ Z, with Z ≥ Y.  (21)

For F_{2}^{s_{1}} = F_{2}∪(F_{1}\F_{1}^{s_{1}}), F_{2}^{s_{2}} ⊆ F_{2}, F_{2}∩F_{3} ⊆ F_{2}^{s_{2}}, F_{2}^{s_{2}} ≥ F_{3}, and |F_{2}^{s_{2}s_{1}}| = |F_{2}^{s_{2}}| = |F_{3}|. Theorem 2.8, asserts that (21) is feasible. Note that from (21), we have

F_{2}^{s_{2}} ≥ F_{2}^{s_{2}s_{1}}.  (22)

We may choose a witness s of F_{1}^{s_{2}} ≥ F_{2}^{s_{2}} with F_{1}^{s_{2}}∩F_{2}^{s_{2}} ⊆ s(F_{2}^{s_{2}}), such that s(F_{1}^{s_{2}}, F_{2}^{s_{2}}) = (F_{1}^{s_{1}s_{2}}, F_{2}^{s_{1}s_{2}}) satisfies

F_{1}^{s_{1}s_{2}} ⊆ F_{1}^{s_{1}},
F_{1}^{s_{1}} \ F_{1}^{s_{1}s_{2}} ≥ F_{2} \ F_{2}^{s_{2}}.  (23)

For, F_{1} ∩ F_{2} ⊆ F_{1}^{s_{1}}, F_{1}^{s_{1}} ≥ F_{2}, and F_{2} = F_{2}^{s_{2}} ∪ (F_{3}^{s_{2}} \ F_{3}). Again, proposition (2.4), (c), asserts that (23) is feasible.

Notice that F_{2}^{s_{1}s_{2}} ≥ F_{3}^{s_{1}s_{2}} = F_{3}^{s_{2}}. Note also that F_{2}^{s_{1}s_{2}} = F_{2}^{s_{2}} ∪ (F_{1} \ F_{1}^{s_{1}s_{2}}) = F_{2}^{s_{2}} ∪ (F_{1} \ F_{1}^{s_{1}}) ∪ (F_{1}^{s_{1}} \ F_{1}^{s_{1}s_{2}}) and F_{2}^{s_{1}} = F_{2} ∪ (F_{1} \ F_{1}^{s_{1}}) = F_{2}^{s_{2}} ∪ (F_{2} \ F_{2}^{s_{2}}) ∪ (F_{1} \ F_{1}^{s_{1}}). Henceforth, by (23), we find

F_{2}^{s_{1}s_{2}} ≥ F_{2}^{s_{1}}.  (24)

Finally, we may choose a witness s of F_{1}^{s_{2}s_{1}} ≥ F_{2}^{s_{2}s_{1}} with F_{1}^{s_{2}s_{1}} ∩ F_{2}^{s_{2}s_{1}} ⊆ s(F_{2}^{s_{2}s_{1}}) such that s(F_{1}^{s_{2}s_{1}}, F_{2}^{s_{2}s_{1}}) = (F_{1}^{s_{1}s_{2}s_{1}}, F_{2}^{s_{1}s_{2}s_{1}}), satisfies F_{1}^{s_{1}s_{2}s_{1}} = F_{1}^{s_{1}s_{2}}. From (23) and recalling that F_{1}^{s_{2}s_{1}} = F_{1}^{s_{1}}, it is enough to show that (F_{1}^{s_{2}s_{1}}, F_{2}^{s_{2}s_{1}}) and (F_{1}^{s_{1}s_{2}}, F_{2}^{s_{1}s_{2}s_{1}}) satisfy (18), that is,

F_{1}^{s_{1}s_{2}} ⊆ F_{1}^{s_{1}} = F_{1}^{s_{2}s_{1}},

and using (21) and (22),

F_{1}^{s_{2}s_{1}} ∩ F_{2}^{s_{2}s_{1}} ⊆ F_{1}^{s_{2}} ∩ F_{2}^{s_{2}} ⊆ F_{1}^{s_{1}s_{2}}, F_{1}^{s_{1}s_{2}} ≥ F_{2}^{s_{2}} ≥ F_{2}^{s_{2}s_{1}}.

Conditions of definition 4.2 are, therefore, fulfilled.

Hence, 𝔽 is generated by (F_{1}, F_{2}, F_{3}).

(b) was obtained in (22) and (24).

(c) (i) and (ii) are consequence of (18).

(iii) Note that F_{1}^{s_{1}s_{2}} ≥ F_{2}^{s_{2}} ≥ F_{3} and since F_{2}^{s_{2}} ≥ F_{2}^{s_{2}s_{1}}, it follows F_{1}^{s_{1}s_{2}} ≥ F_{2}^{s_{2}s_{1}} ≥ F_{3}, with |F_{1}^{s_{1}s_{2}}| = |F_{2}^{s_{2}}| = |F_{2}^{s_{2}s_{1}}| = |F_{3}|. The sets in the first sequence are subsets of F_{1}^{σ}, F_{2}^{σ}, F_{3}^{σ}, respectively, for σ ∈ {s_{0}, s_{1}, s_{2}, s_{1}s_{2}}, and the sets in the second sequence are subsets of F_{1}^{σ}, F_{2}^{σ}, F_{3}^{σ}, for σ ∈ {s_{2}s_{1}, s_{1}s_{2}s_{1}}. □

Theorem 4.2 Let 𝔽 = {(F_{1}^{σ}, F_{2}^{σ}, F_{3}^{σ}) : σ ∈< s_{1}, s_{2} >}. 𝔽 is be generated by (F_{1}, F_{2}, F_{3}) iff

(I) (a) F_{3}^{s_{1}} = F_{3} and {(F_{1}^{σ}, F_{2}^{σ}) : σ ∈< s_{1} >} is generated by (F_{1}, F_{2}).

(b) F_{1}^{s_{2}} = F_{1} and {(F_{2}^{σ}, F_{3}^{σ}) : σ ∈< s_{2} >} is generated by (F_{2}, F_{3}).

(II) (a) F_{1}^{s_{2}s_{1}} = F_{1}^{s_{1}} and {(F_{2}^{σs_{1}}, F_{3}^{σs_{1}}) : σ ∈< s_{2} >} is generated by (F_{2}^{s_{1}}, F_{3}^{s_{1}}).

(b) F_{3}^{s_{1}s_{2}} = F_{3}^{s_{2}} and 𝔽_{s_{1}s_{2}} := {(F_{1}^{σs_{2}}, F_{2}^{σs_{2}}) : σ ∈< s_{1} >} is generated by (F_{1}^{s_{2}}, F_{2}^{s_{2}}).

(III) (a) F_{3}^{s_{1}s_{2}s_{1}} = F_{3}^{s_{2}s_{1}} and {(F_{1}^{σs_{2}s_{1}}, F_{2}^{σs_{2}s_{1}}) : σ ∈< s_{1} >} is generated by (F_{1}^{s_{2}s_{1}}, F_{2}^{s_{2}s_{1}}) and s(F_{1}^{s_{2}s_{1}}, F_{2}^{s_{2}s_{1}}) = (F_{1}^{s_{1}s_{2}s_{1}}, F_{2}^{s_{1}s_{2}s_{1}}) such that F_{1}^{s_{1}s_{2}s_{1}} = F_{1}^{s_{1}s_{2}}.

(b) {(F_{2}^{s_{1}s_{2}}, F_{3}^{s_{1}s_{2}}); (F_{2}^{s_{1}s_{2}s_{1}}, F_{3}^{s_{1}s_{2}s_{1}})} is generated by (F_{2}^{s_{1}s_{2}}, F_{3}^{s_{1}s_{2}}).

(IV) F_{2}^{s_{1}s_{2}} ≥ F_{2}^{s_{1}} and F_{2}^{s_{2}} ≥ F_{2}^{s_{2}s_{1}}.

Proof: The only if part. Suppose that 𝔽 satisfy the conditions of definition 4.2. We have only to prove (III), (b). Note that F_{2}^{s_{1}s_{2}} ≥ F_{3}^{s_{1}s_{2}}. We shall show that we may choose a witness s of F_{2}^{s_{1}s_{2}} ≥ F_{3}^{s_{1}s_{2}} with F_{2}^{s_{1}s_{2}} ∩ F_{3}^{s_{1}s_{2}} ⊆

s(F_{2}^{s_{1}s_{2}}) such that

s(F_{2}^{s_{1}s_{2}}, F_{3}^{s_{1}s_{2}}) = (F_{2}^{s_{1}s_{2}s_{1}}, F_{3}^{s_{1}s_{2}s_{1}}).

In fact, recalling definition 4.2, we have F_{1}^{s_{1}s_{2}s_{1}} = F_{1}^{s_{1}s_{2}}, F_{2}^{s_{1}s_{2}} = F_{2}^{s_{2}} ∪ (F_{1} \ F_{1}^{s_{1}s_{2}}) and F_{2}^{s_{1}s_{2}s_{1}} = F_{2}^{s_{2}s_{1}} ∪ (F_{1}^{s_{2}s_{1}} \ F_{1}^{s_{1}s_{2}}), and using (21),(23), we get

F_{2}^{s_{1}s_{2}s_{1}} ⊆ F_{2}^{s_{1}s_{2}}.

On the other hand, from F_{1}^{s_{1}} \ F_{1}^{s_{1}s_{2}} ≥ F_{2} \ F_{2}^{s_{2}} = F_{3}^{s_{2}} \ F_{3}, and since F_{2}^{s_{2}s_{1}} ≥ F_{3}, we have

F_{2}^{s_{1}s_{2}s_{1}} = F_{2}^{s_{2}s_{1}} ∪ (F_{1}^{s_{2}s_{1}} \ F_{1}^{s_{1}s_{2}}) ≥ F_{3} ∪ (F_{3}^{s_{2}} \ F_{3}) = F_{3}^{s_{1}s_{2}}.

Now, using (21), notice that (F_{1} \ F_{1}^{s_{1}}) ∩ F_{3}^{s_{2}} ⊆ Y,

and write F_{2}^{s_{1}s_{2}s_{1}} = X ∪ Y ∪ (F_{1}^{s_{1}} \ F_{1}^{s_{1}s_{2}}), with X ⊆ F_{2}^{s_{2}} and Y ⊆ F_{1} \ F_{1}^{s_{1}}. Then, recalling that F_{3}^{s_{1}s_{2}} = F_{3}^{s_{2}}, we get

F_{2}^{s_{1}s_{2}} ∩ F_{3}^{s_{1}s_{2}} = (F_{2}^{s_{2}} ∩ F_{3}^{s_{2}}) ∪ ((F_{1} \ F_{1}^{s_{1}s_{2}}) ∩ F_{3}^{s_{2}})
= (F_{2}^{s_{2}} ∩ F_{3}) ∪ (((F_{1} \ F_{1}^{s_{1}}) ∪ (F_{1}^{s_{1}} \ F_{1}^{s_{1}s_{2}})) ∩ F_{3}^{s_{2}})
⊆ X ∪ ((F_{1} \ F_{1}^{s_{1}}) ∩ F_{3}^{s_{2}}) ∪ ((F_{1}^{s_{1}} \ F_{1}^{s_{1}s_{2}}) ∩ F_{3}^{s_{2}})
⊆ X ∪ Y ∪ ((F_{1}^{s_{1}} \ F_{1}^{s_{1}s_{2}}) = F_{2}^{s_{1}s_{2}s_{1}}.

Finally, recalling that F_{2} ∩ (F_{1} \ F_{1}^{s_{1}}) = ∅, we have

F_{3}^{s_{1}s_{2}s_{1}} = F_{3}^{s_{2}s_{1}} = F_{3} ∪ (F_{2}^{s_{1}} \ F_{2}^{s_{2}s_{1}})
= F_{3} ∪ ((F_{2} ∪ (F_{1} \ F_{1}^{s_{1}})) \ F_{2}^{s_{2}s_{1}})
= F_{3} ∪ (F_{2} \ F_{2}^{s_{2}s_{1}}) ∪ ((F_{1} \ F_{1}^{s_{1}}) \ F_{2}^{s_{2}s_{1}}),

On the other hand, since F_{2}^{s_{2}} ∩ (F_{1} \ F_{1}^{s_{1}s_{2}}) = ∅ and (F_{1}^{s_{1}} \ F_{1}^{s_{1}s_{2}}) ∩ F_{2}^{s_{2}} = ∅, F_{1}^{s_{2}s_{1}} = F_{1}^{s_{1}}, and F_{1}^{s_{1}s_{2}} ⊆ F_{1}^{s_{1}}, we get

F_{3}^{s_{1}s_{2}s_{1}} = F_{3}^{s_{1}s_{2}} ∪ (F_{2}^{s_{1}s_{2}} \ F_{2}^{s_{1}s_{2}s_{1}})
= F_{3} ∪ (F_{2} \ F_{2}^{s_{2}}) ∪ ((F_{2}^{s_{2}} ∪ (F_{1} \ F_{1}^{s_{1}s_{2}})) \ (F_{2}^{s_{2}s_{1}} ∪ (F_{1}^{s_{2}s_{1}} \ F_{1}^{s_{1}s_{2}})))
= F_{3} ∪ (F_{2} \ F_{2}^{s_{2}}) ∪ (F_{2}^{s_{2}} \ (F_{2}^{s_{2}s_{1}} ∪ (F_{1}^{s_{2}s_{1}} \ F_{1}^{s_{1}s_{2}}))) ∪
∪((F_{1} \ F_{1}^{s_{1}s_{2}}) \ (F_{2}^{s_{2}s_{1}} ∪ (F_{1}^{s_{2}s_{1}} \ F_{1}^{s_{1}s_{2}})))

= F_{3} ∪ (F_{2} \ F_{2}^{s_{2}}) ∪ (F_{2}^{s_{2}} \ F_{2}^{s_{2}s_{1}}) ∪ ((F_{1} \ F_{1}^{s_{1}s_{2}}) \ (F_{2}^{s_{2}s_{1}} ∪ (F_{1}^{s_{1}} \ F_{1}^{s_{1}s_{2}})))

= F_{3} ∪ (F_{2} \ F_{2}^{s_{2}s_{1}}) ∪ [((F_{1} \ F_{1}^{s_{1}s_{2}}) \ (F_{1}^{s_{1}} \ F_{1}^{s_{1}s_{2}})) \ F_{2}^{s_{2}s_{1}}]
= F_{3} ∪ (F_{2} \ F_{2}^{s_{2}s_{1}}) ∪ ((F_{1} \ F_{1}^{s_{1}}) \ F_{2}^{s_{2}s_{1}}).

Henceforth, the map s is well defined.

The if part . Suppose that 𝔽 = {(F_{1}^{σ}, F_{2}^{σ}, F_{3}^{σ}) : σ ∈< s_{1}, s_{2} >} satisfy (I), (II), (III) and (IV) as above. To show that 𝔽 is generated by (F_{1}, F_{2}, F_{3}) it remains to prove (II) of definition 4.2.

Since {(F_{2}^{σs_{1}}, F_{3}^{σs_{1}}) : σ ∈< s_{2} >} is generated by (F_{2}^{s_{1}}, F_{3}^{s_{1}}), we have F_{2}^{s_{2}s_{1}} ⊆ F_{2}^{s_{1}} = F_{2} ∪ (F_{1} \ F_{1}^{s_{1}}) and, therefore,

F_{2}^{s_{2}s_{1}} = X ∪ Y, where X ⊆ F_{2} and Y ⊆ F_{1} \ F_{1}^{s_{1}}.

From (III),(a) and (b) above, we get F_{1}^{s_{1}s_{2}} = F_{1}^{s_{1}s_{2}s_{1}} ⊆ F_{1}^{s_{1}}.

We may write

F_{2}^{s_{1}s_{2}s_{1}} = F_{2}^{s_{2}s_{1}} ∪ (F_{1}^{s_{1}} \ F_{1}^{s_{1}s_{2}}) = X ∪ Y ∪ (F_{1}^{s_{1}} \ F_{1}^{s_{1}s_{2}}),  (25)

and

F_{2}^{s_{1}s_{2}} = F_{2}^{s_{2}} ∪ (F_{1} \ F_{1}^{s_{1}s_{2}}) = F_{2}^{s_{2}} ∪ (F_{1} \ F_{1}^{s_{1}}) ∪ (F_{1}^{s_{1}} \ F_{1}^{s_{1}s_{2}}).  (26)

On the other hand, from (III), (b), we have the inclusion F_{2}^{s_{1}s_{2}s_{1}} ⊆ F_{2}^{s_{1}s_{2}}. As X ⊆ F_{2}^{s_{2}s_{1}} and F_{2}^{s_{2}s_{1}}, we get from (25), (26), X ⊆ F_{2}^{s_{2}}. Let Z := F_{2}^{s_{2}} \ X. Since F_{2}^{s_{2}} ≥ F_{2}^{s_{2}s_{1}}, we must have Z ≥ Y.

Finally, from proposition 2.3, using F_{2}^{s_{1}s_{2}} ≥ F_{2}^{s_{1}}, (26), and F_{2}^{s_{1}} = F_{2} ∪ (F_{1} \ F_{1}^{s_{1}}), we get F_{1}^{s_{1}} \ F_{1}^{s_{1}s_{2}} ≥ F_{2} \ F_{2}^{s_{2}}.

Therefore, the set 𝔽 is generated by the sequence (F_{1}, F_{2}, F_{3}). □

Remark 2 If in definition 4.2 we replace condition (II)(a) by

F_{2}^{s_{2}s_{1}} = X ∪ Y with X ⊆ F_{2}^{s_{2}} and Y ⊆ F_{1} \ F_{1}^{s_{1}} only if F_{1}^{s_{1}s_{2}} ≥ X ∪ Y

then proposition 4.1 follows except condition (a), as well as theorem 4.2 except condition (IV).

Corollary 4.3 Let F_{1} ≥ F_{2} ≥ F_{3} and 𝔽 = {(F_{1}^{σ}, F_{2}^{σ}, F_{3}^{σ}) : σ ∈< s_{1}, s_{2} >} generated by (F_{1}, F_{2}, F_{3}). Let ψ_{s_{i}} : 𝔽 → 𝔽 defined by ψ_{s_{i}}(F_{1}^{σ}, F_{2}^{σ}, F_{3}^{σ}) = (F_{1}^{s_{i}σ}, F_{2}^{s_{i}σ}, F_{3}^{s_{i}σ}), i = 0, 1, 2, σ ∈< s_{1}, s_{2} >. Then, ψ_{s_{i}}^{2} = id, i = 1, 2, and ψ_{s_{1}}ψ_{s_{2}}ψ_{s_{1}} = ψ_{s_{2}}ψ_{s_{1}}ψ_{s_{2}}. That is, the symmetric group S_{3} acts on the set 𝔽.

The generation of the set 𝔽 by F_{1} ≥ F_{2} ≥ F_{3} is equivalent to a decomposition of F_{1} ≥ F_{2} ≥ F_{3}.

Theorem 4.4 Let F_{1} ≥ F_{2} ≥ F_{3}. The following assertions are equivalent:

(a) 𝔽 = {(F_{1}^{σ}, F_{2}^{σ}, F_{3}^{σ}) : σ ∈< s_{1}, s_{2} >} is generated by (F_{1}, F_{2}, F_{3}).

(b) The sequence F_{1} ≥ F_{2} ≥ F_{3} has a decomposition F_{1} = ∪_{j=1}^{5}A_{1}^{j}, F_{2} = ∪_{j=3}^{5}A_{2}^{j}, F_{3} = A_{3}^{5} ∪ A_{3}^{2},

F_{1}, F_{2}, F_{3} = \begin{matrix}A_{1}^{1} \\ A_{1}^{2} & & A_{3}^{2} \\ A_{1}^{3} & A_{2}^{3} \\ A_{1}^{4} & A_{2}^{4} \\ A_{1}^{5} & A_{2}^{5} & A_{3}^{5} \end{matrix}  (27)

satisfying:

1. A_{1}^{4} ≥ A_{2}^{4} ≥ A_{1}^{2} ≥ A_{3}^{2}, with |A_{1}^{4}| = |A_{2}^{4}| = |A_{1}^{2}| = |A_{3}^{2}|, A_{1}^{5} ≥ A_{2}^{5} ≥ A_{3}^{5}, with |A_{1}^{5}| = |A_{2}^{5}| = |A_{3}^{5}|, A_{1}^{3} ≥ A_{2}^{3}, with |A_{1}^{3}| = |A_{2}^{3}|.

2. A_{1}^{i} ∩ A_{1}^{j} = ∅, if i ≠ j, A_{2}^{i} ∩ A_{2}^{j} = ∅, if i ≠ j, A_{3}^{2} ∩ A_{3}^{5} = ∅.

3. F_{1} ∩ A_{2}^{5} ⊆ A_{1}^{5}, (F_{1} \ A_{1}^{5}) ∩ A_{2}^{4} ⊆ A_{1}^{4}, [F_{1} \ (A_{1}^{5} ∪ A_{1}^{4})] ∩ A_{2}^{3} ⊆ A_{1}^{3}, [F_{2} ∪ (A_{1}^{2} ∪ A_{1}^{1})] ∩ A_{3}^{2} ⊆ A_{1}^{2}, and [F_{2} ∪ (A_{1}^{2} ∪ A_{1}^{1})] ∩ A_{3}^{5} ⊆ A_{2}^{5}.

such that the sets F_{1}^{σ}, F_{2}^{σ}, F_{3}^{σ}, with σ ∈ {s_{1}, s_{2}, s_{1}s_{2}, s_{2}s_{1}, s_{1}s_{2}s_{1}}, are obtained from F_{1}, F_{2}, F_{3} as follows:

F_{1}^{s_{1}}, F_{2}^{s_{1}}, F_{3}^{s_{1}} = \begin{aligned}& A_{1}^{1} \\ & A_{1}^{2} & A_{3}^{2} \\ A_{1}^{3} & A_{2}^{3} \\ A_{1}^{4} & A_{2}^{4} \\ A_{1}^{5} & A_{2}^{5} & A_{3}^{5} \end{aligned} , F_{1}^{s_{2}s_{1}}, F_{2}^{s_{2}s_{1}}, F_{3}^{s_{2}s_{1}} = \begin{aligned}& & A_{1}^{1} \\ & A_{1}^{2} & A_{3}^{2} \\ A_{1}^{3} & & A_{2}^{3} \\ A_{1}^{4} & & A_{2}^{4} \\ A_{1}^{5} & A_{2}^{5} & A_{3}^{5} \end{aligned} ,  (28)

F_{1}^{s_{1}s_{2}s_{1}}, F_{2}^{s_{1}s_{2}s_{1}}, F_{3}^{s_{1}s_{2}s_{1}} = \begin{aligned}& & A_{1}^{1} \\ & A_{1}^{2} & A_{3}^{2} \\ & A_{1}^{3} & A_{2}^{3} \\ A_{1}^{4} & & A_{2}^{4} \\ A_{1}^{5} & A_{2}^{5} & A_{3}^{5} \end{aligned} ,  (29)

F_{1}^{s_{2}}, F_{2}^{s_{2}}, F_{3}^{s_{2}} = \begin{matrix}A_{1}^{1} \\ A_{1}^{2} & & A_{3}^{2} \\ A_{1}^{3} & & A_{2}^{3} \\ A_{1}^{4} & A_{2}^{4} \\ A_{1}^{5} & A_{2}^{5} & A_{3}^{5} \end{matrix} , F_{1}^{s_{1}s_{2}}, F_{2}^{s_{1}s_{2}}, F_{3}^{s_{1}s_{2}} = \begin{aligned}& A_{1}^{1} \\ & A_{1}^{2} & A_{3}^{2} \\ & A_{1}^{3} & A_{2}^{3} \\ A_{1}^{4} & A_{2}^{4} \\ A_{1}^{5} & A_{2}^{5} & A_{3}^{5} \end{aligned} .  (30)

Proof: (a) ⇒ (b) Let 𝔽 = {(F_{1}^{σ}, F_{2}^{σ}, F_{3}^{σ}) : σ ∈< s_{1}, s_{2} > be generated by the sequence (F_{1}, F_{2}, F_{3}), and consider the involutions ψ_{s_{1}}, ψ_{s_{2}} defined in corollary 4.3.

Since ψ_{s_{1}}(F_{1}, F_{2}, F_{3}) = (F_{1}^{s_{1}}, F_{2}^{s_{1}}, F_{3}^{s_{1}}) and ψ_{s_{2}}(F_{1}, F_{2}, F_{3}) = (F_{1}^{s_{2}}, F_{2}^{s_{2}}, F_{3}^{s_{2}}) we find that F_{1}^{s_{1}} ⊆ F_{1}, F_{1} ∩ F_{2} ⊆ F_{1}^{s_{1}}, F_{2}^{s_{1}} = F_{2} ∪ (F_{1} \ F_{1}^{s_{1}}), and F_{2}^{s_{2}} ⊆ F_{2}, F_{2} ∩ F_{3} ⊆ F_{2}^{s_{2}}, F_{3}^{s_{2}} = F_{3} ∪ (F_{2} \ F_{2}^{s_{2}}).

Consider now the sequence (F_{1}^{s_{2}s_{1}}, F_{2}^{s_{2}s_{1}}, F_{3}^{s_{2}s_{1}}) = ψ_{s_{2}}(F_{1}^{s_{1}}, F_{2}^{s_{1}}, F_{3}^{s_{1}}). We have F_{2}^{s_{2}s_{1}} ⊆ F_{2}^{s_{1}} = F_{2} ∪ (F_{1} \ F_{1}^{s_{1}}). Note that F_{2} and F_{1} \ F_{1}^{s_{1}} are disjoint, since F_{1} ∩ F_{2} ⊆ F_{1}^{s_{1}}. So we may write

F_{2}^{s_{2}s_{1}} = A_{2}^{5} ∪ A_{1}^{2},  (31)

where A_{2}^{5} ⊆ F_{2} and A_{1}^{2} ⊆ F_{1} \ F_{1}^{s_{1}}. Let A_{1}^{1} := F_{1} \ (F_{1}^{s_{1}} ∪ A_{1}^{2}).

From (31), since F_{2}^{s_{2}s_{1}} ≥ F_{3} and |F_{2}^{s_{2}s_{1}}| = |F_{3}|, by we may factorize F_{3} as

F_{3} = A_{3}^{5} ∪ A_{3}^{2},

where A_{2}^{5} ≥ A_{3}^{5}, A_{1}^{2} ≥ A_{3}^{2}, |A_{2}^{5}| = |A_{3}^{5}|, |A_{1}^{2}| = |A_{3}^{2}|, and A_{2}^{5} ∩ A_{2}^{3} = A_{1}^{2} ∩ A_{3}^{5} = ∅. Recalling that F_{2}^{s_{1}} ∩ F_{3}^{s_{1}} ⊆ F_{2}^{s_{2}s_{1}} = A_{3}^{5} ∪ A_{1}^{2}, we find that F_{2}^{s_{1}} ∩ A_{3}^{5} ⊆ A_{2}^{5} and F_{2}^{s_{1}} ∩ A_{3}^{2} ⊆ A_{1}^{2}.

Now, (F_{1}^{s_{1}s_{2}s_{1}}, F_{2}^{s_{1}s_{2}s_{1}}, F_{3}^{s_{1}s_{2}s_{1}}) = ψ_{s_{1}}(F_{1}^{s_{2}s_{1}}, F_{2}^{s_{2}s_{1}}, F_{3}^{s_{2}s_{1}}). Since F_{1}^{s_{1}s_{2}s_{1}} ≥ F_{2}^{s_{2}s_{1}} = A_{2}^{5} ∪ A_{1}^{2}, we may define A_{1}^{5} := min_{A_{2}^{5}}F_{1}^{s_{1}s_{2}s_{1}} and A_{1}^{4} := F_{1}^{s_{1}s_{2}s_{1}} \ A_{1}^{5}. Since F_{1}^{s_{1}s_{2}s_{1}} ⊆ F_{1}^{s_{1}}, define A_{1}^{3} := F_{1}^{s_{1}} \ F_{1}^{s_{1}s_{2}s_{1}}. Then we obtain

F_{1}^{s_{1}s_{2}s_{1}} = A_{1}^{5} ∪ A_{1}^{4}, and F_{1}^{s_{1}} = A_{1}^{5} ∪ A_{1}^{4} ∪ A_{1}^{3},  (32)

where A_{1}^{4} ≥ A_{1}^{2}, A_{1}^{5} ≥ A_{2}^{5}, |A_{1}^{4}| = |A_{1}^{2}|, |A_{1}^{5}| = |A_{2}^{5}|, and F_{1}^{s_{1}s_{2}s_{1}} ∩ A_{2}^{5} ⊆ A_{1}^{5}. Note that F_{1} ∩ A_{2}^{5} ⊆ A_{1}^{5}, since F_{1} ∩ F_{2} ⊆ F_{1}^{s_{1}} and F_{1}^{s_{1}} ∩ F_{2}^{s_{2}s_{1}} ⊆ F_{1}^{s_{1}s_{2}s_{1}}. Since F_{2}^{s_{1}s_{2}s_{1}} = F_{2}^{s_{2}s_{1}} ∪ (F_{1}^{s_{1}} \ F_{1}^{s_{1}s_{2}s_{1}}), we have

F_{2}^{s_{1}s_{2}s_{1}} = A_{2}^{5} ∪ A_{1}^{2} ∪ A_{1}^{3}.  (33)

Consider the sequence (F_{1}^{s_{1}s_{2}}, F_{2}^{s_{1}s_{2}}, F_{3}^{s_{1}s_{2}}) = ψ_{s_{1}}(F_{1}^{s_{2}}, F_{2}^{s_{2}}, F_{3}^{s_{2}}). We have F_{1}^{s_{1}s_{2}} ⊆ F_{1}, F_{1}^{s_{1}s_{2}} ≥ F_{2}^{s_{2}}, and F_{2}^{s_{1}s_{2}} = F_{2}^{s_{2}} ∪ (F_{1} \ F_{1}^{s_{1}s_{2}}). Finally, consider

ψ_{s_{2}}(F_{1}^{s_{1}s_{2}}, F_{2}^{s_{1}s_{2}}, F_{3}^{s_{1}s_{2}}) = (F_{1}^{s_{1}s_{2}s_{1}}, F_{2}^{s_{1}s_{2}s_{1}}, F_{3}^{s_{1}s_{2}s_{1}}).

Thus, we have

F_{1}^{s_{1}s_{2}} = F_{1}^{s_{1}s_{2}s_{1}} = A_{1}^{5} ∪ A_{1}^{4}.

From (33) and the inclusion A_{2}^{5} ∪ A_{1}^{2} ∪ A_{1}^{3} = F_{2}^{s_{2}s_{1}s_{2}} ⊆ F_{2}^{s_{1}s_{2}} = F_{2}^{s_{2}} ∪ A_{1}^{3} ∪ A_{1}^{2} ∪ A_{1}^{1}, it follows that A_{2}^{5} ⊆ F_{2}^{s_{2}} ∪ A_{1}^{1}. But since the sets A_{2}^{5} and A_{1}^{1} are disjoints, we have A_{2}^{5} ⊆ F_{2}^{s_{2}}. Let A_{2}^{4} := F_{2}^{s_{2}} \ A_{2}^{5} and A_{2}^{3} := F_{2} \ F_{2}^{s_{2}}. Thus,

F_{2}^{s_{2}} = A_{2}^{5} ∪ A_{2}^{4}.

Since |F_{2}^{s_{2}}| = |F_{1}^{s_{1}s_{2}}| we have |A_{1}^{4}| = |A_{2}^{4}| and |A_{1}^{3}| = |A_{2}^{3}|. Moreover, from the inequality F_{1}^{s_{1}s_{2}} ≥ F_{2}^{s_{2}} and the definition of A_{1}^{5}, we obtain A_{1}^{4} ≥ A_{2}^{4}.

From the inequalities F_{2}^{s_{2}} ≥ F_{2}^{s_{2}s_{1}} and F_{2}^{s_{1}s_{2}} ≥ F_{2}^{s_{1}}, we get A_{2}^{4} ≥ A_{1}^{2} and A_{1}^{3} ≥ A_{2}^{3}.

(b) ⇒ (a) Let 𝔽 := {(F_{1}^{σ}, F_{2}^{σ}, F_{3}^{σ}) : σ ∈< s_{1}, s_{2} >} be the set defined in (27), (28), (29) and (30). Clearly, 𝔽 is generated by (F_{1}, F_{2}, F_{3}). □

We show now that the transformations Θ_{k}^{∗}, k = 1, 2, may be used to obtain a decomposition of a sequence F_{1} ≥ F_{2} ≥ F_{3} according to the rules of the previous theorem.

Proposition 4.5 Given F_{1} ≥ F_{2} ≥ F_{3}, there exists a set 𝔽^{∗} generated by (F_{1}, F_{2}, F_{3}) such that, for all σ ∈ S_{3}, and j = 1, 2, Θ^{∗}(F_{j}^{σ}, F_{j+1}^{σ}) = (F_{j}^{s_{j}σ}, F_{j+1}^{s_{j}σ}) and F_{p}^{s_{j}σ} = F_{p}^{σ}, p ≠ j, j + 1. 𝔽^{∗} is uniquely determined by F_{1} ≥ F_{2} ≥ F_{3}.

We say that 𝔽^{∗} is the set ∗-generated by (F_{1}, F_{2}, F_{3}).

Proof: We have to show that conditions (I), (II), (III) and (IV) of theorem 4.2 are feasible with s_{∗}. Let (F_{1}^{s_{1}}, F_{2}^{s_{1}}, F_{3}^{s_{1}}), where F_{3}^{s_{1}} = F_{3} and s_{∗}(F_{1}, F_{2}) = (F_{1}^{s_{1}}, F_{2}^{s_{1}}), and (F_{1}^{s_{2}}, F_{2}^{s_{2}}, F_{3}^{s_{2}}), where F_{1}^{s_{2}} = F_{1} and s_{∗}(F_{1}, F_{2}) = (F_{1}^{s_{2}}, F_{2}^{s_{2}}).

Define now (F_{1}^{s_{2}s_{1}}, F_{2}^{s_{2}s_{1}}, F_{3}^{s_{2}s_{1}}), where F_{1}^{s_{2}s_{1}} = F_{1}^{s_{1}} and (F_{2}^{s_{2}s_{1}}, F_{3}^{s_{2}s_{1}}) = s_{∗}(F_{2}^{s_{1}}, F_{3}^{s_{1}}). Since F_{2}^{s_{1}} = F_{2} ∪ (F_{1} \ F_{1}^{s_{1}}) and F_{2}^{s_{2}} = min_{F_{3}}F_{2}, by theorem 2.8, we have

F_{2}^{s_{2}s_{1}} = min_{F_{3}}[F_{2} ∪ (F_{1} \ F_{1}^{s_{1}})] = min_{F_{3}}[F_{2}^{s_{2}} ∪ (F_{1} \ F_{1}^{s_{1}})] = X ∪ Y,  (34)

and F_{2}^{s_{2}} = X ∪ Z, where X ⊆ F_{2}^{s_{2}}, Y ⊆ F_{1} \ F_{1}^{s_{1}} and Z ≥ Y.

Recalling that F_{1}^{s_{2}} = F_{1} ≥ F_{2}^{s_{2}}, define (F_{1}^{s_{1}s_{2}}, F_{2}^{s_{1}s_{2}}, F_{3}^{s_{1}s_{2}}), such that F_{3}^{s_{1}s_{2}} = F_{3}^{s_{2}} and (F_{1}^{s_{1}s_{2}}, F_{2}^{s_{1}s_{2}}) = s_{∗}(F_{1}^{s_{2}}, F_{2}^{s_{2}}). By corollary 2.12, we have

F_{1}^{s_{1}} = min_{F_{2}^{s_{2}}}F_{1} ∪ min_{(F_{2}\F_{2}^{s_{2}})}(F_{1} \ F_{1}^{s_{1}s_{2}}),  (35)

Thus, since F_{1}^{s_{1}s_{2}} = min_{F_{2}^{s_{2}}}F_{1}, we must have F_{1}^{s_{1}s_{2}} ⊆ F_{1}^{s_{1}}. By corollary 2.6, F_{1}^{s_{1}s_{2}} = min_{F_{2}^{s_{2}}}F_{1}^{s_{1}}, and from (35), F_{1}^{s_{1}}\F_{1}^{s_{1}s_{2}} = min_{(F_{2}\F_{2}^{s_{2}})}(F_{1}\F_{1}^{s_{1}s_{2}}). Hence F_{1}^{s_{1}}\F_{1}^{s_{1}s_{2}} ≥ F_{2}\F_{2}^{s_{2}}.

Finally, define (F_{1}^{s_{1}s_{2}s_{1}}, F_{2}^{s_{1}s_{2}s_{1}}, F_{3}^{s_{1}s_{2}s_{1}}), where F_{3}^{s_{1}s_{2}s_{1}} = F_{3}^{s_{2}s_{1}} and (F_{1}^{s_{1}s_{2}s_{1}}, F_{2}^{s_{1}s_{2}s_{1}}) = s_{∗}(F_{1}^{s_{2}s_{1}}, F_{2}^{s_{2}s_{1}}). Notice that F_{1}^{s_{1}s_{2}} = min_{F_{2}^{s_{2}}}F_{1} = min_{X∪Z}F_{1}^{s_{1}}, and F_{1}^{s_{1}s_{2}s_{1}} = min_{F_{2}^{s_{2}s_{1}}}F_{1}^{s_{1}} = min_{X∪Y} F_{1}^{s_{1}}, where Z ⊆ F_{2}^{s_{2}}, Y ⊆ F_{1} \ F_{1}^{s_{1}} and Z ≥ Y.

Using theorem 2.10, we have F_{1}^{s_{1}s_{2}s_{1}} = min_{F_{2}^{s_{2}s_{1}}}F_{1}^{s_{1}} = F_{1}^{s_{1}s_{2}}.

Note that s_{∗}(F_{2}^{s_{1}s_{2}}, F_{3}^{s_{1}s_{2}}) = (F_{2}^{s_{2}s_{1}s_{2}}, F_{3}^{s_{2}s_{1}s_{2}}). In fact, min_{F_{3}^{s_{1}s_{2}}}F_{2}^{s_{1}s_{2}} = min_{F_{3}^{s_{2}}}F_{2}^{s_{1}s_{2}} and

min_{F_{3}^{s_{2}}}F_{2}^{s_{1}s_{2}} = min_{[F_{3}∪(F_{2}\F_{2}^{s_{2}})]}[F_{2}^{s_{2}} ∪ (F_{1}^{s_{1}} \ F_{1}^{s_{1}s_{2}}) ∪ (F_{1} \ F_{1}^{s_{1}})],  (36)

where min_{(F_{2}\F_{2}^{s_{2}})}[(F_{1}^{s_{1}} \ F_{1}^{s_{1}s_{2}}) ∪ (F_{1} \ F_{1}^{s_{1}})] = F_{1}^{s_{1}} \ F_{1}^{s_{1}s_{2}}.

Then, by theorem 2.14,

(36) = (F_{1}^{s_{1}} \ F_{1}^{s_{1}s_{2}}) ∪ min_{F_{3}}[F_{2}^{s_{2}} ∪ (F_{1} \ F_{1}^{s_{1}})] = F_{2}^{s_{1}s_{2}s_{1}}.

By theorem 4.2 we conclude the proof.

Therefore, the set 𝔽^{∗} := {(F_{1}^{σ}, F_{2}^{σ}, F_{3}^{σ}) : σ ∈< s_{1}, s_{2} >}, is generated by (F_{1}, F_{2}, F_{3}), and satisfy, for all σ ∈ S_{3} and j = 1, 2, Θ^{∗}(F_{j}^{σ}, F_{j+1}^{σ}) = (F_{j}^{s_{j}σ}, F_{j+1}^{s_{j}σ}) and F_{p}^{s_{j}σ} = F_{p}^{σ}, p ≠ j, j + 1. □

Corollary 4.6 Let 𝔽^{∗} be the set ∗-generated by (F_{1}, F_{2}, F_{3}). Then, for j = 1, 2,

Θ∗_{j}(F_{i}^{σ})_{i=1}^{3} = (F_{i}^{s_{j}σ})_{i=1}^{3}, σ ∈ < s_{1}, s_{2} >, satisfy:

(a) (Θ_{j}^{∗})^{2} = id, j = 1, 2.

(b) Θ_{1}^{∗}Θ_{2}^{∗}Θ_{1}^{∗} = Θ_{2}^{∗}Θ_{1}^{∗}Θ_{2}^{∗}.

That is, S_{3} acts on 𝔽^{∗}.

Proof: Use previous proposition. □

Let us consider the canonical words of S_{k+1}, k ≥ 1, (20), written as : θ_{r}ω, with θ_{r} := s_{r}θ_{r+1}, θ_{k+1} := id, and ω ∈ S_{k}, for r = 1, …, k.

Definition 4.3 Let k ≥ 1 and F_{1} ≥ … ≥ F_{k} ≥ F_{k+1}. We define, recursively, the set 𝔽^{∗} = {(F_{1}^{σ}, .., F_{k+1}^{σ}) : σ ∈< s_{1}, .., s_{k} >} ∗-generated by (F_{1}, .., F_{k}, F_{k+1}) as follows:

• If k = 1, 𝔽^{∗} := {(F_{1}, F_{2}), s_{∗}(F_{1}, F_{2})}.

• If k > 1, 𝔽^{∗} := {(F_{i}^{ω})_{i=1}^{k+1} : ω ∈ S_{k}} ∪ {(F_{i}^{θ_{r}ω})_{i=1}^{k+1} : 1 ≤ r ≤ k, ω ∈ S_{k}}, where

(i) {(F_{i}^{ω})_{i=1}^{k} : ω ∈ S_{k}} is ∗-generated by (F_{1}, …, F_{k}), and F_{k+1}^{ω} = F_{k+1}, for all ω ∈ S_{k};

(ii) for each r = 1, ..., k, and ω ∈ S_{k},

Θ^{∗}(F_{r}^{θ_{r+1}ω}, F_{r+1}^{θ_{r+1}ω}) = (F_{r}^{s_{r}θ_{r+1}ω}, F_{r+1}^{s_{r}θ_{r+1}ω}), and F_{p}^{s_{r}θ_{r+1}ω} = F_{p}^{θ_{r+1}ω}, p ≠ r, r + 1. (37)

Proposition 4.7 Let k ≥ 1 and F_{1} ≥ ... ≥ F_{k} ≥ F_{k+1}. The following statements hold

(I) There exists always 𝔽^{∗} ∗-generated by (F_{i})_{i=1}^{k+1}.

(II) If 𝔽^{∗} is ∗-generated by (F_{i})_{i=1}^{k+1}, then, for each r ∈ {1, …, k + 1}, and ω ∈ S_{k}, there exist G_{i}^{ω} ⊆ F_{i}^{ω}, with |G_{i}^{ω}| = |F_{k+1}|, for 1 ≤ i < r, such that

G_{1}^{ω} ≥ ... ≥ G_{r−1}^{ω} ≥ F_{r}^{θ_{r}ω} ≥ … ≥ F_{k}^{θ_{k}ω} ≥ F_{k+1},

where F_{i}^{θ_{i}ω} ⊆ F_{i}^{ω}, |F_{i}^{θ_{i}ω}| = |F_{k+1}|, for i = r, …, k, and F_{k+1} ⊆ F_{k+1}^{θ_{k}ω}.

Proof: By double induction on k and r. When k = 1, this is definition 4.1 with s_{∗}. When k = 2, this is definition 4.2 with s_{∗}, and this set was constructed in proposition 4.5.

We have to show that (37) is feasible, for k ≥ 3. By induction, there exists a set 𝔽̃ = {(F_{i}^{ω})_{i=1}^{k} : ω ∈ S_{k}} ∗-generated by (F_{i})_{i=1}^{k}, satisfying (II) above. Fix ω arbitrarily in S_{k}.

Then, there exist, for i = 1, ..., k, G_{i}^{ω} ⊆ F_{i}^{ω}, with G_{k}^{ω} = F_{k} and |G_{i}^{ω}| = |F_{k}|, such that

G_{1}^{ω} ≥ ... ≥ G_{k}^{ω} = F_{k} ≥ F_{k+1}.

Since G_{k}^{ω} = F_{k} ⊆ F_{k}^{ω}, it follows that F_{k}^{ω} ≥ F_{k+1}. So, putting F_{k+1}^{ω} = F_{k+1}, we may define Θ^{∗}(F_{k}^{ω}, F_{k+1}^{ω}) = (F_{k}^{s_{k}ω}, F_{k+1}^{s_{k}ω}) and F_{p}^{s_{k}ω} = F_{p}^{ω}, p ≠ k, k + 1.

We have F_{k}^{s_{k}ω} = min_{F_{k+1}}F_{k}^{ω} and F_{k+1}^{s_{k}ω} = F_{k+1} ∪ (F_{k}^{ω} \ F_{k}^{s_{k}ω}). Thus, G_{k}^{ω} ≥ F_{k}^{s_{k}ω} and G_{1}^{ω} ≥ ... ≥ G_{k−1}^{ω} ≥ F_{k}^{s_{k}ω} ≥ F_{k+1}, with F_{k+1} ⊆ F_{k+1}^{s_{k}ω}, F_{k}^{s_{k}ω} ⊆ F_{k}^{ω}, and |F_{k}^{s_{k}ω}| = |F_{k+1}|. Clearly we may consider |G_{i}^{ω}| = |F_{k+1}|, for i = 1, …, k − 1.

Suppose we have already defined (F_{i}^{s_{r+1}...s_{k}ω})_{i=1}^{k+1}, for 1 < r + 1 ≤ k, such that

G_{1}^{ω} ≥ ... ≥ G_{r}^{ω} ≥ F_{r+1}^{s_{r+1}...s_{k}ω} ≥ ... ≥ F_{k}^{s_{k}ω} ≥ F_{k+1},

with F_{i}^{s_{i}...s_{k}ω} ⊆ F_{i}^{s_{i+1}...s_{k}ω}, |F_{i}^{s_{i}...s_{k}ω}| = |F_{k+1}|, i = r + 1, ..., k, G_{i}^{ω} ⊆ F_{i}^{ω} = F_{i}^{s_{r+1}...s_{k}ω}, |G_{i}^{ω}| = |F_{k+1}|, i = 1, …, r.

So we must have F_{r}^{ω} = F_{r}^{s_{r+1}...s_{k}ω} ≥ F_{r+1}^{s_{r+1}...s_{k}ω}, and we may define

Θ^{∗}(F_{r}^{s_{r+1}...s_{k}ω}, F_{r+1}^{s_{r+1}...s_{k}ω}) = (F_{r}^{s_{r}s_{r+1}...s_{k}ω}, F_{r+1}^{s_{r}s_{r+1}...s_{k}ω})

and F_{p}^{s_{r}s_{r+1}...s_{k}ω} = F_{p}^{s_{r+1}...s_{k}ω}, p ≠ r, r + 1. As F_{r}^{s_{r}...s_{k}ω} = min_{F_{r+1}^{s_{r+1}...s_{k}ω}}F_{r}^{s_{r+1}...s_{k}ω} and F_{r+1}^{s_{r}...s_{k}ω} = F_{r+1}^{s_{r+1}...s_{k}ω} ∪ (F_{r}^{s_{r+1}...s_{k}ω} \ F_{r}^{s_{r}...s_{k}ω}), then, G_{r−1}^{ω} ≥ G_{r}^{ω} ≥ F_{r}^{s_{r}...s_{k}ω}, and

G_{1}^{ω} ≥ ... ≥ G_{r−1}^{ω} ≥ F_{r}^{s_{r}...s_{k}ω} ≥ ... ≥ F_{k}^{s_{k}ω} ≥ F_{k+1},

with F_{r}^{s_{r}...s_{k}ω} ⊆ F_{r}^{s_{r+1}...s_{k}ω} = F_{r}^{ω} and |F_{r−1}^{s_{r−1}...s_{k}ω}| = |F_{k+1}|. By induction, the result follows. □

Next we show that the operators Θ_{k}^{∗}, k = 1, …, t − 1, may be used to decompose a sequence F_{1} ≥ … ≥ F_{t}, t ≥ 3, such that we have an action of S_{t}.

Theorem 4.8 Let F_{1} ≥ ... ≥ F_{k} ≥ F_{k+1}, k ≥ 2, and 𝔽^{∗} = {(F_{i}^{σ})_{i=1}^{k+1} : σ ∈ S_{k+1}} ∗- generated by (F_{i})_{i=1}^{k}. For each t, t + 1, t + 2 ∈ {1, …, k + 1} and σ ∈ S_{k+1}, let G = {(F_{t}^{ασ}, F_{t+1}^{ασ}, F_{t+2}^{ασ}) : α ∈< s_{t}, s_{t+1} >} ⊆ 𝔽^{∗}. Then,

Θ^{∗}(F_{j}^{ασ}, F_{j+1}^{ασ}) = (F_{j}^{s_{j}ασ}, F_{j+1}^{s_{j}ασ}), for all α ∈< s_{t}, s_{t+1} >, j = t, t + 1,

and F_{p}^{s_{j}ασ} = F_{p}^{ασ}, for p ≠ j, j + 1.

Proof: By induction on k. When k = 2, we have {ασ : α ∈< s_{1}, s_{2} >} =< s_{1}, s_{2} >, for all σ ∈ S_{2}, and this is proposition 4.5.

Let k ≥ 3 and 𝔽̃ = {(F_{i}^{ω})_{i=1}^{k} : ω ∈ S_{k}} ∗-generated by (F_{1}, …, F_{k}). By induction hypothesis, for each ω ∈ S_{k}, and i, i + 1 ∈ {1, …, k − 1},

Θ^{∗}(F_{i}^{ω}, F_{i+1}^{ω}) = (F_{i}^{s_{i}ω}, F_{i+1}^{s_{i}ω}),  (38)

and F_{p}^{s_{i}ω} = F_{p}^{ω}, p ≠ i, i + 1.

Fix ω ∈ S_{k} arbitrarily. If t + 1 = k, since F_{k}^{ω} ≥ F_{k+1} and

Θ^{∗}(F_{k−1}^{ω}, F_{k}^{ω}) = (F_{k−1}^{s_{k−1}ω}, F_{k}^{s_{k−1}ω}),

it follows , by (38),

F_{k−1}^{ω} ≥ F_{k}^{ω} ≥ F_{k+1}, or  (39)
F_{k−1}^{s_{k−1}ω} ≥ F_{k}^{s_{k−1}ω} ≥ F_{k+1}.  (40)

Notice that {αs_{k−1} : α ∈< s_{k−1}, s_{k} >} =< s_{k−1}, s_{k} >. Then, G = {(F_{k−1}^{αω}, F_{k}^{αω}, F_{k+1}^{αω}) : θ ∈< s_{k−1}, s_{k} >} is ∗-generated by (39) or by (40). Again, by proposition 4.5 the claim is true.

Now, let σ = θ_{r}ω, where θ_{r} = s_{r}θ_{r+1}, 1 ≤ r ≤ k, with θ_{k+1} = id, and suppose the claim is true for all θ_{i}, with r < i ≤ k.

If t + 2 < r, by induction hypothesis, the claim is true.

If t > r, then s_{t}s_{r} … s_{k}ω = s_{r} … s_{k}ω′, with ω′ = s_{t−1}ω ∈ S_{k}. So it is enough to analyze the cases t = r, t + 1 = r and t + 2 = r.

Case t + 2 = r. We have F_{t}^{σ} = F_{t}^{ω}, F_{t+1}^{σ} = F_{t+1}^{ω}. Then by previous theorem, (II), F_{r−1}^{ω} ≥ F_{r}^{σ}, and, by induction, Θ^{∗}(F_{j}^{σ}, F_{j+1}^{σ}) = Θ^{∗}(F_{t}^{ω}, F_{t+1}^{ω}) = (F_{t}^{s_{t}ω}, F_{t+1}^{s_{t}ω}). So,

F_{r−2}^{s_{r−2}ω} ≥ F_{r−1}^{s_{r−2}ω} ≥ F_{r}^{σ} or  (41)
F_{r−2}^{ω} ≥ F_{r−1}^{ω} ≥ F_{r}^{σ}.  (42)

Then G = {(F_{r−2}^{ασ}, F_{r−1}^{ασ}, F_{r}^{ασ}) : α ∈< s_{r−2}, s_{r−1} >} is ∗-generated by (41) or by (42). Again proposition 4.5 shows the claim.

Case t + 1 = r. We have by previous theorem, (II), F_{r−1}^{σ} = F_{r−1}^{ω} ≥ F_{r}^{σ} ≥_{op} F_{r+1}^{σ} and Θ^{∗}(F_{r}^{σ}, F_{r+1}^{σ}) = (F_{r}^{s_{r}σ}, F_{r+1}^{s_{r}σ}). So, F_{r}^{s_{r}σ} = F_{r}^{ω} and F_{r+1}^{s_{r}σ} = F_{r+1}^{s_{r+1}...s_{k}σ}. By induction, Θ^{∗}(F_{r−1}^{ω}, F_{r}^{ω}) = (F_{r−1}^{s_{r−1}ω}, F_{r}^{s_{r−1}ω}). Hence,

F_{r−1}^{ω} ≥ F_{r}^{ω} ≥ F_{r+1}^{s_{r+1}...s_{k}ω}, or  (43)
F_{r−1}^{s_{r−1}ω} ≥ F_{r}^{s_{r−1}ω} ≥ F_{r+1}^{s_{r+1}...s_{k}ω}.  (44)

Then G is ∗-generated by (43) or by (44). Again apply proposition 4.5

Case t = r. By previous theorem, F_{r}^{σ} ≥_{op} F_{r+1}^{σ} and

Θ^{∗}(F_{r}^{σ}, F_{r+1}^{σ}) = (F_{r}^{s_{r}σ}, F_{r+1}^{s_{r}σ}).

Then, using previous theorem, (II), F_{r}^{ω} ≥ F_{r+1}^{s_{r+1}...s_{k}ω} ≥_{op} F_{r+2}^{σ} = F_{r+2}^{s_{r+1}...s_{k}ω}, and

Θ^{∗}(F_{r+1}^{s_{r+1}...s_{k}ω}, F_{r+2}^{s_{r+1}...s_{k}ω}) = (F_{r+1}^{s_{r+2}...s_{k}ω}, F_{r+2}^{s_{r+2}...s_{k}ω}) = (F_{r+1}^{ω}, F_{r+2}^{s_{r+2}...s_{k}ω}).

By induction Θ^{∗}(F_{r}^{ω}, F_{r+1}^{ω}) = (F_{r}^{s_{r}ω}, F_{r+1}^{s_{r}ω}). Hence,

F_{r}^{ω} ≥ F_{r+1}^{ω} ≥ F_{r+2}^{s_{r+2}...s_{k}ω} or  (45)
F_{r}^{s_{r}ω} ≥ F_{r+1}^{s_{r}ω} ≥ F_{r+2}^{s_{r+2}...s_{k}ω}.  (46)

Therefore, G is ∗-generated by (45) or by (46). Again proposition 4.5 shows the claim. □

Corollary 4.9 Let k ≥ 2, F_{1} ≥ ... ≥ F_{k}, and 𝔽^{∗} = {(F_{i}^{σ})_{i=1}^{k} : σ ∈ S_{k}} ∗-generated by (F_{i})_{i=1}^{k}. Then, for j = 1, ..., k − 1, Θ_{j}^{∗}((F_{i}^{σ})_{i=1}^{k}) = (F_{i}^{s_{j}σ})_{i=1}^{k}, σ ∈ S_{k}, satisfy:

(a) (Θ_{j}^{∗})^{2} = id, 1 ≤ j ≤ k − 1.

(b) Θ_{j}^{∗}Θ_{r}^{∗} = Θ_{r}^{∗}Θ_{j}^{∗}, |j − r| > 1.

(c) Θ_{j}^{∗}Θ_{j+1}^{∗}Θ_{j}^{∗} = Θ_{j+1}^{∗}Θ_{j}^{∗}Θ_{j+1}^{∗}, 1 ≤ j ≤ k − 2.

That is, S_{k} acts on 𝔽^{∗}.

Proof: Use previous theorem. □

In view of the results above, we may give the following definitions.

Definition 4.4 Given J_{1}, ..., J_{t} ⊆ {1, ..., n} and σ ∈ S_{t}, we say that (J_{1}, ..., J_{t}) is a σ-LR sequence (or σ-Yamanouchi sequence) of sets if there exists F_{1} ≥ ... ≥ F_{t} such that (J_{1}, ..., J_{t}) = (F_{1}^{σ}, ..., F_{t}^{σ}) ∈ 𝔽^{∗}, with 𝔽^{∗} ∗-generated by (F_{1}, ..., F_{t}).

Proposition 4.10 Given J_{1}, ..., J_{t} ⊆ {1, ..., n}, the sequence (J_{1}, ..., J_{t}) is a σ-LR sequence of sets if and only if Θ_{i_{1}}^{∗}Θ_{i_{2}}^{∗}...Θ_{i_{r}}^{∗}(J_{1}, ..., J_{t}) is a LR sequence of sets, where s_{i_{1}}s_{i_{2}}...s_{i_{r}} is a word of σ in the alphabet {s_{1}, ..., s_{t−1}}.

Proof: Use previous corollary. □

Now we shall characterize σ-LR sequences of lenght 3, with σ ∈ S_{3}, and we show that the elements generated in a set 𝔽, by an LR sequence, may also be generated by the transformations Θ_{k}^{∗}, k = 1, 2, by some other LR sequence.

Theorem 4.11 Let J_{1}, J_{2}, J_{3} ⊆ {1, ..., n}. Then,

(a) (J_{1}, J_{2}, J_{3}) is a s_{1}-LR sequence iff ∃A ⊆ J_{2} with |A| = |J_{1}| such that J_{1} ≥ A ≥ J_{3}.

(b) (J_{1}, J_{2}, J_{3}) is a s_{2}-LR sequence iff

(i) ∃A_{1}^{1} ⊆ J_{1}, A_{3}^{1} ⊆ J_{3} with |A_{1}^{1}| = |A_{3}^{1}| = |J_{2}| such that A_{1}^{1} ≥ J_{2} ≥ A_{3}^{1},

(ii) ∃A_{1}^{2} ⊆ J_{1} \ A_{1}^{1} with |A_{1}^{2}| = |J_{3} \ A_{3}^{1}| such that A_{1}^{2} ≥ J_{3} \ A_{3}^{1}.

(c) (J_{1}, J_{2}, J_{3}) is a s_{1}s_{2}-LR sequence iff

(i) ∃A_{2}^{1} ⊆ J_{2}, A_{3}^{1} ⊆ J_{3} with |J_{1}| = |A_{2}^{1}| = |A_{3}^{1}| such that J_{1} ≥ A_{2}^{1} ≥ A_{3}^{1},

(ii) ∃A_{2}^{2} ⊆ J_{2} \ A_{2}^{1} with |A_{2}^{2}| = |J_{3} \ A_{3}^{1}| such that A_{2}^{2} ≥ J_{3} \ A_{3}^{1}.

(d) (J_{1}, J_{2}, J_{3}) is a s_{2}s_{1}-LR sequence iff

(i) ∃A_{1}^{1} ⊆ J_{1}, A_{3}^{1} ⊆ J_{3} with |A_{1}^{1}| = |J_{2}| = |A_{3}^{1}| such that A_{1}^{1} ≥ J_{2} ≥ A_{3}^{1},

(ii) ∃A_{3}^{2} ⊆ J_{3} \ A_{3}^{1} with |A_{3}^{2}| = |J_{1} \ A_{1}^{1}| such that J_{1} \ A_{1}^{1} ≥ A_{3}^{2}.

(e) (J_{1}, J_{2}, J_{3}) is a s_{1}s_{2}s_{1}-LR sequence iff

(i) ∃A_{2}^{1} ⊆ J_{2}, A_{3}^{1} ⊆ J_{3} with |J_{1}| = |A_{2}^{1}| = |A_{3}^{1}| such that J_{1} ≥ A_{2}^{1} ≥ A_{3}^{1},

(ii) ∃A_{3}^{2} ⊆ J_{3} \ A_{3}^{1} with |A_{3}^{2}| = |J_{2} \ A_{2}^{1}| such that J_{2} \ A_{2}^{1} ≥ A_{3}^{2}.

Proof: The only if part. If (J_{1}, J_{2}, J_{3}) is a σ-LR sequence, then there exists F_{1} ≥ F_{2} ≥ F_{3} such that (J_{1}, J_{2}, J_{3}) = (F_{1}^{σ}, F_{2}^{σ}, F_{3}^{σ}) ∈ 𝔽^{∗}, the set ∗-generated by (F_{1}, F_{2}, F_{3}). Using theorem 4.4, the conclusion follows easily.

The if part. (a) and (b) are obvious.

(c) It is enough to prove that Θ_{1}^{∗}(J_{1}, J_{2}, J_{3}) is a s_{2}-LR sequence.

Define Ã:= max{X ⊆ J_{2} : |X| = |J_{1}|, J_{1} ≥ X} and let F_{2} := Ã and F_{1} := J_{1}∪(J_{2}\F_{2}). Clearly, Θ_{1}^{∗}(J_{1}, J_{2}, J_{3}) = (F_{1}, F_{2}, F_{3}), with F_{3} = J_{3}.

Since J_{1} ≥ Ã ≥ A_{2}^{1}, we may write Ã = X_{1}∪Y_{1}∪Z, A_{2}^{1} = X_{1}∪X_{2}∪X_{3}, and A_{2}^{2} = Y_{1}∪Y_{2}, union of pairwise disjoint subsets, with Z ⊆ J_{2} \ (A_{2}^{1} ∪ A_{2}^{2}), |Y_{1}| = |X_{2}|, and |Z| = |X_{3}| such that Y_{1} ≥ X_{2}, Z ≥ X_{3}. Let A_{3}^{2} := J_{3} \ A_{3}^{1}. Since A_{2}^{1} ≥ A_{3}^{1} and A_{2}^{2} ≥ A_{3}^{2}, we may also write A_{3}^{1} = X′_{1} ∪ X′_{2} ∪ X′_{3} and A_{3}^{2} = Y′_{1} ∪ Y′_{2}, union of pairwise disjoint subsets, where |X′_{i}| = |X_{i}|, X_{i} ≥ X′_{i} i = 1, 2, 3, and |Y′_{i}| = |Y_{i}|, Y_{i} ≥ Y′_{i} i = 1, 2.

We have: (i) J_{1} ⊆ F_{1} and Ã_{3} := X′_{1} ∪ X′_{3} ∪ Y′_{1} ⊂ F_{3} with |J_{1}| = |F_{2}| = |Ã_{3}| such that J_{1} ≥ F_{2} ≥ Ã_{3}; and (ii) X_{2} ∪ Y_{2} ⊆ F_{1} \ J_{1} with |X_{2} ∪ Y_{2}| = |F_{3} \ Ã_{3}| such that X_{2} ∪ Y_{2} ≥ F_{3} \ Ã_{3}. Hence, by (b), Θ_{1}^{∗}(J_{1}, J_{2}, J_{3}) is a s_{2}-LR sequence.

(d) It is enough to prove that Θ_{2}^{∗}(J_{1}, J_{2}, J_{3}) is a s_{1}-LR sequence. Let F_{1} := J_{1}, F_{3} := max{X ⊆ J_{3} : |X| = |J_{2}|, J_{2} ≥ X} and F_{2} := J_{2} ∪ (J_{3} \ F_{3}). Clearly, Θ_{2}^{∗}(J_{1}, J_{2}, J_{3}) = (F_{1}, F_{2}, F_{3}). Since A_{1}^{1} ≥ J_{2} ≥ A_{3}^{1} and J_{1} \ A_{1}^{1} ≥ A_{3}^{2}, we may write F_{3} = X′_{1} ∪ Y′_{1} ∪ Z, J_{2} = X_{1} ∪ X_{2} ∪ X_{3}, A_{3}^{1} = X′_{1} ∪ X′_{2} ∪ X′_{3}, J_{1} \ A_{1}^{1} = Y_{1} ∪ Y_{2}, and A_{3}^{2} = Y′_{1} ∪ Y′_{2}, union of pairwise disjoint subsets, with |X_{i}| = |X′_{i}|, X_{i} ≥ X′_{i}, i = 1, 2, 3, |Y_{i}| = |Y′_{i}|, Y_{i} ≥ Y′_{i}, i = 1, 2, and |Z| = |X_{3}|, such that X_{3} ≥ Z ≥ X′_{3} and X_{2} ≥ Y′_{1} ≥ X′_{2}.

Therefore, F_{1} = A_{1}^{1}∪Y_{1}∪Y_{2} ≥ J_{2}∪X′_{2}∪Y′_{2}, with J_{2}∪X′_{2}∪Y′_{2} ⊆ F_{2} and |J_{2}∪X′_{2}∪Y′_{2}| = |F_{1}|. Hence, by (a), Θ_{2}^{∗}(J_{1}, J_{2}, J_{3}) is a s_{1}-LR sequence.

(e) It is enough to prove that Θ_{1}^{∗}(J_{1}, J_{2}, J_{3}) is a s_{2}s_{1}-LR sequence. If F_{3} := J_{3}, F_{2} := max{X ⊆ J_{2} : |X| = |J_{1}|, J_{1} ≥ X} and F_{1} := J_{1} ∪ (J_{2} \ F_{2}), then clearly, Θ_{1}^{∗}(J_{1}, J_{2}, J_{3}) = (F_{1}, F_{2}, F_{3}). We may write J_{1} = X_{1} ∪ X_{2}, A_{2}^{1} = Y_{1} ∪ Y_{2}, J_{2} \ A_{2}^{1} = Y_{3} ∪ Y_{4}, A_{3}^{1} = Z_{1} ∪ Z_{2}, A_{3}^{2} = Z_{3} ∪ Z_{4}, and F_{2} = Y_{1} ∪ Y_{3}, union of pairwise disjoint subsets, with |X_{i}| = |Y_{i}| = |Z_{i}|, X_{i} ≥ Y_{i} ≥ Z_{i}, i = 1, 2, and |Y_{i}| = |Z_{i}|, Y_{i} ≥ Z_{i}, i = 3, 4, such that |Y_{3}| = |Y_{2}| and X_{2} ≥ Y_{3} ≥ Y_{2}.

Therefore, (i) X_{1}∪X_{2} ⊆ F_{1} and Z_{2}∪Z_{3} ⊆ F_{3} with |X_{1}∪X_{3}| = |F_{2}| = |Z_{1}∪Z_{3}|, such that X_{1} ∪X_{2} ≥ F_{2} ≥ Z_{1} ∪Z_{3}; and (ii) Z_{2} ∪Z_{4} ⊆ F_{3} \(Z_{1} ∪Z_{3}), with |Z_{2} ∪Z_{4}| = |F_{1} \(X_{1} ∪X_{2})|, such that F_{1} \ (X_{1} ∪ X_{2}) ≥ Z_{2} ∪ Z_{3}. Hence, by (d), Θ_{1}^{∗}(J_{1}, J_{2}, J_{3}) is a s_{2}s_{1}-LR sequence. □

Definition 4.5 Given σ ∈ S_{t}, we say that T is a σ-LR tableau of type (a, σm, c), with m a partition, if its indexing sets are a σ-LR sequence.

Let a, m, c be partitions of length ≤ n with a, m ⊆ c. Given σ ∈ S_{t}, we denote by LR_{σ}(a, σm, c) the set constituted by the indexing sets of all σ-LR tableau of type (a, σm, c). If {(A_{i})_{i=1}^{t}, (B_{i})_{i=1}^{t}, ..., (F_{i})_{i=1}^{t}} are the indexing sets of all LR tableaux of type (a, m, c), let 𝔽_{A}^{∗}, 𝔽_{B}^{∗}, ..., 𝔽_{F}^{∗} be, respectively, the sets ∗-generated by those indexing sets. Then,

LR_{σ}(a, σm, c) = {(A_{i}^{σ})_{i=1}^{t}, (B_{i}^{σ})_{i=1}^{t}, ..., (F_{i}^{σ})_{i=1}^{t}}.

Hence,

⋃_{σ∈S_{t}} LR_{σ}(a, σm, c) = 𝔽_{A}^{∗} ∪ 𝔽_{B}^{∗} ∪ ... ∪ 𝔽_{F}^{∗} .

If J_{1}, ..., J_{t} are the indexing sets of a σ-LR tableau of type (a, σm, c), then Θ_{i}^{∗}(J_{1}, ..., J_{t}) are the indexing sets of a s_{i}σ-LR tableau of type (a, s_{i}σm, c), for all i = 1, …, t. Hence, given a tableau T of type (a, σm, c) with indexing sets J_{1}, ..., J_{t}, T is a σ-LR tableau if and only if Θ_{i_{1}}^{∗}Θ_{i_{2}}^{∗}...Θ_{i_{r}}^{∗}(J_{1}, ..., J_{t}) are the indexing sets of an LR tableau of type (a, m, c), where s_{i_{1}}s_{i_{2}}...s_{i_{r}} is a word of σ in the alphabet {s_{1}, ..., s_{t−1}}.

Given ε, σ ∈ S_{t} and s_{i_{1}}s_{i_{2}}...s_{i_{r}} a word of εσ^{−1} in the alphabet {s_{1}, ..., s_{t−1}}, Θ_{i_{1}}^{∗}Θ_{i_{2}}^{∗}...Θ_{i_{r}}^{∗} defines a bijection between LR_{σ}(a, σm, c) and LR_{ε}(a, εm, c).

Theorem 4.12 The involutions Θ_{i}^{∗}, i = 1, ..., t − 1, define an action of the symmetric group S_{t} on ∪_{σ∈S_{t}}LR_{σ}(a, σm, c).

Acknowledgement: We are very grateful to Ana Paula Escada and Alexander Kovačec for useful comments. In particular, we are much obliged to Alexander Kovačec for the concept of ”witness” which led us to a better understanding of the operations under consideration in this paper.

References

[1] O. Azenhas, E. Marques de Sá, Matrix Realizations of Littlewood-Richardson Sequences, Linear and Multilinear Algebra, 27 (1990), 229-242.

[2] O. Azenhas, Realizações Matriciais de Quadros de Young e Suas Formas Canónicas (in Portuguese), Phd Thesis, Universidade de Coimbra, Coimbra, 1991.

[3] O. Azenhas, A Regra de Littlewood-Richardson: Generalizações e Realizações Matriciais, Proceedings of the Third Meeting of the Portuguese Algebraists (in Portuguese), Coimbra, pp. 9-32, 1993.

[4] O. Azenhas, Opposite Litlewood-Richardson Sequences and their Matrix Realizations, Linear Algebra Appl., 225 (1995), 91-116.

[5] O. Azenhas, The admissible interval for the invariant factors of a product of matrices, Linear and Multilinear Algebra, 46:51-99, 1999.

[6] W. Fulton, Young Tableaux, London Mathematical Society Student Texts 35, Cambridge, University Press, 1997.

[7] L. Gerstein, A Local Approach to Matrix Equivalence, Linear and Multilinear Algebra, 16 (1977), 221-232.

[8] G. Grätzer, General Lattice Theory, Birkhäuser Verlag, Basel, 1998.

[9] T. Klein, The Multiplication of Schur Funtions and Extensions of p-Modules, Journal of London Mathematical Society, 43 (1968), 280-282.

[10] A. Lascoux, M.P. Schutzenberger, Le monoïde plaxique, Noncommutative structures in algebra and geometric combinatorics, (Naples, 1978), Quad. ”Ricerca Sci.”, vol. 109, CNR, Rome, 1981.

[11] A. Lascoux, M.P. Schutzenberger, Keys and standard bases, Invariant theory and Tableaux, Minneapolis, MN, 1988.

[12] M. Lothaire, Algebraic combinatorics on words, Cambridge University Press, Cambridge, 2002.

[13] R. Mamede, Permutações de sequências de Littlewood-Richardson e suas Realizações Matriciais (in Portuguese), Master Thesis, Universidade de Coimbra, Coimbra, 2000.

[14] M. Newman, Integral Matrices, Academic Press, New York, 1972.