Hipoteza Erdősa – Strausa
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
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, są 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
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ń:
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 :
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}
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
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
- Ahmadi, MH; Bleicher, MN (1998), „O przypuszczeniach Erdősa i Strausa oraz Sierpińskiego o ułamkach egipskich”, International Journal of Mathematical and Statistical Sciences , 7 (2): 169–185, MR 1666363 .
- Bernstein, Leon (1962), "Zur Lösung der diophantischen Gleichung , insbesondere im Spadek ", Journal für die Reine und Angewandte Mathematik (w języku niemieckim), 211 : 1–10, doi : 10.1515/crll.1962.211.1 , MR 0142508 , S2CID 118098315 .
- Jasny, Marcin; Loughran, Daniel (2020), „Przeszkoda Brauera – Manina dla powierzchni Erdősa – Strausa”, Bulletin of the London Mathematical Society , 52 (4): 746–761, arXiv : 1908.02526 , doi : 10.1112/blms.12374 , MR 4171399 , S2CID 218959757 .
- Elsholtz, Christian (2001), „Suma ” , Transactions of the American Mathematical Society , 353 (8): 3209–3227, doi : 10.1090 / S0002-9947-01-02782-9 , MR 1828604 .
- Elsholtz, chrześcijanin; Tao, Terence (2013), „Liczenie liczby rozwiązań równania Erdősa – Strausa na ułamkach jednostkowych” (PDF) , Journal of the Australian Mathematical Society , 94 (1): 50–105, arXiv : 1107,1010 , doi : 10,1017 /S1446788712000468 , MR 3101397 , S2CID 17233943 .
- Eppstein, David (1995), „Dziesięć algorytmów dla ułamków egipskich”, Mathematica in Education and Research , 4 (2): 5–15 . Zobacz w szczególności sekcję „Małe liczniki”.
- Erdős, Paul (1950), "Az egyenlet egész számú megoldásairól (O równaniu diofantycznym)" (PDF) , Mat . Lapok. (w języku węgierskim), 1 : 192–210, MR 0043117 .
- Graham, Ronald L. (2013), „Paul Erdős i frakcje egipskie” (PDF) , w: Lovász, László ; Ruzsa, Imre Z .; Sós, Vera T. (red.), Erdös Centennial , Bolyai Society Mathematical Studies, tom. 25, Budapeszt: János Bolyai Mathematical Society , s. 289–309, doi : 10.1007/978-3-642-39286-3_9 , MR 3203600
- Guy, Richard K. (2004), Unsolved Problems in Number Theory (wyd. 3), Springer Verlag , s. D11, ISBN 0-387-20860-7 .
- Hagedorn, Thomas R. (2000), „Dowód hipotezy na temat ułamków egipskich”, American Mathematical Monthly , Mathematical Association of America, 107 (1): 62–63, doi : 10.2307/2589381 , JSTOR 2589381 , MR 1745572 .
- Hofmeister, Gerd; Stoll, Peter (1985), „Notatka o ułamkach egipskich”, Journal für die Reine und Angewandte Mathematik , 362 : 141–145, MR 0809971 .
- Ionascu, Eugen J.; Wilson, Andrew (2011), „O hipotezie Erdösa – Strausa”, Revue Roumaine de Mathématiques Pures et Appliquées , 56 (1): 21–30, arXiv : 1001,1100 , MR 2848047 .
- John H. (2004), „O rozszerzeniu trzy ułamki egipskie” , Crux Mathematicorum , : 36–37 .
- Jollensten, Ralph W. (1976), „Uwaga dotycząca problemu egipskiego”, Proceedings of the Seventh Southeastern Conference on Combinatoryics, Graph Theory and Computing (Louisiana State Univ., Baton Rouge, La., 1976) , Congressus Numerantium, tom. XVII, Winnipeg, Man.: Utilitas Math., s. 351–364, MR 0429735 .
- Pocałunek, Ernest (1959), „Quelques remarques sur une équation diophantienne”, Acad. RP Romîne Fil. Cluj Stadnina. Cerk. Mata. (w języku rumuńskim), 10 : 59–62, MR 0125069 .
- Kotsireas, Ilias (1999), „The Erdős-Straus conjecture on Egyptian ułamki”, Paul Erdős i jego matematyka (Budapeszt, 1999) , Budapeszt: János Bolyai Math. Soc., s. 140–144, MR 1901903 .
- Li, Delang (1981), „Z równania ”, Journal of Number Teoria , 13 (4): 485–494, doi : 10.1016/0022-314X(81)90039-1 , MR 0642923 .
- Mordell, Louis J. (1967), Równania diofantyczne , Academic Press, s. 287–290 .
-
Obláth, Richard (1950), "Sur l'équation diophantienne ", Mathesis (po francusku), 59 : 308–316, MR 0038999 ,
M. Strauss [sic] a vérifié l'hypothèse de M. Erdős pour toute valeur de n <5.000, et M. Shapiro pour n <20.000. Nos théorèmes donnent la solution pour tout nombre < 106,128
. - Rosati, Luigi Antonio (1954), "Sull'equazione diofantea ”, Boll. Un. Mata. włoski. (3) (w języku włoskim), 9 : 59–63, MR 0060526 .
- E. (2014), Przypuszczenie sprawdzanie do Strausa i : 1406,6307 , Bibcode :
- Sander, JW (1994), „On i półwymiarowe sito Iwanieca ", Journal of Number Theory , 46 (2): 123-136, doi : 10.1006/jnth.1994.1008 , MR 1269248 .
- Schinzel, André (1956), „Sur quelques propriétés des nombres i , où jest un nombre impair", Mathesis ( w języku francuskim), 65 : 219–222, MR 0080683 .
- Sierpiński, Wacław (1956), Sur les décompositions de nombres rationnels en frakcje primaires, Mathesis (po francusku), 65 : 16–32, MR 0078385 . Przedruk z dodatkowymi adnotacjami w : Sierpiński, Wacław (1974), Oeuvres Choisies , t. I, Warszawa: PWN — Éditions Scientifiques de Pologne, s. 169–184, MR 0414302 .
- Suryanarayana, D.; Rao, N. Venkateswara (1965), „Na papierze André Schinzela”, J. Indian Math. soc. , Nowa seria, 29 : 165–167, MR 0202659 .
- Terzi, DG (1971), „Na podstawie przypuszczenia Erdősa-Strauusa”, Nordisk Tidskr. Obsługa informacji (BIT) , 11 (2): 212–216, doi : 10.1007/BF01934370 , MR 0297703 , S2CID 124845157 .
- Vaughan, RC (1970), „O problemie Erdősa, Strausa i Schinzela”, Mathematika , 17 (2): 193–198, doi : 10.1112 / S0025579300002886 , MR 0289409
- Webb, William A. (1970), „Na ", Proceedings of the American Mathematical Society , American Mathematical Society, 25 (3): 578–584, doi : 10.2307/2036647 , JSTOR 2036647 , MR 0256984 .
- Yamamoto, Koichi (1965), „O równaniu diofantyny ", Wspomnienia Wydziału Nauk. Uniwersytet Kiusiu. Seria A. Matematyka , 19 : 37–47, doi : 10.2206/kyushumfs.19.37 , MR 0177945 .
- Yang, Xun Qian (1982), „Uwaga na ", Proceedings of the American Mathematical Society , 85 (4): 496–498, doi : 10.2307/2044050 , JSTOR 2044050 , MR 0660589 .