Cap set 问题：FunSearch 在 8 维找到更大的 cap set

问题

在 $\mathbb{F}_3^n$ 中，如果一个点集里不存在三个不同的点 $x, y, z$ 满足 $x + y + z = 0$，也就是不存在三点共线，就称它为 cap set。问题是：在 $n$ 维中，cap set 最大能有多大？

2016 年，Ellenberg 与 Gijswijt 证明了 cap set 的规模不超过约 $2.756^n$，但对于具体维度的精确最大值，以及渐近增长率的真实值，至今没有答案。

AI 做了什么

FunSearch 不直接输出答案，而是让大语言模型反复改写一段“生成 cap set 的程序”，再由自动评估器打分、筛选，留下更好的程序继续演化。在 $n = 8$ 时，它找到了大小为 512 的 cap set，此前已知最大为 496。

它同时找到了一类新的构造，把渐近下界中的增长常数从 2.2180 提高到 2.2202。

如何验证

构造本身是一个具体的点集，任何人都可以用几行程序在数秒内检查其中是否存在三点共线。这是 AI 数学结果中最容易核实的一类：不需要信任模型，只需要信任验算。

局限

这一结果改进的是下界，并未确定 8 维 cap set 的精确最大值；渐近意义上，2.2202 与 2.756 之间仍有很大差距。因此本条记录为“部分结果”。

∎