Un étrange échiquier

L’échiquier 8 x 8 du logo ne permet certes pas de jouer aux échecs, mais il jouit d’une propriété très spéciale : prenez deux lignes quelconques, et comptez les colonnes dont les deux cases sont de même couleur, c’est-à-dire toutes deux blanches ou toutes deux orange. Alors vous trouverez exactement 4 concordances de couleur, et donc automatiquement 4 discordances de couleur [1]. Vérifions-le pour les lignes numéro 1 et 2, par exemple :

Lignes 1 et 2 du logo

Les concordances de couleur ont lieu aux colonnes numéros 1, 3, 5 et 7, et les discordances aux quatre colonnes restantes. Prenons deux autres lignes au hasard, disons la 3ème et la 5ème :

Lignes 3 et 5 du logo

Les concordances de couleur ont lieu ici aux colonnes numéros 1, 2, 7 et 8. Testez toutes les autres paires de lignes : vous trouverez toujours exactement quatre colonnes avec concordance, respectivement discordance, de couleurs.

Le problème

Grisés par cet étrange échiquier de taille 8 x 8, on aimerait naturellement savoir s’il en existe de similaires dans d’autres tailles. On appellera provisoirement échiquier égalitaire tout échiquier de taille $n$ x $n$ ayant la propriété que pour chaque paire de lignes distinctes, il y a exactement autant de colonnes dont les cases correspondantes sont de couleur identique que de colonnes dont les cases correspondantes sont de couleurs distinctes. Le problème suivant reste largement non-résolu à ce jour.

Problème. Pour quels entiers naturels $n$ existe-t-il un échiquier égalitaire de taille $n$ x $n$ ?

Matrices de Hadamard

Ce problème a été formulé par le célèbre mathématicien français Jacques Hadamard [2] en 1893, à l’âge de 28 ans, un an après sa thèse et trois ans avant sa fameuse preuve du Théorème des nombres premiers [3].

Jacques Salomon HADAMARD (1865-1963)

C’est la raison pour laquelle le terme officiel pour désigner un échiquier égalitaire de taille $n$ x $n$ est matrice de Hadamard d’ordre $n$. Nous adopterons ce terme à partir d’ici.

Précisons qu’en langage mathématique, une matrice n’est rien d’autre qu’un tableau de nombres. Quel rapport avec les échiquiers ? Eh bien, il est facile de considérer un échiquier comme une matrice ne contenant que des $1$ et des $-1$. Il suffit pour cela de coder les cases blanches par $1$ et les cases orange par $-1$.

Par exemple, les deux premières lignes du logo correspondent à la matrice
\[ \left[ \begin{array}{rrrrrrrr} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 & 1 & -1 & 1 & -1 \end{array} \right]. \]

La motivation originelle de Hadamard est extrêmement intéressante, mais il faut changer de couleur de piste pour bien la décrire ! C’est ce que nous ferons dans une suite à cet article, où l’on expliquera que Hadamard cherchait à trouver le « déterminant maximum des matrices carrées d’ordre $n$ à coefficients dans l’intervalle $[-1,1]$ ». Mais cela ne nous sera nullement utile ici.

Revenons donc à notre problème, dans sa terminologie officielle : quels sont les ordres possibles des matrices de Hadamard ?

Hadamard a obtenu la condition nécessaire suivante : s’il existe une matrice de Hadamard d’ordre $n$, alors forcément $n=1$, $n=2$ ou $n$ est un multiple de 4.

Cette condition nécessaire est-elle aussi suffisante ? La réponse est très probablement oui, mais malgré plus d’un siècle d’efforts, personne ne sait encore le démontrer. C’est cela, la fameuse conjecture de Hadamard.

La formulation précise de Hadamard n’est peut-être pas aussi explicite, mais elle en est très proche ! En effet, voici ce qu’il écrit dans [4], après avoir construit dans [5] des matrices de Hadamard d’ordre 12 et 20 :

J’ai formé des déterminants réels pour $n$ = 12 et $n$ = 20, sans avoir pu néanmoins reconnaître d’une façon certaine s’il en existe chaque fois que $n$ est divisible par 4.

Nombres de Hadamard

Par commodité, on appellera ici nombre de Hadamard tout entier $n$ pour lequel il existe effectivement une matrice de Hadamard d’ordre $n$.

La conjecture de Hadamard consiste donc à postuler que les nombres de Hadamard sont exactement 1, 2 et tous les multiples de 4. Cela reste largement non-démontré à ce jour.

Echiquiers anallagmatiques de Sylvester

L’invention des matrices de Hadamard remonte à... 1867, soit 26 ans avant l’article de Hadamard. Elle est due au célèbre mathématicien anglais James Joseph Sylvester [6], dans un article au titre délectable : Thoughts on inverse orthogonal matrices, simultaneous sign-successions, and tessellated pavements in two or more colors, with applications to Newton’s rule, ornamental tile-work, and the theory of numbers [7].

James Joseph SYLVESTER (1814-1897)

Sylvester appellera échiquiers anallagmatiques [8] ses matrices. Pour le lecteur qui serait un peu perdu par cette profusion de noms, précisons bien que échiquier égalitaire, matrice de Hadamard et échiquier anallagmatique sont trois synonymes pour désigner le même objet mathématique !

Dans son article de 1867, Sylvester en construit de tout ordre une puissance de 2, c’est-à-dire de toute taille $n$ x $n$ avec
\[n\, =\, 2^r\, =\, 1,\, 2,\, 4,\, 8,\, 16,\, 32,\, 64,\, \textrm{etc}.\]
Le logo de cet article est justement le cas $n$ = 8 de sa construction.

L’idée de Sylvester est simple et astucieuse, et consiste à montrer que si l’on a un échiquier anallagmatique $A$ d’ordre $n$, alors on peut en construire un nouveau d’ordre $2n$.

Voici comment procéder. Notons $A'$ le négatif de $A$, c’est-à-dire l’échiquier obtenu à partir de $A$ en intervertissant ses deux couleurs. Evidemment, $A'$ est encore un échiquier anallagmatique d’ordre $n$. On construit maintenant l’échiquier $B$ suivant :
\[ B \,=\, \left[ \begin{array}{cc} A & A \\ A & A' \end{array} \right]. \]
On a fini : $B$ est d’ordre $2n$, et c’est toujours un échiquier anallagmatique.

Cela peut se vérifier facilement. Pour une paire de lignes donnée, on distingue deux cas : celui où les deux lignes sont dans la même moitié, supérieure ou inférieure, de $B$ ; et celui où l’une des lignes est dans la moitié supérieure et l’autre dans la moitié inférieure de $B$. Le lecteur est encouragé à pousser les vérifications jusqu’au bout ; pour chauffer le terrain, rien ne vaut l’examen préliminaire de quelques exemples concrets.

Voici les échiquiers anallagmatiques d’ordre $n$ pour $n$ = 2, 4, 8, 16 et 32 obtenus par application répétée de la construction de Sylvester :

Echiquiers anallagmatiques d’ordre 2, 4, 8, ...

... 16 et 32

Regardez bien ce dernier échiquier d’ordre 32 : comme évoqué plus bas, il a joué un rôle clé entre 1969 et 1976 dans la transmission efficace de photos de Mars prises par les sondes Mariner !

Les cas $n$ = 12 et $n$ = 20

C’est Hadamard qui a découvert, dans son article fondateur de 1893, le lien entre « échiquiers anallagmatiques » et le problème fondamental de la maximisation du déterminant. Après avoir rappelé la construction de Sylvester, il entreprend de montrer que d’autres nombres que les puissances de 2 sont réalisables comme ordres de matrices de Hadamard. Spécifiquement, il y parvient pour $n=12$ et $n=20$. Voici les matrices qu’il a obtenues :

Une matrice de Hadamard d’ordre 12 ...

... et une autre d’ordre 20

Curieusement, au lieu de simplement exhiber ses matrices d’ordre 12 et 20 comme ici, Hadamard le fait d’une façon indirecte, mais ayant le grand mérite de révéler leur structure interne.

Pour décrire sa construction à l’ordre 12, nous symboliserons par B une case blanche et par O une case orange.

Tout d’abord, les 3 premières lignes ne présentent aucune difficulté, on peut toujours commencer comme ça : que des B en 1ère ligne, alternance d’une moitié de B et d’une moitié de O en 2ème ligne, et enfin alternance par quarts de B et de O en 3ème ligne.

Reste à décrire les 9 lignes restantes. Pour cela, Hadamard livre le tableau suivant :
\[ \begin{array}{cccc} 1 & 1 & 1 & 1 \\ 1 & 2 & 2 & 2 \\ 1 & 3 & 3 & 3 \\ & & \\ 2 & 1 & 2 & 3 \\ 2 & 2 & 3 & 1 \\ 2 & 3 & 1 & 2 \\ & & \\ 3 & 1 & 3 & 2 \\ 3 & 2 & 1 & 3 \\ 3 & 3 & 2 & 1 \end{array} \]
Dans celui-ci, on remplace maintenant

• les 1 par OBB dans les colonnes 1 et 4, et par BOO dans les colonnes 2 et 3 ;
• les 2 par BOB dans les colonnes 1 et 4, et par OBO dans les colonnes 2 et 3 ;
• les 3 par BBO dans les colonnes 1 et 4, et par OOB dans les colonnes 2 et 3.

C’est fini, on vient d’achever la construction de la matrice d’ordre 12 de Hadamard telle que lui-même l’a présentée.

Il vaut la peine d’examiner de près la structure des quatre colonnes du tableau. La 1ère colonne est très simple, c’est juste 111 222 333. La seconde l’est aussi, c’est juste une triple répétition de 123. Toute la subtilité est concentrée dans les deux dernières colonnes, vues ici horizontalement :
\[ \begin{array}{ccc} 123 & 231 & 312\\ 123 & 312 & 231 \end{array} \]
On voit qu’elles aussi sont des répétitions de 123, mais avec permutations cycliques appropriées.

Cette surprenante description semble être une sorte de piste pour travaux futurs laissée par Hadamard à ses successeurs. On sent bien, en effet, qu’il aurait voulu pouvoir réaliser d’autres ordres que 12 et 20 comme nombres de Hadamard basiques [9], et qu’il sentait que ses constructions devaient pouvoir être généralisées d’une façon ou d’une autre.

Son très judicieux choix de présentation a probablement été à l’origine des progrès ultérieurs majeurs que nous allons maintenant commenter.

Le théorème de Scarpis

Le premier mathématicien à avoir efficacement capté le subtil message de Hadamard est Umberto Scarpis [10]. Voici le théorème qu’il a obtenu en 1898, cinq ans à peine après la parution de l’article de Hadamard [11].

La preuve de Scarpis est constructive, et consiste à combiner astucieusement les lignes de la matrice d’origine pour en construire une nouvelle de plus grande taille. En cela, elle tire certainement son inspiration de la présentation, très combinatoire justement, par Hadamard de sa matrice d’ordre 12. Le grand mérite de Scarpis est d’avoir flairé la présence imperceptible des nombres premiers dans cette construction via permutations cycliques. Scarpis semble d’ailleurs désolé de n’avoir pas pu généraliser l’autre construction de Hadamard, celle à l’ordre 20.

Umberto SCARPIS (Padova 1861- Bologna 1921)

 [12]

Comme premier exemple, le théorème de Scarpis s’applique au cas $n=4$, puisqu’il existe une matrice de Hadamard d’ordre 4 et que 3 est un nombre premier. Scarpis en déduit donc une matrice de Hadamard d’ordre 12. La voici.

Matrice de Hadamard d’ordre 12 par Scarpis

Bien sûr, cet ordre n’est pas nouveau, Hadamard l’avait déjà obtenu. Mais grâce aux échiquiers anallagmatiques de Sylvester, la construction de Scarpis s’applique chaque fois que $n$ est une puissance de 2 avec la propriété supplémentaire que $n-1$ est un nombre premier.

Les nombres de Mersenne

Cela nous conduit tout naturellement à une petite digression : quand donc $2^r-1$ est-il un nombre premier ? Déjà, il faut que $r$ lui-même soit premier [13]. Lorsque $r$ est premier justement, les nombres de la forme $2^r-1$ sont appelés nombres de Mersenne. Eh bien, quels nombres de Mersenne sont-ils premiers ? Cette question reste nimbée de mystères depuis longtemps ; on ne connaît actuellement que quarante-sept premiers de Mersenne, et on ne sait toujours pas s’il en existe une infinité. Voici les quatre plus petits premiers de Mersenne [14] :
\[ 2^2-1=3, \quad 2^3-1=7, \quad 2^5-1=31, \quad 2^7-1=127. \]
Par contre, bien que $2^{11}-1$ soit aussi un nombre de Mersenne puisque 11 est premier, ce n’est pas un premier de Mersenne puisque
\[2^{11}-1=2047 = 23 \times 89.\] Notons enfin que le plus grand nombre premier actuellement connu est justement un premier de Mersenne. Il s’agit de
\[ 2^{43\,112\,609}-1, \]
un monstre à presque 13 millions de chiffres découvert en 2008 dans le cadre collaboratif du Great Internet Mersenne Prime Search, auquel chacun peut d’ailleurs contribuer [15].

Scarpis a donc implicitement établi un lien surprenant entre les premiers de Mersenne et les matrices de Hadamard. Ce lien concerne par exemple $n=8=2^3$, puisque 7 est un premier de Mersenne, et il fournit donc une matrice de Hadamard d’ordre 56. Or ça, c’est bien nouveau en 1898 ! Voici cette matrice :

Matrice de Hadamard d’ordre 56 par Scarpis

Le théorème de Scarpis ne s’applique pas à $2^4=16$, puisque 15 n’est pas premier. Mais il s’applique bien à $n=2^5=32$ puisque 31 est premier, et fournit donc une matrice de Hadamard d’ordre 992. Et bien sûr, il s’applique aussi au monstrueux premier de Mersenne ci-dessus.

Répétition

De plus, dans les cas favorables, la construction de Scarpis peut être répétée. En effet, en partant de $n=4$ comme on l’a vu, elle fournit une matrice de Hadamard d’ordre 12. Mais 11 étant premier, on peut réappliquer la méthode à celle-ci et obtenir ainsi une nouvelle matrice de Hadamard, d’ordre 132 cette fois-ci. La voici en noir et blanc, sans grille [16] :

Matrice de Hadamard d’ordre 132 par Scarpis

En contemplant cet échiquier, on ne peut que constater son incroyablement subtile facture. Souhaitons bon courage au lecteur qui voudrait vérifier, sur la seule base de l’image, que la propriété égalitaire caractéristique des matrices de Hadamard est bien satisfaite : il y a 8646 paires de lignes à passer en revue.

Mais alors, comment peut-on être sûrs que cet échiquier est vraiment anallagmatique ? C’est tout simplement la puissance du langage mathématique qui le permet : l’article de Scarpis ne fait que 6 pages, et sa méthode de construction décrite algébriquement suffit amplement pour vérifier, de façon mathématiquement certaine, que le résultat produit satisfait bien les contraintes requises.

Les théorèmes de Gilman et de Paley

Le premier mathématicien à avoir rebondi sur le théorème de Scarpis est Ray Edwin Gilman [17], qui a montré en 1930 que l’une des hypothèses dans le théorème de Scarpis est automatiquement satisfaite ! Voici son remarquable résultat.

Son idée, très novatrice, fait intervenir la répartition des carrés parfaits $1^2, 2^2, 3^2,$ etc. dans les entiers modulo $p$, où $p$ est le nombre premier $n-1$. Nous y reviendrons plus en détail dans une suite à cet article.

Malheureusement, la seule trace qui reste du travail de Gilman n’est pas un article complet, mais seulement un résumé [18] dans le compte-rendu d’une grande conférence annuelle de l’American Mathematical Society à Cleveland, Ohio en décembre 1930. Le fait est que peu de temps après cette conférence, le résultat de Gilman a été grandement généralisé par Raymond Paley, ce qui a probablement conduit Gilman à retirer son article du processus de publication.

Ray Edwin GILMAN (1887-1975)

 [19]

Voici le tout aussi remarquable résultat de Paley [20].

La construction de Paley est essentiellement la même que celle de Gilman, en plus général : elle se base sur la répartition des carrés parfaits dans une structure algébrique que l’on nomme « corps fini », et dont les entiers modulo $p$ sont un cas particulier.

Raymond Edward Alan Christopher PALEY (1907-1933)

Remarquons au passage la beauté de la situation, dans laquelle des concepts sophistiqués d’algèbre, comme les corps finis justement, permettent de construire des objets mathématiques très concrets comme le sont les matrices de Hadamard. Et ce, alors même que rien a priori ne les liait entre eux. C’est l’une des innombrables manifestations de l’unité des mathématiques.

Jusqu’à 100

Tirons maintenant quelques conséquences des résultats ci-dessus, par exemple parmi les multiples de 4 bornés par 100. Il résulte du théorème de Gilman que parmi eux, les entiers suivants sont tous des nombres de Hadamard :

\[4,\, 8,\, 12,\, 20,\, 24,\, 32,\, 44,\, 48,\, 60,\, 68,\, 72,\, 80\, \textrm{ et }\, 84.\]

Il suffit en effet de constater que $n-1$ est premier pour chaque entier $n$ ci-dessus. A cette liste de nombres de Hadamard, le théorème de Paley permet d’en rajouter cinq de plus :
\[28,\, 36,\, 52,\, 76 \textrm{ et } 100.\]
On constate en effet que
\[ 28-1=27=3^3, \quad \frac{36}{2}-1=17, \quad \frac{52}{2}-1=5^2, \quad \frac{76}{2}-1=37 \quad \textrm{et}\quad \frac{100}{2}-1=7^2. \]
Dans chaque cas, on obtient un premier ou une puissance de premier, et l’on peut donc appliquer le théorème de Paley.

Notons que
\[16,\, 40,\, 56,\, 64,\, 88 \textrm{ et } 96,\]
quoiqu’absents des deux listes ci-dessus, sont eux aussi des nombres de Hadamard. Cela se déduit en appliquant aux deux listes la construction de Sylvester permettant de passer de $n$ à $2n$.

En résumé, rien qu’en utilisant les théorèmes de Gilman/Paley et la construction de doublement de Sylvester, on trouve que tous les multiples de 4 bornés par 100 — sauf 92, le seul absent des trois listes — sont des nombres de Hadamard !

L’entier $n=92$ est lui aussi un nombre de Hadamard, mais cela n’a été obtenu que bien plus tard, grâce à une construction générale proposée par Williamson en 1944 et rendue ensuite effective pour $n=92$ par un gros calcul sur ordinateur dû à Baumert, Golomb et Hall en 1962.

Etat des connaissances

De nombreux progrès ont été accomplis depuis, mais on est encore très loin d’une solution complète du problème. L’état des connaissances actuelles sur la conjecture de Hadamard est d’ailleurs très contrasté.

D’un côté, de nombreuses constructions de matrices et de nombres de Hadamard sont maintenant connues. Jusqu’en 2004, les chercheurs ont pu établir que tous les multiples de 4 bornés par 1000 sont des nombres de Hadamard, sauf éventuellement les cinq nombres 428, 668, 716, 764 et 892.

Puis 428 et 764 sont tombés, en 2005 et 2008 respectivement, grâce à des calculs sur ordinateur à la fois futés et massifs ayant abouti à des matrices de Hadamard de ces ordres-là. Le cas $n=428$ est dû à H. Kharaghani et B. Tayfeh-Rezaie, et le cas $n=764$ à D.Z. Djokovic.

A ce jour donc, seuls trois cas inférieurs à 1000 restent encore en suspens :
\[668,\, 716 \textrm{ et } 892.\]
Autrement dit, pour tout $n$ multiple de 4 et inférieur ou égal à 1000, on connaît une matrice de Hadamard d’ordre $n$, sauf pour l’un de ces trois cas. C’est assez remarquable.

Mais on en sait déjà moins pour les multiples de 4 compris entre 1000 et 2000, où il reste dix cas en suspens, c’est-à-dire dont on ignore encore s’ils sont des nombres de Hadamard ou pas. Ces dix cas en suspens sont :
\[ 1004,\, 1132,\, 1244,\, 1388,\, 1436,\, 1676,\, 1772,\, 1916,\, 1948 \textrm{ et } 1964. \]

D’un autre côté, asymptotiquement parlant, on ne sait pratiquement rien. En effet, pour un très grand multiple de 4 sans propriété arithmétique particulière, on ne sait pas dire en général si c’est un nombre de Hadamard ou pas. Plus précisément, lorsque $N$ tend vers l’infini, la densité des $n \le 10^N$ multiples de 4 et pour lesquels on connaît en 2012 une matrice de Hadamard d’ordre $n$ tend vers 0. On est loin de la densité 1/4 entraînée par la conjecture.

Le contraste est saisissant : d’un côté on en sait énormément, comme le montre la situation jusqu’à 1000, mais de l’autre on ne sait pratiquement rien lorsqu’on file vers l’infini. C’est un peu contradictoire, mais telle est la situation actuelle.

Un scoop exclusif !

Alors que la rédaction de cet article est presque terminée, mon collègue Ilias Kotsireas, de l’Université Wilfrid-Laurier à Waterloo au Canada, m’informe d’un scoop majeur en ce début septembre : il vient de construire, en collaboration avec D. Djokovic et O. Golubitsky, une matrice de Hadamard d’ordre 1004.

Leur article n’est pas encore disponible. C’est donc en primeur mondiale que les lecteurs de Images des Mathématiques sont informés de cette avancée !

Parmi les multiples de 4 entre 1000 et 2000 encore en attente du statut officiel de nombre de Hadamard, on peut donc rayer 1004 de la liste ci-dessus, qui se réduit désormais à neuf nombres en suspens :
\[ 1132,\, 1244,\, 1388,\, 1436,\, 1676,\, 1772,\, 1916,\, 1948 \textrm{ et } 1964. \]

Applications

Les applications mathématiques et technologiques des matrices de Hadamard sont nombreuses, que ce soit en algèbre, en statistiques, en cryptographie, dans les théories du codage, du signal, des télécommunications, etc. En téléphonie mobile par exemple, ces matrices sont utilisées pour bien séparer les unes des autres les conversations simultanées de centaines d’utilisateurs. Voir par exemple le chapitre 3 du livre « Hadamard matrices and their applications » de Kathy Horadam [21].

Une jolie application, liée à l’actualité de l’exploration planétaire et sa mission Curiosity, concerne des missions passées vers la planète Mars. On y a déjà fait allusion plus haut. En effet, l’échiquier anallagmatique d’ordre 32 de Sylvester a joué un rôle clé dans toutes les missions Mariner de la NASA, de 1969 à 1976. Grâce à cet échiquier et à un code correcteur d’erreurs basé dessus [22], les sondes Mariner ont pu nous transmettre efficacement toutes les photos qu’elles prenaient de Mars. En voici une, prise par Mariner 9 en 1972 :

Noctis Labyrinthus, extrémité ouest de Valles Marineris sur Mars (photo par Mariner 9, 1972)

C’est la qualité des photos transmises par Mariner 9, justement, qui a permis la découverte de Valles Marineris, gigantesque système de canyons sur Mars de plus de 4000 km de long, 200 km de large et jusqu’à 7 km de profondeur. Cette magnifique mosaïque de 102 photos prises ultérieurement par la sonde Viking 1 en 1980 en fournit une vue globale :

Valles Marineris (assemblage de photos par Viking 1, 1980)

C’est toujours émouvant lorsqu’un objet mathématique, inventé dans son contexte propre, se voit attribuer un rôle clé dans un projet technologique des décennies ou des siècles plus tard. Le fait que la NASA ait eu besoin, pour son programme Mariner, d’un échiquier anallagmatique inventé par pur jeu intellectuel un siècle auparavant est savoureux.

Cela confirme une fois encore que tout objet mathématique, aussi abstrait soit-il, est susceptible de servir un jour à des applications complètement inattendues, même s’il faut attendre des décennies, des siècles voire des millénaires pour cela. Un autre exemple, sans doute plus connu, est celui des nombres premiers : étudiés depuis l’Antiquité pour leur beauté propre, ils jouent maintenant un rôle crucial en cryptographie et dans la sécurisation des transactions sur Internet.

Pour la suite

Dans une prochaine suite à cet article, sur piste rouge, on abordera quelques détails mathématiques supplémentaires relatifs à la conjecture de Hadamard. On y parlera de déterminants, de vecteurs orthogonaux, d’arithmétique modulaire et de corps finis.