|
|
| (One intermediate revision by one other user not shown) |
| Line 1: |
Line 1: |
| In [[number theory]], '''Waring's problem''', proposed in 1770 by [[Edward Waring]], asks whether for every [[natural number]] ''k'' there exists an associated [[positive integer]] ''s'' such that every natural number is the sum of at most ''s'' ''k''<sup>th</sup> powers of natural numbers (for example, every number is the sum of at most 4 squares, or 9 cubes, or 19 fourth powers, etc.). The affirmative answer, known as the '''Hilbert–Waring theorem''', was provided by [[David Hilbert|Hilbert]] in 1909.<ref>{{cite journal|author=D. Hilbert |title=Beweis für die Darstellbarkeit der ganzen Zahlen durch eine feste Anzahl n-ter Potenzen (Waringsches Problem) |journal=Mathematische Annalen |volume=67 | pages=281-300 |year=1909 |url=http://gdz.sub.uni-goettingen.de/index.php?id=11&PPN=PPN235181684_0067&DMDID=DMDLOG_0029&L=1}}</ref> Waring's problem has its own [[Mathematics Subject Classification]], 11P05, "Waring's problem and variants."
| | My name is Delmar (27 years old) and my hobbies are Radio-Controlled Car Racing and Shortwave listening.<br><br>Also visit my web-site - [http://Anecdotarioscout.blogspot.fr/2013/05/para-ir-al-jamboree-2012.html FIFA coin generator] |
| | |
| ==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 [[Lagrange's four-square theorem|sum of four perfect squares]] greater than or equal to zero; this 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 [[Lagrange's four-square theorem|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 ''k'', we denote by ''g''(''k'') the minimum number ''s'' of ''k''<sup>th</sup> powers needed to represent all integers. Note we have ''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) ≥ 4, ''g''(3) ≥ 9, and ''g''(4) ≥ 19. Waring conjectured that these values were in fact the best possible.
| |
| | |
| [[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 ''g''(2) = 4. Lagrange's four-square theorem was conjectured in [[Claude Gaspard Bachet de Méziriac|Bachet]]'s 1621 edition of [[Diophantus]]'s [[Arithmetica]]; [[Pierre de Fermat|Fermat]] claimed to have a proof, but did not publish it.<ref>{{cite book | last = Dickson | first = Leonard Eugene | authorlink = Leonard Eugene Dickson | title = [[History of the Theory of Numbers]], Volume II: Diophantine Analysis | publisher = [[Carnegie Institution of Washington|Carnegie Institute of Washington]] | year = 1920 | chapter = Chapter VIII}}</ref>
| |
| | |
| Over the years various bounds were established, using increasingly sophisticated and complex proof techniques. For example, [[Joseph Liouville|Liouville]] showed that ''g''(4) is at most 53. [[G. H. Hardy|Hardy]] and [[John Edensor Littlewood|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 [[Arthur Wieferich|Wieferich]]<ref>{{cite journal | last = Wieferich | first = Arthur | authorlink = Arthur Wieferich | title = Beweis des Satzes, daß sich eine jede ganze Zahl als Summe von höchstens neun positiven Kuben darstellen läßt | journal = Mathematische Annalen | volume = 66 | issue = 1 | pages = 95–101 | year = 1909 | url = http://dz-srv1.sub.uni-goettingen.de/sub/digbib/loader?did=D38240 | doi = 10.1007/BF01450913}}</ref> and [[Aubrey J. Kempner|A. J. Kempner]],<ref>{{cite journal | last = Kempner | first = Aubrey | title = Bemerkungen zum Waringschen Problem | journal = Mathematische Annalen | volume = 72 | issue = 3 | pages = 387–399 | year=1912 | url = http://dz-srv1.sub.uni-goettingen.de/sub/digbib/loader?did=D28751 | doi = 10.1007/BF01456723}}</ref> ''g''(4) = 19 in 1986 by [[Ramachandran Balasubramanian|R. Balasubramanian]], F. Dress, and [[Jean-Marc Deshouillers|J.-M. Deshouillers]],<ref>Balasubramanian, Ramachandran; Deshouillers, Jean-Marc; Dress, François, ''Problème de Waring pour les bicarrés. I. Schéma de la solution.'' (French. English summary) [Waring's problem for biquadrates. I. Sketch of the solution] C. R. Acad. Sci. Paris Sér. I Math. 303 (1986), no. 4, pp. 85-88</ref><ref>Balasubramanian, Ramachandran; Deshouillers, Jean-Marc; Dress, François, ''Problème de Waring pour les bicarrés. II. Résultats auxiliaires pour le théorème asymptotique.'' (French. English summary) [Waring's problem for biquadrates. II. Auxiliary results for the asymptotic theorem] C. R. Acad. Sci. Paris Sér. I Math. 303 (1986), no. 5, pp. 161-163</ref> ''g''(5) = 37 in 1964 by [[Chen Jingrun]], and ''g''(6) = 73 in 1940 by [[Subbayya Sivasankaranarayana Pillai|Pillai]].<ref>{{cite journal | last1 = Pillai | first1 = S. S. | year = | title = On Waring's problem g(6)=73 | url = | journal = Proc. Indian Acad. Sci. | volume = 12A | issue = | pages = 30–40 }}</ref>
| |
| | |
| Let [''x''] and {''x''} denote the [[integral part|integral]] and [[fractional part]] of ''x'' respectively. Since 2<sup>k</sup>[(3/2)<sup>k</sup>]-1<3<sup>k</sup> only 2<sup>k</sup> and 1<sup>k</sup> can be used to represent this number and the most economical representation requires [(3/2)<sup>k</sup>]-1 2<sup>k</sup>s and 2<sup>k</sup>-1 1<sup>k</sup>s it follows that g(k) is at least as large as 2<sup>''k''</sup> + [(3/2)<sup>''k''</sup>] − 2. J. A. Euler, the son of [[Leonhard Euler]], conjectured about 1772 that, in fact, g(k) = 2<sup>''k''</sup> + [(3/2)<sup>''k''</sup>] − 2.<ref>[[Euler|L. Euler]] "Opera postuma" (1), 203-204 (1862)</ref> Later work by [[Leonard Eugene Dickson|Dickson]], [[Subbayya Sivasankaranarayana Pillai|Pillai]], [[R. K. Rubugunday|Rubugunday]], [[Ivan M. Niven|Niven]]<ref>{{cite journal|author = Niven, Ivan M.|authorlink = Ivan M. Niven|title = An unsolved case of the Waring problem|journal = [[American Journal of Mathematics]]|volume = 66|pages = 137–143|year = 1944|issue = 1|doi = 10.2307/2371901|publisher = The Johns Hopkins University Press|jstor = 2371901}}</ref> and many others have proved that
| |
| | |
| :g(k) = 2<sup>''k''</sup> + [(3/2)<sup>''k''</sup>] − 2 if 2<sup>''k''</sup>{(3/2)<sup>''k''</sup>} + [(3/2)<sup>''k''</sup>] ≤ 2<sup>''k''</sup>
| |
| | |
| :g(k) = 2<sup>''k''</sup> + [(3/2)<sup>''k''</sup>] + [(4/3)<sup>''k''</sup>] − 2 if 2<sup>''k''</sup>{(3/2)<sup>''k''</sup>} + [(3/2)<sup>''k''</sup>] > 2<sup>''k''</sup> and [(4/3)<sup>''k''</sup>][(3/2)<sup>''k''</sup>] + [(4/3)<sup>''k''</sup>] + [(3/2)<sup>''k''</sup>] = 2<sup>''k''</sup>
| |
| | |
| :g(k) = 2<sup>''k''</sup> + [(3/2)<sup>''k''</sup>] + [(4/3)<sup>''k''</sup>] − 3 if 2<sup>''k''</sup>{(3/2)<sup>''k''</sup>} + [(3/2)<sup>''k''</sup>] > 2<sup>''k''</sup> and [(4/3)<sup>''k''</sup>][(3/2)<sup>''k''</sup>] + [(4/3)<sup>''k''</sup>] + [(3/2)<sup>''k''</sup>] > 2<sup>''k''</sup>.
| |
| | |
| No values of ''k'' are known for which 2<sup>''k''</sup>{(3/2)<sup>''k''</sup>} + [(3/2)<sup>''k''</sup>] > 2<sup>''k''</sup>, [[Kurt Mahler|Mahler]]<ref>{{cite journal | last1 = Mahler | first1 = K. | year =1957 | title = On the fractional parts of the powers of a rational number II | url = | journal = Mathematika | volume = 4 | issue = | pages = 122–124 }}</ref> has proved there can only be a finite number of such ''k'' and Kubina and Wunderlich <ref>Kubina, J. M. and Wunderlich, M. C. "Extending Waring's
| |
| conjecture to 471,600,000" ''Math. Comp.'' (55) 815--820 (1990)</ref> have shown that any such ''k'' must satisfy ''k'' > 471,600,000. Thus it is conjectured that this never happens, i.e. that g(k) = 2<sup>''k''</sup> + [(3/2)<sup>''k''</sup>] − 2 for each positive integer ''k''.
| |
| | |
| The first few values of g(k) are:
| |
| : [[1 (number)|1]], [[4 (number)|4]], [[9 (number)|9]], [[19 (number)|19]], [[37 (number)|37]], [[73 (number)|73]], [[143 (number)|143]], 279, 548, 1079, 2132, 4223, 8384, 16673, 33203, 66190, 132055 ... {{OEIS|A002804}}.
| |
| | |
| ==The number ''G''(''k'')==
| |
| From the work of [[G. H. Hardy|Hardy]] and [[John Edensor Littlewood|Littlewood]], the related quantity ''G''(''k'') turned out to be more fundamental than ''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'' ''k''<sup>th</sup> powers of positive integers. 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. [[Harold Davenport|Davenport]] showed 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 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'')===
| |
| | |
| {| class="wikitable" style="float:right; text-align: center"
| |
| ! Bounds
| |
| |-
| |
| | 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
| |
| :2<sup>''r'' + 2</sup> if ''k'' = 2<sup>''r''</sup> with ''r'' ≥ 2, or ''k'' = 3×2<sup>''r''</sup>;
| |
| :''p''<sup>''r'' + 1</sup> if ''p'' is a prime greater than 2 and ''k'' = ''p''<sup>''r''</sup>(''p'' − 1);
| |
| :(''p''<sup>''r'' + 1</sup> − 1)/2 if ''p'' is a prime greater than 2 and ''k'' = p<sup>''r''</sup>(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 four (since cubes are congruent to 0, 1 or −1 mod 9); for numbers less than 1.3{{e|9}}, 1290740 is the last to require six cubes, and the number of numbers between N and 2N requiring five cubes drops off with increasing N at sufficient speed to have people believe G(3)=4;<ref>Nathanson (1996)p.71</ref> the largest number now known not to be a sum of four cubes is 7373170279850,<ref name="x7373170279850">{{cite journal|last1=Deshouillers|first1=Jean-Marc|last2=Hennecart|first2= François |last3=Landreau|first3= Bernard|last4=I. Gusti Putu Purnaba|first4=Appendix by |title=7373170279850|journal=Mathematics of Computation|volume=69|issue=229|year=2000|pages=421–439|doi=10.1090/S0025-5718-99-01116-3}}</ref> and the authors give reasonable arguments there that this may be the largest possible. The upper bound G(3) ≤ 7 is due to Linnik.<ref>Nathanson (1996) p.46,71</ref>
| |
| | |
| 13792 is the largest number to require seventeen fourth powers (Deshouillers, Hennecart and Landreau showed in 2000<ref name="sixteen-biquadrates">{{cite journal|last1=Deshouillers|first1=Jean-Marc|last2=Hennecart|first2= François |last3=Landreau|first3= Bernard |title=Waring's Problem for sixteen biquadrates - numerical results|journal=[[Journal de théorie des nombres de Bordeaux]]|volume=12|year=2000|pages=411–422|url= http://www.math.ethz.ch/EMIS/journals/JTNB/2000-2/Dhl.ps}}</ref> that every number between 13793 and 10<sup>245</sup> required at most sixteen, and Kawada, Wooley and Deshouillers extended Davenport's 1939 result to show that every number above 10<sup>220</sup> required no more than sixteen). Sixteen fourth powers are always needed to write a number of the form 31·16<sup>n</sup>.
| |
| | |
| 617597724 is the last number less than 1.3{{e|9}} which requires ten fifth powers, and 51033617 the last number less than 1.3{{e|9}} which requires eleven.
| |
| | |
| The upper bounds on the right with k=5,...,20 are due to [[R. C. Vaughan|Vaughan]] and [[Trevor Wooley|Wooley]].<ref name=Vaughan-Wooley>{{cite book |author=R. C. Vaughan, [[Trevor Wooley]] |url=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.145.8949&rep=rep1&type=pdf Waring's Problem: A Survey |title=Number Theory for the Millennium |volume=III |publisher=A. K. Peters |pages=301–340 |year=2002 |isbn=978-1-56881-152-9}}</ref>
| |
| | |
| Using his improved [[Hardy-Littlewood method]], [[Ivan Matveyevich Vinogradov|I. M. Vinogradov]] published numerous refinements leading to
| |
| :<math>G(k)\le k(3\log k +11)</math>
| |
| in 1947 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.
| |
| | |
| 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]] obtained<ref>{{cite journal|first=A. A.|last=Karatsuba|title=On the function G(n) in Waring's problem|pages=935–947| journal= Izv. Akad. Nauk SSSR, Ser. Math.|issue=49:5|year=1985}}</ref> (1985) a new estimate of the [[G. H. Hardy|Hardy]] function <math>G(n)</math> (for <math>n \ge 400</math>):
| |
| | |
| : <math>\! G(n) < 2 n\log n + 2 n\log\log n + 12 n.</math>
| |
| | |
| Further refinements were obtained by Vaughan [1989].
| |
| | |
| Wooley then established that for some constant ''C'',<ref name=Vaughan>{{cite book | zbl=0868.11046 | last=Vaughan | first=R.C. | title=The Hardy-Littlewood method | edition=2nd | series=Cambridge Tracts in Mathematics | volume=125 | location=Cambridge | publisher=[[Cambridge University Press]] | year=1997 | isbn=0-521-57347-5 }}</ref>
| |
| :<math>G(k)\le k\log k+k\log\log k+Ck.</math>
| |
| | |
| Vaughan and Wooley have written a comprehensive survey article.<ref name=Vaughan-Wooley/>
| |
| | |
| ==See also==
| |
| *[[Polygonal number theorem]]
| |
| *[[Waring–Goldbach problem]]
| |
| | |
| ==Notes==
| |
| {{clear}}
| |
| {{Reflist|colwidth=30em}}
| |
| | |
| ==References==
| |
| * G. I. Arkhipov, V. N. Chubarikov, [[Anatolii Alexeevitch Karatsuba|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).
| |
| *[[Ivan Matveyevich Vinogradov|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).
| |
| * W. J. Ellison: ''Waring's problem''. American Mathematical Monthly, volume 78 (1971), pp. 10–36. Survey, contains the precise formula for ''g''(''k''), a simplified version of Hilbert's proof and a wealth of references.
| |
| *{{Cite book | authorlink = Aleksandr Khinchin | last = Khinchin | first = A. Ya. | title = Three Pearls of Number Theory | publisher = Dover | location = Mineola, NY | date = 1998 | isbn = 978-0-486-40026-6 | postscript = <!--None-->}} Has an elementary proof of the existence of ''G''(''k'') using [[Schnirelmann density]].
| |
| * {{cite book | first=Melvyn B. | last=Nathanson | title=Additive Number Theory: The Classical Bases | volume=164 | series=[[Graduate Texts in Mathematics]] | publisher=[[Springer-Verlag]] | year=1996| isbn=0-387-94656-X | zbl=0859.11002 }} 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''<sup>th</sup> powers.
| |
| * [[Hans Rademacher]] and [[Otto Toeplitz]], ''The Enjoyment of Mathematics'' (1933) (ISBN 0-691-02351-4). Has a proof of the Lagrange theorem, accessible to high school students.
| |
| | |
| {{DEFAULTSORT:Waring's Problem}}
| |
| [[Category:Additive number theory]]
| |
| [[Category:Mathematical problems]]
| |