20
$\begingroup$

I was stunned when I first saw the article Counterexample to Euler's conjecture on sums of like powers by L. J. Lander and T. R. Parkin:.

enter image description here

How was it possible in 1966 to go through the sheer astronomical space of possibilities, on a CDC 6600 computer?

1) Did Lander and Parkin reveal their strategy?

2) How would you, using all the knowledge that was accessable until 1965, go to search for counter-examples, if you have access to a computer with 3 MegaFLOPS?

(As a comparison, todays home computers can have beyond 100 GigaFLOPS, using GPUs even TeraFLOPs)

$\endgroup$
  • 4
    $\begingroup$ I would compute a table of fifth powers (say 200 entries), then a table of sums of two fifth powers (say 20000 entries), and then do a search (say 2*10^8 tries). If I felt like using number theory I could eliminate some cases with considerations mod 5. Gerhard "Not Quite Pencil And Paper" Paseman, 2019.03.11. $\endgroup$ – Gerhard Paseman Mar 11 at 16:47
  • $\begingroup$ open access projecteuclid.org/euclid.bams/1183528522 $\endgroup$ – Will Jagy Mar 11 at 17:09
  • 1
    $\begingroup$ There appear to be some tidbits on how these sorts of searches are done in a 1967 paper: L. J. Lander, T. R. Parkin and J. L. Selfridge, A Survey of Equal Sums of Like Powers, Mathematics of Computation 21 (1967) 447-459 - ams.org/journals/mcom/1967-21-099/S0025-5718-1967-0222008-0/… The authors don't seem to specifically address the fifth-power case. $\endgroup$ – Michael Lugo Mar 11 at 18:56
  • $\begingroup$ With today's computers, one could try $a\le b\le c\le d\le 1024.\ $ Did anybody? $\endgroup$ – Wlod AA Mar 13 at 0:08
21
$\begingroup$

The search strategy is laid out in a paper devoted to finding all "small" non-negative solutions of $$x_1^5+\cdots x_n^5=y^5\text{ with }n \leq 6$$

L. Lander & T. Parkin, "A counterexample to Euler's sum of powers conjecture," Math. Comp., v. 21, 1967, pp. 101-103.

The one result was striking enough grab the title and get separate mention in the Bulletin.

The search was carried out for

  • $n=6$ and $y \leq 100$ turning up $10$ primitive solutions of which two had $n=5$
  • $n=5$ and $y \leq 250$ turning up $3$ more including the unexpected one for $n=4$
  • $n=4$ and $y \leq 750$ turning up nothing else new.

That last search covers more than $5000$ times as many cases as going to $133^5.$

The length of the paper hints that the method is fairly simple. Space must have been limited because a table of fifth powers was maintained but not a table of sums $a^5+b^5$ for a meet in the middle attack.

$\endgroup$
16
$\begingroup$

Even simply generating all quadruples $(a, b, c, d)$ with $1 \le a \le b \le c \le d \le 133$ should work fine. There are only about 13 million such quadruples. For each, we need to add together the fifth powers (which can be looked up in a small table) and check whether the result is another fifth power, which we can do by binary search in a table of fifth powers (of size, say, 200 or so). I'm not familiar with the CDC 6600 but it seems like a direct implementation of this kind would finish in under an hour.

There are faster algorithms possible, using the "meet-in-the-middle" method. For example, record all the sums $a^5 + b^5$ for $1 \le a \le b \le 200$ or so, and sort them. Now, for each $1 \le c \le d \le e$, compute $e^5 - c^5 - d^5$ and check whether it is in this table. This algorithm is cubic (up to log factors) in the size of the eventual counterexample, rather than quartic. However, the actual counterexample in this case is small enough that this kind of method seems to be unnecessary.

$\endgroup$
  • $\begingroup$ The fact that the authors say they used "direct search" and don't elaborate suggests, to me, that they didn't do anything fancy, and probably used this approach. $\endgroup$ – Michael Lugo Mar 11 at 18:50
  • 6
    $\begingroup$ One could easily gain a constant factor of 2ish by noting, for example, that all 5th powers are in $\{-1,0,1\}$ modulo $11$; this rules out lots of possible quadruples. $\endgroup$ – Greg Martin Mar 11 at 22:17
  • 1
    $\begingroup$ Using $x^5=x /bmod 30$ gives a constant factor of $30.$ $\endgroup$ – Aaron Meyerowitz Mar 12 at 7:27

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.