Une version de la conjecture de Kendall

Piste rouge Le 21 mars 2019  - Ecrit par  Nicolas Chenavier Voir les commentaires (3)

Nous parlerons d’une conjecture faisant intervenir de la géométrie et du hasard. La branche des mathématiques dans laquelle se situe cette conjecture est la géométrie aléatoire. On pourra, à ce titre, consulter Qu’est-ce que la géométrie aléatoire ? pour une présentation de ce domaine.

Construction de la mosaïque de Voronoï

Plaçons-nous dans un carré (disons de côté 1), et prenons deux points, $A$ et $B$, dans ce dernier, comme dans la figure ci-dessous.
Nous y avons également tracé, en rouge, la portion de la médiatrice qui se situe dans le carré. C’est en fait le lieu où l’on est aussi proche de $A$ que de $B$. La figure suivante est un peu plus précise : elle fait apparaître en vert le lieu où l’on est plus proche de $A$ que de $B$ ; et en bleu le cas opposé. Un point est plus proche de A ou de B selon qu’il se situe d’un côté ou de l’autre de la médiatrice.

Ce que nous avons fait concerne deux points. Mais, que se passe-t-il si, au lieu d’en prendre deux, on en prend trois ? Voici, par exemple, ce que l’on obtient :
Dans cette figure, nous avons pris trois points : $A$, $B$ et $C$. La partie bleue est l’endroit où l’on est plus proche de $A$ que des deux autres points ; la beige est celle où l’on est plus proche de $B$ ; et la verte celle où l’on est plus proche de $C$. Remarquons que le segment qu’il y a entre $A$ et $B$, par exemple, est une portion de la médiatrice entre ces deux points.

Allons plus loin : que se passe-t-il si on prend encore plus de points ? Disons 28. On obtient, par exemple, ceci :
En vert, se situe le lieu où l’on est plus proche du point $A$ que de tous les autres points noirs. On remarque que c’est un polygone. Ce dernier a un nom : on l’appelle la cellule de Voronoï de germe $A$. Remarquons qu’en fait on a la même chose pour tous les points noirs : pour chacun de ces points, la portion où l’on est plus proche de ce point que des autres est aussi un polygone. En fait, ce n’est guère étonnant car toutes ces portions ont été construites à partir des médiatrices des points noirs pris deux à deux. On obtient donc une famille de polygones qui forment un découpage du carré. On appelle ce découpage la mosaïque, ou le diagramme, de Voronoï. La mosaïque de Voronoï a un grand nombre d’applications dans divers domaines, notamment en télécommunications pour des modélisations de réseaux, en biologie pour modéliser des protéines, ou encore en astrophysique pour l’étude de structures spatiales des populations d’étoiles. On l’observe également dans la nature : par exemple, les taches de girafe ressemblent à des cellules de Voronoï.

À notre connaissance, cela vient du fait que les cellules productrices de mélanine, qui confèrent le caractère brun aux taches, grossissent jusqu’à rencontrer des cellules issues d’autres taches. On trouve également des cellules de Voronoï sur d’autres animaux, notamment la carapace de certaines tortues :

JPEG - 150 ko

Pour de plus amples informations sur cette mosaïque, nous vous invitons à lire « Jouez avec les diagrammes de Voronoï ».

Des mosaïques construites au hasard

Dans ce qui suit, nous allons jouer aux probabilités avec Voronoï. Plus précisément, les points qui permettent de construire nos cellules (c’étaient les points noirs dans la figure précédente) seront pris au hasard. Par hasard, il faut comprendre que chacun de ces points a autant de chance (et ce, indépendamment des autres points) de se trouver dans n’importe quel petit carré d’un quadrillage de la figure aussi fin qu’on le fasse. Nous avons demandé à Matlab (c’est un logiciel de mathématiques) de lancer au hasard 1000 points puis de construire la mosaïque associée à ces points. Voici ce que l’on obtient.
On dit, dans un vocabulaire probabiliste, que l’on a une réalisation de la mosaïque. La figure suivante donne une autre réalisation quand on lance, encore au hasard, 1000 points, indépendamment de ce qu’on a fait précédemment.
Une troisième réalisation, toujours avec 1000 points qui ont été pris au hasard, donne ceci.
On constate que les trois mosaïques ci-dessus sont différentes : cela est dû au fait que les points qui ont permis de construire nos cellules ont été lancés au hasard.

La plus grosse cellule

Nous ne sommes intéressés que par les cellules qui ne touchent aucun des quatre côtés du carré. On dira de ces cellules qu’elles sont « à l’intérieur ». A contrario, les cellules qui touchent l’un des quatre côtés du carré (celles qui se situent donc à la frontière) ne nous intéressent pas car elles sont atypiques, peu représentatives, et de toute façon elles sont peu nombreuses par rapport aux autres. La question principale de cet article est : que peut-on dire de la cellule (à l’intérieur du carré) qui a la plus grande aire ? Si l’on reprend les figures de la section précédente, la cellule coloriée en rouge est celle qui a la plus grande aire. Que constate-t-on ? A chaque fois, la cellule rouge est assez arrondie. Elle n’est d’ailleurs pas la seule à l’être, mais nous nous concentrons ici sur l’étude de cette plus grande cellule.

Regardons ce qu’il se passe lorsque le nombre de points lancés est plus grand. Pour cela, nous avons demandé à Matlab de prendre un million de points au hasard, de tracer la mosaïque, et de nous dire quelle est la plus grande cellule. Puis, nous avons refait la même chose une deuxième fois, et une troisième fois, en prenant à nouveau un million de points au hasard. Nous obtenons donc trois mosaïques. Nous ne les avons pas représentées car les cellules sont toutes petites. La figure ci-dessous représente la plus grosse cellule (celle qui a la plus grande aire) pour chacune d’entre elles. Nous avons fait un zoom, en précisant l’échelle, pour bien voir à quoi elle ressemble (le germe de chaque cellule est représenté par un point noir). Remarquons au passage que l’aire de chaque cellule est (un peu) plus grande que $10^{-6}$, c’est-à-dire un millionième. Ce n’est guère étonnant. En effet, on sait qu’il y a, à chaque fois, un million de cellules dans un carré dont l’aire est égale à 1. Donc l’aire d’une cellule prise au hasard est d’environ un millionième, et la cellule qui a la plus grande aire a nécessairement une aire supérieure à cette valeur. On constate également que les trois cellules sont assez arrondies. En fait, on est dans le cœur d’une conjecture due à Kendall que nous énonçons comme suit.

Conjecture 1 (une version de la conjecture de Kendall) : Lançons $n$ points au hasard dans un carré. Alors, quand $n$ est très grand, il y a de très fortes chances que la plus grosse cellule ressemble à un disque.

Cette conjecture signifie que si nous lançons beaucoup de points au hasard, la plupart du temps, la plus grosse cellule ressemblera à un disque, et sera donc arrondie. Elle ne veut pas dire pour autant qu’on est toujours sûr qu’elle sera arrondie : un scénario où la cellule n’est pas du tout circulaire peut se produire, par exemple si c’est un triangle allongé, mais très rarement ; et d’autant plus rarement que le nombre de points qu’on a lancés est grand.

Nous avons intitulé notre article, ainsi que l’énoncé ci-dessus, « une version de la conjecture de Kendall » car il ne s’agit pas de la version originale, telle qu’elle a été réellement énoncée par D. G. Kendall dans les années 40. Cette conjecture a été en fait émise dans un autre contexte (voir l’avant-propos de la première édition de [SKM95]). Nous avons préféré donner une version modifiée de sa conjecture car nous pensons qu’elle est plus compréhensible. Pour une biographie de D. G. Kendall, nous renvoyons le lecteur à wikipedia.

La conjecture originale de Kendall a été résolue par I. N. Kovalenko en 1997 (voir Ko99 pour une preuve). La version que nous avons énoncée a été résolue, dans un contexte légèrement différent, par trois mathématiciens allemands : D. Hug, M. Reitzner et R. Schneider en 2004 (Théorème 1 de HRZ). Voici une adaptation de leur résultat.

Théorème 2 : Lançons $n$ points au hasard dans un carré, où $n$ est un grand nombre, et construisons la mosaïque de Voronoï. Soit $C$ la cellule qui possède la plus grande aire, et soit $A$ le germe de cette cellule. Désignons par $r(C)$ le rayon du plus grand disque qui se trouve à l’intérieur de la cellule et dont le centre est le point $A$ ; et par $R(C)$ le rayon du plus petit disque qui contient la cellule et dont le centre se trouve aussi en $A$. Alors, il y a de très fortes chances que $r(C)/R(C)$ soit proche de 1.

Afin de bien comprendre le théorème, regardons la figure suivante.
Elle fait apparaître une cellule de Voronoï (en vert) et son germe $A$. Dans cette figure, le cercle bleu délimite le plus grand disque, centré en $A$, qui est contenu dans la cellule tandis que le cercle rouge délimite le plus petit disque, centré en $A$, qui contient la cellule. Bien entendu, le rayon $r(C)$ du cercle bleu est toujours plus petit que le rayon $R(C)$ du cercle rouge. Ce que dit le théorème, c’est que lorsqu’on lance un grand nombre de points et qu’on prend la plus grande cellule, le plus souvent, ces deux rayons sont très proches (dans le sens où le quotient $r(C)/R(C)$ est proche de 1). Cela répond bien à la conjecture 1 car dire que les cercles bleu et rouge sont presque identiques signifie que la cellule est presque un disque.

Si l’on reprenait la figure du début de cette section et qu’on devait tracer les cercles bleus et rouges, pour chacune des trois cellules, on se rendrait compte qu’ils ne sont pas vraiment identiques. La raison est que, pour des questions techniques, nous n’avons lancé qu’un million de points pour construire chacune des trois mosaïques. Il faut imaginer que si on avait pris beaucoup plus de points (mais vraiment beaucoup plus !) alors le plus souvent le cercle bleu sera presque le même que le cercle rouge. Plus précisément, la chance que le rapport des rayons $r(C)/R(C)$ soit proche de 1 est d’autant plus élevée que le nombre $n$ de points est grand. En fait, on est même capable d’avoir une idée de la chance que ce rapport soit plus grand qu’une tolérance qu’on se fixe. Par exemple, si le nombre de points $n$ possède environ 500 000 chiffres, alors on sait qu’il y a au moins 95% de chance que $r(C)/R(C)$ soit plus grand que 0.99. Il faut un peu plus d’une centaine de pages pour écrire un tel nombre $n$, et sa taille anéantit toute tentative d’imagination (par exemple, le nombre de particules dans l’Univers visible possède moins de 100 chiffres). Les ordinateurs ne seront jamais capables de construire des mosaïques avec autant de points. En pratique, on peut dire qu’on n’arrivera jamais à observer des mosaïques (aléatoires) dont la plus grande cellule est très proche d’un cercle (c’est le cas, par exemple, si $r(C)/R(C)$ est plus grand que 0.99) ; et pourtant, en théorie, on sait que cela est vrai lorsque le nombre de points $n$ est très grand. L’une des beautés des mathématiques est de savoir qu’un résultat est vrai alors qu’on n’est pas capable de l’observer.

La conjecture de Kendall a débouché sur un grand nombre de questions. En voici quelques unes. Est-ce que ce résultat est encore vrai si on considère non pas la cellule qui a la plus grande aire, mais celle qui a le plus grand périmètre ou celle qui a le plus grand nombre de sommets ? C’est une question différente car il n’y a pas de raison que la cellule qui a la plus grande aire soit la même que celle qui a le plus grand périmètre, ou le plus grand nombre de sommets. Que se passe-t-il si à la place de considérer une mosaïque dans le carré, on considère une mosaïque dans un cube ? Que se passe-t-il si l’on considère d’autres types de mosaïques ? Plusieurs de ces questions ont déjà été résolues entre 2000 et 2010. Il s’avère que, suivant ce que l’on entend par « grosse » cellule (cela peut être celle qui a la plus grande aire, celle qui a le plus grand périmètre, ou encore celle qui a le plus grand nombre de sommets), la réponse est généralement la même : une grosse cellule est presque toujours arrondie quand on lance beaucoup de points.

La plus petite cellule

Il reste encore de nombreuses questions ouvertes et qui constituent une part active de la recherche en géométrie aléatoire. On sait donc à quoi ressemblent les grosses cellules ; en revanche peu de choses ont été faites sur les petites cellules. À quoi ressemblent-elles ? Pour voir cela de plus près, nous avons construit une mosaïque de Voronoï avec un million de points lancés au hasard et observé la cellule qui a la plus petite aire ; puis nous avons fait cela, une deuxième, une troisième fois. À nouveau, nous n’avons pas représenté les mosaïques. La figure suivante montre à quoi ressemble la cellule qui a la plus petite aire pour chacune de ces trois mosaïques. Il semble, au vu de ces figures, que la cellule la plus petite est souvent un triangle. Mais, ce n’est pas très convaincant car nous n’avons que trois mosaïques

Pour avoir une idée plus précise de ce à quoi ressemble une petite cellule, nous avons fait la même chose que ci-dessus, cette fois-ci non pas avec trois mosaïques mais avec cent mosaïques. Plus précisément, nous avons lancé un million de points au hasard pour construire une mosaïque ; et nous avons réitéré l’expérience pour avoir un total de cent mosaïques. Nous avons compté le nombre d’entre elles pour lesquelles la plus petite cellule est un triangle (trois sommets), un quadrilatère (quatre sommets), un pentagone (cinq sommets). Les résultats sont donnés dans le tableau ci-dessous.

Nature de la plus petite cellule triangle quadrilatère pentagone
Nombre de mosaïques 85 15 0

Dans ce tableau, on peut constater que sur les 100 mosaïques, il y en a 85 dont la plus petite cellule est un triangle et 15 dont la plus petite est un quadrilatère. Il n’y a eu aucun cas où la plus petite cellule avait au moins 5 sommets. Cela ne signifie pas qu’il est impossible que la plus petite cellule ait au moins 5 sommets : peut-être que nous n’avons pas eu de chance avec nos mosaïques. Sans doute que si nous avions fait énormément de mosaïques, nous serions tombés sur un cas où la plus petite cellule est un pentagone ; mais cela est sans doute extrêmement rare par rapport au nombre de fois où l’on va avoir un triangle ou un quadrilatère.

Il n’est pas clair que la plus petite cellule est, la quasi-totalité du temps, un triangle : 15 d’entre elles, en effet, ne sont pas des triangles, ce qui est quand même non négligeable. Peut-être que si nous lancions plus de points, nous en saurions davantage ; et peut-être que nous constaterions, dans ce cas, que la plupart du temps la plus petite cellule est un triangle. Mais construire une mosaïque avec beaucoup de points (par exemple 1000 milliards) demande beaucoup de temps à l’ordinateur, et d’ailleurs les ordinateurs ne sont pas suffisamment performants pour faire cela. En consultant le tableau, nous avons cependant envie d’émettre la conjecture suivante.

Conjecture 3 : Lançons $n$ points au hasard dans un carré. Alors, quand $n$ est très grand, il y a de très fortes chances que la plus petite cellule ait trois ou quatre sommets.

À la différence de la première conjecture, celle qui apparaît ci-dessus est une question ouverte. Aujourd’hui, on ne sait pas si ce résultat est vrai.

Post-scriptum :

Je remercie chaleureusement Shalom Eliahou et Bruno Martin pour m’avoir encouragé à écrire un article dans Images des mathématiques. Merci également à Christophe Boilley, François Guéritaud, Daniel Massart, Baptiste Mélès et Thomas Sauvaget pour leur relecture attentive. Enfin, merci à Christophe Bourel pour les simulations sur Matlab.

Article édité par Shalom Eliahou

Partager cet article

Pour citer cet article :

Nicolas Chenavier — «Une version de la conjecture de Kendall» — Images des Mathématiques, CNRS, 2019

Crédits image :

Image à la une - Flickr.
img_19342 - https://www.flickr.com/photos/snake3yes/229891787/in/photostream/
img_19849 - Yotcmdr [Public domain]. https://commons.wikimedia.org/wiki/File:Giant_Tortoise.JPG

Commentaire sur l'article

  • Girafes

    le 21 mars à 19:36, par Rémi Peyre

    Cher Nicolas,

    Félicitations pour ce bel article ! 8-) J’ai une question concernant la photo des girafes : sur le plage de la girafe la plus à droite, on voit clairement un petit point plus clair dans chaque tache sombre, qui semble correspondre au germe de la cellule de Voronoï correspondante. Est-ce bien le cas ? À quoi correspondent ces points clairs du point de vue biologique ; et comment se fait-il qu’on ne les observe pas sur les deux autres girafes de la photo ? J’en suis en effet venu à me demander s’il ne s’agissait pas d’une retouche ajoutée artificiellement à la photo par un mathématicien désireux de mettre en évidence la structure voronoïde du pelage de la girafe…

    Amicalement,

    Répondre à ce message
    • Girafes

      le 23 mars à 12:11, par Nicolas Chenavier

      Merci pour tes encouragements et tes questions. Je ne sais pas d’où viennent ces points blancs, et serai ravi de le savoir. La girafe en question est une girafe réticulée. Visiblement, il s’agit de quelque chose d’assez courant sur ce type de girafe (en voici une autre https://fr.wikipedia.org/wiki/Girafe_r%C3%A9ticul%C3%A9e#/media/File:Giraffa_camelopardalis_reticulata_01.JPG). Je ne pense donc pas qu’il s’agit d’une retouche faite par un mathématicien ! Après quoi, j’ai mis cette photo car il semble en effet qu’il s’agit des germes des cellules ; ce qui permet entre autres d’illustrer Voronoï.

      Répondre à ce message
      • Girafes

        le 27 mars à 23:06, par Rémi Peyre

        Merci pour le lien vers la deuxième photo, qui me convainc en effet que ces points clairs ne proviennent pas d’une retouche, mais ont bel et bien une réalité biologique ! :-)

        Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?