SEQUENCES OF IDEAL SOLUTIONS IN THE TARRY-ESCOTT

SEQUENCES OF IDEAL SOLUTIONS IN THE

TARRY-ESCOTT PROBLEM

H. L. DORWART

Introduction. In the Tarry-Escott problem (sometimes called

the problem of multi-degree equalities, or of equal sums of like pow-

ers),

one seeks integral solutions of the k equations

(1) E *! = Ê

Vif

I = 1, 2, • • • , *.

The usual notation is to represent a solution of (1) by

(2) 0i, • • • , a

= bu • • •

#«•

Such a solution is called trivial if the a's form a permutation of the b's,

and will be called semi-trivial if any

= a, or

6»

A solution is said

to be in reduced form when X]ai = 0, (a», 6») = 1, and solutions having

the same reduced form are called equivalent solutions.

It is easily shown that for nontrivial solutions, s>k. The case

s = k+l, called the ideal or optimum case [l, 2],

is of particular inter-

est in many applications [5]. For a given fe, N(k) is defined as the

least value of 5 for which (1) has nontrivial solutions. It is known in

general [7] that N(k) ^k(k + l)/2, but numerical examples [ó] give

N(k)=k + lîork = l,2, • • • ,9.

In order to decrease the number of the equations (1), many writers

have imposed the conditions

(3) Xi = — yu i = 1, 2, • • • , s, for 5 odd,

(4) aVfi-i = — #••»

Vê+ir-i

= — ?*, * = If 2, • • • , 5/2, for s even.

Solutions of (1) subject to (3) or (4) will be called symmetric solu-

tions.

It is evident that the conditions for symmetry are sufficient

to assure that symmetric solutions are reduced.

By use of the binomial theorem, one finds that (2) implies

(5) Ma! + K, • • • , Ma, + K = Mfa + K

• • • , Mb, + K,

and

Received by the editors January 17, 1946, and, in revised form, April 20, 1946.

Numbers in brackets refer to the references cited at the end of the paper.

381

382

H. L. DORWART

[April

ai,

• • • , a„ bi + h, • • • , b

+ h

(y)

= bu ' • • ,

b»,

0i + h, • • • , a, + A,

where M, X and ft are any integers.

Equation (6) shows the existence of multi-degree equalities of arbi-

trarily high degree, but in general each time the degree is raised by

one,

the number of terms on each side of the equality is doubled. How-

ever, by taking for h a difference |a*

—

a,-|

|&»-

—

bj\

which occurs /

times,

t terms on one side will cancel with the same number of terms

on the other side. The set of all differences | a*--ay| and

16*

—6y|

will

be called the difference table for a given equality.

If the process indicated in (6) is applied to a nontrivial ideal solu-

tion and leads to another nontrivial ideal solution, these ideal solu-

tions will be said to be in sequence. Thus for a nontrivial ideal equality

of degree k to be in sequence with one of degree

ife

+1,

the value used

for h in (6) must occur exactly

2(&

+ l)

—

(k+2) =k times in the differ-

ence table for the ideal equality of degree k.

The following sequence of ideal solutions has been noted [5].

1,9 = 4, 6,

ft = 2, 1, 8, 9 = 3,4, 11,

(7) ft = 1, 1, 5, 8, 12 = 2, 3, 10, 11,

h = 7,

1,5,9,

17, 18 = 2,3, 11, 15, 19,

h = 8, 1, 5, 10, 18, 23, 27 = 2, 3, 13, 15, 25, 26.

It is the purpose of this paper to determine all sequences of ideal

solutions which begin with degrees one, two and three (the nonsym-

metric case for degree three in not completed). The appearance of

certain substitution groups in the solutions, apparently not previously

observed, will be noted. These groups are then used to simplify many

of the computations which would otherwise be very tedious. Although

the methods of the paper do not lead to new solutions, it is believed

that the tabulation of complete information concerning sequences be-

ginning with low degrees sheds new light on the structure of existing

solutions.

Sequences beginning with the first degree. All reduced ideal solu-

tions of first degree are of necessity in the symmetric form

19471 IDEAL SOLUTIONS IN THE TARRY-ESCOTT PROBLEM 383

(8) a, — a = 6, — b.

If we apply (6) with h = 2a (h =

gives similar results) and then (5)

with M=l and K=

—

a to (8), there results

(9) a +

a — b, — 2a = — a — b, — a + b, 2a.

The difference table for this equality contains 3a+b, 3a

—b

and 2b

each repeated two times. Applying (6) to (9) with h = 3a+by followed

by (5) with M =

and K =

—

we have

(10) ± (7a +

a + 3b) = ± (5a + 36, 5a - 6).

The relationship of (10) and other solutions found in this and suc-

ceeding sections to results given in [2] will be pointed out later.

When the difference table for (10) is formed, it is found by equating

all ai

—

aj-

with each other and with all

—

bj that for the same differ-

ence to occur exactly three times (and thus lead to another nontrivial

ideal solution), a/b must have one of the following sixteen values:

1/2, -5, 1/4, -1/4, -3/7, -1/6, -5/9,

-3/11,

-2/5, 1/7, -2,

3/5, —2/3, —1/9. Fourteen distinct ideal equalities of degree 1 are

obtained from these, leading to only six distinct ideal equalities of de-

gree 2, which in turn give rise to four ideal equalities of degree 3.

These imply two ideal equalities of degree 4 and finally three ideal

equalities of degree 5. Here the sequences end. The relationship of

these qualities to each other is shown in the accompanying chart

(p.

390).

The ideal equality

± (1, 11, 12) = ± (4, 9, 13)

is the reduced form of the fifth degree equality in (7) and is of par-

ticular interest. Two applications of (6) to the last equality of (7) give

h = 13, 1, 5, 10, 16, 27, 28, 38, 39 = 2, 3, 13, 14, 25, 31, 36

40,

h = 11, 1, 5, 10, 24, 28, 42, 47, 51 = 2, 3, 12, 21, 31, 40, 49, 50.

Thus we have an example of an equality of degree 6 which, although

not itself ideal, leads to an ideal equality of degree 7 (see [2, p. 632

(C)]).

This particular ideal equality of degree 7 was first found by

Tarry and has been used as the basis of extensive calculations [8].

Until recently [ó], it was not known if ideal equalities of degree

greater than 7 existed. The best results for N(k)

k>9

are still given

384

H. L. DORWART [April

by numerical examples rather than by theoretical methods.

Application of (6) to (9) with h = 3a

—

followed by (5) with M = 2

and K=

—

3a+b leads to

(11) ± (7a

—

3ft) = ± (5a - 3ft, 5a + ft),

and with h = 26 followed by (5) with M=l and K= —b leads to

(12) ± (2a + ft, a - 2ft) = ± (2a - ft, a + 2ft).

However, neither (11) nor (12) leads to further ideal solutions

dif-

fering from those in the chart.

We now summarize the results of this section in the following theo-

rem.

THEOREM 1. Every reduced ideal equality of degree 1 is symmetric

and implies an ideal equality of degree 2 of the form (9), which in turn

implies three ideal equalities of degree 3 of the form (10), (11) and (12).

The only sequences beginning with degree 1 which extend to degrees 4 and

5 are equivalent to those of the chart; none extends beyond degree 5.

Sequences beginning with the second degree. The general ideal

solution of second degree [3, p. 52] is

(13) AG + BD, AD, BG = AD + BG, AG, BD

where A, B, D, G are any integers. Let A =XJ9, G=[xD, and (13) be-

comes

(14) X/x + 1, X,

Xju, 1,

where

and

are rational numbers. When (14) is put in reduced form

by the application of (5) with M =

and 2£=—X/x—X—/z

—

1, it is

found that the conditions for trivial solutions are X or

= 0, 1, and

for symmetric solutions are

or /x= —1,2, 1/2.

The symmetric ideal solutions of degree two are all equivalent to

(15) X, 1 - X, - 1 = - X, X - l

given directly by (14) with /x=

—

1, with

followed by (5) with

M=l and i£=--X-l, or with

= 1/2 followed by (5) with M = 2

and K=

—X—1.

= (a+ft)/2a, (15) reduces to (9), which is there-

fore equivalent to the general symmetric solution of degree two. Also,

we now see that there are no symmetric sequences which begin with

degree two.

47l IDEAL SOLUTIONS IN THE TARRY-ESCOTT PROBLEM 385

The fact that special cases of (14) are given by

= 0, 1 and

—

1/2 suggests a possible connection with the cross-ratio group G*

of projective geometry. It is easy to show that (15) is invariant under

the substitutions X, 1-X, (X~l)/X, 1/X,

1/(1-X),

X/(X-1) which

form this group.

The difference table for (15) contains X+l,

—2,

2X+1 each twice,

and the equality in

which corresponds to (10) is

(100 ± (3X + 1,

- 3) = ± (3X - 1,

+ 3).

It is evident that (10') is invariant under the substitutions of the

group X, —X, 1/X, —1/X. The values of

for which (10') leads to an

ideal equality of degree 4 (corresponding to the sixteen values of a/b

given in the preceding section) are ±2/3, ±3/2, ±2/5, ±5/2, ±3/4,

±4/3,

±4, ±1/4. Hence we now see why these sixteen values give

only four distinct equalities of degree 3.

Corresponding to (11) and (12) are

(11') ± (3X - 4,

+ 2) « ± (3X - 2,

- 4)

which is invariant under X, 2—X, X/(X

—

1),

(X —

2)/(X

—

1), and

(12') ± (4X - 1, 2X - 3) = ± (4X - 3, 2X + 1),

invariant under X, 1—X, X/(2X—1),

(X —

1)/(2X

—1).

The groups for

(100,

(HO and (120 are abstractly the same G

If neither

nor

± 1, 1/2, 2 in (14) we have a nontrivial, non-

symmetric solution. Forming the difference table, we find that for

(14) to give rise to an ideal equality of degree 3,

fi = X, 1 - X, X/(X - 1), 1/X, 1/(1 - X), (X - 1)/X,

(X + l)/(2 - X), (X - 2)/(2X - 1), (2X - 1)/(X + 1),

(X + 1)/(2X - 1), (1 - 2X)/(2 - X), (2 - X)/(l + X).

These substitutions form a Gn. The first six are, of course, the cross

ratio subgroup, and lead to semi-trivial solutions. The remaining six

all give

(16) X

- 2X, - X

+ 1, 2X - 1 - 0, X

+ 1, - X

- 1,

which is invariant under the G12. An examination of the difference

table for (16) shows that a nontrivial equality of degree 3 can be

formed from (16) by the application of (6) only if ft=X

—X+l. Mak-

ing this application followed by (5) with Af =

and K= —X

—1,

386 H. L. DORWART [April

we have

-3X+3,

-X

+5\-3,

-3X

+X+1, X

-3X-1

(17) '

+3X-1,

-X

--X+3, 3X

-5X+1, -3\

+3X-3,

which is also invariant under the Gn.

The difference table for (17) is found to contain the same value

three times (and one which will lead to a nontrivial equality of de-

gree 4) for twelve numerical values of X. One of these is 3 and the

others can be obtained by substituting

in the last eleven ele-

ments of the G12. The only sequence given is the following.

0, - 7 = 5, 3, - 8,

(18) h = 7, 21, 3, - 1, - 23 = 17, 13, - 9, - 21,

h = 22, 14, 12, - 4, - 5, - 17 = 16, 7, 3, - 10, - 16.

Replacing

by c/d in (16) and (17), we have the following theorem.

THEOREM 2. The only sequences of ideal solutions beginning with de-

gree two are nonsymmetric and are equivalent to

- led, - c

+ d

, led - d

= 0, c

- cd + d

, - c

+ cd - d

- Zed + 3d

, - c

+ 5cd - 3d

, - 3c

+ cd + d

- 3cd - d

= c

+ 3cd - d

- c

- cd + 3d

, 3c

- Scd + d

, - 3c

+ 3cd - 3d

or to (18).

Sequences beginning with the third degree. A. Symmetric case.

The general symmetric solution of third degree is [2, (4)]

(19) öi, a

, — d\, — a* = bi, 6

, — 61, ~ 62

where ai

—

pipz+pzpt, b

= p

—

pzp4,

= pips — p2ph b^^pipz+P^P^

Solution (10') is the special case £i=X, pi —3, pi

—

p±

—

\, (11') the

case £i = 2, pi—\, pz=\

—

=— 1, and (12') the case pi =

—

£2=1,£3 = 2,£4= —1.

Let

p2==apz,

pi~fipi. Then (19) becomes

(20) ± (a + 0, 1 - aft = ± (a - 0, 1 + a/3)

where a and /3 are rational, and where a and /3 play an interchange-

47l IDEAL SOLUTIONS IN THE TARRY-ESCOTT PROBLEM 387

able role. Equality (20) is trivial if a or

= 0, ± 1, and semi-trivial if

P = a, - a, 1/a, - 1/a, (1 + a)/(l - a), - (1 + a)/(l - a),

(1 - a)/(l + a), - (1 - a)/(l + a).

These substitutions form a G

. Three equal differences leading to a

nontrivial equality of degree 4 occur in the difference table for (20)

if/3,

-^,l/^,-l/^

= (3a+l)/(a+l),(3a-l)/(a-l),(ce+3)/(a+l),

(ce-3)/(ce-l), (ce+3)/(3ce-l),

(3ce

+ l)/(3-ce). But since (20) is in-

variant under /3, —/3, 1/3,

—

l/j8 we need consider only the six ex-

pressions in a. Finally, since the first four expressions are invariant

under ce,

—

ce,

1/ce, —1/a, and the last two under ce and 1/a, we need

consider only 0 = (3ce+l)/(ce + l) and

= (ce+3)/(3ce-1).

(i) Let

(3ce

+ l)/(ce,+ l). Then (20) becomes

(21) ± (3a

+ 2a + 1, a

- 2ce - 1) = ± (3a

- 1, ce

+ 4a + 1),

which is trivial if

= 0, ±1, —1/2, —1/3 and which is given by [2,

(11)] with a=a

+4ce+l,

3ce

+ 2ce+l, and fe=ce

-2ce-l. The

only value for h leading to a nontrivial ideal equality of degree 4 is

2ce

—4ce

—2,

giving

-a-l, ce

+2ce+l, -3ce-l, -a

+2a+l, -2ce

(22)

= 2a

, a

-2a-l, 3ce+l, -ce

-2ce-l, -2<x

+ce+l.

There are sixteen values of

for which the sequence continues, twelve

of them (in three sets of four each) when substituted in (21) leading to

± (1, 17) = ± (11, 13), ± (3, 11) = ± (7, 9),

± (1, 13) = ± (7, 11),

all of which appear in the chart. The remaining four values, —3/2,

1/5, -1/7, -3/4 all give

± (11, 23) = ± (17, 19),

(23) h = 34, 18, 17, - 1, - 14, - 20 = 20, 14, 1, - 17, - 18,

h = 19, ± (15, 47, 59) = ± (9, 53, 55).

(ii) Let/3 = (ce+3)/(3ce-l). Then (20) becomes

(24) ± (3a

+ 3, a

+ 1) = ± (3a

- 2a - 3, a

+ 6a - 1),

388 H. L. DORWART [April

which is trivial if a = 0, ±1, 2, —1/2, —3, 1/3, and which is given

by [2, (13)] with

= 3a

-2a-3, v**a*+6a-l, k*=a

+l. For

a =—2, (24) gives the fourth equality of degree 3 of the chart,

namely

± (5, 15) = ± (9, 13).

The sequence beginning with (24) continues for h =

-\-\

with

--a-l, a

+3a, -3a+l, -a

+a+2, -2a

--2

(25)

= 2a

+2, a

-a-2, 3a-l, -a

-3a, -2a

+a+l,

and then for h = a

—

with

± (5a

- 4a + 3, 3a

- 6a - 5, a

+ 10a + 1)

(26)

= ± (5a

- 6a - 3, 3a

+ 4a + 5, a

- 10a + 1),

or for h = 2a

+2a -

with

, , ± (3a

+ a + 1, 2a

- 3, a

+ 4a - 2)

(27)

= ± (3a

- 2, 2a

+ 4a - 1, a

- a + 3).

However, there are no real values of a giving an ideal equality of de-

gree 6.

Nonsymtnetric case. The general nonsymmetric solution of third

degree is [2, (10)]

a\ —

—

mr + ns + /, h\ =

—

r + s + mnt,

ai = mr — ns + t,

= r

—

5 + mw/,

(28)

«3 = wr + ws

—

/, #3 = r -\- s — mnt,

at =

—

/, £

—

s — mnt,

where m and n are rational numbers not equal to 0, ±1 and where

r = - (

* -

tf*

- 2(w

- 1)1/7 + (w

- 1>7

* = (

2 _ j)^ _

- l)nUV - (w

- 1)F

t~{m

- 1)U

+ (n

- 1)F

with U and F relatively prime integers.

Equality (17) is given by (28) with m = X, n =

—

(X — 1)/X,

/=--(X-2),

r=X+l, s=X(2X-l). The equality of degree 3 of (18)

is given by w =

n = 3, Z7= 1, V=

—3.

To determine sequences starting with (28), it is best to form the

47l IDEAL SOLUTIONS IN THE TARRY-ESCOTT PROBLEM 389

difference table for the transformation used in [2, (6)]. This leads to

a series of linear conditions which are then incorporated in [2, (8)]

and finally in the parametric solution. The following example shows

the existence of such sequences. Withw =

= 2,

£7=3,

F=l,wehave

31,

13, - 21, - 23 = 29, 11, - 7, - 33

h = 18, 47, 13, - 15, - 21, - 23 = 49, - 3, - 5, - 7, - 33.

THEOREM 3. All symmetric sequences beginning with degree three are

equivalent to (21) (22), to (24) (25) (26) or (27) (in all of which a is ra-

tional),

or to (23). Nonsymmetric sequences beginning with degree three

exist and can be determined by the method of this paper.

Sequences beginning with higher than the third degree. Gen-

eral parametric ideal solutions have not been found beyond the third

degree, but many special solutions are known [l, 2, 4, 6]. Although

probably only sequences beginning with low degrees extend for more

than 2 or 3 steps, sequences beginning with high degrees do exist.

This paper will be concluded with two numerical examples of se-

quences which were obtained from known ideal equalities of degrees

6 and 8 by the use of a theorem of Escott [5, page 617] which gives

the predecessor of a given equality. In neither case can the sequence

be extended in either direction.

The first example is

18, 35, 59, 72 = 2, 15, 39, 56, 73,

h - 17, 1, 19, 32, 59, 72, 90 = 2, 15, 39, 52, 76, 89,

h = 13, 1, 19, 28, 59, 65, 90, 102 = 2, 14, 39, 45, 76, 85, 103,

where the equality of degree 6 is due to Escott [5, p. 616].

The second example is

25, 31, 72, 87, 128, 134, 158

= 2, 18, 43, 59, 100, 116, 141, 157,

' 1, 25, 31, 84, 87, 134, 158, 182, 198

= 2, 18, 42, 66

113, 116, 169, 175, 199,

where the equality of degree 8 is due to Letac [6, p. 48].

1111111 1111111

±1

±3 ±1 = ±2 ±1 = ±5 ±1 = ±4 ±3 = ±7 ±1=±6 ±5=±9 ±3=±11 ±2 = ±5 ±1=±7 ±1=±2 ±3 = ±5 ±2 = ±3 ±1=±9

h=6 h=2 h=2 h = 10 &=2 A=6 A = 14 h=2 A = 10

1 1 1 I 1 I 1 I

2 2 2

-1,

-2=2, 1, -3

2, -5=5, -2, -3

5, 2,

-7 =

-2, -5

h=6 h=4: h = U h=2 A=4 k=6 A = 10 A=4 *=2

I 1 I 1 I I 1 1

2 2 2

3, -7=7, -3, -4 3, 1, -4=4,

-1,

-3 4, 1, -5=5,

-1,

-4

fc=5

h =

= 7 A»3 fc = l h=7 A=5 A=3

±(3,

11) =

±(7,

h = U

±(1,17) =

±(11,

13)

£=2

3 3

±(5, 15)

= ±(9, 13) ±(1,

13)

= ±(7,11)

A = 10 h = U

8,7, -1, -5,

-9=9,5,1,

-7,

6=4

9, 7, -2 -4, -10 =

10,

4, 2, -7, -9

A=2 Â = ll

±(1,11, 12)

= ±(4,9,13)

±(1,9,10) = ±(5, 6, 11)

±(9,

25, 29) =

±(15,

19,31)

47] IDEAL SOLUTIONS IN THE TARRY-ESCOTT PROBLEM 391

REFERENCES

J. L. Burchnall and T. W. Chaundy, A type of magic square in Tarry

s prob-

lem,

Quart. J. Math. Oxford Ser. vol. 8 (1937) pp. 119-130.

J. Chernick, Ideal solutions of the Tarry-Escott

problem,

Amer. Math. Monthly

vol.

44 (1937) pp. 626-633.

L. E. Dickson, Introduction to the theory of

numbers,

Chicago, 1929, pp. 49-58.

, History of

the

theory of

numbers,

Washington, 1920, vol. 2, chap. 24.

H. L. Dorwart and O. E. Brown, The Tarry-Escott problem, Amer. Math.

Monthly vol. 44 (1937) pp. 613-626.

6. A. Gloden,

Mehrgradige

Gleichungen,

Noordhoff, Groningen, Holland, 1944.

G. H. Hardy and E. M. Wright, An introduction to the theory of numbers,

Oxford, 1938, pp.

328-331.

8. A. Moessner and W. Schulz, Über Potenzsummen ganzer rationaler Zahlen,

Math. Zeit. vol. 41 (1936) pp. 340-344.

WASHINGTON

AND JEFFERSON COLLEGE