✨Đị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

:$N\; =\; N(k,\backslash delta)\backslash ,$

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à

:$C^\{\backslash log(1/\backslash delta)^\{k-1\; \backslash leq\; N(k,\backslash delta)\; \backslash leq\; 2^\{2^\{\backslash delta^\{-2^\{2^\{k+9\}$

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.