Szemedin lause

Szemeredi-lause (aiemmin Erdős-Turan-oletus [1] ) on kombinatorisen lukuteorian lausunto pitkien aritmeettisten progressien olemassaolosta tiheissä joukoissa.

Se on klassinen esimerkki lauseesta additiivisessa kombinatoriossa . Joitakin sen todistusmenetelmiä käytettiin Green-Tao-lauseen todistuksessa [2] .

Sanamuoto

Lauseen alkuperäinen muotoilu sisälsi vain ehdon joukon tiheydelle kokonaisuutena.

Missä tahansa äärettömässä positiivisen asymptoottisen tiheyden joukossa on etenemistä minkä tahansa pituinen . [3] $A\subset {\mathbb {N} }$ $D(A)>0$ $k$

On olemassa lopullinen versio , joka vastaa yllä annettua [4] .

Kaikille ja riittävän suurille, mikä tahansa kokojoukko sisältää aritmeettisen pituuden progression . $\delta>0$ $N > N(k, \delta)$ $A\subset \{1,\dots ,N\}$ $|A|\geqslant \delta N$ $k$

Lopullinen variantti on tärkeä, kun otetaan huomioon mahdollisuus muotoilla kvantitatiivisia tuloksia suhteesta ja välillä . Hän osoittaa, että ensimmäisessä (äärettömässä) muunnelmassa raja, jonka jälkeen progressioiden läsnäolo tulee väistämättömäksi, ei ole itse tiheysarvo, vaan jokin jakautumislaki. Tämän rajan tarkkaa kuvausta ei tiedetä vuodesta 2019 lähtien. $\delta$ $N$

Lauseen lopullinen versio pysyy ekvivalenttina, jos tarkastellaan ja vastaavasti etenemistä jäännösrenkaassa modulo . Tämä lähestymistapa avaa tien trigonometrisiä summia käyttävälle todistukselle . $A\subset \mathbb {Z} _{N}$ $N$

Sillä tai lauseen väite on triviaali. Erikoistapausta kutsutaan Rothin lauseeksi . Sen todistaminen on paljon yksinkertaisempaa kuin yleisessä tapauksessa, ja se esitetään usein kirjallisuudessa erikseen. Lisäksi Rothin lauseesta tunnetaan paljon parempia arvioita kriittisistä arvoista yleisiin verrattuna, mukaan lukien yleistykset eri ryhmiin . $k = 1$ $k = 2$ $k = 3$ $\delta$

Historia

Lauseen väitteen muotoilivat ensimmäisen kerran olettamukseksi Erdős ja Turan [5] vuonna 1936.

Klaus Roth [6] todisti tapauksen vuonna 1953 soveltamalla Hardy-Littlewoodin ympyrämenetelmää . $k = 3$

Tapauksen todisti vuonna 1969 Endre Semeredi [7] käyttämällä kombinatorista menetelmää, joka on samanlainen kuin tapauksen todistamisessa . Roth [8] antoi toisen todisteen samasta tapauksesta vuonna 1972. $k = 4$ $k = 3$

Myös Szemedi [9] osoitti kekseliäisillä ja monimutkaisilla kombinatorisilla argumenteilla vuonna 1975 minkä tahansa yleisen tapauksen . Hänen todistuksensa perustana on ns. säännönmukaisuuslemma , joka kuvaa mielivaltaisten graafien rakennetta näennäissatunnaisuuden kannalta. $k$

Myöhemmin lauseelle löydettiin muita todisteita, joista tärkeimmät ovat Furstenbergin ( saksaksi Hillel Fürstenberg ) [10] todistus vuonna 1977 käyttäen ergodista teoriaa ja Gowersin todistus [11] vuonna 2001 harmonisen analyysin avulla . ja kombinatoriikka .

Arviot

Kvantitatiivisista estimaateista Szemeredi-lauseessa puhuttaessa tarkoitetaan yleensä intervallin [12] suurimman osajoukon kokoa, joka ei sisällä tietyn pituisia progressioita: $\{1,\dots ,N\}$

a_{k}(N)=\max {\big \{}|A|:A\subset \{1,\dots ,N\},\ \noleskelee a,d:\{a,a+ d ,\pisteet ,a+(k-1)d\}\subset A{\big \}}.

Ylärajojen johtamiseksi :lle tarvitaan siis yleisiä todisteita, ja alarajojen todistamiseksi (eli vastaavien ylärajojen kumoamiseksi) riittää yhden vastaesimerkin konstruktion esittäminen. $a_{k}(N)$

Ylärajat

Ensimmäinen yleinen todistus Szémerédyn lauseesta, johtuen säännönmukaisuuslemman käytöstä, antoi erittäin huonot arviot eksponentiaalien torneina ilmaistulle riippuvuudelle . $\delta =\delta (N)$

Gowers sai vuonna 2001 kvantitatiivisia arvioita, jotka ovat samanlaisia kuin vastaavat Rothin lauseen estimaatit [11] :

$a_{k}(N)\ll {\frac {N}{(\log N)^{c_{k))))$ , missä $c_{k}=2^{-2^{k+9)).$

Tapaukselle on olemassa paljon parempia arvioita , jotka on saatu tapauskohtaisilla menetelmillä. [13] $k = 3$

Alarajat

Suurimman (vuodesta 2019) sarjasta ilman progressioita on Behrendin rakentaminen . Se antaa kokoisia sarjoja . $k = 3$ $\exp {\Big (}{-}O{\big (}(\log N)^{1/2}{\big )}{\Big )}N$

Rankin yleisti tämän rakenteen mielivaltaisiksi vuonna 1961 ja muodosti joukon kokoa ilman pituusprosentteja . [neljätoista] $k$ $\exp \left({-}O\left((\log N)^{\frac {1}{k-1}}\right)\right)N$ $k$

Lyhyt kuvaus suunnittelusta

Behrendin konstruktio yhdistää luvun moniulotteisen avaruuden pisteeseen, jonka koordinaatit vastaavat luvun numeroita jossain numerojärjestelmässä. Joukko koostuu pisteistä, jotka vastaavat tässä mielessä jonkin pallon pisteitä. Pallon tiukka kuperaus takaa kolmen pisteen puuttumisen yhdellä suoralla ja siten kolmen termisen progression puuttumisen.

Rankinin idea on toistaa tämä temppu. Esimerkiksi for:lle otetaan pisteitä (ja niiden kuvia lukujärjestelmässä) ei yhdeltä pallolta, vaan kaikilta palloilta, joiden säteiden neliöt kuuluvat Behrend-joukon tyypin mukaan muodostettuun joukkoon (konstruktio for ). Sillä - palloista, joiden säteiden neliöt kuuluvat edellisen lauseen pistejoukkoon jne. $k = 4$ $k = 3$ $k = 5$

Samalla numerojärjestelmän kanta ja rajoitukset numeroiden arvolle kussakin iteraatiossa valitaan erityisellä tavalla, jotta yhtälön ratkaisujen lukumäärän lemma voidaan todistaa sellaisissa olosuhteissa, joten Itse asiassa rakentamisen välivaiheissa syntyvät pistejoukot eivät ole kooltaan optimaalisia pienempiä arvoja varten . $x_{1}^{2}+\dots +x_{k}^{2}=N$ $k$

Suhde muihin lauseisiin

Szemedyn lause on suora yleistys van der Waerdenin lauseesta , koska kun luonnolliset luvut jaetaan äärelliseen määrään luokkia, ainakin yhdellä niistä on positiivinen tiheys.

Szémeredyn lauseen kriittisten tiheysarvojen kohtuullisen hyvistä ylärajoista voi seurata Erdősin aritmeettisia progressioita . [viisitoista]

Katso myös

Kirjallisuus

Rue, Juanjo. Laskemisen taito. Kombinatoriikka ja numeraatio. - M .: De Agostini, 2014. - S. 123-132. — 144 s. — (Matematiikan maailma: 45 nidettä, nide 34). - ISBN 978-5-9774-0729-8 .
Tao, Terence Ergodinen ja kombinatorinen lähestymistapa Szemerédin lauseeseen // Additive Combinatoriics (uuspr.) / Granville, Andrew; Nathanson, Melvyn B.; Solymosi, Jozsef. - American Mathematical Society , 2007. - V. 43. - S. 145-193. — (CRM Proceedings & Lecture Notes). - ISBN 978-0-8218-4351-2 .
I. D. Shkredov. Szemedin lause ja aritmeettisten progressioiden ongelmat // Advances in Mathematical Sciences . - Venäjän tiedeakatemia , 2006. - Numero. 6 . - S. 111-179 . (Venäjän kieli)

Muistiinpanot

↑ On olemassa myös toinen hypoteesi, joka on nimetty näiden tiedemiesten mukaan - Erdős-Turanin olettamus additiivisista perusteista .
↑ Shkredov, 2006 , s. 159-165.
↑ Lauseesta ei seuraa äärettömien aritmeettisten progressioiden olemassaoloa , ja tällainen väite olisi todellakin väärä. Esimerkiksi vastaesimerkki on joukko numeroita, jotka sisältävät yhden desimaalimerkinnän ensimmäisessä numerossa. $A$
↑ Shkredov, 2006 , s. 113.
↑ Erdős, Paul & Turán, Paul (1936), Joistakin kokonaislukujonoista , Journal of the London Mathematical Society , osa 11 (4): 261–264, doi : 10.1112/jlms/s1-11.4.261 , < http: //www.renyi.hu/~p_erdos/1936-05.pdf > Arkistoitu 23. heinäkuuta 2020 Wayback Machinessa .
↑ Roth, Klaus Friedrich (1953), Tietyistä kokonaislukujoukoista, I , Journal of the London Mathematical Society , osa 28: 104–109, Zbl 0050.04002, MR : 0051853 , DOI 10.1112/jlms.10.1112/jlms .
↑ Szemerédi, Endre (1969), Kokonaislukujoukoista, joissa ei ole neljää elementtiä aritmeettisessa progressiossa , Acta Math. Acad. sci. ripustettu. T. 20: 89–104, Zbl 0175.04301, MR : 0245555 , DOI 10.1007/BF01894569
↑ Roth, Klaus Friedrich (1972), Sekvenssien epäsäännöllisyydet suhteessa aritmeettisiin progressioihin, IV , Periodica Math. unkari. T. 2: 301–326, MR : 0369311 , DOI 10.1007/BF02018670 .
↑ Szemerédi, Endre (1975), Kokonaislukujoukoista, joissa ei ole k alkiota aritmeettisessa progressiossa , Acta Arithmetica T. 27: 199–245, Zbl 0303.10056, MR : 0369312 , < http://matwedun.pl . ksiazki/aa/aa27/aa27132.pdf > Arkistoitu 10. joulukuuta 2020 Wayback Machinessa .
↑ Furstenberg, Hillel (1977), Diagonaalimittojen ergodinen käyttäytyminen ja Szemerédin lause aritmeettisista progressioista , J. D'Analyse Math. T. 31: 204–256, MR : 0498471 , DOI 10.1007/BF02813304 .
↑ 1 2 Gowers, Timothy (2001), Uusi todiste Szemerédin lauseesta , Geom. Toiminto. Anaali. T. 11(3): 465–588, MR : 1844079 , doi : 10.1007/s00039-001-0332-9 , < http://www.dpmms.cam.ac.uk/~wtg10/sz898.dvi > Arkistoitu kopio , joka on päivätty 26. syyskuuta 2020 Wayback Machinessa .
↑ Tai syklinen ryhmä , joka on sama vakioon asti. $\mathbb {Z} _{N}$
↑ Kvantitatiivinen parannus Rothin aritmeettisia progressioita koskevaan lauseeseen, Journal of the London Mathematical Society , osa 93 (3): 643-663, 2016 .
↑ Rankin, Robert A. (1962), Kokonaislukujoukot, jotka sisältävät enintään tietyn määrän termejä aritmeettisessa progressiossa, Proc. Roy. soc. Edinburghin lahko. A T. 65: 332–344, Zbl 0104.03705, MR : 0142526 .
↑ Shkredov, 2006 , s. 139-140.

Linkit

Ben Greenin ja Terence Taon ilmoitus – esipainos on saatavilla osoitteessa math.NT/0404188
Keskustelu Szemedin lauseesta (osa 1/5)
Ben Green ja Terence Tao: Szemedin lause Scholarpediassa
Weisstein, Eric W. SzemeredisTheorem (englanniksi) Wolfram MathWorld -verkkosivustolla .

Sanakirjat ja tietosanakirjat	Britannica (verkossa)