Nombre de contacts

Summarize Timeline Fact Check

En dimension un, les boules sont juste des segments de droites dont la longueur est l'unité. Le nombre de contacts est 2^[4].

En dimension deux, le nombre de contacts est 6^[4]. 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 dimension trois, le nombre de contacts est 12, mais la valeur correcte est beaucoup plus difficile à établir que dans les dimensions un et deux^[4]. Il est facile de disposer 12 sphères de manière que chacune touche une sphère centrale : une réalisation du nombre de contacts 12 en dimension 3 consiste à placer les centres des sphères externes aux 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[4]. 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^[5], 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ée^[4]. Certaines preuves, mais incomplètes, de l'affirmation de Newton ont été proposées au XIX^e siècle, notamment une de Reinhold Hoppe^[6],[7],[8] 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^[9] et en 1956 par John Leech^[10],[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 dimension quatre, 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 et centré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 contacts pour n = 4 était de 24, en utilisant un raisonnement subtil^[11],[12].

En dimension n > 4, le nombre de contacts n'est connu que pour n = 8, où il vaut 240 et pour n = 24, où il est égal à 196 560^[13],[14]. 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 réseau, dans lesquels les centres des sphères sont positionnés sur des points d'un réseau, alors ce nombre de contacts, appelé le nombre de contacts en réseau est connu pour les dimensions de n = 1 à 9 et pour n = 24. Pour les dimensions 5, 6 et 7, le nombre de contacts en réseau est aussi le nombre de contacts général le plus élevé connu jusqu'à présent.

Le tableau suivant liste certaines bornes connues pour le nombre de contacts en fonction des dimensions^[3]. Les dimensions pour lesquelles le nombre de contacts est connu exactement sont indiquées en gras.

Les nombres de contacts en réseau sont connus pour les dimension 1 à 9, et pour 24^[17],[18].

Le problème du nombre de contacts 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 réseau. Pour le tétraèdre régulier, par exemple, il est connu que le nombre de contacts en réseau et le nombre de contacts par translation sont égaux à 18, alors que le nombre de contacts congruents est d’au moins 56^[19].

Il existe plusieurs algorithmes d’approximation sur les graphes d’intersection où le rapport d’approximation dépend du nombre de contacts^[20]. 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.

Summarize Timeline Top Qs Fact Check

Le problème du nombre de contacts 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^[21] :

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