In number theory, Waring's problem, proposed in 1770 by Edward Waring, asks whether for every natural number k there exists an associated positive integer s such that every natural number is the sum of at most s kth powers of natural numbers. The affirmative answer was provided by David Hilbert in 1909. Sometimes this topic is described as Hilbert-Waring's theorem.
For every k, we denote the least such s by g(k). Note we have g(1) = 1. Some simple computations show that 7 requires 4 squares, 23 requires 9 cubes, and 79 requires 19 fourth-powers. Waring conjectured that these values were in fact the best possible.
Lagrange's four-square theorem of 1770 states that every natural number is the sum of at most four squares; since three squares are not enough, this theorem establishes g(2) = 4. Lagrange's four-square theorem was conjectured by Fermat in 1640 and was first stated in 1621.
Over the years various bounds were established, using increasingly sophisticated and complex proof techniques. For example, Liouville showed that g(4) is at most 53. Hardy and Littlewood showed that all sufficiently large numbers are the sum of at most 19 fourth powers.
That g(3) = 9 was established from 1909 to 1912 by Wieferich and A. J. Kempner, g(4) = 19 in 1986 by R. Balasubramanian, F. Dress, and J.-M. Deshouillers, g(5) = 37 in 1964 by Chen Jingrun and g(6) = 73 in 1940 by Pillai.
All the other values of g are now also known, as a result of work by Dickson, Pillai, Rubugunday and Niven. Their formula contains two cases, and it is conjectured that the second case never occurs; in the first case, the formula reads
- g(k) = floor((3/2)k) + 2k - 2 for k ≥ 6.
giving the values
From the work of Hardy and Littlewood, more fundamental than g(k) turned out to be G(k), which is defined to be the least positive integer s such that every sufficiently large integers can be represented as a sum of at most s kth powers of positive integers. It is easy to see that G(2)≥ 4 since every integer congruent to 7 modulo 8 cannot be represented as a sum of three squares. Davenport showed that G(4)=16 in 1939. The exact value of G(k) is unknown for any other k. Using his improved Hardy-Littlewood method, Vinogradov has shown that
- W. J. Ellison: Waring's problem. American Mathematical Monthly, volume 78 (1971), pp. 10-76. Survey, contains the precise formula for g(k) and a simplified version of Hilbert's proof.
- Hans Rademacher and Otto Toeplitz, The Enjoyment of Mathematics (1933) (ISBN 0-691-02351-4). Has a proof of the Lagrange theorem, accessible to high school students.