SUBGROUPS OF THE FREE SEMIGROUP ON A BIORDERED SET

IN WHICH PRINCIPAL IDEALS ARE SINGLETONS

Brett McElwee^{1}

School of Mathematics and Statistics, University of Sydney,

NSW 2006, Australia

2GMO Woolley Ltd, One Angel Court, Throgmorton Street, London EC2R 7HJ, United Kingdom

Abstract

Easdown has conjectured that the subgroups of the free semigroup on an arbitrary biordered set are free. In this note a weaker conjecture is verified. It is shown that the subgroups of the free semigroup on a biordered set in which principal ideals are singletons are free. In addition, an expression is given for the ranks of the maximal subgroups. This generalizes a result due to Pastijn which involves the free semigroup on a rectangular biset.

1 INTRODUCTION

The biordered set (we use ‘biset’ for brevity) of an arbitrary semigroup S is the set of idempotents of S equipped with a certain partial product. This partial product is the restriction of the product of S to those pairs (e, f) of idempotents such that ef = e, ef = f, fe = f or fe = e. It is readily verified that the resultant structure is indeed a partial algebra.

1email: brett mcelwee@gmow.co.uk 2current postal address, November 2001

Nambooripad introduced the notion of biset in [4], where he characterized the bisets of regular semigroups. Easdown subsequently characterized the bisets of arbitrary semigroups in [2]. Specifically, he demonstrated that if E is a partial algebra satisfying certain second order axioms, which had been identified by Nambooripad [4], then the semigroup which is generated by the elements of E, subject to the defining relations given by the product of E, will have E as its biset. Consequently, this is termed the free semigroup on E, and the characterizing partial algebras are what we term the abstract bisets, or simply bisets.

Now Easdown has conjectured that the subgroups of the free semigroup on a biset are free. Pastijn [5] has confirmed this in the special case that the biset is rectangular, and in addition he has obtained, in that case, the ranks of the maximal subgroups. In this note we generalize Pastijn’s observations by showing that the subgroups of the free semigroup on a locally trivial biset are free, and by giving an expression for the ranks of those subgroups which are maximal.

2 PRELIMINARIES

Note that when we consider an arbitrary abstract biset there is no loss of generality, due to Easdown’s characterization, if the reader considers this to be the biset of an arbitrary semigroup. Thus we can avoid giving the defining axioms of an abstract biset.

Now let us have a precise definition of the free semigroup on a given biset. Let E be an arbitrary biset. Denote by E^{+} the free semigroup on E regarded as an alphabet, so that E^{+} comprises nonempty words over E under the binary operation of concatenation. Let R be the set of relations of the form ef = g, where e, f, g ∈ E and the biset product ef exists and equals g in E. The free semigroup on the biset E, denoted by F_{E}, is the quotient E^{+}/γ where γ is the congruence on E^{+} generated by R. We denote by \overline{w} the γ-equivalence class of w ∈ E^{+}.

The free semigroups of concern here are those defined on locally trivial bisets. To say that a biset E is locally trivial is simply to say that its principal ideals are singletons, and the reader who is acquainted with bisets can readily verify that E is locally trivial if and only if ef = e lies in R precisely when fe = f does, and fe = e lies in R precisely when ef = f does. Moreover, one can easily verify that any set E equipped with a partial multiplication with domain D_{E} and equivalence relations R and L such that D_{E} = R ∪ L, R ∩ L = id_{E}, and

(e, f) ∈ R [L] implies ef = f [e] and fe = e [f] ,

satisfies the biset axioms and is locally trivial. It follows that the free semigroup on a locally trivial biset E is simply the semigroup generated by the elements of E subject to, firstly, the idempotent relations ee = e, and secondly, any collection of relations satisfying the aforementioned conditions.

Now we can obviously exploit Green’s L and R-class notation when dealing with E by taking L and R to be Green’s relations restricted to idempotents. We can also exploit his D-class notation by taking D to be the equivalence on E generated by L ∪ R.

Let E be a locally trivial biset for the duration. We want to demonstrate the uniqueness of the reduced representatives of the γ-classes of E^{+}, whereby we say a word over E is reduced precisely when it contains no consecutive L or R-related letters.

Our demonstration is an adaptation of an existing proof, due to Artin [1] and van der Waerden [6], of the uniqueness of reduced representative words of free group elements. Firstly, we define a function [·] which operates on the tails of words according to the relations of F_{E}. Let w be a word, possibly empty, over E. Let e be empty or an element of E, though in the former case only if w is also empty, and let f and g be elements of E. Put

[wefg] = \begin{cases}wefg & if f \ L g and f \ R g; \\ wef & if f L g and f \ R g; \\ weg & if f R g and e \ L g; \\ we & if f R g and e L g, \end{cases}

where e \ L g is taken to be true if e is the empty word. Now define a function Υ by

\begin{aligned}Υ(ϵ) & = & ϵ \\ Υ(e) & = & e \\ Υ(we) & = & [Υ(w)e], \end{aligned}

for all e in E, for all nonempty words w over E, and for ϵ the empty word. By a simple induction, for any nonempty word w, Υ(w) is a reduced word the final letter of which is L-related to the final letter of w.

Lemma 2.1 Let w be a word, possibly empty, over E. Let e be either the empty word or an element of E, though in the former case only if w is also empty, and let f and g be elements of E such that ef is reduced and f L g. We have [wefg] = wef.

Proof. If f R g, then

[wefg] = weg [e L g ⇒ e L f, a contradiction]
= wef.  [f L g R f so that f = g]

If f \ R g, then [wefg] = wef and we are done. □

Lemma 2.2 Let w be a word, possibly empty, over E. Let e be either the empty word or an element of E, though in the former case only if w is also empty, and let f, g and h be elements of E such that ef is reduced and g R h. We have [[wefg]h] = [wefh].

Proof. If f L g, then the result follows by 2.1. So suppose that f \ R g. Consider the case that f \ R g and f L h. In that case, [[wefg]h] = [wefgh] = wef, and wef = [wefh], as if f R h were to hold, then f R g would hold, yielding a contradiction. Thus that case holds, and the remaining cases can be similarly verified. □

Lemma 2.3 There exists a unique reduced word in each equivalence class of F_{E}.

Proof. Let u and v be words over E, and let f and g be elements of E such that either f L g or f R g. Suppose that f R g. As Υ(u) is reduced, by 2.2 we have

Υ(ufg) = [[Υ(u)f]g] = [Υ(u)g] = Υ(ug).

If v is empty then immediately Υ(ufgv) = Υ(ufv). If v = v′x for some word v′ and letter x then, by an inductive hypothesis,

Υ(ufgv) = [Υ(ufgv′)x] = [Υ(ugv′)x] = Υ(ugv).

On the other hand, suppose that f L g. By 2.1 we have [[Υ(u)f]g] = [Υ(u)f], as Υ(u) is reduced and its last letter h satisfies h L f L g. Thus Υ(ufgv) = Υ(ufv). It follows that the restriction of Υ to any γ-class is a constant map. As Υ fixes reduced words, the result follows. □

3 THE SUBGROUPS

Let H be an H-class of F_{E} which contains an idempotent. Denote by l_{H} the number of L_{F_{E}}-classes in the D_{F_{E}}-class in which H resides, and denote by r_{H} the number of R_{F_{E}}-classes in the D_{F_{E}}-class. Pastijn demonstrates in [5] that if E comprises a single solid D-class, that is, if it is a rectangular biset, then the subgroups of F_{E} are free, and if E is, in addition, finite, then the maximal subgroup H has rank (l_{H} − 1)(r_{H} − 1). Pastijn demonstrates this by employing Rees-matrix semigroups. We demonstrate our result by showing that our subgroups are fundamental groups of graphs.

For a graph Γ and one of its vertices v, denote by π(Γ, v) the fundamental group based at v. We denote by \overline{(v, v_{1}, … v_{n}, v)} the equivalence class of a loop (v, v_{1}, … v_{n}, v). The following fact is well known.^{1}

Theorem 3.1 For a finite connected graph Γ, each fundamental group π(Γ, v) is free and of rank |E(Γ)| − |V(Γ)| + 1. □

For H as above, denote by d_{H} the total number of idempotent-free Hclasses in the D_{F_{E}}-class in which H resides. This number is easily determined because the only idempotents of F_{E} are the images \overline{e} of elements e of E. The following is our generalization of Pastijn’s result.

1See [3], for example.

Theorem 3.2 All subgroups of F_{E} are free, and in the case that E is finite, each maximal subgroup H has rank (l_{H} − 1)(r_{H} − 1) − d_{H}.

Proof. Since all subgroups of a free group are free, it remains to show that all the H_{F_{E}}-classes which contain idempotents are free and that the expression for the rank holds in the case that E is finite. Let H be the H_{F_{E}}-class of an idempotent. Let e be the preimage of the idempotent and let D the D_{E}-class of e. Let the set of R-classes of D be well-ordered by an order ≤_{R}. Observe that this induces a well ordering on each L-class L by taking

f ≤_{L}g precisely when R_{f} ≤_{R}R_{g}.

Now do the same with L and R interchanged. For an L-class L of D and R-class R of D, denote by m_{L} and m_{R} the least elements of L and R respectively.

Form a graph Γ with vertices the elements of D, and

E(Γ) = {{x, m_{L_{x}}}| x ≠ m_{L_{x}}} ⋃ {{x, m_{R_{x}}}| x ≠ m_{R_{x}}}.

We show that π(Γ, e) is isomorphic to H. Define the map ζ: π(Γ, e) → H by putting

ζ (\overline{(e, x_{1}, …, x_{n}, e)}) = \overline{ex_{1} ⋯ x_{n}e},

for all \overline{(e, x_{1}, …, x_{n}, e)} in π(Γ, e), with the understanding that (e, e) denotes the empty path based at e. The map is evidently well-defined. That it maps into H follows by Green’s Lemma and a simple induction. That it is a homomorphism is obvious. So in showing that ζ is an isomorphism, it remains to show that it is injective and surjective.

Consider any p ≠ 1 in π(Γ, e). There exists a reduced representative of p, and it can be written π_{1}π_{2} ⋯ π_{2n}, where n ≥ 1, π_{i} is nonempty, for i = 1, …, 2n − 1, and one of the following holds.

(i) For all odd i, π_{i} is contained wholly within an L-class, and for all even j, π_{j} is contained wholly within an R-class.

(ii) For all even i, π_{i} is contained wholly within an L-class, and for all odd j, π_{j} is contained wholly within an R-class.

Evidently none of the subgraphs corresponding to L-classes or R-classes can contain a reduced loop, whence each π_{i} must not be a loop. It follows that n ≥ 2. It also follows that if (i) holds, then the length of the reduced word in the γ-class ζ(p), as given by 2.3, is either n or n + 1, depending on whether π_{2n} is empty or not. Finally, it follows that if (ii) holds, then the length of the reduced word is n. It follows that ζ(p) ≠ \overline{e}, whence ζ is injective.

We show surjectivity. Let e_{1}, …, e_{n} be elements of E such that e_{1} ⋯ e_{n} is reduced and \overline{e_{1} ⋯ e_{n}} H \overline{e}. If n = 1, then e_{1} = e, as E ≅ E(F_{E}), whence \overline{e_{1} ⋯ e_{n}} is the image of \overline{(e, e)}. So suppose not. We have a nonempty reduced word w over E such that we_{1} ⋯ e_{n}γe. Write w = f_{1} ⋯ f_{t}, for some f_{i} in E. By the proof of 2.3, we can transform f_{1} ⋯ f_{t}e_{1} ⋯ e_{n} into e simply by deleting letters. We want to show that for i = 1, …, n − 1, there exists f_{j} such that e_{i} L f_{j} R e_{i+1}. Suppose that f_{t} R e_{1}. It cannot be that f_{t−1} R e_{1}, for that would contradict the fact that f_{1} ⋯ f_{t} is reduced. As f_{1} ⋯ f_{t−1}e_{1} ⋯ e_{n} γ e and n > 1, we conclude that t > 1 and f_{t−1} L e_{1}. So we see that without loss of generality we can suppose that f_{t} L e_{1}. So we have f_{1} … f_{t}e_{2} ⋯ e_{n} γ e. Now if f_{t} L e_{2}, then e_{2} L e_{1}, contradicting the fact that e_{1} ⋯ e_{n} is reduced. So f_{t} R e_{2}. As f_{1} ⋯ f_{t−1}e_{2} ⋯ e_{n} γ e, an inductive hypothesis applies and we are done. Now for i = 1, …, n−1, we denote by x_{i} the letter of f_{1} ⋯ f_{t} which is L-related to e_{i} and R-related to e_{i+1}. Obviously e_{1}x_{1} ⋯ e_{n−1}x_{n−1}e_{n} γ e_{1} ⋯ e_{n}, and by Green’s Lemma and a simple induction, e_{1} R e L e_{n}. Thus

ee_{1}x_{1} ⋯ e_{n−1}x_{n−1}e_{n}e γ e_{1} ⋯ e_{n},

and consecutive letters in the former word are either L or R-related. So after possibly inserting some letters into that word, we have a word ey_{1} ⋯ y_{k}e such that (e, y_{1}, …, y_{k}, e) is a loop based at e and

ey_{1} ⋯ y_{k}e γ e_{1} ⋯ e_{n}.

Thus ζ is surjective.

Now by 3.1, it remains only to show that the expression holds in the finite case. Let E be finite. We have

(l_{H} − 1)(r_{H} − 1) − d_{H} = (l_{H}r_{H} − d_{H}) − l_{H} − r_{H} + 1
= |V(Γ)| − l_{H} − r_{H} + 1
= (|V(Γ)| − l_{H} + |V(Γ)| − r_{H}) − |V(Γ)| + 1
= |E(Γ)| − |V(Γ)| + 1,

and so we are done. □

REFERENCES

[1] Artin, E. The free product of groups. Amer. J. Math. 1947, 69, 1–4.

[2] Easdown, D. Biordered sets come from semigroups. J. Algebra 1985, 96, 581-591.

[3] Lyndon, R.C.; Schupp, P.E. Combinatorial Group Theory; Springer-Verlag, Berlin/Heidelberg/New York, 1977.

[4] Nambooripad, K.S.S. Structure of regular semigroups. I. Mem. Amer. Math. Soc. 1979, 224.

[5] Pastijn, F. The biorder on the partial groupoid of idempotents of a semigroup. J. Algebra 1980, 65, 147-187.

[6] Van der Waerden, B.L. Free products of groups. Amer. J. Math. 1948, 70, 527-528.