Inverse Conjecture for the Gowers norm （続き） - 某理論計算機科学者の研究日誌

前回のエントリの肝心の中身について書こうと思います．そもそも Gowers uniformity norm というのは Gowers が Erdos-Turan conjecture の(Szemerediの定理として知られている)ある特殊ケースの別証明のために導入した概念です．

一般的には以下のように定義されます．

定義（degree-d Gowers uniformity norm）

$G$ を加法群とする．複素関数 $f:G\rightarrow\mathbb{C}$ に対して，その degree-d Gowers uniformity norm $||f||_{U^d(G)}$ は以下の式で与えられる．

$||f||_{U^d(G)} = \bigg(\mathbb{E}_{x\in G, h\in G^d}\bigg(\prod_{\omega\in\{0,1\}^d}C^{|\omega|}T^{\omega\cdot h}(f(x)) \bigg) \bigg)^{1/2^d}$

ここで， $h=(h_1,...,h_d), \omega=(\omega_1,...,\omega_d)$ としたときに， $\omega\cdot h = \omega_1h_1+\cdots+\omega_dh_d, |\omega|=\omega_1+\cdots+\omega_d$ であり， $C$ は共役作用素 $C(f(x))=\overline{f(x)}$ ， $T^h$ はシフト作用素 $T^h(f(x))=f(x+h)$ を表す．

これだとどうなっているのか分かりにくいので $f$ を計算機科学者に馴染みの深いnビット列( $GF(2^n)$ )から実数への関数として定義した場合にどうなるか見てみましょう．

定義（degree-d Gowers uniformity norm over $GF(2^n)$ ）

実関数 $f:GF(2^n)\rightarrow\mathbb{R}$ に対して，その degree-d Gowers uniformity norm は以下の式で与えられる．

$||f||_{U^d(GF(2^n))} = \bigg(\mathbb{E}_{x\in\{0,1\}^n, y_1,...,y_d\in\{0,1\}^n}\bigg(\prod_{S\subseteq\{1,...,d\}}f\left(x\oplus\bigoplus_{j\in S}y_j\right) \bigg) \bigg)^{1/2^d}$

これでもまだ分かりにくいですね．実は d=0 のときには
$||f||_{U^0(GF(2^n))} = \mathbb{E}(f(x))$
d=1 のときには
$||f||_{U^1(GF(2^n))} = \left|\mathbb{E}(f(x))\right|$
となっていることが分かります．残念ながら d が 2 以上のときはこのような簡単な表現は持ちません．ここ数年，この概念の計算量理論への重要な応用がいくつか見つかっており，注目を集めつつあります．例えば

多項式の相関評価

E. Viola and A. Wigderson
- Norms, XOR lemmas, and lower bounds for GF(2) polynomials and multiparty protocols

確率的検査可能証明(PCP)の検査解析

A. Samorodnitsky and L. Trevisan
- Gowers Uniformity, Influence of Variables, and PCPs

A. Samorodnitsky
- Low-degree tests at large distance

低次数多項式に対する擬似乱数生成器

A. Bogdanov
- Pseudorandom generators for low degree polynomials

A. Bogdanov and E. Viola
- Pseudorandom bits for polynomials

S. Lovett
- Unconditional Pseudorandom Generators for Low Degree Polynomials

とりあえず知っている限りで挙げてみましたが，既に結構たくさんの論文が出ていますね．またこの続きは次回のエントリに書こうと思います．