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

for each integer i from 1 to a given k. It has been shown that n must be strictly greater than k. Solutions with are called ideal solutions. Ideal solutions are known for and for . No ideal solution is known for or for .[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

edit

Ideal solutions

edit

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

edit

Prouhet used the Thue–Morse sequence to construct a solution with   for any  . Namely, partition the numbers from 0 to   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.[3] For instance, for   and  , 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

edit

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  , find two different multi-sets  ,   of points from   such that

 

for all   with   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   and   is given, for instance, by:

  and
 .

No solutions for   with   are known.

See also

edit

Notes

edit
  1. ^ Borwein 2002, p. 85.
  2. ^ Solution found by Nuutti Kuosa, Jean-Charles Meyrignac and Chen Shuwen, in 1999.
  3. ^ 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

edit
edit