Si on veut paver le plan avec des carrés congruents, il est impossible de le faire sans que des carrés partagent une arête commune. En dimension 3, si on pave l’espace avec des cubes congruents, certains doivent partager une face commune. Ott-Heinrich Keller a conjecturé en 1930 que c’est le cas en toute dimension. Une annonce que la conjecture de Keller a été résolue a été faite en 20201 : la conjecture est vraie jusqu’en dimension 7 et fausse en dimension supérieure à 7.
La dimension 2
Essayons de paver le plan avec des carrés congruents sans qu’ils partagent un côté.
Tentons de couvrir l’espace autour du coin supérieur droit du carré rouge.
On n’a pas beaucoup de choix en plaçant un premier carré.
Et maintenant un deuxième carré va nécessairement partager une arête avec le carré rouge. On dira qu’il est jumeau du carré rouge.
Donc la conjecture est vraie en dimension 2. Remarquons que l’hypothèse que les carrés sont congruents est essentielle, car il existe des pavages pythagoriciens avec des carrés de différentes tailles et tels que deux carrés n’ont jamais de côtés communs.
Les dimensions supérieures
Commençons par regarder la dimension 3. Déjà, il y a une différence avec la dimension 2. Tous les carrés d’un pavage du plan ont leurs côtés parallèles à deux axes. Ce n’est plus le cas avec un pavage de l’espace par des cubes.
En effet, on peut effectuer un tel pavage par couches successives :
Mais rien n’empêche d’effectuer une rotation dans le plan horizontal avant d’appliquer la deuxième couche, et une autre avant d’appliquer la troisième. On aurait alors des arêtes de cubes dans plus de trois directions.
Cet exemple est beaucoup plus profond qu’il n’en a l’air. Regardons le processus de construction. Chaque couche est un pavage d’un plan avec des carrés que l’on a ensuite épaissis pour les transformer en cubes. Si on avait pu paver le plan avec des carrés, sans paires de carrés jumeaux, alors la construction avec une rotation entre les différentes couches nous aurait donné un pavage de l’espace avec des cubes ne partageant aucune face entière, donc sans paires de cubes jumeaux.
Autrement dit, si la conjecture de Keller est fausse en dimension d, elle est fausse dans toutes les dimensions supérieures à d.
Jeffrey Lagarias et Peter Schor ont montré en 1992 que la conjecture est fausse en dimension 10. On peut donc en conclure qu’elle est fausse en toute dimension supérieure à 10.
Retour à la dimension 3
Il existe une autre différence avec la dimension 2. En dimension 2, on ne pouvait recouvrir le voisinage d’un coin d’un carré sans introduire un carré jumeau du carré initial. En dimension 3, on peut entourer un cube par 12 cubes ne partageant aucune face avec lui.
Jouer avec un jeu de cubes aide à se convaincre des arguments. Commençons par entourer le coin avant gauche supérieur du cube bleu. Il nous faudra trois cubes. Pour couvrir le côté gauche du coin, on a trois choix :
La figure de droite nous ramène au problème en dimension 2 pour les deux autres faces, dont on sait qu’il est impossible. Les deux autres cas sont symétriques l’un de l’autre. Donc, on se limite au premier.
Ceci force les choix suivants pour les deux autres cubes (pour que les figures soient claires, on ne mettra pas les trois cubes sur la même figure) :
On peut continuer le processus et entourer le cube bleu de 12 cubes jaunes ne partageant aucune face avec lui. Voici les 12 cubes présentés quatre par quatre.
Mais, bien sûr, on a introduit des paires de cubes jumeaux. On n’a pas eu beaucoup de jeu pour couvrir le premier sommet. Le seul jeu possible aurait consisté à glisser un peu les trois cubes jaunes le long du cube bleu.
Même chose pour les trois cubes autour du sommet opposé. Ensuite, on n’aurait plus eu aucun choix pour les six derniers cubes : le seul jeu est donc de faire glisser les paires de cubes jaunes.
Ceci assure que la conjecture de Keller est vraie en dimension 3.
Les dimensions 4, 5 et 6
En 1940, Oskar Perron a montré la conjecture en dimensions 4, 5 et 6. Ce qu’il a montré est que, quelle que soit la manière dont on essaie de paver l’espace, il existera toujours une paire d’hypercubes jumeaux.
Invalider la conjecture en grandes dimensions
Remarquons qu’invalider la conjecture en dimension d revient à montrer l’existence d’un pavage de l’espace sans hypercubes jumeaux.
Pour pouvoir invalider la conjecture dans certaines dimensions, on y va par simplifications successives du problème. Une première simplification est la suivante : si la conjecture est fausse en dimension \(d\), alors il existe un pavage sans hypercubes jumeaux dont les arêtes sont parallèles aux axes de coordonnées, ce qui n’est pas trivial au vu de l’exemple des couches successives en dimension 3.
Pour la deuxième simplification, on fait l’hypothèse que les arêtes des hypercubes ont longueur 2 (ce choix jouera un rôle plus bas). Sándor Szabó a montré en 1988 que si la conjecture est fausse en dimension \(d\), alors il existe un pavage sans hypercubes jumeaux qui est périodique de période 4 dans chacune des d directions des axes. Cette simplification est très loin d’être triviale. Mais c’est une percée très significative: elle ouvre la voie à une solution par ordinateur.
Regardons encore une fois nos exemples en dimension 2 et en dimension 3 :
Dans le premier cas nous aurions pu glisser le carré vert le long du carré rouge, et dans le deuxième cas le cube jaune le long du cube bleu. Donc, le carré vert ou le cube jaune auraient pu occuper une infinité de positions. La troisième simplification pour infirmer la conjecture consiste à remarquer qu’il suffit de considérer des pavages dans lesquels le chevauchement des faces des hypercubes doit être de la forme 1/2 fois la longueur de l’arête. Avec cette troisième simplification, on s’est vraiment ramené à un problème fini.
Le génie de Sándor Szabó, dans un article conjoint avec Kerestztély Corrádi en 1990, a ensuite été de transformer ce problème en un problème de théorie des graphes. Ici encore, nous allons considérer des hypercubes d’arête 2. En effet, pour infirmer la conjecture, il suffit de trouver un pavage sans hypercubes jumeaux qui soit périodique de période 4 dans la direction de chaque axe de coordonnées. On peut alors supposer que les centres des hypercubes du pavage sont des points de coordonnées entières.
\[(x_1,\cdots,x_d)\in \{0,1,2,3\}^d .\]
En effet, à translation près on peut supposer qu’on aura un hypercube centré en (0,…, 0) d’arête 2. Alors, ses faces sont dans les hyperplans \(x_i=\pm 1\). Donc, un deuxième hypercube centré en \((y_1,\ldots, y_d)\) qui partage une portion de face avec cet hypercube doit avoir une face dans un des hyperplans \(x_j = \pm1\), et par suite son centre doit être dans l’hyperplan \(x_j = \pm 2\) : on a \(y_j = \pm 2\).
Pour les autres coordonnées du centre du deuxième hypercube on a deux choix :
- \(y_i =0\) pour tout \(i \neq j\). Alors ce deuxième hypercube est jumeau et partage avec le premier la face dans l’hyperplan \(x_j = \pm 1\).
- \(y_i \in [-2,2]\) pour tout \(i \neq j\) et, pour au moins un \(i, y_i \neq \pm 2\) (pour éviter que les hypercubes ne se touchent par le coin). Comme on se limite à des chevauchements de demi-arêtes, alors on a \(y_i \in \{0,\pm 1,\pm 2\}\).
Alors, pourquoi permet-on des valeurs \(y_i = 3\) ? C’est parce qu’on cherche un pavage périodique de période 4 dans la direction de chacun des axes. Donc, si on a un hypercube centré en (0, …, 0), on aura aussi des hypercubes du pavage centrés en tous les points \((x_1, \ldots, x_d) \in \{0,4\}^d\).
La définition du graphe
Sommets :
Les points de \(\{0,1,2,3\}^d\) seront les sommets du graphe.
Arêtes :
On aura une arête entre deux sommets \((x_1, \ldots, x_d)\) et \((y_1, \ldots, y_d)\) si il existe \(i\) tel que \(x_i – y_i = \pm 2\) et il existe \(j \neq i\) tel que \(x_j \neq y_j\).
Au vu de ce qui précède deux sommets \((x_1, \ldots, x_d)\) et \((y_1, \ldots, y_d)\) sont joints par une arête dans le graphe si
- soit les hypercubes associés ou leurs translatés partagent une portion de face sans être jumeaux,
- ou encore les hypercubes associés ou leurs translatés se touchent par le coin.
Pour que la conjecture de Keller soit fausse en dimension d il faut qu’il y ait suffisamment d’hypercubes qui se touchent sans être jumeaux.
Le graphe ainsi défini est appelé graphe de Keller. Comme on est en dimension d et qu’on a considéré des chevauchements de 1⁄2 arête, on le notera \(G_{d,2}\).
L’affirmation (non triviale) de Corrádi et Szabó est que, si la conjecture de Keller est fausse, alors on peut trouver \(2^d\) sommets du graphe dans \(\{0,1,2,3\}^d\), telle que chaque paire de ces sommets partage une arête. Les \(2^d\) hypercubes formeront le bloc répété périodiquement pour paver l’espace.
Dans le langage de la théorie des graphes,
la conjecture de Keller en dimension d est fausse s’il existe un sous-graphe à \(2^d\) sommets, dont tous les sommets sont deux à deux joints par une arête, c’est-à-dire que le sous-graphe est complet. Un tel sous-graphe est appelé une clique.
Réfléchissons un peu à cette affirmation. Supposons qu’il existe une clique de taille \(2^d\).
Alors les \(2^d\) hypercubes associés et leurs translatés ne se chevauchent pas. Donc, à eux tous, ils occupent un volume de \(4^d\). Et les translatés de ce volume ne se chevauchent pas non plus. Donc, en prenant leurs translatés par des multiples de 4 le long de chaque axe, on va remplir tout l’espace. De plus, comme il y a des arêtes entre tous les sommets, ceci exclut toute paire d’hypercubes jumeaux parmi les \(2^d\) hypercubes et leurs translatés. On a donc construit un contre-exemple à la conjecture de Keller.
Regardons le cas \(d = 2\). Le graphe \(G_{2,2}\) a 16 sommets :
\[ 00, 01, 02, 03, 10, 11, 12, \ldots, 33.\]
Dans ce graphe, chaque sommet est relié à cinq autres sommets.
Mais il n’y a même pas de sous-graphe complet à trois sommets. Donc, la taille maximum d’une clique est 2. Le critère de Corrádi-Szabó n’est pas vérifié. Ceci reflète le fait qu’il n’est pas possible de disposer trois carrés dans le plan de telle manière que chaque paire de carrés partage une demie arête sans être jumeaux. Cela ne suffit pas à confirmer la conjecture car le critère n’est pas un « si et seulement si » mais, ici, on sait que la conjecture est vraie.
C’est ce critère de Corrádi-Szabó qui a été utilisé par Lagarias et Shor en 1990 dans leur preuve que la conjecture est fausse en dimension 10. À l’aide de l’ordinateur, ils ont pu montrer l’existence d’une clique de taille \(2^{10} = 1024\). La même méthode a été utilisée par John Mackey en 2002 : il a exhibé une clique de taille \(2^8 = 256\), ce qui garantit que la conjecture est fausse en dimension 8 et, par suite, en dimension 9.
Il ne restait donc que la dimension 7. On aurait pu penser que la dimension 7 était plus facile que les dimensions 8 et 10, puisque le graphe a beaucoup moins de sommets. Mais, en dimensions 8 et 10, le graphe a beaucoup de symétries qui ont été exploitées dans la recherche d’une clique de taille \(2^d\), lesquelles symétries sont inexistantes en dimension 7, puisque 7 est premier.
La dimension 7
Cette dernière dimension a résisté jusqu’à l’automne 2020. Le critère de Corrádi-Szabó énoncé plus haut ne fonctionne que pour infirmer la conjecture en une dimension \(d\). Or la conjecture de Keller se révélera vérifiée en dimension 7. Il fallait donc une nouvelle idée pour l’attaquer. Celle-ci sera une généralisation de la précédente.
Rappelons que pour infirmer la conjecture il suffit de considérer des pavages dans lesquels le chevauchement des faces des hypercubes doit être de la forme 1/2 fois la longueur de l’arête. Pour confirmer la conjecture en dimension \(d\), il suffira de se limiter à des pavages dans lesquels le chevauchement des côtés des carrés ou des faces des hypercubes doit être de la forme \(p/q\) fois la longueur de l’arête, pour un certain entier \(q\). Dans le cas de la dimension 7, il a été montré en 2017 par Andrzej Kisielewicz que l’on peut prendre pour entier \(q = 3\). Pour traiter ce cas et travailler avec des nombres entiers, nous allons donc considérer des hypercubes d’arête 3 et travailler avec la période 6. On peut alors supposer que les centres des hypercubes du pavage sont des points de coordonnées entières et, comme on cherche des pavages périodiques de période 6 dans la direction de chaque axe, on prendra des centres d’hypercubes aux points
\[( x_1 , \cdots , x_d ) \in \{ 0 , 1, \cdots , 5 \}^7.\]
Comme précédemment les points de \(\{0,1,\ldots,5\}^7\) seront les sommets du graphe de Keller associé qui sera désigné \(G_{7,3}\) pour mettre en évidence la dimension \(d = 7\) et l’entier \(q = 3\). Et on aura une arête entre deux sommets du graphe chaque fois que les hypercubes correspondants ou leurs translatés partagent une portion de face sans être jumeaux ou encore se touchent par le coin.
Un résultat d’Andrzej Kisielewicz et Magdalena Łysakowska affirme que la conjecture de Keller est vraie en dimension 7 s’il n’existe pas de clique de taille \(2^7\) dans le graphe de Keller \(G_{7,3}\). C’est la non-existence d’une telle clique qui vient d’être annoncée, fin 2020, par Joshua Brakensiek, Marijn Heule, John Mackey et David Narváez, et qui terminerait, après 90 ans, la preuve de la conjecture de Keller. Cette démonstration est une preuve assistée par ordinateur. Remarquons qu’elle est beaucoup plus difficile à vérifier que les preuves en dimensions 8 et 10. En effet, prenons la dimension 8. La preuve que la conjecture est fausse revient à montrer l’existence d’une clique de taille \(2^8 = 256\) dans le graphe \(G_{8,2}\). Pour cela, il suffit de donner les 256 sommets de la clique et de vérifier que ces sommets sont deux à deux liés par une arête. Et en dimension 10, la clique a \(2^{10} = 1024\) sommets, donc 523 776 paires de sommets, ce qui n’est pas encore énorme pour un ordinateur. Par contre, en dimension 7, comme la conjecture est vraie, il faut montrer qu’il n’existe aucune clique de taille \(2^7 = 128\) dans le graphe \(G_{7,3}\) qui a \(6^7 = 279\,936\) sommets. Cela fait
\[\begin{pmatrix}279\,936 \\ 128 \end{pmatrix}\]
sous-ensembles de sommets de taille 128 dont il faut vérifier s’ils forment une clique.
Les idées de la méthode utilisée par Brabensiek-Heule-Mackey-Naváez pour simplifier cette vérification apparaissent dans l’encadré.
La conjecture de Keller est vraie en dimension 7
Les idées de la preuve font appel à la logique propositionnelle. Dans cette logique, on considère des variables propositionnelles \(p_i\) qui peuvent prendre les valeurs VRAI (V) et FAUX (F). On construit ensuite des formules plus compliquées appelées formules propositionnelles à l’aide des connecteurs logiques OU (∨), ET (∧), NON (¬), IMPLIQUE (→). On sait que toute formule qui n’est pas toujours vraie quand on assigne des valeurs de vérité aux variables propositionnelles peut être transformée sous la forme d’une conjonction de disjonctions de variables propositionnelles ou leur négation, par exemple :
\[(p_1 \lor p_2 \lor (\lnot p_3))\land ((\lnot p_1) \lor p_2 \lor (\lnot p_3))\land (p_1 \lor(\lnot p_2)\lor p_3).\]
Pour vérifier si on peut satisfaire à la formule, on assigne des valeurs de vérité V ou F à \(p_1, p_2\) et \(p_3\) et on cherche s’il en existe qui donnent la valeur V à toute la formule. Une telle assignation de valeurs de vérité doit donc donner la valeur V à chacun des trois morceaux \(p_1 \lor p_2 \lor (\lnot p_3), (\lnot p_1) \lor p_2 \lor (\lnot p_3)\) et \(p_1 \lor (\lnot p_2 ) \lor p_3\). Par exemple, ici la formule est vraie si \(p_1, p_2\) et \(p_3\) prennent la valeur V. Par contre, la formule
\[ (p_1 \lor p_2) \land ((\lnot p_1)\lor p_2)\land(p_1 \lor (\lnot p_2))\land ((\lnot p_1) \lor (\lnot p_2 ))\]
ne prend que la valeur \(F\), quelles que soient les valeurs de vérité assignées à \(p_1\) et \(p_2\).
L’idée centrale de la preuve est de construire une formule propositionnelle à laquelle des valeurs de vérité peuvent satisfaire s’il existe une clique de dimension 128 dans \(G_{7,3}\) et de montrer que cette formule ne prend jamais la valeur V, pour aucune assignation de valeurs de vérité aux variables propositionnelles. Ceci demande un bon choix de variables propositionnelles qui prennent les valeurs V ou F selon des propriétés d’un sous-ensemble de 128 sommets du graphe. Vérifier si une formule propositionnelle donnée comme conjonction de disjonctions peut prendre la valeur V est un problème très étudié en informatique théorique. Par contre, c’est un calcul qui peut être très long et gourmand en mémoire. Pour pouvoir conclure, Brakensiek, Heule, Mackey et Narváez ont dû commencer par simplifier le problème. Ainsi, il existe une partition des sommets du graphe en 128 sous-ensembles ayant chacun 2187 sommets \((128\times 2187 = 279\,936= 6^7)\). Une clique, si elle existe, a exactement un sommet dans chaque sous-ensemble. Ensuite, on réduit encore le problème en montrant que, si une clique existe, alors il en existe une qui contient certains sommets particuliers, dont le sommet 0000000. Après suffisamment de réductions astucieuses, la non-existence d’une clique de taille 128 a pu être tranchée par ordinateur.
Pour en s\(\alpha\)voir plus !
- HARTNETT, Kevin, Paver l’espace avec des cubes : la conjecture de Keller résolue, Pour la Science, 7 avril 2021.
- L’annonce a été faite lors de la conférence International Joint Conference on Automated Reasoning 2020 (IJCAR 2020) et le résultat publié dans les Comptes rendus de IJCAR 2020. ↩
