Quotient Tests and Gröbner Bases

Martin Kreuzer FB Mathematik Univ. Dortmund Dortmund, Germany

Alexei Myasnikov Dept. of Mathematics McGill University Montreal, Canada

Gerhard Rosenberger FB Mathematik Univ. Dortmund Dortmund, Germany Alexander Ushakov Graduate Center CUNY New York, USA

March 15, 2005

Given a finitely presented group G = ⟨X; R⟩, the word problem asks to decide effectively whether a given word in the free group w ∈ F (X) represents the identity element in G or not. Another important computational problem is to check effectively whether G is finite or not. For the ”No” parts of these problems, we can use quotient tests. For instance, for the ”No” part of the word problem, we can devise a procedure which proves w ≠_{G} 1 or returns "Dont't know" if we have an effectively computable group homomorphism φ : G ⟶ H and if the ”No” part of the word problem is decidable in H.

To find a suitable group homomorphism φ : G ⟶ H, we use universal linear representations of G. Special cases of such representations have been used in [12] and [2] for other purposes. Here the universal linear representation ϱ : G ⟶ SL(n, Q_{R}) is constructed as follows. We map each generator x_{k} of G to a matrix of indeterminates (a_{i,j}^{(k)}). In the polynomial ring P having these indeterminates, we form the ideal I_{R} generated by the entries of the images of the relators in R and by the polynomials det(a_{i,j}^{(k)}) − 1. Letting Q_{R} = R/I_{R}, we obtain a well-defined linear representation ϱ : G ⟶ SL(n, Q_{R}) which maps x_{k} to the residue class of (a_{i,j}^{(k)}).

At this point Gröbner bases come into play: if we succeed in computing a Gröbner basis of the ideal I_{R}, we can check effectively whether the matrix of polynolmials ϱ(w) defines the identitiy element in ϱ(G). Moreover, we have several methods available for showig that ϱ(G), and hence G, is an infinite group. For example, Algorithm 6.2 determines the minimal polynomial of a matrix in a matrix ring over an affine algebra. If we find a word w such that the minimal polynomial of ϱ(w) is zero or does not divide a polynomial z^{m} − 1, the element ϱ(w) has infinite order.

In the last two sections we apply these new techniques to several examples. First we study two problems from the Kourovka Notebook [14]. We show the the universal linear representations of size 2 × 2 of the groups G_{i} = ⟨a, b; a^{i} = 1, ab = b^{3}a^{3}⟩ are commutative and finite for i = 5, 7, 9, 11. This makes is plausible that this could be true for the groups themselves, but is it known that G_{9} is infinite. Next we prove that a ≠ 1 in the groups H_{i} = ⟨a, b; a^{i} = 1, ababa = b^{2}ab^{−1}ab⟩ for i = 5, 10, 15, 20, and that ϱ(a) = 1 in the universal linear representations of size 2 × 2 of these groups for the other groups H_{i} with i ≤ 20. Our third collection of examples are some groups of deficiency zero mentioned in [4]. For these groups, we can show that their universal linear 2×2 representations are all isomorphic to (ℤ/(3))^{3}. In fact, the ideals I_{R} turn out to be identical. However, the Gröbner bases of the ideals corresponding to the universal linear representations of size 3 × 3 are too difficult to compute at present.

In the last section we apply our methods to the classification of finite generalized triangle resp. tetrahedron groups in [6] and [10], resp. in [20]. For generalized triangle groups, this classification is complete. We show some methods for checking individual cases. For generalized tetrahedron groups, there are five groups for which it is not known whether they are finite or not. Unfortunately, as our Proposition 8.3 and the companying computer calculations show, we cannot expect to prove infinitude for these groups using their universal linear representation of size 2 × 2, and for size 3 × 3 we were only able to compute truncated Gröbner bases and deduce some partial results.

It is clear that there is ample room for optimizing the Gröbner basis computations necessary for our algorithms. In view of the ease with which we were able to get new results for some difficult problems, we are optimistic that the Gröbner bases methods we discuss will prove to be useful tools in computational group theory.

Contents

1 The Word Problem in Groups 3

2 Quotient Tests 4

3 Linear Representations of Groups 5

4 Universal Linear Representations 7

5 Linear Quotient Tests for WP 9

6 Linear Quotient Tests for Infinitude 10

7 Some Examples 12 7.1 From the Kourovka Notebook (1) . . . . . . . . . . . . . . . . 13 7.2 From the Kourovka Notebook (2) . . . . . . . . . . . . . . . . 13 7.3 Some Groups of Deficiency Zero . . . . . . . . . . . . . . . . . 14

8 Classification of Finite Generalized Triangle and Tetrahedron Groups 15

1 The Word Problem in Groups

In this section we briefly discuss the word problem in groups. For a more detailed discussion of decision problems for groups we refer the reader to the surveys [1], [15], and [16].

Let X be a set. Denote by X^{−1} = {x^{−1} | x ∈ X} the set of formal inverses of elements of X. The map x ↦ x^{−1}(x ∈ X) naturally extends to an involution on the set X^{±1} = X ∪ X^{−1}, where we define (x^{−1})^{−1} = x. Denote by (X^{±1})^{∗} the free monoid with basis X^{±1} viewed as the set of all words (including the empty word ε) in the alphabet X^{±1} with concatenation as multiplication. A word w ∈ (X^{±1})^{∗} is called reduced if it does not have subwords of the type yy^{−1} for y ∈ X^{±1}. It is easy to see that the rewriting system

yy^{−1} → ε, (y ∈ X^{±1})

is complete, so for every word w ∈ (X^{±1})^{∗} there exists a unique reduced word w̄ which can be obtained from w by cancellations yy^{−1} → ε.

Let F (X) be the set of all reduced words in X^{±1} with multiplication · given by concatenation and subsequent reduction. It is known that F (X) is a free group with basis X.

Let R ⊆ F (X) and let gp_{F} (R) be the normal closure of R in F (X). Then we write

G = ⟨X; R⟩  (1)

for the group G ≅ F (X)/gp_{F} (R). In this setting the set X is called a set of generators of G, the set R is called a set of relators of G, and the pair P = ⟨X; R⟩ is called a presentation of G. A presentation P = ⟨X; R⟩ is finite if the sets X and R are both finite. A group G is called finitely presented if G has a finite presentation G = ⟨X; R⟩. By η : F (X) → G we denote the canonical homomorphism from F (X) onto its quotient G = F (X)/gp_{F} (R).

A finite presentation ⟨X; R⟩ has decidable Word Problem if the set gp_{F} (R) is recursive. Equivalently, the Word Problem (WP) is decidable in G (with respect to the presentation G = ⟨X; R⟩) if for every word w ∈ F (X) one can effectively decide whether η(w) = 1 in G or not. Sometimes instead of η(w) = 1 in G we write w =_{G} 1, or simply w = 1. It is not hard to see that if WP is decidable in G with respect to one finite presentation then WP is decidable in G with respect to every finite presentation of G. Therefore, we often refer to G as a group with decidable word problem without mentioning any particular presentation.

It is convenient to partition the word problem over a group G = ⟨X; R⟩ into two parts: the ”Yes” part and the ”No” part:

WP_{Y es} = {w ∈ F (X) | w =_{G} 1}
WP_{No} = {w ∈ F (X) | w ≠_{G} 1}

We consider partial decision algorithms for each part separately. Here a procedure A is said to be a partial decision algorithm for the ”Yes” (resp. ”No”) part in G if for every input word w ∈ F (X) the procedure A halts and returns "Yes" (resp. "No") only if w ∈ WP_{Y es} (resp. w ∈ WP_{No}), otherwise A either does not stop, or A stops and returns "Don't know".

2 Quotient Tests

In this section we discuss quotient tests. They yield partial decision algorithms for the ”No” part of the word problem. Quotient tests provide one of the key methods for designing decision algorithms for groups. They are based on the following simple idea:

Let φ : G → H be a group homomorphism from G to a group H. Then the following implication holds for every element u ∈ F (X):

φ(u) ≠_{H} 1 ⟹ u ≠_{G} 1.

Now suppose that the group H is provided with a generating set Y such that WP is decidable in H with respect to Y. Suppose also that the homomorphism φ is given by the images of elements x ∈ X which are described by some words u_{x} ∈ F (Y), i.e. for which we have u_{x} =_{H} φ(x). In this case one can design a partial decision algorithm A for the ”No” part of WP in G as follows:

Given a word w ∈ F (X), the procedure A performs the substitution σ : x → u_{x} in w and applies the decision procedure B for WP in H to the resulting word σ(w). If B stops on σ(w) and says ”No”, then A stops and says ”No”, in all other cases A does not stop. The procedure A is called the quotient test for WP in G with respect to the homomorphism φ : G → H.

The computational complexity of general quotient tests in groups has been studied recently in [7] and [8].

3 Linear Representations of Groups

A homomorphism ϱ : G → GL(n, K) from a group G to the general linear group GL(n, K) of invertible matrices of size n × n over a commutative unitary ring K is called a linear representation of G. Usually, the ring K is assumed to be a field, but we do not not need this assumption here. Similarly, one can introduce linear representations of G in the special linear group SL(n, K). For purely technical reasons we usually prefer linear representations in SL(n, K), even though everything goes through for representations in GL(n, K), or even more generally, in any linear algebraic group.

Let G = ⟨X; R⟩ be a finite presentation of a group G, where X = {x_{1}, …, x_{s}} and R = {r_{1}, …, r_{t}} ⊆ F (X). Every linear representation

ϱ : G → SL(n, K)

is completely determined by the set ϱ(X) = {ϱ(x_{1}), …, ϱ(x_{s})} of images of the elements of X in SL(n, K). Letting ϱ(x_{k}) = (a_{i,j}^{(k)}) ∈ SL(n, K), we have

x_{k} ⟼^{ϱ} (\begin{matrix}a_{(1,1)}^{(k)} & … & a_{(1,n)}^{(k)} \\ a_{(n,1)}^{(k)} & … & a_{(n,n)}^{(k)} \end{matrix})  (2)

Since ϱ(r) = 1 in SL(n, K) for every r ∈ R, the elements a_{i,j}^{(k)} ∈ K form a solution of the following system S_{R} = 0 of polynomial equations with integer coefficients:

\begin{matrix}det(ϱ(x)) − 1 = 0 & (x ∈ X); \\ (ϱ(r))_{i,j} − δ_{i,j} = 0 & (r ∈ R, i, j = 1, …, n) \end{matrix}  (3)

where (ϱ(r))_{i,j} is the (i, j) entry of the matrix ϱ(r), viewed as a polynomial in the entries of the matrices ϱ(x) (x ∈ X). Here we let δ_{i,j} = 1 if i = j and δ_{i,j} = 0 otherwise.

Clearly, every solution a = (a_{i,j}) ∈ K^{sn^{2}} of the system S_{R} = 0 gives rise to a linear representation ϱ_{a} : G → SL(n, K). Hence linear representations of a finitely presented group G = ⟨X; R⟩ in SL(n, K) can be viewed as K-ra-tional points of the variety V_{R} in K^{sn^{2}} defined by the system S_{R} = 0. This variety is called the variety of representations of G. For a detailed discussion of this variety, see [12].

Remark 3.1. (Optimization of the System S_{R} = 0) Computationally, it is more advantageous to consider a slightly modified version of the system S_{R} = 0 defined in (3).

Suppose we have an equation r = r′∘r′′ in G. Since ϱ is a homomorphism, it follows that ϱ(r) = 1 in SL(n, K) if and only if ϱ(r′)ϱ(r′′) = 1, and this is equivalent to ϱ(r′) = ϱ((r′′)^{−1}). Therefore the system S_{R} = 0 is equivalent to the system obtained from S_{R} by removing the equations corresponding to ϱ(r) = 1 and adding equations corresponding to ϱ(r′) = ϱ((r′′)^{−1}).

Notice that the polynomial equations corresponding to ϱ(r′) = ϱ((r′′)^{−1}) have smaller degree than those coming from ϱ(r) = 1. The smallest degrees will be obtained when the relators in R are divided in the middle, i.e. when each r ∈ R is represented as r = r′ ∘ r′′ such that the lengths of the words representing r′ and r′′ differ at most by one.

Example 3.2. (The System S_{R} = 0 for a Baumslag Solitar Group) Consider the group G = ⟨ x_{1}, x_{2} ; x_{1}x_{2}x_{1}^{−1}x_{2}^{−2} ⟩. Here a linear representation μ : G → SL(2, K) is given by

x_{1} ⟼^{ϱ} (\begin{matrix}a & b \\ c & d \end{matrix}) and x_{2} ⟼^{ϱ} (\begin{matrix}e & f \\ g & h \end{matrix})

We divide the only relator of G into halves and get x_{1}x_{2} ∘ x_{1}^{−1}x_{2}^{−2}. Then we have ϱ(x_{1}x_{2}) = ϱ(x_{2}^{2}x_{1}) in SL(2, K), and therefore

1. det(ϱ(x_{1})) = ad − bc = 1.

2. det(ϱ(x_{2})) = eh − fg = 1.

3. ϱ(x_{1}x_{2}) = ϱ(x_{2}^{2} x_{1}) which yields the matrix equality

(\begin{matrix}ae + bg & af + bh \\ ce + dg & cf + dh \end{matrix}) = (\begin{matrix}ae^{2} + afg + acf + cfh & be^{2} + bfh + def + dfh \\ age + ahg + cgf + ch^{2} & bge + bhg + dgf + dh^{2} \end{matrix})

Thus the system S_{R} = 0 is given by

S_{R} = {ad − bc − 1,
eh − fg − 1,
ae + bg − (ae^{2} + afg + acf + cfh),
af + bh − (be^{2} + bfh + def + dfh),
ce + dg − (age + ahg + cgf + ch^{2}),
cf + dh − (bge + bhg + dgf + dh^{2})}.

Notice that had we constructed a system using ϱ(r) = 1, the last four polynomials would be of degree five.

4 Universal Linear Representations

In this section we discuss a general method for constructing linear representations of finitely presented groups.

Let G be a group, and let K and L be commutative unitary rings. A ring homomorphism φ : K → L induces a group homomorphism φ′ : SL(n, K) → SL(n, L). We say that a linear representation ϱ : G → SL(n, K) is universal if for every linear representation ϱ′ : G → SL(n, L) there exists a ring homomorphism φ : K → L such that ϱ′ = φ′ ∘ ϱ, i.e. such that the following diagram is commutative:

G →^{ϱ} SL(n, K)
↘^{ϱ′}  ↓^{φ′}
SL(n, L)

Similarly, one can introduce universal linear representations of G in the general linear groups GL(n, K).

Remark 4.1. More generally, we can define universal linear representations with respect to a given class of rings. For example, let C_{F} be the class of all unitary commutative algebras L over a fixed field F. We say that a linear representation ϱ : G → SL(n, K) is C_{F} -universal if K ∈ C_{F} and for every linear representation ϱ′ : G → SL(n, L) with L ∈ C_{F} there exists a homomorphism of F -algebras φ : K → L such that ϱ′ = φ′ ∘ ϱ.

In the following we want to determine the universal linear representation of a finitely presented group G = ⟨X; R⟩ explicitly. Let S_{R} = 0 be the polynomial system of equations (3) in sn^{2} indeterminates which defines the variety of representations of G in SL(n, K) for every ring K. We use

T = {y_{ij}^{(k)} | k = 1, …, s, i, j = 1, …, n}

to denote these indeterminates. Furthermore, let I_{R} be the ideal in ℤ[T] generated by the set of polynomials S_{R}, and let the commutative unitary ring Q_{R} be defined by

Q_{R} = ℤ[T]/I_{R}.

Proposition 4.2. Let G = ⟨X; R⟩ be a finitely presented group, and let Q_{R} = ℤ[T]/I_{R} be constructed as above. Then the group homomorphism ϱ : G → SL(n, Q_{R}) defined by

x_{k} ⟼^{ϱ} (\begin{matrix}y_{(1,1)}^{(k)} & … & y_{(1,n)}^{(k)} \\ y_{(n,1)}^{(k)} & … & y_{(n,n)}^{(k)} \end{matrix})  (4)

is a universal linear representation of G.

Proof. This follows directly from the construction.

The group homomorphism ϱ : G → SL(n, Q_{R}) is called a universal linear representation of G. Similarly, for a fixed field F one can construct a representation

ϱ_{F} : G → SL(n, Q_{F,R})

of G in the special linear group over the ring Q_{F,R} = F [T]/I_{R}. Clearly, the map ϱ_{F} is a C_{F} -universal representation of G.

5 Linear Quotient Tests for WP

Quotient tests of the type φ : G → SL(n, K) are called linear quotient tests. Obviously, it suffices to consider only quotient tests with respect to universal linear representations. We refer to such tests as universal linear quotient tests.

Algorithm 5.1. (Universal Linear Quotient Test) Input: A finite presentation G = ⟨X; R⟩, a word w = x_{i_{1}} ⋯ x_{i_{ℓ}} ∈ F (X), and n ∈ ℕ. Output: "No" if φ(w) ≠ 1 where φ : G → SL(n, Q_{R}) is the universal linear representation of G, "Don't know" otherwise. Computations:

1) Compute the set of polynomial equations S_{R} according to (3).

2) Compute a Gröbner basis for I_{R} in ℚ[T].

3) Compute φ(w) = φ(x_{i_{1}}) ⋯ φ(x_{i_{ℓ}}).

4) Let φ(w) = (f_{i,j})_{i,j=1}^{n}. Check whether the polynomial f_{i,j} − δ_{i,j} belongs to the ideal I_{R} for all 1 ≤ i, j ≤ n by reducing it modulo the Gröbner basis. If all f_{i,j} − δ_{i,j} belong to the ideal I_{R}, return "Don't know", otherwise return "No".

Similarly, given a field F, we can construct a C_{F} -universal linear quotient test.

6 Linear Quotient Tests for Infinitude

A further question which can be studied using Gröbner bases is whether a finitely presented group G = ⟨X; R⟩ is finite or infinite. There are several methods available but it is not yet clear how often they apply. The first method uses the following observation.

Remark 6.1. Let φ : G ⟶ SL(n, K) be a group homomorphism to a special linear group over a unitary commutative ring K. If there exists a word w ∈ F (X) such that the matrix W = φ(w) has infinite order in SL(n, K) then G is infinite.

Again we may obviously restrict our attention to the case K = Q_{R}, i.e. to the universal linear representation. Moreover, if φ(G) is infinite then usually almost every element will have infinite order, so that we can try short words first.

In view of this remark we have to compute the minimal polynomial of a matrix in SL(n, Q_{R}) or SL(n, Q_{F,R}). Since this ring is not commutative, the usual computer algebra methods (see e.g. [9], Cor. 3.6.4) do not apply. The following algorithm solves our task using Gröbner basis theory.

Algorithm 6.2. (Minimal Polynomial of a Matrix) Input: A matrix W = (w_{i,j}) ∈ Mat(n, K) where K = F [y_{1}, …, y_{m}]/I is an affine algebra over some field F. Output: The minimal polynomial f ∈ F [z] of W over F, or zero if W is algebraically independent. Computations:

1) In F [y_{1}, …, y_{m}, z]^{n}, form the submodule U generated by the column vectors of W − z · I_{n} and by the elements of I · F [y_{1}, …, y_{m}, z]^{n}. (Here I_{n} denotes the identity matrix of size n.)

2) Using standard Gröbner basis techniques (see e.g. [9], Sect. 3.2), compute the ideal V = U : ⟨e_{1}, …, e_{n}⟩ = ⋂_{i=1}^{n} U : ⟨e_{i}⟩ in F [y_{1}, …, y_{m}, z]. Here {e_{1}, …, e_{n}} denotes the canonical basis of F [y_{1}, …, y_{m}, z]^{n}.

3) Using elimination, compute V ∩ F [z] and return a monic generator of this principal ideal.

Proof. First we equip the F [y_{1}, …, y_{m}]-module Q_{F,R}^{n} with an additional F [z]- module structure by letting z · e_{i} = W · e_{i} = w_{1,i}e_{1} + ⋯ + w_{n,i}e_{n}. We want to compute the annihilator of this F [z]-module. To this end, we consider it as an F [y_{1}, …, y_{m}, z]-module and observe that it has a presentation F [y_{1}, …, y_{m}, z]^{n}/U. Hence it suffices to compute the annihilator of this F [y_{1}, …, y_{m}, z]-module and intersect this annihilator with F [z].

Notice that the matrix W may have infinite order even when this algorithm returns a non-zero polynomial. We can check this easily by examining whether f divides a polynomial of the form z^{m} − 1. This algorithm admits a number of optimizations and variations. Let us point out some possibilities.

Remark 6.3. 1. It is possible to compute the colon ideals U : ⟨e_{i}⟩ in step 2) individually and intersect them at the end. We can use an elimination ordering for {y_{1}, …, y_{m}}. As soon as one of the annihilators contains a non-zero element of F [z] we test whether it is contained in all annihilators. If that holds true, we know that the order of W is finite.

2. Some of the indeterminates y_{i} can be specialized to random elements of F. If the minimal polynomial of W is zero after this specialization, it was zero before. In practice, this technique is quite effective, but requires great care in judging which indeterminates y_{i} can be specialized without harm.

3. In some cases it is easier to construct a suitable subgroup of G, consider its universal linear representation, and find an element of infinite order there.

The following test simplifies the check for infinitude by looking at the diagonal elements of W only. It seems this test is usually weak, but still it may work sometimes.

Algorithm 6.4. (Diagonal Quotient Test for Infinitude) Input: A finitely presented group G = ⟨X; R⟩, and its C_{F} -universal linear representation φ : G ⟶ SL(n, Q_{F,R}) where F is a field. Output: "Yes" for some cases when φ(G) has infinite order, "Don't know" otherwise. Computations:

1) Compute the set of polynomial equations S_{R} ⊆ F [y_{i,j}^{(k)}] as in (3).

2) Repeat the following steps 3) – 5) for k = 1, …, s.

3) Let W_{k} = (y_{i,j}^{(k)}) be the matrix corresponding to φ(x_{k}).

4) For ℓ = 1, …, n, choose a term ordering such that y_{ℓ,ℓ}^{(k)} is the biggest indeterminate. Compute a Gröbner basis of I_{R} with respect to this term ordering and check whether it contains a leading term of the form (y_{ℓ,ℓ}^{(k)})^{N} for some N > 0.

5) If one of the Gröbner bases contains no leading term of the form (y_{ℓ,ℓ}^{(k)})^{N} for some N > 0, return "Yes".

  6) Return "Don't know".

Proof. If the algorithm returns "Yes" then the matrix W_{k} = (y_{i,j}^{(k)}) under consideration has infinite order in φ(G). Namely, if W_{k} has a finite order N then the leading term of the (ℓ, ℓ)-entry of W_{k}^{N} is (y_{ℓ,ℓ}^{(k)})^{N}. Since there are no polynomials in I_{R} to reduce such a leading term, the element W_{k} = φ(x_{k}) generates an infinite cyclic group.

If this diagonal quotient test does not work initially because the elements x_{i} have finite orders in G, we can change the presentation of G suitably and apply it again.

Remark 6.5. Another simple approach which works occasionally is to determine the minimal polynomial of det(φ(w)) for some word w ∈ F (X) which is expected to be of infinite order in G = ⟨X; R⟩. Obviously we have to use the universal representation φ : G ⟶ GL(n, Q_{R}) in this case. If we have φ(w)^{N} = 1 in GL(n, Q_{R}) for some N > 1 then det(φ(w))^{N} = 1 holds in Q_{R}. Thus if det(φ(w)) has infinite order in Q_{R} then w has infinite order.

7 Some Examples

In this section we put our algorithms to work and study some difficult or otherwise inaccessible group presentations.

In following we let G = ⟨a, b, ...; r_{1} = ⋯ = r_{t} = 1⟩ be a finitely presented group and φ_{n} : G ⟶ GL(n, Q_{R}) its universal representation of size n. The images of the generators will be denoted by x = φ_{n}(a), y = φ_{n}(b), z = φ_{n}(c), w = φ_{n}(d).

7.1 From the Kourovka Notebook (1)

For i ≥ 2 consider the groups

G_{i} = ⟨a, b; a^{i} = 1, ab = b^{3}a^{3}⟩.

They appeared in the Kourovka Notebook [14] in Problem 7.7 (a question of R.G. Burns for i = 9) and Problem 8.10 (D.L. Johnson’s question for i = 7, 9, 15). The task is to decide whether G_{i} is finite for i = 5, 7, 9, . . .. For i = 9 and i = 15 the groups are known to be infinite (see [17] for i = 9,

[21] for i = 15, and also [19] for i = 9, 15). Whether G_{7} is finite or not is an open question. Our computations give the following partial results for these groups.

Lemma 7.1. If φ_{n}(G_{i}) (or G_{i}) is commutative, it is a finite group of order 2i.

Proof. Since xy = y^{3}x^{3} = x^{3}y^{3} implies (xy)^{2} = x^{2}y^{2} = 1, the group φ_{n}(G_{i}) is a commutative group generated by two elements of order i and 2, respectively.

Remark 7.2. Using n = 2 and the representation φ_{2}(G_{i}) = ⟨x, y, z, w; xz = zx = 1, x^{(i+1)/2} = z^{(i−1)/2}, xy = y^{3}x^{3}, yw = wy = 1⟩, we can compute a truncated Gröbner basis of I_{R} to show that we have xy = yx in the groups φ_{2}(G_{i}) for i = 5, 7, 9, 11. Therefore these groups are commutative and finite.

7.2 From the Kourovka Notebook (2)

The following series of groups appeared in the Kourovka Notebook [14] as Problem 11.10.b. Let

H_{i} = ⟨a, b; a^{i} = 1, b^{−2}ab^{2} = a(b^{−1}ab)a^{−1}(b^{−1}a^{−1}b)⟩
= ⟨a, b; a^{i} = 1, ababa = b^{2}ab^{−1}ab⟩

for i ≥ 2. We want to examine the question whether a = 1 in H_{i}. By [14], it is known that a ≠ 1 in H_{5}.

Remark 7.3. First we use n = 2. To describe φ_{2}(H_{i}), we use the monoid representation ⟨x, y, z; x^{i} = 1, xz = zx = 1, xyxyx = y^{2}xzxy⟩. By computing the complete Gröbner bases of I_{R}, we can show that x ≠ 1 in φ_{2}(H_{i}) for i = 5, 10, 15, 20. Consequently, we have a ≠ 1 in H_{5}, H_{10}, H_{15}, and H_{20}.

In the groups φ_{2}(H_{i}) with i ∈ {2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19}, we have x = φ_{2}(a) = 1. Furthermore, if we use n = 3, we can show that in the subgroup φ_{3}(H_{2}) of GL(3, Q_{R}) we also have x = 1.

7.3 Some Groups of Deficiency Zero

The following groups appeared in [5], page 63. It is still unknown whether they are finite or not. Our Gröbner basis techniques yield the following partial results.

Example 7.4. Consider the group

F_{11} = ⟨a, b, c; cac^{−1}b^{−1}aba, bacba^{−1}c^{−1}b, cb^{−1}acbca^{−1}⟩

For practical computations, we present the group φ_{n}(F_{11}) by

φ_{n}(F_{11}) = ⟨x, y, z; xyxzx = yz, y^{2}xzy = zx, xy^{2} = yzyxz^{2}⟩

To obtain the third equation, we use yzyxz^{2} = xyxzxyxz^{2} = xyxzyzx^{−1}z = xy^{2}.

The question whether this group is finite or infinite is still open. However, the reduced Gröbner basis with respect to DegRevLex of the ideal I_{R} for the universal representation φ_{2} : F_{11} ⟶ SL(2, Q_{R}) can be calculated. It has 117 elements and enables us to check that φ_{2}(F_{11}) ≅ ℤ/(3) × ℤ/(3) × ℤ/(3).

Example 7.5. Consider the group

F_{12} = ⟨a, b, c; acab^{−1}c^{−1}ab, b^{2}a^{−1}c^{−1}acb, ca^{−1}b^{−1}cabc⟩

For practical computations, we present φ_{n}(F_{12}) as

φ_{n}(F_{12}) = ⟨x, y, z; xyxzx = zy, xzy^{3} = zx, zxyz^{2} = yx⟩

The reduced Gröbner basis with respect to DegRevLex of the ideal I_{R} for the universal representation φ_{2} : F_{12} ⟶ SL(2, Q_{R}) can be calculated and show that this ideal agrees with the ideal of φ_{2}(F_{11}). Hence we have φ_{2}(F_{12}) ≅ ℤ/(3) × ℤ/(3) × ℤ/(3). A Gröbner basis of the ideal of φ_{3}(F_{12}) is difficult to compute. A partial computation has so far revealed five equations of degree three and 31 equations of degree four.

Example 7.6. Consider the group

F_{13} = ⟨a, b, c; acab^{−1}c^{−1}ab, acbc^{−1}ba^{−1}b, b^{−1}abc^{2}a^{−1}c⟩

Using the equations abc^{2}baca = abc^{2}a^{−1}cb = b^{2} and abacbacb = abacab^{−1}c = c^{2}, we see that we can present φ_{n}(F_{13}) in the form

φ_{n}(F_{13}) = ⟨x, y, z; xyxzx = zy, xyz^{2}yxzx = y^{2}, xyxzyxzy = z^{2}⟩

The reduced DegRevLex-Gröbner basis of the ideal corresponding to the representation φ_{2} : F_{13} ⟶ SL(2, Q_{R}) turn out to be the same as for φ_{2}(F_{11}) and φ_{2}(F_{12}). Hence we get φ_{2}(F_{13}) ≅ ℤ/(3) × ℤ/(3) × ℤ/(3) once again.

Apparently, it is not known whether this group is finite or not, and the Gröbner basis for φ_{3}(F_{13}) is difficult to compute.

8 Classification of Finite Generalized Triangle and Tetrahedron Groups

In this section we want to connect some methods used in the classifications of finite generalized triangle and tetrahedron groups with our Gröbner basis techniques and report on some partial additional results. Generalized triangle groups and tetrahedron groups play an important role in the theory of onerelator products of cyclics as well as in the theory of 3-dimensional hyperbolic orbifolds, especially for those with small covolume. A generalized triangle group is a group having a presentation

G = ⟨a, b; a^{p} = b^{q} = R(a, b)^{r} = 1⟩

where p, q, r ≥ 2 and R(a, b) is a cyclically reduced word involving both a and b, and not a proper power in the free product of cyclics. A generalized tetrahedron group is a triangle of groups, i.e. a colimit of a triangle of groups with injective homomorphisms, with generalized triangle groups as vertices, and with cyclic groups as edge groups (see [3]). Both generalized triangle groups and tetrahedron groups admit essential representations into (projective) linear groups, that is representations such that the images of the generators and relators have the respective orders. This fact has been used to classify finite generalized triangle and tetrahedron groups.

For generalized triangle groups, the classification was achieved in [6] and [10]. Here we describe two typical cases.

Example 8.1. In order to examine the group D_{1} = ⟨a, b; a^{2} = b^{3} = (abababab^{2}abab^{2}ab^{2})^{2} = 1⟩, we look at its commutator subgroup D′_{1}. The group D′_{1} is generated by x = b and y = aba, and in these generators it has a presentation

D′_{1} = ⟨x, y; x^{3} = y^{3} = xy^{−1}x^{−1}yxyx^{−1}yx^{−1}y^{−1}xyxy^{−1} = 1⟩

In [10] it was shown that D′_{1} has an essential representation φ_{3} : D′_{1} ⟶ GL(3, F) where F ⊃ ℚ is an algebraic number field containing an element γ which satisfies γ^{6} − 3γ^{3} + 1 = 0. Moreover, the element φ_{3}(xy) has infinite order.

Using the methods of this paper, we can compute a reduced Gröbner basis of the ideal corresponding to the universal representation φ_{2} : D′_{1} ⟶ SL(2, Q_{R}). Algorithm 6.2 then shows that minimal polynomial of φ_{2}(xy) is z^{7} − 2z^{6} + 3z^{5} − 4z^{4} + 4z^{3} − 3z^{2} + 2z − 1, and therefore this matrix has order 20. However, if we repeat the calculation for φ_{3} : D′_{1} ⟶ SL(3, Q_{R}), we get that φ_{3}(xy) has minimal polynomial 0, i.e. infinite order.

Example 8.2. To show that the group

D_{2} = ⟨a, b; a^{3} = b^{3} = (a^{−1}b^{−1}ababa^{−1}b)^{2} = 1⟩

is infinite, we use the following method from [11]. Let N be the normal closure of {b} in D_{2}. Then N has index 3 and a presentation

N = ⟨x, y, z; x^{3} = y^{3} = z^{3} = (z^{−1}xyx)^{2} = (x^{−1}yzy)^{2} = (y^{−1}zxz)^{2} = 1⟩

The subgroup N has an essential representation φ̄_{2} : N ⟶ P SL(2, ℂ) for which the element φ̄_{2}(xy) has infinite order.

If we compute the universal representation φ_{2} : N ⟶ SL(2, Q_{R}), it turns out that the image of N is trivial. To simulate a representation in P SL(2, ℂ), we can use the base field F = ℤ/(2). In this way we achieve the equality of the identity matrix and its negative. The Gröbner basis of the corresponding ideal I_{R} can be computed easily. Then we can apply Algorithm 6.2 and check that the image of xy in this universal representation has order 28. It is an open question how we can treat PSL-representations such as φ̄_{2} using our methods.

In the paper [20], G. Rosenberger and M. Scheer classified the finite generalized tetrahedron groups, except for five groups for which it is still unknown whether they are finite or not. The following proposition is useful for studying the universal representations of size 2 × 2 of these groups.

Proposition 8.3. Let K be a commutative unitary ring, and let u, v ∈ SL(2, K) \ {1, −1}.

1. If tr(u) = 0 then u^{2} = −1.

2. If u^{2} = −1 then (tr(u))^{2} = 0.

3. If u^{2} = 1 then (tr(u))^{2} = 4.

4. For all k ≥ 1 and all α_{i}, β_{j} ∈ ℕ, we have

tr(u^{α_{1}}v^{β_{1}} ⋯ u^{α_{k}}v^{β_{k}}) = tr(u^{−α_{1}}v^{−β_{1}} ⋯ u^{−α_{k}}v^{−β_{k}}).

Proof. First we show (1). We let u = \binom{u_{1} u_{2}}{u_{3} u_{4}} and calculate

u^{2} = (\begin{matrix}u_{1}^{2} + u_{2}u_{3} & u_{2}(u_{1} + u_{4}) \\ u_{3}(u_{1} + u_{4}) & u_{4}^{2} + u_{2}u_{3} \end{matrix}) = (\begin{matrix}u_{1}(u_{1} + u_{4}) − 1 & u_{2}(u_{1} + u_{4}) \\ u_{3}(u_{1} + u_{4}) & u_{4}(u_{1} + u_{4}) − 1 \end{matrix})

because we have det(u) = u_{1}u_{4} − u_{2}u_{3} = 1. Therefore tr(u) = u_{1} + u_{4} = 0 implies u^{2} = −1.

To prove (2), we note that u_{1}(u_{1}+u_{4}) = u_{4}(u_{1}+u_{4}) = 0 by the hypothesis, and hence (u_{1} + u_{4})^{2} = 0. Consequently, we get (tr(u))^{2} = (u_{1} + u_{4})^{2} = 0. Similarly, claim (3) follows from u_{1}(u_{1} + u_{4}) = u_{4}(u_{1} + u_{4}) = 2.

Finally, we prove (4). We proceed by induction on k and use the general formula

tr(AB^{−1}) = (tr(A)) (tr(B)) − tr(AB)

for A, B ∈ SL(2, K). We certainly have tr(u^{−α_{1}}v^{−β_{1}}) = tr(u^{α_{1}}v^{β_{1}}). For k ≥ 2, we find

tr(u^{−α_{1}}v^{−β_{1}} ⋯ u^{−α_{k}}v^{−β_{k}}) = = tr(u^{−α_{1}}v^{−β_{1}}) tr(u^{−α_{2}}v^{−β_{2}} ⋯ u^{−α_{k}}v^{−β_{k}}) − tr(v^{β_{1}}u^{α_{1}−α_{2}}v^{−β_{2}} ⋯ u^{−α_{k}}v^{−β_{k}}) = tr(u^{α_{1}}v^{β_{1}}) tr(u^{α_{2}}v^{β_{2}} ⋯ u^{α_{k}}v^{β_{k}}) − tr(u^{α_{1}−α_{2}}v^{β_{2}} ⋯ u^{α_{k}}v^{β_{k}−β_{1}}) = tr(u^{α_{1}}v^{β_{1}} ⋯ u^{α_{k}}v^{β_{k}})

This concludes the proof.

Therefore we have to expect many additional relations in φ_{2}(T) where T is the group under consideration. In fact, the following examples are based on our computer calculations and show that all representations of size 2 × 2 of the five groups are finite.

Example 8.4. Consider the group

T_{1} = ⟨a, b, c; a^{2} = b^{3} = c^{3} = (ac)^{2} = (bc)^{2} = (abababab^{2}abab^{2}ab^{2})^{2} = 1⟩

First we use the universal representation φ_{2} : T_{1} ⟶ GL(2, Q_{R}). For the group φ_{2}(T_{1}), we can use the computation of a trucated Groebner basis of I_{R} to show (xy)^{2} = (yx)^{2} = 1. Thus we have

φ_{2}(T_{1}) = ⟨x, y, z; x^{2} = y^{3} = z^{3} = (xy)^{2} = (yz)^{2} = (xz)^{2} = 1⟩

This group is clearly finite. In fact, it is easy to see that it has 24 elements and is a double cover of the alternating group A_{4}.

However, the question whether the image of the universal representation φ_{3} : T_{1} ⟶ GL(3, Q_{R}) is finite or infinite is still open.

Example 8.5. The second group on the Rosenberger-Scheer list is

T_{2} = ⟨a, b, c; a^{2} = b^{5} = c^{2} = (ac)^{2} = (bc)^{2} = (abab^{3}ab^{2}ab^{4}ab)^{2}⟩

Using the modified presentation

φ_{n}(T_{2}) = ⟨x, y, z ; x^{2} = y^{5} = z^{2} = 1, xz = zx, zyz = y^{4},
yxyxy^{3}xy^{2}xy^{4}xy = xyxy^{3}xy^{2}xy^{4}x⟩

and a truncated Gröbner basis computation, we get (xy)^{2} = (yx)^{2} = 1 for the universal representation φ_{2} : T_{2} ⟶ GL(2, Q_{R}). Hence every word in φ_{2}(T_{2}) can be written in the form x^{ε} w with ε ∈ {0, 1} and a word w involving only y and z. Since ⟨y, z; y^{5} = z^{2} = (yz)^{2} = 1⟩ is known to be a finite triangle group, the group φ_{2}(T_{2}) is finite, too.

For the universal representation φ_{3} : T_{2} ⟶ GL(3, Q_{R}), it appears to be difficult to compute a Gröbner basis of I_{R}.

Example 8.6. The third group considered by Rosenberger and Scheer is

T_{3} = ⟨a, b, c; a^{3} = b^{5} = c^{3} = (ac)^{2} = (b^{2}c)^{2} = (aba^{2}b^{2})^{2}⟩

For practical computations, we present the group φ_{n}(T_{3}) by

φ_{n}(T_{3}) = ⟨x, y, z; x^{3} = y^{5} = z^{3} = 1, xzx = z^{2}, y^{3} = zy^{2}z, yx^{2}y^{2}xy = x^{2}y^{3}x⟩

In this way, the defining equations of the universal ideal have degrees ≤ 7. For the representation φ_{2} : T_{3} ⟶ GL(2, Q_{R}), a truncated Gröbner basis computation yields the equations x = y = z = 1. Hence this representation is trivial.

For the representation φ_{3} : T_{3} ⟶ GL(3, Q_{R}), a truncated Gröbner basis computation yields tr(x^{2}) = tr(z) and tr(z^{2}) = tr(x).

Example 8.7. Next we consider the group

T_{4} = ⟨a, b, c; a^{3} = b^{5} = c^{2} = (ac)^{2} = (bc)^{2} = (a^{2}ba^{2}b^{2}abab^{−1})^{2} = 1⟩

To get equations of low degree, we use the presentation

φ_{n}(T_{4}) = ⟨x, y, z ; x^{3} = y^{5} = z^{2} = 1, zxz = x^{2}, zyz = y^{4},
yx^{2}y^{2}xyxy^{4}x^{2}y = xyx^{2}y^{4}x^{2}y^{3}x⟩

A computation of a Gröbner basis for the ideal I_{R} corresponding to the universal representation φ_{2} : T_{4} ⟶ SL(2, Q_{R}) yields x = y = 1 and z = ±1. Hence φ_{2}(T_{4}) is the group with two elements. Notice that we used SL(2, Q_{R}) here, since the computation for GL(2, Q_{R}) is more involved.

Example 8.8. Finally, we want to examine the group

T_{5} = ⟨a, b, c; a^{3} = b^{3} = c^{3} = (ac)^{2} = (bc^{−1})^{2} = (ababa^{−1}b^{−1})^{2} = 1⟩

A more balanced presentation of this group is

φ_{n}(T_{5}) = ⟨x, y, z ; x^{3} = y^{3} = z^{3} = 1, xzx = z^{2}, yz^{2} = zy^{2},
xyxyx^{2}y^{2}x = yxy^{2}x^{2}y^{2}⟩

Using the representation φ_{2} : T_{5} ⟶ GL(2, Q_{R}), a truncated Gröbner basis computation of I_{R} shows y = z and x^{2} = y. Hence φ_{2}(T_{5}) is the group with three elements.

The Gröbner basis of the universal ideal corresponding to the representation φ_{3} : T_{5} ⟶ GL(3, Q_{R}) is harder to compute. A truncated computation yields several equalities in φ_{3}(T_{5}), for instance tr(y) = tr(z). However, it is not clear whether φ_{3}(T_{5}) is finite or not.

References

[1] S.I. Adian and V.G. Durnev, Algorithmic problems for groups and semigroups, Uspekhi Mat. Nauk. 55 (2000), 3–94; translation in Russian Math. Surveys 55 (2000), 207–296.

[2] G.W. Brumfiel and H.M. Hilden, SL(2) Representations of Finitely Presented Groups, Contemp. Math. 187, Amer. Math. Soc., Providence, 1995

[3] B. Fine and G. Rosenberger, Algebraic Generalization of Discrete Groups, Marcel Dekker, New York, 1999.

[4] G. Havas, D.F. Holt, P.E. Kenne and S. Rees, Some challenging group presentations, J. Austral. Math. Soc. 67 (1999), 137–163.

[5] G. Havas, M. F. Newman, and E. A. O’Brien, Groups of deficiency zero, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 25, 1996.

[6] J. Howie, V. Metaftsis, and R.M. Thomas, Finite generalized triangle groups, Trans. Amer. Math. Soc. 347 (1995), 3613-3624.

[7] I. Kapovich, A. Myasnikov, P. Schupp, and V. Shpilrain, Generic-case complexity and decision problems in group theory, J. of Algebra 264 (2003), 665–694.

[8] I. Kapovich, A. Myasnikov, P. Schupp, and V. Shpilrain, Average-case complexity for the word and membership problems in group theory, Adv. Math. (to appear)

[9] M. Kreuzer and L. Robbiano, Computational Commutative Algebra 1, Springer, Heidelberg 2000.

[10] L. Levai, G. Rosenberger, and B. Souvignier, All finite generalized triangle groups, Trans. Amer. Math. Soc. 347 (1995), 3625–3627.

[11] F. Levin and G. Rosenberger, On free subgroups of generalized triangle groups, Part II, in: Group Theory, World Scientific 1993, 206–228.

[12] A. Lubotzky and A.R. Magid, Varieties of representations of finitely generated groups, AMS Memoirs 336, Amer. Math. Soc, Providence 1985

[13] R. Lyndon and P. Schupp, Combinatorial Group Theory, Springer, New York 1977.

[14] V.D. Mazurov and E.I. Khukhro (eds.), Open problems in group theory: The Kourovka Notebook, Institute of Mathematics, Novosibirsk, 2002.

[15] C.F. Miller III, On Group-theoretic Decision Problems and their Classification, Ann. of Math. Studies 68, Princeton University Press, Princeton 1971.

[16] C.F. Miller III, Decision problems for groups – Survey and reflections, in: G. Baumslag and C.F. Miller III (eds.), Algorithms and Classification in Combinatorial Group Theory, Springer, New York 1992, pp. 1–60.

[17] M.F. Newman, Proving a group infinite, Arch. Math. 54 (1990), 209– 211.

[18] M.F. Newman, private communication, 2005.

[19] M.I. Prishchepov, Aspherisity, atorisity and symmetrically presented groups, Commun. in Alg. 23 (1995), 5095–5117.

[20] G. Rosenberger and M. Scheer, Classification of finite generalized tetrahedron groups, Contemp. Math. 296 (2002), 207–229.

[21] D.J. Seal, The orders of the Fibonacci groups, Proc. Roy. Soc. Edinburgh, Sect. A 92 (1982), 181–192.