Farey(ファレイ)数列に関する個人的な証明

この記事は高校数学における整数を勉強した方であれば,ある程度理解ができるかと思われる. 主に,ユークリッドの互除法の仕組みや一次不定方程式 $ax+by=c$ あたりの知識を深く知っておくと読みやすい.

後,文中で現れる $gcd(p,q)$ は非負整数 $p,q$ の最大公約数を表す.

経緯
証明概要
証明手順
最後に

経緯

とある大学の授業でFarey数列について学んだ. ここで扱うFarey数列 $F_n　(n=1,2,3,...)$ とは,分母が $n$ 以下の0以上1以下のすべての既約分数を小さい順に並べてできる数列を指す. このとき,議論の都合上 $0=\frac{0}{1}, 1=\frac{1}{1}$ として扱うことにする. 例えば, $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}),...$ という感じになる. この数列を調べていくと以下の命題(A)が成り立ちそうである.

命題(A) : $F_n$ で連続する $\frac{b}{a},\frac{y}{x},\frac{d}{c}$ について, $\frac{y}{x}=\frac{b+d}{a+c}$ .

ここでは,便宜上 $\frac{b+d}{a+c}$ を $\frac{b}{a},\frac{d}{c}$ のmediantと呼ぶことにする. つまり,命題(A)は「Farey数列の連続する3数を取り出すと真ん中の数は左右のmediantになる」と主張する. もしこれが成り立つなら,Farey数列は綺麗な性質を持っていると感じる.この命題を自分で示せないかと考え,なんとか示すことができたので記事にした.

証明概要

証明の発想は「Farey数列自体がそもそも命題(A)を満たすように構成されていればいいのになぁ」という感じ. 具体的には以下の操作(T)から構成された数列 $G_n$ に対して, $G_n=F_n (n=1,2,3,...)$ を示す. 操作(T)から数列 $G_n$ が様々な性質を持つことが示せる.

操作(T)：数列 $G_1=F_1=(\frac{0}{1},\frac{1}{1})$ とする.数列 $G_{n}$ の連続する2数それぞれに対し,そのmediantの分母が $n+1$ になれば,その2数の間にmediantを挿入する. そうして構成された新しい数列を $G_{n+1}$ とする.

証明手順

まず,数列 $G_n$ に対して以下の性質(B)が成り立つ.

性質(B) : 数列 $G_n$ の連続する2数 $\frac{b}{a},\frac{d}{c}$ に対して, $ad-bc=1$ .

[証明]

まず $G_1=(\frac{0}{1},\frac{1}{1})$ について, $1×1-0×1=1$ となるから成り立つ. 次に操作(T)によって,数列 $G_n$ の連続する2数 $\frac{b}{a},\frac{d}{c}$ のmediant $\frac{b+d}{a+c}$ が挿入されたとする. このとき数列 $G_{n+1}$ の該当する並びとして $(...,\frac{b}{a},\frac{b+d}{a+c},\frac{d}{c},...)$ となるが, $ad-bc=1$ ならば, $a(b+d)-b(a+c)=ad-bc=1$ , $(a+c)d-(b+d)c=ad-bc=1$

となり性質(B)を保持する. よって数列 $G_n$ の構成から,性質(B)は成り立つ. ■

性質(B)を用いて,次の性質(B1),(B2)も示せる.

性質(B1) : 数列 $G_n$ に並ぶ項は全て既約分数である.

[証明]

数列 $G_n$ の連続する2数 $\frac{b}{a},\frac{d}{c}$ に対して,性質(B)より $ad-bc=1$ が成り立つが,これは $gcd(a,b)=gcd(c,d)=1$ を表す. ■

性質(B2) : 数列 $G_n$ は小さい数順に並んでいる.

[証明]

数列 $G_n$ の連続する2数 $\frac{b}{a},\frac{d}{c}$ に対して,性質(B)より $\frac{d}{c}-\frac{b}{a}=\frac{ad-bc}{ac}=\frac{1}{ac} \gt 0$ が成り立つ. なお $a,c$ は正の整数なので最後の不等号が成り立つ. ■

性質(B1),(B2)より,数列 $G_n$ は0以上1以下かつ分母が $n$ 以下の既約分数が小さい順に並んでいる. これより $F_n$ の部分列として $G_n$ があることを示せた. 次の証明として,数列 $G_n$ には0以上1以下かつ分母が $n$ 以下のすべての既約分数が出てくることを示す必要がある.

具体的には,数列 $G_{n-1}$ から操作(T)をする際,0以上1以下かつ分母が $n$ の既約分数が挿入されるような連続する2数 $\frac{b}{a},\frac{d}{c}$ について考えればよい. この2数の分母の組 $[a,c$ ]に着目していく.

ところで,0以上1以下かつ分母が $n$ の既約分数の個数について以下の命題(C),命題(D)が成り立つ.

命題(C) :0以上1以下で分母が $n(\geq 2)$ の既約分数の個数 $\varphi (n)$ は, $a+c=n$ かつ $gcd(a,c)=1$ を満たす非負整数の組 $[a,c$ ]の個数と等しい.

[証明]

0以上1以下の分母が $n$ の分数を小さい順に並べてみると

$0=\frac{0}{n},\frac{1}{n},...,\frac{a}{n},...,\frac{n-1}{n},\frac{n}{n}=1$ .

このとき,それぞれの分数 $\frac{i}{n}$ について $a=i,c=n-i$ とすると,

$gcd(a,c)=gcd(i,n-i)=gcd(i,(n-i)+i)=gcd(i,n)$ となり題意は成り立つ. ■

命題(D):操作(T)によって数列 $G_{n}$ で初めて現れる数は $\varphi(n)$ 個ある.

[証明]

数列 $G_{n}$ の分母列 $H_n$ を考えると, $H_{1}=(1,1)$ , $H_{2}=(1,1+1,1)=(1,2,1)$ , $H_{3}=(1,1+2,2,2+1,1)=(1,3,2,3,1)$ ,...のようになる.

この数列 $H_k (k=1,2,3,...)$ の連続する2数 $a,c$ は互いに素である. これは,性質(B)によって $ad-bc=1 (b,dは整数)$ となるから $gcd(a,c)=1$ が示せるためである. また $a+c=n$ かつ $gcd(a,c)=1$ を満たす非負整数の組 $[a,c$ ]は, $H_{n-1}$ 中に必ず連続する2数としてちょうど1か所で現れる.

これはユークリッドの互除法と同じ原理で,組 $[a,c$ ]に対して「大きい方から小さい方を引く」という操作を繰り返すと必ず[1,1]になるためである. 例えば、 $a=4,c=7$ とすると,

$[4,7]$ $\rightarrow$ $[4,7-4 ] = [4,3 ]$ $\rightarrow$ $[4-3,3] = [1,3]$ $\rightarrow$ $[1,3-1] = [1,2]$ $\rightarrow$ $[1,2-1] = [1,1]$ .

この一連の操作を文字 $a,c$ を用いて表すと,

$[a,c$ ] $\rightarrow$ $[a,c-a$ ] $\rightarrow$ $[a-(c-a),c-a$ ] $=$ $[2a-c,c-a$ ] $\rightarrow$ $[2a-c,c-a-(2a-c)$ ] $=$ $[2a-c,2c-3a$ ] $\rightarrow$ $[2a-c,2c-3a-(2a-c)$ ] $=$ $[2a-c,3c-5a$ ].

この操作を逆順に辿ってのみ対象の組 $[a,c$ ]が出てくるので $H_{n-1}$ 中にちょうど1か所だけで現れる. 逆順で辿るというのは一体どういうことか. これは $H_{n}$ の構成は $G_{n}$ の構成つまり操作(T)によるので,以下のような対応付けがされるということである.

$H_1 : [1,1] \leftrightarrow G_1 : (\frac{0}{1},\frac{1}{1})$ ,

$H_2(の部分列): [1,2] \leftrightarrow G_2(の部分列) : (\frac{0}{1},\frac{0+1}{1+1})=(\frac{0}{1},\frac{1}{2})$ ,

$H_3(の部分列) : [1,3] \leftrightarrow G_3(の部分列) : (\frac{0}{1},\frac{0+1}{1+2})=(\frac{0}{1},\frac{1}{3})$ ,

$H_4(の部分列): [4,3] \leftrightarrow G_4(の部分列) : (\frac{0+1}{1+3},\frac{1}{3})=(\frac{1}{4},\frac{1}{3})$ ,

$H_7(の部分列): [4,7] \leftrightarrow G_7(の部分列) : (\frac{1}{4},\frac{1+1}{4+3})=(\frac{1}{4},\frac{2}{7})$ ,

$H_{11}(の部分列): [4+7 ]=[11 ] \leftrightarrow G_{11}(の部分列) : (\frac{1+2}{4+7})=(\frac{3}{11})$ .

つまり,この場合 $G_{11}$ 中の $\frac{3}{11}$ は上のような手順で生成されたということを表しており,これはどの既約分数においてもただ1通りである.

さて,操作(T)によって数列 $G_{n}$ で初めて現れる数は $a+c=n$ かつ $gcd(a,c)=1$ を満たすの非負整数の組 $[a,c$ ]それぞれに対応する分母が $n$ の分数である. これと命題(C)により,数列 $G_{n}$ で初めて現れる数は $\varphi(n)$ 個ある. ■

以上の性質や命題を踏まえることでお待ちかねの命題(A)が示せる.

[命題(A)の証明]

$G_{n}=F_{n}(n=1,2,3,...)$ を $n$ に関する帰納法で示す.

まず, $G_{1}=F_{1}=(\frac{0}{1},\frac{1}{1})$ が成り立つ.

次に, $G_{n-1}=F_{n-1}$ が成り立つと仮定する.

操作(T)によって数列 $G_{n}$ が構成されるが,性質(B1)および命題(D)により0以上1以下で分母が $n$ の既約分数が $\varphi (n)$ 個新しく現れる. さらに性質(B2)より,それらの $\varphi (n)$ 個の既約分数はすべて相異なっており,小さい順に適切な場所へ挿入されて現れる. これは $F_{n}$ の並べ方に他ならず, $G_{n}=F_{n}$ . 以上より $G_{n}=F_{n}(n=1,2,3,...)$ は成り立ち,操作(T)の方法から命題(A)はただちに成り立つ. ■

最後に

ここでは,Farey数列の定義を「既約分数が小さい順に並んでいる数列」から「ある初期状態の数列からmediantを次々と挿入して出来る数列」というように言い換えられる事を出来るだけ噛み砕いて証明した. なおmediantという用語はWikipedeiaに記載されていたので,ここでも同じように利用した. おそらくこの記事での証明は Stern–Brocot tree に関連するものだと思われる. 筆者は数学専攻ではないのでこういう話題に疎い. もっとスマートな証明がありそうな気がする. Farey数列に関する良い図書やサイトがあれば是非コメント欄にて教えてほしい.

ja.wikipedia.org