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 {\displaystyle k=n-1} {\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, 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:
- 01 + 51 + 61 + 161 + 171 + 221 = 11 + 21 + 101 + 121 + 201 + 211
- 02 + 52 + 62 + 162 + 172 + 222 = 12 + 22 + 102 + 122 + 202 + 212
- 03 + 53 + 63 + 163 + 173 + 223 = 13 + 23 + 103 + 123 + 203 + 213
- 04 + 54 + 64 + 164 + 174 + 224 = 14 + 24 + 104 + 124 + 204 + 214
- 05 + 55 + 65 + 165 + 175 + 225 = 15 + 25 + 105 + 125 + 205 + 215.
For n = 12, an ideal solution is given by A = {±22, ±61, ±86, ±127, ±140, ±151} and B = {±35, ±47, ±94, ±121, ±146, ±148}.[2]
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 \( {\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.[3] For instance, for n=8 and k=3, Prouhet's solution is:
- 01 + 31 + 51 + 61 + 91 + 101 + 121 + 151 = 11 + 21 + 41 + 71 + 81 + 111 + 131 + 141
- 02 + 32 + 52 + 62 + 92 + 102 + 122 + 152 = 12 + 22 + 42 + 72 + 82 + 112 + 132 + 142
- 03 + 33 + 53 + 63 + 93 + 103 + 123 + 153 = 13 + 23 + 43 + 73 + 83 + 113 + 133 + 143.
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\( 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
Taxicab number
Pythagorean quadruple
Sums of powers, a list of related conjectures and theorems
Discrete tomography
Notes
Borwein, p. 85
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.
Undergraduate Texts in Mathematics
Graduate Studies in Mathematics
Hellenica World - Scientific Library
Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License
