14 Non-Commutative Grobner Basis Methods

14.1 Non-Commutative Gröbner Bases

Since we encountered some problems when we tried to use commutative polynomials for constructing secure Gröbner basis cryptosystems, it is natural to examine the possibility to use non-commutative algebraic structures. Given a finite set of letters X = {x₁,…, x_n}, a word in X is an element of the form w = x_t x_t · x_jt with ij ϵ {1,…, n}. Here we denote the empty word by 1 and the set of all words by (X}. It is clear that concatenation makes (X} into a monoid with neutral element 1. We call it the free monoid on X.

Definition 14.1.1. Let K be a field and X = {x₁,…,x_n}. The K-vector space with basis (X} can be made into a K-algebra by extending the multiplication of words K-linearly. In other words, given f = c₁w₁ + … + c_sw_s and g = c1w1 + … + c[w[ with c_j, c- ϵ K and w_t, w- ϵ (X}, we letf • g = _jj- cf-wwj. This defines a K-algebra which is denoted by K (X} and is called the free associative K-algebra on X or the non-commutative polynomial ring in the indeterminates x₁,…,x_n.

Our goal in this section is to develop a Gröbner basis theory for K (X} which is analogous to the Gröbner basis theory for the commutative polynomial ring. We will see that most definitions and results carry over easily, but Buchberger’s Algorithm turns into an enumerating procedure.

Let us start with some basic definitions.

Definition 14.1.2. Let K beafieldand X = {x₁,…,x_n} a set of letters.

(1)  Given a word w = x_t … x_t ϵ (X} with i₁,…,i_k ϵ {1,…, n}, the number l(w) = k is called the length of w. The length of the empty word is defined to be zero.

(2)  Given two words w, w’ ϵ (X}, the word w’ is called a subword of w if w is of the form w = uw’u’ with words u, u’ ϵ (X}.

(3)  Given a non-zero non-commutative polynomial f = c₁ w₁ + … + c_sw_s in K(X} with c_j ϵ K {0} and w_j ϵ (X}, the elements c_j are called the coefficients of the words w_j in f, and the non-negative integer degf) = max{l(w_j) | i = 1,…, s} is called the degree of f.

In order to compute effectively with non-commutative polynomials, we need to represent them in a unique way. Thus we need to order the words in a suitable way.

Definition 14.1.3. A word ordering a on (X} is a complete ordering relation which satisfies the following two additional conditions.

(1)  The ordering a is compatible with multiplication, that is if two words w, w’ ϵ (X) satisfy an inequality w <_a w’ and if u, u’ ϵ (X} are further words, then we have uwu’ <_a uw’u’.

(2)  The ordering o is a well-ordering, that is every descending chain of words w₁ >_o w₂ >_o … becomes eventually stationary.

Notice that a word ordering o has the additional property that w >_o 1 for all w ϵ (X), because 1 >_o w implies 1 >_o w >_o w² >_o …, in contradiction to the well-ordering property.

The most straightforward candidate for a word ordering seems to be the lexicographic word ordering lex defined by w = x¡ · x¡ <_lex w’ = x · x if and only if w’ = ww” with w” ϵ (X) or i₁ < j₁ or i₁ = j₁, i₂ < j₂, etc. However, this ordering is neither compatible with multiplication nor a well-ordering, as the inequalities x2 >_lex x₂ and x₂x₁ >_lex x2x₁ >_lex · show. To construct a true word ordering, we have to modify it as follows.

Example 14.1.4. The length-lexicographic word ordering llex on (X) is defined as follows. Given two words w = x¡ … x_ik and w’ = x · x, we let w <_llex w’ if and only if l(w) < l(w’) or if both words have the same length and w <_lex w’.

It is easy to check that llex is in fact a word ordering. For instance, it satisfies ^x1 >llex ^x2 ^{and x2} >llex ^x2 ^{and x}1^x2 >llex ^x2^x1.

Another method to construct word orderings is to consider the given words as commutative terms in K[x₁, …,x_n], compare them using a term ordering, and break ties using lex. Further word orderings will be discussed in the next section.

In non-commutative polynomial rings there are several kinds of ideals. Let K be a field and X = {x₁,…, x_n} a set of letters.

Definition 14.1.5. Let I be a subset of K(X).

(1)  The set I is called a left ideal in K(X) if I is an additive subgroup of K(X) and if we have K(X) I c I.

(2)  The set I is called a right ideal in K (X) if I is an additive subgroup of K (X) and if we have I • K (X) c I.

(3)  The set I is called a two-sided ideal in K(X), or simply an ideal in K(X), if I is both a left and a right ideal in K (X).

For instance, the set of all polynomials in K(X) whose constant coefficient (that is the coefficient of the word 1) is zero forms a two-sided ideal in K (X). A general method to construct two-sided ideals can be obtained as follows.

Definition 14.1.6. Let S c K(X) be a subset.

(1)  The set

(S) = {f1S1g1 + … + f_rs_rg_r | r > 0, fi, gi ϵ K(X), s_t ϵ S}

is a two-sided ideal in K(X). It is called the ideal generated by S. In this case the set S is called a system of generators of (S).

(2)  An ideal I in K (X) is called finitely generated if there exists a finite subset S of K(X) such that I = (S).

Examples of finitely generated ideals in K (X) are the zero ideal (0) = {0}, the unit ideal K{X), principal ideals (f ) = {gfh | g, h e K(X)}, and the irrelevant ideal (x₁,…,x_n) which consists of all non-commutative polynomials having constant coefficient zero. Not every ideal in K(X) is finitely generated, as our next example shows.

Example 14.1.7. Let X = {x, y},andlet/be the two-sided ideal in K(X) = K(x, y) generated by S = {xy¹x | i > 1}. Then no generator xy’x of I is contained in the two-sided ideal (xyx, xy²x,…, xy^!-1x). Since every finite set of generators of I can be represented using finitely many elements of S, it follows that I is not finitely generated.

Given a word ordering o, the following definitions correspond to the analogous definitions for the commutative case.

Definition 14.1.8. Let o be a word ordering on (X), and let f = c₁w₁ + … + c_sw_s e K(X) {0} be a non-zero non-commutative polynomial, where c¡ e K {0} and where w¡ e (X) are words satisfying w₁ >_o w₂ >_o … >_o w_s.

(1)  The word Lw_o f ) = w₁ is called the leading word off.

(2)  The element Lc_o f) = c₁ is called the leading coefficient off.

(3)  We let Lm_o f) = Lc_o f) • Lw_o f ) and call it the leading monomial off.

(4)  Given a two-sided ideal I in K(X), the two-sided ideal

Lwo(I) = (Lwo(f ) I f e I {0})

is called the leading word ideal of I.

(5)  Given a two-sided ideal I in K(X), we also let O_o(I) = {w e(X)| w i Lw_o(I)}.

Note that we did not define the leading word and the leading coefficient of the zero polynomial. Leading words of polynomials satisfy a few simple rules.

Remark 14.1.9. Let o be a word ordering on (X), let w, w’ e (X), and letf, f ‘ e K(X) {0}.

(1)   If f + f = 0 then we have Lw_o (f + f) <_o max_o {Lw_o (f), Lw_o (f’)}.

(2)  We have Lw_o (wfw’ ) = w Lw_o (f) w’.

(3)  We have Lwo ff) = Lwo (f) Lwo (f’).

Our next example demonstrates that the leading word ideal of a two-sided ideal need not be finitely generated, even if the ideal is finitely generated. In particular, just as in the commutative case, the leading words of the polynomials in a system of generators of I do, in general, not generate the leading word ideal of I.

Example 14.1.10. Let I be the principal ideal in K(x, y) generated by f = x² − xy, and let o be a word ordering on (x, y) such that x >_o y. Then for all i > 1, the polynomials g¡ = xy’x − xyⁱ+¹ are contained in I, as the equality g_i+₁ = xy’f + g_;(y − x) and induction show. In particular, it follows that J = (xy^!x | i > 0) is contained in Lw_o (I). In fact, it is not difficult to verify that J equals Lw_o (I). (For instance, we could apply the Buchberger Procedure below to the set {f, g₁, g₂,…} and verify that it is a o-Gröbner basis of I.)

Thus the ideal I is generated by a single polynomial, but Lw_o (I) is not finitely generated.

Given a two-sided ideal I, the set O_o(I) is an order ideal in (X), that is, it is closed under the formation of subwords. This set plays a prominent role in the following noncommutative version of Macaulay’s Basis Theorem.

Proposition 14.1.11 (Macaulay’s Basis Theorem). Let o be a word ordering on (X), and let I be a two-sided in K (X). Then the residue classes of the words in O_o (I) form a K-basis ofK(X)/I.

Proof. First we show that these residue classes generate K(X)/I. For this it suffices to show that B = (O_o (I))_K + I equals K(X). Suppose it does not. Then there exists a non-zero polynomial f ϵ K(X) B having a minimal leading word with respect to o.

If this leading word is contained in Lw_o(I), there exists a polynomial g ϵ I such that Lw_o (f ) = w Lw_o (g) w’ for some w, w’ ϵ (X). But then the polynomial h = f − (Lc_o (f)/ Lc_o (g)) wgw’ continues to be contained in (X) B and has a smaller leading word than f, a contradiction.

It remains to consider that case that Lw_o(f ) is not in Lw_o(I). Hence this word is in O_o (I) andg = f − Lc_o (f) Lw_o (f) is contained in K(X) B and has a smaller leading word than f, contradicting the choice of f.

Finally, we prove linear independence. Suppose that there exists a polynomial f = c₁w₁ + … + c_sw_s ϵ I {0} such that c¡ ϵ K and w¡ ϵ O_o (I)for i = 1,…, s. Then one of the words W¡ is the leading word of f and contained in both O_o (I) and Lw_o (I), a contradiction again. □

Now we are ready to introduce the non-commutative version of Gröbner bases.

Definition 14.1.12. Let o be a word ordering on (X), and let I be a two-sided ideal in K (X). A set of polynomials G c I is called a o − Gröbner basis of I if we have Lw_o (I) = (Lwo(g) I g ϵ G {0}).

As we have seen above, non-commutative Gröbner bases may be infinite. Thus there can be no algorithm computing them in general. Nevertheless, we will see that there is an enumerative procedure. This is a procedure which computes the elements of a Gröbner basis one by one and has the property that the union of all computed noncommutative polynomials is a Gröbner basis. An important ingredient for this procedure is the non-commutative analogue of the Division Algorithm.

Proposition 14.1.13 (Non-Commutative Division Algorithm). Letf,g₁,…,g_s ϵ K(X) {0}, and let o bea word ordering on (X). Consider the following instructions.

(1)  Let q₁ = … = q_s = 0,r = 0 and h = f.

(2)  Repeat the following steps until h = 0. Then return (q₁,…, q_s) and r and stop.

(3)  Repeat the following step as often as possible.

(4)  Find the smallest i ϵ {1,…,s} such that Lw_o (g_i) is a subword of Lw_o (h). If such an i exists, write Lw_o (h) = w Lw_o (g_i)w’ with w, w’ ϵ (X), append the triple (Lc_o(h)/ Lc_o(g_i), w, w’) to q_i and replace hbyh − (Lc_o(h)/ Lc_o(g_i)) wg_iw’.

(5)  Replace r by r + Lm_o (h) and hbyh − Lm_o (h).

This is an algorithm which computes tuples q₁,…,q_s of triples (c_ij, w_ij, wj and r ϵ K(X) such thatf = xs₌₁ Zj cij- W¡¿- g w’- + r and such that the following conditions hold.

(1)  No word ofr is a multiple of any of the words in {Lw_o (g₁),…, Lw_o (g_s)}.

(2)  For all i, j we have w_ij Lw_o (g) wj <_o Lw_o f).

The proof of this Division Algorithm is completely analogous to the proof of Proposition 13.1.10. As above, we call the polynomial r returned as part of the output of the Division Algorithm the normal remainder of f with respect to G = (g₁,…,g_s) and denote it by NR_{o G}f).

The non-commutative analogues of critical pairs and S-polynomials are defined as follows.

Definition 14.1.14. Let G = (g₁,… ,g_s) be a tuple of non-zero elements of K(X).

(1)  For all i,j ϵ {1,…,s}, a quadruple (W¡, w-; w_;-, w-) of words in (X) is called an obstruction of g_i and g_j if we have (1/ Lc_o (g_i)) w_i Lw_o (g_i) w’¡ = (1/ Lc_o (g_j)) w_j • Lwo (gj)wj.

(2)  For i ϵ{1,…, s}, an obstruction of g_i andg_i is called a self-obstruction of g_i.

(3)  For i, j ϵ {1,…, s}, the set of all obstructions of g_i and gj is denoted by Obs(i, j).

(4)  For every obstruction w = (W¡, w.; w_;-, w-) in Obs(i, j), the non-commutative polynomial S_ij(w) = (1/ Lc_o (g¡)) w_ig_iw’_i − (1/ Lc_o (gj)) wg-wj is called the S-polynomial of w.

Using these definitions, we can now formulate Buchberger’s Procedure for enumerating non-commutative Gröbner bases. (Sometimes this is also called Mora’s Algorithm, although it is clearly no algorithm.)

Theorem 14.1.15 (Buchberger’s Procedure). Let o be a word ordering on (X), and let f₁,…,f_s ϵ K(X) be non-zero polynomials which generate a two-sided ideal I = (f₁,… ,f_s). Consider the following instructions.

(1)  Let G = (f₁,… ,f_s), and let B be the union of all sets Obs(i, j) such that 1 < i < j < s.

(2)  Repeat the following steps until B = 0. Then return G and stop.

(3)  Using a fair strategy, choose an obstruction w = (W¡, w.; w_;-, w-) ϵ B and remove it from B. (By a fair strategy we mean a strategy which ensures that every obstruction is eventually selected.)

(4)  Compute the S-polynomial Sj(w) and its normal remainder Sj(w) = NR_o>G(Sy). If Sj(w) = 0 then continue with step (2).

(5)  Increase s by one, append f_s = S»(w) to G, and append all sets Obs(i, s) such that 1 < i < s − 1 to B. Then continue with step (2).

This is a procedure which enumerates a o-Gröbner basis G of the ideal I. If the ideal I has a finite o-Gröbner basis, the procedure will stop after finitely many steps and return a finite o-Gröbner basis of I.

A proof of this theorem using the current notation is, for instance, contained in [Xiu]. The proof of the preceding theorem is based on the following characterization of noncommutative Gröbner bases.

Proposition 14.1.16 (Buchberger’s Criterion). Let o be a word ordering on (X), let f₁,…,f_s ϵ K(X) be non-zero polynomials which generate a two-sided ideal I = (f₁,… ,f_s), and letG = (f₁,… ,f_s). Then the following conditions are equivalent.

(1)  The tuple G is a o-Gröbner basis of I.

(2)  For every obstruction w ofG, we have NR_{o G}(Sj(w)) = 0.

Again a proof using the current notation can be found in [Xiu]. Notice that Bucherger’s Criterion implies that we can check in finitely many steps whether a given finite set of non-commutative polynomials is a Gröbner basis.

Let us apply the Buchberger Procedure in a concrete example.

Example 14.1.17. In the non-commutative polynomial ring Z₂(x₁,…,x₆), we consider the two-sided ideal I = (f₁,f₂) generated byf₁ = x₃(x₁x₂)³ + x₄(x₁x₂)² + x₃ + x₄ andf₂ = (x₂x₁)³x₅ + (x₂x₁)²x₅ + x₅ + x₆. Using the word ordering o = llex, we have Lw_o (f₁) = x₃(x₁x₂)³ and Lw_o f₂) = (x₂x₁)³x₅. Let us follow the steps of the Buchberger Procedure.

1.  Let G = (g₁, g₂)whereg₁ = f₁ and g₂ = f₂.LetB = Obs(1,1) u Obs(2,2) u Obs(1,2). The sets Obs(1,1) and Obs(2,2) contain only obstructions without overlap, i.e., obstructions derived from leading words Lw_o (g), Lw_o (gj) without a word w such that Lw_o (gi) ends in w and Lw_o (gj) starts with w. The set Obs(1,2) contains obstructions of three types:

(i) obstructions w₁ = (1,x₁x₅;x₃x₁,1), w₂ = (1,x₁x₂x₁x₅;x₃x₁x₂x₁,1), and w₃ = (1, (x₁x₂)²x₁x₅;x₃(x₁x₂)²x₁x₅, 1)

(ii) all obstructions (1, w(x₂x₁)³x₅;x₃(x₁x₂)³w, 1) with a word w ϵ (X)

(iii) all obstructions ((x₁x₂)³x₅w, 1; 1, wx₃(x₁x₂)³) with a word w ϵ (X)

4.  For all obstructions w in Obs(1,1) u Obs(2,2), we get NR_o>g(S¡¡(w)) = 0.

4.  For the obstruction w₁, we get NR_o>G(S₁₂(w₁)) = x₃x₁x₆ + x₄x₁x₅.

5.  We append g₃ = x₃x₁x₆ + x₄x₁x₅ to G and update B.

4.  For w₂, we get NR_{o G}(S₁₂(w₂)) = x₃x₁x₂x₁x₆ + x₄x₁x₂x₁x₅.

5.  We append g₄ = x₃x₁x₂x₁x₆ + x₄x₁x₂x₁x₅ to G and update B.

4.  For w₃,we get NR_{o >G}(S₁₂(w 3) = x₃(x₁x₂)²x₁x₆ + x₄(x₁x₂)²x₁x₅.

5.  Weappendg₅ = x₃(x₁x₂)²x₁x₆ + x₄(x₁x₂)²x₁x₅ to GandupdateB.

4. For the obstructions w of type (ii) and (iii), we get NR_o>G(S₁₂(w)) = 0.

4.  For all obstructions w in Obs(i, j) with j ϵ {3,4,5} and 1 < i < j, we get NRo ¿(Sj(w)) = 0.

2.  The procedure stops and returns G = (g₁,… ,g₅).

Altogether, the tuple G = (g…, g₅)isa o-Gröbner basis of I.

One important application of the Buchberger Procedure is the following Ideal Membership Test for two-sided ideals in K(X):

Corollary 14.1.18. Given a o-Gröbner basis G of a two-sided ideal I in K(X) andf ϵ K(X), we havef ϵ I if and only if NR_{o G}(f) = 0.

Proof. Clearly, if NR_{o G}(f) = 0 then we can collect the reductions and arrive at a representation of f as an element of the ideal generated by G, i.e., as an element of I. Conversely, if we have f ϵ I, then the normal remainder NR_{o G}(f) is also contained in I. It follows that it has to be zero, since otherwise its leading term would be in Oo (I) = (X)Lwo (I).

The Buchberger Procedure can be applied to some problems for finitely presented groups introduced in Section 9.8. For this purpose, we need to introduce the following ring.

Definition 14.1.19. Let G be a group and K a field. Then the K-vector space K[G] = ©_geG K • g has a natural ring structure given by the K-linear extension of the multiplication in G. The resulting ring is called the group ring of G over K.

In other words, for two elements £_geG a_gg and £_geG b_gg of K[G], we let

where only finitely many coefficients a_gb_h are non-zero.

If G = (x₁,…,x_n; r₁ = … = r_m = 1) is a finitely presented group, we can represent the group ring over K by

K[G] = K(xi, …,Xn,yi,.. .,yn)/(xy_; − 1,yx − 1,rj − 1 | i =1… n,j =1… m).

Here the indeterminates y represent the inverses of the residue classes of the elements x_{ and the relators r_t have to be written as words in x_;, y_;.

Remark 14.1.20. Let G = (x₁,…, x_n; r₁ = … = r_m = 1) be a finitely presented group, and let w be a word in the letters {x₁,…,x_n,y₁,…,y_n}, where yi represents x,”¹. The word problem in G asks us to decide effectively whether w represents the identity element of G.

The following instructions provide a semi-decision procedure for the word problem in G which is based on Buchberger’s Procedure. Here “semi-decision” means that the procedure will terminate and give the correct answer if w represents the identity element of G. However, if the correct answer is “no”, the procedure terminates and gives the correct answer only if the ideal defining K[G] has a finite Gröbner basis with respect to the chosen word ordering. If the Gröbner basis is infinite, the procedure will run forever and never produce an answer.

(1)  Consider the non-commutative polynomial ring K(x₁,…,x_n,y₁,…,y_n) and the two-sided ideal I defining K[G] given above. Let H be the stated tuple of generators of I. Choose a word ordering o.

(2)  Compute NR_oh(w). If the result is zero, return YES and stop.

(3)  Run one iteration of the Buchberger procedure, starting with the system of generators H. Afterwards, update H to the resulting partial Gröbner basis.

(4)  If we have B = 0 in the Buchberger Procedure, i.e., if the computed tuple H is indeed a Gröbner basis of I and if NR_oh(w) = 0, return NO and stop. Otherwise, continue with step 1.

Recall that the Buchberger Procedure enumerates a o-Gröbner basis of I. If w represents the identity element, the normal remainder of w with respect to this Gröbner basis is zero. In this reduction to zero only finitely many Gröbner basis elements are involved. Therefore, if we repeat steps 1 and 2 often enough, all necessary Gröbner basis elements will have been found and the procedure stops with the correct answer. Moreover, if the Buchberger Procedure produces a finite Gröbner basis, the answer is correct by the above Ideal Membership Test.

14.2 Elimination and its Applications

In the following we continue to use the setting of the last section. We have a field K, a set of letters X = {x₁,.. .,x_n}, and the non-commutative polynomial ring K(X). Elimination is an important technique in computer algebra and will be essential for Gröbner basis cryptography. The following definition provides the necessary terminology.

Definition 14.2.1. Let L c X be a subset of the given set of letters, and let X = X L.

(1)  A word ordering o on (X) is called an elimination ordering for L, if every polynomial f ϵ K(X) {0} such that Lw_o f) ϵ (X) satisfies f ϵ K(X).

(2)  Given a two-sided ideal I c K(X), the ideal ⁷ = I n K(X) is called the elimination ideal of I with respect to L.

It is clear that ⁷ is a two-sided ideal in K(X). It consists of all non-commutative polynomials in I which do not involve the letters from L. Let us show that elimination orderings exist.

Example 14.2.2. Let I ϵ {1,…, n}, and let L = {x₁,.. .,x_f}. We define a word ordering elim on (X) as follows. Given a word w ϵ (X) and a letter X¡, the number deg_x (w) is the number of occurrences of the letter X¡ in w. Given two words w₁, w₂ ϵ (X), we let w₁ <_elim w₂ if and only if there exists an index j ϵ {1,…, n} such that deg_x.(w₁) = degx (w2) for i < j and deg_x_(w < deg_Xj (w2), or if deg_Xi (w = deg (w2) for i = 1,…, n and w1 <iex w2.

It is easy to check that elim is an elimination ordering for L, independent of the actual value of I.

For instance, inX = (x_1; x₂> we havex₁ >_elim xandx₁x. <_elim X³XjandX >_elim XXj.

In the following we let L c {1,…, n| and .X = X L. The property of a being an elimination ordering for L can be rephrased by saying that if the letters of L do not occur in a word w ϵ (X>, they do not occur in any word w’ ϵ (X> such that w’ <_a w. The following lemma is easily verified and will be used in the main theorem below.