Hipoteza rozbieżności

Węgierski matematyk Paul Erdős już „gościł” na łamach niniejszego bloga. 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 chiński 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.

Autor: xpil

Po czterdziestce. Żonaty. Dzieciaty. Komputerowiec. Krwiodawca. Emigrant. Rusofil. Lemofil. Sarkastyczny. Uparty. Mól książkowy. Ateista. Apolityczny. Nie oglądam TV. Uwielbiam matematykę. Walę prosto z mostu. Gram na paru instrumentach. Lubię planszówki. Słucham bluesa, poezji śpiewanej i kapel a’capella. || Kliknij tutaj po więcej szczegółów ||

Dodaj komentarz

5 komentarzy do "Hipoteza rozbieżności"

Powiadom o
avatar
Sortuj wg:   najnowszy | najstarszy | oceniany
Butter
Gość

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

Kamil
Gość

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

wpDiscuz