向日葵猜想被攻克 — The Knowledge Frontier

取从1到n的数，考虑从中挑选一部分的所有方式：这样的子集共有2ⁿ个。现在挑出几个子集，它们共享完全相同的公共部分，除此之外再无交集。数学家把这称为向日葵：共享部分是花心，每个集合剩下的部分是一片花瓣，与其他任何花瓣都不接触。

向日葵是组合数学的基本工具。论文列举了它与某些逻辑电路的极限、“帽集”（cap set）问题、快速矩阵乘法以及信息论之间的联系。

一个来自1970年的问题

作者指出，关于它们最自然的问题可以追溯到保罗·埃尔德什1970年的一篇论文：如果一个由{1, …, n}的子集构成的集族中没有任何k个集合构成向日葵，这个集族最大能有多大？

20世纪70年代，埃尔德什和塞迈雷迪·安德烈猜想，这样的集族必然比2ⁿ个可能的子集小指数级：至多为cⁿ，其中c是某个严格小于2的数。

几十年来，最好的上界只削减了一点点，始终不足以把底数降到2以下。只有三瓣的情形（k = 3）在2016年得到解决，这得益于帽集问题上的突破以及Alon、Shpilka和Umans给出的一个归约。

维也纳大学的Matija Bucić和Fankang He，以及韩国科学技术院（KAIST）和韩国基础科学研究院的Hyunwoo Lee，证明了这一猜想对每个k ≥ 3都成立。他们的主要定理是：一个不含k瓣向日葵的集族至多有

3 · (2 − 1/(16k³))ⁿ

个成员。底数仅略低于2，但它是一个低于2的固定数，而这正是埃尔德什和塞迈雷迪所要求的。1997年的一个构造表明，对于较大的k，真实值不可能低很多。

证明经过了该问题的一个向量版本。把这些数分成n个块，每块D个元素，每块选一个元素：每种选择就是一个向量。若干向量在每个位置上的分量要么全部相同，要么全部不同时，它们就构成一朵向日葵。

随后，作者构造了一个“向日葵检测器”：一个函数，在不含向日葵的集族上，只有当所有输入都是同一个向量时才不为零。新的要素是用低次插值多项式一步步写出这个函数。对这些多项式计数，就能给出集族大小的上界（他们的定理2）。再通过一个概率论证，即对所有集合大小取随机块的平均，把这个上界转回到普通集合上。

论文关于人工智能的声明异常直接。定理2的证明是由ChatGPT 6 Astra Pro找到的，起因是一段简短的对话，一开始是请它推广已知的三瓣论证。作者需要这一步来实现另一个目标：塞迈雷迪提出的一个图论问题的诱导版本，他们宣布将在后续的短文中发表。

模型用“切片秩”（slice rank）的语言写出了证明。作者用多项式方法的语言改写了它，他们认为这对读者来说更容易理解。他们声明已验证了每一个结果并承担全部责任，并且该证明已在Lean 4.35中得到验证，这是一种证明检验软件，验证结果将发布在Palomar代码库中。

作者没有尝试优化底数。对于三瓣情形，它没有超过Naslund和Sawin在2017年给出的约1.89的上界。而更强的姊妹问题，即埃尔德什–拉多向日葵猜想，仍然悬而未决：他们的上界仍严重依赖块大小D，而这恰恰是那个问题所不允许的。