Rational Growth of a Class of Inverse Semigroups

Joseph Lau

School of Mathematics and Statistics, University of Sydney, N.S.W. 2006, Australia.

August 1996, revised January 1997

We give a necessary condition for a finitely presented Rees quotient of a free inverse semigroup to have rational growth. Using related techniques we give a new proof that non-monogenic free inverse semigroups have irrational growth. A new criterion for polynomial growth is proved and used to show that polynomial growth implies rational growth. However we give an example of such a semigroup which has rational and exponential growth.

§1 Introduction

In [2] Easdown and Shneerson initiated the study of growth of finitely presented Rees quotients of free inverse semigroups. Growth was shown to be polynomial or exponential for semigroups from this class and an algorithm given to recognise which type of growth occurs [2, Section 3]. In Theorem (4.8) below we give a sufficient condition for rational growth, which is used in Theorem (5.3) to show that polynomial growth implies rational growth. Other sufficient conditions for rational growth are given in Proposition (4.10) and Theorem (5.5). Brazil [1] has shown that non-monogenic free inverse semigroups have irrational growth, using techniques from functional analysis. We give a new proof of this result in Section 3.

§2 Preliminaries

We assume familiarity with the basic definitions and elementary results from the theory of semigroups, which can be found in [4]. Let S be a semigroup generated by a finite subset X. Recall that the length l(t) of an element t ∈ S (with respect to X) is the least number of factors in all representations of t as a product of elements of X. Let

g_{S}(m) = |{t ∈ S | l(t) ≤ m}|.

We say that S has polynomial growth if there exist natural numbers q and d such that

g_{S}(m) ≤ qm^{d}

for all natural numbers m, and exponential growth if there exists a real number α > 1 such that

g_{S}(m) ≥ α^{m}

for all sufficiently large m. It is clear that if S has polynomial [exponential] growth with respect to a given finite set of generators then it has polynomial [exponential] growth with respect to any finite set of generators. Clearly, if S contains a noncyclic free subsemigroup then S has exponential growth.

The growth series of S with respect to X is defined to be the usual generating function for the sequence g_{S}(m):

g_{S}(z) = ∑_{m=0}^{∞} g_{S}(m)z^{m}.

A semigroup S is said to have rational growth if g_{S}(z) is a rational function of z for some choice of X. In this paper it is more convenient to work with a slightly different series. We define a sequence

h_{S}(m) = |{t ∈ S | l(t) = m}|

and let h_{S}(z) be its generating function. Since clearly h_{S}(m) = g_{S}(m) − g_{S}(m − 1), we have

h_{S}(z) = (1 − z)g_{S}(z).

Therefore S has rational growth if and only if h_{S}(z) is a rational function of z.

Throughout this paper we shall denote the subring of rational functions in ℝ[[z]] by Rat[[z]]. That is Rat[[z]] = ℝ[[z]] ∩ ℝ(z). An element in Rat[[z]] can be written as \frac{p(z)}{q(z)} for some polynomials p(z) and q(z) such that q(z) has nonzero constant term. It can be easily checked that Rat[[z]]^{∗}, the group of units of Rat[[z]], is precisely ℝ[[z]]^{∗} ∩ Rat[[z]], the elements in Rat[[z]] whose series expansions have nonzero constant term.

Let A be a finite alphabet. We denote the free semigroup and free inverse semigroup over A by F_{A} and F I_{A} respectively. Equality in F_{A} is denoted by ∘ . Recall that a word w is reduced if w does not contain xx^{−1} as a subword for any letter x ∈ A ∪ A^{−1}.

Recall that elements of F I_{A} may be regarded as birooted word trees, the terminology and theory of which are explained in [4, Chapter 2] (see also [2, Section 2]). Thus if u ∈ F_{A∪A^{−1}}, then regarded as an element of F I_{A}, u may be represented as a birooted tree

φ(u) = (T (u), α(u), β(u)).

Recall that u is an idempotent of F I_{A} if and only if α(u) = β(u). Given a birooted word tree B = (T, α, β), we shall adopt the following notation:

(i) e(B) = max{d(α, v) | v ∈ T },

(ii) for m ∈ ℕ, B|_{m} = (T |_{m}, α, α), where T |_{m} is the subtree of T obtained by deleting all vertices of distance greater than m away from α, and all edges incident on such vertices.

It is often convenient to adjoin an identity called 1 to F I_{A} and adopt the convention that l(1) = 0 and φ(1) = (∘, ∘, ∘), the null birooted tree consisting of one vertex.

Given two trees B_{1} = (T_{1}, α_{1}, β_{1}) and B_{2} = (T_{2}, α_{2}, β_{2}), define B_{1} ⊕ B_{2} = (T, α_{1}, β_{2}) where T is the word tree obtained by ‘pasting’ T_{1} and T_{2} together, identifying β_{1} with α_{2} and then further identifying any isomorphic paths from the common vertex β_{1} = α_{2}. Note that B_{1} ⊕ B_{2} = φ(φ^{−1}(B_{1})φ^{−1}(B_{2})).

A birooted word tree (T, α, β) on A is said to be planted if it is null or if it is non-null and α is a leaf of the tree (that is, α is adjacent to exactly one vertex of T). We shall refer to a birooted word tree which is planted simply as a planted tree.

Given a non-null planted tree P = (T, α, β), we shall adopt the following notation:

(i) γ(P) is the unique vertex of T adjacent to α, (ii) the label of P, denoted by label(P), is the label of the edge α → γ(P).

Let P_{1} = (T_{1}, α_{1}, α_{1}) and P_{2} = (T_{2}, α_{2}, α_{2}) be two planted trees representing idempotents, with P_{1} ≠ φ(1). If P_{2} = φ(1), or label(P_{1}) ≠ label(P_{2})^{−1}, then define P_{1} ⊙ P_{2} to be the planted word tree (T, α_{1}, α_{1}), where T is the word tree obtained by ‘pasting’ T_{1} and T_{2} together, identifying γ(P_{1}) with α_{2} and then further identifying any isomorphic paths from the common vertex γ(P_{1}) = α_{2}. The reader can easily verify that order is unimportant where the operation ⊙ is iterated.

Let P be a planted tree representing an idempotent with label x. Then P can be uniquely expressed in the form

P = φ(x) ⊕ P_{1} ⊕ ⋯ ⊕ P_{s} ⊕ φ(x^{−1}),

where s ≥ 0, P_{1}, …, P_{s} are non-null planted trees with distinct labels, and for each i, P_{i} represents an idempotent and label(P_{i}) ≠ x^{−1}. We shall call P_{1}, …, P_{s} and the null tree the components of P.

§3 Free Inverse Semigroups

In this section we give a new proof of a result due to Brazil [1], that the growth series for F I_{{x_{1},...,x_{n}}} is irrational if and only if n ≥ 2. While being an interesting result in its own right, the proof also illustrates some counting techniques employed in the next section.

Let A = {x_{1}, …, x_{n}}. As was mentioned earlier, elements of S = F I_{A}^{1} can be regarded as birooted word trees. We will ‘build’ the series h_{S}(z) from the growth series for certain types of idempotents.

For x ∈ A ∪ A^{−1}, define the sets
A(x) = {e ∈ E(S) | φ(e) is a planted tree with label x} ∪ {1},
B(x) = {u ∈ S \ E(S) | φ(u) is a planted tree with label x}.

By symmetry, for any given natural number m, the integers

a_{m} = |{e ∈ A(x) | l(e) = m}| and b_{m} = |{u ∈ B(x) | l(u) = m}|

are independent of x. Denote the generating functions of the corresponding sequences by a(z) and b(z) respectively.

Now clearly a_{0} = 1 and a_{1} = 0. Suppose m ≥ 2. If e ∈ A(x) and l(e) = m, then

φ(e) = φ(xx^{−1}) ⊙_{y} φ(e_{y})

where y ranges over (A ∪ A^{−1}) \ {x^{−1}}, e_{y} is some element of A(y) for each y, such that ∑ l(e_{y}) = m − 2. Therefore

a_{m} =  ∑_{{m_{1}+···+m_{2n−1} \atop =m−2}}a_{m_{1}} ⋯ a_{m_{2n−1}}  for m ≥ 2.

Translating into generating functions, this gives

a(z)^{2n−1} = ∑_{m≥0}( ∑_{{m_{1}+···+m_{2n−1} \atop =m}}a_{m_{1}} ⋯ a_{m_{2n−1}})z^{m} = ∑_{m≥0} a_{m+2}z^{m},

and hence

z^{2}a(z)^{2n−1} = a(z) − 1.  (1)

Next we turn to deriving an identity for b(z). Clearly b_{0} = 0. Suppose m ≥ 1, u ∈ B(x) and l(u) = m. There are two possibilities. If β(u) = γ(u), then

φ(u) = φ(x) ⊕_{y} φ(e_{y})

where y ranges over (A ∪ A^{−1}) \ {x^{−1}}, e_{y} ∈ A(y) for each y, and ∑ l(e_{y}) = m − 1. If β(u) ≠ γ(u), then there is an x′ ∈ (A ∪ A^{−1}) \ {x^{−1}} such that

φ(u) = (φ(x) ⊕_{y} φ(e_{y})) ⊕ φ(u′)

where y ranges over (A ∪ A^{−1}) \ {x′, x^{−1}}, e_{y} ∈ A(y) for each y, u′ ∈ B(x′), and l(u′) + ∑ l(e_{y}) = m − 1. Because there are 2n − 1 choices for x′, we get

\begin{aligned}b_{m} & = ∑_{{m_{1}+···+m_{2n−1} \atop =m−1}}a_{m_{1}} ⋯ a_{m_{2n−1}} + (2n − 1)a_{m_{1}} ⋯ a_{m_{2n−2}}b_{m_{2n−1}} \\ & = a_{m+1} + (2n − 1) ∑_{{m_{1}+···+m_{2n−1} \atop =m−1}}a_{m_{1}} ⋯ a_{m_{2n−2}}b_{m_{2n−1}}, \end{aligned}

and hence

b(z) = (2n − 1)za(z)^{2n−2}b(z) + \frac{1}{z}(a(z) − 1).  (2)

Finally suppose u ∈ S and l(u) = m. Again we have two cases. If α(u) = β(u), then

φ(u) = ⊕_{y∈A∪A^{−1}}φ(e_{y})

where e_{y} ∈ A(y) for each y, and ∑ l(e_{y}) = m. If α(u) ≠ β(u), then there is an x ∈ A ∪ A^{−1} such that

φ(u) = (⊕_{y}φ(e_{y})) ⊕ φ(u′)

where y ranges over (A ∪ A^{−1}) \ {x}, e_{y} ∈ A(y) for each y, u′ ∈ B(x), and l(u′) + ∑ l(e_{y}) = m. Because there are 2n choices for x, we get

h_{S}(m) = ∑_{{m_{1}+···+m_{2n} \atop =m}}a_{m_{1}} ⋯ a_{m_{2n}} + 2na_{m_{1}} ⋯ a_{m_{2n−1}}b_{m_{2n}}

for all m ≥ 0. Therefore

h_{S}(z) = a(z)^{2n−1}(2nb(z) + a(z)).  (3)

We can now show that h_{S}(z) is irrational if n ≥ 2. The result depends on the following lemmas.

(3.1) Lemma Suppose that f(z) ∈ ℝ[[z]] and f(z) − 1 = z^{s}f(z)^{t} for some integers s ≥ 1, t ≥ 2. Then f(z) is irrational.

Proof. Suppose f(z) = \frac{p(z)}{q(z)} for some polynomials p(z) and q(z). We can assume that p(z) and q(z) have no nonconstant common factors in ℝ[z]. Then

z^{s}p(z)^{t} = q(z)^{t−1}(p(z) − q(z)).

Thus q(z) divides z^{s}p(z)^{t} in ℝ[z]. Since q(z) has a nonzero constant term (see comments following the definition of Rat[[z]]), it has no common factor with z^{s} either. Therefore q(z) is a constant and f(z) is a polynomial. Considering the degrees of the polynomials on both sides of f(z) − 1 = z^{s}f(z)^{t}, this is easily seen to be impossible. □

(3.2) Lemma Suppose that f(z) ∈ ℝ[[z]] and for some natural number t there exist α(z), β(z) ∈ Rat[[z]] such that

zα(z)f(z)^{t} = f(z) + β(z).

Suppose also that for some natural number k ≥ 1, there exist g_{i}(z) ∈ Rat[[z]] such that

f(z)^{k} = ∑_{i=0}^{k−1} g_{i}(z)f(z)^{i}.

Then f(z) ∈ Rat[[z]].

Proof. If t ≤ 1 or k = 1 then one of the above equations will imply that f(z) ∈ Rat[[z]]. So we can assume k, t ≥ 2.

Using the fact that Rat[[z]] is a subring of ℝ[[z]], it can easily be shown by induction that for all m ≥ k,

f(z)^{m} = ∑_{i=0}^{k−1} f_{i}(z)f(z)^{i}

for some f_{i}(z) ∈ Rat[[z]]. In particular,

f(z)^{k+t−2} = ∑_{i=0}^{k−1} h_{i}(z)f(z)^{i}

for some h_{i}(z) ∈ Rat[[z]]. Therefore

f(z)^{k−1} + β(z)f(z)^{k−2} = zα(z)f(z)^{k+t−2} = ∑_{i=0}^{k−1} zα(z)h_{i}(z)f(z)^{i}

and, rearranging the terms,

(1 − zα(z)h_{k−1}(z))f(z)^{k−1} = ∑_{i=0}^{k−2} zα(z)h_{i}(z)f(z)^{i} − β(z)f(z)^{k−2}.

Now 1 − zα(z)h_{k−1}(z) has nonzero constant term, and so is in Rat[[z]]^{∗}. Therefore

f(z)^{k−1} = ∑_{i=0}^{k−2} g′_{i}(z)f(z)^{i}

for some g′_{i}(z) ∈ Rat[[z]]. We can repeat the process and decrement k each time until we get to the case k = 1. □

(3.3) Theorem F I_{{x_{1},...,x_{n}}} has irrational growth if and only if n ≥ 2.

Proof. Suppose n ≥ 2. From (2) we have

b(z)z(1 − (2n − 1)za(z)^{2n−2}) = a(z) − 1.

Mutiplying both sides by a(z) and using (1), this becomes

b(z)(za(z) − (2n − 1)(a(z) − 1)) = a(z)(a(z) − 1).

Putting this into (3) and using (1) again gives

\begin{matrix}h_{S}(z)z^{2} & (za(z) − (2n − 1)(a(z) − 1)) \\ = & (a(z) − 1)a(z)(2n(a(z) − 1) + za(z) − (2n − 1)(a(z) − 1)) \\ = & (a(z) − 1)a(z)(a(z) − 1 + za(z)). \end{matrix}

Suppose that h_{S}(z) is rational. Then by rearranging the previous equation, (1 + z)a(z)^{3} can be expressed in the form

g_{2}(z)a(z)^{2} + g_{1}(z)a(z) + g_{0}(z)

for some g_{i}(z) ∈ Rat[[z]]. Since 1 + z ∈ Rat[[z]]^{∗}, a(z)^{3} can also be expressed in this form. By (1) and Lemma (3.2), a(z) ∈ Rat[[z]]. But by (1) and Lemma (3.1), a(z) is irrational, which yields a contradiction. Therefore h_{S}(z) cannot be rational.

For n = 1, the equations (1), (2) and (3) still hold, and

a(z) = \frac{1}{1 − z^{2}} and h_{S}(z) = \frac{1}{(1 + z)(1 − z)^{3}} .

□

We have shown that, in the case of free inverse semigroups, h_{S}(z) can be built out of the growth series a(z) for certain idempotents, and the rationality of h_{S}(z) depends on that of a(z). This motivates the general construction in the next section.

§4 Rational Growth

In this section we give a sufficient graphical condition for a Rees quotient of a finitely generated free inverse semigroups by a finitely generated ideal to have rational growth series. Along the way we shall ‘build’ h_{S}(z) from some component series, and give an algorithm for doing so. First we review some terminology from graph theory.

By a cycle in a directed graph we mean a path which starts and finishes at the same vertex. By a loop at a vertex v we mean a cycle which begins at v using no other vertex more than once. If there is a path from u to v, we say the vertex u is reachable from v. The strongly connected components of a directed graph are the equivalence classes of vertices under the ‘are mutually reachable’ relation.

Let 𝔐_{F I} denote the class of finitely presented inverse semigroups S with zero having a presentation of the form

S = ⟨A | c_{i} = 0 for i = 1, …, k⟩

where A is some finite alphabet, k some nonnegative integer, c_{i} ∈ F_{A∪A^{−1}} for i = 1 to k. Then 𝔐_{F I} is precisely the class of Rees quotients of finitely generated free inverse semigroups by finitely generated ideals. We shall write A ∪ A^{−1} = {x_{1}, x_{2}, …, x_{2n}} and put

d + 1 = max{3, |c_{i}| | i = 1, …, k},

where |c_{i}| denotes the length of c_{i} with respect to F_{A∪A^{−1}}. By our definition, d ≥ 2. This is a slight modification of the convention in [2], where it is assumed d ≥ 1. The reasons for this definition are given in the remarks following Theorem (4.8). Also we have the following useful criterion, which lies behind much of the proofs which follow and ensures the words we count are not zero in the semigroup.

(4.1) Lemma Let w ∈ F_{A∪A^{−1}}. Then w = 0 in S if and only if T (w) contains T (c_{i}) as a subtree for some i.

We will now define a directed graph Γ′_{S}, depending on the presentation of S, called the word tree graph of S:

(i) the vertices of Γ′_{S} are planted trees P = (T, α, α) on A satisfying the properties that e(P) = d and φ^{−1}(P) is nonzero in S; (ii) there is a directed edge from vertex P to vertex Q if Q|_{d−1} is a compo-

nent of P and φ^{−1}(P ⊙ Q) is nonzero in S.

Note that if Q|_{d−1} is a component of P, then label(P) ≠ label(Q)^{−1}, so P ⊙Q is defined. Furthermore (P ⊙ Q)|_{d} = P.

Denote the set of vertices of Γ′_{S} by V (Γ′_{S}). For P ∈ V (Γ′_{S}), define

V (P) = {P′ ∈ V (Γ′_{S}) | P → P′ is an edge in Γ′_{S}},
V_{i}(P) = {P′ ∈ V (P) | label(P′) = x_{i}},  for i = 1, …, 2n.

Here the label of a vertex in Γ′_{S} is simply its label as a planted tree.

For each vertex P in Γ′_{S} define A(P) to be the set of u ∈ F I_{A} such that u is nonzero in S, and φ(u) is a planted word tree with φ(u)|_{d} = P. For r, m ∈ ℕ put

\begin{aligned}A(P, r, m) & = \{u ∈ A(P) | l(u) = m, d(α(u), β(u)) = r\}, and \\ B(P, m) & = \{u ∈ A(P) | l(u) = m, d(α(u), β(u)) > 0\}. \end{aligned}

Let a(P, r, m) = |A(P, r, m)| and b(P, m) = |B(P, m)|. Denote their generating functions by a(P, r)(z) and b(P)(z) respectively.

Let P be a vertex of Γ′_{S} with label x_{j}. Then P can be uniquely expressed in the form

P = φ(x_{j}) ⊕ P_{1} ⊕ ⋯ ⊕ P_{2n} ⊕ φ(x_{j}^{−1}),

where P_{k} is null for k such that x_{k} = x_{j}^{−1} and, for each i, either P_{i} is null or P_{i} is a planted tree with label x_{i}. For 1 ≤ i ≤ 2n, let c(P, i, r, m) denote the number of planted trees B = (T, α, β) such that (T, α, α) = P_{i}, d(α, β) = r, and l(φ^{−1}(B)) = m. Define the polynomials

c(P, i, r)(z) = ∑_{m≥0} c(P, i, r, m)z^{m}.

Because e(P_{i}) < d for each i, it is clear that c(P, i, r)(z) = 0 whenever r ≥ d.

In the following propositions we shall construct h_{S}(z) as an element of ℚ(z, a(P, 0)(z) | P ∈ V (Γ′_{S})), the set of rational functions of z and the series a(P, 0)(z) (P ∈ V (Γ′_{S})). The proofs actually give an algorithm for doing so.

(4.2) Proposition For each vertex P in Γ′_{S},

\begin{aligned}a(P, 0)(z) & = z^{2} ∏_{i=1}^{2n}\{c(P, i, 0)(z) + ∑_{P′∈V_{i}(P)}a(P′, 0)(z)\}, \\ a(P, 1)(z) & = z ∏_{i=1}^{2n}\{c(P, i, 0)(z) + ∑_{P′∈V_{i}(P)}a(P′, 0)(z)\}, \end{aligned}

and for all natural numbers r ≥ 2,

\begin{matrix}a(P, r)(z) = z ∑_{j=1}^{2n} & \{c(P, j, r − 1)(z) + ∑_{P′∈V_{j}(P)}a(P′, r − 1)(z)\}× \\ ∏_{i≠j}\{c(P, i, 0)(z) + ∑_{P′∈V_{i}(P)}a(P′, 0)(z)\}. \end{matrix}

Proof. Let P ∈ V (Γ′_{S}). Without loss of generality assume label(P) = x_{1} and x_{1}^{−1} = x_{2n}. Thus

P = φ(x_{1}) ⊕ P_{1} ⊕ ⋯ ⊕ P_{2n−1} ⊕ φ(x_{1}^{−1}),

where for each i, either P_{i} is null or P_{i} is a planted tree with label x_{i}.

We will first consider the case when r ≥ 2, which is more complicated. Clearly a(P, r, 0) = a(P, r, 1) = 0. Consider an element u of A(P, r, m) for m ≥ 2. Since φ(u)|_{d} = P, for some 1 ≤ j ≤ 2n − 1,

φ(u) = φ(x_{1}) ⊕ φ(e_{1}) ⊕ ⋯ ⊕ φ(e_{j−1}) ⊕ φ(e_{j+1}) ⊕ ⋯ ⊕ φ(e_{2n−1}) ⊕ φ(u′),

where ∑ l(e_{i}) + l(u′) = m − 1, and

(i) for each i ≠ j, either e_{i} ∈ A(P′, 0, l(e_{i})) for some P′ ∈ V_{i}(P) or φ(e_{i}) = P_{i},

(ii) either u′ ∈ A(P′, r − 1, l(u′)) for some P′ ∈ V_{j}(P) or φ(u′) = (T, α, β)

with (T, α, α) = P_{j} and d(α, β) = r − 1. Therefore

\begin{matrix}a(P, r, m) = ∑_{j=1}^{2n−1} ∑_{{m_{1}+···+m_{2n−1} \atop =m−1}} \\ \{c(P, j, r − 1, m_{j}) + ∑_{P′∈V_{j}(P)}a(P′, r − 1, m_{j})\}× \end{matrix} ; ∏_{i≠j}\{c(P, i, 0, m_{i}) + ∑_{P′∈V_{i}(P)}a(P′, 0, m_{i})\}.

Translating into generating functions gives the formula we want. (Note that, by our assumption at the beginning of this proof, c(P, 2n, 0)(z) = 1, c(P, 2n, i) = 0 if i ≥ 1, and V_{2n}(P) = ∅.)

We now consider the case when r = 1. Clearly a(P, 1, 0) = 0. Consider an element u of A(P, 1, m) for m ≥ 1. Since φ(u)|_{d} = P,

φ(u) = φ(x_{1}) ⊕ φ(e_{1}) ⊕ ⋯ ⊕ φ(e_{2n−1}),

where ∑ l(e_{i}) = m − 1, and for each i, either e_{i} ∈ A(P′, 0, l(e_{i})) for some P′ ∈ V_{i}(P) or φ(e_{i}) = P_{i}. Therefore

a(P, 1, m) = ∑_{{m_{1}+···+m_{2n−1} \atop =m−1}} ∏_{i=1}^{2n−1}\{c(P, i, 0, m_{i}) + ∑_{P′∈V_{i}(P)}a(P′, 0, m_{i})\}.

The formula for r = 1 now follows. The case for r = 0 is similar. □

(4.3) Proposition For all P ∈ V (Γ′_{S}), b(P)(z) ∈ ℚ(z, a(P′, 0)(z) | P′ ∈ V (Γ′_{S})).

Proof. Write V (Γ′_{S}) = {P_{1}, P_{2}, …, P_{t}}. Because c(P, i, r)(z) = 0 whenever r ≥ d, from the previous proposition

a(P_{i}, r)(z) = ∑_{j=1}^{t} zf_{ij}(z)a(P_{j}, r − 1)(z)

for all r > d, where f_{ij}(z) ∈ ℚ[z, a(P, 0)(z) | P ∈ V (Γ′_{S})] are some series independent of r. Let M be the t × t matrix with entries zf_{ij}(z). By the Hamilton-Cayley Theorem,

M^{t} + f_{t−1}(z)M^{t−1} + ⋯ + f_{1}(z)M + f_{0}(z)I = 0

where c_{M}(Y) = Y^{t}+f_{t−1}(z)Y^{t−1}+⋯+f_{0}(z) is the characteristic polynomial of M, and I is the t × t identity matrix. Applying both sides to the column vector [a(P_{i}, r)(z)]_{i=1}^{t}, we get that

a(P, r + t)(z) + f_{t−1}(z)a(P, r + t − 1)(z) + ⋯ + f_{0}(z)a(P, r)(z) = 0

for all P ∈ V (Γ′_{S}), and for all r ≥ d. Since b(P)(z) = ∑_{r≥1} a(P, r)(z),

(1 + f_{t−1}(z) + ⋯ + f_{0}(z))b(P)(z)

is a polynomial in f_{i}(z) and a(P′, r)(z) for P′ ∈ V (Γ′_{S}) and r ≤ d + t. Now each entry in the matrix M is an element of ℚ[z, a(P, 0)(z) | P ∈ V (Γ′_{S})] with zero constant term, therefore each f_{i}(z) is also. Thus

1 + f_{t−1}(z) + ⋯ + f_{0}(z) ∈ ℚ[z, a(P, 0)(z) | P ∈ V (Γ′_{S})]

and is invertible in ℚ[[z]]. From the previous proposition, each a(P′, r)(z) is also in ℚ[z, a(P, 0)(z) | P ∈ V (Γ′_{S})]. The result now follows. □

(4.4) Proposition h_{S}(z) ∈ ℚ(z, a(P, 0)(z) | P ∈ V (Γ′_{S})).

Proof. Let {P_{1}, …, P_{2n}} be a set of planted trees whose initial and terminal vertices coincide such that φ^{−1}(P_{1} ⊕ ⋯ ⊕ P_{2n}) is nonzero in S, and for each i, e(P_{i}) ≤ d and either P_{i} is null or label(P_{i}) = x_{i}. To control h_{S}(z), it is enough to calculate for each such set of {P_{1}, …, P_{2n}} the number of u ∈ F I_{A} which are nonzero in S and satisfy

φ(u)|_{d} = P_{1} ⊕ P_{2} ⊕ ⋯ ⊕ P_{2n}.

Consider such an element u. If u ∈ E(S), then

φ(u) = φ(e_{1}) ⊕ ⋯ ⊕ φ(e_{2n}),

where ∑ l(e_{i}) = l(u), and for each i, either φ(e_{i}) = P_{i} or e_{i} ∈ A(P_{i}, 0, l(e_{i})) (the latter can only occur if P_{i} ∈ V (Γ′_{S})).

The contribution this makes to h_{S}(z) is

a(P_{1}, 0)(z)a(P_{2}, 0)(z) ⋯ a(P_{2n}, 0)(z),

where a(P, 0)(z) has its usual meaning when P ∈ V (Γ′_{S}), and a(P_{i}, 0)(z) = z^{l(φ^{−1}(P_{i}))} otherwise. If u ∉ E(S), then for some 1 ≤ j ≤ 2n,

φ(u) = φ(e_{1}) ⊕ ⋯ ⊕ φ(e_{j−1}) ⊕ φ(e_{j+1}) ⊕ ⋯ ⊕ φ(e_{2n}) ⊕ φ(u′),

where ∑ l(e_{i}) + l(u′) = l(u), and

(i) for each i ≠ j, either φ(e_{i}) = P_{i} or e_{i} ∈ A(P_{i}, 0, l(e_{i})) (the latter can only occur if P_{i} ∈ V (Γ′_{S})),

(ii) either φ(u′) = (T, α, β) with (T, α, α) = P_{j} and d(α, β) > 0, or u′ ∈ B(P_{j}, l(u′)) (the latter can only occur if P_{j} ∈ V (Γ′_{S})).

The contribution this makes to h_{S}(z) is

b(P_{j})(z) ∏_{i≠j} a(P_{i}, 0)(z)

where a(P, 0)(z) and b(P)(z) have their usual meanings when P ∈ V (Γ′_{S}), and are some polynomials in z otherwise.

Therefore h_{S}(z) can be expressed as a polynomial in z, a(P, 0)(z) and b(P)(z), P ∈ V (Γ′_{S}). The theorem now follows from the last proposition.

□

As an immediate corollary we have

(4.5) Theorem Suppose a(P, 0)(z) is rational for each P ∈ V (Γ′_{S}). Then S has rational growth.

Theorem (4.7) gives a condition on Γ′_{S} which guarantees the hypothesis of Theorem (4.5) is satisfied. First we prove a lemma.

(4.6) Lemma Suppose f(z) ∈ Rat[[z]] has nonnegative coefficients. Then f(z) has radius of convergence R > 0, and as x ∈ ℝ increases to R, f(x) increases to ∞.

Proof. Suppose f(z) = \frac{p(z)}{q(z)}, where p(z), q(z) ∈ ℝ[z] have no nonconstant common factors. Let z_{1}, …, z_{s} ∈ ℂ be the roots of q(z). Then f(z) has a positive radius of convergence R = min{|z_{1}|, …, |z_{s}|}. Let R = |z_{i}|, say.

Suppose f(R) converges. Because f(z) has nonnegative coefficients, for each z with |z| ≤ R, f(z) converges and |f(z)| ≤ f(R). But if |z| < R and z approaches z_{i}, |p(z)| is bounded below by a positive real number and q(z) → 0, so |f(z)| is not bounded. This contradiction shows that f(R) must diverge. □

(4.7) Theorem a(P, 0)(z) ∈ Rat[[z]] for each P ∈ V (Γ′_{S}) if and only if Γ′_{S} does not contain a vertex P such that P is in two cycles

P → P_{1} → ⋯ → P_{s} → P and P → P′_{1} → ⋯ → P′_{t} → P

with label(P_{1}) ≠ label(P′_{1}).

Proof. Let V_{1}, …, V_{t} be the strongly connected components of Γ′_{S}, ordered so that the vertices in V_{i} are reachable from the vertices in V_{j} only if i ≤ j.

We shall prove the ‘if’ part by induction. Suppose that the condition on Γ′_{S} holds. Suppose a(P, 0)(z) ∈ Rat[[z]] for all vertices P ∈ V_{1} ∪ V_{2} ∪ ⋯ ∪ V_{k}. (So k = 0 initially.)

Let V_{k+1} = {P_{1}, …, P_{s}}. Because the vertices in V_{k+1} are mutually reachable, the condition on Γ′_{S} implies that if P′ ∈ V_{i}(P) and P′′ ∈ V_{j}(P) for some P, P′ and P′′ in V_{k+1}, then label(P′) = label(P′′) and so i = j. By the formula for a(P, 0)(z) in Proposition (4.2) and the inductive hypothesis, there are functions g_{i}(z), f_{ij}(z) ∈ Rat[[z]] such that

a(P_{i}, 0)(z) = z^{2}(g_{i}(z) + ∑_{j=1}^{s} f_{ij}(z)a(P_{j}, 0)(z))

for each i. Let M be the matrix with entries

M_{ij} = \{ \begin{matrix}1 − z^{2}f_{ij}(z), & if i = j; and \\ −z^{2}f_{ij}(z), & if i ≠ j. \end{matrix}

Then

M[a(P_{i}, 0)(z)]_{i=1}^{s} = [z^{2}g_{i}(z)]_{i=1}^{s}.

Because det M clearly has constant term 1, det M ∈ Rat[[z]]^{∗} and M is invertible in the ring of s × s matrices over Rat[[z]]. Therefore a(P, 0)(z) ∈ Rat[[z]] for all P ∈ V_{k+1}. By induction on k, a(P, 0)(z) ∈ Rat[[z]] for all P ∈ V (Γ′_{S}).

Conversely, suppose P ∈ V (Γ′_{S}) is in two cycles

P → P_{1} → ⋯ → P_{s} → P and P → P′_{1} → ⋯ → P′_{t} → P

with label(P_{1}) ≠ label(P′_{1}). It is easy to check, by the definition of Γ′_{S}, that if u ∈ A(P, 0, l(u)) and u′ ∈ A(P, 0, l(u′)), then

\begin{aligned}φ^{−1}(P & ⊙ (P_{1} ⊙ (P_{2} ⊙ ⋯ ⊙ (P_{s} ⊙ φ(u)) ⋯)) \\ & ⊙ (P′_{1} ⊙ (P′_{2} ⊙ ⋯ ⊙ (P′_{t} ⊙ φ(u′)) ⋯))) \end{aligned}

is in A(P, 0, l(u) + l(u′) + l), for some positive integer l which is independent of u and u′. Thus for m ≥ l,

a(P, 0, m) ≥ ∑_{i+j=m−l} a(P, 0, i)a(P, 0, j).

Therefore

a(P, 0)(z) − z^{l}a(P, 0)(z)^{2} = a(P, 0)(z)(1 − z^{l}a(P, 0)(z))

is a power series with nonnegative coefficients.

Suppose a(P, 0)(z) ∈ Rat[[z]] and has radius of convergence R. Since a(P, 0)(z) has nonnegative coefficients, as x increases to R, a(P, 0)(x) → ∞ by Lemma (4.7), contradicting that 1 − x^{l}a(P, 0)(x) ≥ 0. Therefore a(P, 0)(z) ∉ Rat[[z]]. □

Combining this with Theorem (4.5) gives a sufficient graphical condition for rational growth.

(4.8) Theorem Suppose Γ′_{S} does not contain a vertex P in two cycles

P → P_{1} → ⋯ → P_{s} → P and P → P′_{1} → ⋯ → P′_{t} → P

with label(P_{1}) ≠ label(P′_{1}). Then S has rational growth.

It is an open problem whether the converse of the theorem holds also.

We conclude this section with a few remarks on the definitions of d and Γ′_{S}. The fact that

d + 1 ≤ max{|c_{i}| | i = 1, …, k}

ensures that if P → P′ is an edge in Γ′_{S} and u ∈ A(P′), then φ^{−1}(P ⊙φ(u)) is nonzero in S. The fact that d ≥ 2 ensures that if P′, P′′ ∈ V (P) have different labels, then φ^{−1}((P ⊙ P′) ⊙ P′′) is nonzero in S. These two observations, easily seen using Lemma (4.1), lie behind many of the proofs.

For each natural number i ≥ 1 we now define a directed graph Γ′_{S}(i) as follows:

(i) the vertices of Γ′_{S}(i) are planted trees P = (T, α, α) on A satisfying the properties that e(P) = i and φ^{−1}(P) is nonzero in S;

(ii) there is a directed edge from vertex P to vertex Q if Q|_{i−1} is a component of P and φ^{−1}(P ⊙ Q) is nonzero in S.

Obviously Γ′_{S} = Γ′_{S}(d).

(4.9) Proposition Suppose i ≥ d. Then Γ′_{S}(i + 1) does not contain a vertex P in two cycles

P → P_{1} → ⋯ → P_{s} → P and P → P′_{1} → ⋯ → P′_{t} → P

with label(P_{1}) ≠ label(P′_{1}) if and only if Γ′_{S}(i) does not.

Proof. The proof in one direction is obvious given the observation that if

P → P_{1} → ⋯ → P_{s} → P

is a cycle in Γ′_{S}(i + 1), then

P |_{i} → P_{1}|_{i} → ⋯ → P_{s}|_{i} → P |_{i}

is a cycle in Γ′_{S}(i). (This does not require i ≥ d.)

For the converse we first need to observe that if P_{1} → P_{2} → P_{3} in Γ′_{S}(i), then P_{1} ⊙ P_{2} → P_{2} ⊙ P_{3} is an edge in Γ′_{S}(i + 1). This is because

φ^{−1}((P_{1} ⊙ P_{2}) ⊙ (P_{2} ⊙ P_{3})) = φ^{−1}(P_{1} ⊙ (P_{2} ⊙ P_{3}))

is nonzero in S, given that i ≥ d.

With this observation, we see that if

P → P_{1} → ⋯ → P_{s} → P

is a cycle in Γ′_{S}(i), and P′_{1} ∈ V (P) with label(P_{1}) ≠ label(P′_{1}), then

(P ⊙ P_{1}) ⊙ P′_{1} → P_{1} ⊙ P_{2} → ⋯ → P_{s} ⊙ P → (P ⊙ P_{1}) ⊙ P′_{1}

is a cycle in Γ′_{S}(i + 1). The proof of the converse is now obvious. □

This proposition means that it is at least plausible that the converse of Theorem (4.8) holds, because the condition on Γ′_{S} is ‘stable’ with respect to d. As remarked above, only half of the proof of Proposition (4.9) requires i ≥ d. So we have

(4.10) Proposition If Γ′_{S}(i) does not contain a vertex P in two cycles

P → P_{1} → ⋯ → P_{s} → P and P → P′_{1} → ⋯ → P′_{t} → P

with label(P_{1}) ≠ label(P′_{1}), then Γ′_{S}(i + 1) does not either.

This gives a possible shortcut for showing S has rational growth: for Γ′_{S} to satisfy the condition in Theorem (4.8), it is enough to show that Γ′_{S}(i) satisfies the same condition for some i ≤ d.

§5 The Word Tree Graph and Polynomial Growth

In this section we apply Theorem (4.8) to prove that if a semigroup S from our class 𝔐_{F I} has polynomial growth then it has rational growth. Along the way we develop a new graphical criterion for polynomial growth.

Easdown and Shneerson introduced in [2] a directed graph Γ_{S}, the Ufnarovsky graph of S (depending on the presentation of S). Vertices of Γ_{S} are defined to be reduced words of length d which are nonzero in S. If v_{1} and v_{2} are vertices then a directed edge from v_{1} to v_{2} is defined in Γ_{S} if there exist letters g, h ∈ A ∪ A^{−1} such that v_{1}g is a reduced word which is nonzero in S and v_{1}g ∘ hv_{2}. We regard the letter g as a label for this edge. Paths in Γ_{S} may then be labelled by reduced words which are nonzero in S. The pair (w, x) is an adjacent pair if w is a reduced word which labels a loop in Γ_{S} at a vertex v and x is a letter labelling an edge which emanates from v and terminates outside the loop. The following is Theorem 1 of [2].

(5.1) Theorem Let S = ⟨A | c_{i} = 0 for i = 1, …, k⟩ be an inverse semigroup from the class 𝔐_{F I} . Then the following conditions are equivalent:

(a) S has polynomial growth.

(b) S does not contain any noncyclic free subsemigroup.

(c) (i) Γ_{S} has no vertex contained in different cycles; and

(ii) If (w, x) is an adjacent pair in Γ_{S} then

w^{d+1}xx^{−1}w^{d+1} = 0 in S.

Using the word tree graph we can give yet another characterisation of polynomial growth. This condition is slightly neater than Theorem (5.1), but generally the word tree graph is much more complicated than the Ufnarovsky graph. Other criteria for polynomial growth can be found in [3]. First we prove a technical lemma.

(5.2) Lemma Let P be a vertex in Γ′_{S}, and P_{1}, …, P_{s} be distinct elements of V (P). Then there are constants n_{1}, …, n_{s} ∈ ℕ such that for m sufficiently large,

a(P, 0, m) ≥ a(P_{1}, 0, m − n_{1}) + ⋯ + a(P_{s}, 0, m − n_{s}).

Proof. Let u_{i} ∈ A(P_{i}, 0, l(u_{i})) for each i. Let v_{i} = φ^{−1}(P ⊙ φ(u_{i})). Then v_{i} ∈ A(P, 0, l(v_{i})), and l(v_{i}) = n_{i} + l(u_{i}) for some constant n_{i} independent of the choice of u_{i}. Moreover if i ≠ j then v_{i} ≠ v_{j} because

φ(v_{i})|_{d+1} = P ⊙ P_{i} ≠ P ⊙ P_{j} = φ(v_{j})|_{d+1}.

The result now follows. □

(5.3) Theorem Let S = ⟨A | c_{i} = 0 for i = 1, …, k⟩ be an inverse semigroup from the class 𝔐_{F I} . Then S has polynomial growth if and only if Γ′_{S} has no vertex contained in different cycles.

Proof. Suppose the vertex P is in two different cycles. Applying the previous lemma to the vertices in the two cycles we find that for m sufficiently large,

a(P, 0, m) ≥ a(P, 0, m − n_{1}) + a(P, 0, m − n_{2})

for some constants n_{1}, n_{2} ∈ ℕ. Let n = n_{1}n_{2}. Then for m large,

a(P, 0, m − n_{1}) ≥ a(P, 0, m − 2n_{1}) + a(P, 0, m − n_{1} − n_{2}) ≥ a(P, 0, m − 2n_{1}).

So repeating we get

a(P, 0, m − n_{1}) ≥ a(P, 0, m − 2n_{1}) ≥ ⋯ ≥ a(P, 0, m − n).

Similarly a(P, 0, m−n_{2}) ≥ a(P, 0, m−n). Therefore a(P, 0, m) ≥ 2a(P, 0, m− n). Now a(P, 0, s) > 0 for infinitely many s ∈ ℕ since we have a cycle at the vertex P. Fix an s sufficiently large. Then for all t ∈ ℕ, a(P, 0, s + tn) ≥ 2^{t}. Therefore S has exponential growth.

To prove the converse, we use condition (c) of Theorem (5.1). It is clear that mapping a vertex w of Γ_{S} to φ(ww^{−1}) embeds Γ_{S} in Γ′_{S}. Therefore if no vertex of Γ′_{S} is contained in different cycles then no vertex of Γ_{S} is contained in different cycles.

Now suppose w^{d+1}xx^{−1}w^{d+1} is nonzero in S for some adjacent pair (w, x) in Γ_{S}. We shall show that this gives a vertex in two different cycles in Γ′_{S}. Let s be the least multiple of l(w) such that s ≥ d. For 0 ≤ i ≤ s, denote the prefix of w^{d+1} of length i by v_{i}, and the suffix of w^{d+1}v_{i} of length d by w_{i}. Let P_{i} = φ(w_{i}w_{i}^{−1}), which is planted because w is cyclically reduced. Then

P_{0} ⟶ P_{1} ⟶ ⋯ ⟶ P_{s−1} ⟶ P_{s} = P_{0}

is a cycle at P_{0} in Γ′_{S}. For 1 ≤ i ≤ d − 1, denote the suffix of w^{d+1} of length d − i by u_{i}, and let P′_{i} = φ(u_{i}xx^{−1}v_{i}(u_{i}xx^{−1}v_{i})^{−1}). Then

P_{0} ⟶ P′_{1} ⟶ P′_{2} ⟶ ⋯ ⟶ P′_{d−1} ⟶ P_{d} ⟶ P_{d+1} ⟶ ⋯ ⟶ P_{s} = P_{0}

is a different cycle at P_{0}. □

Clearly if Γ′_{S} has no vertex in two cycles then the hypothesis of Theorem (4.8) is satisfied. So we have

(5.4) Theorem If S has polynomial growth, then it has rational growth.

It is of course interesting that a simple condition on Γ′_{S} gives a criterion for polynomial growth. But in fact Theorem (5.4) could have been deduced easily from Theorem (5.1) and the following result, which gives yet another possible shortcut for showing S has rational growth.

(5.5) Theorem The following conditions are equivalent:

(a) Γ_{S} has no vertex contained in different cycles.

(b) If a vertex P in Γ′_{S} is contained in two cycles

P → P_{1} → ⋯ → P_{s−1} → P_{s} = P and P → P′_{1} → ⋯ → P′_{t−1} → P′_{t} = P,

then label(P_{i}) = label(P′_{i}) for each i = 1, …, min{s, t}.

Proof. First we make the following observation: if P_{1} → P_{2} → ⋯ → P_{d} is a path in Γ′_{S}, and a_{i} = label(P_{i}) for each i, then φ(a_{1}a_{2} ⋯ a_{d}) is a subtree of P_{1} ⊙ (P_{2} ⊙ ⋯ ⊙ (P_{d−1} ⊙ P_{d}) ⋯)). Therefore a_{1}a_{2} ⋯ a_{d} is a vertex of Γ_{S}.

To show (a) implies (b), suppose (b) does not hold. Let

P → P_{1} → ⋯ → P_{s} → P_{s+1} = P and P → P′_{1} → ⋯ → P′_{t} → P′_{t+1} = P

be two cycles in Γ′_{S}. Let a = label(P), a_{i} = label(P_{i}) and b_{i} = label(P′_{i}) for each i. Suppose a_{i} ≠ b_{i} for some 1 ≤ i ≤ min{s + 1, t + 1}.

By replacing P → P_{1} → ⋯ → P_{s} → P by

P → P_{1} → ⋯ → P_{s} → P → P_{1} → ⋯ → P_{s} → P

and so on if necessary, we can assume s ≥ d. Applying the above observation to each subpath of length d of

P → P_{1} → ⋯ → P_{s} → P → P_{1} → ⋯ → P_{d−1},

we see that

\begin{matrix}aa_{1} ⋯ a_{d−1} → a_{1}a_{2} ⋯ a_{d} → ⋯ → a_{s−d+2} ⋯ a_{s}a \\ → & a_{s−d+3} ⋯ a_{s}aa_{1} → ⋯ → a_{s}aa_{1} ⋯ a_{d−2} → aa_{1} ⋯ a_{d−1} \end{matrix}

is a cycle in Γ_{S}. But applying the observation to

P → P_{1} → ⋯ → P_{s} → P → P′_{1} → ⋯ → P′_{t} → P → P_{1} → ⋯ → P_{d−1},

shows that

\begin{matrix}aa_{1} ⋯ a_{d−1} → a_{1}a_{2} ⋯ a_{d} → ⋯ → a_{s−d+2} ⋯ a_{s}a \\ → & a_{s−d+3} ⋯ a_{s}ab_{1} → ⋯ → b_{t}aa_{1} ⋯ a_{d−2} → aa_{1} ⋯ a_{d−1} \end{matrix}

is another cycle in Γ_{S}. Because a_{i} ≠ b_{i} for some i, aa_{1} ⋯ a_{d−1} is in two different cycles in Γ_{S}.

Now suppose (b) holds. Given two cycles

w → w_{1} → ⋯ → w_{s} → w_{s+1} = w and w → w′_{1} → ⋯ → w′_{t} → w′_{t+1} = w

in Γ_{S}, we need to show that they are the same cycle. We can assume that the cycles are actually loops.

Let P = φ(ww^{−1}), P_{i} = φ(w_{i}w_{i}^{−1}), P′_{i} = φ(w_{i}w_{i}^{−1}). By considering Munn trees, it is clear that w_{i} is the concatenation of the labels of the first d vertices in the sequence

P_{i} → P_{i+1} → ⋯ → P_{s} → P → P_{1} → · · · .

Therefore condition (b) applied to the cycles

\begin{matrix}P → P_{1} → ⋯ → P_{s} → P → P_{1} → ⋯ and \\ P → P′_{1} → ⋯ → P′_{t} → P → P′_{1} → ⋯ \end{matrix}

actually shows that w_{i} = w′_{i} for each i. So the original cycles are the same.

□

If the equivalent conditions in Theorem (5.5) are satisfied by a semigroup S from the class 𝔐_{F I} , then clearly S has rational growth by Theorem (4.8). However the hypothesis in Theorem (4.8) is stronger than the conditions stated in Theorem (5.5). One example is S = ⟨x, y | x^{2} = y^{2} = 0⟩. In this example d = 2, and Γ_{S} is isomorphic to Γ′_{S}. By Theorems (4.8) and (5.3), S also serves as an example of a semigroup in the class 𝔐_{F I} which has rational and exponential growth.

References

[1] M. Brazil, unpublished communication.

[2] D. Easdown and L.M. Shneerson, “Growth and existence of identities in a class of finitely presented inverse semigroups with zero”, International Journal of Algebra and Computation, 6(1) (1996), 105-121.

[3] D. Easdown and L.M. Shneerson, “Growth of finitely presented Rees quotients of free inverse semigroups”, Research report of the School of Mathematics and Statistics, University of Sydney, (95)38.

[4] P.M. Higgins, Techniques of semigroup theory, Oxford University Press, 1992.