The n-dimensional Stern-Brocot tree
Responsible organisation
2012 (English)Report (Other academic)Alternative title
Stern-Brocots träd i n dimensioner (Swedish)
Abstract [en]
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.
Abstract [sv]
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.
Place, publisher, year, edition, pages
2012.
Series
Blekinge Tekniska Högskola Forskningsrapport, ISSN 1103-1581 ; 4
Keywords [en]
Stern-Brocot tree, relatively prime integers, relative primality, Fibonacci numbers, multiresolution partition, ON-base, continued fraction, Minkowski question mark function.
National Category
Mathematical Analysis Geometry
Identifiers
URN: urn:nbn:se:bth-00534Local ID: oai:bth.se:forskinfoA02A252219018A4EC1257A16003CC993OAI: oai:DiVA.org:bth-00534DiVA, id: diva2:834871
2012-09-182012-06-072016-09-06Bibliographically approved