## A prime as a sum of two squares

In this note, we are interested in the following well-known result:

Theorem: A prime $p \geq 3$ can be written as the sum of two squares if and only if $p \equiv 1 \ \mathrm{mod} \ 4$.

There exist many different proofs of this theorem, but a surprising one is exposed by D. Zagier in his article A one-sentence proof that every prime $p = 1 \ ( \mathrm{mod} \ 4)$ is a sum of two squares. Our note is dedicated to this proof.

First of all, it is easy to prove that the sum of two squares is either congruent to $0$, $1$ or $2$ modulo $4$. Thus, because $p$ is necessarily odd, if it can be written as the sum of two squares then $p \equiv 1 \ \mathrm{mod} \ 4$.

Conversely, let $p$ be a prime satisfying $p \equiv 1 \ \mathrm{mod} \ 4$, and define the set

$S= \{ (x,y,z) \in \mathbb{N}^3 \mid x^2+4yz=p \}$.

Notice that $S$ is nonempty since $p \equiv 1 \ \mathrm{mod} \ 4$: there exists a $k \geq 1$ such that

$p=4k+1= 1^2+4 \cdot k \cdot 1$.

Now, let $f : S \to S$ be the map defined by

$(x,y,z) \mapsto \left\{ \begin{array}{cl} (x+2z, z, y-x-z) & \text{if} \ x 2y \end{array} \right.$

It is not difficult to show that $f$ is well-defined on $S$, because $(2y,y,z), (y-z,y,z) \notin S$ for all $y,z \geq 1$. Furthermore, an easy calculation proves that the image of $f$ is included into $S$.

Now, we want to prove that $f$ is an involution with exactly one fixed point.

The map $f$ is an involution. Let $(x,y,z) \in S$. If $x, then $x+2z>2z$ implies

$f \circ f(x,y,z)= (x+2z-2z, x+2z-z+y-x-z,z)=(x,y,z)$;

if $y-z, then $y-x+y-z< 2y-x<2y$ implies

$f \circ f(x,y,z)= (2y-2y+x,y, 2y-x-y+x-y+z)= (x,y,z)$;

if $x>2y$, then $x-2y implies

$f \circ f (x,y,z) = (x-2+2y, y , x-y+z-x+2y-y)=(x,y,z)$.

Therefore, $f \circ f = \mathrm{Id}_S$ ie. $f$ is an involution.

The map $f$ has only one fixed point. Clearly, if $p = 4k+1$ then $(1,1,k)$ is a fixed point of $f$. Conversely, let $(x,y,z) \in S$ be a fixed point of $f$. If $x < y-z$ then $(x,y,z)$ is a solution of

$\left\{ \begin{array}{l} x= x+2z \\ y= z \\ z = y- x -z \end{array} \right.$,

hence $x=y=z=0$, which is impossible. If $y-z then $(x,y,z)$ is a solution of

$\left\{ \begin{array}{l} x=2y-x \\ z = x-y+z \end{array} \right.$,

hence $x=y$. Thus, $(x,x,z) \in S$ implies $p=x^2+4xz=x(x+4z)$. Because $p$ is prime, necessarily $x=1$, and we deduce that $(x,y,z)= (1,1,k)$.

Finally, if $x >2y$ then $(x,y,z)$ is a solution of

$\left\{ \begin{array}{l} x =x -2y \\ y= x-y +z \\ z= y \end{array} \right.$,

hence $x=y=z=0$, which is impossible. Therefore, $f$ has exactly one fixed point: $(1,1,k)$.

In order to conclude the proof of our theorem, we need the following lemma:

Lemma: Let $X$ be a set and $h : X \to X$ an involution. Then $\# \mathrm{Fix}(h) \equiv \# X \ \mathrm{mod} \ 2$.

Proof. Let $Y$ be a maximal subset of $X$ satisfying $Y \cap h(Y)= \emptyset$. Then

$X= \mathrm{Fix}(h) \sqcup Y \sqcup h(Y)$,

which implies $\# X = \# \mathrm{Fix} (h) + 2 \cdot \# Y$. This proves the lemma. $\square$

Now we are able to conclude the proof of our theorem. Let $g : S \to S$ be a new map defined by $(x,y,z) \mapsto (x,z,y)$. Clearly, $g$ is a well-defined involution of $S$. By applying our previous lemma twice, we deduce that

$\# \mathrm{Fix}(g) \equiv \# X \equiv \# \mathrm{Fix} (f) \equiv 1 \ \mathrm{mod} \ 2$.

In particular, $\mathrm{Fix}(g)$ is nonempty. Let $(x,y,y) \in S$ be one of its points. Then

$p = x^2+4yy = x^2+(2y)^2$.

This proves that $p$ can be written as the sum of two squares, and the proof is complete.

## Another application of Baire category theorem

There exist a large number of, sometimes surprising, applications of Baire category theorem. For instance, in this blog, we saw that

• two generic orientation-preserving homeomorphisms of the circle $\mathbb{S}^1$ generate a non abelian free subgroup,
• a generic continuous function $[0,1] \to \mathbb{R}$ is nowhere differentiable.

See the previous notes Free groups acting on the circle and Almost all continuous functions are nowhere differentiable. Now, we want to prove:

Theorem: If $n \geq 3$, the space $\mathbb{R}^n \backslash \mathbb{Q}^n$ is simply connected.

Fix a base point $x \in \mathbb{R}^n \backslash \mathbb{Q}^n$ and an enumeration $\mathbb{Q}^n = \{ q_1, q_2, \ldots \}$. Given two closed curves $c_0,c_1 : [0,1] \to \mathbb{R}^n \backslash \mathbb{Q}^n$ satisfying $c_0(0)=c_1(0)=x$, we want to prove that $c_0$ and $c_1$ are homotopic (relatively to $x$) in $\mathbb{R}^n \backslash \mathbb{Q}^n$. Let

$\mathcal{H}(c_0,c_1) = \{ \text{homotopy between} \ c_0 \ \text{and} \ c_1 \ \text{in} \ \mathbb{R}^n \}$.

It is a closed subset of the Banach space $\left( \mathcal{C}^0([0,1]^2, \mathbb{R}^n), \| \cdot \|_{\infty} \right)$ of the continuous functions $[0,1]^2 \to \mathbb{R}^n$ with respect to the supremum norm $\| \cdot \|_{\infty}$, so that $\mathcal{H}(c_0,c_1)$, endowed with the distance induced by $\| \cdot \|_{\infty}$, is a complete metric space. Now, let

$\mathcal{H}^k(c_0,c_1) = \{ h \in \mathcal{H}(c_0,c_1) \mid \mathrm{Im}(h) \cap \{ q_1, \ldots, q_k \}= \emptyset \}$.

Because $n \geq 3$, the space $\mathbb{R}^n \backslash \{ q_1, \ldots, q_k \}$ is simply connected, so that $\mathcal{H}^k(c_0,c_1) \neq \emptyset$. In fact, it is not difficult to convince ourself that $\mathcal{H}^k(c_0,c_1)$ is a dense open subset of $\mathcal{H}(c_0,c_1)$. A possible argument is the following:

First, if $h \in \mathcal{H}^k(c_0,c_1)$ and if $d$ denotes the distance between $\{q_1, \ldots, q_k \}$ and $\mathrm{Im}(h)$ (which is positive since $\mathrm{Im}(h)$ is compact), then the ball in $\mathcal{H}(c_0,c_1)$ of radius $d/2$ and centered at $h$ is clearly included into $\mathcal{H}^k(c_0,c_1)$. Therefore, $\mathcal{H}^k(c_0,c_1)$ is open in $\mathcal{H}(c_0,c_1)$.

Then, let $f_{\epsilon}$ be a bump function whose support is included into $\bigcup\limits_{j=1}^k B(q_i,\epsilon)$ and satisfying $\| f_{\epsilon} \|_{\infty} \leq \epsilon$. Now, given a homotopy $h \in \mathcal{H}(c_0,c_1)$, define the perturbation

$h_{\epsilon} : (s,t) \mapsto (t(t-1)f_{\epsilon} + \mathrm{Id}_X) \circ h(s,t)$.

Of course, $\| h-h_{\epsilon} \|_{\infty} \leq \| f_{\epsilon} \|_{\infty} \leq \epsilon$ and $h_{\epsilon} \in \mathcal{H}(c_0,c_1)$. Furthermore, if $\epsilon$ is small enough and $f_{\epsilon}$ well chosen, then $\mathrm{Im}(h_{\epsilon}) \cap \{ q_1, \ldots, q_k \} = \emptyset$. This proves that $\mathcal{H}^k(c_0,c_1)$ is dense in $\mathcal{H}(c_0,c_1)$.

Now, it is sufficient to apply Baire category theorem to conclude that the intersection $\bigcap\limits_{k \geq 1} \mathcal{H}^k (c_0,c_1)$ is non empty. But any element $h$ of this intersection defines a homotopy between $c_0$ and $c_1$ satisfying $\mathrm{Im}(h) \cap \mathbb{Q}^n = \emptyset$, that is to say a homotopy in $\mathbb{R}^n \backslash \mathbb{Q}^n$.

Therefore, we have proved that any two closed curves in $\mathbb{R}^n \backslash \mathbb{Q}^n$ based at $x$ are homotopic in $\mathbb{R}^n \backslash \mathbb{Q}^n$. This shows that the group $\pi_1(\mathbb{R}^n \backslash \mathbb{Q}^n,x)$ is trivial, ie., the space $\mathbb{R}^n \backslash \mathbb{Q}^n$ is simply connected.

## 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

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

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$.

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:

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

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

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

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

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

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:

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:

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$.

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:

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$