Trisha Shetty (Editor)

Prouhet–Tarry–Escott problem

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

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

Contents

∑ a ∈ A a i = ∑ b ∈ 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 ≤ n ≤ 10 and for n = 12 . No ideal solution is known for n = 11 or for n ≥ 13 .

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

Examples

It has been shown that n must be strictly greater than k. The largest value of k for which a solution with n = k+1 is known is given by A = {±22, ±61, ±86, ±127, ±140, ±151}, B = {±35, ±47, ±94, ±121, ±146, ±148} for which k = 11.

An example for n = 6 and k = 5 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.

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. 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 , k ∈ N , find two different multi-sets { ( x 1 , y 1 ) , … , ( x n , y n ) } , { ( x 1 ′ , y 1 ′ ) , … , ( x n ′ , y n ′ ) } of points from Z 2 such that

∑ i = 1 n x i j y i d − j = ∑ i = 1 n x ′ i j y ′ i d − j

for all d , j ∈ { 0 , … , k } with j ≤ 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 ) , … , ( 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 ) } .

No solutions for n = k + 1 with k ≥ 6 are known.

References

Prouhet–Tarry–Escott problem Wikipedia
(Text) CC BY-SA