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

${\displaystyle \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 ${\displaystyle k=n-1}$ are called ideal solutions. Ideal solutions are known for ${\displaystyle 3\leq n\leq 10}$ and for ${\displaystyle n=12}$. No ideal solution is known for ${\displaystyle n=11}$ or for ${\displaystyle n\geq 13}$.[1]

This problem was named after Eugène Prouhet, who studied it in the early 1850s,[2] 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}.[3]

Other solutions

Prouhet used the Thue–Morse sequence to construct a solution with ${\displaystyle n=2^{k}}$ for any ${\displaystyle k}$. Namely, partition the numbers from 0 to ${\displaystyle 2^{k+1}-1}$ into the evil numbers and the odious numbers; then the two sets of the partition give a solution to the problem.[4] For instance, for ${\displaystyle n=8}$ and ${\displaystyle 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 ${\displaystyle n,k\in \mathbb {N} }$, find two different multi-sets ${\displaystyle \{(x_{1},y_{1}),\dots ,(x_{n},y_{n})\}}$, ${\displaystyle \{(x_{1}',y_{1}'),\dots ,(x_{n}',y_{n}')\}}$ of points from ${\displaystyle \mathbb {Z} ^{2}}$ such that

${\displaystyle \sum _{i=1}^{n}x_{i}^{j}y_{i}^{d-j}=\sum _{i=1}^{n}{x'}_{i}^{j}{y'}_{i}^{d-j}}$

for all ${\displaystyle d,j\in \{0,\dots ,k\}}$ with ${\displaystyle 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 ${\displaystyle n=6}$ and ${\displaystyle k=5}$ is given, for instance, by:

${\displaystyle \{(x_{1},y_{1}),\dots ,(x_{6},y_{6})\}=\{(2,1),(1,3),(3,6),(6,7),(7,5),(5,2)\}}$ and

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

No solutions for ${\displaystyle n=k+1}$ with ${\displaystyle 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

Notes

1. Borwein, p. 85 harvnb error: no target: CITEREFBorwein (help)
2. A New Kind of Science
3. Solution found by Nuutti Kuosa, Jean-Charles Meyrignac and Chen Shuwen, in 1999.
4. Wright, E. M. (1959), "Prouhet's 1851 solution of the Tarry–Escott problem of 1910", The American Mathematical Monthly, 66: 199–201, doi:10.2307/2309513, MR 0104622.

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.