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

## A free group contains a free group of any rank

For free groups, rank is a kind of dimension so it is surprising that a free group of rank $n$ can contain a free subgroup of rank $m>n$; it is even possible that $m$ be infinite! In this note, we propose three nice proofs of this fact:

Theorem: The free group $\mathbb{F}_2$ of rank two has a subgroup isomorphic to the free group $\mathbb{F}_{\infty}$ of countable rank.

In particular, we deduce that a free group of rank $n \geq 2$ (possibely infinite) contains a subgroup isomorphic to $\mathbb{F}_m$ for every $m \leq \aleph_0$!

1) A proof based on SQ-universality. A countable group $G$ is SQ-universal if every countable group is isomorphic to a subgroup of a quotient of $G$. First, notice that a SQ-universal group $G$ has a subgroup isomorphic to $\mathbb{F}_{\infty}$.

Indeed, as a countable group, $\mathbb{F}_{\infty}$ is isomorphic to a subgroup of a quotient $G/H$; let $\{x_1,x_2, \dots\}$ be a free basis of this subgroup. Let $\pi : G \to G/H$ be the canonical surjection and, for all $i \geq 1$, let $x_i^* \in G$ be such that $\pi(x_i^*)=x_i$. If $w$ is a reduced word, then $w(x_1^*,x_2^*,\dots) \neq 1$ since $\pi(w(x_1^*,x_2^*,\dots))=w(x_1,x_2,\dots) \neq 1$, so $\{x_1^*,x_2^*,\dots\}$ is a free basis of the subgroup $F = \langle x_1^*,x_2^*,\dots \rangle \leq G$, hence $F \simeq \mathbb{F}_{\infty}$.

Therefore, it is sufficient to prove that $\mathbb{F}_2$ is SQ-universal, that is (following Fred Calvin, Embeddings Countable Groups in 2-Generator Groups, The Amer. Math. Monthly, Vol. 100, No. 6, pp. 578-580):

Theorem: Every countable group is embeddable in a 2-generator group.

Proof. Let $G= \{g_1,g_3,g_5, \dots \}$ be a countable group. Notice first that $\varphi : \left\{ \begin{array}{ccc} G & \to & \mathrm{Sym}(G) \\ g & \mapsto & (h \mapsto gh) \end{array} \right.$ is an injective morphism, so without loss of generality we may suppose that $G$ is a subgroup of $\mathrm{Sym}(\mathbb{N}) \simeq \mathrm{Sym}(G)$.

Let $a,b \in \mathrm{Sym}(\mathbb{Z} \times \mathbb{Z} \times \mathbb{N})$ be such that:

$(m,n,p)a=(m+1,n,p)$

and

$(m,n,p)b = \left\{ \begin{array}{cl} (m,n+1,p) & \text{if} \ m=0 \\ (m,n,g_m \cdot p) & \text{if} \ m \ \text{is odd}, m>0,n \geq 0 \\ (m,n,p) & \text{otherwise} \end{array} \right.$.

Let $b_i=a^iba^{-i}$ and $\hat{g}_i=b_ib^{-1}b_i^{-1}b$ for all $i=1,3,5, \dots$. Then notice that

$(m,n,p) \hat{g}_i = \left\{ \begin{array}{cl} (0,0,g_i \cdot p) & \text{if} \ m=n=0 \\ (m,n,p) & \text{otherwise} \end{array} \right.$.

For example,

$\begin{array}{ll} (0,0,p) \hat{g}_i & = (0,0,p) a^iba^{-i}b^{-1}b_i^{-1}b = (i,0,p)ba^{-i}b^{-1}b_i^{-1}b \\ & = (i,0, g_i \cdot p)a^{-i}b^{-1}b_i^{-1}b = (0,0,g_i \cdot p) b^{-1}b_i^{-1}b \\ & = (0,-1,g_i \cdot p) a^ib^{-1} a^{-i} b = (i,-1,g_i \cdot p)b^{-1}a^{-i}b \\ & = (i,-1,g_i \cdot p) a^{-i}b = (0,-1,g_i \cdot p) b =(0,0,g_i \cdot p) \end{array}$

The other cases are left to the reader as exercice. Then $g_i \mapsto \hat{g}_i$ defines an isomorphism between $G$ and $\hat{G} = \{\hat{g}_1,\hat{g}_3,\hat{g}_5, \dots\}$. We conclude by noticing that $\hat{G}$ is a subgroup of the $2$-generator group $\langle a,b \rangle \leq \mathrm{Sym}(\mathbb{Z} \times \mathbb{Z} \times \mathbb{N})$. $\square$

2) A proof based on algebraic topology. The free group $\mathbb{F}_2$ is the fundamental group of a bouquet of two circles $X$. Therefore, if $\hat{X}$ denotes the universal covering of $X$, then the derived subgroup $D := [\mathbb{F}_2,\mathbb{F}_2]$ is the fundamental group of $\hat{X}/D$.

But $\hat{X}$ is the usual Cayley graph of $\mathbb{F}_2$ (Figure 1) and $\hat{X} /D$ is the usual Cayley graph of $\mathbb{Z}^2$ (Figure 2):

If $T$ is a maximal subtree of $\hat{X}/D$, then $\{ \text{edges of} \ \hat{X}/D \ \text{not in} \ T\}$ is a free basis of $D$, hence $D \simeq \mathbb{F}_{\infty}$. $\square$

Explicitely, taking $T = (\{0\} \times \mathbb{R}) \cup \bigcup\limits_{i \in \mathbb{Z}} \mathbb{R} \times \{i\}$, we find

$\{a^ib^ja^{-1}b^{-j}a^{1-i},a^{-i},b^jab^{-j}a^{i-1} \mid i>0,j \in \mathbb{Z} \backslash \{0\} \}$

as a free basis of $D$. More information on algebraic topology can be found in Hatcher’s book, Algebraic Topology (available on the author’s webpage).

3) A proof based on combinatorial group theory. Following Serre’s book Trees, we prove the following lemma (proposition 4 page 6):

Lemma: Let $A,B$ be two groups. For convenience, let $S= \{[a,b] \mid a \in A \backslash \{1\}, b \in B \backslash \{1\} \}$. Then $S$ is a free basis of the derived subgroup of $A \ast B$.

Proof. The derived subgroup $D$ of $A \ast B$ is the smallest subgroup so that $(A \ast B) / D$ be abelian. Therefore, we may deduce that $D$ is generated by $S$. To prove that $S$ is a free basis, we prove by induction that the reduced word (over $S$)

$g = [a_1,b_2]^{\epsilon_1} \cdots [a_n,b_n]^{\epsilon_n}$

with $\epsilon_i \in \{ \pm 1\}$, satisfies the two following conditions

1. The length of $g$ (as an element of $A \ast B$) is at least $n+3$,
2. The reduction of $g$ (as an element of $A \ast B$) finishes by $a_n^{-1}b_n^{-1}$.

The case $n=1$ is obvious. From now on, suppose it is true for $n$ and let

$g = [a_1,b_1]^{\epsilon_1} \cdots [a_{n+1},b_{n+1}]^{\epsilon_{n+1}} \hspace{1cm} (1)$

be a reduced word over $S$. By induction hypothesis, we can write

$g = s_1 \cdots s_pa_n^{-1} b_n^{-1} [a_{n+1},b_{n+1}]^{\epsilon_{n+1}}$,

where $s_1 \cdots s_pa_n^{-1} b_n^{-1}$ is reduced (as an element of $A \ast B$) and $p \geq n+1$. If $\epsilon_{n+1}=1$, there is no cancellation is the expression above, so $\ell g(g) = p+6 \geq n+7$. If $\epsilon_{n+1}=-1$, two cases happen:

• Case 1: $b_n \neq b_{n+1}$. Then, setting $\tilde{b}= b_n^{-1}b_{n+1}$, the word

$g = s_1 \cdots s_p a_n^{-1} \tilde{b} a_{n+1}b_{n+1}^{-1}a_{n+1}^{-1}$

is reduced (as an element of $A \ast B$), hence $\ell g(g) = p+5 \geq n+6$.

• Case 2: $b_n=b_{n+1}$. Because $(1)$ is reduced and $\epsilon_{n+1}=-\epsilon_n$, necessarily $a_n \neq a_{n+1}$, so setting $\tilde{a} = a_n^{-1} a_{n+1}$,

$g= s_1 \cdots s_p \tilde{a} b_{n+1}^{-1} a_{n+1}^{-1}$

is reduced (as an element of $A \ast B$) hence $\ell g(g) = p+3 \geq n+4$. $\square$

Corollary: The derived subgroup of $\mathbb{F}_2$ is isomorphic to $\mathbb{F}_{\infty}$.

Just for fun, notice the following consequence of our lemma:

Corollary: The only non-trivial soluble free product is $\mathbb{Z}_2 \ast \mathbb{Z}_2$.

Sketch of proof. Show the following straightforward results:

1. A subgroup of a soluble group is soluble,
2. A quotient of a soluble groupe is soluble,
3. Deduce from 2 that a free group of rank at least two is not soluble,
4. Deduce from 1 and 3 that a soluble group has no subgroup isomorphic to a free group of rank at least two,
5. Conclude using our lemma. $\square$

## When does a finite metric space embed isometrically into an euclidean space?

A first preliminary remark is that embedding isometrically a finite metric space into an euclidean space is not a trivial problem. Indeed, although there exists always such an embedding into $\mathbb{R}^n$ for a metric space of cardinality $n \leq 3$, there exist four-point metric spaces which cannot be emdebbed into any euclidean space:

Let $X= \{a,b,c,d\}$ be a metric space satisfying $d(a,d)=d(b,d)= \ell/2$ and $d(a,b)=d(a,c)=d(b,c)=\ell$ for some $\ell >0$. If $\varphi : X \to \mathbb{R}^n$ is an isometric embedding, then $\{ \varphi(a), \varphi(b), \varphi(c) \}$ are the vertices of an equilateral triangle and $\varphi(d)$ is the middle point of the segment $[\varphi(a),\varphi(b)]$, hence $d(\varphi(d),\varphi(c))= \frac{\sqrt{5}}{2} \ell$. Therefore, if $X$ embeds into an euclidean space then $d(c,d)= \frac{\sqrt{5}}{2} \ell$. Taking another value for $d(c,d)$ (so that triangular inequalities hold) makes $(X,d)$ an example of four-point metric space that does not embed into any euclidean space.

A second remark is that our problem may be applied to infinite metric spaces. Indeed, to show that an arbitrary metric space $X$ cannot be embedded isometrically into $\mathbb{R}^n$ it is sufficient to find a finite subset $Y \subset X$ having that property.

In fact, our previous example have such an interpretation. Let $\mathbb{S}^2 \subset \mathbb{R}^3$ be the two-dimensional sphere and $d$ be the metric on $\mathbb{S}^2$ defined by: if $x,y \in \mathbb{S}^2$, $d(x,y)$ is the length of the shortest great circle between $x$ and $y$. Let $a=(1,0,0)$, $b=(0,1,0)$, $c=(0,0,1)$ and $d= \left( \frac{1}{\sqrt{2}}, \frac{1}{\sqrt{2}},0 \right)$. Then $d(a,b)=d(a,c)=d(b,c)= \frac{\pi}{2}$, $d(a,d)=d(b,d)= \frac{\pi}{4}$ and $d(c,d)= \frac{\pi}{2} \neq \frac{\sqrt{5}\pi}{4}$.

We deduce that there is no isometry $\mathbb{S}^2 \hookrightarrow \mathbb{R}^n$ for every $n \geq 0$.

More generally, if $\Omega \subset \mathbb{S}^2$ is a nonempty open subset, we may suppose without loss of generality that $(0,0,1) \in \Omega$ and then $\Omega$ contains a (small) triangle similar to $(a,b,c)$. With the same argument, we deduce that there is no isometry $\Omega \hookrightarrow \mathbb{R}^n$ for every $n \geq 0$, hence:

Theorem: The sphere $\mathbb{S}^2$ is not locally flat, ie. for every nonempty open subset $\Omega \subset \mathbb{S}^2$ and integer $n \geq 0$ there does not exist any isometry $\Omega \hookrightarrow \mathbb{R}^n$.

The same thing can be done for the hyperbolic plane $\mathbb{H} = \{(x,y) \in \mathbb{R}^2 \mid y \geq 0 \}$ endowed with the metric $d$ defined by: if $x,y \in \mathbb{H}$ are on the same vertical line, $d(x,y)$ agrees with the euclidean distance between $x$ and $y$, otherwise $d(x,y)$ is the arc length between $x$ and $y$ of the circle centered at some point of $\mathbb{R} \times \{0\}$ and passing through $x$ and $y$.

For example, if $a=(-1,0)$, $b=(1,0)$, $c=(0,1)$ and $d=(0,0)$ then $d(a,c)=d(b,c)= \frac{\pi}{2}$, $d(a,b)=\pi$, $d(a,d)=d(b,d)= \frac{\pi}{2}$ and $d(c,d)=1$. If $\varphi : \mathbb{H} \to \mathbb{R}^n$ were an isometry, $\varphi(c)$ would belong to the hyperplane normal to the line $(\varphi(b), \varphi(d))$ and passing through its middle point $\varphi(d)$, hence

$\displaystyle \frac{\pi^2}{4}= d(\varphi(a),\varphi(c))^2= d(\varphi(a),\varphi(d))^2+ d(\varphi(c), \varphi(d))^2= \frac{\pi^2}{4}+1$,

a contradiction. The more general case is left as an exercice of elementary geometry:

Theorem: The hyperbolic plane $\mathbb{H}$ is not locally flat, ie. for every nonempty open subset $\Omega \subset \mathbb{H}$ and integer $n \geq 0$ there does not exist any isometry $\Omega \hookrightarrow \mathbb{R}^n$.

More information can be found in The Sphere Is Not Flat, P. L. Robison, The American Mathematical Monthly, Vol. 113, No. 2 (Feb. 2006), pp. 171-173.

From now on, let us back to our main problem: Let $X= \{x_0,\dots,x_m\}$ be a finite metric space and $n \geq 0$. Does there exist an isometry $X \hookrightarrow \mathbb{R}^n$?

Suppose that $\varphi : X \to \mathbb{R}^n$ is such an isometry; without loss of generality, we may suppose $\varphi(x_0)=0$. Then the equations $\| y_k- \varphi(x_i)\|= d(x_i,x_k)$ have solutions.

Noticing that $\|y_k- \varphi(x_i)\|^2= \|y_k\|^2+ \|\varphi(x_i)\|^2-2 \langle y_k, \varphi(x_i) \rangle$, $\|y_k\|^2= \|y_k- \varphi(x_0)\|^2=d(x_0,x_k)^2$ and $\|\varphi(x_i)\|^2= \| \varphi(x_i)- \varphi(x_0)\|^2=d(x_i,x_0)^2$, we deduce that

$\displaystyle \langle y_k, \varphi(x_i) \rangle = \frac{1}{2} \left( d(x_k, x_0)^2 + d(x_0, x_i)^2 - d(x_k, x_i)^2 \right)$.

For convenience, let $m_{ik}$ denote the expression in the right-hand of the previous equality; in particular, $m_{ik}$ depends only on the metric space $(X,d)$.

Therefore, if $\varphi(x_i)= \sum\limits_{j=1}^n \xi_{ij} e_j$ and $y_i= \sum\limits_{j=1}^n \zeta_{ij}e_j$,

$\left( \begin{matrix} \xi_{11} & \xi_{12} & \dots & \xi_{1n} \\ \xi_{21} & \xi_{22} & \dots & \xi_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ \xi_{m1} & \xi_{m2} & \dots & \xi_{mn} \end{matrix} \right) \left( \begin{matrix} \zeta_{11} & \zeta_{21} & \dots & \zeta_{m1} \\ \zeta_{12} & \zeta_{22} & \dots & \zeta_{m2} \\ \vdots & \vdots & \ddots & \vdots \\ \zeta_{1n} & \zeta_{2n} & \dots & \zeta_{mn} \end{matrix} \right) = \left( \begin{matrix} m_{11} & m_{12} & \dots & m_{1n} \\ m_{21} & m_{22} & \dots & m_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ m_{n1} & m_{n2} & \dots & m_{nn} \end{matrix} \right)$.

In particular, taking $\zeta_{ij}= \xi_{ij}$, we deduce that the matrix $M=(m_{ij})$ can be written as $^tPP$ for some $P \in M_{nm}(\mathbb{R})$. Conversely, if $M= \ ^tPP$ where $P=(v_1, \dots, v_m) \in M_{nm}(\mathbb{R})$ then $\varphi : x_i \mapsto v_i$ is an isometry $X \hookrightarrow \mathbb{R}^n$. Indeed, $\langle v_i,v_j \rangle = (^tPP)_{ij}=m_{ij}$ for all $i,j$ hence

$\| v_i-v_j \|^2 = \langle v_i, v_j \rangle -2 \langle v_i, v_j \rangle + \langle v_j, v_j \rangle = m_{ii} -2m_{ij} + m_{jj} = d(x_i, x_j)^2$.

We just showed that $X$ embeds isometrically into $\mathbb{R}^n$ if and only if the matrix $M$ can be written as $^tPP$ for some $P \in M_{nm}(\mathbb{R})$.

An equivalent condition is that $M$ is positive semi-definite and $\mathrm{rank}(M) \leq n$. Indeed, the matrix $M$ is symmetric so there exist $R \in O_m(\mathbb{R})$ and $\lambda_1,\dots,\lambda_m \in \mathbb{R}$ such that

$M= \ ^tR \left( \begin{matrix} \lambda_1 & & 0 \\ & \ddots & \\ 0 & & \lambda_m \end{matrix} \right) R$.

If $\mathrm{rank}(M) \leq n$ we may suppose $\lambda_k=0$ when $k \geq n+1$, and if $M$ is positive semi-definite then $\lambda_i \geq 0$. Consequently, $M= \ ^tPP$ with

$P = \left( \begin{matrix} \sqrt{\lambda_1} & & 0 & \\ & \ddots & & 0 \\ 0 & & \sqrt{\lambda_n} & \end{matrix} \right)R \in M_{nm}(\mathbb{R})$.

Conversely, suppose that $M= \ ^t PP$ for some $P \in M_{nm}(\mathbb{R})$. Then $t^xMx= \ ^tx^tPPx= \|P(x)\|^2 \geq 0$ for all $x$ so $M$ is positive semi-definite, and $Mx=0$ implies $\|Px\|^2= \ ^txMx=0$ so $M$ and $P$ have the same nullspace hence $\mathrm{rank}(M)= \mathrm{rank}(P) \leq n$ since $P$ has only $n$ rows.

We finally showed:

Theorem: A finite metric space $X=\{x_0,\dots,x_m\}$ embeds isometrically into $\mathbb{R}^n$ if and only if the matrix $M \in M_n(\mathbb{R})$ whose coefficients are $\frac{1}{2} \left( d(x_i,x_0)^2+d(x_0,x_j)^2-d(x_i,x_j)^2 \right)$ is positive semi-definite and of rank $\leq n$.

Notice that our proof gives an algorithm to find an embedding $X \hookrightarrow \mathbb{R}^n$ when it exists. As an exercice, the reader may verify that the matrices associated to our two previous examples are not positive semi-definite or of rank $\leq n$.

A geometrical interpretation of the criterion given in this note can be found in Embedding Metric Spaces in Euclidean Spaces, C. L. Morgan, Journal of Geometry, 5 (1974).

## Number of group topologies on the real line

In this note, we show how functional analysis can be used to compute the number of group topologies on the real line and how representation theory of locally compact abelian groups leads to the existence of a compact group topology on $(\mathbb{R},+)$.

Theorem 1: There exist exactly $2^{2^{\mathfrak{c}}}$ distinct group topologies on $(\mathbb{R},+)$.

Definition: Let $X$ be a normed vector space (over $\mathbb{R}$) and $\Phi$ be a linear subspace of the topological dual $X^*$ (ie. the space of continuous functionals). The weak topology $\sigma(X,\Phi)$ on $X$ is the initial topology associated to $\Phi$.

Lemma 1: A weak topology is a group topology.

Proof. Let $X$ be a normed vector space and $\sigma(X,\Phi)$ be a weak topology. To show that $\varphi : (x,y) \mapsto x+y$ is continuous, it is sufficient to notice that for all $\phi_1, \dots, \phi_n \in \Phi$ and $\epsilon>0$ the following set is open for $\sigma(X,\Phi)$:

$\displaystyle \varphi^{-1} \left( \bigcap\limits_{i=1}^n \phi_i^{-1} ((x_i- \epsilon_i,x_i+ \epsilon_i)) \right) \\ = \bigcap\limits_{i=1}^n \{(x,y) \in X \times X \mid x+y \in \phi_i^{-1}((x_i-\epsilon_i,x_i+ \epsilon_i)) \} \\ = \bigcap\limits_{i=1}^n \{(x,y) \in X \times X \mid x_i- \epsilon_i < \phi_i(x)+ \phi_i(y) < x_i+ \epsilon_i \} \\ = \bigcap\limits_{i=1}^n \bigcup\limits_{\delta \in (0,\epsilon_i)} \{ (x,y) \in X \times X \mid x_i- \delta < \phi_i(x) < x_i+ \delta, -\epsilon_i + \delta < \phi_i(y) < \epsilon_i - \delta \} \\ = \bigcap\limits_{i=1}^n \bigcup\limits_{\delta \in (0,\epsilon_i)} \phi_i^{-1} ((x_i- \delta,x_i+ \delta)) \times \phi_i^{-1} ((-\epsilon_i+ \delta,\epsilon_i- \delta))$

Then, $x \mapsto -x$ is clearly continuous, since $r-\epsilon < \phi(x) < r+ \epsilon$ is equivalent to $-r- \epsilon < \phi(-x) < -r + \epsilon$ for all $\phi \in \Phi$, $x \in X$, $r \in \mathbb{R}$ and $\epsilon >0$. $\square$

Lemma 2: Let $X$ be a normed vector space and $\sigma(X,\Phi)$ be a weak topology. With respect to $\sigma(X,\Phi)$, a functional $\varphi : X \to \mathbb{R}$ is continuous if and only if $\varphi \in \Phi$.

Proof. Let $\phi$ be a linear functional continuous for $\sigma(X,\Phi)$. Then there exist linear functionals $\phi_1, \dots, \phi_n \in \Phi$ and open neighborhoods of the origin $V_1, \dots, V_n \subset \mathbb{R}$ so that

$\displaystyle \phi^{-1}((-1,1)) \supset \bigcap\limits_{i=1}^n \phi_i^{-1}(V_i) \supset \bigcap\limits_{i=1}^n \mathrm{ker}(\phi_i)$.

In particular, $\phi$ is bounded on $\bigcap\limits_{i=1}^n \mathrm{ker}(\phi_i)$ hence $\bigcap\limits_{i=1}^n \mathrm{ker}(\phi_i) \subset \mathrm{ker}(\phi)$. Let

$f : \left\{ \begin{array}{ccc} X & \to & \mathbb{R}^n \\ x & \mapsto & (\phi_1(x), \dots,\phi_n(x)) \end{array} \right.$.

Because $\bigcap\limits_{i=1}^n \mathrm{ker}(\phi_i) \subset \mathrm{ker}(\phi)$, we may define $\varphi : f(X) \to \mathbb{R}$ by $\varphi(x)= \phi(y)$ when $f(y)=x$

Let $\tilde{\varphi} : \mathbb{R}^n \to \mathbb{R}$ be a linear extension of $\varphi$. In particular, $\phi = \tilde{\varphi} \circ f$.

Let $\lambda_1, \dots, \lambda_n \in \mathbb{R}$ such that $\tilde{\varphi} : x \mapsto \sum\limits_{i=1}^n \lambda_i x_i$. Then for all $x \in X$,

$\phi(x)= \tilde{\varphi} \circ f(x)= \tilde{\varphi} (\phi_1(x) ,\dots \phi_n(x)) = \sum\limits_{i=1}^n \lambda_i \phi_i(x)$,

hence $\phi = \sum\limits_{i=1}^n \lambda_i \phi_i \in \Phi$. $\square$

Lemma 3: (Erdös-Kaplansky theorem) Let $V$ be an infinite-dimensional vector space. If $V^*$ denotes its dual space, $\dim(V^*)= 2^{\dim(V)}$.

We do not prove Erdös-Kaplansky theorem here and refer to Bourbaki’s book, Algebra. Chapters 1 to 3 (exercice 3 page 400).

Proof of theorem 1. Let $c_0$ be the set of eventually zero sequences endowed with the sup norm and let $B$ be a basis of $c_0^*$. For all $S \subset B$, let $\Phi_S= \mathrm{span}(S) \subset c_0^*$. According to lemma 2, for all $R,S \subset B$

$\sigma(X, \Phi_S)= \sigma(X,\Phi_R) \Leftrightarrow \Phi_S = \Phi_R \Leftrightarrow R=S$.

Therefore, according to lemmas 1 and 3, $\{ \sigma(X,\Phi_S) \mid S \subset B\}$ is a family of $2^{2^{\mathfrak{c}}}$ distinct group topologies on $(c_0,+)$.

Because $c_0$ and $\mathbb{R}$ are both a linear vector space over $\mathbb{Q}$ of dimension $\mathfrak{c}$, there exists an isomorphism $\phi$ between the abelian groups $(c_0,+)$ and $(\mathbb{R},+)$. Then we can use $\phi$ to transfer the $2^{2^{\mathfrak{c}}}$ distinct group topologies from $(c_0,+)$ to $(\mathbb{R},+)$.

So $(\mathbb{R},+)$ has at least $2^{2^{\mathfrak{c}}}$ distinct group topologies.  On the other hand, $(\mathbb{R},+)$ has at most $|\mathfrak{P}(\mathfrak{P}(\mathbb{R}))|=2^{2^{\mathfrak{c}}}$ distinct group topologies. $\square$

Then we may deduce the following corollaries:

Theorem 2: $(\mathbb{R},+)$ has exactly $2^{2^{\mathfrak{c}}}$ non-isomorphic group topologies.

Proof. $(\mathbb{R},+)$ has at most $| \mathbb{R}^{\mathbb{R}}|= 2^{\mathfrak{c}}$ automorphisms and has exactly $2^{2^{\mathfrak{c}}}$ group topologies. $\square$

Theorem 3: $(\mathbb{R},+)$ has exactly $2^{2^{\mathfrak{c}}}$ non-locally-compact group topologies.

Proof. It is known that every locally compact topological vector space is finite-dimensional (the reader might see Tao’s article on his blog or Bourbaki’s book, Topological vector spaces). Therefore, the weak topologies defined on $c_0$ in the proof of theorem 1 are not locally compact. $\square$

Despite theorems 1 and 3, $(\mathbb{R},+)$ admits compact group topologies:

Theorem 4: $(\mathbb{R},+)$ has infinitely many compact group topologies.

Definition: Let $G$ be a locally compact abelian group. The character group $\hat{G}$ of $G$ is the set of continuous morphisms from $G$ to the circle group $\mathbb{T}$ endowed with the compact-open topology.

Then $\hat{G}$ is also a locally compact abelian group and

Theorem: (Pontryagin duality) Let $G$ be a locally compact abelian group. Then $G$ and $\widehat{\widehat{G}}$ are isomorphic.

Pontryagin duality theorem is a difficult result so we do not prove it here; a proof for discrete and compact abelian groups (the case we deal with here) can be found here. We deduce:

Lemma 4: Let $G$ be a discrete abelian group and $H \subset G$ be a proper subgroup. Then the annihilator $A(H)= \{ \chi \in \hat{G} \mid \forall h \in H , \chi(h)=1 \}$ is not trivial.

Proof. Because $H$ is a proper subgroup, $\widehat{G/H}$ is not trivial (otherwise, $G/H \simeq \widehat{\widehat{G/H}}$ would be trivial). Let $\hat{\chi} \in \widehat{G/H}$ be a non-trivial character and let $\chi = \hat{\chi} \circ \pi$ where $\pi : G \to G/H$ is the canonical projection. Then $\chi \in A(H) \backslash \{1\}$. $\square$

Lemma 5: Let $G$ be a discrete abelian group. Then $G$ is divisible (resp. torsion free) if and only if $\hat{G}$ is torsion free (resp. torsion free).

Proof. For every group $H$, let $H_n'= \{ x \in H \mid nx=0 \}$ and $H_n''= \{x \in H \mid \exists H, x=ny\}$. First, we notice

$\begin{array}{cl} A(G_n'') & = \{ \chi \in \hat{G}\mid \forall y\in G, \chi(ny)=1 \} \\ & = \{ \chi \in \hat{G} \mid \forall y \in G, \chi^n(y)=1 \} \\ & = \{ \chi \in \hat{G} \mid \chi^n=1 \} = \hat{G}_n' \end{array}$

By Pontryagin duality, we also have $G_n' \simeq \hat{\hat{G}}_n'= A(\hat{G}_n'')$.

If $G$ is divisible, $G_n''=G$ hence $\{1\}=A(G)= A(G_n'')= \hat{G}_n'$. So $\hat{G}$ is torsion free.

If $G$ is torsion free ie. $G_n'=\{0\}$, then $A(\hat{G}_n'')= \{1\}$ hence $\hat{G}_n''=\hat{G}$ according to lemma 4. Therefore, $\hat{G}$ is divisible.

To conclude, we deduce that $G$ is torsion-free if and only if $\hat{G}$ is divisible by Pontryagin duality. $\square$

Proof of theorem 4. According to lemma 5, when $(\mathbb{Q},+)$ is endowed with the discrete topology, $\hat{\mathbb{Q}}$ is a divisible torsion-free abelian group, so $\hat{\mathbb{Q}}$ can be viewed as a vector space over $\mathbb{Q}$.

Notice that $| \hat{\mathbb{Q}}|= \mathfrak{c}$, because $\varphi_r : q \mapsto e^{irq}$ with $r \in (0,2\pi)$ defines a family of pairwise dijoint characters, so $\hat{\mathbb{Q}}$ is a vector space over $\mathbb{Q}$ of dimension $\mathfrak{c}$. Consequently $\hat{\mathbb{Q}}$ and $\mathbb{R}$ are isomorphic as abelian groups, so it is sufficient to show that $\hat{\mathbb{Q}}$ is compact to deduce a compact group topology on $\mathbb{R}$.

Because $\mathbb{Q}$ is discrete, the compact-open topology on $\hat{\mathbb{Q}}$ coincide with induced topology of $\mathbb{T}^{\mathbb{Q}}$ (endowed with the product topology) on $\hat{\mathbb{Q}}$. Since $\mathbb{T}^{\mathbb{Q}}$ is compact according to Tychonoff’s theorem, it is sufficient to show that $\hat{\mathbb{Q}}$ is closed in $\mathbb{T}^{\mathbb{Q}}$.

Let $\varphi \in \mathbb{T}^{\mathbb{Q}} \backslash \hat{\mathbb{Q}}$ that is $\varphi$ is not a homomorphism, so there exist $x,y \in \mathbb{Q}$ such that $\varphi(x-y) \neq \varphi(x) \cdot \varphi(y)^{-1}$. Let

$\Omega= \prod\limits_{q \in \mathbb{Q}} X_q$ where $X_q = \left\{ \begin{array}{cl} \{\varphi(z) \} & \text{if} \ q =z \in \{x,y,x-y\} \\ \mathbb{T} & \text{otherwise} \end{array} \right.$

Then $\Omega$ is an open neighborhood of $\varphi$ in $\mathbb{T}^{\mathbb{Q}}$ and does not meet $\hat{\mathbb{Q}}$. Hence $\hat{\mathbb{Q}}$ is closed in $\mathbb{T}^{\mathbb{Q}}$.

In the same way, we may induce a compact group topology on $\mathbb{R}$ using $\widehat{\mathbb{Q}^n}$. $\square$

In fact, $( \mathbb{R},+)$ turns out to have exactly $\aleph_0$ compact group topologies. For more information, see for example:

## Almost all matrices are diagonalizable

Diagonalization is often presented as a useful tool for computing powers of matrices; however, if only few matrices are diagonalizable, the method might be not really powerful. Here, we prove that almost all matrices are diagonalizable over $\mathbb{C}$ from different viewpoints.

Definition: Let $P,Q \in k[X]$ be two polynomials. The resultant $\mathrm{res}(P,Q)$ is defined as the product

$\displaystyle p^{\deg(P)} q^{\deg(Q)} \prod\limits_{(x,y) \in \tilde{k}, \ P(x)=Q(y)=0} (x-y)$,

where $\tilde{k}$ denote the algebraic closure of $k$ and $p,q$ denote the leading coefficients of $P$ and $Q$ respectively; in the case of multiple roots, the factors are repeated according to their multiplicities.

Notice that $\mathrm{res}(P,Q)$ is a symmetric polynomial on the roots of $P$ and $Q$ in $\tilde{k}$. Therefore, according to the fundamental theorem of symmetric polynomials and to Vieta’s formulas, $\mathrm{res}(P,Q) \in k$.

Definition: The discriminant of a polynomial $P \in k[X]$ is defined by $\Delta(P)= \mathrm{res}(P,P')$.

Lemma 1: Let $P,Q \in k[X]$ be two polynomials. Then $\mathrm{res}(P,Q) \neq 0$ if and only if $P$ and $Q$ are coprime.

Proof. If $P$ and $Q$ have a common divisor then clearly they have a common root in $\tilde{k}$ hence $\mathrm{res}(P,Q)=0$. Conversely, suppose that $P$ and $Q$ are coprime. According to Bézout’s identity of polynomials, there exist two polynomials $U,V \in k[X]$ such that

$UP+VQ=1$.

Because the equality still holds in $\tilde{k}[X]$, we deduce that $P$ and $Q$ do not have any commom root in $\tilde{k}$, hence $\mathrm{res}(P,Q) \neq 0$. $\square$

We deduce easily the following corollary:

Lemma 2: Let $P \in \mathbb{C}[X]$ be a polynomial. Then $P$ has only simple roots if and only if $\Delta(P) \neq 0$.

Because $\Delta(P)$ is a polynomial on the coefficients of $P$, we will able to deduce the following theorems from lemmas 3, 4 and 5:

Theorem 1: The set $D \subset M_n(\mathbb{C})$ of diagonalizable matrices is dense in $M_n(\mathbb{C})$.

Theorem 2: The set $D \subset M_n(\mathbb{C})$ of diagonalizable matrices is a set of full measure (ie. its complement has measure zero).

Lemma 3: Let $M \in M_n(\mathbb{C})$ be a matrix. If its characteristic polynomial $P$ has only simple roots then $M$ is diagonalizable.

Proof. Let $\lambda_1, \dots, \lambda_n \in \mathbb{C}$ be the distinct eigenvalues of $M$ (ie. the roots of $P$), and for every $1 \leq i \leq n$, let $v_i$ be an eigenvector associated to $\lambda_i$.

We show that $(v_1, \dots, v_n)$ is a basis of $\mathbb{C}^n$ by induction on $n$. For $n=1$, it is clear. Suppose that it is true for $n-1$ and let $\alpha_1, \dots, \alpha_n \in \mathbb{C}$ be such that

$\alpha_1 \cdot v_1 + \alpha_2 \cdot v_2+ \cdots + \alpha_n \cdot v_n=0$,

Suppose by contradiction that one $\alpha_i$ is non-zero, say $\alpha_1$. Then

$\displaystyle v_1= - \frac{\alpha_2}{\alpha_1} \cdot v_2 - \cdots - \frac{\alpha_n}{\alpha_1} \cdot v_n$,

hence

$\displaystyle \lambda_1 \cdot v_1 = - \lambda_1 \frac{\alpha_2}{\alpha_1} \cdot v_2- \cdots - \frac{\alpha_n}{\alpha_1} \cdot v_n$.

On the other hand,

$\displaystyle \lambda_1 \cdot v_1= M \cdot v_1= - \lambda_2 \frac{\alpha_2}{\alpha_1} \cdot v_2- \cdots - \lambda_n \frac{\alpha_n}{\alpha_1} \cdot v_n$.

We deduce

$\displaystyle (\lambda_1- \lambda_2) \frac{\alpha_2}{\alpha_1} \cdot v_2 + \cdots + (\lambda_1- \lambda_n) \frac{\alpha_n}{\alpha_1} \cdot v_n=0$.

Because $\lambda_1 \neq \lambda_i$ when $i \neq 1$ and according to our induction hypothesis, we deduce that $\alpha_2= \cdots = \alpha_n=0$, hence $\alpha_1 \cdot v_1=0$ ie. $\alpha_1=0$: a contradiction. $\square$

Corollary 1: Let $D \subset M_n(\mathbb{C})$ be the set of diagonalizable matrices. Then $\mathrm{int}(D)$ is the set of matrices whose eigenvalues are pairwise distinct.

Proof. For every matrix $M$, let $P_M$ denote its characteristic polynomial. Let $\varphi : M \mapsto \Delta(P_M)$. In particular, $\varphi$ is a polynomial on the coefficient of $M$ so $\varphi$ is continuous. According to lemma 2 and 3, we deduce that the set $\varphi^{-1}(\mathbb{C} \backslash \{0\})$ of diagonalizable matrices whose eigenvalues are pairwise discinct is open in $D$.

Let $M$ be a diagonalizable matrix with an eigenvalue $\lambda$ of multiplicity at least two. There exist $P \in Gl_n(\mathbb{C})$ and two diagonal matrices $D_1,D_2$ such that

$M=P \left( \begin{matrix} D_1 & 0 & 0 \\ 0 & \begin{matrix} \lambda & 0 \\ 0 & \lambda \end{matrix} & 0 \\ 0 & 0 & D_2 \end{matrix} \right)P^{-1}$.

For all $\epsilon>0$, let

$M_{\epsilon} = P \left( \begin{matrix} D_1 & 0 & 0 \\ 0 & \begin{matrix} \lambda & \epsilon \\ 0 & \lambda \end{matrix} & 0 \\ 0 & 0 & D_2 \end{matrix} \right) P^{-1}$.

Suppose that $M_{\epsilon}$ is diagonalizable; in particular, there exists a polynomial $Q \in \mathbb{C}[X]$ whose roots are simple such that $Q(M_{\epsilon})=0$. Clearly, the matrix $\left( \begin{matrix} \lambda & \epsilon \\ 0 & \lambda \end{matrix} \right)$ vanishes the polynomial $Q$, so this matrix is diagonalizable, that is there exists $S \in Gl_n(\mathbb{C})$ such that

$M_{\epsilon}= S \left( \begin{matrix} \lambda & 0 \\ 0 & \lambda \end{matrix} \right) S^{-1} = \lambda \cdot \mathrm{I_n}$,

hence $\epsilon =0$. Therefore, $M_{\epsilon}$ is diagonalizable if and only if $\epsilon=0$ and $M_{\epsilon} \underset{\epsilon \to 0}{\longrightarrow} M$, so $D \backslash \varphi^{-1}(\mathbb{C} \backslash \{0\}) \subset \partial D$.

Finally, we deduce that $\mathrm{int}(D) = \varphi^{-1}(\mathbb{C} \backslash \{0\})$. $\square$

Lemma 4: Let $P \in \mathbb{C}[X_1,\dots,X_n]$ be a non-zero polynomial. Then $P^{-1}(0)$ is nowhere dense in $\mathbb{C}^n$.

Proof. Suppose that $P$ vanishes on an open ball $B(x_0,r) \subset \mathbb{C}^n$ and let $x_1 \in \mathbb{C}^n$. The restriction of $P$ on the straight line passing through $x_0$ and $x_1$ coincides with a polynomial $p$ in one variable. Because $P$ vanishes on $B(x_0,r)$, we deduce that $p$ has infinitely many roots hence $p=0$ and $P(x_1)=0$. Therefore, $P=0$. $\square$

Lemma 5: Let $P \in \mathbb{R}[X_1,\dots,X_n]$ be a non-zero polynomial. Then $P^{-1}(0)$ has measure zero in $\mathbb{R}^n$.

Proof. We prove by induction on $n$ that the null set of a non-zero polynomial in $\mathbb{R}[X_1, \dots, X_n]$ has measure zero. For $n=1$, it is clear since $P^{-1}(0)$ is finite. Suppose the result holds for $n-1$ and let $P \in \mathbb{R} [X_1,\dots ,X_n]$.

Let $I = \{x_1 \in \mathbb{R} \mid P(x_1, \cdot)=0\}$. It is possible to write $P$ as

$\displaystyle P(x_1,x_2, \dots, x_n)= \sum\limits_{k=0}^m P_k(x_1) \cdot m_k(x_2, \dots, x_n)$,

where $P_k \in \mathbb{R}[X_1]$, $m_k \in \mathbb{R}[X_2,\dots,X_n]$ are monomials and $P_m \neq 0$. Notice that $P(x_1, \cdot)=0$ implies $P_m(x_1)=0$ so $I$ is finite since $P_m$ has only finitely many roots. Then

$\begin{array}{cl} \mu_n(P^{-1}(0)) & \displaystyle = \int_{\mathbb{R}^n} \mathbf{1}_{P^{-1}(0)} (x_1,\dots,x_n) dx_1 \dots dx_n \\ \\ & \displaystyle = \int_{\mathbb{R}} \int_{\mathbb{R}^{n-1}} \mathbf{1}_{P^{-1}(0)} (x_1,x_2,\dots,x_n) dx_1dx_2 \dots dx_n \\ \\ & \displaystyle = \int_{\mathbb{R}} \underset{:=f(x_1)}{\underbrace{ \mu_{n-1} \left( \{ (x_2, \dots ,x_n) \in \mathbb{R}^{n-1} \mid P(x_1,x_2, \dots,x_n)=0 \} \right) }} dx_1 \\ \\ & \displaystyle = \int_I f(x_1)dx_1 + \int_{\mathbb{R} \backslash I} f(x_1)dx_1 \end{array}$

Because $\mu(I)=0$, we deduce that $\displaystyle \int_I f(x_1)dx_1=0$.

Then, if $x_1 \notin I$ we have $P(x_1, \cdot) \neq 0$, hence

$\mu_{n-1} \left( \{ (x_2,\dots,x_n) \in \mathbb{R}^{n-1} \mid P(x_1,x_2,\dots,x_n) =0 \} \right)=0$,

by our induction hypothesis. Therefore, $\displaystyle \int_{\mathbb{R} \backslash I} f(x_1)dx_1=0$ and finally $\mu_n(P^{-1}(0))=0$. $\square$

Proof of theorems 1 and 2. For every matrix $M \in M_n(\mathbb{C})$, let $P_M \in \mathbb{C}[X]$ denote its characteristic polynomial. Let $\varphi : M \mapsto \Delta(P_M)$. Because $\varphi$ is a polynomial on the coefficients of $M$, we deduce from corollary 1 and lemmas 3 to 5 that $\mathrm{int}(D)= \varphi^{-1}(\mathbb{C} \backslash \{0\})$ is dense in $M_n(\mathbb{C})$ and is a set of full measure. $\square$

In fact, theorem 1 (resp. lemma 3) is a consequence of theorem 2 (resp. lemma 4).

Notice that there are no theorems similar to theorems 1 and 2 when we deal with diagonalization over $\mathbb{R}$. Indeed, the characteristic polynomial of $M= \left( \begin{matrix} 0 & -1 \\ 1 & 0 \end{matrix} \right)$ has a negative discriminant, so there exists a neighborhood $V$ of $M$ such that the discriminant is negative on $V$; in particular, the matrices in $V$ are not diagonalizable.

However, it is possible to determine the closure of the set of diagonalizable matrices in $M_n(\mathbb{R})$:

Property: The closure of the set of diagonalizable matrices (over $\mathbb{R}$) in $M_n(\mathbb{R})$ is the set of triangularizable matrices.

Proof. Let $M \in M_n(\mathbb{R})$ be a triangularizable matrix. So there exist $P \in Gl_n(\mathbb{R})$ and $\lambda_1, \dots, \lambda_n \in \mathbb{R}$ such that

$M=P \left( \begin{matrix} \lambda_1 & & \ast \\ & \ddots & \\ 0 & & \lambda_n \end{matrix} \right) P^{-1}$.

For all $\epsilon>0$, let $0<\epsilon_1,\dots, \epsilon_n<\epsilon$ be such that $\lambda_i+ \epsilon_i \neq \lambda_j + \epsilon_j$ when $i \neq j$. Therefore, the matrix

$M= P \left( \begin{matrix} \lambda_1+ \epsilon_1 & & \ast \\ & \ddots & \\ 0 & & \lambda_n + \epsilon_n \end{matrix} \right) P^{-1}$

is diagonalisable according to lemma 3. Because $M_{\epsilon} \underset{\epsilon \to 0}{\longrightarrow} M$, we deduce that $M$ belongs to the closure of the set of diagonalizable matrices.

Conversely, let $M$ be the limit of diagonalizable matrices $(M_j)$. Let $P_j$ (resp. $P$) be the characteristic polynomial of $M_j$ (resp. $M$). We can write

$\displaystyle P_j = \prod\limits_{k=1}^n (X- \lambda_{j,k} )$ and $\displaystyle P= \prod\limits_{k=1}^n (X-\lambda_k)$,

where $\lambda_{j,k} \in \mathbb{R}$ and $\lambda_k \in \mathbb{C}$.

From now on, we fix some $1 \leq k \leq n$. For all $s \geq 0$, let $1 \leq i_s \leq n$ be such that $|\lambda_k- \lambda_{s,i_s}| = \min\limits_{1 \leq j \leq n} |\lambda_k-\lambda_{s,j}|$. Therefore,

$\displaystyle |P_s(\lambda_k)| = \prod\limits_{j=1}^n |\lambda_k- \lambda_{s,j}| \geq |\lambda_k- \lambda_{s,i_s}|^n$

hence

$\displaystyle |\lambda_k-\lambda_{s,i_s}| \leq \sqrt[n]{|P_s(\lambda_k)|} \underset{s \to + \infty}{\longrightarrow} \sqrt[n]{|P(\lambda_k)|}=0$.

(We used the fact that the coefficients of a characteristic polynomial are polynomials on the coefficient of the matrix to justify that $P_k \to P$.)

Therefore, the complex roots of $P$ are limits of roots of the $P_n$ so $\lambda_1,\dots,\lambda_n \in \mathbb{R}$. We deduce that $M$ is triangularizable. $\square$

Now, we deal with a probabilistic viewpoint; intuitively, the following theorem states that a matrix in $M_n(\mathbb{Z})$ is diagonalizable over $\mathbb{C}$ with a probability of one:

Theorem 3: Let $T_n(k)$ be the number of matrices in $M_n(\mathbb{Z})$ whose coefficients are in $\{ -k , \dots ,k\}$ and $R_n(k)$ be the number of similar matrices whose (complex) eigenvalues are not pairwise distinct. Then

$\displaystyle \lim\limits_{k \to + \infty} \frac{R_n(k)}{T_n(k)} = 0$.

Proof. Let $\varphi : M \mapsto \Delta(P_M)$ where $P_M$ denotes the characteristic polynomial of $M$. We already know that $\varphi$ is a polynomial $g_0(x_1, \dots , x_{n^2})$ on the coefficients of $M$ and that $\varphi(M)=0$ if and only if $M$ has a complex eigenvalue with multiplicity at least two. Therefore, if

$S= \{ (x_1, \dots, x_{n^2}) \in \{-k, \dots,k\}^{n^2} \mid g_0(x_1,\dots, x_{n^2})=0 \}$

then $R_n(k)= |S|$.

By induction, we define $g_i \in \mathbb{Z}[X_{i+1}, \dots, X_{n^2}]$ for $1 \leq i \leq n^2$ as the leading coefficient of $g_{i-1} \in \mathbb{Z} [X_{i+1}, \dots, X_{n^2}] [X_i]$. In particular, notice that $g_{n^2} \in \mathbb{Z} \backslash \{0\}$ and $\deg(g_i) \leq m$. For all $i \geq 1$, let us introduce the set

$\begin{array}{lc} S_i = & \{ (x_1,\dots, x_{n^2}) \in S \mid g_0(x_1,\dots,x_{n^2})= \cdots = g_{i-1}(x_i,\dots,x_{n^2})=0, \\ & g_i(x_{i+1},\dots,x_{n^2}) \neq 0 \} \end{array}$

Then $\displaystyle S= \coprod\limits_{i=1}^{n^2} S_i$ so $\displaystyle |S|= \sum\limits_{i=1}^{n^2} |S_i|$.

If $g_i(x_{i+1}, \dots, x_{n^2}) \neq 0$, the polynomial $g_{i-1}( \cdot,x_{i+1}, \dots,x_{n^2}) \in \mathbb{Z}[X_i]$ is non-zero so it has at most $\deg(g_{i-1}) \leq m$ roots. We deduce that

$\displaystyle |S_i| \leq m(2k+1)^{n^2-1}$.

(We have at least $m$ choices for $x_i$ and $2k+1$ choices for each $x_j$ with $j \neq i$.)

Therefore, $|S| \leq mn^2(2k+1)^{n^2-1}$, and because $T_n(k)= (2k+1)^{n^2}$:

$\displaystyle \frac{R_n(k)}{T_n(k)} \leq \frac{mn^2}{2k+1} \underset{k \to + \infty}{\longrightarrow} 0. \hspace{1cm} \square$

Again, theorem 3 does not hold for diagonalizations over $\mathbb{R}$ or $\mathbb{Q}$. For example,

$\displaystyle \lim\limits_{k \to + \infty} \frac{D_2(k)}{T_2(k)} = \frac{49}{72}$

over $\mathbb{R}$, and even

$\displaystyle \lim\limits_{k \to + \infty} \frac{D_2(k)}{T_2(k)} =0$

over $\mathbb{Q}$, where $D_2(k)$ is the number of diagonalizable (over $\mathbb{R}$ or $\mathbb{Q}$) matrices whose coefficients are in $\{-k, \dots,k \}$.

More information can be found in the paper The probability that a matrix of integers is diagonalizable.

## Some surprising but elementary facts in infinite-dimensional topology

Topological properties of a normed space $X$ are widely different depending on $X$ is either finite-dimensional or infinite-dimensional; in fact, whole books are devoted to topology in infinite dimensions. Here, we propose some surprising but elementary facts in infinite-dimensional topology.

Lemma 1: Let $X$ be a normed space and $A \subset X$ be a proper closed linear subspace. For every $\epsilon>0$, there exists $x \in X$ such that $\|x\|=1$ and $d(x,A) \geq 1- \epsilon$.

Proof. Let $\epsilon>0$; without loss of generality, we may suppose $\epsilon<1$. Let $y \in X \backslash A$ and $a_0 \in A$ be such that

$\displaystyle d(y,A) \leq \| y-a_0 \| \leq \frac{d(y,A)}{1- \epsilon}$.

Let $\displaystyle x = \frac{y-a_0}{\|y-a_0\|}$. Then for all $a \in A$,

$\displaystyle \|x-a\|= \frac{y- (a_0+ \|y-a_0\| \cdot a)}{\|y-a_0\|} \geq \frac{d(y,A)}{\|y-a_0\|} \geq 1- \epsilon$,

because $a_0+ \|y-a_0\| \cdot a \in A$, hence $d(x,A) \geq 1- \epsilon$. $\square$

Theorem 1: Let $X$ be a normed space. The unit closed ball $B= \{x \in X \mid \|x\| \leq 1\}$ is compact if and only if $X$ is finite-dimensional.

Proof. Let $x_0 \in S(0,1)$. Because any finite-dimensional linear subspace of $X$ is closed, we can use lemma 1 to construct by induction a sequence $(x_n)$ satisfying

$\|x_n\|=1$ and $d(x_n, \mathrm{span}(x_0,\dots,x_{n-1})) \geq \frac{1}{2}$

for all $n \geq 1$; the sequence has infinitely many terms because $X$ is infinite-dimensional.

In particular $\|x_n-x_m\| \geq \frac{1}{2}$ when $n \neq m$. Therefore, $(x_n)$ is a sequence in the sphere $S(0,1) \subset B$ without converging subsequence: $B$ cannot be compact. $\square$

Corollary: Let $X$ be an infinite-dimensional normed space. Then the interior of any compact subspace $K \subset X$ is empty.

Theorem 2: Let $X$ be an infinite-dimensional normed space and $K \subset X$ be a compact subspace. Then $X \backslash K$ is path connected.

Proof. Without loss of generality we may suppose that $K \subset B(0,1)$ since $x \mapsto a \cdot x$ is a homeomorphism for all $a \in \mathbb{R} \backslash \{0\}$. Because the sphere $S(0,1)$ is path-connected, it is sufficient to show that any point $x_0 \notin K$ can be connected to $S(0,1)$. If $\|x_0\|>1$ the statement is clear, so from now on suppose that $x \in B(0,1)$.

As in the proof of theorem 1, there exists a sequence $(x_n)$ in $S(0,1)$ satisfying $\|x_n-x_m\| \geq \frac{1}{2}$ for all $n \neq m$.

Suppose by contradiction that every line $\mathbb{R} \cdot x_n -x$ meets $K$, that is for every $n \geq 1$ there exists $\lambda_n \in \mathbb{R}$ such that $\lambda_n \cdot x_n-x \in K$.

Because $K$ is compact and $x \notin K$, there exists $\delta>0$ (independent on $n$) such that $\delta \leq |\lambda_n| \leq 1$. Therefore, there exists a subsequence $(\lambda_{\sigma(n)})$ converging to some $\lambda \neq 0$.

Again by compactness, the sequence $(\lambda_{\sigma(n)} \cdot x_n-x)$ has a subsequence $(\lambda_{\sigma \circ \mu(n)} \cdot x_{\mu(n)}-x)$ converging to some $y \in K$.

Therefore, the sequence $(x_{\mu(n)})$ converges to $\frac{1}{\lambda} \cdot (y-x)$, a contradiction with $\|x_n-x_m\| \geq \frac{1}{2}$ when $n \neq m$. $\square$

Theorem 3: For all $n \geq 2$, the $n$-dimensional sphere $\mathbb{S}^n$ is simply connected but not contractible.

According to the following lemma, our theorem is just a consequence of Brouwer’s fixed point theorem, proved in a previous post about topological degree theory:

Lemma 2: Let $X$ be a normed space. The following statements are equivalent:

1. The unit sphere $\mathbb{S}$ is not contractible,
2. Any continuous map $\mathbb{B} \to \mathbb{B}$ has a fixed point,
3. $\mathbb{S}$ is not a retract of the unit ball $\mathbb{B}$.

Proof. Suppose that there exists a continuous map $f : \mathbb{B} \to \mathbb{B}$ without fixed point. Then

$H : (t,x) \mapsto \left\{ \begin{array}{cl} \displaystyle \frac{x-2tf(x)}{\|x-2tf(x)\|} & \displaystyle \text{if} \ 0 \leq t \leq \frac{1}{2} \\ \displaystyle \frac{(2-2t)x-f((2-2t)x)}{\|(2-2t)x-f((2-2t)x)\|} & \displaystyle \text{if} \ \frac{1}{2} \leq t \leq 1 \end{array} \right.$

defines a homotopy between $\mathrm{Id} : \mathbb{S} \to \mathbb{S}$ and $x \mapsto \frac{f(0)}{\|f(0)\|}$, so $\mathbb{S}$ is contractible. We proved $(1) \Rightarrow (2)$

Suppose that there exists a retraction $r : \mathbb{B} \to \mathbb{S}$. Then $f : x \mapsto -r(x)$ has no fixed point. Indeed, if $x_0 \in \mathbb{B}$ were a fixed point, we would have $x \in - r(\mathbb{B})=\mathbb{S}$ hence $r(x)=x$ whereas $r(x)=-x$ by assumption; therefore, $x=0$ a contradiction with $x \in \mathbb{S}$. We proved $(2) \Rightarrow (3)$.

Suppose that there exists a homotopy $H : [0,1] \times \mathbb{S} \to \mathbb{S}$ between $\mathrm{Id} : \mathbb{S} \to \mathbb{S}$ and a constant map $H(0, \cdot) : x \mapsto x_0$. Then

$r : x \mapsto \left\{ \begin{array}{cl} x_0 & \displaystyle \text{if} \ \|x\| \leq \frac{1}{2} \\ \displaystyle H \left( 2 \|x\| -1, \frac{x}{\|x\|} \right) & \displaystyle \text{if} \ \|x\| \geq \frac{1}{2} \end{array} \right.$

defines a retraction of $\mathbb{B}$ onto $\mathbb{S}$. We proved $(3) \Rightarrow (1)$. $\square$

In order to opposite our theorem with a statement in infinite dimension, we want to introduce an infinite-dimensional sphere $\mathbb{S}^{\infty}$. A possible construction is the following:

Defintion: Let $\mathbb{R}^{\infty}$ be the direct sum of countably many copies of $\mathbb{R}$ endowed with the norm $\displaystyle \| \cdot \| : (x_1,x_2, \dots) \mapsto \left( \sum\limits_{i \geq 1} x_i^2 \right)^{1/2}$. Then we define $\mathbb{S}^{\infty} = \{x \in \mathbb{R}^{\infty} \mid \|x\|=1\}$.

Theorem 4: The infinite-dimensional sphere $\mathbb{S}^{\infty}$ is contractible.

Proof. First, with

$H_1 : (t,x) \mapsto (1-t)(x_1,x_2, \dots)+t(0,x_1,x_2, \dots)$,

the map $\displaystyle \frac{H_1}{\|H_1\|}$ defines a homotopy between the identity $\mathrm{Id} : \mathbb{S}^{\infty} \to \mathbb{S}^{\infty}$ and the shift operator $S : (x_1,x_2,\dots) \mapsto (0,x_1,x_2,\dots)$. Then, with

$H_2 : (t,x) \mapsto (1-t) (0,x_1,x_2,\dots)+t(1,0,0, \dots)$,

the map $\displaystyle \frac{H_2}{\|H_2\|}$ defines a homotopy between $S$ and the constant map $x \mapsto (1,0,\dots)$.

Therefore, $\mathrm{Id} : \mathbb{S}^{\infty} \to \mathbb{S}^{\infty}$ is homotopic to $x \mapsto (1,0,\dots)$, ie. $\mathbb{S}^{\infty}$ is contractible. $\square$

To understand theorem 4, we may notice that $\mathbb{S}^{\infty}= \bigcup\limits_{n \geq 1} \mathbb{S}^n$ where $\mathbb{S}^n$ is included into $\mathbb{S}^{n+1}$ thanks to $(x_1, \dots, x_n) \mapsto (x_1, \dots, x_n,0)$; in particular, $\mathbb{S}^n$ is a subcomplex of $\mathbb{S}^{n+1}$. Then, because attaching a $m$-cell to a CW complex does not change the $n$-th homotopy group when $m>n$, we deduce that

$\pi_n(\mathbb{S}^{\infty})= \pi_n(\mathbb{S}^{n+1})=0$,

that is $\mathbb{S}^{\infty}$ is weakly contractible. However, according to Whitehead theorem, a weakly contractible CW complex is in fact contractible, so $\mathbb{S}^{\infty}$ is contractible.

Therefore, intuitively, we add cells to $\mathbb{S}^1$ to kill successively the homotopy groups in order to make $\mathbb{S}^{\infty}$ weakly contractible and finally contractible.