[proofplan] We prove the bound $|A + B| \geq \min(p, |A| + |B| - 1)$ by strong induction on $|A|$, exploiting the fact that $\mathbb{Z}_p$ has no proper non-trivial subgroups. The base case $|A| = 1$ is immediate (a translate of $B$). For the inductive step, we translate $A$ and $B$ so that $0 \in A \cap B$ but some element $a \in A \setminus B$ exists, which is possible because every non-zero element of $\mathbb{Z}_p$ generates the whole group. The pair $(A \cap B, A \cup B)$ then has $|A \cap B| < |A|$ and $|A \cap B| + |A \cup B| = |A| + |B|$, so the induction hypothesis applies and the inclusion $(A \cap B) + (A \cup B) \subseteq A + B$ finishes the argument. [/proofplan] [step:Reduce to the case $|A| + |B| \leq p + 1$] If $|A| + |B| > p + 1$, then $|A| + |B| - 1 > p$, and since $A + B \subseteq \mathbb{Z}_p$ we have $|A + B| \leq p$, so the bound $|A + B| \geq \min(p, |A| + |B| - 1) = p$ requires $|A + B| = p$. We verify this holds: for any $c \in \mathbb{Z}_p$, we claim $c \in A + B$. Since $|A| + |B| > p + 1 \geq p$, and $|A| + |c - B| = |A| + |B| > p$ while both $A$ and $c - B$ are subsets of $\mathbb{Z}_p$ (which has $p$ elements), the sets $A$ and $c - B$ cannot be disjoint. So there exists $a \in A \cap (c - B)$, meaning $a \in A$ and $a = c - b$ for some $b \in B$, giving $c = a + b \in A + B$. We may therefore assume $|A| + |B| \leq p + 1$ for the remainder of the proof, and WLOG $|A| \leq |B|$ (since $A + B = B + A$ by commutativity of $\mathbb{Z}_p$). [guided] The minimum in $\min(p, |A| + |B| - 1)$ serves as a ceiling: the sum set $A + B$ is a subset of $\mathbb{Z}_p$, so $|A + B| \leq p$ always. When $|A| + |B| - 1 \geq p$, the bound simply asks $|A + B| = p$, i.e., the sum set fills all of $\mathbb{Z}_p$. Why must $A + B = \mathbb{Z}_p$ when $|A| + |B| > p$? Fix any target $c \in \mathbb{Z}_p$ and consider the two sets $A$ and $c - B = \{c - b : b \in B\}$. Since translation is a bijection on $\mathbb{Z}_p$, we have $|c - B| = |B|$. Both $A$ and $c - B$ are subsets of $\mathbb{Z}_p$, which has $p$ elements. If they were disjoint, their union would have $|A| + |B| > p$ elements inside a set of size $p$, which is impossible. So $A \cap (c - B) \neq \varnothing$: there exists $a \in A$ and $b \in B$ with $a = c - b$, i.e., $c = a + b \in A + B$. Since $c$ was arbitrary, $A + B = \mathbb{Z}_p$. With this case dispatched, we assume $|A| + |B| \leq p + 1$ and proceed by induction on $|A|$ (taking $|A| \leq |B|$ WLOG). [/guided] [/step] [step:Base case: $|A| = 1$ gives $|A + B| = |B|$] If $|A| = 1$, say $A = \{c\}$, then $A + B = \{c + b : b \in B\}$. The map $b \mapsto c + b$ is a bijection on $\mathbb{Z}_p$ (with inverse $x \mapsto x - c$), so $|A + B| = |B| = 1 + |B| - 1 = |A| + |B| - 1$. [/step] [step:Translate so that $0 \in A \cap B$ and some $a \in A \setminus B$] Assume $|A| \geq 2$. The sum set $A + B$ is invariant under the simultaneous replacements $A \mapsto A - \alpha$ and $B \mapsto B - \beta$ for any $\alpha \in A$, $\beta \in B$ (since $(A - \alpha) + (B - \beta) = A + B - \alpha - \beta$ is a translate of $A + B$, and translation preserves cardinality). So we may assume $0 \in A$. Pick any $a \in A$ with $a \neq 0$. Since $a \neq 0$ in $\mathbb{Z}_p$ and $p$ is prime, the element $a$ generates $\mathbb{Z}_p$ additively: the multiples $0, a, 2a, \ldots, (p-1)a$ are a permutation of $\mathbb{Z}_p$. In particular, the sequence $0a, 1a, 2a, \ldots, (p-1)a$ visits every element of $\mathbb{Z}_p$, so there exists a smallest $k \geq 0$ such that $ka \in B$ but $(k+1)a \notin B$. Replace $B$ by $B - ka$ (this is another translation that preserves $|A + B|$). After this replacement, $0 = ka - ka \in B$ and $a = (k+1)a - ka \notin B$. We now have $0 \in A$, $0 \in B$, $a \in A$, and $a \notin B$. [guided] We want to arrange the sets so that $A \cap B$ is non-empty but strictly smaller than $A$. Why? Because we are performing induction on $|A|$, and the inductive step will apply the hypothesis to the pair $(A \cap B, A \cup B)$, which requires $|A \cap B| < |A|$. First, translate $A$ so that $0 \in A$ (pick any element of $A$ and subtract it). Now we need to translate $B$ so that $0 \in B$ (ensuring $A \cap B \neq \varnothing$) while also ensuring some element of $A$ stays outside $B$ (ensuring $A \cap B \subsetneq A$). Pick any $a \in A$ with $a \neq 0$ (possible since $|A| \geq 2$). Since $p$ is prime and $a \neq 0$, the element $a$ is a generator of the cyclic group $\mathbb{Z}_p$: the multiples $0, a, 2a, \ldots, (p-1)a$ exhaust all of $\mathbb{Z}_p$. In particular, as $k$ ranges over $\{0, 1, \ldots, p-1\}$, the translates $B - ka$ cycle through all shifts of $B$ by multiples of $a$. Consider the set $B$ and the arithmetic progression $0, a, 2a, \ldots$. Since this progression hits every element of $\mathbb{Z}_p$ and $B \subsetneq \mathbb{Z}_p$ (we have $|B| \leq p - 1$ because $|A| \geq 2$ and $|A| + |B| \leq p + 1$), there exists a smallest $k \geq 0$ such that $ka \in B$ but $(k+1)a \notin B$. Translating $B$ by $-ka$, we ensure $0 \in B$ and $a \notin B$. After these translations: $0 \in A \cap B$ (so $A \cap B \neq \varnothing$), and $a \in A \setminus B$ (so $A \cap B \subsetneq A$). This is exactly the configuration needed for the inductive step. Note where primality was used: the claim that $a$ generates $\mathbb{Z}_p$ requires $\gcd(a, p) = 1$, which is automatic when $p$ is prime and $a \not\equiv 0$. In a composite group $\mathbb{Z}_n$, a non-zero element $a$ with $\gcd(a, n) > 1$ generates a proper subgroup, and the argument would fail. [/guided] [/step] [step:Apply the induction hypothesis to $(A \cap B,\, A \cup B)$] We have $0 \in A \cap B$ and $a \in A \setminus B$, so \begin{align*} 1 \leq |A \cap B| < |A|. \end{align*} By the inclusion-exclusion principle for finite sets, \begin{align*} |A \cap B| + |A \cup B| = |A| + |B|. \end{align*} Since $|A \cap B| < |A|$, the induction hypothesis (applied with $A \cap B$ in the role of $A$ and $A \cup B$ in the role of $B$) gives \begin{align*} |(A \cap B) + (A \cup B)| \geq |A \cap B| + |A \cup B| - 1 = |A| + |B| - 1. \end{align*} We verify the size condition for the induction hypothesis: $|A \cap B| + |A \cup B| = |A| + |B| \leq p + 1$, so the pair $(A \cap B, A \cup B)$ satisfies the same constraint we imposed at the start. [guided] This is the heart of the proof. We have reduced $|A|$ strictly: $|A \cap B| < |A|$, so the induction hypothesis applies. But will the resulting bound be strong enough? The inclusion-exclusion identity $|A \cap B| + |A \cup B| = |A| + |B|$ is the key algebraic fact. The induction hypothesis for the pair $(A \cap B, A \cup B)$ gives \begin{align*} |(A \cap B) + (A \cup B)| \geq |A \cap B| + |A \cup B| - 1 = |A| + |B| - 1. \end{align*} This is exactly the bound we want for $|A + B|$, provided we can show $(A \cap B) + (A \cup B) \subseteq A + B$. That containment is verified in the next step. We should also check the size condition: the induction hypothesis requires $|A \cap B| + |A \cup B| \leq p + 1$, which equals $|A| + |B| \leq p + 1$ by inclusion-exclusion. This is exactly the assumption we made at the start, so the condition is satisfied. [/guided] [/step] [step:Conclude via the containment $(A \cap B) + (A \cup B) \subseteq A + B$] Every element of $(A \cap B) + (A \cup B)$ has the form $x + y$ where $x \in A \cap B$ and $y \in A \cup B$. Since $x \in A \cap B \subseteq A$, we have $x \in A$. If $y \in B$, then $x + y \in A + B$. If $y \in A$, then $y \in A$ and $x \in B$ (since $x \in A \cap B \subseteq B$), so $x + y = y + x \in A + B$ by commutativity. In either case, $x + y \in A + B$. Therefore $(A \cap B) + (A \cup B) \subseteq A + B$, and combining with the induction hypothesis: \begin{align*} |A + B| \geq |(A \cap B) + (A \cup B)| \geq |A| + |B| - 1. \end{align*} Since we also established $|A + B| \leq p$ (as $A + B \subseteq \mathbb{Z}_p$), we conclude \begin{align*} |A + B| \geq \min(p,\, |A| + |B| - 1). \end{align*} [guided] Why does $(A \cap B) + (A \cup B) \subseteq A + B$ hold? Take any element $s \in (A \cap B) + (A \cup B)$, so $s = x + y$ with $x \in A \cap B$ and $y \in A \cup B$. - If $y \in B$: then $x \in A$ (since $A \cap B \subseteq A$), so $s = x + y \in A + B$. - If $y \in A$: then $x \in B$ (since $A \cap B \subseteq B$), so $s = x + y = y + x \in A + B$ by commutativity of $\mathbb{Z}_p$. In both cases, $s \in A + B$. So $(A \cap B) + (A \cup B) \subseteq A + B$. This containment is the reason intersection and union work as a replacement for the original pair: the sum set of the "refined" pair is no larger than the original sum set, yet the refined pair has the same total size $|A \cap B| + |A \cup B| = |A| + |B|$. The induction hypothesis gives the same numerical lower bound $|A| + |B| - 1$, and the containment transfers this bound to $|A + B|$. Combining everything: $|A + B| \geq |A| + |B| - 1$, and since $|A + B| \leq |\mathbb{Z}_p| = p$, we get $|A + B| \geq \min(p, |A| + |B| - 1)$. [/guided] [/step]