Undecidability in extending partial permutations
by
Benjamin Steinberg
University of Porto
Coauthors: Karl Auinger (University of Vienna)

We show that there exists a pseudovariety U of finite (in fact solvable) groups which has a decidable membership problem, but for which the following problem is undecidable: Given a finite set S of partial permutations of a finite set X as input, does there exist a finite set Y containing X and a collection T of permutations of Y extending S such that T generates a group in the pseudovariety U.

This implies that the pseudovariety of inverse semigroups Sl*U has an undecidable membership problem. It also implies that any pseudovariety of semigroups in the interval [Sl*U, DA malcev LU] has undecidable membership problem. This includes the pseudovariety generated by Schutzenberger products of groups in U.

We can also show that the pseudovariety of semigroups generated by power semigroups of groups in U has an undecidable membership problem. Also the join of the pseudovariety of aperiodic semigroups with U is undecidable. We can, in fact, find a semigroup variety generated by a single cyclic monoid whose join with U is undecidable.

Joins, semidirect products and Malcev products were first shown to not preserve decidability (for semigroups) by resp. Albert, Baldinger and Rhodes (for joins) and Rhodes for the others. But none of these examples involve groups and the proofs are more involved. Also the join results used non-locally finite factors. The results for the power operator and the Schutz. product operator are completely new.

We note that U satisfies no group identities and in fact U contains solvable groups of arbitrary length (we mention that the undecidability of the identity problem for fintie semigroups is used in all the above mentioned results). However, one can find similar decidable pseudovarieties of groups U_n (provided n > 1) such that U_n contains groups of solvable length n, but not n+1, which lead to analogous undecidability results. The author has shown in the past that the extension problem for partial permutations is decidable for any decidable pseudovariety of Abelian groups.

Date received: January 2, 2002