Plactic monoid

AUTHORS:

  • Daniel Chen, Lisa Johnston, Junbok Lee, Evuilynn Nguyen, Heather Ross, Chenchen Zhao (2026): initial version

This file implements the plactic monoid on the alphabet \(\{1, 2, \ldots, n\}\). Elements are represented by words, with equality determined by their RSK insertion tableaux. Multiplication is given by concatenation of words, and the identity element is the empty word.

This file consists of the following major classes:

Parent classes:

Element classes:

The main functionality includes constructing plactic monoid elements, computing their RSK insertion tableaux, converting elements to their row reading word representatives, computing shapes and equivalence classes, testing canonical representatives, and listing all elements of a fixed word length.

class sage.monoids.plactic_monoid.PlacticMonoid(n)[source]

Bases: WordMonoid

The plactic monoid on the alphabet \(\{1, 2, \ldots, n\}\).

INPUT:

  • n – a positive integer; the size of the alphabet

Elements are represented by words in \(\{1, 2, \ldots, n\}\). Equality is determined by comparing RSK insertion tableaux. Multiplication is induced by concatenation of words, and the identity is the empty word.

EXAMPLES:

sage: M = PlacticMonoid(4)
sage: M
Plactic monoid of rank 4
sage: M.rank()
4
sage: M([2, 1, 3]).to_tableau()
[[1, 3], [2]]
sage: M([2, 1, 3]) == M([2, 3, 1])
True
sage: M([2, 1]) * M([3, 2])
2132
sage: (M([2, 1]) * M([3, 2])).to_word()
2312

>>> from sage.all import *
>>> M = PlacticMonoid(Integer(4))
>>> M
Plactic monoid of rank 4
>>> M.rank()
4
>>> M([Integer(2), Integer(1), Integer(3)]).to_tableau()
[[1, 3], [2]]
>>> M([Integer(2), Integer(1), Integer(3)]) == M([Integer(2), Integer(3), Integer(1)])
True
>>> M([Integer(2), Integer(1)]) * M([Integer(3), Integer(2)])
2132
>>> (M([Integer(2), Integer(1)]) * M([Integer(3), Integer(2)])).to_word()
2312
class Element(parent, value)[source]

Bases: WordMonoidElement

An element of a plactic monoid, represented by a word.

EXAMPLES:

sage: M = PlacticMonoid(4)
sage: M([2, 1, 3])
213

>>> from sage.all import *
>>> M = PlacticMonoid(Integer(4))
>>> M([Integer(2), Integer(1), Integer(3)])
213
equivalence_class()[source]

Return the plactic equivalence class of self.

This is the list of all words with the same RSK insertion tableau as self.

EXAMPLES:

sage: M = PlacticMonoid(3)
sage: M([2, 1, 3]).equivalence_class()
[213, 231]

>>> from sage.all import *
>>> M = PlacticMonoid(Integer(3))
>>> M([Integer(2), Integer(1), Integer(3)]).equivalence_class()
[213, 231]
to_tableau()[source]

Return the RSK insertion tableau corresponding to self.

EXAMPLES:

sage: M = PlacticMonoid(4)
sage: M([1, 3, 2]).to_tableau()
[[1, 2], [3]]
sage: M([]).to_tableau()
[]

>>> from sage.all import *
>>> M = PlacticMonoid(Integer(4))
>>> M([Integer(1), Integer(3), Integer(2)]).to_tableau()
[[1, 2], [3]]
>>> M([]).to_tableau()
[]
to_word()[source]

Return the row reading word representative of self.

EXAMPLES:

sage: M = PlacticMonoid(4)
sage: M([2, 3, 1]).to_word()
213

>>> from sage.all import *
>>> M = PlacticMonoid(Integer(4))
>>> M([Integer(2), Integer(3), Integer(1)]).to_word()
213
subset(k)[source]

Return the plactic monoid elements represented by words of length k.

Since the plactic monoid is infinite, this returns the finite set of elements of a fixed size, using their row reading word representatives.

EXAMPLES:

sage: M = PlacticMonoid(2)
sage: M.subset(1)
Lazy family (to_word(i))_{i in Semistandard tableaux of size 1 and maximum entry 2}
sage: list(M.subset(1))
[1, 2]
sage: M.subset(2)
Lazy family (to_word(i))_{i in Semistandard tableaux of size 2 and maximum entry 2}
sage: list(M.subset(2))
[11, 12, 22, 21]

>>> from sage.all import *
>>> M = PlacticMonoid(Integer(2))
>>> M.subset(Integer(1))
Lazy family (to_word(i))_{i in Semistandard tableaux of size 1 and maximum entry 2}
>>> list(M.subset(Integer(1)))
[1, 2]
>>> M.subset(Integer(2))
Lazy family (to_word(i))_{i in Semistandard tableaux of size 2 and maximum entry 2}
>>> list(M.subset(Integer(2)))
[11, 12, 22, 21]
class sage.monoids.plactic_monoid.WordMonoid(n)[source]

Bases: UniqueRepresentation, Parent

This class is an ancestor class for the plactic and hypoplactic monoid.

INPUT:

  • n – a positive integer; the size of the alphabet

Elements are represented by words in \(\{1, 2, \ldots, n\}\). It is assumed that the methods \(to_tableau\), \(to_word\) and \(equivalence_class\) are implemented. Equality is determined by methods \(to_tableau\).

an_element()[source]

Return an element of self.

EXAMPLES:

sage: M = PlacticMonoid(3)
sage: M.an_element()
1
sage: from sage.monoids.hypoplactic_monoid import HypoplacticMonoid
sage: H = HypoplacticMonoid(3)
sage: H.an_element()
1

>>> from sage.all import *
>>> M = PlacticMonoid(Integer(3))
>>> M.an_element()
1
>>> from sage.monoids.hypoplactic_monoid import HypoplacticMonoid
>>> H = HypoplacticMonoid(Integer(3))
>>> H.an_element()
1
monoid_generators()[source]

Return the generators of self.

EXAMPLES:

sage: M = PlacticMonoid(4)
sage: G = M.monoid_generators()
sage: G[1], G[2], G[3], G[4]
(1, 2, 3, 4)
sage: from sage.monoids.hypoplactic_monoid import HypoplacticMonoid
sage: H = HypoplacticMonoid(4)
sage: G = H.monoid_generators()
sage: G
Finite family {1: 1, 2: 2, 3: 3, 4: 4}
sage: G[1], G[2], G[3], G[4]
(1, 2, 3, 4)

>>> from sage.all import *
>>> M = PlacticMonoid(Integer(4))
>>> G = M.monoid_generators()
>>> G[Integer(1)], G[Integer(2)], G[Integer(3)], G[Integer(4)]
(1, 2, 3, 4)
>>> from sage.monoids.hypoplactic_monoid import HypoplacticMonoid
>>> H = HypoplacticMonoid(Integer(4))
>>> G = H.monoid_generators()
>>> G
Finite family {1: 1, 2: 2, 3: 3, 4: 4}
>>> G[Integer(1)], G[Integer(2)], G[Integer(3)], G[Integer(4)]
(1, 2, 3, 4)
one()[source]

Return the identity element of self.

EXAMPLES:

sage: M = PlacticMonoid(3)
sage: M.one() == M([])
True
sage: len(M.one())
0
sage: from sage.monoids.hypoplactic_monoid import HypoplacticMonoid
sage: H = HypoplacticMonoid(3)
sage: H.one() == H([])
True
sage: len(H.one())
0

>>> from sage.all import *
>>> M = PlacticMonoid(Integer(3))
>>> M.one() == M([])
True
>>> len(M.one())
0
>>> from sage.monoids.hypoplactic_monoid import HypoplacticMonoid
>>> H = HypoplacticMonoid(Integer(3))
>>> H.one() == H([])
True
>>> len(H.one())
0
rank()[source]

Return the rank of self.

EXAMPLES:

sage: PlacticMonoid(4).rank()
4
sage: from sage.monoids.hypoplactic_monoid import HypoplacticMonoid
sage: HypoplacticMonoid(4).rank()
4

>>> from sage.all import *
>>> PlacticMonoid(Integer(4)).rank()
4
>>> from sage.monoids.hypoplactic_monoid import HypoplacticMonoid
>>> HypoplacticMonoid(Integer(4)).rank()
4
class sage.monoids.plactic_monoid.WordMonoidElement(parent, value)[source]

Bases: ElementWrapper

An element of a word monoid.

Elements are represented by words in the alphabet \(\{1, 2, \ldots, n\}\).

EXAMPLES:

sage: M = PlacticMonoid(4)
sage: M([2, 1, 3])
213

sage: from sage.monoids.hypoplactic_monoid import HypoplacticMonoid
sage: H = HypoplacticMonoid(4)
sage: x = H([3, 2, 2, 1])
sage: x
3221
sage: parent(x)
Hypoplactic monoid of rank 4

>>> from sage.all import *
>>> M = PlacticMonoid(Integer(4))
>>> M([Integer(2), Integer(1), Integer(3)])
213

>>> from sage.monoids.hypoplactic_monoid import HypoplacticMonoid
>>> H = HypoplacticMonoid(Integer(4))
>>> x = H([Integer(3), Integer(2), Integer(2), Integer(1)])
>>> x
3221
>>> parent(x)
Hypoplactic monoid of rank 4
equivalence_class()[source]

Return the equivalence class of self.

This is the list of all words with the same insertion tableau as self.

EXAMPLES:

sage: from sage.monoids.hypoplactic_monoid import HypoplacticMonoid
sage: H = HypoplacticMonoid(3)
sage: H([2, 1, 3]).equivalence_class()
[213, 231]
sage: H = HypoplacticMonoid(4)
sage: H([3, 1, 4, 2]).equivalence_class()
[3142, 3124, 3412, 1342, 1324]
sage: H([3, 1, 1, 2]).equivalence_class()
[3112, 1312, 1132]

>>> from sage.all import *
>>> from sage.monoids.hypoplactic_monoid import HypoplacticMonoid
>>> H = HypoplacticMonoid(Integer(3))
>>> H([Integer(2), Integer(1), Integer(3)]).equivalence_class()
[213, 231]
>>> H = HypoplacticMonoid(Integer(4))
>>> H([Integer(3), Integer(1), Integer(4), Integer(2)]).equivalence_class()
[3142, 3124, 3412, 1342, 1324]
>>> H([Integer(3), Integer(1), Integer(1), Integer(2)]).equivalence_class()
[3112, 1312, 1132]
grade()[source]

Return the length of self as a word.

This is also the grade of self.

EXAMPLES:

sage: M = PlacticMonoid(4)
sage: len(M([3, 1, 2]))
3
sage: from sage.monoids.hypoplactic_monoid import HypoplacticMonoid
sage: H = HypoplacticMonoid(4)
sage: len(H([2, 1, 3]))
3

>>> from sage.all import *
>>> M = PlacticMonoid(Integer(4))
>>> len(M([Integer(3), Integer(1), Integer(2)]))
3
>>> from sage.monoids.hypoplactic_monoid import HypoplacticMonoid
>>> H = HypoplacticMonoid(Integer(4))
>>> len(H([Integer(2), Integer(1), Integer(3)]))
3
is_canonical()[source]

Return whether self is its row reading word representative.

EXAMPLES:

sage: M = PlacticMonoid(3)
sage: M([3, 2, 1]).is_canonical()
True
sage: M([1, 3, 2]).is_canonical()
False

sage: from sage.monoids.hypoplactic_monoid import HypoplacticMonoid
sage: H = HypoplacticMonoid(4)
sage: H([3, 2, 2, 1]).is_canonical()
False
sage: H([2,1,3,2]).is_canonical()
True

>>> from sage.all import *
>>> M = PlacticMonoid(Integer(3))
>>> M([Integer(3), Integer(2), Integer(1)]).is_canonical()
True
>>> M([Integer(1), Integer(3), Integer(2)]).is_canonical()
False

>>> from sage.monoids.hypoplactic_monoid import HypoplacticMonoid
>>> H = HypoplacticMonoid(Integer(4))
>>> H([Integer(3), Integer(2), Integer(2), Integer(1)]).is_canonical()
False
>>> H([Integer(2),Integer(1),Integer(3),Integer(2)]).is_canonical()
True
shape()[source]

Return the shape of the insertion tableau of self.

EXAMPLES:

sage: M = PlacticMonoid(4)
sage: M([2, 1, 3]).shape()
[2, 1]
sage: M([]).shape()
[]

>>> from sage.all import *
>>> M = PlacticMonoid(Integer(4))
>>> M([Integer(2), Integer(1), Integer(3)]).shape()
[2, 1]
>>> M([]).shape()
[]