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
Edit