Дерево Штерн–Броко

В теории чисел дерево Штерна –Броко представляет собой бесконечное полное двоичное дерево , в котором вершины однозначно соответствуют положительным рациональным числам , значения которых упорядочены слева направо, как в двоичном дереве поиска .

Дерево Штерна–Броко было введено независимо Морицем Штерном  (1858) и Ахиллом Броко  (1861). Штерн был немецким теоретиком чисел; Броко был французским часовщиком , который использовал дерево Штерна–Броко для проектирования систем зубчатых передач с передаточным отношением, близким к некоторому желаемому значению, путем нахождения отношения гладких чисел вблизи этого значения.

Корень дерева Штерна–Броко соответствует числу 1. Отношение родитель-потомок между числами в дереве Штерна–Броко может быть определено в терминах простых непрерывных дробей или медиан , а путь в дереве от корня до любого другого числа q обеспечивает последовательность приближений к q с меньшими знаменателями , чем q . Поскольку дерево содержит каждое положительное рациональное число ровно один раз, поиск в ширину дерева обеспечивает метод перечисления всех положительных рациональных чисел, который тесно связан с последовательностями Фарея . Левое поддерево дерева Штерна–Броко, содержащее рациональные числа в диапазоне (0,1) , называется деревом Фарея .

Каждая вершина в дереве может быть связана с тройкой дробей, состоящей из трех дробей в той же строке, что и вершина, а именно дроби непосредственно слева от вершины, дроби в самой вершине и дроби непосредственно справа от вершины. (См. рисунок выше.) Левая и правая дроби не соответствуют вершинам в той же строке, что и вершина, а скорее вершинам в некоторой предыдущей строке. Каждая такая дробь может пониматься как обозначение области плоскости, ограниченной двумя бесконечными путями, спускающимися из предыдущей вершины, обозначенной той же дробью. Второй элемент тройки всегда будет медианой первого и третьего элементов. Например, корень связан с и его левые и правые потомки связаны с и${\displaystyle {\bigl (}{\tfrac {0}{1}},{\tfrac {1}{1}},{\tfrac {1}{0}}{\bigr )}}$${\displaystyle {\bigl (}{\tfrac {0}{1}},{\tfrac {1}{2}},{\tfrac {1}{1}}{\bigr )}}$${\displaystyle {\bigl (}{\tfrac {1}{1}},{\tfrac {2}{1}},{\tfrac {1}{0}}{\bigr )}.}$

Дерево генерируется по следующему правилу: $${\displaystyle {\begin{array}{ccccc}&&\left({\dfrac {a}{b}},{\dfrac {c}{d}},{\dfrac {e}{f}}\right)&&\\&\swarrow &&\searrow &\\\left({\dfrac {a}{b}},{\dfrac {a+c}{b+d}},{\dfrac {c}{d}}\right)&&&&\left({\dfrac {c}{d}},{\dfrac {c+e}{d+f}},{\dfrac {e}{f}}\right)\end{array}}}$$

Связь между родителями и потомками также можно понять в терминах непрерывных дробей. Каждое положительное рациональное число q может быть выражено как непрерывная дробь вида , где k и a ₀ являются неотрицательными целыми числами, а каждый последующий коэффициент a _i является положительным целым числом. Это представление не является уникальным, поскольку, но использование этой эквивалентности для замены каждой непрерывной дроби, заканчивающейся на единицу, более короткой непрерывной дробью показывает, что каждое рациональное число имеет уникальное представление, в котором последний коэффициент больше единицы. Тогда, если только q = 1 , число q имеет родителя в дереве Штерна–Броко, заданном выражением непрерывной дроби Эквивалентно этот родитель образуется путем уменьшения знаменателя в самом внутреннем члене непрерывной дроби на 1 и сокращения с предыдущим членом, если дробь становится ⁠$${\displaystyle q=a_{0}+{\cfrac {1}{a_{1}+{\cfrac {1}{a_{2}+{\cfrac {1}{a_{3}+{\cfrac {1}{\ddots +{\cfrac {1}{a_{k}}}}}}}}}}}=[a_{0};a_{1},a_{2},\ldots ,a_{k}]}$$$${\displaystyle [a_{0};a_{1},a_{2},\ldots ,a_{k-1},1]=[a_{0};a_{1},a_{2},\ldots ,a_{k-1}+1],}$$$${\displaystyle [a_{0};a_{1},a_{2},\ldots ,a_{k}-1].}$$1/1⁠ . Например, рациональное число ⁠23/16⁠ имеет представление в виде непрерывной дроби , поэтому ее родителем в дереве Штерна–Броко является число $${\displaystyle {\frac {23}{16}}=1+{\cfrac {1}{2+{\cfrac {1}{3+{\frac {1}{2}}}}}}=[ 1;2,3,2],}$$$${\displaystyle [1;2,3,1]=[1;2,4]=1+{\cfrac {1}{2+{\frac {1}{4}}}}={\frac {13 {9}}.}$$

Наоборот, каждое число q в дереве Штерна–Броко имеет ровно двух потомков: если то один потомок — это число, представленное непрерывной дробью , а другой потомок представлен непрерывной дробью Один из этих потомков меньше q , и это левый потомок; другой больше q , и это правый потомок (фактически первое выражение дает левого потомка, если k нечетное, и правого потомка, если k четное). Например, представление непрерывной дроби ⁠$${\displaystyle q=[a_{0};a_{1},a_{2},\ldots ,a_{k}]=[a_{0};a_{1},a_{2},\ldots ,a_{k}-1,1]}$$$${\displaystyle \displaystyle [a_{0};a_{1},a_{2},\ldots ,a_{k}+1]}$$$${\displaystyle [a_{0};a_{1},a_{2},\ldots ,a_{k}-1,2].}$$13/9⁠ — это [1;2,4] , а его два потомка — это [1;2,5] = ⁠16/11⁠ (правый потомок) и [1;2,3,2] = ⁠23/16⁠ (левый ребенок).

Ясно, что для каждого конечного выражения цепной дроби можно многократно перейти к его родителю и достичь корня [1;] = ⁠1/1⁠ дерева за конечное число шагов (точнее, за a ₀ + ... + a _k − 1 шагов). Следовательно, каждое положительное рациональное число появляется в этом дереве ровно один раз. Более того, все потомки левого потомка любого числа q меньше q , а все потомки правого потомка q больше q . Числа на глубине d в дереве — это числа, для которых сумма коэффициентов цепной дроби равна d + 1 .

Дерево Штерна–Броко образует бесконечное двоичное дерево поиска относительно обычного порядка рациональных чисел. ^{[1] [2]} Множество рациональных чисел, нисходящих от узла q, определяется открытым интервалом ( L _q , H _q ) , где L _q — предок q , который меньше q и ближайший к нему в дереве (или L _q = 0 , если q не имеет меньшего предка), а H _q — предок q , который больше q и ближайший к нему в дереве (или H _q = +∞ , если q не имеет большего предка).

Путь от корня 1 до числа q в дереве Штерна–Броко может быть найден с помощью алгоритма бинарного поиска , который может быть выражен простым способом с использованием медиантов . Увеличьте неотрицательные рациональные числа, включив значение ⁠1/0⁠ (представляющее +∞), которое по определению больше всех других рациональных чисел. Алгоритм бинарного поиска работает следующим образом:

• Инициализируем два значения L и H для ⁠0/1⁠ и ⁠1/0⁠ , соответственно.
• Пока q не будет найдено, повторяйте следующие шаги:
  • Пусть L = ⁠а/б⁠ и Н = ⁠с/г⁠ ; вычислить медиану${\displaystyle M=L\oplus H={\frac {a+c}{b+d}}.}$
  • Если M меньше q , то q находится в открытом интервале ( M , H ) ; замените L на M и продолжайте.
  • Если M больше q , то q находится в открытом интервале ( L , M ) ; замените H на M и продолжайте.
  • В оставшемся случае q = M ; завершить алгоритм поиска.

Последовательность значений M, вычисленная этим поиском, — это в точности последовательность значений на пути от корня к q в дереве Штерна–Броко. Каждый открытый интервал ( L , H ) , встречающийся на некотором шаге поиска, — это интервал ( L _M , H _M ), представляющий потомков медианы M . Родитель q в дереве Штерна–Броко — это последняя найденная медиана, которая не равна q .

Эту процедуру бинарного поиска можно использовать для преобразования чисел с плавающей точкой в ​​рациональные числа. Останавливаясь после достижения желаемой точности, числа с плавающей точкой можно аппроксимировать до произвольной точности. ^[3] Если действительное число x аппроксимируется любым рациональным числом ⁠а/б⁠ которая не входит в последовательность медиан, найденную с помощью вышеприведенного алгоритма, то последовательность медиан содержит более близкое приближение к x , знаменатель которого не превышает b ; в этом смысле эти медианы образуют наилучшие рациональные приближения к x .

Дерево Штерна–Броко может быть определено непосредственно в терминах медиан: левый потомок любого числа q является медианой q с его ближайшим меньшим предком, а правый потомок q является медианой q с его ближайшим большим предком. В этой формуле q и его предок должны быть взяты в наименьших терминах, и если нет меньшего или большего предка, то ⁠0/1⁠ или ⁠1/0⁠ следует использовать соответственно. Опять же, используя ⁠7/5⁠ в качестве примера, его ближайший меньший предок — ⁠4/3⁠ , поэтому его левый потомок — ⁠4 + 7/3 + 5⁠ = ⁠11/8⁠ , а его ближайший более крупный предок — ⁠3/2⁠ , поэтому его правый потомок — ⁠7 + 3/5 + 2⁠ = ⁠10/7⁠ .

Последовательность Фарея порядка n — это отсортированная последовательность дробей в замкнутом интервале [0,1] , знаменатель которых меньше или равен n . Как и в методе бинарного поиска для генерации дерева Штерна–Броко, последовательности Фарея могут быть построены с использованием медиан: последовательность Фарея порядка n + 1 формируется из последовательности Фарея порядка n путем вычисления медианы каждого из двух последовательных значений в последовательности Фарея порядка n , сохраняя подмножество медиан, знаменатель которых точно равен n + 1 , и помещая эти медианы между двумя значениями, из которых они были вычислены.

Аналогичный процесс вставки медианта, начинающийся с другой пары конечных точек интервала, можно также рассматривать для описания построения вершин на каждом уровне дерева Штерна–Броко. Последовательность Штерна–Броко порядка 0 является последовательностью , а последовательность Штерна–Броко порядка i является последовательностью, образованной вставкой медианта между каждой последовательной парой значений в последовательности Штерна–Броко порядка i − 1. Последовательность Штерна–Броко порядка i состоит из всех значений на первых i уровнях дерева Штерна–Броко вместе с граничными значениями ⁠${\displaystyle {\bigl [}{\tfrac {0}{1}},{\tfrac {1}{0}}{\bigr ]},}$${\displaystyle {\bigl [}{\tfrac {0}{1}},{\tfrac {1}{0}}{\bigr ]},}$0/1⁠ и ⁠1/0⁠ , в порядке возрастания номеров.

Таким образом, последовательности Штерна–Броко отличаются от последовательностей Фарея двумя способами: они в конечном итоге включают все положительные рациональные числа, а не только рациональные числа в интервале [0,1] , и на n -м шаге включаются все медианты, а не только те, знаменатель которых равен n . Последовательность Фарея порядка n может быть найдена путем симметричного обхода левого поддерева дерева Штерна–Броко, возвращаясь назад всякий раз, когда достигается число со знаменателем, большим n .

Если все рациональные числа находятся на одинаковой глубине дерева Штерна–Броко, то${\displaystyle {\tfrac {p_{1}}{q_{1}}},{\tfrac {p_{2}}{q_{2}}},\dots ,{\tfrac {p_{n}}{q_{n}}}}$

$${\displaystyle \sum _{k=1}^{n}{\frac {1}{p_{k}q_{k}}}=1.}$$

Более того, если имеются две последовательные дроби на определенном уровне дерева или выше (в том смысле, что любая дробь между ними должна находиться на более низком уровне дерева), то ^[4]${\displaystyle {\tfrac {p}{q}}<{\tfrac {p'}{q'}}}$

$${\displaystyle p'q-pq'=1.}$$

Наряду с определениями в терминах непрерывных дробей и медиан, описанными выше, дерево Штерна–Броко может быть также определено как декартово дерево для рациональных чисел, упорядоченных по их знаменателям. Другими словами, это уникальное двоичное дерево поиска рациональных чисел, в котором родительский элемент любой вершины q имеет меньший знаменатель, чем q (или если q и его родительский элемент оба являются целыми числами, в котором родительский элемент меньше, чем q ). Из теории декартовых деревьев следует, что наименьшим общим предком любых двух чисел q и r в дереве Штерна–Броко является рациональное число в замкнутом интервале [ q , r ] , которое имеет наименьший знаменатель среди всех чисел в этом интервале.

Перестановка вершин на каждом уровне дерева Стерна–Броко с помощью перестановки битов дает другое дерево, дерево Калкина–Вильфа , в котором потомки каждого числа ⁠а/б⁠ — это два числа ⁠а/а + б⁠ и ⁠а + б/б⁠ . Как и дерево Стерна–Броко, дерево Калкина–Вильфа содержит каждое положительное рациональное число ровно один раз, но оно не является бинарным деревом поиска.

• Функция вопросительного знака Минковского , определение которой для рациональных аргументов тесно связано с деревом Штерна–Броко
• Дерево Калкина–Вильфа
• Код для генерации деревьев Штерна-Броко

• Броко, Ашиль (1861), «Расчет румян по аппроксимации, новый метод», Revue Chronométrique , 3 : 186–194 ..
• Броко, Ахилл (1862), «Расчет румян по номинальной аппроксимации, новый метод», https://gallica.bnf.fr/ark:/12148/bpt6k1661912?rk=21459;2
• Стерн, Мориц А. (1858), «Ueber eine zahlentheoretische Funktion», Journal für die reine und angewandte Mathematik , 55 : 193–220 ..
• Berstel, Jean; Lauve, Aaron; Reutenauer, Christophe; Saliola, Franco V. (2009), Комбинаторика слов. Слова Кристоффеля и повторения в словах , CRM Monograph Series, т. 27, Providence, RI: American Mathematical Society , ISBN 978-0-8218-4480-9, ЗБЛ  1161.68043

• Айылам, Дхрува (2013), Модифицированные последовательности Штерна-Броко , arXiv : 1301.6807 , Bibcode : 2013arXiv1301.6807A
• Остин, Дэвид, Деревья, зубы и время: математика создания часов, тематическая колонка от AMS
• Богомольный, Александр , Stern Brocot-Tree, cut-the-knot , получено 2008-09-03.
• Слоан, NJA , Дерево Стерна–Броко или Фэри, Онлайновая энциклопедия целочисленных последовательностей.
• Вильдбергер, Норман, MF96: Дроби и дерево Штерна-Броко.
• Вайсштейн, Эрик В. , «Дерево Штерна–Броко», MathWorld
• Дерево Стерна–Броко на PlanetMath .
• Бесконечные дроби, Numberphile
• Удивительные графики III, Numberphile
• Последовательность OEIS A002487 (Двухатомная серия Штерна (или последовательность Штерна-Броко))