Vecteurs presque orthogonaux

Georges Abitbol

On dit que deux vecteurs unitaires sont écartés si leur produit scalaire est inférieur à $\frac{\sqrt{2}}{2}$.

Quel est le nombre maximum de vecteurs deux à deux écartés que l'on peut trouver sur la sphère de dimension $2$ ? Je suis sûr que ce problème est super classique !

Math Coss

Je dirais $8$ ou $9$.

Au moins $8$ car les sommets d'un cube sont deux à deux écartés (produit scalaire : $1/\sqrt3$).

Pas plus de $9$ parce que pour un vecteur donné, disons le vecteur $(0,0,1)$, l'ensemble des vecteurs qui ne sont pas écartés sont ceux de la calotte comprise entre les plans $z=1/\sqrt2$ et $z=1$. Grâce à Archimède, on sait que son aire est celle du cylindre de diamètre $2/\sqrt2=\sqrt2$ et de hauteur $1-1/\sqrt2$, c'est-à-dire $\pi\sqrt2\bigl(1-1/\sqrt2\bigr)=\pi\bigl(\sqrt2-1\bigr)$.

Le nombre de calottes que l'on peut mettre sans chevauchement sur une sphère d'aire $4\pi$ est donc majoré par \[\left\lfloor\frac{4\pi}{\pi(\sqrt2-1\bigr)}\right\rfloor=9.\]

Georges Abitbol

Euuuuh... Attends, si on inscrit un octogone régulier dans un équateur, alors ces sommets marchent (enfin, il me semble) et on doit pouvoir rajouter le pôle Nord et le pôle Sud.

Tu es sûr de ton Archimède ? L'aire de la calotte est l'aire du cylindre de diamètre le diamètre de toute la sphère, pas le diamètre de la calotte.

Et puis, attention, en fait, deux vecteurs sont écartés si les calottes centrées en eux et d'angle $\frac{\pi}{8}$ sont disjointes, pas $\frac{\pi}{4}$.

Math Coss

Pour calculer sans Archimède l'aire de la calotte d'angle au centre $\alpha$ autour de $(0,0,1)$, je calcule avec pour coordonnées sphérique longitude-colatitude $(\theta,\phi)$, i.e. ces coordonnées désignent $(\sin\phi\cos\theta,\sin\phi\sin\theta,\cos\phi)$. L'élément de surface est $\sin\phi\,\mathrm{d}\theta\,\mathrm{d}\phi$, de sorte que l'aire est \[\int_{[0,2\pi]\times[0,\alpha]}\sin\phi\,\mathrm{d}\theta\,\mathrm{d}\phi=2\pi(1-\cos\alpha).\]Tu fais bien de remarquer que si on impose aux calottes d'être disjointes, il convient de diviser l'angle par deux, i.e. prendre $\alpha=\pi/8$ plutôt que $\alpha=\pi/4$. Cela donne alors pour majorant \[\left\lfloor\frac{4\pi}{2\pi\bigl(1-\cos\frac\pi8\bigr)}\right\rfloor=26.\]C'est probablement beaucoup trop pour être une condition pertinente.

Je tente quelques essais numériques.

Math Coss

Avec un dodécaèdre régulier, deux des vingt sommets reliés par une arête ont un produit scalaire de $0{,}74$ environ.

Étonnamment, avec la répartition de vingt points donnée en p.j., il n'y a que dix paires de points qui posent problème (contre trente ci-dessus).

PS : Voici dans l'autre p.j. dix-neuf points qui me semblent deux à deux écartés, obtenus de haute lutte.

GaBuZoMeu

En regardant la page wikipedia "Thomson problem", il semble bien que 18 soit l'optimum, avec un angle minimal de 47.534°.

Math Coss

Mince alors ! Je crois que la liste de dix-neuf points ci-dessous donne un angle minimal de $45{,}136$. Est-ce que quelqu'un pourrait vérifier ?

[(-0.694981308018915, 0.718897478300984, 0.0136893095809882),
(-0.170709045892207, 0.766410952482587, 0.619251704531611),
(0.662940835046976, -0.284684868717329, 0.692433372065945),
(-0.524694706987313, -0.850783268432634, -0.0293818756137444),
(0.190525761883125, -0.872170875126701, 0.450575075475308),
(0.329038831193125, 0.944173069868447, 0.0164517993622266),
(-0.979642747613120, -0.200585704037439, -0.00809088282092192),
(0.603776656069222, 0.507412662964045, -0.614805773435485),
(0.196671715197059, -0.896017582895863, -0.398086331821256),
(-0.174886892920924, 0.804868951697422, -0.567098355911881),
(0.832392986939869, -0.553454284330441, -0.0284652498601860),
(0.587378659041105, 0.503347980671766, 0.633740578830746),
(-0.484098925757123, -0.535686770660191, 0.691872758403201),
(0.600833182117440, -0.295084184367456, -0.742916422892121),
(0.973672675861705, 0.227930073478325, -0.00306624925164643),
(-0.746976378435951, 0.209109224715438, 0.631109833703785),
(-0.757375148665960, 0.209064385753040, -0.618607279938508),
(-0.419817471160785, -0.519012997435877, -0.744566182015266),
(-0.0215563417752754, 0.109123582292587, -0.993794429405247)]

Georges Abitbol

@Math Coss : mon algorithme dit que tes points marchent !

Par contre, je suis dégoûté, mon algorithme à moi n'arrive même pas à trouver 10 points écartés

Math Coss

Cet algorithme fait bouger des espèces d'électrons – maintenant ça me revient, j'avais consulté la page sur le problème de Thomson quand j'ai fait le script. Plus précisément, on place des points au hasard sur la sphère, on les soumet à une force répulsive (en $1/d^2$ je crois, de l'électricité si on veut) et à un peu de frottements (proportionnel à la vitesse), on laisse évoluer (Runge-Kutta est là pour ça) et ça aboutit quelque part.

Je suis tombé sur 19 points bien écartés qui battent la page Wikipédia mais la référence de ladite page est celle d'un très mystérieux Kevin Brown. Bref, c'est bien pour mon amusement ce matin mais ce n'est pas un bouleversement de la physique ou de la géométrie modernes...

PS : Je donne mon code à qui le veut, évidemment.

Georges Abitbol

Ben j'essayais de faire un truc comme ça aussi, mais en fait il n'arrive même pas à trouver quatre vecteurs bien écartés, sauf si par hasard ils le sont déjà au départ xD

Merci pour les infos !

Georges Abitbol

J'en ai 20 !

[[-0.9473083951238701, 0.31923033509220033, 0.026434781723313375], 
[-0.01065719799355906, -0.23060702204443573, -0.9729886050282004], 
[-0.029989260645253858, -0.5746210492833267, 0.8178699737528452], 
[-0.6333208241506013, 0.22200053050806193, -0.7413639444640818], 
[0.772649063131548, 0.18029256380231978, -0.6086936969277137], 
[-0.47756772963339156, -0.8521426460136824, 0.21396722753171318], 
[-0.8047271158225653, -0.21565563658464407, 0.5530885240801582], 
[0.3489009443106665, -0.9151846383822922, 0.2017553189588771], 
[0.6060375016368769, -0.5801795634314155, -0.5441601058385891], 
[0.5752828949171634, -0.07193981692701105, 0.8147847897182643], 
[0.9079404023591432, 0.39399328876252276, 0.1428758698101553], 
[0.3386847584718381, 0.6935719081621003, 0.6358070796926187], 
[0.9109516201699132, -0.3784059196126239, 0.16424404315510177], 
[-0.1485335315337787, -0.8481872033335331, -0.5084449410814743], 
[-0.24181041768833875, 0.1821755656439241, 0.9530686151477802], 
[-0.8319375603409613, -0.42119122245697727, -0.3612171781894192], 
[0.37740405960429807, 0.9149236765855457, -0.14311129171865938], 
[-0.4369538800728791, 0.7647504889172726, 0.47352718653742437], 
[0.12566265882408106, 0.5467017757802671, -0.8278442272166698], 
[-0.4006979745481112, 0.8685432407216883, -0.2916740855641939]]

P.2

Kevin Brown est a Cornell. C'est un specialiste des immeubles de Tits. Ce n'est pas un sot.

Georges Abitbol

Non, justement, sur Internet, les gens disent que ce n'est pas Ken Brown !

P.2

Pardon, OK.

Math Coss

@Georges Abitbol : Désolé d'être déplaisant, je détecte un problème entre les vecteurs d'indices 0 et 6 : \[(-0.9473083951238701, 0.31923033509220033, 0.026434781723313375)\cdot(-0.8047271158225653, -0.21565563658464407, 0.5530885240801582)\ge0{,}708.\]

Math Coss

Cependant, cela correspond à un angle de $44{,}910^\circ$, qu'on trouve dans la ligne 19 de la table de Wikipedia. Dans cette table, l'angle minimal n'est pas décroissant : je soupçonne une permutation des deux valeurs (19 et 20), celle pour 20 correspondant à la configuration que tu viens de donner.

Georges Abitbol

Hahahaha miiince. Je crois que dans ma fonction de test d’écartement, j’avais laissé une petite marge pour pas que le programme croie les vecteurs écartés alors qu’ils ne le sont pas, mais… j’ai mis la marge du mauvais côté 

EDIT : quelqu’un a corrigé mon subjonctif, je recorrige…

i.zitoussi

@Math Coss Tu peux expliquer l’intérêt de l'ajout d'un peu de frottement dans ton système pour la résolution numérique ?

Math Coss

Oui : c'est pour stabiliser un peu le système, i.e. ralentir les points qui sinon se barrent à l'ouest instantanément (enfin, pour des systèmes analogues dans le plan ; sur une sphère ce serait bizarre mais disons que ça tourne de façon inconsidérée). L'analogie, c'est une bille qui descend une pente et rate une position d'équilibre faute de frottements parce qu'elle est « emportée par l'élan ».

Le même genre d'algorithme est très commode pour dessiner des graphes. On met de la force répulsive à distance pour que les sommets soient le plus loin possible les uns des autres ; un ressort pour chaque arête pour rapprocher les points adjacents ; un peu de frottement fluide pour calmer le jeu. Les figures obtenues sont très semblables à celles que produit Sage pour sa fonction "show", qui en fait utilise il me semble cette idée, voire cette méthode.

i.zitoussi

Merci! Je n'y aurais jamais pensé, mais me dis que cette idée a du apparaître expérimentalement, à force de pratiquer.

Pour les graphes, j'avais vu quelque chose de similaire par exemple dans d3.js (pour html/javascript). Je pensais que ça n'avait qu'un but visuel et esthétique, et étais loin de me douter que c'était la méthode. J'adore ce genre de trucs, vraiment astucieux!

Math Coss

Je n'ai rien inventé de ce qui précède. C'est vrai que c'est très amusant de résoudre numériquement des équations de la physique pour des problèmes qui n'ont a priori rien à voir.