On growth of the inverse semigroup of partially defined co–finite automorphisms of integers
The inverse semigroup of partially defined co– finite automorphisms of integers is considered. This semigroup is presented by generators and defining relations and its growth function is described.
Збережено в:
| Дата: | 2004 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | English |
| Опубліковано: |
Інститут прикладної математики і механіки НАН України
2004
|
| Назва видання: | Algebra and Discrete Mathematics |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/156412 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | On growth of the inverse semigroup of partially defined co–finite automorphisms of integers / O. Bezushchak // Algebra and Discrete Mathematics. — 2004. — Vol. 3, № 2. — С. 45–55. — Бібліогр.: 15 назв. — англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-156412 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1564122019-06-19T01:28:22Z On growth of the inverse semigroup of partially defined co–finite automorphisms of integers Bezushchak, O. The inverse semigroup of partially defined co– finite automorphisms of integers is considered. This semigroup is presented by generators and defining relations and its growth function is described. 2004 Article On growth of the inverse semigroup of partially defined co–finite automorphisms of integers / O. Bezushchak // Algebra and Discrete Mathematics. — 2004. — Vol. 3, № 2. — С. 45–55. — Бібліогр.: 15 назв. — англ. 1726-3255 2000 Mathematics Subject Classification: 20B27, 20M05, 20M18. http://dspace.nbuv.gov.ua/handle/123456789/156412 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
The inverse semigroup of partially defined co–
finite automorphisms of integers is considered. This semigroup is
presented by generators and defining relations and its growth function is described. |
| format |
Article |
| author |
Bezushchak, O. |
| spellingShingle |
Bezushchak, O. On growth of the inverse semigroup of partially defined co–finite automorphisms of integers Algebra and Discrete Mathematics |
| author_facet |
Bezushchak, O. |
| author_sort |
Bezushchak, O. |
| title |
On growth of the inverse semigroup of partially defined co–finite automorphisms of integers |
| title_short |
On growth of the inverse semigroup of partially defined co–finite automorphisms of integers |
| title_full |
On growth of the inverse semigroup of partially defined co–finite automorphisms of integers |
| title_fullStr |
On growth of the inverse semigroup of partially defined co–finite automorphisms of integers |
| title_full_unstemmed |
On growth of the inverse semigroup of partially defined co–finite automorphisms of integers |
| title_sort |
on growth of the inverse semigroup of partially defined co–finite automorphisms of integers |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2004 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/156412 |
| citation_txt |
On growth of the inverse semigroup of partially defined co–finite automorphisms of integers / O. Bezushchak // Algebra and Discrete Mathematics. — 2004. — Vol. 3, № 2. — С. 45–55. — Бібліогр.: 15 назв. — англ. |
| series |
Algebra and Discrete Mathematics |
| work_keys_str_mv |
AT bezushchako ongrowthoftheinversesemigroupofpartiallydefinedcofiniteautomorphismsofintegers |
| first_indexed |
2025-07-14T08:47:38Z |
| last_indexed |
2025-07-14T08:47:38Z |
| _version_ |
1837611466572693504 |
| fulltext |
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.
Algebra and Discrete Mathematics RESEARCH ARTICLE
Number 2. (2004). pp. 45 – 55
c© Journal “Algebra and Discrete Mathematics”
On growth of the inverse semigroup of partially
defined co–finite automorphisms of integers
O. Bezushchak
Communicated by V. I. Sushchanskii
Abstract. The inverse semigroup of partially defined co–
finite automorphisms of integers is considered. This semigroup is
presented by generators and defining relations and its growth func-
tion is described.
1. Introduction
One of the main trends in the theory of semigroups is the study of ob-
jects by means of certain semigroups connected with the different kind
of mathematical objects. For a graph, these special objects may be,
e.g., automorphisms, endomorphisms, extensive transformations, etc. For
the proposes of classifying and finding some characteristics of graphs
were studied partial endomorphism semigroups of graphs (L.M.Gluskin,
Yu.M.Vaz̆enin, A.Solomon, B.M.Schein, A.Vernitskii and others, see [13],
[16]). If the set of endomorphisms of a graph is extended by including
partial endomorphisms, we arrive at a more informative semigroup (in the
papers of L.M.Popova, A.M.Kalmanovic̆, C.J.Maxson, V.A.Molc̆anov,
V.H.Fernandes and others, see [3], [7], [9], [10], [11]).
Recently in modern combinatorial algebra has been observed the in-
creasing of interest in growth functions, particulary for groups (see [5],
[6], [15] and references therein), especially concerned with its relation-
ships with various properties of algebraic objects ([1], [2], [4], [8], [14]).
Also for many groups the growth function can be determined by calcu-
lated the growth function of some special monoid being an extension of
given group ([2], [12]).
2000 Mathematics Subject Classification: 20B27, 20M05, 20M18.
Key words and phrases: semigroup, growth function.
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.46 On growth of the inverse semigroup...
The object of this paper is to introduce a semigroup of co–finite par-
tial transformations (i.e. partial transformations with finite codomain)
defined on a poset and to investigate the structure and properties of this
semigroup. We consider the inverse semigroup ID∞ of partially defined
automorphisms of integers Z with a finite codomain, defined by the auto-
morphism group of poset Z. In Theorem 1 we describe semigroup ID∞
by generators and defining relations:
Theorem 1. The semigroup ID∞ is an inverse monoid, and has the
following generators and defining relations:
ID∞ =< a, b, f |
a2 = 1, bb−1 = b−1b = 1, aba = b−1, f2 = f, af = fa; (1)
fb−rfbr = b−rfbrf, r ∈ N > . (2)
Such definition of ID∞ makes it possible to compute its length func-
tion and therefore its growth function explicitly. We obtain that this
semigroup has the exponential growth in contrary the polynomiallity of
growth of the automorphism group of poset Z. Theorem 2 is devoted the
investigation of the growth function:
Theorem 2. The inverse monoid ID∞ has the exponential growth.
2. Preliminaries
Let M be a semigroup generated by a finite set S. Then we may consider
elements of M as words over the alphabet S and let h be a word in S.
We denote the element of M corresponding to h as h, and we define the
length of h, lw(h), as the word length of h with respect to S. Recall that
the length l(m) of an element m ∈ M (with respect to S) is the least
number of factors in all representations of m as a product of elements
of S, so l(m) = min{lw(h) : h = m}. Obviously for any m ∈ M the
length l(m) is great than 0, let’s put l(1) = 0 when the semigroup M is
a monoid. The function
γM,S : N → N (N is the set of all natural numbers)
defined by
γM,S(n) = |{w ∈ M : l(w) ≤ n}|
(where |E| means the cardinality of set E) is called the growth function
of M with respect to the set of generators S.
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.O. Bezushchak 47
We say that a function f : N → R is dominated by a function g : N →
R, denote by f ¹ g, if there are constants C1, C2, N0 ∈ N such that
f(n) ≤ C1 g(C2 n)
for all n ≥ N0. Two functions f, g : N → R are called equivalent, denoted
by f ∼ g, if f ¹ g and g ¹ f . It is well known that for any two
finite sets of generators S1, S2 of semigroup M the corresponding two
growth functions γM,S1
(n) and γM,S2
(n) are equivalent, that is to say a
semigroup growth is independent of the choice of generators. For this
reason let denote the growth function of M by γM (n) or briefly γ(n).
Note also that if |S| = k, then γ(n) ≤ kn.
A growth of semigroup M is called exponential if γ(n) ∼ en. A
growth of semigroup M is called polynomial if γ(n) ∼ nc for some c > 0.
A growth of semigroup M is called intermediate if M hasn’t neither an
exponential nor a polynomial growth.
3. General construction of the inverse monoid IG
For convenience, regarding the purpose of this paper, in what follows we
will always consider a monoid rather than a semigroup.
Let X be a nonempty poset. An order preserving partial automor-
phism of set X is a bijection g : Dom g → Ran g between subsets Dom g
and Ran g of set X, that is to say, g is a partial permutation of set X,
which preserves order on the set X. The set Dom g is the domain of the
automorphism g and Ran g is the range. The automorphism g is defined
in a point x ∈ X if and only if x ∈ Dom g. The set X\Dom g is the
codomain of g (let’s denote its by Codom g).
The composition of two partial automorphisms g1 and g2 is the partial
automorphism g1g2 with the domain Dom g1g2 = g−1
1 (Dom g2
⋂
Ran g1)
and defined on the domain by the condition g1g2(x) = g2(g1(x)) (here
the composition acts from the left to the right). For the partial automor-
phism g of set X its inverse is the automorphism g−1 with the domain
Dom g−1 = Ran g and the range Ran g−1 = Dom g such that the prod-
uct gg−1 is the identical map id|Ran g of set Ran g (or, equivalently, g−1g
is the identical map of set Dom g).
Let IS(X) be a set of all partial automorphisms of poset X. Then
IS(X) is closed with respect to the composition of automorphisms and
IS(X) is the inverse partial automorphism monoid action on the set X.
Let’s now G be an infinite group of automorphisms over a poset X,
acting transitively on X. For a subset Y ⊆ X and an automorphism g ∈
G let’s denote by gY the partial automorphism with Dom gY = X\ Y and
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.48 On growth of the inverse semigroup...
Codom gY = Y such that gY |Dom gY
= g|Dom gY
(here the symbol f |A
is used to denote the restriction of f onto the set A). We put separately
g∅ = g. The set IG of all such defined partial automorphisms gY with
a finite codomain Y forms the monoid under the composition. And it is
clear that any partial automorphism of IG is also a partial automorphism
of IS(X), i.e. the monoid IS(X) contains IG.
Definition 1. The inverse monoid IG are called an inverse monoid of
partially defined automorphisms of X with a finite codomain, defined by
the group G of partial order preserving automorphisms of poset X, acting
transitively on X.
For some fixed point x0 ∈ X by ex0
we denote a partial automorphism
with Codom ex0
= {x0}, which acts identically on Dom ex0
= X\ {x0}.
The partial automorphism ex0
is an idempotent of IG and
Proposition 1. Let S be a set of generators of G. Then the monoid IG
is generated by S
⋃
{ex0
}.
Proof. Let gY , where g ∈ G, Y = {y1, . . . , yk} ⊂ X, be an arbi-
trary element. The group G acts transitively on X, so that there
exists h1, . . . , hk ∈ G such that yh1
1 = x0, . . . , y
hk
k = x0. Then
h = h1ex0
h−1
1 . . . hkex0
h−1
k ∈ IG, Codom h = Y, h|X\Y = id|X\Y and
gY = hg. Therefore, IG ⊆< S, ex0
> .
The inclusion IG ⊇< S, ex0
> is obvious.
From Proposition 1 it is easy to obtain
Corollary 1. Every g ∈ ID∞ can be expressed in the form
g = w1ex0
w2ex0
. . . wt−1ex0
wt,
where w2, . . . , wt−1 ∈ G\{1}, w1, wt ∈ G, t ∈ N.
Corollary 2. 1. An idempotent of IG has the following form
w1ex0
. . . ex0
wt, where w2, . . . , wt−1 ∈ G\{1}, w1, wt ∈ G, t ∈ N,
such that (w1 . . . wt)|Y = id|Y for Y = {y1, . . . , yt−1} and yw1
1 = x0,
. . . , y
w1...wt−1
t−1 = x0.
2. All idempotents of IG form a lower semilattice.
Proof. 1. Let g ∈ IG be an idempotent, that is g = w1ex0
. . . ex0
wt,
where w2, . . . , wt−1 ∈ G\{1}, w1, wt ∈ G, t ∈ N, and g2 = g. Then
Codom g = {y1, . . . , yt−1}, where yw1
1 = x0, . . . , y
w1...wt−1
t−1 = x0,
and Codom g2 = {y1, . . . , yt−1, y̌1, . . . , y̌t−1}, where y̌w1...wtw1
1 = x0,
. . . , y̌
w1...wtw1...wt−1
t−1 = x0. Thus {y̌1, . . . , y̌t−1} ⊆ {y1, . . . , yt−1} and
(w1 . . . wt)|Dom g = (w1 . . . wt)
2|Dom g.
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.O. Bezushchak 49
Remark 1. We would like to make a notice that it is possible to de-
fine such construction for any relative algebra X with transitive action of
Aut X on X.
4. Presentation for the inverse monoid ID∞
Let G = D∞ be the automorphism group of integers Z, that is to say
D∞ =< a, b|a2 = 1, aba = b−1 >. And let’s denote by ID∞ the semi-
group of partially defined automorphisms of Z with a finite codomain
defined by D∞. Then from Proposition 1 we obtain that ID∞ is gen-
erated by following partial automorphisms a, b, f , where for all x ∈ Z
a : x → −x, b : x → x + 1, Codom f = {0} and for all x ∈ Z\{0}
f : x → x. Hence we can identify elements of semigroup ID∞ with cor-
respond semigroup words over the alphabet S = {a, b, f}.
Proposition 2. Every g ∈ ID∞ admits an unique representation as a
word of the form
h1 . . . hth, where hi = b−αifbαi for i ∈ {1, . . . , t}, h = bkaε, (3)
α1, . . . , αt ∈ Z such that α1 < . . . < αt, t ∈ N ∪ {0}, k ∈ Z, ε ∈ {0, 1}.
Proof. Since a2 = 1, aba = b−1 and also clearly that f2 = f, af = fa,
it follows that every g ∈ ID∞ admits a representation as a word of such
form g = bk1fbk2 . . . bks−1fbksaε, where k1, . . . , ks ∈ Z, ε ∈ {0, 1}. Then
g = bk1fb−k1 bk1+k2f . . . fb−k1−...−ks−1 bk1+...+ksaε. But elements bkfb−k
and blfb−l are commuted because of Corollary 2 they are idempotents.
Moreover, bkfb−kbkfb−k = bkfb−k, and this proves the existence of the
representation (3). Now let’s prove an unique of (3). Let g = h1 . . . hth =
h̃1 . . . h̃sh̃ be two representations of the form (3), where hi = b−αifbαi ,
i ∈ {1, . . . , t}, h = bk1aε1 , h̃j = b−βjfbβj , j ∈ {1, . . . , s}, h̃ = bk2aε2 .
Then Codom g = Codom (h1 . . . ht) = Codom (h̃1 . . . h̃s) and by virtue of
Corollary 2 (h1 . . . ht)|Dom g = (h̃1 . . . h̃s)|Dom g = id|Dom g we conclude
that h|Dom g = h̃|Dom g and hence h = h̃. Moreover,
Codom (h1 . . . ht) = {α1, . . . , αt}, Codom (h̃1 . . . h̃s) = {β1, . . . , βs}
and α1 < . . . < αt, β1 < . . . < βs. Therefore we can see easily that t = s
and α1 = β1, . . . , αt = βt.
Definition 2. Let g ∈ ID∞ be an arbitrary element. The canonical
form of this element is a representation as a word of the form (3) (let’s
denote the representation (3) of an element g by [g]). Also, the number
r ∈ {1, . . . , t}, such that α1 < . . . < αr < 0 ≤ αr+1 < . . . < αt, is called
the crossing index and is denoted by i([g]).
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.50 On growth of the inverse semigroup...
5. Proof of Theorem 1
Proof. It is easy to check that the relations (1) and (2) hold. Moreover,
from the proof of Proposition 2 we also can obtain the following commut-
ing of idempotents from ID∞ :
b−lfblb−kfbk = b−kfbkb−lfbl, l, k ∈ Z, l 6= k, (4)
where k = r + l. And by using relations (1) and (4) each elements can be
ambiguously reduced to the canonical form (3). If semigroup elements
g1 = b−α1fbα1 . . . b−αtfbαtbkaε1 and g2 = b−β1fbβ1 . . . b−βsfbβsblaε2 de-
fine the same partial automorphism over Z, then we can easily conclude
that t = s, α1 = β1, . . . , αt = βt, ε1 = ε2 and k = l in a way analo-
gous to that used in the proof of Proposition 2. Therefore, semigroup
elements, which are written in different canonical forms, define different
partial automorphisms. The theorem is completely proved.
Remark 2. The infinite system of relations (1) and (2) is independent,
i.e., none of these relations can be derived from the rest.
6. Length function
We have already been discussed that every element g of semigroup ID∞
is identified with a semigroup word over the alphabet S = {a, b, f} in the
canonical form (3). Then the length lw([g]) of semigroup word [g] is equal
to lw([g]) = |α1|+1+ |α1 −α2|+1+ . . .+ |αt−1 −αt|+1+ |αt + k|+ ε =
|α1|+ αt −α1 + |αt + k|+ t + ε, as α1 < . . . < αt. Denote by gπ the word
hπ(1) . . . hπ(t)h for some permutation π ∈ St. Likewise, the length of gπ
is equal to lw(gπ) =
|απ(1)|+1+|απ(1)−απ(2)|+1+. . .+|απ(t−1)−απ(t)|+1+|απ(t)+k|+ε, (5)
and
Proposition 3. For any arbitrary element g ∈ ID∞
l(g) = min
π∈St
{lw(gπ)}, (6)
where g = h1 . . . hth is the canonical form of element g.
Proof. Let π be a permutation in St such that lw(gπ) = minπ∈St
{lw(gπ)}.
The inequality l(g) ≤ lw(gπ) is obviously. Let d = d1d2 . . . dj be a semi-
group word such that l(g) = lw(d) = j < lw(gπ). Suppose that for
some i ∈ {1, . . . , j − 1} di = a. Then di+1 6= a. If di+1 = f it fol-
lows from (1) that d = d1 . . . di−1di+1didi+2 . . . dj , and hence di+2 6= a,
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.O. Bezushchak 51
di+2 6= f because in another way lw(d1 . . . di−1di+1didi+2 . . . dj) = j − 1
and l(g) < j. If di+1 = b, then similarly d = d1 . . . di−1di+1didi+2 . . . dj
and hence di+2 6= a. So, we may further rewrite d so that it has the
form d = bδ1fbδ2f . . . fbδqaµ, where δ2 6= 0, . . . , δq−1 6= 0, µ ∈ {0, 1} and
|δ1|+ . . .+ |δq|+(q−1)+µ = j. Our aim now to show that lw(d) = lw(gπ)
for some permutation π ∈ St. Since d = gπ by Proposition 2 we have that
h = bδ1+...+δqaµ and
bδ1fb−δ1bδ1+δ2fb−δ1−δ2 . . . bδ1+...+δq−1fb−δ1−...−δq−1 = h1 . . . ht
are idempotents. From l(g) = lw(d) it follows that all δ1, δ1 + δ2, . . . , δ1 +
. . . + δq−1 are different. Now the required equality follows from the com-
parison of codomains {α1, . . . , αt} and {δ1, δ1 + δ2, . . . , δ1 + . . .+ δq−1} of
idempotents under the consideration and Corollary 2.
We can compute the length function l(g) explicitly.
Proposition 4. Let g be an arbitrary element of ID∞, [g] is its canonical
form (3) and r = i([g]) is its crossing index. Then for k > 0
l(g) =
2αt − α1 + |α1 + k| + t + ε, if r 6= 0, t,
2αt + k + t + ε, if r = 0,
−α1 + |α1 + k| + t + ε, if r = t;
and for k ≤ 0
l(g) =
−2α1 + αt + |αt + k| + t + ε, if r 6= 0, t,
αt + |αt + k| + t + ε, if r = 0,
−2α1 − k + t + ε, if r = t.
Proof. It follows from (5) and (6) that for k > 0 the length of word gπ
will be the least when
π(1) = r + 1, . . . , π(t − r) = t, π(t − r + 1) = r, . . . , π(t) = 1, (7)
that is l(g) = lw(gπ) = lw(hr+1 . . . hthr . . . h1h). For k ≤ 0 the length will
be the least when
π(1) = 1, . . . , π(t) = t, (8)
and we have l(g) = lw(h1 . . . hrhr+1 . . . hth). It remains to count by using
(5) the length lw(gπ) in all cases which have been indicated above.
Definition 3. Let g be an arbitrary element of ID∞, [g] is its canonical
form (3) and r = i([g]) is its crossing index. An amplification canonical
form of element g (let’s denote it by [g]amp) is the representation g as a
word gπ, were π ∈ St is a permutation of the form (7) for k > 0 and the
form (8) for k ≤ 0.
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.52 On growth of the inverse semigroup...
7. Growth function for ID∞
From now let γ(n) be the growth function of ID∞, that is γ(n) is the
number of all irreducible elements in the semigroup ID∞ of a length not
more that n. We can to compute the growth function γ(n) explicitly in
the following way.
Let g ∈ ID∞ and hπ(1) . . . hπ(t)h, where h = bkaε, be the amplification
canonical form [g]amp of element g. Denote by k(g) the index k, by ε(g)
the index ε in h, and will be denote by t(g) the number t in [g]amp.
Now let’s fix some m ∈ N and find the number of all g from ID∞
such that l(g) = m, k(g) = 0, i([g]) = 0, ε(g) = 0 (denote this number by
Q1(m)). By Proposition 4 and relation (5) for all such elements we have
l(g) = m = 2αt + t = α1 +(α2−α1)+ . . .+(αt−αt−1)+αt + t. Count the
number p1,m,t of decompositions of αt = m−t
2 into t terms k1 = α1 ≥ 0,
k2 = α2 −α1 > 0, . . . , kt = αt −αt−1 > 0. So, p1,m,t is equal to
(
(m−t)/2
t−1
)
when m− t is even, and is equal to 0 when m− t is odd. The parameter t
varies from 1 to [m+2
3 ] (here [x] is the integer part of number x), because
of αt = m−t
2 ≥ t − 1. Hence Q1(m) =
∑[(m+2)/3]
t=1 p1,m,t.
Find the number of all g from ID∞ such that l(g) = m, k(g) = 0,
i([g]) 6= 0, t, ε(g) = 0 (denote this number by Q2(m)). Then we have
l(g) = m = 2(αt −α1) + t = −α1 + (α2 −α1) + . . . + (αt −αt−1) + αt + t.
Count the number p2,m,t of decompositions of αt − α1 = m−t
2 into t − 1
terms k1 = α2 − α1 > 0, . . . , kt−1 = αt − αt−1 > 0. So, p2,m,t is equal
to
(
(m−t)/2−1
t−2
)
when m − t is even, and is equal to 0 when m − t is odd.
The number q2,m,t of decompositions of m−t
2 into terms s1 = αt ≥ 0 and
s2 = −α1 > 0 is equal to m−t
2 when m − t is even, and is equal to 0
when m − t is odd. The parameter t varies from 1 to [m+2
3 ], because of
αt − α1 = m−t
2 ≥ t − 1. Hence Q2(m) =
∑[(m+2)/3]
t=1 p2,m,tq2,m,t.
Next find the number of all g from ID∞ such that l(g) = m, k(g) > 0,
i([g]) = 0, ε(g) = 0 (denote this number by Q3(m)). Then we have
l(g) = m = 2αt + t + k = α1 + (α2 −α1) + . . . + (αt −αt−1) + αt + t + k.
Count the number p3,m,t of decompositions of i = αt into t terms k1 =
α1 ≥ 0, k2 = α2 − α1 > 0, . . . , kt = αt − αt−1 > 0. So, p3,m,t is
equal to
(
i
t−1
)
. The parameter t varies from 1 to [m+1
3 ] as before, and
the parameter i varies from t − 1 to [m−t−1
2 ] because of i = αt. Hence
Q3(m) =
∑[(m+1)/3]
t=1
∑[(m−t−1)/2]
i=t−1 p3,m,t.
Now let’s find the number of all g from ID∞ such that l(g) = m,
k(g) > 0, r := i([g]) 6= 0, t, ε(g) = 0 (denote this number by Q4(m)).
Then we have l(g) = m = 2αt−α1 + |α1+k|+t = αr+1 +(αr+2−αr+1)+
. . .+(αt −αt−1)+ (αt −αr)+ (αr −αr−1)+ . . .+(α2 −α1)+ |α1 +k|+ t.
Count the number p4,m,t of decompositions of i = αt − α1 into t terms
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.O. Bezushchak 53
k1 = αr+1 ≥ 0, k2 = αr+2−αr+1 > 0, . . . , kt−r = αt−αt−1 > 0, kt−r+1 =
−αr > 0, kt−r+2 = αr − αr−1 > 0, . . . , kt = α2 − α1 > 0. So, p4,m,t is
equal to
(
i
t−1
)
. The parameter t varies from 1 to [m
2 ] and the parameter
i varies from t to m − t as before. Hence Q4(m) =
∑[m/2]
t=1
∑m−t
i=t p4,m,t.
Finitely, find the number of all g from ID∞ such that l(g) = m,
k(g) < 0, i([g]) 6= 0, t, ε(g) = 0 (denote this number by Q5(m)). Then
we have l(g) = m = −2α1 + αt + |αt + k| + t = −α1 + (α2 − α1) + . . . +
(αt − αt−1) + |αt + k| + t. Count the number p5,m,t of decompositions of
i = αt −α1 into t− 1 terms k1 = α2 −α1 > 0, . . . , kt−1 = αt −αt−1 > 0.
So, p5,m,t is equal to
(
i−1
t−2
)
. The number q5,m,t of decompositions of m−2t
into terms s1 = −α1 > 0, s2 = αt − α1 − t ≥ 0 and s3 = |αt + k| ≥ 0
is equal to (m−2t)(m−2t+1)
2 . The parameter t varies from 1 to [m−1
2 ] and
the parameter i varies from t to m − t − 1 as before. Hence Q5(m) =
∑[(m−1)/2]
t=1
∑m−t−1
i=t p5,m,tq5,m,t.
In the same way we can consider the another cases of Proposition 4
and count Q6(m), . . . , Q18(m), but its will be omitted.
Proposition 5. The growth function γ(n) of ID∞ is equal to the follow-
ing sum
n
∑
m=1
(Q1(m) + . . . + Q18(m)) .
8. Proof of Theorem 2
Now let’s prove Theorem 2.
Proof. Let us separately consider the sum
Σ(n) =
n
∑
m=1
Q1(m).
Denote by q(s, t) the binomial coefficient
( s−t
2
t−1
)
. Then we have
Q1(m) =
[m+2
3
]
∑
t=1
m−t is even
q(m, t).
Let N = [n
3 ]. Then q(2N +1), q(2N +2, 2), . . . , q(3N, N) ∈ {q(s, t), t ∈
{1, . . . , m−t}, m ∈ {1, . . . , n}, m−t is even}, that is such binomial coeffi-
cients are different components of sum Σ(n) because of 3N+1 = 3[n3 ] ≤ n.
So, Σ(n) > 2[n
3
] and hence ID∞ has the exponential growth.
The theorem is completely proved.
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.54 On growth of the inverse semigroup...
Acknowledgments
We are grateful to Vitalii Sushchanskii for introduction to the subject,
for encouragement and helpful conversations.
This paper was written during the visit of the author to Uppsala Uni-
versity, which was supported by The Swedish Institute. The financial
support of The Swedish Institute and the hospitality of Uppsala Univer-
sity are gratefully acknowledged.
References
[1] V.V.Belyaev, N.F.Sesekin, and V.I.Trofimov, Growth functions of semigroups and
loops, Zapiski Ural. Gos. Univ., 10 (1977) no.3 3-8.
[2] M.Brazil, Growth functions for some one–relator monoids, Communications in
Algebra, 21(9) (1993), 3135-3146.
[3] V.H.Fernandes, The monoid of all injective order preserving partial transforma-
tions on a finite chain, Semigroup Forum 62 (2001), 178-204.
[4] R.I.Grigorchuk, On the cancellation semigroups with polynomial growth, Matem.
Zametki 43 (1988), 305-319. [in Russian]
[5] R.I.Grigorchuk, V.V.Nekrashevich, and V.I.Sushchanskii Automata, dynamical
systems, and groups, Trudy Math. Inst. Steklov [Proc. Steklov Inst. Math.], 231
(2000), 134-214.
[6] M.Gromov, Groups of polynomial growth and expandihg maps, Inst. Hautes
Etudes Sci. Publ. Math. 53 (1981), 53-73.
[7] A.M.Kalmanovic̆, Partial endomorphism semigroups of graphs, Dopovidi Acad.
Nauk URSR, 2 (1965), 147-150. [in Russian]
[8] J.Lau, Degree of growth of some inverse semigroups, Journal of Algebra 204
(1998), 426-439.
[9] C.J.Maxson, Semigroups of order–preserving partial endomorphisms on trees, I,
Colloquim Mathematicum, XXXII (1974), 25-37.
[10] V.A.Molc̆anov, Semigroups of mappings on graphs, Semigroup Forum 27 (1983),
155-199.
[11] L.M.Popova, Generation relations of partial endomorphism semigroup of a finite
linearly ordered set, Uc̆. Zap. Leningrad. Gos. Ped. Inst., 238 (1962), 78-88. in
Russian
[12] I.I.Reznicov and V.I.Sushchanskii, Two-state Mealy automata of intermediate
growth over a two-letter alphabet, Mathematical Notes, vol. 72, no. 1 (2002),
90-104.
[13] B.M.Schein, Endomorphisms of finite symmetric inverse semigroups Journal of
Algebra 198 (1997), 300-310.
[14] V.I.Trofimov, The growth functions of finitely generated semigroups, Semigroup
Forum 21 (1980), 351-360.
[15] V.A.Ufnarovskii, Combinatorial and asymptotic methods in algebra, in: Current
Problems in Mathematics. Fundamental Directions [in Russian], vol. 20, VINITI,
Moscow, 1988, vol. 57, VINITI, Moscow, 1990, pp. 5-177.
Jo
u
rn
al
A
lg
eb
ra
D
is
cr
et
e
M
at
h
.O. Bezushchak 55
[16] A.Vernitskii, Semigroups of order–decreasing graph endomorphisms, Semigroup
Forum 58 (1999), 222-240.
Contact information
O. Bezushchak Department of Mechanics and Mathemat-
ics, Kyiv Taras Shevchenko University, 64,
Volodymyrska st., 01033, Kyiv, UKRAINE
E-Mail: bezusch@univ.kiev.ua
Received by the editors: 29.03.2004.
|