インテジャーズ

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

インテジャーズ

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

Grahamの第一論文を読む -②

Grahamの定理

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

定義

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

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

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

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

定義4 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/qM(S)^{-1}-近似可能
  • qM(S)のある項を割り切る

が成り立つことである。

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

定理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から主結果を導きましょう。

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

定理2 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/qM(S)^{-1}-近似可能
  • qM(S)のある項を割り切る

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

定理1を仮定した定理2の証明. 正の整数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}が定理1の仮定を満たしていることを示せば証明が完了する。確認すべきは\{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.

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

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

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

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

  • p/qM(S)^{-1}-近似可能
  • qM(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を得るが、pqは互いに素であると仮定しているので

q \mid a_1 \cdots a_n

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

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