Short Communication, Res Rep Math Vol: 2 Issue: 4

# Two Algorithmic Problems in Group Theory

**Alexander P Goryushkin ^{*}**

Department of Mathematics and Physics, Kamchatka State University, Russia

***Corresponding Author :** **Alexander P Goryushkin**

Professor, Department of Mathematics and Physics, Kamchatka State University, Petropavlovsk- Kamchatsky, Russia** E-mail:** [email protected]

**Received:** August 16, 2018 **Accepted:** December 18, 2018 **Published:** December 25, 2018

**Citation:** *Goryushkin AP (2018) Two Algorithmic Problems in Group Theory. Res Rep Math 2:4.*

## Abstract

For individual classes of groups, a relationship is established between the existence of an algorithm for calculating the index of a subgroup and the algorithm for solving the problem of occurrence.

### Keywords: Direct product; Almost free group; Algorithmic problem; Solvability; Occurrence problem; Index problem

## Introduction

In recent years, difficult algorithmic problems in group theory have found practical application in cryptography. A difficult or even algorithmically unsolvable group-theoretic problem can be a reliable basis for cryptographic protection of the protocol. For cryptographic applications, the classical problems of Dan (the word problem, the conjugacy problem and the isomorphism problem) are of interest, and the algorithmic problems in group theory that are closely related to the classical ones. Such are the problem of the occurrence and the problem of the index.

The occurrence problem for a finitely presented group G consists in finding or proving the impossibility of an algorithm that for any finite set of elements *hi (i = 1, 2, ..., m)* and w would know whether or not the element w belongs to the subgroup *H = rp (h1 , h2, ..., hm)* generated by the elements hi . From the algorithmic solvability of the problem of occurrence follows the solvability of the problem of equality. Therefore, the problem of occurrence is also called the generalized equality problem.

The index problem for a finitely presented group G consists in finding an algorithm that, for any finite set of elements *hi (i = 1, 2, ..., m)* of G , would recognize that a finite or infinite index in G has a subgroup *H = gr (h1, h2 , ..., hm)* generated by this set.

A finitely generated group contains only a finite number of subgroups for every given finite index. Therefore, if the problem of occurrence and the index problem are solvable in G , then having obtained information that the index of the subgroup H in G is finite, it is possible to calculate this index in a finite number of steps by a simple search of subgroups of finite index (for a description of such an algorithm see, for example, [1]).

For a particular group *G*, computing its order is not a mass problem. However, if *G* is infinite, then there are subgroups of infinite and finite indices. Such indices have, for example, trivial subgroups, but it is possible that in *G* there are other subgroups, both finite and infinite index. If *G* is an infinite simple finitely presented group, then the solvability of the index problem follows from the solvability in *G* of the occurrence problem, since in this group only one subgroup of finite index is itself *G*.

However, the reverse situation with simple groups is more complicated. It was shown in [2] that every countable group is isomorphically embeddable in a two-generated simple group. In particular, a finitely presented group *S* with an unsolvable problem of equality (and hence an unsolvable entry problem) is also isomorphically imbedded in a simple two-generated group *G*. In each recursively defined simple group, the word problem is solvable [3]. This means that a two-generated simple group containing such a group *S* is not only not definite, it cannot even be recursively represented.

The classical Kronecker-Capelli theorem of linear algebra is essentially an algorithm for solving the problem of entering into a subspace of a finite-dimensional vector space. This algorithm consists in calculating the smallest possible number of elements in the generating system. This number - dimension - is found by means of a sequence of changes in the generating set of the subspace and its transformation into a basis.

To find the index of a finitely generated subgroup *H*, in the same way one can find a generating set *H* consisting of the smallest number of elements. The generating set of a subgroup is modified by means of elementary transformations analogous to elementary transformations of the generating set of a subspace of a vector space:

(1) replacing the element *x* by *x*^{-1};

(2) replacing the element *x* by an element *x y*, where *x **≠** y*;

(3) removal of a single element.

If as a result of such transformations a single element appears, then this unit from the generating set can be deleted.

Let *H = gr (h*_{1}*, h*_{2}*, ..., h*_{m}*)* be a finitely generated subgroup of the free group *F*_{n}. A system of free generators for a subgroup H is called a basis, and the number of elements in a basis is called a rank. This basis is the Nilsen set of generators see, for example, [4]. Let *R* be some set of elements from the free group *F*_{r} written in the reduced, that is, irreducible, form. Elements of the set *R* are words in the alphabet *a*_{1}, *a*_{2}, ..., *a*_{r} and their inverses, and abbreviations inside words are impossible. The symbol *R*^{-1} denotes all the inverse elements of *R.* A word *w* in *F*r is said to be isolated with respect to the set *R* if there is at most one element *v* in *R* ´ *R*^{-1} such that w is an initial or terminal subword for *v*. The leading beginning of the word *v* is the initial subword s of the word *v* whose length satisfies the inequality

Similarly, the leading end of the word *v* is defined.

The set *R* of non-unitary, incontractible words is said to be Nielsen if:

1) the older beginnings and the upper ends of all words from *R* are isolated;

2) for each word of even length, at least one of its halves - left or right - is isolated.

Using the transformations (1) - (3) of the generating set in a finite number of steps, one can obtain the Nilsen generators for the subgroup *H*, and thus find the rank of *H*. This method of obtaining free generating subgroups of free is usually called the Nielsen method.

Using the Nielsen method, it is possible in a finite number of steps to find out whether an element of the free group enters or does not belong to a given finite generated subgroup, that is, the occurrence problem for free groups is algorithmically solvable.

Otto Schreyer, using not only the generating elements of a subgroup, but also representatives of adjacent classes, established a connection between the index of a subgroup of a free group, the rank of this subgroup, and the rank of the original free group, see, for example, [4]. If a subgroup *H* of rank *k* has finite index in a free non-cyclic group of rank r, then this index is equal to

Using the Schreier formula, the index problem of a subgroup of a free group reduces to calculating the rank of a subgroup, which can be found using the Nielsen method.

Thus, the index problem for a free group is also algorithmically solvable.

We call a group *G* almost free if it contains as a subgroup of finite index a free non-cyclic group *F*. If a finitely presented group *G* is almost free, then its free subgroup *F* has finite rank; in addition, we can assume that *F* is normal in *G*.

The solution of both problems under discussion for an almost free group is reduced to solving this problem for the free part *F*.

In an almost free group, both the index problem and the problem of occurrence are solvable.

A free group is a free product of infinite cyclic groups. In an infinite cyclic group, both problems were algorithmically solvable, and both of them were inherited under a free product.

Let us now consider another important group-theoretic construction-the direct product.

Each element of the direct product A × B has a representation in the form of the product ab, where a × A and b × B.

The element ab is equal to one if and only if a and b are both single. This means that if the equality problem is algorithmically solvable in groups A, B, then this problem is solvable in the direct product A×B. In other words, the solvability of the equality problem is inherited by the direct product. The solvability of the index problem in such a construction may not be inherited.

## Theorem

In the direct product of two almost free groups, the index problem is algorithmically unsolvable.

**Evidence**

Let groups *A* and *B* be two almost free groups. The group *A* contains, as a normal subgroup of finite index, a free subgroup *A*1 of rank *m*; and the elements *a*_{1}, *a*_{2}, ..., *a*_{m} are free generators for *A*_{1}. Similarly, the group *B* contains a normal subgroup *B*_{1}, where B1 is free of rank m and *b*_{1}, *b*_{2}, ..., *b*_{m}-ee are its free generators. In addition, both indices are finite.

If the group *G* = *A*×*B* is a direct product of the groups *A* and *B*, then its subgroup *G*_{1} generated by the subgroups *A*_{1} and *B*_{1} forms a direct product:

*G*_{1} = *A*_{1} × *B*_{1}

The index *G*_{1} in *G* is equal to , and is therefore finite.

We now consider an arbitrary finitely presented group *R* given by the representation

where *r*_{1}, *r*_{2}, ..., *r*_{k} are generating elements, and *w*_{1} (*r*_{i}), ..., *w*_{n} (*r*_{i}) are defining relations. Recall that the defining relation is a word in the alphabet *r*_{1}, *r*_{2}, ..., *r*_{k}, In the group A1 we choose a subgroup P of index s in A1 such that inequality

Then by the Schreier formula the rank of the subgroup *P* is equal to *s* (*m* − 1 + 1,and this number is not less than *k*. If the rank of the subgroup *P* turns out to be strictly greater than *k*, then the representation of the group R is supplemented by *s-k* generators and equates these elements to unity. Without loss of generality, we can assume that this has already been done, that is, *s* = *k*.

Let the elements *p*_{1}, *p*_{2}, ..., *p*_{k} freely generate the subgroup P. In the group B_{1} we choose a subgroup *Q* of rank *k*, of index sin *B*1 and with free generators *q*_{1}, *q*_{2}, ..., *q*_{k}.

We now consider two normal subgroups, one in the group *P* and the other in *Q*. In the group *P*, the normal subgroup *N*_{1} generated by the elements *w*1 (*r*_{i}), ..., *w*_{n} (*r*_{i}), and in the group *Q* the normal subgroup *N*_{2} generated by the elements *w*_{1} ( *q*_{i}), ..., w_{n} (*q*_{i}). More precisely,

*N*_{1}* = < w*_{1}*(r*_{i}*), …, w*_{n}*(r*_{i}*) >P;*

*N*_{1}* = < w*_{1}*(r*_{i}*), …, w*_{n}*(r*_{i}*) >P;*

In the group G1 we take two subgroups:

*H*_{1}*= гр(w*_{1}*(q*_{i}*), …, w*_{n}*(q*_{i}*), p*_{1}*q*_{1}*, …, p*_{k}*q*_{k}*);*

*H*2* = гр(w*_{1}*(p*_{i}*), …, w*_{n}*(p*_{i}*), p*_{1}*q*_{1}*, …, p*_{k}*q*_{k}*).*

The elements *r*i*, q*i lie in different direct factors of *G*_{1}, therefore they commute:

*r*_{i}* q*_{i} * = q _{i} r*

_{i}

*.*

This means that for any word *j* the equality

*φ**(p*_{i}*q*_{i}*) = **φ**(p*_{i}*) **φ(q*_{i}*).*

The conjugation of the element w_{j}* (p*_{i}*) *by means of an element of *H*_{1} is equal to the corresponding conjugation by means of an element of the subgroup *A*. Hence it follows that the subgroup *H*_{1} contains *N*_{1}. Similarly, *H*_{2} includes *N*_{2}.

In addition, the subgroups *H*_{1} and *H*_{2} themselves coincide. Let *H = H*_{1}* = H*_{2}; then:

*H **∩** P = N*_{1}*;*

*H **∩** Q = N*_{2}.

The Hasse diagram for the inclusion of subgroups [**Figure 1**] represents all the links between all these groups. If the subgroup *H* has a finite index in the direct product *A *×* B*, then the index *H* in the subgroup *A*_{1}×* B*1is also finite, which means that the indices *N*_{1} and *N*_{2} are finite in the subgroups *P* and *Q*, respectively. This means that the group *R* is finite. Conversely, if the group *R* is finite, then the indices *N*_{1} and *N*_{2} in the subgroups *P* and *Q* are also finite; but *P* and *Q* are subgroups of finite index in direct factors, and hence the index is [*G*_{1}* :H*] finite, and [*G :H*] therefore also finite.

In other words, the index problem in the group G is equivalent to the finiteness problem in the class of all finitely presented groups.

The finiteness problem for groups is algorithmically unsolvable [5], and, hence, the index problem for a finitely determined group is also algorithmically undecidable.

The assertion is proved.

Algorithmic unsolvability of the problem means that there is no machine solution for such a problem. For example, no technique will ever be able to answer the question, whether a finite or infinite index of an arbitrarily chosen finitely generated subgroup in the group *F*_{2}×*F*_{2}, given by the representation

We note that in some cases the calculation of the index of a finitely generated subgroup in a finitely determined group can be entrusted to the technique. True, the result can be obtained, as a rule, only in the case of a finite (and relatively small) index of the subgroup. Computer calculations of this kind associated with the solution of specific problems in group theory are presented in [6-9].

For the direct product of two free groups of the second rank, the problem of occurrence is also unsolvable [10]. The proof of this assertion in [9], carried out for only one group *F*_{2} ×* F*_{2}, is also carried over to the general case of a direct product of almost free non-cyclic groups.

Thus, there arises an infinite series of finitely presented groups for which the occurrence problem and the index problem turn out to be equivalent - both are undecidable.

On the other hand, in an almost free group both problems: both the problem of occurrence and the index problem are algorithmically solvable. It is known that a free product inherits the solvability of the problem of occurrence [11].

Using Nielsen's method, which was improved by the Moldovan method [12], it can be shown (see, for example, [1]) that for the solvability of the index problem in the free product *A*×*B*, the solvability of the occurrence problem in groups is sufficient.

This sufficient condition for the existence of an algorithm that computes the index of a subgroup is also necessary: If the index problem is solvable in a nontrivial free product *A*×*B*, then the occurrence problem is solvable in the free factors *A* and *B*.

The algorithm from [1] that solves the index problem in the free product *A*×*B* does not use the solvability of the index problem in the factors *A* and *B*. Therefore, the natural question arises: is it true that the decidability of the index problem in free factors follows the solvability of the index problem in the free product ?

The converse is also interesting: is it true that the decidability of the index problem in a free product implies the solvability of the index problem in free multipliers?

From positive answers to both questions, the following statement would follow: in the class of finitely presented groups the problem of occurrence is algorithmically equivalent to the index problem.

## References

- Goryushkin A (2012) Amalgamated free products of groups. Fed University, Vladivostok: Publishing house Dalnevost, Russia.
- Goryushkin AP (1974) Imbedding of countable groups in 2-generated simple groups. Mathematical Notes. 16: 725-727.
- Kuznetsov AV (1958) Algorithms as operations in algebraic systems. Uspekhi Mat. Nauk 13: 240-241.
- Lyndon RC, Shupp PE (1980) Combinatorial group theory Mir 12: 448.
- Adyan SI (1955) Algorithmic unsolvability of recognition problems for certain properties of groups, Dokl. Academy of Sciences of the USSR 103: 533-535.
- Goriushkin AP (2013) Features of computer research of discrete group. Ser Phys Math Science 1: 43-55.
- Goryushkin A (2011) The machine solution of problems of discrete mathematics. Ser Phys Math Science 2: 58-68.
- Goryushkin AP (2010) On groups with the representation. Ser Fiz Mat Science 1: 8-11.
- Goryushkin A (2011) Elements of Abstract and Computer Algebra: A Tutorial. Petropavlovsk-Kamchatsky: KamSU them Vitus Bering.
- Mikhailova KA (1968) The occurrence problem for free products of groups. Matematicheskii Sbornik 117: 199-210.
- Mikhailova SA (1968) The problem of occurrence for free products of groups. Mat Coll 2: 199-210.
- Moldavansky DI (1969) Nielsen's method for the free product of groups. Uch Zap Ivanov state ped Institute 61: 170-182.