2016-09-13

Grahamの第一論文を読むー③

Grahamの定理

過去の記事を読むには上のカテゴリーをクリックしてください。

定理１ $S=\{a_n\}_{n=1}^{\infty}$ を正の整数からなる数列であって、

$M(S)$ は半完全
$S$ は非有界
$\{a_{n+1}/a_n\}_{n=1}^{\infty}$ は有界

を満たすようなもの、 $p/q$ ( $p, q$ は $(p, q)=1$ を満たす正整数)を

$p/q$ は $M(S)^{-1}$ -近似可能
$q$ は $M(S)$ のある項を割り切る

を満たすような正の有理数とする。このとき、 $p/q \in P(M(S)^{-1})$ が成り立つ。

証明.
1.1 $\{a_{n+1}/a_n\}_{n=1}^{\infty}$ は有界という仮定から、或る $A > 1$ が存在して

$\displaystyle \frac{a_{n+1}}{a_n} < A, \ \ \ n=1, 2, 3, \dots$

が成り立つ。

1.2 正の整数 $d$ を固定する。

1.3 $M(S) = \{b_n\}_{n=1}^{\infty}$ と表す。 $b_1 < b_2 < b_3 < \cdots$ .

1.4 正整数 $m$ を

$\displaystyle \frac{b_m}{b_d} > A$

となるように選ぶ( $S$ が非有界という仮定から存在が分かる)。

1.5 正整数 $n_0$ であって

$j \geq n_0 \Longrightarrow b_1, \dots, b_m$ のどの項にも $a_n$ の有限個の積として表した際に $a_j$ は現れない。

を満たすようなものが存在する。

1.6 $\theta$ を $M(S)$ の敷居とする。 $M(S)$ は半完全という仮定より有限確定値を取る。

1.7 正整数 $u$ を $u > n_0$ 、 $a_u > \theta$ を満たすように選ぶ( $S$ は非有界なので存在する)。

1.8 $q$ は $M(S)$ のある項を割り切るという仮定から、或る正整数 $r, e$ が存在して

$\displaystyle \frac{p}{q} = \frac{pe}{qe} = \frac{pe}{a_1a_2\cdots a_r}$

が成り立つ。

1.9 正整数 $l_1, n_1$ 、非負整数 $N$ および $M(\{a_n\}_{n=1}^{l_1})$ の項 $t_1, \dots, t_{n_1}$ であって $t_1 < t_2 < \cdots < t_{n_1}$ を満たすものが存在して、

$\displaystyle 0 \leq \frac{p}{q} - \sum_{j=1}^{n_1}\frac{1}{t_j} = \frac{N}{a_1 \cdots a_{l_1}} < \frac{1}{a_1\cdots a_u},\quad \frac{N}{a_1\cdots a_{l_1}} < \frac{1}{t_{n_1}}$

が成り立つ。

理由: $p/q$ は $M(S)^{-1}$ -近似可能なので、Grahamの第一論文を読む -① - INTEGERSで示した補題を $\varepsilon = 1/(a_1 \cdots a_u)$ として適用する( $M(S)$ は狭義単調増加数列であり、 $S$ が非有界であることから補題の仮定が満たされることが分かる)。

$\displaystyle \frac{p}{q} - \sum_{j=1}^{n_1}\frac{1}{t_j} = \frac{N}{a_1 \cdots a_{l_1}}$

と書けることは1.8より分かる。

1.10 $N = 0$ ならば証明は完了するため、 $N > 0$ と仮定する。

1.11 $S$ が非有界なので

$a_{l_1+1}a_{l_1+2}\cdots a_{l_2} \geq \theta$

を満たすような整数 $l_2$ が存在する。

1.12 $M(S)$ が半完全であり、 $\theta$ がその敷居なので(1.6)、

$\theta \leq k \leq b_da_u+\theta \Longrightarrow k \in P(M(\{a_n\}_{n=1}^{l_3}) )$

を満たすような正整数 $l_3$ が存在する。

1.13 整数 $l$ を $l > l_2+l_3+u, \ \ a_ua_{u+1} < a_l$ を満たすように選ぶ( $S$ 非有界より存在)。

2.1 $N^* := Na_{l_1+1}a_{l_1+2}\cdots a_l$ と整数 $N^*$ を定義する。

2.2 (1.11)より $N^* \geq a_{l_1+1}\cdots a_l \geq \theta$ が成り立つ。

2.3 (2,1)、(1.9)より

$\displaystyle \frac{N^*}{a_1\cdots a_l} = \frac{N}{a_1 \cdots a_{l_1}} < \frac{1}{a_1\cdots a_u},$

よって、 $N^* < a_{u+1} \cdots a_l$ が成り立つ( (1.13)より $l > u$ )。

2.4 (2.2)、(2.3)より

$0 \leq N^*-\theta < a_{u+1} \cdots a_l$

が成立する。

3.1 $N^* \in P(M(\{a_n\}_{n=1}^l) )$ と仮定する。このとき、正整数 $n_2$ および $u_1, \dots, u_{n_2} \in M(\{a_n\}_{n=1}^l)$ であって

$u_1 < u_2 < \cdots < u_{n_2}$

および

$\displaystyle \sum_{k=1}^{n_2}u_k = N^*$

を満たすようなものが存在する( $P(\ )$ の定義)。

3.2

$\displaystyle \frac{N^*}{a_1\cdots a_l} = \sum_{k=1}^{n_2}\frac{u_k}{a_1a_2\cdots a_l} = \sum_{k=1}^{n_2}\frac{1}{t'_k}$

とすると、(3.1)より $t'_k \in M(\{a_n\}_{n=1}^l)$ および

$t'_1 > t'_2 > \cdots > t'_{n_2}$

が成り立つ。

3.3 (2.3)、(1.9)より

$\displaystyle \frac{N^*}{a_1\cdots a_l}=\frac{N}{a_1\cdots a_{l_1}} < \frac{1}{t_{n_1}}$

なので、

$\displaystyle \frac{1}{t'_{n_2}} < \frac{1}{t_{n_1}}$

が成り立つ。

3.4 (1.9)、(3.2)より

$\displaystyle \frac{p}{q} = \sum_{k=1}^{n_1}\frac{1}{k}+\frac{N^*}{a_1\cdots a_l} = \sum_{j=1}^{n_1}\frac{1}{t_j}+\sum_{k=1}^{n_2}\frac{1}{t'_k}$

が成り立ち、(3.3)より $t_1, \dots, t_{n_1}, t'_1, \dots, t'_{n_2}$ は相異なる $M(\{a_n\}_{n=1}^l)$ の元である。故に

$\displaystyle \frac{p}{q} \in P(M(S)^{-1})$ .

3.5 よって、

$N^* \in P(M(\{a_n\}_{n=1}^{l}) )$

を示すことに帰着された。

4.1 $\mathbb{S}$ を $\{a_1, a_2, \dots \}$ の生成する自由半群とする(積は $\circ$ で表す)。 $\mathbb{S}$ の元からなる有限列 $\{c_k\}_{k=1}^{s}$ を次のように定める。

4.2 $c_1 := a_u$ .

4.3 $c_k = a_{i_1}\circ a_{i_2}\circ \cdots \circ a_{i_h},\ u \leq i_1 < i_2 < \cdots < i_h \leq l$ と仮定する。このとき、 $l \geq i_j+1 \neq i_1, i_2, \dots, i_h$ となるような最大の $1 \leq j \leq h$ をとって、

$c_{k+1} := a_{i_1}\circ \cdots a_{i_{j-1}}\circ a_{i_j+1}\circ a_{i_{j+1}}\circ \cdots \circ a_{i_h}$

と定める。ただし、 $j=1$ や $j=h$ のときは $a_{i_{j}+1}$ が端っこにくる。

4.4 $c_k=a_v\circ a_{v+1}\circ \cdots \circ a_l$ のとき(ただし、 $u+2 \leq v \leq l$ )、

$c_{k+1} := a_u\circ a_{u+1} \circ a_v\circ a_{v+1}\circ \cdots \circ a_{l-1}$

と定める(1.13より $l > u+2$ 。 $v=l$ のときは $c_{k+1}=a_u\circ a_{u+1}$ )。

4.5 (4.3)、(4.4)を繰り返して、 $c_s=a_{u+1}\circ a_{u+2}\circ \cdots \circ a_l$ となるまで続ける。

例) $u=5, l=8$ の場合

$\begin{align}c_1&=a_5\\ c_2&=a_6\\ c_3&=a_7\\ c_4&=a_8\\ c_5&=a_5\circ a_6\\ c_6&=a_5\circ a_7\\ c_7&=a_5\circ a_8\\ c_8&=a_6\circ a_8\\ c_9&=a_7\circ a_8\\ c_{10}&=a_5\circ a_6\circ a_7\\ c_{11}&=a_5\circ a_6\circ a_8\\ c_{12}&=a_5\circ a_7\circ a_8\\ c_{13}&=a_6\circ a_7\circ a_8\end{align}$

5.1 $c_j=a_{i_1}\circ \cdots \circ a_{i_h} \in \mathbb{S}$ に対して、 $\left|c_j\right| \in \mathbb{Z}_{>0}$ を

$\left|c_j\right| := a_{i_1}\cdots a_{i_h}$

と定義する。

5.2 正整数からなる狭義単調増大有限数列 $\{f_k\}_{k=1}^w$ を次のように定める。

5.3 $f_1 := \left|c_1\right|$ .

5.4 $f_k$ まで決まっているとき、 $f_{k+1}$ を $g > f_k$ 、 $g=\left|c_i\right|$ (或る $1 \leq i \leq s$ に対して)が成り立つような最小正整数として定める(そのような $g$ がなければその $f_k$ で終わりで $w=k$ とする。また、そうのような $i$ が複数ある場合は最小のものを取る)。

5.5 4節における $c_j$ の定義および上記 $f_k$ の定義より、 $k=1, \dots, w$ に対して $f_k \in M(\{a_n\}_{n=u}^l)$ である。

5.6 (4.3)の $c_k$ については

$\displaystyle \frac{\left|c_{k+1}\right|}{\left|c_k\right|} = \frac{a_{i_j+1}}{a_{i_j}} < A$

が成立する(1.1より)。

5.7 (4.4)の $c_k$ については

$\displaystyle \frac{\left|c_{k+1}\right|}{\left|c_k\right|} = \frac{a_ua_{u+1}}{a_l} < 1 < A$

が成立する(1.13より)。

5.8 つまり、任意の $i=1, 2, \dots, s-1$ について

$\displaystyle \frac{\left|c_{i+1}\right|}{\left|c_i\right|} < A$

が成り立つ。

5.9 任意の $k=1, 2, \dots, w-1$ に対して

$\displaystyle \frac{f_{k+1}}{f_k} < A$

が成り立つ。

理由： $f_k=\left|c_i\right|$ とする( $k \leq w-1$ )。このとき、 $\epsilon > 0$ が存在して $f_{k+1}=\left|c_{i+\epsilon}\right|$ と書ける。 $\epsilon = 1$ なら(5.8)よりOK。 $\epsilon \geq 2$ なら、 $f_{k+1}$ の定義より $\left|c_i\right| \geq \left|c_{i+\epsilon-1}\right|$ なので、(5.8)より

$\displaystyle \frac{f_{k+1}}{f_k} = \frac{\left|c_{i+\epsilon}\right|}{\left|c_i\right|} \leq \frac{\left|c_{i+\epsilon}\right|}{\left|c_{i+\epsilon-1}\right|} < A$ .

5.10 定義より次が成り立つ：

$\displaystyle f_1=a_u,\quad f_w \geq a_{u+1}a_{u+2}\cdots a_l.$

6.1 (2.4)、(5.10)、(1.4)より

$0 \leq N^*-\theta < a_{u+1}a_{u+2}\cdots a_l \leq f_w \leq b_mf_w$ .

6.2 $b_1f_1 > N^*-\theta$ と仮定する。このとき、(1.3)より $\{b_n\}_{n=1}^m$ が狭義単調増加であることと(ただし $m=1$ の可能性はある)、(5.10)より

$\theta \leq N^* < b_1f_1 + \theta \leq b_ma_u+\theta$ .

よって、(1.12)、(1.13)より $N^* \in P(M(\{a_n\}_{n=1}^l) )$ が言えて、(3.5)より証明が完了する。

6.3 以下、 $b_1f_1 \leq N^*-\theta$ と仮定する。

6.4 (1.4)、(5.9)より

$\displaystyle \frac{b_m}{b_1} \geq \frac{b_m}{b_d} > A > \frac{f_{k+1}}{f_k}$

なので、 $k=1, 2, \dots, w-1$ に対して

$b_mf_k> b_1f_{k+1}$

が成り立つ。

6.5 (6.3)、(6.1)より

$b_1f_1 \leq N^*-\theta < b_mf_w$

なので、 $x' \leq m-1$ なる正整数 $x'$ と $1 \leq a' \leq w$ なる整数 $a'$ が存在して

$b_{x'}f_{a'} \leq N^*-\theta < b_{x'+1}f_{a'}$

が成り立つ。

理由：存在しなかったと仮定する。このとき、

$b_1f_1 \leq b_2f_1 \leq \cdots \leq b_mf_1 \leq N^*-\theta$

より、(6.4)から $b_1f_2 \leq N^*-\theta$ が言え、

$b_1f_2 \leq b_2f_2 \leq \cdots \leq b_mf_2 \leq N^*-\theta$

より、(6.4)から $b_1f_3\leq N^*-\theta$ が言え、終いには $b_mf_w \leq N^*-\theta$ となって(6.1)に矛盾する。

6.6 そのような $x'$ で最大のものを $x$ 、そのときの $a'$ を $a$ とする。

$b_{x}f_{a} \leq N^*-\theta < b_{x+1}f_{a}$ .

6.7 $x < d$ と仮定する。このとき、 $b_df_1 > N^*-\theta$ が成り立つ。

理由： $b_df_1 \leq N^*-\theta$ と仮定する。このとき、

$b_{d+1}f_1 \leq N^*-\theta$

が成り立つ。というのも、 $b_{d+1}f_1 > N^*-\theta$ ならば

$b_df_1 \leq N^*-\theta < b_{d+1}f_1$

となって $x$ の最大性に反するからである( $x < d$ と仮定している)。

同じ議論を繰り返すと、

$b_{d+2}f_1 \leq N^*-\theta$

$\cdots$

$b_mf_1 \leq N^*-\theta$

が得られる。(1.4)、(5.9)より

$\displaystyle \frac{b_m}{b_d} > A > \frac{f_2}{f_1}$

なので、 $b_mf_1 > b_df_2$ が成り立つ。よって、

$b_df_2 \leq N^*-\theta$

が成立。これを出発点にして先ほどと同じ議論を行っていくと

$b_{d+1}f_2 \leq N^*-\theta$

$\cdots$

$b_mf_2 \leq N^*-\theta$

に辿り着く。(1.4)、(5.9)より

$\displaystyle \frac{b_m}{b_d} > A > \frac{f_3}{f_2}$

なので、 $b_mf_2 > b_df_3$ が成り立ち、

$b_df_3 \leq N^*-\theta$

が得られる。そうして、 $b_mf_3 \leq N^*-\theta$ が成立。

これを最後まで繰り返すと、遂には

$b_mf_w \leq N^*-\theta$

に到達し、(6.1)に矛盾する。

6.8 (2.2)、(6.7)、(5.10)より

$\theta \leq N^* < b_df_1+\theta = b_da_u+\theta$

が成り立つので、(1.12)より

$N^* \in P(M(\{a_n\}_{n=1}^l) )$

となって、(3.5)より証明が完了する。

6.9 よって、 $x \geq d$ と仮定する。

6.10 正整数 $c$ が存在して、

$k \geq c \Longrightarrow b_1+b_2+\cdots +b_k \geq b_{k+1}$

が成り立つと仮定する。

6.11 (1.2)で定めた $d$ は任意性があったので、 $d \geq c$ ととって良い(仮定(6.10)が成立する場合、 $c$ は $S$ のみから決まる)。

6.12

$\begin{align}&N^*-b_xf_a, \\ &N^*-(b_x+b_{x-1})f_a, \\&\cdots \\ &N^*-(b_x+b_{x-1}+\cdots +b_1)f_a\end{align}$

を考える。

6.13 (6.9)、(6.11)より $x \geq d \geq c$ なので、(6.10)より

$b_1+\cdots +b_x \geq b_{x+1}$

が成り立つ。よって、(6.6)より

$N^*-(b_x+\cdots +b_1)f_a \leq N^*-b_{x+1}f_a < \theta$ .

6.14 $k$ を

$N^*-(b_x+b_{x-1}+\cdots +b_k)f_a \geq \theta$

なる最小の整数とする。(6.6)より $N^*-b_xf_a \geq \theta$ なので、このような $k$ は必ず存在する。つまり、

$\begin{align}&2 \leq k \leq x,\\ &N^*-(b_x+b_{x-1}+\cdots +b_{k-1})f_a < \theta. \end{align}$

このとき、

$N^*-(b_x+b_{x-1}+\cdots +b_k)f_a < \theta + b_{k-1}f_a$

が成り立つ。

6.15 一方、 $\theta + b_{k-1}f_a < b_kf_a$ である。

理由：(5.10)、(1.7)より $f_a \geq a_u > \theta$ であり、(1.3)より $b_{k-1}+1 \leq b_k$ なので

$(b_k-b_{k-1})f_a \geq f_a > \theta$ .

6.16 すなわち、

$N^{**} := N^*-(b_x+b_{x-1}+\cdots +b_k)f_a < b_kf_a$

が示された。すると、

$N^* = b_xf_a+b_{x-1}f_a+\cdots +b_kf_a + N^{**}$

であり、(6.14)から

$\theta \leq N^{**} < \min \{b_kf_a, N^{*}\}$

が成り立つ。

6.17 $N^{**} \in P(M(\{a_n\}_{n=1}^l) )$ を示せばよい。

理由：(1.5)より $j \geq n_0$ ならば $a_j$ は $b_1, \dots, b_m$ に一切現れない。今、(1.7)より $u > n_0$ であった。しかし、 $f_a$ は $a_u, \dots, a_l$ の幾つかの積として構成されている。また、 $b_1, \dots, b_m$ は $M(S)$ の相異なる元である(1.3)。すると、

$b_xf_a, \dots, b_kf_a$

はそれぞれが $a_1, \dots, a_l$ の幾つかの積であり、どれも相異なることがわかる( (6.5)+(6.6)より $x \leq m-1$ であることに注意)。よって、

$b_xf_a+\cdots +b_kf_a \in P(M( \{a_n\}_{n=1}^l) )$

であることが分かる。また、(6.16)より

$N^{**} < b_kf_a < b_{k+1}f_a < \cdots < b_xf_a$

なので、 $N^{**} \in P(M( \{a_n\}_{n=1}^l) )$ が示されれば、 $b_kf_a, \dots, b_xf_a$ とかぶることはない。すなわち、

$N^* \in P(M( \{a_n\}_{n=1}^l) )$

となって、(3.5)より証明が完了する。

6.18 (6.16)、(6.1)より

$0 \leq N^{**}-\theta < N^*-\theta < b_mf_w$

が成り立つ。この後、(6.1)に戻って、 $N^*$ の代わりに $N^{**}$ について同様の議論を行うことになる( $< b_mf_w$ があれば同じ議論が出来る)。が、とりあえず(6.19)へ進む。

6.19 次に、任意の正整数 $c$ に対して正整数 $k_c$ が存在して、

$k_c \geq c$ かつ $b_1+b_2+\cdots +b_{k_c} < b_{k_c+1}$

であると仮定する。

6.20 このとき、 $M(S)$ は完全である。

理由：正整数 $n$ で $n \not \in P(M(S) )$ なるものが存在したと仮定する。すると、 $c=1, 2, 3, \dots$ に対して

$\displaystyle \sum_{j=1}^{k_c}b_j - n \not \in P(\{b_i\}_{i=1}^{k_c})$

が成り立つ(背理法(対偶)で簡単に確認出来る)。しかし、(6.19)より

$\displaystyle \sum_{j=1}^{k_c}b_j < b_{k_c+1} < b_{k_c+2} < \cdots$

であるから、

$\displaystyle \sum_{j=1}^{k_c}b_j - n \not \in P(M(S) )$

が $c=1, 2, 3, \dots$ で成立する。すなわち、 $P(M(S) )$ に属さない正整数が無数に存在することになって、 $M(S)$ が半完全であるという仮定に矛盾する。

6.21 よって、 $\theta = 0$ である。

6.22

$\begin{align}&N^* -b_xf_a, \\ &N^*-(b_x+b_{x-1})f_a, \\ &\cdots \\ &N^* -(b_x+b_{x-1}+\cdots +b_1)f_a\end{align}$

を考えよう。

6.23 (6.20)より $M(S)$ は完全なので、Brownの判定法より、

$\displaystyle \sum_{j=1}^kb_j \geq b_{k+1}-1$

が任意の非負整数 $k$ に対して成立する。

6.24 (6.23)より

$\begin{align}N^* - (b_x+\cdots +b_1)f_a &\leq N^* - (b_{x+1}-1)f_a \\ &=N^* - b_{x+1}f_a+f_a \\ &< f_a \ \ \ \ \ \ \ \ (\text{(6.6)} + (\theta = 0) ) \\ &\leq b_1f_a\end{align}$