Định lýĐã chứng minh

Định lý Szemerédi

Phát biểu

Mọi tập con $A \subseteq \mathbb{N}$ có mật độ trên dương ( $\limsup_{N\to\infty} |A \cap [1,N]|/N > 0$ ) đều chứa các cấp số cộng dài tùy ý: với mọi $k \ge 1$ và $\delta > 0$ , tồn tại $N(k,\delta)$ sao cho mọi tập con của $\{1,\dots,N\}$ có lực lượng ít nhất $\delta N$ với $N \ge N(k,\delta)$ đều chứa một cấp số cộng $k$ số hạng.

Vì sao đúng?

Nếu một tập con của tập số nguyên chiếm một tỷ lệ dương cố định trong toàn bộ các số, nó không thể tránh né mãi các mẫu cách đều nhau — dù bạn cố rải các số được chọn như thế nào, một cấp số cộng với độ dài mong muốn bất kỳ cuối cùng cũng phải xuất hiện. Chỉ riêng mật độ đã buộc phải có cấu trúc số học.

Phác thảo chứng minh

Một tập $A \subseteq [1,N]$ có mật độ $\delta$ hoặc hành xử giả ngẫu nhiên — khi đó nó chứa xấp xỉ số lượng kỳ vọng $\delta^k N^2$ cấp số cộng $k$ số hạng — hoặc không giả ngẫu nhiên, điều này tạo tương quan giữa $A$ với một cấu hình có cấu trúc và cho phép chuyển sang một cấp số cộng con mà trên đó $A$ có mật độ lớn hơn hẳn $\delta + c(\delta)$ . Vì mật độ không thể vượt quá 1, vòng lặp tăng mật độ này buộc phải dừng, và bổ đề chính quy Szemerédi (hoặc trong các chứng minh về sau là giải tích Fourier bậc cao, lý thuyết ergodic hay tính chính quy siêu đồ thị) cung cấp phép phân rã thành phần có cấu trúc và phần giả ngẫu nhiên.

Người chứng minh

chứng minh năm 1975Endre Szemerédi

Chủ đề chứa định lý này

Định lý Szemerédi

Định lý liên quan

Định lý Ramsey Định lý Green–Tao

Chứng minh từng bước

Chưa có chứng minh từng bước cho định lý này.

Tài liệu tham khảo

Endre Szemerédi (1975). On sets of integers containing no k elements in arithmetic progression