RANDOM UBIQUITOUS TRANSFORMATION SEMIGROUPS

arXiv:1705.05709v1 [math.GR] 16 May 2017

JULIUS JONUŠAS AND SASCHA TROSCHEIT

Abstract. A smallest generating set of a semigroup is a generating set of the
smallest cardinality. Similarly, an irredundant generating set X is a generating
set such that no proper subset of X is also a generating set. A semigroup S is
ubiquitous if every irredundant generating set of S is of the same cardinality.
We are motivated by a naı̈ve algorithm to find a small generating set for a
semigroup, which in practice often outputs a smallest generating set. We give a
sufficient condition for a transformation semigroup to be ubiquitous and show
that a transformation semigroup generated by k randomly chosen transformations asymptoticly satisfies the sufficient condition. Finally, we show that
under this condition the output of the previously mentioned naı̈ve algorithm
is irredundant.

1. Introduction
A generating set X of a semigroup S is a smallest generating set, also known
as minimum generating set, if every subset of S with cardinality strictly smaller
than |X| does not generate S. The size of a smallest generating set is known
as the rank of S. Similarly, an irredundant generating set for S is a generating
set X such that no proper subset of X is a generating set for S. Of course, the
notions of a smallest generating set, irredundant generating set, and the rank have
a natural interpretation for groups and other algebraic objects. The question of
finding a smallest generating set or a rank is a classical one, see for example [1, 14]
in the case of quasigroups and [8, 9, 10] in the case of semigroups. However,
from a computational perspective this is, in general, not an easy problem. In
particular, there is no known efficient algorithm to find the rank of a given S,
besides examining most of its subsets. As such, fast naı̈ve algorithms are sometimes
used to obtain small, but not necessarily smallest, generating sets. The simplest of
them is Algorithm 1.
Algorithm 1: Greedy
Input : A list S of all the elements of a semigroup
Output: A generating set X
1
2
3
4
5

X ←− ∅;
while |hXi| 6= |S| do
for s ∈ S do
if s ∈
/ hXi then
X ←− X ∪ {s} ;

The algorithm applies to both groups and semigroups. The advantages of the
Greedy algorithm are its speed and that it requires no a priori knowledge about
the object. The latter might be seen as a drawback if some structural information
We want to thank J. D. Mitchell for providing the experimental data.
ST was initially supported by EPSRC DTG EP/K503162/1.
1

2

JULIUS JONUŠAS AND SASCHA TROSCHEIT

is known. For semigroups this algorithm can be improved by taking into account
its J -class structure.
In order to define the next algorithm, we require some notation. Let S be a
semigroup and let 1 be a symbol which is not in S. Define S 1 = S ∪ {1} to be
a semigroup such that for all x, y ∈ S the product x · y in S 1 is the same as the
product in S, and x · 1 = 1 · x = x for all x ∈ S 1 . It is routine to verify that the
operation [·] on S 1 is associative. If A, B ⊆ S 1 define Ax = {a · x : a ∈ A} and
similarly define xA and AxB. Define a relation on S by
x≤y

if and only if S 1 xS 1 ⊆ S 1 yS 1 .

Then ≤ is reflexive and transitive, however it might fail to be antisymmetric. In
other words, ≤ is a preorder on S. Clearly, the relation
aJ b

if and only if

a ≥ b and a ≤ b

is an equivalence relation on S and the preorder ≤ induces a partial order on
the equivalence classes of J , which we will also denote by ≤ if the distinction is
clear from the context. We say that the list s1,1 , . . . , s1,n1 , s2,1 , . . . , s2,n2 . . . sk,nk
of all elements of S is ordered according to the preorder ≤ if {si,1 , . . . , si,ni } is an
equivalence class of J for all i and if si,k ≤ sj,m then i ≤ j. Using this idea we can
state Algorithm 2.
Algorithm 2: SmallGeneratingSet, (implemented in Semigroups [13] for
GAP [7])
Input : A semigroup S
Output: A generating set X
1
2

L ←− order elements of S according to the preorder ≤;
X ←− Greedy(L);

If S is a group, then S 1 xS 1 = S for every x ∈ S. Hence there is a single J class in S and so any permutation of elements of S is ordered according to the
preorder ≤, and so the SmallGeneratingSet algorithm does not perform any better
than Greedy. For proper semigroups the algorithm is particularly useful if the J class structure is known in advance, for example if the semigroup was enumerated
using the Froidure-Pin algorithm [6, 12] or algorithms appearing in [5]. It is easy
to come up with examples for which SmallGeneratingSet might return a generating
set which is not a smallest generating set or even an irredundant generating set,
for example any non-trivial finite group G. Even though the algorithm is naı̈ve, it
performs surprisingly well in practice. For instance, we ran the SmallGeneratingSet
algorithm on all 836 021 semigroups (up to (anti-)isomorphism) of size 7, available
in SmallSemi [4]. In all cases the generating set found was a smallest generating
set.
Let n ∈ N and let Tn be the transformation monoid on n points, that is the set
of all functions from {1, . . . , n} to itself. The set Tn forms a semigroup under the
composition of functions. In the following table, we consider every subgroup of T3
up to conjugation. Observe that — for most of them — the size of the generating
set output by SmallGeneratingSet is equal to the rank or is one greater.
The main motivation for this paper is to provide mathematical justification as
to why SmallGeneratingSet algorithms often returns a smallest generating set. In
order to do so, we consider properties of transformation semigroups picked at random, in a certain way. We say that a semigroup S is ubiquitous if every irredundant
generating of S is also a smallest generating set. Alternatively, if r is the rank of
S, then S is ubiquitous if every irredundant generating set is of size r.

RANDOM UBIQUITOUS TRANSFORMATION SEMIGROUPS

3

Table 1. Subsemigroups of T3
Rank
1
2
3
4
5

1
7
-

Size of
2 3
3 1
32 25
- 38
-

the output
4 5 6
0 0 0
11 3 1
50 23 9
23 28 6
5 7

7
0
0
2
6
2

First we will provide a sufficient condition for a transformation semigroup to be
ubiquitous.
Theorem 1.1. Let S ≤ Tn and suppose that X is a generating set for S such that
rank(xyz) < rank(y) for all x, y, z ∈ X. Then S is ubiquitous.
Even though we restrict our attention to transformation semigroups in this paper, Theorem 1.1 can be generalised to include semigroups of partial bijections as
well. We follow the approach of Cameron [2] of choosing a random transformation
semigroup. That is for some k ≥ 1 we choose k transformations of degree n with
uniform probability and consider the semigroup generated by them. We show that
most transformation semigroups are ubiquitous.
Theorem 1.2. Let k ≥ 1, and let Pk (n) be the probability that for x1 , . . . , xk ∈ Tn ,
chosen with uniform probability, the semigroup hx1 , . . . , xk i is ubiquitous. Then
Pk (n) → 1 as n → ∞ exponentially fast.
Even though SmallGeneratingSet does not return an irredundant generating set
in general, we show that under the assumptions of Theorem 1.1 the output is
irredundant. Hence the final result of the paper is as follows.
Theorem 1.3. Let k ≥ 1, and let Wk (n) be the probability that for x1 , . . . , xk ∈ Tn ,
chosen with uniform probability, SmallGeneratingSet returns a smallest generating
set for a semigroup hx1 , . . . , xk i. Then Wk (n) → 1 as n → ∞ exponentially fast.
Here we only look at the asymptotic behaviour of transformation semigroups,
however the same question can be investigated for any other infinite family of semigroups, for example symmetric inverse monoids on {1, . . . , n}, or binary relations
on n points.
2. Preliminaries
In this section we give the definitions and notation needed in the remainder of
the paper.
Definition 2.1. Let S be a semigroup and let x, y ∈ S. The Green’s relations L,
R, J , and D are the following equivalence relations on S:
xLy

if and only if S 1 x = S 1 y

xRy

if and only if xS 1 = yS 1

xJ y

if and only if S 1 xS 1 = S 1 yS 1

and D is the smallest equivalence relation containing both L and R.
Let x ∈ S. Then Lx , Rx , and Dx denote the equivalences classes of L, R, and D,
respectively, containing x. If S is finite, then D = J , for a proof see [11]. Since we
are only interested in finite semigroups we will not make any distinction between
the D and J relations.

4

JULIUS JONUŠAS AND SASCHA TROSCHEIT

Throughout the paper, we write elements of Tn on the right of their argument
and we write functions from a subset of Rn to R on the left. This is done in
agreement with two different notations prevalent in algebra and analysis.
Let f ∈ Tn , and let A ⊆ {1, . . . , n}. Then
(A)f = {(a)f : a ∈ A}
and the image of f is the set im(f ) = ({1, . . . , n})f . A transversal of f is a set
T ⊆ {1, . . . , n} such that f is injective on T and (T)f = im(f ). The rank of f is
rank(f ) = | im(f )| = |T|, where T is a transversal of f . The kernel of f , denoted
by ker(f ), is the equivalence relation defined by
(x, y) ∈ ker(f )

if and only if

(x)f = (y)f.

Hence a kernel class of f containing x ∈ {1, . . . , n} is the set
{y ∈ {1, . . . , n} : (y)f = (x)f }.
Using the above definition we can state a classical result describing Green’s
classes of transformation semigroups. The proof is easy and thus omitted.
Lemma 2.2. Let S ≤ Tn , and let f, g ∈ S. Then
(i) if f Lg then im(f ) = im(g);
(ii) if f Rg then ker(f ) = ker(g);
(iii) if f Dg then rank(f ) = rank(g).
For n, r ∈ N such that r ≤ n, define A(n, r) to be the set of partitions of
{1, . . . , n} into r non-empty components.
Lemma 2.3. Let n, r ∈ N such that r ≤ n. Then
X

{A1 ,...,Ar }∈A(n,r)

r
Y

 
n n−r
|Ai | =
r
.
r
i=1

Proof. A function f ∈ Tn is called idempotent if f 2 = f . We prove the lemma
by finding the number of idempotent transformation of Tn of rank r in two ways.
Denote this number by N . It can be shown that f is an idempotent if and only if
(x)f = x for all x ∈ im(f ).

If f ∈ Tn is an idempotent of rank r, then there are nr choices for the im(f )
and for every point in {1, . . . , n} \ im(f ) there are r choices in im(f ) to map to.
Hence
 
n n−r
N=
r
.
r
On the other hand, the sets A1 , . . . , Ar are the kernel classes of f ∈ Tn if and only
if {A1 , . . . , Ar } ∈ A(n, r). If f is an idempotent and A1 , . . . , A
Qrr are kernel classes
of f then (Ai )f ∈ Ai for all i ∈ {1, . . . , r}, and so there are i=1 |Ai | choices for
the im(f ). Hence
r
Y
X
|Ai |,
N=
{A1 ,...,Ar }∈A(n,r) i=1

as required.



n

Since |A(n, r)| = r , the following easy upper bound for the Stirling numbers
is an immediate consequence of Lemma 2.3.
Corollary 2.4. Let n, r ∈ N be such that r ≤ n. Then
   
n
n n−r
≤
r
.
r
r

RANDOM UBIQUITOUS TRANSFORMATION SEMIGROUPS

5

We will make use of Stirling’s approximation formula
√
√
1
1
1
2πnn+ 2 e−n ≤ n! ≤ 2πnn+ 2 e−n+ 2n .
If F : R → R, then we say that G ∈ O(F ) if there are c > 0 and x0 ∈ R such that
|G(x)| ≤ c|F (x)| for all x ≥ x0 . Then Stirling’s formula can be written as follows
log n! = n log n − n + O(log(n)).

Let R+ = {x ∈ R : x > 0}. The final notion required in this paper is the function
W : R+ → R+ defined so that
x = W (x)eW (x)

for all x ∈ R+ . Since the function x 7→ xex is strictly increasing on R+ , it follows
that W (x) is a well-defined function on R+ . In the literature W (x) is known as
Lambert W function or product logarithm, see e.g. [3]. The value Ω = W (1) is
known as the omega constant and it satisfies ΩeΩ = 1, with the numerical value
Ω = 0.5671439 . . . .
3. Sufficient condition for ubiquitous semigroups
In this section we prove Theorem 1.1. We will do so in a series of lemmas. The
first of which is the following easy observation about products in the D-classes.
Recall that if x, y ∈ S, then by Dx we denote the D-class containing x and x ≤ y
if and only if S 1 xS 1 ⊆ S 1 yS 1 .
Lemma 3.1. Let S be a semigroup, and let z1 · · · zm ∈ Dx where x, z1 , . . . , zm ∈ S.
Then x ≤ zi · · · zj under the preorder on S for all i, j ∈ {1, . . . , m} with i ≤ j.
Proof. Let x, z1 , . . . , zm ∈ S be such that z1 · · · zm ∈ Dx . Then
S 1 xS 1 = S 1 z1 · · · zm S 1 ⊆ S 1 zi · · · zj S 1 ,

and so x ≤ zi · · · zj by definition for all i, j ∈ {1, . . . , m} with i ≤ j.



Next we give a condition for a semigroup S which restricts allowed products in
a given D-class.
Lemma 3.2. Let S ≤ Tn , let X be a generating set for S, and let x ∈ X be such
that rank(y1 xy2 ) < rank(x) for all y1 , y2 ∈ X where y1 , y2 ≥ x. Then only the
following products
x,

y1 · · · ym ,

xy1 · · · ym ,

or

y1 · · · ym x

where m ≥ 1, y1 , . . . , ym ∈ X \ {x} and y1 , . . . , ym ≥ x can be in Dx .
Proof. First observe that if x2 ∈ Dx , then both x and x2 have the same rank
by Lemma 2.2, in other words |im(x)| = |im(x2 )|. However, since x is a finite
degree transformation and im(x2 ) ⊆ im(x), it follows that im(x) = im(x2 ), and
so x acts as a bijection on im(x). Hence rank(x3 ) = rank(x), contradicting the
hypothesis of the lemma. Therefore x2 ∈
/ Dx , and since S 1 x2 S 1 ⊆ S 1 xS 1 , it follows
2
that x < x under the preorder on S. Similarly, for every y1 , y2 ∈ X such that
y1 , y2 ≥ x, it follows from Lemma 2.2 that y1 xy2 < x, since rank(y1 xy2 ) < rank(x)
and S 1 y1 xy2 S 1 ⊆ S 1 xS 1 .
Let z1 , . . . , zm ∈ X be such that z1 · · · zm ∈ Dx . Then x ≤ zi for all i by
Lemma 3.1. Hence there are k ∈ N, n1 , . . . , nk , m2 , . . . , mk ≥ 1, and m1 , mk+1 ≥ 0
such that
z1 · · · zm = y1,1 · · · y1,m1 xn1 y2,1 · · · yk,mk xnk yk+1,1 · · · yk+1,mk+1

6

JULIUS JONUŠAS AND SASCHA TROSCHEIT

where yi,j ∈ X \ {x} and yi,j ≥ x for all i and j. Here we are assuming that
m=

k
X
i=1

ni +

k+1
X

mi ,

i=1

z1 = y1,1 , z2 = y1,2 , and so on. Again by Lemma 3.1, if z = zi · · · zj is a subproduct
of z1 · · · zm , then x ≤ z. However x2 < x, and thus x2 is not a subproduct of
z1 · · · zm . That is, ni = 1 for all i ∈ {1, . . . , k}. Hence
z1 · · · zm = y1,1 · · · y1,m1 xy2,1 · · · xyk+1,1 · · · yk+1,mk+1 .
In a similar fashion, if yi,mi , yi+1,1 ∈ X \ {x} for yi,mi , yi+1,1 ≥ x, then as observed
above yi,mi xyi+1,1 < x, and so yi,mi xyi+1,1 is not a subproduct of z1 · · · zm . Hence
z1 · · · zm is one of the following products
x,

y1 · · · ym ,

xy1 · · · ym ,

y1 · · · ym x,

or xy1 · · · ym x

where m ≥ 1, y1 , . . . , ym ∈ X \ {x} and y1 , . . . , ym ≥ x. Hence it remains to show
that xy1 · · · ym x ∈
/ Dx .
Suppose that xy1 · · · ym x ∈ Dx for some m ≥ 1, y1 , . . . , ym ∈ X \ {x} such that
y1 , . . . , ym ≥ x. Then there are a, b ∈ S 1 such that axy1 · · · ym xb = x. Note that
unless a = b = 1, the product axy1 · · · ym xb is not in one of the above forms, and
so cannot be in Dx . Hence a = b = 1, and thus xy1 · · · ym x = x. Which is only
possible if y1 . . . ym acts bijectively on im(x). Thus y1 acts bijectively on im(x). If
im(ym x) = im(x), then it follows that
rank(ym xy1 ) = |im(ym xy1 )| = |im(ym x)| = |im(x)| = rank(x),
which contradicts the hypothesis of the lemma. Hence im(ym x) ( im(x). However,
it then follows that
rank(xy1 · · · ym x) ≤ | im(ym x)| < rank(x),
contradicting xy1 · · · ym x = x. Therefore xy1 · · · ym x ∈
/ Dx for all m ≥ 1 and all
y1 , . . . , ym ∈ X \ {x} such that y1 , . . . ym ≥ x, as required.

We prove a corollary in the case where the generating set is irredundant.
Corollary 3.3. Let S ≤ Tn , let X be an irredundant generating set for S, and
let x ∈ X be such that rank(z1 xz2 ) < rank(x) for all z1 , z2 ∈ X where z1 , z2 ≥ x.
Then pxuys ∈
/ Dx for all p, u, s ∈ S 1 and any x, y ∈ X such that xDy.
Proof. Let Y = {z ∈ X \ {x} : z ≥ x}. It follows from Lemma 3.2 that every
product of elements of X which is in Dx is of the form x, z, xz, or zx for some
product z of elements of Y . In particular, x ∈
/ Y as X is irredundant, and so x
occurs at most once in the product. If x, y ∈ X, xDy, and pxuys ∈ Dx = Dy for
some p, u, s ∈ S 1 , then there are a, b, c, d ∈ S 1 such that
axsyb = x and cxsyd = y.
Hence axscxsydb = x ∈ Dx , but x occurs twice in the product, which is a contradiction.

Finally, we prove Theorem 1.1. Observe that if a transformation semigroup
S ≤ Tn is such that all irredundant generating sets have the same cardinality, then
every irredundant generating set is a smallest generating set.
Theorem 1.1. Let S ≤ Tn and suppose that X is a generating set for S such that
rank(xyz) < rank(y) for all x, y, z ∈ X. Then S is ubiquitous.

RANDOM UBIQUITOUS TRANSFORMATION SEMIGROUPS

7

Proof. Let X ′ ⊆ X be irredundant. Then rank(xyz) < rank(y) for all x, y, z ∈ X ′ .
It is sufficient to show that every irredundant generating set is of the same cardinality. Moreover, without loss of generality we may assume that X is irredundant
and show that every irredundant generating set is of size |X|.
Let Y be an irredundant generating set for S. Let ≤d be a total order defined
on D-classes of S such that if D and D′ are D-classes of S and D ≤ D′ under
the partial order of D-classes, then D ≤d D′ . Let {D1 , . . . , Dd } be the set of all
D-classes of S, indexed so that Dd <d . . . <d D1 . For k ∈ {1, . . . , d}, define
!
!
k
k
[
[
Di .
and Yk = Y ∩
Di
Xk = X ∩
i=1

i=1

Let k ≥ 1 and let z ∈ Dk . By Lemma 3.1 if x1 · · · xm ∈ Dk where x1 , . . . , xm ∈ X,
then z ≤ xi , and so there is j ≤ k so that xi ∈ Dj for all i ∈ {1, . . . , m}. In other
words,
(1)

x1 · · · xm ∈ Dk where x1 , . . . , xm ∈ X =⇒ xi ∈ Xk for all i ∈ {1, . . . , m}.

The same argument applies to Y , and so
(2)

Dk ⊆ hXk i

and Dk ⊆ hYk i

for all k ≥ 1.
By the definition of the total order ≤d , the D-class D1 is maximal, and so both
X and Y intersect D1 non-trivially. For any i ≥ 2 and x1 , . . . , xi ∈ X1 , it follows
/ Dx1 = D1 , and so D1 = X1 . Hence Y1 ⊆ X1
from Corollary 3.3 that x1 · · · xi ∈
and D1 ∩ hY1 i = Y1 . However, since D1 is a maximal D-class, D1 ⊆ hY1 i, and thus
X1 = D1 ⊆ Y1 . In other words, X1 = Y1 = D1 .
For k ≥ 1, suppose that |Xk | = |Yk | and hXk i = hYk i. If X ∩ Dk+1 = ∅, then
Dk+1 ⊆ hXk i = hYk i. Hence Xk+1 = Xk and Yk+1 = Yk , and thus |Xk+1 | = |Yk+1 |
and hXk+1 i = hYk+1 i.
Suppose that X ∩ Dk+1 6= ∅. Then Dk+1 6⊆ hXk i = hYk i, and so Y ∩ Dk+1 6= ∅.
Suppose that t ≥ 0 is largest integer such that there is X ′ ⊆ X ∩ Dk+1 and
Y ′ ⊆ Y ∩ Dk+1 with |X ′ | = |Y ′ | = t and hXk , X ′ i = hYk , Y ′ i. If t = |Y ∩ Dk+1 |
and x ∈ X ∩ Dk+1 \ X ′ , then
x ∈ Dk+1 ⊆ hYk+1 i = hYk , Y ′ i = hXk , X ′ i,

/ Xk ∪ X ′ ⊆ X.
by (2). However, this is impossible, since X is irredundant and x ∈
′
Hence if t = |Y ∩ Dk+1 | then X = X ∩ Dk+1 , or in other words Xk+1 = Xk ∪ X ′
and Yk+1 = Yk ∪ Y ′ . Therefore, |Xk+1 | = |Xk | + t = |Yk | + t = |Yk+1 | and
hXk+1 i = hYk+1 i. We will now show that t = |Y ∩ Dk+1 |.
Suppose that t < |Y ∩ Dk+1 |. Then there is y ∈ Y ∩ Dk+1 \ Y ′ and y is equal to a
product of elements of Xk+1 by (2). It follows from Corollary 3.3 that if x1 · · · xm ∈
Dk+1 where x1 , . . . , xm ∈ X then there is at most one i ∈ {1, . . . , m} such that xi ∈
X ∩ Dk+1 , otherwise some subword of x1 · · · xm would not be an element of Dk+1 .
Since y ∈
/ Yk ∪ Y ′ , the irredundancy of Y implies that y ∈
/ hYk , Y ′ i = hXk , X ′ i.
It follows that y = p1 · · · pm xs1 · · · sl for some x ∈ X ∩ Dk+1 \ X ′ , m, l ≥ 0 and
si , pi ∈ Xk . Hence y ∈ hx, Xk i. Since x, y ∈ Dk+1 , it follows that there are a, b ∈ S 1
such that
ap1 · · · pm xs1 · · · sl b = ayb = x.

It follows from (1) and the discussion above that a, b ∈ hXk i1 , and so x ∈ hy, Xk i.
Moreover
x ∈ hy, Xk , X ′ i and y ∈ hx, Xk , X ′ i.

Therefore hx, Xk , X ′ i = hy, Xk , X ′ i = hy, Yk , Y ′ i, since hXk , X ′ i = hYk , Y ′ i. However |X ′ ∪ {x}| = |Y ′ ∪ {y}| = t + 1, which contradicts the maximality of t.

8

JULIUS JONUŠAS AND SASCHA TROSCHEIT

Therefore t = |Y ∩ Dk+1 | and by the previous paragraph hXk+1 i = hYk+1 i and
|Xk+1 | = |Yk+1 |.
By induction it follows that hXk i = hYk i and |Xk | = |Yk | for all k ∈ {1, . . . , d}.
In particular, Xd = X and Yd = Y , and thus |X| = |Y |, as required.

4. SmallGeneratingSet
In this section we return to the motivating question about the algorithm SmallGeneratingSet. First, we note that SmallGeneratingSet might return a generating
set which is not irredundant. For example, if the semigroup under investigation is
a group of size at least 2, the algorithm can first pick an identity and so return
a generating set which includes an identity. However, we show that under the assumptions of Theorem 1.1 the generating set returned by SmallGeneratingSet is
irredundant.
Lemma 4.1. Let S ≤ Tn and suppose that X is a generating set for S such that
rank(xyz) < rank(y) for all x, y, z ∈ X. Then SmallGeneratingSet returns an
irredundant generating set.
Proof. Let X = {x1 , . . . , xm } be the output of the algorithm, and assume that
the elements were selected in the order they are listed. Suppose that I ⊆ X is
irredundant and let xi ∈ X \ I. Since xi was selected by the algorithm, it means
that
xi ∈
/ hx1 , . . . , xi−1 i,
and so there exists xj ∈ I such that xi Dxj and j > i, otherwise xi ∈
/ hIi. Without
loss of generality, we can assume that i is the largest integer such that xi ∈ X \ I
and xi Dxj . Then there are a1 , . . . , aka , b1 , . . . , bkb ∈ I such that
a1 · · · aka xi b1 · · · bkb = xj .

Since xj ∈
/ hx1 , . . . , xi i, it follows that at least one of the a1 , . . . , aka , b1 , . . . , bkb is
xk for some k > i. It follows from Lemma 3.1 that xk ≥ xj , and since k > i implies
that xk  xi , we have that xk Dxi .
Finally, there are c1 , . . . , ckc , d1 , . . . , dkd ∈ I such that
and so

c1 · · · ckc xj d1 · · · dkd = xi ,

a1 · · · aka c1 · · · ckc xj d1 · · · dkd b1 · · · bkb = xj .
Which contradicts Corollary 3.3 as at least one of a1 , . . . , aka , b1 , . . . , bkb is xk .
Therefore, X = I.

The following result is then immediate from Theorem 1.1.
Corollary 4.2. Let S ≤ Tn and suppose that X is a generating set for S such
that rank(xyz) < rank(y) for all x, y, z ∈ X. Then SmallGeneratingSet returns a
smallest generating set.
5. Asymptotics
The main aim of this section is to show that if for some fixed k ≥ 1 we
choose x1 , . . . , xk ∈ Tn with uniform probability, then the probability Pk (n) that
hx1 , . . . , xk i is ubiquitous and the probability Wk (n) that SmallGeneratingSet returns a smallest generating set for hx1 , . . . , xk i both tend to 1 as n increases.
Lemma 5.1. Let X ⊆ Tn be such that rank(xyz) = rank(y) for some x, y, z ∈ X.
Then one of the following holds:
(i) there is x ∈ X such that hxi is a group;
(ii) there are distinct x, y ∈ X such that rank(xyx) = rank(y);

RANDOM UBIQUITOUS TRANSFORMATION SEMIGROUPS

9

(iii) there are mutually distinct x, y, z ∈ X such that rank(xyz) = rank(y).
Proof. Suppose that rank(xyz) = rank(y) for some x, y, z ∈ X and suppose that
not all x, y, and z are distinct. If x = y = z, then rank(x3 ) = rank(x), which is
only possible if x acts bijectively on im(x). However, in that case hxi is a group.
Hence we only need to consider the case that where exactly two of x, y, and z are
equal.
Suppose that x = y. Then rank(y 2 z) = rank(y), and since
rank(y) ≤ rank(y 2 ) ≤ rank(y 2 z) = rank(y),

it follows that rank(y 2 ) = rank(y). Hence by an argument similar to above hyi is a
group. The case y = z can be dealt with in an almost identical fashion. Therefore,
there are distinct x, y ∈ X such that rank(xyx) = rank(y).

In order to show that Pk (n) → 1 as n → ∞, for every n ∈ N, we define three
probabilities:
Gn is the probability that hxi is a group where x ∈ Tn is chosen
randomly with uniform probability

Tn is the probability that rank(xyx) = rank(y) where x, y ∈ Tn are
chosen randomly with uniform probability

Vn is the probability that rank(xyz) = rank(z) where x, y, z ∈ Tn
are chosen randomly with uniform probability.

For a fixed k ≥ 1, if x1 , . . . , xk ∈ Tn are chosen randomly with uniform probability,
it follows from Lemma 5.1 that the probability that there are x, y, z ∈ {x1 , . . . , xk }
such that rank(xyz) = rank(y) is bounded from above by
kGn + k(k − 1)Tn + k(k − 1)(k − 2)Vn .

Hence by Theorem 1.1

Pk (n) ≥ 1 − kGn − k(k − 1)Tn − k(k − 1)(k − 2)Vn ,

and the same lower bound hold for Wk (n) by Corollary 4.2. Hence in order to prove
Theorems 1.2 and 1.3 it suffices to show that Gn → 0, Tn → 0, and Vn → 0 as
n → ∞. We will do so in the remaining three subsections of the paper.
5.1. Gn tends to zero. We begin by obtain an expression for Gn in terms of n.
Lemma 5.2. Let n ∈ N. Then

n−1
n! X (n − k)k
.
Gn = n
n
k!
k=0

Proof. First observe that for any x ∈ Tn , the semigroup hxi is a group if and only
if x acts as a bijection on im(x). There are
n  
X
n n−r
r
r!
r
r=1

transformations x such that x acts bijectively on im(x). That is, if | im(x)| = r,
then there are nr choices for im(x), r! ways of bijectively mapping im(x) to itself,
and rn−r ways to map every point from {1, . . . , n}\im(x) to im(x). Since |Tn | = nn ,
the probability of randomly choosing x ∈ Tn such that hxi is a group is
n  
n
n! X rn−r
1 X n n−r
r
r! = n
.
Gn = n
n r=1 r
n r=1 (n − r)!

10

JULIUS JONUŠAS AND SASCHA TROSCHEIT

Finally, rewriting the equation using k = n − r we obtain

n
n−1
n! X rn−r
n! X (n − k)k
=
,
nn r=1 (n − r)!
nn
k!
k=0

as required.



In order to prove that Gn → 0 as n → ∞ we use an auxiliary function for which
we prove some analytical properties. Also recall that Ω ∈ R is a unique constant
which satisfies ΩeΩ = 1.
Lemma 5.3. Let F : (0, 1) → R be given by F (x) = x log(x−1 − 1) + x. Then F
Ω
has a unique maximum at α = 1+Ω
∈ (0, 1) and F (α) = Ω < 1.
Proof. First observe that F (x) is continuous on (0, 1), and F (x) → 0 as x → 0 and
F (x) → −∞ as x → 1. The first and second derivative are continuous and given
by
1
1
d2 F (x)
dF (x)
=−
=1−
+ log(x−1 − 1) and
.
2
dx
1−x
dx
(x − 1)2 x
2

F (x)
< 0 for all x ∈ (0, 1), but dFdx(x) → ∞ as x → 0 and so the derivative
Clearly, d dx
2
is positive in a neighbourhood of 0. But F (x) → −∞ as x → 1 and thus F has a
unique maximum at α implicitly given by


1−α
1
= 0,
+ log
1−
1−α
α

or in other words

α
= log
1−α



1−α
α



.

Ω
= Ω, by the definition of Ω. Hence α = 1+Ω
and




1−α
α
α
F (α) = α log
+α=α 1+
=
= Ω.
α
1−α
1−α

It then follows that

α
1−α



Finally, we conclude this section by describing the asymptotic behaviour of Gn .
Propostion 5.4. The probability Gn , that hxi is a group where x ∈ Tn is chosen
with uniform distribution, tends to 0 exponentially at the rate less than 1 − Ω.
Proof. By Lemma 5.2
Gn =

n−1
n! X (n − k)k
.
nn
k!
k=0

We use the Stirling approximation log n! = n log n − n + O(log(n)). Then
n−1

X (n − k)k
log Gn
= n−1 O(log(n)) − 1 + n−1 log
.
n
k!
k=0

Note that the last term can be bounded from above and below in the following way




n−1
X (n − k)k
(n − k)k
(n − k)k
log
max
≤ log
.
≤ log n
max
k!
k!
k!
k∈{0,...,n−1}
k∈{0,...,n−1}
k=0

Hence

log

n−1
X
k=0

(n − k)k
= log
k!

(n − k)k
max
k∈{0,...,n−1}
k!





+ O(log n),

RANDOM UBIQUITOUS TRANSFORMATION SEMIGROUPS

11

and so



log Gn
(n − k)k
.
= −1 + lim n−1 log
max
n→∞
n→∞
n
k∈{0,...,n−1}
k!
Considering the second term in the above equation, noting that for n ≥ 3 the
maximum does not occur at k = 0, it follows that




(n − k)k
(n − k)k
−1
−1
=
max
n log
n log
max
k∈{1,...,n−1}
k!
k!
k∈{0,...,n−1}
lim

n−1 k log(n − k) − k log k + k

− O(log k)

= max x log(x−1 − 1) + x − n−1 O (log n) ,
=

max

k∈{1,...,n−1}

x∈Mn

where Mn = { n1 , n2 , . . . , n−1
n }. Since F is continuous on
maxx∈Mn F (x) → maxx∈(0,1) F (x) as n → ∞. Therefore

log Gn
= −1 + lim n−1 log
lim
n→∞
n→∞
n
by Lemma 5.3 as required.

(n − k)k
max
k∈{0,...,n−1}
k!





(0, 1) we conclude that

= F (α) − 1 = Ω − 1 < 0,


5.2. Tn tends to zero. Recall that for n, r ∈ N such that r ≤ n, A(n, r) denotes
the set of partitions of {1, . . . , n} into r non-empty components. Similarly, define

B(n, r) to be the set of subsets of {1, . . . , n} of cardinality r. Then |B(n, r)| = nr .

Lemma 5.5. Let n ∈ N. Then the probability that rank(xyx) = rank(y), where
x, y ∈ Tn are chosen with uniform probability, is
r  
n   X
X
X Y
r
1 X n
r!
k!k n−r
|Ai |.
Tn = 2n
n r=1 r
k
{A1 ,...,Ar }∈A(n,r) B∈B(r,k) i∈B

k=1

Proof. Let x, y ∈ Tn be such that rank(xyx) = rank(y). We first show that im(xy)
is contained in a transversal of x. Let T be a transversal of xyx. Then xyx is
injective on T by definition, and so x is injective on (T)xy. Hence im(xy) = (T)xy
is contained in a transversal of x.
Suppose that rank(x) = r, rank(y)
 = k, and {A1 , . . . , Ar } ∈ A(n, r) are the
kernel classes of x. Then there are nr r! choices for x. Since
rank(y) ≥ rank(xy) ≥ rank(xyx) = rank(y),

it follows that rank(xy) = rank(y) = k, and also im(y) = im(xy). Since x is
injective on im(xy), there are
X Y
|Ai |
B∈B(r,k) i∈B

choices for im(y) = im(xy). That is, im(xy) contains at most one point from any
kernel class of x. Since (im(x))y = im(xy) = im(y), there are kr k! ways for y to
map im(x) to im(y). Finally, ({1, . . . , n}) \ im(x))y ⊆ im(y), and so there k n−r for
y to map ({1, . . . , n}) \ im(x)) to im(y). Hence there are in total
 
X Y
r
k!k n−r
|Ai |
k
B∈B(r,k) i∈B

choices for y. Therefore
r
n
1 XX
Tn = 2n
n r=1

X

k=1 {A1 ,...,Ar }∈A(n,r)

since |Tn | = nn .

   
n
r
r!
k!k n−r
r
k

X

Y

B∈B(r,k) i∈B

|Ai |,


12

JULIUS JONUŠAS AND SASCHA TROSCHEIT

Next, we simplify the expression for Tn .
Lemma 5.6. Let n, r, k ∈ N such that k ≤ r ≤ n. Then
n+k−r
X
X Y
X nn − s s 
|Ai | =
k s−k .
s
r−k
k
{A1 ,...,Ar }∈A(n,r) B∈B(r,k) i∈B

s=k

Proof.
Let B ∈ B(r, k) and {A1 , . . . , Ar } ∈ A(n, r) be fixed and denote the number
S
| {Ab : b ∈ B}| by s. Note that every Ai is non-empty, so k ≤ s ≤ n−(r −k). Now
suppose
 that only BSis fixed, then for every value of
 s ∈ {k, . . . , n + k − r}, there
are ns choices for {Ab : b ∈ B}, and there are n−s
r−k many choices to choose
{Ab : b ∈
/ B}. Hence we can write
n+k−r
k
X
X Y
X nn − s
X
Y
|Ai |.
|Ai | =
s
r−k
i=1
{A1 ,...,Ar }∈A(n,r) B∈B(r,k) i∈B

s=k

{A1 ,...,Ak }∈A(s,k)

The result follows by Lemma 2.3.



Finally, we prove the main lemma of this section.
Lemma 5.7. There exist r ∈ (0, 1) and c > 0 such that Tn ≤ cn7/2 rn .
Proof. Note that by Stirling’s approximation there are constants a, b > 0 such that
1
ann e−n ≤ n! ≤ bnn+ 2 e−n for all n ∈ N.
It follows from Lemmas 2.4, 5.5, and 5.6 that
r  
n+k−r
n   X
X nn − s s 
X
n
r
r!
k! k n−r
n2n Tn =
k s−k
r
k
s
r
−
k
k
r=1
k=1
s=k




r
n+k−r
n
X r
X n s n − s
X n
r!
k n−k k!
≤
(r − k)n−s−r+k k s−k .
r
k
s
k
r
−
k
r=1
k=1

s=k

Observe that
    



 


n
s
n n−k
n−k
n−s
n−k
n−r
(3)
=
and
=
.
s
k
k
n−s
n−s
r−k
r−k
s−k
Hence
r  
n+k−r
n   X
X nn − k n − r 
X
n
r n−k
2n
r!
k
k!
(r − k)n−s−r+k k s−k
n Tn ≤
r
k
k
r−k
s−k
r=1
k=1
s=k
 

 n−r 
r  
n   X
X
n
r n−k
n n−k X n−r
r!
k
k!
(r − k)n−r−i k i
=
r
k
k
i
r
−
k
r=1
i=0
k=1
 

r  
n   X
X
n
r n−k
n n − k n−r
r!
k
k!
r
.
=
r
k
k
r−k
r=1
k=1

It can also be show that

 
   
n n−k
n
r
=
,
k
r−k
r
k

(4)
and so

r  2
n
n  2 X
r
X
X
X
n!2
n
r
r!
r!
k! k n−k rn−r =
n Tn ≤
k n−k rn−r .
2
2
r
k
(n
−
r)!
k!(r
−
k)!
r=1
r=1
2n

k=1

k=1

Hence using Stirling’s formula there is a constant c > 0 such that
1
r
n
X
X
rr+ 2 e−r
n2n+1 e−2n
k n−k rn−r ,
n2n Tn ≤ c
2(n−r) e−2(n−r)
−k k k e−2(r−k) (r − k)2(r−k)
(n
−
r)
e
r=1
k=1

RANDOM UBIQUITOUS TRANSFORMATION SEMIGROUPS

13

which can be simplified to
n X
r
X

1

nrn+ 2 k n−2k
Tn ≤ c
er+k (n − r)2(n−r) (r − k)2(r−k)
r=1 k=1
(
)
1
nrn+ 2 k n−2k
2
≤ cn max
.
1≤r≤n
er+k (n − r)2(n−r) (r − k)2(r−k)
1≤k≤r

Let x, y ∈ [0, 1] be such that r = xn and k = yr = xyn. Then
)
(
n+ 21
n−2k
3
x
(xy)
Tn ≤ cn2 max n 2 r+k
1≤r≤n
e (1 − x)2(n−r) (x − xy)2(r−k)
1≤k≤r
(
)
2(n−xn)+ 12 n−2xyn
7
x
y
sup
≤ cn 2
exn+xyn (1 − x)2(n−xn) (1 − y)2(xn−xyn)
(x,y)∈[0,1]2
!n

x2(1−x) y 1−2xy
7
.
sup
≤ cn 2
ex(1+y) (1 − x)2(1−x) (1 − y)2x(1−y)
(x,y)∈[0,1]2
It only remains to show that the supremum in the above equation is less than 1.
In order to do so, define F : [0, 1]2 → R by
F (x, y) =

x2(1−x) y 1−2xy
.
ex(1+y) (1 − x)2(1−x) (1 − y)2x(1−y)

Note that F is continuous on a compact set [0, 1]2 , and so has a maximum. Hence
we only need to consider the boundary of the domain and stationary points of
F , that is points in [0, 1]2 where ∂F/∂x = 0 = ∂F/∂y. However, while it can
be immediately be deduced from plots, using any mathematical software, that the
maximum of F is strictly less than 1, we show it here analytically. To this end,
define the functions F1 , F3 : [0, 1] → R and F2 : [0, 1]2 → R by
F1 (x) =
and

x2(1−x)
,
(1 − x)2(1−x)

F2 (x, y) =

y 1−2xy
,
ex(1+y) (1 − y)2x(1−y)

F3 (y) = −1 − y − 2(1 − y) log(1 − y) − 2y log y.

Then F (x, y) = F1 (x)F2 (x, y), and it can be shown that ∂F2 (x, y)/∂x = F2 (x, y)F3 (y).
Also note that that F1 , F2 , and F3 are all continuous.
Since F1 (x) is continuous on a compact set, we can perform standard analysis
of stationary points. Then
dF1 (x)
= F1 (x)(1 + x log(1 − x) − x log x).
dx
and F1 (x) > 0 for all x ∈ (0, 1]. Thus the stationary points of F1 are either 0, 1, or
x0 , which is given by the equation
(1 + x0 log(1 − x0 ) − x0 log x0 ) = 0,

or in other words, x0 = 1/(1 + W (e−1 )) where W is the Lambert-W function.
It follows that F1 is bounded from above by max{F1 (0), F1 (1), F (x0 )}. A simple
algebraic manipulation gives
−

F1 (x0 ) = W (e−1 )

2
1+W (e−1 )−1

< 1.75.

Since F1 (0) = 0 and F1 (1) = 1, it follows that F1 (x) ≤ 1.75 for all x ∈ [0, 1]. We
also note here, that dF1 (x)/dx is positive for all x ∈ [0, x0 ).

14

JULIUS JONUŠAS AND SASCHA TROSCHEIT

Next we show that ∂F2 (x, y)/∂x ≤ 0 for all xy ∈ [0, 1]. First, observe that
F2 (x, y) ≥ 0 over [0, 1]2 . Since ∂F2 (x, y)/∂x = F2 (x, y)F3 (y), we are left to show
that F3 (y) ≤ 0 for y ∈ [0, 1]. Note that F3 (0) = −1, F3 (1) = −2, and
dF3 (y)
= −1 + 2 log(1 − y) − 2 log y
dy

and

2
d2 F3 (y)
=
.
dy 2
(y − 1)y

Since d2 F3 (y)/dy 2 < 0 for all y ∈ (0, 1), F3 has a unique maximum at (1 +
and


√
1
√
= 2 log(1 + e) − 2 < 0.
F3
1+ e

√

e)−1 ,

Hence ∂F2 (x, y)/∂x ≤ 0 for all x, y ∈ [0, 1], and so F2 (x, y) ≤ F2 (0, y) = y and in
particular F2 (x, y) ≤ 1.
For the last step of the proof consider

1−y
1
y
− y+1
2
F2 ( , y) = e
.
2
1−y

Then


dF2 ( 21 , y)
1
1
= F2 ( , y)(y −1 − + log y −1 − 1 )
dy
2
2

and the derivative has a single root at y0 = 1/(1 + W (e−1/2)). Hence if x ∈ [1/2, 1]
and y ∈ [0, 1], then
F2 (x, y) ≤ F2 (1/2, y) ≤ max{F2 (1/2, 0), F2 (1/2, 1), F2 (1/2, y0)} < 0.56,

and so F (x, y) ≤ 1.75 ·0.56 = 0.98. Since F (x, y) continuous on [0, 1]2 there is ε > 0
and β < 1 such that F (x, y) ≤ β for all x ∈ [1/2 − ε, 1] and all y ∈ [0, 1].
Finally, recall that x0 = 1/(1+W (e−1 )) > 0.78 and F1 (x) is increasing on [0, x0 ).
We observe that if x ∈ [0, 1/2 − ε] ⊆ [0, x0 ) then 0 = F1 (0) ≤ F1 (x) ≤ F1 (1/2 − ε) <
F1 (1/2) = 1. Since F2 (x, y) ≤ 1, it follows that F (x, y) ≤ F1 (1/2 − ε) < 1 for all
x ∈ [0, 1/2 − ε] and all y ∈ [0, 1]. Therefore F (x, y) ≤ max{β, F1 (1/2 − ε)} < 1 for
all x, y ∈ [0, 1], as required.

The following is an immediate corollary of Lemmas 5.5 and 5.7.
Corollary 5.8. The probability Tn , that rank(xyx) = rank(y) where x, y ∈ Tn are
chosen with uniform distribution, tends to 0 as n → ∞ exponentially fast.
5.3. Vn tends to zero. We start by finding an expression for Vn in terms of n.
The argument is similar to the proof of Lemma 5.5.
Lemma 5.9. Let n ∈ N. Then the probability that rank(xyz) = rank(y), where
x, y, z ∈ Tn are chosen with uniform probability, is
n
r min(r,k)       
n+t−k
X nn − ss
n n
n
r
1 XX X
r!
k!
ts−t .
t!tn−r
Vn = 3n
n r=1
r
s
r
r
−
k
k
t
t
s=t
t=1
k=1

Proof. If x, y, z ∈ Tn are such that rank(xyz) = rank(y). We first show that im(xy)
is contained in a transversal of z. Let T be a transversal of xyz. Then xyz is
injective on T by definition, and so z is injective on (T)xy. Hence im(xy) = (T)xy
is contained in a transversal of z.
Suppose that rank(x) = r, rank(z) = k, rank(y) = t, and {A1 , . . . , Ak } ∈ A(n,
 k)
n n
are the kernel classes
of
z.
Note
that
t
≤
r
and
t
≤
k.
Then
there
are
r
r r!

n
choices for x and k k! choices for z. Since
rank(y) ≥ rank(xy) ≥ rank(xyz) = rank(y),

RANDOM UBIQUITOUS TRANSFORMATION SEMIGROUPS

15

it follows that rank(xy) = rank(y) = t, and also im(y) = im(xy). Since z is injective
on im(xy), there are
X Y
|Ai |
B∈B(r,t) i∈B

choices for im(y) = im(xy). That is, im(xy) contains at most one
 point from any
kernel class of z. Since (im(x))y = im(xy) = im(y), there are rt t! ways for y to
map im(x) to im(y). Finally, ({1, . . . , n})\ im(x))y ⊆ im(y), and so there tn−r ways
for y to map ({1, . . . , n}) \ im(x)) to im(y). Hence there are in total
 
X Y
r
t!tn−r
|Ai |
t
B∈B(r,t) i∈B

choices for y. Therefore
n
r min(r,k)
1 XX X
Vn = 3n
n r=1
t=1
k=1

X

{A1 ,...,Ak }∈A(n,k)

      
n
n
n r
r!
k!
t!tn−r
r
k
r
t

X

Y

B∈B(r,t) i∈B

|Ai |,

since |Tn | = nn . It follows from Lemma 5.6 that
Vn =

n
r min(r,k)       
n+t−k
X nn − ss
n n
n
r
1 XX X
n−r
r!
k!
t!t
ts−t ,
n3n r=1
r
r
k
t
s
r
−
k
t
s=t
t=1
k=1

as required.



Finally, we prove the main two lemmas of this section. This is an analogue of
Lemma 5.7.
Lemma 5.10. There exist c > 0 such that


Vn ≤ cn5 

where
G(x, y, z) =

max

x,y,z∈(0,1]
z≤min(x,y)

n


G(x, y, z) ,

x1−x y 1−y z 1−2z
.
ex+y+z (1 − x)2(1−x) (1 − y)2(1−y) (x − z)x−z (y − z)y−z

Proof. We begin by applying the same strategy as in Lemma 5.7. That is we use
Lemma 2.4 to give an upper bound without Stirling numbers of the second kind
and then use equations (3) and (4). It follows that
n X
r min(r,k)
n+t−k
X
X nn − ss
X nn n r 
n−r
r!
k!
t!t
n Vn =
ts−t
r
r
k
t
s
r
−
k
t
s=t
r=1
t=1
3n

k=1

≤

n X
n min(r,k)
X
X 
r=1 k=1

t=1

n!
(n − r)!

2 

n!
(n − k)!

2

tn−t rn−r k n−k
(r − t)!(k − t)!t!

Replacing the sums with n times their maximal value we obtain after some algebraic
manipulation


(n!)4 k n−k rn−r tn−t
n3n Vn ≤ n3
max
1≤r≤n
((n − r)!(n − k)!)2 (r − t)!(k − t)!t!
1≤k≤n
1≤t≤min(r,k)

16

JULIUS JONUŠAS AND SASCHA TROSCHEIT

Using Stirling’s approximation Vn can be bounded by


n4n+2 k n−k rn−r tn−2t
3n
3
n Vn ≤ cn
max
1≤r≤n
(n − r)2(n−r) (n − k)2(n−k) (r − t)r−t (k − t)k−t er+k+t
1≤k≤n
1≤t≤min(r,k)

for some c > 0. Let x = r/n, y = k/n, and z = t/n. The above equation can be
rearranged to obtain

n


1−x 1−y 1−2z
x
y
z


Vn ≤ cn5  max
 .
x+y+z
2(1−x)
2(1−y)
x−z
y−z
x,y,z∈(0,1]
e
(1 − x)
(1 − y)
(x − z)
(y − z)
z≤min(x,y)

Hence

as required.




Vn ≤ cn5 

max

x,y,z∈(0,1]
z≤min(x,y)

n


G(x, y, z) ,



By inspection we see that G is continuous and bounded on
X = {(x, y, z) ∈ R3 | 0 < x, y < 1 and 0 < z < min(x, y)}.

We can further extend the definition of G to the closure X. It remains to find the
maximum of G, which we do in the last lemma of this section.
Lemma 5.11. There exists r ∈ (0, 1) such that G(x, y, z) ≤ r for all x, y, z ∈ [0, 1]
such that z ≤ min(x, y).
Proof. First we establish the value of G on the boundary X \ X. Clearly for either
x = 0, y = 0 or z = 0 we have G(x, y, z) = 0. If x = 1
G(1, y, z) =

e1+y+z (1
−x

−

y 1−y z 1−2z
.
− z)1−z (y − z)y−z

y)2(1−y) (1

By considering the derivative of x , we can show that x−x ≤ ee for all x ∈ [0, 1].
Hence
−1
yz
G(1, y, z) = e7e −1 · y+z .
e
Also note that x → xe−x is increasing on [0, 1], and so xe−x ≤ e−1 . Therefore
−1

G(1, y, z) ≤ e7e

−1

−3

By symmetry this also holds for y = 1.
Let x = z. Then
G(x, y, x) =

e2x+y (1

Similarly,
G(x, y, x) ≤ e

3e−1

−



≤ 0.7.

x2−3x y 1−y
.
− y)2(1−y) (y − x)y−x

x)2(1−x) (1

x1−x
ex (1 − x)1−x
1−x

2

·

y 1−y
.
ey (1 − y)1−y

x
By considering the derivatives of x → ex (1−x)
1−x , we can show that the function
1
has a unique maximum at x0 = 1+Ω . Hence after some algebraic manipulations we
get
1
Ω
x01−x0
= e− 1+Ω · Ω− 1+Ω = eΩ−1 ,
1−x
x
0
0
e (1 − x0 )
and so
−1
G(x, y, x) ≤ e3(e +Ω−1) < 1.
By symmetry the same holds for y = z.

RANDOM UBIQUITOUS TRANSFORMATION SEMIGROUPS

17

The partial derivatives of G are as follows


 
1−x
∂G(x, y, z)
(1 − x)2
+
G(x, y, z),
= log
∂x
x2 − xz
x


 
∂G(x, y, z)
1−y
(1 − y)2
+
G(x, y, z),
= log
∂y
y 2 − yz
y


 
1−z
(x − z)(y − z)
∂G(x, y, z)
G(x, y, z).
+
= log
∂z
z2
z
Suppose that (α, β, γ) ∈ (0, 1]3 is a stationary point of G(x, y, z). Note that
G(x, y, z) > 0 if x, y, z 6= 0, and so




(1 − α)2
1−α
1−β
(1 − β)2
log
+
+
= 0 and log
=0
α2 − αγ
α
β 2 − βγ
β
Hence
eβ
eα (1 − α)2
=β−
eα
−1

(5)

γ =α−

x−1

−1

(1 − β)2
eβ

2

(x−1)
is increasing and thus injective, implying
However, the function x → x − e ex
that α = β. Hence all stationary points of G(x, y, z) are of the form (α, α, γ).
Substituting α = β into ∂G(x, y, z)/∂z = 0 and rearranging we obtain that

1
α−γ
+ 2 log(
) = 1.
γ
γ
Combining the above equation with (5) we get that α satisfies
!
−1
eα
eα (1 − α)2
= 1.
(6)
+ 2 log
eα2 − eα−1 (1 − α)2
eα2 − eα−1 (1 − α)2
It can be shown that the derivative of the function given by the left hand side of
the above equation is


−1
e ex3 (x + 3) − ex (1 − x)2 (x2 + 2x − 1)
D(x) = −
.
2
(1 − x) ex2 − ex−1 (1 − x)2
Note that since the function in (5) is increasing, and so if α ≤ 0.587, then
e0.587 (1 − 0.587)2
γ ≤ 0.587 −
< 0,
e · 0.587
−1

which contradicts γ ∈ (0, 1]. Hence α > 0.587. It is easy to see that x → ex (1−x)2
is decreasing for x ∈ (0, 1) and that x → x2 + 2x − 1 is increasing for x ≥ −1. Thus
−1

ex (1 − x)2 (x2 + 2x − 1) ≤ 2e0.587 (1 − 0.587)2 < 1.88
−1

−1

for x ∈ [0.587, 1]. On the other hand, x → ex3 (x + 3) is increasing, and so for
x ≥ 0.587
ex3 (x + 3) ≥ e · 0.5873(0.587 + 3) > 1.97.

Therefore
ex3 (x + 3) − ex (1 − x)2 (x2 + 2x − 1) > 0
−1

for x > 0.587, and thus D(x) < 0, implying that the left handside of (6) is strictly
decreasing. Hence there is a unique value α satisfying the (6). Moreover, we can

18

JULIUS JONUŠAS AND SASCHA TROSCHEIT

see by inspection that 0.68152 < α < 0.68153. Since (5) is strictly increasing, it
also follows that 0.44403 < γ < 0.44407. Finally
G(α, α, γ) =
≤

α2(1−α) γ 1−2γ
e2α+γ (1 − α)4(1−α) (α − γ)2(α−γ )

0.681532(1−0.68153)0.444071−2·0.44407
0.44407)2(0.68153 −0.44403) e2·0.68152+0.44403

0.68153)4(1−0.68152)(0.68152 −

(1 −
< 0.999.

Therefor there exists r ∈ (0, 1) such that G(x, y, z) ≤ r for all x, y, z ∈ [0, 1] such
that z ≤ min(x, y).

The following is an immediate corollary of Lemmas 5.10 and 5.11, which concludes the proof of Theorems 1.2 and 1.3.
Corollary 5.12. The probability Vn , that rank(xyz) = rank(y) where x, y, z ∈ Tn
are chosen with uniform distribution, tends to 0 as n → ∞ exponentially fast.
References
[1] Vikraman Arvind and Jacobo Torán. The complexity of quasigroup isomorphism and the
minimum generating set problem. In Algorithms and computation, volume 4288 of Lecture
Notes in Comput. Sci., pages 233–242. Springer, Berlin, 2006.
[2] Peter J. Cameron. Dixon’s theorem and random synchronization. Discrete Math.,
313(11):1233–1236, 2013.
[3] Robert M. Corless, Gaston H. Gonnet, David E. G. Hare, David J. Jeffrey, and Donald E.
Knuth. On the Lambert W function. Adv. Comput. Math., 5(4):329–359, 1996.
[4] Andreas Distler and James D. Mitchell. Smallsemi - GAP package, Version 0.6.10, 2016.
[5] James East, Attila Egri-Nagy, James D. Mitchell, and Yann Péresse. Computing finite semigroups. to appear in J. Symbolic Comput.
[6] Véronique Froidure and Jean-Eric Pin. Algorithms for computing finite semigroups. pages
112–126, 1997.
[7] The GAP Group. GAP – Groups, Algorithms, and Programming, Version 4.8.7, 2017.
[8] Gracinda M. S. Gomes and John M. Howie. On the ranks of certain finite semigroups of
transformations. Math. Proc. Cambridge Philos. Soc., 101(3):395–403, 1987.
[9] Gracinda M. S. Gomes and John M. Howie. On the ranks of certain semigroups of orderpreserving transformations. Semigroup Forum, 45(3):272–282, 1992.
[10] Robert D. Gray. The minimal number of generators of a finite semigroup. Semigroup Forum,
89(1):135–154, 2014.
[11] John M. Howie. Fundamentals of Semigroup Theory. LMS monographs. Clarendon Press,
1995.
[12] Julius Jonušas, James D. Mitchell, and Marcus Pfeiffer. Parallel algorithms for computing
finite semigroups. preprint, 2017.
[13] James D. Mitchell et al. Semigroups - GAP package, Version 2.8.0, May 2016.
[14] Christos H. Papadimitriou and Mihalis Yannakakis. On limited nondeterminism and the
complexity of the V-C dimension. J. Comput. System Sci., 53(2, part 1):161–170, 1996.
Eighth Annual Structure in Complexity Theory Conference (San Diego, CA, 1993).
Julius Jonušas, Mathematical Institute, University of St Andrews, St Andrews,
KY16 9SS, UK.
E-mail address: julius.jonusas@st-andrews.ac.uk
Sascha Troscheit, Department of Pure Mathematics, University of Waterloo, 200
University Avenue West, Waterloo, N2L 3G1, Canada.
E-mail address: stroscheit@uwaterloo.ca

