Träd av primitiva Pythagoras trippel

Berggrens träd av primitiva pythagoras trippel.

I matematik är ett träd av primitiva Pythagoras trippel ett dataträd där varje nod förgrenar sig till tre efterföljande noder med den oändliga uppsättningen av alla noder som ger alla (och endast) primitiva Pythagoras trippel utan duplicering.

En pytagoreisk trippel är en uppsättning av tre positiva heltal a, b och c som har egenskapen att de kan vara de två benen respektive hypotenusan i en rät triangel , och därmed uppfyller ekvationen $a^{2}+b^{2}=c^{2}$ ; trippeln sägs vara primitiv om och endast om den största gemensamma delaren av a, b och c är en. Primitiv Pythagoras trippel a, b och c är också parvis coprime . Uppsättningen av alla primitiva Pythagoras trippel har strukturen av ett rotat träd , närmare bestämt ett ternärt träd , på ett naturligt sätt. Detta upptäcktes första gången av B. Berggren 1934.

FJM Barning visade att när någon av de tre matriserna

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

multipliceras till höger med en kolumnvektor vars komponenter bildar en Pythagoras trippel, då blir resultatet en annan kolumnvektor vars komponenter är en annan Pythagoras trippel . Om den initiala trippeln är primitiv, så är den som blir resultatet också. Således har varje primitiv pythagoras trippel tre "barn". Alla primitiva pythagoras trippel härstammar på detta sätt från trippeln (3, 4, 5), och ingen primitiv trippel förekommer mer än en gång. Resultatet kan representeras grafiskt som ett oändligt ternärt träd med (3, 4, 5) vid rotnoden (se klassiskt träd till höger). Detta träd förekom också i tidningar från A. Hall 1970 och AR Kanga 1990. 2008 visade VE Firstov generellt att endast tre sådana trikotomiträd existerar och ger uttryckligen ett träd som liknar Berggrens men börjar med initial nod (4, 3, 5) ).

Bevis

Närvaro av exklusivt primitiva pytagoreiska trippel

Det kan visas induktivt att trädet innehåller primitiva pytagoreiska trippel och inget annat genom att visa att med utgångspunkt från en primitiv pythagoras trippel, som den som finns vid den initiala noden med (3, 4, 5), är varje genererad trippel både pytagoreisk och primitiv .

Bevarande av Pythagoras egendom

Om någon av ovanstående matriser, säg A , appliceras på en trippel ( a , b , c ) ^T som har den pytagoreiska egenskapen a ² + b ² = c ² för att erhålla en ny trippel ( d , e , f ) ^T = A ( a , b , c ) ^T , denna nya trippel är också pytagoreisk. Detta kan ses genom att skriva ut var och en av d , e , och f som summan av tre termer i a , b , och c , kvadrera var och en av dem och ersätta c ² = a ² + b ² för att få f ² = d ² + e ² . Detta gäller för B och C såväl som för A .

Bevarande av primitivitet

Matriserna A , B och C är alla unimodulära - det vill säga de har bara heltalsposter och deras determinanter är ±1. Sålunda är deras inverser också unimodulära och har i synnerhet endast heltalsposter. Så om någon av dem, till exempel A , tillämpas på en primitiv pytagoreisk trippel ( a , b , c ) ^T för att erhålla ytterligare en trippel ( d , e , f ) ^T , har vi ( d , e , f ) ^T = A ( a , b , c ) ^T och därmed ( a , b , c ) ^T = A ⁻¹ ( d , e , f ) ^T . Om någon primtalsfaktor delas av två av (och därmed alla tre av) d , e , och f så skulle det primtal också dividera var och en av a , b och c . Så om a , b och c faktiskt är parvisa coprime, då måste d , e och f också vara parvis coprime. Detta gäller för B och C såväl som för A .

Närvaro av varje primitiv Pythagoras trippel exakt en gång

För att visa att trädet innehåller varje primitiv pytagoreisk trippel, men inte mer än en gång, räcker det att visa att det för en sådan trippel finns exakt en väg tillbaka genom trädet till startnoden (3, 4, 5). Detta kan ses genom att i sin tur tillämpa var och en av de unimodulära inversa matriserna A ⁻¹ , B ⁻¹ , och C ⁻¹ på en godtycklig primitiv pytagoreisk trippel ( d , e , f ), och notera att med ovanstående resonemang primitivitet och pythagoras egenskaper behålls, och att notera att för varje trippel som är större än (3, 4, 5) ger exakt en av de inversa övergångsmatriserna en ny trippel med alla positiva poster (och en mindre hypotenusa). Genom induktion leder denna nya giltiga trippel i sig till exakt en mindre giltig trippel, och så vidare. Genom ändligheten av antalet mindre och mindre potentiella hypotenuser nås så småningom (3, 4, 5). Detta bevisar att ( d , e , f ) faktiskt förekommer i trädet, eftersom det kan nås från (3, 4, 5) genom att vända stegen; och det inträffar unikt eftersom det bara fanns en väg från ( d , e , f ) till (3, 4, 5).

Egenskaper

Transformationen med matris A , om den utförs upprepade gånger från ( a , b , c ) = (3, 4, 5), bevarar egenskapen b + 1 = c ; matris B bevarar a – b = ±1 från (3, 4, 5); och matris C bevarar egenskapen a + 2 = c med början från (3, 4, 5).

En geometrisk tolkning för detta träd involverar de cirklar som finns vid varje nod. De tre barnen i vilken föräldertriangel som helst "ärver" sina inradii från föräldern: förälderns cirkelradier blir inradii för nästa generation. Till exempel, förälder (3, 4, 5) har cirkelradier lika med 2, 3 och 6. Dessa är just inradierna för de tre barnen (5, 12, 13), (15, 8, 17) och (21 , 20, 29) respektive.

Om endera av A eller C appliceras upprepade gånger från vilken pythagoras trippel som helst som används som ett initialt villkor, då kan dynamiken för vilken som helst av a , b och c uttryckas som dynamiken för x i

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

som är mönstrad på matrisernas gemensamma karakteristiska ekvation

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

Om B appliceras upprepade gånger kan dynamiken för vilken som helst av a , b och c uttryckas som dynamiken för x i

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

som är mönstrad på den karakteristiska ekvationen för B .

differensekvationer av tredje ordningen hittas genom att multiplicera vilken som helst av de tre matriserna ett godtyckligt antal gånger i en godtycklig sekvens. Till exempel, matrisen D = CB flyttar en ut genom trädet med två noder (tvärs över, sedan ner) i ett enda steg; den karakteristiska ekvationen för D tillhandahåller mönstret för tredje ordningens dynamik för någon av a , b eller c i det icke uttömmande trädet som bildas av D .

Alternativa metoder för att generera trädet

Prices träd av primitiva Pythagoras trippel.

Ett annat tillvägagångssätt för dynamiken i detta träd förlitar sig på standardformeln för att generera alla primitiva Pythagoras trippel:

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

$b=2mn,\,$

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

med m > n > 0 och m och n coprime och av motsatt paritet. Par ( m , n ) kan itereras genom att förmultiplicera dem (uttryckt som en kolumnvektor) med någon av

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

var och en bevarar ojämlikheterna, coprimeness och motsatt paritet. Det resulterande ternära trädet, som börjar vid (2,1), innehåller varje sådant ( m , n ) par exakt en gång, och när det omvandlas till ( a , b , c ) trippel blir det identiskt med trädet som beskrivs ovan.

Ett annat sätt att använda två underliggande parametrar för att generera trippelträdet använder en alternativ formel för alla primitiva trippel:

$a=uv,\,$

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

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

med u > v > 0 och u och v coprime och båda udda . Par ( u , v ) kan itereras genom att förmultiplicera dem (uttryckt som en kolumnvektor) med någon av ovanstående 2 × 2 matriser, som alla tre bevarar olikheterna, coprimeness och den udda pariteten för båda elementen. När denna process påbörjas vid (3, 1), innehåller det resulterande ternära trädet varje sådant ( u , v ) par exakt en gång, och när det omvandlas till ( a , b , c ) trippel blir det identiskt med trädet som beskrivs ovan.

Ett annat träd

Alternativt kan man också använda 3 olika matriser hittade av Price. Dessa matriser A', B', C' och deras motsvarande linjära transformationer visas nedan.

${\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{matris}}\höger]} }}\vänster[{\begin{matrix}a\\b\\c\\\end{matris}}\höger]=\vänster[{\ börja{matris}a_{3}\\b_{3}\\c_{3}\slut{matris}}\höger]$

Prices tre linjära transformationer är

${\begin{aligned}&{\begin{matrix}+2a +bc=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{matris}}\\&\end{aligned}}$

De 3 barnen som produceras av var och en av de två uppsättningarna av matriser är inte desamma, men varje uppsättning separat producerar alla primitiva trippel.

Om vi ​​till exempel använder [5, 12, 13] som förälder får vi två uppsättningar med tre barn:

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

externa länkar

• Trinärträdet/träden som ligger bakom primitiva Pythagoras trippel vid klippa-knuten
• Frank R. Bernhart och H. Lee Price, "Pythagoras trädgård, återbesökt", Australian Senior Mathematics Journal 01/2012; 26(1):29-40. [1]
• Weisstein, Eric W. "Pythagorean Triple" . MathWorld .