arXiv:1712.07426v1 [math.GR] 20 Dec 2017

Actions of E−dense semigroups and an application to
the discrete log problem
James Renshaw
Mathematical Sciences
University of Southampton
Southampton, SO17 1BJ
England
j.h.renshaw@maths.soton.ac.uk

June 2017
Abstract
We describe the structure of E−dense acts over E−dense semigroups in an analogous
way to that for inverse semigroup acts over inverse semigroups. This is based, to a large
extent, on the work of Schein on representations of inverse semigroups by partial oneto-one maps. We consider an application to the discrete log problem in cryptography
as well as an application to the same problem using completely regular semigroups.

Key Words Semigroup, monoid, E−dense, E−inversive, completely regular, semigroup
acts, E−dense acts, discrete logarithm, cryptography
2010 AMS Mathematics Subject Classification 20M30, 20M50, 20M99.

1

Introduction and Preliminaries

Let S be a semigroup. By a left S−act we mean a non-empty set X together with an action
S × X → X given by (s, x) 7→ sx such that for all x ∈ X, s, t ∈ S, (st)x = s(tx). If S is a
monoid with identity 1, then we normally require that 1x = x for all x ∈ X. A right S−act
is defined dually. If X is a left S−act then the semigroup morphism ρ : S → T (x) given
by ρ(s)(x) = sx is a representation of S. Here T (X) is the full transformation semigroup
on X consisting of all maps X → X. Conversely, any such representation gives rise to an
action of S on X. If X is both a left S−act and a right T −act for semigroups/monoids S
and T and if in addition (sx)t = s(xt) then X is said to be an (S, T )−biact. Throughout
this paper, unless otherwise stated, all acts will be left S−acts. We refer the reader to [7]
for basic results and terminology in semigroups and monoids and to [2] and [8] for those
concerning acts over monoids. If S is an inverse semigroup then we can replace T (X) by
I(X), the inverse semigroup of partial one-to-one maps. A comprehensive theory of these
types of representations was given by Boris Schein in the early 1960’s and an account of
that work can be found in [1] and [7]. Here we wish to emulate that approach for E−dense
semigroups and do so in section 2. In section 3, we apply some of these results to the discrete
log problem found in cryptography (see for example [9]).
Recall that an idempotent in a semigroup S is an element s ∈ S such that s2 = s. A band is
a semigroup consisting entirely of idempotents whilst a semilattice is a commutative band.
We shall denote the idempotents of a semigroup S as E(S) or more generally E. Let S
1

be a semigroup and let W (s) = {s′ ∈ S|s′ ss′ = s′ } be the set of weak inverses of s and
V (s) = {s′ ∈ S|s′ ∈ W (s), s ∈ W (s′ )} be the set of inverses of s. If S is a group then clearly
W (s) = V (s) = {s−1 } for all s ∈ S, whilst if S is a rectangular band, that is to say a band
in which xyx = x for all x, y ∈ S, then W (s) = V (s) = S for each s ∈ S. Notice that if
s′ ∈ W (s) then s′ s, ss′ ∈ E. Moreover, if e ∈ E then e ∈ W (e). It may of course be the case
that for a given element s ∈ S, W (s) = Ø. We do however have
Lemma 1.1 ([20, Corollary 3.3]) Let S be a semigroup in which E 6= Ø. Then E is a
band if and only if for all s, t ∈ S, W (st) = W (t)W (s).
From the proof of [5, Lemma 7.14] we can deduce
Lemma 1.2 Let S be a semigroup with band of idempotents E. Then for all s ∈ S, s′ ∈
W (s), e ∈ E it follows that ses′ , s′ es ∈ E.
If the conclusions of Lemma 1.2 hold, we say that S is weakly self conjugate. We shall make
frequent use of both the previous properties of semigroups in which E is a band without
further reference. Notice also that if s′ ∈ W (s) then ss′ s ∈ V (s′ ) ⊆ W (s′ ), a fact that we
shall also use frequently. In particular, s′ is a regular element of S.
It was shown by Mitsch [12] that the following is a natural partial order on any semigroup
S
a ≤M b if and only if there exists x, y ∈ S, a = xb = by, xa = ay = a.
Notice that if there exist idempotents e and f such that a = eb = bf then it follows that
a = ea = af and so a ≤M b. If a is a regular element of S then it is easy to check that
e = aa′ x ∈ E and f = ya′ a ∈ E for any a′ ∈ V (a), and that a = eb = bf . Hence if a is
regular then
a ≤M b if and only if there exists e, f ∈ E, a = eb = bf.
In particular, this is true if a ∈ E. It is also worth noting here that if E is a semilattice then
the restriction of ≤M to E is compatible with multiplication, a fact that we shall use later.
Let A be a subset of a semigroup S and define
AωM = {s ∈ S|a ≤M s for some a ∈ A}.
If A = {a} then we will write AωM as aωM . Notice that (AωM )ωM = AωM and that if
A ⊆ B then AωM ⊆ BωM . Also, if A ⊆ BωM then AωM ⊆ BωM . We call AωM the
(ωM −)closure of A and say that A is (ωM −)closed if A = AωM . Notice that if A ⊆ B with
B being (ωM −)closed, then AωM ⊆ B.
If T is a subset of a semigroup S then we say that T is left (resp. right) dense in S if for all
s ∈ S there exists s′ ∈ S such that s′ s ∈ T (resp. ss′ ∈ T ). We say that T is dense in S if
it is both left and right dense in S. We are particularly interested in the case where T = E
the set of idempotents of S and we shall refer to semigroups in which E is dense in S as
E−dense or E−inversive semigroups. This concept was originally studied by Thierrin [19]
and subsequently by a large number of authors (see Mitsch [15] for a useful survey article,
but note that the term E−dense has a slightly different meaning there). Included in this
class of semigroup are the classes of all regular semigroups, inverse semigroups, groups,
eventually regular semigroups (that is to say every element has a power that is regular),
periodic semigroups (every element is of finite order) and finite semigroups.
Let S be a semigroup, let L(s) = {s′ ∈ S|s′ s ∈ E}. Then it is well known that W (s) ⊆ L(s).
Moreover, for each s′ ∈ L(s), s′ ss′ ∈ W (s) and so W (s) 6= Ø if and only if L(s) 6= Ø. The
following is then immediate.
2

Lemma 1.3 Let S be an E−dense semigroup. Then for all s ∈ S there exists s′ ∈ S such
that s′ s, ss′ ∈ E.
Let S be an E−dense semigroup with a band of idempotents E and define a partial order
on S by
s ≤ t if and only if either s = t or there exists e, f ∈ E with s = te = f t
and note that ≤ ⊆ ≤M and that if E is a semilattice then ≤ is compatible with multiplication
by weak inverses. If s is regular (in particular idempotent) then s ≤ t if and only if s ≤M t.
If A is a subset of S then define
Aω = {s ∈ S|a ≤ s for some a ∈ A}
and notice that A ⊆ Aω ⊆ AωM . It is also clear that (Aω)ω = Aω. Note from above that
if A ⊆ E then AωM = Aω. We shall make use of ω in Section 2.
Weak inverses of elements will not in general be unique and in section 2 we will often need
to deal with more than one weak inverse of a given element. The following useful result is
easy to establish.
Lemma 1.4 Let S be an E−dense semigroup with a semilattice of idempotents E.
1. If s′ ∈ W (s) and e, f ∈ E then es′ f ∈ W (s).
2. If s′ , s∗ ∈ W (s) then s′ ss∗ ∈ W (s) and s′ ss∗ = s′ ∧ s∗ .
3. If s′ ∈ W (s) and s′∗ ∈ W (s′ ) then s′∗ = s′∗ s′ s = ss′ s′∗ and for all e ∈ E, es′∗ ≤ s. In
particular s′∗ ≤ s.
4. If s′ ∈ W (s) then W (s′ ) = sW (s)s and V (s′ ) = {ss′ s}. In particular if s∗ ∈ W (s)
then W (s′ ) = W (s∗ ) and ss′ ss∗ s ∈ W (s′ ).
5. Let W = {s′ ∈ W (s)|s ∈ S}. Then W is an inverse subsemigroup of S.
6. For all s ∈ S, W (W (W (s))) = W (s).
Proof.

Let E and S be as stated.

1. Suppose that e, f ∈ E and s′ ∈ W (s). Then (es′ f )s(es′ f ) = es′ f ss′ f = es′ f and so
es′ f ∈ W (s)
2. This is straightforward on noting that (s′ ss∗ )s(s′ ss∗ ) = s′ ss′ ss∗ ss∗ = s′ ss∗ . Note that
s′ ss∗ = s∗ ss′ . It is clear that s′ ss∗ ≤ s′ , s∗ , so suppose that t ≤ s′ , s∗ . Then there exist
e, f, g, h ∈ E(S) such that t = es′ = s′ f = gs∗ = s∗ h. Hence since t = s′ st = (s′ ss∗ )h
and t = tss′ = gs∗ ss′ = g(s′ ss∗ ) then t ≤ s′ ss∗ as required.
3. If s′∗ ∈ W (s′ ) then s′∗ = s′∗ s′ s′∗ = s′∗ s′ ss′ s′∗ = ss′ s′∗ s′ s′∗ = ss′ s′∗ = s′∗ s′ s′∗ s′ s =
s′∗ s′ s. Finally notice that for all e ∈ E,
s(s′ s′∗ s′ es′∗ s′ s) = (ss′ s′∗ s′ es′∗ s′ )s = s′∗ s′ es′∗ = es′∗ s′ s = es′∗
and so es′∗ ≤ s.
4. Clearly sW (s)s ⊆ W (s′ ). Let s′∗ ∈ W (s′ ) so that by part (3), s′∗ = ss′ s′∗ = ss′ s′∗ s′ s
and s′ s′∗ s′ ∈ W (s).
Now let s′∗ ∈ V (s′ ) ⊆ W (s′ ). Since s′ s′∗ = s′ s′∗ s′ s = s′ s then s′∗ = ss′ s′∗ = ss′ s.
If s∗ ∈ W (s) then W (s∗ ) = sW (s)s = W (s′ ) and since s′ ss∗ ∈ W (s) then ss′ ss∗ s ∈
W (s′ ).
3

5. Clearly W 6= Ø. Let s′ , t′ ∈ W with s′ ∈ W (s), t′ ∈ W (t) then it is easy to check that
s′ t′ ∈ W (ts) ⊆ W and by part (4), |V (s′ )| = 1 for each s′ ∈ W and so W is an inverse
subsemigroup of S. Alternatively, note that W = Reg(S) the set of regular elements
of S.
6. Let s′ ∈ W (s), s′∗ ∈ W (s′ ), s′∗ ′ ∈ W (s′∗ ). Then by part (3), s′∗ ′ ss′∗ = s′∗ ′ ss′ s′∗ s′∗ ′ =
′
′
′
s′∗ s′∗ s′∗ = s′∗ . On the other hand s′ = s′ ss′ = s′ (ss′ s)s′ ∈ W (W (s′ )) and the result
follows easily.
′

Lemma 1.5 ([13, Proposition 2]) A semigroup S is a group if and only if for every element s ∈ S, |L(s)| = 1.
It is also easy to see that
Lemma 1.6 Let S be an E−dense monoid. Then S is a group if and only if |E| = 1.
A subset A of a semigroup S is called unitary in S if whenever sa ∈ A or as ∈ A it necessarily
follows that s ∈ A. If E is a unitary subset of S then we shall refer to S as an E−unitary
semigroup.
Lemma 1.7 ([17], [15, Theorem 6.8]) Let S be an E−dense semigroup.
E−unitary if and only if E is a band and Eω = E.

Then S is

Lemma 1.8 ([3, Proposition 1.2]) Let S be an E−unitary semigroup. For all s ∈ S, if
s′ ∈ L(s) then s ∈ L(s′ ).

2

E−dense actions of E−dense semigroups

In this section we take inspiration from the theory of inverse semigroup actions, which in
turn is based on Schein’s representation theory of inverse semigroups by partial one-to-one
maps (see [1] and [7]).
Let S be an E−dense semigroup, let X be a non-empty set and let φ : S × X → X be a
partial map with the property that φ(st, x) exists if and only if φ(s, φ(t, x)) exists and then
φ(st, x) = φ(s, φ(t, x)).
We will, as is usual, denote φ(s, x) as sx and simply write (st)x as stx when appropriate.
By a partial map we of course mean that not every element of S need act on every element
of X. A more formal definition can be found in [7]. We say that φ is an E−dense action of
S on X, and refer to X as an E−dense S−act, if
1. the action is cancellative; meaning that whenever sx = sy then x = y;
2. the action is reflexive; that is to say, for each s ∈ S, if sx exists then there exists
s′ ∈ W (s) such that s′ (sx) exists.
The domain of an element s ∈ S is the set
DsX = {x ∈ X|sx exists}.
We shall denote DsX as simply Ds when the context is clear. We shall denote the domain
of an element x ∈ X by
Dx = {s ∈ S|sx exists}.
4

Clearly x ∈ Ds if and only if s ∈ Dx . Notice also that it follows from the definition that
x ∈ Ds if and only if x ∈ Ds′ s for some s′ ∈ W (s).
If S is a group then an E−dense act X is simply an S−set, while if S is an inverse semigroup
then an E−dense act is an inverse semigroup act defined by the Wagner-Preston representation ρ : S → I(X) where sx = ρ(s)(x) and Ds = dom(ρ(s)) (see Example 2.2 below for a
generalisation).
Let X be an E−dense S−act and let x ∈ X. We define the stabilizer of an element x as the
set Sx = {s ∈ S|sx = x}. The following is easy to establish.
Lemma 2.1 Let S be an E−dense semigroup and X an E−dense S−act. Let s, t ∈ S, x, y ∈
X. Then
1. E ∩ Dx ⊆ Sx ,
2. if s′ ∈ W (s) then x ∈ Ds′ if and only if x ∈ Dss′ ,
3. if s ∈ Dx then sx = y if and only if there exists s′ ∈ W (s) ∩ Dy such that x = s′ y,
4. if s, t ∈ Dx then sx = tx if and only if there exists s′ ∈ W (s) such that s′ t ∈ Sx . In
addition, any such s′ necessarily satisfies s′ ∈ Dsx ,
Example 2.2 (Wagner-Preston action) Let S be an E−dense semigroup with semilattice of
idempotents E and X a set on which S acts (on the left) via the representation ρ : S → T (X).
In other words the action on X is a total action. For each s ∈ S define
Ds = {x ∈ X| there exists s′ ∈ W (s), x = s′ sx} = {s′ sx|x ∈ X, s′ ∈ W (s)}
and define an E−dense action of S on X by s ∗ x = sx for all x ∈ Ds .
To see that ∗ really is an E−dense action suppose that x ∈ Dst so that there exists (st)′ ∈
W (st) such that x = (st)′ (st)x. By Lemma 1.1 there exists s′ ∈ W (s), t′ ∈ W (t) such that
(st)′ = t′ s′ and so x = t′ s′ stx. Then t′ tx = t′ tt′ s′ stx = t′ s′ stx = x and so x ∈ Dt . In
addition, s′ stx = s′ stt′ s′ stx = tt′ s′ stx = tx and tx ∈ Ds . Conversely, suppose that x ∈ Dt
and tx ∈ Ds . Then there exists t′ ∈ W (t), s′ ∈ W (s) such that x = t′ tx and tx = s′ stx and
so x = t′ s′ stx ∈ Dst . Clearly, (st) ∗ x = s ∗ (t ∗ x). Finally, if x, y ∈ Ds and s ∗ x = s ∗ y
then there exists s′ ∈ W (s), s∗ ∈ W (s) such that x = s′ sx, y = s∗ sy and such that sx = sy.
Hence
x = s′ sx = s′ sy = s′ ss∗ sy = s∗ ss′ sy = s∗ ss′ sx = s∗ sx = s∗ sy = y.
In addition, if x ∈ Ds then x = s′ sx for some s′ ∈ W (s), and so letting (s′ s)′ = s′ s ∈ W (s′ s)
then
(s′ s)′ (s′ s)x = s′ sx = x
and x ∈ Ds′ s as required. Hence ∗ satisfies the conditions of an E−dense action.
In particular, we can take X = S, or indeed any left ideal of S, with (total) action given by
the multiplication in S.
A element x of X is said to be effective if Dx 6= Ø. An E−dense S−act X is effective if all
its elements are effective. An E−dense S−act is transitive if for all x, y ∈ X, there exists
s ∈ S with y = sx. Notice that this is equivalent to X being locally cyclic in the sense
that for all x, y ∈ X there exists z ∈ X, s, t ∈ Dz with x = sz, y = tz. We shall consider
transitive acts in more detail in Section 2.2.
If X is an E−dense S−act and Y is a subset of X then we shall say that Y is an E−dense
S−subact of X if for all s ∈ S, y ∈ DsX ∩ Y ⇒ sy ∈ Y . Notice that this makes Y an E−dense
S−act with the action that induced from X and DsY = DsX ∩ Y for all s ∈ S.
5

Let X and Y be two E−dense S−acts. A function f : X → Y is called an (E−dense)
S−map if for all s ∈ S, x ∈ DsX if and only if f (x) ∈ DsY and then f (sx) = sf (x).
For example, if Y is an S−subact of an E−dense S−act X, then the inclusion map ι : Y → X
is an S−map.
Let x ∈ X and define the S−orbit of x as
Sx = {sx|s ∈ Dx } ∪ {x}.
Notice that if x is effective, then there exists s ∈ Dx and so for any s′ ∈ W (s) ∩ Dsx , x =
s′ sx ∈ {sx|s ∈ Dx } = Sx. However if x is not effective then {sx|s ∈ Dx } = Ø and Sx = {x}.
Notice also that Sx is an E−dense S−subact of X (the subact generated by x) and that the
X
action is such that, for all tx ∈ Sx and all s ∈ S, tx ∈ DsSx if and only if x ∈ Dst
and in
which case s(tx) = (st)x. Then we have
Lemma 2.3 For all x ∈ X, if x is effective then so is Sx, in which case Sx is a transitive
E−dense S−act. Conversely, if an E−dense S−act is effective and transitive then it has
only one S−orbit.
Proof.
Suppose that x is effective. Then let s ∈ Dx so that sx ∈ Sx, and notice that
there exists s′ ∈ W (s) ∩ Dsx . Therefore ss′ (sx) = sx ∈ Sx and hence Sx is effective. If
y = s1 x and z = s2 x then put t = s1 s′2 , where s′2 ∈ W (s2 ) ∩ Dz , to get y = tz (if x = y 6= z
then take t = s′2 ; if x = z 6= y then take t = s1 while if x = y = z take t = s′ s where
s ∈ Dx , s′ ∈ W (s) ∩ Dsx ).
The converse is easy. Note that in this case Sx = {sx|s ∈ Dx }.
Notice that Sx = Sy if and only if y ∈ Sx and so the orbits partition X.
Recall that Green’s L−relation is given by aLb if and only if S 1 a = S 1 b. As is normal, we
shall denote the L−class containing a as La .
Proposition 2.4 Let S be an E−dense semigroup with semilattice of idempotents E and
consider S as an E−dense S−act with the Wagner-Preston action.
1. If e ∈ E then Se = eω and Se = Le .
2. For all s ∈ S and for all s′ ∈ W (s), Ss ⊆ (ss′ )ω and Ss ⊆ Ls . In addition Ss = (ss′ )ω
for some s′ ∈ W (s) if and only if s is regular, in which case Ss = Ls and we can
assume that s′ ∈ V (s).
3. For all se ∈ Se (the orbit of e), Sse = (ses′ )ω for some s′ ∈ W (s) and Sse = Lse .
4. For all s ∈ S, s′ ∈ W (s) it follows that Ss′ = (s′ s)ω and Ss′ = Ls′ .
Proof.
1. If t ∈ Se then there exists t′ ∈ W (t) such that e = t′ te = t′ e. Hence
′
e = e(t t) = (tet′ )t and so e ≤ t and t ∈ eω.
Conversely, if e ≤ t then there exists f, g ∈ E such that e = f t = tg and it is easy to
check that e = et = te. Since e ∈ W (e) then there exist e′ ∈ W (e), t′ ∈ W (t) such
that e = e′ t′ and so t′ te = t′ tee′ t′ = ee′ t′ = e and t ∈ De and since te = e then t ∈ Se
as required.
If te ∈ Se then there exists t′ ∈ W (t) such that e = t′ te. Hence teLe. On the other
hand, if sLe then there exist u, v ∈ S 1 such that us = e, ve = s, from which we deduce
that se = s. If s = e then obviously s ∈ Se, otherwise note that s′ = eu ∈ W (s) and
so since s′ se = euse = e then s ∈ De and s = se ∈ Se and hence the orbit of e and
L−class containing e coincide.
6

2. Let t ∈ Ss so that there exists t′ ∈ W (t) such that s = t′ ts and ts = s. Then
ss′ = tss′ = t(t′ tss′ ) = (tss′ t′ )t
and so t ∈ (ss′ )ω. If rs ∈ Ss then there exists r′ ∈ W (r) such that s = r′ rs and so
rsLs and Ss ⊆ Ls .
If (ss′ )ω ⊆ Ss then in particular ss′ ∈ Ss and so s′ ∈ Ds . Hence there exists s′∗ ∈
W (s′ ) such that s = s′∗ s′ s and so s = s′∗ ∈ W (s′ ) which means that s is regular and
s′ ∈ V (s). Conversely, if s is regular then there exists s′ ∈ V (s) and so ss′ ∈ Ss .
Hence (ss′ )ω ⊆ Ss since Ss is closed. In this case, since L is a right congruence, then
for any s′ ∈ V (s)
′

ts ∈ Ss ⇐⇒ t ∈ Ds ⇐⇒ t ∈ Dss ⇐⇒ tss′ ∈ Sss′ ⇐⇒ tss′ Lss′ ⇐⇒ tsLs
Hence Ss = Ls .
3. This follows from part (2) since se is regular.
4. Since s′ is regular then from part(2) there exists s′∗ ∈ V (s′ ) such that Ss′ = (s′ s′∗ )ω
and Ss′ = Ls′ . But from Lemma 1.4, s′∗ = ss′ s and the result follows.
Let x ∈ X and set E x = E ∩ Dx . In analogy with group theory, and following [6], we shall
say that an E−dense S−act X is locally free if for all x ∈ X, Sx = (E x )ω.
Theorem 2.5 Let S be an E−dense semigroup with semilattice of idempotents E and let
X be an E−dense S−act. Then X is locally free if and only if for all x ∈ X, s, t ∈ Dx ,
whenever sx = tx there exists e ∈ Sx such that se = te.
Proof.
Suppose that S acts locally freely on X and that sx = tx for some x ∈ X, s, t ∈
Dx . Then there exists s′ ∈ W (s) with s′ t ∈ Sx and so there exist f, g ∈ E, e ∈ E x with
(s′ t)g = f (s′ t) = e. Since e ∈ W (e) then there exist t′ ∈ W (t), s′∗ ∈ W (s′ ), f ′ ∈ W (f ) with
e = t′ s′∗ f ′ . Hence since ge = eg = e, t′ te = e and ss′ s′∗ = s′∗ then
se = sf s′ tt′ s′∗ f ′ = tt′ sf s′ tt′ s′∗ f ′ = tt′ ss′ tgt′ s′∗ f ′ = tt′ tgt′ s′∗ f ′ = tt′ tge = te.
Conversely, suppose that s ∈ Sx so that sx = x. Then there exists s′ ∈ W (s) such that sx =
s′ sx. By assumption there exists e ∈ E x such that se = s′ se = es′ s. But ses′ = es′ ss′ = es′
and so se = (ses′ )s ∈ E x and hence s ∈ (E x )ω and X is locally free.

2.1

Graded actions

Let S be an E−dense semigroup with semilattice of idempotents E. We can consider E as
an E−dense S−act with action given by the Munn representation on E. In more detail, let
e ∈ E and let [e] denote the order ideal generated by e. This is the set
[e] = {s ∈ S|s ≤ e} = {s ∈ E|s = es = se} = eE.
The second equality is easy to establish on observing that [e] ⊆ E (see [14, Lemma 2.1]).
Lemma 2.6 Let S be an (E−dense) semigroup with semilattice of idempotents E. Then
for all e ∈ E, [e] = W (e).

7

Proof.
If s ∈ [e] then s = es = se and so ses = s2 = s. Hence [e] ⊆ W (e). Conversely,
if s ∈ W (e) then ses = s and so es, se ∈ E. Hence s = ses = sees ∈ E. Consequently,
s = se = es ∈ [e] and so [e] = W (e).
S
The action of S on E is given as follows. For each s ∈ S define Ds = s′ ∈W (s) [s′ s] and for
each x ∈ Ds ⊆ E define an action s ∗ x = sxs′ where x ∈ [s′ s] with s′ ∈ W (s). Notice that if
x ∈ [s∗ s] ∩ [s′ s] and s′ , s∗ ∈ W (s) then x = s′ sx = xs′ s and x = s∗ sx = xs∗ s. Consequently,
sxs′ = sxs∗ ss′ = ss′ sxs∗ = sxs∗ .
So the action is well-defined. Notice then that if x ∈ Dst then x ≤ (st)′ (st) for some (st)′ ∈
W (st). Since, by Lemma 1.1, W (st) = W (t)W (s) then there exists s′ ∈ W (s), t′ ∈ W (t)
such that x = t′ s′ stx = xt′ s′ st. Hence xt′ t = t′ tx = t′ tt′ s′ stx = t′ s′ sx = x and so x ∈ Dt .
In addition s′ s(txt′ ) = (txt′ )s′ s = txt′ s′ stt′ = txt′ and so t ∗ x ∈ Ds .
Conversely, suppose that x ∈ Dt and t ∗ x ∈ Ds so that x = t′ tx = xt′ t for some t′ ∈ W (t)
and that txt′ = s′ stxt′ = txt′ s′ s for some s′ ∈ W (s). Then
xt′ s′ st = t′ s′ stx = t′ s′ stxt′ t = t′ txt′ t = x
and so x ∈ Dst .
Now, if x ∈ Dst then for some (st)′ ∈ W (st), s′ ∈ W (s), t′ ∈ W (t) we have
(st) ∗ x = (st)x(st)′ = stxt′ s′ = s ∗ (txt′ ) = s ∗ (t ∗ x).
If s∗ x = s∗ y then x = s′ sx = xs′ s, y = s∗ sy = ys∗ s and sxs′ = sys∗ for some s′ , s∗ ∈ W (s).
Hence x = s′ sxs′ s = s′ sys∗ s and so x ≤ y. Dually y ≤ x and so x = y.
Finally, if x ∈ Ds then there exists s′ ∈ W (s) such that x = s′ sx = xs′ s. Since s′ s ∈ W (s′ s)
then it easily follows that x ∈ Ds′ s . Consequently we have established that E is an E−dense
S−act with action given as above.
Let X be an E−dense S−act. Following [18] we say that the action is graded if there exists
a function p : X → E such that for all e ∈ E, De = p−1 ([e]), and refer to p as the grading.
Lemma 2.7 Let S be an E−dense semigroup with semilattice of idempotents E, and X
a graded E−dense S−act. Then X is effective and for all x ∈ X, p(x) is the minimum
idempotent in Sx .
Proof.
Suppose that X is graded with grading p : X → E and let x ∈ X. Then as
x ∈ p−1 ([p(x)]) = Dp(x) for all x ∈ X it follows that X is effective. Notice also that
p(x) ∈ Sx ∩ E. Suppose that there exists e ∈ Sx ∩ E. Then x ∈ De = p−1 ([e]) and so
p(x) ∈ [e]. Hence p(x) ≤ e as required.
The following is fairly clear.
Proposition 2.8 Let S be an E−dense semigroup with semilattice of idempotents E, and
X a graded E−dense S−act with grading p : X → E. Then X is locally free if and only if
for all x ∈ X, Sx = p(x)ω.
Conversely, if X is an E−dense S−act with the property that for all x ∈ X there exists
ex ∈ E with Sx = ex ω, then X is locally free and graded with grading p : X → E given by
p(x) = ex .

8

Proof.
Suppose that X is locally free. If s ∈ (E x )ω then there exists e ∈ E x such that
e ≤ s. Then since e ∈ Sx it follows that p(x) ≤ e ≤ s. On the other hand, it is clear that
p(x)ω ⊆ (E x )ω ⊆ Sx and so Sx = p(x)ω.
If Sx = p(x)ω then clearly Sx ⊆ (E x )ω. But (E x )ω ⊆ Sx and so X is locally free.
The converse follows easily from Lemma 2.7.
Notice that it follows from Lemma 2.7 that the grading function p is unique. Notice also
that if p(x)′ ∈ W (p(x)) ∩ Dp(x)x then p(x)′ p(x) ∈ Sx and so p(x)′ ∈ Sx . Consequently
p(x)p(x)′ ∈ Sx . Moreover p(x) ≤ p(x)′ p(x), p(x)p(x)′ from which we easily deduce that
p(x) = p(x)′ p(x) = p(x)p(x)′ . But then p(x)′ = p(x)′ p(x)p(x)′ = p(x)p(x)′ = p(x).
Lemma 2.9 Let S be an E−dense semigroup with semilattice of idempotents E and X a
graded E−dense S−act with grading p. Then for x ∈ Ds , if s′ s = p(x) for s′ ∈ W (s) then
ss′ = p(sx).
Proof.
Suppose that s′ s = p(x). Then x ∈ Ds′ s and so x ∈ Ds . In addition, sx ∈ Ds′
′
and so ss ∈ Ssx which means that p(sx) ≤ ss′ . Now s′ s = s′ ss′ s ≥ s′ p(sx)s (since E is a
semilattice). But since s′ p(sx)s ∈ Sx ∩ E then by Lemma 2.7, p(x) = s′ s = s′ p(sx)s and
so ss′ = sp(x)s′ = ss′ p(sx)ss′ , or in other words ss′ ≤ p(sx). But as ss′ ≥ p(sx) then
p(sx) = ss′ as required.
Corollary 2.10 Let S be an E−dense semigroup with semilattice of idempotents E and X a
graded E−dense S−act with grading p. Let s ∈ S and x ∈ Ds . Then for all s′ ∈ W (s)∩Dsx ,
p(sx) = sp(x)s′ .
Proof.
Let t = sp(x) and let s′ ∈ W (s) ∩ Dsx . Then t′ = p(x)s′ ∈ W (sp(x)) = W (t).
′
Hence t t = p(x)s′ sp(x) = s′ sp(x) = p(x) as s′ s ∈ Sx . In addition, tx = sp(x)x = sx and so
by Lemma 2.9, p(sx) = p(tx) = tt′ = sp(x)p(x)s′ = sp(x)s′ as required.

Proposition 2.11 (Cf. [18, Proposition 1.1]) Let S be an E−dense semigroup with semilatticeS
of idempotents E and X a graded E−dense S−act
with grading p and let s ∈ S. Then
S
Ds = s′ ∈W (s) p−1 ([s′ s]) and sX = {sx|x ∈ Ds } = s′ ∈W (s) p−1 ([ss′ ]).
Let s ∈ S, x ∈ Ds , s′ ∈ W (s) ∩ Dsx . Then x ∈ Ds′ s = p−1 ([s′ s]) and so Ds =
([s′ s]). Since p(sx) = sp(x)s′ = (sp(x)s′ )(ss′ ) = (ss′ )(sp(x)s′ ) ≤ ss′ then
s′ ∈W (s) p
′
p(sx) ∈ [ss ] and so sx ∈ p−1S
([ss′ ]). Conversely, if y ∈ p−1 ([ss′ ]) = Dss′ then y = ss′ y = sx
′
where x = s y. Hence sX = s′ ∈W (s) p−1 ([ss′ ]).
Proof.
S

−1

Theorem 2.12 Let S be an E−dense semigroup with semilattice of idempotents E and X
an E−dense S−act. The following are equivalent.
1. X is a graded E−dense S−act,
2. there exists an E−dense S−map f : X → E,
3. X is an effective E−dense S−act and for all x ∈ X, Sx contains a minimum idempotent.

9

X
′
sx
Proof.
(1) =⇒ (2). If x ∈ D
Ss then from Corollary 2.10, for all s ∈ W (s)∩D , p(sx) =
sp(x)s′ = s ∗ p(x) and p(x) ∈ s′ ∈W (s) [s′ s]. Hence p(x) ∈ DsE . Conversely, if p(x) ∈ DsE
S
then p(x) ∈ s′ ∈W (s) [s′ s] and so there exists s′ ∈ W (s) such that x ∈ p−1 ([s′ s]) ⊆ DsX . In
addition s ∗ p(x) = sp(x)s′ = p(sx) and it follows that p is an S−map.
(2) =⇒ (3). Suppose that X is an S−act with an E−dense S−map f : X → E and let
x ∈ X. Then as f (x) ∈ DfE(x) , it follows that x ∈ DfX(x) and X is effective. Notice also that
f (x) ∈ Sx ∩ E. Suppose then that there exists e ∈ Sx ∩ E. Then x ∈ DeX so f (x) ∈ DeE = [e]
and so f (x) ≤ e as required.
(3) =⇒ (1). If X is an effective E−dense S−act and for all x ∈ S, Sx contains a minimum
idempotent, say ex , then define a function p : X → E by p(x) = ex . Suppose then that
e ∈ E and x ∈ DeX . Then e ∈ Sx ∩ E and so p(x) ≤ e. Hence p(x) ∈ [e] or in other words
x ∈ p−1 ([e]) and so DeX ⊆ p−1 ([e]). On the other hand, if x ∈ p−1 ([e]) then p(x) ∈ [e] and
so p(x) = p(x)e and since x ∈ Dp(x) then x ∈ De as well. Hence De = p−1 ([e]) and p is a
grading.

It is easy to check that E is a graded E−dense S−act with grading 1E : E → E, the identity
function. The following is clear.
Corollary 2.13 If X is an E−dense S−act and E is finite then X is graded.
Let (X, p) and (Y, q) be graded E−dense S−acts with grading functions p and q. A graded
morphism is an E−dense S−map f : X → Y such that qf = p. It is clear that graded
E−dense S−acts and graded morphisms form a category and that (E, 1E ) is a terminal
object in this category.

2.2

Transitive S−acts

An E−dense S−act is called indecomposable if it cannot be written as the coproduct (i.e.
disjoint union) of two other E−dense S−acts. In particular, a transitive S−act is easily seen
to be indecomposable. Conversely, if X is indecomposable, then suppose that Y = X \ Sx 6=
Ø for some x ∈ X. Then Y cannot be a subact of X as X is indecomposable, so there
exists y ∈ Y, s ∈ S with sy ∈ Sx and hence y ∈ Sx, a contradiction. Therefore X = Sx is
transitive. The transitive S−acts are therefore the ‘building blocks’ of E−dense S−acts. In
this section, we restrict our attention, in the main, to those E−dense semigroups where E
is a semilattice.
Suppose that S is an E−dense semigroup and that H is a subsemigroup of S. If for all
h ∈ H, W (h) ∩ H 6= Ø then we will refer to H as an E−dense subsemigroup of S. For
example, if E is a band then E is an E−dense subsemigroup of S.
Lemma 2.14 Let S be an E−dense semigroup with semilattice of idempotents E and let H
be an E−dense subsemigroup of S. Then Hω is an E−dense subsemigroup of S.
Proof.
Suppose that x, y ∈ Hω so that there exist a, b ∈ H such that a ≤ x, b ≤ y. In
addition, there exists a′ ∈ W (a) ∩ H, b′ ∈ W (b) ∩ H. Hence there exists e, f, g, h ∈ E such
that a = xe = f x, b = yg = hy. Let x′ ∈ W (x), f ′ ∈ W (f ), y ′ ∈ W (y), h′ ∈ W (h) be such
that a′ = x′ f ′ ∈ W (a), b′ = y ′ h′ ∈ W (b). Then
(xy)(y ′ h′ hx′ f ′ f xy) = (xyy ′ h′ hx′ f ′ f )(xy) = (f ′ f )(xhyy ′ h′ x′ )(xhy) =
(f ′ f )(f xhyy ′ h′ x′ )(xhy) = (f xhyy ′ h′ x′ )(f ′ f xhy) = abb′ a′ ab ∈ H

10

and so xy ∈ Hω and Hω is a subsemigroup of S. Now suppose that x ∈ Hω so that there
exists h ∈ H and e, f ∈ E such that h = ex = xf . Suppose also that h′ ∈ W (h) ∩ H so that
there exists x′ ∈ W (x), f ′ ∈ W (f ) such that h′ = f ′ x′ . Then
x′ (xf f ′ x′ ) = (x′ xf f ′ )x′ = f f ′ x′ xf f ′ x′ = f ′ x′ xf f f ′ x′ = h′ hh′ = h′ ∈ H
and so x′ ∈ Hω and Hω is an E−dense subsemigroup of S.
Lemma 2.15 Let S be an E−dense semigroup with semilattice of idempotents E and let H
be an E−dense subsemigroup of S. Let x, y ∈ S, x′ ∈ W (x), y ′ ∈ W (y), e ∈ E. Then
1. if x′ ex ∈ Hω then x′ x ∈ Hω;
2. if x′ ey, y ′ y ∈ Hω then x′ y ∈ Hω.
Proof.
Let x, y ∈ S, x′ ∈ W (x), y ′ ∈ W (y), e ∈ E. Notice that by Lemma 2.14, Hω is an
E−dense subsemigroup of S.
1. By assumption there exists f, g ∈ E, a ∈ H such that a = (x′ ex)f = g(x′ ex). Consequently
a = x′ exf = (x′ x)(x′ exf ) = (x′ exf )(x′ x)
and so a ≤ x′ x and x′ x ∈ Hω.
2. By assumption there exists f, g ∈ E, a ∈ H such that a = (x′ ey)f = g(x′ ey). Consequently
ay ′ y = x′ eyf y ′ y = x′ eyy ′ yf = (x′ y)(y ′ eyf ) = x′ xx′ eyf y ′ y = (x′ eyf y ′ x)(x′ y)
and so ay ′ y ≤ x′ y and x′ y ∈ Hω as required.

Proposition 2.16 Let S be an E−dense semigroup with semilattice of idempotents E and
let H be an E−dense subsemigroup of S. Then the following are equivalent
1. H is ω−closed in S;
2. H is unitary in S;
3. H is ωM −closed in S.
Proof.
(1) =⇒ (2). Suppose that H is ω−closed in S and suppose that hs = h1 for
some s ∈ S, h, h1 ∈ H. Then there exists h′ ∈ W (h) ∩ H, h′1 ∈ W (h1 ) ∩ H and so there exist
s′ ∈ W (s), h∗ ∈ W (h) such that h′1 = s′ h∗ ∈ W (hs). Then
s(s′ h′ hh∗ hs) = (ss′ h′ hh∗ h)s = h′ hss′ h∗ h1 = h′ h1 h′1 h1 ∈ H
and so s ∈ Hω = H. Consequently H is left unitary in S. The right unitary property
follows in a similar way.
(2) =⇒ (3). Suppose H is unitary in S and that s ≥M h for h ∈ H. Then there
exist x, y ∈ S with h = xs = sy, xh = hy = h. Let h′ ∈ W (h) ∩ H and notice that
h′ hyh′ h = h′ hh′ h = h′ h ∈ H. Therefore y ∈ H and so s ∈ H and H is ωM −closed in S.
(3) =⇒ (1). As H ⊆ Hω ⊆ HωM then this is clear.

11

In view of the above result, we shall simply say that a set A is closed if it is ω−closed.
We briefly review Schein’s theory of partial congruences when applied to E−dense semigroups which have a semilattice of idempotents (see [1, Chapter 7] or [7, Chapter 5] for
more details of the case for inverse semigroups).
Let T ⊆ S be sets and suppose that ρ is an equivalence on T . Then we say that ρ is a partial
equivalence on S with domain T . It is easy to establish that ρ is a partial equivalence on
S if and only if it is symmetric and transitive. If now T is an E−dense subsemigroup of
an E−dense semigroup S and if ρ is left compatible with the multiplication on S (in the
sense that for all s ∈ S, (u, v) ∈ ρ either su, sv ∈ T or su, sv ∈ S \ T and (su, sv) ∈ ρ in the
former case) then ρ is called a left congruence on S and the set T /ρ of ρ−classes will often
be denoted by S/ρ.
Theorem 2.17 Let H be a closed E−dense subsemigroup of an E−dense semigroup S and
suppose that E is a semilattice. Define
πH = {(s, t) ∈ S × S|∃s′ ∈ W (s), s′ t ∈ H}.
Then πH is a left partial congruence on S and the domain of πH is the set DH = {s ∈
S|∃s′ ∈ W (s), s′ s ∈ H}.
The (partial) equivalence classes are the sets (sH)ω for s ∈ DH . The set (sH)ω is the
equivalence class that contains s and in particular H is one of the πH −classes.
Proof.
It is clear that πH is reflexive on DH . Notice first that if there exists s′ ∈ W (s)
such that s′ t ∈ H then s′ ss′ t ∈ H and so since H is unitary, s′ s ∈ H. Suppose then
that (s, t) ∈ πH . Then there exists s′ ∈ W (s), t′ ∈ W (t) such that s′ s, t′ t, s′ t ∈ H. Let
t∗ ∈ W (t), s′∗ ∈ W (s′ ) be such that t∗ s′∗ ∈ W (s′ t) ∩ H. Then let x = t′ s and x′ =
(s′ t)(t′ t) ∈ W (x) so that x′∗ = (t′ t)(t∗ s′∗ ) ∈ W (x′ ) ∩ H. By Lemma 1.4 x′∗ = (t′ t)x′∗ ≤ x
and so t′ s = x ∈ H and hence πH is symmetric.
Now suppose that (s, t), (t, r) ∈ πH . Then there exists s′ ∈ W (s), t′ ∈ W (t), r′ ∈ W (r) such
that s′ s, s′ t, t′ t, t′ r, r′ r ∈ H. Consequently
(s′ r)(r′ tt′ ss′ r) = (s′ rr′ tt′ s)(s′ r) = s′ tt′ rr′ ss′ r = s′ tt′ rr′ r ∈ H
and so s′ r ∈ Hω = H and πH is transitive.
Suppose that (s, t) ∈ πH and that r ∈ S and suppose further that rs, rt ∈ DH . Then there
exists s′ ∈ W (s), t′ ∈ W (t) such that s′ s, t′ t, s′ t ∈ H. Further, there exists s∗ ∈ W (s), t∗ ∈
W (t), r′ , r∗ ∈ W (r) such that s∗ r′ rs, t∗ r∗ rt ∈ H. From Lemma 1.4, s∗ ss′ ∈ W (s) and
so (rs)′ (rt) = s∗ ss′ r′ rt = s∗ r′ rss′ t ∈ H. Hence (rs, rt) ∈ πH and πH is a left partial
congruence on S.
Now suppose that s ∈ (tH)ω where t′ t ∈ H. Then there exists h ∈ H such that th ≤ s and so
there exists e, f ∈ E such that th = se = f s. Hence t′ th = t′ se = t′ f s = t′ tt′ f s = (t′ f t)t′ s
and so t′ th ≤ t′ s and t′ s ∈ Hω = H. Consequently s ∈ [t]πH . On the other hand, if
s ∈ [t]πH then there exists s′ ∈ W (s), t′ ∈ W (t) such that s′ s, t′ t, s′ t ∈ H. Hence there exists
t∗ ∈ W (t), s′∗ ∈ W (s′ ) such that t∗ s′∗ ∈ W (s′ t) ∩ H. Now by Lemma 1.4, tt∗ s′∗ ≤ s and
hence s ∈ (tH)ω.
Finally, if s ∈ DH then there exists s′ ∈ W (s) such that s′ s ∈ H and so s(s′ s) = (ss′ )s ∈ sH
and hence s ∈ (sH)ω. In particular, for all h1 , h2 ∈ H we see that h1 πH h2 and so H =
Hω = (hH)ω for all h ∈ H is an equivalence class.
The sets (sH)ω, for s ∈ DH , are called the left ω−cosets of H in S. The set of all left
ω−cosets is denoted by S/H. Notice that (sH)ω is a left ω−coset if and only if there exists
s′ ∈ W (s) such that s′ s ∈ H. The following is then immediate.
12

Proposition 2.18 Let H be a closed E−dense subsemigroup of an E−dense semigroup S
in which E is a semilattice, and let (aH)ω, (bH)ω be left ω−cosets of H. Then the following
statements are equivalent:
1. (aH)ω = (bH)ω;
2. aπH b that is, there exists b′ ∈ W (b), b′ a ∈ H;
3. a ∈ (bH)ω;
4. b ∈ (aH)ω.

Lemma 2.19 With H and S as in Theorem 2.17,
1. precisely one left ω−coset, namely H, contains idempotents,
2. each left ω−coset is closed,
3. πH is left cancellative i.e. xaπH xb implies that aπH b,
4. ((st)H)ω is an ω−coset if and only if (tH)ω and (s((tH)ω))ω are ω−cosets and then
(s((tH)ω))ω = ((st)H)ω.
Proof.
1. If e is an idempotent contained in an ω−coset then there exists e′ ∈ W (e)
′
with e e ∈ H. As e′ e ≤ e then e ∈ Hω = H. As H is an E−dense subsemigroup of S
then for each h ∈ H there exists h′ ∈ W (h) ∩ H and so h′ h ∈ H and hence E(H) 6= Ø.
2. This is clear.
3. Suppose that (xa, xb) ∈ πH so that there exists (xa)′ ∈ W (xa), (xb)′ ∈ W (xb) such
that (xa)′ (xa), (xa)′ (xb) ∈ H. Then there exists x′ ∈ W (x), a′ ∈ W (a) such that
a′ x′ xb ∈ H and a′ x′ xa ∈ H. It follows from Lemma 2.15 that a′ a, a′ b ∈ H. Hence
aπH b.
4. Suppose that ((st)H)ω is an ω−coset, so that there exists (st)′ ∈ W (st) such that
(st)′ st) ∈ H. Then there exist s′ ∈ W (s), t′ ∈ W (t) such that t′ s′ = (st)′ . Since
t′ s′ st ∈ H and H is closed then it follows from Lemma 2.15 that t′ t ∈ H and so
(tH)ω is an ω−coset. If x ∈ (s((tH)ω))ω then there exists y ∈ (tH)ω such that
sy ≤ x and so there exists h ∈ H such that th ≤ y. Hence there exist idempotents
e1 , e2 , f1 , f2 such that sy = e1 x = xf1 and th = e2 y = yf2 . Now let h′ ∈ W (h)
then h′ t′ ∈ W (th) = W (yf2 ) and so there exists f2′ ∈ W (f2 ) and y ′ ∈ W (y) such that
h′ t′ = f2′ y ′ . But y ′ s′ ∈ W (sy) = W (xf1 ) and so there exist f1′ ∈ W (f1 ) and x′ ∈ W (x)
such that y ′ s′ = f1′ x′ . Hence
x(f1 f2 f2′ f1′ f1 f2 x′ x) = (xf1 f2 f2′ f1′ f1 f2 x′ )x
= sthf2′ f1′ x′ xf1 f2 = sthh′ t′ s′ sth ∈ (st)H
and so x ∈ ((st)H)ω.
On the other hand, suppose that x ∈ ((st)H)ω so that there exists e, f ∈ E, h ∈ H such
that ex = xf = sth. Then s(th) ≤ x and th ∈ tH ⊆ (tH)ω and hence x ∈ (s((tH)ω))ω.
Conversely, if (tH)ω and (s((tH)ω))ω are ω−cosets then as t ∈ (tH)ω it follows
that st ∈ s((tH)ω) ⊆ (s((tH)ω))ω. Which means that (s((tH)ω))ω is the ω−coset
containing st and so equals ((st)H)ω.

13

Notice that Sx is a closed E−dense subsemigroup of S for every x ∈ X.
Theorem 2.20 For all x ∈ X, Sx is either empty or a closed E−dense subsemigroup of S.
Proof.
Assume that Sx 6= Ø. If s, t ∈ Sx then x = sx = s(tx) = (st)x and so Sx is a
subsemigroup. Also sx = x implies that x = s′ x for any s′ ∈ W (s) ∩ Dsx and so Sx is an
E−dense subsemigroup of S. Let s ≤ h with s ∈ Sx . Then there exist e, f ∈ E such that
s = he = f h. Consequently e ∈ Dx and h ∈ Dex = Dx and so hx = hex = sx = x which
means that h ∈ Sx . Hence Sx is ω−closed and so closed.
From Lemma 2.19 we can easily deduce the following important result.
Theorem 2.21 If H is a closed E−dense subsemigroup of an E−dense semigroup S with
semilattice of idempotents E then S/H is a transitive E−dense S−act with action given by
s · X = (sX)ω whenever X, sX ∈ S/H. Moreover, it is easy to establish that SHω = H.
Proof.
Let X = (rH)ω be an ω−coset and suppose that s, t ∈ S and that X ∈ Dst .
Then by Lemma 2.19, ((st)X)ω = (st(rH)ω)ω is an ω−coset and
(st) · X = ((st)X)ω = ((str)H)ω = s · (t · X).
In addition if s · X = s · Y then (sX)ω = (sY )ω and so Lemma 2.19 X = Y . Now suppose
that X ∈ Ds . We are required to show that there exists s′ ∈ W (s) ∩ DsX . Suppose then
that X = (tH)ω so that s · X = ((st)H)ω. Then there exists (st)′ ∈ W (st) such that
(st)′ (st) ∈ H. Hence there exist s′ ∈ W (s), t′ ∈ W (t) such that t′ s′ st ∈ H. Consequently,
t′ s′ (ss′ s)s′ st ∈ H and since t′ s′ (ss′ s) ∈ W (s′ st) then there exists (s′ st)′ ∈ W (s′ st) such that
(s′ st)′ (s′ st) ∈ H and so ((s′ st)H)ω is an ω−coset of H and s′ ∈ W (s) ∩ DsX as required.
If (sH)ω and (tH)ω are ω−cosets then there exist s′ ∈ W (s), t′ ∈ W (t) such that s′ s, t′ t ∈ H.
Now as s′ (ss′ s)t′ = s′ st′ ∈ W (ts′ s) and as s′ st′ ts′ s = t′ ts′ s ∈ H then ((ts′ s)H)ω is an
ω−coset. Moreover, as (ts′ s)t′ t = tt′ (ts′ s) ∈ tH then ts′ s ∈ (tH)ω and so (tH)ω =
((ts′ s)H)ω = (ts′ ) · ((sH)ω) and S/H is transitive.
Finally SHω = {s ∈ S|(sH)ω = Hω}. Hence sπH h for any h ∈ H and so s ∈ H as H is an
ω−coset.
The converse of Theorem 2.21 is also true.
Theorem 2.22 Let S be an E−dense semigroup with semilattice of idempotents E, let X
be an effective, transitive E−dense S−act, let x ∈ X and let H = Sx . Then X is isomorphic
to S/H. If K is a closed E−dense subsemigroup of S and if X is isomorphic to S/K then
there exists x ∈ X such that K = Sx .
Proof.
Let y ∈ X and notice that since X is transitive then there exists s ∈ S such that
y = sx. Notice then that there exists s′ ∈ W (s) ∩ Dsx such that s′ s ∈ Sx = H. Moreover
if y = tx for some t ∈ S then sx = tx and so s′ t ∈ H and hence (sH)ω = (tH)ω. Therefore
we have a well-defined map φ : X → S/H given by
φ(y) = (sH)ω.
Since φ(sx) = (sH)ω for all (sH)ω ∈ S/H then φ is onto. If (sH)ω = (tH)ω then s′ t ∈
H = Sx and so sx = tx and φ is a bijection. Finally, suppose φ(y) = (sH)ω and t ∈ S.
Then y ∈ Dt if and only if t ∈ Dy if and only if ts ∈ Dx if and only if there exists
(ts)′ ∈ W (ts) such that (ts)′ (ts) ∈ Sx = H if and only if ((ts)H)ω is an ω−coset if and only
if φ(y) = (sH)ω ∈ Dt . In this case it is clear that φ(ty) = tφ(y) and φ is an isomorphism.
14

By assumption there is an isomorphism θ : S/K → X. Let x = θ(Kω) so that sx = θ((sK)ω)
for all s ∈ DK . Notice also that since θ is an S−map then s ∈ Dx if and only if s ∈ DK . If
s ∈ Sx then θ(Kω) = θ((sK)ω) and so s ∈ K as θ is an isomorphism. On the other hand,
if s ∈ K then sx = θ((sK)ω) = θ(Kω) = x and so s ∈ Sx as required.
Recall that Le denotes the L−class containing e.
Theorem 2.23 Let S be an E−dense semigroup with a semilattice of idempotents E and
let X be a locally free, transitive, graded E−dense S−act with grading p. Then there exists
e ∈ E such that X ∼
= Se ∼
= Le . Conversely, if e ∈ E then the orbit Se of e in the E−dense
S−act S (with the Wagner-Preston action) is a locally free, transitive, graded E−dense
S−act.
Proof.
If X is transitive then X ∼
= Sx for some (any) x ∈ X. Using a combination of
Theorem 2.21, Proposition 2.8 and Proposition 2.4, we deduce
X∼
= S/Sx = S/p(x)ω ∼
= S/Sp(x) = Sp(x) = Lp(x) .
Conversely, the orbit Se is clearly a transitive E−dense S−act. By Proposition 2.4, Ste =
(tet′ )ω and so by Proposition 2.8 Se is locally free and graded with grading p : Se → E
given by p(te) = tet′ .
Lest X be a graded S−act and let x ∈ X. If p(x) ∈ DsS then there exists s′ ∈ W (s) such
that p(x) = s′ sp(x) and so it follows that x ∈ DsX . Conversely, if x ∈ DsX then there exists
s′ ∈ W (s) ∩ Dsx and so p(x) ≤ s′ s. Consequently p(x) = s′ sp(x) and p(x) ∈ DsS . Hence
the map Sp(x) → Sx given by sp(x) 7→ sx is an S−map which is clearly onto. We have
therefore demonstrated
Proposition 2.24 Let S be an E−dense semigroup with a semilattice of idempotents E
and let X be a graded E−dense S−act. Then X is a quotient of a locally free graded S−act.
The question now arises as to when two transitive E−dense S−acts are isomorphic.
Lemma 2.25 Let H be a closed E−dense subsemigroup of an E−dense semigroup S with a
semilattice of idempotents E. Let (sH)ω be a left ω−coset of H so that there exists s′ ∈ W (s)
such that s′ s ∈ H. Then sHs′ ⊆ S(sH)ω .
Proof.
Let h ∈ H and consider (shs′ ) · ((sH))ω. First notice that (shs′ s)Hω is an
ω−coset as for any h′ ∈ W (h) ∩ H, s′ sh′ s′ ∈ W (shs′ s) and (s′ sh′ s′ )(shs′ s) ∈ H. So
(shs′ ) · ((sH))ω = ((shs′ s)H)ω = (sH)ω and so sHs′ ⊆ S(sH)ω .
If H and K are two closed E−dense subsemigroups of an E−dense semigroup S with
semilattice of idempotents E, then we say that H and K are conjugate if S/H ∼
= S/K (as
E−dense S−acts).
Theorem 2.26 Let H and K be closed E−dense subsemigroups of an E−dense semigroup
S with semilattice of idempotents E. Then H and K are conjugate if and only if there exist
s ∈ S, s′ ∈ W (s) such that
s′ Hs ⊆ K and sKs′ ⊆ H.
Moreover, any such element s necessarily satisfies ss′ ∈ H, s′ s ∈ K.

15

Proof.
Suppose that H and K are conjugate. Then by Theorem 2.21 there is an ω−coset,
(sK)ω say, such that S(sK)ω = H. So by Lemma 2.25 there exists s′ ∈ W (s) such that
s′ s ∈ K and sKs′ ⊆ H. Hence ss′ ∈ H. In addition, for each h ∈ H, (hsK)ω = (sK)ω and
so hsπK s. Consequently s′ hs ∈ K and so s′ Hs ⊆ K as required.
Conversely suppose there exist s ∈ S, s′ ∈ W (s) such that s′ Hs ⊆ K and sKs′ ⊆ H. Then
ss′ Hss′ ⊆ sKs′ ⊆ H. If e ∈ E(H) then ss′ ess′ = ess′ = ss′ e ∈ H and since H is unitary
in S then ss′ ∈ H from which we deduce that s′ s ∈ K. Therefore (sK)ω is an ω−coset of
K in S. Now suppose that t ∈ S(sK)ω . Then ((ts)K)ω = (sK)ω and so tsπK s. Therefore
s′ ts ∈ K and so ss′ tss′ ∈ H and since H is unitary in S we deduce that t ∈ H. Conversely
if t ∈ H then s′ ts ∈ K and so sπK ts or in other words ((ts)K)ω = (sK)ω and t ∈ S(sK)ω .
Hence H = S(sK)ω . Define φ : S/H → S/K by φ((tH)ω) = (tsK)ω and notice that φ is a
well-defined morphism. To see this note that there exists t′ ∈ W (t) with t′ t ∈ H. It follows
that s′ (t′ t)s ∈ K and since s′ t′ ∈ W (ts) then ((ts)K)ω is an ω−coset. If (tH)ω = (rH)ω
then there exists r′ ∈ W (r) such that r′ r, r′ t ∈ H = S(sK)ω and so (rsK)ω = (tsK)ω.
Finally, as H = S(sK)ω then φ is injective and as S/K is transitive then φ is onto and so an
isomorphism as required.
In fact we can go a bit further
Theorem 2.27 Let H and K be closed E−dense subsemigroups of an E−dense semigroup
S. Then H and K are conjugate if and only if there is exist s ∈ S, s′ ∈ W (s)
(s′ Hs)ω = K and (sKs′ )ω = H.
Moreover, any such element s necessarily satisfies ss′ ∈ H, s′ s ∈ K.
Proof.
From Theorem 2.26, if H and K are conjugate, then there exists s ∈ S, s′ ∈ W (s)
such that
s′ Hs ⊆ K and sKs′ ⊆ H.
Now it is clear that (s′ Hs)ω ⊆ K so let k ∈ K, k ′ ∈ W (k) ∩ K and let l = skk ′ ks′ ∈ H. Now
put m = s′ ls = s′ skk ′ ks′ s ∈ s′ Hs and notice that m ≤ k and so k ∈ (s′ Hs)ω as required.
Notice that if ss′ ∈ H then s′ Hs is an E−dense subsemigroup of H. To see this note that
it is clearly a subsemigroup and that s′ h′ ss′ s ∈ W (s′ hs) ∩ s′ Hs for any h′ ∈ W (h) ∩ H. In
particular from Theorem 2.20 we immediately deduce
Proposition 2.28 Let S be an E−dense semigroup with a semilattice of idempotents E
and let X be an E−dense S−act. Let s ∈ S and x ∈ Ds . Then sSx s′ is an E−dense
subsemigroup of S for any s′ ∈ W (s) ∩ Dsx .
Theorem 2.29 Let S be an E−dense semigroup with semilattice of idempotents E and let
X be an E−dense S−act. Let s ∈ S and x ∈ Ds . Then Sx and Ssx are conjugate.
Proof.
Since Sx = Ssx the result follows from Theorem 2.22. In fact, we have that
(sSx s′ )ω = Ssx for any s′ ∈ W (s) ∩ Dsx .
If H is a closed E−dense subsemigroup of an E−dense semigroup S with semilattice of
idempotents E, then we say that H is self-conjugate if H is only conjugate to itself.
Proposition 2.30 Let H be a closed E−dense subsemigroup of an E−dense semigroup S
with semilattice of idempotents E. Then H is self-conjugate if and only if for all s ∈ S and
all s′ ∈ W (s) such that s′ s ∈ H then sHs′ ⊆ H.
16

Proof.
If s ∈ S and s′ ∈ W (s) with s′ s ∈ H then by Lemma 2.25, sHs′ ⊆ S(sH)ω . By
Theorem 2.22, S(sH)ω is conjugate to H and so since H is self-conjugate, sHs′ ⊆ H.
Conversely, suppose that K is a closed E−dense subsemigroup of S and that K is conjugate
to H. Then by Theorem 2.21 there is an ω−coset, (sH)ω say, such that S(sH)ω = K. Hence
there exists s′ ∈ W (s) such that s′ s ∈ H. If k ∈ K then sπH ks and so s′ ks ∈ H and in
addition, since s′ s ∈ H and sHs′ ⊆ H then ss′ = s(s′ s)s′ ∈ H. Hence s(s′ ks)s′ ∈ sHs′ ⊆ H
and so K ⊆ H as H is unitary in S. Since ss′ = (ss′ s)s′ and since ss′ s ∈ W (s′ ) then
s′ H(ss′ s) ⊆ H and so s′ Hs ⊆ H as H is unitary. Consequently, for all h ∈ H, sπH hs and
so H ⊆ S(sH)ω = K.
An alternative characterisation of self-conjugacy is given by
Proposition 2.31 Let H be a closed E−dense subsemigroup of an E−dense semigroup S
with semilattice of idempotents E. Then H is self-conjugate if and only if for all s, t ∈
S, st ∈ H implies ts ∈ H.
Proof.
If st ∈ H then there exists t′ ∈ W (t), s′ ∈ W (s) such that t′ s′ ∈ W (st) and
′ ′
t s st ∈ H. Hence (t′ t)(t′ s′ st) ∈ H and so t′ t ∈ H. Since tHt′ ⊆ H then tt′ ∈ H. But then
ts(tt′ ) = tstt′ tt′ = t(stt′ t)t′ ∈ tHt′ ⊆ H and so ts ∈ H as H is unitary in S.
Conversely, suppose that s ∈ S, s′ ∈ W (s) with s′ s ∈ H and let h ∈ H. Then s′ (shs′ s) =
(s′ s)h(s′ s) ∈ H and so shs′ = (shs′ s)s′ ∈ H and H is self-conjugate.
If H is self-conjugate then S/H has a richer structure. First notice that
Lemma 2.32 Let H be a self-conjugate closed E−dense subsemigroup of an E−dense semigroup S with semilattice of idempotents E. Then DH is a closed E−dense subsemigroup of
S.
Proof.
Let s, t ∈ DH and s′ ∈ W (s), t′ ∈ W (t) with s′ s, t′ t ∈ H. By Proposition 2.31
′
tt ∈ H and since tt′ t ∈ W (t′ ) then t′ Htt′ t ⊆ H. Then t′ s′ ∈ W (st) and t′ s′ st = t′ s′ stt′ t ∈
t′ Htt′ t ⊆ H so that st ∈ DH . Further, as ss′ ∈ H and as ss′ s ∈ W (s′ ) then s′ ∈ DH .
Hence DH is an E−dense subsemigroup of S. Now suppose that s ≤ r with r ∈ S so that
there exist e, f ∈ E such that s = re = f r. Hence there exists f ′ ∈ W (f ), r′ ∈ W (r) such
that s′ = r′ f ′ Consequently, r′ rs′ s = r′ rr′ f ′ f r = r′ f ′ f r = s′ s ∈ H and so r′ r ∈ H as H is
unitary in S. Hence DH is a closed E−dense subsemigroup of S.
As a consequence we can deduce the following interesting result.
Theorem 2.33 Let H be a self-conjugate closed E−dense subsemigroup of an E−dense
semigroup S with semilattice of idempotents E. Then S/H is a group under the multiplication
((sH)ω)((tH)ω) = ((st)H)ω.
Proof.
The multiplication given is well defined as if (s1 H)ω = (s2 H)ω and (t1 H)ω =
(t2 H)ω with s1 , s2 , t1 , t2 ∈ DH then there exist s′1 ∈ W (s1 ), t′1 ∈ W (t1 ) such that s′1 s2 , t′1 t2 ∈
H and so by Proposition 2.31 we have t2 t′1 ∈ H and s′1 s2 t2 t′1 ∈ H and so t′1 s′1 s2 t2 ∈ H.
Hence ((s1 t1 )H)ω = ((s2 t2 )H)ω as required. Multiplication is clearly associative and it is
easy to see that Hω is the identity. It is also clear that (s′ H)ω ∈ W ((sH)ω) and so S/H
is an E−dense monoid. Let (sH)ω ∈ E(S/H) so that s′ s2 ∈ H. Since s′ s ∈ H and H is
unitary in S then s ∈ H and so |E(S/H)| = 1. Hence by Lemma 1.6, S/H is a group.
In particular, if H is self-conjugate and DH = S then πH is a group congruence on S.

17

Proposition 2.34 Let H be a self-conjugate closed E−dense subsemigroup of an E−dense
semigroup S with semilattice of idempotents E. Then for each s ∈ DH ρs : S/H → S/H
given by ρs (X) = (sX)ω is a bijection. The map ρ : DH → Sym(S/H) given by ρ(s) = ρs
is a semigroup homomorphism with ker(ρ) = πH .
Proof.
If s, t ∈ DH then it is clear that ρst = ρs ρt and so ρ is a homomorphism.
Let X ∈ S/H so that X = (tH)ω for some t ∈ DH . If s ∈ DH then st ∈ DH and
so ρs (X) = (sX)ω = ((st)H)ω ∈ S/H. In addition there exists s′ ∈ DH ∩ W (s) and
so s′ s ∈ DH and ρs′ s (X) = ((s′ s)X)ω = ((s′ st)H)ω = (tH)ω = X. In a similar way
ρss′ (X) = ((ss′ )X)ω = X and so ρs′ is the inverse of ρs .
If (s, t) ∈ ker(ρ) then in particular ρs (Hω) = ρt (Hω) and so (s, t) ∈ πH . Conversely
if (s, t) ∈ πH then (sH)ω = (tH)ω and so since S/H is a group then for any r ∈ DH ,
(srH)ω = (trH)ω or in other words (sX)ω = (tX)ω for any X ∈ S/H. Therefore (s, t) ∈
ker(ρ).

3

Semigroup acts and the discrete log problem

Many modern cryptographic applications make implicit use of the inherent difficulty of
solving the discrete log problem. In this section we consider the problem from an abstract
perspective focussing on the (total) action of semigroups on sets (see [9] for more details of
this approach).
Let S be a semigroup and X a (total) left S−act. Suppose also that the action on X is
cancellative in the sense that for all s ∈ S and all x, y ∈ X if sx = sy then x = y. For each
s ∈ S we shall call the pair (X, s) an S−cryptosystem with encryption (function) x 7→ sx.
We refer to x as the plaintext, sx as the ciphertext and s as the cipher key. Our problem is
then to find a decrypt key t such that (ts)x = x.
If for s ∈ S, x, y ∈ X we have y = sx then we shall refer to s as the discrete log of y to the
base x. The discrete log problem is then to compute s given sx and x. In general of course,
the discrete log of sx may not be unique.
As an example, let S = Up−1 be the group of units of the ring Zp−1 and X = Up the group
of units of Zp with p a prime. For n ∈ S, x ∈ X define n · x = xn mod p. By Fermat’s
little theorem, if x is a unit modulo p, then xp−1 ≡ 1 mod p and since n is coprime to p − 1
then there is a positive integer m such that mn ≡ 1 mod p − 1 and hence xmn ≡ x mod p.
Consequently m is a decrypt key for n. The usefulness of this system lie in the fact that we
know of no efficient, non-quantum algorithms, to solve this particular discrete log problem.
More generally, we can let X be a finite group of order r and let S be the group of units
of the ring Zr . Then the action S × X → X given by (n, x) 7→ xn is the basis of an
S−cryptosystem, in which the inverse of any key n ∈ S can easily be computed using the
Euclidean algorithm. The case when r = pq with p and q being distinct primes, forms the
basis of the RSA public-key encryption system.
There are in fact a number of well-know algorithms or protocols for public key encryption
which depend on the difficulty of solving the discrete log problem. For example
Example 3.1 Massey-Omura
Let S be a commutative semigroup that acts on a set X and suppose that for each s ∈ S
there is an inverse element s−1 with the property that s−1 sx = x for all x ∈ X. Suppose
now that Alice wants to send Bob a secure message x. She chooses a secret random element
of the semigroup s, say and sends Bob the value sx. Bob also chooses a secret random
element of the semigroup t, say and sends Alice the value t(sx). Alice then computes
18

tx = (s−1 s)(tx) = s−1 (t(sx)) and sends this to Bob. Bob then computes x = t−1 (tx) as
required.
We can in fact remove the need for S to be commutative if we assume that X is an
(S, S)−biact. In this case, Alice sends Bob the value sx and Bob sends Alice the value
(sx)t = s(xt). Alice then computes xt = (s−1 s)(xt) = s−1 (s(xt)) and Bob then proceeds as
normal.
The beauty of such a scheme is that the values of s and t are chosen at random, do not need
to be exchanged in advance and do not need to be re-used.
Example 3.2 Generalised ElGamal encryption.
In this system, we again assume that S is a (not necessarily commutative) semigroup that
acts on a set X and that a shared secret key, s ∈ S, has previously (or concurrently)
been exchanged. Alice chooses a secret random value c ∈ S, while Bob chooses a secret
random value d ∈ S and publishes sd as his public key. Alice then sends the pair of values
((c(sd))x, cs) to Bob, who computes (cs)d = c(sd) and hence (c(sd))−1 and so recovers x.
Again the values c and d do not have to be re-used.
It is clear that if S is a group, the inverse element s−1 will always exist, namely the group
inverse. For semigroups in general however this may not always be the case. We require
that the stabilizers Sx be left dense in S in order to guarantee that the inverse key will exist
for all s ∈ S.
Proposition 3.3 Let S be a semigroup and X an S−act. The following are equivalent;
1. for all x ∈ X, Sx is left dense in S,
2. for all x ∈ X, Sx is a transitive S−act and x ∈ Sx,
3. every locally cyclic S−subact of X is transitive and for all x ∈ X, x ∈ Sx.
Proof.
(1) =⇒ (2). For all s, r ∈ S there exists t ∈ S such that tsx = x and so
(rt)sx = rx. Hence Sx is transitive and x ∈ Sx.
(2) =⇒ (3). Let Y be a locally cyclic S−subact of X and let x, y ∈ Y . Then there exists
z ∈ Y such that x, y ∈ Sz and so since Sz is transitive then there exists s ∈ S such that
y = sx as required.
(3) =⇒ (1). Let x ∈ X so that by assumption x ∈ Sx. It is clear that Sx is locally cyclic
and so transitive. Consequently, for all s ∈ S there exists t ∈ S such that t(sx) = x and Sx
is left dense in S.
We also require that X is a cancellative S−act. The following result is straightforward to
prove, but note that we only require S to be E−dense in order to justify (4) =⇒ (1).
Lemma 3.4 Let S be an E−dense semigroup and X an S−act. The following are equivalent
1. X is cancellative,
2. for all x ∈ X, E ⊆ Sx ,
3. for all x ∈ X, Eω ⊆ Sx ,
4. for all s ∈ S, s′ ∈ L(s), x ∈ X then s′ s ∈ Sx .

19

Notice from property (4) that if X is a cancellative S−act then for all x ∈ X, Sx is left dense
in S. So if S is an E−dense semigroup then all cancellative cyclic acts are automatically
transitive. So the question arises as to how we can construct a cancellative S−act over an
E−dense semigroup. We do know the structure of E−dense transitive acts over E−dense
semigroups and these are automatically cancellative. In fact it is then clear that if S is
E−dense, then a total S−act X is cancellative if and only if it is an E−dense S−act in
which for each s ∈ S, Ds = X.
Let S be an E−dense semigroup, let (X, s) be an S−cryptosystem and let s′ , s′′ ∈ L(s).
Then for any x ∈ X we see that
s′ x = (s′′ s)(s′ x) = s′′ (ss′ x) = s′′ x.
As with E−dense S−acts we have
Lemma 3.5 Let S be an E−dense semigroup and let X be a cancellative S−act. Then for
all x ∈ X, Sx is ω−closed.
If K(s, x) = {t ∈ S|ts ∈ Sx }, the decrypt key space, then we know that W (s) ⊆ L(s) ⊆
K(s, x).
Theorem 3.6 Let S be an E−dense semigroup, let (X, s) be an S−cryptosystem and let
x ∈ X. Then
1. K(s, x) is ωM −closed,
2. (Sx W (s)Ssx ) ωM ⊆ K(s, x),
3. If E is a band then (Sx W (s)Ssx ) ω = K(s, x),

4. If S is an inverse semigroup then K(s, x) = Sx s−1 ω.
Proof.

Let S, s and x be as in the statement of the theorem.

1. If t ∈ K(s, x) and if t ≤M r then there exist a, b ∈ S such that t = ar = rb, at = tb = t.
Hence if b′ ∈ W (b) then rsx = r(bb′ sx) = tb′ sx = tbb′ sx = tsx = x and so r ∈ K(s, x).
2. Let t ∈ Sx , s′ ∈ W (s) and let r ∈ Ssx . Then (ts′ r)(sx) = ts′ sx = tx = x and so
ts′ r ∈ K(s, x) and the result then follows by part (1).
3. Let t ∈ K(s, x) and notice that for any s′ ∈ W (s) and any t′ ∈ W (t) it follows that
tss′ t′ t ∈ Sx W (s)Ssx . But ss′ t′ t ∈ E since E is a band and tss′ t′ ∈ E since S is weakly
self-conjugate. Hence tss′ t′ t ≤ t and so K(s, x) ⊆ (Sx W (s)Ssx )ω.
4. If t ∈ Sx then ts−1 = ts−1 ss−1 ∈ Sx L(s)Ssx and so (Sx s−1 )ω ⊆ K(s, x). Conversely,
let t ∈ K(s, x) so that tsx = x. Then tss−1 ∈ Sx s−1 and since tss−1 ≤ t the result
follows.

In particular, if S is a group then K(s, x) = Sx s−1 and so |K(s, x)| = |Sx |. A group S is
said to act freely on a set X if for all x ∈ X, Sx = {1}. Clearly in this case, for each key s
there is then a unique decrypt key s−1 . However if the action is not free then there will be
more than one decrypt key for at least one s ∈ S. Notice that for the classic discrete log
cipher Up−1 × Up → Up , (n, x) 7→ xn , the action is indeed a free action. Notice also that for
any E−dense semigroup S and for all x ∈ X, Eω ⊆ Sx . As with E−dense acts, we shall
say that a cancellative S−act X is locally free if for all x ∈ X, Sx = Eω. This is a different
definition from the usual concept of freeness in S−acts (see [8]).
20

Example 3.7 Let S be an E−dense semigroup with a band of idempotents E and let I be
a left ideal of S. Then I is a locally free S−act.
To see this suppose that s ∈ S, x ∈ I and that sx = x. Then for x′ ∈ W (x), s′ ∈ W (s)
it follows that sxx′ s′ s = xx′ s′ s ∈ E since E is a band. However, sxx′ s′ s = s(xx′ s′ s) =
(sxx′ s′ )s and since xx′ s′ s, sxx′ s′ ∈ E it follows that s ≥ sxx′ s′ s so that Sx ⊆ Eω.
From the point of view of decryption, ideally we need a group acting freely on a set. However,
the point of the discrete log problem is not that it is impossible to solve, but rather that it is
hard to solve. Perhaps if finding one needle in a haystack is hard, then finding two, or at least
a relatively small number, is equally hard. Having said that, we probably wish to minimise
the size of K(s, x) and so if S is an E−dense semigroup then we may wish to consider
those semigroups for which Eω = E, which in the case of those E−dense semigroups with
a band of idempotents is, by Lemma 1.7, an E−unitary semigroup. We shall refer to such
semigroups as E−unitary dense semigroups. Notice that in this case, if X is locally free,
K(s, x) = {t|ts ∈ Sx } = {t|ts ∈ E} = L(s). Notice also that by Lemma 1.5, if |L(s)| = 1
then S is a group.
Proposition 3.8 Suppose that S is an E−unitary dense semigroup with a semilattice of
idempotents E and suppose that X is a locally free cancellative S−act. Then for all s ∈
S, x ∈ X, K(s, x) = (W (s))ω.
Proof.
By Theorem 3.6, K(s, x) = (EW (s)E)ω and by Lemma 1.4, EW (s)E ⊆ W (s).
Hence K(s, x) ⊆ (W (s))ω. But if s′ ≤ t for some s′ ∈ W (s), t ∈ S then there exist e, f ∈ E
such that s′ = et = f t. Consequently f ts = s′ s ∈ E and so ts ∈ E as S is E−unitary.
Hence (W (s))ω ⊆ L(s) = K(x, s) and the result follows.
There have been many results concerning the structure of E−unitary dense semigroups
based on the celebrated results of McAlister ([10], [11]) and we present here a version of
the one first given in [3]. First notice that if S is a semigroup and if 1 S is the monoid
obtained from S by adjoining an identity element 1 (regardless of whether S already has
an identity), then S is an E−unitary dense semigroup if and only if 1 S is an 1 E−unitary
dense monoid. This observation allows us to present the construction for E−unitary dense
monoids, without much loss of generality. We use, for the most part, the terminology of [5].
Let C be a small category, considered as an algebraic object, with a set of objects, Obj C and
a disjoint collection of sets, Mor(u, v) of morphisms, for each pair of objects u, v ∈ Obj C.
The collection of all morphisms of C is denoted by Mor C, for each object u ∈ Obj C
the identity morphism is denoted by 0u and composition of morphisms, denoted by p + q
for p, q ∈ Mor C, is considered as a partial operation on Mor C. Notice that, despite the
notation, we do not assume that + is commutative. For each object u ∈ Obj C the set
Mor(u, u) is a monoid under composition and is called the local monoid of C at u. We shall
say that C is locally idempotent if each local monoid Mor(u, u) is a band, and that C is
strongly connected if for every u, v ∈ Obj C, Mor(u, v) 6= Ø.
Let G be a group. An action of the group G on a category C, is given by a group action on
Obj C and Mor C such that
1. if p ∈ Mor(u, v) then gp ∈ Mor(gu, gv),
2. g(p + q) = gp + gq for all g ∈ G, p, q ∈ Mor C, (whenever both sides are defined),
3. g0u = 0gu for all g ∈ G, u ∈ Obj C.

21

The action is said to be transitive if for all objects u, v ∈ Obj C there exists g ∈ G, gu = v,
and free if the action on the objects if a free action (i.e. Su = {1} for all u ∈ Obj C). Notice
that if the action is both transitive and free then for each pair u, v ∈ Obj C there exists a
unique g ∈ G with gu = v.
Now suppose that C is a strongly connected, locally idempotent category and that the group
G acts transitively and freely on C. Let u ∈ Obj C and let
Cu = {(p, g)|g ∈ G, p ∈ Mor(u, gu)}.
Then Cu is a monoid with multiplication defined by
(p, g)(q, h) = (p + gq, gh).
Theorem 3.9 ([3, Proposition 3.2, Theorem 3.4]) Let S be a monoid with band of
idempotents E. Then S is E−unitary dense if and only if there exists a strongly connected,
locally idempotent category C and a group G that acts transitively and freely on C and S is
isomorphic to Cu for some (any) u ∈ Obj C.
Notice that the idempotents of S correspond to the elements of the form (p, 1). Also,
as K(s, x) = L(s), we see that K((p, g), x) = {(q, g −1 ) ∈ S} and so |K((p, g), x)| =
|Mor(u, g −1 u)|. Consequently we see by Lemma 1.5 that S is a group if and only if for
all g ∈ G, |Mor(u, gu)| = 1. In fact we see from Lemma 1.6 that in order for G not to be a
group we require |E| > 1 (this would not be true if S is not a monoid).
Define the support of the category C to be the underlying graph of C. Now consider the
following category. Let Obj C = S and for u, v ∈ Obj C define Mor(u, v) = {(u, s, v)|s ∈
S, v = su}. This is called the derived category of the monoid S. The support of C is often
called the left Cayley graph of S.
For a specific example of the above construction of an E−unitary dense monoid, let G be a
group and let C be the derived category of G with the induced action of G on C. That is
to say g(u, s, v) = (gu, gsg −1, gv). Then Cu is an E−unitary dense monoid, C is a locally
idempotent category on which G acts transitively and freely and Cu ∼
= G. Notice that
= C1 ∼
in this case every morphism in C is an isomorphism and so C is a groupoid.
01
1

(h, h−1 , 1)

0h

h

(1, h, h)

(g, g −1 , 1)

(1, g, g)

g

0g

If we wish to work with E−unitary dense semigroups rather than monoids, we can simply
remove the need for an identity element in Mor(u, u) (see [3] for more details).
A simple modification of the previous example can provide us with an E−unitary dense
semigroup that is not a group. Let G be a group and in the derived category of G, replace
Mor(u, u) = {0u } with the 2-element band {0u , eu }. Now extend the composition of maps
so that we form a category. In other words for each u ∈ Obj C, g ∈ G add in the maps
eu + (u, g, gu), (u, g, gu) + egu , eu + (u, g, gu) + egu . In addition we can extend the action of
G accordingly so that geu = egu .
22

01
(1, h, h)

eh

e1
1

(1, g, g)

(h, h−1 , 1)(g, g −1 , 1)

h

g
0g

0h

eg

Notice then that (u, g, gu)+egu +(gu, g −1, u) ∈ Mor(u, u) and so must be either equal to 0u or
eu . If it were equal to 0u then we can add (gu, g −1 , u) to the left and (u, g, gu) to the right to
deduce that eu = 0u which is obviously a contradiction. Hence (u, g, gu)+egu +(gu, g −1, u) =
eu and so for all u ∈ Obj C, g ∈ G we have
(u, g, gu) + egu = eu + (u, g, gu).
It then follows that Mor(u, gu) = {(u, g, gu), eu + (u, g, gu)} and C1 is an E−unitary dense
monoid with 2 idempotents and |K(s, x)| = 2 for all s ∈ S and x ∈ X. Notice that we can
view this monoid in the following way. Let G be a group and e a symbol not in G and let
eG = {eg|g ∈ G} be a set in 1-1 correspondence with G. Let S = G ∪˙ eG and extend the
multiplication on G to S by setting e2 = e, eg = ge for all g ∈ G and all other products
defined by associativity or the multiplication in G. Then S ∼
= C1 and the isomorphism
is given by g 7→ ((1, g, g), g), eg 7→ (e1 + (1, g, g), g) = (e1 , 1)((1, g, g), g). The element e
corresponds to (e1 , 1) ∈ C1 .
By replacing Mor(u, u) by a band of any given size, we should be able to construct an
E−unitary dense monoid with any finite number of idempotents.
The above construction gives us a mechanism to build a suitable E−unitary dense semigroup
S. However we need X to be a locally free cancellative S−act, so let us revisit the theory
of E−dense S−acts. If S is finite (or at least E is finite) and E is a semilattice, then every
E−dense actṠis graded and so by Theorem 2.23, X is a locally free E−dense S−act if and
only if X ∼
= Sei for some idempotents ei , where the action is that given in Example 2.2.
As previously observed, if X is a cancellative total act then it is automatically reflexive and
hence an E−dense act. Consequently, if X is locally free then as every idempotent acts on
ei , we can deduce that for each i, ei = f , the minimum idempotent in S. Conversely if f is
the minimum idempotent in S then Sf ∼
= S/f ω is a locally free transitive cancellative total
S−act. We have therefore shown
Theorem 3.10 Let S be a finite E−dense semigroup with semilattice of idempotents E,
let s ∈ S and let f be the minimum idempotent in S. Then (X, s) is a locally free
Ṡ
S−cryptosystem if and only if X ∼
= Sf . In addition, if S is E−unitary then for each
x ∈ X, |K(s, x)| = |(W (s))ω|.
In the above example where S = G ∪˙ eG, the minimum idempotent is e and X = eG = Ge
is a locally free cancellative S−act and for each x ∈ X, |K(s, x)| = 2. In the classic discrete
log cipher, Up−1 acts freely on Up by exponentiation, the minimm idempotent is 1 ∈ Up−1
Ṡ
and in fact Up ∼
= |Up | Up−1 .

23

3.1

Completely Regular Semigroups

In the classic discrete log cipher, a group acts freely on a group by exponentiation. We now
briefly consider a group acting freely on a semigroup by exponentiation. It is clear that the
semigroup needs to be periodic as every element will need to have finite order.
A semigroup S is called completely regular if every element of S belongs to a subgroup of S.
A particular example of such a semigroup is a completely simple semigroup, which by Rees’
Theorem ([7, Theorem 3.2.3]), can be shown to be isomorphic to a Rees Matrix Semigroup.
Indeed a semigroup is completely regular if and only if it is isomorphic to a semilattice
of completely simple semigoups ([7, Theorem 4.1.3]). A semigroup S = M[G; I, Λ; P ] is a
called a Rees Matrix Semigroup if
S =I ×G×Λ
and P = (pλi ) is a Λ × I matrix with entries in the group G, and where multiplication is
given by
(i, g, λ)(j, h, µ) = (i, gpλj h, µ).
If follows that for n ∈ N, (i, g, λ)n = (i, (gpλi )n−1 g, λ). Notice that S is not in general
commutative, even if G is abelian.
Suppose now that S is a completely simple semigroup, considered as a Rees matrix semigroup
M[G; I, Λ; P ] and suppose also that G is finite, of order r so that g r = 1 for all g ∈ G. Define
an action of Ur , the group of units in Zr , on S by n · x = xn , so that if x = (i, g, λ) then
n · x = (i, (gpλi )n−1 g, λ). This action is clearly a free action and group actions are always
cancellative.
Suppose now that n is coprime to r and that mn ≡ 1 mod r. Then
−1
xmn = (i, (gpλi )mn−1 g, λ) = (i, (gpλi )mn p−1
λi , λ) = (i, (gpλi )pλi , λ) = (i, g, λ) = x.

Consequently if we know n, xn and P , then we can compute xmn and so recover x. We can
in fact compute xmn in an efficient manner, as we can deduce the values of i and λ from xn
and so we can compute pλi . Then
 m
(gpλi )mn−1 g = (gpλi )mn p−1
(gpλi )n−1 g pλi p−1
λi .
λi =
Suppose now we know x, xn and G. Can we compute n? If we also know P then we know pλi
and so (gpλi )n . Consequently, the discrete log problem in this case is equivalent to that in
the classic discrete log problem. Suppose however that P is secret. We know (gpλi )n−1 g and
we know g and so we can compute (gpλi )n−1 but we don’t know pλi and so can’t obviously
recover the classic discrete log problem from this. However, according to [4], the discrete
log problem here, can be reduced, in polynomial time, to the classic discrete log problem in
a subgroup of S, namely the kernel of the element x.
An alternative strategy might be to utilise the matrix P to form a kind of “Vigenère” version
of the discrete log cipher. Here, the data to be enciphered would be encoded using the group
G alone as with the classic discrete log cipher, and an additional keyword would be used to
generate a large sequence of values (i, λ)j with the j th such pair used to encipher the j th
plaintext block using the scheme above. In principle different data blocks, even if containing
the same value, would produce different ciphertext blocks, thereby potentially increasing the
diffusion.

References
[1] A.H. Clifford and G.B. Preston, The Algebraic Theory of Semigroups II, American
Mathematical Society, Mathematical Surveys 7, AMS, 1967.
24

[2] Ahsan, Javed and Liu Zhongkui, A Homological Approach to the Theory of Monoids,
Science Press, Beijing, (2008).
[3] J. Almeida, J.E. Pin and P. Weil, Semigroups whose idempotents form a subsemigroup,
Math. Proc. Camb. Phil. Soc. (1992), 111241–253.
[4] Matan Banin, Boaz Tsaban, A reduction of Semigroup DLP to Classic DLP, Designs,
Codes and Cryptography, (2016), Volume 81, Issue 1, 75–82.
[5] John Fountain, Jean-Eric Pin, Pascal Weil, Covers for monoids, Journal of Algebra,
271 (2004) 529–586.
[6] Jonathon Funk and Pieter Hofstra, Topos theoretic aspects of semigroup actions, Theory
and applications of Categories, Vol 24, No. 6, 2010, pp. 117–147.
[7] J.M. Howie, Fundamentals of Semigroup Theory, London Mathematical Society Monographs, (OUP, 1995).
[8] Kilp, Mati, Knauer, Ulrich and Alexander V. Mikhalev, Monoids, Acts and Categories,
De Gruyter Expositions in Mathematics (29), (Walter de Gruyter, Berlin, New York,
2000).
[9] Maze, G., Monico, C., Rosenthal, J., Public key cryptography based on semigroup
actions, Adv. Math. Commun., 1(4), 489–507 (1996).
[10] D. B. McAlister. Groups, semilattices and inverse semigroups. I. Trans. Amer. Math.
Soc. 192 (1974) 227-244.
[11] D. B. McAlister. Groups, semilattices and inverse semigroups. II. Trans. Amer. Math.
Soc. 196 (1974) 351-370.
[12] H. Mitsch, A Natural Partial Order for Semigroups, Proceedings of the American Mathematical Society, Vol. 97, No. 3 (Jul., 1986), pp. 384-388.
[13] H. Mitsch, Subdirect Products Of E−inversive Semigroups, J. Austral. Math. Soc.
(Series A) 48 (1990), 66–78
[14] H. Mitsch, Semigroups and their natural order, Mathematica Slovaca, Vol 44 (1994),
No 4, 445-462.
[15] H. Mitsch, Introduction to E−inversive semigroups, in “Proceedings of the International
Conference on Semigroups. Ed. Paula Smith, Emilia Giraldes, Paula Martins, World
Scientific, 1999, 114–135.
[16] J. Renshaw, Inverse semigroups acting on graphs in “Proceedings of the Workshop Semigroups and Languages. Ed. Isabel M. Araújo, Mário J.J. Branco, Vitor H. Fernandes,
Graconda M.S. Gomes, World Scientific, 2004, 212–239.
[17] S. Reither, Die nat urliche Ordnung auf Halbgruppen, University of Vienna, PhD-Thesis
(1994).
[18] Benjamin Steinberg, A note on amalgams of inverse semigroups Journal of the Australian Mathematical Society (2001), 70: 71-75.
[19] G. Thierrin, Demigroupes inversés et rectangularies, Bull. Cl. Sci. Acad. Roy. Belgique,
(1955) 41, 83–92.

25

[20] B. Weipoltshammer, On classes of E−inversive semigroups and semigroups whose idempotents form a subsemigroup, Comunications in Algebra, Vol 32, No 8, pp. 2929–2948
(2004).

26

