My goal in this post is to describe a surprising and beautiful method (the Stern-Brocot tree) for generating all positive reduced fractions. I’ll then discuss how properties of the tree yield a simple, direct proof of a famous result in Diophantine approximation due to Hurwitz. Finally, I’ll discuss how improvements to Hurwitz’s theorem led Markoff to define another tree with some mysterious (and partly conjectural) similarities to the Stern-Brocot tree.
In my last post, I wrote about two infinite games whose analysis leads to interesting questions about subsets of the real numbers. In this post, I will talk about two more infinite games, one related to the Baire Category Theorem and one to Diophantine approximation. I’ll then talk about the role which such Diophantine approximation questions play in the theory of dynamical systems.
The Choquet game and the Baire Category Theorem
The Cantor game from Part I of this post can be used to prove that every perfect subset of is uncountable. There is a similar game which can be used to prove the Baire Category Theorem. Let be a metric space. In Choquet’s game, Alice moves first by choosing a non-empty open set in . Then Bob moves by choosing a non-empty open set . Alice then chooses a non-empty open set , and so on, yielding two decreasing sequences and of non-empty open sets with for all . Note that ; we denote this set by . Alice wins if is empty, and Bob wins if is non-empty. Continue reading