From elkies@abel.MATH.HARVARD.EDUTue Jul  9 23:46:59 1996
Date: Tue, 9 Jul 1996 16:54:56 -0400
From: Noam Elkies <elkies@abel.MATH.HARVARD.EDU>
To: Multiple recipients of list NMBRTHRY <NMBRTHRY@listserv.nodak.edu>
Subject: x^3 + y^3 + z^3 = d

Representing an integer d as a sum x^3+y^3+z^3 of three integer cubes
is a long-standing problem.  It is known that this cannot be done for
d congruent to 4,5 mod 9 (clearly) or d=0 (Euler); there are infinitely
many polynomial solutions whenever d is a cube, and finitely many when
d is twice a cube, e.g. the only known polynomial solution for d=2 is
(x,y,z)=(1+6t^3+1,1-6t^3,-6t^2) [with permutations of x,y,z or changes
of variable in t consider to be the same].  There are no analytic
results for any other d, though the usual heuristics suggest that
given d (not 4 or 5 mod 9) solutions should occur infinitely often,
but rarely, with asymptotically c*log(N) solutions in |x|,|y|,|z|<N.
[This conjecture is made in the paper of Conn and Vaserstein cited in
the next paragraph; it should also apply when d is twice a cube once
the parametric solutions are discarded.]

In the absence of theoretical understanding, we accumulate numerical
data.  Richard Guy's _Unsolved Problems in Number Theory_ includes this
problem in D5 (p.84), and refers to a paper of V.L. Gardiner, R.B.
Lazarus, and P.R.Stein in Math. of Computation 1964, reporting on an
exhaustive search for solutions up to N=2^16, which extended an earlier
computation of JMP Miller and MFC Woolett with N=3200 (J.LMS 1955).
They found solutions for all but 78 of the d<10^3 not of the form 9k+4
or 9k+5, and also indicated eleven other d of the form a^3*d' (a>1)
whose only known representations came from representations of d' by
scaling, and several d for which only one representation was known,
e.g. 12 = 7^3 + 10^3 - 11^3.  R.Guy wrote with more recent references:
W.Conn and L.N.Vaserstein (in "The Rademacher Legacy to Mathematics",
Contemp.  Math. 166 (1994)) and D.R.Heath-Brown, W.M.Lioen and H.J.J.
te Riele (Math.Comput.1993) found several new solutions, including

   2 = 1214928^3 + 3480205^3 - 3528875^3

(the first one not accounted for by the above polynomial) and

  39 = 117367^3 + 134476^3 - 159380^3

(39 was the third-smallest unknown value of d, the first two being
30 and 33), and more recently (mid-1995) Richard F. Lukes found
several new solutions such as

 110 = 109938919^3 + 16540290030^3 - 16540291649^3

with x,y,z rather large but y+z small.  The methods were:

1) Extending the exhaustive search for small values of x^3+y^3=z^3,
which takes time N^2 (ignoring logarithms) and logarithmic space;

2) For specific d, solve for each potential value of y+z the congruence
x^3 == d mod y+z  and search over x satisfying this congruence.  This
takes time N, and can also efficiently find larger solutions such as
Lukes' above with y+z small, but only gets solutions for one d at a
time and in practice requires more space (to sieve over y+z) and,
at least as implement by Heath-Brown et al., auxiliary conditions
on the arithmetic of Q(cbrt(d)).

Some weeks ago I realized that it is possible to find all solutions of
|x^3+y^3+z^3|<<|x|+|y|+|z|<<N also in heuristically expected time
N^(1+epsilon), which is almost as good as one can hope for since one
expects about N solutions.  Moreover the algorithm generalizes to
any smooth ternary cubic form P(x,y,z), whereas (2) above requires
P to have a special form that "happens" to contain x^3+y^3+z^3.
Essentially the idea is as follows:

As usual it is enough to find solutions with the largest coordinate
in [N,2N].  The condition that P(x,y,z) << N  then means that the
rational point (x:y:z) in P^2 is close to the curve P=0, in fact at
distance O(1/N^2).  So split the curve into N segments [i.e. specify
one of the ratios x:y, x:z etc. to within O(1/N)], and replace each
one by its tangent line; since the segment has length O(1/N) the
tangent approximates it to within O(1/N^2) and it is enough to find
rational points at that distance from the corresponding segment
of the tangent line.  But this is just a linear approximation problem:
in effect we're looking for all integer points (x,y,z) in a sheared box
of dimensions O(N) by O(1) by O(1/N).  By lattice reduction we readily
find them all, and expect only O(N^epsilon) per box on the average;
we then try all O(N^1+epsilon) candidates (x:y:z), and retain those
for which P(x,y,z) is an acceptably small multiple of N (in fact I
retained only those for which it is less than sqrt(N) or, for N<10^6,
in [-1000,1000]).

Naturally there are further improvements that enhance the practical
performance of the algorithm without substantially changing its
asymptotic behavior; e.g. in the lattice reduction, start from the
transformation that worked for the previous box rather than start
from scratch, and exploit the linear approximation to rule out most
candidates for |P(x,y,z)|<max(1000,sqrt(N)) before computing P(x,y,z)
in 64- or 96-bit arithmetic.  Of course for x^3+y^3+z^3 we can use
the S_3 symmetry to save a factor of 6: try only (x,y,z) with
0 <= x <= y <= -z.  Note too that the computation takes only
logarithmic space, and is readily parallelized by parceling out
different chunks of the curve to different processors, which
need not communicate with each other.

I implemented this in gp and ran it on one of our department's
machines, reaching N=10^7 in about a week.  This yielded solutions
for fourteen new values of d:

    143 = 7023^3 + 84942^3 - 84958^3
    180 = 223403^3 + 441721^3 - 460002^3
   -231 = 344065^3 + 711814^3 - 737660^3
    312 = 234734^3 + 268952^3 - 318760^3
   -321 = 66319^3 + 321142^3 - 322082^3
    321 = 1884818^3 + 4294529^3 - 4412290^3
   -367 = 117360^3 + 857002^3 - 857735^3
    367 = 2085815^3 + 3229419^3 - 3496723^3
   -439 = 211402^3 + 382489^3 - 402906^3
        = 869418^3 + 2281057^3 - 2322404^3
    439 = 264488^3 + 331574^3 - 380193^3
   -462 = 1024946^3 + 1832411^3 - 1933609^3
    462 = 1612555^3 + 2598019^3 - 2790488^3
    516 = 87856^3 + 130585^3 - 142685^3
    542 = 1645813^3 + 3654604^3 - 3762639^3
   -542 = 47673^3 + 207056^3 - 207895^3
        = 2920907^3 + 3887474^3 - 4373769^3
   -660 = 159116^3 + 199163^3 - 228487^3
   -663 = 105841^3 + 1068592^3 - 1068938^3
   -754 = 238441^3 + 253285^3 - 310050^3
        = 789785^3 + 1029653^3 - 1165759^3
   -777 = 1005823^3 + 3912759^3 - 3934790^3

and four new primitively represented d:

    384 = 470129^3 + 521807^3 - 626572^3
        = 1246631^3 + 2277026^3 - 2395327^3
   -480 = 149615^3 + 1000052^3 - 1001167^3
    624 = 650695^3 + 758290^3 - 892751^3
   -768 = 496589^3 + 1937723^3 - 1948534^3

plus assorted other finds such as the second solution for d=12:

 9730705^3 - 9019406^3 - 5725013^3 = 12.

With faster hardware and parallelization it should be straightforward
to take this to 10^10 at least if enough people are interested...

--Noam D. Elkies (elkies@math.harvard.edu)
  Dept. of Mathematics, Harvard University