Sums of Cubes: Algorithmic and Numerical Aspects
François Hennecart
A2X, Université Bordeaux 1
Algorithms Seminar
January 13, 1997
[summary by Alain Plagne]
A properly typeset version of this document is available in
postscript and in
pdf.
If some fonts do not look right on your screen, this might be
fixed by configuring your browser (see the documentation here).
Abstract
Here are presented results of joint work by J.M. Deshouillers, F. Hennecart and B. Landreau
on sums of powers (and especially of three and four cubes): do they have a positive density?
is their behaviour that of the probabilistic model? Moreover, they exhibit a candidate for being
the largest integer which is not sum of four cubes, namely
7 373 170 279 850.
1 Sums of cubes
In 1770, Waring wrote that every integer is the sum of 4 squares, 9 cubes, 19 biquadrates
and so on, meaning that for each integer k, there exists a constant g(k) such that
every integer N is the sum of at most g(k) kth powers. It was not until 1909, that
Hilbert [11] proved it, by a difficult argument.
We say that an integer is C_{k} if it is the sum of at most k cubes. In 1912, Kempner and
Wierferich proved that every integer is C_{9}, that is sum of at most 9 cubes. In 1939,
Dickson [7] proved that, except 23 and 239, every integer is C_{8}. Later, Linnik [15] (and later Watson [21] and Mac Curley [16]), proved that every
sufficiently large integer is C_{7}. Papers by Bohman and Fröberg [2] and Romani [17]
suggest that there are only 15 integers C_{8} and not C_{7} (the
largest one being 454), 121 that are C_{7} and
not C_{6} (the largest one being 8042), and 3922 that are C_{6} and
not C_{5} (the largest one being 1290740).
The circle
method, introduced and developed by Hardy, Littlewood and Ramanujan [10] yields an
asymptotic formula for the number of solutions to some Diophantine equations. It gives, for large
enough s,
R_{s}(N) =  { 0 £ x_{1},...,x_{s} £ N, N= x_{1}^{3}+...+x_{s}^{3} } 
~ S_{s}(N) 

N^{s/31}
(1) 
when N tends to + ¥. The factor S _{s}(N) is
commonly called the singular series
S 
_{s}(N)= 


q^{s} S(a,q)^{s} e_{q}(aN),

where e_{q}(u)= exp(2 p i u/q) and
This singular series reflects the arithmetic
properties of sums of cubes and usually does not imply difficulty because (when it is convergent)
it can be written as an Eulerian product (that is a product over primes). In 1985, Vaughan [19]
proved that (1) holds true for s ³ 8 and two years later, showed [20]
the lower bound
R_{7}(N) » S_{7}(N) N^{4/3}.
The usual conjecture is that (1) is true as soon as s ³ 4. In
this direction, Davenport [4] proved, in 1939, that
E(N)=  { n £ N, such that n is not 
C_{4} } « 

N 

,

which implies that almost every integer is C_{4}. Recently the exponent has been
reduced to 37/43 [3].
We denote by R'_{3}(n) the number of solutions of x^{3}+ y^{3} + z^{3} = n, with
0 £ x £ y £ z. It is clear that the number f_{3}(N) of integers n £ N which
are sums of three positive cubes (that is such that R'_{3}(n)>0) cannot exceed
the number of triples (x,y,z) subject to x^{3}+ y^{3} + z^{3} £ N
and 0 £ x £ y £ z, asymptotically
equal to

G (4/3)^{3}N=0.1186... N.

Now, a natural question is: does the set of sums of 3 cubes have a density? If so, is it strictly
positive? Barrucand [1] computed f_{3}(x) for 1 £ x £ 288000 and conjectured that
it was o(x), as x tends to ¥. Vaughan [18] proved in the opposite direction that
f_{3}(x) »_{e } x^{8/9  e }, improved to
f_{3}(x) »_{e } x^{19/21  e } in [19] and then to
f_{3}(x) »_{e } x^{11/12  e } in [20]
and Hooley [12] conjectured, contrarily to
Barrucand, that f_{3}(x) ~ x. Hooley's approach consists in studying
He proves a first lower bound
M(x) ³ 36 

R'_{3}(n) ~ 6 G (4/3)^{3}x,

which corresponds to the socalled ``combinatorial'' contribution, and then a second, taking now into
account the ``arithmetic'' contribution: if
we have (by just considering the contribution of major arcs)
M(x) ³ 
ó õ 

 F(q)^{2} d q ³ G (4/3)^{6}
Sx +o(x),

with
Hooley conjectures
that these two contributions are ``independent'' and thus that their sum gives the good equivalent for M(x),
namely
M(
x) ~ (6
G (4/3)
^{3} +
G (4/3)
^{6} S)
x,
(3)
which would imply by Cauchy inequality that sums of 3 cubes have a lower density.
2 The first probabilistic approach for sums of three cubes
This is due to Erdös and Rényi [8] in 1960. They consider a sequence (x_{n})_{n ³ 1}
of Bernoulli independent random variables such that
The random variable counting the number of representations of N as
the sum of 3 pseudocubes (that is
integers n for which x_{n} = 1) is
R_{3}(N)= 

å 
N=h_{1}+h_{2}+h_{3} 
h_{1}<h_{2}<h_{3} 


x 

x 

x 

.

Erdös and Rényi announced that R_{3}(N) follows asymptotically a Poisson law:
where g= G (4/3)^{3}/6. But their ``proof'' contained a gap that Landreau [14] recently
filled in a general context (cf. [9]) by using original correlation inequalities
which also enable him to show
that the density of sums of 3 pseudocubes is almost surely
1 e^{ g}=0.1119.... This model has the disadvantage to give a positive
density for the sums of 2 pseudosquares, although
sums of 2 squares are known to have zero density [13].
3 Second probabilistic approach. Sums of three cubes continued
The previous paradox came at least from the following fact: the model did not deal
with arithmetic properties of sums of powers. A new model has been recently presented [6] taking into account arithmetic parameters.
Let K ³ 1. One builds an integer random sequence (µ_{l}^{(k)})_{l ³ 1}
restricted to be equal to k^{3} modulo K and satisfying
µ_{l}^{(k)} ~ (k+lK)^{3}
almost surely.
Let us denote
r_{3}(k,K)=  { (k_{1}, k_{2}, k_{3}), 1 £ k_{i} £ K: k=k_{1}^{3}+k_{2}^{3}+k_{3}^{3}
mod K } 
and
R'_{3}(n,K)=  { n=µ 

+µ 

+µ 

,
µ 

< µ 

< µ 

, n= k_{1}^{3}+k_{2}^{3}+k_{3}^{3}
mod K } .

Once again, it has been shown that R'_{3}(n,K) converges in distribution towards a Poisson law:
Pr 
{ R'_{3}(n,K)=r } ¾® 



l (k,K)^{r} e 

,

with
We can show also that the density of integers such that R'_{3}(n,K) >0 is almost surely 1 d_{0}(K)
where
Notice that it is satisfactory to observe that the probabilistic square mean value satisfies



R'_{3}(n,K)^{2} ~
G (4/3)^{3} + G (4/3)^{6} S'_{2}(K)/6

which is consistent with Hooley's conjecture (3) (for the definition of S'_{2}(K) see
the next section).
4 Numerical viewpoint.
It is now natural to ask what happens when K tends to infinity. It seems reasonable
to consider the following multiplicatively increasing sequence of moduli
Using convexity of the exponential, we first show that d_{0}(K_{B}) has a limit d_{0}
when B tends to infinity. Then in order to find a good approximation for d_{0} ,
we compute d_{0}(K_{B}) for a big value of B, by developing it in series
d_{0}(K_{B})= 

(1)^{i} 

S_{i}'(K_{B})
+R(K_{B}),

where
and
R(K_{B}) £ 

S_{I+1}'(K_{B}).

The multiplicativity of the S_{i}'(K_{B}) is used to estimate
them efficiently. Computations have been done using PARI package. For example, with a B around 5000,
the truncation parameter I has to be around 18000. Now we use the inequality
0 £ d_{0}  d_{0} (K_{B}) £ 

( S 
S_{2}'(K_{B})),

where S, defined by equation (2) appears to be
also the limit of S_{2}'(K_{B}) as B tends to infinity.
Practically, numbers of the form of K_{B} are replaced by numbers with the following form
This finally allows us to deduce
0.09992 £ d_{0} £ 0.09997.
The previous method did not permit to compute d_{0} with an arbitrary number of
significant digits. Ph. Flajolet indicated a more efficient method consisting in the use of
the Mellin transform. Using the formula
valid for any c>1, x>0, we get
d_{0}(K)= 


ó õ 

G (s)
S_{s}'(K) 

(4) 
where
It then remains to estimate (4) by numerical integration.
5 About 7 373 170 279 850
As asserted before, one expects that every sufficiently large integer is C_{4}. Western's conjectures [22] assert that the size of this ``last'' nonC_{4} integer has to be
in the range between 10^{12}
and 10^{14}. Practically, it is intractable to test every integer between 10^{12} and 10^{13}
for example. But the repartition of cubes in arithmetical progressions is far from being regular: this
leads to the idea of discriminating the search depending on the class modulo a good integer.
So, the strategy has been the following: try to ``find'' the last nonC_{4} integer
N_{0} in each class modulo 9. It is considered that it is found if no other nonC_{4}
integer is found between N_{0} and 10N_{0} (10 is a factor seeming largely
sufficient in view of previous experiments). This process allowed to treat the cases
of every residue class modulo 9, except 4 and 5. For these ones, it has been needed to
proceed to a new discrimination (modulo 7). So there were 14 residue classes modulo 63
to examine. This discrimination has allowed to finish all computations.
This has permitted to conjecture that the last nonC_{4} integer is
7 373 170 279 850;
it appears to be equal to 32 modulo 63. Computations have needed
8000 hours. Note that the size of this integer is in accordance with Western's
conjectures. This work is more precisely presented in [5].
References
 [1]

Barrucand (Pierre). 
Sur la distribution empirique des sommes de trois cubes ou de quatre
bicarrés. ComptesRendus de l'Académie des Sciences, vol. 267,
1968, pp. 409411.
 [2]

Bohman (Jan) and Fröberg (CarlErik). 
Numerical investigation of Waring's problem for cubes. BIT,
vol. 21, n°1, 1981, pp. 118122.
 [3]

Brüdern (J.). 
On Waring's problem for cubes. Mathematical Proceedings of the
Cambridge Philosophical Society, vol. 109, n°2, 1991,
pp. 229256.
 [4]

Davenport (H.). 
On Waring's problem for fourth powers. Annals of Mathematics,
vol. 40, 1939, pp. 731747.
 [5]

Deshouillers (J.M.), Hennecart (F.), and Landreau (B.). 
7 373 170 279 850. 
Prépublication, UMR 9936, 1996.
 [6]

Deshouillers (J.M.), Hennecart (F.), and Landreau (B.). 
Sums of powers: an arithmetic refinement to the probabilistic
model of Erdös and Rényi. 
Prépublication, UMR 9936, 1996.
 [7]

Dickson (L.). 
All integers except 23 and 239 are sums of eight cubes. Bulletin
of the American Mathematical Society, vol. 45, 1939,
pp. 588591.
 [8]

Erdös (P.) and Rényi (A.). 
Additive properties of random sequences of positive integers. Acta Arithmetica, vol. 6, 1960, pp. 83110.
 [9]

Halberstam (Heini) and Roth (Klaus Friedreich). 
Sequences. 
SpringerVerlag, New YorkBerlin, 1983, 2nd edition.
 [10]

Hardy (G. H.) and Ramanujan (S.). 
Asymptotic formulæ in combinatory analysis. Proceedings of
the London Mathematical Society, vol. 16, 1917, pp. 75115.
 [11]

Hilbert (D.). 
Beweis für die Darstellbarkeit der ganzen Zahlen durch eine
feste Anzahl nter Potenzen (Waringsche Problem). Mathematische Annalen, vol. 67, 1909, pp. 281300.
 [12]

Hooley (Christopher). 
On some topics connected with Waring's problem. Journal
für die Reine und Angewandte Mathematik, vol. 369, 1986,
pp. 110153.
 [13]

Landau (E.). 
Über die Einteilung der ... Zahlen in 4 Klassen. Arch.
Math. Phys., vol. 13, n°3, 1908, pp. 305312.
 [14]

Landreau (Bernard). 
Étude probabiliste des sommes de s puissances sièmes. Compositio Mathematica, vol. 99, n°1, 1995, pp. 131.
 [15]

Linnik (U. V.). 
On the representation of large numbers as sums of seven cubes. Mat. Sbornik, vol. 12, n°54, 1943, pp. 218224.
 [16]

McCurley (Kevin S.). 
An effective seven cube theorem. Journal of Number Theory,
vol. 19, n°2, 1984, pp. 176183.
 [17]

Romani (F.). 
Computations concerning Waring's problem. Calcolo, vol. 19,
n°4, 1982, pp. 415431.
 [18]

Vaughan (R. C.). 
Sums of three cubes. Bulletin of the London Mathematical
Society, vol. 17, 1985, pp. 1720.
 [19]

Vaughan (R. C.). 
On Waring's problem for cubes. Journal für die Reine und
Angewandte Mathematik, vol. 365, 1986, pp. 122170.
 [20]

Vaughan (R. C.). 
On Waring's problem for cubes II. Journal of the London
Mathematical Society, vol. 39, n°2, 1989, pp. 205218.
 [21]

Watson (G. L.). 
A proof of the seven cube theorem. Journal of the London
Mathematical Society, vol. 26, n°2, 1951, pp. 153156.
 [22]

Western (A. E.). 
Computations concerning numbers representable by four or five cubes.
Journal of the London Mathematical Society, vol. 1, n°2,
1926, pp. 244251.
This document was translated from L^{A}T_{E}X by
H^{E}V^{E}A.