Định lý Szemerédi

Trong lý thuyết số, định lý Szemerédi là một kết quả trước đó mang tên  giả thuyết Erdős–Turán (không nên nhầm lẫn với giả thuyết Erdős–Turán về cơ sở cộng). Năm 1936 Erdős và Turán đưa ra giả thuyết . rằng với mọi giá trị d gọi là mật độ thỏa mãn 0 < d < 1 và số nguyên k, tồn tại số nguyên N(d, k) sao cho mọi tập hợp con A của {1, ..., N} với lực lượng  dN đều có một cấp số cộng độ dài k, nếu N > N(d, k).

Đây là một tổng quát hóa của định lý van der Waerden.

Trường hợp k = 1 và k = 2 là tầm thường. Trường hợp k = 3 được chứng minh năm 1956 bởi Klaus Roth. bằng phương pháp đường tròn Hardy–Littlewood. Trường hợp k = 4 được chứng minh năm 1969 bởi Endre Szemerédi bằng phương pháp tổ hợp. Bằng phương pháp tương tự như cho trường hợp k = 3, Roth. đưa ra một chứng minh khác cho kết quả này năm 1972.

Cuối cùng trường hợp tổng quát cho mọi k được chứng minh năm 1975, cũng bởi Szemerédi, bằng một mở rộng phức tạp của chứng minh tổ hợp trước đó ("một kiệt tác của lập luận tổ hợp", R. L. Graham). Ngày nay nhiều chứng minh khác của kết quả này đã được tìm ra, một vài chứng minh quan trọng trong số đó là của Hillel Fürstenberg. năm 1977, bằng lý thuyết ergodic, và bởi Timothy Gowers. năm 2001, bằng giải tích Fourier và toán học tổ hợp.

Đặt k là một số nguyên dương và đặt 0 < δ ≤ 1/2. Một phiên bản hữu hạn của định lý khẳng định rằng tồn tại số nguyên

sao cho mọi tập hợp con của  {1, 2,..., N} với kích thước δN đều chứa một cấp số cộng độ dài k.
Chặn chặt nhất đến nay cho N(k, δ) là

với C > 1. Chặn dưới là của Behrend. (cho k = 3) và Rankin,. và chặn trên là của Gowers. 
Trong trường hợp đặc biệt k = 3; chặn trên chặt nhất đến nay là

bởi Bourgain..

Xem thêm
Các bài toán về cấp số cộng
Lý thuyết Ramsey ergodic
Tổ hợp số học
Bổ đề đều Szemerédi
Định lý Green–Tao
Giả thuyết Erdős về cấp số cộng

Ghi chú

Liên kết ngoài
PlanetMath 
math.NT/0404188 Bài báo chứng minh định lý Green-Tao 
Thảo luận về định lý Szemerédi (phần 1 trong 5 phần)
Ben Green và Terence Tao: Szemerédi's theorem trên Scholarpedia

Thể loại:Lý thuyết Ramsey
Thể loại:Toán học tổ hợp
Thể loại:Định lý trong toán rời rạc
Thể loại:Định lý trong lý thuyết số