Calkin-Wilf Tree
- PDF / 162,600 Bytes
- 13 Pages / 595 x 842 pts (A4) Page_size
- 36 Downloads / 172 Views
Calkin-Wilf Tree∗ K Siddharth Choudary, A Satyanarayana Reddy
In this article, we prove various properties of the Calkin-Wilf tree. We also see how the Minkowski question mark function acts on the Calkin-Wilf tree and its diagonals.
1 Introduction and Preliminaries The Calkin-Wilf tree is named after Neil Calkin and Herb Wilf. They used this tree in [1] to enumerate rational numbers in a novel approach. The Calkin-Wilf tree is a rooted binary tree, where each vertex (or fraction) has a left and a right child. The vertices of this tree are labeled by fractions. The root node is labeled with 11 . If the label of a vertex is ab , then the labels of its left and a right children respectively are a+b and a+b b . We denote gcd(a, b) as (a, b).
Siddharth Choudary is a BS (Research) Mathematics student from the Department of Mathematics, Shiv Nadar University. His research interests are number theory, combinatorics and computing.
a b
Satyanarayana Reddy is an a a+b
a+b b
Associate professor in the Department of Mathematics, Shiv Nadar University. His research interests are
The rooted tree, given in Figure 1 is the Calkin Wilf tree (CWtree) of height 5. Before stating a few immediate properties of the CW-tree, we need the following notations. Most of these observations are stated and proved in one of the following [1, 2, 3, 4], and we are sharing the proofs for the sake of completeness. Theorem 1.1.
1. Every fraction in CW-tree is in reduced form.
2. Every positive rational number appears uniquely in CW-tree. ∗ Vo.25,
combinatorial matrix theory and algebraic number theory.
Keywords Binary tree, continued fractions, Minkowski question mark function.
No.7, DOI: https://doi.org/10.1007/s12045-020-1015-x
RESONANCE | July 2020
1001
GENERAL ARTICLE
Figure 1.
CW-tree of
height 5.
1 1
1 2
2 1
1 3
3 2
1 4 1 5
4 3 5 4
4 7
2 3
3 5 7 3
3 8
2 5
5 2 8 5
5 7
3 1
7 2
2 7
3 4
5 3 7 5
5 8
8 3
3 7
4 1 7 4
4 5
5 1
3. At any given level, denominator of any fraction is equal to the numerator of its successive fraction (fraction on its right). 4. The jth vertex in any given level is the reciprocal of jth vertex form the end of that level. 5. Every vertex is the product of its children. 6. Product of all the elements in a given level is 1. 7. Sum of simplicities of all elements in a level is 1. 8. Product of complexities of all the elements in a level is a perfect square. 9. Sum of traces of all the elements at a level n is 2 · 3n−1 10. Sum of complexities at level n is equal to the sum of squares of traces at level n − 1. 11. Sum of all elements in a level n is 3 · 2n−2 − 21 . Product of all the elements in a given level is 1. Sum of simplicities of all elements in a level is 1. Product of complexities of all the elements in a level is a perfect square.
1002
Proof. We prove all these results except Part 2 using mathematical induction on heights of levels. using mathematical induction on levels. Proof of Part 1. The only fraction at level 1 is 11 and (1, 1) = 1. Assume that all the fractions at leve
Data Loading...
