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 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^{3} = 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 x^{4} - 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_{1}+y_{1}^{2}).(x^{2}-xy_{1}+y_{1}^{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_{2}^{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_{1}^{2}).(x^{4}+y_{1}^{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_{i} 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.

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.

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}

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

(A_{1} x y_{1},A_{2} x y_{2}, ..... ,A_{k} x y_{k})^{m}

to denote

y_{1}^{m} + ..... + y_{1}^{m} + y_{2}^{m} + ..... + y_{2}^{m} + .......... + y_{k}^{m} + ..... + y_{k}^{m}

{A_{1} times} {A_{2} times} {A_{k} times}

When A_{i} = 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:

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}

and

21^{10} = (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 x^{m} 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 E_{m}(x).

Then s(m) can be redefined as the minimum of E_{m}(x^{m}) 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

9^{4} = (6,6,6,6,6,3)^{4} = (8,7,2,2,2,2)^{4}

and a much larger example is

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

with Euler length E_{12}(5^{12}) = 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 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 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

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 result at present is n = 31 at x = 25:

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

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

and

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

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 to date is n = 40 at x = 23:

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

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

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

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

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

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

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