Le fractal accroché à mon mur pendant 12 ans

 (chriskw.xyz)
2 points par GN⁺ 2025-05-23 | 1 commentaires | Partager sur WhatsApp
  • Après avoir gardé pendant 12 ans sur mon mur un motif de carrés répliqués dessiné sur papier quadrillé au collège, je l’analyse comme un fractal appelé wallflower, en le reliant aux L-systems, à l’algèbre linéaire, aux systèmes de numération et aux généralisations en dimensions supérieures
  • En partant d’un carré, on réplique la forme courante vers le haut, le bas, la gauche et la droite, puis, à l’étape suivante, on la réplique dans des directions tournées d’environ 27 degrés ; cette procédure produit un fractal qui remplit le plan
  • De simples règles de L-system R → RLR, L → RLL produisent un contour similaire, mais pas la même figure ; une forme plus courante est documentée sous les noms Quadratic von Koch island, Quadratic Flake, Minkowski Sausage, etc.
  • Le wallflower peut s’interpréter comme un système de numération à base matricielle, avec la matrice (M=\begin{bmatrix}-2&1\1&2\end{bmatrix}) comme base et des vecteurs de direction comme chiffres ; (\det(M)=-5) inverse l’orientation à chaque itération
  • La généralisation en 3D s’est révélée maladroite à cause de problèmes de symétrie et de chevauchement ; en 4D, une matrice satisfaisant les contraintes a permis de créer l’orthotopeflower, mais avec les mêmes contraintes seules les dimensions 1D, 2D et 4D semblent possibles

Le point de départ du fractal accroché au mur

  • Au collège, j’ai dessiné sur du papier quadrillé un gribouillage qui combinait et répliquait des carrés à répétition, puis je l’ai accroché au mur pour l’analyser plus tard
  • En raison de sa structure qui s’étend comme des pétales et de l’histoire de son long séjour au mur, j’appelle ce fractal wallflower
  • La procédure d’origine était la suivante
    • Commencer avec un seul carré
    • Placer 4 copies de l’état courant à gauche, à droite, au-dessus et au-dessous
    • Ensuite, placer 4 copies de l’état courant dans ces mêmes quatre directions, mais à des positions inclinées d’environ 27 degrés dans le sens horaire
    • Répéter en alternant ces deux modes de placement jusqu’à remplir le papier quadrillé
  • Comme la courbe de Gosper, cette procédure peut, si on l’itère, couvrir n’importe quelle région du plan, et chaque état intermédiaire peut aussi paver le plan

Presque comme un L-system, mais avec un contour différent

  • Il y a environ un an, j’ai vu que ce contour pouvait être produit avec un L-system
  • Les règles utilisées ne reposent que sur des rotations de 90 degrés vers la droite (R) et vers la gauche (L)
    • La chaîne initiale est (RRRR)
    • À chaque itération, on remplace (R \rightarrow RLR) et (L \rightarrow RLL)
  • Les premières étapes semblaient avoir le même contour que le wallflower, mais en créant une animation, j’ai constaté qu’à partir de la 4e itération, les deux méthodes divergeaient
  • La différence vient de la façon de placer les copies
    • La méthode “drag and drop” place directement les copies de la 3e itération en haut, en bas, à gauche et à droite par rapport au centre
    • La méthode L-system place les copies en diagonale
  • La forme produite par le L-system est déjà documentée à plusieurs endroits
  • Pour la variante drag and drop qui était sur le mur, je n’ai pas trouvé de forme identique via Google Images ni en parcourant Wikipédia
  • J’ai trouvé des règles correspondant au wallflower, (L \rightarrow RLR), (R \rightarrow LLR), mais elles ont pour effet d’inverser le sens de tracé du contour à chaque étape

Une façon de compter le fractal

  • Comme le wallflower grandit depuis l’origine vers l’extérieur, on peut le voir comme une correspondance entre les entiers naturels et les coordonnées d’une grille
  • On place le carré central à 0, puis on numérote les 4 carrés ajoutés autour à la première itération 1, 2, 3, 4 dans le sens horaire
  • À l’itération suivante, on pourrait aussi les numéroter en les parcourant de haut en bas et de gauche à droite, mais cette méthode s’accorde mal avec la structure récursive
  • En utilisant le fait que chaque pétale est une copie de l’itération précédente, on peut réutiliser une numérotation du centre vers l’extérieur aussi bien à l’intérieur des pétales qu’entre eux
  • Avec cette numérotation, les multiples de 5, les (5n+1), les multiples de 25, etc. forment des motifs de grille inclinés
  • La raison est que le nombre de carrés à chaque itération augmente comme (1, 5, 25, 125, ...)
    • Chaque itération ajoute 4 copies à l’état précédent, pour un total multiplié par 5
    • Les puissances de 5 et l’écriture en base 5 s’accordent donc bien avec la structure

Un système de numération à base matricielle

  • Si l’on décompose un nombre comme des chiffres en base 5, on peut trouver sa position dans la grille fractale en additionnant les vecteurs correspondant à chaque valeur de position
  • Par exemple, on considère 231 comme (200 + 30 + 1), puis on additionne les vecteurs de position correspondants pour obtenir la position de 231
  • Les valeurs à un chiffre sont définies comme des vecteurs de direction
    • (\vec{0}=(0,0))
    • (\vec{1}=(1,0))
    • (\vec{2}=(0,1))
    • (\vec{3}=(-1,0))
    • (\vec{4}=(0,-1))
  • Les valeurs de position de la forme (10^n) avaient d’abord été exprimées par des conditions dépendant de la parité, mais on peut les calculer sans condition en appliquant une seule matrice à répétition
  • La matrice utilisée est la suivante

[ M=\begin{bmatrix} -2 & 1 \ 1 & 2 \end{bmatrix} ]

  • Cette matrice vérifie (M^2=5I), ce qui réaligne l’échelle d’un facteur 5 toutes les deux étapes
  • On peut donc l’exprimer ainsi

[ \overrightarrow{(10^n)}=M^n\vec{1} ]

  • Cette structure peut être vue comme un système de numération utilisant une base matricielle et des chiffres vectoriels, au lieu d’une base scalaire et de chiffres scalaires comme dans les bases habituelles

Le déterminant sépare les deux fractals

  • Le déterminant de (M) est (\det(M)=-5), et ce déterminant négatif inverse l’orientation de l’espace à chaque itération
  • À cause de cette inversion, des valeurs comme 20 et 40 semblent échanger de position par rapport à la numérotation d’origine
  • Pour éviter cette inversion, on peut choisir une matrice à déterminant positif

[ M'=\begin{bmatrix} 2 & 1 \ -1 & 2 \end{bmatrix} ]

[ \det(M')=5 ]

  • (M') n’inverse pas l’orientation et continue à faire tourner les vecteurs chiffres dans le sens horaire ; utilisée comme base, cette matrice reproduit la version L-system mentionnée plus haut
  • La différence entre les deux fractals est la suivante
    • Le wallflower vient de (M), avec (\det(M)=-5)
    • La famille plus courante des quadratic flakes vient de (M'), avec (\det(M')=5)
  • La valeur absolue 5 du déterminant correspond au fait que la taille du fractal est multipliée par 5 à chaque itération
    • Si le déterminant était plus grand, les copies grandiraient trop vite et laisseraient des vides
    • S’il était plus petit, les copies grandiraient trop lentement et les itérations se chevaucheraient
  • L’angle d’environ 27 degrés est lié au vecteur (\langle1,2\rangle), qui découle des contraintes de coordonnées entières, de déterminant (\pm5) et de norme vectorielle (\sqrt5)
    • L’angle de ce vecteur est (\arctan(2/1)\approx63.43^\circ)
    • Par rapport à l’axe y, il s’écarte d’environ 27 degrés

Règles d’addition et retenues

  • L’addition vectorielle convient bien aux valeurs de position développées, mais elle ne se comporte pas comme l’addition numérique ordinaire, par exemple (\vec{2}+\vec{2}\neq\vec{4})
  • Il est plus naturel de voir 1 à 4 non pas comme de vrais chiffres, mais comme les directions haut, droite, bas et gauche
  • Les directions opposées s’annulent
    • (\vec{1}+\vec{3}=\vec{0})
    • (\vec{2}+\vec{4}=\vec{0})
  • Si l’on dresse une table des combinaisons de vecteurs unitaires, certains résultats d’addition deviennent des valeurs à deux chiffres
  • C’est pourquoi, pour additionner de grands nombres, il faut gérer les retenues, comme dans une addition posée classique
  • Par exemple, si l’on calcule (\vec{22}+\vec{1}), la règle (\vec{2}+\vec{1}=\vec{13}) donne le résultat 133
  • Je ne prouve pas que ce système d’addition fonctionne en général et laisse cette vérification aux lecteurs

Systèmes de numération et recherches connexes

  • Le système de numération du fractal wallflower se rattache à d’autres bases qui n’utilisent pas seulement des entiers naturels comme chiffres
  • Le ternaire équilibré utilise (-1,0,1) comme chiffres et 3 comme base ; le wallflower peut être vu comme un analogue bidimensionnel qui y ajoute les chiffres correspondant aux directions positive et négative de l’axe y
  • Le ternaire équilibré généralisé se généralise à des dimensions quelconques via des grilles de permutoèdres ; en 2D, cela donne une grille hexagonale
  • La base quater-imaginaire est un système qui utilise (2i) comme base et 0, 1, 2, 3 comme chiffres
  • (M') peut être vu comme une base correspondant au nombre complexe (2+i), et Balanced base 2+i (and some gratuitous fractals) de Timothy James McKenzie Makarios traite ce concept
  • J’ai trouvé les ressources connexes suivantes
    • Project BinSys : un projet visant à trouver une base matricielle dont le déterminant vaut 2
    • Replicating Tesselations d’Andrew Vince : un traitement plus rigoureux des fractals, pavages, de l’algèbre linéaire et des systèmes de numération, avec une extension au-delà de (\mathbb{Z}^2) vers des réseaux généraux

Extension en 3D et 4D

  • En 3D, on envisage une structure “3D plus” qui part d’un cube et le copie dans les six directions
  • Les conditions souhaitées pour une matrice 3x3 sont les suivantes
    • Toutes les entrées doivent être entières
    • Chaque vecteur colonne doit être à distance de Hamming 3 de l’origine
    • Comme chaque itération ajoute 6 copies, la taille doit être multipliée par 7, et le déterminant doit être (\pm7)
  • J’ai trouvé une matrice 3x3 satisfaisant ces conditions, mais la visualisation donnait une forme comme écrasée, avec l’itération précédente qui restait visible
  • En ajoutant deux “3D plus”, il a été possible de combler les vides, et les 8 points centraux se sont disposés comme les sommets d’un cube tordu
  • Pour une disposition plus symétrique, il pourrait suffire que chaque colonne soit orthogonale aux autres et de même norme, mais en 3D cela semble impossible avec la contrainte de coordonnées entières
  • En 4D, les conditions s’accordent
    • Il suffit que la somme des carrés des composantes de chaque vecteur colonne soit 3
    • Il est possible de prendre, parmi les 4 composantes, trois valeurs (\pm1) et une valeur 0
  • Le fractal 4D est construit avec la matrice 4x4 suivante

[ \begin{bmatrix} 0 & -1 & -1 & -1 \ 1 & 0 & -1 & 1 \ 1 & 1 & 0 & -1 \ 1 & -1 & 1 & 0 \end{bmatrix} ]

  • J’appelle ce fractal 4D orthotopeflower
  • Pour le visualiser, on peut regarder des tranches 3D à valeur (w) fixe, ou représenter une fenêtre à quatre dimensions en plaçant des grilles 7x7 à l’intérieur d’une grille 7x7
  • Dans une fenêtre de visualisation 31x31x31x31, il semble s’étendre vers l’extérieur sans l’écrasement excessif observé en 3D

Dimensions supérieures et dernier retournement

  • Si l’on étend les mêmes contraintes aux dimensions supérieures, seules les dimensions 1D, 2D et 4D semblent les satisfaire
    • En 1D, le ternaire équilibré
    • En 2D, le wallflower ou le quadratic flake
    • En 4D, l’orthotopeflower
  • La matrice choisie en 4D encode le quaternion (i+j+k), ce qui permet d’imaginer une base quaternionique nonaire équilibrée dont la base est (i+j+k) et les chiffres (0,\pm1,\pm i,\pm j,\pm k)
  • Je ne sais pas si ce système de quaternions fonctionne réellement ; je laisse cela à mon futur moi qui connaîtra davantage de mathématiques
  • Après un burn-out, une tentative de raviver mon intérêt pour les mathématiques et la programmation a transformé un vieux gribouillage en exploration reliant fractals, systèmes de numération, algèbre linéaire et dimensions supérieures
  • Dernier retournement : les visualisations de l’article ne correspondent pas au vrai fractal mural visible dans la miniature
    • À la 4e itération, le vrai fractal mural est copié dans la direction opposée d’environ 27 degrés
    • À l’époque, je pensais qu’en continuant à l’incliner dans la même direction il sortirait de l’axe et j’ai essayé de corriger cela, mais la structure de (M) se corrige déjà elle-même à chaque étape
    • Donald Knuth a lui aussi fait un mauvais virage en accrochant un fractal au mur, et c’est là-dessus que l’article se conclut

À lire aussi

1 commentaires

 
GN⁺ 2025-05-23
Commentaires sur Hacker News

  • C’était un texte perspicace et très soigné, et la visualisation 3D était particulièrement réussie
    Ça m’a rappelé quelque chose que j’avais bricolé autrefois en jouant avec une décimation récursive pour produire un effet pseudo-fractal à partir d’une image arbitraire
    On peut l’essayer directement ici : https://jsfiddle.net/nicobrenner/a1t869qf/
    Il suffit d’appuyer plusieurs fois sur Blursort 2x2 pour créer les frames, puis sur Animate. On peut aussi copier/coller des images, et tout s’exécute dans le navigateur sans backend. Je ne le recommande pas sur mobile

    • Je me demande si ça fonctionnerait aussi en 3D

  • Ça m’a tellement captivé que je crois avoir créé, avec un L-system, une forme qui remplit le “wallflower”
    https://onlinetools.com/math/l-system-generator?draw=AB&skip...
    En y repensant, ça génère probablement un autre fractal, mais je n’en suis pas certain

  • Je pensais que ce serait une lecture légère, mais comme je devais travailler, je n’ai pu qu’en parcourir certaines parties
    Je reviendrai plus tard pour tester plein de choses, c’est vraiment un texte très bien fait

  • C’est un texte bien plus profond et exigeant que prévu, on sent le dévouement
    J’aimerais demander à l’auteur ce qu’il recommanderait d’accrocher aujourd’hui sur le mur de la chambre d’un enfant

    • Je ne suis absolument pas spécialiste de l’éducation, mais je dirais que tout ce qui est lié à ce qui suscite chez l’enfant, à ce moment-là, de la passion ou de l’émerveillement est une bonne chose
      J’ai glissé à la fin du texte un petit paragraphe sur le burnout. Dans mon cas, le problème venait au fond de la perte de la fascination et de la curiosité que j’avais pour les maths et la programmation, et écrire ce texte m’a permis de retrouver un peu de cet émerveillement enfantin que je ressentais autrefois si facilement

  • J’ai vérifié l’arithmétique de deux nombres à deux chiffres, et ça fonctionne effectivement
    Je m’attendais à ce que 41+14 donne 12. En effet, deux cases vers la droite et deux cases vers le haut donnent deux cases vers la droite et deux cases vers le haut
    Dans l’addition longue ci-dessous, = sert à montrer des lignes équivalentes, c’est-à-dire une réorganisation des termes (1+2=2+1), une décomposition des nombres (41=40+1) et des additions à un chiffre (1+4=22) ; -> sert quand l’algorithme produit un chiffre ; et < sert à passer à la colonne suivante
    41+14 = (40+1)+(10+4) = 40 + 10 + (1+4) = 40 + 10 + 22 -> 1s digit = 2 < 4 + 1 + 2 = 22 + 2 = 20 + 2 + 2 = 20 + 41 -> 10s digit = 1 < 2 + 4 = 0 -> done == 12
    L’article utilise deux systèmes de base distincts : dans l’un, 10, 20, 30, 40 tournent dans le sens horaire, et dans l’autre dans le sens antihoraire. Dans les deux, 1, 2, 3, 4 tournent dans le sens horaire. L’addition ci-dessus se base sur le second système montré dans la table d’addition, celui où les dizaines tournent dans le sens antihoraire
    Ça fonctionne aussi dans l’autre système. 14+21 devrait donner 12
    14+21 =10+20+42 ->2 <1+2+4 =13+4 =10+3+4 =10+31 ->1 <1+3 =0 ==12

  • Je me demande comment l’idée du système de numérotation “middle out” lui est venue
    Quand je fais des maths seul, je n’arrive presque jamais à avoir ce genre d’intuition inspirée

    • Dans le texte, l’ordre paraît un peu différent, mais au final tout est parti du moment où j’ai compris que la façon dont le fractal grandit par 5, le système de numération en base 5 et la “spirale” évoquée dans le texte pouvaient s’emboîter
      J’ai aussi beaucoup réfléchi à la manière de dessiner ce fractal par programme, et la façon naturelle de le faire était de partir du centre et de s’agrandir vers l’extérieur
      Il existe une anecdote sur Richard Feynman : il gardait une douzaine de problèmes aléatoires en arrière-plan dans son esprit, avançait un peu chaque fois qu’il apercevait un lien, puis quand il en résolvait enfin un, les gens avaient l’impression qu’il l’avait trouvé comme par magie sur-le-champ. C’était un peu similaire ici, sauf que je suis très loin de son niveau et que je peux à peine faire ça sur un seul problème, pas sur une douzaine

  • J’avais ça accroché en grand format imprimé au mur de mon ancien lieu de travail
    https://raw.githubusercontent.com/cies/haskell-fractal/refs/... [17MB, désolé, c’est sur Github]
    Le code Haskell utilisé pour le générer est aussi inclus : https://github.com/cies/haskell-fractal
    Le processus qui a mené à la fonction sharpen était particulièrement intéressant. Pour ajuster les courbes, j’avais utilisé un outil aujourd’hui disparu : https://github.com/cies/haskell-fractal/blob/master/fractal....
    C’était un petit projet amusant

  • Le passage “j’ai décidé de déléguer ça à une version future de moi qui connaîtrait davantage de mathématiques” m’a parlé
    Ça a aussi beaucoup pesé dans le choix du diplôme que j’allais faire : il y avait toute une liste de problèmes que je devais résoudre mais que je n’avais pas pu, faute de cartes et de connexion internet suffisante. C’étaient surtout des problèmes d’algèbre linéaire

  • Il semble y avoir une coquille dans la formule du motif. Juste après “Looking closely you might pick up on the pattern”, l’expression devrait être 5**(n/2) au lieu de 5**n, et 5**((n-1)/2) au lieu de 5**(n-1)
    \overrightarrow{10*4} vaut [0, 25], mais avec la formule d’origine on obtient [0, 625]
    Par ailleurs, à propos de l’erreur de Knuth, quelqu’un dit dans les commentaires YouTube que son fractal était en fait correct et qu’il avait simplement confondu le point de départ et le point d’arrivée. En gros, ce fractal est symétrique par rapport à une rotation centrale, et c’est précisément cette rotation que Knuth croyait erronée. Cela dit, ça reste bien une erreur liée au fractal, donc la conclusion tient toujours

    • Bien vu, j’ai corrigé la formule