Counterexamples to a conjecture on one-sided restricted sumsets
Henry Zweiman
September 8, 2026
Abstract
For finite integer sets and a forbidden relation , let be the set of sums represented by pairs outside . Ouyang conjectured that, when and every vertex of has forbidden degree at most , one has . We give explicit counterexamples for every , . For every , our sets have cardinality and restricted sumset cardinality , falling below the conjectured bound by . Consequently a universal linear loss coefficient must be at least . For and equal summand sizes , the construction attains the known lower bound , and hence determines the exact minimum.
1. Introduction
Let be finite, nonempty sets and let . The restricted sumset associated with the forbidden relation is
For , put . We consider the one-sided condition for all . Degrees on are unrestricted.
Ouyang proved that, if and the one-sided degree condition holds, then
[1, Conjecture 1.10]. All numbered references to that paper refer to its September 4, 2025 author version, arXiv:2503.09121v3.
We disprove (2) by a family whose forbidden degree is unbounded. The construction uses an interval with three holes as , an interval as , and four intervals of deleted sums. The holes near the endpoints of control the degree when both interior intervals of deleted sums meet the same translate of . Exact intersection counts show that the resulting degree is at most , while the loss from is .
Throughout, denotes the integer interval for integers .
Theorem 1.
Let be integers satisfying
Define
and put
Let and
Then
Corollary 2.
Conjecture 1.10 of [1] is false. For each , Theorem 1 gives examples with whose restricted sumset has fewer elements than the proposed lower bound.
Proof.
The proposed lower bound is , whereas the actual cardinality is . Their difference is
Corollary 3.
Suppose real constants , independent of , satisfy
for all finite, nonempty with and all relations of degree at most on . Then .
Proof.
Apply Theorem 1 with and . The claimed universal bound implies . Divide by and let tend to infinity.
The three holes in are disjoint and have total cardinality . Hence , and clearly . Both endpoints and belong to . The largest difference between consecutive elements of is . Thus the intervals , as runs through in increasing order, overlap or are adjacent. It follows that
The parameter inequalities imply that are disjoint, lie in this interval, and have lengths , respectively. Consequently .
It remains to prove the degree assertion. For , define
The interval can contribute only when , and can contribute only when . The two interior intervals can both contribute only when
Indeed, meeting requires , while meeting requires . The three ranges
are pairwise disjoint: and . Outside their union, neither endpoint interval contributes and at most one interior interval contributes. Its length is , so there.
The left endpoint range. Suppose . Only and contribute. The first count is the number of elements in after removing . The second is the number of elements of in . This interval can meet the central hole but no other hole. Direct counting gives
Every entry in the last column is at most .
The middle range. Write with . Only and contribute. To compute , intersect with
This interval meets only the left endpoint of and the hole ; its upper endpoint is less than . For the second count,
Set . Reflection takes this interval to . The reflected set has the endpoint hole and its central hole begins at . Since , no other hole contributes to this count. The exact intersection sizes are therefore
Again every entry in the last column is at most .
The right endpoint range. The left endpoint calculation also handles this range by reflection. To make the parameter change explicit, write for the constructed sets. With
we have
Moreover, . The map
therefore carries the forbidden relation for to the forbidden relation for . For , the new coordinate lies in , where (6) applies. This proves in the right endpoint range.
Together these calculations establish for every . Equality holds at by (6). Finally, by the definition of , every representation of a sum in is forbidden and every representation of a sum outside is permitted. Using (4), we obtain
Its cardinality is , as required.
3. Exact sharpness at degree three
For completeness, we recall the elementary lower-bound argument underlying (1). This is the argument of [1, Theorem 1.5(i)].
Proposition 4 (Ouyang).
Let be finite, nonempty sets, with , and let be an integer. If has degree at most on , then .
Proof.
Write and . If has forbidden degree at most , the strictly increasing chain of sums along
has elements and at most forbidden pairs. It supplies at least permitted sums.
Otherwise, has degree at least . Since
there is some with whose degree is at most . Consider the chain along the first column up to , then along the row of , then along the last column:
It contains strictly increasing sums. The number of forbidden pairs is at most , since the two columns have degree at most . Thus at least sums remain.
Corollary 5.
For every integer ,
where the minimum is over finite integer sets of cardinality and relations of degree at most three on .
Proof.
Proposition 4 gives the lower bound. Theorem 1, with and any , attains it.
For example, take , , and . Then
The degree sequence on , in increasing order, is
The restricted sumset has elements, whereas (2) requires .
The construction leaves a gap in the possible universal leading coefficient: Corollary 3 requires at least , while (1) supplies . We do not determine that coefficient, classify the equality cases at degree three, or assert a corresponding counterexample under a degree restriction on both sides.
References
[1] Minghui Ouyang, On restricted sumsets with bounded degree relations, Mathematika 71 (2025), no. 4, e70045. doi:10.1112/mtk.70045. Author version: arXiv:2503.09121v3, September 4, 2025.