Posted by: dschadewald | November 24, 2008

## Reading Project: Recounting the Rationals

Recounting the Rationals

It might sound crazy, but there actually is a way to count up all the rational numbers.  When I read this, I first tried to come up with my own method for counting the rational numbers.  The method that I at first came up with (and this is actually not included in the paper at all since it is a very poor method J) went something like this:

1, 2, ½, 3, 1/3, 2/3, 4, ¼, 2/4, ¾, 5, 1/5, 2/5, 3/5, 4/5, 6…

This method makes sense, but contains many errors.  For one, certain numbers are counted more than once.  In the list above, we can already see that ½ is counted twice.  Each denominator that is NOT prime will end up containing a number of fractions that are being double counted.  The fractions that are double counted are the ones whose numerators are NOT relatively prime with the denominator (meaning that they share a common factor). For instance, with the denominator 12, the fractions containing the numerators 2, 3, 4, 6, 8, 9, 10 will all have occurred earlier and are thus being double counted.  The number of fractions that are double counted can be calculated if a number has just two different prime factors: n, q, and is equal to n+q-2.  This actually came up in one of the exploratory problems earlier (the one worth 6 points), except we subtract 2 now because we have already counted n*q/(n*q), or the number 1.  For other numbers, it becomes increasingly complicated to calculate which fractions are being double counted and thus this method (created by me) does a very poor job of counting all the rational numbers.  Furthermore, in this list, a number like 1.25 is not counted.  Only the whole numbers and the fractions below 1.

This paper, on the other hand, shows a remarkably better way of counting all the rationals.  First it provides a list of all the rational numbers and shows how it is calculated, and then it comes up with a method that explains why this is true.  The contribution of this paper is not the list of rational numbers (this was actually discovered in a previous paper), but another method for discovering how this list is created and why this makes sense.

The list of positive rational numbers looks as follows:

$\frac{1}{1}, \frac{1}{2}, \frac{2}{1}, \frac{1}{3}, \frac{3}{2}, \frac{2}{3}, \frac{3}{1}, \frac{1}{4}, \frac{4}{3}, \frac{3}{5}, \frac{5}{2}, \frac{2}{5}, \frac{5}{3}, \frac{3}{4}, \frac{4}{1}, \frac{1}{5}, \frac{5}{4}, \frac{4}{7}, \frac{7}{3}, \frac{3}{8}, \frac{8}{5}, \frac{5}{7}, \frac{7}{2}, \frac{2}{7},$

This list looks extremely confusing and the numbers in the list seem arbitrary.  However, this list is constructed using a sequence b(n) and having each number in the above sequence be equal to b(n)/b(n+1).  This means that the denominator of one element will be the numerator of the subsequent element of the sequence.  If we look above, we see that the sequence of b(n) (starting at b(0)) is {1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, 1, 5, 4, 7, …}  This sequence looks very strange at first glance, but after inspection we can see that it actually counts something.  In fact, b(n) is just equal to the number of ways that you can write the number n as a sum of the powers of 2, with each power of two being used at most twice.  A few examples will make this much more clear:

5 = 4 +1 = 22 + 20 ,  5 = 2 + 2 + 1 = 21 + 21 + 20   Thus b(5) is equal to 2.

7 = 4 + 2 + 1 = 22 +21 + 20,  Also, 7 = 2 + 2 + 2 + 1, but this is not valid since we are using 21 more than the limit of 2 times.  Thus b(7) is equal to 1.

This paper denotes the function b(n) as the number of hyperbinary representations of the integer n.   A very nice feature of this sequence is that consecutive values of b(n) are relatively prime, thereby eliminating the possibility of double counting since each rational number is in its reduced form in the list.

The paper’s biggest contribution, however, is what the authors call the “tree of fractions.”  Unfortunately, I cannot find a way to get this tree on the blog, so to see it you will have to go to:  http://isites.harvard.edu/fs/docs/icb.topic446960.files/Calkin%20Wilf%20-%20Recounting%20the%20rationals.pdf

For those of you who don’t want to click on the link, I will try my best to describe the tree.  First, start with the fraction 1/1 at the top of the tree.  The numerator, in this case 1, is called ‘i’ and the denominator, in this case 1 again, is called ‘j’.  Then, the tree has two “children”: the left one is i/(j+i) and the right one is (i+j)/j.  These are 1/2 and 2/1 respectively.  Then, continuing on this pattern, the “children” of 1/2 are 1/3 and 3/2 while “children” of 2/1 are 2/3 and 3/1.  This tree, like the list, has some interesting features.  To begin with, the numerator and denominator of each child are relatively prime.  Furthermore, every reduced rational number will then occur at each child, since the numbers are relatively prime with one another and therefore there will be no repeats.

To reconstruct the list of numbers written earlier, we simply need to read the tree from top down and read each child from left to right. This makes sense, because like in the list, the denominator of one child will be the numerator of the successor.  This is because the denominator on the left child is (i+j) and the numerator of the right child is (i+j).  Then, we can see that the list created by the tree will be of the form f(n)/f(n+1) for some f.  As it turns out, f(n) are actually creates the same list as b(n) and thus at the end of the paper, the authors come up with the theorem:

The nth rational number, in reduced form, can be taken to be b(n)/b(n+1), where b(n) is the number of hyperbinary representations of the integer n, for n = 0, 1, 2, . . .   That is, b(n) and b(n+1) are relatively prime, and each positive reduced rational number occurs once and only once in the list b(0)/b(1), b(1)/b(2), . . .

In all seriousness, I am not quite sure how this question relates directly with Math 152.  It fits in with the counting we did very early in the class, but beyond that it does not directly relate to a topic we have covered.  The construction of the list, however, does remind me a little bit of the concept of the order of an element since it uses powers of two to construct a number.  Beyond that, however, it seems a little bit unrelated to the course.

I found this paper extremely interesting to be honest.  I never actually thought much about how to count all the rational numbers, because the method that I had always thought of (see earlier) has so many problems with it.  This method of counting discussed/uncovered in this paper is remarkable and makes little mathematical sense.  There seems to be no correlation between the hyperbinary representations of an integer n, and a method for constructing a list of all the rational numbers.   This, however, is what mathematics is all about, finding relationships and symmetries between two seemingly unlike things.  It is simply amazing that one strange and seemingly worthless list of numbers can be used to generate a list of all the rational numbers.

## Responses

1. If this is the sequence I think it is, it appeared as a Putnam problem in 2002. This counting makes much more sense if you split it up into two steps:

– Convert a binary string into a finite list of positive integers. For example, you can take the list of lengths of repeated strings of 1s. This is closely related to hyperbinary representation.

– Convert that list into a continued fraction.

Both operations are bijections, so their composition – which is this very mysterious sequence – is also a bijection.

2. I’m very pleased you started off the paper with your own investigations. That’s doing mathematics, even if it didn’t end up in the author’s published article! Sometimes you learn a lot more from things that don’t work than things that do. And I agree with you, the topic is fascinating. A good place to look up sequences and find out about them is Sloane’s On-Line Encyclopedia of Integer Sequences. Here’s the sequence:

http://www.research.att.com/~njas/sequences/A002487

There are many other ways to count the rationals too, but I don’t know any that are as nice as this — it automatically avoids repeats and the n-th term can be computed without first computing all the earlier ones.

You will find the Farey sequence very interesting and you should look this up on Wikipedia, PlanetMath or Cut the Knot as a study break. Also look up Ford circles. The Farey sequence is another way to count rationals in a sort of “tree” and it has a fascinating geometric meaning (the Ford circles).