0
$\begingroup$

There are 4 Tietze transformations and one of them is removal of superfluous relator. Is there a mechanical approach/algorithm for deciding which relators can be removed and which cannot?

$\endgroup$
0

1 Answer 1

2
$\begingroup$

A relator $R_n$ can be removed if it can be derived from the other ones $R_1...R_{n-1}$. In order to check if such derivation is possible you need to check if $R_n=e$ in group $\langle A| R_1...R_{n-1} \rangle$. This is called word problem and is undecidable (so there is no algorithm).

However, you can do something else. If the group is finite, you can use perform enumeration of cosets. This way you can find Cayley graph, Schreier transversal, permutation representation and most importantly a definition table with all relations necessary for the group. While this does not tell you which of the original relations were superfluous, you may use the "definition" column in monitor table to produce a new set of relators.

It is also worth mentioning the Knuth-Benedix algorithm for solving the word problem. You may use it to semi-decide whether a relator is not superfluous, but Knuth-Benedix may fail if the relator is superfluous.

$\endgroup$
1
  • $\begingroup$ I suspect that, even if the original group is trivial, then it is undecidable whether $R_n$ is redundant i.e. whether $\langle A \mid R_1,\ldots,R_{n-1} \rangle$ is trivial - but I am not sure about that. $\endgroup$
    – Derek Holt
    Oct 6 at 9:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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