Chapter 1

Euler's Conjecture

We begin with a topic that will be familiar to most number theorists.

Euler stated the well known conjecture that the Diophantine equation

(1.1)

has no non-trivial solutions in non-negative integers when n < m. In the case m = 2, there is no real issue, since there is an infinite number of solutions for n = 2, also known as Pythagorean triples, and generated by the parametric characterisation:

All primitive solutions of the Pythagorean equation x2 + y2 = z2 may be obtained from setting x = 2st, y = s2 - t2,

z = s2 + t2 for integers s > t > 0 such that gcd (s,t) = 1 and one is odd and the other even (see page 245 of [5]).

For m > 2, Fermat's Last Theorem, which we shall take to be true, implies that there are no solutions for n = 2. Immediately, this means that the conjecture is true for m = 3. In fact, there are many known solutions of equation (1.1) for m = n = 3, the smallest, i.e. the solution with lowest value of x, being that 63 = 53 + 43 + 33, and the general parametric solution was given by Euler himself (see, for example, [8]).

The first case of real interest arises for m = 4. The smallest solution for n = 4 is

3534 = 3154 + 2724 + 1204 + 304

and was found by Norrie [18]. A list of the first 23 solutions is given in [12]. These were found by direct search as no parametric solution is known. Euler's Conjecture implies that no solution exists for n = 3. A simple argument using the congruences a4 º 0 or 1 mod 16 and a4 º 0 or 1 mod 5 implies that a primitive solution for n = 3 requires that x and one of the yi, y1 say, are odd and that x and one of the yi are not divisible by 5. There are two cases, either y1 is not divisible by 5 or one of the other yi, y2 say, is not divisible by 5. In the first case a direct search can then be restricted to locating x and y1 satisfying these conditions and such that x4 - y14 is divisible by 104, and then attempting to decompose T = (x4-y14)/104 as the sum of two fourth powers. The congruences given above also require that both T mod 8 and T mod 5 are less than 3, and so any T for which these conditions do not hold can be ignored as a solution cannot exist. In the second case, x4 - y14 - y24 must actually be a fourth power. An additional argument due to Ward (see [26]) requires that either x+y1 or x-y1 must be divisible by 210. Given the severe restrictions which can be imposed, it is surprising that no solutions had been found by direct search before 1987, when Elkies [11], using the theory of elliptic curves, obtained the first known solution for n = 3:

206156734 = 187967604 + 153656394 + 26824404

and a method of generating a new solution from a known solution. The solution obtained from the above equation has all four integers of 70 digits. Thus Euler's Conjecture is false for m = 4. Following this discovery, Frye (see [11]) located the smallest solution by direct search:

4224814 = 4145604 + 2175194 + 958004

Definition: Let s(m) be the minimum value of n such that a non-trivial solution of (1.1) exists.

Then we have s(2) = 2, s(3) = 3, s(4) = 3 and Fermat's Theorem implies that s(m) > 2 for all other values of m. Euler's Conjecture can now be rephrased simply as: s(m) ³ m for all m.

We have seen that the conjecture is false for m = 4. In fact, the earliest counterexample, and the only other known to date, is for m = 5, and was discovered in 1966 by Lander & Parkin [13] during a direct search for solutions for m = 5 and n £ 5:

1445 = 1335 + 1105 + 845 + 275

This is the only known solution for n = 4, (but then only one is enough) and implies that either s(5) = 3 or s(5) = 4. During the same search, Lander & Parkin also found the smallest solution for n = 5:

725 = 675 + 475 + 465 + 435 + 195

The first 12 solutions for n = 5 are listed in [13]. A non-exhaustive two-parameter characterisation is known that gives an infinite number of solutions (see [19]).

The situation is less clear for m > 5. Consider m = 6. Since a6 º 0 or 1 mod 9, in order to obtain a primitive solution for n = 8 we must have x and one of the yi, y1 say, not divisible by 3, and all others divisible by 3. We may then restrict a direct search over x and y1 such that x6 - y16 is divisible by 36 and then try to decompose T = (x6 - y16)/36 as the sum of seven sixth powers. If such a decomposition is found, we multiply each value by 3 to obtain y2 to y8. In this way, Lander, Parkin & Selfridge [14] found the smallest solution for n = 8:

2516 = 2466 + 1656 + 1386 + 1026 + 786 + 306 + 126 + 86

Restricting to n = 7, we can also use the congruence a6 º 0 or 1 mod 8, so that x and one of the yi must be odd. We now have two cases, since the above argument modulo 9 still holds, and so either y1 is odd, or another yi, y2 say, is odd. In the first case, x6 - y16 must now be divisible by 66 and we try to decompose T = (x6 - y16)/66 as the sum of six sixth powers. We also note that T mod 9 and T mod 8 must both be less than 7, and that since x6 - y16 = (x+y1).(x-y1).(x2+xy1+y12).(x2-xy1+y12) and the last two terms here cannot be divisible by 2, then either x+y1 or x-y1 is divisible by 25. Any solutions are then multiplied by 6 to obtain y2 to y7. In the second case, x6 - y16 - y26 must now be divisible by 66 and T = (x6 - y16 - y26)/66 must be the sum of five sixth powers.

Lander, Parkin & Selfridge found the smallest, and currently only known, solution for n = 7:

11416 = 10776 + 8946 + 7026 + 4746 + 4026 + 2346 + 746

Proceeding further, we consider n = 6. The preceding arguments still apply, and we may now additionally use the congruence a6 º 0 or 1 mod 7 so that x and one of the yi are not divisible by 7, but all the others are. We now have five cases to consider: y1 is not divisible by either 2, 3 or 7; y1 is not divisible by either 2 or 3 and y2 is not divisible by 7; y1 is not divisible by either 2 or 7 and y2 is not divisible by 3; y1 is not divisible by either 3 or 7 and y2 is not divisible by 2; y1 is not divisible by 2 and y2 is not divisible by 3 and y3 is not divisible by 7. In the last of these cases, we require that

x6 - y16 - y26 - y36 is divisible by 426 and that T = (x6 - y16 - y26 - y36)/426 is the sum of three sixth powers. We also note that in this case T mod 9, T mod 8 and T mod 7 must all be less than 4. Other restrictions may also be applied, depending on the particular case being considered. Lander, Parkin & Selfridge applied these conditions to a direct search for n = 6 but found no solutions for x up to 38314.

For m = 8, we can use the congruence a8 º 0 or 1 mod 32 and so for any n < 32, x and one of the yi, y1 say, must be odd, x8 - y18 must be divisible by 28, T = (x8 - y18)/28 must be decomposable as the sum of n-1 eighth powers, and that since x8 - y18 = (x+y1).(x-y1).(x2+y12).(x4+y14) and the last two terms here are congruent to 2 mod 4, then, as for m = 6 above, either x+y1 or x-y1 must be divisible by 25. Also, T mod 32 must be less than n. An unrestricted initial search quickly reveals that the equation:

178 = 158 + 168 + 88 + 88 + 88 + 88 + 88 + 88 + 88 + 48 + 48 + 48 + 48 + 48 + 48 + 48 +28

is a solution for n = 17, where the odd yi has been brought to the front to emphasise its importance. From this point on, we may then restrict ourselves to n £ 16 in order to speed up the search. A solution for n = 13 is found at x = 53, and a solution for n = 12 is found at x = 65. Further progress is made by restricting the search to n £ 11, whereupon the following solution is found:

1258 = 938 + 1128 + 1068 + 968 + 928 + 708 + 668 + 448 + 448 + 188 + 148

We can thus say that s(8) £ 11.

In the above treatment, I have left out any explanation of the decomposition stage. This is the only purely computational part of the process, and is one of a set of algorithms I have developed to aid my searches, details of which may be found in Chapter 2. It is basically a direct search and, while being completely deterministic in that if a solution exists it will be found, it is by far the most expensive part of the search, especially for large n. Thus every possible restriction should be sought and applied before committing resources to it.

For m = 7 and 9, the only results available are obtained by an unrestricted direct search. The following equations obtained by Lander, Parkin & Selfridge imply that s(7) £ 8 and s(9) £ 15.

1027 = 907 + 857 + 837 + 647 + 587 + 537 + 357 + 127

269 = 239 + 239 + 219 + 219 + 189 + 159 + 109 + 99 + 99 + 79 + 69 + 69 + 49 + 29 + 29

Notation: Since some of the solutions from now on would otherwise take up several lines to display as straightforward sums of powers, I will often use the notation

(A1 x y1,A2 x y2, ..... ,Ak x yk)m

to denote

y1m + ..... + y1m + y2m + ..... + y2m + .......... + ykm + ..... + ykm

{A1 times} {A2 times} {Ak times}

When Ai = 1, the ‘1x’ may sometimes be left out.

The case m = 10 is less approachable than other even powers as there is no convenient congruence that will help us to restrict the search. The best result that is currently available is that s(10) £ 23, given by the two equations:

1510 = (14,13,12,12,10,9,9,9,9,7,7,7,7,7,7,6,3,2,1,1,1,1,1)10

and

2110 = (19,18,18,17,15,15,13,12,10,10,9,9,9,9,9,8,7,5,5,3,1,1,1)10

For m > 10, the published data is limited. The best way to prepare for direct searches is to obtain a reasonable working limit. This is done by taking each small mth power xm in turn and trying to decompose this into as few smaller mth powers as possible.

Definition: An Euler representation to power m, or in mth powers, is a minimal, in terms of length, representation of a positive integer in terms of a sum of mth powers. When x is an mth power, we consider the sum to be of lesser mth powers.

Definition: The Euler length to power m of a number x is the length of an Euler representation in mth powers, and is denoted by Em(x).

Then s(m) can be redefined as the minimum of Em(xm) over all x > 1.

Although every number has an Euler representation to any power, a fact that will be picked up again in Chapter 7, we are at present only interested in representations of powers by lesser like powers. We also note in passing that the definition of an Euler representation allows the possibility of more than one existing for the same base. These two facts combine to provide us with the following concept.

Definition: A coincidence is a set of Euler representations in mth powers of another mth power which has more than one member. A simple example is

94 = (6,6,6,6,6,3)4 = (8,7,2,2,2,2)4

and a much larger example is

512 = (7x4,238x3,53x2,67x1)12 = (9x4,175x3,35x2,146x1)12 = (11x4,112x3,1x2,225x1)12

with Euler length E12(512) = 365.

A comprehensive list of coincidences can be found in Appendix C.

In an effort to find the value of s(m) for various powers m, or at least to reduce the upper limit on this value, it is appropriate to begin by trying to obtain representations of xm for small bases x as sums of lesser mth powers by unrestricted search and then use the results to restrict the bounds of further search. As an alternative, I have developed a constructive algorithm to find Euler representations. Since this algorithm is recursive, it is possible to build in an early abort strategy that will quicky, in comparison to the full execution time, provide rough limits, some of which may be very tight indeed. Details of the algorithm can be found in the next Chapter, and the results of a comprehensive search for upper estimates may be found in Appendix B. These limits may then be used to restrict search bounds for higher bases. However, occasionally the restricted search will itself be prohibitive in computer resources due to the exact nature of the representation being sought. In this case, it may be possible to use the full recursive algorithm to provide a definite result, as long as the base x is small.

Using the early abort method, and for x up to 20, we obtain the rough limits:

s(11) £ 41; s(12) £ 54; s(13) £ 697; s(14) £ 505; s(15) £ 96

s(16) £ 103; s(17) £ 144; s(18) £ 267; s(19) £ 292; s(20) £ 256

It so happens that this algorithm gives s(10) £ 23, which is the best result currently known for m = 10. Also, it is reasonable, but unproven, conjecture to expect that s(m) < s(m+1). This would improve the bounds for m = 13 and 14 which are inexplicably rather poor.

For m = 11, the unrestricted direct decomposition algorithm applied for n £ 40 quickly locates the solutions

1411 = (4x12,3x11,2x10,2x8,2x7,1x6,1x5,12x4,1x3,9x2,1x1)11

and

1911 = (2x17,2x16,2x14,2x13,3x11,6x9,4x8,1x5,3x4,3x3,8x2,2x1)11

for n = 38, an immediate improvement on the rough estimate given above. The best result at present is n = 31 at x = 25:

2511 = (3x22,3x19,4x18,1x16,3x13,6x11,3x7,3x3,4x2,1x1)11

For m = 12, a length of n = 66 is obtained for x = 10, 12, 14 and 15. In fact, there are two separate solutions (i.e. a coincidence) for n = 66 and x = 12:

1212 = (2x11,2x10,1x9,4x8,2x7,24x6,8x5,3x4,14x3,1x2,5x1)12

and

1212 = (7x10,4x9,8x8,16x7,6x6,8x5,9x4,2x3,4x2,2x1)12

The value of n = 54 suggested by the limit above was estimated for x = 19. In fact, it is attained for x = 16:

1612 = (1x15,1x14,1x13,7x12,2x11,1x10,7x9,3x7,13x6,1x5,16x3,1x1)12

and the first improvement over this is n = 53 at x = 17, with

1712 = (3x15,3x14,1x12,3x11,1x10,14x9,7x6,3x5,7x4,1x2,10x1)12

The best result for m = 12 to date is n = 40 at x = 23:

2312 = (2x21,2x18,4x17,5x16,8x15,2x14,1x8,7x6,1x5,5x4,2x3,1x2)12

For m = 13, the estimated limit above is unsatisfactorily high. A detailed investigation through small powers locates the earliest improvement at n = 605, with

813 = (446x5,78x4,66x3,5x2,21x1)13

and the best result to date at n = 289, with

1613 = (1x14,73x11,97x10,84x9,9x8,13x7,2x5,5x4,1x3,3x2,1x1)13

For m = 14, the estimated limit is also very poor. A detailed study reveals a solution for

n = 490 and x = 10, with

1014 = (5x8,80x7,300x6,39x5,17x4,15x3,8x2,26x1)14

and the best result to date at n = 225, with

1414 = (7x11,63x10,92x9,10x8,7x7,2x6,34x5,3x4,1x3,3x2,3x1)14

For m = 15, improved estimation algorithms can be pushed to higher values of x. The best result available at present is s(15) £ 83.

No improvements over the estimated values have been found as yet by direct search for any higher power.

A list of Euler representations for m £ 16 and x up to 20 may be found in Appendix A1. A more comprehensive list may be accessed via Appendix A2. A summary of Euler lengths for various m and x may be found in Appendix A3.