Échos de la recherche Retour à la rubrique

Un carrelage original

Piste verte Le 13 juin 2016 - Ecrit par Pierre-Antoine Guihéneuf Voir les commentaires

« ’Til morning comes, let’s tessellate »

$\Delta$

Émilien fait des travaux chez lui. Il refait sa salle de bains et sa cuisine. Ça lui fait pas mal de carrelage à faire. Et il en a un petit peu marre de toujours carreler de la même manière. Le dessin suivant, il le trouve monotone.

Pour changer, il aimerait bien trouver d’autres manières de carreler, en piochant dans son stock de carreaux, qui sont carrés et tous de même taille. Assez rapidement, il se rend compte qu’il peut modifier la manière de carreler habituelle, en déplaçant chaque ligne de carreaux vers la gauche ou la droite d’autant qu’il le souhaite, comme sur le dessin suivant. Et bien sûr, il peut faire la même chose en remplaçant les lignes de carreaux par les colonnes.

Mais il a beau faire plein d’autres essais, il n’arrive pas à trouver d’autres configurations de carrelage. Et il se convainc assez rapidement qu’il n’y a pas le choix : un carreau quelconque a forcément au moins un côté entièrement en commun avec un autre carreau.

Il trouve même une démonstration de cette propriété. Il commence par écrire de manière rigoureuse ce qu’est un carrelage ; ou ce que les mathématiciens appellent pavage :

Un pavage du plan par des carrés est une collection de carrés, tous de la même taille, qui recouvrent tout le plan sans jamais se chevaucher.

Émilien démontre la propriété suivante sur les pavages :

Proposition : Dans un pavage du plan par des carrés, chaque carré a au moins un côté entièrement en commun avec un autre carré.

Preuve trouvée par Émilien

Choisissons un carré du pavage, qu’on colorie en rouge. Il y a au moins un autre carré qui touche le côté droit de notre carré rouge ; ce carré on le colorie en bleu. On a alors deux cas :

Soit le carré bleu a tout un côté entièrement en commun avec le carré rouge. Dans ce cas, on vient de démontrer notre propriété.
Sinon, le côté gauche du carré bleu rencontre au moins un sommet du carré rouge ; ce sommet on l’appelle $S$. Puisqu’on a un pavage du plan, ce point $S$ appartient à la fois aux carrés rouge et bleu, mais aussi à un autre carré, qu’on colorie en vert. Et forcément, le carré vert a un côté entièrement en commun avec le rouge, ce qui démontre notre propriété.

En continuant le raisonnement de sa démonstration, Émilien se rend compte que s’il veut paver le plan avec ses carreaux carrés, il est obligé d’avoir des bandes verticales, ou des bandes horizontales, de carreaux. Il est un peu déçu.

Mais si ça se trouve, il ne se passe pas la même chose dans l’espace : si on remplit, on pave l’espace avec des cubes, est-ce que forcément n’importe lequel de ces cubes possède une face en commun avec un autre cube ? Il pose la question à Lucie, sa femme, qui s’y connaît pas mal en matière de pavages du plan, de l’espace, et de mathématiques en général. Lucie sait que la réponse est oui : c’est un théorème dû à Hermann Minkowski (voir [StSz]) [1]. Et celui-ci reste vrai jusqu’au moins la dimension 6.

L’espace de dimension $n$ : mode d’emploi

Tout point du plan est repéré par ses 2 coordonnées : son abscisse et son ordonnée, donc par 2 nombres. De la même manière, tout point de l’espace est repéré par ses 3 coordonnées : son abscisse, son ordonnée et sa cote (autrement dit, sa hauteur), donc par 3 nombres. Plus généralement, on peut considérer l’ensemble des points à $n$ coordonnées ; cet ensemble est appelé l’espace de dimension $n$. Par exemple, $(1\ ,\ -2\ ,\ 3\ ,\ 42)$ est un point de l’espace de dimension 4. Cet espace de dimension $n$ possède les mêmes propriétés agréables que le plan ou l’espace de dimension 3.

En particulier, on peut y définir une notion de cube : étant donné un point $x$ de l’espace de dimension $n$, le cube dont les arêtes sont de longueur 1 et centré en $x$ est l’ensemble des points dont chaque coordonnée est à distance au plus 1/2 de la coordonnée correspondante de $x$. Par exemple, l’ensemble des points dont toutes les coordonnées sont entre 0 et 1 est un cube de centre $(1/2\ ,\ \cdots\ ,\ 1/2)$.

Le théorème est le suivant, et a été démontré par Oskar Perron en 1940 [Per] :

Théorème : Pour toute dimension $n\le 6$, dans un pavage de l’espace de dimension $n$ par des cubes, chaque cube a au moins une face entièrement en commun avec un autre cube.

Voilà ce que ça donne, par exemple, dans l’espace de dimension 3.


Un pavage possible en dimension 3

En 1930, Ott-Heinrich Keller avait même conjecturé [2] [3] que cette propriété est vraie pour n’importe quelle dimension $n$. Cette conjecture est restée sans réponse jusqu’en 1992, lorsque Jeffrey Lagarias et Peter Shor ont trouvé un contre-exemple pour toute dimension plus grande que 10 [LaSh]. Ce résultat a été amélioré par John MacKey en 2002, qui a trouvé un contre-exemple pour toute dimension plus grande que 8 [McK] :

Théorème : Pour tout $n\ge 8$, il existe un pavage de l’espace de dimension $n$ par des cubes tel que chaque cube n’a aucune face entièrement en commun avec un autre cube.

Pour une preuve assez courte [4] de ce résultat lorsque $n\ge 12$, voir cet article de Terence Tao.

Ce résultat n’est pas tant contre-intuitif quand on sait qu’en dimension 3, il existe des pavages dont certains cubes n’appartiennent à aucune bande, comme par exemple le cube bleu foncé dans le pavage suivant [5] (inspiré d’un dessin de cette page, en chinois)


Un autre pavage en dimension 3, un peu plus complexe

On peut donc espérer qu’en augmentant assez la dimension, on a assez de marge de manœuvre pour éviter les faces communes pour certains cubes.

Émilien est heureux : quitte à se placer en dimension assez grande, il peut carreler l’espace de manière originale !

Notons que pour la dimension 7, on ne sait toujours pas si la conjecture de Keller est vraie ou non : avis aux amateurs !

Pour aller plus loin : la conjecture d’Hermann Minkowski, et sa preuve par György Hajòs

La conjecture de Keller reste cependant vraie pour toute dimension $n$ sous la condition que les centres des cubes sont les points d’un réseau.

Un réseau de l’espace de dimension $n$ est un sous-ensemble $L$ de l’espace de dimension $n$, qui est :

stable par addition [6] (si $l_1$ et $l_2$ sont deux éléments de $L$, alors $l_1+l_2$ est lui aussi un élément de $L$) ;
discret (si $l$ est un élément de $L$, alors il existe un petit cube centré en $l$ qui ne contient qu’un seul point de $L$) ;
relativement dense (il existe un rayon $R$ tel que tout cube dont les arêtes sont de longueur $R$ contient au moins un élément de $L$).

Ceci est un réseau	Ceci n’est pas un réseau : cet ensemble n’est pas relativement dense
Ceci n’est pas un réseau : cet ensemble n’est pas discret	Ceci n’est pas un réseau : cet ensemble n’est pas stable par addition

Hermann Minkowski avait conjecturé en 1896 que si les centres des cubes sont les points d’un réseau de l’espace de dimension $n$, et si ces cubes forment un pavage de cet espace, alors forcément chaque cube possède une face en commun avec un autre cube. Cette conjecture a quand même résisté pendant plus de 30 ans aux mathématiciens, jusqu’à ce que György Hajòs parvienne à la démontrer en 1941, en transformant ce problème de pavage de l’espace en un problème d’algèbre abstrait concernant les groupes abéliens finis (voir la publication originale en allemand [Haj], ainsi que le livre [StSz]).

Ce théorème de Hajòs a servi récemment à l’auteur, pour caractériser les applications linéaires du plan pour lesquelles on n’a pas de perte d’information lorsqu’on les applique à des images numériques... mais cela fera sans doute l’objet d’un autre article sur Images des Maths !

[Per]
Oskar Perron. Über lückenlose Ausfüllung des $n$-dimensionalen Raumes durch kongruente Würfel. Paru dans Mathematische Zeitschrift no. 46 (1940), p. 1-26.

[LaSh]
Jeffrey C. Lagarias et Peter W. Shor. Keller’s cube-tiling conjecture is false in high dimensions. Paru dans Bulletin of American Mathematical Society no. 27 (1992), p. 279-283.

[McK]
John MacKey. A cube tiling of dimension eight with no facesharing. Paru dans Discrete Computational Geometry no. 28 (2002), p. 275-279.

[Haj]
György Hajòs. Über einfache und mehrfache Bedeckung des n-dimensionalen
Raumes mit einem Würfelgitter. Paru dans Mathematische Zeitschrift no. 47 (1941), p. 427-467.

[StSz]
Sherman Stein et Sandor Szabó. Algebra and tiling, Homomorphisms in the service of geometry. Carus Mathematical Monographs, 1994.

Post-scriptum :

Je remercie Frédéric Le Roux pour m’avoir encouragé à écrire cet article, les éditeurs Mélanie Guénais et Jérôme Buzzi, ainsi que les relecteurs attentifs projetmbc, moahaha, Laurent Dietrich et Clément M., sans oublier les très efficaces secrétaires de rédaction.

Article édité par Frédéric Le Roux

Notes

[1] Hermann Minkowski avait été amené à étudier ce problème par des questions d’approximation diophantienne : étant donné un nombre $\alpha$, peut-on trouver des fractions $p/q$ qui sont proches de $\alpha$, dans le sens que $|\alpha-p/q|\le 1/q^2$ ? On peut répondre à cette question en utilisant le théorème de Minkowski, qui est maintenant à la base de tout un pan des mathématiques appelé théorie géométrique des nombres. Le cas d’égalité de ce théorème est caractérisé par le théorème de Hajòs présenté à la fin de cet article.

[2] Une conjecture est une propriété dont on ne connaît pas de démonstration, mais que l’on soupçonne d’être vraie.

[3] Pour plus de détails, voir cet article de Wikipedia (en anglais).

[4] De niveau licence, mais pas forcément facile à lire !

[5] Le lecteur pourra faire tourner le dessin pour y voir plus clair en ouvrant le fichier GeoGebra. La construction de ce pavage est assez simple : on part du pavage le plus simple où tous les cubes ont tous toutes leurs faces entièrement en commun avec un autre, et on « pousse » trois rangées de cubes (en rouge, jaune et vert sur le dessin) qui jouxtent un même cube (en bleu foncé sur le dessin).

[6] Dans l’espace de dimension $n$, l’addition se fait coordonnée par coordonnée. Par exemple en dimension 2, $(1\ ,\ 3) + (2\ , -1) = (1+2\ ,\ 3-1) = (3\ ,\ 2)$.

Commentaire sur l'article

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexion | s’inscrire | mot de passe oublié ?