Erdős et la méthode probabiliste : prouver l'existence par le hasard
Paul Erdős n'avait pas de domicile, pas d'emploi au sens ordinaire et presque aucune possession. Il a passé sa vie à voyager d'une université à l'autre avec une valise, arrivant chez un collègue avec la formule « mon cerveau est ouvert », et laissant derrière lui un flot de théorèmes et de problèmes non résolus sur lesquels les mathématiciens travaillent encore aujourd'hui. Parmi tout ce qu'il a créé, une idée se distingue pour avoir changé la façon même de faire des preuves. Elle s'appelle la méthode probabiliste, et au cœur de celle-ci se trouve un geste qui ressemble presque à de la triche : prouver que quelque chose existe en refusant de le construire.
La question : quand l'ordre est-il inévitable ?
Commençons par une énigme à l'air anodin. Lors d'une fête de six personnes, deux personnes quelconques sont soit amies, soit inconnues. Il se trouve que parmi six personnes quelconques, on peut toujours trouver trois personnes toutes mutuellement amies, ou trois personnes toutes mutuellement inconnues. L'ordre s'impose de lui-même. La branche des mathématiques qui étudie quand cela doit se produire est la théorie de Ramsey, et elle associe un nombre à la question.
Le théorème de Ramsey garantit que ces nombres existent, mais il ne dit pas à quel point ils sont grands. La suite naturelle est : quelle taille un groupe peut-il atteindre tout en évitant tout amas monochrome de taille k ? Y répondre signifie prouver qu'un tel coloriage astucieux existe. Et c'est précisément là qu'en construire un à la main devient désespéré, car le nombre de coloriages possibles est astronomique.
Le geste d'Erdős : ne le construisez pas, comptez-le
L'intuition d'Erdős, en 1947, fut de cesser de chercher à concevoir un bon coloriage et de colorier plutôt complètement au hasard, puis de laisser l'arithmétique faire le travail. L'argument est assez court pour être suivi en entier.
Colorier chaque connexion en lançant une pièce
Prenez n personnes et considérez le réseau complet où chaque paire est reliée par une arête. Coloriez chaque arête indépendamment au hasard, rouge ou bleu, chacune avec une probabilité d'un demi. Aucune astuce, aucune conception. Juste une pièce équilibrée pour chaque arête.
Mesurer la probabilité qu'un groupe soit monochrome
Fixez un ensemble particulier de k personnes. Parmi elles, il y a C(k,2) arêtes, soit k(k-1)/2 connexions. Que toutes ces arêtes partagent une seule couleur est peu probable : la probabilité est 2 × (1/2)^C(k,2), puisqu'il y a deux couleurs et que chacun des C(k,2) lancers de pièce doit concorder. Appelons ce petit nombre p.
Additionner le nombre attendu de mauvais groupes
Il y a C(n,k) groupes différents de k personnes dont il faut se soucier. Par la linéarité de l'espérance, le nombre attendu de groupes entièrement monochromes est simplement le nombre de groupes multiplié par la probabilité pour chacun : C(n,k) × 2 × (1/2)^C(k,2). Cette seule expression capture, en moyenne, combien d'amas d'une seule couleur un coloriage aléatoire contiendra.
Si la moyenne est sous 1, un coloriage sans défaut doit exister
Choisissez maintenant n environ égal à 2^(k/2). Avec ce choix, le nombre attendu ci-dessus s'avère inférieur à 1. Or, un décompte de groupes monochromes réels est un nombre entier, et si la moyenne sur tous les coloriages est inférieure à 1, alors au moins un coloriage doit valoir 0. Ce coloriage n'a aucun groupe monochrome de taille k. Par conséquent, R(k,k) est plus grand que n, qui vaut environ 2^(k/2).
Relisez ce dernier pas, car c'est là toute la magie. Nous n'avons jamais produit de bon coloriage. Nous n'en avons jamais décrit un. Nous avons montré que le coloriage moyen est si proche de la perfection qu'un coloriage parfait est forcé d'exister quelque part dans le tas. La preuve vous donne la certitude d'un objet précis tout en ne désignant aucun objet en particulier.
Pourquoi c'était révolutionnaire
Avant Erdős, prouver que quelque chose existait signifiait presque toujours le construire, ou du moins décrire une procédure qui le ferait. La méthode probabiliste a brisé cette attente. Elle a établi que le hasard lui-même pouvait servir de preuve : si une tentative aléatoire réussit avec une probabilité supérieure à zéro, alors la réussite est possible, un point c'est tout.
Cette saveur non constructive place l'argument dans la même famille que certains des résultats les plus élégants des mathématiques. L'argument diagonal de Cantor prouve lui aussi l'existence de quelque chose, un nombre absent de n'importe quelle liste, par pure force logique plutôt que par construction explicite. Tous deux partagent cette puissance tranquille, presque troublante : la conclusion est inattaquable même si elle ne vous montre jamais la chose qu'elle promet. Le hasard repose ici sur les mêmes fondations que celles abordées dans comprendre la probabilité intuitivement, où l'idée d'une espérance, le moteur de l'étape trois, est construite à partir de zéro.
Les problèmes d'Erdős et leur moment IA
Erdős n'a pas seulement prouvé des théorèmes. Il a posé des problèmes, des centaines, attachant souvent de petites récompenses en argent allant de quelques dollars pour un exercice retors à des milliers pour une question qu'il croyait véritablement profonde. Beaucoup de ces problèmes sont encore ouverts, et ils ont été soigneusement catalogués et maintenus sur erdosproblems.com.
Le zen de la chose
La méthode probabiliste est belle pour la même raison qu'un bon tour de magie : vous observez chaque étape, vous ne parvenez pas à trouver l'endroit où vous avez été dupé, et pourtant le résultat semble encore impossible. Il n'y a aucun tour de passe-passe. L'espérance est réellement inférieure à un, et un nombre entier inférieur à sa propre moyenne doit réellement chuter à zéro quelque part. La certitude est totale, la construction est absente, et ces deux choses sont vraies en même temps.
C'est la leçon durable qu'Erdős a laissée. L'existence et la construction ne sont pas la même chose. Parfois, la manière la plus nette de savoir qu'un objet parfait existe quelque part est de prouver que l'objet moyen est presque parfait, et de laisser l'écart faire le reste. Pour un autre résultat où une seule ligne relie des idées qui semblent sans rapport, l'identité d'Euler offre le genre de beauté opposé : là où Erdős fait surgir l'existence du dénombrement, Euler épingle un nombre exact et inévitable.
Questions fréquentes
- Qu'est-ce que la méthode probabiliste ?
- C'est une façon de prouver qu'un objet possédant une certaine propriété existe, sans construire l'objet directement. On bâtit une version aléatoire de la chose, on montre que la probabilité qu'elle ait la propriété voulue est strictement supérieure à zéro, et on en conclut qu'au moins un tel objet doit exister. Paul Erdős a été le pionnier de cette technique, qui est aujourd'hui un outil central en combinatoire et en informatique.
- Qu'a démontré Erdős avec elle ?
- Son résultat marquant de 1947 a donné une borne inférieure sur les nombres de Ramsey : il a montré que le nombre de Ramsey diagonal R(k,k) est plus grand que 2^(k/2). En clair, il existe des façons de colorier les connexions d'un grand réseau avec deux couleurs de sorte qu'aucun grand groupe ne soit entièrement relié par une seule couleur. Il a prouvé que ces coloriages existent sans jamais en exhiber un, simplement par dénombrement.
- Comment prouver que quelque chose existe sans le construire ?
- En utilisant des moyennes. Si l'on choisit un objet au hasard et que l'on calcule le nombre attendu de défauts qu'il possède, et que ce nombre attendu ressort inférieur à 1, alors au moins un objet de l'ensemble doit avoir zéro défaut. Un tirage aléatoire dont le nombre moyen de défauts est inférieur à un garantit qu'un exemple parfait se trouve quelque part dans la collection, même si l'argument ne désigne jamais lequel.
- Qu'est-ce qu'un nombre de Ramsey ?
- Le nombre de Ramsey R(k,k) est la plus petite taille de groupe qui force l'ordre à apparaître, quelle que soit la disposition. Concrètement, R(k,k) est le plus petit nombre de personnes tel que, peu importe comment vous séparez chaque paire en amis ou inconnus, vous êtes assuré d'avoir un groupe de k personnes toutes mutuellement amies ou toutes mutuellement inconnues. Le théorème de Ramsey affirme que ces nombres existent ; la méthode d'Erdős montre qu'ils croissent très vite.
- Pourquoi la méthode probabiliste est-elle importante aujourd'hui ?
- Elle a transformé le hasard en technique de preuve, et cette idée parcourt désormais la combinatoire, la conception d'algorithmes, la théorie des codes et l'informatique théorique. De nombreux résultats sur les réseaux et les algorithmes sont encore prouvés en montrant qu'une construction aléatoire fonctionne avec une probabilité positive. La méthode explique aussi pourquoi une grande partie des problèmes posés par Erdős lui-même restent des cibles de recherche actives.
Tu as aimé suivre ce raisonnement ?
Math Zen transforme ce type d'intuition en pratique quotidienne, avec des exercices adaptatifs sur 24 thèmes de maths.
