Stern–Brocot木

同義語:Stern-Brocot木Stern–Brocotの木Stern–Brocot treeStern-Brocot tree

概要

Stern–Brocot木(Stern–Brocot tree)とは、$\frac01$ と $\frac10$ から始めて、隣り合う 2 つの分数 $\frac ab,\frac cd$ の間に中間数 $\frac{a+c}{b+d}$ を挟むことをくり返し、挟んだ分数を親子の関係で並べた根 $\frac11$ の 2 分木である。隣り合う 2 項はつねに $bc-ad=1$ を満たし、正の有理数はどれもちょうど 1 回、既約分数として現れる。根からの左右の曲がり方の塊の長さは連分数展開の部分商に一致し、深さ $k$ の節点は部分商の和が $k+1$ の分数である。開区間で深さが最小の節点は、その区間の分数のうち分子と分母が最小のものになり、語を逆に読むと Calkin–Wilf 木と Stern の 2 原子列による数え上げが得られる。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 有理数, 連分数, Euclidの互除法, 二分木

Stern–Brocot木(Stern–Brocot tree)は、$\frac01$ と $\frac10$ から始めて、隣り合う 2 つの分数 $\frac ab,\frac cd$ の間に 中間数(mediant)
$$ \frac{a+c}{b+d} $$
を挟むことをくり返し、挟んだ分数を親子の関係で並べた 2 分木である。根は $\frac11$ で、正の有理数がどれもちょうど 1 回ずつ、既約分数として現れる。根から分数までの左右の曲がり方を記録すると、その分数の 連分数 展開がそのまま読める。分数を「足し算だけ」で数え上げる仕組みであり、同じ構成は Fareyグラフ の三角形の作り方や、Minkowskiの疑問符関数 の定義にも現れる。
この記事では、すべての正の有理数がちょうど 1 回現れること(thm-sb-main)を証明し、木の路と連分数の対応(thm-sb-cf)、区間の中で分子・分母がいちばん小さい分数の求め方(thm-sb-simplest)、Calkin–Wilf 木と Stern の 2 原子列との関係を扱う。高校の範囲の紹介は 等式の証明と比例式 の節「大学数学で見る:Farey 数列と Stern–Brocot 木」にある。

定義

この記事では、分数 $\frac ab$ を非負整数の組 $(a,b)\ne(0,0)$ の形のまま扱い、$\frac10$ は「無限大」を表す記号とみる。分母が $0$ の分数との大小は、$\frac ab<\frac10$($b\ge1$)と約束する。分母が正の 2 つの分数については、$\frac ab<\frac cd$ と $ad< bc$ は同値である。

中間数と Stern–Brocot 列

分数 $\frac ab$ と $\frac cd$ の 中間数 を $\frac{a+c}{b+d}$ とする。Stern–Brocot 列 $\mathcal S_0,\mathcal S_1,\mathcal S_2,\dots$ を
$$ \mathcal S_0:=\Bigl(\frac01,\ \frac10\Bigr) $$
から始め、$\mathcal S_n$ の隣り合うどの 2 項の間にもその中間数を挟んで $\mathcal S_{n+1}$ を作ることで定める。$\mathcal S_n$ は $2^n+1$ 項からなる。

$\mathcal S_1=(\frac01,\frac11,\frac10)$、$\mathcal S_2=(\frac01,\frac12,\frac11,\frac21,\frac10)$、$\mathcal S_3=(\frac01,\frac13,\frac12,\frac23,\frac11,\frac32,\frac21,\frac31,\frac10)$ である。

Stern–Brocot 木

$\mathcal S_{n+1}$ を作るときに $\mathcal S_n$ の隣り合う 2 項 $\ell,r$ の間に挟んだ中間数 $m$ を、深さ $n$ の 節点 とよび、$\ell$ を $m$ の 左の祖先、$r$ を 右の祖先 とよぶ。$m$ の 左の子 を $\ell$ と $m$ の中間数、右の子 を $m$ と $r$ の中間数とする(どちらも $\mathcal S_{n+2}$ を作るときに挟まれる、深さ $n+1$ の節点である)。この親子の関係で節点を結んだ 2 分木を Stern–Brocot 木 という。根は $\frac11$ である。

深さ $n$ の節点は $2^n$ 個あり、$\mathcal S_{n+1}$ の項のうち $\mathcal S_n$ に無いものがちょうどそれである。深さ $2$ までは
$$ \frac11\ \longrightarrow\ \Bigl(\frac12,\ \frac21\Bigr)\ \longrightarrow\ \Bigl(\frac13,\ \frac23,\ \frac32,\ \frac31\Bigr) $$
である。根から節点への路を、左の子へ進むことを $L$、右の子へ進むことを $R$ と書いた語で表す。たとえば $\frac23$ の路は $LR$ である。

主定理

Stern–Brocot の定理
  1. 各 $\mathcal S_n$ は狭義に増加する列で、隣り合う 2 項 $\frac ab<\frac cd$ は $bc-ad=1$ を満たす。$\mathcal S_n$ に現れる分数はどれも既約である。
  2. 正の有理数はどれも、既約分数としてちょうど 1 つの節点に現れる。
  3. 非負整数を成分とする既約な分数 $\frac ab<\frac cd$($\frac10$ を含む)について、ある $\mathcal S_n$ で隣り合うことと、$bc-ad=1$ は同値である。
隣り合う 2 項の行列式は 1 のまま

$n$ についての帰納法で示す。$\mathcal S_0$ では $1\cdot1-0\cdot0=1$ である。$\mathcal S_n$ の隣り合う $\frac ab<\frac cd$ が $bc-ad=1$ を満たすとし、中間数 $\frac{a+c}{b+d}$ を挟むと、新しく隣り合う 2 組について
$$ b(a+c)-a(b+d)=bc-ad=1,\qquad (b+d)c-(a+c)d=bc-ad=1 $$
である。$b,d\ge0$ は $(b,d)\ne(0,0)$ を満たす(両方 $0$ なら $bc-ad=0$ になる)ので $b+d\ge1$ であり、分母が正の 2 項 $\frac ab,\frac{a+c}{b+d}$ では $b(a+c)-a(b+d)=1>0$ が $\frac ab<\frac{a+c}{b+d}$ を意味し、同様に $\frac{a+c}{b+d}<\frac cd$ である($d=0$ のときは約束により $\frac{a+c}{b+d}<\frac10$)。よって $\mathcal S_{n+1}$ も狭義に増加し、主張が $n+1$ で成り立つ。最後に、$\frac ab$ の隣の項 $\frac cd$ について $bc-ad=1$ なので、$a$ と $b$ の公約数は $1$ を割り切り、$\frac ab$ は既約である。$\square$

探索の手順は分子と分母の和で止まる

高々 1 回:節点は、作られた時点の列の隣り合う 2 項の間に、両者と異なる値として挟まれ(1 による)、以後のすべての列に残る。のちに挟まれる値は、その時点の列の隣り合う 2 項の間に狭義に入るので、すでに列にある値とは異なる。よって同じ値の節点は 2 つない。
少なくとも 1 回:$p,q\ge1$、$\gcd(p,q)=1$ とする。次の手順を考える。$\ell=\frac01$、$r=\frac10$ から始め、$\ell<\frac pq< r$ を保ちながら、$m$ を $\ell$ と $r$ の中間数として、$m=\frac pq$ なら止め、$\frac pq< m$ なら $r:=m$、$m<\frac pq$ なら $\ell:=m$ とする。$(\ell,r)$ はつねにある $\mathcal S_n$ の隣り合う 2 項で、$m$ は深さ $n$ の節点である。$\ell=\frac ab$、$r=\frac cd$ とおくと、$\frac ab<\frac pq<\frac cd$ と 1 から
$$ \alpha:=cq-dp\ge1,\qquad \beta:=bp-aq\ge1 $$
であり($d=0$ のときも $c=1$ なので $\alpha=q\ge1$)、展開すると
$$ \alpha a+\beta c=p(bc-ad)=p,\qquad \alpha b+\beta d=q(bc-ad)=q\qquad\text{(1)} $$
となる。よって $(a+b)+(c+d)\le\alpha(a+b)+\beta(c+d)=p+q$ である。1 回進むごとに $\ell$ か $r$ の一方が中間数に替わり、$a+b+c+d$ は $1$ 以上増えるので、手順は高々 $p+q$ 回で止まる。止まるのは $m=\frac pq$ となるときで、$\frac pq$ はある節点に(1 により既約分数として)現れる。$\square$

中間数への分け方はただ 1 通り

$\mathcal S_n$ で隣り合う 2 項が $bc-ad=1$ を満たすことは 1 で示した。逆に、既約な $\frac ab<\frac cd$ が $bc-ad=1$ を満たすとする。$\frac ab=\frac01$ かつ $\frac cd=\frac10$ なら $\mathcal S_0$ で隣り合う。そうでなければ $m:=\frac{a+c}{b+d}$ は分子・分母がともに正であり、$\gcd(a+c,b+d)$ は $(a+c)d-(b+d)c=-1$ を割り切るので既約である。2 により $m$ はある節点に現れる。その節点の左右の祖先を $\frac{a'}{b'},\frac{c'}{d'}$ とすると、$\frac{a'+c'}{b'+d'}$ も既約で値が $m$ に等しいので、列ベクトルとして
$$ v:=\binom ab,\quad w:=\binom cd,\quad v':=\binom{a'}{b'},\quad w':=\binom{c'}{d'},\qquad v+w=v'+w'=:\mu $$
である。行列式を $\det(x,y)$ と書くと $\det(v,\mu)=\det(v,w)=ad-bc=-1$ で、同様に $\det(v',\mu)=-1$ なので $\det(v-v',\mu)=0$ である。$\mu$ の成分は互いに素なので、$v-v'=t\mu$ となる整数 $t$ がある。$v,v'$ の成分は $0$ 以上で $\mu$ の成分以下($w,w'$ の成分が非負なので)だから $t\in\{-1,0,1\}$ であり、$t=\pm1$ なら $v$ か $v'$ が零ベクトルになって既約な分数を表さない。よって $v=v'$、$w=w'$ で、$\frac ab,\frac cd$ は $m$ を挟む直前の列で隣り合う。$\square$

証明の所在と名前

Hat22 は、$\frac10,\frac01,\frac11$ から中間数で頂点の名前を付けていく図形(Farey 図形)について、辺で結ばれることと行列式が $\pm1$ であることの同値(Proposition 1.1、p. 23)、名前がどれも既約であること(Corollary 1.2、p. 25)、どの既約分数も現れること(Proposition 1.3、p. 26)を、列の引き算(Euclidの互除法 の引き算の形)で示している。上の 2 の証明は、その逆向きの足し算を式 (1) の不等式で数えたものである。この構成は M. A. Stern(1858 年)と A. Brocot(1860 年)にさかのぼる(KS08 §2、p. 4 とその文献表。Stern の論文については Alk10 §1.2、pp. 4–5 も)。

2 から、Stern–Brocot 木は正の有理数の全体を数え上げる。深さの順、同じ深さの中では小さい順に並べると
$$ \frac11,\ \frac12,\ \frac21,\ \frac13,\ \frac23,\ \frac32,\ \frac31,\ \frac14,\ \frac25,\ \dots $$
となる。$\mathcal S_n$ のうち $\frac01$ から $\frac11$ までの部分は $\mathcal S_n$ の左半分で、$[0,1]$ の有理数を同じ仕組みで数え上げる。2 により、$n$ を十分大きくとった $\mathcal S_n$ の左半分から分母が $N$ 以下の項だけを残すと、位数 $N$ の Farey 数列(Farey数列(高校数学) の定義「Farey 数列」)が小さい順に得られる。

行列と連分数

路の語と分数の関係は行列で書ける。
$$ L:=\begin{pmatrix}1&0\\1&1\end{pmatrix},\qquad R:=\begin{pmatrix}1&1\\0&1\end{pmatrix} $$
とおき、$L,R$ の積の語 $W$ を $2\times2$ 行列とみる。$W$ を列ベクトル $\binom xy$ に掛けた結果 $\binom{x'}{y'}$ を分数 $\frac{x'}{y'}$ とみる。

節点の行列

路が語 $W$ の節点 $m$ の右の祖先と左の祖先は、$W$ の第 1 列と第 2 列が表す分数であり、$m$ は $W\binom11$ が表す分数である。

子へ進むと右から L か R が掛かる

根では $W$ は単位行列で、第 1 列 $\binom10$ が右の祖先 $\frac10$、第 2 列 $\binom01$ が左の祖先 $\frac01$、$\binom11$ が根 $\frac11$ である。路 $W$ の節点の右の祖先を $w$、左の祖先を $v$(列ベクトル)とし、$W=(w\ v)$ とする。左の子の祖先は、右が $v+w$(親)、左が $v$ なので、行列は $(v+w\ \ v)=(w\ v)L$ である。右の子の祖先は、右が $w$、左が $v+w$ なので $(w\ \ v+w)=(w\ v)R$ である。どちらも語の右に文字を足したものに一致する。節点は 2 つの祖先の中間数なので $W\binom11=v+w$ が表す分数である。$\square$

$\det L=\det R=1$ なので、lem-sb-matrix は thm-sb-main の 1 の $bc-ad=1$ の別の見方でもある。分数 $t>0$ に $\binom t1$ を対応させると、$R$ と $L$ は
$$ R\colon t\mapsto t+1,\qquad L\colon t\mapsto\frac{t}{t+1}=\cfrac1{1+\cfrac1t} $$
と働く。くり返すと $R^k(t)=t+k$、$L^k(t)=1/(k+1/t)$ である。

路と連分数

正の有理数 $x=[a_0;a_1,\dots,a_n]$($a_0\ge0$、$a_1,\dots,a_n\ge1$ は整数。$n=0$ なら $a_0\ge1$)について、$x$ の節点の路は
$$ R^{a_0}L^{a_1}R^{a_2}L^{a_3}\cdots X^{a_n-1}\qquad\bigl(X=R\ (n\ \text{が偶数}),\ X=L\ (n\ \text{が奇数})\bigr) $$
である。$x$ の 2 通りの連分数展開(連分数 の定理「有理数の連分数展開」の 3)のどちらからも同じ語が得られる。とくに $x$ の深さは $a_0+a_1+\cdots+a_n-1$ である。

左右の入れ替えは逆数をとること

語 $W$ の文字 $L$ と $R$ を入れ替えた語を $W^\ast$ とする。$J:=\begin{pmatrix}0&1\\1&0\end{pmatrix}$ について $JLJ=R$、$JRJ=L$ なので $W^\ast=JWJ$ であり、$J\binom11=\binom11$ から $W^\ast\binom11=JW\binom11$ である。$J$ は成分を入れ替えるので、lem-sb-matrix により、路 $W^\ast$ の節点は路 $W$ の節点の逆数である。
主張を $n$ についての帰納法で示す。thm-sb-main の 2 により節点はただ 1 つなので、語 $W$ について $W\binom11$ が $x$ を表せば、$W$ が $x$ の路である。$n=0$ では $x=a_0\ge1$ で、$R^{a_0-1}\binom11=\binom{a_0}1$ である。$n\ge1$ とし、$x_1:=[a_1;a_2,\dots,a_n]$ とおく。$a_1\ge1$ なので $x_1\ge1>0$ で、帰納法の仮定により $x_1$ の路は $W_1:=R^{a_1}L^{a_2}\cdots$(最後の指数は $a_n-1$)である。上の注意により $W_1^\ast=L^{a_1}R^{a_2}\cdots$ の節点は $\frac1{x_1}$ であり、$x=a_0+\frac1{x_1}$ なので
$$ R^{a_0}W_1^\ast\binom11=R^{a_0}\binom{1}{x_1}\cdot(\text{正の数}) $$
は $a_0+\frac1{x_1}=x$ を表す($R^{a_0}$ は分数に $a_0$ を足す)。$R^{a_0}W_1^\ast$ は主張の語である。2 通りの展開は $[a_0;\dots,a_{n-1},a_n]$ と $[a_0;\dots,a_{n-1},a_n-1,1]$ である。後者の語では、第 $n$ 番目の塊は最後の塊ではないので $X^{a_n-1}$(文字は前者の最後の塊と同じ $X$、個数も同じ)であり、最後の第 $n+1$ 番目の塊は指数が $1-1=0$ の空の語なので、2 つの語は一致する。深さは語の長さ $a_0+\cdots+a_{n-1}+(a_n-1)$ である。$\square$

深さと部分商の和

深さ $k$ の節点は、連分数展開の部分商の和 $a_0+a_1+\cdots+a_n$ が $k+1$ に等しい正の有理数の全体であり、その個数は $2^k$ である。

thm-sb-cf により節点の深さは部分商の和から $1$ を引いたものであり(2 通りの展開で和は等しい)、thm-sb-main の 2 により各正の有理数は 1 つの節点に現れる。深さ $k$ の節点は $2^k$ 個ある。$\square$

部分商の和が $k+1$ の分数がちょうど $2^k$ 個あるという数え上げは、Stern による観察として Alk10 §1.2(p. 5)に引かれている。

路の例

$\frac38=[0;2,1,2]$ の路は $R^0L^2R^1L^{1}=LLRL$ で、実際 $\frac11\to\frac12\to\frac13\to\frac25\to\frac38$ と進む($\frac38$ は $\frac13$ と $\frac25$ の中間数)。もう一方の展開 $[0;2,1,1,1]$ からも $L^2R^1L^1R^0=LLRL$ が得られる。$\frac{22}7=[3;7]$ の路は $R^3L^6$、深さは $9$ である。$\frac{355}{113}=[3;7,16]$ の路は $R^3L^7R^{15}$、深さは $25$ である。

無理数 $x>0$ については、$\ell< x< r$ となる隣り合う 2 項 $(\ell,r)$ が各 $\mathcal S_n$ にただ 1 組あり、$n$ を増やすとそれらの間の節点が根から下へ続く無限の路を作る。この路は $R^{a_0}L^{a_1}R^{a_2}\cdots$ の形で、塊の長さが $x$ の無限連分数展開 $[a_0;a_1,a_2,\dots]$ の部分商になる(有理数の場合の thm-sb-cf の極限の形で、この記事では証明しない。Hat22 Theorem 2.1(p. 39)と Proposition 2.3(p. 44)は、同じ対応を Farey 図形の三角形の帯と、$x$ の真上を通る直線が横切る三角形の列で述べる)。$x<1$ のとき、この路から最初の $L$ を除いた語の $L,R$ を 2 進数の $0,1$ と読んだ数が Minkowskiの疑問符関数 の値 $?(x)$ である。

いちばん簡単な分数

開区間に入る分数のうち、分子と分母がいちばん小さいものは木の上で探せる。

区間の中のいちばん簡単な分数

$0\le\alpha<\beta\le\infty$ とし、開区間 $(\alpha,\beta)$ に入る節点のうち深さが最小のものを $\frac uv$ とする。このとき $\frac uv$ はただ 1 つに定まり、$(\alpha,\beta)$ に入るどの正の既約分数 $\frac pq$ も $p\ge u$ かつ $q\ge v$ を満たす。

最小の深さの節点の下に区間の分数がすべてある

$(\alpha,\beta)$ は正の有理数を含むので、thm-sb-main の 2 によりそこに入る節点があり、深さが最小のものがとれる。$\frac uv$ をその 1 つとし、その左右の祖先を $\ell,r$ とする。$\frac pq\in(\alpha,\beta)$ を $\frac uv$ と異なる既約分数とし、$\frac pq$ の節点の路と $\frac uv$ の路が最後に共通する節点を $\nu$ とする。
$\nu\ne\frac uv$ と仮定する。$\nu$ は $\frac uv$ の真の祖先なので深さは $\frac uv$ より小さい。$\nu$ が $\frac pq$ と等しくなければ、2 つの路は $\nu$ から左右に分かれ、$\nu$ の左の子の下の節点は $\nu$ より小さく、右の子の下の節点は $\nu$ より大きい(子孫は、親を挟む 2 項の一方と親の間に挟まれるので)。よって $\nu$ は $\frac uv$ と $\frac pq$ の間にあり、$(\alpha,\beta)$ に入る。$\nu=\frac pq$ の場合も $\nu\in(\alpha,\beta)$ である。どちらも深さの最小性に反する。
よって $\nu=\frac uv$ で、$\frac pq$ は $\frac uv$ の真の子孫である。子孫は $\ell$ と $r$ の間に狭義に入るので、prf-sb-main-2 の式 (1) と同じく、$\ell=\frac ab$、$r=\frac cd$ に対して $\alpha'=cq-dp\ge1$、$\beta'=bp-aq\ge1$ を整数として
$$ p=\alpha'a+\beta'c\ge a+c=u,\qquad q=\alpha'b+\beta'd\ge b+d=v $$
を得る。同じ議論で深さ最小の節点が 2 つあれば一方は他方の真の子孫になり、深さが異なって矛盾するので、$\frac uv$ はただ 1 つである。$\square$

いちばん簡単な分数の例

区間 $(0.31,\,0.32)$ の場合、探索は $\frac11\to\frac12\to\frac13\to\frac14\to\frac27\to\frac3{10}\to\frac4{13}\to\frac5{16}$ と進み、$\frac5{16}=0.3125$ で初めて区間に入る。よって分母が $16$ 未満の分数はこの区間に無い。区間 $(3.14,\,3.15)$ では $\frac11\to\frac21\to\frac31\to\frac41\to\frac72\to\frac{10}3\to\frac{13}4\to\frac{16}5\to\frac{19}6\to\frac{22}7$ と進み、$\frac{22}7\approx3.1429$ が分子・分母とも最小の分数である。

Calkin–Wilf 木と Stern の 2 原子列

Stern–Brocot 木と同じ分数を別の順に並べる木がある。

Calkin–Wilf 木

根を $\frac11$ とし、節点 $\frac ab$ の左の子を $\frac a{a+b}$、右の子を $\frac{a+b}b$ とする 2 分木を Calkin–Wilf 木 という。

列ベクトルで書くと、左の子は $L\binom ab=\binom a{a+b}$、右の子は $R\binom ab=\binom{a+b}b$ である。したがって路が $W=w_1w_2\cdots w_k$($w_1$ が最初の一歩)の節点は $w_k\cdots w_2w_1\binom11$ が表す分数であり、lem-sb-matrix と比べて次が分かる。

2 つの木は語を逆に読むと一致する

Calkin–Wilf 木で路が $w_1w_2\cdots w_k$ の節点は、Stern–Brocot 木で路が $w_k\cdots w_2w_1$ の節点に等しい。とくに Calkin–Wilf 木の各深さの節点は、Stern–Brocot 木の同じ深さの節点を並べ替えたもので、正の有理数はどれも Calkin–Wilf 木にちょうど 1 回、既約分数として現れる。

前半は直前の計算と lem-sb-matrix による。語の逆転は長さ $k$ の語の全単射なので、深さ $k$ の節点の集合は 2 つの木で同じであり、後半は thm-sb-main の 2 から従う。$\square$

たとえば Calkin–Wilf 木で路 $LR$ の節点は $\frac11\to\frac12\to\frac32$ で、Stern–Brocot 木の路 $RL$ の節点 $\frac11\to\frac21\to\frac32$ と同じである。Calkin–Wilf 木の深さの順の並びは、次の整数列で書ける。

Stern の 2 原子列

$s(0)=0$、$s(1)=1$ とし、$n\ge1$ について
$$ s(2n)=s(n),\qquad s(2n+1)=s(n)+s(n+1) $$
で定める整数列 $s(0),s(1),s(2),\dots=0,1,1,2,1,3,2,3,1,4,3,5,2,5,3,4,1,\dots$ を Stern の 2 原子列(Stern's diatomic sequence)という。

2 原子列による数え上げ

Calkin–Wilf 木の節点に、根を $1$、番号 $n$ の節点の左の子を $2n$、右の子を $2n+1$ として番号を付けると、番号 $n\ge1$ の節点は $\dfrac{s(n)}{s(n+1)}$ である。したがって $n\mapsto\dfrac{s(n)}{s(n+1)}$ は正の整数の全体から正の有理数の全体への全単射で、$s(n)$ と $s(n+1)$ は互いに素である。

番号についての帰納法

番号 $1$ の根は $\frac11=\frac{s(1)}{s(2)}$ である($s(2)=s(1)=1$)。番号 $n$ の節点が $\frac ab=\frac{s(n)}{s(n+1)}$ なら、左の子 $\frac a{a+b}$ は
$$ \frac{s(2n)}{s(2n+1)}=\frac{s(n)}{s(n)+s(n+1)} $$
に、右の子 $\frac{a+b}b$ は $s(2n+2)=s(n+1)$ により $\frac{s(2n+1)}{s(2n+2)}=\frac{s(n)+s(n+1)}{s(n+1)}$ に等しい。番号は正の整数を重複なく尽くすので、prop-sb-cw により全単射であり、節点の分数は既約なので $s(n),s(n+1)$ は互いに素である。$\square$

Calkin–Wilf 木の名は N. Calkin と H. Wilf(2000 年)による。Alk10 §1.2(pp. 4–5)は、この木がどの正の有理数もちょうど 1 回含むことと、深さの順に読んだ分子の列が Stern の 2 原子列で上の漸化式を満たすことを述べている。

反例

thm-sb-main と prop-sb-cw の仮定は外せない。各行は仮定を 1 つだけ替える。

替えた仮定例成り立たなくなる結論
出発の 2 項の行列式が $1$$\frac13,\frac23$($bc-ad=3$)から中間数を挟む現れる分数が既約であること:最初の中間数が $\frac36$
出発の 2 項が $\frac01,\frac10$$\frac01,\frac11$ から始める(行列式は $1$)正の有理数がどれも現れること:$1$ より大きい分数、たとえば $\frac21$ は現れない
挟む数が中間数$\frac01,\frac11$ の間に算術平均を挟み続ける$(0,1)$ の有理数がどれも現れること:分母が 2 の冪の分数しか現れず、$\frac13$ は現れない
Calkin–Wilf の路を逆に読む路 $LR$ をそのまま Stern–Brocot 木で読む節点の一致:Calkin–Wilf 木の $LR$ は $\frac32$、Stern–Brocot 木の $LR$ は $\frac23$
表の確かめ
確かめを開く

1 行目:$\frac{1+2}{3+3}=\frac36$ は既約でない。2 行目:$\frac01$ と $\frac11$ の間に挟まれる数はすべて $0$ と $1$ の間にある(中間数は 2 項の間に入る)ので、$\frac21$ は現れない。3 行目:$0$ と $1$ の算術平均を挟み続けると、$n$ 回目までに現れる数は $\frac k{2^n}$($0\le k\le2^n$)の形で、$\frac13=\frac k{2^n}$ は $2^n=3k$ となって起こらない。4 行目:Stern–Brocot 木では $\frac11\to\frac12\to\frac23$、Calkin–Wilf 木では $\frac11\to\frac12\to\frac{1+2}2=\frac32$ である。

関連項目

参考文献

[1]
Allen Hatcher, Topology of Numbers, American Mathematical Society, 2022, 著者公開の改訂版(Revised Version, September 2024)の頁:§1.1, Proposition 1.1(p. 23)、Corollary 1.2(p. 25)、Proposition 1.3(p. 26);§2.1, Theorem 2.1(p. 39);§2.2, Proposition 2.3(p. 44)

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する