Problème des triplets booléens de Pythagore
Le problème des triplets booléens de Pythagore est un problème de la théorie de Ramsey qui consiste à savoir si les entiers positifs peuvent être colorés en rouge et en bleu de sorte qu'aucun triplet de Pythagore ne se compose de tous les membres rouges ou bleus. Le problème des triplets booléens de Pythagore a été résolu par Marijn Heule, Oliver Kullmann et Victor W. Marek en mai 2016 grâce à une preuve assistée par ordinateur[1].
Énoncé
modifierLe problème consiste à savoir s'il est possible de colorier chacun des entiers positifs en rouge ou en bleu, de sorte qu'aucun triplet de Pythagore d'entiers a, b, c, satisfaisant soient tous de la même couleur.
Par exemple, dans le triplet de Pythagore 3, 4 et 5 ( ), si 3 et 4 sont colorés en rouge, alors 5 doit être coloré en bleu.
Solution
modifierMarijn Heule, Oliver Kullmann et Victor W. Marek ont montré qu'une telle coloration n'est possible que jusqu'au nombre 7824. L'énoncé réel du théorème prouvé est
Théorème — L'ensemble {1, . . . , 7824} peut être partitionné en deux sous-ensembles de sorte qu'aucun des sous-ensembles n'inclut un triplet de Pythagore. Cela est impossible pour {1, . . . , 7825}[2].
Il existe 27825 ≈ 3.63×102355 combinaisons de couleurs possibles pour les nombres jusqu'à 7825 . Ces colorations possibles ont été logiquement et algorithmiquement réduites à environ un billion de cas (toujours très complexes), et celles-ci ont été examinées à l'aide d'un solveur booléen de satisfiabilité. La création de la preuve a nécessité environ 4 années CPU de calcul sur une période de deux jours sur le supercalculateur Stampede du Texas Advanced Computing Center et a généré une preuve propositionnelle de 200 téraoctets, qui a été compressée à 68 gigaoctets.
L'article décrivant la preuve a été publié lors de la conférence SAT 2016[2], où il a remporté le prix du meilleur article[3]. La figure ci-dessous montre une famille possible de colorations pour l'ensemble {1,...,7824} sans triplet de Pythagore monochromatique, et les carrés blancs peuvent être colorés en rouge ou en bleu tout en satisfaisant à cette condition.
Prix
modifierDans les années 1980 , Ronald Graham a offert un prix de 100 $ pour la solution du problème, qui a maintenant été décerné à Marijn Heule[1].
Généralisations
modifierDepuis 2018, le problème est toujours ouvert pour plus de 2 couleurs, c'est-à-dire s'il existe une k-coloration ( k ≥ 3) des entiers positifs telle qu'aucun triplet de Pythagore n'est de la même couleur[4].
Articles connexes
modifierRéférences
modifier- (en) Evelyn Lamb, « Two-hundred-terabyte maths proof is largest ever », Nature, vol. 534, no 7605, , p. 17-18 (PMID 27251254, DOI 10.1038/nature.2016.19990, Bibcode 2016Natur.534...17L).
- Marijn J. H. Heule, Oliver Kullmann et Victor W. Marek « Theory and Applications of Satisfiability Testing – SAT 2016: 19th International Conference, Bordeaux, France, July 5-8, 2016, Proceedings » () (DOI 10.1007/978-3-319-40970-2_15, arXiv 1605.00723)
- SAT 2016
- (en) Eliahou, Fromentin, Marion-Poty et Robilliard, « Are Monochromatic Pythagorean Triples Unavoidable under Morphic Colorings? », Experimental Mathematics, vol. 27, no 4, , p. 419–425 (ISSN 1058-6458, DOI 10.1080/10586458.2017.1306465, arXiv 1605.00859, S2CID 19035265, lire en ligne)
