Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society since 1960 (published as Mathematical Tables and other Aids to Computation 1943-1959), Mathematics of Computation is devoted to research articles of the highest quality in computational mathematics.

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

The 2020 MCQ for Mathematics of Computation is 1.78.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.


On the computation of $g(k)$ in Waring’s problem
HTML articles powered by AMS MathViewer

by Francine Delmer and Jean-Marc Deshouillers PDF
Math. Comp. 54 (1990), 885-893 Request permission


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 \[ \{ {(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 \[ 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.
Similar Articles
Additional Information
  • © Copyright 1990 American Mathematical Society
  • Journal: Math. Comp. 54 (1990), 885-893
  • MSC: Primary 11P05; Secondary 11J25, 11Y16
  • DOI:
  • MathSciNet review: 1011440