Absolwent pierwszego roku znajduje zestaw liczb paradoksalnych | Magazyn Quanta

Matematycy cieszą się, gdy udowadniają, że istnieją rzeczy pozornie niemożliwe. Tak jest w przypadku a nowy dowód opublikowane w marcu przez Cedric Pilatte, student pierwszego roku na Uniwersytecie Oksfordzkim.

Pilatte udowodnił, że możliwe jest stworzenie zbioru — zbioru liczb — który spełnia dwie pozornie sprzeczne właściwości. Po pierwsze, żadne dwie pary liczb w zestawie nie dają tej samej sumy. Na przykład dodaj do siebie dowolne dwie liczby w {1, 3, 5, 11}, a zawsze otrzymasz unikalny numer. Łatwo jest konstruować małe zestawy „Sydon”, takie jak ten, ale wraz ze wzrostem liczby elementów rośnie również prawdopodobieństwo, że sumy się zbiegną, niszcząc sydoński charakter zestawu.

Drugim wymogiem jest to, że zestaw musi być bardzo duży. Musi być nieskończony i powinieneś być w stanie wygenerować dowolną wystarczająco dużą liczbę, dodając do siebie co najwyżej trzy liczby w zestawie. Ta właściwość, która sprawia, że ​​zbiór jest „asymptotyczną bazą rzędu 3”, wymaga dużego, gęstego zbioru liczb. — Ciągną w przeciwnych kierunkach — powiedział Pilatte. „Zestawy Sydona muszą być małe, a baza asymptotyczna musi być duża. Nie było oczywiste, że to może zadziałać”.

Pytanie, czy taki zestaw istnieje, trwa od dziesięcioleci był pozowany przez płodnego węgierskiego matematyka Paula Erdősa i dwóch współpracowników w 1993 r. Fascynację Erdősa zbiorami Sidon można przypisać rozmowie, którą odbył w 1932 r. z ich wynalazcą Simonem Sidonem, który w tamtym czasie był zainteresowany zrozumieniem tempa wzrostu tych zestawów. (Erdős opisał później Sidona jako „bardziej szalonego niż przeciętny matematyk”, co prawie na pewno miał na myśli jako komplement).

Zbiory Sidona pojawiają się w różnych kontekstach matematycznych, w tym w teorii liczb, kombinatoryce, analizie harmonicznej i kryptografii, ale proste pytanie, jak duże mogą być, było trwałą tajemnicą, nad którą Erdős zastanawiał się przez większą część swojej kariery. Erdős wcześnie zdał sobie sprawę, że zestawy Sidon są niezwykle trudne do skalowania. W 1941 on i inny matematyk okazały że największy możliwy zbiór Sidon, którego wszystkie elementy są mniejsze niż pewna liczba całkowita N musi być mniejszy niż pierwiastek kwadratowy z N plus termin, który rośnie proporcjonalnie do czwartego pierwiastka N. (Do 1969 roku Bernt Lindström wykazałby, że jest mniejszy niż $latex sqrt{N}+sqrt[4]{N}+1$, a w 2021 inna grupa matematyków zacieśnił więzy do $latex sqrt{N}+0.998 razy sqrt[4]{N}$.) Innymi słowy, zbiory Sidon muszą być rzadkie.

Od dawna wiadomo, że zbiór Sidon nie może być asymptotyczną bazą rzędu 2, gdzie dowolną liczbę całkowitą można przedstawić jako sumę co najwyżej dwóch liczb. (Na przykład liczby nieparzyste stanowią podstawę zamówienia 2.) Jak wyjaśnił Pilatte, wykazanie tego jest tak proste, że matematycy nie zadali sobie trudu, aby to zapisać: „To, że kolejność 2 jest niemożliwa, było prawdopodobnie znane znacznie wcześniej, niż zostało to wyraźnie napisane w literaturze”. Wyjaśnił, że dzieje się tak, ponieważ „sekwencje Sidon nie mogą przekroczyć określonej gęstości, podczas gdy asymptotyczne bazy rzędu 2 są zawsze gęstsze niż ten próg, więc te dwie właściwości nie mogą być spełnione jednocześnie”.

Powszechnie uważano, że asymptotyczną bazę rzędu 3 można zbudować ze zbioru Sidon, ale udowodnienie tego było inną sprawą. „Ludzie wierzyli, że to powinna być prawda”, powiedział doradca Pilatte'a Jamesa Maynarda. „Ale były trudności z technikami, których używaliśmy”.

Zanim Pilatte podjął wyzwanie, poczyniono pewne postępy. W 2010 roku węgierski matematyk Sándor Kiss pokazał że zbiór Sidona może być asymptotyczną bazą rzędu 5 — co oznacza, że ​​każdą dostatecznie dużą liczbę całkowitą można zapisać jako sumę co najwyżej pięciu elementów zbioru — aw 2013 roku Kiss i dwóch jego kolegów okazały przypuszczenie asymptotycznej podstawy porządku 4. Dwa lata później hiszpański matematyk Javier Cilleruelo wziął te wyniki krok dalej, udowadniając, że możliwe jest skonstruowanie zbioru Sidon, który jest asymptotyczną bazą rzędu 3 + e, co oznacza, że ​​​​dowolna wystarczająco duża liczba całkowita N można zapisać jako sumę czterech członków zbioru Sidon, z których jeden jest mniejszy niż N^e dla dowolnie małych dodatnich e.

Odkrycia te uzyskano przy użyciu wariantów metody probabilistycznej zapoczątkowanej przez Erdősa, która polega na generowaniu losowego zestawu liczb całkowitych i nieznacznym modyfikowaniu go w celu utworzenia zestawu spełniającego obie właściwości.

Pilatte zdał sobie sprawę, że metoda probabilistyczna została posunięta tak daleko, jak tylko mogła. „Można uzyskać podstawę rzędu 4, stosując metody probabilistyczne, ale nie można uzyskać podstawy rzędu 3” — powiedział. „To po prostu zawodzi”.

Więc Pilatte przyjął inną taktykę, zwracając się zamiast tego do procedury, która używa logarytmów liczb pierwszych jako cegiełek budulcowych zbiorów Sydonu. Opracowany przez węgierskiego teoretyka liczb Imre Ruzsa i Cilleruelo, to podejście daje większe, gęstsze zbiory Sidon niż metoda probabilistyczna, której Pilatte potrzebował do stworzenia bazy niskiego rzędu, która również była zgodna z właściwością Sidon. Ale metoda wymagała obiektu z liczbami pierwszymi, których brakowało nawet czołowym światowym ekspertom. „Potrzebowałbyś zrozumienia liczb pierwszych, które wykracza poza wszystko, co mamy” – powiedział Pilatte. „Więc to nie było dobre”.

Poszukiwanie rozwiązania zaprowadziło Pilatte'a w nieoczekiwanym kierunku, oddalając się od addytywnej teorii liczb do świata geometrii algebraicznej, gałęzi matematyki, która bada relacje między kształtami geometrycznymi, takimi jak krzywe i powierzchnie, oraz równaniami, które je definiują. Wykorzystując pomysł Cilleruelo, Pilatte zaczął od zastąpienia liczb wielomianami, co natychmiast uczyniło problem łatwiejszym do rozwiązania.

Wielomian to wyrażenie algebraiczne składające się z sumy wyrazów, z których każdy jest iloczynem stałego współczynnika i jednej lub więcej zmiennych podniesionych do nieujemnych potęg całkowitych. Warunki można łączyć za pomocą dodawania, odejmowania i mnożenia. Na przykład 3x² + 22x + 35 to wielomian z trzema wyrazami. Rozkładanie wielomianu na czynniki oznacza rozbicie go na iloczyn innych, prostszych wielomianów. W tym przykładzie 3x² + 22x + 35 = (x + 5)(3x + 7). Nieredukowalny wielomian — taki, którego nie można rozłożyć na czynniki — jest odpowiednikiem liczby pierwszej.

Zamiana liczb całkowitych na zmienne i współczynniki może wydawać się dziwna, ale mają ze sobą więcej wspólnego, niż mogłoby się wydawać. „Okazuje się, że wielomiany zachowują się bardzo podobnie do liczb całkowitych” — powiedział kolega Pilatte'a z Oksfordu Tomasza Blooma. „Mogę je dodawać, odejmować, mnożyć, dzielić”. Pod pewnymi względami matematycy rozumieją wielomiany znacznie lepiej niż liczby. „Wszystkie te rzeczy, które z liczbami pierwszymi brzmią dla nas jak science fiction, są znane w świecie wielomianów” – powiedział Maynard.

Korzystanie ostatni wynik przez matematyka z Uniwersytetu Columbia Willa Sawina na rozkładzie nieredukowalnych wielomianów w postępach arytmetycznych, Pilatte był w stanie skonstruować zbiór, który posiadał odpowiednią ilość losowości i odpowiednią gęstość liczb, aby spełnić ograniczenia Erdősa.

„Byłem bardzo szczęśliwy”, powiedział Pilatte. „Dołączam do grupy ludzi, którzy rozwiązali problem Erdősa i to jest zabawne”.

Ale najbardziej zachwyca go zaskakujący sposób, w jaki doszedł do rozwiązania. „Fajnie, że te bardzo głębokie techniki z geometrii algebraicznej można również wykorzystać do tego prostego i konkretnego pytania dotyczącego zbiorów liczb” — powiedział.

Problemy Erdősa mają niesamowity talent do odkrywania powiązań między rzekomo niepowiązanymi gałęziami matematyki, a odkrycia, których dokonują matematycy, próbując na nie odpowiedzieć, są często bardziej znaczące niż same odpowiedzi. „Są zwodnicze, jeśli chodzi o ich głębokość, a rozwiązanie Cédrica jest tego doskonałym przykładem” — powiedział Bloom. „Jestem pewien, że Erdős byłby zachwycony”.

korekta: 5 czerwca 2023 r.
Ten artykuł pierwotnie podał przykład zestawu Sidon, który w rzeczywistości nie jest zestawem Sidon. Ten przykład został usunięty.