Comments on Comment piéger un David Madore

Nicolas (2004-06-03T07:04:55Z)

Bravo !

Tiens un touriste (2004-05-30T09:50:05Z)

Et bien ces fourmis elles m'auront bien usé aussi ces derniers temps. J'ai finalement une solution, originellement probablement la même que celle de Hugues R. à base d'indice de Hopf, puis qui s'est laissé transformer en purement combinatoire. Allez je la poste à l'usage de votre maman. Remarque en passant : si vous passez gare de Waterloo obnubilé par un problème que vous n'arrivez pas à résoudre, aller s'asseoir quelques jours plus tard gare d'Austerlitz mène à la solution.

Remarque supplémentaire : après une nuit de sommeil, ça s'est encore simplifié ; je recommence donc et effacerai à la fin la version précédente.

C'est une preuve par l'absurde : je suppose qu'il y a une façon de faire tourner les fourmis sans collisions. Comme le fait remarquer Hugues R. dans un commentaire précédent, il n'est pas très difficile de voir qu'on peut supposer que chaque fourmi fait exactement un tour. Je suppose enfin que la période du mouvement des fourmis est 1. Je note selon l'usage f le nombre de faces, a le nombre d'arêtes, s le nombre de sommets du polyèdre. Accessoirement, on interdit aux fourmis de se reposer exactement aux sommets.

Pour chaque couple (A,S), avec S extrémité de l'arête A, je noterai :

t_1(A,S) le temps de parcours de A par la fourmi y pénétrant par le sommet S ;
t_2(A,S) le temps qui s'écoule entre le passage en S de la fourmi y arrivant par l'arête A et le passage en S de la fourmi quittant S par l'arête A ;
t_3(A,S) le temps qui s'écoule entre le passage en S de la fourmi y arrivant par l'arête A et le passage suivant d'une fourmi en S.

On va estimer de deux façons différentes le nombre Sigma, somme sur (A,S) des t_1(A,S)+t_2(A,S).

La première façon est de regrouper la somme en sommant d'abord les quatre nombres qui concernent une même A, puis en sommant toutes les A. La somme pour A fixé est égale à la somme du parcours de A dans un sens, puis de la première durée d'inoccupation de A, puis du parcours de A dans l'autre sens, puis de la deuxième durée d'inoccupation de A. Cette somme vaut donc 1. La somme sur tous les A vaut finalement a. Donc Sigma = a.

Dans une deuxième optique, on sépare Sigma en Sigma_1 (somme des t_1) et Sigma_2 (somme des t_2).
Regroupons les sommants de Sigma_1 par fourmi. Pour chaque fourmi, la somme des t_1 qui la concernent est le temps total qu'elle passe sur les arêtes du polyèdre : c'est donc 1. La valeur totale de Sigma_1 est donc le nombre de fourmis : Sigma_1=f.
Pour Sigma_2, on se contente d'une inégalité. On remarque que par définition, t_3(A,S) <= t_2(A,S). Donc Sigma_3 <= Sigma_2, en appelant Sigma_3 la somme des t_3. En regroupant les sommants de Sigma_3 par même S puis en sommant sur tous les sommets, on voit que Sigma_3 = s. Donc s <= Sigma_2. Donc f + s <= Sigma.

En synthétisant f + s <= a.

Or (Euler-Poincaré), f - a + s = 2. Contradiction !

phi (2004-05-15T15:56:54Z)

Hughes, merci!
j'avais des idées plutôt confuses et ce qui me gênait était qu'une fourmi puisse ressortir du cycle immédiatement mais c'est impossible sur une sphère.

Nepomucene (2004-05-14T10:18:07Z)

Au fait, si je puis me permettre une question, que pensent les personnes compétentes de ce que dit (l'ami de) Gao Xingjian?

Anonymous Coward #926 (Hugues R) (2004-05-14T07:08:02Z)

Pour phi:

Je ne suis pas sûr de comprendre ta question ; le graphe "instantané" dont je parle n'est pas un sous graphe du polyèdre, mais un sous-graphe du graphe dual (ses sommets sont les centres des faces). Ce graphe est construit de façon à contenir un cycle avec la propriété que toutes les fourmis qui le traversent se dirigent vers l'intérieur du secteur qu'il délimite. Ensuite, lorsque le temps avance, ce cycle se casse ; on peut même supposer qu'une seule arête est responsable de cette cassure ; alors, puisque les fourmis se dirigent vers l'intérieur du cycle, l'arête qui s'est déplacée l'a fait elle aussi vers l'intérieur ; ce faisant, elle aura créé un nouveau cycle qui se trouvera à l'intérieur du cycle précédent (à ce stade, il vaut mieux faire un dessin pour comprendre) ; et ce nouveau cycle aura encore la propriété que toutes les fourmis qui le croisent y entrent, sans qu'aucune n'en sorte. Ainsi un certain nombre de fourmis sont "piégées" dans des secteurs de plus en plus petits, et donc vont forcément devoir entrer en collision.

L'idée de base est que, si, par exemple, d'un certain sommet du polyèdre partent n arètes, et que les n fourmis des faces correspondantes se trouvent toutes sur ces arètes à un même moment et se dirigent vers ce sommet, alors forcément il y aura une collision (selon la description du paragraphe précédent, on peut dessiner un petit disque autour du sommet, et toutes les fourmis se dirigent vers l'intérieur de ce disque). C'est cela que la construction de Klyachko généralise.

Je ne pense pas pouvoir expliquer mieux, pour plus de détails je t'invite à consulter l'article klyachko.ps cité dans les commentaires de David et de Denis F. (très clair, il y a même des dessins pour illustrer !)

Ruxor (2004-05-13T23:21:02Z)

Suite à ce que je disais dans le précédent commentaire : on me signale que la valeur de d(n) pour tout n est connue. Précisément, si on appelle c+4d l'exposant de la plus grande puissance de 2 divisant n, alors d(n) vaut 2^c + 8d. C'est expliqué dans <URL: http://www.math.niu.edu/~rusin/known-math/99/vec_fields >.

Anonymous Coward #932 (Nepomucene) (2004-05-13T21:31:35Z)

Ce commentaire n'est pas forcément passionnant mais bon…

A propos de la beauté des mathématiques, j'ai lu dernièrement un petit livre de Gao Xingjian qui reprend son très intéressant discours de Stockholm et des entretiens un peu inégaux qu'il a eus avec Denis Bourgeois (dont j'ignore tout), et je suis tombé sur ces propos de G.X. qui m'ont immédiatement, à tort ou à raison, fait penser à David:

"Une fois, j'ai eu une discussion avec un ami, mathématicien, il m'a dit: On croit que les mathématiques, c'est ce qu'il y a de plus logique, de plus scientifique, en fait c'est une création de l'imagination, avec même un caractère esthétique".

phi (2004-05-13T19:33:16Z)

Hugues:
Sur la preuve de Klyachko, je suis d'accord, même, que les arêtes vont former des cycles ("instantanés") et le graphe dual permet de se rendre compte plus facilement, en essayant, de ce que les les arêtes ne peuvent pas être déplacées "continûment" (à chaque étape, l'arête avance sur le sommet adjacent suivant, ou bien reste immobile), mais jene vois pas comment appliquer la suite de l'explication pour conclure…

Anonymous Coward #931 (Jeff) (2004-05-13T18:22:53Z)

ok désolé :)

Ruxor (2004-05-13T18:16:17Z)

Jeff: Nous sommes d'accord que pour n=2 le maximum de la dimension est d=2. En fait, pour n valant 1, 2, 4 ou 8 le maximum est d=n, et ce sont les seuls n pour lesquels c'est le cas. Ce que je dis, c'est que pour n impair, le maximum est d=1 : en clair, si M et N sont deux matrices réelles n×n avec n impair, il existe forcément des coefficients a et b (réels) non tous les deux nuls tels que aM+bN ne soit pas inversible. Enfin, la remarque de l'« individu » prouve que pour n=2^k le maximum est *au moins* d=k.

Bref, si j'appelle d(n) la plus grande dimension possible d'un sous-espace vectoriel des matrices n×n à coefficients réels dont tous les éléments non nuls sont inversibles (en tant que matrices n×n), alors il résulte des diverses remarques qui ont été faites que : primo, d(n) est toujours compris entre 1 et n (ça c'est vraiment élémentaire), secundo d(n)=n si et seulement si n vaut 1, 2, 4 ou 8, tertio d(n)=1 si n est impair, quarto d(2^k)≥k (et en particulier, d(n) n'est pas bornée, ce qui était ma question initiale). Je peux rajouter que d(mn) vaut au moins le max de d(m) et d(n). Je ne sais pas ce que vaut d(6), par exemple, si ce n'est qu'il est compris entre 2 et 5 (et je soupçonne que c'est plutôt 2). Je peux rajouter que d(n) est une fonction théoriquement calculable (au sens usuel de Church-Turing) de n puisque la théorie du premier ordre du corps des réels est décidable (c'est la théorie des corps réel-clos, qui est complète).

Évidemment, on pourrait ensuite poser la question sur d'autres corps (c'est-à-dire pour des matrices à coefficients dans d'autres corps), par exemple les rationnels.

Anonymous Coward #931 (Jeff) (2004-05-13T18:06:15Z)

Ok je viens de me rendre compte que j'avais pas compris le pb, maintenant le but c'est de monter au dessus de n, en gros? :o)

Anonymous Coward #929 (Jeff) (2004-05-13T17:54:21Z)

Ruxor & le même individu> Heu je vais surement dire une connerie, mais dans les matrices 2x2, si on fait l'ensemble des matrices [[X, Y];[-Y, X]], qui forme bien un sous-espace vectoriel de M2,2, et dont les déterminants s'écrivent X^2+Y^2 (qui ne peut être nul que si X=Y=0) bien un ensemble de la forme voulue.
Comme ce sous-espace est de dimension 2, j'ai de gros doutes sur un maximum à 1 (à moins que j'aie mal compris vos commentaires?)
Sachant qu'on peut étendre ce résultat à n'importe quelles matrices nxn avec n pair en faisant des blocs 2x2 sus-mentionnés sur la diagonale (ce qui donne un sous espace de dimension n), je dirais qu'il n'y a pas de maximum.

J'ai dit une connerie?
Je n'en ai pas l'impression.

Anonymous Coward #928 (Grothendieck) (2004-05-13T16:08:42Z)

Elementaire. Multi-imbiter la n-Z scarface polycubique et lui appliquer l'application bi-dérivationnelle de collision fractale de l'opérateur merdouillant Zéta. Le reste est trivial et intuitif : le torscheur collisionnel du mytho-graph fictionnel de Levsourtschorty réduit à sa projection bi-diagonalique sur la matrice elle-même différantiante de Lishphephiyzsckyrscksi et s'apercevoir que son indice fusionnel en structure psychanalytique est aussi multi-imbitable.

Anonymous Coward #926 (Hugues R) (2004-05-13T12:37:58Z)

Pour le problème des fourmis ("Klyachko's car crash theorem" pour les intimes), l'énoncé original ne posait aucune condition d'intégralité sur le nombre de tours : on demandait juste que, le temps tendant vers l'infini, le nombre de tours parcourus par chaque fourmi soit aussi infini.

La preuve de Klyachko est en effet complètement élémentaire. A tout instant, considérons le graphe orienté dont les sommets sont les centres des faces, et dans lequel une arète joint le sommet correspondant à la face i à celui correspondant à la face j lorsque la fourmi de la face i se trouve à la frontière de la face j. Ainsi, dans ce graphe dual instantané, de chaque sommet part une et une seule arète, et puisque ce graphe est fini, certaines de ces arètes vont former un chemin fermé. Par construction, les fourmis se dirigent alors vers l'intérieur du secteur délimité par ce chemin fermé, de sorte qu'en faisant avancer le temps, lorsqu'une des fourmis passera un sommet, ce chemin fermé se cassera pour reconstruire un chemin délimitant un secteur plus petit, ce qui ne peut durer infiniment.

La preuve que j'avais trouvée se plaçait, elle, dans un cas très particulier, celui où les fourmis font toutes exactement un tour dans un même intervalle de temps donné (ou, ce qui revient au même, en supposant que les trajectoires des fourmis sont périodiques, de même période fondamentale). L'esprit en relève plus de la topologie algébrique. Ca va faire un mois que je m'étais promis (et que j'avais promis à d'autres) de la rédiger proprement, mais je ne l'ai toujours pas fait -- je suis certainement encore pire que David pour ce genre de choses ; j'espère que le fait de faire ce genre de déclarations publiques va finir par m'obliger à m'exécuter.

denis f (2004-05-13T03:37:13Z)

Je viens de lire la démo à <URL: http://www.maths.warwick.ac.uk/~cpr/ftp/klyachko.ps > (oui, il est 5h, Paris s'éveille, tout ça) et je confirme : c'est élémentaire. Mais tu va quand même avoir un peu de mal à l'expliquer à ta maman…L'idée essentielle, c'est d'introduire le graphe de collision (le sous-graphe du dual du complexe, joignant les centres des faces aux fourmis), et de montrer qu'en fonction du temps, certaines cellules de ce graphe se contractent…

Ruxor (2004-05-13T02:46:39Z)

jko: Dis carrément que je radote. :-)

Hagen: Non, la démonstration de l'histoire des fourmis est assez longue même avec le théorème de l'indice comme théorème-massue, et je ne l'ai lue qu'en diagonale. Tu peux demander à Hugues Randriambololona (c'est lui qui l'avait trouvée ; son adresse doit se trouver sans trop de mal en Googlifiant) s'il peut t'en envoyer une copie. Sinon, il paraît qu'il y a une démonstration censément élémentaire sur <URL: http://www.maths.warwick.ac.uk/~cpr/ftp/klyachko.ps >, mais je n'ai pas encore trouvé le temps de la lire.

phi: Oui, j'ai cherché selon cette ligne-là, entre autres idées, mais je n'ai jamais trouvé une façon de faire fusionner deux faces.

le meme individu: En effet, pour n impair quelconque, le majorant est 1 puisque le déterminant détermine une forme homogène de degré n sur l'espace vectoriel de dimension d, et une telle forme a forcément un zéro réel non trivial.

Je vais peut-être poser la question sur sci.math.research, voir s'il y a des gens qui ont des choses intéressantes à dire.

Anonymous Coward #923 (le meme individu) (2004-05-13T00:05:21Z)

non on peut pas atteindre n !
pour n=3 la dimension maximale est 1 (a verifier)

phi (2004-05-12T22:40:33Z)

dans l'idée d'une solution maman-acceptable j'ai pensé à un raisonnement par récurrence (la raison inavouable est que c en gros la seule méthode à ma portée). Avec 2 faces, c'est évidemment impossible. Supposant qu'on a une solution avec n faces et p arêtes, n p minimaux, on pourrait engendrer une solution pour n-1 faces en fusionnant deux d'entre elles ou en en supprimant une. Si les faces n'ont pas plus de 4 côtés, il y a au plus 2 fois plus d'arêtes et il semble (du moins sur le cube) qu'il y ait deux faces dont les fourmis (alors sur deux arêtes contigües) ont "failli" se croiser. Il semble vraisemblable qu'on puisse fusionner ces deux faces et raccorder les trajectoires des deux fourmis. Si on a des faces avec beaucoup de côtés, et qu'à aucun moment les fourmis n'ont failli se croiser, on pourrait peut-être supprimer une arête en fusionnant deux sommets.
Bof, c'est au mieux des maths-fiction…

Anonymous Coward #922 (Hagen) (2004-05-12T20:33:51Z)

Et pour l'histoire de la fourmi sur le polyèdre, c'est quoi la solution avec le théorème de l'indice ?

Anonymous Coward #921 (2004-05-12T18:16:15Z)

Un indice: le carré de l'hypoténuse. Ca devrait suffire au plus forts

Anonymous Coward #920 (2004-05-12T17:27:50Z)

bon en fait c'est trop compliqué pour moi, ça me rassure en un sens …

jko (2004-05-12T17:06:23Z)

Ces mots sonnent dans mes oreilles comme un air déjà entendu, comme plusieurs entrées précédentes ;)

Anonymous Coward #920 (2004-05-12T16:53:46Z)

Oups j'ai compris ma boulette ;-)
bon alors le majorant est clairement n, peut-on l'atteindre? j'y réfléchis les enfants…

Anonymous Coward #919 (2004-05-12T16:27:53Z)

ce que je dirais:
- si on prend toutes les matrices dont la première ligne est nulle, on obtient un espace constitué exclusivement de matrices singulières, et de dimension n^2-n: on a donc déjà un majorant pour la dimension considérée, qui est n.
- si on prend la matrice compagnon A d'un polynôme unitaire de degré n, et l'espace vectoriel engendré par (I,A,…A^(n-1)), on obtient bien un espace de dimension n qui a la bonne propriété, non?
j'avoue que ça fait longtemps que j'ai pas fait d'algèbre linéaire, donc j'ai peut-être dit une connerie (ou plus)…
Ca paraît un peu trop simple pour faire sécher l'élite de la nation ;-)

Matoo (2004-05-12T16:18:17Z)

Au s'couuuuuuuuuuuuuurs Père Doduuuuuuue !

Anonymous Coward #918 (2004-05-12T15:55:40Z)

Hé ben c'est pas comme ça qu'on va conserver la médaille fields

Ruxor (2004-05-12T15:52:18Z)

un individu: Merci pour cette très jolie solution. Je n'aurais jamais pensé aux algèbres de Clifford (je n'ai jamais réussi à m'en faire une intuition valable). En tout cas, c'est le genre de construction qui me rassure quant à la beauté des maths (j'aurais été un peu fâché qu'on ne pût pas dépasser la dimension 8).

Ensuite, on peut évidemment se demander pour quels d et n on arrive à construire un espace vectoriel de dimension d dans les matrices n×n tel que seule la matrice nulle ne soit pas inversible. La construction de l'algèbre de Clifford montre que pour n=2^d ça marche, et par ailleurs la remarque faite par Laurent montre que pour n=d ça ne marche que pour d dans {1,2,4,8}. Ceci dit, je suis nettement moins intéressé par cette question raffinée.

Anonymous Coward #917 (un individu) (2004-05-12T13:21:28Z)

Considerons un espace quadratique anisotrope (V,q) de
dimension quelconque sur les reels R. Comme (V,q) est
anisotrope, les elements de V (a part 0)
sont inversibles dans l'algebre de Clifford C(V,q)
ceci dit la dimension en question peut etre arbitraire.

Ruxor (2004-05-12T12:07:13Z)

laurent: Ouais, je m'étais effectivement posé la question du lien avec la parallélisabilité de la sphère, en voyant que mes tentatives les plus naïves pour construire la chose cherchaient systématiquement dans des matrices de similitudes (orthonormales fois homothétie, je veux dire), et qu'en Gram-Schmidtisant ou quelque chose comme ça, on pouvait se ramener à ça de toute façon, si d=n. Mais ensuite je ne vois pas de raison pour laquelle les choses ne marcheraient pas mieux avec n>>d (la topologie seule ne suffit pas, le fibré tangent d'une sphère devenant trivial dès qu'on y rajoute un fibré trivial comme le normal du plongement dans une plus grande sphère), et je n'ai pas vu d'argument d'algèbre linéaire pour se ramener à d=n. Je ne connais pas assez de théorie de la représentation, d'autre part, pour savoir si ça permet d'approcher ce genre de questions.

Anonymous Coward #891 (laurent) (2004-05-12T08:38:55Z)

C'est marrant comme question. Bon mettons que ton espace V est de dimension d et composé de matrices n x n. On a d inferieur ou égal à n et on peut peut etre se ramener à d=n? Dans ce cas considérons l'application c_i de V dans R^n qui à M associe la i-ème colonne de M. Les applications c_1 … c_n sont n champs de vecteurs linéairement indépendants sur V\{0}. Ceci dit grosso modo que le fibré tangent de ce truc est parallélisable et il me semble que cela ne se produit que pour n = 2,4 ou 8.

Anonymous Coward #914 (2004-05-12T05:03:56Z)

J'ai bien une solution mais la case de la réponse est trop petite pour la contenir.

Anonymous Coward #912 (Houlala) (2004-05-12T00:39:13Z)

A qui fais tu allusion Ruxor?


You can post a comment using the following fields:
Name or nick (mandatory):
Web site URL (optional):
Email address (optional, will not appear):
Identifier phrase (optional, see below):
Attempt to remember the values above?
The comment itself (mandatory):

Optional message for moderator (hidden to others):

Spam protection: please enter below the following signs in reverse order: 4bbea2


Recent comments