Pour faciliter la tâche de Gabrielle, je coupe les aubergines épluchées en deux, dans le sens de la longueur, et je pose des moitiés d’aubergines sur la planche à découper. Gabrielle se penche sur la planche, elle s’applique. Ses tranches sont bien demi-rondes, de taille à peu près constante. Tom les dispose dans l’assiette. Curieusement, il prend soin de reconstituer les rondelles. Puis sa cousine asperge le tout de sel. Il y en a pas mal à côté, notamment entre les tranches. Mon esprit vagabonde : comment faire pour réduire l’espace entre les tranches ? La méthode de Tom est-elle la meilleure ? Aurait-on plutôt intérêt à exploiter plus librement les demi-rondelles ?

Les enfants ont terminé, les voilà repartis. Cela les aura occupés cinq minutes tout au plus. Quant à moi, le problème continue de me tourner dans la tête. Au moment de jeter les aubergines dans la poêle, la même question resurgit : comment disposer au mieux les demi-rondelles sans qu’elles se chevauchent ?

Empiler des rondelles

Dans le cas de rondelles complètes, le problème est familier. J’ai remarqué que quand on dispose des verres identiques sur une table, on a tendance à les mettre en quinconces, i.e. en lignes droites, chaque ligne étant décalée par rapport à la précédente. Alors chaque verre en touche 6 autres. Est-ce la meilleure façon de procéder ?

Qu’est-ce qu’on entend par « meilleure façon » ? Il s’agit de mettre le plus possible de verres sur la table. Ainsi formulé, le problème dépend du choix de table. Sur une toute petite table, les effets de bords dominent. Par exemple, sur une table carrée dont le côté est le double du diamètre des verres, la disposition en quinconces ne permet de poser que 3 verres, alors qu’on peut en poser 4 en carré.

Pour s’affranchir des effets de bord, on imagine des tables de plus en plus grandes. Cela conduit au problème modèle suivant.

La densité d’un empilement

Dans le plan, un empilement $E$ est une collection (éventuellement infinie) de disques de même rayon unité dont les intérieurs sont disjoints. Le terme, bien adapté pour des boules dans l’espace (oranges, pommes, boulets de canon), peut sembler bizarre pour des disques dans le plan, mais l’usage l’a consacré, paresse de mathématiciens.
Étant donnée une région $R$ du plan, la densité de $E$ dans $R$ est le rapport $\frac{\mathrm{aire}(E \cap R)}{\mathrm{aire}(R)}$. La densité de $E$ est une limite des densités de $E$ dans de grands disques

La densité de l’empilement hexagonal dans un cercle de rayon variant de 1 à 100

Par exemple, comparons deux empilements, l’empilement hexagonal $E_{hex}$ et l’empilement carré $E_{car}$.

La nomenclature dérive du pavage associé, par hexagones réguliers, dans le premier cas, par carrés dans le second.

Si $H$ désigne un pavé hexagonal, circonscrit à un cercle de rayon 1, l’aire de $H$ vaut $\sqrt{12}$. En effet, $H$ est constitué de 6 triangles équilatéraux de hauteur 1, dont la base vaut $\frac{2}{\sqrt{3}}$. On en déduit que la densité de $E_{hex}$ dans $H$ vaut $\frac{\pi}{\sqrt{12}}$. Si $C$ désigne un pavé carré, circonscrit à un cercle de rayon 1, l’aire de $C$ vaut 4, donc la densité de $E_{car}$ dans $C$ vaut $\frac{\pi}{4}$. Dans les deux cas, on peut en déduire, en approchant un grand disque par une réunion de pavés, que les densités respectives des deux empilements sont $\frac{\pi}{\sqrt{12}}$ et $\frac{\pi}{4}$, c’est l’empilement hexagonal qui gagne.

Approximation d’un grand disque par des pavés

Sachant que $\frac{\pi}{\sqrt{12}}=$ 0,90..., moins de 10% de la surface n’est pas occupée par les disques.

L’intuition du rangeur de verres est confirmée par le théorème mathématique suivant : tout empilement de disques de même rayon dans le plan a une densité inférieure ou égale à $\frac{\pi}{\sqrt{12}}$.

La référence la plus ancienne connue pour une démonstration de ce théorème est un article du mathématicien norvégien Axel Thue, paru en allemand dans une revue régionale norvégienne, Skrifter udg. af Videnskabs-Selskabet i Christiania, en 1910, [8]. L’argument exposé en encadré apparaît dans un manuscrit non publié de deux mathématiciens chinois de Taiwan, Hai-Chau Chang et Lih-Chung Wang, déposé sur l’archive ArXiv en 2010, [1].

Encadré : Pavages associés à un empilement de disques

En général, à un empilement de disques est associé un pavage naturel, dit de Voronoi. La cellule d’un disque $D$ de $E$ est le lieu des points du plan qui sont plus proches du centre de $D$ que de tous les autres centres des disques de $E$. C’est un polygone convexe.

Nous allons utiliser aussi une seconde construction, la triangulation de Delaunay associée à l’empilement. Ses sommets sont les centres des disques, elle compte une arête par paire de cellules de Voronoi qui se touchent. Les triangles de Delaunay constituent un pavage du plan dès que l’enveloppe convexe de l’empilement est le plan entier. Ils ont la propriété suivante : l’intérieur du cercle circonscrit à un triangle de Delaunay ne contient aucun autre centre de disque de l’empilement.

Voronoi rencontre Delaunay

7 centres de disques, une cellule de Voronoi et 6 triangles de Delaunay

Pour majorer la densité d’un empilement $E$, on peut le supposer saturé, i.e. qu’il est impossible d’ajouter un disque et d’obtenir encore un empilement. Dans ce cas, H.-C. Chang et L.-C. Wang observent que tous les angles des triangles de Delaunay ont une mesure au plus égale à $\frac{2\pi}{3}$. Pour cela, ils s’appuient sur la loi des sinus, qui relie angles, côtés et rayon du cercle circonscrit. Ils en déduisent que l’aire de chaque triangle de Delaunay est au moins égale à $\sqrt{3}$. La densité de l’empilement $E$ dans un de ses triangles de Delaunay est donc majorée par $\frac{\pi}{\sqrt{12}}$. Comme les triangles de Delaunay ont des diamètres uniformément bornés et constituent un pavage du plan, cela démontre le théorème.

Détails de l’argument de H.-C. Chang et L.-C. Wang.

Un triangle de Delaunay

Comment minorer l’aire d’un triangle de Delaunay

Soit $ABC$ un triangle de Delaunay, soit $R$ le rayon de son cercle circonscrit $\Gamma$ et $O$ le centre de ce cercle. Supposons que $R > 2$. Alors le disque $D$ de centre $O$ et de rayon $1$ est disjoint de tous les disques de l’empilement, puisque leurs centres sont tous à l’extérieur de $\Gamma$. On peut donc l’ajouter à l’empilement, ce qui contredit le choix d’un empilement saturé. On conclut que $R \le 2$. Comme $B$ et $C$ sont des centres de disques de l’empilement, $BC \ge 2$. Notons $\alpha=\widehat{CBA}$ l’angle en $A$. La loi des sinus donne $2R = \frac{BC}{\sin(\alpha)}$, d’où $\sin(\alpha)=\frac{BC}{2R} \geq \frac{1}{2}$, $\alpha$ mesure au moins $\frac{\pi}{6}$. Par conséquent, le plus grand angle du triangle mesure au plus $\frac{2\pi}{3}$, et au moins $\frac{\pi}{3}$. Comme les côtés de cet angle ont des longueurs au moins égales à $2$, l’aire du triangle $ABC$ vaut au moins
\[ \frac{1}{2}\,AB\,BC\sin(\alpha)\ge\frac{1}{2}\,2^2\,\frac{\sqrt{3}}{2} = \sqrt{3}. \]
L’intersection de l’empilement avec le triangle consiste en trois secteurs circulaires de rayon $1$, dont la somme des angles vaut $\pi$, donc son aire vaut $\frac{\pi}{2}$. On conclut que la densité vaut au plus $\frac{\pi}{\sqrt{12}}$.

Merci à Camille Coustillet et Émilie Mboussa qui m’ont expliqué tout cela !

Empilements de boules en dimension 3

Comment empiler des boules de même rayon de la façon la plus dense possible, en dimension 3 ? Appelons couche hexagonale un empilement formé de boules centrées sur un plan $P$, dont l’intersection avec $P$ est un empilement hexagonal de $P$.

Une couche hexagonale

Sur une première couche hexagonale, on peut en poser une seconde. Elle ne remplit que la moitié des « creux » de la première couche, il y a donc deux façons de faire, celle illustrée dans la figure de gauche ci-dessus, et la manière symétrique par rapport à un axe horizontal.

Néanmoins, tous les empilements obtenus en posant les unes sur les autres des couches hexagonales ont la même densité, égale à $\frac{\pi}{\sqrt{18}}$. (Question : si on empile des couches carrées, quelle densité obtient-on ?).

Déjà en 1611, J. Kepler conjecturait que la densité d’un empilement de boules de même rayon dans l’espace euclidien à trois dimensions ne pouvait dépasser celle des empilements par couches hexagonales. Cette conjecture a été résolue en 1998 par Thomas C. Hales et Samuel Ferguson, [4]. Il s’agit d’une démonstration très longue (plus de 300 pages) et lourdement assistée par ordinateur. Certifier cette démonstration, i.e. démontrer qu’elle est correcte et complète par les techniques formelles de l’informatique, a été l’un des moteurs du développement des assistants de preuve. L’équipe montée par Tom Hales y est parvenue après 15 ans d’efforts, en 2014, [5].

D’autres dimensions

À quoi bon empiler des boules dans d’autres dimensions que 2 et 3 ? Je recommande l’article qui explique le lien entre empilements de boules et codes correcteurs d’erreurs. Les codes correcteurs sont omniprésents et indispensables au bon fonctionnement des canaux de télécommunications, du téléphone à internet. Les images envoyées par les sondes spatiales n’existeraient pas sans codes correcteurs, voir l’article. Le fait que les codes correcteurs soient reliés aux empilements de boules est une des bonnes surprises dont les mathématiques sont coutumières.

Des majorations de densité existent dans toutes les dimensions. Il se passe quelque chose de remarquable en dimension 8 et en dimension 24 : ce sont les seules dimensions (avec 2 et 3) pour lesquelles la borne optimale est connue. Elle est atteinte pour deux empilements présentant de très nombreuses symétries, le réseau dit $E_8$ en dimension 8, et le réseau de Leech en dimension 24. Ce résultat spectaculaire est dû à Maryna Viazovska, mathématicienne ukrainienne fixée en Suisse, avec Henry Cohn, Abhinav Kumar, Stephen D. Miller et Danylo Radchenko en 2016, [9] , [2]. Les mêmes auteurs ont établi en 2019 une propriété plus forte : ces mêmes réseaux minimisent toute une famille d’énergies d’interaction. Cette propriété plus forte n’est pas satisfaite par les empilements de couches hexagonales en dimension 3. La question de savoir si elle est satisfaite par l’empilement hexagonal du plan est toujours ouverte.

Et les demi-disques ?

L’empilement de Hind Taibi

Deux demi-disques dans un hexagone qui pave le plan

C’est là qu’intervient Hind Taibi. Elle a découvert d’abord l’hexagone irrégulier ci-contre, qui pave le plan et contient deux demi-disques. Cela donne un empilement périodique de densité $\frac{\pi}{\sqrt{3}-4(1-\sqrt{2})} =$ 0.927..., qui bat de 2% l’empilement hexagonal.

Le second empilement de Hind Taibi

Un demi-disque inscrit dans un pentagone qui pave le plan.

Ensuite, elle a cherché à inscrire un seul demi-disque dans un pentagone qui pave le plan. Les pavages par pentagones sont assez bien connus. L’article de C. Mann, J. McLoud-Mann et D. von Derau, [6] range les pavages périodiques par pentagones connus en 15 familles. Cette liste est conjecturalement complète, une tentative de démonstration par M. Rao, [7], est à l’étude. Dans la famille II, Hind a trouvé un pentagone symétrique qui enveloppe bien un demi-disque, et obtient ainsi un empilement de demi-disques de densité $\frac{\pi}{4(3+\sqrt{3})} =$ 0.929... qui bat son record précédent de 0,2 %.

Ce bel empilement semble un bon candidat pour le meilleur parmi tous les empilements de demi-disques. Toutefois, en déformant légèrement l’empilement hexagonal irrégulier de Hind, on obtient une densité de 0,933...

Qui dit mieux ? Voilà qui donne l’impression que l’on ne peut espérer trouver un jour le meilleur empilement de demi-disques dans le plan. Néanmoins, des bornes supérieures de densité seraient bienvenues.

Des demi-tranches dans une assiette

On a parlé de densité d’empilements du plan tout entier. Quand il s’agit de garnir une assiette ou une poêle avec une dizaine de demi-tranches d’aubergines, l’effet de bord domine, et on gagne parfois substantiellement en plaçant des demi-tranches le long du bord. La densité d’extraits de l’empilement de disques hexagonal entièrement contenus dans des cercles de petit rayon est basse. Ces valeurs confirment l’intuition du cuisinier : les rondelles remplissent mal les assiettes !

Des rondelles dans des assiettes

En rouge : densité de la partie de l’empilement hexagonal entièrement contenue dans un disque de rayon R, pour R de 0,5 à 10
En vert : densités de quelques empilements de demi-disques entièrement contenus dans les disques de même rayon

Il y a tout de même des valeurs particulières du rayon où la densité est assez élevée. Les figures ci-dessous indiquent deux maxima locaux à $\frac{7}{9} =$ 77,7..% et $\frac{19}{25} =$ 76% atteints lorsque le rayon de l’assiette est respectivement 3 et 5 fois celui des rondelles.

Si on s’autorise à couper les rondelles en deux, on peut dépasser ces scores. C’est encore Hind qui a proposé les configurations que voilà :

de densités respectives $\frac{27}{19+9\sqrt{3}}=$ 82,1..%, $\frac{10}{13}=$ 76,9..%, 84,8..% et $\frac{13}{13+2\sqrt{3}}=$ 78,9... Les trois premiers correspondent aux 4ème, 5ème et 6ème pics verts de la courbe ci-dessus.

Conclusion

En tout cas, le petit Tom avait raison : si on néglige les effets de bord, en cherchant des empilements sophistiqués, on n’arrive pas à augmenter la densité de beaucoup plus que 3%, donc en pratique, autant reconstituer les rondelles.

Pour finir, voici ma recette de gratin d’aubergines. Après avoir épluché, coupé, salé et fait revenir les tranches d’aubergines dans l’huile d’olive, tapisser le fond d’un plat allant au four avec de l’huile d’olive. Déposer des couches alternées d’aubergines, de sauce tomate et de comté râpé. Assaisonner, mettre au four assez chaud (200°) pendant 30 minutes.

Références

[1]↑ H.-C. Chang, L.-C. Wang, A simple proof of Thue’s theorem on circle packing, 2010

[2] ↑ H. Cohn, A. Kumar, S. D. Miller, D. Radchenko, M. Viazovska, The sphere packing problem in dimension 24. Ann. of Math. (2) 185 (2017), no. 3, 1017-1033.

[3] ↑ T. Fernique, Empilements de disques de densité maximale, 2019.

[4] ↑T. C. Hales, A proof of the Kepler conjecture. Ann. of Math. (2) 162 (2005), no. 3, 1065-1185.

[5] ↑T. C. Hales, M. Adams, G. Bauer, T. D. Dang, J. Harrison, Le Truong Hoang, C. Kaliszyk, V. Magron, S. McLaughlin, T. T. Nguyen, Q. T. Nguyen, T. Nipkow, S. Obua, J. Pleso, J. Rute, A. Solovyev, T. H. A. Ta, N. T. Tran, T. D. Trieu, J. Urban, K. Vu, R. Zumkeller, A formal proof of the Kepler conjecture. Forum Math. Pi 5 (2017), e2, 29 pp.

[6] ↑ C. Mann, J. McLoud-Mann, D. von Derau, Convex pentagons that admit i-block transitive tilings. Geom. Dedicata 194 (2018), 141-167.

[7] ↑ M. Rao, Exhaustive search of convex pentagons which tile the plane. ArXiv 1708.00274.

[8] ↑ A. Thue, Über die dichteste Zusammenstellung von kongruenten Kreisen in einer Ebene, Skrifter udg. af Videnskabs-Selskabet i Christiania., 1. Math.-naturv. kl. ; 1910, 1.

[9] ↑ M. Viazovska, The sphere packing problem in dimension 8. Ann. of Math. (2) 185 (2017), no. 3, 991-1015.