Waring's problem

Long before Waring posed his problem, Diophantus had asked whether every positive integer could be represented as the sum of four perfect squares greater than or equal to zero. This question later became known as Bachet's conjecture, after the 1621 translation of Diophantus by Claude Gaspard Bachet de Méziriac, and it was solved by Joseph-Louis Lagrange in his four-square theorem in 1770, the same year Waring made his conjecture. Waring sought to generalize this problem by trying to represent all positive integers as the sum of cubes, integers to the fourth power, and so forth, to show that any positive integer may be represented as the sum of other integers raised to a specific exponent, and that there was always a maximum number of integers raised to a certain exponent required to represent all positive integers in this way.

For every ${\displaystyle k}$, let ${\displaystyle g(k)}$ denote the minimum number ${\displaystyle s}$ of ${\displaystyle k}$th powers of naturals needed to represent all positive integers. Every positive integer is the sum of one first power, itself, so ${\displaystyle g(1)=1}$. Some simple computations show that 7 requires 4 squares, 23 requires 9 cubes,^[2] and 79 requires 19 fourth powers; these examples show that ${\displaystyle g(2)\geq 4}$, ${\displaystyle g(3)\geq 9}$, and ${\displaystyle g(4)\geq 19}$. Waring conjectured that these lower bounds were in fact exact values.^[3]

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 ${\displaystyle 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.^[4]

Over the years various bounds were established, using increasingly sophisticated and complex proof techniques. For example, Liouville showed that ${\displaystyle 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 ${\displaystyle q}$ and ${\displaystyle r}$ be defined by the Euclidean division$${\displaystyle 3^{k}=2^{k}q+r,\quad 0\leq r<2^{k},}$$or explicitly by ${\displaystyle q=\lfloor (3/2)^{k}\rfloor }$ and ${\displaystyle r=2^{k}\{(3/2)^{k}\}}$, where ${\displaystyle \lfloor x\rfloor }$ and ${\displaystyle \{x\}}$ respectively denote the integral and fractional part of a real number ${\displaystyle x}$.

Since the number ${\displaystyle 2^{k}q-1}$ is less than ${\displaystyle 3^{k}}$, as a sum of integer powers, it can only be expressed using ${\displaystyle 1^{k}}$ and ${\displaystyle 2^{k}}$. Using modular arithmetic, one shows that the fewest number of terms is achieved by the formula$${\displaystyle 2^{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 that$${\displaystyle g(k)\geq 2^{k}+q-2,}$$which was noted by J. A. Euler in about 1772.^[20] Let ${\displaystyle 4^{k}=3^{k}d+s,\,0\leq s<3^{k}}$. Combined work from the authors quoted above has led to the formula,^[21][22] valid for all ${\displaystyle k}$:$${\displaystyle g(k)={\begin{cases}2^{k}+q-2&{\text{if }}~q+r\leq 2^{k}\\2^{k}+q+d-2&{\text{if }}~q+r>2^{k}~{\text{ and }}~qd+q+d=2^{k}\\2^{k}+q+d-3&{\text{if }}~q+r>2^{k}~{\text{ and }}~qd+q+d>2^{k}.\end{cases}}}$$Dickson and Pillai both independently proved the first case, for ${\displaystyle q+r\leq 2^{k}-3}$, and the two other cases,^[23] and they noted that ${\displaystyle q+r\neq 2^{k}-1}$ for ${\displaystyle k>1}$. Rubugunday proved that ${\displaystyle q+r\neq 2^{k}}$ for all ${\displaystyle k}$, leaving the final case ${\displaystyle q+r=2^{k}-2}$ open. In this scenario, Niven proved that ${\displaystyle g(k)=2^{k}+q-2}$.

No value of ${\displaystyle k}$ is known for which the hypothesis ${\displaystyle q+r>2^{k}}$ in the last two cases holds. Mahler^[24] proved that there can only be a finite number of such ${\displaystyle k}$. Kubina and Wunderlich^[25], extending work of Stemmler^[26], have shown that any such ${\displaystyle k}$ must satisfy ${\displaystyle k>471\,600\,000}$. It is conjectured that there are no such ${\displaystyle k}$; in that case, ${\displaystyle g(k)=2^{k}+q-2}$ for every positive integer ${\displaystyle k}$.

The first few values of ${\displaystyle g(k)}$ are

1, 4, 9, 19, 37, 73, 143, 279, 548, 1079, 2132, 4223, 8384, 16673, 33203, 66190, 132055, 263619, 526502, 1051899, ... (sequence A002804 in the OEIS).

From the work of Hardy and Littlewood,^[27] the related quantity G(k) was studied with g(k). G(k) 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 positive integers to the power of k. Clearly, G(1) = 1. Since squares are congruent to 0, 1, or 4 (mod 8) (and also to 0, 1, or 4 (mod 5)^[28]) , no integer congruent to 7 (mod 8) can be represented as a sum of three squares, implying that G(2) ≥ 4. Since G(k) ≤ g(k) for all k, this shows that G(2) = 4. Davenport showed^[29] that G(4) = 16 in 1939, by demonstrating that any sufficiently large number congruent to 1 through 14 mod 16 could be written as a sum of 14 fourth powers (Vaughan in 1986^[30] and 1989^[31] reduced the 14 biquadrates successively to 13 and 12). The exact value of G(k) is unknown for any other k, but there exist bounds.

• Centered polygonal number theorem
• Fermat polygonal number theorem, that every positive integer is a sum of at most n of the n-gonal numbers
• Jacobi's four-square theorem, provides the number of ways a positive integer can be represented as the sum of 4 squares
• Pollock's conjectures
• Subset sum problem, an algorithmic problem that can be used to find the shortest representation of a given number as a sum of powers
• Sums of four cubes problem, discusses whether every integer is the sum of four cubes of integers
• Sums of three cubes, discusses what numbers are the sum of three not necessarily positive cubes
• Waring–Goldbach problem, the problem of representing numbers as sums of powers of primes