Twierdzenie Erdősa-Szemerédiego

Erdősa -Szemerédiego w kombinatoryce arytmetycznej stwierdza, że ​​dla każdego $displaystyle A\cdot A}$ zbioru liczb całkowitych $,$ co najmniej jeden z , $ZA$ parami lub , zbiór iloczynów parami tworzy znacznie większy zbiór. Dokładniej, twierdzenie Erdősa-Szemerédiego stwierdza, że ​​istnieją stałe dodatnie c i takie, że dla dowolnego niepustego zbioru $N}}$$Displaystyle A \ podzbiór \ mathbb$

${\ Displaystyle \ max (| A + A |, | A \ cdot A |) \ geq c | A | ^ {1+ \ varepsilon}}$ .

Udowodnili to Paul Erdős i Endre Szemerédi w 1983 roku. Notacja ${\ Displaystyle | A |}$ oznacza liczność zbioru ${\ displaystyle A}$ .

Zbiór sum parami to ${\ Displaystyle A + A = \ {a + b: a, b \ w A \}}$ i nazywa się zestawem sum ${\ Displaystyle A}$ .

Zbiór iloczynów parami to ${\ Displaystyle A \ cdot A = \ {ab: a, b \ w A \}}$ i jest nazywany zestawem iloczynów ${ \displaystyle A}$ .

Twierdzenie jest wersją maksymy, że struktura addytywna i struktura multiplikatywna nie mogą współistnieć. Można to również postrzegać jako stwierdzenie, że prosta rzeczywista nie zawiera żadnego zbioru przypominającego skończony podpierścień lub skończone podciało; jest to pierwszy przykład tego, co jest obecnie znane jako zjawisko iloczynu sumy , o którym wiadomo, że występuje w wielu różnych pierścieniach i polach, w tym w polach skończonych.

Hipoteza o sumie iloczynu

Hipoteza iloczynu sumy nieformalnie mówi, że jeden ze zbioru sum lub zbioru iloczynów dowolnego zbioru musi być prawie tak duży, jak to tylko możliwe. Pierwotnie Erdős i Szemerédi przypuszczali, że dotyczy to liczb całkowitych, ale uważa się, że dotyczy liczb rzeczywistych.

${\ Displaystyle \ max (| A + A |, | AA |) \ geq | A | ^ {2-o (1)}.}$ : dla $_$ ma

Parametr asymptotyczny w notacji o(1) to |A|.

Przykłady

Jeśli ${\ Displaystyle A = \ {1,2,3, \ kropki, n \}}$ to ${\ Displaystyle | A + A | = 2 | A | + 1 = O (| A |)}$ przy użyciu notacji asymptotycznej , z ${\ displaystyle | A |}$ parametr asymptotyczny. Nieformalnie mówi to $, że$ sum nie rośnie. Z drugiej strony zbiór $postaci$ spełnia granicę ${\ Displaystyle | A \ cdot A | \ geq | A | ^ {2- \ epsilon}}$ dla wszystkich ${\ Displaystyle \ epsilon > 0}$ . Jest to związane z tabliczki mnożenia Erdősa . Najlepsza dolna granica na ${\ Displaystyle | A \ cdot A |}$ za ten zestaw jest zasługą Kevina Forda .

Ten przykład jest przykładem problemu sumy produktów György Elekesa i Imre Z. Ruzsy w wersji Few Sums, Many Products . Konsekwencją ich wyniku jest to, że każdy zbiór z niewielkim podwojeniem addytywnym, na przykład postęp arytmetyczny , ma dolną granicę zbioru iloczynów ${\ Displaystyle | AA | = \ Omega (| A | ^ {2} \ log ^ {- 1} (| A |))}$ . Xu i Zhou udowodnili, że ${\ Displaystyle | AA | = \ Omega (| A | ^ {2} \ log ^ {1-2 \ log 2-o (1)} (| A |))}$ dla dowolnego gęstego podzbioru $liczbach$ całkowitych, który jest ostry aż do ${\ Displaystyle O (1) }$ czynnik w wykładniku.

Odwrotnie, zbiór spełnia ${\ Displaystyle B = \ {2,4,8, \ kropki, 2 ^ {n} \}$ } ${\ Displaystyle | B \ cdot B | = 2 | B | -1}$ , ale ma wiele sum: ${\ Displaystyle | B + B | = {\ binom {| B|+1} {2}}}$ . Ta granica wynika z rozważenia binarnej reprezentacji liczby. Zbiór $geometrycznego$ przykładem postępu .

W przypadku losowego zestawu $liczb$ zarówno zestaw iloczynu, jak i zestaw sum mają liczność ${\ Displaystyle {\ binom {n + 1} {2}}$ ; czyli z dużym prawdopodobieństwem zbiór sumy nie generuje powtarzających się elementów i to samo dotyczy zbioru produktów.

Ostrość przypuszczenia

Erdős i Szemerédi podają przykład wystarczająco gładkiego zbioru liczb całkowitych z ograniczeniem: ${\ displaystyle A}$

${\ Displaystyle \ max \ {| A + A |, | A \ cdot A |\} \ równoważnik | A | ^ {2} e ^ {- {\ Frac {c \ log | A |} {\ log \ log |A|}}}}$ .

To pokazuje, że warunek o(1) w przypuszczeniu jest konieczny.

Ekstremalne przypadki

Często badane są skrajne przypadki hipotezy:

• kilka sum, wiele produktów (FSMP) : jeśli ${\ Displaystyle | A + A | \ ll | A |}$ , a następnie ${\ Displaystyle | AA | \ geq | A | ^ {2-o (1)}}$
• mało produktów, wiele sum (FPMS) : jeśli ${\ Displaystyle | AA | \ ll | A |}$ , a następnie ${\ Displaystyle | A + A | \ geq | A | ^ {2-o (1)}}$ .

Historia i aktualne wyniki

Poniższa tabela podsumowuje postępy w rozwiązaniu problemu sumy iloczynów w liczbach rzeczywistych. Wykładniki 1/4 György Elekesa i 1/3 Józsefa Solymosiego są uważane za kamienie milowe w cytowanej literaturze. Wszystkie ulepszenia po $i reprezentują udoskonalenia$ roku mają postać Konyagina i

Wykładnik $\ delta}$${\ Displaystyle \ max (| A + A |, | AA |) \ geq | A | ^ {1 + \ delta -o (1)}}$ gdzie dla ${\ Displaystyle A \subset \mathbb {R} }$

Rok	Wykładnik potęgowy	Autorski)	Uwagi
1983	niewyraźne ${\ Displaystyle \ delta > 0}$	Erdős i Szemerédi	Tylko dla $Displaystyle 1$$delta}$ \ zamiast ${\ Displaystyle 1+ \ delta - o(1)}$ .
1997	${\ Displaystyle {\ Frac {1} {31}}}$	Nathanson	Tylko dla $Displaystyle 1$$delta}$ \ zamiast ${\ Displaystyle 1+ \ delta - o(1)}$ .
1998	${\ Displaystyle {\ Frac {1} {15}}}$	Bród	Tylko dla $Displaystyle 1$$delta}$ \ zamiast ${\ Displaystyle 1+ \ delta - o(1)}$
1997	${\ Displaystyle {\ Frac {1} {4}}}$	Elekes	postaci ${\ Displaystyle 1 + \ delta -o (1)}$ . Obowiązuje również nad ${\ Displaystyle \ mathbb {C}.}$
2005	${\ Displaystyle {\ Frac {3} {11}}}$	Solymosi	Obowiązuje również przez do ${\ displaystyle \ mathbb {C}$
2009	${\ Displaystyle {\ Frac {1} {3}}}$	Solymosi
2015	${\ Displaystyle {\ Frac {1} {3}} + {\ Frac {1} {20598}} = 0,333381 \ kropki}$	Konyagin i Shkredow
2016	${\ Displaystyle {\ Frac {1} {3}} + {\ Frac {5} {9813}} = 0,333842 \ kropki}$	Konyagin i Shkredow
2016	${\ Displaystyle {\ Frac {1} {3}} + {\ Frac {1} {1509}} = 0,333996 \ kropki}$	Rudnev, Shkredov i Stevens
2019	${\ Displaystyle {\ Frac {1} {3}} + {\ Frac {5} {5277}} = 0,334280 \ kropki}$	Shakan
2020	${\ Displaystyle {\ Frac {1} {3}} + {\ Frac {2} {1167}} = 0,335047 \ kropki}$	Rudniewa i Stevensa	Aktualny zapis

Liczby zespolone

$się$ tylko twierdzenie Szemerédi-Trottera rozciągają na liczby zespolone, ponieważ twierdzenie Szemerédi-Trottera jest nadrzędne przez twierdzenie Tótha. Konyagin i Rudnev dopasowali wykładnik 4/3 na liczbach zespolonych. $nie$ postaci zostały dopasowane na

Nad skończonymi polami

Problem iloczynu sumy jest szczególnie dobrze zbadany w przypadku ciał skończonych . Motywowany hipotezą Kakeyi o skończonym polu $Displaystyle$ Wolff przypuszczał , $A \ subseteq \ mathbb {F} _ {p}}$ dla każdego podzbioru , gdzie jest (dużą) liczbą pierwszą, to $_$ dla $_ \displaystyle\epsilon >0}$ . Przypuszczenie to zostało również sformułowane w latach 90. przez Wigdersona , motywowanego ekstraktorami losowości .

Zauważ, że problem z iloczynem sumy nie może być bezwarunkowo spełniony w polach skończonych z powodu następującego przykładu:

Przykład: Niech będzie polem skończonym i weźmy $ZA$$F}}$ . Następnie, ponieważ $dodawaniu$ i mnożeniu, $Displaystyle A + A = A \ cdot A = \ mathbb {F}}$ i tak ${\ Displaystyle | A + A | = | A \ cdot A | = | \ mathbb {F} |}$ . Ten patologiczny przykład rozciąga się na przyjęcie dowolnego $podrzędnego$ danego pola.

Jakościowo problem sumy iloczynu został rozwiązany na polach skończonych:

$($${\ Displaystyle p ^ {\ delta }<| A | <p ^ {1-\ delta}}$ )): Niech ${\ displaystyle p}$ będzie liczbą pierwszą i niech za dla pewnego ${\ Displaystyle 0 <\ delta <1}$ . Wtedy mamy ${\ Displaystyle \ max (| A + A |, | A \ cdot A |) \ geq c _ {\ delta} | A | ^ {1+ \ epsilon}} dla$ niektórych ${ \displaystyle \epsilon =\epsilon (\delta)>0}$ .

Bourgain , Katz i Tao rozszerzyli to twierdzenie na dowolne pola. Nieformalnie następujące twierdzenie mówi, że jeśli wystarczająco duży zbiór nie rośnie ani w wyniku dodawania, ani mnożenia, to jest on w większości zawarty w rozszerzeniu podobszaru.

$Katz , Tao ($ )): Niech będzie $że$ skończonego ciała tak, ${\ Displaystyle | A |> | \ mathbb {F} | ^ {\ delta}}$ dla pewnego ${\ Displaystyle 0 <\ delta <1}$ i załóżmy, że ${\ Displaystyle | A + A |, | A \ cdot A | \ równoważnik K | A |}$ . $_$$zestaw$ podrzędne | i $_$ _ ${\ Displaystyle X \ podzbiór \ mathbb {F}}$ z $\ Displaystyle | X | \ równoważnik K ^ {C _ {\ delta}}}$ tak, że ${\ Displaystyle A \ subseteq xG \ puchar X}$ .

Sugerują, że stała $\ displaystyle C _ {\ delta}$ być niezależna od $}$ .

$.$ sumy iloczynu pola skończonego $zwykle$ dwie kategorie: gdy jest w odniesieniu do charakterystyki z i kiedy $jest$ duży w odniesieniu do charakterystyki $\ displaystyle A \ podzbiór \ mathbb$ { $F}$ . Wynika to z faktu, że w każdym ustawieniu stosowane są różne rodzaje technik.

Małe zestawy

W tym reżimie $niech$$.$ polem Zauważ, że pole nie zawsze jest skończone. Gdy tak jest, a charakterystyka $.$ zero, to $-$ zostaje pominięte

Wykładnik $\ delta}$$_$ gdzie _ $_ \subset \mathbb {F} }$

Rok	Wykładnik potęgowy	${\ displaystyle p}$ -ograniczenie: ${\ Displaystyle | A | < p ^ {c}}$	Autorski)	Uwagi
2004	nieokreślony ilościowo	${\ displaystyle c <1}$	Bourgain, Katz, Tao	Tylko dla $.$
2007	${\ Displaystyle {\ Frac {1} {14}}}$	$7/13$	Garajew	Tylko dla $.$ Ograniczenie p obejmuje współczynnik ${\ Displaystyle \ log (| A |)}$
2008	${\ Displaystyle {\ Frac {1} {13}}}$	${\ displaystyle c = 1/2}$	Kaz, Shen	Tylko dla $.$
2009	${\ Displaystyle {\ Frac {1} {12}}}$	$12/23$	Burgain, Garajew	Tylko dla $.$ o(1) usunięte przez Li.
2012	${\ Displaystyle {\ Frac {1} {11}}}$	${\ displaystyle c = 1/2}$	Rudniew	Tylko dla $.$
2016	${\ Displaystyle {\ Frac {1} {5}}}$	$\ displaystyle c = 5/8$	Roche-Newton, Rudnev, Shkredov
2016	${\ Displaystyle {\ Frac {1} {9}}}$	$18/35$	Rudnev, Shkredov, Shakan	Wynik ten jest najlepszym z trzech jednoczesnych wyników.
2021	${\ Displaystyle {\ Frac {1} {4}}}$	${\ displaystyle c = 1/2}$	Mohammadi, Stevens	Aktualny zapis. Rozciąga się na zbiory różnic i zbiory proporcji.

W polach o rzędzie innym niż pierwsze ograniczenie -ograniczenie $na$ można zastąpić założeniem, że $F}}$$\$ podzbiór \ mathbb duże przecięcie z dowolnym podpolem. Najlepsza praca w tym kierunku wynika z osiągnięcia przez Li i Roche-Newtona $zapisie$ powyższej

Duże zestawy

Kiedy dla $liczby$ pierwszej, problem sumy iloczynu uważa się za rozwiązany z powodu następującego wyniku Garaeva: ${\ displaystyle \ mathbb {F} = \ mathbb {F} _ {p}$

Twierdzenie (Garaev (2007)): ​​Niech ZA $\ Displaystyle A \ podzbiór \ mathbb {F} _ {p}}$ . Wtedy ${\ Displaystyle \ max \ {| A + A |, | A \ cdot A |\} \ gg \ min \ {p ^ {1/2} | A | ^ {$ .

Jest to optymalne w zakresie ${\ Displaystyle | A | \ geq p ^ {2/3}}$ .

Wynik ten został rozszerzony na skończone pola porządku innego niż pierwszy przez Vinha w 2011 roku.

Warianty i uogólnienia

Inne kombinacje operatorów

Bourgain i Chang udowodnili bezwarunkowy wzrost dla zbiorów ${\ displaystyle A \ subseteq \ mathbb {Z}}$ o ile weźmie się pod uwagę wystarczającą liczbę sum lub produktów: ZA

Twierdzenie (Bourgain, Chang (2003) ): Niech ${\ Displaystyle A \ subseteq \ mathbb {Z}}$ i ${\ Displaystyle b \ in \ mathbb {N}}$ . Wtedy istnieje ${\ Displaystyle k \ in \ mathbb {N}},$ więc ${\ Displaystyle \ max \ {| kA |, | A ^ {(k)} |\} = \ max \ {| A + A + \ kropki A |, | A \ cdot A \ cdot \ kropki A |\} \geq |A|^{b}}$ .

W wielu pracach dodawanie i mnożenie są łączone w jednym wyrażeniu. Zgodnie z mottem dodawanie i mnożenie nie może współistnieć, oczekuje się, że każda nietrywialna kombinacja dodawania i mnożenia zbioru powinna gwarantować wzrost. Zauważ, że w skończonych ustawieniach lub w polach z nietrywialnymi podpolami takie stwierdzenie wymaga dalszych ograniczeń.

Interesujące zestawy obejmują (wyniki dla ${\ Displaystyle A \ podzbiór \ mathbb {R}}$ ):

• ${\ Displaystyle AA + A}$ - Stevens i Warren pokazują, że ${\ Displaystyle | AA + A | \ gg | A | ^ {{\ Frac {3} {2}} + {\ Frac {3} {170}} -o (1 )}}$
• ${\ Displaystyle A (A + A)}$ - Murphy, Roche-Newton i Shkredov pokazują, że ${\ Displaystyle | A (A + A) | \ gg | A | ^ {{\ Frac {3} {2}} + {\ Frac {5} {242}} - o(1)}}$
• ${\ Displaystyle A (A + 1)}$ - Stevens i Warren pokazują, że ${\ Displaystyle | A (A + 1) | \ gg | A | ^ {{\ Frac {49} {38}} -o (1)}}$
• ${\ Displaystyle AA + AA}$ - Stevens i Rudnev pokazują, że ${\ Displaystyle | AA + AA | \ gg | A | ^ {{\ Frac {127} {80}} -o (1)}}$

Zobacz też

• Zestaw bez sumy

Linki zewnętrzne

• Hartnett, Kevin (6 lutego 2019). „Jak dziwna siatka ujawnia ukryte połączenia między prostymi liczbami” . Magazyn Quanta .