number theory Number theory is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic functions. Number theorists study prime numbers as well as the properties of mathematical objects constructed from integers (for example ...

, Waring's problem asks whether each

natural number In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positive in ...

''k'' has an associated

positive integer In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positiv ...

''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 David Hilbert (; ; 23 January 1862 – 14 February 1943) was a German mathematician and philosophy of mathematics, philosopher of mathematics and one of the most influential mathematicians of his time. Hilbert discovered and developed a broad ...

in 1909. Waring's problem has its own

Mathematics Subject Classification The Mathematics Subject Classification (MSC) is an alphanumerical classification scheme that has collaboratively been produced by staff of, and based on the coverage of, the two major mathematical reviewing databases, Mathematical Reviews and Zen ...

, 11P05, "Waring's problem and variants".

Relationship with Lagrange's four-square theorem

Long before Waring posed his problem,

Diophantus Diophantus of Alexandria () (; ) was a Greek mathematician who was the author of the '' Arithmetica'' in thirteen books, ten of which are still extant, made up of arithmetical problems that are solved through algebraic equations. Although Jose ...

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 Joseph-Louis Lagrange (born Giuseppe Luigi Lagrangiafour-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

k

, let

g(k)

denote the minimum number

s

k

th 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 Lagrange's four-square theorem, also known as Bachet's conjecture, states that every natural number, nonnegative integer can be represented as a sum of four non-negative integer square number, squares. That is, the squares form an additive basi ...

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

's ''

Arithmetica Diophantus of Alexandria () (; ) was a Greek mathematics, Greek mathematician who was the author of the ''Arithmetica'' in thirteen books, ten of which are still extant, made up of arithmetical problems that are solved through algebraic equations ...

'';

Fermat Pierre de Fermat (; ; 17 August 1601 – 12 January 1665) was a French mathematician who is given credit for early developments that led to infinitesimal calculus, including his technique of adequality. In particular, he is recognized for his d ...

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

g(3) = 9

was established from 1909 to 1912 by Wieferich and A. J. Kempner,

g(4) = 19

in 1986 by R. Balasubramanian, F. Dress, and J.-M. Deshouillers,

g(5) = 37

in 1964 by Chen Jingrun, and

g(6) = 73

in 1940 by Pillai. Let

\lfloor x\rfloor

and

\

respectively denote the

integral In mathematics, an integral is the continuous analog of a Summation, sum, which is used to calculate area, areas, volume, volumes, and their generalizations. Integration, the process of computing an integral, is one of the two fundamental oper ...

and

fractional part The fractional part or decimal part of a non‐negative real number x is the excess beyond that number's integer part. The latter is defined as the largest integer not greater than , called ''floor'' of or \lfloor x\rfloor. Then, the fractional ...

of a positive real number

x

. Given the number

c = 2^k \lfloor(3/2)^k\rfloor - 1 < 3^k

, only

2^k

and

1^k

can be used to represent

c

; the most economical representation requires

\lfloor(3/2)^k\rfloor - 1

terms of

2^k

and

2^k - 1

terms of

1^k

. It follows that

g(k)

is at least as large as

2^k + \lfloor(3/2)^k\rfloor - 2

. This was noted by J. A. Euler, the son of

Leonhard Euler Leonhard Euler ( ; ; ; 15 April 170718 September 1783) was a Swiss polymath who was active as a mathematician, physicist, astronomer, logician, geographer, and engineer. He founded the studies of graph theory and topology and made influential ...

, in about 1772. The Ideal Waring Theorem would be an unconditional strengthening of Euler's observation: : Define: g*(k)

= 2^k + \lfloor(3/2)^k\rfloor - 2

. Then g(k) = g*(k). Work by Dickson and Pillai in 1936, Rubugunday in 1942, Niven in 1944 and many others has proved that :

g(k) = \begin
 2^k + \lfloor(3/2)^k\rfloor - 2
  &\text\quad
  2^k \ + \lfloor(3/2)^k\rfloor \le 2^k, \\
 2^k + \lfloor(3/2)^k\rfloor + \lfloor(4/3)^k\rfloor - 2
  &\text\quad
  2^k \ + \lfloor(3/2)^k\rfloor > 2^k
  \text
  \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\quad
  2^k \ + \lfloor(3/2)^k\rfloor > 2^k
  \text
  \lfloor(4/3)^k\rfloor \lfloor(3/2)^k\rfloor + \lfloor(4/3)^k\rfloor + \lfloor(3/2)^k\rfloor > 2^k.
\end

Dickson's 1936 proof applies when k > 6, and Pillai's when k > 7, leaving g(4), g(5), and g(6) to be resolved as documented above. No value of

k

is known for which

2^k\ + \lfloor(3/2)^k\rfloor > 2^k

Mahler Gustav Mahler (; 7 July 1860 – 18 May 1911) was an Austro-Bohemian Romantic composer, and one of the leading conductors of his generation. As a composer he acted as a bridge between the 19th-century Austro-German tradition and the modernism ...

proved that there can only be a finite number of such

k

, and Kubina and Wunderlich have shown that any such

k

must satisfy

k > 471\,600\,000

, extending work of Stemmler. Thus it is conjectured that this never happens, that is,

g(k) = 2^k + \lfloor(3/2)^k\rfloor - 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'')

From the work of Hardy and Littlewood, 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 In the mathematical areas of number theory and analysis, an infinite sequence or a function is said to eventually have a certain property, if it does not have the said property across all its ordered instances, but will after some instances have ...

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 . Since for all ''k'', this shows that . Davenport showed that 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 and 1989 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'')

The number ''G''(''k'') is greater than or equal to : In the absence of congruence restrictions, a density argument suggests that ''G''(''k'') should equal .

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, is the last to require 6 cubes, and the number of numbers between ''N'' and 2''N'' requiring 5 cubes drops off with increasing ''N'' at sufficient speed to have people believe that ; the largest number now known not to be a sum of 4 cubes is , and the authors give reasonable arguments there that this may be the largest possible. The upper bound 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, and , respectively.) is the largest number to require 17 fourth powers (Deshouillers, Hennecart and Landreau showed in 2000 that every number between and 10²⁴⁵ required at most 16, and Kawada, Wooley and Deshouillers extended Davenport's 1939 result to show that every number above 10²²⁰ required at most 16). Numbers of the form 31·16^''n'' always require 16 fourth powers. is the last known number that requires 9 fifth powers (Integer sequence S001057, Tony D. Noe, Jul 04 2017), is the last number less than 1.3 that requires 10 fifth powers, and is the last number less than 1.3 that requires 11. The upper bounds on the right with are due to

Vaughan Vaughan ( ) (2022 population 344,412) is a city in Ontario, Canada. It is located in the Regional Municipality of York, just north of Toronto. Vaughan was the fastest-growing municipality in Canada between 1996 and 2006 with its population increa ...

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

G(k) \le k(3\log k + 11)

in 1947 and, ultimately, :

G(k) \le k(2\log k + 2\log\log k + C\log\log\log k)

for an unspecified constant ''C'' and sufficiently large ''k'' in 1959. 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 in 1985 a new estimate, for

k \ge 400

: :

G(k) \le k(2\log k + 2\log\log k + 12).

Further refinements were obtained by Vaughan in 1989. Wooley then established that for some constant ''C'', :

G(k) \le k(\log k + \log\log k + C).

Vaughan and Wooley's survey article from 2002 was comprehensive at the time.

Notes

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). * Survey, contains the precise formula for ''G''(''k''), a simplified version of Hilbert's proof and a wealth of references. * Has an elementary proof of the existence of ''G''(''k'') using Schnirelmann density. * 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'' ''k''th powers. *

Hans Rademacher Hans Adolph Rademacher (; 3 April 1892 – 7 February 1969) was a German-born American mathematician, known for work in mathematical analysis and number theory. Biography Rademacher received his Ph.D. in 1916 from Georg-August-Universität Göt ...

and Otto Toeplitz, ''The Enjoyment of Mathematics'' (1933) (). Has a proof of the Lagrange theorem, accessible to high-school students.

External links

* {{DEFAULTSORT:Waring's Problem Additive number theory Mathematical problems Unsolved problems in number theory Squares in number theory