Algorithmic problems in group theory and elements of recursion theory

Section 1.7 Algorithmic problems in group theory and elements of recursion theory

Our combinatorial approach to group theory naturally turns groups into computational objects: sets of strings with rewriting rules. In the 1920s Max Dehn proposed the following three algorithmic problems:

The word problem: Given a group presentation \(G = \pres X R\) and word \(w(X)\) in the alphabet \(X\) determine if \(w(X)=_G 1\text{.}\)
The conjugacy problem: Given a group presentation \(G = \pres X R\) and words \(w(X),u(X)\) in the alphabet \(X\) determine if there exists some \(g \in G\) such that \(g^{-1}w(X)g=_G u(X).\)
The isomorphism problem: Given two group presentations \(\pres X R\) and \(\pres Y S\) determine if they define isomorphic groups.

First the bad news:

Theorem 1.7.1. The Novikov-Boone theorem.

There exists a finitely presented group \(G=\pres{x_1,\ldots,x_n}{r_1,\ldots,r_m}\) for which the word problem is undecidable.

Let's explain this result in more detail. There exists a group presentation which you can actually write out so that for any algorithm you come up with, for example a computer program written in Python, to determine correctly whether words are equal to the trivial element, there will be a word (in fact many, many words) for which your algorithm will never terminate.

We say a set \(S\) is recursively enumerable or r.e. if there is some algorithm \(\mathfrak A\) which enumerates the elements of \(S\text{.}\)

Proposition 1.7.2. Trivial elements are recursively enumerable.

Let \(G=\pres {x_1,\ldots,x_n}{r_1,\ldots,r_m}\) be a finitely presented group. Then the set

\begin{equation*} \mathcal E = \left\{w(X) \mid w(X) \textrm{ is reduced and } w(X)=_G 1\right\} \end{equation*}

of reduced words equal to \(1\) is recursively enumerable.

Proof.

By Proposition 1.4.2 the set \(\mathcal E\) consists of taking all products

\begin{equation*} \prod_{i=1}^n c_i^{-1}r_{j_i}^{\epsilon_i}c_i \end{equation*}

where \(r_{j_i} \in \{r_1,\cdots,r_m\}, \epsilon_i \in \{\pm 1\}\) and then performing free reduction. Consider the sets \(\mathcal E_N\) consisting of all products consisting of at most \(N\) factors \(c_i^{-1}r_{j_i}c_i\text{,}\) and where each conjugator also has length at most \(N\text{.}\) Then \(\mathcal E_N\) is recursively enumerable for each \(N\) therefore so must the countable union

\begin{equation*} \mathcal E = \bigcup_{N=1}^{\infty} \mathcal E_N. \end{equation*}

Although enumeration seems somewhat contrived, it is fact equivalent the more mathematically natural concept of set membership.

Proposition 1.7.3.

Let \(S\) be a set of strings of symbols in some alphabet \(X\text{.}\) The following are equivalent:

There exists a membership algorithm \(\mathfrak A\) which takes as inputs strings in \(X\) with the following property: \(s \in S\) if and only if \(\mathfrak A\) terminates on the input \(s\text{.}\)
\(S\) is recursively enumerable.

Proof.

Suppose first you are given the algorithm \(\mathfrak A\) as in the statement of the proposition. Let \(w_1,w_2,\ldots\) be an enumeration of the strings in \(X\) and let \(\mathfrak M_N\) be a program which performs the \(N\) first steps of \(\mathfrak A\) on the inputs \(w_1,\ldots,w_N\text{.}\) If one of the parallel processes terminates then \(\mathfrak N\) outputs the string \(w_j\) of the corresponding terminating process. Then our enumeration algorithm is an algorithm which sequentially runs \(\mathfrak N_{1},\mathfrak N_2,\ldots\text{.}\)

Conversely suppose \(S\) is \(r.e.\) and let \(\mathfrak B\) be the enumeration algorithm. Then we can make our membership algorithm \(\mathfrak A\) a follows: gien an input \(s\text{,}\) run \(\mathfrak B\) and wait until \(s\) appears, if it ever does, stop.

Now, in general, when asking

\begin{equation*} x \stackrel{?}{\in} S \end{equation*}

we expect a definitive yes or no answer. So consider the finitely presented group \(G = \pres X R\text{,}\) then the word problem is decidable if and only if \(\mathcal E\text{,}\) the set of reduced words representing \(1\) in \(G\) is r.e. and the set \(F(X)\setminus \mathcal E\) of reduced words not representing the identity is also recursively enumerable. Indeed, in this case, there is a procedure which is guaranteed to terminate on any reduced word and correctly say whether or not the word is trivial.

So how does this work with Theorem 1.7.1? Well Proposition 1.7.2 says that all trivial elements can be enumerated, so what is difficult is to show that some reduced word represents a non-trivial element. This is equivalent to saying that some word cannot be written as a product of conjugates of the relations. Thus, asserting that a word is non-trivial, is a non-existence statement: there does not exist a product of conjugates of relators that is freely equal to some word.

It is a common theme in mathematics that non-existence proofs are difficult. One of the triumphs of geometric group theory is that we can solve all three of Dehn's problems for many interesting classes of groups. Next lecture we will do this for free groups.

Exercises 1.7.1 Exercises

1.

Show that the word problem is solvable for \(F(X)\text{,}\) the free group on the alphabet \(X\text{.}\)

Hint: This problem is not difficult.

2.

The equality problem for \(G = \pres X R\) is do decide, given two words, whether:

\begin{equation*} u \stackrel ? = w. \end{equation*}

Show that solvability of the equality problem is equivalent to solvability of the word problem.

3.

The conjugacy search problem is a variation of the conjugacy problem which, given elements \(h,k\text{,}\) not only outputs YES or NO to the question of whether they are conjugate, but, if YES, will also produce an element such that

\begin{equation*} g^{-1}hg = k \end{equation*}

Show that solvability of the conjugacy search problem is equivalent to solvability of the conjugacy problem.

4.

Let \(G = \pres X R\) be a finite presentation.

Show that (up to relabeling the generators) the set of all finite presentations which define groups isomorphic to \(G\) is recursively enumerable.

5.

We say that \(G = \pres X R \) is recursively presented if there are algorithms \(\mathfrak{X}\) and \(\mathfrak{R}\) which enumerate the sets \(X=\{x_1,x_2,\ldots\}\) and \(R=\{r_1,r_2,\ldots\}\) (respectively.)

Show that if \(G = \pres X R\) is a recursive presentation, then the set of finite words is recursively enumerable.