Wprowadzenie
W połowie października Justina Gilmera przyleciał z Kalifornii do Nowego Jorku, aby wziąć udział w ślubie przyjaciela. Będąc na Wschodnim Wybrzeżu odwiedził swojego byłego doradcę, Michał Saks, matematyk z Rutgers University, gdzie Gilmer obronił doktorat siedem lat wcześniej.
Saks i Gilmer spotkali się podczas lunchu, ale nie rozmawiali o matematyce. W rzeczywistości Gilmer nie myślał poważnie o matematyce od czasu ukończenia Rutgers w 2015 roku. Wtedy zdecydował, że nie chce kariery akademickiej i zamiast tego zaczął uczyć się programowania. Kiedy on i Saks jedli, Gilmer opowiedział swojemu dawnemu mentorowi o swojej pracy w Google, gdzie zajmuje się uczeniem maszynowym i sztuczną inteligencją.
Dzień, w którym Gilmer odwiedził Rutgersa, był słoneczny. Spacerując, przypomniał sobie, jak w 2013 roku spędził większą część roku, spacerując tymi samymi ścieżkami kampusu, myśląc o problemie zwanym domniemaniem zamkniętych związków zawodowych. To była fiksacja, choć bezowocna: mimo całego swojego wysiłku Gilmerowi udało się tylko dowiedzieć, dlaczego pozornie prosty problem dotyczący zbiorów liczb jest tak trudny do rozwiązania.
„Myślę, że wiele osób myśli o problemie, dopóki nie są usatysfakcjonowane, że rozumieją, dlaczego jest to trudne. Prawdopodobnie spędziłem nad tym więcej czasu niż większość ludzi” – powiedział Gilmer.
Po jego październikowej wizycie stało się coś nieoczekiwanego: wpadł na nowy pomysł. Gilmer zaczął myśleć o sposobach zastosowania technik z teorii informacji do rozwiązania hipotezy związku zamkniętego. Realizował ten pomysł przez miesiąc, na każdym kroku spodziewając się, że się nie powiedzie. Ale zamiast tego droga do dowodu wciąż się otwierała. Wreszcie 16 listopada br opublikował pierwszy w swoim rodzaju wynik to znacznie przybliża matematyków do udowodnienia pełnej hipotezy.
Artykuł zapoczątkował lawinę dalszych prac. Matematycy z University of Oxford, Massachusetts Institute of Technology i Institute for Advanced Study, między innymi, szybko zbudowali nowatorskie metody Gilmera. Ale zanim to zrobili, zadali własne pytanie: Kim jest ten facet?
W połowie pełna
Hipoteza domkniętych związków dotyczy zbiorów liczb zwanych zbiorami, takich jak {1, 2} i {2, 3, 4}. Na zbiorach można wykonywać operacje, w tym brać ich sumę, czyli łączyć. Na przykład suma {1, 2} i {2, 3, 4} to {1, 2, 3, 4}.
Kolekcja lub rodzina zestawów jest uważana za „zamkniętą na sumę”, jeśli suma dowolnych dwóch zestawów w rodzinie jest równa jakiemukolwiek istniejącemu zestawowi w rodzinie. Rozważmy na przykład tę rodzinę czterech zestawów:
{1}, {1, 2}, {2, 3, 4}, {1, 2, 3, 4}.
Połącz dowolną parę, a otrzymasz zestaw, który jest już w rodzinie, dzięki czemu związek rodzinny jest zamknięty.
Matematycy rozmawiali o wersjach hipotezy zamkniętej unii już w latach sześćdziesiątych, ale jej pierwsze oficjalne stwierdzenie pojawiło się w 1960 r. Petera Frankla, węgierski matematyk, który wyemigrował do Japonii w latach 1980., a do swoich zainteresowań zalicza występy uliczne.
Frankl przypuszczał, że jeśli rodzina zbiorów jest zwarta, musi zawierać co najmniej jeden element (lub liczbę), który pojawia się w co najmniej połowie zbiorów. Był to naturalny próg z dwóch powodów.
Po pierwsze, istnieją łatwo dostępne przykłady rodzin zwartych, w których wszystkie elementy występują dokładnie w 50% zestawów. Jak na przykład wszystkie różne zestawy, które możesz wykonać z liczb od 1 do 10. Istnieje 1,024 takich zestawów, które tworzą rodzinę zamkniętą na związki, a każdy z 10 elementów występuje w 512 z nich. Po drugie, w czasie, gdy Frankl stawiał hipotezę, nikt nigdy nie przedstawił przykładu rodziny zamkniętej w związkach, w której hipoteza się nie sprawdzała.
Tak więc 50% wydawało się właściwą prognozą.
Nie oznaczało to, że łatwo było to udowodnić. W latach, które upłynęły od artykułu Frankla, było niewiele wyników. Przed pracą Gilmera w tych artykułach udało się jedynie ustalić progi, które różniły się w zależności od liczby zestawów w rodzinie (w przeciwieństwie do tego samego progu 50% dla rodzin zestawów wszystkich rozmiarów).
„Wydaje się, że powinno to być łatwe i jest podobne do wielu łatwych problemów, ale oparło się atakom” — powiedział Willa Sawina Uniwersytetu Columbia.
Brak postępu odzwierciedlał zarówno skomplikowaną naturę problemu, jak i fakt, że wielu matematyków wolało o tym nie myśleć; martwili się, że stracą lata kariery, goniąc za kuszącym problemem, którego nie da się rozwiązać. Gilmer pamięta dzień w 2013 roku, kiedy poszedł do biura Saksa i przedstawił domniemanie zamkniętego związku. Jego doradca, który w przeszłości sam zmagał się z tym problemem, prawie wyrzucił go z pokoju.
„Mike powiedział:„ Justin, sprawisz, że znowu będę myślał o tym problemie, a nie chcę tego robić ”- powiedział Gilmer.
Wgląd w niepewność
Po wizycie u Rutgersa Gilmer zastanowił się nad problemem, próbując zrozumieć, dlaczego było to takie trudne. Podpowiedział sobie podstawowy fakt: jeśli masz rodzinę składającą się ze 100 zestawów, istnieje 4,950 różnych sposobów wybrania dwóch i połączenia ich. Następnie zadał sobie pytanie: jak to możliwe, że 4,950 różnych połączeń jest mapowanych z powrotem na zaledwie 100 zestawów, jeśli żaden element nie pojawia się w tych połączeniach z przynajmniej pewną częstotliwością?
Nawet w tym momencie był w drodze do dowodu, choć jeszcze o tym nie wiedział. Techniki z teorii informacji, które zapewniają rygorystyczny sposób myślenia o tym, czego się spodziewać, gdy losowo wyciągniemy parę przedmiotów, zaprowadzą go tam.
Teoria informacji rozwinęła się w pierwszej połowie XX wieku, najsłynniej w artykule Claude'a Shannona z 20 r. „Matematyczna teoria komunikacji”. W artykule podano precyzyjny sposób obliczenia ilości informacji potrzebnych do wysłania wiadomości, w oparciu o stopień niepewności co do tego, co dokładnie będzie zawierała wiadomość. Ten link — między informacją a niepewnością — było niezwykłym, fundamentalnym spostrzeżeniem Shannona.
Aby wziąć przykład z zabawką, wyobraź sobie, że rzucam pięć razy monetą i wysyłam wynikową sekwencję do ciebie. Jeśli jest to zwykła moneta, do przesłania wymaga pięciu bitów informacji. Ale jeśli jest to załadowana moneta – powiedzmy, 99% prawdopodobieństwa wyląduje na reszce – zajmuje to dużo mniej. Na przykład, możemy uzgodnić z wyprzedzeniem, że wyślę ci 1 (pojedynczy bit informacji), jeśli załadowana moneta wypadnie reszką wszystkie pięć razy, co jest bardzo prawdopodobne. W wyniku uczciwego rzutu monetą jest więcej niespodzianek niż w przypadku rzutu stronniczego, a zatem więcej informacji.
To samo myślenie dotyczy informacji zawartych w zbiorach liczb. Jeśli mam rodzinę zbiorów domkniętych sumą — powiedzmy 1,024 zbiorów utworzonych z liczb od 1 do 10 — mógłbym wybrać losowo dwa zbiory. Wtedy mógłbym ci przekazać elementy każdego zestawu. Ilość informacji potrzebnych do wysłania tej wiadomości odzwierciedla stopień niepewności co do tego, czym są te elementy: na przykład istnieje 50% szans, że pierwszym elementem w pierwszym zestawie jest 1 (ponieważ 1 pojawia się w połowie zestawów w rodzina), tak jak istnieje 50% szans, że pierwszym wynikiem w serii uczciwych rzutów monetą będzie orzeł.
Teoria informacji pojawia się często w kombinatoryce, dziedzinie matematyki zajmującym się liczeniem obiektów, którą Gilmer studiował jako doktorant. Ale wracając do domu w Kalifornii, martwił się, że sposób, w jaki myślał o połączeniu teorii informacji z hipotezą zamkniętego związku, był naiwnym spostrzeżeniem amatora: z pewnością pracujący matematycy natknęli się już wcześniej na ten błyszczący obiekt i uznali go za złoto głupców .
„Szczerze mówiąc, jestem trochę zaskoczony, że nikt wcześniej na to nie wpadł” — powiedział Gilmer. „Ale może nie powinienem się dziwić, bo sam myślałem o tym przez rok i znałem się na teorii informacji”.
Bardziej prawdopodobne niż nie
Gilmer pracował nad problemem nocami, po zakończeniu pracy w Google, oraz w weekendy drugiej połowy października i początku listopada. Zachęciły go pomysły, które grupa matematyków zbadała wiele lat wcześniej w an otwarta współpraca na blogu wybitnego matematyka Tima Gowersa. Pracował także z podręcznikiem, aby móc wyszukać formuły, o których zapomniał.
„Można by pomyśleć, że ktoś, kto osiąga świetne wyniki, nie powinien zaglądać do rozdziału 2 Elementy teorii informacji, ale tak zrobiłem” – powiedział Gilmer.
Strategia Gilmera polegała na wyobrażeniu sobie zamkniętej w związkach rodziny, w której żaden element nie pojawił się nawet w 1% wszystkich zestawów - kontrprzykład, który, gdyby naprawdę istniał, sfalsyfikowałby przypuszczenia Frankla.
Załóżmy, że wybierasz losowo dwa zestawy, A i B, z tej rodziny i rozważasz elementy, które mogą znajdować się w tych zestawach, po jednym na raz. Teraz zapytaj: Jakie są szanse, że zbiór A zawiera liczbę 1? A zestaw B? Ponieważ każdy element ma nieco mniej niż 1% szansy na pojawienie się w danym zestawie, nie spodziewałbyś się, że A lub B będą zawierały 1. Co oznacza, że nie będzie niespodzianki — i niewiele uzyskanych informacji — jeśli dowiesz się, że w rzeczywistości ani robi.
Następnie pomyśl o prawdopodobieństwie, że suma A i B zawiera 1. Nadal jest to mało prawdopodobne, ale bardziej prawdopodobne niż prawdopodobieństwo, że pojawi się w którymś z poszczególnych zestawów. Jest to suma prawdopodobieństwa, że pojawi się w A i prawdopodobieństwa, że pojawi się w B minus prawdopodobieństwo, że pojawi się w obu. Więc może nieco poniżej 2%.
To wciąż mało, ale bliżej propozycji 50-50. Oznacza to, że potrzeba więcej informacji, aby udostępnić wynik. Innymi słowy, jeśli istnieje rodzina zamknięta w związkach, w której żaden element nie pojawia się w co najmniej 1% wszystkich zestawów, w połączeniu dwóch zestawów jest więcej informacji niż w każdym z samych zestawów.
„Pomysł odkrywania rzeczy element po elemencie i patrzenia na ilość informacji, których się uczysz, jest niezwykle sprytny. To jest główna idea dowodu” – powiedział Ryana Alweissa Uniwersytetu Princeton.
W tym momencie Gilmer zaczynał zbliżać się do przypuszczenia Frankla. Dzieje się tak, ponieważ łatwo jest wykazać, że w rodzinie zamkniętej na związki suma dwóch zbiorów z konieczności zawiera mniej informacji niż same zbiory — nie więcej.
Aby zrozumieć dlaczego, pomyśl o tej zamkniętej na związki rodzinie zawierającej 1,024 różne zestawy, które możesz utworzyć z liczb od 1 do 10. Jeśli wybierzesz losowo dwa z tych zestawów, otrzymasz średnio zestawy zawierające pięć elementów. (Z tych 1,024 zestawów 252 zawiera pięć elementów, co czyni ten zestaw najbardziej powszechnym rozmiarem). Prawdopodobnie skończysz z sumą zawierającą około siedmiu elementów. Ale istnieje tylko 120 różnych sposobów tworzenia zestawów zawierających siedem elementów.
Chodzi o to, że więcej jest niepewności co do zawartości dwóch losowo wybranych zestawów niż co do ich związku. Unia pochyla się do większych zestawów z większą liczbą elementów, dla których jest mniej możliwości. Kiedy bierzesz sumę dwóch zestawów w rodzinie zamkniętej przez sumę, wiesz w pewnym sensie, co dostaniesz — jak w przypadku rzutu tendencyjną monetą — co oznacza, że suma zawiera mniej informacji niż zbiory, z których się składa.
Dzięki temu Gilmer miał dowód. Wiedział, że jeśli żaden element nie pojawia się nawet w 1% zestawów, związek jest zmuszony zawierać więcej informacji. Ale związek musi zawierać mniej informacji. Dlatego musi istnieć co najmniej jeden element, który pojawia się w co najmniej 1% zestawów.
Pchnięcie do 50
Kiedy Gilmer opublikował swój dowód 16 listopada, załączył notatkę, że jego zdaniem możliwe jest użycie jego metody, aby jeszcze bardziej zbliżyć się do dowodu pełnego przypuszczenia, potencjalnie podnosząc próg do 38%.
Pięć dni później trzy różne grupy matematyków opublikowało artykuły w ciągu kilku godzin, które opierały się na pracy Gilmera, aby to zrobić. Dodatkowy Papiery następnie, ale wydaje się, że początkowy wybuch doprowadził metody Gilmera do granic możliwości; osiągnięcie 50% prawdopodobnie będzie wymagało dodatkowych nowych pomysłów.
Jednak dla niektórych autorów kolejnych artykułów osiągnięcie 38% było stosunkowo proste i zastanawiali się, dlaczego Gilmer po prostu tego nie zrobił. Najprostsze wyjaśnienie okazało się poprawne: po ponad pół dekadzie bez matematyki Gilmer po prostu nie wiedział, jak wykonać część technicznych prac analitycznych wymaganych do wykonania tego zadania.
„Byłem trochę zardzewiały i szczerze mówiąc, utknąłem” - powiedział Gilmer. „Chciałem jednak zobaczyć, dokąd zaprowadzi to społeczność”.
Jednak Gilmer uważa, że te same okoliczności, które wykluczyły go z praktyki, prawdopodobnie sprawiły, że jego dowód był możliwy.
„Tylko w ten sposób mogę wyjaśnić, dlaczego myślałem o tym problemie przez rok na studiach podyplomowych i nie zrobiłem żadnych postępów, porzuciłem matematykę na sześć lat, a potem wróciłem do problemu i dokonałem przełomu” – powiedział. „Nie wiem, jak to wyjaśnić inaczej niż uczenie maszynowe, które wypaczyło moje myślenie”.
korekta: 3 stycznia 2023 r.
Oryginalny nagłówek odnosił się do Gilmera jako „inżyniera Google”. W rzeczywistości jest badaczem.
