2016-11-15

Grahamの第二論文を読むー②

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

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

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

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

このとき、

$\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$ よりも近づくことはできないと言っているので、 $x$ が $S$ -近似可能( $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}$

が成り立つときに言う*1。 $M$ を極小な $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_I$ は $S$ において滑らかに置換可能なので

$\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$ が極小であることに矛盾する。以上で定理２の証明が完了する。 Q.E.D.

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

2016-11-11

ポッキー＆プリッツの日

整数整数-145 整数-541 整数-829 整数-145829 整数-24133 整数-1111

$100$ 番目の素数は $541$ です*1。"今宵"と語呂合わせできますね。

integers.hatenablog.com

で紹介したように、 $2+3+5+7+11+\cdots + 541$ と最初の $100$ 個の素数を足すと $24133$ となって、これまた素数となります*2。

最初の $100$ 個の素数を並べると

$\begin{align}&2, \ 3, \ 5, \ 7, \ 11, \ 13, \ 17, \ 19, \ 23, \ 29, \ 31, \ 37, \ 41, \ 43, \ 47, \ 53, \ 59, \ 61, \ 67, \ 71, \ 73, \ 79, \\ &83, \ 89, \ 97, \ 101, \ 103, \ 107, \ 109, \ 113, \ 127, \ 131, \ 137, \ 139, \ 149, \ 151, \ 157, \ 163, \ 167, \\ &173, \ 179, \ 181, \ 191, \ 193, \ 197, \ 199, \ 211, \ 223, \ 227, \ 229, \ 233, \ 239, \ 241, \ 251, \ 257, \\ &263, \ 269, \ 271, \ 277, \ 281, \ 283, \ 293, \ 307, \ 311, \ 313, \ 317, \ 331, \ 337, \ 347, \ 349, \ 353, \\ &359, \ 367, \ 373, \ 379, \ 383, \ 389, \ 397, \ 401, \ 409, \ 419, \ 421, \ 431, \ 433, \ 439, \ 443, \ 449, \\ &457, \ 461, \ 463, \ 467, \ 479, \ 487, \ 491, \ 499, \ 503, \ 509, \ 521, \ 523, \ 541\end{align}$

となりますが、ここに現れる $271$ 個のアラビア数字を全部足してみましょう：

$\begin{align}&2+3+5+7+(1+1)+(1+3)+(1+7)+(1+9)+(2+3)+\cdots + (5+2+3)\\&+(5+4+1) = 1111\end{align}$

そうです。みんな大好き $1111$ になります。

それでは寒いので暖かくして今宵も素数を想いましょう*3。

コピペ確認用→
2+3+5+7+1+1+1+3+1+7+1+9+2+3+2+9+3+1+3+7+4+1+4+3+4+7+5+3+5+9+6+1+6+7+7+ 1+7+3+7+9+8+3+8+9+9+7+1+0+1+1+0+3+1+0+7+1+0+9+1+1+3+1+2+7+1+3+1+1+3+7+
1+3+9+1+4+9+1+5+1+1+5+7+1+6+3+1+6+7+1+7+3+1+7+9+1+8+1+1+9+1+1+9+3+1+9+
7+1+9+9+2+1+1+2+2+3+2+2+7+2+2+9+2+3+3+2+3+9+2+4+1+2+5+1+2+5+7+2+6+3+2+
6+9+2+7+1+2+7+7+2+8+1+2+8+3+2+9+3+3+0+7+3+1+1+3+1+3+3+1+7+3+3+1+3+3+7+
3+4+7+3+4+9+3+5+3+3+5+9+3+6+7+3+7+3+3+7+9+3+8+3+3+8+9+3+9+7+4+0+1+4+0+
9+4+1+9+4+2+1+4+3+1+4+3+3+4+3+9+4+4+3+4+4+9+4+5+7+4+6+1+4+6+3+4+6+7+4+
7+9+4+8+7+4+9+1+4+9+9+5+0+3+5+0+9+5+2+1+5+2+3+5+4+1

*1:そういえば、 $541$ をひっくり返した $145$ は $145=1!+4!+5!$ という面白い性質を持ちますね。 $145$ と言えば $145$ 番目の素数が $829$ ですが、 $145829$ も素数です。 $145$ は素数じゃないですが、 $1+4+5+8+2+9=29$ で割り切れます ( $145=5\times 29$ )。