Sums of Cubes: Algorithmic and Numerical Aspects

Franois 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 Frberg [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 Erds and Rnyi [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
.
Erds and Rnyi 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) FACE=sym } <
 
TABLE CELLSPACING=2 CELLPADDING=0>
Nn/I> +FONT FACE=symbol>
Nn/I> k<mod qK/I>
3I>r!
< FONT FACE=symbol>l/FONT> (4I>k,K)=SUP>r<e
- gl/FONT> (4I>k,K)=SFONT>
 
,
whith
gl/FONT> (4I>k,K)= Gg/FONT> +FTD>
FONT FACE=symbol>r<(4I>k,K)=SFD>
3I>rK/I>2//FONT>
.
TWecan bhow lso ehat the density of sntegers R'3(n,K) cgt;0)is almost surely 1 gd/FONT>30/FONT>(n) cwhere
gd/FONT>30/FONT>(n) c
1
3I>qK/I>
<
qK/I>
qk/I>=1
e
- gl/FONT> (4I>k,K)=SFONT>
 
,
Ntica that et is catisfyctor to observeehat the drobabilistic aquaresmeani valuecatisfyes
1
3I>qx/I>
n x
R'3(n,K) SUP>2 <~< FONT FACE=symbol>
(4/3)3 + G (4/3)6 S)32/FONT>(n) /6
which imsconsistsnt rith aooley's aonjecture i) i(or the sdefiniion of mFONT COLOR=red> S)32/FONT>(n) ee tthe nuxt (ection )

Tt is cow iatural qo acsk wat thappnsi hen N }ends to
RK/I>nB/I>=
/FONT>
I>np/I>
/TABLE>
-a
&FONT SIZE=2>
FONT SIZE=2>-a xB/I>
Rp/I>
-FONT FACE=symbol>a
 
, Usng fonverxty of she exponent ial, w first phow hat gd/FONT>30/FONT>(n)SUPBnB/I>=)has ba limi gd/FONT>30/FONT>( when NB/I> }ends to gd/FONT>30/FONT>( , we homputedgd/FONT>30/FONT>(n)SUPBnB/I>=)hfr
NB/I>< by aevelopeng intin stries
gd/FONT>30/FONT>(n)SUPBnB/I>=) <
qI/I>
q<=
| (-1=SUP>r
FONT FACE=symbol>Gg/FONT> SUP>r /TD>
3I>qi/I>!
S)SUB>i 'n)SUPBnB/I>=) +F>R'n)SUPBnB/I>=)
where <
Si 'n)SUPBnB/I>=)
1
3I>qK/I>nB/I>=/FD>
qk/I>=mod qK/I>nB/I>=/FD>
< /TD> BR> BR> BR> /FONT>
ALIGN=center> g<(4I>k,K)SUPBnB/I>=)/TD>
3I>qK/I>nB/I>=/UP>2//FONT>
. BR> BR> BR> /FONT> /TABLE>
0I>i


0nbsp;
nd
<|F>R'n)SUPBnB/I>=)|a
FONT FACE=symbol>Gg/FONT> SUP>rI/I><+1/FONT> /TD>
3(I>rI/I><+1)
S)SUB>iI/I><+1/FONT> 'n)SUPBnB/I>=)
he pmultiplcalivety of she eFONT COLOR=red> S
i 'n)SUPBnB/I>=)is cusd to bstiomti tthe m eficiently . Cmputetions oave zeen sdne bsing oPARI pck>age. Fr NB/I> }arund 5000,tthe ntrunction iarameters I>iI/I>
< gd/FONT>30/FONT>( gd/FONT>30/FONT>( n)SUPBnB/I>=)iFONT FACE=symbol>a <
FONT FACE=symbol>Gg/FONT> SUP>
32/TD>
| (FONT COLOR=red> S< < S32/FONT>('n)SUPBnB/I>=),
where S
<,sdefind by Hquationsi<2/F>) iappnrs lh be e lso ehae limi S
)/UB>32/FONT>('n)SUPBnB/I>=)as xB/I> }ends to N)SUPBnB/I>=are krepackd by Humber soith he following farmu
/FONT>
I>np/I>
/TABLE>
-a
&FONT SIZE=2>
FONT SIZE=2>-nB/I>1
<a< 12/FONT> /TABLE> Rp/I>
-FONT FACE=symbol>a
 
, < /TABLE>
/FONT>
I>np/I>< lt;hB/I>1
I>np/I><=1mod <3/FONT>
Rp/I><
hes cfnal y a lows au to <0.0999 p gd/FONT>30/FONT>( FONT FACE=symbol>p <0.09997. BR> gd/FONT>30/FONT>(with anarebirariynumber of r igmniiciantdidgits. Ph. Flajoletin dcalid a gmoe keficientlpetehoddonsistsng int he fse (f r he fMellnt hransarmu. Usng fhe eormuula
R- I>x=0 /TABLE>
1
32<>i gp/FONT>

<
1<>ic/I><+<>i g


0<>ic/I><-<>i g
G (4<>s ) <
F>x1-<>s /FONT>
3<>s /FD>
Rd
vald nfr ic/I>x
< gd/FONT>30/FONT>(n) 0 /TABLE>
1
32<>i gp/FONT>

<
1<>ic/I><+<>i g


0<>ic/I><-<>i g
G (4<>s )< S3-<>s /FONT>('n))
F>xd /FD> <
3<>s /FD>
    (34
Hhere
S3-<>s /FONT>('n))0
1
3I>qK/I>
qk/I>=mod qK/I>
< /TD> BR> BR> BR> /FONT>
ALIGN=center> g<(4I>k,K))/TD>
3I>qK/I>2//FONT>
. BR> BR> BR> /FONT>
/TABLE>
0-<>s /FONT>


0nbsp;
,
Itthen aremainsto bstiomti t<4/F>) iy Humbrical Antegertions

TA asyserid abefr e, ne bexpcti that tevery suficiently largeinteger ri xC/I>)SUPB<4/FONT>(. Wstierns aonjecture snbsp;[
62] csyseriehat the dsizeof shei <``las'' anon-I>xC/I>)SUPB<4/FONT>(integer ras th be e nt he frang zeetwen s10/UP>21 < nd 10/UP>214/FONT> . Pracically ,nt is citrarctble ho thstitevery nteger reetwen s10/UP>21 21 mfr xC/I>)SUPB<4/FONT>(integer rMN/I>)SUPB<0/FONT>(int ech colassmodulo <9 It imsconsisdeed that t is cfund iffno ohaerfnon-I>xC/I>)SUPB<4/FONT>(i nteger ri MN/I>)SUPB<0/FONT>(ind 10/>MN/I>)SUPB<0/FONT>(i(1)is al yctor iee mng olargey 1suficientlint viewof poevious pexpcrimntls) This mproc ssa lowsd to btret the dcass wf pevery e siue tolassmodulo <9,pexcept 4ind 5. Fr xC/I>)SUPB<4/FONT>(integer ri < 7 373 170 279 850;i ntiappnrs lh be equal to <32modulo <63. Cmputetions oave zneedd t 000 hous. ANoteehat the dsizeof shei 65/CITE>].

<<<

2Ref rece -/H2> T[1]/FONT> Cmpuhst-Rndes den l'Aca/FEM>mi sdes Siente -/HEM>, vol [267, 19608, pp [409--411

<<[2]/FONT> BIT/HEM>, vol [21, n°01,<1981, pp [118--122

<<[3]/FONT> Mahe maic l AProc d ng sof she Cambridg zPhilosophc l ASoienty/HEM>, vol [109, n°02,<1991, pp [229--256

<<[4]/FONT> Annalsof sMahe maic s/HEM>, vol [40,<1939, pp [731--747

<<[5]/FONT> 7 373 170 279 850/HEM> [-- Prpublcalivn, aUMR 9936,<1996

<<[6]/FONT> Sms of powers.: anarethmetic prefindmntlto the srobabilistic model hf EIFEM>r/FEM> and R/FEM>R/FEM>nyi/HEM> [-- Prpublcalivn, aUMR 9936,<1996

<<[7]/FONT> Buledong of she eAbricaln Mahe maic l ASoienty/HEM>, vol [45,<1939, pp [588--591

<<[8]/FONT> Actb Aithmetic l/HEM>, vol [6,<1960, pp [83--110

<<[9]/FONT> Squence /HEM> [-- Sping er-Verlag, Nw mYork-Berln, i1983, 2d Rediions

<<[10]/FONT> Proc d ng sof she eLodomn Mahe maic l ASoienty/HEM>, vol [16,<1917, pp [75--115

<<[11]/FONT> n
=-er NPotenzn s(Waing sce eProle m) TMahe maicsce eAnnalen/HEM>, vol [67,<1909, pp [281--300

<<[12]/FONT> Junrnal f/FEM>IFEM>rdise Reng nd Ag ewnd ie Mahe maick/HEM>, vol [369 i1986, pp [110--153

<<[13]/FONT> Arch. Mahe. Phys./HEM>, vol [13, n°03,<1908, pp [305--312

<<[14]/FONT> s
puissace o<>s -imes TCmpuwitivo Mahe maic l/HEM>, vol [99, n°01,<1995, pp [1--31

<<[15]/FONT> Mah. Sbornck/HEM>, vol [12, n°054,<1943, pp [218--224

<<[16]/FONT> Junrnalof pNmber oTeidry/HEM>, vol [19, n°02,<1984, pp [176--183

<<[17]/FONT> Calcolo/HEM>, vol [19, n°04,<1982, pp [415--431

<<[18]/FONT> Buledongof she eLodomn Mahe maic l ASoienty/HEM>, vol [17,<1985, pp [17--20

<<[19]/FONT> Junrnalof/FEM>IFEM>rdise Reng nd Ag ewnd ie Mahe maick/HEM>, vol [365 i1986, pp [122--170

<<[20]/FONT> Junrnalof phe eLodomn Mahe maic l ASoienty/HEM>, vol [39, n°02,<1989, pp [205--218

<<[21]/FONT> Junrnalof phe eLodomn Mahe maic l ASoienty/HEM>, vol [26, n°02,<1951, pp [153--156

<<[22]/FONT> Junrnalof phe eLodomn Mahe maic l ASoienty/HEM>, vol [1, n°02, 19626, pp [244--251<<