帽集问题(Cap set 问题)
已解决,2016年组合数学与离散数学
问题陈述
确定帽集(即不包含三项等差数列、满足不存在三个互异元素 使得 的子集 )的最大规模 是否以严格小于 的底数呈指数增长,即是否存在常数 使得 。
2016年5月,厄尼·克鲁特、弗谢沃洛德·列夫和彼得·帕尔·帕赫引入了一项突破性的多项式方法,用于界定 中的无等差数列集合。数日之内,乔丹·埃伦伯格和迪翁·海斯维特将该技术推广至 ,证明了 中任意帽集的规模至多为 ,其中 (即 )。陶哲轩随后利用张量的切片秩(slice rank)对这一证明给出了简洁的对称重述。虽然这解决了关于指数级节约的定性猜想,但在目前最优下界()与 之间确定精确的指数底数仍是一个公开问题。
在流行的纸牌游戏 Set 中,一副牌共有 张,一组“Set”恰为 中的一条直线;不含任何 Set 的最大牌数为 。切片秩多项式方法随即在埃尔德什–塞梅雷迪向日葵问题、矩阵乘法屏障以及代数超图染色数等领域引发了一系列突破。
参考文献
- Jordan S. Ellenberg, Dion Gijswijt (2017). On large subsets of with no three-term arithmetic progression · DOI:10.4007/annals.2017.185.1.8 · arXiv:1605.09223
- Ernie Croot, Vsevolod F. Lev, Péter Pál Pach (2017). Progression-free sets in are exponentially small · DOI:10.4007/annals.2017.185.1.7 · arXiv:1605.01506
- Fred Tyrrell (2023). New lower bounds for cap sets · arXiv:2209.10045