WorksMathematics
Balanced additive complements with bounded representation functions
Abstract
We construct infinite sets and of positive integers such that for every , every integer at least belongs to , and the number of ordered representations of any integer as with and is at most . In particular, , giving a negative answer to a conjecture of Erdős and Sárközy. The construction uses two nested prime-power scales, a uniform residue bound, and a local cardinality matching.
Introduction
For sets , define their sumset and ordered representation function by
Erdős and Sárközy asked whether, for infinite and some ,
where and are the increasing enumerations of and . The question appears as Problem 1.17 in the 1999 collection [4] and as Problem 1145 in [1].
Theorem 1.1. There are infinite sets and of positive integers satisfying
Consequently the implication in (1) is false.
The construction proceeds through finite blocks whose elements have size comparable to the square of their scale. Geometric block constructions and matched local configurations for this problem were considered in the public notes [2, 3]. Here we maintain a residue-class bound for the full union of preceding blocks. Powers of two control one component and powers of three control the other. The resulting invariant bounds all mixed representations at a fixed maximal scale simultaneously.
Scales and residue bounds
Fix
For , put and let be the least power of two greater than . Since distinct positive powers of two and three are unequal,
Indeed, , so the next selected power of two is either or . In particular, , , and for all . Each of the two modulus sequences is nested under divisibility.
For a finite set and a positive integer , write
At stage , the preceding blocks will have unions
The induction maintains
Lemma 2.1. Let be positive integers with , and suppose for every . Call a residue class modulo safe if it contains at most elements of . Each residue class modulo contains at most one unsafe class modulo . Moreover, if a finite set uses only safe classes and for every , then for every .
Proof. Two unsafe classes in the same class modulo would contain at least
elements of . In a safe class, the union contains at most elements. An unsafe class receives no element of , and its old count is bounded by the count of its parent class modulo . □
At stage , safety for the -component is defined from modulo . Safety for the -component is defined from modulo . Thus every class modulo has at most one unsafe child among its three classes modulo , and every class modulo has at most one unsafe child among its classes modulo .
Construction of a block
Assume that the earlier blocks have been constructed, satisfy (7), and are pairwise disjoint within each component. Throughout this section abbreviate and .
Separating the blocks
We choose integers
Write and . The candidate sets are
All parameters in these formulas are integers.
Lemma 3.1. The anchors in (8) can be chosen so that and for every .
Proof. For each earlier , impose
Each condition in (11) excludes one residue class for modulo . Because , this removes exactly a fraction of its possible values. Also,
The union of the excluded choices therefore has size less than . Similarly, the excluded fraction of the possible values of is at most
Both anchors exist.
A point of is congruent to modulo , since . Every point of is congruent to for some . Thus (11) gives the required disjointness on the -side. The divisibility and (12) give the same conclusion on the -side.
The parameters within each candidate set are unique. Indeed, an equality between two expressions in (9), reduced modulo , gives . Coprimality and imply , and then . On the -side, reduction modulo gives , whence and .
Every candidate satisfies
For the upper bound in (9), use and to obtain
The -bound follows from .
Selection and matching
Only safe candidates will be retained. This suffices to preserve the next instance of (7). For a fixed and a fixed residue modulo , exactly indices give that residue, because is invertible modulo . Consequently
Every class modulo is contained in a class modulo , so its candidate count is also at most . Likewise , which bounds every candidate count modulo . Lemma 2.1 now applies to any subsets of the safe candidates.
The choice of those subsets is arranged to give a close matching. For an integer , put
The interval description
shows that
Indeed, the half-open interval in (14) has length and lies in .
For integers and , form the two stocks
Let and denote their safe subsets. The three -points occupy the three different children of one class modulo . Hence . For each , the two -points occupy different children of one class modulo , because . At least one is safe. Parameter uniqueness gives
The mandatory points in each stock are its safe unshifted points, obtained by setting or . Their counts, say and , satisfy and . Set . By (16), on each side we can choose exactly safe points containing all its mandatory points. Match the two chosen subsets by any bijection.
Let and be the unions of these choices over all . The uniqueness of and , together with parameter uniqueness, makes the stocks pairwise disjoint on each side. We have therefore constructed finite sets and a bijection
Every safe unshifted point in (9) or (10) belongs to the corresponding selected set.
Proposition 3.2. The sets are disjoint from the preceding blocks in their respective components. They satisfy (13), and , satisfy (7) with replaced by . Moreover,
Proof. Disjointness follows from Lemma 3.1, and the range bound holds for all candidates. The residue bounds follow from the safety argument above.
For points in one matched group, the term cancels and their difference is
We have , , , and . The triangle inequality proves (18). □
Coverage of each scale interval
Lemma 4.1. Suppose satisfy (8) and is an integer with . There are integers , , and such that
Proof. Coprimality gives unique and in the stated ranges satisfying
Thus is divisible by . Put . The parameter ranges imply
In particular, , so is a nonnegative integer. If , then
contrary to . If , then gives
This proves the bounds on . □
Proposition 4.2. Every integer in belongs to .
Proof. Use Lemma 4.1, and consider
where ranges over the integer interval
Both and lie between and . The bounds show that contains at least thirteen consecutive integers.
All the lie in a single class modulo . Modulo , changing by one changes by . Since is relatively prime to , the three residues of modulo give the three different child classes. Lemma 2.1 implies that at most one residue of modulo makes unsafe.
Write with . All the lie in one class modulo . Changing by one changes by , and is relatively prime to . The residues of modulo therefore give the different child classes. At most one of those residues makes unsafe.
In any thirteen consecutive integers, a fixed residue modulo occurs at most five times, and a fixed residue modulo occurs at most seven times. At most twelve positions are excluded. Choose a remaining . Then and are safe unshifted candidates, so both were retained. Finally (19) gives . □
The infinite sets and their representation function
Start at with empty preceding unions, which satisfy (7). Lemma 3.1 and Proposition 3.2 allow the construction to continue for every . Define
Proposition 4.2 makes each block nonempty. Disjointness within each component therefore makes both unions infinite. All their elements are positive by (13).
The intervals covered in Proposition 4.2 overlap, since
Their endpoints tend to infinity. Their first lower endpoint is , which proves (3).
Lemma 5.1. For any positive integer , at most five indices satisfy
Proof. Successive values of increase by a factor of at least four. If six indices satisfied (23), then
which is impossible. □
Proposition 5.2. The sets in (22) satisfy for every .
Proof. There are no representations when , so let . Each representation has unique block indices with and . Put . Monotonicity of the scales and (13) give
Lemma 5.1 leaves at most five possibilities for . Fix one such , and abbreviate , , , . Representations with maximal index fall into the following three disjoint cases.
The -point lies in and the -point lies in . The -point belongs to one of the three residues modulo . For a fixed , its partner belongs to the residue modulo . The invariant (7) bounds the number of such partners in the entire set by . Each partner determines the -point uniquely, giving at most representations.
The -point lies in and the -point lies in . There are two possible residues modulo for the -point. The same argument, using the -side of (7), gives at most representations.
Both points lie in block . Fix their shifts and . The remaining equation is
Modulo , this determines uniquely as a residue class. Among the indices , that class contains choices. Each choice determines at most one . The six shift pairs therefore contribute at most representations.
Summing first over the three cases and then over the eligible maximal indices yields
Increasing enumerations
The block bijections (17) combine to a bijection , because the blocks are disjoint within each component. For , both and are at least . Equation (18) thus gives
Lemma 6.1. Suppose infinite sets , admit a bijection satisfying (24). Their increasing enumerations satisfy for every .
Proof. The images of are distinct points of . Each is at most , since the function is increasing. Hence
Apply the same argument to to obtain . If , the first inequality gives . If , the second gives the required bound directly. □
Proof of Theorem 1.1. The construction in Section 5 gives infinite positive sets satisfying (3). Proposition 5.2 proves (4), and Lemma 6.1 proves (2). Since ,
The representation function has finite upper limit, which disproves (1). □
The everywhere-covering formulation
The same construction also gives a counterexample when the covering condition is imposed on every nonnegative integer, with zero allowed in the summand sets.
Corollary 7.1. There are infinite sets with , whose increasing enumerations satisfy and whose ordered representation function is uniformly bounded.
Proof. Let be the sets in Theorem 1.1 and put . The complement of in is infinite. Otherwise, for any 47006 distinct elements of , every sufficiently large would have for all of them. This would give , contradicting (4).
Set and . We have because . Choose a set with and , and put , . Every is represented by , and every retains an original representation.
For a fixed target, the representations using an element of number at most , and those using an element of number at most . Thus . Beyond the finitely many added elements, the increasing enumerations are and . Their ratio therefore tends to one.
Acknowledgments
The authors acknowledge assistance from OpenAI’s artificial intelligence systems in developing the construction and preparing and checking the exposition.
References
- [1]Erdős Problems, Problem 1145, problem statement and discussion, accessed November 2026. https://www.erdosproblems.com/1145.
- [2]Plasma AI, Proof of the annular square-complement limits, public research notes, 2026. https://erdosproblems.ai/wiki/theory/additive_bases/L3_square_complement_nine_halves/_proof.
- [3]Plasma AI, Monotone path shells for Erdős Problem 1145, public research notes, 2026. https://github.com/plasma-ai/erdos/blob/main/wiki/research/erdos_1145/monotone_path_shells.md.
- [4]Various authors, Some of Paul’s favorite problems, booklet circulated at the conference “Paul Erdős and his mathematics,” Budapest, July 1999, Problem 1.17. https://web.math.pmf.unizg.hr/~vjekovac/EP/Some_of_Pauls_favorite_problems.pdf.