LE PLUS GRAND MONTANT IMPOSSIBLE À PAYER, ENFIN PLAFONNÉ AU PLUS JUSTE

Imaginez une caisse qui n’accepte que quelques sortes de pièces, en quantité illimitée, et qui ne rend jamais la monnaie. Certains montants se paient exactement ; d’autres, jamais. Les mathématiciens appellent les valeurs des pièces des générateurs, et posent une question d’apparence toute simple : quel est le plus grand montant impossible à payer ?

Des montants qu’on ne peut jamais payer

Prenons des nombres entiers a₁ < a₂ < … < aₙ sans facteur commun à tous. Un total obtenu en additionnant ces nombres, chacun autant de fois qu’on veut, est dit « représentable ». Seul un nombre fini d’entiers ne le sont pas ; le plus grand d’entre eux est le nombre de Frobenius, F. (Si l’une des valeurs vaut 1, tout se paie, et l’on pose F = −1.)

Un petit exemple : avec des pièces de 3, 4 et 6, on peut payer 3, 4, 6, 7, 8 et tous les montants suivants, mais jamais 1, 2 ni 5. Donc F = 5. Notez que 3 et 6 ont un facteur commun ; ce qui compte, c’est qu’aucun facteur ne soit commun aux trois.

Pour deux pièces, il existe une réponse exacte, la formule de Sylvester : F(a₁, a₂) = a₁a₂ − a₁ − a₂. À partir de trois, le travail consiste à borner F : démontrer qu’il ne peut pas dépasser une certaine valeur calculée à partir des pièces.

Un facteur 2 tenace

Paul Erdős et Ronald Graham ont démontré, pour trois générateurs ou plus :

F ≤ 2aₙ₋₁⌊aₙ/n⌋ − aₙ

Ici aₙ est la plus grande valeur, aₙ₋₁ la deuxième plus grande, n le nombre de valeurs, et ⌊ ⌋ signifie qu’on arrondit à l’entier inférieur. Comme la formule de Sylvester, cette borne fait intervenir les deux plus grosses pièces.

Ils ont aussi estimé le pire cas, le plus grand F possible quand les n valeurs sont toutes au plus égales à t. L’écart entre leurs estimations, environ un facteur 2, a conduit à une conjecture répertoriée comme le problème d’Erdős n° 433. Jacques Dixmier l’a résolue, et a aussi démontré une borne plus simple, valable pour tout ensemble : F ≤ aₙ²/(n − 1). Le facteur 2 a disparu, mais la deuxième plus grosse pièce aussi.

Garder les deux plus grosses pièces

Lin Chen, Tingwei Hu, Yuchen Mao et Guochuan Zhang, du College of Computer Science and Technology de l’université du Zhejiang, voulaient les deux : pas de facteur 2, et la deuxième plus grosse pièce conservée. Leur réponse, valable pour tout ensemble de deux valeurs ou plus :

F ≤ aₙ₋₁⌈aₙ/(n − 1)⌉ − aₙ − 1

Ici ⌈ ⌉ signifie qu’on arrondit à l’entier supérieur. Par rapport à Erdős et Graham, le facteur 2 a disparu, au prix d’une division par n − 1 au lieu de n et d’un arrondi vers le haut. Par rapport à Dixmier, la nouvelle borne peut être nettement plus petite quand la deuxième plus grosse pièce est petite à côté de la plus grosse.

Sur l’exemple 3, 4, 6, la borne d’Erdős et Graham donne 10, celle de Dixmier 18, et la nouvelle 4 × 3 − 6 − 1 = 5, exactement la vraie valeur. Rien d’étonnant : cet ensemble appartient à la famille de cas extrêmes décrite plus bas, construite pour atteindre exactement la borne ; l’article ne donne aucune comparaison sur des ensembles typiques.

Trier les montants par leur reste

La démonstration suit la voie d’Erdős et Graham. On range chaque montant selon son reste dans la division par la plus grosse pièce, aₙ. Dès qu’une somme des pièces plus petites atteint un reste donné, ajouter des exemplaires de aₙ permet d’atteindre tous les montants plus grands ayant ce reste. Il s’agit donc de montrer que chaque reste peut être atteint à peu de frais.

L’outil clé est le théorème de Kneser, sur la taille minimale d’un ensemble de sommes. Erdős et Graham s’en servaient pour montrer que les sommes d’environ aₙ/n pièces couvrent plus de la moitié des restes, puis doublaient la mise pour les couvrir tous. Chaque pièce de ces sommes vaut au plus aₙ₋₁ ; doubler le nombre de pièces double donc le coût : d’où le facteur 2.

La nouvelle démonstration utilise des sommes de ⌈aₙ/(n − 1)⌉ pièces. Quand ces sommes manquent certains restes, le théorème de Kneser dit que les restes manquants ne sont pas éparpillés au hasard : ils forment des familles entières, espacées régulièrement. Plus il manque de familles, plus les petites pièces doivent s’entasser dans chaque famille atteinte ; chacune contient donc de petites pièces, et les quelques pièces supplémentaires qu’il faut pour atteindre les familles manquantes coûtent peu. Le total ne dépasse jamais ⌈aₙ/(n − 1)⌉ × aₙ₋₁.

Cette première étape donne la borne sans son « − 1 » final. La dernière unité vient d’un argument distinct, fondé sur un théorème de Scherk et Kemperman à propos des sommes qui ne peuvent s’obtenir que d’une seule façon : il montre que le montant limite aₙ₋₁⌈aₙ/(n − 1)⌉ − aₙ peut lui-même toujours être payé. D’après les remerciements, les auteurs ont d’abord démontré la borne plus faible ; GPT-6 a ensuite aidé à trouver l’argument qui l’abaisse d’une unité, et a aussi contribué à la preuve que la borne ne peut pas être abaissée, ainsi qu’à la correction de l’anglais. Les auteurs déclarent assumer la responsabilité du manuscrit final.

Des cas qui touchent exactement la limite

Cette borne ne peut pas être abaissée : pour tout n ≥ 3, les auteurs construisent une infinité d’ensembles où F lui est exactement égal. Prenez n’importe quel q ≥ 2 et les valeurs q, 2q, …, (n − 1)q, plus (n − 2)q + 1. Toutes sauf une sont des multiples de q : elles ne paient rien que q seul ne puisse payer. L’ensemble se comporte comme deux pièces, q et (n − 2)q + 1, et la formule de Sylvester donne un F qui coïncide exactement avec la nouvelle borne. Avec n = 3 et q = 3, cette recette donne précisément l’exemple 3, 4, 6 ci-dessus.

Moins de pièces, un plafond plus bas

La borne se lit aussi en termes de densité. Elle s’applique à tout ensemble réduit formé des i plus petites valeurs et de la plus grande, tant que celles-ci n’ont toujours pas de facteur commun. Retirer des pièces ne peut que rendre le paiement plus difficile : un plafond démontré pour le jeu réduit vaut donc aussi pour le jeu complet. Ce qui gouverne le résultat est à peu près aᵢ/i, l’inverse de la densité avec laquelle les i premières valeurs remplissent les nombres de 1 à aᵢ : le groupe le plus dense l’emporte. En particulier, notent les auteurs, la deuxième plus grosse pièce peut tout simplement être mise de côté chaque fois que les pièces restantes n’ont toujours aucun facteur commun à toutes.

L’article reste purement théorique : il ne chiffre pas de combien la nouvelle borne est plus petite sur des jeux de pièces typiques, et son optimalité n’est démontrée qu’à partir de trois valeurs de pièces.