Hypoplactic monoid

This file implements the hypoplactic monoid on the alphabet \(\{1, 2, \ldots, n\}\). Elements are represented by words, with equality determined by comparing the quasi-ribbon tableaux obtained from Krob–Thibon insertion. Multiplication is induced by concatenation of words, followed by replacing the product with its quasi-ribbon reading word representative. For references, see [KT1997] and [Nov2000].

AUTHORS:

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

class sage.monoids.hypoplactic_monoid.HypoplacticMonoid(n)[source]

Bases: WordMonoid

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

INPUT:

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

OUTPUT:

The hypoplactic monoid of rank n.

The hypoplactic monoid is a quotient of the free monoid on the alphabet \(\{1, 2, \ldots, n\}\). In this implementation, elements are represented by words in the alphabet \(\{1, 2, \ldots, n\}\). Equality is determined by comparing the quasi-ribbon tableaux obtained from Krob–Thibon insertion.

The identity element is the empty word. Multiplication is induced by concatenation of words. The product is stored using the quasi-ribbon reading word representative obtained from hypoplactic insertion.

EXAMPLES:

sage: H = HypoplacticMonoid(4)
sage: H
Hypoplactic monoid of rank 4
sage: H.rank()
4

>>> from sage.all import *
>>> H = HypoplacticMonoid(Integer(4))
>>> H
Hypoplactic monoid of rank 4
>>> H.rank()
4

Elements are constructed from tuples:

sage: x = H([3, 2, 2, 1])
sage: x
3221
sage: x.to_tableau()
[[1], [2, 2], [None, 3]]
sage: x.to_word()
2132
[Python] 
>>> from sage.all import *
>>> x = H([Integer(3), Integer(2), Integer(2), Integer(1)])
>>> x
3221
>>> x.to_tableau()
[[1], [2, 2], [None, 3]]
>>> x.to_word()
2132

Two words represent the same hypoplactic element when they have the same quasi-ribbon insertion tableau:

sage: H([3, 2, 2, 1]) == H([2, 3, 1, 2])
True
sage: H([3, 2, 2, 1]) == H([1, 2, 2, 3])
False

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

Multiplication is induced by concatenation, followed by replacing the result with its quasi-ribbon reading word representative:

sage: H([3]) * H([4])
34
sage: H([4]) * H([3])
43
[Python] 
>>> from sage.all import *
>>> H([Integer(3)]) * H([Integer(4)])
34
>>> H([Integer(4)]) * H([Integer(3)])
43
class Element(parent, value)[source]

Bases: WordMonoidElement

An element of a hypoplactic monoid.

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

EXAMPLES:

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 *
>>> H = HypoplacticMonoid(Integer(4))
>>> x = H([Integer(3), Integer(2), Integer(2), Integer(1)])
>>> x
3221
>>> parent(x)
Hypoplactic monoid of rank 4
to_tableau()[source]

Return the quasi-ribbon insertion tableau corresponding to self.

The tableau is computed using Krob–Thibon insertion.

OUTPUT:

The quasi-ribbon tableau obtained by inserting the word representing self.

EXAMPLES:

sage: H = HypoplacticMonoid(4)
sage: H([3, 2, 2, 1]).to_tableau()
[[1], [2, 2], [None, 3]]
sage: H([3, 4, 3, 2, 1, 2]).to_tableau()
[[1], [2, 2], [None, 3, 3], [None, None, 4]]

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

Return the quasi-ribbon reading word representative of self.

The reading word is obtained from the quasi-ribbon insertion tableau by reading columns from left to right, and from bottom to top within each column.

OUTPUT:

A tuple containing the quasi-ribbon reading word of self.

EXAMPLES:

sage: H = HypoplacticMonoid(4)
sage: H([3, 2, 2, 1]).to_word()
2132
sage: H([3, 4, 3, 2, 1, 2]).to_word()
213243

>>> from sage.all import *
>>> H = HypoplacticMonoid(Integer(4))
>>> H([Integer(3), Integer(2), Integer(2), Integer(1)]).to_word()
2132
>>> H([Integer(3), Integer(4), Integer(3), Integer(2), Integer(1), Integer(2)]).to_word()
213243
subset(k)[source]

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

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

EXAMPLES:

sage: H = HypoplacticMonoid(2)
sage: H.subset(1)
Lazy family (to_word(i))_{i in Quasi-ribbon tableaux of size 1 with entries at most 2}
sage: list(H.subset(1))
[1, 2]
sage: H.subset(2)
Lazy family (to_word(i))_{i in Quasi-ribbon tableaux of size 2 with entries at most 2}
sage: list(H.subset(2))
[11, 12, 22, 21]

>>> from sage.all import *
>>> H = HypoplacticMonoid(Integer(2))
>>> H.subset(Integer(1))
Lazy family (to_word(i))_{i in Quasi-ribbon tableaux of size 1 with entries at most 2}
>>> list(H.subset(Integer(1)))
[1, 2]
>>> H.subset(Integer(2))
Lazy family (to_word(i))_{i in Quasi-ribbon tableaux of size 2 with entries at most 2}
>>> list(H.subset(Integer(2)))
[11, 12, 22, 21]