Forcer la complexité

02.09.2013 par Jean-Paul Delahaye, dans pavages

Les pavages non périodiques du plan suscitent une étonnante curiosité. Pourtant certains sont très simples. Celui-ci par exemple :

Pas de quoi s'extasier ! Un seul pavé rectangulaire est utilisé, un rectangle 1x2. Puisqu'aucune translation ne laisse invariant le pavage, il s'agit d'un pavage non périodique.

Ce qui est étonnant et a exigé un authentique travail mathématique, c'est la découverte d'ensembles de pavés apériodiques, c'est-à-dire forçant la non périodicité : avec un tel ensemble de formes, on peut paver le plan, mais aucun des pavages possibles du plan n'est périodique. L'ensemble «force» la non périodicité.

On connaît des dizaines d'ensembles de pavés apériodiques très différents les uns des autres —et une infinité en s'amusant à changer ce qui peut l'être. Le plus élémentaire est celui-ci qui est composé de deux formes particulièrement simples, et qui donne —parmi beaucoup d'autres le pavage non périodique dessiné en dessous :

 

Un jeu fini de contraintes géométriques élémentaires —faire se joindre des copies de deux formes sans laisser d'espace et en s'interdisant de couper les courbes dessinées sur les formes— produit une contrainte à l'infini : la «non périodicité» (qui est une forme faible de complexité).

Aller plus loin : quel type de complexité peut-on forcer ?

Un pavage est «quasi-périodique» si pour tout motif M qui y apparaît (un motif est un assemblage fini de formes), il existe un entier n tel que M apparaît dans tout motif couvrant un disque de rayon n. Les pavages quasi-périodiques sont donc ceux qui font apparaître tout motif de manière régulière, chaque motif présent revenant partout assez fréquemment (et donc une infinité de fois). Le dessin constitué par un pavage quasi-périodique est un peu moins simple que celui d'un pavage périodique, mais le désordre qui s'y trouve reste contrôlé et modéré car tout s'y répète infiniment dans toutes les directions. On montre le beau résultat que tous les pavages faisables avec les deux pavés de Penrose sont quasi-périodiques (et c'est d'ailleurs pour cela que ces pavages sont importants pour comprendre les quasi-cristaux). Ce résultat signifie que les pavages obtenus avec les deux formes de Penrose sont tous d'une complexité minimum (ils ne sont pas périodiques) mais pas trop grande (puisqu'ils sont quasi-périodiques). L'ensemble apériodique de Penrose force une complexité modérée sans pouvoir la dépasser.

Notons qu'il est cependant facile de concevoir des pavages qui ne sont pas quasi-périodiques : le pavage donné au tout début n'est pas quasi-périodique car on peut trouver des disques aussi grands qu'on le veut ne contenant pas le motif central. Une question naturelle se pose alors :

- Puisqu'on peut forcer la «non périodicité», peut-on forcer la «non quasi-périodicité» ?

Autrement dit : peut-on trouver un ensemble de formes qui pavent le plan mais seulement en dessinant des pavages qui ne sont pas quasi-périodiques (contenant donc une sorte de grand désordre) ?

La réponse est négative :

- si un ensemble de pavés recouvre le plan, alors, il peut en particulier le faire de manière quasi-périodique.

Ce beau théorème est dû à Bruno Durand un chercheur Français qui l'a établi en 1999. Il signifie que le type de désordre exprimé par la propriété de «non quasi-périodicité» ne se force pas à l'aide de règles locales. Ce résultat mathématique formule une importante loi du monde de la complexité :

- des règles locales peuvent forcer la «non périodicité», mais pas la «non quasi-périodicité».

La «non-quasi-périodicité» est une forme de désordre, mais la «non calculabilité»  aussi, et cette fois on peut la forcer. William Hanf et Dale Myers ont en effet démontré, qu'il existe des ensembles finis de formes qui pavent le plan mais ne le font que de manière «non calculable». Disposer les pavés d'un tel ensemble sur tout le plan est possible jusqu'à l'infini, mais aucun algorithme n'indique comment le faire ; avec un tel ensemble de formes, pour paver le plan, il faut procéder au hasard et avoir de la chance ! Dit autrement encore : il y a des pavages mais aucun ne résulte de manière déterministe d'un ensemble de règles qui en fixeraient la construction.

La complexité exprimée par la propriété de «non quasi-périodicité», n'est pas de même nature que la complexité exprimée par la propriété de «non calculabilité» : l'une se force localement, l'autre non !

Dans cette veine, un autre beau résultat a été démontré en 2008 par Bruno Durand, Leonid Levin et Alexander Shen. Il pousse à son extrême cette étude du forçage de la complexité par un ensemble fini de pavés. Son énoncé indique qu'il existe des ensembles de pavés qui forcent une croissance rapide de la complexité de Kolmogorov des dessins produits par tout pavage. Tout pavage possible est tel que pour en décrire un motif couvrant un disque de rayon n, il faut un programme de longueur au moins proportionnelle à n (la complexité de Kolmogorov du dessin est supérieure à C.n pour un certain C). Un tel ensemble de pavés force donc une grande complexité des dessins.

Ces résultats impossibles à deviner sans un travail mathématique délicat nous disent comment le local détermine le global de la complexité. Ils viennent compléter les propositions souvent inattendues que les sciences de la complexité nous livrent et qui enrichissent notre compréhension profonde du monde abstrait et déterminent alors le monde concret, en l'occurrence, ici, celui des quasi-cristaux.

Voir Pavage de Penrose


Un commentaire pour “Forcer la complexité”

  1. benoit Répondre | Permalink

    Eh bien, voilà des explications bien éclairantes !

Publier un commentaire