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

密度昇格定理 $\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$ の速度に関する一つ目の指定: 記事４の②より、任意の $\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}$ の二重カウンティング性質に付随して存在する整数とし( $L$ は $L\geq N_1(\varepsilon)$ なる任意の整数)、これらと $\mathcal{P}, \mathbf{A}, c$ のみに依存する整数 $N_1'(\varepsilon), N_2'(\varepsilon, L)$ を以下の条件を満たすように定める( $L$ は $L\geq N_1'(\varepsilon)$ なる任意の整数)。

$N_2'$ の条件１: $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'$ の条件２: $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'$ の定義: 記事４の①で定まる $N=N(\varepsilon)$ は $\varepsilon$ に関する単調減少関数で $N \to \infty \ (\varepsilon \to 0)$ あるとしてよい。 $N(\varepsilon)$ の逆関数を $\eta'(N)$ とする。 $N \to \infty$ で $\eta' \to 0$ が成り立つ。

$(\overrightarrow{R_1})_h$ が $L_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$ が成り立つ。記事４の上密度に対する鳩ノ巣原理より、或る $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.

INTEGERS

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

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