Chapter 1

Euler's Conjecture

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 6 = 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+xy+y2).(x2-xy+y2) 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 - y16)/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+y2).(x4+y4) 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 y1 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.

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. The Euler length to power m is the length of an Euler representation to power m.

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. 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 quickly, 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 Chapter 2, and the results of a comprehensive search for upper estimates may be found in Appendix B1 and Appendix B4. These limits may then be used to restrict search bounds for higher bases.

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

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

In recent years, a number of other individuals have been working to improve on the early results of Lander, Parkin & Selfridge. These include Jean-Charles Meyrignac, who developed the Windows program Euler2000 and its predecessor Sum95 for use by anyone who can download from the Internet, and Nuuti Kuosa, who found the first improvement over the above result for m = 8, with n = 10 :

2358 = 2268 + 1848 + 1718 + 1528 + 1428 + 668 + 588 + 348 + 168 + 68

and later, a further improvement with n = 9 :

11678 = 10948 + 10408 + 5608 + 5588 + 3668 + 3488 + 2848 + 2718 + 1908

However, the best result available was obtained by Scott Chase but not published until recently, giving s(8) £ 8 :

14098 = 13248 + 11908 + 10888 + 7488 + 5248 + 4788 + 2238 + 908

For m = 7 and 9, 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

However, the following equations were obtained by Dodrill and Meyrignac respectively using Meyrignac's programs and imply that s(7) £ 7 and s(9) £ 12.

5687 = 5257 + 4397 + 4307 + 4137 + 2667 + 2587 + 1277

1039 = 919 + 919 + 899 + 719 + 689 + 659 + 439 + 429 + 199 + 169 + 139 + 59

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 first early result of use is

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

giving s(10) £ 23. This was for a long time the best result available. However, pushing x a bit higher using Euler2000, we reach

3310 = (2x30, 2x26, 23, 21, 19, 18, 2x13, 2x12, 5x10, 2x9, 7, 6, 3)10

giving s(10) £ 22. More recently, Meyrignac has used his method to obtain

10810 = (100, 94, 91, 77, 77, 76, 63, 62, 52, 45, 35, 33, 16, 10, 1)10

and Torbjörn Alm, using Meyrignac's program, found

12010 = (115, 104, 91, 80, 80, 74, 63, 55, 40, 35, 33, 13, 10, 5)10

giving s(10) £ 14. However, again Scott Chase provides the current best s(10) £ 13 with :

22810 = (210, 204, 187, 179, 128, 122, 85, 73, 59, 57, 49, 13, 6)10

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 early result obtained is

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

giving s(11) £ 31. Using Meyrignac's programs, Luigi Morelli found the current best results for length n = 19 and n = 16 :

6911 = (3x62, 50, 48, 46, 45, 42, 2x38, 20, 19, 16, 15, 8, 2x7, 2x6)11

and

7811 = (71, 69, 66, 64, 63, 52, 47, 43, 29, 2x23, 22, 14, 12, 7, 1)11

For m = 12, a length of n = 66 is obtained for x = 10, 12, 14 and 15.

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 that I obtained is n = 40 at x = 23:

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

and the current best is s(12) £ 26, obtained by Meyrignac :

5212 = (50, 2x43, 42 ,41, 2x35 ,2x33, 2x32, 2x31, 25, 4x23, 18, 16, 14, 12, 11, 10, 9, 6)12

For m = 13, the estimated limit above is unsatisfactorily high, and in general this exponent is reluctant to submit to computation. A detailed investigation through small powers locates the earliest improvement at n = 605, with

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

The best result found I found prior to using Euler2000 was

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

giving s(13) £ 289 (although the Euler length for 1613 is actually 279). Kevin O'Hare provided s(13) £ 36 using Meyrignac :

99013 = (989, 709, 423, 305, 225, 157, 119, 98, 73, 52, 45, 2x37, 2x36, 31, 30, 28, 27, 25, 4x24, 2x22, 20, 16, 2x15, 9, 2x7, 3x3)13

This was found using a feature of Meyrignac's programs that allows each base value in a specified range to be checked for a specified duration, with the position at the emd of each pass stored on disc. Any solution found results in the upper bound being reduced. Gradually, solutions are found for shorter and shorter lengths, and the hope is that with the random nature of solutions, this process will home in on the shortest solutions more quickly that exhaustively checking every base in turn.

More recently, Joe Crump, using his own method (for more details on which, see below), found

183813 = (1833, 1418, 1021, 769, 635, 436, 264, 195, 145, 110, 72, 61, 50, 44, 39, 34, 29, 24, 20, 14, 14, 12, 9, 8, 6, 6, 6, 5, 5, 4, 4, 3, 3)13

giving s(13) £ 33.

For m = 14, the estimated limit is also very poor, but in general this is not as bad as m = 13 to investigate. 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 I found was for n = 225, with

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

It turns out that the Euler length for x = 14 is actually 223. However, using Meyrignac, Frank Clowes found :

3814 = (2x35,4x31,2x30,29,28,4x26,2x25,22,2x21,20,2x18,17,2x14,3x13,2x12,9,8,7x4,2)14

giving s(14) £ 40.

For the higher powers, new methods of finding solutions have recently been developed by borrowing from linear algebra and vector space theory, which has a large body of available software. The general method is to construct and then reduce a sparse matrix and then extract solutions or combine near solutions, Initially, Joe Crump used the LLL (Lenstra-Lenstra-Lovasz) algorithm, available as part of the NTL number theory package. Greg Childers then used the PARI-GP version of the same algorithm before moving to the NTL version of the BKZ (block Korkin-Zolotarev) lattice reduction algorithm.

For n = 14, Greg Childers found the current best result s(14) £ 39:

4714 = (2x43,42,40,2x37,35,2x34,32,2x24,18,2x16,15,5x14,12,3x11,2x10,9,2x7,3x5,4x4,3,1)14

For m = 15, improved estimation algorithms can be pushed to higher values of x. The first Euler representation shorter than 100 is

1715 = (16,3x15,14,11x12,16x11,3x10,3x9,8x8,8x7,3x6,5,2x4,6x3,9x2,2x1)15

giving s(15) £ 77. A significant early improvement is

2515 = (24,23,2x21,19,18,16,3x14,2x12,11,2x10,5x9,7,3x5,5x4,3x3,6x2+14x1)15

giving s(15) £ 52. However, the current best are :

3015 = (8x26,2x23,2x22,21,3x19,18,2x16,15,4x14,5x11,2x10,2x9,7,5x6,2x5,4,2*2,3x1)15

5015 = (49, 45, 40, 37, 35, 3x31, 4x30, 2x28, 2x26, 3x24, 18, 17, 16, 2x14, 13, 3x11, 2x10, 2x8, 2x6, 3x5, 4x3, 2x2, 3x1)15

with n = 47 and n = 46 respectively, found by Kuosa.

For m = 16, the first Euler representation shorter than 100 is

2016 = (10x17,7x16,3x15,5x14,13*13,8x11,4x9,8,4x7,14x6,8x5,2x4,14x3,3x2)16

giving s(16) £ 96. The current best, also found by Kuosa, is

3216 = (31,30,25,2x23,22,8x21,2x19,8x17,2x16,3x15,14,8x13,5x12,11,10,21x9,2x6,5x5,3x3,1)16

giving s(16) £ 77.

Prior to the explosion of new results obtained using the lattice reduction algorithms, I used the estimation algorithm specifically in an attempt to obtain explicit solutions for high powers. This is explained in greater detail in Appendix B4, and provided the following results :

s(23) £ 434 ; s(26) £ 869 ; s(27) £ 1059 ; s(28) £ 1975

s(29) £ 3989 ; s(31) £ 11265 ; s(32) £ 6038

However, the current records are

s(17) £ 59; s(18) £ 60; s(19) £ 77; s(20) £ 87

s(21) £ 93 ; s(22) £ 95 ; s(23) £ 105; s(24) £ 156

s(25) £ 189 ; s(26) £ 201; s(27) £ 182; s(28) £ 217

s(29) £ 281 ; s(30) £ 312 ; s(31) £ 339 ; s(32) £ 342

These results were obtained by Fumitaka Yura and Torbjorn Alm using Childers approach.

A list of Euler representations for base x up to 20 and power m up to 16 is available in Appendix A1. A comprehensive list of results for all powers may be found in Appendix A2.