インテジャーズ

INTEGERS

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

セメレディの定理の組合せ論的証明ー5

密度昇格定理 \mathcal{P} \subset \mathcal{AP}は非有界かつ二重カウンティング性質を満たすと仮定する。\mathbf{A} \subset \mathbb{Z}\mathcal{P}に沿った上密度が\overline{d}_{\mathcal{P}}(\mathbf{A})=\deltaであるとき、非有界かつ二重カウンティング性質を満たす\mathcal{P}' \subset \mathcal{P}であって、\mathbf{A}\mathcal{P}'に沿った密度が存在し、d_{\mathcal{P}'}(\mathbf{A}) = \deltaが成り立つようなものが存在する。

証明. c \colon \mathbb{N} \to \mathbb{R}_{>0}を十分遅くc(N) \to 0 \ (N \to \infty)となるような\mathcal{P}\mathbf{A}のみに依存する広義単調減少関数とする(どれだけ十分遅くとるかは後で指定する)。このcを用いて、\mathcal{P}'\subset \mathcal{P}

\displaystyle \mathcal{P}' := \left\{\overrightarrow{P{ }} \in \mathcal{P} \left| \ \left|\mu_{\overrightarrow{P{ }}}(\mathbf{A})-\delta\right| \leq c(\mathrm{len}(\overrightarrow{P{ }}) )\right\}\right.

と定義する。

cの速度に関する一つ目の指定: 記事4の②より、任意の\varepsilon > 0に対していくらでも長さが大きい\overrightarrow{P{ }} \in \mathcal{P}であって

\displaystyle \left|\mu_{\overrightarrow{P{ }}}(\mathbf{A})-\delta\right| \leq \varepsilon

が成り立つようなものが存在する。そこで、各n=1, 2, \dotsに対して、l_n:=\mathrm{len}(\overrightarrow{P_n}), l_1 < l_2 < l_3 < \cdots,

\displaystyle \left|\mu_{\overrightarrow{P_n}}(\mathbf{A})-\delta\right| \leq 2^{-n}

となるように\{\overrightarrow{P_n}\}_{n=1}^{\infty}を選び、c(l_n) \geq 2^{-n}が成り立つだけ遅くc \to 0となるものとする

すると、\overrightarrow{P_n} \in \mathcal{P}'なので、\mathcal{P}'は非有界であることがわかる。また、c \to 0であることから\mathbf{A}\mathcal{P}'に沿った密度をもち、d_{\mathcal{P}'}(\mathbf{A}) = \deltaが成り立つ。

あとは\mathcal{P}'が二重カウンティング性質を満たすことを示せばよい。\varepsilon > 0をとる。N_1(\varepsilon), N_2(\varepsilon, L)\mathcal{P}の二重カウンティング性質に付随して存在する整数とし(LL\geq N_1(\varepsilon)なる任意の整数)、これらと\mathcal{P}, \mathbf{A}, cのみに依存する整数N_1'(\varepsilon), N_2'(\varepsilon, L)を以下の条件を満たすように定める(LL\geq N_1'(\varepsilon)なる任意の整数)。

N_2'の条件1: N_2'(\varepsilon, L)L^{-1} \geq c(N_2')を満たすだけ大きくとる。

\etaの定義: N_1(\varepsilon)\varepsilonについて単調減少でN_1 \to \infty \ (\varepsilon \to 0)あるとしてよい。N_1(\varepsilon)の逆関数を\eta(N)とする。N \to \infty\eta \to 0が成り立つ。

N_1'の条件: N_1'(\varepsilon)\frac{1}{\varepsilon} \leq \min\{\sqrt{N_1'(\varepsilon)}, \frac{1}{\sqrt{\eta(N_1'(\varepsilon) )}}, \frac{1}{\sqrt{\eta'(N_1'(\varepsilon) )}}\}および\eta(N_1'(\varepsilon) ) \leq \frac{\varepsilon}{2}を満たすだけ大きくとる。

N_2'の条件2: N_2'(\varepsilon, L) \geq N_2(\eta(L), L)を満たす。

N_1'(\varepsilon) \leq L_1 \leq N_2'(\varepsilon, L_1) \leq L_2なるL_1, L_2 \in \mathbb{N}をとり、H_1, H_2 \in \mathbb{N}とし、L_1 \times H_1-長方形\overrightarrow{R_1}L_2\times H_2-長方形\overrightarrow{R_2}であって

\displaystyle d_{\mathrm{TV}}(\mu_{\overrightarrow{R_1}}, \mu_{\overrightarrow{R_2}}) \leq \frac{1}{L_1} −①

が成り立つようなものを考える。H_2個のL_2-AP (\overrightarrow{R_2})_h \ (h\in [H_2])\mathcal{P}'に属するとする。

任意のh \in [H_2]に対して

\left|\mu_{(\overrightarrow{R_2})_h}(\mathbf{A}) - \delta\right| \leq c(\mathrm{len}( (\overrightarrow{R_2})_h) )

であり、\mathrm{len}( (\overrightarrow{R_2})_h)=L_2なので

\displaystyle \mu_{(\overrightarrow{R_2})_h}(\mathbf{A}) \geq \delta-c(L_2) \geq \delta-c(N_2'(\varepsilon, L_1) ) \geq \delta-\frac{1}{L_1}

が成り立つ。二重カウンティング恒等式を使ってh \in H_2について平均化すると、

\displaystyle \mu_{\overrightarrow{R_2}}(\mathbf{A}) = \frac{1}{H_2}\sum_{h \in H_2}\mu_{(\overrightarrow{R_2})_h}(\mathbf{A}) \geq \delta - \frac{1}{L_1}

が成り立つ。①より

\displaystyle \left|\mu_{\overrightarrow{R_1}}(\mathbf{A}) -\mu_{\overrightarrow{R_2}}(\mathbf{A})\right| \leq d_{\mathrm{TV}}(\mu_{\overrightarrow{R_1}}, \mu_{\overrightarrow{R_2}}) \leq \frac{1}{L_1}

なので、

\displaystyle \mu_{\overrightarrow{R_1}}(\mathbf{A}) =  \mu_{\overrightarrow{R_2}}(\mathbf{A})+\left( \mu_{\overrightarrow{R_1}}(\mathbf{A})- \mu_{\overrightarrow{R_2}}(\mathbf{A})\right) \geq \delta-\frac{2}{L_1}

が得られる。よって、二重カウンティング恒等式より

\displaystyle \sum_{h \in [H_1]}\mu_{(\overrightarrow{R_1})_h}(\mathbf{A}) = \mu_{\overrightarrow{R_1}}(\mathbf{A})H_1 \geq \left(\delta-\frac{2}{L_1}\right)H_1

が成り立つ。

\mathcal{P}が二重カウンティング性質を満たすという仮定およびN_2'の取り方から、高々\eta(L_1)H_1個の例外を除いて(\overrightarrow{R_1})_h \ (h \in [H_1])\mathcal{P}に属する。よって、

\displaystyle \sum_{h \in [H_1], \ (\overrightarrow{R_1})_h \not \in \mathcal{P}}\mu_{(\overrightarrow{R_1})_h}(\mathbf{A}) \leq \sum_{h \in [H_1], \ (\overrightarrow{R_1})_h \not \in \mathcal{P}}1 \leq \eta(L_1)H_1

\displaystyle \sum_{h \in [H_1], \ (\overrightarrow{R_1})_h \in \mathcal{P}}\mu_{(\overrightarrow{R_1})_h}(\mathbf{A}) = \sum_{h \in [H_1]}\mu_{(\overrightarrow{R_1})_h}(\mathbf{A})-\sum_{h \in [H_1], \ (\overrightarrow{R_1})_h \not \in \mathcal{P}}\mu_{(\overrightarrow{R_1})_h}(\mathbf{A}) \geq \left(\delta-\frac{2}{L_1}-\eta(L_1)\right)H_1

となる。

\eta'の定義: 記事4の①で定まるN=N(\varepsilon)\varepsilonに関する単調減少関数でN \to \infty \ (\varepsilon \to 0)あるとしてよい。N(\varepsilon)の逆関数を\eta'(N)とする。N \to \infty\eta' \to 0が成り立つ。

(\overrightarrow{R_1})_hL_1-APであることに注意して、\eta'の定義より

\displaystyle \mu_{(\overrightarrow{R_1})_h}(\mathbf{A}) \leq \delta+\eta'(L_1)

(\overrightarrow{R_1})_h \in \mathcal{P}を満たすような任意のh \in [H_1]に対して成り立つ。すると、

\begin{align} &\sum_{h \in [H_1], \ (\overrightarrow{R_1})_h \in \mathcal{P}}\left( \delta+\eta'(L_1)-\mu_{(\overrightarrow{R_1})_h}(\mathbf{A})\right) \\ &\leq (\delta+\eta'(L_1) )H_1-\sum_{h \in [H_1], \ (\overrightarrow{R_1})_h \in \mathcal{P}}\mu_{(\overrightarrow{R_1})_h}(\mathbf{A}) \leq \left(\frac{2}{L_1}+\eta(L_1)+\eta'(L_1)\right)H_1\end{align}

が得られる。これにMarkovの不等式を適用すると

\begin{align} &\#\left\{h \in [H_1] \left| \ \delta+\eta'(L_1)-\mu_{(\overrightarrow{R_1})_h}(\mathbf{A}) \leq \frac{2}{\varepsilon}\left(\frac{2}{L_1}+\eta(L_1)+\eta'(L_1)\right) \right\}\right. \\ &\geq \#\{h \in [H_1] \mid (\overrightarrow{R_1})_h \in \mathcal{P}\} - \frac{\varepsilon}{2}H_1 \geq \left(1-\left(\eta(L_1)+\frac{\varepsilon}{2}\right)\right)H_1\end{align}

となる。すなわち、高々\left(\eta(L_1)+\frac{\varepsilon}{2}\right)H_1個の例外を除くh \in [H_1]に対して(\overrightarrow{R_1})_h \in \mathcal{P}かつ

\displaystyle 0 \leq \delta+\eta'(L_1)-\mu_{(\overrightarrow{R_1})_h}(\mathbf{A}) \leq \frac{2}{\varepsilon}\left(\frac{2}{L_1}+\eta(L_1)+\eta'(L_1)\right)

が成り立つことがわかった。

cの速度に関する二つ目の指定: c

\displaystyle c(N) \geq \max\left\{\eta'(N), \ 2\left(\frac{2}{\sqrt{N}}+\sqrt{\eta(N)}\right)+\left(\frac{2}{\sqrt{\eta'(N)}}-1\right)\eta'(N)\right\}

を満たすだけ遅くc \to 0となるものとする

N_1'の条件およびcの速度指定から高々\varepsilon H_1個の例外を除くh \in [H_1]に対して(\overrightarrow{R_1})_h \in \mathcal{P}かつ

\displaystyle \left|\mu_{(\overrightarrow{R_1})_h}(\mathbf{A})-\delta\right| \leq c(L_1)

が成り立ち、従って (\overrightarrow{R_1})_h \in \mathcal{P}'が成り立つことがわかった(\mathrm{len}( (\overrightarrow{R_1})_h)=L_1に注意)。これが示したかったことである。 Q.E.D.

系 (飽和等差数列とパーフェクトカラー) \mathbf{S} \subset \mathbb{Z}\overline{d}_{\mathcal{AP}}(\mathbf{S}) = \sigma > 0なる集合とし、c\colon \mathbf{S} \to \mathbf{C}\mathbf{S}の塗り分け写像とする(\mathbf{C}は有限個の色の集合)。このとき、或るp \in \mathbf{C}および非有界で二重カウンティング性質を満たす\mathcal{P} \subset \mathcal{AP}が存在して、\mathbf{A}(p):=\{s \in \mathbf{S} \mid c(s) = p\}\mathbf{S}\mathcal{P}に沿った密度をもち、d_{\mathcal{P}}(\mathbf{A}(p) )=:\delta > 0かつd_{\mathcal{P}}(\mathbf{S}) = \sigmaが成り立つ。

pをパーフェクトカラーといい、\mathcal{P}の元を飽和等差数列とよぶ。

証明. 密度昇格定理より或る非有界で二重カウンティング性質を満たす\mathcal{P}' \subset \mathcal{AP}が存在して、\mathbf{S}\mathcal{P}'に沿った密度をもってd_{\mathcal{P}'}(\mathbf{S})=\sigmaが成り立つ。記事4の上密度に対する鳩ノ巣原理より、或るp \in \mathbf{C}が存在して、\overline{d}_{\mathcal{P}'}(\mathbf{A}(p) )=\delta > 0が成り立つ。ここで、再度密度昇格定理を適用すれば、或る非有界で二重カウンティング性質を満たす\mathcal{P} \subset \mathcal{P}'が存在して、\mathbf{A}(p)\mathcal{P}に沿った密度をもち、d_{\mathcal{P}}(\mathbf{A}(p))=\deltaが成り立つ。極限の定義より、d_{\mathcal{P}'}(\mathbf{S})=\sigmaからd_{\mathcal{P}}(\mathbf{S})=\sigmaが従う。 Q.E.D.