Nombre de contact
En géométrie, le nombre de contact ou nombre de Newton ou nombre de baisers (de l'anglais kissing number) d'un espace est défini comme le plus grand nombre de boules identiques qui peuvent être placées dans cet espace sans qu'elles ne se chevauchent et telles que chacune touche une boule identique commune. Le terme nombre de Newton renvoie à Isaac Newton, l'auteur du problème en trois dimensions.
Le problème du nombre de contact consiste à déterminer le plus grand nombre de contact pour des sphères n-dimensionnelles dans l'espace euclidien de dimension n + 1. Les sphères ordinaires correspondent à des surfaces fermées bidimensionnelles dans un espace tridimensionnel. Si les arrangements sont limités à des arrangements en treillis, dans lesquels les centres des sphères sont positionnés sur des points d'un treillis, alors ce nombre de contact est appelé le nombre de contact en treillis.
Déterminer le nombre de contact lorsque les centres des boules sont alignés sur une droite (le cas unidimensionnel) ou dans un plan (le cas à deux dimensions) est aisé. Une solution du cas tridimensionnel, bien qu'il soit facile à conceptualiser et à modéliser dans le monde physique, n'est connue que depuis le milieu du XXe siècle[1],[2]. Les solutions dans des dimensions supérieures sont considérablement plus difficiles, et seuls dans quelques cas connaît-on la solution exacte. Pour d'autres, des estimations sont données pour des bornes supérieures et inférieures, mais pas des solutions exactes[3].
Nombres de contact connus
modifier
En dimension un, les boules sont juste des segments de droites dont la longueur est l'unité. Le nombre de contact est 2.
En deux dimensions, le nombre de contact est 6. Les boules sont des disques unitaires ; on peut imaginer qu'elles représentent des pièces de monnaie que l'on arrange pour qu'elles touchent toutes une pièce commune.
En trois dimensions, le nombre de contact est 12, mais la valeur correcte est beaucoup plus difficile à établir que dans les dimensions un et deux. Il est facile de disposer 12 sphères de manière que chacune touche une sphère centrale : une réalisation du nombre de contact 12 en trois dimensions consiste à aligner les centres des sphères externes sur les sommets d'un icosaèdre régulier. En faisant cela, il reste beaucoup d'espace et il n'est pas évident qu'il n'y aurait pas moyen de tasser les boules pour insérer une 13e. En fait, il y a suffisamment d'espace supplémentaire pour déplacer deux des 12 sphères extérieures jusqu'à échanger leurs places[1] par un mouvement continu sans qu'aucune des sphères extérieures ne perde le contact avec la sphère centrale. Le problème a, selon la tradition[4], fait l'objet d'un célèbre désaccord entre les mathématiciens Isaac Newton et David Gregory en 1692 à propos de la conjecture de Kepler. Newton pensait à juste titre que la limite était de 12 ; Gregory pensait qu'une 13e pouvait être ajoutées. Certaines preuves, mais incomplètes, de l'affirmation de Newton ont été proposées au XIXe siècle, notamment une de Reinhold Hoppe[5],[6],[7] mais, d'après Brass, Moser et Pach[2], les premières preuves correctes n'ont été publiées qu'en 1953 par Kurt Schütte et Bartel Leendert van der Waerden[8] et en 1956 par John Leech[9],[1].
Les douze voisins de la sphère centrale correspondent au nombre de coordination maximal d'un atome dans un réseau cristallin dans lequel tous les atomes ont la même taille. Un nombre de coordination égal à 12 se trouve dans une structure cubique fermée ou hexagonale serrée.
En quatrième dimension, on savait depuis un certain temps que la réponse était soit 24, soit 25. Il est simple de produire un groupement de 24 sphères autour d'une sphère centrale, en plaçant les sphères aux sommets d'un icositétrachore (ou « 24-cellules ») convenablement mises à l'échelle etcentrées à l'origine). Comme dans le cas tridimensionnel, il reste beaucoup d'espace — en fait encore plus que pour n = 3 — donc la situation était encore moins claire. En 2003, Oleg Musin a prouvé que le nombre de contact pour n = 4 était de 24, en utilisant un raisonnement subtil[10],[11].
En dimension n > 4, le nombre de contact n'est connu que pour n = 8, où il vaut 240 et pour n = 24, où il est égal à 196 560[12],[13]. Les résultats dans ces dimensions proviennent de l'existence de réseaux très symétriques : le réseau E8 (en) et le réseau de Leech.
Si les arrangements sont limités à des arrangements en treillis, dans lesquels les centres des sphères sont positionnés sur des points d'un treillis, alors ce nombre de contact, appelé le nombre de contact en treillis est connu pour les dimensions de n = 1 à 9 et pour n = 24. Pour les dimensions 5, 6 et 7, le nombre de contact en treillis est aussi le nombre de contact général le plus élevé connu jusqu'à présent.
Table des encadrements connus
modifierLe tableau suivant liste certaines bornes connues pour le nombre de contact en fonction des dimensions[3]. Les dimensions pour lesquelles le nombre de contact est connu exactement sont indiquées en gras.
| Dimension | Minorant | Majorant |
|---|---|---|
| 1 | 2 | |
| 2 | 6 | |
| 3 | 12 | |
| 4 | 24[10] | |
| 5 | 40 | 44 |
| 6 | 72 | 78 |
| 7 | 126 | 134 |
| 8 | 240 | |
| 9 | 306 | 364 |
| 10 | 500 | 554 |
| 11 | 582 | 870 |
| 12 | 840 | 1357 |
| 13 | 1154[14] | 2069 |
| 14 | 1606 | 3183 |
| 15 | 2564 | 4866 |
| 16 | 4320 | 7355 |
| 17 | 5346 | 11072 |
| 18 | 7398 | 16572 |
| 19 | 10668 | 24812 |
| 20 | 17400 | 36764 |
| 21 | 27720 | 54584 |
| 22 | 49,896 | 82340 |
| 23 | 93150 | 124416 |
| 24 | 196560[15] | |
Table des nombres de contact en treillis
modifierLes nombres de contact en treillis sont connus pour les dimension 1 à 9, et pour 24[16],[17].
| Dimension | Nombre de contact en treillis |
|---|---|
| 1 | 2 |
| 2 | 6 |
| 3 | 12 |
| 4 | 24 |
| 5 | 40 |
| 6 | 72 |
| 7 | 126 |
| 8 | 240 |
| 9 | 272 |
| 10 | ≥ 336 |
| 11 | ≥ 438 |
| 12 | ≥ 756 |
| Dimension | Nombre de contact en treillis |
|---|---|
| 13 | ≥ 918 |
| 14 | ≥ 1422 |
| 15 | ≥ 2340 |
| 16 | ≥ 4320 |
| 17 | ≥ 5346 |
| 18 | ≥ 7398 |
| 19 | ≥ 10668 |
| 20 | ≥ 17400 |
| 21 | ≥ 27720 |
| 22 | ≥ 49896 |
| 23 | ≥ 93150 |
| 24 | 196560 |
Généralisation
modifierLe problème du nombre de contact peut être généralisé au problème de la recherche du nombre maximum de copies congruentes non chevauchantes de tout corps convexe qui touche un exemplaire donné du corps. Il existe différentes versions du problème selon que les copies doivent seulement être des copies congruentes, ou translatées du corps original ou translatées sur un treillis. Pour le tétraèdre régulier, par exemple, il est connu que le nombre de contact en treillis et le nombre de contact par translation sont égaux à 18, alors que le nombre de contact congruents est d'au moins 56[18]
Algorithmes
modifierIl existe plusieurs algorithmes d'approximation sur les graphes d'intersection où le rapport d'approximation dépend du nombre de contacts[19]. Par exemple, il existe un algorithme d'approximation en temps polynomial pour trouver un sous-ensemble maximal non intersectant d'un ensemble de carrés unitaires ayant subi des rotations.
Formulation mathématique
modifierLe problème du nombre de contact peut être formulé comme l'existence d'une solution pour un ensemble d'inégalités. Soit un ensemble de N vecteurs en dimension D qui désignent les centres des sphères. On suppose que les rayons des sphères valent 1/2. La condition pour que cet ensemble de sphères puisse être placé autour de la sphère centrale sans chevauchement est[20] :
La condition sous le deuxième quantificateur universel ne chanqe pas si l'on échange m et n ; on il suffit donc que ce quantificateur porte sur .
Ainsi, le problème peut être exprimé, pour chaque dimension, dans la théorie existentielle sur les réels. Cependant, les méthodes générales de résolution de problèmes sous cette forme prennent au moins un temps exponentiel ; c'est pourquoi ce problème n'a été résolu que jusqu'à la dimension quatre. En ajoutant des variables supplémentaires le système peut être transformé en une seule équation quartique en variables :
- .
Dans la matrice seules les entrées pour m<n sont nécessaires ou, de manière équivalente, la matrice peut être supposée antisymétrique. La matrice n'a que variables libres.
Par conséquent, la résolution du cas en dimension D = 5 et avec N = 40 + 1 équivaut à déterminer l'existence de solutions réelles d'un polynôme quartique en 1025 variables. Pour les dimensions D = 24 et N = 196560 + 1, le polynôme quartique aurait 19 322 732 544 variables. Un autre énoncé en termes de géométrie de distance est donné par les distances au carré entre la m ième et la n ième sphère.
Cette condition doit être complétée par la condition que le déterminant de Cayley–Menger est nul pour tout ensemble de points qui forme un ( D + 1) simplex en dimension D, puisque ce volume doit être nul. En posant , cela donne un ensemble d'équations polynomiales simultanées en y qui doivent être résolues pour des valeurs réelles uniquement. Les deux méthodes, étant tout à fait équivalentes, ont des usages différents. Par exemple, dans le second cas, on peut modifier aléatoirement les valeurs de y par petites quantités pour essayer de minimiser le polynôme en termes de y.
Notes et références
modifier- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Kissing number » (voir la liste des auteurs).
- John Horton Conway et Neil J.A. Sloane, Sphere Packings, Lattices and Groups, New York, Springer-Verlag, (ISBN 0-387-98585-9), p. 21.
- Peter Brass, W. O. J. Moser et János Pach, Research problems in discrete geometry, Springer, (ISBN 978-0-387-23815-9), p.93 .
- Hans D. Mittelmann et Frank Vallentin, « High accuracy semidefinite programming bounds for kissing numbers », Experimental Mathematics, vol. 19, , p. 174–178 (arXiv 0902.1105).
- (en) Bill Casselman, « The Difficulties of Kissing in Three Dimensions », Notices of the AMS, vol. 51, no 8, , p. 884-885 (lire en ligne)
- C. Bender, « Bestimmung der größten Anzahl gleich Kugeln, welche sich auf eine Kugel von demselben Radius, wie die Übrigen, auflegen lassen », Archiv Math. Physik, vol. 56, , p. 302–306.
- S. Günther, « Ein stereometrisches Problem », Archiv Math. Physik, vol. 57, .
- Reinhold Hoppe, « Bemerkung der Redaction », Archiv Math. Physik, vol. 56, , p. 307–312.
- Kurt Schütte et Bartel Leendert van der Waerden, « Das Problem der dreizehn Kugeln », Math. Annalen, vol. 125, , p. 325–334.
- (en) John Leech, « The Problem of Thirteen Spheres », The Mathematical Gazette, vol. 40, , p. 23
- O. R. Musin, « The problem of the twenty-five spheres », Russ. Math. Surv., vol. 58, no 4, , p. 794–795 (DOI 10.1070/RM2003v058n04ABEH000651)
- Pfender et Ziegler 2004.
- (ru) Levenshtein, « О границах для упаковок в n-мерном евклидовом пространстве », Doklady Akademii Nauk SSSR, vol. 245, no 6, , p. 1299–1303
- Andrew Odlyzko et Neil Sloane, « New bounds on the number of unit spheres that can touch a unit sphere in n dimensions », J. Combin. Theory Ser. A, vol. 26, no 2, , p. 210—214.
- V. A. Zinov'ev et T. Ericson, « New Lower Bounds for Contact Numbers in Small Dimensions », Problems of Information Transmission, vol. 35, no 4, , p. 287–294 (MR 1737742, lire en ligne) — L'article original est en russe
- Réseau de Leech
- John Horton Conway, Neil J. A. Sloane: « The Kissing Number Problem » et « Bounds on Kissing Numbers » dans John Horton Conway, Neil J. A. Sloane: Sphere Packings, Lattices, and Groups. 2e édition, Springer-Verlag, New York 1993. pages 21–24 et 337–339, (ISBN 0-387-98585-9).
- Neil J. A. Sloane, Gabriele Nebe, Table of Highest Kissing Numbers Presently Known.
- Jeffrey C. Lagarias et Chuanming Zong, « Mysteries in packing regular tetrahedra », Notices of the American Mathematical Society, , p. 1540–1549 (lire en ligne)
- Kammer et Tholey, « Approximation Algorithms for Intersection Graphs », Algorithmica, vol. 68, no 2, , p. 312–336 (DOI 10.1007/s00453-012-9671-1).
- Sergei Kucherenko et al., « New formulations for the Kissing Number Problem », Discrete Applied Mathematics, vol. 155, no 14, 1. september 2007, p. 1837–1841 (DOI 10.1016/j.dam.2006.05.012, lire en ligne).
Bibliographie
modifier- Tomaso Aste et Denis Weaire, The pursuit of perfect packing, New York, Taylor & Francis, , 2e éd., xiv+200 (ISBN 978-1-4200-6817-7, zbMATH 1159.52019).
- Christine Bachoc et Frank Vallentin, « New upper bounds for kissing numbers from semidefinite programming », Journal of the American Mathematical Society, vol. 21, no 3, , p. 909–924 (DOI 10.1090/S0894-0347-07-00589-9, MR 2393433, arXiv math.MG/0608426)
- Table of the Highest Kissing Numbers Presently Known maintenue par Gabriele Nebe et Neil Sloane
- Florian Pfender et Günter M. Ziegler, « Kissing numbers, sphere packings, and some unexpected proofs », Notices of the American Mathematical Society, vol. 51, no 8, , p. 873–883 (lire en ligne).
- Bill Casselman, « The Difficulties of Kissing in Three Dimensions », Notices of the American Mathematical Society, vol. 51, no 8, , p. 884-885 (lire en ligne).
- (en) Eric W. Weisstein, « Kissing Number », sur MathWorld
- (en) Eric W. Weisstein, « Coxeter-Todd Lattice », sur MathWorld
- (en) Eric W. Weisstein, « Leech Lattice », sur MathWorld
Liens externes
modifier- Grime, « Kissing Numbers » [vidéo], youtube, Brady Haran (consulté le )
