Math Labs

解法:多项式方法解决帽集问题(克罗特–列夫–帕赫,埃伦伯格–海斯维克,2016年)

第 1/7 步:帽集问题:无进展集合能有多大?
通俗地说

设想纸牌游戏SET,每张牌由 nn 个三元特征描述:帽集就是不含三张牌构成合法“集合”的牌的集合(被禁止的模式正是 F3n\mathbb{F}_3^n 中的三项等差数列 x+y+z=0x+y+z=0)。数十年来,已知的最大帽集上界与下界相差极大,使得帽集究竟能占据 F3n\mathbb{F}_3^n 的几乎全部,还是只能占据指数级微小的一部分,一直悬而未决。

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
详细分析

帽集是子集 A⊂F3nA\subset\mathbb{F}_3^n,不含满足 x+y+z=0x+y+z=0 的三个不同点 x,y,z∈Ax,y,z\in A;因为在特征 33 中 −x=x+x-x=x+x,这恰等价于没有三个不同元素构成仿射直线(即公差 d≠0d\ne0 的三项等差数列 x,x+d,x+2dx,x+d,x+2d)。记 r3(F3n)=max⁡∣A∣r_3(\mathbb{F}_3^n)=\max|A|。

平凡上界 ∣A∣≤3n|A|\le3^n 是数十年间唯一的指数级结论:Meshulam (1995) 用 F3n\mathbb{F}_3^n 上的 Fourier 分析证明 ∣A∣=O(3n/n)|A|=O(3^n/n),Bateman–Katz (2012) 改进到 O(3n/n1+ϵ)O(3^n/n^{1+\epsilon}) —— 与平凡界只差多项式因子。另一侧,已知最大构造(Edel,Tyrell 改进)仅约 2.2n2.2^n,连“增长率是否严格小于 33”这一定性问题都悬而未决。

Ellenberg–Gijswijt (2017) 借助 Croot–Lev–Pach (2016) 在 (Z/4Z)n(\mathbb{Z}/4\mathbb{Z})^n 上的多项式方法突破解决了此问题:∣A∣≤O(cn)|A|\le O(c^n),且 c=3e−I(2/3)≈2.756c=3e^{-I(2/3)}\approx2.756 为显式常数。证明的其余部分把帽集变成消失多项式问题,让维数计数完成工作。

本步骤中的术语
帽集
F3n\mathbb{F}_3^n 的子集 AA,其中不含满足 x+y+z=0x+y+z=0 的三个互异点 x,y,zx,y,z,即不含非平凡的三项等差数列。
三项等差数列
三个元素 x,y,zx,y,z,其中 yy 是 xx 与 zz 的平均值;在 F3\mathbb{F}_3 上这恰好就是方程 x+y+z=0x+y+z=0。
本步骤用到的知识