 Minkowski's question mark function

In mathematics, the Minkowski question mark function, sometimes called the slippery devil's staircase and denoted by
?(x), is a function possessing various unusual fractal properties, defined by Hermann Minkowski in 1904. It maps quadratic irrationals 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. In addition, it maps rational numbers to dyadic rationals, as can be seen by a recursive definition closely related to the SternBrocot tree.Contents
Definition
If is the continued fraction representation of an irrational number x, then
whereas:
If is a continued fraction representation of a rational number x, then
Intuitive explanation
To get some intuition for the definition above, consider the 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;a_{1},a_{2},...], where the integers a_{i} are the run lengths in a runlength encoding of the string. The same example string 001001001001001001001001... then corresponds to [0;2,1,2,1,2,1,...] = (√31)/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;a_{1},...,a_{n},∞]=[0;a_{1},...,a_{n}+1/∞]= [0;a_{1},...,a_{n}+0]=[0;a_{1},...,a_{n}].)
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, just as the Cantor function can be understood as mapping a triadic base 3 representation to a base 2 representation. Our example string gives the equality
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
Using the base cases
it is then possible to compute ?(x) for any rational x, starting with the Farey sequence of order 2, then 3, etc.
If p_{n − 1} / q_{n − 1} and p_{n} / q_{n} are two successive convergents of a continued fraction, then the matrix
has determinant ±1. Such a matrix is an element of S ^{*} L(2,Z), the group of twobytwo matrices with determinant ±1. This group is related to the modular group.
Algorithm
This 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 SternBrocot tree in search of the input x, and sums the terms of the binary expansion of on the way. As long as the loop invariant qr − ps = 1 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 d 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.
/* Minkowski's question mark function */ double minkowski(double x) { long p=x; if ((double)p>x) p; /* p=floor(x) */ long q=1, r=p+1, s=1, m, n; double d=1, y=p; if (x<(double)p(p<0)^(r<=0)) return x; /* out of range ?(x) =~ x */ for (;;) /* invariants: q*rp*s==1 && (double)p/q <= x && x < (double)r/s */ { d/=2; if (y+d==y) break; /* reached max possible precision */ m=p+r; if ((m<0)^(p<0)) break; /* sum overflowed */ n=q+s; if (n<0) break; /* sum overflowed */ if (x<(double)m/n) r=m, s=n; else y+=d, p=m, q=n; } return y+d; /* final roundoff */ }
Selfsymmetry
The question mark is clearly visually selfsimilar. A monoid of selfsimilarities may be generated by the operators S and R, where S shrinks the question mark to half its size:
and R is the reflection:
Both identities hold for all . These may be repeatedly combined, forming a monoid. A general element of the monoid is then
for positive integers . Each such element describes a selfsimilarity of the question mark function. This monoid is sometimes called the perioddoubling monoid, and all perioddoubling fractal curves have a selfsymmetry 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 with the continued fraction . Since both
and
are linear fractional transformations with integer coefficients, the monoid may be regarded as a subset of the modular group PSL(2,Z).
Properties of ?(x)
The question mark function is a strictly increasing and continuous, but not absolutely continuous function. The derivative vanishes on the rational numbers. 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 multifractal measures.
The question mark function sends 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 sends quadratic irrationals to nondyadic 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.
Conway box function
See also: Sawtooth waveThe ? 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 ( ). For technical reasons, this is instead denoted here by □(x). The box function can be computed as an encoding of the base two expansion of , where denotes the floor function. To the right of the decimal point, this will have n_{1} 0s, followed by n_{2} 1s, then n_{3} 0s and so on. For ,
where the term on the right is a continued fraction.
Historical references
 H. Minkowski, Verhandlungen des III. internationalen MathematikerKongresses in Heidelberg, (1904) Berlin.
 A. Denjoy, Sur une fonction réelle de Minkowski, J. Math. Pures Appl. 17 (1938) p105151.
References
 Bibiloni, L.; Paradis, J.; Viader, P. (1998), "A new light on Minkowski's ?(x) function", Journal of Number Theory 73 (2): 212–227, doi:10.1006/jnth.1998.2294, http://www.econ.upf.es/en/research/onepaper.php?id=226.
 Bibiloni, L.; Paradis, J.; Viader, P. (2001), "The derivative of Minkowski's singular function", Journal of Mathematical Analysis and Applications 253 (1): 107–125, doi:10.1006/jmaa.2000.7064, http://www.econ.upf.es/en/research/onepaper.php?id=378.
 Conley, R. M. (2003), A Survey of the Minkowski ?(x) Function, Masters thesis, West Virginia University.
 Conway, J. H. (2000), "Contorted fractions", On Numbers and Games (2nd ed.), Wellesley, MA: A K Peters, pp. 82–86.
External links
Categories: Fractal curves
 Continued fractions
 Special functions
 Continuous mappings
Wikimedia Foundation. 2010.
Look at other dictionaries:
Question mark — ? redirects here. For other uses, see Question mark (disambiguation). For the backwards or mirrored question mark used to indicate irony or sarcasm, see percontation point. For Wikipedia s help pages, see Help:Contents ? Question mark … Wikipedia
Question mark (disambiguation) — A question mark is a type of punctuation mark.Question mark or ? may also refer to:* ? (album), a progressive rock album by Neal Morse * ? (Modwheelmood EP), an electronic alternative EP by Modwheelmood * ? (bistro), a kafana (tavern) located in… … Wikipedia
Minkowski — (Hebrew: מינקובסקי, Russian: Минковский) is a surname, and may refer to: Eugène Minkowski (1885 1972), French psychiatrist Hermann Minkowski (1864 1909) Russian born German mathematician and physicist, known for: Minkowski addition… … Wikipedia
Hermann Minkowski — Infobox Scientist name = Hermann Minkowski 300px caption = birth date = birth date1864622mf=y birth place = Aleksotas, Kaunas, Lithuania, Russian Empire death date = death date and age19091121864622mf=y death place = Göttingen,… … Wikipedia
Cantor function — In mathematics, the Cantor function, named after Georg Cantor, is an example of a function that is continuous, but not absolutely continuous. DefinitionThe Cantor function c : [0,1] → [0,1] is defined as follows:#Express x in base 3. If possible … Wikipedia
List of mathematics articles (M) — NOTOC M M estimator M group M matrix M separation M set M. C. Escher s legacy M. Riesz extension theorem M/M/1 model Maass wave form Mac Lane s planarity criterion Macaulay brackets Macbeath surface MacCormack method Macdonald polynomial Machin… … Wikipedia
De Rham curve — In mathematics, a de Rham curve is a certain type of fractal curve named in honor of Georges de Rham. The Cantor function, Césaro curve, Minkowski s question mark function, the Lévy C curve, the blancmange curve and the Koch curve are all special … Wikipedia
Fonction point d'interrogation — de Minkowski. La fonction point d interrogation est, en mathématiques, une fonction, notée . Cette fonction fut définie par Hermann Minkowski en 1904 … Wikipédia en Français
Fonction Point D'interrogation — La fonction point d interrogation est, en mathématiques, une fonction, notée . Cette fonction fut définie par Hermann Minkowski en 1904 afin de créer une application continue de l ensemble des nombres irrationnels quadratiques de l intervalle… … Wikipédia en Français
Modular group — For a group whose lattice of subgroups is modular see Iwasawa group. In mathematics, the modular group Γ is a fundamental object of study in number theory, geometry, algebra, and many other areas of advanced mathematics. The modular group can be… … Wikipedia