Mange summer

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 11. maj 2018; checks kræver 7 redigeringer .

Sættet af summer er begrebet additiv kombinatorik , svarende til Minkowski-summen af endelige mængder .

Definition

Lad være enhver gruppe og være endelige mængder. Så er deres sum sættet ${\mbox{G}}$ $A,B\subset {\mbox{G))$

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

For et sæt kaldes dets mængde summer . Flere summer er forkortet [1] $EN$ $A+A$

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

Relaterede definitioner

På samme måde er sættet af forskelle , sættet af produkter , sættet af kvotienter og lignende defineret for enhver operation. For eksempel er sættet af produkter defineret som følger [2] :

{\displaystyle A\ gange B=\{ab\ :\ a\i A,\ b\i B\))

Værdien kaldes fordoblingskonstanten [3] , og de mængder, som den er afgrænset for, siges at have en lille fordobling [4] . I forbindelse med sum-produktsætningen betragtes ofte mængder med lille multiplikativ fordobling , det vil sige, for hvilke værdien er begrænset [5] . $K(A)={\frac {|A+A|}{|A|}}$ ${\frac {|AA|}{|A|}}$

Egenskaber

Styrken af sættet af summer er relateret til den additive energi ved uligheden [6] , så sidstnævnte bruges ofte til at estimere den. $A+B$ $E(A,B)$ ${\displaystyle |A+B|E(A,B)\leq |A|^{2}|B|^{2))$

Summer af ét sæt

Freimans teorem betragter størrelse som en indikator for struktureringen af en mængde (hvis fordoblingskonstanten er begrænset, svarer strukturen til en generaliseret aritmetisk progression ). [7] [8] $A+A$ $EN$

Sum-produkt-sætningen relaterer størrelsen af mængden af summer og mængden af produkter. Hovedhypotesen siger, at for . [9] Kombinationen af summering og produkt i ét udtryk førte til fremkomsten af aritmetisk kombinatorik . ${\displaystyle \max\{|A+A|,\ |AA|\}\geq |A|^{2-o(1)))$ $A\subset \mathbb {R}$

Vi studerer indflydelsen af element-for-element-anvendelse af en konveks funktion til summerbare mængder på størrelsen af mængden af summer. For konvekse sekvenser er nedre grænser på og kendt . [10] Mere generelt, for en konveks funktion og et sæt, betragtes estimeringsproblemet og nogle lignende nogle gange som en generalisering af sumproduktsætningen, da og derfor , og funktionen er konveks. [elleve] $|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$

Summer af flere sæt

Plünnecke-Rouge-uligheden fastslår, at væksten (stigningen i størrelse i forhold til summerbare mængder) af flere summer i gennemsnit ikke (i forhold til ), overstiger væksten på . $|kA+lB|,\ k,l\in {\mathbb {N} }$ $k,l$ $|A+B|$

Rouge-trekantens ulighed relaterer størrelserne for alle sæt og viser, at den normaliserede størrelse af forskellen mellem mængder kan betragtes som en pseudometrisk, der afspejler tætheden af strukturen af disse sæt. [12] $AB,\ BC,\ CA$ $A,B,C$ ${\displaystyle {\frac {|AB|}{\sqrt {|A||B|))))$

Struktur

Et af de grundlæggende spørgsmål ved additiv kombinatorik er: hvilken struktur kan eller bør sæt af summer have. Fra begyndelsen af 2020 kendes ingen ikke-trivielt hurtig algoritme til at bestemme, om et givet stort sæt kan repræsenteres som eller . Der kendes dog nogle delresultater om strukturen af sumsæt. $A+B,\ (|A|,|B|\geq 2)$ $A+A,\ |A|\geq 2$

For eksempel kan sæt af summer af reelle tal ikke have lille multiplikativ fordobling, det vil sige hvis , så for nogle . [13] Og i gruppen af rester modulo a primtal er der kun mængder, der kan repræsenteres som . [14] [15] $A=B+C$ $|AA|\geq |A|^{1+c}$ $c>0$ $s$ $2^{\left({{\frac {1}{2}}+o(1)}\right)p}$ $A+B,\ |A|,|B|\to \infty$

Det er kendt, at hvis er tætte sæt af naturlige tal, så indeholder lange aritmetiske progressioner . [16] Ikke desto mindre kendes eksempler på tætte sæt med en stærk øvre grænse for længden af sådanne progressioner. [17] [18] $A,B$ $A+B$ ${\displaystyle {\mathbb {Z} }_{p))$

Se også

Litteratur

Freiman, Grigory Abelevich . Begyndelsen af strukturel mængdeteori . - Trykkeriet "Tatpoligraf". - 1966. (Russisk)

T. Tao , Van H. Vu. Additive kombinatorier . — Cambridge University Press. - 2006. - ISBN 0-511-24530-0 .

I. D. Shkredov . Flere nye resultater om højere energier // Proceedings of the Moscow Mathematical Society. - 2013. - T. 74 , no. 1 . - S. 35-73 . (Russisk)

Paul Erdős , Endre Szemeredi . Om summer og produkter af heltal (engelsk) // Studies in Pure Mathematics. - 1983. - S. 213-218 .

George Shakan. Om højere energinedbrydninger og sum-produkt-fænomenet // Mathematical Proceedings of the Cambridge Philosophical Society. - 2019. - Bd. 167 , udg. 3 . - S. 599-617 .

Ilya D. Shkredov, Dmitrii Zhelezov. På additive baser af sæt med lille produktsæt . - 2016. - arXiv : math/1606.02320 .

B.Grøn . Aritmetiske progressioner i sumsæt (engelsk) // Geometrisk og funktionel analyse GAFA. - 2002. - Bd. 12 . - S. 584-597 .

Ernie Croot, Izabella Laba, Olof Sisask. Aritmetiske progressioner i sumsæt og -næsten-periode $L^{p}$ // Kombinatorik, sandsynlighed og beregning. - 2013. - Bd. 22 , udg. 3 . - S. 351-365 .

N. Alon, A. Granville, A. Ubis. Antallet af sumsæt i et begrænset felt // Bulletin of the London Mathematical Society. - 2010. - Bd. 42 , udg. 4 .

Imre Z Ruzsa. Aritmetiske progressioner i sumsæt (engelsk) // Acta Arithmetica. - 1991. - Bd. 60 , iss. 2 . - S. 191-202 .

J. Bourgain. Om aritmetiske progressioner i summer af sæt af heltal // En hyldest til Paul Erdos. - 1990. - S. 105-110 .

Ernie Croot, Imre Z. Ruzsa, Tomasz Schoen. Aritmetiske progressioner i sparsomme summængder . – 2007.

ID Shkredov, T. Schoen. Om mængder af konvekse mængder // Combinatorics, Probability and Computing. - 2011. - S. 793-798 . - arXiv : math/1105.3542 .

G. Elekes, MB Nathanson, IZ Ruzsa. Convexity and Sumsets (engelsk) // Journal of Number Theory. - 2000. - Vol. 83 , udg. 2 . - S. 194-201 .

Noter

↑ 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
↑ Ifølge Cauchy-Bunyakovsky uligheden , hvor er antallet af repræsentationer $(|A||B|)^{2}={\venstre({\sum \limits _{x\in A+B}{(A*B)(x)))\right)}^ {2}\leq |A+B|\sum \limits _{x\in A+B}{(A*B)(x)^{2}}=|A+B|E(A,B)$ $(A*B)(x)$ $x=a+b,\ a\in A,\ b\in B$
↑ Freiman, 1966 .
↑ Dette spørgsmål kaldes ofte det omvendte problem med additiv kombinatorik (se f.eks. Freiman, 1966 , afsnit 1.8, s. 19)
↑ Erdős, Szemeredi, 1983 ; Shakan, 2019
↑ Shkredov, Schoen, 2011 .
↑ Elekes, Nathanson, Ruzsa, 2000 .
↑ Tao, Wu, 2006 , s. 60
↑ Shkredov, Zhelezov, 2016 , konsekvens 2
↑ Alon, Granville, Ubis, 2010 .
↑ Mens det samlede antal sæt i denne gruppe åbenbart er $2^{p}$
↑ Bourgain beviste dette første gang i Bourgain, 1990 . Det bedste resultat for 2020 blev opnået i Green, 2002 , og efterfølgende irettesat af en ny, mere generel metode i Croot, Laba, Sisask, 2013
↑ Ruzsa, 1991 .
↑ En oversigt over resultater om dette emne kan findes i Croot, Ruzsa , Schoen, 2007