Pavages : quasi-périodicité

On fixe un ensemble T fini de tuiles. Une configuration est une application c : ℤ^{2} ↦ T . Un motif carré de côté n est une application m : [[1, n]] × [[1, n]] ↦ T . On note ℓ(m) = n. Le motif m apparaît dans la configuration c s’il existe (i, j) ∈ ℤ^{2} tel que m soit la restriction de c à [[i, i + n − 1]] × [[j, j + n − 1]] ; on dit aussi que m est extrait de c. On définit de façon analogue la notion de motif extrait d’un autre motif (plus grand).

On note M_{n}(c) l’ensemble des motifs carrés de côté n extraits de c, et M(c) = ⋃_{n⩾1} M_{n}(c).

Soit d une autre configuration ; on note c ≺ d si M(c) ⊂ M(d). La relation ≺ est un préordre sur l’ensemble des configurations. Nous dirons que c est quasi-périodique si, quel que soit le motif m ∈ M(c), il existe n_{m} ⩾ ℓ(m) tel que m apparaît dans tout motif carré de côté n_{m} extrait de c. Exemple : si c est doublement périodique, de périodes p et q, alors c est quasi-périodique avec n_{m} = ℓ(m) + 2 max(p, q) − 2. Exemple : la configuration c définie par c(i, j) : δ_{i,0}δ_{j,0} n’est pas quasi-périodique. Soient m un motif et c une configuration ; considérons l’ensemble des n ⩾ 1 tels que m apparaît dans tout motif carré de côté n extrait de c. Le rang de m vis-à-vis de cette configuration, noté ρ_{c}(m), est le plus petit élément de cet ensemble s’il n’est pas vide, +∞ sinon. Notons que ρ_{c}(m) ⩾ ℓ(m). Un motif m apparaissant dans une configuration c est régulier pour cette configuration si ρ_{c}(m) < +∞; sinon, il est dit critique. Remarque : c est quasi-périodique ssi tous les motifs extraits de c sont réguliers pour c. Lemme 1 : si m est critique pour c, il existe d ≺ c tel que m ∉ M(c). Preuve : notons n = ℓ(m). Il existe un motif m_{0} ∈ M_{n}(c) distinct de m, et ayant une infinité d’occurrences dans c. Il existe alors un motif m_{1} ∈ M_{n+2}(c) ayant une infinité d’occurrences dans c, au centre duquel apparaît m_{0}, et dans lequel n’apparaît pas m. On peut poursuivre indéfiniment cette construction : supposons obtenu un motif m_{k} ∈ M_{n+2k}, ayant une infinité d’occurrences dans c; il existe un motif m_{k+1} ∈ M_{n+2(k+1)}, ayant une infinité d’occurrences dans c, au centre duquel apparaît m_{k}, et dans lequel n’apparaît pas m. Superposons ces motifs, leur centre commun étant en (0, 0) : on obtient une configuration d extraite de c, et ne contenant pas le motif m. Théorème : c est quasi-périodique ssi c est minimal vis-à-vis de ≺. Preuve du sens direct : soit d ≺ c. Tout motif m ∈ M(c) apparaît dans tout carré de côté ρ_{c}(m) extrait de c, et à plus forte raison dans tout carré de côté ρ_{c}(m) extrait de d, donc m ∈ M(d), si bien que c ≺ d. Preuve de la réciproque : supposons c non quasi-périodique. Soit m un motif critique de c; d’après le lemme 1, il existe une configuration d extraite de c mais dans laquelle m n’apparaît pas. d minore strictement c pour la relation ≺, si bien que c n’est pas minimal pour cette relation. Lemme 2 : si m est critique pour c, et si c ≺ d, alors m est critique pour d. Preuve : pour tout n, m est absent d’au moins un motif de côté n extrait de c, donc de d. Théorème : si le jeu de tuiles T permet de paver le plan, alors il permet de le paver de façon quasi-périodique. Preuve : soit c un pavage réalisé avec T . Si c ne possède qu’un nombre fini de motifs critiques, on peut les éliminer l’un après l’autre avec le lemme 1, pour obtenir un pavage quasi-périodique. Sinon, comme l’ensemble des motifs est dénombrable, on peut, toujours avec le lemme 1, construire une suite (c_{k})_{k∈ℕ} de pavages tels que c_{k+1} ≺ c_{k} ≺ c. Soit m_{k} ∈ M_{k}(c_{k}) : le procédé d’extraction diagonale utilisé pour la preuve du lemme 1 peut être utilisé à nouveau ici, pour obtenir un pavage γ extrait de c, et ne contenant aucun motif critique. Remarque : cette preuve n’est pas constructive.

Définition : la fonction de quasi-périodicité d’une configuration c quasi-périodique est l’application f_{c} qui, à n ∈ ℕ, associe f_{c}(n) = min{ρ_{c}(m) | m ∈ M_{n}(c)}. f_{c}(n) est donc le plus petit naturel N tel que, dans tout motif carré de côté N, tous les motifs de côté n apparaissent au moins une fois. Théorème : f est strictement croissante. Preuve : que f soit croissante est claire. Pour la croissance stricte, observer la figure ci-dessous.

m m′  μ μ′ \overbrace{f_{c}(n)} \overbrace{n}

m est un motif carré de côté ℓ(m) = f_{c}(n) − 1, et dans lequel n’apparaissent pas tous les motifs carrés de côté n. m′ est le motif carré de côté ℓ(m′) = ℓ(m) + 1 = f_{c}(n) obtenu en ^{⟨⟨} bordant^{⟩⟩} m par une rangée au-dessus et une colonne à droite. μ est un motif carré de côté ℓ(μ) = n qui n’apparaît pas dans m; comme il apparaît nécessairement dans m′, il est calé contre le bord haut ou le bord droit de celui-ci. Soit alors μ′ le motif carré de côté ℓ(μ′) = ℓ(mu) + 1 obtenu en bordant μ comme il a été fait pour m. μ′ n’apparaît pas dans m′ (sinon, μ apparaîtrait dans m) donc f_{c}(n + 1) > f_{c}(n). Définition : la fonction de complexité de la configuration c est l’application g_{c} qui, à n ∈ ℕ, associe le cardinal de M_{n}(c). Il est clair que g_{c} est croissante. Théorème : soit c une configuration quasi-périodique. Les assertions suivantes sont équivalentes :

• c est périodique

• la suite de terme général f_{c}(n) − n stationne

• g_{c} stationne

• il existe un indice n_{0} tel que g_{c}(n_{0} + 1) = g_{c}(n_{0})

Preuve : 1 ⇒ 2 et 3 ⇔ 4 sont clairs ; 2 ⇒ 3 se déduit de la majoration g_{c}(n) ⩽ (f_{c}(n) − n + 1)^{2} ; pour 3 ⇒ 1, il suffit de noter que, n_{0} désignant l’indice à partir duquel g_{c} stationne, toute bande (horizontale ou verticale) de largeur n_{0} est périodique. Théorème : c est quasi-périodique ssi f_{c}(n) − n est borné.

[qpavages] Composé le 24 mai 1998