Complement transfer and density bounds for one-sided restricted sumsets
September 9, 2026
Abstract
Let be nonempty, with , and forbid at most one pair in each -column of . We prove that the remaining sums number at least whenever and , where . In particular, an absolute linear size condition suffices. This gives an affirmative answer to the existence-of-a-constant question preceding Ouyang’s one-sided restricted-sumset conjecture. A complement transfer first reduces a hypothetical counterexample to one whose larger complementary set has at least half the available elements. Deleting the endpoints of unique representations then permits a high-density inverse theorem in the unbalanced case; small-doubling rectification handles the comparable case. We also obtain the bound under and . The sharp conjecture without a sparsity restriction on remains open.
1. Introduction
For nonempty finite subsets of an abelian group and a relation , write
The relation is one-sided of degree at most one if each belongs to at most one pair in . No degree bound is imposed at . Such a relation need not be a matching.
Lev’s study of mapping restrictions [3] shows why the classical Erdős–Heilbronn bound does not extend to arbitrary maps without size assumptions. Ouyang [5] establishes the degree-one bound with hypotheses and . Immediately before Conjecture 1.13, he asks for a bound under a linear size condition with an absolute coefficient on . His conjecture predicts that suffices. The following theorem retains this boundary when the smaller summand has sufficiently small absolute density.
Theorem 1.
Set
Let be prime and let be nonempty. Suppose
For every relation of degree at most one on ,
Corollary 2.
With the absolute integer , the conclusion of Theorem 1 holds whenever and .
Proof.
Since and , the stated conditions imply both and .
The constant is very small and is not optimized. The qualitative existence of a suitable has a shorter proof by combining the complement transfer below with Ouyang’s existing finite-field theorem; we include that deduction to distinguish it from the quantitative argument. The explicit bound in Theorem 1 uses Grynkiewicz’s inverse theorem [2] and Green–Ruzsa rectification [1]. A second consequence uses cardinality rectification instead.
Theorem 3.
Let satisfy the nonemptiness, ordering, degree, and boundary assumptions of Theorem 1. Its conclusion also holds if
The logarithmic bound can give a much smaller explicit threshold for a fixed number of columns. It is a quantitative companion to the positive-density theorem, not a separate asymptotic resolution. Neither theorem covers all of Ouyang’s Conjecture 1.13.
2. Complement transfer
Lemma 4.
Let be a finite abelian group of order . Suppose , and put . Define a relation on by
Its degree at is at most the degree of at , and
If , then
Proof.
For fixed , every with corresponds injectively to the forbidden pair , since its sum is outside . This proves the degree assertion. A pair is allowed precisely when , proving the inclusion. The cardinality identity follows from .
Thus a counterexample to a lower bound with loss transfers to one with the same loss and one-sided degree bound. In the degree-one problem, enlarge a putative counterexample to a set of size . Under , its complement has size , while
If necessary, apply Lemma 4 to interchange and replace by . We may therefore assume
The new relation may differ from the original relation, but it remains one-sided of degree at most one, and its allowed sumset has size at most with the new value of . We use this normalization only within a contradiction argument.
Proposition 5.
There exists an absolute such that the conclusion of Theorem 1 holds for .
Proof.
Take , using the constant in [5, Corollary 1.8(i)]. The cases follow from the elementary argument below. For , normalize a counterexample as in (1)–(2). Then
Extend the relation to the graph of a function by filling any empty forbidden column. This can only shrink the allowed sumset. Ouyang’s corollary, with , now contradicts the counterexample.
For completeness, the degree-one bound when or follows by retaining a single column, which gives at least sums. If and the allowed sumset had size at most , every column would have exactly that same set of surviving sums; call it . Thus . Cauchy–Davenport gives , a contradiction. Here ensures the last equality.
3. An inverse theorem after deleting unique representations
We use the following version of [2, Theorem 1.4]. If are nonempty, , and
then both summands lie in arithmetic progressions of lengths at most their respective cardinalities plus . This follows by ordering the summands in the cited theorem. Its high-density hypothesis is essential here.
Lemma 6.
There is no normalized counterexample satisfying (1)–(2) with , , and .
Proof.
Let and be the numbers of residues with and , respectively. In particular, . Pollard’s theorem [6], at level for and , gives
Consequently
Delete from every endpoint of a unique representation , , . Let be the number of deleted elements and let be the remaining set. Since there are unique representations, . All missing or unique differences are now absent from . If
then Cauchy–Davenport and the deletion estimate give
The sets to which we apply the inverse theorem are nonempty, since
Thus both and exceed ; also . The cited inverse theorem places in a progression of length with
After dilation and translation, write , where and . Common dilation and the corresponding translations of preserve the difference counts in (2).
For a set and a residue , put
Write . If , translate and so that a missing difference becomes zero. The sets are then disjoint, so
For , this yields
If , use a unique difference instead; such a difference exists by (3). After translation for some , and
The same counting identity, with an additional nonnegative term for , gives . In either case
Removing elements from an interval can decrease this boundary by at most : every point of remains in unless it belongs to . Hence . For , direct interval intersection gives
It follows that all elements of have integer representatives in . Use these representatives and those of in . Their entire integer sumset is contained in , an interval with elements. Reduction modulo is injective on it, and therefore preserves the size of the restricted sumset and the forbidden relation.
Ouyang’s integer theorem [5, Theorem 1.5(i)], at degree one, now gives at least allowed sums, contradicting the normalization.
4. Rectification when the sizes are comparable
Recall that a Freiman isomorphism of order two is an injective map preserving, in both directions, equalities between two-term sums. Applied to , it preserves the cardinality of every restricted sumset, after transferring the relation through its coordinate restrictions. Overlap between and causes no difficulty.
Lemma 7.
Suppose , the degree of at is at most one, and . For ,
Proof.
Put . There are at most forbidden pairs. Each sum outside is the sum of at least one such pair, so
The Plünnecke inequality gives and . More explicitly, choose a nonempty minimizing . Petridis’ inequality, in the form of [2, Theorem 2.4], gives
The other estimate follows by interchanging . Since and , the ratio satisfies
For the last inequality, the function on the right is convex on the positive real axis; its values at and are and , both below . Finally .
The cases were handled in Section 2. For , assume a counterexample and normalize it by complement transfer. Since , we have . Lemma 6 excludes , so Lemma 7 applies to the transformed pair. It gives
Green and Ruzsa [1, Theorem 1.3] prove that a subset of with doubling ratio is Freiman-isomorphic to an integer set when its density is at most . This threshold decreases for , and , . The theorem therefore rectifies . Transfer the forbidden relation to the integer images of and apply [5, Theorem 1.5(i)]. The resulting lower bound contradicts the assumed counterexample.
Normalize a counterexample with as before. Lemma 6 again gives , so
Lev’s rectification theorem [4, Theorem 1], at order two, makes Freiman-isomorphic to an integer set. The same integer restricted-sumset bound gives the contradiction. The cases remain elementary.
5. Scope and further questions
The proof isolates two operations that may be useful in sharper density questions: complement transfer preserves a one-sided degree condition exactly, and endpoint deletion converts low representation counts into small excess in an unrestricted difference set. The latter operation is particularly efficient at degree one. For larger degrees, deleting endpoints of low-multiplicity differences need not leave an excess small enough for the inverse theorem used here.
The complement lemma itself works for every fixed degree and every loss parameter . It does not preserve a degree bound at the other summand, so it cannot automatically transfer results whose hypotheses require a matching. The quantitative proof depends on the existing inverse theorem and rectification bounds; improving those inputs or treating comparable summands at higher density could improve the absolute constant.
The remaining sharp question is whether alone suffices. The results here resolve the weaker existence-of-an-absolute-linear-coefficient question, not that full conjecture. The earlier logarithmic and the positive-density conclusions are two bounds in this single investigation.
Preparation.
This manuscript was prepared with OpenAI Codex assistance. Proof checking recorded with the manuscript is internal; no independent human peer review is claimed.
[2] D. J. Grynkiewicz, The Theorem modulo a Prime: High Density for , Mathematika 71 (2025), e70030. doi:10.1112/mtk.70030. Author version: arXiv:2402.15028v1.
[3] V. F. Lev, Restricted set addition in groups, II. A generalization of the Erdős–Heilbronn conjecture, Electron. J. Combin. 7 (2000), R4. Journal article.
[4] V. F. Lev, The rectifiability threshold in abelian groups, Combinatorica 28 (2008), 491–497. doi:10.1007/s00493-008-2299-8.
[5] M. Ouyang, On restricted sumsets with bounded degree relations, Mathematika 71 (2025), e70045. doi:10.1112/mtk.70045. Revised author version: arXiv:2503.09121v3.
[6] J. M. Pollard, A generalisation of the theorem of Cauchy and Davenport, J. London Math. Soc. (2) 8 (1974), 460–462. doi:10.1112/jlms/s2-8.3.460.