2017-09-14

タオのセメレディ論文の§1, 2を読む

この記事から

T. Tao, A quantitative ergodic theory proof of Szemerédi’s theorem, The electronic Journal of Combinatorics 13, (2006), 1−49.

を読んでいきます。

integers.hatenablog.com

Szemerédiの定理の証明のスキーム*1を常に思い出しておきましょう。

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

括弧書きの定理番号等は論文における番号を表します。

§1 Intorductionを読む

これはイントロなので読めばそれで終わりです。ブログ的には前回の記事の内容を知っていれば十分(殆ど重複している)なのでとばします。

§2 The finite cyclic group settingを読む

このセクションでは記号を導入して、主定理を述べています。

記号設定

正整数 $N$ に対して $\mathbb{Z}_N:=\mathbb{Z}/N\mathbb{Z}$ とする。
$\mathbb{R}^+$ は非負実数全体のなす集合*2。一方、 $\mathbb{Z}_+$ は正の整数全体のなす集合。
Landauの記号 $O(X)$ は $N$ が十分大きいときに絶対値が $N$ に依らない定数と $X$ の積で上から押さえられることを表す。定数部分が $k$ や $\delta$ などに依存する場合は $O_{k, \delta}(X)$ のような記法を用いる(この際、「 $N$ が十分大きいときに」の $N$ は $k, \delta$ に依存して決まる)。
Vinogradovの記号 $X \ll Y, \ Y\gg X$ も用いる。これらは $X = O(Y)$ に等しい。先ほどと同様に $\ll_{k, \delta}$ などの記法も用いる。

注意１: 標準的な射影 $\mathrm{pr}_N\colon \mathbb{Z} \to \mathbb{Z}_N$ がありますが、 $\mathrm{pr}_N$ を省略して $\mathbb{Z}_N$ の元を普通の整数の記号をもって表現することがあります。

注意２: この論文では背景にある理論の記号と整合性のあるような記号を使っていますが、Szemerédiの定理の証明を理解するだけであれば背景を理解する必要はありません。例えば、単なる有限和を積分記号を用いて表していたりしますが、積分論を知っている必要があるわけではありません。

論文全体で記号 $N$ は素数として固定します*3。想定としては $N$ はばかでかい素数です。"ばかでかい"の意味は、各定理において $N$ が( $k$ や $\delta$ などの考えているパラメータに依存して)十分大きければ成り立つという場合(大抵それはLandauの記号かVinogradov記号を持って主張される)の"十分大きい"を満たすだけでかいという意味です。Szemerédiの定理の $N$ に対応するものなのでこの記号ですが、証明の技術上素数と仮定します(そうすると $\mathbb{Z}_N$ が体をなす)。素数は無数に存在することから $N \to \infty$ とできますし、他にもBertrandの仮説などを用いることによって素数の場合のみ考えれば十分であることがわかります。

さて、証明のスキームにおける対象 $A$ ですが、Taoの論文では非負値有界関数

$f\colon \mathbb{Z}_N \longrightarrow \mathbb{R}^+$

です。ただし、"有界"はこの論文中での意味*4です(Definition 2.3)。

定義１(期待値, Definition 2.2) $X$ は空でない任意の集合とする。関数 $f\colon X \to \mathbb{C}$ と空でない有限部分集合 $A \subset X$ に対して、 $A$ で条件付けられる $f$ の期待値を

$\displaystyle \mathbb{E}_A(f)=\mathbb{E}_{x \in A}(f(x)) := \frac{1}{\#A}\sum_{x \in A}f(x)$

で定義する。また、空でない有限部分集合 $\Omega \subset X$ に対して特性関数 $\mathbf{1}_{\Omega}$ を

$\displaystyle \mathbf{1}_{\Omega}(x) := \begin{cases} 1 & (x \in \Omega) \\ 0 & (x \in X\setminus \Omega) \end{cases}$

で定めるとき、 $\mathbb{P}_{A}(\Omega)$ を

$\displaystyle \mathbb{P}_{A}(\Omega) := \mathbb{E}_{A}(\mathbf{1}_{\Omega})=\frac{\#(\Omega \cap A)}{\#A}$

と定義する。

定義１における設定において $P=P(x)$ を $A$ の元に対するstatementとするとき、集合 $S(P):=\{x \in A\mid P(x)\}$ を付随させて、

$\begin{align} &\mathbb{E}_P(f)=\mathbb{E}_{P(x)}(f(x)):=\mathbb{E}_{S(P)}(f), \\ &\mathbf{1}_{P}=\mathbf{1}_{P(x)}:=\mathbf{1}_{S(P)}, \\ &\mathbb{P}_A(P)=\mathbb{P}_{x \in A}(P(x)):=\mathbb{P}_A(S(P))=\mathbb{E}_A(\mathbf{1}_P)\end{align}$

という略記法も適宜用います。ただし、一行目については $S(P) \neq \emptyset$ を仮定します。また、連載全体において、有限集合とは限らない場合にも特性関数を同じ記号で利用します(無限集合の場合の期待値も若干使いますが、そちらは積分で定義しなければなりません)。

定義２ (積分) 関数 $f \colon \mathbb{Z}_N \to \mathbb{C}$ に対して、その積分を

$\displaystyle \int_{\mathbb{Z}_N}f := \mathbb{E}_{\mathbb{Z}_N}(f) = \frac{1}{N}\sum_{x=1}^Nf(x)$

で定義する。

定義３ (シフト作用素) $n \in \mathbb{Z}_N$ と $f \colon \mathbb{Z}_N \to \mathbb{C}$ に対して、 $T^nf\colon \mathbb{Z}_N \to \mathbb{C}$ を

$T^nf(x) := f(x+n)$

によって定義する。

$n \in \mathbb{Z}_N$ , $\Omega \subset \mathbb{Z}_N$ に対して $T^n\Omega := \Omega - n = \{x - n \mid x \in \Omega\}$ とすると

$T^n\mathbf{1}_{\Omega} = \mathbf{1}_{T^n\Omega}$

が成り立ちます。理由: 定義より $T^n\mathbf{1}_{\Omega}(x) = \mathbf{1}_{\Omega}(x+n)$ であり、 $x+n \in \Omega$ $\Longleftrightarrow$ $x \in \Omega - n$ なので。

$\mathrm{Map}(\mathbb{Z}_N, \mathbb{C})$ を関数 $f \colon \mathbb{Z}_N \to \mathbb{C}$ 全体のなす $\mathbb{C}$ -代数とするとき(和と積は点毎に定義)、

$T^n \in \mathrm{End}(\mathrm{Map}(\mathbb{Z}_N, \mathbb{C}))$

が成り立ちます(つまり、シフト作用素は準同型ということで、それは

$T^n(fg)=(T^nf)(T^ng), \ T^n(f+g)=T^nf+T^ng, \ T^n(\lambda f)=\lambda T^n(f)$

ということ。なお、明らかに定数関数はシフト作用素で不変)。

また、 $\mathbb{T} := \{T^n \mid n \in \mathbb{Z}_N\}$ とすれば

$\mathbb{T} \subset \mathrm{End}(\mathrm{Map}(\mathbb{Z}_N, \mathbb{C}))^{\times}$

は部分群をなします( $\mathrm{End}$ 環の積は合成。 $T^{n+m}=T^nT^m$ で単位元は $T^0$ 。逆元は $(T^n)^{-1}=T^{-n}$ )。

積分のシフト不変性 任意の $n \in \mathbb{Z}_N$ , $f \in \mathrm{Map}(\mathbb{Z}_N, \mathbb{C})$ に対して

$\displaystyle \int_{\mathbb{Z}_N}T^nf = \int_{\mathbb{Z}_N}f$

が成り立つ。

これは $\displaystyle \sum_{x=1}^Nf(x+n) = \sum_{x=1}^Nf(x)$ よりわかります。

内積 $\ f, g \in \mathrm{Map}(\mathbb{Z}_N, \mathbb{C})$ に対して、内積 $\langle f, g \rangle$ を

$\displaystyle \langle f, g \rangle := \int_{\mathbb{Z}_N}f\overline{g}$

と定義する。 $\overline{g}$ は $\overline{g}(x) := \overline{g(x)}$ で定義し、バーは複素共役を意味する。

これが内積の公理を満たすことは明らかで、 $\mathrm{Map}(\mathbb{Z}_N, \mathbb{C})$ はHilbert空間になります(下記 $L^2$ -ノルムが入る)*5。

シフト作用素の積分不変性と準同型性からユニタリ性

$\langle T^nf, T^ng \rangle = \langle f, g \rangle$

が成り立ちます( $f, g \in \mathrm{Map}(\mathbb{Z}_N, \mathbb{C})$ は任意)。

ノルム $\ f \in \mathrm{Map}(\mathbb{Z}_N, \mathbb{C})$ に対して、 $\left\|f\right\|_{L^{\infty}}$ 及び $\left\|f\right\|_{L^2}$ を

$\displaystyle \left\|f\right\|_{L^{\infty}}:= \sup_{x \in \mathbb{Z}_N}\left|f(x)\right|, \quad \left\|f\right\|_{L^2}:=\sqrt{\langle f, f \rangle} = \sqrt{\int_{\mathbb{Z}_N}\left|f\right|^2}$

で定義する。

$L^{\infty}$ -ノルムがノルム性質を満たすことは簡単にわかります。

定義２ (Definition 2.3) $\ f \in \mathrm{Map}(\mathbb{Z}_N, \mathbb{C})$ が有界であるとは、 $\left\| f \right\|_{L^{\infty}} \leq 1$ が成り立つときに言う。

以上を記号の準備として、Taoの論文の主定理を述べます。

主定理 (定量的回帰定理, Theorem 2.4) $k \geq 3$ を任意の整数、 $\delta$ を $0 < \delta \leq 1$ を満たす任意の実数とする。このとき、十分大きい素数 $N$ に対して*6次が成立する：条件

$\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$

が成り立つ。

一見、これはSzemerédiの定理には見えませんが、実は主定理とSzemerédiの定理は同値です。しかし、Green-Taoの定理にレベルアップするにはこの言い換えは重要な視点となります。我々の目的(Szemerédiの定理を証明する)から、ここでは主定理からSzemerédiの定理が導出されることのみ確認しましょう。

主定理 $\Longrightarrow$ Szemerédiの定理

$k, \delta$ を固定し、 $N$ を十分大きい整数とする。 $A \subset \{1, \dots, N\}$ が $\#A \geq \delta N$ を満たすと仮定する。このとき、示すべきは $A$ が長さ $k$ の等差数列を含むことである。Bertrandの仮説より、 $kN < N' < 2kN$ なる素数 $N'$ が存在する。このとき、射影 $\mathrm{pr}_{N'}\colon \mathbb{Z} \to \mathbb{Z}_{N'}$ に対して

$\iota := \left. \mathrm{pr}_{N'} \right|_{\{1, \dots, N\}}\colon \{1, \dots, N\} \hookrightarrow \mathbb{Z}_{N'}$

は単射となる。 $A':=\iota(A) \subset \mathbb{Z}_{N'}$ とする。このとき、

$\displaystyle \int_{\mathbb{Z}_{N'}}\mathbf{1}_{A'} = \frac{\#A'}{N'} = \frac{\#A}{N'} > \frac{\#A}{2kN} \geq \frac{\delta}{2k}$

なので、定量的回帰定理の条件が全て満たされていることから

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

が成り立つ。 $x, r \in \mathbb{Z}_{N'}$ に対して、

$\displaystyle \prod_{j=0}^{k-1}T^{jr}\mathbf{1}_{A'}(x) = 1$

となるための必要十分条件は

$\displaystyle x, x+r, \dots, x+(k-1)r \in A'$

なので、先ほどの帰結は

$\#\{(x, r) \in \mathbb{Z}_{N'}^2 \mid x, x+r, \dots, x+(k-1)r \in A'\} \gg_{k, \delta} (N')^2$ –①

ということである。

左辺の集合を $\mathfrak{X}$ としよう。 $(x, r) \in \mathfrak{X}$ に対して、まず $x \in A'$ であることから $a := \iota^{-1}(x) \in A$ が定まる(特に $1 \leq a \leq N$ )。 $d:=\iota^{-1}(x+r)-a \in \mathbb{Z}$ とすれば、 $1\leq a+d \leq N$ より $-N < d < N$ 。

このとき、 $0 \leq j \leq k-1$ に対して $a+jd \in A$ であることを確認したい。

$a, j, d$ の範囲から

$-(k-1)N < a+jd < kN.$

$\mathrm{pr}_{N'}(a+jd) = x+jr$ なので、 $c_j:=\iota^{-1}(x+jr)$ とすると

$a+jd \equiv c_j \pmod{N'}.$

$1 \leq c_j \leq N$ なので

$-N' < -kN < a+jd-c_j < kN < N'$

であるから、 $a+jd = c_j \in A$ がわかった。 $(x, 0) \in \mathfrak{X}$ の個数は高々 $N'$ 個なので、 $N$ が十分大きければ①より $r \neq 0$ であるような $(x, r) \in \mathfrak{X}$ が存在することがわかる。この $(x, r)$ に対する $a, a+d, \dots, a+(k-1)d \in A$ を考えると、 $d \neq 0$ なので $A$ は長さ $k$ の等差数列を含むことが示されたことになる。 Q.E.D.

以上で§2を読み終わります。

付録 Hilbert空間

定義 $\mathcal{H}$ を $\mathbb{C}$ -ベクトル空間とする。 $\langle \cdot , \cdot \rangle \colon \mathcal{H}\times \mathcal{H} \to \mathbb{C}$ が内積であるとは

$\langle z, z \rangle \geq 0 \quad ({}^{\forall}z \in \mathcal{H}), \quad\langle z, z \rangle = 0 \Longleftrightarrow z=0$
$\langle z, w \rangle = \overline{\langle w, z\rangle} \quad ({}^{\forall}z, w \in \mathcal{H})$
$\langle \lambda z+\mu z', w \rangle = \lambda \langle z, w\rangle + \mu \langle z', w\rangle \quad ({}^{\forall}\lambda, \mu \in \mathbb{C}, \ z, z', w \in \mathcal{H})$

が成り立つときにいう。 $z \in \mathcal{H}$ のノルム $\left\|z\right\|$ を $\left\|z\right\|:=\sqrt{\langle z, z\rangle}$ で定義する。

ノルムの基本性質 $\mathcal{H}$ を内積 $\langle \cdot , \cdot \rangle \colon \mathcal{H}\times \mathcal{H} \to \mathbb{C}$ を持つような $\mathbb{C}$ -ベクトル空間とする。このとき、ノルムについて次の性質が成り立つ。

$\left\|z\right\| \geq0 \quad ({}^{\forall}z \in \mathcal{H}) \quad \left\|z\right\| =0 \Longleftrightarrow z= 0$
$\left\|\lambda z\right\| = \left|\lambda \right|\left\|z\right\| \quad ({}^{\forall}\lambda \in \mathbb{C}, \ z \in \mathcal{H})$
(Cauchy-Schwarzの不等式) $\left|\langle z, w\rangle \right| \leq \left\|z\right\|\left\|w\right\| \quad ({}^{\forall}z, w \in \mathcal{H})$
(三角不等式) $\left\|z+w\right\| \leq \left\|z\right\|+\left\|w\right\| \quad ({}^{\forall}z, w \in \mathcal{H})$
(中線定理) $\left\|z+w\right\|^2+\left\|z-w\right\|^2=2\left\|z\right\|^2+2\left\|w\right\|^2 \quad ({}^{\forall}z, w \in \mathcal{H})$

証明. 最初の2つは簡単。任意の $t \in \mathbb{R}$ に対して

$\displaystyle \left\|tz+w\right\|^2=\left\|z\right\|^2t^2+2\mathrm{Re}(\langle z, w\rangle)t+\left\|w\right\|^2 \geq 0$

が成り立つので、 $\left|\mathrm{Re}(\langle z, w\rangle)\right| \leq \left\|z\right\|\left\|w\right\|$ を得る。 $\langle z, w\rangle = re^{i\theta}$ のとき、 $\left\|e^{-i\theta}z\right\|=\left\|z\right\|$ , $\left|\langle e^{-i\theta}z, w\rangle\right|=\left|\langle z, w\rangle\right|$ , $\langle e^{-i\theta}z, w\rangle \in \mathbb{R}$ なので $z \mapsto e^{-i\theta}z$ とすることによってCauchy-Schwarzの不等式が得られる。Cauchy-Schwarzの不等式より

$\begin{align}\left\|z+w\right\|^2 &= \left\|z\right\|^2+2\mathrm{Re}(\langle z, w\rangle)+\left\|w\right\|^2 \\ &\leq \left\|z\right\|^2+2\left|\langle z, w\rangle\right|+\left\|w\right\|^2 \\ &\leq \left\|z\right\|^2+2\left\|z\right\|\left\|w\right\|+\left\|w\right\|^2 = (\left\|z\right\|+\left\|w\right\|)^2\end{align}$

と三角不等式が示される。中線定理は

$\begin{align}\left\|z+w\right\|^2+\left\|z-w\right\|^2 &= \langle z+w, z+w\rangle + \langle z-w, z-w\rangle \\ &= \left( \left\|z\right\|^2+2\mathrm{Re}(\langle z, w \rangle)+\left\|w\right\|^2\right) + \left( \left\|z\right\|^2-2\mathrm{Re}(\langle z, w \rangle)+\left\|w\right\|^2\right) \\ &=2\left\|z\right\|^2+2\left\|w\right\|^2\end{align}$

と内積の公理に従って計算すればよい。Q.E.D.

このように内積空間はノルム空間になり、 $d(z, w):=\left\|z-w\right\|$ によって距離空間となります。

Hilbert空間 内積空間 $\mathcal{H}$ がHilbert空間であるとは、上記距離について完備であるときにいう。

この論文で扱う空間 $\mathrm{Map}(\mathbb{Z}_N, \mathbb{C})$ はHilbert空間になっています*7。

理由: $\{f_n\}_{n=1}^{\infty}$ を $\mathrm{Map}(\mathbb{Z}_N, \mathbb{C})$ のCauchy列とする。このとき、 $x \in \mathbb{Z}_N$ に対して

$\displaystyle \left|f_n(x)-f_m(x)\right| \leq \sqrt{N}\left\|f_n-f_m\right\|_{L^2}$

なので $\{f_n(x)\}_{n=1}^{\infty}$ は $\mathbb{C}$ におけるCauchy列である。従って、 $\displaystyle \lambda_x:=\lim_{n\to \infty}f_n(x) \in \mathbb{C}$ が存在する。これらを用いて $f \in \mathrm{Map}(\mathbb{Z}_N, \mathbb{C})$ を $f(x):=\lambda_x$ で定義する。 $\mathbb{Z}_N$ は有限集合なので、 $\varepsilon > 0$ を任意にとったときに