19 mai 2013
[#] Le seigneur des anneaux factoriels
Je me suis toujours dit que je pourrais écrire une épopée d'Héroic Fantasy que j'appellerai "le seigneur des anneaux factoriels". L'histoire d'anneaux de pouvoirs, répartis entre les rois Elfes, les seigneurs Nains et les Hommes mortels ; l'histoire de l'Anneau unitaire forgé par Saurond, pour les gouverner tous. Une communauté se formerait, pour débarasser la Terre des Milieux de l'Anneau unitaire, un groupe comprenant quatre Hobbits géomètres, deux Hommes analystes, un nain algébriste, un elfe probabiliste et un magicien logicien. On y croiserai les Spectres de l'Anneau, l'Armée des morphismes ou les Tanj-Ent, créatures de la forêt.
Je suis pas convaincu de vendre autant que Tolkien.
21 avril 2013
[#] Itérons !
Itérer une fonction : voilà un plaisir simple que l'on a tous fait dès lors que nous avons eu entre les mains notre première calculette ! On écrit un nombre, on écrit "+1", puis on martèle la touche [=] pour voir les nombres défiler. Le premier arrivé à 1000 sera prem's à la Master System !
Très vite, on essaye les autres touches de la calculatrice. Répéter la touche [X²] donne des nombres de plus en plus grands tandis que la touche [√X] donne des nombres de plus en plus proches de 1. Les touches [-x] et [1/x] ne sont vraiment pas amusantes, puisqu'elles alternent entre les deux mêmes nombres, alors que les touches [sin] et [cos] donnent des résultats bizarres. Comme on ne comprend pas vraiment le sens de toutes ces touches, on ne sait jamais ce que l'on va obtenir, la surprise est donc toujours au rendez-vous.
Toi aussi, lecteur, tambourine la touche [=] pour voir les nombres se transformer
La sagesse arrive avec l'âge et on arrête de taper bêtement sur sa calculatrice. On préfère inventer des théorèmes qui prédisent ce qui va arriver quand on le fera. Un tel théorème, c'est un théorème de point fixe, et c'est sans doute pour ça qu'il en existe autant (Wikipédia en recense 16, et c'est seulement ceux qui portent un nom particulier).
Le point fixe d'une fonction f est une solution de l'équation f(x)=x. Bien souvent, pour trouver cette solution, il suffit d'itérer la fonction f en partant de n'importe quel point de départ. Dans la théorie, un théorème de point fixe sert surtout à savoir si c'est une bonne idée a priori d'itérer la fonction. Dans la pratique, on commence par essayer de répéter la fonction, on ne regarde que dans un deuxième temps elle était bien k-lipschitzienne...
Itérons des fonctions
Par exemple, que se passe-t-il si on itère la fonction cosinus ? Pour cela, on part d'un nombre, n'importe lequel (disons, 1), et on calcule son cosinus. On obtient :
cos(1) = 0.5403023058681398
Si maintenant, on applique à nouveau la fonction à son résultat, on trouve
cos(0.5403023058681398) = 0.8575532158463934
On peut maintenant marteler la touche cos et observer ce qu'il se passe :
cos(0.8575532158463934) = 0.6542897904977791
cos(0.6542897904977791) = 0.7934803587425656
...
après beaucoup trop d'itérations...
...
cos(0.7390851332151607) = 0.7390851332151607
La suite finit par se stabiliser autour du nombre 0.739, qui n'est autre que la solution de cos(x) = x. C'est en itérant la fonction que l'on a pu trouver une valeur (approchée) du point fixe de cos(x) ; c'est d'ailleurs la seule façon de le faire.
Itérons des opérateurs
Puisqu'il est amusant d'itérer des fonctions, on peut aussi itérer des fonctions de fonctions. Par exemple, que se passe-t-il si on itère la transformation ci-dessous en partant de la fonction f:x ↦ x ?
La réponse, c'est un point fixe de l'opérateur, une fonction particulièrement anguleuse :
La fonction que l'on obtient après une infinité d'étapes (bien que la cinquième itération en soit une bonne approximation), c'est la courbe de Bolzano-Lebesgue, un exemple de courbe continue partout mais dérivable nulle part.
I. F. S.
Faisons encore mieux : itérons des transformations d'images, avec les IFS (Système de fonctions itérées). On part d'une image et on crée plusieurs sous-images identiques à la première.
Partons de la transformation suivante, où l'image est rapetissée et dédoublée :
En la répétant suffisamment de fois (ici, 7 fois), on obtient une nébuleuse de smileys particulièrement esthétique !
Ces transformations sont surtout une excellente façon de produire des images fractales, puisque l'auto-similarité est au coeur de la procédure.
Cette fractale a été obtenue par itération de la transformation représentée à droite qui transforme le carré blanc en chacun des parallélogrammes rouges
Dans ce titre, on peut compter exactement vingt-neuf voyelles et quarante-cinq consonnes
Comment compléter la phrase "Cette phrase auto-référente compte ___ A, ___ B, ___ C, ___ D et ___ E" pour qu'elle soit vraie ? Encore une fois, les itérations vont nous sauver, bien qu'aucun théorème de point fixe ne peut nous garantir le résultat. Cette méthode est due à Douglas Hofstadter, auteur du célèbre Gödel, Escher, Bach.
Commençons donc par une phrase ostensiblement fausse :
Cette phrase auto-référente compte quarante-deux A, zéro B, quarante-deux C, quarante-deux D et quarante-deux E !
Puis, on remplace les nombres affichés par les nombres réels :
Cette phrase auto-référente compte onze A, un B, trois C, cinq D et dix-neuf E !
La phrase n'est toujours pas correcte, mais rien ne nous empêche de continuer :
Cette phrase auto-référente compte trois A, un B, quatre C, deux D et douze E !
Cette phrase auto-référente compte quatre A, un B, trois C, trois D et treize E !
Cette phrase auto-référente compte quatre A, un B, trois C, un D et treize E !
Cette phrase auto-référente compte quatre A, un B, trois C, un D et treize E !
Après quelques itérations, on finit par tomber sur une phrase authentique. Le mauvais côté de cette méthode, c'est que très souvent, elle finit par boucler sans trouver de point fixe... Et ça peut arriver alors même qu'il existe une solution :
Cette phrase auto-référente compte plusieurs A, un B, quelques C, un D et plein de E !
Cette phrase auto-référente compte trois A, un B, trois C, deux D et quinze E !
Cette phrase auto-référente compte trois A, un B, trois C, deux D et douze E !
Cette phrase auto-référente compte trois A, un B, trois C, trois D et douze E !
Cette phrase auto-référente compte trois A, un B, trois C, deux D et onze E !
Cette phrase auto-référente compte trois A, un B, trois C, deux D et douze E !
Avec cette méthode, on peut relativement facilement construire des phrases qui n'ont rien à cacher (à l'heure de la transparence...), comme celle-ci, œuvre de l'oulipo :
Huit a, un b, cinq c, six d, dix-huit e, trois f, six g, cinq h, vingt-six i, un j, un k, trois l, un m, vingt-quatre n, huit o, sept p, sept q, neuf r, quinze s, vingt-deux t, vingt u, six v, un w, dix x, un y, deux z, cinq traits d'union, une apostrophe, trente virgules, soixante-quatre espaces, et un point final.
I XKCD
En janvier 2012, xkcd publiait ceci :
Comment a-t-il obtenu cette image ? Avec des itérations, sans doute !... Le principe est toujours le même : on part d'une image qui n'a rien à voir, et décrit ce qu'il s'y passe pour fabriquer une nouvelle image. En réitérant le processus suffisament de fois, on arrive à une version publiable :
Première itération, obtenue à partir de l'image ci-dessus...
Après de nombreuses itérations, on obtient cette version un peu cheap du strip d'xkcd...
Sources :
Glito IFS fractals, pour dessiner des fractales par IFS
Ce titre contient quatre 'a', un 'b', [...] un 'y' et quatre 'z', de Jacques Pitrat [rtf]
07 avril 2013
[#] Deligne de vie
Le mois dernier, l'Académie norvégienne des sciences et des lettres a remis son traditionnel prix Abel (le prix Nobel des maths) au mathématicien belge Pierre Deligne. L'algébriste n'en est pas à son coup d'essai, puisqu'il avait déjà reçu la médaille Fields (le prix Nobel des maths) en 1978, le prix Crafoord (le prix Nobel des maths) en 1988 ou le prix Wolf (pas le prix Nobel des maths) en 2008. Ce nouveau prix récompense l'ensemble de ses travaux en géométrie algébrique (en particulier, la démonstration de la conjecture de Weil), ainsi que ses retombées dans la théorie des nombres, dans la théorie des représentations et tout le toutim.
Non seulement, ce type est génial, mais en plus, il est vicompte vicomte !
En 1949, le mathématicien français André Weil formule, en s'inspirant de l'hypothèse de Riemann, plusieurs questions (assez pointues) de géométrie algébrique (domaine des mathématiques qui, à l'origine, s'intéresse aux objets géométriques par le prisme de leurs équations) : les quatre conjectures de Weil. Il se dit qu'il serait pas mal d'utiliser, pour aborder ces problèmes, des outils topologiques : la cohomologie. Des cohomologies, il en existe pléthore, mais celle réclamée par Weil fait partie de celles qui n'existe pas encore... Dans les années 1960, le français Alexander Grothendieck invente la cohomologie "étale", qui a l'air parfaite pour résoudre les conjectures de Weil. C'est effectivement le cas, puisqu'elle ont permis d'en faire tomber trois sur quatre. Pour la dernière partie, la plus difficile des quatre, ce n'est pas Grothendiek qui s'en chargera mais son étudiant, Pierre Deligne (1974), à partir des travaux de son superviseur.
Et concrètement, de quoi parle ces fameuses conjectures, dont la dernière a valu à Pierre Deligne toutes ces distinctions ? La chose la plus précise que je peux dire sur ce blog, c'est qu'elles s'intéressent au comportement de Ζ, une fonction définie à l'aide de considérations géométrico-algébriques sur les corps finis. Heureusement, Deligne a aussi résolu des problèmes un peu plus explicables, comme la conjecture de Ramanujan(-Peterson), qui peut donner une idée
La conjecture de Ramanujan
Pour comprendre cette conjecture (qui sera résolue par Deligne en 1968), on a besoin de la fonction Δ(q) suivante :
S'intéresser à cette fonction peut paraître totalement arbitraire, mais ne l'est pas tant que ça. Il se trouve que cette fonction, lorsque son paramètre est un nombre complexe q(z)=e2iπz, possède de nombreuses propriétés intéressantes que l'on rencontre rarement ensemble. C'est un exemple de forme modulaire, des fonctions qui n'ont plus à prouver leur utilité puisqu'elles sont centrales dans la démonstration par Wiles du dernier théorème de Fermat. Le nombre 24 n'est pas arbitraire non plus, il se trouve que les espaces de dimension 24 possèdent des structures particulièrement intéressantes (les réseaux de Leech).
Δ(q), donc, c'est un produit infini. On peut l'écrire :
Δ(q) = q.(1-q)24.(1-q2)24.(1-q3)24.(1-q4)24...
= q.(1-q)...(1-q).(1-q2)...(1-q2).(1-q3)...(1-q3).(1-q4)...(1-q4)....
(chaque terme se retrouve 24 fois)
Écrire Δ sous la forme d'un produit, c'est bien, mais ça serait encore plus marrant de le développer (même si il y a une infinité de termes, on a le droit de le faire). Chacun des termes du développement s'obtient en choisissant soit 1, soit -qn dans chacune des parenthèses (sachant qu'on ne peut pas choisir les termes -qn une infinité de fois). En tout cas, il n'y a qu'un nombre fini de façon d'obtenir le terme qn. Par exemple, pour obtenir q42, on peut choisir q1, q1 et q40. On peut aussi le faire en choisissant 24 fois le terme q1 et 9 fois le terme q2. On ne peut cependant pas obtenir q42 en prenant 42 fois le terme q1, puisqu'on chaque terme qk ne peut être pris qu'au plus 24 fois.
Le développement de Δ commence donc par :
Δ(q) = q.(1 - 24q1 + 252 q2 - 1472 q3 + ...)
Le coefficient de qn dans ce développement, on l'appelle τ(n) : la fonction tau de Ramanujan. Ainsi, τ(1) = 1, τ(2) = -24, τ(3) = 252 (la présence du facteur q devant la parenthèse crée un décalage). C'est ainsi qu'est défini la fonction τ de Ramanujan : il correspond au nombre de façons d'écrire n-1 comme une somme où chaque nombre se retrouve au plus 24 fois.
A cause du signe - dans "-qn", il faut être en fait un peu plus précis : τ(n), c'est le nombre de façon d'obtenir n-1 en sommant un nombre pair de termes, auquel on soustrait le nombre de façons d'obtenir n-1 avec un nombre impair de termes.
Une formule donnant explicitement les valeurs de τ n'existera sans doute jamais. Le problème, c'est plutôt de connaître l'ordre de grandeur de τ(n). C'est justement d'un des nombreux problèmes de Ramanujan. À partir des constations décrites en dessous, il formule la conjecture suivante :
Si p est premier, alors -2p11/2 ≤ τ(p) ≤ 2p11/2
Pourquoi 11/2 ? Ça, c'est une bonne question !
D'autres conjectures sur τ existent ; en particulier, la conjecture de Lehmer suppose que τ n'est jamais égal à 0, conjecture vérifiée vraie jusqu'à n = 22 798 241 520 242 687 999.
Pourquoi cette conjecture a l'air vraie ?
Étonnament, le nombre τ(n) est lié au nombre r(n) de façons d'écrire un nombre n (impair) comme somme de 24 carrés, par la formule suivante, due à Ramanujan :
r(n) = 16/691 σ11(n) + 33152/691 τ(n)
Le terme σ11(n) (somme des puissances 11eme des diviseurs de n) donne l'ordre de grandeur de r(p), et τ(n) est son terme correctif. Et c'est grâce à cette formule et de considérations à la limite du hors-sujet que l'on peut prédire que τ(p) est de l'ordre de p11/2.
Écrire un nombre n comme somme de 24 carrés, c'est trouver 24 entiers x1, ..., x24 qui vérifient :
x12 + x22 + ... + x242 = n
Ce qui tombe bien, c'est que x12 + x22 + ... + x242 = n, c'est aussi l'équation d'une sphère de rayon √n dans un espace de dimension 24. Il y a donc autant de façons de partager un entier en somme de 24 carrés que de points à coordonnées entières sur cette sphère.
Le nombre de points entiers sur la surface, on peut justement l'estimer. Puisque l'on est dans un espace de dimension 24, le volume d'une boule de rayon r étant C r24, celui de la boule de rayon √n est donc de C n12 (C est le coefficient de proportionnalité, on ne cherche pas à le connaître de façon précise). Le nombre de points de la surface va alors être proportionnel à la différence entre le volume des boules de rayon √n et √n-1 (qui valent respectivement C.n12 et C.(n-1)12)
r(n) ≈ C n12 - C (n-1)12 ≈ 12 C n11
On peut donc dire que le nombre de façons de partager un nombre n en 24 entiers est proportionnel à n11. La présence de σ11(n), lui aussi de l'ordre de n11, dans la formule de r(n) est donc tout à fait légitime.
Pour ce qui est du terme d'erreur, on peut adopter une démarche probabiliste : supposons qu'on choisit au hasard (avec 1 chance sur 2) si les r points proches de la surface appartiennent ou non à la sphère. On peut donc s'attendre à ce que la moitié des points appartiennent à la sphère, plus ou moins l'écart-type (la marge d'erreur), qui vaut √r. Dans le cas présent, cette marge d'erreur, proportionnelle à τ(n) selon la formule de Ramanujan, est donc de l'ordre de √(n11) = n11/2 ! Tout concorde !
Évidemment, tout ceci n'a rien d'une démonstration rigoureuse, mais permet de montrer que la majoration |τ(p)| ≤ 2p11/2 est intuitivement vraie. Ce qui est réellement étonnant, c'est que cette estimation faite à la volée soit vraie ! Le terme d'erreur de r(n) est précisément ce à quoi on pouvait s'attendre, alors que les arguments utilisés sont très éloignés de l'arithmétique !
Les conjectures de Weil permettent de montrer ce genre de choses : l'erreur dans l'estimation de certaines quantités est parfois précisément ce à quoi l'on pouvait s'attendre. Finalement, c'est grace aux travaux de Pierre Deligne que l'on peut aujourd'hui dire ce genre d'évidences !
Sources :
The work of Pierre Deligne, W.T. Gowers
31 mars 2013
[#] De l'autre côté du miroir (et ce que Euclide y a trouvé)
Le journal Le Monde, avec l'assentiment de Cédric Villani, vient de lancer "Le monde est mathématique", une série de 40 ouvrages vulgarisant l'ensemble des mathématiques. Il s'agit en fait d'une réédition revue et corrigée de la même série sortie en août 2011.
Le nombre d'or : le langage mathématique de la beauté
~~~~~~
Pour le numéro 1, ils ont choisi le sujet qui domine les mathématiques, le phénomène qui explique la beauté du monde qui nous entoure, de la nature à l'architecture en passant par l'astronomie. Aussi incroyable que cela puisse paraître, un simple nombre régit l'Univers et l'esthétisme : le nombre d'or ! Qu'on l'appelle "divine proportion", "chiffre d'or", "ratio pimpant" ou Φ, on fait toujours référence à ce nombre qui régit l'agencement des pétales des tulipes, de la forme des galaxies ou de l'ensemble des productions artistiques depuis la Renaissance italienne. Bref, un excellent choix pour un premier numéro, qui laisse présager d'une excellente série !
Les origines du nombre d'or
Les origines du nombre d'or remontent à l'antiquité, lorsque Euclide écrit dans son livre XLII :
"Un rectangle est dit coupé en extrême et moyenne raison quand, comme le plus grand côté est au plus petit, ainsi est le plus petit relativement à la moitié plus grand "
Le nombre d'or prendra ses lettres de noblesse à la Renaissance lorsque Luca Pacioli le met à l'honneur De divina proportionne, illustré par Léonard de Vinci himself ! Puisque ce rectangle en extrême et moyenne raison est l'oeuvre de Dieu, il devient pour la première fois "divin". La renommée du nombre d'or aujourd'hui est due aux travaux sur l'esthétisme du philosophe allemand Adolf Zeising, qui montre que tout ce qui est lié au beau est également lié au ratio d'or. Il prend alors le nom Φ (phi), en référence à Phidias, le sculpteur du Parthénon.
Géométriquement, cela revient à déterminer la proportion a/b qui vérifie :
Algébriquement, on peut calculer la valeur de Φ :
Le nombre d'or est également lié aux suites de Fibonacci, deux suites (pn) et (qn) où chaque terme est obtenu en ajoutant les termes des rangs précédents : pn = pn-1 + qn-1 et qn = 2pn-1 + qn-1. En démarrant les suites à 1, on obtient :
(pn) : 1, 2, 5, 12, 29, 70, 169, 408
(qn) : 1, 3, 7, 17, 41, 99, 239, 577
La particularité de cette suite, c'est que les quotients des termes de même rang se rapprochent de Φ !
Le nombre d'or dans la nature
Considérer le nombre d'or comme l'étalon de la beauté n'a rien d'arbitraire, la nature offrant son lot d'exemples pour le confirmer. Pour les débusquer, on a besoin de ces outils que sont le rectangle d'or, le triangle d'or, la spirale d'or ou l'ellipse d'or :
Si ces formes vous semblent familières, c'est qu'elles sont le langage de la nature !
La spirale d'or permet de repérer le nombre d'or dans le coquille d'un nautile, dans le bras d'une galaxie, dans le pavillon d'une oreille ou dans les spirales des feuilles d'aloès :
Le nombre d'or dans l'architecture
Le nombre d'or trouve évidemment ses origine dans les plans du Parthénon, qui s'inscrit dans un rectangle d'or parfait, mais on le retrouve dans de nombreux monuments. Par exemple, le nombre d'or apparaît dans la Tour Eiffel, dans la grande mosquée de Kairouan ou dans le dolmen de Crucono :
Le nombre d'or dans l'art
Le nombre d'or se retrouve naturellement dans de nombreuses oeuvres d'art, que ce soit dans la Joconde ou dans l'École d'Athène. On pourrait multiplier ces exemples chez la plupart des artistes, de la période hellénistique grecque au Pop Art moderne, en passant par l'art Byzantin ou le néo-classicisme.
Attention cependant, le rectangle encadrant l'homme de Vitruve de De Vinci n'est pas un rectangle d'or, mais la page sur lequel il est dessiné possède bien ces proportions. Puisque je vous dis que le nombre d'or est partout !
Bref, si la nature possède un cadenas à sa compréhension, le nombre d'or Φ = 1.414... ne peut qu'en être sa clé !
Images :
Nautilus Cutaway Logarithmic Spiral, Ear, Aloe polyphylla spiral, 2006 01 21 Athènes Parthénon, Galerie mosquée Kairouan, Crucono Dolmen
Vous l'aurez évidemment compris, cet article est un hilarant poisson d'avril. Pour de vraies informations sur le nombre d'or, retournez là-bas.
24 mars 2013
[#] Pikachu, attaque séries de Fourier !
Arrêtez tout, voici... l'équation de Pikachu !
Quand on le trace pour t entre 0 et 51 π, on obtient...
Pika pikaa !!
Depuis janvier dernier, cette équation est disponible sur WolframAlpha avec la requête "Pikachu curve". Elle est l'oeuvre de Richard Clarke, qui a créé entre autres la courbe des Rolling Stones ou la courbe de Dark Vador. Ces trois courbes sont construites sur le même modèle, un astucieux mélange de courbes paramétriques et de polynômes trigonométriques.
Bon, concrètement, comment peut-on obtenir Pikachu à partir de ce ramassis de sinus ?
Equation paramétrique par morceaux
Déjà, il faut remarquer que l'équation est paramétrique : pour chaque valeur de t (entre 0 et 51 π) correspond un point (x(t);y(t)).
Quand on la regarde de plus près, les équations x(t) et y(t) suivent le même schéma : 13 morceaux composés d'une somme de fonctions de la forme a.sin(m.t+b) multipliée par des fonctions de la forme θ(n.pi-t) θ(t-(n-4).π), le tout multiplié par cette étrange fonction qu'est "theta(sqrt(sgn(sin(t/2))))". Autrement dit, les équations ressemblent à ceci :
(C'est pas forcément plus clair...)
On y retrouve la fonction θ, qui n'est autre que la fonction de Heaviside ; θ(t) vaut 1 si t>0, 0 sinon. Les morceaux θ((4k+3)π-t)θ(t-(4k-1)π) valent donc 1 sur les intervalles [(4k-1)π;(4k+3)π], et 0 sinon.
Ces fonctions θ permettent donc de construire la courbe morceaux par morceaux. En l’occurrence, chacune des 13 parties de l'équation correspond à un morceau du corps de notre souris électrique : corps, oeil gauche, pupille droite, double-menton...
Prenons par exemple le morceau qui correspond au corps de Pikachu :
A cause de la présence de θ(3π-t)θ(t+π), le couple (x(t),y(t)) vaut (0,0) partout, sauf sur l'intervalle [-π;3π]. Graphiquement, cela donne:
De même, l'oeil gauche sera tracé pour t ∈ [3π,7π], l'oeil droit pour t ∈ [7π,11π], et ainsi de suite.
La multiplication finale par θ(√(sgn(sin(t/2)))) en rajoute une couche : (x(t),y(t)) vaut (0,0) partout, sauf sur les intervalles de la forme [2(2k)π;2(2k+1)π] (La racine carrée me semble de trop dans cette équation, mais bon...). Cet ajout n'est pas fondamentalement nécessaire, mais empêche la courbe de repasser sur elle-même.
Bref : l'équation de Pikachu est la réunion de 13 courbes paramétriques, chacune définie sur des intervalles de longueur 2 π.
Polynômes trigonométriques
Tout ça ne nous dit pas comment obtenir les courbes en question... La réponse, il faut la chercher du côté des séries de Fourier.
Point théorique très bref : toute fonction périodique peut s'écrire sous la forme d'une somme (infinie ou non) de fonctions cosinus et sinus de différentes fréquences (sous certaines hypothèses de régularité des fonctions qui entrent en jeu, là n'est pas la question). Les théories des séries de Fourier et de ses transformées sont un domaine actif de la recherche mathématique ; elles ont en particulier donné naissance à la compression JPEG des images ou à la compression MP3 des musiques.
A titre d'exemple, on peut écrire la fonction périodique cos(t)3 sous la forme d'une somme de (co)sinus : cos(t)3=0.75 cos(t)+0.25 cos(3t). Mais les fonctions qui nous intéressent ici, ce sont celles qui nous donnent l'abcisse et l'ordonnée des points de la courbe en fonction du temps t.
Pour obtenir ces fonctions, la méthode la plus simple est d'échantilloner sa courbe. Le mieux, c'est de faire ça sur un exemple :
A gauche : Courbe avant échantillonage (dessinée à la souris - ça se voit)
Au milieu : courbe après échantillonage - 226 points
A droite : Courbes x(t) (rouge) et y(t) (bleu)
La théorie des séries de Fourier nous indique que l'on peut décomposer/approximer cette fonction en somme de fonctions trigonométriques, moyennant des calculs d'intégrales (ou de sommes, dans le cas discret).
La précision du résultat est directement liée à l'ordre N (le nombre de cosinus/sinus) de cette décomposition :
Ordre N=4 : ça ressemble vaguement à un J...
x(t) = -0.15 + 1.02 cos(t) - 0.69 sin(t) + 0.04 cos(2t) - 0.71 sin(2t) + 0.68 cos(3t) - 0.06 sin(3t) + 0.15 cos(4t) - 0.07 sin(4t)
y(t) = 0.26 + 1.59 cos(t) + 0.89 sin(t) + 0.22 cos(2t) - 0.09 sin(2t) -0.39 cos(3t) - 0.03 sin(3t) + 0.2 cos(4t) + 0.09 sin(4t
Ordre N = 10 : Ca ressemble vraiment à un J !
Une petite transformation des couples cosinus/sinus permettent de n'avoir plus que des fonctions de la forme a.sin(b+nt) (ça prend moins de place et ça a plus de gueule !). La touche finale, c'est l'écriture fractionnaire des coefficients, qui plaira aux Pokéfans les plus pythagoriciens.
Bref : l'équation de Pikachu a été obtenue grâce à l'approximation de Fourier de courbes (bien) dessinées à la main !
Du coup, on peut s'amuser à réduire l'ordre des approximations :
Le fichier GeoGebra pour ceux qui sont intéressés : Pikachu25.ggb
Les 51 courbes Pokémon disponibles sur Wolfram alpha
10 février 2013
[#] Le plus grand nombre premier a été découvert ?
Le 25 janvier, Dr Curtis Cooper, par l'intermédiaire du projet GIMPS, a découvert M48, le 48e nombre premier de Mersenne. Ce nombre, 257 885 161-1, est donc officiellement aujourd'hui le plus grand nombre premier connu ! Le précédent record (M47, qui possède 12 978 189 chiffres) datait de 2008.
Comme tout a déjà été dit sur ce blog à propos des nombres premiers, revenons plutôt aux bases de la base.
Ca veut dire quoi, 257 885 161-1 ?
C'est le nombre qui vaut 2×2×...×2-1 (où l'on peut compter 57 885 161 fois le nombre 2). Il s'écrit avec 17 425 170 chiffres, ce qui est plutôt long : si on l'imprimait sur des feuilles A4, cela serait profondément stupide (imprimer autant de pages coûterait au bas mot 500€ en encre, sans compter le prix de l'imprimante et du papier).
Qu'est ce qu'un nombre premier ?
La plupart des nombres peuvent s'écrire sous la forme d'une multiplication : 4=2×2, 6=2×3, 8=2×4, 9=3×3, 42=6×7... Mais d'autres, non : ce sont les nombres premiers, comme 2, 3, 5, 7, 11 ou 13, qui n'apparaissent dans aucune table de multiplication (sauf dans la table de 1, mais c'est trop facile). Par exemple, les nombres pairs ne sont pas premiers, puisqu'ils sont dans la table de 2 (sauf 2).
(J'aurais aussi pu dire qu'un nombre premier est un nombre dont les seuls diviseurs sont 1 et lui-même...)
Qu'est ce qu'un nombre de Mersenne ?
Un nombre de Mersenne, c'est un nombre que l'on peut écrire 2p-1, noté Mp :
M1 = 21-1 = 1
M2 = 22-1 = 3
M3 = 23-1 = 7
M4 = 24-1 = 15
M5 = 25-1 = 31
Parmi les nombres de Mersenne, certains sont premiers, d'autres non :
M7 = 27-1 = 127 (premier)
M8 = 28-1 = 255 (non premier)
M9 = 29-1 = 511 (non premier)
M10 = 210-1 = 1023 (non premier)
M11 = 211-1 = 2047 (non premier)
...
M57 885 161 = 257 885 161-1 = 58...plein de chiffres…51 (premier)
On ne sait pas combien de nombres de Mersenne sont premiers, on en connaît seulement 48 (que l'on a logiquement numérotés de M1 à M48). On sait que si Mp est premier, alors p est premier (ce qui simplifie donc grandement les recherches), mais la réciproque n'est pas vraie.
C'est qui, ce Mersenne ?
Un moine sarthois du XVIIe siècle. D'autres questions ?
M48 est-il le plus grand nombre premier ?
NON ! (Contrairement aux titres que l'on peut lire là, là, là, là, ...)
Il existe une infinité de nombres premiers (la preuve) ! Ce n'est pas le plus grand nombre premier qui a été découvert, c'est simplement que le record du plus grand nombre premier connu a été battu. Il y a des nombres premiers encore plus grands, mais ils se cachent.
C'est si difficile que ça de savoir si un nombre est premier ?
En général, oui.
Prenons le nombre 91, par exemple : il n'est divisible ni par 2 (il ne finit pas par 0, 2, 4, 6 ou 8), ni par 5 (il ne finit pas par 0 ou 5), ni par 3. A vue de nez, ce nombre a l'air d'être un nombre premier. Mais pour en être sûr, il faut vérifier qu'il est divisible par aucun nombre. Après investigations, il s'avère que 91 est dans la table de 7 : ce n'est pas un nombre premier.
Du coup, pour savoir si un nombre est premier ou pas, il faut vérifier qu'il est divisible par aucun autre nombre. Pour un petit nombre, ça va, pour un nombre de 17 425 170 chiffres, c'est forcément un peu long.
Heureusement, les mathématiciens ont mis au point des méthodes pour accélérer les choses. Il existe des méthodes (très longues) pour savoir si n'importe quel nombre est premier. Il existe des méthodes (très rapides) pour savoir si un nombre est peut-être premier (mais se trompe parfois), et surtout, il existe une méthode (le test de Lucas-Lehmer - rapide) pour savoir si un nombre de Mersenne est premier. Le problème, c'est qu'il ne fonctionne que sur les nombres de Mersenne...
Du coup, si on veut trouver de très grands nombres premiers, il faut se tourner vers les nombres de Mersenne, les seuls qui disposent d'un test de primalité abordable.
Il sort d'où, ce Cooper ?
Si Curtis Cooper a réussi à trouver ce nouveau nombre premier, c'est parce qu'il (et son équipe) est le plus gros contributeur du projet GIMPS (Great Internet Mersenne Prime Search) : un petit programme que n'importe qui peut installer et qui cherche quels sont les (grand) nombres de Mersenne premier. A titre d'exemple, la découverte du 45e nombre de Mersenne a été faite par un ingénieur allemand passionné par les nombres premiers.
Moi aussi, je peux devenir milliardaire avec GIMPS ?
Bien sûr que oui ! Mais il faudra avoir beaucoup de chances et trouver plein de nombres premiers.
En quoi cette découverte est-elle géniale ?
En réalité, ça ne révolutionnera en rien le monde des mathématiques. L'algorithme utilisé est le même depuis plus de 100 ans et le programme utilisé est le même depuis 15 ans. Cela dit, il reste intéressant de constater que l'on continue de remplir le panier des nombres premiers titanesques.
A quoi ça sert de savoir ça ?
A rien. Mais si fallait arrêter de faire tout ce qui ne sert à rien, on ne ferait plus grand chose...
(Après, on peut toujours parler du fait que les nombres premiers sont à la base des transactions bancaires sur Internet (et ailleurs), et donc, que les recherches théoriques dans le domaine sont absolument nécessaires. Cela dit, même sans application concrète, la recherche mathématique restera toujours nécessaire)
Le site du projet Gimps, et le communiqué de presse annonçant la découverte. Vous pouvez lire la bête ici.
03 février 2013
[#] Finistère amer
Ce soir, c'est crêpes party ! Une soirée conviviale et bon enfant où nous dégusterons ensemble de délicieuses crêpes à la mode bretonne !
Daou ha daou-ugent krampouezh
Entrées : farine, lait, oeufs (telles que les quantités appartiennent à l'enveloppe convexe des recettes acceptables de pâte à crêpe), sucre (parce que c'est meilleur) et un ingrédient secret (rhum, cognac, bière, fleur d'oranger, épice à pain d'épice, gouda, ...)
Sortie : de délicieuses crêpes
Algorithme :
: Mélanger le tout, puis laisser reposer la pâte.
: ???
: Profit !
Mais attention à ne pas négliger le plus important : le dressage ! Des crêpes, ça ne s'empile pas à la va-vite, il faut respecter une certaine harmonie quand on les superpose, de la plus grande à la plus petite !
Le problème des pancakes, par le mec devenu le plus riche au monde en vendant des logiciels
Pour trier des données, les informaticiens ont inventé un grand nombre d'algorithmes, plus ou moins efficaces : tri à bulles, tri par insertion, tri rapide, tri fusion, tri stupide, tri spaghetti... Mais ces méthodes de tri ne fonctionnent pas lorsque l'on doit trier une pile de crêpes (ou de pancake, pour les non breton-friendly) : des crêpes, ça ne s'échange pas, ça se retourne !
Le problème des crêpes est donc le suivant : vous êtes livreur de crêpes et vous travaillez pour le compte d'un crêpier renommé. Votre chef a cependant une très mauvaise habitude, ses crêpes sont de taille variable, et il les empile au fur et à mesure qu'elles arrivent. Avant de les apporter à vos clients, vous devez donc les trier, de la plus grande à la plus petite. Pour cela, vous ne disposez que d'une simple spatule. En la glissant entre deux crêpes, vous pouvez retourner le haut de la pile ; c'est la seule opération que vous pouvez faire pour réordonner votre tas de crêpes. Au pire, combien d'opérations (que l'on notera f(n)) seront nécessaires pour ranger complètement un tas de n crêpes ?
La seule opération permise est de retourner à la spatule un certain nombre de crêpes au sommet de la pile.
Le problème a été proposé en 1975 par Harry Dweighter dans les pages de l'American Mathematical Monthly. Aucune solution n'est alors proposée, seulement quelques résultats obtenues à la main pour n petit. Il trouve par exemple que f(2)=1 ou f(7)=8 (OEIS : A058986). Si cette histoire de pancakes est aujourd'hui célèbre, c'est surtout parce qu'un certain William H. Gates (avec Christos H. Papadimitriou) s'intéresse à la question en 1979 dans un papier de Discrete Mathematics. Ils prouvent que 17n/16 ≤ f(n) ≤ (5n+5)/3. Ça sera le seul article écrit par Bill Gates avant qu'il invente Windows et devienne l'homme le plus riche au monde.
f(n) existe
Avant de chercher la meilleur solution, il faut au moins prouver qu'une solution existe. Utilisons le langage des permutations : puisque les transpositions élémentaires engendrent l'ensemble des permutations, il suffit de montrer qu'il est toujours possible d'échanger la place de deux crêpes adjacentes dans la pile.
Pour cela, appellons Mk l'opération qui consiste à glisser sa spatule sous la k-ième crêpe (en partant du haut), puis de retourner le haut de la pile. On peut alors montrer que pour échanger les crêpes n°k et k+1, il suffit de faire successivement les opérations Mk, Mk+1, Mk et Mk-1 :
Pour échanger la 4e et 5e crêpe, on effectue successivement les retournements M4, M5, M4 et M3.
Chaque transposition demande donc 4 opérations. On peut donc estimer à 16n2 le nombre de retournements à effectuer pour trier l'ensemble des crêpes (avec le tri à bulles). L'estimation est haute, on peut facilement améliorer ce résultat.
f(n) ≤ 2n-3 : algorithme simple
Il existe en fait un algorithme plutôt simple pour trier ses crêpes. Dans le pire des cas, cela demandera 2n-3 opérations. Le principe, c'est d'amener à sa place (au plus près de l'assiette) la plus grande des crêpes, puis de continuer avec la deuxième crêpe la plus grande, et ainsi de suite.
Dans la pratique :
- on repère la plus grande des crêpes non déjà triée. (disons que l'on cherche à amener la k-ième crêpe à la position i)
- on l'amène au sommet de la pile par un premier retournement (Mk)
- on l'amène à sa place par un deuxième retournement (Mi)
Ceci donne 2 opérations pour chacune des crêpes. Sachant que les deux dernières crêpe demanderont au pire une opération, on a le compte : 2n-3.
En suivant l'algorithme, on peut ranger ces 7 crêpes en seulement 6 retournements.
Vous pouvez voir l'algorithme en action dans cette vidéo.
f(n) ≤ 5/3 n + 5/3 : l'algorithme de Gates
Alors que l'algorithme simple consiste à ranger les crêpes en partant de la base de la pile, l'algorithme de Gates cherche à créer des blocs de crêpes rangées. Quand toutes les crêpes appartiennent au même bloc, c'est qu'elles sont complètement triées.
Il existe donc deux type de crêpes : celles qui sont libres et celles qui appartiennent à un bloc. On dira qu'une succession de crêpes forme un bloc quand elles y sont rangées (par ordre croissant ou décroissant). Si une crêpe n'appartient pas à un bloc, elle sera dite "libre".
On regarde alors la première crêpe de la pile, notée t. On notera t+o une crêpe immédiatement plus grande ou plus petite que t (o désigne en fait 1 ou -1). Il y a alors huit possibilités (liste exhaustive) :
- t est libre, t+o aussi. (cas a - 1 opération)
- t est libre, t+o est le premier élément d'un bloc. (cas b - 4 opérations)
- t est libre, t+o et t-o sont chacun le dernier élément d'un bloc. (cas c - 1 opération)
- t est dans un bloc, t+o est libre. (cas d - 1 opération)
- t est dans un bloc, t+o est le premier élément d'un bloc. (cas e - 1 opération)
- t est dans un bloc de longueur k+1, t-o est le dernier élément d'un bloc et t+(k+1).o est libre. (cas f et g - 4 opérations)
- t est dans un bloc de longueur k+1, t-o est le dernier élément d'un bloc et t+(k+1).o est dans un bloc. (cas h et k - 2 opérations)
- t est dans un bloc de longueur n.
Si on se trouve dans le dernier cas, c'est que les crêpes sont rangées. Sinon, on effectue une suite de mouvements en fonction de la situation. (Voir ici les différents mouvements). À chaque itération, la longueur des blocs augmente : l'algorithme se terminera forcément. Une analyse plus fine montre qu'il faudra au plus (5n+5)/3 opérations.
Application de l'algorithme : les 7 crêpes sont triées en seulement 5 opérations (seuls les cas a, d et e sont rencontrés)
L'algorithme de Gates et Papadimitriou sera amélioré en 2009 par une équipe de chercheurs américains. Le nombre d'opération nécéssaire pour trier n crêpes sera dans le pire de l'ordre de 18/11 n.
Le problème des pancakes cramés, par le mec qui a fait un dessin animé avec une cyclope sexy et un robot alcoolique
Il existe une variante du problème des pancakes : celui des pancakes cramés. Dans ce nouveau problème, l'une des faces de chacune des crêpes est brûlée. Dans l'empilement final, aucune de ces faces ne doit apparaître. La question reste la même : dans le pire des cas, quel est le nombre g(n) de retournements à effectuer pour ranger notre pile de crêpes ?
g(n) ≤ 3n-2
Pour ranger nos crêpes cramées, on peut reprendre l'algorithme simple en ajoutant l'étape qui consiste à retourner la crêpe la plus haute si nécéssaire. Ceci donne un nombre d'opérations proportionnel à 3n. Encore une fois, cette borne supérieure est améliorable.
g(n) ≤ 2n
Si le problème des pancakes doit sa renommée à Bill Gates, celui des pancakes cramés doit la sienne à David S. Cohen (appellé aujourd'hui David X. Cohen pour ajouter un effet SF), co-créateur de la série Futurama (une série bourrée de références mathématiques). Dans un papier publié en 1993 dans Discrete Applied Mathematics, il prouve, avec Manuel Blum, l'encadrement 3/2 n ≤ g(n) ≤ 2n - 2.
L'algorithme suit le même principe que celui de Gates : former des blocs, sous la contrainte qu'au sein de ce bloc, une face brûlée doit toujours être en contact avec la face non-brûlée de la crêpe qui suit. Chaque itération de l'algorithme (qui demande à chaque fois deux opérations) consiste alors à augmenter la taille de ces blocs.
Dans la pratique, deux cas se présentent :
- Au moins une crêpe est dans le bon sens. Supposons que la plus grande d'entre elles est en position k :
-- si c'est la plus grande des crêpes, on l'amènera au bas de la pile (cas a : Mk puis Mn).
-- sinon, il existe une crêpe à l'envers immédiatement plus grande, en position l. On collera ces deux crêpes (cas b : Ml puis Mk'-1 si l>k ; cas c Mk puis Ml'-1 sinon).
- Toutes les crêpes sont à l'envers :
-- Si elles sont complètement rangées, on effectuera n fois les opérations Mn puis Mn-1 (cas *).
-- Sinon, il existe au moins deux crêpes (en position l et k) non collées et non ordonnées que l'on peut réunir en deux opérations (cas d : Ml puis Mk'-1).
À chaque étape (sauf dans le cas *), le nombre de crêpes à considérer diminue (soient elles sont collées - elles comptent comme une seule crêpe, soit elle sont rangées dans le bon ordre depuis l'assiette - on ne les prendra plus en compte).
Ces 7 crêpes sont rangées en 9 retournements.
Au final, cet algorithme rangera les n crêpes en au plus 2n retournements. En l'améliorant un peu, il est possible de gagner deux opérations.
Les deux problèmes restent à l'heure actuelle toujours ouverts. Les calculs ont été menés jusqu'à n=17 (ce qui donne tout de même 17!=3.5×1014 configurations à analyser !) : il faut au maximum 19 retournements pour trier 17 crêpes. Le problème des pancakes brûlés n'a été étudié que jusqu'à n=12 (12!×212=2×1012 configurations possibles) : il faudra au maximum 21 mouvements.
La principale question ouverte reste cependant la suivante : quand on est un vrai Breton, doit-on mettre du sucre dans la pâte à crêpe ?
Sources :
Stack of pancakes, Harry Dweighter, The American Mathematical Monthly Vol. 84, No. 4
Bounds for Sorting by Prefix Reversal, William H. Gates et Christos H. Papadimitriou, Discrete Mathematics 27
On the problem of sorting burnt pancakes, David S. Cohen et Manuel Blum, Discrete Applied Mathematics 61
Images :
Crêpes
27 janvier 2013
[#] Cervalobélophilie
Cartes Pokémon, Minifigurines Légo, Départ'aimants, vignettes Panini, Pogs, surprises Kinder, fèves Astérix, cartes Magic, canards vivants... Combien de collections a-t-on débuté sans jamais en voir le bout, la faute aux doubles qui s'accumulent et aux nouveaux qui se font de plus en plus rares ?... Très vite, des moyens collaboratifs ont été mis en place pour compléter sa collection : échanges dans la cour de récré, échanges via forum internet, achat à l'unité sur des sites d'occasion... Aujourd'hui, petit tour de ce qu'il faut savoir avant de commencer une collection.
Sachez cependant que débuter aujourd'hui une collection de Pogs est une mauvaise idée.
Compléter sa collection ?
Prenons un collectionneur de base, qui veut coûte que coûte acquérir ses n vignettes Panini, quel que soit le nombre de paquets qu'il faudra acheter. On supposera que l'on achète chaque vignette une par une, au hasard. Celles-ci sont équiprobables : la probabilité d'obtenir une vignette donnée est de 1/n.
Estimons donc le nombre de vignettes qu'il faudra acheter en moyenne pour compléter son album.
- Quand on achète sa première vignette, notre album est vide. La probabilité d'obtenir une nouvelle vignette est donc de 1.
- Maintenant que l'on a une vignette dans son album, il ne faut pas retomber sur la même. Cette proba est de 1/n. La proba d'obtenir une nouvelle vignette est donc de (n-1)/n.
- De façon équivalente, si on a déjà k-1 vignettes dans son album, la probabilité d'obtenir une nouvelle vignette sera de (n-k+1)/n.
- Enfin, quand il ne manque qu'une seule vignette, la probabilité d'obtenir cette dernière est de 1/n.
De la même façon qu'il faut jeter en moyenne 6 fois un dé avant d'obtenir pour la première fois le chiffre 6, la première apparition d'un événement de probabilité p n'aura lieu en moyenne qu'après 1/p tentatives (espérance d'une loi géométrique de paramètre p).
Ainsi, puisque la probabilité d'obtenir la k-ième vignette est de (n-k+1)/n, il faudra acheter en moyenne n/(n-k+1) vignettes en plus avant d'avoir cette k-ième.
Pour avoir les n vignettes, il faudra en acheter en moyenne :
ce qui équivaut, pour n grand, à n (ln n + γ), où γ≃0.577 est la constante d'Euler-Mascheroni (la petite soeur de π et e qu'on a tendance à oublier).
En considérant n=456 vignettes à collectionner, il faudra en acheter en moyenne 3056 pour compléter son album. Cela demandera 612 packs de 5 vignettes (soit 367.20€), ou 34 packs de 90 vignettes (soit 326.40€).
y = x (ln x + γ)
Minifigurines légos : n=16, f(n) = 54
Départ'aimants : n=93, f(n) = 475
Images panini Rugby 2012-2013 : n=456, f(n) = 3056
La formule n'est en réalité pas tout à fait correcte, puisqu'un pack de cartes ne peut pas contenir de vignettes en double. La formule que l'on obtient est un peu plus compliquée, mais les résultats restent grosso modo les mêmes.
Rareté ?
Certaines cartes ont l'air plus rares que d'autres. Les joueurs Hongrois ou Slovènes pullulent, alors qu'il me manque toujours le Nosferalto brillant, le Pog Noel ou le départ'aimant de la Mayenne... Sylvain Sardy et Yvan Velenik, deux mathématicien suisses, ont mené l'enquête. En dépouillant 6000 vignettes de l'édition 2010 de l'album football Panini et en procédant à un test du χ², ils en sont arrivés à la conclusion qu'aucune carte n'est plus rare qu'une autre. Oui, même les brillantes !
Mais alors, pourquoi ce sentiment de complot ? La réponse est en fait assez simple : plus on avance dans la collection, plus les nouveautés se font rares.
x = Tn(y) = ∑i=0y-1 n/(n-i) pour n=456
Nombre moyen de vignettes distinctes en fonction du nombre de vignettes achetées
Par exemple, sur une collection Panini de 456 vignettes, la première moitié de la collection demandera environ 320 achats. Avec 320 vignettes en plus, on peut espérer compléter son album à 75%. Les 25% restantes demanderont 2500 vignettes en plus, et les 3 dernières nécessiteront à elles seules presque 1500 achats !
Trésors sur Internet
Heureusement, grâce au réseau mondial de l'Internet, il est désormais possible de faire des échanges avec des collectionneurs du monde entier. On peut même acheter la vignette de ses rêves à l'unité. Évidemment, les vignettes supplémentaires seront un peu plus chères que les vignettes aléatoires, mais quand on aime...
Ainsi, on peut se demander à partir de quel moment il devient le plus intéressant de ne plus se laisser tenter au hasard. Supposons qu'une vignette est trois fois plus chère sur internet qu'en pack aléatoires (estimation haute). En décidant d'acheter ses images au hasard jusqu'à en avoir k, puis d'obtenir les (n-k) autres par des moyens détournés, le prix de revient sera Tn(k).e+(n-k).3e, où Tn(k) est le nombre moyen de vignettes (de prix unitaire e) à acheter pour en avoir k distinctes.
Dans le cas de la collection Panini Rugby 2012-13, on a le graphique suivant :
Coût moyen (en €) de la collection complète en fonction du moment où l'on arrête d'acheter au hasard
y = 0.12.Tn(x)+0.36.(n-x) pour n=456
Le minimum de la courbe est atteint aux alentours de x=300
Le meilleur moment pour passer aux échanges sur Internet, c'est donc le moment où l'on possède 300 vignettes sur les 456. On peut alors obtenir la collection pour un peu plus de 100€. De manière générale, il est préférable d'arrêter les packs aléatoires quand on possède les deux tiers de la collection complète.
Maintenant vous savez : le plus important quand on commence une collection, c'est de savoir s'arrêter à temps !
Sources :
L'émission suisse A bon entendeur du 18 mai 2010, avec son sujet sur les images Panini.
Coupon collector's problem sur Wikipedia
06 janvier 2013
[#] 2012+1 (Cette nouvelle année est-elle intéressante ? Episode 04)
Que doit-on attendre de cette nouvelle année à venir ? L'argent ? L'amour ? La santé ? Comme il est de coutume sur ce blog, nous allons répondre à cette épineuse question par la pratique ce difficile art divinatoire consistant à lire l'avenir dans l'OEIS. Cette encyclopédie regroupe aujourd'hui plus de 200 000 listes, de la suite de Fibonacci à [A000045] à la suite des coefficients du développement en série entière de x(1+x+x2)/[(x-1)(x3+x2-1)] [A171861]. Pour savoir si l'année 2013 sera intéressante, il suffit de regarder le nombre d'apparitions du nombre 2013.
Ainsi, l'année 2011 était très intéressante, puisque 2011 a 363 propriétés intéressantes. Par exemple, 2011 est un nombre premier p qui n'est pas de Ramanujan tel que ]p, 2q] (où q est le plus petit nombre premier supérieur à p/2) contient au moins un nombre premier [A164368] !...
L'année 2012 était beaucoup moins intéressante : seulement 113 propriétés. Parmi celles-ci, on peut constater que le numérateur de 1+1/2+1/3+1/4+...+1/2012 est un nombre premier (A056903).
Et 2013, dans tout ça ? L'année qui arrive sera-t-elle passionnante ou déprimante ? Le grand amour frappera-t-il à votre porte ? Si oui, va-t-il se barrer en courant ? Suspens...
2013 ne possède que 90 propriétés !
Il faut voir la vérité en face : la crise des propriétés qui a débuté l'année dernière se prolongera cette année... Avant de se passer la corde au cou, détaillons-en quelques-unes.
Arbres à 4 feuilles [A055291]
En combinatoire, on aime bien les arbres. Mais ce qu'on aime encore plus, c'est compter les arbres.
Tiens, par exemple, combien existe-t-il d'arbres à 5 branches (et donc, à 6 sommets) ?
Six. Il existe 6 arbres à 5 branches.
En détaillant un peu plus, on compte :
à 2 feuilles : 1 arbre
à 3 feuilles : 2 arbres
à 4 feuilles : 2 arbres
à 5 feuilles : 1 arbre
Et pour les arbres à 26 branches comme celui-ci ?
Un arbre à 26 branches et 4 feuilles parmi tant d'autres.
Des arbres à 26 branches (et 27 noeuds), il en existe 751 065 460. Mais le plus intéressant, c'est qu'il y en a exactement 2013 qui possèdent 4 feuilles !
Nombre de Smith [A104390]
Prenez le nombre 4937775. Sa décomposition en facteurs premiers est 4937775=3×5×5×65837. Ce nombre est tout à fait fascinant, puisque la somme S de ses chiffres (4+9+3+7+7+7+5=42) est égal à la somme Sp des chiffres de ses diviseurs premiers (3+5+5+6+5+8+3+7=42). Un tel nombre a été baptisé "nombre de Smith" par l'américain Albert Wilansky, en l'honneur de son beau frère Harold Smith dont le numéro de téléphone était 493-7775.
Il existe 376 nombres de Smith inférieurs à 10000 (on exclut les nombres premiers la définition). Parmi eux, le nombre 666=2×3×3×37, puisque S(666)=6+6+6=18 et Sp(666)=2+3+3+3+7=18.
Et 2013, dans tout ça ? La décomposition en facteurs premiers de 2013 est 2013=3×11×61. En sommant les chiffres, on trouve :
S(2013) = 2+0+1+3 = 6
Sp(2013) = 3+1+1+6+1 = 12 (= 2×6)
2013 n'est donc pas un nombre de Smith, mais un nombre de 2-Smith : les chiffres de sa décomposition valent le double de ses chiffres. De manière générale, un nombre N composé est un nombre de k-Smith si Sp(N)=k.S(N).
Il a été montré qu'il existe une infinité de nombres de k-Smith, quelque soit k et la base b>2 considérée. La question de la finitude des nombres de k-1-Smith reste cependant encore à trancher.
Règle 942 [A169649]
Le roi des automates cellulaires, c'est le jeu de la vie : une grille infinie et quelques règles à suivre régissant la vie ou la mort des cellules, étapes après étapes. Pour l'automate qui nous intéresse (celui défini par la règle 942 de Wolfram), il n'y a qu'une seule règle à suivre : si une cellule est voisine de 1 ou 4 cellules activées, elle sera activée à l'étape suivante. A l'étape 1, une seule cellule est activée.
Les premières étapes ressemblent alors à :
Les 6 premières étapes de cet automate cellulaire
La 34e étape est moins esthétique, mais elle comptera 2013 cellules activées !
Attention, ne pas fixer trop longtemps cette image sous peine de céphalées sévères.
Mais 2013 a d'autres propriétés intéressantes :
- 2013 et ses deux entiers successeurs possèdent exactement trois diviseurs premiers [A066509, A113789, A113789]. Du coup, d'autres propriétés en découlent : ils ont le même nombre de diviseurs (ils en ont 8) [A005238], ils ont la même signature [A052214]
- 2013 est le produit de trois nombre premiers tels que la somme du carré de ces nombres est aussi un nombre premier. En effet, 2013 = 3×11×61, et 3²+11²+61²=3851 est un nombre premier [A176878].
- 2013 est un nombre allitératif (en anglais) : chaque mot commence par la même lettre (t) [A146755].
- A priori, une puissance de 2 écrite en base 3 ne peut pas avoir 2013 zéros [A036462].
- 2013, qu'il soit écrit en base 2 (11111011101<sub>2</sub>), en base 3 (2202120<sub>3</sub>) ou en base 5 (31023<sub>5</sub>), a la somme de ses chiffre égale à 9 [A135121].
- 2013 = 29²+23²-13²-5²-2². Écrit ainsi sous forme d'une somme de carrés de nombres premiers, 2013 est le premier des entiers à utiliser le nombre 29 [A089295].
- 2013 est le 11e terme d'une suite de Fibonacci commençant par 1 et 22 [A022392]
- 2013 apparaît dans le développement en fraction continue de ζ(3) [A033167].
Mais surtout, 2013 est un nombre de la forme 1 + (144 + (50 + (35 + (10 + n)*n)*n)*n)*n/120... Euh... Qu'est ce que cette propriété fait dans l'OEIS ?! [A145127]
Et au niveau des curiosités qui ne sont pas dans l'OEIS, citons que
- 2013 possède 4 chiffres différents. Ce n'était pas arrivé depuis 1987. Par contre, la prochaine date possédant 8 chiffres différents sera le 17/06/2345, la dernière étant le 25/06/1987.
- ((10/9!)*8!)*7! - 6!*5!/4! + 3!*2! + 1! = 2013
Bref : bonne année 2013 !
Et la santé !
Sources :
Fascinating Smith numbers
30 décembre 2012
[#] Avant de changer d'année (édition 2012)
Dans à peine deux jours, nous allons changer d'année (si si !). L'année 2012 a été plutôt riche sur le plan scientifique : découverte du boson de Higgs, amarsissage de Curiosity, suicide médiatique de la méthodologie scientifique sur fond d'engrais Monsanto... Mais sur le plan strictement mathématique, il s'est aussi passé des choses. Je ne prends pas trop de risques en prédisant qu'il ne se passera plus grand chose d'important dans le monde mathématiques d'ici 2013 (au pire, j'éditerai cet article). Comme j'ai pu le faire en 2010, passons en revue ce ce qui a fait de 2012 une année si mathématique, l'occasion d'évoquer des sujets qui ne méritaient pas d'article dominical.
2012, année Turing-Poincaré
L'année 1912 a vu mourir Henri Poincaré, mais naître Alan Turing. Du coup, cent ans plus tard, on célèbre à la fois "l'année Poincaré" et "l'année Turing".
D'un côté, on a le français Henri Poincaré (mort en 1912, né en 1854), de l'autre, l'anglais Alan Turing (né en 1912, mort en 1954). Le premier a révolutionné la topologie en la rendant un peu plus algébrique, le second a révolutionné l'informatique en comblant les trous de la théorie. L'un a amené une conjecture en topologie ("la conjecture de Poincaré"), question incontournable du domaine pendant presque un siècle, l'autre a révolutionné la cryptanalyse en décodant les messages allemands durant la seconde guerre mondiale. Bref, ils ont chacun révolutionné à leur manière tout ce qui a pu passer entre leurs deux oreilles, il n'était pas de trop de consacrer une année à célébrer leur mémoire. (Alan Turing : 1912-2012).
Vivement l'année 2054 : 42 ans après l'année Turing-Poincaré, on pourra fêter les 100 ans de la mort de Turing et les 200 ans de la naissance de Poincaré !
2012, de nouveaux théorèmes
La topologie a été mise à l'honneur cette année. Grâce à une équipe de chercheurs grenoblois, on sait depuis avril à quoi ressemble un tore plat, prédit dans les années 50 par John Nash (Plat comme un tore), et grâce à l'américain Ian Agol et à sa démonstration de la conjecture de fibration virtuelle (initié par Thurston...), on comprend mieux depuis avril la géométrie hyperbolique en dimension 3 !
Côté arithmétique, on se contente d'annonces : Terrence Tao annonce en janvier avoir démontré une forme faible de la conjecture de Goldbach (Les deux font le pair) et Shinichi Mochizuki révèle en août sa démonstration de la conjecture ABC (La conjecture ABC, aussi facile que 123 ?). Il ne s'agit pour l'instant que d'annonces, on attend le verdict des relecteurs. Affaire à suivre, donc.
D'autres résultats à noter : Gary McGuire a prouvé en janvier qu'une grille de Sudoku devait contenir au moins 17 chiffres pour être faisable (Pendant ce temps, chez les Sudokus), tandis que Khalegh Mamakani et Frank Ruskey ont montré en juillet l'existence d'un diagramme de Venn simple et symétrique à 11 pétales (Mignonne, allons voir si Newroz...). Le point commun de ces deux découvertes : la part importante accordée à l'informatique dans une recherche qui aurait été laborieuse (voire impossible) à la main.
Du côté des anciens théorèmes, celui de Feit-Thompson a fait parler de lui en septembre. Après 6 ans de travail, une équipe internationale de chercheurs menée par l'anglais Georges Gonthier a mis un terme à la preuve formelle de ce théorème d'algèbre, première pierre du théorème de classification des groupes finis simples. De la même façon qu'ils avaient vérifié en 2004 la démonstration le théorème des quatre couleurs, c'est avec l'assistant de preuve Coq qu'ils ont testé la validité de Feit-Thompson, aujourd'hui indiscutable. A présent, c'est au théorème de classification qu'il faut se coller, pour mettre de l'ordre dans une démonstration qui n'a jamais été faite en un seul morceau. Une victoire de plus pour l'informatique en mathématiques.
Les prix de 2012
2012 n'étant pas congru à 2 modulo 4, aucune chance d'avoir de nouveaux médaillés Fields. Heureusement, il reste le prix Abel et bien d'autres prix Nobel de seconde zone.
Le prix Abel ("L'autre Nobel des mathématiciens"), remis au hongrois Endre Szemerédi "pour ses contributions fondamentales aux mathématiques discrètes et à l'informatique théorique", ce qui inclus entre autres son théorème d'arithmétique ("si la série des inverses d'une suite entière positive diverge, alors elle admet une progression arithmétique arbitrairement longue"). (Szemerédi, go !)
Le prix Wolf de mathématiques ("Le troisième Nobel des mathématiques"), à l'américain Michael Aschbacher (travaux en théorie des groupes) et à l'argentin Luis Caffarelli (travaux sur les EDP).
Le prix Shaw de sciences mathématiques ("Le prix Nobel asiatique"), au russe Maxim Kontsevich (travaux en physique mathématiques).
Le prix Crafoord ("le prix Nobel des domaines sans Nobel"), au belge Jean Bourgain et à l'australo-américain Terrence Tao (pour l'ensemble de leur oeuvre).
Le prix d'Alembert ("le Nobel français de la vulgarisation mathématique"), à Robin Jamet (pour sa chronique Magic Math dans Science & Vie Junior) et Shaula Fiorelli Vilmart et Pierre-Alain Chérix (pour l'ensemble de leur oeuvre).
Le prix Nobel d'économie ("le vrai-faux prix Nobel"), remis à l'économiste Alvin Roth et au mathématicien Lloyd Shapley, pour une utilisation pratique du problème des mariages stables. (Quatre mariages et un prix Nobel)
Nouveaux records
En 2012, a-t-on découvert de nouveaux nombres premiers gigantesques ? A-t-on calculé toujours plus de décimales de constantes fondamentales ? Oui !
Rien de nouveau du côté des nombres premiers de Mersenne, les plus grands nombres premiers connus à ce jour (on reste bloqué à 243 112 609-1, soit 12 978 189 chiffres, depuis 2008). On peut cependant noter que le plus grand nombre premier primorial est désormais 2·3·5·7·11·...·1098133-1 (476 311 chiffres), alors que le plus grand nombre premier de Sophie Germain (un nombre premier p tel que 2p+1 est également premier) est maintenant 18543637900515·2666667-1 (200 701 chiffres, le précédent record de 2010 était d'à peine 80 000 chiffres !).
Du côté du calcul de décimales de π, on en connaît aujourd'hui 10 000 000 000 050. Shigeru Kondo & Alexander Yee, responsable du calcul des 5 000 000 000 000 premières décimales en 2010, on simplement relancé leur programme en le faisant tourner quatre fois plus longtemps. Après ça, ils en ont profité pour calculer, avec le même programme, les 2 000 000 000 050 premières décimales de √2 (doublant le précédent record de 2010).
Ils nous ont quitté en 2012
Sur une musique solennelle, il aurait fallu faire passer en blanc sur fond noir le nom de la trentaine de mathématiciens qui nous ont quitté cette année. Au milieu de ces noms, on aurait pu lire :
William Thurston (1946 - 2012), médaillé Fields en 1982 pour ses travaux sur les géométrie en dimension 3. Ce mathématicien américain laisse d'ailleurs son nom en 1976 a sa "conjecture de géométrisation", qui permet de classifier en huit catégories les différentes géométries à trois dimensions existantes. Elle sera définitivement démontrée en 2003 par Perelman (l'ermite qui a démontré seul la conjecture de Poincaré dans un recoin de la Sibérie).
Nicolaas Govert de Bruijn (1931 - 2012). En plus d'une constantes et de quelques théorèmes non négligeables, ce mathématicien hollandais laissera son nom aux suites de De Bruijn : une suite (cyclique) qui contient une fois chaque mot de k lettres sur un alphabet à n lettres. Par exemple, une (parmi 2048) suite de Bruijn contenant tous les mots à 5 lettres sur l'alphabet {A,B} est AAAAABAAABBAABABAABBBABABBABBBBB.
Lars Hörmander (1931 - 2012), mathématicien suédois médaillé Fields en 1962 pour ses travaux sur les EDP linéaires.
Et aussi Bruno Kostrzewa, plus connu sous le nom de @mathoscope, source infatigable de revues de presses mathématiques sur Internet.
Et le blog
Cette année, à cause de considérations professionnelles, j'ai dû limiter mon rythme de publication (seulement 23 articles cette année). Ceci ne vous a pas empêché de venir consulter ce blog, puisque vous avez été environ 500 000 (!) cette année à passer par ici. Si on enlève la moitié qui pensait découvrir un moyen infaillible de gagner à l'Euromillions, il reste tout de même un sacré paquet de monde, en particulier pour les articles orientés proba (Une chance sur beaucoup, Erreur des probabilités en votre faveur). Je vous invite également à redécouvrir les quelques articles lus par l'équipe de Podcast Sciences (ici, là et là), celui que j'ai réécrit pour Images des Mathématiques (ici) et l'article qui a servi de bibliographie pour un article de JP Delahaye dans le Pour la Science de février 2012 (ici).
Et un merci tout particulier à tous ceux qui laissent une trace de leur passage dans les commentaires ou sur les réseaux sociaux (comme on dit à la télé), rendez-vous en 2013 !
