„Drużyna A” matematyki udowadnia kluczowy związek między dodawaniem a zbiorami | Magazyn Quanta

W losowo wybranym zestawie liczb dodawanie może szaleć.

Dodaj do siebie każdą parę z takiego zestawu, a otrzymasz nową listę, która prawdopodobnie będzie zawierać o wiele więcej liczb niż ta, od której zacząłeś. Zacznij od 10 liczb losowych, a nowa lista (zwana zbiorem sumarycznym) będzie zawierać około 50 elementów. Zacznij od 100, a suma będzie prawdopodobnie wynosić około 5,000; 1,000 losowych liczb początkowych da sumę o długości 500,000 XNUMX liczb.

Jeśli jednak początkowy zestaw ma strukturę, suma może mieć mniejszą liczbę liczb. Rozważmy inny zbiór 10-cyfrowy: wszystkie liczby parzyste od 2 do 20. Ponieważ różne pary dodadzą tę samą liczbę — 10 + 12 to to samo co 8 + 14 i 6 + 16 — suma ma tylko 19 liczb, a nie 50. Ta różnica staje się coraz większa w miarę powiększania się zbiorów. Ustrukturyzowana lista zawierająca 1,000 liczb może zawierać sumę zawierającą zaledwie 2,000 liczb.

W latach 1960. XX w. matematyk im Grzegorz Freiman rozpoczął badanie zbiorów z małymi sumsetami, próbując zbadać związek między dodawaniem a strukturą zbiorów — kluczowe połączenie definiujące pole matematyczne kombinatoryki addytywnej. Freiman poczynił imponujące postępy, udowadniając, że zbiór o małym sumie musi zawierać się w większym zbiorze, którego elementy są rozmieszczone w bardzo regularny sposób. Ale potem pole się zatrzymało. „Oryginalny dowód Freimana był niezwykle trudny do zrozumienia, do tego stopnia, że ​​nikt tak naprawdę nie był całkowicie pewien, że jest poprawny. Więc tak naprawdę nie miało to takiego wpływu, jaki mogło mieć” – powiedział Timothy Gowers, matematyk z Collège de France i Uniwersytetu w Cambridge oraz medalista Fieldsa. "Ale wtedy Imre Ruzsa wbiegł na scenę.”

W serii drugiej Papiery w latach 1990. Ruzsa ponownie udowodnił twierdzenie Freimana, przedstawiając nowy, elegancki argument. Kilka lat później, Katalin Marton, wpływowy węgierski matematyk, który zmarł w 2019 r., poprawił kwestię tego, co mały sumset oznacza dla struktury pierwotnego zbioru. Zamieniła typy elementów, które pojawiały się w zbiorze oraz rodzaj struktury, jakiej powinni szukać matematycy, myśląc, że dzięki temu matematycy będą mogli wydobyć jeszcze więcej informacji. Hipoteza Martona ma powiązania z systemami dowodowymi, teorią kodowania i kryptografią i zajmuje ważne miejsce w kombinatoryce addytywnej.

Jej przypuszczenie „wydaje się być jedną z najbardziej podstawowych rzeczy, których nie zrozumieliśmy” – stwierdziła Bena Greena, matematyk z Uniwersytetu Oksfordzkiego. „To po prostu ugruntowało wiele rzeczy, na których mi zależy”.

Green połączył siły z Gowersem, Maniery Freddiego Uniwersytetu Kalifornijskiego w San Diego i Terence tao, medalista Fieldsa na Uniwersytecie Kalifornijskim w Los Angeles, co stworzył izraelski matematyk i bloger Gil kalai zwany „Drużyna„matematyków”. Udowodnili wersję przypuszczenia w artykule udostępniony 9 listopada.

Nets Katz, matematyk z Rice University, który nie był zaangażowany w tę pracę, opisuje dowód jako „pięknie prosty” i „mniej więcej zupełnie niespodziewany”.

Następnie Tao podjął próbę sformalizowania dowodu Lean, język programowania, który pomaga matematykom weryfikować twierdzenia. W ciągu zaledwie kilku tygodni ten wysiłek się powiódł. Wczesnym rankiem we wtorek 5 grudnia Tao ogłosił że Lean udowodnił tę hipotezę bez żadnego „przepraszam” – standardowego stwierdzenia, które pojawia się, gdy komputer nie może zweryfikować określonego kroku. Jest to najgłośniejsze zastosowanie tego typu narzędzia weryfikacji od 2021 ri wyznacza punkt zwrotny w sposobie, w jaki matematycy piszą dowody w terminach zrozumiałych dla komputera. Jeśli narzędzia te staną się wystarczająco łatwe w użyciu dla matematyków, mogą zastąpić często długotrwały i uciążliwy proces wzajemnej oceny, powiedział Gowers.

Składniki dowodu gotowały się przez dziesięciolecia. Pierwsze kroki Gowersa pojawiły się na początku XXI wieku. Jednak udowodnienie tego, co Kalai nazwał „świętym Graalem” w tej dziedzinie, zajęło 2000 lat.

Grupa w grupie

Aby zrozumieć hipotezę Martona, pomaga znajomość pojęcia grupy, obiektu matematycznego składającego się ze zbioru i operacji. Pomyśl o liczbach całkowitych — nieskończonym zbiorze liczb — i operacji dodawania. Za każdym razem, gdy dodasz do siebie dwie liczby całkowite, otrzymasz kolejną liczbę całkowitą. Dodawanie podlega także kilku innym zasadom operacji na grupach, np. skojarzeniu, które pozwala na zmianę kolejności operacji: 3 + (5 + 2) = (3 + 5) + 2.

W grupie można czasami znaleźć mniejsze zbiory, które spełniają wszystkie właściwości grupy. Na przykład, jeśli dodasz dwie dowolne liczby parzyste, otrzymasz kolejną liczbę parzystą. Liczby parzyste stanowią grupę samą w sobie, co czyni je podgrupą liczb całkowitych. Natomiast liczby nieparzyste nie stanowią podgrupy. Jeśli dodasz dwie liczby nieparzyste, otrzymasz liczbę parzystą - nie z pierwotnego zestawu. Ale możesz otrzymać wszystkie liczby nieparzyste, po prostu dodając 1 do każdej liczby parzystej. Taka przesunięta podgrupa nazywana jest kosetą. Nie ma wszystkich właściwości podgrupy, ale pod wieloma względami zachowuje strukturę swojej podgrupy. Na przykład, podobnie jak liczby parzyste, wszystkie liczby nieparzyste są równomiernie rozmieszczone.

Marton przypuszczał, że jeśli masz seta, sprawdzimy A składa się z elementów grupowych, których suma nie jest wcale dużo większa niż A sama w sobie, wówczas istnieje jakaś podgrupa – nazwijmy to G – ze specjalną właściwością. Zmiana G kilka razy, aby zrobić narzuty, a te razem wzięte będą zawierać oryginalny zestaw A. Co więcej, przypuszczała, że ​​liczba cosetów nie rośnie znacznie szybciej niż rozmiar sumy - uważała, że ​​należy to powiązać czynnikiem wielomianowym, a nie znacznie szybszym wzrostem wykładniczym.

Może to brzmieć jak wysoce techniczna ciekawostka. Ale ponieważ dotyczy prostego testu — co się stanie, jeśli dodasz tylko dwa elementy do zbioru? — dla nadrzędnej struktury podgrupy jest to bardzo ważne dla matematyków i informatyków. Ten sam ogólny pomysł pojawia się, gdy informatycy próbują szyfrować wiadomości, aby można było odszyfrować tylko część wiadomości na raz. Pojawia się również w dowodach sprawdzalnych probabilistycznie, czyli formie dowodu, który informatycy mogą zweryfikować, sprawdzając tylko kilka izolowanych fragmentów informacji. W każdym z tych przypadków pracujesz z kilkoma punktami w strukturze — dekodujesz zaledwie kilka bitów długiej wiadomości lub weryfikujesz niewielką część skomplikowanego dowodu — i wyciągasz wnioski na temat większej struktury wyższego poziomu.

„Możesz albo udawać, że wszystko jest dużym podzbiorem grupy” – powiedział Tom Sanders, byłego studenta Gowersa, a obecnie kolegi Greena w Oksfordzie, lub możesz „dostać wszystko, czego chciałeś, z istnienia wielu addytywnych zbiegów okoliczności. Obie te perspektywy są przydatne.”

Ruza opublikował hipotezę Martona w 1999 roku, przyznając jej pełne uznanie. „Doszła do tego przypuszczenia niezależnie ode mnie i Freimana, a prawdopodobnie przed nami” – powiedział. „Dlatego kiedy z nią rozmawiałem, zdecydowałem się nazwać to jej przypuszczeniami”. Mimo to matematycy nazywają to obecnie wielomianową hipotezą Freimana-Ruzsy, w skrócie PFR.

Zera i jedynek

Grupy, podobnie jak wiele obiektów matematycznych, przyjmują wiele różnych form. Marton przypuszczała, że ​​jej przypuszczenia są prawdziwe dla wszystkich grup. To jeszcze nie zostało pokazane. Nowa praca udowadnia to dla szczególnego rodzaju grupy, której elementami są listy liczb binarnych, takie jak (0, 1, 1, 1, 0). Ponieważ komputery działają binarnie, grupa ta ma kluczowe znaczenie w informatyce. Ale okazało się to również przydatne w kombinatoryce addytywnej. „To jak miejsce na zabawki, w którym można się bawić i próbować różnych rzeczy” – powiedział Sanders. „Algebra jest o wiele, wiele przyjemniejsza” niż praca z liczbami całkowitymi – dodał.

Listy mają stałą długość, a każdy bit może mieć wartość 0 lub 1. Dodajesz je do siebie, dodając każdy wpis do jego odpowiednika na innej liście, zgodnie z zasadą, że 1 + 1 = 0. Zatem (0, 1, 1, 1 , 0) + (1, 1, 1, 1, 1) = (1, 0, 0, 0, 1). PFR jest próbą ustalenia, jak może wyglądać zbiór, jeśli nie jest to całkiem podgrupa, ale ma pewne cechy podobne do grupy.

Aby dokładnie określić PFR, wyobraź sobie, że masz zestaw list binarnych o nazwie A. Teraz weź każdą parę elementów z A i dodaj je. Otrzymane sumy składają się na sumę A, Zwane A + A. Jeżeli elementy A są wybierane losowo, wówczas większość sum różni się od siebie. Jeśli tam są k elementy w A, co oznacza, że ​​będzie w okolicy k²/2 elementy w sumie. Gdy k jest duży — powiedzmy 1,000 — k²/2 jest dużo większe niż k. Ale jeśli A jest podgrupą, każdy element A + A jest w A, co oznacza, że A + A jest tego samego rozmiaru co A sama.

PFR uwzględnia zbiory, które nie są losowe, ale nie są też podgrupami. W tych zestawach liczba elementów w A + A jest nieco mały — powiedzmy 10kLub 100k. „Jest to naprawdę przydatne, gdy pojęcie struktury jest znacznie bogatsze niż tylko dokładna struktura algebraiczna” – powiedział Shachara Lovetta, informatyk z Uniwersytetu Kalifornijskiego w San Diego.

Wszystkie zbiory, o których znali matematycy, a które spełniają tę właściwość, „są bardzo zbliżone do rzeczywistych podgrup” – powiedział Tao. „Taka była intuicja, że ​​w pobliżu nie było żadnych innych fałszywych grup”. Freiman przedstawił wersję tego stwierdzenia w swojej oryginalnej pracy. W 1999 Ruzsa rozszerzył twierdzenie Freimana z liczb całkowitych na ustalanie list binarnych. Udowodnił że gdy liczba elementów w A + A jest stałą wielokrotnością rozmiaru A, A jest zawarta w podgrupie.

Jednak twierdzenie Ruzsy wymagało, aby podgrupa była ogromna. Marton doszedł do wniosku, że zamiast zamykać się w jednej gigantycznej podgrupie, A może być zawarta w wielomianowej liczbie cosetów podgrupy, która nie jest większa niż zbiór pierwotny A.

„Poznaję prawdziwy pomysł, kiedy widzę prawdziwy pomysł”

Na przełomie tysiącleci Gowers natknął się na dowody Ruzsy na twierdzenie Freimana, badając inny problem dotyczący zbiorów zawierających ciągi liczb o równych odstępach. „Potrzebowałem czegoś takiego, uzyskania informacji strukturalnych na podstawie znacznie luźniejszych informacji o pewnym zestawie” – powiedział Gowers. „Miałem szczęście, że nie tak dawno temu Ruzsa stworzyła ten absolutnie wspaniały dowód”.

Gowers zaczął opracowywać potencjalny dowód wielomianowej wersji hipotezy. Jego pomysł był taki, żeby zacząć od seta A którego suma była stosunkowo mała, a następnie stopniowo manipuluj A w podgrupę. Gdyby mógł udowodnić, że powstała podgrupa była podobna do pierwotnego zbioru Az łatwością mógł stwierdzić, że przypuszczenie to było prawdziwe. Gowers podzielił się swoimi pomysłami z kolegami, ale nikt nie był w stanie przekształcić ich w pełny dowód. Chociaż strategia Gowersa w niektórych przypadkach okazała się skuteczna, w innych manipulacja trwała A dalej od pożądanego wniosku wielomianu hipotezy Freimana-Ruzsy.

W końcu boisko ruszyło dalej. W 2012 roku Sandersa prawie udowodnione PFR. Jednak liczba przesuniętych podgrup, których potrzebował, przekraczała poziom wielomianu, choć tylko trochę. „Kiedy to zrobił, oznaczało to, że stał się on mniej pilną sprawą, ale nadal stanowił naprawdę fajny problem, do którego darzę wielkim sentymentem” – powiedział Gowers.

Jednak pomysły Gowersa przetrwały w pamięci i na dyskach twardych jego kolegów. „To naprawdę dobry pomysł” – powiedział Green, który również był uczniem Gowersa. „Poznaję prawdziwy pomysł, kiedy widzę prawdziwy pomysł”. Tego lata Green, Manners i Tao w końcu wyzwolili idee Gowersa z czyśćca.

Green, Tao i Manners zajmowali się współpracą przez 37 stron, zanim pomyśleli o powrocie do 20-letnich pomysłów Gowersa. W dniu 23 czerwca papier, z powodzeniem wykorzystali koncepcję z teorii prawdopodobieństwa zwaną zmiennymi losowymi do zbadania struktury zbiorów o małych sumach. Dokonując tej zmiany, grupa mogła manipulować swoimi setami z większą finezją. „Radzenie sobie ze zmiennymi losowymi jest w jakiś sposób znacznie mniej sztywne niż radzenie sobie ze zbiorami” – powiedział Manners. W przypadku zmiennej losowej „mogę nieznacznie poprawić jedno z prawdopodobieństw, co może dać mi lepszą zmienną losową”.

Korzystając z tej probabilistycznej perspektywy, Green, Manners i Tao mogli przejść od pracy z liczbą elementów w zbiorze do pomiaru informacji zawartej w zmiennej losowej, wielkości zwanej entropią. Entropia nie była nowością w kombinatoryce addytywnej. Faktycznie, Tao próbował spopularyzować tę koncepcję pod koniec XXI wieku. Ale nikt jeszcze nie próbował użyć tego w przypadku hipotezy Freimana-Ruzsy dotyczącej wielomianu. Green, Manners i Tao odkryli, że jest potężny. Ale nadal nie byli w stanie udowodnić tej hipotezy.

W miarę jak grupa przeżuwała nowe wyniki, zdała sobie sprawę, że w końcu stworzyła środowisko, w którym uśpione pomysły Gowersa mogą rozkwitnąć. Gdyby zmierzyli rozmiar zbioru na podstawie jego entropii, a nie liczby elementów, szczegóły techniczne mogłyby działać znacznie lepiej. „W pewnym momencie zdaliśmy sobie sprawę, że stare pomysły Tima sprzed 20 lat mają większe szanse powodzenia niż te, których próbowaliśmy” – powiedział Tao. „Dlatego ponownie włączyliśmy Tima do projektu. A potem wszystkie elementy zaskakująco ładnie do siebie pasują.”

Jednak zanim zebrano dowód, trzeba było ustalić wiele szczegółów. „To było trochę głupie, że cała nasza czwórka była niesamowicie zajęta innymi sprawami” – powiedział Manners. „Chcesz opublikować ten wspaniały wynik i powiedzieć o tym światu, ale tak naprawdę nadal musisz napisać swoje oceny śródokresowe”. W końcu grupa przeforsowała się i 9 listopada opublikowała swoją pracę. Udowodnili, że jeśli A + A nie jest większy niż k razy większy A, następnie A może obejmować nie więcej niż około k¹² przesunięcia podgrupy nie większej niż A. To potencjalnie ogromna liczba zmian. Ale jest to wielomian, więc nie rośnie wykładniczo szybciej, jak k staje się większy, tak jakby k były w wykładniku.

Kilka dni później Tao zaczęły sformalizować dowód. Wspólnie prowadził projekt formalizacji, korzystając z pakietu kontroli wersji GitHub do koordynowania wkładu 25 wolontariuszy na całym świecie. Użyli narzędzia tzw Plan opracowany przez Patryka Massota, matematyka na uniwersytecie Paris-Saclay, do zorganizowania wysiłków w celu przetłumaczenia z tego, co Tao nazywa „Matematyczny angielski” na kod komputerowy. Blueprint może między innymi stworzyć chart przedstawiający różne logiczne etapy dowodu. Kiedy wszystkie bąbelki pokryły się, jak to określił Tao, „pięknym odcieniem zieleni”, zespół skończył. Odkryli kilka bardzo drobnych literówek w gazecie – w Internecie wiadomośćTao zauważył, że „najbardziej interesujące matematycznie części projektu można było stosunkowo łatwo sformalizować, ale najdłużej trwały „oczywiste” kroki techniczne”.

Marton zmarła zaledwie kilka lat przed potwierdzeniem jej słynnego przypuszczenia, ale dowody ją powtarzają praca życia o entropii i teorii informacji. „Wszystko działa znacznie lepiej, gdy robisz to w środowisku entropii, niż w środowisku, w którym próbowałem to zrobić” – powiedział Gowers. „Dla mnie nadal wydaje się to nieco magiczne”.

Quanta przeprowadza serię ankiet, aby lepiej służyć naszym odbiorcom. Weź nasze ankieta dla czytelników matematyki i zostaniesz wpisany, aby wygrać za darmo Quanta towar.