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:

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 x⁴ - 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_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⁸ = 93⁸ + 112⁸ + 106⁸ + 96⁸ + 92⁸ + 70⁸ + 66⁸ + 44⁸ + 44⁸ + 18⁸ + 14⁸

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⁷ = 90⁷ + 85⁷ + 83⁷ + 64⁷ + 58⁷ + 53⁷ + 35⁷ + 12⁷

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

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₁ x y₁,A₂ x y₂, ..... ,A_k x y_k)^m

to denote

y₁^m + ..... + y₁^m + y₂^m + ..... + y₂^m + .......... + y_k^m + ..... + y_k^m

{A₁ times} {A₂ 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¹⁰ = (14,13,12,12,10,9,9,9,9,7,7,7,7,7,7,6,3,2,1,1,1,1,1)¹⁰

and

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

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⁴ = (6,6,6,6,6,3)⁴ = (8,7,2,2,2,2)⁴

and a much larger example is

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

with Euler length E₁₂(5¹²) = 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¹¹ = (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 result at present is n = 31 at x = 25:

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

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¹² = (2x11,2x10,1x9,4x8,2x7,24x6,8x5,3x4,14x3,1x2,5x1)¹²

and

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

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

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

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

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

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

For m = 14, the estimated limit is also very poor. 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 to date at n = 225, with

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

 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.

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