## Euler-Poincaré characteristic (I): Euler’s formula and graph theory

This is the introductory note of a sequence of notes dedicated to Euler-Poincaré characteristic. Here, we deal with Euler’s formula from a graph theoritical viewpoint and exhibit several applications including a proof of Pick’s theorem and the classification of Plato’s solids.

We say that a grah is planar if it can be drawn on $\mathbb{R}^2$ (or equivalently on $\mathbb{S}^2$) without edge-crossings. Determining whether a given graph is planar or not is a difficult question in general, and Euler’s formula gives a useful necessary condition:

Theorem: (Euler’s formula) Let $\Gamma \subset \mathbb{R}^2$ be a connected planar graph. Let $v,e,f$ denote respectively the number of vertices, edges and faces (including the unbounded one) of $\Gamma$. Then

$v-e+f=2$.

Proof. Let $T \subset \Gamma$ be a spanning tree. Let $\Gamma^*$ be the dual graph of $\Gamma$ and $T^*$ be the subgraph of $\Gamma^*$ corresponding to the edges of $\Gamma \backslash T$.

Because $T$ is connected, $T^*$ is acyclic, and because $T$ is acyclic, $T^*$ is connected. Therefore, $T^*$ is a spanning tree. We deduce that

$\left\{ \begin{array}{l} v(T)-e(T)=1 \\ v(T^*)-v(T^*)=1 \end{array} \right. \Rightarrow v(T) -e(T)-e(T^*) +v(T^*)=2$.

But $v(T)=v$, $v(T^*)=v(\Gamma^*)=f$ and $e(T)+e(T^*)=e$, hence $v-e+f=2$. $\square$

Twenty proofs of Euler’s formula (including this one) can be found on Eppstein’s webpage.

Theorem: The complete graph $K_n$ is planar if and only if $n \in \{0,1,2,3,4 \}$.

Proof. We may see easily that $K_n$ is planar when $0 \leq n \leq 4$, just draw it! Then, because $K_n$ is a subgraph of $K_m$ when $n \leq m$, it is sufficient to prove that $K_5$ is not planar. Suppose by contradiction that $K_5$ can be drawn on the plane without edge-crossings.

Let $f_i$ be the corresponding faces, whose boundaries have $n(f_i)$ edges. Notice that $K_5$ is simple, so $n(f_i) \geq 3$, and that each edge belongs to two faces, hence

$\displaystyle 2e= \sum\limits_i n(f_i) \geq 3f$.

We deduce from Euler’s formula that $2=v-e+ f \leq v- \frac{1}{3}e$. But $K_5$ has five vertices and ten edges, so the relation becomes $6 \leq 5$, a contradiction. $\square$

Theorem: The complete bipartite graph $K_{m,n}$ is planar if and only if $m$ or $n \leq 2$.

Proof. If $m \leq 2$ or $n \leq 2$, then $K_{m,n}$ is planar as shown by the following figure:

Then, since $K_{m,n}$ is a subgraph of $K_{p,q}$ if $m \leq p$ and $n \leq q$, it is sufficient to prove that $K_{3,3}$ is not planar. Suppose by contradiction that $K_{3,3}$ can be drawn on the plane without edge-crossings.

Let $f_i$ be the corresponding faces, whose boundaries have $n(f_i)$ edges. Notice that any cycle in $K_{3,3}$ has even length, so $n(f_i) \geq 4$, and that each edge belongs to two faces, hence

$\displaystyle 2e= \sum\limits_i n(f_i) \geq 4f$.

We deduce from Euler’s formula that $2=v-e+f \leq v- \frac{1}{2}e$. But $K_{3,3}$ has six vertices and nine edges, so the relation becomes $4 \leq 3$, a contradiction. $\square$

Theorem: Petersen’s graph is not planar.

Proof. Suppose by contradiction that Petersen’s graph can be drawn on the plane without edge-crossings and let $f_i$ be the correponding faces. Noticing that the smallest cycle in Petersen’s graph has length five, we deduce that $n(f_i) \geq 5$, hence

$\displaystyle 2e= \sum\limits_i n(f_i) \geq 5f$.

From Euler’s formula, we deduce that $2=v-e+f \leq v- \frac{3}{5}e$. But Petersen’s graph has ten vertices and fifteen edges, so the relation becomes $2 \leq 1$, a contradiction. $\square$

Our proofs are in fact based on the corollary of Euler’s formula stating that a connected planar graph $\Gamma$ satisfies

$\displaystyle 2 \leq v- \frac{\ell-2}{\ell} e$

where $\ell$ is the length of the smallest cycle in $\Gamma$.

In fact, topological graph theory asks more generally whether, given a graph $\Gamma$ and a space $X$, there exists an embedding $\Gamma \hookrightarrow X$. The answer depends widely on the topology of $X$, so it is not surprinsing to notice topological applications of Euler’s formula.

Theorem: $\mathbb{R}^2$ and $\mathbb{R}^3$ are not homeomorphic.

Proof. We just saw that there is no embedding $K_5 \hookrightarrow \mathbb{R}^2$ whereas there is clearly an embedding $K_5 \hookrightarrow \mathbb{R}^3$. $\square$

Theorem: $\mathbb{S}^2$ and $\mathbb{R}P^2$ are not homeomorphic.

Proof. We just saw that there is no embedding $K_5 \hookrightarrow \mathbb{R}^2$. However, it is possible to draw $K_5$ on $\mathbb{R}P^2$ (or on the Möbius band) without edge-crossings, as illustrated by the following figure:

$\square$

During our proof of Euler’s formula, we implicitely used Jordan curve theorem to state that connectedness and acyclicness are dual; moreover, applying Euler’s formula for a loop gives Jordan curve theorem, so these two theorems are in fact equivalent. Therefore, while the two previous theorems follow easily from Jordan curve theorem, we did not simplify the proofs, but we formulated them as motivating examples of purely topological applications of topological graph theory.

We already gave a proof of Pick’s theorem in a previous note, here is another one based on Euler’s formula. We also use the following lemma, proved in the mentionned note:

Lemma: Let $P \subset \mathbb{R}^2$ be a polygon. Then $P$ contains a diagonal, that is an edge between two vertices lying in the interior of $P$.

Theorem: (Pick) Let $P \subset \mathbb{R}^2$ be a simple polygon whose vertices are in $\mathbb{Z}^2$. Let $i$ (resp. $b$) denote the cardinality of $\mathrm{int}(P) \cap \mathbb{Z}^2$ (resp. of $\partial P \cap \mathbb{Z}^2$). Then the area $A(P)$ of $P$ is given by the formula

$\displaystyle A(P)= i + \frac{b}{2}-1$.

Proof. According to the previous lemma, we may triangulate $P$. Moreover, if a triangle $T$ contains a point of $\mathbb{Z}^2$, we may join this point to the three vertices of $T$. Therefore, we may triangulate $P$ using triangles intersecting $\mathbb{Z}^2$ only at their vertices. For example:

Now, it is not difficult to check Pick’s formula for the previous kind of triangles, hence

$A(P)= \frac{1}{2}(f-1)$.

Let $e_b$ (resp. $e_i$) be the number of boundary edges (resp. interior edges) of the triangulation. Noticing that a boundary edge (resp. an interior edge) lies in exactly one (resp. exactly two) triangle(s), we deduce that $3(f-1)=2e_b+e_i$. Moreover, we clearly have $e_b=b$, $e=e_i+e_b$ and $v=i+b$. According to Euler’s formula:

$2 = v-e+f = v - (e_i+e_b) + \left( \frac{2}{3} e_i+ \frac{1}{3} e_b + 1 \right) =v- \frac{1}{3} e_i - \frac{2}{3} e_b +1 \\ \\ 2= (i+b) - \frac{1}{3} \left( 3 A(P) - \frac{1}{2} b \right) - \frac{2}{3} b +1 = i- A(P) + \frac{1}{2} b+1$

hence $A(P)=i + \frac{1}{2}b-1$. $\square$

Theorem: There exist only five Plato’s solids, namely the tetrahedron, the hexahedron (cube), the octahedron, the dodecahedron and the icosahedron.

Proof. If each vertex has degree $m$ and each face is a $n$-gon, then summing the number of edges adjacent to each vertex we get $2e=mv$; summing the number of boundary edges of each face we get $2e=nf$. Using Euler’s formula, we deduce the relation

$\displaystyle \frac{1}{m} + \frac{1}{n} = \frac{1}{2} + \frac{1}{e}$.

Of course, we necessarily have $m,n \geq 3$. But if $m,n \geq 4$ then $\frac{1}{n}+ \frac{1}{m} \leq \frac{1}{2}$, which is in contradiction with the previous relation; therefore, either $m=3$ and necessarily $n \in \{ 3,4,5 \}$ so that $\frac{1}{n}+ \frac{1}{m} > \frac{1}{2}$, or $n=3$ and $m \in \{3,4,5\}$ for the same reason.

Consequently, $(m,n,e)$ is:

• either $(3,3,6)$ and the polyhedron is a tetrahedron,
• or $(3,4,12)$ and the polyhedron is a hexahedron (cube),
• or $(3,5,30)$ and the polyhedron is a dodecahedron,
• or $(4,3,12)$ and the polyhedron is an octahedron,
• or $(5,3,30)$ and the polyhedron is an icosahedron. $\square$

Theorem: Any map can be coloured so that two adjacent regions have different colors using only six colors.

Proof. First, we prove that a simple planar graph has a vertex of degree at most five. Suppose by contradiction that any vertex has degree at least six. Let $f_k$ denote the number of faces whose boundaries contain exactly $k$ edges and let $v_k$ denote the number of vertices of degree $k$. Because our graph is simple,

$\left\{ \begin{array}{l} f=f_3+f_4+ \cdots \\ 2e= 3f_3+4f_4+ \cdots \end{array} \right. \Rightarrow 2e \geq 3(f_3+f_4+ \cdots)=3f$,

and because each vertex has degree at least six,

$\left\{ \begin{array}{l} v=v_6+v_7+ \cdots \\ 2e= 6v_6+7v_7+ \cdots \end{array} \right. \Rightarrow 2e \geq 6(v_6+v_7+ \cdots) = 2v$.

Using Euler’s formula, we deduce $2 =v-e+f \leq \frac{1}{3}e- e + \frac{2}{3}e=0$, a contradiction.

Now, a map defines a planar graph; let $\Gamma$ be its dual graph. In particular, $\Gamma$ is a simple planar graph, and our theorem is equivalent to the fact that the vertices of $\Gamma$ can be coloured using only six colors so that two adjacent vertices have different colors. We show this by induction on the number $n$ of vertices of $\Gamma$. For $n\leq 6$, there is nothing to prove. Otherwise, let $v$ be a vertex of degree at most five. Thanks to our induction hypothesis, $\Gamma \backslash \{v\}$ can be coloured in a good way. Now, we can label $v$ by any color that is different from its neighbors; it is possible because $v$ has degree at most five and that we use six colors. Finally, $\Gamma$ is coloured in a good way. $\square$

Actually, the theorem is true for four colors only, but the proof is far from being as elementary as the previous one; see four color theorem. An elementary proof for five colors can be found in M. Aigner and G. Ziegler’s book, Proofs from the Book.

## Free groups acting on the circle

We present here an unusual application of Baire category theorem between topology, group theory and dynamical systems. Roughly speaking, we prove that almost all pairs of homeomorphisms of the circle are unrelated; in particular, it leads to natural occurrences of free groups.

More precisely, if $\mathrm{Homeo}^+(\mathbb{S}^1)$ denotes the set of orientation-preserving homeomorphisms of the circle, endowed with the distance

$d(f,g)= \max \left( \| f-g \|_{\infty}, \| f^{-1}-g^{-1} \|_{\infty} \right), \ \forall f,g \in \mathrm{Homeo}^+(\mathbb{S}^1)$

where $\| \cdot \|_{\infty} = \sup\limits_{\mathbb{S}^1} \| \cdot \|$, we prove

Theorem: The set of pairs $(f,g) \in \mathrm{Homeo}^+(\mathbb{S}^1) \times \mathrm{Homeo}^+(\mathbb{S}^1)$ generating a free subgroup of rank two in $\mathrm{Homeo}^+(\mathbb{S}^1)$ is a dense $G_{\delta}$ in $\mathrm{Homeo}^+(\mathbb{S}^1) \times \mathrm{Homeo}^+(\mathbb{S}^1)$.

Proof. With the distance given above, $\mathrm{Homeo}^+(\mathbb{S}^1)$ is a complete metric space, so Baire category theorem applies.

If $w \in \mathbb{F}_2$ is a reduced word, let $X_w$ denote the set of

$(f,g,x) \in \mathrm{Homeo}^+( \mathbb{S}^1) \times \mathrm{Homeo}^+( \mathbb{S}^1) \times \mathbb{S}^1$

satisfying $w(f,g)(x) =x$. Let us show that each $X_w$ is a closed set whose interior is empty; it will allow us to deduce that the set of  $(f,g) \in \mathrm{Homeo}^+(\mathbb{S}^1) \times \mathrm{Homeo}^+(\mathbb{S}^1)$ satisfying $w(f,g)= \mathrm{Id}$ is a closed set whose interior is nonempty: indeed, if $w(f,g)= \mathrm{Id}$ and $x \in \mathbb{S}^1$, then $(f,g,x) \in X_w$, so there exist $f_0$, $g_0$ and $x_0$ arbitrarily close to $f$, $g$ and $x$ respectively, so that $(f_0,g_0,x_0) \notin X_w$ ie. $w(f_0,g_0)(x_0) \neq x_0$, hence $w(f_0,g_0) \neq \mathrm{Id}$; consequently, according to Baire category theorem, the set

$\displaystyle \{ (f,g) \mid \langle f,g \rangle \not\simeq \mathbb{F}_2 \} = \bigcup\limits_{w \in \mathbb{F}_2} \{ (f,g) \mid w(f,g)= \mathrm{Id} \}$

has empty interior and its complement  is a dense $G_{\delta}$, completing the proof.

By contradiction, let $w$ be a word of minimal length $k$ such that $X_w$ has nonempty interior. In particular, there exists a nonempty open set $U \subset X_w$. For all words $w_1,w_2 \in \mathbb{F}_2$, let

$F(w_1,w_2)= \{ (f,g,x) \mid w_1(f,g)w_2(f,g)(x)=w_2(f,g)(x) \}$

denote the image of $X_{w_1}$ by the homeomorphism  $(f,g,x) \mapsto (f,g,w_2(f,g)^{-1}(x))$; in particular, $F(w_1,w_2)$ is closed set whose interior is empty if $\mathrm{\ell g}(w_1),\mathrm{\ell g}(w_2).

Because $\bigcup\limits_{\mathrm{\ell g}(w_1),\mathrm{\ell g}(w_2) is itself a closed set whose interior is empty, there exists $(f,g,x) \in U$ such that $(f,g,x) \notin F(w_1,w_2)$ for all words satisfying $\mathrm{lg}(w_1), \mathrm{lg}(w_2).

Let $w(f,g)=h_1 \circ \cdots \circ h_k$ where $h_i \in \{ f,f^{-1},g,g^{-1}\}$ ($1 \leq i \leq k$) and set

$x_1=h_1(x), ~ \dots, ~ x_{k-1}=h_{k-1}(x_{k-2}), ~ x_k=h_k(x_{k-1})$.

First, notice that $x_k=w(f,g)(x)=x$ since $(f,g,x) \in X_w$ and that $x_i \neq x_j$ if $i \neq j$. Indeed, if it was not the case, there would exist a proper subword $w_1(f,g)$ of $w(f,g)$ fixing $x_i$, while $x_i=w_2(f,g)(x)$ for some word $w_2$, hence $(f,g,x) \in F(w_1,w_2)$, a contradiction.

To conclude, let $\tilde{f}$ and $\tilde{g}$ be two homeomorphisms arbitrarily close to $f$ and $g$ respectively, and satisfying $x_1= \tilde{h}_1(x_1), ~ \dots, ~ x_{k-1}= \tilde{h}_{k-1}(x_{k-2})$ but $x_k \neq \tilde{h}_k(x_{k-1})$.

[To do that, let $\mathbb{S}^1= \mathbb{R}/ \mathbb{Z}$ and show that each homeomorphism of the circle can be approximated by a piecewise linear homeomorphism (using a classical argument based on uniform continuity); then we deduce easily that a homeomorphism of the circle can be approximated by a homeomorphism agreeing on a finite set of points and disagreeing on another finite set of points.]

Thus, $(\tilde{f}, \tilde{g},x) \in U \subset X_w$ because $U$ is open, but $w(\tilde{f},\tilde{g})(x)=\tilde{h}_k(x_{k-1}) \neq x_k=x$ by construction, a contradiction. $\square$

We deduce from our theorem that $\mathrm{Homeo}^+(\mathbb{S}^1)$ has a lot of free subgroups, but the given proof does not provide any explicit example. In order to exhibit free subgroups, we use ping-pong lemma:

Lemma: Let $G$ be a group acting on a set $S$ such that there exist $x,y \in G$ and $X,Y \subset S$ satisfying

• $X$ and $Y$ are non-empty and disjoint,
• $x^n \cdot X \subset Y$ and $y^n \cdot Y \subset X$ for all $n \in \mathbb{Z} \backslash \{ 0\}$.

Then $\langle x,y \rangle$ is a free group of basis $\{x,y \}$.

Proof. Clearly, the second condition implies that $x$ and $y$ has infinite order. Moreover, any reduced word $w$ over $\{ x^{\pm 1}, y^{\pm 1} \}$ not in $\langle x \rangle \cup \langle y \rangle$ can be written (up to conjugacy) as

$w= y^{m_0} \cdot x^{n_1} \cdot y^{m_1} \cdots x^{n_r} \cdot y^{m_r}$ with $r \geq 1$ and $n_i,m_i \in \mathbb{S} \backslash \{ 0 \}$.

Let $a \in Y$. If $w=1$ in $G$, then $a = w \cdot a$. But $a \in Y$, hence $y^{m_r} \cdot a \in X$, hence $x^{n_r} \cdot y^{m_r} \cdot a \in Y$, and so on; finally, $w \cdot a \in X$. We deduce that $a = w \cdot a \in X \cap Y = \emptyset$, a contradiction. Therefore, $w \neq 1$ in $G$ and $\langle x,y \rangle$ is a free subgroup of basis $\{x,y \}$. $\square$

The first example of free subgroup of $\mathrm{Homeo}^+(\mathbb{S}^1)$ comes from the natural action of $GL(2, \mathbb{Z})$ on the set of lines passing through the origin, that is on $\mathbb{R}P^1$. An explicit homeomorphism between $\mathbb{R}P^1$ and $\mathbb{S}^1$ is illustrated by Figure 1, where the two blue points are identified.

Figure 1.

Now we wan to apply ping-pong lemma to $A = \left( \begin{matrix} 1 & 2 \\ 0 & 1 \end{matrix} \right)$ and $B= \left( \begin{matrix} 1 & 0 \\ 2 & 1 \end{matrix} \right)$. The actions of $A$ and $B$ on the circle are illustrated by Figures 2 and 3 respectively, through the previous homeomorphism.

Figure 2.

Figure 3.

Therefore, ping-pong lemma applies with $X$ and $Y$ as indicated:

Therefore, $\{ A, B \}$ is a free basis and generates a free subgroup of $GL(2,\mathbb{Z})$, and a fortiori of $\mathrm{Homeo}^+(\mathbb{S}^1)$.

Our second example comes from the homeomorphism $\mathbb{R} / \mathbb{Z} \simeq \mathbb{S}^1$ and is based on piecewise linear homeomorphisms:

Definition: Let $f : \mathbb{R} \to \mathbb{R}$ be a homeomorphism satisfying $f(x+1)=f(x)+1$ for all $x \in \mathbb{R}$. If there exists a sequence of reals $\{ x_i \mid i \in \mathbb{Z} \}$ satisfying $\lim\limits_{i \to \pm \infty} x_i = \pm \infty$ and such that $f$ is affine on each $[x_i,x_{i+1}]$, then the induced homeomorphism $\tilde{f} : \mathbb{R} / \mathbb{Z} \to \mathbb{R} / \mathbb{Z}$ is said piecewise linear.

The set of piecewise linear homeomorphisms of the circle is denoted by $PL_+(\mathbb{S}^1)$.

Let $f$ and $g$ be two piecewise linear homeomorphisms of the circle whose graphs are respectively

Moreover, the graphs of $f^{-1}$ and $g^{-1}$ are respectively

Easily, we deduce that for all $n \in \mathbb{Z} \backslash \{ -1,0,1 \}$,

$f^n \left( \left( \frac{1}{3}, \frac{2}{3} \right) \right) \subset \left( 0, \frac{1}{3} \right) \cup \left( \frac{2}{3}, 1 \right)$ and $g^n \left( \left( 0,\frac{1}{3} \right) \cup \left( \frac{2}{3},1 \right) \right) \subset \left( \frac{1}{3}, \frac{2}{3} \right)$.

Therefore, ping-pong lemma applies, and $\langle f^2,g^2 \rangle$ is a free subgroup of rank two of the group $PL_+(\mathbb{S}^1) \subset \mathrm{Homeo}^+(\mathbb{S}^1)$.

More information about the group of homeomorphisms of the circle can be found in Etienne Ghys’ document, Groups acting on the circle.

## Third Homotopy Group of the Sphere and Hopf Fibration

The idea of this note comes from the chapter $\pi_3(S^2)$, H. Hopf, W.K. Clifford, F. Klein written by H. Samelson in I.M. James’ book, History of Topology, and more precisely from the quoted letter from Hopf to Freudhental:

In case you are still interested in the question of the [homotopy] classes of maps of the 3-sphere $S^3$ onto the 2-sphere $S^2$ I want to tell you that I now can answer this question: there exist infinitely many classes. Namely there is a class invariant of the given map the counter image of $x$ consists of finitely many simple closed oriented polygons $P_1$, $P_2$, …, $P_a$ and likewise the counter image of $y$ consists of polygons $Q_1$, $Q_2$, …, $Q_b$. If $v_{ij}$ denotes the linking number of $P_i$ and $Q_j$, then $\sum_{i,j} v_{ij}= \gamma$ is independent of $x, ~ y$ and of the approximation and does not change under continuous change of the map. For every $\gamma$ there exists maps. Whether to every $\gamma$ there is only one map, I do not know. If the whole $S^2$ is not covered by the image, then $\gamma$ is $=0$. A consequence is that one cannot sweep the line elements on $S^2$ continuously into a point.

Our aim is to developp this nice geometric argument following problems 13, 14 and 15 of Milnor’s book, Topology from differential viewpoint. Thus, our main result is:

Theorem: The group $\pi_3(\mathbb{S}^2)$ is infinite.

In fact, it may be proved that $\pi_3(\mathbb{S}^2) \simeq \mathbb{Z}$. As a consequence that $\pi_n(\mathbb{S}^m)$ may be non-trivial when $n>m$ is that the homotopy group is not determined by the CW complex structure, unlike homology and cohomology groups.

The first step is to define the linking number of two submanifolds of $\mathbb{R}^{k+1}$ with total dimension $k$. For that purpose, we use degree theory; for more information, see Milnor’s book.

Definition: Let $f : M \to N$ be a smooth map between two $n$-dimensional smooth compact oriented manifolds. If $p \in M$ is a regular point, let $\mathrm{sign} (df(p))$ be $+1$ if $df(p)$ is orientation-preserving and $-1$ otherwise. The degree of $f$ with respect to a regular value $q \in N$ is defined by

$\displaystyle \mathrm{deg}(f,q)= \sum\limits_{p \in f^{-1}(q)} \mathrm{sign}(df(p))$.

Property 1: The degree $\mathrm{deg}(f,q)$ does not depend on the regular value $q$.

In particular, property 1 allows us to define the degree $\mathrm{deg}(f)$ of a smooth map $f$ without reference to any regular value.

Property 2: If two smooth maps $f$ and $g$ are smoothly homotopic, then $\mathrm{deg}(f)= \mathrm{deg}(g)$.

Property 3: Let $M$, $N$ be two smooth manifolds and $f : M \to N$ be a smooth map. If there exists a smooth manifold $X$ whose boundary is $M$ and such that $f$ extends to a smooth map $X \to N$, then $\mathrm{deg}(f)=0$.

Properties 1 and 2 are fundamental in degree theory; property 3 is a rather technical lemma used to prove the two previous properties, but it will be useful later.

Definition: Let $M,N \subset \mathbb{R}^{k+1}$ be two submanifolds of total dimension $m+n=k$. The linking number $l(M,N)$ is defined as the degree of the linking map

$\lambda : \left\{ \begin{array}{ccc} M \times N & \to & \mathbb{S}^k \\ (a,b) & \mapsto & \frac{a-b}{ \| a-b \| } \end{array} \right.$.

Property 4: $l(M,N)= (-1)^{(m+1)(n+1)} l(N,M)$.

Proof. Let $\lambda_1, \lambda_2$ be the linking maps

$\lambda_1 : \left\{ \begin{array}{ccc} M \times N & \to & \mathbb{S}^k \\ (a,b) & \mapsto & \frac{a-b}{ \| a - b \| } \end{array} \right.$ and $\lambda_2 : \left\{ \begin{array}{ccc} N \times M & \to & \mathbb{S}^k \\ (a,b) & \mapsto & \frac{a-b}{ \| a-b \| } \end{array} \right.$,

and let for convenience

$I : \left\{ \begin{array}{ccc} M \times N & \to & N \times M \\ (a,b) & \mapsto & (b,a) \end{array} \right.$.

Then $\lambda_1 = - \lambda_2 \circ I$. It is an easy exercice to show that $\deg(f \circ g)= \deg(f) \cdot \deg(g)$ when $g$ is a diffeomorphism, and that $\deg(-f)= (-1)^{k+1} \deg(f)$. So

$l(M,N)= \deg(\lambda_1)= (-1)^{k+1} \cdot \deg(I) \cdot \deg(\lambda_2)= (-1)^{m+n+1} (-1)^{mn} l(N,M)$. $\square$

Property 5: If $M$ bounds an oriented manifold disjoint from $N$, then $l(M,N)=0$.

Proof. If $X \subset \mathbb{R}^{k+1}$ is an oriented submanifold such that $\partial X = M$, then the map

$\Lambda : \left\{ \begin{array}{ccc} X \times N & \to & \mathbb{S}^k \\ (a,b) & \mapsto & \frac{a-b}{ \| a-b \| } \end{array} \right.$

extends the linking map $\lambda : M \times N \to \mathbb{S}^k$, and $\partial (X \times N)= \partial X \times N= M \times N$, hence $l(M,N)= \deg(\lambda)=0$ according to property 3. $\square$

If $M$ and $N$ are two knots in $\mathbb{R}^3$, it is possible to compute $l(M,N)$ from a regular diagram.

More precisely, if $v \in \mathbb{S}^2$ and $P$ is the plane normal to $v$, then the projection of $M \cup N$ on $P$ is a regular diagram $D$ if $v$ is a regular value of $\lambda$; moreover, $\lambda^{-1}(v)$ is exactly the crossing points of $D$ when $M$ is over $N$. Therefore, $l(M,N)=r-s$ where $r$ (resp. $s$) is the number of crossing points where $\lambda$ is orientation-preserving (resp. orientation-reversing); on $D$, such crossing points correspond respectively to

For example, the linking number computed on the following diagramm is two:

Before introducing Hopf invariant, let us mention some results about cobordism, needed in the sequel:

## Some cobordism theory:

Definition: Two oriented compact manifolds $M, N$ are cobordant if there exists an oriented compact manifold $X$, called a cobordism, such that $\partial X= M \coprod (-N)$ where $-N$ denotes $N$ with the reversed orientation.

Lemma 1: Let $f : M \to \mathbb{S}^p$ be a smooth map and $y \in \mathbb{S}^p$ be a regular value. If $z \in \mathbb{S}^p$ is a regular value sufficently close to $y$, then there exists a cobordism $X \subset M \times [0,1]$ between $f^{-1}(y)$ and $f^{-1}(z)$.

Proof. If $C$ is the set of singular points of $f$, $f(C)$ is compact so there exists an open neighborhood $V$ of $y$ containing only regular values. Let $z \in V$.

Let $\gamma : [0,1] \to \mathbb{S}^p$ be a great circle from $y$ to $z$, and let $r_t$ be a rotation whose restriction to $\mathrm{span}(y,z)$ is a rotation sending $y$ to $\gamma(t)$. In particular, if $r_0= \mathrm{Id}$, $(r_t)$ defines an isotopy between $\mathrm{Id}$ and $r_1$. Let

$F : \left\{ \begin{array}{ccc} M \times [0,1] & \to & \mathbb{S}^p \\ (x,t) & \mapsto & r_t \circ f(x) \end{array} \right.$.

Because $r_t^{-1}(z) \in V$, $z$ is a regular value of $F(t, \cdot)$ and finally to $F$ since

$\displaystyle dF(m,s)= r_s \circ df(m) + \frac{\partial r_t}{\partial t}_{|t=s} \circ f(m) dt$.

Thus, $F^{-1}(z) \subset M \times [0,1]$ defines a cobordism between $f^{-1}(z)$ and $f^{-1}(r_1^{-1}(z))=f^{-1}(y)$. $\square$

Lemma 2: If $f,g : M \to \mathbb{S}^p$ are smoothly homotopic and $y \in \mathbb{S}^p$ is a regular value for both, then there exists a cobordism $X \subset M \times [0,1]$ between $f^{-1}(y)$ and $g^{-1}(y)$.

Proof. Let $H : M \times [0,1] \to \mathbb{S}^p$ be a homotopy between $f$ and $g$. Let $z$ be a regular value of $H$ close to $y$ so that $f^{-1}(y)$ and $f^{-1}(z)$, and $g^{-1}(y)$ and $g^{-1}(z)$, are cobordant (using lemma 1). Then $H^{-1}(z)$ defines a cobordism between $f^{-1}(z)$ and $g^{-1}(z)$. Lemma 2 follows since cobordism is an equivalent relation. $\square$

## Hopf invariant:

From now on, let $f : \mathbb{S}^{2p-1} \to \mathbb{S}^p$ be a smooth map and $y \neq z$ be two regular values. Applying a stereographic projection, we may view $f^{-1}(y)$ and $f^{-1}(z)$ as submanifolds of $\mathbb{R}^{2p-1}$. Then the linking number $l(f^{-1}(y),f^{-1}(z))$ is well-defined.

Claim 1: The linking number $l(f^{-1}(y),f^{-1}(z))$ does not depend on the stereographic projection.

Proof. A stereographic projection is an orientation-preserving diffeomorphism, so if $p$ and $q$ are two stereographic projections, then $q \circ p^{-1} \times q \circ p^{-1}$ induces an orientation-preserving diffeomorphism between $pf^{-1}(y) \times pf^{-1}(z)$ and $qf^{-1}(y) \times qf^{-1}(z)$, hence

$l(pf^{-1}(y),pf^{-1}(z))= l(qf^{-1}(y),qf^{-1}(z))$. $\square$

Claim 2: The linking number $l(f^{-1}(y),f^{-1}(z))$ is locally constant as a function of $y$.

Proof. Let the mapping maps

$\lambda_1 : \left\{ \begin{array}{ccc} f^{-1}(y) \times f^{-1}(z) & \to & \mathbb{S}^{2p-2} \\ (a,b) & \mapsto & \frac{a-b}{ \| a-b \| } \end{array} \right.$ and $\lambda_2 : \left\{ \begin{array}{ccc} f^{-1}(x) \times f^{-1}(z) & \to & \mathbb{S}^{2p-2} \\ (a,b) & \mapsto & \frac{a-b}{ \| a-b \| } \end{array} \right.$.

According to lemma 1, there exists a cobordism $X \subset \mathbb{R}^{2p-1} \times [0,1]$ between $f^{-1}(y)$ and $f^{-1}(x)$ when $x$ is close to $y$. Let

$\Phi : \left\{ \begin{array}{ccc} X \times f^{-1}(z) & \to & \mathbb{S}^{2p-2} \times [0,1] \\ (a,t,b) & \to & \left( \frac{a-b}{ \| a-b \| },t \right) \end{array} \right.$.

For convenience, let $\partial \Phi$ be the restriction of $\Phi$ on $\partial X \times f^{-1}(z)$, and $\partial_1\Phi$ (resp. $\partial_2 \Phi$) be the restriction of $\partial \Phi$ on $f^{-1}(x) \times \{ 0 \} \times f^{-1}(z)$ (resp. on $f^{-1}(y) \times \{ 1 \} \times f^{-1}(z)$). According to property 3,

$0 = \deg(\partial \Phi)= \deg( \partial_1 \Phi)+ \deg(\partial_2 \Phi)$.

If $\varphi_1, \varphi_2$ are the obvious diffeomorphisms

$\varphi_1 : f^{-1}(x) \times \{ 0 \} \times f^{-1}(z) \to f^{-1}(x) \times f^{-1}(z)$

and

$\varphi_2 : f^{-1}(y) \times \{1\} \times f^{-1}(z) \to f^{-1}(y) \times f^{-1}(z)$,

then $\partial_i \Phi= \lambda_i \circ \varphi_i$ ($i=1,2$), hence

$0= \deg( \lambda_1 ) \cdot \deg(\varphi_1)+ \deg( \lambda_2) \cdot \deg(\varphi_2)$.

But $\varphi_1$ is orientation-preserving whereas $\varphi_2$ is not. Therefore,

$l( f^{-1}(y), f^{-1}(z))= \deg( \lambda_1)= \deg(\lambda_2)= l(f^{-1}(x), f^{-1}(z))$. $\square$

Claim 3: If $y \neq z$ are regular values of $g : \mathbb{S}^{2p-1} \to \mathbb{S}^p$ and $\| f-g \|_{\infty} <1$, then

$l(f^{-1}(y),f^{-1}(z)) = l(g^{-1}(y), f^{-1}(z))$.

Proof. Let $H : \mathbb{S}^{2p-1} \times [0,1] \to \mathbb{S}^p$ be the homotopy

$\displaystyle H(x,t)= \frac{(1-t)f(x)+tg(x)}{ \| (1-t)f(x)+g(x) \| }$.

$H$ is well-defined since $(1-t)f(x)+tg(x)=0$ implies

$1= \| f(x) \| =t \| f(x)-g(x) \| \leq \| f-g \|_{\infty} <1$,

a contradiction. Therefore, $f$ and $g$ are smoothly homotopic. Using lemma 2, we prove in the same way as for claim 2 that the degrees of the associated linking maps are equal so that

$l(f^{-1}(y) , f^{-1}(z))= l(g^{-1}(y),f^{-1}(z))$. $\square$

Property 6: The linking number $l(f^{-1}(y),f^{-1}(z))$ depends only on the homotopy class of $f$.

Proof. According to claim 1, $l(f^{-1}(y),f^{-1}(z))$ does not depend on the stereographic projection. According to claim 2 and property 4, the linking number does not depend on the regular values $y$ and $z$ by connectedness of $\mathbb{S}^{2p-1}$. Finally, if $H$ is a smooth homotopy between $f$ and $g$, then we deduce that

$l(f^{-1}(y),f^{-1}(z))= l(g^{-1}(y),g^{-1}(z))$

from claim 3 and property 4, taking a sequence $0=t_0 < t_1 < \cdots < t_k=1$ satisfying $\| H(t_i , \cdot ) - H ( t_{i+1} , \cdot ) \|_{\infty} < 1$ for all $0 \leq i \leq k-1$. $\square$

Definition: We define the Hopf invariant $H(f)$ of $f$ as the linking number $l(f^{-1}(y),f^{-1}(z))$ for some regular values $y \neq z$.

We just showed that Hopf invariant is a homotopic invariant.

Property 7: If $f : \mathbb{S}^{2p-1} \to \mathbb{S}^p$ and $g : \mathbb{S}^p \to \mathbb{S}^p$, then $H(g \circ f )= H(f) \cdot \deg(g)^2$.

Proof. Let $y \neq z$ be two regular values of $g \circ f$ and $g$, and let $g^{-1}(y)= \{ y_1, \dots, y_r \}$ and $g^{-1}(z)= \{ z_1, \dots, z_s \}$. The inclusions

$f^{-1}(y_i) \times f^{-1}(z_i) \hookrightarrow (g \circ f)^{-1}(y) \times (g \circ f)^{-1} (z)$

induce an orientation-preserving diffeomorphism between

$\displaystyle \coprod\limits_{i=1}^r \coprod\limits_{j=1}^s \left( \mathrm{sign}(dg(y_i)) f^{-1}(y_i) \right) \times \left( \mathrm{sign}(dg(z_j)) f^{-1}(z_j) \right)$

and

$\displaystyle (g \circ f)^{-1}(y) \times (g \circ f )^{-1}(z)$,

so, if $\lambda_{ij} : \left\{ \begin{array}{ccc} f^{-1}(y_i) \times f^{-1}(z_j) & \to & \mathbb{S}^{2p-2} \\ (a,b) & \mapsto & \frac{a-b}{ \| a-b \| } \end{array} \right.$, we have:

$\begin{array}{lcl} \deg(\lambda) & = & \displaystyle \sum\limits_{i=1}^r \sum\limits_{j=1}^s \mathrm{sign}(dg(y_i)) \mathrm{sign}(dg(z_j)) \cdot \underset{= H(f)}{\underbrace{\deg(\lambda_{ij})}} \\ \\ & = & \displaystyle H(f) \left( \sum\limits_{i=1}^r \mathrm{sign}(dg(y_i)) \right) \left( \sum\limits_{j=1}^s \mathrm{sign}(dg(z_j)) \right) \\ \\ & = & H(f) \cdot \deg(g)^2 \hspace{1cm} \square \end{array}$

## Hopf fibration:

The sphere $\mathbb{S}^3$ can be viewed as the unit sphere $\{ (z_1,z_2) \mid |z_1|^2+ |z_2|^2=1 \}$ in $\mathbb{C}^2 \simeq \mathbb{R}^4$. Noticing that the intersection between $\mathbb{S}^3$ and any complexe line is a circle, we can say that $\mathbb{S}^3$ is covered by a family of circles $\mathbb{S}^1$ indexed by $\mathbb{C}P^1 \simeq \mathbb{S}^2$.

More precisely, if $(x,y,z,t) \in \mathbb{S}^3 \subset \mathbb{R}^4$ then $(x+iy,z+it) \in \mathbb{S}^3 \subset \mathbb{C}^2$ belongs to the complex line $(z+it)z_2= (x+iy)z_1$; to this line (in $\mathbb{C}P^1$) is associated the complex number $\frac{x+iy}{z+it} \in \mathbb{C} \cup \{ \infty\}$. Finally, if $h : \mathbb{S}^2 \to \mathbb{C} \cup \{\infty\}$ denotes the diffeomorphism induced by the stereographic projection, we get a point $h^{-1} \left( \frac{x+iy}{z+it} \right)$ of the sphere $\mathbb{S}^2$.

Definition: Hopf map $\pi : \left\{ \begin{array}{ccc} \mathbb{S}^3 & \to & \mathbb{S}^2 \\ (x_1,x_2,x_3,x_4) & \mapsto & h^{-1} \left( \frac{x_1+ix_2}{x_3+ix_4} \right) \end{array} \right.$ induces the Hopf fibration $\mathbb{S}^1 \to \mathbb{S}^3 \overset{\pi}{\longrightarrow} \mathbb{S}^2$.

It is possible to visualize the decomposition of $\mathbb{S}^3$ by circles in $\mathbb{R}^3$ using stereographic projection. It gives something like that, a decomposition in concentric torii each covered by their Villarceau circles:

Very nice animations about Hopf fibration can be found in Etienne Ghys, Joe Leys and Aurélien Alvarèz’s movie, Dimensions, and in Niles Johnson’s lecture, Visualizations of Hopf fibration. Now,

$\pi^{-1}(1,0,0)= \{ (x,y,x,y) \mid x^2+y^2= \frac{1}{2} \}$ and $\pi^{-1}(-1,0,0) = \{ (x,y,-x,-y) \mid x^2+y^2= \frac{1}{2} \}$

are two circles in $\mathbb{S}^3$. If $\varphi : \mathbb{S}^3 \subset \mathbb{R}^4 \to \mathbb{R}^3$ is the stereographic projection with respect to $(0,0,0,1)$, then $\varphi(x,y,z,t)= \left( \frac{x}{1-t}, \frac{y}{1-t}, \frac{z}{1-t} \right)$, so the previous circles become

$\left\{ \left( \frac{x}{1-y}, \frac{y}{1-y}, \frac{x}{1-y} \right) \mid x^2+y^2= \frac{1}{2} \right\}$ and $\left\{ \left( \frac{x}{1+y}, \frac{y}{1+y}, - \frac{x}{1+y} \right) \mid x^2+y^2= \frac{1}{2} \right\}$.

In fact, it is just a Hopf link; precisely, if $C_1$ and $C_2$ denotes the projections of the two previous circles on the plane $z=0$, that is

$C_1=\left\{ \left( \frac{x}{1-y}, \frac{y}{1-y} \right) \mid x^2+y^2= \frac{1}{2} \right\}$ and $C_2= \left\{ \left( \frac{x}{1+y}, \frac{y}{1+y} \right) \mid x^2+y^2= \frac{1}{2} \right\}$,

then $C_1 \cap C_2= \left\{ \left( \pm \frac{1}{\sqrt{2}}, 0 \right) \right\}$ where $C_1$ is over $C_2$ at one point, and vice-versa at the other. Therefore, $H(\pi)=1$ (be careful to the orientations!).

On the other hand, $H(f)=0$ for every constant map $f : \mathbb{S}^3 \to \mathbb{S}^2$. Indeed, let

$p : \left\{ \begin{array}{ccc} \mathbb{S}_3 & \to & D^2 \\ (x,y,z,t) & \mapsto & (z,t) \end{array} \right.$

where $D^2$ is the unit two-dimensional disk viewed as a subspace of $\mathbb{S}^2$; in particular, since $D^2$ is contractible, $p$ is homotopic to a constant map $f$ and $H(p)=H(f)$. But the circles $p^{-1}(0,0)= \{ (x,y,0) \mid x^2+y^2=1 \}$ and $p^{-1}(1/2,0)= \{ (x,y,1/2) \mid x^2+y^2= 3/4 \}$ (viewed in $\mathbb{R}^3$ thanks to the stereographic projection with respect to $(0,0,0,1)$) are clearly unlinked, hence $H(p)=0$ according to property 5.

Moreover, using property 7, we deduce that the applications

$p_n : \left\{ \begin{array}{ccc} \mathbb{S}^{3} \subset \mathbb{C}^2 & \to & \mathbb{S}^2= \mathbb{C} \cup \{ \infty \} \\ (z_1,z_2) & \mapsto & \left( z_1/z_2 \right)^n \end{array} \right.$

define a family of pairwise non-homotopic maps, since $H(p_n)= n^2$. We just proved our main theorem!

## Hopf fibration in higher dimensions:

Hopf fibration $\mathbb{S}^1 \to \mathbb{S}^3 \to \mathbb{S}^2$ is obtained using Hopf map $\left\{ \begin{array}{ccc} \mathbb{S}^3 \subset \mathbb{C}^2 & \to & \mathbb{S}^2= \mathbb{C} \cup \{ \infty \} \\ (z_1,z_2) & \mapsto & z_1/z_2 \end{array} \right.$. But the same thing can be done by replacing $\mathbb{C}$ with any real division algebra, for example the quaternions $\mathbb{H}$ or the octonions $\mathbb{O}$.

The associated maps $p : \mathbb{S}^7 \subset \mathbb{H}^2 \to \mathbb{S}^4 = \mathbb{H} \cup \{ \infty \}$ and $q : \mathbb{S}^{15} \subset \mathbb{O}^2 \to \mathbb{S}^8 = \mathbb{O} \cup \{ \infty \}$ induce respectively the Hopf fibrations $\mathbb{S}^3 \longrightarrow \mathbb{S}^7 \overset{p}{\longrightarrow} \mathbb{S}^4$ and $\mathbb{S}^7 \longrightarrow \mathbb{S}^{15} \overset{q}{\longrightarrow} \mathbb{S}^8$.

It can be shown (for example in Hatcher’s book, Algebraic topology, using a homological interpretation of Hopf invariant) that $H(p)=H(q)=1$, hence:

Theorem: $\pi_3(\mathbb{S}^2)$, $\pi_7(\mathbb{S}^4)$ and $\pi_{15}(\mathbb{S}^8)$ are infinite.

However, Hopf fibrations do not exist in other dimensions since a finite-dimensional real division algebra has dimension one, two, four or eight.

## Rado graph and 0-1 law for finite graphs

Given a set of vertices $X$, a random graph is given by deciding, independently with probability $1/2$, whether each unordered pair of vertices should be joined by an edge or not. Following Peter Cameron’s book, Permutation Groups, we prove here that there exists a countable graph $R$ (unique up to isomorphism) such that each random countable graph is isomorphic to $R$ with probability $1$. Moreover, we shall see that the existence of such a graph implies a 0-1 law for first-order properties of finite graphs.

Definition: We say that a graph $\Gamma$ has the property $\mathcal{P}$ if for all disjoint finite subsets of vertices $U,V$ there exists a vertex $z \notin U \cup V$ joined to every vertex of $U$ and to no vertex of $V$.

The two following lemmas show that, up to isomorphism, there exists only one countable graph satisfying property $\mathcal{P}$: the so-called Rado graph, denoted $R$.

Lemma 1: Two countable graphs satisfying property $\mathcal{P}$ are isomorphic.

Proof. Let $\Gamma_1, \Gamma_2$ be two countable graphs satisfying property $\mathcal{P}$. For convenience, let $(f_1,f_2, \dots)$ and $(g_1,g_2, \dots)$ be an enumeration of $\Gamma_1$ and $\Gamma_2$ respectively.

Let $\varphi_0 : \emptyset \to \Gamma_2$ be the empty morphism. Then, by induction:

1) If $n$ is odd: Let $f$ be the first vertex in the enumeration of $\Gamma_1$ not in the domain $S_{n-1}$ of $\varphi_{n-1}$. If $U$ (resp. $V$) denotes the set of vertices of $S_{n-1}$ joined (resp. not joined) to $f$ by an edge, according to property $\mathcal{P}$, there exists a vertex $z \notin \varphi_{n-1}(U) \cup \varphi_{n-1}(V) = \varphi_{n-1}(S_{n-1})$ joined by an edge to any vertex of $\varphi_{n-1}(U)$ and to no vertex of $\varphi_{n-1}(V)$. Therefore, $\varphi_{n-1}$ can be extended to $\varphi_n : S_{n-1} \cup \{f\} \to \Gamma_2$ by setting $\varphi_n(f)=z$.

2) If $n$ is even: Let $g$ be the first vertex in the enumeration of $\Gamma_2$ not in the range $R_{n-1}$ of $\varphi_{n-1}$. If $U$ (resp. $V$) denotes the set of vertices of $R_{n-1}$ joined (resp. not joined) to $g$ by an edge, according to property $\mathcal{P}$, there exists a vertex $z \notin \varphi_{n-1}^{-1}(V) \cup \varphi_{n-1}^{-1}(U)= \varphi_{n-1}^{-1}(R_{n-1})$ joined by an edge to any vertex of $\varphi_{n-1}^{-1}(U)$ and to no vertex of $\varphi_{n-1}^{-1}(V)$. Therefore, $\varphi_{n-1}$ can be extended to $\varphi_n : S_{n-1} \cup \{z\} \to R_{n-1} \cup \{g \}$ by setting $\varphi_n(z)=g$.

Finally, $\varphi := \bigcup\limits_{n \geq 0} \varphi_n$ defines an isomorphism between $\Gamma_1$ and $\Gamma_2$. $\square$

It is worth noticing that the previous proof gives an isomorphism as soon as $\varphi_0$ is an isomorphism between two subgraphs. Therefore, we have:

Property 1: $R$ is homogenous, ie. every isomorphism between two finite induced subgraphs can be extented to an automorphism of $R$.

Moreover, using only the first step of our induction, we have:

Property 2: $R$ is universal, ie. every at most countable graph is isomorphic to a subgraph of $R$.

In fact, it can be shown that $R$ is the only countable, universal and homogenous graph (up to isomorphism); see Peter Cameron’s book for more details.

Lemma 2: A countable random graph has property $\mathcal{P}$ with probability $1$.

Proof. Because there exist only countably many pairs of finite subsets of vertices $(U,V)$, it is sufficient to show that the event that the property $\mathcal{P}$ for $U$ and $V$ fixed fails has probability $p$ zero. But the probability that a point $z \notin U \cup V$ be joined by an edge to any vertex of $U$ and to no vertex of $V$ is $1/2^k$, where $k= |U \cup V|$. Therefore,

$\displaystyle p = \lim\limits_{n \to + \infty} \left( 1- \frac{1}{2^k} \right)^n =0$. $\square$

In particular, lemma 2 shows that there exists a countable graph satisfying property $\mathcal{P}$, justifying our definition of $R$. We deduce the following theorem from lemmas 1 and 2:

Theorem 1: A countable random graph is isomorphic to $R$ with probability $1$.

From now on, let us consider graph theory from model theory viewpoint, that is we view a graph as a model of the theory

$\mathcal{T}_{\text{graph}} = \left\{ \forall x, \neg (x \sim x) ; \forall x,y (x \sim y \Leftrightarrow y \sim x) \right\}$

over the langage $\mathcal{L}= \{ \sim, =\}$. Here, the relation $x \sim y$ means that the vertices $x$ and $y$ are joined by an edge; therefore, in $\mathcal{T}_{\text{graph}}$ the graphs are unoriented and do not contain loops. It is worth noticing that a graph satisfies property $\mathcal{P}$ if and only if it satisfies the first-order sentence

$\Phi_{m,n} = \forall x_1, \dots, x_m \forall y_1, \dots, y_n \exists z \Phi_{m,n} ( \overline{x} , \overline{y},z)$

for all $m,n \geq 1$, where

$\Phi_{mn} (\overline{x}, \overline{y},z) = \left[ \bigwedge\limits_{i,n} (x_i \neq y_j ) \Rightarrow \left( \bigwedge\limits_{i,j} (z \neq x_i,y_j ) \wedge \bigwedge\limits_i (z \sim x_i ) \wedge \bigwedge\limits_{j} \neg (z \sim y_j) \right) \right]$.

Therefore, $\mathcal{P}$ is a first-order property. We now are able to deduce a 0-1 law for finite graphs:

Definition: A property is true in almost all finite graphs if the proportion of graphs of cardinality $n$ satisfying the given property tends to $1$ as $n \to + \infty$.

Theorem 2: Let $\sigma$ be a sentence in the first-order langage of graph theory. If $R \models \sigma$ (resp. if $R \not\models \sigma$) then $\sigma$ is true (resp. false) in almost all finite graphs. In particular, a first-ordre sentence is either true in almost all finite graphs or false in almost all finite graphs.

Proof. Suppose that $R \models \sigma$. By our previous remark, the sentence $\sigma$ can be logically deduced from the sentences $\Phi_{m,n}$, ie. $\{\Phi_{m,n}, m,n \geq 1 \} \vdash \sigma$. Then, it is a consequence of compactness theorem that $\sigma$ can be logically deduced from only finitely many sentences $\Phi_{m,n}$. Therefore, it is sufficient to prove that each $\Phi_{m,n}$ fails in a random graph of cardinality $k$ with probability $p_k$ such that $p_k \underset{k \to + \infty}{\longrightarrow} 0$.

Clearly, $p_k$ is smaller than the product of the number of choices of a subset of $m+n$ vertices by the probability that the other vertices are not correctly joined (so that $\Phi_{m,n}$ be not satisfied), that is

$\displaystyle p_k \leq C_{k}^{m+n} \left( 1- \frac{1}{2^{m+n}} \right)^{k-m-n} \underset{k \to + \infty}{\longrightarrow} 0$.

If $R \not\models \sigma$, then $R \models \neg \sigma$ and $\neg \sigma$ is true in almost all finite graphs. $\square$

It can be unsatisfactory that we only give a non-constructive proof for the existence of $R$; to conclude, we give an explicit construction:

Let $\mathbb{N}$ be the set of vertices; two integers $n < m$ are joined by an edge if and only if the $n$-th digit (from right to left) of $m$, written in binary, is one. Then, the constructed graph has property $\mathcal{P}$: Let $U, V$ be two finite disjoint subsets of vertices and $p \geq 1$ be such that $2^p>x$ for all $x \in U \cup V$. Now, let $z$ be the binary number $\epsilon_p \cdots \epsilon_0$, where $\epsilon_p=1$, and for every $0 \leq i \leq p-1$, $\epsilon_i=1$ if $i \in U$ and $0$ otherwise (in particular, if $i \in V$). Then $z \notin U \cup V$ is joined by an edge to every vertex of $U$ and to no vertex of $V$.

## Hairy ball theorem without degree theory

Often, hairy ball theorem is mentioned as an application of degree theory derived from singular homology in algebraic topology or from de Rham cohomology in differential topology; we also mentionned it as an application of Brouwer’s degree in Brouwer’s Topological Degree (III): First Applications. Here we describe an argument due to Milnor, exposed in Gallot, Hullin and Lafontaine’s book Riemannian Geometry, using only integration of differential forms.

For convenience, we begin by exposing some basic definitions and first properties about integration on manifolds.

If $M$ is a smooth manifold, let $TM$ and $\Omega^k(M)$ denote respectively its tangent bundle and its space of differential forms of degree $k$ (ie. the vector space $\Gamma( \Lambda^k T^*M)$ of sections of the $k$-th extorior power of the cotangent bundle).  We say that $M$ is orientable if there exists an atlas $(U_i,\varphi_i)$, said oriented, such that $\varphi_i \circ \varphi_j^{-1}$ is orientation-preserving for all $i,j$.

Property: A smooth manifold $M$ is orientable if and only if there exists $\omega \in \Omega^n(M)$ satisfying $\omega_m \neq 0$ for all $m \in M$. Such a differential form is a volume form.

Sketch of proof. Let $\omega \in \Omega^n(M)$ be a volume form and let $(U_i,\varphi_i)$ be a family of charts covering $M$. Because $(\varphi_i)_* \omega_{|U_i} \in \Omega^n (\varphi_i(U_i))$ is a volume form, we can write

$(\varphi_i)_* \omega_{|U_i} = f_i ~ dx_1 \wedge \cdots \wedge dx_n$

where $f_i \in C(\varphi_i(U_i), \mathbb{R})$ does not vanish. Without loss of generality, we may suppose that $f_i > 0$ (otherwise, switch two coordinates of the chart). Then $(U_i, \varphi_i)$ is an oriented atlas.

Conversely, let $(U_i, \varphi_i)$ be an oriented atlas and $(\chi_i)$ be an associated partition of unity. Then

$\displaystyle \omega = \sum\limits_i \chi_i \varphi_i^* (dx_1 \wedge \cdots \wedge dx_n)$

is a volume form. $\square$

As an example, we may mention the differential form

$\displaystyle \omega = \sum\limits_{i=0}^n (-1)^i x^i dx_0 \wedge \cdots \wedge \widehat{dx_i} \wedge \cdots \wedge dx_n \in \Omega^n(\mathbb{R}^{n+1})$.

Then $\omega$ induces a volume form on $\mathbb{S}^n$ viewed as the unit sphere in $\mathbb{R}^{n+1}$. [In fact, $\omega$ is the canonical volum form of $\mathbb{S}^n$ as a Riemannian manifold. In particular, we define $\displaystyle \mathrm{Vol}(\mathbb{S}^n) = \int_{\mathbb{S}^n} \omega$.]

An interesting property of volum forms is that, if $\omega \in \Omega^n(M)$ is a volume form and $\alpha \in \Omega^n(M)$, then there exists $f \in C(M, \mathbb{R})$ such that $\alpha= f \omega$. It is clear locally, and then it is sufficient to extend it globally using a partition of unity.

Definition: Let $M$ be an orientable compact $n$-dimensional smooth manifold. There exists one and only one linear map $\int_{M} : \Omega^n(M) \to \mathbb{R}$ such that for every $\omega \in \Omega^n(M)$ supported in an open chart $(U,\varphi)$,

$\displaystyle \int_M \alpha = \int_{\varphi(U)} (\varphi^{-1})^* \alpha$.

[Where the right-hand side is the usual integral of a differential form defined on an open subspace in $\mathbb{R}^n$.]

Sketch of proof. First, suppose that such a linear map exists. Let $(U_i, \varphi_i)$ be a finite family of charts covering $M$ (such a family exists by compactness) and $(\chi_i)$ be an associated partition of unity. Then necessarily:

$\displaystyle \int_M \omega= \int_M \sum\limits_{i} \chi_i \omega_{|U_i} = \sum\limits_{i} \int_M \chi_i \omega_{|U_i} = \sum\limits_{i} \int_{\varphi(U_i)} (\varphi_i^{-1})^* \chi_i \omega_{|U_i}$,

hence $\int_M$ is uniquely defined by the mentionned properties. Conversely, it is sufficient to show that the above equality does not depend on the family of charts and on the partition of unity chosen. An argument for that is to notice that if $\varphi : U \to V$ is a diffeomorphism between two open subsets $U,V \subset \mathbb{R}^n$, and $\omega \in \Omega^n(\mathbb{R}^n)$, then

$\displaystyle \int_U \varphi^* \omega= \epsilon \int_V \omega$,

where $\epsilon=1$ if $\varphi$ is orientation-preserving and $-1$ otherwise. We can write $\omega= f dx_1 \wedge \cdots \wedge dx_n$ for some $f \in C(M, \mathbb{R})$, and

$\begin{array}{lcl} \displaystyle \int_U \varphi^* \omega & = & \displaystyle \int_U f \circ \varphi ~ \varphi^* (dx_1 \wedge \cdots \wedge dx_n) \\ \\ & = & \displaystyle \int_U f \circ \varphi ~ \mathrm{Jac} (\varphi) ~ dx_1 \wedge \cdots \wedge dx_n \\ \\ & = & \displaystyle \epsilon \int_U f \circ \varphi ~ | \mathrm{Jac} ( \varphi ) | ~ dx_1 \wedge \cdots \wedge dx_n \\ \\ & = & \displaystyle \epsilon \int_{\varphi(U)} f = \epsilon \int_V \omega \hspace{1cm} \square \end{array}$

Using the proof above, we may notice:

Property: Let $M,N$ be two compact orientable $n$-dimensional smooth manifolds and $\omega \in \Omega^n(N)$. If $f : M \to N$ is a diffeomorphism then

$\displaystyle \int_N \omega= \epsilon \int_M f^*\omega$,

where $\epsilon=1$ if $f$ is orientation-preserving and $\epsilon=-1$ otherwise.

Theorem: (Hairy ball theorem) If $n$ is even, any continuous vector field on $\mathbb{S}^n$ has a zero.

Proof. Let $X$ be a continuous vector field on $\mathbb{S}^n$, that is $X : \mathbb{S}^n \to \mathbb{R}^{n+1}$ is a map satisfying $X(p) \cdot p =0$ for every $p \in \mathbb{S}^n$. By contradiction, suppose that $X$ does not vanish.

According to Stone-Weierstrass theorem, it is possible to approximate $X$ by a sequence of smooth maps $X_k : \mathbb{S}^n \to \mathbb{R}^{n+1}$. Then, if $X_k(p)^{\top}$ denotes the orthogonal projection of $X_k(p)$ on $T_p \mathbb{S}^n$, $X_k^{\top}$ is a sequence of smooth vector fields on $\mathbb{S}^n$ converging uniformely to $X$. Therefore, we may suppose without loss of generality that $X$ is smooth.

[Such an argument may be generalized to other manifolds; see Tubular neighborhood.]

Let $\omega \in \Omega^n(\mathbb{S}^n)$ be the volume form as defined above by the restriction on $\mathbb{S}^n$ of

$\displaystyle \omega = \sum\limits_{i=0}^n (-1)^i x^i \underset{ := \omega_i }{ \underbrace{ dx_0 \wedge \cdots \wedge \widehat{dx_i} \wedge \cdots \wedge dx_n }} \in \Omega^n ( \mathbb{R}^{n+1})$

and let $f_{\epsilon} : S(1) \to S( \sqrt{1+\epsilon^2}), \ x \mapsto x + \epsilon X(x)$. For every $p \in S(1)$ and $v_0, \dots, v_n \in \mathbb{R}^{n+1}$, we may write

$\begin{array}{lcl} ( f_{\epsilon}^* \omega)_p(v_0, \dots, v_n) & = & \sum\limits_{i=0}^n (-1)^i (p^i+ \epsilon X(p)^i) \omega_i (v_0+ \epsilon dX(p) \cdot v_0, \dots, v_n+ \epsilon dX(p) \cdot v_n) \\ & = & \sum\limits_{i=0}^n \sum\limits_{k=0}^{n+1} (-1)^i (p^i+ \epsilon X(p)^i) \epsilon^k \omega_{ik} (v_0, \dots, v_n) \end{array}$

where $\omega_{ik} \in \Omega^n(\mathbb{R}^{n+1})$ is such that $\omega_{i0}=\omega_i$ and $\omega_{ik}(v_0, \dots, v_n)= \omega_i (\tilde{v_0}, \dots, \tilde{v_n})$ with $\tilde{v_j} = v_j$ or $dX(p) \cdot v_j$. Therefore, there exist $\alpha_k \in \Omega^n (\mathbb{R}^{n+1})$ such that

$\displaystyle f_{\epsilon}^* \omega= \omega+ \sum\limits_{k=1}^{n+2} \epsilon^k \alpha_k \hspace{1cm} (1)$.

First, let us show how conclude the proof if $f_{\epsilon}$ is a diffeomorphism:

Let $r= \sqrt{1+ \epsilon^2}$ for convenience, $\psi : x \mapsto rx$ be a diffeomorphism from $S(1)$ to $S(r)$ and  as mentioned above $\displaystyle \mathrm{Vol}(\mathbb{S}^n)= \int_{\mathbb{S}^n} \omega$. Then

$\displaystyle \mathrm{Vol}(\mathbb{S}^n) (1+ \epsilon^2)^{\frac{n+1}{2}} = r^{n+1} \int_{\mathbb{S}^n} \omega = \int_{S(1)} \psi^* \omega= \int_{S(r)} \omega= \int_{S(1)} f_{\epsilon}^* \omega$,

so according to $(1)$, the expression $\displaystyle (1+\epsilon^2)^{\frac{n+1}{2}}$ is a polynomial in $\epsilon$. Of course, it is only possible when $n$ is odd.

To conclude the proof, we shall see that $f_{\epsilon}$ is a diffeomorphism when $\epsilon$ is sufficiently small. From $(1)$, if $g_k \in C(\mathbb{S}^n,\mathbb{R})$ is such that $\alpha_k = g_k \omega$,

$\displaystyle f_{\epsilon}^* \omega= \left( 1+ \sum\limits_{k=1}^{n+1} \epsilon^k g_k \right) \omega$.

By compactness, the $g_k$ are bounded so the quantity $1+ \sum\limits_{k=1}^{n+1} \epsilon^k g_k$ does not vanish when $\epsilon$ is small enough. Therefore, $f_{\epsilon}^*\omega$ is a volume form and $f_{\epsilon}$ is an immersion.

Moreover, if $f_{\epsilon}$ were not injective for $\epsilon$ small enough, there would exist sequences $(\epsilon_k)$, $(x_k)$ and $(y_k)$ such that $\epsilon_k \to 0$, $x_k \neq y_k$ and $f_{\epsilon_k}(x_k)= f_{\epsilon_k}(y_k)$, hence

$\displaystyle \frac{x_k-y_k}{\| x_k-y_k \|} = - \epsilon_k \frac{X(x_k)-X(y_k)}{ \| x_k-y_k \| }$.

The first term has norm one, $\epsilon_k \to 0$ and the last term is bounded according to mean value theorem: a contradiction.

Therefore, for $\epsilon$ small enough, $f_{\epsilon}$ is an injective immersion, and consequently a local diffeomorphism according to inverse function theorem. In particular, $\mathrm{Im}(f_{\epsilon})$ is open but also closed by compactness of $S(1)$; by connectedness, $\mathrm{Im}(f_{\epsilon})= S(r)$ and $f_{\epsilon}$ is a diffeomorphism. $\square$

## A short proof of Cantor–Bernstein–Schroeder theorem

We present here a short proof of Cantor-Berstein-Schroeder theorem based on a fixed-point argument, probably not known enough; this proof is less explicit that the usual one, but it is worth noticing that it does not depend on the axiom of choice.

As a lemma, we first prove a particular case of Knaster-Tarski fixed point theorem:

Theorem: (Tarski) Let $A$ be a set and $f : \mathfrak{P}(A) \to \mathfrak{P}(A)$ be a nondecreasing function (ie. such that $X \subset Y \Rightarrow f(X) \subset f(Y)$ for all $X,Y \in \mathfrak{P}(A)$). Then $f$ has a fixed point.

Proof. Let $C= \{ X \in \mathfrak{P}(A) \mid X \subset f(X) \}$ and $F= \bigcup\limits_{X \in C} X \in \mathfrak{P}(A)$.

Notice that for all $X \in C$, $X \subset f(X) \subset f(F)$, hence $F \subset f(F) \ (1)$.

Moreover, $(1)$ implies $f(F) \subset f(f(F))$ ie. $f(F) \in C$, so $f(F) \subset F \ (2)$.

We deduce that $F$ is a fixed point of $f$ from $(1)$ and $(2)$, and the theorem follows. $\square$

Theorem: (Cantor-Bernstein-Schroeder) Let $A,B$ be two sets. Suppose that there exist two injections $f : A \hookrightarrow B$ and $g : B \hookrightarrow A$. Then there exists a bijection $A \overset{\sim}{\to} B$.

Proof. First, we define the map

$\Phi : \left\{ \begin{array}{ccc} \mathfrak{P}(A) & \to & \mathfrak{P}(A) \\ X & \mapsto & g( B \backslash f(A \backslash X)) \end{array} \right.$.

Easily, we see that $\Phi$ is nondecreasing, so $\Phi$ has a fixed point $X$ according to Tarski’s theorem. Now notice that

$A = X \coprod (A \backslash X) \ \text{and} \ B= ( B \backslash f(A \backslash X)) \coprod f(A \backslash X)$,

and that $g$ induces a bijection $B \backslash f(A \backslash X) \overset{\sim}{\to} g( B \backslash f(A \backslash X)) = \Phi(X)=X$ and $f$ induces a bijection $A \backslash X \overset{\sim}{\to} f(A \backslash X)$. Therefore, $A$ and $B$ are equipotent. By the way, an explicit bijection from $A$ to $B$ is given by

$x \mapsto \left\{ \begin{array}{cl} f(x) & \text{if} \ x \in X \\ g^{-1}(x) & \text{if} \ x \notin X \end{array} \right. . \hspace{1cm} \square$

## Weak Tarski’s problem: Groups having the same universal theory as a free group

In 1945, Alfred Tarski asked the question:

Let $G$ be a group. How to determine the groups elementarily equivalent to $G$?

We answered the question when $G$ is a divisible group in the previous note Elementary Theories of Divisible Groups. However, Tarski’s problem seemed to be dramatically difficult when $G$ is a free group; in particular, it was not known wether two non-abelian free groups of finite rank were elementarily equivalent.

Some partial results have been showed in the last half of the twentieth century, but the first complete answer was given by Z. Sela between 2001 and 2006 in a series of papers untitled Diophantine Geometry over Groups. Of course, because of its complexity, it is not possible to describe the solution here: we restrict ourself to the weaker problem

How to describe the finitely generated groups having the same universal theory as a free group of finite rank?

The solution described here is based on the paper Limit groups as limits of free groups by C. Champetier and V. Guirardel, simplifying an argument of Z. Sela. Another argument, without using the space of marked groups, can be found in Chiswell’s book, Introduction to $\Lambda$-trees.

First, notice that $\mathrm{Th}_{\forall}(\mathbb{F}_n)= \mathrm{Th}_{\forall} (\mathbb{F}_m)$ for all $n,m \geq 2$. It is a consequence of our previous note A free group contains a free group of any rank, showing that $\mathbb{F}_n \hookrightarrow \mathbb{F}_m$ and $\mathbb{F}_m \hookrightarrow \mathbb{F}_n$. So the problem becomes

How to describe the finitely generated groups $G$ satisfying $\mathrm{Th}_{\forall}(G)= \mathrm{Th}_{\forall} (\mathbb{F}_2)$ or $\mathrm{Th}_{\forall}(G)= \mathrm{Th}_{\forall} (\mathbb{Z})$?

The space of marked groups has already been defined in our previous note Cantor-Bendixson rank in group theory. The link between universal theories and the space of marked groups is made explicit by the following lemma:

Lemma 1: Let $(H_i,R_i)$ be a sequence of marked groups converging to $(G,S)$. Then

$\limsup\limits_{i \to + \infty} \mathrm{Th}_{\forall}(H_i) \subset \mathrm{Th}_{\forall}(G)$.

Conversely, if $G$ and $H$ are two finitely generated groups satisfying $\mathrm{Th}_{\forall} (H) \subset \mathrm{Th}_{\forall} (G)$ then, for every marking $S$, $(G,S)$ is the limit of $(H,R_i)$ for some markings $R_i$.

Proof. Let $(H_i,R_i)$ be a sequence of marked groups converging to $(G,S)$ and let $\sigma \notin \mathrm{Th}_{\forall} (G)$ be a universal formula. Then $\neg \sigma \in \mathrm{Th}_{\exists} (G)$ and we may write

$\neg \sigma = \exists x_1, \dots , x_m \Sigma(x_1, \dots, x_m)$,

where $\Sigma$ is a system of equations and inequations. In particular, there exist $g_1, \dots, g_m \in G$ such that $G \models \Sigma(g_1, \dots, g_m)$. For all $1 \leq i \leq m$, let $w_i$ be a word so that $g_i=w_i(S)$ in $G$.

Because $G \models \Sigma(w_1(S),\dots, w_m(S))$, we deduce that for all but finitely many $i$

$H_i \models \Sigma(w_1(R_i),\dots, w_m(R_i))$,

ie. $\neg \sigma \in \mathrm{Th}_{\exists}(H_i)$ or $\sigma \notin \mathrm{Th}_{\forall} (H_i)$. Thus, $\sigma \notin \limsup\limits_{i \to + \infty} \mathrm{Th}_{\forall} (H_i)$.

Let $G$, $H$ be two finitely generated groups satisfying $\mathrm{Th}_{\forall} (H) \subset \mathrm{Th}_{\forall} (G)$ and let $S$ be a marking of $G$. Let $\{w_i \mid i \in I\}$ be the set of reduced words of length at most $n$ over an alphabet of size $|S|=m$.

With $J= \{i \in I \mid G \models (w_i(S)=1) \}$ and $K= \{ i \in I \mid G \models (w_i(S) \neq 1) \}$ (in particular, $I= J \coprod K$), let $\Sigma(x_1,\dots, x_m)$ be the system

$\{ w_j(x_1, \dots, x_m)=1 \mid j \in J \} \cup \{ w_k(x_1,\dots, x_m) \neq 1 \mid k \in k \}$.

Then $\exists x_1, \dots, x_m \Sigma(x_1, \dots, x_m) \in \mathrm{Th}_{\exists}(G) \subset \mathrm{Th}_{\exists}(H)$ so there exist $h_1,\dots, h_m \in H$ such that $H \models \Sigma(h_1, \dots, h_m)$. Finally, with $R_n= (h_1, \dots, h_m)$, $d((H,R_n),(G,S)) \leq e^{-n}$ by construction hence $(H,R_n) \underset{n \to + \infty}{\longrightarrow} (G,S)$. $\square$

The lemma above justifies the following family of groups as a possible solution of our weak Tarski’s problem:

Definition: A finitely generated group $G$ is a limit group if there exists a marking $S$ such that $(G,S)$ is a limit of marked free groups.

We first notice that the property does not depend on the marking $S$, so that being a limit group becomes an algebraic property:

Lemma 2: Let $(H_i,R_i)$ be a sequence of marked groups converging to $(G,S)$ and let $\tilde{S}$ be a marking of $G$. Then $(G, \tilde{S})$ is the limit of $(H_i,\tilde{R}_i)$ for some marking $\tilde{R}_i$ of $H_i$.

Proof. Let $\tilde{S} = (\tilde{s}_1, \dots, \tilde{s}_m)$. Then for each $1 \leq i \leq m$, there exists a word $w_i$ such that $\tilde{s}_i=w_i(S)$. Let $\tilde{r}_{in} = w_i(R_n)$ and $\tilde{R}_n= (\tilde{r}_{1n} , \dots, \tilde{r}_{mn})$.

Notice that for any word $w$$w(\tilde{s}_1, \dots, \tilde{s}_m)=w(w_1(S), \dots, w_m(S))$, so $w(\tilde{S})=1$ in $G$ if and only if $w(\tilde{R}_n)= w(w_1(R_n), \dots, w_m(R_n))=1$ in $H_n$ for all but finitely many $n$ (because $(H_n, R_n)$ converges to $(G,S)$). Therefore, $(H_n, \tilde{R}_n)$ converges to $(G,\tilde{S})$. $\square$

In particular, lemma 1 solves (weak) Tarski’s problem for $\mathbb{Z}^m$:

Corollary: A finitely generated group $G$ has the same universal theory as $\mathbb{Z}$ if and only if it is isomorphic to $\mathbb{Z}^n$ for some $n \geq 1$.

Proof. If $G$ has the same universal theory as $\mathbb{Z}$ then $G$ is a finitely generated torsion-free abelian group, so it is isomorphic to a free abelian group of finite rank. Conversely, it is sufficient to show that $\mathbb{Z}$ and $\mathbb{Z}^m$ have the same universal theory for every $m \geq 1$.

Because $\mathbb{Z} \subset \mathbb{Z}^n$, $\mathrm{Th}_{\forall} (\mathbb{Z}^n) \subset \mathrm{Th}_{\forall}(\mathbb{Z})$. Conversely, according to lemma 1, it is sufficient to notice that $(\mathbb{Z}^m, \mathrm{can})$ (where $\mathrm{can}= \left( (1,0, \dots, 0),(0,1,\dots,0), \dots, (0,0, \dots, 1) \right)$ is the canonical marking) is the limit of $(\mathbb{Z}, S_n)$ where $S_n= \{ 1, 2^{2n}, 2^{3n}, \dots, 2^{mn} \}$. More precisely, it can be shown that $d((\mathbb{Z},S_n),(\mathbb{Z}^m, \mathrm{can})) \leq e^{1- 2^n}$. $\square$

Corollary: Let $G$ be a finitely generated group and $m \geq 1$. Then $G$ and $\mathbb{Z}^m$ are elementarily equivalent if and only if they are isomorphic.

Proof. Let $\{ w_i \mid i \in I\}$ be the set of words of the form $x_1^{\epsilon_1} \cdots x_m^{\epsilon_m}$ with $\epsilon_i \in \{ 0,1 \}$ and

$\sigma_m = \exists x_1,\dots,x_m \forall x \exists y \left( \bigvee\limits_{i \in I} x = 2y+ w_i(x_1, \dots,x_m) \right)$.

Then $\mathbb{Z}^n \models \sigma_m$ is equivalent to $| \mathbb{Z}^n / 2 \mathbb{Z}^n | \leq 2^m$, ie. $n \leq m$. Therefore, $\mathbb{Z}^n$ and $\mathbb{Z}^m$ are elementarily equivalent if and only if $n=m$. Finally, we conclude using the previous corollary. $\square$

Now, we may prove that limit groups actually solve weak Tarski’s problem:

Theorem 1: Let $G$ be a finitely generated group. Then $G$ has the same universal theory as $\mathbb{F}_2$ or $\mathbb{Z}$ if and only if $G$ is an limit group.

Lemma 3: Let $(H_i,R_i)$ be a sequence of marked groups converging to $(G,S)$, $K \subset G$ be a subgroup and $T$ be a marking of $K$. Then there exist subgroups $F_i \subset H_i$ and markings $Q_i$ of $F_i$ such that $(F_i, Q_i)$ converges to $(K,T)$.

Proof. Let $T= (t_1, \dots, t_m)$. In particular, for all $1 \leq k \leq m$, there exists a word $w_k$ such that $t_k=w_k(S)$. Let $h_{ik}=w_k(R_i)$, $F_i= \langle h_{i1}, \dots, h_{im} \rangle \leq H_i$ and $Q_i=(h_{i1}, \dots, h_{im} )$. Then for any word $w$:

$w(T)=1 \ \text{in} \ K \Leftrightarrow w(w_1(S), \dots, w_m(S))=1 \ \text{in} \ G \\ \\ \hspace{1cm} \Leftrightarrow w(w_1(R_i), \dots, w_m(R_i)) = 1 \ \text{in} \ H_i \ \text{for all but finitely many} \ i \\ \\ \hspace{1cm} \Leftrightarrow w(Q_i)=1 \ \text{in} \ F_i \ \text{for all but finitely many} \ i$

Therefore, $(F_i,Q_i)$ converges to $(K,T)$. $\square$

Lemma 4: A non-abelian $2$-generator subgroup of a limit group is isomorphic to $\mathbb{F}_2$.

Proof. Let $G$ be a limit group and let $a,b \in G \backslash \{1\}$. Using lemma 3, we deduce that $\langle a,b \rangle$ is a limit group, and using lemma 2, we deduce that there exist free groups $F_k$ and markings $(e_k,f_k)$ such that $(F_k,(e_k,f_k))$ converges to $(\langle a,b \rangle, (a,b))$.

If $\langle a,b \rangle$ were not free over $\{a,b\}$, there would exist a non-trivial relation $w(a,b)=1$ in $G$. In particular, $w(e_k,f_k)=1$ in $F_k$ for all but finitely many $k$, so $\mathrm{rank}(F_k) < 2$. Therefore, $(\langle a,b \rangle, (a,b))$ would be the limit of abelian marked groups that is $\langle a,b \rangle$ would be abelian itself: a contradiction. $\square$

Proof of theorem 1. The case where $G$ is abelian is clear according to our previous corollaries. If $\mathrm{Th}_{\forall} (G)= \mathrm{Th}_{\forall}(\mathbb{F}_2)$, then $G$ is a limit group according to lemma 1. Conversely, suppose that $G$ is a limit group. According to lemma 1, $\mathrm{Th}_{\forall} (\mathbb{F}_2) \subset \mathrm{Th}_{\forall} (G)$. Moreover, if $a,b \in G$ do not commute, $\langle a,b \rangle \simeq \mathbb{F}_2$ according to lemma 4 hence $\mathrm{Th}_{\forall} (G) \subset \mathrm{Th}_{\forall} (\mathbb{F}_2)$. $\square$

Because of Los’ theorem, a natural way to “construct” a limit group is the following: Let $\mathbb{F}_n$ be a free group of finite rank $n \geq 2$ and let $\omega$ be a non-principal ultrafilter over $\mathbb{N}$. Then the ultrapower $\mathbb{F}_n^{\omega}$ is elementarily equivalent to $\mathbb{F}_n$; therefore, any finitely generated subgroup $L \subset \mathbb{F}_n^{\omega}$ is a limit group since $\mathrm{Th}_{\forall} ( \mathbb{F}_n) = \mathrm{Th}_{\forall} \left( \mathbb{F}_n^{\omega} \right) \subset \mathrm{Th}_{\forall} (L)$ and using lemma 1.

In fact, the converse is also true:

Theorem 2: A finitely generated group is a limit group if and only if it embeds into an ultrapower of a free group of finite rank.

Notice that it is sufficient to consider the ultrapowers $\mathbb{F}_2^{\omega}$ where $\omega$ is non-principal. Our theorem is an easy consequence of the following lemma:

Lemma 5: Let $(H_k,R_k)$ be a sequence of marked groups converging to $(G,S)$. Then for all non-principal ultrafilter $\omega$, $G$ embeds into the ultraproduct $\prod\limits_{k \geq 1} H_k / \omega$. Conversely, if $G$ is a finitely generated subgroup of an ultraproduct $\prod\limits_{k \geq 1} G_k / \omega$ (where $\omega$ is non-principal), then for every marking $S$ of $G$, there exist an increasing sequence $(i_k)$, subgroups $H_{i_k} \subset G_{i_k}$, markings $R_{i_k}$ of $H_{i_k}$ such that $(H_{i_k},R_{ik})$ converges to $(G,S)$.

Proof. Let $(H_k,R_k)$ be a sequence of marked groups converging to $(G,S)$. Notice that for any words $w_1$ and $w_2$, if $w_1(S)=w_2(S)$ then $w_1(R_k)=w_2(R_k)$ for all but finitely many $k$ hence $(w_1(R_k))=(w_2(R_k))$ in $\prod\limits_{k \geq 1} H_k / \omega$. Therefore, the morphism

$\varphi : \left\{ \begin{array}{ccc} G & \to & \prod\limits_{k \geq 1} H_k / \omega \\ w(S) & \mapsto & (w(R_k)) \end{array} \right.$ for any word $w$

is well-defined. Let $w(S) \in \mathrm{ker}(\varphi)$. Then $\{k \geq 1 \mid w(R_k)=1 \}$ belongs to $\omega$ and is infinite in particular, so there exists $k$ arbitrarily large such that $w(R_k)=1$ in $H_k$, hence $w(S)=1$. Therefore, $\varphi$ is an embedding.

Let $G$ be a finitely generated subgroup of an ultraproduct $\prod\limits_{k \geq 1} H_k / \omega$ and let $S$ be a marking of $G$. Let $S=(s_1, \dots, s_m)$ where $s_i=(r_{ik})$. Set $H_k= \langle r_{1k}, \dots, r_{mk} \rangle \leq G_k$ and $R_k= (r_{1k}, \dots, r_{mk} )$.

Now notice that $\bigcap\limits_{ \ell g(w) \leq n} \{ k \geq 1 \mid w(R_k)=1 \Leftrightarrow w(S)=1 \}$ belongs to $\omega$ and in particular is infinite. Therefore, there exists $p$ arbitrarily large such that $d((H_p,R_p),(G,S)) \leq e^{-n}$. We deduce that the sequence $(i_k)$ can be easily constructed by induction. $\square$

Finally, a purely algebraic characterization of limit groups can be stated:

Definition: A group $G$ is fully residually free if for every finite set $S \subset G \backslash \{1\}$ there exists a morphism $\varphi$ from $G$ to a free group $F$ such that $\varphi(g) \neq 1$ for all $g\in S$.

Theorem 3: A finitely generated group $G$ is a limit group if and only if it is fully residually free.

Lemma 6: Let $\omega$ be a non-principal ultrafilter and let $R$ be a finitely generated subring of $\mathbb{Z}^{\omega}$. Then $R$ is fully residually $\mathbb{Z}$, that is for every finite subset $S \subset R \backslash \{0\}$ there exists a ring homomorphism $\rho : R \to \mathbb{Z}$ such that $\rho(s) \neq 0$ for all $s \in S$.

Proof. Because $R$ is finitely generated, there exist $t_1, \dots, t_n \in \mathbb{Z}^{\omega}$ such that $R= \mathbb{Z} [t_1, \dots, t_n]$. Let $\mathbb{Z}[T_1, \dots, T_n ]$ denote the ring of $n$-variable polynomials and let

$\varphi : \mathbb{Z}[T_1, \dots, T_n] \twoheadrightarrow \mathbb{Z} [t_1, \dots, T_n] = R$

be the canonical projection. Because $\mathbb{Z} [T_1, \dots, T_n]$ is noetherian, $\mathrm{ker}(\varphi)$ is generated by finitely many elements $f_1, \dots, f_s \in \mathbb{Z}[T_1, \dots, T_n]$.

Let $r_1, \dots, r_m \in R \backslash \{0\}$ and $g_1, \dots, g_m \in \mathbb{Z}[T_1, \dots, T_n]$ such that $\varphi(g_i)=r_i$ for all $1 \leq i \leq m$. Then

$\left\{ \begin{array}{ll} f_i(t_1, \dots, t_n)=0, & 1 \leq i \leq s \\ g_i(t_1, \dots,t_n ) \neq 0, & 1 \leq i \leq m \end{array} \right.$

Therefore, for all $1 \leq i \leq s$ (resp. $1 \leq i \leq m$) and for $\omega$-almost all $k$, $f_i(t_{1k}, \dots,t_{nk})=0$ (resp. $g_i(t_{1k}, \dots, t_{nk}) \neq 0$). Thus, there exist $x_1, \dots, x_n \in \mathbb{Z}$ such that

$\left\{ \begin{array}{ll} f_i(x_1, \dots, x_n)=0, & 1 \leq i \leq s \\ g_i(x_1, \dots,x_n ) \neq 0, & 1 \leq i \leq m \end{array} \right.$

Now let $\phi : \mathbb{Z}[T_1, \dots, T_n] \to \mathbb{Z}$ be the only morphism satisfying $\phi(T_i)=x_i$ for all $i$. Because $f_i(x_1, \dots, x_n)=0$ for all $i$, $\phi$ induces a morphism $\overline{\phi} : R \to \mathbb{Z}$. Because $g_i(x_1, \dots, x_n) \neq 0$ for all $i$, $\overline{\phi}(r_i)= \phi(g_i) \neq 0$ for all $i$.

We deduce that $R$ is fully residually $\mathbb{Z}$. $\square$

Proof of theorem 3. Suppose that $G$ is fully residually free. Let $X$ be a finite generator set and let $G_n \subset G \backslash \{1\}$ be the set of non-trivial elements of length at most $n$ over $X$. For all $n$, let $\phi_n$ be a morphism from $G$ to a free group $F_n$ such that $\phi_n(g) \neq 1$ for all $g \in G_n$. Finally, let the morphism

$\varphi : \left\{ \begin{array}{ccc} G & \to & \prod\limits_{n \geq 1} F_n / \omega \\ g & \mapsto & (\phi_n(g)) \end{array} \right.$,

where $\omega$ is a non-principal ultrafilter. Let $g \in G$ such that $\ell g(g)=m \geq 1$. Then $g \in \bigcap\limits_{n \geq m} G_n$ so $\phi_n(g) \neq 1$ for all $n \geq m$. Thus, $\{n \geq 1 \mid \phi_n(g) \neq 1 \} \in \omega$ ie. $\varphi(g) \neq 1$. Therefore, $\varphi$ is injective and $G$ is a limit group according to theorem 2.

Conversely, suppose that $G$ is a limit group. According to theorem 2, there exists a non-principal ultrafilter $\omega$ such that $G \hookrightarrow \mathbb{F}_2^{\omega}$. The canonical projection $\mathbb{Z} \twoheadrightarrow \mathbb{Z}_p$ induces a morphism $\varphi : SL_2(\mathbb{Z}) \to SL_2(\mathbb{Z}_p)$. Then the modular group $\Gamma_p = \mathrm{ker}(\varphi)$ is a non-abelian free group.

(This fact is shown in Serre’s book, Trees. The idea is to notice that $SL_2(\mathbb{Z})$ acts on a tree in the hyperbolic plane, to deduce that $SL_2(\mathbb{Z}) \simeq \mathbb{Z}_4 \underset{\mathbb{Z}_2}{\ast} \mathbb{Z}_6$ and finally to show that a subgroup of $SL_2(\mathbb{Z})$ is free if and only if it is torsion-free.)

Thus, if $\varphi^* : SL_2(\mathbb{Z}^{\omega}) \to SL_2(\mathbb{Z}_p^{\omega})$ is induced by the canonical projection $\mathbb{Z}^{\omega} \twoheadrightarrow \mathbb{Z}_p^{\omega}$,

$G \hookrightarrow \mathbb{F}_2^{\omega} \hookrightarrow \Gamma_p^{\omega} \simeq \mathrm{ker}(\varphi^*)$.

Therefore, we may suppose without loss of generality that $G$ is a subgroup of $SL_2(\mathbb{Z}^{\omega})$. Moreover, because $G$ is finitely generated, there exists a finitely generated subring $R$ of $\mathbb{Z}^{\omega}$ such that $G \leq SL_2(R)$.

Let $g_1, \dots, g_n \in G \backslash \{1\}$ and let $a_1, \dots, a_r \in R$ denote the non-zero coefficients of the matrices $g_i - \mathrm{Id}$. According to lemma 6, there exists a ring homomorphism $\rho : R \to \mathbb{Z}$ such that $\rho(a_i) \neq 0$ for all $i$. In particular, $\rho$ induces a ring homomorphism $\overline{\rho} : SL_2(R) \to SL_2(\mathbb{Z})$.

Noticing that $\rho(G) \subset \Gamma_p$ since $G \subset \mathrm{ker}(\varphi^*)$ and that $\rho(g_i) \neq \mathrm{Id}$, we deduce that $G$ is fully residually free. $\square$

Finally, we proved:

Theorem A: Let $G$ be a finitely generated group. Then the following statements are equivalent:

1. $G$ is an abelian limit group,
2. $G$ has the same universal theory as $\mathbb{Z}$,
3. $G$ is abelian and embeds into an ultrapower $\mathbb{F}_2^{\omega}$,
4. $G$ is abelian and fully residually free,
5. $G$ is isomorphic to $\mathbb{Z}^n$ for some $n\geq 1$.

Theorem B: Let $G$ be a finitely generated group. Then the following statements are equivalent:

1. $G$ is a non-abelian limit group,
2. $G$ has the same universal theory as $\mathbb{F}_2$,
3. $G$ embeds into an ultrapower $\mathbb{F}_2^{\omega}$,
4. $G$ is non-abelian and fully residually free.

From theorems A and B, we may deduce the following properties of limit groups:

Property 1: The following statements hold:

1. A limit group is torsion-free,
2. A limit group is commutative-transitive (ie. if $y \neq 1$ commute with $x$ and $z$, then $x$ and $y$ commute),
3. A limit group is residually finite,
4. A finitely-generated subgroup of a limit group is a limit group,
5. A non-trivial $2$-generator subgroup of a limit group is isomorphic to either $\mathbb{Z}$, $\mathbb{Z}^2$ or $\mathbb{F}_2$,
6. Let $G_1, \dots, G_n$ be finitely generated groups. Then $G_1 \ast \cdots \ast G_n$ is a limit group if and only if $G_1, \dots, G_n$ are limit groups.

We also have the following property as a consequence of lemma 7:

Property 2: A limit group (and more generally, any residually free group) is hopfian.

Lemma 7: Let $G_1 \overset{\varphi_1}{\twoheadrightarrow} G_2 \overset{\varphi_2}{\twoheadrightarrow} G_3 \overset{\varphi_2}{\twoheadrightarrow} \dots$ be a sequence of epimorphisms between finitely generated residually free groups. Then all but finitely many epimorphisms are isomorphisms.

Indeed, if $\varphi : G \to G$ is an epimorphism but not an isomorphism (where $G$ is finitely generated and residually free), then the sequence $G \overset{\varphi}{\twoheadrightarrow} G \overset{\varphi}{\twoheadrightarrow} G \overset{\varphi}{\twoheadrightarrow} \dots$ contradicts the lemma.

Proof: Let $S_1=(s_1^{(1)}, \dots, s_n^{(1)})$ be a generator set of $G_1$; then $S_k:= \varphi_k(S_1)= (s_1^{(k)}, \dots, s_n^{(k)})$ is a generator set of $G_k$ by surjectivity of $\varphi_k$. Let $V_k$ be the set of $(M_1, \dots, M_n) \in SL_2(\mathbb{C})^n$ such that $r(M_1, \dots, M_n)= \mathrm{Id}$ for every relation $r$ of $G_k$.

Notice that $V_k$ is an affine algebraic variety in $\mathbb{C}^{4n}$ and $V_1 \supset V_2 \supset \cdots$, so the sequence $(V_k)$ is eventually constant. To conclude, it is sufficient to show that if $\varphi_k : G_k \to G_{k+1}$ is not an isomorphism, then $V_{k+1} \subsetneq V_k$.

Let $r$ be a word such that $r(S_{k+1})=1$ in $G_{k+1}$ but $r(S_k) \neq 1$ in $G_k$. $G_k$ being residually free, there exists a morphism $\rho : G_k \to \mathbb{F}_2$ such that $\rho(r) \neq 1$. Because $\mathbb{F}_2$ is a subgroup of $SL_2(\mathbb{C})$, we may suppose that $\rho : G_k \to SL_2(\mathbb{C})$.

Let $N_i = \rho(s_i^{(k)}) \in SL_2(\mathbb{C})$. Then $r(N_1, \dots, N_n)= \rho(r) \neq 1$ so $(N_1, \dots, N_n) \notin V_{k+1}$. If $w$ is a word over $S_k$ such that $w$ is a relation of $G_k$, then $w(N_1, \dots, N_n) = \rho(w) = \rho(1)=1$ so $(N_1, \dots, N_n) \in V_k$. $\square$

A difficult result about limit groups is:

Property: A limit group is finitely presented.

See for example V. Guirardel’s article, Limit groups and groups acting freely on $\mathbb{R}^n$-trees, for a proof based on actions on $\Lambda$-trees.

To conclude this note, let us mention a result giving examples of non-free limit groups:

Theorem 4: Let $F$ be a free group and $C \leq F$ be a cyclic subgroup closed under taking roots. Then $F \underset{C}{\ast} F$ is a limit group.

A proof can be found in Henry Wilton’s document, An introduction to limit groups (proprosition 2.9). In particular, the fundamental group of a surface $\Sigma$ is a limit group when $\Sigma$ is not a non-orientable surface whose Euler characteristic -1, 0 or 1.