重み付き中間数に関する性質

ファレイ数列,近似,中間数

138

この記事は有理数が作る無限文字列についての考察の続きです。

有理数は全て既約分数として表すものとします。

前回のその後

この問題について数学を愛する会で共有したところ、ｻｲﾊﾞﾝﾁｮ( https://twitter.com/Saibanty0_math )さんより以下の補題と証明をいただきました。
(記事の形にするために一部表現を変更しています)

隣接している

有理数$ \frac{a}{c}, \frac{b}{d} $が隣接しているとは、$ ad - bc = \pm 1 $を満たすことである。

$ a, b, c, d \in \mathbb{Z}, c > 0, d > 0, a \perp c, b \perp d $とする。
$ \frac{a}{c}, \frac{b}{d} $と書ける$ 2 $つの有理数が隣接していることと、$ \frac{a}{c}, \frac{a + b}{c + d} $が隣接していることは、同値である。

$ \frac{a}{c}, \frac{b}{d} $が隣接する正の有理数でかつ$ c \leq d $であるとする。このとき、任意の$ 0 \leq k < c $を満たす整数$ k $に対して$ \frac{a}{c} \cdot k $と$ \frac{b}{d} \cdot k $の整数部分は等しい。

$ k = 0 $のとき、$ \frac{a}{c} \cdot k = \frac{b}{d} \cdot k = 0 $であるから明らか。
隣接の定義より$ ad - bc = \pm 1 $であるから、$ \frac{a}{c} - \frac{b}{d} = \pm \frac{1}{cd} $である。よって、$ \frac{k}{cd} < \frac{c}{cd} = \frac{1}{d} $より、
$ \frac{bk - 1}{d} < \frac{ak}{c} < \frac{bk}{d} $
が成り立つ。
$ 0 < k < c \leq d $より$ \frac{bk}{d} $は整数ではないので、
$ \lfloor \frac{bk}{d} \rfloor \leq \frac{bk - 1}{d} < \frac{bk}{d} < \lfloor \frac{bk}{d} \rfloor + 1 $
より題意が従う。

有理数$ \frac{a}{c}, \frac{b}{d} (c < d)$に対し、任意の$ 0 \leq k < c $を満たす整数$ k $に対して$ \frac{a}{c} \cdot k $と$ \frac{b}{d} \cdot k $の整数部分が等しいならば、$ \frac{a}{c} $と$ \frac{b}{d} $は隣接する。

量化の関係は$ \forall a, c, b, d ((\forall k\ P(a, c, b, d, k)) \Longrightarrow Q(a, c, b, d)) $です。

対偶を示す。

$ D = |ad - bc| \geq 2 $であると仮定する。
$ bk' \equiv 1 (\operatorname{mod} d) $を満たす$ 0 < k' < d $が存在するので、$ k = \max(k', d - k') $とすると、$ k \geq \frac{d}{2} $より
$ \left| \frac{a}{c} - \frac{b}{d} \right| \cdot k = \frac{D}{cd} \cdot k \geq \frac{2k}{cd} \geq \frac{1}{c} > \frac{1}{d} $
が成り立つ。
よって、$ \frac{a}{c} \cdot k < \frac{bk - 1}{d} $または$ \frac{a}{c} \cdot k > \frac{bk + 1}{d} $が成り立つ。
$ k = k' $の場合は$ \frac{a}{c} \cdot k < \frac{bk - 1}{d} (\in \mathbb{Z}) < \frac{b}{d} \cdot k $、$ k = d - k' $の場合は$ \frac{a}{c} \cdot k > \frac{bk + 1}{d} (\in \mathbb{Z}) > \frac{b}{d} \cdot k $が成り立つので、どちらの場合でも整数部分は異なる。

先行研究

ファレイ数列

$ n $に対応するファレイ数列$ F_n $とは、$ 0 $以上$ 1 $以下の分母が$ n $以下である有理数を小さい方から順に並べた数列である。

$ F_1 = \frac{0}{1}, \frac{1}{1} $
$ F_2 = \frac{0}{1}, \frac{1}{2}, \frac{1}{1} $
$ F_3 = \frac{0}{1}, \frac{1}{3}, \frac{1}{2}, \frac{2}{3}, \frac{1}{1} $
$ F_4 = \frac{0}{1}, \frac{1}{4}, \frac{1}{3}, \frac{1}{2}, \frac{2}{3}, \frac{3}{4}, \frac{1}{1} $
$ \vdots $

次の定理が知られています:

任意のファレイ数列の隣接する$ 2 $項$ \frac{a}{b}, \frac{c}{d} $に対して、$ ad - bc = 1 $が成り立つ。

証明は高校数学の美しい物語をご覧ください。

$ r $を$ 1 $以上$ 2 $未満の有理数とする。このとき、次の整数$ a, b, c, d > 0 $が存在する:

$ a $と$ b $は互いに素である。
$ c $と$ d $は互いに素である。
$ r = \frac{a + c}{b + d} $である。
任意の整数$ 0 \leq k < b $に対して、$ r \cdot k $と$ \frac{a}{b} \cdot k $の整数部分は等しい。

ファレイ数列の全ての項に$ 1 $を足して補題2と定理4を適用することで直ちにわかる。

主定理の証明の前に補題を$ 1 $つ示します。

整数$ a, b, c, d $が$ ad - bc = 1 $を満たしているとする。このとき、任意の整数$ m $に対して以下が成り立つ:

$ (a - cm)d - (b - dm)c = 1 $
$ a - cm $と$ b - dm $は互いに素

$ (a - cm)d - (b - dm)c = ad - cmd - bc + dmc = ad - bc = 1 $である。
また、仮に$ a - cm $と$ b - dm $に$ 2 $以上の公約数が存在するとすれば、この式の右辺が$ 1 $であることに矛盾するので$ a - cm $と$ b - dm $は互いに素である。

主定理: 一般分割定理

$ r $を$ 1 $以上$ 2 $未満の有理数とする。このとき、次の整数$ a, b, c, d, m > 0 $が存在する:

$ a $と$ b $は互いに素である。
$ c $と$ d $は互いに素である。
$ r = \frac{am + c}{bm + d} $である。
$ \frac{a}{b} < \frac{c}{d} $である。
$ bm > d $である。
任意の整数$ 0 \leq k < bm $に対して、$ r \cdot k $と$ \frac{a}{b} \cdot k $の整数部分は等しい。

定理4と比較すると、$ \frac{a}{b} $の分母と分子を$ m $倍して非既約分数として使ってよい代わりに、$ \frac{a}{b} < \frac{c}{d} $と$ bm > d $の条件が追加されていることが分かります。

定理4の$ a, b, c, d $を$ b > d $となるようにとり、$ m = 1 $としたときに定理5を満たしているならば、その場合はすでに証明終了であるためそうでない場合を考える。
すなわち、定理4の$ a, b, c, d$が$ b > d $かつ$ \frac{c}{d} < r < \frac{a}{b} $を満たしている場合を考える。
混同を避けるため、この条件を満たすように取った$ a, b, c, d $を$ a', b', c', d' $と書く。

$ r - \frac{c'}{d'} = \frac{1}{d'(b'+d')} $である。したがって、$ 0 \leq k < b' + d' $の範囲において$ r \cdot k $と$ \frac{c'}{d'} \cdot k $の整数部分は等しい。

ところで、仮定より$ b' > d' $であるから、$ b' + d' $を$ d' $で割った商を$ m' $、余りを$ s' $とすると、この$ m' $が条件を満たす$ m $である。以下でそのことを確認する。

$ r $を既約分数で表したものを$ \frac{p + q}{q} $とおき、$ a = c', b = d', c = p + q - c'm', d = q - d'm', m = m' $とする。

このとき、

定理4から$ a $と$ b $が互いに素であることは直ちに従う。
$ c $と$ d $が互いに素であることは補題5から従う。
$ r = \frac{am + b}{cm + d} $は取り方から明らか。
$ \frac{a}{b} < \frac{c}{d} $は下で示す。
仮定4より$ q = b' + d' $であるから$ d = s' $であり、$ bm \geq d' > d $が従う。
$ d'm' \leq b'+ d' $であるから「任意の整数$ 0 \leq k < bm $に対して、$ r \cdot k $と$ \frac{a}{b} \cdot k $の整数部分は等しい。」も成り立つ。

(2.の証明)
\begin{align*} & bc - ad \\ =& d'(p + q - c'm') - c'(q - d'm') \\\ =& d'(p + q) - c'q \\ =& d'q \cdot \left(\frac{p + q}{q} - \frac{c'}{d'} \right) \\ >& 0 \end{align*}

(Q.E.D.)