Words

In this and following sections, words are considered to be elements of some ordered monoid, that is a free monoid whose generators have an explicit ordering. The most important example is the monoid of words generated by the positive integers, though Magma also allows the creation of finitely generated ordered monoids. The words in this section are developed in connection with the theory of Young tableaux (see section Tableaux), which are defined over some ordered set of labels (generators of an ordered monoid in Magma).

The importance of the ordering on the generators is in the definition of an equivalence known as Knuth equivalence. Knuth equivalence is defined by the two relations      yzxyxz    x < yz
     xzyzxy    xy < z

The plactic monoid is the quotient of an ordered monoid with respect to Knuth equivalence. This plactic monoid is in fact isomorphic to the monoid of tableaux over the same generators. Elements of the plactic monoid are represented by a canonical representative from the Knuth equivalence class of the ordered monoid. This canonical representative is in fact the row word of the corresponding tableau (see section Tableaux).

Contents

Ordered Monoids

An ordered monoid is a free monoid with an ordered basis. Magma has two different types of ordered monoids. The first is the monoid of words over the positive integers, which retain their natural ordering. The second are finitely generated monoids, whose generators may be assigned names.

OrderedMonoid(n) : RngIntElt -> MonOrd
Given a positive integer n, return the monoid with n ordered generators.
OrderedIntegerMonoid() : -> MonOrd
Return the ordered monoid of words over the positive integers.
Id(O) : MonOrd -> MonOrdElt
O ! 1 : MonOrd, RngInt -> MonOrdElt
Given an ordered monoid O, return its identity element. i.e., the null word.
O . i : MonOrd, RngIntElt -> MonOrdElt
Given an ordered monoid O and a positive integer i, return the ith generator of O.
O ! [w1, ..., wn] : MonOrd, [MonOrdElt] -> MonOrdElt
Given an ordered monoid O, and a sequence of elements from O, return the word w1 ... wn.
O ! [i1, ..., in] : MonOrd, [RngIntElt] -> MonOrdElt
Given the ordered monoid O over the positive integers, and a sequence of integers, return the word i1 ... in.
w1 eq w2 : MonOrdElt, MonOrdElt -> BoolElt
Given two words w1 and w2 from the same ordered monoid, return true if they are equal.
w1 * w2 : MonOrdElt, MonOrdElt -> MonOrdElt
Given two words w1 and w2 from the same ordered monoid, return their product under word concatenation.
IsKnuthEquivalent(w1, w2) : MonOrdElt, MonOrdElt -> BoolElt
Two words w1 and w2 from the same monoid are Knuth equivalent if they can be transformed into one another using elementary Knuth transformations, (defined in the introduction to this section).
w[i] : MonOrdElt, RngIntElt -> RngElt
Given a word w from an ordered monoid, expressed as a product of generators, return the ith generator in the product.
ElementToSequence(w) : MonOrdElt -> SeqEnum
Eltseq(w) : MonOrdElt -> SeqEnum
Given a word w from the ordered monoid of positive integers, return w as a sequence of integers.
Length(w) : MonOrdElt -> RngIntElt
# w : MonOrdElt -> RngIntElt
Given a word w from an ordered monoid, return its length.
Content(w) : MonOrdElt -> SeqEnum[RngIntElt]
Given a word w from an ordered monoid, return a sequence of non-negative integers denoting its content. The content of a word is a sequence where the ith position denotes the number of occurrences of the ith generator in the word.
IsReverseLatticeWord(w) : MonOrdElt -> BoolElt
A word w from an ordered monoid is said to be a reverse lattice word (or Yamanouchi word) if for any n>0, the last n letters of w have a content which is a partition.
MaximalIncreasingSequence(w) : MonOrdElt -> RngIntElt
Given a word w from an ordered monoid, return a weakly increasing subsubsequence of w of maximal length. This sequence is not necessarily unique.
MaximalIncreasingSequences(w, k) : SeqEnum,RngIntElt -> RngIntElt
Given a word w from an ordered monoid and some positive integer k, return a sequence of k distinct increasing subsequences of the word w, such that the maximal number of entries from w is used. Empty sequences are returned if all entries from w are used. These sequences are not necessarily unique.

Example Tableau_OrderedMonoid-Creation (H154E3)

We create the ordered monoid over the positive integers and look at a few elements.
> O := OrderedIntegerMonoid();
> O;
The monoid of words over the positive integers
>
> w1 := O ! [3,5,2,8];
> w1;
3 5 2 8
> w2 := O ! [6,7,2,4];
> w2;
6 7 2 4
>
> w2[3];
2
> Eltseq(w1);
[ 3, 5, 2, 8 ]
>
> w1*w2;
3 5 2 8 6 7 2 4

Example Tableau_orderedmon--fingen (H154E4)

We create a finitely generated ordered monoid and create an element.
> O<a,b,c,d> := OrderedMonoid(4);
> O;
The monoid of words over 4 generators: a b c d
>
> w := a*b*a*d*c;
> w;
a b a d c

Example Tableau_OrderedMonoid-longest (H154E5)

We take a word of integers and look at weakly increasing subsequences of maximal length.
> O := OrderedIntegerMonoid();
> w := O ! [1,3,4,2,3,4,1,2,2,3,3,2];
>
> MaximalIncreasingSequence(w);
1 1 2 2 2 3
> MaximalIncreasingSequences(w,2);
[ 1 1 2 2 2 3 , 2 3 3  ]
> MaximalIncreasingSequences(w,3);
[ 1 1 2 2 2 3 , 2 3 3 , 3 4 4  ]
> MaximalIncreasingSequences(w,4);
[ 1 1 2 2 2 3 , 2 3 3 , 3 4 4 , Id(O) ]

Plactic Monoids

The plactic monoid of an ordered monoid is the quotient defined by Knuth equivalence. Elements of a plactic monoid are equivalence classes of words from the original ordered monoid, and are represented by a canonical representative.

PlacticMonoid(O) : MonOrd -> MonOrd
Given an ordered monoid O, return the plactic monoid obtained by factoring O by Knuth equivalence.
PlacticIntegerMonoid() : -> MonOrd
Return the plactic monoid obtained by factoring the ordered monoid over the positive integers by Knuth equivalence.
OrderedMonoid(P) : MonPlc -> MonOrd
Given a plactic monoid P, return the ordered monoid on which P is based.
Id(P) : MonPlc -> MonPlcElt
P ! 1 : MonPlc, RngIntElt -> MonPlcElt
Given a plactic monoid P, return its identity element which is the null word.
P . i : MonPlc, RngIntElt -> MonPlcElt
Given a plactic monoid P and a positive integer i, return the ith generator of P.
P ! [u1, ..., un] : MonPlc, [MonPlcElt] -> MonPlcElt
Given a plactic monoid P, and a sequence of elements from P, return the product u1 ... un.
P ! [i1, ..., in] : MonPlc, [RngIntElt] -> MonPlcElt
Given the plactic monoid P over the positive integers, and a sequence of integers, return the element of P corresponding to the Knuth equivalence class of i1 ... in.
P ! w : MonPlc, MonOrdElt -> MonPlcElt
Given a plactic monoid P, and a word w from the ordered monoid that its based on, return the element of P corresponding to the Knuth equivalence class of w.
P ! [w1, ..., wn] : MonPlc, [MonOrdElt] -> MonPlcElt
Given a plactic monoid P, and a sequence of elements from the ordered monoid that its based on, return the element of P corresponding to the Knuth equivalence class of w1 ... wn.
P ! t : MonPlc, Tbl -> MonPlcElt
Given a plactic monoid P and a tableau t which are both associated with the same ordered monoid, return the element of P which is uniquely associated to t.
u1 eq u2 : MonPlcElt, MonPlcElt -> BoolElt
Given two elements u1 and u2 from the same plactic monoid, return true if they are equal.
u1 * u2 : MonPlcElt, MonPlcElt -> MonPlcElt
Given two elements u1 and u2 belonging to the same plactic monoid, return their product which is inherited from word concatenation in the ordered monoid.
Length(u) : MonPlcElt -> RngIntElt
# u : MonPlcElt -> RngIntElt
Given a element u from a plactic monoid, return its length. The length of a word is invariant under Knuth equivalence and so is well defined for elements of the plactic monoid.
Content(u) : MonPlcElt -> SeqEnum[RngIntElt]
Given a word u from a plactic monoid, return a sequence of non-negative integers denoting its content. The content of a word is a sequence where the ith position denotes the number of occurrences of the ith generator in the word. The content of a word is invariant under Knuth equivalence and so is well defined for elements of the plactic monoid.

Example Tableau_OrderedMonoid-basic (H154E6)

We create both the ordered monoid and plactic monoid over the integers and look at several elements.
> O := OrderedIntegerMonoid();
> P := PlacticIntegerMonoid();
>
> w1 := O ! [2,7,4,8,1,5,9];
> w1;
2 7 4 8 1 5 9
> P!w1;
7 2 8 1 4 5 9
First we look at a word that is Knuth equivalent to w1,
> w2 := O ! [7,2,1,8,4,5,9];
> w2;
7 2 1 8 4 5 9
>
> IsKnuthEquivalent(w1,w2);
true
> (P!w1) eq (P!w2);
true
and then one that is not Knuth equivalent.
> w3 := O ! [7,1,5,8,2,9,4];
> w3;
>
7 1 5 8 2 9 4
> IsKnuthEquivalent(w1,w3);
false
> (P!w1) eq (P!w3);
false
> P!w3;
7 5 8 1 2 4 9

Example Tableau_OrderedMonoid-fingen (H154E7)

We create a finitely generated ordered monoid, its associated plactic monoid, and look at some properties which are invariant under Knuth equivalence.
> O<a,b,c,d,e> := OrderedMonoid(5);
> P := PlacticMonoid(O);
> P;
The plactic monoid of words over 5 generators: a b c d e
>
> w := b*c*e*e*a*d*a*d;
> w;
b c e e a d a d
> Length(w);
8
> Content(w);
[ 2, 1, 1, 2, 2 ]
>
> u := P!w;
> u;
a a b c d d e e
> Length(u);
8
> Content(u);
[ 2, 1, 1, 2, 2 ]
V2.28, 13 July 2023