Sztuczki matematyczne do ujarzmienia średniego dystansu | Magazyn Quanta

Jak dotąd w tym roku, Quanta opisał trzy główne postępy w teorii Ramseya, studium, jak uniknąć tworzenia matematycznych wzorców. The pierwszy wynik nałóż nowy limit na to, jak duży może być zestaw liczb całkowitych, który nie zawiera trzech równomiernie rozmieszczonych liczb, takich jak {2, 4, 6} lub {21, 31, 41}. The Dopiero i trzeci podobnie nałóż nowe ograniczenia na rozmiar sieci bez skupisk punktów, które są albo wszystkie połączone, albo wszystkie odizolowane od siebie.

Dowody odnoszą się do tego, co dzieje się, gdy zaangażowane liczby rosną nieskończenie duże. Paradoksalnie, czasami może to być łatwiejsze niż radzenie sobie z irytującymi ilościami w świecie rzeczywistym.

Rozważmy na przykład dwa pytania dotyczące ułamka o naprawdę dużym mianowniku. Możesz zapytać, jakie jest rozwinięcie dziesiętne, powiedzmy, 1/42503312127361. Możesz też zapytać, czy liczba ta zbliży się do zera w miarę wzrostu mianownika. Pierwsze pytanie jest konkretnym pytaniem o rzeczywistą wielkość i jest trudniejsze do obliczenia niż drugie, które pyta, jak ilość 1/n zmieni się „asymptotycznie” jako n rośnie. (Zbliża się coraz bardziej do 0.)

„To problem nękający całą teorię Ramseya” – powiedział Williama Gasarcha, informatyk z University of Maryland. „Teoria Ramseya znana jest z asymptotycznie bardzo dobrych wyników”. Jednak analiza liczb mniejszych od nieskończoności wymaga zupełnie innego zestawu narzędzi matematycznych.

Gasarch przestudiował pytania z teorii Ramseya dotyczące liczb skończonych, które są zbyt duże, aby problem można było rozwiązać brutalną siłą. W jednym projekcie przyjął skończoną wersję pierwszego z tegorocznych przełomów — lutowego artykułu o Zandera Kelleya, doktorant na Uniwersytecie Illinois, Urbana-Champaign i Raghu Meka z Uniwersytetu Kalifornijskiego w Los Angeles. Kelley i Meka znaleźli nową górną granicę liczby liczb całkowitych z przedziału od 1 do N możesz umieścić w zestawie, unikając progresji trzyterminowych lub schematów równomiernie rozmieszczonych liczb.

Chociaż wynik Kelleya i Meki ma zastosowanie, nawet jeśli N jest stosunkowo mały, nie daje w tym przypadku szczególnie użytecznej granicy. Dla bardzo małych wartości N, lepiej trzymać się bardzo prostych metod. Jeśli N to, powiedzmy, 5, po prostu spójrz na wszystkie możliwe zestawy liczb od 1 do Ni wybierz największy bez progresji: {1, 2, 4, 5}.

Ale liczba różnych możliwych odpowiedzi rośnie bardzo szybko i sprawia, że ​​stosowanie tak prostej strategii staje się zbyt trudne. Istnieje ponad 1 milion zestawów składających się z liczb od 1 do 20. Jest ich ponad 10⁶⁰ używając liczb od 1 do 200. Znalezienie najlepszego zestawu wolnego od progresji dla tych przypadków wymaga ogromnej dawki mocy obliczeniowej, nawet przy zastosowaniu strategii poprawiających wydajność. „Musisz być w stanie wycisnąć z rzeczy dużo wydajności” – powiedział Jamesa Glenna, informatyk z Uniwersytetu Yale. W 2008 roku Gasarch, Glenn i Clyde'a Kruskala z Uniwersytetu Maryland napisał program aby znaleźć największe zestawy wolne od progresji do an N ze 187. (Poprzednia praca dała odpowiedzi do 150, a także do 157). Pomimo listy sztuczek, ich program trwał miesiące, powiedział Glenn.

Aby zmniejszyć obciążenie obliczeniowe, zespół zastosował proste testy, które uniemożliwiły programowi poszukiwanie w ślepy zaułek i podzielił swoje zbiory na mniejsze części, które analizowali osobno.

Gasarch, Glenn i Kruskal wypróbowali także kilka innych strategii. Jeden obiecujący pomysł opierał się na przypadkowości. Prostym sposobem na wymyślenie zestawu bez progresji jest umieszczenie 1 w swoim zestawie, a następnie zawsze dodanie kolejnej liczby, która nie tworzy postępu arytmetycznego. Postępuj zgodnie z tą procedurą, aż trafisz liczbę 10, a otrzymasz zestaw {1, 2, 4, 5, 10}. Ale okazuje się, że ogólnie nie jest to najlepsza strategia. „A co jeśli nie zaczniemy od 1?” — powiedział Gasarch. „Jeśli zaczniesz w przypadkowym miejscu, faktycznie pójdzie ci lepiej”. Dodał, że badacze nie mają pojęcia, dlaczego losowość jest tak przydatna.

Obliczanie skończonych wersji dwóch innych nowych wyników teorii Ramseya jest jeszcze bardziej irytujące niż określanie wielkości zestawów wolnych od progresji. Wyniki te dotyczą sieci matematycznych (zwanych grafami) złożonych z węzłów połączonych liniami zwanymi krawędziami. Liczba Ramseya r(s, t) to najmniejsza liczba węzłów, jaką musi mieć graf, zanim niemożliwe stanie się uniknięcie włączenia którejkolwiek z grup s połączone węzły lub t odłączone. Obliczenie liczby Ramseya jest takim bólem głowy r(5, 5) jest nieznany — jest gdzieś między 43 a 48.

W 1981, Brendana McKay'a, obecnie informatyk z Australian National University, napisał program o nazwie nauty, który miał uprościć obliczanie liczb Ramseya. Nauty zapewnia, że ​​badacze nie marnują czasu na sprawdzanie dwóch wykresów, które są po prostu odwróconymi lub obróconymi wersjami siebie nawzajem. „Jeśli ktoś jest w okolicy i nie używa nauty, gra się kończy. Musisz to wykorzystać – powiedział Stanisława Radziszowskiego, matematyk z Rochester Institute of Technology. Mimo to ilość wymaganych obliczeń jest prawie niezrozumiała. W 2013 Radziszowski i Jana Goedgebeura udowodniłem to r(3, 10) wynosi co najwyżej 42. „Myślę, że zajęło to prawie 50 lat procesora” — powiedział Goedgebeur, informatyk z Uniwersytetu KU Leuven w Belgii.

Jeśli nie możesz obliczyć dokładnej liczby Ramseya, możesz spróbować zawęzić jej wartość za pomocą przykładów. Gdybyś znalazł 45-węzłowy wykres bez pięciu węzłów, które były wszystkie połączone i bez pięciu węzłów, które były rozłączone, udowodniłoby to, że r(5, 5) jest większe niż 45. Matematycy badający liczby Ramseya myśleli, że znalezienie tych przykładów, zwanych wykresami Ramseya, będzie proste - mówi Radziszowski. Ale tak nie było. „Było oczekiwanie, że ładne, fajne konstrukcje matematyczne dadzą najlepsze możliwe konstrukcje, a my po prostu potrzebujemy więcej ludzi do pracy nad tym” – powiedział. „Coraz bardziej czuję, że jest chaotycznie”.

Losowość jest zarówno przeszkodą w zrozumieniu, jak i użytecznym narzędziem. Geoffrey Exo, informatyk z Indiana State University, spędził lata udoskonalając losowe metody generowania wykresów Ramseya. W papier 2015 ogłaszając dziesiątki nowych, bijących rekordy wykresów Ramseya, Exoo i Milos Tatarevic wygenerowali losowe wykresy, a następnie stopniowo je poprawiali, usuwając lub dodając krawędzie, które zmniejszały liczbę niechcianych klastrów, aż do znalezienia wykresu Ramseya. Jednak techniki Exoo są tak samo sztuką jak cokolwiek innego, powiedział Radziszowski. Czasami wymagają od niego połączenia wielu metod lub oceny, od jakiego rodzaju wykresów zacząć. „Wielu, wielu ludzi tego próbuje i nie mogą tego zrobić” – powiedział Radziszowski.

Techniki opracowane w celu generowania wykresów Ramseya mogą być kiedyś bardziej przydatne, powiedział Goedgebeur, który to zrobił pracował nad tworzenie innych rodzajów wykresów, takich jak wykresy przedstawiające związki chemiczne. „Nie jest nieprawdopodobne, że techniki te można również przenieść i dostosować, aby pomóc w wydajniejszym generowaniu innych klas wykresów (i odwrotnie)”, napisał w e-mailu.

Jednak dla Radziszowskiego powód badania małych liczb Ramseya jest znacznie prostszy. „Ponieważ jest otwarta, ponieważ nikt nie wie, jaka jest odpowiedź” – powiedział. „Trywialne przypadki wykonujemy ręcznie; trochę większy, potrzebujesz komputera, a trochę większy, nawet komputer nie jest wystarczająco dobry. I tak pojawia się wyzwanie”.