For every k, let g(k) denote the minimum number s of kth powers of naturals needed to represent all positive integers. Every positive integer is the sum of one first power, itself, so g(1) = 1. Some simple computations show that 7 requires 4 squares, 23 requires 9 cubes, and 79 requires 19 fourth powers; these examples show that g(2) \ge 4, g(3) \ge 9, and g(4) \ge 19. Waring conjectured that these lower bounds were in fact exact values.
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 in
Bachet's 1621 edition of
Diophantus's
Arithmetica;
Fermat claimed to have a proof, but did not publish it. 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. Let q and r be defined by the
Euclidean division3^k = 2^k q + r, \quad 0 \le r or explicitly by q = \lfloor(3/2)^k\rfloor and r = 2^k \{(3/2)^k\} , where \lfloor x\rfloor and \{x\} respectively denote the
integral and
fractional part of a real number x. Since the number 2^k q - 1 is less than 3^k, as a sum of integer powers, it can only be expressed using 1^k and 2^k. Using
modular arithmetic, one shows that the fewest number of terms is achieved by the formula2^k q - 1 = \underbrace{1^k + \dots + 1^k}_{2^k-1 \text{ times}} + \underbrace{2^k + \dots + 2^k}_{q - 1 \text{ times}},and it follows thatg(k) \ge 2^k + q - 2,which was noted by
J. A. Euler in about 1772. Let 4^k = 3^k d + s,\, 0 \le s . Combined work from the authors quoted above has led to the formula, valid for all k :g(k) = \begin{cases} 2^k + q - 2 &\text{if }~ q + r \le 2^k \\ 2^k + q + d - 2 &\text{if }~ q + r > 2^k ~\text{ and }~ q d + q + d = 2^k \\ 2^k + q + d - 3 &\text{if }~ q + r > 2^k ~\text{ and }~ q d + q + d > 2^k. \end{cases}Dickson and Pillai both independently proved the first case, for q + r \le 2^k - 3, and the two other cases, and they noted that q + r \neq 2^k - 1 for k > 1. Rubugunday proved that q + r \neq 2^k for all k, leaving the final case q + r = 2^k - 2 open. In this scenario, Niven proved that g(k) = 2^k + q - 2. No value of k is known for which the hypothesis q + r > 2^k in the last two cases holds.
Mahler proved that there can only be a finite number of such k. Kubina and Wunderlich, extending work of Stemmler, have shown that any such k must satisfy k > 471\,600\,000. It is conjectured that there are no such k; in that case, g(k) = 2^k + q - 2 for
every positive integer k. The first few values of g(k) are : 1, 4, 9, 19, 37, 73, 143, 279, 548, 1079, 2132, 4223, 8384, 16673, 33203, 66190, 132055, 263619, 526502, 1051899, ... . ==The number
G(
k)==