The lattice conjecture for the left-division order on Krammer's asymmetric Artin monoid $A_n$ (Conjecture 11.12 of ‘An asymmetric generalisation of Artin monoids’)

Daan Krammer introduced an asymmetric generalisation of Artin monoids: for each $n$, the monoid $A_n$ generated by $p_1,\dots,p_n$ with relations $p_a p_b = p_b p_a$ for $|a-b|>1$ and $(p_a p_{a-1})^2 = p_{a-1} p_a p_{a-1}$ for $2 \le a \le n$. He proved that $A_n$ is left-cancellative, admits a Garside element $\Delta_n = p_1(p_2 p_1)\cdots(p_n\cdots p_1)$, and has a polynomially solvable word problem, and he conjectured (Conjecture 11.12 in the published version) that the left-division order $x \le y \iff y \in xA_n$ makes $A_n$ a lattice, so that $A_n$ is a ‘weak left-Garside monoid’, with an explicit factorisation of the left-divisors of $\Delta_n$. No proof or refutation is known: the conjecture remains open.

Background

An Artin monoid is the monoid of positive words in the standard generators of an Artin group, i.e. it is presented by generators $s \in S$ and relations of the form $stst\cdots = tsts\cdots$ with equally many letters on both sides, one relation for each pair of generators; its defining feature is that the two alternating products are symmetric in $s$ and $t$. When such a monoid is generated by involutions (each $s^2 = 1$) one obtains the corresponding Coxeter monoid. Artin monoids of finite Coxeter type (spherical type) are the basic examples of Garside monoids: cancellative monoids in which the left-divisibility order $x \le y \iff y = xz$ for some $z$ is a lattice (any two elements have a greatest common left-divisor, or meet, and a least common right-multiple, or join) and which admit a Garside element $\Delta$ whose left-divisors generate the monoid. The lattice property underlies the classical normal forms and fast word-problem solutions (the word problem asks to decide whether two words in the generators represent the same monoid element) for braid monoids, the free positive braid monoids $B_n^+$ being the type-$A$ Artin monoids.

Krammer (2013) proposed an asymmetric weakening. Writing $[a,b;k]$ for the alternating word $aba\cdots$ of length $k$, he classified monoids generated by two idempotents whose left-division order is a lattice and was led to monoids presented by one-sided relations $[a,b;k] = [b,a;k+1]$, asymmetric counterparts of Artin's two-sided relations. This motivated the class of AI monoids (A for Artin, I for idempotent, since the generators of the associated ‘Coxeter-like’ monoid are idempotent) and their twins, CI monoids. The paper studies one infinite series: the AI monoid $A_n$ on generators $p_1,\dots,p_n$ with relations $p_a p_b = p_b p_a$ for $|a-b|>1$ and $(p_a p_{a-1})^2 = p_{a-1} p_a p_{a-1}$ for $2 \le a \le n$, and the CI monoid $M_n$ obtained by further imposing $p_a^2 = p_a$ and the mirror relation $(p_{a-1}p_a)^2 = p_{a-1} p_a p_{a-1}$. The monoid $M_n$ had appeared (as $Q_n$) in the factorability studies of A. Hess and V. Ozornova. The relations look like braid relations with one side shortened; a useful check is that Picantin's ‘emblematic Artin–Krammer monoid’ $\langle a,b,c \mid abab = aba,\ ac = ca,\ bcbc = bcb\rangle^+$ is the mirror image of $A_3$: with $a = p_1$, $b = p_2$, $c = p_3$ its relations are obtained from those of $A_3$ by reversing each side of the equation, so it is the opposite monoid of $A_3$ (the monoid with the multiplication order reversed, interchanging left and right division).

Krammer proved for these monoids: fast (polynomial) solutions to the word problems of $A_n$ and $M_n$ via convergent rewriting systems (convergent means terminating and confluent, so every word reduces to a unique irreducible normal form) ordered by the shortlex order (words compared first by length, then alphabetically); left-cancellativity of $A_n$ (from $xy = xz$ follows $y = z$); and the existence of a Garside element in $A_n$, namely $\Delta_n = p_1(p_2 p_1)(p_3 p_2 p_1)\cdots(p_n p_{n-1}\cdots p_1)$, meaning every element divides some power of $\Delta_n$ and $x\Delta_n = \Delta_n\varphi_n(x)$ for an endomorphism $\varphi_n$. He also showed that the generalisation genuinely loses structure: a certain 2-generator AI monoid fails the cube condition (the local confluence flavour condition that holds in all Artin monoids and underpins their lattice properties), and contains two elements with a common upper bound but no join. Because $\Delta_n$ has infinitely many left-divisors, $A_n$ cannot be a Garside monoid in the classical sense; Krammer therefore calls a monoid with a Garside element whose left-division order is a lower semi-lattice a weak left-Garside monoid and conjectures $A_n$ is one — indeed that the order is a full lattice.

Problem Statement

For an integer $n \ge 1$, let $A_n$ be the monoid presented by generators $p_1,\dots,p_n$ and relations $p_a p_b = p_b p_a \quad (|a-b| > 1), \qquad p_a p_{a-1} p_a p_{a-1} = p_{a-1} p_a p_{a-1} \quad (2 \le a \le n),$ that is, $(p_a p_{a-1})^2 = p_{a-1} p_a p_{a-1}$. Define the left-division order by $x \le y$ if and only if $y \in xA_n$, and let $\Delta_n = p_1 (p_2 p_1)(p_3 p_2 p_1) \cdots (p_n p_{n-1} \cdots p_1)$, the Garside element of $A_n$. Resolve Krammer's Conjecture 11.12:

(a) Prove or refute that the ordered set $(A_n, \le)$ is a lattice, i.e. that any two elements of $A_n$ have a greatest common left-divisor (meet) and a least common right-multiple (join). An affirmative answer makes $A_n$ a weak left-Garside monoid in Krammer's sense (a monoid with a Garside element whose left-division order is at least a lower semi-lattice, i.e. in which any two elements have a meet).

(b) Prove or refute the proposed explicit description of the left-divisors of $\Delta_n$: an element $x$ of $A_n$ satisfies $x \le \Delta_n$ if and only if there exist elements $z_a$ of the submonoid $\langle p_2, p_3, \dots, p_n\rangle$ (the same submonoid for every $a$) for $a = 1,\dots,n$ such that $x = z_n (p_1 \cdots p_n)\, z_{n-1} (p_1 \cdots p_{n-1}) \cdots z_2 (p_1 p_2)\, z_1\, p_1.$

The conjecture is the assertion that the ordered set $(A_n,\le)$ is a lattice for the whole series $A_n$, with $n \ge 1$ arbitrary; the lattice property of one particular $A_n$ is the corresponding special case of that series-level assertion. Part (b) is the explicit divisor description that Krammer attached to the same conjecture, a claim about the left-divisors of $\Delta_n$ in $A_n$ that is separate from the lattice property of $(A_n,\le)$.

References

1. Daan Krammer, An asymmetric generalisation of Artin monoids, Groups – Complexity – Cryptology 5(2) (2013) 141–168. DOI: 10.1515/gcc-2013-0010, https://doi.org/10.1515/gcc-2013-0010 ; arXiv:1211.5545, https://arxiv.org/abs/1211.5545
2. Patrick Dehornoy, Yves Guiraud, Quadratic normalization in monoids, International Journal of Algebra and Computation 26(5) (2016) 935–972. DOI: 10.1142/S0218196716500399, https://doi.org/10.1142/S0218196716500399 ; arXiv:1504.02717, https://arxiv.org/abs/1504.02717
3. Patrick Dehornoy, Garside and Quadratic Normalisation: A Survey, in Developments in Language Theory (DLT 2015), Lecture Notes in Computer Science, Springer (2015) 14–45. DOI: 10.1007/978-3-319-21500-6_2, https://doi.org/10.1007/978-3-319-21500-6_2 ; arXiv:1504.07788, https://arxiv.org/abs/1504.07788
4. Alexander Heß, Viktoriya Ozornova, Factorability, String Rewriting and Discrete Morse Theory, arXiv preprint (2014). arXiv:1412.3025, https://arxiv.org/abs/1412.3025
5. Viktoriya Ozornova, Discrete Morse theory and a reformulation of the K(π,1)-conjecture, Communications in Algebra 45(4) (2017) 1760–1784. DOI: 10.1080/00927872.2016.1226852, https://doi.org/10.1080/00927872.2016.1226852 ; arXiv:1309.1337, https://arxiv.org/abs/1309.1337
6. Matthieu Picantin, Automatic semigroups vs automaton semigroups, in 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), LIPIcs vol. 132, Article 124. DOI: 10.4230/LIPIcs.ICALP.2019.124, https://doi.org/10.4230/LIPIcs.ICALP.2019.124 ; arXiv:1609.09364, https://arxiv.org/abs/1609.09364
7. Patrick Dehornoy, François Digne, Eddy Godelle, Daan Krammer, Jean Michel, Foundations of Garside Theory, EMS Tracts in Mathematics 22, European Mathematical Society (2015). DOI: 10.4171/139, https://doi.org/10.4171/139 ; arXiv:1309.0796, https://arxiv.org/abs/1309.0796
8. Alen Đurić, Correspondence between factorability and normalization in monoids, International Journal of Algebra and Computation 35(1) (2025) 1–30. DOI: 10.1142/S0218196724500516, https://doi.org/10.1142/S0218196724500516 ; arXiv:2206.01672, https://arxiv.org/abs/2206.01672