Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



On the computation of $ g(k)$ in Waring's problem

Authors: Francine Delmer and Jean-Marc Deshouillers
Journal: Math. Comp. 54 (1990), 885-893
MSC: Primary 11P05; Secondary 11J25, 11Y16
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 kth 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 $ g(k)$.

A first goal is to show that our knowledge of $ g(k)$ is rather satisfactory:

--Writing down all the numbers $ g(2),g(3), \ldots ,g(K)$ may be performed in $ O({K^2})$ bit operations, which is best possible, since $ g(k)$ has $ (k + 1)$ digits in its binary expansion.

--Writing down $ g(k)$ may be performed in $ O(k\log k.\log \log k)$ 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

$\displaystyle \{ {(3/2)^k}\} \leq 1 - {(3/4)^k};$

the underlying idea has led J. M. Kubina and M. C. Wunderlich to check this up to 471,600,000. This inequality is related to Waring's problem in that it would imply the formula

$\displaystyle g(k) = {2^k} + [{(3/2)^k}] - 2;$

however, the knowledge of this relation would not improve our knowledge on the complexity of computing $ g(k)$, neither on average, nor for individual values of k.

References [Enhancements On Off] (What's this?)

  • [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)

Similar Articles

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

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

Additional Information

Keywords: Computational number theory, Waring's problem, Diophantine inequalities
Article copyright: © Copyright 1990 American Mathematical Society

American Mathematical Society