1 Paradoxical Decompositions
1.2 Free groups
Let \(S\) be a set and \(T\) be the alphabet \(\{s,\ s\in S\}\cup\{s^{-1},\ s\in S\}\). That is \(T\) is the set constructed from \(S\) and adding an element denoted \(s^{-1}\) for each \(s\in T\). A word \(w\) on \(T\) is just a finite sequence \(a_1a_2\dots a_n\) of elements \(a_i\) (called letters) of \(T\). The length of \(w\) is the number of its letters, that is \(n\) here. This includes the empty word which has zero length. The word \(w=a_1\dots a_n\) is reduced if there is no index \(i\) and \(s\in S\) such that \(a_i=s\) and \(a_{i+1}=s^{-1}\) or \(a_{i+1}=s\) and \(a_{i}=s^{-1}\).
From any word \(w=a_1a_2\dots a_n\) one can get a reduced one. If for some index \(a_i=s\) and \(a_{i+1}=s^{-1}\) (or \(a_{i+1}=s\) and \(a_{i}=s^{-1}\)), one considers the word \(w'=a_1\dots a_{i-1}a_{i+2}\dots a_n\). One repeats this process (called reduction process) up to ending with a reduced word. The process finishes since the length is a non-negative integer and at each step of the process, the length decreases.
Let \(w=a_1\dots a_n\) and \(w'=b_1\dots b_m\) be two words on \(T\), the concatenation of \(w\) and \(w'\) is the word \(a_1\dots a_nb_1\dots b_m\). For two reduced words \(w\), \(w'\), we denote by \(w\cdot w'\) the redcution of their concatenation.
Definition 1.1 (Free group) Let \(S\) be a set and \(T\) as above. The free group with generator set \(S\) is the set of reduced words on \(T\) and inner law \((w,w')\mapsto w\cdot w'\). We denote this group by \(\mathbf{F}(S)\).
A group \(G\) is free if there is a set \(S\) such that \(G\) is isomorphic to \(\mathbf{F}(S)\).
The rank of a free group \(\mathbf{F}(S)\) is the cardinal of \(S\).
Remark. The identity element in \(\mathbf{F}(S)\) is the empty word and the inverse of the reduced word \(w=a_1\dots a_n\) is \(w^{-1}=a_n^{-1}\dots a_1^{-1}\).
Example 1.1 The fundamental group of a bouquet of \(n\) circles is the free group on \(n\) generators, one per circle.
Lemma 1.1 Let \(S\) be a set and \(\mathbf{F}(S)\) the free group on \(S\). Let \(G\) be some group. Any map \(\varphi\colon S\to G\) extends to a unique homomorphism \(\bar\varphi\colon \mathbf{F}(S)\to G\).
Proof. Let us show uniqueness first and assume \(\bar\varphi\) is as in the lemma. Let \(w\) be some reduced word, \(w=a_1^{\pm1}\dots a_n^{\pm1}\) with \(a_i\in S\). So \(\bar\varphi(w)=\varphi(a_1)^{\pm1}\dots\varphi(a_n)^{\pm1}\) because of the homomorphism property and the fact that \(\bar\varphi(a_i)=\varphi(a_i)\). This shows uniqueness.
To get the existence part, we merely define \(\bar\varphi(a_1\dots a_n)=\varphi(a_1)\dots\varphi(a_n)\). This gives a map \(\bar\varphi\colon \mathbf{F}(S)\to G\) that extends \(\varphi\). It remains to show the homomorphism property. Let \(w=a_1\dots a_n\) and \(w'=b_1\dots b_m\) be reduced word on \(T=S\cup S^{-1}\). If \(a_n\neq b_1^{\pm 1}\) then \(ww'\) is just the concatenation of \(w\) and \(w'\) so by the definition of \(\bar\varphi\), \(\bar\varphi(ww')=\bar\varphi(w)\bar\varphi(w')\). If there are reductions, there is \(k\) such that \(a_{n-i+1}=b_i^{-1}\) for \(i=1,\dots,k-1\) and \(a_{n-k+1}=b_k^{-1}\). So \(ww'=a_1\dots a_{n-k+1}b_k\dots b_m\) and \(\bar\varphi(ww')=\bar\varphi(a_1)\dots \bar\varphi(a_{n-k+1})\bar\varphi(b_k)\dots \bar\varphi(b_m)\). Now, \(\bar\varphi(w)=\bar\varphi(a_1)\dots \bar\varphi(a_{n})\) and, \(\bar\varphi(w')=\bar\varphi(b_1)\dots \bar\varphi(b_{m})\). For \(i=1,\dots,k-1\), \(\bar\varphi(a_{n-i+1})=\bar\varphi(b_i)^{\pm1}\). Finally, \(\bar\varphi(w)\bar\varphi(w')=\bar\varphi(a_{n-k+1})\bar\varphi(b_k)\dots \bar\varphi(b_m)=\bar\varphi(ww').\)
Given a group, it is not always an easy task to determine if it is free or not. The following lemma gives a characterization of free subgroups on two generators.
Lemma 1.2 (Ping-pong lemma) Suppose a group \(G\) acts on a set \(X\) and there are two elements \(a,b\in G\) and 4 disjoint (non-empty) subsets \(A_+\), \(A_-\), \(B_+\), and \(B_-\) of \(X\) such that
- \(a (B_+\cup B_-\cup A_+)\subseteq A_+\),
- \(a^{-1}(B_+\cup B_-\cup A_-) \subseteq A_-\),
- \(b (A_+\cup A_-\cup B_+)\subseteq B_+\) ,and
- \(b^{-1}(A_+\cup A_-\cup B_-)\subseteq B_-\).
Then the subgroup generated by \(a\) and \(b\) is the free group on \(S=\{a,b\}\).
Proof. Let F be the free group on \(S=\{a,b\}\). Let \(\varphi\colon S\to G\) mapping \(a\) to \(a\) and \(b\) to \(b\). By the above lemma, we extends \(\varphi\) to a group homomorphism \(\bar\varphi\colon F\to G\). Its image is the subgroup generated by \(a\) and \(b\) by construction. So it suffices to show injectivity of \(\bar\varphi\). This exactly means that if \(w\) is a reduced word that is not the empty word its image is non trivial in \(G\)
We call \(A_+\) and \(A_-\) the attractive and repulsive sets of \(a\) and vice-versa for \(a^{-1}\). We do the same for \(b,b^{-1}\) with \(B_+,B_-\). If \(w\) is not starts with an \(a\) (i.e. \(a\) is the leftmost letter) then we choose \(x\) not in \(A_+\) and not in the repelling set of the last letter. A short induction on the length shows that \(\bar\varphi(w)(x)\in A_+\) and thus \(\bar\varphi(w)\) is not the identity. Arguing similarly for the other possibilities for the first letter, we get that \(\bar\varphi(w)\) is the identity only if \(w\) is the empty word.
Theorem 1.1 The group \(\mathrm{SO}(3)\) of rotations of the Euclidean space of dimension 3 contains a free subgroup on two generators.
Proof. One considers the matrices \(a=\begin{bmatrix}1/3&-2\sqrt{2}/3&0\\ 2\sqrt{2}/3&1/3&0\\0&0&1\end{bmatrix}\), \(b=\begin{bmatrix}1&0&0\\0&1/3&-2\sqrt{2}/3\\0& 2\sqrt{2}/3&1/3\end{bmatrix}\) that are rotations of angle \(\arccos(1/3)\) along orthogonal axes. Let \(w\) be a non-empty word in \(a\) and \(b\). Up to conjugating \(w\) by \(a\), we may assume that \(w\) finishes (on the right) with an \(a\). Let us prove by induction on the length of \(w\) that
\[w\begin{bmatrix}1\\0\\0\end{bmatrix}=\frac{1}{3^k}\begin{bmatrix}x\\ y\sqrt{2}\\z\end{bmatrix}\] where \(k\) is the length of \(w\), \(x,y,z\) are integers and \(y\) is not divisible by 3.
For \(k=1\), \(w=a\) and the result is a simple computation. Assume the result for \(k>0\), and that \(w=\ell w'\) where \(|w'|=k\) and \(\ell\in\{a^{\pm1},b^{\pm1}\}\). So
\[w'\begin{bmatrix}1\\0\\0\end{bmatrix}=\frac{1}{3^{k-1}}\begin{bmatrix}x'\\ y'\sqrt{2}\\z'\end{bmatrix}\] where \(x',y',z'\) are integers and \(y'\) is not divisible by 3. So \[w\begin{bmatrix}1\\0\\0\end{bmatrix}=\frac{1}{3^k}\begin{bmatrix}x\\ y\sqrt{2}\\z\end{bmatrix}\] where \(x=x'\mp 4y'\), \(y=(\pm 2x'+y')\) and \(z=3z'\) (if \(\ell=a^{\pm1}\)) or \(x=3x'\), \(y=y'\mp 2z'\) and \(z=\pm 4y'+z'\) (if \(\ell=b^{\pm1}\)). In particular, \(x,y,z\in\mathbf{Z}\) and it remains to show that \(b\) is not divisible by 3.
We consider the following four cases depending on the first two letters of \(w\): \(w=a^{\pm2}v,b^{\pm2}v, a^{\pm1}b^{\pm1}v,b^{\pm1}a^{\pm1}v\) and \(|v|=k-2\).
- \(w=a^{\pm2}v\). By assumption, \(v=\frac{1}{3^{k-2}}\begin{bmatrix}x''\\ y''\sqrt{2}\\z''\end{bmatrix}\) and \(y''\) is not divisible by 3. So, \(y=\pm 2x'+y'=\pm 2(x''\mp 4y'')+y'\)
- \(w=b^{\pm2}v\).
1.3 Paradoxes
Definition 1.2 Let \(G\) be a group acting on a space \(X\).
Two subsets \(A,B\subset X\) are \(G\)-equidecomposable if there are finite partitions \(A=\sqcup A_i\) and \(B=\sqcup B_i\) and elements \(g_i\in G\) such that \(g_i(A_i)=B_i\).
We denote this by \(A\equiv_G B\).
Example 1.2 Let \(G=\mathrm{Isom}(\mathbf{R}^2)\) and \(X=\mathbf{R}^2\). If \(A\) and \(B\) are two polygons with same area then \(A\) and \(B\) are \(G\)-equicomposable. This is a strenghtening of a famous theorem due to Bolyai.
This is no more true in dimension 3. It was Hilbert’s third problem solved in the negative by Max Dehn (a student of Hilbert) in 1900.
Lemma 1.3 Equidecomposability is an equivalence relation.
Proof. The only non-obvious point is transitivity of this relation. Let \(A,B,C\subset X\) such that \(A\equiv_GB\) and \(B\equiv_GC\). So there are finite partitions \(A=\sqcup A_i\) and \(B=\sqcup B_i\) and elements \(g_i\in G\) such that \(g_i(A_i)=B_i\) and \(B=\sqcup B'_j\) and \(C=\sqcup C_j\) and elements \(h_j\in G\) such that \(h_j(B'_j)=C_j\).
Let us define \(A_{i,j}=A_i\cap g_i^{-1}(B'_j)\) and \(C_{i,j}=C_j h_j(g_i(A_{i,j}))\) then \((A_{i,j})\) and \((C_{i,j})\) are finite partitions of \(A\) and \(C\) and \(h_jg_i(A_{i,j})=C_{i,j}\). So, \(A\equiv_G C\).
Definition 1.3 We say that the action of a group \(G\) on a space \(X\) is paradoxical if there are disjoints subsets \(A,B\subset X\) such that \(A\equiv_G X\) and \(B\equiv_GX\).
Proposition 1.1 The action of the free group on two generators on itself by left multiplications is paradoxical.
Proof. Let \(G\) be the free group on generators \(a\) and \(b\). Let us write
\[G=\{e\}\sqcup A^+\sqcup A^-\sqcup B_+\sqcup B_-.\]
Let \(A=A_+\sqcup A_-\) and \(B=B_+\sqcup B_-\). Since \(a(G\setminus A_-)=A_+\), \(G\equiv_G A\) and similarly \(G\equiv_GB\).
(#cor:paradox_action) Let \(G\) be a group acting on a space \(X\) such that there exists a free subgroup of rank 2 \(F\) in \(G\) and the action restricted to \(F\) is free then the action of \(G\) on \(X\) is paradoxical.
Proof. Since the action of \(F\) is free, each orbit \(O\) of \(F\) can be identified with \(F\) via the choice of a point \(x\in O\) and the orbit map \(g\mapsto gx\).
For each orbit \(O\), choose a point \(x_O\in O\). Let \(X_{A^\pm}=\sqcup A^\pm x_0\), \(X_{B^\pm}=\sqcup B^{\pm}x_0\) and \(X_e=\sqcup\{x_O\}\) where the unions are over all orbits \(O\) and the set \(A^\pm, B^\pm\) are those from Proposition ??. These sets give a partition of \(X\)
As above one has \(X\equiv_F X_{A^+}\sqcup X_{A^-}\) and \(X\equiv_G X_{B^+}\sqcup X_{B^-}\).
Theorem 1.2 (Hausdorff paradox) There is a countable subset \(C\) of \(\mathbf{S}^2\) and a subgroup \(G\) of \(\mathrm{SO}(3)\) generating by two rotations preserving \(C\) such that \(G\) acts paradoxically on \(\mathbf{S}^2\setminus C\).
Proof. Let \(a\) and \(b\) be two rotations generating a free subgroup \(G\). Let \(C\) be the collection of all points of the sphere that lies on the axis of an element of \(G\). Since the intersection of a vector line and the sphere is two points and \(G\) is countable, \(C\) is countable. Moreover \(G\) preserves \(C\) and we can apply @ref(prop:paradox_action) with \(F=G\) and \(X=\mathbf{S}^2\setminus C\).
Corollary 1.1 The action of \(\mathrm{SO}(3))\) on \(\mathbf{S}^2\) is paradoxical.
Proof. We continue with the same notations as in 1.2. It remains to show that \(\mathbf{S}^2\) and \(\mathbf{S}^2\setminus C\) are \(\mathrm{SO}(3)\)-equidecomposable.
Choose a vector line \(\ell\) that does not meet \(C\). We denote by \(R_\alpha\) the rotation of angle \(\alpha\) and axis \(\ell\) (an orientation of \(\mathbf{R}^3\))
1.5 Exercises
Exercise 1.1 Prove that the subgroup of \(\mathrm{SL}_2(\mathbf{Z})\) generated by the matrices \(a=\begin{bmatrix}1&2\\0&1\end{bmatrix}\) and \(b=\begin{bmatrix}1&0\\2&1\end{bmatrix}\) is free.
One can consider the two subsets of \(\mathbf{R}^2\): \(A=\{(x,y)\in\mathbf{R}^2,\ |x|>|y|\}\) and \(B=\{(x,y)\in\mathbf{R}^2,\ |x|<|y|\}\), show that \(a^{\pm1}B\subseteq A\), \(b^{\pm1}A\subseteq B\) and argue similarly as in the ping-pong lemma.
Exercise 1.2 (Nielsen-Schreier theorem) Using the action of a free group on its Cayley graph, prove that a subgroup of a free group is free.
Exercise 1.3 (A theorem of Vitali) Let \(R\) be an irrational rotation of the circle \(\mathbf{S}^1\) and let \(G\) be the group generated by \(R\).
- Prove that \(G\) acts freely on \(S^1\) (the stabilizer of any point in \(\mathbf{S}\) is trivial).
- Prove there is a partition \(G=\sqcup_{i\in\mathbf{Z}}X_i\) such that \(R(X_i)=X_{i+1}\) for any \(i\in\mathbf{Z}\).
- Prove there is no probability measure on the \(\sigma\)-algebra of all subsets of \(S^1\) that is \(\mathrm{SO}_2(\mathbf{R})\)-invariant. In particular, the Lebesgue measure cannot be extended to all ausbsets of \(\mathbf{S}^1\) and there are non Lebesgue measurable subsets.