\documentclass[11pt]{smfart}
\usepackage{graphicx}
\usepackage{amssymb}
\usepackage{isolatin1}

\newtheorem{theorem}{Théorème}
%\newtheorem{corollary}[theorem]{Corollary}

\def\lu{\lambda_{1}}
\def\sll{\mathcal{S}_{\ell}}

\title{Groupes aléatoires}
\author{Pierre Pansu}
\begin{document}
\maketitle

\section{Introduction}

L'étude des groupes donnés par une présentation, née au début du 20ème siècle dans un contexte algébrique, a été relancée dans la seconde moitié du 20ème siècle par l'essor de la topologie différentielle : le groupe fondamental s'est révélé l'obstacle principal au programme de classification des variétés compactes. De mon point de vue, cette étude constitue aussi un pas de plus dans la démarche millénaire des géomètres, qui est d'envisager la géométrie euclidienne non pas isolément, mais au sommet d'une hiérarchie de géométries de moins en moins symétriques. Ainsi il est enrichissant de passer des pavages euclidiens aux pavages non euclidiens puis aux pavages abstraits associés aux présentations finies de groupes.

L'apparente simplicité du procédé qui produit un groupe à partir d'une présentation est trompeuse.
Le problème général de savoir quelles présentations $\langle S\mid R\rangle$ définissent des groupes non triviaux est \emph{indécidable}, \cite{Rabin}. Chaque progrès sur un problème particulier est un tour de force. Par exemple, le problème de Burnside (un groupe ayant un nombre fini de générateurs dans lequel toutes les puissances $N$-èmes sont égales à l'identité est il fini ?), déjà posé en 1902, a résisté jusqu'en 1968, \cite{AdianNovikov}.

C'est pourquoi l'idée avancée dès 1987 par Misha Gromov qu'on puisse choisir une présentation finie d'un groupe au hasard et trouver un groupe non trivial est révolutionnaire. Elle se fonde sur l'observation qu'un groupe hyperbolique supporte bien les relations supplémentaires. Cette idée féconde (elle a conduit à la résolution presque complète du problème de Burnside, \cite{IO}), Gromov la développe encore pour construire des groupes ``sur mesure''. Ce qui se dessine, c'est une ingéniérie en théorie des groupes.

Ce bref exposé est largement inspiré du Séminaire Bourbaki d'Etienne Ghys portant le même titre, \cite{Ghys}.

\section{Groupes et géométries}

Les groupes dont il est question dans cet exposé sont discrets et infinis. Le prototype en est le groupe des symétries d'un pavage.

\subsection{Pavages et présentations}

Prenons le pavage du plan euclidien représenté sur la figure \ref{gralpav}.
\begin{figure}
\begin{center}
\includegraphics[width=3in]{gralpav.eps}
\caption{Un pavage du plan euclidien}
\label{gralpav}
\end{center}
\end{figure}
Les seules isométries du plan qui le préservent sont des translations. Elles s'obtiennent en combinant deux translations élémentaires $a$ (la translation d'un pavé vers la droite), $b$ (la translation d'un pavé vers le haut) et leurs inverses $a^{-1}$ et $b^{-1}$. On dit que le groupe $G$ des symétries du pavage est \emph{engendré} par $a$ et $b$. Ces translations commutent : $ab=ba$. On montre aisément que toute relation entre $a$ et $b$ (i.e. tout mot écrit avec les lettres $a$, $b$, $a^{-1}$ et $b^{-1}$ qui correspond à l'isométrie identité du plan) se ramène à l'unique relation  $aba^{-1}b^{-1}=e$. En effet, en faisant commuter $a$ et $b$, on réécrit tout mot sous la forme $a^{n}b^{m}$ où $n$ et $m$ sont des entiers relatifs. Un tel mot agit sur le plan par l'identité seulement si $n=m=0$. Autrement dit, le groupe abstrait infini $G$ (c'est le groupe abélien libre à deux générateurs) peut être décrit par des données finies : deux \emph{générateurs} $a$ et $b$ et un \emph{relateur} $aba^{-1}b^{-1}$. On dit que $G$ admet une \emph{présentation finie}.

\bigskip

Cette propriété est partagée par tous les groupes de symétries de pavages, lorsqu'un nombre fini de pavés et leurs images par des symétrie du pavage suffisent à recouvrir l'espace. Par exemple, la figure \ref{gralkang} représente un pavage du plan hyperbolique dont le groupe de symétrie est engendré par trois rotations $r$, $s$ et $t$ sujettes à des relations engendrées par les relateurs $r^{4}$, $s^{3}$ et $t^{3}$.
\begin{figure}
\begin{center}
\includegraphics[width=2in]{gralkang.ps}
\caption{Un pavage du plan hyperbolique}
\label{gralkang}
\end{center}
\end{figure}

Pour la même raison, le groupe fondamental d'un polyèdre fini ou d'une variété compacte admet des présentations finies.

Inversement, on peut se donner abstraitement un groupe par une présentation $\langle S\mid R\rangle$. Ici $S$ est un ensemble fini interpreté comme un ensemble de lettres, et $R$ un ensemble fini de mots écrits au moyen de l'alphabet $S\cup S^{-1}$. Le groupe associé est le quotient du groupe libre formé sur $S$ par le sous-groupe distingué engendré par $R$. Comme les mots ne manquent pas, il n'est pas surprenant que cette construction fournisse des groupes très variés. 

\subsection{Pavage abstrait associé à une présentation}

A la suite de Felix Klein, on a coutume de penser que faire de la géométrie, c'est étudier un groupe (en général, on pense à un groupe continu). Inversement, il est utile d'associer une géométrie à un groupe. 

Pour un groupe $G$ de présentation finie, le \emph{polyèdre de Cayley} associé à une présentation $\langle S\mid R\rangle$ est d'usage courant. Il est construit comme suit. On part du graphe $g$ ayant un sommet et autant d'arêtes qu'il y a d'éléments dans $S$. Chaque mot $m$ écrit au moyen de l'alphabet $S\cup S^{-1}$ est représenté par une courbe $f_{m}$ dans $g$. Pour chaque relateur $r\in R$, on colle une 2-cellule au graphe, au moyen d'une paramétrisation $f_{r}:S^{1}=\partial D^{2}\to g$. On obtient ainsi un polyèdre fini de dimension 2, dont le groupe fondamental est isomorphe à $G$. C'est son revêtement universel qu'on appelle \emph{polyèdre de Cayley} $P_{\langle S\mid R\rangle}$ associé à la présentation $\langle S\mid R\rangle$. Les sommets de ce polyèdre sont naturellement numérotés par les éléments du groupe $G$. Les arêtes sont numérotées par les éléments de $G\times S$ (l'arête $(\gamma,s)$ relie les sommets marqués $\gamma$ et $\gamma s$). Si $s\in S$, on convient d'étiqueter d'un $s^{-1}$ l'arête $(\gamma,s)$ lorsqu'elle est parcourue de $\gamma s$ vers $\gamma$. Les 2-cellules sont numérotées par les éléments de $G\times R$ (le bord de la 2-cellule $(\gamma,r)$ est le chemin qui part du sommet $\gamma$ et suit des arêtes etiquetées par les lettres du mot $r$). 

Le polyèdre de Cayley est pavé par ses 2-cellules, et le groupe $G$ est contenu dans le groupe de symétrie de ce pavage.

\bigskip

La figure \ref{gralgrille} représente le polyèdre de Cayley associé à la présentation $\langle a,b\mid aba^{-1}b^{-1}\rangle$ du groupe abélien libre à deux générateurs. Ce n'est autre que le plan pavé par des carrés. On a indiqué les quatre arêtes orientées issues de l'origine $e$.
\begin{figure}
\begin{center}
\includegraphics[width=2in]{gralgrille.eps}
\caption{Polyèdre de Cayley}
\label{gralgrille}
\end{center}
\end{figure}

\subsection{Un exemple de problème géométrique}

Que signifie faire de la géométrie sur un polyèdre de Cayley ? Voici un exemple, le problème isopérimétrique. 

Etant donnée une courbe fermée formée d'arêtes, chercher à la remplir par un disque (réunion de 2-cellules) d'aire minimale (ici, l'aire est le nombre de 2-cellules utilisées), se demander comment cette aire dépend de la longueur de la courbe (ici, la longueur est le nombre d'arêtes). La fonction qui à un nombre positif $L$ associe la plus grande aire de remplissage des courbes de longueur inférieure ou égale à $L$ s'appelle la \emph{fonction de Dehn} $F_{\langle S\mid R\rangle}$ de la présentation. 

Dans le plan pavé par des carrés, il est enfantin de voir que les courbes les plus difficiles à remplir sont des grands carrés ou des rectangles proches de carrés, voir figure \ref{gralisop}. 
\begin{figure}
\begin{center}
\includegraphics[width=1.5in]{gralisop.eps}
\caption{Deux solutions du problème isopérimétrique dans le plan pavé par des carrés}
\label{gralisop}
\end{center}
\end{figure}
Par conséquent,
\begin{displaymath}
F_{\langle a,\,b\mid aba^{-1}b^{-1}\rangle}(L)\sim \frac{1}{4}L^{2}.
\end{displaymath}

\bigskip

Attention, changer de présentation du groupe modifie le polyèdre. Par exemple, le groupe abélien libre à deux générateurs admet une présentation à trois générateurs et deux relateurs $\langle a,\,b,\,c\mid abc,\,bac\rangle$ dont le polyèdre de Cayley est le plan pavé par des triangles équilatéraux. La fonction de Dehn reste quadratique, $F_{\langle a,\,b,\,c\mid abc,\,bac\rangle}\sim \frac{1}{6}L^{2}$, mais la constante change. La géométrie associée au groupe n'est unique que si l'on n'est pas trop pointillieux~: il faut être tolérant sur les constantes, par exemple.

\bigskip

Voici quelques résultats sur les fonctions de Dehn des groupes de présentation finie.
\begin{enumerate}
  \item Pour les pavages euclidiens, $F$ est quadratique.
  \item Pour les pavages hyperboliques, $F$ est linéaire.
  \item Il existe des groupes de présentation finie dont la fonction de Dehn n'est pas récursive, \cite{PNovikov}, \cite{Boone}. 
  \item Une fonction de Dehn est ou bien linéaire, ou bien au moins quadratique, \cite{Gromov87}.
  \item L'énoncé 4 est probablement la seule restriction quantitative sur les fonctions de Dehn, \cite{BORS}.

\end{enumerate}
Il y a donc une grande diversité dans les fonctions de Dehn. Quel est le comportement typique ? Gromov propose une réponse à cette question.


\section{Choisir des relateurs au hasard}

Nous allons décrire le modèle probabiliste choisi par Gromov en 1993, \cite{Gromov93}. 

\subsection{Modèle à densité}

Fixons l'alphabet $S$. Tirer un ensemble $R$ de relateurs au hasard, c'est tirer indépendamment des éléments dans le groupe libre sur $S$. Faute de mesure de probabilité naturelle sur le groupe libre, on choisit, pour chaque rayon $\ell>0$, de tirer de façon équiprobable des éléments dans une couronne 
\begin{displaymath}
\mathcal{S}_{\ell}=\{\ell-\epsilon<|r|<\ell+\epsilon\}
\end{displaymath}
de rayon $\ell$ du groupe libre.

On a l'intuition que le nombre de relateurs va jouer un rôle essentiel : si on met beaucoup de relateurs, il y a toutes les chances que le groupe obtenu soit trivial. Précisons : si $R_{1}$ et $R_{2}$ sont deux sous-ensemble de $\sll$ de même cardinal $N$, alors dès que $N>\sqrt{\#\sll}$, avec une forte probabilité, $R_{1}\cap R_{2}\not=\emptyset$. Par conséquent, si $s$ est un générateur, si $R$ est tiré au hasard et si $\# R>\sqrt{\#\sll}$, alors $sR\cap R\not=\emptyset$, donc $s$ appartient au sous-groupe engendré par $R$, avec une forte probabilité. Par conséquent, le groupe associé à la présentation $\langle S\mid R\rangle$ est trivial, avec une probabilité tendant vers 1 quand $\ell$ tend vers l'infini.

On voit qu'il convient de mesurer les sous-ensembles (tirés au hasard) de $\sll$ par leur \emph{densité}
\begin{displaymath}
d(R)=\frac{\log(\# R)}{\log(\#\sll)}
\end{displaymath}
plutôt que par leur cardinal. 

Soit $d$ un réel compris entre 0 et 1. On dira qu'une propriété des groupes est \emph{générique en densité $d$} si la probabilité qu'elle soit satisfaite pour le groupe associé à une présentation $\langle S\mid R\rangle$ où $R$ est tiré au hasard parmi les sous-ensembles de $\sll$ de densité $d$ tend vers 1 lorsque $\ell$ tend vers l'infini.

\begin{theorem}
\label{93}
(M. Gromov, \cite{Gromov93}, \cite{Ollivier_spt}). Si $d>1/2$, un groupe générique en densité $d$ est trivial. Si $d<1/2$, un groupe générique en densité $d$ est infini et a une fonction de Dehn linéaire.
\end{theorem}

La preuve consiste à montrer qu'une combinatoire (graphe planaire) donnée est réalisable par un disque dans le groupe quotient, avec une probabilité non négligeable, seulement si celle-ci satisfait l'inégalité isopérimétrique
\begin{displaymath}
A\leq \frac{1}{(1-2d)\ell}L
\end{displaymath}
où $A$ est le nombre de 2-cellules et $L$ la longueur (nombre d'arêtes) du bord. Pour cela, on compte inconnues et équations \emph{en termes de densité} relativement à $\#\sll$. Les inconnues sont des relateurs à écrire le long du bord de chaque 2-cellule. En densité $d$, elles sont au nombre de $dA$. Chaque arête \emph{interne} du graphe planaire impose une égalité de lettres entre deux relateurs de longueur $\ell$, ce qui compte pour $1/\ell$. Le nombre total d'équations imposées par la combinatoire du graphe est donc $\ell'/\ell$ où $\ell'$ désigne la longueur des arêtes internes (voir figure \ref{gralaretes}. 
\begin{figure}
\begin{center}
\includegraphics[width=2in]{gralaretes.eps}
\caption{Arêtes internes d'un graphe planaire}
\label{gralaretes}
\end{center}
\end{figure}
Comme la longueur cumulée des bords des 2-cellules vaut $A\ell=L+2\ell'$, le nombre de $A$-uplets de relateurs solutions vaut
\begin{displaymath}
dA-\frac{\ell'}{\ell}=\frac{L}{2\ell}-A(\frac{1}{2}-d)
\end{displaymath}
qui est négatif si $A> \frac{1}{(1-2d)\ell}L$. On montre ainsi que, étant donné une constante $C$, dans un groupe générique en densité $d<1/2$, tous les disques d'aire $<C$ satisfont l'inégalité isopérimétrique $A\leq \frac{1}{(1-2d)\ell}L$. Cela entraîne, par un passage du local au global généralisant le théorème de Cartan-Hadamard, \cite{Gromov87}, \cite{Papa}, qu'une inégalité isopérimétrique linéaire est satisfaite par tous les disques.

\subsection{Transition de phase}

Les groupes dont la fonction de Dehn est linéaire sont appelés groupes \emph{hyperboliques au sens de Gromov}, car ils partagent la plupart des propriétés communes aux groupes de symétries des pavages hyperboliques. Un groupe générique est donc trivial en densité $>1/2$, hyperbolique et infini en densité $<1/2$.

Le théorème \ref{93} suggère l'existence d'une transition de phase. En utilisant, pour tester si le groupe associé à une présentation est trivial ou hyperbolique, l'algorithme de \cite{Papa} et son implémentation \cite{HR}, Richard Kenyon a mené des expérimentations numériques. Il a constaté, dans un modèle un peu différent, l'existence d'une zone critique pour la densité de relateurs, en dehors de laquelle le test donne rapidement une conclusion : le groupe est hyperbolique infini s'il y a peu de relateurs, le groupe est trivial sinon. Au voisinage de la zone critique, le test met un temps très long (parfois trop long) à conclure. Toutefois, l'ordre de grandeur de $\ell$ dans ces expérimentations reste trop faible pour localiser précisément la valeur critique de la densité.

D'autre part, en physique statistique, on classifie les transitions de phases suivant le comportement (continuïté, dérivabilité au paramètre critique) de grandeurs macroscopiques en fonction du paramètre. Ces idées s'appliquent aussi en informatique, \cite{BCM}. Pour l'instant, dans le contexte des présentations de groupes, il n'y a aucune grandeur numérique dont on sache évaluer la valeur pour une présentation aléatoire.

En fait, le résultat le plus prometteur dont on dispose actuellement dans cette direction est le théorème suivant.

\begin{theorem}
\label{zuk}
(M. Gromov, A. Zuk \cite{Zuk})  Si $d>1/3$, un groupe générique en densité $d$ possède la propriété (T) de Kazhdan : toute action isométrique sur un espace de Hilbert affine possède un point fixe.
\end{theorem}

On connait peu d'autres propriétés génériques des groupes. On sait que la dimension homologique d'un groupe générique est 2. Cela entraîne que même parmi les groupes hyperboliques, ceux qu'on aime (les réseaux de groupes de Lie, leurs combinaisons), et qui ont une dimension $>2$ sont loin d'être génériques. On s'attend donc à un comportement étrange, gouverné par la densité. Peut-être les groupes génériques ont ils peu d'intérêt en eux-mêmes, et qu'il faut les voir comme des outils pour explorer d'autres groupes, comme les courbes aléatoires en géométrie et en analyse. C'est ainsi que des caractéristiques intéressantes des groupes, comme la croissance et la cocroissance, apparaissent lorsqu'on s'intéresse aux quotients génériques d'un groupe hyperbolique non nécessairement libre, voir \cite{Ollivier_spt}. 

\section{Des groupes sur mesure}

A l'instar de la théorie des graphes, la théorie des groupes peut tirer profit de méthodes probabilistes pour produire des exemples.

\subsection{Une question motivée par la topologie différentielle}

Une variété dont le groupe fondamental est non trivial possède des classes de cohomologie naturelles, obtenues en ramenant l'homologie de l'espace classifiant du groupe fondamental. Par exemple, si $\pi_{1}(M)=\mathbb{Z}$, alors $H^{1}(M,\mathbb{Z})=\mathbb{Z}$ vient avec un générateur préféré. En multipliant ces classes par les classes caractéristiques du fibré tangent, on obtient parfois des classes en dimension maximum, donc de nouveaux nombres caractéristiques. On appelle ces nombres les \emph{signatures d'ordre supérieur}. Sergei Novikov a montré que les nombres caractéristiques ordinaires sont des invariants d'homotopie orientée. La question de savoir si cette propriété s'étend aux signatures d'ordre supérieur est typique des problèmes sur lesquels la topologie différentielle a buté dans les années 1960, \cite{SNovikov}.

Au début des années 1980, Paul Baum et Alain Connes ont englobé ce problème dans un problème plus vaste, formulé dans le langage des $C^{*}$-algèbres réduites de groupes discrets, \cite{BaumConnes}. La conjecture de Baum-Connes a été résolue pour diverses classes de groupes discrets, voir \cite{Skandalis}. La classe figurant dans le théorème de Gaoliang Yu, \cite{Yu}, est celle des groupes qui possèdent un \emph{plongement uniforme} dans un espace de Hilbert. Par plongement uniforme, on entend une application $f$ du polyèdre de Cayley $P$ vers un espace de Hilbert $\mathcal{H}$ telle qu'il existe deux fonctions $\phi$ et $\psi$ tendant vers l'infini telles que pour tous sommets $\gamma$, $\gamma'$,
\begin{displaymath}
\phi(d^{P}(\gamma,\gamma'))\leq d^{\mathcal{H}}(f(\gamma),f(\gamma'))\leq \psi(d^{P}(\gamma,\gamma'))).
\end{displaymath}

Récemment, Gromov a construit des exemples de groupes de présentation finie qui n'admettent pas de plongement uniforme dans un espace de Hilbert, \cite{Gromov02}. Ces groupes constituent des contre-exemples à certains avatars de la conjecture de Baum-Connes, \cite{HLS}, mais pas encore à celle de Novikov.

On connait depuis longtemps (\cite{Enflo}) des espaces métriques qui se plongent mal dans les espaces de Hilbert, ce sont les \emph{expanseurs}. Un \emph{expanseur}, c'est une suite de graphes finis de valences bornées, dont le nombre de sommets tend vers l'infini, et dont le bas du spectre est borné inférieurement. De telles suites existent, on les trouve en tirant des graphes au hasard. Il existe aussi des constructions déterministes, voir \cite{Lubotzky}.

L'idée de Gromov est de construire des présentations dont le \emph{graphe de Cayley} (c'est la réunion des arêtes du polyèdre de Cayley) contient un expanseur.


\subsection{Plonger des graphes dans des groupes}

Comment construire des groupes dont le graphe de Cayley contient un graphe donné ? Gromov a introduit récemment le procédé suivant.

Soit $g$ un graphe fini. On \emph{étiquette} $g$ en associant à chaque arête orientée de $g$ une lettre choisie dans un alphabet fini $S$, de sorte que renverser l'orientation d'une arête change l'étiquette $s$ en $s^{-1}$. En parcourant un chemin dans $g$, on lit un mot. On note $R$ l'ensemble des mots lus le long de cycles de $g$. On s'intéresse au groupe $G$ de présentation $\langle S\mid R\rangle$. 

Le graphe $g$ s'envoie dans le graphe de Cayley de $G$ : il suffit de fixer une origine dans $g$ et de relever les chemins issus de l'origine en lisant les mots. Gromov donne une condition suffisante pour que l'application obtenue soit injective. Elle s'inspire de la notion de \emph{petite simplification}.

\subsection{Petite simplification}

C'est une idée géométrique qui remonte aux années 1940 : si les relateurs d'une présentation ne présentent pas de trop grandes pièces communes, alors le groupe associé est hyperbolique. 

En effet, considérons un disque dans le polyèdre de Cayley, obtenu comme réunion de 2-cellules. Si chaque 2-cellule n'a en commun avec une cellule voisine qu'une proportion $<\lambda$ de la longueur de son bord, alors une 2-cellule interne est entourée d'au moins $1/\lambda$ autres cellules, voir figure \ref{gralsimpl}. 
\begin{figure}
\begin{center}
\includegraphics[width=2in]{gralsimpl.eps}
\caption{Disque dans un groupe à petite simplification}
\label{gralsimpl}
\end{center}
\end{figure}
Si $\lambda<1/6$, la triangulation duale est à courbure négative, elle ressemble à un pavage hyperbolique, donc son aire est linéaire par rapport à la longueur de son bord.

Dans notre situation, on appelle \emph{pièce} d'un graphe étiqueté $g$ une paire de sous-graphes étiquetés de $g$, isomorphes mais distincts. On dit que le graphe étiquetté $g$ vérifie la condition de \emph{petite simplification} $C'(\lambda)$ si le diamètre de toute pièce est au plus $\lambda$ fois le \emph{tour de taille} de $g$, i.e. la plus petite longueur d'un cycle de $g$.

\begin{theorem}
\label{thsimpl}
(Gromov, \cite{Gromov02}). 
Soit $g$ un graphe étiqueté vérifiant la condition de petite simplification $C'(1/6)$. Alors le groupe $G$ associé est hyperbolique infini, et son graphe de Cayley contient une copie isométrique de $g$.
\end{theorem}

Etant donné un graphe $g$, on a le choix de l'étiquetage. Il se trouve que si un graphe $g$ a un grand tour de taille (du même ordre que son diamètre), alors, en subdivisant suffisamment ses arêtes, puis en tirant un étiquetage au hasard, on obtient avec une grande probabilité un graphe qui vérifie la condition de petite simplication $C'(1/6)$.

Pour plonger un second graphe fini dans un graphe de Cayley, on voudrait appliquer le théorème \ref{thsimpl} une première fois, puis l'appliquer à nouveau au groupe obtenu. Pour cela, il faut une version du théorème \ref{thsimpl} relative à un groupe hyperbolique. Yann Ollivier en a donné une preuve détaillée, \cite{Ollivier_sc}.

On obtient ainsi un groupe, limite de groupes hyperboliques, dont le graphe de Cayley contient (approximativement) un expanseur. Il est de présentation infinie mais récursive, donc se plonge dans un groupe de présentation finie, qui est l'exemple recherché.

\subsection{Des groupes non linéaires}

Le modèle ``à graphe'' de groupe aléatoire généralise le modèle ``à densité''. En effet, ce dernier consiste à choisir comme graphe un bouquet de cercles tous subdivisés en $\ell$ arêtes. Le théorème \ref{zuk} s'étend aux groupes aléatoires modelés sur des expanseurs, mais avec une preuve différente. Celle-ci donne une version non linéaire de la propriété (T) de Kazhdan, plus forte que la superrigidité de Margulis : toute action isométrique sur un polyèdre à courbure négative ou nulle, à singularités bornées, possède un point fixe. Un tel groupe ne possède aucune représentation linéaire de dimension finie hormis celles factorisant par (d'improbables) quotients finis. Ceci confirme le caractère déroutant des groupes tirés au hasard. Doit on y voir une limite du modèle probabiliste (les deux modèles imposent des restrictions fortes sur les longueurs des relations) ?

\bibliographystyle{plain}
\bibliography{gral}

\par\medskip\noindent
Pierre Pansu\\
Laboratoire de Math\'ematique d'Orsay\\
UMR 8628 du C.N.R.S.\\
B\^atiment 425\\
Universit\'e Paris-Sud - 91405 Orsay (France)\\
\smallskip\noindent
{\tt\small Pierre.Pansu@math.u-psud.fr}\\
http://www.math.u-psud.fr/$\sim$pansu
 \end{document}



\subsection{Expanseurs}
La question se pose de savoir s'il existe des groupes ne possèdant aucun plongement uniforme dans un espace de Hilbert. On connait depuis longtemps (\cite{Enflo}) des espaces métriques qui se plongent mal dans les espaces de Hilbert, ils sont construits à partir d'\emph{expanseurs}.

Commençons par définir le \emph{bas du spectre} $\lu$ d'un graphe fini $g$. Le \emph{laplacien} sur $g$ est l'opérateur symétrique sur l'espace des fonctions sur les sommets de $g$ défini comme suit. Si $x$ est un sommet, $f(x)-\Delta f(x)$ est la moyenne des valeurs de $f$ aux sommets voisins de $x$. On note $\lu(g)$ la plus petite valeur propre non nulle du laplacien sur $g$. C'est aussi la meilleure constante dans l'inégalité
\begin{displaymath}
\lu\sum_{\textrm{sommets}} v(\gamma)|f(\gamma)|^{2}\leq \sum_{\textrm{arêtes}}|f(\gamma')-f(\gamma)|^{2}
\end{displaymath}
pour les fonctions $f$ de moyenne nulle.

Un \emph{expanseur}, c'est une suite de graphes de valences bornées, dont le nombre de sommets tend vers l'infini, et dont le bas du spectre est borné inférieurement. De telles suites existent, on les trouve en tirant des graphes au hasard. Il existe aussi des constructions déterministes.

Soit $g$ un graphe de valence $v\leq V$, ayant $s$ sommets, et soit $f:g\to\mathcal{H}$ est une application à valeurs dans un espace de Hilbert. Quitte à effectuer une translation et une homothétie, on peut supposer que la moyenne de $f$ sur les sommets est nulle, et que la distance entre les images des extrémités de toute arête est inférieure à 1. Montrons qu'il existe des sommets éloignés dans $g$ dont les images sont proches. Par définition du bas du spectre,
\begin{eqnarray*}
\frac{1}{s^{2}}\sum_{\textrm{paires de sommets}}|f(\gamma')-f(\gamma)|^{2}
&=&
\frac{2}{s}\sum_{\textrm{sommets}}|f(\gamma)|^{2}\\
&\leq&\frac{2}{s}\sum_{\textrm{sommets}}v(\gamma)|f(\gamma)|^{2}\\
&\leq &\frac{2}{\lu(g)s}\sum_{\textrm{arêtes}}|f(\gamma')-f(\gamma)|^{2}\\
&\leq &\frac{2V}{\lu(g)}.
\end{eqnarray*}
Le nombre de paires de sommets à distance mutuelle $\leq k$ est au plus $V^{k+1}s$. Si $k=\log(s/2)/\log(V)$, il existe une paire telle que $d(\gamma,\gamma')>k$ et $|f(\gamma')-f(\gamma)|^{2}\leq \frac{4V}{\lu(g)}$. Il en résulte que la réunion d'une suite de graphes formant un expanseur n'admet pas de plongement uniforme dans un espace de Hilbert.


