Formule autoréférente de Tupper

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

La formule autoréférente de Tupper est une inégalité à deux variables. Lorsque l'ensemble des points du plan qui satisfont cette inégalité sont tracés, une partie du plan représente la formule elle-même. Créée par Jeff Tupper en 2001[1], il s'agit d'un exemple d'autoréférence.

Caractéristiques[modifier | modifier le code]

Définition[modifier | modifier le code]

La formule est une inégalité définie par :

{1\over 2} < \left\lfloor \mathrm{mod}\left(\left\lfloor {y \over 17} \right\rfloor 2^{-17 \lfloor x \rfloor - \mathrm{mod}(\lfloor y\rfloor, 17)},2\right)\right\rfloor

\lfloor \cdot \rfloor est la fonction partie entière et mod l'opérateur modulo[1],[2],[3],[4].

Tracé[modifier | modifier le code]

Soit k le nombre de 544 chiffres égal à :

960939379918958884971672962127852754715004339660129306651505519271702802395266
424689642842174350718121267153782770623355993237280874144307891325963941337723
487857735749823926629715517173716995165232890538221612403238855866184013235585
136048828693337902491454229288667081096184496091705183454067827731551705405381
627380967602565625016981482083418783163849115590225610003652351370343874461848
378737238198224849863465033159410054974700593138339226497249461751545728366702
369745461014655997933798537483143786841806593422227898388722980000748404719

Si on trace le graphe de l'ensemble des points (x,y) qui satisfont l'inégalité de Tupper sur la restriction du plan à 0 < x < 106 et k < y < k+17, on obtient le graphe suivant[1],[5] :

Tracé de l'inégalité de Tupper sur [0..106;k..k+17] ; par simplicité, le tracé a été ramené verticalement au niveau de y=0.

Fonctionnement[modifier | modifier le code]

Du fait de la partie entière et du modulo 2, la partie droite de l'inégalité ne peut prendre comme valeur que 0 ou 1. Les solutions de l'inégalité sont donc celles de l'égalité :

\left\lfloor \mathrm{mod}\left(\left\lfloor {y \over 17} \right\rfloor 2^{-17 \lfloor x \rfloor - \mathrm{mod}(\lfloor y\rfloor, 17)},2\right)\right\rfloor = 1

On pose q le quotient de la division euclidienne de \left\lfloor {y} \right\rfloor par 17 et r son reste : q = \left\lfloor { y \over 17 } \right\rfloor et r = \mathrm{mod}\left(\left\lfloor {y} \right\rfloor,17\right). On peut écrire : \left\lfloor {y} \right\rfloor = 17q + r. L'équation précédente devient (en divisant par la puissance de 2 plutôt qu'en multipliant par son opposé) :

\left\lfloor \mathrm{mod}\left({q \over 2^{17 \lfloor x \rfloor + r}},2\right)\right\rfloor = 1

c'est-à-dire :

\left\lfloor {q \over 2^{17 \lfloor x \rfloor + r}} \right\rfloor est impair.

Dans cette formule, la partie entière de la division de q par 2^{17 \lfloor x \rfloor + r} permet d'obtenir le 17\lfloor x \rfloor + r-ième bit de q[6].

De façon générale, la formule de Tupper décode une image matricielle monochrome stockée dans une constante q. Le bit de poids faible de q encode le pixel du coin inférieur-gauche de l'image, les 17 premiers bits de poids faibles encodent la colonne de pixels la plus à gauche, les 17 bits suivants encodent la 2e colonne la plus à gauche, ainsi de suite.

Lorsqu'elle est appliquée à tous les nombres y positifs, l'inégalité trace une bande verticale contenant toutes les images possibles de 17 pixels de hauteur. La tranche située entre k et k+17 décrit la formule elle-même, mais ce n'est qu'un cas particulier : toutes les autres formules possibles sont également décrites ailleurs, pour peu qu'elles tiennent sur 17 pixels de hauteur.

Historique[modifier | modifier le code]

Jeff Tupper publie la formule dans un article pour le SIGGRAPH 2001 (une conférence annuelle sur l'infographie), discutant des méthodes de tracés analogues à celle employée par GrafEq, un programme de représentation graphique[1].

Tupper a composé depuis des versions étendues de sa formule originale, qui excluent tout le plan sauf une zone particulière[7].

Références[modifier | modifier le code]

  1. a, b, c et d (en) Tupper Jeff, « Reliable Two-Dimensional Graphing Methods for Mathematical Formulae with Two Free Variables », SIGGRAPH 2001 Conference Proceedings,‎ juillet 2001 (lire en ligne)
  2. (en) « Tupper's Self-Referential Formula », MathWorld
  3. (en) D. H. Bailey ; J. M. Borwein ; N. J. Calkin ; R. Girgensohn ; D. R. Luke ; V. H. Moll, Experimental Mathematics in Action, Natick, MA, A. K. Peters,‎ 2006 (ISBN 978-1568812717), p. 289
  4. collectif, « Self-Answering Problems », Math Horizons, vol. 13,‎ avril 2006, p. 19
  5. (en) S. Wagon, « Best Puzzles - Problem 14 »
  6. (fr) « Le produit de Tupper », Choux romanesco, vache qui rit et intégrales curvilignes
  7. « Index of /selfplot », peda.com

Annexes[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Liens externes[modifier | modifier le code]