Grahamの第一論文を読む -②

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

定義

定義１ $S$ を正の実数からなる数列とする。このとき、 $S$ が半完全であるとは、ある非負整数 $n_0$ が存在して、 $\mathbb{Z}_{\geq n_0} \subset P(S)$ が成り立つときにいう。

定義２ 正の実数からなる数列 $S$ が半完全であるとする。このとき、定義１における $n_0$ の役割を満たす最小の整数を $S$ の敷居という。 $S$ が半完全でなければ、敷居は $\infty$ と定義する。

$S$ が完全 $\Longleftrightarrow$ $S$ の敷居が $0$ .

定義３ 正の実数からなる数列 $S=\{a_n\}_{n=1}^{\infty}$ に対して、数列 $S^{-1}$ を $S^{-1} = \{ a_n^{-1}\}_{n=1}^{\infty}$ によって定義する。

定義４ $S=\{a_n\}_{n=1}^{\infty}$ を正の実数からなる数列とする。集合 $\Pi(S)$ を

$\displaystyle \Pi (s) := \left\{ \left. \prod_{i=1}^ma_{k_i} \right| m=1, 2, 3, \dots, \ \ \ k_1 < k_2 < \cdots < k_m \right\}$

と定める。このとき、 $\Pi (S)$ の元を小さい順に並べてできる単調増大数列を $M(S)$ と定義する。

主定理

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

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

を満たすようなものとする。このとき、正の有理数 $p/q\ \ ( (p, q)=1)$ が $P(M(S)^{-1})$ の元となるための必要十分条件は

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

が成り立つことである。

Grahamの第一論文を読むー③ - INTEGERSで次の定理を証明します：

定理１ $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})$ が成り立つ。

この記事では定理１から主結果を導きましょう。

まず、二つ目の仮定を次のように置き換えることができます：

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

$M(S)$ は半完全
$S$ は有界かつ $a_n > 1$ なる $n$ が無数に存在する
$\{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})$ が成り立つ。

定理１を仮定した定理２の証明

正の整数 $k, n_1, n_2, n_3, \dots$ であって

$n_1 < n_2 < n_3< \cdots$

$1 < k = a_{n_1}=a_{n_2}=a_{n_3}=\cdots$

を満たすようなものが存在する(二つ目の仮定から分かる)。このとき、

$a_1, \ k, \ a_2, \ k, \ k^2, \ a_3, \ k, \ k^2, \ k^3, \ a_4, \dots$

という順に並べて得られる新しい非有界数列を $S^*$ とする。正の整数 $m$ に対していくらでも大きい $l$ をとって $k^m=a_{n_l}a_{n_{l+1}}\cdots a_{n_{l+m}}$ とできることに注意すれば

$M(S)=M(S^*)$

が成り立つことが分かる( $S^*$ の項を順番に有限個掛け合わせたときに、 $k$ のべきはまとめて一番右端に持っていって考えればよい)。よって、 $S^*=\{a_n^*\}_{n=1}^{\infty}$ が定理１の仮定を満たしていることを示せば証明が完了する。確認すべきは $\{a_{n+1}^*/a_n^*\}$ が有界であることであるが、