Stern-Brocot-puu

On matematiikka , Stern-Brocot puu on esitys kaikista tiukasti positiivinen rationals , muodossa irreducible fraktiot .

Sen löysivät melkein samanaikaisesti saksalainen matemaatikko Moritz Stern (1858) ja ranskalainen kelloseppä Achille Brocot (1861).

Rakentaminen

Stern-Brocot-puu on ääretön binääripuu, jonka solmut on merkitty pelkistämättömillä jakeilla. Se on rakennettu toistuvasti, yksi kerros toisensa jälkeen.

Kerros 1 sisältää vain puun juuren, jossa on murto 1/1.

Puun vaihe p +1 rakennetaan seuraavasti: luetellaan kaikki p- pistettä vastaavat äärellisen alipuun murtoluvut vasemmalta oikealle. Lisätään jae 0/1 luettelon yläosaan ja 1/0 luettelon loppuun, jolloin saadaan luettelo 2 p +1 jakeesta (katso kuva). Tässä luettelossa yksi kahdesta jakeesta kuuluu vaiheeseen p , yksi neljästä vaiheeseen p - 1 ja niin edelleen.

Kuhunkin p- vaiheeseen kuuluvaan fraktioon yhdistämme sen kaksi p- 1- tason tytärtä, jotka saadaan tekemällä mediaani kumpaankin listan naapuriin: murtoluvun mediaani ja murtoluku . ${\ frac mn}$ ${\ frac {m '} {n'}}$ ${\ frac {m + m '} {n + n'}}$

Esimerkki: puun ensimmäiset vaiheet

Tässä ovat luettelot puun sisältämistä murto-osista jokaisen neljän ensimmäisen vaiheen rakentamisen jälkeen (esitetty myös piirustuksessa), joihin lisättiin ensin 0/1, viimeinen 1/0. Jokaisessa kerroksessa siihen kerrokseen lisätyt jakeet ovat väriltään punaisia, muut ovat edellisten kerrosten osia.

${\ displaystyle {\ begin {array} {lccccccccccccccccc} {\ text {1. kerros:}} ja {\ frac {0} {1}} &&&&&&&& {{color {red} {\ frac {1} {1}}} &&&&&&&& {\ frac {1} {0}} \\ {\ text {2. kerros:}} ja {\ frac {0} {1}} &&&& {\ color {punainen} {\ frac {1} {2}} } &&&& {\ frac {1} {1}} &&&& {\ color {red} {\ frac {2} {1}}} &&&& {{frac {1} {0}} \\ {\ text {kerros 3: }} & {\ frac {0} {1}} && {\ color {red} {\ frac {1} {3}}} && {\ frac {1} {2}} && {\ color {red} { \ frac {2} {3}}} && {\ frac {1} {1}} && {\ color {punainen} {\ frac {3} {2}}} && {\ frac {2} {1}} && {\ color {red} {\ frac {3} {1}}} && {\ frac {1} {0}} \\ {\ text {Kerros 4:}} ja {\ frac {0} {1} } & {\ color {red} {\ frac {1} {4}}} & {\ frac {1} {3}} & {\ color {red} {\ frac {2} {5}}} ja { \ frac {1} {2}} ja {\ color {red} {\ frac {3} {5}}} & {\ frac {2} {3}} ja {\ color {red} {\ frac {3 } {4}}} ja {\ frac {1} {1}} ja {\ color {punainen} {\ frac {4} {3}}} ja {\ frac {3} {2}} ja {\ color {red} {\ frac {5} {3}}} ja {\ frac {2} {1}} ja {\ color {red} {\ frac {5} {2}}} ja {\ frac {3} {1}} ja {\ color {punainen} {\ frac {4} {1}}} ja {\ frac {1} {0}} \ end {array}}}$

Perusominaisuudet: linkki Fareyn sviitteihin

Stern-Brocot-puu liittyy läheisesti Farey-sviitteihin . Muistakaamme, että kaksi pelkistämätöntä jaetta m / n ja m ' / n' ovat lähellä Fareyä jos meillä on:

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

Tässä tapauksessa tarkistamme (katso alla), että heidän mediaaninsa on lähellä Fareyä, ensimmäisen oikealla puolella, toisen vasemmalla puolella. Tämän seurauksena on erityisesti, että m / n <( m + m ' ) / ( n + n' ) < m ' / n' ; päätellään, että Stern-Brocot-puun jokaisessa vaiheessa p alipuussa esiintyvien 2 p + 1 -murtolukujen luettelo järjestetään pienimmästä suurimpaan ja että tässä luettelossa kaksi peräkkäistä murto-osaa ovat Fareyn naapureita. Tämä viimeinen ominaisuus tarkoittaa myös sitä, että kaikki puussa esiintyvät jakeet ovat pelkistämättömiä.

Huomaa, että puun vasen haara sisältää kaikki yksikköosuudet , kun taas oikea haara sisältää kaikki kokonaisuudet, jotka on kirjoitettu murtoina nimittäjällä, joka on yhtä suuri kuin 1.

Kullakin tasolla vastaavan luettelon murtolukujen nimittäjät muodostavat Sternin piimaa .

Stern-Brocot-puu ja euklidinen algoritmi

Stern-Brocot-puu, kuten Farey-sekvenssit, liittyy myös Euclidin algoritmiin ; tämä antaa mahdollisuuden murtoluku m / n huomioon ottaen laskea polun, joka johtaa juuresta jälkimmäiseen.

Tätä varten käytämme Bachet-Bézout-teoreemaa : jos oletetaan, että m / n on pelkistämätön, ts. Että m ja n ovat kopriimeja, niin on olemassa kaksi kokonaislukua m ' ja n' siten, että m'n - mn ' = 1 ( tai mn '- m'n = 1); jos lisäksi oletetaan, että m ja n ovat erillisiä eivätkä molemmat ole nollia, voimme valita m ' ja n' siten, että 0 ≤ m '≤ m ja 0 ≤ n' ≤ n (kertoimet m ' ja n' tyydyttävät kaikki nämä rajoitukset lasketaan suoraan laajennetulla Euclidean algoritmilla ). Tässä tapauksessa, kuten näimme yllä, murtoluvut m ' / n' ja m / n ovat lähellä Fareyä .

Sitten asetetaan m '' = m - m ' ja n' '= n - n' ; jos m'n - mn ' = 1, niin mn' '- m''n = 1, muuten mn' - m'n = 1 ja siksi m''n - mn '' = 1. Lisäksi m / n on mediaani murto-osa m ' / n' ja m '' / n '' , joista päätellään m ' / n' < m / n < m '' n '', jos mn '- m'n = 1 tai m' ' / n '' < m / n < m ' / n' si m'n - mn ' = 1. Stern-Brocot puu, osa m / n on tytär kuin kaksi fraktiota m '/ n' ja m '' / n '', jolla on korkein nimittäjä, koska tämä on alimmalla kerroksella, ja m'n - mn -merkin mukaan määritämme, onko tyttö vasemmalla vai oikealla .

Esimerkiksi, jos tarkastellaan murto-osaa 2/5, Euclidin algoritmi antaa meille -2 × 2 + 1 × 5 = 1. Johtopäätöksenä on, että 1/2 ja (2 - 1) / (5 - 2) = 1/3 ovat naapurit 2/5 Farey-järjestyksessä järjestyksessä 5; koska 1/3: lla on suurin nimittäjä, hän on 2/5: n äiti; lisäksi yhtälö -2 × 2 + 1 × 5 = 1 tarkoittaa, että 1/2> 2/5, siis se 1/3 <2/5, josta päätellään, että 2/5 on 1/3: n oikea tytär.

Toistamalla yllä oleva argumentti voimme induktiolla osoittaa, että tuotamme rajallisen sekvenssin murtoluvuista tyttärestä äidiksi, ts. Polun puusta, joka nousee alkuperäisestä jakeesta juurelle. Erityisesti tämä antaa todistuksen jokaisen pelkistämättömän jakeen olemassaolosta puussa.

Perustelujen luettelointi

Stern-Brocot-puun perusominaisuus on, että se sisältää kaikki pelkistämättömät tiukasti positiiviset jakeet kerran ja vain kerran kussakin. Johdamme prosessin kaikkien positiivisten perustelujen numeroimiseksi, toisin sanoen positiivisten perustelujen bijektion positiivisista luonnollisista luvuista. Lyhyesti sanottuna yhdistämme rationaaliin kokonaisluvun, jonka edustus pohjassa 2 koodaa polun puun juuresta valittuun rationaaliin.

Annettuna murtoluku yhdistämme siihen sarjan 0 ja 1, joka edustaa polkua puun juuresta ja johtaa siihen. Siksi määritellään kaksi "vaihetta": vaihe 0 (vasen) ja vaihe 1 (oikea) (viitteessä mainitussa kirjassa nämä merkitään L vasemmalle ja R oikealle ). Esimerkiksi murtoon 2/5 johtavaa polkua edustaa seuraava (0, 0, 1): mene juuresta kahdesti vasemmalle ja sitten oikealle. Yksinkertaistamiseksi merkitsemme nyt 0: n ja 1: n sekvenssit binäärisanoiksi , esimerkiksi sekvenssi (0, 0, 1) esitetään binäärisanana 001.

Ajatus on nyt lukea binäärisana liittyy murto kuin pohjan 2 esitys on kokonaisluku. Kuitenkin, koska useat binäärisanat voivat edustaa samaa kokonaislukua (esimerkiksi sanat 1, 01, 001, ..., kaikki edustavat kokonaislukua 1), etuliitämme ensin polun edustuksen 1. Jos otamme esimerkin l rationaalisen 2/5: n polkua edustaa sana 001, josta kun sen etuliite on 1, tulee 1001, joka lukee samalla tavalla kuin kokonaisluvun 9 emäksessä 2 oleva esitys. Samoin rationaalinen 3/5 liittyy kokonaislukuun , järkevä 5/2 jne. Siksi osoitamme jokaiselle järkevälle numerolle yksilöllisen numeron, ja vastavuoroisesti kaikki pohjaan 2 kirjoitetut kokonaisluvut voidaan tulkita puun poluksi, joka johtaa järkevyyteen. ${\ displaystyle (1010) _ {2} = 10}$ ${\ displaystyle (1110) _ {2} = 14}$

Esittelyt

Kunkin jakeen pelkistämättömyys

Osoitamme, että jokainen puussa esiintyvä jae on indusoitumaton .

Muistamme , että Stern-Brocot-puun p-kerrokseen liittyvä luettelo on luettelo korkeuden p alipuun murtoluvuista vasemmalta oikealle luettuna, johon lisätään yläosaan 0/1 ja 1/0 häntä. Näytämme virallisesti yllä mainitun ominaisuuden: kaksi peräkkäistä murto-osaa luettelossa ovat lähellä Fareyä. ${\ displaystyle 2 ^ {p + 1} -1}$

Alustus : Vaiheessa 0 on selvää: meillä on 1,1 - 0,0 = 1.

Perintö : Oletetaan induktiolla ominaisuus, joka on tarkistettu vaiheessa p .

Rakentamisen perusteella vaiheessa p + 1 esiintyvät uudet jakeet ovat mediaaneja (m + m ') / (n + n'), joissa m / n ja m '/ n' ovat peräkkäisiä vaiheeseen p liittyvässä luettelossa ; induktiohypoteesin perusteella meillä on m'n - mn '= 1 . Pitäisi nähdä, että murtoluvut m / n , (m + m ') / (n + n') ja m '/ n', jotka ovat peräkkäisiä vaiheeseen p + 1 liittyvässä luettelossa, ovat lähellä Fareyä, joka on johdettu seuraavista laskelmista:

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

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

Täten kaikki vaiheeseen p + 1 liittyvän luettelon peräkkäisten murtolukujen m / n ja m '/ n' parit varmistavat, että m'n - mn '= 1 on Bézout-suhde, josta päätellään erityisesti, että m ja n ovat kopriimeja, joten m / n (samoin kuin m '/ n' ) on pelkistämätön.

Ainutlaatuisuus

Haluamme osoittaa, että jokainen ehdottomasti positiivinen osa esiintyy korkeintaan kerran puussa. Tämä on seurausta siitä, että kussakin vaiheessa liitetty luettelo kasvaa tiukasti, mikä itsessään on seurausta edellä osoitetusta tosiasiasta, että vaiheeseen p liittyvän luettelon peräkkäiset jakeet ovat lähellä Fareyä; todellakin m'n - mn '= 1 tarkoittaa erityisesti, että m' / n '- m / n = 1 / nn'> 0, siis m / n <m '/ n' .

Olemassaolo

Olemme jo nähneet käyttämällä Euclidin algoritmia, että mikä tahansa pelkistämätön osa näkyy puussa. Toinen mielenosoitus annetaan täällä.

Tarkastellaan pelkistämätöntä jaetta, jota merkitään a / b . Tulemme rakentamaan neljä sviittiä kokonaislukujen , , ja induktiolla p : ${\ displaystyle (m_ {p})}$ ${\ displaystyle (n_ {p})}$ ${\ displaystyle (m '_ {p})}$ ${\ displaystyle (n '_ {p})}$

Sillä p = 0 asetamme , , ja . ${\ displaystyle m_ {0} = 0}$ ${\ displaystyle n_ {0} = 1}$ ${\ displaystyle m '_ {0} = 1}$ ${\ displaystyle n '_ {0} = 0}$

Vaiheessa p on käytettävissä kolme tapausta:

${\ displaystyle {\ frac {m_ {p} + m '_ {p}} {n_ {p} + n' _ {p}}} = {\ frac {a} {b}}}$ : laitamme sitten ja . ${\ 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}}}$ : poseeramme ; ; ja . ${\ 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}$ : poseeramme ; ; ja . ${\ 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}}$

Tällä määritelmällä on useita seurauksia, jotka voidaan helposti tarkistaa toistumisen avulla:

neljä jono kokonaislukuja , , ja kasvaa (mutta ei tiukasti kasvava). ${\ displaystyle (m_ {p})}$ ${\ displaystyle (n_ {p})}$ ${\ displaystyle (m '_ {p})}$ ${\ displaystyle (n '_ {p})}$

kaikki p , jos fraktiot ja ovat erilaisia silloin meillä on , ne ovat peräkkäisiä luettelossa liittyy vaiheessa p , siis erityisesti lähellä Farey, mikä merkitsee erityisesti, että ne ovat redusoitumaton. Lisäksi toinen näistä kahdesta kuuluu vaiheeseen p ja siten niiden mediaani kuuluu vaiheeseen p + 1 . Itse asiassa vaiheeseen p liittyvässä luettelossa yksi jae kahdesta kuuluu vaiheeseen p , joten kahden peräkkäisen jakeen mediaani kuuluu vaiheeseen p + 1 . ${\ displaystyle m_ {p} / n_ {p}}$ ${\ displaystyle m '_ {p} / n' _ {p}}$ ${\ displaystyle m_ {p} / n_ {p} <a / b <m '_ {p} / n' _ {p}}$

kaikille p: lle, jos murtoluvut ja ovat yhtä suuria, ne ovat molemmat yhtä suuria kuin a / b, ja niin on ja kaikille . ${\ displaystyle m_ {p} / n_ {p}}$ ${\ displaystyle m '_ {p} / n' _ {p}}$ ${\ displaystyle m_ {q} / n_ {q}}$ ${\ displaystyle m '_ {q} / n' _ {q}}$ ${\ displaystyle q \ geq p}$

Haluamme osoittaa, että on olemassa sellainen p , joka ; jos sellainen p on olemassa, olettaen, että se on pienin, yksi on ja koska mediaani kuuluu sitten vaiheeseen p + 1, tämä osoittaa, että yksi on löydetty puusta. ${\ 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$

Kuten meillä on ja kokonaisuutena päätämme . Samoin päätämme . Näiden kahden arvon kertominen eriarvoisuutta vastaavasti ja saamme: . ${\ 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}}$

Kuitenkin käyttämällä se, että ja ovat naapurit Farey olemme: ${\ displaystyle m_ {p} / n_ {p}}$ ${\ displaystyle m '_ {p} / n' _ {p}}$

{\ displaystyle {\ begin {tasattu} (m '_ {p} + n' _ {p}) (an_ {p} -bm_ {p}) + (m_ {p} + n_ {p}) (bm ' _ {p} -an '_ {p}) & = olen' _ {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 \ loppu {tasattu}}}

Siksi vihdoin: . ${\ displaystyle a + b \ geq m '_ {p} + n' _ {p} + m_ {p} + n_ {p}}$

Siksi kokonaislukujen sarjaa rajaa . Siksi se ei voi nousta tiukasti, mutta se kasvaa, koska se on neljän kasvavan sekvenssin summa, joten on olemassa p-arvo , josta se on paikallaan. Mutta silloin meillä on muuten oltava ja määritelmän mukaan ainakin yksi (mahdollisesti molemmat) tai yhtä suuri kuin mediaani, niin että summa olisi ehdottomasti suurempi kuin , mikä on ristiriidassa p: n sekvenssin stationaarisuuden kanssa . ${\ 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}}$

Vertailu Euclidin algoritmiin

Eukleidesin algoritmi antaa mahdollisuuden osoittaa murto-osan esiintyminen puussa tästä alkaen ja peräkkäisillä euklidisilla jakoilla, jotka menevät ylöspäin juurta kohti, siten rakentaen polun ylöspäin murtoluvusta juurelle. Yllä oleva esittely etenee toiseen suuntaan: alkaen juuresta tuotamme sarjan murtoja, jotka lopulta päättyvät alun perin annettuun, tuottaen polun, joka laskeutuu juuresta siihen. Huomaa, että sama algoritmi, jota sovelletaan reaalilukuun eikä murtolukuun, antaa mahdollisuuden rakentaa tämän todellisen lähentävän murtolukujen ääretön haara.

Jatkuvat jakeet

Mikä tahansa murtoluku sallii äärellisen jatkuvan murtolaajennuksen, jonka kertoimet ovat Euclidin algoritmilla laskettuja peräkkäisiä osamääriä . Sama Eukleidesen algoritmi, joka tekee mahdolliseksi löytää polku, joka johtaa Stern-Brocot-puun juuresta tiettyyn murto-osaan, voimme päätellä, että jatko-osan laajennus koodaa tämän polun. Tarkalleen, jos $[ q 1 ; q 2 , ..., q p , 1] = [ q 1 ; q 2 , ..., q p + 1]$ on murtoluvun $m / n$ jatkuva murtolaajennus , $m / n: n$ kahdella tyttärellä Stern-Brocot-puussa on jatkuva murtolaajennus:

$[ 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]$ .

Induktiolla päätellään, että murtoluku $m / n$ esiintyy vaiheessa $q 1 + ... + q n$ ja että sekvenssi $( q 1 + ... + q n )$ kuvaa polun, joka johtaa siihen juuresta $1/1$ : mene alas $q 1$ askel oikealle, sitten $q 2$ askelta vasemmalle jne. jopa $q p$ ei vasemmalle, jos $p$ on parillinen, oikealle, jos $p$ on pariton.

Toisin sanoen polku, joka johtaa laajenemisosaan $[ q 1 ; q 2 , ..., q p , 1]$ koodataan sanalla $1 q 1 0 q 2 ... ε q p,$ jossa $ε$ on symboli $0,$ jos $p$ on parillinen, $1,$ jos $p$ on pariton.

Esimerkiksi jatkuva fraktion laajeneminen 2/5 on $[0; 2, 1, 1] = [0; 2, 2],$ joka vastaa polkua $001$ : 0 askelta oikealle, sitten 2 askelta vasemmalle, sitten yksi askel oikealle. Voimme myös laskea, että 17/12: n jatkuva jakeen laajeneminen on $[1; 2, 2, 2] = [1; 2, 2, 1, 1],$ kun taas puuhun 17/12 johtavaa polkua edustaa sana $100110$ .

Esittely

Katsotaan puhelun korkeus on numero . Oletetaan induktiolla, että mikä tahansa korkeuden tai pienempi murtoluku näkyy yläkerrassa Stern-Brocot-puussa. Ensinnäkin huomaamme , että kaksi oletettua tytärtä ovat pitkiä ja kun he ilmestyvät yläkertaan (heidän äitinsä on yläkerrassa ), olemme osoittaneet induktiolla hyvin puun korkeuden ja lattian välisen tasa-arvon. $m / n$ ${\ displaystyle N = q_ {1} + \ cdots + q_ {p}}$ $EI$ $EI$ $m / n$ $N + 1$ $N + 1$ $EI$

Vielä on osoitettava, että nämä kaksi jaetta ovat todellakin tytärtä . Siksi löydämme lattiaan liittyvästä luettelosta kaksi naapuria . $m / n$ $m / n$ $EI$

Aloitetaan kahdesta alustavasta muistutuksesta. Farey-naapurustojen ominaisuuksien joukossa on erityisesti se tosiasia, että kun ja ovat Fareyn naapureita, mikä tahansa tiukasti näiden kahden välissä oleva murto-osa saadaan iteroimalla mediaanitoiminta alkaen, ja siksi se ilmestyy välttämättä korkeammalle tasolle molemmissa Stern- Brocot-puu. $a / b$ $a '/ b'$ ${\ displaystyle a '' / b ''}$ $a / b$ $a '/ b'$

Toisaalta, jos se on jatkuva murtoluku, sen alennettu arvo annetaan toistumisella: ${\ displaystyle [q_ {1}; q_ {2}, \ pisteitä, q_ {p}]}$ ${\ displaystyle m_ {k} / n_ {k} = [q_ {1}; q_ {2}, ..., q_ {k}]}$ ${\ displaystyle k = 1, \ pistettä, 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}}$

Erityisesti, koska meillä on ${\ displaystyle m / n = [q_ {1}, \ pistettä, 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} }}}

Harkitse jatko-osuutta . Tämä on Fareyn naapuri . Voimme todellakin tehdä seuraavan laskelman: ${\ displaystyle m '/ n' = [q_ {1}, \ pistettä, q_ {n-1}] = m_ {p-1} / n_ {p-1}}$ $m / n$

{\ displaystyle {\ begin {tasattu} 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}) \ loppu {tasattu}}}

josta johtopäätöksemme induktiolla että ja siksi ja ovat lähellä Fareyä . Toisin sanoen kahden jatketun murto-osan reduktiot, joiden ensimmäinen on toisen etuliite ja joiden pituudet eroavat yhdestä, ovat lähellä Fareyä. Siksi ja ovat Fareyn naapureita. Tai onko korkeus, kun taas korkeus , induktio-hypoteesi on yläkerrassa , joten molemmat ovat tarinaan liittyvässä luettelossa ja ovat siksi peräkkäisiä siinä. ${\ displaystyle m_ {k + 1} n_ {k} -m_ {k} n_ {k + 1} = (- 1) ^ {k + 1}}$ ${\ displaystyle m_ {k} / n_ {k} = [q_ {1}, \ pisteitä, q_ {k}]}$ ${\ displaystyle m_ {k + 1} / n_ {k + 1} = [q_ {1}, \ pistettä, q_ {k + 1}]}$ ${\ displaystyle k = 1, \ pistettä, p}$ ${\ displaystyle m / n = [q_ {1}, \ pistettä, q_ {p} +1]}$ ${\ displaystyle m '/ n' = [q_ {1}, \ pistettä, q_ {p-1}]}$ $m / n$ $EI$ $m '/ n'$ ${\ displaystyle N '= q_ {1} + \ cdots q_ {p-1} -1 <N}$ $m '/ n'$ $EI'$ $EI$

Johtopäätöksenä on, että yksi yläkerran tytöistä on heidän mediaani: $m / n$ $N + 1$

{\ displaystyle {\ begin {tasattu} {\ 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}}} \ loppu {tasattu} }}

mikä on jatkuvan jakeen pienennys odotetusti. ${\ displaystyle [q_ {1}, \ pisteet, q_ {p} +2]}$

Harkitse nyt murto-osaa . Joten meillä on: ${\ displaystyle m '' / n '' = [q_ {1}, \ pistettä, q_ {p}] = m_ {p} / n_ {p}}$

{\ displaystyle {\ begin {aligned} 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} \ loppu {tasattu}}}

niin että taas ja ovat Fareyn naapureita. Mutta onko korkeus siis induktiolla, onko se yläkerrassa , on siis lähellä lattiaan liittyvää luetteloa . Siksi heidän toinen tyttärensä on heidän mediaani: $m '' / n ''$ $m / n$ $m '' / n ''$ ${\ displaystyle N '' = q_ {1} + \ cdots + q_ {p} -1 = N-1}$ $m '' / n ''$ $N-1$ $m / n$ $EI$ $m / n$

{\ displaystyle {\ begin {tasattu} {\ 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}}} \ loppu {tasattu}}}

mikä on mainostetun jatkuvan jakeen vähennys . ${\ displaystyle [q_ {1}, \ pisteet, q_ {p}, 2]}$

Tämä jatko-osien ja Stern-Brocot-puun vastaavuus on funktion määritelmän perusta ? Minkowskista : epävirallisesti tämä vastaa todellista, joka liittyy Stern-Brocot-puun osapuun haaraan, joka on juurtunut $1/2: een$ (pidetään äärettömänä jatkuvana murto-osuutena, jonka todellinen pienempi kuin 1) todelliseen, joka liittyy tähän samaan haaraan mutta diadiapuussa , toisin sanoen todelliselle, jonka laajeneminen pohjassa 2, jota pidetään 0: n ja 1: n äärettömänä sekvenssinä, koodaa haaraa.

Jos kyseessä on pienempi kuin 1 murtoluku, jonka laajeneminen jatkuvaksi jakeeksi on siis muotoa $[0; q 1 , ..., q p ]$ , toiminto? tarkastelee polusta alkaen fraktiosta $1/2,$ joka koodataan sen jälkeen $q 1 - 1, ..., q p,$ ja yhdistää siihen diadisen rationaalin, joka esiintyy samassa asemassa diadiapuussa; tämä lasketaan ottamalla huomioon polkua koodaava sana $1 q 1 -1 0 q 2 ... ε q p$ , lisäämällä loppuun 1, joka antaa $1 q 1 -1 0 q 2 ... ε q p 1$ ja luetaan sana, joka on saatu kaksisuuntaisen rationaalin laajennuksena pohjaan 2.

Esimerkiksi $2/5$ on laajennukseen $[0; 2, 2] = [0; 2, 1, 1]$ . Murtoluvusta $1/2$ johtava polku on siis koodattu alapuolelle $(1, 1),$ mikä antaa binäärisanan $0 1 1 1 1 = 011$ . Tämä sana luetaan dinaattisen rationaalisen $(0,011) 2 = 1/4 + 1/8 = 3/8$ binäärisenä laajenemisena . Samoin $5/7$ on laajennukseen $[0; 1, 2, 1, 1]$ , joten sen polku $1/2: sta$ koodataan sen jälkeen $(0, 2, 1)$ , joten binäärisana $0 0 1 2 0 1 1 = 1101,$ joka lopulta antaa laajennusbinaarin $(0.1101) 2 = 1/2 + 1/4 + 1/16 = 13/16$ .

Matriisialgoritmi

Annamme tässä menetelmän, joka käyttää matriisilaskua murtoluvun määrittämiseksi tietäen sen sijainnin Stern-Brocot-puussa, joka on muunnelma sen laajenemisen pienennysten laskemisesta jatkuva murtoluku. Tämän osan luettavuuden vuoksi koodataan polut sanoiksi aakkosessa, joka koostuu kahdesta kirjaimesta G (vasemmalle suuntautuville liikkeille) ja D (oikealle suuntautuville liikkeille).

Näin ollen sanan S , joka koostuu G ja D , määritellään f (S) kuin osa, joka vastaa S , eli saavuttamiseen osa alkaa juuresta ja pitkin polkua, jota koodaa S . Esimerkiksi jos S = GGD sitten f (S) = 2/5.

Otamme huomioon vain 2x2-matriisit tai 1x2-sarakematriisit. Annettu sarakematriisi merkitsemme järkevää . Jos ja ovat kaksi sarakematriisia, niiden mediaani on ; terminologia on perusteltu sillä, että murtoluku on mediaani edellä määritellyssä murtolukujen ja . ${\ 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})}$

Huomaa, että mediaani ja saadaan laskemalla matriisi, joka koostuu kahdesta lohkosta, ja pylväsmatriisiin ; ja koska sama tulos saadaan lohkomatriisilla . Yhteenvetona : $V_ {1}$ $V_ {2}$ ${\ begin {pmatrix} V_ {1} & 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} & 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}}}

Määritelmän Stern-Brocot puu, kukin osa näkyy mediaani kaksi fraktiota ja joista toinen sijaitsee kerroksessa välittömästi edellä. Matriisialgoritmin idea on laskea ja pikemminkin ; tarkemmin laskemme matriisin . Päätämme tästä, koska olemme juuri nähneet sen . ${\ 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}}}$

Tästä huomaamme, että jos saadaan mediaani ja , sitten kaksi vasemmalle ja oikealle tyttäret ovat vastaavasti mediaanit ja sekä ja . Toisin sanoen, me menevät matriisin liittyvät matriiseihin liittyy sen vasen tytär, ja liittyvät oikeutensa tytär. ${\ 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}}}$

Tämä johtaa määrittelemään siitä lähtien meillä on: ja . ${\ hat G} = {\ aloita {pmatrix} 1 & 0 \\ 1 & 1 \ end {pmatrix}}, \, {\ hat D} = {\ begin {pmatrix} 1 ja 1 \\ 0 & 1 \ loppu {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}}}$

Siten olemme määrittäneet matriisit, jotka vastaavat kahta vasenta ja oikeaa laskeutumista äidistä tyttäreen; jää toistamaan prosessi polkua S pitkin (sanomme sanojen monoidin vaikuttavan matriiseihin) rekursiivisen määritelmän avulla:

jos on tyhjä sana (edustaa polkua juuresta itseensä) sitten ; ${\ displaystyle S = \ epsilon}$ ${\ displaystyle {\ hat {S}} = {\ hat {\ epsilon}} = {\ begin {pmatrix} 1 & 0 \\ 0 & 1 \ end {pmatrix}}}$
jos edustaa vasemmalla liikkeellä päättyvää polkua, niin ; ${\ displaystyle S = TG}$ ${\ displaystyle {\ hattu {S}} = {\ hattu {T}} {\ hattu {G}}}$
jos edustaa suoralla liikkeellä päättyvää polkua, niin . ${\ displaystyle S = TD}$ ${\ displaystyle {\ hattu {S}} = {\ hattu {T}} {\ hattu {D}}}$

Huomaa, että matriisilla on muoto missä ja ovat kaksi sarakematriisia, jotka vastaavat kahta fraktiota 0/1 ja 1/0, joiden mediaani on Stern-Brocot-puun juuri. Tyhjään polkuun liittyvä matriisi antaa siten mahdollisuuden laskea tyhjään polkuun liittyvä osa, nimittäin puun juuri. Huomaa, että se on identiteettimatriisi; Tämän yksinkertaistamisen saamiseksi olemme kääntäneet matriisien järjestyksen päinvastaiseksi laskemisen sijaan . ${\ displaystyle {\ hattu {\ epsilon}}}$ ${\ displaystyle {\ begin {pmatrix} V_ {2} & V_ {1} \ end {pmatrix}}}$ ${\ displaystyle V_ {1} = {\ alku {pmatrix} 0 \\ 1 \ loppu {pmatrix}}}$ ${\ displaystyle V_ {2} = {\ aloita {pmatrix} 1 \\ 0 \ end {pmatrix}}}$ ${\ displaystyle {\ hattu {\ epsilon}}}$ ${\ displaystyle {\ begin {pmatrix} P_ {2} & P_ {1} \ end {pmatrix}}}$ ${\ displaystyle {\ begin {pmatrix} P_ {2} & P_ {1} \ end {pmatrix}}}$

Joten jos on sana, jossa ovat G tai D, on sitten matriisi . $S$ ${\ displaystyle S_ {1} S_ {2} \ ldots S_ {n}}$ $Joo}$ ${\ hattu S}$ ${\ displaystyle {\ hattu {\ epsilon}} {\ hattu {S}} _ {1} \ pistettä {\ hattu {S}} _ {n} = {\ hattu {S}} _ {1} \ pistettä { \ hattu {S}} _ {n}}$

Tämä antaa meille erittäin mukavan tavan laskea murto-osa : $f (S)$

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

Joten esimerkissä polusta, joka johtaa murto-osaan 2/5, meillä on: ${\ 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}}}$ niin että lopulta odotetusti. ${\ displaystyle {\ hat {S}} {\ begin {pmatrix} 1 \\ 1 \ end {pmatrix}} = {\ begin {pmatrix} 2 \\ 5 \ end {pmatrix}}}$

Katso myös

Aiheeseen liittyvät artikkelit

Ulkoiset linkit

Roger Mansuy, " Achille Brocot, matemaatikko vapaa-ajallaan " , osoitteessa CultureMATH ,20. toukokuuta 2008
(en) Eric W. Weisstein , ” Stern-Brocot Tree ” , MathWorldissa

Viitteet

Linas Vepstas, " Minkowskin kysymysmerkki ja Modular Group SL (2, Z) " ,2004

Betoni Matematiikka ( 2 th edition) ja Ronald Graham , Donald Knuth ja Oren Patashnik ( ISBN 978-2-7117-4824-2 )