Rediffusion d’un article publié publié le 21 décembre 2016

Les nombres de Schur, des centenaires pleins d’avenir

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

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

Rediffusion d’un article publié publié le 21 décembre 2016.

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.

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

Voir tous les messages - Retourner à l'article

  • Les nombres de Schur, des centenaires pleins d’avenir S(4)

    le 3 janvier 2017 à 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

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