On the computation of in Waring's problem

Authors:
Francine Delmer and Jean-Marc Deshouillers

Journal:
Math. Comp. **54** (1990), 885-893

MSC:
Primary 11P05; Secondary 11J25, 11Y16

DOI:
https://doi.org/10.1090/S0025-5718-1990-1011440-6

MathSciNet review:
1011440

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Over two hundred years ago, Waring raised the question of representing natural integers as sums of integral *k*th powers. At the beginning of this century, Hilbert proved that, for any fixed *k*, the minimal number of summands needed in the representation of any integer can be uniformly bounded. The least such bound is denoted by .

A first goal is to show that our knowledge of is rather satisfactory:

--Writing down all the numbers may be performed in bit operations, which is best possible, since has digits in its binary expansion.

--Writing down may be performed in bit operations, which we expect to be fairly close to the actual complexity.

A second aim is to discuss the complexity of checking the validity of the conjectured Diophantine inequality

*k*.

**[1]**R. Balasubramanian, J.-M. Deshouillers, and F. Dress,*Problème de Waring pour les bicarrés*. 1, 2, C.R. Acad. Sci. Paris Sér. I Math.**303**(1986), 85-88, 161-163.**[2]**L. E. Dickson,*History of the theory of numbers*. II, New York, 1934.**[3]**F. Dress,*Théorie additive des nombres, problème de Waring et théorème de Hilbert*, Enseign. Math.**18**(1972), 175-190. MR**0337763 (49:2532)****[4]**H. Ehlich,*Zur Pillaischen Vermutung*, Arch. Math.**16**(1965), 223-226. MR**0177969 (31:2227)****[5]**W. J. Ellison,*Waring's problem*, Amer. Math. Monthly**78**(1971), 10-36. MR**0414510 (54:2611)****[6]**D. E. Knuth,*The art of computer programming*, Addison-Wesley, Reading, MA, 1981. MR**0378456 (51:14624)****[7]**J. M. Kubina and M. C. Wunderlich,*Extending Waring's conjecture to*471,600,000, Math. Comp.**55**(1990), (to appear). MR**1035936 (91b:11101)****[8]**K. Mahler,*On the fractional parts of powers of real numbers*, Mathematika**4**(1957), 122-124. MR**0093509 (20:33)****[9]**D. Ridout,*Rational approximations to algebraic numbers*, Mathematika**4**(1957), 125-131. MR**0093508 (20:32)****[10]**R. M. Stemmler,*The ideal Waring theorem for exponents*401-200,000, Math. Comp.**18**(1964), 144-146. MR**0159803 (28:3019)**

Retrieve articles in *Mathematics of Computation*
with MSC:
11P05,
11J25,
11Y16

Retrieve articles in all journals with MSC: 11P05, 11J25, 11Y16

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1990-1011440-6

Keywords:
Computational number theory,
Waring's problem,
Diophantine inequalities

Article copyright:
© Copyright 1990
American Mathematical Society