Gowersノルム(Gowers norm)とは、有限アーベル群上の複素数値関数 $f$ について、$f$ とその共役を $k$ 次元の立方体 $\{x+\omega\cdot h\}$ の $2^k$ 個の頂点で掛け合わせて平均し、$2^k$ 乗根をとった量 $\|f\|_{U^k}$ である。Gowers–Cauchy–Schwarz の不等式から $k\ge2$ でノルムになり、$k$ について単調に増え、巡回群では $U^2$ ノルムは Fourier 係数の $\ell^4$ ノルムに等しい。位数が $(k-1)!$ と互いに素な巡回群では、絶対値が $1$ 以下の関数による $k$ 項等差数列の重み付き個数が $U^{k-1}$ ノルムで抑えられ、4 項では $U^2$ ノルムでは足りない。Szemerédi の定理と Green–Tao の定理の証明で使われる。
前提知識: アーベル群, Cauchy–Schwarzの不等式, 離散Fourier変換, 半ノルム
Gowersノルム(Gowers norm)とは、有限アーベル群 $G$ 上の複素数値関数 $f$ に対して、$f$ の値を $k$ 次元の「立方体」$\{x+\omega_1h_1+\dots+\omega_kh_k\}$ の $2^k$ 個の頂点で掛け合わせた平均から定まる量 $\|f\|_{U^k}$ である。$\|f\|_{U^k}$ が小さいことを、$f$ が $U^k$ 一様(ランダムな関数のように振る舞う)という。
$k=2$ のとき $\|f\|_{U^2}$ は Fourier 係数の $\ell^4$ ノルムに等しく、3 項の等差数列の個数は $U^2$ ノルムで制御される。ところが 4 項の等差数列は Fourier 係数では制御できず、$U^3$ ノルムが必要になる。一般に $k$ 項の等差数列の重み付きの個数は $U^{k-1}$ ノルムで抑えられる(一般化 von Neumann の定理)。Gowers はこのノルムを導入して Szemerédiの定理 の新しい証明を与え、その方法は高次 Fourier 解析と呼ばれる(Zha23 p. 213)。Green と Tao も Green–Taoの定理 の証明でこのノルムを使った(GT08 §5)。
この記事では、Gowers ノルムを定義し、Gowers–Cauchy–Schwarz の不等式、単調性、ノルムであること、$U^2$ と Fourier 係数の関係、等差数列の数え上げ補題を証明する。
以下、$G$ は有限アーベル群、$\mathbb{E}_{x\in G}$ は $G$ 上の平均 $\frac1{\lvert G\rvert}\sum_{x\in G}$ である。$\mathcal{C}$ を複素共役 $z\mapsto\bar z$ とし、$\mathcal{C}^0z=z$、$\mathcal{C}^1z=\bar z$ と書く。$\omega=(\omega_1,\dots,\omega_k)\in\{0,1\}^k$ と $h=(h_1,\dots,h_k)\in G^k$ について $\lvert\omega\rvert:=\omega_1+\dots+\omega_k$、$\omega\cdot h:=\omega_1h_1+\dots+\omega_kh_k$ とおく。
$k\ge1$ とし、$f_\omega\colon G\to\mathbb{C}$($\omega\in\{0,1\}^k$)を $2^k$ 個の関数とする。
$$
\langle(f_\omega)_\omega\rangle_{U^k}:=\mathbb{E}_{x\in G,\ h\in G^k}\prod_{\omega\in\{0,1\}^k}\mathcal{C}^{\lvert\omega\rvert}f_\omega(x+\omega\cdot h)
$$
を Gowers 内積 という。すべての $f_\omega$ が $f$ に等しいときの値は $0$ 以上の実数で(lem-gn-cs-step)、
$$
\|f\|_{U^k}:=\langle(f)_\omega\rangle_{U^k}^{1/2^k}
$$
を $f$ の $U^k$ ノルム(Gowers の一様性ノルム)という。
$k=2$ では $\|f\|_{U^2}^4=\mathbb{E}_{x,h_1,h_2}f(x)\overline{f(x+h_1)}\,\overline{f(x+h_2)}f(x+h_1+h_2)$ で、平行四辺形の 4 頂点で $f$ を掛けて平均したものである。この定義は GT08 Definition 5.1・(5.4)(pp. 11–12)の実数値の定義に共役を入れたもので、Zha23 Exercise 6.2.13・6.2.14(pp. 213–214)、p. 262 と同じである。
関数の族 $F=(f_\omega)_\omega$、座標の番号 $i\in\{1,\dots,k\}$、$j\in\{0,1\}$ について、$F^{i\to j}$ を「$f_\omega$ を、$\omega$ の第 $i$ 成分を $j$ に置き換えた添字の関数に替えた族」とする。$F^{i\to j}$ は第 $i$ 成分によらない。
$h$ の座標の並べ替えは $G^k$ の全単射で平均を変えないので、$i=k$ としてよい。$h=(h',h_k)$、$\omega=(\omega',\omega_k)$ と分け、$h'$ を固定して $j\in\{0,1\}$ について
$$
\Phi_j(y):=\prod_{\omega'\in\{0,1\}^{k-1}}\mathcal{C}^{\lvert\omega'\rvert}f_{(\omega',j)}(y+\omega'\cdot h')
$$
とおく($k=1$ では $\Phi_j=f_j$)。$\mathcal{C}^{\lvert\omega'\rvert+1}=\mathcal{C}\circ\mathcal{C}^{\lvert\omega'\rvert}$ なので、立方体の積は $\Phi_0(x)\,\overline{\Phi_1(x+h_k)}$ である。$x$ と $y:=x+h_k$ は独立に $G$ 上を動くので
$$
\langle F\rangle_{U^k}=\mathbb{E}_{h'}\Bigl(\mathbb{E}_x\Phi_0(x)\Bigr)\overline{\Bigl(\mathbb{E}_y\Phi_1(y)\Bigr)}
$$
である。1:$F$ が第 $k$ 成分によらなければ $\Phi_0=\Phi_1$ で、右辺は $\mathbb{E}_{h'}\lvert\mathbb{E}_x\Phi_0\rvert^2\ge0$ である。これは 3 の式でもあり、$k=1$ では $\lvert\mathbb{E}f\rvert^2$ である。2:Cauchy–Schwarzの不等式 を $h'$ の平均に当てると $\lvert\langle F\rangle\rvert\le(\mathbb{E}_{h'}\lvert\mathbb{E}\Phi_0\rvert^2)^{1/2}(\mathbb{E}_{h'}\lvert\mathbb{E}\Phi_1\rvert^2)^{1/2}$ で、1 の計算から右辺の因子はそれぞれ $\langle F^{k\to0}\rangle$、$\langle F^{k\to1}\rangle$ である(GT08 (5.2)・(5.3), pp. 11–12 の議論)。$\square$
$\eta\in\{0,1\}^i$ について、$F$ の第 $1,\dots,i$ 成分を $\eta$ に置き換えた族を $F^{\eta}$ とする。$i$ についての帰納法で
$$
\lvert\langle F\rangle\rvert\le\prod_{\eta\in\{0,1\}^i}\langle F^{\eta}\rangle^{1/2^i}
$$
を示す。$i=1$ は lem-gn-cs-step の 2 である。$i$ で成り立てば、右辺の各因子に第 $i+1$ 成分について lem-gn-cs-step の 2 を当てると、$(F^{\eta})^{i+1\to j}=F^{(\eta,j)}$ なので $i+1$ でも成り立つ。$i=k$ では $F^{\eta}$ は全成分が $f_\eta$ の族なので $\langle F^{\eta}\rangle=\|f_\eta\|_{U^k}^{2^k}$ であり、主張を得る。$\square$
$k\ge1$ とする。
1:立方体の積には $c$ が $2^{k-1}$ 回、$\bar c$ が $2^{k-1}$ 回現れるので、$\|cf\|^{2^k}=\lvert c\rvert^{2^k}\|f\|^{2^k}$ である。Gowers 内積は各 $f_\omega$ について加法的なので、$\|f+g\|^{2^k}=\langle(f+g)_\omega\rangle$ は、各頂点に $f$ か $g$ を置いた $2^{2^k}$ 個の内積の和になる。$f$ を $s$ 個の頂点に置いた項は thm-gn-gcs により絶対値が $\|f\|^s\|g\|^{2^k-s}$ 以下なので、和は $(\|f\|+\|g\|)^{2^k}$ 以下である(GT08 p. 12)。
2:$U^{k+1}$ の族を $\omega_{k+1}=0$ の頂点では $f$、$\omega_{k+1}=1$ の頂点では定数関数 $1$ として定める。$h_{k+1}$ はどこにも現れないので、この族の内積は $\|f\|_{U^k}^{2^k}$ である。thm-gn-gcs と $\|1\|_{U^{k+1}}=1$ により $\|f\|_{U^k}^{2^k}\le\|f\|_{U^{k+1}}^{2^k}$ である(GT08 (5.7), p. 13)。
3:lem-gn-cs-step の 3 を $k=2$ で使い、$h_1=0$ の項だけを残すと
$$
\|f\|_{U^2}^4=\mathbb{E}_{h_1}\Bigl\lvert\mathbb{E}_xf(x)\overline{f(x+h_1)}\Bigr\rvert^2\ge\frac1{\lvert G\rvert}\Bigl(\mathbb{E}_x\lvert f(x)\rvert^2\Bigr)^2
$$
である。よって $\|f\|_{U^2}=0$ なら $f=0$ で、2 により $k\ge2$ でも同じである。$U^1$ については、$G=\mathbb{Z}/N\mathbb{Z}$($N\ge2$)で $f(x)=e^{2\pi ix/N}$ とすると $f\ne0$ だが $\|f\|_{U^1}=\lvert\mathbb{E}f\rvert=0$ である。$\square$
ここでは $G=\mathbb{Z}/N\mathbb{Z}$ とし、$e(t):=e^{2\pi it}$、$\hat f(\xi):=\mathbb{E}_xf(x)e(-x\xi/N)$ とする。離散Fourier変換 の反転公式 $f(x)=\sum_\xi\hat f(\xi)e(x\xi/N)$ と Parseval の等式 $\mathbb{E}_x\lvert f(x)\rvert^2=\sum_\xi\lvert\hat f(\xi)\rvert^2$ を使う。
定義の 4 つの因子に反転公式を代入すると、$\|f\|_{U^2}^4$ は
$$
\sum_{\xi_1,\dots,\xi_4}\hat f(\xi_1)\overline{\hat f(\xi_2)}\,\overline{\hat f(\xi_3)}\hat f(\xi_4)\ \mathbb{E}_{x,h_1,h_2}e\Bigl(\frac{x(\xi_1-\xi_2-\xi_3+\xi_4)+h_1(\xi_4-\xi_2)+h_2(\xi_4-\xi_3)}{N}\Bigr)
$$
になる。$\mathbb{E}_ye(ay/N)$ は $a=0$ なら $1$、そうでなければ $0$ なので、平均は $\xi_2=\xi_4$、$\xi_3=\xi_4$、$\xi_1=\xi_4$ のときだけ $1$ で、ほかは $0$ である。よって和は $\sum_\xi\lvert\hat f(\xi)\rvert^4$ である。後半:$\max\lvert\hat f\rvert^4\le\sum\lvert\hat f\rvert^4\le\max\lvert\hat f\rvert^2\sum\lvert\hat f\rvert^2$ と Parseval の等式による。$\square$
したがって、値が単位円板に入る $f$ について、$U^2$ ノルムが小さいことと、すべての Fourier 係数が小さいことは同値である。
$k\ge3$ と $f_0,\dots,f_{k-1}\colon\mathbb{Z}/N\mathbb{Z}\to\mathbb{C}$ について
$$
\Lambda_k(f_0,\dots,f_{k-1}):=\mathbb{E}_{x,d\in\mathbb{Z}/N\mathbb{Z}}\prod_{j=0}^{k-1}f_j(x+jd)
$$
とおく。$A\subset\mathbb{Z}/N\mathbb{Z}$ の指示関数 $1_A$ について $N^2\Lambda_k(1_A,\dots,1_A)$ は、公差 $0$ のものも含めた $A$ の中の $k$ 項等差数列の個数である。
$k\ge3$ とし、$N$ を $(k-1)!$ と互いに素な正の整数とする。$\lvert f_j\rvert\le1$($1\le j\le k-1$)なら
$$
\lvert\Lambda_k(f_0,\dots,f_{k-1})\rvert\le\|f_0\|_{U^{k-1}}
$$
である。$\lvert f_j\rvert\le1$($0\le j\le k-2$)なら $\lvert\Lambda_k\rvert\le\|f_{k-1}\|_{U^{k-1}}$ である。
$f_j$ をすべて $\lvert f_j\rvert\le1$ とすると、$\lvert\Lambda_k\rvert\le\min_j\|f_j\|_{U^{k-1}}$ が成り立つ(中間の $f_j$ については、下の証明の $n_m$ を $n'_m(y):=\sum_{i\ne j}\bigl(1-\frac{m-j}{i-j}\bigr)y_i$($y$ の添字 $i$ は $0,\dots,k-1$ のうち $j$ 以外を動く。$0< \lvert i-j\rvert\le k-1$ なので $i-j$ は可逆)に替えると、$n'_m$ は $y_m$ によらず $n'_j=\sum_iy_i$ なので、同じ議論で示せる)。これは Gowers による(GT08 p. 14 の Remark。GT08 Proposition 5.3, p. 14 は擬ランダムな重みのついた一般化を述べる。$k=4$、$G=\mathbb{F}_p^n$ の場合は Zha23 Exercise 6.2.14 (d), p. 214)。
変数の取り替え. $1,\dots,k-1$ は $\mathbb{Z}/N\mathbb{Z}$ で可逆である。$y=(y_1,\dots,y_{k-1})\in(\mathbb{Z}/N\mathbb{Z})^{k-1}$ について
$$
n_j(y):=\sum_{i=1}^{k-1}\Bigl(1-\frac ji\Bigr)y_i\qquad(0\le j\le k-1)
$$
とおく。$X:=\sum_iy_i$、$D:=\sum_ii^{-1}y_i$ とすると $n_j=X-jD$ である。$y\mapsto(X,D)$ は全射な準同型($y_1,y_2$ だけを動かすと、行列 $\begin{pmatrix}1&1\\1&1/2\end{pmatrix}$ の行列式 $-1/2$ が可逆)なので、$(X,-D)$ は $(\mathbb{Z}/N\mathbb{Z})^2$ 上で一様に分布し、$\Lambda_k=\mathbb{E}_y\prod_jF_j(y)$、$F_j:=f_j\circ n_j$ である。$n_j$ の $y_j$ の係数は $1-j/j=0$ なので、$F_j$($1\le j\le k-1$)は $y_j$ によらない。$F_0(y)=f_0(y_1+\dots+y_{k-1})$ である。
消去の補題. $r\ge1$、$Y:=(\mathbb{Z}/N\mathbb{Z})^r$ とし、$F_1,\dots,F_r\colon Y\to\mathbb{C}$ が $\lvert F_j\rvert\le1$ で $F_j$ は $y_j$ によらないとする。$y^{(0)},y^{(1)}\in Y$ と $\omega\in\{0,1\}^r$ について $y^{(\omega)}:=(y^{(\omega_1)}_1,\dots,y^{(\omega_r)}_r)$ とおくと
$$
\Bigl\lvert\mathbb{E}_y\prod_{j=0}^rF_j(y)\Bigr\rvert^{2^r}\le\mathbb{E}_{y^{(0)},y^{(1)}}\prod_{\omega\in\{0,1\}^r}\mathcal{C}^{\lvert\omega\rvert}F_0(y^{(\omega)})\qquad(\ast)
$$
で、右辺は $0$ 以上の実数である。$r$ についての帰納法で示す。$F_r$ は $y_r$ によらないので、$y_{< r}:=(y_1,\dots,y_{r-1})$ と書くと、$\lvert F_r\rvert\le1$ と Cauchy–Schwarz により
$$
\Bigl\lvert\mathbb{E}_y\prod_{j=0}^rF_j\Bigr\rvert^2\le\mathbb{E}_{y_{< r}}\Bigl\lvert\mathbb{E}_{y_r}\prod_{j< r}F_j\Bigr\rvert^2=\mathbb{E}_{s_0,s_1}\,\mathbb{E}_{y_{< r}}\prod_{j< r}G^{s}_j(y_{< r})
$$
である。ここで $s=(s_0,s_1)$ を固定して $G^{s}_j(y_{< r}):=F_j(y_{< r},s_0)\overline{F_j(y_{< r},s_1)}$ とおいた。$r=1$ では右辺は $\lvert\mathbb{E}F_0\rvert^2$ で、$(\ast)$ の右辺に等しい。$r\ge2$ では $G^s_j$($1\le j\le r-1$)は $\lvert G^s_j\rvert\le1$ で $y_j$ によらないので、各 $s$ に帰納法の仮定($r-1$)を当てられる。べき平均の不等式 $\lvert\mathbb{E}_sa_s\rvert^{2^{r-1}}\le\mathbb{E}_s\lvert a_s\rvert^{2^{r-1}}$ と合わせると、$\lvert\mathbb{E}_y\prod_jF_j\rvert^{2^r}$ は、$G^s_0$ についての $(\ast)$ の右辺を $s$ で平均したもの以下である。$G^s_0$ の立方体の積は $F_0$ の $r$ 次元の立方体の積なので、これが $(\ast)$ の右辺である。
まとめ. $(\ast)$ を $r=k-1$ で当てる。$x:=\sum_iy^{(0)}_i$、$h_i:=y^{(1)}_i-y^{(0)}_i$ とおくと $\sum_iy^{(\omega_i)}_i=x+\omega\cdot h$ で、$(x,h)$ は $(\mathbb{Z}/N\mathbb{Z})^{k}$ 上で一様に分布する。よって $(\ast)$ の右辺は $\|f_0\|_{U^{k-1}}^{2^{k-1}}$ で、前半を得る。後半は、$x':=x+(k-1)d$、$d':=-d$ の取り替えで $\Lambda_k(f_0,\dots,f_{k-1})=\Lambda_k(f_{k-1},\dots,f_0)$ となることから従う。$\square$
$N$ を $6$ と互いに素な正の整数とし、$c\in\mathbb{Z}$ を $N$ と互いに素として $q_c(x):=e(cx^2/N)$ とおく。
| 主張 | 外す仮定・形 | 例 | 何が成り立たなくなるか |
|---|---|---|---|
| cor-gn-norm の 3 | $k\ge2$ | $f(x)=e(x/N)$、$k=1$ | $f\ne0$ だが $\Vert f\Vert_{U^1}=0$ |
| thm-gn-von-neumann($k=4$) | $U^{3}$ を $U^2$ に替える | ex-gn-quadratic の $q_1,q_{-3},q_3,q_{-1}$ | $U^2$ ノルムは $N^{-1/4}$ だが $\Lambda_4=1$ |
| thm-gn-von-neumann の後半($k=3$) | $\lvert f_1\rvert\le1$ | $f_0(x)=e(-x^2/N)$、$f_1=N\cdot1_{\{0\}}$、$f_2=q_1$($N$ は奇数) | $\Lambda_3=1$ だが $\Vert f_2\Vert_{U^2}=N^{-1/4}$ |
3 行目:$f_1$ は $0$ でだけ値 $N$ をとるので、$\Lambda_3$ の平均で残るのは $d=-x$ の項で、$\Lambda_3=\frac1{N^2}\sum_xf_0(x)\,N\,f_2(-x)=\mathbb{E}_xe(-x^2/N)e(x^2/N)=1$ である。$\lvert f_0\rvert=\lvert f_2\rvert=1$ なので、外した仮定は $\lvert f_1\rvert\le1$ だけである。$\|f_2\|_{U^2}$ は ex-gn-quadratic の 2 による。証明で $\lvert F_j\rvert\le1$ を使って Cauchy–Schwarz で $F_j$ を消す段が、この仮定なしでは働かない。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する