Arborele Stern-Brocot

În matematică , arborele Stern-Brocot este o reprezentare a tuturor raționalelor strict pozitive, sub formă de fracțiuni ireductibile .

A fost descoperită aproape simultan de matematicianul german Moritz Stern (1858) și de ceasornicarul francez Achille Brocot (1861).

Constructie

Arborele Stern-Brocot este un arbore binar infinit ai cărui noduri sunt etichetate prin fracțiuni ireductibile. Este construit prin recurență, un etaj după altul.

Etajul 1 conține doar rădăcina arborelui, purtând fracția 1/1.

Etapa p +1 a arborelui este construită după cum urmează: enumerăm toate fracțiile subarborelui finit corespunzător etapei p , citite de la stânga la dreapta. Inserăm fracția 0/1 în partea de sus a listei și 1/0 la sfârșitul listei, obținând astfel o listă de 2 fracții p +1 (vezi imaginea). În această listă, una din două fracții aparține stadiului p , una din patru stadiului p - 1 și așa mai departe.

Cu fiecare fracție aparținând stadiului p , îi asociem cele două fiice ale nivelului p + 1 obținute făcând mediana cu fiecare dintre cei doi vecini din listă: mediana fracțiilor și este fracția . ${\ frac mn}$ ${\ frac {m '} {n'}}$ ${\ frac {m + m '} {n + n'}}$

Exemplu: primele etape ale copacului

Iată listele cu fracțiile conținute în copac după construirea fiecăreia dintre primele 4 etape (prezentate și în desen) la care am adăugat 0/1 mai întâi, 1/0 ultima. Pe fiecare etaj, fracțiile adăugate la acel etaj au fost colorate în roșu, celelalte fiind cele de la etajele anterioare.

${\ displaystyle {\ begin {array} {lccccccccccccccccc} {\ text {Etaj 1:}} & {\ frac {0} {1}} &&&&&&&&&& {\ color {red} {\ frac {1} {1}}} &&&&&&&&& {\ frac {1} {0}} \\ {\ text {Etajul 2:}} & {\ frac {0} {1}} &&&& {\ color {red} {\ frac {1} {2}} } &&&& {\ frac {1} {1}} &&&&& \ \ color {red} {\ frac {2} {1}}} &&&& {\ frac {1} {0}} \\ {\ text {Etajul 3: }} & {\ frac {0} {1}} && {\ color {red} {\ frac {1} {3}}} && {\ frac {1} {2}} && {\ color {red} { \ frac {2} {3}}} && {\ frac {1} {1}} && {\ color {red} {\ frac {3} {2}}} && {\ frac {2} {1}} && {\ color {red} {\ frac {3} {1}}} && {\ frac {1} {0}} \\ {\ text {Etajul 4:}} & {\ frac {0} {1} } & {\ color {red} {\ frac {1} {4}}} & {\ frac {1} {3}} & {\ color {red} {\ frac {2} {5}}} și { \ frac {1} {2}} & {\ color {red} {\ frac {3} {5}}} & {\ frac {2} {3}} & {\ color {red} {\ frac {3 } {4}}} & {\ frac {1} {1}} & {\ color {red} {\ frac {4} {3}}} & {\ frac {3} {2}} & {\ color {red} {\ frac {5} {3}}} & {\ frac {2} {1}} & {\ color {red} {\ frac {5} {2}}} și {\ frac {3} {1}} și {\ color {red} {\ frac {4} {1}}} și {\ frac {1} {0}} \ end {array}}}$

Proprietăți elementare: legătură cu apartamentele Farey

Arborele Stern-Brocot este strâns legat de suitele Farey . Amintiți-vă că două fracții ireductibile m / n și m ' / n' sunt aproape de Farey daca avem :

{\ displaystyle m'n-mn '= 1}

În acest caz, verificăm (vezi mai jos) dacă mediana lor este aproape de Farey, în dreapta primului, în stânga celui de-al doilea. În special, aceasta are consecința că m / n <( m + m ' ) / ( n + n' ) < m ' / n' ; deducem că, în fiecare etapă p a arborelui Stern-Brocot, lista asociată a celor 2 fracțiuni p +1 care apar în subarborele este ordonată de la cea mai mică la cea mai mare și că două fracții consecutive din această listă sunt vecine cu Farey. Această ultimă proprietate implică, de asemenea, că toate fracțiile care apar în copac sunt ireductibile.

Rețineți că ramura stângă a arborelui conține toate fracțiile unitare , în timp ce ramura dreaptă conține toate numerele întregi scrise ca fracții cu un numitor egal cu 1.

La fiecare nivel, numitorii fracțiilor de pe lista aferentă formează secvența diatomică Stern .

Arborele Stern-Brocot și algoritmul lui Euclid

Arborele Stern-Brocot, la fel ca secvențele Farey, este, de asemenea, legat de algoritmul lui Euclid ; acest lucru face posibilă, având o fracțiune m / n , să se calculeze calea care duce de la rădăcină la aceasta din urmă.

Pentru aceasta, folosim teorema Bachet-Bézout : dacă presupunem că m / n este ireductibil, adică m și n sunt coprimă, atunci există două numere întregi m ' și n' astfel încât m'n - mn ' = 1 (sau mn '- m'n = 1); dacă, în plus, presupunem că m și n sunt distincte și ambele nu sunt zero, atunci putem alege m ' și n' astfel încât 0 ≤ m '≤ m și 0 ≤ n' ≤ n (coeficienții m ' și n' satisfacând toate acestea constrângerile sunt calculate direct de algoritmul euclidian extins ). În acest caz, așa cum am văzut mai sus, fracțiile m ' / n' și m / n sunt apropiate de Farey .

Apoi setăm m '' = m - m ' și n' '= n - n' ; dacă m'n - mn ' = 1 atunci mn' '- m''n = 1, altfel mn' - m'n = 1 și, prin urmare, m''n - mn '' = 1. Mai mult, m / n este mediana fracțiune de m ' / n' și m '' / n '' din care deducem m ' / n' < m / n < m '' n '' dacă mn '- m'n = 1, sau m' ' / n '' < m / n < m ' / n' si m'n - mn ' = 1. În arborele Stern-Brocot, fracția m / n este fiica celei din cele două fracții m' / n ' și m '' / n '' care are cel mai mare numitor, deoarece acesta este cel care se află la etajul inferior și stabilim dacă este fata stângă sau dreaptă în funcție de semnul lui m'n - mn ' .

De exemplu, dacă luăm în considerare fracția 2/5, atunci algoritmul lui Euclid ne dă -2 × 2 + 1 × 5 = 1. Deducem că 1/2 și (2 - 1) / (5 - 2) = 1/3 sunt vecinii de 2/5 din secvența Farey de ordinul 5; deoarece 1/3 are cel mai mare numitor, este mama a 2/5; în plus, ecuația -2 × 2 + 1 × 5 = 1 implică faptul că 1/2> 2/5, deci 1/3 <2/5, din care deducem că 2/5 este fiica dreaptă a 1/3.

Iterând argumentul de mai sus, putem arăta prin inducție că producem o secvență finită de fracții de la fiică la mamă, adică o cale în arbore care urcă de la fracția inițială la rădăcină. În special, aceasta oferă o dovadă a existenței fiecărei fracții ireductibile din copac.

Enumerarea raționalelor

Proprietatea fundamentală a arborelui Stern-Brocot este că acesta conține toate fracțiile ireductibile strict pozitive o singură dată. Deducem un proces pentru numerotarea tuturor raționalelor pozitive, adică o bijecție a raționalelor pozitive pe numerele naturale pozitive. Pe scurt, asociem cu un rațional întregul a cărui reprezentare în baza 2 codifică calea de la rădăcina arborelui la raționalul ales.

Având o fracțiune, asociem cu aceasta o secvență de 0 și 1 reprezentând calea de la rădăcina arborelui și care duce la acesta. Prin urmare, definim doi „pași”: pasul 0 (stânga) și pasul 1 (dreapta) (în cartea citată în referință, acestea sunt notate L pentru stânga și R pentru dreapta ). De exemplu calea care duce la fracțiunea 2/5 este reprezentată de următorul (0, 0, 1): de la rădăcină coborâți de două ori spre stânga apoi o dată spre dreapta. Pentru a simplifica, vom indica acum secvențele lui 0 și 1 ca cuvinte binare , de exemplu secvența (0, 0, 1) va fi reprezentată de cuvântul binar 001.

Ideea este acum de a citi cuvântul binar asociat cu o fracție ca reprezentare de bază 2 a unui întreg. Cu toate acestea, deoarece mai multe cuvinte binare pot reprezenta același număr întreg (de exemplu cuvintele 1, 01, 001, ..., toate reprezintă numărul întreg 1) vom prefixa mai întâi reprezentarea căii cu un 1. Dacă luăm l exemplu din raționalul 2/5, calea sa este reprezentată de cuvântul 001, care atunci când este prefixat cu 1 devine 1001, care se arată ca reprezentarea din baza 2 a întregului 9. În mod similar, raționalul 3/5 este asociat cu întregul , raționalul 5/2 cu etc. Astfel, atribuim un număr unic fiecărui număr întreg rațional și reciproc, scris în baza 2, poate fi interpretat ca o cale în arborele care duce la un rațional. ${\ displaystyle (1010) _ {2} = 10}$ ${\ displaystyle (1110) _ {2} = 14}$

Demonstrații

Ireductibilitatea fiecărei fracții

Arătăm că fiecare fracție care apare în copac este ireductibilă prin inducție .

Amintim că lista asociată cu etajul p al arborelui Stern-Brocot este lista fracțiilor conținute în subarborele de înălțime p , citit de la stânga la dreapta, la care adăugăm 0/1 în cap și coada 1/0 . Vom arăta formal proprietatea menționată mai sus: două fracții consecutive în listă sunt aproape de Farey. ${\ displaystyle 2 ^ {p + 1} -1}$

Inițializare : pe etapa 0, este evident: avem 1,1 - 0,0 = 1.

Moștenire : Să presupunem prin inducție proprietatea verificată în etapa p .

Prin construcție, noile fracțiuni care apar în etapa p + 1 sunt mediane (m + m ') / (n + n') unde m / n și m '/ n' sunt consecutive în lista asociată cu etapa p ; prin ipoteză de inducție avem m'n - mn '= 1 . Ar trebui să se vadă că fracțiile m / n , (m + m ') / (n + n') și m '/ n' care sunt consecutive în lista asociată cu stadiul p + 1 sunt apropiate de Farey care se deduce din următoarele calcule:

$(m + m ') nm (n + n') = m'n-mn '= 1,$

$m '(n + n') - (m + m ') n' = m'n-mn '= 1.$

Astfel, toate perechile m / n și m '/ n' ale fracțiilor consecutive din lista asociată cu etapa p + 1 verifică m'n - mn '= 1 care este o relație Bézout din care deducem în special că m și n sunt coprimă, astfel încât m / n (precum și m '/ n' ) este ireductibil.

Unicitate

Vrem să arătăm că fiecare fracție strict pozitivă apare cel mult o dată în copac. Aceasta este o consecință a faptului că în fiecare etapă lista asociată este strict în creștere, ceea ce în sine este o consecință a faptului demonstrat mai sus că fracțiile consecutive din lista asociată cu etapa p sunt apropiate de Farey; într-adevăr m'n - mn '= 1 implică în special că m' / n '- m / n = 1 / nn'> 0 deci că m / n <m '/ n' .

Existenţă

Am văzut deja folosind algoritmul lui Euclid că orice fracțiune ireductibilă apare în copac. O altă demonstrație este dată aici.

Luați în considerare o fracție ireductibilă notată a / b . Vom construi patru apartamente de numere întregi , , și prin inducție p : ${\ displaystyle (m_ {p})}$ ${\ displaystyle (n_ {p})}$ ${\ displaystyle (m '_ {p})}$ ${\ displaystyle (n '_ {p})}$

Pentru p = 0 am stabilit , , și . ${\ displaystyle m_ {0} = 0}$ ${\ displaystyle n_ {0} = 1}$ ${\ displaystyle m '_ {0} = 1}$ ${\ displaystyle n '_ {0} = 0}$

În pasul p sunt disponibile trei cazuri:

${\ displaystyle {\ frac {m_ {p} + m '_ {p}} {n_ {p} + n' _ {p}}} = {\ frac {a} {b}}}$ : punem apoi și . ${\ displaystyle m_ {p + 1} = m '_ {p + 1} = a}$ ${\ displaystyle n_ {p + 1} = n '_ {p + 1} = b}$
${\ displaystyle {\ frac {m_ {p} + m '_ {p}} {n_ {p} + n' _ {p}}} <{\ frac {a} {b}}}$ : pozăm ; ; și . ${\ displaystyle m_ {p + 1} = m_ {p} + m '_ {p}}$ ${\ displaystyle n_ {p + 1} = n_ {p} + n '_ {p}}$ ${\ displaystyle m '_ {p + 1} = m' _ {p}}$ ${\ displaystyle n '_ {p + 1} = n' _ {p}}$
${\ frac {m + m '} {n + n'}}> {\ frac ab}$ : pozăm ; ; și . ${\ displaystyle m_ {p + 1} = m_ {p}}$ ${\ displaystyle n_ {p + 1} = n_ {p}}$ ${\ displaystyle m '_ {p + 1} = m_ {p} + m' _ {p}}$ ${\ displaystyle n '_ {p + 1} = n_ {p} + n' _ {p}}$

Această definiție are mai multe consecințe care pot fi ușor verificate prin recurență:

cele patru secventa de numere întregi , , și sunt în creștere (dar nu strict în creștere). ${\ displaystyle (m_ {p})}$ ${\ displaystyle (n_ {p})}$ ${\ displaystyle (m '_ {p})}$ ${\ displaystyle (n '_ {p})}$

pentru toate p, dacă fracțiile și sunt diferite, atunci avem , sunt consecutive în lista asociată cu etapa p , deci în special aproape de Farey, ceea ce implică în special că sunt ireductibile. În plus, unul dintre cele două aparține stadiului p și, prin urmare, mediana lor aparține stadiului p + 1 . De fapt, în lista asociată cu stadiul p, o fracție din două aparține stadiului p , în consecință mediana a două fracții consecutive aparține stadiului p + 1 . ${\ displaystyle m_ {p} / n_ {p}}$ ${\ displaystyle m '_ {p} / n' _ {p}}$ ${\ displaystyle m_ {p} / n_ {p} <a / b <m '_ {p} / n' _ {p}}$

pentru toate p dacă fracțiile și sunt egale atunci ambele sunt egale cu a / b și așa este și pentru toate . ${\ displaystyle m_ {p} / n_ {p}}$ ${\ displaystyle m '_ {p} / n' _ {p}}$ ${\ displaystyle m_ {q} / n_ {q}}$ ${\ displaystyle m '_ {q} / n' _ {q}}$ ${\ displaystyle q \ geq p}$

Vrem să arătăm că există un p astfel încât ; dacă un astfel de p există atunci presupunând că este cel mai mic, există și, din moment ce mediana aparține etapei p + 1, aceasta arată că s-a găsit în copac. ${\ displaystyle a / b = m_ {p + 1} / n_ {p + 1} = m '_ {p + 1} / n' _ {p + 1}}$ ${\ displaystyle a / b = (m_ {p} + m '_ {p}) / (n_ {p} + n' _ {p})}$ $a / b$

După cum avem și așa cum este întreg deducem . La fel din noi deducem . Înmulțind aceste inegalități, respectiv, și obținem: . ${\ displaystyle a / b> m_ {p} / n_ {p}}$ ${\ displaystyle an_ {p} -bm_ {p}> 0}$ ${\ displaystyle an_ {p} -bm_ {p}}$ ${\ displaystyle an_ {p} -bm_ {p} \ geq 1}$ ${\ displaystyle a / b <m '_ {p} / n' _ {p}}$ ${\ displaystyle bm '_ {p} -an' _ {p} \ geq 1}$ ${\ displaystyle m '_ {p} + n' _ {p}}$ ${\ displaystyle m_ {p} + n_ {p}}$ ${\ displaystyle (m '_ {p} + n' _ {p}) (an_ {p} -bm_ {p}) + (m_ {p} + n_ {p}) (bm '_ {p} -an '_ {p}) \ geq m' _ {p} + n '_ {p} + m_ {p} + n_ {p}}$

Cu toate acestea, folosind faptul că și suntem vecini cu Farey, avem: ${\ displaystyle m_ {p} / n_ {p}}$ ${\ displaystyle m '_ {p} / n' _ {p}}$

{\ displaystyle {\ begin {align} (m '_ {p} + n' _ {p}) (an_ {p} -bm_ {p}) + (m_ {p} + n_ {p}) (bm ' _ {p} -an '_ {p}) & = am' _ {p} n_ {p} + an_ {p} n '_ {p} -bm_ {p} m' _ {p} -bm_ {p } n '_ {p} + bm_ {p} m' _ {p} + bm '_ {p} n_ {p} -am_ {p} n' _ {p} -an_ {p} n '_ {p } \\ & = a (m '_ {p} n_ {p} -m_ {p} n' _ {p}) + b (m '_ {p} n_ {p} -m_ {p} n'_ {p}) \\ & = a + b \ end {align}}}

De aceea în cele din urmă: . ${\ displaystyle a + b \ geq m '_ {p} + n' _ {p} + m_ {p} + n_ {p}}$

Prin urmare, succesiunea numerelor întregi este mărginită de . Prin urmare, nu poate fi strict în creștere, dar este în creștere, deoarece este suma a patru secvențe în creștere, deci există un rang p de la care este staționar. Dar atunci trebuie să avem altfel și, prin definiție, cel puțin unul (posibil ambele) dintre sau dintre ar fi egal cu mediana, astfel încât suma să fie strict mai mare decât , contrazicând staționaritatea secvenței de la p . ${\ displaystyle (m '_ {p} + n' _ {p} + m_ {p} + n_ {p})}$ $a + b$ ${\ displaystyle m_ {p} / n_ {p} = m '_ {p} / n' _ {p} = a / b}$ ${\ displaystyle m_ {p} / n_ {p} <a / b <m '_ {p} / n' _ {p}}$ ${\ displaystyle m_ {p + 1} / n_ {p + 1}}$ ${\ displaystyle m '_ {p + 1} / n' _ {p + 1}}$ ${\ displaystyle (m_ {p} + m_ {p + 1}) / (n_ {p} + n_ {p + 1})}$ ${\ displaystyle m_ {p + 1} + m '_ {p + 1} + n_ {p + 1} + n' _ {p + 1}}$ ${\ displaystyle m_ {p} + m '_ {p} + n_ {p} + n' _ {p}}$

Comparație cu algoritmul lui Euclid

Algoritmul lui Euclid face posibilă arătarea prezenței unei fracțiuni în copac începând de la acesta și prin diviziuni euclidiene succesive care urcă spre rădăcină, construind astfel o cale care urcă de la fracție la rădăcină. Demonstrația de mai sus se desfășoară în cealaltă direcție: pornind de la rădăcină producem o serie de fracții care se termină în cele din urmă pe cea dată inițial, producând o cale care coboară de la rădăcină la ea. Rețineți că același algoritm aplicat unui număr real mai degrabă decât unei fracțiuni face posibilă construirea ramurii infinite a fracțiilor care aproximează acest real.

Fracții continuate

Orice fracție admite o expansiune continuă a fracției finite ai cărei coeficienți sunt coeficienții succesivi calculați de algoritmul lui Euclid . Același algoritm euclidian care face posibilă găsirea căii care duce de la rădăcina arborelui Stern-Brocot la o fracție dată, putem deduce că expansiunea într-o fracție continuă codifică această cale. Tocmai dacă $[ q 1 ; q 2 , ..., q p , 1] = [ q 1 ; q 2 , ..., q p + 1]$ este expansiunea continuă a fracției fracției $m / n$ , cele două fiice ale $m / n$ din arborele Stern-Brocot au expansiunea continuă a fracției:

$[ q 1 ; q 2 , ..., q p + 1, 1] = [ q 1 ; q 2 , ..., q p + 2]$ ,
$[ q 1 ; q 2 , ..., q p , 1, 1] = [ q 1 ; q 2 , ..., q p , 2]$ .

Deducem prin inducție că fracția $m / n$ apare la etapa $q 1 + ... + q n$ și că secvența $( q 1 + ... + q n )$ descrie calea care duce la ea de la rădăcina $1/1$ : coborâți $q 1$ pas spre dreapta, apoi $q 2$ pași spre stânga etc. până la $q p$ pas la stânga dacă $p$ este par, la dreapta dacă $p$ este impar.

Cu alte cuvinte, calea care duce la fracția de expansiune $[ q 1 ; q 2 , ..., q p , 1]$ este codificat de cuvântul $1 q 1 0 q 2 ... ε q p$ unde $ε$ este simbolul $0$ dacă $p$ este par, $1$ dacă $p$ este impar.

De exemplu, expansiunea continuă a fracției de 2/5 este $[0; 2, 1, 1] = [0; 2, 2]$ care corespunde căii $001$ : 0 pași la dreapta, apoi 2 pași la stânga, apoi un pas la dreapta. De asemenea, putem calcula că expansiunea continuă a fracției de 17/12 este $[1; 2, 2, 2] = [1; 2, 2, 1, 1] în$ timp ce calea din copac care duce la 17/12 este reprezentată de cuvântul $100110$ .

Demonstrație

Apel Să înălțimea de numărul . Presupunem prin inducție că orice fracțiune de înălțime mai mică sau egală cu apare la etaj în arborele Stern-Brocot. Observăm în primul rând că cele două presupuse fiice ale lui sunt înalte și, pe măsură ce apar la etaj (mama lor este la etaj ), am demonstrat bine prin inducție egalitatea dintre înălțimea și podeaua copacului. $m / n$ ${\ displaystyle N = q_ {1} + \ cdots + q_ {p}}$ $NU$ $NU$ $m / n$ $N + 1$ $N + 1$ $NU$

Rămâne de arătat că aceste două fracții sunt într-adevăr fiicele . Pentru aceasta îi vom găsi pe cei doi vecini din lista asociată etajului . $m / n$ $m / n$ $NU$

Să începem cu două memento-uri preliminare. Printre proprietățile cartierelor Farey există în special faptul că atunci când și sunt vecini cu Farey, atunci orice fracție situată strict între cele două este obținută prin iterarea operației mediane din și , prin urmare, apare în mod necesar la un nivel mai ridicat atât în Stern- Arborele brocot. $a / b$ $a '/ b'$ ${\ displaystyle a '' / b ''}$ $a / b$ $a '/ b'$

Pe de altă parte , în cazul în care este o fracțiune a continuat, sa redus pentru sunt date de recurența: ${\ displaystyle [q_ {1}; q_ {2}, \ dots, q_ {p}]}$ ${\ displaystyle m_ {k} / n_ {k} = [q_ {1}; q_ {2}, ..., q_ {k}]}$ ${\ displaystyle k = 1, \ dots, p}$

${\ displaystyle m _ {- 1} = 0}$ , , , ; ${\ displaystyle m_ {0} = 1}$ ${\ displaystyle n _ {- 1} = 1}$ ${\ displaystyle n_ {0} = 0}$
${\ displaystyle m_ {k + 1} = m_ {k} q_ {k + 1} + m_ {k-1}}$ , . ${\ displaystyle n_ {k + 1} = n_ {k} q_ {k + 1} + n_ {k-1}}$

În special, deoarece avem ${\ displaystyle m / n = [q_ {1}, \ dots, q_ {p} +1]}$

{\ displaystyle {\ frac {m} {n}} = {\ frac {m_ {p-1} (q_ {p} +1) + m_ {p-2}} {n_ {p-1} (q_ { p} +1) + n_ {p-2}}} = {\ frac {m_ {p-1} q_ {p} + m_ {p-2} + m_ {p-1}} {n_ {p-1 } q_ {p} + n_ {p-2} + n_ {p-1}}} = {\ frac {m_ {p} + m_ {p-1}} {n_ {p} + n_ {p-1} }}}

Luați în considerare fracția continuată . Acesta este un vecin al lui Farey's . Într-adevăr, putem face următorul calcul: ${\ displaystyle m '/ n' = [q_ {1}, \ dots, q_ {n-1}] = m_ {p-1} / n_ {p-1}}$ $m / n$

{\ displaystyle {\ begin {align} m_ {k + 1} n_ {k} -m_ {k} n_ {k + 1} & = (m_ {k} q_ {k + 1} + m_ {k-1} ) n_ {k} -m_ {k} (n_ {k} q_ {k + 1} + n_ {k-1}) \\ & = - (m_ {k} n_ {k-1} -m_ {k- 1} n_ {k}) \ end {align}}}

din care deducem prin inducție că și deci acel și sunt apropiați de Farey for . Cu alte cuvinte, reducerile a două fracții continuate a căror prima este un prefix al celei de-a doua și a căror lungimi diferă de 1 sunt apropiate de Farey. Prin urmare și sunt vecini cu Farey. Sau este înălțime în timp ce este înălțime , prin ipoteză de inducție este la etaj , deci ambele sunt în lista asociată cu povestea și, prin urmare, sunt consecutive în ea. ${\ displaystyle m_ {k + 1} n_ {k} -m_ {k} n_ {k + 1} = (- 1) ^ {k + 1}}$ ${\ displaystyle m_ {k} / n_ {k} = [q_ {1}, \ dots, q_ {k}]}$ ${\ displaystyle m_ {k + 1} / n_ {k + 1} = [q_ {1}, \ dots, q_ {k + 1}]}$ ${\ displaystyle k = 1, \ dots, p}$ ${\ displaystyle m / n = [q_ {1}, \ dots, q_ {p} +1]}$ ${\ displaystyle m '/ n' = [q_ {1}, \ dots, q_ {p-1}]}$ $m / n$ $NU$ $m '/ n'$ ${\ displaystyle N '= q_ {1} + \ cdots q_ {p-1} -1 <N}$ $m '/ n'$ $NU'$ $NU$

Deducem că una dintre cele două fete de la etaj este mediana lor: $m / n$ $N + 1$

{\ displaystyle {\ begin {align} {\ frac {m + m '} {n + n'}} & = {\ frac {m_ {p-1} (q_ {p} +1) + m_ {p- 2} + m_ {p-1}} {n_ {p-1} (q_ {p} +1) + n_ {p-2} + n_ {p-1}}} \\ & = {\ frac {m_ {p-1} (q_ {p} +2) + m_ {p-2}} {n_ {p-1} (q_ {p} +2) + n_ {p-2}}} \ end {align} }}

care este reducerea fracției continue așa cum era de așteptat. ${\ displaystyle [q_ {1}, \ dots, q_ {p} +2]}$

Acum ia în considerare fracția . Deci avem: ${\ displaystyle m '' / n '' = [q_ {1}, \ dots, q_ {p}] = m_ {p} / n_ {p}}$

{\ displaystyle {\ begin {align} m''n-mn '' & = m_ {p} (n_ {p} + n_ {p-1}) - (m_ {p} + m_ {p-1}) n_ {p} \\ & = m_ {p} n_ {p-1} -m_ {p-1} n_ {p} \\ & = (- 1) ^ {p} \ end {align}}}

astfel încât din nou și sunt vecini cu Farey. Dar este înălțime , prin inducție, este la etaj , prin urmare este aproape în lista asociată cu podeaua . Prin urmare, cealaltă fiică a lor este mediana lor: $m "/ n"$ $m / n$ $m "/ n"$ ${\ displaystyle N '' = q_ {1} + \ cdots + q_ {p} -1 = N-1}$ $m "/ n"$ $N-1$ $m / n$ $NU$ $m / n$

{\ displaystyle {\ begin {align} {\ frac {m + m ''} ​​{n + n ''}} & = {\ frac {m_ {p} + m_ {p-1} + m_ {p }} {n_ {p} + n_ {p-1} + n_ {p}}} \\ & = {\ frac {2m_ {p} + m_ {p-1}} {2n_ {p} + n_ {p -1}}} \ end {align}}}

care este reducerea fracției continue așa cum este publicitate. ${\ displaystyle [q_ {1}, \ dots, q_ {p}, 2]}$

Această corespondență între fracțiile continuate și arborele Stern-Brocot este baza definiției funcției? lui Minkowski : în mod informal, acesta se potrivește cu realul asociat cu o ramură a subarborelui arborelui Stern-Brocot înrădăcinat în $1/2$ (văzut ca o expansiune infinită a fracției continue a unui real mai mic de 1) la realul asociat cu aceeași ramură dar în arborele diadic , adică realul a cărui expansiune în baza 2, văzută ca o secvență infinită de 0 și 1, codifică ramura.

În cazul unei fracții mai mici de 1, a cărei expansiune într-o fracție continuă este deci de forma $[0; q 1 , ..., q p ]$ , funcția? consideră calea care începe de la fracțiunea $1/2$ care este deci codificată ulterior $q 1 - 1, ..., q p$ și asociază cu ea raționalul diadic care apare în aceeași poziție în arborele diadic; aceasta se calculează luând în considerare cuvântul $1 q 1 -1 0 q 2 ... ε q p care$ codifică calea, adăugând un 1 la final, care dă $1 q 1 -1 0 q 2 ... ε q p 1$ și citirea cuvântului obținut ca expansiune în baza 2 a unui rațional diadic.

De exemplu $2/5$ are pentru expansiune $[0; 2, 2] = [0; 2, 1, 1]$ . Calea care duce acolo de la fracțiunea $1/2$ este, prin urmare, codificată mai jos $(1, 1),$ care dă cuvântul binar $0 1 1 1 1 = 011$ . Acest cuvânt este citit ca expansiune binară a raționalului $diadic (0,011) 2 = 1/4 + 1/8 = 3/8$ . De asemenea, $5/7$ are pentru extindere $[0; 1, 2, 1, 1]$ , deci calea sa de la $1/2$ este codificată ulterior $(0, 2, 1)$ , de unde cuvântul binar $0 0 1 2 0 1 1 = 1101$ care dă în cele din urmă binarul de expansiune $(0.1101) 2 = 1/2 + 1/4 + 1/16 = 13/16$ .

Algoritm matricial

Oferim aici o metodă care utilizează calculul matricial pentru a determina o fracțiune cunoscând poziția sa în arborele Stern-Brocot care este o variantă a calculului reducerilor expansiunii sale într-o fracție continuată. Pentru lizibilitate în această secțiune, vom codifica căile ca cuvinte pe alfabetul compus din cele două litere G (pentru mișcări spre stânga) și D (pentru mișcări spre dreapta).

Este , prin urmare , un cuvânt S format din G si D , definim f (S) ca fracția corespunzătoare S , adică fracția de realizare începând de la rădăcină și de-a lungul traseului codificat de S . De exemplu, dacă S = GGD atunci f (S) = 2/5.

Luăm în considerare doar matricile 2x2 sau matricele 1x2 coloane. Având în vedere o matrice de coloane, denotăm raționalul . Dacă și sunt două matrice de coloane, mediana lor este ; terminologia este justificată de faptul că fracția este mediana în sensul definit mai sus al fracțiilor și . ${\ begin {pmatrix} m \\ n \ end {pmatrix}}$ ${\ displaystyle q {\ begin {pmatrix} m \\ n \ end {pmatrix}}}$ ${\ frac mn}$ $V_ {1}$ $V_ {2}$ $V_ {1} + V_ {2}$ ${\ displaystyle q (V_ {1} + V_ {2})}$ ${\ displaystyle q (V_ {1})}$ ${\ displaystyle q (V_ {2})}$

Rețineți că mediana și se obține aplicând matricea formată din cele două blocuri și matricii coloanei ; și întrucât același rezultat se obține cu matricea bloc . În concluzie : $V_ {1}$ $V_ {2}$ ${\ begin {pmatrix} V_ {1} și V_ {2} \ end {pmatrix}}$ $V_ {1}$ $V_ {2}$ ${\ displaystyle {\ begin {pmatrix} 1 \\ 1 \ end {pmatrix}}}$ ${\ displaystyle V_ {1} + V_ {2} = V_ {2} + V_ {1}}$ ${\ displaystyle {\ begin {pmatrix} V_ {2} și V_ {1} \ end {pmatrix}}}$

{\ displaystyle V_ {1} + V_ {2} = {\ begin {pmatrix} V_ {1} & V_ {2} \ end {pmatrix}} {\ begin {pmatrix} 1 \\ 1 \ end {pmatrix}} = {\ begin {pmatrix} V_ {2} & V_ {1} \ end {pmatrix}} {\ begin {pmatrix} 1 \\ 1 \ end {pmatrix}}}

Prin definiția arborelui Stern-Brocot, fiecare fracție apare ca mediana a două fracții și dintre care una este situată pe podeaua imediat deasupra. Ideea algoritmului matricial este de a calcula și mai degrabă decât ; mai exact vom calcula matricea . Deducem din aceasta din moment ce tocmai am văzut asta . ${\ displaystyle q (V)}$ ${\ displaystyle q (P_ {1})}$ ${\ displaystyle q (P_ {2})}$ $P_ {1}$ $P_ {2}$ $V$ ${\ displaystyle {\ begin {pmatrix} P_ {2} & P_ {1} \ end {pmatrix}}}$ $V$ ${\ displaystyle V = {\ begin {pmatrix} P_ {2} & P_ {1} \ end {pmatrix}} {\ begin {pmatrix} 1 \\ 1 \ end {pmatrix}}}$

Pentru aceasta observăm că dacă se obține ca mediană a și , atunci cele două fiice din stânga și din dreapta sunt, respectiv, medianele din și și din și . Cu alte cuvinte, mergem de la matricea asociată cu matricile asociate fiicei sale stângi și asociate fiicei sale drepte. ${\ displaystyle q (V)}$ ${\ displaystyle q (P_ {1})}$ ${\ displaystyle q (P_ {2})}$ ${\ displaystyle q (V)}$ ${\ displaystyle q (P_ {1})}$ ${\ displaystyle q (V)}$ ${\ displaystyle q (V)}$ ${\ displaystyle q (P_ {2})}$ ${\ displaystyle {\ begin {pmatrix} P_ {2} & P_ {1} \ end {pmatrix}}}$ ${\ displaystyle V = P_ {1} + P_ {2}}$ ${\ displaystyle {\ begin {pmatrix} P_ {1} + P_ {2} & P_ {1} \ end {pmatrix}}}$ ${\ displaystyle {\ begin {pmatrix} P_ {2} & P_ {1} + P_ {2} \ end {pmatrix}}}$

Acest lucru duce la definirea de atunci avem: și . ${\ hat G} = {\ begin {pmatrix} 1 & 0 \\ 1 & 1 \ end {pmatrix}}, \, {\ hat D} = {\ begin {pmatrix} 1 & 1 \\ 0 & 1 \ sfârșit {pmatrix}}$ ${\ displaystyle {\ begin {pmatrix} P_ {2} & P_ {1} \ end {pmatrix}} {\ hat {G}} = {\ begin {pmatrix} P_ {2} + P_ {1} & P_ { 1} \ end {pmatrix}}}$ ${\ displaystyle {\ begin {pmatrix} P_ {2} & P_ {1} \ end {pmatrix}} {\ hat {D}} = {\ begin {pmatrix} P_ {2} & P_ {2} + P_ { 1} \ end {pmatrix}}}$

Astfel am definit matricele corespunzătoare celor două coborâri din stânga și din dreapta de la o mamă la fiica ei; rămâne să itereze procesul de-a lungul căii S (spunem că facem ca monoidul cuvintelor să acționeze asupra matricilor) prin definiția recursivă:

dacă este cuvântul gol (reprezentând calea de la rădăcină la sine) atunci ; ${\ displaystyle S = \ epsilon}$ ${\ displaystyle {\ hat {S}} = {\ hat {\ epsilon}} = {\ begin {pmatrix} 1 & 0 \\ 0 & 1 \ end {pmatrix}}}$
dacă reprezintă o cale care se termină cu o mișcare la stânga, atunci ; ${\ displaystyle S = TG}$ ${\ displaystyle {\ hat {S}} = {\ hat {T}} {\ hat {G}}}$
dacă reprezintă o cale care se termină printr-o mișcare dreaptă, atunci . ${\ displaystyle S = TD}$ ${\ displaystyle {\ hat {S}} = {\ hat {T}} {\ hat {D}}}$

Rețineți că matricea are forma unde și sunt cele două matrice de coloane corespunzătoare celor 2 fracții 0/1 și 1/0, a căror mediană este rădăcina arborelui Stern-Brocot. Astfel, matricea asociată cu calea goală face posibilă calcularea fracției asociate cu calea goală, și anume rădăcina arborelui. Observăm că aceasta este matricea identității; Pentru a obține această simplificare am inversat ordinea matricilor, preferând să calculăm mai degrabă decât . ${\ displaystyle {\ hat {\ epsilon}}}$ ${\ displaystyle {\ begin {pmatrix} V_ {2} și V_ {1} \ end {pmatrix}}}$ ${\ displaystyle V_ {1} = {\ begin {pmatrix} 0 \\ 1 \ end {pmatrix}}}$ ${\ displaystyle V_ {2} = {\ begin {pmatrix} 1 \\ 0 \ end {pmatrix}}}$ ${\ displaystyle {\ hat {\ epsilon}}}$ ${\ displaystyle {\ begin {pmatrix} P_ {2} & P_ {1} \ end {pmatrix}}}$ ${\ displaystyle {\ begin {pmatrix} P_ {2} & P_ {1} \ end {pmatrix}}}$

Deci, dacă este cuvântul în care sunt G sau D, atunci este matricea . $S$ ${\ displaystyle S_ {1} S_ {2} \ ldots S_ {n}}$ $Da}$ ${\ hat S}$ ${\ displaystyle {\ hat {\ epsilon}} {\ hat {S}} _ {1} \ dots {\ hat {S}} _ {n} = {\ hat {S}} _ {1} \ dots { \ hat {S}} _ {n}}$

Acest lucru ne oferă un mod foarte frumos de a ne calcula fracția : $f (S)$

{\ displaystyle f (S) = q \ left ({\ hat {S}} _ {1} {\ hat {S}} _ {2} \ ldots {\ hat {S}} _ {n} {\ begin {pmatrix} 1 \\ 1 \ end {pmatrix}} \ right)}

Deci, pe exemplul căii care duce la fracția 2/5 avem: ${\ displaystyle S = GGD}$

${\ displaystyle {\ hat {S}} = {\ hat {G}} {\ hat {G}} {\ hat {D}} = {\ begin {pmatrix} 1 & 0 \\ 1 & 1 \ end { pmatrix}} {\ begin {pmatrix} 1 & 0 \\ 1 & 1 \ end {pmatrix}} {\ begin {pmatrix} 1 & 1 \\ 0 & 1 \ end {pmatrix}} = {\ begin {pmatrix} 1 & 1 \\ 2 & 3 \ end {pmatrix}}}$ astfel încât în cele din urmă așa cum era de așteptat. ${\ displaystyle {\ hat {S}} {\ begin {pmatrix} 1 \\ 1 \ end {pmatrix}} = {\ begin {pmatrix} 2 \\ 5 \ end {pmatrix}}}$

Vezi și tu

Articole similare

linkuri externe

Roger Mansuy, „ Achille Brocot, matematician în timpul liber ” , la CultureMATH ,20 mai 2008
(ro) Eric W. Weisstein , „ Stern-Brocot Tree ” , pe MathWorld

Referințe

Linas Vepstas, „ Punctul de întrebare Minkowski și grupul modular SL (2, Z) ” ,2004

Matematică concretă ( ediția a II- a ) pentru Ronald Graham , Donald Knuth și Oren Patashnik ( ISBN 978-2-7117-4824-2 )