s (f) \geq de g (f)

感度予想

Sensitivity conjecture (Huang's theorem)

マドリードのホテルで申請書を書くうち、符号を変える考えが浮かんだ。

0 と 1 の関数の感度は、多項式の次数の平方根以上になる。2019 年、ファンは立方体の頂点の問題を解き、30 年近く残った感度予想を証明した。

年代: 2019年
習う: 大1・線形代数・固有値と固有ベクトル
レベル: 大学(例題 5 問)
人物: ハオ・ファン、ノーム・ニサン、マリオ・セゲディ、クレイグ・ゴッツマン、ナティ・リニアル、マイケル・サックス、クロード・シャノン

数学情報科学物理学工学

逸話

5 個目の頂点

サイコロの形の立方体の頂点 8 個から、どの 2 つも辺で隣り合わないように選ぶと、何個まで選べるか。答えは 4 個である。頂点を 0 と 1 の 3 けたで書くと、辺でつながる 2 頂点はちょうど 1 けただけ違う。000・011・101・110 のように 1 の個数が偶数の頂点を集めれば、どの 2 つも 2 けた違うので、辺で隣り合わない。一方、8 個の頂点は辺で結ばれた 2 個ずつの 4 組に分けられるので、5 個を選ぶと、同じ組の 2 個が必ず入る。

5 個目を足すと、辺は 1 本では済まない。001 を足せば、001 は 000・011・101 の 3 つと辺でつながる。選び方を工夫しても、5 個のうちどれかの頂点は、選んだ頂点と 2 本以上の辺でつながる(図の 1 枚目)。では $n$ 次元の立方体から、半分より 1 つ多い $2^{n - 1} + 1$ 個を選ぶと、選んだ頂点どうしの辺がいちばん多く集まる頂点には、何本の辺が集まるか。

2019 年 7 月 1 日、アメリカ・アトランタのエモリー大学で助教授をしていたハオ・ファンが、この問いに答える論文を arXiv に公開した。答えは $n$ 本以上である。arXiv の原稿は参考文献まで入れて 6 ページで、証明の部分は 2 ページほどしかない。この不等式から、理論計算機科学で 30 年近く解けなかった「感度予想」がすぐに従う。

ハオ・ファン21 世紀に活躍立方体の頂点の問題を符号つきの行列で解き、感度予想を証明した

翌日、計算機科学者スコット・アーロンソンはブログでこの証明を紹介し、「神でさえ、これより簡単に感度予想を証明する方法を知っているとは思えない」と書いた。7 月 3 日、ファンはその記事のコメント欄に、ここまでの経緯を書き込んだ。2012 年 11 月、プリンストン高等研究所のポスドク(博士研究員)だったときに、数学者マイケル・サックスからこの問題を教わった。科学誌 Quanta の記事によれば、2 人で昼食をとっていたときのことである。

秋の林が見える大きな窓の食堂で、2 人の男性が昼食をとりながら話す。2 人とも後ろ姿か遠くからの姿で、顔は見えない(画像生成 AI で描いたイメージ) — 2012 年 11 月、高等研究所での昼食の席で、サックスから感度予想を聞く(Quanta の記事による)画像生成 AI で描いたイメージ

それから数週間で、知っている組合せ論の手法を出し尽くした。それでも、1988 年のチョン、フュレディ、グラハム、シーモアの論文の定数さえ改良できなかった。2013 年の半ばには、頂点の次数より、隣接行列の最大の固有値を調べるほうがよいと考えるようになる。その後は新しい道具を覚えるたびにこの予想に戻ったが、うまくいかない。「少なくとも、考えていると多くの夜すぐに眠れた」とファンは振り返る。2018 年の終わり、固有値を使う別の共同研究を終え、大学院の組合せ論の授業も何学期か受け持ったころ、固有値の交互定理(インターレース定理)がこの問題に効くかもしれないと思い始めた。

2019 年 6 月、ファンはマドリードのホテルで、研究費の申請書を苦労して書いていた。そのさなかに、辺の場所の成分を $+ 1$ か $- 1$ にした行列なら、どんな符号の付け方でも、最大の固有値は頂点の次数の最大値を超えないと気づいた。「残りは、少しの試行錯誤と線形代数だ」とコメントは続く。

夕方のホテルの部屋で、男性が窓辺の机のノートパソコンに向かう後ろ姿。窓の外にマドリードの屋根と教会の丸屋根が見える(画像生成 AI で描いたイメージ) — 2019 年 6 月、マドリードのホテルで研究費の申請書を書くうちに、証明の鍵に気づく(本人の回想による)画像生成 AI で描いたイメージ

論文の謝辞には、行列の 2 乗を計算する補題の証明を短くしてくれたのは、博士課程の指導教員だったベニー・スダコフだとある。論文は 7 月 20 日に Annals of Mathematics に投稿され、8 月 28 日に受理されて、190 巻(2019 年)に載った。

起源

リレー回路から生まれた物差し

0 と 1 を $n$ 個受け取り、0 か 1 を返す関数 $f : {0, 1}^{n} \to {0, 1}$ をブール関数という。1938 年、クロード・シャノンは、リレーとスイッチの回路をブール代数で表せることを論文にまとめた。情報エントロピーの式を立てる 10 年前である。デジタル回路は、入力のビットから出力のビットを決めるブール関数の組とみなせる。

クロード・シャノンの肖像(ClaudeShannon MFO3807) — クロード・シャノン1916–2001情報の量を測る式を立て、情報理論を始めた出典: Wikimedia Commons・Jacobs, Konrad・CC BY-SA 2.0 de

ブール関数の「感度」は、1982 年ごろ、スティーヴン・クックとシンシア・ドワーク、リュディガー・ライシュクが、並列計算機の計算時間の下限を調べる中で使い始めた量である。入力 $x$ の $i$ けた目だけを反転した入力を $x^{(i)}$ と書く。

s (f, x) = # {i : f (x) \neq = f (x^{(i)})}, s (f) = x max s (f, x)

1 けたの反転で出力が変わるけたを、いちばん多い入力で数えた数である。 $n$ ビットの OR(どれか 1 つでも 1 なら 1)は、入力が全部 0 のとき、どのけたを反転しても出力が 1 に変わるので、 $s = n$ になる。

1989 年、ノーム・ニサンは、けたを 1 つずつでなく、重ならないまとまり(ブロック)ごとに反転して数える「ブロック感度」 $b s (f)$ を考えた。定義から $b s (f) \geq s (f)$ である。ニサンは、CREW PRAM という並列計算のモデルでブール関数を計算する時間が、 $lo g b s (f)$ の程度になることも示している。

もう 1 つの物差しが多項式の次数である。ブール関数は、どの変数についても 1 次の多項式(多重線形の多項式)で、ただ 1 通りに書ける。2 ビットの OR なら $x_{1} + x_{2} - x_{1} x_{2}$ で、次数 $de g (f)$ は 2 である。ニサンとマリオ・セゲディは 1992 年の学会(STOC)で発表した論文で、次数がブロック感度や決定木の深さと多項式の関係にあることを示した。たとえば $b s (f) \leq 2 de g (f)^{2}$ である。決定木とは、入力のけたを 1 つずつ問い合わせて答えを決める手順をいう。1994 年に論文誌に載った版の最後の章「未解決の問題」で、2 人は問うている。感度とブロック感度の間にも多項式の関係があるか。たとえば $s (f)^{2} \geq b s (f)$ か。

この問いに「ある」と答えるのが感度予想である。ブロック感度と次数は多項式の関係にあるので、「次数は感度の多項式で抑えられる」と言い換えてもよい。

同じ 1992 年、クレイグ・ゴッツマンとナティ・リニアルは、この問題を立方体の問題に言い換えた。 $n$ 次元の立方体の頂点を、ちょうど半分ではない個数だけ選ぶ。選んだ頂点どうしの辺と、選ばなかった頂点どうしの辺について、1 つの頂点に集まる本数の最大を $Γ$ とする。どの選び方でも $Γ \geq h (n)$ となることと、どのブール関数でも $s (f) \geq h (de g f)$ となることが同値になる( $h$ は単調に増える関数)。2 人はさらに強く、 $de g (f) = O (s (f)^{2})$ と予想した。

立方体の側では、チョン、フュレディ、グラハム、シーモアが 1988 年に、半分より多く選べば最大の本数は $(\frac{1}{2} - o (1)) lo g_{2} n$ 以上になることを示し、本数を $⌈ n ⌉$ に抑える選び方も作っていた。下限は対数、例は平方根で、その間が埋まらない。関数の側では、1995 年にデイヴィッド・ルビンスタインが $b s (f) = \frac{1}{2} s (f)^{2}$ となる関数を作った。ブロック感度を感度で抑える式は、指数関数の形しか知られていなかった。

予想と、証明されたことを分けて並べる。

ニサンとセゲディの問い(感度予想) ある定数 $C$ があって、すべての $f$ で $b s (f) \leq s (f)^{C}$ となるか。
ゴッツマンとリニアルの同値と予想 立方体の問題と $s (f) \geq h (de g f)$ の問題は同じ。予想は $de g (f) = O (s (f)^{2})$ 。
ファンが示したこと 半分より 1 つ多い頂点を選べば $Δ \geq n$ 。ここから $s (f) \geq de g (f)$ が出て、ゴッツマンとリニアルの予想が成り立つ。アビシャイ・タルの $b s (f) \leq de g (f)^{2}$ (2013 年)と合わせて $b s (f) \leq s (f)^{4}$ となり、感度予想が解けた。

証明

偶奇で塗り替え、符号で数える

前半で関数の問題を立方体の問題に直し(ゴッツマンとリニアルの同値のうち、ここで使う向き)、後半で立方体の問題を解く。頂点から出る辺の本数を、その頂点の次数という。一筆書きの定理で数えた次数と同じものである。多項式の次数と紛れないよう、グラフ $H$ の頂点の次数の最大値を $Δ (H)$ と書く。

$f$ の次数を $d$ とし、係数が 0 でない $d$ 次の項 $x_{S}$ を 1 つ選ぶ。 $S$ の外の変数をすべて 0 に固定した関数を $g$ とする。 $S$ の外の変数を含む項だけが消えるので $x_{S}$ は残り、感度は増えない。
$de g (g) = d, s (g) \leq s (f)$
$g$ は $d$ 変数の関数で、最高次の係数は値の交代和で書ける( $∣ x ∣$ は $x$ の 1 の個数)。
$c_{S} = x \in {0, 1}^{d} \sum (- 1)^{d - ∣ x ∣} g (x) \neq = 0$
1 の個数が偶数の頂点の集まりを $E$ 、奇数の集まりを $O$ とする。偶数の頂点では $g$ の値を、奇数の頂点では反転した値を見て、頂点の集合 $V_{1}$ を作る。残りを $V_{0}$ とする。
$V_{1} = {x \in E : g (x) = 1} \cup {x \in O : g (x) = 0}$
$∣ E ∣ = ∣ O ∣ = 2^{d - 1}$ を使って数えると、 $V_{1}$ の大きさはちょうど半分にならない。
$∣ V_{1} ∣ = 2^{d - 1} + x \in E \sum g (x) - x \in O \sum g (x) = 2^{d - 1} + (- 1)^{d} c_{S} \neq = 2^{d - 1}$
辺でつながる 2 頂点は 1 の個数の偶奇が逆なので、2 つが同じ側( $V_{1}$ どうしか $V_{0}$ どうし)に入るのは、 $g$ の値が違うときだけである。よって頂点 $x$ から同じ側へ出る辺の本数は、 $x$ での感度に等しい。
$# {i : x と x^{(i)} が同じ側} = s (g, x)$
$V_{1}$ と $V_{0}$ の一方は $2^{d - 1} + 1$ 個以上の頂点をもつ。そこから $2^{d - 1} + 1$ 個を選んだグラフ $H$ に、後半で示す $Δ (H) \geq d$ を使う。
$s (f) \geq s (g) \geq Δ (H) \geq d = de g (f)$

後半では、 $n$ 次元の立方体 $Q_{n}$ から $2^{n - 1} + 1$ 個の頂点を選んだグラフ $H$ について、 $Δ (H) \geq n$ を示す。

行列を順に作る( $I$ は単位行列)。左上と右下のブロックが $n - 1$ 次元の 2 つの立方体に、 $I$ がその間をつなぐ辺にあたる。成分は 0 か $\pm 1$ で、 $- 1$ を $1$ に替えると $Q_{n}$ の隣接行列になる。
$A_{1} = (0110), A_{n} = (A_{n - 1} I I - A_{n - 1})$
ブロックごとに 2 乗すると、右上と左下は $A_{n - 1} - A_{n - 1} = O$ で消える。帰納法の仮定 $A_{n - 1}^{2} = (n - 1) I$ を使う。
$A_{n}^{2} = (A_{n - 1}^{2} + I O O A_{n - 1}^{2} + I) = n I$
固有値 $λ$ は $λ^{2} = n$ を満たす。トレース(対角成分の和)が 0 なので、 $n$ と $- n$ が同じ数ずつ並ぶ。
$n が 2^{n - 1} 個, - n が 2^{n - 1} 個$
$H$ の頂点の行と列だけを残した行列を $A_{H}$ とする。固有値 $n$ の固有ベクトルの空間は $2^{n - 1}$ 次元、 $H$ にない頂点の成分がすべて 0 のベクトルの空間は $2^{n - 1} + 1$ 次元で、次元の和が $2^{n}$ を超える。よって両方に入る 0 でないベクトル $v$ がある。 $v$ から $H$ の頂点の成分だけを抜き出したベクトルを $v_{H}$ とすると、 $∣ v_{H} ∣ = ∣ v ∣$ である。
$v_{H}^{T} A_{H} v_{H} = v^{T} A_{n} v = n ∣ v ∣^{2}$
対称行列 $B$ の最大の固有値は、 $x^{T} B x /∣ x ∣^{2}$ の最大値である。手順 10 と合わせると、コーシーの交互定理(インターレース定理)のうち、ここで要る部分になる。
$λ_{1} (A_{H}) \geq \frac{v _{H}^{T} A _{H} v _{H}}{∣ v _{H} ∣ ^{2}} = n$
$A_{H}$ の固有値 $λ_{1}$ の固有ベクトル $w$ で、絶対値が最大の成分を $w_{u}$ とする。 $u$ の行で 0 でない成分は、 $H$ の中で $u$ と隣り合う頂点 $y$ の列にだけあり、多くとも $Δ (H)$ 個で、大きさはどれも 1 である。 $∣ w_{y} ∣ \leq ∣ w_{u} ∣$ を使う。
$λ_{1} ∣ w_{u} ∣ = y \sim u \sum (A_{H})_{u y} w_{y} \leq Δ (H) ∣ w_{u} ∣$
手順 11 と手順 12 を合わせる。
$Δ (H) \geq λ_{1} (A_{H}) \geq n$

手順 8 の打ち消しは、辺の符号で見ると分かりやすい。方向 $k$ の辺の符号は、頂点の座標で $k$ より上のけたにある 1 の個数の偶奇で決まり、どの正方形の面でも $- 1$ の辺は奇数本になる(図の 2 枚目)。向かい合う 2 頂点を結ぶ 2 通りの道は符号の積が逆になり、 $A_{n}^{2}$ の対角でない成分は 0 になる。対角の成分は、各頂点から出る $n$ 本の辺の $(\pm 1)^{2}$ を足した $n$ である。

最後に、タルの不等式 $b s (f) \leq de g (f)^{2}$ と組み合わせる。

b s (f) \leq de g (f)^{2} \leq (s (f)^{2})^{2} = s (f)^{4}

ファンの論文によれば、立方体の不等式は $n$ が平方数のとき等号の例がある。関数の不等式も、 $k$ 個ずつの OR を AND で束ねた関数で $s (f) = k$ , $de g (f) = k^{2}$ となり、これ以上はよくできない。

途中の計算

4 行 4 列の行列を 2 乗する

正方形の 4 頂点を 00・01・10・11 の順に並べ、手順 7 の行列で $n = 2$ の場合を手で確かめる。

$A_{1}$ を 2 乗する
$A_{1}^{2} = (0110) (0110) = (1001) = I$
漸化式に $n = 2$ を入れる
$A_{2} = (A_{1} I I - A_{1}) = 01101001 100 - 1 01 - 1 0$
ブロックのまま 2 乗を展開する
$A_{2}^{2} = (A_{1}^{2} + I^{2} I A_{1} - A_{1} I A_{1} I - I A_{1} I^{2} + A_{1}^{2})$
$I A_{1} = A_{1} I = A_{1}$ を使う
$A_{1} I - I A_{1} = A_{1} - A_{1} = O$
手順 1 の $A_{1}^{2} = I$ を代入する
$A_{2}^{2} = (2 I O O 2 I) = 2 I$
1 行目と 4 列目の積を成分で確かめる
$(A_{2}^{2})_{14} = 0 \cdot 0 + 1 \cdot 1 + 1 \cdot (- 1) + 0 \cdot 0 = 0$
固有ベクトル $v$ に $A_{2}$ を 2 回掛ける
$A_{2}^{2} v = λ^{2} v = 2 v$
$λ^{2} = 2$ を解く
$λ = \pm 2$
トレースが 0 なので、 $\pm 2$ が 2 個ずつ
$2 + 2 - 2 - 2 = 0 = tr A_{2}$
頂点 00・01・10 の行と列だけを残す
$A_{H} = 011100100$
固有方程式を展開する
$det (λ I - A_{H}) = λ^{3} - 2 λ = λ (λ^{2} - 2) = 0$
最大の固有値を読む
$λ_{1} (A_{H}) = 2$
00 に辺が 2 本集まるので、手順 12 と比べる
$Δ (H) = 2 \geq λ_{1} (A_{H}) = 2 = n$

手順 6 の $1 \cdot 1$ と $1 \cdot (- 1)$ は、頂点 00 から 11 へ行く 2 通りの道(01 を通る道と 10 を通る道)にあたる。10 と 11 を結ぶ辺だけが $- 1$ なので、2 つの道が打ち消し合う。手順 13 の右の等号は、 $n = 2$ では選び方によって $λ_{1}$ が $n$ ちょうどまで下がりうることを示している。

応用

1 ビットの誤りと 4096 個のチップ

検査ビットが 1 ビットの誤りを必ず見つける理由。 1 の個数が奇数なら 1 を返すパリティ関数は、どの入力でも、どのけたを反転しても値が変わる。感度は最大の $n$ で、次数も $n$ である。7 ビットの文字コードに 1 ビットを足して 1 の個数を偶数にそろえる検査は、この性質を使う。A の文字コード 1000001 は 1 が 2 個なので、検査ビットは 0 になる。送る途中で 1 ビットだけ反転すると 1 の個数が奇数になり、誤りが分かる。2 ビットが同時に反転すると偶数に戻り、見逃してしまう。

多数決は、そろった入力で強い。 3 つの入力の多数決は、3 つがそろった 111 では感度が 0 で、どれか 1 つが反転しても答えは変わらない。110 のように割れた入力では、1 になっている 2 けたが感度をもち、どちらかが反転すると答えが変わる。同じ計算を 3 台でして多数決をとる三重化は、3 台がそろっている限り、1 台の故障に耐える。

感度が分かれば、次数とブロック感度に上限がつく。 感度が 3 の関数なら、次数は $3^{2} = 9$ 以下、ブロック感度は $9^{2} = 81$ 以下になる。

12 次元の立方体の網。 シンキング・マシンズ社の並列計算機コネクションマシン CM-2(1987 年)は、4096 個のチップを 12 次元の立方体の形の網でつないだ。チップの番号を 12 けたの 2 進数で書くと、1 けた違うチップどうしが直接つながる。

コネクションマシン CM-2(ミムズ技術芸術博物館の CM-2 とデータボールト) — コネクションマシン CM-21987年4096 個のチップを 12 次元の立方体の形の網でつないだ並列計算機出典: Wikimedia Commons・Logg Tandy・CC BY-SA 4.0

この網で、半分より 1 つ多い 2049 個のチップを選ぶとする。ファンの不等式から、選んだチップのどれかは、選んだチップのうち $12 \approx 3.46$ 個以上、つまり 4 個以上と直接つながる。チョンらの選び方を使えば、4 個で済ませられる。2048 個なら、1 の個数が偶数の番号を選べば、どの 2 つも直接にはつながらない。半分を 1 つ超えたとたん、4 本のつながりが避けられなくなる。

例題と解説

感度と次数を手で数える

例題 1基本3 人の多数決

3 つの入力のうち 2 つ以上が 1 なら 1 を返す関数 $f (x_{1}, x_{2}, x_{3})$ について、次の問いに答えよ。入力は $x_{1} x_{2} x_{3}$ の順に並べて書く。

(1) 多重線形の多項式を求め、次数を答えよ。

(2) 感度 $s (f)$ を求め、 $s (f) \geq de g (f)$ を確かめよ。

解説を見る

(1) 係数は値の交代和で求まる。1 次の項と定数項は、 $f (100) - f (000) = 0$ などからすべて 0 である。 $x_{1} x_{2}$ の係数は次のとおり。

f (110) - f (100) - f (010) + f (000) = 1 - 0 - 0 + 0 = 1

$x_{1} x_{3}$ 、 $x_{2} x_{3}$ の係数も同じく 1 である。3 次の項の係数を求める。

f (111) - (f (110) + f (101) + f (011)) + (f (100) + f (010) + f (001)) - f (000) = 1 - 3 + 0 - 0 = - 2

よって次の式で、次数は 3 である。

f = x_{1} x_{2} + x_{1} x_{3} + x_{2} x_{3} - 2 x_{1} x_{2} x_{3}

(2) 1 の個数が 2 の入力、たとえば 110 では、1 のけたのどちらを反転しても 1 の個数が 1 になり、値が 0 に変わる。0 のけたを反転しても 1 の個数は 3 で、値は 1 のままである。よって $s (f, 110) = 2$ 。1 の個数が 1 の入力でも同じく 2、000 と 111 では 0 である。

s (f) = 2 \geq 3 \approx 1.73

例題 2基本何本以上と言い切れるか

(1) 4 次元の立方体(頂点 16 個)から 9 個、(2) 10 次元の立方体(頂点 1024 個)から 513 個の頂点を選ぶ。選んだ頂点どうしの辺がいちばん多く集まる頂点には、少なくとも何本の辺が集まるか。(3) 10 次元で 512 個を選ぶときはどうか。

解説を見る

(1) $n = 4$ で、 $2^{3} + 1 = 9$ 個は半分より 1 つ多い。 $Δ \geq 4 = 2$ なので、2 本以上である。

(2) $2^{9} + 1 = 513$ も半分より 1 つ多い。 $Δ \geq 10 \approx 3.16$ で、本数は整数なので 4 本以上である。

(3) 1 の個数が偶数の頂点 512 個を選ぶと、どの 2 つも 2 けた以上違うので、辺は 0 本である。半分では何も言えない。

チョンらの 1988 年の選び方を使うと、(1) は 2 本、(2) は 4 本ちょうどで済む。ファンの不等式と合わせると、いちばん多く集まる本数の最小値は $⌈ n ⌉$ に決まる。

例題 3大学星の形の部分行列

3 次元の立方体で、1 の個数が偶数の 4 頂点 000・011・101・110 に、001 を足す。この 5 頂点のグラフを $H$ とする(図の 1 枚目の左)。ファンの行列 $A_{3}$ から $H$ の行と列を残した $A_{H}$ の固有値を求め、 $Δ (H) \geq λ_{1} (A_{H}) \geq 3$ を確かめよ。

解説を見る

$H$ の辺は、001 から 000・011・101 へ出る 3 本だけである。方向 $k$ の辺の符号は、 $k$ より上のけたにある 1 の個数の偶奇で決まる。001 の 1 は最も下のけたにしかないので、3 本とも $+ 1$ になる。頂点を 000・001・011・101・110 の順に並べる。

A_{H} = 0100010110010000100000000

110 の行と列はすべて 0 なので、固有値 0 を 1 つ出す。残りの 4 行 4 列は、001 を中心に 3 本の辺が出る星の形である。

det (λ I - A_{H}) = λ \cdot λ^{2} (λ^{2} - 3) = λ^{3} (λ^{2} - 3)

固有値は $\pm 3$ と $0$ (3 重)で、 $λ_{1} = 3$ である。001 に辺が 3 本集まるので $Δ (H) = 3$ である。

3 \geq 3 \geq 3

右の不等号は等号になる。ファンの論文も、どの $n$ でも偶数の頂点に 1 つ足すと $H$ は星の形になり、隣接行列の最大の固有値がちょうど $n$ になると指摘している。星の形では、辺の符号を変えても固有値は変わらない。

例題 4大学OR を立方体の塗り分けに直す

$g (x_{1}, x_{2}) = x_{1} \lor x_{2}$ (どちらかが 1 なら 1)について、証明の手順 3 の集合 $V_{1}$ を作れ。さらに $∣ V_{1} ∣ \neq = 2$ と、各頂点から同じ側へ出る辺の本数が感度に等しいことを確かめよ。入力は $x_{1} x_{2}$ の順に書く。

解説を見る

偶数の頂点は 00 と 11 で、 $g (00) = 0$ , $g (11) = 1$ なので、11 が $V_{1}$ に入る。奇数の頂点 01・10 では $g = 1$ なので、どちらも入らない。

V_{1} = {11}, V_{0} = {00, 01, 10}

$∣ V_{1} ∣ = 1 \neq = 2$ である。手順 4 の式で確かめる。最高次の係数は $c_{S} = g (11) - g (10) - g (01) + g (00) = - 1$ なので、次のようになる。

2^{1} + (- 1)^{2} \cdot (- 1) = 1

$V_{0}$ の中で、00 は 01・10 の 2 つとつながる。00 ではどちらのけたを反転しても値が 0 から 1 に変わるので、 $s (g, 00) = 2$ と一致する。01 は $V_{0}$ の中で 00 とだけつながり、01 では $x_{2}$ を反転して 00 にするときだけ値が変わるので、 $s (g, 01) = 1$ と一致する。11 は $V_{1}$ の中で辺をもたず、 $s (g, 11) = 0$ である。

例題 5大学等号になる関数

$f = (x_{1} \lor x_{2}) \land (x_{3} \lor x_{4})$ について、 $de g (f) = 4$ と $s (f) = 2$ を示し、 $s (f) = de g (f)$ を確かめよ。

解説を見る

$x_{1} \lor x_{2} = x_{1} + x_{2} - x_{1} x_{2}$ なので、次のように書ける。

f = (x_{1} + x_{2} - x_{1} x_{2}) (x_{3} + x_{4} - x_{3} x_{4})

展開すると $x_{1} x_{2} x_{3} x_{4}$ の係数は $(- 1) \cdot (- 1) = 1$ で、次数は 4 である。

感度を調べる。 $f (x) = 1$ の入力では、2 つの OR がともに 1 である。1 けたの反転で OR を 0 にできるのは、その OR の中の 1 がちょうど 1 つのときに、その 1 を反転する場合だけで、各 OR から多くとも 1 けたしかない。よって $s (f, x) \leq 2$ である。 $f (x) = 0$ の入力では、0 になっている OR がある。1 けたの反転で $f$ を 1 にできるのは、0 の OR がちょうど 1 つのときに、その OR の 2 けたのどちらかを反転する場合だけである。よって $s (f, x) \leq 2$ である。入力 1010 では $x_{1}$ と $x_{3}$ が感度をもつので、 $s (f) = 2$ になる。

s (f) = 2 = 4 = de g (f)

図示

半分と、半分より 1 つ多い

3 次元の立方体で 5 個の頂点を選ぶ 2 通り。左は 1 の個数が偶数の 4 頂点に 001 を足した選び方で、001 に太い辺が 3 本集まる。右は別の選び方で、辺は 4 本と左より多いが、どの頂点も 2 本まで。

ファンの行列 A₃ の符号を立方体の辺に書いたもの。実線が +1、破線が −1 で、どの面でも破線は 1 本か 3 本になる。

1 枚目の右は、いちばん多く集まる本数を 3 次元でいちばん小さくした選び方の 1 つで、 $⌈ 3 ⌉ = 2$ 本になっている。辺の総数は左の 3 本より多い。問うているのは辺の総数でなく、1 つの頂点に集まる本数である。2 枚目の符号は証明の手順 7 の漸化式で決まり、破線を実線に替えると、ふつうの立方体に戻る。

シミュレーション

頂点を 1 つずつ選ぶ

頂点をたたくと選ぶ・外すが切り替わり、選んだ頂点どうしの辺が太くなる。初めは 1 の個数が偶数の頂点が半分だけ選ばれていて太い辺は無いが、どれか 1 つを足すと、その頂点に $n$ 本の辺が一度に集まる。「集まる本数を最小に」を押すと、いちばん多く集まる本数がちょうど $⌈ n ⌉$ の選び方になる。下の欄には選んだ頂点だけを残したファンの行列の最大固有値 $λ_{1}$ が出て、半分より多く選ぶと $Δ \geq λ_{1} \geq n$ が並ぶ(「符号」を入れると $- 1$ の辺が破線になる)。

広がる学問

回路の理論から粒子の行列まで

数学ファンは論文の終わりで、対称性の高いほかのグラフでも、互いに隣り合わない頂点の最大数より 1 つ多く選んだときの最大次数を同じ方法で調べられるかを問うている。ダニエル・マシューズは $A_{n}$ を、 $e_{i}^{2} = 1$ と $e_{i} e_{j} = - e_{j} e_{i}$ を満たすクリフォード代数で $S = e_{1} + \dots + e_{n}$ を右から掛ける操作の行列として読み直した。 $S^{2} = n$ が、そのまま $A_{n}^{2} = n I$ になる。
情報科学 決定木の深さ、証明書複雑度(certificate complexity)、乱択や量子のクエリ計算量など、ブール関数の計算の手間を測る量の多くは、互いに多項式の関係にある。感度もこの仲間に入った。ファンの論文の時点で、ブロック感度と感度の差がいちばん大きい例はアンバイニスとスンの $b s (f) = \frac{2}{3} s (f)^{2} - \frac{1}{3} s (f)$ で、2 乗の程度にとどまり、上限の 4 乗との間は開いていた。
物理学 ディラック方程式の $γ$ 行列も、 $γ^{μ} γ^{ν} + γ^{ν} γ^{μ} = 2 η^{μν}$ を満たすクリフォード代数の行列である。2 乗が単位行列で、互いに反交換する行列を $n$ 個足すと、和の 2 乗は単位行列の $n$ 倍になる。ファンの $A_{n}$ も、方向ごとの辺の行列 $n$ 個の和として、この形に分けられる。
工学誤りの検出と故障への強さは、感度の言葉で言い直せる。検査ビットは感度が最大のパリティを、三重化は、そろった入力で感度が 0 になる多数決を使う(応用の章)。

参考文献

H. Huang, "Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture", Ann. of Math. 190 (2019), 949-955(arXiv:1907.00847、2019 年 7 月 1 日公開)
N. Nisan, M. Szegedy, "On the degree of Boolean functions as real polynomials", Proc. 24th ACM STOC (1992), 462-467; Comput. Complexity 4 (1994), 301-313.
C. Gotsman, N. Linial, "The equivalence of two problems on the cube", J. Combin. Theory Ser. A 61 (1992), 142-146; F. Chung, Z. Füredi, R. Graham, P. Seymour, "On induced subgraphs of the cube", J. Combin. Theory Ser. A 49 (1988), 180-187.
P. Hatami, R. Kulkarni, D. Pankratov, "Variations on the Sensitivity Conjecture", Theory of Computing Library, Graduate Surveys 4 (2011), 1-27.
N. Nisan, "CREW PRAMs and decision trees", Proc. 21st ACM STOC (1989), 327-335; D. Rubinstein, "Sensitivity vs. block sensitivity of Boolean functions", Combinatorica 15 (1995), 297-299; A. Tal, "Properties and applications of boolean function composition", Proc. ITCS (2013), 441-454.
E. Klarreich, "Decades-Old Computer Science Conjecture Solved in Two Pages", Quanta Magazine(2019 年 7 月 25 日); S. Aaronson, "Sensitivity Conjecture resolved", Shtetl-Optimized(2019 年 7 月 2 日)と、同じ記事への H. Huang のコメント #49(2019 年 7 月 3 日)
C. E. Shannon, "A symbolic analysis of relay and switching circuits", Trans. AIEE 57 (1938), 713-723; D. V. Mathews, "The sensitivity conjecture, induced subgraphs of cubes, and Clifford algebras", J. Eur. Math. Soc. 24 (2022), 4201-4205; Thinking Machines Corporation, Connection Machine Model CM-2 Technical Summary, HA87-4 (1987).

感度予想

5 個目の頂点

リレー回路から生まれた物差し

偶奇で塗り替え、符号で数える

4 行 4 列の行列を 2 乗する

1 ビットの誤りと 4096 個のチップ

感度と次数を手で数える

例題 1基本3 人の多数決

例題 2基本何本以上と言い切れるか

例題 3大学星の形の部分行列

例題 4大学OR を立方体の塗り分けに直す

例題 5大学等号になる関数

半分と、半分より 1 つ多い

頂点を 1 つずつ選ぶ

回路の理論から粒子の行列まで

参考文献

タグ

同じタグを持つ公式

姉妹サイト