インテジャーズ

INTEGERS

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

約数個数関数のラマヌジャンによる評価

この記事は日曜数学 Advent Calendar 2017 - Adventarの14日目の記事です。9日目はasangi_a4acさんによる

itonayuta60.hateblo.jp

でした。

クリスマスが待ち遠しいですね。Advent Calendarの日程も半分を超えていますが、クリスマスまでもう少しの辛抱です。

今日はRamanujanの論文を一つ読んでみようと思います。選んだ論文は

S. Ramanujan, On the number of divisors of a number, Journal of the Indian Mathematical Society, VII, 1915, 131-133.

です。

論文は5つのセクションからなり、正整数Nの正の約数の個数d(N)の上からの評価を与える公式を幾つか示すことが目的の論文となっています。約数は正の約数のみを考えることにしましょう。

1. 自明な評価

dNの約数であれば、必ずその共役な約数d'であってdd'=Nなるものが存在する。これは1から\sqrt{N}までのNの約数の個数は\sqrt{N}からNまでのNの約数の個数に等しいことを示している。N \geq 3であれば1からNの中にNの約数でない整数があることに注意すると、

d(N) < 2\sqrt{N}

がわかる。

2. Nの素因数分解が完全に判明している場合

Nの素因数分解がN=\prod_{i=1}^nq_i^{a_i}であったとする。このとき、d(N)=\prod_{i=1}^n(1+a_i)である。相加相乗平均の不等式より

\displaystyle \frac{1}{n}\sum_{i=1}^n(1+a_i)\log q_i > \sqrt[n]{\prod_{i=1}^n(1+a_i)\prod_{i=1}^n\log q_i}

なので

\displaystyle \frac{1}{n}\left(\sum_{i=1}^n\log q_i+\log N\right) > \sqrt[n]{d(N)\prod_{i=1}^n\log q_i}

であり

\displaystyle d(N) < \frac{\left(\frac{1}{n}\log(N\prod_{i=1}^nq_i)\right)^n}{\prod_{i=1}^n\log q_i}

が成り立つ。

3. Nの素因数の個数のみが判明している場合

Nの素因数の個数がn個であるとする。p_ii番目の素数とする。Nの素因数分解がN=\prod_{i=1}^nq_i^{a_i}であれば、N':=\prod_{i=1}^np_i^{a_i}とするとd(N')=d(N)が成り立つ。§2の結果より

\displaystyle d(N') < \frac{\left(\frac{1}{n}\log(N\prod_{i=1}^np_i)\right)^n}{\prod_{i=1}^n\log p_i}

が成り立つので、結局

\displaystyle d(N) < \frac{\left(\frac{1}{n}\log(N\prod_{i=1}^np_i)\right)^n}{\prod_{i=1}^n\log p_i}

と評価できる。

4. Nについて何も知らない場合

a_iを非負整数としてN= \prod_{i=1}^{\infty}p_i^{a_i}と表す。また、h > 0を任意にとって、x > 0x^h=2で定める。このとき、

\displaystyle \frac{d(N)}{N^h} = \prod_{i=1}^{\infty}\frac{1+a_i}{p_i^{ha_i}}.

p > xであれば

\displaystyle \frac{1+a_p}{p^{ha_p}} \leq \frac{1+a_p}{x^{ha_p}}=\frac{1+a_p}{2^{a_p}} \leq 1

なので、\pi(x)x以下の素数の個数とすれば

\displaystyle \frac{d(N)}{N^h} \leq \prod_{i=1}^{\pi(x)}\frac{1+a_i}{p_i^{ha_i}} \leq \prod_{i=1}^{\pi(x)}\frac{1+a_i}{2^{ha_i}}

が得られる。ここで、aの関数として増減表でも書いてみると

\displaystyle \frac{1+a}{2^{ha}} \leq \frac{2^h}{he\log 2}

がわかるので(a=(h\log 2)^{-1}-1で最大値をとる)、

\displaystyle \frac{d(N)}{N^h} \leq \left(\frac{2^h}{he\log 2}\right)^{\pi(x)}

を得る。h=\log 2/\log xなので、

\displaystyle d(N) \leq N^{\frac{\log 2}{\log x}}\left(\frac{2^{\frac{\log 2}{\log x}}\log x}{e(\log 2)^2}\right)^{\pi(x)}.

e^{\frac{1+2\log \log 2}{(\log 2)^2}} = 6.04737\cdotsなので、x \geq 6.05であれば2^h < e(\log 2)^2が成り立ち*1

\displaystyle d(N) < 2^{\frac{\log N}{\log x}}(\log x)^{\pi(x)}

なる評価が得られる。

5. Nについて何も知らない場合(N \to \inftyにおける漸近不等式)

x=\frac{\log N}{(\log \log N)^2}とおき、N \to \inftyにおける漸近挙動を考える。自明に\pi(x) = O(x)であることに注意する。

\begin{align} \log x &= \log \log N+O(\log \log \log N) \\ \frac{\log N}{\log x}&=\frac{\log N}{\log \log N} + O\left(\frac{\log N \log \log \log N}{(\log \log N)^2}\right) \\ \pi(x)\log \log x &= O(x \log \log x) = O\left(\frac{\log N \log \log \log N}{(\log \log N)^2}\right) \end{align}

が成り立つので、§4の不等式より

\begin{align} \log d(N) &< \frac{\log 2\log N}{\log x} + \pi(x)\log \log x \\ &= \frac{\log 2\log N}{\log \log N}+O\left(\frac{\log N\log \log \log N}{(\log \log N)^2}\right)\end{align}

が得られる。このセクションの結果をまとめると

定理 (Ramanujan, 1915) Nの正の約数の個数をd(N)と表すと、
\displaystyle \log d(N) < \frac{\log 2\log N}{\log \log N}+O\left(\frac{\log N\log \log \log N}{(\log \log N)^2}\right), \quad N \to \infty
が成り立つ。

integers.hatenablog.com

の結果と比較してみてください。

日曜数学 Advent Calendar 2017 15日目の記事はToshiki Takahashiさんによる「脳の長距離伸長戦略」です。

*1:6.05はRamanujanが選んだ数値。

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

定理 (混合補題) \mathcal{P}\subset \mathcal{AP}を非有界で二重カウンティング性質を満たすものとし、\mathbf{A} \subset \mathbb{Z}\mathcal{P}に沿った密度をもち、d_{\mathcal{P}}(\mathbf{A})=\deltaであるとする。任意の\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}をとり、L \times H-長方形\overrightarrow{R{ }}であって任意のl \in [L]に対して\overrightarrow{R^l} \in \mathcal{P}なるものをとるとき、次が成立する:
(i) (単混合) \mathbf{E} \subset [H]に対してl \in [L]が存在して
\#\{h \in \mathbf{E} \mid R(l, h) \in \mathbf{A}\} \geq \delta\#\mathbf{E}-\varepsilon H
が成り立つ。
(ii) (多重混合) A\leq C_{\varepsilon}を満たすA \in \mathbb{N}と、\mathbf{E}_1, \dots, \mathbf{E}_A \subset [H]に対してl \in [L]が存在して
\left|\#\{h \in \mathbf{E}_a \mid R(l, h) \in \mathbf{A}\}-\delta \#\mathbf{E}_a\right| \leq \varepsilon H
が任意のa \in [A]に対して成り立つ。ただし、C_{\varepsilon}記事2の系のA=O_{\varepsilon}(1)\varepsilon \mapsto \frac{\varepsilon}{3}としたときの定数*1
(iii) (高次多重混合) 有限集合\mathbf{W}で添字付けられる、集合\mathbf{E}_w \subset [H]からなる族\{\mathbf{E}\}_{w \in \mathbf{W}}に対してl \in [L]が存在して
\left|\#\{h \in \mathbf{E}_w \mid R(l, h) \in \mathbf{A}\}-\delta \#\mathbf{E}_w\right| \leq \varepsilon H
が高々\varepsilon \#\mathbf{W}個の例外を除くw \in \mathbf{W}に対して成立する。

(ii)の証明にvan der Waerdenの定理を用い、(iii)の証明に弱正則化補題(の系)を用いる。N_1, N_2は(i)〜(iii)で共通ではなく、証明中ではN_1^{(\mathrm{i})}のように表す。van der Waerdenの定理によって存在するN(k, m)N_{\mathrm{vdW}}(k, m)と表す。

証明. (i)の証明: N_1^{(\mathrm{i})}(\varepsilon)は記事4の命題のN_1(\varepsilon/2)および記事4の③の\varepsilon/2に対するN以上であるとし、N_2^{(\mathrm{ii})}(\varepsilon, N)は記事4の命題のN_2(\varepsilon/2, N)以上であるとする。すると、記事4の命題の(ii)より、高々\frac{\varepsilon}{2}H個の例外を除くh \in [H]に対して\overrightarrow{R_h} \in \mathcal{P}が成り立つ。このようなh \in [H]に対して記事4の③より

\displaystyle \mu_{\overrightarrow{R_h}}(\mathbf{A}) \geq \delta-\frac{\varepsilon}{2}

が成り立つ。このとき、

\displaystyle \#\{h \in \mathbf{E} \mid \overrightarrow{R_h} \not \in \mathcal{P}\} \leq \#\{h \in [H]\mid \overrightarrow{R_h} \not \in \mathcal{P}\} \leq \frac{\varepsilon}{2}H

より

\begin{align} \sum_{l \in [L]}\#\{h \in \mathbf{E} \mid \overrightarrow{R_h} \in \mathbf{A}\}&=\sum_{l \in [L]}\sum_{h \in \mathbf{E}}\mathbf{1}_{\mathbf{A}}(R(l, h) )=\sum_{h \in \mathbf{E}}\sum_{l \in [L]}\mathbf{1}_{\mathbf{A}}(R(l, h) )\\ &\geq \sum_{h \in \mathbf{E}, \ \overrightarrow{R_h} \in \mathcal{P}}\mu_{\overrightarrow{R_h}}(\mathbf{A})L \geq \left(\#\mathbf{E}-\frac{\varepsilon}{2}H\right)\left(\delta-\frac{\varepsilon}{2}\right)L \\ &\geq \delta L\#\mathbf{E}-\varepsilon LH\end{align}

と評価できる。よって、鳩の巣原理により或るl \in [L]が存在して

\#\{h \in \mathbf{E} \mid R(l, h) \in \mathbf{A}\} \geq \delta\#\mathbf{E}-\varepsilon H

が成り立つ。

(ii)の証明: L':=N_1^{(\mathrm{i})}(\varepsilon/2) \geq N_1^{(\mathrm{i})}(\varepsilon)として、N_1^{(\mathrm{ii})}(\varepsilon) \geq N_{\mathrm{vdW}}(L', 3^{C_{\varepsilon}}) \geq N_{\mathrm{vdW}}(L', 3^{A})およびN_2^{(\mathrm{ii})}(\varepsilon, N) \geq \max\{N_2^{(\mathrm{i})}(\varepsilon/2, L'), N, N(\varepsilon/2)\} \geq N_2^{(\mathrm{i})}(\varepsilon, L')を満たすようにN_1^{(\mathrm{ii})}, N_2^{(\mathrm{ii})}をとる(ただし、N(\varepsilon/2)は記事4の③のもの)。

[L]3^A色塗り分けc\colon [L] \to \{-1, 0, +1\}^Aを各l \in [L]に対してc(l) = (c_a(l) )_{a \in [A]}と表して、

\#\{h \in \mathbf{E}_a \mid R(l, h) \in \mathbf{A}\} < \delta \#\mathbf{E}_a-\varepsilon H

ならc_a(l):=-1,

\#\{h \in \mathbf{E}_a \mid R(l, h) \in \mathbf{A}\} > \delta \#\mathbf{E}_a+\varepsilon H

ならc_a(l):=+1,

\left|\#\{h \in \mathbf{E}_a \mid R(l, h) \in \mathbf{A}\}-\delta \#\mathbf{E}_a\right| \leq \varepsilon H

ならc_a(l)=0と定義する。

van der Waerdenの定理より、[L]に含まれる或るL'-AP \overrightarrow{Q{ }}および色c = (c_a)_{a \in [A]} \in \{-1, 0, +1\}^Aが存在して、任意のl' \in L'に対してc(Q(l') ) = cが成り立つ。

c_a=-1なるa \in [A]が存在したと仮定する。このとき、任意のl' \in [L']に対して

\#\{h \in \mathbf{E}_a \mid R(Q(l'), h) \in \mathbf{A}\} < \delta \#\mathbf{E}_a-\varepsilon H

が成り立つ。これは、\mathbf{E} \mapsto \mathbf{E}_aとしてL'\times H-長方形(R(Q(l'), h) )_{(l', h) \in [L'] \times [H]}に対する(i)の主張に矛盾する(\overrightarrow{Q{ }}がAPであるから長方形となることに注意)。

c_a=+1なるa \in [A]が存在したと仮定する。このとき、任意のl' \in [L']に対して

\#\{h \in \mathbf{E}_a \mid R(Q(l'), h) \in \mathbf{A}\} > \delta \#\mathbf{E}_a+\varepsilon H

が成り立つ。また、\overrightarrow{R^{Q(l')}} \in \mathcal{P}は長さHなので、記事4の③より

\displaystyle \#\{h \in [H] \mid R(Q(l'), h) \in \mathbf{A}\} \leq \delta H+\frac{\varepsilon}{2}H

である。よって、

\displaystyle \#\{h \in [H]\setminus \mathbf{E}_a \mid R(Q(l'), h) \in \mathbf{A}\} < \delta(H-\#\mathbf{E}_a)-\frac{\varepsilon}{2}H

なので、\mathbf{E} \mapsto [H]\setminus \mathbf{E}_a, \ \varepsilon \mapsto \frac{\varepsilon}{2}としてL'\times H-長方形(R(Q(l'), h) )_{(l', h) \in [L'] \times [H]}に対する(i)の主張にやはり矛盾する。

従って、任意のa \in [A]に対してc_a=0が示された。lとしては例えばQ(1)を選べる。

(iii)の証明: N_1^{(\mathrm{iii})}(\varepsilon) \geq N_1^{(\mathrm{ii})}(\frac{\varepsilon}{3C_{\varepsilon}})およびN_2^{(\mathrm{iii})}(\varepsilon, N) \geq N_2^{(\mathrm{ii})}(\frac{\varepsilon}{3C_{\varepsilon}}, N)を満たすようにN_1^{(\mathrm{iii})}, N_2^{(\mathrm{iii})}をとる。

弱正則化補題の系より、或るA\leq C_{\varepsilon}と分割

[H]=\mathbf{V}_1 \sqcup \cdots \sqcup \mathbf{V}_A,

a \in [A], w \in \mathbf{W}毎に0 \leq c_{a, w} \leq 1が存在して、任意の\mathbf{C} \subset [H]に対して

\displaystyle \left| \#\{\mathbf{C} \cap \mathbf{E}_w\} - \sum_{a \in [A]}c_{a, w}\#\{\mathbf{C} \cap \mathbf{V}_a\}\right| \leq \frac{\varepsilon}{3}H –①

が高々\frac{\varepsilon}{3}\#\mathbf{W}個の例外を除くw \in \mathbf{W}に対して成立する。

\mathbf{E}_a \mapsto \mathbf{V}_aとして(ii)を使うと、或るl \in [L]が存在して

\displaystyle \left|\#\{h \in \mathbf{V}_a \mid R(l, h) \in \mathbf{A}\}-\delta \#\mathbf{V}_a\right| \leq \frac{\varepsilon}{3A}H –②

が任意のa \in [A]に対して成り立つ。\mathbf{C}=\{h \in [H] \mid R(l, h) \in \mathbf{A}\}とすると①は

\displaystyle \left|\#\{h \in \mathbf{E}_w \mid R(l, h) \in \mathbf{A} \}-\sum_{a \in [A]}c_{a, w}\#\{h \in \mathbf{V}_a \mid R(l, h) \in \mathbf{A}\}\right| \leq \frac{\varepsilon}{3}H –③

となるので、②、③より

\begin{align} &\left|\#\{h \in \mathbf{E}_w \mid R(l, h) \in \mathbf{A}\}-\delta \sum_{a \in [A]}c_{a, w}\#\mathbf{V}_a\right| \\ &\leq \left|\#\{h \in \mathbf{E}_w \mid R(l, h) \in \mathbf{A}\}-\sum_{a \in [A]}c_{a, w}\#\{h \in \mathbf{V}_a \mid R(l, h) \in \mathbf{A}\}\right|\\ &\quad +\sum_{a \in [A]}c_{a, w}\left|\#\{h \in \mathbf{E}_w \mid R(l, h) \in \mathbf{A} \}-\delta \#\mathbf{V}_a\right| \\ &\leq \frac{\varepsilon}{3}H+\sum_{a \in [A]}c_{a, w}\frac{\varepsilon}{3A}H \leq \frac{2\varepsilon}{3}H \end{align} –④

が高々\frac{\varepsilon}{3}\#\mathbf{W}個の例外を除くw \in \mathbf{W}に対して成立する。

また、\mathbf{C}=[H]とすると①は

\displaystyle \left|\#\mathbf{E}_w-\sum_{a \in [A]}c_{a, w}\#\mathbf{V}_a\right| \leq \frac{\varepsilon}{3}H –⑤

となるので、④、⑤より高々\varepsilon \#\mathbf{W}個の例外を除くw \in \mathbf{W}に対して*2

\displaystyle \left|\#\{h \in \mathbf{E}_w \mid R(l, h) \in \mathbf{A}\}-\delta \#\mathbf{E}_w \right| \leq \frac{2\varepsilon}{3}H+\delta\cdot \frac{\varepsilon}{3}H \leq \varepsilon H


が成り立つことが示された。 Q.E.D.

*1:この選び方は(iii)を示すためのもの。

*2:\frac{\varepsilon}{3}\#\mathbf{W}+\frac{\varepsilon}{3}\#\mathbf{W} \leq \varepsilon \#\mathbf{W}.

セメレディの定理の組合せ論的証明ー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})=\deltaが成り立つ。極限の定義より、d_{\mathcal{P}'}(\mathbf{S})=\sigmaからd_{\mathcal{P}}(\mathbf{S})=\sigmaが従う。 Q.E.D.