The n-dimensional Stern-Brocot tree
| Document type: | Researchreports |
|---|---|
| Full text: | |
| Author(s): | Håkan Lennerstad |
| Title: | The n-dimensional Stern-Brocot tree |
| Translated title: | Stern-Brocots träd i n dimensioner |
| Series: | Research Report |
| Year: | 2012 |
| Issue: | 4 |
| ISSN: | 1103-1581 |
| Organization: | Blekinge Institute of Technology |
| Department: | School of Engineering - Dept. Mathematics and Science (Sektionen för teknik – avd. för matematik och naturvetenskap) School of Engineering S- 371 79 Karlskrona +46 455 38 50 00 http://www.tek.bth.se/ |
| Authors e-mail: | hln@bth.se |
| Language: | English |
| Abstract: | The n-dimensional Stern-Brocot tree consists of all sequences (p₁, ...,p_{n}) of positive integers with no common multiple. The relatively prime sequences can be generated branchwise from each other by simple vector summation, starting with an ON-base, and controlled by a generalized Euclidean algorithm.The tree induces a multiresolution partition of the first quadrant of the (n-1)-dimensional unit sphere, providing a direction approximation property of a sequence by its ancestors. Two matrix representations are introduced, where in both a matrix contains the parents of a sequence. From one of them the isomorphism of a subtree to the entire tree of dimension equal to the number of parents of the top sequence follows. A form of Fibonacci sequences turn out to be the sequences of fastest growing sums. The construction can be regarded an n-dimensional continued fraction, and it may invite further n-dimesional number theory. |
| Summary in Swedish: | Stern-Brocots träd består av alla sekvenser (p₁, ...,p_{n}) av positiva heltal som saknar gemensam delare. De genereras gren för gren med vektoraddition, med en ON-bas som start, och kontrolleras av en generaliserad Euklidisk algoritm. Trädet inducerar en multiresolutionpartition av den första kvadranten av den (n-1)-dimensionella enhetssfären, vilket ger en riktningsapproximationsegenskap för en sekvens med dess föregångare i trädet. Två matrisrepresentationer presenteras, i båda innehåller matrisen alla föräldrar till en sekvens. Från en av dem följer isomorfismen av ett delträd med ett helt träd vars dimension är antalet föräldrar av toppsekvensen i delträdet. En typ av Fibonaccisekvenser visar sig vara sekvenserna som har snabbast växande summa. Konstruktionen kan ses som ett n-dimensionellt kedjebråk, och den kan vara en inbjudan till fortsatt n-dimensionell talteori. Nyckelord: Stern-Brocots träd, relativt prima tal, Fibonaccital, multiresolution partition, ON-bas, kedjebråk, Minkowskis frågeteckenfunktion. |
| Subject: | Mathematics\Discrete Mathematics Mathematics\Geometry |
| Keywords: | Stern-Brocot tree, relatively prime integers, relative primality, Fibonacci numbers, multiresolution partition, ON-base, continued fraction, Minkowski question mark function. |
| URN: | urn:nbn:se:bth-00534 |
