SOME GROUP PRESENTATIONS WITH RATIONAL GROWTH

MICHAEL STOLL

Abstract. A class of group presentations is introduced which have an explicitly computable rational growth series. The standard presentation of an orientable surface group belongs to this class.

1. Notations and Definitions

Let G = ⟨S | T ⟩ be a finitely presented group. We will always consider S to be closed under inversion, i.e. for every s ∈ S, its inverse s^{−1} is also an element of S. It is then useful to require that the set of relators T contain the words ss^{−1} for all s ∈ S. Thus ⟨S | T ⟩ is a semigroup presentation of G. We remark that s and s^{−1} need not be distinct; s may be a generator of order 2.

Let S^{∗} be the free semigroup (with unity) generated by S. In our context, S^{∗} is usually called the set of words over S. Every word w ∈ S^{∗} is of the form w = s_{1}s_{2} ⋯ s_{n} with s_{1}, …, s_{n} ∈ S, where n ≥ 0 is some integer. The length of w is then defined to be |w| = n. The empty word (it is obtained with n = 0) is denoted ϵ; it is the unit element in S^{∗} and has length |ϵ| = 0. We extend the inversion mapping s ↦ s^{−1} from S to S^{∗} by setting (s_{1}s_{2} ⋯ s_{n})^{−1} = s_{n}^{−1} ⋯ s_{2}^{−1}s_{1}^{−1}.

There is a canonical surjective semigroup homomorphism π : S^{∗} → G, which sends every s ∈ S to the element it represents in G. Let g ∈ G be some element. Then its length with respect to S is l(g) = min{|w| | π(w) = g}. Since there are only finitely many words of any given length, this is well-defined, as is the growth series of G with respect to S, which is defined to be the formal power series

F (z) = ∑_{g∈G} z^{l(g)}.

We will use the theory of rewriting systems, which is explained for example in [2], and some formal language theory, which may be found for example in [3]. A survey on group growth in general is given in Grigorchuk’s talk [4].

I wish to thank Rostislav Grigorchuk for many interesting discussions during his stay at the Max Planck Institute for Mathematics in Bonn, out of which emerged (among other things) the result presented here.

Date: Feb 28, 1995.

2 MICHAEL STOLL

2. The result and its proof

Let G be a group given by a presentation G = ⟨S | T ⟩ of the following type: S = X ∪ Y, where X and Y are disjoint and invariant under inversion s ↦ s^{−1}. Relators are T = {ss^{−1} | s ∈ S} ∪ R, where R ⊂ S^{∗} is some set of non-empty words over S having the following properties:

1) If r ∈ R, then the length |r| of r is a multiple of 4.

2) every r ∈ R has the form r = x_{1}y_{1} ⋯ x_{k}y_{k} with x_{j} ∈ X, y_{j} ∈ Y. (In short, R ⊂ (XY)^{∗}.)

3) Take all words obtainable from elements of R by cyclic permutations and/or inversion and call \overline{R} the set of those of these words that begin with some x ∈ X. Then we require: If r, r′ ∈ \overline{R} begin with the same two letters xy, then r = r′.

As an example of what \overline{R} looks like, take R = \{xyxy^{−1}\} and assume that x ≠ x^{−1} and y ≠ y^{−1}. Then \overline{R} = \{xyxy^{−1}, xy^{−1}xy, x^{−1}y^{−1}x^{−1}y, x^{−1}yx^{−1}y^{−1}\}.

We now state our result:

Theorem: Let G be given by a presentation ⟨S | T ⟩ with the properties given above. Then the growth series F (z) of G with respect to S is a rational power series. Explicitly,

F (z) = \frac{1 + z}{1 − (#S − 1)z + ∑_{r∈\overline{R}} \frac{1 − z}{1 − z^{|r|/2}} z^{|r|/2}} .

The first step in the proof is to construct a system of rewrite-rules that lead to a unique and shortest normal form for the elements of G. The set of rules will be the following:

• ss^{−1} → ϵ for every s ∈ S;

• r_{1} → r_{2}^{−1} for every r = r_{1}r_{2} ∈ \overline{R}, where r_{1} and r_{2} have the same length |r|/2.

Note that by properties 1) and 2), r_{1} is of the form xy ⋯ xy and r_{2}^{−1} is of the form yx ⋯ yx (where x ∈ X and y ∈ Y may denote different elements at each occurrence). It is clear that every reduction sequence using these rules has to stop sooner or later—a rule of the first type reduces the length, whereas a rule of the secod type shifts some of the x’s to the right, which is possible only finitely many times. As soon as we have shown that these rules give unique normal forms, it will be clear that these normal forms will also be shortest representatives, for the rules never increase the length of a word.

SOME GROUP PRESENTATIONS  WITH RATIONAL GROWTH  3

Now for uniqueness. By the standard theory of rewriting systems, it suffices to check local confluence (see e.g. [2]) in the nontrivial cases. This means that for any two rules of the form

ab → u and bc → v

(with b ≠ ϵ), we have to check that uc and av (which we get by reducing abc using either the first or the second rule) can be reduced to the same word (using rules of our given set). We have to distinguish the following four cases.

a) The rules are of the form ss^{−1} → ϵ and s^{−1}s → ϵ. In this case, uc = av = s already.

b) The rules are x^{−1}x → ϵ and xa → b, where x ∈ X and xab^{−1} ∈ \overline{R} and |b| = |a| + 1. Then we have to look at the two words a and x^{−1}b. We have x^{−1}ba^{−1} ∈ \overline{R}. Let b = cx′ with some x′ ∈ X, then |x^{−1}c| = |x′a^{−1}|, hence x^{−1}c → a^{−1}x′^{−1} is a rule, and we have the reduction x^{−1}b = x^{−1}cx′ → a^{−1}x′^{−1}x′ → a, and case b) is settled.

c) The rules are ay → b and yy^{−1} → ϵ, where y ∈ Y and ayb^{−1} ∈ \overline{R} with |b| = |a| + 1. We have to look at a and by^{−1}. Let b = y′c with some y′ ∈ Y. Then, since cy^{−1}a^{−1}y′ ∈ \overline{R} and |cy^{−1}| = |a^{−1}y′|, we have the rule cy^{−1} → y′^{−1}a, whence the reduction by^{−1} = y′cy^{−1} → y′y′^{−1}a → a.

d) The rules are ab → u and bc → v with abu^{−1}, bcv^{−1} ∈ \overline{R}, |ab| = |u| and |bc| = |v|. Since ab and bc are both of the form xy ⋯ xy, b has to be of even length, so |b| ≥ 2, and by property 3), we have bu^{−1}a = bcv^{−1}, hence u^{−1}a = cv^{−1}. Since u and v are longer than a and c, respectively, this means that u = dc^{−1}, v = a^{−1}d with some word d. Then uc = dc^{−1}c and av = aa^{−1}d both reduce to d by applying the first set of rules.

This proves uniqueness of normal forms.

Given this set of rules, the normal forms are exactly those words that do not contain any of the left hand sides of the rules as a subword. This condition defines a regular language L ⊂ S^{∗}. Furthermore, given g ∈ G and starting with any word w such that π(w) = g, repeated application of the rewrite-rules finally gives a word in normal form w_{g}. It is uniquely determined by g and satisfies π(w_{g}) = g and |w_{g}| = l(g). (The first assertion follows from the general theory of rewriting systems; the second one follows from the fact that our rules never increase length.)

Hence ρ : G → L, g ↦ w_{g}, gives a bijection compatible with the notions of length on both sides, and thus

F (z) = ∑_{g∈G} z^{l(g)} = ∑_{w∈L} z^{|w|}

is a rational power series, since it is the growth series of a regular language.

4 MICHAEL STOLL

In order to compute F (z) explicitly, we have to construct a finite state automaton that recognizes the language L. The standard way to do this is to take all proper prefixes of the left hand sides of the rules as the set of states (plus some failure state which will not be mentioned explicitly) with the following transitions:

Let w be the state and s the letter causing the transition. If ws ends with the left hand side of some rule, fail. Else go to state w′, where w′ is the state of maximum length such that ws ends with w′.

In our case, the states are

• ϵ, the start state;

• x for every x ∈ X;

• y for every y ∈ Y;

• x_{1}y_{1} ⋯ x_{k}y_{k} if some r ∈ \overline{R} begins with this word and 1 ≤ k < |r|/4;

• x_{1}y_{1} ⋯ x_{k−1}y_{k−1}x_{k} if some r ∈ \overline{R} begins with this word and 1 < k ≤ |r|/4.

In the following, Y_{x} stands for the set of y ∈ Y such that some r ∈ \overline{R} begins with xy, and Y′_{x} = Y \Y_{x}. Symbols x, x′, x_{i} always denote elements of X, symbols y, y′, y_{i} always denote elements of Y.

Then the transitions are given by

• ϵ →^{x} x, ϵ →^{y} y;

• x →^{x′} x′ (if x′ ≠ x^{−1}), x →^{y} xy (if y ∈ Y_{x}), x →^{y} y (if y ∈ Y′_{x});

• y →^{x} x, y →^{y′} y′ (if y′ ≠ y^{−1});

• Let w = x_{1}y_{1} ⋯ x_{k}y_{k}, and let x_{k+1} be the next letter in the corresponding

r ∈ \overline{R}. Then w →^{x_{k+1}} wx_{k+1}, w →^{x} x (if x ≠ x_{k+1}), w →^{y} y (if y ≠ y_{k}^{−1});

• Let w = x_{1}y_{1} ⋯ x_{k−1}y_{k−1}x_{k}, and let y_{k} be the next letter in the corresponding

r ∈ \overline{R}. Then w →^{x} x (if x ≠ x_{k}^{−1}), w →^{y_{k}} wy_{k} (if k < |r|/4), w →^{y} x_{k}y (if

y ∈ Y_{x_{k}} \ {y_{k}}), w →^{y} y (if y ∈ Y′_{x_{k}}).

(The state xy is to be interpreted as the failure state, if the word r ∈ R̄ beginning with xy has length |r| = 4.)

For a word w, we write L_{w} = {u ∈ S^{∗} | wu ∈ L} and F_{w}(z) for the growth series of L_{w}. From the transitions we get the following equations:

F (z) = 1 + z ∑_{x} F_{x}(z) + z ∑_{y} F_{y}(z)
F_{x}(z) = 1 + z ∑_{x′≠x^{−1}}F_{x′}(z) + z ∑_{y∈Y′_{x}} F_{y}(z) + z ∑_{y∈Y_{x}} F_{xy}(z)
F_{y}(z) = 1 + z ∑_{x} F_{x}(z) + z ∑_{y′≠y^{−1}}F_{y′}(z)
F_{x_{1}y_{1}···x_{k}y_{k}}(z) = 1 + z ∑_{x≠x_{k+1}}F_{x}(z) + zF_{x_{1}y_{1}···x_{k}y_{k}x_{k+1}}(z) + z ∑_{y≠y_{k}^{−1}}F_{y}(z)
F_{x_{1}y_{1}···x_{k}}(z) = 1 + z ∑_{x≠x_{k}^{−1}}F_{x}(z)

+ z ∑_{y∈Y′_{x_{k}}} F_{y}(z) + z ∑_{y∈Y_{x_{k}} \{y_{k}}}F_{xy}(z) + zF_{x_{1}y_{1}···x_{k}y_{k}}(z)

where the last summand is zero when x_{1}y_{1} ⋯ x_{k}y_{k} is the first half of some r ∈ \overline{R}.

From the first and third equations we see that all F_{y}(z) are the same, and F (z) = (1 + z)F_{y}(z). Using the second and third equations, the last two can be rewritten as

F_{x_{1}y_{1}···x_{k}y_{k}}(z) = F_{y}(z) − zF_{x_{k+1}}(z) + zF_{x_{1}y_{1}···x_{k}y_{k}x_{k+1}}(z)
F_{x_{1}y_{1}···x_{k}}(z) = F_{x_{k}}(z) − zF_{x_{k}y_{k}}(z) + zF_{x_{1}y_{1}···x_{k}y_{k}}(z) .

Hence, with x_{1}y_{1} ⋯ the beginning of r ∈ \overline{R},

F_{x_{1}y_{1}···x_{k}y_{k}} = \{ \begin{matrix}0 & , k = |r|/4 \\ F_{y}(z) − z^{2}F_{x_{k+1}y_{k+1}}(z) + z^{2}F_{x_{1}y_{1}···x_{k+1}y_{k+1}} & , 1 ≤ k < |r|/4 \end{matrix}

Unwinding this recursion down to k = 1, we get with n = |r|/4

F_{x_{1}y_{1}}(z) + z^{2}F_{x_{2}y_{2}}(z) + ⋯ + z^{2n−2}F_{x_{n}y_{n}} = (1 + z^{2} + ⋯ + z^{2n−4})F_{y}(z) .

Looking at all cyclic permutations of r = x_{1}y_{1} ⋯ x_{2n}y_{2n} which are in \overline{R}, we get 2n equations of this type which determine the F_{x_{j}y_{j}}(z) uniquely in terms of F_{y}(z), so by symmetry, all F_{x_{j}y_{j}}(z) have to be equal, and we get

F_{xy}(z) = \frac{1 − z^{2n−2}}{1 − z^{2n}} F_{y}(z) = (1 − z^{2n−2} \frac{1 − z^{2}}{1 − z^{2n}} )F_{y}(z)

for r = xy ⋯ ∈ \overline{R}, |r| = 4n.

6 MICHAEL STOLL

Summing the second of our original set of equations over all x, we get with

F_{X}(z) = ∑_{x} F_{x}(z)

(1 − (#X − 1)z)F_{X}(z) = #X + #X#Y zF_{y}(z) − ∑_{r∈\overline{R}} z^{|r|/2−1} \frac{1 − z^{2}}{1 − z^{|r|/2}} F_{y}(z) .

Multiplying the third equation by (1 − (#X − 1)z) and plugging in the expression for F_{X}(z), we finally have

(1 − (#X + #Y − 2)z − (#X + #Y − 1)z^{2} + ∑_{r∈\overline{R}} \frac{1 − z^{2}}{1 − z^{|r|/2}} z^{|r|/2})F_{y}(z) = 1 + z .

Substituting F (z) = (1 + z)F_{y}(z), we get the formula stated in the Theorem.

3. Examples

Let us see what can be done with our result.

Free products of Z/2Z and Z. This is the case where R is empty. We get the well-known formula

F (z) = \frac{1 + z}{1 − (s − 1)z} ,

where s = #S.

Direct product of two such free products. Let X, Y generate the first and second factors, resp. \overline{R} consists of all xyx^{−1}y^{−1} with x ∈ X, y ∈ Y. Let a = #X, b = #Y, then #\overline{R} = ab, and all relators have length 4. This gives

F (z) = \frac{1 + z}{1 − (a + b − 1)z + ab\frac{1 − z}{1 − z^{2}} z^{2}} = \frac{1 + z}{1 − (a − 1)z} \frac{1 + z}{1 − (b − 1)z}

(an equally well-known result, of course).

Surface groups. This one is more interesting. The standard presentation of the fundamental group of a closed orientable surface of genus g is

⟨x_{1}, y_{1}, …, x_{g}, y_{g} | [x_{1}, y_{1}] ⋯ [x_{g}, y_{g}] = 1⟩ .

We take X = {x_{1}, x_{1}^{−1}, …, x_{g}, x_{g}^{−1}} and Y = {y_{1}, y_{1}^{−1}, …, y_{g}, y_{g}^{−1}}. The one relator has all required properties, and \overline{R} consists of 4g words of length 4g. Hence,

F (z) = \frac{1 + z}{1 − (4g − 1)z + 4g \frac{1 − z}{1 − z^{2g}} z^{2g}}

= \frac{(1 + z)(1 − z^{2g})}{1 − (4g − 1)z + (4g − 1)z^{2g} − z^{2g+1}}

= \frac{1 + 2z + 2z^{2} + ⋯ + 2z^{2g−1} + z^{2g}}{1 − (4g − 2)z − (4g − 2)z^{2} − ⋯ − (4g − 2)z^{2g−1} + z^{2g}} .

Some Coxeter groups. Our result is applicable to groups of the form

⟨x_{1}, …, x_{m}, y_{1}, …, y_{n} | x_{i}^{2} = y_{j}^{2} = (x_{i}y_{j})^{2a_{ij}} = 1⟩ ,

where the a_{ij} are some natural numbers. \overline{R} consists of all (x_{i}y_{j})^{2a_{ij}} with a_{ij} > 0. (It is known that Coxeter groups always have rational growth series (with respect to a Coxeter generating set), see the exercise in [1] which also gives a method to calculate the series by recurrence. Our result, when applicable, gives a closed formula.)

A final example. Let G_{n} = ⟨a, b, c | a^{2} = b^{2} = c^{2} = (abac)^{n} = 1⟩. We take X = \{a\} and Y = \{b, c\}. \overline{R} consists of the two words (abac)^{n} and (acab)^{n}, each of length 4n. This gives

F (z) = \frac{1 + z}{1 − 2z + 2\frac{1 − z}{1 − z^{2n}} z^{2n}} = \frac{(1 + z)(1 − z^{2n})}{1 − 2z + z^{2n}}

= \frac{1 + 2z + 2z^{2} + ⋯ + 2z^{2n−1} + z^{2n}}{1 − z − z^{2} − ⋯ − z^{2n−1}} .

Springer 1983

References [1] Bourbaki, Nicolas: Groupes et algèbres de Lie, Ch. 4–6, Paris: Hermann 1968 [2] B. Buchberger, R. Loos: Algebraic Simplification. In: B. Buchberger et. al. (eds.):

Computer Algebra—Symbolic and Algebraic Computation (second edition), Wien New York:

[3] Epstein, D.B.A., Cannon, J.W., Holt, D.F., Levy, S.V.F., Paterson, M.S.,

Thurston, W.P.: Word processing in groups, Boston–London: Jones and Bartlett 1992 [4] Grigorchuk, Rostislav I.: On growth in group theory, Proceedings of the International

Congress of Mathematicians Kyoto 1990, 325–338 (1991)

Mathematisches Institut der Heinrich-Heine-Universität, Universitätsstr. 1, 40225 Düsseldorf, Germany.

E-mail address: stoll@math.uni-duesseldorf.de