# Waring's problem

Contents 1 Relationship with Lagrange's four-square theorem 2 The number g(k) 3 The number G(k) 3.1 Lower bounds for G(k) 3.2 Upper bounds for G(k) 4 See also 5 Notes 6 References 7 External links Relationship with Lagrange's four-square theorem 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.

The number g(k) 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, 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.

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. 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.

That {displaystyle g(3)=9} was established from 1909 to 1912 by Wieferich and A. J. Kempner, {displaystyle g(4)=19} in 1986 by R. Balasubramanian, F. Dress, and J.-M. Deshouillers, {displaystyle g(5)=37} in 1964 by Chen Jingrun, and {displaystyle g(6)=73} in 1940 by Pillai. Let {displaystyle lfloor xrfloor } and {displaystyle {x}} respectively denote the integral and fractional part of a positive real number {displaystyle x} . Given the number {displaystyle c=2^{k}lfloor (3/2)^{k}rfloor -1<3^{k}} , only {displaystyle 2^{k}} and {displaystyle 1^{k}} can be used to represent {displaystyle c} ; the most economical representation requires {displaystyle lfloor (3/2)^{k}rfloor -1} terms of {displaystyle 2^{k}} and {displaystyle 2^{k}-1} terms of {displaystyle 1^{k}} . It follows that {displaystyle g(k)} is at least as large as {displaystyle 2^{k}+lfloor (3/2)^{k}rfloor -2} . This was noted by J. A. Euler, the son of Leonhard Euler, in about 1772. Later work by Dickson, Pillai, Rubugunday, Niven and many others has proved that {displaystyle g(k)={begin{cases}2^{k}+lfloor (3/2)^{k}rfloor -2&{text{if}}quad 2^{k}{(3/2)^{k}}+lfloor (3/2)^{k}rfloor leq 2^{k},\2^{k}+lfloor (3/2)^{k}rfloor +lfloor (4/3)^{k}rfloor -2&{text{if}}quad 2^{k}{(3/2)^{k}}+lfloor (3/2)^{k}rfloor >2^{k}{text{ and }}lfloor (4/3)^{k}rfloor lfloor (3/2)^{k}rfloor +lfloor (4/3)^{k}rfloor +lfloor (3/2)^{k}rfloor =2^{k},\2^{k}+lfloor (3/2)^{k}rfloor +lfloor (4/3)^{k}rfloor -3&{text{if}}quad 2^{k}{(3/2)^{k}}+lfloor (3/2)^{k}rfloor >2^{k}{text{ and }}lfloor (4/3)^{k}rfloor lfloor (3/2)^{k}rfloor +lfloor (4/3)^{k}rfloor +lfloor (3/2)^{k}rfloor >2^{k}.end{cases}}} No value of {displaystyle k} is known for which {displaystyle 2^{k}{(3/2)^{k}}+lfloor (3/2)^{k}rfloor >2^{k}} . Mahler proved that there can only be a finite number of such {displaystyle k} , and Kubina and Wunderlich have shown that any such {displaystyle k} must satisfy {displaystyle k>471,600,000} . Thus it is conjectured that this never happens, that is, {displaystyle g(k)=2^{k}+lfloor (3/2)^{k}rfloor -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). The number G(k) From the work of Hardy and Littlewood,[citation needed] 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), 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[citation needed] 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 1985[citation needed] and 1989[citation needed] reduced the 14 successively to 13 and 12). The exact value of G(k) is unknown for any other k, but there exist bounds.

Lower bounds for G(k) Bounds 1 = G(1) = 1 4 = G(2) = 4 4 ≤ G(3) ≤ 7 16 = G(4) = 16 6 ≤ G(5) ≤ 17 9 ≤ G(6) ≤ 24 8 ≤ G(7) ≤ 33 32 ≤ G(8) ≤ 42 13 ≤ G(9) ≤ 50 12 ≤ G(10) ≤ 59 12 ≤ G(11) ≤ 67 16 ≤ G(12) ≤ 76 14 ≤ G(13) ≤ 84 15 ≤ G(14) ≤ 92 16 ≤ G(15) ≤ 100 64 ≤ G(16) ≤ 109 18 ≤ G(17) ≤ 117 27 ≤ G(18) ≤ 125 20 ≤ G(19) ≤ 134 25 ≤ G(20) ≤ 142 The number G(k) is greater than or equal to 2r+2 if k = 2r with r ≥ 2, or k = 3 × 2r; pr+1 if p is a prime greater than 2 and k = pr(p − 1); (pr+1 − 1)/2   if p is a prime greater than 2 and k = pr(p − 1)/2; k + 1 for all integers k greater than 1.

In the absence of congruence restrictions, a density argument suggests that G(k) should equal k + 1.

Upper bounds for G(k) G(3) is at least 4 (since cubes are congruent to 0, 1 or −1 mod 9); for numbers less than 1.3×109, 1290740 is the last to require 6 cubes, and the number of numbers between N and 2N requiring 5 cubes drops off with increasing N at sufficient speed to have people believe that G(3) = 4; the largest number now known not to be a sum of 4 cubes is 7373170279850, and the authors give reasonable arguments there that this may be the largest possible. The upper bound G(3) ≤ 7 is due to Linnik in 1943. (All nonnegative integers require at most 9 cubes, and the largest integers requiring 9, 8, 7, 6 and 5 cubes are conjectured to be 239, 454, 8042, 1290740 and 7373170279850, respectively.) 13792 is the largest number to require 17 fourth powers (Deshouillers, Hennecart and Landreau showed in 2000 that every number between 13793 and 10245 required at most 16, and Kawada, Wooley and Deshouillers extended[citation needed] Davenport's 1939 result to show that every number above 10220 required no more than 16). Numbers of the form 31·16n always require 16 fourth powers.

617597724 is the last number less than 1.3×109 that requires 10 fifth powers, and 51033617 is the last number less than 1.3×109 that requires 11.

The upper bounds on the right with k = 5, 6, ..., 20 are due to Vaughan and Wooley. Using his improved Hardy-Littlewood method, I. M. Vinogradov published numerous refinements leading to {displaystyle G(k)leq k(3log k+11)} in 1947[citation needed] and, ultimately, {displaystyle G(k)leq k(2log k+2log log k+Clog log log k)} for an unspecified constant C and sufficiently large k in 1959[citation needed].