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

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^[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.

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.

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

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]

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.

Le problème du nombre de contact peut être formulé comme l'existence d'une solution pour un ensemble d'inégalités. Soit ${\displaystyle 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] :

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

${\displaystyle \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 ${\displaystyle 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 ${\displaystyle 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é ${\displaystyle R_{m,n}}$ entre la m ^ième et la n ^ième sphère.

${\displaystyle \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 ${\displaystyle 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.

• (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).

• 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, 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, 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

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

• 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