Đị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 ^[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ên

N=N(k,\delta )\,

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^{\log(1/\delta )^{k-1}}\leq N(k,\delta )\leq 2^{2^{\delta ^{-2^{2^{k+9}}}}}

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à

N(3,\delta )\leq C^{\delta ^{-2}\log(1/\delta )},

bởi Bourgain.^[10]

Xem thêm

Ghi chú

^ Erdős, Paul; Turán, Paul (1936), “On some sequences of integers” (PDF), Journal of the London Mathematical Society, 11 (4): 261–264, doi:10.1112/jlms/s1-11.4.261.
^ Roth, Klaus Friedrich (1953), “On certain sets of integers, I”, Journal of the London Mathematical Society, 28: 104–109, doi:10.1112/jlms/s1-28.1.104, Zbl 0050.04002, MR 0051853.
^ Szemerédi, Endre (1969), “On sets of integers containing no four elements in arithmetic progression”, Acta Math. Acad. Sci. Hung., 20: 89–104, doi:10.1007/BF01894569, Zbl 0175.04301, MR 0245555
^ Roth, Klaus Friedrich (1972), “Irregularities of sequences relative to arithmetic progressions, IV”, Periodica Math. Hungar., 2: 301–326, doi:10.1007/BF02018670, MR 0369311.
^ Szemerédi, Endre (1975), “On sets of integers containing no k elements in arithmetic progression” (PDF), Acta Arithmetica, 27: 199–245, Zbl 0303.10056, MR 0369312
^ Fürstenberg, Hillel (1977), “Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions”, J. D’Analyse Math., 31: 204–256, doi:10.1007/BF02813304, MR 0498471.
^ ^a ^b Gowers, Timothy (2001), “A new proof of Szemerédi's theorem”, Geom. Funct. Anal., 11 (3): 465–588, doi:10.1007/s00039-001-0332-9, MR 1844079.
^ Behrend, Felix A. (1946), “On the sets of integers which contain no three in arithmetic progression”, Proceedings of the National Academy of Sciences, 23 (12): 331–332, doi:10.1073/pnas.32.12.331, Zbl 0060.10302.
^ Rankin, Robert A. (1962), “Sets of integers containing not more than a given number of terms in arithmetical progression”, Proc. Roy. Soc. Edinburgh Sect. A, 65: 332–344, Zbl 0104.03705, MR 0142526.
^ Bourgain, Jean (1999), “On triples in arithmetic progression”, Geom. Func. Anal., 9 (5): 968–984, doi:10.1007/s000390050105, MR 1726234.