The Prouhet-Tarry-Escott Problem

The Prouhet-Tarry-Escott Problem (PTE Problem) is an old unsolved problem in number theory. Extensive accounts on it are available in [27] or [15].

In its most general setting the PTE Problem asks for two multisets of integers (or, equivalently, of rational numbers) $X=\{x_1,\ldots,x_s\}$ and
$Y=\{y_1,\ldots,y_s\}$ such that

$$\sum_{i=1}^s x_i^e=\sum_{i=1}^s y_i^e\ \ \ \ \ \ e=1,2,\ldots,s-1.$$ (9)

Of course the system (9) is satisfied if X and Y are equal as multisets; such solutions we call trivial. Also, if X,Y are multisets satisfying the system (9) and $f:t\mapsto at+b$ is a linear transformation with rational coefficients, then the multisets f(X), f(Y) satisfy (9). We then say that X,Y and f(X),f(Y) are equivalent solutions. In what follows we consider only non-trivial solutions up to equivalence.

Solutions to the PTE Problem are known only for $s=1,\ldots,10$, and in all these cases (except s=9) it is known that there are infinitely many non-equivalent solutions.

Due to its large underdeterminacy as a polynomial equation system, the PTE Problem is often considered in its more restrictive, symmetric version. For s odd, the symmetric version takes the form

$$\sum_{i=1}^s z_i^e=0\ \ \ \ \ \ e=1,3,\ldots,s-2.$$ (10)

Clearly, if $z_1,\ldots,z_s$ satisfy (10), then $x_1=z_1,\ldots,x_s=z_s$ and $y_1=-z_1,\ldots,$y_s=-z_s is a solution of (9). Such PTE solutions we call odd symmetric solutions [15].

In the case s=9, only two solutions to the PTE Problem are known, and they are both odd symmetric solutions. They are, up to equivalence, generated by

$$\{z_1,\ldots,z_9\}= \{-98, -82, -58, -34, 13, 16, 69, 75, 99\}$$ (11)

and

$$\{z_1,\ldots,z_9\}=\{-169, -161, -119, -63, 8, 50, 132, 148, 174\}.$$ (12)

Since the entries of (11) and (12) are small integers, we of course expect that there exist many relations for them with small integer coefficients. There is, however, one type of relations whose frequency is striking in the output of an integer relation algorithm: it is

 

z_i1+z_i2+z_i3+z_i4=z_j1+z_j2+z_j3+z_j4+z_j5=0 (13)

where $\{i_1,i_2,i_3,i_4\}\cup\{j_1,j_2,j_3,j_4,j_5\}$ is a disjoint partition of $\{1,2,\ldots,9\}$. (Recall from (10) that $\sum_{i=1}^9 z_i=0$. Thus (13) represents just one relation, in spite of being written as two equations.) While there is one relation of the form (13) for the vector (11), there are as many as four linearly independent relations of the form (13) in the case of the vector (12), far more than would be suggested by a simple counting argument: merely assuming that (12) consisted of nine random integers that sum up to 0.

This finding suggested forcibly that split relations of the type (13) are a frequent feature of odd symmetric PTE solutions, and led us to check the other odd symmetric solutions we knew for the presence of this phenomenon. Interestingly, of the more 265 odd symmetric solutions of size 7 that we computed in several months of CPU time, more than 86% have a relation analogous to (13), that is z_i1+z_i2+z_i3=z_j1+z_j2+z_j3+z_j4=0. (Here, analogously, the i and j index sets are a disjoint partition of $\{1,2,\ldots,7\}$.)

While we do not yet have an explanation for this phenomenon, we have apparently discovered a new fact about the symmetric PTE solutions that had not been noted previously in the literature.