Minkowski's question-mark function

(x), is a function with unusual fractal properties, defined by Hermann Minkowski in 1904.

[1] It maps quadratic irrational numbers to rational numbers on the unit interval, via an expression relating the continued fraction expansions of the quadratics to the binary expansions of the rationals, given by Arnaud Denjoy in 1938.

Interpreting the fractional part "0.00100100001111110..." as a binary number in the same way, replace each consecutive block of 0's or 1's by its run length (or, for the first block of zeroes, its run length plus one), in this case generating the sequence

The question-mark function reverses this process: it translates the continued-fraction of a given real number into a run-length encoded binary sequence, and then reinterprets that sequence as a binary number.

is represented by a periodic continued fraction, so the value of the question-mark function on

A monoid of self-similarities may be generated by two operators S and R acting on the unit square and defined as follows:

Visually, S shrinks the unit square to its bottom-left quarter, while R performs a point reflection through its center.

The elements of the monoid are in correspondence with the rationals, by means of the identification of a1, a2, a3, … with the continued fraction [0; a1, a2, a3,…].

are linear fractional transformations with integer coefficients, the monoid may be regarded as a subset of the modular group PSL(2, Z).

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.

Adding the subscripts C and D, and, for clarity, dropping the composition operator

Thus, every dyadic rational is in one-to-one correspondence with some self-symmetry of the question mark function.

as a general element of the monoid, there is a corresponding self-symmetry of the question mark function:

These correspond to bit-sequences consisting of a finite initial "chaotic" sequence of bits

In fact, every rational number can be expressed in this way: an initial "random" sequence, followed by a cycling repeat.

There is an initial "chaotic" orbit, of some finite length, followed by a repeating sequence.

The repeating sequence generates a periodic continued fraction satisfying

It is not hard to verify that the solutions to this meet the definition of quadratic irrationals.

The question mark function provides the correspondence in each case.

The question-mark function maps rational numbers to dyadic rational numbers, meaning those whose base two representation terminates, as may be proven by induction from the recursive construction outlined above.

In both cases it provides an order isomorphism between these sets,[8] making concrete Cantor's isomorphism theorem according to which every two unbounded countable dense linear orders are order-isomorphic.

[10] In 1943, Raphaël Salem raised the question of whether the Fourier–Stieltjes coefficients of the question-mark function vanish at infinity.

This was answered affirmatively by Jordan and Sahlsten, as a special case of a result on Gibbs measures.

The algorithm descends the Stern–Brocot tree in search of the input x, and sums the terms of the binary expansion of y = ?

As long as the loop invariant qr − ps = 1 remains satisfied there is no need to reduce the fraction ⁠m/n⁠ = ⁠p + r/q + s⁠, since it is already in lowest terms.

The only statements in the loop that can possibly affect the invariants are in the last two lines, and these can be shown to preserve the truth of both invariants as long as the first three lines have executed successfully without breaking out of the loop.

To prove termination, it is sufficient to note that the sum q + s increases by at least 1 with every iteration of the loop, and that the loop will terminate when this sum is too large to be represented in the primitive C data type long.

However, in practice, the conditional break when y + d == y is what ensures the termination of the loop in a reasonable amount of time.

This distribution is symmetric about its midpoint, with raw moments of about m1 = 0.5, m2 = 0.290926, m3 = 0.186389 and m4 = 0.126992,[13] and so a mean and median of 0.5, a standard deviation of about 0.2023, a skewness of 0, and an excess kurtosis about −1.147.