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 k^th powers of natural numbers. The affirmative answer, known as the Hilbert-Waring theorem, was provided by David Hilbert in 1909.D. Hilbert, Beweis für die Darstellbarkeit der ganzen Zahlen durch eine feste Anzahl n-ter Potenzen (Waringsches Problem), Mathematische Annalen, 67, pages 281-300 (1909)

The number g(k)

---

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.

Apart from a certain ambiguity, all the other values of g are now also known, as a result of work by Dickson, Pillai, Rubugunday and Ivan M. Niven. Their formula contains two cases, and it is conjectured that the second case, which has been shown to occur at most finitely many times by MahlerMahler, K. On the fractional parts of the powers of a rational number II, 1957, Mathematika, 4, pages 122-124, never occurs; in the first case,

$2^k\backslash left\backslash \{\backslash left(\backslash frac\{3\}\{2\}\backslash right)^k\backslash right\backslash \}+\backslash Bigg\backslash lfloor\backslash left(\backslash frac\{3\}\{2\}\backslash right)^k\backslash Bigg\backslash rfloor\backslash le\; 2^k,$

where {x} denotes the fractional part x - ^* of x, the formula reads:

$g(k)=\backslash Bigg\backslash lfloor\backslash left(\backslash frac\{3\}\{2\}\backslash right)^k\backslash Bigg\backslash rfloor+2^k-2,$

giving the values 1, 4, 9, 19, 37, 73, 143, 279, 548, 1079, 2132, 4223, 8384, 16673, 33203, 66190,132055 ... listed in Sloane's A002804.

The above equality is easily seen to be a lower bound for g(k) for all k by considering the number

$2^k\backslash Bigg\backslash lfloor\backslash left(\backslash frac\{3\}\{2\}\backslash right)^k\backslash Bigg\backslash rfloor-1,$

and observing that it smaller than $3^k$, hence has to be a sum of k-th powers of 1 or 2.

The number G(k)

---

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 integer (i.e. every integer greater than some constant) can be represented as a sum of at most s k^th 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. Since G(k) ≤ g(k) for all k, this shows that G(2) = 4. Davenport showed that G(4) = 16 in 1939. The exact value of G(k) is unknown for any other k, but there exist bounds.

Lower bounds for G(k)

The number G(k) is greater than or equal to

$2^\{r+2\}$ if $k=2^r$ with r ≥ 2, or $k=2^r3;$

$p^\{r+1\}$ if p is a prime greater than 2 and $k=p^r(p-1);$

$\backslash frac\{1\}\{2\}\backslash left(p^\{r+1\}-1\backslash right)$ if p is a prime greater than 2 and $k=\backslash frac\{1\}\{2\}p^r(p-1);$

k + 1 for all integers k greater than 1.

Upper bounds for G(k)

The following upper bounds for G(k) are known:

k              3   5   6   7   8   9  10  11  12  13  14   15   16   17   18   19   20
G(k) =<    7  17  21  33  42  50  59  67  76  84  92  100  109  117  125  134  142 

Using his improved Hardy-Littlewood method, I. M. Vinogradov has shown that

$G(k)\backslash le\; k(3\backslash log\; k\; +11).$

T. D. Wooley has established the bound

$G(k)\backslash le\; k\backslash log\; k+k\backslash log\backslash log\; k+O(k),$

which holds for any k.

Further reading

---

• W. J. Ellison: Waring's problem. American Mathematical Monthly, volume 78 (1971), pp. 10-76. Survey, contains the precise formula for g(k), a simplified version of Hilbert's proof and a wealth of references.
• 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.

Notes

---

Number theory | Analytic number theory

Waringsches Problem | Problème de Waring | בעיית וארינג | ウェアリングの問題 | Waringin probleema