In
mathematics
Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
, the Prouhet–Tarry–Escott problem asks for two
disjoint multiset
In mathematics, a multiset (or bag, or mset) is a modification of the concept of a set that, unlike a set, allows for multiple instances for each of its elements. The number of instances given for each element is called the ''multiplicity'' of ...
s ''A'' and ''B'' of ''n''
integer
An integer is the number zero (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative in ...
s each, whose first ''k''
power sum symmetric polynomial In mathematics, specifically in commutative algebra, the power sum symmetric polynomials are a type of basic building block for symmetric polynomials, in the sense that every symmetric polynomial with rational coefficients can be expressed as a sum ...
s 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
.
This problem was named after
Eugène Prouhet, who studied it in the early 1850s, and
Gaston Tarry
Gaston Tarry (27 September 1843 – 21 June 1913) was a French mathematician. Born in Villefranche de Rouergue, Aveyron, he studied mathematics at high school before joining the civil service in Algeria. He pursued mathematics as an amateur.
In ...
and Edward B. Escott, who studied it in the early 1910s. The problem originates from letters of
Christian Goldbach and
Leonhard Euler
Leonhard Euler ( ; ; ; 15 April 170718 September 1783) was a Swiss polymath who was active as a mathematician, physicist, astronomer, logician, geographer, and engineer. He founded the studies of graph theory and topology and made influential ...
(1750/1751).
Examples
Ideal solutions
An ideal solution for ''n'' = 6 is given by the two sets
and , because:
: 0
1 + 5
1 + 6
1 + 16
1 + 17
1 + 22
1 = 1
1 + 2
1 + 10
1 + 12
1 + 20
1 + 21
1
: 0
2 + 5
2 + 6
2 + 16
2 + 17
2 + 22
2 = 1
2 + 2
2 + 10
2 + 12
2 + 20
2 + 21
2
: 0
3 + 5
3 + 6
3 + 16
3 + 17
3 + 22
3 = 1
3 + 2
3 + 10
3 + 12
3 + 20
3 + 21
3
: 0
4 + 5
4 + 6
4 + 16
4 + 17
4 + 22
4 = 1
4 + 2
4 + 10
4 + 12
4 + 20
4 + 21
4
: 0
5 + 5
5 + 6
5 + 16
5 + 17
5 + 22
5 = 1
5 + 2
5 + 10
5 + 12
5 + 20
5 + 21
5.
For ''n'' = 12, an ideal solution is given by ''A'' = and ''B'' = .
Other solutions
Prouhet used the
Thue–Morse sequence
In mathematics, the Thue–Morse or Prouhet–Thue–Morse sequence is the binary sequence (an infinite sequence of 0s and 1s) that can be obtained by starting with 0 and successively appending the Boolean complement of the sequence obtained thus ...
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.
[.] For instance, for
and
, Prouhet's solution is:
:0
1 + 3
1 + 5
1 + 6
1 + 9
1 + 10
1 + 12
1 + 15
1 = 1
1 + 2
1 + 4
1 + 7
1 + 8
1 + 11
1 + 13
1 + 14
1
:0
2 + 3
2 + 5
2 + 6
2 + 9
2 + 10
2 + 12
2 + 15
2 = 1
2 + 2
2 + 4
2 + 7
2 + 8
2 + 11
2 + 13
2 + 14
2
:0
3 + 3
3 + 5
3 + 6
3 + 9
3 + 10
3 + 12
3 + 15
3 = 1
3 + 2
3 + 4
3 + 7
3 + 8
3 + 11
3 + 13
3 + 14
3.
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
, 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
In number theory, a Gaussian integer is a complex number whose real and imaginary parts are both integers. The Gaussian integers, with ordinary addition and multiplication of complex numbers, form an integral domain, usually written as \mathbf /ma ...
(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
*
Euler's sum of powers conjecture
In number theory, Euler's conjecture is a disproved conjecture related to Fermat's Last Theorem. It was proposed by Leonhard Euler in 1769. It states that for all integers and greater than 1, if the sum of many th powers of positive integers ...
*
Beal's conjecture
The Beal conjecture is the following conjecture in number theory:
:If
:: A^x +B^y = C^z,
:where ''A'', ''B'', ''C'', ''x'', ''y'', and ''z'' are positive integers with ''x'', ''y'', ''z'' > 2, then ''A'', ''B'', and ''C'' have a common prime fa ...
*
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
* Chap.11.
*.
External links
*
{{DEFAULTSORT:Prouhet-Tarry-Escott problem
Diophantine equations
Unsolved problems in mathematics