Minkowski's question mark function

From Wikipedia, the free encyclopedia

Minkowski question mark function
Enlarge
Minkowski question mark function

In mathematics, the Minkowski question mark function, sometimes called the slippery devil's staircase, is a function, denoted ?(x), possessing various unusual fractal properties. It was defined by Hermann Minkowski in 1904 by matching the quadratic irrationals to the dyadic rationals on the unit interval. The expression relating continued fractions to the dyadics (as commonly used, and defined below) was given by Arnaud Denjoy in 1938.

Contents

[edit] Definition

If [a_0; a_1, a_2, \ldots] is the continued fraction representation of an irrational number x, then

{\rm ?}(x) = a_0 + 2 \sum_{n=1}^\infty \frac{(-1)^{n+1}}{2^{a_1 + \cdots + a_n}}

whereas:

If [a_0; a_1, a_2, \ldots, a_m] is a continued fraction representation of a rational number x, then

{\rm ?}(x) = a_0 + 2 \sum_{n=1}^m \frac{(-1)^{n+1}}{2^{a_1 + \cdots + a_n}}

It should be noted that if am > 1 then [a_0; a_1, a_2, \ldots, a_m-1, 1] is also a continued fraction for the same number, but the two expressions give identical values for ?(x).

[edit] Intuitive explanation

To get some intuition for the definition above, let's consider two different ways of interpreting an infinite string of bits beginning with 0 as a real number in [0,1]. One obvious way to interpret such a string is to place a binary point after the first 0 and read the string as a binary expansion: thus, for instance, the string 001001001001001001001001... represents the binary number 0.010010010010..., or 2/7. Another interpretation views a string as the continued fraction [0;a1,a2,...], where the integers ai are the run lengths in a run-length encoding of the string. The same example string 001001001001001001001001... then corresponds to [0;2,1,2,1,2,1,...] = (√3-1)/2. (If the string ends in an infinitely long run of the same bit, we ignore it and terminate the representation; this is suggested by the formal "identity" [0;a1,...,an,∞]=[0;a1,...,an+1/∞]= [0;a1,...,an+0]=[0;a1,...,an].)

The effect of the question mark function on [0,1] can then be understood as mapping the second interpretation of a string to the first interpretation of the same string. Our example string gives the equality

?\left(\frac{\sqrt3-1}{2}\right)=\frac{2}{7}.

[edit] Recursive definition for rational arguments

For rational numbers in the unit interval, the function may also be defined recursively; if p/q and r/s are reduced fractions such that |ps − rq| = 1 (so that they are adjacent elements of a row of the Farey sequence) then

?\left(\frac{p+r}{q+s}\right) = \frac12 \left(?\bigg(\frac pq\bigg) + {}?\bigg(\frac rs\bigg)\right)

Using the base cases

?\left(\frac{0}{1}\right) = 0 \quad \mbox{ and } \quad ?\left(\frac{1}{1}\right)=1

it is then possible to compute ?(x) for any rational x, starting with the Farey sequence of order 2, then 3, etc.

If pn − 1 / qn − 1 and pn / qn are two successive convergents of a continued fraction, then the matrix

\begin{pmatrix} p_{n-1} & p_{n} \\ q_{n-1} & q_{n} \end{pmatrix}

has determinant ±1. Such a matrix is an element of S * L(2,Z), the group of two-by-two matricies with determinant ±1. This group is related to the modular group.

[edit] Self-symmetry

The question mark is clearly visually self-similar. A monoid of self-similarities may be generated by the operators S and R, where S shrinks the question mark to half its size:

[S?](x) = ?\left(\frac{x}{x+1}\right) = \frac{?(x)}{2}

and R is the reflection:

[R?](x) = ?(1-x) = 1-?(x)\,

Both identities hold for all x\in [0,1]. These may be repeatedly combined, forming a monoid. A general element of the monoid is then

S^{a_1} R S^{a_2} R S^{a_3} \cdots

for positive integers a_1, a_2, a_3, \ldots. 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). Note also that the elements of the monoid are in correspondence with the rationals, by means of the identification of a_1, a_2, a_3, \ldots with the continued fraction [0; a_1, a_2, a_3, \ldots]. Since both

S: x \mapsto \frac{x}{x+1}

and

T: x \mapsto 1-x

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

[edit] Properties of ?(x)

?(x) - x
Enlarge
?(x) - x

The question mark function is a strictly increasing and absolutely continuous function. The derivative vanishes on the rational numbers; however, since the rationals are a set of measure zero, this vanishing of the derivative at the rationals is not in contradiction with the continuity of the function. It does not have a well-defined derivative, in the classical sense, on the irrationals; however, there are several constructions for a measure that, when integrated, yields the question mark function. One such construction is obtained by measuring the density of the Farey numbers on the real number line. The question mark measure is the prototypical example of what are sometimes referred to as multi-fractal measures.

The question mark function sends rational numbers to dyadic rational numbers, meaning those whose base two representation terminates. It sends quadratic irrationals to non-dyadic rational numbers. It is an odd function, and satisfies the functional equation ?(x + 1) = ?(x) + 1; consequently x→?(x) − x is an odd periodic function with period one. If ?(x) is irrational, then x is either algebraic of degree greater than two, or transcendental.

The Minkowski question mark function is a special case of fractal curves known as de Rham curves.

[edit] Conway box function

The ? is invertible, and the inverse function has also attracted the attention of various mathematicians, in particular John Conway, who discovered it independently, and whose notation for ?−1(x) is x with a box drawn around it. If we denote this instead by □(x), then we may compute the box function as an encoding of the base two expansion of (x-\lfloor x \rfloor)/2, where \lfloor x \rfloor denotes the floor function. To the right of the decimal point, this will have n1 0s, followed by n2 1s, then n3 0s and so on. Now set n_0 = \lfloor x \rfloor. Then

\Box(x) = [n_0; n_1, n_2, n_3, \ldots],

where the term on the right is a continued fraction.

[edit] Historical references

  • H. Minkowski, Verhandlungen des iii internationalen mathematiker-kongresses in heidelberg, (1904) Berlin.
  • A. Denjoy, Sur une fonction reelle de Minkowski, J. Math. Pures Appl. 17 (1938) p105-151.

[edit] References

Retrieved from "http://en.wikipedia.org../../../m/i/n/Minkowski%27s_question_mark_function.html"
In other languages