Prouhet–Tarry–Escott problem

In mathematics, the Prouhet–Tarry–Escott problem asks for two disjoint multisets A and B of n integers each, whose first k power sum symmetric polynomials are all equal. That is, the two multisets should satisfy the equations

$\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\leq n\leq 10$ and for $n=12$. No ideal solution is known for $n=11$ or for $n\geq 13$.

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

Examples

Ideal solutions

An ideal solution for n = 6 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⁵.

For n = 12, an ideal solution is given by A = {±22, ±61, ±86, ±127, ±140, ±151} and B = {±35, ±47, ±94, ±121, ±146, ±148}.

Other solutions

Prouhet used the Thue–Morse sequence to construct a solution with $n=2^{k}$ for any $k$. Namely, partition the numbers from 0 to $2^{k 1}-1$ into a) the numbers each with an even number of ones in its binary expansion and b) the numbers each with an odd number of ones in its binary expansion; then the two sets of the partition give a solution to the problem. For instance, for $n=8$ and $k=3$, Prouhet's solution is:

0¹ 3¹ 5¹ 6¹ 9¹ 10¹ 12¹ 15¹ = 1¹ 2¹ 4¹ 7¹ 8¹ 11¹ 13¹ 14¹

0² 3² 5² 6² 9² 10² 12² 15² = 1² 2² 4² 7² 8² 11² 13² 14²

0³ 3³ 5³ 6³ 9³ 10³ 12³ 15³ = 1³ 2³ 4³ 7³ 8³ 11³ 13³ 14³.

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}^{n}x_{i}^{j}y_{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 special Prouhet-Tarry-Escott solutions over the Gaussian integers (though solutions to the Alpers-Tijdeman problem do not exhaust the Gaussian integer solutions to Prouhet-Tarry-Escott).

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\geq 6$ are known.

See also

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

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-1685-96&rft.pub=Springer-Verlag&rft.date=2002&rft.isbn=0-387-95444-9&rft.aulast=Borwein&rft.aufirst=Peter B.&rft_id=https://books.google.com/books?id=A_ITwN13J6YC&pg=85#PPA85,M1&rfr_id=info:sid/en.wikipedia.org:Prouhet–Tarry–Escott problem" class="Z3988"> 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-01403-412&rft.date=2007&rft_id=info:doi/10.1016/j.jnt.2006.07.001&rft.aulast=Alpers&rft.aufirst=Andreas&rft.au=Rob Tijdeman&rft_id=http://www.math.leidenuniv.nl/~tijdeman/altijd.pdf&rfr_id=info:sid/en.wikipedia.org:Prouhet–Tarry–Escott problem" class="Z3988">.

External links

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