インテジャーズ

INTEGERS

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

グリーン・タオ論文の§5を読む(その一)

§5 Gowers uniformity norms, and a generalized von Neumann theorem を二回に分けて読みます。この記事ではGowers一様性ノルムの定義を行います。Tao(2006)の方でも既に取り扱っていますが、Gowers内積を用いてGowers一様性ノルムを再定義し、Tao(2006)では省略していた三角不等式を証明します。

定義1 (Definition 5.1) d \geq 1に対して、標準的離散d次元立方体 \{0, 1\}^dを考える。h = (h_1, \dots, h_d) \in \mathbb{Z}_N^d\omega=(\omega_1, \dots, \omega_d) \in \{0, 1\}^dに対して、\omega \cdot h \in \mathbb{Z}_N
\omega \cdot h := \omega_1h_1+\cdots +\omega_dh_d
と定義する。そうして、L^{\infty}(\mathbb{Z}_N)の関数達からなる\{0, 1\}^d-tuple (f_{\omega})_{\omega \in \{0, 1\}^d}に対して、d次元Gowers内積 \langle (f_{\omega})_{\omega \in \{0, 1\}^d}\rangle_{U^d}
\displaystyle \langle (f_{\omega})_{\omega \in \{0, 1\}^d}\rangle_{U^d}:=\left.\mathbb{E}\Biggl(\prod_{\omega \in \{0, 1\}^d}f_{\omega}(x+\omega \cdot h) \ \right| \ x \in \mathbb{Z}_N, h\in \mathbb{Z}_N^d\Biggr)
と定義する。

\{x+\omega\cdot h\mid \omega \in \{0, 1\}^d\}d次元立方体と呼ぶことにします。

例) d=2の場合

\displaystyle \langle f_{00}, f_{10}, f_{01}, f_{11}\rangle_{U^2}=\left.\mathbb{E}(f_{00}(x)f_{10}(x+h_1)f_{01}(x+h_2)f_{11}(x+h_1+h_2) \ \right| \ x, h_1, h_2 \in \mathbb{Z}_N).

補題1 1 \leq i \leq dなる或るiが存在して、(f_{\omega})_{\omega \in \{0,1\}^d}f_{\omega}\omegai成分に依存しないと仮定する。
すなわち、\omega, \omega' \in \{0,1\}^di成分が等しければ、f_{\omega}=f_{\omega'}である。このとき、内積の非負性
\langle (f_{\omega})_{\omega \in \{0, 1\}^d}\rangle_{U^d}\geq 0
が成り立つ。

証明. i=dの場合に証明する(他の場合も同様)。d \geq 2のとき \omega=(\omega_1, \dots, \omega_d), h=(h_1, \dots, h_d)に対して\omega'=(\omega_1, \dots, \omega_{d-1}), h'=(h_1, \dots, h_{d-1})と書くことにすれば、f_{\omega}=f_{\omega'}と書くことができ、Tao(2006) §4のvan der Corputの補題より

\begin{align}\langle(f_{\omega})_{\omega \in \{0, 1\}^d}\rangle_{U^d}
&= \left.\mathbb{E}\Biggl(\prod_{\omega'\in \{0, 1\}^{d-1}}f_{\omega'}(x+\omega'\cdot h')f_{\omega'}(x+\omega'\cdot h'+h_d) \ \right| \ x \in \mathbb{Z}_N, h' \in \mathbb{Z}_N^{d-1}, h_d \in \mathbb{Z}_N\Biggr)\\
&=\left.\mathbb{E}\Biggl( \ \Biggl|\mathbb{E}\Biggl(\prod_{\omega'\in \{0, 1\}^{d-1}}f_{\omega'}(y+\omega'\cdot h') \ \Bigg| \ y \in \mathbb{Z}_N\Biggr)\Biggr|^2 \ \right|  \ h' \in \mathbb{Z}_N^{d-1}\Biggr)\end{align}

と変形できる。これは0以上である。d=1の場合も同様というか、van der Corputの補題の証明における変形そのものとなる。 Q.E.D.

特に、f \in L^{\infty}(\mathbb{Z}_N)に対して \langle (f)_{\omega \in \{0, 1\}^d}\rangle_{U^d} \geq 0である。この非負性から、Gowers内積を用いてGowers一様性ノルムを定義できる。

定義 d \geq 1とする。 f \in L^{\infty}(\mathbb{Z}_N)d-Gowers一様性ノルム \left\|f\right\|_{U^d}
\displaystyle \left\|f\right\|_{U^d} := \langle(f)_{\omega \in \{0, 1\}^d}\rangle_{U^d}^{1/2^d}=\left.\mathbb{E}\Biggl(\prod_{\omega \in \{0, 1\}^d}f(x+\omega \cdot h) \ \right| \ x \in \mathbb{Z}_N, h \in \mathbb{Z}_N^d\Biggr)^{1/2^d}
と定義する。

Tao(2006)で使ったシフト作用素を用いると

\begin{align}\left\|f\right\|_{U^d}^{2^d}
&=\left.\mathbb{E}\Biggl(\mathbb{E}\Biggl(\prod_{\omega' \in \{0, 1\}^{d-1}}f(x+\omega'\cdot h')f(x+\omega' \cdot h'+h) \ \Bigg| \ x \in \mathbb{Z}_N, h' \in \mathbb{Z}_N^{d-1}\Biggr) \ \right| \ h \in \mathbb{Z}_N\Biggr)\\
&=\left.\mathbb{E}\left(\left\|fT^hf\right\|_{U^{d-1}}^{2^{d-1}} \ \right| \ h \in \mathbb{Z}_N\right)\end{align}

と書けるので、Tao(2006)で扱ったGowers一様性ノルムと同じものであることがわかります(こちらの論文では実数値関数しか考えていませんが)。

Gowers内積に対して成り立つ、次のCauchy-Schwarz型不等式は強力です:

命題1 (GowersのCauchy-Schwarz不等式=GCS不等式) d \geq 1とする。任意の(f_{\omega})_{\omega \in \{0, 1\}^d}に対して、不等式
\displaystyle \left|\langle (f_{\omega})_{\omega \in \{0, 1\}^d}\rangle_{U^d}\right| \leq \prod_{\omega \in \{0, 1\}^d}\left\|f_{\omega}\right\|_{U^d}
が成り立つ。

証明. 補題1と同様の計算を行うと(d=1のときは若干記述を変える必要があるが同様)、

\begin{align}&\langle(f_{\omega})_{\omega \in \{0, 1\}^d}\rangle_{U^d} \\
&= \left.\mathbb{E}\Biggl(\prod_{\omega'\in \{0, 1\}^{d-1}}f_{\omega', 0}(x+\omega'\cdot h')f_{\omega', 1}(x+\omega'\cdot h'+h_d) \ \right| \ x \in \mathbb{Z}_N, h' \in \mathbb{Z}_N^{d-1}, h_d \in \mathbb{Z}_N\Biggr)\\
&=\mathbb{E}\Biggl( \mathbb{E}\Biggl(\prod_{\omega'\in \{0, 1\}^{d-1}}f_{\omega', 0}(y+\omega'\cdot h') \ \Bigg| \ y \in \mathbb{Z}_N\Biggr) \\ &\quad \quad \quad \times \left.\mathbb{E}\Biggl(\prod_{\omega'\in \{0, 1\}^{d-1}}f_{\omega', 1}(y+\omega'\cdot h') \ \Bigg| \ y \in \mathbb{Z}_N\Biggr) \ \right| h' \in \mathbb{Z}_N^{d-1}\Biggr)\end{align}

を得る。h'についてCauchy-Schwartzの不等式を適用すると

\begin{align}& \ \Bigg|\mathbb{E}\Biggl( \mathbb{E}\Biggl(\prod_{\omega'\in \{0, 1\}^{d-1}}f_{\omega', 0}(y+\omega'\cdot h') \ \Bigg| \ y \in \mathbb{Z}_N\Biggr) \\
&\quad \quad \quad \times \left.\mathbb{E}\Biggl(\prod_{\omega'\in \{0, 1\}^{d-1}}f_{\omega', 1}(y+\omega'\cdot h') \ \Bigg| \ y \in \mathbb{Z}_N\Biggr) \ \right| h' \in \mathbb{Z}_N^{d-1}\Biggr)\Bigg| \\
&\leq \sqrt{\left.\mathbb{E}\Biggl( \ \Bigg| \mathbb{E}\Biggl(\prod_{\omega' \in \{0, 1\}^{d-1}}f_{\omega', 0}(y+\omega'\cdot h') \ \Bigg| \ y \in \mathbb{Z}_N\Biggr) \Bigg|^2 \ \right| h' \in \mathbb{Z}_N^{d-1}\Biggr)} \\ 
&\quad \quad \times \sqrt{\left.\mathbb{E}\Biggl( \ \Bigg| \mathbb{E}\Biggl(\prod_{\omega' \in \{0, 1\}^{d-1}}f_{\omega', 1}(y+\omega'\cdot h') \ \Bigg| \ y \in \mathbb{Z}_N\Biggr) \Bigg|^2 \ \right| h' \in \mathbb{Z}_N^{d-1}\Biggr)}\end{align}

となるが、最後の二つのルートの中にある期待値に対して補題1の証明の式の逆向きの変形を行えば、

\displaystyle \left|\langle(f_{\omega})_{\omega \in \{0, 1\}^d}\rangle_{U^d}\right| \leq \langle(f_{\omega', 0})_{\omega \in \{0, 1\}^d}\rangle_{U^d}^{1/2}\times \langle(f_{\omega', 1})_{\omega \in \{0, 1\}^d}\rangle_{U^d}^{1/2}

が得られたことになる。d=1ならば、これはGCS不等式を与えている。d \geq 2のときは、\omega'':=(\omega_1, \dots, \omega_{d-2})として、一般に

\displaystyle \left|\langle(f_{\omega})_{\omega \in \{0, 1\}^d}\rangle_{U^d}\right| \leq \langle(f_{\omega'', 0, \omega_d})_{\omega \in \{0, 1\}^d}\rangle_{U^d}^{1/2}\times \langle(f_{\omega'', 1, \omega_d})_{\omega \in \{0, 1\}^d}\rangle_{U^d}^{1/2}

が成り立つことを同様に示すことができるので(d=2のときは若干記述が異なる)、特に

\displaystyle \langle(f_{\omega', 0})_{\omega \in \{0, 1\}^d}\rangle_{U^d} \leq \langle (f_{\omega'', 0, 0})_{\omega \in \{0, 1\}^d}\rangle^{1/2} \times \langle (f_{\omega'', 1, 0})_{\omega \in \{0, 1\}^d}\rangle^{1/2}

及び

\displaystyle \langle(f_{\omega', 1})_{\omega \in \{0, 1\}^d}\rangle_{U^d} \leq \langle (f_{\omega'', 0, 1})_{\omega \in \{0, 1\}^d}\rangle^{1/2} \times \langle (f_{\omega'', 1, 1})_{\omega \in \{0, 1\}^d}\rangle^{1/2}

が成り立ち、先ほどの不等式と組み合わせることにより

\begin{align}&\left|\langle(f_{\omega})_{\omega \in \{0, 1\}^d}\rangle_{U^d}\right| \\ &\leq \langle (f_{\omega'', 0, 0})_{\omega \in \{0, 1\}^d}\rangle^{1/4} \times \langle (f_{\omega'', 1, 0})_{\omega \in \{0, 1\}^d}\rangle^{1/4}\times \langle (f_{\omega'', 0, 1})_{\omega \in \{0, 1\}^d}\rangle^{1/4} \times \langle (f_{\omega'', 1, 1})_{\omega \in \{0, 1\}^d}\rangle^{1/4}\end{align}

と評価できる。この議論を繰り返していけば、最終的には任意の\eta \in \{0, 1\}^dに対して

\displaystyle \langle(f_{\eta})_{\omega \in \{0, 1\}^d}\rangle_{U^d}^{1/2^d}=\left\|f_{\eta}\right\|_{U^d}

が現れ、GCS不等式の証明が完了する。 Q.E.D.

GCS不等式を用いればTao(2006)では省略したGowers一様性ノルムの三角不等式を証明できるだけでなく、他の性質についても別証明を与えることができます。

補題2 d\geq 2のとき、任意の f \in L^{\infty}(\mathbb{Z}_N)に対して
\displaystyle \left\|f\right\|_{U^{d-1}} \leq \left\|f\right\|_{U^d}
が成り立つ。

証明. \left\|\nu_{\text{const}}\right\|_{U^d}=\left\|1\right\|_{U^d}=1なので

\displaystyle f_{\omega}:=\begin{cases} 1 & (\omega_d=1) \\ f & (\omega_d=0)\end{cases}

とすると、GCS不等式より

\displaystyle \left| \langle (f_{\omega})_{\omega \in \{0, 1\}^d}\rangle_{U^d}\right| \leq \left\|f\right\|_{U^d}^{2^{d-1}}

が得られる。一方、

\begin{align} \langle (f_{\omega})_{\omega \in \{0, 1\}^d}\rangle_{U^d} &= \left.\mathbb{E}\Biggl( \prod_{\omega' \in \{0, 1\}^{d-1}}f(x+\omega'\cdot h') \ \right| \ x \in \mathbb{Z}_N, h \in \mathbb{Z}_N^d \Biggr) \\
&=\left.\mathbb{E}\Biggl( \prod_{\omega' \in \{0, 1\}^{d-1}}f(x+\omega'\cdot h') \ \right| \ x \in \mathbb{Z}_N, h' \in \mathbb{Z}_N^{d-1} \Biggr) = \left\|f\right\|_{U^{d-1}}^{2^{d-1}}\end{align}

なので、\left\|f \right\|_{U^{d-1}} \leq \left\|f\right\|_{U^d}が示された。 Q.E.D.

命題2 d \geq 1に対して \left\|\cdot \right\|_{U^d}は半ノルム(非負性・斉次性・三角不等式を満たす)であり、d \geq 2であればノルム(半ノルム+非退化性)である。

証明. 非負性・斉次性は定義から明らか。

三角不等式: f, g \in L^{\infty}(\mathbb{Z}_N)を任意にとる。Gowers内積は定義から多重線形性をもつので、GCS不等式より

\begin{align} \langle (f+g)_{\omega \in \{0, 1\}^d}\rangle_{U^d} &= \sum_{(f_{\omega})_{\omega \in \{0, 1\}^d} \in \{f, g\}^{2^d}}\langle (f_{\omega})_{\omega \in \{0, 1\}^d}\rangle_{U^d} \\ &\leq \sum_{(f_{\omega})_{\omega \in \{0, 1\}^d} \in \{f, g\}^{2^d}}\prod_{\omega \in \{0, 1\}^d}\left\|f_{\omega}\right\|_{U^d} \\ &= \left(\left\|f\right\|_{U^d}+\left\|g\right\|_{U^d}\right)^{2^d}\end{align}

と評価できる。よって、

\displaystyle \left\|f+g\right\|_{U^d}= \langle (f+g)_{\omega \in \{0, 1\}^d}\rangle_{U^d}^{1/2^d} \leq \left\|f\right\|_{U^d}+\left\|g\right\|_{U^d}

が成り立つ。

非退化性: 補題2によって d=2の場合に帰着される。d=2の場合のGCS不等式は一般に

\begin{align} &\left|\left.\mathbb{E}(f_{00}(x)f_{10}(x+h_1)f_{01}(x+h_2)f_{11}(x+h_1+h_2) \ \right| \ x, h_1, h_2 \in \mathbb{Z}_N)\right| \\
&\leq \left\|f_{00}\right\|_{U^2}\left\|f_{10}\right\|_{U^2}\left\|f_{01}\right\|_{U^2}\left\|f_{11}\right\|_{U^2}\end{align}

という形をしているので、f_{00}=fとおいて \left\|f\right\|_{U^2}=0と仮定すると、任意の関数 f_{10}, f_{01}, f_{11}に対して

\displaystyle \left.\mathbb{E}\left( f(x) \left.\mathbb{E} ( f_{10}(x+h_1)f_{01}(x+h_2)f_{11}(x+h_1+h_2) \ \right| \ h_1, h_2 \in \mathbb{Z}_N) \right| x \in \mathbb{Z}_N \right) = 0 −①

が成り立つ。この式を用いて、任意のa \in \mathbb{Z}_Nに対して f(a)=0を示せばよい。a \in \mathbb{Z}_Nを固定する。関数 f_a

\displaystyle f_a(x) := \begin{cases}1 & (x=a) \\ 0 & (x \neq a)\end{cases}

と定義して f_{10}=f_{01}=f_{11}=f_a とする。このとき、

a+h_1=a+h_2=a+h_1+h_2=a \Longleftrightarrow h_1=h_2=0

なので

\displaystyle \left.\mathbb{E}(f_a(a+h_1)f_a(a+h_2)f_a(a+h_1+h_2) \ \right| \ h_1, h_2 \in \mathbb{Z}_N) = \frac{1}{N^2}

であり、x \neq aなる x \in \mathbb{Z}_Nに対しては

x+h_1=x+h_2=x+h_1+h_2=a

とはなり得ないことから

\displaystyle \left.\mathbb{E}(f_a(x+h_1)f_a(x+h_2)f_a(x+h_1+h_2) \ \right| \ h_1, h_2 \in \mathbb{Z}_N) = 0

である。よって、①より f(a) = 0が従う。 Q.E.D.

補題3 \nuk-擬ランダム測度とする。このとき、任意の1 \leq d \leq k-1に対して
\left\|\nu-\nu_{\text{const}}\right\|_{U^d} = o(1)
が成り立つ。

証明. 補題2より、d=k-1のときに証明すればよい。また、\left\|\cdot \right\|_{U^d}の定義より 2^{k-1}乗した

\displaystyle \left.\mathbb{E}\Biggl( \prod_{\omega \in \{0, 1\}^{k-1}}(\nu(x+\omega \cdot h)-1) \ \right| \ x \in \mathbb{Z}_N, h \in \mathbb{Z}_N^{k-1}\Biggr) = o(1)

を示せばよい(o(1)k依存してよいことに注意)。この左辺は

\begin{align}&\left.\mathbb{E}\Biggl( \prod_{\omega \in \{0, 1\}^{k-1}}(\nu(x+\omega \cdot h)-1) \ \right| \ x \in \mathbb{Z}_N, h \in \mathbb{Z}_N^{k-1}\Biggr) \\ &= \sum_{A \subset \{0, 1\}^{k-1}}(-1)^{\#A}\left.\mathbb{E}\Biggl( \prod_{\omega \in A}\nu(x+\omega \cdot h) \ \right| \ x \in \mathbb{Z}_N, h \in \mathbb{Z}_N^{k-1}\Biggr)\end{align}

と展開できるので、部分集合 A \subset \{0, 1\}^{k-1}に対して

\displaystyle \left.\mathbb{E}\Biggl( \prod_{\omega \in A}\nu(x+\omega \cdot h) \ \right| \ x \in \mathbb{Z}_N, h \in \mathbb{Z}_N^{k-1}\Biggr)

を考える(A=\emptysetの場合はこの期待値は1)。これは、(\#A, k, 1)-線形形式条件が使える形である: 変数はx, h_1, \dots, h_{k-1}、線形形式は\omega \in Aに対するx+\omega \cdot hを考える。係数の作るベクトルに対する一次独立性条件は\omega \in A毎に0の場所が異なることからわかる。

よって、上記期待値は1+o(1)であり、Aを動かすと

\displaystyle \sum_{A \subset \{0, 1\}^{k-1}}(-1)^{\#A}(1+o(1))=\sum_{A \subset \{0, 1\}^{k-1}}(-1)^{\#A}+o(1)=(1-1)^{2^{k-1}}+o(1)=o(1)

となる。 Q.E.D.