Teorema lui Roth

Teorema lui Roth este un rezultat al combinatoriei aditive , un caz special al teoremei lui Szemeredi pentru progresii de lungime 3; afirmă prezența progresiilor aritmetice în orice mulțimi suficient de dense. $(a,a+d,a+2d),\d\not =0$

Formularea exactă este: pentru orice , orice mulțime care are o densitate asimptotică conține o progresie aritmetică de lungime 3. $\delta \in (0;1)$ $A\subset {\mathbb {N} }$ $d(A)>\delta$

Formulări similare care utilizează densitățile asimptotice superioare și inferioare sunt echivalente cu [1] .

Formularea pentru mulțimi finite este, de asemenea, echivalentă cu cea inițială: pentru orice există astfel încât dacă , și , atunci conține o progresie aritmetică de lungime 3. Majoritatea covârșitoare a demonstrațiilor demonstrează formularea pentru mulțimi finite. $\delta \in (0;1)$ $N_{0}=N_{0}(\delta )$ $N>N_{0)$ $A\subset \left\lbrace {1,2,\dots ,N}\right\rbrace$ $|A|>\delta N$ $A$

Istoricul scorurilor îmbunătățite

Dimensiunea maximă a subsetului $\{1,\dots ,N\}$ fără progresii de lungime 3
Anul publicării	Dimensiune (până la o constantă)	Autorii)
1953	${\frac {N}{\log \log N}}$	gura [2]
1987	${\frac {N}{(\log N)^{c}}},\c>0$	Heath-Brown [3] [4]
1999	${\frac {N(\log \log N)^{1/2}}{(\log N)^{1/2)))$	Bourgain [5]
2008	${\frac {N(\log \log N)^{2}}{(\log N)^{2/3)))$	Bourgain [6]
2012	${\frac {N}{(\log N)^{3/4-o(1)}))$	Sanders [7]
2011	${\frac {(\log \log N)^{5}}{\log N}}N$	Slefuitoare [8]
2014	${\frac {(\log \log N)^{4}}{\log N}}N$	Bloom [9]
2020 (preprint)	${\frac {(\log \log N)^{3}(\log \log \log N)^{5}}{\log N}}N$	Shoen [10]
2020 (preprint)	${\frac {N}{(\log N)^{1+c)}},\c>0$	Bloom, Sisask [11]

Diferite dovezi

Analiza armonică

Teorema a fost demonstrată pentru prima dată în 1953 de Klaus Roth [2] [12] prin adaptarea metodei cercului Hardy-Littlewood. Demonstrarea a folosit ideea [13] , care a fost generalizată ulterior pentru demonstrația generală a teoremei lui Szémeredi: toate mulțimile de o densitate dată sunt împărțite în două grupe - „uniform” și „neuniform”, iar „uniformitate” înseamnă o densitate superioară. legat de coeficienții Fourier . Dacă mulțimea este uniformă, atunci prezența progresiilor în ea poate fi dovedită direct, altfel se poate dovedi existența unei subprogresii în care densitatea mulțimii este mai mare decât în rândul segmentului seriei naturale din care face parte. .

Metoda vă permite să obțineți o estimare . Detaliile tehnice ale demonstrației, limita coeficienților Fourier care definesc „uniformitatea” și constantele rezultate pot diferi de la sursă la sursă. $N_{0}(\delta )\leqslant e^{e^{\frac {c}{\delta ))}$

Combinatorial (prin lema lui Szemeredi)

Dovada teoremei lui Roth poate fi dedusă [14] ca un caz special al teoremei lui Szemeredy din demonstrația lui Szemeredy. Acest mod de demonstrare necesită utilizarea lemei de regularitate a lui Szémerédy și a teoremei colțului , din care decurge direct teorema lui Roth. Este chiar posibil [15] să renunți la utilizarea teoremei colțului și să derivăm teorema lui Roth direct din lema de eliminare a triunghiului , dar numai în formularea pentru grupuri ciclice finite (vezi secțiunea „Generalizări la diverse grupuri”).

Deoarece lema de regularitate Szemeredi dă limite superioare extrem de mari pentru valoarea obținută prin ea (cel puțin, turnuri de exponenți ), metoda în sine nu permite obținerea unor limite mai bune decât acestea.

Elementare (prin progresii aritmetice generalizate)

Ronald Graham , în cartea sa despre teoria Ramsey, oferă o versiune simplificată a demonstrației, bazată tot pe metoda Szemeredi, dar fără a utiliza lema regularității. Demonstrarea folosește progresii aritmetice generalizate de forma , care este mult mai ușor de demonstrat prezența în mulțime, iar din aceasta se deduce deja teorema Roth în sine. $a+\sum \limits _{k=1}^{n}{\epsilon _{k}x_{k}}\ (\epsilon _{i}\in \left\lbrace {0,1}\ dreapta\rcolata )$

Dovada lui Graham nu dă estimări pentru , ci arată doar existența, deoarece folosește existența unui punct din șir, pornind de la care toate punctele sunt suficient de aproape de limită , dar numai existența este demonstrată și pentru limită, și caracterul de convergenţă nu este analizat în principiu. $N$

Contraexemple pentru mulțimi non-dense

Pe lângă găsirea limitelor superioare pentru dimensiunea unei mulțimi fără progresii aritmetice, există și o problemă inversă - construirea celei mai mari mulțimi posibile care nu conține progresii aritmetice, adică un contraexemplu pentru denotarea limitelor îmbunătățirii estimărilor pe . Toate construcțiile cunoscute ale unor astfel de mulțimi se bazează pe ideea de a lua în considerare cifrele individuale ale numerelor într-un anumit sistem de numere și de a stabili condiții asupra valorilor acestor cifre. $A\subset \left\lbrace {1,\dots ,N}\right\rbrace$ $A$ $N_{0}(\delta )$

Erdős, Turan (1936)

Primul exemplu de mulțime fără progresii a fost dat în 1936 de Erdős și Turan, care au propus să se ia în considerare numerele care în sistemul ternar conțin doar cifrele 0 și 2. O astfel de mulțime conține doar numere, ceea ce este foarte mic în comparație cu cel de sus. limite. [16] $N^{\log _{3}{2}}$

Dovada corectitudinii construcției

Să --- Erdős--Turan să se aşeze. $A$

Dacă și , atunci în sistemul ternar în cifra cea mai semnificativă , unde aceste numere sunt diferite, egalitățile sunt îndeplinite . Prin urmare, într-o progresie aritmetică , ar fi satisfăcut și, prin urmare, . $a,b\in A$ $a<b$ $i$ $a_{i}=0,\b_{i}=2$ $a<c<b$ $c_{i}=1$ $c\nu \in A$

Salem, Spencer (1942)

Salem și Spencer în 1942 au generalizat ideea lui Erdős și Turan la sisteme de numărare cu o bază în creștere (în funcție de dimensiunea setului) și au obținut un set fără progresii de dimensiune . [17] $\exp \left({-O\left({\frac {\log N}{\log \log N)}\right)}\right)N$

Scurtă descriere a designului

În construcția Erdős-Turan, este foarte posibil să se permită numerele 0 și 1 în loc de 0 și 2 (atunci locul numărului mijlociu în progresie va ocupa un loc mai mare în dovada corectitudinii). Prin analogie cu aceasta, Salem și Spencer în sistemul -ary au considerat numere care conțin doar cifre de la 0 la , și un număr egal de apariții ale fiecărei cifre (cu asimptotice , poate fi considerat impar, iar numărul total de cifre --- împărțirea ). $d$ ${\frac {d-1}{2)}$ $d$ ${\frac {d-1}{2)}$

Prezența progresiilor este blocată de condiția privind apariția cifrelor individuale. Într-adevăr, dacă purtarea nu este utilizată în timpul adunării , atunci toate zerourile din (și, prin urmare, din ) pot fi formate numai prin adăugarea de zerouri din cifrele corespunzătoare și . Mai departe, prin inducție, putem demonstra coincidența pozițiilor tuturor celor uni, doi etc. și să ajungem la concluzia că . $a+c=2b$ $2b$ $b$ $A$ $c$ $a,b,c$ $a=b=c$

Scorul declarat se obține luând în considerare . $d\asymp {\frac {\log N}{(\log \log N)^{2))}$

Berend (1946)

În 1946, Behrend a adăugat o interpretare geometrică prin asocierea cifrelor numerelor cu coordonatele punctelor dintr-un spațiu multidimensional și luând în considerare numerele corespunzătoare în acest sens punctelor unei sfere . Acest lucru a făcut posibilă construirea unui set de dimensiuni fără progresie . [optsprezece] $\exp \left({-O\left({\sqrt {\log N}}\right)}\right)N$

Scurtă descriere a designului

Toate numerele cu cifre nu mai mari decât reprezentarea -ary sunt împărțite în grupuri cu aceleași valori . Cel mai mare dintre aceste grupuri este ales ca set și dimensiunea sa este estimată conform principiului Dirichlet . $x<(2m+1)^{n)$ $m$ $(2m+1)$ $x=x_{1}x_{2}\dots x_{n)$ $\sum \limits _{i=1}^{n}{x_{i}^{2))$

Datorită cifrelor limitate, la adăugarea unor astfel de numere, nu există transfer de cifre , astfel încât progresiile de lungime 3 au și o interpretare geometrică (ca punctele de pe aceeași linie). Dar, deoarece mingea este un corp strict convex , atunci sfera, ca limită, nu poate conține trei puncte pe o singură linie dreaptă. De aici rezultă că nu există progresii în setul ales.

Dimensiunea setului este cel mai bine estimată la $n\asymp {\sqrt {\log N}}$

Ulterior, estimarea lui Behrend a fost mărită cu un factor logaritmic printr-o ușoară rafinare a metodei [19] , dar nu există rezultate semnificativ mai bune din 2019.

Deoarece limitele superioare de un tip similar sunt cunoscute pentru unele generalizări ale teoremei lui Roth [20] [21] , există motive pentru a crede că limita lui Behrend este clară.

Variații și generalizări pentru diferite grupuri

Pentru grupuri ciclice finite

Atât demonstrația prin analiză armonică, cât și modul particular în care se aplică lema lui Szemeredi nu demonstrează teorema în sine, ci versiunea ei „ciclică”.

Pentru orice , există astfel încât dacă , și , atunci conține triplul , unde se înțelege că adăugarea înseamnă adăugare modulo $\delta \in (0;1)$ $N_{0}=N_{0}(\delta )$ $N>N_{0)$ $A\subset \mathbb {Z} _{N}$ $|A|>\delta N$ $A$ $(a,a+d,a+2d),\d\not =0$

Progresiile promise de această formulare pot fi progresii în dar nu în (de exemplu, ). Cu toate acestea, teorema lui Roth rezultă în mod evident din aceasta dacă considerăm mulțimea ca o mulțime de reziduuri în . Aceasta modifică doar densitatea cu o constantă, dar face ca toate progresiile să fie potrivite pentru . Prin urmare, această teoremă este echivalentă cu teorema principală a lui Roth. ${\mathbb {Z} }_{N}$ ${\mathbb {N} }$ $(N-2,N-1,0)$ $\left\lbrace {N+a:a\in A}\right\rbrace$ $\mathbb {Z} _{3N}$ ${\mathbb {N} }$

Pentru grupuri cu torsiune fixă mică

Următoarea teoremă, similară ca idee cu teorema lui Roth, nu rezultă din aceasta și nu o implică, dar este de interes pentru un studiu separat.

Lasă unele să fie reparate . Atunci pentru orice există astfel încât dacă , atunci $q\geq 3$ $\delta \in (0;1)$ $n_{0}=n_{0}(\delta,q)$ $n>n_{0},\A\subset {\mathbb {F} }_{q}^{n},\ |A|>\delta q^{n)$ $\exists a,d(d\not =(0,\dots ,0)):a,a+d,a+2d\in A$

Limite superioare

Teorema pentru grupuri a fost demonstrată pentru prima dată de Brown și Bahler în 1982 [22] , dar ei au demonstrat doar că pentru mulțimi fără progresii aritmetice, , dar restricțiile mai precise asupra au rămas o întrebare deschisă. ${\mathbb {F} }_{p}^{n}$ $|A|=o(q^{n})$ $|A|$

În 1993 (publicat în 1995) Roy Meshulam a demonstrat [23] că . Dovada lui a luat în considerare grupuri arbitrare și caracterele lor . Există și versiuni mai simplificate [24] ale acestei demonstrații, exclusiv pentru , care, folosind coeficienții Fourier din , generalizează direct ideile din demonstrația analitică a teoremei lui Roth. Dovada este chiar mai simplă din punct de vedere tehnic decât demonstrația teoremei lui Roth în sine, așa că [24] [25] este adesea dat ca prim exemplu de aplicare a metodei. $|A|\leq 2{\frac {q^{n}}{n}}$ ${\mathbb {F} }_{p}^{n}$ ${\mathbb {F} }_{p}^{n}$

În 2012, Bateman și Katz, luând în considerare cazul , au demonstrat [26] existența unei constante absolute , astfel încât pentru fără progresii aritmetice, . $q=3$ $\epsilon > 0$ $C$ $A\subset {\mathbb {F} }_{3}^{n)$ $|A|\leq {\frac {3^{n}}{n^{1+\epsilon }}}$

În 2016, Krut, Lev și Pach au demonstrat [27] pentru cazul că pentru seturi fără progresii. Ellenberg și Gijswijt, generalizând metoda lui Krut, Löw și Pach, folosind algebra polinomială , au demonstrat [28] [29] existența pentru fiecare a unei simple constante astfel încât if nu conține progresii de lungime 3. În lucrarea lor , . În special, pentru cazul . În ipoteza , din optimizarea funcției rezultă că , unde este o constantă absolută, care este soluția ecuației , adică , , unde $q=4$ $|A|\leq {3,62}^{n)$ $A\subset {\mathbb {F} }_{4}^{n)$ $q\geq 3$ $c=c(q)<q$ $|A|=O(c^{n})$ $A\subset {\mathbb {F} }_{q}^{n)$ $c(q)={\frac {q}{exp({\sup \limits _{\theta}\left\lbrace ({\frac {q-1}{3))\theta +\ln { \frac {e^{q\theta }-1}{q(e^{\theta }-1)}}}\right\rbrace })}}$ $q=3$ $|A|=o(2,756^{n})$ $\theta ={\frac {c_{0}}{q}}$ ${\frac {c}{3}}-\ln {\frac {e^{c}-1}{c}}$ $c(q)\sim {\frac {e^{c_{0}}-1}{c_{0}e^{(c_{0}/3)))}q$ $c_{0}$ $2ce^{c}-3e^{c}+c+3=0$ $c(q)\sim c_{1}q$ $c_{1}\aproximativ 0,841434...$

Limite inferioare

Cel mai bun [28] din 2016 construcție-contraexemplu permite [30] să construiască seturi de dimensiuni pentru grupuri de forma care nu conțin progresii aritmetice de lungime 3. ${\mathbb {F} }_{3}^{n)$ $\Omega (2,2^{n})$

Pentru grupuri arbitrare

Meshulam consideră [23] teorema lui Roth pentru un grup arbitrar și derivă o estimare pentru o mulțime fără progresii aritmetice de lungime 3. $G={\mathbb {Z} }_{k_{1}}\oplus \dots \oplus {\mathbb {Z} }_{k_{n}}$ $|A|<2{\frac {|G|}{n))$

Aceasta implică existența unei constante absolute astfel încât, pentru o mulțime fără progresii, $\beta>0$ $A\subset G$ $|A|<{\frac {|G|}{(\log {|G|})^{\beta )))$

Generalizare bidimensională

Generalizarea clasică a teoremei lui Roth pentru mulțimi bidimensionale este teorema colțului . Deși nu se menționează progresiile aritmetice (în sensul bidimensional), teorema lui Roth decurge din aceasta. $A\subset \left\lbrace {1,\dots ,N}\right\rbrace \times \left\lbrace {1,\dots ,N}\right\rbrace$

Vezi și

teorema lui Van der Waerden

Literatură

KF Roth. Despre anumite seturi de numere întregi // Journal of the London Mathematical Society. - 1953. - P. 104-109 . - doi : 10.1112/jlms/s1-28.1.104 .
DR Heath-Brown. Seturi întregi care nu conțin progresii aritmetice (engleză) // Journal of the London Mathematical Society. - 1987. - Vol. s2-35 , iss. 3 . - P. 385-394 . - doi : 10.1112/jlms/s2-35.3.385 .
E. Szemeridi. Seturi întregi care nu conțin progresii aritmetice // Acta Mathematica Hungarica. - 1990. - Vol. 56 . - P. 155-159 . - doi : 10.1007/BF01903717 .
J. Bourgain. Despre triple în progresia aritmetică (engleză) // Analiză geometrică și funcțională GAFA. - 1999. - Vol. 9 . - P. 968-984 . - doi : 10.1007/s000390050105 .
J. Bourgain. Teorema lui Roth asupra progresiilor revizuită // Journal d'Analyse Mathématique. - 2008. - Vol. 104 . - P. 155-192 . - doi : 10.1007/s11854-008-0020-x .
T. Sanders. Pe anumite alte seturi de numere întregi // Journal d'Analyse Mathématique. - 2012. - Vol. 116 . - P. 53-82 . - doi : 10.1007/s11854-012-0003-9 . - arXiv : 1007.5444 .
T. Sanders. Despre teorema lui Roth asupra progresiilor // Analele matematicii. - 2011. - Vol. 174 . - P. 619-636 . - doi : 10.4007/annals.2011.174.1.20 . - arXiv : 1011.0104 .
TF Bloom. O îmbunătățire cantitativă pentru teorema lui Roth privind progresiile aritmetice (engleză) // Journal of the London Mathematical Society. - 2014. - Vol. 93 , iss. 3 . - P. 643-663 . doi : 10.1112 / jlms/jdw010 . - arXiv : 1405,5800 .
T. Schoen. Legătura îmbunătățită în teorema lui Roth asupra progresiilor aritmetice . - 2020. - arXiv : 2005.01145 .
T. F. Bloom, O. Sisask. Depășirea barierei logaritmice în teorema lui Roth asupra progresiilor aritmetice . - 2020. - arXiv : 2007.03528 .

Note

↑ I. D. Shkredov, „Teorema lui Szemeredi și problemele progresiilor aritmetice”, Uspekhi Mat. Nauk, 61:6(372) (2006), 111-178; Matematică rusă. Surveys, 61:6 (2006), 1101-1166 . Preluat la 23 decembrie 2017. Arhivat din original la 24 decembrie 2017. (nedefinit)
↑ 12 Roth , 1953 .
↑ Heath-Brown, 1987 .
↑ Szemerédi, 1990 .
↑ Bourgain, 1999 .
↑ Bourgain, 2008 .
↑ Sanders, 2012 .
↑ Sanders, 2011 .
↑ Bloom, 2014 .
↑ Schoen, 2020 .
↑ Bloom, Sisask, 2020 .
↑ Dovada lui Roth prezentată de Harold Helfgott în rusă (link inaccesibil) . Preluat la 23 decembrie 2017. Arhivat din original la 24 decembrie 2017. (nedefinit)
↑ Postnauka, Ilya Shkredov - Teorema lui Semeredi
↑ Laboratorul Cebyshev, curs de prelegeri „Combinatorică aditivă”, curs 3
↑ Un mini curs de combinatorică aditivă Arhivat 29 august 2017 la Wayback Machine , p. 6
↑ P. Erdős, P. Turán, „On some sequences of integers”, Journal of the London Mathematical Society (iunie 1936) . Preluat la 23 decembrie 2019. Arhivat din original la 23 decembrie 2019. (nedefinit)
↑ R. Salem, DC Spencer, Proc. Natl. Acad. sci. USA 28 (1942), 561-563 . Preluat la 23 decembrie 2017. Arhivat din original la 3 iunie 2018. (nedefinit)
↑ FA Behrend, „Despre seturi de numere întregi care nu conțin trei termeni în progresia aritmetică”, Proc. Natl. Acad. sci. SUA 32 (1946), 331-332. . Preluat la 23 decembrie 2017. Arhivat din original la 4 iunie 2018. (nedefinit)
^ Michael Elkin, „An improved construction of progression-free sets”, Israel Journal of Mathematics, 184:93 (august 2011) . Preluat la 23 decembrie 2019. Arhivat din original la 27 noiembrie 2018. (nedefinit)
↑ T. Schoen, ID Shkredov, „Teorema lui Roth în multe variabile”, Israel Journal of Mathematics, volumul 199, paginile 287-308 (2014) Arhivat la 23 decembrie 2019 la Wayback Machine ( arXiv: 1106.1601 Arhivat la 23 decembrie 2019 la Wayback mașină )
↑ T. Schoen, O. Sisask, „Teorema lui Roth pentru patru variabile și structuri aditive în sume de mulțimi rare”, Forum of Mathematics Forum of Mathematics, Sigma, 4, E5. doi:10.1017/fms.2016.2 Arhivat la 1 mai 2020 la Wayback Machine ( arXiv:1408.2568 Arhivat la 23 decembrie 2019 la Wayback Machine )
^ TC Brown și JP Buhler, A density version of a geometric Ramsey theorem, Journal of Combinatorial Theory, Seria A 32 (1982), nr. 1, 20-34. . Preluat la 23 decembrie 2017. Arhivat din original la 9 august 2017. (nedefinit)
↑ 1 2 R. Meshulam, On subsets of finite abelian groups with no 3-term arithmetic progressions, Journal of Combinatorial Theory, Seria A 71 (1995), nr. 1, 168-172. (link indisponibil)
↑ 1 2 Un mini curs de combinatorie aditivă Arhivat 29 august 2017 la Wayback Machine , p. 39-42
↑ Laboratorul Cebyshev, Ilya Shkredov, Metode analitice în combinatorică aditivă, prelegere generală
↑ M. Bateman și N. Katz, New bounds on cap sets, Journal of the American Mathematical Society 25 (2012), nr. 2, 585-613. . Preluat la 23 decembrie 2017. Arhivat din original la 9 ianuarie 2018. (nedefinit)
↑ E. Croot, V. Lev și PP Pach, Seturile fără progresie în Z_n^4 sunt exponențial mici (2016). arXiv preprint 1605.01506. . Consultat la 23 decembrie 2017. Arhivat din original la 12 iunie 2018. (nedefinit)
↑ 1 2 Demonstrarea teoremei lui Roth pentru grupuri cu torsiune mică la arxiv.org . Consultat la 23 decembrie 2017. Arhivat din original la 12 iunie 2018. (nedefinit)
↑ Prezentarea dovezii lui Ellenberg și Gijswijt în limba rusă
↑ Y. Edel, Extensions of generalized product caps, Designs, Codes and Cryptography 31 (2004), nr. 1, 5-14. . Consultat la 23 decembrie 2017. Arhivat din original la 10 ianuarie 2018. (nedefinit)