Farey数列（高校数学）
概要
Farey数列（Farey sequence）とは、正の整数 $n$ に対し、$0$ 以上 $1$ 以下で分母が $n$ 以下の既約分数を小さい順に並べた列 $F_n$ である。$F_n$ で隣り合う $\frac ab<\frac cd$ は $bc-ad=1$ を満たし（原点と格子点 $(b,a)$、$(d,c)$ の三角形が頂点以外に格子点を含まず面積 $\frac12$ になることから示せる）、$b+d>n$ である。$F_{n+1}$ で 2 つの間に新しく入る分数は、$b+d=n+1$ のときの中間の分数 $\frac{a+c}{b+d}$ だけで、連続する 3 項の真ん中は両端の中間の分数に等しい。項の数は $1+\sum_{k=1}^n\varphi(k)$ である。
前提知識: Pickの定理（高校数学）, 等式の証明と比例式, 靴ひも公式, Eulerのφ関数（高校数学）
高校での出発点：分母の小さい分数を並べる
$0$ 以上 $1$ 以下の分数のうち、分母が $5$ 以下のものを、約分した形で小さい順に並べてみる。
分母 $1$ の分数は $\frac01,\frac11$、分母 $2$ は $\frac12$、分母 $3$ は $\frac13,\frac23$、分母 $4$ は $\frac14,\frac34$（$\frac24$ は約分すると $\frac12$）、分母 $5$ は $\frac15,\frac25,\frac35,\frac45$ である。小さい順に並べると
$$
\frac01,\ \frac15,\ \frac14,\ \frac13,\ \frac25,\ \frac12,\ \frac35,\ \frac23,\ \frac34,\ \frac45,\ \frac11
$$
の 11 個になる。
ex-fry-f5 で隣り合う $\frac ab<\frac cd$ について $bc-ad$ を計算すると、
$$
\frac15,\frac14:\ 5\cdot1-1\cdot4=1,\qquad \frac13,\frac25:\ 3\cdot2-1\cdot5=1,\qquad \frac25,\frac12:\ 5\cdot1-2\cdot2=1
$$
で、どの組でも $1$ になる。また、連続する 3 つ $\frac13,\frac25,\frac12$ では、両端の分子どうし・分母どうしを足すと $\frac{1+1}{3+2}=\frac25$ で、真ん中の分数になっている。
等式の証明と比例式 の節「大学数学で見る：Farey 数列と Stern–Brocot 木」では、$bc-ad=1$ を満たす 2 つの分数の間に、中間の分数 $\frac{a+c}{b+d}$ が入ることを扱った。そこでは、並べた分数の隣り合う組がいつも $bc-ad=1$ を満たすことは例で確かめただけだった。この記事では、それを格子点の三角形を使って証明する。問いは次の 2 つである。
- 隣り合う 2 つの分数は、いつも $bc-ad=1$ を満たすか。→ thm-fry-unimodular
- 分母の上限を 1 つ上げると、新しい分数はどこに入るか。連続する 3 つの関係はいつも成り立つか。→ thm-fry-mediant
分数の言葉 格子点の言葉 分数 $\frac ab$（約分した形） 原点から見える格子点 $(b,a)$ $\frac ab<\frac cd$ 原点からの傾きが小さい $bc-ad$ 原点と $(b,a)$、$(d,c)$ の三角形の面積の $2$ 倍 隣り合う 2 点の作る三角形が基本三角形
Farey 数列の定義
正の整数 $n$ に対し、$0\le h\le k\le n$、$k\ge1$ で、$h$ と $k$ が互いに素である分数 $\frac hk$ をすべて小さい順に並べた列を、位数 $n$ の Farey 数列 といい、$F_n$ と書く。$\frac01$ と $\frac11$ を両端に含む。
| $n$ | $F_n$ | 項の数 | 新しく入った分数 |
|---|---|---|---|
| $1$ | $\frac01,\frac11$ | $2$ | — |
| $2$ | $\frac01,\frac12,\frac11$ | $3$ | $\frac12$ |
| $3$ | $\frac01,\frac13,\frac12,\frac23,\frac11$ | $5$ | $\frac13,\frac23$ |
| $4$ | $\frac01,\frac14,\frac13,\frac12,\frac23,\frac34,\frac11$ | $7$ | $\frac14,\frac34$ |
| $5$ | ex-fry-f5 の 11 個 | $11$ | $\frac15,\frac25,\frac35,\frac45$ |
| $6$ | $F_5$ に $\frac16,\frac56$ を加えた 13 個 | $13$ | $\frac16,\frac56$ |
表を見ると、新しく入った分数は、どれも両隣の中間の分数になっている。たとえば $F_5$ の $\frac25$ は、$F_4$ で隣り合う $\frac13$ と $\frac12$ の中間の分数 $\frac{1+1}{3+2}$ である。
主定理 1：隣り合う 2 項
格子点の三角形を使う。Pickの定理（高校数学） の定理「基本三角形の面積は $\frac12$」によれば、頂点のほかに内部にも辺の上にも格子点を含まない格子点の三角形（基本三角形）の面積は $\frac12$ である。原点 $O$、$(b,a)$、$(d,c)$ の三角形の面積は、靴ひも公式 で $\frac12\lvert bc-ad\rvert$ である。
$F_n$ で隣り合う 2 つの分数 $\dfrac ab<\dfrac cd$ は
$$
bc-ad=1
$$
を満たす。
方針：原点 $O$、$U=(b,a)$、$V=(d,c)$ の三角形が基本三角形であることを示し、面積から $bc-ad$ を求める。
段 1（三角形の点の書き方）。$\frac ab<\frac cd$ から $bc-ad>0$ で、$O,U,V$ は一直線上にない。三角形 $OUV$（周も含む）の点は、$s\ge0$、$t\ge0$、$s+t\le1$ を使って $sU+tV=(sb+td,\ sa+tc)$ と書ける。
段 2（頂点以外に格子点があるとする）。三角形 $OUV$ の中に、頂点以外の格子点 $X=(k,h)=sU+tV$ があったとする。$k=sb+td$ で、$b,d\ge1$ だから、$k=0$ なら $s=t=0$ で $X=O$ となってしまう。よって $k\ge1$ で、$k\le(s+t)\max(b,d)\le n$ である。さらに
$$
bh-ak=t(bc-ad)\ge0,\qquad ck-dh=s(bc-ad)\ge0
$$
（$h=sa+tc$、$k=sb+td$ を代入して整理した）なので、$\dfrac ab\le\dfrac hk\le\dfrac cd$ である。とくに $0\le\frac hk\le1$ で、$\frac hk$ を約分すると分母は $k$ 以下、つまり $n$ 以下なので、$\frac hk$ は $F_n$ の項である。
段 3（矛盾）。$\frac ab$ と $\frac cd$ は隣り合うので、間に $F_n$ の項はなく、$\frac hk=\frac ab$ か $\frac hk=\frac cd$ である。$\frac hk=\frac ab$ なら $bh-ak=0$、つまり $t=0$ で、$X=sU=(sb,sa)$、$0< s\le1$ である。$s=\frac pq$（約分した形、$q\ge1$）とおくと、$\frac{pb}q$、$\frac{pa}q$ が整数で $p$ と $q$ は互いに素なので、$q$ は $a$ と $b$ の両方を割り切る。$a,b$ は互いに素なので $q=1$、つまり $s$ は整数で $s=1$、$X=U$ となり、頂点以外という仮定に反する。$\frac hk=\frac cd$ のときも同じく $X=V$ となり矛盾する。
段 4（結論）。三角形 $OUV$ は基本三角形で、面積は $\frac12$ である。靴ひも公式から面積は $\frac12(bc-ad)$ なので、$bc-ad=1$ である。$\square$
図 1 は、$F_5$ の分数 $\frac ab$ を格子点 $(b,a)$ として打ち、隣り合う 2 つと原点が作る三角形を色分けした図である。10 個の三角形はどれも、頂点のほかに格子点を含まない。分数を小さい順にたどることは、原点から出る半直線を $x$ 軸から反時計回りに回して、格子点に当たる順にたどることにあたる。
F5 の分数 a/b を格子点 (b, a) で表した図。隣り合う 2 つの分数と原点 O が作る三角形（色分け）は、どれも面積 1/2 の基本三角形になる
$F_5$ の隣り合う $\frac25<\frac12$ は格子点 $(5,2)$、$(2,1)$ で、三角形 $O,(5,2),(2,1)$ の面積は $\frac12\lvert5\cdot1-2\cdot2\rvert=\frac12$ である。
隣り合わない $\frac14<\frac12$（間に $\frac13$ と $\frac25$ がある）では、三角形 $O,(4,1),(2,1)$ の面積は $\frac12\lvert4\cdot1-1\cdot2\rvert=1$ で、たすき掛けの差は $2$ である。実際、この三角形の辺の上に格子点 $(3,1)$（分数 $\frac13$）がある。
主定理 2：新しく入る分数と連続する 3 項
$F_n$ で隣り合う 2 つの分数を $\dfrac ab<\dfrac cd$ とする。
(R1) $b+d>n$ である。
(R1) $F_{n+1}$ で $\dfrac ab$ と $\dfrac cd$ の間に入る分数は、$b+d=n+1$ のときは中間の分数 $\dfrac{a+c}{b+d}$ ただ 1 つで、$b+d>n+1$ のときはない。
(R1) $F_n$ で連続する 3 つの分数 $\dfrac ab<\dfrac hk<\dfrac cd$ について、$\dfrac hk=\dfrac{a+c}{b+d}$ である（右辺は約分した値）。
方針：主定理 1 の $bc-ad=1$ から、間にある分数の分母の下限を出す。
段 1（(i)）。中間の分数 $\frac{a+c}{b+d}$ は $\frac ab$ と $\frac cd$ の間にある（等式の証明と比例式 の定理「中間の分数は 2 つの分数の間にある」）。$b+d\le n$ なら、それを約分した分数は分母が $n$ 以下で、$F_n$ の項として 2 つの間に入ってしまう。2 つは隣り合うので、$b+d>n$ である。
段 2（間の分数の分母）。$\frac ab<\frac xy<\frac cd$（$x,y$ は整数、$y\ge1$）とする。$bx-ay$ と $cy-dx$ は正の整数なので、どちらも $1$ 以上である。主定理 1 の $bc-ad=1$ を使うと
$$
y=y(bc-ad)=b(cy-dx)+d(bx-ay)\ge b+d
$$
である。等号は $bx-ay=1$ かつ $cy-dx=1$ のときに限る。このとき $x=x(bc-ad)=c(bx-ay)+a(cy-dx)=a+c$、$y=b+d$ である。つまり、分母が $b+d$ の分数で間にあるのは中間の分数だけである。
段 3（(ii)）。$F_{n+1}$ で 2 つの間に入る分数 $\frac xy$（約分した形）は、$F_n$ には含まれないので $y=n+1$ である。段 2 から $y\ge b+d$、段 1 から $b+d\ge n+1$ なので、$y=b+d=n+1$ で、$\frac xy=\frac{a+c}{b+d}$ である。逆に $b+d=n+1$ なら、$b(a+c)-a(b+d)=bc-ad=1$ から $a+c$ と $b+d$ は互いに素で（公約数は $1$ を割り切る）、中間の分数は約分した形で分母 $n+1$ の $F_{n+1}$ の項である。$b+d>n+1$ なら、段 2 から間の分数の分母は $n+1$ より大きく、$F_{n+1}$ の項は入らない。
段 4（(iii)）。主定理 1 を隣り合う 2 組に使うと $bh-ak=1$、$ck-dh=1$ である。$m=bc-ad$ とおく（$\frac ab<\frac cd$ なので $m\ge1$）。1 つ目に $c$、2 つ目に $a$ を掛けて足すと $h(bc-ad)=a+c$、1 つ目に $d$、2 つ目に $b$ を掛けて足すと $k(bc-ad)=b+d$ である。よって $a+c=mh$、$b+d=mk$ で、$\frac{a+c}{b+d}=\frac hk$ である。$\square$
$F_5$ で隣り合う組の分母の和を見る。$\frac01,\frac15$ は $1+5=6$、$\frac45,\frac11$ も $6$ なので、$F_6$ ではその間に $\frac{0+1}{1+5}=\frac16$ と $\frac{4+1}{5+1}=\frac56$ が入る。ほかの組、たとえば $\frac15,\frac14$ は $5+4=9>6$ なので何も入らない。
$F_6$ から $F_7$ では、分母の和が $7$ の組 $\frac01,\frac16$、$\frac14,\frac13$、$\frac25,\frac12$、$\frac12,\frac35$、$\frac23,\frac34$、$\frac56,\frac11$ の間に、それぞれ $\frac17,\frac27,\frac37,\frac47,\frac57,\frac67$ が入る。$F_7$ は $13+6=19$ 項である。
$F_5$ の連続する $\frac14,\frac13,\frac25$ では $\frac{1+2}{4+5}=\frac39=\frac13$ で、約分すると真ん中になる（ここでは $m=4\cdot2-1\cdot5=3$）。$\frac13,\frac25,\frac12$ では $\frac{1+1}{3+2}=\frac25$ で、約分は要らない（$m=1$）。
$F_n$ の項の数は $1+\varphi(1)+\varphi(2)+\cdots+\varphi(n)$ である。ここで $\varphi(k)$ は、$1$ 以上 $k$ 以下で $k$ と互いに素な整数の個数である（Eulerのφ関数（高校数学））。
分母 $1$ の項は $\frac01$、$\frac11$ の 2 個で、$1+\varphi(1)=2$ である。$k\ge2$ のとき、分母 $k$ の項 $\frac hk$ は $1\le h\le k-1$ で $h$ と $k$ が互いに素なものなので（$h=0$ や $h=k$ は $k$ と互いに素でない）、$\varphi(k)$ 個ある。合わせて $2+\varphi(2)+\cdots+\varphi(n)=1+\varphi(1)+\cdots+\varphi(n)$ である。$\square$
$n=1,\dots,8$ で $1+\sum\varphi(k)$ は $2,3,5,7,11,13,19,23$ で、上の表と ex-fry-insert に一致する。項の数は $n$ を大きくすると $\frac{3n^2}{\pi^2}$ と比が $1$ に近づく大きさで増えることが知られている（HW60 Theorem 331。この記事では証明しない）。$n=100$ では項の数は $3045$、$\frac{3\cdot100^2}{\pi^2}\approx3039.6$ である。
例と反例
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 隣り合う | $F_5$ の $\frac14$ と $\frac12$ | $bc-ad=2$ になる |
| （定義の外の例）約分した形で並べる | $\frac12$ を $\frac24$ と書いて並べる | 隣の $\frac13$ とのたすき掛けの差が $2$ になる |
| 分母に上限がある | $0$ と $1$ の間の分数をすべて並べる | 隣り合う 2 つという組がなくなる |
$F_4$ の $\frac12$ を $\frac24$ と書き、$\frac13<\frac24<\frac23$ と並べると、$\frac13$ と $\frac24$ のたすき掛けの差は $3\cdot2-1\cdot4=2$、$\frac24$ と $\frac23$ では $4\cdot2-2\cdot3=2$ である。格子点 $(4,2)$ は原点との間に格子点 $(2,1)$ をもち（原点から「見えない」）、三角形 $O,(3,1),(4,2)$ は辺の上に $(2,1)$ を含むので、基本三角形にならない。主定理 1 の証明の段 3 は、$a,b$ が互いに素であることを使っていた。
$0$ と $1$ の間の分数をすべて並べると、どの 2 つ $\frac ab<\frac cd$ の間にも中間の分数 $\frac{a+c}{b+d}$ があるので、「隣り合う 2 つ」がない。Farey 数列は、分母に上限 $n$ を付けることで、有限個の分数の並びになり、隣り合う組が意味をもつ。
$F_5$ の $\frac13$ と $\frac12$ は $3\cdot1-1\cdot2=1$ を満たすが、間に $\frac25$ があり、隣り合わない。主定理 2 の (ii) のとおり、分母の和 $3+2=5$ が $n=5$ 以下なので、中間の分数が $F_5$ に入っている。$bc-ad=1$ の 2 つが $F_n$ で隣り合うのは、$b,d\le n< b+d$ のときである（段 2 から、間の分数の分母は $b+d$ 以上だから）。
大学数学で見る
Hardy と Wright の教科書の第 3 章は、主定理 1 と、連続する 3 項の中間の分数の性質を基本の定理とし、3 通りの証明を与えている（HW60 §3.1 Theorems 28・29、§3.3、§3.7）。その第 3 の証明は、この記事と同じく、隣り合う分数を表す 2 つの格子点と原点の三角形の中に格子点がないことから導くものである。同書の章末の注は、この 2 つの性質を最初に述べて証明したのは Haros（1802 年）で、Farey は 1816 年に後者（連続する 3 項の性質）を証明なしに述べた、と記している（HW60 第 3 章の注）。
隣り合う 2 つの分数が $bc-ad=1$ を満たすことは、2 つの格子点 $(b,a)$、$(d,c)$ を並べた行列の行列式が $\pm1$ であることにあたる。整数を成分とし行列式が $\pm1$ の行列は、格子点全体を格子点全体に 1 対 1 に移す。分数の近似の理論（連分数）でも、近似分数の組が同じ関係を満たす。
さらに先へ
- 各分数 $\frac pq$ に、$x$ 軸に接する半径 $\frac1{2q^2}$ の円を立てると、Farey 数列で隣り合う分数の円はちょうど接する。これが次の Fordの円（高校数学） である。
- $bc-ad=1$ は、未知数 $x,y$ の 1 次不定方程式 $bx-ay=1$ の整数解の話でもある（不定方程式の解法）。
- 分数を連分数で近似すると、近似分数 $\frac{p_n}{q_n}$ でも $p_nq_{n-1}-p_{n-1}q_n=\pm1$ が現れる（連分数（高校数学））。
関連項目
- 前提: Pickの定理（高校数学）, 等式の証明と比例式, 靴ひも公式, Eulerのφ関数（高校数学）
- 前に読む: Pickの定理（高校数学）, 等式の証明と比例式
- 次に読む: Fordの円（高校数学）
- 関連（高校数学）: 連分数（高校数学）, 整数の割り算と互除法, 不定方程式の解法
- 発展: 連分数
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
