Der Satz von Cauchy-Davenport, , 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.Stasys Jukna: Extremal Combinatorics. 2011, S. 232 ff., S. 363 ff.Henry B. Mann: Addition theorems: The Addition Theorems of Group Theory and Number Theory. 1965, S. 1 ff.Niederreiter/Winterhof: Applied Number Theory. 2015, S. 383 ff.
Formulierung des Satzes Der Satz lässt sich folgendermaßen angeben:Niederreiter/Winterhof, op. cit., S. 384 Gegeben seien eine Primzahl und dazu in der zyklischen Gruppe zwei nichtleere Teilmengen sowie die zugehörige Teilmenge .Man nennt eine solche in einer abelschen Gruppe enthaltenen Teilmengen auch Summenmenge (). Summenmengen in abelschen Gruppen bilden einen wesentlichen Gegenstand der Additiven Zahlentheorie. Dann gilt die Ungleichung .Mit bezeichnet man die Mächtigkeit einer Menge . Ist eine endliche Menge, so ist die Anzahl der in enthaltenen Elemente.
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 ZivAbraham Ziv, früher Abraham Zubkowski, geboren am 6. März 1940, gestorben am 5. März 2013, war ein israelischer Mathematiker; vgl. Artikel über Ziv in der englischsprachigen Wikipedia! und Noga Alon verbunden sind.
Knesers Satz Dieser Satz von Martin Kneser () aus dem Jahre 1955 hat zahlreiche Anwendungen in der Additiven Zahlentheorie und schließt insbesondere den Satz von Cauchy-Davenport in sich ein.Der hier vorgetragene Satz ist die abgeschwächte Version eine stärkeren Satzes, den Martin Kneser in einer früheren Arbeit im Jahre 1953 lieferte. Er lässt sich folgendermaßen angeben:Jukna, op. cit., S. 363–364 Gegeben seien eine abelsche Gruppe , welche nicht allein aus dem neutralen Element bestehen soll, und darin zwei nichtleere endliche Teilmengen sowie die zugehörige Teilmenge . Dabei soll
gelten. Dann gibt es eine echte Untergruppe mit .
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:Mann, op. cit., S. 1Hans Schwerdtfeger: Introduction to Group Theory. 1976, S. 58Schwerdtfeger zufolge hat Mann diese Abschätzung bereits 1952 vorgetragen. Angesichts der Einfachheit des dahinter liegenden Grundgedankens ist es naheliegend zu vermuten, dass diese Abschätzung auch schon vorher von anderen Mathematikern gefunden und benutzt wurde. Gegeben seien eine (nicht notwendig abelsche!) Gruppe und darin zwei Teilmengen sowie die zugehörige Teilmenge . Dann gilt oder .
Beweis des Satzes von Mann Manns Satz beruht auf einem einfachen Gedankengang:
Im Falle existiert ein Element . Damit bildet man die Teilmenge
und schließt, dass
gelten muss, da nämlich bei Vorliegen eines mit unmittelbar folgte, was jedoch unmöglich ist.
Mit dieser Disjunktheit ergibt sich dann sogleich .In einer Gruppe sind Inversion und Linkstranslation stets Bijektionen.
Kombinatorischer Nullstellensatz Der kombinatorische Nullstellensatz, [sic!], den Noga Alon im Jahre 1999 veröffentlichte,Alon stellte seinen „Combinatorial Nullstellensatz“ bereits 1995 vor, und zwar auf der Tagung über Diskrete Mathematik in Mátraháza, die vom 22. bis 28. Oktober 1995 dort stattfand. 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: Noga Alon: Combinatorial Nullstellensatz, Combin. Probab. Comput. 8 (1999), S. 7–29Jukna, op. cit., S. 228 ff., S. 229 Gegeben seien eine natürliche Zahl sowie ein Körper und dazu der Polynomring . Weiter gegeben seien eine natürliche Zahl sowie ein Polynom vom Grade , wobei es unter den Monomen von eines geben soll von der Gestalt mit und .Gemeint ist hier das neutrale Element der abelschen Gruppe . Gegeben seien schließlich noch endliche Mengen mit .
Dann gilt: Es existieren Elemente mit .
Satz von Erdős-Ginzburg-Ziv Dieser Satz (), den Erdős, Ginzburg und Ziv im Jahre 1961 vorlegten und mit Hilfe des Satzes von Cauchy-Davenport bewiesen, besagt Folgendes:Jukna, op. cit., S. 233 Zu jeder natürlichen Zahl und zu jeder dazu gegebenen endlichen Folge von (nicht notwendig verschiedenen) ganzen Zahlen gibt es eine Teilfolge , deren Summe durch teilbar ist. Dabei wird der Satz von Cauchy-Davenport benutzt, um den Spezialfall, in dem 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
Anmerkungen
Einzelnachweise
Cauchy-Davenport, Satz von Cauchy-Davenport, Satz von Cauchy-Davenport