ファレイ数列の定義・証明・具体例・性質・例題について
1. ファレイ数列とは
- \( 0 \leq a \leq b \leq n \)
- \( \gcd(a, b) = 1 \) （すなわち、\( a \) と \( b \) が互いに素である）
\[ F_1 = \left\{ \frac{0}{1}, \frac{1}{1} \right\} \]
\[ F_2 = \left\{ \frac{0}{1}, \frac{1}{2}, \frac{1}{1} \right\} \]
\[ F_3 = \left\{ \frac{0}{1}, \frac{1}{3}, \frac{1}{2}, \frac{2}{3}, \frac{1}{1} \right\} \]
\[ F_4 = \left\{ \frac{0}{1}, \frac{1}{4}, \frac{1}{3}, \frac{1}{2}, \frac{2}{3}, \frac{3}{4}, \frac{1}{1} \right\} \]
\[ F_5 = \left\{ \frac{0}{1}, \frac{1}{5}, \frac{1}{4}, \frac{1}{3}, \frac{2}{5}, \frac{1}{2}, \frac{3}{5}, \frac{2}{3}, \frac{3}{4}, \frac{4}{5}, \frac{1}{1} \right\} \]
2. ファレイ数列の性質
ファレイ数列（Farey sequence）は、多くの興味深い性質を持っています。以下に、ファレイ数列の主要な性質をいくつか紹介します。
2.1. 連続する分数の挿入
例: ファレイ数列 \( F_2 \) から \( F_3 \) を構築する。
ファレイ数列 \( F_2 \): \( F_2 \) は、分母が最大2までのすべての既約分数からなる数列です。したがって、 \[ F_2 = \left\{ \frac{0}{1}, \frac{1}{2}, \frac{1}{1} \right\} \]
ファレイ数列 \( F_3 \) の構築: \( F_2 \) の連続する分数 \( \frac{a}{b} \) と \( \frac{c}{d} \) の間に、新しい分数 \( \frac{a+c}{b+d} \) を挿入します。ここでは、以下のステップに従います。
- \( \frac{0}{1} \) と \( \frac{1}{2} \) の間に、\( \frac{0+1}{1+2} = \frac{1}{3} \) を挿入します。
- \( \frac{1}{2} \) と \( \frac{1}{1} \) の間に、\( \frac{1+1}{2+1} = \frac{2}{3} \) を挿入します。
これにより、次のファレイ数列 \( F_3 \) が得られます。 \[ F_3 = \left\{ \frac{0}{1}, \frac{1}{3}, \frac{1}{2}, \frac{2}{3}, \frac{1}{1} \right\} \]
このようにして、ファレイ数列 \( F_n \) から \( F_{n+1} \) を構築できます。
2.2. 隣接する分母の和
隣接する分数 \( \frac{f_i}{g_i} \) と \( \frac{f_{i+1}}{g_{i+1}} \) の間に$g_i + g_{i+1} \geq n + 1$が成立することを数学的帰納法で証明します。
まず、 \( n = 1 \) の場合を考えます。このとき、ファレイ数列 \( F_1 \) は次のようになります。
\[ F_1 = \left\{ \frac{0}{1}, \frac{1}{1} \right\} \]
隣接する分数は \( \frac{0}{1} \) と \( \frac{1}{1} \) です。このとき、分母の和は
\[ g_1 + g_2 = 1 + 1 = 2 \]
です。 \( g_1 + g_2 \geq n + 1 = 2 \) なので、$n=1$のときに成り立ちます。
次に、$n=k$のとき 、\( F_k \) の任意の隣接する分数 \( \frac{f_i}{g_i} \) と \( \frac{f_{i+1}}{g_{i+1}} \) に対して
\[ g_i + g_{i+1} \geq k + 1 \]
が成立すると仮定します。
$n=k+1$のとき次のファレイ数列 \( F_{k+1} \) でも同じ関係が成り立つことを示します。\( F_{k+1} \) は \( F_k \) を基本とし、隣接する分数 \( \frac{f_i}{g_i} \) と \( \frac{f_{i+1}}{g_{i+1}} \) の間に新しい分数
\[ \frac{f_i + f_{i+1}}{g_i + g_{i+1}} \]
が該当箇所に挿入されたものである。
ファレイ数列である条件を満たすために、\( F_{n+1} \) における新たな隣接する分数について、2つの場合に分けることができる。
1. 新しい分数 \( \frac{f_i + f_{i+1}}{g_i + g_{i+1}} \) と \( \frac{f_i}{g_i} \) の間
この場合、分母の和は、帰納法の仮定より \( g_i + g_{i+1} \geq k + 1 \) なので
\[ (g_i + g_{i+1}) + g_i \geq k + 1+ g_{i} \geq k + 2 \]
2. 新しい分数 \( \frac{f_i + f_{i+1}}{g_i + g_{i+1}} \) と \( \frac{f_{i+1}}{g_{i+1}} \) の間
この場合、分母の和は
\[ (g_i + g_{i+1}) + g_{i+1} \geq k + 1+ g_{i+1} \geq k + 2 \]
より、この場合も成り立ちます。
したがって、$n=k+1$のとき、
\[ g_i + g_{i+1} \geq k + 2 \]
となる。
数学的帰納法により、すべての \( n \) に対してファレイ数列 \( F_n \) の隣接する分数 \( \frac{f_i}{g_i} \) と \( \frac{f_{i+1}}{g_{i+1}} \) の間に
\[ g_i + g_{i+1} \geq n + 1 \]
が成り立つことが証明されました。
2.3. 隣接する分数の差
ファレイ数列 \( F_n \) の隣接する分数 \( \frac{f_i}{g_i} \) と \( \frac{f_{i+1}}{g_{i+1}} \) の間に、次の関係 \( f_{i+1}g_i – f_ig_{i+1}= 1 \) が成立することを数学的帰納法で示します。
まず、\( n = 1 \) の場合を考えます。ファレイ数列 \( F_1 \) は \( \frac{0}{1} \) と \( \frac{1}{1} \) の2つの分数からなります。これらの分数について、次の計算を行います。
\[ f_{i+1}g_i – f_ig_{i+1} = 1 \times 1 – 0 \times 1 = 1 \]
\( n = 1 \) のとき、関係が成り立つ。
次に、\(n = k \) について、ファレイ数列 \( F_k \) の任意の隣接する分数 \( \frac{f_i}{g_i} \) と \( \frac{f_{i+1}}{g_{i+1}} \) について、 \( f_{i+1}g_i – f_ig_{i+1} = 1 \) が成立すると仮定します。
ファレイ数列 \( F_{k+1} \) は \( F_k \) の各隣接する分数 \( \frac{f_i}{g_i} \) と \( \frac{f_{i+1}}{g_{i+1}} \) の間に、新しい分数 \( \frac{f_i + f_{i+1}}{g_i + g_{i+1}} \) を必要箇所に挿入して得られます。つまり、\( F_{k+1} \) には次のような隣接する分数があります。
- \( \frac{f_i}{g_i} \) と \( \frac{f_i + f_{i+1}}{g_i + g_{i+1}} \)
- \( \frac{f_i + f_{i+1}}{g_i + g_{i+1}} \) と \( \frac{f_{i+1}}{g_{i+1}} \)
それぞれのペアについて、式を確認します。
1. \( \frac{f_i}{g_i} \) と \( \frac{f_i + f_{i+1}}{g_i + g_{i+1}} \) について、
\[(f_i + f_{i+1})g_i – f_i(g_i + g_{i+1})\]
\[= f_ig_i + f_{i+1}g_i – f_ig_i – f_ig_{i+1}\]
\[= f_{i+1}g_i – f_ig_{i+1} = 1\]
2. \( \frac{f_i + f_{i+1}}{g_i + g_{i+1}} \) と \( \frac{f_{i+1}}{g_{i+1}} \) について、
\[f_{i+1} (g_i + g_{i+1}) – (f_i + f_{i+1}) g_{i+1}\]
\[= f_{i+1}g_i +f_{i+1}g_{i+1}- f_ig_{i+1}-f_{i+1}g_{i+1}\]
\[= f_{i+1}g_i – f_ig_{i+1} = 1 \]
これにより、ファレイ数列 \( F_{k+1} \) においても隣接する分数に関して関係式 \( f_{i+1}g_i – f_ig_{i+1} = 1 \) が成り立つことが確認されました。
したがって、数学的帰納法により、任意の \( n \) に対して、ファレイ数列 \( F_n \) の隣接する分数 \( \frac{f_i}{g_i} \) と \( \frac{f_{i+1}}{g_{i+1}} \) の間に \( f_{i+1}g_i – f_ig_{i+1} = 1 \) が成り立つことが示されました。
2.4. 分数の総数
3. ファレイ数列の例題
3.1. 例題1（隣接する分数の和）
\[ g_i + g_{i+1} \geq 6 \]
ここで、\( g_i \) と \( g_{i+1} \) はそれぞれ分母の値です。すべての隣接するペアについて計算を行い、この不等式が成立することを確認しなさい。
まず、ファレイ数列 \( F_5 \) の全ての分数を列挙します。
ファレイ数列 \( F_5 \) は以下のような分数の列から成ります。
\[ F_5 = \left\{ \frac{0}{1}, \frac{1}{5}, \frac{1}{4}, \frac{1}{3}, \frac{2}{5}, \frac{1}{2}, \frac{3}{5}, \frac{2}{3}, \frac{3}{4}, \frac{4}{5}, \frac{1}{1} \right\} \]
隣接する分数 \( \frac{f_i}{g_i} \) と \( \frac{f_{i+1}}{g_{i+1}} \) について、\( g_i + g_{i+1} \geq 6 \) を確認します。
- \( \frac{0}{1} \) と \( \frac{1}{5} \): \( g_1 = 1, g_2 = 5 \) なので \( 1 + 5 = 6 \geq 6 \)
- \( \frac{1}{5} \) と \( \frac{1}{4} \): \( g_1 = 5, g_2 = 4 \) なので \( 5 + 4 = 9 \geq 6 \)
- \( \frac{1}{4} \) と \( \frac{1}{3} \): \( g_1 = 4, g_2 = 3 \) なので \( 4 + 3 = 7 \geq 6 \)
- \( \frac{1}{3} \) と \( \frac{2}{5} \): \( g_1 = 3, g_2 = 5 \) なので \( 3 + 5 = 8 \geq 6 \)
- \( \frac{2}{5} \) と \( \frac{1}{2} \): \( g_1 = 5, g_2 = 2 \) なので \( 5 + 2 = 7 \geq 6 \)
- \( \frac{1}{2} \) と \( \frac{3}{5} \): \( g_1 = 2, g_2 = 5 \) なので \( 2 + 5 = 7 \geq 6 \)
- \( \frac{3}{5} \) と \( \frac{2}{3} \): \( g_1 = 5, g_2 = 3 \) なので \( 5 + 3 = 8 \geq 6 \)
- \( \frac{2}{3} \) と \( \frac{3}{4} \): \( g_1 = 3, g_2 = 4 \) なので \( 3 + 4 = 7 \geq 6 \)
- \( \frac{3}{4} \) と \( \frac{4}{5} \): \( g_1 = 4, g_2 = 5 \) なので \( 4 + 5 = 9 \geq 6 \)
- \( \frac{4}{5} \) と \( \frac{1}{1} \): \( g_1 = 5, g_2 = 1 \) なので \( 5 + 1 = 6 \geq 6 \)
全ての隣接する分数に対して、\( g_i + g_{i+1} \geq 6 \) が成り立つことが確認できました。
3.2. 例題2（隣接する分数の差）
\[ f_{i+1}g_i – f_ig_{i+1} = 1 \]
ここで、すべての隣接するペアについて計算を行い、この等式が成立することを確認しなさい。
まず、ファレイ数列 \( F_5 \) の全ての分数を列挙します。
ファレイ数列 \( F_5 \) は以下のような分数の列から成ります。
\[ F_5 = \left\{ \frac{0}{1}, \frac{1}{5}, \frac{1}{4}, \frac{1}{3}, \frac{2}{5}, \frac{1}{2}, \frac{3}{5}, \frac{2}{3}, \frac{3}{4}, \frac{4}{5}, \frac{1}{1} \right\} \]
隣接する分数 \( \frac{f_i}{g_i} \) と \( \frac{f_{i+1}}{g_{i+1}} \) について、\( f_{i+1}g_i – f_ig_{i+1} = 1 \) を確認します。
- \( \frac{0}{1} \) と \( \frac{1}{5} \): \( 1 \times 1 – 0 \times 5 = 1 – 0 = 1 \)
- \( \frac{1}{5} \) と \( \frac{1}{4} \): \( 1 \times 5 – 1 \times 4 = 5 – 4 = 1 \)
- \( \frac{1}{4} \) と \( \frac{1}{3} \): \( 1 \times 4 – 1 \times 3 = 4 – 3 = 1 \)
- \( \frac{1}{3} \) と \( \frac{2}{5} \): \( 2 \times 3 – 1 \times 5 = 6 – 5 = 1 \)
- \( \frac{2}{5} \) と \( \frac{1}{2} \): \( 1 \times 5 – 2 \times 2 = 5 – 4 = 1 \)
- \( \frac{1}{2} \) と \( \frac{3}{5} \): \( 3 \times 2 – 1 \times 5 = 6 – 5 = 1 \)
- \( \frac{3}{5} \) と \( \frac{2}{3} \): \( 2 \times 5 – 3 \times 3 = 10 – 9 = 1 \)
- \( \frac{2}{3} \) と \( \frac{3}{4} \): \( 3 \times 3 – 2 \times 4 = 9 – 8 = 1 \)
- \( \frac{3}{4} \) と \( \frac{4}{5} \): \( 4 \times 4 – 3 \times 5 = 16 – 15 = 1 \)
- \( \frac{4}{5} \) と \( \frac{1}{1} \): \( 1 \times 5 – 4 \times 1 = 5 – 4 = 1 \)
全ての隣接する分数に対して、\( f_{i+1}g_i – f_ig_{i+1} = 1 \) が成り立つことが確認できました。
3.3. 例題3（分数の総数）
\[ |F_5| = 1 + \sum_{k=1}^{5} \phi(k) \]
ここで、\( \phi(k) \) はオイラーのトーシェント関数です。各 \( k \) に対して \( \phi(k) \) の値を計算し、最終的な \( |F_5| \) の値を求めなさい。
\[ \phi(1) = 1, \quad \phi(2) = 1, \quad \phi(3) = 2, \quad \phi(4) = 2, \quad \phi(5) = 4 \]
\[ |F_5| = 1 + (1 + 1 + 2 + 2 + 4) = 11 \]
実際に$F_5$を列挙してみると、
\[ F_5 = \left\{ \frac{0}{1}, \frac{1}{5}, \frac{1}{4}, \frac{1}{3}, \frac{2}{5}, \frac{1}{2}, \frac{3}{5}, \frac{2}{3}, \frac{3}{4}, \frac{4}{5}, \frac{1}{1} \right\} \]
