Cauchy-Davenports sætning

Cauchy-Davenport-sætningen er et resultat af additiv kombinatorik, opkaldt efter Augustin Cauchy og Harold Davenport , der siger, at størrelsen af mængden af summer af to mængder i en restgruppe aldrig er væsentligt mindre end summen af deres størrelser. ${\displaystyle {\mathbb {Z} }_{p))$

Sætningen blev foreslået af Hans Heilbronn som et uløst problem til Harold Davenport, som løste det og offentliggjorde beviset i 1935. [en]

Ordlyd

Lad . Lad os definere . $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$

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

Essensen af ikke-trivialitet

For sæt af heltal (eller reelle) tal er en lignende erklæring indlysende, da for

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

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

tal og er altid forskellige. ${\displaystyle a_{1}+b_{1},a_{2}+b_{1}\dots ,a_{n}+b_{1))$ ${\displaystyle a_{n}+b_{2},\dots ,a_{n}+b_{m))$

Et lignende bevis virker ikke i ringen af rester, hvor de naturlige tal "løkker". For en ring med et sammensat udsagn er udsagnet simpelthen ikke sandt, da der er undergrupper (aritmetiske progressioner med en differensdeling ) for hvilke (dette er generelt, pr. definition, altid sandt for undergrupper). ${\displaystyle {\mathbb {Z} }_{m))$ $m$ $G$ $m$ $G+G=G$

Tilfældet med et simpelt modul er interessant, fordi det fungerer som en mellemting mellem disse to. Hvis sætningen viste sig at være forkert, så ville det betyde, at konstruktionen af selve restringen, selv uden undergrupper, indeholder en eller anden struktur tæt på en aritmetisk progression . Men sætningen er sand.

Metoder til bevis

Ekstremt tilfælde

Hvis , Så er udsagnet bevist elementært, da for ethvert sæt og skærer simpelthen på grund af deres størrelse, ifølge Dirichlet-princippet . $\min \left({|A|+|B|-1,p}\right)=p$ ${\displaystyle A+B={\mathbb {Z} }_{p))$ $x$ $EN$ $\left\lbrace {xb:b\in B}\right\rbrace$

Derfor ligger den største vanskelighed i at bevise hvornår . $|A+B|\geq |A|+|B|-1$ $|A|+|B|\leq p$

Kombinatorisk bevis

Det kombinatoriske bevis bruger det åbenlyse faktum, at . Hvis , så giver dette os mulighed for at anvende induktion på størrelsen af det mindste af disse to sæt. Ellers er to situationer mulige: $(A\cap B)+(A\cup B)\subset A+B$ $0<|A\cap B|<\min \left\lbrace {|A|,|B|}\right\rbrace$

$EN$ og krydser ikke $B$

et af sættene er fuldstændig indeholdt i det andet

Den første situation kan elimineres ved at flytte elementerne i et af sættene, da . Hvis alle sådanne forskydninger ligger fuldstændigt i mængden (uden tab af generalitet, antager vi, at ), Så er det let at vise, at for enhver , det vil sige, er en sløjfet uendelig aritmetisk progression med forskel . I lyset af de særlige kendetegn ved gruppen af rester modulo a prime betyder dette, at , og dette fører til det enkleste tilfælde . [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$

Algebraisk bevis

Et algebraisk bevis blev præsenteret i 2004 af Terence Tao. [3] . Dens grundlag er den kombinatoriske nulsætning . Hvis , hvor , så har polynomiet en koefficient, der ikke er nul ved . Af dette, ifølge den kombinatoriske nulsætning, følger det, at for nogle forsvinder polynomiet ikke, og dette er naturligvis ikke tilfældet pr. definition . [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$

Analytisk bevis

Beviset ved hjælp af harmonisk analyse bruger usikkerhedsprincippet og foldning af funktioner over . Funktionerne under overvejelse er sådan , at ${\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{matrix}}

hvor og , og krydset er så lille, som det kan være med sådanne dimensioner. Ved at bruge foldningens egenskaber har vi i dette tilfælde: $|{\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

Da, ifølge usikkerhedsprincippet , så følger Cauchy-Davenport-sætningen direkte fra dette, med det rigtige valg . [fire] $|{\rm {supp}}(f*g)|+|{\rm {supp}}({\widehat {f*g}})|\geq p+1$ ${\tilde {A}}$ ${\tilde {B}}$

Variationer og generaliseringer

Da vi overalt nedenfor vil tale om delmængder af et endeligt felt, så må man i ethvert estimat af størrelsen af mængden af summer lave en korrektion for, at hvis mængderne, som termerne er taget fra, er meget store i størrelse, så fylder summen hele feltet. Derfor betyder, for nemheds skyld, overalt under notationen for ethvert sæt summer (f.eks. ), at $|Q|\geq n$ $Q$ $Q=A+B$ $|Q|\geq \min \left\lbrace {p,n}\right\rbrace$

Forbud mod tilføjelse af lige elementer

I 1964 formodede Erdős og Heilbronn, at dette er sandt for et sæt [5] . Dette blev bevist i 1994 af Diaz da Silva og Hamidaon ved hjælp af repræsentationsteorien for symmetriske grupper ( specielt afsnit af repræsentationsteorien). De viste et endnu mere generelt resultat [6] , nemlig: $A\oplus A=\venstre\lbrace {a+b:a,b\in 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

Desuden falder dette udsagn nøjagtigt sammen med Erdős og Heilbronns formodninger. $m=2$

Dette skøn viste sig ikke at være det bedste - i 1996 beviste Alon, Natanzon og Rouja det . ${\Bigg \lbrace }{\sum \limits _{a\in A'}a\ :\ A'\subset A,|A'|=m}{\Bigg \rbrace }\geq m|A |-{\binom {m+1}{2}}+1$

Spørgsmålet opstod naturligvis - er det overhovedet muligt at sige noget lignende om . Dette spørgsmål kan løses ved at ændre det algebraiske bevis på Cauchy-Davenports hovedsætning, hvis vi tilføjer én faktor til det overvejede polynomium, det vil sige overveje , hvor . [2] $A\oplus B=\venstre\lbrace {a+b:a\i A,b\in B,a\not =b}\right\rbrace$ ${\displaystyle P(x,y)=(xy)\prod \limits _{c\in C}{(x+yc)))$ $A+B\subset C$

Forbud mod elementer med givne forskelle

I 2009 blev der offentliggjort en modifikation af det analytiske bevis, som gjorde det muligt at vise , at uligheden for et vilkårligt endeligt sæt ${\displaystyle S\subset {\mathbb {Z} }_{p))$

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

Kort beskrivelse af bevisideen

Som nævnt ovenfor bruger det analytiske bevis det faktum, at . For en mere kompliceret form af problemet er det derfor nødvendigt at modificere foldningsoperationen, så . Men det originale bevis gjorde betydelig brug af det faktum, at , så det er vigtigt at sikre, at det også overholder nogle generelle love. ${\rm {supp}}(A*B)\subset A+B$ $\cirk$ ${\rm {supp}}(A\cirkel B)\delsæt A{+}_{S}B$ ${\widehat {f*g}}={\widehat {f}}\cdot {\widehat {g}}$ ${\widehat {f\circ g))$

En oplagt måde at konstruere en modificeret foldning, for hvilken den udføres, er at begrænse den normale foldning. En grov konstruktion giver følgende formel: ${\rm {supp}}(A\cirkel B)\delsæt A{+}_{S}B$

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

(firkantede parenteser bruges i betydningen Iverson-notation ), men denne tilgang tillader ikke, at man kan udvide værket ved og arbejde analytisk med det. Derfor er det passende at introducere en funktion (vilkårlig til at begynde med) og overveje følgende operation: $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 )))))

Det er klart, hvis , så produktet med hensyn til forsvinder, så . $ab\in S$ $d\in S$ ${\rm {supp}}(f\circ g)\subset A{+}_{S}B$

Det næste trin er at vælge en bestemt funktion . For at gøre det nemmere at analysere Fourier-koefficienterne er det hensigtsmæssigt at forbinde funktioner med rødder fra enhed (da ideen om Fourier-koefficienter er baseret på egenskaberne af rødder fra enhed). For eksempel, $\lambda$ $f \cirkel 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 )))))

hvor er roden til enhed. En eksplicit betragtning af Fourier-koefficienten for en sådan funktion giver dog ikke det ønskede resultat. For at få en formel, der er praktisk at bruge , skal graderne af enhedsroden transformeres ved den samme lineære transformation, henholdsvis opnå og og overveje operationen $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 )))))

Så ud fra permutationen af termerne i det eksplicitte udtryk kan vi udlede det ${\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)))

hvor er koefficienter kun afhængige af . $c(k)$ $S$

Dernæst vælges mængderne på samme måde som det analytiske bevis for hovedsætningen. Men nu er de nødvendigvis valgt, så deres elementer er i en række - dette giver dig mulighed for at kontrollere og få det ønskede skøn, der handler på samme måde som i hovedbeviset. ${\tilde {A)],{\tilde {B))$ ${\widehat {A\circ B}}(x)$

Dette skøn er ikke nøjagtigt - tidligere, i 2002, beviste Pan og Sun, ved hjælp af algebraiske metoder, blandt de stærkere påstande, at . [7] $|A{+}_{S}B|\geq |A|+|B|-|S|-2$

Også i deres arbejde formodede Pan og Sun, at subtrahend 2 kan erstattes af 1, hvis endda. Forfatterne til et papir fra 2009 (som generaliserer den analytiske metode) foreslog, at selv betingelsen er tilstrækkelig til dette . [otte] $|S|$ $A\not =B$

Polynomiske restriktioner på termer

En stærk generalisering af Cauchy-Davenport-problemet består i at udlede en generel metode til estimering i form af dimensioner og størrelsen af et sæt af formen $EN$ $B$

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

hvor er et eller andet polynomium . For eksempel, i tilfældet, er et sådant problem reduceret til Erdős-Helbronn-formodningen. Sagen repræsenterer sin analog for flere sæt. $P$ $P(x,y)=xy$ ${\displaystyle p(x_{1},\dots ,x_{n})=\prod \limits _{1\leq i<j\leq n}{(x_{i}-x_{j)))))$

I 2002 overvejede Pan og Sun dette spørgsmål for polynomier i to variable og beviste følgende resultat [7] : $P(x,y)$

Lade være et homogent polynomium af grad over et vilkårligt felt af karakteristiske , Og der eksisterer, for hvilke dens koefficienter på og er ikke lig med nul. Overvej polynomiet og dets udvidelse . Lad os betegne . Lad også få et hvilket som helst polynomium af grad . Derefter $P(x,y)$ $d$ $s$ $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}}\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 \ venstre\lbrace {ps,\ |A|+|B|-1-dN(P_{*})}\right\rbrace

Erstatning af summeringen med et polynomium

I 2008 fik Sun følgende resultat [9] :

Lade være et polynomium sådan, at . $f(x_{1},\dots ,x_{n})=a_{1}{x_{1}}^{k}+\dots +a_{n}{x_{n}}^{k }+g(x_{1},\dots,x_{n})$ ${\rm {deg}}\ g<k$

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

Hvis , så gælder en lignende ulighed, selvom sættet af betingelser for . $k\geq n$ $(x_{1},\dots,x_{n})$ ${\displaystyle x_{i}\not =x_{j))$ $i\not =j$