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)$ のある項を割り切る

が成り立つことである。

integers.hatenablog.com
で次の定理を証明します：

定理１ $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^*\}$ が有界であることであるが、

$\displaystyle \frac{a_{n+1}^*}{a_n^*} \leq \max \{k, a_1, a_2, a_3, \dots \} < \infty$

より成立する。 Q.E.D.

そして、２つ目の仮定は必要ないことが判明します：

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

$M(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})$ が成り立つ。

定理１を仮定した定理３の証明. もし、 $a_n > 1$ なる $n$ が有限個しか存在しないならば $M(S)$ は有限数列となるので、 $M(S)$ は半完全ではない。従って定理１または定理２の二つ目の仮定が成立することが分かる。 Q.E.D.

補題 $S$ を正の実数からなる数列、 $p/q$ を正の有理数とする( $p, q$ は正の整数で $(p, q)=1$ )。 $p/q \in P(M(S)^{-1})$ ならば

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

が成り立つ。

証明. 一つ目の条件は自明に成立する。 $p/q \in M(S)^{-1}$ なる仮定より、正整数 $r, n$ が存在して

$\displaystyle \frac{p}{q} = \frac{1}{a_{i_1}\cdots a_{i_k}}+\cdots +\frac{1}{a_{j_1}\cdots a_{j_m}} = \frac{r}{a_1\cdots a_n}$

と書ける。すなわち、 $pa_1\cdots a_n = qr$ を得るが、 $p$ と $q$ は互いに素であると仮定しているので

$q \mid a_1 \cdots a_n$

が成り立ち、 $a_1 \cdots a_n$ は $M(S)$ の項である。 Q.E.D.

以上で、定理１が証明できれば主定理が従うことが分かりました。