Le produit de Tupper
Les mathématiques s'avèrent parfois surprenantes : une formule parachutée de nulle part peut permettre de dessiner le logo de Batman ou de donner l'ensemble des nombres premiers. C'est peut-être ça, la magie que l'on attribue aux maths...
Mais la magie n'existe pas ! A l'instar d'un Denis Brogniart dévoilant les secrets de la magie, je vais détruire aujourd'hui le mystère qui se cache derrière la formule auto-référente de Tupper, la seule formule égale à sa représentation graphique...
Place au tour :
Dessinez l'ensemble des points (x,y) tels que
dans la région
où N est l'entier suivant (qui compte 544 chiffres) :
48584506361897134235820959624942020445814005879832445494830930850619
34704708809928450644769865524364849997247024915119110411605739177407
85691975432657185544205721044573588368182982375413963433822519945219
16512843483329051311931999535024137587652392648746133949068701305622
95813219481113685339535565290850023875092856892694555974281546386510
73004910672305893358605254409666435126534936364395712556569593681518
43348576052669401612512669514215505395545191537854575257565907405401
57929001765967965480064427829131488548259914721248506352686630476300
Quelques petits détails pour comprendre la formule : la notation ⌊x⌋ correspond à la partie entière de x (par exemple, ⌊4.2⌋ = 4) et la notation mod(x,k) correspond au reste de x dans la division euclidienne par k (par exemple, mod(4.2,3) = 1.2)
Si vous n'avez pas de calculatrice graphique capable de dessiner des équations implicites ou de manipuler des nombres à plus de 500 chiffres, voilà ce que vous obtenez :
Eh oui ! Le graphe de la formule est... la formule elle-même !
La formule de Tupper
C'est donc cette formule que l'on appelle la formule de Tupper. A ce stade de l'article, vous vous demandez surement "Mais comment ce truc-là fonctionne ?". Mais à ce stade de l'article, je vais plutôt vous dire qui est donc ce mystérieux Tupper.
Jeff Tupper, donc, n'est pas mathématicien, mais plutôt informaticien. On lui doit GrafE, un logiciel capable de tracer facilement toutes ses courbes préférées (même avec des équations implicites). Sa formule apparaît pour la première fois dans un papier de 2001 qui parle de techniques révolutionnaires pour dessiner des équations. Son article est évidemment égayé d'illustrations, notamment la figure 13, qui sera plus tard appelée "formule autoréférente de Tupper".
Petit détail supplémentaire : le nombre N que l'on trouve dans ce papier (et dans quelques articles y faisant référence) est environ N'=960...719. Cette valeur est fausse ! La formule réplique bien la formule, mais à l'envers. Voilà ce qu'il se passe lorsque les conventions des graphiques sont changées en passant des maths à l'informatique...
Le truc
La formule s'affiche elle-même, c'est génial ! Mais comment marche-t-elle exactement ?... Evidemment, il y a un truc, une formule simple ne peut pas faire des choses aussi complexes (n'est pas Mandelbrot qui veut). Par contre, il y a un truc bien plus complexe dans cette équation, c'est le domaine dans lequel il faut la tracer. Pourquoi un N si compliqué ? ...
L'image finale, finalement, n'est qu'une image de 17×106 pixels, soit 1802. Dans la formule, le nombre 17 apparaît de bien nombreuses fois. Et puis, le nombre N démesurément grand (544 chiffres quand il est écrit en base décimale) fait 1807 bits (il faut 1807 chiffres pour l'écrire en binaire). Coïncidence ?... Je ne crois pas ! C'est sûrement ce nombre-là qui code d'une façon ou d'une autre l'image que l'on cherche à obtenir.
Regardons donc la formule d'un peu plus près : il faut prendre les nombres réels (x,y) tels que
En fait, seule la partie entière des nombres x et y est intéressante, puisque l'on considère toujours ⌊x⌋ et ⌊y⌋ (en effet, ⌊y/17⌋=⌊⌊y⌋/17⌋). En fait, on peut se contenter de regarder les nombres entiers (x,y) tels que :
Et ce 1/2, il sert vraiment à quelque chose ? La partie entière d'un truc modulo 2, c'est jamais que 0 ou 1, si bien que 1/2 est de trop... On doit finalement tracer :
Parlons un peu arithmétique. Un nombre entier y peut s'écrire de façon unique sous la forme y=17q+r (avec r entier entre 0 et 16, inclus.). q, c'est quotient, et r, c'est le reste. Pour calculer q et r, le mieux est d'utiliser les fonctions mod et ⌊*⌋, avec les formules q=⌊y/17⌋ et r=mod(y,17). Du coup, si on note y=17q+r, la formule de Tupper demande de trouver les entiers (x,y) vérifiant :
En français, on dirait plutôt :
Quelle est la formule pour obtenir le x-ème chiffre en base 2 d'un nombre q donné ? Je vous le donne en mille : c'est ⌊q/2x⌋ mod 2 (en partant du principe que le 0-ème est le chiffre le plus à droite). Autrement dit, on demande de trouver les entiers (x,y) tels que :
Vous ai-je dit que le nombre N était divisible par 17 ? Parce que, du coup, quand y est dans l'intervalle [N,N+16], son quotient par 17 reste toujours le même : c'est q. Tracer l'équation pour (x,y)∈[0,106]×[N,N+16], c'est donc la même chose que de la tracer pour (x,r)∈[0,106]×[0,16] : le pixel en (x,r) est donc coloré si et seulement si le (17x+r)-ème bit de q est 1.
Pour tracer l'équation, il faut donc lire un à un les bits de q, dans lequel le dessin plus haut a été soigneusement codé. La grille est lue colonnes par colonnes, de bas en haut...
Personnalisation
Finalement, on retrouve dans le graphe de la formule de Tupper n'importe quel dessin en noir et blanc d'une hauteur de au plus 17 pixels. Il suffit de sélectionner le bon N pour le retrouver.
Avec ce truc, on peut en fait tracer tout ce que l'on veut, quitte à changer "17" en autre chose pour un dessin avec de meilleures résolutions.
Par exemple, en traçant les nombres (x,y) tels que
pour
on obtient le graphe suivant :
Pour fabriquer ça, je me suis contenté de griffoner ma signature sur la feuille quadrillée qui traînait. Elle rentre dans un rectangle 8×5, c'est parfait ! Il faut ensuite regarder les pixels sélectionnés, colonnes par colonnes, de bas en haut (ce qui donne les n°0, 1, 4, 5, 9, 10, 11, 12, 13, 14, 19, ...), puis poser :
q = 1+2+24+25+29+210+211+212+213+214+219+
220×(1+2+24+25+29+210+211+212+213+214+219)
= 583632715315
Il n'y a plus qu'à multiplier q par 5 pour obtenir le N magique, ici à 13 chiffres !
Retour au tour !
Quand un tour de magie est révélé, il y a toujours quelqu'un de plus malin pour faire le même tour avec un autre truc. La formule de Tupper n'y fait pas exception !
Un certain Jakub Trávník a fabriqué très récemment une formule qui s'affiche elle-même, mais qui affiche aussi les constantes qui la composent. Voici ce qu'il se passe quand on la dessine sur [-15,352]×[-1950,116] :
(J'ai un peu tronqué l'image, les 12876 décimales de N prennent de la place)
Reliable Two-Dimensional Graphing Methods for Mathematical Formulae with Two Free Variables, le papier de Jeff Tupper qui donne naissance à sa formule.
How does Tupper’s self-referential formula work? : Là où j'ai piqué la majorité des informations...
Self Referential Formula in Math : la formule de Trávník (sans les explications, malheureusement)