Problème de Prouhet-Tarry-Escott

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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 n, deux ensembles A et B de n entiers chacun, tel que :

\sum_{a\in A} a^i = \sum_{b\in B} b^i

pour chaque i de 1 jusqu'à un entier k donné[1]. Si A et B vérifient ces conditions, on écrit A=_k B.

On cherche une solution de taille n minimale pour un degré k donné. Ce problème, toujours ouvert, est nommé d'après 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 k pour laquelle on connaît une solution avec n=k+1 est k=11. C'est la solution est donnée par les ensembles suivants[2] :

A=\{\pm22, \pm61, \pm86,\pm127,\pm140,\pm151\}\ ,
 \qquad     B=\{\pm35, \pm47, \pm94,\pm121,\pm146,\pm148\}

Exemple[modifier | modifier le code]

L'entier k de la définition est le degré, et l'entier n est la taille. Il est facile de voir que pour toute solution, on a n>k. On cherche donc une solution de taille minimale.

Pour la taille n=6 et le degré k=5, les deux ensembles

\{0, 5, 6, 16, 17, 22\} et \{1, 2, 10, 12, 20, 21\}

sont une solution du problème, puisque:

0+5+6+16+17+22=66=1+2+10+12+20+21
0^2+5^2+6^2+16^2+17^2+22^2=1090=1^2+2^2+10^2+12^2+20^2+21^2
0^3+5^3+6^3+16^3+17^3+22^3=19998=1^3+2^3+10^3+12^3+20^3+21^3
0^4+5^4+6^4+16^4+17^4+22^4=385234=1^4+2^4+10^4+12^4+20^4+21^4
0^5+5^5+6^5+16^5+17^5+22^5=7632966=1^5+2^5+10^5+12^5+20^5+21^5.

Une solution idéale est une solution dont la taille est égale au degré + 1. Les deux solutions ci-dessus sont idéales.

Histoire[modifier | modifier le code]

En 1851, Eugène Prouhet pose le problème plus général de répartir les entiers x de 1 à n^m en n classes, de façon que la somme des puissances k-èmes des entiers de chaque classe soit la même, pour k = 0, 1, ... Le procédé qu'il propose[3] 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, dans son Histoire de la théorie des nombres, consacre le chapitre XXIV du deuxième volume aux Sets of integers with equal sums of like powers[4], et liste pas moins de 70 articles sur ce sujet. Dans son article historique[5], 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[6],[7],[8]. Une version en deux dimensions a été étudié par Alpers et Tijdeman (2007).

Propriétés et résultats[modifier | modifier le code]

1. Si le couple A=\{a_1,a_2,\ldots,a_n\} et B=\{b_1,b_2,\ldots,b_n\} est une solution de degré k, alors pour tout N\ne0 et tout M le couple A'=\{Na_1+M,Na_2+M,\ldots,Na_n+M\} et B'=\{Nb_1+M,Nb_2+M,\ldots,Nb_n+M\} est encore une solution du même degré. Ainsi, la solution

\{0, 5, 6, 16, 17, 22\}=_5\{1, 2, 10, 12, 20, 21\}

donne aussi la solution

\{1, 6, 7, 17, 18, 23\}=_5\{2, 3, 11, 13, 21, 22\}

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

2. On ne connaît pas de solution idéale pour tout degré, mais on sait[6] que pour tout degré k, il existe une solution de taille n\le k(k+1)/2 +1.

3. Solutions symétriques : une solution de taille paire n=2m est symétrique si chaque composante est de la forme

\{\pm c_1,\pm c_2,\ldots,\pm c_m\}.

La solution donnée dans l'introduction est de cette forme.

4. Une solution de taille impaire est symétrique si les composantes de la solution sont opposées, c'est-à-dire

A=\{a_1,a_2,\ldots,a_n\} et B=\{-a_1,-a_2,\ldots,-a_n\}.

Solutions idéales et symétriques[modifier | modifier le code]

Des solutions idéales et symétriques sont connues pour les degrés k\le11, sauf pour k=10[9] :

  • k=1
\{\pm2\}=_1\{\pm1\}
  • k=2
\{-2,-1,3\}=_2\{2,1,-3\}
  • k=3
\{\pm3,\pm11\}=_3\{\pm7,\pm9\}
  • k=4
\{-8,-7,1,5,9\}=_4\{8,7,-1,-5,-9\}
  • k=5
\{\pm4,\pm9,\pm13\}=_5\{\pm1,\pm11,\pm12\}
  • k=6
\{-51,-33,-24,7,13,38,50\}=_6\{51,33,24,-7,-13,-38,-50\}
  • k=7
\{\pm2,\pm16,\pm21,\pm25\}=_7\{\pm5,\pm14,\pm23,\pm24\}
  • k=8
\{-98,-82,-58,-34,13,16,69,75,99\}=_8\{98,82,58,34,-13,-16,-69,-75,-99\}
  • k=9
\{\pm99,\pm100,\pm188,\pm301,\pm313\}=_9\{\pm71,\pm131,\pm180,\pm307,\pm308\}

Cette dernière solution est donnée, avec d'autres, dans Borwein et al. (2003). Aucune solution idéale n'est connue pour k=10.

Une formulation algébrique[modifier | modifier le code]

Il existe une façon plus algébrique de formuler le problème[10] :

Proposition —  Les conditions suivantes sont équivalentes:

  1. \sum_{i=1}^n a_i^j=\sum_{i=1}^n b_i^j,\quad (j=1,\ldots,k)
  2. \deg\left(\prod_{i=1}^n(x-a_i)-\prod_{i=1}^n(x-b_i)\right)\le n-(k+1)
  3. (x-1)^{k+1}\left| \sum_{i=1}^n x^{a_i}-\sum_{i=1}^n x^{b_i}\right.

Notes et références[modifier | modifier le code]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Prouhet–Tarry–Escott problem » (voir la liste des auteurs)

Notes[modifier | modifier le code]

  1. Borwein (2002), p. 85
  2. Solution donnée par Nuutti Kuosa, Jean-Charles Meyrignac et Chen Shuwen, en 1999, voir The Prouhet-Tarry-Escott problem.
  3. M. E. Prouhet, Mémoire sur quelques relations entre les puissances des nombres, C. R. Acad. Sci. Paris, série I, 33, (1851), 225
  4. Leonard Eugene Dickson, Histoire de la théorie des nombres, t.II, (1919) ch.XXIV, p.705, Sets of integers with equal sums of like powers
  5. Wright (1959)
  6. a et b Borwein et Ingalls (1944)
  7. Borwein (2002)
  8. Borwein, Lisonĕk et Percival 2003
  9. Borwein (2002) et The Prouhet-Tarry-Escott problem.
  10. Voir Borwein et Ingalls (1944) pour des références.

Références[modifier | modifier le code]

  • (en) Leonard Eugene Dickson, The History of the Theory of Numbers, Carnegie Institution of Washington,‎ 1919-1923 (lire en ligne)
  • (de) Albert Gloden, Mehrgradige Gleichungen : Mit einem Vorwort von Maurice Kraitchik, Groningen, P. Noordhoff,‎ 1944, lien Math Reviews
  • (en) G. H. Hardy et E. M. Wright, An Introduction to the Theory of Numbers [détail des éditions]
    Les sections 20.5 "The four-square theorem" et 21.9 "The problem of Prouhet and Tarry: The number P(k,j)" traitent de ce sujet
  • (en) Edward M. Wright, « Prouhet's 1851 solution of the Tarry-Escott problem of 1910 », Amer. Math. Monthly, vol. 66,‎ mars 1959, p. 199-201
  • (en) Peter Borwein et Colin Ingalls, « The Prouhet-Tarry-Escott problem revisited », Enseign. Math., vol. 40, no 1-2,‎ 1994, p. 3–27 (lire en ligne)
  • (en) Peter Borwein, Computational Excursions in Analysis and Number Theory, Springer, coll. « CMS Books in Mathematics »,‎ 2002 (ISBN 0-387-95444-9, lire en ligne)
    Le chapitre 11: The Prouhet–Tarry–Escott problem (pages 85–96) est consacré au problème
  • (en) Peter Borwein, Petr Lisonĕk et Colin Percival, « Computational investigations of the Prouhet-Tarry-Escott problem », Mathematics of Computation, vol. 72, no 244,‎ 2003, p. 2063-2070 (lire en ligne)
  • (en) Andreas Alpers et Robert Tijdeman (de), « The two-dimensional Prouhet-Tarry-Escott problem », J. Num. Th. (en), vol. 123,‎ 2007, p. 403-412

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Liens externes[modifier | modifier le code]