【§2準備】定義の盛り合わせ

※4/25追記:シフト作用素の定義を変更しました。

これから§2 The finite cyclic group settingを読んでいきます。

さてこれからSzemerédiの定理の証明に向けていろいろ頑張るわけですが、その前にいろんな下準備が必要になります。

定義だけでもかなりたくさんあるので、それだけで一つの記事が必要になりそうです。

がんばるぞい!

暗黙の了解など

論文全体を通していくつか前準備しておくことがあります。

  • 特に断りがない限り、N十分大きな素数とする。
  • \mathbb{Z}_NNの剰余類、つまり\mathbb{Z}/N\mathbb{Z}を表す。
  • O(X)は、Nによらない定数とXの積で上から押さえられることを意味する。つまりA=O(X)と書いた場合は、A\lt CX(ただしCNに依存しない)を意味する。
  • 上から押さえるCk\deltaに依存する場合は、明示的にO_{k,\delta}(X)と書く。
  • X\ll Y(またはY\gg X)はXYより十分小さいことを表す。X=O(Y)と同義。また、X\ll_{k,\delta} Yと書いた場合はX=O_{k,\delta}(Y)と同義。

ちょっと補足しましょう

十分大きな素数N

十分大きな素数というのは、とにかく大きな素数(?)です。これからの定理などで「もしかしたら素数Nが小さかったら成り立たなくなるんじゃない?(´-`)」というものが出てくるかもしれないですが、いいからそういうのを成り立たせるようなでかい素数を持って来いという雰囲気で捉えてもらえれば大丈夫だと思います。

同じものを同じとみなす

\mathbb{Z}_NというのはNの剰余類を表します。自然数をNで割ったあまりが等しいものを同じとみなしましょう!というようなグループです。
Nで割ったあまりですので、\{1,2,\dots, N-1, N\}の中で計算を行うようなイメージです*1
そして嬉しいことに、Nは素数ですので\mathbb{Z}_Nの中で四則演算が成り立ちます。やったね!

オーダー

O(X)で用いるOはランダウの記号ですね。「オーダー」などと読んだりします。(普通にオーと読む場合もある)。
どちらかというと微分積分学で見ることが多いかな?
例えば…xが十分大きいとき、$$
x^3-4x^2+1=O(x^3)
$$です。なぜならある定数c>1を持ってこれば$$
x^3-4x^2+1 < cx^3
$$だからです。実際、x\to\inftyで$$
\frac{x^3-4x^2+1}{x^3}\to 1
$$となるため、定数で押さえることができます。

関数と期待値と積分と大きさと

ガンガン定義していきます。

定義2.2 期待値
f:X\to\mathbb{C}とする。また、AXの空でない部分集合とする。(A\subset X, A\neq \emptyset)
このとき、Aで条件付けられるf期待値を$$
\mathbb{E}_{A}f=\mathbb{E}_{x\in A}f(x) := \frac{1}{|A|}\sum_{x\in A}f(x)
$$と定める。
Aに属している要素に対してfを作用させてその結果の平均を取る、といったことですね。いかにも期待値っぽい。
定義2.2(続き) 特性関数とその期待値
空でない部分集合\Omega \subset Xに対して、特性関数\mathbb{1}_\Omega(x)を$$
\mathbb{1}_\Omega(x):=\begin{cases}
1&(x\in \Omega)\\
0&(x \notin \Omega)
\end{cases}
$$と定めるとき、$$
\mathbb{P}_{A}(\Omega):=\mathbb{E}_{A}\mathbb{1}_{\Omega}=\frac{|A\cap\Omega|}{|A|}
$$と定める。
最後の等号は簡単に証明できます。
\begin{align}
\mathbb{E}_{A}\mathbb{1}_{\Omega}&=\frac{1}{|A|}\sum_{x\in A}\mathbb{1}_{\Omega}(x)\\
&=\frac{1}{|A|}\sum_{x\in A\cap \Omega}1\\
&=\frac{|A\cap\Omega|}{|A|}
\end{align}
定義2.2(続き) 述語とその期待値
P(x)xに関する述語とするとき、$$
\mathbb{P}_{A}(P):=\mathbb{E}_{A}\mathbb{1}_{P}
$$と定める。
(正直まだ登場していないので実用性がわからない)
定義2.2(続き) 積分
関数f:\mathbb{Z}_{N}\to \mathbb{C}に対して、積分を$$
\int_{\mathbb{Z}_N}f := \mathbb{E}_{\mathbb{Z}_{N}} f=\frac{1}{N}\sum_{x=1}^{N}f(x)
$$と定める。
期待値の範囲が\mathbb{Z}_Nになっただけで、結局期待値と同じです。
定義2.2(続き) シフト作用素
自然数n\in\mathbb{Z}_Nと関数f:\mathbb{Z}_{N}\to \mathbb{C}に対して、シフト作用素T^nを$$
T^{n}f(x):=f(x+n)
$$と定める。
※4/25追記:定義をf(x-n)からf(x+n)に変更しました。
関数に左から作用させる使い方をします。
シフト作用素にはいろんな性質があるのでちょっと紹介しましょう。

シフト作用素の性質

※4/25追記:定義の変更に伴い、一部符号が入れ替わっています。

特性関数とシフト作用素
n\in\mathbb{Z}_N, \Omega\subset\mathbb{Z}_Nに対して、\Omega - n = T^{n}\Omega:=\{\omega-n\mid\omega \in \Omega\}と定めると、$$
T^{n}\mathbb{1}_\Omega=\mathbb{1}_{T^n\Omega}
$$が成立。
\begin{align}
T^{n}\mathbb{1}_\Omega(x)&=\mathbb{1}_\Omega(x+n)\\
&=\mathbb{1}_{T^n\Omega}(x)\\
&(\because x+n\in\Omega \Leftrightarrow x \in \Omega - n)
\end{align}
準同型写像
シフト作用素は準同型写像となる。つまり、\begin{align}
T^n(fg)&=(T^nf)(T^ng)\\
T^n(f+g)&=T^nf+T^ng
\end{align}
\begin{align}
T^n(fg)(x)&=(fg)(x+n)\\
&=f(x+n)g(x+n)\\
&=(T^nf(x))(T^ng(x))\\
&=(T^nf)(T^ng)(x)
\end{align}\begin{align}
T^n(f+g)(x)&=(f+g)(x+n)\\
&=f(x+n)+g(x+n)\\
&=T^nf(x)+T^ng(x)\\
&=(T^nf+T^ng)(x)
\end{align}
定数関数とシフト作用素
定数関数はシフト作用素に関して不変$$
T^nc=c (c\text{は定数})
$$
積分とシフト作用素
積分はシフト作用素に関して不変$$
\int_{\mathbb{Z}_N}T^nf=\int_{\mathbb{Z}_N}f
$$
\begin{align}
\int_{\mathbb{Z}_N}T^nf&=\mathbb{E}_{x\in\mathbb{Z}_N}T^nf(x)\\
&=\mathbb{E}_{x\in\mathbb{Z}_N}f(x+n)\\
\end{align}ここでx\in\mathbb{Z}_Nx+n\in\mathbb{Z}_Nは一対一対応するため、\begin{align}
\mathbb{E}_{x\in\mathbb{Z}_N}f(x+n)&=\mathbb{E}_{x\in\mathbb{Z}_N}f(x)\\
&=\int_{\mathbb{Z}_N}f
\end{align}(\mathbb{Z}_N内全ての項に対するf(x)の足し算なので、結局足している項は変わらない)

シフト作用素は群をなす*2
T^nT^mの演算はT^nT^m(合成)と定める。

演算に関して閉じている
 任意のn,m\in\mathbb{Z}_Nf(x)に対して、
\begin{align}
T^nT^mf(x)&=T^nf(x+m)\\
&=f(x+n+m)\\
&=f(x+(n+m))\\
&=T^{n+m}f(x)
\end{align}
結合法則
 任意のa,b,c\in\mathbb{Z}_Nに対して、
\begin{align}
(T^aT^b)T^c&=T^{a+b}T^c\\
&=T^{a+b+c}\\
&=T^aT^{b+c}\\
&=T^a(T^bT^c)
\end{align}
単位元の存在
 単位元はT^0である。
 任意のn\in\mathbb{Z}_Nに対して、\begin{align}
T^0T^n&=T^n\\
&=T^nT^0
\end{align}
逆元の存在
 任意のx\in\mathbb{Z}_Nに対して、T^nの逆元はT^{-n}$$
T^nT^{-n}=T^0=T^{-n}T^n
$$
いろいろ語弊がありそうですがざっくりと群の公理を満たしてるっぽいなということがわかります。

つづき

シフト作用素の性質の紹介が終わったので、定義に戻ります。

定義2.2(続き) 内積
関数f, g: \mathbb{Z}_N\to\mathbb{C}に対して、内積\langle f, g \rangleを$$
\langle f, g \rangle:= \int_{\mathbb{Z}_N}f\bar{g}
$$と定める。
ここで、\bar{\cdot}は複素共役を表し、$$
\bar{g}(x)=\overline{g(x)}
$$
定義2.2(続き) ノルム
関数f:\mathbb{Z}_N\to\mathbb{C}に対して、\|f\|_{L^\infty},\|f\|_{L^2}を\begin{align}
\|f\|_{L^\infty}&:=\sup_{x\in\mathbb{Z}_N}|f(x)|\\
\|f\|_{L^2}&:=\sqrt{\langle f,f\rangle}=\sqrt{\int_{\mathbb{Z}_N}|f|^2}
\end{align}と定める。
ここで\supとは上限*3を表します。最大値と思ってもらえれば大丈夫です。(正確には最大値を一般化したものです。)
というか探索範囲が\mathbb{Z}_Nで有限だから最大値でもいいような気がするんだが……謎。
定義2.3 有界
f:\mathbb{Z}_N\to\mathbb{C}\|f\|_{L^\infty}\leqq 1を満たすとき、f有界であるという。
こちらは単純に言葉の定義。fが有界と言われたら\|f\|_{L^\infty}\leqq 1ですよーーーってことです。

疲れた

次回からSzemerédiの定理につながるような定理がモリモリ出てきます。
いろんな記号が入り乱れてパラダイスになりますが、コツはその圧力に負けないことです。
気合入れていきましょう(僕が)。

*1:\{0,1,2,\dots, N-1\}とする考え方もあります。というかこのあたりは正直うまいことまだ掴みきれていないので下手なこと言えない…

*2:ちなみに交換法則も成り立つのでアーベル群となります。

*3:\sup f(x)=Aであるとは、「Af(x)のどの値よりも大きい(f(x)\leqq A)けど、Aを少しでも下げるととそうじゃなくなっちゃう!」ということです(?)。f(x)より大きな値でどれだけギリギリまで下げられるかチャレンジしているみたいな。f(x)の最大値が存在すれば\max f(x)=\sup f(x)となります。