Дерево примитивных пифагорейских троек

В математике дерево примитивных пифагоровых троек — это дерево данных , в котором каждый узел разветвляется на три последующих узла, при этом бесконечное множество всех узлов дает все (и только) примитивные пифагоровые тройки без дублирования.

Пифагорова тройка — это набор из трех положительных целых чисел a, b и c, обладающих тем свойством, что они могут быть соответственно двумя катетами и гипотенузой прямоугольного треугольника , таким образом удовлетворяя уравнению ; тройка называется примитивной тогда и только тогда, когда наибольший общий делитель a , b и c равен единице. Примитивные пифагоровы тройки a, b и c также являются попарно взаимно простыми . Набор всех примитивных пифагоровских троек имеет структуру корневого дерева , в частности тернарного дерева , естественным образом. Это было впервые обнаружено Б. Берггреном в 1934 году. ^[1] $а^{2}+b^{2}=c^{2}$

FJM Barning показал ^[2] , что когда любая из трех матриц

{\begin{array}{lcr}A={\begin{bmatrix}1&-2&2\\2&-1&2\\2&-2&3\end{bmatrix}}&B={\begin{bmatrix}1&2&2\\2&1&2\\2&2&3\end{bmatrix}}&C={\begin{bmatrix}-1&2&2\\-2&1&2\\-2&2&3\end{bmatrix}}\end{array}}

умножается справа на вектор-столбец , компоненты которого образуют пифагорову тройку, тогда результатом является другой вектор-столбец, компоненты которого являются другой пифагоровой тройкой. Если исходная тройка является примитивной, то таковой является и та, которая получается. Таким образом, каждая примитивная пифагорова тройка имеет трех «потомков». Все примитивные пифагоровы тройки происходят таким образом от тройки (3, 4, 5), и ни одна примитивная тройка не появляется более одного раза. Результат может быть графически представлен в виде бесконечного тернарного дерева с (3, 4, 5) в корневом узле (см. классическое дерево справа). Это дерево также появилось в работах А. Холла в 1970 году ^[3] и А. Р. Канги в 1990 году. ^[4] В 2008 году В. Е. Фирстов показал, что в общем случае существуют только три таких дерева трихотомии, и явно дает дерево, похожее на дерево Берггрена, но начинающееся с начального узла (4, 3, 5). ^[5]

Доказательства

Наличие исключительно примитивных пифагорейских троек

Можно показать индуктивно, что дерево содержит только примитивные пифагоровы тройки и ничего больше, показав, что начиная с примитивной пифагоровы тройки, например, присутствующей в начальном узле с (3, 4, 5), каждая сгенерированная тройка является как пифагоровой, так и примитивной.

Сохранение пифагорейского имущества

Если любая из вышеприведенных матриц, скажем A , применяется к тройке ( a , b , c ) ^{T ,} имеющей пифагорейское свойство a ² + b ² = c ^{2 ,} чтобы получить новую тройку ( d , e , f ) ^T = A ( a , b , c ) ^T , эта новая тройка также является пифагорейской. Это можно увидеть, записав каждую из d , e , и f как сумму трех членов в a , b , и c , возведя каждую из них в квадрат и подставив c ² = a ² + b ^{2 ,} чтобы получить f ² = d ² + e ² . Это справедливо как для B и C , так и для A .

Сохранение первобытности

Матрицы A , B , и C все унимодулярны — то есть они имеют только целые элементы, и их определители равны ±1. Таким образом, их обратные матрицы также унимодулярны и, в частности, имеют только целые элементы. Так что если любая из них, например A , применяется к примитивной пифагорейской тройке ( a , b , c ) ^{T ,} чтобы получить другую тройку ( d , e , f ) ^T , мы имеем ( d , e , f ) ^T = A ( a , b , c ) ^T и, следовательно, ( a , b , c ) T = A −1 ⁽ d , ^e , f ) T . Если бы ^любой простой множитель был общим для любых двух из (и, следовательно, всех трех) d , e , и f , то по этому последнему уравнению этот простой множитель также делил бы каждый из a , b , и c . Итак, если a , b , и c на самом деле попарно взаимно просты, то d , e , и f также должны быть попарно взаимно простыми. Это справедливо для B и C , а также для A .

Присутствие каждой примитивной пифагорейской тройки ровно один раз

Чтобы показать, что дерево содержит каждую примитивную пифагорову тройку, но не более одного раза, достаточно показать, что для любой такой тройки существует ровно один путь обратно через дерево к начальному узлу (3, 4, 5). Это можно увидеть, применяя по очереди каждую из унимодулярных обратных матриц A ⁻¹ , B ⁻¹ и C ⁻¹ к произвольной примитивной пифагоровой тройке ( d , e , f ), отмечая, что по приведенным выше рассуждениям примитивность и свойство Пифагора сохраняются, и отмечая, что для любой тройки, большей, чем (3, 4, 5), ровно одна из обратных матриц перехода дает новую тройку со всеми положительными элементами (и меньшей гипотенузой). По индукции эта новая допустимая тройка сама по себе приводит ровно к одной меньшей допустимой тройке и так далее. В силу конечности числа все меньших и меньших потенциальных гипотенуз в конечном итоге достигается (3, 4, 5). Это доказывает, что ( d , e , f ) действительно встречается в дереве, поскольку до него можно добраться из (3, 4, 5), выполнив шаги в обратном порядке; и это происходит уникально, поскольку существует только один путь от ( d , e , f ) до (3, 4, 5).

Характеристики

Преобразование с использованием матрицы A , если оно выполняется повторно из ( a , b , c ) = (3, 4, 5), сохраняет признак b + 1 = c ; матрица B сохраняет a – b = ±1, начиная с (3, 4, 5); а матрица C сохраняет признак a + 2 = c, начиная с (3, 4, 5).

Геометрическая интерпретация этого дерева включает в себя вневписанные окружности , присутствующие в каждом узле. Три дочерних элемента любого родительского треугольника «наследуют» свои вписанные радиусы от родителя: радиусы вневписанных окружностей родителя становятся вписанными радиусами для следующего поколения. ^[6]^{: стр.7} Например, родительский элемент (3, 4, 5) имеет радиусы вневписанных окружностей, равные 2, 3 и 6. Это в точности радиусы вписанных окружностей трех дочерних элементов (5, 12, 13), (15, 8, 17) и (21, 20, 29) соответственно.

Если любой из A или C применяется повторно из любой пифагорейской тройки, используемой в качестве начального условия, то динамика любого из a , b и c может быть выражена как динамика x в

x_{n+3}-3x_{n+2}+3x_{n+1}-x_{n}=0\,

который построен на основе общего характеристического уравнения матриц

\lambda ^{3}-3\lambda ^{2}+3\lambda -1=0.\,

Если B применяется повторно, то динамика любого из a , b и c может быть выражена как динамика x в

x_{n+3}-5x_{n+2}-5x_{n+1}+x_{n}=0,\,

который построен по образцу характеристического уравнения B. ^[7]

Более того, бесконечное множество других одномерных разностных уравнений третьего порядка можно найти, умножая любые из трех матриц вместе произвольное число раз в произвольной последовательности. Например, матрица D = CB перемещает один из дерева на два узла (поперек, затем вниз) за один шаг; характеристическое уравнение D дает шаблон для динамики третьего порядка любого из a , b или c в неисчерпывающем дереве , образованном D.

Альтернативные методы генерации дерева

Использование двух параметров

Другой подход к динамике этого дерева ^[8] основан на стандартной формуле для генерации всех примитивных пифагорейских троек:

а=м^{2}-н^{2},\,

b=2mn,\,

с=м^{2}+н^{2},\,

с $m > n > 0$ и $m$ и $n$ взаимно просты и имеют противоположную четность (т.е. не оба нечетные). Пары $(m, n)$ можно итерировать, предварительно умножая их (выраженные как вектор-столбец) на любой из

{\begin{array}{lcr}{\begin{bmatrix}2&-1\\1&0\end{bmatrix}},&{\begin{bmatrix}2&1\\1&0\end{bmatrix}},&{\begin{bmatrix}1&2\\0&1\end{bmatrix}},\end{array}}

каждое из которых сохраняет неравенства, взаимную простоту и противоположную четность. Полученное троичное дерево, начинающееся с $(2, 1)$ , содержит каждую такую пару $(m, n) ровно один раз, и при преобразовании в тройки$ $(a, b, c)$ оно становится идентичным дереву, описанному выше.

В качестве альтернативы, начните с $(m, n) = (3, 1)$ для корневого узла. ^[9] Тогда умножение матриц сохранит неравенства и взаимность, и $m$ и $n$ останутся нечетными. Соответствующие примитивные пифагоровы тройки будут иметь $a = (m 2 - n 2) / 2$ , $b = mn$ и $c = (m 2 + n 2) / 2$ . Это дерево произведет те же примитивные пифагоровы тройки, хотя и с переставленными $a$ и $b .$

Использование одного параметра

Этот подход основан на стандартной формуле для генерации любой примитивной пифагоровой тройки из касательной к половинному углу. В частности, записывается $t = n / m = b / (a + c)$ , где $t$ — тангенс половины внутреннего угла, противолежащего стороне длины $b$ . Корневой узел дерева — $t = 1/2$ , что соответствует примитивной пифагоровой тройке $(3, 4, 5)$ . Для любого узла со значением $t$ его тремя дочерними элементами являются $1 / (2 - t)$ , $1 / (2 + t)$ и $t / (1 + 2 t)$ . Чтобы найти примитивную пифагорову тройку, связанную с любым таким значением $t$ , вычислите $(1 - t 2, 2 t, 1 + t 2)$ и умножьте все три значения на наименьшее общее кратное их знаменателей. (В качестве альтернативы запишите $t = n / m$ в виде дроби в наименьших числах и используйте формулы из предыдущего раздела.) Корневой узел, который вместо этого имеет значение $t = 1/3,$ даст то же самое дерево примитивных пифагорейских троек, хотя значения $a$ и $b$ поменяются местами.

Другое дерево

В качестве альтернативы можно также использовать 3 различные матрицы, найденные Прайсом. ^[6] Эти матрицы A', B', C' и соответствующие им линейные преобразования показаны ниже.

{\overset {{A}'}{\mathop {\left[{\begin{matrix}2&1&-1\\-2&2&2\\-2&1&3\end{matrix}}\right]} }}\left[{\begin{matrix}a\\b\\c\end{matrix}}\right]=\left[{\begin{matrix}a_{1}\\b_{1}\\c_{1}\end{matrix}}\right],\quad {\text{ }}{\overset {{B}'}{\mathop {\left[{\begin{matrix}2&1&1\\2&-2&2\\2&-1&3\end{matrix}}\right]} }}\left[{\begin{matrix}a\\b\\c\\\end{matrix}}\right]=\left[{\begin{matrix}a_{2}\\b_{2}\\c_{2}\end{matrix}}\right],\quad {\text{ }}{\overset {{C}'}{\mathop {\left[{\begin{matrix}2&-1&1\\2&2&2\\2&1&3\\\end{matrix}}\right]} }}\left[{\begin{matrix}a\\b\\c\\\end{matrix}}\right]=\left[{\begin{matrix}a_{3}\\b_{3}\\c_{3}\end{matrix}}\right]

Три линейных преобразования Прайса:

{\begin{aligned}&{\begin{matrix}+2a+b-c=a_{1}\quad &-2a+2b+2c=b_{1}\quad &-2a+b+3c=c_{1}&\quad \to \left[{\text{ }}a_{1},{\text{ }}b_{1},{\text{ }}c_{1}\right]\end{matrix}}\\&{\begin{matrix}+2a+b+c=a_{2}\quad &+2a-2b+2c=b_{2}\quad &+2a-b+3c=c_{2}&\quad \to \left[{\text{ }}a_{2},{\text{ }}b_{2},{\text{ }}c_{2}\right]\end{matrix}}\\&{\begin{matrix}+2a-b+c=a_{3}\quad &+2a+2b+2c=b_{3}\quad &+2a+b+3c=c_{3}&\quad \to \left[{\text{ }}a_{3},{\text{ }}b_{3},{\text{ }}c_{3}\right]\end{matrix}}\\&\end{aligned}}

Три дочерних элемента, созданных каждым из двух наборов матриц, не одинаковы, но каждый набор в отдельности создает все примитивные тройки.

Например, используя [5, 12, 13] в качестве родителя, мы получаем два набора из трех дочерних элементов:

{\begin{array}{ccc}&\left[5,12,13\right]&\\A&B&C\\\left[45,28,53\right]&\left[55,48,73\right]&\left[7,24,25\right]\end{array}}\quad \quad \quad \quad \quad \quad {\begin{array}{ccc}{}&\left[5,12,13\right]&{}\\A'&B'&C'\\\left[9,40,41\right]&\left[35,12,37\right]&\left[11,60,61\right]\end{array}}

Примечания и ссылки

^ Б. Берггрен, «Питагорейский треугольник» (на шведском языке), Elementa: Tidskrift for elementär matematik, fysik och kemi 17 (1934), 129–139. См. стр. 6 для дерева с корнями.
^ Барнинг, FJM (1963), «Пифагорические и биджна-пифагоресовые дриехокен и один процесс генерации с использованием унимодулирующих матриц» (на голландском языке), Math. Центр Амстердама Afd. Зуйвере Виск. ZW-011:37, https://ir.cwi.nl/pub/7151
↑ А. Холл, «Генеалогия пифагорейских триад», The Mathematical Gazette , том 54, номер 390, декабрь 1970 г., страницы 377–39.
↑ Канга, А.Р., «Родословное древо пифагорейских троек», Бюллетень Института математики и ее приложений 26, январь/февраль 1990 г., 15–17.
^ Фирстов, ВЕ (2008). "Специальная матричная полугруппа преобразований примитивных пар и генеалогия пифагорейских троек". Матем. Заметки . 84 (2): 281–299. doi : 10.4213/mzm4074 .
^ ab Price, H. Lee (2008). «Пифагорейское дерево: новый вид». arXiv : 0809.4324 [math.HO].
^ Митчелл, Дуглас В., «Обратная связь по 92.60», Mathematical Gazette 93, июль 2009 г., 358–9.
↑ Сондерс, Роберт А.; Рэндалл, Тревор (июль 1994 г.), «Повторное рассмотрение генеалогического древа пифагорейских триплетов», Mathematical Gazette , 78 : 190–193, doi : 10.2307/3618576, JSTOR 3618576, S2CID 125749577.
↑ Митчелл, Дуглас В., «Альтернативная характеристика всех примитивных пифагорейских троек», Mathematical Gazette 85, июль 2001 г., 273–275.

Внешние ссылки

Тринарное дерево(а), лежащее в основе примитивных пифагорейских троек в cut-the-knot
Фрэнк Р. Бернхарт и Х. Ли Прайс, «Повторное посещение сада Пифагора», Australian Senior Mathematics Journal 01/2012; 26(1):29-40.[1]
Вайсштейн, Эрик В. «Пифагорова тройка». MathWorld .