On the computation of $g(k)$ in Waring’s problem
HTML articles powered by AMS MathViewer
 by Francine Delmer and JeanMarc Deshouillers PDF
 Math. Comp. 54 (1990), 885893 Request permission
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 \[ \{ {(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.References

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), 8588, 161163.
L. E. Dickson, History of the theory of numbers. II, New York, 1934.
 François Dress, Théorie additive des nombres, problème de Waring et théorème de Hilbert, Enseign. Math. (2) 18 (1972), 175–190; errata, ibid. (2) 18 (1972), 301–302 (1973) (French). MR 337763
 Hartmut Ehlich, Zur Pillaischen Vermutung, Arch. Math. (Basel) 16 (1966), 223–226 (German). MR 177969, DOI 10.1007/BF01220025
 W. J. Ellison, Waring’s problem, Amer. Math. Monthly 78 (1971), no. 1, 10–36. MR 414510, DOI 10.2307/2317482
 Donald E. Knuth, The art of computer programming, 2nd ed., AddisonWesley Series in Computer Science and Information Processing, AddisonWesley Publishing Co., Reading, Mass.LondonAmsterdam, 1975. Volume 1: Fundamental algorithms. MR 0378456
 Jeffrey M. Kubina and Marvin C. Wunderlich, Extending Waring’s conjecture to $471,600,000$, Math. Comp. 55 (1990), no. 192, 815–820. MR 1035936, DOI 10.1090/S00255718199010359366
 K. Mahler, On the fractional parts of the powers of a rational number. II, Mathematika 4 (1957), 122–124. MR 93509, DOI 10.1112/S0025579300001170
 D. Ridout, Rational approximations to algebraic numbers, Mathematika 4 (1957), 125–131. MR 93508, DOI 10.1112/S0025579300001182
 Rosemarie M. Stemmler, The ideal Waring theorem for exponents $401200,000$, Math. Comp. 18 (1964), 144–146. MR 159803, DOI 10.1090/S0025571819640159803X
Additional Information
 © Copyright 1990 American Mathematical Society
 Journal: Math. Comp. 54 (1990), 885893
 MSC: Primary 11P05; Secondary 11J25, 11Y16
 DOI: https://doi.org/10.1090/S00255718199010114406
 MathSciNet review: 1011440