Grahamの第二論文を読むー①

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

前回までにGrahamの第一論文を読み終えました。

一連のプロジェクトの目標は
integers.hatenablog.com

で紹介したGrahamの定理を証明することです。

それは分母が平方数であるようなエジプト分数の有限和として表すことができる有理数の特徴付けを与えるものですが、第二論文では平方数に限定せず、一般の $n$ 乗数の場合にも適用できる形で定理を証明します。

$n$ を正の整数とし、 $n$ 乗数を小さい順に $1^n, 2^n, 3^n, 4^n, \dots$ と並べてできる数列を $E(n)$ と表すことにします。すると、 $E(n)^{-1}$ は $n$ 乗数を分母に持つようなエジプト分数を大きいものから順に $1^{-n}, 2^{-n}, 3^{-n}, 4^{-n}, \dots$ と並べてできる数列になります。

このとき、目標は「集合 $P(E(n)^{-1})$ を決定すること」と表現することができます。正の実数からなる数列 $S$ に対して、集合 $\mathrm{Ac}(S)$ を

$\mathrm{Ac}(S) := \{ \alpha \in \mathbb{R}_{\geq 0} \mid \alpha\text{は}S\text{-近似可能}\}$

と定めます。すると、第一論文の主定理から次の定理が得られます：

定理１ 集合の等号

$P(E(n)^{-1}) = \mathrm{Ac}(E(n)^{-1}) \cap \mathbb{Q}$

が成り立つ。

証明. 定義上、 $0$ は両辺ともに入る。よって、正の有理数 $p/q$ ( $p, q$ は互いに素な正の整数)に対して、

$\displaystyle \frac{p}{q} \in P(E(n)^{-1}) \Longleftrightarrow \frac{p}{q} \in \mathrm{Ac}(E(n)^{-1})$ ー①

を示せばよい。

まず、 $E(n) = M(E(n) )$ であることに注意する。Spragueの定理

integers.hatenablog.com

より、 $E(n)$ は半完全である。

$E(n)=\{a_k\}_{k=1}^{\infty}$ とすると、

$\displaystyle \frac{a_{k+1}}{a_k} = \frac{(k+1)^n}{k^n} = \left( 1+ \frac{1}{k} \right)^n \xrightarrow{k \to \infty} 1$

なので、 $\{a_{k+1}/a_k\}_{k=1}^{\infty}$ は有界である。 $q$ が $E(n)$ のある項を割り切ることは自明
( $q \mid q^n$ である)。

従って、Grahamの第一論文の主定理

integers.hatenablog.com

より①が従う。 Q.E.D.

定理１によって、 $P(E(n)^{-1})$ を知るには $\mathrm{Ac}(E(n)^{-1})$ を知ればよいことがわかりました。なので、第二論文は正の実数からなる数列 $S$ に対して、 $\mathrm{Ac}(S)$ をより明示的に与える一般論を展開することから始まります。

この記事では定義１つと補題３つを片付けておくことにしましょう。

定義１ 正の実数からなる数列 $S=\{a_n\}_{n=1}^{\infty}$ の項 $a_n$ が $S$ において滑らかに置換可能であるとは、

$\displaystyle a_n \leq \sum_{k=1}^{\infty}a_{n+k}$

が成り立つときにいう。

補題１ 正の実数からなる数列 $S=\{a_n\}_{n=1}^{\infty}$ に対し、或る正整数 $m$ が存在して、

$n \geq m \Longrightarrow a_n \leq 2a_{n+1}$

が成り立つと仮定する。このとき、 $n \geq m$ ならば、 $a_n$ は $S$ において滑らかに置換可能である。

証明. $\displaystyle \sum_{k=1}^{\infty}a_k = \infty$ なら主張は自明となるため、 $\displaystyle \sum_{k=1}^{\infty}a_k < \infty$ と仮定する。このとき、

$\begin{align}n \geq m &\Longrightarrow a_{n+k} \geq \frac{1}{2}a_{n+k-1}, \ \ (k =1, 2, 3, \dots) \\ &\Longrightarrow \sum_{k=1}^{\infty}a_{n+k} \geq \frac{1}{2}\sum_{k=1}^{\infty}a_{n+k-1} = \frac{1}{2}a_n+\frac{1}{2} \sum_{k=1}^{\infty}a_{n+k}\end{align}$

が成り立つ。最後の条件は $a_n$ が $S$ において滑らかに置換可能であることと同値である。 Q.E.D.

これは、
integers.hatenablog.com
において紹介したSierpinskiの補題とBrownの命題における条件の関係と似ています。

補題２ 正整数 $k$ が $k \leq (2^{\frac{1}{n}}-1)^{-1}$ を満たし、 $k^{-n}$ が $E(n)^{-1}$ において滑らかに置換可能であると仮定する。このとき、 $(k+1)^{-n}$ も $E(n)^{-1}$ において滑らかに置換可能である。

証明.

$\begin{align}k \leq (2^{\frac{1}{n}}-1)^{-1} &\longleftrightarrow \frac{1}{k} \geq 2^{\frac{1}{n}}-1 \longleftrightarrow \left( 1+\frac{1}{k} \right)^n \geq 2 \longleftrightarrow \frac{(k+1)^n}{k^n} \geq 2 \\ &\longleftrightarrow k^{-n} \geq 2(k+1)^{-n}\end{align}$

であり、仮定より

$\displaystyle k^{-n} \leq \sum_{j=k+1}^{\infty}j^{-n}$

が成り立つので、

$\displaystyle 2(k+1)^{-n} \leq \sum_{j=k+1}^{\infty}j^{-n}$

を得る。これは

$\displaystyle (k+1)^{-n} \leq \sum_{j=k+2}^{\infty}j^{-n}$

と書き換えられ、 $(k+1)^{-n}$ が $E(n)^{-1}$ において滑らかに置換可能であることが示された。 Q.E.D.

補題３ 正整数 $k$ が $k \geq (2^{\frac{1}{n}}-1)^{-1}$ を満たすと仮定する。このとき、 $k^{-n}$ は $E(n)^{-1}$ において滑らかに置換可能である。

証明. 正整数 $r$ が $r \geq k$ を満たすならば、補題２の証明と同様の変形によって

$r^{-n} \leq 2(r+1)^{-n}$

が成り立つ。よって、補題１より $r \geq k$ なる $r$ に対して、 $r^{-n}$ は $E(n)^{-1}$ において滑らかに置換可能であることがわかる。特に、 $r=k$ としてもそうである。 Q.E.D.

Grahamの第二論文を読むー①

インテジャーズ

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