Teorema Cauchy-Davenport

Teorema Cauchy-Davenport este un rezultat al combinatoriei aditive, numită după Augustin Cauchy și Harold Davenport , afirmând că dimensiunea mulțimii sumelor a două mulțimi dintr- un grup de reziduuri nu este niciodată substanțial mai mică decât suma dimensiunilor acestora. ${\mathbb {Z} }_{p)$

Teorema a fost propusă de Hans Heilbronn ca o problemă nerezolvată lui Harold Davenport, care a rezolvat-o și a publicat demonstrația în 1935. [unu]

Formulare

Lasă . Să definim . $A,B\in {\mathbb {Z} }_{p},\A\not =\emptyset ,\B\not =\emptyset$ $A+B=\left\lbrace {a+b\mod p:a\in A,b\in B}\right\rbrace$

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

Esența non-trivialității

Pentru mulțimi de numere întregi (sau reale), o afirmație similară este evidentă, deoarece for

A=\left\lbrace {a_{1}<\dots <a_{n}}\right\rbrace

B=\left\lbrace {b_{1}<\dots <b_{m}}\right\rbrace

numere și sunt întotdeauna distincte. ${\displaystyle a_{1}+b_{1},a_{2}+b_{1}\dots, a_{n}+b_{1))$ $a_{n}+b_{2},\dots ,a_{n}+b_{m)$

O dovadă similară nu funcționează în inelul de reziduuri, unde numerele naturale „buclă”. Pentru un inel cu o declarație compusă , afirmația pur și simplu nu este adevărată, deoarece există subgrupuri (progresii aritmetice cu o împărțire a diferențelor ) pentru care (acest lucru este, în general, prin definiție, întotdeauna adevărat pentru subgrupuri). ${\mathbb {Z} }_{m)$ $m$ $G$ $m$ $G+G=G$

Cazul unui modul simplu este interesant deoarece acţionează ca un intermediar între acestea două. Dacă teorema s-a dovedit a fi greșită, atunci aceasta ar însemna că construcția inelului de reziduuri în sine, chiar și fără subgrupuri, conține o structură apropiată de o progresie aritmetică . Dar teorema este adevărată.

Metode de probă

Caz extrem

Dacă , atunci enunțul este dovedit elementar, deoarece pentru orice mulțime și se intersectează pur și simplu din cauza dimensiunii lor, conform principiului Dirichlet . $\min \left({|A|+|B|-1,p}\right)=p$ $A+B={\mathbb {Z} }_{p)$ $X$ $A$ $\left\lbrace {xb:b\in B}\right\rbrace$

Prin urmare, principala dificultate constă în a demonstra când . $|A+B|\geq |A|+|B|-1$ $|A|+|B|\leq p$

Dovada combinatorie

Dovada combinatorie folosește faptul evident că . Dacă , atunci acest lucru ne permite să aplicăm inducție pe dimensiunea celei mai mici dintre aceste două seturi. În caz contrar, sunt posibile două situații: $(A\cap B)+(A\cup B)\subset A+B$ $0<|A\cap B|<\min \left\lbrace {|A|,|B|}\right\rbrace$

$A$ și nu se intersectează $B$

unul dintre seturi este complet cuprins în celălalt

Prima situație poate fi eliminată prin deplasarea elementelor unuia dintre mulțimi, deoarece . Dacă toate astfel de schimbări se află complet în mulțime (fără pierderea generalității, presupunem că ), atunci este ușor să arătăm că pentru orice , adică este o progresie aritmetică infinită în buclă cu diferență . Având în vedere particularitățile grupului de reziduuri modulo un prim, aceasta înseamnă că , și aceasta duce la cel mai simplu caz . [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}$ $B={\mathbb {Z} }_{p)$ $|A|+|B|>p$

Dovada algebrică

O demonstrație algebrică a fost prezentată în 2004 de Terence Tao. [3] . Baza sa este teorema nulă combinatorie . Dacă , unde , atunci polinomul are un coeficient diferit de zero la . Din aceasta, conform teoremei combinatorii zero, rezultă că pentru unii polinomul nu dispare, iar acest lucru, evident, nu este cazul, prin definiție . [2] $|A+B|=(|A|-1)+(|B'|-1)<|A|+|B|-1$ $B'\subset B$ $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$

Dovada analitică

Demonstrarea prin analiza armonică folosește principiul incertitudinii și convoluția funcțiilor peste . Funcţiile luate în considerare sunt astfel încât ${\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{matrice}}

unde și , iar intersecția este cât se poate de mică cu astfel de dimensiuni. Folosind proprietățile convoluției, în acest caz avem: $|{\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

Deoarece, conform principiului incertitudinii, , atunci din aceasta, cu alegerea corectă , decurge direct teorema Cauchy-Davenport. [patru] $|{\rm {supp}}(f*g)|+|{\rm {supp}}({\widehat {f*g}})|\geq p+1$ ${\tilde {A}}$ ${\tilde {B}}$

Variații și generalizări

Deoarece peste tot mai jos vom vorbi despre submulțimi ale unui câmp finit, atunci în orice estimare a mărimii mulțimii de sume, trebuie să facem o corecție pentru faptul că, dacă mulțimile din care sunt prelevați termenii sunt foarte mari ca dimensiune, atunci suma ocupă întregul câmp. Prin urmare, pentru comoditatea prezentării, peste tot sub notația pentru orice set de sume (de exemplu, ) înseamnă că $|Q|\geq n$ $Q$ $Q=A+B$ $|Q|\geq \min \left\lbrace {p,n}\right\rbrace$

Interzicerea adăugării de elemente egale

În 1964, Erdős și Heilbronn au presupus că acest lucru este adevărat pentru o mulțime [5] . Acest lucru a fost demonstrat în 1994 de Diaz da Silva și Hamidaon folosind teoria reprezentării grupurilor simetrice ( secțiunea specială a teoriei reprezentării). Au demonstrat un rezultat și mai general [6] , și anume: $A\oplus A=\left\lbrace {a+b:a,b\în A,a\not =b}\right\rbrace$ $|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

Mai mult , această afirmație coincide exact cu conjectura lui Erdős și Heilbronn. $m=2$

Această estimare s-a dovedit a nu fi cea mai bună - în 1996 Alon, Natanzon și Rouja au demonstrat că . ${\Bigg \lbrace }{\sum \limits _{a\in A'}a\ :\ A'\subset A,|A'|=m}{\Bigg \rbrace }\geq m|A |-{\binom {m+1}{2}}+1$

Întrebarea a apărut în mod natural - este posibil să spunem ceva asemănător despre . Această întrebare poate fi rezolvată prin modificarea dovezii algebrice a principalei teoreme Cauchy-Davenport, dacă adăugăm un factor la polinomul luat în considerare, adică considerăm , unde . [2] $A\oplus B=\left\lbrace {a+b:a\in A,b\in B,a\not =b}\right\rbrace$ $P(x,y)=(xy)\prod \limits _{c\in C}{(x+yc))$ $A+B\subset C$

Interzicerea elementelor cu diferențe date

În 2009, a fost publicată o modificare a dovezii analitice, permițând să se arate că pentru o mulțime finită arbitrară , inegalitatea $S\subset {\mathbb {Z} }_{p)$

$|A{+}_{S}B|=\#\left\lbrace {a+b:a\in A,b\in B,ab\nu \in S}\right\rbrace \leq | A|+|B|-2|S|-1$

Scurtă descriere a ideii de probă

După cum sa menționat mai sus, dovada analitică folosește faptul că . În consecință, pentru o formă mai complicată a problemei, este necesar să se modifice operația de convoluție astfel încât . Cu toate acestea, dovada originală a folosit în mod semnificativ faptul că , deci este important să ne asigurăm că respectă și unele legi generale. ${\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)}$

O modalitate evidentă de a construi o convoluție modificată pentru care este efectuată este de a restricționa convoluția normală. O construcție brută oferă următoarea formulă: ${\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 ]}}

(parantezele pătrate sunt folosite în sensul notației Iverson ), dar această abordare nu permite să extindă lucrarea și să lucreze cu ea analitic. Prin urmare, este adecvat să introduceți o funcție (arbitrară pentru început) și să luați în considerare următoarea operație: $d\în S$ $\lambda:{\mathbb {Z} _{p}}\la {\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 )))))

Evident, dacă , atunci produsul cu privire la dispare, astfel încât . $ab\în S$ $d\în S$ ${\rm {supp}}(f\circ g)\subset A{+}_{S}B$

Următorul pas este să selectați o caracteristică specifică . Pentru comoditatea analizei coeficienților Fourier, este oportun să se asocieze funcții cu rădăcini din unitate (deoarece ideea coeficienților Fourier se bazează pe proprietățile rădăcinilor din unitate). De exemplu, $\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 \în S}{{\Big (}{e_{p}(t-(xt))-e_{p}(d)}{\Big )))))

unde este rădăcina unității. Cu toate acestea, o luare în considerare explicită a coeficientului Fourier al unei astfel de funcții nu dă rezultatul dorit. Pentru a obține o formulă convenabilă de utilizat, gradele rădăcinii unității și trebuie să fie transformate prin aceeași transformare liniară, obținând, respectiv , și și luați în considerare operația $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 )))))

Apoi, din permutarea termenilor din expresia explicită , putem deduce că ${\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)))

unde sunt coeficienţi care depind numai de . $c(k)$ $S$

În continuare, se aleg mulțimile , în mod similar cu demonstrația analitică a teoremei principale. Dar acum sunt alese neapărat astfel încât elementele lor să fie într-un rând - acest lucru vă permite să controlați și să obțineți estimarea dorită, acționând în același mod ca în dovada principală. ${\tilde {A)], {\tilde {B)}$ ${\widehat {A\circ B}}(x)$

Această estimare nu este exactă - mai devreme, în 2002, Pan și Sun au dovedit, folosind metode algebrice, printre afirmația mai puternică că . [7] $|A{+}_{S}B|\geq |A|+|B|-|S|-2$

De asemenea, în lucrarea lor, Pan și Sun au presupus că subtrahendul 2 poate fi înlocuit cu 1 dacă este egal. Autorii unei lucrări din 2009 (care generalizează metoda analitică) au sugerat că chiar și condiția este suficientă pentru aceasta . [opt] $|S|$ $A\nu =B$

Restricții polinomiale asupra termenilor

O generalizare puternică a problemei Cauchy-Davenport constă în derivarea unei metode generale de estimare în termeni de dimensiuni și mărime a unei mulțimi de formă $A$ $B$

\oplus _{P}\sum \limits _{k=1}^{n}{A_{k}}=\left\lbrace {a_{1}+\dots +a_{n}:a_{ i}\în A_{i},P(a_{1},\dots ,a_{n})\not =0}\right\rbrace

unde este un polinom . De exemplu, în acest caz, o astfel de problemă se reduce la conjectura Erdős-Helbronn. Carcasa reprezintă analogul său pentru mai multe seturi. $P$ $P(x,y)=xy$ $p(x_{1},\dots,x_{n})=\prod \limits _{1\leq i<j\leq n}{(x_{i}-x_{j))))$

În 2002, Pan și Sun au considerat această întrebare pentru polinoame în două variabile și au demonstrat următorul rezultat [7] : $P(x,y)$

Fie un polinom omogen de grad peste un câmp arbitrar de caracteristică , și există pentru care coeficienții săi la și nu sunt egali cu zero. Luați în considerare polinomul și expansiunea lui . Să notăm . Fie de asemenea dat orice polinom de grad . Apoi $P(x,y)$ $d$ $p$ $i\in [0;|A|),\j\in [0;|B|)$ $x^{i}y^{di)$ $x^{dj}y^{j)$ $P_{*}(x)=P(x,1)$ $P_{*}(x)=(x+1)^{s}(x+\alpha _{1})^{t_{1}}\dots (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}}\right\rbrace }\right\rbrace$ $R(x,y)$ ${\rm {deg}}R<d$

{\Bigg \vert }{\oplus _{P+R}\sum \limits _{k=1}^{n}{A_{k)}}{\Bigg \vert }\geq \min \ stânga\lbrace {ps,\ |A|+|B|-1-dN(P_{*})}\dreapta\rbrace

Înlocuirea însumării cu un polinom

În 2008, Sun a obținut următorul rezultat [9] :

Fie un polinom astfel încât . $f(x_{1},\dots ,x_{n})=a_{1}{x_{1}}^{k}+\dots +a_{n}{x_{n}}^{k }+g(x_{1},\dots ,x_{n})$ ${\rm {grade}}\ g<k$

Apoi $\#\left\lbrace {f(x_{1},\dots,x_{n}):x_{1}\in A_{1},\dots,x_{n}\in A_{n} }\right\rbrace \geq \sum \limits _{i=1}^{n}{\left\lfloor {\frac {|A_{i}|-1}{k}}\right\rfloor }+1$

Dacă , atunci o inegalitate similară este valabilă chiar dacă setul de condiții pentru . $k\geq n$ $(x_{1},\dots ,x_{n})$ $x_{i}\nu =x_{j)$ $i\nu =j$

În 2009, acest rezultat a fost consolidat într-un caz particular [10] :

Fie un polinom astfel încât . $f(x_{1},\dots,x_{n})={x_{1}}^{k}+\dots +{x_{n}}^{k}+g(x_{1} ,\puncte ,x_{n})$ ${\rm {deg}}g<k$

Apoi , $\#\left\lbrace {f(x_{1},\dots,x_{n}):x_{1}\in A_{1},\dots,x_{n}\in A_{n} }\right\rbrace \geq \sum \limits _{i=1}^{n}{q_{i}}+1$

Unde $q_{i}=\min \limits _{i\leq j\leq n:j\equiv i{\pmod {k)}}{\left\lfloor {\frac {|A_{j}|- j}{k}}\dreapta\retaj }$

Vezi și

Multe sume

Note

^ Journal of the London Mathematical Society, H. Davenport, „On the Addition of Residue Classes” (ianuarie, 1935) . Preluat la 6 mai 2018. Arhivat din original pe 7 mai 2021. (nedefinit)
↑ 1 2 3 Laboratorul de matematică Cebyshev, Curs de prelegeri „Combinatorică aditivă”, Cursul 1
↑ Terence Tao, Un principiu de incertitudine pentru grupurile ciclice de ordin prim, Math. Res. Lett. 12 (2005) 121–127 . Preluat la 6 mai 2018. Arhivat din original la 12 iunie 2018. (nedefinit)
↑ arXiv:math/0308286 Terence Tao, „Un principiu de incertitudine pentru grupurile ciclice de ordin prim” . Preluat la 6 mai 2018. Arhivat din original la 12 iunie 2018. (nedefinit)
↑ P. Erdos, H. Heilbronn, Despre adăugarea claselor de reziduuri modulo p, Acta Arith. 9 (1964) 149–159 . Preluat la 6 mai 2018. Arhivat din original la 8 ianuarie 2022. (nedefinit)
↑ JA Dias da Silva, YO Hamidoune, Spații ciclice pentru derivați Grassmann și teoria aditivilor, Bull. London Math. soc. 26 (1994) 140–146
↑ 1 2 Hao Pan, Zhi-Wei Sun, „O limită inferioară pentru |{a + b: a ∈ A, b ∈ B, P(a, b) = 0}|”, J. Combin. Teoria Ser. A 100(2002), nr. 2, 387–393 . Preluat la 6 mai 2018. Arhivat din original la 13 august 2017. (nedefinit)
^ Song Guo, Zhi-Wei Sun, „A variant of Tao's method with application to restricted sumsets”, Journal of Number Theory, volumul 129, numărul 2, februarie 2009, paginile 434-438 . Preluat la 6 mai 2018. Arhivat din original la 21 ianuarie 2022. (nedefinit)
↑ Zhi-Wei Sun, „On value sets of polynomials over a field”, Finite Fields and Their Applications 14 (2008) 470–481 (link indisponibil)
↑ Hao Pan, Zhi-Wei Sun, „O nouă extensie a conjecturei Erd'os-Heilbronn”, J. Combin. Teoria Ser. A116(2009), nr. 8, 1374-1381.