537 NOMBRES, SIX COULEURS, AUCUNE SOMME

Voici un casse-tête qu’un enfant peut comprendre. Prenez les nombres 1, 2, 3, et ainsi de suite. Donnez une couleur à chacun. Seule règle : dans une même couleur, on ne doit jamais trouver deux nombres en même temps que leur somme. Les deux nombres peuvent même être identiques : si 2 est rouge, alors 4 ne peut pas être rouge, puisque 2 + 2 = 4.

Un ensemble sans un tel trio est dit sans somme. Jusqu’où peut-on aller avant que la règle ne force l’arrêt ? Cette limite, pour k couleurs, est le nombre de Schur S(k). Le problème remonte à un article de 1916 d’I. Schur, en tête de la liste des références.

Une suite réputée coriace

Avec une seule couleur, on est bloqué tout de suite : 1 + 1 = 2, donc la couleur ne peut contenir que le nombre 1. Les valeurs connues sont :

• S(1) = 1
• S(2) = 4
• S(3) = 13
• S(4) = 44
• S(5) = 160, déterminé par M. J. H. Heule (dans un article publié en 2018).

Pour six couleurs, personne ne connaît la réponse. Depuis 2000, la meilleure construction connue, trouvée par H. Fredricksen et M. M. Sweet en cherchant parmi les colorations symétriques, atteignait 536. Ce nombre est cité depuis comme la meilleure borne inférieure — un plancher : S(6) vaut au moins cela, et sa vraie valeur, encore inconnue, pourrait être plus grande.

Un nombre de plus

Zhiyang Chen et Fan Long, de l’université de Toronto, et Ligeng Zhu, de NVIDIA Research, la portent à 537. Leur preuve est du genre que les mathématiciens adorent pour sa franchise : ils impriment la réponse. Six listes de nombres — 76, 76, 88, 70, 76 et 151 — qui contiennent ensemble chaque entier de 1 à 537 exactement une fois, sans qu’aucune couleur contienne x, y et x + y. La vérifier, c’est tester toutes les sommes dans chaque liste : un travail rapide pour un ordinateur.

La solution a une forme frappante. Elle est symétrique : chaque nombre x a la même couleur que 538 − x. Les quatre premières couleurs commencent à 1, 2, 3 et 4 ; la cinquième n’apparaît qu’à partir de 38, la sixième qu’à partir de 151, et cette sixième couleur remplit tout le milieu, de 237 à 301. Même la première couleur peut être reconstruite à partir d’une graine de 14 petits nombres, par des symétries miroir, un décalage et un nombre ajouté, 95.

Des répercussions plus haut

Les nombres de Schur s’alimentent les uns les autres. Des recettes connues transforment une bonne coloration à k couleurs en une coloration à k + 2 ou k + 5 couleurs : S(k + 2) vaut au moins 10 S(k) + 2, et S(k + 5) au moins 380 S(k) + 148. Le nouveau 537 relève donc d’autres records :

• huit couleurs : de 5 362 à 5 372 — et l’équipe a aussi construit cette coloration explicitement ;
• onze couleurs : de 203 828 à 204 208 ;
• treize couleurs : de 2 038 282 à 2 042 082.

Il améliore aussi un nombre de Ramsey, R₆(3) : le plus petit nombre de points, tous reliés deux à deux, pour lequel toute coloration des liens en six couleurs contient forcément un triangle d’une seule couleur. Numérotez 538 points de 0 à 537 et coloriez le lien entre i et j de la couleur de leur différence |i − j| : la coloration sans somme ne laisse aucun triangle d’une seule couleur. R₆(3) vaut donc au moins 539, contre 538 avant.

131 façons de faire

La recherche n’a pas trouvé une solution mais 131 réellement différentes, que les auteurs classent en cinq familles et publient en entier. La plupart restent très proches de la première : celles des familles F1 à F4 coïncident avec elle sur au moins 462 des 537 positions. Une famille brise la symétrie miroir ; une autre est construite en mélangeant trois copies brouillées de l’original.

L’article n’explique pas comment la recherche elle-même a été menée. Les auteurs soulignent que leurs 131 colorations ne forment pas un catalogue complet des solutions à six couleurs, seulement de nouveaux points de départ pour qui voudra tenter 538.