In der Mathematik ist der Baum primitiver pythagoreischer Tripel ein Datenbaum, in dem jeder Knoten zu drei nachfolgenden Knoten verzweigt, wobei die unendliche Menge aller Knoten alle (und nur die) primitiven pythagoreischen Tripel ohne Duplikate ergibt.

Ein pythagoreisches Tripel ist eine Menge von drei positiven ganzen Zahlen a, b und c mit der Eigenschaft, dass sie jeweils die Seitenlängen eines rechtwinkligen Dreiecks sein können, wodurch die Gleichung ${\displaystyle a^{2}+b^{2}=c^{2}}$ erfüllt wird. Das Tripel gilt genau dann als primitiv, wenn der größte gemeinsame Teiler von a, b und c eins ist. Primitive pythagoreische Tripel (a, b, c) sind sogar paarweise teilerfremd. Die Menge aller primitiven pythagoreischen Tripel hat auf natürliche Weise die Struktur eines Wurzelbaums, insbesondere eines ternären Baums. Dies wurde erstmals 1934 von B. Berggren entdeckt.

F. J. M. Barning zeigte Folgendes: Wenn eine der folgenden Matrizen

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

rechts mit einem Spaltenvektor, dessen Komponenten ein pythagoreisches Tripel bilden, multipliziert wird, dann ist das Ergebnis ein weiterer Spaltenvektor, dessen Komponenten ein anderes pythagoreisches Tripel bilden. Wenn das anfängliche Tripel primitiv ist, ist auch das so errechnete Tripel primitiv. Somit hat jedes primitive pythagoreische Tripel drei „Kinder“. Alle primitiven pythagoreischen Tripel stammen auf diese Weise vom Tripel (3, 4, 5) ab, und kein primitives Tripel erscheint mehr als einmal. Das Ergebnis kann grafisch als unendlicher ternärer Baum mit (3, 4, 5) als Wurzelknoten dargestellt werden (siehe klassischer Baum rechts). Dieser Baum erschien auch in Papieren von A. Hall im Jahr 1970 und A. R. Kanga im Jahr 1990. Im Jahr 2008 zeigte V. E. Firstov allgemein, dass nur drei solcher Bäume existieren und explizit einen Baum ähnlich dem von Berggren ergeben, jedoch beginnend mit dem Anfangsknoten (4, 3, 5).

Beweise

Eigenschaften

Die Transformation unter Verwendung der Matrix A, wenn sie wiederholt von (a, b, c) = (3, 4, 5) durchgeführt wird, bewahrt das Merkmal ${\displaystyle b+1=c}$; die Matrix B bewahrt ${\displaystyle |a-b|=1}$; und die Matrix C bewahrt die Beziehung ${\displaystyle a+2=c}$.

Eine geometrische Interpretation für diesen Baum beinhaltet die an jedem Knoten vorhandenen Ankreise. Die drei Kinder eines Elterndreiecks „erben“ ihren Inkreisradius vom Elterndreieck: Die Ankreisradien des Elternteils werden zu den Inkreisradien für die nächste Generation. Zum Beispiel hat das Elterndreieck (3, 4, 5) die Ankreisradien 2, 3 und 6. Dies sind genau die Inkreisradien der drei Kinder (5, 12, 13), (15, 8, 17) und (21, 20, 29).

Wird A oder C wiederholt auf ein pythagoreisches Tripel angewendet, dann kann die Dynamik von a, b und c als die Dynamik von x in folgender Gleichung ausgedrückt werden

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

die strukturell den charakteristischen Polynomen der Matrizen A und C gleicht:

${\displaystyle \lambda ^{3}-3\lambda ^{2}+3\lambda -1=0}$

Wird B wiederholt auf ein pythagoreisches Tripel angewendet, entspricht die Dynamik von a, b und c der Dynamik von x wie folgt

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

was strukturell dem charakteristischen Polynom von B gleicht.

Darüber hinaus kann eine Unendlichkeit von Differenzengleichungen 3. Ordnung gefunden werden, indem die drei Matrizen beliebig oft in einer beliebigen Reihenfolge miteinander multipliziert werden. Zum Beispiel bewegt die Matrix D = CB einen Knoten im Baum um zwei Positionen (quer, dann runter) in einem einzigen Schritt. Das charakteristische Polynom von D liefert das Muster für die Dynamik 3. Ordnung von a, b oder c in dem durch D gebildeten Baum.

Alternative Methoden zum Generieren des Baums

Ein anderer Ansatz zur Dynamik dieses Baums beruht auf der Standardformel zur Erzeugung aller primitiven pythagoreischen Tripel:

${\displaystyle a=m^{2}-n^{2},}$

${\displaystyle b=2mn,}$

${\displaystyle c=m^{2}+n^{2},}$

mit m > n > 0 und m und n teilerfremd und unterschiedlicher Parität. Paare (m, n) können iteriert werden, indem eine der folgenden Matrizen mit dem Vorgängerpaar als Spaltenvektor multipliziert wird.

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

Jede der Multiplikationen bewahrt die obige Ungleichung, die Teilerfremdheit und die entgegengesetzte Parität. Der resultierende ternäre Baum – beginnend bei (2,1) – enthält jedes solche (m, n)-Paar genau einmal, und wenn es in (a, b, c) konvertiert wird, entsteht exakt der oben beschriebenen Baum.

Eine andere Möglichkeit – mit zwei zugrunde liegenden Parametern zum Generieren des Dreifachbaums – verwendet eine alternative Formel für alle primitiven Tripel:

${\displaystyle a=uv,}$

${\displaystyle b={\frac {u^{2}-v^{2}}{2}},}$

${\displaystyle c={\frac {u^{2}+v^{2}}{2}},}$

mit u > v > 0 und u und v teilerfremd und beide ungerade. Paare (u, v) können iteriert werden, indem eine der obigen (2 × 2)-Matrizen mit dem Vorgängerpaar als Spaltenvektor multipliziert wird. Jede der Multiplikationen bewahrt die obige Ungleichung, die Teilerfremdheit und dass beide Terme ungerade sind. Wenn dieser Prozess bei (3, 1) begonnen wird, enthält der resultierende ternäre Baum jedes solche (u, v)-Paar genau einmal, und wenn es in (a, b, c) konvertiert wird, entsteht ebenso der oben beschriebenen Baum.

Ein anderer Baum

Alternativ kann man auch drei andere Matrizen verwenden, die von Price gefunden wurden. Diese Matrizen A', B', C' lauten:

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

Ihre entsprechenden linearen Transformationen sind:

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

Die drei Kinder, die von jedem der beiden Sätze von Matrizen (Berggren und Price) erzeugt werden, sind nicht gleich, aber jeder Satz erzeugt separat alle primitiven Tripel. Wenn man beispielsweise (5, 12, 13) als Eltern-Tripel verwendet, erhält man zwei Sätze mit je drei Kindern:

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

Einzelnachweise

1. ↑ B. Berggren, Pytagoreiska trianglar (auf Schwedisch), Elementa: Tidskrift för elementär matematik, fysik och kemi 17 (1934), 129–139. Siehe Seite 6 für den Wurzelbaum.
2. ↑ Barning, F. J. M. (1963), Over pythagorese en bijna-pythagorese driehoeken en een generatieproces met behulp van unimodulaire matrices (auf Niederländisch), Math. Centrum Amsterdam Afd. Zuivere Wisk. ZW-011: 37, ir.cwi.nl.
3. ↑ A. Hall, Genealogy of Pythagorean Triads, The Mathematical Gazette, volume 54, number 390, December, 1970, pages 377–9.
4. ↑ Kanga, A. R., The family tree of Pythagorean triples, Bulletin of the Institute of Mathematics and its Applications 26, January/February 1990, 15–17.
5. ↑ V. E. Firstov, A Special Matrix Transformation Semigroup of Primitive Pairs and the Genealogy of Pythagorean Triples, Mathematical Notes, volume 84, number 2, August 2008, pages 263–279, Russian; mathnet.ru.
6. 1 2 H. Lee Price: The Pythagorean Tree: A New Species. 25. September 2008, S. 7; abgerufen im 1. Januar 1 (englisch). 
7. ↑ Mitchell, Douglas W., Feedback on 92.60, Mathematical Gazette 93, July 2009, 358–9.
8. ↑ Robert A. Saunders: The family tree of the Pythagorean triplets revisited. In: Mathematical Gazette. Band 78, Juli 1994, S. 190–193, JSTOR:3618576. 
9. ↑ Mitchell, Douglas W., An alternative characterisation of all primitive Pythagorean triples, Mathematical Gazette 85, July 2001, 273–275.