problème de Prouhet-Tarry-Escott

Prenez deux groupes de même taille, constitués de nombres entiers. Additionnez d’abord les nombres de chaque groupe, puis leurs carrés, leurs cubes, et ainsi de suite. Le défi consiste à obtenir les mêmes totaux pendant plusieurs étapes, alors que les groupes sont différents.

Si les égalités tiennent jusqu’à la puissance numéro k, les deux groupes sont dits k-équivalents. Plus k augmente, plus les nombres doivent imiter finement les mêmes sommes de puissances.

Le problème de Prouhet-Tarry-Escott est un problème de théorie des nombres et de combinatoire. Pour un entier k donné, on cherche deux ensembles A et B, contenant chacun le même nombre n d’entiers. Pour chaque entier i allant de 1 à k, la somme des puissances i-ièmes des éléments de A doit être égale à celle des éléments de B. Cette condition s’écrit :

Lorsque toutes ces égalités sont satisfaites, A et B sont k-équivalents. Une solution trouvée pour un degré k ne l’est pas forcément pour k + 1. La recherche porte généralement sur la plus petite taille n possible. Le problème reste ouvert dans le cas général ; la plus grande valeur de k pour laquelle une solution avec n = k + 1 est connue est k = 11. Eugène Prouhet étudia le problème en 1851. Gaston Tarry et Edward Brind Escott y revinrent indépendamment au début des années 1910.

On veut vérifier si les ensembles A = {0, 3, 5, 6} et B = {1, 2, 4, 7} sont 2-équivalents. Chaque ensemble contient quatre entiers, donc n = 4, et le degré testé est k = 2.

1. Puissance 1. On additionne les éléments de chaque ensemble.

2. Puissance 2. On additionne ensuite les carrés.

Les deux égalités requises sont vérifiées : A et B sont 2-équivalents. Un contrôle supplémentaire délimite le résultat : les sommes des cubes valent respectivement 368 et 416. Ces ensembles ne sont donc pas 3-équivalents. La figure synthétise les égalités obtenues et le premier écart.

Pour vérifier une paire proposée, on calcule les sommes de puissances dans l’ordre, de 1 à k. Comparer seulement les sommes ordinaires ne suffit pas dès que k est supérieur à 1.

Pour écarter une paire, on s’arrête au premier exposant qui produit deux totaux différents. Dans l’exemple, la puissance 3 donne 368 contre 416 : elle suffit à exclure la 3-équivalence.

Pour chercher une solution de taille minimale, trouver une paire de taille n donne une borne, mais ne prouve pas qu’elle est minimale. Il faut aussi montrer qu’aucune paire admissible de taille plus petite ne convient.

Égalité des sommes et k-équivalence. Deux ensembles de même cardinalité qui ont la même somme ne sont que 1-équivalents tant que les puissances suivantes n’ont pas été contrôlées. Le critère testable est le nombre d’exposants consécutifs validés à partir de 1.

Solution triviale. Si les deux ensembles sont identiques, toutes les sommes de puissances coïncident automatiquement. Pour étudier le problème non trivial, il faut donc exiger deux ensembles distincts ; les éléments communs peuvent être retirés des deux côtés.

Contrôle incomplet. Vérifier les puissances 1 et k ne garantit pas les égalités intermédiaires. Pour conclure à la k-équivalence, chaque exposant entier de 1 à k doit être testé ou couvert par une preuve.

Minimalité non acquise. Une solution de taille n prouve seulement que cette taille est réalisable. La qualifier de minimale exige d’exclure toutes les tailles inférieures.

Frontière des connaissances. Le cas connu k = 11 avec n = k + 1 ne signifie pas que le problème général est résolu, ni qu’une telle solution est impossible pour k supérieur à 11. La source indique précisément que le cas général reste ouvert.

La question naturelle suivante porte sur les constructions qui produisent des ensembles k-équivalents et sur la preuve de leur taille minimale. Ces deux directions expliquent pourquoi un énoncé élémentaire conduit à un problème encore ouvert.

Suite de Prouhet-Thue-Morse — Retrouvez une autre notion mathématique portant le nom de Prouhet.