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) k-th powers. It was not until 1909, that Hilbert [11] proved it, by a difficult argument.

We say that an integer is Ck if it is the sum of at most k cubes. In 1912, Kempner and Wierferich proved that every integer is C9, that is sum of at most 9 cubes. In 1939, Dickson [7] proved that, except 23 and 239, every integer is C8. Later, Linnik [15] (and later Watson [21] and Mac Curley [16]), proved that every sufficiently large integer is C7. Papers by Bohman and Fröberg [2] and Romani [17] suggest that there are only 15 integers C8 and not C7 (the largest one being 454), 121 that are C7 and not C6 (the largest one being 8042), and 3922 that are C6 and not C5 (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,
Rs(N) = | { 0 £ x1,...,xs £ N, N= x13+...+xs3 } | ~ Ss(N)
G (4/3)s
G(s/3)
Ns/3-1     (1)
when N tends to + ¥. The factor S s(N) is commonly called the singular series
S s(N)=
¥
å
q=1
 
å
a mod q
(a,q)=1
q-s S(a,q)s eq(-aN),
where eq(u)= exp(2 p i u/q) and
S(a,q)=
q
å
m=1
eq(amk).
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
R7(N) » S7(N) N4/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 C4 }| «
 
e
N
29
30
+ e
 
,
which implies that almost every integer is C4. Recently the exponent has been reduced to 37/43 [3].

We denote by R'3(n) the number of solutions of x3+ y3 + z3 = n, with 0 £ x £ y £ z. It is clear that the number f3(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 x3+ y3 + z3 £ N and 0 £ x £ y £ z, asymptotically equal to
1
6
G (4/3)3N=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 f3(x) for 1 £ x £ 288000 and conjectured that it was o(x), as x tends to ¥. Vaughan [18] proved in the opposite direction that f3(x) »e x8/9 - e , improved to f3(x) »e x19/21 - e in [19] and then to f3(x) »e x11/12 - e in [20] and Hooley [12] conjectured, contrarily to Barrucand, that f3(x) ~ x. Hooley's approach consists in studying
M(x) =
 
å
n £ x
R3(N)2.
He proves a first lower bound
M(x) ³ 36
 
å
n £ x
R'3(n) ~ 6 G (4/3)3x,
which corresponds to the so-called ``combinatorial'' contribution, and then a second, taking now into account the ``arithmetic'' contribution: if
F (q)=
 
å
n £ x
R3(n) e(n q),
we have (by just considering the contribution of major arcs)
M(x) ³ ó
õ
1


0
| F(q)|2 d q ³ G (4/3)6 Sx +o(x),
with
S =
¥
å
q=1
 
å
a mod q
(a,q)=1
|S(a,q)/q|6.     (2)
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 (xn)n ³ 1 of Bernoulli independent random variables such that
Pr (xn=1)= an=
1
3n2/3
.
The random variable counting the number of representations of N as the sum of 3 pseudo-cubes (that is integers n for which xn = 1) is
R3(N)=
 
å
N=h1+h2+h3
h1<h2<h3
x
 
h1
x
 
h2
x
 
h3
.
Erdös and Rényi announced that R3(N) follows asymptotically a Poisson law:
Pr (R3(N)=r) ¾®
 
N ® + ¥
gr
r!
e
- g
 
,
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 pseudo-cubes is almost surely 1- e- g=0.1119.... This model has the disadvantage to give a positive density for the sums of 2 pseudo-squares, 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 k3 modulo K and satisfying
µl(k) ~ (k+lK)3
almost surely.

Let us denote
r3(k,K)= | { (k1, k2, k3), 1 £ ki £ K: k=k13+k23+k33 mod K } |
and
R'3(n,K)= | { n=µ
(k1)
 
l1
+µ
(k2)
 
l2
+µ
(k3)
 
l3
, µ
(k1)
 
l1
< µ
(k2)
 
l2
< µ
(k3)
 
l3
, n= k13+k23+k33 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 } ¾®
 
n ® ¥
n=k mod K
1
r!
l (k,K)r e
- l (k,K)
 
,
with
l (k,K) = g
r (k,K)
K2
.
We can show also that the density of integers such that R'3(n,K) >0 is almost surely 1- d0(K) where
d0(K) =
1
K
K
å
k=1
e
- l (k,K)
 
.
Notice that it is satisfactory to observe that the probabilistic square mean value satisfies
1
x
 
å
n £ x
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
KB=
 
Õ
p
a
 
£ B
p
a
 
.
Using convexity of the exponential, we first show that d0(KB) has a limit d0 when B tends to infinity. Then in order to find a good approximation for d0 , we compute d0(KB) for a big value of B, by developing it in series
d0(KB)=
I
å
i=0
(-1)i
gi
i!
Si'(KB) +R(KB),
where
Si'(KB)=
1
KB
 
å
k mod KB
æ
ç
ç
è
r (k,KB)
KB2
ö
÷
÷
ø
i



 
and
|R(KB)| £
gI+1
(I+1)!
SI+1'(KB).
The multiplicativity of the Si'(KB) 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 £ d0 - d0 (KB) £
g2
2
( S - S2'(KB)),
where S, defined by equation (2) appears to be also the limit of S2'(KB) as B tends to infinity. Practically, numbers of the form of KB are replaced by numbers with the following form
 
Õ
p
a
 
< B1
a ³ 2
p
a
 
 
Õ
p <B2
p=1 mod 3
p.
This finally allows us to deduce
0.09992 £ d0 £ 0.09997.

The previous method did not permit to compute d0 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
e-x=
1
2i p
ó
õ
c+i ¥


c-i ¥
G (s)
x-s
s
ds
valid for any c>1, x>0, we get
d0(K)=
1
2i p
ó
õ
c+i ¥


c-i ¥
G (s) S-s'(K)
ds
s
    (4)
where
S-s'(K)=
1
K
 
å
k mod K
æ
ç
ç
è
r (k,K)
K2
ö
÷
÷
ø
-s



 
.
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 C4. Western's conjectures [22] assert that the size of this ``last'' non-C4 integer has to be in the range between 1012 and 1014. Practically, it is intractable to test every integer between 1012 and 1013 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 non-C4 integer N0 in each class modulo 9. It is considered that it is found if no other non-C4 integer is found between N0 and 10N0 (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 non-C4 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. Comptes-Rendus de l'Académie des Sciences, vol. 267, 1968, pp. 409--411.

[2]
Bohman (Jan) and Fröberg (Carl-Erik). -- Numerical investigation of Waring's problem for cubes. BIT, vol. 21, n°1, 1981, pp. 118--122.

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

[4]
Davenport (H.). -- On Waring's problem for fourth powers. Annals of Mathematics, vol. 40, 1939, pp. 731--747.

[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. 588--591.

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

[9]
Halberstam (Heini) and Roth (Klaus Friedreich). -- Sequences. -- Springer-Verlag, New York-Berlin, 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. 75--115.

[11]
Hilbert (D.). -- Beweis für die Darstellbarkeit der ganzen Zahlen durch eine feste Anzahl n-ter Potenzen (Waringsche Problem). Mathematische Annalen, vol. 67, 1909, pp. 281--300.

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

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

[14]
Landreau (Bernard). -- Étude probabiliste des sommes de s puissances s-ièmes. Compositio Mathematica, vol. 99, n°1, 1995, pp. 1--31.

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

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

[17]
Romani (F.). -- Computations concerning Waring's problem. Calcolo, vol. 19, n°4, 1982, pp. 415--431.

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

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

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

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

[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. 244--251.
This document was translated from LATEX by HEVEA.