STOC2日目以降の感想 (主にsunflower conjecture周り)

STOCが終わったので記憶が残っているうちに勢いに任せて前回に引き続きSTOC参加記(2日目〜5日目)を駆け足で書いていきます. 聴講して特に印象に残ったものについて記載しています. 勢いに任せて書いているのでテクニカルな内容はありません. ただし, sunflower lemmaの話については結構面白いと思ったので自分が理解した範囲で定義とかを書いていきます.

2日目

朝にLength-Constrained Expandersというワークショップに参加しました. 近年巷を騒がせているエクスパンダー分解や小直径分解という概念があるのですが, length-constrained expanderとはどちらの性質も同時に兼ね備えた分解を与える概念のようです. どちらの分解でも共通して頂点部分集合の分割$\mathcal{P}=(P_1,\dots,P_\ell)$であって, 各部分集合$P_i$のなる誘導部分グラフ$G[P_i]$が小直径または(Cheeger定数の意味で)エクスパンダーグラフとなるようなものを求めます. そして各$P_i$を縮約して得られるグラフに対して再帰的に分解を適用することによって, エクスパンダーからなる階層構造が得られます.

端的に言えば, 最悪時の問題例を分解によってエクスパンダー上で解くことに帰着するみたいなことをするようです. length-constrained expanderとは小直径分解とエクスパンダー分解両方の嬉しい性質を同時に達成するような分解らしいです.

2日目の午後は自分の発表を行いました. その次のセッションはランダムウォークなど確率解析のセッションでした. 時差ボケであまりちゃんと聞けなかったのですが最後の発表

On the Fourier Coefficients of High-Dimensional Random Geometric Graphs (Kiril Bangachev and Guy Bresler)

が印象的でした. この論文ではランダム幾何グラフとErdős--Rényiグラフの識別問題に対してよく知られる計算量と情報理論のギャップ (computational-statistical gap) について議論しており, low-degree polynomialと呼ばれるアルゴリズムのクラスでは両者のギャップが埋まる, という話でした.

3日目

午後は誤り訂正符号のセッションに行きました. 近年のTCSでは3クエリのlocally correctable codeのレートに関する効率性の下界を, これまで知られていたものより指数的に改善したという論文

An Exponential Lower Bound for Linear 3-Query Locally Correctable Codes (Pravesh K. Kothari, Peter Manohar)

の発表がありました. これはTCSの符号界隈で非常に大きな話題になりました.

その次のセッションは

Complexity-Theoretic Implications of Multicalibration, (Sílvia Casacuberta, Cynthia Dwork, Salil Vadhan)

でした. この論文はarXivに出た瞬間から個人的に注目していた論文です. additive combinatoricsにおけるdense model theorem (Green-Taoの定理の証明で重要な役割を果たした定理), Impagliazzoのhardcore補題, そしてFrieze-Kannanの正則化補題がどれも同じような構成的証明を与えていることに着目して共通の一般化を与えたという論文があるのですが, この論文はそれをmulticalibrationの観点でさらに一般化したというものです. この論文もquanta magazineの記事で紹介されています.

4日目

Applications of Turán-type problems in Theoretical Computer Scienceというワークショップに参加しました. Turánの定理とは完全グラフ$K_r$を部分グラフとして含まないグラフのうち最も辺数が多いものは, 等分割された完全$(r-1)$部グラフであるという主張です. 例えば三角形を含まないグラフの中で最もデンスなのは完全二部グラフです.

この問題は次のような自然な設定で登場します:

$n$個の電池があり, そのうち$r$個のみが充電されていて他は全て充電が空なのですが, どれが充電されていてどれが空か分からないとします. 手元には懐中電灯があり, 充電されている電池を2個入れると光ります. $n$個の中から二つの電池を入れて試すという試行を何回か行って懐中電灯を光らせたいとき, 最も試行回数を少なくするにはどうすればよいか?

グラフの言葉に翻訳すると以下になります: $n$個の頂点があってサイズ$r$の独立点集合を含まないグラフのうち最も辺数が少ないものは何か? グラフを一つ固定したとき, 各辺は懐中電灯の一回の試行に対応します. このグラフがもしもサイズ$r$の独立点集合$I$を持つならば, この頂点部分集合$I$が「充電された電池」であったときにこの試行で懐中電灯を光らせることができません. この解となるグラフの補グラフをとるとTuránの定理の設定になります.

Turán-typeな問題とは, 固定されたグラフ$H$を含まないグラフの中で最も密なものは何かという極値グラフ理論の問題です. 例えば奇数長の閉路は完全二部グラフを考えれば辺数$\Omega(n^2)$を達成しますが, 四角形を含まない任意の$n$頂点グラフは辺数が$O(n^{1.5})$になります (こちらの記事で証明しています). 応用として, ワークショップではErdősの内周予想やそれの最近の進展について取り上げられていました. 特に興味深かったのは$H=C_8$のときは未解決であるということでした. つまり, 長さ$8$の閉路を含まない$n$頂点グラフのうち最大辺数を$\mathrm{ex}(n;C_8)$とすると現在知られている最善のバウンドが

\[
\Omega(n^{6/5}) \le \mathrm{ex}(n;C_8) \le O(n^{5/4})
\]
となっており, このギャップを埋めるのはこの分野の中心的な未解決問題らしいです.

5日目

前日に引き続きTuranのワークショップに参加しました. とあるpseudorandomnessを満たす部分集合族を使ってsunflower lemmaの改善を与えた論文の話がありました. 集合$S_1,\dots,S_r \subseteq [n]$は, 全ての$i\neq j$に対して$S_i \cap S_j = S_1 \cap \dots \cap S_r$を満たすとき, $r$-ひまわりと呼びます. 

$[n]$上の集合族$\mathcal{S}=\{S_1,\dots,S_m\}$は, ある$S_{i_1},\dots,S_{i_r}\in\mathcal{S}$が$r$-ひまわりをなすとき, $r$-ひまわりを含むといいます. $r$-ひまわりを含まない部分集合族$\mathcal{S}$であって最も多くの集合を持つものはどのようなものになるでしょうか?

定理 (Erdős-Rado, '60)

集合族$\mathcal{S}=\{S_1,\dots,S_m\}$が$|S_i|\le w$を満たすとする. もし$|\mathcal{S}| > w! \cdot (r-1)^w$を満たすならば, $\mathcal{S}$は必ず$r$-ひまわりを含む.

この$m$のバウンド$w!\cdot (r-1)^w$を漸近的に改善できるのではないか? というのがひまわり予想です.

予想 (Erdős-Rado, '60).

集合族$\mathcal{S}=\{S_1,\dots,S_m\}$が$|S_i|\le w$を満たすとする. 各$r \ge 3$に対してある定数$C>0$が存在して, $|\mathcal{S}|>C^w$を満たすならば, 集合族$\mathcal{S}$は必ず$r$-ひまわりを含む.

Alweiss, Lovett, Wu, and Zhang (STOC20) はErdős-Radoの定理のバウンドを改善し以下の定理を証明しました:

定理 (Alweiss, et al. (2021)).

集合族$\mathcal{S}=\{S_1,\dots,S_m\}$が$|S_i|\le w$を満たすとする.  各$r \ge 3$に対してある定数$C>0$が存在して, $|\mathcal{S}|>(Cr^3 \log w \log\log w)^w$を満たすならば, 集合族$\mathcal{S}$は必ず$r$-ひまわりを含む.

ワークショップではこの定理の証明の雰囲気が紹介されました. まず, 集合族$\mathcal{S}$の擬似ランダム性を以下で定義します:

定義.

$[n]$上の部分集合族$\mathcal{S}=\{S_1,\dots,S_m\}$が$|S_i|\le w$を満たすとする. この集合族$\mathcal{S}$は, 任意の$T\subseteq[n]$に対して
\begin{align*}
\Pr_{S \sim \mathcal{S}} [ S \supseteq T ] \le \kappa^{|T|}
\end{align*}
を満たすとき, $\kappa$-spreadという.

部分集合族$\mathcal{S}=\{S_1,\dots,S_m\}$および$T\subseteq[n]$に対し, $T$のリンク$\mathcal{S}_T$とは, 部分集合族であって,
\begin{align*}
\mathcal{S}_T = \{S\setminus T \colon T \subseteq S\in\mathcal{S} \}
\end{align*}
によって定まるものです. リンクの言葉を使うと, $\mathcal{S}$が$\kappa$-spreadであるというのは, 任意の$T$のリンク$\mathcal{S}_T$が
\begin{align*}
|\mathcal{S}_T| \ge \kappa^{-|T|}\cdot |\mathcal{S}|
\end{align*}
を満たすことを意味します ($\mathcal{S}_T$の要素数は$T$を含む$\mathcal{S}$に属す部分集合の個数に等しいから).

重要な観察として, もしもリンク$\mathcal{S}_T$が$r$-ひまわり$\{S'_1,\dots,S'_r\}$を含むとしましょう. すると, $S'_1\cup T, \dots, S'_r \cup T$は$\mathcal{S}$における$r$-ひまわりになっているはずです. すなわち, リンクをとった後にひまわりがあるならば元の集合族に復元することができます.

適切な$\kappa$を選びます. もしも今持っている集合族$\mathcal{S}$が$\kappa$-spreadでないとするならば, 定義よりある$T$が存在して$|\mathcal{S}_T| > \kappa^{|T|}\cdot |\mathcal{S}|$となります. このリンク$\mathcal{S}_T$に対してひまわりの存在性を言えば, $\mathcal{S}$がひまわりを持つことが示せます. これを再帰的に繰り返していくと, $\kappa$-spreadingな集合族に対して議論すれば良いことになります. Alweissらの貢献は$\kappa$-spreadingな集合族に対してはdisjointな部分集合$S_{i_1},\dots,S_{i_r}$がとってこれることを示したこと(らしい)です. disjointな部分集合族はひまわりをなすので, これで定理の主張が証明できたことになります.

確率論的手法の計算論的な複雑性 (大雑把なサーベイ)

組合せ論や計算量理論ではしばし, 良い性質を持った離散構造の存在性が議論されます. 例えば

• 疎な正則エクスパンダーグラフ
• girthと彩色数が無限に大きくなるグラフ
• ランダム抽出器 (randomness extractor)
• 困難な真理値表 (hard truthtable)
• rigid matrix
• universal transversal sequence
• 大きい素数
• discrepancyの小さな部分彩色
• quasi-random graph
• Lovász local lemma
• 多変数多項式の根

といった離散構造はそれ自体が興味の対象となるだけではなく非常に幅広い応用をもち, 擬似ランダム生成器, 良い性質を持つ誤り訂正符号, 計算量下界の証明, 脱乱択の証明, 近似アルゴリズムの構成, アルゴリズムの近似率の限界(PCP定理)などに用いられます.

しかしながらこれらの存在性の証明の多くはしばし確率論的手法や鳩の巣原理などに基づいた非構成的な手法もしくは非効率的な構成に基づく証明になっています. 実際の応用では(特に擬似ランダムネスの文脈では)しばし効率的(計算量が小さい)かつ決定的(ランダムネスを使わない)な構成が求められます. これを確率論的手法の脱乱択化と呼ぶことにします. 

確率論的手法の脱乱択化は組合せ論と計算量理論が密接に関連しているとても面白いトピックですので, ここでは非常に大雑把にいくつかのトピックを紹介していきます. なお, この辺りの擬似ランダムネスに関するトピックはVadhanの本に詳しいです.

疎なエクスパンダーグラフ (ラマヌジャングラフ)

頂点数$n$の$d$-正則グラフ$G$を考えます (ただし$n\geq 2, d\geq 3$). 隣接行列$A$の固有値を大きい順に並べて$d=\lambda_1\geq \lambda_2 \geq \dots \geq \lambda_n$とします. すると, 

\[
\lambda_2 \geq 2\sqrt{d-1} - \frac{2\sqrt{d-1}-1}{\lfloor \mathrm{diam}(G)/2\rfloor}
\]

が成り立つことが知られています(Alon-Boppanaの定理). ここで$\mathrm{diam}(G)$はグラフ$G$の直径で, Moore bound (または幅優先探索に基づく議論)により, $\mathrm{diam}(G)=\Omega(\log_{d-1} n)$が成り立ちます. 従って上記のバウンドにより, $d\geq 3$を固定し$n\to\infty$の漸近を考えると$\lambda_2 \geq 2\sqrt{d-1} - O(1/\log n)$となります.

では, このバウンドは(漸近的に)タイトなのでしょうか? 実はこの問いはランダム正則グラフを考えることで簡単に肯定的に解けます. $n$頂点$d$正則グラフ全体の集合から一様ランダムに選んだグラフを$G_{n,d}$と書くと, Friedman(2003)によると, $n\to\infty$の漸近的を考えると, 確率$1-n^{-0.1}$で$G_{n,d}$は

\[
\lambda_2 \leq 2\sqrt{d-1} + O\left(\left(\frac{\log\log n}{\log n}\right)^2\right)
\]

を満たすことが知られています. なので, 無限に多くの$n$について上記を満たす$n$頂点$d$正則グラフがとれるため, $n\to \infty$の漸近においてAlon-Boppanaの定理のバウンドはほぼタイトであることがわかります. ちなみにFriedman(2003)の定理の別証明を与えたという論文も知られています.

しかしながらこの証明は非構成的であるという点で応用向きではありません. スペクトルグラフ理論では, $\lambda_2 \leq 2\sqrt{d-1}$を満たすグラフをラマヌジャングラフと呼びます. ある$d\geq 3$に対して$d$-正則ラマヌジャングラフの列$(G_i)_{i=1,2,\dots}$であって, $G_i$の頂点数が$i\to\infty$で発散するようなものが陽に構成できるか, という問題を考えます. この問題はLubotzky, Phillips, Sarnak (1988)によって解決され, その後も様々な進展を見ています.

• Lubotzky, Phillips, Sarnak (1988)は$p\equiv 1 \bmod 4$を満たす全ての素数$p$に対して$(p+1)$-正則ラマヌジャングラフの列を代数的に構成する方法を与えました. この構成はいわゆるLPSラマヌジャンなどと呼ばれています.
• Morgenstern (1994)はLPSラマヌジャンを$p$がprime powerの場合に拡張しました.
• 全ての$d\geq 3$に対して$d$正則ラマヌジャングラフは存在するのでしょうか?Friedmanの定理によるとランダム正則グラフは$\lambda_2 \leq 2\sqrt{d-1}+o(1)$を満たすことが知られていますが, 厳密にはラマヌジャングラフであるということを意味しません. このように, $\lambda_2\leq 2\sqrt{d-1}+o(1)$を満たすグラフをnear-Ramanujan graphといいます.
• Marcus, Spielman, Srivastava (2015)は上の問いを解決し, 任意の$d\geq 3$に対して$d$正則二部ラマヌジャン(multi)グラフの無限列の存在性を証明しました. 彼らの証明はinterlacing polynomial methodと呼ばれる手法に基づいており, LPSラマヌジャンなどの代数的なアプローチとは根本的に異なっています.
• すぐ後にCohen(2016)はMarcus, Spielman, Srivastavaの証明を構成的に修正し, $n$頂点ラマヌジャングラフを$\mathrm{poly}(n)$時間で構成するアルゴリズムを与えました.

ランダムネス抽出器

平たく言うとランダムネス抽出器(または単に抽出器)とは, ランダムっぽい文字列を受け取ってランダムな文字列を出力する乱択アルゴリズムです. 入力で与えられる文字列の「ランダムっぽさ」はmin-entropy(以下で定義している)によって測り, 出力文字列のランダムネスは一様ランダムな文字列との統計距離(total variation distance)によって測ります. 一般にdata processing inequalityより, どのような決定的なアルゴリズムを考えても分布のエントロピーを増大させることはできないため, ランダム抽出器は乱択アルゴリズムとしています.

定義1 (min-entropy).

確率変数$X$のmin-entropy $H_\infty(X)$を以下で定める:
\begin{align*}
H_\infty (X) = \min_{x\in\mathsf{supp}(X)}\log_2\frac{1}{\Pr[X=x]}.
\end{align*}

通常のShannon entropyは情報量の期待値によって定義されますが, min-entropyでは情報量の最小値を考えます. すなわちmin-entropyの方がworst-caseの情報量を考えていることになります. 二つの確率変数$X,Y$の統計距離を$d_\mathrm{TV}(X,Y)$で表します.

定義2 (ランダムネス抽出器)

以下を満たす関数$\mathrm{Ext}\colon \{0,1\}^m\times\{0,1\}^d\to\{0,1\}^n$を$(k,\epsilon)$-抽出器と呼ぶ: 任意の$H_{\infty}(X)\geq k$を満たす$\{0,1\}^m$上の分布$X$と$\{0,1\}^d$上の一様分布$U_d$に対し, $d_{\mathrm{TV}}\left( \mathrm{Ext}(X,U_d) , U_n \right) \leq \epsilon$.

すなわち, 抽出器とは, $m$ビットのランダムっぽい文字列$X$と$d$ビットの一様ランダムな文字列$U_d$を受け取り, $n$ビットのランダムな文字列を返す関数のことです. 一般に$m,d$は小さい方がよく, $n$は大きい方が良いです. 入力$X$をしばし弱ランダムソースと呼びます.

ランダムな関数を考えると高確率でランダムネス抽出器になっていることが簡単に示せます. すなわち, 各$\mathrm{Ext}(x,r)$の値を$\{0,1\}^n$上の一様ランダムにとってきたとき, $\mathrm{Ext}(\cdot,\cdot)$が抽出器になっている確率は適切なパラメータの下で$1-o(1)$になることが示せます.

ランダムネス抽出器は以下のように二部グラフによって表現することによって組合せ論的な解釈を与えることができ, そこに組合せ論のテクニックが介入する余地があります.

左側の各頂点は弱ランダムソース$X$の入力に対応しており, 右側の各頂点は$\{0,1\}^n$の元に対応します. 頂点$X$からは$2^d$本の辺が出ており, 各辺には$\{0,1\}^d$の元でラベル付けされています. 頂点$X$からラベル$u\in\{0,1\}^d$の辺を辿った先にある右側の頂点が$\mathrm{Ext}(X,u)$になるようにグラフを構成します.

このように二部グラフを構成すると, 抽出器とは以下の性質を持つ二部グラフ$G=(L,R,E)$であると解釈できます:

左側の頂点集合$L$上のmin-entropy$\ge k$であるような任意の分布に従って頂点$X$を選び, そこから$1$ステップだけランダムウォークを行って得られる右側の頂点を$Y\in R$とする. このとき, $Y$は$R$上一様分布に(統計距離の意味で)近い.

特に, エクスパンダーグラフを考えるとある条件下では抽出器になることが知られています. 抽出器についてのサーベイは, 古い論文ですがNisan(1996)に詳しいです.

エクスパンダーグラフなどの組合わせ論的な道具を使った構成のほかにも, 平均時計算量の道具を使って抽出器を構成するという手法も知られています. Trevisan (2001)は非常に賢いアイデアによって, 多くの擬似ランダム生成器の構成が実は抽出器の構成とみなせるということが示しました. 擬似ランダム生成器(pseudorandom generator; PRG)とは短いランダム文字列を受け取って長いランダム文字列を出力するアルゴリズムです. ただし一般に任意のアルゴリズムはエントロピーを増大しないので, PRGの出力は擬似ランダムであるということが求められます. 詳細は以前の記事をご覧ください. 

例えばNisan-Wigderson generator $G^f_{\mathrm{NW}}\colon \{0,1\}^d\to\{0,1\}^n$は, 計算が非常に困難なBoolean関数$f\colon\{0,1\}^\ell\to\{0,1\}$を使って$d$ビットのランダム文字列$U$(いわゆる乱数シード)を$n$ビットのランダム文字列に変換しています. Trevisan (2001)の抽出器では, 弱ランダムシード$x\in\{0,1\}^m$をまず誤り訂正符号で$2^\ell$ビットの文字列に復号化し, この文字列を真理値表として持つ関数をNisan-Wigderson generatorの構成に用いることによって, 抽出器を構成しています.

解析の大雑把な概要:

もしもTrevisan's extractorの出力値が一様ランダム文字列$U_n$から統計的に離れているならば, Nisan-Wigderson generatorのreconstructionの議論により関数$\mathrm{ECC}(x)\colon\{0,1\}^\ell\to\{0,1\}$からハミング距離$1/2-\epsilon$以下の文字列は短い記述を持つ. さらに$\mathrm{ECC}(x)$に対するリスト復号のアルゴリズムを用いれば, 最終的に弱ランダムシード$x$は短い記述を持つ. これはmin-entropyの仮定に反する.

Rigid Matrix

グラフの剛性とは違う文脈で行列のrigidityと呼ばれる概念があります. 直感的には, $M$がrigidであるというのは, $M$の成分をたくさん書き換えなければ低ランクにできない, ということを意味します. 有限体上の行列$M \in \mathbb{F}_q^{n\times n}$のランクを$\mathrm{rank}(M)$と書き, 二つの行列のハミング距離(異なる成分の個数)を$d_{\mathrm{ham}}(\cdot,\cdot)$で定義します. 

定義3 (matrix rigidity)

行列$M\in\mathbb{F}_q^{n\times n}$と自然数$r\leq n$に対し, $R_M(r)$を
\begin{align*}
R_M(r) := \min\{|S|\colon \mathrm{rank}(A+S)\leq r\}
\end{align*}
で定める. ここで, $|S|$は行列$S\in\mathbb{F}_q^{n\times n}$の非ゼロ成分の個数である.

$(n-r)\times (n-r)$首小行列を考えれば任意の行列$M$に対し$R_M(r)\leq (n-r)^2$が簡単に分かります.

各成分を$\mathbb{F}_q$から一様ランダムに選んで得られるランダム行列$M$に対し高確率で$R_M(r)\leq (n-r)^2/\log n$であることが示せます. 実際, ランク$r$以下の行列の個数とハミング距離$\leq s$のボールのサイズを考える数え上げによる議論で示せます.

Rigid matrixの概念はValiant(1977)によって, 線形変換を計算する算術回路のサイズ下界を得るという文脈で導入されました. 大雑把にいうと, Valiant(1977)はrigidな行列に基づく線形変換は超線形サイズの算術回路を要することを証明しており, ランダム行列は高確率でrigidであることを踏まえると, ランダムな線形変換の算術回路複雑性は超線形であることを意味します. この辺りのサーベイについてはLokam(2009)をご覧ください.

線形変換の回路下界自体も重要なトピックで, 例えば高速フーリエ変換は実用的にも重要な線形変換の一つなのでその計算の下界がわかればアルゴリズムの最適性も議論できることになります.

行列のrigidityに関しては次の重要な予想が重要な未解決問題として知られています.

予想 (Valiant, 1977)

ある体$\mathbb{F}_q$, 定数$\delta,\epsilon>0$およびサイズが発散していく陽に構成できる行列の列$(M_n)_{n=1,2,\dots}$が存在して, 十分大きな任意$n\in\mathbb{N}$に対して$R_{M_n}(\epsilon n) \geq n^{1+\delta}$を満たすようにできるか?

現在は$R_M(r)=\Omega\left(\frac{n^2}{r}\log\frac{n}{r}\right)$という下界が知られています(Friedman(1993), Shokrollahi, Spielman, Stemann (1997)).

近年はrigid matrixを計算量の道具を使って(NPオラクルを使って)構成するという手法が開発されました. Alman and Chen (2019)はNPオラクルを用いてrigid matrixを決定的に構成する手法を与えました. この解析は後にrectanglar PCPというアイデアを用いてsimplifyされました (Bhangale, Harsha, Paradise, Tal (2020)). 以下ではrectanglar PCPについてものすごくざっくり説明します.

非決定性機械に対する時間階層定理より, $\mathsf{NTIME}(2^n)\setminus \mathsf{NTIME}(2^n/n)$に属する判定問題$L$が存在します. さらに$\mathsf{NTIME}(2^n)$に対してPCP定理から PCP $\pi$とPCP検証者$V^{\pi}(\cdot)$が得られます. rencangular PCPとはその名の通り, 行列として表現できるPCP $\pi$のことです. ただしPCP検証者はランダムネスを使って行$i$と列$j$を選び, $\pi[i][j]$を見ます. これを定数回繰り返し, 見た証明ビットの内容においじて受理/拒否を決定します. Bhangaleら(2020)はNTIMEで解ける問題に対してある種の性質を満たすrectangular PCPが存在するということを示しています.

PCP定理から, 入力$x$上で元の問題$L$を得くためにはPCP検証者$V^{\pi}(x)$の受理確率を十分な精度で近似できれば良いです. もしrectanglular PCP $\pi$がrigidでないならば, ある低いランク行列$L$にハミング距離の意味で非常に近いはずです. そこで, nondeterministicに$L$の分解$L=R^\top R$をguessします. 実はこの情報を使ってPCP検証者の受理確率を決定的に十分な精度で近似することができます(!!). 実際には受理確率をある行列内に含まれる$1$の個数で表現し, $\pi$の低ランク分解を用いるとその行列もまた低ランク分解できることを示し, 最後に低ランク行列内に含まれる1の個数は高速に数え上げられるという結果(Chan and Williams, 2016)を使い, 最終的に$L$を$\mathsf{NTIME}(2^n/n)$で解けることを主張します. ところがこれは時間階層定理に矛盾するので, rectangular PCP $\pi$はrigidであることが結論づけられます.

その他の話題 (クラスPPAD)

確率論的手法以外にも非構成的な存在性の証明手法はあります. 例えばゲーム理論ではナッシュ均衡の存在性はブラウアーの不動点定理でその存在性が保証されるものの実際にそれを構成しているわけではありません. このような問題を扱うため, 計算量理論ではPPADと呼ばれる計算量クラスが考えられています. ナッシュ均衡の計算やブラウアーの不動点定理における不動点の計算はPPAD完全である, というある種の困難性の結果が知られています (Daskalakis, Goldberg, Papadimitriou, 2009).

まとめ

確率論的手法は興味深い離散構造の存在性を証明できる非常に強力なツールである一方, その離散構造をどのように得るかについては明示的な情報を与えてくれません. それではそれをどのように構成するかに関しては組合せ論や計算量理論で広く研究されており, 驚くほど広い(理論的な)応用を持っています.

discrepancy: ハムサンドイッチ定理の離散化 (確率論的手法)

本記事ではdiscrepancyと呼ばれる組合せ論(特に確率論的手法の文脈)でよく知られる概念について紹介します. この概念はハムサンドイッチ定理と呼ばれる定理を離散化したような概念とみなすことができます. discrepancyはその定義自体はとても簡単である一方で奥深い結果が多く知られており, 理論計算機科学においてはビンパッキング問題に対する近似アルゴリズムの設計にも応用されています. 後の章になっていくほどテクニカルになっていきます.

1. ハムサンドイッチ定理

ハムサンドイッチ定理とは, 直感的に説明すると「3次元空間内に配置された三つの物体は、ある平面でうまくスラッシュすることによって全ての物体の体積を半分にできる」ということ主張する定理です. 私は詳しくないのですが, wikipediaによると, より一般に$d$次元空間にある$d$個の「物体」（有限測度を仮定するが必ずしも連結である必要はない）はある$d-1$次元超平面によってそれぞれの測度を半分ずつにできる、という主張をハムサンドイッチの定理と呼ぶらしいです.

名前の由来はハムとそれを挟む2枚のパンからなる三つの物体は, 一回のナイフカットによって平等に二分割できるということから来るようです. 特に二次元($d=2$)の場合はパンケーキの定理とも呼ばれるようで, 限りなく薄い2枚のパンケーキを等分割するようにカットできるということを意味します (下図)

要するにハムサンドイッチ定理とは二つの物体を組み合わせたものはうまくナイフを入れることで等分できる, ということを主張しています. この定理を数学的に厳密に述べるのは難しいのですが, ここではそれを離散化した設定を考えます.

2. discrepancy

ハイパーグラフ$H=(V,E)$を考える (各$e\in E$は$e\subseteq V$を満たす). 関数$\chi\colon V\to\{-1,1\}$と集合$S\subseteq V$に対して$\chi(S)=\sum_{i\in V}\chi(i)$とし, $\chi$のdiscrepancyを
\begin{align*}
\mathrm{disc}_{\chi}(H) = \max_{e\in E}|\chi(e)|
\end{align*}
で定義します. 直感的には$\chi$は頂点集合$V$を二つに分けるナイフカットを意味しており, そのdiscrepancyは$\chi$がどれだけ二等分に近いかを表す指標とみなすことができます. この設定下ではdiscrepancyが最小となる$\chi$が最も公平な分割と思うことができます. すなわち, 以下で定義される最小discrepancyを考えてみましょう:
\[
\mathrm{disc}(H):=\min_{\chi\colon V\to\{-1,1\}}\mathrm{disc}_{\chi}(H).
\]

以後, 関数$\chi\colon V\to\{-1,1\}$を彩色と呼びます.

例えば$G=(V,E)$が通常の意味でのグラフだとすると, $\mathrm{disc}(G)=0$であることと$G$が二部グラフが同値になります.

図: グラフ$G=(V,E)$が二部グラフならば, それぞれの部集合を$\chi^{-1}(1),\chi^{-1}(-1)$とすれば, discrepancyを$0$にできる.

3. 行列を用いたdiscrepancyの表現

ハイパーグラフ$H=(V,E)$の接続行列$A_H\in\{0,1\}^{E\times V}$を,
\[
A_H(e,v) = \begin{cases}
1 & \text{ if }v\in e,\\
0 & \text{otherwise}
\end{cases}
\]
で定義します. 関数$\chi\colon V\to\{-1,1\}$をベクトル$\chi\in\{-1,1\}^V$と同一視すると, 行列$A\chi \in \mathbb{Z}^{E}$は, その第$e$成分が$\sum_{v\in V}\chi(v)$になるので,
\[
\mathrm{disc}(H) = \min_{\chi\in\{-1,1\}^V}\left\| A_H\chi \right\|_{\infty}
\]
と表せます. ここで$\|\cdot\|_{\infty}$は$\ell^{\infty}$-ノルムで, 各成分の最大絶対値を表します.　いくつかの論文ではこの形でdiscrepancyを議論していくこともあります. 

より一般に$A\in\{0,1\}^{m\times n}$に対して$\mathrm{disc}(A)$を
\[
\mathrm{disc}(A) = \min_{\chi\in\{-1,1\}^V}\left\| A\chi \right\|_{\infty}
\]
と定義することができ, さらにこの定義は一般の実行列$A\in\mathbb{R}^{m\times n}$に対して考えるもできます. これを行列$A$のdiscrepancyと呼びます.

蛇足になりますが, 関連する概念としてlinear discrepancyと呼ばれるものが知られています. この値は$m\times n$実行列$A$に対して定義でき,
\[
\mathrm{lindisc}(H) = \max_{w\in[-1,1]^n}\min_{x\in \{-1,1\}^n} \left\| A(x-w) \right\|_{\infty}
\]
で定義されます. この概念は元々は連続変数$w\in[-1,1]^n$を持つ線形計画問題を整数変数$x\in\{1,1\}^n$に丸めた際のギャップを考えるという文脈で定義されています.

4. discrepancyの計算量

考えるハイパーグラフ$H=(V,E)$の頂点数を$n$, ハイパー辺の個数を$m$で表します.

[Charikar, Newman, Nikolov, SODA11]によって, $m=O(n)$を満たすとき, 以下の二つの入力を区別することがNP困難であることが示されています:

• $\mathrm{disc}(H)=0$
• $\mathrm{disc}(H)=\Omega(\sqrt{n})$

例えば$m=n$を満たす任意のハイパーグラフ$H$に対して$\mathrm{disc}(H)\leq 6\sqrt{n}$であることが知られている (後述するがこの結果はSpencer's six standard deviations theoremと呼ばれる重要な結果) ので, 上記の困難性は定数倍を除いてタイトです.

5. ランダム彩色による上界

彩色$\chi\colon V \to \{-1,1\}$を一様ランダムにとってきたときのdiscrepancyを考えてみましょう. すなわち, 各$v\in V$に対して$\chi(v)$を$\pm 1$から一様ランダムに選びます. このとき, Hoeffding boundとunion boundを組み合わせることによって簡単に以下を示すことができます.

命題1 (ランダム彩色のdiscrepancy)

ハイパーグラフ$H=(V,E)$に対し, $n=|V|,m=|E|$とする. 一様ランダムに選ばれた彩色$\chi\colon V \to \{-1,1\}$を考えると, 以下が成り立つ:
\begin{align*}
\Pr\left[\mathrm{disc}_\chi(H) \leq \sqrt{2n\log(3m)} \right] \geq \frac{1}{3}.
\end{align*}

特に, $\mathrm{disc}(H)\leq \sqrt{2n\log(3m)}$である.

命題1の証明のために以下のHoeffding boundを用います:

補題1 (Hoeffding bound)

$X_1,\dots,X_\ell$を$\pm 1$に値をとる独立一様ランダムな確率変数とし, $X=\sum_{i\in[\ell]} X_i$とする. このとき, 任意の$t\geq 0$に対して

\begin{align*}
\Pr\left[ |X| \geq t \right] \leq 2\exp\left(-\frac{t^2}{2\ell}\right).
\end{align*}

[命題1の証明].

固定した辺$e\in E$に対して, 補題1より
\begin{align*}
\Pr\left[\chi(e) > \sqrt{2n\log(3m)} \right] \leq \Pr\left[\chi(e) > \sqrt{2|e|\log(3m)}\right] \leq \frac{2}{3m}.
\end{align*}
従って, $e\in E$に関するunion boundにより
\begin{align*}
\Pr\left[\mathrm{disc}_{\chi}(H) > \sqrt{2n\log(3m)}\right] \leq \Pr\left[\exists e\in E,\,\chi(e)>\sqrt{2n\log(3m)}\right] \leq \frac{2}{3}.
\end{align*}

すなわち, ランダムに選ばれた$\chi$のdiscrepancyは確率$1/3$で$\mathrm{disc}_\chi(H)\leq \sqrt{2n\log(3m)}$を満たす. (証明終)

証明から分かるように, $\log(3m)$の定数$3$は任意の定数$c>1$に対し$\log(cm)$に置き換えることが可能です.

6. Spencer's six standard deviation theorem

$m=O(n)$のとき, 5章では確率論的手法を使って$\mathrm{disc}(H)=O(\sqrt{n\log n})$が得られますが, 実はさらに改善して$\mathrm{disc}(H)=O(\sqrt{n})$を示すことができます[Spencer, 1985].

定理1 [Spencer's six standard deviation theorem]

$|V|=|E|$を満たす任意のハイパーグラフ$H=(V,E)$は$\mathrm{disc}(H)\leq 6\sqrt{|V|}$を満たす.

この結果は, その係数からSpencer's six standard deviation theoremと呼ばれます. 実はこの証明は$\chi$の存在性を鳩の巣原理から導出しており構成的ではないのですが, 後に構成論的な証明が与えられ[Bansal, 2010], 現在ではより簡単な証明も知られています[Lovett, Meka, 2015]. ここではhidden constantについてはoptimizeせず, 単に存在性($\mathrm{disc}(H)=O(\sqrt{n})$)を証明します.

証明では部分彩色 (partial coloring) という概念が鍵になります. 部分彩色とは関数$\chi\colon V\to\{-1,0,1\}$です. 部分彩色に対しても$\chi(e) = \sum_{v\in e} \chi(v)$とし, $\chi$のdiscrepancyを
\[
\mathrm{disc}_{\chi}(H) = \max_{e\in E}\left| \chi(e) \right|
\]
で定義することができます.

明らかに, 全ての頂点に$0$を割り当てる部分彩色を考えるとdiscrepancyが$0$となり最小値をとります. 従って, 部分彩色$\chi$であって

• 多くの頂点(少なくとも$0.01|V|$個以上の頂点) に$\pm 1$の値を割り当てる, かつ
• $\mathrm{disc}_{\chi}(H)$が小さい

ような部分彩色が望ましい部分彩色であるといえます. 以下の補題はそのような部分彩色の存在性を保証します.

補題2 (部分彩色補題)

ある定数$C_0$が存在して, $m\leq \frac{n}{10}$を満たす任意のハイパーグラフ$H=(V,E)$に対し, 以下の二つを同時に満たすある部分彩色$\chi\colon V\to \{-1,0,1\}$が存在する:

• $\chi(v)\in \{-1,1\}$を満たす頂点$v$が少なくとも$\frac{n}{10}$個ある.
• $\mathrm{disc}_\chi(H)\leq C_0\sqrt{n}$

補題2の証明が最もテクニカルなパートになるので次の章で紹介するとして, ここでは補題2$\Rightarrow$定理1を示します.

まずは証明のアウトラインを述べます. 元々は$m=n$という仮定でしたが, ダミー頂点を追加すれば相対的に$|E|\leq \frac{|V|}{10}$になるようにできるので, 与えられたハイパーグラフは$m=\frac{n}{10}$を満たすと仮定して良いです (ダミー頂点追加後の彩色に対するdiscrepancyは$O(\sqrt{O(n)})=O(\sqrt{n})$になるのでdiscrepancyのバウンドも大丈夫). これに対して補題2を適用して得られる部分彩色に対し, $0$が割り当てられた頂点部分集合からなる誘導部分ハイパーグラフに対して再帰に彩色を得て先ほどの部分彩色とマージするという方針になります. 一回の反復で塗られていない頂点の個数は$0.9$倍になるので, 全体のdiscrepancyは高々$\sum_{t=0}^\infty C_0 \sqrt{0.9^t n}=O(\sqrt{n})$になるという議論です.

[補題2$\Rightarrow$定理1]. 

以下の手順に従ってハイパーグラフの列$(H_t)_{t=0,1,\dots}$と各$H_t$上の部分彩色$\chi_t$を定義します:

1. $H_0 = (V_0,E_0) = H$とする.
2. For $t=1,2,\dots,$ do:
1. 部分彩色$\chi_t$を, $H_{t-1}$に対する補題2で存在性が保証される部分彩色とする.
2. $V_t=\{v\in V_{t-1}\colon \chi_t(v)= 0\}$, $E_t = \{e\cap V_t\colon e\in E_{t-1}$とし, $H_t=(V_t,E_t)$で定める.
3. $E_t=\emptyset$になったら終了する.

補題2の条件より, $|V_t| \leq 0.9|V_{t-1}|$ なので, 十分大きな$T=O(\log n)$に対して$E_T=\emptyset$となるため, 上の手順は有限ステップで終了します. このとき, $\chi_1,\dots,\chi_T$に対して彩色$\chi$を, $\chi(v) = \chi_i(v)$で定めます. ここで$i\in[T]$は$\chi_i(v)\neq 0$を満たす唯一の$i$とします. 

上で定義した$\chi$のdiscrepancyを評価します. 各辺$e\in E$に対して
\begin{align*}
|\chi(e)| \leq \left|\sum_{v\in e}\chi(v)\right| \leq \sum_{t=1}^T \left| \sum_{e\in E_{t-1}\setminus E_t } \chi(e) \right| \leq \sum_{t=1}^T C_0\sqrt{0.9^t n} = O(\sqrt{n})
\end{align*}

を得ます.

7. 部分彩色補題の証明(スケッチ)

6章で紹介した補題2(部分彩色補題)を証明します. この証明はその鳩の巣原理からその存在性が保証されるため構成的ではありません. 部分彩色補題 (ひいては定理1) を満たす彩色$\chi$の構成については長年未解決だったのですが, Bansal (2010) によるブレイクスルーにより解決され, 現在ではLovett and Meka (2015) による(ランダムネスを用いる)簡単な構成法も知られています. 厳密な証明をしようとすると瑣末な部分のケアで煩雑になってしまい大変なので, できる限り本質を捉えつつ厳密性を捨てて, 分かった気になれる証明のスケッチを紹介します.

定義1 (エントロピー)

離散集合上に値をとる確率変数$X$に対し, そのエントロピー$\mathrm{H}(X)$を
\begin{align*}
\mathrm{H}(X) = \mathbb{E}_{x\sim X}\left[\log\frac{1}{\Pr[X=x]}\right] = \sum_{x\in \mathsf{supp}(X)} \Pr[X=x]\log\frac{1}{\Pr[X=x]}
\end{align*}
で定義します. ここで対数の底はlogとし, $\mathsf{supp}(X)$は$X$の台(support)と呼ばれる集合で, $\mathsf{supp}(X)=\{x\colon \Pr[X=x]>0\}$で定義されます.

なお, 連続値をとり密度関数が存在するような確率変数に対しても$\Pr[X=x]$を密度関数$f(x)$に置き換えて微分エントロピーという値が定義されます. すなわち, 密度関数$f$を持つ実数値をとる確率変数$X$の微分エントロピー$\mathrm{H}(X)$は

\begin{align*}
\mathrm{H}(X)=\int_\mathcal{\mathsf{supp}(X)} f(x) \log\frac{1}{f(x)}\mathrm{d}x
\end{align*}
で定義されます. エントロピーに関しては上記の定義と以下の性質のみを使います.

補題3 (エントロピーの劣加法性).

ランダムなベクトル$X=(X_1,\dots,X_n)$に対し, そのエントロピー$\mathrm{H}(X)$は
\[\mathrm{H}(X) \leq \sum_{i\in[n]}\mathrm{H}(X_i)\]を満たす.

さて, 部分彩色補題の証明に戻ります. ランダムな彩色$\chi\colon V \to \{-1,1\}$を考え, パラメータ$w>0$と頂点部分集合$S$に対し, 確率変数
\[
Z_S = \left\lfloor \frac{\chi(S)}{w\sqrt{|S|}}\right\rfloor
\]
のエントロピー$\mathrm{H}(Z_S)$を考えます. 実際にはもう少し複雑な式を使って評価するのですが, ここでは以下の主張を認めて証明を進めていきます.

主張1.

パラメータ$w$を適切にとり, 部分集合$S$の要素数が十分大きいとき, $\mathrm{H}(Z_S)\leq 0.9$とできる.

なお, この主張は本当に成り立つかは分かりません(えっ...). 実際の証明ではもう少し複雑な式を使ってエントロピーを評価します. ここではその証明のアイデアを簡潔に説明するためにあえて「成り立つか分からない主張」を仮定します. ただ, この主張には一応の理由づけはできるので, 以下ではその妥当性を説明します (実際の研究の場面ではこのようなことは私はよくやります).

[主張1の妥当性の説明]

• 定義よりエントロピーはスケーリングで不変なので, $\mathrm{H}(Z_S)=\mathrm{H}(w\cdot Z_S) \approx \mathrm{H}(\chi(S)/\sqrt{|S|})$ (本当は切り下げの有無でのエントロピーの誤差の評価が必要).
  
• $\chi(S)$は平均$0$, 分散$1$の独立な確率変数$(\chi(v))_{v\in S}$の和なので, $|S|$が十分大きければ中心極限定理より$\chi(S)/\sqrt{|S|}$は漸近的に標準正規分布$\mathcal{N}(0,1)$で近似できる.
• 従って, $\mathrm{H}(\chi(S)/\sqrt{|S|}) \approx \mathrm{H}(\mathcal{N}(0,1)) = (1+\log(2\pi))/2 \approx 1.419$. なお, 正規分布の微分エントロピーについての事実を使っている(例えばこの記事参照).  本当はBerry--Esseenの不等式などを使ってエントロピーの誤差評価が必要.
• これらをまとめると, $\mathrm{H}(Z_S)\approx 1.419$なので, パラメータ$w$を適切にとり, 集合サイズ$|S|$が十分大きいならば, 近似精度を$0.001$未満にできて$\mathrm{H}(Z_S)\leq 1.42$にできる.

ハイパーグラフ$H$に対し, ランダムベクトル$Z=Z(\chi)=(Z_e)_{e\in E}$を考えます. ここで, 全ての辺$e$の要素数は十分大きいと仮定します (そうでない場合はサイズが小さいのでdiscrepancyに寄与しないため無視できる). するとエントロピーの劣加法性(補題3)と主張1より
\begin{align*}
\mathrm{H}(Z) \leq \sum_{e\in E}\mathrm{H}(Z_e) \leq 1.42m \leq 0.2n
\end{align*}
を得ます. エントロピーの定義より, averaging argumentにより, あるベクトル$z^*\in\mathbb{Z}^E$が存在して
\begin{align*}
\log\frac{1}{\Pr[Z=z^*]} \leq 0.2n
\end{align*}
となります. これを整理すると$\Pr[Z=z^*] \geq \mathrm{e}^{0.2n} > 2^{0.2n}$を得ます. ここでの確率は一様ランダムな彩色を考えていたので, 少なくとも$2^{0.8n}$個の$\chi\in \{-1,1\}^V$が存在して$Z(\chi)=z^*$を満たすことになります. そのような$\chi$の集合を$B\subseteq\{-1,1\}^V$とします. ここで, $|B|\geq 2^{0.8n}$より, ある二つのベクトル$\chi_1,\chi_2\in B$が存在して, $\|\chi_1-\chi_2\|_1 \geq 0.1n$となります (後述). そのような$\chi_1,\chi_2$に対して$\chi = \frac{1}{2}(\chi_1 - \chi_2)$と定義します. するとこの$\chi$は部分彩色補題の要件を満たしています:

• $\chi_1,\chi_2$の選び方より, $\chi(v)=0\iff \chi_1(v)=\chi_2(v)$となる$v\in V$は高々$0.9n$個あります.
• $\chi_1,\chi_2\in B$より, $Z(\chi_1)=Z(\chi_2)$です. すなわち, 任意の$e\in E$に対して
  \[
  \left\lfloor\frac{\chi_1(e)}{w\sqrt{|e|}} \right\rfloor = \left\lfloor \frac{\chi_2(e)}{w\sqrt{|e|}} \right\rfloor
  \]
  が成り立つので, $|\chi(e)| = |\chi_1(e) - \chi_2(e)| \leq w\sqrt{|e|} \leq w\sqrt{n}$です. これは$\mathrm{disc}_\chi(H)\leq w\sqrt{n}$を意味します.

以上より, 部分彩色補題(補題3)の証明が完了し, 同時に定理1の証明も完了しました. (証明終)

以上の証明では次の事実を用いています:

主張2.

集合$B\subseteq \{-1,1\}^n$が$|B|\geq 2^{0.8n}$を満たすならば, ある二つのベクトル$x,y\in B$が存在して$\|x - y \|_1\geq 0.1n$となる.

証明(概要). 一般に, 任意のベクトル$x\in \{-1,1\}^n$に対し$x$からハミング距離$\alpha n$以内にある点の個数は高々$\sum_{i=0}^{\alpha n} \binom{n}{i} \leq 2^{\mathrm{H}(\alpha)n}$を満たします (ここで$\mathrm{H}(\alpha):=\alpha\log_2\frac{1}{\alpha} + (1-\alpha)\log_2\frac{1}{1-\alpha}$はbinary entropy function). $\alpha=0.1$を代入すると, この個数は$2^{\mathrm{H}(0.1)n}< 2^{0.469n}<|B|$なので, 主張を満たす2点をとることができます. (証明終)

Further Reading

• 驚くべきことにスタンフォード大学では過去にdiscrepancyについての講義(おそらく集中講義?)があり, いくつかの講義ノートが公開されています.
• The Probabilistic Method (Alon and Spencer)の12章ではランダムな$\chi$の解析とsix-deviation theoremとBeck-Fiala theoremとHadamard行列に基づく下界の紹介がされています.
• ビンパッキング問題の近似アルゴリズムに対する応用については "A Logarithmic Additive Integrality Gap for Bin Packing" (Hoberg and Rothvoss, SODA2017) 参照. なお, 箇条書き一つ目のリンクにあるLecture 10のノートには少し弱い近似精度を持つビンパッキングの近似アルゴリズムについての解説があります.

combinatorial designの構成

集合族$\mathcal{S}$であって任意の相異なる二つの元の共通部分が小さいものを平均計算量理論の文脈でcombinatorial designと呼ぶことがあり, 擬似乱数生成器の構成などにおいて非常に重要な役割を果たします. 具体的には, 台集合$E$上の集合族$\mathcal{S}$であって以下を満たすものを($E$上の)$(d,n)$-designと呼びます.

• 各$S\in\mathcal{S}$に対して$|S|=n$.
• 各$S\neq T\in \mathcal{S}$に対して$|S\cap T|\leq d$.

例1. グリッド

台集合$E=[m]^2$上の集合$S_i=\{(x,y)\in E\colon x=i\text{ or }y=i\}$を考えると $\mathcal{S}=\{S_i\}_{i\in[m]}$は$(2,2m-1)$-designになります.

本記事では$(d,n)$-designの応用先には特に触れず, [NW94]で与えられた以下の$(d,n)$-designを紹介します. Nisan--Wigderson Generatorを知っていても具体的なcombinatorial designを知らない人向けの備忘録です.

定理 (Lemma 2.4 of [NW94]).

各素べき$n$と$d\in\mathbb{N}$に対して, $|E|=n^2$かつ$|\mathcal{S}|=n^{d+1}$を満たす台集合$E$上の$(d,n)$-designが存在する.

証明.

有限体$\mathbb{F}_n$を考え, $E=\mathbb{F}_n^2$とします. $\mathcal{P}_{\leq d}$を$\mathbb{F}_n$上の次数高々$d$の多項式全体の集合とし, 各$p\in\mathcal{P}_{\leq d}$に対して$S_p=\{(x,p(x))\colon x\in \mathbb{F}_n\}$とし, $\mathcal{S}=\{S_p\}_{p\in\mathcal{P}_{\leq d}}$とします. 明らかに$|\mathcal{S}|=|\mathcal{P}_{\leq d}|=n^{d+1}$です.

上で与えた$\mathcal{S}$が確かに$(d,n)$-designになっていることを確認します. まず, 各$S\in\mathcal{S}$は$n$個の点の集合なので確かに$|S|=n$を満たします. 次に$|S_p\cap S_q|>d$を満たす相異なる二つの多項式$p,q\in\mathcal{P}_{\leq d}$が存在すると仮定します. このとき, $p(x)=q(x)$を満たす$x\in\mathbb{F}_n$が$d+1$個以上存在することになりますが, このとき多項式$p-q$は次数高々$d$で$d+1$個の点で$0$になるので, 恒等的に$0$となり, $p\neq q$と矛盾します.

(証明終)

参考文献

[NW94] N. Nisan and A. Wigderson, Hardness vs Randomness, JCCS, 1994.

Bogolyubov-Ruzsaの補題 (加法的組合せ論)

加法的組合せ論(additive combinatorics)で知られるBogolyubov--Ruzsaの補題と呼ばれる結果を紹介します. この補題は様々なバリエーションが知られていますが, ここでは以下のタイプの結果を証明します. 

加法的組合せ論は極値グラフ理論(ラムゼー理論)と密接に関連しており, 密な部分集合が持つ構造的特徴を解析します. 例えばRothの定理は$\mathbb{N}$上の任意の密な部分集合$S\subseteq\mathbb{N}$は長さ3の非自明な等差数列 (つまり交差が非ゼロ) を含むことを主張します. ここでは$S$が「密な部分集合」, 「長さ3の等差数列を含む」が「構造的特徴」に対応します. なお, Rothの定理よりも強い主張として, 任意の密な自然数の部分集合は無限に長い等差数列を含むという事実が知られています (Szemerédiの定理).

$\mathbb{F}_q$を素体として$n\in\mathbb{N}$に対して線形空間$\mathbb{F}_q^n$を考えます. $D\subseteq\mathbb{F}_q^n$が密である時にそれはどのような性質を持つかを考えます. 幾つか記号を導入します.

• $D+D = \{a+a'\colon a,a'\in D\}$.
• $-D = \{-a\colon a\in D\}$.
• $k\in\mathbb{N}$に対して$kD=\{a_1+\dots+a_k\colon a_1,\dots,a_k\in D\}$.
• $D-D = D+(-D) = \{a-a'\colon a,a'\in D\}$.

例えば$D$が部分空間ならば$D+D,D-D$などは全て$D$と一致します. イメージとしては$D$と$D-D$などの"ギャップ"を考えることによって$D$の"部分空間っぽさ"を捉えることができます. Bogolyubov--Ruzsaの補題は, $D$が密ならば$2D-2D$は大きな線形部分空間を含むことを主張します.

定理1 (Bogolyubov--Ruzsaの補題).

集合$D\subseteq \mathbb{F}_q^n$が$|D|\geq \delta |\mathbb{F}_q^n|$を満たすならば, $\dim V\geq n-\delta^{-2}$を満たす線形部分空間$V$であって

任意の$x\in V$に対してある$a,b,c,d\in D$が存在して$x=a+b-c-d$

を満たすものが存在する (即ち$V\subseteq 2D-2D$).

本記事ではより強いことを主張する以下の結果を証明します.

定理2 (確率的Bogolyubov--Ruzsaの補題).

集合$D\subseteq \mathbb{F}_q^n$が$|D|\geq \delta |\mathbb{F}_q^n|$を満たすならば, $\dim V\geq n-\delta^{-2}$を満たす線形部分空間$V$であって,

任意の$x\in V$に対して$\Pr_{a,b,c,d\sim \mathbb{F}_q^n}[a,b,c,d\in D|a+b-c-d=x]\geq \delta^5$

を満たすものが存在する.

証明.

フーリエ解析の記法を用いる (定義の記事参照). $D\subseteq \mathbb{F}_q^n$に対し, $\mathbb{1}_D$を指示関数 ($x\in D$なら$\mathbb{1}_D(x)=1$, そうでなければ$\mathbb{1}_D(x)=0$) とする. この関数のフーリエ変換$\widehat{\mathbb{1}}_D$を考え, パラメータ$\epsilon>0$に対して

$$R_\epsilon = \{v\in\mathbb{F}_q^n\colon |\widehat{\mathbb{1}}_D(v)|\geq\epsilon\}$$

とする. Parsevalの等式より

$$\delta = \|\mathbb{1}_D\|^2 = \sum_{v\in\mathbb{F}_q^n}|\widehat{\mathbb{1}}_D(v)|^2 \geq \epsilon^2|R_\epsilon|$$

なので$|R_\epsilon|\leq\delta\epsilon^{-2}$である. $V$を$R$の張る部分空間の直交補空間, すなわち

$$V=\{v\in \mathbb{F}_q^n\colon \forall r\in R_{\epsilon},\langle v,r\rangle=0\}$$

とする. 明らかに$\dim V \geq n-|R_\epsilon|\geq n-\delta\epsilon^{-2}$である.

よって, $\epsilon=\delta^{1.5}$のときに上で定義された$V$が所望の性質を満たすことを言えば良い. 関数$f\colon\mathbb{F}_q^n\to\mathbb{C}$を

$$f=\mathbb{1}_D\ast \mathbb{1}_D \ast \mathbb{1}_{-D}\ast \mathbb{1}_{-D}$$

とする. 畳み込みの定義より

$$f(x) = \Pr_{a,b,c,d\sim\mathbb{F}_q^n}[a,b\in D,c,d\in -D|a+b+c+d=x]$$

であるので, 任意の$x\in V$に対して$|f(x)|\geq \delta^5$を示せばよい.

$f(x)$をフーリエ級数展開する. 畳み込みの性質から$\widehat{f}(v)=\widehat{\mathbb{1}}_D(v)^2\widehat{\mathbb{1}}_{-D}(v)^2$だが,

$$\widehat{\mathbb{1}}_{-D}(v) = \mathbf{E}_{x\sim\mathbb{F}_q^n}\left[\mathbb{1}_{-D}(x) \overline{\omega^{\langle v,x\rangle}}\right] = \mathbf{E}_{x\sim\mathbb{F}_q^n}\left[\mathbb{1}_{D}(x) \omega^{-\langle v,-x\rangle}\right] = \overline{\widehat{\mathbb{1}}_{D}(v)}$$

より, $\widehat{f}(v)=|\widehat{\mathbb{1}}_D|^4$となるので$f(x)=\sum_{v\in\mathbb{F}_q^n}|\widehat{\mathbb{1}}_D(v)|^4\chi_v(x)$である. この和を

1. $v=0$
2. $v\in R_\epsilon$
3. それ以外 ($v\not\in R_\epsilon\cup\{0\}$)

に分けて考える.

• $v=0$の時は$\chi_0\equiv 1$より$\widehat{\mathbb{1}}_D(0)\chi_0(x)=\langle \mathbb{1}_D,1\rangle = \delta$である.
• $v\in R_\epsilon$の時は, $V$の定義より$\langle x,v\rangle = 0$なので$\widehat{\mathbb{1}}_D(v)\chi_v(x)=\widehat{\mathbb{1}}_D(v)$である.

それ以外の場合は, $v\not\in R_\epsilon$より$|\widehat{\mathbb{1}}_D|\leq \epsilon$より

$$\sum_{v\not\in R_\epsilon\cup \{0\}} |\widehat{\mathbb{1}}_D(v)|^4 \leq \epsilon^2\sum_{v\not\in R_\epsilon\cup \{0\}} |\widehat{\mathbb{1}}_D(v)|^2 \leq \epsilon^2\left(\delta -  |\widehat{\mathbb{1}}_D(0)|^2\right)=\epsilon^2(\delta-\delta^2).$$

以上の三つのケース組み合わせると, $\epsilon=\delta^{1.5}$のとき,

$$|f(x)|\geq \delta + \sum_{v\in R_\epsilon}|\widehat{\mathbb{1}}_D(v)|^4 - \epsilon^2(\delta-\delta^2) \geq \delta^5$$

となり主張を得る. (証明終).