14 septembre 2014

Artur Avila, celui qui mélange

Dans le dernier épisode, j'avais entrepris d'écrire de petits articles pour décrire les travaux de la dernière fournée des médaillés Fields. Dès le premier article sur Manjul Bhargava, j'ai échoué, puisque l'article était trop long. Je vais tenter de me rattraper, en parlant aujourd'hui du plus brésilien de tous les médaillés Fields français (puisque c'est le seul qui soit franco-brésilien) : Artur Avila !

RTEmagicC_Artur_Avila
Artur Ávila Cordeiro de Melo

Artur Ávila est né le 29 juin 1979 à Rio de Janeiro, si bien qu'il a été médaillé Fields à moins de 36 ans (ce qui est plutôt rare). En même temps, vu qu'il a démarré sa thèse à 19 ans, il est normal qu'il obtienne la médaille Fields plus tôt que les autres. Cette médaille, il l'a remporté grâce à 

"ses profondes contributions à la théorie des systèmes dynamiques qui ont bouleversé le domaine, en utilisant la puissante idée de renormalisation comme principe unificateur"

Suite logistique
Ce qui intéresse Artur Avila, c'est de comprendre le comportement des systèmes dynamiques : le mouvement des planètes, la dynamique des populations, le mouvement des électrons... Ce qui caractérise un système dynamique, c'est que leur évolution est parfaitement déterministe : la connaissance exacte des conditions initiales permet toujours de savoir leur avenir. Mais si on ne connaît que vaguement les conditions initiales, la prédiction du futur du système est souvent compromise. Mais ce n'est pas une fatalité ! Commençons déjà par étudier le plus célèbre des systèmes dynamiques, issu d'une modélisation de la croissance de populations : la suite logistique.

Pour un nombre réel r∈ ]0,4], on définit la fonction logistique f:x ↦ r.x.(1-x). 
Puis, étant donné un nombre u0  ]0,1[, on va observer le comportement de la suite (un) définie par un+1 = f(un).

Malgré son apparence très simple, cette suite peut avoir des comportements très bizarres pour certaines valeurs de r et de u0.

Prenons un premier exemple, avec r = 2.8 et u0 = 0.2. Dans ce cas, la suite logistique est la suivante :
u0 = 0.2, u1 = f(u0) = 0.448, u2 = f(u1) = 0.692..., u3 = 0.596..., u4 = 0.674..., u5 = 0.615..., u6 = 0.662...
En itérant davantage, on constate que la suite finit par se stabiliser autour de 0.6428 (9/14). La suite converge !

On peut observer le comportement de ces suites à l'aide de ce que l'on appelle les diagrammes en "toile d'araignée" (ou diagrammes de Vershult). Pour cela, on dessine la fonction que l'on va itérer (ici, f), ainsi que la droite d'équation y=x, et on place le terme initial u0 sur l'axe horizontal. On va ensuite placer le point u1 en reliant verticalement u0 à la courbe de f, puis horizontalement la courbe f à la droite y=x. En répétant l'opération, on fabriquera la "toile d'araignée" qui représentera les différents termes de la suite.
La convergence d'une suite se traduit sur ce diagramme par la convergence des zig-zag.

Logistic_28 (2)
Diagramme en toile d'araignée de la suite logistique, pour r = 2.8 et u0 = 0.2
Les 500 premiers termes de (un) sont représentés (même si 99% d'entre eux sont concentrés autour de 9/14)

En fait, le choix du terme initial u0 n'a aucune incidence sur le devenir de cette suite de paramètre r=2.8 : elle finira toujours par converger vers 9/14.

Mais pour les autres valeurs de r ? Eh bien, ça dépend...

Déjà, il y a les valeurs r comprises entre 0 et 3 : c'est toujours la même chose qui se passe, la suite converge :

logistique_13logistique_2logistique_23
logistique_26logistique_295logistique_3
Pour r ∈ ]0,3], la suite converge, quelle que soit la valeur initiale u0.
Pour r=3, la convergence vers 2/3 est cependant particulièrement lente.

Mais pour les valeurs plus grandes que r=3, les choses se corsent. D'abord, gentiment, lorsque r est compris entre 3 et 3.449 : la suite ne se stabilise pas autour de une seule valeur, mais autour de 2 :

logistique_310logistique_320logistique_330logistique_342
Diagramme pour r=3.1, r=3.2, r=3.3 et r=3.42
Pour r ∈ ]3,1+√6], la suite se stabilise autour de 2 valeurs, quelle que soit (sauf exception) la valeur initiale u0.

Pour des valeurs encore plus grande de r, ça se complique davantage : la suite se stabilisera autour de 4 valeurs (r ∈]3.449, 3.544]), puis autour de 8 valeurs (r∈]3.544;3.564]), puis autour de 16 valeurs, etc., et ce, tant que r ≤ 3.57.

logistique_350logistique_356logistique_3565
Diagramme pour r=3.5, r=3.56, r=3.565
Pour ces valeurs r ≤ 3.57, la suite finira par se stabiliser autour de 2n valeurs

Mais pour les valeurs plus grandes que 3.57, le chaos arrive ! Il n'y a plus aucune valeur autour desquelles la suite va se stabiliser. De plus, si on change même très légèrement la valeur initiale u0, la trajectoire sera complètement différente. On peut alors dire que la suite a un comportement chaotique. Encore une fois, ce chaos est indépendant de la valeur initiale (sauf exceptions)

logistique_370logistique_380logistique_390logistique_400
Diagramme pour r=3.7, r=3.8, r=3.9 et r=4
Pour ces valeurs r ∈ [3.57;4], la suite est chaotique : elle ne se stabilisera autour d'aucune valeur

En fait, ceci n'est pas totalement vrai. A partir de r=3.57, on peut trouver parfois des valeurs r pour lesquelles la suite se stabilisera autour de 3 valeurs, autour de 6 valeurs, ou autour de n'importe quel nombre de valeurs choisies à l'avance. Par exemple, pour r=3.83, la suite se stabilise autour de 3 valeurs :

logistique_383
Diagramme pour r=3.83 : la suite se stabilise autour de 3 valeurs.

On peut résumer le comportement de la suite logistique par son diagramme de bifurcation : en abscisse, le paramètre r, et en ordonnée, ses valeurs d'adhérence :

800px-LogisticMap_BifurcationDiagram

Finalement, la suite peut présenter deux comportements, suivant la valeur r :
- ou bien elle est régulière : elle finit par se stabiliser autour d'une ou de plusieurs valeurs
- ou bien elle est chaotique

Dans le cas où la suite est chaotique, elle n'est cependant pas si imprévisible qu'on voudrait bien le croire. Même si on ne peut pas connaître la valeur de la suite après un grand nombre de valeurs, on peut tout de même prédire avec une certaine probabilité dans quel intervalle elle se trouvera. Par exemple, on peut vérifier que dans le cas r = 0.9, la suite passera plus de 20% de son temps dans l'intervalle [0.9;1], ou qu'elle sera deux fois plus souvent autour de 0.35 qu'autour de 0.7. Et ça, indépendemment du choix de u0 (sauf, comme toujours, cas particuliers). 
Autrement dit, quand on connaît la valeur r, on peut connaître la répartition des valeurs prises par la suite. Le système dynamique se comporte alors comme un objet aléatoire : on dit alors que la suite stochastiquement stable.

Existe-t-il des valeurs r pour laquelle la suite serait ni régulière, ni stochastiquement stable ? ... Eh bien, oui, mais ces exemples sont négligeables (les cycles attracteurs peuvent par exemple être des ensembles de Cantor...). C'est l'objet du théorème de Lyubich (2002), qui indique que presque toutes les suites logistiques sont régulières ou stochastiquement stable.

Mais ça, c'était juste pour le cas très particulier des suites logistiques. Qu'en est-il de tous les autres systèmes dynamiques ? Eh bien, c'est ça l'objet du travail de Artur Avila : il a démontré, avec Lyubich et Melo, que la plupart des systèmes dynamiques observent cette dualité régulier/stochastiquement stable !

Les échanges d'intervalles
Un autre problème qui a longtemps empêché Avila de dormir est celui du mélange des jeux de cartes (bon, avec un nombre infini et continu de cartes, mais l'idée est là).

Par exemple, pour mélanger un jeu de 32 cartes, on peut répéter plusieurs fois l'opération suivante : faire 4 tas de cartes A, B, C, D, puis les réassembler en mélangeant l'ordre des tas (par exemple, D, A, C, B). Quand on parle de système dynamique, il est nécessaire que l'opération soit toujours identique.

Disons que les tas A, B, C et D contiennent respectivement 7, 7, 7, et 11 cartes. En numérotant les cartes de 1 à 32, on a le découpage suivant :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

En permutant ces 4 tas selon le motif DACB, on obtient :

22 23 24 25 26 27 28 29 30 31 32 1 2 3 4 5 6 7 15 16 17 18 19 20 21 8 9 10 11 12 13 14

Et si on répète encore la même opération :

18 19 20 21 8 9 10 11 12 13 14 22 23 24 25 26 27 28 4 5 6 7 15 16 17 29 30 31 32 1 2 3
7 15 16 17 29 30 31 32 1 2 3 18 19 20 21 8 9 10 25 26 27 28 4 5 6 11 12 13 14 22 23 24
28 4 5 6 11 12 13 14 22 23 24 7 15 16 17 29 30 31 21 8 9 10 25 26 27 32 1 2 3 18 19 20
10 25 26 27 32 1 2 3 18 19 20 28 4 5 6 11 12 13 17 29 30 31 21 8 9 14 22 23 24 7 15 16
31 21 8 9 14 22 23 24 7 15 16 10 25 26 27 32 1 2 6 11 12 13 17 29 30 3 18 19 20 28 4 5
13 17 29 30 3 18 19 20 28 4 5 31 21 8 9 14 22 23 27 32 1 2 6 11 12 24 7 15 16 10 25 26
2 6 11 12 24 7 15 16 10 25 26 13 17 29 30 3 18 19 9 14 22 23 27 32 1 20 28 4 5 31 21 8
23 27 32 1 20 28 4 5 31 21 8 2 6 11 12 24 7 15 30 3 18 19 9 14 22 16 10 25 26 13 17 29

Après 10 répétitions, le jeu est plutôt mélangé, et c'est parfait pour une bataille ! 
Après un grand nombre n d'opérations, on dira que le jeu est mélangé si, dans n'importe quel petit groupe de carte, la proportion de carte d'un groupe donné est la même que dans le jeu complet.
Autrement dit, un jeu de carte est bien mélangé si, dans une main, on a toujours environ 50% de cartes rouges, 25 % de piques, 12.5% de carte as ou roi...

Il y a quand même un problème avec le mélange d'un jeu de 32 cartes, c'est qu'après un certain nombre de répétitions, on reviendra forcément à un jeu parfaitement trié. En effet, puisque chaque répétition donne une nouvelle permutation des 32 cartes, et qu'il n'existe *que* 32! (=32×31×30×...×1 = 3.2×1035) permutations différentes, on retombera tôt ou tard sur le jeu trié.
Cela signifie qu'il existe des grands nombres d'itérations n pour lesquelles le jeu n'est pas mélangé...

Cependant, un tel mélange par permutation peut facilement se généraliser à des intervalles :

MelangeIntervalles
Permutation DACB, itérée deux fois

On peut se poser la même question : est-ce que cette permutation est mélangeante ?
Si oui, cela signifierait que, après plusieurs itérations, la première moitié (ou n'importe quel sous-ensemble) de l'intervalle contiendrait exactement la même proportion de rouge (et des autres couleurs) que dans l'intervalle initial. Une telle perfection de mélange est impossible à obtenir, mais on peut l'exprimer en terme de limite : la limite de la proportion de rouge dans la première moitié de l'intervalle doit tendre vers la proportion initiale de rouge.
Malheureusement, une permutation mélangeante, ça n'existe pas, et c'est à Anatole Katok que l'on doit se résultat. Mais ce que Avila a montré, avec Giovanni Forni, c'est que la plupart des permutations d'intervalles sont faiblement mélangeantes : elles sont mélangentes à condition d'exclure un "petit" nombre de valeurs de n.

Ce résultat sur les intervalles peut s'appliquer sur les billards de forme quelconque, ce qui fournit de précieux résultats dans l'étude des mouvements des particules en physique statistique.

Le problème des 10 Martinis
Il existe des problèmes mathématiques côtés à un million de dollars (les fameux problèmes du prix du millénaire, comme l'hypothèse de Riemann ou le problème P=NP). Et il y en existe pour qui la récompense est à première vue moindre, comme le problème des dix martinis. Comme son nom l'indique, dix martinis seraient offerts en échange de la résolution du problème ; une proposition du mathématicien Mark Kac (proposer une ou plusieurs boissons alcoolisées en échange de la résolution d'un problème étant l'une des coutumes des mathématiciens de l'école de Lwów, en Pologne). A noter qu'il existe une variante plus "sèche" de ce problème, appelé problème des dix dry martini... Le problème des 10 martinis est donc le suivant :

Montrer que, pour tout λ ≠ 0, et pour tout α irrationnel, le spectre de l'opérateur presque-Mathieu OperateurMathieu
est un ensemble de Cantor

J'ai retranscrit l'énoncé pour la forme, je ne vais pas le détailler davantage. La seule chose qu'il faut dire, c'est que l'opérateur presque-Mathieu décrit l'évolution d'un électron dans un champ magnétique particulier. Il ne fait nul doute que les physiciens apprécient de connaître le spectre d'un tel opérateur. 

Artur Avila, ainsi que Raphaël Krikorian, Svetlana Jitomirskaya et David Damanik ont résolu ce problème des 10 martinis, ainsi que d'autres problèmes issus de la liste des problèmes de Simon, 15 problèmes issus de la théorie des opérateurs de Schrödinger à destination des mathématiciens du XXIe sicèle. L'histoire ne dit pas si ils ont gagné leur dix verres de vermouth.

L'opérateur presque-Mathieu est lié au papillon de Hofstadter, qui, avant d'écrire des livres (Godel, Escher, Bach), s'intéressait à la physique. Cette fractale issue de la physique représente la conductance de Hall (?) en fonction de l'énergie (??) et du flux magnétique (???). Autant dire que je n'ai pas compris exactement ce qu'est le papillon de Hofstadter, mais comme c'est joli, je ne vais pas me priver de le mettre ici pour conclure cet article...

Hofstadter's_butterfly
Le papillon de Hofstadter
Je devrais un jour faire un top 10 des utilisations du papillon en mathématiques...


Sources
The work of Artur Avila
La suite logistique et le chaos, Daniel Perrin
Weak mixing for interval exchange transformations and translation flows, Artur Avila et Giovanni Forni

 

Posté par El Jj à 10:00 - Commentaires [1] - Permalien [#]
Tags : , , , ,


31 août 2014

Manjul Bhargava, celui qui compte

Quand on part en vacances, on se coupe des informations. Parfois par choix, parfois simplement parce que le wifi du camping n'est pas tout à fait fonctionnel. Et quand on rentre de vacances, on découvre que l'on est passé à côté du décès de Robin Williams et de la révélation des nouveaux médaillés Fields. Du coup, je ne sais pas comment les médias ont traité l'hommage au professeur John Keating, à Sean Maguire ou à Alan Parish, ni comment ils sont parvenus à saboter l'événement de l'année de la communauté mathématique.

Rappellons-le : la médaille Fields, c'est comme le prix Nobel, mais pour les mathématiques. Mais elles ne sont remies que tous les quatre ans, contrairement au prix Nobel. C'est donc plutôt les JO des mathématiques. Mais ça n'a rien à voir, d'autant que les Olympiades de mathématiques existentt, et qu'elles ont lieu tous les ans. Mais chaque année, 4 mathématiciens sont récompensés par la médaille Fields, ce qui fait une moyenne de une médaille Fields par an, ce qui est équivalent au prix Nobel. Mais la médaille Fields limite ses récipiendaires à 40 ans, ce qui n'a rien à voir avec le Nobel. Du coup, on n'a qu'à dire que le Nobel des mathématiques est le prix Abel, et que la médaille Fields est la médailles Fields des mathématiques, puisqu'ils ne font jamais rien comme tout le monde.

En cette année 2014, les quatre mathématiciens qui ont reçu la fameuse médaille sont :
- Artur Ávila, franco-brésilien
- Manjul Bhargava, américano-canadien, d'origine indienne
- Maryam Mirzakhani, iranienne, professeur aux USA
- Martin Hairer, autrichien, professeur au Royaume-Uni

Trois choses sont alors à remarquer :
- il faut arrêter de donner la nationalité des mathématiciens, puisqu'ils font vraiment tout pour compliquer les choses
- je n'ai pas encore parlé des lauréats du prix Nevanlinna, du prix Gauss, du prix Leelavati ni de la médaille Chern, remis en même temps que les médailles Fields, mais j'en parlerai (peut-être) dans un futur article
- heureusement qu'une femme et qu'un français ont été médaillés, sinon, on aurait vraiment rien eu à dire

Mais qu'on fait ces 4 mathématiciens pour mériter une médaille ? Commençons aujourd'hui en nous penchant sur les travaux de Manjul Bhargava.

RTEmagicC_ManjulBhargava_FieldsMedal
मंजुल भार्गव

Pour situer, Manjul Bhargava est né le 8 août 1974 à Hamilton, au Canada, si bien qu'il avait plus de 40 ans lorsqu'il a reçu la médaille Fields (mais le règlement stipule(rait) qu'il faut être âgé de moins de 40 ans au 1er janvier de l'année du congrès). Il obtient son doctorat en 2001 à Princeton (USA), sous la direction de Andrew Wiles, célèbre pour avoir démontré le grand théorème de Fermat (mais comme il a finalisé sa démonstration à 41 ans, il est passé à côté de la médailles Fields...). Il a donc été récompensé :

"pour avoir développé des nouvelles méthodes en géométrie des nombres, lesquelles ont été utilisées pour compter les anneaux de petits rangs, ainsi que pour avoir borné le rang moyen des courbes elliptiques"

... en géométrie des nombres...
La géométrie des nombres consiste à résoudre de façon géométrique des problèmes issus de théorie des nombres (la théorie des nombres est le domaine où l'on cherche les solutions entières ou rationnelles (les fractions) d'équations).
Par exemple, on peut chercher quels sont les entiers x et y qui vérifient x² + y² = 13. La façon la plus simple de le faire est de dessiner dans un repère le cercle de centre (0,0) et de rayon √13 (autrement dit, le cercle d'équation x²+y²=13), et de regarder où il coupe le quadrillage. Un coup d'oeil rapide permet de vérifier que l'équation possède 8 solutions entières.

EquationCercle
Géométriquement, on voit que l'équation x²+y² = 13 possède 8 solutions entières.

On peut également poser la question du nombre de solutions (entières) de l'inéquation x² + y² ≤ 13. Cette fois-ci, il faut compter le nombre de points à l'intérieur du disque de centre (0,0) et de rayon √13.

InequationCercle
Géométriquement, on voit que l'équation x²+y² ≤ 13 possède 45 solutions.

En généralisant la construction, on peut voir que si le nombre C est assez grand, l'équation x² + y² ≤ C aura environ π.C solutions entières. En effet, l'équation x² + y² ≤ C correspond à un disque de rayon √C, donc d'aire π.C. Chaque noeud du quadrillage correspond à un carré d'aire 1, qui recouvre à peu près le disque, ce qui nous donne une approximation pas trop mauvaise.

InequationCercleGeneralise
Le cercle d'équation x² + y² ≤ C est d'aire π.C, il contient donc environ π.C noeuds du quadrillages

Autrement dit, une considération géométrique sur l'aire d'un disque nous apporte une réponse à une question de thoérie des nombres. C'est ça, la géométrie des nombres, et c'est pour ça que c'est cool.

... de nouvelles méthodes...
Le principal fait d'arme de Bhargava, c'est d'avoir découvert de nouvelles lois de compositions pour des polynômes. Cette découverte s'est faite en trois étapes :
- il a lu attentivement Disquisitiones arithmeticae, de Carl Friedrich Gauss, où il est entre autre question de composition de formes quadratiques
- il a joué avec un Rubik's Cube 2x2x2, ce qui lui a fait penser que le cube serait parfait pour illustrer le problème de la composition de formes quadratiques (sérendipité !)
- il a réfléchi longuement, et a abouti à la découverte de 13 nouvelles lois de compositions (là où Gauss en a péniblement décrit une).

Gauss s'est donc intéressé aux formes quadratiques binaires, autrement dit, aux polynômes à deux variables où tous les monômes sont de degré total 2. Bref, aux polynômes de la forme :

Q(x,y) = a x² + b xy + c y²
avec a, b, c entiers

On apprend au lycée qu'il existe trois types de trinômes du second degré : ceux qui possèdent deux racines, ceux qui n'en possèdent qu'une seule, et ceux qui n'en ont aucune. Pour savoir à quel type de trinôme on a affaire, on calcule son discriminant :

Δ = b² − 4ac

Lorsque Δ est négatif, le trinôme n'a pas de racine, et c'est là que c'est intéressant. Pour les formes quadratiques binaires, c'est pareil, elles ne sont intéressantes que lorsque Δ est négatif. Et si, en plus, les coefficients a et c sont positifs, on leur donne un nom : les formes quadratiques définies positives.

Une question qui taraude Gauss est de savoir combien il existe de formes quadratiques binaires définies positives (que je vais abrégéer en écrivant simplement "forme", parce que c'est pénible à écrire) différentes ayant un discriminant -Δ donné. Par exemple, quels sont les formes de discriminant -4 ?
Déjà, il y a Q(x,y) = x² + y².
Mais il y a aussi Q'(x,y) = x² + 2xy + 2y²
Ou alors il y a Q''(x,y) = 65 x² + 94 xy + 34 y²
En fait, n'importe quelle forme Q(rx+sy,tx+uy) (avec r,s,t,u entiers tel que ru-st=1) a le même discriminant que Q, ce qui donne une infinité d'exemples possibles 
Du coup, tous ces exemples de formes ne sont pas réellement différents. Ils constituent alors une même classe d'équivalence, à un changement de variable près. Mais y en a-t-il d'autres ? Pour Δ=-4, non, mais ce n'est pas le cas pour d'autres valeurs de Δ.

La question qu'il faut donc se poser est donc plutôt : combien existe-t-il de classes différentes de formes quadratiques, pour un discriminant -Δ donné ? C'est avec des outils de la géométrie des nombres que l'on peut répondre, au moins de manière approximative, à cette question.

Une autre question qui taraudait Gauss était celle de la structure de ces formes quadratiques : y a t-il un opération (une composition) que l'on peut faire entre deux formes qui donnerait une autre forme ? Il y a des façons naïves de le faire (en additionnant deux formes, on trouve une autre forme), mais celles-ci ne préservent pas le coeur de la forme quadratique : son déterminant. Et c'est là que le génie de Gauss, et plus tard, celui de Bhargava, opèrent !

Pour cela, Gauss s'appuie sur un fait bien connu : quand on multiplie deux sommes de deux carrés (x²+y²), on obtient une somme de deux carrés. Par exemple, le produit de 13 (=2²+3²) et de 25 (=3²+4²) est 325 (=6²+17²), tous trois sommes de deux carrés.
Ceci vient du fait que, pour tout nombres x, y, x', y', on a l'identité (x²+y²)(x'²+y'²) = (xx'-yy')² + (xy'+yx')² (on peut l'illustrer en remarquant que le module d'un produit de deux nombres complexes est égal au produit des modules).
Ainsi, en combinant la forme Q(x,y)=x²+y² avec elle-même, on trouve à nouveau cette forme : d'une certaine façon, on peut dire que Q×Q=Q.

On peut voir sur un autre exemple. Il existe seulement deux formes (à équivalence près) de déterminant -12 :
Q1 = x² + 3y² et Q2 = 2x² + 2xy + 2y²

On peut alors vérifier que l'on a les identités suivantes :
Q1(x,y)×Q1(x',y') = Q1(xx'-3yy',xy'+x'y) 
Q1(x,y)×Q2(x',y') = Q2(xx'-x'y-2yy',xy'+2x'y+yy') 
Q2(x,y)×Q2(x',y') = Q2(xx'-xy'+2yx'+yy',xx'+xy'+yy') 

Autrement dit : Q1×Q1 = Q1, Q1×Q2 = Q2 et Q2×Q2 = Q1 ! C'est ce que l'on appelle la composition des formes quadratiques, et on peut trouver des formules similaires liant entre eux toutes les différentes forme d'un même déterminant donné. Ces identités sont plutôt obscures, et il fallait au moins le génie de Gauss pour découvrir leur existence. 

Mais là où Bhargava intervient, c'est qu'en reprenant et en améliorant les méthodes de Gauss, il est parvenu à généraliser la composition des formes quadratiques à des polynômes de degré supérieur. Du coup, il a fait passer de 1 à 14 le nombre de lois de compositions connues pour les polynômes, cassant au passage l'idée que de telles identités ne pouvait exister que dans le cas des formes quadratiques.

Outre la satisfaction d'avoir plein de nouvelles identités pour les polynômes de degré 2 ou plus, toutes ces constructions sont utiles pour étudier les corps de nombres, objet central en algèbre.
Un corps, c'est un ensemble dans lequel on peut faire sans problèmes les quatre opérations de base : addition, soustraction, multiplication et division. On peut citer, par exemple, le corps des nombres rationnels ℚ, ou celui des nombres réels ℝ.

Ce que l'on aime bien faire avec les corps, c'est y ajouter des nombres pour voir ce que cela donne (on parle d'extensions de corps). Par exemple, on peut prendre le corps des nombres réels ℝ, et y ajouter un nombre qui serait la racine du polynôme X²+1. Si on appelle cette racine i, on obtient des nombres de la forme a+ib, où i²=-1, autrement dit, le corps des nombres complexes. C'est un corps quadratique de discriminant -4, puisqu'il a été construit à partir du polynôme X²+1.
Ce qui serait génial de savoir, c'est le nombre d'extensions de corps qui existent pour un déterminant donné (plus le déterminant est grand, plus le corps sera complexe). Grâce à Bhargava et à ses lois de compositions des polynômes, c'est chose faite !

(Mine de rien, la théorie des corps est centrale en algèbre, et c'est quand elle a été mise au point que l'on a pu résoudre sans difficulté les 3 grands problèmes de l'antiquité)

...avoir borné le rang moyen des courbes elliptiques...
Deuxième prouesse de Manjul Bhargava (avec Arul Shankar) : avoir borné le rang moyen des courbes elliptiques. Evidemment, rien n'aurait été possible sans tous les outils qu'il venait de mettre au point. Par ce théorème qui a fait sa renommé, Bhargava et Shankar ont fait un pas de plus vers la résolution de la conjecture de Birch et Swinnerton-Dyer, l'un des 7 problèmes du millénaire.

Une équation elliptique, c'est une équation de la forme :

y² + a1 xy + a2y = x3 +a3 x² +a4 x + a5
où a1a2a3a4a5 sont des nombres rationnels

Par exemple, les deux equations suivantes sont elliptiques :

y² = x3 +1

y² + y = x3 - x

Encore une fois, le but est de trouver des solutions rationnelles pour ces équations, et surtout, dire combien il y en a : un nombre infini ou pas ?
Dans le cas de l'équation y² = x3 +1, il n'y a que 5 solutions : (-1,0), (0,1), (0,-1), (2,3) et (-2,3)
Dans le cas de l'équation y² + y = x3 - x, il y a une infinité de solutions : (0,0), (1,-1), (1,0), (-1,0), (-1,-1), (2,2), (2,-3), (6,-15), (0.25, -0.375), ...

Mais pourquoi certaines équations elliptiques ont un nombre fini de solutions, et d'autres un nombre infini ? C'est injuste ! Pour cela, on va voir comment déterminer ces solutions, et on va le faire de façon graphique, puisque à chaque équation elliptique correspond sa courbe elliptique :

EquationCourbesElliptiques
Deux courbes elliptiques

Sur ces courbes, on va définir deux opérations : étant donné deux point P et Q de la courbe, on note :

  • P*Q : le troisième point d'intersection entre la courbe et la droite (PQ). Si P=Q, la droite (PQ) est la tangente à la courbe au point P.
  • P+Q : le symétrique de P*Q par rapport à l'axe de symétrie de la courbe.
    On peut démontrer que le point P+Q existe toujours, sans aucune ambiguité (le point P+Q peut éventuellement être un point à l'infini)

CompositionCourbesElliptiques4

Pour deux points P et Q de la courbe (distincts ou non), on fait correspondre un point P*Q et un point P+Q.

Ce qui est intéressant avec cette opération, c'est que si P et Q sont des points à coordonnées rationnelles (des solutions de l'équation de départ), alors P*Q et P+Q aussi. On peut donc, si l'on connaît une solution de l'équation, en déterminer d'autres.

Reprenons la première équation : y² = x3 +1. Une solution particulière de cette équation est le point A (2,3).
Pour déterminer le point A+A, on trace la tangente à la courbe au point A. Cette tangente coupe la courbe en A*A = D(0,-1), donc A+A est le symétrique de D par rapport à l'axe Ox, c'est B (0,1).

SolutionsEquationsElliptiques
Les 5 solutions rationnelles de l'équation y² = x3 +1

On a donc A*A = D, donc 2A = A+A = B
De même :
A*B = C, donc 3A = A + 2A = A+B = C
A*C = B, donc 4A = A + 3A = A+C = D
A*D = A, donc 5A = A + 4A = A + D = E
Et enfin, A*E = O (le point à l'infini), donc 6A = A + E = O
O est élément neutre, puisque A+O = A.
Les 5 solutions de l'équation y² = x3 +1 sont donc tous les multiples du point A !

Si on part sur la deuxième équation y² + y = x3 - x, les choses se passent légèrement différement. Une solution évidente est la solution A(0,0).
En suivant la même méthode, on trace la tangente à la courbe au point A, ce qui nous donne le point A*A = B'(1,-1), et donc, 2A = B(1,0).

SolutionsEquationsElliptiques2

On peut poursuivre : 3A = C (-1,1)
4A = D (2,-3)
5A = E (-0.25, -0.625)
6A = (6,14)
7A = (-5/9 , 8/27)
etc.
En continuant ainsi, on passera par tous les points à coordonnées rationnelles de la courbe, qui sont en nombre infini. Puisque le point A(0,0) permet de trouver l'ensemble infini des solutions de l'équation, on dira que A est un point générateur.

Mais parfois, il arrive qu'un point générateur ne suffise pas pour obtenir l'ensemble des points rationnels de la courbe. C'est par exemple ce qui arrive avec la courbe d'équation y² + y = x3 + x² - 2x, où il est nécéssaire d'avoir deux points générateurs.
Le nombre minimum de points générateurs nécéssaires pour engendrer l'ensemble des points rationnels de la courbe est appellé son rang, et c'est ce nombre qui mesure la complexité de la courbe elliptique que l'on étudie.
Ainsi, la courbe y² + y = x3 - x est de rang 1, la courbe y² + y = x3 + x² - 2x est de rang 2 et la courbe y² = x3 +1 est de rang 0 (puisqu'elle n'a qu'un nombre fini de solution).
Le rang d'une courbe elliptique est toujours un nombre fini, mais n'est a priori pas borné. On ne connaît cependant que très peu de courbes elliptique de très haut rang, le record étant une courbe de rang (au moins) 28, et date de 2006 :

y² + xy + y = x3 - x² - 20067762415575526585033208209338542750930230312178956502x + 34481611795030556467032985690390720374855944359319180361266008296291939448732243429

Les courbes de haut rang sont en fait particulièrement rares, tandis que les courbes de rang 0 ou 1 semblent légions. Mais est-ce toujours le cas ? Si je prend au hasard une courbe elliptique, quelle est la probabilité de tomber sur une courbe de rang 0 ou 1 ? L'expérience montre que environ la moitié sont de rang 0, l'autre moitié de rang 1, et que les rang supérieurs sont négligeables. 
En moyenne (dans un sens que je n'expliquerai pas), on doit donc s'attendre à ce que le rang d'une courbe elliptique soit autour de 0.5. 

Mais la démonstration que le rang moyen est bien 0.5 n'est pas aisée... Ce n'est d'ailleurs aujourd'hui toujours pas démontré, mais on s'approche doucement de cette valeur.
Avant que Bhargava et Shankar ne s'intéressent au sujet en 2010, on s'était arrêté à un rang moyen inférieur à 1.79. Mais la démonstration de cette valeur sous-optimale utilise comme acquis la démonstration de l'hypothèse de Riemann et de la conjecture de Birch et Swinnerton-Dyer (deux conjectures à un millions de dollars que l'on est très loin d'avoir percé).
Aujourd'hui, on sait que le rang moyen des courbes elliptique est inférieur à 1.17, et pas besoin de théorèmes non démontrés pour le prouver. C'est en particulier ce théorème qui a permis à Bhargava d'obtenir la médaille Fields.

Le théorème 290.
Un dernier théorème de Bhargava que j'apprécie tout particulièrement : le théorème 290 ! Il dit la chose suivante :

On considère une forme quadratique définie positive à coefficients entiers.
Si elle peut représenter les 29 nombres suivants :
1, 2, 3, 5, 6, 7, 10, 13, 14, 15, 17, 19, 21, 22, 23, 26, 29, 30, 31, 34, 35, 37, 42, 58, 93, 110, 145, 203, and 290
alors, elle peut représenter n'importe quel nombre entier (on dit qu'elle est universelle).

Par exemple, le polynôme Q(x,y,z,t) = x²+y²+z²+t² est une forme quadratique définie positive à coefficients entiers.
On peut vérifier qu'il existe un moyen d'écrire 
tous les nombres de la liste avec ce polynôme : 1 = Q(1,0,0,0), 2 = Q(1,1,0,0), 31 = Q(5,2,1,1), etc. D'après le théorème 290, tous les nombres entiers 
Autrement dit, n'importe quel nombre peut être écrit comme somme de (au plus) 4 carrés. Cette propriété porte un nom, c'est le théorème des quatre carrés de Lagrange. Le théorème 290, lui, permet de généraliser le théorème de Lagrange en fournissant un critère d'universalité des formes quadratiques. (à noter tout de même que le théorème de Lagrange intervient dans la démo du théorème 290)
Par contre, le polynôme Q(x,y,z) = x² + y² + z² échoue au test, puisqu'il est impossible d'écrire 7 comme somme de trois carrés : ce polynôme n'est pas universel.

Les 29 nombres de l'énoncé sont optimaux : pour chacun de ces entiers, il existe une forme quadratique représentant l'ensemble des entiers sauf lui. Par exemple, la forme quadratique x² + 2y² + 2z² + 5t² représente tous les nombres, sauf 15 !

Ce critère a permis à Bhargava de compléter la liste des forme quadratiques quaternaires (à 4 inconnues) universelles. Alors que Ramanujan pensait qu'il n'y en avait que 54, Bhargava a montré qu'il y en avait en fait 6436 !


Sources
The Work of Manjul Bhargava

Composition and Bhargava's cube, Florian Bouyer

Answers on a donut – the Fields medal lecture of Manjul Bhargava, Rachel Thomas

Universal quadratic forms and the 290-Theorem, Manjul Bhargava and Jonathan Hanke

Manjul Bhargava, médaille Fields 2014, Étienne Ghys
Le rang des courbes elliptiques, François Brunault

Posté par El Jj à 10:00 - Commentaires [3] - Permalien [#]
Tags : , , , , ,

07 août 2014

Aquitaine-Poitou-Charente-Limousin

En juillet dernier, Antoine Planchot, sur Twitter, proposait aux matheux le défi suivant :

Quand on me pose, directement ou indirectement, ce genre de question, je réagis toujours plus ou moins de la même façon 
- je lis l'énoncé en me disant que cela n'a pas l'air si difficile, et je retourne vaquer à mes occupation, 
- je libère 10 minutes de mon planning pour y réfléchir un peu plus précisément, 
- deux heures plus tard, j'enrage de ne pas encore avoir trouvé, 
- trois jours plus tard, je résous enfin le problème, maugréant qu'en fait, c'était trivial !

Pour ce problème de #RéformeTerritoriale, je suis toujours bloqué dans la phase 3, mais je suis persuadé qu'un lecteur bien plus malin que moi trouvera l'idée qui m'a échappé. Je ne suis donc pour l'instant pas encore en mesure d'aider François Hollande et son gouvernement, mais on va quand même essayer pour aujourd'hui de trouver une borne supérieure satisfaisante du nombre de cartes à envisager !

Si je compte bien, la France compte 26 régions (métropolitaine ou d'outre-mer), ainsi qu'une collectivité métropolitaine (la Corse) et 5 d'outre-mer.
Je ne crois pas qu'il ait été à un moment donné question de fusionner la Martinique avec la Franche-Compté, donc on ne prendra pas en compte les régions et collectivités d'outre-mer dans le problème. Puisque l'idée que la Corse puisse fusionner avec la région PACA a été étudiée, on prendra en compte dans le calcul 22 régions françaises.

CarteDeFrance
La France de la #RéformeTerritoriale : 22 régions, 44 frontières, 23 points triples

Les nombres de Bell
Première idée naïve : combien existe-t-il de façon de partionner un tel ensemble de 22 éléments ? De toutes ces partitions, on aura par exemple l'actuel projet de réforme territoriale :

ReformeTerritoriale
Une carte de France à 13 régions, dont la future Aquitaine-Poitou-Charente-Limousin, qu'il faudra renommer au plus vite.

Ou bien, la partition correspondant aux différents indicatifs téléphoniques locaux :

Projet06
Une carte de France à 5 régions

Mais il y aura également cette partition des régions Françaises en 3, en fonction du nombre de voyelles et consonnes dans leur nom. Cette dernière ne répond pas au problème initial, puisque les régions formées ne sont pas d'un seul tenant ("connexe"). Pas grave, on cherche pour l'instant une estimation haute du nombre de carte que l'on pourrait faire.

MauvaiseReforme4
Un redécoupage à exclure
(En bleu, les régions comptant plus de consonnes que de voyelles, en rouge les régions comptant plus de voyelles que de consonnes, et en blanc les régions égalitaires)

Le nombre de façons de partionner un ensemble à n éléments porte un nom, ce sont les nombres de Bell (du nom de Eric Temple Bell, mathématicien célèbre autant pour ses travaux en combinatoire que pour ses livres d'histoire des mathématiques ou de science-fiction). Le n-ième nombre de Bell, noté Bn, représente donc le nombre de partitions différentes d'un ensemble à n éléments.

B0 = 1 : il n'y a qu'une seule (non) façon de découper un ensemble vide.
B1 = 1 : il n'y a qu'une seule façon de découper un ensemble à 1 élément.
B2 = 2 : dans un ensemble à 2 éléments, on peut soit regrouper les deux éléments (première partition), soit ne pas les regrouper (seconde partition).
B3 = 5 : 1 partition en une seule région, 3 partitions en deux régions et 1 partition en trois régions.

GrandOuestRedecoupé
5 façons de redécouper le grand Ouest

B4 = 15. Pour trouver cette valeur, procédons méthodiquement, en rajoutant la haute-Normandie dans le grand Ouest. Après un redécoupage, 4 cas différents peuvent se produire, suivant le nombre de régions pouvant être annexées à la Haute-Normandie.
- zéroième cas : toutes les régions sont liées à la HN → 1 découpage
- unième cas : une région (parmi les 3 du grand Ouest) n'est pas annexée à la HN → 3 découpages
- deuxième cas : deux régions ne sont pas fusionnées à la HN, soit 3 paires possibles. Chacune de ces paires admet 2 découpages. Au total, on a donc 3 × 2 = 6 découpages
- troisième cas : aucune région n'est accolée à la HN. On ne compte donc que les découpages à 3 régions, soit B3 → 5 découpages.
On a bien B4 = 1 + 3 + 6 + 5 = 15.

On peut déterminer les valeurs plus grande de Bn en suivant la même trame, en fonction du nombre de région k qui ne seront pas annexées à une n+1-ième région. Parmi les n premières régions, il y a k parmi n façons de choisir ces k régions. Ces k régions admettant Bk découpages, on a donc, pour chaque k,  k parmi n×Bk découpages.

NombreDeBell

Les valeurs suivantes de Bn se calculent par récurrence


Au final, les valeurs plus grandes des Bn sont donc données par la formule de récurrence :

Formule Aitkin

Ainsi,  B5  = 1×B0 + 4×B1 + 6×B2  +4×B3 + 1×B4 = 52

Cette formule nous permet alors de savoir que, pour 22 régions, on peut compter
B22 = 4 506 715 738 447 323 (=4,5×1015) (=4,5 billiards de) partitions !

Les nombres de Bell ont des tas de propriétés fascinantes (par exemple, le n-ième nombre de Bell est la valeur en 0 de la n-ième dérivée de la fonction f(x) = exp(exp(x)-1)), mais il est inutile d'en parler davantage ici, puisque n'est de toutes évidence pas une bonne modélisation ; le nombre de partitions est bien supérieur au nombre de redécoupages.

Passage au dual
Plutôt que de chercher à fusionner les régions, cherchons donc plutôt à retirer les frontières entre régions. Ainsi, il n'y a plus aucun risque de fabriquer des régions non connexes.

La France (métropolitaine) compte 43 frontières, auquel on peut ajouter une 44e frontière P.A.C.A./Corse. Un redécoupage territorial consiste alors à choisir, pour chacune des 44 frontières, si il faut la garder ou non.
Avec cette approche, on peut donc donner une nouvelle estimation (haute) du nombre de partitions. Il y a donc (au plus) 244 = 17 592 186 044 416 (=1,8 ×1013) (=18 billions de) redécoupages !

Le problème de cette approche, c'est que plusieurs choix différents de frontières à retirer donnent un même redécoupage.

Tripoint_Problem
Autour du tripoint Haute-Normandie/Picardie/Île-de-Frane, 4 choix différents des frontières à retirer aboutissent à la fusion des mêmes régions

Ce problème apparaît pour chacun des tripoints (point où trois frontières se rejoignent), lorsque sur les trois frontières, une seule est gardée (la région formée est alors mal délimitée). Et des tripoints régionaux, il y en a 23 en France (sur les 44 frontières, 42 sont ratachées à au moins un tripoint).

Autour d'un tripoint, 3 frontières se rejoignent, ce qui devrait donner 23=8 redécoupages. Mais sur ces 8 redécoupages, 5 sont vraiment différents.
Pour dénombrer les découpages, on va partir d'un premier tripoint (par exemple, le tripoint Bretagne/Pays-de-la-Loire/Basse-Normandie), qui donne naissance à 5 découpages. On choisit ensuite un deuxième tripoint tel qu'il existe une frontière la reliant au premier tripoint (par exemple, le tripoint Pays-de-la-Loire/Basse-Normandie/Centre). On a alors deux nouvelles frontières que l'on peut garder ou non, ce qui multiplie par 2²=4 le nombre de découpages possibles. En regardant d'un peu plus près, on peut remarquer que multiplier par 3 à chaque nouveau tripoint suffit :

  • Si la frontière liant les deux tripoints est gardée, alors il faut qu'au moins une des deux nouvelles frontières soit gardée. On exclut donc un des 4 découpages, celui où les deux nouvelles frontières ne sont pas gardées.

  • Si la frontière liant les deux tripoints n'est pas gardée, il n'y a que deux possibilités pour créer des régions bien délimitées : soit on garde les deux nouvelles frontières, soit on en garde aucune.
    Dans certains cas, on multiplie par 3, dans d'autres, on multiplie par 2. Pour avoir une estimation haute, on multipliera toujours par 3.

A chacun des 22 tripoints suivant, on mutlipliera donc par 3 le nombre de découpages. Le résultat sera à multiplier par 2², pour prendre en compte les frontières sans tripoints (PACA/Corse et Nords-Pas-de-Calais/Picardie). On a donc au total :

5 × 322 × 4 = 627 621 192 180 (=6,3 × 1011) (=627 milliards de) découpages

Encore une fois, cette estimation est trop haute, pour plusieurs raisons. La première, c'est qu'on a supposé que chaque tripoint apporte deux nouvelles frontières, ce qui n'est pas toujours le cas. Suivant la façon dont on choisit le tripoint suivant, on peut avoir qu'une seule nouvelle frontière, voire aucune. Si seule une nouvelle frontière se présente, on ne multipliera le nombre de découpage que par 2 ; si un tripoint n'apporte pas de nouvelle frontière, on multipliera par 1.

La deuxième, c'est que la multiplication par 3 n'est pas optimale (on multiplie par 3 si la frontière est gardée (62% des découpages), et par 2 sinon. Un meilleur coefficient multiplicateur serait de 2,61). Les multiplicateurs 2 et 1 du paragraphe précédent ne sont eux non plus pas optimaux.

En prenant ceci en compte, cela donne * (environ) 2 000 000 000 (=2 milliards de) découpages. Cette dernière estimation a elle aussi été faite à la hache, d'autant qu'il y a encore d'autres points à prendre en compte pour parfaire le calcul. En effet, il est possible que les régions formées ne sont pas simplement connexes (si une région est enclavée à l'intérieur d'un autre), ce qui diminue encore une fois le nombre de redécoupages possibles.

En fait, la seule façon de connaître le nombre exact de redécoupages possibles serait d'écrire un programme informatique qui les énumère tous... Mais en attendant, j'estime le nombre de découpages à un milliard, et c'est mon dernier mot.


Pour les besoins des illustrations de l'article, j'ai fabriqué un petit script pour fabriquer de *jolies* cartes pour tester des réformes territoriales, disponibles sur eljjdt. En fouillant le script, vous y trouverez les données utiles pour faire un programme compteur.

06 juillet 2014

Du simple au Dobble

C'est les vacances, l'occasion de sortir une nouvelle fois les jeux de société pour jouer avec beau-papa. Pas de Monopoly ou de serpents et échelles, sortons plutôt un véritable jeu moderne, comme il en existe des floppées aujourd'hui, tous plus inventifs les uns que les autres (sérieusement, allez dans les boutiques de jeu de société !). Je vais donc parler de Dobble de Asmodée, un jeu d'observation et de vitesse pour toute la famille, qui cache une structure mathématique hallucinante.  Une fois n'est pas coutume, l'article qui suit m'a été inspiré d'un des derniers épisodes de Podcast Science.

p-3700427700183_15543_3-dobble
55 cartes, 8 symboles par cartes ; deux cartes spont retournées, quel est leur symbole en commun ?...

Le concept du jeu Dobble est assez simple, surtout quand on le compare aux mathématiques qui ont été déployées pour le concevoir. Plusieurs variantes des règles du jeu existent, mais le principe reste toujours le même : deux cartes contenant chacune 8 symboles sont présentées, il faut retrouver le plus rapidement possible quel est le symbole commun aux deux cartes.

Là où les mathématiques rentrent en jeu, c'est que quel que soit le couple de cartes retournées, il y a toujours un (et un seul) symbole commun. La conception des cartes n'a donc pas du tout été faite au hasard, et n'est pas du tout évidente a priori. 

Comment fabriquer soi-même son propre jeu Dobble ? Combien faut-il prévoir de cartes ? De symboles ? Puis-je faire un Dobble à 157 cartes ? Il n'y a qu'une seule façon de résoudre le problème : comprendre ce que sont les plans projectifs finis !

Dobble d'ordre 7
Le jeu original Dobble chaque contient 8 symboles différents par cartes et 55 cartes.

La première chose à dire, c'est qu'il n'existe pas un symbole qui soit commun à toutes les cartes, puisque cela diminuerait grandement l'intérêt du jeu. Mais cette trivialité va nous permettre de dénombrer le nombre de cartes existant au maximum.
Pour cela, on prend un des symboles (disons, le morceau de fromage), et on compte le nombre de cartes où il apparaît (disons r). Ces r cartes ont des symboles tous différents.
D'après ce que l'on vient de dire, il existe au moins une autre carte sur lequel le morceau de fromage n'apparaît pas. Mais cette carte a tout de même un symbole en commun avec chacune des r cartes possédant le fromage (différent à chaque fois). Ces symboles étant tous différent, le nombre r est donc au maximum égal à 8.
Donc, au maximum, il y a 8 cartes possédant un symbole donné.

Prenons maintenant une carte au hasard. Cette carte possède 8 symboles. Pour chaque symbole, on peut compter (au plus) 7 autres cartes possédant ce symbole, ce qui donne finalement 1+8×7 = 57 cartes différentes au maximum.

En suivant le même raisonnement, on peut donc montrer qu'un jeu de Dobble avec n symboles par cartes contiendra au maximum 1+n(n-1) cartes.

Mais alors, pourquoi le jeu Dobble ne contient que 55 cartes ? La réponse est désespérement terre à terre : l'imprimeur du jeu ne permettait que de faire 60 cartes, et les auteurs ont préféré mettre 5 cartes "règles" pour diversifier le jeu, plutôt que d'en respecter la complétude (ce qui ne chagrinera que les mathématiciens, qui ne sont heuresement pas le coeur de cible du jeu...).

Dobble d'ordre 2
La règle qui régit les cartes du Dobble est 

Deux cartes possèdent toujours un (et un seul) symbole en commun

Ce qui rappelle forcément un des principes de base de la géométrie :

Par deux points distincts passe toujours une (et une seule) droite.

Du coup, on a envie de faire le rapprochement, et de se dire que les cartes d'un jeu de Dobble peuvent être les points d'un plan, tandis que les symboles seront les droites. Et ça marche plutôt bien !

PG(2,1)
Représentation géométrique du jeu de Dobble à 2 symboles par cartes (et donc, à 1+2*1 = 3 cartes)

Bien sûr, le plan contient une infinité de points, et par chaque point passe une infinité de droites, ce qui permettrait de fabriquer un jeu de Dobble possédant une infinité de cartes, chacune possédant une infinité de symboles... Le plan euclidien complet possède beaucoup trop de points !
Du coup, on va limiter notre plan à, disons, seulement 4 points (les autres points n'existent pas !), ce qui permet de fabriquer un jeu jouable comptant 4 cartes et 6 symboles :

PG(2,2,0)
On se limite ici à 4 points-cartes : les droites roses et vertes n'ont donc pas de points d'intersection. On peut même aller jusqu'à dire qu'elles sont parallèles, puisqu'elles ne se coupent pas.
Par chacun des 4 points passe donc exactement 3 droites.

D'un côté, on sait que pour n=3 symboles par cartes, il semble possible de fabriquer 1 + 3*2 = 7 cartes.
D'un autre côté, on sait que quand la géométrie est projective, les droites parallèles se coupent sur une droite d'horizon, et qu'en plus, le principe de dualité laisse entendre que si par 1 point passe 3 droites, alors on doit toujours compter sur 1 droite 3 points.

Du coup, il nous faut trouver un moyen d'ajouter 3 cartes à ce Dobble, en ajoutant des points d'intersection aux droites parallèles (violet/rouge, bleu/jaune, ainsi que rose/verte, qui sont parallèles). Pour cela, il va être nécéssaire de prendre conscience que "droite" ne fera plus référence à l'objet géométrique rectiligne, mais à un *truc* qui passe par plusieurs *points* : on peut donc courber les droites, et faire apparaître trois nouveaux points d'intersection.

PG(2,2)

Un Dobble parfait : 7 droites (symboles) et 7 points (cartes) 

Cette représentation est affreuse, d'autant qu'il existe une représentation un peu plus habituelle de ce regroupement de 7 points et 7 droites où chaque droite contient 3 points et où chaque point est à l'intersection de 3 droites, le plan de Fano :

Fano
Le plan de Fano (rien à voir avec les reliques de la mort)
Contrairement aux apparences, le cercle vert est bien une droite, et passe comme les autres par trois points

Le plan de Fano est en fait l'exemple le plus dépouillé qui existe de plan projectif, puisqu'il ne contient pas une infinité de points selon deux dimensions (comme dans la représentation basique d'un plan, qu'il soit projectif ou non), mais est composé de seulement 7 points. Les axiomes de base de la géométrie (projective) s'y appliquent cependant toujours :
- par deux points passe toujours une (et une seule) droite
- deux droites se coupent toujours en un (et un seul) point (la notion de parallélisme n'existe pas en géométrie projective, les droites se coupent à l'infini)
- il existe un quadrangle n'ayant pas trois points alignés (pour éviter les cas dégénérés)

Lorsqu'une structure respecte ces trois axiomes, elle peut prétendre au titre de plan projectif. Si, en plus, elle possède un nombre non infini de points, on parlera... de plan projectif fini. C'est le cas du plan de Fano.
Un jeu de Dobble complet (possédant les n(n-1)+1 cartes avec n symboles) est donc un plan projectif fini, puisque les trois axiomes y sont bien respectés, si on admet la convention 'point'='carte' et 'droite'='symbole' :
- deux cartes ont toujours un (et un seul) symbole en commun
- deux symboles donnés n'apparaissent ensemble que sur une seule carte
- on peut trouver quatre cartes ayant deux à deux des symboles communs différents (sinon, le jeu n'est pas intéressant)

L'exemple du jeu de Dobble à 3 cartes et 2 symboles par carte ne peut pas être qualifié de complet, à cause du dernier axiome non respecté. En rajoutant une quatrième carte, on se retrouve à construire un Dobble à 7 cartes, qui lui, est complet, puisque c'est le plan de Fano. En généralisant, l'existence d'un jeu de Dobble complet à n symboles entraîne l'existence d'un plan projectif fini à n²-n+1 points et droites, et vice versa.

Pour construire des Dobble, il suffit donc finalement de construire des plans projectifs finis, et le jeu du Dobble nous permet de donner les propriétés de ces plan projectifs :
Etant donné un plan projectif fini, il existe un entier n tel que 
- il contient n²–n+1 points
- il contient n²–n+1 droites
- chaque droite est composé de n points
- par chaque point passe n droites
Le nombre n n'est pas appellé l'ordre du plan projectif. Par contre, on appelle ordre du plan projectif le nombre q=n–1 (un plan projectif fini d'ordre q possède donc q²+q+1 points et droites, chaque droite contient q+1 points, chaque point est à l'intersection de q+1 droites).

Bref, construisons encore plus de plans projectifs finis, pour ensuite construire encore plus de Dobbles !

Dobble d'ordre 3
Pour construire des plans projectifs finis, on peut tenter de généraliser la construction du plan de Fano, qui était d'ordre 2. Pour cela, nous allons avoir besoin... des corps finis !

Un corps, c'est une structure algébrique dans lequel on peut faire des additions, soustractions, multiplications et divisions. L'ensemble infini des nombres réels est un l'exemple le plus intuitif de corps mais il y en a bien d'autres, comme par exemple le corps F3, composé des trois nombres 0, 1 et 2. Les additions et multiplications fonctionnent comme sur les entiers habituels, mais on n'y garde que le reste dans la division euclidienne par 3 :

F3
Table d'addition et de multiplication dans le corps F3
Ici, 2+2 = 1, car 4 a pour reste 1 dans la division euclidienne par 3.

Le corps F<sub>3</sub> donne naturellement naissance au plan F²<sub>3</sub>, qui possède 9 points :

F3²
Le plan (non projectif) fini F²3

Puisqu'on peut y faire additions et multiplication, on peut y faire des fonctions affines, ce qui correspondra aux équations des droites. Miracles des corps finis : chaque droite passera par exactement 3 points !

Droites de F3²
On peut ainsi écrire 12 équations de droites, réparties en 4 familles de 3 droites parallèles.
Remarquons que y = x+2, y = x -1 sont des équations d'une même droite, puisque, dans le corps F3, 2 = -1.

Par chacun des 9 points passe exactement 4 droites : on vient de fabriquer un Dobble à 9 cartes, 12 symboles et 4 symboles par cartes, en faisant correspondre un symbole à chaque droite. 
Mais on peut faire encore mieux, puisqu'on peut a priori atteindre 13 cartes, en rendant projectif ce plan. Pour cela, on admet que chaque famille de droites parallèle se coupent sur une droite à l'infini, ce qui nous donne les 3 points d'intersection manquant et la droite manquante :

Fano3
Chaque droite est composé de 4 points, par chaque point passe 4 droites
Cette structure, construite à partir du corps F3, permet de construire un jeu de Dobble à 4 symboles par cartes

En réorganisant les points, on peut obtenir une version un peu plus symétrique du plan projectif fini d'ordre 3 :

GraphePlanProjOrdre2
Plan projectif fini d'ordre 3.
On admet que le point central et les trois points extrémaux sont alignés, pour ne pas alourdir le schma avec une droite disgracieuse

Dobble d'ordre q premier
Cette construction se généralise très facilement, mais seulement pour les ordres où q est un nombre premier, puisque, dans ce cas, le corps Fq existe, et se construit à partir à partir des entiers 0, 1, 2, ..., q-1 et de la division euclidienne par q.

Du coup, en prenant q=5, on peut construire le corps F5, le plan associé à 25 points, ses 30 droites (5 par direction), puis sa version projective à 31 points et 31 droites.
Le gros problème, c'est que si on le dessine, ça sera complètement illisible... Pas grave, on va le faire seulement algébriquement : les points sont de la forme (x,y), avec x et y compris entre 0 et 4 ; les droites sont de la forme y=ax+b ou x=b, avec a et b compris entre 0 et 4, ainsi que la droite à l'infini. Chaque famille de droite donne naissance à un point à l'infini.
Il n'y a plus qu'à compléter le tableau pour avoir une idée d'un plan projectif fini d'ordre 5, et donc, d'un Dobble à 6 symboles par cartes.

PG(5,1)
Le tableau permettant de fabriquer le Dobble d'ordre 5, autrement dit, l'édition Junior du Dobble.
La notation des points à l'infini est loin d'être propre, mais la notation (∞,2∞) correspond au point à l'infini dans la direction y = 2x.

La même construction avec q=7 permet de fabriquer le Dobble à 8 symboles par cartes, autrement dit, le Dobble classique. Les joueurs invétérés fabriqueront eux même leur version du jeu à 12 symboles par carte (q=11) ou à 14 symboles par carte (q=13)...

Dobble d'ordre q quelconque
Et pour les autres valeurs de q ?... Eh bien, ça va dépendre !

Déjà, il y a les puissances des nombres premiers : 4=2², 8 = 23, 9 = 3², ...
Pour chacun de ces ordres, il existe un corps fini ayant le nombre adéquat d'éléments. Le seul soucis, c'est que la construction est un peu plus compliquée (on doit passer par des calculs avec des polynômes, que je ne vais pas détailler ici). Par exemple, le corps à 4 éléments (0, 1, u et v) ressemble à ça :

F4
Table d'addition et de multiplication de F4

Du coup, à partir de ces tables, on peut faire le même travail sur les équations des droites... Et ça marche ! 

PG(2²,1)
Sur chaque ligne et chaque colonne, on compte 5 X (donc, 5 symboles par cartes et 5 cartes par symboles)

On pourrait faire le même travail pour F8 et F9, mais après avoir fait celui de F4, je n'ai plus le courage...
La méthode des équations de droites n'est pas la seule façon de construire des plan projectifs finis. En procédant autrement, on peut tomber sur des plans fondamentalement différents. Il existe ainsi des plans projectifs finis d'ordre 9 différents de celui construit à partir de F9, mais les trois plans en question ne seront plus arguésiens (espace dans lequel le théorème de Desargues, que j'avais évoqué ici, n'est plus vrai).

Et puis, il y a les autres valeurs, celles qui ne sont pas des puissances de nombres premiers, comme 6, 10 et 12. Pour ces valeurs là, il n'y a pas de règle, mais la seule chose qui est sûre, c'est que la méthode des équations de droites ne fonctionnera pas, puisqu'il n'existe pas de corps fini ayant ce nombre d'éléments.

Pour q=6, le problème n'a aucune solution, ce qui a été démontré en 1901 par Gaston Terry, quand il a prouvé que le problème des 36 officiers d'Euler (comment placer 36 officiers de 6 régiments différents et de 6 grades différents dans une grille 6x6 sans qu'une ligne ou une colonne compte deux fois des officiers de même régiment ou de même grade) était insoluble.

Pour q=10, Clement Lam a montré qu'un plan projectif fini de cet ordre ne peut pas exister, en calculant l'ensemble des possibilités.

Pour q=12, on n'en sait rien. L'existence d'un Dobble à 13 symboles par cartes et à 157 cartes est donc encore aujourd'hui un problème ouvert. A vous de chercher ! Pour les valeurs de q non premières plus grandes (15, 18, 20, 42, ...), le problème est lui aussi toujours ouvert.

Bref, le Dobble à est mon avis la seule application des plans projectifs finis avec des dessins de bonhomme de neige et de fromages.

Resumay
Récapitulatif des différents Dobble existants


Sources :
Dobble et la géométrie finie, sur Images des Maths 

Posté par El Jj à 10:00 - Commentaires [11] - Permalien [#]
Tags : , , ,

08 juin 2014

L'énigme la plus difficile de TOUS LES TEMPS !!!!

xkcd-246-casse-tete-labyrinthe

On connaît tous l'énigme des deux portes :

Dans un labyrinthe, deux gardes protègent deux portes. L'une des deux portes mène à la liberté, l'autre à une mort certaine. L'un des deux gardes ment systématiquement, tandis que l'autre dit toujours la vérité, mais vous ne savez pas qui est qui. Pour déterminer le chemin de la liberté, vous n'avez le droit qu'à une seule question à l'un des deux gardes. Quelle question poser ?

Cette énigme, sous sa forme actuelle, a été popularisée par le film Labyrinthe (1986) de Jim Henson, avec David Bowie. Mais les problèmes de logique du style "l'un ment, l'autre dit la vérité" viennent essentiellement de l'esprit tordu du génial Raymond Smullyan, où il pose les bases en 1978 dans son livre "Quel est le titre de ce livre ?" (à feuilleter absolument !).

Pour déterminer le chemin vers la liberté, il suffit de poser à l'un des deux gardes la question :

Q : Si je demande à l'autre garde le chemin de la liberté, quelle porte m'indiquera-t-il ?

Puisque les deux gardes sont impliqués dans cette question, la réponse sera forcément un mensonge. Il suffit donc de choisir la porte qui n'a pas été indiquée par le garde pour garantir son accès à la liberté. Des questions alternatives sont possibles, notamment la suivante, qui a le mérite de ne pas faire intervenir les deux gardes dans l'histoire :

Q' : Si je vous demandais quel est le chemin de la liberté, quelle porte m'indiqueriez-vous ?

Si on pose la question "quel est le chemin de la liberté ?" au garde menteur, il indiquerait la porte de la mort. Sachant cela, il répondra donc à Q' le contraire, à savoir, la porte de la liberté. Quel que soit le garde à qui cette question est posée, la réponse que l'on obtiendra indiquera donc forcément le bon chemin (il faut admettre que les gardes raisonnent en parfaits logiciens, ce qu'il est préférable de vérifier avant de risquer sa vie en posant des questions tordues).

Ca, c'est l'énigme classique. Mais je suis tombé cette semaine sur une version alternative de l'énigme, sobrement intitulée :

L'énigme de logique la plus difficile de tous les temps
Cette énigme, attribuée à Raymond Smullyan a particulièrement été étudiée par le philosophe et logicien George Boolos. C'est dans un article du Harvard Review of Philosophy qu'il publie en 1996 l'énigme :

Trois dieux A, B et C se nomment Vérité, Mensonge et Hasard (vous ne savez pas quel dieu est qui). Lorsqu'on leur pose une question, Vérité répond toujours la vérité, Mensonge répond toujours le contraire de la vérité, et Hasard répond toujours au hasard entre la vérité et son contraire. Votre tâche est de déterminer l'identité de ces trois dieux, à l'aide de trois questions fermées.
Les dieux comprennent parfaitement le français et la logique, mais ils ne répondront que dans leur propre langue qui ne possèdent que deux mots, « da » et « ja ». Ces mots signifient « oui » et « non », mais vous ne savez pas lequel se rapporte à quoi (!).

Quelques remarques tout de même : on peut poser plusieurs questions à un même dieu (mais pas plus de 3 en tout) ; la deuxième question que l'on posera peut dépendre de la réponse « da » / « ja » obtenue à la première réponse (idem pour la troisième) ; quand on pose une question à Hasard, il jette une pièce dans sa tête, et répondra la vérité s'il obtient pile, et le contraire de la vérité sinon.

Oui, cette énigme est particulièrement horrible. Si vous ne voulez pas vous faire spoiler la solution, arrêter tout de suite la lecture de cet article, et revenez dans quelques jours. Pour les autres, voici les questions à poser, selon l'article de Boolos :

Q1, à poser à A :

Est-ce que (« da » signifie « oui » si et seulement si vous êtes Vérité) si et seulement si B est Hasard ?

Q2 à poser à B si la réponse était « ja » ou à C si la réponse était « da » :

Est-ce que « da » signifie « oui » si et seulement si Rome est en Italie ?

Q3, à poser au même dieu que lors de question 2 :

Est-ce que « da » signifie « oui » si et seulement si A est Hasard ?

Si la réponse à Q2 est « da », le dieu ayant répondu à cette question est Vérité, sinon, c'est Mensonge.
Si Vérité a répondu à Q3, la réponse « da » signifie que A est Hasard, et la réponse « ja » signifie que A est Mensonge ;
Si Mensonge a répondu à Q3, la réponse « da » signifie que A est Vérité, et la réponse « ja » signifie que A est Hasard.
On connaît maintenant l'identité des trois dieux !

Oui, mais... pourquoi ?!
Rappelons que, en logique, le "si et seulement si" (ssi) désigne l'équivalence logique : l'expression "P ssi Q" est vraie lorsque les expressions P et Q sont soit toutes les deux vraies, soit toutes les deux fausses. Ainsi, l'expression "(P ssi Q) ssi R" sera vraie dans deux cas : lorsque P, Q et R sont toutes les trois vraies, ou lorsque exactement une seule des trois propositions est vraie.
On peut donc reformuler plus clairement Q1 par :

Est-ce qu'un nombre impair des affirmations suivantes sont vraies : « da » signifie « oui », vous êtes Vérité, B est Hasard ?

Cette question n'a que un seul but : déterminer un des deux dieux qui n'est pas Hasard, afin d'être certain de ne pas s'adresser à lui lors des questions Q2 et Q3. 
Si A est Hasard, alors quelle que soit sa réponse, on sera amené à parler à B ou C lors des questions suivantes.
Dans le cas où A est soit Vérité, soit Mensonge, on peut observer 8 éventualités :

TableDesVerités

Et finalement, que l'on s'adresse à Vérité ou à Mensonge, on obtiendra les mêmes réponses :

TableDesVeritésEtMensonges

Un « da » signifie alors que B est Hasard, on s'adressera donc à C lors des questions suivantes ; un « ja » nous amenera à parler à B, qui n'est pas Hasard.

La question 2 (Est-ce que « da » signifie « oui » si et seulement si Rome est en Italie ?) nous permet de connaître l'identité du Dieu à qui l'on s'adresse.
Puisque Rome est en Italie, la réponse est « oui » si « da » signifie « oui », et est « non » sinon. Vérité répondra donc « oui » (« da ») dans le premier cas, et « non » (« da ») dans l'autre cas : au final, Vérité répondra « da » quel que soit la sens de « da ». Mensonge, quant à lui, répondra toujours « ja ». Le cas où l'on s'adresserait à Hasard ayant été exclu lors de la question 1, cette deuxième question permet d'identifier le dieu à qui l'on parle.
Remarquons que l'ajout « Rome est en Italie » n'a aucun intérêt, et qu'on peut se contenter de demander "Est-ce que « da » signifie « oui »".

Enfin, la question 3 (Est-ce que « da » signifie « oui » si et seulement si A est Hasard ?) nous permet de statuer sur la réelle identité de A, et donc, des trois dieux. En admettant que l'on s'adresse à Vérité, une réponse « da » signifie que A est bien Hasard, et « ja » signifie que A n'est pas Hasard (et que donc, c'est Mensonge). Si on s'adresse à Mensonge, on a les interprétations contraires. 

Variantes
Cette énigme de logique la plus difficile de tous les temps a longuement été analysée, si bien que plusieurs variantes de réponses ont été proposées.

Une première variante, observée en 2001 par Tim Roberts, est d'utiliser des questions s'inspirant de l'énigme des deux portes, c'est à dire, des questions de la forme :

Si je vous demandais Q, me répondriez-vous « da » ?

Si la réponse logique à la question embarquée Q est « oui », la réponse sera « da », que l'on s'adresse à Vérité ou à Mensonge ; sinon, la réponse sera « ja ». Ce "lemme de la question embarquée" a pour conséquence de simplifier grandement l'énigme, au point que cela revient à ignorer le fait que les dieux puisse mentir et qu'ils répondent dans une langue inconnue.
On peut alors reformuler les questions :

  • Q1' (à A) : Si je vous demandais « B est-il Hasard » , me répondriez-vous « da » ?
  • Q2' (à B « ja » à Q1', à C sinon) : Si je vous demandais « Êtes-vous Vérité » , me répondriez-vous « da » ?
  • Q3' (au même qu'à Q2') : Si je vous demandais « A est-il Hasard » , me répondriez-vous « da » ?

Une autre variante, proposée par Brian & Landon Rabern, est de confronter les dieux au paradoxe logique du menteur (« Je mens »). Imaginons que l'on pose à A la question Q1'' suivante : 

Si je vous demandais Q*, me répondriez-vous « da » ?
où Q* est la question :
« Est-ce que : [(Vous allez répondre « ja » à la question Q1'') et (B est Vérité)] ou (B est Mensonge) »

Trois réponses peuvent arriver :

  • Si A répond « da », c'est que la réponse à Q* est oui. Donc soit B est Mensonge (ce qui est envisageable), soit B est vérité et A a répondu « ja » (ce qui serait paradoxal, donc impossible). Donc B est Mensonge.
  • Si A répond « ja », c'est que la réponse à Q* est non. B est donc ni Mensonge, ni Vérité (car « Vous allez répondre « ja » la question Q1'' » est vrai). Donc B est Hasard.
  • Si B est Vérité, alors la question Q* se ramène à la question paradoxale «Vous allez répondre « ja » à la question Q1''». La tête de A explose, et on en déduit que B est bien vérité.

En une seule question, on a pu déterminer l'identité de B. Un seconde question permet alors simplement de clarifier l'identité de A et C. Il reste alors une question en rab, que l'on pourra poser à Vérité afin d'avoir une réponse définitive à « P=NP ? », « l'hypothèse de Riemann est-elle indécidable ? » ou tout autre question existentielle.


Sources :
Georges Boolos, The Hardest Logic Puzzle Ever
Brian Rabern & Landon Rabern, A simple solution to the hardest logic puzzle ever

Posté par El Jj à 10:00 - Commentaires [7] - Permalien [#]
Tags : , , ,



25 mai 2014

DRH Simulator

Il y a le problème des cartes Panini : à quel moment faut-il arrêter d'acheter au hasard ses cartes à collectionner et les acheter à l'unité, quitte à les payer plus cher ? J'en avais parlé dans cet article.
Il y a le problème du parking avant un concert : faut-il se garer dès la première place disponible et avoir à marcher jusqu'à la salle, ou bien faut-il tenter de se rapprocher au maximum de l'entrée, quitte à perdre du temps en ayant à faire demi-tour ?
Il y a aussi le problème de la meilleure station-service : faut-il s'arrêter prendre de l'essence à la grande surface avant de partir, ou bien s'arrêter à l'une des stations sur le trajet, en espérant y trouver de meilleurs prix ?
On trouve des questions équivalentes dès qu'il s'agit d'investir en bourse ou de poursuivre l'exploitation d'une machine usée plutôt que de la remplacer... Bref, dans une situation qui fait la part belle au hasard, à quel moment faut-il arrêter de tenter le diable ? Un tel problème est un problème d'arrêt optimal, et c'est du plus célèbre d'entre eux que je souhaite parler aujourd'hui : le problème du gogol, aka problème du mariage, aka problème de la dot, aka problème du casting aka...

Queuing
Qui sera le meilleur secrétaire ?...

Le problème des secrétaires
En bon chef d'entreprise que vous êtes, vous avez décidé d'engager un (et un seul) nouveau secrétaire. Vous organisez donc une série d'entretiens, où n candidats se présentent (vous connaissez à l'avance ce nombre n de postulants). Les candidats seront interviewés tour à tour, l'ordre étant aléatoire. A l'issue de chaque entrevue, vous n'avez que deux possibilités : le candidat est embauché ou bien rejeté. S'il est embauché, vous ne poursuivez pas les entretiens ; si il est rejeté, vous n'aurez plus l'occasion de le revoir. Attention : si vous rejetez tous les candidats, vous devrez impérativement garder le dernier (La France est en crise, il faut réduire le chômage, quitte à embaucher n'importe qui). La question est donc : à quel moment est-il préférable d'arrêter les entretiens ? 

Pour faire le meilleur choix, vous ne pouvez vous baser que sur un seul critère : le candidat est-il oui ou non meilleur que tous ses prédécesseurs (on suppose ici que l'on peut classer l'ensemble des postulants du moins bon au meilleur, sans ex aequo possibles). Mais comment peut-on faire pour maximiser les chances de tomber sur LE meilleur des candidats ?

La modélisation du problème est critiquable : un bon responsable des ressources humaines se gardera toujours la possibilité de rappeler un candidat après interview ("on vous rappellera"). De plus, il s'agit rarement de trouver le meilleur candidat, mais celui qui est qualifié pour le poste, quitte à ne garder au final aucun candidat. De plus, on peut imaginer que tous les candidats ne sont pas comparables deux à deux. Le problème des secrétaires connaît de très nombreuses variantes prenant ou non en compte ces objections, ce qui fait que le problèmes d'arrêt optimal forment une catégorie de problèmes particulièrement étudiés.

Cas n = 4
Prenons un premier exemple, avec n = 4 candidats : A (d'un niveau assez bon), B (d'un bon niveau), C (niveau très bon) et D (niveau excellent). L'objectif est donc de choisir D.
L'ordre étant aléatoire, on dénombre 24 possibilités : ABCD, ABDC, ACBD, ACDB, ADBC, ADCB, BACD, BADC, BCAD, BCDA, BDAC, BDCA, CABD, CADB, CBAD, CBDA, CDAB, CDBA, DABC, DACB, DBAC, DBCA, DCAB et DCBA.

Stratégie 0 : Une première stratégie envisageable est de choisir le premier candidat, quoi qu'il arrive. On obtient alors une stratégie qui fonctionne avec une chance sur 4 (25%).

Stratégie 1 : Une autre stratégie envisageable est de s'entrenir avec le premier candidat, sans le garder. Ensuite, on gardera le premier des candidats à se présenter qui sera meilleur que le candidat n°1. Plusieurs cas sont envisageables :
- le premier candidat est D : il sera éliminé, tant pis.
- le premier candidat est C : le seul candidat meilleur que C est D, qui sera donc forcément choisi quand il se présentera -> 6 possibilités sur 24
- le premier candidat est B. Sous cette condition, on prendra le premier des candidats C ou D à se présenter -> 3 possibilités sur 24
- le premier candidat est A. Sous cette condition, le candidat n°2 sera choisi, soit une chance sur trois de tomber sur D -> 2 possibilités sur 24.
Au final, cette stratégie donne 11 chances sur 24 (46% de chances) de tomber sur D, le meilleur candidat. On peut aussi vérifier que l'on choisira C avec une probabilité de 7/24, B avec une probabilité de 4/24 et A avec une probabilité de 2/24.

Stratégie 2 : Une autre stratégie envisageable est de s'entrenir avec les deux premiers candidats sans les garder, puis de choisir le candidat n°3 s'il est meilleur que les deux premier, et le n°4 sinon.
Dans ce cas, D sera choisi systématiquement si les premiers candidats sont AC, BC, CA ou CB. Si les premiers candidats sont AB ou BA, D sera choisi dans la moitié des cas. Sinon, c'est que D est parmi les deux premiers candidats, et donc éliminé. On en déduit alors que D sera choisi avec une probabilité de 10/24 (soit 42%). Pour C, la probabilité est de 6/24, pour B et A, elle est de 4/24.

On peut oublier la stratégie 3 consistant à ne pas sélectionner les trois premiers candidats pour ne garder que le dernier, qui fait retomber la probabilité d'embaucher D à 1 chance sur 4.

En appelant "stratégie k" la stratégie consistant à faire passer les k premiers candidats sans les garder, puis sélectionner le premier des candidats meilleur que ces k premiers, on vient de vérifier que dans le cas n = 4, la stratégie optimale est la stratégie 1. Le meilleur des candidats sera sélectionné avec une probabilité d'environ 46%.

Cas n = 5
On peut procéder à la même analyse pour le cas n = 5, en envisageant les 120 ordres possibles pour 5 candidats. Les probabilités d'obtenir le meilleur candidat, suivant les différentes stratégies envisageables, sont alors :

Stratégie 0 : p = 20 %
Stratégie 1 : p = 41.7 %
Stratégie 2 : p = 43,3 %
Stratégie 3 : p = 35 %
Stratégie 4 : p = 20 %

Bref, la meilleure stratégie consiste ici à laisser passer les deux premiers candidats.

Mais pour les valeurs plus grande ? Il existe forcément une stratégie meilleure que les autres, mais laquelle ? Et la solution est plutôt simple : même si vous devez auditionner 100 000 secrétaires, il existe toujours une stratégie permettant de trouver le meilleur avec une probabilité supérieure à 36% ! Cette stratégie, c'est la stratégie n/e : il faut laisser passer le premier tiers (36.79% des candidats, pour être un peu plus précis) des candidats, puis prendre le premier des candidats meilleurs. Et on va le prouver !

Le jeu du gogol
Le problème des secrétaires trouve ses origines dans la rubrique Mathematical Games de Martin Gardner dans le numéro de février 1960 du Scientific American. Le problème y est présenté sous la forme du "jeu du gogol" : un joueur écrit sur des feuilles des nombres quelconques, arbitrairement grands ou petits (d'où le nom du jeu : on peut y écrire des nombres aussi grand qu'un gogol, ie, 10100), le but étant pour l'autre joueur de les retourner successivement, mais de s'arrêter sur le plus grand d'entre eux. La question de la stratégie optimale à suivre pour le deuxième joueur revient à résoudre le problème des secrétaires.  La solution arrivera dans la même rubrique du magazine, le mois suivant. On retrouvera plus tard le même problème sous le nom de "problème du mariage" (un Don Juan fait défiler des candidate pour son mariage, jusqu'à faire un choix), ou sous d'autres appellations tout aussi sexistes (problème de la dot, problème du concours de beauté, ...).

Les origines du problème semble cependant remonter au XVIIe siècle, après que l'astronome allemand Johannes Kepler a perdu sa première femme à cause du choléra. Bien décidé à en trouver une nouvelle, il a cherché à ne pas faire la même erreur que pour son premier mariage, qui lui avait été arrangé. Pour ce faire, il a consacré deux ans de sa vie à chercher la femme idéale, et 11 ont répondu à l'appel. De nombreuses lettres de Kepler relatent son processus de décision pas tout à fait au point. Le problème se termine bien : il finira par choisir la cinquième, ils se marièrent et eurent beaucoup (7) d'enfants.
En fait, Kepler n'a pas réellement inventé le problème des secrétaires (la plupart des hypothèses du problème ne sont pas respectées, puisqu'il s'est autorisé à revenir sur ses choix), mais il a quand même énoncé le premier problème d'arrêt optimal, en inventant au passage le principe du speed-dating (qui dure deux ans).

Cas général
Revenons au problème général, avec n secrétaires. Les informations que l'on a à notre disposition limitent pas mal les différentes stratégies possibles. En fait, les seules stratégies envisageables sont les stratégie k (k ∈ [0 ; n-1]) : on interroge les k premiers candidats pour se donner une idée de leur niveau en les rejetant systématiquement, puis, parmi les n-k candidats suivants, on choisit le premier à être meilleur que les k premiers. Reste à savoir quelle est, en fonction de n, la valeur de k idéale.

Notons j la position de ce mystérieux candidat meilleur que les autres. La probabilité que j soit une valeur fixée à l'avance est de 1/n.
Si j ≤ k, alors le candidat n°j sera ignoré, et donc, non choisi.
Si j = k+1, c'est que le meilleur candidat arrive pile au bon moment : il est choisi.
Si j ≥ k+2, le candidat n°j sera sélectionné seulement s'il n'y a pas de candidat opportuniste (meilleur que les k premiers) entre la position k+1 et j-1. Ceci n'arrivera qu'avec une probabilité de k/(j-1) : la probabilité que le meilleur des (j-1) premiers soit dans les k premiers (formellement, c'est la probabilité de choisir le j-ième candidat sachant que c'est le meilleur).

La probabilité que la stratégie k permette de trouver le meilleur candidat est donc :

ProbaSecretaire1

En simplifiant :

ProbaSecretaire2

Pour des petites valeurs de n, on peut calculer ces probabilités pour toutes les valeurs de k afin de déterminer la stratégie optimale :

Pour n = 3, P est maximal pour k = 1 (P = 0.5)
Pour n = 4, P est maximal pour k = 1 (P = 0.458)
Pour n = 5, P est maximal pour k = 2 (P = 0.433)
Pour n = 6, P est maximal pour k = 2 (P = 0.428)
Pour n = 7, P est maximal pour k = 2 (P = 0.414)
Pour n = 8, P est maximal pour k = 3 (P = 0.410)
Pour n = 9, P est maximal pour k = 3 (P = 0.406)
Pour n = 10, P est maximal pour k = 3 (P = 0.398)
En poursuivant les calculs, on peut se convaincre que n/k tend vers e.

Pour des valeurs de n plus élevées, on va plutôt déterminer une valeur approchée de Pn,k. Un peu de calcul intégral permet de voir que

ProbaSecretaire3

La probabilité de succès de la stratégie k est donc environ égale à Pn,k = (k/n) ln(n/k). Il n'y a plus qu'à chercher pour quelle valeur de k cette probabilité est maximale. 
Posons x = (k/n). La fonction f(x) = x ln(1/x) est maximale (si si, je vous l'assure) lorsque x = 1/e ≈ 0.368, ce qui signifie que la probabilité est maximale quand le rapport entre k et n vaut approximativement 36.8 %.
La meilleure stratégie, pour un nombre de candidat n, est donc la stratégie n/e. Cette stratégie offre une probabilité de succès valant f(1/e) = 1/e ≈ 0.368.

Il y a des tas d'autres problèmes d'arrêt optimal, comme celui du jeu d'Arthur "à prendre ou à laisser". Puisqu'il paraît que le jeu revient à la télé à la rentrée, ça me fera une bonne excuse pour faire d'autres articles sur le sujet !


Sources :
Who solved the secretary problem, Thomas S. Ferguson

Illustration : Queue

Posté par El Jj à 10:00 - Commentaires [5] - Permalien [#]
Tags : , ,

13 avril 2014

La dualité. Mesdames et messieurs.

Il n'y a pas que les physiciens quantiques et les philosophes qui ont le monopole de la dualité. Les mathématiciens ont aussi leur mot à dire, et ils ne se sont pas privés : dual d'un polyèdre, dual d'un graphe, dual d'un espace vectoriel, dualité de Poincaré...

Ma dualité préférée est celle de la géométrie projective, le domaine de la géométrie qui étudie les notions de perspectives. Cette dualité permet sans effort de fabriquer plein de nouveaux théorèmes de géométrie. Mais pour cela, il faut comprendre dans ses très grandes lignes la géométrie projective, en admettant ses deux axiomes suivants :

  1. Par deux points distincts passe toujours une droite (et une seule).
  2. Deux droites distinctes se coupent toujours en un point (et un seul).

Le premier axiome, on le retrouve dans notre bonne vieille géométrie euclidienne, il ne va pas nous étonner. Par contre, le deuxième axiome a l'air manifestement faux, puisque deux droites parallèles ne se coupent a priori en aucun point. Mais ça, c'était avant : en géométrie projective, des droites parallèles se coupent quand même, mais en un point "à l'infini", sur la ligne d'horizon.

En fait, ces deux axiomes peuvent tout les deux se résumer sous la forme :

  • Deux machins distincts se schtroumpfent toujours en un truc

Ces machins-trucs que sont les droites et les points sont en quelque sorte en dualité : en les inversant dans un axiome, on obtient l'autre.

Mais on peut faire encore plus fort. Partons de l'idée qu'un plan, c'est juste un ensemble de droites et des points. Alors on peut imaginer un nouvel espace où l'on appellerait "points" les droites du premier espace, et inversement (on se moque de savoir à quoi ressemble ce plan, ce n'est pas la question qui nous intéresse). Ce nouveau plan, on peut l'appeller "dual" du premier.
Mais ce plan dual vérifie toujours les deux axiomes de départ : il y a de bonnes raisons à le considérer comme un plan projectif comme les autres...

En fait, on peut mathématiser proprement la construction de ce plan projectif dual ; en le faisant, on s'aperçoit qu'il ressemble étrangement au plan de départ. Du coup, puisque ces objets passent au dual, on peut démontrer que les propriétés qui les définissent aussi.

Par exemple :

  • Un point P du plan devient une droite (p) du dual ; une droite (d) du plan devient un point D du dual
  • Dans le plan, deux droites (d) et (e) se coupent en un point P
    => dans le dual, deux points D et E forment une droite (p)
  • Dans le plan, trois points alignés P, Q et R forment une droite (d)
    => dans le dual, trois droites concourantes (p), (q) et (r) forment un point D

Plan_et_son_dual
Une configuration du plan : trois droites (d), (e) et (f) concourantes en P, et trois points P, Q et R alignés sur (d).
La même configuration dans le dual : trois points D, E et F alignés sur (p), et trois droites (p), (q) et (r) concourantes en D.

Du coup, si un théorème de géométrie ne fait appel qu'à des notions d'alignements de points ou de concourances de droites, on peut les dualiser afin d'obtenir un nouveau théorème. C'est l'outil parfait pour doubler le nombre de théorèmes existants ! Place aux exemples !

Le théorème de Pappus
Parmi les théorèmes de géométrie injustement méconnus, il y a le théorème de Pappus (que l'on doit à Pappus d'Alexandrie) :

Théorème de Pappus :
Soit A, B et C trois points distincts alignés sur une droite (d),
soit A', B' et C' trois points distincts alignés sur une droite (d'), 
Notons (p)=(AB'), (p')=(A'B), (q)=(AC'), (q')=(A'C), (r)=(BC') et (r')=(B'C)
Alors, les points E = (p')∩(p'), F = (q)∩(q') et G = (r)∩(r') sont alignés

Pappus

Ce théorème peut se dualiser, en inversant "droite" et "point", et en inversant "concourant" et "alignés". On obtient alors un tout nouveau théorème :

Théorème dual de Pappus : 
Soit (a), (b) et (c) trois droites distinctes concourantes en un point D, 
Soit (a'), (b') et (c') trois droites distinctes concourantes en un point D', 
Notons P=(a)∩(b'), P'=(a')∩(b), Q=(a)∩(c'), Q'=(a')∩(c)R=(b)∩(c'), R'=(b')∩(c)

Alors, les droites (E) = (PP'), F=(QQ') et G=(RR') sont concourantes

 Pappus_dual

Ce théorème est loin d'être aussi élégant que son dual, mais il a le mérite d'exister. (Bon, en réalité, il décrit exactement la même configuration que dans le théorème de Pappus !...)

Le théorème de Desargues
Le théorème phare de la géométrie projective, c'est le théorème de Desargues, conséquence de celui de Pappus. On le doit au français Girard Desargues, que l'on peut considérer comme le père de la géométrie projective. Il indique :

Théorème de Desargues (*)
Soit deux triangles (non aplatis) ABC et A'B'C'
Si les droites (AA'), (BB') et (CC') sont concourantes
alors les points P = (AB)∩(A'B'), Q = (AC)∩(A'C') et R = (BC)∩(B'C') sont alignés

Desargues

Encore une fois, le passage au dual permet de fabriquer un nouveau théorème. Enfin, presque nouveau, puisque ce n'est autre que la réciproque du théorème précédent. La seule différence est la surcomplexification inutile de son énoncé...

Réciproque du théorème de Desargues
Soit deux triangles (non aplatis) de côtés (a), (b) et (c), et de côtés (a'), (b') et (c') 

Si les points (a)∩(a'), (b)∩(b') et (c)∩(c') sont alignés
alors les droites (p) = (ab;a'b'), (q) = (ac;a'c') et (r) = (bc;b'c') sont concourantes
(en notant (ab;a'b') la droite passant par ab=(a)∩(b) et a'b'=(a')∩(b'))
Desargues_dual

 

Le théorème de Pascal
Un autre théorème qui passe parfaitement au dual est celui de l'hexagramme mystique de Pascal, qui parle de coniques (ellipses, hyperboles, paraboles, ...) :

Théorème de Pascal
Soit A, B, C, A', B' et C' six points distincts sur une conique
Notons (p)=(AB'), (p')=(A'B), (q)=(AC'), (q')=(A'C), (r)=(BC') et (r')=(B'C)
Alors, les points E = (p)∩(p'), F = (q)∩(q') et G = (r)∩(r') sont alignés

Pascal

On peut voir que ce théorème est une généralisation de celui du théorème de Pappus, puisqu'un couple de droites n'est qu'un cas particulier de conique dégénéré.

L'hexagramme de Pascal peut également être dualisé, en ajoutant deux nouvelles correspondances entre le plan et son dual :

  • Une conique dans le plan reste une conique dans le dual
  • Un point sur une conique dans le plan devient une droite tangente à une conique dans le dual

Théorème de Brianchon
Soit (a), (b), (c), (a'), (b') et (c') six droites distinctes tangente à une conique
Notons P=(a)∩(b'), P'=(a')∩(b), Q=(a)∩(c'), Q'=(a')∩(c), R=(b)∩(c'), R'=(b')∩(c)

Alors, les droites (E) = (PP'), F=(QQ') et G=(RR') sont concourantes


Pascal_dual

Le théorème de Pascal est vrai quel que soit l'ordre des points A, B, C, A', B', C' que l'on considère. La droite orange obtenue dépend donc de l'ordre des points. Puisqu'il y a 60 façons de dessiner un hexagone à partir de 6 points, on peut obtenir une famille de 60 droites, les droites de Pascal. Cet énoncé passe au dual, ce qui entraîne l'existence de 60 points particuliers, les points de Kirkman (points de concourance des droites de Pascal).

Droites_de_Pascal
(Une partie de) Les 60 droites de Pascal et les 60 points de Kirman
Oui, c'est n'importe quoi.


(*) Note de bas de page : à première vue, le théorème de Desargues n'est qu'un amas sans fond ni forme de points et de cercles. Pour le visualiser (et le mémoriser), on peut penser à cette figure : il faut imaginer que ABC et A'B'C' sont des coupes transversales parallèles d'une même pyramide. Ces coupes étant parallèles, les côtés se prolongent et se coupent deux à deux sur la même ligne d'horizon : ces points de concours sont donc alignés.


Sources :
Wikipedia, essentiellement
Pascal Lines, sur MathWorld

Posté par El Jj à 10:00 - Commentaires [6] - Permalien [#]
Tags : , , , ,

06 avril 2014

Mokshû Patamû

Après une partie contre des banquiers véreux qui n'ont jamais voulu échanger votre Faubourg Saint-Honoré contre leur Boulevard Malesherbes, vous avez choisi de renoncer définitivement à ouvrir cette boîte de ce jeu de l'enfer qu'est le Monopoly. Mais à quoi jouer avec beau-papa en ce dimanche après-midi ? Une partie de Scrabble ? des colons de Catanes ? des Aventuriers du Rail ? Non ! Revenons aux bases, et ouvrons la boîte pleine de poussière qui renferme un vénérable plateau de Serpents et échelles !

Bon, finalement, vous avez débuté le jeu, et vous n'avez maintenant plus qu'une seule envie : que cela se termine ! Mais au fait, combien de temps dure en moyenne une partie de Serpents et échelles ?!

320px-Snakes_and_ladders2

Pour les quelques-uns qui n'ont jamais perdu des heures à tomber en boucle sur la même gueule de serpent, voici ce qu'il faut savoir sur ce jeu :

  • Le plateau de jeu est composé de 100 cases, numérotées de 1 à 100.
  • Les joueurs, chacun leur tour, lancent le dé, puis déplacent leur pion du nombre de cases indiqué.
  • Des serpents et des échelles sont disséminés sur le plateau de jeu. Lorsqu'on arrive au pied d'une échelle, on la monte ; inversement, lorsque l'on tombe sur une tête de serpent, on descend jusqu'à sa queue.
  • Le premier joueur à atteindre (ou dépasser) la 100e case est déclaré vainqueur, et félicité pour sa chance au jeu.
  • A l'origine, ce jeu est une métaphore indoue du chemin spirituel pour atteindre le Nirvana.

De nombreuses variantes de plateaux de jeu existent, je vais me baser sur la version Hasbro, dont le plateau comporte 9 échelles et 7 serpents, et qui ressemble à ceci :

Plateau

Au nom de la loi de X
En détaillant un peu le plateau, on peut voir que la centième case peut être atteinte en seulement 7 lancés de dés, en empruntant 3 échelles (l'échelle 1 -> 38, la 51-> 67 et la 71 -> 91). Cependant, il n'y a pas de nombre maximum de coups permettant d'atteindre la dernière case. Heureusement, ce cas est presque impossible.

Finalement, quel est le temps moyen permettant d'atteindre cette centième case ? Les chaînes de Markov sont là pour nous aider à appréhender la situation. Pour comprendre, observons ce qu'il se passe lancé par lancé.

Au début du jeu, les pions sont en dehors du plateau. Au premier lancé de dé, 6 cases sont atteignables (38 (si on obtient 1 au dé, grâce à l'échelle), 2, 3, 14 (4 au dé), 5 ou 6). La probabilité d'atteindre chacune de ces cases après le premier lancé de dé est donc de 1/6 (≈0.17).

proba_ees_lance_1

Pour ce qui est du deuxième lancé de dé, il faut envisager les 6 cas précédents :

  • depuis la case 38, on peut atteindre 39, 40, 41, 42, 43, 44
  • depuis la case 2, on peut atteindre 3, 14, 5, 6, 7, 8
  • depuis la case 3, on peut atteindre 14, 5, 6, 7, 8, 31
  • depuis la case 14, on peut atteindre 15, 6, 17, 18, 19, 20
  • depuis la case 5, on peut atteindre 6, 7, 8, 31, 10, 11
  • depuis la case 6, on peut atteindre 7, 8, 31, 10, 11, 12

Puisqu'il y a 36 façons de lancer deux fois le dé, chacune de ces cases a pour probabilité 1/36 d'être atteinte par le chemin indiqué. On peut alors remarquer, par exemple, que :

  • il n'y a qu'une seule façon d'atteindre la case 42 en deux lancés de dé : sa probabilité est de 1/36 (≈0.03).
  • il y a 4 façons d'atteindre la case 6 en deux lancés de dé : la probabilité de cette case est donc de 4/36 (≈0.11).

proba_ees_lance_2

On pourrait suivre le même raisonnement pour le troisième lancé de dé, mais le décrire entièrement serait trop long. Heureusement, les matrices vont venir prendre le relai. Pour cela, on a besoin de la matrice de transition M du plateau, qui donne la probabilité d'atteindre une case sachant que l'on est sur une autre case.

Pour être plus précis, le coefficient de la ligne I et de la colonne J correspond à la probabilité d'atteindre la J-ième case sachant que l'on se trouve sur la I-ème. A titre d'exemple, le coefficient ligne 2 colonne 3 est 1/6 car il y a une chance sur 6 d'atteindre la case 3 en partant de la case 2.

matrice_ligne23_echelles_et_serpents

La matrice finale M contient donc une très grand nombre de 0, beaucoup de 1/6 et quelques valeurs un peu plus grandes (le coefficient ligne 52 colonne 53 vaut 2/6, car il y a deux façons d'atteindre la case 53 depuis la 52). Graphiquement, la matrice ressemble à ceci.

matrice_echelles_et_serpents

Cette matrice nous permet de calculer la probabilité de chacune des cases pour un nombre de lancé choisi, en utilisant le fait que

U(n+1) = U(n) × M
où U(n) la matrice-ligne qui donne la probabilité de chacune des 100 cases lors du n-ième lancé de dé.

On peut notemment calculer la distribution des probabilités pour 6 ou 7 lancés, ce qui confirme la remarque initiale : il est théoriquement possible de gagner en 7 lancés de dés, mais la probabilité est excessivement faible (0.2 %). Après 7 lancés, on se retrouve plus facilement en case 26...

proba_ees_lance_6_7

Le temps d'en finir
Tout ceci ne nous dit pas encore combien de temps on doit se farcir les serpents et les échelles pour en finir avec le jeu. Il ne reste en fait plus qu'à chercher la probabilités d'atteindre la 100e en exactement n lancés de dés, pour toutes les valeurs de n. Aussitôt dit, aussitôt fait :

proba_case100

Ce graphique (et quelques calculs autour des données) nous apprend des choses essentielles :

  • Le plus probable est d'atteindre la centième case en 20 lancés de dés
  • En moyenne, il faut 36 lancés de dés pour gagner
  • Il y a 50% de chances de finir en moins de 29 mouvements
  • Il y a 98% de chances d'en finir en moins de 100 mouvements

Oui, mais...
D'aucun me diront que, dans les règles officielles du jeu, il faut atteindre exactement la case 100, sinon la règle "tu dépasses, tu recules" s'applique. Ca change tout !

Qu'il en soit ainsi, je modifie la matrice tout de suite :

matrice_echelles_et_serpents_2

Ce qui nous donne ce chouette graphique :

proba_case1002

En détaillant en peu les chiffres, on découvre que...

  • Le plus probable est d'atteindre la centième case en 22 lancés de dés (et la probabilité est bien plus faible que dans le cas précédent)
  • En moyenne, il faut 43 lancés de dés pour gagner
  • Il y a 50% de chances de finir en moins de 34 mouvements
  • Il y a 94% de chances d'en finir en moins de 100 mouvements

Mouais... Finalement, cette règle supplémentaire a surtout pour effet de rallonger la traîne de la courbe : le cas le plus probable ne change pas, mais les événements très rares le deviennent un petit peu moins.


 

Sources :
Analysis of Chutes and Ladders, sur DataGenetics

Images :
Snakes_and_ladders
 

Posté par El Jj à 10:00 - Commentaires [5] - Permalien [#]
Tags : , , , ,

30 mars 2014

Made in Sinaï

Le prix Abel 2014 a été annoncé le 26 mars dernier, et l'heureux lauréat est russe ! C'est donc le mathématicien (et un peu physicien) Iakov Sinaï qui décroche cette année le prix Nobel des maths (parce que, non, la médaille Fields n'est pas l'équivalent d'un Nobel, c'est encore plus prestigieux). Il est récompensé pour l'ensemble de son œuvre : des travaux sur les systèmes dynamiques, sur la théorie ergodique et en physique mathématique. Son nom restera surtout associé aux systèmes dynamiques, grâce au billard de Sinaï et à l'entropie de Sinaï-Kolmogorov. A quoi ressemblent ces bêtes là ? Quelques éléments de réponse.

174px-Yakov_G_Sinai_photo
Iakov (Yakov ?!) Sinaï

Le billard de Sinaï
On appelle système dynamique un processus évoluant au cours du temps qui ne fait absolument pas intervenir le hasard (autrement dit, déterministe). L'objet préféré des gens qui étudient les systèmes dynamiques, c'est le billard. Enfin, pas n'importe quel billard : un billard sans trou et qui se joue avec une seule boule (infiniment fine). Une fois lancée, la boule ne s'arrête plus, et suit les loi de la physique lorsqu'elle rebondit sur les parois. En fait, le billard des mathématicien est surtout une façon simple de modéliser le comportement d'un particule d'un gaz.

Dans un tel billard, une fois que l'on connaît la position précise de la balle et sa direction initiale, les lois de la physique nous permettent de prédire avec exactitude la trajectoire qu'elle suivra. Cette trajectoire est donc parfaitement déterministe.

Billard_1
Je lance ma boule selon la direction bleue : elle rebondit, tout est normal.

Si je modifie un peu la position ou la direction initiale de la balle, la trajectoire change. Mais pas tant que ça. En déplaçant la balle et en conservant la même direction, la balle aura une trajectoire parallèle à sa trajectoire initiale ; si c'est la direction que l'on change, la balle déviera de plus en plus de sa trajectoire initiale avec le temps, mais rien de très inquiétant.

Billard_non_chaotique
à gauche, un changement de position initiale
à droite, un changement de direction initiale
De petits changements entraînent de petites déviations

Par contre, quand Sinaï joue au billard, il n'hésite pas à rajouter un gros cylindre en plein milieu de sa table. La physique permet toujours de prédire la trajectoire de la balle, ce système dynamique est toujours parfaitement déterministe.

Billard_Sinaipng
Le véritable "billard de Sinaï" est carré, mais l'idée est la même

La grosse différence d'avec le premier billard, c'est que la trajectoire devient difficile à prévoir lorsque l'on modifie un peu les conditions initiales. En déplaçant, même légèrement, la position de départ de la balle, la trajectoire devient très rapidement complètement différente. Même remarque si l'on modifie un peu sa direction.

Billard_Sinai_chaotique
Avec un petit changement des conditions initiales, la trajectoire change du tout au tout.

Bien que les trajectoires soient complètement prévisible, puisque déterministe, il est en fait impossible de les prévoir sans passer par l'essai. On peut alors qualifier ces trajectoires comme "chaotique" : une petite modification des conditions initiales change très rapidement l'aspect global de la trajectoire. Il existe de très nombreux exemple de systèmes chaotiques, je vous invite plutôt à écouter le dernier épisode de Podcast Science sur le sujet.

Assez paradoxalement, bien qu'il soit impossible de prévoir le comportement d'une trajectoire sans connaître précisément ses conditions initiales, il est quand même possible d'y prévoir des choses. Par exemple, (sauf cas particuliers), les trajectoires seront ergodiques : si on choisit un point sur le bord du billard, la balle finira forcément par passer à un moment ou à un autre près de ce point (et même, aussi près de ce point que l'on veut, si l'on accepte d'attendre longtemps).

Sinaï a en fait produit cet exemple de billard pour montrer qu'il existe un système qui soit à la fois chaotique ("d'exposant de Lyapounov positif") et ergodique, dans le cadre d'un problème sur le comportement physique du mouvement de gaz.

L'entropie de Sinaï-Kolmogorov
Finalement, certains systèmes dynamiques sont faciles à prévoir à court comme à long terme, d'autres le sont à court terme mais pas à long terme, d'autres encore ne le sont plus à moyen terme... Il faut trouver quelque chose pour mesurer tout ça ; ce quelque chose, c'est l'entropie.

Cette entropie n'a pas de rapport direct avec l'entropie des physiciens, mais plutôt avec celle des théoriciens de l'information, à travers l'entropie de Shannon. La définition de l'entropie de Shannon permet de dire qu'une suite de caractère possédant une forte entropie est riche en informations.

Par exemple, les deux phrases "six fois sept égale quarante-deux" et "6×7=42" apportent exactement la même information, mais la deuxième compte sensiblement moins de caractère que la première. La quantité d'information par caractère contenu dans la première phrase est donc très faible, par rapport à l'autre ; son entropie est donc plus petite.
Du coup, quand on commence à écrire "six fois se...", on peut sans trop se tromper penser que les caractères suivants seront "p" et "t" : il est facile de prédire le futur d'une phrase de faible entropie. C'est en s'appuyant sur cette idée que Sinaï produit une notion d'entropie pour certains systèmes dynamiques, en s'appuyant sur les travaux de Kolmogorov (son directeur de recherche).

L'entropie de Sinaï-Kolmogorov permet donc de quantifier la complexité d'un système dynamique, et offre un moyen parfait pour mesurer le chaos. Un système à forte entropie est difficile à prévoir, tout comme il est difficile de prévoir quel sera le mot suivant d'une phrase très riche en information (forte entropie, au sens de Shannon). Si l'on s'accorde à dire que le désordre est riche en information, on peut aussi la relier à l'entropie des physiciens.

Finalement, le mathématicien Iakov Sinaï s'est inspiré de la théorie de l'information pour décrire mathématiquement des systèmes dynamiques issus de la physique. Celui qui a écrit un article intitulé "Mathematicians and Physicists = Cats and Dogs ?" a en fait passé son temps a relier les deux milieux.


Sources :
Site officiel du prix Abel

Images :
Yakov G Sinai photo

Posté par El Jj à 10:00 - Commentaires [0] - Permalien [#]
Tags : , , ,

23 février 2014

Cravate club

L'info a largement été relayée dans les médias, il existerait 177 147 façons de nouer une cravate, et c'est une équipe de mathématiciens et d'informaticiens suédoise qui vient de le publier. Cette étude fait suite à une autre étude qui n'avait compté *que* 85 nouages de cravates différents. 

Mais concrètement, comment ont-ils compté tout ces nœuds de cravate ? Et quel est le rapport entre le film Matrix et cette histoire de cravates ? Détaillons un peu leur méthode.

Les 85 nœuds de Fink et Mao
Thomas Fink et Young Mao, deux physiciens anglais, sont les premiers à s'être formellement penché sur l'épineux problème du nœud de cravate en 1999. 

Pour aborder le problème, pensons cravate. Pour avoir une belle cravate, selon Fink et Mao :
- c'est la partie large de la cravate que l'on manipule
- on commence en plaçant cette partie large du côté gauche du corps (au-dessus ou en dessous de la partie fine, selon le nœud)
- on la passe alternativement au dessus et au-dessous du nœud.
- on termine en passant ce bout à l'intérieur du nœud, pour le "fermer".

La plus simple des variantes est le nœud "quatre en main", qui s'élabore en 4(+1) étapes, de la façon suivante :

Quatre mouvements pour un quatre en main

- on commence en plaçant la partie large de la cravate au-dessus et à gauche de l'autre partie (Li)
- on passe la partie large en-dessous et à droite de l'autre partie (Ro)
- on passe la partie large au-dessus et à gauche de l'autre partie (Li)
- on passe la partie large en-dessous du nœud et on la fait sortir par le col (Co)
- on passe la partie large dans le nœud de la cravate (U)

Les opérations que l'on peut finalement faire, c'est passer la partie large en-dessous (noté o) et au-dessus (noté i) de l'autre partie ; on peut, selon les situations, faire ressortir ce bout du côté droit de la cravate (R), gauche (L) ou au niveau du col (C). La dernière opération faisable, c'est celle qui consiste à passer la partie large dans le nœud de la cravate (et qui n'interviendra qu'une seule fois, à la fin) : la fermeture, notée U.

Bref, il y a 7 opérations possibles : Ro Ri Lo Li Co Ci et U. Un nœud de cravate sera alors complètement défini par une suite de ces opérations, en respectant tout de même certaines règles :

  • Règle 1 : on commence par Lo ou Li (commencer par Ro ou Ri entrainerait des nœuds miroirs, oublions-les).
  • Règle 2 : on ne peut pas faire successivement deux opérations R, L ou C identiques
  • Règle 3 : les opérations o et i doivent être alternées.
  • Règle 4 : la fermeture U n'intervient qu'à la fin, et seulement après les opérations Ro Li Co ou Lo Ri Co (car la cravate doit venir par le dessous du nœud, en passant par le côté col)

Ainsi, la succession de mouvements Lo Ri Lo Ri Co Li Ro Li Co U est tout à fait convenable (et il s'agit du nœud Grandchester, le #44 de la liste de Fink, qui requiert 9 mouvements). 

En traduisant les conditions par un graphe, on peut voir qu'une succession de mouvements qui donne un beau nœud de cravate correspond à un chemin sur le graphe ci-dessous, qui commence à D et se termine en U.

Cravate_simple

On peut alors voir qu'il y a un seul nœud faisable en 3 mouvements (Lo Ri Co U, le nœud oriental), un nœud en 4 mouvements (Li Ro Li Co U, le nœud quatre en main présenté plus haut) et 3 nœuds en 5 mouvements (les nœuds Kelvin, Nicky et Pratt). 
En notant an le nombre de nœuds faisables en n mouvements, on peut remarquer que l'on a an+2 = an+1 + 2 an. En se limitant à 8 mouvements au maximum, on dénombre alors 85 nœuds de cravate différents (le mouvement U final n'intervient pas dans le décompte).

85_noeuds

La notation WTU de Vejdemo-Johansson
Sauf qu'en 2003, toute la théorie a sauté, puisque le film Matrix Reloaded est sorti au cinéma. On ne retiendra qu'une seule chose du film : la cravate porté par Lambert Wilson, qui interprète Le Mérovingien, est nouée de façon à ce que la partie large de la cravate termine en-dessous de la partie fine ! Incroyable ! Luke Housego se dépêche de créer un tutoriel sur Internet, et baptise ce nœud le nœud Edeity.

Noeud_Merovingien
Le nœud Mérovingien, ou nœud Edeity, porté avec classe par Lambert Wilson
Séquence : Lo Ci Lo Ri Co Ri Lo Ci U

En 2008, c'est un nouveau nœud qui apparaît sur Youtube, le nœud Eldredge. Tous les tabous de la cravate sautent : ce n'est pas la partie large de la cravate qui est manipulée mais sa partie fine, celle-ci passe plusieurs fois dans le nœud et, ultime affront, elle termine sa course dans le col de son porteur !

Noeud_eldredge
Le nœud Eldredge
Séquence : Li Ro Ci Lo Ri Co Li Ro U Ci Lo Ci Ro U

Les règles imposées par Fink et Mao sont clairement trop restrictives, en particulier la règle n°4. Pour englober davantage de nœuds (dont le nœud Eldredge), disons plutôt que :

  • Règle 4' : le mouvement U peut intervenir n'importe quand, même après un mouvement L ou R, à condition qu'au moins deux mouvements au moins le précède. De plus, sous certaines conditions d'existence, on autorisera le mouvement UU (ou U²) consistant à rentrer la cravate dans deuxième couche du nœud, et, de manière générale, Uk qui consiste à rentrer la cravate dans la k-ième couche du nœud. Un tel mouvement est possible qu'après au moins 2k autres mouvements.

Il faut alors adapter les règles 2 et 3, en précisant qu'un mouvement U n'influence pas le fait que deux mouvements R, L ou C ne peuvent se succéder à l'identique, même chose pour o et i.

D'ailleurs, la notation o et i est complètement superflue. En effet, une fermeture U ne peut exister qu'après un mouvement o, où la cravate passe sous le nœud. Du coup, l'alternance o/i permet de retrouver les directions d'une séquence RLC de mouvements donnée.

Par exemple, la suite de mouvements du nœud Trinity est LCLRCRLCURLU. Le L qui précède le dernier U ne peut être qu'un mouvement de type Lo, et donc, en remontant, on peut retrouver que le mouvement initial est Li :

Noeud_Trinity
Le nœud Trinity (aucun rapport avec Matrix)
Li Co Li Ro Ci Ro Li Co U Ri Lo U

On peut donc se restreindre à seulement 4 symboles pour décrire le nouage de la cravate : L, R, C et U.
Enfin... Pas tout à fait, puisque l'on a pris pour hypothèse que l'on commence toujours à gauche (mouvement L). Il est donc inutile de le noter dans la liste. Comme deux mouvements L, R et C ne peuvent se succéder à l'identique, on peut se contenter de dire si le prochain mouvement est un mouvement dans le sens des aiguilles d'une montre (noté T - comme Turnwise) ou dans le sens inverse (noté W - comme widdershin).

  • T : tourner dans le sens des aiguilles d'une montre (sens indirect) : R -> L, L -> C ou C -> R.
  • W : tourner dans le sens inverse des aiguilles d'une montre (sens direct) : L -> R, R -> C ou C -> L.

Par exemple, la suite de mouvement WTWTWUTTU du nœud Floating Spiral débute, comme tous les nœuds, par L. Puisque le premier mouvement est de type W, la région suivante est R. On peut ainsi en déduire la séquence complète :

Noeud_Floating_Spiral
Nœud Floating Spiral
Li Ro Li Ro Li Ro U Li Co U

Les 177 147 nœuds de Vejdemo-Johansson
Il est temps de dénombrer les différents nœuds de cravate. Pour cela, l'équipe de Vejdemo-Johansson a remarqué que les nœuds de cravate de 1ere espèce (où la cravate ne peut passer que sous la couche la plus récente crée au dessus du nœud) obéissent toujours au schéma ⟨préfixe⟩ ⟨développement⟩ ⟨fermeture⟩, sachant que

  • le préfixe peut être T ou W (ou rien).
  • le développement est constitué d'une suite (pouvant être vide) de paires (TT, TW, WW ou WT) et de fermetures (TTU ou WWU)
  • la fermeture finale est obligatoire (TTU ou WWU).

Ainsi, WWU et TTU sont des nœuds possibles (correspondant respectivement à un nœud de cravate oriental, et à un nœud où la cravate est mise comme une écharpe autour du cou...). Le nœud T.WW.WW.WWU (Windsor) correspond lui aussi parfaitement à cette description.

Ce schéma peut alors se traduire par un graphe, où les nœuds de cravates valides correspondent à un chemin débutant et terminant sur la case centrale :

Graphe_cravates

Avec un peu de théorie des graphes, on peut remarquer que le nombre de nœuds de 1ere espèce de longueur n et ne comportant qu'une seule fois l'opération U est de 2n-1. En se limitant à au plus 11 mouvements (nécéssaires pour Eldredge), on compte un total de 2048 nœuds de référence fondamentalement différents, auquels s'ajoutent les variantes comptant plusieurs fois l'opération U.

On peut alors les répartir en trois classes, selon la position finale de la cravate (CU, LU ou RU), les nœuds classiques recensés par Fink et Mao sont alors ceux de la première classe, (où la différence entre le nombre de W et de T est de 2 modulo 3).

2046_noeuds
Répartition des 2046 nœuds de référence (Le U final ne rentre pas de le décompte des mouvements)

Mais ces 2046 nœuds et leurs variantes ne représentent qu'une petite portion des 177 147 différents nœuds de cravate recensés. Il faut en effet ajouter toutes leurs variantes de fermetures pour obtenir les nœuds de seconde espèce. Les conditions d'existence de ces variantes s'appuient sur des considérations sur le nombre de W et T précédant les différentes fermetures U. A titre d'exemple, TTWTUU est une séquence valide de 2nde espèce, même si elle n'obéit pas au schéma présenté plus haut.

Au final, les 2046 nœuds engendrent 177 147 nœuds de cravate, ce qui est prodigieusement... beaucoup. Ce que la théorie ne dit cependant pas, c'est le caractère esthétique de chacun de ces nœuds, point qui avait été abordé par Fink et Mao. Du coup, il est aujourd'hui impossible de savoir si nous sommes passé à côté d'un nouage de cravate inédit mêlant élégance et originalité. En attendant, vous pouvez toujours tenter de reproduire l'un des nœuds obtenu à partir du générateur !


Sources :
D. Hirsch, M. L. Patterson, A. Sandberg, M.Vejdemo-Johansson, More tie than we though (d'où provient le dernier graphe)
M.Vejdemo-Johansson, Random tie knots
T. Fink, Encyclopedia of tie knot - donne la liste des 85 nœuds de Fink et Mao
T. Fink, Y. Mao, Designing tie knots by random walks (d'où provient la première illustration)

Posté par El Jj à 10:00 - Commentaires [4] - Permalien [#]
Tags : , , , ,



  1  2  3  4  5    Fin »