What methods exist to prove that a finitely presented group is finite? - MathOverflow

What methods exist to prove that a finitely presented group is finite?

2009-12-03T22:24:31Z

Suppose I have a finitely presented group (or a family of finitely presented groups with some integer parameters), and I'd like to know if the group is finite. What methods exist to find this out? I know that there isn't a general algorithm to determine this, but I'm interested in what plans of attack do exist.

One method that I've used with limited success is trying to identify quotients of the group I start with, hoping to find one that is known to be infinite. Sometimes, though, your finitely presented group doesn't have many normal subgroups; in that case, when you add a relation to get a quotient, you may collapse the group down to something finite.

In fact, there are two big questions here:

How do we recognize large finite simple groups? (By "large" I mean that the Todd-Coxeter algorithm takes unreasonably long on this group.) What about large groups that are the extension of finite simple groups by a small number of factors?
How do we recognize infinite groups? In particular, how do we recognize infinite simple groups?

(For those who are interested, the groups I am interested in are the symmetry groups of abstract polytopes; these groups are certain nice quotients of string Coxeter groups or their rotation subgroups.)

Answer by Ryan Budney for What methods exist to prove that a finitely presented group is finite?

2009-12-03T22:41:15Z

This is sort of a sideways look at your question:

There's software called "Heegaard" by John Berge that takes as input a finite presentation and attempts to find a corresponding Heegaard splitting of a 3-manifold which has that fundamental group. It seems to be fairly effective. There are algorithms to produce triangulations of Heegaard splittings available (Hall and Schleimer for example). So you could take the presentation, find (if possible) the Heegaard splitting, produce the triangulation and then use software like Regina and SnapPea to analyze the geometry of those manifolds. There's a lot of heuristics there and also some serious algorithms. All the links the the various packages and their documentation is available here: http://www.math.uiuc.edu/~nmd/computop/

So for groups that are the fundamental groups of 3-manifolds at least, there's a decent toolkit to play with.

As an example, consider testing to see if a group is trivial. Step 1: Heegaard could get stuck. Step 2: if Heegaard finds a splitting, you triangulate it and pass it to Regina. Step 3: Regina has an algorithm to recognise a triangulated 3-sphere, so it will tell you whether or not your group is trivial.

Answer by Leonid Positselski for What methods exist to prove that a finitely presented group is finite?

2009-12-03T23:59:51Z

I suppose Groebner bases can be used to compute the size of a group with generators and relations, just as they can be used to compute the size of a commutative or noncommutative algebra with generators and relations. This certainly would not work in all cases, but in some simple enough cases it will. In particular, when your group is actually finite, you will eventually discover this with Groebner bases, though the computation time may be impracticable for a human, or even for a computer. When your group is infinite, Groebner bases will sometimes tell you it is, but sometimes they wouldn't.

Answer by Agol for What methods exist to prove that a finitely presented group is finite?

2009-12-04T01:46:41Z

There is no algorithm to tell if a finitely presented group is finite, but in principle there is a procedure which will terminate if your group is finite, and tell you which group it is. You can recursively list all finite groups (e.g. by group tables), and therefore presentations for them. You can recursively perform all Tietze transformations on your group presentation, and check at each stage whether it agrees with one of the finite group presentations you have computed (imagine doing this in parallel or alternating the steps of the two recursive procedures). This will eventually tell you whether your group is finite if it is. But of course this is completely impractical, and I realize this isn't what you want. The uncomputable thing is to prove that a group is not finite.

Answer by HW for What methods exist to prove that a finitely presented group is finite?

2009-12-04T02:29:43Z

Regarding part 2 of your question - "In particular, how do we recognize infinite simple groups?" - I think the answer is that it depends on which infinite simple group you're looking at! Some famous examples:-

Higman's original construction of an infinite simple group starts with a group with no non-trivial finite quotients. (Roughly, you construct one of these by building in a pair of conjugate elements which would have to have different orders in a finite quotient.) You then proceed to take the quotient by a maximal proper normal subgroup. The result can't be finite, because that would be a non-trivial finite quotient! (There was some discussion of this here.)
Thompson's groups T and V contain elements of infinite order!
Tarski Monsters are infinite because of Sylow's Theorems. Every proper subgroup is of prime order p, so Sylow's Theorems tell you that if it were finite then it would be cyclic, which it isn't by construction.

Do you have a particular reason to think that your groups are simple? What do you know about the kernel of the map from the Coxeter group?

EDIT: Just wanted to emphasize that of course, of the examples listed, only Thompson's Groups happen to be finitely presented. Finitely presented infinite simple groups are pretty special.

Answer by Ben Fairbairn for What methods exist to prove that a finitely presented group is finite?

2009-12-04T12:00:43Z

Your approach of finding infinite quotients is certainly a standard one. There is, however, a slight tweeking of it that helps in the event that this approach breaks down - search through some low index subgroups. If any of these have infinite homomorphic images then your group must posses an infinite subgroup and thus must also be infinite. In Magma the command "LowIndexSubgroups" can do this and I suspect somthing similar works in GAP, matlab etc.

As with the other techniques this is not a sure-fire 100% guaranteed method, but it is sometimes useful.

Simplicity of an infinite group is a much harder question to address. Needless to say that if I was a beting man then I would certainly put money on your group not being simple.

Answer by Steve D for What methods exist to prove that a finitely presented group is finite?

2010-02-05T07:52:39Z

One can also sometimes use Fox calculus, which describes the abelianization of a finite-index normal subgroup of $G$. If this abelianization is infinite, your group is infinite. Johnson's "Presentations of Groups", chapter 12, describes this in detail.

Also see this thread for some examples of other techniques: group-pub

Steve

Answer by Victor Miller for What methods exist to prove that a finitely presented group is finite?

2010-02-05T13:10:56Z

The theory of automatic groups may be a help here. There is a nice package written by Derek Holt and his associates called kbmag (available for download here: http://www.warwick.ac.uk/~mareg/download/kbmag2/ ). A previous answer mentioned groebner bases. The KB in kbmag stand for Knuth-Bendix which is a string rewriting algorithm which can be considered to be a non-commutative generalization of groebner bases. There is a book "Word Processing in Groups" by Epstein, Cannon, Levy, Holt, Paterson and Thurston that describes the ideas behind this approach. It's not guaranteed to work (not all groups have an "automatic" presentation) but it is surprisingly effective.

Answer by kakaz for What methods exist to prove that a finitely presented group is finite?

2010-02-08T12:51:30Z

There is a software called Magnus (http://www.grouptheory.org/magnus) which gives You some insight how it may be implemented. I do not know anything about details, but it has some documentation, and works pretty well;-)

Answer by Anne Thomas for What methods exist to prove that a finitely presented group is finite?

2010-02-11T18:42:06Z

If a discrete group is amenable and has Kazhdan's Property (T), then it is finite.

I'm not sure it would help you, but it's a technique.

This technique was used by Margulis in his original proof of his Normal Subgroup Theorem. It's since been used in a couple of other Normal Subgroup Theorems, which have been applied to prove simplicity of some infinite groups. See for example "Lattices in products of trees" by Burger and Mozes, and "Simplicity and superrigidity of twin building lattices" by Caprace and Remy.