Math Labs

Lời giải: Phương pháp đa thức giải quyết bài toán tập mũ (Croot-Lev-Pach, Ellenberg-Gijswijt, 2016)

Bước 1 trên 7: Bài toán tập mũ: một tập không chứa cấp số cộng có thể lớn tới đâu?
Hiểu nôm na

Hãy hình dung trò chơi SET, chơi trên các lá bài mô tả bởi nn đặc trưng tam phân: một tập mũ là một tập hợp các lá bài không có ba lá nào tạo thành một "bộ" hợp lệ (mẫu bị cấm chính là cấp số cộng ba số hạng x+y+z=0x+y+z=0 trong F3n\mathbb{F}_3^n). Trong nhiều thập kỷ, chặn trên và chặn dưới tốt nhất được biết cho tập mũ lớn nhất khác xa nhau, để ngỏ câu hỏi liệu tập mũ có thể chiếm gần như toàn bộ F3n\mathbb{F}_3^n hay chỉ một phần cực nhỏ theo hàm mũ.

A⊆F3n, ∄ x,y,z∈A distinct with x+y+z=0  ⟹  ∣A∣≤O(cn), c<3A \subseteq \mathbb{F}_3^n,\ \nexists\, x,y,z \in A \text{ distinct with } x+y+z=0 \implies |A| \le O(c^n),\ c < 3
Phân tích chi tiết

Tập cap là tập con A⊂F3nA\subset\mathbb{F}_3^n không chứa ba điểm khác nhau x,y,z∈Ax,y,z\in A thỏa x+y+z=0x+y+z=0; vì −x=x+x-x=x+x chỉ đúng trong đặc số 33, điều này tương đương với việc không có ba phần tử khác nhau tạo thành một đường thẳng affine (hay cấp số cộng ba số hạng x,x+d,x+2dx,x+d,x+2d với d≠0d\ne0). Ký hiệu r3(F3n)=max⁡∣A∣r_3(\mathbb{F}_3^n)=\max|A|.

Cận tầm thường ∣A∣≤3n|A|\le3^n là khẳng định mũ duy nhất trong nhiều thập kỷ: Meshulam (1995) chứng minh ∣A∣=O(3n/n)|A|=O(3^n/n) bằng phân tích Fourier trên F3n\mathbb{F}_3^n, và Bateman–Katz (2012) đẩy lên O(3n/n1+ϵ)O(3^n/n^{1+\epsilon}) — vẫn chỉ kém cận tầm thường một thừa số đa thức. Về phía dưới, các cấu hình lớn nhất đã biết (Edel, cải tiến bởi Tyrell) chỉ đạt khoảng 2.2n2.2^n, nên ngay cả câu hỏi định tính 'tốc độ tăng có thực sự nhỏ hơn 33 không?' cũng còn mở.

Ellenberg–Gijswijt (2017), dựa trên đột phá phương pháp đa thức mới của Croot–Lev–Pach (2016) cho (Z/4Z)n(\mathbb{Z}/4\mathbb{Z})^n, trả lời câu hỏi đó: ∣A∣≤O(cn)|A|\le O(c^n) với c=3e−I(2/3)≈2.756c=3e^{-I(2/3)}\approx2.756 tường minh. Phần còn lại của chứng minh biến một tập cap thành bài toán về đa thức triệt tiêu và để phép đếm chiều làm việc.

Thuật ngữ trong bước này
Tập mũ
Một tập con AA của F3n\mathbb{F}_3^n không chứa ba điểm phân biệt x,y,zx,y,z với x+y+z=0x+y+z=0, tức không chứa cấp số cộng ba số hạng không tầm thường.
Cấp số cộng ba số hạng
Ba phần tử x,y,zx,y,z với yy là trung bình cộng của xx và zz; trên F3\mathbb{F}_3 điều này chính là phương trình x+y+z=0x+y+z=0.
Kiến thức dùng ở bước này