WorksMathematics
Infinite Generalized Sidon Sets with a Negative Answer to a Problem of Szemerédi
Abstract
Let . For every integer , every finite set , and every , we construct an infinite set containing such that has upper limit and lower limit zero. This extends the range obtainable from our first construction, which answered a question of Cilleruelo and Nathanson, later raised by O'Bryant, on the existence of a positive upper limit. For , a positive upper limit disproves the assertion in Szemerédi's Problem~186(d). The improved range follows from an integer lift of a modular construction of Gómez Ruiz and Trujillo Solarte, with large gaps between sums of distinct -element multisets for each fixed . These gaps ensure that successive blocks can be adjoined by translation while preserving the property. The same prescribed limits can be attained inside every set of asymptotic density one containing . Separately, we construct extensions of that are maximal among all subsets of , have the prescribed limits, and avoid any prescribed finite subset of . These maximal extensions can be chosen so that diverges arbitrarily slowly.
Introduction
Throughout the paper, is an integer with . Let . A set is a set if , with all summands in , implies equality of the two multisets of summands. Repetitions are permitted. For , let . A nonempty set is also a set for , by adding the same terms to both sides of an equality. The distinct -term sums of a finite set give
Thus the natural density scale is .
Finite constructions of Bose and Chowla [2] attain this order of magnitude. The infinite problem requires dense finite sets at different scales to be compatible. Krückeberg [14] constructed an infinite Sidon set with normalized upper limit at least . Cilleruelo and Nathanson [7] observed that, for each and each function , one can construct an infinite set with by dilating successive blocks. Their 2007 preprint identified the existence of a positive upper limit without the factor as open. O’Bryant [17 v1, Section 5] later conjectured that such a set exists for every . In the first version of this paper, we constructed an extension of every finite set with normalized upper limit and lower limit zero. This settled the existence question for , as O’Bryant records in [17 v2, Section 5.3]. Proportional thinning while retaining the initial set gives each . Here we enlarge that range to for .
We include in Theorem 1.1 for use in the statements below. In that case the statement follows from earlier work. O’Bryant’s proof of Krückeberg’s bound can start with any finite Sidon set by [16 Lemma 9]. The normalized lower limit is zero for every Sidon set by Erdős’s bound (see [16 Theorem 1]). If the upper limit is , retaining the initial set and a proportion of the remaining terms gives each .
Keywords. Generalized Sidon sets, Szemerédi problem, infinite Sidon sequences.
Theorem 1.1. Let , let be a finite set, and define
For every , there is an infinite set containing such that
For , our first version disproved the assertion in Szemerédi’s Problem 186(d) [18 p. 56] by attaining upper limit . Theorem 1.1 raises this value to . This full-limit assertion is distinct from the question whether every infinite set has normalized lower limit zero. Helm [13] discusses the latter question and rules out for , while Chen [3] gives logarithmic lower-limit restrictions for even orders. Neither conclusion excludes a positive normalized upper limit.
The finite initial set can also be prescribed inside a restricted ambient set. Density below always means asymptotic density in .
Theorem 1.2. Let have density one, and let be a finite set. For every , there is an infinite set with satisfying (1.2).
In particular, a prescribed set of density zero can be avoided whenever it is disjoint from the initial set. Section 5 also treats positive upper density, infinite initial sets, and compatible families. The constants are attainable values; optimality is not asserted.
Maximality under inclusion in can also coexist with the limits in (1.2). A set is maximal if no further positive integer can be adjoined while preserving the property.
Theorem 1.3. Let be a finite set, and let be finite. For every , there are infinite maximal sets containing , disjoint from , and satisfying (1.2).
Theorem 6.2 proves this statement together with all the conclusions of Proposition 4.2. In contrast, Proposition 6.3 constructs arbitrarily sparse maximal sets, showing why sparsity alone does not suffice for extending an infinite initial set.
The main issue in joining blocks is the separation of shorter sums. A large translation distinguishes sums with different numbers of new terms. With the same number , however, the translation cancels, and a mixed relation becomes
If the old set lies in , the right side has absolute value at most . For each fixed , our finite blocks ensure that sums of distinct -element multisets differ by more than . In our first version we encoded the finite-field moment curve of [10, 20] in base and proved the separation estimate that yields upper limit . For the improved constant we use the modular logarithmic graph of Gómez Ruiz and Trujillo Solarte [9, Theorem 4]. Its integer lift has shorter-sum gaps large enough for the same iteration and fits in a shorter interval. For we apply the deletion argument of Cilleruelo and Nathanson [6, Lemma 3.2] to a Bose–Chowla block [2].
The study of Sidon sets goes back to Erdős and Turán [8]; see [11, 15] for broader accounts. Ajtai, Komlós and Szemerédi [1], Ruzsa [21], and Cilleruelo [5] obtain lower bounds holding at every large scale. For , Cilleruelo constructs a set with . Our growth statements in Section 4 concern simultaneous control of the prescribed positive upper limit, a finite initial set, and the behavior between dense scales; they do not claim a larger all-scale exponent than those earlier results.
Section 2 gives one recursive construction and proves the three available finite-block choices and their compatibility. Section 3 proves Theorem 1.1 and the exact value for the moment-curve choice. Sections 4 and 5 apply the common lemmas to growth, ambient restrictions and prescribed initial sets. Section 6 treats maximality, the number of extensions, and the obstruction from sparse maximal initial sets.
Construction and finite blocks
We give one construction for the three block choices, verify it below, and prove its density in Section 3. For an integer , let be its representative modulo .
Step 1. The old set and the prime. Start with a finite nonempty set , where is a positive integer, and choose a prime . The value is permitted. The parameters satisfy
Step 2. The finite block. Choose a nonempty block of integers, where is an integer fixed throughout the recursion. The moment-curve choice is
The other choices in Lemmas 2.3 and 2.4 have and , respectively; the second is available only for .
Step 3. The required block properties. Each chosen is a set, and sums of distinct -element multisets from it differ by more than whenever . For the block in (2.2), , and for distinct parameter multisets,
Step 4. The translation and the enlarged set. Define
Then is a set, for every , and . Its normalized count at the endpoint is
Step 5. Iteration. Start with if , and with otherwise. At stage , choose and a block satisfying Step 3 with , and define
Here is an upper endpoint, not necessarily an element of . Larger bounds for the old set and correspondingly larger primes may also be used. The set is an infinite set containing .
Step 6. Density. Whenever , the source set satisfies
For the moment-curve choice the normalized upper limit is exactly . Using the logarithmic block for and the Sidon block for , selection gives every prescribed upper limit up to . In the Sidon deletion construction, is ensured by making the old bound negligible relative to .
The next lemma proves that the extension in (6) is a set and also permits the larger translations used later inside a prescribed ambient set.
Lemma 2.1. Let be a finite nonempty set, and let be a finite nonempty set of integers, where are positive integers. Suppose that sums of distinct -element multisets from differ by more than for every . For every integer , the set is a set, and the new block lies above .
Proof. We first prove that equal sums contain the same number of new terms. Since , the old and new sets are disjoint. If one -term sum contains new terms and the other contains , their difference is at least
Here the first sum is at least , whereas the second is at most ; also . Exchanging the sums excludes the case . If or , the property of or identifies the summands, after cancellation of the translation when .
We resolve the remaining case by the shorter-sum gap. Let and be the new parameters, and let and be the old terms on the two sides. Cancellation gives
The gap hypothesis forces the new multisets to agree. After cancelling them, add the same copies of any fixed element of the nonempty set to both old sums. The property of identifies the padded multisets; removing the added copies identifies the original old multisets. □
The following lemma recalls the integer encoding and shorter-sum estimate from Proposition 2.3 of our first version. Its power-sum argument comes from the finite-field moment curve [10, 20]. For , the integer encoding is the Erdős–Turán construction [8].
Lemma 2.2. For a prime , the set in (4) is a set of elements, the map is strictly increasing, and
For , sums of distinct -element parameter multisets differ by at least after applying .
Proof. We first prove the range and cardinality assertions. Since for , the terms after in satisfy
This proves (9). The intervals for consecutive parameters are disjoint and ordered, so is strictly increasing and .
We next identify the power sums that distinguish two parameter multisets. For two -tuples in with common power sums , , let be their elementary symmetric functions and . Newton’s identities give
Since each is invertible in , induction gives . The two monic polynomials with the tuple entries as roots are therefore equal. Unique factorization identifies each root with its multiplicity, so the two multisets agree.
We now prove uniqueness and all shorter-sum gaps in one comparison. Fix and distinct multisets of parameters and in . For each power , let ; then . The preceding power-sum argument shows that not all are zero. Let be the first index with . Its coefficient has absolute value at least one, so
An empty sum here is zero. Since , the last expression is at least one; taking proves the property. If , then and the geometric sum is at least one. The same expression is therefore at least , proving (2.3). □
For the second block we lift the modular graph of Gómez Ruiz and Trujillo Solarte [9 Theorem 4] to the integers. Its order-two specialization is Ruzsa’s construction [22], as observed in [9 Observation 4]. The next lemma gives the width of the lift and the gaps between its shorter sums.
Lemma 2.3. For a prime , there is a set with elements if and elements if . For , sums of distinct -element multisets from differ by at least .
Proof. We first define the parameters and their integer representatives. Let generate the multiplicative group . Its degree over is : if this degree were , the field would have elements, so the order of would be at most , a contradiction. For with , let be its representative in and define
The chosen generator gives a unique integer in the indicated range. When , the degree of is at least two, so and every is permitted. When , exactly the parameter is excluded.
We next check the size and range in the statement. If , reduction modulo gives , since both remainders lie in . Thus . This proves the asserted cardinality. Moreover,
These are integer inequalities, whereas the defining equation for is an equation in .
We prove the property by comparing two sums of block elements. Let and be their respective parameters, with repetitions allowed, and suppose that . The definition in (2.8) gives
The absolute value of the right side is at most . It is a multiple of , so it is zero. Both the sums of the integer representatives and the sums of the integer logarithms therefore agree. We now recover the parameters from these two equalities. Reduction of the first equality modulo gives in , and exponentiation of in the second gives . Consequently the polynomial
vanishes at . Its coefficients of cancel because the products are monic, and its coefficients of cancel because the parameter sums agree. Its degree is at most , below the degree of , so it is the zero polynomial. Unique factorization identifies the parameter multisets, including their multiplicities. The corresponding multisets of are equal, proving the property. This argument also covers , when the difference is a constant polynomial.
We finally separate all shorter sums. Fix and two distinct multisets of permitted parameters. Equality of their integer logarithm sums would imply equality of the products at . The difference of the two monic degree- products has degree at most , so the preceding degree argument would identify the two parameter multisets, a contradiction. Thus their logarithm sums are distinct integers and differ by at least one. Applying the reverse triangle inequality to (2.8) gives
This proves the separation required for every . □
For , the preceding block gives an attainable upper limit of after the selection in Lemma 3.2. The next lemma applies the short-difference deletion argument of Cilleruelo and Nathanson [6 Lemma 3.2] to a Bose–Chowla block [2], with the gap chosen for the old set.
Lemma 2.4. For a prime and a positive integer , there is a Sidon set with , whose distinct elements differ by more than .
Proof. We first construct a Sidon set with elements. Let generate , and take the integer representatives defined by
The degree of is two, so every parameter is permitted. Different parameters give different representatives. If as integers, exponentiation gives equal quadratic products at . Their monic leading coefficients cancel, leaving a polynomial of degree at most one that vanishes at . It is zero, so its two multisets of roots agree. This proves the Sidon property for the set of representatives.
We next remove all differences at most with at most deletions. In a Sidon set, a positive difference has at most one ordered representation: if , then . Equality of the two unordered pairs implies either and , or and . The second possibility contradicts positivity. For each integer difference in that occurs, mark the larger endpoint of its unique pair, and delete all marked elements. At most elements are deleted; every pair with a forbidden difference loses an endpoint. The remaining subset is a Sidon set with the asserted size and gaps. □
The next lemma verifies the recursion in Step 5 for all three block choices, using only their range and separation properties.
Lemma 2.5. Suppose the blocks in (2.5) satisfy Steps –, with fixed and . Then is an infinite set containing , and
Moreover, .
Proof. We first verify each finite extension and the infinite union. At stage , apply Lemma 2.1 with , and the chosen block . The integer inequality gives . Induction proves that every is a finite set and that the new block lies above all old elements. Each block is nonempty, so and . Any equality of -term sums in involves finitely many elements, all contained in one . Its property proves the same property for .
We next check that later blocks do not affect the recorded counts. All elements of lie below , and since the new block is nonempty. Consequently
Thus . Before only contributes; the new and old sets are disjoint. These observations prove (11). □
Density and the main theorem
The common endpoint calculation and selection argument below prove Theorem 1.1. The final proposition then bounds the count inside each moment-curve block to obtain its exact upper limit .
Lemma 3.1. Under the hypotheses of Lemma 2.5, if , then the three limits in (8) hold. In particular, has normalized upper limit at least and normalized lower limit zero.
Proof. We first bound the old count relative to the new block size. By (3), applied with , and ,
Here by Lemma 2.5.
We determine the limits by dividing the counts in (11) by the corresponding scales. The recursion gives
Together with (12) and , these prove the first two limits in (8). Taking the ratio of and in (7) gives the third. Nonnegativity then makes the normalized lower limit zero. □
The next lemma selects an exact upper limit while retaining a prescribed subset with negligible counting function.
Lemma 3.2. Let be an infinite set, let satisfy , and let . For every , there is a set with such that
If is finite, the error in the last equality is . The normalized upper limit of is ; if the normalized lower limit of is zero, then that of is also zero.
Proof. We first choose the retained elements outside . The bound (1) makes finite. The set is infinite, since otherwise . Enumerate its elements in increasing order as . Retain exactly when , and include every element of . Since , each increase is either zero or one. Among the first elements outside , the number retained is the telescoping sum . Taking proves the first equality in (3.2).
We next determine the counting error and the limiting values. The first equality gives . This is , and it is bounded when is finite. Division by now gives the claimed upper and lower limits. The positive upper limit makes infinite, and preserves the property. □
For the improved blocks, let and for , so that .
Proof of Theorem 1.1. We choose the blocks in (7) with . Let and, at stage , choose a prime . For use Lemma 2.3. For use Lemma 2.4 with old bound , and additionally require . The first blocks have elements; the second have between and elements. Thus in both cases. Their shorter-sum gaps exceed , which is at least , so Lemma 2.5 applies.
We obtain the exact upper limit by selection. Lemma 3.1 gives and lower limit zero. The endpoint calculation alone does not exclude larger values inside a block. Apply Lemma 3.2 with and to obtain the required exact upper limit and retain the initial set. □
For the moment-curve blocks, the upper limit is exact before any selection. We recall Proposition 3.2 of our first version, which establishes this for every admissible choice of primes.
Proposition 3.3. With the blocks in (4) and , the recursion (7) gives an infinite set satisfying
Any primes may be used.
Proof. We first determine the endpoint density and the lower limit. Lemma 2.2 gives . Lemmas 2.5 and 3.1, with , therefore give upper limit at least and lower limit zero.
We next bound the count at every point in a new block. Fix , abbreviate , and consider with . Lemma 2.5 ensures that no later block contributes to , and is strictly increasing by Lemma 2.2. Hence . The lower bound in (9) gives, for ,
For , we have . Thus the term involving is at most , with value zero at . The remaining term is at most
by (12), independently of . Hence the block estimate is uniform.
We finally extend the estimate to all sufficiently large real . If is the last element of at most , then and . As , the element tends to infinity and its block index does also, because each stage is finite. The uniform error consequently tends to zero. This proves the upper bound and hence equality. □
For , the moment-curve block and translation are explicitly
The proposition gives upper limit for this construction; Theorem 1.1 permits every value up to . Both conclusions concern the full-limit assertion discussed in the introduction.
Growth between dense scales
The size of in (7) determines how far the next block is from the preceding one. For a finite prescribed set, (13) changes the counting function by a fixed positive factor and a bounded error. Consequently the growth estimates below pass from the source set to the selected set. Unless stated otherwise, we use the blocks from the proof of Theorem 1.1, with . The notation means upper and lower bounds by positive constant multiples, with fixed parameters permitted in the constants.
Proposition 4.1. Let , let be a finite set, and let and . The set in Theorem 1.1 can be chosen so that
The implied constant may depend on .
Proof. We first choose the prime sizes to control the successive endpoints. Bertrand’s theorem permits a prime between and . Thus in (7) we can require . Since , the original condition holds. The endpoint formula and (8) give
The constants in these comparisons are independent of .
We next prove the lower bound at every sufficiently large scale. For , monotonicity of the count and (14) yield
Let and apply Lemma 3.2 with . Then , where is fixed. Since , the bounded error can be absorbed into a smaller positive constant in the preceding lower bound.
We identify a sequence on which the lower logarithmic exponent is attained. Immediately before the th block, . Equations (7) and (14) give
Their quotient tends to . The bounded-error selection changes the numerator by , because . Together with the all-scale lower bound, this proves the stated lower logarithmic exponent.
We finally determine the upper logarithmic exponent. The counting bound (1) gives . Since the normalized upper limit of is , along a sequence ; on that sequence the logarithmic quotient tends to . This proves the remaining equality. □
For , the constants require a separate distinction. The logarithmic block in Lemma 2.3 has elements in , so the same proof gives every and exponent for . For the full range , use Lemma 2.4 and take . The choice of then gives , as required to make the deletions negligible. At the endpoint exponent , choose instead once . Here
We obtain an explicit lower bound on the intervals between endpoints. The same choice of primes gives
Since is increasing for , the inequality for gives . The fixed positive proportion and bounded error in (13) therefore give . The values at still give lower logarithmic exponent .
Primes may also be chosen much farther apart. The next proposition imposes a slowly growing critical sum and small counts at prescribed late scales in the same construction. The functions need not be monotone. For , the existence of a Sidon set with was proved by Riblet and Schehr [19 Corollary 3.4]. For , divergence of already follows from the positive upper limit in our first version. Here we impose arbitrarily slow divergence together with a prescribed finite initial set and normalized upper limit.
Proposition 4.2. Let and satisfy Theorem 1.1. Given positive functions tending to infinity and any sequence , the set can satisfy (2) and
It can also have scales , with , such that
Proof. We first impose the size requirements during the recursion (7). Once is fixed, choose large enough that
Also keep and, for , . These choices are possible because both functions tend to infinity: each required lower bound holds at every argument beyond a threshold, and as . This uses no monotonicity assumption.
We next bound the critical sum of the source set. Every new block has at most elements, all at least . Its contribution to is therefore at most . For , only the initial set and the first blocks contribute, so
Select by Lemma 3.2, with . The partial-sum bound passes to , and (2) holds.
We prove divergence from the positive normalized upper limit. For fixed and , each satisfies , whence
If the series converged, taking the upper limit as and then letting would give . This contradicts and proves divergence.
We finally locate the requested dense and sparse scales after the selection. Between consecutive elements of , the count is constant and its quotient by decreases. Thus the upper limit can be approached at elements of . Choose such elements in blocks with strictly increasing indices . This is possible because each block is finite. Let . Then (15) gives
Here explains why the prefix maximum in (15) suffices even if is not increasing. Since , we have and . Equation (8) proves the ratio bound. ▫
Taking gives lower logarithmic exponent zero: at the scales , eventually , whereas for all sufficiently large . Together with Proposition 4.1, this realizes every lower logarithmic exponent in for , while retaining any prescribed . For comparison, every set satisfies when : by (1), the contribution from is , a summable geometric bound.
Corollary 4.3. For every set satisfying (2), the subsequential limits of form exactly the interval .
Proof. We first show that consecutive normalized counts have vanishing differences. Since and ,
We next obtain every intermediate limit by a crossing argument. Fix . The lower and upper limits in (2) give arbitrarily late indices with values below and above . Choose a value below and a later value above , and take the first index in between with value at least . Its distance from is at most the preceding consecutive difference, which tends to zero as the starting index tends to infinity. Thus is a subsequential limit. The endpoints are subsequential limits by their definitions, and no value outside is permitted by (2). For real , setting gives and , so the real and integer subsequential limits coincide. □
Ambient restrictions and initial sets
Lemma 2.1 remains applicable if a block is replaced by a nonempty subset or its translation is increased. The first change preserves the property and all shorter-sum gaps; the second preserves the required lower bound for the translation. We use these two facts to place blocks inside a prescribed set . The notation continues to mean a finite block, whereas denotes the ambient set.
Proof of Theorem 1.2. We first find a translate that loses only a small proportion of a block. Let the current finite set lie in , fix , and use the blocks of Theorem 1.1, with width . Choose the prime sufficiently large that
The last requirement follows from density one with fixed . Let . For every integer between and , all of lies in . We prove the retained-cardinality estimate by averaging. For a fixed , distinct translations give distinct integers , so at most translations send outside . Summing this bound over , and using at least available translations, gives a translation for which at most elements are lost. Hence
This nonempty retained block can be appended to by Lemma 2.1.
We next iterate the retained blocks while controlling their endpoints. Start from , or one point of if is empty, and choose . At each stage let be the preceding integer endpoint, and take the next endpoint to be . The next translation exceeds this endpoint because its prime exceeds . Thus later stages do not change counts at earlier endpoints. The logarithmic blocks have elements for ; for , the condition gives . It follows from (16) that each added block has elements. Its endpoint divided by tends to , so the source upper limit is at least .
We finally prove the zero lower limit and select the exact upper limit. Immediately before each chosen translation , only the old set contributes. By (1) and its cardinality is , whereas . Thus the source has normalized lower limit zero. Every finite stage is a set by the extension lemma. Any comparison of two -term sums in the nested union involves finitely many elements and hence lies in one finite stage, so the union is a set. Lemma 3.2, with , yields the requested while retaining containment in .
Positive upper density supplies sufficiently many points at a sequence of endpoints, although it does not make the losses in a short translation interval negligible. Averaging over a longer interval gives the following explicit, smaller constant.
Proposition 5.1. Let have upper density , and let be a finite set. For every
there is an infinite set with satisfying (2). In particular, is permitted.
Proof. We first choose a block size relative to a dense endpoint. Fix the old bound and . There are arbitrarily large integers with . Bertrand’s theorem permits a prime
Taking such an large enough ensures , and . The upper bound on also gives . Use the appropriate block of Theorem 1.1 and let
We next average over all integer translations . For and , the integer satisfies . For fixed , different give different translations. Counting these pairs yields
There are at most translations in the sum, so at least one retains the proportion of . The retained set lies below , and its union with the old set is a set by Lemma 2.1.
We compute the density supplied by this retained block. As , the condition makes , including in the Sidon case. The lower bound on in (17) and the upper bound give
Multiplication by the limiting retained proportion gives exactly the constant in the statement. In particular, the upper limit of the source count is at least that constant.
We complete the recursion and obtain its lower limit. Repeat the construction with , starting from or one point of , and use as the next old bound. Later blocks then lie above each recorded endpoint. Immediately before a new translation , only the old set contributes, with cardinality . Since , the normalized count there tends to zero. The nested union is a subset of , and Lemma 3.2 with gives every stated . Finally, for and , while . Therefore the displayed constant is at least .
Corollary 5.2. In a positive arithmetic progression of common difference , every finite initial set extends to an infinite set satisfying (2) for any . In every -colouring of , some colour contains a set satisfying (2) with .
Proof. We first transfer the progression assertion to . For the progression , with , the map is a bijection from . An equality of two -term sums in its image cancels the common translation and the nonzero factor . Thus this map and its inverse on the progression preserve the property. Apply Theorem 1.1 to the inverse image of the seed, with upper limit . The image count is . As , its normalized limits are and zero.
We next obtain the colouring assertion from a finite partition. Choose a set with upper limit and lower limit zero. Let be its colour parts. Since , . One part therefore has upper limit at least . It is infinite and inherits the zero lower limit from . Lemma 3.2, with empty prescribed set, selects within this part a set with upper limit exactly . The assertion concerns some colour, not a colour specified in advance. □
An infinite prescribed subset requires room for both the dense blocks and its later elements. The next sufficient conditions ensure this room. The assumption that the prescribed union is a set is necessary for any extension.
Proposition 5.3. Let have density one, let lie in , and let be finite with a set. If eventually , then for every there is an infinite set with satisfying (2). If instead , the full range is permitted.
The stronger separation enlarges the range of only for , from to ; for both ranges coincide.
Proof. We first justify the insertion of an isolated prescribed element. Let be a finite nonempty set of positive integers and let . In a comparison of two -term sums from , let be the multiplicities of on the two sides. The first sum minus the second is at least . Equal sums must therefore have the same multiplicity of . Cancelling those copies and padding with the same old element reduces to the property of . Hence is a set.
We next construct the blocks under the fixed gap bound. Choose so large that and all subsequent size conditions hold, and start with . Suppose the current maximum is . Choose a prime using Lemma 2.3 for every . This block has elements in . No estimate is required here, since no Sidon deletion is performed.
We place almost all of this block in with a small additional translation. Density one and permit such that
For all large , a possible choice is . Since , we also have for all large . The averaging argument proving (16), with width , gives a compatible block of elements below . The separate condition from the Sidon case is not used in this averaging argument.
We check that the next prescribed element can be inserted. For all sufficiently large , the preceding endpoint is at most , and gives
The first inequality uses and . For the second, is an equality when , and follows from when . Thus exceeds times the new maximum. The first paragraph permits its insertion and restores the old maximum to for the next stage. We treat the stronger gap condition using larger intermediate primes. Choose
Then and . For all large the inequality holds. Use the blocks of Theorem 1.1, now including the Sidon deletion when . Its loss is at most . Density-one averaging retains elements, with endpoint . Increasing if needed ensures that this endpoint is less than at every stage. The same singleton argument again inserts .
We determine the normalized limits of these two sources. Each finite stage is a subset of , so each nested union is an infinite set containing . In the first construction the dense endpoints have new elements below , giving upper limit at least . In the second the corresponding bound is , giving upper limit at least . Immediately before each block, the count is that of a finite set with maximum , hence is . The scale is comparable to , so both lower limits are zero.
We finally check that selection can retain the entire infinite seed. Either gap assumption implies eventually. For a sufficiently large fixed index with , iteration gives . Thus forces , and . Adding the finite set does not change this estimate. Lemma 3.2, with prescribed subset , therefore gives the exact upper limits claimed. □
Proposition 5.4. Let have density one, and prescribe for each positive integer . There are pairwise disjoint infinite sets , each satisfying (1.2) with , whose union is a set. A finite family of pairwise disjoint finite subsets of can be retained in the corresponding sets if its union is a set.
Proof. We first construct the sets together to preserve compatibility. Begin with the union of the specified seeds, retaining their labels. If this union is empty, choose one point of and give it label 1. Use the label sequence , in which every positive integer occurs infinitely often. At each stage apply the retained-block construction of Theorem 1.2 to the whole current finite union, with , and give every element of the new block that stage’s label. All new blocks lie above the previous endpoint, so the labelled portions are pairwise disjoint. Every finite union in the recursion is a set; consequently their infinite union is also a set.
We next verify the required limits separately for each label. Immediately before any new block, the total old count is , so has normalized lower limit zero. Since , every inherits this zero lower limit. At every endpoint assigned label , its new block alone contributes elements below . There are infinitely many such endpoints for each , so and is infinite. Apply Lemma 3.2 separately to , retaining its finite seed and selecting upper limit . The resulting sets remain disjoint, and their union is a subset of , so it retains the property. □
Maximal extensions
A subset of is maximal if no further positive integer can be adjoined while preserving the property. For , Cilleruelo and Nathanson [6 Theorem 1.3] constructed a perfect difference set with . Such a set is maximal Sidon because adjoining repeats the nonzero difference for any . Chen and Fang [4 Theorem 1.1] proved that for every Sidon set one can even choose a perfect difference set with for any prescribed positive .
When only the upper limit is prescribed, the construction in [6 Section 3] also yields every . Indeed, put . If is the current maximum, their prime gives a translated block of points in . Retain of the first points for each . At step , adjoin their auxiliary pair for is missing from the differences of the actual old set. The full block and this pair satisfy their Sidon separation bounds, which preserved on passing to the retained block. Thus each positive difference is realized exactly once. A final translation by one moves their construction, which starts at zero, into .
Before this final translation, consider with . The old set contributes at most points. The finite Sidon bound [16 Lemma 4] gives at most points from the full block up to , hence at most from the retained block, uniformly in . Since , the normalized count is at most . At it is . Up to the next block, the auxiliary pair adds at most two points, so the upper limit is exactly .
The same argument gives the order-two case of Theorem 6.2. Start with the prescribed seed (or one allowed point if it is empty). Take at step and place every addition beyond the finite exclusions. Each stage adds to the critical series. Choose so that for and, at , we have and the old count is at most . The dense endpoint is at most . At each stage allow two choices of prime, with the second block starting beyond all additions of the first choice. The resulting branches are distinct.
Lemma 6.1. Let be a finite nonempty set and let . Above any prescribed bound, one can adjoin distinct elements to obtain a set such that is not a set.
Proof. For a positive integer parameter , define
For all sufficiently large , these elements are positive, distinct, and exceed both the given bound and every element of . Indeed, has leading term and differs from by a polynomial with leading term ; all other distinctions follow from their degrees. The relation prevents the insertion of .
Consider two distinct multisets of labels from and the new labels. Their sum difference is a polynomial in . Let be the difference of the multiplicities of , and let be those of for . If the polynomial is identically zero, comparison of its even and odd powers gives and . If , one side contains at least copies of each of the labels . Its length forces and that side to consist exactly of these labels. The other side then consists of and one element ; the constant coefficient gives , a contradiction. Exchanging the multisets excludes . If , all new multiplicities agree. After their cancellation, the old multisets agree by the property of , with identical padding if their common length is less than . Thus no nontrivial comparison is identically zero. There are finitely many comparisons and each has finitely many integer roots, so every sufficiently large integer outside their union gives the required .
:::
In the following theorem maximality is taken in .
Theorem 6.2. Let be a finite set, and let be finite. Given , positive functions tending to infinity, and a sequence , there are infinite maximal sets with , , and (2). Each of these sets also satisfies
and has integer scales , with , such that
The functions need not be monotone.
Proof. Start with ; if it is empty, start with one integer exceeding . For each , apply Lemma 6.1, placing all its new elements above and the current set. We obtain a nonempty finite set containing , disjoint from , and preventing the insertion of every element of . All elements of are declared forced and retained throughout. If a superset of contained some , it would contain , contradicting the relation just imposed. Thus every later extension of avoids .
Construct a binary tree of finite sets rooted at . At level , choose an integer threshold exceeding and, when , the full candidate endpoint at every node of level . Since each level has finitely many nodes and , we may also require
At the first level it also exceeds . For the current set , if and is a set, use Lemma 6.1 to prevent the insertion of , with all new terms above and the current set. If is already present or already impossible to add, leave unchanged at this step.
Choose with . In the first continuation adjoin ; the singleton argument in Proposition 5.3 shows that this preserves the property. In the second use Lemma 6.1 to prevent its insertion, placing all new elements above both and the current set. Call the elements added in these two steps forced elements. Each continuation receives fewer than of them at level , all above .
For each continuation, let be its current set and put . Choose a prime and the block from Theorem 1.1, with . Define as in (2.5), and require
For also require . All conditions hold for sufficiently large primes, since . The chosen block has all distinct shorter sums separated by more than , while
Lemma 2.1, with , therefore applies to this current set , including its forced elements. For the block has elements; for it has between and elements. Consequently . Process the candidate elements in increasing order. If non-forced elements have already been retained along this branch, retain precisely when . Forced additions do not change . Retaining a subset preserves the property. All later additions must exceed , the full candidate endpoint, including the part containing rejected candidates. There are finitely many nodes at each level, so these choices define the tree successively.
Fix an infinite branch and let be the union of its finite sets. The thresholds tend to infinity, so the corresponding primes do also. Let consist of and all its forced elements, and let be the retained non-forced elements. Through level there are at most forced elements. At any forced element of level , (6.1) therefore gives . Between consecutive forced elements this quotient decreases. There is a forced addition at every level, so . The counting threshold gives , and hence .
At a rejected candidate , the preceding count is at most by the threshold at earlier candidates, but exceeds it. Thus . Later stages cannot change this value. Infinitely many rejections give upper limit at least . If only finitely many occur, every sufficiently late candidate block is retained in full. At such endpoints,
In both cases the upper limit equals . Immediately before each candidate block, and . Our choice therefore gives normalized lower limit zero.
The fewer than forced elements of level contribute at most to the critical series by (6.1). A complete candidate block has at most elements, each at least , so its contribution is also at most one. For from the first new element of level up to the first new element of level , excluding that last element, the partial sum is at most , whereas . These intervals cover all sufficiently large . Their quotient tends to zero. Positive normalized upper limit forces divergence by the tail estimate in Proposition 4.2.
Let . Then and . If the candidate block has a rejected element, choose one as ; the equality for and give along these levels. Otherwise choose . The calculation in (19) applies to every fully retained block, regardless of the decisions at other levels. Along any infinite sequence of these levels the endpoint ratios therefore tend to . They occur only finitely often if , by the upper bound already proved; if , they give the required limit as well. Finally and by their definitions, proving the ratio bound.
Every finite stage is a set, so every branch union is a set by the finite-comparison argument. Each integer is either present or impossible to adjoin after level . The finite relation preventing its insertion is retained forever, so the union is maximal and still avoids . At the first differing continuation of two branches, one union contains the chosen , while the other retains a relation preventing its insertion. Their unions are different. The binary tree has infinite branches, and has at most that many subsets, proving the asserted cardinality.
Maximality also explains why sparsity alone cannot replace the gap condition in Proposition 5.3. An infinite initial set can have arbitrarily slow counting growth and still admit no proper extension. For , this also follows from Hall’s construction of an infinite perfect difference set extending a finite Sidon set. Each pair realizing a missing difference can be placed arbitrarily far out [12], Theorem 3.1.
Proposition 6.3. Let be a finite set, and let be nondecreasing with . There is an infinite maximal set such that for all sufficiently large . In particular, an arbitrary infinite initial set need not admit an extension with positive normalized upper limit.
Proof. We first construct a maximal set while controlling every new addition. Start with , or with if is empty, and process . For the current finite set , take no action if or is not a set. Otherwise choose an integer with , and apply Lemma 6.1 with , placing all new elements above . The nested union is a set. Every omitted integer has a permanent finite obstruction to its insertion, so is maximal. It is infinite, since any finite nonempty set can be enlarged by an integer greater than times its maximum.
We check the count on the whole tail, not just at the chosen thresholds. At the smallest element of a new block, is already at least the total cardinality after that block. Until the next block starts, the count is at most this cardinality and cannot decrease. This proves for every sufficiently large . For , it follows that . Every superset of equals by maximality, and therefore none has positive normalized upper limit.
The order is fixed throughout these constructions. No infinite subset of can be a set for unbounded orders. Indeed, any three of its elements satisfy . Both sides have terms, and their multisets are distinct. Adding the same number of copies of to both sides gives a nontrivial equality at every larger order. The preceding results do not determine the optimal density constant or necessary and sufficient conditions for retaining an infinite initial set.
Declaration of generative AI and AI-assisted technologies
The authors used a large language model during the preparation of this manuscript for assistance with mathematical exploration, checking arguments, organization and language editing. The authors are responsible for the mathematical statements, proofs, references and final text.
References
School of Mathematical Sciences, Tiangong University, Tianjin 300387, P.R. China
Email address: [email protected]
Center for Combinatorics, Nankai University, Tianjin 300071, P.R. China
Email address: [email protected]
References
- [1]M. Ajtai, J. Komlós and E. Szemerédi, A dense infinite Sidon sequence, European J. Combin. 2 (1981), no. 1, 1–11.DOI
- [2]R. C. Bose and S. Chowla, Theorems in the additive theory of numbers, Comment. Math. Helv. 37 (1962/1963), 141–147.DOI
- [3]S. Chen, On Sidon sequences of even orders, Acta Arith. 64 (1993), no. 4, 325–330.DOI
- [4]Y.-G. Chen and J.-H. Fang, Dense perfect difference sets constructed from Sidon sets, J. Combin. Theory Ser. A 225 (2027), article 106239 (online 2026).DOI
- [5]J. Cilleruelo, Infinite Sidon sequences, Adv. Math. 255 (2014), 474–486.arxiv.org/abs/1209.0326
- [6]J. Cilleruelo and M. B. Nathanson, Perfect difference sets constructed from Sidon sets, Combinatorica 28 (2008), 401–414.arxiv.org/abs/math/0609244
- [7]J. Cilleruelo and M. B. Nathanson, Dense sets of integers with prescribed representation functions, European J. Combin. 34 (2013), 1297–1306. The positive-limsup question is stated on p. 4 of arXiv:0708.2853v1 (2007).
- [8]P. Erdős and P. Turán, On a problem of Sidon in additive number theory, and on some related problems, J. London Math. Soc. 16 (1941), no. 4, 212–215.
- [9]C. A. Gómez Ruiz and C. A. Trujillo Solarte, Una nueva construcción de conjuntos B_h modulares, Matemáticas: Enseñanza Universitaria 19 (2011), no. 1, 53–62.
- [10]D. J. Hajela, Construction techniques for some thin sets in duals of compact abelian groups, Ann. Inst. Fourier (Grenoble) 36 (1986), no. 3, 137–166.DOI
- [11]H. Halberstam and K. F. Roth, Sequences, revised edition, Springer-Verlag, New York–Berlin, 1983. Originally published by Clarendon Press, Oxford, 1966.
- [12]M. Hall, Jr., Cyclic projective planes, Duke Math. J. 14 (1947), 1079–1090.DOI
- [13]M. Helm, On the distribution of B_3-sequences, J. Number Theory 58 (1996), no. 1, 124–129.
- [14]F. Krückeberg, B_2-Folgen und verwandte Zahlenfolgen, J. Reine Angew. Math. 206 (1961), 53–60.
- [15]K. O’Bryant, A complete annotated bibliography of work related to Sidon sequences, Electron. J. Combin. (2004), Dynamic Survey 11, 39 pp.DOI
- [16]K. O’Bryant, On the Thickness of Infinite Generalized Sidon Sets, I, arXiv:2606.28651v3 (2026).arxiv.org/abs/2606.28651
- [17]K. O’Bryant, On the Thickness of Infinite Generalized Sidon Sets, II, arXiv:2607.23795v1 (26 July 2026), Section 5. Revised version, arXiv:2607.23795v2 (9 November 2026), Section 5.3.arxiv.org/abs/2607.23795
- [18]M. Th. Rassias, Solved and Unsolved Problems, EMS Newsletter 105 (September 2017), 55–60. Section II: Two combinatorial problems by Endre Szemerédi; Problem 186(d), p. 56.
- [19]R. Riblet and T. Schehr, Existence of a Sidon set for the distinct distance constant, Acta Math. Hungar. 178 (2026), 323–338.arxiv.org/abs/2505.20851
- [20]D. Ruiz and C. Trujillo, Construction of B_h[g] sets in product of groups, Rev. Colombiana Mat. 50 (2016), no. 2, 165–174.
- [21]I. Z. Ruzsa, An infinite Sidon sequence, J. Number Theory 68 (1998), 1–63–71.DOI
- [22]I. Z. Ruzsa, Solving a linear equation in a set of integers I, Acta Arith. 65 (1993), 259–282.DOI