COMPUTATIONS WITH FINITE PREES

ROBERT H. GILMAN

1. Introduction

It is well known that most questions about finitely presented groups are undecideable but that the word problem and conjugacy problem are solvable for presentations satisfying small cancellation conditions. We will consider another class of presentations which are amenable to computation. The basic idea is simple: Start with a finite multiplication table and take as relations all products defined in the table. The table is allowed to have blanks, so that it is really a partial multiplication table. It is straighforward to use Tietze transformations to change any finite presentation into one given by such a table, and with more Tietze transformations one can insure that the multiplication table satisfies the following definition.

Definition 1.1. A pree is a set P with a partial binary multiplication satisfying the conditions listed below.

1. There is an identity element, and every element has an inverse.

2. The multiplication obeys the following associative law. If the products ab = x and bc = y are defined, then xc is defined if and only if ay is defined, and the latter two products are equal when defined.

It is not hard to show that in a pree inverses are unique. Further if ab = c, then a^{−1}c = b etc. Products may be thought of as triangles. The triangle in Figure 1 represents the six products obtained by reading

Figure 1. A product ab = c. the edge labels around the boundary in both directions starting from each of the vertices. If any of these six products is defined in a pree, then all are.

[figure: c; a; b] Prepared for the Meeting on Computational Group Theory, Oberwolfach, June, 1997.

The associative law is equivalent to the statement that if three triangles in a pree P fit around a common vertex as in Figure 2, then the perimeter is also a valid triangle in P. If the set of defined prod-

[figure]

Figure 2. The associative law.

ucts ab = c is thought of as a collection of reductions ab → c, then the associative law can also be interpreted as a sort of local confluence condition.

Definition 1.2. The universal group of a pree P is the group U(P) with generators P and relators abc^{−1} for every product ab = c defined in P.

From the preceding discussion we see that every finitely presented group is the universal group of a finite pree.

Prees were invented by Reinhold Baer [2] in his study of the amalgamated free product construction. The prototypical pree is an amalgam of two groups with the induced partial multiplication. The name pree is due to John Stallings [15]. A class of prees called pregroups plays a role in his work on groups with more than one end [14]. Other authors who have worked on prees are A. H. M. Hoare [6], Seymour Lipschutz and Harvey Kushner [7, 8, 9, 10], and Frank Rimlinger [13]. Hanna Neumann’s dissertation [12] on embedding amalgams should also be mentioned.

2. Virtually Free Groups

Since every finitely presented group is the universal group of a finite pree, we will not make much progress by studying all finite prees. Instead we distinguish subclasses which satisfy certain axioms. The first axioms were introduced in connection with the embedding problem. Considering prees as generalizations of amalgams we naturally ask when the canonical pree-morphism π : P → U(P) from a pree P to its universal group is an embedding.

Theorem 2.1. The question of whether or not a finite pree embeds in its universal group is undecidable.

This theorem is a special case of a result of Trevor Evans [3] which says that if the embedding problem is solvable for a class of finite partial algebras, then the word problem is solvable for the corresponding class of algebras.

The canonical pree-morphism π : P → U(P) will be injective and the partial multiplication in P will be the one induced by the injection if P satisfies Axiom S, illustrated in Figure 3. Axiom S is actually an

Figure 3. Axiom S.

infinite sequence of axioms A(n) for n = 4, 5, . . .. Axiom A(n) says that if n triangles in P fit around a common vertex, then there exist two successive sides of the perimeter which form two sides of a valid triangle in P.

By work of Muller and Schupp [11] and Autebert, Boasson, and Senizergues [1] we know something about the universal groups of Sprees.

Theorem 2.2. The following conditions are equivalent.

1. G is the universal group of a finite pree satisfying Axiom S.

2. G has a free subgroup of finite index.

3. G admits a length reducing monadic presentation confluent at the identity.

4. The language of all words defining the identity in G is context-free.

This result is a basis for computation with virtually free groups. Consider the following simple example from [5].

Example 2.3. G = ⟨e, f | ff, efef⟩.

Start by converting the presentation to one with all relators of length 3. To accomplish this goal we need two new generators, E, the identity element, and g = ef. Inverses for e, f, g are also necessary. We obtain the multiplication table presentation in Table 1.

E e e^{−1} f f^{−1} g g^{−1}
E E e e^{−1} f f^{−1} g g^{−1}
e e  E g
e^{−1} e^{−1} E
f f  E E
f^{−1} f^{−1}  E
g g f^{−1}  E
g^{−1} g^{−1}  E

Table 1. A multiplication table presentation for G.

It may happen that coincidences appear. One generator will be visibly equal to another. These coincidences are dealt with as in coset enumeration. In our case imposing the associative law on Table 1 leads to the coincidences f = f^{−1}, g = g^{−1} and yields the pree P of Table 2.

E e e^{−1} f g
E E e e^{−1} f g
e e  E g
e^{−1} e^{−1} E  f
f f  E e^{−1}
g g f^{−1}  e E

Table 2. The Pree P.

To check Axiom S construct a directed graph Γ with vertices the non-identity elements of P and with an edge labeled by b ∈ P from vertex a to vertex c whenever a = bc. Axiom S holds if and only if the label of every cycle in Γ is reducible. That is, if a_{1} ⋯ a_{n} is the label of a cycle, then some product a_{i}a_{i+1} or a_{n}a_{1} is defined in P. It suffices to check the labels of the simple cycles of Γ. In the case of the pree P of Table 2 we obtain the graph of Figure 4 from which it follows that P is an S-pree and G is virtually free.

If a pree P fails the test, we can add the labels of the offending simple cycles to the presentation and begin again. [5] gives some results of a computer implementation of this procedure and also shows how to use

[figure: g; e; f; g; f; g; f; e; e^{−1}]

Figure 4. The Graph Γ.

an S-pree presentation for a group G to solve the word and order problems, determine the cardinality of the group, and find representatives of the conjugacy classes of elements of finite order.

3. Word Hyperbolic and Biautomatic Groups

Gersten and Short [4] have shown that groups satisfying the nonmetric small cancellation conditions C(6) or C(4) and T(4) or C(3) and T(6) are biautomatic. For a pree the condition C(3) is vacuous, and T(6) says that if fewer than six triangles fit around a common vertex, then the perimeter is not freely reduced. Thus T(6) implies that axioms A(4) and A(5) hold. Most of the argument of Gersten and Short applies verbatim to this more general situation. The situation really is more general because some prees satisfying these axioms have universal groups which do not admit small cancellation presentations.

Theorem 3.1. If P is a finite pree satisfying Axioms A(4) and A(5), then P embeds in U(P), and U(P) is biautomatic.

As in the preceding section we can turn an arbitrary finite presentation for a group G into a pree P whose universal group is isomorphic to G and test if P satisfies Axioms A(4) and A(5). If P fails the test, then each instance of failure may be resolved by the addition of new elements and products to P and the test repeated. My student Chih-Huei Wang is using a computer implementation of this procedure in her investigation of Artin groups.

Adding Axiom A(6) to Axioms A(4) and A(5) yields a class of prees whose universal groups are word hyperbolic. By taking more elaborate axioms of the same type we can characterize the class of word hyperbolic groups.

Theorem 3.2. Let G be δ-hyperbolic with δ ≥ 1. Take as new generators all group elements represented by words of length at most 144000δ. Let P be the pree consisting of these generators. Then G is isomorphic to the universal group of P, and P satisfies twelve axioms. Conversely if P is any pree satisfying these axioms, then its universal group is word hyperbolic.

Theorem 3.2 could be the basis of a procedure which tests if a finitely presented group is word hyperbolic by trying to change the presentation into a pree satisfying the twelve axioms. A more plausible possibility is to use a computer to search for word hyperbolic groups by having it construct random examples of prees of this type. Random examples might help resolve some of the open questions about word hyperbolic groups, and there does not seem to be any other method capable of producing all word hyperbolic groups each with with positive probability.

References

[1] J.-M. Autebert, L. Boasson, and G. Senizergues, Groups and NTS languages, J. Computer and System Science, 35 1978, 243-267.

[2] R. Baer, Free sums of groups and their generalizations II, III, American J. Mathematics 72 1950, 625-670.

[3] T. Evans, Embeddability and the word problem, J. London Math. Soc. 28, 1953, 76-80.

[4] S. Gersten and H. Short, Rational subgroups of biautomatic groups, Annals of Math. 134 1991, 125-158.

[5] R. Gilman, Verifying that a group is virtually free, Int. J. of Algebra and Computation, 1 1991, pages 339-351.

[6] A. H. M. Hoare, On generalizing Stallings’ pregroup. J. Algebra 145, 1992, 113–119.

[7] H. Kushner and S. Lipschutz, A generalization of Stallings’ pregroup, J. Algebra, 119, 1988, 170–184.

[8] , On embeddable prees. J. Algebra, 160, 1993, no. 1, 1–15.

[9] S. Lipschutz, Note on generalizing pregroups, Publ. Inst. Math. (Beograd) (N. S.) 45 1989, 77-80.

[10] , Generalizing the Baer-Stallings pregroup, The mathematical legacy of Wilhelm Magnus: groups, geometry and special functions (Brooklyn, NY, 1992), 415–430, Contemp. Math., 169, Amer. Math. Soc., Providence, RI, 1994.

[11] D. E. Muller and P. E. Schupp, Groups, the theory of ends and context-free languages, J. Computer and System Sciences 26 1983, 295–310.

[12] H. Neumann, Generalized free products with amalgamated subgroups. Amer. J. Math. 70, 1948, 590-625.

[13] F. S. Rimlinger, Pregroups and Bass-Serre theory, Memoirs of the A. M. S., 361 , 1987.

[14] J. Stallings, Group Theory and Three Dimensional Manifolds, Yale University Press, New Haven and London 1971.

[15] , Adian groups and pregroups, in Essays in Group Theory, S. M. Gersten ed., M. S. R. I. Publications 8, Springer Verlag, 1987, 321-342.

Department of Mathematical Sciences, Stevens Institute of Technology, Hoboken, New Jersey

E-mail address: rgilman@stevens-tech.edu