半分の元を探して —— 和集合閉集合予想・攻略ノート（1）最前線の再現と壁の測量

半分の元を探して —— 和集合閉集合予想・攻略ノート（1）

最前線の再現と壁の測量

このシリーズについて

新しい攻略ノートを始める。標的は Frankl の和集合閉集合予想（union-closed sets conjecture）。主張は一文で書ける初等的なものなのに、45年間未解決の組合せ論の名物問題である。

この標的を選んだ理由は戦略的である。2022年、この問題の最前線はエントロピー論法（情報量の簿記）によって大きく動いた。情報量の簿記は、前シリーズ（発散情報保存理論・全40稿）で一貫して磨いてきた道具であり、武器と戦場が噛み合っている。

交戦規定は前シリーズから引き継ぐ：主張はすべて等級づけし（検証済み／定理／仮説／未解決）、計算は実行して検算し、攻撃が失敗したときは失敗を定理まで煮詰め、撤回は帳簿に記録する。解けると約束はしない。誠実に攻めることだけを約束する。

前提知識：問題と歴史

0.1 予想の主張

有限集合の有限族 $\mathcal{F}$ が和集合閉（union-closed）であるとは、$A,B\in \mathcal{F}$ ならば $A\cup B\in \mathcal{F}$ となることをいう。

和集合閉集合予想（P. Frankl, 1979）　$\mathcal{F}$ が和集合閉で $\mathcal{F}\ne \{\varnothing \}$ ならば、$\mathcal{F}$ の集合の半数以上に属する元 $x$ が存在する。

例：$\mathcal{F}=\{\varnothing ,\{1\},\{1,2\}\}$ は和集合閉で、元 $1$ は 3 つ中 2 つの集合に属する（$2/3\ge 1/2$ ✓）。冪集合 $2^{\{1,\dots ,n\}}$ では、どの元もちょうど半数に属する。等号がタイトであることを示す基本例である。

主張はこれだけで、中学生にも説明できる。そして45年、落ちていない。

0.2 歴史：対数の時代

長い停滞の時代の主な結果：Knill（1994）は、ある元が $\ge (|\mathcal{F}|-1)/{\log }_2|\mathcal{F}|$ 個の集合に属することを示した。半分どころか、族が大きいほど割合としては 0 に向かう保証しかない。Wójcik（1999）が定数倍を改善。台集合が小さい場合（元の種類が 12 個程度まで）は計算機による全数検証で予想が確認されている（Bošnjak–Marković, Vučković–Živković らの系譜）。割合一定の保証は、2022年まで一つもなかった。

0.3 2022年の地殻変動：Gilmer のエントロピー論法

J. Gilmer（arXiv, 2022年11月）は、初めて定数割合を証明した：ある元が $\ge 0.01|\mathcal{F}|$ 個の集合に属する。証明の発想が新しかった。集合を確率変数とみなし、情報量（Shannon エントロピー）の簿記で攻める：

1. $A,B$ を $\mathcal{F}$ から独立一様に取る。$H(A)=H(B)={\log }_2|\mathcal{F}|$。
2. 和集合閉だから $A\cup B\in \mathcal{F}$、ゆえに $H(A\cup B)\le {\log }_2|\mathcal{F}|$。
3. 鍵：もし全ての元の出現頻度が $p$ 未満なら、和集合を取る操作は各ビットの分布を $1/2$ に近づけ、エントロピーを増やしてしまう（$H(A\cup B)>H(A)$）。これは 2 と矛盾。ゆえに頻度 $\ge p$ の元が存在する。

数日のうちに複数のグループ（Alweiss–Huang–Sellke、Chase–Lovett、Sawin、Pebody）が独立にこの論法を研ぎ、定数は一気に

に到達した。目標の $1/2$ まで、残り約 $0.118$。

0.4 壁：なぜ $\psi$ で止まったか

Chase–Lovett は、近似的に和集合閉な族（$A\cup B$ が族に「ほぼ」入る）で頻度が $\psi$ に張り付く構成を与えた。Gilmer 型の一発エントロピー論法は「$A\cup B\in \mathcal{F}$ ⟹ エントロピーが増えない」という情報しか使わないため、近似版と厳密版を区別できず、$\psi$ が方法の天井である。Sawin はわずかに天井を越える改良（積構造でない結合の利用）を示し、明示的評価は $\approx 0.3823$。天井の上に、指の厚さだけ隙間がある。$1/2$ へ至るには、厳密な和集合閉性（近似版にない構造）を使う新しいアイデアが要る。ここが2026年現在の最前線であり、本シリーズの戦場である。

要旨：第1稿の成果

橋頭堡1（全数検証）。台集合の元が $n=2,3,4$ 個のすべての和集合閉族（$12$・$120$・$4958$ 族）を機械で列挙し、予想の成立を確認した。あわせて、最小の最大頻度はすべての $n$ でちょうど $1/2$ だった（等号達成族は $n=4$ で 51 個）。予想が真なら、それは「ぎりぎりの真」である。改善の余地（$1/2$ を $1/2+\epsilon$ に置き換える強い予想）は存在しない。

橋頭堡2（エンジンの再現）。Gilmer 論法の心臓部を再現・検証した。一ビット版：出現確率 $q$ のビットの和集合は確率 $2q-q^2$ で 1 になり、エントロピー差 $h(2q-q^2)-h(q)$ は $q<\psi$ で正、$q=\psi$ でちょうど零（$(1-\psi {)}^2=\psi$ を $10^{-12}$ 精度で確認）。本物のスカラー補題（条件つき版の核）：

（最小は角 $x=y=1-p$ で達成することを格子探索で確認）、そして $p=\psi$ でちょうど $c_p=1/2$ となる。天井の位置を数値で測量した。

最初の定理（小さいが自前）。「二つの和集合でダメなら三つ・四つ束ねればよいのでは」という自然な多重化案を検査した：

定理F1（多重化の袋小路）　$k$ 重和集合 $A_1\cup \cdots \cup A_k$ を使う一発エントロピー論法の固定点 $q_k$（$(1-q{)}^k=q$ の根）は $k$ について厳密に減少する（$q_2=\psi \approx 0.382$、$q_3\approx 0.318$、$q_4\approx 0.276,\dots$）。ゆえにこの論法の族内では二重和集合が最適であり、多重化は改悪である。

証明　$k$ を増やすと固定 $q$ で $(1-q{)}^k$ は厳密減少するから、等式 $(1-q{)}^k=q$ を保つには $q$ が減るしかない（左辺は $q$ の減少関数、右辺は増加関数なので根は一意）。$■$（$k=\mathrm{2..8}$ の数値でも単調性を確認。おそらく folklore だが、壁の地図の一部として自前で確定させた。）

直観的な理由も明快である：和集合を重ねるほどビットは 1 に飽和し、分布が $1/2$ から遠ざかる方向に押されて、エントロピー増大の動力が失われる。壁を越える鍵は「もっと混ぜる」ことではない。

第一部　橋頭堡：全数検証が教える三つのこと

1. 予想は「ぎりぎりの真」である

$n\le 4$ の全数検証（$12+120+4958$ 族、機械照合）から読み取れること：

1. 反例は小さな世界にはない。これは既知（文献では $n\le 12$ 程度まで確認済み）だが、自前の検証系を持ったことが後続稿の資産になる。攻撃案が出るたび、まず $4958$ 族に当てて即座に棄却検査ができる。
2. 等号達成族が豊富にある（$n=4$ で 51 個）。冪集合だけでなく、その変種が多数 $1/2$ に張り付く。証明は、これらすべてで等号が成り立つ「余裕のない」議論でなければならない。ゆるい不等式の積み上げでは原理的に届かない。
3. 強化予想は偽である。最大頻度 $\ge 1/2+\epsilon$ はいかなる $\epsilon >0$ でも成立しない。目標値は動かせない。

2. エンジンルームの見取り図

Gilmer 論法の全体は「チェーンルールでビットごとに分解し、各ビットでスカラー不等式を適用する」構造をもつ。検証したスカラー補題 $c_p$ の意味：$h(xy)\ge c_p(h(x)+h(y))$（$x,y$ は各コピーでビットが 0 の条件つき確率、$\ge 1-p$）。チェーンルールで束ねると $H(A\cup B)\ge 2c_{p}H(A)$ が出て、$c_p>1/2$ なら $H(A\cup B)>H(A)={\log }_2|\mathcal{F}|$ で矛盾する。$c_p=1/2$ となる $p=\psi$ が正確に天井である。数値測量はこの理論値を格子探索で再現した（$p=0.30$ で $0.5672$、$p=\psi$ で $0.500000$、$p=0.40$ で $0.4854$）。

第二部　壁の測量と、越えるための候補

3. 壁の正体（Chase–Lovett）を自分の言葉で

天井 $\psi$ の原因は、論法が使う情報の貧しさにある。使ったのは「$A\cup B$ が族に入る ⟹ $H(A\cup B)\le {\log }_2|\mathcal{F}|$」だけで、これは近似的に和集合閉な族でも成り立つ性質であり、Chase–Lovett の構成はそのクラスに $\psi$ 張り付きの例があることを示した。つまり、厳密な和集合閉性がもつ情報のうち、一発エントロピー論法は「一回の和のエントロピー上界」しか使っていない。使い残している構造、すなわち反復（$\mathcal{F}$ は和の反復でも閉じる）、束構造（$\mathcal{F}$ は結び半束）、部分族の遺伝性（$x$ を含まない集合の族 ${\mathcal{F}}_{\neg x}$ も和集合閉）のどれかに、残り $0.118$ が眠っている。

4. 候補の第一次検査：定理F1

使い残しの筆頭候補「反復」を検査したのが定理F1である。結果は袋小路、しかし収穫のある袋小路だった。$k$ 重和集合は情報を増やさず、ビットを 1 に飽和させてエントロピーの動力をむしろ削る。前シリーズの語彙を借りれば、混ぜすぎは情報を読みたい方向と直交する方向へ押し流す。壁を越える構造は「回数」ではなく「条件づけの仕方」（束構造・遺伝性）の側にあると、第一次検査は示唆している。

5. 帳簿（新シリーズ・第1項）

F-1.（第1稿）全数検証 $n\le 4$（$4958$ 族・予想成立・最小最大頻度ちょうど $1/2$・等号族 51）。Gilmer エンジンの再現（固定点 $\psi$ の $10^{-12}$ 検証、スカラー補題 $c_p$ の格子測量、$c_{\psi }=1/2$）。定理F1：多重和集合の固定点 $q_k$ は厳密減少、多重化は袋小路（証明二行＋数値）。未解決の的：束構造・遺伝性 ${\mathcal{F}}_{\neg x}$ を使う条件つきエントロピー論法の設計。

第三部　次稿への計画

6. 攻撃計画（2）

第2稿の的は遺伝性である。元 $x$ を含まない集合たちの族 ${\mathcal{F}}_{\neg x}$ もまた和集合閉であり、予想は「ある $x$ で $|{\mathcal{F}}_{\neg x}|\le |\mathcal{F}|/2$」と同値である。この再帰構造（族の中に同じ問題の小さいコピーが入れ子になっている）は、一発論法が完全に捨てている厳密構造であり、Sawin が天井をわずかに越えた際に使った「積でない結合」とも別方向である。条件つきエントロピーの簿記を入れ子に沿って組めるか。まず $4958$ 族の橋頭堡でデータを取り、入れ子の深さと最大頻度の相関を測るところから始める。

7. 結び

45年ものの予想に、2022年に初めて開いた突破口があり、突破口は3週間で天井に達し、天井には指一本分の隙間（Sawin）が確認されている。これほど「攻め時」の輪郭が明確な未解決問題は珍しい。第1稿で橋頭堡（検証系・エンジンの再現・壁の座標）は築いた。武器は前のシリーズで40稿かけて磨いた情報量の簿記である。焦らず、等級を偽らず、失敗は定理に換えて進む。攻略ノート、開帳。

参考文献

• P. Frankl（1979頃、口頭・文献上の初出には諸説）：予想の提起。総説として H. Bruhn & O. Schaudt, The journey of the union-closed sets conjecture, Graphs Combin. 31 (2015)
• E. Knill, Graph generated union-closed families of sets（1994, arXiv math/9409215）：対数下界
• P. Wójcik, Union-closed families of sets, Discrete Math. 199 (1999)：対数時代の改善
• J. Gilmer, A constant lower bound for the union-closed sets conjecture（arXiv:2211.09055, 2022）：エントロピー論法による定数割合の突破
• R. Alweiss, B. Huang, M. Sellke（arXiv:2211.11731）；Z. Chase & S. Lovett（arXiv:2211.11689）；W. Sawin（arXiv:2211.11504）；L. Pebody（arXiv:2211.11227）（すべて2022）：定数 $\psi =(3-\sqrt{5})/2$ への即時改良と、方法の限界・天井越えの微小改良
• I. Bošnjak & P. Marković, The 11-element case of Frankl's conjecture, Electron. J. Combin.（2008）ほか：小さな台集合の全数検証の系譜