[proofplan] We argue by contradiction. Assuming $|A \mathbin{\dot{+}} B| \leq |A| + |B| - 3$, we choose a set $C$ of size $|A| + |B| - 3$ containing $A \mathbin{\dot{+}} B$ and construct the polynomial $f(X, Y) = (X - Y) \prod_{c \in C}(X + Y - c)$. This polynomial vanishes on $A \times B$: pairs with $a = b$ are killed by the factor $(X - Y)$, and pairs with $a \neq b$ are killed because $a + b \in C$. The total degree is $|A| + |B| - 2$, matching $d_1 + d_2$ for $d_1 = |A| - 1$, $d_2 = |B| - 1$. The coefficient of $X^{|A|-1} Y^{|B|-1}$ is a difference of binomial coefficients that is nonzero in $\mathbb{Z}_p$ because $|A| < |B|$ and $|C| < p$. [Alon's Combinatorial Nullstellensatz](/theorems/2617) then provides the contradiction. [/proofplan] [step:Encode the assumption as polynomial vanishing on $A \times B$] Suppose for contradiction that $|A \mathbin{\dot{+}} B| \leq |A| + |B| - 3$. Choose a set $C \subseteq \mathbb{Z}_p$ with $A \mathbin{\dot{+}} B \subseteq C$ and $|C| = |A| + |B| - 3$. Define \begin{align*} f(X, Y) = (X - Y) \prod_{c \in C}(X + Y - c) \in \mathbb{Z}_p[X, Y]. \end{align*} For any $(a, b) \in A \times B$: - If $a = b$: the factor $(X - Y)$ vanishes at $(a, b)$, so $f(a, b) = 0$. - If $a \neq b$: then $a + b \in A \mathbin{\dot{+}} B \subseteq C$, so the factor $(X + Y - (a + b))$ appears in the product and vanishes, giving $f(a, b) = 0$. Therefore $f$ vanishes identically on $A \times B$. [guided] The polynomial $f$ is built to detect the restricted sumset. Without the extra factor $(X - Y)$, the product $\prod_{c \in C}(X + Y - c)$ would vanish on $A \times B$ only when $a + b \in C$. But this need not hold when $a = b$ (since $a + b = 2a$ might not be in $C$ -- the restricted sumset excludes diagonal pairs). The factor $(X - Y)$ patches this: it contributes a zero at every diagonal pair $(a, a)$, regardless of whether $2a \in C$. The cost of this extra factor is that it raises $\deg f$ by $1$: from $|C| = |A| + |B| - 3$ to $|C| + 1 = |A| + |B| - 2$. This means the target monomial has degree $|A| + |B| - 2 = (|A| - 1) + (|B| - 1)$, and the coefficient computation becomes more delicate than in the [Cauchy-Davenport](/theorems/2604) proof. [/guided] [/step] [step:Compute the coefficient of $X^{|A|-1} Y^{|B|-1}$ in $f$] Set $a = |A|$, $b = |B|$, and $m = |C| = a + b - 3$. The total degree of $f$ is $1 + m = a + b - 2$. We apply the Nullstellensatz with $S_1 = A$, $S_2 = B$, $d_1 = a - 1$, $d_2 = b - 1$, so $d_1 + d_2 = a + b - 2 = \deg f$. The target monomial is $X^{a-1} Y^{b-1}$. The product $\prod_{c \in C}(X + Y - c)$ is a polynomial of degree $m$ in $X + Y$. By the binomial theorem, the coefficient of $X^j Y^{m-j}$ in $\prod_{c \in C}(X + Y - c)$ is $\binom{m}{j}$ (since the leading homogeneous part is $(X + Y)^m$). To extract the coefficient of $X^{a-1} Y^{b-1}$ in $f = (X - Y) \prod_{c \in C}(X + Y - c)$, we note that the factor $(X - Y)$ contributes: - $X \cdot [\text{coeff of } X^{a-2} Y^{b-1} \text{ in } \prod_{c \in C}(X + Y - c)]$, which gives $\binom{m}{a - 2}$; - $(-Y) \cdot [\text{coeff of } X^{a-1} Y^{b-2} \text{ in } \prod_{c \in C}(X + Y - c)]$, which gives $-\binom{m}{a - 1}$. Therefore the coefficient of $X^{a-1} Y^{b-1}$ in $f$ is \begin{align*} \binom{m}{a - 2} - \binom{m}{a - 1}. \end{align*} [guided] We need to be precise about why the leading homogeneous part suffices. Write $\prod_{c \in C}(X + Y - c) = (X + Y)^m + \text{lower-order terms}$. When we multiply by $(X - Y)$ and look for the monomial $X^{a-1} Y^{b-1}$ of total degree $a + b - 2 = m + 1$, only the top-degree part $(X + Y)^m$ of the product contributes: the lower-order terms have degree at most $m - 1$, and after multiplication by $(X - Y)$ they produce monomials of degree at most $m$, which is less than $m + 1 = a + b - 2$. So the coefficient of $X^{a-1} Y^{b-1}$ in $f$ equals the coefficient of $X^{a-1} Y^{b-1}$ in $(X - Y)(X + Y)^m$. Expanding $(X - Y)(X + Y)^m$: \begin{align*} (X - Y)(X + Y)^m &= X \sum_{j=0}^m \binom{m}{j} X^j Y^{m-j} - Y \sum_{j=0}^m \binom{m}{j} X^j Y^{m-j}. \end{align*} The monomial $X^{a-1} Y^{b-1}$ arises from the first sum when $j = a - 2$ (giving $\binom{m}{a-2}$) and from the second sum when $j = a - 1$ (giving $-\binom{m}{a-1}$). The total coefficient is $\binom{m}{a-2} - \binom{m}{a-1}$. [/guided] [/step] [step:Verify the coefficient is nonzero in $\mathbb{Z}_p$] We must show $\binom{m}{a-2} \neq \binom{m}{a-1}$ in $\mathbb{Z}_p$, where $m = a + b - 3$. Since $a + b \leq p + 2$, we have $m = a + b - 3 \leq p - 1 < p$, so $\binom{m}{k}$ for $0 \leq k \leq m$ is computed in $\mathbb{Z}$ and reduced modulo $p$, with $0 < \binom{m}{k} < p$ for all such $k$ (since $m < p$ implies $\binom{m}{k} \leq \binom{m}{\lfloor m/2 \rfloor} \leq 2^m \leq 2^{p-1}$, and more precisely Lucas' theorem shows $p \nmid \binom{m}{k}$ when $m < p$). The symmetry relation $\binom{m}{k} = \binom{m}{m - k}$ gives $\binom{m}{a-2} = \binom{m}{a-1}$ in $\mathbb{Z}$ if and only if $a - 2 = a - 1$ (impossible) or $a - 2 = m - (a - 1) = b - 2$, i.e., $a = b$. But $a = |A| < |B| = b$ by hypothesis, so $a \neq b$. Since $\binom{m}{a-2} \neq \binom{m}{a-1}$ in $\mathbb{Z}$ and both values lie in $\{1, \ldots, p - 1\}$ (as $m < p$), their difference is a nonzero integer with absolute value at most $p - 1$, hence nonzero modulo $p$. [guided] Why is $|A| < |B|$ essential? The binomial coefficients $\binom{m}{a-2}$ and $\binom{m}{a-1}$ are equal in $\mathbb{Z}$ only when the indices are symmetric around $m/2$: $a - 2 + (a - 1) = m = a + b - 3$ gives $2a - 3 = a + b - 3$, i.e., $a = b$. When $a < b$, this symmetry is broken, so the two coefficients are genuinely different integers. Could they still coincide modulo $p$ despite being different in $\mathbb{Z}$? No: since $m < p$, every binomial coefficient $\binom{m}{k}$ with $0 \leq k \leq m$ is a positive integer less than $p$ (by Lucas' theorem, $\binom{m}{k} \not\equiv 0 \pmod{p}$ when $m < p$, and the maximum value is at most $\binom{p-1}{\lfloor(p-1)/2\rfloor} < 2^{p-1}$). Their difference, being a nonzero integer of absolute value less than $p$, cannot be divisible by $p$. [/guided] [/step] [step:Apply the Nullstellensatz to reach a contradiction] We have $f \in \mathbb{Z}_p[X, Y]$ vanishing on $A \times B$ with $\deg f = |A| + |B| - 2 = d_1 + d_2$ and the coefficient of $X^{d_1} Y^{d_2}$ nonzero. By [Alon's Combinatorial Nullstellensatz](/theorems/2617), $f$ cannot vanish on $A \times B$, a contradiction. Therefore $|A \mathbin{\dot{+}} B| \geq |A| + |B| - 2$. [/step]