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

\[\begin{split}\begin{aligned}yzx &\sim yxz \qquad x < y \le z \\ xzy &\sim zxy \qquad x \le y < z\end{aligned}\end{split}\]

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).

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 \(i\)th generator of \(O\).

O ! [w₁, ..., wₙ]: MonOrd, [MonOrdElt] -> MonOrdElt#: Given an ordered monoid \(O\), and a sequence of elements from \(O\), return the word \(w_1\cdots w_n\).

O ! [i₁, ..., iₙ]: MonOrd, [RngIntElt] -> MonOrdElt#: Given the ordered monoid \(O\) over the positive integers, and a sequence of integers, return the word \(i_1\cdots i_n\).

w1 eq w2: MonOrdElt, MonOrdElt -> BoolElt#: Given two words \(w_1\) and \(w_2\) from the same ordered monoid, return true if they are equal.

w1 * w2: MonOrdElt, MonOrdElt -> MonOrdElt#: Given two words \(w_1\) and \(w_2\) from the same ordered monoid, return their product under word concatenation.

IsKnuthEquivalent(w1, w2): MonOrdElt, MonOrdElt -> BoolElt#: Two words \(w_1\) and \(w_2\) 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 \(i\)th 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 \(i\)th position denotes the number of occurrences of the \(i\)th 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: OrderedMonoid Creation (ex-9cc372)#

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

Run in calculator

Example: Orderedmon Fingen (ex-18b21e)#

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

Run in calculator

Example: OrderedMonoid Longest (ex-31d600)#

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) ]

Run in calculator

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 \(i\)th generator of \(P\).

P ! [u₁, ..., uₙ]: MonPlc, [MonPlcElt] -> MonPlcElt#: Given a plactic monoid \(P\), and a sequence of elements from \(P\), return the product \(u_1\cdots u_n\).

P ! [i₁, ..., iₙ]: 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 \(i_1\cdots i_n\).

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 ! [w₁, ..., wₙ]: 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 \(w_1\cdots w_n\).

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 \(u_1\) and \(u_2\) from the same plactic monoid, return true if they are equal.

u1 * u2: MonPlcElt, MonPlcElt -> MonPlcElt#: Given two elements \(u_1\) and \(u_2\) 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 \(i\)th position denotes the number of occurrences of the \(i\)th 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: OrderedMonoid Basic (ex-0e6aa3)#

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

Run in calculator

First we look at a word that is Knuth equivalent to \(w_1\),

> 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

Run in calculator

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

Run in calculator

Example: OrderedMonoid Fingen (ex-b4e54f)#

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 ]

Run in calculator