キャップ集合問題：FunSearch が 8 次元でより大きなキャップ集合を発見

問題

$\mathbb{F}_3^n$ の点の集合が、$x + y + z = 0$ を満たす相異なる 3 点 $x, y, z$、すなわち一直線上に並ぶ 3 点を含まないとき、それを キャップ集合 と呼ぶ。問題は、$n$ 次元でキャップ集合がどこまで大きくなれるかである。

2016 年、Ellenberg と Gijswijt はキャップ集合の大きさがおよそ $2.756^n$ 以下であることを証明した。しかし、特定の次元における正確な最大値も、漸近的な増大率の真の値も、いまだ分かっていない。

AI が行ったこと

FunSearch は答えを直接出力するわけではない。大規模言語モデルが「キャップ集合を生成するプログラム」を繰り返し書き換え、自動評価器が採点と選別を行い、よりよいプログラムが進化を続ける。$n = 8$ において、それまでの既知最大 496 を上回る、大きさ 512 のキャップ集合を見つけた。

さらに新しい構成の族を見つけ、漸近的な下界の増大定数を 2.2180 から 2.2202 に引き上げた。

検証の方法

構成そのものは具体的な点の集合であり、誰でも数行のプログラムで、一直線上に並ぶ 3 点がないことを数秒で確かめられる。これは数学における AI の成果のなかで最も検証しやすい種類のものだ。モデルを信用する必要はなく、検算を信用すればよい。

限界

この結果が改良したのは下界であり、8 次元におけるキャップ集合の正確な最大値は定まっていない。漸近的にも 2.2202 と 2.756 の間には大きな隔たりが残る。そのため本記録は「部分的結果」としている。

∎