\documentclass[12pt,a4paper]{amsart}

\usepackage{fullpage}
\usepackage{amsmath,amssymb}

\usepackage[colorlinks]{hyperref}


%% The usual theorems, etc
\theoremstyle{plain}
%% Do not number in section here because there are none.
\newtheorem{theorem}{Theorem}
\newtheorem*{theorem*}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}

%% Style for remarks
\theoremstyle{remark}
\newtheorem{remark}{Remark}

%% Style for definitions
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}

%% Use the AMS versions of the "less than or equal to" and "larger
%% than or equal to" signs
\renewcommand{\leq}{\leqslant}
\renewcommand{\geq}{\geqslant}

%% The basic number sets in the bold style
\newcommand{\C}{\mathbf{C}}
\newcommand{\R}{\mathbf{R}}
\newcommand{\Q}{\mathbf{Q}}
\newcommand{\Z}{\mathbf{Z}}


\begin{document}

\title{The Cauchy--Davenport Theorem}

\maketitle

We denote by $|X|$ the cardinality of a finite set~$X$. 

\begin{theorem}
  Let $p$ be a prime number. For any non-empty subsets $A$ and $B$ of
  $\Z/p\Z$, we have
  $$
  |A+B|\geq \min(|A|+|B|-1),
  $$
  where $A+B$ is the set of all elements of the form $a+b$ for some
  $(a,b)\in A\times B$.
\end{theorem}

\begin{proof}
  We proceed by induction on the size of the set~$B$.

  If $|B|=1$, then $A+B$ is a translate of~$A$, and therefore
  $|A+B|=|A|=|A|+|B|-1$, so that the inequality holds.

  We now assume that~$|B|\geq 2$ and that the bound is valid for all
  sets $B'$ such that $|B'|<|B|$.

  We can assume that~$0\in B$: indeed, if $b_0$ is any fixed element
  of~$B$, then $|A+B|=|A+B-b_0|$, and $B-b_0$ has the same size as~$B$,
  so we can replace $B$ by $B-b_0$.

  If $A=\Z/p\Z$, then $|A+b|=p$, so the result also holds. Thus we
  assume that $|A|<p$.

  Let $b_0$ be a non-zero element of $B$, which exists since $|B|\geq
  2$. Then we claim that $A+b_0\not=A$. Indeed, if that were the case,
  we would obtain $A+kb_0=A$ for any integer~$k\geq 0$, and fixing some
  element $a_0\in A$, it follows that $a_0+kb_0\in A$ for all~$k$, which
  then implies that $A=\Z/p\Z$, contrary to our assumption.

  We can therefore fix $a_0\in A$ such that $a_0+b_0\notin A$.  Define
  the sets
  \begin{gather*}
    B'=\{b\in B\,\mid\, a_0+b\in A\}\\
    A'=A\cup (a_0+(B\setminus B')).
  \end{gather*}

  Note that $|B'|<|B|$ since $b_0\notin B'$. Applying the induction
  hypothesis, we deduce the bound
  \begin{equation}\label{eq-1}
    |A'+B'|\geq \min(p,|A'|+|B'|-1).
  \end{equation}

  Now we note that, by construction, $A'+B'$ is contained in $A+B$: it
  suffices to check that $a_0+b_1+b_2\in A+B$ if $b_1\in B\setminus B'$
  and $b_2\in B'$; but $a_0+b_1+b_2=(a_0+b_2)+b_1$, and $a_0+b_2$ is
  in~$A$ by definition of $B'$.

  Finally, we note also that $|A'|=|A|+|B\setminus B'|$ (since the two
  sets in the union defining $A'$ are disjoint), so that
  $$
  |A'|+|B'|-1=|A|+|B\setminus B'|+|B'|-1=|A|+|B|-1.
  $$

  The inequality~(\ref{eq-1}) therefore implies
  $$
  |A+B|\geq |A'+B'|\geq |A|+|B|-1,
  $$
  which concludes the proof.
\end{proof}

\begin{remark}
  The lower bound provided by the theorem cannot be improved in
  general. For instance, let $n<p/2$ be an integer, and let
  $$
  A=B=\{0,1\bmod{p},...,n-1\bmod{p}\}.
  $$

  Then it is elementary that
  $$
  A+B=\{0\bmod{p},\ldots, 2n-2\bmod{p}\}
  $$
  (because $2n<p$), and hence
  $$
  |A+B|=2n-1=|A|+|B|-1.
  $$
\end{remark}

\end{document}
