Year
2001
Degree Name
Doctor of Philosophy
Department
Faculty of Informatics
Recommended Citation
Bates, Bruce P., Self-matching and interleaving in some integer sequences and the gauss map, Doctor of Philosophy thesis, Faculty of Informatics, University of Wollongong, 2001. https://ro.uow.edu.au/theses/1850
Abstract
This thesis is primarily concerned with self-matching and interleaving within the following integer sequences: Paperfolding, the Stern-Brocot Sequence (and the related Stern-Brocot Tree), the Hyperbinary Sequence (and the related Hyperbinary Tree), the Gray Code and the Stickbreaking Sequence. It also investigates symmetry properties of the Gauss Map and the connection the Gauss Map has with the Stern-Brocot Tree.
Symmetry within the Gauss Map is shown to exist between neighbouring iterates. Repetition and Symmetry are shown to exist both within the same iterate, and amongst neighbouring iterates of the Generalised Gauss Map, which is an extension of the Gauss Map such that its domain covers all reals. The fixed points, periodic points and conditions for symmetry of the Gauss Map are each defined and explored, as is the location of each symmetric and repetitive element of the Generalised Gauss Map.
Self-matching and interleaving are shown to be fundamental properties of the Stern-Brocot Tree. The Stern-Brocot sequence is shown to be simply an interleave of mediants formed from an ancestral Stern-Brocot sequence. Mediants of the Stern-Brocot sequence are found to represent new terms forming a new level of the tree. The connections between the partial convergents of an irrational number and the Stern-Brocot Tree are also established. We show that these partial convergents when mapped into R2 reveal an interesting collinearity and equispacing.
T w o of the most important techniques found in this thesis are diagonalisation and additive factorisation. These techniques allow us to answer the following questions: "What is the jth term in the nth level of the tree?", and the related question "Where does the term a-b appear in the tree?" We demonstrate that additive factorisation is also useful in identifying terms in the Hyperbinary Tree. This tree similar to the Stern-Brocot Tree.
Another key result of this thesis is the demonstration that, for all their apparent dissimilarity, the Gauss Map and the Stern-Brocot Tree are intimately linked. We show that Branches in the Stern-Brocot Tree are analogues of Clusters in the Gauss Map.These linkages are preserved in the Generalised Stern-Brocot Tree and the Generalised Gauss Map.
The Paperfolding Sequence is shown to be a sequence that can be represented in both a self-matching manner as well as by an interleave operator. We show that these dual formulations are derivable from each other indicating the interconnectedness that can exist between self-matching sequences and interleave sequences. We also reveal that the Paperfolding sequence is subtly embedded in both the Stem-Brocot Tree and the Gray Code. Another interleaving sequence, the Stickbreaking sequence, is also defined. It is also examined in terms of its mixedness, a concept that measures the disorder that arises in a sequence. Stickbreaking and Perfect Shuffling are compared terms of their relative mixedness.
Unless otherwise indicated, the views expressed in this thesis are those of the author and do not necessarily represent the views of the University of Wollongong.