On the computation of \(g(k)\) in Waring’s problem. (English) Zbl 0701.11043

Let \(g(k)\) be the smallest number \(s\) such that all natural numbers are the sum of at most \(s\) \(k\)-th powers. It is conjectured that \(g(k)=2^ k+[(3/2)^ k]-2\) for \(k\geq 6\), and this is known for \(k\geq k_ 0\), for some non-effective \(k_ 0\). The present paper describes “fast” algorithms for writing down all the numbers \(g(2), g(3),\dots, g(k)\) (here \(O(k^ 2)\) operations are needed, best possible), and for writing down an individual \(g(k)\) (needs \(O(k \log k \log\log k)\) operations, close to best possible). The authors have also developed an algorithm which is fast, and which in certain cases gives a positive answer to the conjecture on \(g(k)\), but not a negative one.
Reviewer: J. Brüdern


11P05 Waring’s problem and variants
11Y16 Number-theoretic algorithms; complexity
11J25 Diophantine inequalities
Full Text: DOI