インテジャーズ

INTEGERS

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

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

等間隔に並ぶ素数を追い求めて

K-AP \overrightarrow{P{ }}に対して、一様確率測度\mu_{\overrightarrow{P{ }}}\colon 2^{\mathbb{Z}} \to [0, 1]を\mathbf{A} \subset \mathbb{Z}に対して

\displaystyle \mu_{\overrightarrow{P{ }}}(\mathbf{A}) := \frac{1}{K}\#\{i \in [K] \mid P(i) \in \mathbf{A}\}

と定義する。

L, H \in \mathbb{N}に対して、\overrightarrow{R{ }}がL\times H-長方形であるとは、a \in \mathbb{Z}, r, s \in \mathbb{N}を用いて

\displaystyle \overrightarrow{R{ }}=(a+lr+hs)_{(l, h) \in [L]\times [H]}

と表されるもののことをいう。\overrightarrow{R{ }}に付随する写像R\colon \mathbb{Z}^2 \to \mathbb{Z}をR(l, h) := a+lr+hsで定義する。

L\times H-長方形\overrightarrow{R{ }}に対して、各h \in [H]毎にL-AP \overrightarrow{R_h}を

\overrightarrow{R_h}:= (R(l, h) )_{l \in [L]}

で定義し、各l \in [L]毎にH-AP \overrightarrow{R^l}を

\overrightarrow{R^l} := (R(l, h) )_{h \in [H]}

で定義する。また、一様確率測度\mu_{\overrightarrow{R{ }}}\colon 2^{\mathbb{Z}} \to [0, 1]を\mathbf{A} \subset \mathbb{Z}に対して

\displaystyle \mu_{\overrightarrow{R{ }}}(\mathbf{A}) := \frac{1}{LH}\#\{(l, h) \in [L]\times [H] \mid R(l, h) \in \mathbf{A}\}

と定義する。このとき、二重カウンティング恒等式

\displaystyle \mu_{\overrightarrow{R{ }}} = \frac{1}{H}\sum_{h \in [H]}\mu_{\overrightarrow{R_h}} = \frac{1}{L}\sum_{l \in [L]}\mu_{\overrightarrow{R^l}}

が成り立つ。

確率測度\mu, \nu\colon 2^{\mathbb{Z}} \to [0, 1]に対して、全変動d_{\mathrm{TV}}(\mu, \nu)を

\displaystyle d_{\mathrm{TV}}(\mu, \nu) := \sup_{\mathbf{A} \subset \mathbb{Z}}\left|\mu(\mathbf{A})-\nu(\mathbf{A})\right|

で定義する。

補題１ L, H \in \mathbb{N}, L \leq H, \overrightarrow{P{ }}: H-APとし、L\times H-長方形\overrightarrow{R{ }}を\overrightarrow{R{ }}:=(P(l+h) )_{(l, h) \in [L]\times [H]}で定義する。このとき、
\displaystyle d_{\mathrm{TV}}(\mu_{\overrightarrow{P{ }}}, \mu_{\overrightarrow{R{ }}}) \leq \frac{2L}{H}
が成り立つ。

証明. \mathbf{A} \subset \mathbb{Z}を任意にとる。このとき、

\displaystyle \mu_{\overrightarrow{R{ }}}(\mathbf{A}) = \frac{1}{H}\sum_{l \in [L]}\mu_{\overrightarrow{R^l}}(\mathbf{A}) = \frac{1}{LH}\sum_{l \in [L]}\#\{h\in l+[H] \mid P(h) \in \mathbf{A}\}

なので、

\displaystyle \mu_{\overrightarrow{R{ }}}(\mathbf{A})-\mu_{\overrightarrow{P{ }}}(\mathbf{A}) = \frac{1}{LH}\sum_{l \in [L]}\left(\#\{h\in l+[H] \mid P(h) \in \mathbf{A}\}-\#\{h\in [H] \mid P(h) \in \mathbf{A}\}\right)

が成り立つ。[H]とl+[H]が重ならない部分は高々2Lなので、

\displaystyle \left|\mu_{\overrightarrow{R{ }}}(\mathbf{A})-\mu_{\overrightarrow{P{ }}}(\mathbf{A}) \right| \leq \frac{1}{LH}\sum_{l \in [L]}2L = \frac{2L}{H}

が得られる。\mathbf{A}は任意だったので証明が完了する。 Q.E.D.

APからなる集合\mathcal{P} \subset \mathcal{AP}が非有界であるとは、集合\{\mathrm{len}(\overrightarrow{P{ }}) \mid \overrightarrow{P{ }} \in \mathcal{P}\}が非有界であることと定義する。非有界な\mathcal{P} \subset \mathcal{AP}と\mathbf{A} \subset \mathbb{Z}に対して、\mathbf{A}の\mathcal{P}に沿った上密度\overline{d}_{\mathcal{P}}(\mathbf{A})を

\displaystyle \overline{d}_{\mathcal{P}}(\mathbf{A}) := \limsup_{\mathrm{len}(\overrightarrow{P{ }}) \to \infty, \ \overrightarrow{P{ }} \in \mathcal{P}}\mu_{\overrightarrow{P{ }}}(\mathbf{A})=\inf_{N \in \mathbb{Z}}\sup_{\overrightarrow{P{ }} \in \mathcal{P}, \ \mathrm{len}(\overrightarrow{P{ }}) \geq N}\mu_{\overrightarrow{P{ }}}(\mathbf{A})

と定義し、\mathbf{A}の\mathcal{P}に沿った下密度\underline{d}_{\mathcal{P}}(\mathbf{A})を

\displaystyle \underline{d}_{\mathcal{P}}(\mathbf{A}) := \liminf_{\mathrm{len}(\overrightarrow{P{ }}) \to \infty, \ \overrightarrow{P{ }} \in \mathcal{P}}\mu_{\overrightarrow{P{ }}}(\mathbf{A})=\sup_{N \in \mathbb{Z}}\inf_{\overrightarrow{P{ }} \in \mathcal{P}, \ \mathrm{len}(\overrightarrow{P{ }}) \geq N}\mu_{\overrightarrow{P{ }}}(\mathbf{A})

と定義する。定義から明らかに0 \leq \underline{d}_{\mathcal{P}}(\mathbf{A}) \leq \overline{d}_{\mathcal{P}}(\mathbf{A}) \leq 1が成り立つ。 \underline{d}_{\mathcal{P}}(\mathbf{A})= \overline{d}_{\mathcal{P}}(\mathbf{A})が成り立つとき、その値を\mathbf{A}の\mathcal{P}に沿った密度といい、d_{\mathcal{P}}(\mathbf{A})と表す。

例１) \mathcal{P} = \{\overrightarrow{[N]} \mid N \in \mathbb{N}\}の場合、\overline{d}_{\mathcal{P}}(\mathbf{A})は\mathbf{A}の上漸近密度で \underline{d}_{\mathcal{P}}(\mathbf{A})は下漸近密度、d_{\mathcal{P}}(\mathbf{A})は漸近密度(自然密度)である。

例２) \mathcal{P} = \{a+\overrightarrow{[N]} \mid a \in \mathbb{Z}, N \in \mathbb{N}\}の場合、\overline{d}_{\mathcal{P}}(\mathbf{A})は\mathbf{A}のBanach上漸近密度で \underline{d}_{\mathcal{P}}(\mathbf{A})はBanach下漸近密度、d_{\mathcal{P}}(\mathbf{A})はBanach漸近密度である(Banach上漸近密度しか使わない)。

\mathcal{P} \subset \mathcal{AP}は非有界とし、\mathbf{A} \subset \mathbb{Z}とする。任意の\varepsilon > 0に対してN \in \mathbb{N}が存在し、長さがN以上の\overrightarrow{P{ }} \in \mathcal{P}に対して

\displaystyle \mu_{\overrightarrow{P{ }}}(\mathbf{A}) \leq \overline{d}_{\mathcal{P}}(\mathbf{A})+\varepsilon −①

が成り立ち、いくらでも長さが大きい\overrightarrow{P{ }} \in \mathcal{P}が存在して

\displaystyle \left|\mu_{\overrightarrow{P{ }}}(\mathbf{A})- \overline{d}_{\mathcal{P}}(\mathbf{A})\right| \leq \varepsilon −②

が成り立つ。\mathbf{A}の\mathcal{P}に沿った密度が存在すれば、任意の\varepsilon > 0に対してN \in \mathbb{N}が存在して

\displaystyle \left|\mu_{\overrightarrow{P{ }}}(\mathbf{A})- d_{\mathcal{P}}(\mathbf{A})\right| \leq \varepsilon −③

が長さがN以上の\overrightarrow{P{ }} \in \mathcal{P}に対して成り立つ(定義の確認)。

注意) この記号設定においては、Szemerédiの定理は \overline{bd}(\mathbf{A}) > 0 \Longrightarrow \overline{d}_{\mathcal{AP}}(\mathbf{A})=1と簡潔に表現することができる。この同値性に関する\Longrightarrowは自明であるが、\Longleftarrowは次のように示す*1: K \in [N]を任意にとる。\overline{d}_{\mathcal{AP}}(\mathbf{A})=1が成り立つと仮定すると、②より

\displaystyle \#\{i \in [M] \mid P(i) \in \mathbf{A}\} \geq \left(1-\frac{1}{K+1}\right)M > M-L

が成り立つようなM-AP \overrightarrow{P{ }}が存在する(M=KL+N, L, N \in \mathbb{N}, 0 \leq N < K)。任意のl \in [L]に対してP( (l-1)K+[K]) \not \subset \mathbf{A}であると仮定すると

\displaystyle \#\{i \in [M] \mid P(i) \not \in \mathbf{A}\} \geq L

となって矛盾する。よって、或るl \in [L]が存在してP( (l-1)K+[K]) \subset \mathbf{A}となる。これは\mathbf{A}がK-APを含むことを示しており、Kは任意であるためSzemerédiの定理が従う。

補題２ (劣加法性) \mathbf{A}, \mathbf{B} \subset \mathbb{Z}と非有界な\mathcal{P} \subset \mathcal{AP}を考える。このとき、
\overline{d}_{\mathcal{P}}(\mathbf{A}\cup \mathbf{B}) \leq \overline{d}_{\mathcal{P}}(\mathbf{A}) + \overline{d}_{\mathcal{P}}(\mathbf{B})
が成り立つ。

証明. これは

\displaystyle \limsup \mu_{\overrightarrow{P{ }}}(\mathbf{A} \cup \mathbf{B}) \leq \limsup (\mu_{\overrightarrow{P{ }}}(\mathbf{A})+\mu_{\overrightarrow{P{ }}}(\mathbf{B}) ) \leq \limsup \mu_{\overrightarrow{P{ }}}(\mathbf{A})+\limsup \mu_{\overrightarrow{P{ }}}(\mathbf{B})

からわかる。 Q.E.D.

補題３ (上密度に対する鳩ノ巣原理) \mathcal{P} \subset \mathcal{AP}は非有界で、\mathbf{S} \subset \mathbb{Z}は\mathcal{P}に沿った上密度が正であるとする。このとき、\mathbf{S}をどのように有限色に類別しても、\mathcal{P}に沿った上密度が正であるような類が存在する。

証明. 劣加法性と背理法で示せる。 Q.E.D.

重要な概念を定義する。

定義 (二重カウンティンング性質) \mathcal{P} \subset \mathcal{AP}が二重カウンティング性質を持つとは以下の性質が成り立つときにいう: 任意の\varepsilon > 0に対してN_1(\varepsilon) \in \mathbb{N}が存在し、\varepsilonと任意の整数L \geq N_1(\varepsilon)に対してN_2(\varepsilon, L) \geq 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}に属するならば、高々\varepsilon H_1個の例外を除くL_1-AP (\overrightarrow{R_1})_h \ (h \in [H_1])は\mathcal{P}に属する。

とりあえず\mathcal{AP}は自明に二重カウンティング性質を満たす。二重カウンティンング性質の威力は次の命題の形で発揮される。

命題 \mathcal{P} \subset \mathcal{AP}は二重カウンティング性質を満たすとする。任意の\varepsilon > 0に対してN_1(\varepsilon) \in \mathbb{N}が存在し、\varepsilonと任意の整数N \geq N_1(\varepsilon)に対してN_2(\varepsilon, N) \geq Nが存在して、N_1(\varepsilon) \leq L \leq N_2(\varepsilon, L) \leq HなるL, H\in \mathbb{N}をとるとき、次が成立する。
(i) H-AP \overrightarrow{P{ }} \in \mathcal{P}に対して、高々\varepsilon H個の例外を除いてL-AP (P(h+l) )_{l \in [L]} \ (h \in [H])は\mathcal{P}に属する。
(ii) L\times H-長方形\overrightarrow{R{ }}に対して、L個のH-AP \overrightarrow{R^l} \ (l \in [L])が\mathcal{P}に属するならば、高々\varepsilon H個の例外を除いてL-AP \overrightarrow{R_h} \ (h \in [H])は\mathcal{P}に属する。

証明. (i)の証明: N_1(\varepsilon)は二重カウンティング性質の定義のものとし、N_2(\varepsilon, N)は定義のものと2N^2の\maxをとって再定義する。

\displaystyle \overrightarrow{R_1} := (P(h+l) )_{(l, h) \in [L]\times [H]}, \quad \overrightarrow{R_2} := (P(h) )_{(h, 1) \in [H] \times [1]}

とすると、(\overrightarrow{R_2})_1 = \overrightarrow{P{ }}\in \mathcal{P}である。また、補題１より

\displaystyle d_{\mathrm{TV}}(\mu_{\overrightarrow{R_1}}, \mu_{\overrightarrow{R_2}}) \leq \frac{2L}{H} \leq \frac{1}{L}

が成り立つので、\mathcal{P}の二重カウンティング性質をL_1=L, L_2=H, H_1=H, H_2=1として適用することにより、高々\varepsilon H個の例外を除いて、h \in [H]に対して

(\overrightarrow{R_1})_h = (P(h+l) )_{l \in [L]} \in \mathcal{P}

である。

(ii)の証明: \overrightarrow{R_1}:=\overrightarrow{R{ }}=(R(l, h) )_{(l, h) \in [L]\times [H]}として、\overrightarrow{R_2}を

\displaystyle \overrightarrow{R_2} := (R(l, h))_{(h, l) \in [H]\times [L]}

と定義する。このとき、二重カウンティング恒等式から

\displaystyle \mu_{\overrightarrow{R_1}} = \frac{1}{L}\sum_{l \in [L]}\mu_{\overrightarrow{(R_1)^l}}= \frac{1}{L}\sum_{l \in [L]}\mu_{\overrightarrow{R^l}}= \frac{1}{L}\sum_{l \in [L]}\mu_{\overrightarrow{(R_2)_l}}=\mu_{\overrightarrow{R_2}}

なので、d_{\mathrm{TV}}(\mu_{\overrightarrow{R_1}}, \mu_{\overrightarrow{R_2}}) = 0である。よって、 \mathcal{P}の二重カウンティング性質をL_1=L, L_2=H, H_1=H, H_2=Lとして適用することにより主張が従う。 Q.E.D.

*1:セミナー中に飛鳥さんに指摘していただきました。