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

最前線の再現と限界の見積もり

このシリーズについて

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

この問題を選んだ理由ははっきりしている。2022年、この問題の最前線はエントロピー論法（情報量の数え上げ）によって大きく動いた。情報量の数え上げは、前シリーズ（発散情報保存理論・全7部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$ 未満なら、どのビットも 0 の側に偏っている。和集合を取る操作はその偏りをほぐして分布を $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$ へ上がる。この二つの確率に対応する一ビットぶんのエントロピーの差 $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$（$n=2,3,4$ でそれぞれ $12$・$120$・$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 が上限をわずかに越えた際に使った「積でない結合」とも別方向である。条件つきエントロピーの評価を入れ子に沿って組めるか。ただし遺伝分解が最初に差し出してくるのは、エントロピーではなく個数の比較である（「ある $x$ で $|{\mathcal{F}}_{\neg x}|\le |\mathcal{F}|/2$」は、含まない側から含む側への単射があれば済む）。そこでまず $4958$ 族の検証系でデータを取り、この単射がどこまで作れてどこで折れるかを測るところから始める。

7. 結び

45年ものの予想に、2022年に初めて開いた突破口があり、突破口は数日のうちに方法の上限へ達し、上限のすぐ上にごくわずかな隙間（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）ほか：小さな台集合の全数検証の系譜