Waring's problem

Template:Short description In number theory, Waring's problem asks whether each natural number k has an associated positive integer s such that every natural number is the sum of at most s natural numbers raised to the power k. For example, every natural number is the sum of at most 4 squares, 9 cubes, or 19 fourth powers. Waring's problem was proposed in 1770 by Edward Waring, after whom it is named. Its affirmative answer, known as the Hilbert–Waring theorem, was provided by Hilbert in 1909.<ref>Template:Cite journal</ref> Waring's problem has its own Mathematics Subject Classification, 11P05, "Waring's problem and variants".

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 <math>k</math>, let <math>g(k)</math> denote the minimum number <math>s</math> of <math>k</math>th powers of naturals needed to represent all positive integers. Every positive integer is the sum of one first power, itself, so <math>g(1) = 1</math>. Some simple computations show that 7 requires 4 squares, 23 requires 9 cubes,<ref>Remember we restrict ourselves to positive natural numbers. With general integers, it is not hard to write 23 as the sum of 4 cubes, e.g. <math>2^3 + 2^3 + 2^3 + (-1)^3</math> or <math>29^3 + 17^3 + 8^3 + (-31)^3</math>.</ref> and 79 requires 19 fourth powers; these examples show that <math>g(2) \ge 4</math>, <math>g(3) \ge 9</math>, and <math>g(4) \ge 19</math>. 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 <math>g(2) = 4</math>. 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.<ref>Template:Cite book</ref>

Over the years various bounds were established, using increasingly sophisticated and complex proof techniques. For example, Liouville showed that <math>g(4)</math> is at most 53. Hardy and Littlewood showed that all sufficiently large numbers are the sum of at most 19 fourth powers.

That <math>g(3) = 9</math> was established from 1909 to 1912 by Wieferich<ref>Template:Cite journal</ref> and A. J. Kempner,<ref>Template:Cite journal</ref> <math>g(4) = 19</math> in 1986 by R. Balasubramanian, F. Dress, and J.-M. Deshouillers,<ref>Template:Cite journal</ref><ref>Template:Cite journal</ref> <math>g(5) = 37</math> in 1964 by Chen Jingrun,<ref name="ChenWaring5">Template:Cite journal</ref> and <math>g(6) = 73</math> in 1940 by Pillai.<ref>Template:Cite journal</ref>

Let <math>\lfloor x\rfloor</math> and <math>\{x\}</math> respectively denote the integral and fractional part of a positive real number <math>x</math>. Given the number <math>c = 2^k \lfloor(3/2)^k\rfloor - 1 < 3^k</math>, only <math>2^k</math> and <math>1^k</math> can be used to represent <math>c</math>; the most economical representation requires <math>\lfloor(3/2)^k\rfloor - 1</math> terms of <math>2^k</math> and <math>2^k - 1</math> terms of <math>1^k</math>. It follows that <math>g(k)</math> is at least as large as <math>2^k + \lfloor(3/2)^k\rfloor - 2</math>. This was noted by J. A. Euler, the son of Leonhard Euler, in about 1772.<ref>L. Euler, "Opera posthuma" (1), 203–204 (1862).</ref>

The Ideal Waring Theorem would be an unconditional strengthening of Euler's observation:

Define: g*(k) <math> = 2^k + \lfloor(3/2)^k\rfloor - 2</math>. Then g(k) = g*(k).

Work by Dickson and Pillai in 1936, Rubugunday<ref name="Rubugunday">Template:Cite journal</ref> in 1942, Niven in 1944<ref>Template:Cite journal</ref> and many others has proved that

<math>

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 \le 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} </math>

Dickson's 1936 proof<ref name="Dickson1936">Template:Cite journal</ref> applies when k > 6, and Pillai's<ref name="Pillai1936">Template:Cite journal</ref> when k > 7, leaving g(4), g(5), and g(6) to be resolved as documented above.

No value of <math>k</math> is known for which <math>2^k\{(3/2)^k\} + \lfloor(3/2)^k\rfloor > 2^k</math>. Mahler<ref>Template:Cite journal</ref> proved that there can only be a finite number of such <math>k</math>, and Kubina and Wunderlich<ref>Template:Cite journal</ref> have shown that any such <math>k</math> must satisfy <math>k > 471\,600\,000</math>, extending work of Stemmler.<ref name="Stemmler 1964">Template:Cite journal</ref> Thus it is conjectured that this never happens, that is, <math>g(k) = 2^k + \lfloor(3/2)^k\rfloor - 2</math> for every positive integer <math>k</math>.

The first few values of <math>g(k)</math> 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,<ref name="Hardy Littlewood 1922 pp. 161–188">Template:Cite journal</ref> 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 Template:Nowrap. Since Template:Nowrap for all k, this shows that Template:Nowrap. Davenport showed<ref>Template:Cite journal</ref> that Template:Nowrap 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<ref name="Vaughan 1986 pp. 445–463">Template:Cite journal</ref> and 1989<ref name="Vaughan 1989 pp. 1–71">Template:Cite journal</ref> 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.

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 Template:Nowrap.

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.3Template:E, Template:Val 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 Template:Nowrap;<ref>Template:Harvtxt.</ref> the largest number now known not to be a sum of 4 cubes is Template:Val,<ref name="x7373170279850">Template:Cite journal</ref> and the authors give reasonable arguments there that this may be the largest possible. The upper bound Template:Nowrap is due to Linnik in 1943.<ref>U. V. Linnik. "On the representation of large numbers as sums of seven cubes". Mat. Sb. N.S. 12(54), 218–224 (1943).</ref> (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, Template:Val and Template:Val, respectively.)

Template:Val is the largest number to require 17 fourth powers (Deshouillers, Hennecart and Landreau showed in 2000<ref name="sixteen-biquadrates">Template:Cite journal</ref> that every number between Template:Val and 10²⁴⁵ required at most 16, and Kawada, Wooley and Deshouillers extended<ref name="Deshouillers Kawada Wooley 2005 pp. 1–120">Template:Cite journal</ref> Davenport's 1939 result to show that every number above 10²²⁰ required at most 16). Numbers of the form 31·16ⁿ always require 16 fourth powers.

Template:Val is the last known number that requires 9 fifth powers (Integer sequence S001057, Tony D. Noe, Jul 04 2017), Template:Val is the last number less than 1.3Template:E that requires 10 fifth powers, and Template:Val is the last number less than 1.3Template:E that requires 11.

The upper bounds on the right with Template:Nowrap are due to Vaughan and Wooley.<ref name=Vaughan-Wooley>Template:Cite book</ref>

Using his improved Hardy–Ramanujan–Littlewood method, I. M. Vinogradov published numerous refinements leading to

<math>G(k) \le k(3\log k + 11)</math>

in 1947<ref name="Vinogradov 1947 ">Template:Cite book</ref> and, ultimately,

<math>G(k) \le k(2\log k + 2\log\log k + C\log\log\log k)</math>

for an unspecified constant C and sufficiently large k in 1959.<ref name="Math-Net.Ru z658">Template:Cite journal</ref>

Applying his p-adic form of the Hardy–Ramanujan–Littlewood–Vinogradov method to estimating trigonometric sums, in which the summation is taken over numbers with small prime divisors, Anatolii Alexeevitch Karatsuba obtained<ref>Template:Cite journal</ref> in 1985 a new estimate, for <math>k \ge 400</math>:

<math>G(k) \le k(2\log k + 2\log\log k + 12).</math>

Further refinements were obtained by Vaughan in 1989.<ref name="Vaughan 1989 pp. 1–71">Template:Cite journal</ref>

Wooley then established that for some constant C,<ref name=Vaughan>Template:Cite book</ref>

<math>G(k) \le k(\log k + \log\log k + C).</math>

Vaughan and Wooley's survey article from 2002 was comprehensive at the time.<ref name=Vaughan-Wooley/>

See also

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

References

• G. I. Arkhipov, V. N. Chubarikov, A. A. Karatsuba, "Trigonometric sums in number theory and analysis". Berlin–New-York: Walter de Gruyter, (2004).
• G. I. Arkhipov, A. A. Karatsuba, V. N. Chubarikov, "Theory of multiple trigonometric sums". Moscow: Nauka, (1987).
• Yu. V. Linnik, "An elementary solution of the problem of Waring by Schnirelman's method". Mat. Sb., N. Ser. 12 (54), 225–230 (1943).
• R. C. Vaughan, "A new iterative method in Waring's problem". Acta Mathematica (162), 1–71 (1989).
• I. M. Vinogradov, "The method of trigonometrical sums in the theory of numbers". Trav. Inst. Math. Stekloff (23), 109 pp. (1947).
• I. M. Vinogradov, "On an upper bound for G(n)". Izv. Akad. Nauk SSSR Ser. Mat. (23), 637–642 (1959).
• I. M. Vinogradov, A. A. Karatsuba, "The method of trigonometric sums in number theory", Proc. Steklov Inst. Math., 168, 3–30 (1986); translation from Trudy Mat. Inst. Steklova, 168, 4–30 (1984).
• Template:Cite journal Survey, contains the precise formula for G(k), a simplified version of Hilbert's proof and a wealth of references.
• Template:Cite book Has an elementary proof of the existence of G(k) using Schnirelmann density.
• Template:Cite book Has proofs of Lagrange's theorem, the polygonal number theorem, Hilbert's proof of Waring's conjecture and the Hardy–Littlewood proof of the asymptotic formula for the number of ways to represent N as the sum of s kth powers.
• Hans Rademacher and Otto Toeplitz, The Enjoyment of Mathematics (1933) (Template:Isbn). Has a proof of the Lagrange theorem, accessible to high-school students.

External links

• Template:Springer