March 12, 2025
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 \colon (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| \leqslant p\) and \(\mathcal{R}\) is a matching between subsets of \(A\) and \(B\), then \(|A +_{\mathcal{R}} B| \geqslant|A| + |B| - 3\).
We confirm this conjecture in the case where \(|A| + |B| \leqslant(1-\varepsilon)p\) for any \(\varepsilon > 0\), provided that \(p > p_0\) for some sufficiently large \(p_0\) depending only on \(\varepsilon\). 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| \geqslant p\) holds given \(\mathcal{R} = \{(a,a) \colon a \in A\}\) is the equality relation on \(A\) and \(|A| \geqslant\frac{p+3}{2}\).
Keywords: restricted sumsets, generalized Erdős–Heilbronn problem, rectifiability, small subset with large sumset.
Given a prime number \(p\) and two subsets \(A, B \subseteq \mathbb{F}_p\), the sumset \(A+B \coloneq\{a + b \colon a \in A, b \in B\}\) is defined as the collection of all pairwise sums of elements from the Cartesian product \(A \times B\). The classical Cauchy–Davenport theorem states that for any two non-empty subsets \(A, B\) of \(\mathbb{F}_p\), we have \(|A+B| \geqslant\min\{p, |A|+|B|-1\}\). A natural generalization of the Cauchy–Davenport theorem is to exclude a few pairs from \(A \times B\) and consider the sumset formed by the remaining pairs.
In 1964, Erdős and Heilbronn [1] conjectured that if \(A\) is a non-empty subset of \(\mathbb{F}_p\), then \(|A \dot{+} A| \geqslant\min\{p, 2|A|-3\}\), where \(A \dot{+} A \coloneq\{a+b \colon a,b \in A,\, a \neq b\}\). Dias da Silva and Hamidoune [2] confirmed this conjecture using the exterior algebra method in 1994. Later, Alon, Nathanson, and Ruzsa [3] extended the Erdős–Heilbronn conjecture to a non-symmetric setting using the polynomial method, particularly through the Combinatorial Nullstellensatz. Their method applies not only to the restricted sumset of distinct pairs but also to restricted sumsets with any restriction specified by a low-degree polynomial \(P(x,y)\), i.e. \(A +_{\mathcal{R}} B = \{a + b \colon P(a,b) \neq 0\}\). For further details on this approach, see [3]–[7].
In this paper, we investigate the size of the restricted sumset with respect to any degree-bounded, combinatorially defined relation between \(A\) and \(B\). Lev [8] defined the restricted sumset as
Definition 1 (Restricted Sumset). Suppose \(A, B\) are two subsets of \(\mathbb{F}_p\) or \(\mathbb{Z}\), and \(\mathcal{R}\subseteq A \times B\) is a binary relation between \(A\) and \(B\). The restricted sumset* of \(A\) and \(B\) is defined as \[A +_{\mathcal{R}} B \mathrel{\vcenter{:}}=\left\{ a+b \colon a \in A, b \in B, (a,b) \notin \mathcal{R}\right\}.\]*
One should note that \(\mathcal{R}\) consists of the set of forbidden pairs, rather than the set of pairs allowed under the addition operation, which was adopted in some other context. For more reference about research on this kind of restricted sumsets, see [8]–[10], where Lev [8] investigates the minimum size of \(A +_{\mathcal{R}} B\) according to \(|A|, |B|\) and \(|\mathcal{R}|\) for an arbitrary relation \(\mathcal{R}\), and [10] under a notion of \((K,s)\)-regular on \(\mathcal{R}\), which requires the maximum degree of \(\mathcal{R}\) on both sides \(A\) and \(B\) to be at most \(s\), and every element \(c\) has at most \(K\) representations as \(c = a + b\) for \((a,b) \in \mathcal{R}\).
As a special case, when \(\mathcal{R}\) is taken as an injective function from \(B\) to \(A\), i.e. \(\mathcal{R}\) is a matching between subsets of \(A\) and \(B\), Lev [8] proposed the following conjecture.
Conjecture 2 (Lev [8]). Suppose \(p\) is a prime number, \(A, B \subseteq \mathbb{F}_p\), \(|B| \leqslant|A|\), and \(\mathcal{R}\colon B \to A\) is an injective function from \(B\) to \(A\). Then \[|A +_{\mathcal{R}} B| \geqslant \left\{ \begin{array}{cl} |A| + |B| - 3& \quad \text{if } |A| + |B| \leqslant p \\ p-3& \quad \text{if } |A| + |B| = p+1 \\ p-2& \quad \text{if } |A| + |B| \geqslant p+2. \end{array} \right.\]
The second case in the statement is necessary because of an example constructed by Lev [8], which shows that there exists \(A \subseteq \mathbb{F}_p\) and a matching \(\mathcal{R}\) on \(A\) satisfying \(|A| = \frac{p+1}{2}\) and \(|A +_{\mathcal{R}} A| = p-3\). We later give an example (6) with \(A \subseteq \mathbb{F}_p\) that extends this construction, where \(|A| = \frac{6p}{11} - O(1)\) and \(|A +_{\mathcal{R}} A| \leqslant p-3\). Hence, we should be more cautious concerning the restricted sumset in \(|A| + |B| \geqslant p\) regime.
For symmetric restricted sumset, Bollobás, Leader, and Tiba [11] established a deep result on the size of the restricted sumset when replacing one summand of \(A+A\) by a subset \(A' \subseteq A\) of constant size. Our proof is based on a few auxiliary results in the proof of their result.
Theorem 1 ([11]). Let \(\{d(n)\}_{n=1}^{\infty}\) be a sequence of natural numbers with \(d(n) = o(n)\), and let \(\varepsilon>0\). Then there are integers \(c\) and \(n_0\) such that the following holds.
Let \(A\subseteq \mathbb{F}_p\) with \(n_0 \leqslant|A| = n \leqslant(1 - \varepsilon)p/2\), and let \(\mathcal{R}\subseteq A \times A\) have degree at most \(d(n)\). Then there is a set \(A' \subseteq A\) of size at most \(c\), such that \(|A +_{\mathcal{R}} A'|\geqslant 2|A|-1-2d\).
As a corollary, this confirms Lev’s conjecture under the assumption \(A = B\) in \(|A| \leqslant(1-\varepsilon)p/2\) regime.
Corollary 1 ([11]). For each \(\varepsilon> 0\) and integer \(d\) there is an \(n_0\) such that the following holds. Let \(A\) be a subset of \(\mathbb{F}_p\) with \(n_0 \leqslant|A| < (1-\varepsilon)p/2\), and \(\mathcal{R}\subseteq A \times A\) is symmetric and has degree at most \(d\). Then \(|A +_{\mathcal{R}} A| \geqslant 2|A| - 1 - 2d\).
In 4, we generalize this theorem to a non-symmetric setting.
We first prove the following result about restricted sumsets with respect to a bounded degree relation for subsets of \(\mathbb{Z}\). The proof is quite straightforward and not the main focus of this paper. However, since this result closely resembles its counterpart in \(\mathbb{F}_p\), which is the primary focus of our study, we include it here for completeness.
Theorem 2 (\(\mathbb{Z}\) case). Suppose \(\Delta\geqslant 1\) is an integer, \(A, B \subseteq \mathbb{Z}\) satisfy \(|B| \leqslant|A|\), and \(\mathcal{R}\subseteq A \times B\) is a binary relation between \(A\) and \(B\).
(i) If the maximum degree of \(\mathcal{R}\) on \(B\) is at most \(\Delta\), then \[|A +_{\mathcal{R}} B| \geqslant|A| + |B| - 3\Delta.\]
(ii) If the maximum degree of \(\mathcal{R}\) on both \(A\) and \(B\) is at most \(\Delta\), then \[|A +_{\mathcal{R}} B| \geqslant|A| + |B| - 1 - 2\Delta.\]
For the \(\mathbb{F}_p\) case, we have the following result.
Theorem 3 (\(\mathbb{F}_p\) case). For any \(\varepsilon> 0\) and integer \(\Delta\geqslant 1\), there exist constants \(c_\varepsilon> 0\) and an integer \(p_0\), such that the following holds for any prime number \(p\). Suppose \(A, B \subseteq \mathbb{F}_p\) satisfy \(|B| \leqslant|A|\), \(|A| + |B| \leqslant(1-\varepsilon)p\), \(|B| \leqslant c_\varepsilon p\), and \(\mathcal{R}\subseteq A \times B\) is a binary relation between \(A\) and \(B\). Then, provided that \(p > p_0\) or \(|A| \geqslant 10\Delta\), we have
(i) If the maximum degree of \(\mathcal{R}\) on \(B\) is at most \(\Delta\), then \[|A +_{\mathcal{R}} B| \geqslant|A| + |B| - 3\Delta.\]
(ii) If the maximum degree of \(\mathcal{R}\) on both \(A\) and \(B\) is at most \(\Delta\), then \[|A +_{\mathcal{R}} B| \geqslant|A| + |B| - 1 - 2\Delta.\]
Moreover, \(c_\varepsilon\) and \(p_0\) can be chosen as \(c_\varepsilon= \left(1 + \frac{1}{\alpha}\right)^{-1} \left( 8(2\Delta+ 3 + \frac{1}{\alpha}) \right)^{-24(2\Delta+ 3 + \frac{1}{\alpha})^4}\), \(p_0 = 4^{10\Delta}\), where \(\alpha = 2^{-18} \cdot 3.1 \cdot 10^{-1549} \varepsilon\).
The condition \(p > p_0\) for some constant \(p_0\) is more natural and easier to state compared to \(|A| \geqslant 10\Delta\). However, the latter can be particularly useful when \(\mathcal{R}\) is dense, i.e. \(\Delta= \Theta(p)\), as otherwise the requirement \(p > p_0\) may force \(p\) to be exponentially large in terms of \(\Delta\). We therefore impose both conditions here. If either condition holds, the conclusion follows.
When the degree is bounded on both sides, we have the following stronger result. We do not combine 4 with 3(ii) because the dependence of \(\beta, p_0\) on \(\varepsilon, \Delta\) in 4 is more intricate than that the corresponding parameters \(c_\varepsilon\) and \(p_0\) in 3. Determining their explict forms requires a more detailed examination of the references.
Theorem 4 (\(\mathbb{F}_p\) case). For any \(\varepsilon> 0\) there exists \(\beta > 0\) such that for any integer \(\Delta\geqslant 1\), there exists an integer \(p_0\) with the following property: If \(p\) is a prime number, \(A, B \subseteq \mathbb{F}_p\) satisfy \(|A| + |B| \leqslant(1-\varepsilon)p\), and \(\mathcal{R}\subseteq A \times B\) is a binary relation between \(A\) and \(B\) with maximum degree (on both sides) at most \(\Delta\), then provided that \(|A| \geqslant\beta\Delta\) or \(p > p_0\), we have \[|A +_{\mathcal{R}} B| \geqslant|A| + |B| - 1 - 2\Delta.\]
Moreover, \(p_0\) can be chosen as \(p_0 = \exp(O_\varepsilon(\Delta))\) which we shall determine in the proof.
It is noteworthy that Bollobás, Leader, and Tiba [11] proved a related theorem, showing that whenever \(|A| + |B| \leqslant(1-\varepsilon)p\) and \(|B|\) is sufficiently small relative to \(|A|\), then the optimal lower bound for the sumset, as given by the Cauchy–Davenport theorem, can be attained using just three elements from \(B\), i.e. \(|A + \{b_1, b_2, b_3\}| \geqslant|A| + |B| - 1\) for some \(b_1, b_2, b_3 \in B\).
A direct application of this theorem could give us a weaker bound \(|A +_{\mathcal{R}} B| \geqslant|A| + |B| - 3\Delta- 1\) in 3(i). Thus, our main objective is to improve the \(O(\Delta)\) term in this inequality, which turns out to be rather delicate. Apart from harnessing some of the ideas from their proof, we also utilise a rectifiability argument given by Green and Ruzsa [12] to deal with the case when the size of \(A\) and \(B\) are comparable.
As a corollary, we confirm 2 proposed by Lev whenever \(|A| + |B| \leqslant(1-\varepsilon)p\) for sufficiently large \(p\).
Corollary 2. (i) For any \(\varepsilon> 0\), let \(c_\varepsilon= \left( \frac{\varepsilon}{10^{1600}} \right)^{\frac{10^{6400}}{\varepsilon^4}}\). Suppose \(p\) is a prime number, \(A, B \subseteq \mathbb{F}_p\) satisfy \(|A| + |B| \leqslant(1-\varepsilon)p\), \(|B| \leqslant|A|\), \(|B| \leqslant c_\varepsilon p\), and \(f \colon B \to A\) is an arbitrary function. We have \[\Big| \big\{ a+b \colon a \in A, b \in B, a \neq f(b) \big\} \Big| \geqslant|A| + |B| - 3.\]
(ii) For any \(\varepsilon> 0\), there exists \(p_0\) such that for any prime number \(p > p_0\), \(A, B \subseteq \mathbb{F}_p\) satisfy \(|A| + |B| \leqslant(1-\varepsilon)p\), and \(\mathcal{R}\) is a matching between some elements of \(A\) and \(B\). We have \[\Big| \big\{ a+b \colon a \in A, b \in B, (a,b) \notin \mathcal{R}\big\} \Big| \geqslant|A| + |B| - 3.\]
A natural question is how tight 3 is. 3(ii) is already tight even in \(\mathbb{Z}\), and the bound in (i) is weaker than (ii) whenever \(\Delta\geqslant 2\). One would hope that we could prove \(|A +_{\mathcal{R}} B| \geqslant|A| + |B| -1 - 2\Delta\) for any relation \(\mathcal{R}\) with bounded degree \(\Delta\) from the smaller side \(B\) under some reasonable assumption. However, the following example shows that this is too optimistic, even in the case where \(|A| = |B|\) and \(A, B \subseteq \mathbb{Z}\).
Theorem 5. Given integers \(\Delta\geqslant 1\) and \(n \geqslant 2\Delta\). There exist \(A, B \subseteq \mathbb{Z}\), \(|A| = |B| = n\) and a relation \(\mathcal{R}\subseteq A \times B\) with bounded degree \(\Delta\) from \(B\) such that \[|A +_{\mathcal{R}} B| = |A| + |B| - 1 - \left\lfloor \frac{5\Delta}{2} \right\rfloor.\]
We believe the above theorem is tight, which suggests 2(i) could potentially be strengthened to \(|A +_{\mathcal{R}} B| \geqslant|A| + |B| - 1 - \left\lfloor \frac{5\Delta}{2} \right\rfloor\). It is worth noting that any improvement of the \(-3\Delta\) term in 2(i) would directly lead to a strengthening of 3(i), with the same parameters \(c_\varepsilon, p_0\) unchanged. The bottleneck of the current method for potential improvement of 3(i) lies in the case \(A, B \subseteq \mathbb{Z}\) after applying the rectifiability argument. The remaining part of the proof would remain valid without any modification.
Conjecture 3. Suppose \(\Delta\geqslant 1\) is an integer, \(A, B \subseteq \mathbb{Z}\) satisfies \(|B| \leqslant|A|\), and \(\mathcal{R}\subseteq A \times B\) is a binary relation between \(A\) and \(B\). If the maximum degree of \(\mathcal{R}\) on \(B\) is at most \(\Delta\), we have \[|A +_{\mathcal{R}} B| \geqslant|A| + |B| - 1 - \left\lfloor \frac{5\Delta}{2} \right\rfloor.\]
The second part of this paper presents several constructions, two of which serve the main purpose. 3(ii) explains why the additional requirement \(|B| = O_\varepsilon(p)\) is necessary for 2(i) to hold; 6(iii) demonstrates why a stronger assumption \(|A| + |B| \geqslant(1+\delta)p\) is required for 2 to hold in order to prove \(|A +_{\mathcal{R}} B| \geqslant p-2\), even in the case where \(|B| \leqslant\varepsilon p\).
6(i) restates a construction originally given by Lev [8]. We reformulated it here for consistency with the notation and style used throughout this paper. 6(ii) was inspired from the same paper.
Theorem 6. Suppose \(p\) is a prime number.
(i) For any integer \(k \geqslant 1\) and \(1 \leqslant\ell \leqslant\lfloor \frac{p-k-1}{2k-1} \rfloor\), there exist subsets \(A, B \subseteq \mathbb{F}_p\) and a function \(R \colon B \to A\) such that \(|A| = p - (k-1) \ell - k + 1\), \(|B| = k\ell + 2\) and \(|A +_{\mathcal{R}} B| = p-k\).
(ii) For any prime number \(p\), there exists a subset \(A \subseteq \mathbb{F}_p\) and a symmetric relation \(\mathcal{R}\subseteq A \times A\) with maximum degree \(1\), such that \(|A| = 6 \lfloor \frac{p}{11} \rfloor - 3\) and \(|A +_{\mathcal{R}} A| = p-3\).
(iii) For any \(\varepsilon> 0\), there exists \(\delta > 0\) such that for any sufficiently large prime number \(p\), there exist \(A, B \subseteq \mathbb{F}_p\) with \(|A| + |B| > (1+\delta)p - O(1)\), \(|B| \leqslant\varepsilon p\), and a relation \(\mathcal{R}\subseteq A \times B\) with maximum degree \(1\), such that \(|A +_{\mathcal{R}} B| = p-3\).
Plugging \(\ell = \lfloor \frac{p-k-1}{2k-1} \rfloor\) and \(\ell = 1\) into 6(i), we have the following.
Corollary 3. Suppose \(p\) is a prime number.
(i) For any integer \(k \geqslant 1\), there exist subsets \(A, B \subseteq \mathbb{F}_p\) and a function \(R \colon B \to A\) such that \(|A| = p - (k-1) \lfloor \frac{p-k-1}{2k-1} \rfloor - k + 1\), \(|B| = k \lfloor \frac{p-k-1}{2k-1} \rfloor + 2\) and \(|A +_{\mathcal{R}} B| = p-k\).
(ii) For any \(\varepsilon> 0\), there exist \(A, B \subseteq \mathbb{F}_p\) and a function \(R \colon B \to A\) such that \(|A| = (1-2\varepsilon)p + O(1)\), \(|B| = \varepsilon p + O(1)\) and \(|A +_{\mathcal{R}} B| = |A| + |B| - 4\), where the value of the \(O(1)\) term within the expressions of \(|A|\) and \(|B|\) are smaller than \(3\).
Thus, for potential extensions of 2(i), in the regime where \(|A| + |B| \geqslant p\), it is necessary to assume at least \(|A| + |B| \geqslant p-k+\lfloor \frac{p-k-1}{2k-1} \rfloor + 4 > \frac{2k}{2k-1} p - k + 2\) in order to establish \(|A +_{\mathcal{R}} B| \geqslant p-k+1\). In the regime \(|A| + |B| \leqslant(1-\varepsilon)p\), an additional assumption \(|B| \leqslant\varepsilon p\) is required.
Combining 2(i) and the constructions above, we propose the following conjecture. The main obstacle in proving this conjecture lies in the fact that, in 3, the parameter \(c_\varepsilon\) is not linear in \(\varepsilon\). So it remains unclear how to prove \(|A +_{\mathcal{R}} B| \geqslant|A| + |B| - 3\) under assumptions such as \(|A| + c|B| < p\) for any constant \(c\).
Conjecture 4. Suppose \(p\) is a prime number, \(A, B \subseteq \mathbb{F}_p\) with \(|B| \leqslant|A|\). Let \(\mathcal{R}\colon B \to A\) be an arbitrary function from \(B\) to \(A\). If \(|A| + 2|B| \leqslant p\), then \(|A +_{\mathcal{R}} B| \geqslant|A| + |B| - 3\).
In the case where both sides have bounded degree \(1\), 6(ii) and (iii) indicate that extra care is required when extending 2 beyond the \(|A| + |B| \leqslant p\) regime. In particular, a stronger assumption \(|A| + |B| \geqslant(1+\delta)p\) is necessary even in the case \(|B| \leqslant\varepsilon p\) in order to prove \(|A +_{\mathcal{R}} B| \geqslant p-2\).
At the end of this paper, we examine the tightness of the construction in 3(i). Specifically, we investigate the minimum possible value of \(|A| + |B|\) required to ensure that \(|A +_{\mathcal{R}} B| \geqslant p - k + 1\). We have the following result, with a proof that follows from a straightforward counting argument.
Theorem 7. Suppose \(p\) is a prime number and \(k \geqslant 1\) is an integer. For any subsets \(A, B \subseteq \mathbb{F}_p\), let \(\mathcal{R}\colon B \to A\) be an arbitrary function. If \(|A| + |B| \geqslant\lfloor \frac{2kp}{2k-1} \rfloor + 1\), then \(|A +_{\mathcal{R}} B| \geqslant p-k+1\).
This shows that the construction in 3(i) is tight up to an additive term of \(k-2\) in \(|A| + |B|\).
Throughout this paper, we assume that \(p\) is a prime number, \(A, B\) are finite subsets of either \(\mathbb{Z}\) or \(\mathbb{F}_p\), as will be clarified in context. Additionally, we consider \(\mathcal{R}\subseteq A \times B\) to be a binary relation between \(A\) and \(B\).
We say that \(\mathcal{R}\) has bounded degree \(\Delta\) if, when viewed as a bipartite graph with parts \((A, B)\), its maximum degree is at most \(\Delta\). Similarly, we say that \(\mathcal{R}\) has bounded degree \(\Delta\) on \(B\) if the maximum degree among elements in \(B\) is at most \(\Delta\).
In 3, we prove 2, 3 and 4. Then, in 4, we establish 5, 6, and 7, along with additional discussions.
We first state the celebrated Plünnecke–Ruzsa theorem here.
Theorem 8 (Plünnecke–Ruzsa [13]–[15]). Let \(A, B\) be finite non-empty subsets of an abelian group, and suppose that \(|A+B| \leqslant K |A|\). Then, for all non-negative integers \(m, n\) we have \(|mB - nB| \leqslant K^{m+n} |A|\), where \(mB\) denote the \(m\)-fold sumset \(\underbrace{B + \cdots + B}_{m}\).
We also need the notion of rectifiability.
Definition 5 (Rectifiability). Suppose \(p\) is a prime number and \(k \geqslant 2\) is an integer. A subset \(A \subseteq \mathbb{F}_p\) is called rectifiable of order \(k\)* if there exists an injection \(f \colon A \to \mathbb{Z}\) such that, for any \(a_1, \cdots a_k, a_1', \cdots a_k' \in A\), \(a_1 + \cdots + a_k = a_1' + \cdots + a_k'\) if and only if \(f(a_1) + \cdots + f(a_k) = f(a_1') + \cdots + f(a_k')\). When \(k = 2\), we simply say that \(A\) is rectifiable.*
A pair of subsets \((A,B)\) of \(\mathbb{F}_p\) is called rectifiable, if there exist injections \(f \colon A \to \mathbb{Z}\) and \(g \colon B \to \mathbb{Z}\) such that, for any \(a, a' \in A\) and \(b, b' \in B\), \(a + b = a' + b'\) if and only if \(f(a) + g(b) = f(a') + g(b')\).
We use the following results from [11]. We write out the parameters \(\varepsilon, \alpha\) explicitly in 9 and modify the statement of 10 in order to adapt our usage. The proof of 10 can be found in 6.
Theorem 9 ([11]). For all \(\varepsilon, \gamma>0\) and \(t \geqslant 2^{10}\) there exist \(\delta, \alpha>0\) such that the following holds. Let \(A\) and \(B\) be subsets of \(\mathbb{F}_p\). Suppose that \[2\leqslant|B| \leqslant\alpha |A| \text{ and } |A|+|B|\leqslant(1-\varepsilon)p\] and \[\max_{b_1, b_2 \in B}|A+\{b_1, b_2\}| \leqslant|A|+|B|-1+\delta |B|.\]
Then there exist arithmetic progressions \(P\) and \(Q\) with the same common difference, and sizes at least \(t|B|\) and at most \(\lfloor(1+\gamma)|B|\rfloor\) respectively, such that \(|A \cap P| \leqslant\gamma |B|\) and \(B \subseteq Q\).
Moreover, \(\delta, \alpha\) can be chosen as \(\delta = \min(2^{-13} \cdot 3.1 \cdot 10^{-1549}, 2^{-3} \gamma)\), \(\alpha = \varepsilon\cdot \min(2^{-5} \delta, 2^{-5}t^{-2} \gamma)\).
Theorem 10 ([11]). Let \(A\) and \(B\) be subsets of \(\mathbb{F}_p\), and let \(r \geqslant 0\) be an integer. Suppose that \(I=[p_l, p_r]\) and \(J=[q_l, q_r]\) are intervals of \(\mathbb{F}_p\) satisfying \[|A| \geqslant 8r ,\;2\leqslant|B| \leqslant\min(|A|-2r, p/2^{11}) ,\;|I|=(2^{10}+2r)|B| \;\text{and} \;|J| \leqslant(1+2^{-10})|B|\] and \[|A \cap I| \leqslant 2^{-10} |B| \;\text{and} \;\{q_l,q_r\} \subseteq B \subseteq J.\]
Then either there exist \(b_1, b_2, b_3 \in B\) such that \(|A+\{b_1, b_2, b_3\}|\geqslant|A|+|B|-1+r\) or the pair \((A,B)\) is rectifiable.
Theorem 11 ([11]). For every \(\varepsilon> 0\), there exists \(\delta > 0\) such that for every \(\alpha > 0\), there is a value \(c\) for which the following holds. Let \(A\) and \(B\) be subsets of \(\mathbb{F}_p\). Suppose that \[2 \leqslant\min(|A|,|B|) ,\;\alpha |B| \leqslant|A| \leqslant\alpha^{-1} |B| \;\text{and} \;|A|+|B| \leqslant(1-\varepsilon)p\] and \[\max_{B'\in B^{(c)}} |A+B'| = |A|+|B|-1+r \leqslant|A|+|B|-1+ \delta \min(|A|,|B|)\] for some integer \(r\).
Then \(B\) is contained in an arithmetic progression of size \(|B|+r\). Here \(B^{(c)}\) stands for the set of all subsets of \(B\) of size at most \(c\).
Green and Ruzsa proved the following theorem, which states that if both the doubling constant and the size of a subset \(A\) of \(\mathbb{F}_p\) are small, then \(A\) is rectifiable.
Theorem 12 ([12]). Suppose \(p\) is a prime number, \(k \geqslant 2\) is an integer, and \(A \subseteq \mathbb{F}_p\) of size \(\alpha p\). If \(|A+A| \leqslant K|A|\) and \(\alpha \leqslant(16kK)^{-12K^2}\), then \(A\) is rectifiable of order \(k\).
Proof of 2. (i) Since \(|A| \geqslant|B|\) and the degree of each element in \(B\) is at most \(\Delta\), there exists \(a \in A\) such that the degree \(d(a) \leqslant\Delta\).
Let \(A = \{a_1, \cdots, a_m\}\) and \(B = \{b_1, \cdots, b_n\}\), where \(a_1 < a_2 < \cdots < a_m\) and \(b_1 < b_2 < \cdots < b_n\).
If \(d(a_1) \leqslant\Delta\), consider the following \(|A| + |B| - 1\) elements: \[a_1 + b_1, a_1 + b_2,\cdots,a_1 + b_n,\;a_2 + b_n,\cdots \;,a_m + b_n,\]
At most \(2\Delta\) of these elements are missing from \(A +_{\mathcal{R}} B\), so we obtain \(|A +_{\mathcal{R}} B| \geqslant|A| + |B| - 1 - 2\Delta\).
If \(d(a_1) > \Delta\), then by the averaging argument, there exists \(a_i \in A\) such that \(d(a_i) < \Delta\). Consider the following \(|A|+|B|-1\) elements: \[a_1+b_1, a_2+b_1, \cdots, a_i+b_1,\;a_i+b_2, \cdots, a_i+b_n,\;a_{i+1}+b_n, \cdots, a_m+b_n.\]
At most \(d(b_1) + d(a_i) + d(b_n) \leqslant 3\Delta- 1\) of these elements are missing from \(A +_{\mathcal{R}} B\). Thus, \(|A +_{\mathcal{R}} B| \geqslant|A + B| - (3\Delta- 1) \geqslant|A| + |B| - 3\Delta\).
(ii) The argument follows similarly to the first case in (i). ◻
Remark 6. There is a theorem from [11] states that if \(A\) and \(B\) are two finite non-empty subsets of \(\mathbb{Z}\) with \(|A| \geqslant|B|\), then there exist elements \(b_1,b_2,b_3 \in B\) such that \(|A+\{b_1,b_2,b_3\}| \geqslant|A|+|B|-1\).
2(i) could also be derived with a minor modification in the proof of this theorem. However, for our specific purpose, the proof presented here is more direct and less involved.
Remark 7. The bound \(|A| + |B| - 1 - 2\Delta\) in 2(ii) is tight. Consider the construction where \(A = B = [n]\) and define \(\mathcal{R}= \left( [\Delta] \times [\Delta] \right) \cup \left( \left\{ n-\Delta+1, \cdots, n \right\} \times \left\{ n-\Delta+1, \cdots, n \right\} \right)\).
In this case, \(A+B = \{ \Delta+2, \Delta+3, \cdots, 2n-\Delta\}\), giving \(|A + B| = 2n - 1 - 2\Delta\), which matches our bound exactly.
We need the following lemma showing any sufficiently small subset of \(\mathbb{F}_p\) is rectifiable.
Lemma 1. For any integer \(n > 0\), if \(p\) is a prime number satisfying \(p > 4^n\), then any subset of \(\mathbb{F}_p\) of size at most \(n\) is rectifiable.
Proof. Let \(X \subseteq \mathbb{F}_p\) be a subset of size at most \(n\), We aim to show that there exists some \(t \in \mathbb{F}_p^\times\) such that all elements in \(tX\) have residues within the interval \([-\frac{p}{4}, \frac{p}{4}]\). This ensures that if \(a+b \equiv c+d \pmod{p}\), then the equality holds in \(\mathbb{Z}\) as well, proving rectifiability.
Consider the set of \(p\) of vectors in \(\{0,1,\cdots, p-1\}^{|X|}\), where the \(i\)-th vector is given by \((ix_1 \!\!\!\mod{p},\, ix_2 \!\!\!\mod{p},\, \cdots,\, ix_n \!\!\!\mod{p})\). Since \(p > 4^n\), the pigeonhole principle guarantees that there exist distinct indices \(i, j\) such that \[(ix_1 \mod{p},\, ix_2 \mod{p},\, \cdots,\, ix_n \mod{p}) - (jx_1 \mod{p},\, jx_2 \mod{p},\, \cdots,\, jx_n \mod{p}) \in \left[-\frac{p}{4}, \frac{p}{4}\right]^{|X|}.\]
Setting \(t = i - j\), we conclude that the function \(f \colon x \mapsto \overline{tx}\) is a rectifying map for \(A\), where \(\overline{x}\) denotes the least absolute residue of \(x\) modulo \(p\). ◻
Let \(\alpha\) be the constant given in 9, whose explicit value will be determined later. The proof of 3 is divided into two cases: If \(|B| \geqslant\alpha |A|\), we establish 3 using a rectifiability argument due to Green and Ruzsa [12]. If \(|B| < \alpha |A|\), we apply a modified technique developed by Bollobás, Leader, and Tiba [11].
Proof of 3. Let \(\alpha = 2^{-18} \cdot 3.1 \cdot 10^{-1549} \varepsilon\) and take \(c_\varepsilon= (1 + \frac{1}{\alpha})^{-1} \left( 8(2\Delta+ 3 + \frac{1}{\alpha}) \right)^{-24(2\Delta+ 3 + \frac{1}{\alpha})^4}\), \(p_0 = 4^{10\Delta}\). We will show that 3 holds for \(c_\varepsilon\) and \(p_0\).
We prove (i) and (ii) simultaneously by contradiction. Suppose that the conclusion does not hold, i.e. \(|A +_{\mathcal{R}} B| < |A| + |B| -1 - 2\Delta\).
Case 1: \(|B| \geqslant\alpha |A|\).
We aim to derive a contradiction by finding a rectifying map that lifts \(A \cup B\) to \(\mathbb{Z}\), allowing us to apply 2.
Since each element in \(B\) is connected to at most \(\Delta\) elements in \(A\) with respect to \(\mathcal{R}\), we have \[|A+B| \leqslant|A +_{\mathcal{R}} B| + \Delta|B| < |A| + |B| - 1 - 2\Delta+ \Delta|B| < \min \left\{ (\Delta+2)|A| , (\Delta+ 1 + \frac{1}{\alpha})|B| \right\}.\]
By Plünneke–Ruzsa’s inequality, it follows that \[|A+A| \leqslant(\Delta+1 + \frac{1}{\alpha})^2 |B|, \quad |B+B| \leqslant(\Delta+2)^2 |A|.\]
Thus, \[\begin{align} | (A \cup B) + (A \cup B) | \leqslant|A+A| + |B+B| + |A+B| &\leqslant(\Delta+1 + \frac{1}{\alpha})^2 |B| + (\Delta+2)^2 |A| + (\Delta+2)|A| \\ &\leqslant(2\Delta+ 3 + \frac{1}{\alpha})^2 |A| \\ &\leqslant(2\Delta+ 3 + \frac{1}{\alpha})^2 |A \cup B|. \end{align}\]
Since \(\alpha |A| \leqslant|B|\), we have \[|A \cup B| \leqslant(1 + \frac{1}{\alpha}) |B| \leqslant(1 + \frac{1}{\alpha}) c_\varepsilon p = \left( 8(2\Delta+ 3 + \frac{1}{\alpha}) \right)^{-24(2\Delta+ 3 + \frac{1}{\alpha})^4}p.\]
By 12, \(A \cup B\) is rectifiable.
Let \(f \colon A \cup B \to \mathbb{Z}\) be a rectifying map. We lift the relation \(\mathcal{R}\subseteq A \times B\) to \(\widetilde{\mathcal{R}} \subseteq f(A) \times f(B)\) along \(f\). Then we have \(|A +_{\mathcal{R}} B| = |f(A) +_{\widetilde{\mathcal{R}}} f(B)|\). Applying 2 we get the desired result, thus completing this case.
Case 2: \(|B| < \alpha |A|\).
If \(|B| = 1\), the result is trivial. Assume \(|B| \geqslant 2\). If there exist \(b_1, b_2 \in B\) such that \(|A + \{b_1, b_2\}| \geqslant|A| + |B| - 1\), then, by degree boundedness, we have \(|A +_{\mathcal{R}} B| \geqslant|A| + |B| -1 - 2\Delta\). Setting2 \(\gamma = 2^{-10}\) and \(t = 2^{10} + 2\Delta\) in 9, we obtain arithmetic progressions \(P\) and \(Q\) with the same common difference satisfying \[|P| \geqslant(2^{10} + 2\Delta)|B|, \quad |Q| \leqslant\lfloor (1+2^{-10})|B| \rfloor, \quad |A \cap P| \leqslant 2^{-10} |B|,\quad \text{and} \quad B \subseteq Q.\]
By rescaling \(A, B\) and shrinking \(Q\) if necessary, we may assume the common difference of \(P\) and \(Q\) is \(1\), and the endpoints of \(Q\) belonging to \(B\).
If \(|A| < 8\Delta\), then \(|A \cup B| < (1 + \alpha)|A| < 10\Delta\). Furthermore, since the second assumption \(p > p_0\) holds in this case, by 1, we know that \(A \cup B\) is rectifiable. This allows us to apply 2 and conclude the proof.
If \(|A| \geqslant 8\Delta\), by 10, we conclude that either there exist \(b_1, b_2, b_3 \in B\) such that \(|A + \{b_1, b_2, b_3\}| \geqslant|A| + |B| - 1 + \Delta\), or \((A, B)\) is a rectifiable pair. In the first case, we have \(|A +_{\mathcal{R}} B| \geqslant|A +_{\mathcal{R}} \{b_1, b_2, b_3\}| \geqslant|A| + |B| - 1 - 2\Delta\). In the latter case, applying again 2 yields the desire result, completing the proof. ◻
Proof of 4. Assume without loss of generality that \(|B| \leqslant|A|\). Define \(\alpha = 2^{-18} \cdot 3.1 \cdot 10^{-1549} \varepsilon\). The case where \(|B| < \alpha |A|\) has already been addressed in the proof of 3, so we may assume that \(|B| \geqslant\alpha |A|\).
Let \(c\) and \(\delta\) be the constants given by 11 for parameters \(\varepsilon\) and \(\alpha\). Without loss of generality, assume \(\delta < 1\). Define \(r = c\Delta\) and set \(\beta = \frac{c}{\delta \alpha}\), \(p_0 = 4^{2\beta\Delta}\). Now, assume either \(|A| \geqslant\beta\Delta\) or \(p > p_0\).
If \(|A| < \beta\Delta\), we have \(p > p_0 = 4^{2\beta\Delta}\) and \(|A \cup B| \leqslant|A| + |B| \leqslant 2|A| < 2\beta\Delta\). Hence, by 1, \(A \cup B\) is rectifiable. Then apply 2, we get the desired result.
Now assume that \(|A| \geqslant\beta\Delta\). In this case, we have \(r \leqslant\delta \cdot \min (|A|, |B|) = \delta |B|\), since otherwise we would have \[|A| \leqslant\frac{1}{\alpha} |B| < \frac{r}{\delta \alpha} = \frac{c\Delta}{\delta \alpha} = \beta\Delta,\] a contradiction.
Besides, since \(p \geqslant|A|\), we have \[\label{eqn:eps95p} \varepsilon p \geqslant\varepsilon|A| \geqslant\varepsilon\beta\Delta= \frac{\varepsilon c\Delta}{\delta\alpha} > (3c+1)\Delta= 3r + \Delta.\tag{1}\]
Let \(A^{(c)}\) denote the set of all subsets of \(A\) of size at most \(c\). We may further assume that \[\max_{A'\in A^{(c)}}|A'+B| \leqslant|A|+|B|-1+r,\] since otherwise, we would have \[\begin{align} \max_{A' \in A^{(c)}}|A' +_{\mathcal{R}} B| &\geqslant\max_{A' \in A^{(c)}} |A' + B| - c\Delta\geqslant|A| + |B| - 1 + r - c\Delta\\ &= |A| + |B| - 1 \\ &> |A| + |B| - 1 - 2\Delta, \end{align}\] which would directly lead to the desired result.
Thus, the assumptions3 of 11 hold, implying that \(A\) is contained in an arithmetic progression \(I\) of size \(|A| + r\). By multiplying an element from \(\mathbb{F}_p^\times\), we may assume \(I\) is an interval.
If there exist two elements \(b_1, b_2 \in B\) such that the distance between them (i.e., \(\min(b_1 - b_2 \mod{p},\, b_2 - b_1 \mod{p})\)) is at least \(|B| + r\), then we have \[|A + \{b_1, b_2\}| \geqslant\min (|I| + |B| + r - 2r, 2|A|) \geqslant|A| + |B|.\]
Thus, \[|A +_{\mathcal{R}} B| \geqslant|A +_{\mathcal{R}} \{b_1, b_2\}| \geqslant|A| + |B| - 2\Delta.\]
If there is no such pair, suppose \(b_1, b_2 \in B\) be the elements with the maximum distance among elements of \(B\), and let \(J\) be the minor arc between them (i.e., the interval ending at \(b_1\) and \(b_2\) with size smaller than \(\frac{p}{2}\)).
If \(B \subseteq J\), then \(B\) is contained in an interval of length at most \[|J| \leqslant|B| + r - 1 < p - |A| - r = p - |I|,\] where the second inequality follows from \(|A| + |B| \leqslant(1-\varepsilon)p\) and (1 ). By translating \(I\) and \(J\), we may assume that both intervals start from \(0\). In this case, the sum of the maximum elements of \(A\) and \(B\) is smaller than \(p\). Therefore, \((A, B)\) forms a rectifiable pair.
If \(B \nsubseteq J\), let \(b_3 \in B \setminus J\). By the maximality of the distance between \(b_1\) and \(b_2\), the minor arcs between \(b_1 b_3\) and \(b_2 b_3\) are not contained in \(J\). Hence, the union of the minor arcs between \(b_1b_2\), \(b_2b_3\), and \(b_1b_3\) covers all of \(\mathbb{F}_p\), and the length of each minor arc is at most \(|B| + r \leqslant|A| + r\). This implies that \(I + \{b_1, b_2, b_3\} = \mathbb{F}_p\). Therefore, \[\begin{align} |A +_{\mathcal{R}} B| &\geqslant|A +_{\mathcal{R}} \{b_1, b_2, b_3\}| \geqslant|I + \{b_1, b_2, b_3\}| - 3r - 3\Delta\\ &\geqslant|\mathbb{F}_p| - 3r - 3\Delta= p-3r - 3\Delta\\ &\geqslant|A| + |B| - 1 - 2\Delta, \end{align}\] where the last inequality again follows from \(|A| + |B| \leqslant(1-\varepsilon)p\) and (1 ). ◻
We prove 5 first. Recall that in proving 5, we need to construct two subsets \(A, B \subseteq \mathbb{Z}\), both of size \(n\), along with a relation \(\mathcal{R}\) of bounded degree \(\Delta\) on \(B\), such that \(|A +_{\mathcal{R}} B| = |A| + |B| - 1 - \left\lfloor \frac{5\Delta}{2} \right\rfloor\).
Proof of 5. Let \(r = \lfloor \frac{\Delta}{2} \rfloor\). Define \[A = \{1,2,\cdots, n-\Delta, n-\Delta+r+1, \cdots, n+r\},\quad B = \{1,2,\cdots, n\}.\]
Then \(|A| = |B| = n\), and \(A + B = \{2, 3, \cdots, 2n+r\}\). Define \[C \coloneq\{n-\Delta+1, \cdots, n-\Delta+r\} + \{1,n\} = \{n-\Delta+2, \cdots, n-\Delta+r+1\} \cup \{2n-\Delta+1, \cdots, 2n-\Delta+r\},\] \[D \coloneq\{2,\cdots,\Delta+1\} \cup \{2n+r-\Delta+1, \cdots 2n+r\}.\]
Then \(C, D\) are disjoint subsets of \(A+B\), and for any \(b \in B\) we have \(|(A + b) \cap C| + |(A + b) \cap D| \leqslant\Delta\). We associate each \(b\) with those \(a \in A\) such that \(a + b \in C \cup D\) in \(\mathcal{R}\). Then each element in \(B\) connects with at most \(\Delta\) elements in \(A\), and \[|A +_{\mathcal{R}} B| = |(A+B) \setminus (C \cup D)| = (2n+r-1) - (2r + 2\Delta) = 2n-1-\left\lfloor \frac{5\Delta}{2} \right\rfloor.\] ◻
The idea behind this construction is to remove \(r\) additional elements from the trivial construction, which achieves \(|A +_{\mathcal{R}} B| = |A| + |B| - 1 - 2\Delta\) by taking \(A\) and \(B\) as two intervals and deleting \(\Delta\) elements near both endpoints of \(A+B\).
Let \(r\) be an arbitrary integer for now. The bottleneck of this construction is that there is a translation \(A + b\) containing \(C\), which consists of the union of two intervals \(C_1 \cup C_2\) with total size \(2r\). This forces us to impose the condition \(r \leqslant\lfloor \frac{\Delta}{2} \rfloor\).
One may attempt to improve this by removing \(r\) elements evenly across \(A\) rather than a contiguous interval. If we do this, each translation of \(A\) would cover at most \(r+1\) deleted elements. This seems to be a wiser approach since we can take \(r = \Delta- 1\), yielding \(|A| = |B| = n\) and \(|A +_{\mathcal{R}} B| = 2n-3\Delta\). However, at this point, we would fail to remove \(\Delta\) elements around the the endpoints of \(A + B\) from \(A +_{\mathcal{R}} B\). This explains why we have to remove an interval and why \(|A +_{\mathcal{R}} B| = |A| + |B| - 1 - \left\lfloor \frac{5\Delta}{2} \right\rfloor\) is optimal concerning this idea.
We believe this construction is tight. A potential proof approach is to apply stability results for \(|A + B| \geqslant|A| + |B| - 1\) to first establish that \(A\) and \(B\) look like intervals. Next, we analyze \(|A + \{b_{\min}, b_{\max}\}|\) which should approximately as large as \(|A| + |B|\). Then we study the translations \(A + b\) with \(b\) is near \(b_{\min}, b_{\max}\) and where \(b\) is an appropriately chosen interior element from \(B\) respectively.
We now prove 6(i).
Proof of 6(i). Let \[A = \{0, k, 2k, \cdots, \ell k, (\ell+1)k, (\ell+1)k+1, \cdots, p-1\},\;B = \{0, -1, -2, \cdots, -(\ell k + 1)\}.\]
Then we have \(|A| = p - (\ell+1)k + \ell + 1 = p - (k-1)\ell - k + 1\) and \(|B| = \ell k + 2\).
Denote \(C = \{0,1, \cdots, k-1\}\). For each \(b \in B\), we have \(|(A + b) \cap C| = 1\). Hence, there is a way to associate each element in \(B\) with an element \(a \in A\) when constructing \(\mathcal{R}\) so that \((A +_{\mathcal{R}} B) \cap C = \varnothing\). This implies \(|A +_{\mathcal{R}} B| \leqslant|\mathbb{F}_p\setminus C| = p-k\). ◻
Although this construction is quite simple, I would like to briefly explain the underlying idea. The key insight is to first consider the avoiding set \(\mathcal{F}\coloneq\mathbb{F}_p\setminus (A +_{\mathcal{R}} B)\). Given \(A\) and \(\mathcal{F}\), we know that \(B\) must be a subset of \(\{b \colon|(\mathcal{F}- b) \cap A| \leqslant 1\}\). For optimality, we may take \(B\) to be the entire set. This reduces the problem to the following: Given the sizes of \(A\) and \(\mathcal{F}\), determine the maximum size of \(\{b \colon|(\mathcal{F}- b) \cap A| \leqslant 1\}\).
Suppose \(k = |\mathcal{F}|\), and let \(r_i\) denote the number of translations of \(\mathcal{F}\) such that \(|(\mathcal{F}+ x) \cap A| = i\). Then, we have \[\label{eqn:sum95of95r} r_0 + r_1 + \cdots + r_k = p,\tag{2}\] and \[\begin{align} \label{eqn:weighted95sum95of95r} r_1 + 2r_2 + \cdots + kr_k = k|A|. \end{align}\tag{3}\]
Moreover, we know that \(|B| = r_0 + r_1\).
Let us examine the case where \(k = 3\). Consider an arbitrary subset \(A \subseteq \mathbb{F}_p\) of size approximately \(\frac{p}{2}\), and let \(\mathcal{F}\) be a subset of \(\mathbb{F}_p\) of size \(3\). Define the sequences \((r_0, r_1, r_2, r_3)\) and \((r_0', r_1', r_2', r_3')\) corresponding to \(A\) and \(\mathbb{F}_p\setminus A\) respectively.
Since a translation of \(\mathcal{F}\) that contains exactly \(i\) elements of \(A\) must contain exactly \(3-i\) elements of \(\mathbb{F}_p\setminus A\), we obtain \((r_0', r_1', r_2', r_3') = (r_3, r_2, r_1, r_0)\). Furthermore, adding a new element to \(A\) decreases both \(r_0\) and \(r_1\) by at most \(3\).
Consequently, if we always have \(|A +_{\mathcal{R}} B| \geqslant p-2\) for any subsets \(A, B\) satisfying \(|A| + |B| \geqslant p + O(1)\) and any relation \(\mathcal{R}\) a mapping from \(B\) to \(A\), then we must have \[r_0 + r_1 \leqslant\frac{p}{2} + O(1),\quad r_2 + r_3 \leqslant\frac{p}{2} + O(1),\] which implies \[\frac{p}{2} - O(1) \leqslant r_0 + r_1 \leqslant\frac{p}{2} + O(1)\label{eqn:r043r1}\tag{4}\] for any \(A \subseteq \mathbb{F}_p\) of size \(\frac{p}{2} \pm O(1)\).
Fixing \(\mathcal{F}\), this condition is highly restrictive, as each \(r_i\) is the sum of indicator functions for the event that a translation of \(\mathcal{F}\) contains exactly \(i\) elements of \(A\). Each of these indicator functions depends only on a constant number of elements being included or excluded from \(A\), meaning that selecting an element \(a \in A\) affects only a constant number of terms in the summation. Consequently, the distribution of \(r_0 + r_1\) should approximately follow a normal distribution, suggesting that the condition (4 ) is too rigid to hold universally.
The following lemma is helpful in understanding the constructions of 6(ii) and (iii).
Lemma 2. There exists a set \(A \subseteq \mathbb{Z}\) with period \(11\) and density \(\frac{6}{11}\) such that for each element \(a \in A\), there exists a translation of \(\{0,1,4\}\) that intersects \(A\) only at \(a\).
Proof. Consider the set \(A = \{0,1,2,3,5,6\} + 11\mathbb{Z}\). Then, we observe that \[(\{0,1,4\} + (-4)) \cap A = \{0\},\;(\{0,1,4\} + (-3)) \cap A = \{1\},\;(\{0,1,4\} + (-2)) \cap A = \{2\},\] \[(\{0,1,4\} + 3) \cap A = \{3\},\;(\{0,1,4\} + 4) \cap A = \{5\},\;(\{0,1,4\} + 6) \cap A = \{6\}.\]
Thus, \(A\) satisfies the required condition. ◻
For the case where the degree is bounded on both sides, adding the constraint that each element in \(A\) has degree at most \(1\) further reduces the maximum possible size of \(B\) to \(r_0 + |\{a \in A \colon\exists x \text{ such that } (\mathcal{F}+ x) \cap A = \{a\}\}|\). The second term is at most \(r_1\). This loss is caused by each element in \(A\) can be only connected to at most \(1\) element in \(B\).
Lev [8] provided a construction with \(|A| = \frac{p+1}{2}\) and \(|A +_{\mathcal{R}} A| = p-3\), demonstrating that the condition \(|A| + |B| \geqslant p+1\) is insufficient to guarantee \(|A +_{\mathcal{R}} B| \geqslant p-2\). The sum of sizes of this construction has one extra gain from \(p\). The key idea behind 6(ii) and (iii) is that we can replicate Lev’s construction to amplify this gap, given that the initial sum \(|A| + |B|\) exceeds \(p\). However, if the initial value of \(|A| + |B| - p\) were negative, this approach would offer no advantage. This is why such techniques are effective only when \(|A| + |B| > p\), and cannot be extended to the \(|A| + |B| = (1-\varepsilon)p\) regime in the first construction.
We are now ready to prove 6(ii) and (iii)
Proof. We begin with the proof of 6(ii).
The construction differs slightly, depending on whether \(\lfloor \frac{p}{11} \rfloor\) is even or odd.
If \(\lfloor \frac{p}{11} \rfloor\) is even, suppose \(\lfloor \frac{p}{11} \rfloor = 2t\). Set \[A = \Big( \{0,1,2,3,5,6\} + 11 \cdot \{-(t-1), -(t-2), \cdots, -1,0,1, \cdots, t-1\} \Big) \cup \big\{-11t+3, -11t+5, -11t+6 \big\},\] and define \(\mathcal{R}\) as \[\begin{align} \mathcal{R}&= \bigcup_{i = -t+1}^{t-1} \big\{(11i, -11i+2), (11i+1, -11i+1), (11i+2, -11i) \big\} \\ &\qquad\quad \cup \bigcup_{i = -t}^{t-1} \big\{(11i+3, -11(i+1)+6), (11i+5, -11(i+1)+5), (11i+6, -11(i+1)+3) \big\}. \end{align}\]
If \(\lfloor \frac{p}{11} \rfloor\) is odd, suppose \(\lfloor \frac{p}{11} \rfloor = 2t+1\). Set \[A = \Big( \{0,1,2,3,5,6\} + 11 \cdot \{-t, -(t-2), \cdots, -1,0,1, \cdots, t-1\} \Big) \cup \big\{11t, 11t+1, 11t+2 \big\},\] and define \(\mathcal{R}\) as \[\begin{align} \mathcal{R}&= \bigcup_{i = -t}^{t} \big\{(11i, -11i+2), (11i+1, -11i+1), (11i+2, -11i) \big\} \\ &\qquad\quad \cup \bigcup_{i = -t}^{t-1} \big\{(11i+3, -11(i+1)+6), (11i+5, -11(i+1)+5), (11i+6, -11(i+1)+3) \big\}. \end{align}\]
In both cases, \(|A| = 6 \lfloor \frac{p}{11} \rfloor - 3\), \(\mathcal{R}\) is a symmetric matching within \(A\), and \(|A +_{\mathcal{R}} A| = |\mathbb{F}_p\setminus \{-2,-1,2\}| = p-3\).
We now proceed to prove (iii). Without loss of generality, we may assume \(\varepsilon\leqslant\frac{6}{11}\). Let \(t = \lfloor \frac{\varepsilon p}{12} \rfloor\) and \(\delta = \frac{\varepsilon}{6}\). Set \[B = \Big( \{0,1,2,3,5,6\} + 11 \cdot \{-(t-1), -(t-2), \cdots, -1,0,1, \cdots, t-1\} \Big) \cup \big\{-11t+3, -11t+5, -11t+6 \big\},\] \[A = B \cup \{11t, 11t+1, \cdots, p - 11t-1\},\] and define \(\mathcal{R}\) as \[\begin{align} \mathcal{R}&= \bigcup_{i = -t+1}^{t-1} \big\{(11i, -11i+2), (11i+1, -11i+1), (11i+2, -11i) \big\} \\ &\qquad\quad \cup \bigcup_{i = -t}^{t-1} \big\{(11i+3, -11(i+1)+6), (11i+5, -11(i+1)+5), (11i+6, -11(i+1)+3) \big\}. \end{align}\]
Then we have \(|A| = (1-\frac{5\varepsilon}{6})p - O(1)\), \(|B| = \varepsilon p - O(1)\), and \(A +_{\mathcal{R}} B = \mathbb{F}_p\setminus \{-2,-1,2\}\). This completes the proof. ◻
Remark 8. If we could replace the set \(\{0,1,4\}\) in 2 with any set of integers of size \(4\) or more while keeping the upper density of \(A\) greater than \(\frac{1}{2}\), then the constructions in 6(ii) and (iii) could be improved to satisfy \(|A +_{\mathcal{R}} B| \leqslant p-4\).
Proof of 7. We prove the contrapositive. Suppose \(|A +_{\mathcal{R}} B| \leqslant p-k\). Let \(\mathcal{F}\) be a subset of \(\mathbb{F}_p\setminus (A +_{\mathcal{R}} B)\) of size \(k\). Denote \(r_i \coloneq\left| \left\{ x \in \mathbb{F}_p\colon|(\mathcal{F}+ x) \cap A| = i \right\} \right|\). Then we have (2 ) and (3 ). Hence \[r_1 + 2r_2 + \cdots + kr_k \leqslant(r_0 + r_1) + k(r_2 + \cdots + r_k) = (r_0 + r_1) + k(p - r_0 - r_1) = kp - (k-1)(r_0 + r_1).\]
So we have \[kp - (k-1)(r_0 + r_1) \geqslant k|A|.\]
Since \(|B| \leqslant r_0 + r_1\), we conclude \[\begin{align} |A| + |B| &= |A| + \frac{2k-2}{2k-1}|B| + \frac{1}{2k-1}|B| \leqslant|A| + \frac{2k-2}{2k-1}(r_0 + r_1) + \frac{1}{2k-1}|A| \\ &\leqslant|A| + \frac{2k-2}{2k-1} \cdot \frac{kp - k|A|}{k-1} + \frac{1}{2k-1}|A| \\ &= \frac{2kp}{2k-1}. \end{align}\]
This completes the proof. ◻
In this paper, we studied general restricted sumsets over \(\mathbb{F}_p\) and compared their behavior with that in the Erdős–Heilbronn theorem. When \(\mathcal{R}\) is a matching, the two settings behave similarly in the regime \(|A| + |B| \leqslant(1-\varepsilon)p\); however, when \(|A| + |B| > p\), we provided an example illustrating their difference. Nevertheless, the avoiding set \(\mathcal{F}\mathrel{\vcenter{:}}=\mathbb{F}_p\setminus (A +_\mathcal{R}B)\) remains an interesting object of study in the range \(|A| + |B| > p\). It was shown in [8] that \(\mathcal{F}\) is a Sidon set and hence satisfies the bound \(|\mathcal{F}| < \sqrt{p} + \frac{1}{2}\), which is currently the best known. Any construction achieving \(|\mathcal{F}| = \omega(1)\), or any improvement proving \(|\mathcal{F}| = o(\sqrt{p})\), would be of interest.
I would like to thank Vsevolod Lev for several helpful comments on earlier versions of this paper and for bringing [11] to my attention. I also benefited from valuable discussions with Boris Bukh and Zichao Dong. This work was initiated during the \(2^{\text{nd}}\) IBS ECOPRO Student Research Program in the summer of 2024. I am grateful to Hong Liu for hosting my visit to IBS as a student researcher.
Proof. By the assumptions, there is a partition \(I = I_{-2}\sqcup I_{-1}\sqcup I_0\sqcup I_1\sqcup I_2\) of the interval \(I\) into five consecutive disjoint subintervals, such that \(p_l \in I_{-2} \text{ and } p_r \in I_2\), \(|I_0|=|I_{-2}|= |I_{2}| = |J|\), and \(|I_0\cap A| \leqslant 2^{-4} |(I_{-1} \sqcup I_0 \sqcup I_1)\cap A|\). This partition can be constructed by placing \(I_{-2}, I_2\) at the endpoints of \(I\) and selecting \(I_0\) as a random subinterval within \(I \setminus (I_{-2} \sqcup I_2)\).
Let \(I_{\infty}\) be the complement of \(I\), i.e. \(I_{\infty}=I^c\). For a subset \(S\subseteq \{-2,-1,0,1,2, \infty\}\) write \(A_S = \sqcup_{x\in S} (A \cap I_x)\). By the construction, for any \(x, y \in B\), we have the following three assertions: \[\text{the sets} \;\;A_{-1}+q_r,\;A_1+q_l \;\;\text{and} \;\;A_{-2,\infty, 2}+y \;\;\text{are disjoint},\] \[\text{the sets} \;\;A_{-1,0,1}+x \;\;\text{and} \;\; A_{\infty}+y \;\;\text{are disjoint},\] and \[|A_0| \leqslant 2^{-4}|A_{-1,0,1}|.\]
From the proof of [11] we have the following two claims. Here, \(\mathbb{E}_{b \in \ast}|\mathrel{\raisebox{0.3ex}{\scalebox{0.5}{\bullet}}}|\) denotes the expectation of the size of the set \(\mathrel{\raisebox{0.3ex}{\scalebox{0.5}{\bullet}}}\) when \(b\) is chosen uniformly at random from \(\ast\). We decompose the value \(|A + X|\) for a given set \(X\) using the equation \(|A + X| = |A_{-2,\infty,2} + X| + |(A_{-1,0,1} + X) \setminus (A_{-2,\infty,2} + X)|\), and estimate each term separately.
Claim A. If \(|A_{-2,\infty,2}| \geqslant|B|-1\) then \[\mathbb{E}_{b \in B \setminus \{q_r\}} \bigg| A_{-2,\infty,2} + \{q_l,q_r, b\} \bigg| \geqslant|A_{-2,\infty,2}| + |B| - 1.\] If \(|A_{-2,\infty,2}| \leqslant|B|-1\) then either \[\mathbb{E}_{b \in B \setminus \{q_r\}} \bigg| A_{-2,\infty,2} + \{q_l,q_r, b\} \bigg| \geqslant 2|A_{-2,\infty,2}| + 2^{-3} (|B| - 1 - |A_{-2,\infty,2}|)\] or \[\mathbb{E}_{b_2,b_3\in B \setminus \{q_r\}} \bigg| A_{-2,\infty,2} + \{q_l,b_2, b_3\} \bigg| \geqslant 2.5 |A_{-2,\infty,2}|.\]
Claim B. We have \[\mathbb{E}_{b\in B \setminus \{q_r\}}\bigg|(A_{-1,0,1}+\{q_l,q_r, b\}) \setminus ( A_{-2,\infty,2}+\{q_l,q_r, b\} ) \bigg| \geqslant(2-2^{-3})|A_{-1,0,1}|\] and \[\mathbb{E}_{b_2,b_3\in B \setminus \{q_r\}}\bigg|(A_{-1,0,1}+\{q_l,b_2, b_3\}) \setminus ( A_{-2,\infty,2}+\{q_l,b_2, b_3\} ) \bigg| \geqslant(2-2^{-3})|A_{-1,0,1}|.\]
Now we proceed to prove 10.
Case 1: If \(|A_{-2, \infty, 2}|\geqslant|B|-1\). Applying Claim A and B, we have \[\begin{align} &\mathbb{E}_{b \in B \setminus \{q_r\}} \bigg| A+\{q_l, q_r,b\} \bigg| \\ & \geqslant\mathbb{E}_{b\in B \setminus \{q_r\}}\bigg|A_{-2,\infty,2}+\{q_l,q_r, b\} \bigg|+ \mathbb{E}_{b\in B \setminus \{q_r\}}\bigg|(A_{-1,0,1}+\{q_l,q_r, b\}) \setminus ( A_{-2,\infty,2}+\{q_l,q_r, b\} ) \bigg| \\ & \geqslant|A_{-2, \infty, 2}|+|B|-1+(2-2^{-3})|A_{-1,0,1}| \\ & = |A| + |B| - 1 + \frac{7}{8} \cdot |A_{-1,0,1}|. \end{align}\]
If \(|A_{-1,0,1}| \geqslant\frac{8r}{7}\), this expression is at least \(|A| + |B| - 1 + r\). We get the desired result. Otherwise, since \(I_{-1,0,1}\) is an interval of size \[\begin{align} |I_{-1,0,1}| &= |I| - |I_{-2}| - |I_{2}| = |I| - 2|J| \geqslant(2^{10} + 2r) |B| - 2|J| \\ &\geqslant((1+2^{-10})^{-1}(2^{10} + 2r) - 2)|J| \geqslant(\frac{8r}{7}+1)|J|, \end{align}\] there exists a subinterval \(I' \subseteq I\) of size at least \(|J|-1\) such that \(I' \cap A = \varnothing\). Translating \(A\) and \(B\), we may assume \(J = \{0,1, \cdots, |J|-1\}\) and \(\{p-|J| + 1, \cdots, p-1\} \subseteq I'\). Then the sum of \(A\) and \(B\) has no carry-over and hence \((A,B)\) is a rectifiable pair.
Case 2: If \(|A_{-2, \infty, 2}|< |B|\), using Claims A and B we have either \[\begin{align} & \mathbb{E}_{b \in B \setminus \{q_r\}} \bigg| A+\{q_l, q_r,b\} \bigg| \\ & \geqslant\mathbb{E}_{b\in B \setminus \{q_r\}} \bigg| A_{-2,\infty,2}+\{q_l,q_r, b\} \bigg| + \mathbb{E}_{b\in B \setminus \{q_r\}} \bigg| (A_{-1,0,1}+\{q_l,q_r, b\}) \setminus ( A_{-2,\infty,2}+\{q_l,q_r, b\} ) \bigg| \\ & \geqslant 2|A_{-2,\infty,2}| + 2^{-3} (|B|-1-|A_{-2,\infty,2}|) + (2-2^{-3}) |A_{-1,0,1}| \\ & = (2-2^{-3})|A|+2^{-3}(|B|-1) \\ & \geqslant|A| + (1-2^{-3})(|B| + 2r) + 2^{-3}(|B|-1) \\ & \geqslant|A|+|B|-1+r, \end{align}\] or \[\begin{align} & \mathbb{E}_{b_2, b_3 \in B \setminus \{q_r\}} \bigg| A+\{q_l, b_2,b_3\} \bigg| \\ & \geqslant\mathbb{E}_{b_2,b_3\in B \setminus \{q_r\}} \bigg| A_{-2, \infty, 2} + \{q_l, b_2, b_3\} \bigg| + \mathbb{E}_{b_2, b_3 \in B \setminus \{q_r\}} \bigg| (A_{-1,0,1} + \{q_l,b_2, b_3\}) \setminus ( A_{-2, \infty, 2} + \{q_l,b_2, b_3\} ) \bigg| \\ & \geqslant 2.5 |A_{-2, \infty, 2}| + (2-2^{-3}) |A_{-1,0,1}| \\ & \geqslant(2.25 - 2^{-4}) |A| \\ & \geqslant|A|+|B|-1+r. \end{align}\] Here we use the assumptions \(|A| \geqslant|B| + 2r\), \(|A| \geqslant 8r\), and the fact \(|A_{-1,0,1}| \leqslant|A\setminus I^c| \leqslant 2^{-1}|A|\).
This completes the proof of 10. ◻