Cauchy–Davenportの定理

$g\in\mathbb{F}_p$ とする。$A$ と $g-B$ はどちらも $\mathbb{F}_p$ の部分集合で、個数の和 $\lvert A\rvert+\lvert B\rvert$ が $p$ を超えるので交わる（鳩の巣原理）。$a=g-b$（$a\in A$、$b\in B$）なら $g=a+b\in A+B$ である。$\square$

$n:=\lvert B\rvert$ についての帰納法で、すべての空でない $A$ について主張を示す。$n=1$ なら $\lvert A+B\rvert=\lvert A\rvert$ で成り立つ。
$n=2$ の場合．$B=\{b_1,b_2\}$、$\beta:=b_1-b_2\neq0$ とする。$\lvert A\rvert=p$ なら明らかなので $\lvert A\rvert\le p-1$ とし、結論が成り立たない、すなわち $\lvert A+B\rvert\le\lvert A\rvert$ と仮定する。$A+b_1$ と $A+b_2$ はどちらも $A+B$ に含まれ、個数は $\lvert A\rvert\ge\lvert A+B\rvert$ なので、$A+b_1=A+B=A+b_2$ である。両辺から $b_2$ を引くと $A+\beta=A$ となり、繰り返して $A+u\beta=A$（$u\in\mathbb{Z}$）を得る。$p$ は素数なので $\beta$ の整数倍は $\mathbb{F}_p$ 全体を動き、$a\in A$ を 1 つとると $\mathbb{F}_p=\{a+u\beta\}\subset A$ となって $\lvert A\rvert\le p-1$ に反する。
$n\ge3$ の場合．$\lvert B\rvert< n$ のとき主張が成り立つとする。$C:=A+B$ とおき、$\lvert C\rvert< p$ としてよい。$B$ の相異なる 2 元 $b,b'$ をとる。$n=2$ の場合を $C$ と $\{b,b'\}$ に当てると $\lvert C+\{b,b'\}\rvert\ge\min\{p,\lvert C\rvert+1\}=\lvert C\rvert+1$ なので、$C+b\not\subset C+b'$ であり、
$$ \delta-b\in C,\qquad \delta-b'\notin C $$
となる $\delta\in\mathbb{F}_p$ がある。$B':=\{\beta\in B\mid\delta-\beta\notin C\}$ とおくと、$b'\in B'$、$b\notin B'$ なので $1\le\lvert B'\rvert\le n-1$ である。
$A+B'$ と $\delta-(B\setminus B')$ は $C$ の互いに交わらない部分集合である。実際、どちらも $C$ に含まれ（後者は $B'$ の定義による）、$a+\beta'=\delta-\beta$（$a\in A$、$\beta'\in B'$、$\beta\in B\setminus B'$）なら $\delta-\beta'=a+\beta\in C$ となって $\beta'\in B'$ に反する。よって
$$ \lvert A+B'\rvert\le\lvert C\rvert-\lvert B\setminus B'\rvert=\lvert C\rvert-n+\lvert B'\rvert $$
である。帰納法の仮定から $\lvert A+B'\rvert\ge\min\{p,\lvert A\rvert+\lvert B'\rvert-1\}$ で、$\lvert A+B'\rvert\le\lvert C\rvert< p$ なので $\lvert A+B'\rvert\ge\lvert A\rvert+\lvert B'\rvert-1$ である。2 つの不等式から $\lvert C\rvert\ge\lvert A\rvert+n-1$ を得る。$\square$

要点：$e\in\mathbb{F}_p$ について $A(e):=A\cup(B+e)$、$B(e):=B\cap(A-e)$ とおくと、$A(e)+B(e)\subset A+B$ かつ $\lvert A(e)\rvert+\lvert B(e)\rvert=\lvert A\rvert+\lvert B\rvert$ である。$B(e)$ が空でなく $B$ より小さくなる $e$ を選んで、$\lvert B\rvert$ が最小の反例から矛盾を導く。

lem-cd-pigeonhole により $\lvert A\rvert+\lvert B\rvert\le p$ としてよい。$\lvert A+B\rvert\le\lvert A\rvert+\lvert B\rvert-2$ と仮定し、$A+B\subset E$、$\lvert E\rvert=\lvert A\rvert+\lvert B\rvert-2$ となる $E\subset\mathbb{F}_p$ をとって
$$ f(x,y):=\prod_{e\in E}(x+y-e)\in\mathbb{F}_p[x,y] $$
とおく。$f$ は $A\times B$ の全点で $0$ である。$f$ の全次数は $\lvert E\rvert$ で、最高次の部分は $(x+y)^{\lvert E\rvert}$ なので、$t_1:=\lvert A\rvert-1$、$t_2:=\lvert B\rvert-1$ について $x^{t_1}y^{t_2}$ の係数は $\binom{\lvert A\rvert+\lvert B\rvert-2}{\lvert A\rvert-1}$ である。$\lvert A\rvert+\lvert B\rvert-2< p$ なので分子の階乗は $p$ で割り切れず、この二項係数は $\mathbb{F}_p$ で $0$ でない。Combinatorial Nullstellensatz の第 2 形（$S_1=A$、$S_2=B$、$\lvert A\rvert>t_1$、$\lvert B\rvert>t_2$）により $f(a,b)\neq0$ となる $(a,b)\in A\times B$ があり、矛盾する。$\square$

$A=\{a_1<\cdots< a_k\}$、$B=\{b_1<\cdots< b_l\}$ とする。$(1,1)$ から $(k,l)$ まで、1 歩ごとに一方の添字を $1$ 増やす道 $(i_0,j_0),\dots,(i_{k+l-2},j_{k+l-2})$ をとると、$a_{i_m}+b_{j_m}$ は $m$ について狭義に増加するので、$A+B$ の相異なる $k+l-1$ 個の元である。
等号が成り立つとし、$1\le i< k$、$1\le j< l$ とする。$(i,j)$ と $(i+1,j+1)$ を通り、その間で $(i,j+1)$ を通る道と $(i+1,j)$ を通る道を、ほかの部分は共通にとる。どちらの道の値の列も $A+B$ 全体を小さい順に並べたものなので、同じ位置の値は等しく、$a_i+b_{j+1}=a_{i+1}+b_j$、すなわち $a_{i+1}-a_i=b_{j+1}-b_j$ である。これがすべての $i,j$ で成り立つので、隣り合う差はすべて同じ値 $d$ で、$A,B$ は公差 $d$ の等差数列である。逆は ex-cd-equality の 1 と同じ計算による。$\square$

$K$ は $\mathbb{F}_p$ の部分群なので、位数は $p$ の約数で、$K=\{0\}$ か $K=\mathbb{F}_p$ である（Lagrangeの定理）。$K=\mathbb{F}_p$ なら $A+B=A+B+\mathbb{F}_p=\mathbb{F}_p$ で $\lvert A+B\rvert=p$ である。$K=\{0\}$ なら $\lvert A+B\rvert\ge\lvert A\rvert+\lvert B\rvert-1$ である。$\square$

$k$ についての帰納法による。$k=1$ は明らかである。$X:=A_1+\cdots+A_{k-1}$ について帰納法の仮定から $\lvert X\rvert\ge\min\{p,m\}$（$m:=\sum_{i< k}\lvert A_i\rvert-k+2$）で、thm-cd-main から $\lvert X+A_k\rvert\ge\min\{p,\lvert X\rvert+\lvert A_k\rvert-1\}$ である。$\lvert X\rvert=p$ なら $X+A_k=\mathbb{F}_p$ で、そうでなければ $\lvert X\rvert\ge m$ なので $\lvert X+A_k\rvert\ge\min\{p,m+\lvert A_k\rvert-1\}$ である。$\square$

各 $a_i$ を $p$ で割った余りに取り替え、$0\le a_1\le a_2\le\cdots\le a_{2p-1}\le p-1$ と並べ替えてよい。ある $i\le p-1$ で $a_i=a_{i+p-1}$ なら、並びの単調性から $a_i=a_{i+1}=\cdots=a_{i+p-1}$ で、この $p$ 個の和 $pa_i$ は $p$ で割り切れる。そうでなければ、$i=1,\dots,p-1$ について $A_i:=\{a_i,a_{i+p-1}\}$ は $\mathbb{F}_p$ の 2 元集合である。cor-cd-iterated により
$$ \lvert A_1+\cdots+A_{p-1}\rvert\ge\min\{p,\ 2(p-1)-(p-1)+1\}=p $$
なので、$-a_{2p-1}$ も $s_1+\cdots+s_{p-1}$（$s_i\in A_i$）と書ける。$s_i$ は $a_i$ か $a_{i+p-1}$ で、添字 $i$（$1\le i\le p-1$）と $i+p-1$（$p\le i+p-1\le 2p-2$）はすべて異なるので、$s_1,\dots,s_{p-1}$ と $a_{2p-1}$ は相異なる添字の $p$ 個で、和は $p$ で割り切れる。$\square$