フランクルの予想（和集合で閉じた族・1%から38%へ）

証明の筋はこうだ。どの要素もまれにしか現れない族があるとすると、2つの集合の和集合のほうが、元の集合より情報が多くなる。ところが和集合で閉じた族では、和集合は族の中に収まるので、情報は増えない。この矛盾を式で書く。

有限集合$[n]=\{1,\dots ,n\}$の部分集合を集めた族$\mathcal{F}$が和集合で閉じていて、空でない集合を1つ以上含むとする。空集合が$\mathcal{F}$に入っていてもよく、入っていれば割合の分母に数える。このとき、ある要素は$\psi =(3-\sqrt{5})/2$以上の割合の集合に入る。2022年に4組が示したこの定理を、チェイスとロヴェットが3ページの論文で示した道筋で追う。

$\mathcal{F}$から独立に等確率で集合$A$、$B$を選び、和集合を$U=A\cup B$と書く。要素$i$が$A$に入っていれば$A_i=1$、入っていなければ$A_i=0$と書き、$A_{<i}=(A_1,\dots ,A_{i-1})$とする。$H$はシャノンのエントロピーで、$h(x)=-x{\log }_{2}x-(1-x){\log }_2(1-x)$は確率$x$で1になるビットのエントロピーである。ただし$h(0)=h(1)=0$とする。$\phi =(1+\sqrt{5})/2$は黄金比である。

1. $U$は$\mathcal{F}$の集合だから、とりうる値は$|\mathcal{F}|$個しかない。エントロピーは等確率のときに最大で、$A$はその等確率である

   $$\begin{array}{rl}H(U)& \le {\log }_2|\mathcal{F}|\\ & =H(A)\end{array}$$

2. 要素を1つずつ明かしていくと、エントロピーは連鎖律で足し算に分かれる

   $$\begin{array}{rl}& H(A)\\ & =\sum _{i}H(A_i\mid A_{<i})\end{array}$$

3. $U$も同じように分かれる。$U_{<i}$は$A_{<i}$と$B_{<i}$から決まるので、条件を$C_i=(A_{<i},B_{<i})$に増やすと、エントロピーは減るか変わらない

   $$\begin{array}{rl}& H(U)\\ & \ge {\sum }_{i}H(U_i\mid C_i)\end{array}$$

4. $i$を固定する。過去$A_{<i}$のもとで$A_i=0$となる確率を$X$、過去$B_{<i}$のもとで$B_i=0$となる確率を$Y$とする。$X$と$Y$は独立で同じ分布に従う。和集合の$i$番目が0になるのは$A_i$も$B_i$も0のときだけだから

   $$\begin{array}{rl}& H(U_i\mid C_i)\\ & =\mathbb{E}[h(XY)]\end{array}$$

5. 要になるのは、$0\le x,y\le 1$で成り立つ次の不等式である。証明はこの章の後半に回す

   $$\begin{array}{rl}& h(xy)\\ & \ge \frac{\phi }{2}(xh(y)\\ & +yh(x))\end{array}$$

6. $x=X$、$y=Y$を入れて平均をとる。独立だから積の期待値は期待値の積になり、$q_i=\mathrm{Pr}(A_i=0)$とおくと$\mathbb{E}[X]=q_i$、$\mathbb{E}[h(X)]=H(A_i\mid A_{<i})$である

   $$\begin{array}{rl}& \mathbb{E}[h(XY)]\\ & \ge \phi q_{i}H(A_i\mid A_{<i})\end{array}$$

7. ここで、どの要素も$\psi$未満の割合の集合にしか入らないと仮定する。$q_i>1-\psi =1/\phi$だから、係数は1を超える

   $$\phi q_i>1$$

8. 手順2から7をつなぐ。$|\mathcal{F}|\ge 2$なら$H(A)={\log }_2|\mathcal{F}|>0$で、どれかの$H(A_i\mid A_{<i})$は正だから

   $$H(U)>H(A)$$

手順1と矛盾する。残る$|\mathcal{F}|=1$の場合は、ただ1つの集合が空でないので、その要素が100%の集合に入る。どちらの場合も、$\psi$以上の割合の集合に入る要素がある。

手順5の不等式は、両辺を$xy$で割って$g(t)=h(t)/t$とおくと、$g(xy)\ge \frac{\phi }{2}(g(x)+g(y))$になる。チェイスとロヴェットは、比$g(xy)/(g(x)+g(y))$が内側で1未満、端で1になることから最小点は内側にあるとし、そこで偏微分を0とおいた。$t{g}^{\prime }(t)={\log }_2(1-t)/t$は単調に減るので、$x=y$が出る。残るのは1変数の不等式である。

この形には前史があり、ラヴィ・ボッパナが1980年代に使っていた。ボッパナが2023年に公開した短い証明では、$f(x)=h(x^2)-\phi xh(x)$を3回微分する。分子は負の根を持つ3次式になるので、$f^{\prime \prime \prime }$の$(0,1)$の零点は高々2個である。ロルの定理を3回使うと、$f$の零点は$[0,1]$に重複を数えて高々5個で、$x=0$の重根、$x=1/\phi$の重根、$x=1$の単根で尽きる。$f$は符号を変えず、0に近い$x$で正だから、全体で$f\ge 0$となる。ここで省いたのは、3回の微分の計算と、端での比の値や根の重複度を確かめる計算である。

ギルマーの最初の論文は、手順5と6にあたる所を粗い場合分けで評価して、$H(A\cup B)\ge 1.26H(A)$と0.01を得ていた。2022年の4組が差し替えたのは、この1か所である。つまり、発想そのものはギルマーの手順1から4にある。アルワイスは「要素を1つずつ明かして、得られる情報の量を見ていくアイデアは実に巧妙で、そこが証明の中心だ」と語った。