Imaginez que vous avez deux cartes du Québec, l’une par-dessus l’autre. Vous prenez celle du dessus que vous déformez en la froissant, tournant, retournant et pliant comme vous voulez, et vous la déposez à nouveau sur l’autre carte, sans qu’elle dépasse. Alors, il y a toujours au moins un point de la carte déformée qui est exactement au-dessus du même point sur la carte du dessous. Surprenant?
Transformation topologique
Lorsque l’on déforme une carte sans la déchirer, la fonction qui décrit la transformation est continue. Intuitivement, on voit que si deux points sont près l’un de l’autre sur la carte initiale, alors ils sont toujours près l’un de l’autre après la déformation de la carte. Si la carte est imprimée sur une surface malléable que l’on peut étirer (comme un tissu élastique) ou même contracter (comme une mince couche de pâte à modeler), et que l’on permet en plus d’étirer ou de contracter certaines parties de la carte, la transformation est toujours continue: il s’agit d’une transformation topologique.
Lorsque l’on dépose la carte déformée sur la carte initiale, sans qu’elle dépasse, alors il y a toujours au moins un point de la carte déformée qui est exactement au-dessus du même point sur la carte du dessous. Ce résultat est un exemple d’application du Théorème du point fixe de Brouwer, lequel a de nombreuses applications. (Voir l’encadré Un résultat aux multiples ramifications.)
Point fixe d’une fonction
Point fixe d’une fonction
Pour une fonction f d’un ensemble E vers lui-même, un point P est fixe si f(P) = P.
Dans l’exemple de la carte du Québec, où chaque point de la carte déformée se trouve au-dessus d’un point P’ de la carte du dessous,la fonction f est définie par f(P)=P’. Le fait que les déformations permises de la carte donnent une fonction f continue est essentiel. Si on déchire la carte, le résultat ne tient plus.
Si le domaine n’est pas borné, une fonction, même continue, n’a pas nécessairement de point fixe. Par exemple, la fonction \(f (x) = x^2 + 1/4\) définie sur les nombres réels possède un point fixe \((x = 1/2,\) car \(f (1/2) = 1/2)\) alors que la fonction \(f (x) = x^2 + 1\) n’en a pas (toujours sur les nombres réels).
Pour garantir l’existence d’un point fixe, le théorème de Brouwer demande que la fonction continue soit définie sur un domaine borné et qui inclut sa frontière. Mais il doit aussi être sans trou. Par exemple, la rotation d’un quart de tour d’un anneau est une transformation continue qui n’a pas de point fixe.
Théorème du point fixe de Brouwer (dans le plan)
Soit E une région bornée du plan, délimitée par une courbe comme un cercle où un polygone, qui inclut sa frontière et n’ayant pas de trou. Alors toute fonction continue \(f: E \to E\) possède au moins un point fixe P.
Un résultat aux multiples ramifications
Le Théorème de Brouwer a de nombreuses applications, dans des domaines variés. On peut l’utiliser pour démontrer un résultat sur les matrices (le théorème de Perron-Frobenius) qui est au cœur de l’algorithme Pagerank utilisé par Google. Il est aussi utile pour démontrer le Théorème de Jordan, un résultat topologique fondamental, dont l’énoncé semble à ce point évident que l’on peut se demander ce qu’il y a à prouver. Dans sa formulation naïve, le Théorème de Jordan dit qu’une courbe fermée simple dans le plan le divise en deux parties dont cette courbe est la frontière, et que l’une de ces parties est bornée et l’autre pas. Pour être précis, il faut définir correctement ce qu’est une courbe fermée simple: la continuité joue ici un rôle, et l’intuition initiale qui rendait le résultat évident ne permet pas de démontrer le théorème facilement.
En généralisant le résultat de Brouwer, Kakutani a obtenu le théorème de point fixe qui porte son nom, et dont John Forbes Nash Jr a fait usage pour ses travaux portant sur ce que l’on appelle maintenant l’équilibre de Nash. Rappelons que Nash, qui a obtenu le Prix Nobel d’économie en 1994, est le mathématicien dont la biographie a été adaptée pour produire le film Un homme d’exception.
Démontrer un tel résultat n’est pas évident car on connaît très peu de choses sur la transformation de la carte: froisser, plier, retourner, ce n’est pas très bien défini mathématiquement, enfin, pas dans le sens habituel. Où sont les coordonnées? Où est la formule? L’important ici n’est pas que la fonction nous soit donnée sous une forme particulière mais bien qu’elle soit continue: par exemple, on ne peut permettre de déchirer la carte, car à ce moment le résultat n’est plus vrai.
Tout cela est bien beau, mais comment alors prouver le Théorème du point fixe de Brouwer?
Triangle et point fixe
Pour prouver le Théorème du point fixe dans le plan, il suffit de le démontrer dans le cas où E est la région formée par un triangle et son intérieur. On peut en effet transformer de manière continue en un triangle une région qui respecte les conditions énoncées dans le Théorème de Brouwer, et ainsi se ramener à une fonction continue f du triangle ABC vers lui-même. (Voir l’encadré Un triangle suffit.) On veut donc montrer qu’une fonction continue f d’un triangle dans lui-même possède un point fixe, c’est-à-dire un point P tel que f(P) = P.
Un triangle suffit
Si on a une région plane E dont la frontière est une courbe qui est suffisamment régulière, alors on peut la déformer de manière continue pour obtenir un triangle T. Plus précisément, il existe une fonction continue \(g: T \to E\) dont l’inverse \(g^{-1}: E \to T\) est aussi une fonction continue, tel que montré sur le diagramme ci-contre.
Pour montrer que \(f: E \to E\) possède un point fixe, il suffit alors de considérer la fonction \(F = g^{-1}\circ f\circ g,\) qui va de T vers T. Si on trouve un point P tel que \(F(P) = P\), alors on a que \(Q = g(P)\) est un point fixe de f. En effet comme \(F = g^{-1}\circ f\circ g\) alors \(g\circ F = f\circ g\) et donc:
\[g(P) = (g\circ F)(P) = (f\circ g)(P) = f(g(P)).\]
Coloriage et point fixe
En mathématiques, on s’intéresse depuis longtemps aux problèmes de coloriage. Cela peut paraître surprenant, et ce qui peut l’être encore plus, c’est que c’est utile! Le Lemme de Sperner en est un magnifique exemple. Il décrit des conditions qui garantissent l’existence d’un triangle ayant ses trois sommets de couleurs différentes, et nous allons voir comment l’utiliser pour prouver l’existence d’un point fixe pour toute fonction continue d’un triangle vers lui-même. Mais avant de l’utiliser, encore faut-il l’énoncer correctement.
Le Lemme de Sperner
On divise un triangle ABC en plusieurs petits triangles tel que sur le dessin ci-contre. (On a ce qu’on appelle une triangulation du triangle.) On colore A en rouge, B en bleu et C en jaune, et chacun des autres sommets en jaune, bleu ou rouge, avec la seule condition que les sommets sur le côté AC sont jaunes ou rouges, ceux sur le côté BC sont jaunes ou bleus, et ceux sur le côté AB sont rouges ou bleus. Les sommets intérieurs sont jaunes, bleus ou rouges, sans autre condition.
Le Lemme de Sperner affirme qu’il existe au moins un petit triangle qui a ses trois sommets de couleurs différentes: on le dira tricoloré. Sur la figure, le petit triangle bleu est tricoloré.
Trouver un triangle tricoloré
Lorsqu’il y a peu de triangles, on pourrait espérer trouver un argument qui permette de traiter tous les cas pour montrer qu’il existe au moins un triangle tricoloré. Mais que faire si on a plusieurs triangles? Pourriez-vous traiter tous les cas de coloriage de ce triangle? Et que dire si on a des millions de petits triangles?
La preuve du Lemme de Sperner utilise un joli argument de parité (voir l’encadré).
Balade dans la maison triangulaire
Pour montrer qu’il existe toujours au moins un triangle tricoloré, on considère que le triangle ABC est une maison, que chacun des petits triangles est une pièce dont les côtés sont les murs, et que tout segment reliant un sommet rouge et un sommet jaune est un mur ayant une porte.
On considère alors les pièces que l’on peut visiter en entrant dans la maison, sans revenir sur ses pas et sans passer deux fois par la même porte.
Chaque chemin possible débutant à l’extérieur doit passer par une porte pour rentrer dans la maison: on peut continuer le chemin et sortir de la pièce par une autre porte lorsque le triangle est coloré rouge – jaune – rouge; sinon, le chemin se termine et on est alors dans un triangle qui est tricoloré. Donc chaque chemin qui se termine à l’intérieur de la maison doit se terminer dans un triangle tricoloré.
Mais attention!, un chemin qui débute à l’extérieur peut ressortir de la maison en empruntant ainsi deux portes extérieures.
Comment alors montrer qu’il y a au moins un chemin qui se termine à l’intérieur de la maison?
Pair ou impair
On peut voir qu’il y a toujours un nombre impair de portes extérieures. En effet, comme le mur AC débute avec un sommet rouge A et termine avec un sommet jaune C, il y a un nombre impair de changements de couleurs entre des sommets consécutifs: s’il y en avait un nombre pair, les sommets A et C seraient de la même couleur.
Un chemin qui débute et se termine à l’extérieur emprunte deux portes extérieures. Puisque aucune pièce n’a trois portes, on ne peut avoir deux chemins différents qui passent par une même pièce: il n’y a jamais de choix. Comme il y a un nombre impair de portes extérieures, au moins un des chemins qui débute à l’extérieur doit se terminer dans une pièce intérieure – et on a gagné, car cette pièce doit être un triangle tricoloré!
Un coloriage à la Sperner
Pour prouver l’existence d’un point fixe pour toute fonction continue d’un triangle vers lui-même en utilisant le Lemme de Sperner, on veut un coloriage des points du triangle qui respecte les conditions du lemme tout en étant relié au comportement de la fonction f. Il y a plusieurs choix possibles, dont celui donné par l’algorithme suivant. (Voir les coordonnées barycentriques pour une définition plus rigoureuse.)
On colore les sommets: A en rouge, B en bleu et C en jaune.- Si f(X) se retrouve dans la région en rouge, on dit que f(X) s’éloigne A de A et on colore X en rouge (comme A). (La région ne contient pas le côté contenant X.)
- Si f(X) ne s’éloigne pas de A et qu’il s’éloigne de B (i.e. f(X) est strictement à gauche de la parallèle à AC par le point X), alors on colore X en bleu (comme B): f(X) sera en fait dans la région en bleu sur la figure.
- Si f(X) ne s’éloigne ni de A, ni de B, et qu’il s’éloigne de C, alors on le colore en jaune: il sera dans la région en jaune.
Si il y a un point X qui ne peut être coloré, c’est qu’il est fixe car il ne s’éloigne ni de A, ni de B, ni de C. Dans la suite, on supposera que les sommets des petits triangles considérés sont colorés: si un sommet ne peut être coloré, alors on a déjà un point fixe.
Notons que pour un point X sur le côté AB, il n’y a pas de région jaune et X est donc rouge ou bleu; de même, un point sur le côté AC est rouge ou jaune, et un point du côté BC est bleu ou jaune. Le coloriage respecte donc bien les conditions du Lemme de Sperner.
Coordonnées barycentriques
Pour un point X dans un triangle, on considère que les trois régions colorées représentent les points qui sont plus loin de A, plus loin de B et plus loin de C.
On peut définir précisément ces régions en utilisant les coordonnées barycentriques. Si on place le triangle dans un plan cartésien, on peut vérifier que tout point X du triangle peut être exprimé sous la forme
\[X = \alpha_1 A + \alpha_2 B + \alpha_3 C,\]
où les \(\alpha_i, = 1, 2, 3,\) sont positifs et de somme 1, ce que l’on note \(X(\alpha_1, \alpha_2, \alpha_3).\) Alors, un point \(Y(\beta_1, \beta_2, \beta_3)\) du triangle est dans la première région si \(\beta_1 < \alpha_1,\) dans la deuxième si \(\beta_2 < \alpha_2\) et dans la troisième si \(\beta_3 < \alpha_3\).
Pour définir le coloriage des points, on considère les coordonnées barycentriques de \(f(X) = X’ \alpha’_1, \alpha’_2, \alpha’_3)\). On colore \(X\) en rouge si \(\alpha’_1 < \alpha_1\). Si ce n’est pas le cas, (ce qui revient à dire que \(\alpha’_1 ≥ \alpha_1)\), alors on colore \(X\) en bleu si \(\alpha’_2 < \alpha_2.\) Si \(X\) n’est ni rouge ni bleu (ce qui revient à dire que \(\alpha’_1 ≥ \alpha_1\) et \(\alpha’_2 ≥ \alpha_2),\) alors on colore \(X\) en jaune si \(\alpha’_3 < \alpha_3.\) Autrement, on doit avoir \(\alpha’_i = \alpha_i \) pour \(i=1,2,3,\) ce qui implique que \(X=f(X)\) est un point fixe.
Emanuel Sperner 1905-1980
Emanuel Sperner était un mathématicien allemand, né à Waltdorf près de Neisse. Cette ville fait maintenant partie de la Pologne et porte le nom polonais de Nysa. Sperner a étudié au Carolinum Gymnasium de Neisse et est entré à l’Université de Fribourg en 1925. À l’époque, les étudiants avaient l’habitude de fréquenter plusieurs universités et, après deux semestres, Sperner s’est inscrit à l’Université de Hambourg.
Il y a reçu son doctorat en 1928. C’est dans sa thèse qu’il a présenté l’important résultat appelé maintenant Lemme de Sperner.
Un triangle multicolore
Chacun des points du triangle a ainsi été coloré en jaune, bleu ou rouge, tout en respectant les conditions du Lemme de Sperner. Alors, pour toute triangulation du triangle en petits triangles, il existe un petit triangle qui est tricoloré: si le triangle est très petit, ses sommets jaune, bleu et rouge sont très près les uns des autres.
Une infinité de triangles tricolorés, de plus en plus petits
On considère des triangulations avec des triangles de plus en plus petits (disons que l’on diminue la longueur des côtés des petits triangles par 2 à chaque étape), et pour chaque triangulation, on considère un des petits triangles tricolorés dont l’existence est garantie par le Lemme de Sperner. On a donc une infinité de triangles tricolorés, de plus en plus petits.
Une infinité de sommets rouges
Considérons la suite des sommets rouges de ces petits triangles tricolorés, et divisons le triangle initial en 10 régions: il y a forcément au moins une de ces régions qui contient une infinité de points rouges. Divisons cette région en 10 régions plus petites: il y en a encore forcément une qui contient une infinité de points rouges. Et ainsi de suite. En subdivisant toujours ainsi, on peut voir qu’il y a une infinité de points rouges dans une région aussi petite que l’on veut. À la limite, les régions ainsi obtenues tendent vers un point: ce point est donc la limite de points rouges.
Un point que l’on ne peut colorer
Le point est la limite de points rouges. Mais comme ces points rouges sont les sommets de triangles tricolorés de plus en plus petits, les autres sommets de ces triangles se rapprochent aussi de P qui est donc la limite de points rouges, de points bleus et de points jaunes.
Peut-on le colorer? En fait, selon la définition de coloriage donnée plus tôt, le point ne pourra être coloré (voir encadré), et il est donc fixe, ce qui démontre le Théorème du point fixe de Brouwer.
Un point fixe dans \(\mathbb{R}^n\)
Le résultat de point fixe que nous avons montré a des formulations plus générales. Il demeure vrai si on a une fonction \(f: E \to E\) où \(E\) est une région bornée et suffisamment régulière dans l’espace, sans trou et incluant sa frontière, telle une sphère ou un polyèdre, et aussi pour des régions aux propriétés analogues dans \(\mathbb{R}^n\) pour \(n ≥ 4.\)
Le Lemme de Sperner est aussi vrai pour l’analogue des triangles dans \(\mathbb{R}^n\), soit les tétraèdres dans \(\mathbb{R}^3\) et les simplexes en général dans \(\mathbb{R}^n\).
L’utilité du Lemme de Sperner montre bien que le coloriage a sa place en mathématiques, et illustre que les mathématiques discrètes peuvent être utiles dans d’autres domaines.
Le point fixe: un point limite
Si on a une suite de points rouges Rk qui tend vers un point P du triangle, que peut-on dire de P? Comme la fonction est continue et que f(Rk) s’éloigne de A, alors f(P) ne peut pas se rapprocher de A.
Si une suite de points bleus Bk tend vers ce même point P, alors f(P) ne peut pas se rapprocher de B. Et si en plus une suite de points jaunes Jk tend vers P, alors f(P) ne peut pas s’approcher de C.
Donc, si trois suites Jk, Bk et Rk tendent vers un même point P, alors P est fixe, car f(P) n’est plus près ni de A, ni de B, ni de C.
On peut formuler cet argument de manière plus rigoureuse, en utilisant les coordonnées barycentriques.
Un résultat évident en 1D
Si au lieu de considérer une carte comme représentant une surface en 2D, on considère une ficelle comme représentant un segment, alors il est simple de montrer que l’on a un point fixe. Sur la figure, en allant d’une extrémité à l’autre de la ficelle et de la même ficelle repliée, on passe par toutes les couleurs. Deux points de même couleur seront forcément superposés car à l’extrême gauche, le point de la ficelle du dessous est à gauche du même point sur la ficelle repliée, et à l’extrême droite, le point de la ficelle du dessous est à droite du même point sur la ficelle repliée.
Une représentation graphique le montre aussi. En effet, le graphe d’une fonction continue \(f: [0, 1] \to [0, 1]\) doit couper la droite \(y = x\) en au moins un point dont les coordonnées sont alors égales: soit ce point de coordonnées \((a, a).\) Alors \(f(a) = a\) et \(a\) est donc un point fixe de \(f.\)
PDF« >PDF
