S. I. Adian

ON ALGORITHMIC PROBLEMS IN EFFECTIVELY COMPLETE CLASSES OF GROUPS

(Presented by Academician I. M. Vinogradov, 16 V 1958)

The purpose of the present note is a further generalization of the theorems on undecidable algorithmic problems of group theory \((^{1-3})\). Here we use the notation of papers \((^{2}), (^{3})\). In the first part of the note we give a number of remarks on paper \((^{3})\), making it possible to reconstruct completely the proof of the main lemma of that paper.* From the remarks given below there follows the proof of a somewhat stronger assertion, from which the indicated lemma follows as a consequence. Namely, in the first part the following lemma on the groups \(F_{qA}\) will be proved.

Lemma B. Let the word \(A\) of the group \(F\) contain no letters \(p^\sigma\). If \(A=1\) in the group \(F\), then \(F_{qA}\) is the trivial group. If \(A\ne 1\) in \(F\), then the group \(F\) is a subgroup of the group \(F_{qA}\).

In the second part, using Lemma B, we shall prove some theorems on undecidable algorithmic problems for effectively complete classes of finitely presented groups (briefly: e.-c. groups).

I. Some remarks on paper \((^{3})\). The analogy between the defining relations of the groups \(\mathfrak A_{q,A,B}\), constructed in \((^{2})\), and the defining relations of the groups \(F_{qA}\), constructed in \((^{3})\), is evident. In the defining relations of the groups \(F_{qA}\), the role of the words \(AB^{-1}\equiv pXpX^{+}Y^{+-1}p^{-1}Y^{-1}p^{-1}\) is played by the words \(E\equiv p^2Ap^{-1}Ap^{-1}\). This analogy is deep.

The first two paragraphs of Chapter II of paper \((^{2})\) are devoted to the proof of Lemma 4, § 2, Chapter II. In doing so, a number of auxiliary assertions are used, which are contained in Chapter I. The assertions contained in § 1, Chapter I, are of a general character and may be applied to any group. As for the assertions contained in § 2, Chapter I of paper \((^{2})\), they concern the particular group \(\mathfrak A_p\) and are connected with the features of the construction of this group. Nevertheless, analogous assertions are true for the group \(F=F_0*F'_2*F_3\) constructed in \((^{3})\).

For each of the assertions of § 2, Chapter I of paper \((^{2})\), used in the first two paragraphs of Chapter II, we indicate the corresponding assertion about the group \(F\), which will be used in the proof of Lemma B.

1) Lemma 1, § 2, Chapter I (p. 242). To this lemma there corresponds the following obvious assertion.

Lemma 1*. Let \(D\) be a word of the group \(F\), containing no letters \(p^\sigma\). If \(D=1\) in \(F\), then in the group \(F\) the projections of the word \(D\) onto the alphabets of the groups \(F_0\) and \(F'_2\) are also equal to \(1\).

2) Lemma 3, § 2, Chapter I (p. 243). To this lemma there corresponds Lemma 3 of paper \((^{3})\) (see p. 10). This lemma is also obvious.

* In \((^{3})\), on p. 10, after formula (8) there should follow the line: “where by \(E\) is denoted the word \(p^2Ap^{-1}Ap^{-1}\).”

** Theorem 1 of paper \((^{3})\) was also proved by Rabin in \((^{5})\).

3) Lemma 4, § 2, Ch. I (p. 244). This lemma will be replaced by Lemma 2 of paper (³) (p. 10). The proof of Lemma 2 of paper (³) rests on Lemma 1 of the same paper, which we shall first prove.

Proof of Lemma 1. Let a c.-p. group \(F_2\) be given by generators \(a_1, a_2, \ldots, a_n\) and defining relations \(A_i=1\). As the group \(F'_2\) one may take the group defined by the generators

\[ b_1, b_2, \ldots, b_n, c \tag{1} \]

and defining relations \(B_i=1\), where the word \(B_i\) is obtained from the word \(A_i\) by replacing each letter \(a_j^\sigma\), \(\sigma=\pm1\), occurring in \(A_i\), by the word \((cb_j)^\sigma\). The subgroup of \(F'_2\) generated by all the elements \(cb_j\) is isomorphic to the group \(F_2\). It is also easy to see that the generators (1) have infinite order in \(F'_2\).

Proof of Lemma 2. All generators of the group \(F\) have infinite order in \(F\) (for the generators of the group \(F_0\) this follows from Theorem 2, p. 69, of paper (⁴), and for the generators of the group \(F'_2\) from the lemma just proved; the letter \(p\) does not occur in the defining relations of the group \(F\)). Any two distinct letters of the alphabet of the group \(F\) are generators of different free factors of the group \(F\). Consequently, they will be free generators of the subgroup generated by them in \(F\). Lemma 2 is proved.

4) Lemma \(2'\), § 2, Ch. I (p. 245). This lemma is a consequence of the fact that \(a_n\) and \(a_{n-1}\) are free generators of the subgroup generated by them in \(\mathfrak A_p\). By Lemmas 3 and 2 of paper (³), \(e_k\) and \(e_{k-1}\) are free generators of the subgroup generated by them in \(F\). Hence it follows that in \(F\), for \(e_k\) and \(e_{k-1}\), the assertion of Lemma \(2'\) is true.

5) Lemma 7, § 2, Ch. I (p. 254) may be replaced by the following assertion.

Lemma 7*. Let \(A, C, D\) be arbitrary words of the group \(F\) not containing letters \(p^\sigma\), and let \(A\ne1\) in \(F\). If, moreover,

\[ p^2Ap^{-1}Ap^{-1}DpA^{-1}pA^{-1}p^{-2}C = 1 \quad \text{in } F, \]

then in the group \(F\) the word \(C\) and also the projections of the word \(D\) onto the alphabets of the groups \(F_0\) and \(F'_2\) are equal to 1.

This lemma is a consequence of the fact that \(F_0\), \(F'_2\), and \(F_3=\{p\}\) are free factors of the group \(F\).

6) Lemma 6, § 2, Ch. I, and its corollary (pp. 246 and 253) are replaced by the following lemma.

Lemma 6*. Let the word \(A\) of the group \(F\) contain no letters \(p\) and not be equal to 1 in \(F\). In order that the word

\[ Q \equiv e^{k_1}(p^2Ap^{-1}Ap^{-1})^{s_1} e^{k_2}\ldots e^{k_\mu}(p_2Ap^{-1}Ap^{-1})^{s_\mu} e^{k_{\mu+1}}, \]

where \(e\) is an arbitrary letter of the alphabet of the group \(F\), be equal to 1 in \(F\), it is necessary and sufficient that the corresponding sequence of numbers \(k_1, s_1, k_2, \ldots, k_\mu, s_\mu, k_{\mu+1}\) be degenerate.

Lemma \(6^*\) is proved in the same way as Lemma 6 and its corollary were proved in Ch. I of paper (²).

Thus, for each of the auxiliary assertions concerning the group \(\mathfrak A_p\) (1)—6)), we have the corresponding assertion concerning the group \(F\). Now the proof of Lemma B is obtained by a literal repetition of all the arguments of the first two paragraphs of Chapter II of paper (²).

II. Algorithmic problems in effectively complete classes of groups. By the recognition problem for a group property \(\alpha\) for groups of a class \(K\) we shall mean the problem of finding an algorithm which, for any group of the class \(K\), would decide whether it has the property \(\alpha\).

or not. In works \((^{1-3})\) a special case of such problems was studied, when the class \(K\) coincides with the class of all f.p. groups.

We shall call a class of f.p. groups \(K\) effectively complete if there exists an algorithm \(\mathfrak A\) which transforms a presentation of an arbitrary f.p. group \(F\) into a presentation of such a group from the class \(K\), to some subgroup of which the group \(F\) is isomorphic. In this case we shall call the algorithm \(\mathfrak A\) an algorithm effectively realizing the completeness of the class \(K\). We shall say that the algorithm \(\mathfrak A\) leaves the group \(F_0\) fixed if it transforms any presentation of the group \(F_0\) into a presentation of this same group.

Condition T. We shall say that for the pair \((K,\alpha)\), where \(K\) is some class of f.p. groups and \(\alpha\) is any invariant group-theoretic property, condition T is satisfied if one can indicate an f.p. group \(F_1\) from the class \(K\) possessing the property \(\alpha\), and such an f.p. group \(F_2\) which cannot be embedded in any f.p. group with the property \(\alpha\).

Theorem 1. Let \(K\) be some effectively complete class of f.p. groups. If the invariant property \(\alpha\) is such that condition T is satisfied for the pair \((K,\alpha)\), and the algorithm \(\mathfrak A\), effectively realizing the completeness of the class \(K\), leaves fixed the group \(F_1\) with the property \(\alpha\), then the problem of recognizing the property \(\alpha\) for groups of the class \(K\) is undecidable.

Proof. Consider the group \(F_2\), which by condition T is not embeddable in any f.p. group with the property \(\alpha\). Using Lemma 1 of the paper \((^3)\), embed \(F_2\) in an f.p. group \(F'_2\), all generators of which have infinite order. Next, on the basis of the group \(F=F_0*F'_2*\{p\}\), where \(F_0\) is an f.p. group with unsolvable identity problem, we construct, exactly as indicated in \((^3)^*\), a system of groups \(F_{qA}\). Above we proved that Lemma B is valid for the groups \(F_{qA}\). Let \(F_A=F_{qA}*F_1\), where \(F_1\) is a group of the class \(K\) possessing the property \(\alpha\). Consider the system of groups \(G_A=\mathfrak A(F_A)\), where \(A\) is an arbitrary word of the group \(F_0\). Since the algorithm \(\mathfrak A\) effectively realizes the completeness of the class \(K\), all the groups \(G_A\) belong to the class \(K\). Theorem 1 will be proved if we prove that there is no algorithm which would decide, for every group \(G_A\), whether it has the property \(\alpha\) or not. For this it is enough to prove that \(G_A\) will have the property \(\alpha\) if and only if \(A=1\) in the group \(F_0\).

Let \(A=1\) in \(F_0\). Then \(A=1\) in \(F\). By Lemma B, in this case the group \(F_{qA}\) is trivial. Consequently, \(F_A\) is isomorphic to the group \(F_1\), and hence \(G_A\) is isomorphic to \(F_1\). Then the invariant property \(\alpha\) will hold in \(G_A\).

Let \(A\ne 1\) in \(F_0\). Then \(A\ne 1\) in \(F\). In this case, by Lemma B, the group \(F\) is a subgroup of the group \(F_{qA}\). We have
\[ F_2 \subset F'_2 \subset F \subset F_{qA} \subset F_A \subset \mathfrak A(F_A)=G_A, \]
i.e. the group \(F_2\) is embedded in \(G_A\). Then, by condition T, the group \(G_A\) cannot have the property \(\alpha\). The theorem is proved.

The following special case of Theorem 1 is of interest.

Theorem 2. Let \(K\) be an effectively complete class of f.p. groups whose effective algorithm leaves fixed every group of this class. If the invariant property \(\alpha\) is such that condition T is satisfied for the pair \((K,\alpha)\), then the problem of recognizing the property \(\alpha\) for groups of the class \(K\) is undecidable.

It is easy to see that Theorem 1 of the paper \((^3)\) is a special case of this theorem.

We shall call a class of f.p. groups \(K\) recursive if there exists an algorithm which makes it possible, for any f.p. group, to decide whether it belongs to the class \(K\) or not.

Theorem 3. Let \(K\) be a recursive and effectively complete class of f.p. groups, and let \(\alpha\) be some invariant group-theoretic property. If for the pair \((K,\alpha)\) condition T is satisfied, then the problem of recognizing the property \(\alpha\) for groups of the class \(K\) is undecidable.

* See the footnote on p. 13.

Proof. Let \(\mathfrak N\) be an effectivizing algorithm for the class \(K\), and let \(\mathfrak M\) be an algorithm which makes it possible to check, for any finitely generated group, whether it belongs to the class \(K\) or not. Using these two algorithms, we easily construct an algorithm \(\mathfrak N^*\) which effectivizes the completeness of the class \(K\) and leaves fixed every group of the class \(K\), thereby proving Theorem 3.

As a nontrivial example of a recursive and effectively complete class of finitely generated groups one may indicate the class of finitely generated groups that coincide with their commutator subgroup.

Every system of nontrivial identical relations
\[ L_i \equiv 1 \qquad (i=1,2,\ldots,k), \tag{2} \]
written with the aid of variable symbols \(x_1,x_2,\ldots,x_r\), determines a class of groups that are conditionally trivial with respect to this system of identical relations (see (3), p. 11).

Theorem 4. Let \(K_1\) be the class of groups conditionally trivial with respect to the system of nontrivial identical relations (2). If an invariant group-theoretic property \(\alpha\) is such that the pair \((K_1,\alpha)\) satisfies condition T, then the problem of recognizing the property \(\alpha\) for groups of the class \(K_1\) is unsolvable.

Proof. First embed the group \(F_2\), by Lemma 1 of [3], in a group \(F'_2\), all generators of which have infinite order. At the same time we shall take the group \(F'_2\) so that it contains a free subgroup with two generators \(b_1\) and \(b_2\). Let \(B_1,B_2,\ldots,B_r\) be free generators of the subgroup generated by them in the free group with generators \(b_1\) and \(b_2\). Substitute in the words \(L_i\) everywhere in place of the variables \(x_1,x_2,\ldots,x_r\) the words \(B_1,B_2,\ldots,B_r\). Denote the resulting words of the group \(\{b_1,b_2\}\) by \(Y_i\) \((i=1,2,\ldots,k)\). Since all the identical relations (2) are nontrivial by hypothesis, no \(Y_i\) is equal to \(1\) in the group \(\{b_1,b_2\}\). Hence \(Y_i \ne 1\) also in \(F'_2\). Let \(C\) be an arbitrary word of the group \(F_0\). Put
\[ A=[\ldots[[C,Y_1],Y_2]\ldots Y_k], \tag{3} \]
where the square brackets denote the taking of a commutator. \(A\) is a word of the group
\[ F=F_0*F'_2*\langle \rho\rangle . \]

It is easy to see that \(A=1\) in \(F\) if and only if \(C=1\) in \(F_0\). Therefore there is no algorithm which would check, for any word \(A\) of the form (3), whether it is equal to \(1\) in \(F\) or not. Note also that adding to the relations of the group \(F\) any one of the identical relations (2) turns the corresponding word \(Y_i\) into \(1\), and together with it also the word \(A\).

Now consider the system of groups \(F_{qA}\), constructed in the same way as was done in [3], which correspond to the words (3) for all possible \(C\in F_0\). By Lemma B, each of these groups will be conditionally trivial with respect to the system (2), i.e. all these groups belong to the class \(K_1\). Obviously, every group
\[ F_A=F_{qA}*F_1, \]
where \(F_1\) is a group which, by condition T, belongs to \(K_1\) and has property \(\alpha\), also belongs to the class \(K_1\). Theorem 4 will be proved if we prove that there is no algorithm which would check, for any group \(F_A\), whether it has property \(\alpha\) or not. And for this it is enough to prove that the group \(F_A\) has property \(\alpha\) if and only if \(A=1\) in the group \(F\). This is proved in the same way as in Theorem 1.

Mathematical Institute named after V. A. Steklov
Academy of Sciences of the USSR

Received
15 V 1958

References

1. S. I. Adyan, DAN, 103, No. 4 (1955).
2. S. I. Adyan, Trudy Moskovsk. matem. obshch., 6 (1957).
3. S. I. Adyan, DAN, 117, No. 1 (1957).
4. P. S. Novikov, Trudy Matem. inst. im. V. A. Steklova, 44 (1955).
5. M. Rabin, Ann. Math., 67, No. 1 (1958).