フェアリー数列

数学において、n次ファレー数列は、 0 から 1 まで、あるいはこの制限のない、完全に約分された分数列であり、 ^[a]最小の項では分母がn以下であり、大きさの順に並べられています。

制限された定義では、各ファレイ数列は分数で表される値0から始まり、⁠0/1⁠ 、分数⁠で表される値 1 で終わります。1/1⁠ (ただし、著者によってはこれらの用語を省略している場合もあります)。

ファレイ数列はファレイ級数と呼ばれることもあるが、項が合計されていないため厳密には正しくない。^[2]

1 から 8 までのファレイ数列は次のとおりです。

F ₁ = { ⁠0/1⁠ _、 ⁠1/1⁠ }

F ₂ = { ⁠0/1⁠ _、 ⁠1/2⁠ _、 ⁠1/1⁠ }

F ₃ = { ⁠0/1⁠ _、 ⁠1/3⁠ _、 ⁠1/2⁠ _、 ⁠2/3⁠ _、 ⁠1/1⁠ }

F ₄ = { ⁠0/1⁠ _、 ⁠1/4⁠ _、 ⁠1/3⁠ _、 ⁠1/2⁠ _、 ⁠2/3⁠ _、 ⁠3/4⁠ _、 ⁠1/1⁠ }

F ₅ = { ⁠0/1⁠ _、 ⁠1/5⁠ _、 ⁠1/4⁠ _、 ⁠1/3⁠ _、 ⁠2/5⁠ _、 ⁠1/2⁠ _、 ⁠3/5⁠ _、 ⁠2/3⁠ _、 ⁠3/4⁠ _、 ⁠4/5⁠ _、 ⁠1/1⁠ }

F ₆ = { ⁠0/1⁠ _、 ⁠1/6⁠ _、 ⁠1/5⁠ _、 ⁠1/4⁠ _、 ⁠1/3⁠ _、 ⁠2/5⁠ _、 ⁠1/2⁠ _、 ⁠3/5⁠ _、 ⁠2/3⁠ _、 ⁠3/4⁠ _、 ⁠4/5⁠ _、 ⁠5/6⁠ _、 ⁠1/1⁠ }

F ₇ = { ⁠0/1⁠ _、 ⁠1/7⁠ _、 ⁠1/6⁠ _、 ⁠1/5⁠ _、 ⁠1/4⁠ _、 ⁠2/7⁠ _、 ⁠1/3⁠ _、 ⁠2/5⁠ _、 ⁠3/7⁠ _、 ⁠1/2⁠ _、 ⁠4/7⁠ _、 ⁠3/5⁠ _、 ⁠2/3⁠ _、 ⁠5/7⁠ _、 ⁠3/4⁠ _、 ⁠4/5⁠ _、 ⁠5/6⁠ _、 ⁠6/7⁠ _、 ⁠1/1⁠ }

F ₈ = { ⁠0/1⁠ _、 ⁠1/8⁠ _、 ⁠1/7⁠ _、 ⁠1/6⁠ _、 ⁠1/5⁠ _、 ⁠1/4⁠ _、 ⁠2/7⁠ _、 ⁠1/3⁠ _、 ⁠3/8⁠ _、 ⁠2/5⁠ _、 ⁠3/7⁠ _、 ⁠1/2⁠ _、 ⁠4/7⁠ _、 ⁠3/5⁠ _、 ⁠5/8⁠ _、 ⁠2/3⁠ _、 ⁠5/7⁠ _、 ⁠3/4⁠ _、 ⁠4/5⁠ _、 ⁠5/6⁠ _、 ⁠6/7⁠ _、 ⁠7/8⁠ _、 ⁠1/1⁠ }

ファレイ数列の分子と分母をプロットすると、右に示すF ₆のような形になります。

この形状を対角軸と主軸の周りに反射すると、以下に示すFarey サンバーストが生成されます。 n次 Farey サンバーストは、原点を中心とする2 n辺の正方形内の原点からの可視整数グリッド ポイントを結びます。ピックの定理を使用すると、サンバーストの面積は4(| F _n | − 1)になります。ここで、| F _n | はFn 内の分数の個数です。

「フェアリーシリーズ」の歴史は非常に興味深い- ハーディ＆ライト（1979）^[3]

... 記録に残る限り、数学的関係に名前が付けられた人物は、今回も最初の発見者ではなかった。—ベイラー (1964) ^[4]

ファレイ数列はイギリスの 地質学者 ジョン・ファレイ・シニアにちなんで名付けられ、これらの数列に関する彼の手紙は1816年に哲学雑誌に掲載されました。ファレイは、証明を示さずに、ファレイ数列展開における各新しい項はその近傍の媒介語であると推測しました。ファレイの手紙を読んだコーシーは、著書『数学演習』で証明を行い、この結果をファレイによるものとしました。実際、別の数学者チャールズ・ハロスが1802年に同様の結果を発表していましたが、それはファレイもコーシーも知りませんでした。^[4]したがって、ファレイの名前がこれらの数列と結びついたのは歴史的な偶然でした。これはスティグラーの名詞同名法則の一例です。

n次ファレイ数列には、それより低い次数のファレイ数列の要素がすべて含まれる。特に、F _{n には}F _{n −1}の要素がすべて含まれ、さらにnより小さく n と互いに素な各数について追加の分数も含まれる。したがって、 F 6_はF ₅と分数 ⁠から構成される。1/6⁠と⁠5/6⁠ .

ファレイ数列F _nの中間項は常に⁠1/2⁠、n > 1の場合。これから、オイラーのトーシェント関数φ ( n )を使用して、F _nとF _{n −1}の長さを関連付けることができます。

$${\displaystyle |F_{n}|=|F_{n-1}|+\varphi (n)。}$$

| F ₁ | = 2という事実を用いて、 F _nの長さを表す式を導くことができる: ^[5]

$${\displaystyle |F_{n}|=1+\sum _{m=1}^{n}\varphi (m)=1+\Phi (n),}$$ ここでΦ( n )は総括的トーティエントである。

また、次も成り立ちます。また 、メビウスの反転公式 により次が成り立ちます 。 ここで、μ ( d )は数論的メビウス関数、は 床関数です。 $${\displaystyle |F_{n}|={\frac {1}{2}}\left(3+\sum _{d=1}^{n}\mu (d)\left\lfloor {\tfrac {n}{d}}\right\rfloor ^{2}\right),}$$$${\displaystyle |F_{n}|={\frac {1}{2}}(n+3)n-\sum _{d=2}^{n}|F_{\lfloor n/d\rfloor }|,}$$${\displaystyle \lfloor n/d\rfloor }$

| F _n |の漸近挙動は次のようになる。 $${\displaystyle |F_{n}|\sim {\frac {3n^{2}}{\pi ^{2}}}.}$$

F _nにおける分母がkに等しいファレイ分数の個数は、k ≤ nのときはφ ( k )で与えられ、それ以外のときは 0 である。分子に関しては、 F _nにおける分子がhに等しいファレイ分数の個数を返す関数を定義できる。この関数には次のような興味深い性質がある^[6]。${\displaystyle {\mathcal {N}}_{n}(h)}$

${\displaystyle {\mathcal {N}}_{n}(1)=n}$、

${\displaystyle {\mathcal {N}}_{n}(p^{m})=\left\lceil (n-p^{m})\left(1-1/p\right)\right\rceil }$任意の素数に対して、${\displaystyle p}$

${\displaystyle {\mathcal {N}}_{n+mh}(h)={\mathcal {N}}_{n}(h)+m\varphi (h)}$ 任意の整数 m ≥ 0に対して、

${\displaystyle {\mathcal {N}}_{n}(4h)={\mathcal {N}}_{n}(2h)-\varphi (2h).}$

特に、上記の3行目の性質は次を意味し、さらに、後者は、偶数次のファレイ数列nに対して、分子が⁠に等しい分数の個数が${\displaystyle {\mathcal {N}}_{mh}(h)=(m-1)\varphi (h)}$${\displaystyle {\mathcal {N}}_{2h}(h)=\varphi (h).}$ん/2⁠ は、分母が⁠に等しい分数の個数と同じですん/2⁠、つまり。 ${\displaystyle {\mathcal {N}}_{n}(n/2)=\varphi (n/2)}$

ファレー数列における分数の指数は、数列内で占める位置です。これは、リーマン予想 の別の定式化で使用されるため、特に重要です。以下を参照してください。さまざまな有用な特性が以下にあります。 ${\displaystyle I_{n}(a_{k,n})=k}$${\displaystyle a_{k,n}}$${\displaystyle F_{n}=\{a_{k,n}:k=0,1,\ldots ,m_{n}\}}$${\displaystyle a_{k,n}}$$${\displaystyle {\begin{aligned}I_{n}(0/1)&=0,\\[6pt]I_{n}(1/n)&=1,\\[2pt]I_{n}(1/2)&={\frac {|F_{n}|-1}{2}},\\[2pt]I_{n}(1/1)&=|F_{n}|-1,\\[2pt]I_{n}(h/k)&=|F_{n}|-1-I_{n}\left({\frac {k-h}{k}}\right).\end{aligned}}}$$

⁠のインデックス1/け⁠どこ⁠ん/私+1⁠ < k ≤ ⁠ん/私⁠そしてnは最初のi個の数の最小公倍数、 n= lcm ([2, i ])は次のように与えられる: ^[7] $${\displaystyle I_{n}(1/k)=1+n\sum _{j=1}^{i}{\frac {\varphi (j)}{j}}-k\Phi (i).}$$

任意の Farey 数列で隣接する項である分数はFarey ペアと呼ばれ、次の特性を持ちます。

もし⁠1つの/b⁠と⁠ｃ/d⁠ はファレイ数列で隣接しており、 ⁠1つの/b⁠ < ⁠ｃ/d⁠、それらの違いは⁠ｃ/d⁠ − ⁠1つの/b⁠ は⁠に等しい1/BD⁠ . 以来 $${\displaystyle {\frac {c}{d}}-{\frac {a}{b}}={\frac {bc-ad}{bd}},}$$

これは次のように言うのと同じである $${\displaystyle bc-ad=1.}$$

したがって⁠1/3⁠と⁠2/5⁠ はF ₅で隣接しており、それらの差は⁠1/15⁠ .

逆もまた真なりである。 $${\displaystyle bc-ad=1}$$

正の整数a、b、c、d（a < bかつc < d ）の場合、⁠1つの/b⁠と⁠ｃ/d⁠ は、順序max( b,d )の Farey 数列の隣接点になります。

もし⁠p/q⁠隣人がいる⁠1つの/b⁠と⁠ｃ/d⁠ファレイ数列で、 ⁠1つの/b⁠ < ⁠p/q⁠ < ⁠ｃ/d⁠、そして⁠p/q⁠ は⁠の中位数です1つの/b⁠と⁠ｃ/d⁠ – つまり、 $${\displaystyle {\frac {p}{q}}={\frac {a+c}{b+d}}.}$$

これは前の性質から簡単に導かれる。なぜなら、 $${\displaystyle {\begin{aligned}&&bp-aq&=qc-pd=1,\\[4pt]\implies &&bp+pd&=qc+aq,\\[4pt]\implies &&p(b+d)&=q(a+c),\\\implies &&{\frac {p}{q}}&={\frac {a+c}{b+d}}.\end{aligned}}}$$

したがって、もし⁠1つの/b⁠と⁠ｃ/d⁠がファレイ数列で隣り合っている場合、ファレイ数列の順序が増加するにつれてそれらの間に現れる最初の項は $${\displaystyle {\frac {a+c}{b+d}},}$$

これは、 b + dの順序のファレイ数列で初めて出現します。

したがって、 ⁠の間に現れる最初の項は、1/3⁠と⁠2/5⁠は⁠3/8⁠ 、 F ₈に出現します。

F _nの Farey 隣接ペアの総数は2| F _n | − 3です。

シュテルン・ブロコット木は、0 （＝⁠0/1⁠ )と 1 ( = ⁠1/1⁠）、連続した媒介変数を取ることによって。

連続するファレイ有理数のペアは、面積が1である。^[8] 連続する有理数を xy平面上の ベクトル（p、q）として解釈すると、このことがわかります。面積は 次のように与えられます。連続する2つのファレイ数列分数の間に追加された分数は、中分数（⊕）として計算されるため、 （r ₁ = ⁠なので）$${\displaystyle r_{1}={\frac {p}{q}}\qquad r_{2}={\frac {p'}{q'}}}$$$${\displaystyle A\left({\frac {p}{q}},{\frac {p'}{q'}}\right)=qp'-q'p.}$$$${\displaystyle {\begin{aligned}A(r_{1},r_{1}\oplus r_{2})&=A(r_{1},r_{1})+A(r_{1},r_{2})\\&=A(r_{1},r_{2})\\&=1\end{aligned}}}$$1/0⁠そしてr ₂ = ⁠0/1⁠、その面積は 1) でなければなりません。

ファレイ数列で隣り合う分数には、密接に関連した連分数展開があります。すべての分数には2つの連分数展開があります。1つは最後の項が1で、もう1つは最後の項が1だけ大きいです。もし、p/q⁠ は、ファレイ数列F _qに初めて現れるが、連分数展開は $${\displaystyle {\begin{aligned}&[0;\ a_{1},\ a_{2},\ \ldots ,\ a_{n-1},\ a_{n},\ 1]\\{}&[0;\ a_{1},\ a_{2},\ \ldots ,\ a_{n-1},\ a_{n}+1]\end{aligned}}}$$

次に、 ⁠の最も近い隣り合うp/q⁠ F _q（分母が大きい方の隣の分数） は$${\displaystyle [0;\ a_{1},\ a_{2},\ \ldots ,\ a_{n}]}$$

そして、その他の隣の数は連分数展開である。 $${\displaystyle [0;\ a_{1},\ a_{2},\ \ldots ,\ a_{n-1}]}$$

例えば、⁠3/8⁠ には2 つの連分数展開[0; 2, 1, 1, 1]と[0; 2, 1, 2]があり、F ₈におけるその近傍は⁠です。2/5⁠は[0; 2, 1, 1]と展開でき、⁠1/3⁠は[0; 2, 1]と展開できます。

最小公倍数は、ファレー分数の積として次のように表すことができます。 $${\displaystyle {\text{lcm}}[1,2,...,N]=e^{\psi (N)}={\frac {1}{2}}\left(\prod _{r\in F_{N},0<r\leq 1/2}2\sin(\pi r)\right)^{2}}$$

ここでψ ( N )は2番目のチェビシェフ関数である。^{[9] [10]}

オイラーのトーシェント関数は最大公約数に直接関連しているので、 F _nの要素数も同様に関連します。 $${\displaystyle |F_{n}|=1+\sum _{m=1}^{n}\varphi (m)=1+\sum \limits _{m=1}^{n}\sum \limits _{k=1}^{m}\gcd(k,m)\cos {2\pi {\frac {k}{m}}}.}$$

任意の3つのファレー分数について⁠1つの/b⁠、⁠ｃ/d⁠、⁠e/ふ⁠ 2x2行列の絶対値行列式の最大公約数の間には次の恒等式が成り立つ: ^[11] $${\displaystyle \gcd \left({\begin{Vmatrix}a&c\\b&d\end{Vmatrix}},{\begin{Vmatrix}a&e\\b&f\end{Vmatrix}}\right)=\gcd \left({\begin{Vmatrix}a&c\\b&d\end{Vmatrix}},{\begin{Vmatrix}c&e\\d&f\end{Vmatrix}}\right)=\gcd \left({\begin{Vmatrix}a&e\\b&f\end{Vmatrix}},{\begin{Vmatrix}c&e\\d&f\end{Vmatrix}}\right)}$$

^[7]

ファレイ数列は無理数の有理数近似値を求めるのに非常に有用である。^[12]例えば、エリアホウ^{[13]による}3 x +1過程における非自明な閉路の長さの下限の構築は、ファレイ数列を使用してlog ₂ (3)の連分数展開を計算している。

^{共鳴現象を伴う物理系では、ファレー数列は1D [14]}および2D ^[15]における共鳴位置を計算するための非常にエレガントで効率的な方法を提供します。

ファレイ列は、正方セルグリッド上の任意角度の経路計画の研究で、例えば計算の複雑さ^{[16]や最適性[17]}の特徴付けにおいて重要な役割を果たしています。この接続は、 r制約経路、つまり最大r行および最大r 列のセルを通る線分で構成される経路の観点から考えることができます。 Q を、 、、およびp、qが互いに素であるようなベクトル( q、p )の集合とします。Q* を、Q を直線y = xで反射した結果とします。 とします。 すると、任意のr制約経路は、 Sからのベクトルの列として記述できます。 Qと、にマッピングされる( q、p )によって与えられる順序rのファレイ列の間には一対一の関係があります。 ${\displaystyle 1\leq q\leq r}$${\displaystyle 0\leq p\leq q}$${\displaystyle S=\{(\pm x,\pm y):(x,y)\in Q\cup Q*\}}$${\displaystyle {\tfrac {p}{q}}}$

ファレイ数列とフォード円の間には関連があります。

すべての分数について⁠p/q⁠ (最も単純な表現では) フォード円C [ p / q ]があり、これは半径が で中心が である円です。異なる分数の 2 つのフォード円は互いに交わらないか、互いに接しています。2 つのフォード円が交わることはありません。0 < ⁠の場合、${\displaystyle {\tfrac {1}{2q^{2}}}}$${\displaystyle {\bigl (}{\tfrac {p}{q}},{\tfrac {1}{2q^{2}}}{\bigr )}.}$p/q⁠ < 1の場合、 C [ p / q ]に接するフォード円は、 ⁠の近傍の分数のフォード円とまったく同じです。p/q⁠何らかのFareyシーケンスで。

したがってC [2/5]はC [1/2]、C [1/3]、C [3/7]、C [3/8]などに接します。

フォード円はアポロニアンガスケット (0,0,1,1)にも現れる。下の図はこれをファレイ共鳴線とともに示している。^[18]

ファレイ数列は、リーマン予想の2つの同等な定式化で使用されます。F _nの項が次のように定義されます。言い換えると、 n番目のファレイ数列のk番目の項と、単位区間に均等に分布する同じ数の点の集合のk番目の要素との差です。1924 年にジェローム・フランエル^[19]は、次の命題が成り立つことを証明しました 。${\displaystyle \{a_{k,n}:k=0,1,\ldots ,m_{n}\}.}$${\displaystyle d_{k,n}=a_{k,n}-{\tfrac {k}{m_{n}}},}$${\displaystyle d_{k,n}}$

$${\displaystyle \sum _{k=1}^{m_{n}}d_{k,n}^{2}=O(n^{r})\quad \forall r>-1}$$

はリーマン予想と同値であり、エドモンド・ランダウ^[20]は（フランネルの論文の直後に） $${\displaystyle \sum _{k=1}^{m_{n}}|d_{k,n}|=O(n^{r})\quad \forall r>{\frac {1}{2}}}$$

リーマン予想とも同等です。

n次のすべてのファレイ分数の合計は要素数の半分です。 $${\displaystyle \sum _{r\in F_{n}}r={\frac {1}{2}}|F_{n}|.}$$

ファレイ数列の分母の合計は分子の合計の 2 倍であり、オイラーのトーティエント関数に関連します。

$${\displaystyle \sum _{a/b\in F_{n}}b=2\sum _{a/b\in F_{n}}a=1+\sum _{i=1}^{n}i\varphi (i),}$$

これは1962年にハロルド・L・アーロンによって予想され、1966年にジーン・A・ブレイクによって実証された。^[21]ハロルド・L・アーロン予想の1行証明は以下の通りである。分子の合計は、 分母の合計 は、 最初の合計を2番目の合計で割った商は、⁠$${\displaystyle 1+\sum _{2\leq b\leq n}\ \sum _{(a,b)=1}a=1+\sum _{2\leq b\leq n}b{\frac {\varphi (b)}{2}}.}$$$${\displaystyle 2+\sum _{2\leq b\leq n}\ \sum _{(a,b)=1}b=2+\sum _{2\leq b\leq n}b\varphi (b).}$$1/2⁠ .

b _jをF _nの分母の順序とする。^[22]

$${\displaystyle \sum _{j=0}^{|F_{n}|-1}{\frac {b_{j}}{b_{j+1}}}={\frac {3|F_{n}|-4}{2}}}$$ そして $${\displaystyle \sum _{j=0}^{|F_{n}|-1}{\frac {1}{b_{j+1}b_{j}}}=1.}$$

F _nのj番目のファレー分数とすると、 ${\displaystyle {\tfrac {a_{j}}{b_{j}}}}$$${\displaystyle \sum _{j=1}^{|F_{n}|-1}(a_{j-1}b_{j+1}-a_{j+1}b_{j-1})=\sum _{j=1}^{|F_{n}|-1}{\begin{Vmatrix}a_{j-1}&a_{j+1}\\b_{j-1}&b_{j+1}\end{Vmatrix}}=3(|F_{n}|-1)-2n-1,}$$

^{これは[23]}で実証されています。また、この文献によると、合計内の項はさまざまな方法で表現できます。 $${\displaystyle a_{j-1}b_{j+1}-a_{j+1}b_{j-1}={\frac {b_{j-1}+b_{j+1}}{b_{j}}}={\frac {a_{j-1}+a_{j+1}}{a_{j}}}=\left\lfloor {\frac {n+b_{j-1}}{b_{j}}}\right\rfloor ,}$$

ファレイ要素上のさまざまな和が同じ結果になる。1/2の周りの対称性を使用すると、前者の和はシーケンスの半分に制限される。

$${\displaystyle \sum _{j=1}^{\left\lfloor {\frac {|F_{n}|}{2}}\right\rfloor }(a_{j-1}b_{j+1}-a_{j+1}b_{j-1})={\frac {3(|F_{n}|-1)}{2}}-n-\left\lceil {\frac {n}{2}}\right\rceil ,}$$

メルテンス関数は、ファレー分数の合計として次のように表すことができます 。 ここで、はn次ファレー数列です。 $${\displaystyle M(n)=-1+\sum _{a\in {\mathcal {F}}_{n}}e^{2\pi ia}}$$${\displaystyle {\mathcal {F}}_{n}}$

この式はフランネル・ランダウの定理の証明に用いられる。^[24]

F _nの項を従来の順序 (昇順) または非従来の順序 (降順) で生成する驚くほど単純なアルゴリズムが存在します。このアルゴリズムは、上記の中位プロパティを使用して、各連続するエントリを前の 2 つのエントリの観点から計算します。1つの/b⁠と⁠ｃ/d⁠ は与えられた2つのエントリであり、⁠p/q⁠ は未知の次のエントリであり、次に⁠ｃ/d⁠ = ⁠a + p/b + q⁠ . 以来⁠ｃ/d⁠ を最小の項で表すと、 kc = a + pかつkd = b + qとなる整数kが存在し、p = kc − aかつq = kd − bとなる。 pとq をkの関数と見なすと、

${\displaystyle {\frac {p(k)}{q(k)}}-{\frac {c}{d}}={\frac {cb-da}{d(kd-b)}}}$

kが大きくなるほど、より近くなります。p/q⁠ ⁠に到達するｃ/d⁠ .

数列の次の項を与えるには、kはkd − b ≤ n （分母がnより大きくない数のみを考慮しているため）を条件として、可能な限り大きくする必要があります。したがって、 kは最大の整数≤ ⁠n + b/d⁠ . このkの値をpとqの式に戻す、

${\displaystyle p=\left\lfloor {\frac {n+b}{d}}\right\rfloor c-a}$

${\displaystyle q=\left\lfloor {\frac {n+b}{d}}\right\rfloor d-b}$

これはPythonでは次のように実装されます。

 fractions からFractionをインポートし、 collections.abcからGeneratorをインポートします。
   


def  farey_sequence ( n :  int ,  descending :  bool  =  False )  ->  Generator [ Fraction ]: 
"""     n 番目の Farey シーケンスを出力します。昇順または降順のいずれかを許可します。    


    >>> print(*farey_sequence(5), sep=' ') 
    0 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1 
    """ 
    a 、 b 、 c 、 d  =  0 、 1 、 1 、 n
    降順の場合 : a 、c = 1 、n - 1 Fraction ( a 、b )が生成されますが、 0 <= c <= nの場合: k = ( n + b ) // d a 、b 、c 、d = c 、d 、k * c - a 、k * d - b Fraction ( a 、b )が生成されます
              
      
         
              
                        
          


 __name__  ==  "__main__"の場合: 
    doctestをインポートします 

    doctest.testmod ( )の

ディオファントス方程式の解を有理数で力ずくで探す場合、ファレー級数（簡約された形式のみを検索する）を利用することが多い。このコードでは、数列の最初の2つの項を使用してa、b、c、およびd を初期化していますが、隣接する項のペアを置き換えることで、特定のしきい値より小さい（または大きい）項を除外することができます。^[25]