インテジャーズ

インテジャーズ

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

Grahamの第二論文を読む ー②

過去の記事を読むには上のカテゴリーをクリックしてください。前の記事で導入した記号・用語については説明を省略しています。

この記事では次の定理を証明します:

定理2 S=\{a_n\}_{n=1}^{\infty}を正の実数列であって、次の二条件を満たすようなものとする:

  • \displaystyle \lim_{n \to \infty}a_n = 0.
  • 自然数mが存在して、n \geq mならばa_nSにおいて滑らかに置換可能である。

このとき、

\displaystyle \mathrm{Ac}(S) = \bigcup_{a \in P_{m-1}}[a, a+\sigma )
が成り立つ。ただし、P_{m-1} := P(\{a_n\}_{n=1}^{m-1})であり(P_0:=\{0\})、\sigma := \sum_{k=m}^{\infty}a_kである(\sigma = \inftyでもよい)。

P_{m-1}は有限集合であることに注意しておきます。また、和の記号\sumにおいて、足す条件集合が空集合の場合は0と規約しておきます。

証明. まず、

\displaystyle \mathrm{Ac}(S) \subset \bigcup_{a \in P_{m-1}}[a, a+\sigma)

を証明する(なお、こちら側の証明にはSに関する条件を用いない)。そのためには、x \in \mathrm{Ac}(S)かつ\displaystyle x \not \in \bigcup_{a \in P_{m-1}}[a, a+\sigma)なるx \geq 0が存在したと仮定して矛盾を導けばよい。x \in \mathrm{Ac}(S)であることから、x \geq \sum_{k=1}^{\infty}a_kとなることはない(もしそうなったらxは明らかにS-近似可能ではない)。従って、\displaystyle x \not \in \bigcup_{a \in P_{m-1}}[a, a+\sigma)なる仮定より、或るa, b \in P_{m-1}が存在して、x \in [a+\sigma, b)が成り立ち、 a以外の任意のP_{m-1}の元cに対してc < aまたはb \leq cであるような状況にある。このとき、或る\delta > 0が存在してx \leq b-\deltaが成り立つ。

さて、P(S)の任意の元yに対してa_y \in P_{m-1}が存在して、y \in [a_y, a_y+\sigma)が成り立つ。実際、非負整数s, tおよび

1 \leq i_1 < i_2 < \cdots < i_s \leq m-1 < j_1 < j_2 < \cdots < j_t

が存在して

\displaystyle y = \sum_{u=1}^sa_{i_u}+\sum_{v=1}^ta_{j_v}

と書けるので、\displaystyle a_y :=  \sum_{u=1}^sa_{i_u}とすればよいことが分かる。

y \in P(S)に対して、a_y < aまたはb \leq a_yである。もし、y > xであればa_y < aにはなり得ないので、b \leq a_yとなり、

y \geq a_y \geq b \geq x+\delta

と評価できることが分かる。これはxより大きいP(S)の元はxと距離にして\deltaよりも近づくことはできないと言っているので、xS-近似可能(x \in \mathrm{Ac}(S))であるという仮定に矛盾する。


次に、

\displaystyle \bigcup_{a \in P_{m-1}}[a, a+\sigma) \subset \mathrm{Ac}(S)

を示そう。そのためには、\displaystyle x \in \bigcup_{a \in P_{m-1}}[a, a+\sigma)かつx \not \in \mathrm{Ac}(S)なるx \geq 0が存在したと仮定して矛盾を導けばよい。x \in [a, a+\sigma)なるa \in P_{m-1}をとって固定する。

a+P(\{a_n\}_{n=m}^{\infty})の元

\displaystyle a+\sum_{j=1}^{k}a_{i_j}, \quad m \leq i_1 < i_2 < \cdots < i_k

極小であるとは、

\displaystyle a+\sum_{j=1}^{k-1}a_{i_j} < x < a+\sum_{j=1}^{k}a_{i_j}

が成り立つときに言う*1Mを極小なa+P(\{a_n\}_{n=m}^{\infty})の元全体のなす集合とする。

主張 Mは無限集合である。

主張を証明するために、Mが有限集合であると仮定しよう。Mの元のP(S)の元としての表記に現れるa_nの添字nのうち、最大のものをIとする(有限の仮定から存在する)。そして、

\displaystyle \alpha = a+\sum_{j=1}^la_{i_j} + a_I, \quad m \leq i_1 < i_2 < \cdots < i_l < I

を、a_Iが実際に現れるようなMの元とする(l=0でもよい)。今、a_ISにおいて滑らかに置換可能なので

\displaystyle a+\sum_{j=1}^la_{i_j} < x < a+ \sum_{j=1}^{l}a_{i_j}+\sum_{k=1}^{\infty}a_{I+k}

が成立する。よって、

\displaystyle x < \beta = a+ \sum_{j=1}^la_{i_j} + \sum_{k=1}^da_{I+k}

なる最小のd \in \mathbb{N}が存在する。このとき、\beta \in Mは極小になっているが、a_{I+d}という項を用いており、I+d > IであることからIの最大性に矛盾する。これで主張の証明が完了する。


\delta := \inf \{\alpha - x\mid \alpha \in M\}とすると、x \not \in \mathrm{Ac}(S)なので、\delta > 0である。Sに関する一つ目の条件より、n \geq n_0ならばa_n < \delta /2となるような番号n_0が存在する。さて、n < n_0なるようなa_nのみを用いるa+P(\{a_n\}_{n=m}^{\infty})の元は有限個しか存在しないため、Mの元\alphaであって、

\displaystyle \alpha = a + \sum_{j=1}^ka_{i_j}, \quad m \leq i_1 < i_2 < \cdots < i_k, \ i_k \geq n_0

を満たすものが存在することが主張より分かる。このとき、

\displaystyle \alpha -a_{i_k} - x > \alpha - \frac{\delta}{2} - x = (\alpha - x) - \frac{\delta}{2} \geq \delta - \frac{\delta}{2} = \frac{\delta}{2} > 0

となって、\alphaが極小であることに矛盾する。以上で定理2の証明が完了する。 Q.E.D.

*1:x \not \in \mathrm{Ac}(S) \supset P(S)なので、定義の不等式において等号は成り立ちえない。