Prouhet–Tarry–Escott problem

In mathematics, the Prouhet–Tarry–Escott problem asks for two disjoint multisets A and B of n integers each, such that:

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

for each integer i from 1 to a given k. It has been shown that n must be strictly greater than k. Solutions with $k = n - 1$ are called ideal solutions. Ideal solutions are known for $3 \le n \le 10$ and for $n = 12$. No ideal solution is known for $n=11$ or for $n \ge 13$.^[1]

This problem was named after Eugène Prouhet, who studied it in the early 1850s, and Gaston Tarry and Escott, who studied it in the early 1910s. The problem originates from letters of Christian Goldbach and Leonhard Euler (1750/1751).

Examples

It has been shown that n must be strictly greater than k. The largest value of k for which a solution with n = k+1 is known is given by A = {±22, ±61, ±86, ±127, ±140, ±151}, B = {±35, ±47, ±94, ±121, ±146, ±148} for which k = 11.^[2]

An example for n = 6 and k = 5 is given by the two sets { 0, 5, 6, 16, 17, 22 } and { 1, 2, 10, 12, 20, 21 }, because:

0¹ + 5¹ + 6¹ + 16¹ + 17¹ + 22¹ = 1¹ + 2¹ + 10¹ + 12¹ + 20¹ + 21¹

0² + 5² + 6² + 16² + 17² + 22² = 1² + 2² + 10² + 12² + 20² + 21²

0³ + 5³ + 6³ + 16³ + 17³ + 22³ = 1³ + 2³ + 10³ + 12³ + 20³ + 21³

0⁴ + 5⁴ + 6⁴ + 16⁴ + 17⁴ + 22⁴ = 1⁴ + 2⁴ + 10⁴ + 12⁴ + 20⁴ + 21⁴

0⁵ + 5⁵ + 6⁵ + 16⁵ + 17⁵ + 22⁵ = 1⁵ + 2⁵ + 10⁵ + 12⁵ + 20⁵ + 21⁵.

Generalizations

A higher dimensional version of the Prouhet–Tarry–Escott problem has been introduced and studied by Andreas Alpers and Robert Tijdeman in 2007: Given parameters $n,k \in \mathbb{N}$, find two different multi-sets $\{(x_1,y_1),\dots,(x_n,y_n)\}$, $\{(x_1',y_1'),\dots,(x_n',y_n') \}$ of points from $\mathbb{Z}^2$ such that

$\sum_{i=1}^nx_i^jy_i^{d-j}=\sum_{i=1}^n{x'}_i^j{y'}_i^{d-j}$

for all $d,j \in \{0,\dots,k\}$ with $j \leq d.$ This problem is related to discrete tomography and also leads to Prouhet-Tarry-Escott solutions over the Gaussian integers.

A solution for $n=6$ and $k=5$ is given, for instance, by:

$\{(x_1,y_1),\dots,(x_6,y_6)\}=\{(2,1),(1,3),(3,6),(6,7),(7,5),(5,2)\}$ and

$\{(x'_1,y'_1),\dots,(x'_6,y'_6)\}=\{(1,2),(2,5),(5,7),(7,6),(6,3),(3,1)\}$.

No solutions for $n=k+1$ with $k\geq6$ are known.

See also

• Thue–Morse sequence
• Euler's sum of powers conjecture
• Beal's conjecture
• Jacobi–Madden equation
• Taxicab number
• Pythagorean quadruple
• Sums of powers, a list of related conjectures and theorems
• Discrete tomography

Notes

1. Borwein, p. 85
2. Solution found by Nuutti Kuosa, Jean-Charles Meyrignac and Chen Shuwen, in 1999.

References

• Borwein, Peter B. (2002), "The Prouhet–Tarry–Escott problem", Computational Excursions in Analysis and Number Theory, CMS Books in Mathematics, Springer-Verlag, pp. 85–96, ISBN 0-387-95444-9, retrieved 2009-06-16 Chap.11.
• Alpers, Andreas; Rob Tijdeman (2007), "The Two-Dimensional Prouhet-Tarry-Escott Problem" (PDF), Journal of Number Theory 123 (2): 403–412, doi:10.1016/j.jnt.2006.07.001, retrieved 2015-04-01.

External links

• Weisstein, Eric W., "Prouhet-Tarry-Escott problem", MathWorld.