Stare i nowe problemy oraz wyniki w kombinatorycznej teorii liczb

Twierdzenie van der Waerdena i tematy powiązane

Oznaczmy przez W(n) najmniejszą liczbę całkowitą , taką ,że jeśli (dodatnie) liczby całkowite nie przekraczają W(n) są podzielone arbitralnie na dwie klasy, co najmniej jedna klasa zawsze zawiera postęp arytemtyczny długości n. Słynne twierdzenie van der Waerdena pokazuje ,że W(n) istnieje dla wszystkich n ale wszystkie znane dowody skutkują górną granicą na W(n) które są ekstremalnie słabe, np. nie są nawet pierwotnymi funkcjami rekurencyjnymi z n. W drugim kierunku, najniższa dolna granica aktualnie dostępna to W(N+2) > n ⋅ 2n dla n liczb pierwszych. Jedyne wartość W(n) znane obecnie to :
W(2) = 3, W(3) = 9, W(4) = 35, W(5) = 178 .Wyniki Parisa i Harringtoan pokazuję ,że pewne problemy kombiantoryczne, mają dolne granice rosnące szybciej niż dowolna funkcja, która jest łatwo udowadnialna w arytmetyce pierwszego rzędu arytmetyki Peano. Erdos i Turan, dla celu poprawienia estymacji dla W(n) wprowadzili wielkość rk(n), definiującą najmniejszą liczbę całkowitą r taką ,że jeśli 1 ≤ a1 < … < ar ≤ n, wtedy sekwencja ai′s musi zawierać k-wyraz A.P. Najlepiej znana granica na r3(n) to:
n/exp(c1√log n) < r3(n) < c2n/log log n, gdzie c, c1, c2,… będą zawsze oznaczały odpowiednie dodatnie stałe. Rankin miał lepsze granice dla rk(n) k > 3. Jednak, dziełem Szemerdiego jest dowód górnej granicy rk(n) = o(n)
Jego dowód, używający twierdzenia vad der Waerden′a nie daje żadnej użytecznej granicy dla W(n) .Wynik ten również został udowodniony przez Furstenberga używając twierdzenia ergodycznego. Dowód ten również nie dostarcza żadnych szacunków dla rk(n). Dużo krótszą wersję podali Katznelson i Ornstein: rk =? O(n/(log n)2
dla każdego t. To będzie implikować jako następstwo, że dla każdego k istnieje k liczb pierwszych które formują A.P. Najdłuższe A.P. liczb pierwszych dobrze znanych ma długość 17. To 3430751869 + 87297210t , 0 ≤ t ≤ 16. Wymienimu następnie kilka przypuszczeń, które wydają siędosyć głębokie. Będą one implikować twierdzenie Szemerediego, np. Czy jest prawdą ,że jeśli zbiór A dodatnich liczb całkowitych spełnia Rysunek 1. Wtedy A musi zawierać arbitralnie długi A.P?. Zbiór Rysunek 2, gdzie Ak rozciąga się na wszystkie zbiory dodatnich liczb całkowitych, która nie zawiera k-wyrazów A.P. O ile wiemy, αk = ∞ jest możliwe ,ale wydaje się to mało prawdopodobne. Najlepszą dolną granicą znaną dla αk przez wzgląd na Gervera: αk ≥ (1 + o(1)) k log k. Trywialnie, αk ≥ ? ⋅ log W(k)
Wydaje się ciekawe wykazać ,że: αk/log W(k) > 1 / 2 + c, lub nawet Rysunek 3, ale obecnie nie mamy pomysłu jak zaatakować tą kwestię. Drugie przypuszczenie jest oparte na poniższej idei .Dla skończonego zbioru X = {x1,…,xy}, niech XK oznacza zbiór N-krotek {(y1, … yN) : yi ∈ X, 1 ≤ i ≤ N}. Nazwijmy zbiór P = {p1^, p2^, … ,pt} z t N-krotek pi^ ∈ XN linią jeśli pt^ ma następującą właściwość : Dla każdego j, 1 ≤ j ≤ N, albo j-ty komponent z pt^ to xt, 1 ≤ i ≤ t, albo wszystkie j-te komponenty pt^ są równe. Ponieważ |P| = t, wtedy co najmniej jedno j musi spełniać pierwszy warunek. Jest twierdzenie Halesa i Jewetta, które dla dowolnego r, jeśli N ≥ N(t,r) wtedy dla dowolnego rozkładu xn na r klas, pewne klasy muszą zawierać linię. To bezpośrednio implikuje twierdzenie van der Waerdena przez wzięcie xi = i-1, 1 ≤ i ≤ t, i wynajmując N-krotki (y1, …, yN) odpowiadający podstawie t rozwinięcia liczb całkowitych. Rysunek 4. Faktycznie , to również implikuje, wysokowymiarowe uogólnienie twierdzenia nad der Waerdena , które krótko wymienimy. Pytanie brzmi : Czy odpowiednia "gęstość" przechowuje wyniki? Innymi słowy, czy prawdziwe jest ,że dla każdego ε > 0 i każdej liczby całkowitej t, istnieje N (T,ε) takie ,że jeśli N ≥ N(t,ε) a R jest dowolnym podzbiorem XN spełniającym |R| ) εtN wtedy R zawiera linię P?. Dla t = 2 każda linia P może być naturalnie powiązanych z parą podzbiorów A,B ⊆ X przy A ⊂ B . Prawdziwość przypuszczenia dla t = 2 wtedy wynika z twierdzenia Spernera o maksymalnym rozmiarze rodziny nieporównywalnych podzbiorów N-zbioru, mianowicie, tak ,że rodzina może mieć co najwyżej Rysunek 5 zbiorów. Jednak dla t ≥ 3 pytanie jest nadal otwarte. Pewne częściowe wyniki zostały podane przez Browna. Nawet nie wiadomo czy dla każdego, c,ckN/√N punktów można wybrać bez zawierania linii. Naturalne pytanie czy analogiczne twierdzenie van der Waredena kryje się w wyższym wymiarze, tj. dla skończonego podzbioru S punktów kratowych EN i rozkładu punktów kratowych EN na dwie klasy, co najmniej jedna klasa zawiera podzbiór podobny do S. Ten przypadek został po raz pierwszy pokazany przez Gallaiai niezależenie przez Witta i Garsię. Odpowiedni "gęsty" wynik, tj. analogiczne twierdzenie Szeremerediego w wyższym wymiarze, zostało udowodnione przez Furstenberga i Katzelsona używając technik teorii ergodycznej. Wynika to również z prawdziwości wcześniej wspomnianego "liniowego" przypuszczenia. Szemeredi (używając rk(n) = o(n)) ,że jeśli R jest podzbiorem {(i,j) : 1 ≤ i,j ≤ n} przy |R| ≥ εn2 i n ≥ n(ε) wtedy R musi zawierać 4 punkty, które formują kwadrat. Przedtem, Ajtai i Szemeredi udowodnili słabszy wynik dla trójkąta prostokątnego równoramiennego
Dla dowolnego rozkładu {1,2, … [r!e] na r klas, równanie x + y = z ma rozwiązanie całkowicie w jednej klasie. Zostłao to uogólnione (niezależenie) przez Rado ,Sandersa i Folkmana, którzy wykazali ,że dla dowolnego rozkładu N na skończenie wiele klas, pewna klasa C mysz zawierać arbitralnie duże zbiory {x1, x2,…, xk} takie ,że wszystkie sumy Rysunek 6, należą do C. Jedna te wyniki zostały podsumowane przez Hindmana , który wykazał ,że przy tej smaej hipotezie, pewna klasa C musi zawierać nieskończony zbiór {x1,x2, … } taki ,że wszystkie skończone sumy Rysunek 7 εi = 0 lub 1, należy do C (odpowiadając przypuszczeniu Grahama, Rotschilda i Sandersa). Następnie proste dowody zostały podane przez Baumgartnera i Glazera. Naturalnym pytaniem jest czy pewne C musi równocześnie zawierać niekończone zbiory A i B , takie ,że wszystkie skończone sumy z A i wszystkie skończone iloczyny z B są w C? Co więcej, czy możliwe jest ,że można wziąć A = B? Hindman wykazał ,.że odpowiedź na pierwsze pytanie brzmi tak, a n drugie nie. Zbudował rozkład n Na dwie klasy, takie ,że żadne nieskończony zbiór {x1,x2, …} nie ma wszystkich skończonych iloczynów i par sum xi + xj, i ≠ j , w jednej klasie. Zbudował również rozkład N na siedem klas takich ,że żaden zbiór nieskończony {x1,x2, …} nie ma wszystkich swoich par iloczynów xixj i parę sum xi + xj, i ≠ j należących do pojedynczej klasy. Arbitralnie duży zbiór skończony {{x1, … , xk} z tą właściwością mogą być zawsze znajdowane dla dowolnego rozkłady N na skończenie wiele klas jest całkowicie otwarty. Istnieje szybko rosnąca wyników, pod nazwą eulkidesowej teorii Ramseya. Pytanie brzmi : Przy danym n i r, jaka konfiguracja C ⊆ EN ma taką właściwość ,że dla dowolnego rozkładu EN na r klas, pewna klasa musi zawierać zbiór izometryczny do C. Na przykład, jeśli C składa się z 3 punktów formujących trójkąt prostokątny, wtedy wynik Shadera pokazuje że dowolny rozkład E2 na 2 klasy zawsze ma kopię C w co najmniej jednej z tych klas. Podobne wyniki osiąga się również dla trójkątów 30o i trójkątów 150o. Zwróć uwagę ,że nie jest to prawda jeśli C jest jednostkowym trójkątem równobocznym - w tym przypadku po prostu rozkładamy płaszczyznę na alternatywne pół otwarte wstęgi szerokości √3/2. Najsilniejsze przypuszczenie odnośnie tego przypadku jest takie ,że dla dowolnego rozkładu E2 na 2 klasy, pewna klasa zawiera przystające kopie wszystkich 3-punktowych zbiorów, z możliwym wyjątkiem pojedynczego trójkąta równobocznego. Konfiguracja C ⊆ En jest nazywana Ramseya jeśli dla wszystkich r, istnieje N(C,r) takie ,że dla rozkładu EN przy N ≥ N(C,r) na r klas pewna klasa zawsze zawiera podzbiór przystający do C. Istnieją dwie naturalne klasy , które są związane w konfiguracją Ramseya .Z drugiej strony, wiadomo ,ze każda konfiguracja Ramseya musi leżeć na powierzchni pewnej sfery Sn. Zatem, dowolny zbiór 3 punktów w linii prostej nie jest Ramseya (istnieją rozkłady En na 16 klas, które unikają posiadania 3 określonych punktów zbioru liniowego w jednej klasie. Inny wynik tego typu jest następujący Można wykazać ,że istnieje duże M , takie ,że jest możliwy rozkład E2 na dwa zbiory A i B ,takie ,że A nie zawiera żadnej pary punktów o odległości 1 a B nie zawiera A.P. o długości . Jak małe M możemy uwtorzyć? Aktulanie znanym M jest M ≤ 10 000 000 (mniej więcej) .W drugim kierunku, R.Juhasz wykazała ,że musimy mieć M ≥ 5. Faktycznie, wykazała , że B musi zawierać przystającą kopię dowolnego zbioru 4 punktowego. Na koniec pytania o euklidesowskiego Ramseya, wspomnijmy to co poniżek. Zostało wykazane przez Grahama ( w odpowiedzi na pytanie R.Gurewicza) ,że dla dowolnego r, istnieje (bardzo duża) liczba G( r ), taka ,że dla dowolnego rozkładu punktów kratowych płaszyzny na r klas, pewna klasa zawiera wierzchołki trójkąta prostokątnego z polem dokładnie G ( r ). Wynika z tego ,że dla rozkładu wszystkich punktów E2 na skończenie wiele klas, pewna klasa zawiera wierzchołki trójkątów każdego obszaru. Pytanie brzmi : Czy jest to prawdziwe dla prostokątów? lub być może równoległoboków? Z pewnością nie jest to prawdziwe dla rombów. Ciekawą wariacją twierdzenia van der Waerdena jest wymaganie, aby pożądane A.P jedną klasę ponad drugą klasą przez pewną stałą ilość (niż przez całkowite zawarcie w jednej klasie). Dokładniej, niech(n,k) oznaczają najmniejszą liczbę całkowitą taką ,że jeśli podzielimy liczby całkowite nie przekraczające f(n,k) na dwie klasy, musi być A.P. długości n, powiedzmy a + ud , 0 ≤ u ≤ n-1, z a + (n-1)d ≤ f (n,k) takim ,że Rysunek 8 gdzie g(m) to +1jeśli m jest w pierwszej klasie i -1 jeśli m jest w drugiej klasie. f(2n,0) zostało określone przez Spencera ale nie mamy przyzwoitego powiązania dla nawet f(n,1)/ Wydaje się ,że Rysunek 9 , ale być może Rysunek 10. Niestety , nie możemy nawet udowodnić Rysunek 11. Być może to nie będzie trudne ale z pewnością nie zobaczymy jak udowodnić Rysunek 12. Definiujemy Rysunek 13 gdzie maksimum przyjmuje wszystkie A.P, których wyrazy są dodatnimi liczbami całkowitymi a minimum przyjmuje wszystkie funkcje g:Z → {-1,1}. Roth udowodnił ,że F(x) > cx1/4 i przypuszczał ,że dla każdego ε > 0, F(x) > x1/2-g dla x > x0(ε). W drugim kierunku, Spencer wykazał ,że F(x) < cx1/2 ⋅log log x / log x
Jednak Sarkozy potem wykazał ,że F(x) = O(x log x)1/3 obalając przypuszczenie Rotha. Cantor, Erdos, Schreiber i Strauss udowodnili ,że istnieje g(n) = &;plusmn; 1 dla którego Rysunek 14 dla pewnej funkcji h(d). Wykazali ,że h(d) < cd. Żadna dobra dolna granica dla h(d) nie jest znana. O ile wiemy, występujący powiązany bardziej ogólny problem jest nadal otwarty. Niech Ak = {a1(k) < a2(k) < … }, k = 1,2, … będzie nieskończoną klasą nieskończonego zbioru liczb całkowitych. Czy isteniej funkcja F(d) (w zależności od ciągu Ak) taka ,że dla odpowiedniego g(n) = ± 1 Rysunek 15. Wydaje się pewne ,że odpowiedź jest twierdząca. W końcu, czy jest prawdą ,że dla każdego c, istniejąd i m są takie ,że Rysunek 16. Najlepiej możemy to osiągnąć tak Rysunek 17. Zaobserwujmy ,że te pytania mogą być również zadane dla funkcji g(n) która pobiera k-te pierwiastków jedności jako wartość niż ±1. Inny ciekawy problem : Dla r < s oznaczy przez fr(n,s) najmniejszą liczbę całkowitą taką ,że każdy ciag liczb całkowitych z n wyrazami, które zawierają fr(n,s) A.P. długości r musi również zawierać A.P. długości s. Być może dla s - o(log n), fs(n,s) = o(n2); to jest z pewnością fałszywe dla s > ε log n. Obenie nie możemy udowodnić f3(n,4) = o(n2) .Abbot, Liu i Riddel zdefiniowali gk(n) jako największą liczbę całkowitą taką ,że między dowolnymi n liczbami rzeczywistymi można zawsze znaleźć g(n) z nich, które nie zawierają A.P długości k. Z pewnością jest możliwe posiadanie gk < rk(n); faktycznie Riddel wykazał ,że g3(14) = 7 ale r3(14) = 8. Nie wiadomo czy g3(n) < r3(n) dla nieskończenie wielu. Wynika z tego bardzo ciekawe ogólne twierdzenie Komlosa, Sulyoka i Szeremediego ,że g3(n) > cr3(n). Być może Rysunek 18.Szeremedi wykazał ,że nie wiadomo czy Rysunek 19. Poniższe pytanie pochodzi od F.Cohena. Określenie lub oszacowanie funkcji h(d) tak ,że jeśli podzielimy liczby całkowite podzielimy na dwie klasy, co najmniej jedna klasa zawiera dla nieskończenie wielu d A.P. różnic d i długości co najmniej h(d). Erdos zaobserwował ,że h(d) < cd jest wymuszone a Petruska i Szeremedi wzomocnili to przez wykazanie ,że h(d) < cd1/2. J.Beck wykazał h(d) < (1+o(1)) log d/ log 2. Twierdzenie van der Waerdena pokazuje ,że h(d) → &infine; z d ,ale nie mamy nadającej się do zastosowania dolnej granicy dla h(d) .Zdefiniujemy H(n) będące najmniejszą liczbę całkowitą taką ,że dla dowolnego rozkładu liczb całkowitych {1,2,… ,H(n)} na dowolną liczbę klas rozłącznych, istnieje zawsze n-wyrazowy postęp arytmetyczny w którym wszystkie wyrazy albo należeć do jednej klasy lub wszystkich różnych klas. Istnienie H(n) jest gwarantowane przez twierdzenie Szeremediego. Łatwo jest wykazać ,że H(n)1/n → &infine;; wykazanie H(n)1/n/n → &infine; może być trudniejsze. A co możemy powiedzieć o małych wartościach H(n).? Czy jest prawdą,że dla każdego rozkładu pary dodatnich liczb całkowitych na dwie klasy, suma
Rysunek 20 są nieograniczone, gdzie X pokrywa wszystkie podzbiory które mają wszystkie pary należące do jednej klasy? Erdos przypuszczła ,że dla każdego ε > 0 istnieje tε tak więc liczba kwadratów w dowolnym A.P. a + kd , 0 ≤ k ≤ tε jest mniejsza niż εtε. Wynika to , z wyniku Szemerediego rk(n) = o(n); faktycznie, jego wcześniejszy wynik r4(n) = o(n) wystarcza do tego celu. Rudin przypuszczał ,że istnieje stała bezwzględna c taka ,że liczba kwadratów w a+kd , 0 ≤ k ≤ t, jest mniejsza niż c√t. Przypuszczenie Rudina jest jeszcze otwarte. Oznaczmy przez F(n) największą liczbę całkowitą r dla której istnieje ciąg bez uśredniania 1 ≤ a1 < … < ar ≤ n tzn. żadne ai nie jest średnią arytmetyczną pozostałych a. Erdos i Straus udowodnili : exp (c√log n) < F(n) < n2/3. Jednak Abbott udowodnił nieoczekiwany wynik: F(n) > n1/10. Było by miło znać jaki tu mamy poprawny wykładni. Wydaje się trudne ustanowienie rozsądnych warunków, które implikują istnienie nieskończonego A.P. w zbiorze liczb całkowitych . Np. ponieważ istnieje tylko przeliczalnie wiele nieskończonych A.P. Wtedy dla dowolnego ciągu an istnieje ciąg bn, z bn > an tak więc bn trafia każda nieskończoną A.P., Nietrudno wykazać ,że dla dowolnego ciągu B = (b1, b2, …) przy b1 ≥ 5 i bt+1 ≥ 2bi istnieje zbiór A = {a1, a2, …} z 2 ≤ ak+1 - ak ≤ 3 dla wszystkich k tak ,że dla wszystkich i , bi ∉ A + A = {a + a′ : a, a′ ∈ A}. Czy takie zachowanie można zastosować dla A + A + A (lub więcej składników sumy) nie wiemy. Sytuacja jest zupełnie inna kiedy rozpatrujemy uogólnione A.P.: S(α,β) = (a1, a2, … ,an, …). Uogólnione A.P. jest formowane przez an = [αn + β] dla danej liczby rzeczywistej α ≠ 0 i β, Wynika to z wyniku Grahama i Sosa ,że jeśli bn+1/bn ≥ c > 2 wtedy uzupełnienia bn zawierają nieskończenie uogólnione A.P. Pollington , udowodnił nie istnieje ciąg bn uderzający w każdy uogólniony A.P z bk+1/bk ≥ c > 1 dla wszystkich k. Z drugiej strony, dla ciągu cn istnieje ciąg bn z bn > cn który trafia uogólnione A.P.. Uogólnione A.P. S(α) = S(α,0) = {[αn]:n = 1,2,…} ma szeroką literaturę. Jeden z wczesnych wyników zakłada ,że S(α1) i S(α2) Rozłącznie pokrywają dodtanie liczby całkowite jeśli i tylko jeśli α1 są niewymierne a 1/ α1 + 1/ α2 = 1. Starszy wynik Uspenskiego pokazuje ,że Z+ może nigdy nie być rozłożona na trzy lub więcej rozłącznych S(αi); faktycznie , dla dowolnych trzech S(αi) pewna ich para mus mieć nieskończenie wiele wspólnych elementów. Ta sytuacja nie maj jednak miejsca dla ogólnego S(α , β) . Na przykład S(2;0),S(4;1),S(4;3) i s(7/4; 0), S(7/2;5/2),S(7;4) oba formują dekompozycję nieujemnych liczb całkowitych. Oczywiście bardziej ogólnie Rysunek 21 jest dekompozycją z Z na rozłączne A.P. liczb całkowitych wtedy S(α ,β) = ∑i=1m S(a1α;β + αbi. Graham wykazał ,że jeśli m ≥ 3, Z+ = ∑i=1m S(αi;β) a pewne αt jest niewymierne wtedy S(αi;β) muszą być wygenerowane z dwóch rozłącznych S(γi; 0) któtre pokrywa Z+ przez przekształcenie tego typu. W szczególności, wynika z twierdzenia Mirskiego i Newmana, że dla pewnych i ≠ j, αi = αj. Sytuacja staje się niezrozumiała kiedy wszystkie αi są wymierne. Twierdzenie Fraenkela zakłada ,że dla dowolnych takich dekompozycji (przy m ≥ 3), ze wszystkimi różnymi αi, musimy mieć {α1, … , αm = {2m-1 / 2k : 0 ≤ k < m}. Można zapytać ,jak rzadki (w pewnym sensie) S zbiór liczb całkowitych może być i jeszcze mieć właściwość taką ,że dla dowolnej dekompozycji S na r klas, pewna klasa musi zawierać A.P. długości k. Oczywiście, ponieważ wielokrotność z dowolnego d ma tą właściwość, musimy być bardziej dokładnie co mamy na myśli jeśli chodzi o rzadkość. Na przykład, możemy zapytać czy takie S istnieje, które samo nie zawiera A.P. długości k+1. Że takie S istnieją pierwszy wykazał Spencer (używając poprzednio wspomnianego twierdzenia Hales′a i Jewetta) i niezależnie przez Nesetrila i Rodla Starsze twierdzrenie Brauera udowadnia silniejszą postać twierdzenia van der Waerdena w którym nie tylko jedna klasa musi zawierać A.P długości r, powiedzmy, a + kd, 0 ≤ k < r, ale również wspólną różnicę d. Jednak , analogiczne twierdzenie Szemerediego nie zawiera takiego przypadku - możemy znaleźć zbiory dodatniej wielkości, które nie zawierają k-wyrazu A.P razem z ich różnicą. Na przykład, zbiór nieparzystych liczb całkowitych nie może zawierać a, a+d i d. Jednak, najgęstszy zbiór R z {1,2,… ,n} nie zawiera k-wyarazu A.P., a jego różnica została określona przez Grahama, Spencera i Witsenhausena. Ich wynik pokazuje ,że takie R musi spełniać |R| ≤ n [ [n/k]. Prawie wszystkie przypadki takiego typu problemu pozostają otwarte. Jeden z najprostszy z nich: Niech Rn będzi podzbiorem maksymalnym z {1,2,…,n} w taką właściwością ,że nie x są x, 2xx i 3x wszystkich w Rn. Co to jest Rysunek 22 (Istnienie jest znane). W szczególności, udowodnimy ,że λ jest niewymierna. Oczywiście, można zadać te pytania dla nieskończonych zbiorów liczb całkowitych, Na przykład jeśli a1 < a2 < … jest nieskończonym ciągiem liczb całkowitych takich ,że dla nie x są x,2x,3x wszystkich ai, wtedy jak duża może być gęstość z a (jeśli istnieje)? Czy górna granica może być duża?. W innym kierunku dążąc ,można zapytać ile podzbiorów z {1,2,…, n} ,powiedzmy, S1, … ,Si można mieć takich ,że dla wszystkich i ≠ j , Si ∩ Sj jest A.P. Simonowitz, Sós i Graham wykazali ,że
t ≤ (n      3) + (n     2) + (n     1) + 1 i jest to najlepsze z możliwych. Jeśli Si ∩ Sj musi być niepustym A.P. wtedy Simonovitz i Sós podali pomysłowy dowód ,że t < cn2. Jest to przypuszczenie w tym przypadku ,że maksymalne rodziny formują silny Δ-systemy, tzn. Si są wszystkie skończonymi A.P. w {1,2,…,n} zawierający określony element, przypuszczalnie liczby całkowitej [n/2]. Łatwa konsekwencja twierdzenia van der Waerdena jest następująca: Jeśli A = (a1, a2, …) jest rosnącym nieskończonym ciągiem liczb całkowitych z ak+1 - ak ograniczeniem wtedy A zawiera arbitralnie długie A.P.. Analogiczne pytanie w wyższym wymiarze nie są jeszcze całkowicie unormowane. Na przykład, niech pi = (xi, yi), i = 1,2,… będą nieskończonym zbiorem punktów kratowych w E2 tak więc pi+1 - pi to albo (0,1) albo (1,0). Czy pi musi zawierać arbitralnie długie A.P.? O dziwo, odpowiedź brzmi, nie Możliwe jest użycie silniejszych niepowtarzalnych ciągów Dekkinga dla zbudowania takiego ciągu z pi nie mający 5 wyrazów A.P.. Z drugiej strony, nie trudno zauważyć ,że 4 wyrazowe A.P. nie mogą być unikane. Podobne techniki mogą być zastosowane dla wykazania ,że istnieje rosnące jednokrokowe ciągi punktów kratowych w E5 nie zawierając 3-wyrazowych A.P. Czy lub nie można to zrobić w E3 lub E4 nie jest znane. Pomerance wykazał ,że jeśli rozmiar średniego kroku jest ograniczony, musi być arbitralnie dużym zbiorem z ak , które leży w tej samej linii. Faktycznie, wykazał coś więcej, np. że to samo odnosi się do punktów (n,pn) gdzie pn oznacza n-tą liczbę pierwszą. Gerver i Ramsey podali efektywne oszacowanie dla następującego specjalnego przypadku. Załóżmy ,że S ⊆ Z2 jest skończony i niech A = (a1, a2, …, aN) będzie ciągiem punktów kratowych z ak+1 - ak ∈ S dla wszystkich k < N (taki ciąg jest nazywany jest S-walk). Wtedy dla dowolnego ε > 0, jeśli N ≥ N0(M,ε) gdzie M oznacza maksymalną odległość dowolnego punktu w S od początku układu, A musi zawierać co najmniej C(M,ε)(log N)1/4-ε punktów kolinearnych. Z drugiej strony, taki wynik nie ma zastosowania w Z3 .W szczególności, budują one ciąg nieskończony ciąg B = (b1,b2, …) punktów kratowych w Z3 dla których bk+1 - bk jest wektorem jednostkowym dla wszystkich k i takim ,że B ma co najwyżej 511 punktów kolinearnych. Ich przypuszczenia ,że 3 jest w rzeczywistości poprawnym ograniczeniem dla ich konstrukcji. Nie wiadomo czy istnieje nieskończony S-walk w Z3 dla S skończonego, który nie ma trzech punktów kolinearnych.
Powiedzmy ,że (możliwie nieskończony) ciąg (a1,a2, … ) ma monotoniczność A.P. długości k jeśli dla pewnego wyboru indeksów i1 < i2 < … < ik, podciąg ai1 , ai2, … , aik jest albo rosnącym albo malejącym A.P. Często zauważysz ,że jest możliwe ułożenie skończonego zbioru liczb całkowitych do ciągu nie zawierającego monotonicznego A.P. długości 3. Zasadniczo, to może być zrobione przez umieszczenie wszystkich elementów nieparzystych po lewej stronie wszystkich elementów parzystych, układając (przez indukcję) nieparzyste i parzyste pojedynczo nie mających monotonicznego A.P. długości 3 i używając faktu ,że pierwszy i ostatni wyraz 3-wyrazowego A.P. muszą mieć tą samą parzystość. Jeśli M(n) oznacza liczbę permutacji z {1,2, …,n} nie mającego monotoniczności 3-wyrazowego A.P., Davis, Entringer, Graham i Simmons ,że
M(n) ≥ 2n-1M, M(2n-1) ≤ (n!)2, M(2n+1) ≤ (n+1)(n!)2
Byłoby ciekawe znać ,czy M(n)1/n jest ograniczone lub nawet prowadzi do granicy. Sytuacja dla permutacji i zbiorów nieksończonych jest różna. Powyżsi autorzy wykazali ,że dowolna permutacja z Z+ zawiera rosnący 3-wyrazowy A.P., ale ,że istnieją permutacje z Z+, które nie mają monotonicznych 5-wyrazowych A.P. Pytanie, czy lub nie monotoniczny 4-wyrazowy A.P. musi wystąpić jako aktualny całkowicie otwarty. Jeśli jest dozwolone ułożenie Z+w podwójnie nieskończony ciąg … , a-1, a0, a1, … wtedy monotoniczny 3-wyrazowy A.P. musi jeszcze wystąpić ale jest teraz możliwe zachowanie tej długości 4. Jeśli elementy będące permutowanymi wszystkie są liczbami całkowitymi niż tylko dodatnimi liczbami całkowitymi, mniej znanymi. Wiadomo ,że monotoniczny 7-wyrazowy A.P. może być zatrzymany w pojedynczo skończonym przypadku. Powinniśmy odnotować ,że modularne analogie tych problemów zbadał Nathjanson. Czy porządek liczb rzeczywistych zawiera monotniczny k-wyrazowy postęp arytemtyczny dla każdego k? Zawrzemy ten temat w bardzo irytującym pytaniu : Czy jest możliwy rozkład Z+ na dwa zbiory, każdy z nich permutujący aby uniknąć monotonicznego 3-wyrazowego A.P.? Jeśli dopuścimy trzy zbiory, jest to możliwe; odpowiednia sytuacja dla Z nie zostaną zbadana. Nie jest trudno znaleźć zbiory A = {a1, …, an} z taką właściwością ,że dla dwóch elementów ai, aj ∈ A istnieje ak ∈ A takie ,że { ai, aj, ak} formują A.P. np. {1,2,3} i {1,3,4,5,7} .Faktycznie, nie jest trudno wykazać ,że dla pewnych przekształceń afinicznych x → ax + b, istrnieją tylko takie zbiory. Wynika z tego ,że analogiczne twierdzenia Sylvestra przechowuje A.P. tzn. żaden zbiór skończony A nie ma właściwości takiej ,że każde 3 wyrazy z A należą do pewnego A.P. w A. Załóżmy wymaganie takie ,że dla każdego wyboru k wyrazów z A, pewne 3 (lub m) z nich należą do A.P. w A. Czy można teraz te A scharakteryzować? Można również zadać te pytanie dla uogólnienia A.P. jak również gdzie oczekiwać będziemy bogatszych klas z A z powodu większej liczby uogólnień A.P. Zaczynając od a0 = 0 , a1 = a formujemy ciąg nieskończony a0, a1 , a2, a3, … rekurencyjnie przez wybór an+1 będącego najmniejszą liczbą całkowitą przekraczającą an, która może być dołączona tak więc żaden 3-wyrazowy A.P. nie jest formowany .Czy ak może być wyraźnie określone? Na przykład, jeśli a = 1 wtedy ak są tylko tymi liczbami całkowitymi, które nie mają 2 w bazie rozwinięcia 3. Podobne charakteryzacje są znane kiedy a = 3′ a a = 2 ⋅ 3′ . Dla tych przypadków, jeśli α = log 3 / log 2 wtedy
Rysunek 23. Rysunek 24. Jednak przypadek α = 4 (i wszystkich pozostałych wartości nie równych 3r) wydaje się to być całkowicie różnym charakterem. Hoffman, Klarner i Rado uzyskali wiele ciekawych wyników w poniższym problemie : Niech R oznacza zbiór liniowych działań na zbiorze nieujemnych liczb całkowitych, każdy typu ρ(x1, … , xr) = m0 + m1x1 + … + mrxr Przy danym zbiorze A dodatnich liczb całkowitych , niech < R : A > oznacza najmniejszy zbiór zawierający A , który jest domknięty pod wszystkimi działaniami w R. Jaka jest struktura < R:A >? Dwa podstawowe wyniki to:
(i)Dla dowolnego nieskończonego zbioru B istnieje skończony zbiór A taki ,że < R : B > = < R:A > , kiedy co najmniej jedno ρ(x1, … , x2) = m0 + m1x1 + … + mrxr ma (m1, … , mr) = 1
(ii)Jeśli R = { m0 + m1x1 + … + mrxr} i wszystkie mi są dodatnie wtedy < R:A > jest skończoną sumą nieskończonych A.P. ponownie kiedy (m1, … , mr = 1
Szczególnie ciekawym przypadkiem jest ten kiedy R = {a1x + b1 + … + arx + br} Zostało wykazane przez Erdosa, Klarnera i Rado, że jeśli
Rysunek 25 wtedy < R:A > ma gęstość 0. Sytuacja, w której Rysunek 26 nie jest jeszcze całkowicie zrozumiała. Zależy to, na przykład, od tego ,kiedy zbiór przekształceń x → aix + bi , 1 ≤ i ≤ r, generuje wolną półgrupę pod złożeniem. Erdos pytał : Jeśli S jest zbiorem liczb rzeczywistych, który nie zawiera 3-wyrazowego A.P. wtedy musi dopełnienie z S zawierać nieskończone A.P.? R.O. Davies wykazał ,z pomocą hipotezy continuum, że odpowiedź brzmi nie. Baumgartner udowodnił o samo bez korzystania z hipotezy continuum. Baumgartner również udowodnił przypuszczenie Erdosa ,że jeśli A jest ciągiem dodatnich liczb całkowitych ze wszystkimi sumami a + a′ odrębne dla a,a′ ∈ A wtedy dopełnienie zawiera nieskończone A.P. .Oczywiście, możliwych jest wiele uogólnień. Czy można udowodnić ,że najdłuższy postęp arytmetyczny
{a+kd : 0 &;le; k &le t}, przy a + kt < x, która składa się całkowicie z liczb pierwszych spełniających t = o(log x)? Tylko t ≤ (1+o(1)) log x jest jasne; to wynika z teorii liczb pierwszych. Załóżmy ,że co najmniej ct wyrazów jest liczbami pierwszymi. Nie trudno zobaczyć ,że t < (log x)α(c) gdzie α (c ) & rarrl; ∞ jeśli c → o. Jeśli isnieje α( c ) nie powinny dążyć do nieskończoności . Jeśli weźmiemy t = log x być może liczba liczb pierwszych dąży do 0 jednostajnie w d

Kongruencje pokrywające

Rodzina klas resztkowych ai(mod ni) z 1 < n1 < … < nr jest nazywany systemem kongruencji pokrywających jeśli liczby całkowite należące do co najmniej jednej klasy resztkowej, tj. każda liczba całkowita spełnia co najmniej jedną kongruencję x ≡ ai (mod ni >W 1934 roku Romanoff pytał Erdosa czy istnieje nieskończenie wiele nieparzystych liczb całkowitych nie w postaci b + 2k gdzie p jest liczbą pierwszą. To poprowadziło Erdosa do pojęcia kongruencji pokrywających i odpowiedział Romanoffowi przez zastosowanie systemu kongrencji pokrywających 0( mod 2), 0 (mod 3), 1 (mod 4), 3 (mod 8), 7 (mod 12), 23 (mod 24). Główny otwarty problem to :
Czy jest prawdą ,że dla każdego istnieje system kongruencji pokrywających przy n1 ≥ c?
Choi zbudował kongruencje pokrywające z n1 = 20. Jeśli odpowiedź jest twierdząca bezpośrednio uzyskamy ,że dla każdego m istnieje postęp arytmetyczny bez wyrazów który jest sumą potęg dwa i liczby całkowitej mającej co najmniej m czynników pierwszych. Czy jest prawdą ,że istnieje system kongruencji pokrywających ze wszystkimi ni nieparzystymi, lub ogólniej, względnie pierwszymi do danej liczby całkowitej d? Selfridge udowodnił ciekawy wynik ,że system kongruencji pokrywających ze wszystkich nieparzystych modułów istnieje jeśli system pokrywający istnieje bez żadnych ni podzielnych przez dowolne inne nj. Schinzel zastosował ten pomysł do pewnych nieredukowalnych wielomianowych problemów. Czy można wybrać wszystkie ni będących w postaci p-1 dla p pierwszego i co najmniej 5? Oznaczmy przez f(u) najmniejszą liczbę całkowitą taką ,że istnieje system z f(u) kongruencji pokrywających z n1 = u. Jeśli f(u) jest skończone czy można uzyskać rozsądne oszacowanie tego? Powinno być całkiem duże np. jest prawdopodobnie prawdziwe ,że F(u)/uk → ∞ dla każdego k, (gdzie system kongruencji pokrywających jest zawsze zakładany będący skończony chyba ,że stanowi inaczej). Powinno być prawdziwe ,że Rysunek 27, jeśli u → ∞. Jeśli tak, top jak szybko suma dąży do nieskończoności? Oznaczmy przez A(n) największą liczbę rozłącznych systemów kongruencji pokrywających które mogą być formowane przy użyciu wszystkich modułów mniejszych lub równych n. Nie wiemy ,że A(n) → ∞ . Niech B(n) oznacza największą liczbę całkowitą taką ,że dla odpowiedniego wyboru z ai, każda liczba całkowita spełnia co najmniej B(n) kongruencji ai (mod i) dla 1 ≤ i ≤ n. Jaka jest relacja między A(n) i B(n)? Dla liczb całkowitych n < m niech A(m,n) oznacza najmniejszą gęstość liczb całkowitych nie pokrytych przez kongruencję ai(mod(n+i)), 1 ≤ i ≤ m-n, przejmując wszystkie wybory z ai >Trywialnie Rysunek 28 Powinno być to poprawione jeśli m/n jest duże. Czy jest prawdą ,że A(m,n) > εe jeśli m/n < c (dla dużego n)?
Niech 0 < n1 < n2 < … < nr. Miło by było uzyskać nietrywialne warunki na ni,które gwarantowałyby ,że system kongruencji pokrywających {ai(mod ni} istnieje. Czy jest prawdą ,że jeśli Rysunek 29, rośnie dosyć szybko wtedy taki system istnieje? To samo pytanie stosujemy jeśli Rysunek 30 .Wydaje się pewne ,że Rysuenk 31 będzie konieczne, tj. nie istnieje system kongruencji pokrywających gdzie wszystkie moduły są między εx a x. Określenie lub oszacowanie największego h(x) takie ,że istnieje system kongruencji pokrywających gdzie wszystkie moduły z n1 = h(x) i nr ≤ x. Nasza ignorancja jest tu zupełna - z jednej strony, h(x) może być ograniczone; z drugiej strony nawet h(x) > εx nie może być wyłączone. Czy jest prawdą, że jeśli dodatnie liczby całkowite są rozkładane na skończenie wiele klas, wtedy co najmniej jedna z klas zawiera moduł systemu pokrywającego? Być może jeśli podzbiór X ⊆ Z+ ma dodatnią górną gęstość wtedy X już musi zawierać moduł systemu pokrywającego. Swego czasu Erdos przypuszczał , a Ł. Miskrii i M.Newman udowodnili, że nie istnieje system dokładnych kongruencji pokrywających, tzn. system {ai(mod ni)} prze n1 < n2 < … < nr taki ,że każde x spełnia dokładnie jedną kongruencję x ≡ ai(mod ni) . Faktycznie, nie jest trudno wykazać ,że jeśli {ai(mod ni)} pokrywa liczby całkowite dokładnie z n1 ≤ n2 ≤ … ≤ nr wtedy nr-1 = nr. Wspomnijmy problem Herzoga i Schönheima : Jeśli G jest grupą abelową, czy może istnieć dokładne pokrycie G przez warstwy różnych rozmiarów? System kongruencji jest nazywany rozłącznym jeśli żadna z liczb całkowitych nie spełnia więcej niż jedną z nich. Erdös i Stein przypuszczali ,że jeśli {ai(mod ni)} z n1 < … < nr ≤ n jest systemem rozłącznym kongruencji wtedy r = o(x). Zostało to udowodnione przez Erdosa i Szemerediego, który wykazał ,że jeśli f(x) oznacza maksymalną możliwą wartość z r powyższego wtedy Rysunek 32. Wydaje się podobnie ,że niższa granica jest bliższa prawdy ale nie wydaje się łatwe udowodnienie tego. Erdos przypuszczał ,że jeśli system {ai(mod ni), 1 ≤ i ≤ r} pokrywa 2r kolejnych liczb całkowitych, wtedy pokrywa wszystkie liczby całkowite. Zostało to udowodnione przez Selfridge′a jak również Crittendena i van den Eydena. Ta granica jest najlepsza z możliwych jeśli system {2i-1 (mod 2i), 1 ≤ i ≤ r}to wykazuje. Załóżmy ,że {ai(mod ni jest systemem pokrywającym i załóżmy każde ni ma pierwszy współczynnik przekraczający k. Jakie oszacowanie może być dokonane dla Rysunek 33. Grahma rozważał następujące pytanie : Czy istnieje nieskończony ciąg "Lucasa" a,a1,… spełniających an+2 = an+1 + an n ≥ 0, a1 = 1 generuje rodzinę liczb Fibonacciego; istnieje przypuszczenie ,że nieskończenie wiele z nich jest pierwszymi ale dowód tego jest na razie nieprawdopodobne. W swojej pracy C.Stewar zawarł najmocniejsze wyniki aktualnie dostępne w tym kierunku. Okazuje się ,że istnieje taki złożony ciąg Lucasa .Używając systemu kongruencji pokrywających, wykazano ,że takie wybory generują taki ciąg: Rysunek 34. Jest to najmniejsza para (a0,a1) jaką znamy. Byłoby wielką niespodzianką jeśli istniejąca para z oboma komponentami była mniejsza niż 1020 Czy jest możliwe dla ciągu Lucasa posiadanie wszystkich wyrazów złożonych bez posiadania podstawowego systemu kongruencji pokrywających? (Innymi słowy, żadna dodatnia liczba całkowita nie ma wspólnego czynnika z każdym wyrazem ciągu) .Dobrze wiadomo ,że istnieją liczby całkowite nieparzyste 2m+1 takie ,że żadna z liczb 2k(2m+1) + 1 jest pierwsza. Najmniejsza taka liczba nie jest znana; jest to ≥ 3061 i ≤ 78557. H.C.Williams wyeliminował długoterminowe twierdzenie o 383 ,że 383 ⋅ 26393 + 1 jest liczbą pierwszą. Sierpiński wykazał ,że te liczby 2m+1 mają najniższą dodatnią gęstość. Z drugiej strony, Erdos i Odlyżko udowodnili ,że najniższa gęstość zbioru dopełniającego jest dodatnia. Czy są liczby całkowite m z (m,6) = 1 takie ,że żadna z liczb 2α3βm + 1 jest liczbą pierwszą? A co z p1α1 … prαrm + 1? A co z q1 … qrm 1 gdzie qi są liczbami pierwszymi przystającymi do 1 (mod 4)? Jeśli 2αt + 1 nie jest nigdy liczbą pierwszą dla stałego nieparzystego t gdzie α = 1,2,…, musi być odpowiedni system pokrywający, tzn. musi musi być N > 0 takie ,że (2αt + 1), N) > 1 dla wszystkich α > 0? . Odpowiedź brzmi prawdopodobnie nie ponieważ, na przykład, będzie to implikować ,że istnieje nieskończenie wiele liczb pierwszych Fermata tzn. liczb pierwszych postaci 22t + 1. Erdos zapytywał czy istnieje stała C taka ,że jeśli σ(n)/n > C ,wtedy dzielniki z n mogą być użyte jako moduły systemu kongruencji pokrywających. J,. Haight wykazał ,że takie C nie istnieje. Dla jakiego n jest możliwe sformowanie systemu pokrywającego ad (mod d) gdzie d|n które jest rozłączne jeśli to możliwe tzn. jeśli : X &equiv ad (mod d), x ≡ ad′ (mod d′)
wtedy (d,d′) = 1? Gęstość takiego n to zero. Dla danego n, jaka jest minimalna gęstość liczb całkowitych, które nie spełniają żadnej z kongruencji? Prawdopodobnie żadne takie n nie istnieje jeśli system musi być systemem pokrywającym. Dla każdej liczby całkowitej n istnieje liczba rzeczywista cn zdefiniowana jak następuje: Dla wszystkich dzielników di > 1 z n. formuje wszystkie możliwe kongruencje ai (mod di) 1 < d1 < … < dt = n. Niech cn będzie największą dolną granicą gęstości zbioru liczb całkowitych nie spełniającą żadnej z tych kongruencji. Gęstość liczby całkowitej n z cn = 0 istnieje i cn ma funkcję rozkładu która jest ciągła (z wyjątkiem przy 0) i jest ściśle monotniczna . Jeśli cn = 0, n jest nazywane pokryciem. Każda taka liczba jest wielokrotnością "pierwotnej" liczby pokrywającej n′. Bez wątpienia, suma ∑ 1/n′ przyjmuje wszystkie pierwotne liczby pokrywające zbieżne. Dla skończonego zbioru modułów n1, n2, … nr, można zapytać o minimalną wartość gęstości liczb całkowitych nie trafiona przez odpowiedni wybór kongruencji ai (mod ni). Czy najgorszym wybór uzyskamy przez wzięcie wszystkich ai równe? Wróćmy do kilku pytań powiązanych z oryginalnym pytaniem Romanoffa, który zmotywował powstanie pojęcie kongruencji pokrywających. Oznaczmy przez V(n) liczbę pierwszych czynników z n z wielokrotnościami współczynników liczonych wielokrotności. Czy jest prawdą ,że wszystkie duże liczby całkowite są w postaci 2k + m gdzie V(m) < log log m? Łatwo jest zobaczyć z metod probabilistycznych ,że to ma zastosowanie dla prawie wszystkich liczb. Być może log log m może być zastąpione przez ε log log m lub nawet niektóre funkcje, które dążą do nieskończoności dużo wolniej. Cohen i Selfridge znaleźli nieskończony postęp arytmetyczny liczb nieparzystych , który nie jest sumą lub różnicą dwóch pierwszych potęg (i w konsekwencji sumą lub różnicą liczb pierwszych i potęg z 2). Czy jest prawdą ,że dla każdego r ≥ 2 istnieje nieskończenie wiele liczb całkowitych nie będących sumą liczb pierwszych a najwyżej r potęg z 2? Czy istnieje nieskończony postęp arytmetyczny takich liczb? Dla r = 2, Crocker udowodnił ,że istnieje nieskończenie wiele takich liczb ale nie uzyskał postępu arytmetycznego. Gallagher wykazał ,że dla każdego ε > 0 istnieje r takie ,że niska gęstość liczb całkowitych postaci p+2k1 + … + 2kr przekraczających 1 - ε. Czy jest prawdą ,że wszystkie (lub prawie wszystkie) liczby całkowite są sumy potęg z 2 i liczb wolnych kwadratów? Istnieje możliwość rozszerzenia pojęcia systemów pokrywających do dołączenia możliwości nieskończonych systemów kongruencji pokrywających. Omówimy kilka z nich chociaż jest z pewnością możliwe ,że przymkniemy oko na trywialne obserwacje. Aby zacząć możemy wywołać nieskończony system {ai (mod ni)} pokrywający jeśli każda liczba całkowita spełnia co najmniej jeden z nich a gęstość liczb całkowitych nie spełnia pierwszego k dążącego do 0 jeśli k → ∞. Jeśli Rysunek 35, może to być zawsze zrobione tak ,że jedyny ciekawy przypadek mamy wtedy Rysunek 36. W przypadku zwykłego (skończonego) system pokrywającego, możemy zapytać czy zbiór dodatnich gęstość zawsze zabiera moduł nieskończonego system pokrycia. Alternatywnie, można zdefiniować system nieskończony {ai (mod ni)} do pokrycia jeśli każda (duża) liczba całkowita jest postaci ai +tni, t ≥ . To zabezpiecza każdy ciąg z ni przed byciem modułem nieskończonego systemu pokrycia. Jeśli Rysunek 37 wtedy prawie wszystkie liczby całkowite mogą być postaci ai + tni t ≥ 2, ale nie jest to z pewnością przypadek dla wszystkich dużych liczb całkowitych. Generalnie , można zdefiniować {ai (mod ni)} będące systemem pokrywającym jeśli dla pewnego k, wszystkie ale skończona liczba dodatnich liczb całkowitych są postaci ai + tnt dla pewnego t ≥ k. Czy jest prawdą ,że z tej definicji, liczby pierwsze formują moduł nieskończonego pokrywającego systemu dla każdego k? Nawet przypadek k = 3 już wydaje się być trudnym. Wydaje się ,że jeśli Rysunek 38 wtedy istnieją wybory z ai takie ,że {ai (mod ni)} jest systemem pokrywającym tego typu. Jeszcze inną możliwością (sugerowaną przez Selfridge′a) jest taka. System nieskończony {ai (mod ni)} jest pokryciem jeśli kiedy f(k) oznacza liczbę liczb całkowitych m < nk przy m ≠ ai(mod ni) , 1 ≤ i ≤ k, wtedy f(k)/k → 0 jeśli k → ∞. Nie jest jasne czy każda sekwencja dodatniej gęstości zawierające moduł systemu pokrywającego tego typu. Prawdopodobnie jeśli nk > (1 + ε) k log k for ε > 0 a każde k wtedy {ai (mod ni)} nie jest nigdy systemem pokrywającym tego typu ale tego nie wiadomo i możemy musieć poczekać na poprawę metod sita. Załóżmy ,że n1 < n2 < … są takie ,że dla każdego wyboru ai zbiór liczb całkowitych nie spełniających żadnej z kongruencji ai (mod ni) ma gęstość 0. W tym przypadku musimy mieć Rysunek 39 i jeśli ni są parowo względnie pierwsze, wtedy to wystarcza. Jeśli dla każdego &epsilon istnieje k takie ,że gęstość liczb całkowitych nie spełniających ai(mod ni) , 1 ≤ i ≤ k jest mniejsza niż ε Czy jest to faktycznie konieczne?

Ułamki proste

Jednym z najstarszych problemów w matematyce jest przedstawienie liczb wymiernych a/b w postaci : Rysunek 40, przy x1 ≤ x2 ≤ … ≤ xn. Z powodów, które nie są całkowicie jasne (dla nas) Egipcjanie rozpatrywali ułamki w postaci 1/m jako dużo prostsze niż ogólne wyrażenie a/b. Być może pierwszy wynik w tym temacie podał Leonardo Pisan0o (Fibonacci) w 1202 roku. Udowodnił ,że "zachłanny" algorytm może zawsze być użyty dla wyrażenia dodatniej liczby wymiernej a/b jako skończoną sumę różnych ułamków prostych, algorytm zachłanny, może zawsze wybrać największy ułamek prosty 1/m , jeszcze nie używany dla którego reszta jest nieujemna. Na początek postawimy stare pytanie Steina: W reprezentacji a/2b+1 jako sumy różnych ułamków prostych w postaci 1/2m+1, czy algorytm zachłanny zawsze się kończy? Wiadomo ,że jest zawsze możliwe przedstawienie a/2b+1 jak sumy różnych nieparzystych ułamków prostych. Generalnie, można wykazać ,że a/b może być wyrażone jako suma różnych ułamków prostych w postaci 1/pm+q jeśli i tylko jeśli (b/b,(p,q)) , p/(p,q)) = 1 .Można również spytać czy chciwy algorytm zachłanny zawsze kończy się w dowolnym z tych przypadków. Sytuacja może się zmienić jeśli zaburzymy lekko zbiór dopuszczalnych mianowników. Na przykład, definiujemy u1 = 1 i un+1 = un(un+1) , n ≥ 1 i niech S = {n > 0: n ≠ uk, k ≥ }. Wtedy można wykazać ,że zbiór liczb wymiernych dla których zachłanny algorytm nie kończy się kiedy tylko mianownik w S jest gęsty w R+ (chociaż każda dodatnia liczba wymierna ma nieskończenie wiele reprezentacji jako suma różnych odwrotności z S). Wiadomo też ,że a/b może być zapisane jako skończona suma odwrotności różnych kwadratów jeśli i tylko jeśli a/b ∈[o, π2/6 - 1) ∪ [1. π2/6) = I. Wydaje się podobnie ,że istnieją liczby wymierne w zakresie dla którego odpowiedni zachłanny algorytm nie kończy się. Być może jest tak dla wszystkich liczb wymiernych w I. Klasyczny wynik Curtissa stanowi ,że najbliższe ścisłe podprzybliżenie Rn z 1 przez sumę n ułamków prostych jest zawsze dane przez wzięcie : Rysunek 41, gdzie uk zostało zdefiniowane poprzednio. W tym przypadku , Rysunek 42, tak więc Rn jest również formułowane przez zachłanny algorytm, tzn. przez wybranie dla kolejnego wyrazu największego ułamka prostego, których odjęcie pozostawia dodatnią resztę. Znany jest również fakt podprzybliżenia liczb wymiernych w postaci 1/m. Prawdą jest ,że dla liczby wymiernej a/b, najbliższe ściśle podprzybliżenie Rn(a/b) z a/b przez sumę n ułamków prostych jest dana przez Rn(a/b) = Rn-1(a/b) + 1/m, gdzie n jest najmniejszym mianownikiem jeszcze nie używanym dla którego Rn(a/b) < a/b, dowodzi ,że n jest wystarczającą duży. Interesujące twierdzenie jest takie ,że ma to zastosowanie dla dowolnej liczby algebraicznej. Nietrudno jest zbudować liczby niewymierne dla których wynik jest niepoprawny. Dla każdego n, niech ℜ oznacza zbiór : Rysunek 43, i niech ℜ oznacza ∪n≥qn. Podobnie, niech ℜ′ i ℜ′ oznacza odpowiednie zbiory kiedy wymagamy tylko x1 ≤ x2 ≤ ,xn. Istnieje wiele ciekawych nierozwiązanych pytań w odniesieniu do tych zbiorów, klika z nich omówimy. Zazwyczaj, będziemy stanowić problem dla ℜn i pominiemy odpowiednie wyrażenia dla ℜ′ .Aby rozpocząć, ciekawie byłoby mieć asymptotyczne formuły lub nawet dobre nierówności dla |ℜ| Aktualnie znane są oszacowania Straussa i innych autorów .Są to: en2-ε < |ℜ| ≤ c02n+1
gdzie : Rysunek 44. Być może najniższa granica może być zastąpiona przez c02n(1-ε) . Z powodu dużej liczby zbiorów w ℜn można by oczekiwać szerokiej różnorodności zachować dla jego elementów. Na przykład wykazano ,że dla wszystkich m ≤ 78, istnieje zbiór {x1, … ,xr} ∈ ℜ z Rysunek 45. Co więcej, nie jest możliwe dla m = 77. Wydaje się wysoce prawdopodobne ,że dla dowolnego wielomianu p:Z → Z jest prawdą ,że dla wystarczająco dużego m, istnieje zbiór {x1,…m xr} ∈ ℜ z Rysunek 46 pod warunkiem ,że p spełnia konieczne warunki:
(i)Współczynnik prowadzący z p jest dodatni
(ii)gdc(p(1),p(2),…) = 1
Wiadomo, że warunki (i) i (ii) są wystarczające dla wyrażenia każdej wystarczającą dużej liczby całkowitej jako sumy Rysunek 47. Burr wykazał ,że dla dowolnego k, każda wystarczająco duża liczba całkowita występuje jako suma: ∑xik dla pewnego (x1,…,xn) ∈&real.′ .Widać ,że min {x1 : (x1, … , xn) ∈ℜ′n} = n .Ponieważ Rysunek 48 wtedy odpowiednia jednostka: min {x1 : {x1, …, xn} ∈ ℜn} =f(n), spełnia: f(n) ≥ (1+o(1)) ⋅n/e-1.O ile znamy f(n) = (1+o(1)) ⋅n/e-1
jest dobrze. W ten sam sposób, widzimy,że: min {xn:{x1, … ,x {∈ ℜn} ≥ (1+o(1)) ⋅e/e-1 ⋅n ,i może być tak ,że równość tam się pomieści. Z naszych poprzednich rozważań wynika ,że max{xn:{x1,…,xn} ∈ ℜn = un dla n ≥ 3. Generalnie możemy powiedzieć ,że: max{xk:{x1,…,xn} ∈ ℜn dla naszego k = k(n).
(Dla ℜ′ to okazuje się być bardzo łatwe - tylko używając algorytmu "zachłannego" do xk-1 i wybierając resztę xj będące równe). Prawdą jest ,że min{xn - x1 : {x1, …,xn} ∈ ℜn = (e-1)n + o(n)? Nie jest trudno wykazać ,że jest większe niż (e-1)n + ng(n)/ log n dla pewnej funkcji g(n) → ∞. Może być trudno udowodnić to dla g(n) > (log n)ε. Dobrze wiemy ,że dla {x1,… ,xn} ∈ ℜ, max(xk+1 - xk > 1, tzn. suma odwrotności kolejnych liczb całkowitych może nigdy nie być 1, i faktycznie, nigdy może nie być liczbą całkowitą. Prawdą jest ,że max(xk+1 - xk) ≥ 3? Dekompozycja 1 = 1 / 2 + 1 / 3 + 1 / 6 pokazuje ,że równość może tu wystąpić ale nie wiemy czy może wystąpić nieskończenie często (lub nawet nigdy). Ze specjalnego przypadku wynika ,że hipoteza H (wiarygodne , ale beznadziejne przypuszczenie dla liczb pierwszych, mianowicie ,że między x a 2x ewentualnie zawsze mamy k kolejnych liczb całkowitych w postaci q1, 2q2, 3q3,…,kqk, gdzie qi są liczbami pierwszymi, takich ,że max(xj+1 - xj) ≤ k
może pomieścić tylko skończenie wiele {x1, … , xn ∈ ℜ .Nie trudno zauważyć ,że istnieje funkcja f(n) dążąca do nieskończoności przy n tak ,że suma a/b odwrotności n kolejnych liczb całkowitych zawsz ma b ≥ f(n). Faktycznie nie jest zbyt trudno wykazać ,że poprawny rosnący porządek z f(n) to en+o(n) chociaż jej dokładne wartości wydają się beznadziejne. Ten sam typ wyniku również uzyskujemy jeśli mianowniki formują postęp arytmetyczny. Byłoby ciekawe znać które kolejne n liczb całkowitych minimalizują b. Można wykazać ,że największa musi być n+o(n) chociaż nie zawsze n. Załóżmy ,że ∑a,b oznacza sumę Rysunek 49. Jest prawdopodobnie prawdą ,że ∑a,b + ∑c,d jest liczbą całkowitą tylko skończenie cżsto. Jednak to będzie trudne do udowodnienia, ponieważ nie możemy nawet wykazać ,że ∑a,b + 1/n jest tylko liczbą całkowitą skończona liczbę razy. Być może dla każdego k: Rysunek 50, może być tylko liczbą całkowitą skończenie często. Wydaje się podobnie ,że dla dużego k , zawsze możemy zapisać Rysunek 51 przy bi > ai. Przykład takiej reprezentacji dla 2 jest dany przez wzięcie mianowników {2,3,4,5,6,7,9,10,17,18,34,35,84,85}. Nie trudno wykazać ,że ∑a,b = 1/n jest możliwe tylko jeśli b = a = n. Faktycznie, jeśli ∑a,b = ua,b/va,b i b > a wtedy va,b ≥ a(a+1). Generalnie, va,b jest zwiększane z b ale może być podzielone w inkrementacji. Dla stałego a co najmniej b = b(a) takie go ,że va,b+1 < va,b? Faktycznie, czy istnieje takie a b dla każdego a?. Jeśli ustawimy Rysunek 52 gdzie Ln = lcm{1,…,n} wtedy jest prawdą ,że nieskończenie często mamy (a,Ln) = 1 I nieskończenie często mamy (a,Ln) > 1 ?Wydaje się ,że Rysunek 53. Dla stałego n jest problem skończony - pewne wyniki numeryczne mogą być ciekawe dla małych wartości n. Wydaje się oczywiste , że min{xn/x1} = o(log n). Jakie są możliwe wartość xn przy zakresie {x1,…,xn} nad ℜ? Jak napisał Straus, zbiór xn jest domkniętym przy mnożeniu. Czy jest prawdą, że xn zakłada prawie wszystkie wartości całkowite? Zwróć uwagę ,że xn nigdy nie jest potęgą pierwszą, faktycznie xn ≠ apk jeśli p jest liczbą pierwszą wykraczająca poza a! log a. Jakie są xn bez żadnych elementów przekraczających 1 w {xn} jako właściwy dzielnik? Które xn nie są iloczynami dwóch (lub więcej) elementów z {xn}? Ile liczb całkowitych xi ≤ n może wystąpić jako element {x1, … ,xm} ∈ ℜ? Czy o(n), cn lub n-o(n) są takimi liczbami całkowitymi? Jaka jest najmniejsza liczba całkowita v(n) > 1, która nie występuje jako xk, zmiennej k, dla {x1,…,xn} ∈ ℜn?. Łatwo zauważyć ,że v(n) > cn! Używając wyników Bleichera i Erdosa. Może być ,że v(n) rzeczywiście rośnie bardziej jak 22√m lub 22n(1-x). Oznaczmy ,przez kr(n) najmniejszą liczbę całkowitą, która nie występuje jako xr w {x1,…,xt} ∈ ℜ przy x1 < … < xt ≤ n. Łatwo jest wykazać, że: k1(n)< cn log log n/ log n i z lekką elegancją możemy uzyskać : k1(n) < cn/ log n. Nie mamy pojęcia o prawdziwej wartości kr lub nawet z k1(n)
. Załóżmy ,że definiujemy K(n) będącą najmniejszą liczbą całkowitą , która nie występuje jako xi dla dowolnego i w dowolnym {x1, … , xt} ∈ ℜ przy x1 < … < xt ≤ n .Ponownie: K(n) < cn/ log n
jest łatwe, ale obecnie nie wiemy nawet czy k1(n) < K(n). Niech Un oznacza: min{k: {x1, … xk} ∈ ℜ , x1 ≥ n}. Wydaje się ,że : Lim {Un - (e-1)n} = ∞ ale nie możemy tego udowodnić . Erdos i Straus wykazali ,że (e-1)n - c < Un < (e-1)n + c′n/log n. Ile rozłącznych zbiorów Si ∈ℜ, 1 ≤ i ≤ k, można znaleźć takich ,ze Si ⊆ {1,2,…, n}? Bez wątpienia k = o(log n) ale nie musimy tego udowadniać. . Generalnie, ile rozłącznych zbiorów Ti ⊆ {1,2,… n} istnieje takich ,że wszystkie sumy Rysunek 54 są równe. Przez użycie silnych Δ-systemów można wykazać , że istniej co najmniej n/ee√log n takich Ti. Czy jest taki poprawny rząd wielkości? Można również zapytać ile zbiorów rozłącznych {x1k} ∈ ℜk jest możliwych. Trywialnym jest wykazanie ,że nie istnieje więcej niż log k + O(log log k); jednal, jest prawdopodobnie prawdą ,że istnieje tylko o (log k) takich zbiorów. Załóżmy że porzuciliśmy ograniczenie rozłączności i pytamy o liczbę podzbiorów S ⊆ {1,2,…,n}, które należą do ℜ.Czy istniej 2en takich podzbiorów? 2n-o(n)? Możemy wykazać ,że jeśli f(n) oznacza maksymalną liczbę podzbiorów T ⊆ {1,2,…,n} które wszystkie mają taką samą sumę Rysunek 55 wtedy dla dowolnego k: Rysunek 56gdzie logi x oznaczają i-składanych logarytmów z x. Załóżmy ,że arbitralnie dzielimy liczby całkowite na r klas. Czy jest prawdą ,że pewne elementy z ℜ należą całkowicie do jednej klasy? Silniejsze przypuszczenie jest takie, że dowolny ciąg x1 < x2 < … dodatniej gęstości zawiera a podzbiorów x ∈ ℜ Nie jest prawdą ,że jeśli założymy ∑ 1/xk = ∞ jako zbiór liczb pierwszych. Jednak ,być może Rysunek 57 nie może rosnąć dużo szybciej niż to (tzn. log log n) dla xi nie zawierającego x^ ∈ ℜ Dla danego k ,niech a1 < a2 < … < at spełniającego ai+1 - ai ≤ k i nie zakładamy żadnej sumy: Rysunek 58 jest równe 1. Prawdopodobnie at jest ograniczone w odniesieniu do a1 i k ale nie wykluczamy możliwości ,że istnieje nieskończony ciąg z tą właściwością. Niech A(n) oznacza największą wartość z |S| taką ,że S ⊆ {1,2,…,n} nie zawiera zbioru w ℜ. Prawdopodobnie A(n) = n + o(n) ale nie można tego udowodnić. Powiązanym kwestią jest oszacowanie liczby rozwiązań z Rysunek 59 gdzie εn < x1 < … < xn . Jaki jest najmniejszy zbiór S′ ⊆ {1,2,…, n} który nie zawiera zbioru w ℜ i który jest maksymalny w tym zakresie? Nie mamy pojęcia. Generalnie, można pytać o największy podzbiór Sn* z {1,2,…,n} taki ,że dla dowolnych elementów s,s1, … , sm ∈ Sn*, 1/s &nel ∑k=1m 1/sk, gdzie m > 1. Możemy z pewnością mieć |Sn*| > cn jak pokazuje zbiór {i:n/2 < i <≤ n} .Czy |Sn*| > cn dla c> 1 / 2?. Szeremedi pyta: Załóżmy Sn ⊆ {1,2,…,n} takie ,że Rysunek 60. Być może |Sn| > εn nie jest dalej tu możliwe. Faktycznie, czy jest prawdą ,że jeśli S ⊆ {1,2,…n} przy |S| > cn , wtedy S zawiera t,x i y z 1/t = 1/x + 1/y. Oczywiście, 1/t = 1/x+1/y jeśli i tylko jeśli x + y | xy. Czy X może być czymś więcej niż liczby nieparzyste? A co jeśli x.y ∈ X, x ≠ y , implikuje x + y | 2xy? Czy musimy mieć w tym przypadku |X| = o(n)? Można zadać pytanie związane z regularnością (w sensie Rado), układu równań obejmującego ułamki proste, np. czy jest prawdą ,że jeśli liczby całkowite są podzielone na r klas, pewne klasy zawierają x,y i z spełniające 1/x + 1/y = 1/z? Lub czy jest prawdą ,że jednak klasa zawsze zawiera liczby całkowite, których suma jest odwrotnością każdej liczby wymiernej a/b? Miech N(a,b) oznacza najmniejsze t dla którego Rysunek 61, x1 < x2 < … ,xt, jest możliwe. Erdos udowodnił Rysunek 62 poprawiając wcześniej nie publikowane ograniczenie c′ log b/ log log log b de Bruijna. Prawdziwy porządek N(b) wydaje się bardzo trudne do określenia. Nawet wykazanie, że N(b) = o(log b/ log log b) byłoby interesujące. Górne ograniczenie w N(b) można wydedukować z poniższego.
Lemat. Każda liczba mniejsza niż n! jest sumą mniej niż n różnych dzielników z n!
Bez wątpienia dużo mniej niż n dzielników jest wymaganych kiedy n jest duże, być może nawet tylko (log n)c,co implikowałoby N(b) < c′ log log b. Oznaczmy przez nk największą liczbę całkowitą dla której każde m ≤ nk jest sumą k lub mniej różnych dzielników z nk. Byłoby ciekawym oszacować nk - wynik liczbowy byłby tu równie ciekawy. Niech D(a,nb) = min max{xi: a/b = ∑t=1t 1/xi}gdzie minimum rozciąga się nad wszystkie dekompozycje z a/b na sumę różnych ułamków prostych i niech D(b) = max D(a,b) .Bleicher i Erdos wykazali ,że: D(b) < cb (log b)2 i w przeciwnym kierunku, jeśli b jest liczbą pierwszą p wtedy D(p) ≥ c′p log p. Jest przypuszczenie ,że dla każdego &epsilon,; > 0: D(b) ≤ c(ε)b(log b) .Można również zbadać powiązaną jednostkę Rysunek 63. Wiemy ,że n(b) > c log log b. Udowodniono ,że dla dowolnego a/b z b jako wolnym kwadratem istnieje nieskończenie wiele rozłącznych zbiorów S = (s1, …, sr, takie ,że każde sk jest iloczynem trzech różnych współczynników pierwszych a a/b = ∑i=1r1/sk . Czy można to zrobić z dwoma czynnikami pierwszymi nie jest jasne. Barbeau podał przykład {x1, … ,x101} ∈ ℜ z każdym xi jako iloczyn dwóch różnych liczb pierwszych. Wcześniej Burstein podał przykład {x1, … xn } ∈ ℜ z xi X xj dla i < j. Jednak, jak odnotował Barbeau, nie wiadomo czy 1 może być wyrażone jako iloczyn dwóch sum w postaci 1/q1 + … + 1/qk gdzie qi są różnymi liczbami pierwszymi. Być może to można wykonać jeśli założymy qi jako parowo względne liczby pierwsze. Rozważmy zbiór Sn wszystkich liczb całkowitych, które mogą być zapisane w postaci : Rysunek 64 ze zmiennymi 1 ≤ x1 < … < xr ≤ n, r . Jaka jest najmniejsza liczba całkowita nie w Sn? Czy prawdą jest ,że m ∉ Sn implikuje m+1 ∉ Sn? Istnieją z pewnością n elementowe zbiory Yn takie ,że sumy Rysunek 65, r zmienna, przestawiają więcej liczb całkowitych, które mogą przestawione przez Yn + {1,2,… n}. Aby to zobaczyć, niech E′n będzie liczbą całkowitą zdefiniowaną przez Rysunek 66 gdzie prim suma wskazuje ,że wielokrotności liczb pierwszych przekraczające n/log n są pomijane (Takie mianowniki nie mogą być używane w reprezentacji liczby całkowitej) Teraz dołączamy b1, … , br, używane w najkrótszej reprezentacji Rysunek 67 Z poprzednich oszacowań wynika ,że r będzie mniejsze niż liczba wyrazów ≤ n pominiętych przez sumę liczb pierwszych a więc, mamy zbiór mniejszy niż n liczb, których suma odwrotności przedstawia więcej liczb całkowitych niż suma odwrotności 1,2,&hellip,n. Faktycznie, zapisujemy Rysunek 68, gdzie 0 ≤ t < 1 a En jest liczbą całkowitą, wtedy jeśli t nie jest zbyt małe (jako funkcja z n), możemy znaleźć n liczb całkowitych 1 ≤ a1 < … < an dla których sumy : Rysunek 69 εk = 0 lub 1, przedstawia wszystkie liczby całkowite 1,2,… ,En. Aby to zobaczyć, zaczniemy od a1 = 1. Generalnie, jeśli a1 ,… am musi być definiowane dla pewnego m ≤ 1 definiując d przez Rysunek 70 gdzie xm jest najmniejszą liczbą całkowitą nie występującą w a1, … am a * wskazuje ,że żaden mianownik w sumie nie może być ak. Teraz przedstawienie d* s jest tak ekonomiczne jak to możliwe, używając wyniku ,że a/b może być przedstawione jako suma co najmniej c log b / log log b ułamków prostych jeśli a ≤ b. Potem dołączamy wszystkie twe nowe mianowniki to ciągu ak. Kontynuując ten proces, możemy sformować a1, … au , u ≤ b, tak więc jeśli t = t(n) nie jest zbyt małe, wtedy wszystkie liczby całkowitej 1,2,… En mogą być przedstawiane przez sumę odwrotności z ak. Nie mamy pojęcia ile liczb całkowitych może być zapisanych jako Rysunek 71, εk = 0 lub 1 .Nie możemy nawet wykluczyć możliwości ,że istnieje więcej niż c log n liczb całkowitych w tej postaci. Dla stałego c > 0 , załóżmy Sc ⊆ {1,2,… , n} z |Sc| ≥ cn. .Czy prawdą jest ,że istniej funkcja f(c) taka ,że pewna suma Rysunek 72 ma b ≤ f(c)?
. Jakie jest Rysunek 73 gdzie Sn ⊆ {1,2,…,n} rozciąga się na wszystkie zbiory nie zawierające żadnego zbioru z ℜ tzn. Rysunek 74. Powinno to być e-(e=o(1))n dla pewnego c , 0 < c < 1. Jest to trywialne co najwyżej lcm(1,2,…n)-1 i jest prawdopodobnie dużo większe. Czy jest prawdą, że istnieje c > 0 takie ,że dla stałego α i t wystarczająco dużego, jeśli Rysunek 75 wtedy dla pewnego wyboru z &epsilonk = 0 lub 1 Rysunek 76. Znamy tylko c/α2 jak górną granicę. Chociaż 1 / 2 + 1 / 3 = 1 - 1 / 6 i 1 / 2 + 1 / 3 + 1 / 4 = 1 + 1 / 12, prawdopodobnie Rysunek 77 dla każdego innego n gdzie I jest liczbą całkowitą a Ln = lcm(1,2,…,n). Czy możemy mieć 1/q1 + … + 1/qt + 1/m = 1 nieskończenie często, gdzie q1, … , qt są różnymi liczbami pierwszymi, takimi jak 1 / 2 + 1 /3 + 1 / 6 = 1? Nietrudno podać rozwiązanie 1/a1 + … + 1/an + 1/lcm(a1, … , an = 1. Wybieramy t = t(n) będące najmniejszą liczbą całkowitą taką , że : Rysunek 78. Jak małe może być &epsilon?n? Powinno być prawdą ,że lim inf n2εn = 0 ale być może n2+δεn → ∞ dla każdego δ > 0. Jednostka tεn jest równomiernie rozłożona modulo 1 i, faktycznie, jest prawdopodobnie jednostajnie rozłożone. W dowolnym przypadku, może być ciekawe uzyskanie wyniku w funkcji rozkładu. Podobne pytania można zadać dla Rysunek 79, gdzie I jest liczbą całkowitą a Rysunek 80. Przy un zdefiniowanym jak poprzednio, tzn. u1 = 1, un+1 = un(un+1) mamy Rysunek 81 i uk = [c02k + 1], k ≥ 1, gdzie c0 = 1,264085…. Jeśli a1 < a2 < … jest innym ciągiem przy Rysunek 82 jest prawdą , że Lim inf an1 / 2n < lim un1 / 2n = c0?
Czy jest prawdą ,że jeśli a1 < a2 < … < at i Rysunek 83 wtedy istnieje εk = 0 lub 1 takie ,że Rysunek 84. Nie jest prawdą, jeśli zakładamy a1 ≤ a2 ≤ … at , jeśli, na przykład, pokazany ciąg 2,3,3,5,5,5,5. Jest to przypuszczenie Spencera a inni autorzy w danym przypadku, jeśli Rysunek 85 wtedy ak może być podzielone na N ciągów ak(f) , 1 ≤ i ≤ N, tak ,że Rysunek 86 dla wszystkich i. Zbadamy Rysunek 87. Wykazujemy tu ,że r(n) jest co najwyżej n-cαlog n. Bez wątpienia jest prawdą jeśli α ∈ (0,1). Z pewnością
r(n) < e-(log n)k dla wszystkich k jeśli n ≥ n0(k) i faktycznie jest prawdopodobnie prawdą ,że r(n) < e-nε dla pewnego ε > 0. Te pytania prowadzą do rozpatrywania rozkładu sum Rysunek 88 gdzie δk = 0 lub ±1. Łatwo można zobaczyć ,że istnieje c > 0 takie ,że nierówność Rysunek 89 zachodzi dla wszystkich n gdzie wartość 0 nie jest dozwolone. Niestety, nie widzimy jak to udowodnić. Wydaje się całkiem prawdopodobne ,że istnieje c > 0 niezależnych n takie ,że Rysunek 90 gdzie Ln = lcm{2,3,… ,n} Dla dużego n bez wątpienia musimy mieć nierówność ale nie można tego udowodnić. Przykład równości istniejącej dla małego n : 1 / 2 - 1 / 3 - 1 / 4 = - 1 / 12
Erdos i Straus wykazali ,że dla dowolnego niestałego ciągu δk, k = 1,2, … z ±1 jest skończonym podciągiem dla którego Rysunek 91. R.Satter udowodnił odpowiedni dużo trudniejszy dla Rysunek 92. Czy jest również prawdą ,dla ogólnego przypadku Rysunek 93. A co z dowolnym zbiorem mianowników z dodatnią gęstością? Oczywiście, to nie może zachodzić dla wszystkich wyborów z δk dla przypadku Rysunek 94. Jednakże, jest wyobrażalne ,że jest jeszcze prawdą ,jeśli ograniczymy k do będącego co najmniej 2, tzn. dla dowolnego niestałego ciągu δ2, δ3, … z ±1 istnieje skończony podciąg δik dla którego Rysunek 95. Jak duży może być zbiór A ⊆ {1,2,…,n} tak ,że dla pewnego wyboru z δk = ±1 , a ∈ A, mamy: Rysunek 96. Jaka jest liczb t(n) różnych sum w postaci: Rysunek 97, εk = 0 lub 1? Najlepsze oszacowanie dla t(n) to Rysunek 98 dla k ≥ 4 i logk n ≥ k. Powiązane pytanie jest następujące. Ile liczb całkowitych a1 < a2 < … < ar(n) ≤ n możemy mieć takich ,że wszystkie sumy Rysunek 99 są różne? Oszacowanie Bleichera i Erdosa implikuje ,że Rysunek 100
dla dowolnego stałego s. Czy jest prawdą ,że log t(n) / r(n) → ∞ ? Możemy zapytać również o maksymalny taki zbiór ai mających kilka elementów. Łatwo zauważyć ,że liczba elementów w takim zbiorze ma większy rząd wielkości niż π(n). Niech a1 < a2 … będą nieskończonymi ciągami liczb całkowitych i niech f(n) oznacza liczbę rozwiązań z Rysunek 101. Możliwe jest tez mieć : lim f(n)1/n = 2
I nie jest trudno udowodnić ,że dla liczby A(n) sumy Rysunek 101 , lim A(n)1/n istnieje i jest dokładnie mniejsze niż 2. Byłoby ciekawie znać dokładną wartość granicy. Jeśli g(x) jsest dowolną funkcją która dąży do nieskończoności z x wtedy dla sum Rysunek 102 mniejsze niż 1, odpowiadają funkcji zliczającej A′(n) spełniającą lim A′(n)1/n = 2. Podobnie, dla Rysunek 103 , odpowiada funkcji zliczającej A″(n) spełniająca A″(n)1/n = 1. Stare przypuszczenie Erdosa i Strausa zakłada ,że dla wszystkich n > 1 , równanie : 4/n = 1/x + 1/y+1/z< ma równania całkowite, Vaughn i Webb oszacowali liczby f(N) z n ≤ N, które nie rozwiązują powyższego równania. Z tego mamy : f(N) < N exp {-c(log N)2/3} dla pewnego c > 0. Generalnie, Schinzel i Sierpiński przypuszczali ,że dla każdego a ≥ 1 istnieje n(a) takie ,że wszystkie ułamki a/n przy n ≥ n(a) mogą być zapisane w postaci a/n = 1/x ± 1/y ± 1/z
z x,y i z jako liczbami całkowitymi

Podstawy i tematy powiązane

Ciąg A = (a1, a2, …) liczb całkowitych jest nazywana podstawą rzędu k jeśli każda (dodatnia) liczba całkowita jest sumą co najmniej k z ai gdzie dozwolone jest powtarzanie. Na przykład, jak pamiętamy, dobrze wiadomo ,że kwadraty formują podstawę rzędu 4. Pewne ze znanych problemów teorii liczb działa z podstawami , np. przypuszczenie Goldbacha , które stanowi ,że każda liczba parzysta przekraczająca 2 jest sumą dwóch liczb pierwszych. Najostrzejszym wynikiem dla tego przypuszczenia zapewnia ,że każda duża liczba całkowita jest sumą trzech liczb pierwszych i że każda duża liczba parzysta jest postaci p + θ gdzie p jest liczbą pierwszą a θ ma co najmniej dwa czynniki pierwsze. Innym dobrze znanym problemem związanym z podstawami jest problem Waringa Euler przypuszczał ,że każda liczba całkowita jest sumą co najmniej g(k) = 2k + [(3/2)k - 2] k-tych potęg. Udowodniono to dla wielu wartości k i nie zawsze jest to prawdą. Hardy i Littlewood wprowadzili wielkość G(k), definiowaną jako najmniejszą liczbę całkowitą taką ,że każda duża liczba jest sumą co najmniej G(k) k-tych potęg. Teraz wiemy ,że G(k) < ck log k. Prawdopodobnie prawda jest G(k) ≤ 4 z równością jeśli k jest potęgą 2. Wieferich udowodnił g(3) = 9 a Landau pierwszy wykazał ,że G(3) ≤ 8. Dickson udowodnił ,że 23 i 239 są jedynymi liczbami całkowitymi, które wymagają 9 sześcianów w swoich reprezentacjach. Linnik ustanowił G97) ≤ 7; Watson równocześnie udowodnił całkowicie inny dowód, który jest dużo prostszy. Prawdopodobnie G(3) = 4 ale nie jest nawet wiadomo czy każda duża liczba może być wyrażona jao suma x13 ± x23 ± x33. Oznaczmy przez fk, δ fk,k x1-α lub nawet
fk,m (x) > cxm/k
dla każdego m < k i ε > 0 i każdego wystarczająco dużego x. Ta nierówność wydaje się nie do zaatakowanie przez metody obecnie dostępne, chociaż przypadek k = 2 jest całkiem łatwy - Landau udowodnił: f2,2(x) ∼ cx/ √log x. Dla k > 2 nie wiemy czy fk,k (x) = o(x). Oznaczmy przez rk,l(n) liczbę rozwiązań z Rysunek 104. Słynna K-hipoteza Hardy′ego i Littlewooda stanowi rk,k = O(nε) dla każdego ε > 0 Jest to łatwe dla k = 2. Jednak, Mahler obalił to przypuszczenie dla k = 3. Wykazał : r3(n) > cn1/12 dla dużego n, co być może jest poprawnym rzędem wielkości. Prawdopodobnie K-hipoteza jest fałszywa dla każdego k > 3. Hardy i Littlewood również stworzyli słabsze przypuszczenie : Rysunek 105 ,dla każdego ε > 0. Jest to prawdopodobnie prawda ale niewątpliwie bardzo głęboka. Jednak wystarczająca dla wielu zastosowań. Mordell udowodnił lim sup r3,2(n) = ∞ a Mahler wykazał ,że r3,2(n) > (log n)α dla nieskończenie wielu n i pewnego α > 0. Wiadomo też ,że lim sup r4,2(n) ≥ i lim sup r4,3(n) = ∞, poza tym ,nic więcej nie wiadomo. Na przykład nie wiadomo czy x5 + y5 = u5 + v5 ma nietrywialne rozwiązania. Euler przypuszczał ,że Rysunek 106 nie ma nietrywialnych rozwiązań Jest to dobrze wiadomo dla n = 3, nie znane dla n = 4 i obalone dla n = 5: 1445 = 1335 + 1105 + 845 + 275. Erdos i Mahler udowodnili ,że liczba różnych liczb całkowitych nie przekraczających postaci xk + yk , k 2, jest większa niż cn2/k(faktycznie , udowodnili bardziej ogólne twierdzenie). Hooley utrwalił ten wynik przez uzyskanie formuły asymptotycznej .Byłoby ciekawym udowodnić ,że liczba liczb całkowitych mniejsza niż n postaci x1k + x2k + x3k , k ≥ 3, przekracza cn3/k lub nawet n3/k-ε. Byłoby to przydatne nawet dla dużego k . Dla k = 3, najostrzejszy wynik, to stary wynik Davenporta f3,3 (n) > n47/54 - ε. Oznaczmy przez fk(n) liczbę rozwiązań Rysunek 107. Erdos wykazał ( i niezależnie S.Chowla) ,że
fk(n) > nc/log log n
Jeśli xi są ograniczone do liczb pierwszych wtedy odpowiednia liczba f′n(n) zostanie zbadana. Wiadomo ,że f′2(n) > nc/log log n i może być wykazane ,że Rysunek 108 dąży do nieskończoności przy x dość szybko. Jednak dla k ≥ 4 prawie nic nie jest wiadome.
Niech a1 < … < ak ≤ x będą takie ,ż każde n < x jest w postaci ai + aj. Rohrbach przypuszczał ,że to hiopteza
k > 2√x + O(1)
Jednak przypuszczenie Rohrbacha zostało obalone przez Hammera i Hofmeistera. Erdos pytał czy istnieje nieskończony ciąg {ak} dla którego n = ai + aj jest rozwiązywalne dla każdego n i które spełnia ak/k2 → c. Cassels dał przykład takiej podstawy , która spełnia ak = ck2 + O(k) . Cassels w rzeczywistości podał podstawę {bk} gdzie lim sup bk/k2 różni się od lim inf bk/k2 a potem dodał nowe wyrazy. Poprawny sposób sformułowania tego pytania to: Załóżmy a1 < a2 < … jest podstawą rzędu 2 taką ,że usunięcie dowolnego ai niszczy właściwość podstawy, tzn. ak formują minimalną podstawę. Czy może zdarzyć się ,że Rysunek 109 ? Przypuszczamy ,że nie można. Inny sposób postawienia problemu jest taki: Czy każda podstawa rzędu 2 ma podzbiór {ak} który jest również podstawą i dla której Rysunek 110 nie istnieje? Dla ciągu A = {ak} , niech f(n) = fA oznacza liczbę rozwiązań n = ai + aj , i < j. Wspomnijmy kilka interesujących pytań odnośnie f(n).
1.Czy istnieje ciąg {ak} dla którego lim f(n)/ log n istnieje i jest większe niż 0? Można wykazać metodami prawdopodobieństwa ,że istnieje {ak} z
c1 log n < f(n) < c2 log n
.Szczegółowiej, między 2k a 2k+1 wybieramy losowy podzbiór rozmiaru c⋅2k/2/√k, dla k ≥ k0. Wtedy prawie wszystkie takie wybory spełniają żądaną nierówność .Można również wykazać tymi metodami, że istnieją ciągi {ak} dla których f(n) ∼ g(n) log n gdzie g(n) dąży do nieskończoności dowolnie wolno
2.Dana jest wyraźnie konstrukcja ciągu {ak}, który ma 1 ≤ f(n) = o(nε) dla wszystkich ε > 0
3.Wykazano ,że f(n) > 0 dla wszystkich n implikuje lim sup f(n) = ∞. Czy jest prawdą ,że implikuje to f(n) > c log n?
4.Wykazano ,że ak < ck2 implikuje lim sup f(n) = ∞. Wiemy ,że istnieją sekwencje {ak} z lim inf ak/k2 < ∞ i f(n) ≤ 1
5.Ajati, Komlos i Szemeredi wykazali ,że istnieje {ak} z ak = o(k3) i f(n) ≤ 1 dla wszystkich n. Prawdopodobnie ak może być wybrane takie ,że ak < ck2+ε. Wiemy ,że dla wszystkich ε > 0 istnieję cε i ciąg {ak} z ak < k2+ε dla k ≥ k0 i f(n) < cε
6.Załóżmy an < cn3 dla wszystkich n. Czy jest prawdą ,że nie wszystkie potrójne sumy ai + aj + ak mogą być różne? Bose i Chowla udowodnili ,że możliwe jest wybranie (1+o(1))x/3 liczb całkowitych mniejszych niż x takich ,że wszystkie trójki sum są różne. Pytali oni czy jest to możliwe dla (1 + ε)x1/3 liczb całkowitych
7.Załóżmy fA(n) ≤ c dla wszystkich n. Czy zawsze jest możliwe podział A na t = t( c ) podzbiorów A1, … At takie ,że fAk (n) < c dla wszystkich k i n? J.Nesetril i V. Rodl wykazali ,że odpowiedź jest ujemne dla wszystkich c.. Erdos wykazał to dla 3,4 i nieskończnie wielu innych wartości.
8.Załóżmy fA(n) ≥ 1 dla wszystkich n. Jak duże może być pA = lim sup A(n) / √n?. Erdos wykazał ,że pA = 1 / 2 jest możliwe, a Kruckerberg ,że pA = 1 / √2 jest możliwe. Można by wykazać ,że pA ≤ 1 zawsze trwa. Czy jest prawdą ,że dowolny skończony zbiór ze wszystkimi parami różnych sum może być osadzony w pewnym (skończonym) doskonałym zbiorze różnicowym? (Jeśli ta, wtedy wynikałoby ,że pA = 1 jest możliwe).
Ciąg a1 < a2 < … jest nazywany zasadniczym komponentem jeśli dla każdego ciągu b1 < b2 < … z gęstością Schnirelmana α, zbiór wszystkich sum {ai + bj} ma gęstość ściśle większą od α Z wyniku tezy Wirsinga wynika ,że fatycznie gęstość {ai + bj} jest większa niż α + f(α) gdzie f zależy od {ai} ale nie od bj} lub α .W 1935 Erdos wykazał ,że podstawa jest komponentem zasadniczym. Jednak Linnik obalił odwrotność przez podanie przykładu komponentu zasadniczego A = {a1, a2, …} który nie jest podstawą. Jego przykład spełniał
A(x) < e(log x)9/10+ε
dla każdego ε > 0, gdzie A(x) oznacza liczbę elementów z A, które nie przekraczają x. Dowód Linnika jest bardzo skomplikowany. Wirsing podał prostszy dowód,, Jego przykład spełniał
A(x) < e(log x)1 / 2 + ε
dla każdego ε > 0. Przypuszczamy ,że jeśli ak+1 / ak ≥ c > 1 wtedy ciąg A nie może być komponentem zasadniczym .Wirsing wierzył ,że jeśli
A(x) < e(log x)1 / 2 - ε
dla pewnego ε > 0 wtedy A nie może być komponentem zasadniczym. Pytanie Erdosa i Nathansona brzmiało. Zakładając ,że a1 < a2 < … jest minimalną podstawą która ma dodatnią gęstość. Czy może się zdarzyć ,że dla dowolnego ai, (górna) gęstość liczb całkowitych , która nie może być przedstawiona bez użycia ak jest dodatnia? Niech A = {a1 < a2 < …} i B = {b1 < b2 < … } będą ciągami liczb całkowitych spełniających A(x) > εx1 / 2, B(x) > εx 1 / 2 dla pewnego ε > 0. Czy jest prawdą ,że ai - aj = bk - bl ma nieskończenie wiele rozwiązań? Prikry, Tideman, Stewart i inni, wykazali ,że jeśli A = {a1, a2, … } ma dodatnią gęstość, zbiór liczb D(A) = {d1 < d2 < …} ,który występuje nieskończenie często jako ai - aj ma ograniczoną luę tzn. di+1 - di jest ograniczone. Faktycznie, prowadzi to do części wspólnej D(A1) ∩ … ∩ D(An) dla dowolnych n zbiorów Ai dodatniej gęstości. Byłoby ciekawie znać do jakiego stopnia ta konkluzja odnosi się do słabszej hipotezy na Ai. Możemy również zapytać o najlepsza granicę w rozmiarze luki w odniesieniu do gęstości. Co jeśli wymagamy tylko aby D(A) lub D(A1) ∩ … ∩D(An) miały dodatnią gęstość; lub nawet aby
Rysunek 111, lub nawet , że D(A) ≠ ∅ zamiast luki ograniczenia? Niech A będzie zbiorem liczb całkowitych z asymptotyczną gęstością zero. Czy zawsze istnieje podstawa B z B(x) = o(√x) taka ,że każde a ∈ A może być zapisane jako a = bi + bj, bi,bj ∈ B? Wiadomo ,że jest to możliwe, np. kiedy A jest zbiorem kwadratów. Niech Sn = {s1 < s2, < … } oznacza zbiór wszystkich liczb całkowitych, które mają wszystkie czynniki pierwsze mniejsze niż n. Jakie jest największe m = m(n) takie ,że dowolne t ∈ [1,m] może być zapisane jako y = si + sj? Obecnie nie wiemy jak wykazać ,m ≥ n3. Prawdopodobna odpowiedź to około e√n. Dla ciągu X, niech d(x) oznacza gęstość asymptotyczną z X (zakładając jej istnienie). Zakładamy d(A) i d(B) jako dodanie i
• d(A+B) = d(A) + d(B)
gdzie , jak zwykle A + B oznacza zbiór {a+b : a ∈ A, b ∈ A} .To co może się wydarzyć:
Niech μ będzie miarą prawdopodobieństwa na S1, okręgu o obwodzie 1, i nich A^,B^ ⊆ S1 z
μ(A^ + B^) = μ(A^) + μ(B^)
gdzie dodawanie w S1 jest tylko dodawaniem modulo 1. Dla pewengo α > 0 definiujemy
A = {n > 0 : {nα} ∈ A^}
B = {n > 0:{nα} ∈ B}
gdzie {x} oznacza część ułamkową z x
Na przykład, kiedy μ jest miarą Lebesgue a A^ i B^ są przedziałami lub kiedy μ jest miarą atomową wspartą na pewnych liczbach wymiernych a A^ i B^ są pewnymi liczbami wymiernymi w S1 (takimi ,ze A i B są sumami klas kongruencji), możemy uzyskać rozwiązanie dla (&bull). Czy jest prawdą że wszystkie rozwiązania są generowane w podobny sposób? (używając innych grup)? A jest nazywane asymptotyczną podstawą rzędu r jeśli każda wystarczająco duża liczba całkowita jest sumą co najmniej r liczb całkowitych pobranych z A. Mówmimy ,że A ma dokłady rząd t jeśli każda wystarczająco duża liczba całkowita jest sumą dokładnie t liczb całkowitych z A. W pierwszym przypadku piszemy ord(A) = r, w drugim możemy zapisać ord*(A) = t.. Baza A= {a1,a2,…} ma dokładny rząd jeśli i tylko jeśli g.c.d. {a2 - a1, a3 - a2, a4 - a3, …} = 1.Nawet kiedy ord*(A) istnieje może być większe niż ord(A). Na przykład zbiór B definiowany tak : Rysunek 112 gdzie Ik = {x:22k + 1 ≤ x ≤ 22k+1} ma
ord(B) = , ord*(B) = 3
Jedna istnieją dobrze znane granice od stopnia tego wzrostu. Aby to opisać zdefiniujemy funkcję h:Z+ → Z+ jak następuje:
h(r) ≡ max{ord*(A) : ord(A) = r a ord*(A) istnieje}
Wtedy wykażemy ,że
1 / 4 (1+ o(1))r2 ≤ h ( r ) ≤ 5/4(1 + o(1))r2
Nie mamy pojęcia jaki jest poprawny współczynnik r2. Wiadomo ,że h(2) = 4 .Jednak nawet h(3) jest nieznane. Dla zbioru A, niech Am(x) oznacza | {ai1 + … + aim : aik ∈ A} ∩ {1, … ,x}|. Jeśli A jest podstawą a A1(x) = o(x) czy jest prawdą ,że Rysunek 113?. Frelam wykazał ,że dla dowolnego ciągu B gęstości zero Rysunek 114 i ,że stała 3 jest najlepszą z możliwych. Poniższy powiązany wynik został udowodniony przez Rusza. Niech AΔ(x) oznacza |{ai - aj ≤ x : i > j}| dla ciągu A = {a1 < a2 < … }. Wtedy, jeśli A ma gęstość zero Rysunek 115. Przez ograniczony porządek A, oznaczony ordR(A), oznaczamy najmniejszą liczbę całkowita t (jeśli istnieje), taką ,że każda wystarczająco duża liczba całkowita jest sumą co najmniej t różnych składników sumy pobranych z A. Jak wskazał Bateman dla h ≥ 3 , zbiór Ah = {1} ∪ {x > 0 : x ≡ 0 (mod h)} ma ord(A) = h ale nie ma ograniczonego porządku. Jednakże, Kelly wykazał ,że ord(A) 2 implikuje ordR(A) ≤ 4 i przypuszczał ,że , faktycznie, ordR(A) ≤ 3. Jakie są konieczne i wystarczające warunki w podstawie A aby miała ograniczony rząd? Czy istnieje funkcja f( r ) taka ,że jeśli ord(A) = r i ordR(A) istnieją wtedy ordR(A) ≤ f( r )? Jakie są koniecznie i wystarczające warunki aby ord(A) = ordR(A).. Jak zauważyliśmu, sytuacja nie jest jasna nawet dla ciągów wielkości wielomianowych, np. dla zbioru S kwadratów ord(S) = 4 i ordR(S) = 5, podczas gdy zbiór T liczb trójkątnych ma ord(T) = ordR(T) = 3. Czy jest prawdą ,że jeśli dla pewnego r, ord(A - F) = r, dla wszystkich skończonych zbiorów F, wtedy ordR(A) istnieje? A co jeśli założymy ,że rd(A-F) istnieje dla wszystkich skończonych zbiorów F? . Niech n x A oznacz zbiór {at1 + … + ain : aik są różnymi elementami A}. Czy jest prawdą ,że jeśli ord(A) = r wtedy r x A ma dodatnia (niską) gęstość? Jeśli {at1 + … + ais ; atk ∈ A} ma dodatnią górną gęstość wtedy musi s x A również mieć dodatnią górną gęstość? Niech a1, a2, … będą ciągiem definiowanym przez
(i)a1 = 1
(ii)Dla n ≥ 1, an+1 jest najmniejszą liczbą całkowitą przekraczającą an taką ,że wszystkie sumy an+1 + ak , 1 ≤ k ≤ n , różnią się od wszystkich sum poprzedzający aj + ai, 1 ≤ i ≤ j ≤ n .Zatem ciąg zaczyna się 1,2,4,8,13,21,31,45,66,81,97,…. Jaki jest rosnący porządek an? W szczególności czy an = O(n2+ε? Jakie liczby całkowite występują jako różnice aj = ai? Na przykład, czy 22 występuje jako różnica? Czy różnice mają dodatnią gęstość? Można również zbadać odpowiednie pytania gdzie wszystkie sumy trójkowe ai + aj + ak są różne.
Stary problem Dicksona. Przy danym zbiorze liczb całkowitych Ak = {a1 < … ak}, rozszerzamy go do nieskończonego ciągu A = {a1 < … < ak … } przez zdefiniowanie an+1 d;a n ≥ k będącej najmniejszą liczba całkowitą przekraczającą an, która nie jest postaci aij , i,j ≤ n. Czy jest prawdą ,że ciąg różnic am+ - am jest ostatecznie okresowy? Nawet zaczynając od małego zbioru {1,4,9,16,25} wymagane jest tysiące wyrazów znanim wystąpi okresowość. Ulam podniósł następujący problem. Zaczynając od a1 = 1, a2 = 2, zdefiniował an+1 dla n ≥ 2 będącej najmniejszą liczbą całkowitą przekraczającą an, która może być wyrażona jednoznacznie jako ai + aj ,i ≠ j , i,j ≤ n. Zatem, ciąg zaczyna się 1,2,3,4,6,8,11,13,16,18,26,28, …. Co można powiedzieć o tym ciągu. W szczególności, czy występuje nieskończenie wiele par a,a+2? Czy ten ciąg ma okresowe różnice? Czy gęstość wynosi 0? Prawie nic nie wiemy. W końcu, wspomnijmy tai problem. Znajdujemy wielomian f(x) taki ,że wszystkie sumy f(a) + f(b) , a < b ,są różne. Oczywiście, łatwo jest podać taki wielomian - na przykład f(x) = x5 musi z pewnością działać. Niestety, nie możemy udowodnić ,że to f rzeczywiście działa

Zupełność ciągów a tematy powiązane

Dla ciągu A = {α1, α …} liczb rzeczywistych, niech P(A) będzie zdefiniowane przez
Rysunek 116 .Liczbowe wyniki są dostępne w strukturze P(A) dla różnych specjalnych ciągów A, szczególnie kiedy ak są liczbami całkowitymi lub odwrotnościami liczb całkowitych. Ogólne pytanie i wyniki w tym zakresie zazwyczaj różnią się od tych , do czynienia z jakimi mamy działając z podstawami liczb całkowitych ponieważ sumy rozważane nie mają ograniczenia w liczbie używanych wyrazów (natomiast podstawy mają to ograniczenie) chociaż sumy są ograniczone przez wielokrotność określonego wyrazu jaki mogą mieć. Na przykład dla ciągu A = {1,4,9,16,…} kwadratów, dobrze wiadomo ,że A jest podstawą rzędu 4 (twierdzenie Lagarange′a), ale jest mniej dobrze znane ,że 128 ∉ P(A) a wszystkie m > 128 należą do P(A), tzn. dowolna liczba całkowita większa niż 128 jest sumą różnych kwadratów (ale nie samo 128). Nazwijmy ciąg S = (s1, s2,… ) liczb całkowitych zupełnym jeśli P(S) zawiera wszystkie wystarczająco duże liczby całkowite. Nazwijmy S subzupełnym jeśli P(S) zawiera nieskończony postęp arytemtyczny. W końcu nazwijmy S silnie zupełnym jeśli ciąg (sn,sn+1, …) jest zupełny dla każdego n. Na przykład, ciąg T = (t0, t1, …) z tn = 2n jest zupełny ale nie silnie zupełny, dowolny podciąg T(m) = (tm, tm+1, &helip;), m > 0 jest subzupełny ale nie zupełny , a ciąg łączony T* = (t0, x0, t1,x1, t2, x2, …) jest silnie zupełny pod warunkiem ,że nieskończenie wiele z xi jest nieparzystych .Jednym z otwartych pytań odnośnie ciągów zupełnych jest pytanie Jon Folkmana. Jeśli S = (s1, s2, …) jest niemalejącym ciagiem liczb całkowitych spełniających sn < cn dla pewnego c i wszystkich n, wtedy S musi być subzupełnym? Folkman wykazał ,że jest to prawda przy możnej hipotezie sn < cn1-ε. Z drugiej strony dla wszystkich ε > 0, przykładem mogą być ciągi S spełniające sn < cn1+ε które nie są subzupełne Folkman również udowodnił wynik (jaki przypuszczał Erdos) , że jeśli sn ′y są ściśle rosnące a sn < cn2-ε wtedy S jest subzupełne. Silne przypuszczenie ,że to pozostaje prawdziwe jeśli tylko założymy sn ≤ 1 / 2 ⋅n2 dla dużych n jest jeszcze nieudowodnione. Z drugiej strony, znane są kontrprzykłady , które spełniają sn < ?⋅n2 + cn dla pewnego stałego c .Dla ciągów S(p) = p(1),p(2),…) przy p(x) ∈ Z[x], Cassels wykazał ,że oczywistym koniecznym warunkiem dla zupełności S(p) są wystarczające , mianowicie, p(x) powinien mieć dodatni współczynnik wiodący a gcd(p(1),p(2), …) = 1. Zostało to rozszerzone do p(x) ∈ R[x] przez Grahama .Oczywiście, warunki pokazały faktycznie ,że S(p) jest silnie zupełne w tym przypadku. Wynika również z argumentów Cassela ,że jeśli Rysunek 117 jest wielomianem o współczynnikach całkowitych definiującym P-V liczbę wtedy dowolny ciąg S = (s1, s2, …) spełnia liniową rekurencję Rysunek 118 nie jest silnie zupełny. To obejmuje, na przykład, przypadek sn = Fn, n-tą liczbę Fibonacciego, definiowane przez F0 = 0, F1 = 1, Fn+2 = Fn+1 + Fn n ≥ 0, jak również ciągi formowane przez pobranie brzegowych powtórzeń z Fn, tzn. Rysunek 119. Jednak jeśli każdy termin tego ciagu jest powtarzany wystarczająco często (w zależności od wyrazu) wtedy jest silnie zupełny. W szczególności, wykazano ,że Rysunek 120 ,gdziemnn maleje a Φ = 1+√5 / 2 , jest silnie zupełna jeśli i tylko jeśli : Rysunek 121. W dowolnym przypadku S* nie jest silnie zupełny jeśli : Rysunek 122. Jest z pewnością prawdą ,że podobne wyniki muszą posiadać inne ciągi spełniające liniową rekurencję chociaż wydaje się to być złożonym tematem, który jest relatywnie nie ruszonym. Dla ciągu zupełnego S, próg zupełności θS jest definiowany jako najmniejsza liczba całkowita θ taka ,że m ≥ θ implikuje m ∈ P(S). Bardzo mało wiadomo o θs, nawet dla relatywnie prostych ciągów S(p) = (p(1), p(2),…) przy p(x) ∈ Q[x]. Wartości z θs dla S(p) z p(x) = xn znamy tylko dla n ≤ 5. Są to : θS(x) = 1 , θS(x2) = 128, θS(x3) = 12758, θS(x4) = 5134240, θS(5) = 67898771. Wydaje się wysoce prawdopodobne ,że θS(xn) > θS(xn + 1) może pojawić się dla nieskończenie wielu n. Dobrym kandydatem może być n = 2t dla dużego t (lub nawet t ≥ 3?) z powodu wysoce ograniczonych wartości z m2t modulo 2t+1. Dla ciągu S = (s1, s2,…) niech θs(n) oznacza próg zupełności dla ciągu ściętego (sn, sn+1, sn+2, …) .Nawet dla bardzo prostych ciągów, zachowanie θs(n) może być bardzo złożone. Na przykład dla S = S(x2) = (1,4,9,…, n2, …), funkcja θs(n) / n2 oscyluje w złożony sposób między 4 a 5, dążąc do 5 jeśli n → ∞ dla dokładnie 1487 punktów między dowolnymi kolejnymi potęgami 4. Faktycznie, dla tego przypadku θs(n) jest znana dla prawie wszystkich wartości n (na przykład, jest zawsze parzysta z wyjątkiem unikalnej wartości θs(3) = 223 chociaż dokładne określenie dla wszystkich wartości n wydaje się bardzo trudne. Dla ciągu S = (s1, s2, …) z racjonalnym wzroste, θs(n)/sn często wydaje się dążyć do granicy. Na przykład, dla ciągu P = (p1,p2,…) liczb pierwszych , Klove przypuszczał na bazie dowodów obliczeniowych ,ze θp(n) / pn → 3 (co implikowałoby przypuszczenie Goldbacha). Można wykazać metodami probabilistycznymi ,że dla dowolnego α ≥ 2 istnieje ciąg S = (s1, s2, …) z Rysunek 123. Było by ciekawym podać konstrukcję dla każdego α. Jeśli S jest zaburzone nieznacznie, jego właściwości subzupełności nie są często zbytni zmienione. Na przykład, jeśli S*=(s1*, s2*, …) przy sn* = p(n) + γ(n) gdzie p(x) ∈ Z[x] a γ(n) = O(n1-ε) dla ε > 0 , Burr wykazał ,że S* jest subzupełny. Może być tak ,że pozostaje to prawdą przy słabej hipotezie, że γ(n) = o(n) lub nawet γ(n) = O(n). Może być definitywnie błędne jeśli wymagamy tylko γ(n) = o(n1+ε) dla dowolnego stałego ε > 0. Faktycznie można wykazać ,że dla dowolnego ciągu A = (a1, a2, …) i dowolnej funkcji f(n) przy Rysunek 124 istnieje ciąg A′(a′1, a′2, …) przy |an - a′n < f(n) dla n wystarczająco dużego, która nie jest subzupełna. Nie wiadomo czy istnieje ciąg S = (s1, s2, …) przy lim Sn+1/Sn = 2 tak ,że P(S′) ma gęstość jeden dla każdego koskończonego podciągu S′ z S. Wiemy ,że dla dowolnego ε > 0, jeśli Sn+1/Sn ≥ 1 + √5/2 + ε dla dużego n wtedy S nie może być silnie zupełny. Z drugiej strony, stała 1 + √5/2 jest najlepszą z możliwych jak pokazują wyniki. Niech F* = (f*1, f*2, …) oznacza ciąg zdefiniowany przez f*n = Fn - (-1)n gdzie Fn jest n-tą liczbą Fibonacciego. Graham wykazał, że F* cieszy poniższe niezwykłe właściwości :
(i)F* pozostaje zupełne po usunięciu z niego dowolnego skończonego zbioru elementów, tj. F* jest silnie zupełne
(ii)F*nie jest dłużej kompletne po usunięciu z niego nieskończonego zbioru
Czy jest prawdą ,że ciąg S = (s1, s2, …) przy Sn+1 / Sn ≥ 1 + ε spełnia zarównow (i) i (ii) musi mieć lim &sdotSn+1/Sn = 1 + √5/2 ? Łatwo jest zobaczyć ,że jeśli Sn+1/Sn > 1 + √5/2 wtedy (ii) jest spełnione automatycznie. Nie jest trudno zbudować bardzo nieregularny ciąg (tzn. lim inf ⋅ Sn+1/2 = 1, lim sup ⋅ Sn+t/Sn = ∞), który spełnia (i) i (ii). Skończona wersja tego problemu jest bardzo słabo zrozumiana. Szczególnie dla danego ciągu S, niech C(n) i N(n) oznacza poniższe instrukcje:
C(n) : Jeśli dowolne n elementów jest usuniętych z S do postaci S′ wtedy S&prime jest zupełny;
N(n) : Jeśli dowolne n elementów jest usuniętych z S do postaci S′ wtedy S′ nie jest zupełny
Pytanie: Dla jakich wartości m < n istnieją ciągi S , które spełniają zarówno C(m) i N(n)?. Na przykład, T = (1,2,4,… 2n,…) spełnia C(0) i N(1) , podczas gdy F = (F1, F2, F3, …) = (1,1,2,3,5,8,…) spełnia C(1) i N(2) . Nie wiadomo czy istnieje ciąg spełniający C(2) i N(3). Niech S(t,&aplha;) = (s1, s2, …) przy sn = [tαn] . Dla jakich wartości t i α S(t,α) jest zupełne? Nawet w zakresie 0 < t < 1 , 1 < α < 2, zachpwanie jest niespodziewanie złożone. Na przykład, wiadomo ,że dla dowolnego k istnieje tk &isin (0,1) tak więc {α : S(tk, α) jest zupełne} składa się z więcej niż k rozłącznych odcinków prostych. Wydaje się prawdopodobne ,że S(t,α) jest zupełny dla wszystkich 1 < α < 1 + √5/2 i wszystkich t > 0. Możliwe jest rozważenie pytania zupełności dla ciągów liczb wymiernych. Na przykład, wiadomo ,że ciąg S = (s1, s2,…) przy sn = n + 1/n jest silnie zupełny. Prawdą jest ,że jeśli p(x) ∈ Q(x) wtedy ciąg A = (a1, a2, … przy an = p(n) + 1/n jest również silnie zupełny? Która funkcja wymierna r(x) ∈ Z wymuszająca (r(1), r(2), …) będzie wymierna? Załóżmy α i β są dodatnimi liczbami rzeczywistymi z niewymiernym α / β i niech S oznacza ciąg ([α],[β],[2α],[2β],…,[2nα];[2nβ]. Czy S jest zupełny? A co jeśli 2 jest zastępowane przez γ gdzie 1 < γ < 2? Nazwijmy ciąg S = (s1,s2, …) liczb wymiernych Q-zupełnym jeśli każda wystarczająco dużo liczb wymiernych należy do P(S) Na przykład, jeśli każda wystarczająco duża liczba pierwsza i każdy wystarczająco duży kwadrat należy doo S, wtedy S-1 = (1/s1, 1/s2, …) jest Q-zupełny (faktycznie wszystkie dodatnie liczby wymierne należą do P(S-1)). Wykazano ,że jeśli Rysunek 125 wtedy istnieje bn ≥ sn takie ,że ciąg (1/b1, 1/b2, …) jest Q-zupełne. Przyjmijmy S = (s1, s2,…) jest ciągiem rosnącym spełniającym sn+1/sn ≥ c > 1 dla pewnego c. Czy jest możliwe dla P(S-1 zawierać wszystkie liczby wymierne w pewnym przedziale (α,β), α < β? Erdos i Bleicher przypuszczali, że odpowiedź brzmi nie. Niech a1 < … < ak ≤ n będzie ciągiem liczb całkowitych i formuje wszystkie sumy Rysunek 126 . Czy można mieć cn2 różnych liczb w tym zbiorze dla pewnego c > 0? To nie zdarzy się dla wyboru at = i. Co wydarzy się jeśli nałożymy ograniczenie monotoniczności , ale tylko twierdzimy ,że ai będą różne. Być może jakaś permutacja z {1,2,…,n} a cn2 takich sum "przedziałów". Ile kolejnych liczb całkowitych przekraczających n można przedstawić jako Rysunek 127 ? Czy jest prawdą ,że dla dowolnego c > 0, możemy osiągnąć cn? Na przykład, biorąc ai = i, możemy zazwyczaj przejść do 2n (nie możemy pobrać potęgi 2 przez taką sumę). Jednak pomijając pewne liczby całkowite możemy pominąć potęgi 2. Załóżmy, że 1 ≤ a1 < … ak ≤ n jest zbiorem liczb całkowitych z taką właściwością ,że wszystkie sumy kolejnych bloków Rysunek 128 są odmienne. Erdos i Harzheim pytali , jak duże może być k? Musimy mieć k = o(n)? A co jeśli usuniemy ograniczenie monotoniczności i/lub ograniczenie odrębności? A jakie jest najmniejsze m ,które nie jest postaci Rysunek 128 > Czy może być większe niż n? Można wykazać ,że : Rysunek 129 . Czy jest prawdą ,że Rysunek 130 jest ograniczone, niezależne od n?. Czu istnieje ciąg 1 ≤ a1 < a2 … , taki ,że liczba reprezentacji n jako suma kolejnych ai jest zawsze dodatnia? Czy można dążyć do nieskończoności z n? Erdos i Moser rozpatrywali przpadek, gdzie ai są liczbami pierwszymi. Przypuszczali ,że lim sup liczby reprezentacji jest nieskończony i również ,że gęstość liczb całkowitych, które mają dokładnie k reprezentacji istnieje. Nie musimy nawet wiedzieć ,że górna gęstość liczb całkowitych z co najmniej jedną taką reprezentacją jest dodatnia .Adrews zbadał następujący powiązany problem MacMahona. Niech a1 < a2 < … będzie nieskończonym ciągime gdzie at = k a ai+1 jest najmniejszą liczbą całkowitą , która nie jest sumą kolejnych wcześniejszych aj. Co można powiedzieć o gęstości ai? Niech f(n) oznacza najmniejszą liczbę całkowitą taką ,że można podzielić zbiór liczb całkowitych {1,2,…,n} na f(n) klas takich ,że n nie może być wyrażone jako suma różnych elementów z tej samej klasy. Można wykazać ,że f(n) → ∞ ale nie mamy pojęcia jak szybko. Ile liczb całkowitych mniejszych niż n/k można podać ,tak ,ze n nie jest sumą podzbioru tych liczb całkowitych (gdzie k jest stałe a n jest duże)? Czy to zależy od n w sposób nieregularny? Dla ciągu 0 < a1 < … n, niech Fn(t) oznacza liczbę rozwiązań Rysunek 131 . Erdos i Moser udowodnili ,że Fn(t) < c2n/n3/2 ⋅(log n)3/2; przypuszczali ,ze współczynnik (log n)3/2 może być pominięty , co udowodnili Sarkozy i Szemeredi. Stanley wykazał ,że max Fn(t) zakładamy ,jeśli ai formują postęp arytmetyczny a Rysunek 132 . W końcu ,załóżmy α1 < … < αk < x jest ciągiem liczb rzeczywistych z maksymalnym k takim ,że dwie sumy Rysunek 133 , różnią się o co najmniej .Czy jest prawdą ,że k ≤ log x / log 2 + O(1)? Jest to uogólnienie przypuszczenia Erdosa, który zadał to samo pytanie kiedy ai są liczbami całkowitymi. Najlepsze osiągnięte wyniki dla problemu całkowitości to k ≤ log x/ log 2 + log log x / 2 log 2 + O(1). Z drugiej strony, Conway i Guy wykazali, że dla n ≥ 21, możliwe jest znalezienie n + 2 liczb ≤ 2*, wszystkie z różnymi podzbiorami sum, która jest większa niż uzyskane przez wybranie liczb 1,2,4,…2k,… 2n. Erdos przypuszczał a C. Ryavec udowodnił, że jeśli 1 ≤ a1 < a2 < … an jest zbiorem liczb całkowitych ze wszystkimi podzbiorami różnych sum (tzn. P(A) = 2n), wtedy Rysunek 134 . Hanson, Steele i Stenger wykazali Rysunek 135 dla wszystkich liczb rzeczywistych s ≥ 0

Niewymierności i przestępności

Liouville pierwszy udowodnił istnienie liczb przestępnych. Patrząc z naszego punktu widzenia wydaje się dziwnym ,że nie uczynił tego Euler. Cator potem udowodnił ,że liczby algebraiczne są przeliczalne a rzeczywiste nie. Pierwszy znany dowód przestępności pochodzi do Hermite′a, który udowodnił ,że liczba e jest przestępna. Było to wkrótce po tym jak Lindemann udowodnił przestępność π w 1882 roku. Jednak wciąż istnieją zaskakujące luki w naszej wiedzy np. o ile wiemy, e + π stała γ Eulera i ζ(2n+1), n ≥ 2, mogą wszystkie być wymierne. Apery, używając tylko ułamków łańcuchowych i współczynników dwumianowych ,że ζ(3) jest niewymierna. . Wiadomo od pewnego czasu ,że suma Rysunek 136 jest przestępna jeśli n1 < n2 < … jest ciągiem, który rośnie dosyć szybko n. lim sup nk/kt = ∞ dla każdego t jest wystarczające. Jak wiemy słabszy warunek lim sup nk/k = ∞ wystarczy. Z drugiej strony, nie znamy liczb algebraicznych dla których lim sup (nk+1 - nk = ∞ ,ale możemy z pewnością oczekiwać ,że √2 jest taką liczbą, Faktycznie, być może wszystkie niewymierne liczby algebraiczną są normalne. Wydaje się ,że jest nadzieja udowodnienia ,że jeśli nk > ck2 wtedy Rysunek 137 nie jest pierwiastkiem żadnego wielomianu kwadratowego. Jak zwykle d(n) i v(n) oznaczają liczbę dzielników z n i liczbę pierwszych współczynników z n, odpowiednio. Wiemy ,że ∑d(n)/2n jest niewymierne ale jest bardzo uciążliwe ,że nie może ∑v(n)/2n nie może być udowodnione niewymiernie. Prowadzi to do kilku ciekawych przypuszczeń np. czy jest nieskończenie wiele w takich ,że dla pewnego c i pewnego i v(n+1) < ci? . Wiemy już trochę o sicie, aby móc obsłużyć takie pytanie. Nie jest trudno udowodnić ,że Rysunek 138 są niewymierne ale niewymierność Rysunek 139 jest raczej beznadziejna do udowodnienia. Kilka innych wyników tego typu :
(i)∑pn/n! jest niewymierne ponieważ jest ∑pkn/n! dla każdego k, gdzie pn oznacza n-ta liczbę pierwszą; z drugiej strony niewymierność ∑pn/2n jest prawdopodobnie beznadziejna; wiemy ,że ∑εn/2n jest niewymierne, gdzie εn = 1 jeśli P(n+1) > P(n) i 0 jeśli P(n+1) < P(n) , a P(n) oznacza największy współczynnik pierwszy z n.
(ii)∑σk(n)/n! jest niewymierne dla k = 1 lub 2 ale nie wiadomo dla jakiego k > 2, gdzie σn oznacza sumę k-tych potęg dzielników n
(iii)∑1/2n - 1 = ∑d(n)/2n jest niewymierne; jednakże ani ∑ 1 / 2n - 3 ani ∑1 /n! - 1 nie wiadomo czy są niewymierne. Być może Rysunek 140 jest niewymierne dla dowolnego n1 < n2 < …. Być może ∑d(n)/a1 … an jest niewymierne jeśli an → ∞ ale zostało to udowodnione przy założeniu ,że an ≥ an-1. Być może jest stała c ,taka ,że dla nieskończenie wielu n , d(n+1) < ci dla wszystkich i ≥ 1. Ta nierówność byłaby pomocna w dowodzeniu niewymierności ,ale prawdą jest że będzie niezwykle trudno to udowodnić. Suma ∑an/2an powinna być niewymierna jeśli an/n → ∞. Można wykazać ,że jeśli an+1 - an → ∞ wtedy ∑an/2an jest niewymierne. Faktycznie, nie znamy żadnego szeregu ∑an/2an będącego wymiernym dla którego lim sup (an+1 - an = ∞) ale takie szeregi prawdopodobnie istnieją. Suma ∑an/2an jest znana jako niewymierna przy silnej hipotezie ,że an > cn √log n log log n. Suma ∑ q/2q gdzie q jest zakresem nad liczbami squarefree (niepodzielnymi przez kwadrat liczby), powinna być niewymierna ale widać na to dowodu. Doszliśmy do następującego problemu: Czy równanie Rysunek 141 ma rozwiązanie dla nieskończenie wielu n ? Dla wszystkich n? Czy istnieje wymierne x dla którego Rysunek 142 ma dwa rozwiązania?. Jeśli an1 / 2 n → ∞ wtedy nie trudno wykazać ,że ∑ 1 / an jest niewymierne. Nazwijmy ciąg a1 < a2 < … ciągiem niewymiernym jeśli dla wszystkich ciągów liczb całkowitych {tn} przy tn ≥ 1, suma Rysunek 143 jest niewymierna. Na przykład, ciąg an = 22n jest ciągiem niewymiernym podczas gdy an = n! nie. Byłoby miło znaleźć wolno rosnący ciąg z tą właściwością. Jeśli an jest ciągiem niewymiernym wtedy an1/n → ∞ . Jeśli ak nie rośnie zbyt szybko wtedy dla każdego wystarczająco małego α > 0 istnieje odpowiedni wybór z tn taki ,że ∑ 1/tnan = α. Na przykład , dzieje się tak jeśli an < cn dla wszystkich n. Możemy nazwać a1,a2,… ciągiem niewymiernym jeśli dla każdego ciągu bn z bn/an → 1, ∑ 1/bn jest niewymierne. Z tej definicji, nawet nie wiemy czy an = 22n jest ciągiem niewymiernym Prawdopodobnie niewymierność ciągu tego typu musi również spełniać an1/n → ∞. Inną możliwością będzie nazwanie an ciągiem nierównomierności jeśli dla każdego ciągu bn z |bn| < C, ∑ 1/an + bn jest zawsze niewymierne. W tym przypadku, 22n jest ciągiem niewymiernym chociaż nie wiemy o 2n lub n!. Czy istnieje ciąg niewymierności tego typu z an < nk? Powiązany wynik jest twierdzeniem Erdosa: Jeśli lim sup an1 / 2n = &infin a ∑ 1/an jest wymierne wtedy dla każdego ε > 0 istnieje nieskończenie wiele m z am < m 1+ε. Pytamy : Jeśli an → ∞ jest prawdziwe , czy zarówno Rysunek 144 może być wymierne? D.Cantor zaobserwował ,że to mam miejsce dla Rysunek 145; dotychczas jest to najszybciej rosnący ciąg która ma tą właściwość wymierności. Jeśli 1 jest zastępowane przez dużą stałą, wtedy mogą być użyte wielomiany wyższego stopnia. Na przykład, jeśli p(x) = x3 + 6x2 5 x, wtedy zarówno Rysunek 146 i Rysunek 147 są wymierne (ponieważ zarówno p(n) i p(n) + 8 całkowicie dzielą się na liczby całkowite) Podobne przykłady są znane dla wielomianów ze stopniem tak dużym jak 10. Czy istnieje wielomian f(x) stopnia przekraczającego 10 takim ,że dla pewnego m , zarówno f(x) i f(x) + m całkowicie dzielą całkowici na liczby całkowite nie wiadomo. Tu mamt przypuszczenie Stolarsky′ego: Rysunek 148, które nie może być wymierne dla każdej liczby dodatniej całkowitej t . Nie trudno wykazać ,że jeśli ak → ∞ dosyć szybko wtedy ∑ 1/akak+1 jest niewymierne ; faktycznie, ak1/2k > 1 + ε powinno być wystarczające. Byłoby ciekawym znać jakie jest najsilniejsze twierdzenie tego typu. Czy jest prawdą ,że jeśli an+1/an2 → 1 wtedy ∑ 1/an jest niewymierne, chyba ,że an+1 = an2 - an + 1 dla n ≥ n>0? Odnotujmy ,że dla ciągu liczb Fibonacciego Fn definiowanego przez F0 = 0, F1 = 1, Fn+2 = Fn+1 + Fn , n ≥ 0, mamy : Rysunek 149 . Jednak nic nie wiadomo o charakterze powiązanych sum : Rysunek 150, gdzie Ln = Fn-1 + Fn+1. Czy jest prawdą , że Rysunek 151 jest niewymierne dla dowolnego ciągu n1 < n2 < … z nk+1/nk ≥ c > 1? Czy wystarczy mieć nk/k → ∞? A co z Rysunek 152 ? Niech Q będzie zbiorem liczb pierwszych (możliwie nieskończonym) i niech a1 < a2 < a3 < … oznacza zbiór liczb całkowitych wszystkich pierwszych współczynników należących do Q. Suma : Rysunek 153 okazuje się być niewymierna jeśli Q jest nieskończone. Co się stanie dla skończonego Q(z więcej niż jednym elementem)? Erdos i Straus udowodnili ,ze jeśli weźmiemy wszystkie ciągi liczb całkowitych a1, a2, … z ∑1/ak < ∞ wtedy zbiór Rysunek 154 zawiera zbiór otwarty. Czy to samo jest prawdą w trzech (lub więcej) wymiarach ,np. biorąc wszystkie (x,y,z) z : Rysunek 155. Niewymierność może być często wydedukowana jeśli wiemy więcej o równaniach diofantycznych. Na przykład, mamy typowe pytanie. Zbiór An = lcm(1,…n) i wstawiamy Rysunek 156. Czy ∑1/A′n jest niewymierne? To wynika bezpośrednio jeśli możemy wykazać ,że q2 = p3 < q1-ε ma nieskończenie wiele rozwiązań w liczbach pierwszych p i q. Wydaje się ,że szeregi ,jak, : Rysunek 157 są bardzo trudne do traktowania chociaż są z pewnością niewymierne. Jednak wiemy na przykład ,że : Rysunek 158, a więc, są przestępne. Niech f(n) → ∞ jeśli n → &infin. Czy jest prawdą ,że : Rysunek 159 jest niewymierne? Odpowiedź jest prawie z pewnością twierdząca jeśli f(n) jest założona jako niemalejąca ale brakuje nam metod dla podejmowania takich pytań

Problemy diofantyczne

Tu omówimy różne kwestie, które można by sklasyfikować w kategorii problemów "diofantycznych". Pierwszym z nich jest przypuszczenie Catalana, które zakłada ,że 8 i 9 są jedynymi kolejnymi potęgami. Tijdeman dowodził ,że nie istnieją dwie kolejne potęgi przekraczające dużą ale obliczalną liczbę. Jeśli A = {a1 < a2 < … } oznacza zbiór potęgowy, wtedy Choodnowki udowodnił ,że istnieje obliczalna funkcja f(n) dążąca do nieskończoności przy n takim ,że an+1 - an > f(n) . Nie ma wątpliwości ,że f(n) > c1ne2 .Drugim takim problemem jest przypuszczenie ,ze iloczyn kolejnych liczb całkowitych nigdy nie jest potęgą. Nie trudno udowodni ,że dla dowolnego b istnieje skończenie wiele ciągów 0 < a1 < a2 < … < at przy ai+1 - ai < b takie ,że a1a2 …at jest potęgą .Wiadomo ,że powiązany współczynnik dwumianowy ( n k) nigdy nie jest potęgą dla k ≥ 4 i n ≥ 2k. Oczywiście (n 2) jest pierwiastkiem nieskończenie często. Metdody Tijdemana dały prawdopodobnie (n 2) ≠ xl , l > 2 a (n 3) = xl implikuje n = 50 , l = 2 (wiadomo ,że jest to jedyne rozwiązanie dla l = 2). W tym samym duchu można zapytać kiedy iloczyn dwóch lub więcej rozłącznych bloków klejnych liczb całkowitych może być potęgą. Na przykład jeśli A1, … An są rozłącznymi przedziałami każdy składający się z co najmniej 4 liczb całkowitych, wtedy być może iloczyn Rysunek 160 jest niezerowym kwadratem w tylko skończonej liczbie przypadków. Pomerance wykazał ,że iloczyn czterech bloków z 3 kolejnymi liczbami całkowitymi (2n-1 -1)2n-1(2n-1+1), (2n -1)2n(2n + 1), (22n-1-2)(22n-1-1)22n-1 i (22n-2)(22n-1)22n jest kwadratem 23n(22n-2 -1)(22n-1 -1)(22n - 1). Teraz zajmijmy się kilkoma problemami współczynników pierwszych kolejnych liczb całkowitych. Zbiór Rysunek 161, gdzie jak zwykle p oznacza liczbę pierwsza. Mahler udowodnił ,że dla każdego stałego k i l Rysunek 162 dla każdego ε > 0 o ile n > n0 (ε,k,l). Z drugiej strony łatwo zauważyć ,że dla pewnego c > 0
Rysunek 163 , dla nieskończenie wielu n. To oszacowanie w (1) [Rysunek 162] powinno być poprawione ale z pewnością jest to trudne. Z drugiej strony, nie powinno być zbyt trudno poprawić (2) [Rysunek 163] , np.: lim sup A(n,3)A(n+1,2)/n log n → ∞. Jednakże, określenie dokładnego maksymalnego rzędu A(n,3)A(n+1,3) będzie bez wątpienia bardzo trudne. Usatwmy : Rysunek 164. Łatwo zauważyć przez uśrednienie procesu ,że f(n,.k) < ck. Stare przypuszczenie Erdosa zakłada ,że dla każdego ε > 0 istnieje k0(ε) takie ,że dla k > k0(&epsilon)
max f(n,k)/k → 0 jeśli k → ∞ . Będzie ciekawsze określenie dokładnego rzędu (w k) z max f(n,k) - nie ma jednak przekonującego przypuszczenia. Nie trudno zobaczyć ,że dąży to do nieskończoności z k. Niech Bk(n) oznacza : Rysunek 165 .Erdos pytał Mahler czy istnieje nieskończenie wiele liczb całkowitych n, n+1 z
(3) B2(n) = n, B2(n+1) = n+1
Mahler bezpośrednio zaobserwował ,że odpowiedź jest na tak, ponieważ x2 - 8y2 = 1 ma nieskończenie wiele rozwiązań. Jednak system
B2(n) = n, B2(n+1) = n+1, B2(n+2) = n+2
prawie z pewnością nie ma rozwiązań. Czy prawdą jest ,że wszystkie (lub wszystkie ale skończone) liczby rozwiązań (3) pochodzi z równań Pelliana i ,że liczba n < x spełnia (3) jest to co najmniej (log x)c?. Czy jest prawdą ,że B2 = n, B3(n+1) = n+1? nie ma rozwiązań? Czy n = 8 jest jedynym rozwiązaniem dla B3(n) = n, B2(n+1) = n+1?. Ustawiamy Rysunek 166. Być może G(n,k) kn2 ,ale nie możemy nawet obalić ,że nieskończenie często Rysunek 167 dla każdego k. Wydaje się bardzo prawdopodobne ,że G(n,k) < n2+ε dla każdego k i ε > 0. Byłoby ciekawe uzyskać nietrywialną górną i dolną granicę dla Rysunek 168 dla r > 2. Czy jest prawdą ,że Rysunek 169 dla każdego r i k > 1 ? Nie jest to nawet jasne dla r = 3. Oznacz,y przez P(n) największy współczynnik pierwszy z n. Klasyuczny wynik stanowi ,że jeśli f(n) jest wielomianem, który nie jest potęgą liniowego wielomianu wtedy P(f(n)) → ∞ jeśli n → ∞. W szczególności, wiadomo że P(n(n+1)) > c log log n. Bez wątpienia może być to znacząco poprawione. Istnieją powody heurystyczne dla wiary ,ze poprawny rząd wielkości to (log n)2. Schinzel zaobserwował ,że dla nieskończenie wielu n : P(n(n+1)) < nc/log log log n. Czu jest prawdą ,że dla każdego n ≥ n>sub>0(ε) istnieją dwa (lub więcej ogólnych k) kolejnych lizb całkowitych mniejszych niż n, których wszystkie współczynniki pierwsze są mniejsze niż nepsilon;? Problem wydaje się trudny. Podobnie, można zapytać czy istnieje nieskończenie wiele n takich ,że P(n) < √n, P(n+1) < √n+1 , lub ogólniej, P(n+1) < n1-ε , 1 ≤ i ≤ k. Trochę o tym wiemy. Pomerance wykazał ,że P(n) > nε-1/2 , P(n+1) > (n+1)ε-1/2 ma rozwiązania poprzez rozważania gęstości. W podobnym tonie, czy prawdą , że dla każdego n > n0(ε) może być zapisane w postaci a + b z P(a) < nε, P(b) < nε ? . Niespodzianką jest jak niespodziewanie trudne jest to pytanie. Erdos i Pomerance wykazali , że jeśli f(δ) oznacza górną gęstość zbioru n z n < P(n)/P(n+1) < nδ, wtedy f(δ) → 0 jeśli δ → 0. Wykazali też ,że P(n) < P(n+1) > p(n+2) , P(n) > P(n+1) < P(n+2) i P(n) < P(n+1) < P(n+2) ,każdy ma nieskończenie wielu rozwiązań ale nie można udowodnić tego samego dla P(n) > P(n+1) > P(n+2). Przypuszczali ,ze zbiór z n P(n) > P(n+1) ma gęstość 1 / 2 ale można tylko udowodnić ,że on i jego uzupełnienia każdy ma pozytywną górną gęstość. Jeśli wiemy ,że P(n(n+1)/ log n → ∞ jeśli n → ∞ wtedy wynikać będzie ,że równanie
(4) n! = ∏ ai! , n > a1 ≥ a2 ≥ …
może mieć tylko skończenie wiele nietrywialnych rozwiązań. Przez nietrywialne, mamy na myśli ,że a1 ≤ n-2 ponieważ w przeciwnym razie możemy ustawić n = a2!a3!…. Hickerson przypuszczał ,że największe nietrywialne rozwiązanie dla (4) to 16! = 14!5!2!. Równanie
(5) a1!a2! … ai! = y2 zostało badane przez Erdosa. Definiujemy Fk przez Fk = {m : dla pewnego A ⊆ {1,2,…,m} z m ∈ A i |A| ≤ k, &prod a! = y2 dla pewnej liczby całkowitej y} i zbiór Dk = Fk - Fk-1. Oczywiście, jeśli p jest liczbą pierwszą wtedy p ∉ Dk dla dowolnego k. Jeśli dla zbioru S ⊆ Z+ niech S(n) znacza |S ∩ {1,2,… n}|, wtedy wiemy ,że :
(i)D2 = {n2 : n > 1};
(ii) D3(n) - o(D4(n))
(iii) Jeśli p ∈ {2,3,5,7,11} jest właściwym dzielnikie z n wtedy n ∈ F5
(iv) Dla prawie wszystkich liczb pierwszych p, 13p ∉ F5
(v) Ostatni element w D6 to 527 = 17 ⋅ 31
(vi) Dk = ∅ dla k > 6
Nie znamy rzędu wzrostu D4(n) , na przykład. Wydaje się prawdopodobne ,że D6(n) > cn ale tego nie wiemy. Istniało przypuszczenie Grimma ,że jeśli n + 1, …, n+k są kolejnymi liczbami złożonymi, wtedy istnieje zbiór k różnych liczb pierwszych pi takie ,że pi |n + 1, I ≤ l ≤ k. To przypuszczenie jest z pewnością bardzo głębokie ponieważ jak obserwował Erdos i Selfridge, implikowało ,że istnieje zawsze liczba pierwsza między dwoma kolejnymi kwadratami. Najsilniejsze wyniki w tym kierunku to wyniki Ramachandra, Shoreya i Tijdemana. Wykazali oni ,ze przypuszczenie Grimma dla n > n0 o ile k < c(log n/ log log n)3 .Czy jest prawdą ,że Rysunek 170 nigdy nie jest wolnym kwadratem jeśli n > 4? Irytujące jest to ,że problem jest trudny. Ogólniej , oznaczmy przez f(n) największą liczbę całkowitą taką ,że dla liczby pierwszęj p, pf(n) dzieli się przez Rysunek 171. Jednostka f(n) powinna dążyć do ∞ jeśli n → ∞ ale tego nie wiemy. Wiemy ,że n = 23 jest największą wartość n dla której wszystkie Rysunek 172 są squarefree dla 0 ≤ k ≤ n. Z drugiej strony, nie możemy nawet obalić f(n) > c log n. Wiemy ,że dla dwóch liczb pierwszych p i q, istnieje nieskończenie wiele n dla których Rysunek 173. Jednakże , dla trzech liczb pierwszych nie wiemy prawie nic. Na przykład czy Rysunek 174 nieskończenie często? Obliczenia W.Wysckiego wykazały ,że najmniejsza nieparzysty współczynnik pierwszy z (2n n) to 13 dla n = 3160 i co najmnej 11 dla 3160 < n < 1090. Zostało to rozszerzone do 5,3 x 10100 przez Kimblea. Jeśli ustawimy Rysunek 175 wtedy nie możemy zdecydować czy f(n) jest nieograniczony. Wykazaliśmy ,że Rysunek 176 , tak ,że dla wszystkich ale o(n) liczb całkowitych m ≤ n , f(m) = y0 + o(1). Wydaje się prawdopodobne ,że gęstość liczb całkowitych n dla Rysunek 177 jest squarefree dla co najmniej r wartości z k, 1 ≤ k ≤ n-1, ma gęstość cr > 0 i ,że ∑r=0 cr = 1. Możemy udowodnić ,że dla k stałego i dużego, gęstość z n takie ,że Rysunek 178 jest squarefree jest mniejsze niż εk gdzie εk → 0 jeśli k → ∞ Również istnieje nieskończenie wiele n takich ,że Rysunek 179, 1 ≤ k ≤ n-1 , niegdy nie jest squarefree. Prawdopodobnie ich gęstość jest dodatnia. Dla danego, n , niech s (n) oznacza największą liczbę całkowitą taką ,że dla pewnego k, Rysunek 180, jest podzielne przez s(n) potęgę liczby pierwszej. Łatwo zauważyć ,że s(n) → ∞ jeśli n → ∞. Faktycznie nie trudno wykazać ,że s(n) > clog n, co jest prawidłowym rzędem wielkości. Jednakże, jeśli S9n) oznacza największą liczbę całkowitą taką ,że dla wszystkich k, ; ≤ n , Rysunek 181 jest podzielne przez S(n) potęgę liczby pierwszej, wtedy jest całkiem prawdopodobne ,ze lim sup S(n) = ∞ chociaż nie znamy tego obecnie. Prawdopodobne jest to ,że Rysunek 182, ale to wydaje się dość głębokie. Nie trudno udowodnić ,że Rysunek 183. Dla k1+ε będzie prawdą ,że Rysunek 184. Pozwala nam to skrócić do Rysunek 185 .Liczba całkowita n jest nazywana złą, jeśli należy do pewnego przedziału u ≤ n ≤ v takiego ,że największy współczynnik pierwszy P(π(u,v)) występuje w π(u,v) z wykładnikiem większym niż 1 . Niech B(x) oznacza liczbę złych liczb całkowitych nie przekraczających x. Czy jest prawdą ,że B(x) jest asymptotyczne do B′(x), liczba liczb całkowitych n ≤ x dla których P(n)2 | n? Można wykazać ,że
B′(x) = x / exp((c+o(1)) (log x log log x)/2). Wiemy tylko ,że B(x) > x1-ε dla dowolneg0 ε > 0. Liczba całkowita n jest nazywana bardzo złą jeśli dla pewnego u i v , przy u ≤ n ≤ v, π(u,v) jest silne, tzn. p | π(u,v) implikuje p2|π(u,v). Liczba bardzo złych liczb mniejszych niż x powinna być mniejsza niż cx1/2 i, faktycznie, prawdopodobnie jest asymptotyczne do liczby silnych liczb mniejszych niż x ale tego nie wiemy. Pisaliśmy wcześniej ,że n(n+1) jest silne dla nieskończenie wielu n. Erdos i Selfrigde przypuszczali ,że iloczyn więcej niż dwóch kolejnych liczb nigdy nie jest silny. Jeśli P(π(u,v))2 | π(u,v), wtedy v - u musi być relatywnie małe. Wynika to z wyników Ramachandr, że jest co najmniej v1/2-ε ale bez wątpienia jest faktem ograniczenie przez vε dla każdego ε > 0. Z pewnością może być arbitralnie duże , chociaż nie udowodniono tego. Czy jest prawdą ,że dla każdego k istnieje nieskończenie wiele wartości p takiego ,że Rysunek 186. Jeśli p(x) oznacza ,że najmniejszy współczynnik pierwszy z x , wtedy Ecklund udowodnił ,że Rysunek 187 z jednoznacznym wyjątkiem Rysunek 188, zatem spełnia przypuszczenie Erdosa i Selfridge′a. Pryzpuszczali również ,że Rysunek 189, udowodnili ,że Rysunek 190. Definiujemy F(n) przez Rysunek 191. Czy F(n) > n jest dla n > n0? Czy F(n) - n → ∞ jeśli n → ∞? Czy Rysunek 192 będzie iloczynem kolejnych liczb pierwszych nieskończenie często? Dowód na to ,że nie może się to wydarzyć nieskończenie często dla (n 2) wydaje się beznadziejny; prawdopodobnie to nigdy nie może się zdarzyć dla Rysunek 193 jeśli 3 ≤ k ≤ n-3. Erdos przypuszczał ,że Rysunek 194 zawsze ma dzielnik z postaci n - i dla pewnego i < k. Obalone to zostało przez Schinzela i Erdosa. Czy jest prawdą ,że istnieje absolutna stała c taka że, Rysunek 195 zawsze ma dzielnik w (cn, n)? Czy można ławo sklasyfikować wszystkie rozwiązania z Rysunek 196, gdzie l < k1 < k2 i m1 + k1 ≤ m2? Być może istnieje tylko skończenie wiele rozwiązań. Ogólniej, jeśli k1 ? 2. Wtedy dla stałych a i b Rysunek 197 powinny mieć tylko skończoną liczbę rozwiązań. A co jeśli wymagane jest Rysunek 198 mają te same współczynniki pierwsze (powiedzmy przy k1 = k2)? Erdos i Strauss zadali następujące pytanie : Czy jest prawdą ,że dla każdego n istnieje k takie ,że Rysunek 199. Na przykład, dla n = 2 można wybrać k = 4: 3⋅4⋅5⋅6 | 7 ⋅ 8 ⋅ 9 ⋅ 10. Nie znamy żadnego przykładu dla n ≥ 10. Zpiszmy
(6) n! = (n+i1)(n+i2)…(n+ik), 0 < i1 < … < ik, gdzie k jest zmienne. Erdos i Selfridge wykazali ,że min ik = n + cn/log n, co jest poprawnym rzędem wielkści. Jednakże, dokładna wartość c nie jest znnan. Wiemy ,że największa wartość z k w (6) to Rysunek 200. Definiujemy t(n) przez Rysunek 201 .Erdso , Selfridge i Strauss wykazali ,że Rysunek 202Czy może t(n) = n/e - cn/log n ?. Podobne wyniki dla tego przypadku, że ai są potęgami pierwszymi uzyskami Alladi i Grinstead. Można wykazać ,że ostatnia wartość A(n) z t dla każdego n! może być zapisana jako n! = a1a2…at , gdzie ak ≤ n, 1 ≤ k ≤ t, spełnia A(n) = n - n/log n + o(n/log n).(Dowód może być party na "chciwej" dekompozycji n!, tzn. próbujemy użyć n tak często jak to możliwe, wtedy próbujemy n-1 tak często jak to możliwe, itd.) Nie wiadomo jak długo pozostaje to poprawne jeśli rozluźnimy ograniczenia na ak. Na przykład, załóżmy wymaganie ak ≤ n f(n). W szczególności, jaka jest sytuacja kiedy f(n) = n? W tym przypadku jest to prawdą ,że A(n) = n/2 - n/2 log n + o(n/log n)? . Inna kwestia : Piszemy n! = a1a2…at , a1 < … < at, minimalizujemy at - a1 (dla stałego t lub zmiennego t). Nie wiemy nawet ,że to nie może być jedynką nieskończenie często. Niech tk(n) oznacza najmniejszą liczbę całkowitą m dla której Rysunek 203 . Erdos przypuszczał a R.R Hal udowodnił ,że Rysunek 204 jeśli x → ∞. Prawdopodobnie współczynnik 1/x może być zastąpiony przez (log x)α/v ale nie zostało to udowodnione. Stare przypuszczenie Erdos zakłada ,że jeśli x + n ≤ y wtedy lcm(x+1,&hellip, x+n) ≠ lcm(y+1,&hellip.y+n). Wynika z twierdzenia Thue-Siegela, że dla stałego n , lcm(x+1, …x+n) = lcm(y+1,…y+n) ma tylko skończenie wiele rozwiązań w x i y. Czy można wykazać ,że dla każdego k istnieje n takie ,że Rysunek 205. Oczywiście, (n+1) zawsze dzieli się przez Rysunek 206 ale wystąpienia n podzielnego przez Rysunek 207 są dosyć rzadkie. Czy jest tylko skończenie wiele rozwiązań Rysunek 208, gdzie mi i nj są różne? .Stare przypuszczenie stanowi ,że jedynymi rozwiązaniami n! = x2 - 1 to n = 4,5,7. Jest to z pewności prawie prawda ale trudne obecnie. Erdos i Oblath udowodnili ,że n! = xk ± yk, (x,y) = 1 , k> 2 nie ma rozwiąza jeśli k ≠ 4. Pollack i Shapiro wykazali ,że nie ma również rozwiązań jeśli k = 4. Byłoby ciekawe móc mieć warunek (x,y) = 1 ale znane metody załamują się . Irytujące jest to ,że nie możemy nawet wykazać dla wszystkich k istnienia nk takie ,że w pierwszej dekompozycji nk! , nk! = 2α1 3α2 … pαrr, wszystkie αi, 1 ≤ I ≤ k, są parzyste. Łatwo wykazać ,że jeśli n! / a1 ! a2! jest liczbą całkowitą wtedy musimy mieć a1 + a2 < n + c log n, (chociaż najlepsza wartość c nie jest znana). Dla stałego k, definiujemy gk(n), będące największą liczbą całkowitą taka ,że dla pewnego ai z n + gk(n) = a1 + … + ak, n!/a1! … ak! jest liczbą całkowitą. Ponownie, łatwo jest wykazać ,że gk(n) < ck log n chociaż najlepsza wartość ck nie jest znana .Czy można wykazać ,że Rysunek 208. Faktycznie, jest to bez wątpienia prawą ,że gk(n) = ck lg x + o (log x) dla prawie wszystkich n < x ale nie udowodnimy tego. Jeśli pominiemy małe liczby pierwsze wtedy sytuacja prawdopodobnie się zmieni. Na przykład, czy jest prawdą ,że możemy znaleźć a1 + a2 > n + dr lg n przy dr → ∞ jeśli r → ∞ takie ,że n!2n⋅3n…pnr/a1!a2! jest liczbą całkowitą? Przypuszczenie: Dla dowolnego zbioru A z n dodatnimi liczbami całkowitymi Rysunek 209. Możemy zakładać ,bez straty na uogólnieniu ,że g.c.d{A:a∈ A} = 1. Przypuszczano ,że zbiory spełniające (7) [Rysunek 209] z równaniami to:
(i) {1,2,…,n}
(ii) {L/1,L/2,…L/n} gdzie L = lcm{1,2,…n}
(iii) {2,3,4,6}
Wiemy obecnie ,że dla (7) : a)Wszystkie a ∈ Asą squarefre. W tym przypadku (7) jest to równoważne wynikom zbioru teoretycznego Marica i Schonheima, że dla rodziny n różnych zbiorów A1, … An istnieje co najmniej n różnych różnic Ai - Aj .Dajkin i Lovasz udowodnili ,że liczba wartości branych przez nietrywialne funckje boolowskie nie jest mniejsza niż liczba zbiorów nad którymi jest wyliczana.
b)min a jest liczbą pierwszą
c)n jest liczbą pierwszą
d) n-1 jest liczbą pierwszą
e) Dla liczby pierwszej p > n, p | a dla pewengo a ∈ A
f) Dla liczby pierwszej p > n-1/2, p| a dla pewnego a ∈ A
g) n= p2 dla liczby pierwszej p
h) Pewne a ∈ A jest liczbą pierwszą gdzie a ≠ ?(a&primel + a″), a′ , a″ różnych elementów z A
i) Pewne a ∈ A jest liczbą pierwszą
j) min a jest p, p2 lub p3
k) n &le 92
Jednym z podejść udowodnienia (7) byłoby wykazanie ,że zbiór wartości {a/a,a′ : a, a′ ∈ A} ma co najmniej n elementów. Erdos i Szemeredi zanotowali ,że nie jest to prawdą przez zbudowanie przykładów, dla których zbiór wartości ma niej niż n1-e elementów. Jednakże, wykazali ,że musi mieć co najmniej ne′ elementów dla pewnego c′ > 0. P.Frankl pytał czy równanie Rysunek 210 ma tylko skończenie wiele rozwiązań. Wykazał ,że z teorii liczb pierwszych wynika ,że r > cn/log n. Burr i Erdos spytali wtedy czy ∑ ai ! = 2m ,a1 < a2 < … ma tylko skończenie wiele rozwiązań .Największym wydaje się być 27 = 2! + 3! + 5!. To ,że jest to największe rozwiązanie przez Frankla i niezależnie przez S.Lina. Faktycznie Lin wykazał coś nieoczekiwanego ,że największa potęga 2 która może podzielić sumę różnych silni zawierających 2 to 2254. Ogólnie, jeśli pα| | (a1! + a2! + … + ak! , a1 < … ak, jest granicą f(a1, p) dla α (gdzie pα || n oznacza ,że pα jest największa potęgą p podzielną przez n). Odpowiedź może zależeć od a1 i p. Czy istnieje p i nieskończony ciąg a1 < a2 < … takie że Rysunek 211 a αk → ∞ jeśli k → ∞. Lin również wykazał ,że jedyne rozwiązanie ∑ ai! = 3k to : 1! = 30 , 1! + 2! = 3, 1! + 2! + 3! = 32 , 1! + 2! + 4! = 33, 1! + 2! +3! + 6! = 36. Czy jest prawdą ,że równanie (p-1) ! + ap-1 = pk ma tylko skończoną liczbę rozwiązań, (gdzie p jest liczbą pierwszą). Bez wątpienia (p-1)! + ap-1 , a > 1,jest rzadką potęgą chocia 6! + 26 = 282 i mogą być inne rozwiązania. Czy jest prawdą, że 2n = ∑εi3i, εi = 0 lub 1, ma tylko skończenie wiele rozwiązań? 4 = 3 + 1 i 256 = 35 + 32 + 3 + 1 wydaje się być tymi jedynymi. Dla analogicznego pytania w którym tylko εi = 1 lub 2 jest dozowlone, czy 15 jest największą wartości n w tym przypadku. Na koniec wspomnijmy przypuszczenie D.J Newaman, które ilustruje naszą ignorancję w tej materii. Jeśli w(n) oznacza liczbę rozwiązań n = 2a + 3b + 2c ⋅ 3d, jest prawdą ,że w(n) jest ograniczone?

Problemy różne

W tej części omówimy kilka problemów, które są bardziej niekonwencjonalne niż wspominane wcześniej. Zaczniemy od pewnych niekonwencjonalnych problemów iteracji. Przy Φ(n) = Φ1(n) oznaczające zwykłą funkcję Φ Eulera, definiując Φk(n) będąca Φ(Φk-1(n)) dla k ≥ 2. Funkcja f(n) zdefiniowana prze f(n) = min {k:Φk(n) = 1} była pierwszą zbadaną przez Pillaia. Udownił ,że log n/ log 3 < f(n) < log n/ log 2 dla dużego n. H.N.Shapiro udowodnił ,że f(n) jest zasadniczo multiplikatywna. Stary problem Erdosa czy lub nie f(n) / log n a funckję rozkładu. Czy jest możliwe ,że f(n) / log n jest prawie zawsze stała? Co możemy powiedzieć o największym pierwszym czynniku P(Φk(n)) z Φk(n) np. gdzie k = log log n? .Przypuszczalnie możemy mieć k → ∞ tak wolne jak mamy dla dowolnego ε > 0 i prawie wszystlicj n, P(Φk(n)) = o(nε). Ciekawy problem zadał Finucane : Ile iteracji n → Φ(n) + 1 jest koniecznych przed osiągnięciem liczby pierwszej? Czy może zdarzyć się ,że nieskończenie wiele n osiąga tą samą liczbę pierwszą p? Jaka jest gęstoś n które osiąga p? Można zmodyfikować problem i rozważyć transformację n → σ(n) - 1. Czy jest prawdą ,że iteracje te zawsze osiągają liczbę pierwszą?Jeśli tak, kjak szybko? Oczywiście, nie udowodnimy tego tutaj, ale wydaje się ,że osiągną liczbę pierwszą szybko. Weintraub znalazł ,że dla n ≤ 106 , liczba pierwsza jest zawsze osiąganą w mniej niż 50 iteracjach. Jeśli σ1(n) = σ(n) i σk(n) = σ(σk-1(n)) dla k ≥ 2 to lim σk(n)1/k = ∞ ? Niech g(n) = n + Φ(n) = g1(n) i gk(n) = g(gk-1(n)) dla k ≥ 2. Dla jakieg n jest gk+r(n) = 2gk(n) dla wszystkich (dużych) k? Znane rozwiązanie gk+2(n) = 2gk(n) to n = 10 i n = 94. Selfridge i Weintraub znaleźli rozwiązania dla gk+9(n) = 9gk(n) (wszystkie znalezione n były parzyste) a Weintraub również odkrył gk+25(3114) = 729gk(3114), k ≥ 6. W latach pięćdziesiątych XX wieku, van Wijngaared postawił następujący proble : Zbiór σ1(n) = σ(n), σk(n) = σ(σk-1(n)), k ≥ 2. Czy jest prawdą ,że istnieje zasadniczo tylko jeden ciąg {σk(n)}, tzn. dla każdego m i n , σi(m) = σj(n) dla pewnych i i j. Selfridge poinformował ,ze dowody liczbowe sugerują ,że jest to niepoprawne. Ze względu na tą sytuację, Erdos rozpatrywał iteracje funkcji f(n) = n + v(n) gdzie v(n) oznacza liczbę czynników pierwszych z n. Jest tu prawdopodobne ,ze jest zasadniczo tylko jeden ciag {fk(n) }. Wynika to bezpośrednio ,jeśli można udowodnić ,że v(n) ma nieskończenie wiele "barier" tzn. liczb całkowitych n takich ,że dla wszystkich m < n, m+v(m) ≤ n. Można do tego podejść metodą sita ale obecnie te metody nie są dość mocen. Faktycznie, nawet wydaje się możliwym udowodnienie dużo słabszego założenia ,że dla ε > 0 istnieje nieskończenie wiele n takich ,że m + εv(m) ≤ n dla wszystkich m < n. C.Spiro niezależnie podniósł powiązaną kwestię. Jeśli iterujemy funkcję h(n) = n + d(n) , tzn. h1(n) = h(n), hk(n) = h(kk-1(n)) , k ≥ 2 (gdzie, jak zwykle, d(n) oznacza liczbę dzielników z n) wtedy czy istnieje zasadniczo tylko jeden ciąg {hk(n)}?. Odpowiedź wydaje się być na tak, chociaż tu istnienie barier jest dużo bardziej wątpliwe. Erdos i Selfridge przekonali się ,że jeśli istnieje bariera przekraczająca 24 wtedy musi być wyjątkowo duża. Spiro również przypuszczał ,że jeśli g(n) = n - d(n) = g1(n) , gk(n) = gk-1(n) + (-1)kd(gk-1(n)), k ≥2, wtedy {gk(n)} musi być cykliczne. Oczywiście, te kwestie mogą być postawione dla wielu innych funkcji poza d(n). Rozważmy k kolejnych wartości Φ(u+1), Φ(u+2), … Φ(u+k) gdzie k ≤ u + k < n. Jeśli uporządkujemy te k liczb według rozmiaru wtedy mamy dowód Erdosa, że dla k małych, wszystkie możliwe k! permutacji wystąpią i, faktycznie, każda permutacja ma gęstość. Ten sam wynik również osiągamy dla σ(m), d(m), v(m) i faktycznie dla wszystkich przyzwoitych funkcji addytywnych lub multiplikatywnych. Dla k < ci log log log n , występują wszystkie permutacje ale nie jest to prawda dla k > c2 log log log n. Wydaje się prawdopodobne, że przy odrobinie wysiłku można udowodnić ,że ma to miejsce dla k = c log log log n + o (log log log n) (lub być może nawet z błędnym wyrazem z O(1)). Jaka jest permutacja kiedy pojawi się pierwszy błąd? Vzy jest to Φ(u+1) > Φ(u+2) > … > Φ(u+k)? Czy jest prawdą ,że "naturalny" porządek ,tzn. porządek Φ(1), &Phi(2), … Φ(k) jest najbardziej prawdopodobne. Oznaczmy przez q(x) liczbę n ≤ x dla której Φ(m) = n jest rozwiązywalne. Faktem jest ,że q(x) = o(x) pierwszy udowodnił Pillai. Najostrzejsze wynik aktualnie znane to :
x/log x ⋅exp(c(log log log x)2) < q(x) < x /log x ⋅ exp(c√log log x
Czy q(2x)/q(x) → 2 Formuła asymptotyczna dla q(x) nie może istnieć. Niech q′(x) oznacza liczbę różnych liczb całkowitych w zbiorze {Φ(m) m ≤ x}. Oczywiście, q′ (x) ≤ q(x). Czy lim q(x)/q′(x) istnieje? Czy przekracza 1? Wykazao ,że gęstość liczb całkowitych nie w postaci σ(n) - n jest dodatnia. Jest bardzo irytujące ,że nie możemy wykazać, że σ(m) = Φ(n) ma nieskończenie wiele rozwiązań, szczególnie jeśli σ(m) = T i Φ(n) = T są prawdopodobnie rozwiązywalne kiedy T ma współczynniki pierwsze. Erdos i Sierpiński pytali czy istnieje nieskończenie wiele liczb całkowitych nie w postaci n - Φ(n). Jeśli przypuszczenie Goldbacha jest poprawne, wtedy każda nieparzysta liczba jest w tej postaci .A jaka jest sytuacja dla liczb parzystych? Przy d(n) oznaczającym liczbę dzielników z n , można wykazać ,że zbiór punktów granicznych z d((n+1)!)/d(n!) zawiera {1 + 1/k, k= 1,2,…}. To również należy do zbioru punktów granicznych wielkości d((n+2)!)/d(n!). Jednak nie możemy wykazać ,ze nie ma dodatkowych punktów granicznyuch. Łatwo wykazać ,że d((n+[√n])!)/d(n1) → ∞ i faktycznie, wyraz √n może być zastąpione przez n1/2-ε dla wystarczającego (małego) ε > 0. Bez wątpienia jest prawdą ,że d((n+[log n)α])!)/d(n!) → ∞ dla dużego α. Prawdopodobnie d((n+[log n])!)d(n!) jest gdziekolwiek gęste w (1, ∞) ale oczywiście nie możemy tego udowodnić. Generalnie, jest prawdą ,że jeśli t1 ≤ t2 ≤ … tn → ∞ i tn ≤ log n wtedy d((n+tn)!)/d(n!) jest gdziekolwiek gęste? Poniższe problemy zostały podniesione przez Hofstadtera:
(i)Defniujemy f(n) jak następuje : f(1) = f(2) = 1, f(n) = f(n-f(n-1)) + f(m-f(n-2)), n > 2. Czy f(n) pomija wiele liczb całkowitych? Jakie jest zachowanie genralnie?
(ii)Definiujemy ciąg A liczb całkowitych a1,a2, … zaczynając od a1 = 1, a2 = 2 , a następnie wybieramy ak będące najmniejszą liczbą całkowitą przekraczającą ak-1 , która może być przedstawiona jako suma co najmniej dwóch kolejnych wyrazów tego ciągu. Zatem, A zaczyna się 1,2,3,5,6,8,10,11, … Jakie jest asymptotyczne zachowanie A?
(iii)Definiujemy ciąg B liczb całkowitych b1, b2, … jak następuje. Zaczniemy od b1 = 1, b2 = 2. Generalnie, jeśli b1, … bn zdefiniowano, formują wszystkie możliwe wyrażenia bibj - 1 , i ≠ j i dołączone do tego ciągu. B zaczyna się od 2,3,4,9,14,17,26,27,33,4,… Czy jest prawdą ,że B ma gęstość asymptotyczną I?
Czy istnieje ciąg 1 ≤ d1 < d2 < … z gęstością taką ,że wszystkie iloczyny Rysunek 212 są różne? Niech a1 < a2 < … < ak ≤ x będzie ciągiem liczb całkowitych takich ,że iloczyn aiaj są wszystkie różne i niech f(x) oznacza maksymalną wartość z k dla których jest to możliwe. Erdos wykazał ,że istnieją stałe dodatnie c1, c2 takie ,że
(*)π(x) + c1x3/4/(log x)3/2 < f(x) < π(x) + c2x3/4/(log x)3/2
Jest pewne ,że istnieje c dla którego f(x) = π(x) + ( c+ o(1))x3/4/(log x)3/2 ale to nie zostało udowodnione. Zaobserwowano ,ze wiele problemów w teorii liczb może być sformułowanych dla liczb rzeczywistych zamiast tylko liczb całkowitych. Jednakowoż, te bardziej ogólne sformułowania rzadko bywają atakowane. Na przykład załóżmy ,że F(x) jest definiowane dla największej liczby całkowitej m dla której istnieje ciąg liczb rzeczywistych 1 ≤ α1 < α2 < … αm ≤ x, taki ,że dla wszystkich wyborów indeksów i,j,r,s : |αiαj - αrαs | ≥ 1. Podejrzewano ,że F(x) będzie również spełniało (*), Jednak, nikt nie był w stanie udowodnić ,że F(x) = o(x). Powód tego braku sukcesu jest teraz oczywisty z dowodu Alexandra, że F(x) > x/8e. Pomysłowa konstrukcja Alexandra używała dokładnej różnicy zbiorów. Czy można znaleźć cx/log x liczb całkowitych a1 < a2 < … < x takich ,że dla każdego m < x można zapisać m = ai + 2j dla pewnych i i j> ? Ruzsa wykazał ,że można znaleźć cx log log x/ log x takich liczb całkowitych. Czy jest prawdą ,że dla każdego n i d istnieje k dla którego Pn+1 + … + Pn+k ≡ 0 (mod d), gdzie Pr oznacza r-tą liczbę pierwszą? Można wykazać (zakładając przypuszczenie pierwszych k-krotek), że istniej zbiór A = {a1 < a2 < …} takie ,że lim sup A(x)/π(x) → 1 i dla nieskończenie wielu n, wszystkie liczby całkowite n - ai , 0 < ai < n, są liczbami pierwszymi. Czy to pozostaje prawdą jeśli założymy lim inf A(x)/π(x) > 0 ? Wiadomo ,że dla nieskończenie wielu n, n+2k jest zawsz złożone i ,że nieskończenie wiele nieparzystych liczb całkowitych nie jest w postaci p+2k. Wszystkie takie dowody jakie znamy z pracy ponieważ istnieje już skończony zbiór liczb pierwszych, który wymusza te liczby jako złożone. Czy jest możliwe udowodnienie twierdzeń następującego typu : Jeśli a1 < a2 < … dążą do nieskończoności dość szybko i nie pokrywa wszystkich klas resztkowych (mod p) dla dowolnej liczby pierwszej p wtedy dla pewnego n, n + ai jest liczbą pierwszą dla wszystkich i? W odwrotnym kierunku - jeśli ak nie zwiększa się zbyt szybko wtedy czy jest prawdą dla pewnego n n+ai przestawienie wszystkich (lub prawie wszystkich) dużych liczb zapewniających brak pokrycia stających na przeszkodzie kongruencji. Załóżmy ,że dla stałej liczby całkowitej n definiujemy ciąg a1, a2, &helllip;, at przez prowadzące a1 = 1 i dla k ≥ 2 , definiujemy ak będące najmniejszą liczbą całkowitą przekraczającą ak-1 dla której wszystkie czynniki pierwsze z n-ak > 0 są większe niż ak. Czy jest prawdą ,że dla wystarczająco dużego n, nie wszystkie jednostki n - ak mogą być liczbami pierwszymi? Poniższy problem postawił Ostman, Czy są dwa nieskończone zbiory A i B takie ,że suma A + B różnią się od zbioru liczb pierwszych tylko skończenie wielu elementami? Staruss zmodyfikował ten problem przez pytanie jak gęste może być A + B jeśli założymy ,że wszystkie elementy A+B są już parowo względnie pierwsze. Powiązany stary problem : Jeśli S ma dodatnią dolną gęstość, czy zawsze istnieją nieskończone zbiory A i B takie ,że A + B ⊆ S? Dla liczb całkowitych n i t, definiujemy g(n,t) przez : g(n,t) = max G (a1, … , an), gdzie 0 < a1 < … < an &;le; t , gcd(a1, … , an ) = 1 i G(a1, … , an) oznacza największą liczbę całkowitą, która nie może być wyrażona jako Rysunek 213 dla dowolnie wybranej liczby nieujemnej całkowitej xk. Funkcję G wprowadził Frobenius, i była ona temate dziesiątek prac różnych autorów .Ostatni wynik udowadniał G(a1,… , an) ≤ 2an-1 [ an n ] - an. Wynika z tego ,że g(n,t) < 2t2/n. Z drugiej strony nie jest trudno zbudować przykłady pokazujące ,że g(n,t) ≥ t2 / n-1 -St dla n ≥ 2. Wiemy ,że g(2,t) = (t-1)(t-2)-1 i g(3,t) = [(t-2)2 / 2] -1. Czy jest prawdą ,że g(n,t) ∼ t2 / n-1 ?. Selmer wykazał przy dodatkowym wymaganie a1 ≥ n ,że G(a1 , … ,an ≤ 2an-1 [at / n] - at. Za to wybór k dodatnich liczb całkowitych a1 < a2 < … < ak < n jest liczbą liczb całkowitych nie w postaci ∑ciai maksymalnej, gdzie ci pokrywa zakres wszystkich nieujemnych liczb całkowitych? Czy wybe ai = n - i jest optymalny do tego? Kwestia powiązana : Dla n ≠ pα , jaka jest największa liczba całkowita nie w postaci Rysunek 214 gdzie ci są nieujemnymi liczbami całkowitymi? Funkcja Λ(k,m) została wprowadzona przez D.A i Emmę Lehmerów. Dla wystarczająco dużej liczby pierwszej p, niech r = r(k,m,p) oznacza najmniejszą dodatnią liczbę całkowitą, taką ,że r,,r+1,…,r+m-1,są wszystkie k-tymi potęgami reszt modulo p. Definiujemy Λ(k,m) = lim sup r(k,m,p). Wiadomo ,że Rysunek 215. Czy jest prawdą,że Λ(k,2) < ∞ dla wszystkich k i &Lambda(k,3) < ∞ dla wszystkich nieparzystych k? Jeśli tak, jakie są szacunki dla tych wartości? Rozważmy ciąg I ≤ a1 < a2 < … < ak ≤ x i spójrzmy na iloczyny częściowe a1,a1a2, …, a1a2 … ak. Ile tych iloczynów (jako funkcji z x) może być kwadratami? Jest to trywialne o(x) ale prawdopodobnie może być więcej niż x1/2 Być może dla dowolnego ε > 0 może być w rzeczywistości więcej niż xt-s . Jak duże może być A = {a1 , … ,ak ⊆ [1,n] które są ≡ 1 (mod 3), pokazuje ,że k może być tak duże jak n/3. Jednak, k może w rzeczywistości być znacząco większe niż to. Jeśli formujemy graf G z dodatnich liczb całkowitych jako jego wierzchołki i brzegi {i,j}, jeśli i + j jest kwadratem , wtedy Erdos i D.Silverman pytali : Czy liczba chromatyczna z G jest równa ℵ0? A co jeśli i+j są wymagane jak k-ta potęga? Niech a1 < a2 < … będą nieskończonym ciągiem liczb całkowitych i oznaczonym przez A(x) liczba indeksów i dla których lcm(ai, ai+1) ≤ x. Wydaje się prawdopodobne ,że A(x) = O(x1/2) . Łatwo jest podać ciąg z lim sup A(x)/x1/2 = c. Jak duże może być lim inf A(x)/x1/2? Stary problem Erdosa prowadzi do największej wartości k dla której istnieje ciąg a1 < … < ak taki ,że lcm(ai, aj) ≤ x dla wszystkich i i j . Istnieje przypuszczenie ,że ta wartość maksymalna jest uzyskiwana przez wybranie ciągu składającego się z liczb całkowitych w [1,√n/2] razem z parzystymi liczbami całkowitymi w [√n/2, √2n]. Czy jest prawdą,że jeśli a1 < a2 < … jest ciągiem liczb całkowitych spełniających Rysunek 216 Niech m i n będą dodatnimi liczbami całkowitymi i rozważmy dwa zbiory {k(m-k) : 1 ≤ k ≤ m/2} i {l(n-l) : 1 ≤ l ≤ n/2}. Czy można oszacować liczbę liczb całkowitych wspólnych obu? Czy ta liczba jest nieograniczona? Czy z pewnością powinna być mniejsza niż (mn)ε dla każdego ε > 0 jeśli mn jest wystarczające duże. Niech a1 < a2 < … będzie nieskończonym ciągiem liczb całkowitych i niech dA(n) oznacza liczby ai które są dzielnikami n. Erdos i Sarkozy udowodnili Rysunek 217. Dowód jest zaskakująco trudny. Prawdopodobnie jest prawdą ,że Rysunek 218 dla każdego k ale nie można tego udowodnić. Niech x1,x2,… , xn będą różnymi liczbami całkowitymi. Przypuszczamy ,że całkowita liczba liczb całkowitych postaci xi + xj i xixj, 1 ≤ i < j ≤ n , jest większy niż n2-ε. Szeremedi udowodnił ,że liczba przekraczająca n1+ε dla pewnego c > 0. Erdos i Szeremedi zaobserwowali ,że wynika z twierdzenia Freimana, że ta liczba musi rosnąć szybciej niż cn dla dowolnego c; pierwsze n liczb całkowitych pokazuje ,że jest ograniczone powyżej przez n2/(log n)α dla pewnego α > 0. Faktycznie, udowodniono ,że jest ograniczone powyżej przez n2/elog n/ log log n. Być może jest to zasadniczo poprawny rząd wielkości. Ta sama kwestia może być postawiona dla wszystkich 2n Rysunek 219 i iloczynów Rysunek 220. W tym przypadku oczekujemy na więcej niż nε liczb całkowitych dla dowolnego c zapewniając n > n( c ). Czy jest prawdą ,że dla każdego c > 1 / 2, jeśli p jest wystarczająco dużą liczbą pierwszą wtedy przedział (u,u+pc) zawiera dwie liczby całkowite a i b spełniają ab ≡ 1 (mod p)? Twierdzenie Heilbronna gwarantuje to dla c wystarczająco bliskiego 1. Oznaczmy rzez εn gęstość liczb całkowitych mających dzielniki w (n,2n). Wykazano już ,że εn < (log x) a Tenenbaum wykazał ,że εn = (log n)-(1 + o(1)α gdzie α = 1 - (1+log log 2) / log 2 = 0,08607; jednakże aktualnie nie jest dostępna żadna formuła asymptotyczna da &epsilonn. Jeśli ε′n oznacza gęstość liczb całkowitych ma dokładnie jeden dzielnik w (n,2n), czy jest prawdą ,że ε′n / εn → 0? Czy istnieje β takie ,że dla każdego x > n istnieje m ∈ (x,x+(log n)β) który ma dzielnik w (n,2n)? Stare przypuszczenie Erdosa zakłada : Prawie wszystkie liczby całkowite n mają dwa dzielniki d1 i d2 przy d1 < d2 < 2d1. Silniejsza forma tego przypuszczenia jest następująca : Niech τ(n) oznacza liczbę dzielników z n i niech τ*(n) oznacza liczbę liczb całkowitych k dla których n ma dzielnik d z 2k ≤ d < 2k+1. Czy jest prawdą ,że dla wszystkich ε > 0, τ*(n) m ετ(n) dla prawie wszystkich n ? Obecnie nie ma dobrej nierówności znanej dla Rysunek 221. Problem Erdosa i Halla pokazuje ,że r(n) , liczba par dzielników d1 d2 z n spełniających d1 < d2 < 2d1, spełnione są dla każdego ε > 0, r(n) < ετ(n) dla prawie wszystkich n. Jak duże musi być y = y(ε,n) będzie takie ,że liczba liczb całkowitych w (x,x+y) mających dzielnik w (n,2n) jest mniejsza niż εy? Nich nk oznacza najmniejszą liczbę całkowita dla której Rysunek 222 nie ma pierwszego czynnika w (k,2k). Możemy udowodnić nk > k1+c nie bez wątpienia dużo więcej jest prawdziwe. Niech 1 = a1 < a2 < … < aΦ(n) = n - l będzie liczbami całkowitym względnie pierwszymi do n i niech F(n) oznacz max (ak+1 - ak). Erdos wykazał ,że prawie wszystkie n spełniają F(n) = (1 + o(1)) ⋅n log log n/ Φ(n). Oczywiście, F(n) może być dużo większe niż te dla jakiegoś. Jest prawdą ,że jeśli G(n)/F(n) → ∞ wtedy dla prawie wszystkich n każdy przedział długości G(n)) zawiera (1 + o(1))G(n) ⋅n/Φ(n)&adot;ai. Stare przypuszczenie Erdosa zakłada: Rysunek 223 dla absolutnej stałej c. Hooley udowodnił to dla słabszych wyników. Nie powinno być trudno udowodni Rysunek 224. Wiadomo ,że gęstość liczb całkowitych n z v(n) > log lg n to1 / 2 (gdzie v(n) oznacza liczbę różnych czynników pierwszych z n). Łatwo zauważyć z chińskiego twierdzenia o resztach ,że istnieje co najmniej t = (1 = o(1)) ⋅ log x/(log log x)2 kolejnych liczb całkowitych n + i , 1 ≤ i ≤ t, przy v(n+i) > log log x. Jednak nie mamy górnego ograniczenia d tego tzn. jak wiemy log x/(log log x)2 może być to (log x)k lub nawet więc. Pomerance obalił przypuszczenie Erdosa i Strausa przez wykazanie że dla nieskończenie wielu n i każdego i < n
(+) p2n > pn+ipn-i , gdzie pk oznacza k-ta liczbę pierwszą. Faktycznie, udowodnił to dla rosnącego ciągu an z an1/n → 1. Bez wątpienia gęstość n spełniającyx (+) jest zerem ale to nie zostało jeszcze udowodnione. Pomerance również przypuszczał ,że lim sup1/pn(pn2 - max pn+ipn-i ) > 0 ; udowodnił tylko
lim sup 1/(log n)2(pn2 - max pn+ipn-i) &gel 1
Jeśli f(n) oznacza min(pn+i + pn-i , czy jest prawdą ,że lim sup(f(n) - 2pn) = ∞ ?. Pomerance udowodnił ,że lim sup to co najmniej 2. Udowodnił też ,że jeśli funkcja ciągła A(x) zbioru A ⊆ Z+ spełnia A(x) = o(x) wtedy A(n) dzieli się przez n dla nieskończenie wielu n. W szczególności, implikuje to ,że π(n) dzieli się przez n nieskończenie często. Niech q1 < q2 < … będzie ciągiem liczb pierwszych spełniających qn+1 - qn ≥ qn - qn-1. Richter udowodnił ,że lim inf qn/ n2 > 0. Czy to prawda ,że granica jest rzeczywiście nieskończona? Niech sn oznacza najmniejszą liczbę pierwszą ≡ 1 (mod n) i niech mn oznacza najmniejszą liczbę całkowitą z Φ(mn) ≡ 0 (mod n). Czy jest prawdą ,że dla prawie wszystkich n , sn > mn ? Czy sn/mn → ∞ dla prawie wszystkich n ? Czy istnieje nieskończenie wiele liczb pierwszych p takich ,że p-1 jest jedynym n dla którego mn = p? Niech g(n,k) będzie najmniejszą liczbą pierwszą, która nie dzieli się przez Rysunek 225. Czy jest prawdą ,że nieskończenie często g(n, log n) > (2 + ε) log n? . Oznaczmy przez An najmniejszą wspólną wielokrotność liczb całkowitych {1,2,…,n} i niech pk oznacza k-tą liczbę pierwsza. Prawie z pewnością Apk+1-1 < pkApk musi posiadać dla każdego k ale dowód tego jest z pewnością poza naszymi możliwościami faktycznie, z dwóch powodów (co najmniej). Przede wszystkim, może być wiele kwadratów liczb pierwszych q2 przy pk < q2 < pk+1. Dowód ,że może nie być dwóch takich q wynika z pk+t - pk < pk1/2. Najmniejsze liczby pierwsze również powodują trudne problemy. Faktycznie, jeśli A′n oznacza najmniejszą wspólną wielokrotność liczb pα ≤ n przy α ≥ 2 ,wtedy A′n+[√n] / A′n < n wydaje się nam wysoce nieprawdopodobne. Przy danym u , niech v = f(u) będzie największą liczbą całkowitą taką ,że m ∈ (u,v) jest złożoną całkowicie z liczb pierwszych podzielnych przez uv. Oszacujmy f(u). Ta kwestia wynikła z prac Eggletona, Erdosa i Selfridgea. Definiujemy a0, a1,a2, … przez a0 = n, a1 = 1 , ak jest najmniejszą liczbą całkowitą przekraczająca ak-1 dla której (n-ak , n-a1) = 1, 1 ≤ i < k. Ustawiamy Rysunek 226, gdzie w ∑1,p(n-aj) > aj (gdzie p(t) oznacza najmniejszy czynnik pierwszy z t) Czy g(n) → ∞ Czy ∑1 → ∞ ? Ustawmy n + i = aibi , 1 ≤ i ≤ t, gdzie wszystkie współczynniki pierwsze z ai są mniejsze niż t a wszystkie współczynniki pierwsze z bi są większe lub równe t. Oznaczmy przez f(n,t) liczbę różnych ai. Czy istnieje &epsilon. > 0 takie ,że min f(n,t)/t > ε ?. Możemy tylko wykazać f(n,t) > ct/ log t. Przy p(n) oznaczającym najmniejszy współczynnik pierwszy z n, łatwo jest zobaczyć ,że Rysunek 227. Czy jest prawdą ,że ∑ p(n)/n > c′ , gdzie n pokrywa wszystkie liczby całkowite w [x,x+cx1/2(log x)2]? .Przy danym c, czy jest prawdą ,że dla n > n0( c ) istnieje zawsze liczba złożona m > n + c dla której m - p(m) < n? .Przy pk oznaczającym k-tą liczbę pierwszą, niech dk = pk+t - pk. Bez wątpienia dla r kolejnych di, wszystkie możliwe uporządkowane wystąpią (asymptotycznie z równym prawdopodobieństwem?) . Jednak nie możemy wykluczyć możliwości ,że z pewnego punktu na, dm > dm+1, d dm+1. Zbiór liczb całkowitych n dla których Φ(n+1) > Φ(n) , σ(n+1) > σ(n) i d(n+1) > d(n), wszystkie mają gęstość 1 / 2/ Jednak jest problem czy gęstość z {n :P (n+1) > P(n} to 1 / 2 (gdzie P(n) jest największym współczynnikiem pierwszym z n) wydaje się być trudnym. Niech a1 < a2 < … spełniają ak+1/ ak ≥ c > 1 dla wszystkich k. Wykazano ,że istnienie niewymierne α takie ,że {akα - [akα] : k = 1,2,…} nie jest gdziekolwiek gęste. Faktycznie każdy przedział zawierający c (kardynalność continuum) takich α . Twierdzenie Erdosa i Taylora stanowi ,że zbiór α dla którego {akα - [akα] : k = 1,2,…} nie jest jednoznacznie rozłożone ma wymiar Hausdorffa 1. Dla liczby rzeczywistej x, niech ||x|| oznacza odległość od x do najbliższej liczby całkowitej. Dla punktów P i Q na płaszczyźnie, oznaczmy odległość między P a Q przez d(P,Q). W końcu dla stałego X > 0 i δ ∈(0,1/2), niech N (X,δ) oznacza maksymalną liczbę punktów P1,P2. … ,Pn , które mogą być wybrane w okręgu o promieniu X tak, że ||d(Pi, Pj)|| ≥ δ dla 1 ≤ j < j ≤ n. Erdos przypuszczał ,że dla dowolnego δ ∈ (0, 1 / 2), N(X,δ) = o(X) i , z drugiej strony ,że istnieje δ0 > 0, takie ,że lim N(X,δ0) = ∞
Pierwsze przypuszczenie udowodnił Sarkozy, który wykazał ,że N(X,δ) ≤ 4 x 104/ δ3 ⋅ X / log log X, dla wystarczająco dużego X. Drugie przypuszczenie udowodnił Graham, wykazując ,że N(X,1/10) > 1/10 ⋅ log X. Zostało to poprawione przez Sarkozy′ego, który wykazał ,że dla absolutnej stałej c , N(X,1/10) > Xc. Faktycznie Sarkozy wykazał ,że dla wszystkich ε > 0 ,jeśli δ ≤ δ(ε) wtedy N(X,δ) > X1/2 - ε) dla wystarczająco dużego X. Jest jeszcze szeroka luka między górną a dolną granicą. Czy jest prawdą ,że dla dowolnego ε > 0, N(X,δ) < X1/2+ε dla wystarczająco dużego X? Niestety, nie wiemy nawet jak wykazać N(X,δ) < X1-ε dla dodatniego ε . Problem sita : czy można podzielić liczby pierwsze mniejsze niż n na dwie klasy {qi}, {q′i} takie ,że dla odpowiednich wyborów ai i ai′ każda liczba całkowita x mniejsza niż n spełnia x ≡ ai mod qi i x ≡ai′ mod q′i? Dla danego n , niech 1 < d1 < d2 < … będą dzielnika n i rozważmy sumę d1, d1 + d2 , d1 + < d2 + d3, … Ile nowych sum uzyskamy z n, tzn. sum nie występujących dla m < n ? Kiedy N wystąpi po raz pierwszy jako suma? W szczególności, jeśli f(N) oznacza najmniejszą wartość z n dla której występuje N, czy jest prawdą ,że f(N) = o(N)? (lub być może dla prawie wszystkich N?) Załóżmy ,że n = d1 + … + dk gdzie di są różnymi właściwymi dzielnikami z n ale nie jest to prawda dla właściwych dzielników z n . Czy suma odwrotności wszystkich takich n musi być zbieżna? Podobnie , ta sama kwestia może być postawiona dla tych n , które nie maj różnych sum zbiorów dzielników. Liczba całkowita n może być nazwana dziwną jeśli σ(n) / n ≥ 2 i n ≠ d1 + … + dk gdzie di są różnymi właściwymi dzielnikami z n. Czy istnieją dowolne nieparzyste liczby dziwne? Czy jest nieskończenie wiele podstawowych liczb dziwnych, tzn. takich ,że żaden właściwy dzielnik n jest dziwne? Poniższe dwa problemy przedstawił Ulam. Poczynając od danego zbioru liczb pierwszych Q = {q1, … qm} , formujemy zbiór Q′ przez dołączenie do Q wszystkich liczb pierwszych formowanych przez dodanie dowolnych trzech różnych elementów Q. Teraz powtarzamy tą operację na Q′ itd. Czy rozmiary wygenerowanych zbiorów stają się nieograniczone przy odpowiednim wyborze Q? A co z Q = {3,5,7,11}?Zaczynając od zbioru liczb pierwszych Q = { q1,…qm formujemy ciąg Q* = (q1,q2, …) przez ustawienie qk+1 być najmniejszą liczbą pierwszą postaci qn + qi - 1, 1 ≤ < n dla n > m. Na przykład ,jeśli Q = {3,5}, Q* = {3,4,5,7,11,13,17, …}. Czy jest wybór W taki ,że Q* jest nieskończone? A co z A = {3,5}? >Segal sformułował następujący problem. Czy istnieje permutacja a1,a2 … dodatnich liczb całkowitych, taka ,że ak + ak+1 jest zawsze pierwsza? W szczególności C.Watts pytał czy "chciwy" algortym" zawsze generuje taką permutację. Innymi słowy, czy definiując g1 = 1, gn+1 = min { x:gn + x jest liczbą pierwszą a x ≠ gi i ≤ n}, wtedy wszystkie liczby dodatnie całkowite występują jako gk? Czy wszystkie liczby pierwsze występują jako sum>? Odlyzko skonstruował permutację , która rozlicza pierwszy problem, tzn, taki ,że ak + ak+1 jest zawsze liczbą pierwszą. Chciwy algorytm również wydaje się trudny dla podjęcia decyzji. Wykazano ,że wszystkie liczby całkowite do 9990 występują jako gk. Segal równie pytał czy może być to zrobione dla zbioru {1,2,…,n}. Wydaje się prawdopodobne ,że może, ale aktualnie nie wiemy. Formjemy nieskończony ciąg b1, b2 , … przez ustawienie b1 = 1 i definiujemy bn+1 będące najmniejszą liczba całkowitą , która nie jest przedziałem sumy b1 , … bn. Zatem ciąg zaczyna się : 1,2,4,5,8,10,14,15,16,21,22,23,25,26,28, …. Jak ten ciąg wzrasta? Generalnie załóżmy a1 < a2 < … jest ciągiem takim ,że żadne an nie jest sumą kolejnych ai. Czy gęstość ai będzie zerowa? A co z dolną gęstością? Czy można zobaczyć więcej?Stare pytanie Grahama brzmi czy dla dowolnego zbioru {a1, … ,at} niezerowych reszt modulo danej liczby pierwszej p, istnieje zawsze przestawienie (ai1, ai2, … ait) takie ,że wszystkie części sumy ∑mk=1 aik są różne modulo p?. Powiązany wynik Erdosa i Szemerediego stanowi ,że jeśli a1, a2, … ap są p niezerowymi resztami modulo liczb pierwszych takie ,że istnieje tylko jedna wartość k dla której ai1 + ai2 + … + aik ≡ 0 (mod p) przy i1 < i2 < … < ik wtedy ai zakłada co najwyżej dwie różne wartości modulo p. Dowód jest nieoczekiwanie skomplikowany. Czy jest prawdą ,że jeśli a1, … ak są różnymi resztami modulo p wtedy para sum ai + aj , i ≠ j przedstawia co najmneje 2k-3 różnych klas resztkowych modulo p (lub wszystkie Zp , jeśli p ≤ 2k-3)? To stare pytanie Erdosa i Heilbronna pozostaje otwarte. White udowodnił ,że jeśli a1,…,ak są różnymi elementami z grupy a (nie koniecznie abelowej) i żaden podzbiór sum ai jest 0 (tożsamość grupy) wtedy te podzbiory sum, przedstawiają co najmniej 2k-1 różnych elementów grupy. Co więcej, ta granica jest osiągana tylko jeśli k ≤ 3 lub ai generuje grupę dwuścianu. Wiadomo było ,że jeśli a1, … an są resztami modulo n wtedy pewna suma ai1 + … + aim , i1 < … im jest 0 (mod n), To jest uogólnieniem skończonych półgrup przez Gillama, Halla i Wiliamsa, gdzie teraz pewna suma jest wymagana aby być indemoptencją z półgrupy. Selfridge przypuszczał ,że maksymalny zbiór A różnych modułów reszt p mających taką właściwość ,że żaden podzbiór z A sum do 0 (mod p) jest podany przez {-2,1,3,4,5,…,t} dla właściwego t. Dla nie pierwszych p ta sytuacja wydaje się być mniej jasna .Devit i Lam określili maksymalna wartość a(m) dla wszystkich wartości modulus m do 50, np. a(42) = 9, a(43) = 8 , a(44) = 9. Pytali : Czy a(m) prawie zawsze jest niemalejące? Czy a(m) = [(-1 + √8m+9/2] nieskończenie częst>? Dla którego m istnieje zbiór A &sube. Zm przy |A| = a(m) taki ,że żaden element z a nie jest względnie pierwszy do m? .Załóżmy f:Z → Z jest wielomianem stopnia co najmniej 2 i niech S = {f(1),f(2), … } Czy jest prawdą ,że może nigdy nie istnieć bezpośrednia suma dekompozycji Z = S + T, tzn. dla żadnego zbioru T może każde z ∈ Z ma jednoznaczną reprezentachję s + t , s ∈ S , t ∈ T? .Rozważmy ,zbiór Sp różnych reszt w postaci k! (mod p) , 1 ≤ k < p , gdzie p jest liczbą pierwszą. Czy jest prawdą ,że |Sp| / p = 1 - 1/3 + o(1)?. Łatwo zauważyć ,że 2n &nee; 1 (mod n) dla n > 1. Stare przypuszczenie Grahama zakłada ,że dla wszystkich k ≠ 1, istnieje nieskończenie wiele n takich ,że 2n ≡ k (mod n). Wiemy ,że to prawda jeśli k = 2i , i ≥ l i k = -1 D.H. i Emma Lehmerowie znaleźli rozwiązanie przy n < 5,109 dla wszystkich k ≠ 1 przy |k| ≤ 100. Poniższe przypuszczenie określił D.J.Newman. Niech x1,x2,x3, … będą liczbami rzeczywistymi w bliskim przedziale [0,1]. Czy jest prawdą ,że istnieje nieskończenie wiele m i n takich ,że |xm+n - xm| ≤ 1 / n√5 ?. Wiemy ,że to jest fałszywe. Niespodzianką jest ,że poniższy problem oferuje trudności. Dla danych liczb całkowitych a1, … ar, b1,… , br niech T będzie transformacją która zastępuje liczbę całkowitą x przez r liczb całkowitych aix + bi, 1 ≤ i ≤ r. Wykazał ,że jeśli ∑ 1/ai > 1 wtedy dla pewnej granicy B, nie jest możliwe zacząć od 1 i stosować T powtarzalnie dopóki wszystkie liczby całkowite są różne i większe niż B. W końcu, wspomnijmy pewien niekonwencjonalny problem. Definiujemy ciąg liczb całkowitych (a1,a2, …) przy a1 = 1 i an+1= [√2 (an + 1 / 2)], n ≥ 1. Zatem ciąg zaczyna się : 1,2,3,4,6,9,13,19,27,38, …. Wykazano ,że jeśli dn oznacza różnicę a2n+1 - 2a2n-1 , n ≥ 1, wtedy dn jest tylko n-tą cyfrą w binarnym rozwinięciu √2 = 1,01101000…. Wydaje się jasne ,że muszą być podobne wyniki dla √ i inne liczby algebraiczne ale nie mamy pomysłu czy są.