インテジャーズ

読者です 読者をやめる 読者になる 読者になる

インテジャーズ

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

Grahamの第一論文を読む ー③

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

定理1 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/qM(S)^{-1}-近似可能
  • qM(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 \thetaM(S)の敷居とする。M(S)は半完全という仮定より有限確定値を取る。

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

1.8 qM(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}を満たすものが存在して、

\begin{align} &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},\\ &\frac{N}{a_1\cdots a_{l_1}} < \frac{1}{t_{n_1}}\end{align}

が成り立つ。

理由: p/qM(S)^{-1}-近似可能なので、
integers.hatenablog.com
で示した補題を\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 整数ll > 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=1j=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+2v=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の場合

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

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

|c_j| := a_{i_1}\cdots a_{i_h}

と定義する。

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

5.3 f_1 := |c_1|.

5.4 f_kまで決まっているとき、f_{k+1}g > f_kg=|c_i| (或る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{|c_{k+1}|}{|c_k|} = \frac{a_{i_j+1}}{a_{i_j}} < A

が成立する(1.1より)。

5.7 (4.4)のc_kについては

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

が成立する(1.13より)。

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

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

が成り立つ。

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

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

が成り立つ。

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

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

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

\begin{align}&f_1=a_u, \\ &f_w \geq a_{u+1}a_{u+2}\cdots a_l.\end{align}

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)が成立する場合、cSのみから決まる)。

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_jb_1, \dots, b_mに一切現れない。今、(1.7)よりu > n_0であった。しかし、f_aa_u, \dots, a_lの幾つかの積として構成されている。また、b_1, \dots, b_mM(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)は完全である。

理由:正整数nn \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の判定法
integers.hatenablog.com

より、

\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}

が成り立つ。

6.25 整数k (1 \leq k \leq x)を

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

なる最小の整数としてとる( (6.6)から分かるb_xf_a \leq N^*-\theta = N^*より、N^*-b_xf_a \geq 0なのでこのようなkは存在する)。

6.26 k=1のとき。(6.24)より

 0 \leq N^{**}:=N^*-(b_x+\cdots +b_1)f_a < b_1f_a

が成り立つ。よって、

N^* = b_xf_a+ \cdots +b_1f_a + N^{**}

から、N^*について(3.5)を示すには

N^{**} \in P(M(\{a_i\}_{i=1}^l) )

を示せばよいことが、(6.17)と同様に示される。

6.27 (6.26)、(6.1)より0 =\theta \leq N^{**} < N^* < b_mf_wなので、(6.1)に戻ってN^{**}に対して同じ議論を行う。

6.28 k > 1のとき。

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

である(6.25)。よって、(6.25)と合わせて

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

が成り立つ。

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

なので、N^*について(3.5)を示すには

N^{**} \in P(M(\{a_i\}_{i=1}^l) )

を示せばよいことが、(6.17)と同様に示される。

6.29 (6.28)、(6.1)より0 =\theta \leq N^{**} < N^* < b_mf_wなので、(6.1)に戻ってN^{**}に対して同じ議論を行う
ことができる。

6.30 こうして、(6.18)、(6.27)、(6.29)とどのケースでも(6.1)に戻ってN^{**}に対して同様の議論を行うことができる。すると、N^{**} \to N^{***} \to N^{****}と何度でも(6.1)にループすることになるが、実際には

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

N^{\bullet}-\thetaが減少していくので、N^{\bullet}が非負整数であることからこのループは有限回で必ず停止し、(1.12)、(1.13)、(3.5)によって証明が完全に完了する。

Q.E.D.

これで、第一論文は読み終わりました。