Cauchy-davenport: Difference between revisions
mNo edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
The Cauchy-Davenport | The Cauchy-Davenport Theorem states that for all nonempty sets <math>A,B \subseteq \mathbb{Z}/p\mathbb{Z}</math> , we have that | ||
<cmath>|A+B| \geq \min\{|A|+|B|-1,p\},</cmath> | <cmath>|A+B| \geq \min\{|A|+|B|-1,p\},</cmath> | ||
where <math>A+B</math> is defined as the set of all <math>c \in \mathbb{Z}/p\mathbb{Z}</math> that can be expressed as <math>a+b</math> for <math>a \in A</math> and <math>b \in B</math>. | where <math>A+B</math> is defined as the set of all <math>c \in \mathbb{Z}/p\mathbb{Z}</math> that can be expressed as <math>a+b</math> for <math>a \in A</math> and <math>b \in B</math>. | ||
== Proof of the Cauchy-Davenport Theorem by the Combinatorial Nullstellensatz == | |||
== Proof by Induction == | |||
== Applications of the Cauchy-Davenport Theorem == | |||
Latest revision as of 12:39, 20 September 2019
The Cauchy-Davenport Theorem states that for all nonempty sets 
, we have that
![\[|A+B| \geq \min\{|A|+|B|-1,p\},\]](http://latex.artofproblemsolving.com/0/9/f/09f3124f98a7f614911df0ae09fe454a96e533b2.png)
where 
is defined as the set of all 
that can be expressed as 
for 
and 
.
