フェアリー配列

円弧で表されたF9_のファレイ図。SVG画像では、曲線にマウスポインターを合わせると、曲線とその項が強調表示されます。

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

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

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

例

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

F ₁ = { ⁠01⁠ _、 ⁠11⁠ }

F ₂ = { ⁠01⁠ _、 ⁠12⁠ _、 ⁠11⁠ }

F ₃ = { ⁠01⁠ _、 ⁠13⁠ _、 ⁠12⁠ _、 ⁠23⁠ _、 ⁠11⁠ }

F ₄ = { ⁠01⁠ _、 ⁠14⁠ _、 ⁠13⁠ _、 ⁠12⁠ _、 ⁠23⁠ _、 ⁠34⁠ _、 ⁠11⁠ }

F ₅ = { ⁠01⁠ _、 ⁠15⁠ _、 ⁠14⁠ _、 ⁠13⁠ _、 ⁠25⁠ _、 ⁠12⁠ _、 ⁠35⁠ _、 ⁠23⁠ _、 ⁠34⁠ _、 ⁠45⁠ _、 ⁠11⁠ }

F ₆ = { ⁠01⁠ _、 ⁠16⁠ _、 ⁠15⁠ _、 ⁠14⁠ _、 ⁠13⁠ _、 ⁠25⁠ _、 ⁠12⁠ _、 ⁠35⁠ _、 ⁠23⁠ _、 ⁠34⁠ _、 ⁠45⁠ _、 ⁠56⁠ _、 ⁠11⁠ }

F ₇ = { ⁠01⁠ _、 ⁠17⁠ _、 ⁠16⁠ _、 ⁠15⁠ _、 ⁠14⁠ _、 ⁠27⁠ _、 ⁠13⁠ _、 ⁠25⁠ _、 ⁠37⁠ _、 ⁠12⁠ _、 ⁠47⁠ _、 ⁠35⁠ _、 ⁠23⁠ _、 ⁠57⁠ _、 ⁠34⁠ _、 ⁠45⁠ _、 ⁠56⁠ _、 ⁠67⁠ _、 ⁠11⁠ }

F ₈ = { ⁠01⁠ _、 ⁠18⁠ _、 ⁠17⁠ _、 ⁠16⁠ _、 ⁠15⁠ _、 ⁠14⁠ _、 ⁠27⁠ _、 ⁠13⁠ _、 ⁠38⁠ _、 ⁠25⁠ _、 ⁠37⁠ _、 ⁠12⁠ _、 ⁠47⁠ _、 ⁠35⁠ _、 ⁠58⁠ _、 ⁠23⁠ _、 ⁠57⁠ _、 ⁠34⁠ _、 ⁠45⁠ _、 ⁠56⁠ _、 ⁠67⁠ _、 ⁠78⁠ _、 ⁠11⁠ }

中央揃え
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⁠ }

ソート済み

F1 = {0/1, 1/1} F2 = {0/1, 1/2, 1/1} F3 = {0/1、1/3、1/2、2/3、1/1} F4 = {0/1、1/4、1/3、1/2、2/3、3/4、1/1} F5 = {0/1、1/5、1/4、1/3、2/5、1/2、3/5、2/3、3/4、4/5、1/1} F6 = {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} F7 = {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} F8 = {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 6 のような形状になります。$

この形状を対角軸と主軸を中心に鏡映すると、下図に示すファレイ・サンバーストが生成されます。n $次$ のファレイ・サンバーストは、原点を中心とし、辺が $2$ $n$ の正方形内の可視整数グリッド点を原点から結んだものです。ピックの定理を用いると、サンバーストの面積は $4(|$ $F$ $n$ $| - 1)$ となります。ここで、 $|$ $F$ $n$ $|$ はFnの分数の個数です。

歴史

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

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

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

プロパティ

分数のシーケンスの長さとインデックス

$n$ 次のファレイ数列は、それより低い次のファレイ数列のすべての要素を含む。特に、 $F nは$ $F n -1$ のすべての要素を含み、さらに $nより小さく$ $n$ と互いに素な数ごとに分数を含む。したがって、F $6$ $は$ $F$ $5$ と分数 ⁠から構成される。1/6⁠と⁠5/6⁠。

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

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

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

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

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

$| F n |$ の漸近挙動は次の通りである: $|F_{n}|\sim {\frac {3n^{2}}{\pi ^{2}}}.$

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

{\mathcal {N}}_{n}(1)=n

、

{\mathcal {N}}_{n}(p^{m})=\left\lceil (n-p^{m})\left(1-1/p\right)\right\rceil

任意の素数に対して、

p

{\mathcal {N}}_{n+mh}(h)={\mathcal {N}}_{n}(h)+m\varphi (h)

任意の整数

m \geq 0

に対して、

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

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

ファレイ数列における分数の指数は、単に数列中における位置です。これは、リーマン予想の別の定式化（後述）で使用されるため、特に重要です。以下に、様々な有用な性質を示します。 $I_{n}(a_{k,n})=k$ $a_{k,n}$ $F_{n}=\{a_{k,n}:k=0,1,\ldots ,m_{n}\}$ $a_{k,n}$ ${\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 / け ⁠$ どこ $⁠$ $n / 私 +1 ⁠ < k \leq ⁠ n / 私 ⁠$ そして $n$ は最初の $i個の数の$ 最小公倍数、 $n$ $= lcm([2,$ $i$ $])$ であり、次のように与えられる:^[8] $I_{n}(1/k)=1+n\sum _{j=1}^{i}{\frac {\varphi (j)}{j}}-k\Phi (i).$

同様の式は、F.ドレスの古典的な論文^[9]で、低い値のに対する近似値として使われました。任意のファレイ分数に対する一般的な式は^[10]で与えられています。 $I_{n}(x)$ $x$ $I_{n}(h/k)$ $h/k$

フェアリーの隣人

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

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

これは、 $bc-ad=1.$

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

逆もまた真なり。もし $bc-ad=1$

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

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

これは前の性質から容易に導かれる。なぜなら、 ${\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 ⁠$ と $⁠$ $c / d ⁠$ がファレイ数列で隣り合う場合、ファレイ数列の順序が増加するにつれてそれらの間の最初の項は ${\frac {a+c}{b+d}},$

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

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

$F n$ の Farey 隣接ペアの総数は $2| F n | - 3$ です。

シュテルン・ブロコット木は、シーケンスが0 （＝⁠からどのように構築されるかを示すデータ構造です。0/1⁠ )と 1 ( = ⁠1/1⁠ )を、連続する中数を取ることによって構築します。ただし、 $Stern-Brocot木の構築におけるn番目のステップでは、分母が$ $n$ に等しいものだけでなく、すべての中数が含まれることに注意してください。

等価面積解釈

連続するファレイ有理数の組は、面積が1である。^[11] 連続する有理数を xy平面上のベクトル $($ $p$ $,$ $q$ $)$ として解釈すると、このことが分かる。面積は次のように与えられる。連続する2つのファレイ数列分数の間に加えられる分数は、中分数(⊕)として計算されるので、 ( $r$ $1$ $=$ $⁠なので)$ $r_{1}={\frac {p}{q}}\qquad r_{2}={\frac {p'}{q'}}$ $A\left({\frac {p}{q}},{\frac {p'}{q'}}\right)=qp'-q'p.$ ${\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 2 = ⁠ 0 / 1 ⁠$ 、その面積は 1) でなければなりません。

フェアリー近傍と連分数

ファレイ数列において隣接する分数は、密接に関連した連分数展開を持つ。すべての分数には2つの連分数展開があり、1つは最終項が1であり、もう1つは最終項が1だけ大きい。もし $⁠$ $p / q ⁠ は$ $、ファレイ数列F q$ に初めて現れるが、連分数展開は ${\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$ （分母が大きい方の隣の分数）は連分数展開を持つ $。$ $[0;\ a_{1},\ a_{2},\ \ldots ,\ a_{n}]$

そして、その他の隣接関数は連分数展開を持つ。 $[0;\ a_{1},\ a_{2},\ \ldots ,\ a_{n-1}]$

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

ファレー分数と最小公倍数

最小公倍数は、次のようにファレー分数の積として表すことができます。 ${\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チェビシェフ関数である。^[12]^[13]

ファレー分数と最大公約数

オイラーのトーシェント関数は最大公約数に直接関連しているので、 $F n$ の要素数も同様である。 $|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 ⁠ 、 ⁠ c / d ⁠ 、 ⁠ e / f ⁠$ 2×2行列の絶対値行列式のの間には次の恒等式が成り立つ:^[14]^[8]

$\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)$

アプリケーション

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

^{共鳴現象を伴う物理系において、ファレイ列は1次元[17]}および2次元^[18]における共鳴位置を計算するための非常にエレガントで効率的な方法を提供する。

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

フォードサークル

nが1から9までの円弧を持つフォード円とファレー図の比較。各円弧は対応する円と直角に交差します。SVG画像では、円または曲線にマウスポインターを合わせると、円または曲線とその項がハイライト表示されます。

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

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

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

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

リーマン予想

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

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

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

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

ファレイ分数を含むその他の合計

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

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

$\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・ブレイクによって実証された。^[24]ハロルド・L・アーロン予想の一行証明は以下の通りである。分子の和は、分母の和は、最初の和を2番目の和で割った商は、⁠ $1+\sum _{2\leq b\leq n}\ \sum _{(a,b)=1}a=1+\sum _{2\leq b\leq n}b{\frac {\varphi (b)}{2}}.$ $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$ の順序付き分母とすると、次の式が成り立ちます。^[25]

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

$F$ $n$ の $j$ 番目のファレイ分数を ${\tfrac {a_{j}}{b_{j}}}$ $\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,$

^{これは[26]}で実証されています。また、この参考文献によると、合計内の項はさまざまな方法で表現できます。 $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の周りの対称性を利用すると、前者の和は列の半分に制限される。

$\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$ 次ファレイ列です。 $M(n)=-1+\sum _{a\in {\mathcal {F}}_{n}}e^{2\pi ia}$ ${\mathcal {F}}_{n}$

この式はフランネル・ランダウの定理の証明に使われる。^[27]

次の学期

F _nの項を伝統的な順序（昇順）または非伝統的な順序（降順）で生成する、驚くほどシンプルなアルゴリズムが存在します。このアルゴリズムは、前述の中位性を用いて、各項を前の2つの項を用いて計算します。もし、⁠1つの/b⁠と⁠c/d⁠は与えられた2つのエントリであり、⁠p/q⁠は未知の次のエントリです $。$ $c / d ⁠ = ⁠ a + p / b + q ⁠$ . 以来⁠c/d⁠ を最小項で表すと、 $kc$ $=$ $a$ $+$ $p$ かつ $kd$ $=$ $b$ $+$ $q$ となる整数kが存在し、 $p$ $=$ $kc$ $-$ $a$ かつ $q$ $=$ $kd$ $-$ $b$ となる。pとqをkの関数とみなすと、

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

kが大きくなるほど、⁠p/q⁠ ⁠に到達するc/d⁠。

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

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

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

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

分数から分数をインポートする   collections.abcからジェネレータをインポート   def farey_sequence ( n : int , descending : bool = False ) ->ジェネレータ[分数]:         「」 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 利回り 分数( a ,  b )  0  <=  c  <=  nの場合: k  =  ( n  +  b )  //  d a 、 b 、 c 、 d  =  c 、 d 、 k  *  c  -  a 、 k  *  d  -  b 利回り 分数( a ,  b )

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

参照

脚注

^ 「分母がnを超えないすべての約分数を大きさの順に並べたものを、n位のファレイ数列と呼ぶ。」注釈：「このファレイ数列の定義は最も便利と思われる。しかし、分数を0から1の範囲に限定することを好む著者もいる。」— Niven & Zuckerman (1972) ^[1]

参考文献

^ Niven, Ivan M. ; Zuckerman, Herbert S. (1972). 『数論入門（第3版）』John Wiley and Sons. 定義6.1.
^ Guthery, Scott B. (2011). 「1. 中位数」. 『数学のモチーフ：中位数とファレイ数列の歴史と応用』 . ボストン：ドセント・プレス. p. 7. ISBN 978-1-4538-1057-6. OCLC 1031694495 . 2020年9月28日閲覧。
^ ハーディ, GH ;ライト, EM (1979). 『数論入門』（第5版）. オックスフォード大学出版局. 第3章. ISBN 0-19-853171-0。
^ ab Beiler, Albert H. (1964). Recreations in the Theory of Numbers (Second ed.). Dover. Chapter XVI. ISBN 0-486-21096-0。 {{cite book}}: ISBN / Date incompatibility (help)「Farey Series, A Story」に引用。Cut -the-Knot。
^ ジョン・フェアリー・シニア（1816）「俗分数の奇妙な性質について」『哲学雑誌』47 : 385–386
^ Sloane, N. J. A. (編). 「シーケンスA005728」.整数シーケンスのオンライン百科事典. OEIS財団.
^ Tomas Garcia, Rogelio (2024 年7月). 「分子が等しいFarey分数と単位分数の階数」(PDF) . Integers . 24. arXiv : 2404.08283 . doi :10.5281/zenodo.12685697.
^ ab Tomas, Rogelio (2022年1月). 「部分フランエル和」(PDF) . Journal of Integer Sequences . 25 (1).
^ ドレス、F. (1999)。「Farey のスイートの不一致」(PDF)。J. テオリデ Nr.ボルドックス。１１．
^ Tomas Garcia, Rogelio (2025). 「ファレイ分数の階数と局所的不一致の推定に関する新しい解析式」.数学. 13 (1): 140. doi : 10.3390/math13010140 .
^ Austin, David (2008年12月). 「木、歯、そして時間：時計作りの数学」アメリカ数学会. ロードアイランド州. 2020年2月4日時点のオリジナルよりアーカイブ。 2020年9月28日閲覧。
^ Martin, Greg (2009). 「分母が同じ分数のガンマ関数値の積」arXiv : 0907.4384 [math.CA].
^ Wehmeier, Stefan (2009). 「Farey列の点にわたってサンプリングされた正弦値の積としてのLCM(1,2,...,n)」. arXiv : 0909.1838 [math.CA].
^ Tomas Garcia, Rogelio (2020年8月). 「3つの互いに素な対を含む最大公約数間の等式」(PDF) .数論と離散数学に関するノート. 26 (3): 5– 7. doi : 10.7546/nntdm.2020.26.3.5-7 . S2CID 225280271.
^ “Farey 近似”. NRICH.maths.org . 2018年11月19日時点のオリジナルよりアーカイブ。2018年11月18日閲覧。
^ Eliahou, Shalom (1993年8月). 「3x+1問題：非自明な閉路長の新たな下限値」.離散数学. 118 ( 1–3 ): 45–56 . doi : 10.1016/0012-365X(93)90052-U .
^ Zhenhua Li, A.; Harter, WG (2015). 「モース発振器の量子的復活とファリー・フォード幾何学」. Chem. Phys. Lett . 633 : 208– 213. arXiv : 1308.4470 . Bibcode :2015CPL...633..208L. doi :10.1016/j.cplett.2015.05.035. S2CID 66213897.
^ Tomas, R. (2014). 「ファレイ列から共鳴図へ」(PDF) .フィジカル・レビュー特集号加速器とビーム. 17 (1) 014001.書誌コード:2014PhRvS..17a4001T. doi : 10.1103/PhysRevSTAB.17.014001 .
^ ハボル、ダニエル・ダミール;グラスティン、アルバン。オズ、ディンダル。アクサカリ、ヴラル（2016年5月26日）。「実践における最適な任意角度パスファインディング」。人工知能研究ジャーナル。56 : 89–118 .土井: 10.1613/jair.5007。
^ Hew, Patrick Chisan (2017年8月19日). 「二項占有グリッドにおける最短頂点パスの長さとr制約グリッドにおける最短頂点パスの長さの比較」. Journal of Artificial Intelligence Research . 59 : 543–563 . doi : 10.1613/jair.5442 .
^ Tomas, Rogelio (2020). 「不完全性と補正」. arXiv : 2006.10661 [physics.acc-ph].
^ フランネル、ジェローム(1924)。「ファレーと貴族の第一の問題」。Nachrichten von der Gesellschaft der Wissenschaften zu Göttingen。数学物理学クラス (フランス語): 198–201。
^ エドマンド・ランダウ(1924)。「ヘルン・フランネルのベーメルクンゲン・ツー・デア・ヴォルステヘンデン・アブハンドルング」。Nachrichten von der Gesellschaft der Wissenschaften zu Göttingen。数学物理学クラス (ドイツ語): 202–206。
^ Blake, Jean A. (1966). 「ファレイ級数のいくつかの特徴的性質」.アメリカ数学月刊誌. 73 (1): 50– 52. doi :10.2307/2313922. JSTOR 2313922.
^ Kurt Girstmair; Girstmair, Kurt (2010). 「Farey和とDedekind和」.アメリカ数学月刊誌. 117 (1): 72– 78. doi :10.4169/000298910X475005. JSTOR 10.4169/000298910X475005. S2CID 31933470.
^ ホール、RR;シウ、P. (2003)。「フェアリーシーケンスのインデックス」。ミシガン州の数学。 J. 51 (1): 209–223。土井: 10.1307/mmj/1049832901。
^ エドワーズ, ハロルド・M. (1974). 「12.2 雑学. リーマン予想とファレー級数」 .スミス, ポール・A. ;エレンバーグ, サミュエル(編).リーマンのゼータ関数. 純粋・応用数学. ニューヨーク:アカデミック・プレス. pp. 263– 267. ISBN 978-0-08-087373-2. OCLC 316553016 . 2020年9月30日閲覧。
^ Routledge, Norman (2008年3月). 「Computing Farey series」. The Mathematical Gazette . 第92巻、第523号、pp. 55– 62.

さらに読む

ハッチャー、アレン（2022年）、数の位相学、プロビデンス、ロードアイランド州：アメリカ数学会、ISBN 978-1470456115
グラハム, ロナルド L. ;クヌース, ドナルド E. ;パタシュニク, オレン(1989). 『具体的な数学：コンピュータサイエンスの基礎』（第2版）. ボストン, マサチューセッツ州: アディソン・ウェスレー. pp. 115– 123, 133– 139, 150, 462– 463, 523– 524. ISBN 0-201-55802-5。特に、§4.5（115〜123ページ）、ボーナス問題4.61（150ページ、523〜524ページ）、§4.9（133〜139ページ）、§9.3、問題9.3.6（462〜463ページ）を参照してください。
ヴェプスタス、リナス. 「ミンコフスキー疑問符、GL(2,Z)、およびモジュラー群」(PDF) .— シュテルン・ブロコット木の同型性を復習します。
ヴェプスタス、リナス。「周期倍加写像の対称性」（PDF）。— ファレイ分数とフラクタルの関係を復習します。
コベリ, クリスチャン; ザハレスク, アレクサンドル (2003). 「200年前のハロス-ファレイ系列。概観」.アクタ大学アプレンシス数学. インフォーム. (5): 1– 38. 「1～20ページ」（PDF）。アクタ大学アプレンシス。「21～38ページ」（PDF）。アクタ大学アプレンシス。
マトヴェエフ、アンドレイ・O. (2017). 『ファレイ列：部分列間の双対性と写像』ベルリン、ドイツ: De Gruyter. ISBN 978-3-11-054662-0。エラッタ + コード

外部リンク

ハッチャー、アレン。「数の位相幾何学」（PDF）。本のオンラインコピー
ボゴモーリニー、アレクサンダー. 「ファリーシリーズ」. 「カット・ザ・ノット」.
ボゴモーリニー、アレクサンダー. 「シュテルン・ブロコット・ツリー」. 「カット・ザ・ノット」 .
ペンネストリ、エットーレ。「120を底とするブロコ表」
「ファリー級数」数学百科事典、EMSプレス、2001 [1994]
ワイスタイン、エリック・W.「シュテルン・ブロコット木」。MathWorld。
OEISシーケンスA005728（n次のファレイ級数の分数の個数）
OEISシーケンス A006842 (n 次のファリー級数の分子)
OEIS配列A006843（n次のファレイ級数の分母）
GhostarchiveとWayback Machineにアーカイブ：Bonahon, Francis . Funny Fractions and Ford Circles (video). Brady Haran . 2015年6月9日閲覧– YouTube経由。

[2] 「分母がnを超えないすべての約分数を大きさの順に並べたものを、n位のファレイ数列と呼ぶ。」注釈：「このファレイ数列の定義は最も便利と思われる。しかし、分数を0から1の範囲に限定することを好む著者もいる。」— Niven & Zuckerman (1972) ^[1]

[1] Niven, Ivan M. ; Zuckerman, Herbert S. (1972). 『数論入門（第3版）』John Wiley and Sons. 定義6.1.

[3] Guthery, Scott B. (2011). 「1. 中位数」. 『数学のモチーフ：中位数とファレイ数列の歴史と応用』 . ボストン：ドセント・プレス. p. 7. ISBN 978-1-4538-1057-6. OCLC 1031694495 . 2020年9月28日閲覧。

[4] ハーディ, GH ;ライト, EM (1979). 『数論入門』（第5版）. オックスフォード大学出版局. 第3章. ISBN 0-19-853171-0。

[Beiler-5] Beiler, Albert H. (1964). Recreations in the Theory of Numbers (Second ed.). Dover. Chapter XVI. ISBN 0-486-21096-0。 {{cite book}}: ISBN / Date incompatibility (help)「Farey Series, A Story」に引用。Cut -the-Knot。

[6] ジョン・フェアリー・シニア（1816）「俗分数の奇妙な性質について」『哲学雑誌』47 : 385–386

[7] Sloane, N. J. A. (編). 「シーケンスA005728」.整数シーケンスのオンライン百科事典. OEIS財団.

[Tomas2024-8] ^ Tomas Garcia, Rogelio (2024 年7月). 「分子が等しいFarey分数と単位分数の階数」(PDF) . Integers . 24. arXiv : 2404.08283 . doi :10.5281/zenodo.12685697.

[Tomas2018-9] Tomas, Rogelio (2022年1月). 「部分フランエル和」(PDF) . Journal of Integer Sequences . 25 (1).

[Dress1999-10] ドレス、F. (1999)。「Farey のスイートの不一致」(PDF)。J. テオリデ Nr.ボルドックス。１１．

[Tomas2025-11] Tomas Garcia, Rogelio (2025). 「ファレイ分数の階数と局所的不一致の推定に関する新しい解析式」.数学. 13 (1): 140. doi : 10.3390/math13010140 .

[Austin2008-12] Austin, David (2008年12月). 「木、歯、そして時間：時計作りの数学」アメリカ数学会. ロードアイランド州. 2020年2月4日時点のオリジナルよりアーカイブ。 2020年9月28日閲覧。

[13] Martin, Greg (2009). 「分母が同じ分数のガンマ関数値の積」arXiv : 0907.4384 [math.CA].

[14] Wehmeier, Stefan (2009). 「Farey列の点にわたってサンプリングされた正弦値の積としてのLCM(1,2,...,n)」. arXiv : 0909.1838 [math.CA].

[TomasGarcia2020-15] Tomas Garcia, Rogelio (2020年8月). 「3つの互いに素な対を含む最大公約数間の等式」(PDF) .数論と離散数学に関するノート. 26 (3): 5– 7. doi : 10.7546/nntdm.2020.26.3.5-7 . S2CID 225280271.

[16] “Farey 近似”. NRICH.maths.org . 2018年11月19日時点のオリジナルよりアーカイブ。2018年11月18日閲覧。

[17] Eliahou, Shalom (1993年8月). 「3x+1問題：非自明な閉路長の新たな下限値」.離散数学. 118 ( 1–3 ): 45–56 . doi : 10.1016/0012-365X(93)90052-U .

[18] Zhenhua Li, A.; Harter, WG (2015). 「モース発振器の量子的復活とファリー・フォード幾何学」. Chem. Phys. Lett . 633 : 208– 213. arXiv : 1308.4470 . Bibcode :2015CPL...633..208L. doi :10.1016/j.cplett.2015.05.035. S2CID 66213897.

[19] Tomas, R. (2014). 「ファレイ列から共鳴図へ」(PDF) .フィジカル・レビュー特集号加速器とビーム. 17 (1) 014001.書誌コード:2014PhRvS..17a4001T. doi : 10.1103/PhysRevSTAB.17.014001 .

[20] ハボル、ダニエル・ダミール;グラスティン、アルバン。オズ、ディンダル。アクサカリ、ヴラル（2016年5月26日）。「実践における最適な任意角度パスファインディング」。人工知能研究ジャーナル。56 : 89–118 .土井: 10.1613/jair.5007。

[21] Hew, Patrick Chisan (2017年8月19日). 「二項占有グリッドにおける最短頂点パスの長さとr制約グリッドにおける最短頂点パスの長さの比較」. Journal of Artificial Intelligence Research . 59 : 543–563 . doi : 10.1613/jair.5442 .

[Tomas2020-22] Tomas, Rogelio (2020). 「不完全性と補正」. arXiv : 2006.10661 [physics.acc-ph].

[23] フランネル、ジェローム(1924)。「ファレーと貴族の第一の問題」。Nachrichten von der Gesellschaft der Wissenschaften zu Göttingen。数学物理学クラス (フランス語): 198–201。

[24] エドマンド・ランダウ(1924)。「ヘルン・フランネルのベーメルクンゲン・ツー・デア・ヴォルステヘンデン・アブハンドルング」。Nachrichten von der Gesellschaft der Wissenschaften zu Göttingen。数学物理学クラス (ドイツ語): 202–206。

[25] Blake, Jean A. (1966). 「ファレイ級数のいくつかの特徴的性質」.アメリカ数学月刊誌. 73 (1): 50– 52. doi :10.2307/2313922. JSTOR 2313922.

[26] Kurt Girstmair; Girstmair, Kurt (2010). 「Farey和とDedekind和」.アメリカ数学月刊誌. 117 (1): 72– 78. doi :10.4169/000298910X475005. JSTOR 10.4169/000298910X475005. S2CID 31933470.

[27] ホール、RR;シウ、P. (2003)。「フェアリーシーケンスのインデックス」。ミシガン州の数学。 J. 51 (1): 209–223。土井: 10.1307/mmj/1049832901。

[28] エドワーズ, ハロルド・M. (1974). 「12.2 雑学. リーマン予想とファレー級数」 .スミス, ポール・A. ;エレンバーグ, サミュエル(編).リーマンのゼータ関数. 純粋・応用数学. ニューヨーク:アカデミック・プレス. pp. 263– 267. ISBN 978-0-08-087373-2. OCLC 316553016 . 2020年9月30日閲覧。

[29] Routledge, Norman (2008年3月). 「Computing Farey series」. The Mathematical Gazette . 第92巻、第523号、pp. 55– 62.