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..
Quan hệ với định lý 4 số chính phương của Lagrange.
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.
Giá trị "g"("k").
Với mỗi formula_1, gọi formula_2 là số formula_3 nhỏ nhất sao cho ta chỉ cần "s" số lũy thừa bậc formula_1 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 formula_5. 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 formula_6, formula_7, và formula_8. 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 formula_9.
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ị formula_10 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 formula_11 được đưa bởi Wieferich và A. J. Kempner trong khoảng thời gian từ 1909 đến 1912 , Chứng minh formula_12 được đưa bởi R. Balasubramanian, F. Dress, và J.-M. Deshouillers trong 1986 , formula_13 trong 1964 bởi Chen Jingrun, và formula_14 trong 1940 bởi Pillai.
Ký hiệu formula_15 và formula_16 tương ứng là phần nguyên và phần lẻ của số thực dương formula_17. Cho formula_18 và ta chỉ được phép dùng formula_19 và formula_20 để biểu diễn formula_21; số phần tử tối thiểu để biểu diễn là formula_22 cho formula_19 và formula_24 cho formula_20. Có nghĩa là formula_2 phải lớn ít nhất formula_27. 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
Không có giá trị formula_1 được biết sao cho formula_30. Mahler chứng minh chỉ có hữu hạn số formula_1 như vậy, và Kubina và Wunderlich chứng minh rằng nếu tồn tại thì giá trị formula_1 phải thỏa mãn formula_33. Do đó nay người ta giả thuyết rằng số "k" đó không bao giờ tồn tại, nghĩa là formula_34 với mọi số nguyên dương formula_1.
Các giá trị đầu của formula_2 là:
Giá trị "G"("k").
Từ bài viết của Hardy và Littlewood, 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 . Bởi với mọi "k", ta có được . Davenport chứng minh rằng 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 và trong 1989 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.
Cận dưới cho "G"("k").
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 .
Cận trên cho "G"("k").
"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, 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à 2"N" 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 ; 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à , 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 đượ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, và , tương ứng.)
 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 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 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·16"n" luôn cần 16 lũy thừa bậc 4.
 là số cuối cùng nhỏ hơn 1.3 mà cần 10 lũy thừa bậc 5, và là số cuối cùng nhỏ hơn 1.3 mà cần 11 lũy thừa bậc 5.
Cận trên ở bên phải với đượ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ả 
trong 1947 và sau đó cải tiến thêm thành,
với một số hằng số "C" và số "k" đủ lớn trong 1959.
Á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 formula_39 (cho formula_40):
Một số cải tiến được thêm vào bởi Vaughan trong 1989.
Wooley sau đó đặt ra rằng với một số hằng số "C",