# Why free presentations ? Why not permutation or matrix representations?

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 ?

-
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

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.

-

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...

-
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