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:

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³ + 4³ + 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⁴ = 315⁴ + 272⁴ + 120⁴ + 30⁴

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

T = (x⁴ - y₁⁴)/10⁴ 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⁴ - y₁⁴ - y₂⁴ must actually be a fourth power. An additional argument due to Ward (see [26]) requires that either x+y₁ or x-y₁ must be divisible by 2¹⁰. 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⁴ = 18796760⁴ + 15365639⁴ + 2682440⁴

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⁴ = 414560⁴ + 217519⁴ + 95800⁴

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⁵ = 133⁵ + 110⁵ + 84⁵ + 27⁵

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⁵ = 67⁵ + 47⁵ + 46⁵ + 43⁵ + 19⁵

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⁶ º 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₁ say, not divisible by 3, and all others divisible by 3. We may then restrict a direct search over x and y₁ such that x⁶ - y₁⁶ is divisible by 3⁶ and then try to decompose T = (x⁶ - y₁⁶)/3⁶ as the sum of seven sixth powers. If such a decomposition is found, we multiply each value by 3 to obtain y₂ to y₈. In this way, Lander, Parkin & Selfridge [14] found the smallest solution for n = 8:

251⁶ = 246⁶ + 165⁶ + 138⁶ + 102⁶ + 78⁶ + 30⁶ + 12⁶ + 8⁶

Restricting to n = 7, we can also use the congruence a⁶ º 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₁ is odd, or another y_i, y₂ say, is odd. In the first case, x⁶ - y₁⁶ must now be divisible by 6⁶ and we try to decompose T = (x⁶ - y₁⁶)/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⁶ - y₁⁶ = (x+y₁).(x-y₁).(x²+xy+y²).(x²-xy+y²) and the last two terms here cannot be divisible by 2, then either x+y₁ or x-y₁ is divisible by 2⁵. Any solutions are then multiplied by 6 to obtain y₂ to y₇. In the second case, x⁶ - y₁⁶ - y₂⁶ must now be divisible by 6⁶ and T = (x⁶ - y₁⁶ - y₁⁶)/6⁶ must be the sum of five sixth powers.

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

1141⁶ = 1077⁶ + 894⁶ + 702⁶ + 474⁶ + 402⁶ + 234⁶ + 74⁶

Proceeding further, we consider n = 6. The preceding arguments still apply, and we may now additionally use the congruence a⁶ º 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₁ is not divisible by either 2, 3 or 7; y₁ is not divisible by either 2 or 3 and y₂ is not divisible by 7; y₁ is not divisible by either 2 or 7 and y₂ is not divisible by 3; y₁ is not divisible by either 3 or 7 and y₂ is not divisible by 2; y₁ is not divisible by 2 and y₂ is not divisible by 3 and y₃ is not divisible by 7. In the last of these cases, we require that

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

17⁸ = 15⁸ + 16⁸ + 8⁸ + 8⁸ + 8⁸ + 8⁸ + 8⁸ + 8⁸ + 8⁸ + 4⁸ + 4⁸ + 4⁸ + 4⁸ + 4⁸ + 4⁸ + 4⁸ +2⁸

is a solution for n = 17, where the odd y₁ 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⁸ = 93⁸ + 112⁸ + 106⁸ + 96⁸ + 92⁸ + 70⁸ + 66⁸ + 44⁸ + 44⁸ + 18⁸ + 14⁸

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⁸ = 226⁸ + 184⁸ + 171⁸ + 152⁸ + 142⁸ + 66⁸ + 58⁸ + 34⁸ + 16⁸ + 6⁸

and later, a further improvement with n = 9 :

1167⁸ = 1094⁸ + 1040⁸ + 560⁸ + 558⁸ + 366⁸ + 348⁸ + 284⁸ + 271⁸ + 190⁸

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

1409⁸ = 1324⁸ + 1190⁸ + 1088⁸ + 748⁸ + 524⁸ + 478⁸ + 223⁸ + 90⁸

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

102⁷ = 90⁷ + 85⁷ + 83⁷ + 64⁷ + 58⁷ + 53⁷ + 35⁷ + 12⁷

26⁹ = 23⁹ + 23⁹ + 21⁹ + 21⁹ + 18⁹ + 15⁹ + 10⁹ + 9⁹ + 9⁹ + 7⁹ + 6⁹ + 6⁹ + 4⁹ + 2⁹ + 2⁹

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⁷ = 525⁷ + 439⁷ + 430⁷ + 413⁷ + 266⁷ + 258⁷ + 127⁷

103⁹ = 91⁹ + 91⁹ + 89⁹ + 71⁹ + 68⁹ + 65⁹ + 43⁹ + 42⁹ + 19⁹ + 16⁹ + 13⁹ + 5⁹

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¹⁰ = (14, 13, 12, 12, 10, 9, 9, 9, 9, 7, 7, 7, 7, 7, 7, 6, 3, 2, 1, 1, 1, 1, 1)¹⁰

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¹⁰ = (2x30, 2x26, 23, 21, 19, 18, 2x13, 2x12, 5x10, 2x9, 7, 6, 3)¹⁰

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

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

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

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

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

228¹⁰ = (210, 204, 187, 179, 128, 122, 85, 73, 59, 57, 49, 13, 6)¹⁰

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

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

and

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

for n = 38, an immediate improvement on the rough estimate given above. The best early result obtained is

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

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

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

and

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

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¹² = (1x15, 1x14, 1x13, 7x12, 2x11, 1x10, 7x9, 3x7, 13x6, 1x5, 16x3, 1x1)¹²

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

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

The best result for m = 12 that I obtained is n = 40 at x = 23:

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

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

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

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¹³ = (446x5, 78x4, 66x3, 5x2, 21x1)¹³

The best result found I found prior to using Euler2000 was

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

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

990¹³ = (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)¹³

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¹³ = (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)¹³

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¹⁴ = (5x8,80x7,300x6,39x5,17x4,15x3,8x2,26x1)¹⁴

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

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

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

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

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¹⁴ = (2x43,42,40,2x37,35,2x34,32,2x24,18,2x16,15,5x14,12,3x11,2x10,9,2x7,3x5,4x4,3,1)¹⁴

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

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

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

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

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

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

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

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

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

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

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

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

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.

URL : www.glasgowg43.freeserve.co.uk/chap1new.htm