Pavage à tuile unique (avec retournement)

jacquot

Bonjour,

Après une courte recherche sur le forum, je n'ai pas trouvé de discussion concernant le pavage dit "einstein" à tuile unique publié en mars 2023 par Smith, Myers, Kaplan et Goodmann-Strauss. Si je me trompe, le lecteur voudra bien m'orienter vers cette discussion.
Je colle ci-dessous deux liens vers des présentations de ce nouveau pavage qui constitue une avancée dans le domaine des pavages non-périodiques du plan.

* Un pavage non périodique avec une tuile unique | Pour la Science
* 2303.10798.pdf (arxiv.org)

et une image 


La performance réalisée par cette invention est de proposer un pavage non périodique du plan à l'aide d'une tuile unique.
Un examen un peu plus attentif de l'image fera faire la fine bouche aux puristes : ce n'est pas tout à fait un pavage à tuile unique, puisque les tuiles ne sont pas toutes directement superposables: les bleues foncées ont été retournées, elles ne sont superposables aux autres que moyennant une symétrie axiale composée avec un déplacement. 

Les mathématiciens considèrent cependant que ce pavage est réellement innovant, qu'il se distingue des pavages de Penrose et la publication a été remarquée et commentée dans la presse.

J'ai lu en diagonale le document Arxiv , m'arrêtant surout aux images, puisque je ne lis toujours pas bien l'anglais.
Je me suis surtout attardé aux pages 15 et 16 du document arXiv où est présenté un algorithme qui permet de recouvrir progressivement le plan en assemblant des fractales (triangle, parallélogramme, Flèche et Motif) de plus en plus gandes.

Je me suis intéressé à la fréquence des tuiles bleues (retournées) dans cette structure, et à l'aide du tableur, j'observe que cette fréquence se stabilise rapidement aux alentours de 
$$\dfrac 1 {1+\varphi^4}$$ (où $\varphi$ est le nombre d'or).
La démonstration sera cependant un peu compliquée à mettre en forme.
Si quelqu'un est intéressé, je voudrai bien en discuter ici ou bien dans une autre discussion relative à ce pavage "einstein" et présenter mes arguments

Quoiqu'il en soit si nous arrivons à montrer proprement que la fréquence des retournées est bien celle-là, nous aurons en même temps démontré la non-périodicité du pavage puisque cette limite est irrationnelle.

Amicales salutations à mes amis du forum Les-Mathématiques.net et à tous les nouveaux inscrits.
jacquot

Ludwig

Bonjour
Un des auteurs de l'article a posté une animation sur youtube, avec ce commentaire :
Dans notre article, nous présentons une seule forme appelée "le chapeau" qui pave le plan de manière apériodique. Cette forme s'avère n'être qu'un point dans un continuum plus large de formes connexes. Dans cette vidéo, nous nous déplaçons en douceur dans l'espace de toutes ces formes. La seconde moitié de la vidéo est l'inverse de la première ; le tout est fait pour être regardé en boucle. Les formes affichées au début (et à la fin), à la position 1/4 (et 3/4) et à la position 1/2 sont des cas dégénérés qui peuvent également se mosaïquer périodiquement. Toutes les autres formes sont apériodiques. (traduction google).
Je n'ai pas trouvé dans leur article comment construire cette famille de tuiles. Est-ce expliqué ailleurs ?

Dom

Bonjour,
j’ai lu un peu wiki mais n’ai pas bien compris ce que signifie « périodique/apériodique » pour un pavage. 

Est-ce l’idée imagée suivante ? « on ne retrouve pas le même motif par une translation ». 

Cordialement.

gerard0

Plus exactement, aucune translation autre que l'identité ne transforme le motif en lui-même.
Cordialement. 

Dom

Ok. 👍

Math Coss

Un pavage de $\R^2$ est un ensemble $\mathscr P$ de parties du plan qui le recouvre en entier ($\ \bigcup_{P\in\mathscr P}P=\R^2$) et dont les pièces ne se chevauchent que sur leur bords (pour $P,P'\in\mathscr{P}$, $\ P\cap P'\subset \partial P\cap\partial P'$, où $\partial$ désigne le bord : adhérence privée de l'intérieur).
Un pavage est apériodique si pour la seule translation $t$ telle que $t(\mathscr P)=\mathscr P$ (où $t(\mathscr{P})=\{t(P)\mid P\in\mathscr P\}$) est l'identité.

lourrran

J'ai quand même un peu de mal à concevoir qu'un pavage infini soit apériodique ; je pense que ça va occuper mon cerveau pendant quelques heures de sport.

Dom

Oui lourrran, mais en imaginant qu’un motif se déduit de l’autre par une rotation d’angle « non rationnel fois $\pi$ », ça peut s’entendre. 

R.E.

jacquot, j'en avais parlé dans mon fil d'actu ici, ici et ici.
Mais tu as eu raison d’ouvrir un fil dédié, cette découverte le mérite largement. Elle a donné lieu à de nombreuses publications et engagements.

Math Coss

@lourrran : On s'en convainc avec par exemple les tuiles de Robinson, qui font apparaître des carrés de toutes tailles ; en choisissant un tel carré beaucoup plus grand qu'un vecteur de translation qui préserve hypothétiquement le pavage, on ne voit pas comment il pourrait être préservé. Cf. https://fr.wikipedia.org/wiki/Pavage_apériodique#Pavages_apériodiques_hiérarchisés.

lourrran

@Dom
Oui, en écrivant mon message, j'ai soudain envisagé ces rotations, mais le dessin est clair, on a des droites (infinies) sur 3 directions, et tous les segments de la figure sont portés par ces droites. Donc pas de rotation 'non rationnel fois $\pi$ ' dans cette histoire.
Merci MathCoss pour le lien wikipedia, je pars faire ma marche quotidienne, ça va bouillonner là-haut.

jacquot

Merci à tous pour ces réponses.
@Dom
apériodique ou non-périodique signifie effectivement non-superposable à lui-même par une translation autre que l'identité.
Le pavage est extensible par agencenment de structures fractales de plus en plus grandes. Ici,quatre fractales sont en en jeu, un triangle, un trapèze, une "flèche" et un quatrième motif, sorte de triangle à coins coupés un peu comme le logo du Crédit Mutuel (voir page 15 de l'article arXiv) 

J'ai calculé que la fréquence des tuiles retournées tend vers une limite de $\dfrac 1{1+\varphi^4}$ dans ce développement. Si cette limite est irrationnelle, cela prouve qu'il n'existe pas de supertuile capable de recouvrir le plan tout entier par translations.

J'essayerai de donner une démonstration de cette fréquence, mais ce sera assez difficile à rédiger. En tous cas , je pourrai présenter quelques arguments convaincants et peut-être se trouvera-t-il parmi vous des lecteurs qui pourrront m'aider à articuler une preuve bien construite.

J'attire cependant votre attention sur le fait que les supertuiles présentées pages 15 et 16 n'ont pas des frontières nettes, c'est pourquoi je parle d'une extension de type fractale.

Peut-être ma piste est-elle originale, car j'ai lu dans Pour la Science qu'une preuve de la non-périodicité requiert une assistance informatique. Ce ne serait pas le cas pour la preuve que je propose : il s'agirait d'une récurrence avec des nombres de Fibonacci.
De prime abord, il est assez inattendu de voir intervenir le nombre d'or dans ce pavage, mais quand on embraye la récurrence, on veut bien travailler avec les nombres de Fibonacci...
@ suivre : je posterai plus longuement quand j'aurai un peu de temps pour ce faire. 

P.S. Merci @R.E. pour les liens vers l'ancienne discussion sur le sujet.

lourrran

C'est un détail, mais je n'aime pas l'écriture $\frac {1}{1+\varphi^4}$ , je préfère $\frac{1}{3 \times (1+\varphi)}$
Et quelque chose me dit que cette 2ème écriture est plus 'facile à démontrer' que la première. 

jacquot

D'accord avec ton égalité, @lourrran, mais c'est bien $\dfrac 1{\varphi^4+1}$ que j'ai obtenu dans mon étude.
Qu'on l'écrive comme ceci ou comme cela, l'essentiel est ici que cette limite est  irrationnelle ....
@ suivre.

jacquot

Voici donc un exposé de mon étude:

Je me réfère aux pages 15 et 16 du document arXiv où les auteurs présentent un algorithme d'extension du pavage à chemises (ou à chapeaux) par des supertuiles de type fractales

Ils considèrent 4 types de supertuiles que j'apellerai Triangles, Parallélogrammes, Flèches et Motifs (genre logo du Crédit Mutuel). Le schéma d'extension est résumé par les schémas suivants


À un rang $n$ donné, je note $T_n ; P_n ;  F_n$ et $M_n$ le nombre de tuiles contenues dans chacune de ces supertuiles.
Les auteurs ont bien étudié la capacité de ces supertuiles à bien s'assembler bord à bord.
On pourra remarquer que ma supertuile Motif est un peu différente de celle qui est présentée à la page 15 du dcument arXiv, puisqu'elle a des parties non remplies à ses sommets, mais peu importe !

Le schéma d'assemblage donne les relations de récurrence suivantes :
$T_{n+1}=M_n$
$P_{n+1}=P_n+2(M_n + F_n)$
$F_{n+1}=F_n +P_{n+1}$
$M_{n+1}=T_n+3(M_n+P_n+F_n)$

À ce même rang $n$, je peux noter  $Tr_n ; Pr_n ;  Fr_n$ et $Mr_n$ le nombre de tuiles retournées (bleues foncées) contenues dans chacune de ces supertuiles, et j'obtiendrai  des relations de récurrence tout à fait semblables à celles qui sont écrites ci-dessus.
J'ai alors mis tout ça dans un tableur Excel pour voir ce que ça donne. Voici : 

Triangle		Parallélogramme		Flèche		Motif
1	0	2	0	2	0	4	1
4	1	14	2	16	2	25	3
25	3	96	12	112	14	169	22
169	22	658	84	770	98	1156	147
1156	147	4510	574	5280	672	7921	1009
7921	1009	30912	3936	36192	4608	54289	6912
54289	6912	211874	26976	248066	31584	372100	47377
372100	47377	1452206	184898	1700272	216482	2550409	324723
2550409	324723	9953568	1267308	11653840	1483790	17480761	2225686
17480761	2225686	68222770	8686260	79876610	10170050	119814916	15255075
119814916	15255075	467605822	59536510	547482432	69706560	821223649	104559841
821223649	104559841	3205017984	408069312	3752500416	477775872	5628750625	716663808
5628750625	716663808	2,1968E+10	2796948672	2,572E+10	3274724544	3,858E+10	4912086817
3,858E+10	4912086817	1,5057E+11	1,9171E+10	1,7629E+11	2,2445E+10	2,6443E+11	3,3668E+10
2,6443E+11	3,3668E+10	1,032E+12	1,314E+11	1,2083E+12	1,5384E+11	1,8124E+12	2,3076E+11
1,8124E+12	2,3076E+11	7,0735E+12	9,0061E+11	8,2818E+12	1,0545E+12	1,2423E+13	1,5817E+12

 
Pour chaque forme, la première colonne donne les $T_n ; P_n ; ...$ etc, la deuxième colonne donne les $Tr_n ; Pr_n ; ...$ etc .
Je marque une pause et continue dans un message ultérieur.

jacquot

Pour interpréter ces valeurs, je me réfère à la suite de Fibonacci définie par $f_0=1$ ; $f_1=1$ et la relation de récurrence $f_{n+1}=f_n+f_{n-1}$ dont les termes à partir de $f_0$ sont :
$1 ; 1 ; 2 ; 3 ; 5 ; 8 ; 13 ; 21 ; 34 ; 55 ; 89 ; 144$ etc.

J'ai remarqué successivement que pour ces premières valeurs  :
$M_n= f_{2n}^2$ 
$T_n=f_{2n-2}^2$
$F_n=\dfrac 2 3 f_{2n+1}\times f_{2n-1}$
$P_n = 2f_{2n}\times f_{2n-1}-\dfrac 1 3 f_{2n+1}\times f_{2n-1}$ puisque $P_n+F_n =  2f_{2n}\times f_{2n-1}$

La pérennité de ces égalités pourra se démontrer par récurrence.


Pour ce qui concerne les nombres de tuiles bleues dans chaque supertuile fractale, mon observation se limitera à une relation  $$ Xr_{n+1}=X_n-Xr_n$$
Et ce, quelle que soit la forme considérée : Triangle, Parallélogramme, Flèche ou Motif.
Cette égalité pourra elle-aussi être pérennisée par récurrence !

Par ailleurs, si au départ, la fréquence des tuiles retournées n'est pas la même dans le triangle, dans le parallélogramme ou dans le Motif, ces fréquences tendront rapidement à se stabiliser, puisqu'à chaque rang de l'extension du pavage on va moyenner ces fréquences. D'où la convergence des fréquences vers une valeur commune indépendante de la forme considérée.

J'en viens maintenant au calcul de cette limite : je me restreins au cas du Motif:
On a : $Mr_{n+1}=M_n-Mr_n$

donc :  $\dfrac {Mr_{n+1}} {M{n+1}} = \dfrac{M_n}{M_{n+1}} -\dfrac {Mr_n}{M_{n+1}} = \dfrac{M_n}{M_{n+1}} (1-\dfrac {Mr_n} {M_n})$

en passant à la limite : $\dfrac {Mr_{n+1}} {M_{n+1}}$ et $\dfrac {Mr_n} {M_n}$ ont une limite commune que je noterai $\ell$ et qui est la fréquence cherchée, tandis que $\dfrac{M_n}{M_{n+1}}  =\dfrac {f_{2n}^2}{f_{2n+2}^2}$ .
La limite de ce rapport quand $n$ tend vers l'infini est $ \dfrac 1 {\varphi^4}$ puisque la limite du rapport de deux termes consécutifs de la suite de Fibonacci est le nombre d'or.

On a donc l'équation $\ell = \dfrac{1-\ell}{\varphi^4}$ .

La solution est $\ell = \dfrac 1{1+\varphi^4}$

Voilà. J'attends vos remarques ou questions. Amicalement. jacquot

lourrran

Je te dois une réponse, parce que j'ai chipoté sur l'écriture de ta limite.
1. Tu dis $l= 12.7$% : à l’œil, c'est cohérent, c'est à peu près ce qu'on peut compter sur les dessins.
2. L'idée de dire : la proportion est un nombre irrationnel, et donc le pavage est apériodique, vu de ma fenêtre, c'est astucieux. Intuitivement, c'est correct, peut-être faut-il ajouter un théorème qui confirme cette dernière étape.
3. Évidemment, il manque des calculs, les récurrences que tu mentionnes, mais c'est de la cuisine. Le plan me semble bon.

Je valide.

jacquot

Salut @lourran !
Merci de t'être donné la peine de lire et de  me répondre.
J'ai un petit doute concernant la définition de la non-périodicité qui a été donnée plus haut: existence d'une translation de vecteur non nul laissant le pavage globalement invariant : on pourrrait alors avoir une bande de largeur $l$ et de longueur infinie que l'on pose côte à côte comme des lés de papier peint, Auquel cas l'irrationnalité due la fréquence des retournées ne serait pas suffisante !

Moi, j'interprétais  la non-périodicité comme non-existence d'une super-tuile finie qui permettrait de paver le plan par translations. Cette super-tuile présenterait alors un ratio de retournées qui serait un quotient d'entiers et qui s'étendrait alors au plan tout entier. J'avais vu  des études des pavages de Penrose qui jouaient de cet argument pour justifier la non-périodicité, je n'ai donc rien inventé.

Ma non-périodiocité requiert donc une invariance globale par deux translations de vecteurs non-colinéaires....
J'ai cependant l'impression qu'ici, si une translation de vecteur non-nul laisse le pavage invariant, la translation suivant son tourné de $120°$ fera de même, mais ça reste à prouver.

Tu as raison, il faudrait mettre les mains dans le cambouis et présenter les récurrences. Crois-moi sur parole, je l'ai fait mais c'est fastidieux à taper en LaTeX.
Je l'ai d'ailleurs fait un peu à l'envers, car si j'ai vu de mes yeux que $M_n = f_{2n}^2$, je n'ai deviné que plus tard les expressions de $P_n$ et $F_n$ qui permettent de faire fonctionner les récurrences avant de constater que c'étaient les bonnes.

Entretemps, j'ai écrit aux auteurs de façon un peu culottée, mais après-tout, ce ne sont pas des extraterrestres ! Et Kaplan m'a répondu très aimablement :
"Yes, the irrational proportion of flipped tiles is sufficient to prove that the specific tiling that you get by applying our substitution rules is non-periodic"
"However, this fact is *not* sufficient for proving the stronger property of *aperiodicity*, namely that every tiling by the hat must be non-periodic"

Apparemment dans leur document ils prouvent quelque chose de plus fort, à savoir que tout pavage qui combinerait des tuiles-chemises et des retournées serait forcément non-périodique. Je ne maîtrise pas assez l'anglais pour lire leur document de A à Z.

Il m'écrit aussi qu'un certain Adam Goucher a calculé la fréquence des retournées avant moi, obtenant $\varphi^4$ pour le rapport non-retournées / retournées ce qui est cohérent avec ma fréquence de $\dfrac 1{1+\varphi^4}$
Voir ici : https://cp4space.hatsya.com/2023/03/21/aperiodic-monotile/
Goucher travaille avec une matrice et un eigenvector, vecteur-propre, il met en jeu des notions mathématiques que je ne maîtrise pas bien, je crois qu'il doit y avoir du théorème de Perron-Frobenius là-dessous.

Bref, tout ceci est intéressant, encourageant et je reste stupéfait de la gentillesse de Craig Kaplan qui m'a répondu dans la journée !
Amicalement. jacquot

Calli

Bonjour,

jacquot a dit :

J'ai un petit doute concernant la définition de la non-périodicité qui a été donnée plus haut: existence d'une translation de vecteur non nul laissant le pavage globalement invariant [...]

Wikipédia donne la définition suivante, qui est plus forte que la non existence d'une translation non triviale laissant invariant le pavage :

On appelle pavage apériodique un pavage (non périodique) ne contenant pas de parties périodiques arbitrairement grandes (pour éviter des pavages non périodiques tels qu'un pavage périodique déformé en un nombre fini d'endroits, et qu'un pavage périodique déformé en un nombre infini d'endroits « isolés » (distribués « non uniformément »)).

lourrran

Effectivement, on a 2 propriétés différentes. 
J'ai des tuiles, je les dispose d'une façon un peu originale et alambiquée, et j'obtiens un truc apériodique. 
Si je les posais de façon différente, pourrais-je avoir un truc périodique, that is the question. Et ce n'était pas flagrant en lisant en diagonale tout ça que cette 2ème question était également abordée.

Je comprends complètement ta réaction : waohhh, j'ai eu une réponse ! Mais je pense que c'est parce que ton travail était de qualité. Tu as trouvé la bonne proportion, tu as eu la bonne idée de l'irrationnalité ... c'est pas mal du tout.

Bravo. Même moi, je suis content d'avoir été en contact avec quelqu'un qui a été en contact avec Dieu.

jacquot

Merci @Calli et @lourran
Cet argument de partie périodique arbitrairement  grande me semble régler son compte aux lés de papier peint évoqués plu haut : 
La partie périodique arbitrairement grande serait alors une bande de longueur infinie qui croise tous les lés...

Boécien

Dans le sujet, je signale cette video sympathique.

jacquot

Bonjour,
Continuant à me renseigner sur les pavages apériodiques, je tombe sur le pavage de Voderberg.


De prime abord, il me semble posséder toutes les qualités requises pour un "einstein", tuile unique permettant un recouvrement apériodique du plan sans retournement. Quelque chose m'aurait-il échappé ?

Le critère de non-périodicité doit sans doute être précisé. 
Pour ce pavage de Voderberg, les spires vont présenter des sections rectilignes de plus en plus longues. N'est-il pas apériodique malgré cela ?

Amicalement. jacquot

gerard0

Jacquot, il a fallu 2 tuiles, regarde le début des spirales.
Cordialement. 

jacquot

Non @gerard0, la tuile de Voderberg est très chiadée : il suffit de deux pour envelopper complètement une troisième. Sur la figure, on a alterné les couleurs pour permettre une bonne lisibilité,  mais il n'y a qu'une tuile auto-enveloppante avec sa fine queue de scorpion.
Regarde bien, Gérard et, si nécessaire,  clique sur le lien vers Wikipédia que j'ai inséré dans mon message précédent. Amicalement. jacquot.

gerard0

Ah oui, tu as raison !

Heuristique

@jacquot Je pense que le problème de ce pavage vient du fait qu'il faut une infinité de tuiles pour le réaliser : une tuile à rotations et symétries près mais une infinité une fois ces transformations appliquées.

Ludwig

Oui extra cette tuile de Voderberg. Je l'ai construite à partir du polygone régulier à 24 côtés, ce qui permet de facilement voir pourquoi 2 tuiles entourent 1 tuile (via une rotation de 15°).
Voici aussi un lien vers un article intéressant de Pour La Science.

jacquot

Bonsoir @Heuristique,

Je ne comprends pas bien ton message : 
pour recouvrir le plan tout entier, il faudra évidemment une infinité de tuiles ! Mais dans le cas du pavage de Vodeberg,  toutes ces tuiles seront directement superposables. On peut donc considérer qu'il utilise (un modèle) de tuile unique. De plus, ce pavage, de type enroulement spiralaire est bien apériodique,  me semble-t-il.
Je t'invite à bien regarder comment Voderberg prend les virages par juxtaposition de ses tuiles, parfois retournées par symétrie centrale (rotation de 180° )pour ne pas tourner trop vite. 

@tous,
Entretemps,  j'ai écrit à l'auteur principal de la page 
https://en.m.wikipedia.org/wiki/Einstein_problem 
du Wikipedia anglophone.
Il me répond, en substance, que le défi du problème einstein n'est pas de trouver une tuile unique qui permet de recouvrir le plan par un pavage apériodique,  mais que de plus, cette tuile ne permette pas de recouvrir le plan par un pavage périodique. 

Or la tuile de Voderberg permet un recouvrement périodique.
Il me dit aussi que des rectangles permettraient de composer un recouvrement apériodique...
Essayons de voir comment  !

Amicalement. jacquot 

jacquot

Merci pour ton lien vers Pour la Science, @Ludwig !
Merci aussi pour le partage de cette construction sur Geogebra qui pourra alimenter la réflexion des lecteurs. 
Amicalement.  jacquot

Calli

jacquot a dit :

Il me dit aussi que des rectangles permettraient de composer un recouvrement apériodique...
Essayons de voir comment  !

Voici une possibilité. On commence par un pavage totalement régulier par un quadrillage de carrés $2\times 2$. Puis on coupe chaque carré en deux dominos $2\times 1$ dans le sens horizontal ou dans le sens vertical. On décide de l'orientation aléatoirement pour chaque carré, avec proba $\frac12$ pour chaque orientation, et les choix sont faits indépendamment pour les différents carrés. Alors la proba que le pavage obtenu soit apériodique* est égale à 1. Donc il existe bien un pavage apériodique* du plan par des dominos !

*Edit : Plus exactement j'obtiens un pavage stable par aucune autre translation que l'identité, mais il possède des sections périodiques finies de taille arbitrairement grande. Donc il n'est pas vraiment apériodique selon la définition de Wikipédia que j'ai moi-même citée. 😊

jacquot

Merci @Calli, pour cette contribution.
J'avais également pensé à des carrés que l'on  couperait horizontalement ou verticalement...
Mais ensuite, j'imaginais un enroulement de type escargot où la direction de découpe des carrés serait définie par la parité des chiffres du développement décimal de $\pi$ ou par ses chiffres dyadiques. 
Ton idée  d'introduire l'aléa laisse planer une incertitude et je ne comprends pas comment tu en arrives finalement à la conclusion qu'il y aura forcément des parties périodiques arbitrairement grandes.

Mon idée d'enroulement  n'est peut-être pas meilleure, car il sera difficile de regarder ce qui se passe en-haut, en-bas, à gauche et à droite ! La suite des décimales de $\pi$ est juste une façon déterministe d'introduire quelque chose d'incontrôlable

Je ne suis pas sûr d'avoir bien compris la périodicité  selon Wikipédia et il me semble avoir lu, je ne sais plus sur quel WP, anglophone,  germanophone ou anglophone,  que la notion de périodicité d'un pavage reste à préciser.
Il est vrai que le développement dyadique de $\pi$ contient des suites de zéros arbitrairement longues ou, peut-être,  une numérisation de la Joconde !

En tous cas, je te salue bien amicalement. jacquot 

Guego

Je me suis amusé à programmer le pavage avec carrés à orientations aléatoires de Calli. Ça ressemble à ça :

import numpy.random as rd
rng=rd.default_rng()
import matplotlib.pyplot as plt

L=20	# Nombre de carrés en largeur
H=10	# et en hauteur

for x in range(L):
    for y in range(H):
        a=rng.integers(2)
        if a==0:
            plt.plot([x,x+1,x+1,x,x,x,x+1], [y,y,y+1,y+1,y,y+1/2,y+1/2],"b")
        else:
            plt.plot([x,x+1,x+1,x,x,x+1/2,x+1/2], [y,y,y+1,y+1,y,y,y+1],"b")

plt.axis("off")
plt.axis("equal")
plt.show()

Résultat :

gerard0

On y  repère bien des parties périodiques de longueur allant ici jusqu'à 18 (partie droite de la première colonne de carrés $2\times 2$).

Examinons un carré $2\times2$ et ceux qui sont à sa droite. Il y a 2 dispositions des carrés, donc une chance sur 2 que le carré de droite ait la même disposition, une chance sur 2 que le carré suivant ait la même dispositions, etc. la probabilité que les n carrés suivants aient la même disposition, donc qu'on ait une suite périodique de n+1 carrés est $\frac 1{2^n}$. Comme on a une infinité de carrés de départ possibles (même en excluant les suites de n+1 carrés déjà examinées), l'espérance d'obtenir une suite horizontale de n+1 carrés identiques est infinie, quel que soit n. C'est un cas particulier de ce que disait Calli : " il possède des sections périodiques finies de taille arbitrairement grande.".

Cordialement.

Calli

Merci @Guego. J'ai essayé de rajouter des couleurs pour rendre un peu plus attrayant ce pavage pas très sexy (les dominos ça n'est pas la forme la plus originale !).

import numpy.random as rd
rng=rd.default_rng()
import matplotlib.pyplot as plt

L=20	# Nombre de carrés en largeur
H=10	# et en hauteur

for x in range(L):
    for y in range(H):
        a=rng.integers(2)
        if a==0:
            plt.fill([x,x+1,x+1,x], [y,y,y+1/2,y+1/2],"tab:green")
            plt.fill([x,x+1,x+1,x], [y+1/2,y+1/2,y+1,y+1],"g")
            plt.plot([x,x+1,x+1,x,x,x,x+1], [y,y,y+1,y+1,y,y+1/2,y+1/2],'k',linewidth=1)
        else:
            plt.fill([x,x+1/2,x+1/2,x], [y,y,y+1,y+1],"tab:orange")
            plt.fill([x+1/2,x+1,x+1,x+1/2], [y,y,y+1,y+1],"orange")
            plt.plot([x,x+1,x+1,x,x,x+1/2,x+1/2], [y,y,y+1,y+1,y,y,y+1],'k',linewidth=1)

plt.axis("off")
plt.axis("equal")
plt.show()

Calli

jacquot a dit :

Ton idée  d'introduire l'aléa laisse planer une incertitude et je ne comprends pas comment tu en arrives finalement à la conclusion qu'il y aura forcément des parties périodiques arbitrairement grandes.

Étiquetons les carrés à l'aide des éléments de $\mathbb{Z}^2 $. On a une famille de variables aléatoires indépendantes $(X_{p} )_{p\in \mathbb{Z}^2 }$ telles que, pour tout $p\in \mathbb{Z}^2 $, le carré étiqueté par $p$ est coupé horizontalement si $X_{p} =0$ et verticalement si $X_{p} =1$, et $\mathbb{P}(X_{p} =0)=\mathbb{P}(X_{p} =1)= \frac{1}{2}$.

Pourquoi le pavage est presque sûrement stable par aucune translation non triviale ?

Parce que toute translation est associé à un vecteur $v\in \mathbb{Z}^2 $. Et si le pavage est stable par la translation $\tau _{v} : p\mapsto p+v$ alors : $\forall p\in \mathbb{Z}^2 ,\; X_{p}= X_{p+v}$. En particulier : $\forall n\in \mathbb{N}^*, X_{nv} =X_{0}$. Et la proba que ça arrive est $\prod_{n=1}^\infty  \mathbb{P}(X_{nv} =X_{0} )=\prod_{n=1}^\infty  \frac{1}{2} =0$ à condition que $v\neq 0$. Donc \[\mathbb{P}(\exists \text{ translation $\tau $ non triviale, tq le pavage est stable par }  \tau  )\leqslant  \sum _{v\in \mathbb{Z}^2  \setminus \{(0,0)\}} \mathbb{P}(\text{le pavage est stable par }  \tau _{v} ) =0\] car $\mathbb{Z}^2  \setminus \{(0,0)\}$ est dénombrable.

Pourquoi le pavage contient presque sûrement des parties périodiques arbitrairement grandes ?

Il suffit de montrer que, presque sûrement, pour tout $L\in \mathbb{N}$, le pavage contient un grand carré de largeur $L$ petits carrés qui ne contient que des dominos horizontaux. Pour tous $L\in \mathbb{N}^*$ et $q\in \mathbb{Z}^2 $, notons $C_{L,q} = \{Lq+p \mid p\in [\![0,L-1]\!]^2 \}$. C'est un sous-ensemble de $\mathbb{Z}^2 $ en forme de grand carré de largeur $L$ et son coin inférieur gauche est $Lq$.  Alors il suffit de montrer que : \[\mathbb{P}(\forall L\in \mathbb{N}^*, \exists q\in \mathbb{Z}^2 , \forall p\in C_{L,q} ,\; X_{p} =0) =1.\] Or, pour tout $L\in \mathbb{N}^*$, on a : \[\begin{align*} \mathbb{P}(\exists q\in \mathbb{Z}^2 , \forall p\in C_{L,q} ,\; X_{p} =0) &= 1-\mathbb{P}(\forall q\in \mathbb{Z}^2 , \neg(\forall p\in C_{L,q} ,\; X_{p} =0)) \\ &=^* 1- \prod _{q\in \mathbb{Z}^2 } \big(1-\mathbb{P}(\forall p\in C_{L,q} ,\; X_{p} =0)\big)\\ &= 1- \prod _{q\in \mathbb{Z}^2 } (1- 2^{-L^2 } ) \\ &= 1\end{align*}\] *car pour tous $q\neq q'$ dans $\mathbb{Z}^2 $, $C_{L,q} \cap C_{L,q'} = \varnothing $, donc ces grands carrés sont indépendants les uns des autres. Et comme $L$ appartient à $\Bbb N^*$ qui est dénombrable, on en déduit que $\mathbb{P}(\forall L\in \mathbb{N}^*, \exists q\in \mathbb{Z}^2 , \forall p\in C_{L,q} ,\; X_{p} =0) =1$.

Calli

gerard0 a dit :

l'espérance d'obtenir une suite horizontale de n+1 carrés identiques est infinie

Ça n'a pas vraiment de sens de dire ça. On peut dire que la proba d'obtenir [...] est égale à 1, ou que l'espérance du nombre de fois qu'on obtient [...] est infinie.

gerard0

Effectivement, j'ai raccourci la deuxième expression.

jacquot

Merci @Guego, @Calli, @gerard0, pour cette illustration de la non-apériodicité au sens de la définition wikipédienne par ce pavage aléatoire et pour son étude.
Il nous permet en tous cas de comprendre que apériodique n'est pas le contraire de périodique: et par conséquent apériodique et non-périodique ne sont pas synonymes. Il serait en effet stupéfiant qu'un pavage aléatoire soit périodique ! En toute rigueur, ce n'est pas impossible (si le diable s'en mêle), mais la probabilité pour que ça se produise est nulle.
Le pavage de Guego fait apparaître à sa gauche une suite de 18 tuiles horizontales dans une même colonne : c'est relativement inattendu dans un champ aussi réduit. On alors veut bien croire que si l'on remplit le plan tout entier, on pourra probablement trouver une suite de longueur supérieure à $n$ quel que soit ce $n$ préalablement choisi, fut-il grand, arbitrairement grand !

Merci @Calli, pour ton explication détaillée. Dans la notion de pavage aléatoire, c'est précisément l'aléa qui me dérangeait, c'est pourquoi, j'avais pensé à la suite des chiffres décimaux ou dyadiques de $\pi$ puisqu'elle est déterminée jusqu'avant l'infini. L'inconvénient, c'est que personne n'en connaît plus que le début et ton pavage aléatoire semble mieux se prêter à la démonstration, même si en conclusion le pavage n'est que presque sûrement non-apériodique

Calli

@jacquot : Même si mon pavage aléatoire n'est non périodique et non apériodique que presque sûrement, la démarche démontre qu'il existe de manière certaine au moins un pavage par des dominos (fixé et non aléatoire) qui est non périodique et non apériodique. Cette technique de preuve s'appelle la méthode probabiliste.

Bon au final le résultat donné (pavage non périodique et non apériodique) n'est pas très impressionnant. Je m'attendais à mieux en lançant l'idée.

Calli

Le Wikipédia anglophone donne une définition plus précise de l'apériodicité. Parce que cette histoire de "pas de section périodique arbitrairement grande" restait floue pour moi, car elle ne dit pas si la périodicité dépend de la section. En effet pour nos pavages en dominos par exemple, on pourrait considérer que toute section carrée du pavage est périodique puisqu'elle est elle-même une grande tuile qui permet de paver périodiquement le plan. Mais ce serait inintéressant comme définition.

Alors Wikipédia dit :

A tiling is called aperiodic if its hull contains only non-periodic tilings. The hull of a tiling $T \subset \R^d$ contains all translates $T+x$ of $T$, together with all tilings that can be approximated by translates of $T$. Formally this is the closure of the set $\{ T+x \, : \, x \in \R^d \}$ in the local topology. In the local topology (resp. the corresponding metric) two tilings are $\varepsilon$-close if they agree in a ball of radius $1/\varepsilon$ around the origin (possibly after shifting one of the tilings by an amount less than $\varepsilon$).

C'est-à-dire que le "hull" (= coque ?) du pavage $T$ est l'ensemble des pavages $T'$ tels que, pour tout $R>0$, il existe $x\in\Bbb R^d$ tel que $T+x$ et $T'$ coïncident dans le disque de rayon $R$ centré en l'origine. Et on dit que $T$ est apériodique si le "hull" de $T$ ne contient que des pavages non périodiques.

Et je précise que cette définition est compatible avec mon avant-avant-dernier message.

jacquot

Bonjour,

Merci @Calli pour tes exdplications concernant la preuve probabiliste : je suis convaincu par ton
" la démarche démontre qu'il existe de manière certaine au moins un pavage etc."

Pour ne pas être en reste, voici l'escargot de la parité des 110 premières décimales de $\pi$ enroulé dans le sens trigonométrique en commençant par un pas à droite


C'est du hand-made, j'ai dû mastiquer un peu par ci, par là.
Je te rejoins un peu @Calli dans l'expression d'une certaine déception, assortie d'une légère perplexité relative à cette notion d'apériodicité.
Dans la quête dite "einstein" d'un pavé unique capable de recouvrir le plan par un pavage nécessairement apériodique, je trouvais que le polygone de Voderberg faisait le job. Il se trouve finalement répudié à cause de ça :


C'est un peu mesquin à mon goût ! Dès lors, le "problème einstein" me paraît futile , mais avec la découverte des quasi-cristaux faisant suite à l'invention des pavages de Penrose, il serait inconvenant de faire la fine bouche.  Peut-être y aurait-il moyen de trafiquer un peu ce polygone de Voderberg pour rattrapper le coup  ?
L'invention du chapeau de David Smith  ne résout pas entièrement de problème einstein, because les retournements, mais les êtres sensibles succomberont presque sûrement à l'apect esthétique du pavage aux chapeaux (ou chemises).

Pour finir, je voudrais partager ma découverte ce ce matin en lisant Wikipédia:
On a trouvé en 2015* un pavage de Penrose, du moins quelque chose qui y ressemble dans un extrait d'une météorite tombée en Sibérie...
Al71Ni24Fe5 TEM - Quasi-cristal — Wikipédia (wikipedia.org)

Amicalement. jacquot
* j'ai l'impression qu'il y a des incohérences de dates dans les articles de WP relatives à cette découverte. 

Calli

Je pense avoir trouvé un pavage apériodique à l'aide de dominos (au sens de la définition que j'ai donnée hier). La construction est la suivante. On part d'une grille régulière de carrés qu'on coupe chacun en deux dominos identiques horizontaux. Et on étiquette les carrés par les éléments de $\Bbb Z^2$. Ensuite, pour tout entier $n\geqslant 2$, on change l'orientation des dominos de tous les carrés dont l'étiquette est de la forme $n! \cdot p$ avec $p\in \Bbb Z^2$ et $p\neq(0,0)$. On fait ça pour tout entier $n\geqslant 2$, ce qui fait une infinité d'étape de modification, mais chaque carré est modifié un nombre fini de fois donc ce processus converge bien vers un pavage limite.

Une autre façon de le dire est que, pour tout carré d'étiquette $p\in\Bbb Z^2$, on oriente verticalement les dominos de ce carré si et seulement si $\mathrm{card}(\{n\geqslant 2\mid p\in n! \cdot\Bbb Z^2\})$ est impair et $p\neq(0,0)$ (et sinon on les oriente horizontalement).

Le pavage est illustré ci-dessous. Les dominos horizontaux sont verts et les verticaux oranges. Le point $(0,0)$ est en bas à gauche de l'image. Les carrés de base sont délimités par des lignes noires. Et les groupes de $2!\times 2!$, $3!\times 3!$ et $4!\times 4!$ carrés sont délimités par des lignes de couleurs resp. bleues, rouges et rose pâle. Les choses intéressantes se passent en bas à gauche de chaque grand carré de couleur.

Montrons que ce pavage $T$ est apériodique.

Supposons par l'absurde qu'il existe un pavage périodique $T'$ dans le "hull" de $T$. C'est-à-dire que $T$ contient des sections arbitrairement grandes de $T'$. Soit $n\geqslant 2$. Alors il existe une zone carrée $C$ de la forme $[\![1,n!]\!]^2+n!\,p$ avec $p\in\Bbb Z^2$ (i.e. un grand carré de largeur $n!$ petits carrés et dont les coins sont dans $n!\cdot\Bbb Z^2$) sur laquelle $T$ et $T'$ sont d'accord. Or sur cette zone $T$ est $(n-1)!$-périodique dans les deux directions. À plus grande échelle $T$ a certes des perturbations tous les $n!$ petits carrés, mais elles ne sont pas visibles dans $C$. Et $T$ ne possède pas de période plus petite dans $C$ à cause des dominos de $(n-1)!\cdot\Bbb Z^2$ tournés lors de la construction. De plus $C$ contient $\frac{n!}{(n-1)!}=n$ super-tuiles carrés de $T$ de largeur $(n-1)!$ petits carrés. Quand $n$ est grand c'est beaucoup, donc je pense que ça implique que $T'$ doit aussi être $n!$-périodique et qu'il ne possède pas de période plus petite. Or $n$ peut être arbitrairement grand, donc la période de $T'$ devrait être infinie. C'est absurde. Donc $T$ est apériodique.

Est-ce que mon idée de raisonnement est claire ? Et es-tu d'accord avec, @jacquot ?

Calli

jacquot a dit : 

Dans la quête dite "einstein" d'un pavé unique capable de recouvrir le plan par un pavage nécessairement apériodique, je trouvais que le polygone de Voderberg faisait le job. Il se trouve finalement répudié à cause de ça : [image de pavage périodique]

Je trouve quand même le pavage Voderberg surprenant, donc intéressant, même si je n'ai pas bien compris comment il peut paver le plan en spirale. De plus l'article partagé par Ludwig explique que cette tuile a la propriété très particulière de pouvoir être totalement entourée par deux copies seulement d'elle-même (alors que pour entourer complètement un carré, il faut 6 carrés par exemple). Mieux : deux tuiles bien placées peuvent aussi être entourées par seulement deux autres tuiles. Voir l'illustration ci-dessous tirée de l'article. Je signale cette propriété pour ceux qui n'aurait pas lu cet article intéressant. 

jacquot

Calli a dit :

intéressant, même si je n'ai pas bien compris comment il peut paver le plan en spirale. 

Il faut bien regarder comment Voderberg négocie les virages : au début, il ouvre un bel éventail d'1/2 tour (et un chouïa de plus), puis, quand il est amené à repasser sur une spire déjà existante, il commence à placer des tuiles  en tête-bêche de manière à créer des alignements sur la spire extérieure pour que celle-ci tourne moins vite. Les spirales de Voderberg présentent donc des sections rectilignes que l'on peut suivre précisément parce que la tuile de Voderberg peut aussi paver le plan par un bête pavage rectangulaire comme (la plupart des ?) quadrilatère(s)
 C'exst par une juste alternance de poses en éventail ou tête-bêche que Voderberg s'arrange pour recouvrir le plan sans laisser d'interstice....

j'espère, @Calli que cette explication t'aura aidé. De mon côté, je me donnerai la peine d'examiner ta proposition de pavage apériodique à tuiles rectangulaires orientées selon les adresses factorielles. Mais de loin, j'y vois de grandes lignes toutes vertes qui de prime abord me semblent rédhibitoires, c'est sans doute parce que je n'ai pas encore bien lu la règle du jeu.

jacquot

Pardonne-moi @Calli, je ne peux pas me prononcer sur ta construction qui me paraît très astucieuse, mais il faut d'abord que je comprenne mieux cette histoire de "hull" ou de coquille.

Heuristique

@jacquot Désolé pour la réponse tardive, je vais mieux expliquer mon propos.

Evidemment, il faut une infinité de tuiles pour recouvrir le plan, je parle ici de l'ensemble de tuiles utilisé.

Tu peux voir le problème de pavages de plusieurs manières, notamment :

1) étant donné un ensemble de tuiles, peut-on paver le plan avec ces tuiles, quitte à leur appliquer des rotations/symétries ?

2) étant donné un ensemble de tuiles, peut-on paver le plan avec ces tuiles, sans autoriser les rotations et symétries des tuiles ?

Dans le pavage einstein, il y a une tuile de base pour le problème 1 et 12 tuiles de base pour le problème 2 (qui sont obtenues à partir des rotations de $\pi/3$ et symétries).

Dans le pavage de Voderberg apériodique, il y a une tuile de base pour le problème 1 et une infinité de tuiles de base pour le problème 2.

On peut donc se demander s'il existe une tuile qui pave le plan de manière apériodique pour le problème 1, en utilisant un ensemble fini de rotations et symétries de cette tuile. Pour ce problème, j'ai l'impression que la tuile einstein est la première réponse que nous ayons trouvé. Mais l'argument du spécialiste que tu as contacté me semble meilleur que le mien (argument d'autorité : il est spécialiste et pas moi).

Calli

Pas de souci @jacquot. Si tu as des questions, n'hésite pas, je peux essayer d'y répondre.
Moi je te remercie pour ton explication qui m'a bien aidé à comprendre le pavage de Voderberg !

jacquot

Aux lecteurs de ce fil, je signale la nouvelle avancée, par les mêmes auteurs dans la recherche d'un pavage apériodique à tuile unique. J'ai ouvert une nouvelle discussion à ce sujet 
Pavage apériodique à tuile unique sans retournement
Amicalement. jacquot

marco

@jacquot , @Calli : j'ai copié la preuve de @Calli (merci à lui !) pour obtenir un ruban apériodique (c'est-à-dire des cases indexées par $\Z$ remplies par $1$ ou $-1$, autrement dit une fonction de $\Z$ dans $\{-1,1\}$, qui est apériodique). J'ai raisonné avec des puissances de $2$ à la place des factorielles.

En effet, soit $x \in \Z$, alors $x=2^{n_x}q_x$ avec $n_x \in \N$ et $q_x \in \Z$ entier relatif impair.

On définit $f(x):=(-1)^{n_x}$.

Montrons que $f$ est apériodique par contraposée.

Supposons donc que $f$ n'est pas apériodique, alors il existe une fonction $g$ de $\Z$ dans $\{-1,1\}$ de période $T>0$, telle que pour tout $N>0$, il existe $x \in \Z$, tel que pour $y \in \{-N,N\}$, $g(y)=f(y+x)$.

Écrivons $T=2^{n_T}q_T$ avec $q_T$ entier relatif impair.

Choisissons $N= \max (T, 2^{n_T+1}+1)$, alors $I=\{-N+x,N+x\}$ contient un entier $z$ de la forme $2^{n_T+1}q_z$ avec $q_z$ impair. En effet, le diamètre de $I$ est supérieur à $2^{n_T+1}$, donc il contient un entier $t$ divisible par $2^{n_T+1}$. Si $t$ n'est pas divisible par $2^{n_T+2}$, alors on choisit $z:=t$, sinon on choisit $z:=t\pm 2^{n_T+1}$.

Soit $y \in \{-N,N\}$ tel que $y+x=z$, alors $f(z\pm T)=f(y+x\pm T)=g(y \pm T)=g(y)$, car $g$ est $T$-périodique, et $g(y)=f(y+x)=f(z)$. Donc $f(z \pm T)=f(z)$.

Mais $f(z)=(-1)^{n_T+1}$, car $z=2^{n_T+1}q_z$.

Et $z\pm T=2^{n_T+1}q_z\pm 2^{n_T}q_T=2^{n_T}(2q_z \pm q_T)$. Or $2q_z\pm q_T$ est impair, car $q_T$ est impair.

Donc $f(z \pm T)=(-1)^{n_T}$.

Donc $f(z\pm T)=-f(z)$. Contradiction.

(J'ai noté $z \pm T$: on choisit $z-T$ si $z \in \{x,N+x\}$ et $z+T$ si $z \in \{-N+x,x\}$)

Peut-être on peut faire pareil pour le plan $\Z^2$ (je n'ai pas réfléchi).

marco

@Calli , @jacquot : concernant le plan, on définit pour tout $(x,y) \in \Z^2$, $h(x,y)=f(x)f(y)$ où $f$ est définie dans le message ci-dessus.

Si $h$ n'est pas apériodique, il existe $g$ de $\Z^2$ dans $\{-1,1 \}$ telle qu'il existe $(a,b) \neq (0,0) \in \Z^2$, tel que pour tout $(x,y) \in \Z^2$, on a $g(x+a,y+b)=g(x,y)$, et telle que pour tout $N>0$, il existe $(u,v) \in \Z^2$ tel que $\forall (x,y) \in \{-N,N\}^2, g(x,y)=h(x+u,y+v)$.

Soit $a=2^{n_a}q_a$, $b=2^{n_b}q_b$, avec $q_a,q_b$ impair.

De même qu'en dimension $1$, si $N$ est suffisamment grand, on trouve dans $(u,v)+ \{-N,N\}^2$ un couple $(x,y)$ tel que $x=2^{n_a+1}q_x$, et $y=2^{n_b+2}q_y$ avec $q_x,q_y$ impair, et tel que $(x+a,y+b)$ appartient aussi à $(u,v)+\{-N,N\}^2$.

Donc $h(x,y)=g(x-u,y-v)=g(x-u+a,y-v+b)=g(x+a-u,y+b-v)=h(x+a,y+b)$.

Mais $h(x,y)=(-1)^{n_a+1+n_b+2}=-(-1)^{n_a+n_b}$.

Et $h(x+a,y+b)=(-1)^{n_a+n_b}$.

En effet, $x+a=2^{n_a}(2q_x+q_a)$, et $y+b=2^{n_b}(4q_y+q_b)$.

Donc $h(x,y)= - h(x+a,y+b)$.

Contradiction.

Ensuite, on pave le carré $(x,y)$ par deux rectangles $2 \times 1$ horizontaux si $h(x,y)=1$ (resp. verticaux si $h(x,y)=-1$).

La preuve de ce message fonctionne si $a\neq 0$ et $b \neq 0$.

Si $b=0$, et $a\neq 0$, on choisit $n_b=0$ et $q_b=0$, et la preuve fonctionne encore. Ou alors on se ramène au cas de la dimension $1$.