number theory
Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic function, integer-valued functions. German mathematician Carl Friedrich Gauss (1777 ...
, Waring's problem asks whether each
natural number
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called ''Cardinal n ...
''k'' has an associated
positive integer
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called ''cardinal n ...
''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
Edward Waring (15 August 1798) was a British mathematician. He entered Magdalene College, Cambridge as a sizar and became Senior wrangler in 1757. He was elected a Fellow of Magdalene and in 1760 Lucasian Professor of Mathematics, holding the ...
, 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, one of the most influential mathematicians of the 19th and early 20th centuries. Hilbert discovered and developed a broad range of fundamental ideas in many ...
in 1909. Waring's problem has its own
Mathematics Subject Classification
The Mathematics Subject Classification (MSC) is an alphanumerical classification scheme collaboratively produced by staff of, and based on the coverage of, the two major mathematical reviewing databases, Mathematical Reviews and Zentralblatt MATH. ...
, 11P05, "Waring's problem and variants".
Relationship with Lagrange's four-square theorem
Long before Waring posed his problem,
Diophantus
Diophantus of Alexandria ( grc, Διόφαντος ὁ Ἀλεξανδρεύς; born probably sometime between AD 200 and 214; died around the age of 84, probably sometime between AD 284 and 298) was an Alexandrian mathematician, who was the aut ...
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 Claude may refer to:
__NOTOC__ People and fictional characters
* Claude (given name), a list of people and fictional characters
* Claude (surname), a list of people
* Claude Lorrain (c. 1600–1682), French landscape painter, draughtsman and etcher ...
, 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 , let denote the minimum number of th powers of naturals needed to represent all positive integers. Every positive integer is the sum of one first power, itself, so . Some simple computations show that 7 requires 4 squares, 23 requires 9 cubes, and 79 requires 19 fourth powers; these examples show that , , and . 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 can be represented as the sum of four integer squares. That is, the squares form an additive basis of order four.
p = a_0^2 + a_1^2 + a_2^2 + a_ ...
of 1770 states that every natural number is the sum of at most four squares. Since three squares are not enough, this theorem establishes . Lagrange's four-square theorem was conjectured in Bachet's 1621 edition of
Diophantus
Diophantus of Alexandria ( grc, Διόφαντος ὁ Ἀλεξανδρεύς; born probably sometime between AD 200 and 214; died around the age of 84, probably sometime between AD 284 and 298) was an Alexandrian mathematician, who was the aut ...
Fermat
Pierre de Fermat (; between 31 October and 6 December 1607 – 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 i ...
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
Joseph Liouville (; ; 24 March 1809 – 8 September 1882) was a French mathematician and engineer.
Life and work
He was born in Saint-Omer in France on 24 March 1809. His parents were Claude-Joseph Liouville (an army officer) and Thérèse ...
showed that is at most 53. Hardy and Littlewood showed that all sufficiently large numbers are the sum of at most 19 fourth powers.
That was established from 1909 to 1912 by Wieferich and A. J. Kempner, in 1986 by
R. Balasubramanian
Ramachandran Balasubramanian (born 15 March 1951) is an Indian mathematician and was Director of the Institute of Mathematical Sciences in Chennai, India. He is known for his work in number theory, which includes settling the final g(4) case o ...
Chen Jingrun
Chen Jingrun (; 22 May 1933 – 19 March 1996), also known as Jing-Run Chen, was a Chinese mathematician who made significant contributions to number theory, including Chen's theorem and the Chen prime.
Life and career
Chen was the third son in ...
, and in 1940 by Pillai.
Let and respectively denote the
integral
In mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented i ...
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. If the latter is defined as the largest integer not greater than , called floor of or \lfloor x\rfloor, its fractional part can ...
of a positive real number . Given the number , only and can be used to represent ; the most economical representation requires
terms of and terms of . It follows that is at least as large as . This was noted by J. A. Euler, the son of
Leonhard Euler
Leonhard Euler ( , ; 15 April 170718 September 1783) was a Swiss mathematician, physicist, astronomer, geographer, logician and engineer who founded the studies of graph theory and topology and made pioneering and influential discoveries in ma ...
, in about 1772. Later work by Dickson, Pillai, Rubugunday, Niven and many others has proved that
:
No value of is known for which .
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 , and Kubina and Wunderlich have shown that any such must satisfy . Thus it is conjectured that this never happens, that is, for every positive integer .
The first few values of 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 doesn't have the said property across all its ordered instances, but will after some instances have pa ...
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 1985 and 1989 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'')
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 10245 required at most 16, and Kawada, Wooley and Deshouillers extended Davenport's 1939 result to show that every number above 10220 required no more than 16). Numbers of the form 31·16''n'' always require 16 fourth powers.
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 () (2021 population 323,103) 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 increas ...
Hardy-Littlewood method
A twin prime is a prime number that is either 2 less or 2 more than another prime number—for example, either member of the twin prime pair (41, 43). In other words, a twin prime is a prime that has a prime gap of two. Sometimes the term ''twin pr ...
, I. M. Vinogradov published numerous refinements leading to
:
in 1947 and, ultimately,
:
for an unspecified constant ''C'' and sufficiently large ''k'' in 1959.
Applying his ''p''-adic form of the Hardy–Littlewood–Ramanujan–Vinogradov method to estimating trigonometric sums, in which the summation is taken over numbers with small prime divisors,
Anatolii Alexeevitch Karatsuba
Anatoly Alexeyevich Karatsuba (his first name often spelled Anatolii) (russian: Анато́лий Алексе́евич Карацу́ба; Grozny, Soviet Union, 31 January 1937 – Moscow, Russia, 28 September 2008) was a Russian people, Russi ...
obtained (1985) a new estimate of the Hardy function (for ):
:
Further refinements were obtained by Vaughan in 1989.
Wooley then established that for some constant ''C'',
:
Vaughan and Wooley have written a comprehensive survey article.
See also
*
Fermat polygonal number theorem
In additive number theory, the Fermat polygonal number theorem states that every positive integer is a sum of at most -gonal numbers. That is, every positive integer can be written as the sum of three or fewer triangular numbers, and as the sum ...
, that every positive integer is a sum of at most ''n'' of the ''n''-gonal numbers
*
Waring–Goldbach problem The Waring–Goldbach problem is a problem in additive number theory, concerning the representation of integers as sums of powers of prime numbers. It is named as a combination of Waring's problem on sums of powers of integers, and the Goldbach con ...
, the problem of representing numbers as sums of powers of primes
*
Subset sum problem The subset sum problem (SSP) is a decision problem in computer science. In its most general formulation, there is a multiset S of integers and a target-sum T, and the question is to decide whether any subset of the integers sum to precisely T''.'' T ...
, an algorithmic problem that can be used to find the shortest representation of a given number as a sum of powers
*
Sums of three cubes
In the mathematics of sums of powers, it is an open problem to characterize the numbers that can be expressed as a sum of three cubes of integers, allowing both positive and negative cubes in the sum. A necessary condition for n to equal such a ...
, discusses what numbers are the sum of three ''not necessarily positive'' cubes
* Sums of four cubes problem, discusses whether every rational integer is the sum of four cubes of rational integers
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
Yuri Vladimirovich Linnik (russian: Ю́рий Влади́мирович Ли́нник; January 8, 1915 – June 30, 1972) was a Soviet mathematician active in number theory, probability theory and mathematical statistics.
Linnik was born in ...
, "An elementary solution of the problem of Waring by Schnirelman's method". ''Mat. Sb., N. Ser.'' 12 (54), 225–230 (1943).
*
R. C. Vaughan
Robert Charles "Bob" Vaughan FRS (born 24 March 1945) is a British mathematician, working in the field of analytic number theory.
Life
Since 1999 he has been Professor at Pennsylvania State University, and since 1990 Fellow of the Royal Soci ...
, "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
In additive number theory, the Schnirelmann density of a sequence of numbers is a way to measure how "dense" the sequence is. It is named after Russian mathematician Lev Schnirelmann, who was the first to study it.Schnirelmann, L.G. (1930).On the ...
.
* Has proofs of Lagrange's theorem, the
polygonal number theorem
In additive number theory, the Fermat polygonal number theorem states that every positive integer is a sum of at most Polygonal number, -gonal numbers. That is, every positive integer can be written as the sum of three or fewer triangular number ...
, 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, Wandsbeck, now Hamburg-Wandsbek – 7 February 1969, Haverford, Pennsylvania, USA) was a German-born American mathematician, known for work in mathematical analysis and number theory.
Biography
Rademacher r ...
and
Otto Toeplitz
Otto Toeplitz (1 August 1881 – 15 February 1940) was a German mathematician working in functional analysis., reprinted in
Life and work
Toeplitz was born to a Jewish family of mathematicians. Both his father and grandfather were ''Gymnasiu ...
, ''The Enjoyment of Mathematics'' (1933) (). Has a proof of the Lagrange theorem, accessible to high-school students.