En mathématiques, et plus particulièrement en théorie des nombres et en combinatoire, le problème de Prouhet-Tarry-Escott est de trouver, pour chaque entier , deux ensembles et de entiers relatifs chacun, les entiers étant tous distincts, tel que :
pour chaque de jusqu'à un entier donné. Si et vérifient ces conditions, on écrit .
On cherche une solution de taille minimale pour un degré donné. Ce problème, toujours ouvert, est nommé en référence à Eugène Prouhet, qui l'a étudié en 1851, et Gaston Tarry et Edward Brind Escott, qui l'ont considéré au début des années 1910.
La plus grande valeur de pour laquelle on connaît une solution avec est . Une solution correspondante est donnée par les ensembles suivantsSolution donnée par Nuutti Kuosa, Jean-Charles Meyrignac et Chen Shuwen, en 1999, voir The Prouhet-Tarry-Escott problem. :
Propriété et exemple L'entier de la définition est le degré, et l'entier est la taille. On démontre que pour toute solution, on a .
Si on avait , considérons les polynômes de degré : et dont les racines sont respectivement les éléments de et ; les relations impliquent que les premières sommes de Newton des racines de et sont égales, donc que les polynômes symétriques élémentaires en les racines de et sont égales, et que donc , d'où ce qui est contraire aux hypothèses.
Pour le degré il existe une solution de taille donnée par les ensembles :
et
En effet :
.
Une solution idéale est une solution dont la taille est égale au degré + 1. La solution ci-dessus est donc idéale.
Histoire En 1851, Eugène Prouhet pose le problème plus général de répartir les entiers x de 1 à n en n classes, de façon que la somme des puissances k-ièmes des entiers de chaque classe soit la même, pour k = 0, 1, ... Le procédé qu'il proposeM. E. Prouhet, Mémoire sur quelques relations entre les puissances des nombres, C. R. Acad. Sci. Paris, série I, vol. 33, 1851, . revient à numéroter les classes de 0 à n – 1, à décomposer chaque entier x – 1 dans la base de numération n, à faire la somme de ses chiffres, à calculer le reste r de cette somme modulo n et à affecter l'entier x à la classe r.
Dans le cas où n = 2, le placement de l'entier x dans l'une des deux classes d'indice 0 ou 1 se fait selon que le x-ème terme de la suite de Prouhet-Thue-Morse est 0 ou 1. Par exemple, les 8 premiers entiers sont répartis en : 1, 4, 6, 7 d'une part, et en 2, 3, 5, 8 d'autre part, et la somme des puissances k-ème des entiers de ces deux classes coïncide jusqu'à k = 2.
Leonard Eugene Dickson consacre un chapitre de son Histoire de la théorie des nombres aux , vol. 2, 1919, chap. XXIV, ., et liste pas moins de 70 articles sur ce sujet. Dans son article historique, Edward Maitland Wright note que l'article de Prouhet n'a été redécouvert qu'en 1948.
Les récents développements sont décrits par Peter Borwein et ses coauteurs ; voir aussi l'article de Filaseta et Markovich.. Une version en deux dimensions a été étudiée par .
Propriétés et résultats
Si le couple formé par et est une solution de degré , alors pour tout et tout le couple formé parest encore une solution du même degré. Ainsi, la solutiondonne aussi la solutionCette observation permet de normaliser les solutions, en imposant par exemple qu'elles ne contiennent que des entiers positifs ou nuls, et que zéro y figure. On ne connaît pas de solution idéale (de taille le degré +1) pour tout degré, mais on sait que pour tout degré , il existe une solution de taille . Solutions symétriques : une solution de taille paire est symétrique si chaque composante est de la formeLa solution donnée dans l'introduction est de cette forme. Une solution de taille impaire est symétrique si les composantes de la solution sont opposées, c'est-à-dire
Solutions idéales et symétriques Des solutions idéales et symétriques sont connues pour les degrés , sauf pour et The Prouhet-Tarry-Escott problem. :
Cette dernière solution est donnée, avec d'autres, dans . Aucune solution idéale n'est connue pour . Une formulation algébrique Il existe une façon plus algébrique de formuler le problèmeVoir pour des références. :
Notes et références
Notes
Références
Voir aussi Articles connexes Suite de Prouhet-Thue-Morse Conjecture d'Euler Théorème d'Erdős-Suranyi
Liens externes Chen Shuwen, The Prouhet-Tarry-Escott problem
Catégorie:Théorie des nombres Catégorie:Problème non résolu en mathématiques