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

§3 Overview of proof では証明のスキーム

或る $A$ という対象がある。
$A$ には或るランダム性と構造という概念を定義することができる。
$A$ を(構造化部分)+(誤差項)に分ける構造定理を示す。誤差項はランダムな部分。
誤差項を取り除く一般化von Neumann定理及び構造化部分に関する構造化回帰定理を証明する*1。

に従って、主定理(Theorem 2.4)を三つの定理(Thm 3.1, Thm 3.3, Thm 3.5)に分離します。

ランダム性と構造

非負値有界関数 $f \colon \mathbb{Z}_N \to \mathbb{R}^+$ のランダム性と構造は二種類のノルムの族によって定めます*2。

Gowers一様性ノルム族 (ランダム性を定めるノルム族. §4で定義される)

$\left\|f\right\|_{U^0} \leq \left\|f\right\|_{U^1} \leq \cdots \leq \left\|f\right\|_{U^{k-1}} \leq \cdots \leq \left\|f\right\|_{L^{\infty}}$

一様概周期性ノルム族 (構造を定めるノルム族. §5で定義される)

$\left\|f\right\|_{UAP^0} \geq \left\|f\right\|_{UAP^1} \geq \cdots \geq \left\|f\right\|_{UAP^{k-2}} \geq \cdots \geq \left\|f\right\|_{L^{\infty}}$

三つの定理

最初の定理はGowers一様性ノルムが小さい部分は無視できることを主張するものです：

一般化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}}$

が成り立つ。

次の定理は構造化回帰定理です：

一様概周期関数の回帰性 (Theorem 3.3) $d \geq 0, k\geq 1$ を整数とする。非負値有界関数 $f_{U^{\perp}}, f_{UAP}$ は或る $0 < \delta \leq 1, \ M > 0$ に対して

1. $\displaystyle \ \left\| f_{U^{\perp}}-f_{UAP} \right\|_{L^2} \leq \frac{\delta^2}{1024k},\quad$ 2. $\displaystyle \ \int_{\mathbb{Z}_N}f_{U^{\perp}} \geq \delta,\quad$ 3. $\displaystyle \ \left\|f_{UAP}\right\|_{UAP^d} < M$

を満たすと仮定する。このとき、任意の $\mu \in \mathbb{Z}_N$ 及び正整数 $N_1$ に対して

$\displaystyle \mathbb{E}_{0 \leq r \leq N_1}\left( \int_{\mathbb{Z}_N}\prod_{j=0}^{k-1}T^{\mu jr}f_{U^{\perp}}\right) \gg_{d, k, \delta, M} 1$

が成り立つ。

この定理の証明が一番難しい部分で、Furstenberg等の議論とvan der Waerdenの定理を使います。 $\mu, N_1$ は帰納法を回すためのパラメータで $\mu = 1, N_1=N-1$ として適用します。

最後に構造定理です*3：

構造定理 (Theorem 3.5) $k \geq 3$ を整数とし、非負値有界関数 $f\colon \mathbb{Z}_N \to \mathbb{R}^+$ は或る $0 < \delta \leq 1$ に対して

$\displaystyle \int_{\mathbb{Z}_N}f \geq \delta$

を満たすと仮定する。更に $F \colon \mathbb{R}^+ \to \mathbb{R}^+$ を任意の関数とする。このとき、或る正の数 $M=O_{k, \delta, F}(1), \$ 有界関数 $f_U \colon \mathbb{Z}_N \to \mathbb{C}, \$ 非負値有界関数 $f_{U^{\perp}}, \ f_{UAP} \colon \mathbb{Z}_N \to \mathbb{R}^+$ が存在して

1. $\ f=f_U+f_{U^{\perp}},\quad$ 2. Thm 3.3の条件1. 2. 3. が $d=k-2$ で成立 $,\quad$ 3. $\displaystyle \ \left\|f_U\right\|_{U^{k-1}} \leq \frac{1}{F(M)}$

が成り立つ。

この定理はFurstenbergの構造定理とSzemerédi正則化補題のハイブリッドになっているとのことです。それでは、主定理をこれら三つの定理に帰着しましょう。

(再掲) 主定理 (定量的回帰定理, Theorem 2.4) $k \geq 3$ を任意の整数、 $\delta$ を $0 < \delta \leq 1$ を満たす任意の整数とする。このとき、次が成立する：条件

$\displaystyle \int_{\mathbb{Z}_N}f \geq \delta$

を満たす任意の非負値有界関数 $f \colon \mathbb{Z}_N \to \mathbb{R}^+$ に対して

$\displaystyle \mathbb{E}_{r \in \mathbb{Z}_N} \left( \int_{\mathbb{Z}_N}\prod_{j=0}^{k-1}T^{jr}f \right) \gg_{k, \delta} 1$

が成り立つ。

Thm 3.1, Thm 3.3, Thm 3.5 $\Longrightarrow$ Thm 2.4の証明

$k, \delta, f$ をThm 2.4のものとする。また、 $d=k-2$ のときにThm 3.3の結論の不等式の左辺が正定数 $c(k, \delta, M)$ で下から押さえられているものとする。 $F \colon \mathbb{R}^+ \to \mathbb{R}^+$ として任意の $M > 0$ に対して

$\displaystyle F(M) > \frac{2^k-1}{c(k, \delta, M)}$

を満たすものを一つ選ぶ*4。この設定に対してThm 3.5で存在する $M=O_{k, \delta}(1), \ f_U, \ f_{U^{\perp}}, \ f_{UAP}$ を取る*5。このとき、

$\begin{align} \mathbb{E}_{r \in \mathbb{Z}_N} \left( \int_{\mathbb{Z}_N}\prod_{j=0}^{k-1}T^{jr}f \right) &= \mathbb{E}_{r \in \mathbb{Z}_N} \left( \int_{\mathbb{Z}_N}\prod_{j=0}^{k-1}T^{jr}(f_U+f_{U^{\perp}}) \right) \\ &= \sum_{(f_0, \dots, f_{k-1}) \in \{f_U, f_{U^{\perp}}\}^k}\mathbb{E}_{r \in \mathbb{Z}_N}\left( \int_{\mathbb{Z}_N}\prod_{j=0}^{k-1}T^{jr}f_j \right)\end{align}$

と展開できる。最後の和の $f_0=\cdots = f_{k-1} = f_{U^{\perp}}$ なる項はThm 3.3の $\mu=1, N_1=N-1$ の場合によって下から $c(k, \delta, M)$ でおさえられる。

残りの $2^k-1$ 項についてはそれぞれ少なくとも一つ $f_U$ を含むので、Thm 3.1よりどの項も絶対値が $1/F(M)$ で上から押さえらえる。すなわち、

$\displaystyle \mathbb{E}_{r \in \mathbb{Z}_N} \left( \int_{\mathbb{Z}_N}\prod_{j=0}^{k-1}T^{jr}f \right) \geq c(k, \delta, M)-\frac{2^k-1}{F(M)},\quad \mathbb{E}_{r \in \mathbb{Z}_N} \left( \int_{\mathbb{Z}_N}\prod_{j=0}^{k-1}T^{jr}f \right) \gg_{k, \delta, M} 1$