Hipoteza rozbieżności

Węgierski matematyk Paul Erdős już "gościł" na łamach niniejszego blogu. Jest - był - bowiem postacią barwną i interesującą. Pozostawił matematykom kilka całkiem niebanalnych hipotez. Część z nich została udowodniona. Inne ciągle czekają na jakiegoś geniusza.

Gdyby żył, tydzień temu obchodziłby sto trzecie urodziny.

A dziś króciutko o jego hipotezie rozbieżności (discrepancy conjecture)

Otóż Erdős twierdził, że dla dowolnie zdefiniowanego, nieskończenie długiego ciągu składającego się wyłącznie z jedynek (dodatnich bądź ujemnych), oraz dla dowolnie dużej liczby całkowitej C, zawsze można znaleźć liczby całkowite k oraz d spełniające warunek:

\(\left| \sum_{i=1}^k x_{i\cdot d} \right| > C\)

Wyjaśnienie dla Czytelników niezorientowanych w zapisie matematycznym:

Bierzemy dłuuuugi (nieskończenie długi) ciąg składający się wyłącznie z 1 lub -1. Na przykład: 1,-1,1,-1,1,-1,1,-1,1,-1,... albo 1,1,-1,1,-1,-1,1,1,1,1,-1,-1,-1,-1,1,-1,1,1,-1,-1,-1,-1,-1,1,-1,... albo jakikolwiek inny.

Następnie bierzemy sobie dowolną liczbę całkowitą dodatnią C, na przykład 2 albo 7 albo 2397465923746523789456 albo jakąkolwiek inną.

Te dwie rzeczy (ciąg oraz liczba C) to są nasze dane wejściowe.

Naszym zadaniem jest znalezienie takiej liczby d, żeby sumowanie co d-tego elementu naszego ciągu dało w wyniku liczbę większą od C (lub mniejszą od -C - a więc możemy sumować zarówno  "w górę" jak i "w dół") - i to w skończonej liczbie kroków równej k.

Czytam sobie to moje powyższe wyjaśnienie i widzę, że jest raczej mało wyjaśniające. To może teraz konkretny przykład:

Weźmy prościutki ciąg, w którym co trzeci wyraz jest równy minus jeden, a pozostałe są jedynkami:

1, 1, -1, 1, 1, -1, 1, 1, -1, 1, 1, -1, 1, 1, -1, 1, ...

Weźmy sobie liczbę C = 5.

Weźmy liczbę d = 3 i zacznijmy sumować co trzeci element naszego ciągu:

(-1) + (-1) + (-1) + (-1) + (-1) + (-1) = -6

Po zsumowaniu sześciu co-trzecich elementów naszego ciągu dotarliśmy do liczby -6, której wartość bezwzględna jest większa od C. A więc rozwiązaniem problemu rozbieżności Erdősa dla powyższego ciągu oraz liczby C=5 jest para liczb d=3 oraz k=6. Sumując sześć elementów ciągu, ale "przeskakując" co trzeci element, otrzymamy liczbę mniejszą od -5.

No i teraz najważniejsze: Erdős twierdził, że niezależnie od tego, jaki ciąg jedynek (i minus jedynek) sobie wybierzemy, oraz jak dużą przyjmiemy wartość C, zawsze znajdzie się krotność d, która po skończonej liczbie kroków sumowania da w wyniku więcej niż C (lub mniej niż -C)

Terrence Tao, bardzo zdolny australijski matematyk, udowodnił hipotezę Erdősa mniej więcej tydzień temu. Całkiem niezły prezent urodzinowy, trzeba przyznać 😉 Nawiasem mówiąc o tym matematyku też już tu wcześniej pisałem, opisując twierdzenie Green-Tao.

Nadmienię jeszcze, że częściowy dowód hipotezy udało się wcześniej uzyskać metodami komputerowymi dla C<=2. Dowód wymagał wygenerowania ponad 13GB danych, czyli więcej, niż tekst całej Wikipedii.

A Tao łyknął zagadnienie i udowodnił istnienie rozwiązania dla dowolnego C.

Warto wspomnnieć, że Tao nie przedstawił sposobu na znalezienie pary (d,k) dla zadanego ciągu oraz C, ale "tylko" udowodnił prawdziwość hipotezy rozbieżności Erdősa. To jednak i tak wystarczyło, żeby wywołać małe trzęsienie ziemi w świecie matematyków.

6 komentarzy

  1. trochę łatwiej byłoby: zamiast wartość bezwzględna suma, suma wartości bezwzględnych 😉
    A gdzie można to cudo zastosować?

    1. Nie mam bladego pojęcia. Trochę guglałem, ale nie znalazłem niczego sensownego. Tacy właśnie są metmetycy. Dowodzą głupot dla sportu 😉

      1. to ze nie rozumiesz wcale nie znaczy ze ta sa głupoty, znaczy to tylko tyle ze pomimo ze przeczytałeś “poguglales” to i tak dalej nie rozumiesz i w dodatku chetnie chwalisz sie tym ze mimo wszystko dalej nie rozumiesz:D

    2. Jedynki nagminnie wystepuja w informatyce, byc moze w jakichs sprawach wydajnosciowych ktos kiedys to wykorzysta 🙂

  2. Ciekawe. Chyba na wikipedii jest nawet zdjęcie młodego Tao z Erdosem, więc może nie dziwne, że on to udowodnił. 😉 Przy okazji widać,że regularne spożywanie amfetaminy (Erdos) może się okazać pożyteczne dla ludzkości biorąc pod uwagę ile twierdzeń i hipotez ten pan natrzepał przez całe życie. 😉

Leave a Comment

Komentarze mile widziane.

Jeżeli chcesz do komentarza wstawić kod, użyj składni:
[code]
tutaj wstaw swój kod
[/code]