Irreducibility of certain pseudovarieties^{1}

S. Margolis

Department of Mathematics and Computer Science Bar Ilan University 52900 Ramat Gan – Israel

margolis@bimacs.cs.biu.ac.il

M. Sapir

Department of Mathematics and Statistics Center for Communic. and Inform. Science University of Nebraska-Lincoln Lincoln, NE 68588 – USA

mvs@unlinfo.unl.edu

P. Weil

LITP, IBP

Université Paris-VI et CNRS 4 place Jussieu 75252 Paris Cedex 05 – France

                                               weil@litp.ibp.fr

Abstract

We prove that the pseudovarieties of all finite semigroups, and of all aperiodic finite semigroups are irreducible for join, for semidirect product and for Mal’cev product. In particular, these pseudovarieties do not admit maximal proper subpseudovarieties. More generally, analogous results are proved for the pseudovariety of all finite semigroups all of whose subgroups are in a fixed pseudovariety of groups H, provided that H is closed under semidirect product.

Résumé

Nous prouvons que la pseudovariété de tous les semigroupes finis, et celle de tous les semigroupes apériodiques finis sont irréductibles pour le sup, pour le produit semidirect et pour le produit de Mal’cev. En particulier, ces pseudovariétés n’admettent pas de sous-pseudovariété maximale propre. Des résultats analogues sont établis plus généralement pour la pseudovariété de tous les semigroupes finis sont dans une pseudovariété de groupes fixée H, pourvu que H soit fermée par produit semidirect.

1The two first authors were partially supported by NSF Grant DMS920381. Part of this work was done while the second author was an invited Professor at the Université Paris-VI. The third author was partially supported by the PRC Mathématique et Informatique (MESR). All three authors were partially supported by the Center for Communication and Information Science of the University of Nebraska.

Within the context of the general study of the structure of the lattice of pseudovarieties of finite semigroups, the question of describing the irreducible pseudovarieties is both a natural and an old problem. For instance, only a handful of the “classical” pseudovarieties are known to be join-irreducible or join-reducible (see [1, chap. 9]). In particular, the pseudovariety of nilpotent semigroups is join-irreducible, whereas J, the pseudovariety of J -trivial semigroups, is join-reducible (Almeida [2]).

In this paper, we show that if H is a pseudovariety of groups closed under semidirect product, then the pseudovariety of all semigroups all of whose subgroups are in H is irreducible for join, for semidirect product and for Mal’cev product. The particular cases where H is the pseudovariety of all groups, and where H is trivial yield the irreducibility of S, the pseudovariety of all finite semigroups, and of A, the pseudovariety of aperiodic semigroups. As a consequence, it follows that these pseudovarieties do not contain maximal proper subpseudovarieties, a fact which generalizes a result of Margolis [11].

If we consider the analogous problem for S and G, respectively the variety of all semigroups and the variety of all groups, it is known that S is join irreducible (Evans [6]) but that S = Com ◯^{m} Com = Com ∗ Com where Com is the variety of all commutative semigroups: the first equality is immediate when one considers the projection from the free semigroup onto the free commutative semigroup; the second one follows from a result of Mal’cev stating that the free semigroup on 2 generators is embedded in the free metabelian group [10]. It is also known that G is irreducible for join, semidirect product and Mal’cev product [12].

The proof of the join irreducibility of S is based on the manipulation of identities, and cannot be used directly for pseudovarieties. However, it is known that each subpseudovariety of a pseudovariety V is defined by a set of formal equalities between elements of certain relatively free profinite structures (Reiterman’s theorem, see [1, 16, 19]). We call these formal equalities pro-V-identities. They are also called pseudoidentities [1]. Formal definitions are given in Section 1.1.

In order to prove that a pseudovariety V is join (resp. semidirectly, Mal’cev) irreducible, we use an idea inspired by Evans’s proof. It is enough to prove the following:

From every pair of pro-V-identities u_{1} = v_{1} and u_{2} = v_{2} which are non trivial, i.e. which define proper subpseudovarieties V_{1} and V_{2} of V, we can contruct a non trivial pro-V-identity which holds in V_{1} ∨ V_{2} (resp. V_{1} ∗ V_{2}, V_{1} ◯^{m} V_{2}). This is done in several steps, each of which consists in constructing non trivial con-

sequences of u_{1} = v_{1} and u_{2} = v_{2} with some special properties. These consequences are obtained by encoding u_{1} = v_{1} and u_{2} = v_{2}. That is, we substitute given values for the variables of the given pro-V-identities in such a way that the resulting pro-V-identities are again non trivial. The main result is proved in Section 3.

1 Preliminaries

Here we review some elementary definitions on pseudovarieties, profinite semigroups and pro-identities. We also remind the reader of the definition of unambiguous relation semigroups and of the unambiguous product of semigroups (Sakarovitch [20]). This product will appear in the proof of several of our intermediary results.

1.1 Pro-identities and pseudovarieties

A class V of finite semigroups is called a pseudovariety if it is closed under taking subsemigroups, homomorphic images and finite direct products. For classical results concerning semigroups and pseudovarieties, and in particular for the definitions of the semidirect product S ∗ T and the wreath product S ∘ T of semigroups, and of the product V ∗ W of pseudovarieties, the reader is referred to the treatises [5, 13, 1].

If V and W are pseudovarieties, the Mal’cev product V ◯^{m} W is the pseudovariety generated by the semigroups S such that there exists a morphism π: S → T, with T ∈ W and eπ^{−1} ∈ V for each idempotent e of T.

If S is a semigroup, we let S^{1} be the monoid equal to S, if S has an identity, and to S ∪ {1} otherwise. Following Eilenberg, we say that a pseudovariety of semigroups is monoidal if it is generated by monoids, or equivalently, if S^{1} ∈ V for each S ∈ V [5, Prop. V.1.2].

If V is a pseudovariety of semigroups, a semigroup is said to be pro-V if it is a projective limit of semigroups of V. A topological semigroup is pro-V if and only if it is compact, 0-dimensional and all its finite continuous homomorphic images are in V. Let A be a finite set, or alphabet. We denote by A^{+} the free semigroup on A and by F̂_{A}(V) the projective limit of the A-generated elements of V. The main properties of these semigroups for our purposes are summarized in the next proposition [1, 3]. They will be used freely in the sequel.

Proposition 1.1 Let A be an alphabet and let V be a non trivial pseudovariety.

• There exists a natural injective mapping ι: A → F̂_{A}(V) such that Aι generates a dense subsemigroup of F̂_{A}(V).

• F̂_{A}(V) is the free pro-V semigroup over A: if σ is a mapping from A into a pro-V semigroup S, then σ admits a unique continuous extension σ̂: F̂_{A}(V) → S such that σ = ισ̂.

• A finite semigroup is in V if and only if it is a continuous homomorphic image of F̂_{A}(V) for some alphabet A.

Whenever convenient, the mapping ι: A → F̂_{A}(V) is ignored, and A is considered as a subset of F̂_{A}(V).

Observe that, if W is a subpseudovariety of V, then every pro-W semigroup is also pro-V. In particular, the identity on A induces a continuous onto morphism π: F̂_{A}(V) → F̂_{A}(W), called the natural projection of F̂_{A}(V) onto F̂_{A}(W).

Let us fix some notation. For each alphabet A and for each x ∈ F̂_{A}(V), the sequence (x^{n!})_{n} converges in F̂_{A}(V), and we denote by x^{ω} its limit: x^{ω} is the only idempotent in the topological closure of the subsemigroup generated by x [1]. Let A be a n-letter alphabet, A = {a_{1}, …, a_{n}}, let B be an alphabet, and let x_{1}, …, x_{n} ∈ F̂_{B}(V). If u ∈ F̂_{A}(V), we denote by u(x_{1}, …, x_{n}) the image of u under the continuous morphism φ: F̂_{A}(V) → F̂_{B}(V) defined by letting a_{i}φ = x_{i} for 1 ≤ i ≤ n.

A pro-V-identity on the set of variables A (or in |A| variables) is a pair (u, v) of elements of F̂_{A}(V). It is usually denoted u = v. It is said to be non trivial if the elements u and v are distinct. We say that u = v is an identity, or word identity, if u and v are words, i.e. finite products of elements of A, or elements of A^{+}ι. If the pseudovariety V is understood, we also say pro-identity for pro-V-identity.

A semigroup S ∈ V satisfies the pro-V-identity u = v if, for any continuous morphism σ: F̂_{A}(V) → S, one has uσ = vσ. Let Σ be a set of pro-V-identities. A subclass W of V satisfies Σ if each element of W satisfies each element of Σ. It is defined by Σ if it consists of all the elements of V which satisfy Σ. Reiterman proved the following fundamental theorem [19].

Theorem 1.2 Let V be a pseudovariety and let W be a subclass of V. Then W is a pseudovariety if and only if it is defined by a set of pro-V-identities. In particular, every proper subpseudovariety of V satisfies some non trivial pro-V-identity.

1.2 Unambiguous and wreath products

A semigroup of relations is a pair (Q, R) where Q is a finite set and R is a semigroup of Q × Q Boolean matrices. Let A be a (possibly non deterministic) automaton over the alphabet A with state set Q and let u be a word in A^{+}. The transition labeled by u, denoted uρ, is the Q × Q Boolean matrix whose (p, q)-entry is 1 if there is a path labeled u in A, and 0 otherwise (p, q ∈ Q). The set A^{+}ρ is a subsemigroup of the set of all Q × Q Boolean matrices, and (Q, A^{+}ρ) is called the transition semigroup of A. In addition, ρ is a morphism, called the transition morphism of A.

A semigroup of relations (Q, R) is said to be unambiguous if, for any elements s, t ∈ R and for any pair (p, q) corresponding to a non-zero entry in st, there exists a unique element r ∈ Q such that the entries (p, r) of s and (r, q) of t are non zero. The notion of unambiguous relation semigroup is closely associated with that of a code, that is, of a free set of generators of a free subsemigroup of the free semigroup. More precisely, let A be a finite automaton with one initial-terminal vertex 1, and such that each state is visited along some successful path (trim automaton). Let us also assume that each word labeling a path from 1 to 1 and not visiting 1 as an internal state of that path, labels exactly one such path. Let C be the set of those words. Then A recognizes C^{+}. Moreover the transition semigroup of A is unambiguous if and only if C is a code [4, Prop. IV.1.5 and IV.1.7].

If (Q, R) is an unambiguous relation semigroup, we can define, for each semigroup S, a semigroup S ◯^{u} (Q, R) by considering the set of all Q×Q matrices with entries in S ∪{0} (with 0 a new zero) obtained from the matrices in R by replacing the non zero entries by arbitrary elements of S. The usual matrix multiplication makes S ◯^{u} (Q, R) into a semigroup, called the unambiguous product of S and (Q, R). Note that, in the particular case where (Q, R) is a semigroup of partial functions, S ◯^{u} (Q, R) coincides with the wreath product as it is defined by Eilenberg [5] (see [20]), and S ◯^{u} (Q, R) is a semidirect product of the form S^{k} ∗ R for some integer k [5, Cor. V.4.3]. Here S^{k} is the direct product of k copies of S.

If V and W are pseudovarieties, we let V ◯^{u} W be the pseudovariety generated by the semigroups of the form V ◯^{u} (Q, W) where V ∈ V and (Q, W) is a semigroup of unambiguous relations with W ∈ W.

Let us also note the following result [22, Prop. 3.4].

Lemma 1.3 Let S be a finite semigroup and let (Q, R) be a semigroup of unambiguous relations, with Q finite. Then every group G in S ◯^{u} (Q, R) admits a normal subgroup K dividing a finite direct product of copies of S, such that G/K divides R.

1.3 Pseudovarieties of the form \overline{H}

If H is a pseudovariety of groups, we denote by \overline{H} the pseudovariety of all semigroups, all of whose subgroups are in H.

It is clear that \overline{H} is monoidal, and that it contains A, the pseudovariety of aperiodic semigroups. In fact, A = \overline{I}, where I is the trivial pseudovariety. Moreover, Lemma 1.3 shows that \overline{H} = \overline{H} ◯^{u} A. In addition, if H is closed under semidirect product, then \overline{H} is closed under semidirect product, and \overline{H} = \overline{H} ◯^{u} \overline{H}.

2 Pro-V codes

Let A and B be alphabets, and for each a ∈ A, let k_{a} ∈ F̂_{B}(V). By Theorem 1.1, there is a unique continuous morphism κ: F̂_{A}(V) → F̂_{B}(V) such that aκ = k_{a} for each a ∈ A. It is easy to verify that if a semigroup S ∈ V satisfies a pro-V-identity u = v with u, v ∈ F̂_{A}(V), then it satisfies the pro-V-identity uκ = vκ.

In analogy with the terminology concerning the free semigroup (see [4]), we say that the morphism κ is a pro-V coding morphism if it is one-to-one. In this case, we call Aκ a pro-V code. This means exactly that the κ-image of a non trivial pro-V-identity is also non trivial.

2.1 Word codes and pro-V codes

Let A and B be alphabets, and let κ: A^{+} → B^{+} be an injective morphism. The morphism κ admits a unique continuous extension to a morphism from F̂_{A}(V) into F̂_{B}(V), also denoted by κ. Moreover, the set C = Aκ is a (word) code, that is C freely generates a free subsemigroup of B^{+} (namely C^{+}). If the syntactic semigroup of C^{+} belongs to a pseudovariety V, we say that C is a V-code.

In this section, we find a sufficient condition for a word code to be a pro-V code as well.

Let P be the set of proper prefixes of the words of C, that is,

P = {w ∈ B^{∗} | wx ∈ C for some x ∈ B^{+}}.

In particular, 1 ∈ P. The sagittal automaton of C is the automaton with state set P, initial and terminal state 1, and with transitions defined, for each letter b ∈ B, as follows: there is a b-labelled arrow from p to q (p, q ∈ P) if, either q = pb, or q = 1 and pb ∈ C. The transition semigroup of this automaton, denoted Sag(C), is called the sagittal semigroup of C. Since C is a code, the sagittal automaton of C is unambiguous, and (P, Sag(C)) is a semigroup of unambiguous relations [4].

In the particular case where C is a prefix code, that is, no word of C is a proper prefix of another word of C, it is easily verified that the sagittal automaton of C is deterministic, so that the relation semigroup (P, Sag(C)) is a transformation semigroup.

The sagittal semigroup of C is close to the syntactic semigroup of C^{+}. In fact, if the syntactic semigroup of C^{+} lies in a pseudovariety V, then Sag(C) ∈ LI ◯^{m} V where LI is the pseudovariety of all semigroups S such that eSe = e for each idempotent e of S [9].

By adapting the proof of [15, Prop. 4.3], we get the following encoding result.

Proposition 2.1 Let A and B be alphabets, let κ: A^{+} → B^{+} be an injective morphism and let (P, Sag(C)) be the sagittal relation semigroup of the code C = Aκ. If V is a monoidal pseudovariety such that S ◯^{u} (P, Sag(C)) ∈ V for each S ∈ V, then the continuous morphism κ: F̂_{A}(V) → F̂_{B}(V) is injective as well, that is, C is a pro-V code.

Proof. Let u and v be distinct elements of F̂_{A}(V). Then, there exists a semigroup S ∈ V and a continuous morphism σ: F̂_{A}(V) → S such that uσ ≠ vσ. Let ρ: F̂_{B}(V) → Sag(C) be the continuous extension of the transition morphism of the sagittal automaton of C. By hypothesis, S^{1} ◯^{u} (P, Sag(C)) lies in V. We define a continuous morphism τ from F̂_{B}(V) into S^{1} ◯^{u} (P, Sag(C)) by letting, for each letter b ∈ B, bτ be the matrix obtained from bρ by replacing the non zero entries on pairs of the form (p, pb) (p, pb ∈ Aκ) by 1 ∈ S^{1}, and the non zero entries on pairs of the form (p, 1) (p ∈ P and pb = aκ, a ∈ A) by aσ. For each word w = a_{1} ⋯ a_{n} ∈ A^{+}, it is easily verified that wκτ has its (1, 1) entry equal to wσ. By continuity, the same equality holds for all elements w ∈ F̂_{A}(V), since they are limits of sequences of words. Therefore uκτ ≠ vκτ, and hence uκ ≠ vκ. Thus κ is a pro-V coding morphism. ⊓ ⊔

The following consequence of this proposition is easily derived.

Corollary 2.2 Let H be a pseudovariety of groups closed under semidirect product. Then every finite \overline{H}-code is a pro-\overline{H} code. In particular, every finite code is a pro-S code and every finite aperiodic code is a pro-A code.

Note. In [8, Thm. 1], Koryakov shows that the n-element code C_{n} = {y, xy, …, x^{n−1}y} is a pro-\overline{H} code for any pseudovariety of groups H. It is easily verified that C_{n} is an aperiodic code for all n, so this result follows from the above corollary. In the same paper, Koryakov uses the resulting continuous one-to-one morphisms from the n-generated free pro-\overline{H} semigroups F̂_{n}(\overline{H}) into F̂_{2}(\overline{H}) to construct a continuous one-to-one morphism from F̃_{ω}(\overline{H}) (the inductive limit of the F̂_{n}(\overline{H})) into F̂_{2}(\overline{H}) with open image.

Examples. The sufficient condition in Proposition 2.1 is not necessary. Let indeed N denote the pseudovariety of nilpotent semigroups, N = [[x^{ω}y = yx^{ω} = x^{ω}]]. Then F̂_{A}(N) = A^{+} ∪ {0} (see [1]) and it is easily verified that every word code is a pro-N code.

Since every one-generated aperiodic semigroup is also nilpotent, for each one-letter alphabet {a}, we have F̂_{{a}}(A) = a^{+} ∪ {0}. It is then also easily verified that each non empty word a^{k} constitutes a code, whose sagittal semigroup is the k-element cyclic group, and which is also a pro-A code.

However, not every word code is pro-A. A counterexample is given by the word code {aa, ab, ba, bb}. Let indeed B = {x, y, z, t} and let κ: F̂_{B}(A) → F̂_{{a,b}}(A) be given by xκ = aa, yκ = ab, zκ = ba and tκ = bb. Then

(x^{ω}y^{ω}z^{ω}x^{ω})κ = a^{ω}(ab)^{ω}(ba)^{ω}a^{ω}
= a^{ω}(ba)^{ω}bb(ab)^{ω}a^{ω}
= (x^{ω}z^{ω}ty^{ω}x^{ω})κ.

But x^{ω}y^{ω}z^{ω}x^{ω} ≠ x^{ω}z^{ω}ty^{ω}x^{ω} in F̂_{B}(A) (since they have distinct contents), so κ is not one-to-one, and hence {aa, ab, ba, bb} is not a pro-A code.

2.2 A coding for 2-variable pro-identities

In this section, we exhibit another, more specific, coding morphism. The reason for considering this particular coding will be made clear in Section 3.

Proposition 2.3 Let V be a monoidal pseudovariety such that V = V ◯^{u} A. The continuous morphism κ: F̂_{{a,b}}(V) → F̂_{{x,y}}(V) defined by aκ = x^{ω}y^{ω} and bκ = x^{ω}(yx)^{ω}y^{ω}, is a pro-V coding morphism.

Proof. The proof relies on the same idea as the proof of Proposition 2.1, and makes use of an unambiguous automaton recognizing the subsemigroup generated by a certain infinite (word) code.

Let us consider the 2-letter alphabet {x, y} and let C = x^{+}yy^{+} ∪ x^{+}(yx)^{+}yy^{+}. Then C is a code and the following automaton, A, recognizes C^{∗} (with initial and terminal state 1).

Let ρ: {x, y}^{∗} → R be the transition morphism of A, and let Q be its set of states, Q = {1, …, 7}. Since C is a code, (Q, R) is a monoid of unambiguous relations. Moreover, one can verify that R is aperiodic, and hence R ∈ V. Therefore we may consider the continuous extension ρ: F̂_{{x,y}}(V) → R of the transition morphism of A. Let {a, b} be another 2-letter alphabet, and let u, v be distinct elements of F̂_{{a,b}}(V): there exists a semigroup S in V and a continuous morphism σ: F̂_{{a,b}}(V) → S such that uσ ≠ vσ. By hypothesis, the semigroup T = S^{1} ◯^{u} (Q, R) lies in V. Let τ be the continuous morphism from F̂_{{x,y}}(V) into T defined by letting xτ and yτ be the Q × Q matrices obtained from xρ and yρ respectively in the following fashion:

• for xτ, replace all non-zero entries of xρ by 1 ∈ S^{1};

• for yτ, replace the (3, 1) entry of yρ by aσ, the (7, 1) entry of yρ by bσ and all other non-zero entries by 1.

Then, for each n, the (1, 1) entry of (x^{n}y^{n})τ is aσ, the (1, 1) entry of (x^{n}(yx)^{n}y^{n})τ is bσ, and hence, by continuity, the (1, 1) entry of (x^{ω}y^{ω})τ is aσ and the (1, 1) entry of (x^{ω}(yx)^{ω}y^{ω})τ is bσ. More generally, if κ is the continuous morphism from F̂_{A}(V) into F̂_{B}(V) defined by aκ = x^{ω}y^{ω} and bκ = x^{ω}(yx)^{ω}y^{ω}, then for each word w ∈ A^{+}, the (1, 1) entry of wκτ is wσ. By continuity again, the (1, 1) entry of wκτ is wσ for each w ∈ F̂_{A}(V). Therefore, the (1, 1) entries of uκτ and vκτ are distinct, so uκ ≠ vκ. Thus κ is one-to-one, that is, κ is a pro-V coding morphism. ⊓ ⊔

Note. In the above proof, one could only require that V = V ◯^{u} W, where W is the pseudovariety generated by R. But R contains the 3-element monoid U_{2} = {1, g, d} given by g^{2} = dg = g and d^{2} = gd = d. (Say {y^{2}ρ, (y^{2}xy^{2})ρ, (y^{2}xyxy^{2})ρ} is isomorphic to U_{2}.) Therefore V = V ◯^{m} W implies V = V ◯^{u} (U_{2}) = V ∗ (U_{2}). But the semidirect closure of (U_{2}) is A (see [5]), so V ◯^{u} W = V is equivalent to V ◯^{u} A = V.

2.3 A last coding result

Our last coding result shows how one can use the two members of a non trivial pro-\overline{H}- identity to construct a 2-element pro-\overline{H}-code, when H is a pseudovariety of groups closed under semidirect product.

Proposition 2.4 Let H be a pseudovariety of groups closed under semidirect product. Let u′ = v′ be a non trivial pro-\overline{H}-identity on some alphabet B, and let z be a new symbol, not in B. Then the continuous morphism κ: F̂_{\{a,b\}}(\overline{H}) → F̂_{B∪\{z\}}(\overline{H}) given by aκ = u′z and bκ = v′z, is a pro-\overline{H} coding morphism.

Proof. Let u, v be distinct elements of F̂_{\{a,b\}}(\overline{H}). There exists a semigroup S_{1} (resp. S_{2}) in \overline{H} in which the pro-V-identity u = v (resp. u′ = v′) does not hold. Then S = S_{1} × S_{2} ∈ \overline{H}, and S satisfies neither u = v nor u′ = v′. Since \overline{H} is monoidal, we may assume that S is a monoid. Let μ: F̂_{\{a,b\}}(\overline{H}) → S and ν: F̂_{B}(\overline{H}) → S be continuous morphisms such that uμ ≠ vμ and u′ν ≠ v′ν. Let B′ = B ∪ {z}.

Let S̃ be the semigroup S̃ = S ∪ {s̃ | s ∈ S} ∪ {z̃} (where z is a new symbol) endowed with the following product:

\begin{aligned}s · t & = & st \\ x · t̃ & = & t̃ \\ x · z̃ & = & z̃ \\ s̃ · t & = & s̃t \\ z̃ · t & = & t̃ \end{aligned}

for all s, t ∈ S and x ∈ S̃. The elements s̃ (s ∈ S) and z̃ form an aperiodic ideal of S̃, so S̃ ∈ \overline{H}, and it follows that the wreath product S ∘ S̃ lies in \overline{H} as well.

We now define a continuous morphism τ: F̂_{B′}(\overline{H}) → S ∘ S̃ by letting:

• for each letter b ∈ B, bτ = (f_{1}, bν), where f_{1}: S̃ → S is the constant function with value 1;

• zτ = (f_{z}, ˜1), where f_{z}: S̃ → S is given, for each s ∈ S̃, by

f_{z}(s) = \{ \begin{matrix}aμ & if s = u′ν or s = ũ′ν; \\ bμ & if s = v′ν or s = ṽ′ν; \\ 1 & otherwise. \end{matrix}

Then, for each word w ∈ B^{+}, wτ = (f_{1}, wν). By continuity, the same equality holds for all w ∈ F̂_{B}(V). Moreover, (wz)τ = (f_{1}, wν)(f_{z}, ˜1) = (g, ˜1), with g(s) = f_{1}(s)f_{z}(s wν) = f_{z}(s wν) for each s ∈ S̃. In particular, g(1) = f_{z}(wν) and g(˜1) = f_{z}(w̃ν) = f_{z}(wν) = g(1).

Let w′ ∈ F̂_{B}(V) and let w′τ = (g′, ˜1). Then

(wzw′z)τ = (g, ˜1)(g′, ˜1) = (h, ˜1) with h(s) = g(s)g′(s˜1) = g(s)g′(˜1).

So h(1) = g(1)g′(1) = f_{z}(wν)f_{z}(w′ν). More generally, if w ∈ {a, b}^{+}, then wκτ = (h, ˜1) with h(1) = wμ. By continuity, it follows that uκτ = (g, ˜1) and vκτ = (h, ˜1) satisfy

g(1) = uμ and h(1) = vμ.

So uκτ ≠ vκτ, and hence uκ ≠ vκ. Thus κ is one-to-one, and hence it is a pro-\overline{H} coding morphism. ⊓ ⊔

3 Irreducibility of certain pseudovarieties

In the rest of this article, H will be a pseudovariety of groups closed under semidirect product. We will prove that \overline{H} is Mal’cev irreducible. We first prove a weaker result.

Proposition 3.1 Let V be a monoidal pseudovariety closed under unambiguous product with A and let W be a proper subpseudovariety of V. Then (W ◯^{m} Com) ∩ V is proper.

Proof. Let u = v be a non trivial pro-V-identity satisfied by W. Let X be the alphabet of variables of u = v, say, X = {x_{1}, …, x_{n}}. Let A = {a, b} and let κ: X^{+} → A^{+} be defined by x_{i}κ = a^{i}b for each 1 ≤ i ≤ n. Then Xκ is a prefix code, and it is easily verified that Sag(Xκ) is aperiodic. By Proposition 2.1, it follows that uκ = vκ is a non trivial pro-V-identity. In addition, this pro-identity is clearly satisfied by W. So we may assume that u = v was chosen to be a 2-variable pro-V-identity, on the alphabet A.

Let S be the pseudovariety of all semigroups and let π: F̂_{A}(S) → F̂_{A}(V) be the natural projection. Since π is onto, we may consider elements u′ and v′ of F̂_{A}(S) such that u′π = u and v′π = v. In particular, W satisfies the non trivial pro-identity u′ = v′.

We now consider the pro-S-identity

u′(x^{ω}y^{ω}, x^{ω}(yx)^{ω}y^{ω}) = v′(x^{ω}y^{ω}, x^{ω}(yx)^{ω}y^{ω}).  (1)

Observe that Com satisfies (xy)^{ω} = x^{ω}y^{ω} = x^{ω}(yx)^{ω}y^{ω}. Now [17, Lemma 4.2] states that W ◯^{m} Com is defined by the pro-S-identities of the form ℓ(z_{1}, …, z_{n}) = r(z_{1}, …, z_{n}) where ℓ = r is an n-variable pro-S-identity satisfied by W and where Com satisfies z_{1} = ⋯ = z_{n} = z_{1}^{2}. Thus W ◯^{m} Com satisfies the pro-identity (1), and hence so does (W ◯^{m} Com) ∩ V. Since the latter pseudovariety is contained in V, it also satisfies the pro-V-identity obtained by taking the image under π of the pro-identity (1), namely

u(x^{ω}y^{ω}, x^{ω}(yx)^{ω}y^{ω}) = v(x^{ω}y^{ω}, x^{ω}(yx)^{ω}y^{ω}).  (2)

There remains to verify that the pro-V-identity (2) is non trivial, which follows immediately from Proposition 2.3, thus concluding the proof. ⊓ ⊔

Theorem 3.2 Let H be a pseudovariety of groups closed under semidirect product. Then \overline{H} is Mal’cev irreducible.

Proof. Let us first consider a proper subpseudovariety V_{1} of \overline{H}. By Proposition 3.1, (V_{1} ◯^{m} Com) ∩ \overline{H} is proper as well. As above, we may consider a 2-variable non trivial pro-\overline{H}-identity u = v satisfied by (V_{1} ◯^{m} Com) ∩ \overline{H}.

Let us now assume that \overline{H} = V_{1}◯^{m} V_{2} with V_{2} a proper subpseudovariety of \overline{H} as well, and let u′ = v′ be a non trivial pro-\overline{H}-identity satisfied by V_{2}. Let z be a new variable, not in the alphabet of variables of u′ = v′. Then by Proposition 2.4, the pro-\overline{H}-identity u(u′z, v′z) = v(u′z, v′z) is non trivial. To get a contradiction, it suffices to verify that it is satisfied by a set of generators of V_{1} ◯^{m} V_{2}, and hence by the pseudovariety V_{1} ◯^{m} V_{2} itself.

Let C be the alphabet of variables of this pro-identity and let A = {a, b} be the alphabet of variables of u = v. Let S be a semigroup in \overline{H} admitting an onto morphism π: S → T such that T ∈ V_{2} and eπ^{−1} ∈ V_{1} for each idempotent e of T, and let φ: F̂_{C}(\overline{H}) → S be a continuous morphism. Let also κ: F̂_{A}(\overline{H}) → F̂_{C}(\overline{H}) be the continuous morphism determined by aκ = u′z and bκ = v′z. Since T ∈ V_{2}, T satisfies u′z = v′z, that is, aκφπ = bκφπ = t_{0} for some t_{0} ∈ T. Let T_{0} be the subsemigroup of T generated by t_{0}. Then T_{0} ∈ Com. Moreover, if S_{0} = T_{0}π^{−1}, then S_{0} ∈ V_{1} ◯^{m} Com and the range of κφ is in S_{0}. But S_{0} lies also in \overline{H}, so S_{0} satisfies u = v, and hence uκφ = vκφ. Therefore, u(u′z, v′z)φ = v(u′z, v′z)φ. This concludes the proof. ⊓ ⊔

If V is a pseudovariety, we let LV be the pseudovariety of semigroups S such that eSe ∈ V for each idempotent e of S. It is clear that the only pseudovariety V such that \overline{H} = LV is V = \overline{H} itself.

Corollary 3.3 Let H be a pseudovariety of groups closed under semidirect product. Then \overline{H} is semidirectly irreducible.

Proof. Let us assume that \overline{H} = V_{1} ∗ V_{2} where V_{1} and V_{2} are proper subpseudovarieties of \overline{H}. Since \overline{H} ◯^{m} \overline{H} = \overline{H} and V_{1} ∗ V_{2} ⊆ LV_{1} ◯^{m} V_{2} (see for instance [23, Lemma 2.2]), it follows that \overline{H} = LV_{1} ◯^{m} V_{2}, and by Theorem 3.2, \overline{H} = LV_{1}. Therefore \overline{H} = V_{1}, a contradiction. ⊓ ⊔

Corollary 3.4 Let H be a pseudovariety of groups closed under semidirect product. Then \overline{H} is join irreducible.

Proof. Let us assume that \overline{H} = V_{1} ∨ V_{2} where V_{1} and V_{2} are proper subpseudovarieties of \overline{H}. Since \overline{H} ◯^{m} \overline{H} = \overline{H}, we have \overline{H} = V_{1} ◯^{m} V_{2}, in contradiction with Theorem 3.2. So \overline{H} is ∨-irreducible. ⊓ ⊔

4 Applications

The above results have noteworthy consequences. For instance, we get immediate proofs of the infinity of several well-known hierarchies of pseudovarieties.

First let us observe that, if we consider pseudovarieties of monoids, we can prove in the same fashion that, for each pseudovariety of groups H closed under semidirect product, the pseudovariety of all monoids in which the subgroups are in H, is Mal’cev irreducible, semidirectly irreducible and join irreducible. For convenience, this pseudovariety is also denoted by \overline{H}, and in the case of the trivial pseudovariety of groups, we also denote by A the pseudovariety of aperiodic monoids.

The Straubing dot-depth hierarchy is a hierarchy of pseudovarieties of monoids within A, with connections with language theory and the theory of complexity for boolean circuits. It is defined by letting V_{0} = I, the trivial pseudovariety, and V_{n+1} = ♢V_{n} for all n ≥ 0. Here ♢ denotes the Schützenberger operator. For complete definitions and references, see [21, 18]. It is well-known that A is the union of the increasing sequence of the V_{n}. In [14], it is proved that for any pseudovariety V, ♢V ⊆ B_{1} ◯^{m} V, where B_{1} is the pseudovariety of aperiodic semigroups

B_{1} = [[(x^{ω}sy^{ω}tx^{ω})^{ω}sy^{ω}v(x^{ω}uy^{ω}vx^{ω})^{ω} = (x^{ω}sy^{ω}tx^{ω})^{ω}(x^{ω}uy^{ω}vx^{ω})^{ω}]].

Proposition 4.1 The Straubing dot-depth hierarchy is infinite.

Proof. Let us assume that A = V_{n+1}, with n minimal. Then A = ♢V_{n}, and hence A = B_{1} ◯^{m} V_{n}. But A is Mal’cev irreducible and B_{1} is proper, and so is V_{n} by definition of n, so we get a contradiction. ⊓ ⊔

The Krohn-Rhodes theorem [5] states that each finite monoid M divides a wreath product of the form

M < M_{k} ∘ M_{k−1} ∘ ⋯ ∘ M_{1}

where the M_{i} are either groups dividing M or copies of the three element monoid U_{2} (see Section 2.2). It follows that each finite monoid M divides a wreath product of the form

M < A_{n} ∘ G_{n} ∘ A_{n−1} ∘ ⋯ ∘ G_{1} ∘ A_{0}

where the A_{i} are aperiodic and the G_{i} are groups (more precisely, the G_{i} are wreath products of copies of groups dividing M). Let us consider the following sequence of pseudovarieties of monoids: C_{0} = A and C_{n+1} = A ∗ G ∗ C_{n} for each n ≥ 0. By the Krohn-Rhodes theorem, the pseudovariety M of all finite monoids is the union of the increasing sequence (C_{n})_{n}. The least integer n such that a given finite monoid M lies in C_{n} is called the group complexity of M. It is an old-standing conjecture whether the group complexity of a finite monoid M is effectively computable [5, 7]. Our results give an immediate proof that the hierarchy given by the C_{n} is infinite.

Proposition 4.2 The group complexity hierarchy is infinite.

Proof. If M = C_{n+1} with n minimal, then M = A ∗ G ∗ C_{n}. Since M is semidirectly irreducible and M ≠ C_{n} by definition of n, it follows that M = A ∗ G, and hence M = A or M = G, a contradiction. ⊓ ⊔

The Krohn-Rhodes theorem also implies that, if H is a pseudovariety of groups such that H = H ∗ H, then the pseudovariety of monoids \overline{H} is the union of the increasing sequence of pseudovarieties given by C_{0}(H) = A and C_{n+1}(H) = A ∗ G ∗ C_{n}(H) for each n ≥ 0. With the same proof, it can be shown that the resulting hierarchy in \overline{H} is infinite.

An other consequence of the Krohn-Rhodes theorem is that each aperiodic monoid divides a wreath product of copies of U_{2}. Let now V be a subpseudovariety of A containing U_{2} and let V^{(1)} = V and V^{(n+1)} = V ∗ V^{(n)}. This is an increasing sequence of pseudovarieties of monoids within A, and A = ⋃_{n} V^{(n)}. Then we have the following infinity result^{2}.

Proposition 4.3 Let V be a subpseudovariety of A containing U_{2} and let (V^{(n)})_{n} be the associated increasing sequence of subpseudovarieties of A. If V ≠ A, then V^{(n)} is strictly contained in V^{(n+1)} for each n ≥ 1. That is, the resulting hierarchy within A is infinite.

Proof. If V^{(n)} = V^{(n+1)} with n minimal, then A = V ∗ V^{(n)}. Since A is semidirectly irreducible, it follows that A = V by definition of n, a contradiction. ⊓ ⊔

We can also extend a result of Margolis on maximal subpseudovarieties [11] (for pseudovarieties of semigroups or of monoids).

2The authors thank P. Higgins for bringing this corollary to their attention.

Corollary 4.4 Let H be a pseudovariety of groups closed under semidirect product. Then \overline{H} admits no maximal proper subpseudovariety.

Proof. Let W be a maximal proper subpseudovariety of \overline{H}, and let S ∈ \overline{H} \ W. Let W′ be the pseudovariety generated by S. Then W ⊆ W ∨ W′ ⊆ \overline{H} and W ≠ W ∨ W′, so \overline{H} = W∨W′. Since \overline{H} is ∨-irreducible, it follows that \overline{H} = W′. In particular, \overline{H} admits a finite free object over each finite alphabet. This yields immediately a contradiction, since \overline{H} admits infinitely many 1-generated elements. ⊓ ⊔

Finally, let us recall that Eilenberg’s theorem [5] shows that varieties of rational languages are in bijective correspondence with pseudovarieties of semigroups. In particular, the varieties of languages associated with S and A in this correspondance are respectively the variety of all rational languages and the variety of all star-free languages [13]. The irreducibility results obtained in this paper can be readily translated into analogous results for varieties of rational languages.

5 Conclusion

We have proved that, whenever H is a pseudovariety of groups closed under extension, then the pseudovariety \overline{H} of all finite semigroups in which all the subgroups are in H, is irreducible for the three main binary operations on pseudovarieties, the join, the semidirect product and the Mal’cev product.

Our proof relies heavily on coding techniques for identities in relatively free profinite structures (pro-identities). We gave sufficient conditions under which an injective, or coding, morphism between free semigroups extends to an injective continuous morphism between free pro-V semigroups. We also proved the injectivity of other continuous morphisms between free pro-V semigroups. This opens up the question of describing as accurately as possible all finite pro-V codes, that is, all continuous embeddings of a free pro-V semigroup into another one.

Observe that our method does not apply to other pseudovarieties than those of the form \overline{H}, where H is a pseudovariety of groups closed under semidirect product. It would be interesting to develop general techniques to prove just, say, the join irreducibility, or the semidirect irreducibility of a pseudovariety.

We can also ask, more specifically, whether all pseudovarieties of the form \overline{H} (with H a pseudovariety of groups) are irreducible for join, semidirect product or Mal’cev product. For instance, Margolis [11] shows that \overline{H} has no maximal proper subpseudovarieties for any H containing the pseudovariety Ab of all commutative groups.

Another interesting question is that of the join irreducibility of the complexity classes C_{n} introduced in the previous section. We now know that C_{0} is join and semidirectly irreducible. The other classes are trivially semidirectly reducible.

References

[1] J. Almeida. Finite Semigroups and Universal Algebra, World Scientific, Singapore, 1994.

[2] J. Almeida. On direct product decompositions of J -trivial semigroups, Intern. J. Algebra and Comput. 1 (1991) 329–337.

[3] J. Almeida and P. Weil. Relatively free profinite monoids: an introduction and examples, in J. Fountain ed. Semigroups, Formal Languages and Groups, NATO ASI Series C-466, Kluwer Academic, 1995, 73–117.

[4] J. Berstel and D. Perrin. Theory of Codes, Academic Press, New York, 1985.

[5] S. Eilenberg. Automata, Languages and Machines, vol. B, Academic Press, New York, 1976.

[6] T. Evans. The lattice of semigroup varieties, Semigroup Forum 2 (1971) 1–43.

[7] K. Henckell, S. W. Margolis, J.-E. Pin and J. Rhodes. Ash’s type II theorem, profinite topology and Malcev products, International Journal of Algebra and Computation 1 (1991) 411–436.

[8] I. Koryakov. Embedding of pseudofree semigroups, Izvestiya VUZ Matem. 39 (1995), 58–64. English translation: Russian Mathem. (Iz. VUZ) 39 (1995) 53–69.

[9] E. Le Rest and M. Le Rest. Sur le calcul du monoïde syntaxique d’un sous-monoïde finiment engendré, Semigroup Forum 21 (1980) 173–185.

[10] A. Malcev. Nilpotent Semigroups, Uch. Zap. Ivanovsk. Ped. In-ta 4 (1953) 107–111.

[11] S. Margolis. On maximal varieties of finite monoids and semigroups, Izvestiya VUZ Matem. 39 (1995), 65–70. English translation: Russian Mathem. (Iz. VUZ) 39 (1995) 60–64.

[12] H. Neumann. Varieties of groups, Springer (1967).

[13] J.-E. Pin. Variétés de langages formels, Masson, Paris, 1984. English translation: Varieties of formal languages, North Oxford, London and Plenum, New York, 1986.

[14] J.-E. Pin. A property of the Schützenberger product, Semigroup Forum 35 (1987) 53–62.

[15] J.-E. Pin and J. Sakarovitch. Une application de la représentation matricielle des transductions, Theoret. Comp. Science 35 (1985) 271–293.

[16] J.-E. Pin and P. Weil. A Reiterman theorem for pseudovarieties of finite first-order structures, Algebra Universalis, to appear.

[17] J.-E. Pin and P. Weil. Profinite semigroups, Mal’cev products and identities, J. Algebra, to appear.

[18] J.-E. Pin and P. Weil. Polynomial closure and unambiguous product, to appear.

[19] J. Reiterman. The Birkhoff theorem for finite algebras, Algebra Universalis 14 (1982) 1–10.

[20] J. Sakarovitch. Sur la définition du produit en couronne, in G. Pirillo ed. Colloque Codages et Transductions, Florence, 1981, 285–300.

[21] H. Straubing. A generalization of the Schützenberger product of finite monoids, Theoret. Comp. Science 13 (1981) 137–150.

[22] P. Weil. Groups in the syntactic monoid of a composed code, J. Pure Applied Algebra 42 (1986) 297–319.

[23] P. Weil. Closure of varieties of languages under products with counter, Journ. Comp. System and Science 45 (1992) 316–339.