Benutzer:Tino Cannst/Minkowski'schen Fragezeichenfunktion

Dieser Artikel (Minkowski'schen Fragezeichenfunktion) ist im Entstehen begriffen und noch nicht Bestandteil der freien Enzyklopädie Wikipedia.

Wenn du dies liest:

• Der Text kann teilweise in einer Fremdsprache verfasst, unvollständig sein oder noch ungeprüfte Aussagen enthalten.
• Wenn du Fragen zum Thema hast, nimm am besten Kontakt mit dem Autor Tino Cannst auf.

Wenn du diesen Artikel überarbeitest:

• Bitte denke daran, die Angaben im Artikel durch geeignete Quellen zu belegen und zu prüfen, ob er auch anderweitig den Richtlinien der Wikipedia entspricht (siehe Wikipedia:Artikel).
• Nach erfolgter Übersetzung kannst du diese Vorlage entfernen und den Artikel in den Artikelnamensraum verschieben. Die entstehende Weiterleitung kannst du schnelllöschen lassen.
• Importe inaktiver Accounts, die länger als drei Monate völlig unbearbeitet sind, werden gelöscht.

Vorlage:Importartikel/Wartung-2020-05

Minkowski question-mark function.

Left: Vorlage:Math. Right: Vorlage:Math.

Die Minkowski'sche Fragezeichenfunktion denoted by Vorlage:Math, is a Funktion mit einer Reihe ungewöhnlicher Eigenschaften.

Vorlage:Harvs. 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 Stern–Brocot tree.

Definition

If Vorlage:Math is the continued-fraction representation of an irrational number Vorlage:Mvar, then

$\operatorname {?} (x)=a_{0}+2\sum _{n=1}^{\infty }{\frac {\left(-1\right)^{n+1}}{2^{a_{1}+\cdots +a_{n}}}},$

whereas if Vorlage:Math is a continued-fraction representation of a rational number Vorlage:Mvar, then

$\operatorname {?} (x)=a_{0}+2\sum _{n=1}^{m}{\frac {\left(-1\right)^{n+1}}{2^{a_{1}+\cdots +a_{n}}}}.$

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 Vorlage:Closed-closed. 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 Vorlage:Sfrac. Another interpretation views a string as the continued fraction Vorlage:Math, where the integers Vorlage:Mvar are the run lengths in a run-length encoding of the string. The same example string 001001001001001001001001... then corresponds to Vorlage:Math. 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":

Vorlage:Math.

The effect of the question-mark function on Vorlage:Closed-closed 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

$\operatorname {?} \left({\frac {{\sqrt {3}}-1}{2}}\right)={\frac {2}{7}}.$

Recursive definition for rational arguments

For rational numbers in the unit interval, the function may also be defined recursively; if Vorlage:Math and Vorlage:Math are reduced fractions such that Vorlage:Math (so that they are adjacent elements of a row of the Farey sequence) then

$\operatorname {?} \left({\frac {p+r}{q+s}}\right)={\frac {1}{2}}\left[\operatorname {?} \left({\frac {p}{q}}\right)+\operatorname {?} \left({\frac {r}{s}}\right)\right].$

Using the base cases

$\operatorname {?} \left({\frac {0}{1}}\right)=0\quad {\text{ and }}\quad \operatorname {?} \left({\frac {1}{1}}\right)=1,$

it is then possible to compute Vorlage:Math for any rational Vorlage:Mvar, starting with the Farey sequence of order 2, then 3, etc.

If Vorlage:Math and Vorlage:Math 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 Vorlage:Math, the group of 2 × 2 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 Stern–Brocot tree in search of the input Vorlage:Mvar, and sums the terms of the binary expansion of Vorlage:Math on the way. As long as the loop invariant Vorlage:Math remains satisfied there is no need to reduce the fraction Vorlage:Math, since it is already in lowest terms. Another invariant is Vorlage:Math. 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 Vorlage:Math, but since Vorlage:Mvar is halved at the beginning of the loop before any conditions are tested, our conclusion is only that Vorlage:Math 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 * r - p * 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 round-off */
}

Self-symmetry

The question mark is clearly visually self-similar. A monoid of self-similarities may be generated by two operators Vorlage:Mvar and Vorlage:Mvar acting on the unit square and defined as follows:

${\begin{aligned}S(x,y)&=\left({\frac {x}{x+1}},{\frac {y}{2}}\right),\\[5px]R(x,y)&=(1-x,1-y).\end{aligned}}$

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

A point on the graph of Vorlage:Math has coordinates Vorlage:Math for some Vorlage:Mvar in the unit interval. Such a point is transformed by Vorlage:Mvar and Vorlage:Mvar into another point of the graph, because Vorlage:Math satisfies the following identities for all Vorlage:Math:

${\begin{aligned}\operatorname {?} \left({\frac {x}{x+1}}\right)&={\frac {\operatorname {?} (x)}{2}},\\[5px]\operatorname {?} (1-x)&=1-\operatorname {?} (x).\end{aligned}}$

These two operators may be repeatedly combined, forming a monoid. A general element of the monoid is then

$S^{a_{1}}RS^{a_{2}}RS^{a_{3}}\cdots$

for positive integers Vorlage:Math. 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 Vorlage:Math with the continued fraction Vorlage:Math. 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 Vorlage:Math.

Properties of Vorlage:Math

Vorlage:Wide image 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 multi-fractal measures.

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. It is an odd function, and satisfies the functional equation Vorlage:Math; consequently Vorlage:Math is an odd periodic function with period one. If Vorlage:Math is irrational, then Vorlage:Mvar is either algebraic of degree greater than two, or transcendental.

The question-mark function has fixed points at 0, Vorlage:Sfrac and 1, and at least two more, symmetric about the midpoint. One is approximately 0.42037.

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

$\lim _{n\to \infty }\int _{0}^{1}e^{2\pi inx}\,\operatorname {d?} (x)=0.$

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.

Conway box function

The Vorlage:Math function 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 Vorlage:Math is Vorlage:Mvar with a box drawn around it: Vorlage:Mvar. The box function can be computed as an encoding of the base-2 expansion of Vorlage:Math, where Vorlage:Math denotes the floor function. To the right of the point, this will have Vorlage:Math 0s, followed by Vorlage:Math 1s, then Vorlage:Math 0s and so on. For Vorlage:Math,

Vorlage:Math

where the term on the right is a continued fraction.

See also

• Pompeiu derivative

Historical references

• Vorlage:Citation
• Vorlage:Citation

References

• Vorlage:Citation.
• Vorlage:Citation.
• Vorlage:Citation.
• Vorlage:Citation.
• Vorlage:Citation.
• Vorlage:Citation
• Vorlage:Citation
• Vorlage:Citation
• Vorlage:Citation
• Vorlage:Citation
• Vorlage:Cite arxiv

External links

• An extensive bibliography list
• Vorlage:Mathworld
• Simple IEEE 754 implementation in C++

[[Category:De Rham curves]]
[[Category:Continued fractions]]
[[Category:Special functions]]
[[Category:Continuous mappings]]
[[Category:Articles with example C code]]
[[Category:Hermann Minkowski]]