解法:多项式方法解决帽集问题(克罗特–列夫–帕赫,埃伦伯格–海斯维克,2016年)
通俗地说
设想纸牌游戏SET,每张牌由 个三元特征描述:帽集就是不含三张牌构成合法“集合”的牌的集合(被禁止的模式正是 中的三项等差数列 )。数十年来,已知的最大帽集上界与下界相差极大,使得帽集究竟能占据 的几乎全部,还是只能占据指数级微小的一部分,一直悬而未决。
详细分析
帽集是子集 ,不含满足 的三个不同点 ;因为在特征 中 ,这恰等价于没有三个不同元素构成仿射直线(即公差 的三项等差数列 )。记 。
平凡上界 是数十年间唯一的指数级结论:Meshulam (1995) 用 上的 Fourier 分析证明 ,Bateman–Katz (2012) 改进到 —— 与平凡界只差多项式因子。另一侧,已知最大构造(Edel,Tyrell 改进)仅约 ,连“增长率是否严格小于 ”这一定性问题都悬而未决。
Ellenberg–Gijswijt (2017) 借助 Croot–Lev–Pach (2016) 在 上的多项式方法突破解决了此问题:,且 为显式常数。证明的其余部分把帽集变成消失多项式问题,让维数计数完成工作。
- 帽集
- 的子集 ,其中不含满足 的三个互异点 ,即不含非平凡的三项等差数列。
- 三项等差数列
- 三个元素 ,其中 是 与 的平均值;在 上这恰好就是方程 。