Today I’d like to continue my exposition of the paper “Recounting the Rationals”, which I introduced in a previous post. Recall that our goal is to come up with a “nice” list of the positive rational numbers — where by a “nice” list we mean one which:
- is easy to describe,
- includes every rational number,
- exactly once,
- in lowest terms,
- at a finite index.
Sounds like a pretty tall order! But it’s possible, as Calkin and Wilf show. So, without further ado… did you know that fractions grow on trees? Sure they do! Here’s one:
The Calkin-Wilf Tree
This is a tree of fractions defined by the following simple rules:
- The fraction at the top (the “root”) of the tree is 1/1.
- Each fraction
in the tree has two “children” (that is, fractions underneath it connected by “branches”): to the left is
; to the right is
.
For example, starting at the top of the tree, we have 
Pretty simple, right? The picture above only shows the first four levels of the tree, but it’s clear how to continue extending the tree downwards as far as you’d like (for example, the first two rationals on the next level are 1/5 and 5/4). Now, guess what?
- Every positive rational number occurs somewhere in this tree.
- There are no duplicates: each rational occurs exactly once.
- Every rational in the tree is in lowest terms.
- If you list out the rationals in this tree in order by level (that is, 1/1, 1/2, 2/1, 1/3, 3/2, 2/3, 3/1, 1/4…), the denominator of each rational in the list is equal to the numerator of the next.
- The nth integer in the list of denominators (1, 2, 1, 3, 2, 3, 1, 4, 3, 5, …) is the number of hyperbinary representations of n, that is, the number of ways to write n as a sum of powers of two, where at most two copies of each power of two are allowed.
Wow! What an amazing tree. And all that just from those two simple rules! It should be clear that this is an answer to our original goal: just listing the rationals in the tree level-by-level gives us a list of the positive rationals with all the properties we were hoping for. But there’s a lot more interesting stuff here as well. Next time I’ll start talking about why each of these properties is true — but in the meantime, you may want to try figuring some of them out for yourself! They are all consequences of the two simple rules we used to define the tree.
(Hint for #1, #2, and #3: rule 2 tells us how to move down the tree, but with a little cleverness, you should be able to figure out how to move up the tree as well. For example, assuming that 43/19 occurs somewhere in the tree, rule 2 tells us that 43/62 and 62/19 are below it; but can you figure out what fraction must be above it?)
The Math Less Traveled 
fascinating… I wonder if we could start with a different fraction, a different rule #2 and still come up with the whole tree (it doesn’t seem possible at the onset). I also wonder about the negatives… and zero and if they can be ‘treed’
mathercize, excellent questions! You can actually quite easily include zero by placing 0/1 above and to the left of 1/1 — then 1/1 follows from 0/1 by rule 2, although left of 0/1 would be… 0/1 again! To get the negatives you could just flip the sign of everything in the tree (changing the rules appropriately), although I’m not sure whether there’s a different way it could be done.
As for coming up with all the positive rationals in a tree with a different starting fraction and a different rule… I don’t know! It’s a great question. I suspect, as you do, that it isn’t possible, but I’m not sure how one would go about trying to prove it.
I recall learning that using “i” as a variable is a no-no….
People use “i” as a variable all the time. Telling students that using “i” as a variable is a no-no is sort of like telling kids that they’re not allowed to play on the swings unless an adult is around. Is it well-intentioned? Sure, kids really can get hurt on the swings, and maybe when they’re first learning about complex numbers they could be confused by “i” sometimes meaning sqrt(-1) and sometimes being just a variable. But after a certain age/maturity level it just becomes a silly and restrictive rule.
OT: Happy birthday! Too bad 26 isn’t as interesting a number as 25.
Thanks! =)
Pingback: Ars Mathematica » Blog Archive » 24th Carnival of Mathematics
What a great post! Thanks for sharing this — this general topic has come up in classes in the past (usually related to the countability of the rationals) but I hadn’t ever seen this tree, and I’m looking forward to playing around with it.
Hi, good post. I find this subject fascinating and I invite you to read about the Stern-Brocot tree, as well. As a matter of fact, I’ve co-authored a very recent paper (currently for submission) where we present a more general tree that “contains” both Calkin-Wilf and Stern-Brocot trees. If you are interested, you can fetch the paper at:
Click to access RecountingRationalsTwice.pdf
(For me, the most fascinating fact about Calkin-Wilf order is that you can iterate the rationals by keeping as state a single rational, i.e., from the current rational you can determine the next one! Isn’t that great?)
Cheers,
Joao
Hi Joao,
Yes, I am familiar with the Stern-Brocot tree (I encountered it in a number theory class and later in “Concrete Mathematics”). Your paper looks very interesting, I look forward to reading it! Complete with a Haskell implementation, excellent! =) (I am active in the Haskell community — you can find me as byorgey in the #haskell IRC channel, and on my other blog.)
Thanks for reminding me about being able to generate the Calkin-Wilf order with just a single rational as state! It’s very cool indeed. That’s from Gibbons et. al., right? Perhaps I will write about it on this blog once I finish writing about properties of the Calkin-Wilf tree.
Dear Brent,
Gibbons et. al. mention the enumeration in C.W. order using one rational as state, but the original idea is from Mosche Newman (it was published in the American Mathematical Monthly; see the references in our paper for details).
By the way, the most important aspect of our paper is the emphasis on construction. In other words, if you were the first mathematician in the world trying to enumerate the rationals, how would you do it? First: what is a rational? Answer: A pair of coprime numbers. And if co-primality is the important bit, then the greatest common divisor must be involved. So, maybe, we can extend Euclid’s algorithm. And so on… 🙂
Pingback: Math in the News: Infinities « 360
This comment is quite late, but I’m coming back to this series because I want to present this tree to my class tomorrow.
Anyway, in response to the comments on not using “i” as a variable — personally I avoid using it if I expect I’m going to have to deal with complex numbers, for example if I’m doing a computation involving the asymptotics of generating functions. (Most of the tools for that come from complex analysis.) But otherwise, it seems silly to avoid i as a blanket rule.
I do almost always avoid using e to mean anything other than 2.718…, though.
Conway’s, _On_Numbers_And_Games_, covers a variant of this approach in great detail. However, I’m stumped at how a tree can be considered a list? To include all the fractionals, it becomes infinite and I have no clear starting point to “flatten” the tree into a list. Given a target in the tree it can be found quite easily, but it’s not the category of a list, it’s in the category of a tree. This works if the term list is being used loosely.
Hi Shawn,
I’ve read the first few chapters of ONAG, and the construction that yields the surreal numbers is actually not the same as the Calkin-Wilf tree (compare them closely and you’ll see the difference — for example, note that 2/3 shows up on the third level of the C-W tree, but has birthday omega as a surreal number).
I’m not using the term “list” loosely at all. To flatten the Calkin-Wilf tree into a list, you can just read it level-by-level, going from left to right across each level. In this way, every element at a finite depth in the tree ends up at a finite position in the list. You can convert directly between location in the tree and location in the list by reading the series of lefts and rights taken from the root to the element as a binary number — I plan to write more about that soon!
A comment at 360 alerted me to this post. What a nice treatment! Thanks for writing it up.
I spent some productive time thinking about the relationships between Pascal’s triangle and the earlier list of fractions. I posed some questions at the mathfest wiki.
Pingback: Challenge #12 solution, part II « The Math Less Traveled
I’ve just started reading this series and it’s really interesting so far. My notes:
* If you pick a node of the tree you can tell if it was a left or right branch by comparing numerator and denominator. If n<d then left, if n>d then right (and except for 1/1, n never equals d).
* Subtracting whichever is smaller from whichever is larger gives the parent fraction.
* Repeating this process gets you eventually back to 1/1.
* The above process of repeated subtraction is equivalent to to performing Euclid’s algorithm for finding greatest common divisor on the n and d. It always ends with 1/1, so the GCD is 1; so in every case n and d are coprime; thus all in lowest terms! (that’s #3)
* As for #1: Let q be a positive rational number. Express q in lowest terms. Then its numerator and denominator are coprime. Perform the above reverse-tree-walk process process above on it and you will finish up at 1/1, since you are doing the euclidean algorithm on a pair of coprime numbers. Thus there is a route going from q, up the tree, to 1/1. Reversing this gives you a route from 1/1 to q. So q is in the tree.
* #3: Let a positive rational number q appear in two places in the tree. Then working upwards from each position, the paths will be identical. Being a tree, these identical paths will meet at some node. But each node has different children, so this is impossible. So q can only appear in one place.
Thanks for doing this. I’m looking forward to reading the rest.
Nick: glad you’re finding it interesting, and good work so far!
Pingback: The hyperbinary sequence and the Calkin-Wilf tree | The Math Less Traveled
Pingback: Recounting the Rationals, part III | The Math Less Traveled
Pingback: Math Shirt | Calkin-Wilf Tree | The Nerdiest Shirts