TY - JOUR

T1 - Crystal monoids & crystal bases: rewriting systems and biautomatic structures for plactic monoids of types An, Bn, Cn, Dn, and G2

AU - Cain, Alan J.

AU - Gray, Robert D.

AU - Malheiro, António

N1 - The first named author was supported by an Investigador FCT fellowship (IF/01622/2013/CP1161/CT0001).
The first and third named authors were partially supported by the Fundacao para a Ciencia e a Tecnologia (Portuguese Foundation for Science and Technology) through the project UID/MAT/00297/2013 (Centro de Matematica e Aplicacoes) and the projects PTDC/MHC-FIL/2583/2014.
All three authors were partially supported by the Fundacao para a Ciencia c a Tecnologia (Portuguese Foundation for Science and Technology) through the project PTDC/MAT-PUR/31174/2017.
Much of the research leading to this paper was undertaken during visits by the second named author to the Centro de Algebra da Universidade de Lisboa and the Centro de Matematica e Aplicacoes, Universidade Nova de Lisboa. We thank both centres and universities for their hospitality. These visits were funded by the FCT project PEst-OE/MAT/UI0143/2014 (held by CAUL) and the FCT exploratory project IF/01622/2013/CP1161/CT0001 (attached to the first named author's fellowship).
The second named author was partially supported by the EPSRC grant EP/N033353/1 'Special inverse rnonoids: subgroups, structure, geometry, rewriting systems and the word problem'.

PY - 2019/2/1

Y1 - 2019/2/1

N2 - The vertices of any (combinatorial) Kashiwara crystal graph carry a natural monoid structure given by identifying words labelling vertices that appear in the same position of isomorphic components of the crystal. Working on a purely combinatorial and monoid-theoretical level, we prove some foundational results for these crystal monoids, including the observation that they have decidable word problem when their weight monoid is a finite rank free abelian group. The problem of constructing finite complete rewriting systems, and biautomatic structures, for crystal monoids is then investigated. In the case of Kashiwara crystals of types An, Bn, Cn, Dn, and G2 (corresponding to the q-analogues of the Lie algebras of these types) these monoids are precisely the generalised plactic monoids investigated in work of Lecouvey. We construct presentations via finite complete rewriting systems for all of these types using a unified proof strategy that depends on Kashiwara's crystal bases and analogies of Young tableaux, and on Lecouvey's presentations for these monoids. As corollaries, we deduce that plactic monoids of these types have finite derivation type and satisfy the homological finiteness properties left and right FP∞. These rewriting systems are then applied to show that plactic monoids of these types are biautomatic and thus have word problem soluble in quadratic time.

AB - The vertices of any (combinatorial) Kashiwara crystal graph carry a natural monoid structure given by identifying words labelling vertices that appear in the same position of isomorphic components of the crystal. Working on a purely combinatorial and monoid-theoretical level, we prove some foundational results for these crystal monoids, including the observation that they have decidable word problem when their weight monoid is a finite rank free abelian group. The problem of constructing finite complete rewriting systems, and biautomatic structures, for crystal monoids is then investigated. In the case of Kashiwara crystals of types An, Bn, Cn, Dn, and G2 (corresponding to the q-analogues of the Lie algebras of these types) these monoids are precisely the generalised plactic monoids investigated in work of Lecouvey. We construct presentations via finite complete rewriting systems for all of these types using a unified proof strategy that depends on Kashiwara's crystal bases and analogies of Young tableaux, and on Lecouvey's presentations for these monoids. As corollaries, we deduce that plactic monoids of these types have finite derivation type and satisfy the homological finiteness properties left and right FP∞. These rewriting systems are then applied to show that plactic monoids of these types are biautomatic and thus have word problem soluble in quadratic time.

KW - Automatic monoid

KW - Crystal basis

KW - Plactic monoid

KW - Rewriting system

KW - Tableaux

UR - http://www.scopus.com/inward/record.url?scp=85056448357&partnerID=8YFLogxK

U2 - 10.1016/j.jcta.2018.11.010

DO - 10.1016/j.jcta.2018.11.010

M3 - Article

AN - SCOPUS:85056448357

SN - 0097-3165

VL - 162

SP - 406

EP - 466

JO - Journal of Combinatorial Theory. Series A

JF - Journal of Combinatorial Theory. Series A

ER -