Question Du Lundi n°4: "Kissing numbers"

Norbert Verdier3
Norbert Verdier3
dans Géométrie
La « question du lundi » n°4, 29 septembre 2008: « Kissing numbers » !

Ami(e)s du lundi et des autres jours, Bonjour;

Un de mes amis (anglophone), Keerthi, m'interroge au sujet des "kissing numbers" :

"Recently I have undergone a course on optimization and there was one problem which the professor had asked us to solve. The problem is well known as "Kissing Number" Problem. To start with I would like to work on the two dimensional space and the geometric elements of circles with uniform shape with the same diameter. In this case the Kissing Number is the number of adjusent circles whose surfaces touch each other but which are not overlapping. From intusion we could say the kissing number is 6 as we could form the circles by keeping their center as the vertex of the hexogonal and one more circle in the center of the hexogonal. There can be 7 partcipating circles and 6 surfaces in contact which means 6 is the kissing numbers possible.

But I would like to formulate the kissing number problem as an equation to be solved using optimisation techniques. That means there shall be an equation which would have the property to be maximised. That is in this case Kissing number, and there will be constraints which will restrict this maximisation like no overlapping condition.

In my idea, the parameters for this formulation are; Uniform Circles with diameter d are identified by Cx, where x = 0 to N. This implies the kissing number is N and the centered circle is C0. If the two uniform circles touch each other then the distance between their centers shall be d, which is the diameter of these circles. Distance is an function with parameters (Cx, Cy), where x not equal to y and the value of the distance shall be equal to d. I got to prove N is 7.

Constraint 1:
For i = 1 to N
Distance(C0, Ci) = d

Constraint 2:
For j = 1 to N
For k = 1 to N and j is not equal to k
Distance(Cj, Ck) >= d

Constraint 1 = is neighbourhood condition for the centered circle C0, and Constraint 2 is non overlapping condition between all the participating circles. I guess the maxmization parameter here is N.

Geometrically I would like to use the formulas so that I could maximize N. I do not know if I have to use the circumference of the circle to identify the remaining space on the surface of the circle C0 to place another circle. Spatially I could imagine circle C0 located at the origin (0, 0). Then I can consider the first Kissing point of (0, r) where the circle C0 and C1 touch each other. Now my problem comes how mathematically I could place the second circle C2 which touches both C0 and C1 at one point each. My problem is also to identify an optimization technique which I could use to solve this problem.

Could you be able to provide me some hints in solving this problem? »

Could you be able to provide us some hints in solving Keerthi’s problem ? Thanks. Best regards. Norbert.

Réponses

  • Ga?
    Ga?
    Bonjour Norbert,

    J'avoue que je ne comprends pas très bien l'objet de cette question. Le "kissing number" dans le plan ne pose absolument aucun problème, et je ne vois pas l'intérêt d'y introduire une technique d'optimisation.

    Cordialement,

    Ga?

    ******************
    Pourquoi faire simple quand on peut faire compliqué?
  • Norbert Verdier3
    Norbert Verdier3
    Bonjour à tous, Merci Ga;

    Je pense qu'au delà de la dimension 2, son problème concerne les techniques d'optimisation liées au kissing nuumbers. Je lui avait répondu :

    "But I know that last year, a good article about that would be published : "New formulations for the Kissing Number Problem" by Kucherenko, Belotti and Maculan [Discrete applied mathematics, 2007, Vol. 155, Issue 14]. This journal is probably in Ecole des Mines. Do you know this article? Serguei Kucherenko (Imperial College of London) is one of the best researcher about kissing numbers. In his method of optimization, he used "Monte Carlo method". One idea is to contact Kucherenko [s.kucherenko@ic.ac.uk.] in order to have a discussion about that or for having a preprint of this article."

    Cette question a été lancée sur le forum pour avoir accès à toute idée d'optimisation autour de ces problèmes de kissing numbers. Amicalement. Norbert.
  • bs
    bs
    Bonjour,

    N'étant plus trop familiarisé avec l'anglais, j'ai essayé un logiciel de traduction automatique: voilà le résultat, pas vraiment concluant.


    "Récemment j'ai subi un cours sur l'optimisation et il y avait un problème que le professeur nous avait demandé de résoudre. Le problème est bien connu comme" Embrassant le Numéro(Nombre) "le Problème. Pour commencer par je voudrais travailler(marcher) sur le deux espace dimensionnel et les éléments géométriques de cercles avec la forme uniforme avec le même diamètre. Dans ce cas le Numéro(Nombre) s'embrassant est le numéro(nombre) de cercles adjusent dont les surfaces se touchent, mais qui ne se chevauche pas.

    Dans mon idée, les paramètres pour cette formulation sont; des cercles Uniformes avec le diamètre d sont identifiés par Cx, où x = 0 à N. Cela implique que le numéro(nombre) s'embrassant est N et le cercle centré est C0. Si les deux cercles uniformes se touchent alors la distance entre leurs centres sera d, qui est le diamètre de ces cercles. La distance est une fonction avec des paramètres (Cx, Cy), où x non égal à y et la valeur de la distance sera égal à Égal à d.

    Je suis arrivé pour prouver que N est 7.
    Contrainte 1 : Car je = 1 à Distance N (C0, Ci) = d
    Contrainte 2 : Pour j = 1 à N Pour k = 1 à N et j n'est pas égal à la Distance k (Cj, Ck) > = d
    La contrainte 1 = est la condition de voisinage pour le cercle centré C0 et la Contrainte 2 ne chevauche pas de condition entre tous les cercles participants. Je devine le paramètre maxmization voici N.

    Géométriquement je voudrais utiliser les formules pour que je puisse maximiser N. Je ne sais(connais) pas si je dois utiliser la circonférence du cercle pour identifier l'espace restant sur la surface du cercle C0 pour placer un autre cercle. Dans l'espace je pourrais imaginer le cercle C0 situé à l'origine (0, 0). Alors je peux considérer le premier point d'Embrassement (de 0, r) où le cercle C0 et C1 se touche. Maintenant mon problème vient comment mathématiquement je pourrais placer le deuxième cercle C2 que touche tant C0 que C1 une fois chacun. Mon problème est aussi d'identifier une technique d'optimisation que je pourrais utiliser pour résoudre ce problème.
    Pourriez-vous être capables de me fournir quelques allusions dans la résolution de ce problème ? "

    Amicalement.
  • Norbert Verdier3
    Norbert Verdier3
    Merci Bernard;

    A ma connaissance, il n'existe pas vraiment de références en français sur le "kissing numbers". Cela ferait un très bel article pour une revue de vulgarisation comme Quadrature. Amicalement. N
  • Ga?
    Ga?
    Bonsoir,

    J'ai jeté un coup d'oeil au papier de Kucherenko et al. L'idée est assez simple. Si on fixe $D$ (la dimension) et $N$ (le nombre de sphères), on cherche à maximiser $\alpha$ avec
    $\Vert x^i\Vert^2=4$ pour $i=1,\ldots,N$ et $\Vert x^i-x^j\Vert^2 \geq 4\,\alpha$ pour $j\neq i$, où les $x^i$ sont dans $\mathbb{R}^n$. Si on trouve un maximum $\geq 1$ on peut embrasser $N$ sphères, et si on trouve un maximum $<1$ c'est raté.
    Les auteurs utilisent des méthodes d'optimisation et trouvent les bons nombres en dimension 2, 3 et 4 et disent s'attaquer à la dimension 5.

    Je suis un peu perplexe. Les méthodes d'optimisation utilisées donnent des résultats approchés (et avec quelle garantie?). Ils pourraient éventuellement indiquer qu'il existe des configurations avec un plus grand nombre d'embrassements que les configurations actuellement connues (j'en doute), mais je ne vois pas comment ces méthodes pourraient donner une PREUVE de la maximalité d'un kissing number dans une dimension fixée. Or c'est ce problème de preuve qui est difficile (pour la dimension 4 l'article de Musin est publié aux Annals of Math. cette année). Il me semble que le problème du Kissing Number peut servir de banc d'essai pour des méthodes d'optimisation, mais que ces méthodes n'apportent (du moins pour le moment) rien de nouveau pour le problème.

    Je suis sans doute mauvais juge concernant l'intérêt de l'article cité par Norbert. Si d'autres intervenants ont un avis plus éclairé, je suis preneur.

    A signaler à propos du kissing number en dimension 8 : le problème de Mathématiques Générales 2005 de l'agrégation externe contient entre autres une preuve qu'il est au moins égal à 240 (pour un réseau).

    Cordialement.
  • bs
    bs
    Bonjour,

    Tout ou presque sur les Kissing numbers ,

    Et aussi dans OEIS ,

    Amicalement.
  • Yersinia Pestis
    Yersinia Pestis
    Ben mince alors... moi qui m'attendais à trouver là un sujet un peu chaud...
    Quelle déception! X:-(

    A quand un topic : "mathématiques et érotisme"!!?? ;)

    Celà dit il parrait qu'on vient de découvrir dans les archives de la BNF une correspondance inédite entre madame Gauss et madame Cauchy : l'une s'y plaint que son mari est plutôt limité alors que l'autre, au contraire, estime qu'il utilise fort bien son pivot... :D

    A+

    Emmanuel
Connectez-vous ou Inscrivez-vous pour répondre.

Bonjour!

Pour participer au forum, cliquer sur l'un des boutons :

Connexion S'inscrire

Catégories

In this Discussion

Français