Posts Tagged ‘stern brocot tree’


November 11, 2009

Yesterday I talked about the function ?(x). If you recall (or rather, if you don’t… if you do recall, you can probably skip to the next paragraph), I defined this function by lining up two infinite binary trees. One tree was obtained by taking mediants, giving us the Stern-Brocot tree, while the other was obtained by taking midpoints, giving us a tree of “dyadic” fractions (denominators are powers of two). To evaluate ?(x), you find x in the Stern-Brocot tree, and then ?(x) is the value in the corresponding position of the dyadic tree.

Instead of thinking about infinite binary trees, let us think about cutting each tree off at some level, n. The pictures from yesterday’s post are, if you ignore the vertical dots, the trees when n=2. In the dyadic tree, we will obtain all fractions m/2^p where 0<m<2^p is odd and 1\leq p\leq n+1. Said another way, we will get all of the values m/2^{n+1} where 0<m<2^{n+1} (not necessarily odd anymore). If you think about it for a few moments, you’ll notice that these points are equally spaced in the interval, each being 1/2^{n+1} away from its neighbors. This is not the case for the Stern-Brocot tree.

In the truncated Stern-Brocot tree, points are scattered through the interval (0,1). We can see that they are scattered in a way that is symmetric around 1/2, but what else can we say? Think about choosing some number, b, of buckets, call them B_0,\ldots,B_{b-1}. Let B_i collect all of the points from the truncated Stern-Brocot tree whose value lies between i/b and (i+1)/b. Of course, I’m being a little loose with my endpoints, but hopefully the idea comes across. If you choose an appropriate number of buckets, depending on the depth of your truncated tree, you can arrange that no point is an endpoint of a bucket’s interval.

Anyway, when you’re done with that, count how many points are in each bucket. This defines a function from the interval [0,1] to non-negative integers, where the value at all points in B_i is the count of the number of Stern-Brocot points in the bucket B_i. Here’s an example graph, obtained by taking the depth 10 Stern-Brocot tree, and putting points into 59 buckets (unless I coded something up wrong :)):

You could next scale this graph vertically by a constant so that the total area of all of the rectangles is 1. That is, you could make the graph that of a probability distribution. Of course, the distribution you get will depend on not ony the depth of the tree, but also how many buckets you choose. Since I’m only vaguely sure what I’m talking about, let me not say much more about that.

A less graphical way to think about all of this is that, for each n, I define two random variables X_n and Y_n. The first, X_n picks a value from all of the nodes in the Stern-Brocot tree of depth n, assuming each is equally likely. The second is basically the same, using the dyadic tree instead. I’m not particularly well-versed in probability, but I guess you are allowed to take the limit of these probability distributions, let’s say X=\lim X_n, and similarly Y=\lim Y_n. This defines two probability functions on the interval [0,1] (well, I suppose technically it probably defines a probability function on the rationals there…).

How are the two distributions related? Well, basically the same way as the trees are related by ?(x). In particular, we have

P(a\leq X\leq b)=P(?(a)\leq Y\leq ?(b))

Since Y is just the uniform distribution (the dyadic points are equally distributed, recall), the probability on the right is just ?(b)-?(a). Let \mu be the graph of the probability function for X, so that the probability on the left is the integral \int_a^b \mu\ dx. We have, then

\displaystyle \int_a^b \mu(x)\ dx=?(b)-?(a)

This looks so much like the fundamental theorem of calculus that we want to say that ?'(x)=\mu(x). You could also read it as saying that ?(x) is the cumulative distribution function of \mu(x). Thinking back to my buckets from earlier, this means that if I define the value over the interval covered by B_i to be the sum of the counts of all the values in all the buckets up to B_i, then I should get a graph that looks like ?(x). You be the judge:

Of course, we probably aren’t exactly allowed to say ?'(x)=\mu(x). Consider the rational s/t, and suppose that ?'(s/t) exists, i.e., that

\displaystyle\lim_{x\to s/t}\dfrac{?(x)-?(s/t)}{x-s/t}

exists. If this two sided limit exists, then we can calculate it by coming at it from either side. Let’s think about x\to s/t^+, that is, from the right. But let’s simplify some more, still. If the one-sided limit exists, then we can calculate it by calculating the limit of the difference quotient for any sequence of values x converging to s/t. The sequence of values, on the right of s/t, that I want to consider are those neighbors, on the right, of s/t, in the Stern-Brocot sequences.

Let’s say that the first neighbor is the right child of s/t in the Stern-Brocot tree, and call it p/q. Then all of the successive neighbors are the successive left children of p/q. These points are all of the points (ms+p)/(mt+q), for positive values m. If we let m\to \infty, these weighted mediants converge to s/t.

So let’s consider the following:


Let’s start simplifying in the denominator. That fraction is (pt-sq)/(t(mt+q)), but since p/q and s/t are neighbors in some Farey sequence, this difference is 1. So the denominator is 1/(t(mt+q)).

In the numerator, we are evaluating ?(x) at weighted mediants of s/t and p/q. The corresponding ?(x) values are then weighted averages. Playing with the formulas a little bit, you can determine that


Combining all of the formulas so far, and simplifying, it turns out that the limit we are after is just

\displaystyle\lim_{m\to\infty}\left(?(p/q)-?(s/t)\right)\cdot t\cdot (mt+q)\cdot 2^{-m}

Of course, that power of two wins the race to infinity, and so this limit is 0.

We have shown then, that if ?'(p/q) exists, then it is 0. Since ?(x) isn’t a constant graph, we better have ?'(x) non-zero on the irrationals. Perhaps I’ll leave that to you.

I should, of course, mention that I learned about this reading the paper “On the Minkowski measure” by Linas Vepstas, available online here (along with a handful of other papers that look fun). Hopefully I haven’t mangled anything too badly.


Hardy and Wright, Chapter 3

March 28, 2009

Well, somewhat surprisingly, my little reading group hasn’t yet disbanded entirely. Last week we had a great discussion about chapter 2 of H&W, which put us in chapter 3 for this week.

Chris commented that one of the more interesting things, for him, in this chapter was that people would actually be interested in proving things about sequences of reduced fractions with bounded denominator (the Farey sequences that start the chapter). I rather enjoyed playing with them and reading about them. My understanding is that they are useful for starting to get bounds on approximating irrationals by rationals, a topic which I’m fairly certain we will return to. I also was glad to see a proof of Minkowski’s theorem about symmetric regions with large area containing lattice points. I think I’d heard the result before, but it’s always nice to see (and be able to follow!) a proof.

I was a little confused about when a mediant is reduced. I thought that the mediant of reduced fractions was reduced. For any three consecutive terms of a Farey sequence, the middle is the mediant of the other two. There is a footnote stating that the middle term might be the reduced form of the mediant. Why would you need this footnote, if mediants are already reduced? Chris pointed out that in the Farey sequence with denominator no larger than 3 (denote if F_3), 1/3, 1/2, 2/3 are consecutive terms, but the middle is the reduced mediant of the outer terms. All the text claims is that the first time a term shows up, it is the reduced mediant of its neighbors. Clearly mediants of reduced fractions aren’t, necessarily, reduced. Eric and I were frequently embarrased by things we thought were true during this meeting, and I pointed out that this was exactly why I wanted to read about these things: I don’t work with integers too much 🙂

Eric wondered about the fact that the distance between two consecutive terms h/k and h'/k' in a Farey sequence is 1/(kk'). Chris and I noted that this was obvious from the lemma that kh'-hk'=1. Eric was wondering, though, if one could determine it without that lemma somehow. We didn’t come up with much.

I presented the answer I had found to the question I had asked myself: “For h/n in F_n, can you find the first n'>n for which h/n has a new successor in F_{n'}? What can you say about the sequence of all such n'?” The book has a lemma about how to find the next term for h/n in F_n. Suppose that its successor is h'/k'. By other lemmas in this chapter, the next time something comes between these terms, it will be the mediant, \frac{h+h'}{n+k'}, and this occurs in F_{n+k'}. The next time h/n will have a new successor, it will be the mediant of h/n with this new term, \frac{h+h'}{n+k'}, and so will be \frac{2h+h'}{2n+k'}. Continuing on, we see that h/n has a new successor in the Farey sequences F_{m\cdot n+k'}.

Next, I talked about the Stern-Brocot Tree and Minkowski’s Question Mark function, ?(x). We had mentioned in our meeting that the terms of the Farey sequence are not equally distributed, and I pointed out that there was some relation between that and how ‘wobbly’ ?(x)-x is. Notice that the Farey sequences are least dense around 1/2, and most dense around 0 and 1, which relates well to the wobbliness of the graph of ?(x)-x. This has something to do with defining an appropriate measure so that ?(x) is the integral (of… something. 1? x?) with respect to this measure. At least, that’s what I gathered from Wikipedia. I’d like to read more about this.

Also, Eric and I had both noticed the comment on the Wikipedia page that there is a relation between Farey sequences and the Riemann hypothesis, which we found pretty intriguing. Of course, neither of us knew much about it. Perhaps a topic for another day. It seems to be related to the density, or perhaps distribution is more accurate, of the terms of Farey sequences in the interval [0,1].

I completely forgot to bring up Ford circles. If you put circles of appropriate sizes above the points in a Farey sequence, you get lots of nice tangent circles, with fun properties. Perhaps the property most relevant to this section is that any circles tangent to the circle above p/q are centered at x-coordinates that are neighbors of p/q in some Farey sequence.