【§2準備】定義の盛り合わせ
※4/25追記:シフト作用素の定義を変更しました。
これから§2 The finite cyclic group settingを読んでいきます。
さてこれからSzemerédiの定理の証明に向けていろいろ頑張るわけですが、その前にいろんな下準備が必要になります。
定義だけでもかなりたくさんあるので、それだけで一つの記事が必要になりそうです。
がんばるぞい!
暗黙の了解など
論文全体を通していくつか前準備しておくことがあります。
- 特に断りがない限り、は十分大きな素数とする。
- はの剰余類、つまりを表す。
- は、によらない定数との積で上から押さえられることを意味する。つまりと書いた場合は、(ただしはに依存しない)を意味する。
- 上から押さえるがやに依存する場合は、明示的にと書く。
- (または)はがより十分小さいことを表す。と同義。また、と書いた場合はと同義。
十分大きな素数
十分大きな素数というのは、とにかく大きな素数(?)です。これからの定理などで「もしかしたら素数Nが小さかったら成り立たなくなるんじゃない?(´-`)」というものが出てくるかもしれないですが、いいからそういうのを成り立たせるようなでかい素数を持って来いという雰囲気で捉えてもらえれば大丈夫だと思います。
同じものを同じとみなす
というのはの剰余類を表します。自然数をで割ったあまりが等しいものを同じとみなしましょう!というようなグループです。
で割ったあまりですので、の中で計算を行うようなイメージです*1。
そして嬉しいことに、は素数ですのでの中で四則演算が成り立ちます。やったね!
オーダー
で用いるはランダウの記号ですね。「オーダー」などと読んだりします。(普通にオーと読む場合もある)。
どちらかというと微分積分学で見ることが多いかな?
例えば…が十分大きいとき、$$
x^3-4x^2+1=O(x^3)
$$です。なぜならある定数を持ってこれば$$
x^3-4x^2+1 < cx^3
$$だからです。実際、で$$
\frac{x^3-4x^2+1}{x^3}\to 1
$$となるため、定数で押さえることができます。
関数と期待値と積分と大きさと
ガンガン定義していきます。
とする。また、をの空でない部分集合とする。(, )
このとき、で条件付けられるの期待値を$$
\mathbb{E}_{A}f=\mathbb{E}_{x\in A}f(x) := \frac{1}{|A|}\sum_{x\in A}f(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|}
$$と定める。
\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}
をに関する述語とするとき、$$
\mathbb{P}_{A}(P):=\mathbb{E}_{A}\mathbb{1}_{P}
$$と定める。
関数に対して、積分を$$
\int_{\mathbb{Z}_N}f := \mathbb{E}_{\mathbb{Z}_{N}} f=\frac{1}{N}\sum_{x=1}^{N}f(x)
$$と定める。
自然数と関数に対して、シフト作用素を$$
T^{n}f(x):=f(x+n)
$$と定める。
※4/25追記:定義をf(x-n)からf(x+n)に変更しました。
シフト作用素にはいろんな性質があるのでちょっと紹介しましょう。
シフト作用素の性質
※4/25追記:定義の変更に伴い、一部符号が入れ替わっています。
に対して、と定めると、$$
T^{n}\mathbb{1}_\Omega=\mathbb{1}_{T^n\Omega}
$$が成立。
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}
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
$$
\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}ここでとは一対一対応するため、\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}(内全ての項に対するの足し算なので、結局足している項は変わらない)
演算に関して閉じている
任意のとに対して、
\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}
結合法則
任意のに対して、
\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}
単位元の存在
単位元はである。
任意のに対して、\begin{align}
T^0T^n&=T^n\\
&=T^nT^0
\end{align}
逆元の存在
任意のに対して、の逆元は$$
T^nT^{-n}=T^0=T^{-n}T^n
$$
つづき
シフト作用素の性質の紹介が終わったので、定義に戻ります。
関数に対して、内積を$$
\langle f, g \rangle:= \int_{\mathbb{Z}_N}f\bar{g}
$$と定める。
ここで、は複素共役を表し、$$
\bar{g}(x)=\overline{g(x)}
$$
関数に対して、を\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}と定める。
というか探索範囲がで有限だから最大値でもいいような気がするんだが……謎。
がを満たすとき、は有界であるという。
疲れた
次回からSzemerédiの定理につながるような定理がモリモリ出てきます。
いろんな記号が入り乱れてパラダイスになりますが、コツはその圧力に負けないことです。
気合入れていきましょう(僕が)。