Waring's Problem

In his Meditationes algebraicae, Waring (1770, 1782) proposed a generalization of Lagrange's four-square theorem, stating that every rational integer is the sum of a fixed number g(n) of nth powers of integers, where n is any given positive integer and g(n) depends only on n. Waring originally speculated that , , and . In 1909, Hilbert proved the general conjecture using an identity in 25-fold multiple integrals (Rademacher and Toeplitz 1957, pp. 52-61).

In Lagrange's four-square theorem, Lagrange proved that , where 4 may be reduced to 3 except for numbers of the form (as proved by Legendre ; Hardy 1999, p. 12). In 1909, Wieferich proved that . In 1859, Liouville proved (using Lagrange's four-square theorem and Liouville polynomial identity) that . Hardy, and Little established , and this was subsequently reduced to by Balasubramanian et al. (1986). For the case , Maillet (1896) began with a proof that , Wieferich (1909) proved , and Chen (1964) proved that .

Dickson (1936), Pillai (1936), and Niven also conjectured an explicit formula for g(s) for s > 6 (Bell 1945, pp. 318 and 602), based on the relationship

(1)

If the Diophantine (i.e., n is restricted to being an integer) inequality

(2)

is true, where is the fractional part of x, then

(3)

This was given as a lower bound by J. A. Euler, son of Leonhard Euler, and has been verified to be correct for (Kubina and Wunderlich 1990, extending Stemmler 1990). Furthermore, Mahler (1957) proved that at most a finite number of n exceed Euler's lower bound. Unfortunately, the proof is nonconstructive.

There is also a related (but more difficult) problem of finding the least integer n such that every positive integer beyond a certain point (i.e., all but a finite number) is the sum of G(n) nth powers. From 1920-1928, Hardy and Littlewood showed that

(4)

and conjectured that

(5)

Heilbronn (1936) improved results by Vinogradov to obtain

(6)

If , then

(7)

(Karatsuba 1985), and for large k,

(8)

for any positive c (Wooley 1991).

It has long been known that . Deshouillers et al. (2000) conjectured that 7373170279850 is the largest integer that cannot be expressed as the sum of four nonnegative cubes.

Landau (1909) established that , and Dickson (1939) showed that the only integers requiring nine cubes are 23 and 239. Wieferich proved that only 15 integers require eight cubes: 15, 22, 50, 114, 167, 175, 186, 212, 231, 238, 303, 364, 420, 428, and 454 (Sloane's A018889), establishing (Wells 1986, p. 70). The largest number known requiring seven cubes is 8042.

In 1933, Hardy and Littlewood showed that , but this was improved in 1936 to 16 or 17, and shown to be exactly 16 by Davenport (1939b). Vaughan (1986) greatly improved on the method of Hardy and Littlewood, obtaining improved results for . These results were then further improved by Brüdern (1990), who gave , and Wooley (1992), who gave G(n) for n = 6 to 20. Vaughan and Wooley (1993) showed .

Let denote the smallest number such that almost all sufficiently large integers are the sum of nth powers. Then (Davenport 1939a), (Hardy and Littlewood 1925), (Vaughan 1986), and (Wooley 1992). If the negatives of powers are permitted in addition to the powers themselves, the largest number of nth powers needed to represent an arbitrary integer are denoted and (Wright 1934, Hunter 1941, Gardner 1986). In general, these values are much harder to calculate than are g(n) and G(n).

The following table gives g(n), G(n), , , and for . The sequence of g(n) is Sloane's A002804.

n	g(n)	G(n)
2	4	4	3	3
3	9		[4, 5]
4	19	16	[9, 10]
5	37
6	73
7	143
8	279
9	548
10	1079
11	2132
12	4223
13	8384
14	16673
15	33203
16	66190
17	132055
18	263619
19	526502
20	1051899

Euler's Conjecture, Schnirelmann Constant, Schnirelmann's Theorem, Vinogradov's Theorem

Archibald, R. G. "Waring's Problem: Squares." Scripta Math. 7, 33-48, 1940.

Balasubramanian, R.; Deshouillers, J.-M.; and Dress, F. "Problème de Waring pour les bicarrés 1, 2." C. R. Acad. Sci. Paris Sér. I Math. 303, 85-88 and 161-163, 1986.

Bell, E. T. The Development of Mathematics, 2nd ed. New York: McGraw-Hill, 1945.

Brüdern, J. "On Waring's Problem for Fifth Powers and Some Related Topics." Proc. London Math. Soc. 61, 457-479, 1990.

Chen, J.-R. "Waring's Problem for . Sci. Sinica 13, 1547-1568, 1964. Also appeared as Chinese Math Acta 6, 105-127, 1965.

Davenport, H. "On Waring's Problem for Cubes." Acta Math. 71, 123-143, 1939a.

Davenport, H. "On Waring's Problem for Fourth Powers." Ann. Math. 40, 731-747, 1939b.

Deshouillers, J.-M.; Hennecart, F.; and Landreau, B. "7 373 170 279 850." Math. Comput. 69, 421-439, 2000.

Dickson, L. E. "Waring's Problem and Related Results." Ch. 25 in History of the Theory of Numbers, Vol. 2: Diophantine Analysis. New York: Chelsea, pp. 717-729, 1952.

Gardner, M. "Waring's Problems." Ch. 18 in Knotted Doughnuts and Other Mathematical Entertainments. New York: W. H. Freeman, pp. 222-231, 1986.

Guy, R. K. "Sums of Squares." §C20 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 136-138, 1994.

Hardy, G. H. Ramanujan: Twelve Lectures on Subjects Suggested by His Life and Work, 3rd ed. New York: Chelsea, 1999.

Hardy, G. H. and Littlewood, J. E. "Some Problems of Partitio Numerorum (VI): Further Researches in Waring's Problem." Math. Z. 23, 1-37, 1925.

Hardy, G. H. and Wright, E. M. "The Representation of a Number by Two or Four Squares" and "Representation by Cubes and Higher Powers." Chs. 20-21 in An Introduction to the Theory of Numbers, 5th ed. Oxford, England: Clarendon Press, pp. 297-339, 1979.

Heilbronn, H. "Über das waringsche Problem." Acta Arith. 1, 212-221, 1936.

Hunter, W. "The Representation of Numbers by Sums of Fourth Powers." J. London Math. Soc. 16, 177-179, 1941.

Karatsuba, A. A. "The Function G(n) in Waring's Problem." Izv. Akad. Nauk SSSR Ser. Mat. 49, 935-947 and 1119, 1985.

Khinchin, A. Y. "An Elementary Solution of Waring's Problem." Ch. 3 in Three Pearls of Number Theory. New York: Dover, pp. 37-64, 1998.

Kubina, J. M. and Wunderlich, M. C. "Extending Waring's Conjecture to ." Math. Comput. 55, 815-820, 1990.

Landau, E. "Über eine Anwendung der Primzahlen auf das Waringsche Problem in der elementaren Zahlentheorie." Math. Ann. 66, 102-105, 1909.

Mahler, K. "On the Fractional Parts of the Powers of a Rational Number (II)." Mathematica 4, 122-124, 1957.

Rademacher, H. and Toeplitz, O. The Enjoyment of Mathematics: Selections from Mathematics for the Amateur. Princeton, NJ: Princeton University Press, 1957.

Sloane, N. J. A. Sequences A018889 and A002804/M3361 in "The On-Line Encyclopedia of Integer Sequences." http://www.research.att.com/~njas/sequences/.

Small, C. "Waring's Problem." Math. Mag. 50, 12-16, 1977.

Stemmler, R. M. "The Ideal Waring Theorem for Exponents 401-." Math. Comput. 55, 815-820, 1990.

Stewart, I. "The Waring Experience." Nature 323, 674, 1986.

Vaughan, R. C. "On Waring's Problem for Smaller Exponents." Proc. London Math. Soc. 52, 445-463, 1986.

Vaughan, R. C. and Wooley, T. D. "On Waring's Problem: Some Refinements." Proc. London Math. Soc. 63, 35-68, 1991.

Vaughan, R. C. and Wooley, T. D. "Further Improvements in Waring's Problem." Phil. Trans. Roy. Soc. London A 345, 363-376, 1993a.

Vaughan, R. C. and Wooley, T. D. "Further Improvements in Waring's Problem III. Eighth Powers." Phil. Trans. Roy. Soc. London A 345, 385-396, 1993b.

Vaughan, R. C. and Wooley, T. D. "Waring's Problem: A Survey." http://www.math.lsa.umich.edu/~wooley/wps.ps.

Waring, E. Meditationes algebraicae. Cambridge, England: pp. 204-205, 1770.

Waring, E. Meditationes algebraicae, 3rd ed. Cambridge, England: pp. 349-350, 1782.

Waring, E. Meditationes Algebraicae: An English Translation of the Work of Edward Waring. Providence, RI: Amer. Math. Soc., 1991.

Wells, D. The Penguin Dictionary of Curious and Interesting Numbers. Middlesex, England: Penguin Books, pp. 70 and 75, 1986.

Wooley, T. D. "Large Improvements in Waring's Problem." Ann. Math. 135, 131-164, 1992.

Wright, E. M. "An Easier Waring's Problem." J. London Math. Soc. 9, 267-272, 1934.