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 XX^e 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

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 13^e. 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 13^e pouvait être ajoutées. Certaines preuves, mais incomplètes, de l'affirmation de Newton ont été proposées au XIX^e siècle, notamment une de Reinhold Hoppe (en)[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

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

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

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

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

Le problème du nombre de contact peut être formulé comme l'existence d'une solution pour un ensemble d'inégalités. Soit $x=(x_{n})_{n\in \{1,\ldots ,N\}}$ 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] :

\exists x\ \left\{(\forall n)\{x_{n}^{T}x_{n}=1\}\land (\forall m,n\mid m\neq n)\{(x_{n}-x_{m})^{T}(x_{n}-x_{m})\geq 1\}\right\}

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 $(m,n)\mid m<n$ .

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 $y_{n,m}$ le système peut être transformé en une seule équation quartique en $N(N-1)/2+DN$ variables :

\exists x,y\ \left\{\sum _{n}(x_{n}^{T}x_{n}-1)^{2}+\sum _{m,n\mid m<n}{\Big (}(x_{n}-x_{m})^{T}(x_{n}-x_{m})-1-(y_{nm})^{2}{\Big )}^{2}=0\right\}

.

Dans la matrice $y=(y_{m,n})_{N\times {N}}$ 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 $N(N-1)/2$ 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é $R_{m,n}$ entre la m ^ième et la n ^ième sphère.

\exists R\ \{\forall _{n}\{R_{0,n}=1\}\land \forall _{m,n:m<n}\{R_{m,n}\geq 1\}\}

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 $R_{m,n}=1+{y_{m,n}}^{2}$ , 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

(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, 1999 (ISBN 0-387-98585-9), p. 21.
Peter Brass, W. O. J. Moser et János Pach, Research problems in discrete geometry, Springer, 2005 (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,‎ 2009, p. 174–178 (arXiv 0902.1105).
(en) Bill Casselman, « The Difficulties of Kissing in Three Dimensions », Notices of the AMS, vol. 51, n^o 8,‎ septembre 2004, 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,‎ 1874, p. 302–306.
S. Günther, « Ein stereometrisches Problem », Archiv Math. Physik, vol. 57,‎ 1875.
Reinhold Hoppe, « Bemerkung der Redaction », Archiv Math. Physik, vol. 56,‎ 1874, p. 307–312.
Kurt Schütte et Bartel Leendert van der Waerden, « Das Problem der dreizehn Kugeln », Math. Annalen, vol. 125,‎ 1953, p. 325–334.
John Leech, « The Problem of Thirteen Spheres », The Mathematical Gazette, vol. 40,‎ 1956, p. 23
O. R. Musin, « The problem of the twenty-five spheres », Russ. Math. Surv., vol. 58, n^o 4,‎ 2003, p. 794–795 (DOI 10.1070/RM2003v058n04ABEH000651)
Pfender et Ziegler 2004.
(ru) Levenshtein, « О границах для упаковок в n-мерном евклидовом пространстве », Doklady Akademii Nauk SSSR, vol. 245, n^o 6,‎ 1979, 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, n^o 2,‎ 1979, 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, n^o 4,‎ 1999, p. 287–294 (Math Reviews 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. 2^e é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,‎ décembre 2012, p. 1540–1549 (lire en ligne)
Kammer et Tholey, « Approximation Algorithms for Intersection Graphs », Algorithmica, vol. 68, n^o 2,‎ juillet 2012, 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, n^o 14,‎ 1. september 2007, p. 1837–1841 (DOI 10.1016/j.dam.2006.05.012, lire en ligne).

Bibliographie

Tomaso Aste et Denis Weaire, The pursuit of perfect packing, New York, Taylor & Francis, 2008, 2^e é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, n^o 3,‎ 2008, p. 909–924 (DOI 10.1090/S0894-0347-07-00589-9, Math Reviews 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, n^o 8,‎ septembre 2004, p. 873–883 (lire en ligne).
Bill Casselman, « The Difficulties of Kissing in Three Dimensions », Notices of the American Mathematical Society, vol. 51, n^o 8,‎ septembre 2004, 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

Grime, « Kissing Numbers » [vidéo], youtube, Brady Haran (consulté le 11 octobre 2018)

Articles connexes

Code sphérique (en)
Hexlet de Soddy
Empilement compact de sphères dans un cylindre (en)
Problème de Tammes

Portail des mathématiques
Portail de l'informatique théorique

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.

[Conway-1] John Horton Conway et Neil J.A. Sloane, Sphere Packings, Lattices and Groups, New York, Springer-Verlag, 1999 (ISBN 0-387-98585-9), p. 21.

[Brass-2] Peter Brass, W. O. J. Moser et János Pach, Research problems in discrete geometry, Springer, 2005 (ISBN 978-0-387-23815-9), p.93 .

[Mittlemann-3] Hans D. Mittelmann et Frank Vallentin, « High accuracy semidefinite programming bounds for kissing numbers », Experimental Mathematics, vol. 19,‎ 2009, p. 174–178 (arXiv 0902.1105).

[4] (en) Bill Casselman, « The Difficulties of Kissing in Three Dimensions », Notices of the AMS, vol. 51, n^o 8,‎ septembre 2004, 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,‎ 1874, p. 302–306.

[6] S. Günther, « Ein stereometrisches Problem », Archiv Math. Physik, vol. 57,‎ 1875.

[7] Reinhold Hoppe, « Bemerkung der Redaction », Archiv Math. Physik, vol. 56,‎ 1874, p. 307–312.

[8] Kurt Schütte et Bartel Leendert van der Waerden, « Das Problem der dreizehn Kugeln », Math. Annalen, vol. 125,‎ 1953, p. 325–334.

[9] John Leech, « The Problem of Thirteen Spheres », The Mathematical Gazette, vol. 40,‎ 1956, p. 23

[Musin-10] O. R. Musin, « The problem of the twenty-five spheres », Russ. Math. Surv., vol. 58, n^o 4,‎ 2003, p. 794–795 (DOI 10.1070/RM2003v058n04ABEH000651)

[PfenderZiegler2004-11] Pfender et Ziegler 2004.

[12] (ru) Levenshtein, « О границах для упаковок в n-мерном евклидовом пространстве », Doklady Akademii Nauk SSSR, vol. 245, n^o 6,‎ 1979, 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, n^o 2,‎ 1979, p. 210—214.

[Zinoviev99-14] V. A. Zinov'ev et T. Ericson, « New Lower Bounds for Contact Numbers in Small Dimensions », Problems of Information Transmission, vol. 35, n^o 4,‎ 1999, p. 287–294 (Math Reviews 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. 2^e é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,‎ décembre 2012, p. 1540–1549 (lire en ligne)

[19] Kammer et Tholey, « Approximation Algorithms for Intersection Graphs », Algorithmica, vol. 68, n^o 2,‎ juillet 2012, 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, n^o 14,‎ 1. september 2007, p. 1837–1841 (DOI 10.1016/j.dam.2006.05.012, lire en ligne).