Funkcja znaku zapytania Minkowskiego - Minkowski's question-mark function

Funkcja znaku zapytania Minkowskiego.
Po lewej: ?( x ) . Dobrze: ?( x ) − x .

W matematyce , funkcja Minkowski znak zapytania oznaczone ? ( X ) , to funkcja posiadająca różne nietypowe fraktalne właściwości zdefiniowane przez Hermanna Minkowskiego  ( 1904 , strony 171-172). Mapuje kwadratowe Irrationals do liczb wymiernych na przedział jednostkowy poprzez wyrażenie odnoszącego się do ułamka rozwinięć quadratics do tych binarnych rozszerzenia tych wymiernych, podanych Arnaud Denjoy w 1938. Ponadto, mapuje racjonalne numery dwójkowym wymiernych jako można zobaczyć przez rekurencyjną definicję ściśle związaną z drzewem Sterna-Brocota .

Definicja

Jeśli [ a 0 ; a 1 , a 2 , …] jest reprezentacją ułamka łańcuchowego liczby niewymiernej  x , wtedy

mając na uwadze, że jeśli [ a 0 ; a 1 , a 2 , …, a m ] jest reprezentacją ułamka łańcuchowego liczby wymiernej  x , wtedy

Intuicyjne wyjaśnienie

Aby uzyskać intuicję dotyczącą powyższej definicji, rozważ różne sposoby interpretacji nieskończonego ciągu bitów zaczynającego się od 0 jako liczby rzeczywistej w [0, 1] . Jednym z oczywistych sposobów interpretacji takiego ciągu jest umieszczenie kropki binarnej po pierwszym 0 i odczytanie ciągu jako rozwinięcia binarnego : na przykład ciąg 001001001001001001001001... reprezentuje liczbę binarną 0.010010010010... lub2/7. Inna interpretacja postrzega ciąg znaków jako ułamek ciągły [0; a 1 ,  a 2 , …] , gdzie liczby całkowite a i są długościami ciągów w kodowaniu ciągów znaków. Ten sam przykładowy ciąg 001001001001001001001001... odpowiada następnie [0; 2, 1, 2, 1, 2, 1, …] =3 − 1/2. Jeśli ciąg kończy się nieskończenie długim ciągiem tego samego bitu, ignorujemy go i kończymy reprezentację; sugeruje to formalna „tożsamość”:

[0; a 1 , …, a n , ∞] = [0; a 1 , …, a n +1/] = [0; a 1 , …, a n + 0] = [0; 1 , ..., n ] .

Wpływ funkcji znaku zapytania na [0, 1] można zatem rozumieć jako odwzorowanie drugiej interpretacji ciągu na pierwszą interpretację tego samego ciągu, tak jak funkcję Cantora można rozumieć jako odwzorowanie triadycznej bazy 3 reprezentacja na reprezentację o podstawie 2. Nasz przykładowy ciąg daje równość

Rekurencyjna definicja argumentów racjonalnych

Dla liczb wymiernych w przedziale jednostkowym funkcja może być również zdefiniowana rekurencyjnie ; JeśliP/Q oraz r/sułamkami zredukowanymi takimi, że | psrq | = 1 (tak, że są one sąsiadującymi elementami rzędu ciągu Fareya ) then

Korzystanie z podstawowych przypadków

wtedy można obliczyć ?( x ) dla dowolnego wymiernego  x , zaczynając od sekwencji Fareya rzędu 2, potem 3 itd.

Gdyby p n- 1/q n −1 oraz p n/q nto dwie kolejne zbieżności ułamka łańcuchowego , to macierz

ma wyznacznik  ±1. Taka macierz jest elementem SL(2,  Z ) , grupy macierzy 2 × 2 z wyznacznikiem ±1. Ta grupa jest powiązana z grupą modułową .

Samosymetria

Znak zapytania jest wyraźnie podobny wizualnie. Monoid samodzielnych podobieństwa mogą być generowane przez dwóch operatorów S i R działających na placu jednostkę i określa się następująco:

Wizualnie S zmniejsza kwadrat jednostki do jego lewej dolnej ćwiartki, podczas gdy R wykonuje odbicie punktowe przez jego środek.

Punkt na wykresie z ? ma współrzędne ( x , ?( x )) dla pewnego x w przedziale jednostkowym. Taki punkt jest przekształcany przez S i R w inny punkt wykresu, ponieważ ? spełnia następujące tożsamości dla wszystkich x ∈ [0, 1] :

Te dwa operatory mogą być wielokrotnie łączone, tworząc monoid. Ogólnym elementem monoidu jest zatem

dla liczb całkowitych dodatnich a 1 , a 2 , a 3 , … . Każdy taki element opisuje samopodobieństwo funkcji znaku zapytania. Monoid ten jest czasem nazywany monoidem podwajania okresów , a wszystkie krzywe fraktalne podwajania okresów mają opisaną przez siebie samosymetrię ( kategorią takich krzywych jest krzywa de Rhama , której znak zapytania jest przypadkiem szczególnym). Elementy monoid są odpowiednio z wymiernych poprzez identyfikację w 1 , 2 , 3 ... z ułamka [0; a 1 , a 2 , a 3 ,…] . Od kiedy oboje

oraz

liniowymi przekształceniami ułamkowymi o współczynnikach całkowitych, monoid może być traktowany jako podzbiór grupy modułowej PSL(2, Z ) .

irracjonalne kwadratowe

Funkcja znaku zapytania zapewnia odwzorowanie jeden-do-jednego z niewymiernych wymiernych na kwadratowe wymierne , co pozwala na jednoznaczny dowód policzalności tych ostatnich. Mogą one, w rzeczywistości należy rozumieć odpowiadają okresowych orbity dla diadycznej transformacji . Można to wyraźnie zademonstrować w zaledwie kilku krokach.

Symetria diadyczna

Zdefiniuj dwa ruchy: ruch w lewo i ruch w prawo, ważne w interwale jednostkowym jako

oraz

oraz

oraz

Funkcja znaku zapytania zachowuje wtedy symetrię ruchu w lewo

i symetria ruchu w prawo

gdzie oznacza kompozycję funkcji . Mogą być dowolnie łączone. Rozważmy na przykład sekwencję ruchów lewo-prawo Dodanie indeksów dolnych C i D oraz, dla jasności, porzucenie operatora kompozycji we wszystkich miejscach poza kilkoma, mamy:

Arbitralne łańcuchy o skończonej długości w literach L i R odpowiadają wymiernym diadycznym , w tym sensie , że każdy wymierny dwudniowy można zapisać zarówno jako liczby całkowite n i m, jak i jako skończoną długość bitów z Tak więc każda wymierność dwudniowa jest w jednym do- jedna korespondencja z pewną samosymetrią funkcji znaku zapytania.

Niektóre zmiany notacji mogą nieco ułatwić wyrażenie powyższego. Niech i oznaczają L i R. Złożenie funkcji rozszerza to na monoid , w którym można pisać i ogólnie dla niektórych binarnych ciągów cyfr A , B , gdzie AB jest zwykłym połączeniem takich ciągów. Monoid diady M jest zatem monoidem wszystkich takich ruchów lewo-prawo o skończonej długości. Pisząc jako ogólny element monoidu, odpowiada mu samosymetria funkcji znaku zapytania:

Izomorfizm

Wyraźne odwzorowanie między wymiernymi a dwuczłonowymi wymiernymi można uzyskać, zapewniając operator odbicia

i zauważając, że obaj

oraz

Ponieważ jest tożsamość, arbitralne ciąg lewo-prawo ruchów można ponownie zapisać jako ciąg tylko przemieszcza się w lewo, a następnie odbicie, a następnie bardziej lewicowych ruchów, refleksji, i tak dalej, to jest, jak co jest wyraźnie izomorficzny do góry. Obliczenie pewnej wyraźnej sekwencji na argumencie funkcji daje racjonalny dwudniowy; wyraźnie jest równa, gdzie każdy jest bitem binarnym, zero odpowiada ruchowi w lewo, a jeden odpowiada ruchowi w prawo. Równoważna sekwencja ruchów, oceniona jako, daje liczbę wymierną. Jest to wyraźnie ta, którą dostarcza ułamek łańcuchowy, pamiętając, że jest ona wymierna, ponieważ ciąg ma skończoną długość. To ustanawia relację jeden-do-jednego między racjonałami diadycznymi a rozumnymi.

Okresowe orbity transformaty dwójkowej

Rozważmy teraz okresowe orbity na diadycznej transformacji . Odpowiadają one sekwencjom bitowym składającym się ze skończonej początkowej „chaotycznej” sekwencji bitów , po której następuje powtarzający się ciąg o długości . Takie powtarzające się ciągi odpowiadają liczbie wymiernej. Łatwo to wyjaśnić. Pisać

jeden to wyraźnie ma

Włączając początkową nie powtarzającą się sekwencję, mamy wyraźnie liczbę wymierną. W rzeczywistości każdą liczbę wymierną można wyrazić w ten sposób: początkowa „losowa” sekwencja, po której następuje cykliczne powtórzenie. Oznacza to, że okresowe orbity mapy odpowiadają jeden do jednego z wymiernymi.

Orbity okresowe jako ułamki ciągłe

Takie orbity okresowe mają równoważny ułamek okresowy ciągły, zgodnie z izomorfizmem ustalonym powyżej. Istnieje początkowa „chaotyczna” orbita o pewnej skończonej długości, po której następuje powtarzająca się sekwencja. Powtarzająca się sekwencja generuje okresowy ułamek ciągły spełniający Ten ułamek ciągły ma postać

z byciem liczbami całkowitymi, a satysfakcjonujące wartości Jawne można uzyskać, pisząc

na zmianę, żeby

podczas gdy odbicie jest podane przez

tak, że . Obie te macierze są unimodularne , dowolne iloczyny pozostają unimodularne i dają macierz postaci

podając dokładną wartość ułamka łańcuchowego. Ponieważ wszystkie wpisy macierzy są liczbami całkowitymi, ta macierz należy do projekcyjnej grupy modułowej

Rozwiązując jawnie, mamy to. Nietrudno zweryfikować, czy rozwiązania tego problemu spełniają definicję niewymiernych kwadratów. W rzeczywistości w ten sposób można wyrazić każdą kwadratową irracjonalność. Zatem kwadratowe irracjonalne są w relacji jeden-do-jednego z okresowymi orbitami transformacji dwuczłonowej, które są w relacji jeden-do-jednego z (niediadycznymi) wymiernymi, które są w relacji jeden-do-jednego z rozumowania dwudniowe. Funkcja znaku zapytania zapewnia korespondencję w każdym przypadku.

Właściwości ?( x )

?(x) − x

Funkcja znaku zapytania jest funkcją ściśle rosnącą i ciągłą, ale nie absolutnie ciągłą . Pochodna jest określona prawie wszędzie i może przyjmować tylko dwie wartości 0 (wartość prawie wszędzie, w tym na wszystkich liczb wymiernych ) oraz . Istnieje kilka konstrukcji miary, która po zintegrowaniu daje funkcję znaku zapytania. Jedną z takich konstrukcji uzyskuje się mierząc gęstość liczb Fareya na osi liczb rzeczywistych. Miara ze znakiem zapytania jest prototypowym przykładem tego, co czasami określa się mianem miar multifraktalnych .

Funkcja znaku zapytania odwzorowuje liczby wymierne na dwójkowe liczby wymierne , czyli te, których podstawowa reprezentacja kończy się, jak można dowieść przez indukcję z konstrukcji rekurencyjnej opisanej powyżej. Odwzorowuje to kwadratowe Irrationals do non-dwójkowym liczb wymiernych. W obu przypadkach zapewnia to izomorfizm rzędów między tymi zbiorami, czyniąc konkretne twierdzenie o izomorfizmie Cantora, zgodnie z którym każde dwa nieograniczone, policzalne gęste rzędy liniowe są izomorficzne w rzędzie. Jest to funkcja nieparzysta i spełnia równanie funkcjonalne ?( x + 1) = ?( x ) + 1 ; w konsekwencji x → ?( x ) − x jest nieparzystą funkcją okresową z pierwszym okresem. Jeśli ?( x ) jest niewymierne, to x jest albo algebraiczne o stopniu większym niż dwa, albo transcendentalne .

Funkcja znaku zapytania ma stałe punkty na 0,1/2i 1 i co najmniej dwa inne, symetryczne wokół punktu środkowego. Jeden to około 0,42037. Moshchevitin przypuszczał, że są to jedyne 5 stałych punktów.

W 1943 Raphaël Salem postawił pytanie, czy współczynniki Fouriera-Stieltjesa funkcji znaku zapytania znikają w nieskończoności. Innymi słowy, chciał wiedzieć, czy…

Na to odpowiedzieli twierdząco Jordan i Sahlsten, jako szczególny przypadek wyniku środków Gibbsa .

Wykres funkcji znaku zapytania Minkowskiego jest szczególnym przypadkiem krzywych fraktalnych zwanych krzywymi de Rama .

Algorytm

Definicja rekurencyjna naturalnie nadaje się do algorytmu obliczania funkcji z dowolnym pożądanym stopniem dokładności dla dowolnej liczby rzeczywistej, jak pokazuje następująca funkcja C. Algorytm schodzi w dół drzewa Sterna-Brocota w poszukiwaniu danych wejściowych  x i po drodze sumuje warunki rozwinięcia binarnego y = ?( x ) . Dopóki niezmiennik pętli qrps = 1 pozostaje spełniony, nie ma potrzeby zmniejszania ułamkam/n = p + r/q + s, ponieważ jest już na najniższym poziomie. Innym niezmiennikiem jestP/Qx <r/s. forPętla w tym programie mogą być analizowane trochę jak whilepętla, z warunkowym sprawozdania przerwa w pierwszych trzech wierszy składających się warunku. Jedyne instrukcje w pętli, które mogą mieć wpływ na niezmienniki, znajdują się w ostatnich dwóch wierszach i można wykazać, że zachowują one prawdziwość obu niezmienników, o ile pierwsze trzy wiersze zostały wykonane pomyślnie bez przerwania pętli. Trzeci niezmiennik dla ciała pętli (do dokładności zmiennoprzecinkowej) to y ≤ ?( x ) < y + d , ale ponieważ d jest zmniejszane o połowę na początku pętli przed sprawdzeniem jakichkolwiek warunków, nasz wniosek jest taki, że y ≤ ?( x ) < y + 2 d na końcu pętli.

Aby udowodnić zakończenie , wystarczy zauważyć, że suma q + szwiększa się o co najmniej 1 z każdą iteracją pętli i że pętla kończy się, gdy ta suma jest zbyt duża, aby można ją było przedstawić w prymitywnym typie danych C long. Jednak w praktyce warunkowe przerwanie kiedy y + d == yzapewnia zakończenie pętli w rozsądnym czasie.

/* 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 */
}

Rozkład prawdopodobieństwa

Ograniczanie Minkowski znak zapytania funkcję do: [0,1] → [0,1], może być używany jako skumulowanej funkcji rozkładu z pojedynczej dystrybucji na przedział jednostkowy. Rozkład ten jest symetryczny względem jego punktu środkowego, z surowymi momentami około m 1  = 0,5, m 2  = 0,290926, m 3  = 0,186389 i m 4  = 0,126992, a więc średnia i mediana 0,5, odchylenie standardowe około 0,2023, a skośność 0, a kurtoza nadmierna około -1,147.

Funkcja skrzynki Conway

Ponieważ funkcja znaku zapytania Minkowskiego jest ściśle rosnącą, ciągłą bijekcją z liczb rzeczywistych na liczby rzeczywiste, ma ona funkcję odwrotną zwaną funkcją Conway box . Więc ...

To odwzorowuje wymierności dwuczłonowe na wymierne, a wymierne na pole kwadratowe. Argument kardynalności pokazuje, że bez względu na to, ile razy zostanie to powtórzone, prawie wszystkie liczby rzeczywiste są w tym sensie nie do pakowania .

Zobacz też

Uwagi

odniesienia historyczne

Bibliografia

Zewnętrzne linki