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
[1] 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[2] 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[3] 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
[4] đư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,
[5] 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[6] năm 1977, bằng
lý thuyết ergodic, và bởi
Timothy Gowers[7] 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ênsao 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[8] (cho k = 3) và
Rankin,
[9] và chặn trên là của Gowers.
[7] Trong trường hợp đặc biệt k = 3; chặn trên chặt nhất đến nay làbởi
Bourgain.
[10]