Fig. 8.5. Two different graphical realizations of the Whitehead automorphism W(a,{b},{c},{a,d}) .

Given a graphical realization (Γ, Φ) and a word u ∈ (X̃)∗, we may interpret φ(u) as the word φΓ (u) in E ∗ or as an element of the free group F (E+) or by virtue of λ as an element of F (Y). However, there is no risk of confusion.

The trivial homomorphism has a graphic realization by a graph with two points 1 and 2, which are connected in the direction from 1 to 2 by |X| + 1 different arcs and all of them have label y, where y is some fixed letter in the nonempty set Y.

In the following pictures, we draw the edges from the spanning tree thicker and as straight lines while the bridges are curved; see Figure 8.6.

Example 8.35. We use Figure 8.7 and make the following agreement. Let X = E+ T = {A, B, C, D, E} (with φ(x) = x) and Y = {a, b, c, d, e}. The edges e ∈ E+ are also indicated with their labels λ(e) ∈ Y. Thus, the upper picture tells us:

In the lower picture the spanning tree has been changed which leads to new paths:

This gives the following result:

Therefore, φ can be factorized as φ' ∘ W(A,{B},{D},{A,C}).

◊

A graphical realization specifies the base point, the orientation, a spanning tree, etc. However, we are interested in homomorphisms only modulo Whitehead automorphisms. Thus, we can think that a graphical realization without a specification of the items above defines a class of homomorphisms. If every member in such a class is obtained from any other member by a multiplication of a Whitehead automorphism, then we do not lose any substantial information. This will become clear in the next subsections.

Free choice of the base point

Let 1' ∈ V be a vertex different from 1 which we want to make the marked initial and final vertex. Instead of (Γ, Φ), we now consider (Γ' , Φ) with Γ' = (1' , V, E, T, λ). Then, for a ∈ X, we may compute φ(a) in F(Y) by φ(a) = λ(T[1, 1] φ(a) T[1, 1' ]) = hφ(a)h−1 where h = λ(T[1, 1]) ∈ F(Y). Therefore, we obtain φ' by applying an inner automorphism γ of F (Y). In particular, φ' is surjective if and only if φ is surjective.

If φ is surjective then, for y ∈ F (Y), there exists x ∈ F (X) with φ(x) = y. In this case φ(a) = φ(xax−1) = φ ∘ ψ, where ψ is an inner automorphism. Hence, ψ is a product of Whitehead automorphisms. We may therefore move the base point around: every vertex can be chosen to be the base point.

Changing the orientation

It is convenient to change the orientation of identically labeled edges simultaneously. Consider a label y ∈ Y and then take λ' = iy ∘ λ as the new edge labeling. This gives a new pair (Γ' , Φ) and defines φ' : F(X) → F(Y) with iy ∘ φ' = φ.

If φ' = γ' ∘ π' for an inner automorphism γ' of F (Y) and a projection π, then we have φ = γ ∘ π for an inner automorphism γ of F (Y) and a projection π. This follows because iy ∘γ' ∘π(a) = iy(h)iy(π(a))iy (h)−1 for some h ∈ F(Y) and because π = iy ∘π' is a projection. Therefore, we may consider (Γ' , Φ) and φ' instead of (Γ, Φ) and φ. Thus, in the drawing: if y ∈ Y, then we are free to change the orientation of all arcs labeled by y without changing the label of these arcs.

Replacing λ(Φ(a)) by its inverse

Let a ∈ X and e = Φ(a) ∈ E T be a bridge. If we define Φ'(a) = e and Φ'(b) = Φ(b) for all a ≠ b ∈ X, then we obtain φ' = φ ∘ ia. Since ia is a Whitehead automorphism, in this situation we may consider Φ' and φ' instead of Φ and φ.

Changing the spanning tree

This is the heart of the process. A local change of the spanning tree causes a right multiplication by some Whitehead automorphism. Let A ∈ E T be a bridge with s(A) = q ≠ 1 and t(A) = 1. We want to construct a spanning tree T' that contains A, and we want to compute the homomorphism F (X) → F (Y) that results from the modified graphical realization. If there is a parallel edge e ∈ T, that is, s(e) = s(A), t(e) = t(A) with λ(A) = λ(e), then we simply replace A by e in the spanning tree. Now, let Φ(a) = A where a ∈ X. Consider the path T[1, q] = T[1, p] e with e ∈ T and s(e) = p, t(e) = q. This runs in the spanning tree from 1 to the source of A. We remove e, ē from T andwe insert A and Ā into the spanning tree. This defines a new spanning tree T. We define Φ'(a) = e; and for b ∈ X with b ≠ a, we let Φ'(b) = Φ(b). Note that e is a bridge in T'. Let φ' : F(X) → F(Y) be induced by ((1, V, E, T' , λ), Φ'). The path φ(a) = T[1, p]e A has not changed because T[1, p] = T'[1, p] and A = T[q, 1], hence φ(a) = φ(a). Now consider b ∈ X with b ≠ a. Then Φ(b) = B is still a bridge and we have

There are now four different cases that exactly correspond to the distinctions in Whitehead automorphisms.

The change of the spanning tree thus results in φ' : F(X) → F (Y) where φ = φ' ∘ψ and ψ is a Whitehead automorphism. The inverse of a Whitehead automorphism is a (product of) Whitehead automorphism(s). Hence, φ = φ' ∘ ψ−1. We may therefore change spanning trees in the described manner. This is explicitly done in Example 8.35.

Since we also may change the orientation of equally labeled edges, we may assume the following, if necessary: if e, f are equally labeled edges which have the common source 1 and the targets p and q, respectively, and if further 1, p, and q are pairwise distinct, then the above method provides a spanning tree T with e, f ∈ T.

Determinization

We say that a graphical realization (Γ; Φ) is deterministic, if for each u ∈ V and each y ∈ Ỹ there is at most one vertex υ, which is the target t(e) for edges e with s(e) = u and λ(e) = y. Thus, for each word w = y1 ⋅⋅ ⋅ ym ∈ Ỹ∗ there is atmost one vertex q ∈ V, which is reachable from u by a path labeled with w.

Suppose that υ = s(e) = s(f) is the source of two edges e and f , which have the same label y = λ(e) = λ(f) but different final vertices p = t(e) ≠ t(f) = q. This violates the determinism. Note that the determinism is not violated by parallel edges, that is, if t(e) = t(f). We do not have to remove parallel edges with the same labels. They indicate that the homomorphism is not injective, but this fact becomes visible in the projection π at the end, too.

Without restriction we can assume that t(f) ≠ υ; otherwise we interchange the role of e and f . By changing the orientation, if necessary, we may assume that y ∈ Y. By moving the base point we may also assume that υ = 1. In particular, 1 ≠ q. Furthermore, we may assume that f ∈ T is an edge in the spanning tree.

We now fold the graph along the edges e and f . This means, we identify e with f , ē with f̄, and p with q. Formally, we remove f and f̄ from E and hence also from T. All remaining edges with source or target q get the new source or target p. Finally, we remove the now isolated vertex q. Thus, we obtain a new graph Γ' = (1, V' , E' , T' , λ), which is still connected. Since we have removed exactly one vertex and exactly one undirected edge from T, then (V' , T) is a spanning tree of (V' , E).

Moreover, if 1 ≠ t(e), then we may assume, by the above construction, that e ∈ T is an edge of the spanning tree, too, because then e and f are equally labeled edges which both have the source 1 and the target p and q, respectively, where 1, p, and q are pairwise different. Then e ∈ T, and the folding of e and f does not change the outputs of φ in the group F (Y). This means, we have φ = φ.

If 1 = t(e), then the situation is somewhat different. Now, e is a loop and thus a bridge. Therefore, there is exactly one a ∈ X̃ with Φ(a) = e, and we have φ(a) = λ(e) = y. Without loss of generality, let a ∈ X and y ∈ Y.

We compute the new, induced homomorphism φ. We already saw that φ(a) = φ(a). Now, let a ≠ b ∈ X. For φ(b), there are again only the four cases we already know.

The paths φ(b) arise out of the paths φ(b) by deleting all edges f and f̄ . However, a deletion changes the label and therefore the image in F (Y). To compensate for this, we emphasize that we do not delete the edges f and f̄ in φ(b), but replace f by e as well as f̄ by ē. After this modification, φ(b) becomes a word wb ∈ E ∗, and we obtain λ(φ(b)) = λ(wb)∈ F(Y). The word wb is a closed path in (V' , E), and according to the above cases, in F (Y), we obtain

We remark that φ = φ' ∘ ψ for a Whitehead automorphism ψ.

The rose

By the above procedures, we finally obtain a deterministic graphical realization (̂Γ, ̂Φ) for a homomorphism ̂φ: F (X) → F (Y) such that

In Equation (8.9), the mapping γ is an inner automorphism of F (Y), and ψ is a product of Whitehead automorphisms of F (X). With ̂Γ, we now can recognize if φ is surjective. First of all, this is the case if and only if ̂φ is surjective. Let us make a preliminary observation. Suppose, w = uzz̄υ is the label of a path in ̂Γ from 1 to 1 with u, υ ∈ Ỹ∗, and z ∈ Ỹ. By determinism an edge e corresponds to the position of z, and for z̄ we may choose the edge ē without changing the vertices on the path. Hence, uυ also describes a path from 1 to 1. If ŵ is now the reduced word in Ŷ∗, which corresponds to w, then there is a path from 1 to 1, labeled with ŵ.

Suppose, φ is surjective, then certainly y ∈ φ(F(X)) = ̂φ(F(X)) for all y ∈ Y. The letter y is a reduced word and, by the preliminary consideration, the graph ̂Γ contains a loop at 1 labeled by y. This is a necessary condition. Conversely, the existence of these loops is sufficient to guarantee the surjectivity of φ.

For the final part in the proof of Theorem 8.34, we may assume that φ: F (X) → F (Y) is surjective. As we have explained above, if y = φ(z), then

Since an inner automorphism is a product of Whitehead automorphisms, the inner automorphism γ in Equation (8.9) is not needed. Thus, for some product of Whitehead automorphisms ψ of F (X), we may write

The graph ̂Γ is deterministic, and since φ is surjective, for all y ∈ Y there exists a self-loop at 1 with label y. Thus, there can be no other vertices because of determinism. The final graph ̂Γ is therefore a rose: a graph with one vertex 1, in which the set of loops can be identified with X̃. Therefore, we have λ̂= ̂φ for the labeling and π = ̂φ for the desired projection from F (X) on F (Y). As mentioned above, our notion of determinism does not exclude parallel edges. Thus, we may have |X| > |Y| and several x ∈ X can be mapped to the same y. If this happens, then φ is not injective and parallel self-loops with the same label appear in the rose. This concludes the proof of Theorem 8.34.

8.12 The special linear group SL(2, ℤ)

The special linear group SL(2, ℤ) consists of all 2 ×2 matriceswith integer coefficients and determinant 1. This group acts on the complex numbers without the rational numbers by linear fractional transformations: if and z ∈ ℂℚ, we set

Since we have M ⋅ z ∈ ℚonly if z itself is rational. The group SL(2, ℤ) acts on the upper half plane ℍ = {z ∈ ℂ| im(z) > 0 }, and also analogously on { z ∈ ℂ| im(z) < 0 } and ℝ ℚ. To see this, write z = r + is and z = r − is with r, s ∈ ℝ. Then

Since zz̄ ∈ ℝand ad −bc = 1, we obtain that the imaginary part in is im(z) up to a multiplication by a positive real number. Moreover, the operation is a group operation

Also M ⋅ z = z for all z if and only if or The kernel of the homomorphism corresponding to the group operation is therefore exactly the subgroup {±1} ⊆ SL(2, ℤ), which is also the center of SL(2, ℤ). In general, the center of a group is the subgroup of those elements which commute with all other elements of the group. In particular, the center is a normal subgroup.

The modular group PSL(2, ℤ) is defined as the quotient SL(2, ℤ)/{±1}. Especially, the homomorphism of PSL(2, ℤ) into the group of all invertible maps from ℍ to ℍ is injective. In other words, PSL(2, ℤ) is a discrete subgroup of the group of linear fractional transformations from ℍ to ℍ, in particular, PSL(2, ℤ) acts “faithfully” on the upper half plane. The topic of this section is to give algebraic descriptions of SL(2, ℤ) and PSL(2, ℤ). We will show that SL(2, ℤ) is the amalgamated product of ℤ/4ℤ and ℤ/6ℤsuch that the amalgamation is over their respective cyclic subgroups of order 2; and the modular group is the free product of ℤ/2ℤ and ℤ/3ℤ. We start with the study of the matrices in SL(2, ℤ) without negative entries. This forms a monoid, henceforth denoted by SL(2, ℕ). We will see that SL(2, ℕ) is the free monoid on two generators T and U where T, U ∈ SL(2, ℕ) are given by

Proposition 8.36. The monoid SL(2, ℕ) is free with basis {T, U}.

Proof: Let with a, b, c, d ≥ 0. Then a ≥ c or d ≥ b because ad − bc = 1. Suppose that a > c and d > b. Then

and, hence, b = c = 0 and a = d = 1. Therefore, (a − c)(b − d) ≥ 0 for That is, if is not the identity matrix, then either the upper row is strictly greater than the lower, row or, conversely, the lower row is strictly greater than the upper row. Note that a = c and b = d is impossible. A row is strictly greater than another one if, first, it is greater or equal in both components and, second, strictly greater in at least one component. Next, we show that the monoid SL(2, ℕ) is freely generated by T and U. We have

This shows that every product of a (nonempty) sequence of T’s and U’s results in a matrix with one row strictly greater than the other one. Moreover, each matrix in SL(2, ℕ) can uniquely be written as a product of T’s and U’s. This is true for the identity matrix, which corresponds to the empty word. Now, let be a matrix in which the upper row is strictly greater than the lower row. Note that c +d > 0. Then a' = a +c and b' = b + d for a, b ∈ ℕ and

Thus the first factor must be T. Since a + b + c + d < a' + b' + c + d, we can now decompose inductively. If the lower row is strictly greater than the upper row, then the first factor is U, and the induction argument remains unchanged.

□

The geometric interpretation of the matrices T and U is given by their effect on a complex number z with im(z) > 0. For each n ∈ ℤ, we obtain

In particular, the matrices T and U have both infinite order. Next, we consider the two matrices S, R ∈ SL(2, ℤ) given by

We have S2 = −1 and R3 = −1; hence, S has order 4 and R has order 6. Moreover, −R = ST and Geometrically (in the complex plane) we may interpret S, T, R, and R2 as follows:

Hence S(z) is an involution, T(z) a translation, and R(z) a rotation of order 3. Recall that R has order 6 in SL(2, ℤ), but, in the quotient group PSL(2, ℤ), its order is 3.

Lemma 8.37. Any two of the four matrices R, S, T, U generate the group SL(2, ℤ).

Proof: Any two of the four matrices generate the three matrices R, T and U by the above formulas, and hence, also S. This follows by an extensive case distinction. For instance, if we have T and U then we obtain R−1 = R5 by

□

Now, let We show that A is in the subgroup generated by S, T, and U. If c = 0 then d ≠ 0, and we replace A by AS. If c < 0 then we replace A by −A = S2A. Now we may assume that c > 0. If we replace A by TnATn for a sufficiently large n, then, without loss of generality, we obtain a, b, c, d > 0. Now A is already in the submonoid generated by T and U (Proposition 8.36). This proves the lemma.

Theorem 8.38. The groups PSL(2, ℤ) and SL(2, ℤ) have a presentation with R and S as generators and S2 = R3 = 1 or S4 = R6 = S2R3 = 1, respectively, as defining relations. Consequently, PSL(2, ℤ) is the free product of ℤ/2ℤ and ℤ/3ℤ, and SL(2, ℤ) is the amalgamated product of ℤ/4ℤ with ℤ/6ℤ such that the amalgamation is over their respective cyclic subgroups of order 2.

Proof: The product of the two cyclic groups ℤ/2ℤ and ℤ/3ℤ has a presentation G' = {r, s}∗/{s2 = r3 = 1}. The amalgamated product of ℤ/4ℤ and ℤ/6ℤ, with amalgamation of their respective cyclic subgroups of order 2, has a presentation G = {r, s}∗/ {s4 = r6 = 1, s2 = r3}. Consider the homomorphisms φ: G → SL(2, ℤ) and φ' : G' → PSL(2, ℤ) induced by r ↦ R and s ↦ S. Both homomorphisms are surjective by Lemma 8.37. Now, let w ∈ {r, s}∗ with φ(w) = 1 and φ(w) = 1, respectively. If w ∈ s∗ then it follows already w = 1 in G and w = 1 in G, respectively. The analogous statement holds for w ∈ r∗. Each element of G (respectively G), which is not in the subgroup generated by a conjugate of s or r, can be written as a word w = sj0 ri1 (sri2 )⋅ ⋅⋅ (srim )sjm with m ≥ 1 and 0 ≤ j0 ≤ 3 (respectively 0 ≤ j0 ≤ 1), 0 ≤ jm ≤ 1, and 1 ≤ ik ≤ 2 for 1 ≤ k ≤ m. Note that in G, we can move the factors s2 and r3 to the left, and that we have s2 = r3. The only difference between G and G' is the range of j0. The values for j0 are 0, 1, 2, 3 in G and 0, 1 in G. It is enough to show that φ(w) ≠ 1 for such a word w. After a suitable conjugation with r or r2, if necessary, we may assume that w = ri1 s ⋅⋅ ⋅ rim−1 srim , m ≥ 2, with 1 ≤ ij ≤ 2 for j = 1, . . . , m and 1 ≤ i1, im ≤ 2. Now, we apply a ping-pong argument: the modular group also operates on ℝ ℚ by virtue of the above formulas. We obtain , and . In particular, R and R2 map positive values to negative ones, and S maps negative values to positive ones. Hence, if we apply φ(w) on any arbitrary positive, irrational number like then we obtain a negative value for φ(w)(z). This implies φ(w) ≠ 1.Since T and U generate a free submonoid in the group SL(2, ℤ), we might suspect that they generate a free subgroup in SL(2, ℤ). But this is in contradiction to Lemma 8.37 because SL(2, ℤ) contains elements of order 4. Nevertheless, both SL(2, ℤ) and PSL(2, ℤ) contain all free groups with finite or countable rank. To show this, it is enough to prove the existence of a subgroup of rank 2. For this purpose, we consider the following two matrices in SL(2, ℤ):

□

Corollary 8.39. The matrices A and B generate a free subgroup of rank 2 of the modular group PSL(2, ℤ) and, therefore, also of the group SL(2, ℤ).

Proof: Let W ∈ PSL(2, ℤ) be a nonempty reduced word in A, A−1, B and B−1, written in terms of R and S. By Theorem8.38, we may write PSL(2, ℤ) as {R, S}∗/{S2 = R3 = 1}, and we obtain normal forms by cancelling the factors S2 and R3 in W. The normal forms for A, A−1, B, and B−1 are A = RSR, A−1 = R2SR2, B = SRSRS, and B−1 = SR2SR2S.

□

We have to show that W ≠ 1 in PSL(2, ℤ). For this purpose, it is enough to prove by induction that the last letter X ∈ {A, A−1, B, B−1} of W determines the last three letters of the normal form of W in {R, S}∗: for X = A it is RSR, for X = A−1 it is SR2, for X = B it is SRS, and for X = B−1 it is R2S. In particular, the normal form is not the empty word, and therefore W ≠ 1 in PSL(2, ℤ).

Remark 8.40. The embedding of the free group of rank 2 in the group SL(2, ℤ) gives another proof of Proposition 8.12. Since SL(2, ℤ) is residually finite, free groups are residually finite, too. In order to see this, it is enough to consider free groups of finite rank; and free groups of finite rank can be embedded into a free group of rank 2 by Exercise 8.8, which appears as a subgroup of SL(2, ℤ).

◊

The Baumslag–Solitar group BS(2, 3) from Example 8.8 is not Hopfian by Exercise 8.10. Hence, it is not residually finite by Exercise 8.9. Therefore, in contrast to free groups, BS(2, 3) cannot be embedded into SL(2, ℤ) or into any other linear group.

Exercises

8.1. Let M = Σ∗/S for a finite length reducing and confluent semi-Thue system S. Show that the word problem for M is decidable in linear time.

8.2. Prove Proposition 8.11, that is, show that all residually finite and finitely presented monoids have a decidable word problem.

8.3. Let (Σ, I) be a finite, undirected graph and let

be the corresponding free partially commutative monoid. A transitive orientation of (Σ, I) is a subset I+ ⊆ I with I = {(a, b), (b, a) | (a, b) ∈ I+ } such that (a, b), (b, c) ∈ I+ implies (a, c) ∈ I+. Show:

8.4. Let C(Σ, I) = Σ∗/{ a2 = 1, ab = ba | (a, b) ∈ I } be a finitely generated right-angled Coxeter group.

Consider the finite semi-Thue system T ⊆ F∗ × F∗ with the rules

Show: T is convergent and F∗/ T is isomorphic to the Coxeter group C (Σ, I).

8.5. Show that the class of rational sets is closed under homomorphisms, but not closed under inverse homomorphisms.

Hint: For the nonclosure use the standard fact that { anbn | n ∈ ℕ} is not rational (i.e., regular) for a two letter alphabet {a, b} and that the family RAT({a, b}∗) is closed under intersection.

8.6. Let M = {a, b, c}∗/{ac = ca, bc = cb} be the direct product of the free monoids c∗ and {a, b}∗. Show that the family of rational sets RAT(M) is not closed under intersection. Hint: Reuse ideas from Exercise 8.5.

8.7. Show that in free groups, the intersection of two finitely generated subgroups is finitely generated.

Hint: Use that the set of reduced words which belong to a finitely generated subgroup is regular.

8.8. Let F ({a, b}) = F2 be the free group with two generators. Show that the set U = { anba−n | n ∈ ℤ} ⊆ F2 is the basis of a free subgroup. In particular, F2 contains each

free group of finite or countable rank as a subgroup.

8.9. Show that finitely generated, residually finite groups are Hopfian.

8.10. Show that the Baumslag–Solitar group BS(2, 3) = {a, t}∗/{ta2t−1 = a3} is not Hopfian.

8.11. Show that, during the normal form computation (corresponding to Example 8.20) in the group BG(1, 2), extremely long words may arise; for instance, words of the form aτ(n). Here τ : ℕ → ℕis the tower function defined by τ(0) = 1 and τ(n + 1) = 2τ(n).

8.12. Let G be a non-Abelian finite group and let Z (G) denote its center, that is Z (G) = { g ∈ G | ∀h ∈ G: gh = hg }. Show that the index of Z(G) is at least 4.

Using this fact, answer the following question. “What is the probability that two group elements commute?” More precisely, we seek an upper bound for the probability in non-Abelian finite groups, which is tight for certain groups. The answer has been given in a paper (with the question as its title) published by Gustafson in 1973.

8.13. Use Theorem 6.5 for proving Corollary 8.30: commuting elements in a free group lie in a common cyclic subgroup.

8.14. In this exercise, we will show that the automorphism group of a finitely generated free group F (Σ) is generated by at most four elements.

8.15. By Proposition 8.36, all words over the alphabet {T, U} (and hence also all bit sequences in {0, 1}∗) may be encoded as 2 × 2-matrices with entries in ℕ. Moreover, each matrix in SL(2, ℕ) describes a unique word in {T, U}∗. Now, let W ∈ {T, U}∗ be a word of length ℓ and let be the corresponding matrix product. Show that ai ≤ Fℓ+1 for i = 1, 2, 3, 4, where Fℓ+1 is the (ℓ + 1)th Fibonacci number. As usual, F0 = 0, F1 = 1, and Fn+1 = Fn + Fn−1 for n ≥ 1.