Hipoteza Erdősa – Strausa

Nierozwiązany problem z matematyki :

Czy mieć dodatnie rozwiązanie całkowitoliczbowe dla każdej liczby całkowitej ?

Erdősa – Strausa jest niesprawdzonym stwierdzeniem w teorii liczb . Przypuszczenie jest takie, że dla każdej liczby całkowitej która wynosi 2 lub więcej, istnieją dodatnie liczby całkowite y i dla których

Innymi słowy, liczbę jako sumę trzech jednostkowych .

Hipoteza została nazwana na cześć Paula Erdősa i Ernsta G. Strausa , którzy sformułowali ją w 1948 roku, ale jest powiązana ze znacznie bardziej starożytną matematyką; sumy ułamków jednostkowych, takie jak ten w tym zadaniu, są znane jako ułamki egipskie , ze względu na ich zastosowanie w matematyce starożytnego Egiptu . Hipoteza Erdősa – Strausa jest jedną z wielu hipotez Erdősa i jednym z wielu nierozwiązanych problemów matematycznych dotyczących równań diofantycznych .

Chociaż rozwiązanie nie jest znane dla wszystkich wartości n , nieskończenie wiele wartości w pewnych nieskończonych ciągach arytmetycznych ma proste wzory na ich rozwiązanie, a pominięcie tych znanych wartości może przyspieszyć wyszukiwanie kontrprzykładów . Ponadto te wyszukiwania muszą uwzględniać tylko wartości, pierwszymi , ponieważ każdy złożony kontrprzykład miałby mniejszy kontrprzykład wśród swoich czynników pierwszych . Wyszukiwania komputerowe potwierdziły prawdziwość przypuszczenia aż do .

Jeśli przypuszczenie zostanie przeformułowane, aby umożliwić ujemne ułamki jednostkowe, wówczas wiadomo, że jest prawdziwe. Zbadano również uogólnienia przypuszczenia na ułamki o liczniku 5 lub większym.

Tło i historia

Kiedy liczba wymierna jest rozkładana na sumę ułamków jednostkowych, rozwinięcie nazywa się ułamkiem egipskim . Ten sposób zapisywania ułamków wywodzi się z matematyki starożytnego Egiptu , w sposób zamiast w bardziej nowoczesnej postaci ułamka wulgarnego z licznikiem za i mianownik . Egipcjanie stworzyli tabele ułamków egipskich dla ułamków jednostkowych pomnożonych przez dwa, liczby, które we współczesnej notacji byłyby zapisywane , jak tabela Rhind Mathematical w tych tabelach większość tych rozszerzeń używa dwóch lub trzech terminów. Tabele te były potrzebne, ponieważ oczywiste rozszerzenie nie było dozwolone: ​​Egipcjanie wymagali, aby wszystkie ułamki w ułamku egipskim różniły się od siebie. Ten sam wymóg, aby wszystkie ułamki były różne, jest czasami nakładany w hipotezie Erdősa – Strausa, ale nie ma to istotnego znaczenia dla problemu, ponieważ dla dowolnego rozwiązania gdzie ułamki jednostkowe nie są różne, można przekształcić w rozwiązanie, w którym wszystkie są różne; patrz poniżej .

Chociaż Egipcjanie nie zawsze znajdowali rozwinięcia przy użyciu jak najmniejszej liczby wyrazów, późniejsi matematycy byli zainteresowani pytaniem, jak mało wyrazów jest potrzebnych. Każdy ułamek rozwinięcie co najwyżej terminów, więc w szczególności za potrzebuje co najwyżej dwóch terminów, potrzebuje co najwyżej trzech terminów, a co najwyżej warunki. Dla dwa terminy, a dla czasami potrzebne dla obu tych liczników znana jest maksymalna liczba terminów, które mogą być potrzebne. Jednak dla nie wiadomo, czy czasami potrzebne są cztery terminy, czy też możliwe jest wyrażenie wszystkich ułamków formy używając tylko trzech ułamków jednostkowych; to jest hipoteza Erdősa – Strausa. znalezienia dla wszystkich maksymalnej liczby wyrazów potrzebnych w rozwinięciach ułamków za .

Jednym ze sposobów znajdowania krótkich (ale nie zawsze najkrótszych) rozwinięć jest algorytm zachłanny dla ułamków egipskich , po raz pierwszy opisany w 1202 roku przez Fibonacciego w jego książce Liber Abaci . Ta metoda wybiera jeden ułamek jednostkowy na raz, na każdym etapie wybierając największy możliwy ułamek jednostkowy, który nie spowodowałby, że rozszerzona suma przekroczy liczbę docelową. Po każdym kroku licznik ułamka pozostałego do rozwinięcia zmniejsza się, więc całkowita liczba kroków nigdy nie może przekroczyć początkowego licznika, ale czasami jest mniejsza. gdy zostanie zastosowany do algorytm użyje dwóch terminów, ilekroć modulo 3, ale istnieje dwu- rozwinięcie terminu, ilekroć , który wynosi 2 modulo 3, słabszy warunek. Dla liczb postaci algorytm zachłanny wygeneruje rozwinięcie czteroczłonowe, ilekroć 1 modulo 4, oraz rozwinięcie z mniejszą liczbą wyrazów 4 W przeciwnym razie. Zatem inny sposób przeformułowania hipotezy Erdősa – Strausa dotyczy pytania, czy istnieje inna metoda tworzenia ułamków egipskich, przy użyciu mniejszej maksymalnej liczby terminów dla liczb. }

Hipoteza Erdősa – Strausa została sformułowana w 1948 roku przez Paula Erdősa i Ernsta G. Strausa i opublikowana przez Erdősa (1950) . Richard Obláth opublikował również wczesną pracę nad przypuszczeniem, artykuł napisany w 1948 r. I opublikowany w 1950 r., W którym rozszerzył wcześniejsze obliczenia Strausa i Harolda N. Shapiro w celu zweryfikowania przypuszczenia dla wszystkich. n ≤ 10 .

Sformułowanie

Przypuszczenie stwierdza, że ​​dla każdej liczby całkowitej liczby całkowite takie, że , i

Na przykład dla istnieją dwa rozwiązania: n = 5 {\ displaystyle n = 5}

Mnożenie obu stron równania przez prowadzi do równoważnej postaci wielomianu dla problemu.

Wyraźne ułamki jednostkowe

aby liczby i były różne od siebie, tak jak zrobiliby to Egipcjanie, podczas gdy inni pozwalają być Dla nie ma znaczenia, czy muszą być różne: jeśli istnieje rozwiązanie z dowolnymi trzema liczbami całkowitymi, to istnieje rozwiązanie z różnymi liczbami całkowitymi. Dzieje się tak, ponieważ dwa identyczne ułamki jednostkowe można zastąpić jednym z dwóch następujących rozszerzeń:

(w zależności od tego, czy powtarzany ułamek ma parzysty czy nieparzysty mianownik) i to zastępowanie można powtarzać, aż nie pozostaną żadne zduplikowane ułamki. n jednak jedynymi rozwiązaniami są permutacje .

Rozwiązania liczb ujemnych

Hipoteza Erdősa – Strausa wymaga, aby , i dodatnie Wymóg ten ma zasadnicze znaczenie dla trudności problemu. Nawet bez tego złagodzenia hipoteza Erdősa – Strausa jest trudna tylko dla nieparzystych wartości , problem można by rozwiązać dla każdego nieparzystego za pomocą następującego wzoru:

Wyniki obliczeń

prostu znajdując liczbę, która nie ma reprezentacji trzech wyrazów. Aby to sprawdzić, różni autorzy przeprowadzali brutalne poszukiwania kontrprzykładów do przypuszczenia. Wyszukiwania tego typu potwierdziły że przypuszczenie jest prawdziwe dla wszystkich 10 .

wystarczy szukać rozwinięć dla gdzie jest liczbą pierwszą , ponieważ za każdym razem, gdy , to samo wszystkich pozytywnych liczby całkowite . Aby znaleźć rozwiązanie dla , po prostu podziel wszystkie ułamki jednostkowe w rozwiązaniu na przez :

Gdyby były kontrprzykładem do , dla złożonej każdy czynnik pierwszy } zapewniłoby również kontrprzykład zostałby znaleziony wcześniej podczas wyszukiwania metodą brute-force Dlatego sprawdzanie istnienia rozwiązania dla liczb złożonych jest zbędne i można je pominąć podczas wyszukiwania. Ponadto znane modułowe tożsamości hipotezy (patrz poniżej ) mogą przyspieszyć te wyszukiwania, pomijając inne wartości, o których wiadomo, że mają rozwiązanie. Na przykład zachłanny algorytm znajduje rozwinięcie z trzema lub mniej terminami dla każdej liczby, n 1 modulo 4, więc wyszukiwanie tylko muszą testować wartości, które wynoszą 1 modulo 4. Jednym ze sposobów na poczynienie postępów w rozwiązaniu tego problemu jest zebranie większej liczby tożsamości modułowych, co pozwoli wyszukiwaniom komputerowym osiągnąć wyższe limity przy mniejszej liczbie testów.

Liczba różnych rozwiązań jako funkcja , została również znaleziona w wyszukiwarkach komputerowych dla małych i wydaje się rosnąć nieco nieregularnie wraz z . Począwszy od , liczby różnych rozwiązań o różnych mianownikach to n = 3 {\ displaystyle n = 3}

1, 1, 2, 5, 5, 6, 4, 9, 7, 15, 4, 14, 33, 22, 4, 21, 9, ... (sekwencja A073101 w OEIS ) .

Nawet w przypadku większych rozwiązań może być czasem stosunkowo niewiele; na przykład istnieje tylko siedem różnych rozwiązań dla .

Wyniki teoretyczne

postaci _ _ _ równanie diofantyczne . Zasada Hassego dla równań diofantycznych sugeruje, że równania te powinny być badane przy użyciu arytmetyki modularnej . Jeśli równanie wielomianowe ma rozwiązanie w liczbach całkowitych, to przyjęcie tego rozwiązania dla dowolnej liczby całkowitej rozwiązanie w arytmetyce modulo- { Z drugiej strony, jeśli równanie ma rozwiązanie modulo dla każdej potęgi pierwszej , to niektórych przypadkach możliwe jest połączenie tych modułowych rozwiązań przy użyciu metod związanych z chińską twierdzenie , aby uzyskać rozwiązanie w liczbach całkowitych. Siła zasady Hassego w rozwiązywaniu niektórych problemów jest ograniczona przez przeszkodę Manina , ale dla hipotezy Erdősa-Strauusa ta przeszkoda nie istnieje.

Na pierwszy rzut oka zasada ta nie ma większego sensu w przypadku hipotezy Erdősa-Strausa. Dla równanie _ mocy, ale wydaje się, że nie ma sposobu, aby połączyć te rozwiązania w celu uzyskania dodatniego rozwiązania równania w postaci liczb całkowitych. Niemniej jednak arytmetyka modułowa i tożsamości oparte na arytmetyce modułowej okazały się bardzo ważnym narzędziem w badaniu przypuszczeń.

Tożsamości modułowe

Dla wartości pewne relacje kongruencji znaleźć rozwinięcie dla przykład tożsamości wielomianowej Na przykład, ilekroć wynosi 3, ma rozszerzenie

z trzech mianowników ( , jest wielomianem i jest liczbą całkowitą, ilekroć wynosi 2 3. Algorytm zachłanny dla ułamków egipskich znajduje rozwiązanie w trzech lub mniej wyrazach, ilekroć to nie 1 lub 17 mod 24, a przypadek 17 mod 24 jest objęty relacją 2 mod 3, więc jedyne wartości, dla których te dwie metody nie znajdują rozwinięć w trzech lub mniej wyrazach, to są przystające do 1 mod 24.

Tożsamości wielomianowe wymienione przez Mordella 1967) zapewniają trzyczłonowe ułamki egipskie za razem, gdy jest jednym z:

  • 2 mod 3 (powyżej),
  • 3 mod 4,
  • 2 lub 3 mod 5,
  • 3, 5 lub 6 mod 7 lub
  • 5 trybów 8.

Kombinacje tożsamości Mordella mogą być użyte do rozszerzenia dla wszystkich 1, 121, 169, 289, 361 lub 529 mod 840. Najmniejsza liczba pierwsza, której te tożsamości nie obejmują, to 1009. Łącząc większe klasy tożsamości modułowych, Webb i inni wykazali, że naturalna gęstość potencjalnych kontrprzykładów do przypuszczenia wynosi zero: jako parametr idzie { do nieskończoności ułamek wartości w przedziale . które mogą być kontrprzykładami, dąży do zera w granicy.

Nieistnienie tożsamości

Gdyby możliwe było znalezienie rozwiązań takich jak powyższe dla wystarczającej liczby różnych modułów, tworzących kompletny pokrywający system kongruencji, problem zostałby rozwiązany. Jednak, jak Mordell (1967) , tożsamość wielomianowa, która zapewnia rozwiązanie dla wartości przystających może istnieć tylko wtedy, gdy mod nie jest przystający do kwadratu modulo . (Bardziej formalnie, ten rodzaj tożsamości może istnieć tylko wtedy, gdy nie jest resztą kwadratową modulo .) Na przykład 2 jest Mordella pozwala na istnienie p { tożsamości dla mod 3. Jednak 1 jest kwadratem mod 3 (równym kwadratowi zarówno 1, jak i 2 mod 3), więc nie może być podobnej tożsamości dla wszystkich wartości , które są przystające do 1 mod 3. Bardziej ogólnie, ponieważ 1 jest kwadratowym modem wszystkich , nie może istnieć kompletny system obejmujący modułowy dla wszystkich ponieważ 1 zawsze będzie odkryte.

Pomimo tego, że wynik Mordella ogranicza formę tożsamości modułowych dla tego problemu, wciąż istnieje nadzieja na użycie tożsamości modułowych do udowodnienia hipotezy Erdősa – Strausa. Żadna liczba pierwsza nie może kwadratem, więc zgodnie z twierdzeniem Hassego-Minkowskiego , ilekroć jest pierwszą, istnieje większa liczba pierwsza taka, że ​​nie jest resztą kwadratową modulo . Jednym z możliwych podejść do udowodnienia hipotezy byłoby znalezienie dla każdej liczby pierwszej pierwszej rozwiązującej problem dla przystającego do mod . Gdyby można było to zrobić, żadna mogłaby być kontrprzykładem dla przypuszczenia, a przypuszczenie byłoby prawdziwe.

Liczba rozwiązań

Elsholtz i Tao (2013) wykazali, że średnia liczba rozwiązań na liczbach pierwszych do ograniczona góry polilogarytmicznie w . W przypadku niektórych innych problemów diofantycznych istnienie rozwiązania można wykazać za pomocą asymptotycznych dolnych granic liczby rozwiązań, ale działa to najlepiej, gdy liczba rozwiązań rośnie co najmniej wielomianowo, więc wolniejsze tempo wzrostu wyniku Elsholtza i Tao sprawia, że dowód tego typu jest mniej prawdopodobny. Elsholtz i Tao klasyfikują rozwiązania według tego, czy jedno lub dwa z , lub są podzielne przez ; dla prime (średnio) większość rozwiązań dla kompozytu innego typu. Ich dowód wykorzystuje twierdzenie Bombieri-Vinogradov , twierdzenie Bruna-Titchmarsha i system tożsamości modułowych, ważny, gdy jest zgodny z - modulo , gdzie i to dowolne dwie dodatnie liczby całkowite względnie pierwsze i jest dowolną liczbą nieparzystą do współczynnik za . Na przykład ustawienie jedną z tożsamości Mordella, ważną, gdy wynosi 3 mod 4.

Uogólnienia

postaci , przypuszczano, że każdy dla ) można wyrazić jako sumę trzech dodatnich ułamków jednostkowych. Uogólniona wersja przypuszczenia stwierdza, że ​​dla każdego dodatniego , z wyjątkiem nieskończenie wielu, można wyrazić jako sumę trzech dodatnich jednostek ułamki. Przypuszczenie dotyczące ułamków zostało postawione przez Wacława Sierpińskiego w artykule z 1956 którym pełne przypuszczenie przypisuje się uczniowi Sierpińskiego, Schinzelowi .

Nawet jeśli uogólnione przypuszczenie jest fałszywe dla dowolnej ustalonej wartości liczba ułamków z } od 1 do , muszą rosnąć tylko podliniowo jako funkcja . W szczególności hipoteza Erdősa – Strausa (przypadek jest fałszywa, to liczba kontrprzykładów rośnie tylko podliniowo Jeszcze silniej, dla dowolnego ustalonego potrzeba więcej niż dwóch wyrazów w rozwinięciach ułamków egipskich. Uogólniona wersja hipotezy jest równoważna stwierdzeniu, że liczba ułamków nierozszerzalnych jest nie tylko podliniowa, ale ograniczona.

Kiedy jest liczbą nieparzystą analogicznie do problemu nieparzystych zachłannych ekspansji ułamków egipskich, można poprosić o rozwiązania x , i różnymi dodatnimi liczbami nieparzystymi Wiadomo, że rozwiązania tego równania zawsze istnieją dla przypadku, w którym k = 3 .

Zobacz też

Notatki