概要
加法的組合せ論における基本的な定理の一つとして, 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)\}
\]
と定めます (ここでの不等号は真の不等号$>$になっていることに注意).
\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)$を考えていくことになりますが, このようなベクトル値をとる確率変数のエントロピーについては以下の重要な不等式が成り立ちます：
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の不等式（のエントロピーに対する特殊ケース）は, 確率変数のエントロピーと一様分布からの全変動距離の大きさの関係を表す不等式です.
\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の不等式の証明の準備ができました. 以下の重要な補題を証明します.
\sum_{i=1}^n \widehat{A}(e_i)^2 \le 2\alpha^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*}$$
となり, 主張を得ます. (証明終)
\sum_{i=1}^n \widehat{A}(b_i)^2 \le 2\alpha^2\log(1/\alpha).
\]
$$\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*}$$
$$\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}$ が成り立ちます.
0 件のコメント:
コメントを投稿