Equal Sums of Like Powers

    Around late September 1999, I came across Jean-Charles Meyrignac's search for Equal Sums of Like Powers. Intrigued by the idea, I devised a few of my own programs to find such equations and had a good deal of success. Then I left the problem for 6 months or so only to find most of my records were beaten. However, on 9/26/2000, Jean-Charles informed me of a new attack on the problem first proposed by Greg Childers involving the so-called 'Integer Relations' algorithms. I knew NTL implemented LLL (Lenstra-Lenstra-Lovasz) and since I was already familiar with using NTL I quickly (in minutes!) put together a program using it to test its effectiveness. I was amazed at the success! Within hours I took over all the records above the 12th power. Greg Childers has further reduced these solutions. This is a major break-through on this problem. With time we can probably tune the LLL algorithm to outperform all other methods for powers greater than 6.

Another interesting result was being able to find several solutions that hold for multiple powers. For instance the following solution (9,22,22) holds for k=9 as well as k={1,2,3,4,5,6,7,8,9}:

---

(9,22,22):308+310+311*3+315+316*2+317+321*2+324*2+328+329*2+330+334*3+335+337 = 309*3+313+314*4+320*2+322+323+325*2+331*4+332+336*3

---

It is exciting how fast these solutions are found. The (9,22,22) above was found in just a few minutes! Kudos to Greg Childers for pointing out the Equal Sums problem can be turned into an Integer Relation one.

My original strategy

   My original strategy has been what I call 'Fixed-Point Optimal Descent'. I assume the equation I'm looking for has the form 

x^k - (x-a)^k - (x-b)^k ... = F(lhs)

where F(lhs) is the 'optimal descent' representation of the value of the left hand side of the equation. What I do, is make a function to find the optimal (or for speed considerations, greedy/close to optimal) representation of a value as a sum of kth powers. Then, I iterate values of x, and various values for 'a', 'b', etc, for each x, evaluate the lhs then compute its 'optimal descent representation.' If the result doesn't have a small number of terms, we just choose more x, a, b, etc. More on this later...

This is a simple procedure really, but has had a good amount of success. Especially compared to complete iterative methods which don't work well for high powers.

---

I realized that some of the forms of the equations I was after were impossible. Here is a proof I did on a particular form (perhaps you can construct a more simple version).

My proof that x⁴ - (x-1)⁴ = y⁴ + 1, is impossible.

    I took a look into this on 3/15/00 and completed this proof the same day. :) My original interest was whether or not I could construct a (4,1,3) solution of this form.  I might try to make it more general soon using a similar approach. Here's my proof...

Problem Statement: Show that x⁴ - (x-1)⁴ = y⁴ + 1 has no non-trivial integer solutions.

1. Consider the equation x⁴ - (x-1)⁴ = (x-a)⁴ + 1. The two non-complex solutions for 'a' in terms of 'x' are: x +/- (4x³ - 6x² + 4x - 2)^1/4.
2. Let z = 4x³ - 6x² + 4x - 2. This has to be a perfect fourth power in order for 'a' to be integer. E.g. z = H⁴, where H is an integer.
3. First important fact. Any prime divisor of z has to occur a multiple of 4 times, since z = H⁴.
4. Let x = u+1, and you will find that 'z' can be represented as z = 2u(2 + 3u + 2u²). To exclude the trivial solution x=1, y=0, we assume x does not equal 1, and so u is non-zero.
5. Now, you can easily notice that 'u' must be even. For if it was odd, then (2 + 3u + 2u²) would be odd, and so 'z' would only have one prime divisor 2.
6. Let's find out how many twos divide 'u'. Let u = 2^a (2b + 1). That is, a product of some twos and an odd number (All non-zero integers can be represented as such). Using substitution for z = 2u (2 + 3u + 2u²), we see that z = 2^a+2 (2b + 1) (1 + 3*2^a-1 (2b + 1) + u²).
   • Let B equal the expression (1 + 3*2^a-1 (2b + 1) + u²)
   • If a = 1, then B is even and its possible that z contains a multiple of 4 twos.
   • If a = 2 + 4k, then B is odd and since we have 2^a+2 as a factor of z, we definitely have a multiple of 4 twos for this case.
   • If a > 1, and not equal to 2 + 4k, then B is odd and we don't have a multiple of 4 twos (e.g. only numbers of the form 4k+2 added to a+2 construct this).
   So, 2 either divides 'u' only once, or 4k+2 times.
7. Note, that since z = 2u(2 + 3u + 2u²), and z = H⁴, 'u' must have either the form 2d⁴ or 2^4k+2d⁴. This is because any prime divisor of u other than 2, does not divide (2 + 3u + 2u²). So, since z = H⁴, those divisors must occur in multiples of 4.
8. We can eliminate the case where 2 only divides 'u' once. For if u = 2d⁴, z = 4d⁴ (2 + 6d⁴ + 8d⁸) = 16d⁴ ((1+3d⁴)/2 + 2d⁸). Since z = H⁴, (1+3d⁴)/2 + 2d⁸ = (H/2d)⁴. Representing d = 2h + 1, since d is odd, we have (1+3d⁴)/2 + 2d⁸ = 4*(1+5h+13h²+16h³+8h⁴)*(1+6h+22h²+32h³+16h⁴). Whether or not h is odd or even, the two polynomial factors are odd and thus this expression contains only 2 twos. It cannot be a fourth power, so 2 must divide 'u' 4k+2 times instead. I.e. 2^4k+2 | u.
9. But, we can also eliminate the only remaining case, where 2 divides 'u' (4k+2) times as follows. Represent u = 2^4k+2 d⁴. Which can be simplified to just u = 4c⁴. Substituting into z, we have z = 16c⁴ (1 + 6c⁴ + 16c⁸), which must equal H⁴. So, 1 + 6c⁴ + 16c⁸ = (H/2c)⁴. Using 'G' as the expression 1 + 6c⁴ + 16c⁸, G > 16c⁸, so G^1/4 > 2c². But, since G < (2c²+1)⁴, G^1/4 < 2c²+1. There are no integers between 2c² and 2c²+1, so G can never be a fourth power.
10. This concludes the proof as (8) & (9) contradict (6).

[[1, 0, 0, 0, 0, 1^k]
 [0, 1, 0, 0, 0, 2^k]
 [0, 0, 1, 0, 0, 3^k]
 [0, 0, 0, 1, 0, 4^k]
 [0, 0, 0, 0, 1, 5^k]]

   [[1, 0, 0, 0, 0, 1^4]
    [0, 1, 0, 0, 0, 2^4]
    [0, 0, 1, 0, 0, 3^4]
    [0, 0, 0, 1, 0, 4^4]
    [0, 0, 0, 0, 1, 5^4]]

   [[ 1,  0,  0,  0,  0,  1]
    [ 0, -2, -1, -2,  1,  0]
    [ 2, -1, -3,  1,  0, -1]
    [ 0, -3,  2,  2, -1,  1]
    [-5, -1, -6,  2,  0,  5]]

   1*1 = 1   (trivial)
   0*1 - 2*24 - 1*34 - 2*44 + 1*54 = 0
   2*1 - 1*24 - 3*34 + 1*44 + 0*54 = -1
   0*1 - 3*24 + 2*34 + 2*44 - 1*54 = 1
  -5*1 - 1*24 - 6*34 + 2*44 + 0*54 = 5