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$ .[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 $n=2^{k}$ for any $k$ . Namely, partition the numbers from 0 to $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 $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.

Notes

Borwein, p. 85
A New Kind of Science
Solution found by Nuutti Kuosa, Jean-Charles Meyrignac and Chen Shuwen, in 1999.
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.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[Borwein-1] Borwein, p. 85

[NKS_note_a-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.