Student rozwiązuje długotrwały problem dotyczący granic dodawania

Oryginalna wersja tej historii ukazała się w magazynie Quanta .

Najprostsze idee matematyczne mogą być jednocześnie najbardziej zagmatwane.

Weźmy dodawanie. To prosta operacja: Jedną z pierwszych matematycznych prawd, których się uczymy, jest to, że 1 plus 1 równa się 2. Jednak matematycy wciąż mają wiele pytań bez odpowiedzi na temat rodzajów wzorców, które dodawanie może wywoływać. „To jedna z najbardziej podstawowych rzeczy, jakie możesz zrobić” — powiedział Benjamin Bedert , student studiów podyplomowych na Uniwersytecie Oksfordzkim. „W jakiś sposób wciąż jest to bardzo tajemnicze na wiele sposobów”.

Zgłębiając tę ​​tajemnicę, matematycy mają nadzieję również zrozumieć granice mocy dodawania. Od początku XX wieku badają naturę zbiorów „bez sumy” — zbiorów liczb, w których żadne dwie liczby w zbiorze nie sumują się do trzeciej. Na przykład dodaj dowolne dwie liczby nieparzyste, a otrzymasz liczbę parzystą. Zbiór liczb nieparzystych jest zatem bez sumy.

W artykule z 1965 r. płodny matematyk Paul Erdős zadał proste pytanie o to, jak powszechne są zbiory bez sum. Jednak przez dziesięciolecia postęp w rozwiązaniu tego problemu był nieznaczny.

„To brzmi jak coś bardzo podstawowego, o czym mieliśmy szokująco mało pojęcia” – powiedział Julian Sahasrabudhe , matematyk z Uniwersytetu Cambridge.

Aż do lutego. Sześćdziesiąt lat po tym, jak Erdős postawił swój problem, Bedert go rozwiązał. Pokazał, że w każdym zbiorze złożonym z liczb całkowitych — dodatnich i ujemnych liczb liczonych — istnieje duży podzbiór liczb, które muszą być sumowo wolne . Jego dowód sięga głębin matematyki, doskonaląc techniki z różnych dziedzin, aby odkryć ukrytą strukturę nie tylko w zbiorach sumowo wolnych, ale także w wielu innych sytuacjach.

„To fantastyczne osiągnięcie” – powiedział Sahasrabudhe.

Erdős wiedział, że każdy zbiór liczb całkowitych musi zawierać mniejszy podzbiór bez sumy. Rozważ zbiór {1, 2, 3}, który nie jest bez sumy. Zawiera on pięć różnych podzbiorów bez sumy, takich jak {1} i {2, 3}.

Erdős chciał wiedzieć, jak daleko sięga to zjawisko. Jeśli masz zbiór z milionem liczb całkowitych, jak duży jest jego największy podzbiór bez sumy?

W wielu przypadkach jest ogromna. Jeśli wybierzesz milion liczb całkowitych losowo, około połowa z nich będzie nieparzysta, co da ci podzbiór bez sumy z około 500 000 elementów.

W swojej pracy z 1965 r. Erdős wykazał — w dowodzie liczącym zaledwie kilka linijek, uznanym przez innych matematyków za genialny — że dowolny zbiór N liczb całkowitych ma podzbiór sumaryczny składający się z co najmniej N /3 elementów.

Nadal nie był zadowolony. Jego dowód dotyczył średnich: znalazł zbiór podzbiorów bez sumy i obliczył, że ich średni rozmiar wynosił N /3. Ale w takim zbiorze największe podzbiory są zazwyczaj uważane za znacznie większe niż średnia.

Erdős chciał zmierzyć wielkość tych bardzo dużych podzbiorów wolnych od sum.

Matematycy wkrótce wysunęli hipotezę, że wraz ze wzrostem zbioru największe podzbiory sum-free staną się znacznie większe niż N /3. W rzeczywistości odchylenie będzie rosło nieskończenie duże. Ta prognoza — że rozmiar największego podzbioru sum-free wynosi N /3 plus pewne odchylenie, które rośnie do nieskończoności z N — jest obecnie znana jako hipoteza zbiorów sum-free.

„Zaskakujące jest, że to proste pytanie wydaje się przedstawiać znaczne trudności” – napisał Erdős w swoim oryginalnym artykule – „ale być może nie dostrzegamy tego, co oczywiste”.

Przez dziesięciolecia nic oczywistego się nie ujawniało. Nikt nie mógł ulepszyć dowodu Erdősa. „Im dłużej trwało, zanim ludzie nie byli w stanie ulepszyć tego prostego ograniczenia, tym większego znaczenia nabierał ten problem” — powiedział Ben Green , opiekun doktorski Bederta w Oksfordzie. I dodał, że to był dokładnie ten rodzaj problemu, w którym „bardzo, bardzo trudno jest zrobić cokolwiek lepiej”.

Po 25 latach bez poprawy pierwotnego wyniku Erdősa matematycy w końcu zaczęli powoli iść naprzód. W 1990 r. dwóch badaczy udowodniło, że każdy zbiór N liczb całkowitych ma podzbiór bez sumy z co najmniej N /3 + 1/3 elementów, częściej zapisywany jako ( N + 1)/3.

Ale ponieważ rozmiar zbioru jest zawsze liczbą całkowitą, zwiększenie o 1/3 często nie ma znaczenia. Na przykład, jeśli wiesz, że podzbiór bez sumy musi mieć co najmniej 5/3 elementów, oznacza to, że jego rozmiar jest gwarantowany na poziomie 2 lub więcej. Jeśli dodasz 1/3 do 5/3, twoja odpowiedź nadal będzie wynosić 2. „To zabawne, oznacza to, że tak naprawdę nie zawsze go poprawia” — powiedział David Conlon z California Institute of Technology. „Poprawia go tylko wtedy, gdy N jest podzielne przez 3”.

W 1997 roku legenda matematyki Jean Bourgain podniósł granicę do ( N + 2)/3. Wynik mógł wydawać się niewart wzmianki, ale w artykule Bourgaina ukryty był zaskakujący przełom. Opisał pomysł, jak udowodnić, że największe podzbiory bez sumy będą dowolnie większe. Po prostu nie potrafił ustalić szczegółów, aby przekształcić to w pełny dowód.

„W artykule jest mniej więcej tak: oto jak próbowałem rozwiązać problem i dlaczego mi się nie udało” – powiedział Sahasrabudhe.

Bourgain opierał się na wielkości zwanej normą Littlewood, która mierzy strukturę danego zbioru. Ta wielkość, pochodząca z dziedziny matematyki zwanej analizą Fouriera, ma tendencję do bycia dużą, jeśli zbiór jest bardziej losowy, i małą, jeśli zbiór wykazuje większą strukturę.

Bourgain wykazał, że jeśli zbiór składający się z N elementów ma dużą normę Littlewooda, to musi także mieć zbiór wolny od sumy, który jest znacznie większy niż N /3. Nie udało mu się jednak poczynić postępów w przypadku, gdy zbiór ma małą normę Littlewooda.

„Bourgain jest znany ze swojej kompetencji” — powiedziałSean Eberhard z University of Warwick. „To bardzo uderzający wskaźnik tego, jak trudny jest ten problem”.

Bourgain ostatecznie musiał użyć innego argumentu, aby uzyskać swoje ograniczenie ( N + 2)/3. Ale matematycy czytali między wierszami: mogliby użyć normy Littlewood, aby całkowicie rozstrzygnąć przypuszczenie. Musieli tylko wymyślić, jak radzić sobie ze zbiorami z małą normą Littlewood.

Był powód do optymizmu: Matematycy już wiedzieli o zbiorach z małą normą Littlewood, które mają ogromne podzbiory sum-free. Te zbiory, zwane progresjami arytmetycznymi, składają się z równomiernie rozmieszczonych liczb, takich jak {5, 10, 15, 20}. Matematycy podejrzewali, że każdy zbiór z małą normą Littlewood ma bardzo specyficzną strukturę — ​​że jest mniej więcej zbiorem wielu różnych progresji arytmetycznych (z kilkoma poprawkami). Mieli nadzieję, że jeśli uda im się to wykazać, będą mogli użyć tej własności, aby udowodnić, że każdy zbiór z małą normą Littlewood ma duży podzbiór sum-free.

Ale to zadanie nie było łatwe. „Z pewnością próbowałem udowodnić hipotezę bez sumy, używając idei [Bourgaina]”, powiedział Green, ale „nadal niewiele rozumiemy o strukturze zbiorów z małą normą Littlewooda. Wszystko, co ma związek z Littlewoodem, jest trudne”.

I tak, chociaż matematycy nadal wierzyli w strategię Bourgaina opartą na koncepcji Littlewooda, nic się nie wydarzyło.

Minęły ponad dwie dekady. Następnie, jesienią 2021 r., Benjamin Bedert rozpoczął studia podyplomowe.

Mając Greena jako swojego promotora doktorskiego, nieuniknione było, że Bedert natknie się na hipotezę zbiorów wolnych od sumy. Strona internetowa Greena zawiera listę 100 otwartych problemów ; ten pojawia się jako pierwszy.

Bedert przejrzał listę wkrótce po rozpoczęciu studiów podyplomowych. Początkowo unikał problemu zbiorów sum-free. „Pomyślałem sobie, że to jest supertrudne, nie będę o tym myślał” – wspominał. „Zostawię to na przyszłość”.

Przyszłość nadeszła wystarczająco szybko. Latem 2024 r. Bedert zdecydował, że jest gotowy na bardziej ryzykowny projekt. „Do tej pory udowodniłem całkiem niezłe wyniki w moim doktoracie i w pewnym sensie złożyłem już rozprawę” — powiedział. „Zacząłem myśleć o tych bardziej, jak sądzę, znanych problemach”.

Przeczytał artykuł Bourgaina z 1997 r. i zaczął rozmyślać nad tym, jak wdrożyć plan Littlewooda. Niemal natychmiast wpadł na pomysł, jak podejść do problemu zbiorów z małą normą Littlewooda.

Dotychczas było zbyt trudno pokazać, że zbiory z małą normą Littlewooda zawsze przypominają zbiory progresji arytmetycznych. Ale Bedert pomyślał, że może być przydatne udowodnienie czegoś bardziej osiągalnego: że nawet jeśli zbiory te nie są dosłownie zbudowane z progresji arytmetycznych, to jednak mają pewne kluczowe, podobne do progresji własności.

W niedawnym projekcie Bedert natknął się na to, co uznał za dobrego kandydata na własność, na której mógłby się skupić. W postępach arytmetycznych istnieje wiele grup liczb, które mają tę samą sumę. Na przykład w zbiorze liczb parzystych (który jest postępem arytmetycznym) 4 + 8 ma tę samą sumę co 2 + 10 i 2 + 4 + 6. Bedert uważał, że wystarczy pokazać, że zbiory z małą normą Littlewooda zawsze spełniają tę własność.

W ciągu kilku tygodni udało mu się udowodnić, że własność jest prawdziwa. Ale czy wynik dałby mu poziom podobieństwa do postępów arytmetycznych, jakiego potrzebował, aby udowodnić hipotezę zbiorów sumarycznych?

„Zdecydowanie byłem podekscytowany” – powiedział. „Potem zdałem sobie sprawę, że jest jeszcze tak wiele do zrobienia”.

Po pierwsze, Bedert wykazał, że każdy zbiór z małą normą Littlewooda można „odwzorować” na drugi zbiór, który jeszcze bardziej przypominał progresje arytmetyczne. Podejrzewał, że to właśnie w tych nowych zbiorach znajdzie duże podzbiory wolne od sum.

Ostatnim zadaniem było faktyczne pokazanie, jaki będzie rozmiar takiego podzbioru bez sumy. „Podczas przerwy świątecznej obsesyjnie myślałem o tym problemie” — powiedział Bedert. „Do Nowego Roku wciąż nie znalazłem ostatniego elementu układanki”.

Potem, kilka dni po powrocie do Oksfordu w styczniu, to do niego dotarło. „Nie jestem pewien, skąd się to wzięło” – powiedział. „Może te pomysły krążą w twojej głowie przez jakiś czas, a potem [w końcu] wyciągasz coś, co działa”.

Przedstawił strukturę swoich zbiorów za pomocą narzędzia zwanego transformacją Fouriera, a następnie zmodyfikował dowód z 1981 r. , aby pokazać, że niektóre z poszczególnych składników tej reprezentacji muszą mieć dużą normę Littlewooda. Ponieważ Bourgain pokazał już, jak obsługiwać zbiory z dużymi normami Littlewooda, to zakończyło dowód.

Ostatecznie Bedert wykazał, że każdy zbiór N liczb całkowitych ma podzbiór bez sumy składający się z co najmniej N /3 + log(log N ) elementów. Dla wielu wartości N daje to podzbiór bez sumy, który jest tylko nieznacznie większy niż średni rozmiar Erdősa wynoszący N /3. Nawet jeśli N jest tak duże jak 10 ¹⁰⁰ , na przykład, log(log N ) wynosi tylko około 5. Ale gdy N zbliża się do nieskończoności, tak samo dzieje się z różnicą w granicach Bederta i Erdősa — rozstrzygając w ten sposób przypuszczenie.

„To naprawdę niesamowity wynik” — powiedział Yifan Jing z Ohio State University. Jing, który również był pod opieką Greena, przypisuje to osiągnięcie intensywnemu skupieniu Bederta. „Benjamin naprawdę włożył wiele wysiłku w modyfikację dowodu Bourgaina i sprawienie, by zadziałał” — powiedział. „Poświęca on o wiele więcej czasu niż inni ludzie na ten sam problem”.

Jest jeszcze wiele do zrozumienia na temat podzbiorów wolnych od sumy — a zatem na temat stopnia, w jakim dodawanie wpływa na strukturę liczb całkowitych. Na przykład wynik Bederta rozwiązuje kwestię, czy największy podzbiór wolny od sumy staje się nieskończenie większy niż N /3. Ale matematycy nie wiedzą dokładnie, jak szybko to odchylenie może rosnąć. Dzięki artykułowi z 2014 r. autorstwa Greena i dwóch współpracowników wiedzą, że odchylenie rośnie wolniej niż N . Ale, powiedział Green, „pozostaje ogromna luka” między tą górną granicą N a dolną granicą log(log N ) Bederta.

Praca ta dostarcza również nowych spostrzeżeń na temat zbiorów, które mają małą normę Littlewooda. Takie zbiory są podstawowymi obiektami w dziedzinie analizy, ale są bardzo trudne do zbadania. Wynik Bederta pomógł matematykom lepiej zrozumieć ich strukturę, którą Green i inni mają nadzieję nadal badać. „To piękne, to interesujące, to wydaje się naturalne” — powiedział Eberhard. „Chcesz rozwiązać tajemnicę, prawda?”

Dla Sahasrabudhe wniosek jest prosty. „Stary i trudny problem rozwiązany przez genialnego dzieciaka” – powiedział. „To, nad czym pracuje, jest subtelne i trudne w obsłudze. To naprawdę ładny wynik”.

Oryginalny artykuł przedrukowano za zgodą Quanta Magazine , redakcyjnie niezależnej publikacji Fundacji Simonsa , której misją jest pogłębianie wiedzy naukowej wśród społeczeństwa poprzez relacjonowanie osiągnięć badawczych i trendów w matematyce, fizyce i naukach biologicznych.