Aller au contenu

Nombre de contact

Un article de Wikipédia, l'encyclopédie libre.

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 | modifier le code]
Le nombre de contact en dimension un est 2.
Le nombre de contact en dimension deux est 6.
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. Cela laisse un espace entre deux sphères voisines qui est un peu plus grand qu'un dixième du rayon.
Un icositétrachore en rotation.

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

[modifier | modifier le code]

Le 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.

Le volume occupé par un arrangement en n dimensions croît de façon exponentielle en fonction de n. La zone grisée dans le graphique représente les valeurs possibles entre les bornes supérieures et inférieures connues. Les points représentent des valeurs connues exactement.
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

[modifier | modifier le code]

Les nombres de contact en treillis sont connus pour les dimension 1 à 9, et pour 24[16],[17].

Nombre de contact en treillis pour les dimensions 1–12
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
Nombre de contact en treillis pour les dimensions 13–24
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

[modifier | modifier le code]

Le 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

[modifier | modifier le code]

Il 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

[modifier | modifier le code]

Le 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.

Sur les autres projets Wikimedia :

Notes et références

[modifier | modifier le code]
  1. a b et c John Horton Conway et Neil J.A. Sloane, Sphere Packings, Lattices and Groups, New York, Springer-Verlag, (ISBN 0-387-98585-9), p. 21.
  2. a et b Peter Brass, W. O. J. Moser et János Pach, Research problems in discrete geometry, Springer, (ISBN 978-0-387-23815-9), p.93 .
  3. a et b Hans D. Mittelmann et Frank Vallentin, « High accuracy semidefinite programming bounds for kissing numbers », Experimental Mathematics, vol. 19,‎ , p. 174–178 (arXiv 0902.1105).
  4. (en) Bill Casselman, « The Difficulties of Kissing in Three Dimensions », Notices of the AMS, vol. 51, no 8,‎ , p. 884-885 (lire en ligne)
  5. 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.
  6. S. Günther, « Ein stereometrisches Problem », Archiv Math. Physik, vol. 57,‎ .
  7. Reinhold Hoppe, « Bemerkung der Redaction », Archiv Math. Physik, vol. 56,‎ , p. 307–312.
  8. Kurt Schütte et Bartel Leendert van der Waerden, « Das Problem der dreizehn Kugeln », Math. Annalen, vol. 125,‎ , p. 325–334.
  9. (en) John Leech, « The Problem of Thirteen Spheres », The Mathematical Gazette, vol. 40,‎ , p. 23
  10. a et b O. R. Musin, « The problem of the twenty-five spheres », Russ. Math. Surv., vol. 58, no 4,‎ , p. 794–795 (DOI 10.1070/RM2003v058n04ABEH000651)
  11. Pfender et Ziegler 2004.
  12. (ru) Levenshtein, « О границах для упаковок в n-мерном евклидовом пространстве », Doklady Akademii Nauk SSSR, vol. 245, no 6,‎ , p. 1299–1303
  13. 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.
  14. 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
  15. Réseau de Leech
  16. 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).
  17. Neil J. A. Sloane, Gabriele Nebe, Table of Highest Kissing Numbers Presently Known.
  18. Jeffrey C. Lagarias et Chuanming Zong, « Mysteries in packing regular tetrahedra », Notices of the American Mathematical Society,‎ , p. 1540–1549 (lire en ligne)
  19. Kammer et Tholey, « Approximation Algorithms for Intersection Graphs », Algorithmica, vol. 68, no 2,‎ , p. 312–336 (DOI 10.1007/s00453-012-9671-1).
  20. 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 | modifier le code]

Liens externes

[modifier | modifier le code]

Articles connexes

[modifier | modifier le code]