Satz von Cauchy-Davenport

Der Satz von Cauchy-Davenport, englisch Cauchy–Davenport theorem, benannt nach den Mathematikern Augustin-Louis Cauchy und Harold Davenport, ist ein mathematischer Lehrsatz, der dem Übergangsfeld zwischen Additiver Zahlentheorie, Ramseytheorie und Gruppentheorie angehört und Anlass zu einer Anzahl weiterführender Untersuchungen gab. Der Satz behandelt Mächtigkeitsfragen zu Teilmengen von zyklischen Gruppen primer Gruppenordnung.

Formulierung des Satzes

Der Satz lässt sich folgendermaßen angeben:

Gegeben seien eine Primzahl $p$ und dazu in der zyklischen Gruppe $\mathbb {Z} _{p}$ zwei nichtleere Teilmengen $A,B\subseteq \mathbb {Z} _{p}$ sowie die zugehörige Teilmenge $A+B:=\{a+b\mid a\in A\;,\;b\in B\}$.

Dann gilt die Ungleichung

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

Zugehörige Sätze

Zum Umfeld des Satzes von Cauchy-Davenport gehören zahlreiche Resultate und nicht zuletzt vier Sätze, die mit den Namen der Mathematiker Martin Kneser, Henry B. Mann, Paul Erdős, Abraham Ginzburg, Abraham Ziv und Noga Alon verbunden sind.

Knesers Satz

Dieser Satz von Martin Kneser (englisch Kneser's theorem) aus dem Jahre 1955 hat zahlreiche Anwendungen in der Additiven Zahlentheorie und schließt insbesondere den Satz von Cauchy-Davenport in sich ein. Er lässt sich folgendermaßen angeben:

Gegeben seien eine abelsche Gruppe $(G,+)$, welche nicht allein aus dem neutralen Element bestehen soll, und darin zwei nichtleere endliche Teilmengen $A,B\subseteq G$ sowie die zugehörige Teilmenge $A+B:=\{a+b\mid a\in A\;,\;b\in B\}$.

Dabei soll

$|A|+|B|\leq |G|$

gelten.

Dann gibt es eine echte Untergruppe $H<G$ mit

$|A+B|\geq |A|+|B|-|H|$.

Manns Satz

Dieser Satz, den man (etwa) in Henry B. Manns Monographie Addition theorems: The Addition Theorems of Group Theory and Number Theory aus dem Jahre 1965 findet, behandelt Mächtigkeitsfragen zu Teilmengen beliebiger Gruppen und beinhaltet ebenfalls eine grundlegende Abschätzung:

Gegeben seien eine (nicht notwendig abelsche!) Gruppe $(G,\cdot )$ und darin zwei Teilmengen $A,B\subseteq G$ sowie die zugehörige Teilmenge $A\cdot B:=\{a\cdot b\mid a\in A\;,\;b\in B\}$.

Dann gilt

$A\cdot B=G$ oder $|A|+|B|\leq |G|$.

Beweis des Satzes von Mann

Manns Satz beruht auf einem einfachen Gedankengang:

Im Falle $A\cdot B\neq G$ existiert ein Element $c_{0}\in G\setminus {A\cdot B}$. Damit bildet man die Teilmenge

$c_{0}\cdot B^{-1}=\{c_{0}\cdot b^{-1}\mid b\in B\}$

und schließt, dass

$A\cap {c_{0}\cdot B^{-1}}=\emptyset$

gelten muss, da nämlich bei Vorliegen eines $b\in B$ mit $c_{0}\cdot b^{-1}\in A$ unmittelbar $c_{0}=\left(c_{0}\cdot b^{-1}\right)\cdot b\in {A\cdot B}$ folgte, was jedoch unmöglich ist.

Mit dieser Disjunktheit ergibt sich dann sogleich

$|A|+|B|=|A|+|c_{0}\cdot B^{-1}|=|A\;{\dot {\cup }}\;{c_{0}\cdot B^{-1}}|\leq |G|$.

Kombinatorischer Nullstellensatz

Der kombinatorische Nullstellensatz, englisch Combinatorial Nullstellensatz [sic!], den Noga Alon im Jahre 1999 veröffentlichte, ist – wie der Name bereits vermuten lässt – eng verbunden mit dem hilbertschen Nullstellensatz und aus diesem direkt ableitbar. Er zieht in der Kombinatorik und angrenzenden Gebieten eine Anzahl von Folgesätzen nach sich – insbesondere den Satz von Cauchy-Davenport – und lässt sich folgendermaßen darstellen:

Gegeben seien eine natürliche Zahl $n\in \mathbb {N}$ sowie ein Körper $K$ und dazu der Polynomring $K[x_{1},x_{2},\ldots ,x_{n}]$.

Weiter gegeben seien eine natürliche Zahl $d\in \mathbb {N} _{0}$ sowie ein Polynom $f\in K[x_{1},x_{2},\ldots ,x_{n}]$ vom Grade $d$, wobei es unter den Monomen von $f$ eines geben soll von der Gestalt $a_{t_{1},t_{2},\ldots ,t_{n}}\cdot x_{1}^{t_{1}}x_{2}^{t_{2}}\cdots x_{n}^{t_{n}}$ mit $d=t_{1}+t_{2}+\cdots +t_{n}$ und $a_{t_{1},t_{2},\ldots ,t_{n}}\neq 0$.

Gegeben seien schließlich noch endliche Mengen $S_{1},S_{2}\ldots ,S_{n}\subseteq K$ mit $|S_{1}|\geq {t_{1}+1},|S_{2}|\geq {t_{2}+1},\ldots ,|S_{n}|\geq {t_{n}+1}$.

Dann gilt:

Es existieren Elemente $s_{1}\in S_{1},s_{2}\in S_{2}\ldots ,s_{n}\in S_{n}$ mit $f(s_{1},s_{2},\ldots ,s_{n})\neq 0$.

Satz von Erdős-Ginzburg-Ziv

Dieser Satz (englisch Erdős-Ginzburg-Ziv theorem), den Erdős, Ginzburg und Ziv im Jahre 1961 vorlegten und mit Hilfe des Satzes von Cauchy-Davenport bewiesen, besagt Folgendes:

Zu jeder natürlichen Zahl $n\in \mathbb {N}$ und zu jeder dazu gegebenen endlichen Folge $\left(a_{i}\right)_{i=1,\dots ,{2n-1}}$ von $2n-1$ (nicht notwendig verschiedenen) ganzen Zahlen gibt es eine Teilfolge $\left(a_{i_{k}}\right)_{k=1,\dots ,n}$, deren Summe $\sum _{k=1}^{n}a_{i_{k}}$ durch $n$ teilbar ist.

Dabei wird der Satz von Cauchy-Davenport benutzt, um den Spezialfall, in dem $n$ eine Primzahl ist, zu zeigen und dann über die eindeutige Primfaktorzerlegung zu argumentieren.

Siehe auch

• Liste einer Auswahl von Arbeiten zum Satz von Cauchy-Davenport

Literatur

• Noga Alon: Combinatorial Nullstellensatz. In: Combinatorics, Probability and Computing. Band 8, 1999, S. 7–29 (MR1684621). 
• P. Erdős, A. Ginzburg, A. Ziv: Theorem in the additive number theory. In: Bulletin of the Research Council of Israel. Section F. 10F, 1961, S. 41–43 (englisch, MR3618568). 
• Stasys Jukna: Extremal Combinatorics (= Texts in Theoretical Computer Science). 2. Auflage. Springer Verlag, Heidelberg, Dordrecht, London, New York 2011, ISBN 978-3-642-17363-9 (englisch, MR2865719). 
• Martin Kneser: Abschätzung der asymptotischen Dichte von Summenmengen. In: Mathematische Zeitschrift. Band 58, 1953, S. 459–484 (MR0056632). 
• Martin Kneser: Ein Satz über abelsche Gruppen mit Anwendungen auf die Geometrie der Zahlen. In: Mathematische Zeitschrift. Band 61, 1955, S. 429–434 (MR0068536). 
• Henry B. Mann: Addition theorems: The Addition Theorems of Group Theory and Number Theory (= Interscience Publishers Tracts. Band 18). Interscience Publishers John Wiley & Sons , New York, London, Sydney 1965 (englisch, MR0181626). 
• Harald Niederreiter, Arne Winterhof: Applied Number Theory. Springer Verlag, Cham 1976, ISBN 3-319-22320-8, doi:10.1007/978-3-319-22320-6 (englisch, MR3364863). 
• Hans Schwerdtfeger: Introduction to Group Theory. Noordhoff International Publishing, Leyden 1976, ISBN 90-286-0495-2 (englisch, MR0435190).