インテジャーズ

インテジャーズ

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

Grahamの第一論文を読む -①

Grahamのエジプト分数に関する有名な結果の証明を完全に理解しようというプロジェクトを勝手に実施中です。

このプロジェクトは
integers.hatenablog.com

からスタートしました。

Grahamの定理の証明は非常に初等的な手法で実行されるのですが、Brownの判定法

integers.hatenablog.com

およびSpragueの定理

integers.hatenablog.com

を用いるので先に紹介しておきました(これらも非常に初等的に示されます)。


準備が整ったのでGrahamの論文の解説に移りますが、該当する論文は二つあります:


R. Graham, On finite sums of unit fractions, Proc. London Math. Soc. (1964), 193-207.

R. Graham, On finite sums of reciprocals of distinct nth powers, Pacific J. of Math. 14 (1) (1964), 85-92.


これらをそれぞれ順に第一論文第二論文と呼ぶことにしましょう。

早速、第一論文を読んでいきます。Grahamの定理の証明は第二論文で完結されるのですが、第一論文では与えられた有理数を特定の数列の項を分母に持つようなエジプト分数によって分解するための或る(必要)十分条件を与えています。すなわち、一般論を展開しています。

きっかりと有限個の(特定の形の)エジプト分数による分解を与えることに比べれば、「(特定の形の)エジプト分数の有限和によっていくらでも近似できるか」を問う方が簡単な問題になります(エジプト分数分解があれば近似出来ていることになるため。逆は一般には成り立たない)。

第一論文の主定理を非常に大雑把に述べると、

「ある数列の半完全性」という条件があれば、「近似可能性 ≒ 分解可能性」が言えてしまう。

という感じの主張です。

今回の記事では、定理で重要になってくる「近似可能性」についての補題を証明します。

定義

正の実数列Sに関して定まる集合P(S)の定義についてはBrownの判定法に関する記事を参照してください(特に空集合に関する\sum0と規約することに注意)。

定義 正の実数列Sと非負実数\alphaをとる。このとき、\alphaS-近似可能であるとは、任意の\varepsilon > 0に対して\beta \in P(S)が存在して
0 \leq \beta - \alpha < \varepsilon
であるときにいう。

上から近似する場合のみを考えるようです。

補題

しかし、下からも近似されます:

補題 正の実数からなる狭義単調減少数列S=\{a_k\}_{k=1}^{\infty}\displaystyle \lim_{k \to \infty}a_k=0を満たすとする。また、\alphaS-近似可能な非負実数とする。このとき、任意の\varepsilon > 0に対して、非負整数mおよび自然数k_1 < \cdots < k_{m}が存在して
\displaystyle 0 \leq \alpha - \sum_{i=1}^ma_{k_i} < \min \{ a_{k_{m}}, \varepsilon \}
が成立する。

証明. \alpha \in P(S)であれば題意は成り立つ。そこで、\alpha \not \in P(S)と仮定しよう。

Sの部分数列\{b_k\}_{k=1}^n

\displaystyle \alpha - \sum_{k=1}^nb_k < 0 < \alpha - \sum_{k=1}^{n-1}b_k

を満たすとき、\{b_k\}_{k=1}^nは"\alpha-special"であるということにする(n=1でもよい)。このとき、\alpha-specialなSの部分数列全体のなす集合は無限集合である。このことを以下示す。

\alpha-specialなSの部分数列が有限個しか存在しなかったと仮定して、それらの各項からできる集合をそれぞれA_1, \dots, A_tとする(少なくとも一つは存在することはすぐ後に示す)。集合T

\displaystyle T:= \left\{ \left. \sum_{a \in A_j}a - \alpha > 0 \right| 1 \leq j \leq t \right\}

と定義する。今、\varepsilon' > 0を何でもよいので一つ取って固定する。\alphaS-近似可能であるという仮定より、Sの部分数列\{b_k\}_{k=1}^nが存在して

\displaystyle 0 < \sum_{k=1}^nb_k -\alpha < \varepsilon'

が成り立つ(\alpha \not \in P(S)より"0 <"としてよい)。

\displaystyle \beta_j := \sum_{k=1}^{n-j+1}b_k - \alpha

としよう(j=1, \dots, n+1)。\beta_1 > 0\beta_{n+1} < 0であることと\alpha \not \in P(S)より、

\beta_{j-1} < 0 < \beta_{j}

なるj  \in \{1, \dots, n\}が存在する*1(等号は\alpha \not \in P(S)より成り立たない)。このとき、\{b_k\}_{k=1}^j\alpha-special。すなわち、Tは空集合ではない。


T\mathbb{R}_{> 0}の空でない有限部分集合なので、最小元\delta > 0が存在する。

また、\alphaS-近似可能であるという仮定から、Sの或る部分数列\{c_k\}_{k=1}^nが存在して

\displaystyle 0 < \sum_{k=1}^nc_k -\alpha < \delta

が成り立つ。

\displaystyle \gamma_j := \sum_{k=1}^{n-j+1}c_k - \alpha

としよう(j=1, \dots, n)。

\gamma_1 > 0であるが、実は\gamma_2 > 0も成り立つ。というのも、もし\gamma_2 < 0であれば(\alpha \not \in P(S)より\gamma_2\neq 0)、

\displaystyle \gamma_2 = \sum_{k=1}^{n-1}c_k - \alpha < 0 < \gamma_1 = \sum_{k=1}^nc_k - \alpha

より\{c_k\}_{k=1}^n\alpha-specialとなり、\gamma_1  \in Tを得る。しかし、\gamma_1 < \deltaなので\deltaの最小性に反する。

\gamma_2 > 0より、全く同じ論法によって\gamma_3 > 0を示せる。これを繰り返せば、\gamma_n > 0となった後に

-\alpha < 0 < \gamma_n = c_1-\alpha

となって(\alpha \not \in P(S)より\alpha \neq 0に注意)、一項数列\{c_1\}\alpha-special、すなわちc_1-\alpha \in Tとなる。しかし、やはりc_1-\alpha < \deltaであるから、\deltaの最小性に矛盾する。

よって、Tは無限集合であることが示された。

さて、自然数mおよびk_1 < \cdots < k_mであって、\{a_{k_i}\}_{i=1}^m\alpha-specialであり、かつ

a_{k_{m}} < \varepsilon

が成り立つようなものが存在する。何故ならば、Sは狭義単調減少数列であり\displaystyle \lim_{k\to \infty}a_k = 0であるため、上記不等式が成り立たないような\alpha-specialなSの部分数列は有限個しか存在しないからである(今、\alpha-specialなSの部分数列は無数に存在する)。

従って、\alpha-specialの定義より、

\displaystyle 0 < \alpha - \sum_{i=1}^{m-1}a_{k_i} < a_{k_m} < \min\{a_{k_{m-1}}, \varepsilon\}

を得る。 Q.E.D.