MathLabs

帽集问题(Cap set 问题)

已解决,2016年组合数学与离散数学
问题陈述

确定帽集(即不包含三项等差数列、满足不存在三个互异元素 x,y,z∈Ax, y, z \in A 使得 x+y+z=0x + y + z = 0 的子集 A⊆F3nA \subseteq \mathbb{F}_3^n)的最大规模 r3(F3n)r_3(\mathbb{F}_3^n) 是否以严格小于 33 的底数呈指数增长,即是否存在常数 c<3c < 3 使得 r3(F3n)≤cnr_3(\mathbb{F}_3^n) \le c^n。

2016年5月,厄尼·克鲁特、弗谢沃洛德·列夫和彼得·帕尔·帕赫引入了一项突破性的多项式方法,用于界定 (Z/4Z)n(\mathbb{Z}/4\mathbb{Z})^n 中的无等差数列集合。数日之内,乔丹·埃伦伯格和迪翁·海斯维特将该技术推广至 Fqn\mathbb{F}_q^n,证明了 F3n\mathbb{F}_3^n 中任意帽集的规模至多为 O(cn)O(c^n),其中 c=3(8−1/3)(1+8−1/3+8−2/3)/2≈2.7552<3c = 3(8^{-1/3})(1+8^{-1/3}+8^{-2/3}) / 2 \approx 2.7552 < 3(即 381/3⋅⋯≈2.756\frac{3}{8^{1/3}} \cdot \dots \approx 2.756)。陶哲轩随后利用张量的切片秩(slice rank)对这一证明给出了简洁的对称重述。虽然这解决了关于指数级节约的定性猜想,但在目前最优下界(≈2.220n\approx 2.220^n)与 2.7552n2.7552^n 之间确定精确的指数底数仍是一个公开问题。

  1. 多项式方法解决帽集问题(克罗特–列夫–帕赫,埃伦伯格–海斯维克,2016年)Ernie Croot, Vsevolod Lev, Péter Pál Pach; Jordan Ellenberg and Dion Gijswijt; slice-rank reformulation by Terence Tao, 2016难度 4/5进阶

参考文献

  1. Jordan S. Ellenberg, Dion Gijswijt (2017). On large subsets of Fqn\mathbb{F}_q^n with no three-term arithmetic progression · DOI:10.4007/annals.2017.185.1.8 · arXiv:1605.09223
  2. Ernie Croot, Vsevolod F. Lev, Péter Pál Pach (2017). Progression-free sets in Z4n\mathbb{Z}_4^n are exponentially small · DOI:10.4007/annals.2017.185.1.7 · arXiv:1605.01506
  3. Fred Tyrrell (2023). New lower bounds for cap sets · arXiv:2209.10045