ひまわり予想、ついに陥落

1から n までの数を考え、そこからいくつかを選ぶ方法をすべて見てみよう。そのような部分集合は 2ⁿ 個ある。ここで、まったく同じ共通部分を持ち、それ以外には何も共有しない部分集合をいくつか選ぶ。数学者はこれを**ひまわり（sunflower）**と呼ぶ。共通部分が芯で、各集合の残りの部分が、ほかのどの花びらとも触れない花びらだ。

ひまわりは組合せ論の基本的な道具だ。論文には、ある種の論理回路の限界、「キャップセット」問題、高速な行列の掛け算、情報理論とのつながりが挙げられている。

1970年からの問い

著者らによれば、ひまわりについての最も自然な問いは、1970年のポール・エルデシュの論文にさかのぼる。{1, …, n} の部分集合の集まりは、そのどの k 個の集合もひまわりを作らないとき、どこまで大きくなれるか。

1970年代、エルデシュとセメレディ・エンドレは、そのような集まりはありうる 2ⁿ 個の部分集合より指数関数的に小さくなければならない、と予想した。つまり、2 より真に小さいある数 c について、高々 cⁿ 個だ。

何十年もの間、最良の上界はわずかに削るだけで、底を 2 より下げるには決して足りなかった。解決していたのは花びら3枚の場合（k = 3）だけで、2016年、キャップセット問題での画期的な進展と、Alon、Shpilka、Umansによる帰着によって決着した。

上界

Matija BucićとFankang He（ウィーン大学）、Hyunwoo Lee（KAISTおよび韓国の基礎科学研究院）は、この予想をすべての k ≥ 3 について証明した。主定理はこうだ。花びら k 枚のひまわりを含まない集まりの要素数は、高々

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

である。底は 2 のすぐ下にあるが、2 より下の固定された数であり、それこそがエルデシュとセメレディの求めたものだった。1997年のある構成は、k が大きいとき、真の値はこれよりあまり低くはなりえないことを示している。

集合からベクトルへ

証明は、問題をベクトルで表した版を経由する。数を、D 個の要素からなる n 個のブロックに分け、各ブロックから1つずつ要素を選ぶ。それぞれの選び方が1つのベクトルになる。いくつかのベクトルは、どの位置でも成分がすべて等しいか、すべて異なるとき、ひまわりを作る。

次に著者らは「ひまわり判定器」を組み立てる。これは、ひまわりを含まない集まりの上では、入力がすべて同じベクトルのときにだけゼロでない値をとる関数だ。新しい要素は、この関数を一歩ずつ、次数の低い補間多項式で書き表すことにある。そうした多項式を数えることで、集まりの大きさに上界が得られる（論文の定理2）。そして確率的な議論、つまりランダムなブロックをあらゆる集合の大きさにわたって平均することで、この上界を普通の集合に引き戻す。

機械が見つけ、別の機械が確かめた

AIについての論文の記述は、異例なほど率直だ。定理2の証明は ChatGPT 6 Astra Pro が見つけた。既知の花びら3枚の議論を一般化するよう頼むことから始まった短いやりとりの後のことだ。著者らはこの一歩を別の目標のために必要としていた。セメレディが提起したグラフの問題の誘導版で、これは後の論文で発表する予定だという。

モデルは証明を「スライスランク（slice rank）」の言葉で書いた。著者らはそれを、読者にとってわかりやすいと考える多項式法の言葉で書き直した。彼らはすべての結果を確認し、全責任を負うと述べている。また、証明は証明検証ソフトウェアである Lean 4.35 で検証済みであり、その検証結果は Palomar リポジトリで公開される予定だという。

解決していないこと

著者らは底の最適化を試みなかった。花びら3枚の場合、この結果は2017年のNaslundとSawinによる上界、およそ1.89を上回るものではない。そして、より強い姉妹問題であるエルデシュ–ラドのひまわり予想は未解決のままだ。彼らの上界はいまだにブロックの大きさ D に強く依存しているが、それこそがその問題で許されていないことなのだ。