インテジャーズ

INTEGERS

数、特に整数に関する記事。

タオのセメレディ論文の§4を読む

§4 Uniformity norms, and the generalized von Neumann theorem ではGowers一様性ノルムを定義して一般化von Neumann定理(Thm 3.1)を証明します。

van der Corputの補題 任意の関数 f \in \mathrm{Map}(\mathbb{Z}_N, \mathbb{C}) に対して
\displaystyle \Bigg| \int_{\mathbb{Z}_N}f\Bigg|^2 = \mathbb{E}_{h \in \mathbb{Z}_N}\left( \int_{\mathbb{Z}_N}\overline{f}T^hf\right)
が成り立つ。

証明. 左辺は

\displaystyle \mathbb{E}_{x, y \in \mathbb{Z}_N}(\overline{f(x)}f(y))

であり、右辺は

\displaystyle \mathbb{E}_{x, h \in \mathbb{Z}_N}(\overline{f(x)}f(x+h))

なので、x+h \mapsto yとすることにより両者が一致することがわかる。 Q.E.D.

Gowers一様性ノルムの定義 (Definition 4.2.)
関数 f \in \mathrm{Map}(\mathbb{Z}_N, \mathbb{C}) に対してd-Gowers一様性ノルム\left\|f\right\|_{U^d}を次のようにして帰納的に定める:

  1. \displaystyle \left\|f\right\|_{U^0} := \int_{\mathbb{Z}_N}f,
  2. \displaystyle \left\|f\right\|_{U^d} := \left( \mathbb{E}_{h \in \mathbb{Z}_N} \left( \left\|\overline{f}T^hf\right\|_{U^{d-1}}^{2^{d-1}} \right) \right)^{\frac{1}{2^d}}.

\left\|f\right\|_{U^1}は次のような明示的表示を持ちます:

基本性質1 (Example 4.3) \ \ \ \displaystyle \left\|f\right\|_{U^1}=\left| \int_{\mathbb{Z}_N}f \right|.

証明. 定義式とvan der Corputの補題より

\displaystyle  \left\|f\right\|_{U^1} = \sqrt{\mathbb{E}_{h \in \mathbb{Z}_N}\left( \left\| \overline{f}T^hf \right\|_{U^0} \right)}
= \sqrt{\mathbb{E}_{h \in \mathbb{Z}_N}\left( \int_{\mathbb{Z}_N}\overline{f}T^hf \right)}
= \left| \int_{\mathbb{Z}_N}f \right|

と計算できる。 Q.E.D.

よって、d \geq 1ならばd-Gowers一様性ノルムは非負値を取ることがわかります。

基本性質2 (Remark 4.4) d \geq 1に対して \left\|f\right\|_{U^d} \leq \left\|f\right\|_{U^{d+1}} が成り立つ ( fが実数値ならd \geq 0)。

証明. dに関する帰納法で証明する。d-1のときに成立すると仮定すると

\displaystyle \left\|f\right\|_{U^d} = \left( \mathbb{E}_{h \in \mathbb{Z}_N} \left( \left\|\overline{f}T^hf\right\|_{U^{d-1}}^{2^{d-1}} \right) \right)^{\frac{1}{2^d}} \leq \left( \mathbb{E}_{h \in \mathbb{Z}_N} \left( \left\|\overline{f}T^hf\right\|_{U^{d}}^{2^{d-1}} \right) \right)^{\frac{1}{2^d}} −①

なので、示すべきことは

\displaystyle \left( \mathbb{E}_{h \in \mathbb{Z}_N} \left( \left\|\overline{f}T^hf\right\|_{U^{d}}^{2^{d-1}} \right) \right)^2 \leq  \mathbb{E}_{h \in \mathbb{Z}_N} \left( \left\|\overline{f}T^hf\right\|_{U^{d}}^{2^{d}} \right)

である。これはCauchy-Schwarzの不等式から従う。d=1のときも基本事項1より1-Gowers一様性ノルムは非負値なので、三角不等式によって①が成立している。 Q.E.D.

注意: \left\| \cdot \right\|_{U^d}d \geq 2のときに実際にノルム性質を満たすことが知られています。あとで使う非退化性

\left\|f\right\|_{U^d} = 0 \Longleftrightarrow f=0


のみ示しておきます。

証明. 基本性質2によって、d=2のときに示せば十分。\left\|f\right\|_{U^2}=0と仮定すると、定義と基本性質1によって任意のh \in \mathbb{Z}_Nに対して

\displaystyle \left\|\overline{f}T^hf\right\|_{U^1} = \left| \int_{\mathbb{Z}_N}\overline{f}T^hf\right| = 0

である。特に、h=0の場合を考えることによって

\displaystyle \int_{\mathbb{Z}_N}\overline{f}f = \int_{\mathbb{Z}_N}\left|f\right|^2=0

であり、これは f=0を示している。 Q.E.D.

基本性質3 (Example 4.5) d \geq 1に対して \left\|f\right\|_{U^d} \leq \left\|f\right\|_{L^{\infty}} が成り立つ ( fが実数値ならd \geq 0)。

証明. dに関する帰納法で示す。基本性質1と三角不等式により

\displaystyle \left\|f\right\|_{U^1} \leq \int_{\mathbb{Z}_N}\left|f\right| \leq \sup_{x \in \mathbb{Z}_N}\left|f(x) \right|=\left\|f\right\|_{L^{\infty}}

d=1の場合に成立することがわかる。d-1で成立すると仮定すると、

\displaystyle \left\|f\right\|_{U^d} \leq \left( \mathbb{E}_{h \in \mathbb{Z}_N}\left( \left\|\overline{f}T^hf\right\|_{L^{\infty}}^{2^{d-1}}\right)\right)^{\frac{1}{2^d}} \leq \left( \mathbb{E}_{h \in \mathbb{Z}_N}\left( \left\|f\right\|_{L^{\infty}}^{2^{d}}\right)\right)^{\frac{1}{2^d}} = \left\|f\right\|_{L^{\infty}}

dのときも成立することがわかる。 Q.E.D.

よって、fが有界であれば \left\|f\right\|_{U^d} \leq 1 であることがわかります。

基本性質4 (シフト不変性) 任意の n \in \mathbb{Z}_N, d \geq 0 に対して \left\|T^nf\right\|_{U^d} = \left\|f \right\|_{U^d} が成り立つ。

証明. d=0の場合は積分のシフト不変性より従う。一般の場合は

\displaystyle \overline{T^nf}T^hT^nf = T^n\left( \overline{f}T^hf\right)

に注意して帰納法。 Q.E.D.

基本性質5 (複素共役不変性) d \geq 1であれば、\left\|\overline{f}\right\|_{U^d}=\left\|f\right\|_{U^d} が成立する。

証明. d=1のときは基本性質1より成立することがわかる。一般の場合は帰納法。 Q.E.D.

基本性質6 (スケール不変性) 関数 f \in \mathrm{Map}(\mathbb{Z}_N, \mathbb{C})\lambda \in \mathbb{Z}_N \setminus \{0\} に対して f_{\lambda} \in \mathrm{Map}(\mathbb{Z}_N, \mathbb{C})f_{\lambda}(x):=f(x/\lambda) で定義する。このとき、\left\|f_{\lambda}\right\|_{U^d} = \left\|f\right\|_{U^d} が任意の d \geq 0 に対して成立する。

Nが素数なので、\lambdaの逆元が存在することに注意します。

証明. 基本的には\mathbb{Z}_Nにおける\lambda^{-1}倍写像が全単射であることから従うが、帰納法のステップにおいて

\displaystyle \overline{f_{\lambda}}T^hf_{\lambda}(x) = \overline{f\left( \frac{x}{\lambda} \right)} f\left( \frac{x+h}{\lambda} \right) = \overline{f\left( \frac{x}{\lambda}\right)}f\left( \frac{x}{\lambda}+\lambda^{-1}h\right) = \left( \overline{f}T^{\lambda^{-1}h}f\right)_{\lambda}(x)

が成り立つことを使う。 Q.E.D.

補題 \lambda_0, \lambda_1 \in \mathbb{Z}_Nは相異なる元であるとする。このとき、写像
\begin{align}&\mathbb{Z}_N^2 \longrightarrow \mathbb{Z}_N^2 \\ &(x, r)\mapsto (x+\lambda_0r, x+\lambda_1r)\end{align}
は全単射である。

証明. 任意の(y, s) \in \mathbb{Z}_N^2に対して連立方程式 x+\lambda_0r=y, x+\lambda_1r=sが解(x, r) \in \mathbb{Z}_N^2を一意的に持てばよい。これは、\left(\begin{smallmatrix} 1 & \lambda_0 \\ 1 & \lambda_1\end{smallmatrix}\right)の行列式 \lambda_1-\lambda_00でないことからわかる。 Q.E.D.

それでは一般化von Neumann定理を証明しましょう。

(再掲) 一般化von Neumann定理 (Theorem 3.1) k\geq 2を整数、\lambda_0, \dots, \lambda_{k-1}を相異なる\mathbb{Z}_Nの元とする。このとき、任意の有界関数 f_0, \dots, f_{k-1}\colon \mathbb{Z}_N \to \mathbb{C}に対して
\displaystyle \left| \mathbb{E}_{r \in \mathbb{Z}_N} \left( \int_{\mathbb{Z}_N} \prod_{j=0}^{k-1}T^{\lambda_jr}f_j \right) \right| \leq \min_{0 \leq j \leq k-1}\left\|f_j\right\|_{U^{k-1}}
が成り立つ。

証明. kに関する帰納法で証明する。k=2の場合、補題より

\begin{align} \mathbb{E}_{r \in \mathbb{Z}_N}\left( \int_{\mathbb{Z}_N}T^{\lambda_0 r}f_0T^{\lambda_1r}f_1\right) &= \mathbb{E}_{(x, r) \in \mathbb{Z}_N^2}\left(f_0(x+\lambda_0r)f_1(x+\lambda_1r)\right) \\ &= \mathbb{E}_{(x, r) \in \mathbb{Z}_N^2}\left( f_0(x)f_1(r)\right) = \left( \int_{\mathbb{Z}_N}f_0\right) \times \left( \int_{\mathbb{Z}_N}f_1 \right) \end{align}

なので、基本事項1より

\displaystyle \left| \mathbb{E}_{r \in \mathbb{Z}_N}\left(\int_{\mathbb{Z}_N}T^{\lambda_0r}f_0T^{\lambda_1r}f_1 \right) \right| = \left\|f_0\right\|_{U^1}\times \left\|f_1\right\|_{U^1} \leq \min\left\{\left\|f_0\right\|_{U^1}, \left\|f_1\right\|_{U^1}\right\}

を得る(最後の不等号には f_0, f_1が有界であることを用いる)。これでk=2の場合に示されたので、k > 2としてk-1で成立すると仮定する。番号を適当に入れ替えることにより

\displaystyle \min_{0 \leq j \leq k-1}\left\|f_j\right\|_{U^{k-1}}=\left\|f_0\right\|_{U^{k-1}}

であると仮定してよい。積分のシフト不変性とシフト作用素の基本性質によりT^{-\lambda_{k-1}r}を考えることによって\lambda_{k-1}=0と仮定しても一般性を失わない。このとき、\lambda_0\neq 0であり、\mathbb{E}_{r \in \mathbb{Z}_N}の足す順番を全単射 \times \lambda_0^{-1} \colon \mathbb{Z}_N \to \mathbb{Z}_N で入れ替えることによって \lambda_0=1 であると仮定してもよい(入れ替えた際、\lambda_0^{-1}\lambda_1\mapsto \lambda_1, \dots, \lambda_0^{-1}\lambda_{k-2}\mapsto \lambda_{k-2}と置き換えれば仮定はちゃんと満たされている)。よって、示すべきことは

\displaystyle \left| \int_{\mathbb{Z}_N}f_{k-1}\mathbb{E}_{r \in \mathbb{Z}_N}\left(\prod_{j=0}^{k-2}T^{\lambda_jr}f_j\right)\right| \leq \left\|f_0\right\|_{U^{k-1}}

である。ここで、和の順序を入れ替えてf_{k-1}でくくっていることに注意。期待値はx\in \mathbb{Z}_N毎に計算される*1。更に、Cauchy-Schwarzの不等式より

\displaystyle \left|\int_{\mathbb{Z}_N}f_{k-1}\mathbb{E}_{r \in \mathbb{Z}_N}\left(\prod_{j=0}^{k-2}T^{\lambda_jr}f_j\right)\right|^2 \leq \int_{\mathbb{Z}_N}\left|f_{k-1}\mathbb{E}_{r \in \mathbb{Z}_N}\left(\prod_{j=0}^{k-2}T^{\lambda_jr}f_j\right)\right|^2

なので、f_{k-1}の有界性より結局

\displaystyle \int_{\mathbb{Z}_N}\left| \mathbb{E}_{r \in \mathbb{Z}_N}\left( \prod_{j=0}^{k-2}T^{\lambda_jr}f_j\right)\right|^2 \leq \left\|f_0\right\|^2_{U^{k-1}} −②

を示せばよい。x \in \mathbb{Z}_Nを固定するとき、van der Corputの補題(変数r\in \mathbb{Z}_Nに対して適用)とシフト作用素の基本性質より

\begin{align}\left| \mathbb{E}_{r \in \mathbb{Z}_N}\left( \prod_{j=0}^{k-2}T^{\lambda_jr}f_j(x)\right)\right|^2 &= \mathbb{E}_{h, r \in \mathbb{Z}_N} \Biggl(\Biggl( \overline{\prod_{j=0}^{k-2}T^{\lambda_jr}f_j(x)} \Biggr)T^h\left(\prod_{j=0}^{k-2}T^{\lambda_jr}f_j(x)\right) \Biggr) \\
&= \mathbb{E}_{h, r \in \mathbb{Z}_N} \left(\left( \prod_{j=0}^{k-2}T^{\lambda_jr}\overline{f_j}(x) \right)\left(\prod_{j=0}^{k-2}T^{\lambda_j(r+h)}f_j(x)\right) \right)\\
&= \mathbb{E}_{h, r \in \mathbb{Z}_N}\left( \prod_{j=0}^{k-2}T^{\lambda_jr}(\overline{f_j}T^{\lambda_jh}f_j(x))\right)\end{align}

と計算できるので、和の入れ替えにより

\displaystyle \int_{\mathbb{Z}_N}\left| \mathbb{E}_{r \in \mathbb{Z}_N}\left( \prod_{j=0}^{k-2}T^{\lambda_jr}f_j\right)\right|^2= \mathbb{E}_{h \in \mathbb{Z}_N}\left(\mathbb{E}_{r \in \mathbb{Z}_N} \left( \int_{\mathbb{Z}_N}\prod_{j=0}^{k-2}T^{\lambda_jr}(\overline{f_j}T^{\lambda_jh}f_j)\right)\right)

を得る。h \in \mathbb{Z}_N, j=0, \dots, k-2に対して\overline{f_j}T^{\lambda_jh}f_jは有界なので、帰納法の仮定により

\displaystyle \left| \mathbb{E}_{r \in \mathbb{Z}_N}\left(\int_{\mathbb{Z}_N}\prod_{j=0}^{k-2}T^{\lambda_jr}(\overline{f_j}T^{\lambda_jh}f_j)\right) \right| \leq \left\|\overline{f_0}T^hf_0 \right\|_{U^{k-2}}

が任意のh \in \mathbb{Z}_Nに対して成立する(\lambda_0=1であった)。従って、三角不等式より

\displaystyle \int_{\mathbb{Z}_N}\left| \mathbb{E}_{r \in \mathbb{Z}_N}\left( \prod_{j=0}^{k-2}T^{\lambda_jr}f_j\right)\right|^2 \leq \mathbb{E}_{h \in \mathbb{Z}_N}\left( \left\|\overline{f_0}T^hf_0\right\|_{U^{k-2}} \right)

となり、Gowers一様性ノルムの定義によって②は

\displaystyle \left( \mathbb{E}_{h \in \mathbb{Z}_N}\left( \left\|\overline{f_0}T^hf_0\right\|_{U^{k-2}} \right) \right)^{2^{k-2}} \leq \mathbb{E}_{h \in \mathbb{Z}_N}\left( \left\|\overline{f_0}T^hf_0\right\|_{U^{k-2}}^{2^{k-2}} \right)

に帰着される。これはHölderの不等式*2の特殊なケースに他ならない(或いはCauchy-Schwarzの不等式の繰り返し)。 Q.E.D.

*1:f_{k-1}でくくるための作業。今後、点毎に期待値を返す関数としての表記を断りなく使う。

*2:よく知られたHölderの不等式より、fが非負値でq > 0であれば、適当な有限集合X上で

\mathbb{E}_X(f^q) \geq \left( \mathbb{E}_X(f)\right)^q
が成り立つ。