Representation theory of finite groups and commutativity degree

If G is a finite group, we define its commutativity degree P(G) as the probability that two elements of G commute, that is

\displaystyle P(G)= \frac{1}{| G \times G|} \cdot | \{ (g,h) \in G \times G \mid [g,h]=1 \} |.

It is surprising that the value of P(G) may give strong information about G. In particular, we prove here the two following results:

Theorem 1: Let G be a finite group. If P(G) > 5/8 then G is abelian.

Theorem 2: Let G be a finite group. If P(G)>1/2 then G is nilpotent.

In fact, the two theorems above will follow from the upper degree equation bound:

Theorem 3: Let G be a finite group and let G' denote its commutator subgroup. Then

\displaystyle P(G) \leq \frac{1}{4} \left( 1+ \frac{3}{|G'|} \right).

Indeed, if G is non-abelian then |G'| \geq 2, and the upper degree equation bound implies P(G) \leq 5/8; therefore, theorem 1 is proved. Then, if P(G) >1/2 then the upper degree equation bound implies |G'| < 3. If |G'|=1, G is abelian and there is nothing to prove. Otherwise, |G'|=2 ie. G' = \{1,c \} for some c \neq 1. For all g \in G, [c,g] \in G', so either [c,g]=1 or [c,g]=c which implies c=1; therefore, c \in Z(G). We proved that G' \subset Z(G), so [G,G']= \{1\}; in particular G is nilpotent.

In order to prove Theorem 3, we first notice the following link between commutativity degree and the number of conjugacy classes of G:

Lemma 1: Let G be a finite group. Then \displaystyle P(G)= \frac{k(G)}{|G|} where k(G) denotes the number of conjugacy classes of G.

Proof. If x \in G, let C(x) denote the centralizer of x and C_1,\dots, C_{k(G)} denote the conjugacy classes of G; for convenience, let x_i be an element of C_i. Then

CD

Finally, the lemma follows. \square

Therefore, computing P(G) is equivalent to computing |G| and k(G). But we know that the number of conjugacy classes is quite related to representation theory, and indeed we will prove Theorem 3 thanks to representation theory.

Definitions: Let G be a finite group. A (complex) representation is a morphism G \to \mathrm{Aut}(V) for some complex vector space V (of finite dimension); the degree of the representation is the dimension of V. By extension, we often say that V is a representation.

Any finite group admits a representation. For example, if \mathbb{C}[G] denotes the complex vector space with G as a basis, the left multiplication extends to a representation, namely the regular representation of G.

If V is a representation, a subrepresentation is a subspace W stable under the action of G. A representation is irreducible if it does not contain a nontrivial subrepresentation (ie. different from itself and \{0\}).

If V,W are two representations, we define the direct sum V \oplus W as the representation defined by the action g \cdot (v \oplus w) = (g \cdot v) \oplus (g \cdot w) for all g \in G, v \in V and w \in W.

Two representations V and W are isomorphic if there exists a G-invariant isomorphism V \to W.

Our first result is:

Property 1: (Maschke) Any representation is a direct sum of irreducible representations.

Proof. Let G be a finite group and V be a representation. If V is irreducible, there is nothing to prove, so we suppose that V contains a nontrivial representation W. Then, if ( \cdot , \cdot) is any scalar product on V, it is possible to define a scalar product \langle \cdot, \cdot \rangle invariant under G, for example by

\displaystyle \langle u,v \rangle = \sum\limits_{g \in G} ( g \cdot u, g \cdot v).

Therefore, because W is stable under G, the orthogonal W^{\perp} for \langle \cdot , \cdot \rangle so is, and V = W \oplus W^{\perp}. Finally, Property 1 follows by induction on the dimension of V. \square

Of course, in the decomposition given by Property 1, the same representation may appear several times (up to isomorphism). Thanks to a theorem due to Frobenius, this number may be characterized.

Definitions: Let G be a finite group. Let R(G) denote the set of central functions G \to \mathbb{C}, that is the functions f : G \to \mathbb{C} satisfying f(ghg^{-1})=f(h) for all g,h \in G. We endow R(G) with the scalar product

\displaystyle \langle f , g \rangle = \frac{1}{ |G| } \sum\limits_{x \in G } \overline{ f(x) } g(x).

Clearly, the dimension of R(G) is k(G), the number of conjugacy classes of G (a basis of R(G) is given by the set of functions taking the value 1 on a fixed conjugacy class and 0 otherwise).

Associated to a representation \rho : G \to V, we define a character \chi_V : G \to \mathbb{C} defined by \chi_V(g)= \mathrm{tr}( \rho(g)). A character is said irreducible if the associated representation so is.

Property 2: (Frobenius) Let G be a finite group. The set of irreducible characters defines an orthonormal basis of R(G).

Proof. We first prove that the family of irreducible characters is orthonormal. Of course, two isomorphic representations \rho_i : G \to \mathrm{Aut}(V_i) are conjugated, so their characters are equal; therefore, it is sufficient to prove that two irreducible representations V,W satisfy \langle \chi_V, \chi_W \rangle =1 if V and W are isomorphic and \langle \chi_V, \chi_W \rangle=0 otherwise.

We define the representation \mathrm{Hom}(V,W) as the representation defined by the action g \cdot f(v) = g \cdot f(g^{-1} \cdot v) for every f \in \mathrm{Hom}(V,W), g \in G and v\in V. Now, let \mathrm{Hom}_G(V,W) denote the set of fixed points of the action of G on \mathrm{Hom}(V,W).

Claim 1: (Schur) \mathrm{dim} ~ \mathrm{Hom}_G(V,W)=1 if V and W are isomorphic, and 0 otherwise.

A nontrivial element of \mathrm{Hom}_G(V,W) defines a G-invariant isomorphism V \to W, hence \mathrm{dim} ~ \mathrm{Hom}_G(V,W)=0 if V and W are not isomorphic. From now on, suppose that V and W are isomorphic, and let j : V \to W be a G-invariant isomorphism.

Let f \in \mathrm{Hom}_G(V,W). Then j^{-1} \circ f \in \mathrm{Hom}_G(V,V). Let \lambda \in \mathbb{C} be an eigenvalue of j^{-1} \circ f, so that g := j^{-1} \circ f - \lambda \mathrm{Id}_V is not invertible. Notice that \mathrm{ker}(g) is a subrepresentation of V, so \mathrm{ker}(g)=V because V is irreducible and g is not invertible. We deduce that g \equiv 0 that is f = \lambda \cdot j.

We just proved that \mathrm{Hom}_G(V,W) is one-dimensional. \square

Therefore, it is sufficient to prove that \langle \chi_V, \chi_W \rangle =\mathrm{dim} ~ \mathrm{Hom}_G(V,W). We left as an exercise that \chi_{\mathrm{Hom}(V,W)} = \overline{\chi_V} \cdot \chi_W. In particular, we deduce that \langle \chi_V, \chi_W \rangle = \frac{1}{|G|} \sum\limits_{g \in G } \chi_{\mathrm{Hom}(V,W)} (g). Now,

Claim 2: For any representation \rho : G \to \mathrm{Aut}(V), \mathrm{dim} ~ V^G = \frac{1}{|G|} \sum\limits_{g \in G} \chi_V(g) where V^G denotes the set of fixed points.

Let f = \frac{1}{ |G| } \sum\limits_{g \in G} \rho(g) \in \mathrm{Aut}(V). It is easy to show that \rho(h) \circ f= f for all h \in G, so that we deduce that f \circ f = f. Therefore, V = \mathrm{ker}(f) \oplus f(V). Now we notice that f(V)=V^G. Indeed, if u=f(v) \in f(V) then g \cdot u = \rho(g) \circ f(v) = f(v)=u for all g \in G, hence u \in V^G; conversely, if u \in V^G, u = \frac{1}{|G|} \sum\limits_{g \in G} \rho(g)(u) =f(u) hence u \in f(V). We conclude that

\displaystyle \mathrm{dim} ~ V^G = \mathrm{dim} ~ f(V) = \mathrm{tr}(f) = \frac{1}{|G|} \sum\limits_{g \in G} \chi_V(g). \square

Finally, from Claim 1 and Claim 2, we deduce that the family of irreducible characters is orthonormal. Now, if E denotes the subspace of R(G) spanning by the irreducible characters, we want to prove that E= R(G) or equivalently that E^{\perp}= \{ 0 \} .

So let \varphi \in E^{\perp}. We want to prove that, for any representation \rho_V : G \to \mathrm{Aut}(V), the function f = \sum\limits_{g \in G} \overline{ \varphi(g) } \rho_V(g) is zero. According to Property 1, V is a direct sum of irreducible representations V_1 \oplus \cdots \oplus V_n; in particular, \rho_V= \rho_{V_1} \oplus \cdots \oplus \rho_{V_n}. Therefore, we may suppose without loss of generality that V is irreducible.

Now, it is easy to show that \rho(g) \circ f \circ \rho(g)^{-1} =f for every g \in G, so that f \in \mathrm{Hom}_G(V,V). But \mathrm{Id}_V \in \mathrm{Hom}_G(V,V) and \mathrm{dim} ~ \mathrm{Hom}_G(V,V)=1 according to Claim 1, so f = \lambda \cdot \mathrm{Id}_V for some \lambda \in \mathbb{C}. Now,

\lambda \cdot \dim (V)= \mathrm{tr}(\lambda \cdot \mathrm{Id}_V) = \mathrm{tr}(f)= \sum\limits_{g \in G} \overline{ \varphi(g) } \chi_V(g)= |G| \cdot \langle \varphi, \chi_V \rangle = 0,

hence f=0. Now, we apply this result for the regular representation \mathbb{C}[G]: for every h\in G,

\displaystyle 0= \sum\limits_{g \in G} \overline{ \varphi(g) } \rho_V(g) \cdot h = \sum\limits_{g \in G} \overline{ \varphi(g) } \cdot gh,

hence \varphi(g)=0. We just prove that \varphi=0, so E^{\perp} = \{ 0 \}. \square

We now are able to precise Property 1:

Property 3: Let G be a finite group and let W_1,\dots, W_n denote its irreducible representations up to isomorphism. If V is a representations of G, then

\displaystyle V \simeq \bigoplus\limits_{i=1}^n W_i^{\langle \chi_V, \chi_{W_i} \rangle }.

Proof. According to Property 1, V may be written as a direct sum of W_i, say W_{i_1} \oplus \cdots \oplus W_{i_r}. Then \langle \chi_V, \chi_{W_i} \rangle = \sum\limits_{k=1}^r \langle \chi_{W_k}, \chi_{W_i} \rangle because \chi_V= \chi_{W_{i_1}} + \cdots + \chi_{W_{i_r}}. But we saw during the proof of Property 2 that \langle \chi_V, \chi_W \rangle=1 if V and W are isomorphic and 0 otherwise. Therefore, \langle \chi_V, \chi_{W_i} \rangle is the number of representations in the decomposition isomorphic to W_i. So Property 3 follows. \square

Property 3 is our main result from representation theory, and now we are able to prove the two following corollaries:

Corollary 4: Let G be a finite group. The number of conjugacy classes is equal to the number of irreducible representations up to isomorphism.

Proof. We already noticed that isomorphic representations lead to equal characters. Conversely, Property 3 implies that two representations with the same character are isomorphic. Therefore, k(G) is equal to the dimension of R(G), \mathrm{dim} ~ R(G) is equal to the number of irreducible characters according to Property 2, and now the number of irreducible characters is equal to the number of irreducible representations. \square

Corollary 5: Let G be a finite group. Then \displaystyle |G|= \sum\limits_{W \ \mathrm{irr.}} \deg(W)^2 where the sum is taken over the set of irreducible representations up to isomorphism.

Proof. Let V= \mathbb{C}[G] be the regular representation. Let V= \bigoplus\limits_{W \ \mathrm{irr.}} W^{ \langle \chi_V, \chi_W \rangle } be the decomposition given by Property 3. Then

\displaystyle |G| = \dim(V)= \chi_V(1) = \sum\limits_{W \ \mathrm{irr.}} \langle \chi_V, \chi_W \rangle \cdot \chi_W(1).

Of course, \chi_W(1)= \dim(W) so it is sufficient to prove that \langle \chi_V, \chi_W \rangle = \dim(W). Notice that \rho_V(g) is a permutation matrix, so that \mathrm{tr}(\rho_V(g)) is the number of fixed points of the function h \mapsto gh from G to itself; therefore, \mathrm{tr}(\rho_V(g))=|G| if g=1 and 0 otherwise. Hence

\displaystyle \langle \chi_V, \chi_W \rangle = \frac{1}{ |G| } \sum\limits_{g \in G} \overline{ \chi_V (g) } \cdot \chi_W (g) = \chi_W (1) = \dim(W).

Corollary 5 follows. \square

Now we are ready to prove Theorem 3:

Proof of Theorem 3. Let W_1, \dots, W_{k(G)} denote the irreducible representations of G up to isomorphism. Representations of degree 1 are only morphisms from G to \mathbb{C}, so the number of such representations is equal to the number of morphisms from the abelian group G/G' to \mathbb{C}.

But this number turns out to be [G:G'] because the number of morphisms from a finite abelian group A to \mathbb{C} is precisely |A|; we leave this statement as an exercise (hint: argue by induction on the number of factors in the decomposition of A as a direct sum of cyclic groups).

Therefore, the formula given by Corollary 5 may be written as

\displaystyle |G| = [G:G'] + \sum\limits_{i=[G:G']+1}^{k(G)} \dim(W_i)^2,

where \dim(W_i) \geq 2. Therefore,

|G| \geq [G:G'] + 4 ( k(G) - [G:G'] )

and Theorem 3 follows. \square

In fact, the relation

\displaystyle |G| = [G:G'] + \sum\limits_{i=[G:G'] +1}^{k(G)} \dim(W_i)^2

proved above may be quite useful to compute P(G) for some small groups. For example, if Q_8 denotes the quaternion group, its commutator subgroup is \{ \pm 1 \}, so the relation above becomes 8= 1+1+1+1+2^2; therefore, according to Corollary 4, Q_8 has five conjugacy classes, hence P(Q_8)=5/8. (Noticing that Q_8 is not abelian, we deduce that Theorem 1 is optimal.)

Another example is the symmetric group S_3: its commutator subgroup is \{ \mathrm{Id}, \ (123), \ (132) \}, so the relation above becomes 6= 1+1+2^2; therefore, S_3 has three conjugacy classes, hence P(S_3)=1/2. (Noticing that S_3 is not nilpotent, since [S_3, [S_3,S_3]]= [S_3,S_3]=A_3, we deduce that Theorem 2 is optimal; however, a lot a nilpotent groups satisfies P(G) \leq 1/2 because we saw that a group satisfying P(G) >1/2 has nilpotent-length at most two.)

For more information on commutativity degree of finite groups, see Anna Castelaz’s thesis Commutativity degree of finite groups. In particular, an elementary proof of Theorem 1 based on conjugacy class equation can be found there, as well as a complete classification of groups satisfying P(G) \geq 1/2 (see Proposition 5.1.4):

Theorem: Let G be a finite group. If P(G) \geq 1/2, then either

  • G is abelian,
  • or G \simeq P \times A for some abelian group A and some 2-group P (in this case, |G'|=2),
  • or G \simeq G_m \times A where A is an abelian group, m \geq 1 and

G_m= \langle a,b \mid a^3=b^{2^m}=1, \ bab^{-1}=a^{-1} \rangle.

On subgroups of surface groups

It is known that a closed (ie. connected, compact without boundary) surface is homeomorphic to a sphere or to a connected sum of finitely-many tori or projective spaces. Let S_g (resp. \Sigma_g) denote the connected sum of g tori (resp. projective spaces). Because \chi(A \sharp B)= \chi(A)+ \chi(B)-2, we easily deduce the Euler characteristics \chi(S_g)=2-2g and \chi(\Sigma_g)=2-g; the integer g is called the genus.

ClosedSurfaces

A surface group is a group isomorphic to the fundamental group of one of these surfaces. If G is a surface group, two cases happens: either G is the fundamental group of an orientable surface S_g of genus g and

G = \langle a_1,b_1, \dots, a_g,b_g \mid [a_1,b_1] \cdots [a_g,b_g]=1 \rangle,

or G is the fundamental group of a non-orientable surface \Sigma_g of genus g and

G = \langle a_1, \dots, a_g \mid a_1^2 \cdots a_g^2=1 \rangle.

(Just write S_g or \Sigma_g as a polygon with pairwise identified edges, and apply van Kampen’s theorem; for more information, see Massey’s book Algebraic Topology.)

Our main result is the following characterization of subgroups of a surface group:

Theorem 1: Let G be the fundamental group of a closed surface S and H be a subgroup. Either H has finite index h  in G and H is isomorphic to the fundamental group of a closed surface whose Euler characteristic is h \cdot \chi (S), or H is an infinite-index subgroup of G and is free.

For this note, I was inspired by Jaco’s article, On certain subgroups of the fundamental group of a closed surface. The proof of property 2 below comes from Stillwell’s book, Classical topology and combinatorial group theory.

Essentially, the theorem above follows from Property 2 below:

Property 2: The fundamental group of a non-compact surface is free.

Combined with Property 3, let us first notice some corollaries of Theorem 1 on the structure of surface groups.

Property 3: The abelianization of \pi_1(S_g) (resp. \pi_1(\Sigma_g)) is isomorphic to \mathbb{Z}^{2g} (resp. \mathbb{Z}^{g-1} \times \mathbb{Z}_2). Therefore, two closed surfaces S_1 and S_2 are homeomorphic if and only if their fundamental groups are isomorphic.

Proof. In order to compute the abelianizations, it is sufficient to add all the possible commutators as relations in the presentations given above. Therefore,

\pi_1(S_g)^{ab} \simeq \langle a_1,b_1 , \dots, a_g, b_g \mid [a_i,a_j] = [b_i,b_j ] = [a_i,b_i]=1 \rangle \simeq \mathbb{Z}^{2g}

and, with z: = a_1\cdots a_g,

\pi_1( \Sigma_g)^{ab} \simeq \langle a_1, \dots, a_{g-1},z \mid [a_i,a_j] = [a_i,z]=1, \ z^2=1 \rangle \simeq \mathbb{Z}^{g-1} \times \mathbb{Z}_2.

Consequently, the \pi_1(S_g) and \pi_1( \Sigma_1) define a family of pairwise non-isomorphic groups, and the conclusion follows from the classication of closed surfaces. \square

Corollary 1: Let G be the fundamental group of a closed surface different from the projective space. Then G is torsion-free.

Proof. The abelianization of a surface group is cyclic if and only if it is the fundamental group of the projective plane; therefore, the same conclusion holds for the surface groups themself, and we deduce that G has no cyclic subgroup of finite index. Consequently, the cyclic subgroup generated by a non trivial element of G is free, that its order is infinite. \square

Corollary 2: Let G be the fundamental group of a closed surface S satisfying \chi(S) \leq 0 and H be a subgroup generated by k elements. If k < 2- \chi (S) then H is free.

Proof. If \chi(S)=0, S is a torus or a Klein bottle, and the statement just says that its fundamental group is torsion-free, that follows from Corollary 1.

From now on, we suppose that \chi(S)<0. According to Property 3, the abelianization of G has rank 2- \chi(S). We deduce that the smallest cardinality of a generating set of G has cardinality 2- \chi(S); in particular, H \subsetneq G because k < 2- \chi(S). Suppose that H has finite index h. Then H is the fundamental group of a closed surface \Sigma and \chi(\Sigma)= h \cdot \chi(S). In the same way, necessarily k \geq 2- \chi(\Sigma). Therefore,

k \geq 2- \chi(\Sigma) = 2-h \cdot \chi(S) > 2 - \chi(S),

a contradiction. \square

Corollary 3: Let G be the fundamental group of a closed surface S satisfying \chi(S)<0. If x,y \in G \backslash \{1\} commute, then there exist z \in G and m, n \in \mathbb{Z} such that x=z^n and y=z^m.

Proof. Let g \geq 2. Then it is easy to find two epimorphisms

\pi_1 (S_g ) \twoheadrightarrow \langle a_1 , b_1 , a_1 , b_2 \mid [ a_1, b_1 ] = [ a_2, b_2 ] ^{-1} \rangle \simeq \mathbb{F}_2 \underset{\mathbb{Z}}{\ast} \mathbb{F}_2

and

\pi_1 ( \Sigma_g ) \twoheadrightarrow \langle a_1, a_2 \mid a_1^2 = a_2^{-1} = 1 \rangle \simeq \mathbb{Z}_2 \ast \mathbb{Z}_2.

Therefore, the groups \pi_1(S_g) and \pi_1(\Sigma_g) are not abelian for g \geq 2, and we deduce that the sphere, the projective plane and the torus are the only closed surfaces whose fundamental group is abelian.

Because S satisfies \chi(S)<0, we conclude that G has no finite-index abelian subgroup, and that the subgroup genereted by \{ x,y \} is necessarily free; since x and y commute, the subgroup turns out to be cyclic and the conclusion follows. \square

Corollary 4: The commutator subgroup of a surface group is free.

Proof. Let G be the fundamental group of a closed surface S. If S is a projective space, then G \simeq \mathbb{Z}_2 and its commutator subgroup is trivial (in particular free). Otherwise, thanks to Property 3 we know that the abelianization of G is infinite; therefore, the commutator subgroup is an infinite-index subgroup and so is free. \square

Proof of property 2. First, we notice that the fundamental group of a connected compact surface with boundary is free. If S is such a surface, by gluing a disk along each boundary component, we get a closed surface \overline{S}; therefore, S is homotopic to a punctured closed surface. Because a closed surface may be identified with a polygon whose edges are pairwise identified, it is not difficult to prove that a punctured closed surface is homotopic to a graph (by “enlarging the holes”); in particular, we deduce that \pi_1(S) is free.

The figure below shows that the fundamental group a 2-punctured torus is a free group of rank three.

2-punctured torus

From now on, let S be a non-compact surface. In order to prove that \pi_1(S) is free, we want to find a sequence of compact surfaces with boundary

S_1 \subset S_2 \subset \cdots \subset S

such that S= \bigcup\limits_{i \geq 1} S_n and  that the inclusions S_i \hookrightarrow S_{i+1} are \pi_1-injective. It is sufficient to conclude since we proved above that the fundamental group of a compact surface with boundary is free.

Take a triangulation of S so that S may be identified with a simplicial complex; let \Delta_1,\Delta_2, \dots denote the 2-simplexes. Without loss of generality, we may suppose that \Delta_{i+1} is adjacent to one of the simplexes \Delta_1, \dots , \Delta_i; otherwise, number the simplexes by taking first the simplexes adjacent to a vertex P cyclically, then the simplexes within 1 from P, then the simplexes within 2 from P, etc.

Notice that a connected union of simplexes may not be a surface; however, if \Delta_i' denotes the union of \Delta_i with a small closed ball around each of its vertices, a connected union of \Delta_i' is automatically a compact surface with boundary. Now, we construct the surfaces S_n by induction:

Let S_1=\Delta_1'. Now suppose that S_n is given. If \Delta_{n+1}' \subset S_n, then set S_{n+1}=S_n; otherwise, define S_{n+1} as the union of S_n with \Delta_{n+1}' and with the disks bounding a boundary component of S_n \cup \Delta_{n+1}'.

Because S_n is a union of \Delta_i', we know that it is a compact surface with boundary. To conclude, it is sufficent to prove that the inclusion S_i \hookrightarrow S_{i+1} is \pi_1-injective. To do that, just notice that \Delta_{n+1}' is attatched on the boundary of S_n in six possible ways:

Triangles

In the first three cases, S_{n+1}= S_n \cup \Delta_{n+1}' because the boundary component bounds a disk in S if and only if it bounds a disk in S_n. So S_{n+1} clearly retracts on S_n so that the inclusion S_n \hookrightarrow S_{n+1} induces an isomorphism \pi_1(S_n) \simeq \pi_1(S_{n+1}).

In the three last cases, up to homotopy, we just glue one or two edges on a boundary component, and using van Kampen’s theorem, we notice that a free basis of \pi_1(S_{n+1}) is obtained by adding one or two elements to a free basis of \pi_1(S_n). \square

Proof of theorem 1. Let \overline{S} \to S be the covering associated to the subgroup H; in particular, \overline{S} is a surface of fundamental group H. If H is a finite-index subgroup, \overline{S} is compact and the conclusion follows. Otherwise, \overline{S} is not compact, and the conclusion follows from Property 2. \square

Freudenthal Compactification

This note is dedicated to Freudenthal compactification, a kind of compactification for some topological spaces. In particular, it will be noticed how such a compactification leads to the number of ends, a nice topological invariant, and how it can be used to classify compactifications with finitely many points at infinity. The proof of theorem 1 is mainly based on Baues and Quintero’s book, Infinite homotopy theory.

First of all, we introduce the spaces we will work with.

Definition: A generalized continuum is a locally compact, connected, locally connected, \sigma-compact, Hausdorff topological space.

Typically, a generalized continuum may be think of as a locally finite CW complex or as a topological manifold.

Let X be a generalized continuum. Because X is \sigma-compact, it is an increasing union of compact subspaces (K_n); moreover, by locally compactness, we may suppose that K_n \subset \mathrm{int} ~ K_{n+1} for all n \geq 1. Such a family of compact subspaces is called an exhausting sequence.

Definition: Let X be a generalized continuum and (K_n) be an exhausting sequence. An end \epsilon is a decreasing family (C_n) of subspaces such that C_n is an unbounded (ie. not relatively compact) connected component of X \backslash K_n.

Let E(X) denote the set of ends of X and \overline{X} = X \cup E(X). If \epsilon=(C_n) is an end and U \subset X is an open subspace, \epsilon < U will mean that C_n \subset U for some n\geq 1.

The Freudenthal compactification of X is defined as \overline{X} endowed with the topology generated by

\{ U \cup \{ \epsilon \in E(X) \mid \epsilon < U \} \mid U \subset X \ \mathrm{open} \}.

First, notice that \overline{X} does not depend on the sequence of compact subspaces we chose. Indeed, it is possible to consider the increasing functions f associating to any compact K \subset X an unbounded connected component f(K) of X \backslash K, and then to define a space \tilde{X}= X \cup F(X), where F(X) is the set of functions we just mentionned, endowed with the topology generated by

\{U \cup \{ f \in F(X) \mid f(K) \subset U \ \mathrm{for \ some \ compact} \ K \subset X \} \mid U \subset X \ \mathrm{open} \}.

Clearly, the restriction of a function f \in F(X) to the family (K_n) we fixed to construct \overline{X} defines an end of X, so there exists a natural continuous map \tilde{X} \to \overline{X}. Conversely, an end \epsilon = (C_n) naturally corresponds to a function of F(X): if K \subset X is compact, there exists some n \geq 1 such that K \subset K_n, and \epsilon(K) may be defined as the unbounded connected component of X \backslash X containing C_n. Therefore, the map \tilde{X} \to \overline{X} turns out to be a homeomorphism. In particular, \overline{X} does not depend on the sequence (K_n) since neither does \tilde{X}.

Theorem 1: Let X be a generalized continuum. Then \overline{X} is a compactification of X, that is X is a(n) (open) dense subset of \overline{X} and \overline{X} is compact.

We will prove the theorem only at the end of this note. Before that, we will mention two nice consequences of our construction. The first one is that Freudenthal compactification gives a topological invariant: the number of ends, e(X)= |E(X)|.

Theorem 2: Let X,Y be two generalized continua. If \varphi : X \to Y is a homeomorphism, then \varphi extends to a homeomorphism \overline{\varphi} : \overline{X} \to \overline{Y}; in particular, \overline{\varphi} induces a homeomorphism E(X) \to E(Y).

Proof. Let (K_n) be an exhausting sequence for X. Then (\varphi(K_n)) is an exhausting sequence for Y. Moreover, if (C_n) is an end of X then (\varphi(C_n)) is naturally an end of Y: it defines our extension \overline{\varphi} : \overline{X} \to \overline{Y}. We easily check that \overline{\varphi} is a homeomorphism. \square

Corollary: The number of ends is a topological invariant.

Of course, two non-homeomorphic spaces may have the same number of ends (eg. e(\mathbb{R}^n)=1 for all n \geq 2). However, the number of ends appears to be easy to compute in several situations, so it may be a simple way to prove that two spaces are not homeomorphic. For example:

Property: Let n,m \geq 2 and S \subset \mathbb{R}^n, R \subset \mathbb{R}^m be two finite subsets. If |S| \neq |R| then \mathbb{R}^n \backslash S and \mathbb{R}^m \backslash R are not homeomorphic.

Proof. Just notice that e(\mathbb{R}^n \backslash S)= |S| and similarly e(\mathbb{R}^m \backslash R)= |R|. \square

Our second consequence of Freudenthal compactification is the classification of all possible compactifications whose remainders are finite (the remainder of a compactification Y of a space X is Y \backslash X; sometimes, the points of the remainder are also called points at infinity).

Theorem 3: Let X be a generalized continuum and Y be a compactification of X whose remainder is finite. Then Y is obtained from \overline{X} by identifying some ends.

Therefore, Freudenthal compactification can be viewed as a maximal compactification among compactifications with finitely many points at infinity.

Proof. As above, let \overline{X} denote the Freudenthal compactification of X. Let

\overline{X} = X \cup \{ p_1, \dots, p_r \} and Y= X \cup \{ q_1,\dots, q_s \}.

For all 1 \leq i \leq s, let U_i \subset Y be an open neighborhood of q_i; we may suppose that U_i \cap U_j = \emptyset if i \neq j. Let

C= Y \backslash \bigcup\limits_{i=1}^s U_i \subset X;

notice that C is compact. For all 1 \leq i \leq r, let V_i \subset \overline{X} be a connected neighborhood of p_i disjoint from C; again, we may suppose that V_i \cap V_j = \emptyset if i\neq j.

Because V_i is connected, there exists j such that V_i \subset U_j; moreover, because U_i \cap U_j = \emptyset if i \neq j, such a j is unique. Therefore, a map f : \overline{X} \to Y may be defined by f(p_i)=q_j and f_{|X}= \mathrm{Id}_{X}.

Let I_j = \{ 1 \leq i \leq r \mid f(p_i)=q_j \}. Noticing that

f^{-1}(U_j)= \bigcup\limits_{i \in I_j} V_i \cup \{ p_i \}

is open in \overline{X} since i \in I_j if and only if p_i < U_j, we deduce that f is continuous. Moreover, f is onto.

Let \tilde{X} denote the space obtained from \overline{X} by identifying two ends p_i and p_j whenever f(p_i)=f(p_j).

ComDiagram

By construction, \tilde{f} : \tilde{X} \to Y is well-defined and into. Then, \tilde{f} is continuous since \pi is open, and onto since f is onto. Finally, \tilde{f} is a continuous bijection between two compact spaces: it is necessarily a homeomorphism. \square

We illustrate the classification given above with the following example:

FCompactification

 

Corollary 1: Let X be a generalized continuum. Then X has only one compactification with one point at infinity: its Alexandroff compactification.

Corollary 2: Let X be a generalized continuum and Y be a compactification of X whose remainder is finite. Then |Y \backslash X | \leq e(X).

In particular, we get that the circle \mathbb{S}^1 and the segment [0,1] are the only compactifications of \mathbb{R} with finitely many points at infinity. However, there is a lot of possible compactifications of \mathbb{R} with infinitely many points; more precisely, the following result can be found in K. Magill’s article, A note on compactification:

Theorem: Let K be Peano space. Then there exists a compactification X of \mathbb{R} whose remainder is homeomorphic to K.

For example, if \Gamma \subset [0,+ \infty) \times \mathbb{R} denotes the graph of the function x \mapsto \sin(1/x), then \Gamma is homeomorphic to \mathbb{R}, and X = \Gamma \cup \{ 0 \} \cup [ -1 , 1 ] is a compactification of \mathbb{R} whose remainder is homeomorphic to [0,1].

See also B. Simon’s article Some pictoral compactification of the real line to find a compactification of \mathbb{R} whose remainder is homeomorphic to the torus \mathbb{T}^2.

From now on, we turn to the proof of theorem 1.

Lemma: Let X be a generalized continuum. Then E(X) is a compact subspace of \overline{X}.

Proof of Theorem 1: Fistly, the injection X \hookrightarrow \overline{X}= X \cup E(X) is clearly a homeomorphism onto its image; therefore, from now on, X will be confunded with its image in \overline{X}. Then X is clearly dense in \overline{X}, so to conclude the proof, we only need to prove that \overline{X} is compact.

Let \{ O_i \mid i \in I \} be an open covering of \overline{X}. Because E(X) is compact, there exists J_1 \subset I finite such that for all \epsilon \in E(X), there exist j \in J_1 and an unbounded connected component C_j \subset O_j of X \backslash K_{n_j} such that \epsilon < C_j. If p= \max\limits_{j \in J_1} n_j, then \{ O_j \mid j\in J_1 \} is a finite subcovering of the unbounded connected components of X \backslash K_p.

Notice that K_p \subset \mathrm{int} ~ K_{p+1} implies that K_p \cap \partial K_{p+1} = \emptyset, so a connected component of X \backslash K_p intersects \partial K_{p+1} or is included in K_{p+1}. But \partial K_{p+1} is compact, so there are only finitely many components of X \backslash K_p intersecting \partial K_{p+1}. Therefore, if K denotes the union of K_{p+1} with the closure of the bounded components of X \backslash K_p intersecting \partial K_{p+1}, then K is compact. In particular, there exists J_2 \subset I finite such that \{ O_j \mid j \in J_2 \} is a finite subcovering of K.

Finally, we deduce that \{ O_j \mid j \in J_1 \cup J_2 \} is a finite subcovering of \overline{X}. Hence \overline{X} is compact. \square

Proof of the lemma. Let (K_n) be an exhausting sequence and let \pi(K_n) denote the set of unbounded connected components of X \backslash K_n. First notice that \pi(K_n) is finite. Indeed, if C \in \pi(K_n), it cannot be included in K_{n+1} so it intersects \partial K_{n+1}; the conclusion follows by compactness of \partial K_{n+1}. Therefore, if each \pi(K_n) is endowed with the discrete topology, from Tykhonov theorem the cartesian product \prod\limits_{n \geq 1} \pi(K_n) is compact. Because there is a natural map

\phi : E(X) \to \prod\limits_{n \geq 1} \pi(K_n),

it is sufficient to prove that \phi is a homeomorphism onto its image and that its image is closed. In order to show that \phi is continuous, we take an open set O \subset \prod\limits_{n \geq 1} \pi(K_n) of the form

\{ (C_n) \mid C_{n_1}= C_1 \subset \cdots \subset C_{n_r} = C_r \}

for some r \geq 1 and C_1 \in \pi(K_1), \dots, C_r \in \pi(K_r) fixed. Now, if

\Omega = \{ \epsilon \in E(X) \mid \mathrm{for \ all} \ 1 \leq i \leq r, \ \epsilon < C_{n_i} \} = \bigcap\limits_{i=1}^r \{ \epsilon \in E(X) \mid \epsilon < C_{n_i} \},

then \Omega is open since

\Omega = \bigcap\limits_{i=1}^r E(X) \cap \{ C_{n_i} \cap \{ \epsilon \} \mid \epsilon < C_{n_i} \},

and \phi(\Omega) \subset O. We deduce that \phi is continuous. In order to show that \phi is an open map, we take an open subspace V \subset E(X) of the form \{ \epsilon \mid \epsilon < U \} for some open subspace U \subset X, and we notice that

\phi (U) = \{ (C_n) \mid \exists i \in \mathbb{N}, \ C_i \subset U \} = \bigcup\limits_{ i \in \mathbb{N} } \bigcup\limits_{ C \in \omega_i } \{ (C_n) \mid C_i = C \}

where \omega_i is the set of elements of \pi(K_i) included in U. Therefore, \phi(U) is open, and we deduce that \phi is an open map. We just proved that \phi is a homeomorphism onto its image. Now we want to prove that \phi(E(X)) is closed. We have

\phi (E(X)) = \left\{ (C_n) \in \prod\limits_{n \geq 1} \pi(K_n) \mid \forall i \leq j, C_j \subset C_i \right\}.

Now, if i \leq j, let \phi_{ij} denotes the map that sends a connected component of X \backslash K_j to the connected component of X \backslash K_i containing it. Because C_j \subset C_i is equivalent to \phi_{ij} (C_j)=C_i, we deduce that

\phi(E(X))= \bigcap\limits_{i \leq j} M_{ij},

where

M_{ij} = \left\{ C \in \prod\limits_{n \geq 1} \pi(K_n) \mid \phi_{ij} \circ \mathrm{pr}_j (C)= \mathrm{pr}_i (C) \right\}.

But \phi_{ij} : \pi(K_j) \to \pi(K_i) is obviously continuous, \mathrm{pr}_i is continuous by definition and \pi(K_i) is Hausdorff, so M_{ij} is closed. We conclude that \phi(E(X)) is closed, and finally compact. \square

Graphs and Free Groups

Algebraic topology gives a strong link between graphs and free groups. Namely, the fundamental group of a graph is a free group, and conversely, any free group is the fundamental group of a graph. Surprisingly, using the framework of graphs and coverings gives a lot of information about free groups. Our aim here is to exhib some purely algebraic results about free groups and to prove them using graphs.

Our main references are Massey’s book, Algebraic Topology. An Introduction, Hatcher’s book, Algebraic Topology, and Stallings’ article, Topology of finite graphs. We refer to these references for the results of algebraic topology we use below.

Theorem 0: The fundamental group of a graph is free. Conversely, a free group is the fundamental group of a graph.

Proof. Let \Gamma be a graph. If T \subset \Gamma is a maximal subtree, then \Gamma/T is a bouquet of \kappa circles and \pi_1(\Gamma) \simeq \pi_1( \Gamma /T). The universal covering of \Gamma /T is a regular tree of degree \kappa, so it is also the usual Cayley graph of the free group F of rank \kappa. Because a group acts freely on its Cayley graph, we deduce that \pi_1(\Gamma) \simeq F.

Conversely, let F be a free group of rank \kappa. With the same argument, F is the fundamental group of a bouquet of \kappa circles. \square

Notice that in the first part of the proof, \kappa is the cardinal of edges of \Gamma not in T. In particular, the fundamental group of a finite graph is a free group of finite rank.

Theorem 1: A subgroup H of a free group F is free. Moreover, if [F:H], \mathrm{rk}(F) < + \infty then

\mathrm{rk}(H)=1+[F:H] \cdot (\mathrm{rk}(F)-1).

Proof. We view F as the fundamental group of a graph X. Let Y \twoheadrightarrow X be a covering satisfying \pi_1(Y) \simeq H. In particular, the covering induces a structure of graph on Y making the covering cellular; in particular, H is a free group.

If n=[F:H] < + \infty, the covering Y \twoheadrightarrow X is n-sheeted, hence \chi(Y)=n \chi(X). If T \subset X is a maximal subtree, then X is the disjoint union of T and \mathrm{rk}(F) edges, hence

\chi(X)= \chi(T)- \mathrm{rk}(F)=1- \mathrm{rk}(F);

in the same way, \chi(Y)= 1- \mathrm{rk}(H). Therefore, \mathrm{rk}(H)=1+n (\mathrm{rk}(F)-1). \square

Theorem 2: A non-abelian free group contains a free group of infinite rank.

We already proved theorem 2 using covering spaces in the previous note A free group contains a free group of any rank.

We know from theorem 1 that any finite-index subgroup of a finitely generated free group is finitely generated. Of course, the converse is false in general: \langle a \rangle is a finitely-generated subgroup of infinite index in \mathbb{F}_2 = \langle a,b \mid \ \rangle. However, the converse turns out to be true for normal subgroups.

Theorem 3: Let F be a free group of finite rank and H \leq F be a non-trivial normal subgroup. Then H is finitely generated if and only if it is a finite-index subgroup.

Proof. Suppose that H is an infinite-index subgroup. Let X be a bouquet of \mathrm{rk}(F) circles so that F be the fundamental group of X and let Y \twoheadrightarrow X be a covering such that H is the fundamental group of the graph Y. Noticing that a deck transformation associated to the covering is a graph automorphism of Y, we deduce that the group \mathrm{Aut}(Y) of graph automorphisms is vertex-transitive since the covering is normal.

Let T \subset Y be a maximal subtree. Because H is non-trivial, there exists a cycle C in Y. Moreover, because H is an infinite-index subgroup the graph Y is infinite and there exist vertices v_0,v_1, \dots of Y satisfying v_0 \in C and d(v_n,v_m) > \ell g (C) for all n \neq m; let \varphi_n \in \mathrm{Aut}(Y) be a graph automorphism sending v_0 to v_n. Then (\varphi_n(C)) is a family of disjoint cycles, so there exist infinitely-many edges of Y not in T. Therefore, H is not finitely generated. \square

Theorem 4: A free group of finite rank F is subgroup separable. In particular, it is residually finite and Hopfian (ie. every epimorphism F \twoheadrightarrow F is an isomorphism).

It is precisely the content of the note How Stallings proved finitely-generated free groups are subgroup separable. Using the same ideas, we are able to prove the following result:

Theorem 5: (Hall) Let F be a free group of finite rank and H \leq F be a finitely generated subgroup. Then H is a free factor in a finite-index subgroup of F.

Proof. Let X be a bouquet of n:= \mathrm{rk}(F) circles so that \pi_1(X) \simeq F and let Y \to X be a covering so that \pi_1(Y) \simeq H. If T \subset Y is a maximal subtree, because H is finitely generated by assumption, there exist only finitely-many edges of Y not in T; let D \subset Y be a finite connected graph containing these edges and such that T \cap D is a maximal subtree of D. Let Z denote the canonical completion C(D,X).

Now \pi_1(Z) a finite-index subgroup of \pi_1(X) \simeq F and \{ \text{edges of} \ Z \ \text{not in} \ T \cap D \} is a free basis. By construction, this basis contain a free basis of H, so H is a free factor in \pi_1(Z). \square

Theorem 6: (Howson) Let S_1 and S_2 be two finitely-genereated subgroups of a free group F. Then S_1 \cap S_2 is finitely-generated.

It is precisely the content of the note Fiber product of graphs and Howson’s theorem for free groups. We conclude with an application holding not only for free groups of finite rank but for any finitely generated group! The clue is that any group is the quotient of a free group.

Theorem 7: A finitely generated group has finitely many subgroups of a given finite index.

Proof. Let F be a free group of finite rank and n \geq 1. Clearly, a finite graph has finitely many n-sheeted covering (because such a covering is a graph with a fixed number of vertices and edges), so F has finitely many conjugacy classes of groups of index n; moreover, a finite-index subgroup’s conjugacy class is necessarily finite (if a subgroup H has index n, then xH=yH implies xHx^{-1}=yHy^{-1}). Therefore, theorem 7 holds for finitely generated free groups.

Let G be a finitely generated group. Then G is the quotient of a free group, that is there exists an epimorphism \varphi : G \twoheadrightarrow F onto a free group of finite rank. Then, for all n\geq 1, H \mapsto \varphi^{-1}(H) defines an injective map from to set of n-index subgroup of G into the set of n-index subgroup of F. The theorem 7 follows. \square

Fiber product of graphs and Howson’s theorem for free groups

Our aim is to prove Howson’s theorem for free groups followings Stallings’ article, Topology of finite graphs; this note is more or less a sequel of How Stallings proved finitely-generated free groups are subgroup separable. The construction introduced here, the fiber product, will be also useful for the generalization of ideas of Stallings to special cube complexes (due to Wise).

Another interesting proof, based on regular languages, can be found in Meier’s book untitled Graphs, groups and trees.

Theorem: (Howson) Let F be a free group of finite rank and H,K be two finitely-generated subgroups. Then H \cap K is also finitely-generated.

Let \alpha : X \to Z and \beta : Y \to Z be two immersions (ie. locally injective cellular maps) between graphs. We define the fiber product X \otimes_Z Y as the graph whose vertices are

\{ (x,y) \in X \times Y \mid \alpha(x)= \beta(y) \}

where two vertices (x_1,y_1) and (x_2,y_2) are linked by an edge if and only if \alpha(x_1)=\beta(y_1) and \alpha(x_2)=\beta(y_2) are linked by an edge in Z.

Notice that there are two obvious projections p : X \otimes_Z Y \to X, q : X \otimes_Z Y \to Y, and a natural map \gamma : X \otimes_Z Y \to Z so that we have the following commutative diagram:

CommutativeDiagram

Claim 1: \gamma : X \otimes_Z Y \to Z is an immersion.

Proof. Let (x_1,y_1) be a vertex of X \otimes_Z Y and e,f two edges starting from (x_1,y_1); let (x_2,y_2) and (x_3,y_3) denote the ending points of e and f. If \gamma(e)=\gamma(f), then \gamma(x_3,y_3)=\gamma(x_2,y_2) hence (x_2,y_2)=(x_3,y_3). Therefore, if e \neq f then e and f are two loops based at (x_1,y_1), sent via \gamma on two loops based at \gamma(x_1,y_1). So \gamma is locally injective. \square

Claim 2: \gamma_* \pi_1( X \otimes_Z Y) = \alpha_* \pi_1(X) \cap \beta_* \pi_1(Y).

First, we need the following easy lemma:

Lemma: Let \Gamma be a graph and c_1,c_2 be two reduced (ie. without round-trip) loops. If c_1=c_2 in \pi_1(\Gamma) then c_1=c_2.

Sketch of proof. The result is clear if \Gamma is a bouquet of circles, using the usual normal form for free groups. In fact, it is the only case to consider, since the quotient of \Gamma by a maximal subtree is a bouquet of circles. \square

Proof of claim 2. Because \alpha \circ p = \gamma = \beta \circ q, the inclusion

\gamma_* \pi_1( X \otimes_Z Y) \subset \alpha_* \pi_1(X) \cap \beta_* \pi_1(Y)

is clear. Conversely, let c_0 \in \alpha_* \pi_1(X) \cap \beta_* \pi_1(Y), that is there exist c_X \in \pi_1(X) and c_Y \in \pi_1(Y) such that \alpha(c_X)=c_0=\beta(c_Y) in \pi_1(Z). Of course, c_X and c_Y may be chosen reduced so that \alpha(c_X) and \beta(c_Y) so are. We deduce that \alpha(c_X)=\beta(c_Y) from our previous lemma. Therefore, by construction of X \otimes_Z Y, there exist a loop c \in \pi_1(X \otimes_Z Y) such that \gamma(c)=c_0, hence the inclusion

\alpha_* \pi_1(X) \cap \beta_* \pi_1(Y) \subset \gamma_* \pi_1 (X \otimes_Z Y). \square

Proof of Howson’s theorem. As in the previous note, we see F as the fundamental group of a finite bouquet of circles B, and we choose immersions of finite graphs \alpha : X \to B and \beta : Y \to B such that \alpha_* \pi_1(X)=H and \beta_* \pi_1(Y)= K. Then the fiber product \gamma : X \otimes_B Y \to B gives an immersion such that \gamma_* \pi_1(X \otimes_B Y) = H \cap K; because X \otimes_B Y is a finite graph (since X and Y are itself finite), we deduce that H \cap K is finitely-generated. \square

See also Graphs and Free Groups.

Surfaces and commutators in free groups

Let \mathbb{F}_n be a free group of rank n \geq 2 and w \in \mathbb{F}_n, viewed as a word on n letters. Then w is a product of commutators if and only if it belongs to the kernel of \mathbb{F}_n \twoheadrightarrow \mathbb{F}_n^{\text{ab}} \simeq \mathbb{Z}^n, that is if the sum of exponents on each letter is zero. From now on, we suppose that w satisfies this property.

Question: How to find the least integer k such that w can be written as a product of k commutators?

In their article Applications of topological graph theory to group theory, Gorenstein and Turner find a simple solution closely related to the theory of closed surfaces. More precisely, we first construct a polygon whose edges are labelled and oriented by the letters of w; then we we choose a pairing of edges, encoded in a circle graph \Gamma (topologically, a circle with a collection of interior arcs whose endpoints are pairwise distinct), and we construct a closed surface \Sigma_{\Gamma} by pairwise indentifying the edges of our polygon following the circle graph (see the figure below). Of course, the surface depends on the circle graph we chose; in particular, we define the genus \gamma(w) of w as the least genus of a surface obtained from w in the previous way.

GenusCircleGraphs

For example, \gamma(a^2b^{-1}a^{-1}ba^{-1})=1.

We then have the following surprising result:

Theorem 1: w can be written as a product of \gamma(w) commutators, and not fewer.

Moreover, Gorenstein and Turner give in their article a simple way to compute the genus g(\Sigma_{\Gamma}) from the circle graph \Gamma. First, we number the n interior arcs of \Gamma, and we define the n \times n-matrix A(\Gamma) by saying that the entry (i,j) is equal to 1 if the i-th and j-th interior arcs intersect; otherwise, it is equal to 0. Notice that A(\Gamma) is symmetric and that any diagonal element is zero, so, working in \mathbb{Z}_2, it can be written in some basis as a diagonal block matrix (see for example Kaplansky’s book, Linear algebra and geometry):

A(\Gamma) = \left( \begin{array}{cccc} J & & & \\ & \ddots & & \\ & & J & \\ & & & 0 \end{array} \right) where J = \left( \begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array} \right).

In particular, notice that \mathrm{rank}(A(\Gamma)) is even. Let us define the genus of A(\Gamma) as

g(A(\Gamma))= \frac{1}{2} \mathrm{rank}_{\mathbb{Z}_2} (A(\Gamma)).

Finally, we have

Theorem 2: g(\Sigma_{\Gamma})= \gamma(A(\Gamma)).

Proof of theorem 1: We prove by induction on \gamma(w) that w can be written as a product of \gamma(w) commutators. If \gamma(w)=0, then w=1 and there is nothing to prove.

From now on, suppose that our result holds for \gamma(w) \leq n-1 and suppose \gamma(w)=n \geq 1. Let \Gamma be a circle graph such that \gamma(w)= g( \Sigma_{\Gamma}). First, we replace w by a word w' such that each pair of linked letters in w are different in w'. For example,

ChangeLetters

Because n \geq 1, there exist two intersecting interior arcs; therefore, up to a cyclic permutation (that does not change a pairing), we may suppose that w' can be written as

w'= x_1Rx_2Sx_1^{-1} T x_2^{-1} U.

The pairing \Gamma clearly induces a pairing \Gamma' whose underlying circle graph is the same; in particular, g(\Sigma_{\Gamma})= g( \Sigma_{\Gamma'}). Now, we cut and paste \Sigma_{\Gamma'} in the following way:

ProofCircleGraph1

ProofCircleGraph2

From a purely algebraic viewpoint, we set c=Rx_2S and we write w'= x_1cx_1^{-1}TSc^{-1} RU. Up to a cyclic permutation, we have

w'= c^{-1}RUx_1cx_1^{-1}TS.

Then, we set d= x_1^{-1}U^{-1}R^{-1} and we write

w' = c^{-1}d^{-1}c d URTS= [c^{-1},d^{-1}] \cdot URTS.

Now, we want to apply our induction hypothesis to \tilde{w} = URTS. First, the pairing \Gamma' induces a pairing \Gamma'' for [c^{-1},d^{-1}] \cdot URTS just by adding some disjoint interior arcs (because the word is not reduced), but that does not change the surface \Sigma_{\Gamma'} (in the polygon, we just add consecutive identified edges), hence g(\Sigma_{\Gamma'})=g( \Sigma_{\Gamma''}). Then, the pairing \Gamma'' induces a pairing \tilde{\Gamma} for URTS; but the figure below justifies that we have the connected sum \Sigma_{\Gamma''} \simeq \mathbb{T}^2 \sharp \Sigma_{\tilde{\Gamma}}.

ProofCircleGraph3

Therefore,

\gamma(\tilde{w})= g( \Sigma_{\tilde{\Gamma}}) = g( \Sigma_{\Gamma''})-1 = g( \Sigma_{\Gamma'})-1 = g( \Sigma_{\Gamma})-1=n-1.

Using our induction hypothesis, \tilde{w} can be written as a product of n-1 commutators, so w can be written as a product of n commutators.

Conversely, we prove that if w is a product of n commutators then there exists a pairing \Gamma satisfying g(\Sigma_{\Gamma})=n. We consider the case n=3, but the argument is completely general. So

w = [a_1,a_2] \cdot [a_3,a_4] \cdot [a_5,a_6].

We use the pairing \Gamma:

CircleGraph

The associated matrix is A( \Gamma) = \left( \begin{array}{ccc} J & & 0 \\ & J & \\ 0 & & J \end{array} \right) where J = \left( \begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array} \right), hence

g(\Sigma_{\Gamma}) = \frac{1}{2} \mathrm{rank}_{\mathbb{Z}_2}(A(\Gamma)) = 3. \square

Corollary: Let w \in \mathbb{F}_n be a reduced word of length m in the commutator subgroup. Then w can be written as a product of at most m/4 commutators.

Proof. Let \Gamma be a pairing of minimal genus, so that w can be written as a product of \frac{1}{2} \mathrm{rank}_{\mathbb{Z}_2}(A(\Gamma)) commutators. The circle graph \Gamma has m/2 interior arcs (of course, m is even) and A(\Gamma) is a \frac{m}{2} \times \frac{m}{2}-matrix, hence

\gamma(w) = \frac{1}{2} \mathrm{rank}_{\mathbb{Z}_2}(A(\Gamma)) \leq \frac{1}{2} \cdot \frac{m}{2}= \frac{m}{4}. \square

Notice that the proof of Theorem 1 is effective, that is it gives an algorithm to express a word as product with a minimal number of commutators. Let us apply this algorithm to the word w = x^2yx^{-1}y^{-2}x^{-1}y.

Step 1: Draw all the possible pairings.

ExampleCircleGraph

Step 2: Compute the ranks of the associated matrices.

MatricesCircleGraphWe have \gamma(A_1)=\gamma(A_2)=\gamma(A_3)=2 and \gamma(A_4)=1. So we are interesting in the fourth pairing.

Step 3: Cut and paste the surface of minimal genus.

CutPaste

Up to a cyclic permutation, w is therefore

cx^{-1}y^{-1}c^{-1}yx= [c, (yx)^{-1}]= [xy,x^{-1}y^{-1}]= xyx^{-1}y^{-2}x^{-1}yx.

Finally,

w=x[xy,x^{-1}y^{-1}]x^{-1} = [x^2yx^{-1}, y^{-1}x^{-1}].

 Notice that this decomposition is not unique, since we also have

w= [xy,y^{-1}xy^2].

Even more surprisingly, Stallings and Gersten noticed that such ideas may be applied in order to prove the fundamental theorem of algebra, following an intuition of Gauss! See their article On Gauss’s first proof of the fundamental theorem of algabra.

How Stallings proved finitely generated groups are subgroup separable

In this note, we deal with a construction on finite graphs due to Stallings, exposed in his article Topology of finite graphs, admitting some exciting recent generalizations to some graphs of groups (see Henry Wilton’s articles Elementary free groups are subgroup separable and Hall’s theorem for limit groups) or cube complexes (see Haglund and Wise’s article A combination theorem for special cube complexes). A next note will be dedicated to Wise’s construction for Salvetti complexes, and more generally for special cube complexes, but our main result here is:

Main Theorem: Finitely generated groups are subgroup separable.

Definition: Let G be a group and H be a subgroup. We say that H is separable if, for every g \notin H, there exists a finite-index subgroup K containing H and such that g \notin K.

Moreover, if the trivial subgroup is separable, G is said residually finite or RF; if every subgroups of G are separable, G is said ERF (Extended Residually Finite); if every finitely-generated subgroups of G are separable, G is said subgroupe separable or LERF (Locally Extended Residually Finite).

Theses definitions have topological interpretations:

Definition: Let G be a group. Defining the set of finite-index subgroups as a fundamental system of neighborhoods of the identity element, we get the profinite topology. Clearly, endowed with its profinite topology, G is a topological group. Moreover, a morphism between two groups endowed with their profinite topologies is automatically continuous.

Nota Bene: Because a finite-index subgroup H always contains a normal finite-index subgroup (namely \bigcap\limits_{g \in G} gHg^{-1}), finite-index subgroups in the definitions of profinite topology and separable subgroup may be supposed normal.

Lemma: Let G be a group and H be a subgroup. Then H is separable if and only if it is closed for the profinite topology.

Proof. Suppose that H is separable and let g \notin H. By hypothesis, there exists a finite-index subgroup K containing H but not containing g. Then gK is an open set disjoint from H: if there exists x \in H \cap gK, then there exists k \in K such that x=gk, hence g=xk^{-1} \in K, a contradiction. Therefore, H is closed.

Conversely, suppose that H is closed and let g \notin H. By hypothesis, there exists an open subset, say pK for some normal finite-index subgroup G and p \in G, containing g and disjoint from H. Because we chose K normal, HK is a subgroup of G; clearly, it contains H and it is a finite-index subgroup of G. Furthermore, it does not contain g: indeed, g \in HK implies pK \cap HK \neq \emptyset, hence pK \cap H \neq \emptyset, a contradiction. Therefore, H is separable. \square

Corollary: A group is residually finite if and only if its profinite topology is Hausdorff.

Genarally, it is not easy to prove that a given subgroup is separable. A useful tool for that is:

Definition: Let G be a group and H be a subgroup. We say that H is a retract if there exists a morphism (a retraction) r : G \to H such that r_{|H}= \mathrm{Id}_H. We say that H is a virtual retract if it is a retract in some finite-index subgroup of G.

Lemma: Let G be a residually finite group and H be a subgroup. If H is a virtual retract then it is separable.

Sketch of proof. It is sufficient to notice that the image of a (topological) retraction in a Hausdorff topological space is closed. So let X be a Hausdorff space and r : X \to Y \subset X be a retraction. Here, we only work with finitely-generated groups so that profinite topologies are second-countable, therefore it is sufficient to show that Y is sequentially closed; for the more general case, the same argument works with ultrafilters.

Let (x_n) \subset Y be a sequence converging to some \in X. Then, (r(x_n))=(x_n)_n converges to r(x). Because X is Hausdorff, we deduce that x=r(x) \in Y. Therefore, Y is sequentially closed. \square

The construction introduced by Stallings, is the following (recall that an immersion is a locally injective simplicial map):

Theorem: Let B be a finite bouquet of circles, X be a finite graph and X \to B be an immersion. Just by adding edges to X, it is possible to construct a covering C(X,B) \to B and a retraction r : C(X,B) \to X. Moreover, we get a commutative diagram:

Diagram

We say that C(X,B) is the canonical completion and r the canonical retraction.

Now, let us see  how to conclude thanks to Stallings’ construction:

Proof of the main theorem: Let F be a finitely generated free groups. We first prove that F is residually finite in order to apply the previous lemma.

Let B be a bouquet of circles satisfying \pi_1(B) \simeq F; let \widehat{B} denote its universal covering. Now, thinking of g \in F \backslash \{1 \} as a non trivial loop in B, let X \subset \widehat{B} be a finite subgraph containing a lift of g. Then, the fundamental group of the canonical completion C(X,B) is a finite-index subgroup of \pi_1(B) \simeq F not containing g. We just proved that F is residually finite.

Now let H be a finitely generated subgroup of F. Because F is residually finite, it is sufficient to prove that H is a virtual retract to conclude that H is separable.

Again, let us see F as the fundamental group of a bouquet of circles B and let Y \to B denote the covering associated to the subgroup H. If T \subset Y is a maximal subtree, because H is finitely generated, Y \backslash T has only finitely many edges; let X \subset Y be a ball containing all theses edges. Then the canonical retraction r: C(X,B) \to X gives a retraction

r_* : K:= \pi_1(C(X,B)) \to H \simeq \pi_1(X)

so that H be a retract in K, and therefore a virtual rectract in F. \square

During the proof above, the construction of an immersion X \to B with \pi_1(X) \simeq H can be made directly. For example, if F = \langle a,b \mid \ \rangle and H = \langle ab^{-2}a^{-1}, abab^2 \rangle:

Figure1

Notice that the main theorem cannot be extended to the separability of all subgroups, ie. every non-abelian (finitely-generated) free group is not ERF: Suppose by contradiction that there exists an ERF non-abelian free group. Because any quotient of an ERF group is RF, we deduce that any two-generator group is RF, and a fortiori Hopfian. However, we already proved in a previous note that the Baumslag-Solitar group BS(1,2) is not Hopfian.

We now turn on the proof of Stallings’ construction. The figure below illustrates an example; the reader is encouraged to keep in mind this particular case in order to visualize how the argument is simple.

Proof of Stallings’ construction: Because X \to B is an immersion, for any vertex v \in V and any label x_i, there is at most one edge labelled x_i starting from v or ending at v. We want to add edges to X so that exactly one edge of any label start from and end at any vertex; such a graph will be a covering of B.

Step 1: Let e \in X be an edge labelled x_i and let p = (e_0, \dots, e_r) denote the path of oriented edges labelled x_i containing e of maximal length (such a path is uniquely defined). Two cases happens: either p is a loop, and there is nothing to do, or p is not a loop, and we add an edge labelled x_i between the extremities of p.

Doing the same thing for every edges of X and for every label, we get a graph X' satisfying: for any vertex v \in X' and any label x_i, either there is no edge labelled x_i adjacent to x_i, or there are two such edges, one starting from v and the other ending at v.

Step 2: Let v \in X be a vertex and x_i a label. If there is no edge labelled x_i adjacent to v, then add a loop labelled x_i based at v. Keep going for every every vertex and for every label.

Let C(X,B) denote our new graph. It is a covering C(X,B) \to B extending by construction the immersion X \to B, so we have the commutative diagram.

To conclude the proof, let us define a retraction r : C(X,B) \to X. Of course, we only have to define r(e), where e is an edge added to X. Two cases happen: either e is a loop based at a vertex v \in X, and we define r(e)=v, or e completes a path p\subset X to a loop, and we send e on p (first choose a subdivision of e) so that r(e)=p. \square

Nota Bene: In general, the retraction defined above is not simplicial.

See also Graphs and Free Groups.

Follow

Get every new post delivered to your Inbox.