STOC26参加記

STOC2026に参加して4日目にこれを書いている。開催場所はソルトレイキシティで、日本との時差は15時間ある。基本的には夜中の2時に目が覚めて、15時くらいからめちゃくちゃ眠くなる生活が続いている。今回はありがたいことに2本通って2回発表する機会を得たのだが、最後の二日間の夕方のセッションに割り当てられてしまった。一つ目の発表を終えた時点でこれを書いているのだが、発表直前は眠過ぎて寝坊しそうですごい不安で逆に眠れなかった。とりあえず印象的だった内容やその場での自分の思考を思い出しながらメモしているのだが、色々やるべきことを放棄して書いている。ただ、これを書くときに2年前のSTOC参加記を読みおこしているのだが自分で読み直すと意外と楽しいのでこういう参加記はなんとかしてでも残しておくと、未来の自分が楽しめるので頑張ろう（去年のSTOCはプラハですごく楽しかったのに参加記を失念していた）。

最初はワークショップ Algorithmic Frontiers of Graph and Hypergraph Problems via Global Queriesに参加した。まだ時差ボケじゃないので比較的元気な状態で聞けた。グラフ全体が入力として与えられるのではなく、グラフがカットオラクルで与えられる カットクエリモデル と呼ばれる設定で最小カットとかを計算するという話だった。カットオラクルとは、頂点部分集合 $S\subseteq V$ をクエリとして投げると $|E(S,\overline{S})|$ を教えてくれるオラクルで、出来るだけ少ないクエリで最小カットを解きたい。二人目の発表者Puttermanのトークでは、この問題設定の先駆的な結果 Rubinstein, Schramm, Weignberg (ITCS18) の解説をしていた。どうやらカットオラクルを使うと辺を一様ランダムにサンプリングすることができるらしく、これを使ってKargerをする感じらしい。サンプリング辞退は単純な再帰アルゴリズムでできる。ただ、質問したところ固定した頂点に対して接続する辺を一様ランダムにサンプリングできるらしい（？）ので、そもそも次数に比例する確率で頂点を選んでからその接続辺を一様ランダムに選べばもっと簡単にランダムサンプリングできるじゃんとは思った。適当な重みをつけた分布で辺をサンプリングすればカット疎化はできるらしいけどスペクトル疎化は重要な未解決問題らしい。質問したところランダムウォークはサンプリングできるからランダム全域木を何本かサンプリングしてunionをとればspectralを保存できるんじゃなかったっけと思って Kyng, Song, FOCS18 を確認したけど、leverage scoreで重みつけしなきゃらしく、この値の計算が難しそうなのでダメかと思った。あと、カットオラクルは隣接行列 $A$ に対して、二次形式オラクル $(u,v)\mapsto u^\top A v$ にオラクルアクセスできる下でグラフの情報を学習する感じなんだなと思ってたら次の発表者  Mukhopadhyay がまさにそんな感じのことを言ってて確かにそうみなすよなぁと思った。この辺から疲れてきて三つ目の発表はあまり集中できなかった。

ワークショップの終了後はbest paper sessionだった。特に記憶に残っているのは Chen, Chen, Cui, Pires, Stockwell だった。これはboolean function $f\colon\{0,1\}^n\to\{0,1\}$が単調増加関数 ($x\le y \text{ (entry-wise)} \Rightarrow f(x)\le f(y)$) に対する性質検査の結果で、nonadaptive testerではクエリ数の上界と下界は $\widetilde{\Theta}(\sqrt{n})$ であったのだが、nonadaptiveでも $\widetilde{\Omega}(\sqrt{n})$ 必要という下界を示した論文だった。証明はめちゃくちゃ難しそうだが、"monotone"から非常に遠い "anti dictator 関数 $d_i\colon x\mapsto \overline{x_i}$" が重要な役割を果たすらしい。入力全体を適切な手続きに従ってランダムに分割していき、各分割でランダムな $i\sim[n]$ を選び, $d_i$ を貼り合わせて得られる関数を考えるらしい。印象的なbest student paperの発表者はJack Stadeで、art gallaly problemがNPに属することを示す結果だった。平面上の多角形が与えられて、その全てを見渡すために配置すべき警備委員の人数を最小化する問題なのだが、警備員の座標が無理数になる問題例もあるため、NPに属するかはとても非自明な問題である。ところが、座標が無理数であっても適当な形の無理数になるらしく、それをうまく使って証明していた。全くわからなかったがある種の線形不等式系にNP witnessがあるみたいなことを言っててビックリした記憶がある。Stadeといえば最近の論文でETR (existential theory of real; クラスNPの実数版) に対するPCP定理を証明していた。基本的にはDinurのgap amplificationに則るのだが、実数上の誤り訂正符号でPCPP (assignment tester) を構成してアルファベット削減するというところがうまくいかなくて、それをmidpoint codeというBoolean cube上のHadamard codeでなんとかしているのが印象的だった。他にも, Junqiao (Randy) Lin による MIPco=coRE という論文の発表も面白かった。両辺のcoの意味はそれぞれ違っていて、かの有名なMIP*=REではmultiprover同士の相関にある種の制約を仮定するという問題設定を考えているのだが、MIPcoではそれをもっと緩くした (coはcommuteの意) ものを考えるらしい。coREではcoNPと同じ意味のco (complement) なのだが、タイトルの両辺の"co"が違う意味を持つのは面白い。ていうかfull versionが160ページ以上あって、しかも単著ってどういうこと...?

他には Amireddy, Behera, Srinivasan, Sudan, Willumsgaard によるPCPの新しい証明の話が面白かった。PCPのALMSSの証明やDinurの証明は「クエリ数を下げるがアルファベットが増える」「アルファベットを下げる」という二つの種類のPCP (またはPCPP) をめちゃくちゃ巧妙に合成 (composition) して証明するのだが、この論文の手法を使うと一度の合成でPCPを示せるらしい。基本的にはSATの変数や節のindexを二進数で表現したときに得られる $O(\log n)$-variable な関数をmultilinear extensionしてsumcheckとかをすることになる。sumcheckプロトコルではBoolean cube上でのlow-degree polynomialの総和を検証するプロトコルだが、Boolean cubeという構造を少し一般化した空間でもsumcheckみたいなことができるらしい。すごい興味があるので時間があれば読みたい。

この次に聞いたMax Hopkinsによる Dikstein, Hopkins, ,Pitassi, Impagliazzoの発表もめちゃくちゃ面白かった。個人的にはこれがbest paperだと思ってたのだが、去年がHDXだったしそういうのもあったのだろうか。ただ、やはり内容はすごいし応用も広そう。発表後に何度かMaxと話していたのだが、彼はHDXの人という認識だったのだがaverage-case complexityについてもよく知っていて、知識の幅というか守備範囲がひろすぎて感嘆した。

二日目のワークショップも再びグラフのワークショップに参加した。一人目はRobert Krauthgamerで、本とかでしか知らないレジェンドなのだがめちゃくちゃイケおじだった。内容としては、カット疎化に関して、シュタイナー点を許す新しいsparsifierを考えるという内容で面白かった。確か今回のSTOCではその新しいsparsifierに関する下界の結果があったような気がする。二人目はSanjieev Kannaで、彼の最近のマトロイドのブレイクスルーの結果 (FOCS25) とその後の進展 (ICALP26) に関する講演だった。独立オラクルでマトロイドの基を「できるだけ」nonadaptiveに探す問題を考える。普通に要素を一つずつ貪欲に追加していくと全てのqueryがそれ以前のqueryの応答に依存してしまうので、これはめちゃくちゃ適応的である。もうちょっとちゃんと述べると、ラウンド制のオラクルモデルを考える。第一ラウンドではアルゴリズムはクエリ $q^{(1)}_1,q^{(1)}_2,\dots,q^{(1)}_{L_1}$ を作成し、オラクルに投げる。その応答をもとに第二ラウンドでクエリ $q^{(2)}_1,\dots,q^{(2)}_{L_2}$ を作成してオラクルに投げる。さらにその応答をもとに次のラウンドでクエリを作成して... というのを繰り返し、最終的にできるだけ少ないラウンドでマトロイドの基を探してね、という問題である。ただし、一度のラウンドでありうる全てのクエリを投げると必ず1ラウンドで終わるので、基本的には多項式個のクエリを投げて全体で多項式時間で終了するという条件を設ける。貪欲法だと、多項式時間ではあるが、台集合サイズ $n$ に対して $n$ラウンド (各ラウンドで一個ずつクエリを作る)になってしまう。Karp, Upfal, Wigderson, 1988 は、一般のマトロイドに対して $O(n^{1/2})$ラウンドの上界と、$\Omega(n^{1/3}/\log^{1/3} n)$ という情報理論的な下界を示していて、去年のFOCSでKhannaらは $\widetilde{O}(n^{7/15})$ ラウンドの上界を与え、最近の論文 ではとうとう上界が $\widetilde{O}(n^{1/3})$ というnearly-tightな上界を与えた話をしていた。

また、Hair, Sahai によるSVPのdeterministic NP-hardnessの話も面白かった。中身はまったくわからないけどPCPを使ってうまくガジェットを作るらしい。

あと、PKEのworkshopも参加した。最初のSahaiのトークは、基本的にcryptosystemで用いられる困難性の仮定には色々あるが、それを破ることに意義のあるような"useful"なhardnessに基づくPKEを構築しましょうね、みたいな話だった。次のHairのトークはplanted "graph" conjectureに基づくPKEの構築の話をしていた。この問題は大雑把に言えば、固定したexpander graphがランダム二部グラフに含まれるかを判定せよ、という感じの問題であった。

「入力」と「インスタンス」の使い分け

問題に対するアルゴリズムの計算量を議論する際に「入力」「インスタンス」という言葉が登場する。これらは、アルゴリズムが読み込む文字列という意味では、両者ともに同じ役割を果たすため、特に気にせず同じ意味で用いる人が多いと思う。しかし、実は両者は文脈によっては明確に区別されるべき概念である。

インスタンス（問題例）の概念は計算量理論の言い回しであり、問題に対して具体的な一例を意味する。例えば最短経路問題は問題であるが、具体的なグラフの一つ一つ（を表す文字列）は最短経路問題のインスタンスという。

一方で入力とはアルゴリズムが受け取る文字列である。例えばクラスNPの検証者は、判定問題$L$のインスタンス$x$および、それがYesインスタンスであることを支持する文字列$w$を証拠として受け取る。このとき、$x$と$w$を区切り文字「$,$」を一つ間に入れて連結させて得られる文字列
\[
x , w
\]
を入力と呼ぶ（もしくはチューリング機械において、インスタンスを記述する入力テープと証拠を記述する入力テープを別々に用意しておく設定を考えるならば、組$(x,w)$を入力と定義しても良い）。

また、乱択アルゴリズム（特にモンテカルロ法）の文脈においても同様である。モンテカルロ法とは、計算時間が有限であるものの、出力が誤りうる乱択アルゴリズムである。したがって乱択アルゴリズムを$A(x;r)$のように記述することがある。ここで$x$はインスタンスであり、$r$はランダムシードである。ここでは$;$という記号はインスタンス$x$とランダムシード$r$の役割が根本的に違うため、その区別を明確にするためだけに採用している。このような場合、$x,r$もしくは$(x,r)$がアルゴリズム$A$の入力であり、インスタンス$x$とは異なる文字列になる。

---

なお、余談であるが「乱択アルゴリズム」の計算モデルには二通りの定義がある。ほとんどの場合はどちらを採用しても構わないので、教科書を執筆するでもない限りは特に気にする必要はないのだが、文脈によって便利な方を採用する。

• 一つ目の定義は二つの遷移関数$\delta_0,\delta_1$を持つチューリング機械であり、便宜上ここでは乱択チューリング機械と呼ぶ。通常のチューリング機械は自身の繊維関数$\delta$を繰り返し適用して計算を進めていくのだが、乱択チューリング機械では各時刻において一様ランダムに$\delta_0,\delta_1$のいずれかを選び、それを適用していく。これは、計算の過程で逐次的にランダムネスを取得する計算モデルなので、オンライン型とも呼ぶ（cf. Goldreich本）。
• 二つ目の定義は、決定的チューリング機械であるが、乱択シード$r$を入力の一部として受け取るモデルである。

例えば「表が出るまでコイントスをし続ける」のように、運が悪いと無限に計算が終わらないような状況では前者の計算モデルで表現するのが適切である。一方で使用したランダムネスの大きさ（ランダムシードの長さ）を議論する場合は後者の定義を採用するのが適切である。例えば後者の議論はPCP定理で非常に重要である。

エントロピーを使ったXOR補題の証明

嬉しいことに今年STOCに2本の論文を通せたのですが、そのうち一本は、XOR補題（の自然な拡張）をエントロピーを使って証明して、それをaverage-case fine-grained complexityのある数え上げ問題に応用した論文でした。XOR補題は計算量理論では80年代からよく知られている結果で、すでにいくつもの証明方法が知られている（例えば[GNW]が有名）のですが、我々が与えたエントロピーに基づく証明の方が、証明の筋道が直感的にわかり易いのと、（計算量的）疑似エントロピーの良い導入になるので、教育的なのではないかと思っているので、ここで概説します。あくまでも雰囲気がつかめる程度の粒度の記事ですので、細かい詳細は私に直接問い合わせてください（または後日full versionを出すのでそれを参照）。なお、応用についてはここでは省きます。

統計的 vs. 計算量的

平均時計算量という計算量理論の一分野では、情報理論におけるエントロピーなどの概念を「計算量的に」修正したアナロジーを考えることによって、情報理論的な議論に基づいて計算量の結果を証明するということがよく行われます。例えば二つの確率変数$X,Y$の近さを測る指標としてしばし統計距離が使われますが、これは（その確率変数の台を$\Omega$として）

\[
d_{TV}(X,Y)=\max_{D\colon \Omega\to\{0,1\}} \left\{|\Pr[D(X)=1] - \Pr[D(Y)=1]|\right\}
\]
によって定義されます（本来は分布に対して定義されるが、ここでは利便性のため、その分布に従ってサンプリングされた確率変数に対して距離を考えることにする）。ここでは簡単のため$\Omega$は有限集合としています。このとき考える関数$D$を識別者と呼びます。気持ちとしては、識別者は

「与えられた値は$X$と$Y$どちらからサンプリングされたものですか？」

という問題を解こうと頑張っており、その精度の限界値が統計距離となります。すなわち、統計距離が小さいということは、任意の識別者にとって$X$と$Y$が識別できないということになるので、この性質を統計的な識別不可能性（または情報理論的な識別不可能性）と呼びます。

さて、統計距離の定義で考える識別者とは任意の関数を考えていますが、これを

限定的な計算能力を持つ識別者のクラス

に制限することによって新たな識別不可能性の概念を考えることができます。例えば「任意の多項式時間アルゴリズムにとって一様ランダムな文字列と識別できない」といった議論が展開できるわけですが、これを計算量的な識別不可能性と呼び、特に一様ランダムと計算的に識別不可能であるという性質を計算量的疑似ランダムネスと呼びます。

情報理論的には、データ処理不等式により、任意の決定的な関数$f\colon \{0,1\}^n\to\{0,1\}$に対して、分布 $(U_n, f(U_n))$ のエントロピー（ここで$U_n$は$n$ビットの一様ランダムな文字列）は元のランダムシードのエントロピーと一致して必ず$n$のままになる（つまり、決定的な作用を施してもエントロピーは増えない）のですが、計算量理論的な枠組みではある種の計算困難性を仮定すると（計算量理論的）エントロピーを増大できる、という驚くべき結果が知られています。

証明は以前の記事に譲るとして、もう少し深掘りすると、関数$f\colon\{0,1\}^n\to\{0,1\}$が強い平均時困難性を持つとは、任意の効率的な乱択アルゴリズム（注：厳密には非一様なアルゴリズムを考えている）$A$に対して
\[
\Pr_{x\sim U_n,A}[A(x)=f(x)] \le \frac{1}{2} + \varepsilon
\]
を満たすことを言います（$\varepsilon$は文脈依存だがとにかく小さい値。とりあえず$1/\mathrm{poly}(n)$だと思えばよい）。例えば$A$として、$0$ or $1$をランダムに出力するアルゴリズムを考えると正しく$A(x)=f(x)$になる確率はぴったり$1/2$になるわけですが、非自明な精度で$f(x)$を推定しようとすると、その計算能力はすごく沢山要する、というわけです。一方で、右辺が$1$に近い、すなわち
\[
\Pr_{x\sim U_n,A}[A(x)=f(x)] \le 1 - \delta
\]
を満たすとき、弱い平均時困難性を持つと言います。

さて、強い平均時困難性を持つ$f$に対して
\[
(U_n,f(U_n))
\]
という$n+1$ビットの文字列は計算量的疑似ランダムであることが知られており、その逆も成り立ちます。すなわち、関数の計算困難性を計算量的疑似ランダム性で特徴づけられます。例えばNisan-Wigderson生成器を使うと（ある計算量下界の仮定の下での）脱乱択化ができるといった応用があります。

XOR補題

YaoのXOR補題とは、一方向性関数の文脈でYao(1982)で提示された（のちにLevin(1985)で証明が与えられた）結果です。簡単にいうと、弱い平均時困難性を持つ関数 $f\colon \{0,1\}^n\to\{0,1\}$ に対して、別の関数$f^{\oplus k}\colon\{0,1\}^{kn}\to\{0,1\}$を

\[
f^{\oplus k}(x_1,\dots,x_k) = f(x_1) \oplus \dots \oplus f(x_k)
\]

と定義したとき、この関数は（十分大きな$k$に対して）強い平均時困難性を持つ、という結果です。ですので、弱い困難性を持つ関数の下でも、XORをとることでその困難性を増幅させることで、脱乱択といった応用にあてはめることができるようになります。

冒頭でも述べたように、XOR補題の証明は色々知られていて

• 直積定理＋Goldreich-Levin
• hardcore補題
• isolation lemma (Levinによる証明）

などが知られています。本記事で説明する別アプローチの証明は、ZhengのD論(2014)で証明された弱い平均時困難性の計算量的疑似平均最小エントロピー (pseudo average min-entropy)による特徴づけ(PAME theorem)を用います。

疑似（最小）エントロピーとXOR補題

関数 $f$ の強い平均時困難性は疑似ランダム性で特徴づけられると述べましたが、弱い困難性は最小エントロピーの言葉で特徴づけることができます。弱い困難性を持つ関数 $f\colon \{0,1\}^n\to\{0,1\}$ に対して

\[
f(U_n)
\]

という確率変数を考えます。この平均時困難性は、$U_n$が与えられても計算能力が制限された識別者にとっては$f(U_n)$の値が類推できない、すなわちランダムに見えることを保証します。もし$f$が弱い困難性を持つとき、ある程度の精度で類推できるものの、ある程度の確率で間違えます。これを、「$f(U_n)$はある程度のエントロピーを持つ」と解釈します。このエントロピーを疑似エントロピーと呼びます。

もう少しちゃんと述べると、関数 $f$ が疑似エントロピー $\theta$ を持つとは、ある確率変数の組 $(U_n,Z)$ が存在して、

• $(U_n, f(U_n))$ と $(U_n, Z)$ が計算量的に識別不可能
• 条件付き最小エントロピーが$H_{\mathrm{min}}(Z|U_n) \ge \theta$

を満たすことを言います。文脈によってShannonエントロピーを考えることも多いのですが、ここではminエントロピーを考えます（両者の差分については踏み込まないので、詳しくない読者はとりあえず「エントロピーがある」程度の認識で大丈夫です）。

もしも$Z$が一様ランダムなビットだったら疑似ランダム性を持つということになるのですが、この定性的な主張をエントロピーを使って定量的な主張にできます：

定理（Zheng (2014),  informal)

関数 $f\colon \{0,1\}^n\to\{0,1\}$ が弱い困難性を持つ $\iff$ $f$が疑似エントロピー $\log_2 \frac{1}{1-\delta}$ を持つ。

この定理の証明はZhengのD論に書いてあります（私は咀嚼でかなり苦労しました）。この結果は文脈としては[VZ]による、一方向性関数に基づく疑似ランダム生成器の構成の文脈で与えられた結果です（本当は彼らはKL困難性というちょっと異なる概念を考えているが、ほぼ同じ証明でZheng (2014)の結果が示せる）。

ひとまずこの特徴づけを用いると、XOR補題を以下のような流れで証明できます：

1. $f$が弱い困難性を持つので、特徴づけより疑似エントロピーを持つ。
2. $x_1,\dots,x_k \sim U_n$ を独立に選ぶと、$f(x_1),\dots,f(x_k)$はそれぞれ独立でしかも各は$\log_2 \frac{1}{1-\delta}$ の疑似エントロピーを持つ。
3. 情報理論的な議論（本当はフーリエ解析）によって、エントロピーを持つ独立な確率変数の和 $\bmod 2$ はエントロピーが増大する。
4. $k$が十分大きいときはエントロピーはほぼ最大値$1$になる。すなわち$f^{\oplus k}(x_1,\dots,x_k)$は疑似ランダムなので、$f^{\oplus k}$ は強い困難性を持つ。

XOR補題の拡張

XOR補題ではBoolean関数 $f\colon\{0,1\}^n\to\{0,1\}$を考えており、和をとることでBooleanであることを保証するために$\mathbb{F}_2$上での演算を考えていました。我々の論文ではこれを$\mathbb{F}_p$値をとる関数$f\colon\{0,1\}^n\to\mathbb{F}_p$に拡張しました（ただし$p$は素数）。

議論は上のステップ1から4のままです。実はZheng(2014)の結果は$f$がBooleanでなくても成り立つ結果であることを利用します。$p$が素数であるという条件はステップ3において本質で、合成数だと一般には成り立ちません（例えば$\bmod 4$だと、$\{0,2\}$上一様ランダムな確率変数をいくつ足してもエントロピーは変わらない）。

なお、これまで知られているXOR補題の証明はBoolean関数であることを利用しており、例えばhardcore補題ではboostingのために多数決をとるという操作がありますがここでBoolean関数であることを本質的に利用してます（実はZheng (2014)の結果はhardcore補題の拡張とみなすことができます）。Goldreich-Levinは$\mathbb{F}_2$上のHadamard符号のリスト復号アルゴリズムですが、これを$\mathbb{F}_p$に拡張したリスト復号アルゴリズム（[GRS])を用いると、少し異なる主張になってしまいます。

講義資料をCursor+Slidevで作成してみた

私はプログラミング応用という講義＋演習を持っている。昨年はNotionで講義資料を作成したのだが、私はいつもCursorというエディタを使って論文を書いたりしており、最近Slidevというものを知ったので試しにこれらを使って講義資料を準備してみることにした。

今日はプログラミング応用の講義でした. グラフの基本的な定義と全点対最短経路問題について扱いました.https://t.co/dpjbTSJ7ID pic.twitter.com/xMMv5Tek5g

— Nobutaka Shimizu (@knewknowl) October 28, 2025

その結果できたのがこれである。

例えば第６回の講義ではLPの導入として多面体を軽く紹介したが、こんな感じでインタラクティブに可視化できるのが非常に良いと思った。これはVue componentをAIに作ってもらった（なお私はVueを触ったことがない）。

Slidevだとトーク中に画面に書き込みができるので、iPadでスライドショーしても良いと思った。

行列積検算の乱択アルゴリズムと誤り訂正符号

行列積の検証で有名な乱択アルゴリズム (Freivaldsのアルゴリズム) のちょっとした変種が実はSchwartz-Zippelから正当性を直接示せて、とても教育的である、という話。あと、これを決定的にできるのか？について。

 

1. 行列積の検証とFreivaldsのアルゴリズム

Freivaldsの乱択アルゴリズムとは、与えられた三つの$n\times n$行列 $A,B,C$ に対して$AB=C$かどうかを$O(n^2)$時間で乱択を用いて判定する方法です (ただし$A,B,C$は体$K$上の行列で、体の演算に要する計算時間は省略)。具体的には以下のアルゴリズムを考えます:

アルゴリズム1.1

1. 一様ランダムなベクトル $r\sim \{0,1\}^n$ を選ぶ。

2. $ABr \ne Cr$ならば「$AB\ne C$」を出力して終了する。

3. ステップ1-2を何度も繰り返して終了しなかったら「$AB=C$」を出力して終了する。

明らかに$AB=C$を満たすとき、このアルゴリズムは確率1でステップ3で$AB=C$を出力します。一方で$AB\ne C$であったとしても、運が悪いと$AB=C$が出力されうることに注意してください。ところがこの悪い事象の発生確率は小さいことが証明できます:

定理1.2 (Freivalds)

入力が$AB\ne C$を満たす時に上記のステップ1-2を一度実行すると、少なくとも$1/2$の確率で「$AB\ne C$」が出力される。

すなわち、ステップ1-2を$T$回繰り返すと、出力結果が誤っている確率は高$々1/2^T$となります。正当性の証明は他の方の記事がありましたので、そちらを参照します。

そもそも$AB=C$かどうかの判定は、実際に$AB$を計算してそれを$C$と比較すれば良いのですが、行列積の計算が$O(n^2)$時間で行えるかどうかはこの分野の重大な未解決問題です。ところが単に行列積が正しいかどうかの検証は乱択を許すことによって簡単にできてしまうというのが面白いポイントです。このような「行列積を計算する」「行列積の検算を行う」の間にギャップがあるかどうか、つまり簡単に検証できる問題は簡単に解けるか否か?という問題はまさしくP対NP問題の「スケールダウン版」とも言えるでしょう。

2. ちょっとした変種

Freivaldsのアルゴリズムでは
\[ABr = Cr \]
をチェックしましたが、少し修正した以下のアルゴリズムを考えます。ここでは有限体$\mathbb{F}$上の行列を考えます。

アルゴリズム2.1

1. 独立一様ランダムに二つのベクトル $s,r\sim \mathbb{F}^n$ を選ぶ。

2. $r^\top ABs \ne r^\top Cs$ならば「$AB\ne C$」を出力して終了する。

3. ステップ1-2を何度も繰り返して終了しなかったら「$AB=C$」を出力して終了する。

Freivaldsのアルゴリズムとの違いは

1. ランダムベクトルの各成分が$\{0,1\}$ではなく$\mathbb{F}$上でランダムになってる
2. 行列ベクトル積ではなく、二次形式で比較している

という点です。体$\mathbb{F}$が$|\mathbb{F}|\ge 3$なら、その正当性が簡単に証明できます。

定理2.2

$|\mathbb{F}|\ge 3$とする。入力が$AB\ne C$を満たす時にアルゴリズム2.1のステップ1-2を一度実行すると、少なくとも$1/3$の確率で「$AB\ne C$」が出力される。

証明

関数 $F\colon \mathbb{F}^n\times\mathbb{F}^n \to \mathbb{F}$を
\[
F(r,s) = r^\top (AB-C) s\tag{1}
\]
と定義すると、これは$2n$個の変数からなる二次多項式となり、しかも$AB\ne C$であることからこれは非ゼロ多項式である。したがって、Schwartz-Zippelの補題から

\[
\Pr_{r,s\sim\mathbb{F}^n}[F(r,s) = 0] \le \frac{\deg F}{|\mathbb{F}|} \le \frac{2}{3}
\]

となり主張を得ます。

実際に論文に使うのであればアルゴリズム1.1のようなものを使えば良いのですが、個人的にはSchwartz-Zippelの応用としても面白いし証明も単純なのでこちらの方が教育的ではあると考えています。

3. ランダムネスの削減

アルゴリズム1.1や2.1は乱択アルゴリズムですが、決定的に（すなわちランダムネスを使わずに）行列積の（積計算より高速に）検算はできるのでしょうか？これは実は未解決で、最近も論文（例えば[Künnemann, ESA2018]）が出ているようなトピックです。

決定的にするのは難しそうなので、使用するランダムビットを削減する（randomness-efficient）という方針で考えてみましょう。アルゴリズム1.1や2.1はそれぞれ$n$ビットと$O(n\log_2|\mathbb{F}|)$ビットのランダムネスを使っています。これを$0$ビットにできれば脱乱択できたことになります。

ここでは$\mathbb{F}\ge 3n$であれば、簡単に$O(\log |\mathbb{F}|)$ビットに削減できることを示します。このような結果自体は90年代（[Kimbrel, Sinha, IPL1993]）には知られていました。具体的には以下のアルゴリズムを考えます。$\mathbb{F}$は十分大きいと思ってください。

アルゴリズム3.1

1. 体$\mathbb{F}$から一様ランダムに二つの要素 $a,b \sim \mathbb{F}$ を選び、

\begin{align*}
&r = \begin{pmatrix}1 \\ a \\ a^2 \\ \vdots \\ a^{n-1}\end{pmatrix}, \\
&s = \begin{pmatrix}1 \\ b \\ b^2 \\ \vdots \\ b^{n-1} \end{pmatrix}
\end{align*}
とする。

2. $r^\top ABs \ne Cs$ならば「$AB\ne C$」を出力して終了する。

3. ステップ1-2を何度も繰り返して終了しなかったら「$AB=C$」を出力して終了する。

最初の二つのアルゴリズムに比べて、ランダムベクトルの取り方を少し工夫しています。このアルゴリズムは
\[
2\log_2|\mathbb{F}|
\]
ビットのランダムネスを用いています。$\mathbb{F}\ge 3n$の場合には以下のように正当性が担保されます。

定理3.1

$|\mathbb{F}|\ge 3n$とする。入力が$AB\ne C$を満たす時にアルゴリズム3.1のステップ1-2を一度実行すると。少なくとも$1/3$の確率で「$AB\ne C$」が出力される。

証明

定理2.1の証明とほぼ同じです。関数$G\colon\mathbb{F}^2\to\mathbb{F}$を
\[
G(a,b) = (1,a,a^2,\dots,a^{n-1})(AB-C)\begin{pmatrix} 1 \\ b \\ b^2 \\ \vdots \\ b^{n-1} \end{pmatrix} \tag{2}
\]
 で定義します。仮定より$AB\ne C$なので、この関数は非ゼロな二変数多項式であり、その次数は$2n-2\le 2n$です。仮定より$|\mathbb{F}|\ge 3n$なので、Schwartz-Zippelより
\[
\Pr_{a,b\sim\mathbb{F}}[G(a,b)=0] \le \frac{2n}{3n} = \frac{2}{3}
\]
となります。すなわち、各反復でアルゴリズム3.1が誤って「$AB=C$」を出力してしまう確率は高々$1/3$ということになり、主張を得ます。

もっと色々と工夫の余地があり、例えば$r$と$s$を別々にサンプルしていましたが、$\mathbb{F}$が十分大きいという仮定を用いて良いならば$r=s$としてSchwartz-Zippelを適用すればランダムビット長を半分にできると思います。

4. 誤り訂正符号に基づく検算

実は行列積の検算は$AB-C$という行列とみなしたとき、それを誤り訂正符号で符号化し、それが非ゼロ文字列かどうかを確率的に検証している作業とみなすことができます。大雑把にいうと、誤り訂正符号とは文字列から文字列への写像であり、今回の問題設定では行列を符号化するような写像
\[
\mathsf{Enc}\colon \mathbb{F}^{n\times n}\to \mathbb{F}^{N\times N}
\]
であって、

任意の非ゼロ行列$D\in\mathbb{F}^{n\times n}$に対して、$\mathsf{Enc}(D)$は$\delta\cdot N^2$個の非ゼロ成分を含む（$\delta$は適当な定数）

という性質を持つものです。これを用いて行列検算に対する以下のアルゴリズムを考えます：

アルゴリズム4.1

1. $\mathbf{i},\mathbf{j}\sim N$を選ぶ（ここでは$N$は集合として扱う）

2. $\mathsf{Enc}(AB-C)_{\mathbf{i},\mathbf{j}}\ne 0$ならば「$AB\ne C$」を出力

3. ステップ1-2を何度も繰り返して終了しなかったら「$AB=C$」を出力して終了する。

このアルゴリズムはアルゴリズム2.1と3.1を特殊ケースとして含んでいます。例えばアルゴリズム2.1では$N=\mathbb{F}^n$として、式(1)で考えた関数を用いて

\[
\mathsf{Enc}(D)_{r,s} = F(r,s)
\]

で定まる写像を考えることになります。アルゴリズム3.1は、$N=\mathbb{F}$として、式(2)の関数

\[
\mathsf{Enc}(D)_{a,b} = G(a,b)
\]

を考えていることに他なりません。これらの関数が誤り訂正符号として望ましい性質を持つことの証明のみが非自明です。したがって、この非自明な箇所がすでに証明されているような符号を作れば、いろんな行列積検算なアルゴリズムが考えられる、ということになります。

実はこの「行列を誤り訂正符号で行列に符号化する」アイデアは[Hirahara, Shimizu, STOC2025]のアイデア元の一つになっています（この論文を書いてるときに本記事の内容を思いついた）。

約束問題についてのお約束

 ある学会で約束問題について言及したら、その後に約束問題について知らなかった人が意外と多かったのが印象的だった。学生であれば知らないのも仕方ないと思うのだが、分野が少し離れた教員にも「知らなくて勉強になった」旨のお言葉をいただいた。確かに計算量理論の論文とかを読まないとこの用語に出会う機会があまりなさそうだし、我々のアウトリーチ不足ということなのだろう。そこで布教もかねてここで簡単に解説することにした。この調子だと接頭辞にioがつく計算量クラス（io-Pとか）も解説しなければならない日が来る気がする。

色々調べたが、約束問題の用語はArora-Barak本にも載ってなかった。こういうときは大体Goldreichが何とかしてくれるのでGoldreich本を調べたらSection 2.4.1に載ってた。他にも

• Goldreichの記事（これを読めば大体OK）
• Sudanのlecture note（$\mathsf{pr\text{-}BPP}$-完全な問題の話）
• Ta-Shmaのlecture note（$\mathsf{pr\text{-}NP}\cap\mathsf{pr\text{-}coNP}$に属していて、かつ$\mathsf{NP}$-hardな問題の話）

が参考資料となる（誤り訂正符号で有名な人がこういう講義資料を書いてるのはビックリ！）

まずは復習がてら、判定問題の定義を述べる。この記事ではアルファベットは$\{0,1\}$に固定する。

定義1 (判定問題).

集合 $L\subseteq \{0,1\}^*$ を判定問題と呼ぶ。

要するに判定問題とは、アルゴリズムが与えられる任意の文字列に対してYesまたはNoの答えが定まっている問題である。では、次の問題は判定問題だろうか？

問題2 (ハミルトン閉路問題).

与えられたグラフ $G=(V,E)$ はハミルトン閉路を含むならばYes、そうでなければNoを出力せよ。

ほとんどの文脈では、ここでは与えられる入力が暗にグラフであることを仮定するのが自然である。しかし、一般にアルゴリズム（チューリング機械）は必ずしもグラフと解釈できない文字列が与えられる。そのような場合、上記の問題2の記述だけでは「グラフと解釈できない文字列が与えられた場合の答えをどうするか？」が明示されていないので、問題2だけを見るとこれは判定問題とは言えないのである。

そこで我々は暗に問題２は

問題2' (ハミルトン閉路問題).

与えられた文字列 $x\in\{0,1\}^*$ は、その長さ$|x|$が平方数であり、$n=\sqrt{|x|}$に対して、
\[
A[i][j] = x[n*i+j] \quad \text{(0-index)}
\]
で定まる行列$A\in\{0,1\}^{n\times n}$が対称行列かつ、それを隣接行列としてもつグラフがハミルトン閉路を含むならばYes、それ以外の場合はNoを出力せよ。

のように、「与えられた入力がグラフであり、かつハミルトン閉路を持つものをYesインスタンスとみなし、それ以外をNoとする」ことによってハミルトン閉路問題を判定問題として扱うことができるのである。このようにフォーマルに判定問題として扱うことによって初めて我々はクラス$\mathsf{P}$やクラス$\mathsf{NP}$に属するか否か、また$\mathsf{NP}$-完全かどうかの議論が可能になるのである。

確かに論文を書くときにいちいち問題2'のような書き方をするのは面倒なので、基本的には論文や口頭発表などでは問題2の形で議論していく。判定問題の計算量クラスを議論する際は常に問題2'のように明示的な判定問題を議論していることを念頭に置くと良い。

例えば、グラフに関する二つの問題のNP完全性の証明とかで考えるカープ帰着を考えてみよう。カープ帰着とは形式的には多項式時間で計算でき、答えを保存する関数
\[
f \colon \{0,1\}^* \to \{0,1\}^*
\]
である。我々は一方の問題のインスタンス$x$をもう一方の問題のインスタンス$f(x)$に変換するわけだが、基本的には元のインスタンスは常にグラフであることを想定し、変換後も常にグラフになるような構成を考える。しかしながら判定問題を議論する以上は元のインスタンス$x$が必ずしもグラフとは限らず、そういう場合は問題2'のような定義では元問題の自明なNoインスタンスであるため、$f(x)$は自明なNoインスタンス（$x$そのものにすればグラフでないので自明にNo）を出力するように定義される。定義に従って厳密に証明するならばこのような処理も明示する必要があるのだが、これは帰着の数学的に本質的な部分ではないしほとんどの場合は省略される。省略によって特に不便はないのだが、この辺りのことは頭の片隅に置いておく方が良いと思う。

一方で問題2のように、与えられた入力が常に何らかの構造（例えばグラフ）を持つことを仮定するという枠組みを考えたい場合も多々ある。計算量理論ではこのような問題を約束問題という。形式的には以下のように定義される：

定義3 (約束問題）

約束問題とは、組$(\Pi_{\mathrm{yes}},\Pi_{\mathrm{no}})$である。ここで、$\Pi_{\mathrm{yes}},\Pi_{\mathrm{no}}\subseteq\{0,1\}^*$は、$\Pi_{\mathrm{yes}} \cap \Pi_{\mathrm{no}} = \emptyset$ を満たす。

また、$\Pi_{\mathrm{yes}}\cup \Pi_{\mathrm{no}}$を約束という。

アルゴリズム$A$が約束問題$\Pi=(\Pi_{\mathrm{yes}},\Pi_{\mathrm{no}})$を解くとは、任意の入力$x\in\{0,1\}^*$に対して

• $x\in\Pi_{\mathrm{yes}}$ならば$A(x)=1$
  
• $x\in\Pi_{\mathrm{no}}$ならば$A(x)=0$

が成り立つことをいう。

例えば問題2は、その文面を読むと入力がグラフであると約束されているため、形式的には約束問題と呼ぶべき問題なのである。一般に与えられた$x\in\{0,1\}^*$が約束に属するかどうかが簡単に判定できれば、本質的に複雑性に差異は生まれない。例えば問題2と問題2'は、与えられた入力がグラフの隣接行列かどうかは簡単にチェックできるので、問題2を見たときに暗に問題2'とみなして判定問題として扱うことで、「問題2はNP完全である」という主張はすんなりと受け入れられるわけである。

また、約束問題では、与えられたインスタンスが約束に属さない場合は正解は定義されず、そのような入力上ではアルゴリズムはどのような挙動をしても良い（例えば停止する必要すらない）とされる。

約束問題に対しても$\mathsf{P}$や$\mathsf{NP}$の概念が定義でき、$\mathsf{pr}\text{-}\mathsf{P}$や$\mathsf{pr}\text{-}\mathsf{NP}$などと呼ばれる（記法は文献によって色々異なる）。

定義4 (約束問題の計算量クラス）

約束問題$\Pi=(\Pi_{\mathrm{yes}},\Pi_{\mathrm{no}})$は、ある多項式時間アルゴリズム$A$が存在して$A$が$\Pi$を解くとき、クラス$\mathsf{pr}\text{-}\mathsf{P}$に属するといい、そのような約束問題全体の集合を$\mathsf{pr}\text{-}\mathsf{P}$と表す。

また、ある定数$c>0$と多項式時間アルゴリズム$V$が存在して、任意の$x\in\{0,1\}^*$に対して

• $x\in \Pi_{\mathrm{yes}}$ならば、ある$y\in\{0,1\}^{|x|^c}$が存在して$V(x,y)=1$
• $x\in \Pi_{\mathrm{no}}$あらば、任意の$y\in\{0,1\}^{|x|^c}$に対して$V(x,y)=0$

を満たすとき、クラス$\mathsf{pr}\text{-}\mathsf{NP}$に属するといい、そのような約束問題全体の集合を$\mathsf{pr}\text{-}\mathsf{NP}$と表す。

また、上記のyes/noを反転させて定義されるクラスをクラス$\mathsf{pr}\text{-}\mathsf{coNP}$という。

約束が全体集合となる（すなわち$\Pi_{\mathrm{yes}}\cup\Pi_{\mathrm{no}}=\{0,1\}^*$を満たす）ときは判定問題のクラス$\mathsf{P},\mathsf{NP}$の定義と合致することがわかるだろう。

カープ帰着やクック帰着（チューリング帰着）についても同様に定義される。クック帰着については、オラクルへのクエリが約束に属さない場合はオラクルは何を出力しても良いように修正している：

定義5 (帰着）

二つの約束問題$\Pi=(\Pi_{\mathrm{yes}},\Pi_{\mathrm{no}})$と$\Pi'=(\Pi'_{\mathrm{yes}},\Pi'_{\mathrm{no}})$に対し、$\Pi$が$\Pi'$にカープ帰着できるとは、以下を満たす関数 $f\colon \{0,1\}^*\to\{0,1\}^*$ が存在することをいう：

• $f$を計算する多項式時間アルゴリズムが存在する。
• 任意の$x\in\Pi_{\mathrm{yes}}$に対し、$f(x)\in\Pi'_{\mathrm{yes}}$
• 任意の$x\in\Pi_{\mathrm{no}}$に対し、$f(x)\in\Pi'_{\mathrm{no}}$

同様に、$\Pi$が$\Pi'$にクック帰着できるとは、あるオラクルアルゴリズム$A^f$が存在して、オラクル$f\colon\{0,1\}^*\to\{0,1\}$が
\begin{align*}
&x \in \Pi'_{\mathrm{yes}} \Rightarrow f(x)=1,\\
&x \in \Pi'_{\mathrm{no}} \Rightarrow f(x)=0
\end{align*}
を満たす任意の$f$について、$A^f$は$\Pi$を解くことをいう。

ここでもやはり、アルゴリズム自体は任意の文字列を入力として受け取ることを想定しており、ただしその場合のアルゴリズムの挙動は不問に伏すことになる。細かいことだが、ここでオラクル$f$はアルゴリズムではなく関数として扱うので、例えば「停止性判定問題を解くオラクル」といった言葉が意味を持つことに注意されたい。

このような帰着に対して完全性や困難性といった概念が定義できる。

グラフの例で述べたように、約束を満たすかどうかの判定が簡単ならば両者に本質的な差異は生まれない。一方でこの判定が難しい場合は興味深い現象が発生する。例として、以下の約束問題 $\Pi$ を考えてみよう：

定義6（充足可能性択一問題）

一方が充足可能、もう一方が充足不可能であると約束されている二つの論理式 $\phi_0,\phi_1$ が与えられたとき、どちらが充足可能かを判定せよ。すなわち

\begin{align*}
&\Pi_{\mathrm{yes}} = \{(\phi_0,\phi_1)\colon \phi_0\in\mathrm{SAT}\text{ and }\phi_1 \in \mathrm{UNSAT} \}, \\
&\Pi_{\mathrm{no}} = \{(\phi_0,\phi_1) \colon \phi_0\in\mathrm{UNSAT} \text{ and }\phi_1 \in \mathrm{SAT} \}.
\end{align*}

なお、それぞれの論理式は変数は共有しない独立な二つの論理式である。

通常のSAT問題は$\mathsf{NP}$完全であり、広く信じられている$\mathsf{NP}\ne\mathsf{coNP}$を仮定すれば$\mathrm{SAT}\not\in\mathsf{coNP}$となる。この記事の最後で証明するが、$\mathsf{NP}\cap\mathsf{coNP}$に属していて、かつ$\mathsf{NP}$困難の問題が存在すれば$\mathsf{NP}=\mathsf{coNP}$が成り立つ。

主張7.

充足可能性択一問題は$\mathsf{pr}\text{-}\mathsf{NP}\cap \mathsf{pr}\text{-}\mathsf{coNP}$に属する。さらにこの問題は$\mathsf{NP}$困難である。

「属する」の部分は簡単に確認できる。YesインスタンスだろうがNoインスタンスだろうが、どちらか一方は充足可能であることが約束されているので、そちらの充足割り当てを証拠とすれば、答えがYes/Noに限らず常に証拠を持って来れる。

$\mathsf{NP}$困難性についても、以下のようにすればSATを解くことができる：充足可能性択一問題を解くオラクルを $f$ とする。SATのインスタンス$\phi$に対して（論理式でない場合はNoを出力）

1.  変数を$x_1,\dots,x_n$とする。各$i=1,\dots,n$に対して以下を実行する：
1. 論理式$\phi$に$x_i = b$を代入したものを$\phi_b$とする（$b\in\{0,1\}$）
2. オラクル$f$の入力$(\phi_0,\phi_1)$に対する答えが$1$であったとき、$\phi'=\phi_0$とする。それ以外の場合、$\phi'=\phi_1$とする。
3. $\phi$を$\phi'$に置き換えて次のループにうつる
2. 最終的に得られた$\phi$は全変数に値が代入されているため$0$または$1$である。その値をそのまま出力する。

SATインスタンス$\phi$が充足不可能であったとすると、各$x_i$にどのような値を代入しても最終的に$\phi=0$になるので、確かにオラクルアルゴリズムは$0$を正しく出力する。

一方で$\phi$が充足可能であったとする。このとき、反復で構成される$\phi'$は常に充足可能であることを証明する。そのために途中で考える$(\phi_0,\phi_1)$について場合わけを考える：

• $\phi_0,\phi_1\in\mathrm{SAT}$のとき：$x_i$にどちらを代入しても充足可能になるので$\phi'$も充足可能である。
• $\phi_0\in\mathrm{SAT},\phi_1\in\mathrm{UNSAT}$のとき：このときは$(\phi_0,\phi_1)$は充足可能性択一問題のYesインスタンスなのでオラクルは必ず$1$を返す。したがって$\phi'=\phi_0\in\mathrm{SAT}$となる。逆の場合も同様。

以上より、確かに択一問題が解ければSATも解けることになるので主張は示された。（証明終）

最後に、以下の主張を証明しておく。これによって、約束問題と判定問題のギャップが明確になるだろう：

主張8.

任意の判定問題$L\in\mathsf{NP}\cap\mathsf{coNP}$に対し、$P^L\subseteq \mathsf{NP}\cap\mathsf{coNP}$。

この主張から、もしもNP困難な判定問題$L\in\mathsf{NP}\cap\mathsf{coNP}$が存在するならば、$\mathsf{NP}\subseteq P^{L} \subseteq \mathsf{coNP}$となり、特に$\mathsf{NP}=\mathsf{coNP}$が従う。

主張の証明：

$P^L$は補問題で閉じているので、$P^L\subseteq\mathsf{NP}$を示せば十分である。そこで任意の$L'\in P^L$を固定し、$L'\in\mathsf{NP}$を示す。$L'\in P^L$より、$L'$を解くオラクルアルゴリズム $A^L$ が存在する。$L'$を検証する証拠を以下で構成する。

Yesインスタンス$x$に対し、$A^L(x)=1$となる。このとき以下を全て証拠として持つことにする：

• オラクル$L$へのクエリ $q_1,\dots,q_m\in\{0,1\}^*$ ($A$は多項式時間なので、これらのクエリは多項式長）
• 各クエリ $q_i$ に対するオラクルの返答 $a_i \in \{0,1\}$
• $a_i=1$のとき、$q_i \in L$ であることの証拠 ($L\in \mathsf{NP}$なのでそのような証拠が存在する）
• $a_i = 0$のとき、$q_i\not\in L$であることの証拠（$L \in \mathsf{coNP}$なので、同様にとれる）

すなわち$L'$のNP検証者としては、オラクルアルゴリズム$A^L$を、証拠をオラクルの返答とみなして模倣し、最終的にそれが$1$を出力したら受理するというものを考えればよい。

$x$がYesインスタンスのときは確かに上記の証拠を用意できる。Noインスタンスに対しては$A^L(x)=0$になるので、

• $A^L$を模倣する途中で証拠との整合性がとれなくなり、この時点で検証者は拒否
• もしくは整合性が完全に取れたとすると$A^L(x)=0$になるので検証者は拒否

となる。（証明終）

情報理論と加法的組合せ論の交差点: Changの不等式

概要

加法的組合せ論における基本的な定理の一つとして, Changの不等式と呼ばれるものがあります. これは, ベクトル空間 $\mathbb{F}_2^n$ の部分集合 $A\subseteq \mathbb{F}_2^n$ に対し, その指示関数の各フーリエ係数を見たとき, 絶対値の意味で大きい係数に対応するcharacter全体がなす部分空間の次元は小さいことを述べる定理です.

元々は複雑な議論を経て証明されていたのですが, Impagriazzoら(2014)によってエントロピーを用いた簡潔でとても賢い証明が与えられたので解説します. なお, 元論文やこの記事では$\mathbb{F}_2$を考えていますがより一般の有限体$\mathbb{F}_p$ ($p$が素数べき) でも, フーリエ解析の定義を変えるだけへ同様の議論で同じ結論が得られます.

エントロピーとは情報理論では主要な道具であり, 古典的にはシャノンの通信路符号化定理などが大学の講義でよく出てくるのですが, 近年は加法的組合せ論においてはMarton予想を解決したGowersら(2025)をきっかけに大きな注目を浴びています（その前からエントロピーを使った議論はいくつかありましたが）. この記事ではあまり加法的組合せ論には触れず, 単にChangの不等式とその証明にスポットをあてて解説していきます. 情報理論とフーリエ解析の交差点のように謳っていますが本質的にはPinskerの不等式とエントロピーの劣加法性しか使いません.

なお, この記事では簡単のため, 常に$\mathbb{F}_2^n$という空間にスポットをあてて議論していきますが, 加法的組合せ論の研究対象はこれに限らずアーベル群を考えることが多いです.

Changの不等式とは？

Changの不等式を述べるためにまず $\mathbb{F}_2^n$ 上の関数に対するフーリエ変換の定義を述べていきます. $\mathbb{F}_2^n$から$\mathbb{R}$への関数全体に対し,
\[
\langle f,g\rangle = \mathbb{E}_{x\sim \mathbb{F}_2^n} [f(x)g(x)]
\]
によって内積を定めます. ここで $x\sim \mathbb{F}_2^n$ とは, $\mathbb{F}_2^n$から一様ランダムに元 $x$ を選ぶ, ということを意味し, それに関する期待値をとっています. 以後, 期待値をとるときは常に一様分布を考えるので$\mathbb{E}_{x\sim\mathbb{F}_2^n}$を省略して$\mathbb{E}_x$と書くことにします.

次に, 各ベクトル $r\in\mathbb{F}_2^n$ に対し, 関数 $\chi_r\colon\mathbb{F}_2^n\to \{-1,1\}$を
\[
\chi_r(x) = (-1)^{\sum_{i=1}^n r_i x_i}
\]
と定めます. ここで右肩の総和は$\mathbb{F}_2$上の演算で考えています (mod 2をとらなくても$\chi_r(x)$の値は変わらないのでどちらでもよいです).

このとき, 任意の関数 $f \colon \mathbb{F}_2^n\to\mathbb{R}$は以下のように線形結合で表すことができます:
\[
f(x) = \sum_{r\in\mathbb{F}_2^n} \langle f, \chi_r \rangle \cdot \chi_r(x).
\]
これをフーリエ逆変換と呼びます. つまり, $(\chi_r)_{r\in\mathbb{F}_2^n}$は, 関数全体の空間$\{f\colon \mathbb{F}_2^n\to\mathbb{R}\}$を線形空間とみなしたときの直交基底のように扱うことができるわけです. このときの線形結合の各係数を
\[
\widehat{f}(r) := \langle f, \chi_r \rangle = \mathbb{E}_x[f(x)\cdot (-1)^{\sum_{i=1}^n r_ix_i}]
\]
と表します.

以下にフーリエ級数に関する基本的な事実を述べていきます：

• $\langle f,f\rangle = \mathbb{E}_x [f(x)^2] = \langle \widehat{f},\widehat{f} \rangle = \mathbb{E}_r[\widehat{f}(r)^2].$ (Parsevalの等式). より一般に写像 $f\mapsto \widehat{f}$ は線形変換であり, ユニタリである.
• 定義から簡単に確認できるが, $\widehat{f}(0)=\mathbb{E}_x[f(x)]$.

加法的組合せ論は極値組合せ論と少し似ていて, 集合$A\subseteq\mathbb{F}_2^n$が密である時にそれが何かしらの構造的性質を持つことを論ずる理論です (一般に$\mathbb{F}_2^n$に限らず一般のアーベル群を考えます）. 構造的性質とは「($\mathbb{Z}/n\mathbb{Z}$の場合は)長い等差数列を含む」だとか「次元の大きな部分空間を含む」といった類の性質です. 

そこで集合$A\subseteq \mathbb{F}_2^n$ を指示関数 $A\colon \mathbb{F}_2^n\to\{0,1\}$と同一視します. この集合$A$の密度を$\delta(A):=|A|/2^n$ で定めます. 

一般にベクトル $a=(a_1,\dots,a_n)\in\mathbb{R}^n$ に対して, 絶対値の大きな成分があると, そのインデックスはベクトル$a$の特徴を掴んでいるといえます. この発想をフーリエ変換にも持ち込みましょう. 関数 $A$ を基底 $(\chi_r)_r$ の線型結合で表したとき, $|\widehat{f}(A)|$が大きいような $r$ を集めると, それが $A$ の構造的な性質を反映しているように思えます. Changの不等式とは, そのような $r$ の全体は実は小さな部分空間に収まっていることを述べる定理です.

正確に述べるために, パラメータ $\rho>0$ に対して
\[
\mathrm{Spec}_\rho(A) := \{r\in \mathbb{F}_2^n\colon |\widehat{A}(r)|>\rho\cdot\delta(A)\}
\]
と定めます (ここでの不等号は真の不等号$>$になっていることに注意).

定理1 (Changの不等式).

任意の集合 $A\subseteq\mathbb{F}_2^n$ および パラメータ $\rho>0$ に対し, $\mathrm{Spec}_\rho(A)$ は高々 $\rho^{-2}\log(1/\delta(A))$ 本の線形独立なベクトルを含む. すなわち

\[
\dim \mathrm{span}(\mathrm{Spec}_\rho(A)) \le \frac{2\log(1/\delta(A))}{\rho^2}.
\]
(ここで$\log$は自然対数).

証明の準備 (エントロピー)

Changの定理の証明をするために, エントロピーの概念や基礎事項を導入します. 有限集合 $\Omega$ 上に値をとる確率変数 $X$ のエントロピー $H(X)$ を
\[
H(X) := \sum_{x\in\mathsf{supp}(X)} \log\frac{1}{\Pr[X=x]}
\]
で定めます. ここで$\mathsf{supp}(X)=\{x\in\Omega\colon\Pr[X=x]>0\}$は確率変数 $X$ の台です. なお, 情報理論ではしばし$\log$の底は2にしますが, ここでは自然対数を考えます (本質的にはどちらでも良いのですが, 自然対数の方が後で紹介するPinskerの不等式の見栄えが良くなります）.

ここではベクトル空間$\mathbb{F}_2^n$上に値をとる確率変数$X=(X_1,\dots,X_n)$を考えていくことになりますが, このようなベクトル値をとる確率変数のエントロピーについては以下の重要な不等式が成り立ちます：

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

$X=(X_1,\dots,X_n)$を$\Omega^n$上に値をとる確率変数とする (ただし$\Omega$は有限集合). このとき

\[
H(X) \le H(X_1)+\dots+H(X_n).
\]

例えば$X$が$\mathbb{F}_2^n$上で一様ランダムに選ばれたとしましょう. このときは$X_1,\dots,X_n$はそれぞれ独立に$\mathbb{F}_2^n$上で一様に分布するため,
\begin{align*}
&H(X)=n\log 2,\\
&H(X_i)=\log 2
\end{align*}
となり, 補題2を等式で満たします.

次に, Pinskerの不等式と呼ばれる基礎的な不等式を導入します. 同じ有限集合$\Omega$上に値をとる二つの確率変数 $X,Y$ に対して
\[
d_{TV}(X,Y) = \frac{1}{2}\sum_{x\in\Omega}|\Pr[X=x]-\Pr[Y=x]|
\]
を全変動距離 (total variation distance) と呼びます. 分布をベクトルとみなしたときのいわゆる$\ell_1$ノルムに相当する距離です.

一般に確率変数のエントロピー $H(X)$ とは $X$ が「どれほどのランダムネスを含むか」を示す指標ですが, 直感的にはこれが大きいほど$X$の分布は一様分布に近いことが予想されます. Pinskerの不等式（のエントロピーに対する特殊ケース）は, 確率変数のエントロピーと一様分布からの全変動距離の大きさの関係を表す不等式です.

補題3 (Pinskerの不等式の特殊ケース).

有限集合$\Omega$上に値をとる確率変数$X$を考え, $\Omega$上の一様分布に従う確率変数を$U$とする. このとき

\[
\log|\Omega| - H(X) \ge 2d_{TV}(X,U)^2.
\]
ただし$\log$は自然対数.

本来のPinskerの不等式では左辺はより一般の二つの確率変数$X$と$U$のKLダイバージェンス $\mathrm{KL}(X||U)$と呼ばれる量になるのですが, $U$が一様分布のとき$\mathrm{KL}(X||U)=\log|\Omega| - H(X)$という等式が成り立つことを利用しました. 

Changの不等式の証明

ここまででChangの不等式の証明の準備ができました. 以下の重要な補題を証明します.

補題4.

集合 $A\subseteq\mathbb{F}_2^n$ に対し, $\alpha=\delta(A)=|A|/2^n$とする. ベクトル$e_1,\dots,e_n\in\mathbb{F}_2^n$を単位ベクトルとする (つまり, $e_i$は第$i$成分が$1$で他の成分は全て$0$). このとき

\[
\sum_{i=1}^n \widehat{A}(e_i)^2 \le 2\alpha^2\log(1/\alpha).
\]

注釈. 実際には$e_1,\dots,e_n$として, $\mathbb{F}_2^n$の任意の基底をとっても同じ主張が成り立つことが定義から簡単に確認できます（一般の基底を考えても標準基底$e_1,\dots,e_n$のケースに帰着できる).

証明. 集合$A$上一様ランダムに選ばれたベクトルを確率変数として $X=(X_1,\dots,X_n)$とします. このとき, $H(X)=\log |A| = \log \alpha 2^n = n\log 2 - \log(1/\alpha)$ が成り立ちます.

フーリエ級数の定義より
$$\begin{align*}
\widehat{A}(e_i) &= \mathbb{E}_{x}\left[ A(x) \cdot \chi_{e_i}(x) \right] \\
&= \mathbb{E}_{x}\left[ A(x) \cdot (-1)^{x_i} \right] \\
&= \frac{|A|}{2^n}\cdot \frac{1}{|A|} \sum_{x\in A} (-1)^{x_i} \\
&= \alpha\cdot \left(\Pr[X_i=0] - \Pr[X_i=1]\right).
\end{align*}$$
ここで, 一般に$\{0,1\}$上に値をとる確率変数 $Y$ に対して, $\{0,1\}$上一様分布に従う確率変数を$U$とすると,
$$\begin{align*}
d_{TV}(Y,U) &= \frac{1}{2}|\Pr[Y=0]-1/2| + \frac{1}{2} |\Pr[Y=1]- 1/2| \\
&= |\Pr[Y=0]-1/2| \\
&= \frac{1}{2}|2\Pr[Y=0] - 1 | \\
&= \frac{1}{2} |\Pr[Y=0] - \Pr[Y=1]|
\end{align*}$$
が成り立つことから,
$$\begin{align*}
\widehat{A}(e_i)^2 = \alpha^2 \cdot 4d_{TV}(X_i,U)^2 \le 2\alpha^2 \cdot (\log 2 - H(X_i))
\end{align*}$$
を得ます (最後の不等式でPinskerの不等式を用いた). これを全ての$i$について足し合わせてエントロピーの劣加法性を用いると
$$\begin{align*}
\sum_i \widehat{A}(e_i)^2 &\le 2\alpha^2 n \log 2 - 2\alpha^2 \sum_i H(X_i) \\
&\le 2\alpha^2 n\log 2 - 2\alpha^2 H(X) \\
&= 2\alpha^2 n\log 2 - 2\alpha^2 (n\log 2 - \log(1/\alpha) \\
&= 2\alpha^2\log(1/\alpha)
\end{align*}$$
となり, 主張を得ます. (証明終)

この補題は$\mathbb{F}_2^n$の標準基底 $e_1,\dots,e_n$ におけるフーリエ級数の二乗和を抑えるものでしたが, 一般の基底 $b_1,\dots,b_n$ に対しても同様に成り立ちます:

系5.

集合 $A\subseteq\mathbb{F}_2^n$ に対し, $\alpha=\delta(A)=|A|/2^n$とする. 線形独立な$n$個のベクトル $b_1,\dots,b_n\in\mathbb{F}_2^n$ に対して

\[
\sum_{i=1}^n \widehat{A}(b_i)^2 \le 2\alpha^2\log(1/\alpha).
\]

証明. 適当な正則行列 $B$ を用いて $b_i^\top B = e_i^\top$ が成り立つようにできます. 集合 $B\cdot A$を $B\cdot A = \{Bx \colon x\in A\}$ とすると
$$\begin{align*}
\widehat{A}(b_i) &= \mathbb{E}_x\left[ A(x) \cdot (-1)^{b_i^\top x} \right] \\
&= \mathbb{E}_x\left[ A(x) \cdot (-1)^{e_i^\top B x} \right]  \\
&= \mathbb{E}_y\left[ A(B^{-1} y) \cdot (-1)^{e_i^\top y} \right]  & & y=Bx\\
&= \mathbb{E}_y\left[ B\cdot A(y) \cdot (-1)^{e_i^\top y} \right] \\
&= \widehat{B\cdot A}(e_i).
\end{align*}$$

また, $|B\cdot A|=|A|$なので, 補題4を集合$B\cdot A$に適用すれば得られます. (証明終)

いよいよ Chang の不等式の証明の準備ができました.

定理1の証明. 集合$A\subseteq \mathbb{F}_2^n$に対し, 集合 $\mathrm{Spec}_{\rho}(A)$ が $d:=\frac{\log(1/\delta(A))}{\rho^2}$ 本の線形独立なベクトル $b_1,\dots,b_d \in\mathbb{F}_2^n$ を含むとします. これらのベクトルを含む基底 $b_1,\dots,b_d,b_{d+1},\dots,b_n$ を選びます.

この基底に対して系5を適用すると
$$\begin{align*}
\sum_{i=1}^n \widehat{A}(b_i)^2 \le 2\delta(A)^2 \log(1/\alpha).
\end{align*}$$
一方で, $b_1,\dots,b_d\in\mathrm{Spec}_\rho(A)$なので
$$\begin{align*}
\sum_{i=1}^d \widehat{A}(b_i)^2 \ge \rho^2\delta(A)^2\cdot d
\end{align*}$$
が成り立つので, $d \le \frac{2\log(1/\alpha)}{\delta(A)^2}$ が成り立ちます.