Chercher à concilier des contraintes opposées est un puissant moteur de créativité. C’est le cas dans tous les domaines d’activité, que ce soit en art, en littérature, en philosophie, en politique, en technologie, en sciences, etc. Et, plus spécifiquement encore, en mathématiques.

Le Problème des quatre couleurs

Pour ne donner qu’un exemple dans ce dernier domaine, rappelons le fameux

Problème des quatre couleurs. Etant donnée une carte géographique, est-il possible d’assigner à chaque région une couleur parmi quatre disponibles, en respectant la condition d’assigner deux couleurs distinctes à toute paire de régions voisines ?

Voir par exemple cet article sur Images des Maths. Nous sommes bien ici en présence de contraintes tirant dans des sens opposés :

• Utiliser deux couleurs distinctes pour toute paire de régions voisines.

• N’utiliser que quatre couleurs au maximum.

Des solutions seraient évidentes si l’on n’imposait qu’une seule des deux contraintes.

En effet, sans la seconde contrainte, on satisfait facilement la première en utilisant autant de couleurs que de régions. Par exemple, si notre carte comporte 13 régions, il suffit d’utiliser une couleur spécifique pour chaque région, soit 13 couleurs en tout, et le problème est résolu !

De même, sans la première contrainte, on peut largement satisfaire la seconde sans coup férir, en utilisant une seule et même couleur pour toutes les régions.

C’est la conjonction de ces deux contraintes qui fait surgir les difficultés. Est-il possible, donc, de les satisfaire simultanément ? Posé au milieu du 19e siècle, ce problème n’a été résolu qu’en 1974, après un siècle de suspense, avec l’appui de calculs massifs sur ordinateur. Reste le souhait, encore insatisfait de nos jours, d’en donner une solution purement conceptuelle, sans ordinateur. Preuve que l’on n’a pas encore vraiment compris la nature profonde du problème.

Puisqu’il est question de couleurs, profitons-en pour préciser que cet article est conçu pour la piste bleue, même s’il peut tirer ici ou là vers la piste rouge, voire noire à un endroit bien balisé.

Grilles intercalaires

Ce n’était qu’un exemple parmi d’innombrables autres, plutôt bien connu du grand public, de problème mathématique à contraintes opposées. Celui qui nous occupe ici est d’une nature similaire : il s’agit de colorier des cases dans une grille, en utilisant aussi peu de couleurs que possible, tout en respectant certaines contraintes qui tirent le nombre de couleurs nécessaires vers le haut.

Partant d’une grille composée d’un certain nombre de lignes et de colonnes, on souhaite assigner à chacune de ses cases une couleur en respectant les contraintes suivantes :

(1) Pour chaque rangée — ligne ou colonne — toutes les cases sur cette rangée doivent être de couleurs deux-à-deux distinctes.

(2) Pour tout choix de deux lignes et de deux colonnes, les quatre cases qu’elles délimitent doivent utiliser exactement deux ou quatre couleurs.

Une grille intercalaire est une grille dont les cases sont coloriées en respectant simultanément les contraintes (1) et (2).

Le logo représente une grille intercalaire de taille $4 \times 6$, c’est-à-dire à $4$ lignes et $6$ colonnes.

En langage mathématique officiel, on parlerait plutôt de matrice intercalaire : un tableau de nombres, de taille $r \times s$, tel que sur chaque ligne ou colonne, les nombres présents soient deux-à-deux distincts, et tel que pour chaque sous-tableau de taille $2 \times 2$, il y ait exactement soit deux, soit quatre nombres distincts.

La différence entre grille ou matrice intercalaire, on le voit, n’est qu’une question de vocabulaire. Le concept sous-jacent, lui, est identique.

Voici un premier exemple de grille intercalaire, sous forme de matrice justement ; au lieu de sept couleurs, on prend les entiers de $1$ à $7$.

\[ \left( \begin{array}{ccccc} 1 & 2 & 3 & 4 & 5 \\ 2 & 1 & 4 & 3 & 6 \\ 3 & 4 & 1 & 2 & 7 \end{array} \right) \]

Que le lecteur s’amuse à vérifier qu’effectivement, toute sous-matrice à deux lignes et deux colonnes utilise exactement soit deux, soit quatre nombres distincts. Par exemple, la sous-matrice marquée en bleu ci-dessous utilise deux nombres distincts, tandis que celle en rouge en utilise quatre.

\[ \left( \begin{array}{ccccc} \color{blue}{1} & 2 & \color{blue}{3} & 4 & 5 \\ 2 & \color{red}{1} & 4 & 3 & \color{red}{6} \\ \color{blue}{3} & \color{red}{4} & \color{blue}{1} & 2 & \color{red}{7} \end{array} \right) \]

Pour s’assurer que cette matrice est intercalaire, il faut vérifier que cette alternative de deux ou quatre couleurs a bien lieu pour toutes les sous-matrices de taille $2 \times 2$.

Une première construction

Une façon simple de construire une grille intercalaire de taille $r \times s$, c’est d’assigner à chaque case une couleur spécifique, unique pour elle. En effet, la contrainte (1) est alors automatiquement satisfaite ; et la contrainte (2) l’est aussi puisque, dans le cas considéré, chaque sous-grille à deux lignes et deux colonnes utilise quatre couleurs, une pour chaque case, ce qui est explicitement autorisé. Cette simple construction a néanmoins un coût important : elle requiert l’utilisation d’autant de couleurs que de cases présentes, soit de $r \times s$ couleurs.

Par contre, si l’on vise l’économie de couleurs, comme dans le Problème des quatre couleurs, et qu’on cherche donc à construire, pour tout choix de $r$ et $s$, une grille intercalaire de taille $r \times s$ avec le moins de couleurs possibles, ça devient beaucoup plus difficile ; si difficile, même, que ce problème reste ouvert depuis sa formulation par Sergei Yuzvinsky en 1981. Répétons-le formellement.

Problème. Etant donnés deux nombres entiers positifs $r$ et $s$, quel est le plus petit nombre possible de couleurs d’une grille intercalaire à $r$ lignes et $s$ colonnes ?

On ne connaît pas la réponse en général. Mais Yuzvinsky en a formulé une sous forme de conjecture — sujet principal de cet article — présentée plus bas. Examinons d’abord les grilles intercalaires avec une, deux ou trois lignes.

En taille $1 \times s$

Quel est le nombre minimal de couleurs dans une grille intercalaire à $1$ ligne et $s$ colonnes ?

La réponse est $s$, bien sûr. En effet, pour qu’une grille de taille $1 \times s$ soit intercalaire, chaque case doit être coloriée de sa propre couleur exclusive. C’est la contrainte (1) qui l’exige. Il faut donc bien $s$ couleurs, pas moins. Bref, voici à quoi ressemble une grille intercalaire de taille $1 \times s$ :

\[ \left( \begin{array}{cccccc} 1 & 2 & 3 & \cdots & s-1 & s \end{array} \right). \]

En taille $2 \times s$

Quel est le nombre minimal de couleurs dans une grille intercalaire à $2$ lignes et $s$ colonnes ?

La réponse est ici un peu plus compliquée, elle dépend de la parité de $s$.

• Si $s$ est pair, disons $s=2t$, on peut s’en sortir avec $s$ couleurs exactement, comme le montre cet exemple :

\[ \left( \begin{array}{ccccccc} 1 & 2 & 3 & 4 & \cdots & 2t-1 & 2t \\ 2 & 1 & 4 & 3 & \cdots & 2t & 2t-1 \\ \end{array} \right). \]

• Par contre, si $s$ est impair, disons $s=2t+1$, il faut au minimum $s+1$ couleurs :

\[ \left( \begin{array}{cccccccc} 1 & 2 & 3 & 4 & \cdots & 2t-1 & 2t & 2t+1 \\ 2 & 1 & 4 & 3 & \cdots & 2t & 2t-1 & \color{red}{2t+2}\\ \end{array} \right). \]

Ce n’est pas trop difficile — mais pas complètement évident non plus — de prouver qu’il est impossible de s’en tirer avec moins que $s+1=2t+2$ couleurs distinctes. Le bloc déroulant ci-dessous fournit quelques pistes pour les deux cas, pair et impair.

En taille $3 \times s$

Et maintenant, quel est le nombre minimal de couleurs dans une grille intercalaire à $3$ lignes et $s$ colonnes ?

Commençons par une grille intercalaire de taille $3 \times 3$. Quels sont les nombres de couleurs possibles ? La réponse est $4$, $7$ ou $9$ couleurs, rien de plus. En particulier, le minimum possible est $4$. Voici des exemples illustrant chacune de ces trois possibilités :

\[ \left( \begin{array}{ccc} 1 & 2 & 3 \\ 2 & 1 & 4 \\ 3 & 4 & 1 \end{array} \right) ,\quad \; \left( \begin{array}{ccc} 1 & 2 & 3 \\ 2 & 1 & 4 \\ 5 & 6 & 7 \end{array} \right) ,\quad \; \left( \begin{array}{ccc} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{array} \right). \]

Pour une grille intercalaire avec une colonne de plus, soit une grille de taille $3 \times 4$, on peut encore s’en tirer avec $4$ couleurs, comme le montre la construction de $G(4)$ dans la section suivante.

Mais dès la taille $3 \times 5$, il faut au minimum $8$ couleurs. Ce n’est pas complètement évident. Voici quelques remarques générales qui pourraient être utiles pour qui souhaiterait tenter de le démontrer.

Et pour les tailles suivantes, soit $3 \times s$ avec $s \ge 6$, la réponse dépend du reste de la division de $s$ par 8. Pour la connaître exactement dans ce cas, il faut se référer à la fonction de Hopf-Stiefel décrite plus loin, et au fait que la conjecture de Yuzvinsky a été démontrée pour ces tailles-là.

Bref, on le voit, les affaires se compliquent sérieusement assez vite. Les matrices intercalaires recèlent bien des mystères à élucider.

La grille intercalaire carrée $G(n)$ pour $n$ une puissance de 2

Sur une note plus positive, la construction suivante fournit, pour tout $n = 1, 2, 4, 8, 16, \dots$ une grille intercalaire de taille $n \times n$ avec $n$ couleurs seulement. Appelons $G(n)$ la grille obtenue ; on en aura besoin plus loin pour évoquer la conjecture de Yuzvinsky.

Il s’agit d’une construction récursive, c’est-à-dire que la description de l’objet à un niveau donné fait intervenir celle du niveau précédent.

La construction débute avec la grille intercalaire $G(1)$, qui n’a qu’une seule case, munie d’une couleur quelconque :

\[ G(1) \ = \ \left( \begin{array}{c} 1 \end{array} \right). \]

Pour construire $G(2)$ à partir de $G(1)$, on opère comme indiqué ici :

\[ G(2) \ = \ \left( \begin{array}{cc} G(1) & G'(1) \\ G'(1) & G(1) \end{array} \right), \]

où $G'(1)$ est une copie de $G(1)$, mais dans laquelle son unique couleur est remplacée par une toute nouvelle couleur. Plus explicitement, on obtient

\[ G(2) \ = \ \left( \begin{array}{cc} 1 & 2 \\ 2 & 1 \end{array} \right). \]

Plus généralement, pour construire $G(2n)$ à partir de $G(n)$, on opère exactement de la même manière :

\[ G(2n) \ = \ \left( \begin{array}{cc} G(n) & G'(n) \\ G'(n) & G(n) \end{array} \right), \]

où $G'(n)$ est une copie de $G(n)$ dans laquelle les $n$ couleurs de $G(n)$ sont remplacées par $n$ nouvelles couleurs.

On peut vérifier qu’ainsi définie, la grille $G(2n)$ est bien intercalaire, de taille $2n \times 2n$, et comporte exactement $2n$ couleurs distinctes. Voici une indication pour qui souhaite tenter de s’y frotter.

Par exemple, pour $n=4$, on obtient

\[ G(4) \ = \ \left( \begin{array}{cccc} 1 & 2 & 3 & 4\\ 2 & 1 & 4 & 3 \\ 3 & 4 & 1 & 2 \\ 4 & 3 & 2 & 1 \end{array} \right). \]

Puisqu’on part de $n=1$ et qu’on double la taille à chaque étape, les $n$ obtenus ne prennent que les valeurs $1,2,4,8,16,\dots$ soit les puissances de $2$ exclusivement [1].

La conjecture de Yuzvinsky

Le problème de déterminer le plus petit nombre possible de couleurs d’une grille intercalaire de taille $r \times s$ est largement ouvert. Sergei Yuzvinsky a formulé une réponse conjecturale, très plausible, mais dont personne jusqu’ici n’a réussi à démontrer la validité.

De façon plus ou moins surprenante, cette réponse conjecturale fait intervenir une fonction inventée un demi-siècle auparavant par les mathématiciens Hopf et Stiefel à l’Ecole Polytechnique Fédérale de Zurich.

La fonction de Hopf-Stiefel est un peu difficile à décrire complètement si l’on cherche à rester accessible à tout lecteur de 9 à 99 ans. Cela dit, pour les curieux — qu’on souhaite nombreux — révélons-la dans un bloc, à ne dérouler qu’en attachant sa ceinture de sécurité !

Pour qui ne souhaite pas entrer dans sa définition, il suffit de prendre la fonction de Hopf-Stiefel comme une sorte de boîte noire qui associe, à toute paire de nombres entiers positifs $r$ et $s$, un certain nombre entier positif dénoté $r \circ s$ [2].

Certains valeurs de la fonction sont faciles à décrire. Par exemple, si $r$ est une puissance de $2$ et si $s=r+1$, alors $r \circ s = 2r$ dans ce cas. Cela conduit à cette version partielle de la conjecture.

Conjecture de Yuzvinsky (version partielle). Soit $r = 2^d$ une puissance de 2. Alors toute grille intercalaire de taille $r \times (r+1)$ contient au moins $2r$ couleurs distinctes.

Pour $r=2$ par exemple, cette conjecture dit qu’il faut au moins $4$ couleurs pour une grille intercalaire de taille $2 \times 3$. Dans ce cas précis, c’est assez facile à vérifier. De même, pour $r=4$, il faut au moins $8$ couleurs pour une grille intercalaire de taille $4 \times 5$ . C’est déjà beaucoup plus difficile pour $r=8$ ; et pour $r=16$, la conjecture dans ce cas reste ouverte à ma connaissance. Est-il vrai, donc, que tout grille intercalaire de taille $16 \times 17$ nécessite au moins $32$ couleurs ?

Quant à une version complète de la conjecture de Yuzvinsky, donnons-en d’abord une version équivalente qui n’invoque pas la fonction de Hopf-Stiefel ; à la place, elle fait appel aux grilles intercalaires $G(n)$ construites ci-dessus.

Conjecture de Yuzvinsky (version équivalente complète). Le nombre minimal de couleurs d’une grille intercalaire de taille $r \times s$ est égal au nombre minimal de couleurs des sous-grilles de taille $r \times s$ de la grille $G(n)$, pour $n$ une puissance de 2 supérieure ou égale à $r$ et $s$.

En clair, la conjecture dit qu’il est impossible de trouver une grille intercalaire de taille $r \times s$ utilisant moins de couleurs que les sous-grilles de même taille que l’on trouve dans $G(n)$.

Donnons enfin la version originale de la conjecture. Bien qu’elle fasse appel à la fonction de Hopf-Stiefel $r \circ s$, elle est en fait plus facile à lire ! Répétons qu’on peut soit consulter la définition de $r \circ s$ dans le bloc déroulant plus haut, soit simplement considérer cette fonction comme une boîte noire.

Conjecture de Yuzvinsky (version originale). Le nombre minimal de couleurs d’une grille intercalaire de taille $r \times s$ est égal à $r \circ s$.

L’équivalence entre ces deux versions repose sur un théorème assez ardu selon lequel, dans $G(n)$, le nombre minimal de couleurs des sous-grilles de taille $r \times s$ est effectivement égal à $r \circ s$.

Origine du problème

Voici quelques éléments évoquant le contexte dans lequel s’est inscrit le travail de Yuzvinsky en 1981 sur les matrices intercalaires. Il est lié à la recherche de formules algébriques du type suivant :

\[ (x_1^2+x_2^2)\times (y_1^2+y_2^2) \ = \ (x_1y_1 - x_2y_2)^2+(x_1y_2 + x_2y_1)^2. \]

Regardez bien cette formule. Elle accomplit une belle prouesse, exprimant le produit de deux sommes de deux carrés, à gauche, comme la somme de seulement deux carrés d’autres expressions algébriques, à droite [3].

Plus généralement, on cherche à construire des formules analogues, permettant d’exprimer le produit d’une somme de $r$ carrés et d’une somme de $s$ carrés, à savoir

\[ (x_1^2+x_2^2+\dots+x_r^2) \times (y_1^2+y_2^2+\dots+y_s^2), \]

comme une somme d’aussi peu de carrés que possible. On peut très facilement s’en sortir avec $r \times s$ carrés :

\[ (x_1^2+x_2^2+\dots+x_r^2) \times (y_1^2+y_2^2+\dots+y_s^2) \ = \ (x_1y_1)^2+(x_1y_2)^2+\dots+(x_ry_s)^2. \]

Mais on aimerait trouver des formules plus subtiles et plus performantes, nécessitant moins que $r \times s$ carrés. Cela est très souvent possible, comme le cas $r=s=2$ ci-dessus le montre, où l’on n’a besoin, dans le terme de droite, que de deux carrés au lieu de quatre.

Se pose alors la question de savoir, pour tout $r$ et $s$, quel est le plus petit nombre de carrés requis pour une telle formule. Ce problème remonte au 19e siècle, est lié au nom de Hurwitz, et reste largement ouvert de nos jours encore.

Il y a des façons très diverses de l’aborder, par exemple via l’algèbre ou la topologie algébrique. Le mérite de Yuzvinsky est d’avoir trouvé une approche de nature combinatoire. Et c’est ainsi, en 1981, que les matrices intercalaires et cette conjecture à leur sujet sont nées.

Etat de l’art

Que sait-on de nos jours sur la conjecture de Yuzvinsky ? Ce n’est pas très clair, dans la mesure où plusieurs résultats partiels obtenus n’ont jamais été publiés. En particulier, la conjecture a été démontrée dans le cas $r \le 5$, mais la preuve n’a fait l’objet d’aucune publication officielle ; je le sais pour y avoir contribué il y a longtemps, avec des collègues mexicains. Ces collègues se sont d’ailleurs récemment remis à la recherche du trésor — une solution complète de la conjecture — et il se pourrait qu’ils n’en soient plus très loin maintenant. Souhaitons-leur bonne chance !