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
∑ a ∈ A a i = ∑ b ∈ B b i {\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 k = n − 1 {\displaystyle k=n-1} are called ideal solutions. Ideal solutions are known for 3 ≤ n ≤ 10 {\displaystyle 3\leq n\leq 10} and for n = 12 {\displaystyle n=12} . No ideal solution is known for n = 11 {\displaystyle n=11} or for n ≥ 13 {\displaystyle 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:
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}.
Other solutions Prouhet used the Thue–Morse sequence to construct a solution with n = 2 k {\displaystyle n=2^{k}} for any k {\displaystyle k} . Namely, partition the numbers from 0 to 2 k + 1 − 1 {\displaystyle 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 {\displaystyle n=8} and k = 3 {\displaystyle 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 , k ∈ N {\displaystyle n,k\in \mathbb {N} } , find two different multi-sets { ( x 1 , y 1 ) , … , ( x n , y n ) } {\displaystyle \{(x_{1},y_{1}),\dots ,(x_{n},y_{n})\}} , { ( x 1 ′ , y 1 ′ ) , … , ( x n ′ , y n ′ ) } {\displaystyle \{(x_{1}',y_{1}'),\dots ,(x_{n}',y_{n}')\}} of points from Z 2 {\displaystyle \mathbb {Z} ^{2}} such that
∑ i = 1 n x i j y i d − j = ∑ i = 1 n x ′ i j y ′ i d − j {\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 d , j ∈ { 0 , … , k } {\displaystyle d,j\in \{0,\dots ,k\}} with j ≤ d . {\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 n = 6 {\displaystyle n=6} and k = 5 {\displaystyle k=5} is given, for instance, by:
{ ( x 1 , y 1 ) , … , ( x 6 , y 6 ) } = { ( 2 , 1 ) , ( 1 , 3 ) , ( 3 , 6 ) , ( 6 , 7 ) , ( 7 , 5 ) , ( 5 , 2 ) } {\displaystyle \{(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 ′ ) , … , ( x 6 ′ , y 6 ′ ) } = { ( 1 , 2 ) , ( 2 , 5 ) , ( 5 , 7 ) , ( 7 , 6 ) , ( 6 , 3 ) , ( 3 , 1 ) } {\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 n = k + 1 {\displaystyle n=k+1} with k ≥ 6 {\displaystyle k\geq 6} are known. --- "Pythagorean Triangle Approach" to the Prouhet-Tarry-Escott Problem for k=2, n=3 by Ali Uzel, a solution where the algebra meets geometry. a1 + b1 + c1 = d1 + e1 + f1 a2 + b2 + c2 = d2 + e2 + f2 say, a2 + b2 = d2 Pythagóras triangle A, where d is hypotenuse, a and b are sides c2 = e2 + f2 Pythagóras triangle B, where c is hypotenuse, e and f are sides if you sum both sides, a2 + b2 + c2 = d2 + e2 + f2 Thus, this equation seems to contain two Pythagorean Triangles. from equation a1 + b1 + c1 = d1 + e1 + f1 => a1 + b1 - d1 = e1 + f1 - c1 On the other hand you can calculate radius of an inscribed circle in a Pythagorean Triangleas follows: r = (length of the first side + length of the second side - length of the hypotenuse) / 2 Both left and right sides of this equation mimic to calculate the radius of an inscribed circle in a Pythagorean Triangle. Thus, there might be two Pythagorean Triangleas that have the common inscribed circle of which their lengths can be a solution for Prouhet-Tarry-Escott Problem for k=2, n=3. Therefore, lengths of two Pythagorean Triangleas are the solutions if they meet the following equation where (a,b,d) belongs to Pythagorean Triangle A, (e,f,c) belongs to Pythagorean Triangle B. d and c are hypotenus for Pythagorean Triangle A and B respectively. a1 + b1 - d1 = e1 + f1 - c1 Example-1: (5,12,13) and (6,8,10) are the appropriate Pythagorean Triangles for the solution. 5 + 12 - 13 = 6 + 8 - 10 = 4 If you apply to the following equations, a1 + b1 + c1 = d1 + e1 + f1 a2 + b2 + c2 = d2 + e2 + f2 5 + 12 + 10 = 6 + 8 + 13 52 + 122 + 102 = 62 + 82 + 132 By using this approach, different Pythagorean Triangles can be considered for k=2, n=3,6,9...
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
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