インテジャーズ

INTEGERS

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

タオのセメレディ論文の§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が十分大きいときに」のNk, \deltaに依存して決まる)。
  • Vinogradovの記号 X \ll Y, \ Y\gg Xも用いる。これらはX = O(Y)に等しい。先ほどと同様に\ll_{k, \delta}などの記法も用いる。


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

注意2: この論文では背景にある理論の記号と整合性のあるような記号を使っていますが、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)。

定義1(期待値, 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}
と定義する。

定義1における設定において 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 を仮定します。また、連載全体において、有限集合とは限らない場合にも特性関数を同じ記号で利用します(無限集合の場合の期待値も若干使いますが、そちらは積分で定義しなければなりません)。

定義2 (積分) 関数 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)
で定義する。

定義3 (シフト作用素) n \in \mathbb{Z}_Nf \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}-ノルムがノルム性質を満たすことは簡単にわかります。

定義2 (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を任意の整数、\delta0 < \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の定理が導出されることのみ確認しましょう。

主定理\LongrightarrowSzemeré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\|t^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を任意にとったときに

\displaystyle n \geq N_0 \Longrightarrow \left|f_n(x)-\lambda_x\right| < \varepsilon, \quad ({}^{\forall}x \in \mathbb{Z}_N)

なる番号N_0が存在する。このようなN_0に対して、n \geq N_0ならば

\displaystyle \left\|f_n-f\right\|_{L^2} = \sqrt{\frac{\sum_{x=1}^N\left|f_n(x)-\lambda_x\right|^2}{N}} \leq \varepsilon

が成り立つので、\displaystyle \lim_{n \to \infty}f_n = f である。すなわち、\mathrm{Map}(\mathbb{Z}_N, \mathbb{C})L^2-ノルムについて完備である

*1:代数幾何学で出てくるschemeではなく通常の英単語としての意味合い。

*2:\mathbb{R}_{\geq 0}などにするべきだと思いますが、とりあえず論文の記号に合わせます。

*3:ただし、この記事の「主定理\LongrightarrowSzemerédiの定理」ではNを整数として扱います。

*4:Tao, Green-Taoともに奇妙でad hocな言葉が多用されています。

*5:Hilbert空間の非常に簡単な復習を付録に書いています。特に、Cauchy-Schwarzの不等式と三角不等式が大切です。

*6:結果がVinogradov記号を用いて記述されているのでこの仮定文は必要ない。今後の定理では実際に省略する。

*7:ここで直接的な証明を書いていますが、実際には簡単にわかるように\mathrm{Map}(\mathbb{Z}_N, \mathbb{C})N次元空間なので、「有限次元複素内積空間は完備である」という一般的事実からもHilbert空間であることがわかります(§5(その一) )