MathLabs

解法: 多項式法によるキャップ集合問題の解決(クロート=レフ=パック、エレンバーグ=ハイスヴァイト、2016年)

ステップ 7/7: 論理を閉じる:予想より指数的に少ないキャップ集合
ざっくり言うと

ステップ5とステップ6を組み合わせると、何十年も未解決だった指数的増加率の問いが解決する:F3n\mathbb{F}_3^n 内のいかなるキャップ集合も、およそ 2.756n2.756^n 個を超える要素を持つことはできず、自明な 3n3^n より決定的に少ない。同じ多項式法のアイデアは、数日のうちに独立に2つの研究チームによって発見され、すべての素数べき qq について Fqn\mathbb{F}_q^n 上の関連問題にもはるかに良い評価を与えた。

∣A∣≤3⋅(2.756)n|A| \le 3 \cdot (2.756)^n
詳しい解説

ステップ5の不等式 ∣A∣≤3 m(q−1)n/3|A| \le 3\, m_{(q-1)n/3} とステップ6の q=3q=3 における m(q−1)n/3m_{(q-1)n/3} の評価 3e−I(2/3)<2.7563e^{-I(2/3)} < 2.756 を組み合わせると、最終定理が得られる:F3n\mathbb{F}_3^n 内のすべてのキャップ集合 AA は ∣A∣≤3⋅(2.756)n|A| \le 3 \cdot (2.756)^n を満たし、指数的な増加率の問いを否定的に解決する(その率は 33 ではない)。エレンバーグとハイスヴァイトの短い論文(2017年)は、クロート、レフ、パック(2016年)が数週間前に密接に関連する群 (Z/4Z)n(\mathbb{Z}/4\mathbb{Z})^n に対して導入した画期的な多項式法を、任意の有限体 Fq\mathbb{F}_q へと定式化・一般化する。論文の注釈1は、2人の著者が独立かつほぼ同時にキャップ集合の議論を展開したことを記している。