ファレイ数列

数学で、ファレイ数列（ファレイすうれつ、フェアリー数列とも, Farey sequence [ˈfɛəri -]) とは、既約分数を順に並べた一群の数列であり、以下に述べるような初等整数論における興味深い性質を持つ。 正確にいえば、 自然数 n に対して、n に対応する（または、属する）ファレイ数列 (Farey sequence of order n) Fn とは、分母が n 以下で、 0 以上 1 以下の全ての既約分数を小さい順から並べてできる有限数列である。 ただし、整数 0, 1 はそれぞれ分数 0/1, 1/1 として扱われる。 定義によっては 0, 1 は数列から省かれる場合もある。 なお、英語では Farey series と呼ばれることも多いが、series（級数）の定義からいえば厳密には誤りである。 ファレイ数列 Fn は、具体的に n = 1, …, 8 のとき次のようになる： 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) 2 つの分数 a/b と c/d が、あるファレイ数列で隣接しているならば、この 2 つの分数の間に新たな分数が加わるのは次数 b + d のファレイ数列においてであり、それは a/b, c/d の中間数（英語版）（英: mediant）と呼ばれる分数、 a + c/b + d である。 例えば、F5 では隣接している 1/3 と 2/5 の間に現れる最初の項は F8 の 3/8 である。 もし a/b と c/d が、あるファレイ数列でこの順で隣接するなら、その差は bc − ad/bd となるが、ファレイ数列の隣接する分数では bc−ad = 1 が成立し、差は分母の積の逆数 1/bd に等しくなる。 例えば、1/3 と 2/5 の差は 1/15 である。この逆もまた真となる。 もし 0 ≤ a/b < c/d ≤ 1 であるような負でない整数 a, c と正の整数 b, d に対し、bc − ad = 1 が成り立つならば、a/b と c/d は、max {b, d} に対応するファレイ数列において隣接する。 なお、シュターン＝ブロコ木（英語版）（スターン＝ブロコット木、英: Stern–Brocot tree）として知られている木構造は、0 = 0/1 と便宜的な無限大の表現 1/0 から始め、中間数を繰り返し取ることによって 0 以上の既約分数列を作り上げる方法を示すものであり、ファレイ数列と密接な関係がある。 ファレイ数列で隣接する分数は連分数展開と密接な関係がある。 全ての分数は最後の項が 1 となるように連分数展開を行うことができる。 例えば、3/8 のこのような連分数展開は、 3 8 = 0 + 1 2 + 1 1 + 1 2 = 0 + 1 2 + 1 1 + 1 1 + 1 1 = [ 0 ; 2 , 1 , 1 , 1 ] {\displaystyle {\frac {3}{8}}=0+{\frac {1}{2+{\frac {1}{1+{\frac {1}{2}}}}}}=0+{\frac {1}{2+{\frac {1}{1+{\frac {1}{1+{\frac {1}{1}}}}}}}}=[0;2,1,1,1]} となる。 一般に、もし p/q がファレイ数列 Fq で初めて現れる分数で連分数展開 [0; a1, a2, ..., an−1, an, 1] を持つならば、Fq で p/q に隣接する 2 つの分数のうち、値として近い方の分数（これは、分母がより大きな方となる）は、連分数 [0; a1, a2, …, an−1, an] に展開され、もう一方の隣接する分数は、 [0; a1, a2, …, an−1] となる。 例えば、F8 で 3/8 = [0; 2, 1, 1, 1] に隣接する分数 2/5 と 1/3 では、2/5 の方が 3/8 に近く、連分数 [0; 2, 1, 1] に展開される。他方の 1/3 は [0; 2, 1] となる。 ファレイ数列とフォードの円 (en:Ford circle) との間にも面白い関係がある。 任意の既約分数 p/q に対して、フォードの円 C[p/q] は中心が平面座標 ( p q , 1 2 q 2 ) {\displaystyle \left({\frac {p}{q}},{\frac {1}{2q^{2}}}\right)} にある半径 1 2 q 2 {\displaystyle {\frac {1}{2q^{2}}}} の円である。 異なる 2 つの分数に対する 2 つのフォードの円は、互いに交わらないか接しているかのどちらかであって交わることはない。 もし、0 < p/q < 1 ならば、C[p/q] に接するフォードの円とはまさにあるファレイ数列において隣接する分数のフォードの円に他ならない。 例えば、C[1/2], C[1/3] に接する円は 1 + 1/2 + 3 から 中間数 C[2/5] の円を作っている。両端の円は 0/1 , 1/1 と考えれば他の円においても同様である。 n に対応するファレイ数列の長さ |Fn| は、オイラーの (トーティエント) 関数 φ を用いて、 | F n | = 1 + ∑ m = 1 n φ ( m ) {\displaystyle |F_{n}|=1+\sum _{m=1}^{n}\varphi (m)} と書ける。 この |Fn| の漸近的振舞いは、オイラーの関数の性質から、 | F n | ∼ 3 n 2 π 2 {\displaystyle |F_{n}|\sim {\frac {3n^{2}}{\pi ^{2}}}} となることが知られている。 数列の長さがオイラーの関数で書けることは次のようにして確かめられる。 n に対応するファレイ数列は、定義から明らかなように n 未満の正の整数に対応するファレイ数列の数を全て含んでいなければならない。 特に、n に対応するファレイ数列 Fn (n > 1) は、Fn−1 に、分母が n で分子が n と互いに素な n 未満の各数であるような分数を付け加えたものになる。 例えば、F8 は F7 に {1/8, 3/8, 5/8, 7/8} を加えて並べ替えたものである。 オイラーの関数はまさにその引数以下でその数と互いに素な数の個数を表すものであるから、 |Fn| と |Fn−1| (n > 1) の関係は、 |Fn| = |Fn−1| + φ(n) となることになり、初項 |F1| = 2 から最初の式が従う。 非線形力学のような意外な場面で、このファレイ数列やシュターン＝ブロコ木（英）のような分数の関係が現れることがある。 それぞれ単独では振動数（固有振動数）の異なる 2 つの振動子が非線形な影響を与え合う場合、適当な条件の下でそれらが一定の位相のずれをもって振動数が一致する、もしくはある単純な有理数比になることがある。 例えば元の振動数の比が 1 対 2 にある程度近ければ、それらを結合させると正確に 1 対 2 で振動するようになる。 これは引き込み現象として知られている。 一方の振動子のパラメータを操作し固有振動数を変えていくと、引き込みの起きない領域を間に挟んで、固有振動数の比に近いさまざまな有理数比で引き込むことになる。 このとき、ある理想的な場合には、有理数比の現れる順序と現れやすさがシュターン＝ブロコ木の構成と本質的に一致している。 すなわち例えば、1 対 2 と 2 対 3 で引き込むパラメータ領域の間には、それらの中間数である 3 対 5 で引き込むようなより狭い範囲のパラメータ領域が存在している。 ファレイ数列という名前は、イギリスの地質学者ジョン・フェアリー（英語版）に因む。 1816年の「フィロソフィカル・マガジン」(Philosophical Magazine) にこの数列を扱ったフェアリーの要約論文が掲載されている。 この中でフェアリーは、ファレイ数列の各項が、隣接する数の中間数になると推測しているが、知られている限りではフェアリーはこの証明を与えていない。 コーシーはフェアリーの論文を読み、著作 Exercises de mathématique においてその証明を与え、その結果をフェアリーによるものとしている。 おそらくフェアリーやコーシーの知るところではなかったが、類似の結果は 1802 年に数学者シャルル・アロ（英語版）によってすでに出版されていた。 よって、この数列にフェアリーの名が与えられているのは歴史のいたずらの一つといえる。 コンウェイ, J.H., ガイ, R.K （根上生也訳）『数の本』, 2001, シュプリンガー・フェアラーク東京, ISBN 4431707700; Conway, J.H. & Guy, R.K., The Book of Numbers, c1996, Copernicus: New York, ISBN 038797993X. ハーディ, G.H., ライト, E.M.（示野信一、矢神毅訳）『数論入門 (1)』, 2001, シュプリンガー・フェアラーク東京, ISBN 4431708480; Hardy, G.H. & Wright, E.M., An Introduction to the Theory of Numbers (5th ed), 1979, Oxford Univ. Pr. ISBN 0198531710.