Van Kampen diagrams: an application to tiling problems

In this note, we are interested in the following problem: given a chessboard and a set of dominoes, is it possible to tile our chessboard using the dominoes we have? For example, let C(m,n) be the following chessboard

C(m,n)

and let D_2 denote the set of the “true” dominoes of size 2, that is

D_2

Is it possible to tile C(m,n) using only D_2? Surprisingly, this problem can be solved thanks to the van Kampen diagrams used in group theory.

Let \Pi = \langle g_1,\ldots, g_n \mid r_1= \cdots = r_m=1 \rangle be a group presentation. A van Kampen diagram \Gamma \subset \mathbb{R}^2, relative to \Pi, is a finite connected planar graph whose edges are oriented and labelled by the generators g_1, \ldots, g_n, such that the word labelling the boundary of any cell of \Gamma (ie., any bounded component of \mathbb{R}^2 \backslash \Gamma) is a relator r_1, \ldots, r_m. For convenience, we call the word labelling the boundary of the unbounded component of \mathbb{R}^2 \backslash \Gamma the boundary word of \Gamma.

For example, if we consider the presentation \Pi = \langle x,y \mid x^2=y^2, \ y=xyx \rangle, the following graph defines a van Kampen diagram (relative to \Pi) whose boundary word is x^4.

vanKampen

Theorem 1: Let G be a group with a presentation \Pi = \langle \Sigma \mid \mathcal{R} \rangle. A given word w written over \Sigma is equal to 1 in G if and only there exists a van Kampen diagram \Gamma, relative to \Pi, whose boundary word is w.

Proof. Suppose that there exists a van Kampen diagram \Gamma whose boundary word is w. We easily prove that w=1 in G by induction on the number of cells of \Gamma. If \Gamma has just one cell, then its boundary word is a relator of \Pi by definition, so that that w=1 trivially. If \Gamma has at least two cells, then we can write w=uv where u corresponds to the intersection between the boundary path of \Gamma and the boundary of one of its cells c. Let uz=1 be the relator associated to c. Removing c to \Gamma, we obtain a new van Kampen diagram whose boundary word is z^{-1}v. By our induction hypothesis, we conclude that

w=uv=z^{-1}v=1

in our group G.

Conversely, suppose that w=1 in G. Thus, as an element of the free group F(\Sigma), the word w belongs to the normal subgroup generated by \mathcal{R}, so we can write

w = g_1r_1^{\pm 1} g_1^{-1} \cdot g_2r_2^{\pm 1} g_2^{-1} \cdots g_k r_k^{\pm 1} g_k^{-1}

for some r_j \in \mathcal{R} and g_j \in F(\Sigma). Now consider the following van Kampen diagram:

vanKampen - proof

Clearly, it defines a van Kampen diagram whose boundary word is w. \square

Now, we associate a group presentation to any set of dominoes D. Let x,y be two fixed letters. To any dominoe d \in D, we define a word w(d) written over \{ x^{\pm 1}, y^{\pm 1} \} following the rule illustrated by

Rule

Let \Pi(D) denote the group presentation \langle x,y \mid w(d)=1, d \in D \rangle and G(D) the underlying group. For example,

\Pi(D_2)= \langle x,y \mid [x,y^2]=[y,x^2]=1 \rangle

with the notation [a,b]=aba^{-1}b^{-1}. Now, we can notice that a tiling of some chessboard using D produces a van Kampen diagram relative to \Pi(D). For example, the tiling

C(5,2) - Tiling

of C(5,2) using D_2 produces the van Kampen diagram

C(5,2) - vanKampen

Thus, if we defined the boundary word of a chessboard as the word obtained by following the same rule as the one used for the dominoes, we deduce from Theorem 1:

Theorem 2: If a chessboard can be tiled by a set of dominoes D, then its boundary word is equal to 1 in the group G(D).

As a concrete application, we are now able to solve our initial problem:

Theorem 3: C(m,n) can be tiled by D_2 if and only if m and n don’t have the same parity.

Proof. As we already noticed,

\Pi(D_2)= \langle x,y \mid [x,y^2]=[x^2,y]=1 \rangle.

The boundary path of C(m,n) is

w(m,n) = y^{n-1}xyx^{m-1}y^{-n+1}x^{-1}y^{-1}x^{-m+1}.

Notice that x^2 and y^2 belongs to the center of G(D_2). Thus, if m and n are both odd,

w(m,n)= xyx^{-1}y^{-1}=[x,y],

and if they are both even,

w(m,n)=y^{-1}xyx^{-1}yx^{-1}y^{-1}x=[y^{-1},x][y,x^{-1}].

Now we want to prove that [x,y] \neq 1 and [y^{-1},x][y,x^{-1}] \neq 1 in G(D_2). For this purpose, let us consider the morphism

\varphi : G(D_2) \twoheadrightarrow \langle x,y \mid x^2=y^2=1 \rangle

onto the infinite dihedral group D_{\infty}. It is clear that [x,y] \neq 1 and

[y^{-1},x][y,x^{-1}]=(yx)^4 \neq 1

in D_{\infty}. Therefore, these words are not equal to 1 in G(D_2) as well. According to Theorem 2, we conclude that C(m,n) cannot be tiled by D_2 if m and n have the same parity.

Conversely, suppose without loss of generality that m is even and n odd. Now, the particular tiling

C(6,5)

clearly yields a tiling of C(m,n) by D_2. \square

In fact, Theorem 3 can be deduced from the following tricky argument: First, it is obvious that if C(m,n) can be tiled by D_2 then C(m,n) must have an odd number of squares. Thus, if m and n are both odd, C(m,n) cannot be tiled by D_2. Secondly, if we color the squares of C(m,n) in black and white exactly as a true chessboard and if m,n are both even, then C(m,n) is obtained from a m \times n chessboard by removing two squares of the same color, say two black squares. But, if we color the dominoes of D_2 so that they contain a square of each color, we deduce that, if C(m,n) could be tiled by D_2, it would contain the same number of black and white squares. Therefore, we conclude that C(m,n) cannot be tiled by D_2 if m and n are both even.

In the same way, if we denote by K(m,n) the chessboard

K(m,n)

then we can prove:

Theorem 4: K(m,n) can be tiled by D_2 if and only if m or n is odd.

However, the argument using van Kampen diagrams can be adapted successfully to other tiling problems, where our previous trick does not work any more. Let D_3 denote the following set of dominoes:

D_3

Then, the associated group presentation is

\Pi (D_3) = \langle x,y \mid [x,y^3]=[x^3,y]=1 \rangle.

Following the proof of Theorem 3, we get:

Theorem 5: K(m,n) can be tiled by D_3 if and only if m=n=2 \ \text{mod} \ 3.

The proof is left as an exercice.

This point of view was introduced by Conway and Lagarias, in their article Tiling with polyominoes and combinatorial group theory, and was also exploited by Thurston in Conway’s tiling groups. See also Hitchman’s article, The topology of tile invariants, and references therein for more information.

 

Not all finitely-presented groups are fundamental groups of closed 3-manifolds

In our previous note Amalgamated products and HNN extensions (IV): Markov properties, we saw that for every n \geq 4 and for every finitely-presented group G, there exists a n-dimensional closed manifold whose fundamental group is G. However, such a result does not hold for n\leq 3; for the case n=2, see for example the note On subgroups of surface groups. The present note is devoted to the 3-dimensional case n=3.

In particular, we will prove that the groups \mathbb{Z}^n for n \geq 4, \mathbb{F}_m \times \mathbb{F}_n for m \geq 3, \ n \geq 2, and \mathbb{F}_m \times \mathbb{Z}^n for n ,m \geq 2 are not 3-manifold groups.

Definitions: A handlebody of genus g is an orientable 3-manifold (with boundary) obtained by attaching g “handles” to a 3-ball. Roughly speaking, it is a full closed surface of genus g.

A way to construct 3-manifolds (without boundary) is to glue two handlebodies H_1 and H_2 of some genus g along their boundaries by a homeomorphism h : \partial H_1 \to \partial H_2. We say that the triple (H_1,H_2,h) is a Heegaard splitting of genus g of the resulting manifold.

Theorem 1: Every closed 3-manifold admits a Heegaard splitting.

Sketch of proof. Let M be a closed 3-manifold, which will be thought of as a three-dimensional simplicial complex. Let M_1 denote a small neighborhood of the 1-skeleton \Gamma_1 of M and M_2 = M \backslash M_1 its complement. If \Delta is a 3-simplex, then M_1 \cap \Delta and M_2 \cap \Delta are illustrated by the following picture:

Heegaard Diagram

Notice that, if \Gamma_2 \subset M is the graph whose vertices are the centers of the 3-simplices of M and whose edges link two vertices corresponding to adjacent 3-simplices, then M_2 may be thought of as a neighborhood of \Gamma_2.

For i=1,2, let T_i denote a maximal subtree of \Gamma_i. Then, M_i may be thought of as a neighborhood of T_i, which is homeomorphic to a 3-ball, with one handle for each edge of the complement \Gamma_i \backslash T_i. Therefore, M_i is a handlebody of genus 1- \chi(\Gamma_i), since, if v( \cdot) and e(\cdot) denotes respectively the number of vertices and edges of a graph,

\chi( \Gamma_i)= v(\Gamma_i)- e(\Gamma_i)

and

1= \chi(T_i)=v(T_i)-e(T_i)=v(\Gamma_i)-e(T_i)

imply that

e(\Gamma_i) - e(T_i) = 1- \chi(\Gamma_i).

Therefore, we have proved that M is the union of two handlebodies which intersect along their boundaries. To conclude, we need to argue that M_1 and M_2 have the same genus, or equivalently, that \chi(\Gamma_1)= \chi (\Gamma_2).

Let v(M), \ e(M), \ f(M), \ c(M) denote respectively the number of vertices, edges, faces and 3-cells of M. By construction,

\chi (\Gamma_1)= v( \Gamma_1)- e(\Gamma_1) = v( M) - e(M)

and

\chi( \Gamma_2)= v( \Gamma_2) - e( \Gamma_2) = c(M) - f(M).

However, by Poincaré’s duality, \chi(M)=0, hence

\chi ( \Gamma_1) - \chi( \Gamma_2)= v(M)-e(M) + f(M)- c(M) = \chi (M)=0.

The proof is complete. \square

From a Heegaard splitting (H_1,H_2,h) of genus g, it is possible to find a presentation of the fundamental group of the associated 3-manifold M:

We apply van Kampen’s theorem to the decomposition M = H_1 \cup H_2. The handlebodies H_1 and H_2 have a free group of rank g as fundamental groups, and they meet in M along a closed surface \Sigma of genus g. Let \{ c_1, \ldots, c_{2g} \} be a generating set of \pi_1(\Sigma) \leq \pi_1(H_1). Then,

\pi_1(M)= \langle a_1,\ldots, a_g, b_1, \ldots, b_g \mid h_*(c_i)=c_i, \ 1 \leq i \leq 2g \rangle,

where \{ a_1, \ldots, a_g \} (resp. \{ b_1, \ldots, b_g \}) is a generating set of \pi_1(H_1) (resp. \pi_1(H_2)).

It is worth noting that such a presentation has the same number of generators and relations; we say that the presentation is balanced. Therefore, we have proved:

Corollary 2: Every 3-manifold group admits a balanced presentation.

So, a natural question is: which groups admit a balanced presentation? In fact, this question is linked to (co)homology of groups, which we define now.

A space X is aspherical whenever \pi_n(X)= 0 for all n \geq 2; according to Whitehead’s theorem, it amounts to require the universal covering \tilde{X} to be contractible. An interesting property of such spaces is that they are uniquely determined, up to homotopy, by their fundamental groups, that is to say, two aspherical spaces are homotopy equivalent if and only if their fundamental groups are isomorphic. Given a group G, a K(G,1) space or a classifying space for G is an aspherical space whose fundamental group is isomorphic to G; according to our previous remark, such a space is uniquely determined by G, up to homotopy. In particular, this allows us to define the n-th (co)homology group of G as the n-th (co)homology group of such a classifying space.

In order to justify that (co)homology groups are always defined, we need to prove that every group G has a classifying space. First, to a given presentation \langle X \mid \mathcal{R} \rangle of G we associate a two-dimensional CW-complex Y as follow: Define Y^{(1)} as a bouquet of | X | circles, each labelled by a generator of X. Then, for every relation w \in \mathcal{R}, glue a 2-cell along the path labelling by w. Using van Kampen’s theorem, it is not difficult to notice that the fundamental group of our complex Y is isomorphic to G. However, it may not be aspherical. Now, let us define an increasing sequence of CW-complexes Y= Y_1 \subset Y_2 \subset \cdots such that \pi_1(Y_n) \simeq G and \pi_k(Y_n)= \{ 1 \} for all k \leq n (such a sequence will define a Postnikov tower). The spaces (Y_{n}) are defined inductively in the following way: Let (\varphi_{\alpha} : \mathbb{S}^n \to Y_{n-1}) be a generating set for \pi_n(Y_{n-1}); then, define Y_n by gluing n-cells to Y_{n-1} using the \varphi_{\alpha}. By construction, \pi_n(Y_n) = \{1 \}, and we claim that the embedding Y_{n-1} \hookrightarrow Y_n is \pi_i-injective for all i< n by cellular approximation. Finally, let Y_{\infty}= \bigcup\limits_{n \geq 1} Y_n. By construction, Y_{\infty} is aspherical, and because Y_{\infty} have been constructed just by gluing n-cells to Y with n \geq 3, we deduce that \pi_1(Y_{\infty}) \simeq \pi_1(Y) \simeq G (since the fundamental group depends only on the 2-skeleton of a CW-complex). Therefore, Y_{\infty} is a classifying space of G.

For more information on Postnikov towers, see section 4.3 of Hatcher’s book, Algebraic Topology.

Now, we are ready to linked the deficiency of a presentation, that is the number of its generators minus the number of its relations, with the first and second homology groups of the underlying group. The result below is mentioned by Brown in the fifth exercice of chapter II.5 of his book Cohomology of groups. Here is the topological approach he suggests:

Theorem 3: Let \langle X \mid R \rangle be a presentation of a group G with |X|=n and |R|=m. Let also r denote \mathrm{rk}_{\mathbb{Z}} G^{ab}. Then \mathrm{rk}_{\mathbb{Z}} H_2(G) \leq r-n+m.

Proof. Let Y be the CW-complex associated to the given presentation. According to what we have said above, we may add n-cells to Y, with n \geq 3, in order to “kill” higher homotopy groups, ie., our new CW-complex Y_{\infty} is aspherical. Moreover, because we did not modify the 2-squeleton of Y, \pi_1(Y) is isomorphic to \pi_1( Y_{\infty}). Therefore, Y_{\infty} is a K(G,1), hence H_{\ast}(Y_{\infty}) \simeq H_{\ast} (G).

Notice that 1-n+m = \chi(Y)= 1- \mathrm{rk}_{\mathbb{Z}} H_1(Y) + \mathrm{rk}_{\mathbb{Z}} H_2(Y), hence

\mathrm{rk}_{\mathbb{Z}} H_2(Y)=r-n+m.

On the other hand, we clearly have an epimorphism H_2(Y) \twoheadrightarrow H_2(Y_{\infty}), therefore:

\mathrm{rk}_{\mathbb{Z}} H_2(G)= \mathrm{rk}_{\mathbb{Z}} H_2( Y_{\infty}) \leq \mathrm{rk}_{\mathbb{Z}} H_2(Y)=r-n+m. \square

Corollary 4: If a group G admits a balanced presentation, then \mathrm{rk}_{\mathbb{Z}} H_2(G) \leq \mathrm{rk}_{\mathbb{Z}} G^{ab}.

Thus, now we have a necessary criterion to determine whether or not a group admits a balanced presentation. The Proposition below applies this criterion to the right-angled Artin groups (we defined them in our previous note Some SQ-universal groups).

Proposition 5: A right-angled Artin group A(\Gamma) admits a balanced presentation if and only if \Gamma has more vertices than edges.

Sketch of proof. To the canonical presentation of A(\Gamma) is associated a cube complex Y, called Salvetti complex: Y has only one point, one edge for each generator of A(\Gamma), and n+1 generators span an n-cube if and only if they pairwise commute. Now, it can be proved that the Salvetti complex is nonpositively curved so that its universal cover is CAT(0); because a CAT(0) space is contractible, we deduce that Y is a classifying space of A(\Gamma). Moreover, it is not difficult to prove that the n-th homology group of Y is free on the set of n-cubes. Therefore, \mathrm{rk}_{\mathbb{Z}} H_1(A(\Gamma)) corresponds to the number of vertices of \Gamma, and \mathrm{rk}_{\mathbb{Z}} H_2(A(\Gamma)) to its number of edges.

Thus, if A(\Gamma) admits a balanced presentation, according to Theorem 3, \Gamma must have more vertices than edges. The converse is obvious. \square

For more information on CAT(0) geometry, see Bridson and Haefliger’s book, Metric spaces of nonpositive curvature.

Now, we are ready to prove that the groups mentionned at the beginning of this note do not admit a balanced presentation, and thus are not the fundamental groups of closed 3-manifolds.

Corollary 6: Let n \geq 1. Then \mathbb{Z}^n admits a balanced presentation if and only if n \leq 3.

Proof. \mathbb{Z}^n is the right-angled Artin group associated to the complete graph K_n. Because K_n has n vertices and (n-1)! edges, it is sufficient to apply Proposition 5 to conclude. \square

Corollary 7: Let m,n \geq 1. Then \mathbb{F}_n \times \mathbb{F}_m admits a balanced presentation if and only if m \leq 2 and n=1 or m=1 and n \leq 2.

Proof. \mathbb{F}_n \times \mathbb{F}_m is the right-angled Artin group associated to the bipartite complete graph K_{m,n}. Because K_{m,n} has m+n vertices and mn edges, it is sufficient to apply Proposition 5 to conclude. \square

Corollary 8: Let m,n \geq 1. Then \mathbb{F}_m \times \mathbb{Z}^n admits a balanced presentation if and only if m=1 and n \leq 2 or n \geq 2 and m \geq 2.

Proof. Let D_m denote the graph with m vertices and no edges. Then \mathbb{F}_m \times \mathbb{Z}^n is the right-angled Artin group associated to the join K_n \ast D_m. Because D_n \ast D_m has n+m vertices and mn+ (n-1)! edges (here, we suppose 0!=0), it is sufficient to apply Proposition 5 to conclude. \square

An elementary application of ping-pong lemma

Let us denote by \mathrm{SL}(2,\mathbb{Z}) the set of (2 \times 2)-matrices whose determinant is 1, and by \mathrm{PSL}(2,\mathbb{Z}) the quotient \mathrm{SL}(2,\mathbb{Z}) / \{ \pm \mathrm{Id} \}. Our aim here is to prove that \mathrm{PSL}(2,\mathbb{Z}) is a free product:

Theorem: \mathrm{PSL}(2,\mathbb{Z}) \simeq \mathbb{Z}_2 \ast \mathbb{Z}_3.

As noticed in the previous note Some SQ-universal groups, as a corollary we get that \mathrm{SL}(2,\mathbb{Z}) is SQ-universal, that is every countable group is embeddable into a quotient of \mathrm{SL}(2, \mathbb{Z}).

Usually, the theorem above is proved thanks to a natural action of \mathrm{PSL}(2,\mathbb{Z}) on the hyperbolic plane by Möbius transformations. However, as noticed by Roger Alperin in his article published in The American Mathematical Monthly, it is sufficient to make \mathrm{PSL}(2,\mathbb{Z}) act on the set of irrational numbers via:

\displaystyle \left( \begin{matrix} a & b \\ c & d \end{matrix} \right) \cdot r = \frac{a r + b }{ c r + d}.

Notice that cr+d \neq 0 for all c,d \in \mathbb{Z} precisely because r is irrational. The argument below may be thought of as an application of ping-pong lemma (that we already met in the note Free groups acting on the circle in order to find free subgroups).

First, it is a classical exercice to prove that \mathrm{SL}(2,\mathbb{Z}) is generated by the two following matrices:

A= \left( \begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix} \right)  and  B= \left( \begin{matrix} 0 & -1 \\ 1 & 0 \end{matrix} \right).

For convenience, let C= AB. Then B and C also generate \mathrm{SL}(2, \mathbb{Z}), and consequently their images in \mathrm{PSL}(2,\mathbb{Z}) generate it; furthermore, B (resp. C) has order two (resp. order three) in \mathrm{PSL}(2, \mathbb{Z}). Notice that

\displaystyle B=B^{-1} : z \mapsto - \frac{1}{z},    \displaystyle C : z \mapsto 1- \frac{1}{z}    and    \displaystyle C^{-1} : z \mapsto \frac{1}{1-z}.

Now, let \mathcal{P} and \mathcal{N} denote the set of positive and negative irrationals respectively. Clearly,

B( \mathcal{P} ) \subset \mathcal{N}  and  C^{ \pm 1} ( \mathcal{N} ) \subset \mathcal{P}.

To conclude, we want to prove that, for any alternating word w from \langle B \rangle and \langle C \rangle, w \neq 1 in \mathrm{PSL}(2,\mathbb{Z}).

Case 1: w has odd length. Then either w begins and ends with a B, hence w( \mathcal{P} ) \subset \mathcal{N}, or w begins and ends with a C^{\pm 1}, hence w( \mathcal{N} ) \subset \mathcal{P}. In particular, we deduce that w \neq 1 in \mathrm{PSL} (2, \mathbb{Z}).

Case 2: w has even length. Without loss of generality, we may suppose that w begins with a C^{\pm 1}; otherwise, just conjugate w by B. Then either w begins with a C and ends with a B, hence

w( \mathcal{P} ) \subset C(\mathcal{N}) \subset \{ r \ \text{irrationals} \mid r> 1 \},

or w begins with a C^{-1} and ends with a B, hence

w( \mathcal{P} ) \subset C^{-1} ( \mathcal{N} ) \subset \{ r \ \text{irrationals} \mid r< 1 \}.

In either case, we deduce that w(1) \neq 1, so w \neq 1 in \mathrm{PSL}(2, \mathbb{Z}). The proof is complete.

Some SQ-universal groups

A group G is said SQ-universal whenever every countable group can be embedded into a quotient of G. In some sense, SQ-universality is a “largeness property”. Motivating by this idea, we prove the two following properties:

Property 1: A SQ-universal group contain a non-abelian free group (of countable rank).

Proof. Let G be a SQ-universal group. In particular, there exists a quotient \overline{G} containing a free group of infinite rank \langle \overline{x_1}, \overline{x_2}, \ldots \rangle. Let x_i be a lift of \overline{ x_i } in G. If there existed a non-trivial relation between the x_i‘s then the same relation would hold between the \overline{x_i}‘s in \overline{G}. Therefore, \langle x_1,x_2 , \ldots \rangle is a free subgroup of infinite rank in G. \square

Property 2: A countable SQ-universal group contains uncountably many normal subgroups.

Proof. Let G be a countable SQ-universal group. Every quotient of G contains only countably many two-generated subgroups. However, we know that there exist uncountably many two-generated groups up to isomorphism: see for instance the notes Amalgamated products and HNN extensions (I): A theorem of B.H. Neumann or Cantor-Bendixson rank in group theory: A theorem of B.H. Neumann. Therefore, G must have uncountably many quotients, and a fortiori uncountably many normal subgroups. \square

Although SQ-universality seems to be a very strong property, many groups turn out to be SQ-universal. We already saw in previous notes that the free group of rank two \mathbb{F}_2 is SQ-universal; in fact, we gave two proofs, the one in Amalgamated products and HNN extensions (I): A theorem of B.H. Neumann, and the other, completely elementary, in A free group contains a free group of any rank. Other examples come from the following trivial observation: a group with a SQ-universal quotient is itself SQ-universal. Therefore, any group with a non-abelian free quotient is SQ-universal; in particular, we deduce that any non-abelian free group, of any rank, is SQ-universal. Together with the following result, we will be able to exhib a lot of other examples of SQ-universal groups.

Theorem 3: A group containing a SQ-universal subgroup of finite-index is itself SQ-universal.

For an (almost) elementary proof, see P. Neumann’s article, The SQ-universality of some finitely presented groups, J. Aust. Math. Soc. 16, 1 (1973) .

Example 1: Let \Sigma be a closed surface. Then either \pi_1(\Sigma) is SQ-universal or \Sigma is a sphere \mathbb{S}^2, a projective plane \mathbb{P}^2, a torus \mathbb{T}^2 or a Klein bottle \mathbb{K}.

Notice that we already dealt with surface groups in the previous note On subgroups of surface groups. In particular, we know that \pi_1(\mathbb{S}^2) \simeq \{ 1 \}, \pi_1(\mathbb{T}) \simeq \mathbb{Z}^2, \pi_1( \mathbb{P}^2) \simeq \mathbb{Z}_2 are not SQ-universal. We also know that \pi_1(\mathbb{K}) contains \pi_1(\mathbb{T}) \simeq \mathbb{Z}^2 as a subgroup of finite-index two, so it cannot be SQ-universel.

From now on, let \Sigma be a closed surface different from the surfaces mentioned above. If \Sigma is non-orientable, there exist a finite-cover \Sigma' \to \Sigma where \Sigma' is orientable; in particular, \pi_1(\Sigma') is a subgroup of finite-index in \pi_1(\Sigma), so, according to Theorem 3, we may suppose that \Sigma is orientable, that is

\pi_1(\Sigma)= \langle a_1, b_1, \ldots, a_g, b_g \mid [a_1,b_1] \cdots [a_g, b_g] = 1 \rangle

for some g \geq 2. Noticing that the following quotient is free,

\pi_1( \Sigma) / \langle \langle a_1 b_1^{-1}, \ldots, a_g b_g^{-1} \rangle \rangle = \langle a_1, \ldots, a_g \mid \ \rangle \simeq \mathbb{F}_g,

we deduce that \pi_1(\Sigma) is SQ-universal.

Example 2: A right-angled Artin groups is either free abelian or SQ-universal.

The right-angled Artin group associated to a finite simplicial graph \Gamma is defined by the presentation

A(\Gamma)= \langle v \in V ( \Gamma ) \mid [v_1,v_2] = 1, \ (v_1,v_2) \in E(\Gamma) \rangle,

where V ( \Gamma) and E(\Gamma) denote respectively the set of vertices and edges of \Gamma. In particular, if \Gamma is a complete graph with n vertices, then A(\Gamma) is the free abelian group \mathbb{Z}^n; if \Gamma is a graph with n vertices and no edges, then A(\Gamma) is the free group \mathbb{F}_n.

Figure

For another example, if \Gamma is the graph given above, then

A(\Gamma) = \langle a,b,c,d,e \mid [a,b]= [a,c] = [a,d] = [e,b]=[e,c]=[e,d]=1 \rangle

is isomorphic to \mathbb{F}_2 \times \mathbb{F}_3.

We claim that, if \Gamma is not a complete graph, then A(\Gamma) has a non-abelian free quotient, and in particular is a SQ-universal group.

Because \Gamma is not complete, there exist two vertices v_1,v_2 not linked by an edge. Let \Gamma_1 denote the subgraph induced by v_1 and its neighbors, and \Gamma_2 the subgraph induced by V(\Gamma) \backslash \{ v_1 \}. Then \Gamma_1 and \Gamma_2 are non-empty, since v_1 \in \Gamma_1 and v_2 \in \Gamma_2, they cover \Gamma, and \Gamma \backslash (\Gamma_1 \cap \Gamma_2) is not connected, because v_1 and v_2 are separated by \Gamma_1 \cap \Gamma_2. Now, quotienting A(\Gamma) by the subgroup

\langle \langle v \in V(\Gamma_1) \cap V(\Gamma_2), \ uv^{-1} \ (u,v \in V(\Gamma_1)), \ uv^{-1} \ (u,v \in V( \Gamma_2 ) ) \rangle \rangle,

we get the free group \langle a , b \mid \ \rangle. For an explicit example, let us consider the following graph:

Figure1

So, the associated right-angled Artin group is

\langle a, b , c, d \mid [a,b] = [a,c] = [b,c] = [b,d] = [c,e] = [d,e] = 1 \rangle.

Quotienting by the subgroup \langle \langle b,c, de^{-1} \rangle \rangle, we get the free group \langle a,d \mid \ \rangle.

Example 3: If A and B are two finite groups with |A| \geq 2 and |B| \geq 3, then the free product A \ast B is a SQ-universal group.

We proved in the previous note A free group contains a free group of any rank that

\{ [a , b ] \mid a \in A \backslash \{ 1 \}, b \in B \backslash \{ 1 \} \}

is a free basis of the derived subgroup D of A \ast B. Furthermore, the quotient (A \ast B) / D \simeq A \times B is finite, so that D is a non-abelian free subgroup of finite index in A \ast B. From Theorem 3, we deduce that A \ast B is SQ-universal.

For example, SL(2,\mathbb{Z}) is SQ-universal, because it has the SQ-universal group

PSL(2,\mathbb{Z}) \simeq \mathbb{Z}_2 \ast \mathbb{Z}_3

as a quotient. (See An elementary application of ping-pong lemma for an elementary proof of this fact.)

A theorem of Schur on commutator subgroup

The aim of this note is to prove the following theorem, due to Schur, and to exhibit some corollaries. The proof given here comes from J. Dixon’s book, Problems in Group Theory (problems 5.21 to 5.24).

Theorem: Let G be a group. If the center Z(G) is a finite-index subgroup of G, then the commutator subgroup D(G) is finite.

We begin with two easy lemmae. The first one is left to the reader as an exercice: it is just a computation. In the sequel, we use the notation [x,y] = x y x^{-1} y^{-1}.

Lemma 1: For all a,x,y \in G, a[x,y]a^{-1} = [axa^{-1},aya^{-1}].

Lemma 2: If Z(G) is a subgroup of finite index n, then [x,y]^{n+1} = [x,y^2] \cdot [yxy^{-1}, y ]^{n-1}.

Proof. Notice that, because Z(G) is a subgroup of finite index n, for all a \in G we have a^n \in Z(G). Therefore,

[x,y]^{n+1} = [x,y]^n \cdot xyx^{-1} y^{-1} = xyx^{-1} \cdot [x,y]^n \cdot y^{-1}.

Then,

[x,y]^{n+1} = xyx^{-1} \cdot [x,y] \cdot [x,y]^{n-1} \cdot y^{-1} = xy^2 x^{-1} y^{-2} \cdot y [x,y]^{n-1} y^{-1}.

Using Lemma 1, we conclude that

[x,y]^{n+1} = [x,y^2] \cdot \left( y[x,y]y^{-1} \right)^{n-1} = [x,y^2] \cdot [yxy^{-1},y]^{n-1}. \square

Proof of Theorem: Let us suppose that Z(G) is a subgroup of finite index n.

It is not difficult to notice that [x,y]=[a,b] in G whenever x=a and y=b in G/Z(G). Therefore, G has at most n^2 commutators.

Now, any c \in D(G) can be written as a product of commutators

c = c_1 \cdot c_2 \cdots c_r.

Suppose that r is as small as possible, and assume by contradiction that r>n^3. Therefore, because there exist at most n^2 commutators, the product contains some commutator, say k, at least (n+1) times. We claim that it is possible to write

c = k^{n+1} \cdot c_1' \cdots c_{r-n-1}' \ \ \ \ \ \ (1)

for some new commutators c_j'. For example, if c_i=k, notice that

c = c_1 \cdots c_{i-1} \cdot k \cdot c_{i+1} \cdots c_r = k \cdot (k^{-1}c_1k) \cdots (k^{-1}c_{i-1}k) \cdot c_{i+1} \cdots c_r.

Thanks to Lemma 1, we know that each k^{-1}c_jk is again a commutator. We just proved our claim for n=0. The general case follows by induction.

From (1) and Lemma 2, we deduce that c can be written as a product of r-1 commutators, a contradiction with the minimality of r.

Therefore, we just proved that any element of D(G) can be written as a product of at most n^3 commutators. Because there exist at most n^2 commutators, we deduce that the cardinality of D(G) is bounded above by n^{2n^3}; in particular, D(G) is finite. \square

Corollary 1: If G has only finitely many commutators, then D(G) is finite.

Proof. Let [g_1,g_2], \ldots, [g_{2r-1},g_{2r}] denote the commutators of G and H be the subgroup generated by the g_i‘s. Notice that D(G)=D(H), so it is sufficient to prove that D(H) is finite to conclude. Furthermore, according to our previous theorem, it is sufficient to prove that Z(H) is a finite-index subgroup of H.

If C(g_i) denotes the centralizer of g_i in H, notice that

Z(H)= \bigcap\limits_{i=1}^{2r} C(g_i).

Therefore, it is sufficient to prove that each C(g_i) is a finite-index subgroup of H. But H/C(g_i) is finite if and only if g_i has only finitely-many conjugacy classes. Because hg_ih^{-1}=[h,g_i] g_i for all h \in H, and because H has only finitely-many commutators, it is clear that g_i has finitely-many conjugacy classes, concluding our proof. \square

Corollary 2: The only infinite group all of whose non-trivial subgroups are finite-index is \mathbb{Z}.

Proof. Let G be such a group. Let g_0 \in G \backslash \{ 1 \} and g_1, \ldots, g_r \in G \backslash \{ 1 \} be a set of representatives of the cosets of \langle g_0 \rangle. For each 0 \leq i \leq r, \langle g_i \rangle is a finite-index subgroup of G by assumption; but it is also a subgroup of the centralizer C(g_i), so C(g_i) is a finite-index subgroup of G. Therefore, because \{ g_0, \ldots, g_r \} generates G, the center

Z(G)= \bigcap\limits_{i=0}^r C(g_i)

is a finite-index subgroup of G. According to our previous theorem, D(G) is finite, and by assumption, any subgroup of G is either trivial, or finite-index and in particular infinite since G so is. Therefore, D(G) is trivial, that is G is abelian.

From the classification of finitely-generated abelian groups, it is not difficult to prove that the only abelian group all of whose non-trivial subgroups are finite-index is \mathbb{Z}. \square

Notice however that there exist non-cyclic groups all of whose normal subgroups have finite-index: they are called just-infinite groups. The infinite dihedral group D_{\infty} is such an example.

Corollary 3: A torsion-free virtually infinite cyclic group is infinite cyclic.

Proof. Let G be a torsion-free group with an infinite cyclic subgroup H= \langle g_0 \rangle of finite index n. As above, if g_1, \ldots, g_r denotes a set of representatives of the cosets of \langle g_0 \rangle then \{ g_i \mid 0 \leq i \leq r \} generates G. Noticing that g_i^n \in H, we deduce that C(g_i) \cap H is of finite index in H, so the centralizer C(g_i) has a finite index in G. Again, we deduce that the center

Z(G)= \bigcap\limits_{i=0}^r C(g_i)

is a finite-index subgroup of G. According to our previous theorem, D(G) is finite, and in fact trivial because G is torsion-free, so G is abelian. From the classification of finitely-generated abelian groups, it is not difficult to prove that the only abelian torsion-free virtually cyclic group is \mathbb{Z}. \square

In fact, using Stallings theorem, it is possible to prove more generally that any torsion-free virtually free group turns out to be free.

A group G is abelian if and only if Z(G)=G if and only if D(G)= \{ 1 \}. Therefore, a way to say that G is almost abelian is to state that Z(G) is big (eg. is a finite-index subgroup) or that D(G) is small (eg. is finite). Essentially, our main theorem proves that the first idea implies the second. Although the converse does not hold in general, it holds for finitely-generated groups:

Theorem: Let G be a finitely-generated group. If D(G) is finite then Z(G) is a finite-index subgroup.

Proof. Let g_1, \ldots, g_r \in G be a finite generating set of G. Then

Z(G)= \bigcap\limits_{i=1}^r C(g_i).

To conclude, it is sufficient to prove that each C(g_i) is a finite-index subgroup, that is equivalent to say that each g_i has finitely-many conjugacy classes. Noticing that for all h \in G, hg_ih^{-1}=[h,g_i]g_i, we deduce the latter assertion because D(G) is finite. \square

Positive curvature versus negative curvature

A leitmotiv in geometric group theory is to make a group G act on a geometric space X in order to link algebraic properties of G with geometric properties of X. Here, the expression geometric space is intentionally vague: it goes from rather combinatorial objects, like simplicial trees, to rather geometric objects, like Riemannian manifolds. However, it is worth noticing that the link between G and X turns out to be stronger when X is non-positively curved in some sense. A possible definition of geodesic space of curvature bounded above is given by CAT(\kappa) inequality:

Definition: Let X be a geodesic space and \kappa \in \mathbb{R}. For convenience, let M_{\kappa} be the only (up to isometry) simply connected Riemannian surface of constant curvature \kappa and let D_{\kappa} denote its diameter; therefore, M_{\kappa} is just the hyperbolic plane M_{-1}, the euclidean plane M_0 or the sphere M_1 with a rescaling metric and D_{\kappa} is finite only if \kappa >0.

For any geodesic triangle \Delta=\Delta(x,y,z) – that is a union of three geodesics [x,y], [y,z] and [x,z] – of diameter at most 2 D_{\kappa}, there exists a comparison triangle \overline{\Delta}= \overline{\Delta}(\overline{x},\overline{y},\overline{z}) in M_{\kappa} (unique up to isometry) such that

d(\overline{x}, \overline{y})= d(x,y),  d(\overline{y}, \overline{z})= d(y,z)  and  d(\overline{x}, \overline{z})=d(x,z).

We say that \Delta satisfies CAT(\kappa) inequality if for every a,b \in \Delta

d(a,b) \leq d( \overline{a}, \overline{b}).

We say that X is a CAT(\kappa) space if every geodesic triangle of diameter at most 2 D_{\kappa} satisfies CAT(\kappa) inequality, and that X is of curvature at most \kappa if it is locally CAT(\kappa).

This definition of curvature bounded above is good enough to agree with sectional curvature of Riemannian manifolds: A Riemannian manifold is of curvature at most \kappa if and only if its sectional curvature is bounded above by \kappa. For more information, see Bridson and Haefliger’s book, Metric spaces of nonpositive curvature, theorem I.1.A6.

From now on, let us consider a nice kind of action on geodesic spaces:

Definition: A group acts geometrically on a metric space whenever the action is properly discontinuous and cocompact.

Such actions are fundamental in geometric group theory, notably because of Milnor-Svarc theorem: if a group G acts geometrically on a metric space X, then G is finitely-generated and there exists a quasi-isometry between G and X. See [BH, proposition I.8.19].

Let us say that a group is CAT(\kappa) if it acts geometrically on some CAT(\kappa) space. Notice that, if (X,d) is a CAT(\kappa) space, then (X, \sqrt{ | \kappa | } \cdot d ) is a CAT( \kappa / |\kappa|) space. Therefore, a CAT(\kappa) group is either CAT(-1) or CAT(0) or CAT(1).

According to the remark made at the beginning of this note, CAT(-1) and CAT(0) properties should give more information on our group than CAT(1) property. In fact, we are able to prove the following result:

Theorem: Any finitely-presented group is CAT(1).

Sketch of proof. Let G be a finitely-presented group. If X is a Cayley complex of G, it is know that the natural action G \curvearrowright X is geometric – see Lyndon and Schupp’s book, Combinatorial group theory, section III.4. Now, the barycentric subdivision X' of X is a flag complex of dimension two. According to Berestovskii’s theorem mentionned in [BH, theorem II.5.18], the right-angled spherical complex Y associated to X' is a (complete) CAT(1) space. Of course, the action G \curvearrowright Y is again geometric, since the underlying CW complex is just X'. \square

Another important way to link a group G with a geometric space is to write G as a fundamental group. As above, we can prove the following result:

Theorem: Any group G is the fundamental group of a CAT(1) space X. Moreover, if G is finitely-presented, X can be supposed compact.

Sketch of proof. Let X be the CW complex associated to a presentation of G; then G \simeq \pi_1(X) and X is compact if the presentation were finite – see Lyndon and Schupp’s book, Combinatorial group theory, section III.4. As above, the right-angled spherical complex Y associated to the barycentric subdivision X' of X is a CAT(1) space, and its fundamental group is again isomorphic to G, since the underlying CW complex is just X'. \square

On the other hand, many properties are known for CAT(0) groups; the usual reference on the subjet is Bridson and Haefliger’s book, Metric spaces of nonpositive curvature. Furthermore, is not difficult to prove that CAT(-1) groups are Gromov-hyperbolic. However, it is an open question to know whether or not hyperbolic groups are CAT(-1), or even CAT(0).

Let us conclude this note by noticing that, for a fixed CAT(1) space X, it is possible that only few groups are able to act on it. For example, we proved in our previous note Brouwer’s Topological Degree (IV): Jordan Curve Theorem that, for any even number n, \{1 \} and \mathbb{Z}_2 are the only groups acting freely by homeomorphisms on the n-dimensional sphere \mathbb{S}^n.

 

Cancellation property for groups I

A natural question in group theory is to know whether or not the following implication is true:

G \times H \simeq G \times K \Rightarrow H \simeq K.

Of course, such a cancellation property does not hold in general, for example

\mathbb{Z} \times \mathbb{Z} \times ( \mathbb{Z} \times \cdots) \simeq \mathbb{Z} \times \mathbb{Z} \times \cdots \simeq \mathbb{Z} \times ( \mathbb{Z} \times \cdots)

whereas \mathbb{Z} and \mathbb{Z} \times \mathbb{Z} are not isomorphic. However, cancellation property turns out to hold for some classes of groups. In his article On cancellation in groups, Hirshon proves that finite groups are cancellation groups, that is to say, for every groups G,H,K, if G \times H \simeq G \times K with G finite, then H \simeq K. Below, we present an elementary proof of a weaker statement due to Vipul Naik:

Theorem: Let G,H,K be three finite groups. If G \times H \simeq G \times K then H \times K.

Proof. For any finite groups L and G, let h(L,G) denote the number of homomorphisms from L to G and i(L,G) denote the number of monomorphisms from L to G. Notice that

\displaystyle h(L,G)= \sum\limits_{N \lhd L} i(L/N,G) \hspace{1cm} (1)

Let G,H,K be three finite groups such that G \times H \simeq G \times K. Then

\begin{array}{c} h(L,G \times H)=h(L,G \times K) \\ h(L,G) \cdot h(L,H)=h(L,G) \cdot h(L,K) \\ h(L,H)=h(L,K) \end{array}

for any finite group L, since h(L,G) \neq 0. Using (1), it is easy to deduce that i(L,H)=i(L,K) for any finite group L by induction on the cardinality of L. Hence

i(H,K)=i(H,H) \neq 0.

Therefore, there exists a monomorphism from H to K. From G \times H \simeq G \times K, we deduce that H and K have the same cardinality, so we conclude that H and K are in fact isomorphic. \square

Because a classification of finitely-generated abelian groups or of divisible groups is known, it is easy to verify that cancellation property holds also for such groups (the classification of divisible groups was mentionned in a previous note). However, in his book Infinite abelian groups, Kaplansky mentions that the problem is still open for the class of all abelian groups.

We conclude our note by an example where the cancellation property does not hold even if the groups are all finitely-presented.

Let \Pi be the following presentation

\langle a,b,c \mid [a,b] = [a,c] = 1, b^{11}, cbc^{-1}=b^4 \rangle.

Clearly, we have the following decomposition:

\Pi \simeq \langle a \mid \ \rangle \times \underset{:=H}{ \underbrace{ \langle b,c \mid b^{11}=1, cbc^{-1}=b^4 \rangle }}.

Now, we set x=a^2c^5 and y= ac^2. Because a commutes with b and c, we deduce that [x,y]=1. Then,

y^2=a^4c^4=xc^{-1} \Rightarrow c=y^{-2}x

and

x=a(ac^2)c^3=ayc^3 \Rightarrow a=y^5x^{-2}.

Now, let us notice that

c^5bc^{-5} = c^4(cbc^{-1})c^{-4} = c^4b^4c^{-4} = c^3 (cbc^{-1})^4c^{-4}= \cdots = b,

hence [x,b] = [a^2c^5,b]=c^5bc^{-5}b^{-1}=1. Therefore,

\Pi \simeq \langle b,x,y \mid [x,b]=[x,y]=[y^5,b]=1, b^{11}=1, y^{-2}by^2=b^4 \rangle.

Using y^{-2}by^2=b^4, it is not difficult to notice that the relation [y^5,b]=1 can be written as yby^{-1}=b^5. Then, we deduce that

y^2b^4y^{-2}= y(yby^{-1})^4y^{-1} = (yby^{-1})^{-2}=b

so that the relation y^{-2}by^2=b^4 can be removed from the presentation. Finally,

\Pi \simeq \langle b,x,y \mid [x,y]=[x,b]=1, b^{11}=1, yby^{-1}=b^5 \rangle.

Therefore, we find another decomposition of \Pi as a direct product:

\Pi \simeq \langle x \mid \ \rangle \times \underset{:=K}{\underbrace{ \langle b,y \mid b^{11}=1, yby^{-1}=b^5 \rangle }}.

So \mathbb{Z} \times H \simeq \Pi \simeq \mathbb{Z} \times K. To conclude, it is sufficient to prove that H and K are not isomorphic. Notice that they are both a semi-direct product \mathbb{Z}_{11} \rtimes \mathbb{Z}.

Let \varphi : H \to K be a morphism. It is not difficult to show that a torsion element of K has to be conjugated to b, so, without loss of generality, we may suppose that \varphi(b)= b^m for some 0 \leq m \leq 10. Then, \varphi(c)= b^ry^s for some r,s \in \mathbb{Z}. Let \pi : K \to \mathbb{Z} be the canonical projection sending b to 0 and y to 1. If \varphi is onto, then so is \pi \circ \varphi: because \pi \circ \varphi(b)=0 and \pi \circ \varphi(c)=s, we deduce that s= \pm 1. On the other hand,

b^{4m} = \varphi (b^4) = \varphi (cbc^{-1} ) = b^r y^{\pm 1} b^m y^{ \mp 1} b^{-r} = y^{ \pm 1} b^m y^{\mp 1},

hence b^{4m}= b^{5m} or b^{20m}=b^m. Therefore, 11 has to divide m and we deduce that \varphi(b)=b^m=1. We conclude that \varphi cannot be an isomorphism.

Finally, we proved that

\mathbb{Z} \times ( \mathbb{Z}_{11} \rtimes_{a} \mathbb{Z}) \simeq \mathbb{Z} \times ( \mathbb{Z}_{11} \rtimes_b \mathbb{Z}),

where a : n \mapsto 4n and b : n \mapsto 5n, but \mathbb{Z}_{11} \rtimes_a \mathbb{Z} and \mathbb{Z}_{11} \rtimes_b \mathbb{Z} are not isomorphic.

In particular, we deduce that:

Corollary: \mathbb{Z} is not a cancellation group.

 

Follow

Get every new post delivered to your Inbox.