zbMATH — the first resource for mathematics

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