Định lý Szemerédi

Dạng hữu hạn này tương đương logic với phát biểu mật độ vô hạn nhờ một lập luận compact đơn giản, và đây chính là dạng thực sự được chứng minh: thay vì một tập vô hạn, ta chỉ cần kiểm soát hữu hạn cấu hình trong một cửa sổ hữu hạn nhưng đủ lớn.

Bước 1 (quy về cửa sổ hữu hạn). Giả sử phát biểu vô hạn sai với một $d(A_0) > 0$ nào đó mà hoàn toàn không chứa cấp số cộng độ dài $k$. Khi đó với mọi $N$, phần hạn chế $A_0 \cap [1,N]$ là tập con không chứa cấp số cộng độ dài $k$ của $\{1,\dots,N\}$ có kích thước tăng như $\delta$$N$ với $\delta$ > 0 cố định. Nếu phát biểu hữu hạn đúng thì không thể có họ như vậy với $N$ lớn tùy ý — mâu thuẫn, nên hai phát biểu tương đương với nhau.

Bước 2 (phân hoạch chính quy). Xem mỗi cấp số cộng độ dài $k$ tiềm năng trong $\{1,\dots,N\}$ như một cạnh của siêu đồ thị $(k-1)$-đều. Bổ đề chính quy hóa siêu đồ thị chia tập đỉnh thành số phần bị chặn sao cho, trừ một phần ngoại lệ nhỏ, mọi bộ phần đều giống ngẫu nhiên: mật độ cạnh giữa chúng gần như hằng số, không có cụm con đậm đặc hay thưa bất thường.

Bước 3 (bổ đề đếm). Khi phân hoạch đã chính quy, một bổ đề đếm tương ứng cho thấy mọi bộ phần có mật độ tương đối dương phải chứa đúng số lượng cấu hình đầy đủ như kỳ vọng — đặc biệt, ít nhất một cấp số cộng độ dài $k$ thực sự tồn tại, vì cấu trúc chính quy giống ngẫu nhiên có mật độ dương không thể tránh được mẫu hình mà nó đang được kiểm tra.

Bước 4 (lập luận loại bỏ). Nếu $A$ hoàn toàn không có cấp số cộng độ dài $k$, bổ đề đếm sẽ buộc hầu hết cấu hình được đếm bởi phân hoạch chính quy trở nên suy biến, từ đó có thể xóa một số phần tử nhỏ không đáng kể khỏi $A$ để triệt tiêu mọi cấp số cộng gần đúng — mâu thuẫn với việc $A$ giữ mật độ $\delta$ trên tập kích thước $N$ lớn tùy ý. Vậy cấp số cộng độ dài $k$ phải tồn tại. (Chứng minh bằng lý thuyết ergodic của Furstenberg năm 1977 và chứng minh bằng giải tích Fourier bậc cao của Gowers đi đến cùng kết luận theo những con đường hoàn toàn khác nhau, mỗi cách đều cho cận tường minh nhưng cực lớn cho $N(k,\delta)$.)

Đây là trường hợp không tầm thường đầu tiên của định lý Szemerédi, được Roth chứng minh năm 1953 bằng giải tích Fourier thay vì bộ máy chính quy hóa nặng nề cần cho $k$ tổng quát. Chiến lược "tăng mật độ" của ông — hoặc tìm ra mẫu hình, hoặc chỉ ra tập có cấu trúc bất thường rồi chuyển sang cấp số cộng con đậm đặc hơn — trở thành khuôn mẫu được tái sử dụng sau này, ở dạng phức tạp hơn nhiều, cho định lý tổng quát và cho Green–Tao.

Bước 1 (đếm cấp số cộng bằng Fourier). Giả sử $A \subseteq \{1,\dots,N\}$ có mật độ $\delta$ và không có cấp số cộng 3 số hạng không tầm thường nào. Viết $\hat{1_A}(\theta) = \sum_{n \in A} e(\theta n)$ là biến đổi Fourier của hàm chỉ thị của $A$, số bộ ba $(x, x+r, x+2r) \in A^3$ có thể viết thành tích phân của $\hat{1_A}(\theta)^2 \, \overline{\hat{1_A}(2\theta)}$ theo $\theta$.

Bước 2 (trường hợp giống ngẫu nhiên). Nếu mọi hệ số Fourier khác không của $1_A$ đều nhỏ so với $\delta^2$, tích phân sẽ bị chi phối chỉ bởi số hạng $\theta = 0$, điều này đã buộc có khoảng $\delta^3 N^2$ bộ ba — nhiều hơn hẳn các bộ ba tầm thường — mâu thuẫn với giả thiết $A$ không có bộ ba nào.

Bước 3 (tăng mật độ). Vậy phải có hệ số khác không nào đó lớn; nghĩa là $1_A$ tương quan với pha tuyến tính $e(\theta n)$, tức $A$ lệch đáng kể trên một cấp số cộng (hay tập Bohr) nào đó. Hạn chế vào cấp số cộng con đó cho một khoảng ngắn hơn mà mật độ của $A$ đã tăng lên theo một hệ số nhân cố định.

Bước 4 (lặp và kết luận). Mật độ không thể vượt quá 1, nên sau hữu hạn vòng lặp bước tăng mật độ, quá trình phải dừng lại — nghĩa là trường hợp giống ngẫu nhiên ở Bước 2 cuối cùng bị buộc xảy ra, cho ra cấp số cộng 3 số hạng còn thiếu, mâu thuẫn với giả thiết không có. Cách tính toán gốc của Roth cho ngưỡng dạng $N(3,\delta) \lesssim \exp(\exp(1/\delta))$; cận này được cải thiện qua nhiều thập kỷ, và lập luận năm 2023 của Kelley và Meka đưa cận xuống gần với xây dựng cổ điển của Behrend, mật độ dạng $N(3,\delta) \lesssim \exp\!\big(-c(\log N)^{1/12}\big) N$, gần như khép lại khoảng cách cho trường hợp này.