#### 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. http://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 *R**2 *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.