In mathematics, Minkowski's question-mark function, denoted, is a function with unusual fractal properties, defined by Hermann Minkowski in 1904. 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. It also maps rational numbers to dyadic rationals, as can be seen by a recursive definition closely related to the Stern–Brocot tree.
One way to define the question-mark function involves the correspondence between two different ways of representing fractional numbers using finite or infinite binary sequences. Most familiarly, a string of 0s and 1s with a single point mark ".", like "11.001001000011111..." can be interpreted as the binary representation of a number. In this case this number isThere is a different way of interpreting the same sequence, however, using continued fractions. Interpreting the fractional part "0.001001000011111..." 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
[3;3,1,2,1,4,5,...]
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. For instance, for the example above,
\operatorname{?}(3.2676) ≈ \pi
x
x
x
[a0;a1,a2,...,am]
x
Analogously to the way the question-mark function reinterprets continued fractions as binary numbers, the Cantor function can be understood as reinterpreting ternary numbers as binary numbers.
The question mark is clearly visually self-similar. A monoid of self-similarities may be generated by two operators and acting on the unit square and defined as follows:
Visually, shrinks the unit square to its bottom-left quarter, while performs a point reflection through its center.
A point on the graph of has coordinates for some in the unit interval. Such a point is transformed by and into another point of the graph, because satisfies the following identities for all :
These two operators may be repeatedly combined, forming a monoid. A general element of the monoid is then
for positive integers . Each such element describes a self-similarity of the question-mark function. This monoid is sometimes called the period-doubling monoid, and all period-doubling fractal curves have a self-symmetry described by it (the de Rham curve, of which the question mark is a special case, is a category of such curves). The elements of the monoid are in correspondence with the rationals, by means of the identification of with the continued fraction . Since bothandare linear fractional transformations with integer coefficients, the monoid may be regarded as a subset of the modular group .
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.
0\lex\le1
LC(x)=
x | |
1+x |
RC(x)=
1 | |
2-x |
\circ
LRLLR.
\circ
y=n/2m
y=0.b1b2b3 … bm
bk\in\{0,1\}.
Some notational rearrangements can make the above slightly easier to express. Let
g0
g1
g010=g0g1g0
gAgB=gAB
\gamma\inM
An explicit mapping between the rationals and the dyadic rationals can be obtained providing a reflection operatorand noting that both and
r\circRC\circr=LC
r2=1
a1 | |
L |
a2 | |
rL |
a3 | |
rL |
…
a1 | |
S |
a2 | |
TS |
a3 | |
TS |
…
LD,RD
x=1
y=0.b1b2b3 … bm
bk\in\{0,1\}
LC,RC
x=1
p/q.
p/q=[a1,a2,a3,\ldots,aj]
(a1,a2,a3,\ldots,aj)
Consider now the periodic orbits of the dyadic transformation. These correspond to bit-sequences consisting of a finite initial "chaotic" sequence of bits
b0,b1,b2,\ldots,bk-1
bk,bk+1,bk+2,\ldots,bk+m-1
m
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=[an,an+1,an+2,\ldots,an+r,x].
\alpha,\beta,\gamma,\delta
\alpha\delta-\beta\gamma=\pm1.
T2=I
PSL(2,Z).
Solving explicitly, one has that
\gammax2+(\delta-\alpha)x-\beta=0.
The question-mark function is a strictly increasing and continuous, but not absolutely continuous function. The derivative is defined almost everywhere, and can take on only two values, 0 (its value almost everywhere, including at all rational numbers) and
+infty
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. It maps quadratic irrationals to non-dyadic rational numbers. In both cases it provides an order isomorphism between these sets, making concrete Cantor's isomorphism theorem according to which every two unbounded countable dense linear orders are order-isomorphic. It is an odd function, and satisfies the functional equation ; consequently is an odd periodic function with period one. If is irrational, then is either algebraic of degree greater than two, or transcendental.
The question-mark function has fixed points at 0, and 1, and at least two more, symmetric about the midpoint. One is approximately 0.42037.It was conjectured by Moshchevitin that they were the only 5 fixed points.
In 1943, Raphaël Salem raised the question of whether the Fourier–Stieltjes coefficients of the question-mark function vanish at infinity. In other words, he wanted to know whether or not
This was answered affirmatively by Jordan and Sahlsten, as a special case of a result on Gibbs measures.
The graph of Minkowski question mark function is a special case of fractal curves known as de Rham curves.
The recursive definition naturally lends itself to an algorithm for computing the function to any desired degree of accuracy for any real number, as the following C function demonstrates. The algorithm descends the Stern–Brocot tree in search of the input , and sums the terms of the binary expansion of on the way. As long as the loop invariant remains satisfied there is no need to reduce the fraction, since it is already in lowest terms. Another invariant is . The for
loop in this program may be analyzed somewhat like a while
loop, with the conditional break statements in the first three lines making out the condition. 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. A third invariant for the body of the loop (up to floating point precision) is, but since is halved at the beginning of the loop before any conditions are tested, our conclusion is only that at the termination 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.
Restricting the Minkowski question mark function to ?:[0,1] → [0,1], it can be used as the cumulative distribution function of a singular distribution on the unit interval. 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, 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.