Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Two days ago, I asked why free presentations? and frankly I did not get a convincing answer. I am trying here to ask the question in a different way : We know that a group can be defined by a permutation or matrix representation. What is the point of a presentation (I mean here free presentations) for which all the problems are undecidable?

Another point : As I know, permutation representations are preferred for computational purposes (by "HANDBOOK OF COMPUTATIONAL GROUP THEORY" ). Then what's the advantage of free presentations? is it the space needed to store them ?

share|cite|improve this question
One important point: for finite groups given by finite presentations, all the problems can be decided. The main difficulty is the lack of bounds on runtime. However, given a permutation group, finding a presentation is efficient. The same may soon be true in matrix groups, but is not true in practice yet, I don't believe. – Jack Schmidt Apr 9 '14 at 11:30
And presentations are used in algorithms for computing the orders of large permutation and matrix groups, as discussed in Chapter 6 of "Handbook of Computational Group Theory". – Derek Holt Apr 9 '14 at 11:33
up vote 7 down vote accepted

Here are two reasons why group presentations are important. Firstly, they often provide the most compact and precise definition of the group. For example, when classifying groups of small order, they provide a uniform and concise method of description. For example, one of the groups of order $12$ has presentation $\langle x,y \mid x^4=y^3=1, y^{-1}xy=x^{-1} \rangle$. Other descriptions, such as semidirect product of cyclic group of order $3$ by cyclic group of order $4$ with nontrivial action, or subgroup $\langle (1,2,3), (2,3)(4,5,6,7) \rangle$ of $S_7$ are possible, but are less concise.

Even for infinite groups, a presentation is often convenient, such as the Heisenberg group $\langle x,y,z \mid [x,y]=z, [x,z]=[y,z]=1 \rangle$, which can of course also be described as the group of upper unipotent unitriangular $3 \times 3$ matrices over ${\mathbb Z}$.

The second reason is computational. You said that permutation and matrix representations are generally more convenient for computational purposed, and that is to a large extent true, but for some applications you need a presentation as well. For example, if to compute homomorphisms from a group $G$ to another group $H$ (which includes the important problems of the computation of automorphism groups, and isomorphism testing), you need a presentation of $G$. Presentations are also needed for various cohomologcal calcualtions involving groups extensions.

It is worth mentioning also that a particular type of presentation, a polycyclic presentation is the preferred data structure for computing in polycyclic groups (which includes finite solvable groups) - see Chapter 8 in the "Handbook of Computational group Theory". The above presentation of the Heisenberg group is an example.

I should add also that, in some contexts, such as the computation of fundamental groups in topology, the group in question can arise as a presentation, so it is necessary to have techniques for studying such groups.

share|cite|improve this answer

Note: The following answer was written before the second point was added to the question. Therefore, it only answers the question in the first paragraph.

As I said in my answer to that question, the presentation is, in a certain sense, circumstantial. That is, if I give you a (finite) presentation of a group and the presentation has insoluble word problem then no matter how I give you the group it still has insoluble word problem. For example, if I was to concoct a permutation representation of this group I would be unable to determine (in general) if two permutations were equal. So, to be clear: such decision problems are properties of the abstract groups, not of the way you are given them.

Also, you say that a group "can be defined by a matrix representation". This isn't quite correct...or rather, it is a bit vague. You can always find an infinite-dimensional matrix representation, but these are not generally nice. Indeed, if the matrix representation is finite-dimensional and if the group is finitely presentable then the group has soluble word problem (see Below). So, in a certain sense, you are correct to think that matrix representations are nice, but my point is that they are nice so bad groups cannot occur this way. See this answer of mine for more details about representations of infinite groups.

For example, the group $\langle a, b; ab^2a=b^3\rangle$ does not have a finite-dimensional linear representation (although it does have soluble word and conjugacy problems). I explain why it does not have a representation in my above answer on representations.

Below: Such a group has soluble word problem because your group is finitely presented and residually finite, which is a very strong property and again is a property possessed by your abstract group. The finite presentability is, perhaps, necessary as there exist residually finite groups which are finitely generated but do not have soluble word problem. so I need it to use this abstract property called "residually finite". On the other hand, matrix groups have soluble word problem and this is closed under subgroups, so really I could just have referred you to that...but then it is less clear that this is a property of the abstract group...

share|cite|improve this answer
Thanks for the detailed answer. – user135186 Apr 9 '14 at 10:02
As I know, permutation representations are preferred for computational purposes (by "HANDBOOK OF COMPUTATIONAL GROUP THEORY" ). Then what's the advantage of free presentations? is it the space needed to store them? – user135186 Apr 9 '14 at 10:06

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.