A Gröbner-Shirshov basis over a special type of braid monoids

1.   Introduction and preliminaries

The Gröbner basis theory for commutative algebras was introduced by Buchberger ^[2] which provided a solution to the reduction problem for commutative algebras. In ^[3], Bergman generalized this theory to the associative algebras by proving the diamond lemma. On the other hand, the parallel theory of the Gröbner basis was developed for Lie algebras by Shirshov in ^[4]. In ^[5], Bokut noticed that Shirshov's method works for also associative algebras. Hence Shirshov's theory for Lie and their universal enveloping algebras is called the Gröbner-Shirshov basis theory. We may refer the papers ^{[6,7,8,9,10,11,12,13]} for some recent studies over Gröbner-Shirshov bases in terms of algebraic ways, the papers ^[14,15] related to Hilbert series and the paper ^[16] in terms of graph theoretic way. Furthermore citation ^[17] can be used to understand normal forms for the monoid of positive braids by using Gröbner-Shirshov basis.

The word, conjugacy and isomorphism problems (shortly decision problems) have played an important role in group theory since the work of M. Dehn in early 1900's. Among them, especially the word problem has been studied widely in groups (see ^[18]). It is well known that the word problem for finitely presented groups is not solvable in general; that is, given any two words obtained by generators of the group, there may not be an algorithm to decide whether these words represent the same element in this group.

The method Gröbner-Shirshov basis theory gives a new algorithm to obtain normal forms of elements of groups, monoids and semigroups, and hence a new algorithm to solve the word problem in these algebraic structures (see also ^[19], for relationship with word problem for semigroups and ideal membership problem for non-commutative polynomail rings). By considering this fact, our aim in this paper is to find a Gröbner-Shirshov basis of the symmetric inverse monoid in terms of the dex-leg ordering on the related words of symmetric inverse monoids.

Symmetric inverse monoids are partial bijections and they are very well known in combinatorics. Easdown et al. ^[20] studied a presentation for the symmetric inverse monoid $I_n$. By adding relations $\sigma _1^2$ $= \sigma _2^2$ $= \cdots$ $= \sigma _{n-1}^2 = 1$ into the presentation of the braid group described in terms of Artin's Theorem, it is obtained the well-known Moore presentation for the symmetric group as defined in ^[21]. Using this in the Popova's description ^[22] for the presentation of the symmetric inverse monoid $I_n$ yields the following presentation:

In ^[23], the author has also studied presentations of symmetric inverse and singular part of the symmetric inverse monoids.

2.   Gröbner-Shirshov bases and the composition-diamond lemma

Let $k$ be a field and $k\langle X\rangle$ be the free associative algebra over $k$ generated by $X$. Denote by $X^{\ast}$ the free monoid generated by $X$, where the empty word is the identity which is denoted by $1$. For a word $w\in X^{\ast}$, let us denote the length of $w$ by $|w|$. Also assume that $X^{\ast}$ is a well ordered monoid. A well-ordering $\leq$ on $X^{\ast }$ is called a monomial ordering if for $u, v\in X^{\ast }$, we have $u\leq v\Rightarrow w_{1}uw_{2} \leq w_{1}vw_{2}$, for all $w_{1}, w_{2}\in X^*$. A standard example of monomial ordering on $X^*$ is the deg-lex ordering, in which two words are compared first by the degree and then lexicographically, where $X$ is a well-ordered set.

Every nonzero polynomial $f\in k\left\langle X\right\rangle$ has the leading word $\overline{f}$. If the coefficient of $\overline{f}$ in $f$ is equal to $1$, then $f$ is called monic. The following fundamental materials can be found in ^{[3,5,6,7,8,10,11,12,24]}.

Let $f$ and $g$ be two monic polynomials in $k\langle X\rangle$. Therefore we have two compositions between $f$ and $g$ as follows:

$1.$ If $w$ is a word such that $w = \overline{f}b = a\overline{g}$ for some $a, b\in X^{\ast }$ with $|\overline{f}|+|\overline{g}| > |w|$, then the polynomial $(f, g)_{w} = fb-ag$ is called the intersection composition of $f$ and $g$ with respect to $w$ (and denoted by $f\wedge g$). In here, the word $w$ is called an ambiguity of the intersection.

$2.$ If $w = \overline{f} = a\overline{g}b$ for some $a, b\in X^{\ast }$, then the polynomial $(f, g)_{w} = f-agb$ is called the inclusion composition of $f$ and $g$ with respect to $w$ (and denoted by $f\vee g$). In this case, the word $w$ is called an ambiguity of the inclusion.

If $g$ is a monic polynomial, $\overline{f} = a\overline{g}b$ and $\alpha$ is the coefficient of the leading term $\overline{f}$, then the transformation $f\mapsto f-\alpha agb$ is called an elimination of the leading word (ELW) of $g$ in $f$.

Let $S\subseteq k\left\langle X\right\rangle$ with each $s\in S$ monic. Then the composition $(f, g)_{w}$ is called trivial modulo $(S, w)$ if $(f, g)_{w} = \sum\alpha_{i}a_{i}s_{i}b_{i}$, where each $\alpha _{i}\in k, \:a_{i}, b_{i}\in X^{\ast }, \:s_{i}\in S$ and $a_{i}\overline{s_{i}}b_{i} < w$. If this is the case, then we write $(f, g)_{w}\equiv 0\ mod(S, w)$. In general, for $p, q\in k\langle X\rangle$, we write $p\equiv q\ mod(S, w)$ which means that $p-q = \sum\alpha_i a_{i}s_{i}b_{i}$, where each $\alpha _{i}\in k, \:a_{i}, b_{i}\in X^{\ast }, \:s_{i}\in S$ and $a_{i}\overline{s_{i}}b_{i} < w$.

A set $S$ with the well ordering $\leq$ is called a Gröbner-Shirshov basis for $k\left\langle X\mid S\right\rangle$ if every composition $(f, g)_{w}$ of polynomials in $S$ is trivial modulo $S$ and the corresponding $w$.

The following lemma was proved by Shirshov ^[4] for free Lie algebras (with deg-lex ordering) in 1962 (^[24]). In 1976, Bokut ^[5] specialized the Shirshov's approach to associative algebras (see also ^[3]). On the other hand, for commutative polynomials, this lemma is known as the Buchberger's Theorem (cf. ^[2,25]).

Lemma 1 (Composition-Diamond Lemma). Let $k$ be a field,

and $\leq$ a monomial order on $X^{\ast }$, where $Id(S)$ is the ideal of $k\langle X\rangle$ generated by $S$. Then the following statements are equivalent:

1. $S$ is a Gröbner-Shirshov basis.

2. $f\in Id(S)\Rightarrow \overline{f} = a\overline{s}b$ for some $s\in S$ and $a, b\in X^{\ast }$.

3. $Irr(S) = \{u\in X^{\ast }\mid u\neq a\overline{s}b, s\in S, a, b\in X^{\ast }\}$ is a basis of the algebra $A = k\left\langle X\mid S\right\rangle$.

If a subset $S$ of $k\langle X\rangle$ is not a Gröbner-Shirshov basis, then we can add to $S$ all nontrivial compositions of polynomials of $S$, and by continuing this process (maybe infinitely) many times, we eventually obtain a Gröbner-Shirshov basis $S^{comp}$. Such a process is called the Shirshov algorithm.

If $S$ is a set of "semigroup relations" (that is, the polynomials in $S$ are of the form $u-v$, where $u, v\in X^*$), then a nontrivial composition will have the same form. As a result, the set $S^{comp}$ also consists of semigroup relations.

Let $M = sgp\left\langle X\mid S\right\rangle$ be a semigroup presentation. Then $S$ is a subset of $k\langle X\rangle$ and hence one can find a Gröbner-Shirshov basis $S^{comp}$. The last set does not depend on $k$, and as mentioned before, it consists of semigroup relations. We will call $S^{comp}$ a Gröbner-Shirshov basis of $M$. This is the same as a Gröbner-Shirshov basis of the semigroup algebra $kM = k\left\langle X\mid S\right\rangle$. If $S$ is a Gröbner-Shirshov basis of the semigroup $M = sgp\left\langle X\mid S\right\rangle$, then $Irr\left(S\right)$ is a normal form for $M$ ^[9,26].

3.   A Gröbner-Shirshov basis for the monoid $I_n$

The target of this section is to obtain a Gröbner-Shirshov basis for the symmetric inverse monoid $I_n$ by taking into account the presentation given in (1.1). After that we will indicate the solvability of the word problem over $I_n$.

By ordering the generators as $\varepsilon > {\sigma _{n - 1}} > {\sigma _{n - 2}} > {\sigma _{n - 3}} > \cdots > {\sigma _2} > {\sigma _1}$ in (1.1), we have the following main result of this paper.

Theorem 2. A Gröbner-Shirshov basis for the symmetric inverse monoid consists of the following relations:

We also have the following additional conditions.

● For the relation $(5)$: For $1\leq k < i-1$, to take $M_k = 1$ it is necessary $M_{k+1} = 1$.

● For the relation $(6)$: For $1\leq k < n-2$, to take $P_k = 1$ it is necessary $P_{k+1} = 1$.

● For the relation $(7)$: For $i\leq k < n-3$, to take $Q_k = 1$ it is necessary $Q_{k+1} = 1$.

For $j\leq k < n-2$, to take $\varphi_k = 1$ it is necessary $\varphi_{k+1} = 1$.

● For the relation $(7')$: For $i\leq k < n-4$, to take $Q_k = 1$ it is necessary $Q_{k+1} = 1$.

For $j\leq k < n-3$, to take $\varphi_k = 1$ it is necessary $\varphi_{k+1} = 1$.

For $s\leq k < n-2$, to take $\lambda_k = 1$ it is necessary $\lambda_{k+1} = 1$.

● For the relation $(8)$: For $n-t\leq k < n-2$, to take $L_k = 1$ it is necessary $L_{k+1} = 1$.

● For the relation $(9)$: For $1\leq t < (n-k)-1$, to take $U_t = 1$ it is necessary $U_{t+1} = 1$.

For $1\leq t < (n-k)+2$, to take $V_t = 1$ it is necessary $V_{t+1} = 1$.

For $1\leq t < n-1$, to take $S_t = 1$ it is necessary $S_{t+1} = 1$.

For $1\leq t < n-2$, to take $T_t = 1$ it is necessary $T_{t+1} = 1$.

● For the relation $(10)$: For $1\leq t < (n-k)-1$, to take $X_t = 1$ it is necessary $X_{t+1} = 1$.

For $1\leq t < (n-k)+2$, to take $Y_t = 1$ it is necessary $Y_{t+1} = 1$.

For $1\leq t < n-2$, to take $Z_t = 1$ it is necessary $Z_{t+1} = 1$.

For $i\leq t < n-3$, to take $W_t = 1$ it is necessary $W_{t+1} = 1$.

For $j\leq t < n-2$, to take $R_t = 1$ it is necessary $R_{t+1} = 1$.

Proof. Relations given for $I_n$ in (1.1) provide relations among (1)–(10). Now we need to prove that all compositions among relations (1)–(10) are trivial. To do that, firstly, we consider intersection compositions of these relations. Hence we have the following ambiguties $w$:

All these ambiguities are trivial. Let us show some of them as in the following.

It is seen that there are no any inclusion compositions among relations (1)–(10). This ends up the proof.

As a consequence of Lemma 1 and Theorem 2, we have the following result.

Corollary 3. Let $C(u)$ be a normal form of a word $u\in I_{n}$. Then $C(u)$ is of the form

where ${{k_p} = \left\{ {0, 1} \right\}}$ $(1 \leq p \leq n)$. In this above expression,

● if ${k_p} = 1\, \, \left({1 \leq p \leq n - 1} \right)$ then the word ${W_{p\, + 1\, }}$ which begins with ${\sigma _{n - 1}}$ and generated by $\sigma _i$ $(1 \leq i \leq n - 1)$ is actually a reduced word. Moreover the word ${W_{1}}$ generated by $\sigma _i$ $(1 \leq i \leq n - 1)$ is an arbitrary reduced word.

● if ${k_p} = 0\, \, \left({1 \leq p \leq n - 1} \right)$ then the word $W_pW_{p+1}$ is also reduced.

In addition, subwords of the forms $W_i\varepsilon^{k_i}W_{i+1}\varepsilon^{k_{i+1}}$ $\left({1 \leq i \leq n - 1} \right)$, $W_j\varepsilon^{k_j}W_{j+1}\varepsilon^{k_{j+1}}W_{j+2}\varepsilon^{k_{j+2}}$ $\left({1 \leq j \leq n - 2} \right)$, $W_r\varepsilon^{k_r}W_{r+1}\varepsilon^{k_{r+1}}W_{r+2}\varepsilon^{k_{r+2}}W_{r+3}\varepsilon^{k_{r+3}}$ $\left({1 \leq r \leq n - 3} \right)$ and $\varepsilon^{k_s}W_{s+1}\varepsilon^{k_{s+1}}W_{s+2}$ $\left({1 \leq s \leq n - 2} \right)$ must be reduced.

By Corollary 3, we can say that the word problem is solvable for symmetric inverse monoid $I_{n}$.

Remark 4. We note that if we change the orderings on words we find another Gröbner-Shirshov bases related to chosen orederings. Thus we get normal form for given algebraic structure depending on ordering. To get this normal form it is used third item of Composition-Diamond Lemma. It is known that to get normal form structure implies solvability of the word problem. If one can not obtain a Gröbner-Shirshov basis according to chosen ordering on words, this does not mean that the word problem is not solvable.

4.   An application

As an application of Theorem 2, we will give the following Example 5 which describes a Gröbner-Shirshov basis for the symmetric inverse monoid $I_4$. The accuracy and efficiency of this example can be seen by "$GBNP$ package in GAP ^[1] which computes Gröbner bases of non-commutative polynomials as follows.

We note that by $GBNP$ package program one can compute Gröbner-Shirshov basis of symmetric inverse monoids for small sizes, for example $I_4$ and $I_5$. But there are no any other computer programs that compute a Gröbner-Shirshov basis for general size of symmetric inverse monoids. For this reason, it is worth to study and obtain a Gröbner-Shirshov basis for this important structure.

Example 5. The presentation of $I_4$ is as follows.

We use deg-lex order induced by $\sigma _1 < \sigma _2 < \sigma _{3} < \varepsilon$. By this ordering, a Gröbner-Shirshov basis for symmetric inverse monoid $I_4$ consists of the following $38$ relations.

5.   Conclusions

The idea of Gröbner-Shirshov basis theory plays a significant role in several fields of mathematics (algebra, graph theory, knot theory), computer sciences (computational algebra) and information sciences. From algebraic way the method Gröbner-Shirshov basis theory gives a new algorithm to obtain normal forms of elements of groups, monoids, semigroups and various type of algebras, and hence a new algorithm to solve the word problem in these algebraic structures.

In this study, we obtained a Gröbner-Shirshov basis for a special type of braid monoids, namely the symmetric inverse monoid $I_n$, in terms of the dex-leg ordering on the related elements of monoid. As known symmetric inverse monoids are partial bijections and they are very well known and important in combinatorics. By taking into account the Gröbner-Shirshov basis, we achieved the normal form structure of this important monoid. This normal form gave us the solution of the word problem. At the final part of this study, we presented an application of our main result which find out a Gröbner-Shirshov basis for the symmetric inverse monoid $I_4$ by using a package program, $GBNP$, in GAP. Since $GBNP$ is a restricted package program in point of size of symmetric inverse monoids it is worth to study and obtain a Gröbner-Shirshov basis for general size of this important structure.

In the future, the result of this work can be expanded to some other algebraic, computational structures and associated to graph theory, growth, Hilbert series and knot theory.

Acknowledgments

This work was funded by the Deanship of Scientific Research (DSR), King Abdulaziz University, Jeddah, under grant No (130-211-D1439). The authors, therefore, acknowledge with thanks DSR technical and financial support. The authors would like to thank to the referees for their suggestions and valuable comments.

Conflict of interest

The authors declare that they have no conflict of interest.