Ряд Фарея

Діаграма Фарея для послідовності ${\displaystyle F_{9}}$ з використанням дуг кіл. На SVG зображені наведіть курсор на криву, щоб виділити її та її члени.

Діаграма Фарея для ${\displaystyle F_{9}}$

У математиці послідовність Фарея порядку ${\displaystyle n}$ — це послідовність нескоротних дробів, від 0 до 1, або без цього обмеження, знаменники яких менші або рівні ${\displaystyle n}$, а дроби розташовані в порядку зростання.

У рамках обмеженого означення кожна[1] послідовність Фарея починається зі значення 0 (позначається як дріб ${\displaystyle {\frac {0}{1}}}$) і закінчується значенням 1 (позначається як дріб ${\displaystyle {\frac {1}{1}}}$), хоча деякі автори опускають ці члени.

Симетричний візерунок, утворений знаменниками послідовності Фарея ${\displaystyle F_{9}}$.

Послідовність Фарея іноді називають рядом Фарея, що не зовсім коректно, оскільки дроби не підсумовуються[2].

Симетричний візерунок, утворений знаменниками послідовності Фарея ${\displaystyle F_{25}}$.

Наприклад, ряд Фарея порядку 5:

${\displaystyle 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\}.}$

Приклади

Послідовність Фарея порядку від 1 до 8:

${\displaystyle F_{1}=\left\{{\frac {0}{1}},{\frac {1}{1}}\right\},}$

${\displaystyle F_{2}=\left\{{\frac {0}{1}},{\frac {1}{2}},{\frac {1}{1}}\right\},}$

${\displaystyle F_{3}=\left\{{\frac {0}{1}},{\frac {1}{3}},{\frac {1}{2}},{\frac {2}{3}},{\frac {1}{1}}\right\},}$

${\displaystyle 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\},}$

${\displaystyle 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\},}$

${\displaystyle F_{6}=\left\{{\frac {0}{1}},{\frac {1}{6}},{\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 {5}{6}},{\frac {1}{1}}\right\},}$

${\displaystyle F_{7}=\left\{{\frac {0}{1}},{\frac {1}{7}},{\frac {1}{6}},{\frac {1}{5}},{\frac {1}{4}},{\frac {2}{7}},{\frac {1}{3}},{\frac {2}{5}},{\frac {3}{7}},{\frac {1}{2}},{\frac {4}{7}},{\frac {3}{5}},{\frac {2}{3}},{\frac {5}{7}},{\frac {3}{4}},{\frac {4}{5}},{\frac {5}{6}},{\frac {6}{7}},{\frac {1}{1}}\right\},}$

${\displaystyle F_{8}=\left\{{\frac {0}{1}},{\frac {1}{8}},{\frac {1}{7}},{\frac {1}{6}},{\frac {1}{5}},{\frac {1}{4}},{\frac {2}{7}},{\frac {1}{3}},{\frac {3}{8}},{\frac {2}{5}},{\frac {3}{7}},{\frac {1}{2}},{\frac {4}{7}},{\frac {3}{5}},{\frac {5}{8}},{\frac {2}{3}},{\frac {5}{7}},{\frac {3}{4}},{\frac {4}{5}},{\frac {5}{6}},{\frac {6}{7}},{\frac {7}{8}},{\frac {1}{1}}\right\}.}$

Відцентровані
${\displaystyle F_{1}=\left\{{\frac {0}{1}},{\frac {1}{1}}\right\}}$
${\displaystyle F_{2}=\left\{{\frac {0}{1}},{\frac {1}{2}},{\frac {1}{1}}\right\}}$
${\displaystyle F_{3}=\left\{{\frac {0}{1}},{\frac {1}{3}},{\frac {1}{2}},{\frac {2}{3}},{\frac {1}{1}}\right\}}$
${\displaystyle 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\}}$
${\displaystyle 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\}}$
${\displaystyle F_{6}=\left\{{\frac {0}{1}},{\frac {1}{6}},{\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 {5}{6}},{\frac {1}{1}}\right\}}$
${\displaystyle F_{7}=\left\{{\frac {0}{1}},{\frac {1}{7}},{\frac {1}{6}},{\frac {1}{5}},{\frac {1}{4}},{\frac {2}{7}},{\frac {1}{3}},{\frac {2}{5}},{\frac {3}{7}},{\frac {1}{2}},{\frac {4}{7}},{\frac {3}{5}},{\frac {2}{3}},{\frac {5}{7}},{\frac {3}{4}},{\frac {4}{5}},{\frac {5}{6}},{\frac {6}{7}},{\frac {1}{1}}\right\}}$
${\displaystyle F_{8}=\left\{{\frac {0}{1}},{\frac {1}{8}},{\frac {1}{7}},{\frac {1}{6}},{\frac {1}{5}},{\frac {1}{4}},{\frac {2}{7}},{\frac {1}{3}},{\frac {3}{8}},{\frac {2}{5}},{\frac {3}{7}},{\frac {1}{2}},{\frac {4}{7}},{\frac {3}{5}},{\frac {5}{8}},{\frac {2}{3}},{\frac {5}{7}},{\frac {3}{4}},{\frac {4}{5}},{\frac {5}{6}},{\frac {6}{7}},{\frac {7}{8}},{\frac {1}{1}}\right\}}$

Відсортовані

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}

Графік залежності чисельника від знаменника дробів послідовності Фарея має вигляд подібний до наведеного для послідовності ${\displaystyle F_{6}}$. Віддзеркаленя цієї фігури відносно діагоналі та координатних осей утворює сонячний спалах Фарея, як показано нижче.

Сонячний спалах Фарея порядку ${\displaystyle n}$ з'єднує видимі цілі точки решітки з початком координат у квадраті зі стороною ${\displaystyle 2n}$ і центром у початку координат. Відповідно до теореми Піка, площа сонячного спалаху Фарея дорівнює ${\displaystyle 4(|F_{n}|-1)}$, де ${\displaystyle |F_{n}|}$ ― кількість дробів у послідовності ${\displaystyle F_{n}}$.

Ітерації 1–10

Історія

Історія «рядів Фарея» дуже цікава — Харді і Райт (1979)[3]

… і знову людина, чиє ім'я було дано математичному поняттю, не була його першовідкривачем, якщо вірити записам. — Бейлер (1964)[4]

Послідовність Фарея названа на честь британського геолога Джона Фарея старшого, який 1816 року опублікував замітку про ці послідовності у Філософському журналі. Він припустив, але без жодних доведень, що кожен новий дріб у послідовності є медіантою його сусідів. Замітку Фарея прочитав Коші, який довів цю гіпотезу в своїй роботі Exerces de mathématique, і приписав цей результат Фарею. Насправді, інший математик, Чарльз Гарос^[en], ще 1802 року опублікував аналогічні результати, які не були відомі ні Фарею, ні Коші.[5] Тому зв'язок Фарея з цією послідовністю просто історична випадковість. Це приклад вияву закону Стіглера про епонімію.

Властивості

Довжина послідовності та індекс дробу

Послідовність Фарея порядку ${\displaystyle n}$ містить усі члени послідовностей нижчих порядків. Зокрема, послідовність ${\displaystyle F_{n}}$ містить усі члени послідовності ${\displaystyle F_{n-1}}$ та додаткові дроби для кожного числа, яке менше ${\displaystyle n}$, та є взаємно простим з ${\displaystyle n}$. Таким чином, послідовність ${\displaystyle F_{6}}$ складається з послідовності ${\displaystyle F_{5}}$ та дробів ${\displaystyle {\frac {1}{6}}}$ і ${\displaystyle {\frac {5}{6}}}$.

Середнім дробом для послідовності Фарея ${\displaystyle F_{n}}$ завжди є ${\displaystyle {\frac {1}{2}}}$, за умови що ${\displaystyle n>1}$. Тому можемо пов'язати довжини послідовностей ${\displaystyle F_{n}}$ і ${\displaystyle F_{n-1}}$ за допомогою функції Ейлера ${\displaystyle \varphi (n)}$:

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

Використовуючи той факт, що ${\displaystyle |F_{1}|=2}$, можна вивести співвідношення для довжини послідовності ${\displaystyle F_{n}}$ :[6]

${\displaystyle |F_{n}|=1+\sum _{m=1}^{n}\varphi (m)=1+\Phi (n),}$

де ${\displaystyle \Phi (n)}$ ― сумарна тотієнт функція^[en].

Також довжину послідовності ${\displaystyle F_{n}}$ можна знайти за формулою:

${\displaystyle |F_{n}|={\frac {1}{2}}\left(3+\sum _{d=1}^{n}\mu (d)\left\lfloor {\frac {n}{d}}\right\rfloor ^{2}\right),}$

або за формулою інверсії Мебіуса^[en]:

${\displaystyle |F_{n}|={\frac {1}{2}}(n+3)n-\sum _{d=2}^{n}|F_{\lfloor {\frac {n}{d}}\rfloor }|,}$

де ${\displaystyle \mu (d)}$ ― теоретико-числова функція Мебіуса, ${\displaystyle \lfloor {\tfrac {n}{d}}\rfloor }$ ― функція підлоги.

Асимптотична поведінка послідовності ${\displaystyle |F_{1}|}$ визначається за формулою:

${\displaystyle |F_{n}|\sim {\frac {3n^{2}}{\pi ^{2}}}.}$

Індекс ${\displaystyle I_{n}(a_{k,n})=k}$ для дробу ${\displaystyle a_{k,n}}$ у послідовності Фарея ${\displaystyle F_{n}=\{a_{k,n}\colon k=0,1,\ldots ,m_{n}\}}$ це позиція, яку дріб ${\displaystyle a_{k,n}}$ займає в послідовності. Поняття індекса має особливе значення, оскільки використовується в альтернативному формулюванні гіпотези Рімана. Деякі корисні властивості:

${\displaystyle I_{n}(0/1)=0,}$

${\displaystyle I_{n}(1/n)=1,}$

${\displaystyle I_{n}(1/2)=(|F_{n}|-1)/2,}$

${\displaystyle I_{n}(1/1)=|F_{n}|-1,}$

${\displaystyle I_{n}(h/k)=|F_{n}|-1-I_{n}((k-h)/k).}$

Індекс дробу ${\displaystyle {\frac {1}{k}}}$, де ${\displaystyle {\frac {n}{i+1}}<k\leq {\frac {n}{i}}}$ і ${\displaystyle n}$ є найменшим спільним кратним перших ${\displaystyle i}$ чисел, тобто ${\displaystyle n={\rm {lcm}}([2,i])}$, обчислюється за формулою:[7]

${\displaystyle I_{n}\left({\frac {1}{k}}\right)=1+n\sum _{j=1}^{i}{\frac {\varphi (j)}{j}}-k\Phi (i).}$

Сусіди Фарея

Дроби, які є сусідніми в будь-якій послідовності Фарея, називають парами Фарея, вони мають такі властивості: Якщо ${\displaystyle {\frac {a}{b}}}$ і ${\displaystyle {\frac {c}{d}}}$ ― пара Фарея, при чому ${\displaystyle {\frac {a}{b}}<{\frac {c}{d}}}$, то їх різниця ${\displaystyle {\frac {a}{b}}-{\frac {c}{d}}}$ дорівнює ${\displaystyle {\frac {1}{bd}}}$. Це пов'язано з тим, що кожна послідовна пара раціональних чисел Фарея має еквівалентну площу 1[8].

Якщо ${\displaystyle r_{1}={\frac {p}{q}}}$ і ${\displaystyle r_{2}={\frac {p'}{q'}}}$ розглядати як вектори ${\displaystyle (p,q)}$ у площині ${\displaystyle xy}$, то площа ${\displaystyle A\left({\frac {p}{q}},{\frac {p'}{q'}}\right)}$ обчислюється як ${\displaystyle qp'-q'p}$. Оскільки будь-який дріб між двома попередніми послідовними дробами послідовності Фарея обчислюється як медіанта ${\displaystyle (\oplus )}$, то

${\displaystyle A(r_{1},r_{1}\oplus r_{2})=A(r_{1},r_{1}+A(r_{1},r_{2}+A(r_{1},r_{2}))=1}$

(оскільки ${\displaystyle r_{1}=1/0}$ і ${\displaystyle r_{2}=0/1}$, то його площа повинна дорівнювати одиниці).

Оскільки ${\displaystyle {\frac {c}{d}}-{\frac {a}{b}}={\frac {bc-ad}{bd}}}$, то це еквівалентно умові ${\displaystyle bc-ad=1}$. Таким чином, ${\displaystyle {\frac {1}{3}}}$ і ${\displaystyle {\frac {2}{5}}}$ ― сусіди в послідовності ${\displaystyle F_{5}}$, і їх різниця дорівнює ${\displaystyle {\frac {1}{15}}}$.

Обернене також істинне. Якщо

${\displaystyle bc-ad=1}$

для натуральних чисел ${\displaystyle a}$, ${\displaystyle b}$, ${\displaystyle c}$ і ${\displaystyle d}$ та ${\displaystyle a<b}$ і ${\displaystyle c<d}$, то дроби ${\displaystyle {\frac {a}{b}}}$ і ${\displaystyle {\frac {c}{d}}}$ ― пара Фарея порядку ${\displaystyle \max(b,d)}$.

Якщо ${\displaystyle {\frac {p}{q}}}$ має сусідів ${\displaystyle {\frac {a}{b}}}$ і ${\displaystyle {\frac {c}{d}}}$ у деякій послідовності Фарея, причому

${\displaystyle {\frac {a}{b}}<{\frac {p}{q}}<{\frac {c}{d}}}$,

то ${\displaystyle {\frac {p}{q}}}$ є медіантою дробів ${\displaystyle {\frac {a}{b}}}$ і ${\displaystyle {\frac {c}{d}}}$. Іншими словами:

${\displaystyle {\frac {p}{q}}={\frac {a+c}{b+d}}}$.

Це легко випливає з попередньої властивості, оскільки якщо ${\displaystyle bp-aq=qc-pd=1,}$ то ${\displaystyle bp+pd=qc+aq}$, ${\displaystyle p(b+d)=q(a+c)}$, ${\displaystyle {\frac {p}{q}}={\frac {a+c}{b+d}}}$.

З цього випливає, що якщо ${\displaystyle {\frac {a}{b}}}$ і ${\displaystyle {\frac {c}{d}}}$ є парою Фарея, то першим членом, який з'являється між ними при збільшенні порядку послідовності, буде ${\displaystyle {\frac {a+c}{b+d}}}$, і він же буде першим членом послідовності Фарея порядку ${\displaystyle b+d}$.

Наприклад, першим дробом, що з'являється між ${\displaystyle {\frac {1}{3}}}$ і ${\displaystyle {\frac {2}{5}}}$, є ${\displaystyle {\frac {3}{8}}}$ у послідовності ${\displaystyle F_{8}}$.

Загальна кількість пар Фарея в послідовності ${\displaystyle F_{n}}$ становить ${\displaystyle 2F_{n}-3}$.

Дерево Штерна — Броко ― це структура даних, яка показує побудову послідовності з 0 (= ${\displaystyle {\frac {0}{1}}}$) і 1 (= ${\displaystyle {\frac {1}{1}}}$) за допомогою послідовних медіант.

Сусіди Фарея та ланцюгові дроби

Дроби, що з'являються як сусіди в послідовності Фарея тісно пов'язані з розкладами ланцюгових дробів. Кожен дріб має два розклади на неперевні дроби ― один кінцевий член дорівнює 1, інший ― більший за 1. Якщо дріб ${\displaystyle {\frac {p}{q}}}$, який уперше з'являється в послідовності Фарея ${\displaystyle F_{q}}$, допускає розклади у вигляді ланцюгових дробів

${\displaystyle [0,a_{1},a_{2},\ldots ,a_{n-1},a_{n},1],}$

${\displaystyle [0,a_{1},a_{2},\ldots ,a_{n-1},a_{n}+1],}$

то один сусідній дріб дробу ${\displaystyle {\frac {p}{q}}}$ (який є його сусідом із більшим знаменником) у послідовності ${\displaystyle F_{q}}$ має розклад у ланцюговий дріб вигляду

${\displaystyle [0;a_{1},a_{2},\ldots ,a_{n}],}$

а його інший сусід має розклад у ланцюговий дріб вигляду

${\displaystyle [0;a_{1},a_{2},\ldots ,a_{n-1}].}$

Наприклад ${\displaystyle {\frac {3}{8}}}$ має два розклади у вигляді ланцюгових дробів: ${\displaystyle [0;2,1,1,1]}$ та ${\displaystyle [0;2,1,2]}$, а його сусідами в послідовності ${\displaystyle F_{8}}$ є ${\displaystyle {\frac {2}{5}}}$, який можна розкласти як ${\displaystyle [0;2,1,1]}$, та ${\displaystyle {\frac {1}{3}}}$, який можна розкласти як ${\displaystyle [0;2,1]}$.

Дроби Фарея та найменше спільне кратне

Найменше спільне кратне можна представити у вигляді добутку дробів послідовності Фарея

${\displaystyle {\text{lcm}}[1,2,\dots ,N]=e^{\psi (N)}={\frac {1}{2}}\left(\prod _{r\in F_{N},0<r\leq 1/2}2\sin(\pi r)\right)^{2},}$

де ${\displaystyle \psi (N)}$ ― друга функція Чебишова^[en][9][10].

Дроби Фарея та найбільший спільний дільник

Оскільки функція Ейлера безпосередньо пов'язана з найбільшим спільним дільником, так само як і кількість елементів у ${\displaystyle F_{n}}$, то ${\displaystyle |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}}}.}$

Для будь-яких трьох дробів послідовності Фарея ${\displaystyle {\frac {a}{b}}}$, ${\displaystyle {\frac {c}{d}}}$ і ${\displaystyle {\frac {e}{f}}}$ виконується рівність для найбільших спільних дільників абсолютних значень визначників матриць розмірності 2x2:[11],[12]

${\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).}$

Застосування

Послідовності Фарея дуже корисні для пошуку раціональних наближень ірраціональних чисел.[13] Наприклад, побудова Еліахау[14] нижньої межі довжини нетривіальних циклів у ${\displaystyle 3x+1}$ процесі використовує послідовності Фарея для обчислення розкладу в ланцюговий дріб числа ${\displaystyle \log _{2}(3)}$.

У фізичних системах із резонансними явищами послідовності Фарея забезпечують дуже простий і ефективний метод обчислення резонансних позицій для розмірностей 1[15] та 2[16].

Послідовності Фарея посідають важливе місце в дослідженнях планування шляху під будь-яким кутом^[en] на клітинках квадратів сітки, наприклад, для характеристики їх обчислювальної складності[17] або оптимальності[17]. З'єднання можна розглядати з точки зору ${\displaystyle r}$-обмежених шляхів, а саме шляхів, які складаються з відрізків, кожен з яких перетинає максимум ${\displaystyle r}$ рядків і не більше ${\displaystyle r}$ стовпців клітинок. Нехай ${\displaystyle Q}$ ― множина взаємнопростих векторів ${\displaystyle (q,p)}$ таких, що ${\displaystyle 1\leq q\leq r}$, ${\displaystyle 0\leq p\leq q}$. Нехай ${\displaystyle Q*}$ ― результат відбиття множини ${\displaystyle Q}$ відносно прямої ${\displaystyle y=x}$. Нехай ${\displaystyle S=\{(\pm x,\pm y)\colon (x,y)\in Q\cup Q*\}.}$ Тоді будь-який ${\displaystyle r}$-обмежений шлях можна описати як послідовність векторів з ${\displaystyle S}$. Існує бієкція між множиною ${\displaystyle Q}$ і послідовністю Фарея порядку ${\displaystyle r}$, заданою відображенням вектора ${\displaystyle (q,p)}$ на дріб ${\displaystyle {\frac {p}{q}}}$.

Кола Форда

Порівняння кіл Форда і діаграми Фарея з круговими дугами для ${\displaystyle n}$ від 1 до 9. Кожна дуга перетинає відповідні кола під прямим кутом. На svg-рисунку наведіть вказівник на коло чи криву, щоб виділити їх або їх елементи.

Існує зв'язок між послідовністю Фарея і колами Форда.

Для кожного дробу ${\displaystyle {\frac {p}{q}}}$ (в його найменших термінах) існує коло Форда ${\displaystyle C\left[{\frac {p}{q}}\right]}$ з радіусом ${\displaystyle {\frac {1}{2q^{2}}}}$ і центром у точці ${\displaystyle \left({\frac {p}{q}},{\frac {1}{2q^{2}}}\right)}$. Два кола Форда для різних дробів або не перетинаються, або дотикаються ― кола Форда ніколи не перетинаються. Якщо ${\displaystyle 0<{\frac {p}{q}}<1}$, то кола Форда, які дотичні до кола ${\displaystyle C\left[{\frac {p}{q}}\right]}$ є колами Форда для дробів, які є сусідами дробу ${\displaystyle {\frac {p}{q}}}$ в деякій послідовності Фарея. Таким чином, коло ${\displaystyle C\left[{\frac {2}{5}}\right]}$ є дотичним до кіл ${\displaystyle C\left[{\frac {1}{2}}\right]}$, ${\displaystyle C\left[{\frac {1}{3}}\right]}$, ${\displaystyle C\left[{\frac {3}{7}}\right]}$, ${\displaystyle C\left[{\frac {3}{8}}\right]}$ тощо.

Сітка Аполлонія ${\displaystyle (0,0,1,1)}$ і резонансна діаграма Фарея.

Кола Форда з'являються також у сітці Аполлонія ${\displaystyle (0,0,1,1)}$. Рисунок нижче ілюструє це разом з резонансними лініями послідовності Фарея.[18]

Гіпотеза Рімана

Послідовності Фарея використовуються в двох формулюваннях гіпотези Рімана. Нехай ${\displaystyle F_{n}}$ є ${\displaystyle \{{a_{k,n}\colon \ k=0,1,\ldots ,m_{n}}\}.}$ Визначити ${\displaystyle d_{k,n}=a_{k,n}-{\frac {k}{m_{n}}},}$ іншими словами ${\displaystyle d_{k,n}}$ ― різниця між ${\displaystyle k}$-м членом ${\displaystyle n}$-ї послідовності Фарея і ${\displaystyle k}$-м членом множини з тією ж кількістю точок, розміщених на однаковій відстані одна від одної на одиничному інтервалі. У 1924 році Жером Франель^[en][19] довів, що твердження

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

еквівалентне гіпотезі Рімана, а потім Едмунд Ландау[20] зауважив (відразу після статті Франеля), що твердження

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

також еквівалентне гіпотезі Рімана.

Інші суми з дробами Фарея

Сума всіх дробів послідовності Фарея порядку ${\displaystyle n}$ дорівнює половині кількості елементів цієї послідовності:

${\displaystyle \sum _{r\in F_{n}}r={\frac {1}{2}}|F_{n}|.}$

Сума знаменників у послідовності Фарея в два рази перевищує суму чисельників і може бути представлена функцією Ейлера:

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

Цю гіпотезу висунув Гарольд Л. Аарон у 1962 році, а довів Джин А. Блейк у 1966 році. Доведення в один рядок гіпотези Гарольда Л. Аарона таке. Сума чисельників дорівнює:

${\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).}$

Відношення першої суми до другої дорівнює ${\displaystyle {\frac {1}{2}}}$.

Нехай ${\displaystyle b_{j}}$ — впорядковані знаменники послідовності ${\displaystyle F_{n}}$, тоді[21]

${\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.}$

Нехай ${\displaystyle {\frac {a_{j}}{b_{j}}}}$ — ${\displaystyle j}$-й дріб послідовності Фарея ${\displaystyle F_{n}}$, тоді

${\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,}$

як показано в роботі Галла і Шіу[22]. Також, згідно з цією роботою, член всередині суми можна представити багатьма різними способами:

${\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 ,}$

отримуючи таким чином багато різних сум за елементами послідовності Фарея з однаковим результатом. Використовуючи симетрію відносно ${\displaystyle {\frac {1}{2}}}$, суму можна обмежити половиною послідовності:

${\displaystyle \sum _{j=1}^{|F_{n}|/2}a_{j-1}b_{j+1}-a_{j+1}b_{j-1}=3(|F_{n}|-1)/2-n-\lceil n/2\rceil .}$

Функцію Мертенса можна подати як суму дробів послідовності Фарея в такий спосіб:

${\displaystyle M(n)=-1+\sum _{a\in {\mathcal {F}}_{n}}{\rm {e}}^{2\pi {\rm {i}}a},}$

де ${\displaystyle {\mathcal {F}}_{n}}$ ― послідовність Фарея порядку ${\displaystyle n}$. Ця формула використовується в доведенні теореми Франеля ― Ландау[23].

Наступний член

Існує надзвичайно простий алгоритм для обчислення дробів у послідовності Фарея ${\displaystyle F_{n}}$ в традиційному порядку (зростання) або нетрадиційному порядку (спадання). Алгоритм обчислює кожен наступний елемент, враховуючи попередні два і застосовуючи до них властивість медіанти. Якщо ${\displaystyle {\frac {a}{b}}}$ і ${\displaystyle {\frac {c}{d}}}$ — два відомі елементи, і ${\displaystyle {\frac {p}{q}}}$ ― невідомий наступний елемент, то ${\displaystyle {\frac {c}{d}}={\frac {a+p}{b+q}}}$. Оскільки ${\displaystyle {\frac {c}{d}}}$ нескоротний дріб, то існує ціле число ${\displaystyle k}$ таке, що ${\displaystyle kc=a+p}$ і ${\displaystyle kd=b+q}$, а тому ${\displaystyle p=kc-a}$ і ${\displaystyle q=kd-b}$. Якщо розглядати ${\displaystyle p}$ і ${\displaystyle q}$ як функції від ${\displaystyle k}$, то

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

тому чим більше беремо ${\displaystyle k}$, тим ближче ${\displaystyle {\frac {p}{q}}}$ розташовується до ${\displaystyle {\frac {c}{d}}}$.

Щоб знайти наступний дріб у послідовності Фарея, ${\displaystyle k}$ має бути якомога більшим, враховуючи що ${\displaystyle kd-b\leq n}$ (оскільки розглядаємо лише числа зі знаменниками не більше ${\displaystyle n}$), то ${\displaystyle k}$ ― найбільше ціле число, ${\displaystyle k\leq {\frac {n+b}{d}}}$. Підставляючи це значення ${\displaystyle k}$ у співвідношення для ${\displaystyle p}$ і ${\displaystyle q}$ отримуємо:

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

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

Цей алгоритм можна реалізувати мовою Python так:

def farey_sequence(n: int, descending: bool = False) -> None:
    """Print the n'th Farey sequence. Allow for either ascending or descending."""
    (a, b, c, d) = (0, 1, 1, n)
    if descending:
        (a, c) = (1, n - 1)
    print("{0}/{1}".format(a, b))
    while (c <= n and not descending) or (a > 0 and descending):
        k = (n + b) // d
        (a, b, c, d) = (c, d, k * c - a, k * d - b)
        print("{0}/{1}".format(a, b))

Для прямого знаходження розв'язків діофантових рівнянь у раціональних числах часто можна використовувати ряди Фарея (для знаходження лише зведених форм). Рядки з позначкою ${\displaystyle (*)}$ також можна змінити, щоб включити будь-які два суміжних члени для отримання членів лише більших (або менших) ніж заданий член[24].

Див. також

• Дерево Штерна — Броко
• Шаблон ABACABA^[en]
• Функція Ейлера

Примітки

1. «Послідовність усіх нескоротних дробів зі знаменниками, що не перевищують ${\displaystyle n}$, записаних у порядку зростання, називається послідовністю Фарея порядку ${\displaystyle n}$». З коментарем: «Це означення послідовностей Фарея здається найзручнішим. Однак деякі автори вважають за краще обмежувати дроби інтервалом від 0 до 1.» — Нівен і Цукерман (1972).
2. Guthery, Scott B. (2011). «1. The Mediant». A Motif of Mathematics: History and Application of the Mediant and the Farey Sequence. Boston: Docent Press. p. 7. ISBN 978-1-4538-1057-6. OCLC 1031694495. Retrieved 28 September 2020.
3. Hardy, G.H.; Wright, E.M. (1979). An Introduction to the Theory of Numbers (вид. Fifth). Oxford University Press. Chapter III. ISBN 0-19-853171-0.
4. Beiler, Albert H. (1964). Recreations in the Theory of Numbers (вид. Second). Dover. Chapter XVI. ISBN 0-486-21096-0. Cited in Farey Series, A Story. Cut-the-Knot.
5. Beiler, Albert H. (1964). Recreations in the Theory of Numbers (Second ed.). Dover. Chapter XVI. ISBN 0-486-21096-0. Cited in «Farey Series, A Story». Cut-the-Knot.
6. Sloane, N. J. A. (ed.). «Sequence A005728». The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
7. Tomas, Rogelio (January 2022). «Partial Franel sums» (PDF). Journal of Integer Sequences. 25(1).
8. Austin, David (December 2008). «Trees, Teeth, and Time: The mathematics of clock making». American Mathematical Society. Rhode Island. Archived from the original on 4 February 2020. Retrieved 28 September 2020.
9. Martin, Greg (2009). «A product of Gamma function values at fractions with the same denominator». arXiv:0907.4384 [math.CA].
10. Wehmeier, Stefan (2009). «The ${\displaystyle {\rm {LCM}}(1,2,\dots ,n)}$ as a product of sine values sampled over the points in Farey sequences». arXiv:0909.1838 [math.CA].
11. Tomas Garcia, Rogelio (August 2020). «Equalities between greatest common divisors involving three coprime pairs» (PDF). Notes on Number Theory and Discrete Mathematics. 26 (3). doi:10.7546/nntdm.2020.26.3.5-7.
12. Tomas, Rogelio (January 2022). «Partial Franel sums» (PDF). Journal of Integer Sequences. 25 (1).
13. «Farey Approximation». NRICH.maths.org. Archived from the original on 19 November 2018. Retrieved 18 November 2018.
14. Eliahou, Shalom (August 1993). «The ${\displaystyle 3x+1}$ problem: new lower bounds on nontrivial cycle lengths». Discrete Mathematics. 118 (1–3): 45–56. doi:10.1016/0012-365X(93)90052-U.
15. Zhenhua Li, A.; Harter, W.G. (2015). «Quantum Revivals of Morse Oscillators and Farey-Ford Geometry». Chem. Phys. Lett. 633: 208—213. arXiv:1308.4470. doi:10.1016/j.cplett.2015.05.035. S2CID 66213897.
16. Tomas, R. (2014). «From Farey sequences to resonance diagrams». Physical Review Special Topics — Accelerators and Beams. 17: 014001. doi:10.1103/PhysRevSTAB.17.014001.
17. Harabor, Daniel Damir; Grastien, Alban; Öz, Dindar; Aksakalli, Vural (26 May 2016). «Optimal Any-Angle Pathfinding In Practice». Journal of Artificial Intelligence Research. 56: 89–118. doi:10.1613/jair.5007.
18. Tomas, Rogelio (2020). «Imperfections and corrections». arXiv:2006.10661 [physics].
19. Franel, Jérôme (1924). «Les suites de Farey et le problème des nombres premiers». Nachrichten von der Gesellschaft der Wissenschaften zu Göttingen. Mathematisch-Physikalische Klasse (in French): 198—201.
20. Landau, Edmund (1924). «Bemerkungen zu der vorstehenden Abhandlung von Herrn Franel». Nachrichten von der Gesellschaft der Wissenschaften zu Göttingen. Mathematisch-Physikalische Klasse (in German): 202—206.
21. Kurt Girstmair; Girstmair, Kurt (2010). «Farey Sums and Dedekind Sums». The American Mathematical Monthly. 117 (1): 72-78. doi:10.4169/000298910X475005. JSTOR 10.4169/000298910X475005. S2CID 31933470.
22. Hall, R. R.; Shiu, P. (2003). «The Index of a Farey Sequence». Michigan Math. J. 51 (1): 209—223. doi:10.1307/mmj/1049832901.
23. Edwards, Harold M. (1974). «12.2 Miscellany. The Riemann Hypothesis and Farey Series». In Smith, Paul A.; Ellenberg, Samuel (eds.). Riemann's Zeta Function. Pure and Applied Mathematics. New York: Academic Press. pp.~263--267. ISBN 978-0-08-087373-2. OCLC 316553016. Retrieved 30 September 2020.
24. Routledge, Norman (March 2008). «Computing Farey series». The Mathematical Gazette. Vol.~92, no. 523. pp. 55-62.

Джерела

1. Математическая энциклопедия. В пяти томах. Том 5./ Под ред. И. М. Виноградова. М.: Советская энциклопедия, 1984, с. 598

Література

• Hatcher, Allen. Topology of Numbers. Mathematics. Ithaca, NY: Cornell U.
• Graham, Ronald L.; Knuth, Donald E.; Patashnik, Oren (1989). Concrete Mathematics: A foundation for computer science (вид. 2nd). Boston, MA: Addison-Wesley. с. 115—123, 133—139, 150, 462—463, 523—524. ISBN 0-201-55802-5. — in particular, see § 4.5 (pp. 115–123), Bonus Problem 4.61 (pp. 150, 523—524), § 4.9 (pp. 133–139), § 9.3, Problem 9.3.6 (pp. 462–463).
• Vepstas, Linas. The Minkowski Question Mark, GL(2,Z), and the Modular Group (PDF). — reviews the isomorphisms of the Stern-Brocot Tree.
• Vepstas, Linas. Symmetries of Period-Doubling Maps (PDF). — reviews connections between Farey Fractions and Fractals.
• Cobeli, Cristian; Zaharescu, Alexandru (2003). The Haros-Farey sequence at two hundred years. A survey. Acta Univ. Apulensis Math. Inform. (5): 1—38. pp. 1–20 (PDF). Acta Univ. Apulensis. pp. 21–38 (PDF). Acta Univ. Apulensis.
• Matveev, Andrey O. (2017). Farey Sequences: Duality and Maps Between Subsequences. Berlin, DE: De Gruyter. ISBN 978-3-11-054662-0.

Посилання

• Bogomolny, Alexander. Farey series. Cut-the-Knot.
• Bogomolny, Alexander. Stern-Brocot Tree. Cut-the-Knot.
• Pennestri, Ettore. A Brocot table of base 120.
• «Farey series», Encyclopedia of Mathematics, EMS Press, 2001 [1994]
• Weisstein, Eric W. Stern-Brocot Tree(англ.) на сайті Wolfram MathWorld.
• Число дробів у ряді Фарея порядку n — послідовність A005728 з Онлайн енциклопедії послідовностей цілих чисел, OEIS
• Чисельники ряду Фарея порядку n — послідовність A006842 з Онлайн енциклопедії послідовностей цілих чисел, OEIS
• Знаменники ряду Фарея порядку n — послідовність A006843 з Онлайн енциклопедії послідовностей цілих чисел, OEIS
• Archived at Ghostarchive and the Wayback Machine: Bonahon, Francis. Funny Fractions and Ford Circles (video). Brady Haran. Процитовано 9 червня 2015 — через YouTube.

Посилання

• Weisstein, Eric W. Послідовність Фарея(англ.) на сайті Wolfram MathWorld.