Cauchy-Davenport tétel

A Cauchy-Davenport-tétel az Augustin Cauchy -ról és Harold Davenportról elnevezett additív kombinatorika eredménye , amely kimondja, hogy egy maradékcsoport két halmazának összege soha nem kisebb, mint a méretük összege. ${\displaystyle {\mathbb {Z} }_{p))$

A tételt Hans Heilbronn javasolta megoldatlan problémaként Harold Davenportnak, aki megoldotta, és 1935-ben publikálta a bizonyítást. [egy]

Megfogalmazás

Hadd . Határozzuk meg . $A,B\in {\mathbb {Z} }_{p},\ A\not =\emptyset ,\ B\not =\emptyset$ $A+B=\left\lkapcsos zárójel {a+b\mod p:a\in A,b\in B}\right\rbrace$

Akkor $|A+B|\geq \min \left({|A|+|B|-1,p}\right)$

A nem trivialitás lényege

Egész (vagy valós) számok halmazai esetében nyilvánvaló egy hasonló állítás, mivel for

A=\left\lkapcsos zárójel {a_{1}<\pontok <a_{n}}\jobbra\rkapcsos zárójel

B=\left\lkapcsos zárójel {b_{1}<\pontok <b_{m}}\jobbra\rkapcsos zárójel

számok és mindig különböznek egymástól. ${\displaystyle a_{1}+b_{1},a_{2}+b_{1}\dots ,a_{n}+b_{1))$ ${\displaystyle a_{n}+b_{2},\dots ,a_{n}+b_{m))$

Hasonló bizonyítás nem működik a maradékok gyűrűjében, ahol a természetes számok "hurkolnak". Egy összetett állítású gyűrű esetén az állítás egyszerűen nem igaz, mivel vannak olyan alcsoportok (számtani sorozatok, amelyek különbsége osztható ), amelyekre (ez általában definíció szerint mindig igaz az alcsoportokra). ${\displaystyle {\mathbb {Z} }_{m))$ $m$ $G$ $m$ $G+G=G$

Egy egyszerű modul esete azért érdekes, mert köztesként működik a kettő között. Ha a tétel hibásnak bizonyulna, akkor ez azt jelentené, hogy magának a maradékgyűrűnek a konstrukciója még alcsoportok nélkül is tartalmaz valamilyen aritmetikai progresszióhoz közeli struktúrát . De a tétel igaz.

Bizonyítási módszerek

Extrém eset

Ha , akkor az állítás elemi bizonyítást nyer, hiszen bármely halmazra és metszéspontra pusztán a méretük miatt, a Dirichlet-elv szerint . $\min \left({|A|+|B|-1,p}\right)=p$ ${\displaystyle A+B={\mathbb {Z} }_{p))$ $x$ $A$ $\left\lbrace {xb:b\in B}\right\rbrace$

Ezért a fő nehézséget annak bizonyítása jelenti, hogy mikor . $|A+B|\geq |A|+|B|-1$ $|A|+|B|\leq p$

Kombinatorikus bizonyítás

A kombinatorikus bizonyítás azt a nyilvánvaló tényt használja fel, hogy . Ha , akkor ez lehetővé teszi, hogy indukciót alkalmazzunk e két halmaz közül a kisebbik méretére. Ellenkező esetben két helyzet lehetséges: $(A\cap B)+(A\cup B)\subset A+B$ $0<|A\cap B|<\min \left\lbrace {|A|,|B|}\right\rbrace$

$A$ és nem metszik egymást $B$

az egyik készlet teljesen benne van a másikban

Az első helyzet kiküszöbölhető az egyik halmaz elemeinek eltolásával, hiszen . Ha az összes ilyen eltolódás teljesen a halmazban van (az általánosság elvesztése nélkül feltételezzük, hogy ), akkor könnyen kimutatható, hogy bármely , azaz hurkolt végtelen aritmetikai progresszió különbséggel . Figyelembe véve a modulo a prím maradékcsoport sajátosságait, ez azt jelenti, hogy , és ez a legegyszerűbb esethez vezet . [2] $\forall s:|(A+s)+B|=|(A+B)+s|=|A+B|$ $B$ $|A|\leq |B|$ $b\in B\Rightarrow b+(a_{2}-a_{1})\in B$ $a_{1},a_{2}\in A$ $B$ $a_{2}-a_{1}$ ${\displaystyle B={\mathbb {Z} }_{p))$ $|A|+|B|>p$

Algebrai bizonyítás

Terence Tao 2004-ben bemutatott egy algebrai bizonyítékot. [3] . Ennek alapja a kombinatorikus nulltétel . Ha , ahol , akkor a polinom nullától eltérő együtthatóval rendelkezik . Ebből a kombinatorikus nullatétel szerint az következik, hogy egyeseknél a polinom nem tűnik el, és ez nyilvánvalóan definíció szerint nem így van . [2] $|A+B|=(|A|-1)+(|B'|-1)<|A|+|B|-1$ $B'\subset B$ ${\displaystyle P(x,y)=\prod \limits _{c\in C}{(x+yc)))$ ${\displaystyle x^{|A|-1}y^{|B'|-1))$ $x\in A,y\in B'\subset B$ $P(x,y)$ $A+B$

Elemző bizonyítás

A harmonikus elemzéssel történő bizonyítás a bizonytalansági elvet és a függvények konvolúcióját használja . A vizsgált funkciók olyanok, hogy ${\displaystyle {\mathbb {Z} }_{p))$ $f,g$

{\begin{matrix}{\rm {supp}}(f)=A\\{\rm {supp}}({\widehat {f}})={\tilde {A}}\\{ \rm {supp}}(g)=B\\{\rm {supp}}({\widehat {g}})={\tilde {B}}\\\end{mátrix}}

ahol és , és a metszéspont olyan kicsi, amennyire ilyen méretekkel lehet. A konvolúció tulajdonságait felhasználva ebben az esetben a következőket kapjuk: $|{\tilde {A}}|=p+1-|A|$ $|{\tilde {B}}|=p+1-|B|$ ${\tilde {A}}\cap {\tilde {B}}$

{\rm {supp}}({\widehat {f*g}})={\rm {supp}}({\widehat {f}}\cdot {\widehat {g}})={\ rm {supp}}({\widehat {f}})\cap {\rm {supp}}({\widehat {g}})=|{\tilde {A}}|+|{\tilde {B} }|-p

{\rm {supp}}(f*g)\subset {\rm {supp}}(f)+{\rm {supp}}(g)=A+B

Mivel a bizonytalansági elv szerint , akkor ebből a megfelelő választással közvetlenül a Cauchy - Davenport tétel következik. [négy] $|{\rm {supp}}(f*g)|+|{\rm {supp}}({\widehat {f*g}})|\geq p+1$ ${\tilde {A}}$ ${\tilde {B}}$

Változatok és általánosítások

Mivel az alábbiakban mindenhol véges mező részhalmazairól lesz szó, akkor az összeghalmaz méretének bármilyen becslésénél korrekciót kell végezni azon a tényen, hogy ha azok a halmazok, amelyekből a tagokat vettük, nagyon nagyok, akkor az összeg az egész mezőt elfoglalja. Ezért a bemutatás megkönnyítése érdekében az összegek jelölése alatt mindenhol (például ) azt jelenti, hogy $|Q|\geq n$ $K$ $Q=A+B$ $|Q|\geq \min \left\lbrace {p,n}\right\rbrace$

Egyenlő elemek hozzáadásának tilalma

1964-ben Erdős és Heilbronn azt sejtették, hogy ez igaz egy halmazra [5] . Ezt 1994-ben Diaz da Silva és Hamidaon bizonyította a szimmetrikus csoportok reprezentációs elméletével ( az ábrázoláselmélet speciális szakasza ). Még általánosabb eredményt hoztak [6] , nevezetesen: $A\oplus A=\left\lkapcsos zárójel {a+b:a,b\in A,a\not =b}\jobbra\rkapcsos zárójel$ $|A\oplus A|\geq 2|A|-3$

{\Bigg \lbrace }{\sum \limits _{a\in A'}a\ :\ A'\subset A,|A'|=m}{\Bigg \rbrace }\geq m|A |-m^{2}+1

Ráadásul ez az állítás pontosan egybeesik Erdős és Heilbronn sejtésével. $m=2$

Ez a becslés nem bizonyult a legjobbnak – 1996-ban Alon, Natanzon és Rouja bebizonyította ezt . ${\Bigg \lbrace }{\sum \limits _{a\in A'}a\ :\ A'\subset A,|A'|=m}{\Bigg \rbrace }\geq m|A |-{\binom {m+1}{2}}+1$

Természetesen felmerült a kérdés – lehet-e egyáltalán hasonlót mondani róla . Ez a kérdés megoldható a Cauchy-Davenport főtétel algebrai bizonyításának módosításával, ha a vizsgált polinomhoz hozzáadunk egy tényezőt, azaz figyelembe vesszük , ahol . [2] $A\oplus B=\left\lkapcsos zárójel {a+b:a\in A,b\in B,a\not =b}\jobbra\rkapcsos zárójel$ ${\displaystyle P(x,y)=(xy)\prod \limits _{c\in C}{(x+yc)))$ $A+B\subset C$

A megadott eltérésekkel rendelkező elemek tilalma

2009-ben közzétették az analitikus bizonyítást, amely lehetővé tette, hogy megmutassuk, hogy egy tetszőleges véges halmaz esetén az egyenlőtlenség ${\displaystyle S\subset {\mathbb {Z} }_{p))$

$|A{+}_{S}B|=\#\left\lkapcsos zárójel {a+b:a\in A,b\in B,ab\not \in S}\right\rbrace \leq | A|+|B|-2|S|-1$

A bizonyítási ötlet rövid leírása

Mint fentebb említettük, az analitikus bizonyítás azt a tényt használja fel, hogy . Ennek megfelelően a probléma bonyolultabb formájához a konvolúciós műveletet úgy kell módosítani, hogy . Az eredeti bizonyítás azonban jelentős mértékben kihasználta azt a tényt, hogy , ezért fontos gondoskodni arról, hogy néhány általános törvénynek is megfeleljen. ${\rm {supp}}(A*B)\subset A+B$ $\circ$ ${\rm {supp}}(A\circ B)\subset A{+}_{S}B$ ${\widehat {f*g}}={\widehat {f}}\cdot {\widehat {g}}$ ${\widehat {f\circ g))$

Egy kézenfekvő módja a módosított konvolúció megalkotásának, amelyre végrehajtják , a normál konvolúció korlátozása. Egy durva konstrukció a következő képletet adja: ${\rm {supp}}(A\circ B)\subset A{+}_{S}B$

(f\circ g)(x)=\sum \limits _{a+b=x}{f(a)g(b)\prod \limits _{d\in S}{[ab=d ]}}

(a szögletes zárójeleket az Iverson-jelölés értelmében használjuk ), de ez a megközelítés nem teszi lehetővé a munka kiterjesztését és elemzését. Ezért célszerű bevezetni egy függvényt (kezdetben tetszőleges), és figyelembe venni a következő műveletet: $d\in S$ $\lambda :{\mathbb {Z} _{p}}\to {\mathbb {C} }$

{\displaystyle (f\circ g)(x)=\sum \limits _{a+b=x}{f(a)g(b)\prod \limits _{d\in S}{{\Big ( }{\lambda (ab)-\lambda (d)}{\Big )))))

Nyilvánvalóan, ha , akkor a szorzat a tekintetében eltűnik, így . $ab\in S$ $d\in S$ ${\rm {supp}}(f\circ g)\subset A{+}_{S}B$

A következő lépés egy adott funkció kiválasztása . A Fourier-együtthatók elemzésének kényelme érdekében célszerű a függvényeket az egységből származó gyökekhez társítani (mivel a Fourier-együtthatók ötlete az egységből származó gyökök tulajdonságain alapul). Például, $\lambda$ $f \circ g$ $\lambda$

{\displaystyle (f\circ g)(x)=\sum \limits _{a+b=x}{f(a)g(b)\prod \limits _{d\in S}{{\Big ( }{e_{p}(ab)-e_{p}(d)}{\Big )}}}=\sum \limits _{t}{f(a)g(b)\prod \limits _{d \in S}{{\Big (}{e_{p}(t-(xt))-e_{p}(d)}{\Big )))))

hol van az egység gyökere. Egy ilyen függvény Fourier-együtthatójának explicit figyelembevétele azonban nem adja meg a kívánt eredményt. Egy kényelmesen használható képlet elkészítéséhez az egységgyök fokait és az egységgyök fokait ugyanazzal a lineáris transzformációval kell transzformálni, megkapva, illetve figyelembe véve a műveletet $e_{p}(k)=e^{2\pi {\frac {k}{p}}i}$ $t-(xt)=2t-x$ $d$ $xt$ $td$

{\displaystyle (f\circ g)(x)=\sum \limits _{t}{f(a)g(b)\prod \limits _{d\in S}{{\Big (}{e_{ p}(xt)-e_{p}(td)}{\Big )))))

Ezután az explicit kifejezésben szereplő kifejezések permutációjából arra következtethetünk ${\widehat {f\circ g))$

{\displaystyle {\widehat {f\circ g}}(x)=\sum \limits _{k=0}^{|S|}{c(k){\widehat {f}}(x+k) {\widehat {g}}(x+|S|-k)))

ahol csak attól függő együtthatók vannak . $c(k)$ $S$

Ezután a főtétel analitikus bizonyításához hasonlóan a halmazokat választjuk ki . De most szükségszerűen úgy vannak megválasztva, hogy elemeik sorban legyenek - ez lehetővé teszi a kívánt becslés ellenőrzését és elérését, ugyanúgy, mint a fő bizonyításban. ${\tilde {A)],{\tilde {B))$ ${\widehat {A\circ B}}(x)$

Ez a becslés nem pontos – korábban, 2002-ben Pan és Sun algebrai módszerekkel bizonyította az erősebb állítások között, hogy . [7] $|A{+}_{S}B|\geq |A|+|B|-|S|-2$

Szintén munkájukban Pan és Sun azt sejtették, hogy a 2-es részrész 1-gyel helyettesíthető, ha páros. Egy 2009-es (az analitikai módszert általánosító) írás szerzői szerint ehhez még a feltétel is elegendő . [nyolc] $|S|$ $A\not =B$

A kifejezésekre vonatkozó polinomiális korlátozások

A Cauchy-Davenport probléma erős általánosítása abból áll, hogy általános módszert kell levezetni az alakhalmaz méretei és mérete alapján történő becsléshez. $A$ $B$

\oplus _{P}\sum \limits _{k=1}^{n}{A_{k}}=\left\lkapcsos zárójel {a_{1}+\pontok +a_{n}:a_{ i}\in A_{i},P(a_{1},\pontok ,a_{n})\not =0}\jobbra\rkapcsos zárójel

hol van valamilyen polinom . Például az ügyben egy ilyen probléma az Erdős-Helbronn sejtésre redukálódik. A tok több készlet analógja. $P$ $P(x,y)=xy$ ${\displaystyle p(x_{1},\dots ,x_{n})=\prod \limits _{1\leq i<j\leq n}{(x_{i}-x_{j)))))$

2002-ben Pan és Sun ezt a kérdést két változóban vizsgálta polinomokra, és a következő eredményt bizonyította [7] : $P(x,y)$

Legyen homogén fokszámú polinom egy tetszőleges karakterisztikus mező felett , és léteznek olyanok , amelyekre együtthatói a és nem egyenlők nullával. Tekintsük a polinomot és annak kiterjesztését . Jelöljük . Legyen adott is bármely fokszámú polinom . Akkor $P(x,y)$ $d$ $p$ $i\in [0;|A|),\ j\in [0;|B|)$ ${\displaystyle x^{i}y^{di))$ ${\displaystyle x^{dj}y^{j))$ $P_{*}(x)=P(x,1)$ $P_{*}(x)=(x+1)^{s}(x+\alpha _{1})^{t_{1}}\pontok (x+\alpha _{k})^{t_ {k}}$ $N(P_{*})=\max \limits _{k\geq 0}\left\lbrace {p^{k}\cdot \#\left\lbrace {i:t_{i}\geq p ^{k}}\jobbra\rkapcsos zárójel }\jobbra\rkapcsos zárójel$ $R(x,y)$ ${\rm {deg}}R<d$

{\Bigg \vert }{\oplus _{P+R}\sum \limits _{k=1}^{n}{A_{k))}{\Bigg \vert }\geq \min \ bal\lkapcsos zárójel {ps,\ |A|+|B|-1-dN(P_{*})}\jobb\rkapcsos zárójel

Az összegzés cseréje polinomra

2008-ban a Sun a következő eredményt kapta [9] :

Legyen olyan polinom, hogy . $f(x_{1},\dots ,x_{n})=a_{1}{x_{1}}^{k}+\pontok +a_{n}{x_{n}}^{k }+g(x_{1},\pontok,x_{n})$ ${\rm {deg}}\ g<k$

Akkor $\#\left\lkapcsos zárójel {f(x_{1},\pontok ,x_{n}):x_{1}\in A_{1},\pontok ,x_{n}\in A_{n} }\right\rbrace \geq \sum \limits _{i=1}^{n}{\left\lfloor {\frac {|A_{i}|-1}{k))\right\rfloor }+1$

Ha , akkor egy hasonló egyenlőtlenség akkor is fennáll, ha a feltételrendszer . $k\geq n$ $(x_{1},\pontok,x_{n})$ ${\displaystyle x_{i}\not =x_{j))$ $i\not =j$

2009-ben ez az eredmény egy konkrét esetben erősödött [10] :

Legyen olyan polinom, hogy . $f(x_{1},\dots ,x_{n})={x_{1}}^{k}+\pontok +{x_{n}}^{k}+g(x_{1} ,\pontok ,x_{n})$ ${\rm {deg}}g<k$

Akkor , $\#\left\lkapcsos zárójel {f(x_{1},\pontok ,x_{n}):x_{1}\in A_{1},\pontok ,x_{n}\in A_{n} }\right\rbrace \geq \sum \limits _{i=1}^{n}{q_{i}}+1$

ahol $q_{i}=\min \limits _{i\leq j\leq n:j\equiv i{\pmod {k))}{\left\lfloor {\frac {|A_{j}|- j}{k}}\jobbra\rpadló }$

Lásd még

Sok összeget

Jegyzetek

↑ A London Mathematical Society folyóirata, H. Davenport, "On the Addition of Residue Classes" (1935. január) . Letöltve: 2018. május 6. Az eredetiből archiválva : 2021. május 7. (határozatlan)
↑ 1 2 3 Csebisev Matematikai Laboratórium, Előadások kurzusa "Additív kombinatorika", 1. előadás
↑ Terence Tao, Bizonytalansági elv prímrendű ciklikus csoportokhoz, Math. Res. Lett. 12 (2005) 121–127 . Letöltve: 2018. május 6. Az eredetiből archiválva : 2018. június 12. (határozatlan)
↑ arXiv:math/0308286 Terence Tao, "Bizonytalansági elv prímrendű ciklikus csoportokhoz" . Letöltve: 2018. május 6. Az eredetiből archiválva : 2018. június 12. (határozatlan)
↑ P. Erdos, H. Heilbronn, A modulo p maradékosztályok hozzáadásáról, Acta Arith. 9 (1964) 149–159 . Letöltve: 2018. május 6. Az eredetiből archiválva : 2022. január 8.. (határozatlan)
↑ JA Dias da Silva, YO Hamidoune, Ciklikus terek Grassmann-származékokhoz és additív elmélethez, Bull. London Math. szoc. 26 (1994) 140–146
↑ 1 2 Hao Pan, Zhi-Wei Sun, "A |{a + b alsó korlátja: a ∈ A, b ∈ B, P(a, b) = 0}|", J. Combin. Elmélet Ser. A 100(2002), sz. 2, 387–393 . Letöltve: 2018. május 6. Az eredetiből archiválva : 2017. augusztus 13. (határozatlan)
↑ Song Guo, Zhi-Wei Sun, "A Tao-módszer egy változata korlátozott összegekre történő alkalmazással", Journal of Number Theory, 129. kötet, 2. szám, 2009. február, 434-438 . oldal . Letöltve: 2018. május 6. Az eredetiből archiválva : 2022. január 21. (határozatlan)
↑ Zhi-Wei Sun, "A polinomok értékkészleteiről mezőn", véges mezők és alkalmazásaik, 14 (2008) 470–481 (hivatkozás nem érhető el)
↑ Hao Pan, Zhi-Wei Sun, "Az Erd'os-Heilbronn sejtés új kiterjesztése", J. Combin. Elmélet Ser. A116(2009), sz. 8, 1374-1381.