On restricted sumsets with bounded degree relations

Abstract

Given two subsets $A,B\subseteq {\mathbb{F}}_p$ and a binary relation $\mathcal{R}\subseteq A\times B$, the restricted sumset of $A,B$ with respect to $\mathcal{R}$ is defined as $A{+}_{\mathcal{R}}B=\{a+b:(a,b)\notin \mathcal{R}\}$. When $\mathcal{R}$ is taken as the equality relation, determining the minimum value of $|A{+}_{\mathcal{R}}B|$ is the famous Erdős--Heilbronn problem, which was solved separately by Dias da Silva, Hamidoune and Alon, Nathanson and Ruzsa. Lev later conjectured that if $A,B\subseteq {\mathbb{F}}_p$ with $|A|+|B|\le p$ and $\mathcal{R}$ is a matching between subsets of $A$ and $B$, then $|A{+}_{\mathcal{R}}B|\ge |A|+|B|-3$. We confirm this conjecture in the case where $|A|+|B|\le (1-\epsilon )p$ for any $\epsilon >0$, provided that $p>p_0$ for some sufficiently large $p_0$ depending only on $\epsilon$. Our proof builds on a recent work by Bollobás, Leader, and Tiba, and a rectifiability argument developed by Green and Ruzsa. Furthermore, our method extends to cases when $\mathcal{R}$ is a degree-bounded relation, either on both sides $A$ and $B$ or solely on the smaller set. In addition, we construct subsets $A\subseteq {\mathbb{F}}_p$ with $|A|=\frac{6p}{11}-O(1)$ such that $|A{+}_{\mathcal{R}}A|=p-3$ for any prime number $p$, where $\mathcal{R}$ is a matching on $A$. This extends an earlier construction by Lev and highlights a distinction between the combinatorial notion of the restricted sumset and the classcial Erdős--Heilbronn problem, where $|A{+}_{\mathcal{R}}A|\ge p$ holds given $\mathcal{R}=\{(a,a):a\in A\}$ is the equality relation on $A$ and $|A|\ge \frac{p+3}{2}$.

14 pages; revised according to referee comments