Direct Composition–Diamond Lemma proofs for the Gröbner–Shirshov bases of Malcev-problem group embeddings

A methodological open problem in Gröbner–Shirshov basis theory, left open at the end of Section 3 of Bokut and Shum's 2008 St. Petersburg Mathematical Journal paper “Relative Gröbner–Shirshov bases for algebras and groups”: the known relative Gröbner–Shirshov (standard-basis) results for the group constructions arising in Bokut's solution of Malcev's embedding problem (the quotient groups of the multiplicative semigroups of certain rings, Siberian Mathematical Journal 1969, parts I–III, together with the companion 1969 paper “The problem of Mal'cev”) are proved only by inheriting very long original arguments that rely on the machinery of groups with (relative) standard bases. The problem is to give direct and substantially shorter proofs of these relative Gröbner–Shirshov bases, in the sense of the relative Gröbner–Shirshov basis framework of Bokut and Shum, replacing the external combinatorial group theory of the inherited arguments with the intrinsic composition-elimination method.

Background

A Gröbner–Shirshov basis is the non-commutative analogue of a Gröbner basis: given a presentation of an associative algebra (or, via its semigroup algebra, of a semigroup or group) by generators and defining relations, it is a set of relations that is closed under certain “compositions” (intersections and inclusions of leading monomials), so that every element reduces to a unique irreducible normal form. The foundational result is the Composition–Diamond Lemma (Shirshov 1962 for Lie algebras, specialized by Bokut to associative algebras in 1972; independently Bergman's Diamond Lemma, 1978): a set of relations is a Gröbner–Shirshov basis exactly when the set of irreducible words is a linear basis of the presented algebra, which yields normal forms and solves the word problem. This machinery has been applied extensively to braid groups: after Artin's classical presentation and Garside's normal form (a canonical way of writing every braid as a product of positive “simple” braids times a power of the half-twist braid), Birman, Ko and Lee (1998) introduced a new generating system for the $n$-string braid group $B_n$ (the band generators $a_{ts}$, conjugates of the Artin generators) together with a new normal form, and Bokut's 2009 paper found a Gröbner–Shirshov basis for $B_n$ in the Birman–Ko–Lee generators enriched by the Garside half-twist element $\delta$ (the braid in which all $n$ strands cross once, whose powers generate the center of $B_n$), recovering the Birman–Ko–Lee normal form and hence a new word-problem algorithm.

A parallel, older line of Bokut's work concerns Malcev's embedding problem for rings: whether and how the multiplicative semigroup of a ring can be embedded into a group. In the three-part series “Quotient groups of the multiplicative semigroups of certain rings I–III” (Siberian Mathematical Journal, 1969), together with the companion paper “The problem of Mal'cev” (Siberian Mathematical Journal, 1969), Bokut constructed the quotient (universal) groups of the multiplicative semigroups of certain rings — key examples in his solution of the Malcev embedding problem, including semigroup algebras and the Magnus algebra of formal power series over a free semigroup — and established normal forms for them. Those proofs are notoriously long and depend on the theory of groups with a standard basis and its relative version (Siberian Mathematical Journal 1968), which is itself a forerunner of the Gröbner–Shirshov basis method for groups.

In 2007–2008, Bokut and Shum developed a framework of “relative” Gröbner–Shirshov bases for algebras and groups (free $\Gamma$-algebras over a group $\Gamma$ with strong $\Gamma$-Gröbner–Shirshov bases), equipped with a relative Composition–Diamond Lemma. Related progress in the same circle includes Chen and Zhong's Composition–Diamond Lemma for a non-monomial “S-weak” order, with which the Britton lemma and normal-form theorem for HNN extensions of groups (an HNN extension is a group obtained from a base group by adjoining a stable letter $t$ with relations $t^{-1}at=\varphi(a)$ identifying two isomorphic subgroups) were first proved directly via Gröbner–Shirshov bases (2008) — a different, general HNN setting. At the end of Section 3 of their 2008 paper, Bokut and Shum note that their relative Gröbner–Shirshov basis theorems for the Malcev-problem groups (Theorems 3.1 and 3.4) are proved only by inheriting the rewriting and standard-basis results of the 1968–1969 papers, and that one could instead use the relative Composition–Diamond Lemma to prove them “by checking that all possible compositions … are trivial”, an approach that “would be easier than the rather complicated arguments … based on the notion of a ‘group with a relative standard basis’”. This methodological question is the present problem: it asks to bring the Malcev-problem embedding theorems inside the intrinsic composition-elimination framework, as was meanwhile achieved for braid groups and HNN extensions.

Problem Statement

Give direct proofs of the relative Gröbner–Shirshov bases (equivalently, the normal forms) for the universal groups $G(R^*)$ of the multiplicative semigroups of the rings $R$ constructed in the 1969 three-part series “Quotient groups of the multiplicative semigroups of certain rings I–III” and in the companion 1969 paper “The problem of Mal'cev”: the required target class is exactly the set of these groups $G(R^*)$, one for each such ring $R$, and a solution must cover every group in that class — concrete instances being the universal groups $G(GF(2)(Q)^*)$ for the SNA-semigroups $Q$ and the group $G(GF(2)(Q_4)^*)$ for $Q_4$, with $Q_4$ as defined in [13] and the SNA-semigroups $Q$ as defined in [3]. The aim is, for each group of the class just described, to prove that the explicit defining relative relations of the 1968–1969 work (the rewriting relations, taken with respect to the tower order or another stated order) form an explicit relative Gröbner–Shirshov basis with respect to a stated order (possibly a non-monomial or quasi-order) whose compositions are all trivial, so that the normal-form and embeddability statements of the 1969 work follow from these bases. These proofs are to be intrinsic, replacing the original very long arguments that pass through the machinery of groups with (relative) standard bases and without invoking the inherited rewriting/$\Gamma$-basis results of the original proofs; this is the programme explicitly left open at the end of Section 3 of Bokut–Shum (2008).

References

1. L. A. Bokut, Gröbner–Shirshov basis for the Braid group in the Birman–Ko–Lee generators, Journal of Algebra 321 (2009), 361–376, DOI 10.1016/j.jalgebra.2008.10.007, https://doi.org/10.1016/j.jalgebra.2008.10.007 (arXiv preprint: arXiv:0806.1123, https://arxiv.org/abs/0806.1123)
2. L. A. Bokut, Groebner-Shirshov basis for the braid group in the Birman-Ko-Lee-Garside generators, arXiv:0806.1123 (2008), https://arxiv.org/abs/0806.1123
3. L. A. Bokut', Quotient groups of the multiplicative semigroups of certain rings, I–III, Siberian Mathematical Journal 10 (1969): part I, DOI 10.1007/BF00970431, https://doi.org/10.1007/BF00970431; part II, DOI 10.1007/BF00973866, https://doi.org/10.1007/BF00973866; part III, DOI 10.1007/BF00973867, https://doi.org/10.1007/BF00973867
4. L. A. Bokut', Groups with relative standard basis, Siberian Mathematical Journal 9 (1968), DOI 10.1007/BF01040899, https://doi.org/10.1007/BF01040899
5. L. A. Bokut, K. P. Shum, Relative Gröbner–Shirshov bases for algebras and groups, St. Petersburg Mathematical Journal 19 (2008), no. 6, 867–881, DOI 10.1090/S1061-0022-08-01025-X, https://doi.org/10.1090/S1061-0022-08-01025-X
6. Yuqun Chen, Chanyan Zhong, Gröbner–Shirshov basis for HNN extensions of groups and for the alternating group, Communications in Algebra 36 (2008), no. 1, 94–103, DOI 10.1080/00927870701665180, https://doi.org/10.1080/00927870701665180 (arXiv preprint: arXiv:0804.0642, https://arxiv.org/abs/0804.0642)
7. Yuqun Chen, Gröbner–Shirshov bases for Schreier extensions of groups, Communications in Algebra 36 (2008), no. 5, 1609–1625, DOI 10.1080/00927870701869899, https://doi.org/10.1080/00927870701869899 (arXiv preprint: arXiv:0804.0641, https://arxiv.org/abs/0804.0641)
8. Yuqun Chen, Chanyan Zhong, Gröbner–Shirshov bases for some one-relator groups, Algebra Colloquium 19 (2012), 99–116, DOI 10.1142/S1005386712000077, https://doi.org/10.1142/S1005386712000077
9. L. A. Bokut, Yuqun Chen, Gröbner–Shirshov bases: some new results, in Advances in Algebra and Combinatorics, World Scientific (2008), 35–56, DOI 10.1142/9789812790019_0003, https://doi.org/10.1142/9789812790019_0003 (arXiv preprint: arXiv:0804.1344, https://arxiv.org/abs/0804.1344)
10. L. A. Bokut, Yuqun Chen, Qiuhui Mo, Gröbner–Shirshov bases and embeddings of algebras, International Journal of Algebra and Computation 20 (2010), 875–900, DOI 10.1142/S0218196710005923, https://doi.org/10.1142/S0218196710005923 (arXiv preprint: arXiv:0908.1992, https://arxiv.org/abs/0908.1992)
11. L. A. Bokut, Yuqun Chen, Gröbner-Shirshov bases and PBW theorems, arXiv:1502.06472 (2015), https://arxiv.org/abs/1502.06472
12. J. Birman, K. H. Ko, S. J. Lee, A new approach to the word and conjugacy problems in the Braid Groups, Advances in Mathematics 139 (1998), 322–353, DOI 10.1006/aima.1998.1761, https://doi.org/10.1006/aima.1998.1761
13. L. A. Bokut', The problem of Mal'cev, Siberian Mathematical Journal 10 (1969), no. 5, 706–739 (translated from Sibirskii Mat. Zh. 10 (1969), no. 5, 965–1005)