# Why free presentations?

What is the motivation to study “free” presentations of groups,even though all (or almost all) the questions (or the problems) concerning this type of presentations are known to be undecidable ?

#### Solutions Collecting From Web of "Why free presentations?"

Given a presentation, you know exactly how to describe morphisms out of the group: they’re assignments of group elements to the generators which satisfy the relations. That’s a lot of information. In particular, you can count the number of morphisms from any finitely presented group to any finite group.

More abstractly, a presentation is an efficient description of the covariant functor $\text{Hom}(G, -)$ represented by a group $G$ given by describing $G$ as a colimit of simpler groups (namely the free groups). In general, it’s a good idea in mathematics to try to describe complicated objects in terms of simpler objects.

There is nothing special about free presentations. Rather, undecidability is an intrinsic property of the group (or class of group) not of the way you are looking at it (them).

The best reference I can find for this is the following answer of Benjamin Steinberg to an MO question. Alternatively, you could try analysing the proofs yourself.

Decidability of the word problem for a finitely generated group has nothing to do with a presentation of the group. It is not part of the input. If G is a finitely generated group with solvable word problem and H is a finitely generated group of automorphisms of G, then H has decidable word problem. There exists a Turing machine that knows how the generators of H act on the generators of G (don’t ask me which Turing Machine). This machine can implement the algorithm you give.

It is a common misconception that decidability involves something effective. It merely asserts the existence of a Turing machine. This is why a problem with only finitely many inputs is always decidable even though I may not know which Turing machine is the one that says yes in the right cases.

Finally, he gets to the crux of the problem in a comment.

The strange thing about Turing machines is you can assume they know any finite amount information which is independent of the input even if we ourselves don’t know this information. This is why the word problem doesn’t depend on the choice of finite generating set. I may not know how to write the generators from one set as a word in the generators in the other set, but since there are only finitely many generators, there is a Turing machine that does. Knowing this fixed finite information it can algorithmically rewrite any input word in the other generating set and use its word problem TM.

Now, you ask What is the motivation to study “free” presentations of groups,even though all (or almost all) the questions (or the problems) concerning this type of presentations are known to be undecidable? Well, the cynical answer would be that there was already 30 years of work on this subject before the first “undecidable in general” result was proven! So the behemoth that is geometric and combinatorial group theory had already started. Changing to something “better” would not have been feasible.

The idea of looking at free presentations has been very fruitful though. For example, when Dehn first posed the word problem he proved the following observation relating to the usual presentation of the fundamental groups of closed, orientable surfaces of genus at least two: if $W=_G1$ then there exists a cyclic shift $R$ of the relator or the inverse of the relator of the presentation such that $R=R_0R_1$ with $|R_1|>|R_0|$, and $R_1$ is a subword of $W$. Replacing $R_1$ with $R_0^{-1}$ in $W$ yields a word of strictly shorter length, and of course the same observation still holds. Thus, to decide if a word is trivial one repeatedly applies these replacements, and the word is trivial if and only if it terminates at the trivial word. This algorithm is called “Dehn’s algorithm”. This algorithm was generalised to groups called “small cancellation” groups, but Gromov proved that there was an underlying idea going on here. He proved that a group has a presentation whose word problem is soluble by Dehn’s algorithm if and only if the Cayley graph of the group (with respect to an arbitrary finite generating set) is coarsely hyperbolic. My point is that free presentation can often tell us a lot about the group (and also that they relate to geometry, especially of $3$-manifolds, but I haven’t really said that…but they do).

The small cancellation condition I mention above is a condition of the presentation which you can “see” simply by looking at it (although it is undecidable if a group admits such a presentation). A rather simpler property which you can “see” just by looking at a finite presentation is if the group has more generators than relators (just count ’em!). Then, it is a very nice result of Steve Pride and B. Baumslag that if your group has two more generators than relators then your group has a finite index subgroup which maps onto the free group $F_2$, while Gromov and Stohr independently proved that this holds if your group has one more generator than relator and one of the relators is a proper power. If $G$ has such a finite-index subgroup then it is called “Large” or “as Large as $F_2$”.

Finally, I want to end my rambling with a very interesting problem on undecidability. A one-relator group is a presentation of the form $\langle X; R\rangle$ where $R$ is a word over the letters $X^{\pm1}$. Magnus showed, in 1932, that such groups have soluble word problem. However, the analogous result for one-relator semigroups is still open.