Många summor

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 11 maj 2018; kontroller kräver 7 redigeringar .

Mängden summor är begreppet additiv kombinatorik , motsvarande Minkowski-summan av finita mängder .

Definition

Låt vara vilken grupp som helst och vara ändliga mängder. Då är deras summa uppsättningen ${\mbox{G}}$ $A,B\subset {\mbox{G))$

A+B:=\{a+b:a\in A,\ b\in B\}

För en uppsättning kallas dess uppsättning summor . Flera summor förkortas [1] $A$ $A+A$

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

Relaterade definitioner

På samma sätt definieras uppsättningen av skillnader , uppsättningen produkter , uppsättningen kvoter och liknande för alla operationer. Till exempel är uppsättningen produkter definierad enligt följande [2] :

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

Värdet kallas för dubbleringskonstanten [3] , och de mängder som det är avgränsat för sägs ha en liten dubblering [4] . I samband med summaproduktsatsen betraktas ofta mängder med liten multiplikativ fördubbling , det vill säga för vilka värdet är begränsat [5] . $K(A)={\frac {|A+A|}{|A|}}$ ${\frac {|AA|}{|A|}}$

Egenskaper

Kraften i mängden summor är relaterad till den additiva energin genom ojämlikheten [6] , så den senare används ofta för att uppskatta den. $A+B$ $E(A,B)$ ${\displaystyle |A+B|E(A,B)\leq |A|^{2}|B|^{2))$

Summor av en uppsättning

Freimans teorem betraktar storlek som en indikator på struktureringen av en mängd (om dubbleringskonstanten är begränsad, liknar strukturen en generaliserad aritmetisk progression ). [7] [8] $A+A$ $A$

Summaproduktsatsen relaterar storleken på mängden summor och mängden produkter. Huvudhypotesen säger att för . [9] Kombinationen av summering och produkt i ett uttryck ledde till uppkomsten av aritmetisk kombinatorik . ${\displaystyle \max\{|A+A|,\ |AA|\}\geq |A|^{2-o(1)))$ $A\subset \mathbb {R}$

Vi studerar inverkan av element-för-element-tillämpning av en konvex funktion på summerbara mängder på storleken av mängden summor. För konvexa sekvenser är nedre gränser på och kända . [10] Mer allmänt, för en konvex funktion och en mängd, anses uppskattningsproblemet och några liknande ibland som en generalisering av summaproduktsatsen, eftersom och därför , och funktionen är konvex. [elva] $|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$

Summor av flera uppsättningar

Plünnecke-Rouge-ojämlikheten säger att tillväxten (ökningen i storlek med avseende på summerbara uppsättningar) av flera summor i genomsnitt (i förhållande till ) inte avsevärt överstiger tillväxten av . $|kA+lB|,\ k,l\in {\mathbb {N} }$ $k,l$ $|A+B|$

Den Rouge triangelolikheten relaterar storlekarna för alla uppsättningar och visar att den normaliserade storleken på skillnaden mellan uppsättningar kan betraktas som en pseudometrisk som återspeglar närheten av strukturen hos dessa uppsättningar. [12] $AB,\ BC,\ CA$ $A,B,C$ ${\displaystyle {\frac {|AB|}{\sqrt {|A||B|))))$

Struktur

En av de grundläggande frågorna för additiv kombinatorik är: vilken struktur kan eller bör uppsättningar av summor ha. Från och med början av 2020 är ingen icke-trivialt snabb algoritm känd för att avgöra om en given stor uppsättning kan representeras som eller . Vissa delresultat om strukturen hos summamängder är dock kända. $A+B,\ (|A|,|B|\geq 2)$ $A+A,\ |A|\geq 2$

Till exempel kan uppsättningar av summor av reella tal inte ha liten multiplikativ dubblering, det vill säga om , då för vissa . [13] Och i gruppen av rester modulo a primtal finns det bara mängder som kan representeras som . [14] [15] $A=B+C$ $|AA|\geq |A|^{1+c}$ $c>0$ $sid$ $2^{\left({{\frac {1}{2}}+o(1)}\right)p}$ $A+B,\ |A|,|B|\to \infty$

Det är känt att om är täta uppsättningar av naturliga tal, då innehåller långa aritmetiska progressioner . [16] Ändå är exempel på täta uppsättningar med en stark övre gräns för längden av sådana progressioner kända. [17] [18] $A,B$ $A+B$ ${\displaystyle {\mathbb {Z} }_{p))$

Se även

Litteratur

Freiman, Grigory Abelevich . Början av strukturell mängdteori . - Tryckeriet "Tatpoligraf". — 1966. (ryska)

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

I. D. Shkredov . Flera nya resultat om högre energier // Proceedings of the Moscow Mathematical Society. - 2013. - T. 74 , nr. 1 . - S. 35-73 . (ryska)

Paul Erdős , Endre Szemeredi . Om summor och produkter av heltal (engelska) // Studies in Pure Mathematics. - 1983. - S. 213-218 .

George Shakan. Om högre energinedbrytningar och fenomenet summaprodukt // Mathematical Proceedings of the Cambridge Philosophical Society. - 2019. - Vol. 167 , iss. 3 . - P. 599-617 .

Ilya D. Shkredov, Dmitrii Zhelezov. På additiv bas av set med liten produktsats . - 2016. - arXiv : math/1606.02320 .

B.Grön . Aritmetiska progressioner i summamängder (engelska) // Geometric & Functional Analysis GAFA. - 2002. - Vol. 12 . - s. 584-597 .

Ernie Croot, Izabella Laba, Olof Sisask. Aritmetiska progressioner i summamängder och -Nästan-Periodicitet $L^{p}$ // Kombinatorik, sannolikhet och beräkning. - 2013. - Vol. 22 , iss. 3 . - s. 351-365 .

N. Alon, A. Granville, A. Ubis. Antalet summängder i ett ändligt fält // Bulletin of the London Mathematical Society. - 2010. - Vol. 42 , iss. 4 .

Imre Z Ruzsa. Aritmetiska progressioner i sumsets (engelska) // Acta Arithmetica. - 1991. - Vol. 60 , iss. 2 . - S. 191-202 .

J. Bourgain. Om aritmetiska progressioner i summor av uppsättningar av heltal // A Tribute to Paul Erdos. - 1990. - S. 105-110 .

Ernie Croot, Imre Z. Ruzsa, Tomasz Schoen. Aritmetiska progressioner i glesa summamängder . – 2007.

ID Shkredov, T. Schoen. På summamängder av konvexa mängder // Combinatorics, Probability and Computing. - 2011. - S. 793-798 . - arXiv : math/1105.3542 .

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

Anteckningar

↑ Freiman, 1966 , sid. 7-8
↑ Tao, Wu, 2006 , sid. 54, sid. 92
↑ Tao, Wu, 2006 , sid. 57
↑ Tao, Wu, 2006 , sid. 240
↑ Tao, Wu, 2006 , sid. 188; Shkredov, 2013 , § 5
↑ Enligt Cauchy-Bunyakovsky ojämlikheten , , var är antalet representationer $(|A||B|)^{2}={\left({\summa \limits _{x\in A+B}{(A*B)(x)))\right)}^ {2}\leq |A+B|\summa \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 .
↑ Denna fråga kallas ofta det omvända problemet med additiv kombinatorik (se t.ex. Freiman, 1966 , avsnitt 1.8, s. 19)
↑ Erdős, Szemeredi, 1983 ; Shakan, 2019
↑ Shkredov, Schoen, 2011 .
↑ Elekes, Nathanson, Ruzsa, 2000 .
↑ Tao, Wu, 2006 , sid. 60
↑ Shkredov, Zhelezov, 2016 , konsekvens 2
↑ Alon, Granville, Ubis, 2010 .
↑ Medan det totala antalet uppsättningar i denna grupp uppenbarligen är $2^{p}$
↑ Bourgain bevisade detta först i Bourgain, 1990 . Det bästa resultatet för 2020 erhölls i Green, 2002 , och sedan tillrättavisats med en ny, mer allmän metod i Croot, Laba, Sisask, 2013
↑ Ruzsa, 1991 .
↑ En översikt över resultat om detta ämne finns i Croot, Ruzsa , Schoen, 2007