La conjecture de Hadamard (I)

Piste bleue 22 septembre 2012  - Ecrit par  Shalom Eliahou Voir les commentaires (7)

L’étrange échiquier 8 x 8 du logo est, dans un sens, plus égalitaire qu’un échiquier standard : pour chaque paire de lignes, il y a exactement une moitié des colonnes dont les deux cases sont de même couleur. Quelles sont les autres tailles possibles $n$ x $n$ de tels échiquiers égalitaires ? Ce problème a des ramifications mathématiques et technologiques très riches, et reste largement ouvert depuis... 1893.

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 :

GIF - 2 ko
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 :

GIF - 2.3 ko
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].

JPEG - 12.1 ko
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.

Pourquoi ?

Discutons d’abord les cas $n=1$ et $n=2$. Pour $n=1$, l’échiquier à une case est bien une matrice de Hadamard, puisque s’il n’y a qu’une seule ligne, la condition égalitaire portant sur les paires de lignes est automatiquement satisfaite ! Pour $n=2$, le lecteur trouvera sans peine les matrices requises.

Supposons maintenant que $n$ est supérieur ou égal à $3$ et qu’il existe une matrice de Hadamard $A$ d’ordre $n$. Montrons alors, en dix étapes élémentaires, que $n$ est un multiple de $4$. On peut zapper cette preuve sans risques pour la compréhension du reste de l’article.

  • (1) Si l’on permute deux lignes de $A$, ou deux colonnes de $A$, la matrice résultante est encore de Hadamard. Cela découle de la définition.
  • (2) De même, si l’on intervertit les deux couleurs dans une ligne ou dans une colonne quelconque de $A$, la matrice résultante est toujours de Hadamard.
  • (3) On peut supposer, sans perte de généralité, que la 1ère ligne de $A$ ne contient que des cases blanches. Pour y arriver, on cherche toutes les cases orange de cette 1ère ligne, et on intervertit les deux couleurs dans les colonnes correspondantes. Selon le point (2), la matrice résultante est encore de Hadamard.
  • (4) Comparons les deux premières lignes, sous l’hypothèse du point (3). Selon la propriété égalitaire, la 2ème ligne doit contenir autant de cases blanches que de cases orange. Cela force donc $n$ à être pair, déjà. Posons $m = n/2$.
  • (5) Pour la même raison, la 3ème ligne contient $m$ cases blanches et $m$ cases orange.
  • (6) Revenons à la 2ème ligne. Quitte à permuter ses colonnes grâce au point (1), on peut supposer sans perte que ses $m$ premières cases sont blanches et ses $m$ dernières cases sont orange.
  • (7) Revenons à la 3ème ligne. Parmi ses $m$ premières cases, posons $b_1$ le nombre de blanches et $o_1$ le nombre d’orange. Et parmi ses $m$ dernières cases, posons $b_2$ le nombre de blanches et $o_2$ le nombre d’orange. Que valent ces quatre quantités ?
  • (8) D’après le point (5), on a $b_1+b_2=m$ et $o_1+o_2=m$.
  • (9) De même, de par la propriété égalitaire pour les 2ème et 3ème lignes, on doit avoir $b_1+o_2=m$ et $o_1+b_2=m$.
  • (10) Quelques petites manipulations algébriques sur ces équations permettent de conclure que $b_1$, $b_2$, $o_1$ et $o_2$ sont tous égaux. Or comme $b_1+b_2$ égale $m$, il suit que $m$ vaut $2b_1$, et donc in fine que $n$, le double de $m$, vaut $4b_1$.

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.

Conjecture (Hadamard, 1893). Pour tout entier naturel $n$ multiple de 4, il existe une matrice de Hadamard d’ordre $n$.

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].

JPEG - 15.2 ko
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 :

GIF - 5.3 ko
Une matrice de Hadamard d’ordre 12 ...
GIF - 9.7 ko
... 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].

Théorème (Scarpis, 1898). Soit $n$ un multiple de 4 tel que $n-1$ soit un nombre premier. S’il existe une matrice de Hadamard d’ordre $n$, alors il en existe une plus grande d’ordre $(n-1)n$.

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.

JPEG - 10.6 ko
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.

Petit aparté : traduction algébrique

En quoi le langage algébrique peut-il être utile dans ce contexte ? Reprenons le dictionnaire naturel, auquel on a fait allusion plus haut, entre échiquiers et matrices ne contenant que des $1$ et des $-1$.

Eh bien, avec des nombres plutôt que des couleurs, la condition égalitaire portant sur les paires de lignes peut s’exprimer algébriquement de façon très simple. En effet, si l’on représente nos deux lignes par
\[ \begin{array}{l} x_1\quad x_2\quad \cdots\quad x_n \\ y_1\quad y_2\quad \cdots\quad y_n, \end{array} \]
où les $x_i$ et $y_i$ sont maintenant des $1$ et des $-1$, alors la condition égalitaire sur ces deux lignes est exactement équivalente à la condition
\[ x_1y_1\,+\,x_2y_2\,+\,\ldots\,+\,x_ny_n \,=\, 0. \]
Se convaincre de l’équivalence est facile : chaque concordance de coefficients, c’est-à-dire soit deux $1$ soit deux $-1$, contribue pour $+1$ à la somme ci-dessus, tandis que chaque discordance contribue pour $-1$. Du coup, si on a autant de concordances que de discordances, la somme fait 0. Et réciproquement.

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.

Théorème (Gilman, 1930). Soit $n$ un multiple de 4 tel que $n-1$ soit un nombre premier. Alors il existe une matrice de Hadamard d’ordre $n$.

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.

JPEG - 254.7 ko
Ray Edwin GILMAN (1887-1975)

 [19]

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

Théorème (Paley, 1933). Soit $n$ un multiple de 4 tel que $n-1$ ou $n/2-1$ soit une puissance de nombre premier. Alors il existe une matrice de Hadamard d’ordre $n$.

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.

JPEG - 19.7 ko
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 :

JPEG - 47.2 ko
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.

Post-scriptum :

L’auteur remercie Bruno Martin pour ses commentaires. La rédaction d’Images des maths et l’auteur, remercient pour leur relecture attentive, les relecteurs suivants : Martin Andler, Sylvain Barré, Rémi Coulon, Carole Gaboriau, Antonin Guilloux, Aline Parreau et Franz Ridde.

Article édité par Shalom Eliahou

Notes

[1Pour reprendre les termes mêmes de l’article fondateur de Jacques Hadamard en 1893.

[2Hadamard est un géant des maths, dont la mémoire vient d’être honorée par l’établissement en 2011 d’une Fondation de recherche mathématique de haut niveau portant son nom. Voir sa biographie en anglais sur le site McTutor History of Mathematics.

[3Egalement obtenue, la même année, par Charles de La Vallée Poussin.

[4J. Hadamard, « Sur le module maximum que puisse atteindre un déterminant », C. R. Acad. Sci. Paris 116 (1893) 1500-1501.

[5J. Hadamard, « Résolution d’une question relative aux déterminants », Bull. des Sciences Mathématiques 17 (1893) 240-246.

[6Sylvester a eu une carrière plutôt mouvementée, comme le montre sa biographie en anglais sur McTutor. Il a, entre autres, fondé en 1878 l’American Journal of Mathematics, premier journal de recherche mathématique aux Etats-Unis.

[7Philosophical Magazine 34 (1867), 461-475. Voici une traduction libre du titre : Pensées sur les matrices orthogonales inverses, les suites simultanées de signes, et les pavements de mosaïques en deux couleurs ou plus, avec applications à la règle de Newton, aux pavages ornementaux, et à la théorie des nombres.

[8Le terme grec an-allagma signifie « sans changement », et se réfère aux manipulations sur les lignes et les colonnes que l’on peut faire sur un tel échiquier sans changer sa propriété égalitaire. Cela est expliqué en page 186 du très intéressant article de Anne-Marie Décaillot, « Géométrie des tissus. Mosaïques. Echiquiers. Mathématiques curieuses et utiles », Revue d’histoire des mathématiques 8 (2002) 145-206.

[9Par application répétée du doublement de Sylvester à partir de $12$, les nombres $24$, $48$, $96$, etc. sont eux aussi des nombres de Hadamard, mais ils sont moins basiques que $12$ puisqu’ils s’en déduisent.

[10Une brève description de la vie et de l’oeuvre de Umberto Scarpis se trouve dans cet article récent, en italien, de Maurizio Emaldi.

[11U. Scarpis, « Sui determinanti di valore massimo », Rendiconti dello Reale Instituto Lombardo di Scienze e Lettere (2), 31 (1898) 1441-1446. Merci à Andrea Montoli, ex-thésard à Milan en cotutelle avec Calais, d’avoir bien voulu activer ses contacts milanais pour m’obtenir une copie de cet article.

[12Merci à Pietro Rosa, professeur au Liceo Minghetti à Bologne, d’avoir repéré cette photo dans les archives historiques de l’Université de Bologne et de me l’avoir aimablement communiquée pour cet article.

[13En effet, si $d$ divise $r$ alors $2^d-1$ divise $2^r-1$. Cela découle par exemple de l’identité remarquable \[a^n-b^n=(a-b)(a^{n-1}+a^{n-2}b+\dots+ab^{n-2}+b^{n-1}),\] en posant $a=2^d$, $b=1^d=1$ et $n=r/d$.

[14Pour ne pas dire « les quatre premiers premiers de Mersenne ».

[15Le site officiel du Great Internet Mersenne Prime Search est ici.

[16Eh non, désolé, ce n’est pas un flashcode !

[17Il a été professeur de mathématiques à Brown University, dont le site héberge une courte biographie en anglais.

[18R. E. Gilman, « On the Hadamard determinant theorem and orthogonal determinants », Bulletin Amer. Math. Soc. 37 (1931), 30-31. Voici le texte complet de ce résumé :

It is well known that the Hadamard upper bound for the value of a determinant whose elements do not exceed unity in absolute value can, in the case of determinants with real elements, only be attained when the order is a multiple of four. The problem here attacked was proposed by Hadamard in his original paper, namely to discover whether maximum determinants for all orders which are multiples of four attain the Hadamard bound. It is proved that the Hadamard bound is attained for determinants of order $p=2^{\nu} n_1^{\nu_1} n_2^{\nu_2} n_3^{\nu_3} \cdots n_k^{\nu_k}$ where the $n_i$ are multiples of four for which $n_i-1$ are prime, and where $\nu_i-1$ is any positive integer or zero. No statement is made as to the other cases. What is believed to be a new proof of the Hadamard theorem for determinants with real elements, is given. (Received November 30, 1930.)

[19Merci à Jeffrey Hoffstein, directeur du département de mathématiques de Brown University, pour cette photo aimablement envoyée moins d’une heure après ma requête.

[20Paley était un brillantissime jeune mathématicien anglais, hélas mort prématurément à l’âge de 26 ans dans un accident de montagne au Canada. Il est l’auteur d’un célèbre théorème avec Norbert Wiener — un théorème de mathématiques abstraites motivé par la compréhension des débuts de l’électronique. Voir sa biographie en anglais sur McTutor.

[21K.J. Horadam, « Hadamard matrices and their applications », Princeton University Press, 2007

[22Pour plus de détails, voir cet article en anglais sur Wikipedia.

Partager cet article

Pour citer cet article :

Shalom Eliahou — «La conjecture de Hadamard (I)» — Images des Mathématiques, CNRS, 2012

Crédits image :

Image à la une - Les images des échiquiers ont été produites avec Mathematica 7.
Umberto SCARPIS (Padova 1861- Bologna 1921) - Archives historiques de l’Université de Bologne, http://www.archiviostorico.unibo.it

Commentaire sur l'article

  • La conjecture de Hadamard (I)

    le 22 septembre 2012 à 13:57, par B !gre

    Merci pour cet excellent article ! On attend la suite avec impatience.

    Répondre à ce message
    • La conjecture de Hadamard (I)

      le 22 septembre 2012 à 19:28, par Shalom Eliahou

      Merci ! La suite est pour le prochain trimestre au plus tard, enfin j’espère.

      Shalom

      Répondre à ce message
  • La conjecture de Hadamard (I)

    le 22 septembre 2012 à 18:35, par ROUX

    Très bel article.

    Je comprends qu’il existe des échiquiers égalitaires dans le damier 8 fois 8.

    Je comprends qu’il existe des damiers 8 fois 8 qui ne sont pas égalitaires.

    Je comprends qu’on ne peut pas trouver de damiers égalitaires dans des damiers « n fois n » si « n » n’est pas un multiple de 4.

    Est-ce que je comprends bien ?

    Répondre à ce message
    • La conjecture de Hadamard (I)

      le 22 septembre 2012 à 19:34, par Shalom Eliahou

      Merci !

      Oui, c’est tout à fait juste. Petit détail quand même pour le dernier point : il existe des damiers égalitaires « 1 fois 1 » et « 2 fois 2 », mais ce sont des cas vraiment limite. Par contre, effectivement, dès que « n » vaut au moins 3 et n’est pas un multiple de 4, il n’existe aucun damier égalitaire « n fois n ».

      Shalom

      Répondre à ce message
  • Unicité des matrices d’Hadamard ???

    le 2 octobre 2012 à 21:55, par Quentin

    Bonjour,

    une fois que l’on a l’existence de quelque chose, il est assez naturel de ce poser la question de l’unicité :
    Combien y a-t-il de matrices d’Hadamard pour un multiple de 4 donné (aux permutations de lignes, colones et couleurs près) ?
    Existe il des conjectures sur ce nombre ?

    Merci pour cet article et d’avance pour la réponse.

    Répondre à ce message
    • Unicité des matrices d’Hadamard ???

      le 3 octobre 2012 à 17:32, par Shalom Eliahou

      Bonjour,

      il s’agit effectivement d’une question très naturelle et très intéressante. Elle est en plus très difficile : à ce stade, la réponse n’est exactement connue que jusqu’à $n = 28$.

      Pour décrire ce qu’on en sait, notons $h(n)$ le nombre que vous mentionnez, à savoir le nombre de matrices de Hadamard d’ordre $n$, aux permutations de lignes, de colonnes et de couleurs près.

      Voici les seules valeurs exactes de $h(n)$ connues à ce jour :

      • $h(n) = 1$ pour $n =1, 2, 4, 8, 12$.
      • $h(16) = 5$ ; $h(20) = 3$ ; $h(24) = 60$ ; $h(28) = 487$.

      Au delà, seules quelques bornes inférieures sont connues. Je citerai juste les deux suivantes, dues à William Orrick en 2008 :

      • $h(32) \ge 3.578.006$,
      • $h(36) \ge 18.292.717$.

      A partir de $n=40$, on ne sait plus grand chose, et on ignore comment $h(n)$ pourrait se comporter en général.

      Quoiqu’il en soit, les résultats ci-dessus montrent que les matrices de Hadamard semblent fort abondantes ! Et pourtant, on reste loin de savoir montrer qu’il en existe au moins une de tout ordre $n$ multiple de 4.

      Bien cordialement,

      Shalom

      Répondre à ce message
  • La conjecture de Hadamard (I)

    le 5 octobre 2012 à 16:59, par Voaary

    bravo pour cet article très intéressant sur la conjecture d’Hadamard et son application. Vivement la suite.

    Répondre à ce message

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.

Connexions’inscriremot de passe oublié ?

Dossiers

Cet article fait partie du dossier «Jacques Hadamard» voir le dossier

Suivre IDM