Vosperの定理

$\lvert A+B\rvert\ge p-1$ なら成り立つので、$\lvert A+B\rvert\le p-2$ とする。Cauchy–Davenport の定理から $\lvert A+B\rvert\ge\lvert A\rvert+\lvert B\rvert-1$ で、thm-vo-main により等号は成り立たないので $\lvert A+B\rvert\ge\lvert A\rvert+\lvert B\rvert$ である。$\square$

$p$ は素数なので、$\mathbb{F}_p$ の元は $0,d,2d,\dots,(p-1)d$ と 1 回ずつ並び、$(p-1)d$ の次に $pd=0$ に戻る円順列をなす。$X$ はこの円順列の上で、いくつかの極大な連続部分 $\{x,x+d,\dots,x+(r-1)d\}$（$x-d\notin X$、$x+rd\notin X$）に分かれる。$X\neq\mathbb{F}_p$ なのでこのように分けられ、$X\neq\emptyset$ なので連続部分の個数 $t$ は $1$ 以上である。$(X+d)\setminus X$ は、各連続部分の直後の元 $x+rd$ からなるので、$\lvert X\cup(X+d)\rvert=\lvert X\rvert+t\ge\lvert X\rvert+1$ である。等号は $t=1$、すなわち $X$ がただ 1 つの連続部分 $\{x,x+d,\dots,x+(r-1)d\}$ であるときに限り、これは公差 $d$ の等差数列であることにほかならない。$\square$

$l:=\lvert Y\rvert$、$Y=\{y,y+d,\dots,y+(l-1)d\}$ とし、$P:=\{0,d,\dots,(l-2)d\}$ とおくと $Y=y+\{0,d\}+P$ である。$X':=X+\{0,d\}=X\cup(X+d)$ とおくと $X+Y=y+(X'+P)$ である。Cauchy–Davenport の定理から $\lvert X'+P\rvert\ge\min\{p,\lvert X'\rvert+l-2\}$ で、$\lvert X'+P\rvert=\lvert X+Y\rvert\le p-2$ なので
$$ \lvert X'\rvert\le\lvert X+Y\rvert-l+2=\lvert X\rvert+1 $$
である。$\lvert X\rvert\le\lvert X+Y\rvert\le p-2$ より $X$ は真部分集合なので、lem-vo-shift から $\lvert X'\rvert\ge\lvert X\rvert+1$ で、等号が成り立ち、$X$ は公差 $d$ の等差数列である。$\square$

$n:=\lvert B\rvert$ についての帰納法で、すべての空でない $A$ について示す。$S:=A+B$ とおく。$0\in B$ より $A\subset S$ で、$\lvert S\rvert\le p-2$ より $A$ は真部分集合である。
$n=2$ の場合．$B=\{0,d\}$（$d\neq0$）で、$S=A\cup(A+d)$ の個数は $\lvert A\rvert+1$ である。lem-vo-shift により $A$ は公差 $d$ の等差数列である。
$n\ge3$ の場合．$\lvert B\rvert< n$ のとき主張が成り立つとする。$E:=(S+B)\setminus S$ とおく。$0\in B$ より $S\subset S+B$ なので $\lvert E\rvert=\lvert S+B\rvert-\lvert S\rvert$ である。Cauchy–Davenport の定理から、$S+B=\mathbb{F}_p$ なら $\lvert E\rvert=p-\lvert S\rvert\ge2$、そうでなければ $\lvert E\rvert\ge\lvert B\rvert-1\ge2$ であり、いずれにせよ
$$ \lvert E\rvert\ge2 $$
である。$e\in E$ について $D(e):=\{b\in B\mid e-b\notin S\}$、$R(e):=B\setminus D(e)$ とおく。$e\notin S$ より $0\in D(e)$ で、$e\in S+B$ より $e=s+b$（$s\in S$、$b\in B$）と書けて $b\in R(e)$ なので、$R(e)\neq\emptyset$、$\lvert D(e)\rvert< n$ である。
$A+D(e)$ と $e-R(e)$ は $S$ の互いに交わらない部分集合である。実際、$A+D(e)\subset A+B=S$ で、$e-R(e)\subset S$ は $R(e)$ の定義による。$a+b'=e-b$（$a\in A$、$b'\in D(e)$、$b\in R(e)$）なら $e-b'=a+b\in S$ となって $b'\in D(e)$ に反する。よって
$$ \lvert A+D(e)\rvert\le\lvert S\rvert-\lvert R(e)\rvert=\lvert A\rvert+\lvert B\rvert-1-\lvert R(e)\rvert=\lvert A\rvert+\lvert D(e)\rvert-1 $$
である。一方 $\lvert A+D(e)\rvert\le\lvert S\rvert< p$ なので、Cauchy–Davenport の定理から $\lvert A+D(e)\rvert\ge\lvert A\rvert+\lvert D(e)\rvert-1$ で、等号
$$ \lvert A+D(e)\rvert=\lvert A\rvert+\lvert D(e)\rvert-1\le\lvert S\rvert\le p-2 $$
が成り立つ。ある $e\in E$ で $\lvert D(e)\rvert\ge2$ なら、$(A,D(e))$ は命題の仮定をみたし（$0\in D(e)$）、帰納法の仮定から $A$ は等差数列である。
残るのは、すべての $e\in E$ で $D(e)=\{0\}$ となる場合で、これが起こらないことを示す。$B^\ast:=B\setminus\{0\}$ とおくと $\lvert B^\ast\rvert=n-1\ge2$ である。$e\in E$、$b\in B^\ast$ なら $b\in R(e)$ なので $e-b\in S$、すなわち $E-B^\ast\subset S$ である。また $A$ と $E-B^\ast$ は交わらない：$a=e-b$ なら $e=a+b\in S$ となり $e\notin S$ に反する。$E-B^\ast\subset S\neq\mathbb{F}_p$ なので、Cauchy–Davenport の定理から $\lvert E-B^\ast\rvert\ge\lvert E\rvert+\lvert B^\ast\rvert-1$ である。よって
$$ \lvert A\rvert+\lvert B\rvert-1=\lvert S\rvert\ge\lvert A\rvert+\lvert E-B^\ast\rvert\ge\lvert A\rvert+\lvert E\rvert+\lvert B\rvert-2 $$
となり、$\lvert E\rvert\le1$ を得て $\lvert E\rvert\ge2$ に反する。$\square$

十分性は ex-vo-ap による。必要性を示す。$\lvert A+B\rvert=\lvert A\rvert+\lvert B\rvert-1\le p-2$ とし、$b_0\in B$ をとって $B':=B-b_0$ とおく。$A+B'=(A+B)-b_0$ なので $(A,B')$ も同じ等式と不等式をみたし、$0\in B'$ である。prop-vo-onesided により $A$ はある公差 $d$ の等差数列で、$\lvert A\rvert\ge2$ である。lem-vo-partner を $X=B$、$Y=A$ に当てると、$B$ も公差 $d$ の等差数列である。$\square$

$t-a=b$（$t\in T$、$a\in A$、$b\in B$）なら $t=a+b\in A+B$ となって $t\in T$ に反するので、$T-A\subset\mathbb{F}_p\setminus B$ で $\lvert T-A\rvert\le p-\lvert B\rvert$ である。$\lvert T\rvert=p-\lvert A\rvert-\lvert B\rvert+1\ge1$ なので、Cauchy–Davenport の定理から $\lvert T-A\rvert\ge\min\{p,\lvert T\rvert+\lvert A\rvert-1\}=p-\lvert B\rvert$ である。よって個数が等しく、包含は等号になる。$\lvert T-A\rvert=p-\lvert B\rvert=\lvert T\rvert+\lvert A\rvert-1$ である。$\square$

十分性：1 なら $\lvert A+B\rvert$ は他方の個数に等しい。2 なら Cauchy–Davenportの定理 の補題「大きい集合の和」（$\lvert A\rvert+\lvert B\rvert>p$ なら $A+B=\mathbb{F}_p$）により $\lvert A+B\rvert=p=\lvert A\rvert+\lvert B\rvert-1$ である。3 は ex-vo-complement、4 は ex-vo-ap による。
必要性：等号が成り立ち、$\lvert A\rvert,\lvert B\rvert\ge2$ とする。$s:=\lvert A\rvert+\lvert B\rvert-1=\lvert A+B\rvert\le p$ である。$s=p$ なら 2 が成り立つ。$s=p-1$ なら $T:=\mathbb{F}_p\setminus(A+B)$ は 1 元 $\{c\}$ で、prop-vo-dual から $c-A=\mathbb{F}_p\setminus B$、すなわち $B=\mathbb{F}_p\setminus(c-A)$ となり 3 が成り立つ。$s\le p-2$ なら thm-vo-main から 4 が成り立つ。$\square$