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 x^{2} + y^{2} = z^{2} may be obtained from setting x = 2st, y = s^{2} - t^{2},

z = s^{2} + t^{2} 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 = 5^{3} + 4^{3} + 3^{3}, 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

353^{4} = 315^{4} + 272^{4} + 120^{4} + 30^{4}

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 a^{4} º 0 or 1 mod 16 and a^{4} º 0 or 1 mod 5 implies that a primitive solution for n = 3 requires that x and one of the y_{i}, y_{1} say, are odd and that x and one of the y_{i} are not divisible by 5. There are two cases, either y_{1} is not divisible by 5 or one of the other y_{i}, y_{2} say, is not divisible by 5. In the first case a direct search can then be restricted to locating x and y_{1} satisfying these conditions and such that x4 - y_{1}^{4} is divisible by 10^{4}, and then attempting to decompose

T = (x^{4} - y_{1}^{4})/10^{4} 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, x^{4} - y_{1}^{4} - y_{2}^{4} must actually be a fourth power. An additional argument due to Ward (see [26]) requires that either x+y_{1} or x-y_{1} must be divisible by 2^{10}. 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:

20615673^{4} = 18796760^{4} + 15365639^{4} + 2682440^{4}

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:

422481^{4} = 414560^{4} + 217519^{4} + 95800^{4}

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:

144^{5} = 133^{5} + 110^{5} + 84^{5} + 27^{5}

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:

72^{5} = 67^{5} + 47^{5} + 46^{5} + 43^{5} + 19^{5}

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 a^{6} º 0 or 1 mod 9, in order to obtain a primitive solution for n = 8 we must have x and one of the y_{i}, y_{1} say, not divisible by 3, and all others divisible by 3. We may then restrict a direct search over x and y_{1} such that x^{6} - y_{1}^{6} is divisible by 3^{6} and then try to decompose T = (x^{6} - y_{1}^{6})/3^{6} as the sum of seven sixth powers. If such a decomposition is found, we multiply each value by 3 to obtain y_{2} to y_{8}. In this way, Lander, Parkin & Selfridge [14] found the smallest solution for n = 8:

251^{6} = 246^{6} + 165^{6} + 138^{6} + 102^{6} + 78^{6} + 30^{6} + 12^{6} + 8^{6}

Restricting to n = 7, we can also use the congruence a^{6} º 0 or 1 mod 8, so that x and one of the y_{i} must be odd. We now have two cases, since the above argument modulo 9 still holds, and so either y_{1} is odd, or another y_{i}, y_{2} say, is odd. In the first case, x^{6} - y_{1}^{6} must now be divisible by 6^{6} and we try to decompose T = (x^{6} - y_{1}^{6})/6^{6} 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

x^{6} - y_{1}^{6} = (x+y_{1}).(x-y_{1}).(x^{2}+xy+y^{2}).(x^{2}-xy+y^{2}) and the last two terms here cannot be divisible by 2, then either x+y_{1} or x-y_{1} is divisible by 2^{5}. Any solutions are then multiplied by 6 to obtain y_{2} to y_{7}. In the second case, x^{6} - y_{1}^{6} - y_{2}^{6} must now be divisible by 6^{6} and T = (x^{6} - y_{1}^{6} - y_{1}^{6})/6^{6} must be the sum of five sixth powers.

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

1141^{6} = 1077^{6} + 894^{6} + 702^{6} + 474^{6} + 402^{6} + 234^{6} + 74^{6}

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

x^{6} - y_{1}^{6} - y_{2}^{6} - y_{3}^{6} is divisible by 42^{6} and that T = (x^{6} - y_{1}^{6} - y_{2}^{6} - y_{3}^{6})/42^{6} 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 a^{8} º 0 or 1 mod 32 and so for any n < 32, x and one of the y_{i}, y_{1} say, must be odd, x^{8} - y_{1}^{8} must be divisible by 2^{8}, T = (x^{8} - y_{1}^{8})/2^{8} must be decomposable as the sum of n-1 eighth powers, and that since x^{8} - y_{1}^{8} = (x+y_{1}).(x-y_{1}).(x^{2}+y^{2}).(x^{4}+y^{4}) and the last two terms here are congruent to 2 mod 4, then, as for m = 6 above, either x+y_{1} or x-y_{1} must be divisible by 2^{5}. Also, T mod 32 must be less than n. An unrestricted initial search quickly reveals that the equation:

17^{8} = 15^{8} + 16^{8} + 8^{8} + 8^{8} + 8^{8} + 8^{8} + 8^{8} + 8^{8} + 8^{8} + 4^{8} + 4^{8} + 4^{8} + 4^{8} + 4^{8} + 4^{8} + 4^{8} +2^{8}

is a solution for n = 17, where the odd y_{1} 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 :

125^{8} = 93^{8} + 112^{8} + 106^{8} + 96^{8} + 92^{8} + 70^{8} + 66^{8} + 44^{8} + 44^{8} + 18^{8} + 14^{8}

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 x^{m} 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 :

235^{8} = 226^{8} + 184^{8} + 171^{8} + 152^{8} + 142^{8} + 66^{8} + 58^{8} + 34^{8} + 16^{8} + 6^{8}

and later, a further improvement with n = 9 :

1167^{8} = 1094^{8} + 1040^{8} + 560^{8} + 558^{8} + 366^{8} + 348^{8} + 284^{8} + 271^{8} + 190^{8}

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

1409^{8} = 1324^{8} + 1190^{8} + 1088^{8} + 748^{8} + 524^{8} + 478^{8} + 223^{8} + 90^{8}

For m = 7 and 9, the following equations obtained by Lander, Parkin & Selfridge imply that s(7) £ 8 and s(9) £ 15.

102^{7} = 90^{7} + 85^{7} + 83^{7} + 64^{7} + 58^{7} + 53^{7} + 35^{7} + 12^{7}

26^{9} = 23^{9} + 23^{9} + 21^{9} + 21^{9} + 18^{9} + 15^{9} + 10^{9} + 9^{9} + 9^{9} + 7^{9} + 6^{9} + 6^{9} + 4^{9} + 2^{9} + 2^{9}

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.

568^{7} = 525^{7} + 439^{7} + 430^{7} + 413^{7} + 266^{7} + 258^{7} + 127^{7}

103^{9} = 91^{9} + 91^{9} + 89^{9} + 71^{9} + 68^{9} + 65^{9} + 43^{9} + 42^{9} + 19^{9} + 16^{9} + 13^{9} + 5^{9}

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

15^{10} = (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

33^{10} = (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

108^{10} = (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

120^{10} = (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 :

228^{10} = (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

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

and

19^{11} = (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

25^{11} = (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 :

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

and

78^{11} = (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:

16^{12} = (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

17^{12} = (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:

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

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

52^{12} = (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

8^{13} = (446x5, 78x4, 66x3, 5x2, 21x1)^{13}

The best result found I found prior to using Euler2000 was

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

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

990^{13} = (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

1838^{13} = (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

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

and the best result I found was for n = 225, with

14^{14} = (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 :

38^{14} = (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:

47^{14} = (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

17^{15} = (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

25^{15} = (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 :

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

50^{15} = (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

20^{16} = (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

32^{16} = (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.