The question mark function provides a one-to-one mapping from the non-dyadic rationals to the
quadratic irrationals, thus allowing an explicit proof of countability of the latter. These can, in fact, be understood to correspond to the
periodic orbits for the
dyadic transformation. This can be explicitly demonstrated in just a few steps.
Dyadic symmetry Define two moves: a left move and a right move, valid on the
unit interval 0\le x\le 1 as L_D(x) = \frac{x}{2} and L_C(x) = \frac{x}{1+x} and R_D(x) = \frac{1+x}{2} and R_C(x) = \frac{1}{2-x} The question mark function then obeys a left-move symmetry L_D \circ \text{?} = \text{?} \circ L_C and a right-move symmetry R_D \circ \text{?} = \text{?} \circ R_C where \circ denotes
function composition. These can be arbitrarily concatenated. Consider, for example, the sequence of left-right moves LRLLR. Adding the subscripts C and D, and, for clarity, dropping the composition operator \circ in all but a few places, one has: L_D R_D L_D L_D R_D \circ \text{?} = \text{?} \circ L_C R_C L_C L_C R_C Arbitrary finite-length strings in the letters L and R correspond to the
dyadic rationals, in that every dyadic rational can be written as both y=n/2^m for integer
n and
m and as finite length of bits y=0.b_1b_2b_3\cdots b_m with b_k\in \{0,1\}. Thus, every dyadic rational is in one-to-one correspondence with some self-symmetry of the question mark function. Some notational rearrangements can make the above slightly easier to express. Let g_0 and g_1 stand for L and R. Function composition extends this to a
monoid, in that one can write g_{010}=g_0g_1g_0 and generally, g_Ag_B=g_{AB} for some binary strings of digits
A,
B, where
AB is just the ordinary
concatenation of such strings. The dyadic monoid
M is then the monoid of all such finite-length left-right moves. Writing \gamma\in M as a general element of the monoid, there is a corresponding self-symmetry of the question mark function: \gamma_D\circ \text{?} = \text{?}\circ \gamma_C
Isomorphism An explicit mapping between the rationals and the dyadic rationals can be obtained providing a reflection operator r(x)=1-x and noting that both r\circ R_D\circ r = L_D and r\circ R_C\circ r = L_C Since r^2=1 is the
identity, an arbitrary string of left-right moves can be re-written as a string of left moves only, followed by a reflection, followed by more left moves, a reflection, and so on, that is, as L^{a_1}rL^{a_2}rL^{a_3}\cdots which is clearly isomorphic to S^{a_1}TS^{a_2}TS^{a_3}\cdots from above. Evaluating some explicit sequence of L_D,R_D at the function argument x=1 gives a dyadic rational; explicitly, it is equal to y=0.b_1b_2b_3\cdots b_m where each b_k\in\{0,1\} is a binary bit, zero corresponding to a left move and one corresponding to a right move. The equivalent sequence of L_C,R_C moves, evaluated at x=1 gives a rational number p/q. It is explicitly the one provided by the continued fraction p/q=[a_1,a_2,a_3,\ldots,a_j] keeping in mind that it is a rational because the sequence (a_1,a_2,a_3,\ldots,a_j) was of finite length. This establishes a one-to-one correspondence between the dyadic rationals and the rationals.
Periodic orbits of the dyadic transform Consider now the
periodic orbits of the
dyadic transformation. These correspond to bit-sequences consisting of a finite initial "chaotic" sequence of bits b_0,b_1,b_2,\ldots, b_{k-1}, followed by a repeating string b_k,b_{k+1},b_{k+2},\ldots, b_{k+m-1} of length m. Such repeating strings correspond to a rational number. This is easily made explicit. Write y=\sum_{j=0}^{m-1} b_{k+j}2^{-j-1} one then clearly has \sum_{j=0}^\infty b_{k+j}2^{-j-1} = y\sum_{j=0}^\infty 2^{-jm} = \frac{y}{1-2^m} Tacking on the initial non-repeating sequence, one clearly has a rational number. In fact,
every rational number can be expressed in this way: an initial "random" sequence, followed by a cycling repeat. That is, the periodic orbits of the map are in one-to-one correspondence with the rationals.
Periodic orbits as continued fractions Such periodic orbits have an equivalent periodic continued fraction, per the isomorphism established above. There is an initial "chaotic" orbit, of some finite length, followed by a repeating sequence. The repeating sequence generates a
periodic continued fraction satisfying x=[a_n,a_{n+1},a_{n+2},\ldots,a_{n+r},x]. This continued fraction has the form x = \frac{\alpha x+\beta}{\gamma x+\delta} with the \alpha,\beta,\gamma,\delta being integers, and satisfying \alpha \delta-\beta \gamma=\pm 1. Explicit values can be obtained by writing S\mapsto \begin{pmatrix} 1 & 0\\ 1 & 1\end{pmatrix} for the shift, so that S^n\mapsto \begin{pmatrix} 1 & 0\\ n & 1\end{pmatrix} while the reflection is given by T\mapsto \begin{pmatrix} -1 & 1\\ 0 & 1\end{pmatrix} so that T^2=I. Both of these matrices are
unimodular, arbitrary products remain unimodular, and result in a matrix of the form S^{a_n}TS^{a_{n+1}}T\cdots TS^{a_{n+r}} = \begin{pmatrix} \alpha & \beta\\ \gamma & \delta\end{pmatrix} giving the precise value of the continued fraction. As all of the matrix entries are integers, this matrix belongs to the projective
modular group PSL(2,\mathbb{Z}). Solving explicitly, one has that \gamma x^2 + (\delta-\alpha)x-\beta=0. It is not hard to verify that the solutions to this meet the definition of quadratic irrationals. In fact, every quadratic irrational can be expressed in this way. Thus the quadratic irrationals are in one-to-one correspondence with the periodic orbits of the dyadic transform, which are in one-to-one correspondence with the (non-dyadic) rationals, which are in one-to-one correspondence with the dyadic rationals. The question mark function provides the correspondence in each case. ==Properties of ==