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

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

150

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

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

前回のその後

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

隣接している

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

$a, b, c, d \in Z, c > 0, d > 0, a ⊥ c, b ⊥ 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$ であるから明らか。
隣接の定義より $a d - b c = \pm 1$ であるから、 $\frac{a}{c} - \frac{b}{d} = \pm \frac{1}{c d}$ である。よって、 $\frac{k}{c d} < \frac{c}{c d} = \frac{1}{d}$ より、
$\frac{b k - 1}{d} < \frac{a k}{c} < \frac{b k}{d}$
が成り立つ。
$0 < k < c \leq d$ より $\frac{b k}{d}$ は整数ではないので、
$⌊ \frac{b k}{d} ⌋ \leq \frac{b k - 1}{d} < \frac{b k}{d} < ⌊ \frac{b k}{d} ⌋ + 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)) ⟹ Q (a, c, b, d))$ です。

対偶を示す。

$D = | a d - b c | \geq 2$ であると仮定する。
$b k^{'} \equiv 1 (\mod d)$ を満たす $0 < k^{'} < d$ が存在するので、 $k = max (k^{'}, d - k^{'})$ とすると、 $k \geq \frac{d}{2}$ より
$| \frac{a}{c} - \frac{b}{d} | \cdot k = \frac{D}{c d} \cdot k \geq \frac{2 k}{c d} \geq \frac{1}{c} > \frac{1}{d}$
が成り立つ。
よって、 $\frac{a}{c} \cdot k < \frac{b k - 1}{d}$ または $\frac{a}{c} \cdot k > \frac{b k + 1}{d}$ が成り立つ。
$k = k^{'}$ の場合は $\frac{a}{c} \cdot k < \frac{b k - 1}{d} (\in Z) < \frac{b}{d} \cdot k$ 、 $k = d - k^{'}$ の場合は $\frac{a}{c} \cdot k > \frac{b k + 1}{d} (\in 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}$
$⋮$

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

任意のファレイ数列の隣接する $2$ 項 $\frac{a}{b}, \frac{c}{d}$ に対して、 $a d - b c = 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$ が $a d - b c = 1$ を満たしているとする。このとき、任意の整数 $m$ に対して以下が成り立つ:

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

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

主定理: 一般分割定理

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

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

定理4と比較すると、 $\frac{a}{b}$ の分母と分子を $m$ 倍して非既約分数として使ってよい代わりに、 $\frac{a}{b} < \frac{c}{d}$ と $b m > 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{a m + b}{c m + d}$ は取り方から明らか。
$\frac{a}{b} < \frac{c}{d}$ は下で示す。
仮定4より $q = b^{'} + d^{'}$ であるから $d = s^{'}$ であり、 $b m \geq d^{'} > d$ が従う。
$d^{'} m^{'} \leq b^{'} + d^{'}$ であるから「任意の整数 $0 \leq k < b m$ に対して、 $r \cdot k$ と $\frac{a}{b} \cdot k$ の整数部分は等しい。」も成り立つ。

(2.の証明)
$\begin{aligned} b c - a d \\ = & d^{'} (p + q - c^{'} m^{'}) - c^{'} (q - d^{'} m^{'}) \\ = & d^{'} (p + q) - c^{'} q \\ = & d^{'} q \cdot (\frac{p + q}{q} - \frac{c^{'}}{d^{'}}) \\ > & 0 \end{aligned}$