Relations in Rings
Commutativity Theorems

 

Wavrik, John J,  Commutativity Theorems:  Examples in Search of Algorithms

 In Proceedings of the 1999 International Symposium on Symbolic and Algebraic Computation (1999), S. Dooley, ed, 31-36.

 

      This work concerns a collection of theorems in non-commutative ring theory. These assert conditions under which a ring is commutative.  The hypotheses usually take the form of one or more polynomial identities on R, together with side conditions (e.g. the ring has a 1 or  there are no non-zero nilpotents)  The desired conclusion is that the identity xy-yx holds.   A Simple Example

 

     The strategy Herstein has in mind in his undergraduate book is to use various substitutions in the given identities and to apply the growing family to identities to simplify expressions obtained in this way.[1]  In the paper we explore the possibility of automating these computations.  More information is found on the following pages

 

Simplification and Grobner Technology:

 The simplification process used in a computational approach to these problems is similar to the reduction process central to the Gröbner Basis Theory. It can be viewed as simplification by the use of rewrite rules.[2]  In both the commutative and non-commutative case,  the reduction process provides a computational test for ideal membership:  an element f is in the ideal I if and only if f reduces to zero using a Gröbner Basis for I.  An essential component of the method is an algorithm for producing a Gröbner Basis from an arbitrary basis.

For the current work, it is necessary to use a version of the Gröbner Basis Algorithm which not only uses non-commutating variables, but also integer coefficients.  I developed a modification of the Mora algorithm (for non-commuting variables) using a method for handling integer coefficients developed by Buchberger (for the commutative case). The algorithm uses characteristic pairs, rather than S-Polynomials. It has been found necessary to extend the notion of “match” to allow pairs which would not be considered in the case of coefficients in a field. Further modifications were made to increase the efficiency of the algorithm.

Ideals and T-Ideals

A commutativity theorem asserts that xy – yx is a consequence of given starting identities. The set of consequences of a set of identities has the same arithmetic closure properties of an ideal – but, in addition, it is closed under the operation of substitution of polynomials for its variables.  Non-commutative ring theorists call an ideal which has this additional closure property a T-ideal.

 

This work is an attempt to investigate a computational test for membership in a T-ideal. In other words, we want a computational test to determine if a polynomial identity is a consequence of an initial set of identities. Commutativity theorems are a special case (we wish to see if xy – yx is a consequence of the identities given in the hypothesis).

Commutativity Theorems

I was able to prove a number of commutativity theorems by choosing, in each case, a collection of substitutions. These give a set of generators for a subideal of the T-ideal of all consequences of the starting identities.  The modified Mora Algorithm was used to produce a distinguished basis for the relations (called an R-basis) which was then used to test membership of xy-yx in the subideal.

 

The non-algorithmic step in this process is the most delicate: the choice of the starting collection of substitutions.  The proofs are very sensitive, both in outcome and execution time, to the choice of initial substitutions[3]. This work provides a varied collection of examples for examining reduction processes in computational non-commutative ring theory.  


Some Other Commutativity Theorems

The following commutativity theorems were proved in the paper:

Theorem 1:
  If a2 = a "aĪR then R is commutative.

Theorem 2:
  If R is a ring with 1 for which  (ab)2 = a2b2 "a,bĪR then R is commutative.

Theorem 3:
  If R is a ring with no nilpotents for which  (ab)2 = a2b2 "a,bĪR then R is commutative.

Theorem 4:
  Let R be a ring with 1 for which 2x = 0 Ž x=0. If (ab)2 = (ba)2 "a,bĪR then R is commutative.

Theorem 5:
  Let R be a ring with no nilpotents for which  (ab)2 = (ba)2 "a,bĪR then R is commutative.

Theorem 6:
  Let R be a ring in which  a3 = a "aĪR then R is commutative

Theorem 7:
  Let R be a ring in which  a4 = a "aĪR then R is commutative

Theorem 8:
  Let R be a ring which  a2 = a Ī Z(R) "aĪR (where Z(R) is the center of R) then R is commutative

Theorem 9:
  Let R be a ring which  a3 = a Ī Z(R) "aĪR (where Z(R) is the center of R) then R is commutative

Current Work

Several new commutativity theorems have been proved since the ISSAC paper. Quicker proofs have been found for some theorems in the paper.

 

Tools are being created for examining the execution of the algorithms and for gathering statistics about the execution. The most obvious needs at this time are:

 

  1. To develop heuristics for the choice of starting substitutions.
  2. To improve the efficiency of the algorithm.
  3. To rewrite the code including experimental features that have proven useful.
  4. To consider preparing the research software for dissemination.

 

 

 

 

 

 

    Herstein presents some problems of this sort in his undergraduate text Topics in Algebra and in his Carus monograph Noncommutative Ring Theory.  Further examples are in the literature. The simplest example is:

 

Theorem:  If  R is a ring in which x2 = x for all x, then R is commutative.

Proof:      We have x+y = (x+y)2 = x2 + xy + yx + y2
using x2 = x and y2 = y this reduces to xy + yx = 0.
but x = x2 = (-x)2 = -x. so  xy – yx = 0.

 

 

 

 

 

---

 

Modification of the Mora Algorithm

 

      The heart of the Gröbner basis technology is a reduction algorithm similar to a step in division.  We order the terms in the polynomial ring. Suppose cW is a term in a polynomial f. Let g be a polynomial whose leading term is aX.  Suppose X is a subword of W – so W = LXR.  If the coefficients lie in a field, we can reduce f by g by replacing f by f-(c/a)LgR.  This replaces cW by terms of lower order.

 

    We must modify this in case of integer coefficients.  In this case, for example, we cannot expect to eliminate f = 3x by using g=2x.  We can, however, expect to replace 3x by a smaller term (or sum of terms).  This is accomplished by ordering the coefficients.  We order the integers using:

 

                           0 < -1 < 1 < -2 < 2 ….

 

And then we order terms by

 

                cW < dX   if  either  W < X 

                                      or         W=X and c < d.

 

With the setup as in the first paragraph, we reduce f by g by replacing f by f‑qLgR where q is chosen so that  c-aq is as small as possible in the ordering of integers.

 

   The basis algorithm is similar to the Mora algorithm.  Given f1 and f2  we find, if possible, aX where X is a “match” of the leading monomials and a is chosen so that it reduces non-trivially by the leading coefficients.  We reduce pi = aX - qiLifiRi by elements in the current basis. This amounts to reducing aX in two different ways. The reduction of p1-p2 is added to the basis if it is non-zero.

 

 

 

 


[1]     In his Carus monograph, Noncommutative Rings, Herstein shows how general versions of some commutativity theorems can be obtained using the structure theory for rings. 

[2]      This is the point of view taken in my earlier work (joint with Helton) on simplification of expressions that arise in operator theory.

[3]        If the starting set is not large enough, we can see long computation times, some infinite bases, and ideals which do not contain xy-yx.  For this reason an attempt to select substitutions dynamically has not been successful. If, on the other hand, the starting set is too large, time is lost on computations which do not have direct bearing on the problem.