Monta summaa

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 11. toukokuuta 2018 tarkistetusta versiosta . tarkastukset vaativat 7 muokkausta .

Summien joukko on additiivisen kombinatoriikan käsite , joka vastaa äärellisten joukkojen Minkowskin summaa .

Määritelmä

Olkoon mikä tahansa ryhmä ja olla äärellisiä joukkoja. Sitten niiden summa on asetettu ${\mbox{G}}$ ${\näyttötyyli A,B\alajoukko {\mbox{G))}$

{\näyttötyyli A+B:=\{a+b:a\in A,\ b\in B\))

Yhdelle joukolle sen summajoukkoa kutsutaan . Useat summat on lyhennetty [1] $A$ ${\näyttötyyli A+A}$

{\displaystyle kA=A+\pisteet +A=\{a_{1}+\pisteet +a_{k}:a_{i}\in A,\ i=1,\pisteet ,k\))

Aiheeseen liittyvät määritelmät

Samalla tavalla erotusten joukko , tulojen joukko , osamääräjoukko ja vastaavat määritetään mille tahansa toiminnolle. Esimerkiksi tuotejoukko määritellään seuraavasti [2] :

{\displaystyle A\times B=\{ab\ :\ a\in A,\ b\in B\))

Arvoa kutsutaan tuplausvakioksi [3] , ja joukoilla, joille se on rajoitettu, sanotaan olevan pieni tuplaus [4] . Summatulolauseen yhteydessä tarkastellaan usein joukkoja, joissa on pieni kertova kaksinkertaistuminen , eli joiden arvo on rajoitettu [5] . $K(A)={\frac {|A+A|}{|A|}}$ ${\frac {|AA|}{|A|}}$

Ominaisuudet

Summajoukon teho liittyy summautuvaan energiaan epäyhtälöllä [6] , joten jälkimmäistä käytetään usein sen estimoimiseen. $A+B$ $E(A,B)$ ${\displaystyle |A+B|E(A,B)\leq |A|^{2}|B|^{2))$

Yhden sarjan summat

Freimanin lause pitää kokoa joukon rakenteellisuuden indikaattorina (jos tuplausvakio on rajoitettu, niin rakenne on samanlainen kuin yleistetty aritmeettinen progressio ). [7] [8] ${\näyttötyyli A+A}$ $A$

Summatulo-lause yhdistää summa- ja tulojoukon koon. Päähypoteesi sanoo, että . [9] Summauksen ja tulon yhdistelmä yhdessä lausekkeessa johti aritmeettisen kombinatoriikan syntymiseen . ${\displaystyle \max\{|A+A|,\ |AA|\}\geq |A|^{2-o(1)))$ $A\subset \mathbb {R}$

Tutkimme konveksin funktion elementtikohtaisen soveltamisen vaikutusta summattavaan joukkoon summajoukon kokoon. Konveksille sarjoille tunnetaan alarajat ja . [10] Yleisemmin konveksille funktiolle ja joukolle estimointiongelmaa ja joitakin vastaavia pidetään joskus summatulolauseen yleistyksenä, koska ja siksi , ja funktio on konveksi. [yksitoista] $|A+A|$ $|AA|$ $f$ ${\displaystyle f(A):=\{f(a):a\in A\))$ ${\displaystyle \max\{|A+A|,|f(A)+f(A)|\))$ $AA=\exp \left({\log A+\log A}\right)$ $|AA|=|\log A+\log A|$ $\exp$

Useiden sarjojen summat

Plünnecke-Rougen epätasa-arvo toteaa, että useiden summien kasvu (koon kasvu suhteessa summattuviin joukkoihin) ei keskimäärin (suhteessa ) ole paljon suurempi kuin . $|kA+lB|,\ k,l\in {\mathbb {N} }$ $k,l$ $|A+B|$

Rougen kolmion epäyhtälö suhteuttaa minkä tahansa joukkojen koot ja osoittaa, että joukkojen eron normalisoitua kokoa voidaan pitää pseudometriikkana, joka heijastaa näiden joukkojen rakenteen läheisyyttä. [12] $AB,\ BC,\ CA$ $A, B, C$ ${\displaystyle {\frac {|AB|}{\sqrt {|A||B|))))$

Rakenne

Yksi additiivisen kombinatoriikan peruskysymyksistä on: mikä rakenne voi tai pitäisi olla summajoukoilla. Vuoden 2020 alusta ei ole tiedossa ei-triviaalisen nopeaa algoritmia, joka määrittäisi, voidaanko tietty suuri joukko esittää muodossa tai . Kuitenkin joitain osittaisia tuloksia summajoukkojen rakenteesta tunnetaan. $A+B,\ (|A|,|B|\geq 2)$ $A+A,\ |A|\geq 2$

Esimerkiksi reaalilukujen summien joukoilla ei voi olla pientä kerrottavaa kaksinkertaistamista, eli jos , niin joillekin . [13] Ja jäännösten ryhmässä modulo a alkuluku on vain joukkoja, jotka voidaan esittää muodossa . [14] [15] $A=B+C$ $|AA|\geq |A|^{1+c}$ $c>0$ $s$ $2^{\left({{\frac {1}{2}}+o(1)}\oikea)p}$ $A+B,\ |A|,|B|\to \infty$

Tiedetään, että jos ovat tiheitä luonnollisia lukuja, niin se sisältää pitkiä aritmeettisia progressioita . [16] Siitä huolimatta tunnetaan esimerkkejä tiheistä joukoista, joilla on vahva yläraja tällaisten etenemien pituudelle. [17] [18] $A, B$ $A+B$ ${\displaystyle {\mathbb {Z} }_{p))$

Katso myös

Kirjallisuus

Freiman, Grigori Abelevitš . Rakennejoukkoteorian alku . - painotalo "Tatpoligraf". – 1966. (Venäjän kieli)

T. Tao , Van H. Vu. Additiiviset kombinatoriaalit . - Cambridge University Press. - 2006. - ISBN 0-511-24530-0 .

I. D. Shkredov . Useita uusia tuloksia korkeammista energioista // Proceedings of the Moscow Mathematical Society. - 2013. - T. 74 , no. 1 . - S. 35-73 . (Venäjän kieli)

Paul Erdős , Endre Szemedi . Kokonaislukujen summista ja tuloista (englanti) // Studies in Pure Mathematics. - 1983. - S. 213-218 .

George Shakan. Korkeamman energian hajoamisesta ja summatulo-ilmiöstä // Mathematical Proceedings of the Cambridge Philosophical Society. - 2019. - Vol. 167 , iss. 3 . - s. 599-617 .

Ilja D. Shkredov, Dmitrii Zhelezov. Pienen tuotesarjan sarjojen lisäainepohjalla . - 2016. - arXiv : math/1606.02320 .

B. Green . Aritmeettiset progressiot summajoukoissa (englanniksi) // Geometric & Functional Analysis GAFA. - 2002. - Voi. 12 . - s. 584-597 .

Ernie Croot, Izabella Laba, Olof Sisask. Aritmeettiset edistykset summajoukkoissa ja -melkein jaksollisuudessa $L^{p}$ // Kombinatoriikka, todennäköisyys ja laskeminen. - 2013. - Vol. 22 , iss. 3 . - s. 351-365 .

N. Alon, A. Granville, A. Ubis. Summien määrä äärellisessä kentässä // Bulletin of the London Mathematical Society. - 2010. - Vol. 42 , iss. 4 .

Imre Z Ruzsa. Aritmeettiset progressiot summajoukoissa (englanniksi) // Acta Arithmetica. - 1991. - Voi. 60 , iss. 2 . - s. 191-202 .

J. Bourgain. Aritmeettisista progressioista kokonaislukujoukkojen summissa // A Tribute to Paul Erdos. - 1990. - S. 105-110 .

Ernie Croot, Imre Z. Ruzsa, Tomasz Schoen. Aritmeettiset progressiot harvassa summassa . – 2007.

ID Shkredov, T. Schoen. Konveksien joukkojen summista // Kombinatoriikka, todennäköisyys ja laskenta. - 2011. - S. 793-798 . - arXiv : math/1105.3542 .

G. Elekes, MB Nathanson, IZ Ruzsa. Convexity and Sumsets (englanniksi) // Journal of Number Theory. - 2000. - Voi. 83 , iss. 2 . - s. 194-201 .

Muistiinpanot

↑ Freiman, 1966 , s. 7-8
↑ Tao, Wu, 2006 , s. 54, s. 92
↑ Tao, Wu, 2006 , s. 57
↑ Tao, Wu, 2006 , s. 240
↑ Tao, Wu, 2006 , s. 188; Shkredov, 2013 , § 5
↑ Cauchyn-Bunyakovsky-epäyhtälön mukaan , , missä on esitysten lukumäärä $(|A||B|)^{2}={\left({\sum \limits _{x\in A+B}{(A*B)(x)))\oikea)}^ {2}\leq |A+B|\summa \limits _{x\in A+B}{(A*B)(x)^{2}}=|A+B|E(A,B)$ ${\näyttötyyli (A*B)(x)}$ $x=a+b,\ a\in A,\ b\in B$
↑ Freiman, 1966 .
↑ Tätä kysymystä kutsutaan usein additiivisen kombinatoriikan käänteisongelmaksi (ks. esim. Freiman, 1966 , kohta 1.8, s. 19)
↑ Erdős, Szemedi, 1983 ; Shakan, 2019
↑ Shkredov, Schoen, 2011 .
↑ Elekes, Nathanson, Ruzsa, 2000 .
↑ Tao, Wu, 2006 , s. 60
↑ Shkredov, Zhelezov, 2016 , seuraus 2
↑ Alon, Granville, Ubis, 2010 .
↑ Vaikka tämän ryhmän sarjojen kokonaismäärä on ilmeisesti $2^{p}$
↑ Bourgain todisti tämän ensimmäisen kerran Bourgainissa vuonna 1990 . Vuoden 2020 paras tulos saatiin Greenissä, 2002 , ja sittemmin todettiin uudella, yleisemmällä menetelmällä Crootissa, Labassa, Sisaskissa 2013.
↑ Ruzsa, 1991 .
↑ Yleiskatsaus tämän aiheen tuloksista löytyy julkaisusta Croot, Ruzsa , Schoen, 2007