Tag Archives: Diophantine approximation

The Stern-Brocot tree, Hurwitz’s theorem, and the Markoff uniqueness conjecture

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.

Continue reading →

Real Numbers and Infinite Games, Part II

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 {\mathbf R} is uncountable.  There is a similar game which can be used to prove the Baire Category Theorem.  Let X be a metric space.   In Choquet’s game, Alice moves first by choosing a non-empty open set U_1 in X.  Then Bob moves by choosing a non-empty open set V_1 \subseteq U_1.  Alice then chooses a non-empty open set U_2 \subseteq V_1, and so on, yielding two decreasing sequences U_n and V_n of non-empty open sets with U_n \supseteq V_n \supseteq U_{n+1} for all n.  Note that \bigcap U_n = \bigcap V_n; we denote this set by U.  Alice wins if U is empty, and Bob wins if U is non-empty. Continue reading →