Bài toán Waring

Trong lý thuyết số, bài toán Waring hỏi rằng có phải mỗi số tự nhiên k đều có một số nguyên dương s sao cho mỗi số tự nhiên đều có thể viết thành tổng của tối đa s lũy thừa bậc k của số tự nhiên nhỏ hơn. Ví dụ chẳng hạn, mỗi số tự nhiên có thể viết thành tổng của tối đa 4 số chính phương, 9 số lập phương, hoặc 19 lũy thừa bậc 4. Bài toán được phát biểu bởi Edward Waring vào năm 1770, sau này được đặt theo tên ông. Lời giải của bài toán, nay được biết đến là định lý Hilbert–Waring, được đưa bởi Hilbert trong 1909.. Lâu trước khi Waring phát biểu bài toán, Diophantus đã đặt ra câu hỏi liệu mọi số nguyên dương có thể viết thành tổng của bốn số chính phương lớn hơn hoặc bằng không. Câu hỏi này sau được biến thành giả thuyết Bachet, sau bản biên dịch Diophantus của Claude Gaspard Bachet de Méziriac vào năm 1621,và nó được giải bởi Joseph-Louis Lagrange trong bài định lý bốn số chính phương của ông trong 1770. Cũng cùng năm 1770, Waring đặt ra bài toán trên. Với mỗi k {\displaystyle k} , gọi g ( k ) {\displaystyle g(k)} là số s {\displaystyle s} nhỏ nhất sao cho ta chỉ cần s số lũy thừa bậc k {\displaystyle k} của số tự nhiên để biểu diễn tất cả các số nguyên dương. Mọi số nguyên dương đều là lũy thừa bậc 1 của chính nó nên g ( 1 ) = 1 {\displaystyle g(1)=1} . Sau một vài tính toán ta sẽ có được: số 7 cần 4 số chính phương, số 23 cần 9 số lập phương và số 79 thì cần 19 lũy thừa bậc bốn; các ví dụ này cho thấy g ( 2 ) ≥ 4 {\displaystyle g(2)\geq 4} , g ( 3 ) ≥ 9 {\displaystyle g(3)\geq 9} , và g ( 4 ) ≥ 19 {\displaystyle g(4)\geq 19} . Waring giả thuyết các giá trị 4, 9, 19 trên quả thực là giá trị cần tìm. Định lý bốn số chính phương Lagrange trong 1770 phát biểu rằng mọi số tự nhiên là tổng của bốn số chính phương. Nói cách khác, định lý tương đương với g ( 2 ) = 4 {\displaystyle g(2)=4} . Sau đó, nhiều bài chứng minh rất phức tạp đã đặt thêm các giá trị cận cho bài toán. Để lấy ví dụ, Liouville chứng minh rằng giá trị g ( 4 ) {\displaystyle g(4)} không quá 53. Hardy và Littlewood chứng minh rằng mọi số đủ lớn là tổng của tối đa 19 lũy thừa bậc bốn. Chứng minh g ( 3 ) = 9 {\displaystyle g(3)=9} được đưa bởi Wieferich và A. J. Kempner trong khoảng thời gian từ 1909 đến 1912 , Chứng minh g ( 4 ) = 19 {\displaystyle g(4)=19} được đưa bởi R. Balasubramanian, F. Dress, và J.-M. Deshouillers trong 1986 , g ( 5 ) = 37 {\displaystyle g(5)=37} trong 1964 bởi Chen Jingrun, và g ( 6 ) = 73 {\displaystyle g(6)=73} trong 1940 bởi Pillai. Ký hiệu ⌊ x ⌋ {\displaystyle \lfloor x\rfloor } và { x } {\displaystyle \{x\}} tương ứng là phần nguyên và phần lẻ của số thực dương x {\displaystyle x} . Cho c = 2 k ⌊ ( 3 / 2 ) k ⌋ − 1 < 3 k {\displaystyle c=2^{k}\lfloor (3/2)^{k}\rfloor -1<3^{k}} và ta chỉ được phép dùng 2 k {\displaystyle 2^{k}} và 1 k {\displaystyle 1^{k}} để biểu diễn c {\displaystyle c} ; số phần tử tối thiểu để biểu diễn là ⌊ ( 3 / 2 ) k ⌋ − 1 {\displaystyle \lfloor (3/2)^{k}\rfloor -1} cho 2 k {\displaystyle 2^{k}} và 2 k − 1 {\displaystyle 2^{k}-1} cho 1 k {\displaystyle 1^{k}} . Có nghĩa là g ( k ) {\displaystyle g(k)} phải lớn ít nhất 2 k + ⌊ ( 3 / 2 ) k ⌋ − 2 {\displaystyle 2^{k}+\lfloor (3/2)^{k}\rfloor -2} . Tính chất được phát hiện bởi J. A. Euler, con trai của Leonhard Euler, vào khoảng 1772. Sau đó, Dickson, Pillai, Rubugunday, Niven và nhiều người khác đã chứng minh rằng g ( k ) = { 2 k + ⌊ ( 3 / 2 ) k ⌋ − 2 nếu 2 k { ( 3 / 2 ) k } + ⌊ ( 3 / 2 ) k ⌋ ≤ 2 k , 2 k + ⌊ ( 3 / 2 ) k ⌋ + ⌊ ( 4 / 3 ) k ⌋ − 2 nếu 2 k { ( 3 / 2 ) k } + ⌊ ( 3 / 2 ) k ⌋ > 2 k  và  ⌊ ( 4 / 3 ) k ⌋ ⌊ ( 3 / 2 ) k ⌋ + ⌊ ( 4 / 3 ) k ⌋ + ⌊ ( 3 / 2 ) k ⌋ = 2 k , 2 k + ⌊ ( 3 / 2 ) k ⌋ + ⌊ ( 4 / 3 ) k ⌋ − 3 nếu 2 k { ( 3 / 2 ) k } + ⌊ ( 3 / 2 ) k ⌋ > 2 k  và  ⌊ ( 4 / 3 ) k ⌋ ⌊ ( 3 / 2 ) k ⌋ + ⌊ ( 4 / 3 ) k ⌋ + ⌊ ( 3 / 2 ) k ⌋ > 2 k . {\displaystyle g(k)={\begin{cases}2^{k}+\lfloor (3/2)^{k}\rfloor -2&{\text{nếu}}\quad 2^{k}\{(3/2)^{k}\}+\lfloor (3/2)^{k}\rfloor \leq 2^{k},\\2^{k}+\lfloor (3/2)^{k}\rfloor +\lfloor (4/3)^{k}\rfloor -2&{\text{nếu}}\quad 2^{k}\{(3/2)^{k}\}+\lfloor (3/2)^{k}\rfloor >2^{k}{\text{ và }}\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{nếu}}\quad 2^{k}\{(3/2)^{k}\}+\lfloor (3/2)^{k}\rfloor >2^{k}{\text{ và }}\lfloor (4/3)^{k}\rfloor \lfloor (3/2)^{k}\rfloor +\lfloor (4/3)^{k}\rfloor +\lfloor (3/2)^{k}\rfloor >2^{k}.\end{cases}}} Không có giá trị k {\displaystyle k} được biết sao cho 2 k { ( 3 / 2 ) k } + ⌊ ( 3 / 2 ) k ⌋ > 2 k {\displaystyle 2^{k}\{(3/2)^{k}\}+\lfloor (3/2)^{k}\rfloor >2^{k}} . Mahler chứng minh chỉ có hữu hạn số k {\displaystyle k} như vậy, và Kubina và Wunderlich chứng minh rằng nếu tồn tại thì giá trị k {\displaystyle k} phải thỏa mãn k > 471 600 000 {\displaystyle k>471\,600\,000} . Do đó nay người ta giả thuyết rằng số k đó không bao giờ tồn tại, nghĩa là g ( k ) = 2 k + ⌊ ( 3 / 2 ) k ⌋ − 2 {\displaystyle g(k)=2^{k}+\lfloor (3/2)^{k}\rfloor -2} với mọi số nguyên dương k {\displaystyle k} . Các giá trị đầu của g ( k ) {\displaystyle g(k)} là: 1, 4, 9, 19, 37, 73, 143, 279, 548, 1079, 2132, 4223, 8384, 16673, 33203, 66190, 132055, 263619, 526502, 1051899, ... (dãy số A002804 trong bảng OEIS). Từ bài viết của Hardy và Littlewood,[cần dẫn nguồn] một giá trị khác G(k) được nghiên cứu cùng với g(k). G(k) được định nghĩa là số nguyên dương s nhỏ nhất sao cho mọi số nguyên đủ lớn có thể viết thành tổng của tối đa s lũy thừa bậc k của số nguyên dương. Nghiễm nhiên G(1) = 1. Bởi số chính phương đồng dư với 0, 1, hoặc 4 (mod 8), không số nguyên nào đồng dư với 7 (mod 8) có thể viết thành tổng của 3 số chính phương, chỉ ra rằng G(2) ≥ 4. Bởi G(k) ≤ g(k) với mọi k, ta có được G(2) = 4. Davenport chứng minh rằng[cần dẫn nguồn] G(4) = 16 trong 1939 bằng cách chứng minh mọi số nguyên đồng dư với 1 đến 14 mod 16 có thể thành tổng của 14 lũy thừa bậc bốn (Vaughan trong 1985[cần dẫn nguồn] và trong 1989[cần dẫn nguồn] giảm số 14 xuống còn 13 và 12 tương ứng). Giá trị chính xác của G(k) vẫn chưa được tính cho các giá trị k khác, nhưng tồn tại các cận. Giá trị G(k) lớn hơn hoặc bằng với Nếu không có ràng buộc đồng dư thì theo hàm mật độ, giá trị G(k) nên bằng với k + 1. G(3) ít nhất bằng 4 (bởi số lập dương đồng dư với 0, 1 hoặc −1 mod 9); với các số nhỏ hơn 1.3×109, 1290740 là số cuối cùng cần 6 số lập phương để biểu diễn, và số các số giữa N và 2N cần 5 số lập phương giảm đi khi N lớn với tốc độ đủ nhanh khiến người ta tin rằng G(3) = 4; giá trị lớn nhất hiện nay được biết không phải tổng của 4 số lập phương là 7373170279850,, các tác giả cho rằng đây có thể là giá trị lớn nhất và sau đó mọi số đều có thể biểu diễn thành tổng của 4 số lập phương. Cận trên G(3) ≤ 7 được đưa bởi Linnik trong 1943. (Mọi số nguyên không âm cần tối đa 9 số lập phương, và số nguyên lớn nhất cần 9, 8, 7, 6 và 5 số lập phương được giả thuyết là 239, 454, 8042, 1290740 và 7373170279850, tương ứng.) 13792 là số lớn nhất cần 17 lũy thừa bậc bốn (được Deshouillers, Hennecart và Landreau chứng minh trong 2000 rằng tất cả các số nằm giữa 13793 và 10245 cần tối đa 16 số, sau đó Kawada, Wooley và Deshouillers mở rộng kết quả năm 1939 của[cần dẫn nguồn] Davenport để chứng minh rằng mọi số nằm trên 10220 không cần nhiều hơn 16 số). Các số dưới dạng 31·16n luôn cần 16 lũy thừa bậc 4. 617597724 là số cuối cùng nhỏ hơn 1.3×109 mà cần 10 lũy thừa bậc 5, và 51033617 là số cuối cùng nhỏ hơn 1.3×109 mà cần 11 lũy thừa bậc 5. Cận trên ở bên phải với k = 5, 6, ..., 20 được đưa bởi Vaughan và Wooley. Sử dụng phương pháp Hardy-Littlewood đã được cải tiến, I. M. Vinogradov xuất bản một số thay đổi dẫn tới kết quả G ( k ) ≤ k ( 3 log ⁡ k + 11 ) {\displaystyle G(k)\leq k(3\log k+11)} trong 1947[cần dẫn nguồn] và sau đó cải tiến thêm thành, G ( k ) ≤ k ( 2 log ⁡ k + 2 log ⁡ log ⁡ k + C log ⁡ log ⁡ log ⁡ k ) {\displaystyle G(k)\leq k(2\log k+2\log \log k+C\log \log \log k)} với một số hằng số C và số k đủ lớn trong 1959[cần dẫn nguồn]. Áp dụng dạng p-adic của phương pháp Hardy–Littlewood–Ramanujan–Vinogradov để ước tính tổng lượng giác, trong đó các số hạng là các số có ước nguyên tố nhỏ, trong 1985 Anatolii Alexeevitch Karatsuba thu về được ước lượng mới cho hàm Hardy G ( k ) {\displaystyle G(k)} (cho k ≥ 400 {\displaystyle k\geq 400} ): G ( k ) < 2 k log ⁡ k + 2 k log ⁡ log ⁡ k + 12 k . {\displaystyle G(k)<2k\log k+2k\log \log k+12k.} Một số cải tiến được thêm vào bởi Vaughan trong 1989[cần dẫn nguồn]. Wooley sau đó đặt ra rằng với một số hằng số C, G ( k ) ≤ k log ⁡ k + k log ⁡ log ⁡ k + C k . {\displaystyle G(k)\leq k\log k+k\log \log k+Ck.} Bài toán Waring-Goldbach yêu cầu biểu diễn một số là tổng của các lũy thừa của số nguyên tố. Tổng của ba số lập phương thảo luận về việc biểu diễn một số nguyên thành tổng của ba số lập phương khác (không nhất thiết phải dương). Bài toán tổng của bốn số lập phương hỏi xem liệu mọi số hữu tỉ có thể viết thành tổng của bốn số lập phương hữu tỉ. ^ Hilbert, David (1909). “Beweis für die Darstellbarkeit der ganzen Zahlen durch eine feste Anzahl n-ter Potenzen (Waringsches Problem)”. Mathematische Annalen (bằng tiếng Đức). 67 (3): 281–300. doi:10.1007/bf01450405. MR 1511530. ^ Nên nhớ là ta đang giới hạn bài toán với số tự nhiên. Với số nguyên nói chung, ta có thể viết 23 thành tổng của 4 số lập phương ( 2 3 + 2 3 + 2 3 + ( − 1 ) 3 ) {\displaystyle 2^{3}+2^{3}+2^{3}+(-1)^{3})} hoặc 29 3 + 17 3 + 8 3 + ( − 31 ) 3 {\displaystyle 29^{3}+17^{3}+8^{3}+(-31)^{3}} . ^ Wieferich, Arthur (1909). “Beweis des Satzes, daß sich eine jede ganze Zahl als Summe von höchstens neun positiven Kuben darstellen läßt”. Mathematische Annalen (bằng tiếng Đức). 66 (1): 95–101. doi:10.1007/BF01450913. ^ Kempner, Aubrey (1912). “Bemerkungen zum Waringschen Problem”. Mathematische Annalen (bằng tiếng Đức). 72 (3): 387–399. doi:10.1007/BF01456723.[liên kết hỏng] ^ Balasubramanian, Ramachandran; Deshouillers, Jean-Marc; Dress, François (1986). “Problème de Waring pour les bicarrés. I. Schéma de la solution” [Waring's problem for biquadrates. I. Sketch of the solution]. Comptes Rendus de l'Académie des Sciences, Série I (bằng tiếng Pháp). 303 (4): 85–88. MR 0853592. ^ Balasubramanian, Ramachandran; Deshouillers, Jean-Marc; Dress, François (1986). “Problème de Waring pour les bicarrés. II. Résultats auxiliaires pour le théorème asymptotique” [Waring's problem for biquadrates. II. Auxiliary results for the asymptotic theorem]. Comptes Rendus de l'Académie des Sciences, Série I (bằng tiếng Pháp). 303 (5): 161–163. MR 0854724. ^ Pillai, S. S. (1940). “On Waring's problem g(6) = 73”. Proc. Indian Acad. Sci. 12: 30–40. doi:10.1007/BF03170721. MR 0002993. ^ L. Euler, "Opera posthuma" (1), 203–204 (1862). ^ Niven, Ivan M. (1944). “An unsolved case of the Waring problem”. American Journal of Mathematics. The Johns Hopkins University Press. 66 (1): 137–143. doi:10.2307/2371901. JSTOR 2371901. MR 0009386. ^ Mahler, Kurt (1957). “On the fractional parts of the powers of a rational number II”. Mathematika. 4 (2): 122–124. doi:10.1112/s0025579300001170. MR 0093509. ^ Kubina, Jeffrey M.; Wunderlich, Marvin C. (1990). “Extending Waring's conjecture to 471,600,000”. Math. Comp. 55 (192): 815–820. Bibcode:1990MaCom..55..815K. doi:10.2307/2008448. JSTOR 2008448. MR 1035936. ^ Nathanson (1996, tr. 71)Lỗi harv: không có mục tiêu: CITEREFNathanson1996 (trợ giúp). ^ Deshouillers, Jean-Marc; Hennecart, François; Landreau, Bernard; I. Gusti Putu Purnaba, Appendix by (2000). “7373170279850”. Mathematics of Computation. 69 (229): 421–439. doi:10.1090/S0025-5718-99-01116-3. ^ U. V. Linnik. "On the representation of large numbers as sums of seven cubes". Mat. Sb. N.S. 12(54), 218–224 (1943). ^ Deshouillers, Jean-Marc; Hennecart, François; Landreau, Bernard (2000). “Waring's Problem for sixteen biquadrates – numerical results”. Journal de théorie des nombres de Bordeaux. 12 (2): 411–422. doi:10.5802/jtnb.287. ^ Vaughan, R. C.; Wooley, Trevor (2002). “Waring's Problem: A Survey”. Trong Bennet, Michael A.; Berndt, Bruce C.; Boston, Nigel; Diamond, Harold G.; Hildebrand, Adolf J.; Philipp, Walter (biên tập). Number Theory for the Millennium. III. Natick, MA: A. K. Peters. tr. 301–340. ISBN 978-1-56881-152-9. MR 1956283. ^ Karatsuba, A. A. (1985). “On the function G(n) in Waring's problem”. Izv. Akad. Nauk SSSR, Ser. Math. 27 (49:5): 935–947. Bibcode:1986IzMat..27..239K. doi:10.1070/IM1986v027n02ABEH001176. ^ Vaughan, R. C. (1997). The Hardy–Littlewood method. Cambridge Tracts in Mathematics. 125 (ấn bản 2). Cambridge: Cambridge University Press. ISBN 0-521-57347-5. Zbl 0868.11046. Hazewinkel, Michiel biên tập (2001), “Waring problem”, Bách khoa toàn thư Toán học, Springer, ISBN 978-1-55608-010-4