Waring's problem

Remarks

Hilbert proved in 1909 that $g(k)$ exists for every $k$ (the Hilbert–Waring theorem). By definition $G(k) \le g(k)$. Lagrange's four-square theorem gives $g(2) = 4$, and $G(2) = 4$ because no integer $n \equiv 7 \pmod 8$ is a sum of three squares. Known values include $g(3) = 9$ and $g(4) = 19$; the numbers $23$ and $79$ need $9$ cubes and $19$ fourth powers. The lower bound $g(k) \ge 2^k + \floor{(3/2)^k} - 2$ comes from the integer $n = 2^k \floor{(3/2)^k} - 1$, which is less than $3^k$ and so must be written with the powers $1^k$ and $2^k$ only. Equality is known for all $k$ outside a possible finite set, and the possible exceptions have been excluded far beyond any small $k$. For $G(k)$ much less is known: $G(4) = 16$ (Davenport), and $4 \le G(3) \le 7$, the upper bound being due to Linnik. The Hardy–Littlewood circle method gives an asymptotic formula for the number of representations when the number of powers is large compared with $k$.