Profinite semigroups and applications in
Computer Science
Jorge Almeida
Departamento Matem´atica, CMUP
Faculdade de Ciˆencias, Universidade do Porto
Porto, Portugal
http://www.fc.up.pt/cmup/jalmeida/
October, 2011
´Ustav matematiky a statistiky
Pˇr´ırodovˇedeck´a fakulta
Masarykova univerzita
1 / 245
Abstract
Finite semigroups appear naturally in Computer Science, namely as syntactic semigroups of regular
languages, transition semigroups of finite automata, or as finite recognizing devices on their own.
Eilenberg’s correspondence theorem gives a general framework for the classification of regular
languages through algebraic properties of their syntactic semigroups. Here is the resulting typical
problem on the algebraic side: a recursively enumerable set R of finite semigroups is given and one
wishes to decide whether a given finite semigroup is a homomorphic image of a subsemigroup of a
finite product of members of R. Since such a problem is often undecidable, special techniques have
been devised to handle special cases. Relatively free profinite semigroups turn out to be quite
useful in this context. They play the role of free algebras in Universal Algebra, capturing in their
algebraic-topological/metric structure combinatorial properties of the corresponding classes of
languages.
The aim of this short course is to introduce reltively free profinite semigroups and to explore two
topics in which there have been significant recent developments, namely the separation of a given
word from a given regular language by a regular language of a special type (for instance, a group
language), and connections with symbolic dynamics.
Tentative syllabus and preliminary references:
Part 1 Relatively free profinite semigroups. (1 lecture)
Reference:
[1] J. Almeida, Profinite semigroups and applications, in ”Structural Theory of Automata, Semigroups, and
Universal Algebra”, V. B. Kudryavtsev and I. G. Rosenberg (eds.), Proceedings of the NATO Advanced Study
Institute on Structural Theory of Automata, Semigroups and Universal Algebra (Montr´eal, Qu´ebec, Canada,
7-18 July 2003), Springer, New York, 2005, pp. 1-45.
Part 2 Separating words and regular languages. (2 lectures)
Reference:
[2] S. Margolis, M. Sapir, and P. Weil, Closed subgroups in pro-V topologies and the extension problem for
inverse automata, Int. J. Algebra and Comput. 11 (2001) 405-455.
Part 3 Relatively free profinite semigroups and Symbolic Dynamics. (2 lectures)
Reference:
[1] (see above).
2 / 245
Part I
Relatively free profinite semigroups
3 / 245
Outline
Language recognition devices
Eilenberg’s correspondence
Decidable pseudovarieties
Metrics associated with pseudovarieties
Pro-V semigroups
Reiterman’s Theorem
Examples of relatively free profinite semigroups
Pseudowords as operations
Implicit signatures
4 / 245
A regular language is a subset of the free monoid A∗ on an
alphabet A admitting a regular expression, i.e., a formal
expression describing it in terms of the empty set ∅ and the
letters a ∈ A using the following operations:
(K, L) → K ∪ L (union)
(K, L) → KL (concatenation)
L → L∗
(Kleene star)
The syntactic congruence of the language L ⊆ A∗ is the binary
relation σL on A∗ defined by:
u σL v if ∀ x, y ∈ A∗
(xuy ∈ L ⇔ xvy ∈ L).
The syntactic monoid M(L) of the language L ⊆ A∗ is the
quotient monoid A∗/σL.
5 / 245
Theorem 1.1
The following conditions are equivalent for a language L over a
finite alphabet A:
(1) L is regular;
(2) L is recognized by some finite automaton;
(3) L is recognized by some finite complete deterministic
automaton;
(4) the syntactic monoid A∗/σL on A∗ is finite;
(5) L is recognized by some homomorphism ϕ : A∗ → M into a
finite monoid, in the sense that L = ϕ−1ϕL.
Corollary 1.2
The set Reg(A∗) of all regular languages over the alphabet A is a
Boolean subalgebra of the Boolean algebra of all subsets of A∗.
6 / 245
Example: (restricted) Dyck languages
Regular expression: L1 = (ab)∗
Minimal (incomplete) automaton: 0 1
a
bTransition monoid (M(L1)):
0 1
a 1 b
- 0
ab 0 ba
- 1
0 - a
b ab ba 0
a 0 ab 0 a 0
b ba 0 b 0 0
ab a 0 ab 0 0
ba 0 b 0 ba 0
0 0 0 0 0 0
Presentation: a, b; aba = a, bab = b, a2
= b2
= 0 .
One may then compute Green’s relations, which are summarized
in the following eggbox picture:
• same row: elements generate the same right ideal (R)
• same column: elements generate the same left ideal (L)
• elements above are factors of elements below (≥J )
• ∗
e marks an idempotent (e2
= e)
• the“eggboxes”are the J -classes (J = ≥J ∩ ≤J )
• D = R ◦ L = L ◦ R
• in a finite monoid, D = J
*0
a *ab
*ba b
*1
7 / 245
Regular expression: L2 = (a(ab)∗
b)∗
Minimal (incomplete) automaton: 0 1 2
a
b
a
b
Presentation of syntactic monoid M(L2):
a, b; aba = a, bab = b, a2
b2
a2
= a2
, b2
a2
b2
= b2
,
ab2
a = ba2
b, a3
= b3
= 0
Eggbox picture:
*0
aa aab *aabb
baa *abba abb
*bbaa bba bb
a *ab
*ba b
*1
8 / 245
Dyck language: L∞ = n≥0 Ln, where L0 = {1},
Ln+1 = (aLnb)∗.
Recognition by infinite automaton:
0 1 2 · · · n n + 1 · · ·
a
b
a
b
a
b
a
b
a
b
a
b
Syntactic monoid: M(L∞) = a, b; ab = 1 .
Eggbox picture:
∗
1 a a2
· · · an
an+1
· · ·
b ∗
ba ba2
· · · ban
ban+1
· · ·
b2
b2
a ∗
b2
a2
· · · b2
an
b2
an+1
· · ·
...
...
...
...
...
...
bn
bn
a bn
a2
· · · ∗
bn
an
bn
an+1
· · ·
bn+1
bn+1
a bn+1
a2
· · · bn+1
an ∗
bn+1
an+1
· · ·
...
...
...
...
...
...
9 / 245
Exercise 1.3
Consider the transition semigroup S of the following infinite automaton:
2 4
c
ÐÐ
6
c
ÐÐ
8
c
ÐÐ
· · ·
c
~~
1
a
yy
b GG 3
a
yy
b GG 5
a
yy
b GG 7
a
yy
b GG · · ·
1. Note that, in S, aca is a factor of a but a is not regular.
2. Verify that S admits the following presentation:
a, b, c; baca = a, bacb = b2
ac = b, cbac = c,
a2
= ab = bc = c2
= 0 .
3. Show that S has two J -classes, one of which is reduced to zero.
4. Show that the non-trivial J -class of S consists of two infinite
D-classes, one of which is regular and a bicyclic monoid, while the
other is not regular and has only one L-class. All H-classes of S are
trivial.
10 / 245
Outline
Language recognition devices
Eilenberg’s correspondence
Decidable pseudovarieties
Metrics associated with pseudovarieties
Pro-V semigroups
Reiterman’s Theorem
Examples of relatively free profinite semigroups
Pseudowords as operations
Implicit signatures
11 / 245
A variety of languages is a correspondence V associating with
each finitely generated free monoid A∗ a set V(A∗) of
languages over the finite alphabet A such that the following
conditions hold:
1. V(A∗
) is a Boolean subalgebra of Reg(A∗
);
2. if L ∈ V(A∗
) and a ∈ A, then the following languages also
belong to V(A∗
):
a−1
L = {w ∈ A∗
: aw ∈ L}
La−1
= {w ∈ A∗
: wa ∈ L};
3. if ϕ : A∗
→ B∗
is a homomorphism and L ∈ V(B∗
), then
ϕ−1
(L) ∈ V(A∗
).
A pseudovariety of monoids is a nonempty class V of finite
monoids which is closed under taking homomorphic images,
submonoids, and finite direct products.
12 / 245
Theorem 2.1 (Eilenberg [Eil76])
The complete lattices of varieties of languages and of
pseudovarieties of monoids are isomorphic. More precisely, the
following correspondences are mutually inverse isomorphisms
between the two lattices:
to a variety V of languages, associate the pseudovariety V
generated by all syntactic monoids M(L) with L ∈ V(A∗) for
some finite alphabet A;
to a pseudovariety V, associate the variety of languages V
such that, for each finite alphabet A, V(A∗) consists of the
languages L ⊆ A∗ such that M(L) ∈ V.
13 / 245
Thus, problems about varieties of languages admit a
translation into problems about pseudovarieties of monoids.
For instance, to determine if a language L ⊆ A∗ belongs to
smallest variety of languages containing two given varieties of
languages V and W is equivalent to determine if M(L)
belongs to the pseudovariety join V ∨ W.
Typically, we are given a recursively enumerable set R of finite
monoids and we want to determine an algorithm to decide
whether a given finite monoid M belongs to the pseudovariety
V(R) generated by R.
14 / 245
Mutatis mutandis, we have
languages L ⊆ A+ without the empty word 1;
syntactic congruence σL of L over A+:
u σL v if ∀ x, y ∈ A∗
(xuy ∈ L ⇔ xvy ∈ L).
syntactic semigroup A+/σL;
varieties of languages without the empty word;
pseudovarieties of semigroups;
Eilenberg’s correspondence in this setting.
15 / 245
Examples of pseudovarieties:
S: all finite semigroups
I: all singleton (trivial)
semigroups
G: all finite groups
Gp: all finite p-groups
A: all finite aperiodic
semigroups
Com: all finite
commutative
semigroups
J: all finite J -trivial
semigroups
R: all finite R-trivial
semigroups
L: all finite L-trivial
semigroups
Sl: all finite semilattices
RZ: all finite right-zero
semigroups
B: all finite bands
N: all finite nilpotent
semigroups
K: all finite semigroups in
which idempotents are left
zeros
D: all finite semigroups in
which idempotents are right
zeros
16 / 245
Important examples of instances of
Eilenberg’s correspondence
A language L ⊆ A+ is said to be star free if it admits an
expression in terms of the languages {a} (a ∈ A) using only
the operations: ∪ , A+ \ , and concatenation.
Theorem 2.2 ([Sch65])
A language over a finite alphabet is star free if and only if its
syntactic semigroup is finite and aperiodic.
17 / 245
A language L ⊆ A∗ is piecewise testable if it is a Boolean
combination of languages of the form A∗a1A∗a2A∗ · · · anA∗,
with the ai ∈ A.
Theorem 2.3 ([Sim75])
A language over a finite alphabet is piecewise testable if and only if
its syntactic semigroup is finite and J -trivial.
A language L ⊆ A∗ is locally testable if it is a Boolean
combination of languages of the forms A∗u, A∗vA∗, and wA∗,
where u, v, w ∈ A+.
Theorem 2.4 ([BS73, MP71])
A language L over a finite alphabet is locally testable if and only if
its syntactic semigroup S is finite and a local semilattice (i.e.,
eSe is a semilattice for every idempotent e ∈ S).
18 / 245
Outline
Language recognition devices
Eilenberg’s correspondence
Decidable pseudovarieties
Metrics associated with pseudovarieties
Pro-V semigroups
Reiterman’s Theorem
Examples of relatively free profinite semigroups
Pseudowords as operations
Implicit signatures
19 / 245
Definition 3.1
We say that a pseudovariety V is decidable if there is an algorithm
which, given a finite semigroup S as input, produces as output, in
finite time, YES or NO according to whether or not S ∈ V.
The semigroup S may be given in various ways:
extensively, meaning the complete list of its elements together
with its multiplication table;
as the transformation semigroup on a finite set Q
generated by a finite set A of transformations of Q ;
→ transition semigroup of a finite automaton (Q, A, δ, I, F);
by means of a presentation.
Different ways of describing S may lead to different
complexity results, when such an algorithm exists.
20 / 245
Of course, not all pseudovarieties are decidable.
For instance, if P is a non-recursive set of primes, then the
pseudovariety AbP, generated by all groups Z/pZ with p ∈ P,
contains a group Z/qZ of prime order q if and only if q ∈ P.
Since there are non-recursive sets of primes P, there are
pseudovarieties of the form AbP which are not decidable.
Question 3.2 (Very imprecise!!)
Are all“natural”pseudovarieties decidable?
21 / 245
There are many ways to construct new pseudovarieties from known
ones, that is by applying operators to pseudovarieties.
We proceed to introduce some natural operators.
Definition 3.3
Given a pseudovariety V, consider the classes of all finite
semigroups S such that, respectively:
LV: eSe ∈ V for every idempotent e ∈ S;
EV: E(S) ∈ V, where E(S) is the subsemigroup
generated by the set E(S) of all idempotents of S;
DV: the regular J -classes of S (are subsemigroups which)
belong to V;
V: the subgroups of S belong to V;
22 / 245
Let S be a finite semigroup and let D be one of its regular
D-classes.
Let ∼ be the equivalence relation on the set of group
elements of D generated by the identification of elements
which are either R or L-equivalent.
A block of D is the Rees quotient of the subsemigroup of S
generated by a ∼-class modulo the ideal consisting of the
elements which do not lie in D.
*
*
*
*
* *
*
*
*
*
*
*
* *
*
*
1 2 3 4 5 6
*
* * *
*
*
* *
1 3 6 2 4 5
The blocks of S are the blocks of its regular D-classes.
Definition 3.4
For a pseudovariety V, let BV be the class of all finite semigroups
whose blocks lie in V.
23 / 245
Proposition 3.5
For a pseudovariety V, the classes BV, DV, EV, LV, V are
pseudovarieties.
Moreover, if V is decidable then so are those pseudovarieties.
Proof.
We consider only the case of LV, leaving all other cases as exercises.
If ϕ : S → T is an onto homomorphism, with S ∈ S, and f ∈ E(T), then
∃e ∈ ϕ−1
(f ) ∩ E(S) and ϕ|eSe : eSe → fTf is an onto homomorphism
∴ LV is closed under taking homomorphic images.
If S ≤ T and e ∈ E(S), then eSe ≤ eTe
∴ LV is closed under taking subsemigroups.
If S, T are semigroups, e ∈ E(S), and f ∈ E(T), then
(e, f )(S × T)(e, f ) eSe × fTf
∴ LV is closed under taking finite direct products.
Given a finite semigroup, one can compute its set of idempotents E(S) and, for
each e ∈ E(S), the monoid eSe.
Provided V is decidable, one can then effectively check whether eSe ∈ V.
Hence one can effectively check whether S ∈ LV.
24 / 245
But, the most interesting operators are defined not in structural
terms but rather by describing generators: the resulting
pseudovariety is given as the smallest pseudovariety containing
certain semigroups which are constructed from those in the
argument pseudovarieties.
Definition 3.6
We say that a semigroup S divides a semigroup T, or that S is a
divisor of T, and we write S T, if S is a homomorphic image of
a subsemigroup of T.
Proposition 3.7
Let C be a class of finite semigroups. Then the smallest
pseudovariety V(C) containing C consists of all divisors of products
of the form S1 × · · · × Sn with S1, . . . , Sn ∈ C.
In particular, if C is closed under finite direct product, then V(C)
consists of all divisors of elements of C.
25 / 245
Let S and T be semigroups and let ϕ : T1 → End S be a
homomorphism of monoids, with endomorphisms acting on the left.
For s ∈ S and t ∈ T1, let ts = ϕ(t)(s).
The semidirect product S ∗ϕ T is the set S × T under the
multiplication
(s1, t1) · (s2, t2) = (s1
t1
s2, t1t2).
Definition 3.8
The semidirect product V ∗ W of the pseudovarieties V and W is
the smallest pseudovariety containing all semidirect products S ∗ T
with S ∈ V and T ∈ W.
Proposition 3.9
The pseudovariety V ∗ W consists of all divisors of semidirect
products of the form S ∗ T with S ∈ V and T ∈ W.
Proposition 3.10
The semidirect product of pseudovarieties is associative.
26 / 245
Definition 3.11
The Mal’cev product V m W of two pseudovarieties V and W is
the smallest pseudovariety containing all finite semigroups S for
which there exists a homomorphism ϕ : S → T such that T ∈ W
and ϕ−1(e) ∈ V for all e ∈ E(T).
Given two semigroups S and T, a relational morphism S → T is a
relation µ : S → T with domain S such that µ is a subsemigroup
of S × T.
Proposition 3.12
The pseudovariety V m W consists of all finite semigroups S such
that there is a relational morphism µ : S → T such that T ∈ W
and µ−1(e) ∈ V for all e ∈ E(T).
27 / 245
For a semigroup S, denote by P(S) the semigroup of subsets of S
under the product operation
X · Y = {xy : x ∈ X, y ∈ Y }.
Note that the empty set ∅ is a zero and P (S) = P(S) \ {∅} is a
subsemigroup.
Definition 3.13
For a pseudovariety V, denote by
PV: the pseudovariety generated by all semigroups of the
form P(S), with S ∈ V;
P V: the pseudovariety generated by all semigroups of the
form P (S), with S ∈ V.
Proposition 3.14
The pseudovariety PV consists of all divisors of semigroups of the
form P(S) with S ∈ V.
Similar statement for P .
28 / 245
Some examples of results on finite semigroups formulated in terms
of these operators:
1. J = N m Sl
2. DA = LI m Sl, DS = LG m Sl
3. R = Sl ∗ J [Sti73]
4. G ∨ Com = ZE (the pseudovariety of all finite semigroups in
which idempotents are central) [Alm95]
5. ESl = Sl ∗ G = Sl m G = Inv (the pseudovariety generated by
all finite inverse semigroups) [MP87, Ash87, Pin95],
ER = R ∗ G [Eil76], EDS = DS ∗ G [AE03]
6. PG = J ∗ G = J m G = EJ = BG
[MP84, HR91, Ash91, HMPR91, Pin95],
PJ = PV(Y ) [PS85, Alm95] where Y = Synt(a∗bc∗)
7. S = n≥0(A ∗ G)n ∗ A [KR65]
29 / 245
S =
n≥0
(A ∗ G)n
∗ A
The (Krohn-Rhodes) hierarchy (A ∗ G)n ∗ A
n≥0
is strict.
The smallest n such that a given finite semigroup S belongs to
(A ∗ G)n ∗ A is called the complexity of S, denoted c(S).
Let Tn denote the full transformation semigroup of an n-element
set It is known that c(Tn) = n − 1 [Eil76] and so certainly
c(S) ≤ |S| (since S → TS1 ).
Note 3.15
To know an algorithm to compute the complexity function is
equivalent to know algorithms to decide the membership problem
for each pseudovariety in the Krohn-Rhodes hierarchy.
30 / 245
This brings us to the following basic question:
Question 3.16
For the operators which were defined above in terms of generators,
do they preserve decidability?
Theorem 3.17 (Albert, Baldinger & Rhodes’1992
[ABR92])
There exists a finite set Σ of identities such that Com ∨ [[Σ]] is
undecidable.
Let C2,1 = a; a2 = 0 1.
Theorem 3.18 (Auinger & Steinberg’2003 [AS03])
There exists a decidable pseudovariety of groups U such that the
following pseudovarieties are all undecidable:
Sl ∗ U (= Sl m U), V(C2,1) ∨ U, PU (= P U).
31 / 245
The pseudovariety U is defined to be
U =
p∈A
Gp ∗ (Gf (p) ∩ Com) ∨
p∈D
(Gp ∩ Com)
where:
A and B constitute a computable partition of the set of
primes into two infinite sets;
f : A → B is an injective recursive function whose range
C = f (A) is recursively enumerable but not recursive;
D = B \ C is not recursively enumerable.
Exercise 3.19
Show that U is decidable.
32 / 245
Outline
Language recognition devices
Eilenberg’s correspondence
Decidable pseudovarieties
Metrics associated with pseudovarieties
Pro-V semigroups
Reiterman’s Theorem
Examples of relatively free profinite semigroups
Pseudowords as operations
Implicit signatures
33 / 245
Let V be a pseudovariety of semigroups.
For two words u, v ∈ A+, and T ∈ V, let
T |= u = v if, for every homomorphism ϕ : A+ → T, ϕ(u) = ϕ(v),
rV(u, v) = min{|S| : S ∈ V and S |= u = v},
dV(u, v) = 2−rV(u,v)
where we take min ∅ = ∞ and 2−∞ = 0.
Note 4.1
The following hold for u, v, w, t ∈ A+ and a positive integer n:
(1) rV(u, v) ≥ n if and only if, for every S ∈ V with |S| < n,
S |= u = v;
(2) dV(u, v) ≤ 2−n
if and only if, for every S ∈ V with |S| < n,
S |= u = v;
(3) dV(u, v) = 0 if and only if, for every S ∈ V, S |= u = v;
(4) min{rV(u, v), rV(v, w)} ≤ rV(u, w);
(5) min{rV(u, v), rV(w, z)} ≤ rV(uw, vz).
34 / 245
Definition 4.2
A function d : X × X → R≥0 is said to be a pseudo-ultrametric on
the set X if the following properties hold for all u, v, w ∈ X:
1. d(u, u) = 0;
2. d(u, v) = d(v, u);
3. d(u, w) ≤ max{d(u, v), d(v, w)}.
We then also say that X is a pseudo-ultrametric space.
If instead of Condition 3, the following weaker condition holds
4. d(u, w) ≤ d(u, v) + d(v, w) (triangle inequality).
then d is said to be a pseudo-metric on X, and X is said to be a
pseudo-metric space. If the following condition holds
5. d(u, v) = 0 if and only if u = v,
then we drop the prefix“pseudo”.
35 / 245
A function f : X → Y between two pseudo-metric spaces is said to
be uniformly continuous if the following condition holds:
∀ > 0 ∃ δ > 0 ∀ x1, x2 ∈ X d(x1, x2) < δ ⇒ d(f (u), f (v)) < .
Proposition 4.3
1. The function dV is a pseudo-ultrametric on A+
.
2. The multiplication is contractive:
dV(u1u2, v1v2) ≤ max{dV(u1, v1), dV(u2, v2)}.
In particular, the multiplication on A+
is uniformly continuous.
For a (pseudo-ultra)metric d, u ∈ X, and a positive real number ,
consider the open ball
B (u) = {v ∈ X : d(u, v) < }.
The point u is the center and is the radius of the ball.
A metric space that can be covered by a finite number of balls of
any given positive radius is said to be totally bounded.
36 / 245
Proposition 4.4
The metric space (A+, dV) is totally bounded.
Proof.
Let n be a positive integer such that 2−n
< . Note that, up to
isomorphism, there are only finitely many semigroups of cardinality at
most n in V. For such a semigroup Si consider all possible
homomorphisms ϕi,j : A+
→ Si , let S = i,j Si and
ϕ : A+
→ S
u → (ϕi,j (u))i,j .
Then S ∈ V and dV(u, v) < 2−n
if and only if ϕ(u) = ϕ(v).
For each s ∈ S, choose us ∈ A+
such that ϕ(us) = s.
For v ∈ A+
and s = ϕ(v), we have ϕ(v) = ϕ(us), and so v ∈ B (us).
We have thus shown that A+
= s∈S B (us).
37 / 245
A sequence (un)n in a (pseudo-ultra)metric space X is said to
be a Cauchy sequence if
∀ > 0 ∃ N m, n ≥ N ⇒ d(um, un) < .
Note that every convergent sequence is a Cauchy sequence.
The space X is complete if every Cauchy sequence in X
converges in X.
38 / 245
Theorem 4.5
Let X be a pseudo-(ultra)metric space. Then there exists a complete
metric space ˆX and a uniformly continuous function ι : X → ˆX with the
following universal property: for every uniformly continuous function
f : X → Y into a complete metric space Y , there exists a unique
uniformly continuous function ˆf : ˆX → Y such that ˆf ◦ ι = f .
X
ι GG
f
22
ˆX
ˆf

Y .
X
ι

γ
11
ˆX
ˆγ
CC Z.
ˆι
kk
In particular, if γ : X → Z is another uniformly continuous function into
another complete metric space with the above universal property then the
induced unique uniformly continuous mappings ˆι : ˆX → Z and ˆγ : Z → ˆX
are mutually inverse.
The“unique”space ˆX of Theorem 4.5 is called the Hausdorff
completion of X.
39 / 245
It may be constructed in the same way that the real numbers are
obtained by completion of the rational numbers. Here is a sketch:
(a) consider the set C ⊆ XN
of all Cauchy sequences of elements
of X;
(b) note that, for s = (un)n and t(vn)n in C, the sequence of real
numbers d(un, vn) n
is a Cauchy sequence and, therefore, it
converges; its limit is denoted d(s, t);
|d(un, vn) − d(um, vm)|
≤ |d(un, vn) − d(un, vm)| + |d(un, vm) − d(um, vm)|
≤ d(un, um) + d(vn, vm)
(c) Step (B) defines a pseudo-(ultra)metric on C;
(d) for s = (un)n and t(vn)n in C, let s ∼ t if d(s, t) = 0; this is
an equivalence relation on C; the class of s is denoted s/∼;
(e) let ˆX = C/∼ and put d(s/∼, t/∼) = d(s, t), which can be
easily checked to be defined;
(f) finally, let ι : X → ˆX map each u ∈ X to the ∼-class of the
constant sequence (u)n, and check that this mapping is
uniformly continuous and has the appropriate universal
property.
40 / 245
Note that ι(X) is dense in ˆX.
In particular, we may consider the Hausdorff completion of the
pseudo-ultrametric space (A+, dV), which is denoted ΩAV.
Since the multiplication of A+ is uniformly continuous with
respect to dV, it induces a uniformly continuous multiplication
in ΩAV:
A+ × A+ µ
(mult.)
GG
ι×ι

A+
ι

ΩAV × ΩAV
ˆµ
GG ΩAV
41 / 245
We endow each finite semigroup S with the discrete metric:
d(s, t) =
0 if s = t
1 otherwise
Since ι(A+) is dense in ΩAV, multiplication in ΩAV is
associative, and thus ΩAV is naturally a semigroup.
From hereon, we write d for dV. The context should leave
clear which pseudovariety is involved.
42 / 245
Note that, for S ∈ V, every homomorphism ϕ : A+ → S is
uniformly continuous with respect to d.
d(u, v) < 2−|S|
⇒ d(ϕ(u), ϕ(v)) = 0.
Thus, ϕ induces a unique uniformly continuous mapping
ˆϕ : ΩAV → S such that the following diagram commutes:
A+ ι GG
ϕ
44
ΩAV
ˆϕ

S.
One can easily check that ˆϕ is a homomorphism:
ˆϕ(uv) = lim ϕ(ι(unvn)) = lim ϕ(ι(un))ϕ(ι(vn))
= lim ϕ(ι(un)) · lim ϕ(ι(vn)) = ˆϕ(u) ˆϕ(v).
43 / 245
Given u, v ∈ ΩAV and S ∈ V, we write S |= u = v if, for every
homomorphism ϕ : A+
→ S (which is determined by ϕ|A), the
equality ˆϕ(u) = ˆϕ(v) holds.
We call the formal equality u = v a V-pseudoidentity.
Note that, if u = lim un, v = lim vn, and S ∈ V, then S |= u = v if
and only if S |= un = vn for all sufficiently large n.
Given distinct elements u, v ∈ ΩAV, there exists a positive integer
m such that d(u, v) ≥ 2−m
.
Consider sequences of words (un)n and (vn)n such that u = lim ι(un)
and v = lim ι(vn).
Then, for sufficiently large n, d(u, ι(un)) < 2−m
and
d(v, ι(vn)) < 2−m
.
Hence d(un, vn) = d(ι(un), ι(vn)) ≥ 2−m
for all sufficiently large n.
It follows that every S ∈ V with |S| < m fails the identity un = vn
and, therefore, also the pseudoidentity u = v.
44 / 245
Proposition 4.6
For u, v ∈ ΩAV, we have d(u, v) = 2−r(u,v), where
r(u, v) = min{|S| : S ∈ V and S |= u = v}.
Proof.
We have already shown that d(u, v) ≥ 2−m implies r(u, v) ≤ m.
The converse, as well as how the equivalence gives the proposition
are left as an exercise.
45 / 245
Recall that a metric space is compact if every sequence admits
some convergent subsequence. Equivalently, every covering by
open subsets contains a finite covering.
Proposition 4.7
1. If X is a totally bounded pseudo-metric space, then ˆX is also
totally bounded.
2. If X is a totally bounded complete metric space, then X is
compact.
46 / 245
Proof.
1. Given > 0, let u1, . . . , um ∈ X be such that X =
m
i=1 B /2(ui ).
Then ˆX =
m
i=1 B (ι(ui )) since every element of ˆX is at distance at most
/2 of some element of ι(X).
2. For each positive integer m, let Fm be a finite subset of X such that
X = x∈Fm
B2−m (x) and consider an arbitrary sequence (un)n in X.
For infinitely many indices n, the un belong to the same B2−1 (x1). Let k1
be the first of these indices. Similarly, among the remaining such indices,
there are infinitely many n such that the un belong to the same B2−2 (x2).
We let k2 be the first of them. And so on.
We thus construct a subsequence (ukn
)n with the property that
d(ukm
, ukn
) ≤ 2− min{m,n}+1
,
if p = min{m, n}, then ukm , ukn ∈ B2−p (xp), which yields
d(ukm , ukn ) ≤ d(ukm , xp) + d(xp, ukn ) ≤ 2−p
+ 2−p
whence a Cauchy sequence and, therefore, convergent.
47 / 245
Outline
Language recognition devices
Eilenberg’s correspondence
Decidable pseudovarieties
Metrics associated with pseudovarieties
Pro-V semigroups
Reiterman’s Theorem
Examples of relatively free profinite semigroups
Pseudowords as operations
Implicit signatures
48 / 245
By a pro-V semigroup we mean a semigroup S endowed with
a metric such that the following properties hold:
1. S is compact;
2. the multiplication is uniformly continuous (metric semigroup);
3. for every pair u, v of distinct elements of S, there is a uniform
continuous homomorphism ϕ : S → T into a semigroup
from V such that ϕ(u) = ϕ(v) (S residually in V).
By a profinite semigroup we mean a pro-S semigroup.
49 / 245
Proposition 5.1
Let S be a pro-V semigroup. Then there is a sequence (Sn)n∈N of
semigroups from V and an injective homomorphism
ϕ : S → n∈N Sn such that, for each component projection
πm : n∈N Sn → Sm, the homomorphism πm ◦ ϕ is uniformly
continuous.
We may define in n∈N Sn a metric structure by letting
d(u, v) =
n∈N
2−n
dn(πn(u), πn(v))
where dn is the discrete metric on Sn. Then ϕ is uniformly
continuous. In particular, the image T of ϕ is closed in n∈N Sn,
being a compact subset.
50 / 245
Note that the sequence (Sn)n∈N may be chosen so that there
is a finite bound on the number of generators of the Sn if and
only if S is finitely generated in the sense that there is a finite
subset which generates a dense subsemigroup.
On the other hand, if there is no such bound, one can show
that S cannot have a countable dense subset, while it is easy
to see that a compact metric space always admits a countable
dense subset.
Proposition 5.2
Every pro-V metric semigroup is finitely generated.
51 / 245
For a finite set A, we say that the pro-V semigroup S is freely
generated by A if there is a mapping γ : A → S such that
γ(A) generates a dense subsemigroup of S and the following
universal property is satisfied, where ϕ : A → T is an arbitrary
mapping into a pro-V semigroup T, and ˆϕ is a unique
continuous homomorphism:
A
γ
GG
ϕ
11
S
ˆϕ

T
Theorem 5.3
For a pseudovariety of semigroups V and a finite set A, the metric
semigroup ΩAV is a pro-V semigroup freely generated by A via the
mapping ι|A.
52 / 245
Proof.
Let S be a pro-V semigroup and let (Sn)n∈N be a countable family of
semigroups from V as given by Proposition 5.1, so that there is an
embedding ϕ : S → n∈N Sn with each composite function
πn ◦ ϕ : S → Sn uniformly continuous.
Given a mapping ψ : A → S, let ψn = πn ◦ ψ.
A
ι|A
GG
ψ

ψn
22
ΩAV
ˆψn

S πn
GG Sn
The family ( ˆψn)n∈N induces a homomorphism ˆψ : ΩAV → n∈N Sn. Its
image lies in the closed subsemigroup T, whence it lifts to the required
continuous homomorphism ΩAV → S. It is uniformly continuous because
every continuous mapping from a compact metric space into another
metric space is uniformly continuous.
53 / 245
A subset of a metric space is said to be clopen if it is both closed
and open.
A metric space is said to be zero-dimensional if every open set is a
union of clopen subsets.
Proposition 5.4
Every pro-V semigroup is zero-dimensional.
Proof.
Let u be an element of the pro-V semigroup S. It suffices to show that
the open ball B (u) contains some clopen set which contains u.
For each v ∈ S \ B (u), let ϕv : S → Tv be a uniformly continuous
homomorphism into a semigroup from V such that ϕv (u) = ϕv (v). Then
Kv = ϕ−1
v ϕv (v) is a clopen set which contains v but not u. In particular,
the Kv form a clopen covering of the closed set S \ B (u), from which a
finite covering F can be extracted.
The union of the clopen sets in F is itself a clopen set K. Note that
S \ K is also clopen, contains u, and is contained in B (u).
54 / 245
For a mapping ϕ : S → T, let ker ϕ = {(u, v) : ϕ(u) = ϕ(v)}
be the kernel of ϕ.
Theorem 5.5
An A-generated profinite semigroup S is a continuous
homomorphic image of ΩAV if and only if it is a pro-V semigroup.
Corollary 5.6
Let S be a pro-V semigroup and suppose that ϕ : S → T is a
continuous homomorphism onto a finite semigroup. Then
T ∈ V.
55 / 245
Proof of Theorem 5.5.
(⇐) Apply Theorem 5.3.
(⇒) Let ϕ : ΩAV → S be an onto continuous homomorphism. We need
to show that S is residually in V.
Given distinct points s1, s2 ∈ S, since S is residually in S, there is an onto
uniformly continuous homomorphism ψ : S → T such that T ∈ S and
ψ(s1) = ψ(s2). Note that T is a finite continuous homomorphic image
of ΩAV. If we can show that S ∈ V, we will be done. In other words, it
suffices to consider the case where S is finite.
Since ϕ is continuous and ΩAV is compact, ϕ is uniformly continuous.
Hence, there is a positive integer n such that, for all u, v ∈ ΩAV,
d(u, v) < 2−n
⇒ ϕ(u) = ϕ(v).
In view of Proposition 4.6, it follows that the intersection ρ of the kernels
of the uniformly continuous homomorphisms ΩAV → V with V ∈ V and
|V | ≤ n is contained in ker ϕ. Hence, ϕ factors through the natural
homomorphism ΩAV → ΩAV/ρ. Since ΩAV/ρ belongs to V, so
does S.
56 / 245
Lemma 5.7 ([Num57, Hun88])
Let K be a clopen subset of a compact zero-dimensional metric semigroup S.
Then there is a continuous homomorphism ϕ : S → T into a finite semigroup
T such that K = ϕ−1
ϕ(K).
Proof.
We may define on S a syntactic congruence of K by
u σK v if ∀ x, y ∈ S1
(xuy ∈ K ⇔ xvy ∈ K).
It suffices to show that the classes of this congruence are open: then there are
only finitely many of them, so that S/σK is a finite semigroup, and the natural
mapping S → S/σK is a continuous homomorphism.
We show that, if lim un = u, then all but finitely many terms in the sequence
are σK -equivalent to u. Arguing by contradiction, otherwise, there is a
subsequence consisting of terms which fail this property. We may as well
assume that so does the original sequence.
For each n there are xn, yn ∈ S1
such that one, but not both, of the products
xnunyn and xnuyn lies in K. Again, by taking subsequences we may assume that
lim xn = x, lim yn = y (in S1
), and xnuyn /∈ K. Then
xuy = lim xnunyn = lim xnuyn must belong to both K and its complement.
57 / 245
A useful application of Lemma 5.7 is the following result, which
completes that of Proposition 5.4.
Theorem 5.8
A compact metric semigroup is profinite if and only if it is
zero-dimensional.
Proof.
(⇒) This follows from Proposition 5.4.
(⇐) Let S be a compact metric semigroup which is zero-dimensional.
We need to show that it is residually in S, that is that, for every pair s, t
of distinct points of S, there is a continuous homomorphism ϕ : S → T
in to a finite semigroup T such that ϕ(s) = ϕ(t).
Since S is a zero-dimensional metric space, there is some clopen subset
K such that s ∈ K and t /∈ K. By Lemma 5.7, there is a continuous
homomorphism ϕ : S → T into a finite semigroup T such that
K = ϕ−1
ϕ(K). In particular, we have ϕ(s) = ϕ(t), as required.
58 / 245
A language L ⊆ A+
is V-recognizable if its syntactic semigroup
belongs to V.
Theorem 5.9
A language L ⊆ A+
is V-recognizable if and only if the closure K = ι(L)
is open in ΩAV and ι−1
(K) = L. The latter condition is superfluous if
ι is injective and ι(A+
) is a discrete subset of ΩAV.
Proof.
(⇒) Use the universal property of ΩAV (Theorem 5.3).
(⇐) By Lemma 5.7, there is a continuous homomorphism ϕ : ΩAV → S
such that S ∈ V and K = ϕ−1
ϕ(K). Then ψ = ϕ ◦ ι is a homomorphism
A+
→ S such that ψ−1
ϕ(K) = ι−1
(K) = L and so L is
V-recognizable.
Theorem 5.9 implies that, as a topological space, ΩAV is the Stone
dual of the Boolean algebra of V-recognizable languages of A+
.
59 / 245
Theorem 5.10
A set S of V-recognizable languages over a finite alphabet A generates
the Boolean algebra of all such languages if and only if the clopen sets of
the form ι(L) (L ∈ S) suffice to separate points of ΩAV.
Proof.
(⇒) Let u, v ∈ ΩAV be distinct points. Then = d(u, v) is positive. Since
ΩAV is zero-dimensional (Proposition 5.4), there is a clopen subset K
containing u and contained in B (u), whence not containing v. By
Theorem 5.9, L = ι−1
(K) is V-recognizable. From the hypothesis, it follows
that L is a Boolean combination f (L1, . . . , Ln) of languages Li from S. By
Theorem 5.9 again, each set ι(Li ) is clopen. Since ι(X1 ∪ X2) = ι(X1) ∪ ι(X2)
and ΩAV \ ι(X) = ι(A+ \ X) for V-recognizable languages X, X1, X2 ⊆ A+
, we
have K = ι(L) = f (ι(L1), . . . , ι(Ln)). Hence at least one of the sets ι(Li ) must
contain exactly one of the points u and v.
(⇐) By Theorem 5.9, it suffices to show that the clopen sets of the form ι(L),
with L ⊆ A+
V-recognizable, generate the Boolean algebra of all clopen subsets
of ΩAV. This is a nice exercise on compactness.
60 / 245
Outline
Language recognition devices
Eilenberg’s correspondence
Decidable pseudovarieties
Metrics associated with pseudovarieties
Pro-V semigroups
Reiterman’s Theorem
Examples of relatively free profinite semigroups
Pseudowords as operations
Implicit signatures
61 / 245
Recall that a V-pseudoidentity is a formal equality u = v with
u, v ∈ ΩAV for some finite set A.
Recall also that, for S ∈ V, we write S |= u = v if
ϕ(u) = ϕ(v) for every continuous homomorphism
ϕ : ΩAV → S. In this case, we also say that u = v holds in S.
For a set Σ of V-pseudoidentities, let [[Σ]] denote the class of
all S ∈ V such that S |= u = v for every pseudoidentity u = v
from Σ.
For a subpseudovariety W of V, let pW : ΩAV → ΩAW be the
natural continuous homomorphism:
A
ιV
GG
ιW 33
ΩAV
pW:=ˆιW

ΩAW
62 / 245
Lemma 6.1
A pseudoidentity u = v, with u, v ∈ ΩAV, holds in every member
of a subpseudovariety W of V if and only if pW(u) = pW(v).
Theorem 6.2 ([Rei82])
A subclass W of V is a subpseudovariety if and only if it is of the
form [[Σ]] for some set Σ of V-pseudoidentities.
Usually, one takes V = S.
63 / 245
Proof of Theorem 6.2.
(⇐) This amounts to verifying that the property S |= u = v is preserved under
taking homomorphic images, subsemigroups and finite direct products, which
follows easily from the definitions.
(⇒) Fix a countably infinite set X and let Σ be the set of all pseudoidentities
u = v such that u, v ∈ ΩAV for some finite subset A of X and S |= u = v for
all S ∈ W. Then U = [[Σ]] is a subpseudovariety of V by the first part of the
proof, and it clearly contains W. We claim that U = W.
Let S ∈ U and choose an onto continuous homomorphism ϕ : ΩAU → S for
some finite subset A of X (cf. Theorem 5.3).
Consider the natural continuous homomorphisms pU
and pW. By Lemma 6.1 and the choice of Σ, we
have ker pW ⊆ ker pU and so there is a factorization
pU = ψ ◦ pW for some onto continuous homomorphism
ψ : ΩAW → ΩAU. Hence ϕ ◦ ψ : ΩAW → S is an
onto continuous homomorphism. Corollary 5.6 then implies
that S ∈ W since ΩAW is a pro-W semigroup by
Theorem 5.3.
ΩAV
pU
GG
pW

ΩAU
ϕ

ΩAW
ψ
``
S
64 / 245
To write pseudoidentities that are not identities, one needs to
construct some elements of ΩAS \ A+.
Lemma 6.3
Let S be a profinite semigroup, let s be an element of S, and let
k ∈ Z. Then the sequence of powers (sn!+k)n≥|k| converges. For
k = 0 the limit is an idempotent.
Proof.
Using Proposition 5.1, it suffices to consider the case where S is
finite, which is left as an exercise.
The limit lim sn!+k is denoted sω+k.
Note that sω+ksω+ = sω+k+ .
In particular, sω := sω+0 is an idempotent and sω−k and sω+k
are mutual inverses in the maximal subgroup containing the
idempotent sω.
65 / 245
Examples I
S = [[x = x]]
I = [[x = y]]
G = [[xω
= 1]]
Gp =?
A = [[xω+1
= xω
]]
Com = [[xy = yx]]
J = [[(xy)ω
= (yx)ω
, xω+1
= xω
]]
R = [[(xy)ω
x = (xy)ω
]]
L = [[y(xy)ω
= (xy)ω
]]
Sl = [[xy = yx, x2
= x]]
RZ = [[xy = y]]
B = [[x2
= x]]
N = [[xω
= 0]]
K = [[xω
y = xω
]]
D = [[yxω
= xω
]]
66 / 245
Examples II
Since there are uncountably many pseudovarieties of the form
AbP, where P is a set of primes, and one can show that all of
them admit a description of the form [[xy = yx, u = 1]]
[Alm95, Corollary 3.7.8], for some u ∈ Ω{x}S, we conclude
that Ω{x}S is uncountable.
Let P be an infinite set of primes and let p1, p2, . . . be an
enumeration of its elements, without repetitions.
Let uP be an accumulation point in Ω{x}S of the sequence
(xp1···pn )n.
AbP = [[xy = yx, uP = 1]].
Does the sequence (xp1···pn )n converge?
67 / 245
Examples III
To describe the pseudovariety Gp of all finite p-groups, we use
the following result, whose proof is similar to that of
Lemma 6.3.
Lemma 6.4
Let S be a profinite semigroup and s ∈ S. Then the sequence
(spn!
)n converges.
We let spω
= lim spn!
.
Gp = [[xpω
= 1]].
68 / 245
Examples IV
Exercise 6.5 (For those that know some group
theory)
Find, for each of the following pseudovarieties of groups, a single
pseudoidentity defining them:
(1) the pseudovariety Gp of all finite groups which have no
elements of order p (p being a fixed prime number);
(2) the pseudovariety Gnil of all finite nilpotent groups;
(3) the pseudovariety Gsol of all finite solvable groups.
69 / 245
Outline
Language recognition devices
Eilenberg’s correspondence
Decidable pseudovarieties
Metrics associated with pseudovarieties
Pro-V semigroups
Reiterman’s Theorem
Examples of relatively free profinite semigroups
Pseudowords as operations
Implicit signatures
70 / 245
N: finite nilpotent semigroups
Recall that N = [[xω
= 0]] = n≥1[[x1 · · · xn = 0]].
The proof depends on the following key result.
Lemma 7.1
Let S be a finite semigroup with n elements. Then, for every choice of
elements s1, . . . , sn ∈ S, there exist indices i, j such that 0 ≤ i < j ≤ n
and the following equality holds for all k ≥ 1:
s1 · · · sn = s1 · · · si (si+1 · · · sj )k
sj+1 · · · sn.
Proof.
Consider the n products pr = s1 · · · sr (r = 1, . . . , n). If they are all distinct,
then at least one of them, say pr , is idempotent and we may take i = 0, j = r.
Otherwise, there are indices i, j such that 1 ≤ i < j ≤ n and pi = pj , in which
case pi = pj = pi si+1 · · · sj = pi (si+1 · · · sj )k
.
71 / 245
Let ϕ : A+
→ S be a homomorphism into a semigroup S ∈ N, say
satisfying x1 · · · xn = 0. Then, all words of length at least n belong
to ϕ−1
(0) and for s ∈ S \ {0}, the words in the language
L = ϕ−1
(s) have length less than n, and so L is a finite set.
Thus, every N-recognizable language is either finite or cofinite.
To show that these are precisely the N-recognizable languages, it
suffices to show that every singleton language {w} ⊆ A+
is
N-recognizable.
Let n = |w| be the length of the word w. Consider the semigroup S
consisting of the words of A+
of length at most n together with a
zero element 0. The product of two words is the word resulting from
their concatenation if that word has length at most n and is 0
otherwise.1
Then S satisfies the identity x1 · · · xn = 0, for the
natural homomorphism ϕ : A+
→ S, that sends each letter to itself,
we have ϕ−1
(w) = {w}.
1
This amounts to“killing”the ideal of the semigroup A+
consisting of the
words of length greater than n, identifying all the elements in the ideal to a
zero. In semigroup theory, such a construction is called a Rees quotient.
72 / 245
Proposition 7.2
A language over a finite alphabet A is N-recognizable if and only if
it is finite or its complement in A+ is finite.
In view of Theorem 5.9, we deduce the following result:
Proposition 7.3
Let V be a pseudovariety of semigroups containing N. Then the
completion homomorphism ι : A+ → ΩAV is injective and A+ is a
discrete subspace of ΩAV. In particular, a language L ⊆ A+ is
V-recognizable if and only if its closure L in ΩAV is a clopen
subset.
73 / 245
Proof.
The injectivity of ι amounts to V satisfying no identity u = v with
u, v ∈ A+ distinct words. Indeed, Synt({u}) is nilpotent, whence it
belongs to V. Since 1u1 ∈ {u} while 1v1 /∈ {u}, we deduce that u
and v are not σ{u}-equivalent and so Synt({u}) |= u = v.
We may therefore identify each w ∈ A+ with ι(w) ∈ ΩAV.
For w ∈ A+, we have {w} = {w}, because ΩAV is a metric space.
Since {w} is V-recognizable, its closure {w} is an open subset
of ΩAV by Theorem 5.9. Hence A+ is a discrete subset
of ΩAV.
74 / 245
Proposition 7.4
The semigroup ΩAN is obtained by adding to A+ a zero element.
The open sets containing zero consist of zero together with a
cofinite subset of A+.2
Proof.
It suffices to observe that a non-eventually constant sequence
(wn)n of words of A+ is a Cauchy sequence with respect to the
metric dN if and only if lim |wn| = ∞. In the affirmative case, for
every homomorphism ϕ : A+ → S into S ∈ N, we have
lim ϕ(wn) = 0. Thus, all non-eventually constant Cauchy
sequences converge to the same point of ΩAN, which is a zero.
The open subsets of ΩAN containing 0 have complement which is
a closed, whence compact, subset of A+. Since A+ is a discrete
subset of ΩAN, that complement must be finite. The converse is
clear.
2
This is known as the Alexandroff or one-point compactification, which in
general is obtained by adding one point and declaring the open sets containing
it to consist also of the complement of a compact subset of the original space.
75 / 245
K: finite semigroups satisfying es = e
Recall that K = [[xω
y = xω
]]. Note that
K =
n≥1
Kn where Kn = [[x1 · · · xny = x1 · · · xn]].
Let AN
denote the set of all right infinite words over A, i.e.,
sequences of letters.
Endow the set S = A+
∪ AN
with the operation
u · v =
uv if u ∈ A+
u otherwise
and the function d : S × S → R≥0 defined by d(u, v) = 2−r(u,v)
,
where r(u, v) is the length of the longest common prefix of u and v.
76 / 245
Proposition 7.5
The set S is a pro-K semigroup for the above operation and distance
function d. The unique continuous homomorphism ΩAK → S that sends each
letter a ∈ A to itself is an isomorphism.
Proof.
It is easy to check that the multiplication defined on S is associative and that d
is an totally bounded complete ultrametric.
Consider the set Sn consisting of all words of A+
of length at most n, endowed
with the operation
u · v =
uv if |uv| ≤ n
in(u) otherwise
where in(w) denotes the longest prefix of length at most n of the word w. This
operation is associative and Sn ∈ Kn. Moreover, every n-generated semigroup
from Kn is a homomorphic image of Sn. Hence Sn ΩAKn.
Note also that the mapping ϕn : S → Sn which sends each w ∈ S to in(w) is a
continuous homomorphism.
Hence, given two distinct points u and v from S, for n = r(u, v) + 1, the
mapping ϕn is a continuous homomorphism into a semigroup from K which
distinguishes u from v. Thus, S is a pro-K semigroup.
77 / 245
(. . . )
Consider next the unique continuous homomorphism ψ : ΩAK → S which maps
each letter a ∈ A to itself. Since K = n≥1 Kn, given distinct u, v ∈ ΩAK,
there exists a continuous homomorphism θ : ΩAK → Sn such that θ(u) = θ(v).
ΩAK
ψ
GG
θ

S
ϕn

Sn ΩAKn
µ
oo
The fact that the above diagram can always be completed by a homomorphism
µ shows that ψ(u) = ψ(v). Hence ψ is injective.
78 / 245
Outline
Language recognition devices
Eilenberg’s correspondence
Decidable pseudovarieties
Metrics associated with pseudovarieties
Pro-V semigroups
Reiterman’s Theorem
Examples of relatively free profinite semigroups
Pseudowords as operations
Implicit signatures
79 / 245
Implicit operations
Let n be a positive integer.
An n-ary implicit operation on pro-V semigroups is a
correspondence π associating to each pro-V semigroup S an
n-ary operation πS : Sn → S such that , for every continuous
homomorphism ϕ : S → T between pro-V semigroups, the
following diagram commutes:
Sn πS GG
ϕn

S
ϕ

Tn πT GG T,
i.e., ϕ πS (s1, . . . , sn) = πT ϕ(s1), . . . , ϕ(sn) for all
s1, . . . , sn ∈ S.
Examples: the binary multiplication (s1, s2) → s1s2 and the
component projections (s1, . . . , sn) → si are implicit
operations. Composing implicit operations we also obtain
implicit operations.
80 / 245
If A and B are finite sets with the same cardinality n, then
ΩAV ΩBV. We denote by ΩnV any of them. Usually, we
identify ΩnV with ΩXn V, where Xn = {x1, . . . , xn} has
cardinality n.
To each w ∈ ΩnV, we may associate an n-ary implicit
operation πw on pro-V semigroups as follows:
for a pro-V semigroup S, given s1, . . . , sn ∈ S, let f : Xn → S
be the function defined by f (xi ) = si (i = 1, . . . , n);
let (πw )S (s1, . . . , sn) = ˆf (w) where ˆf is a continuous
homomorphism completing the following diagram:
Xn
ι GG
f
33
ΩnV
ˆf

S.
81 / 245
Proposition 8.1
1. For each w ∈ ΩnV, πw is indeed an n-ary implicit
operation on pro-V semigroups.
2. The correspondence w ∈ ΩnV → πw is injective and in
fact πw is completely characterized by the operations
(πw )S with S ∈ V.
82 / 245
Proof.
1. Let ϕ : S → T be a continuous homomorphism between two pro-V
semigroups and let s1, . . . , sn be elements of S. Let f : Xn → S be defined by
f (xi ) = si (i = 1, . . . , n). Then we have the following commutative diagram:
Xn
f

ϕ◦f
ι

ΩnV
ˆf
}} ϕ◦f
33
S ϕ
GG T
which shows that
ϕ (πw )S (f (s1), . . . , f (sn)) = ϕ ˆf (w) = ϕ ◦ f (w)
= (πw )T ϕ(f (s1)), . . . , ϕ(f (sn)) .
83 / 245
(. . . )
2. Let u, v ∈ ΩnV be two distinct elements. Then there exists a continuous
homomorphism ϕ : ΩnV → S into a semigroup S ∈ V such that ϕ(u) = ϕ(v).
Let si = ϕ(xi ) (i = 1, . . . , n). For w ∈ ΩnV, by definition of πw we have
(πw )S (s1, . . . , sn) = ϕ(w).
Since ϕ(u) = ϕ(v), we deduce that
(πu)S (s1, . . . , sn) = (πv )S (s1, . . . , sn)
and so, certainly πu = πv .
We identify w with πw .
Note that S ∈ V satisfies the V-pseudoidentity u = v if and only if
uS = vS .
We say that a pro-V semigroup S satisfies the V-pseudoidentity
u = v if uS = vS .
84 / 245
Outline
Language recognition devices
Eilenberg’s correspondence
Decidable pseudovarieties
Metrics associated with pseudovarieties
Pro-V semigroups
Reiterman’s Theorem
Examples of relatively free profinite semigroups
Pseudowords as operations
Implicit signatures
85 / 245
By an implicit signature we mean a set σ of implicit operations
(on S) which includes the binary operation of multiplication.
Example: κ = { · , ω−1}.
Given an implicit signature σ, each profinite semigroup S
becomes a natural σ-algebra in which each operation w ∈ σ is
interpreted as wS .
In particular, each ΩAV becomes a σ-algebra. The
σ-subalgebra generated by ι(A) is denoted Ωσ
AV.
For the minimum implicit signature σ, consisting only of
multiplication, we denote Ωσ
AV simply by ΩAV.3
A formal term constructed from the letters a ∈ A using the
operations from the implicit signature σ is called a σ-term
over A. Such a σ-term w determines an element wV of Ωσ
AV
by evaluating the operations within Ωσ
AV.
3
The bar in the notation ΩAV comes from the fact ΩAV = ι(A+
) is dense
in ΩAV. This notation (without reference to V) was introduced by
Reiterman [Rei82].
86 / 245
The following result is an immediate consequence of
Theorem 5.3.
Proposition 9.1
The σ-algebra Ωσ
AV is a V-free σ-algebra freely generated by A in
the sense of the following universal property: for every mapping
ϕ : A → S into a semigroup S ∈ V, there is a unique
homomorphism ˆϕ of σ-algebras such that the following diagram
commutes:
A
ι GG
ϕ
33
Ωσ
AV
ˆϕ

S.
87 / 245
Examples:
Ωκ
AN = ΩAN;
for |A| ≥ 2, since ΩAK is uncountable, we have Ωσ
AK ΩAK
for every countable implicit signature σ;
Ωκ
AJ = ΩAJ [Alm95, Section 8.1];
Ωκ
AG is the free group freely generated by ι(A) = A;
Ωκ
ACR is the free completely regular (union of groups)
semigroup freely generated by ι(A) = A.
88 / 245
A key problem for the applications is to be able to solve the
word problem in the free σ-algebra Ωσ
AV: to find an algorithm,
if one exists, that given two σ-terms over A, determines
whether uV = vV.
If such an algorithm exists, then we say that the word problem
is decidable; otherwise, we say that it is undecidable.
89 / 245
Examples:
The word problem for Ωκ
AN: two κ-terms coincide in Ωκ
AN if and
only if they are equal or they both involve the operation ω−1
.
The word problem for Ωκ
AG is well known: the operation ω−1
is
inversion in profinite groups, so all κ-terms can be effectively
reduced (over G) to κ-terms in which that operation is only applied
to letters; then use, in any order, the reduction rules aaω−1
→ 1 and
aω−1
a → 1 (a ∈ A) to obtain a canonical form for κ-terms over G;
two κ-terms are equal over G if and only if they have the same
canonical form.
Word problem for Ωκ
AK: exercise.
The solution of the word problem for Ωκ
AJ = ΩAJ gives the
structure of ΩAJ [Alm95, Section 8.1].
The word problem for Ωκ
ACR has been solved by Kad’ourek and
Pol´ak [KP86].
The word problem for Ωκ
AA has been solved by
McCammond [McC01].
90 / 245
Part II
Separating words and regular
languages
91 / 245
Outline
σ-fullness
σ-reducibility of the V-separation problem
pro-V-metrics
Inverse automata
V-invertibility of endomorphisms
Computing closures of finitely generated
subgroups
The Pin-Reutenauer procedure
92 / 245
A separation problem
Let V be a pseudovariety of semigroups.
Suppose that a regular language L ⊆ A+ and a word w ∈ A+
are given. How do we find out whether a proof that w /∈ L
exists using V-recognizable languages?
More precisely, we wish to decide whether, given such L and
w, there exists a V-recognizable language K ⊆ A+ such that
L ⊆ K and w /∈ K.
For instance, how do we determine whether there exists a
finite permutation automaton such that no word from L ends
in the same state as w does?
Another example of the same type of problem: is there some
integer n such that no word from L has the same subwords of
length at most n as w does?
93 / 245
Our problem sounds like a topological separation problem, and
indeed it admits such a formulation in the profinite world.
Proposition 10.1
Let V be a pseudovariety of semigroups, L ⊆ A+ a regular
language and w a word in A+. Then there is a V-recognizable
language K ⊆ A+ such that L ⊆ K and w /∈ K if and only if ιV(w)
does not belong to the closure of ιV(L) in ΩAV.
Proof.
By Proposition 5.4, the condition ιV(w) belongs to the closure ιV(L)
in ΩAV holds if and only if every clopen subset of ΩAV which contains
ιV(w) has nontrivial intersection with ιV(L). By Theorem 5.9, such
clopen subsets are precisely the sets of the form ιV(K) where K is a
V-recognizable subset of A+
. It remains to observe that, ιV(w) ∈ ιV(K)
and ιV(K) ∩ ιV(L) = ∅ if and only if w ∈ K and K ∩ L = ∅, which follows
from the facts that K = ι−1
V (ιV(K)) and L ⊆ ι−1
V (ιV(L)).
94 / 245
Corollary 10.2
Let V be a pseudovariety containing N. If w is a word in A+ and
L ⊆ A+ is a regular language, then w and L can be separated by a
V-recognizable language if and only if w /∈ L.
Proof.
By Proposition 7.3, ι embeds A+ in ΩAV as a discrete subspace,
meaning that every subset is open. Hence, if w belongs to the
closure L of L in ΩAV, then w ∈ L.
More directly, in case N ⊆ V, the language {w} is
V-recognizable and therefore there is a V-recognizable
language containing w and disjoint from L if and only if
w /∈ L.
Note that the condition N ⊆ V is equivalent to V satisfying
some pseudoidentity of the form xω+n = xn, where n is a
positive integer.
95 / 245
A refined separation separation problem
Even for pseudovarieties V containing N, the separation
problem becomes nontrivial if we wish instead to separate two
regular languages by a V-recognizable language.
The following result can be proved basically by the same
argument as presented for the proof of Proposition 10.1,
taking additionally into account that ΩAV is compact. The
details are left as an exercise.
Proposition 10.3
Let V be a pseudovariety of semigroups and L1, L2 ⊆ A+ regular
languages. Then there is a V-recognizable language K ⊆ A+ such
that L1 ⊆ K and L2 ∩ K = ∅ if and only if the closures of ιV(L1)
and ιV(L2) in ΩAV are disjoint sets.
96 / 245
In the case of A, Henckell has constructed an algorithm,
working directly in a finite semigroup which recognizes
simultaneously two given regular languages, which decides
whether they may be separated by a star-free
language [Hen88].
An idea due to Pin and Reutenauer [PR91] in the case of the
pseudovariety G of all finite groups is to somehow“compute”
the closure of ιV(L) not in ΩAG but in the free group Ωκ
AG, or
even in A+.
Under the assumption of a conjectured property for the
pseudovariety G, they produced an algorithm for computing
the required closure, which solves our problem for G.
We proceed to introduce the required property in general,
returning later to their algorithm.
97 / 245
For a subset L of A+, denote by clσ,V(L) and clV(L)
respectively the closure of ιV(L) in Ωσ
AV and in ΩAV.
Note that clσ,V(L) = clV(L) ∩ Ωσ
AV.
In particular, for w ∈ A+, we have ι(w) ∈ clV(L) if and only if
ι(w) ∈ clσ,V(L).
Denote by pV the natural continuous homomorphism
ΩAS → ΩAV.
Since ΩAS is compact and pV is an onto continuous mapping,
we always have the equality clV(L) = pV(clS(L)).
In general, for a continuous function f : S → T, and a subset
X of S, we have f (X) ⊆ f (X). The reverse inclusion also
holds if f is onto and S is compact.
98 / 245
σ-fullness
We say that the pseudovariety V is σ-full if, for every regular
language L ⊆ A+, the following equality holds:
clσ,V(L) = pV(clσ,S(L)).
In other words, membership of w ∈ Ωσ
AV in clσ,V(L) is
witnessed by some w ∈ clσ,S(L) such that pV(w ) = w.
99 / 245
Theorem 10.4 ([AS00a])
Let V be a pseudovariety, A a finite alphabet and σ an implicit signature such
that the following conditions hold:
(1) V is σ-full;
(2) the word problem for Ωσ
AV is decidable;
(3) σ is recursively enumerable;
(4) V is recursively enumerable;
(5) for each operation in σ, there is an algorithm to compute it in any given
finite semigroup.
Then it is decidable whether, given a regular language L ⊆ A+
and a
pseudoword w ∈ Ωσ
AV, we have w ∈ clσ,V(L).
Proof sketch.
Enumerate the pairs (w, L) for which w ∈ clσ,V(L) holds using the assumptions
(1)–(3). To enumerate those for which the condition fails, enumerate 4-tuples
(ϕ, ψ, X, w) where ϕ : ΩAS → S and ψ : ΩAS → T are onto continuous
homomorphisms with S ∈ S and T ∈ V, X ⊆ S, and w ∈ Ωσ
AS are such that
X × {ψ(w)} ∩ Im(ϕ × ψ) = ∅ and output the corresponding pairs
(w, ϕ−1
(L) ∩ A+
). This requires the assumptions (4) and (5).
100 / 245
Examples:
The pseudovariety N is κ-full: for a regular language L ⊆ A+
and a κ-term w, wN ∈ clκ,N(L) if and only if w is a word
from L or w involves the operation ω−1 and L is infinite; in
the latter case, by compactness there is some κ-term v such
that vS ∈ clκ,S(L) \ A+ and so wN = 0 = pN(vS).
That the pseudovariety J is κ-full follows from the structure
theorem for ΩAJ [Alm95, Section 8.2].
The pseudovariety G is κ-full: the essential ingredient is a
seminal theorem of Ash [Ash91]; the details follow from
[AS00a] and [Del01].
The pseudovariety Ab is κ-full [Del01].
101 / 245
The pseudovariety Gp is not κ-full: this follows from a weak
version of Ash’s theorem proved by Steinberg [Ste01] for Gp
together with the fact that the conjunction of this weaker
property with κ-fullness implies that the pseudovariety is
defined by pseudoidentities in which both sides are given by
κ-terms [AS00a] (cf. Proposition 11.1); however, such a
definition does not exist since, by a theorem of
Baumslag [Bau65], the free group is residually a finite p-group.
That the pseudovarieties A and R are κ-full has been proved
by JA-JCCosta-MZeitoun using the solution of the word
problems for Ωκ
AA [McC01]4 and Ωκ
AR [AZ07].
4
plus refinements from an alternative proof obtained by the same authors
including the fact that Ωκ
AA is closed for taking factors in ΩAA.
102 / 245
Outline
σ-fullness
σ-reducibility of the V-separation problem
pro-V-metrics
Inverse automata
V-invertibility of endomorphisms
Computing closures of finitely generated
subgroups
The Pin-Reutenauer procedure
103 / 245
Separation in σ-algebras
Let σ be an implicit signature.
Let V be a pseudovariety of semigroups.
Note that, if two regular languages K, L ⊆ A+ have disjoint
closures in ΩAV then they also have disjoint closures in Ωσ
AV.
If the converse also holds, then we say that V is weakly
σ-reducible for the separation problem.
This is a special case of a more general weak reducibility
property introduced in [AS00a]. The property is considered in
general for an arbitrary system of equations, the present case
being that of the equation x = y.
Naturally, there is also a stronger form of that property, which
we are not considering in these lectures. For a σ-full
pseudovariety, the two versions of the property are equivalent
[AS00a, AS00b].
104 / 245
Among others, the following pseudovarieties are known to be
weakly κ-reducible for the separation problem:
G [Ash91];
CR [AT01];
Gp, with p prime [Ste01];
A [JA-JCCosta-MZeitoun];
R [AS01];
J (follows from the solution of the word problem for ΩAJ
[Alm95, Section 8.2]);
LSl [CT04].
105 / 245
Say that a pseudovariety V is σ-equational if it admits a
definition by pseudoidentities involving only σ-operations.
Such pseudoidentities are also called σ-identities.
Proposition 11.1 ([AS00a])
If a pseudovariety V is weakly σ-reducible for the separation
problem and σ-full, then V is σ-equational.
106 / 245
Proof.
Let Σ be the set of all σ-identities which are valid in V. Clearly
V ⊆ [[Σ]].
Let S be a finite semigroup S that satisfies Σ. By Reiterman’s
Theorem 6.2, to show that S ∈ V, it suffices to establish that
S satisfies every pseudoidentity which is valid in V. Consider such
a pseudoidentity u = v, say with u, v ∈ ΩAS, and let ϕ : ΩAS → S
be a continuous homomorphism. We claim that ϕ(u) = ϕ(v).
Let K = ϕ−1(ϕ(u)) ∩ A+ and L = ϕ−1(ϕ(v)) ∩ A+. Note that,
since u ∈ clS(K), v ∈ clS(L), and pV(u) = pV(v), we have
clV(K) ∩ clV(L) = ∅. Since V is weakly σ-reducible for the
separation problem, there is some w ∈ clσ,V(K) ∩ clσ,V(L). Since
V is σ-full, there are w1 ∈ clσ,S(K) and w2 ∈ clσ,S(L) such that
pV(w1) = w = pV(w2). Hence w1 = w2 is a pseudoidentity
from Σ, which therefore is valid in S. Hence, we have
ϕ(u) = ϕ(w1) = ϕ(w2) = ϕ(v), which establishes the claim.
107 / 245
Theorem 11.2 ([AS00a])
Let V be a pseudovariety, A a finite alphabet and σ an implicit
signature such that the following conditions hold:
(1) V is σ-full;
(2) V is weakly σ-reducible for the separation problem;
(3) the word problem for Ωσ
AV is decidable;
(4) σ is recursively enumerable;
(5) V is recursively enumerable;
(6) for each operation in σ, there is an algorithm to compute it in
any given finite semigroup.
Then it is decidable whether two given regular languages
L1, L2 ⊆ A+ may be separated by a V-recognizable language
K ⊆ A+.
108 / 245
Proof.
Using property (5), we may enumerate the pairs (L1, L2) of regular languages
over A+
that may be separated by V-recognizable languages, by simply
enumerating triples (L1, L2, ϕ), with ϕ : A+
→ S a homomorphism onto an
arbitrary semigroup from V, and test whether ϕ separates L1 and L2. In the
affirmative case, output (L1, L2).
To enumerate the pairs that may not be separated, we use the assumption (2)
plus Proposition 10.3, which guarantees that, if L1 and L2 cannot be separated
by a V-recognizable language, then there is some w ∈ clσ,V(L1) ∩ clσ,V(L2)
which witnesses the non-separability. Each condition w ∈ clσ,V(Li ) may be
effectively tested by Theorem 10.4 and the candidates for witnesses may be
recursively enumerated by (4). We may thus proceed as follows:
enumerate all triples (L1, L2, w) with L1, L2 ∈ A+
regular languages and
w ∈ Ωσ
AV;
for each such triple, test whether w ∈ clσ,V(Li ) (i = 1, 2);
output the pairs (L1, L2) which pass the test as non-separable by
V-recognizable languages.
109 / 245
The algorithms described in Theorems 10.4 and 11.2 are
purely theoretical, being unusable in practice.
Thus, it is worth, particularly in cases where the decidability
of the separation property is already guaranteed by
Theorem 11.2, to find efficient algorithms to test separability.
110 / 245
Outline
σ-fullness
σ-reducibility of the V-separation problem
pro-V-metrics
Inverse automata
V-invertibility of endomorphisms
Computing closures of finitely generated
subgroups
The Pin-Reutenauer procedure
111 / 245
pro-V metrics
The same way we defined a pseudo-ultrametric on the free
semigroup A+ associated with a pseudovariety V, we may
define a pseudo-ultrametric on an arbitrary semigroup S: let
d(s1, s2) = 2−r(s1,s2)
,
where r(s1, s2) is the smallest cardinality of a semigroup
T ∈ V for which there is a homomorphism ϕ : S → T such
that ϕ(s1) = ϕ(s2).
Similar arguments show that d is indeed a pseudo-ultrametric
on S, with respect to which the multiplication in S is
uniformly continuous. If S is finitely generated, then the
completion ˆS is again a pro-V semigroup, but it may not be a
free pro-V semigroup.
The pseudo-ultrametric d is an ultrametric if and only if S is
residually in V.
Every homomorphism S → T into T ∈ V is uniformly
continuous.
112 / 245
Let V be a pseudovariety of semigroups, and let σ be an
implicit signature.
Considering the members of V as σ-algebras under the natural
interpretation of the operations from σ, since the
homomorphisms are the same, V is still a pseudovariety
of σ-algebras.
We may define a pseudo-ultrametric on a σ-algebra S similarly
to the semigroup case: let
dσ
(s1, s2) = 2−rσ(s1,s2)
where rσ(s1, s2) is the smallest cardinality of a member T ∈ V
for which there is a homomorphism ϕ : S → T of σ-algebras
such that ϕ(s1) = ϕ(s2).
113 / 245
The delicate point here is that, while continuous semigroup
homomorphisms between profinite semigroups respect implicit
operations, and in particular so do semigroup homomorphisms
between finite semigroups, semigroup homomorphisms
between arbitrary σ-algebras may not be homomorphisms of
σ-algebras.
Example: let U1 be two-element semilattice, which the
multiplicative subsemigroup of Z consisting of 0, 1; consider
the mapping ϕ : ΩAN → U1 that maps A+ to 1 and
everything else to 0. Then ϕ is a semigroup homomorphism
but not a homomorphism of κ-algebras.
114 / 245
Proposition 12.1
For a pseudovariety V and an implicit signature σ, the completion
of Ωσ
AV with respect to the pseudo-ultrametric dσ is ΩAV, both
metrically and algebraically.
Proof.
Since the algebraic structure is inherited by extension of uniformly
continuous operations, it suffices to show that, for u, v ∈ Ωσ
AV,
dσ
(u, v) = d(u, v), where d is the completion metric on ΩAV.
By Proposition 4.6, d(u, v) = 2−r
, where r is the smallest cardinality of a
member T ∈ V for which there exists a continuous homomorphism
ϕ : ΩAV → T such that ϕ(u) = ϕ(v). Since the restriction of ϕ to Ωσ
AV
is a homomorphism of σ-algebras which separates u from v, it follows
that rσ
(u, v) ≤ r. On the other hand, by the universal property of ΩAV
and since we interpret σ-operations naturally, every homomorphism of
σ-algebras Ωσ
AV → T ∈ V extends uniquely to a continuous
homomorphism ΩAV → T. Hence rσ
(u, v) = r.
115 / 245
Pro-H metric on groups
Traditionally, one denotes by H an arbitrary pseudovariety of
groups.
Because a group is highly symmetrical, the pro-H metric
structure looks similar everywhere.
Lemma 12.2
Let G be a group and consider the pro-H metric on G. Then, for
every u, v, w ∈ G, the equalities d(uw, vw) = d(u, v) = d(wu, wv)
hold. In particular, for > 0, we have Bε(u) = uBε(1) = Bε(1)u
and a subset X is open (respectively closed) if and only if so is
Xw. Moreover, for > 0, the ball B (1) is a clopen normal
subgroup of G such that G/B (1) ∈ H. A subgroup H is open if
and only if it contains some open ball B (1).
Proof.
This is a simple exercise.
116 / 245
For a subgroup H of a group G, denote by HG the largest
normal subgroup of G which is contained in H. It is given by
the formula
HG =
g∈G
g−1
Hg.
If we let G act on the set of right cosets of H in G by right
translation, then we obtain a homomorphism ϕ : G → SG/H
into the full symmetric group SG/H (of all permutations of the
set G/H) such that ϕ−1(id) = HG .
It follows that, if the index (G : H) of the subgroup H in G is
finite, then so is (G : HG ) and (G : HG ) is a divisor of
(G : H)!.
117 / 245
Lemma 12.3
A subgroup H of G is (cl)open in the pro-H metric if and only if
G/HG ∈ H.
Proof.
Suppose first that H is open. By Lemma 12.2, H contains a
normal subgroup K of G such that G/K ∈ H. Then K ⊆ HG and
so G/HG (G/K)/(HG /K) belongs to H. Conversely, if
G/HG ∈ H then HG is an open set, because the natural
homomorphism G → G/HG is (uniformly) continuous. Since H
contains HG , H is a union of cosets of HG , and so is its
complement. Hence H is clopen.
118 / 245
Another natural question is whether, for a subgroup H of G,
the intersection with H of an open subset of G in the pro-H
metric of G is also open in the pro-H metric of H.
In general, the answer is negative, but there are important
situations in which it is affirmative.
Example 12.4
Let G be the free group on two free generators a, b and consider
the homomorphism ϕ : G → S3 defined by ϕ(a) = (12) and
ϕ(b) = (13). Let K = ϕ−1(1) and let H = ϕ−1 (123) be the
inverse image of the subgroup of index 2. Then H is clopen in the
pro-Ab metric of G and K is clopen in the pro-Ab metric of H but
K is not clopen in the pro-Ab metric of G.
119 / 245
Note that, for pseudovarieties of groups K and H, K ∗ H
consists of all groups G which have a normal subgroup K such
that both K ∈ K and G/K ∈ H.5
If H ∗ H = H, then we say that H is closed under extension.
A condition for the answer to the above question to be
affirmative is drawn from the following result.
Lemma 12.5
Let H be a clopen subgroup of G in the pro-H metric of G and
suppose that U is a normal subgroup of H such that H/U ∈ H.
Then the normal subgroup UG of G is such that G/UG ∈ H ∗ H.
5
For those unfamiliar with semidirect products, take this as the definition of
K ∗ H and show that it is a pseudovariety of groups.
120 / 245
Proof.
Consider also the normal subgroup HG and let g ∈ G. By
Lemma 12.3, G/HG belongs to H. For each x ∈ HG , the
conjugate gxg−1 belongs to H and so the mapping
ϕg : HG → H/U which sends x to gxg−1U is a group
homomorphism. Moreover, for x ∈ HG , we have
x ∈ UG ⇔ x ∈ g−1
Ug for all g ∈ G
⇔ gxg−1
∈ U for all g ∈ G
⇔ ϕg (x) = 1 for all g ∈ G.
It follows that HG /UG embeds in a finite power of H/U and so
HG /UG ∈ H. The result now follows from the observation that
G/HG (G/UG )/(HG /UG ).
121 / 245
A first application of the preceding lemma is the following
answer to the above question.
Proposition 12.6
Suppose that H is closed under extension. Let H be a clopen
subgroup of G in the pro-H metric of G. Then a subset of H is
open in the pro-H metric of H if and only if it is open in the pro-H
metric of G.
Proof.
By Lemma 12.2, a subgroup L of H is open in the pro-H metric
of H if and only if it contains a normal subgroup U of H such that
H/U ∈ H. By Lemma 12.5, the normal subgroup UG of G is such
that U/UG ∈ H ∗ H = H. Hence U is open in the pro-H metric
of G by Lemma 12.3. Since L is a union of cosets of U, L is also
open in the pro-H metric of G.
122 / 245
In terms of pro-H metrics, we obtain the following more
precise result.
Proposition 12.7
Suppose that H is closed under extension and G is a group
residually in H. Let H be a clopen subgroup of G in the pro-H
metric of G. Then the pro-H metric dH of H and the restriction
to H of the pro-H metric dG of G have the same Cauchy
sequences.
123 / 245
Proof.
Let d be the restriction of dG to H and let r be the corresponding partial
function H × H → N. Denote by d the pseudo-metric dH and by r the
corresponding partial function. We start by establishing the following function
inequalities:
r ≤ r ≤ (G : H) · r !. (1)
The first inequality in (1) follows from the observation that, if a
homomorphism from G into a member of H distinguishes two elements of H
then its restriction to H also distinguishes them. Suppose next that u, v ∈ H
and the homomorphism ϕ : H → K with K ∈ H are such that ϕ(u) = ϕ(v).
Let U = ϕ−1
(1). Then H/U embeds in K and, therefore, it belongs to H. By
Lemma 12.5, UG is a normal subgroup of G of finite index such that
G/UG ∈ H ∗ H = H and, by an earlier observation, (G : UG ) divides (G : U)!.
If we choose above K so that |K| is minimum, then (H : U) = r (u, v) and so,
since uUG = vUG ,
r(u, v) ≤ (G : UG ) ≤ (G : U)! = (G : H) · (H : U) ! = (G : H) · r (u, v) !
which proves (1).
124 / 245
(. . . )
From the first inequality in (1) we deduce that every Cauchy sequence
with respect to d is also a Cauchy sequence with respect to d. For the
converse, let f (n) = (G : H) · n !. Then f is an increasing sequence and
a simple calculation shows that, for every ε > 0,
d ≤ 2−f ( − log2 ε )
=⇒ d ≤ ε.
This implies that Cauchy sequences for d are also Cauchy sequences
for d .
125 / 245
Free products
A free product in a variety V of semigroups is given by two
homomorphisms ϕi : Si → F (i = 1, 2), with S1, S2, F ∈ V
such that, given any other pair of homomorphisms
ψi : Si → T, with T ∈ V, there exists a unique
homomorphism θ : F → T such that the following diagram
commutes:
F
θ
22
S1
ϕ1
oo
ψ1

S2
ϕ2
yy
ψ2
GG T
By the usual argument, if the free product exists, then it is
unique up to isomorphism.
126 / 245
Exercise 12.8
Show that, for every variety V and semigroups S1, S2 ∈ V, the free
product of S1 and S2 in V exists.
For semigroups S and T in a variety V, we say that S is a free
factor of T if there exists U ∈ V such that T is a free product
of S and U in V. Note that every semigroup is a free factor of
itself.
Exercise 12.9
Suppose that S is a free factor of T in the variety V generated by
a pseudovariety V. Show that:
1. the pseudo-metric dS
V and the restriction of the pseudo-metric
dT
V to S coincide;
2. the open sets in pro-V metric of S are the intersection with S
of the open sets of T in the pro-V metric of T.
127 / 245
Theorem 12.10
Let H be a finitely generated subgroup of a finitely generated free
group G in the variety generated by the extension-closed
pseudovariety H and suppose that H is a free factor of a clopen
subgroup of G in the pro-H metric. Then the following hold:
1. the pro-H metric dH of H has the same Cauchy sequences as
the restriction of the pro-H metric dG ;
2. the completion of H with respect to dG is a free pro-H group.
128 / 245
Proof.
We may as well assume that H is not the trivial pseudovariety for,
otherwise, the result is obvious. Hence H contains some cyclic
group of prime order Z/pZ. Since H is closed under extension, it
follows that Gp ⊆ H for some prime p. Since the free group is
residually a finite p-group by a result of Baumslag [Bau65], we may
therefore assume that G is an absolutely free group. By the
Nielsen-Schreier Theorem, the subgroup H is also an absolutely
free group. By Proposition 12.1, the completion of H with respect
to the metric dH is a free pro-H group. Since, by Proposition 12.7
and Exercise 12.9, the Cauchy sequences of H are the same with
respect to both metrics dH and dG , the completion of H with
respect to both metrics is the same metric group and so it is a free
pro-H group.
129 / 245
The following corollaries will be useful later.
Corollary 12.11
Let H be an extension-closed pseudovariety of groups and let G be
a finitely generated free group in the variety generated by H. If the
finitely generated subgroup H is a free factor of a clopen subgroup
of G in the pro-H metric, then H is closed in that metric.
The following result is known as the subgroup theorem in the
theory of profinite groups. For simplicity, it is presented here only
in the finitely generated case, although the proof could be
extended to the general case.
Corollary 12.12
Let H be a clopen subgroup of a finitely generated free pro-H
group G, where H is an extension-closed pseudovariety of groups.
Then H is itself a free pro-H group.
130 / 245
Proof of Corollary 12.11.
Since the pro-H metric of a clopen subgroup is the induced metric, we may as
well assume that H is a free factor of G. Let (hn)n be a sequence of elements
of H and suppose that it converges in G to an element g. Suppose H is
another subgroup of G such that G is the free product of H and H . Then, by
considering the identity mapping on H and sending H to 1 we obtain an onto
homomorphism ϕ : G → H which is obviously continuous with respect to the
pro-H metrics of G and H. Hence (hn)n already converges in H, namely to
ϕ(g). Since the metrics dH and dG have the same Cauchy sequences in H by
Theorem 12.10, the limit must be the same in both cases, and so g ∈ H. This
shows that H is closed in the pro-H metric of G.
Proof of Corollary 12.12.
Let A be a finite free generating set for G. Let G be the subgroup of G
discretely generated by A. Then G is a free group over A in the variety
generated by H and it is a dense subgroup of G. Let H = H ∩ G . Then H is
a clopen subgroup of G in the pro-H topology of G . Since H is open, H is
dense in H. Hence H is the completion of H with respect to the metric dG .
Applying Theorem 12.10 to the free factor H of itself, it follows that H is a
free pro-H group.
131 / 245
Outline
σ-fullness
σ-reducibility of the V-separation problem
pro-V-metrics
Inverse automata
V-invertibility of endomorphisms
Computing closures of finitely generated
subgroups
The Pin-Reutenauer procedure
132 / 245
The free group and inverse automata
Let now G be a free group on a finite set A. To each finite subset X of G we
associate a finite inverse automaton as follows.6
For each reduced group word representative w of an element of X,
consider a linear graph with directed edges labeled by the successive
letters of w, the edge appearing in the direction of left-to-right reading of
w if the corresponding generator appears with exponent 1 and in the
opposite direction if the exponent is −1. Thus the label of the undirected
path which traverses the graph in the direction of left-to-right reading
of w is w.
Glue these graphs together by identifying their ends to a single vertex v0
which is the unique initial and final state of the automaton.
Fold edges so that the resulting automaton becomes inverse in the sense
that the transformations defined by the labels are partial bijections. This
can be done by applying the following procedure, in an arbitrary order,
until it no longer applies: whenever we encounter two edges with the
same label leaving from the same state or arriving at the same state, we
identify them.
6
See [Sta83, MSW01, KM02] for details and further references.
133 / 245
Example 1
Let G be the free group on the free generators a, b, c and let
X = {ab−1c−1a, a−1b−1ac−1a, bc−1a}. Then the sequence of pictures in Figure 1
describes the construction of the folded inverse automaton associated with X.
◦ ◦
◦ ◦
◦ ◦
a b
c
a
a b a
c
a
b
c
a
◦◦
◦ a
b
c
aa
b
a
c a
b
c
a
◦
◦ a
b
caa
b
a c a
b
c
a
◦
◦
a
b
c
b
a c a
b
c
a
◦
◦
ab
c
a
b
a c
b
c
ab
c a
b
a
b
Figure: The folding procedure
134 / 245
The automaton resulting from the above procedure is reduced
in the sense that it has a unique initial state which is
simultaneously the unique final state, every state is accessible
from it (through an undirected path), and there is no state of
degree 1 other than possibly the initial and final state.
The set of reduced group words recognized by the automaton
is precisely the subgroup X generated by X.
Moreover, this automaton is unique up to isomorphism and it
depends only on the subgroup X and not on the specific
generating set X. Thus, for a finitely generated subgroup H of
the free group G on a set A, we will denote its automaton
by A(H).
Conversely, a given finite reduced inverse automaton A over
the alphabet A recognizes a finitely generated subgroup of the
free group on A whose associated automaton is A. This
subgroup is the fundamental group of the underlying graph.
135 / 245
The following result summarizes the properties of the construction
of the automaton associated with a finitely generated subgroup of
a free group.
Theorem 13.1
The correspondence which maps each finitely generated subgroup
H of the free group G on the set A to its automaton A(H),
constructed from a finite generating set of H, has the following
properties:
1. the automaton A(H) is effectively constructible and does not
depend on the generating set but only on H;
2. the correspondence defines a bijection between the set of all
finitely generated subgroups of G and the set of all finite
reduced inverse automata with input alphabet A.
136 / 245
Example 2
We recall the procedure to compute the fundamental group
of a connected labeled directed graph with a root vertex,
namely to exhibit a finite generating set for that subgroup.
First, choose a generating tree, that is a maximal subgraph
whose underlying undirected graph is a tree. Note that every
vertex of the original graph is on the tree. To each edge e
which is not on the chosen tree, associate the group word
which is obtained by reading the label of the (undirected)
path which goes from the root along the tree to the beginning
vertex of e, then follows e, and then returns to the root
along the tree. The set of all words associated in this way
to the edges which are not on the tree generates a subgroup
of the free group on the labels which is called the fundamental
group of the labeled graph. This procedure is shown
here for the inverse automaton obtained in the preceding example.
The resulting generating set for the same subgroup,
namely the subgroup recognized by the inverse automaton,
is {a−1
ca−1
ba, ba−1
ba, ab−1
a−1
ba}. The set thus obtained
freely generates the subgroup. This also gives a procedure
to compute free generators for the subgroup of a free group
generated by a given finite set of group words.
ab
a
b
a c
b
ab
a
b
a c
b
ab
a
b
a c
b
a−1
· c · a−1
ba
ab
a
b
a c
b
b · a−1
ba
ab
a
b
a c
b
a · b−1
a−1
ba
137 / 245
We proceed to explore some other relationships between inverse
automata and finitely generated subgroups of free groups.
Let A and B be two reduced inverse automata with the same input
alphabet A. A morphism f : A → B is a function which maps states of A
to states of B, sending the initial state of A to that of B, in such a way
that the action of A is respected:
if q is a state of A, a ∈ A ∪ A−1
, and qa is defined, then f (q)a is
also defined and f (q)a = f (qa).
Note that if such a morphism exists then it is unique.
Proposition 13.2
Let G be a free group and let H and K be finitely generated subgroups
of G. Then H ⊆ K if and only if there is an automaton morphism from
A(H) into A(K). Moreover, if the morphism is injective then H is a free
factor of K.
138 / 245
Proof.
Suppose first that there exists an automaton morphism A(H) → A(K). A
reduced group word w representing an element of H labels a successful path
in A(H). By transforming this path by the morphism, we obtain a successful
path in A(K), which shows that w also represents an element from K. Hence
H ⊆ K.
Conversely, suppose that H ⊆ K. We may choose finite sets X and Y of
reduced words such that X = H and X ∪ Y = K. Then, the construction of
A(H) and A(K) proceeds from sets of linear automata in which the first is
contained in the second. This implies that every identification which is made to
obtain A(H) will also occur in the construction of A(K). Hence there is a
morphism A(H) → A(K).
Suppose next that there is an injective morphism A(H) → A(K). Choose for
A(H) a generating tree. Its image in A(K) is still a tree and so it can be
expanded to a generating tree of A(K). Hence there is a free generating set for
K which contains a free generating set for H and this is equivalent to H being
a free factor of K.
139 / 245
Let A be an inverse automaton. A congruence on A is an
equivalence relation ∼ on the state set of A which is compatible
with the action of the input alphabet A:
if q1, q2 are states, a ∈ A ∪ A−1, q1a, q2a are both defined,
and q1 ∼ q2, then q1a ∼ q2a.
We may then consider the quotient automaton A/∼, whose states
are the ∼-classes of states of A and such that the action of A is
given by (q/∼)a = (qa)/∼. Note that A/∼ is an inverse
automaton.
140 / 245
Lemma 13.3
Let H and K be finitely generated subgroups of the free group on
a finite set A and suppose that H ⊆ K. For each state p, choose a
reduced word up which labels a path in A(H) from the initial state
to p. Then the congruence ∼H,K on A(H) determined by the
kernel of the unique morphism ϕ : A(H) → A(K) satisfies the
following condition:
for all states p, q, p ∼H,K q if and only if upu−1
q ∈ K. (2)
Moreover, if L is the fundamental group of the quotient automaton
A(H)/∼H,K , then H ⊆ L and L is a free factor of K.
141 / 245
Proof.
If upu−1
q ∈ K, then up and u−1
q label paths in A(K) from the
initial-final state to the states ϕ(p) and ϕ(q). Since A(K) is an
inverse automaton which recognizes K, it follows that
ϕ(p) = ϕ(q), that is p ∼H,K q. Conversely, if p ∼H,K q, then
ϕ(p) = ϕ(q) and so the reduced form of upu−1
q labels a loop at
the initial-final state in A(K), that is upu−1
q ∈ K. This proves
condition (2). The last part of the statement of the lemma follows
from Proposition 13.2.
142 / 245
Proposition 13.4
Let H be a finitely generated subgroup of the finitely generated
free group G on a finite set A, which is endowed with the pro-V
topology. Then the following hold:
1. if H is a clopen normal subgroup then A(H) is a permutation
automaton whose transition monoid is isomorphic to G/H and
belongs to V;
2. H is clopen if and only if A(H) is a permutation automaton
whose transition monoid belongs to V.
143 / 245
Proof.
By Lemma 12.3, if H is a clopen normal subgroup then G/H ∈ V. The
Cayley graph of the finite group G/H with respect to A can be viewed as
a reduced inverse automaton which recognizes H as the set of reduced
group words which label loops at the vertex 1. Hence it is isomorphic to
A(H) and A(H) is a (complete) permutation automaton. The states in
the Cayley graph are precisely the cosets of H, on which the input
alphabet acts by right translation. Hence the transition monoid is
isomorphic to G/H and it belongs to V.
Next we assume only that H is clopen. By Lemma 12.3, HG is a clopen
normal subgroup. The quotient automaton A(HG )/∼HG ,H embeds
in A(H). Since A(HG ) is a complete automaton by (1), so is its quotient
A(HG )/∼HG ,H . Since A(H) is a reduced inverse automaton, it follows
that A(H) is also a permutation automaton as there is no room in
A(HG )/∼HG ,H to add vertices or edges. The transition monoid of A(H)
is therefore a quotient of that of A(HG ), which is isomorphic to G/HG
by (1), and therefore it belongs to V.
144 / 245
(. . . )
Conversely, suppose that A(H) is a permutation automaton whose
transition monoid M belongs to V and consider the natural
homomorphism ϕ : G → M and K = ϕ−1
(1). Then K consists of all
reduced words which map every state of A(H) to itself while H consists
of all reduced words which map the state 1 to itself. Hence K ⊆ H and
H is clopen since K is clopen by Lemma 12.3.
145 / 245
A simple application of Proposition 13.4 is the following theorem
due to M. Hall [Hal50] in a paper which first introduced profinite
topologies on free groups.
Theorem 13.5
Every finitely generated subgroup of a free group G on a finite
set A is closed in the profinite metric of G.
146 / 245
Proof.
Let H be a finitely generated subgroup of G. If H = G, then of course H
is closed. Otherwise, it suffices to show that, for every reduced word
g ∈ G \ H, there is a clopen subgroup which contains H but not g.
Consider the automaton A(H) and add to it, starting from the
initial-final state, a linear automaton which reads g. By applying the
folding procedure, we end up with an inverse automaton, which may not
be reduced, in which the end state of the added linear automaton is not
identified to the initial-final state. Each generator a ∈ A determines in
this automaton a partial permutation of the state set. Now, every partial
permutation of a finite set may be completed to a full permutation and
we choose such a completion for each generator a ∈ A. This leads to a
permutation automaton B in which A(H) embeds. By Proposition 13.4,
the fundamental group K of B is a clopen subgroup of G. By
Proposition 13.2, K contains H. On the other hand, g /∈ K since in B
the reduced word g does not label a loop at the initial-final state.
147 / 245
Note 13.6
An alternative proof of Theorem 13.5 is obtained as follows.
Complete the automaton A(H) of the given finitely generated
subgroup of G to a permutation automaton B, with the same
initial-final state. By Proposition 13.4, the fundamental group K
of B is a clopen subgroup. By Proposition 13.2, H is contained
in K. By Corollary 12.11, since G is extension closed, H is closed.
148 / 245
Example 3
In Example 1 we obtained the first inverse automaton in Figure 2
1
2
3
45
ab
a
b
a c
b
1
2
3
45
ab
a
b
a c
b
a
a
b
b
c
c
c
c
Figure: An inverse automaton and one of its completions
which gives the partial permutations defined in the table on the left and one of their
possible completions to permutations in the table on the right
1 2 3 4 5
a 2 − − 1 3
b 3 − 2 − 4
c − − − 3 −
1 2 3 4 5
a 2 4 5 1 3
b 3 1 2 5 4
c 1 2 4 3 5
and the corresponding permutation automaton in Figure 2. This permutation
automaton determines a clopen subgroup K, in the profinite metric of the free group,
of which the original subgroup is a free factor.
149 / 245
More generally, we say that a finitely generated subgroup H of the free
group G on the finite set A is V-extendible if A(H) can be extended to a
permutation automaton whose transition monoid belongs to V. In such
an extension, both states and transitions may be added.
Lemma 13.7
The finitely generated subgroup H of the free group G on a finite set A is
V-extendible if and only if there is a clopen subgroup K of G, in the
pro-V metric of G, such that the congruence ∼H,K on A(H) is the
equality.
Proof.
If H is V-extendible, then there is a permutation automaton B containing
A(H), with the same initial-final state, whose transition monoid belongs
to V. By Proposition 13.4, the fundamental group K of B is clopen in
the pro-V metric of G. Then A(H) embeds in A(K) and so, by definition
of the congruence ∼H,K (cf. Lemma 13.3), this congruence is the equality
relation on the state set of A(H). The converse is proved similarly.
150 / 245
By definition of pro-V metric, the closure of a subgroup of a group
G is the intersection of the clopen subgroups that contain it. In
the case of finitely generated subgroups of a finitely generated free
group, we can use the previous results to obtain a more precise
statement.
Proposition 13.8
Let H be a finitely generated subgroup of the free group G on a
finite set A, which is endowed with the pro-V metric, and let H be
the closure of H in G. Then the following hold:
1. there is a clopen subgroup K of G such that ∼H,H coincides
with ∼H,K ;
2. there is a smallest V-extendible subgroup containing H,
namely the subgroup ˜H such that A(˜H) is the image of A(H)
in A(H);
3. H ⊆ ˜H ⊆ H and ˜H is a free factor of H.
151 / 245
Proof.
By Proposition 13.2, for each clopen subgroup K containing H,
there is a morphism A(H) → A(K), which determines a
congruence on A(H). The intersection ∼ of all such congruences
is still a congruence on A(H). Since the automaton A(H) is finite,
the intersection ∼ involves only finitely many congruences and so
A(H)/∼ is the largest quotient of A(H) which embeds in a
permutation automaton of a clopen subgroup. The fundamental
group of A(H)/∼ is therefore a finitely generated subgroup L
containing H which is a free factor of the clopen subgroup K,
whose automaton A(K) is the smallest permutation automaton in
which A(L) embeds and which has a transition monoid in V. This
proves the proposition.
152 / 245
The following result reduces the computation of ˜H (and therefore also
the question as to whether H is V-extendible) to the membership
problem of the pro-V closure H.
Proposition 13.9
Let G be a finitely generated free group, endowed with the pro-V metric,
and let H be a given finitely generated subgroup of G. If the membership
problem for H is decidable then one can effectively compute the smallest
V-extendible subgroup ˜H of G containing H.
Proof.
By Proposition 13.8, it suffices to compute the congruence ∼H,H on the
automaton A(H). By condition (2) of Lemma 13.3, this congruence can
be computed by the choice of a label uq for a path from the initial-final
state to each state q by using the solution of the membership problem
for H.
Thus, one may concentrate on the membership problem for the closure
subgroup H.
153 / 245
Proposition 13.8 is insufficient to guarantee the existence of an algorithm
to compute the closure H of a given finitely generated subgroup H. In
case V is an extension-closed pseudovariety, we obtain some more precise
results.
Theorem 13.10
Let H be a finitely generated subgroup of a finitely generated free group,
which is endowed with the pro-V metric for an extension-closed
pseudovariety V. The following conditions are equivalent:
1. H is closed;
2. H is V-extendible;
3. H is a free factor of a clopen subgroup.
Proof.
By Proposition 13.8, (1) implies H = ˜H = H which yields (2) since ˜H is
V-extendible. Condition (2) implies (3) by Proposition 13.2. Finally, (3)
implies (1) by Corollary 12.11.
154 / 245
Corollary 13.11
Under the hypotheses of Theorem 13.10, ˜H = H.
Exercise 13.12
Let G be a finitely generated free group and endow it with the
pro-V metric. Let H be a finitely generated subgroup of G. Prove
the following:
1. for every g ∈ G, the automaton A(g−1Hg) is obtained by
modifying A(H) as follows: if the initial-final state of A(H) is
q0 then set that of A(g−1Hg) to be the state q0g;
2. H is V-extendible if and only if all its conjugates are
V-extendible;
3. H is closed (respectively open) if and only if all its conjugates
have the same property.
155 / 245
Outline
σ-fullness
σ-reducibility of the V-separation problem
pro-V-metrics
Inverse automata
V-invertibility of endomorphisms
Computing closures of finitely generated
subgroups
The Pin-Reutenauer procedure
156 / 245
Relative invertibility of endomorphisms
Given a continuous endomorphism ϕ of ΩnM, we denote by
M(ϕ) the n × n-matrix over the profinite ring ˆZ whose
(i, j)-coordinate is the image of ϕ(xi ) of the i-th generator
of ΩnM under the unique continuous homomorphism
ΩnM → ˆZ which maps xj to 1 and all other generators to 0.
The determinant and trace of the matrix M(ϕ) are also called,
respectively, the determinant and trace of ϕ and are denoted
det ϕ and tr ϕ.
Exercise 14.1
Let M be a profinite monoid. Show that m ∈ M is invertible if and
only if m is right invertible, if and only if m is left invertible, if and
only if mω = 1.
157 / 245
For a metric semigroup S, denote by End S the monoid of
continuous endomorphisms of S.
For a pseudovariety V of monoids and w ∈ ΩnM, denote by
wV the restriction of the implicit operation w to V.
For ϕ ∈ End ΩnM, denote by ϕV the continuous
endomorphism of ΩnV induced by ϕ, which maps the
generator xi to (ϕ(xi ))V.
Say that ϕ is V-invertible if ϕV is invertible in End ΩnV.
Proposition 14.2
A continuous endomorphism ϕ of ΩnM is V-invertible if and only
if ΩnV is generated by the set {ϕV(xi ) : i = 1, . . . , n}.
158 / 245
Proof.
Let M be the (closed) submonoid of ΩnV generated by
{ϕV(xi ) : i = 1, . . . , n}.
Suppose first that ϕ is V-invertible. Then (ϕω)V = (ϕV)ω is the
identity mapping on ΩnV. Given u ∈ ΩnV, letting w = ϕω−1
V (u),
we conclude that
u = ϕV(w) = ϕV wΩAV(x1, . . . , xn) = wΩAV ϕV(x1), . . . , ϕV(xn) ,
where the last equality is justified since implicit operations on V
commute with continuous homomorphisms between pro-V
semigroups. Since w is the limit of a sequence of words, it follows
that u ∈ M, which shows that M = ΩnV.
159 / 245
(. . . )
Conversely, suppose that M = ΩnV. Given u ∈ ΩnV, there exists a
sequence of words (wn)n such that
u = lim
n→∞
(wn)ΩnV ϕV(x1), . . . , ϕV(xn) = lim
n→∞
ϕV(wn).
Since ΩnM is a compact metric space, we may assume that the
sequence (wn)n converges to some w ∈ ΩnM. For such an implicit
operation w, we have ϕV(w) = u. In particular, for each generator
xi there exists vi ∈ ΩnM such that xi = ϕV(vi ). Let ψ be the
continuous endomorphism of ΩnM which maps xi to vi . Then the
composite continuous endomorphism ϕV ◦ ψV fixes the generators
xi and, therefore it is the identity mapping of ΩnV. Hence ϕV is
invertible.
160 / 245
Let Ab denote the pseudovariety of all finite Abelian groups.
Let Am denote the pseudovariety of all finite Abelian groups
of exponent m.
Proposition 14.3
The following conditions are equivalent for a continuous
endomorphism ϕ of ΩnM and a prime integer p:
1. ϕ is Gp-invertible;
2. ϕ is Ap-invertible;
3. det ϕ is not divisible by p.
161 / 245
Proof.
Since Ap ⊆ Gp, clearly (1)⇒(2). On the other hand, (2)⇔(3)
follows from elementary Linear Algebra since ΩnAp is the additive
reduct of the n-dimensional vector space over the field Z/pZ. We
prove (2)⇒(1) by contraposition and so we assume that ϕ is not
Gp-invertible. Then, by Proposition 14.2, the set
{ϕGp (xi ) : i = 1, . . . , n} generates a proper closed subgroup H
of ΩnGp. Since ΩnGp is a profinite group, it follows that H is
contained in some proper clopen subgroup K of ΩnGp. Hence
there is a continuous homomorphism ψ : ΩnGp → F onto a finite
p-group F such that ψ(H) is the trivial subgroup. We may assume
that ψ is the restriction mapping ΩnGp → ΩnAp, from which we
deduce that ϕAp is the trivial endomorphism of ΩnAp and,
therefore, it is not Ap-invertible.
162 / 245
Exercise 14.4
Show that the following conditions are equivalent for an element u
of the ring ˆZ:
1. u is multiplicatively invertible (or a unit);
2. no prime integer divides u;
3. u is invertible in each p-adic completion Zp.
Hence, if u ∈ Z, then u is invertible in ˆZ if and only if u = ±1.
163 / 245
Outline
σ-fullness
σ-reducibility of the V-separation problem
pro-V-metrics
Inverse automata
V-invertibility of endomorphisms
Computing closures of finitely generated
subgroups
The Pin-Reutenauer procedure
164 / 245
Here is a first result with an algorithmic flavour towards the
computation of the closure of a finitely generated subgroup of the
free group.
Proposition 15.1
Let V be a non-trivial extension-closed pseudovariety of groups and
let G be a finitely generated free group which is endowed with the
pro-V metric. Suppose that a finitely generated subgroup H of G
is not dense in G and let ϕ : G → F be a homomorphism onto
F ∈ V such that ϕ(H) F. Then one can compute from ϕ a
closed finitely generated free factor L of some clopen subgroup K
of G such that A(L) is a quotient of the automaton A(H).
165 / 245
Proof.
Put K = ϕ−1
ϕ(H) . Then K is a clopen subgroup of finite index in G.
Consider the congruence ∼H,K on the inverse automaton A(H) and let L
be the finitely generated subgroup of G such that A(L) A(H)/∼H,K .
By Lemma 13.3, L is a free factor of K. By Corollary 12.11, L is a closed
subgroup of G.
It remains to argue that all constructions are effective. Given the finite
group F and the onto homomorphism ϕ, and the free generating set A
of G, consider the right action of A on the set F/ϕ(H) of all right cosets
of ϕ(H). This defines a permutation automaton which is precisely the
automaton A(K). Given H by means of a finite set of generators, one
may also construct its automaton A(H). The construction of the
quotient automaton A(H)/∼H,K then can be made from the knowledge
of both automata A(H) and A(K). The quotient automaton in turn
determines the closed subgroup L, for which we may exhibit a finite set of
generators.
166 / 245
Definition 15.2
We say that a pseudovariety V of groups has decidable denseness if,
given a finite set A and a finite subset B of the free group G on A, it is
decidable whether B generates a dense subgroup in the pro-V metric
of G.
The following theorem summarizes and completes some of the above
results.
Theorem 15.3
Let V be an extension-closed pseudovariety of groups. Let H be a finitely
generated subgroup of the finitely generated free group G and let H be
the closure of H in the pro-V metric of G.
1. The group H is finitely generated and a free factor of a clopen
subgroup of G.
2. The automaton A(H) is a quotient of A(H).
3. If V is recursively enumerable and has decidable denseness then
there is an algorithm to construct a finite set of generators of H.
167 / 245
Proof.
By Corollary 13.11, the subgroup H coincides with ˜H, which in turn is
finitely generated by Proposition 13.8. The remainder of the statement
of (1) is a direct consequence of Theorem 13.10 while (2) now also
follows from Proposition 13.8.
It remains to prove (3). Let A be a set of free generators for G. Here is
how the algorithm proceeds. Since V has decidable denseness, we first
check whether H is dense in G. In the affirmative case, we have found H
to be G. In the negative case, we know that there is some
homomorphism ϕ : G → F onto some group F in V such that
ϕ(H) G. Since V is recursively enumerable and G is finitely generated,
we may successively enumerate candidates to such homomorphisms until
we find one with this property.
Once such a homomorphism is found, by Proposition 15.1 one can
compute from ϕ a finite set A = {v1, . . . , vr } of free generators for a
closed free factor L of some clopen subgroup K of G such that A(L) is a
quotient A(H)/∼1 of A(H).
168 / 245
(. . . )
If {w1, . . . , wm} is a set of generators for H, then we may express each wi
as a group word wi (v1, . . . , vr ) on the groups words vj . Consider the
subgroup H of the free group G on the set A generated by
{w1, . . . , wm}. The mapping which sends each free generator vj to itself,
viewed as a group word in the given free generators of G, extends
uniquely to a continuous homomorphism ψ : G → G which is an
isomorphism with L. Since the induced metric on L is the pro-V metric
of L by Theorem 12.10, ψ : G → L is a continuous isomorphism with
respect to the corresponding pro-V topologies. Since ψ preserves the
index of subgroups, as well as quotients for normal subgroups, ψ is an
isomorphism of topological groups. Since L is closed in G by
Corollary 12.11, the problem of computing the closure of H in G is thus
reduced to the computation of the closure of H in G .
169 / 245
(. . . )
Now, if we apply the above procedure to H as a subgroup of G , either
H is dense in G , in which case we conclude that H = L, or we obtain a
free factor L of a clopen subgroup K of G such that
H ⊆ L ⊆ K G and AA (L ) is a quotient of AA (H ). It follows that
H ⊆ ψ(L ) ⊆ ψ(K ) L, ψ(L ) is a free factor of the clopen subgroup
ψ(K ) (of G). Moreover, it is easy to see that A ψ(L ) is the quotient
of A(H) by a congruence ∼2. Since H ⊆ ψ(L ) L, the congruence ∼2
is properly contained in ∼1.
Thus, applying the above procedure recursively, in a finite number of
steps we must obtain an affirmative answer to the question as to whether
the current subgroup is a free factor of the current free group. At that
stage, the closure will be computed and then it is a matter of substituting
back the free generators to their expressions in the original alphabet A to
obtain H.
170 / 245
Corollary 15.4
Let V be an extension-closed pseudovariety of groups with
decidable denseness. Then it is decidable whether a given finitely
generated subgroup of a finitely generated free group is
V-extendible.
Since the closure of a finitely generated subgroup is computed
by successively taking closed factors of clopen subgroups,
combining with Theorem 12.10, we also obtain the following
result.
Corollary 15.5
Let H be a finitely generated subgroup of a finitely generated free
group G and suppose that H is closed with respect to the pro-V
metric of G, where V is an extension-closed pseudovariety of
groups. Then the completion of H with respect to the restriction
to H of the pro-V metric of G is a free pro-V group.
171 / 245
We consider the special case of the extension-closed
pseudovariety Gp for a prime integer p, for which the
denseness test can be done efficiently.
The next result may now be deduced from Proposition 14.2
and Proposition 14.3.
For group words w1, . . . , wm on n letters x1, . . . , xn, let
M(w1, . . . , wm) be the (integer) matrix whose (i, j)-entry is
the exponent of the reduced word in xj which is obtained from
wi by replacing by 1 all xk with k = j.
In particular, when m = n, M(w1, . . . , wn) is the matrix of the
continuous endomorphism of ΩnM which is determined by the
implicit operator defined by the group terms w1, . . . , wn.
172 / 245
Proposition 15.6
Let G be a free group on n free generators and let
H = w1, . . . , wn be an n-generated subgroup of G. Then H is
dense in G if and only if M(w1, . . . , wn) is invertible mod p.
Proof.
By Baumslag’s Theorem asserting that the free group is residually
in Gp, we may regard G as the subgroup of ΩnGp generated by
{x1, . . . , xn}. Since the pro-Gp metric of G is the induced metric
from the metric of ΩnGp by Proposition 12.1, H is dense in G if
and only if it is dense in ΩnGp.
On the other hand, by Proposition 14.2, if H = w1, . . . , wn , then
H is dense in ΩnGp if and only if the associated implicit operator
(w1, . . . , wn) is Gp-invertible. By Proposition 14.3, the latter
condition is equivalent to the integer matrix M(w1, . . . , wn) being
invertible mod p.
173 / 245
Finally, the next result improves the general-purpose algorithm
in the proof of Theorem 15.3 by providing the means to
compute efficiently a proper clopen subgroup containing a
given non-dense finitely generated subgroup.
Proposition 15.7
Let H be a finitely generated subgroup of the free group G on n
free generators x1, . . . , xn and let {w1, . . . , wm} be generating
subset of H. Let A = (Z/pZ)n and consider the homomorphism
ϕ : G → A which sends xi to (0, . . . , 0, 1, 0, . . . , 0), where 1 is in
the ith position.
1. The subgroup H is dense in the pro-Gp metric of G if and
only if, mod p, the matrix M(w1, . . . , wm) has rank n.
2. If, mod p, the submatrix M(wr1 , . . . , wrn ) has rank n, then the
subgroup wr1 , . . . , wrn is dense.
3. If, mod p, the matrix M(w1, . . . , wm) has rank less than n,
then ϕ−1ϕ(H) is a proper clopen subgroup of G containing H.
174 / 245
Proof.
Since Z/pZ is a field, a square matrix with entries in it is invertible
if and only if the matrix has rank n. Moreover, an m × n matrix
has rank n if and only if it contains n rows whose corresponding
submatrix has rank n. On the other hand, since ϕ(H) is generated
by the rows of the matrix M(w1, . . . , wm), with the entries viewed
in Z/pZ, if, mod p, this matrix has rank less than n, then ϕ(H) is
a proper subgroup of the group A ∈ Gp. This proves (3) and shows
that H is not dense in G. The statements (1) and (2) now follow
using Proposition 15.6.
Thus, for the pro-Gp metric of a finitely generated free group
G, combining part (3) of Proposition 15.7 and
Proposition 15.1, one may compute a proper clopen subgroup
containing a given finitely generated subgroup H which is not
dense in G.
175 / 245
To illustrate the above algorithms, we present an example in detail. For this purpose,
we consider again the subgroup H of the free group G on the free generators a, b, c of
Example 1: H is generated by the group words ab−1c−1a, a−1b−1ac−1a, bc−1a. The
corresponding integer matrix is
M0 =


2 −1 −1
1 −1 −1
1 1 −1


and has determinant 2. Hence H is dense in G with respect to the pro-Gp metric for
every odd prime p. For the pro-G2 metric of G, the rank of the matrix M0 mod 2 is 2.
More precisely, if ϕ0 : G → (Z/2Z)3 is the appropriate mapping given by
Proposition 15.7, then H ⊆ ϕ−1
0 ϕ0(H) G. The clopen subgroup ϕ−1
0 ϕ0(H) may be
computed as the fundamental group of the automaton which represents the action of
a, b, c on the right of the right cosets of ϕ0(H), which is represented in Figure 3.
ϕ0(H) ϕ0(H)(0, 1, 0)
b, c
b, c
a a
Figure: The automaton of K1
The clopen subgroup K1 in question is therefore freely generated by
{a, bab−1, b2, bc, cb−1}. The free factor L1 is obtained by taking the fundamental
group of the image of A(H) in A(K1). Recall the automaton A(H) as given in
Figure 177.
176 / 245
1
2
3
45
ab
a
b
a c
b
Figure: The automaton A(H)
The states 1, 2, 4 are mapped to ϕ(H) while 3, 5 are mapped to ϕ(H)(0, 1, 0) and the
only missing edge from the automaton of A(K1) is the edge c from the state
ϕ(H)(0, 1, 0) to ϕ(H), which corresponds to the generator bc of K1. Hence L1 is the
subgroup generated by {a, bab−1, b2, cb−1}. Let b1 = bab−1, b2 = b2 and
c1 = cb−1. Then the elements of H may be expressed as follows:
ab−1
c−1
a = ab−1
2 c−1
1 a
a−1
b−1
ac−1
a = a−1
b−1
2 b1
bc−1
a = c−1
1 a
which are now viewed as generating a subgroup H1 of the free group G1 on the set
a, b1, b2, c1. The matrix corresponding to the generators of H1 is
M1 =


2 0 −1 −1
−1 1 −1 0
1 0 0 −1


which, mod 2, has rank 3. Hence H is not dense in L1 and we need to compute a
clopen subgroup K2 of L1 and a free factor L2 of K2 containing H. 177 / 245
Since the rank of M1 mod 2 is 3, the image of H1 under the homomorphism
ϕ1 : G1 → (Z/2Z)4 has index 2 and again we obtain a 2-state permutation automaton
for K2, which is represented in Figure 5.
ϕ1(H1) ϕ1(H1a)
a, b2, c1
a, b2, c1
b1 b1
Figure: The automaton of K2
To obtain the image of A(H1) in this automaton, it suffices to read through each of
the generators of H1, starting from the initial state, and keeping only the states and
edges which are used. Figure 6 represents the subautomaton which is thus obtained,
whose fundamental group is the required free factor L2 of K2.
178 / 245
ϕ1(H1) ϕ1(H1a)
a, b2
a, c1
b1
Figure: The automaton of L2
Choosing the edge labeled b2 for the generating tree, we obtain the following free
generators for L2:
b1, a1 = ab−1
2 , a2 = b2a, c2 = b2c1. (3)
In terms of these generators, the expressions for the generators of H1 are the following:
ab−1
2 c−1
1 a = a1c−1
2 a2
a−1
b−1
2 b1 = a−1
2 b1
c−1
1 a = c−1
2 a2
The matrix of these generators with respect to the generators of L2 in the order given
by (3) is
M2 =


0 1 1 −1
1 0 −1 0
0 0 1 −1


which again has rank 3.
179 / 245
Proceeding as above, we get a canonical homomorphism ϕ2 : G2 → (Z/2Z)4, where
G2 is the free group on the generators b1, a1, a2, c2. Let H2 be the subgroup of G2
generated by a1c−1
2 a2, a−1
2 b1, c−1
2 a2. The new clopen subgroup K3 is the fundamental
group of the automaton in Figure 7.
ϕ2(H2) ϕ2(H2b1)
b1, a2, c2
b1, a2, c2
a1 a1
Figure: The automaton of K3
Figure 8 gives the subautomaton which is obtained by reading through the preceding
automaton the generators of H2.
ϕ2(H2) ϕ2(H2b1)
b1, a2, c2
a1
Figure: The automaton of L3
Choosing the edge labeled c2 for the generating tree, we obtain the following free
generators for L3:
a1, a3 = c−1
2 a2, b3 = c−1
2 b1. (4)
180 / 245
ϕ2(H2) ϕ2(H2b1)
b1, a2, c2
a1
a1, a3 = c−1
2 a2, b3 = c−1
2 b1.
The corresponding expressions for the generators of H2 are:
a1c−1
2 a2 = a1a3
a−1
2 b1 = a−1
3 b3
c−1
2 a2 = a3
whose matrix has rank 3 mod 2, 3 being also the rank of L3. Hence H2 is dense in L3
and the closure of H = ab−1c−1a, a−1b−1ac−1a, bc−1a in G is obtained by
substituting back in terms of a, b, c the expressions for the generators of L3 given
in (4):
a1 = a1 = ab−1
2 = ab−2
a3 = c−1
2 a2 = c−1
1 b−1
2 b2a = bc−1
a
b3 = c−1
2 b1 = c−1
1 b−1
2 b1 = bc−1
b−2
bab−1
= bc−1
b−1
ab−1
Since the generators of L3 are all recognized by A(H), we conclude that H is closed in
the pro-G2 metric of G.
181 / 245
In terms of generators, we obtained the following chain of subgroups approximating
the closure of H, where we also indicate on the right the corresponding congruences
on A(H) as given by the partitions of the state set:
G = a, b, c
∪
K1 = a, bab
−1
, b
2
, bc, cb
−1
∪
L1 = a, bab
−1
, b
2
, cb
−1
{1, 2, 4|3, 5}
∪
K2 bab
−1
, ab
−2
, b
2
a, b
2
cb
−1
, cb
−3
, b
3
ab
−3
, b
4
∪
L2 bab
−1
, ab
−2
, b
2
a, b
2
cb
−1
{1|2, 4|3, 5}
∪
K3 ab
−2
, bc
−1
a, bc
−1
b
−1
ab
−1
, b
2
ab
2
cb
−1
, babcb
−1
, b
2
cbcb
−1
, bc
−1
b
−2
acb
−1
∪
L3 ab
−2
, bc
−1
a, bc
−1
b
−1
ab
−1
{1|2|3|4|5}
H = ab
−1
c
−1
a, a
−1
b
−1
ac
−1
a, bc
−1
a
Exercise 15.8
Verify that the above calculations are correct.
182 / 245
The above calculations also show that H is not Gp-extendible for every odd prime p
while it is G2-extendible. An G2-extension of the automaton A(H) may be recovered
from our calculations. It is the permutation automaton associated with the following
clopen subgroup:
K = ab−2
, bc−1
a, bc−1
b−1
ab−1
,
b2
ab2
cb−1
, babcb−1
, b2
cbcb−1
, bc−1
b−2
acb−1
,
cb−3
, b3
ab−3
, b4
,
b2
a · cb−3
· (b2
a)−1
, b2
a · b3
ab−3
· (b2
a)−1
, b2
a · b4
· (b2
a)−1
,
bc, a · bc · a−1
,
b2
a · bc · (b2
a)−1
, b2
a · abca−1
· (b2
a)−1
.
Exercise 15.9
Explain in general how to compute a V-extension of a V-extendible finite inverse
reduced automaton, assuming the appropriate hypotheses on the extension-closed
pseudovariety of groups V.
183 / 245
One may calculate the following picture for A(K) and that the transition
monoid of this automaton is a group of order 128. Since it would be too
tedious to do it by hand, this calculation was carried out using some adequate
Mathematica routines for the symbolic computations and the package graphviz
for the drawing itself, which was then converted by hand to GasTeX for
readability. The numbering of states was chosen to facilitate the identification
of the subautomaton A(H). New edges and states are in red.
6
7
5
8
4
2
3
1
a
b
c
b
c
b
a
c
b
c
a
c
a
b
c
b
c
c
b
b
a
a
a
a
Figure: A G2-extension of A(H)
184 / 245
Exercise 15.10
Show that the above algorithms for the pseudovariety Gp (to test
denseness, to compute the closure, to exhibit a Gp-extension, if
one exists) require only polynomial time in the input, which may
be either a finite list of group words over a finite alphabet A, or the
reduced inverse automaton of the subgroup of the free group on A
that they generate. More precisely, estimate the time complexity of
the algorithms.
185 / 245
Outline
σ-fullness
σ-reducibility of the V-separation problem
pro-V-metrics
Inverse automata
V-invertibility of endomorphisms
Computing closures of finitely generated
subgroups
The Pin-Reutenauer procedure
186 / 245
The Pin-Reutenauer procedure
Let us consider again the problem studied by Pin and
Reutenauer [PR91]: given a regular language L ⊆ A+ and a
word w ∈ A+, decide whether w can be separated from L by a
G-recognizable language.
Since G is κ-reducible for the separation problem, the problem
is equivalent to deciding whether w ∈ clκ,G(L).
So, the idea is to compute the subset clκ,G(L) of the free
group Ωκ
AG.
Since L is regular, we may assume that it is given by some
regular expression.
As every finite subset of Ωκ
AG fullfullis closed and closure
behaves well with respect to union, the key question is how
the closure operator clκ,G( ) behaves well with respect to the
multiplication of subsets and the Kleene star operation.
187 / 245
In general, for an arbitrary pseudovariety V and implicit
signature σ, we have the inclusion
clσ,V(K L) ⊇ clσ,V(K) clσ,V(L), (5)
simply because the multiplication in Ωκ
AV is continuous.
Note: in a compact semigroup, the equality K L = K L holds.
For a subset X of a σ-algebra S, denote by S σ the
σ-subalgebra generated by X.
The analogue of (5) for Kleene star is the inclusion
clσ,V(L+
) ⊇ clσ,V(L) σ (6)
The proof of (6) is a bit more delicate and depends on the
following lemma.
188 / 245
Lemma 16.1
Let V be a pseudovariety of semigroups and let S be a pro-V
semigroup. Then the following evaluation mapping is continuous
for every positive integer n:
ΩnV × Sn
→ S
(w, s1, . . . , sn) → wS (s1, . . . , sn).
Proof.
Since V-implicit operations commute with continuous homomorphisms
between pro-V semigroups, in view of Proposition 5.1 it suffices to
consider the case where S ∈ V.
Note that ΩnV(S) is finite, say again by Proposition 5.1. Moreover,
when ΩnV and S are both finite, the continuity of the evaluation
mapping is trivial.
Since, in terms of implicit operations, the natural projection
ΩnV → ΩnV(S) is given by restriction, we deduce the general case.
189 / 245
The inclusion clσ,V(L) σ ⊆ clσ,V(L+
) follows from the next
proposition.
Proposition 16.2
Let V be a pseudovariety, σ and implicit signature, and L a subset
of Ωσ
AV. Then clσ,V(L+
) is a σ-subalgebra of Ωσ
AV.
Proof.
Let u ∈ ΩmS be an implicit operation from σ, and let v1, . . . , vm be
elements of clσ,V(L+
). There are sequences with the following properties:
a sequence (un)n, of words from {x1, . . . , xm}+
, converging
to u;
for each i ∈ {1, . . . , m}, a sequence (vi,n)n, of elements of L+
,
converging to vi .
For each n, the element (un)ΩAV(v1,n, . . . , vm,n) is a product of elements
from L+
and, therefore, also belongs to L+
. By Lemma 16.1, we have
lim(un)ΩAV(v1,n, . . . , vm,n) = uΩAV(v1, . . . , vm).
Hence uΩAV(v1, . . . , vm) belongs to clσ,V(L+
).
190 / 245
Theorem 16.3 (Pin and Reutenauer [PR91])
For the pseudovariety V = G, the signature σ = κ, and a regular
language L ⊆ A+, equality holds in both formulas (5) and (6).
Some comments on the proof:
The proof establishes a stronger result than (6), namely that
clκ,G(L+
) = L κ.
The main reason for not needing to use clκ,G(L) instead of L on the
right hand side is M. Hall’s Theorem 13.5.
The proof depends on several ingredients from language theory,
such as a theorem of Anissimov and Seifert, stating that the
rational7
subgroups of Ωκ
AG are the finitely generated subgroups,
and a theorem of Fliess, stating that the rational subsets of Ωκ
AG
form a Boolean algebra. (See [Ber79, Section III.2] —
http://www-igm.univ-mlv.fr/∼berstel/LivreTransductions/LivreTransductions.html.)
7
A subset of a monoid M is said to be rational if it can be obtained from the
empty set and the singleton subsets of M by using the operations of subset
multiplication and taking the submonoid X∗
generated by a subset X.
191 / 245
The theorem was initially deduced from a conjectured property of
free groups: that the product of finitely many finitely generated
subgroups of Ωκ
AG is closed in the pro-G metric.
This property follows from Ash’s Theorem on inevitable graphs
[Ash91] and was proved independently by Ribes and
Zalesski˘ı [RZ93], using profinite group theory.
The theorem was found as an approach to a conjecture of J. Rhodes
(known as the Rhodes Type II Conjecture), which it implies. Ash’s
Theorem on inevitable graphs was also proved to establish Rhodes’
conjecture. (See [HMPR91] for the original statement and the
history of this conjecture.)
The Rhodes Type II Conjecture, now theorem, may be stated as
follows [AS00a].
Theorem 16.4 (Rhodes Type II)
Let S be a finite semigroup and let A be a generating subset. Consider
the κ-subsemigroup T of S × Ωκ
AG generated by the pairs (a, a) (a ∈ A).
Then, for an element s ∈ S, (s, 1) ∈ T if and only if, for every finite
group G, and every subsemigroup U of S × G, which projects onto the
first component, (s, 1) ∈ U. 192 / 245
Other pseudovarieties for which the
Pin-Reutenauer procedure holds
We say that the Pin-Reutenauer procedure holds for a
pseudovariety V and an implicit signature σ if the following
equalities hold for all subsets L of Ωσ
AV:
clσ,V(K L) = clσ,V(K) clσ,V(L) (7)
clσ,V(L+
) = clσ,V(L) σ. (8)
Note that if the pseudovariety V contains N, then there is
always an implicit signature for which the Pin-Reutenauer
procedure holds (cf. Proposition 7.3), for example the trivial
signature { · }. But, this in general too small for the
pseudovariety to be full with respect to it.
193 / 245
In a sense at the other extreme, if we take σ to consist of all
(finitary) implicit operations, then Ωσ
AV = ΩAV and
clσ,V(L) = L is the closure of L in ΩAV. So, the equality (7)
certainly holds in this case, by compactness of ΩAV. On the
other hand, clσ,V(L+) is the closure of a subsemigroup,
whence a closed subsemigroup of ΩAV, namely the closed
subsemigroup generated by L, which is therefore contained
in clσ,V(L) σ. The reverse inclusion is given by
Proposition 16.2.
Hence, for every pseudovariety V, there is some implicit
signature for which the Pin-Reutenauer procedure holds and V
is σ-full. The question is whether it holds for small such
signatures, such as κ.
The other key question is under what conditions one can turn
the Pin-Reutenauer procedure into an algorithm to test
membership of a given word w ∈ L in the closure clσ,V(L) of a
given regular language L ⊆ A+.
194 / 245
Here are some recent results.
Theorem 16.5 (JA-JCCosta-MZeitoun)
Suppose that V and W are σ-full pseudovarieties of semigroups
such that V ⊆ W. If the Pin-Reutenauer procedure holds for W
then it also holds for V.
Theorem 16.6 (JA-JCCosta-MZeitoun)
The Pin-Reutenauer procedure holds for A in the signature κ.
As was already mentioned, the same authors proved that A
and R are κ-full. Hence the preceding two theorems yield the
following result.
Corollary 16.7
The Pin-Reutenauer procedure holds for R in the signature κ.
195 / 245
Part III
Relatively free profinite semigroups
and Symbolic Dynamics
196 / 245
Outline
Semigroups of implicit operators
Complexity
Complexity of pseudowords generated by
iteration of substitutions
Entropy
197 / 245
Semigroups of implicit operators
Let wi ∈ ΩnS be an n-ary implicit operation for each
i ∈ {1, . . . , n}.
Given a profinite semigroup S, the n-tuple induces a
continuous mapping
[w1, . . . , wn]S : Sn
→ Sn
(s1, . . . , sn) → (w1)S (s1, . . . , sn), . . . , (wn)S (s1, . . . , sn) .
The composition of two such transformations of Sn is again a
transformation of the same form, and thus they constitute a
semigroup, which we call the semigroup of n-ary implicit
operators of S and denote On(S).
In particular, we may iterate an implicit operator
f = [w1, . . . , wn]S by considering its successive powers
f , f 2, f 3, . . ..
198 / 245
The following result is immediate from the commutation of
implicit operations with comtinuous homomorphisms between
profinite semigroups.
Lemma 17.1
Let w1, . . . , wn ∈ ΩnS be n-ary implicit operations and let
ϕ : S → T be a continuous homomorphism between profinite
semigroups. Then the following diagram commutes:
Sn [w1,...,wn]S
GG
ϕn

Sn
ϕn

Tn [w1,...,wn]T
GG Tn.
199 / 245
Lemma 17.2
Let S be a profinite semigroup and let f ∈ On(S) be an n-ary
implicit operator on S. Then, for every (s1, . . . , sn) ∈ Sn, the
sequence f k!(s1, . . . , sn) k
of elements of Sn converges. In other
words, the sequence (f k!)k of transformations of Sn converges
pointwise. Moreover, the limit is an idempotent transformation
of Sn.
200 / 245
Proof.
By definition of profinite semigroup, S admits a complete metric d.
We may endow the product space Sn with various metrics, among
which the maximum metric d defined by
d (s1, . . . , sn), (t1, . . . , tn) = max{d(si , ti ) : i = 1, . . . , n}.
This defines a complete metric structure on Sn. Thus, to prove
that the sequence f k!(s1, . . . , sn) k
converges, it suffices to show
that it is a Cauchy sequence.
By Proposition 5.1 and Lemma 17.1, it suffices to consider the
case where S is a finite semigroup, in which case the result
amounts to the convergence of the corresponding sequence f k! in
the finite monoid of transformations of Sn, where indeed we have
observed that it converges to an idempotent.
201 / 245
We denote the limit lim[w1, . . . , wn]k!
S by [w1, . . . , wn]ω
S .
In particular, given w1, . . . , wn ∈ ΩnS, we may consider the
following n-tuple of n-ary implicit operations:
(v1, . . . , vn) = [w1, . . . , wn]ω
ΩnS
(x1, . . . , xn).
Lemma 17.3
With the above notation, if S is a profinite semigroup, then
[v1, . . . , vn]S = [w1, . . . , wn]ω
S .
Thus, the transformation [w1, . . . , wn]ω
S is again an implicit
operator and the semigroup On(S) is closed under taking ω-powers.
202 / 245
Proof.
Let (s1, . . . , sn) be an n-tuple of elements of S. Then there is a
unique continuous homomorphism ϕ : ΩnS → S such that
ϕ(xi ) = si (i = 1, . . . , n).
In view of Lemma 17.1 and taking into account that ϕn is
continuous, we obtain
[v1, . . . , vn]S (s1, . . . , sn)
= ϕn
[v1, . . . , vn]ΩnS(x1, . . . , xn)
= ϕn
lim[w1, . . . , wn]k!
ΩnS
(x1, . . . , xn)
= lim ϕn
[w1, . . . , wn]k!
ΩnS
(x1, . . . , xn)
= lim[w1, . . . , wn]k!
S (s1, . . . , sn)
= [w1, . . . , wn]ω
S (s1, . . . , sn),
which establishes the desired equality.
203 / 245
Since ΩnS is a profinite semigroup freely generated by the set
{x1, . . . , xn}, the n-tuples of n-ary implicit operations
(w1, . . . , wn) are in bijection with the continuous
endomorphisms ϕ(w1,...,wn) of ΩnS, where ϕ(w1,...,wn)(xi ) = wi
(i = 1, . . . , n).
On the other hand, they are also in bijection with n-ary
implicit operators on ΩnS, namely through the formula
(w1, . . . , wn) = [w1, . . . , wn]ΩAS(x1, . . . , xn).
For a profinite semigroup S, denote by End S the monoid of
continuous endomorphisms of S, acting on the left.
204 / 245
Proposition 17.4
The following mapping is an anti-isomorphism of semigroups:
Θ : End ΩnS → On(ΩnS)
ϕ → [ϕ(x1), . . . , ϕ(xn)]ΩnS.
Proof.
We have already observed that the above mapping is a bijection, and described
its inverse. So, it remains to verify that it is an anti-homomorphism of
semigroups.
Let ϕ, ψ ∈ End ΩnS and let wi = ψ(xi ) (i = 1, . . . , n). Taking into account
Lemma 17.1, we obtain
Θ(ϕ ◦ ψ) = [ϕ(ψ(x1)), . . . , ϕ(ψ(xn))]ΩnS
= [ϕ(w1), . . . , ϕ(wn))]ΩnS
= [w1(ϕ(x1), . . . ϕ(xn)), . . . , wn(ϕ(x1), . . . ϕ(xn))]ΩnS
= [w1, . . . , wn]ΩnS ◦ [ϕ(x1), . . . ϕ(xn)]ΩnS
= Θ(ψ) ◦ Θ(ϕ).
205 / 245
Lemma 17.5
Let ϕk, ϕ ∈ End ΩnS (k ≥ 0). Then (ϕk)k convergences pointwise
to ϕ if and only if (Θ(ϕk))k converges pointwise to Θ(ϕ).
Proof.
Let vk,i = ϕk(xi ) and vi = ϕ(xi ) (i = 1, . . . , n; k ≥ 0).
(⇒) For w1, . . . , wn ∈ ΩnS, we have
Θ(ϕk)(w1, . . . , wn)
= [vk,1, . . . , vk,n]ΩnS(w1, . . . , wn)
= (vk,1)ΩnS(w1, . . . , wn), . . . , (vk,n)ΩnS(w1, . . . , wn)
→ (v1)ΩnS(w1, . . . , wn), . . . , (vn)ΩnS(w1, . . . , wn)
= [v1, . . . , vn]ΩnS(w1, . . . , wn)
= Θ(ϕ)(w1, . . . , wn),
where the convergence step follows from Lemma 16.1.
206 / 245
(. . . )
(⇐) Let w ∈ ΩnS. Then we have
ϕk(w) = ϕk wΩnS(x1, . . . , xn)
= wΩnS vk,1, . . . , vk,n
= wΩnS [vk,1, . . . , vk,n]ΩnS(x1, . . . , xn)
→ wΩnS [v1, . . . , vn]ΩnS(x1, . . . , xn)
= ϕ wΩnS(x1, . . . , xn)
= ϕ(w),
where we use again Lemma 16.1 for the convergence step.
207 / 245
Corollary 17.6
For a continuous endomorphism ϕ of ΩnS, the sequence (ϕk!)
converges pointwise to an idempotent continuous endomorphism
of ΩnS.
The idempotent in question is denoted ϕω and is called the
ω-power or ω-iterate of ϕ.
More generally, Hunter [Hun83] has shown that the monoid
End S of continuous endomorphisms of a finitely generated
profinite semigroup S is profinite. Since it is usually not
finitely generated, this result does not fit in the realm of our
metric approach to profinite semigroups. For those that know
about topology of function spaces, the topology used in End S
is the topology of pointwise convergence (i.e., as a subspace
of the product space SS ), and turns out to coincinde with the
compact-open topology (i.e., the topology of uniform
convergence). See also [Alm02, AV06a, Alm05, Ste11].
208 / 245
Examples
The ω-iteration of continuous endomorphisms of ΩnS, or of
implicit operators on ΩnS can be used to construct useful
implicit operations.
Let ϕ ∈ End Ω1S be defined by ϕ(x1) = xp
1 . Then
ϕk(x1) = xpk
1 and ϕω(x1) = xpω
1 . Recall that we used the
implicit operation xpω
1 previously to define the pseudovariety
Gp in terms of pseudoidentities: Gp = [[xpω
1 = 1]].
209 / 245
Given elements u and v of a profinite semigroup S, let
[u, v] = uω−1
vω−1
uv,
an extension of the group commutator. Note, however, that,
if S is not a group, [u, v] idempotent may not be equivalent
to uv = vu.
Let ϕ ∈ End Ω2S be defined by ϕ(x1) = [x1, x2] and
ϕ(x2) = x2. Note that ϕk(x1) is the iterated commutator
defined recursively by [x1,1 x2] = [x1, x2] together with
[x1,k+1 x2] = [[x1,k x2], x2].
We let [x1,ω x2] = ϕω(x1), which is an implicit operation
in Ω2S.
Using a theorem of Zorn [Zor36], that states that a finite
group is nilpotent (i.e., a direct product of groups of prime
power order) if and only if it satisfies some identity of the
form [x,n y] = 1, it is now easy to solve Exercise 6.5(2):
Gnil = [[[x,ω y] = 1]].
210 / 245
The Prouhet-Thue-Morse substitution
When ϕ ∈ ΩAS extends an endomorphism of A+ it is also
called a (finite) substitution since applying ϕ to a word
corresponds to substituting each letter a ∈ A by the word
ϕ(a).
The substitution over the alphabet {a, b} defined by
τ(a) = ab and τ(b) = ba was first considered by
Prouhet [Pro51], and rediscovered by Thue [Thu06, Thu12]
and Hedlund and Morse [HM38].
Here is an example of a result involving it:
Theorem 17.7 (ˇSirˇsov [ˇS63])
The pseudovariety [[τω(a) = τω(b), xω = 1]] consists of all finite
groups admitting a normal nilpotent subgroup whose
corresponding factor group is a 2-group.
211 / 245
The substitution τ determines a binary implicit operator
[ab, ba]S on every profinite semigroup S. How does it behave
on a finite group?
When iterating a transformation on a finite set, in a finite
number steps one must enter into a periodic orbit.
One possible way to visualize the action of our
Prouhet-Thue-Morse implicit operator on a finite group G is
to draw a square in which the sides stand for G, and a pixel,
an elementary square, for an element of G × G. One may
color each pixel so as to encode for instance how many
applications of the operator it takes to reach a periodic orbit,
and to distinguish between the different periodic orbits.
It is somewhat striking that one obtains pictures like those in
the following two pages. The ordering of the elements in the
groups is that given by GAP [GAP06], a computer algebra
system that was used to carry out the calculations. The
groups are Z/858Z and V4 A3.
212 / 245
Outline
Semigroups of implicit operators
Complexity
Complexity of pseudowords generated by
iteration of substitutions
Entropy
215 / 245
finite factor complexity
Given w ∈ ΩAS, denote by F(w) the set of words u ∈ A+
which are factors of w, and let Fn(w) = F(w) ∩ An.
The complexity sequence qw (n) is defined by letting
qw (n) = |Fn(w)|, where n is a positive integer.
Lemma 18.1
Let w ∈ ΩAS \ A+ and let u ∈ F(w). If there is no a ∈ A such
that ua ∈ F(w), then there is factorization of the form w = vu.
216 / 245
Proof.
Let (wn)n be a sequence of finite words converging to w. For each
z ∈ A+, the set Cz = (ΩAS)1z(ΩAS)1 = A∗zA∗ is a clopen set
such that Cz ∩ A+ = A∗zA∗. By hypothesis, w belongs to Cu and
so we may assume that so do all wn, since Cu is open. On the other
hand, since Cua is closed, we may assume that no wn ∈ Cua, for
any a ∈ A. This leaves only one place for u to be a factor of each
wn, namely as a suffix: wn = vnu for some vn ∈ A∗. Since ΩAS is
compact, some subsequence of (vn)n converges to some v ∈ ΩAS.
By continuity of multiplication, it follows that w = vu.
217 / 245
Lemma 18.2
Let w ∈ ΩAS. Then the following formula holds for every positive
integer n:
qw (n + 1) − qw (n) =
u∈Fn(w)
(|{a ∈ A : ua ∈ Fn+1(w)}| − 1). (9)
Proof.
Each factor of w of length n + 1 is of the form ua, for some a ∈ A,
which yields the following formula:
qw (n + 1) =
u∈Fn(w)
|{a ∈ A : ua ∈ Fn+1(w)}|.
Subtracting qw (n) = u∈Fn(w) 1, we obtain formula (9).
218 / 245
Because of the suffix of length n appearing nowhere else in w
(cf. Lemma 18.1), there may be one negative term in the
sum (9). However, the sum is always nonnegative for
w ∈ ΩAS \ A+.
Lemma 18.3
Let w ∈ ΩAS \ A+. Then the sequence qw (n) is increasing.
219 / 245
Proof.
Suppose that qw (n + 1) < qw (n). Then, as argued above, the suffix u of
length n of w must not appear elsewhere in w as a factor, and all other
terms in the sum must be zero: for every v ∈ Fn(w) \ {u}, there is
exactly one letter av ∈ A such that vav ∈ Fn+1(w).
Now, suppose that tz is a finite suffix of w, with |t| = n. Then there is
no word z with |z | > |z| such that tz is a suffix of w. For, otherwise,
we may take a counterexample (t, z) with |z| minimum. Then z = 1 for,
else, we must have t = u and we know that u does not appear elsewhere
in w. Hence, z = atz1 and, if we write t = bt1, with b ∈ A, then (t1, z1)
is still a counterexample and |z1| < |z|, which contradicts our choice of
counterexample.
Hence every factor of length n of w which appears as part of a finite
suffix, can be found as such in only one position. Since Fn(w) ⊆ An
is
finite, we conclude that w cannot have arbitrarily long finite suffixes,
whence w ∈ A+
, contrary to the hypothesis.
220 / 245
We say that a finite word u is primitive if it is not of the form
vn for some integer n > 1.
Theorem 18.4 ([AV06a])
Suppose that w ∈ ΩAS \ A+ is such that qw (n) ≤ n for some n.
Then there exist finite words x, y, and z and an infinite ν ∈ ˆZ+
such that w = xyνz, |xy| ≤ n, and |yz| ≤ n.
Corollary 18.5 ([AV06a])
Let w be any pseudoword which is not of the form xyνz for some
finite words x, y, z and some ν ∈ ˆZ+. Then qw (n) ≥ n + 1 for
every n.
221 / 245
The next result identifies maximal subgroups of ΩAS of small
complexity.
Theorem 18.6 ([AV06a])
Suppose that w lies in a subgroup of ΩAS and qw (n) ≤ n for
some n. Then the H-class of w is a free procyclic group with
generator of the form yω+1 for some word y of length at most n.
In particular, for each positive n, there are only finitely many
H-classes of such pseudowords w.
Note that J -equivalent elements of ΩAS have the same
complexity.
Corollary 18.7
The complexity of any non-procyclic subgroup of ΩAS is at least
q(n) ≥ n + 1.
222 / 245
Sturmian pseudowords
Thus, the minimum possible complexity for a non-procyclic
subgroup of ΩAS is q(n) = n + 1.
Then q(1) = 2, which means that there are exactly two letters
involved in the subgroup in question.
We say that w ∈ ΩAS is Sturmian if qw (n) = n + 1 for every
n ≥ 1.
223 / 245
Outline
Semigroups of implicit operators
Complexity
Complexity of pseudowords generated by
iteration of substitutions
Entropy
224 / 245
Primitive substitutions
Since substitutions over a one-letter alphabet are not very
interesting, we assume from hereon that |A| ≥ 2.
A finite substitution ϕ ∈ End ΩAS is said to be primitive if
there is some positive integer N such that, for every two
letters a, b ∈ A, a appears in the word ϕN(b).
Proposition 19.1
Let ϕ ∈ End ΩAS be a primitive finite substitution. Then all
pseudowords of the form ϕω(a), with a ∈ A, lie in the same
J -class.
Proof.
Let N be as above and let a, b ∈ A. Then a is a factor of ϕkN(b)
for every k. By compactness, it follows that a is also a factor
of ϕω(b) = (ϕN)ω(b), say ϕω(b) = uav. Since ϕω is idempotent,
we deduce that ϕω(b) = ϕω(u) · ϕω(a) · ϕω(v), which shows that
ϕω(a) is a factor of ϕω(b).
225 / 245
We have already seen one classical example of primitive finite
substitution, namely the Prouhet-Thue-Morse substitution
a → ab, b → ba.
Another classical example is that of the so-called Fibonacci
substitution ϕ(a) = ab, ϕ(b) = a. Note that the fn = |ϕn(b)|
satisfies the recurrence relation fn+2 = fn+1 + fn, with
f1 = f2 = 1.
ϕω(b) is an example of Sturmian pseudoword.
More generally, the following is a consequence of a theorem of
Mignosi and S´e´ebold [MS93] on infinite words.
Theorem 19.2
Let ϕ ∈ End Ω2S be a primitive substitution. Then ϕω(x1) is
Sturmian if and only if ϕ induces an automorphism of the free
group Ωκ
2G.
226 / 245
By Proposition 19.1, one may consider the complexity of a
primitive finite substitution ϕ ∈ End ΩAS.
Theorem 19.3 ([ELR75, Pan84])
The complexity of a primitive finite substitution is at most linear.
227 / 245
Proof.
Let ϕ ∈ End ΩAS be a primitive finite substitution, let q be its complexity, and
let n be a positive integer. There is some p such that
min
a∈A
|ϕp−1
(a)| ≤ n ≤ min
a∈A
|ϕp
(a)|. (10)
Then, every word in Fn(ϕω
(a)) must be a factor of some ϕp
(a) or of some
ϕp
(ab), with ab a factor of ϕω
(ab). For each such two-letter word ab, there are
at most |ϕp
(ab)| factors of length n. Hence, if we let r = |A|2
, then we have
q(n) ≤ 2r max
a∈A
|ϕp
(a)|. (11)
By the Perron-Frobenius Theorem (19.4), there are constants α, c, d > 0 such
that
cαp
≤ min
a∈A
|ϕp
(a)| ≤ max
a∈A
|ϕp
(a)| ≤ dαp
. (12)
Combining the inequalities (11) and (12) and taking also into account (10), we
obtain
q(n) ≤ 2r dαp
≤ 2r
d
c
α n.
228 / 245
The Perron-Frobenius Theorem
Let ϕ ∈ End ΩAS be a finite substitution. For each a, b ∈ A,
one may consider the number |ϕ(a)|b of occurrences of the
letter b in the word ϕ(a). This defines a matrix M(ϕ) with
nonnegative integer entries.
Note that:
the sum of the entries in the row corresponding to a ∈ A is
|ϕ(a)|;
for another finite substitution ψ ∈ End ΩAS,
M(ϕ ◦ ψ) = M(ϕ)M(ψ);
thus M(ϕk
) = (M(ϕ))k
for every k ≥ 1;
hence ϕ is primitive if and only if tere exists k ≥ 1 such that
(M(ϕ))k
has all entries positive; a matrix with nonnegative
real entries satisfying this property is said to be primitive;
An n × n real matrix M is said to be irreducible if, for every
pair of indices i, j, there is a power Mk whose i, j-entry is
nonzero.
229 / 245
Theorem 19.4 (Perron-Frobenius)
Let M be a nonnegative irreducible matrix. Then there is a
positive simple eigenvalue α such that
α ≥ |λ| for every other eigenvalue λ and
α admits an eigenvector whose coordinates are all positive.
In case M is primitive, α > |λ| for every other eigenvalue λ.
The special, dominant eigenvalue α, is called the
Perron-Frobenius eigenvalue of the matrix M.
See http://en.wikipedia.org/wiki/Perron-Frobenius theorem
for the significance of the theorem and several proofs.
230 / 245
For the proof of the existence of constants c, d such that the
inequalities (12) hold, let M be a r × r nonnegative primitive matrix
and let α be its Perron-Frobenius eigenvalue. Let v = (v1, . . . , vr )
be a corresponding positive eigenvector: Mv = αv, whence
Mp
v = αp
v for all p ≥ 1.
Let (Mp
)i,j denote the i, j entry of the matrix Mp
.
For i = 1, . . . , r, we have
r
j=1
(Mp
)i,j vj = αp
vi .
Hence, if c0 = mini vi and d0 = maxi vi , then we get
c0
r
j=1(Mp
)i,j ≤ d0αp
for every i, whence
max
i
r
j=1
(Mp
)i,j ≤
d0
c0
αp
.
On the other hand, we have c0αp
≤ d0
r
j=1(Mp
)i,j for every i,
which gives
c0
d0
αp
≤ min
i
r
j=1
(Mp
)i,j .
231 / 245
Examples
Consider the Prouhet-Thue-Morse substitution τ(a) = ab,
τ(b) = ba.
Then M(τ) =
1 1
1 1
has characteristic polynomial
(1 − x)2 − 1 = x(x − 2) and eigenvalues 0 < 2.
So, 2 is the Perron-Frobenius eigenvalue. The corresponding
eigenspace is generated by (1, 1).
For w = τω(a), the proof of Theorem 19.3 gives
qw (n) ≤ 2 × 22
×
1
1
× 2n = 16n.
It turns out that this is about double the exact value, which
has been computed (see [Fog02, Proposition 5.1.9]).
232 / 245
Let ϕ be the Fibonacci substitution: ϕ(a) = ab, ϕ(b) = a.
Then M(ϕ) =
1 1
1 0
has characteristic polynomial
(1 − x)(−x) − 1 = x2 − x − 1 and eigenvalues 1−
√
5
2 < 1+
√
5
2 .
The Perron-Frobenius eigenvalue, 1+
√
5
2 , has eigenspace
generated by the vector (1+
√
5
2 , 1).
For w = ϕω(a), the proof of Theorem 19.3 gives
qw (n) ≤ 2×22
×
1 +
√
5
2
2
×
1 +
√
5
2
n = 2(1+
√
5)3
n 68n,
while we know that qw (n) = n + 1.
233 / 245
Outline
Semigroups of implicit operators
Complexity
Complexity of pseudowords generated by
iteration of substitutions
Entropy
234 / 245
Entropy
The complexity (function) of a pseudoword has the following
log-subadditive property:
Lemma 20.1
Let w ∈ ΩAS. Then the inequality qw (r + s) ≤ qw (r) qw (s) holds
for all positive integers r and s.
Proof.
A factor of w of length r + s is of the form uv, where u ∈ Fr (w)
and v ∈ Fs(w).
Lemma 20.2 (Fekete’s Lemma)
Let (tn)n be a sequence of real numbers such that tr+s ≤ tr + ts
for all r, s ≥ 1. Then we have lim tn
n = inf tn
n .
235 / 245
Proof.
Let = inf tn
n and let be a positive real number. Let K be an
index such that tK
K < + 2. There is also a positive integer M
such that tr
KM < 2 for r < K.
Let n ≥ KM and write n = qK + r with r < K. Then
≤
tn
n
≤
qtK
qK + r
+
tr
n
≤
qtK
qK
+
tr
KM
≤
tK
K
+
tr
KM
≤ +
2
+
2
which establishes the lemma.
236 / 245
Let A be a finite alphabet and m = |A|.
For a pseudoword w ∈ ΩAS \ A+, by Lemmas 20.1 and 20.2,
the following limit exists:
h(w) = lim
n→∞
1
n
logm qw (n).
It is called the entropy of w.
Since 1 ≤ qw (n) ≤ mn, the entropy h(w) is a real number in
the interval [0, 1].
If u, v ∈ ΩAS \ A+ are such that u is a factor of v, then
h(u) ≤ h(v).
237 / 245
Iteration of primitive finite substitutions leads to minimum
entropy:
Theorem 20.3
Let ϕ ∈ End ΩAS be a primitive finite substitution. Then we have
h(ϕω(a)) = 0.
Proof.
Let w = ϕω(a). By Theorem 19.3, there is some constant C such
that qw (n) ≤ Cn, for every n ≥ 1. Hence h(w) = 0.
A much more general result is uncovered below in
Theorem 20.8.
238 / 245
Proposition 20.4
Let w ∈ ΩAS \ A+. Then h(w) = 1 if and only if every u ∈ ΩAS is
a factor if w.
Proof.
Since h(w) = inf 1
n logm qw (n), we have h(w) = 1 if and only if
qw (n) = mn for every n, that is if and only if every finite word is a
factor of w. But every element of ΩAS is the limit of a sequence of
finite words. Hence every finite word is a factor of w if and only if
every pseudoword is a factor of w.
239 / 245
An ideal in a semigroup S is a nonempty subset I such that
SI ∪ IS ⊆ I.
A minimal ideal is an ideal which is not properly contained in
any other ideal.
Some semigroups, such as A+, have no minimal ideals.
Note that a semigroup cannot have more than one minimal
ideal: given two ideals I and J, IJ is an ideal contained in
both of them.
When there is one minimal ideal, we call it the minimum ideal,
since it is indeed contained in every ideal. The minimum ideal
of a semigroup is often also called its kernel and denoted
K(S).
For a semigroup S, the elements of the minimum ideal, if it
exists, are precisely those elements of S which admit every
element of S as a factor.
240 / 245
Proposition 20.5
Every compact metric semigroup has a minimum ideal.
Proof.
Let S be a compact metric semigroup. For each n, by compactness
S is covered by a finite number of open balls of radius 1
n . If we
choose such balls and collect their centers for varying n in a set, we
obtain a countable dense subset X.
Let X = {x1, x2, . . . , xn, . . .} be an enumeration of the elements
of X. Let s be any limit of a subsequence of the sequence
(x1 · · · xn)n. Then s admits every element of X as a factor and,
since X is dense in S, every element of S must be a factor of S.
Hence s ∈ K(S).
241 / 245
In particular, every finite and every profinite semigroup has a
minimum ideal.
Proposition 20.4 means that w ∈ ΩAS has maximum entropy
(one) if and only if w ∈ K(ΩAS).
Theorem 20.6 ([AV06b])
Let w = w(v1, . . . , vr ) where the vi ∈ ΩAS (i = 1, . . . , r) and
w ∈ Ωr S. The entropy operator satisfies the following inequality:
h(w ) ≤ max{h(w) logm r, h(v1), . . . , h(vr )}. (13)
An ideal I of a semigroup S is said to be prime if st ∈ I
implies s ∈ I or t ∈ I.
Corollary 20.7
The minimum ideal of ΩAS is prime.
242 / 245
Theorem 20.8 ([AV06b])
Let u1, . . . , un ∈ ΩnS and let
(v1, . . . , vn) = [u1, . . . , un]ω
ΩAS
(x1, . . . , xn).
Then the entropy operator satisfies the following inequality:
max
1≤i≤m
h(vi ) ≤ max
1≤i≤m
h(ui ).
The following result is a considerable strengthening of
Corollary 20.9.
Corollary 20.9
For m > 1, the set ΩmS \ K(ΩmS) is a subsemigroup of ΩmS
which is closed under composition and iteration.
243 / 245
All the results we have presented involving complexity and
entropy apply to ΩAV with V a pseudovariety containing LSl:
all we require is to be able to test finite factors, that is sets of
the form (ΩAV)1
w(ΩAV)1
= A∗wA∗, with w ∈ A+
, which we
need to be clopen;
since A∗
wA∗
is LSl-recognizable, such sets are indeed clopen
by Theorem 5.9.
244 / 245
Section 21
References
245 / 245
[ABR92] D. Albert, R. Baldinger, and J. Rhodes, The identity problem for
finite semigroups (the undecidability of), J. Symbolic Logic 57
(1992), 179–192.
[AE03] J. Almeida and A. Escada, Semidirect products with the
pseudovariety of all finite groups, Proceedings of the International
Conference Words, Languages and Combinatorics (Kyoto, March,
2000) (Singapore) (M. Ito and T. Imaoka, eds.), World Scientific,
2003, pp. 1–21.
[Alm95] J. Almeida, Finite semigroups and universal algebra, World
Scientific, Singapore, 1995, English translation.
[Alm02] , Dynamics of implicit operations and tameness of
pseudovarieties of groups, Trans. Amer. Math. Soc. 354 (2002),
387–411.
[Alm05] , Profinite semigroups and applications, Structural Theory
of Automata, Semigroups, and Universal Algebra (New York)
(Valery B. Kudryavtsev and Ivo G. Rosenberg, eds.), NATO Science
Series II: Mathematics, Physics and Chemistry, vol. 207, Springer,
2005, Proceedings of the NATO Advanced Study Institute on
Structural Theory of Automata, Semigroups and Universal Algebra,
Montr´eal, Qu´ebec, Canada, 7-18 July 2003, pp. 1–45.
245 / 245
[AS00a] J. Almeida and B. Steinberg, On the decidability of iterated
semidirect products and applications to complexity, Proc. London
Math. Soc. 80 (2000), 50–74.
[AS00b] , Syntactic and global semigroup theory, a synthesis
approach, Algorithmic Problems in Groups and Semigroups (J. C.
Birget, S. W. Margolis, J. Meakin, and M. V. Sapir, eds.),
Birkh¨auser, 2000, pp. 1–23.
[AS01] J. Almeida and P. V. Silva, SC-hyperdecidability of R, Theor.
Comp. Sci. 255 (2001), 569–591.
[AS03] K. Auinger and B. Steinberg, On the extension problem for partial
permutations, Proc. Amer. Math. Soc. 131 (2003), 2693–2703.
[Ash87] C. J. Ash, Finite semigroups with commuting idempotents, J.
Austral. Math. Soc., Ser. A 43 (1987), 81–90.
[Ash91] , Inevitable graphs: a proof of the type II conjecture and
some related decision procedures, Int. J. Algebra Comput. 1
(1991), 127–146.
[AT01] J. Almeida and P. G. Trotter, The pseudoidentity problem and
reducibility for completely regular semigroups, Bull. Austral. Math.
Soc. 63 (2001), 407–433.
245 / 245
[AV06a] J. Almeida and M. V. Volkov, Subword complexity of profinite
words and subgroups of free profinite semigroups, Int. J. Algebra
Comput. 16 (2006), 221–258.
[AV06b] , Subword complexity of profinite words and subgroups of
free profinite semigroups, Int. J. Algebra Comput. 16 (2006),
221–258.
[AZ07] J. Almeida and M. Zeitoun, An automata-theoretic approach of the
word problem for ω-terms over R, Theor. Comp. Sci. 370 (2007),
131–169.
[Bau65] G. Baumslag, Residual nilpotence and relations in free groups, J.
Algebra 2 (1965), 271–282.
[Ber79] J. Berstel, Transductions and context-free languages, B. G.
Teubner, Stuttgart, 1979.
[BS73] J. A. Brzozowski and I. Simon, Characterizations of locally testable
events, Discrete Math. 4 (1973), 243–271.
[CT04] J. C. Costa and M. L. Teixeira, Tameness of the pseudovariety LSl,
Int. J. Algebra Comput. 14 (2004), 627–654.
[Del01] M. Delgado, On the hyperdecidability of pseudovarieties of groups,
Int. J. Algebra Comput. 11 (2001), 753–771.
245 / 245
[Eil76] S. Eilenberg, Automata, languages and machines, vol. B, Academic
Press, New York, 1976.
[ELR75] A. Ehrenfeucht, K. P. Lee, and G. Rozenberg, Subword
complexities of various classes of deterministic developmental
languages without interaction, Theor. Comp. Sci. 1 (1975), 59–75.
[Fog02] N. Pytheas Fogg, Substitutions in dynamics, arithmetics and
combinatorics, Lecture Notes in Mathematics, vol. 1794,
Springer-Verlag, Berlin, 2002.
[GAP06] The GAP Group, GAP – Groups, Algorithms, and Programming,
Version 4.4, 2006, (http://www.gap-system.org).
[Hal50] M. Hall, A topology for free groups and related groups, Ann. Math.
52 (1950), 127–139.
[Hen88] Karsten Henckell, Pointlike sets: the finest aperiodic cover of a
finite semigroup, J. Pure Appl. Algebra 55 (1988), 85–126.
[HM38] G. A. Hedlund and M. Morse, Symbolic dynamics, Amer. J. Math.
60 (1938), 815–866.
[HMPR91] K. Henckell, S. Margolis, J.-E. Pin, and J. Rhodes, Ash’s type II
theorem, profinite topology and Malcev products. Part I, Int. J.
Algebra Comput. 1 (1991), 411–436.
245 / 245
[HR91] K. Henckell and J. Rhodes, The theorem of Knast, the PG=BG and
Type II Conjectures, Monoids and Semigroups with Applications
(Singapore) (J. Rhodes, ed.), World Scientific, 1991, pp. 453–463.
[Hun83] R. P. Hunter, Some remarks on subgroups defined by the Bohr
compactification, Semigroup Forum 26 (1983), 125–137.
[Hun88] , Certain finitely generated compact zero-dimensional
semigroups, J. Austral. Math. Soc., Ser. A 44 (1988), 265–270.
[KM02] I. Kapovich and A. Myasnikov, Stallings foldings and subgroups of
free groups, J. Algebra 248 (2002), 608–668.
[KP86] Jiˇri Kad’ourek and Libor Pol´ak, On the word problem for free
completely regular semigroups, Semigroup Forum 34 (1986),
127–138.
[KR65] K. Krohn and J. Rhodes, Algebraic theory of machines. I. Prime
decomposition theorem for finite semigroups and machines, Trans.
Amer. Math. Soc. 116 (1965), 450–464.
[McC01] J. McCammond, Normal forms for free aperiodic semigroups, Int.
J. Algebra Comput. 11 (2001), 581–625.
[MP71] R. McNaughton and S. Papert, Counter-free automata, MIT Press,
Cambridge, MA, 1971.
245 / 245
[MP84] S. W. Margolis and J.-E. Pin, Varieties of finite monoids and
topology for the free monoid, Proc. 1984 Marquette Semigroup
Conference (Milwaukee), Marquette University, 1984, pp. 113–129.
[MP87] , Inverse semigroups and varieties of finite semigroups, J.
Algebra 110 (1987), 306–323.
[MS93] F. Mignosi and P. S´e´ebold, Morphismes sturmiens et r`egles de
rauzy, J. Th´eor. Nombres Bordeaux 5 (1993), 221–233.
[MSW01] S. Margolis, M. Sapir, and P. Weil, Closed subgroups in pro-V
topologies and the extension problem for inverse automata, Int. J.
Algebra Comput. 11 (2001), 405–445.
[Num57] K. Numakura, Theorems on compact totally disconnetced
semigroups and lattices, Proc. Amer. Math. Soc. 8 (1957),
623–626.
[Pan84] J.-J. Pansiot, Complexit´e des facteurs des mots infinis engendr´es
par morphismes it´er´es, Automata, Languages and Programming
(Antwerp, 1984) (Berlin), Lect. Notes Comput. Sci., no. 172,
Springer, 1984, pp. 380–389.
245 / 245
[Pin95] J.-E. Pin, BG=PG: A success story, Semigroups, Formal Languages
and Groups (Dordrecht) (J. Fountain, ed.), vol. 466, Kluwer, 1995,
pp. 33–47.
[PR91] J.-E. Pin and C. Reutenauer, A conjecture on the Hall topology for
the free group, Bull. London Math. Soc. 23 (1991), 356–362.
[Pro51] E. Prouhet, M´emoire sur quelques relations entre les puissances des
nombres, C. R. Acad. Sci. Paris 33 (1851), 31.
[PS85] J.-E. Pin and H. Straubing, Monoids of upper triangular matrices,
Semigroups: structure and universal algebraic problems
(Amsterdam) (G. Poll´ak, ed.), North-Holland, 1985, pp. 259–272.
[Rei82] J. Reiterman, The Birkhoff theorem for finite algebras, Algebra
Universalis 14 (1982), 1–10.
[RZ93] L. Ribes and P. A. Zalesski˘ı, On the profinite topology on a free
group, Bull. London Math. Soc. 25 (1993), 37–43.
[Sch65] M. P. Sch¨utzenberger, On finite monoids having only trivial
subgroups, Inform. and Control 8 (1965), 190–194.
[Sim75] I. Simon, Piecewise testable events, Proc. 2nd GI Conf. (Berlin),
Lect. Notes in Comput. Sci., vol. 33, Springer, 1975, pp. 214–222.
245 / 245
[Sta83] J. R. Stallings, Topology of finite graphs, Inventiones
Mathematicae 71 (1983), 551–565.
[Ste01] B. Steinberg, Inevitable graphs and profinite topologies: some
solutions to algorithmic problems in monoid and automata theory,
stemming from group theory, Int. J. Algebra Comput. 11 (2001),
25–71.
[Ste11] , On the endomorphism monoid of a profinite semigroup,
Portugal. Math. 68 (2011), 177–183.
[Sti73] P. Stiffler, Extension of the fundamental theorem of finite
semigroups, Advances in Math. 11 (1973), 159–209.
[Thu06] A. Thue, ¨Uber unendlichen zeichenreihen, Kra. Vidensk. Selsk.
Skrifter, I. Mat. Nat. Kl. (1906), no. 7, 1–22.
[Thu12] A. Thu¨e, ¨Uber die gegenseitige Lage gleicher Teile gewisser
Zeichenreihen, Norske Vid. Selsk. Skr. I. Mat.-nat. Kl., Christiana 1
(1912), 1–67.
[ˇS63] A. I. ˇSirˇsov, On certain near-engel groups, Algebra i Logika 2
(1963), no. 5, 5–18.
[Zor36] M. Zorn, Nilpotency of finite groups (abstract), Bull. Amer. Math.
Soc. 42 (1936), 485–486.
245 / 245