redundant relations

Question

The situation is the following: I have a group of matrices (given by generators), and I am trying to find a presentation. Now, this is in general very hard (undecidable?) but here I want to know if people know heuristics for pruning the set of relators -- in other words, by computing further generations of the group, I get a number of words $w_1, \dots, w_k$ which represent the identity. No doubt some of these relations are consequences of others, so is there some nice way to remove the "dependent relations"?

Answer 1

This doesn't answer the main question, but it does address the parenthetical question of the decidability of computing presentations in matrix groups. In so doing, I hope it helps to clarify Joel and Benjamin's answers.

Bridson and I showed that the problem of computing presentations in matrix groups over $\mathbb{Z}$ is undecidable, in this paper. More precisely, we produce a recursive sequence of subsets $S_n\subseteq SL_{m_n}(\mathbb{Z})$ and an r.e. sequence of integers $r_n$ such that:

• for each $n$, $\langle S_n\rangle$ is finitely presentable (in principle!), but
• the set $\{n\in\mathbb{N}\mid b_1(\langle S_n\rangle)=r_n\}$ is r.e. but not recursive.

So $b_1(\langle S_n\rangle)$ (the first Betti number) is not computable. Since it's straightforward to compute $b_1$ from a presentation, it follows that presentations are not computable.

Unfortunately, in our examples, $m_n\to\infty$ as $n\to\infty$. It would be great to have examples in which $m_n$ was bounded (and even better to have examples in which $m_n=3$).

Answer 2

Let's ignore the source of the group, and concentrate on the question you seem to be asking. Let $G = \langle x_1,x_2,\ldots,x_r \mid r_1,r_2,\ldots,r_s \rangle$ be a finite group presentation, where the $r_i$ are defining relators. Can we decide whether $r_s$ is redundant; that is, whether $G = \langle x_1,x_2,\ldots,x_r \mid r_1,r_2,\ldots,r_{s-1} \rangle$.

As others have pointed out, the theoretical answer is no, but the problem is a semi-decidable probelm in the sense that, if the answer is yes, then you can prove constructively that it is yes. In practice there are two well studied and implemented algorithms that you can use to try and do this.

The first is Todd-Coxeter coset enumeration, which is most useful when the groups are finite, so that is probably not the best choice here.

The second is Knuth-Bendix completion, and that is the most likely to be useful here. You run it on the presentation $\langle x_1,x_2,\ldots,x_r \mid r_1,r_2,\ldots,r_{s-1} \rangle$. It will probably not halt, but that doesn't matter. Just run it for a few minutes or a few days, or whatever. Then interrupt it (or wait until it exceeds some bound - I usually tell it stop when it has produced a million rewrite rules or something). Then you can quickly check whether $r_s$ reduces to the identity under the rewrite rules that you have generated. If $r_s$ really is a consequence of the other relators, then you know that this method will work if you run the program for long eneough but, except in the rare cases when the process completes with a confluent presentation, you cannot use this method to prove the answer is no.

The only practical ways of showing that $r_s$ is not a consequence of the other relators is to compute some of the quotients of $G$ and see if you get different results by leaving out $r_s$. There are algorithms available for computing finite quotients, virtually abelian quotients, virtually nilpotent quoteints, etc.

Knuth-Bendix completion and the quotient algorithms are available in both GAP and Magma.

Answer 3

This should be a comment but is too long. The decidability of the question whether a finite set R of relations implies some other relation r=1 in all linear groups is the same as asking if R implies r=1 in all finite groups because of Malcev's theorem on residual finiteness of linear groups. A beautiful theorem of Slobodoskoii says this latter problem is undecidable.

A consequence is that the first order theory for finite dimensional modules over an algebra of wild representation type is undecidable. (Most books on finite dimensional algebras mistakenly assert it follows from undecidability of the word problem for groups, but one must then allow infinite dimensional modules.)

Edit. The question is not entirely well posed. It is impossible to decide whether your group is finitely presented as @HJRW points out. @IgorRivkin says he wants to know how to prune relations, that is, given a finite set of relations that are true remove others that are consequence. The ambiguity is whether one means redundant in a linear group or in all groups. If one means in all groups, then the fact that your group is linear seems a red herring and you are in the situation that @JoelHamkins and @DerekHolt give in their answers. My answer was assuming that you want to know if certain relations were consequences of others in all linear groups. If this is what you want the best semi-procedure is to look at images under congruence homomorphisms to rule out certain relations as being redundant and follow Derek's procedure to say that certain relations are redundant.

Answer 4

In the general case, to determine whether some relations imply another given relation is an undecidable problem. If it were decidable, then we could decide whether a given finite presentation was presenting the trivial group or not (a known undecidable problem), by testing whether the generators are all redundant as relations.