Les nombres de Schur, des centenaires pleins d’avenir

Piste bleue Le 21 décembre 2016  - Ecrit par  Shalom Eliahou Voir les commentaires (13)

En 1916, le grand mathématicien Issai Schur donnait naissance à une suite de nombres entiers encore très mystérieux, même après un siècle d’existence. Il ne s’agit pourtant que de colorier les entiers naturels en respectant quelques contraintes...

Introduction

Il y a un siècle exactement, en 1916, le grand mathématicien juif allemand Issai Schur (1875-1941) donnait naissance à une suite de nombres entiers $S(1),S(2), S(3),\dots$ très intéressants et si mystérieux que, même 100 ans après, on ne sait encore presque rien sur eux.

Ces nombres de Schur, comme on les appelle depuis, méritent d’être plus largement connus. D’où cet article, dans lequel on verra leur définition, le contexte de leur naissance, les faibles connaissances actuelles à leur sujet, et enfin une conjecture à propos du cinquième d’entre eux, soit $S(5)$.

Pourquoi le cinquième, d’ailleurs ? Tout simplement parce qu’on ne connaît exactement que les quatre premiers, et qu’à partir du sixième, on en sait si peu qu’on ne dispose même pas de conjectures spécifiques quant à leurs valeurs possibles. Sans le moindre doute, les nombres de Schur continueront pendant longtemps encore à faire l’objet de recherches pour percer leurs mystères [1].

Valeurs connues

Mais levons tout de suite un premier coin du voile. Voici les quatre premiers nombres de Schur, les seuls connus à ce jour.

Les quatre premiers nombres de Schur :
\[ \begin{array}{rrr} S(1) & = & \color{red}{1} \\ S(2) & = & \color{red}{4} \\ S(3) & = & \color{red}{13} \\ S(4) & = & \color{red}{44} \end{array} \]

Qu’en est-il de $S(5)$ ? On sait seulement qu’il se situe quelque part entre $160$ et $305$. Mais selon une conjecture datant de l’an 2000, la valeur de $S(5)$ pourrait bien être $160$, en fait. On y reviendra plus loin.

Comment sont-ils donc définis, ces fameux nombres de Schur ? Un peu de patience, chère lectrice, cher lecteur. Abordons tranquillement les quelques bases nécessaires avant de répondre.

Colorions les nombres entiers

Commençons par fixer un nombre $n$ de couleurs, par exemple $n=2$. Comme palette de couleurs, prenons rouge et bleu, disons ; ce qui compte, ce n’est pas ce choix particulier de couleurs, c’est leur nombre.

Maintenant, assignons à chaque entier naturel une couleur de notre palette. Par exemple, colorions en rouge les entiers impairs et en bleu les entiers pairs. Les entiers impairs forment alors un sous-ensemble monochromatique, c’est-à-dire d’une seule couleur. Les entiers pairs aussi, d’ailleurs.

À l’opposé de ce premier exemple, prenons maintenant un coloriage aussi aléatoire et irrégulier que possible, par exemple celui-ci :
\[ \color{red}{1}, \color{red}{2}, \color{blue}{3}, \color{red}{4}, \color{blue}{5},\color{blue}{6},\color{red}{7},\color{red}{8},\color{blue}{9},\color{red}{10},\dots \]
à étendre comme on veut ou avec pile-ou-face. La question qui nous intéresse ici est alors la suivante : malgré l’aspect arbitraire et irrégulier d’un tel coloriage, trouvera-t-on forcément des régularités monochromatiques ? Il nous faut, bien sûr, préciser ce que l’on entend par régularités.

Un exemple : les progressions arithmétiques

Dans un célèbre théorème de Baart van der Waerden en 1927, les régularités cherchées sont les progressions arithmétiques de longueur $k$ donnée, soit les suites d’entiers de la forme
\[ a, a+d, a+2d, \dots, a+(k-1)d. \]
Le théorème de van der Waerden dit que, quel que soit le coloriage en un nombre fini de couleurs des entiers naturels, il est impossible d’éviter l’émergence d’une progression arithmétique de longueur donnée qui soit monochromatique.

Pour Schur, les régularités cherchées sont très simples, ce sont juste les triplets de nombres $(a,b,c)$ tels que $c=a+b$ ; autrement dit, les triplets de la forme \[(a,b,a+b)\] comme $(1,1,2)$ ou $(3,5,8)$ par exemple.

La question est donc : quel que soit le coloriage en deux couleurs des entiers naturels, aussi irrégulier soit-il, trouvera-t-on forcément un tel triplet $(a,b,a+b)$ qui soit monochromatique ?

Dans l’exemple $\color{red}{1}, \color{red}{2}, \color{blue}{3}, \color{red}{4}, \color{blue}{5},\color{blue}{6},\color{red}{7},\color{red}{8},\color{blue}{9},\color{red}{10},\dots$ ci-dessus, la réponse est oui : prendre $(a,b,a+b)=(\color{red}{1},\color{red}{7},\color{red}{8})$, ou $(\color{red}{2},\color{red}{8},\color{red}{10})$, ou encore $(\color{blue}{3},\color{blue}{6},\color{blue}{9})$.

C’est le coeur du sujet, alors répétons-le, mais pour un nombre fini $n$ quelconque de couleurs.

Question.
Pour un coloriage arbitraire en $n$ couleurs des entiers naturels, trouvera-t-on forcément un triplet monochromatique de la forme $(a,b,a+b)$ ?

Le théorème de Schur

Voici la réponse formelle de Schur. Elle est positive !

Théorème (Schur, 1916). Soit $n$ un nombre donné de couleurs. Pour tout coloriage en $n$ couleurs des entiers naturels $1,2,3,\dots$, on trouvera forcément trois entiers naturels $a,b,c$ de même couleur tels que $a+b=c$ ; autrement dit, un triplet monochromatique de la forme $(a,b,a+b)$.

Précisons qu’ici, il n’est pas interdit d’avoir $b=a$. Dans ce cas, le triplet $(a,b,a+b)$ devient $(a,a,2a)$ ; en particulier, si $a$ et $2a$ sont de même couleur, alors le triplet $(a,a,2a)$ sera à la fois monochromatique et de la forme spécifiée $(a,b,a+b)$.

Une version équivalente de ce théorème donne quelques précisions supplémentaires et donne naissance, enfin, aux fameux nombres de Schur $S(n)$.

Théorème (Schur, 1916). Pour $n$ donné, il existe un nombre $S(n)$ défini ainsi : c’est le plus grand entier $N$ pour lequel il est possible de colorier en $n$ couleurs les entiers de $1$ à $N$ de façon à exclure tout triplet monochromatique de la forme $(a,b,a+b)$ avec $a,b,a+b$ compris entre $1$ et $N$.

Ce qui n’est nullement évident a priori dans ce théorème [2], c’est l’existence du nombre $S(n)$ doté de la propriété désirée. Ce n’est pas évident mais c’est néanmoins vrai, comme cela a été rigoureusement démontré par Schur, et comme quiconque ouvert au raisonnement mathématique peut le vérifier.

De l’équivalence entre les deux versions du théorème

Le fait que les deux versions ci-dessus du théorème de Schur soient équivalentes n’est pas complètement évident. D’où ce petit supplément d’information.

La première version affirme l’inévitabilité d’un triplet $(a,b,a+b)$ monochromatique pour un coloriage en $n$ couleurs de tous les entiers naturels, tandis que pour atteindre la même conclusion dans la seconde version, on peut se restreindre à un coloriage en $n$ couleurs des $S(n)$ premiers entiers naturels seulement. La seconde version entraîne donc la première.

Par contre, le fait que la première version entraîne la seconde est plus subtil et repose sur un principe général fort utile appelé principe de compacité.

Que vaut le nombre de Schur $S(2)$ ?

On se donne une palette de deux couleurs, disons rouge et bleu. Pour déterminer la valeur de $S(2)$, voici la question à laquelle il nous faut répondre.

Question.
Jusqu’à quel entier maximal $N$ peut-on colorier en rouge ou bleu chaque entier de $1$ à $N$ de façon à éviter complètement l’émergence de triplets $(a,b,a+b)$ monochromatiques ?

Une fois trouvé ce $N$ maximal, on aura notre réponse : $S(2)=N$.

Démontrons maintenant que le $N$ cherché vaut $4$. Aucune formule hermétique n’est requise pour cela ; il suffit de poser quelques observations sur la table et de raisonner un peu sur ces bases, comme pour n’importe quelle enquête.

Pour commencer, dressons la liste de tous les triplets de la forme $(a,b,a+b)$ dont les éléments constitutifs $a,b,a+b$ sont compris entre $1$ et $4$. La voici.

Triplets $(a,b,a+b)$ entre $1$ et $4$ :
\[ (1,1,2), \, (1,2,3), \, (1,3,4), \, (2,2,4). \]

Cette liste est bien complète, mis à part $(2,1,3)$ et $(3,1,4)$ qu’on peut froidement ignorer, puisque l’ordre entre les deux premiers termes $a,b$ ne joue aucun rôle dans ce problème.

Alors donc, peut-on colorier les entiers $1,2,3,4$ en deux couleurs de façon à ce qu’aucun de ces quatre triplets $(a,b,a+b)$ ne soit monochromatique ?

Eh bien oui, le bicoloriage suivant répond à cette contrainte :
$ \color{red}{1}, \ \color{blue}{2}, \ \color{blue}{3}, \ \color{red}{4}. $
En effet, les quatre triplets concernés deviennent
\[ (\color{red}{1},\color{red}{1},\color{blue}{2}), \, (\color{red}{1},\color{blue}{2},\color{blue}{3}), \, (\color{red}{1},\color{blue}{3},\color{red}{4}), \, (\color{blue}{2},\color{blue}{2},\color{red}{4}) \]
et, visiblement, aucun n’est monochromatique.

Montrons maintenant qu’on ne peut pas construire un tel bicoloriage pour $N=5$. En effet, pour fixer les idées et sans perte de généralité, assignons à $1$ la couleur rouge [3]. Pour empêcher que $(\color{red}{1},\color{red}{1},2)$ ne soit monochromatique, il nous faut alors colorier $2$ en bleu. Mais maintenant, pour empêcher que $(\color{blue}{2},\color{blue}{2},4)$ ne soit monochromatique, il nous faut colorier $4$ en rouge. Donc $\color{red}{1}$ et $\color{red}{4}$ sont tous deux rouges. Du coup, la seule façon d’empêcher que le triplet $(\color{red}{1},3,\color{red}{4})$ ne soit monochromatique est de colorier $3$ en bleu.

En résumé, voici l’état actuel de notre coloriage des entiers de $1$ à $4$, le seul possible à ce stade pour exclure les triplets $(a,b,a+b)$ monochromatiques :
\[ \color{red}{1},\ \color{blue}{2}, \ \color{blue}{3}, \ \color{red}{4}. \]

Maintenant, quelle couleur peut-on assigner à $5$ tout en continuant à exclure les triplets $(a,b,a+b)$ monochromatiques ? Ni rouge ni bleu, à cause des triplets $(\color{red}{1},\color{red}{4},5)$ et $(\color{blue}{2},\color{blue}{3},5)$, tous deux de la forme spécifiée ! Bref, en bicoloriant chaque entier de $1$ à $5$ en rouge ou bleu, il s’avère impossible d’éviter l’émergence d’un triplet $(a,b,a+b)$ monochromatique.

Résumons : il est possible de colorier les entiers de $1$ à $4$ en deux couleurs tout en excluant les triplets $(a,b,a+b)$ monochromatiques, mais il est impossible de faire de même pour les entiers de $1$ à $5$. On vient donc de démontrer l’égalité

\[S(2)=4.\]

Que vaut $S(3)$ ?

Sans plus attendre, rappelons la réponse donnée plus haut :

\[S(3)=13.\]

Pour démontrer cette égalité, et comme pour la détermination de $S(2)$, il faut réaliser deux choses :

  • Construire un coloriage des entiers de $1$ à $13$ en trois couleurs excluant les triplets monochromatiques de la forme $(a,b,a+b)$.

Le logo de cet article fournit une solution pour ce point :
\[ \begin{array}{l} \\ \hline \color{red}{1, \ 4, \ 10, \ 13} \\ \hline \color{blue}{2, \ 3, \ 11, \ 12} \\ \hline \color{green}{5, \ 6, \ 7, \ 8, \ 9} \\ \hline \\ \end{array} \]
Comme on peut aisément le vérifier, il n’y a aucun triplet $(a,b,a+b)$ qui soit tout rouge, ou tout bleu, ou tout vert pour ce coloriage spécifique.

  • Démontrer que $13$ est maximal pour cette propriété. Autrement dit, démontrer que pour tout coloriage des entiers de $1$ à $14$ en trois couleurs, il est impossible d’éviter l’émergence d’au moins un triplet monochromatique de la forme $(a,b,a+b)$.

Nous ne donnerons pas de démonstration ici. Mais tout un chacun, moyennant suffisamment d’essais et de patience, un peu comme face à une grille de sudoku de niveau difficile, peut tenter d’en établir une. Je fais le pari que plusieurs lectrices et lecteurs y parviendront. Cela peut aussi constituer un excellent exercice de réflexion ou de programmation pour ados en quête de défis corsés.

Que vaut $S(4)$ ?

Là encore, rappelons la valeur annoncée plus haut :

\[S(4)=44.\]

  • Pour démontrer l’inégalité $S(4) \ge 44$, considérons le coloriage suivant en quatre couleurs des entiers de $1$ à $44$ :

\[ \begin{array}{l} \\ \hline \color{red}{1, \ 3, \ 5, \ 15, \ 17, \ 19, \ 26, \ 28, \ 40, \ 42, \ 44} \\ \hline \color{blue}{2, \ 7, \ 8, \ 18, \ 21, \ 24, \ 27, \ 33, \ 37, \ 38, \ 43} \\ \hline \color{green}{4, \ 6, \ 13, \ 20, \ 22, \ 23, \ 25, \ 30, \ 32, \ 39, \ 41} \\ \hline \color{orange}{9, \ 10, \ 11, \ 12, \ 14, \ 16, \ 29, \ 31, \ 34, \ 35, \ 36} \\ \hline \\ \end{array} \]

Eh bien, avec une bonne dose de patience, on peut vérifier que pour ce coloriage spécifique, il n’existe aucun triplet $(a,b,a+b)$ qui soit monochromatique. Voici par exemple quelques triplets de la forme $(a,b,a+b)$ :
\[ (\color{red}{1},\color{red}{3},\color{green}{4}), \ (\color{red}{1},\color{red}{5},\color{green}{6}), \ (\color{red}{3},\color{red}{5},\color{blue}{8}), \ (\color{blue}{2},\color{blue}{7},\color{orange}{9}), \ (\color{green}{4},\color{green}{6},\color{orange}{10}), \ (\color{orange}{9},\color{orange}{10},\color{red}{19}), \dots \]
Cela démontre l’inégalité $S(4) \ge 44$.

  • Pour démontrer l’inégalité inverse, soit $S(4) \le 44$, il faut s’assurer que pour tous les coloriages possibles en quatre couleurs des entiers de $1$ à $45$ maintenant, il y aura toujours au moins un triplet $(a,b,a+b)$ monochromatique.

Hélas, les outils théoriques actuellement à notre disposition pour ce faire s’avèrent insuffisants ; c’est seulement grâce à une vérification exhaustive par ordinateur qu’on arrive à l’établir. Le premier à l’avoir fait est Leonard Baumert en 1961.

Une conjecture sur $S(5)$

A l’heure actuelle, on sait seulement que $S(5)$ se situe quelque part entre $160$ et $305$. On dispose cependant de la conjecture suivante, formulée par Harold Fredricksen et Melvin Sweet en l’an 2000.

Conjecture. Le nombre de Schur $S(5)$ vaut probablement $160$.

  • Pour démontrer l’inégalité $S(5) \ge 160$, il « suffit » d’exhiber un coloriage en $5$ couleurs des entiers de $1$ à $160$ excluant les triplets monochromatiques de la forme $(a,b,a+b)$.

Un tel coloriage, trouvé par Geoffrey Exoo en 1994 via une recherche non exhaustive mais astucieuse par ordinateur, est donné ci-dessous. Ce coloriage est symétrique, c’est-à-dire qu’il assigne la même couleur à un entier $x$ et à son symétrique $161-x$. Il suffit donc d’exhiber les couleurs des entiers de $1$ à $80$, puisque celles des entiers de $81$ à $160$ sont automatiquement déterminées par symétrie.

\[ \begin{array}{l} \\ \hline \color{red}{1, 6, 10, 18, 21, 23, 26, 30, 34, 38, 43, 45, 50, 54, 65, 74, \dots ,151,155,160} \\ \hline \color{blue}{2, 3, 8, 14, 19, 20, 24, 25, 36, 46, 47, 51, 62, 73, \dots ,153,158,159} \\ \hline \color{green}{4, 5, 15, 16, 22, 28, 29, 39, 40, 41, 42, 48, 49, 59, \dots ,146, 156, 157} \\ \hline \color{orange}{7, 9, 11, 12, 13, 17, 27, 31, 32, 33, 35, 37, 53, 56, 57, 61, 79, \dots ,150,152,154} \\ \hline \color{brown}{44, 52, 55, 58, 60, 63, 64, 66, 67, 68, 69, 70, 71, 72, 75, 76, 77, 78, 80, \dots ,106,109,117} \\ \hline \\ \end{array} \]

  • Peut-on pousser d’un cran, c’est-à-dire trouver un coloriage similaire en $5$ couleurs des entiers de $1$ à $161$ évitant complètement les triplets monochromatiques de la forme $(a,b,a+b)$ ? On l’ignore ! Pourtant, le nombre de coloriages en $5$ couleurs des entiers de $1$ à $161$ est fini ; on devrait donc pouvoir les passer tous en revue l’un après l’autre, et vérifier si chacun d’eux exclut ce qu’il faut exclure.

Or, bien que fini, ce nombre de coloriages, à savoir $5^{161}$, est bien trop grand pour pouvoir être exploré de façon exhaustive avec les ordinateurs actuels [4]. Il faut attendre des idées nouvelles et/ou des ordinateurs radicalement plus puissants pour savoir si c’est possible. Répétons donc la question.

Question. Est-il possible de colorier les entiers de $1$ à $161$ en $5$ couleurs de façon à éviter tout triplet monochromatique de la forme $(a,b,a+b)$ ?

On l’ignore pour l’instant, mais on finira bien par le savoir, même s’il faut attendre des décennies ou des siècles pour cela.

Si la réponse — qu’elle soit obtenue par arguments théoriques ou par exploration exhaustive par ordinateur — s’avère négative, alors on aura validé la conjecture selon laquelle $S(5)=160$.

Si au contraire, la réponse s’avère positive, cela impliquera $S(5) \ge 161$. Et dans ce cas, il faudra poser la même question pour $162$, puis $163$, etc., jusqu’à tomber sur une réponse négative ; on sait juste que celle-ci arrivera avant $305$.

D’ici à connaître la valeur exacte de $S(5)$, si l’on pouvait commencer par réduire cet écart d’incertitude entre $160$ et $305$, ce serait formidable. Reste à trouver comment faire.

Que sait-on sur $S(n)$ pour $n \ge 6$ ?

Pas grand-chose, à part un encadrement de $S(n)$ entre deux bornes donné ci-dessous. Mais contrairement au cas de $S(5)$, on ne dispose d’aucune conjecture raisonnable quant à la valeur exacte de $S(6)$, et plus généralement de $S(n)$ pour tout $n \ge 6$ ; même après un siècle, on en sait encore trop peu sur ce sujet pour s’y oser.

Voici donc, légèrement simplifié [5], un encadrement de $S(n)$ démontré par Schur lui-même, et pas substantiellement amélioré depuis.

Un encadrement de $S(n)$ :
\[ \frac{3^n-1}{2} \ \le \ S(n)\ \le \ 3 \times n! -1 \]

Rappelons que le symbole $n!$ se lit « $n$ factoriel » et est défini par $n!=1 \times 2 \times \dots \times n$. Ainsi par exemple, $3!=1 \times 2 \times 3 = 6$ et $4!=24$.

L’écart entre ces deux bornes croît très vite en fonction de $n$, comme le montre ce petit tableau pour $n$ allant de $2$ à $8$ :

$\, n\, $ $\, (3^n-1)/2\, $ $\, 3 \times n! -1\, $
$2$ $4$ $5$
$3$ $13$ $17$
$4$ $40$ $71$
$5$ $121$ $359$
$6$ $364$ $2\,159$
$7$ $1\,093$ $15\,119$
$8$ $3\,280 $ $120\,959$

Par conséquent, l’incertitude concernant la valeur précise de $S(n)$ dans l’intervalle ainsi délimité croît elle aussi très vite en fonction de $n$, du moins en l’état actuel des connaissances.

Le Dernier théorème de Fermat

Le contexte de la découverte par Schur des nombres $S(n)$ vaut le détour. Il est en effet directement lié au fameux Dernier théorème de Fermat, qui au début du 20e siècle était encore une conjecture depuis quelque 250 ans.

Fermat (milieu du 17e siècle).
Etant donné un exposant $n$ supérieur ou égal à $3$, il n’existe aucun triplet d’entiers non-nuls $x,y,z$ vérifiant l’équation $x^n+y^n=z^n$.

L’énoncé correspondant pour l’exposant $n=2$ est faux, bien sûr, comme en témoigne l’égalité bien connue $3^2+4^2=5^2$.

En travaillant sur le Dernier théorème de Fermat, Dickson vers 1910 avait démontré que, pour $n \ge 3$ donné, des solutions non nulles de l’équation de Fermat $x^n+y^n=z^n$ existaient non pas en arithmétique ordinaire, mais en arithmétique modulo $p$ pour tout nombre premier $p$ suffisamment grand par rapport à $n$. Intrigué par la preuve assez compliquée de Dickson, Schur en a cherché et découvert une plus simple, entièrement nouvelle, de nature combinatoire. C’est précisément dans ce travail que sont nés les nombres de Schur $S(n)$.

Resté à l’état de conjecture phare pendant des siècles, ce n’est qu’en 1995 que le Dernier théorème de Fermat a été effectivement démontré, par Andrew Wiles, avec une contribution de Richard Taylor pour corriger un point dans une version initiale de la preuve.

La Théorie de Ramsey

Les nombres de Schur s’inscrivent dans une théorie générale appelée Théorie de Ramsey, développée vers 1930 par Frank Plumpton Ramsey (1903-1930), un jeune génie anglais hélas mort prématurément. La Théorie de Ramsey concerne la question suivante : étant donné un objet mathématique quel qu’il soit, si l’on colorie ses éléments en un nombre fini de couleurs, existera-t-il forcément un sous-objet — d’un type spécifié à l’avance — dont tous les éléments sont d’une même couleur, c’est-à dire-monochromatique ?

JPEG - 288.4 ko

Les nombres de Schur sont précisément une manifestation, avant la lettre, de ce type de problématique. Le centenaire de leur naissance a d’ailleurs été récemment célébré, en octobre 2016, lors d’un colloque à Séville dédié à la Théorie de Ramsey.

Quelques mots sur Schur

JPEG - 10.6 ko

Chez les mathématiciens, Issai Schur est connu pour bien d’autres résultats que la seule découverte des nombres $S(n)$. Une page wikipedia recense plus de 25 objets mathématiques ou théorèmes qui portent son nom, dans tous les grands domaines des maths. Comme pour tant de savants juifs d’Europe de cette période, ses contributions fondamentales ne l’ont en rien protégé de la fureur antisémite nazie, qui l’a obligé à quitter son poste de professeur à Berlin et à fuir in extremis l’Allemagne début 1939.

Issai Schur est décédé à Tel Aviv le 10 janvier 1941, jour de son 66ème anniversaire. Un colloque scientifique en sa mémoire s’est tenu en décembre 2000 au prestigieux Institut Weizmann à Rehovot, en Israël.

Post-scriptum :

L’auteur tient à remercier Bruno Martin ainsi que Bruno Duchesne, Sébastien Peronno, alainfa et Gilles Damamme pour leur relecture attentive et leurs commentaires constructifs.

Article édité par Shalom Eliahou

Notes

[1L’existence même de ces mystères révèle des lacunes profondes dans notre compréhension collective des choses mathématiques. Vouloir les percer peut avoir des conséquences bien au-delà des seuls nombres de Schur. Car, comme partout en sciences, la recherche ou la découverte de nouvelles approches pour résoudre un problème donné permet parfois des progrès inattendus dans de tout autres domaines.

[2Outre son énoncé, qu’il faut sans doute relire plusieurs fois avant d’arriver à bien le saisir. C’est du moins ce qui m’est arrivé la première fois que je l’ai rencontré...

[3En prenant bleu au lieu de rouge, ça ne change rien à l’argument, bien sûr.

[4En effet, le nombre $5^{161}$ vaut environ $3 \times 10^{112}$ et compte donc $113$ chiffres ! Avec les plus puissants ordinateurs aujourd’hui, on ne peut guère explorer plus de $10^{20}$ cas — c’est-à-dire cent milliards de milliards de cas — d’un problème donné. Et sachant que $10^{21}$ et $10^{22}$ sont respectivement $10$ fois et $100$ fois plus grands que $10^{20}$, on voit que l’exploration de $10^{113}$ cas est tout simplement impensable en l’état actuel des choses. Fort heureusement, la structure même du problème fait qu’il n’est de loin pas nécessaire de parcourir tous ces coloriages pour faire une recherche exhaustive, comme le montre le cas de deux couleurs traité plus haut. Mais malgré tout, pour cinq couleurs l’arbre des possibilités reste trop grand et rend la détermination de $S(5)$ hors d’atteinte à ce stade.

[5En particulier, le terme de droite $3 \times n!-1$ peut être remplacé par $e \times n!-1$, où $e$ est la base du logarithme népérien et vaut environ $2,718$.

Partager cet article

Pour citer cet article :

Shalom Eliahou — «Les nombres de Schur, des centenaires pleins d’avenir» — Images des Mathématiques, CNRS, 2016

Commentaire sur l'article

  • Les nombres de Schur, des centenaires pleins d’avenir

    le 21 décembre 2016 à 12:53, par projetmbc

    Un problème tout simple en apparence mais qui devient vite complexe. Cela montre peut-être une faiblesses de mathématiques. Peut-être même que ce théorème demande de sortir de l’arithmétique pour être résolu tout comme cela est le cas pour les suites de Goodstein ? Cela a-t-il déjà été envisagé ?

    Pourriez-vous aussi ajouter des références vers les méthodes informatiques envisagées et aussi vers un texte expliquant la majoration de S(5) ?

    Répondre à ce message
    • Les nombres de Schur, des centenaires pleins d’avenir

      le 22 décembre 2016 à 12:46, par Shalom Eliahou

      Bonjour,

      effectivement, comme pour d’autres instances dans la rubrique « Les Conjectures du trimestre », il s’agit d’un problème d’énoncé simple mais très difficile à résoudre.

      Je ne sais pas si cela montre une « faiblesse » des maths ; à mon avis, cela montre plutôt l’extraordinaire richesse et complexité du monde des objets mathématiques.

      Pour aborder ces problèmes liés aux coloriages des entiers naturels, l’arithmétique toute seule ne peut pas suffire en effet. Des outils issus d’autres branches, comme l’algèbre, la théorie de Fourier, la théorie ergodique et la topologie ont déjà été utilisés dans ce contexte. Il faut s’attendre à devoir faire feu de tout bois pour pouvoir avancer !

      L’article d’Exoo (1994) donnant la minoration de 160 pour S(5), ainsi que celui de Fredricksen et Sweet (2000) proposant la conjecture que S(5) pourrait bien valoir 160, se trouvent dans la revue électronique d’accès libre « The Electronic Journal of Combinatorics » [http://www.combinatorics.org]. Voici les liens spécifiques vers les fichiers PDF de ces deux articles :

      * Exoo : http://www.combinatorics.org/ojs/index.php/eljc/article/view/v1i1r8/pdf

      * Fredricksen et Sweet : http://www.combinatorics.org/ojs/index.php/eljc/article/view/v7i1r32/pdf

      Bien cordialement,

      Shalom

      Répondre à ce message
      • Les nombres de Schur, des centenaires pleins d’avenir

        le 22 décembre 2016 à 15:56, par projetmbc

        Merci pour les liens.

        PS : quand je parle de « faiblesse des maths » je sais que j’exagère un peu.

        Répondre à ce message
  • Les nombres de Schur, des centenaires pleins d’avenir

    le 2 janvier à 23:56, par Jérômé

    Bonsoir, j’aimerai savoir pour la version S(4) si il y a une coquille dans le code couleur pour la valeur 33 (bleue) et donc sa symétrie en 12 (jaune), sinon la symétrie serait parfaite comme les autres versions ?
    Merci d’avance

    Répondre à ce message
    • Les nombres de Schur, des centenaires pleins d’avenir

      le 3 janvier à 20:28, par Shalom Eliahou

      Bonsoir,

      merci pour cette excellente question, que seul votre examen particulièrement attentif de ce coloriage pour S(4) pouvait engendrer.

      Non, ce n’est pas une coquille. Comme le révèle l’ordinateur, il y a exactement 273 coloriages possibles des entiers naturels de 1 à 44 en quatre couleurs qui évitent les triplets (a,b,a+b) monochromatiques, à permutation près des couleurs bien sûr.

      Eh bien, il se trouve qu’aucun de ces 273 coloriages possibles n’est complètement symétrique ! C’est très surprenant. A ma connaissance, il n’existe aucun explication théorique à ce fait assez contre-intuitif.

      Bien cordialement,

      Shalom

      Répondre à ce message
    • Les nombres de Schur, des centenaires pleins d’avenir S(4)

      le 3 janvier à 22:00, par Jérômé

      Bonsoir,
      Pour me référer à votre article ci-dessus et être plus précis (j’ai pas dis plus clair) qu’à mon précédent commentaire posté à minuit, sous S(4), vous avez classé la valeur 33 en couleur bleue, or je pense que cela devrait être le jaune (voir votre suite de 4 valeur jaune : 9 ;10 ;11 ;12) au début des données que vous avez classifiez en jaune et seulement une suite de 3 valeur jaune à la fin, 34 ;35 ;36).
      En vérifiant la valeur 33 et en la remplaçant par la couleur jaune, nous résolvons cette coquille (si il y a ;-) ) et respectons la symétrie que vous mentionnez notamment pour réduire les recherches sur S(5) et qui se vérifiait jusqu’alors pour S(2) & S(3).

      Valeur 15 & 30 - symétrie et l’addition

      Par contre, et toujours dans un soucis de symétrie, la valeur 15 et 30 me pose un réel soucis et reste les deux seul valeur sur les 44 pour lesquels (a,b, a+b) oblige au changement de couleur, ici en l’occurrence (a+a), or ils sont placé de manière symétrique ?

      Merci de bien vouloir m’éclairer, peut-être qu’il y a une exception pour l’addition d’une même valeur ?

      Cordialement,

      Répondre à ce message
  • Les nombres de Schur, des centenaires pleins d’avenir

    le 3 janvier à 22:12, par Jérômé

    Pardon Shalom de vous ennuyer, mais je n’ai reçu la réponse de votre poste qu’après ma rédaction précédente.

    Si vous le permettez et pour vous répondre, en remplaçant la couleur bleue de la valeur 33 par du jaune le calcul reste effectif en respectant (a,b, a+b) et la symétrie est quasi parfaite à l’exception du 15 et du 30, comme je vous l’ai mentionné avant et que votre réponse « m’attriste » car je misait sur cette symétrie en me référant non pas au calcul a+b mais à une logique des couleurs.
    En effet, vous parlez pour S(5) de réduire les recherches 5^161 à 5^81, or avec ce que vous venez de me dire pour S(4), qu’est-ce qui vous fait penser à une symétrie pour S(5) ?

    Merci pour le partage de votre savoir et excusez-moi du dérangement !

    Répondre à ce message
    • Les nombres de Schur, des centenaires pleins d’avenir

      le 4 janvier à 13:28, par Shalom Eliahou

      Bonjour,

      vous avez parfaitement raison. En assignant à 33 le jaune plutôt que le bleu, on obtient un coloriage symétrique, sauf pour 15 et 30 qui ne pourront jamais avoir la même couleur dans un coloriage symétrique puisque 30 = 2 x 15 comme vous le relevez, et que les triplets (a,a,2a) monochromatiques sont interdits.

      Ces deux coloriages, celui de l’article et celui que vous proposez obtenu en déplaçant 33 vers le jaune, sont 2 parmi les 273 coloriages possibles. Le votre est plus élégant car quasi symétrique, j’en conviens volontiers.

      Dans mon message d’hier, désolé, j’avais oublié ce point mentionné par Fredricksen et Sweet en l’an 2000 et que vous avez redécouvert : si N+1 est divisible par 3, alors il est impossible d’assigner la même couleur aux deux nombres (N+1)/3 et à son double 2 x (N+1)/3, bien que ces deux nombres soient symétriques l’un de l’autre par rapport à N+1.

      Dans le cas présent, pour S(4), on rencontre bien cette obstruction puisque 44+1 est divisible par 3, les deux nombres concernés étant alors 15 et 30 comme vous le relevez.

      Par contre, cette obstruction arithmétique à la symétrie est la seule connue à ce jour. Et comme les cas de S(2), S(3), S(4) et S(5) le montrent, on peut raisonnablement penser qu’on pourra toujours obtenir un coloriage optimal symétrique mis à part cette exception de (N+1)/3 et son double.

      Merci encore pour votre intérêt et vos remarques extrêmement pertinentes !

      Bien cordialement,

      Shalom

      Répondre à ce message
      • Les nombres de Schur, des centenaires pleins d’avenir

        le 5 janvier à 11:41, par Jérômé

        Bonjour Shalom et merci d’avoir pris de votre temps pour me répondre.

        Pour vous expliquer mon résonnement qui a dû être vu et revu par bien d’autres, je pensais trouver un code couleur de base pour chacun des S(N) connu, afin d’y trouver une corrélation possible pour résoudre, non pas d’un point de vu calcul étant donné les restrictions des possibilités informatiques pour S(5) ou pire S(6)) comme vous l’avez mentionné, mais d’un point de vue logique basée sur l’arrangement des couleurs.
        En effet, pour S(4) il y a 273 possibilités, aussi pour trouver une première corrélation entre chacun des S(N), il faut partir par un code couleur de base identique (1= ROUGE ; 2= Bleu ; etc...) et, le plus important, choisir ensuite le code couleur permettant la symétrie par ce même code couleur, ce qui réduirait l’analyse à son strict minimum, à savoir les possibilités de S(x) / S(x) and so on...
        Une fois cette corrélation établie (laissez le prétentieux qui est en moi y songer ;-) ), on y trouverait peut-être une logique pour devinez le remplissage des couleurs des S(N) suivants sans même passer par la formule (a,b, a+b) mais qui naturellement se vérifierait.
        Pour ne pas abandonner totalement cette idée, mon unique soucis reste la notion de (a,a, 2a) pour laquelle vous m’avez écrit que les triplets monochromatiques sont interdits. Ne souhaitant pas changer les règles pour arriver à mon résultat (facile n’est-ce pas) mais simplement pour comprendre parfaitement cet énoncé, je n’ai pas trouvé dans l’énoncé de Schur cette règle, mais seulement (a,b, a+b). Aussi, ne réfléchissant que par ma propre et pauvre logique pour le profane en mathématique que je suis, pour moi (a,a, 2a) # (a,b, a+b), à moins qu’une loi mathématique vienne valider cette différence (c’est là que j’ai besoin de votre savoir) ou que Schur lui-même l’ait écrit d’une manière qui n’a pas été assez vulgarisée pour que je puisse la comprendre ?
        Pour finir et vous donner un exemple plus lisible, prenons la valeur 2 dans S(2). La couleur de 2 ne dépend pas forcément du double de 1 (1,1, 2), mais surtout de son implication avec les autres possibilités à respecter strictement (a,b, a+b) :

        « 
        1 2 3 4
        1 2 3 4
        1 2 3 4
        1 2 3 4
         »

        Je n’ai pas eu encore le temps de vérifier si pour S(4) et en respectant strictement la règle (a,b, a+b) si nous pouvions aspirer à une symétrie parfaite, mais j’y ai bon espoir ! ;-)

        Dans tous les cas, merci encore pour le partage de votre savoir.
        Bonne journée
        Jérômé

        Répondre à ce message
        • Les nombres de Schur, des centenaires pleins d’avenir

          le 5 janvier à 13:16, par Shalom Eliahou

          Bonjour Jéromé,

          la contrainte de Schur est d’exclure tous les triplets monochromatiques de la forme (a,b,a+b) sans aucune restriction sur les nombres a,b. Donc le cas a=b est permis ; ce qui, en particulier, exclut les triplets monochromatiques de la forme (a,a,a+a), c’est-à-dire (a,a,2a).

          Un problème analogue, lui aussi objet de recherches intensives, consiste a exclure seulement les triplets monochromatiques de la forme (a,b,a+b) avec a,b différents. Dans ce nouveau contexte, les triplets monochromatiques de la forme (a,a,2a) ne sont plus exclus du tout. Pour deux couleurs, on peut alors aller jusqu’à 8 :

          bleu : 1,2,4,8
          rouge : 3,5,6,7

          Et 8 est maximal, il est impossible de caser 9 en plus. On exprime cela en écrivant WS(2) = 8, où WS(n) signifie Weak Schur number, c’est-à-dire nombre de Schur faible. On sait que WS(3)=23, que WS(4)=66, et on conjecture que WS(5)=196. Ces nombres WS(n) sont tout aussi mystérieux que les S(n).

          C’est une excellente idée que de vouloir chercher une logique pour passer de S(n) à S(n+1). ces dernières décennies, d’autres s’y sont également essayés, sans grand succès à ce jour. Mais cela ne signifie pas qu’il n’y a pas une logique subtile à l’oeuvre et qui reste à découvrir. Il faut certainement poursuivre l’effort de recherche. L’idée de se restreindre au cas symétrique, ou quasi symétrique si n+1 est divisible par 3, reste la voie la plus prometteuse à ce jour.

          Bien cordialement,

          Shalom

          Répondre à ce message
          • Les nombres de Schur, des centenaires pleins d’avenir

            le 5 janvier à 13:21, par Shalom Eliahou

            Petit coquille tout à la fin : je voulais dire « quasi symétrique si N+1 est divisible par 3, où N = S(n), reste... »

            Répondre à ce message
          • Les nombres de Schur, des centenaires pleins d’avenir

            le 5 janvier à 23:20, par Jérômé

            Bonsoir Shalom,

            Merci pour toutes ses explications, je vais m’atteler à coder (en VBA) pour me permettre d’analyser tout ça sous mon tableur Excel qui m’a déjà permis d’un simple regard de vous faire part de mes remarques précédentes. Par exemple, sans connaître vos dernières remarques concernant les weak Schur numbers (étant donné que j’ai pris conscience de Schur à ce nouvel an (shame on me ;-) ), j’avais deviné que si nous ne tenions pas compte de (a,a, 2a) , WS(n) serait différent est > à S(n).
            Je vais donc continuer sur cette voie et il est bon de marcher dans les traces de pas d’autres personnes bien plus brillantes, donc à moi d’essayer de les quitter à temps pour des sentiers neigeux encore vierge.
            Je vous remercie vraiment d’avoir pris de votre temps pour partager votre savoir et je vous dis à bientôt.

            Respectueusement,
            Jérômé

            Répondre à ce message
            • Les nombres de Schur, des centenaires pleins d’avenir

              le 6 janvier à 17:21, par Shalom Eliahou

              Bonjour Jérômé,

              à moi de vous remercier pour votre intérêt et vous encourager à poursuivre votre exploration de ce sujet fascinant et sur lequel il reste tant à découvrir. A bientôt j’espère !

              Très cordialement,
              Shalom

              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é ?

Suivre IDM