The Calkin-Wilf Tree
This article assumes some familiarity with set theory, and terms such as countable and uncountable. If you are a student of math, at some point in life you would have been asked to show that the set of rational numbers is countable, i.e. in bijection (one-to-one correspondence) with the set of natural numbers. There are a couple of ways of doing this, most of which do not construct an explicit bijection — they merely prove its existence. While that definitely does the job, it is not the purpose of this article.
We present to you a beautiful bijection between the sets of positive rational and natural numbers. After some thought, you should be able to use this to construct a bijection between all rational numbers and naturals! We do this by means of a tree structure, namely the Calkin-Wilf tree. To warn those who seek rigorous details — we won’t go into the proofs of most results, and you’re suggested to try them out yourself, or look them up in your own time!
Let’s dive right into the main content, now. How do we construct this tree? Given a node associated with a rational number, we do the following (can you figure out what?) to determine its left and right children, uniquely.
In more explicit terms, this is what we do:
It is worth noting that the left child is always smaller than the parent, while the right child is greater. The Calkin-Wilf tree is rooted at 1 and is constructed in the above manner. What is interesting is that every rational number appears in the tree exactly once!
The Calkin-Wilf tree is pretty recent, it is named after Neil Calkin and Herbert Wilf, who talked about it in their 2000 paper. Stern’s diatomic series, which we shall see in a moment, was formulated much earlier by Moritz Stern. This series shares an intimate connection with the Calkin-Wilf tree, one that we shall attempt to describe in some part of this article.
Before getting into the details, let me leave you with some interesting observations! On the leftmost branch of the tree, all the numbers have 1 as the numerator, and on the rightmost branch of the tree, all the numbers have 1 as the denominator. The numerator and denominator at each vertex are relatively prime. Can you find the Fibonacci sequence hidden somewhere inside this tree? Food for thought!
Imagine yourself at the top of the tree. While you hypothetically traverse this beautiful tree, record your path in binary — a 0 denoting a left turn and a 1 denoting a right turn. For example, the path to reach 3/2 is read as 01, i.e. a left turn followed by a right turn. What happens if we reverse this binary number (this is called a reverse-path corresponding to 3/2), i.e. think about 10? We reach 2/3, the reciprocal of 3/2! Will this always happen? Unfortunately, it won’t. 4/3 would be read as 001, while 100 represents 2/5. Reverse paths may not immediately sound interesting, but I promise you that they are, in some sense.
Palindromic paths are ones that look the same when read in reverse order. Nothing new, just palindromic numbers, but in binary. Antipalindromic paths in this context occur when the inverse of the path of a rational, is the same as the reverse path of that rational. An inverse path of a rational is the bitwise complement of the original path. Can you prove that the inverse path of a rational a/b in this tree, is actually the path corresponding to b/a; its multiplicative inverse?
At this point, some important and interesting questions arise (which we won’t really answer) — relating to the density of palindromes and antipalindromes as we go down the tree. How often do they appear?
Now let’s focus our attention on the numerators, for a bit. The first few numerators, read left to right, are 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4 1 5 4 7 3 8 5 7 2 7 5 8 3 7 4 5 1 6 and so on. It is worth noticing that even though 6 is smaller than 7, it appears later in the list. Such numbers are called latecomers. Can you find some more latecomers for fun? 6 10 12 16 17 are the first five. What’s the next one?
The Calkin-Wilf sequence is the sequence of rational numbers generated by a breadth-first search of the tree. You may visualize it as the following red-spiral going through the vertices of the tree.
The Calkin–Wilf sequence can be generated directly by the following recurrence in which the first number is one. Clearly, this is an enumeration of the positive rationals — and the bijection we need!
Stern’s diatomic sequence, which is closely related to this tree, is given by
The nth rational number appearing in the BFS of the Calkin-Wilf tree is given by the following expression. This gives us a way to assign indices to positive rational numbers, and make sense of expressions such as “the first positive rational number” etc.
To leave you with a non-trivial question — can you find a closed-form expression for the sum of all numbers appearing at a particular depth in the Calkin-Wilf tree? How quickly does this grow with the depth?
At this point, you may wonder that we started off by talking about the countability of the set of all rationals, but ended up with a bijection only for the set of positive rationals? Well, this can easily be “extended” to the set of all rationals with the help of the obvious bijection between integers and natural numbers. Try to construct the final map as a composition of these maps!
Read More:
1. Recounting the Rationals by Neil Calkin, Herbert Wilf
2. Calkin-Wilf Tree by K Siddharth Choudary, A Satyanarayana Reddy
3. Enumerating Trees by Robert Kucharczyk
4. The Calkin-Wilf tree of a quadratic surd by Lionel Ponton
1 is an easy introduction, 2 is the place to look for the proofs of most of the results, while 3 and 4 are somewhat advanced extensions for the motivated reader.
