Inverse Conjecture for the Gowers norm（続き）

研究

前回のエントリの続きです．さて Gowers norm というものが計算量理論でいろいろ応用できることを簡単に触れました．その Gowers norm の顕著な特徴として，高次の Gowers norm では低次多項式の影響が失われる，というものがあります．より具体的には，任意の関数 f:G^n\to\mathbb{F} とG上の n 変数 (d-1)次多項式を考えます．このとき，

||f\cdot p||_{U^d(G)} = ||f||_{U^d(G)}

という関係が成立します．つまり f と p の積の degree-d uniformity は f 自身の degree-d uniformity と同じ値を取ります．（ここでは p として多項式を取りましたが，実はもっと一般的な関数に対しても影響が消せます．）したがって f が (d-1)次多項式であれば，その degree-d uniformity は ||1||_{U^d(G)}=1 になります．

では，この逆が成立するか？というのが Gowers norm の逆予想，「f の degree-d Gowers uniformity が大きければ，任意の d 次多項式 p で f が近似できない」というものです．

d の値が 2 あるいは 3 の場合には Green と Tao によって以下の論文で示されています．

では d が 4 以上でどうなるか，と言いますと実は成り立たない，ということが割と最近以下の論文で独立に示されました．

例えば，前者ではブール関数上の degree-4 Gowers uniformity で反例を与えています．
実は困ったことに以前のエントリで挙げた

  • Andrej Bogdanov and Emanuele Viola
    • Pseudorandom bits for polynomials

もこの Inverse Gowers Conjecture の成立を仮定した上で低次多項式に対する擬似乱数生成器を構成しています．しかしこれは最近改良されて

  • Shachar Lovett
    • Unconditional Pseudorandom Generators for Low Degree Polynomials

で Inverse Gowers Conjecture 無しでの構成が与えられているようです．