Minkowski's question-mark function

Define two moves: a left move and a right move, valid on the unit interval ${\displaystyle 0\leq x\leq 1}$ as

$${\displaystyle L_{D}(x)={\frac {x}{2}}}$$

and ${\displaystyle L_{C}(x)={\frac {x}{1+x}}}$

and

$${\displaystyle R_{D}(x)={\frac {1+x}{2}}}$$

and ${\displaystyle R_{C}(x)={\frac {1}{2-x}}}$

The question mark function then obeys a left-move symmetry

$${\displaystyle L_{D}\circ {\text{?}}={\text{?}}\circ L_{C}}$$

and a right-move symmetry

$${\displaystyle R_{D}\circ {\text{?}}={\text{?}}\circ R_{C}}$$

where ${\displaystyle \circ }$ denotes function composition. These can be arbitrary concatenated. Consider, for example, the sequence of left-right moves ${\displaystyle LRLLR.}$ Adding the subscripts C and D, and, for clarity, dropping the composition operator ${\displaystyle \circ }$ in all but a few places, one has:

$${\displaystyle 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 ${\displaystyle y=n/2^{m}}$ for integer n and m and as finite length of bits ${\displaystyle y=0.b_{1}b_{2}b_{3}\cdots b_{m}}$ with ${\displaystyle 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 ${\displaystyle g_{0}}$ and ${\displaystyle g_{1}}$ stand for L and R. Function composition extends this to a monoid, in that one can write ${\displaystyle g_{010}=g_{0}g_{1}g_{0}}$ and generally, ${\displaystyle g_{A}g_{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 ${\displaystyle \gamma \in M}$ as a general element of the monoid, there is a corresponding self-symmetry of the question mark function:

$${\displaystyle \gamma _{D}\circ {\text{?}}={\text{?}}\circ \gamma _{C}}$$

An explicit mapping between the rationals and the dyadic rationals can be obtained providing a reflection operator

$${\displaystyle r(x)=1-x}$$

and noting that both

$${\displaystyle r\circ R_{D}\circ r=L_{D}}$$

and ${\displaystyle r\circ R_{C}\circ r=L_{C}}$

Since ${\displaystyle 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 ${\displaystyle L^{a_{1}}rL^{a_{2}}rL^{a_{3}}\cdots }$ which is clearly isomorphic to ${\displaystyle S^{a_{1}}TS^{a_{2}}TS^{a_{3}}\cdots }$ from above. Evaluating some explicit sequence of ${\displaystyle L_{D},R_{D}}$ at the function argument ${\displaystyle x=1}$ gives a dyadic rational; explicitly, it is equal to ${\displaystyle y=0.b_{1}b_{2}b_{3}\cdots b_{m}}$ where each ${\displaystyle 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 ${\displaystyle L_{C},R_{C}}$ moves, evaluated at ${\displaystyle x=1}$ gives a rational number ${\displaystyle p/q.}$ It is explicitly the one provided by the continued fraction ${\displaystyle p/q=[a_{1},a_{2},a_{3},\ldots ,a_{j}]}$ keeping in mind that it is a rational because the sequence ${\displaystyle (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.

Consider now the periodic orbits of the dyadic transformation. These correspond to bit-sequences consisting of a finite initial "chaotic" sequence of bits ${\displaystyle b_{0},b_{1},b_{2},\ldots ,b_{k-1}}$, followed by a repeating string ${\displaystyle b_{k},b_{k+1},b_{k+2},\ldots ,b_{k+m-1}}$ of length ${\displaystyle m}$. Such repeating strings correspond to a rational number. This is easily made explicit. Write

$${\displaystyle y=\sum _{j=0}^{m-1}b_{k+j}2^{-j-1}}$$

one then clearly has

$${\displaystyle \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.

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 ${\displaystyle x=[a_{n},a_{n+1},a_{n+2},\ldots ,a_{n+r},x].}$ This continued fraction has the form[5]

$${\displaystyle x={\frac {\alpha x+\beta }{\gamma x+\delta }}}$$

with the ${\displaystyle \alpha ,\beta ,\gamma ,\delta }$ being integers, and satisfying ${\displaystyle \alpha \delta -\beta \gamma =\pm 1.}$ Explicit values can be obtained by writing

$${\displaystyle S\mapsto {\begin{pmatrix}1&0\\1&1\end{pmatrix}}}$$

for the shift, so that

$${\displaystyle S^{n}\mapsto {\begin{pmatrix}1&0\\n&1\end{pmatrix}}}$$

while the reflection is given by

$${\displaystyle T\mapsto {\begin{pmatrix}-1&1\\0&1\end{pmatrix}}}$$

so that ${\displaystyle T^{2}=I}$. Both of these matrices are unimodular, arbitrary products remain unimodular, and result in a matrix of the form

$${\displaystyle 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 ${\displaystyle PSL(2,\mathbb {Z} ).}$

Solving explicitly, one has that ${\displaystyle \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.