Intereting Posts

Topology from interiors of closed sets?
Dedekind Cuts versus Cauchy Sequences
Prove that $\sum^{n}_{r=0}(-1)^r\cdot \large\frac{\binom{n}{r}}{\binom{r+3}{r}} = \frac{3!}{2(n+3)}$
Using induction to prove that $\sum_{r=1}^n r\cdot r! =(n+1)! -1$
How to prove the Fibonacci sum $\sum \limits_{n=0}^{\infty}\frac{F_n}{p^n} = \frac{p}{p^2-p-1}$
How to verify satisfialibility in a model? (Confusions with Gödel's Completeness Theorem)
Roll an N sided die K times. Let S be the side that appeared most often. What is the expected number of times S appeared?
What exactly IS a line integral?
Can the induced matrix norms be induced by inner products?
About counting number of n-tuples
Why the difference between definitions of the discrete/continuous Fourier transforms?
The dual space of locally integrable function space
TFAE: Completeness Axiom and Monotone Convergence Theorem
Why is $\mathbb{R}/{\sim}$ not first countable at $$, where $x \sim y \Leftrightarrow x = y\text{ or }x,y \in \mathbb{Z}$?
Iterated Limits Schizophrenia

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 ?

- Ring with convolution product
- One-to-one correspondence of ideals in the quotient also extends to prime ideals?
- How to prove this is a field?
- Have $\alpha:G \to H$. If a subgroup $U$ is normal in $H$ prove the pre-image of $U$ is normal in $G$.
- Product of nilpotent ideal and simple module is zero
- Give an example of a noncyclic Abelian group all of whose proper subgroups are cyclic.
- Condition for abelian subgroup to be normal
- Direct limit of $\mathbb{Z}$-homomorphisms
- Ideals of $\mathbb{Z}$ geometrically
- Two questions about equivalence relations

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.

- The speed of the top of a sliding ladder
- Given a solid sphere of radius R, remove a cylinder whose central axis goes through the center of the sphere.
- Compute $\lim_{n\to\infty} \int_{0}^{\pi/4}\tan^n x \ dx$
- Show there is a continuous isomorphism $l_{\infty}\rightarrow \left(l_1\right)^* $
- About the Polya-Knopp-like inequality $\sum_{k=1}^{n}\frac{k^2}{a^2_{1}+\cdots+a^2_{k}}\le\left(\frac{1}{a_{1}}+\cdots+\frac{1}{a_{n}}\right)^2$
- Proving that $ \frac{1}{\sin(45°)\sin(46°)}+\frac{1}{\sin(47°)\sin(48°)}+…+\frac{1}{\sin(133°)\sin(134°)}=\frac{1}{\sin(1°)}$
- Conjectured new primality test for Mersenne numbers
- What's the limit of $\prod_1^\infty \left(1-\frac{1}{2^n}\right)=(1-1/2)(1-1/4)(1-1/8)…$?
- Use the division algorithm to prove that 3|(n³ + 2n) for all n ∈ ℕ
- Inequality. $\sqrt{\frac{11a}{5a+6b}}+\sqrt{\frac{11b}{5b+6c}}+\sqrt{\frac{11c}{5c+6a}} \leq 3$
- Factor $10^n – 1$
- Question about complete orthonormal basis
- Showing that a congruence subgroup is solvable
- Existence of irreducible polynomials over finite field
- Reference books for learning matrices from the beginning?