9番目のデデキント数

入力$x=(x_1,\dots ,x_n)$は、どの成分も0か1をとる。どの成分でも$x_i\le y_i$のとき$x\le y$と書き、2つの関数も、すべての入力で$f(x)\le g(x)$のとき$f\le g$と書く。$n$変数の単調なブール関数の集まりを${\mathcal{D}}_n$、その個数を$D(n)$とする。

1. 単調であることを、大小の関係で書く

   $$\begin{array}{rl}& x\le y\\ & ⟹f(x)\le f(y)\end{array}$$

2. 値が1になる入力のうち、それより小さい入力では値がすべて0になるものを集める。どの2つも大小を比べられない集まり、つまり反鎖$A$になり、$f$は$A$から次のように決まる

   $$\begin{array}{rl}& f(x)=1\\ & ⟺a\le x\text{ となる}\\ & a\in A\text{ がある}\end{array}$$

3. 1をちょうど$\lfloor n/2\rfloor$個含む$\left(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor }\right)$個の入力は、どの2つも比べられない。このうちからいくつ選んでも反鎖になるので、選び方を数えるだけで下界（かかい）が出る

   $$D(n)\ge 2^{\left(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor }\right)}$$

4. $n+1$変数の関数$f$を、最後の入力を0にした$f_0$と、1にした$f_1$に分ける。$f$が単調になるのは、$f_0$と$f_1$が単調で、どの入力でも$f_0\le f_1$のときに限る。組$(f_0,f_1)$は${\mathcal{D}}_n$から選ぶ

   $$\begin{array}{rl}& D(n+1)\\ & =\#\{(f_0,f_1):\\ & f_0\le f_1\}\end{array}$$

手順4は、立方体を向かい合う2つの面に分けて見ることにあたる。

5. $n+2$変数なら、最後の2つの入力で$f_{00}$, $f_{01}$, $f_{10}$, $f_{11}$の4つに分ける。$f_{00}\le f_{01}$, $f_{00}\le f_{10}$, $f_{01}\le f_{11}$, $f_{10}\le f_{11}$の4つの条件は、次の2つにまとまる

   $$\begin{array}{rl}& f_{00}\le f_{01}\wedge f_{10},\\ & f_{01}\vee f_{10}\le f_{11}\end{array}$$

真ん中の2つを決めてしまえば、下と上は互いに関係なく選べる。

6. $f_{01}=a$, $f_{10}=b$を決め、残る2つの選び方を掛けて足す。$a$と$b$は${\mathcal{D}}_n$全体を動く。$u\le v$のとき、$u\le g\le v$となる関数$g$の集まりを区間$[u,v]$とよび、その元の数を$\#[u,v]$と書く

   $$\begin{array}{rl}& D(n+2)\\ & =\sum _{a,b}\#[0,a\wedge b]\\ & \times \#[a\vee b,1]\end{array}$$

7. 同じ組を、先に$f_{00}\le f_{11}$を決めて数え直す。$a$と$b$は区間$I=[f_{00},f_{11}]$の中なら何でもよい

   $$D(n+2)=\sum _I(\#I{)}^2$$

8. 手順6の2つの数を、行列$M(a,b)=\#[0,a\wedge b]$と$N(a,b)=\#[a\vee b,1]$の成分とみる。$N$は対称なので、和は積$MN$の対角成分の和になる

   $$D(n+2)=\mathrm{Tr}(MN)$$

9. 手順6の組を、$a\wedge b=u$, $a\vee b=v$となる組$(u,v)$ごとにまとめる。こうなる$(a,b)$の数は$2^{C(u,v)}$と書ける¹

   $$\begin{array}{rl}& D(n+2)\\ & =\sum _{u\le v}\#[0,u]2^{C(u,v)}\\ & \times \#[v,1]\end{array}$$

手順6の式は、1976年にバーマンとケーラーが示していた。手順7の形まで直せば、区間の大きさを2乗して足すだけで$D(n+2)$が出る。

2つのチームは、この同じ切り分けから別々の方向に進んだ。イェーケルは入力を一度に4つ切り分ける式を作り、$D(9)$を${\mathcal{D}}_5$の7,581個から組み立てた。${\mathcal{D}}_7$を元にしなかったのは、2兆4千億個あまりの元を書き出すだけで約38.63テラバイトが要るからだ。代わりに、${\mathcal{D}}_5$にある7,828,354個の区間を、形が同じもの、上下を裏返すと同じになるものを1つにすれば、9,919種類に減らせる。形の同じものを見つけるのに、形式概念分析という束の表し方と、グラフの同型を調べるソフトウェアnautyを使った。区間の中の組も同じようにまとめ、86億あまりあった組を4,257,682,565組まで減らしている。組ごとに最大7,581行の行列を掛け、手順8と同じくトレースを足していく。

ファン・ヒルトゥムらは、手順9の式を$n=7$で使った。変数の入れ替えで移り合う関数をまとめ、一方の関数を約4億9千万の代表に絞る。代表ごとに、もう一方の候補を平均4,600万個とり、7変数の入れ替え5,040通りを試す。数える項は、合わせて$5.574\times 10^{18}$個。$C(u,v)$を求めるには図のかたまりを数える必要があり、枝分かれの多い処理なので、CPUでもGPUでも速く回らない。そこでチームは、この計算だけをする回路をFPGAという書き換えのできるチップに300個並べ、450 MHzで動かした。論文誌の版によると、64コアのCPU向けに最適化したプログラムの95倍の速さで、FPGAを延べ4万7千時間使っている。ファン・ヒルトゥムは大学の発表で、「$D(8)$なら8分で済む計算が、$D(9)$では数十万年になる」と話し、大型のスーパーコンピューターを独り占めしても何年もかかると続けた。