betaFeedback

WorksMathematics

Infinite Generalized Sidon Sets with a Negative Answer to a Problem of Szemerédi

Abstract

Let A(x)=∣A∩[1,x]∣A(x)=|A\cap[1,x]|. For every integer h≥3h\ge3, every finite BhB_h set A0⊆NA_0\subseteq\mathbb N, and every 0<c≤h−2/h0<c\le h^{-2/h}, we construct an infinite BhB_h set A⊆NA\subseteq\mathbb N containing A0A_0 such that A(x)/x1/hA(x)/x^{1/h} has upper limit cc and lower limit zero. This extends the range 0<c≤1/h0<c\le1/h 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 h=3h=3, a positive upper limit disproves the assertion A(x)=o(x1/3)A(x)=o(x^{1/3}) 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 rr-element multisets for each fixed 1≤r<h1\le r<h. These gaps ensure that successive blocks can be adjoined by translation while preserving the BhB_h property. The same prescribed limits can be attained inside every set of asymptotic density one containing A0A_0. Separately, we construct 2ℵ02^{\aleph_0} extensions of A0A_0 that are maximal among all BhB_h subsets of N\mathbb N, have the prescribed limits, and avoid any prescribed finite subset of N∖A0\mathbb N\setminus A_0. These maximal extensions can be chosen so that ∑a∈Aa−1/h\sum_{a\in A}a^{-1/h} diverges arbitrarily slowly.

Introduction

Throughout the paper, hh is an integer with h≥2h\ge2. Let N={1,2,…}\mathbb{N}=\{1,2,\ldots\}. A set A⊆ZA\subseteq\mathbb{Z} is a BhB_h set if a1+⋯+ah=a1′+⋯+ah′a_1+\cdots+a_h=a'_1+\cdots+a'_h, with all summands in AA, implies equality of the two multisets of summands. Repetitions are permitted. For A⊆NA\subseteq\mathbb{N}, let A(x)=∣A∩[1,x]∣A(x)=|A\cap[1,x]|. A nonempty BhB_h set is also a BrB_r set for 1≤r<h1\le r<h, by adding the same h−rh-r terms to both sides of an equality. The distinct hh-term sums of a finite BhB_h set S⊆[1,n]S\subseteq[1,n] give

∣S∣hh!≤(∣S∣+h−1h)≤hn,∣S∣≤(h!hn)1/h.(1)\frac{|S|^h}{h!}\le\binom{|S|+h-1}{h}\le hn,\qquad|S|\le(h!hn)^{1/h}. \tag*{(1)}

Thus the natural density scale is x1/hx^{1/h}.

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 1/21/\sqrt{2}. Cilleruelo and Nathanson [7] observed that, for each h≥3h\ge3 and each function ω(x)→∞\omega(x)\to\infty, one can construct an infinite BhB_h set GG with lim sup⁡x→∞ω(x)G(x)/x1/h>0\limsup_{x\to\infty}\omega(x)G(x)/x^{1/h}>0 by dilating successive blocks. Their 2007 preprint identified the existence of a positive upper limit without the factor ω(x)\omega(x) as open. O’Bryant [17 v1, Section 5] later conjectured that such a set exists for every h≥3h\ge3. In the first version of this paper, we constructed an extension of every finite BhB_h set with normalized upper limit 1/h1/h and lower limit zero. This settled the existence question for h≥3h\ge3, as O’Bryant records in [17 v2, Section 5.3]. Proportional thinning while retaining the initial set gives each 0<c≤1/h0<c\le1/h. Here we enlarge that range to 0<c≤h−2/h0<c\le h^{-2/h} for h≥3h\ge3.

We include h=2h=2 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 b≥1/2b\ge1/\sqrt{2}, retaining the initial set and a proportion c/bc/b of the remaining terms gives each 0<c≤1/20<c\le1/\sqrt{2}.

Keywords. Generalized Sidon sets, Szemerédi problem, infinite Sidon sequences.

Theorem 1.1. Let h≥2h \ge2, let A0⊆NA_0 \subseteq\mathbb{N} be a finite BhB_h set, and define

ch={1/2,h=2,h−2/h,h≥3.c_h = \begin{cases} 1/\sqrt{2}, & h=2,\\ h^{-2/h}, & h \ge3. \end{cases}

For every 0<c≤ch0 < c \le c_h, there is an infinite BhB_h set A⊆NA \subseteq\mathbb{N} containing A0A_0 such that

lim sup⁡x→∞A(x)x1/h=c,lim inf⁡x→∞A(x)x1/h=0.(2)\limsup_{x\to\infty}\frac{A(x)}{x^{1/h}}=c,\qquad\liminf_{x\to\infty}\frac{A(x)}{x^{1/h}}=0. \tag*{(2)}

For h=3h=3, our first version disproved the assertion A(x)=o(x1/3)A(x)=o(x^{1/3}) in Szemerédi’s Problem 186(d) [18 p. 56] by attaining upper limit 1/31/3. Theorem 1.1 raises this value to 3−2/33^{-2/3}. This full-limit assertion is distinct from the question whether every infinite B3B_3 set has normalized lower limit zero. Helm [13] discusses the latter question and rules out A(x)∼αx1/3A(x)\sim\alpha x^{1/3} for α>0\alpha>0, 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 N\mathbb{N}.

Theorem 1.2. Let E⊆NE \subseteq\mathbb{N} have density one, and let A0⊆EA_0 \subseteq E be a finite BhB_h set. For every 0<c≤ch0 < c \le c_h, there is an infinite BhB_h set AA with A0⊆A⊆EA_0 \subseteq A \subseteq E 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 N\mathbb{N} can also coexist with the limits in (1.2). A BhB_h set is maximal if no further positive integer can be adjoined while preserving the BhB_h property.

Theorem 1.3. Let A0⊆NA_0 \subseteq\mathbb{N} be a finite BhB_h set, and let F⊆N∖A0F \subseteq\mathbb{N}\setminus A_0 be finite. For every 0<c≤ch0 < c \le c_h, there are 2ℵ02^{\aleph_0} infinite maximal BhB_h sets A⊆NA \subseteq\mathbb{N} containing A0A_0, disjoint from FF, 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 1≤r<h1 \le r < h, however, the translation cancels, and a mixed relation becomes

∑i=1rei−∑i=1rei′=∑j=1h−rsj′−∑j=1h−rsj.\sum_{i=1}^{r} e_i-\sum_{i=1}^{r} e_i'=\sum_{j=1}^{h-r} s_j'-\sum_{j=1}^{h-r} s_j.

If the old set lies in [1,n][1,n], the right side has absolute value at most hnhn. For each fixed 1≤r<h1 \le r < h, our finite blocks ensure that sums of distinct rr-element multisets differ by more than hnhn. In our first version we encoded the finite-field moment curve of [10, 20] in base hqhq and proved the separation estimate that yields upper limit 1/h1/h. For the improved constant h−2/hh^{-2/h} 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 h=2h=2 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 h≥3h \ge3, Cilleruelo constructs a BhB_h set with A(x)=x(h−1)2+1−(h−1)+o(1)A(x)=x^{\sqrt{(h-1)^2+1}-(h-1)+o(1)}. 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 1/h1/h 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 aa, let [a]q∈{0,…,q−1}[a]_q \in\{0,\ldots,q-1\} be its representative modulo qq.

Step 1. The old set and the prime. Start with a finite nonempty BhB_h set S⊆[1,n]S \subseteq[1,n], where nn is a positive integer, and choose a prime q>hnq > hn. The value n=max⁡Sn = \max S is permitted. The parameters satisfy

h≤hn<q,∣S∣q≤(h!hn)1/hq<(h!)1/hq1/h−1.(3)h \le hn < q,\qquad\frac{|S|}{q} \le\frac{(h!hn)^{1/h}}{q} < (h!)^{1/h}q^{1/h-1}. \tag*{(3)}

Step 2. The finite block. Choose a nonempty block Eq⊆[0,dqh)E_q \subseteq[0,dq^h) of integers, where d≥1d \ge1 is an integer fixed throughout the recursion. The moment-curve choice is

fq(a)=∑j=1h[aj]q(hq)h−j,Eq={fq(a):0≤a<q},d=hh−1.(4)f_q(a)=\sum_{j=1}^{h}[a^j]_q(hq)^{h-j},\qquad E_q=\{f_q(a):0\le a<q\},\qquad d=h^{h-1}. \tag*{(4)}

The other choices in Lemmas 2.3 and 2.4 have d=hd=h and d=1d=1, respectively; the second is available only for h=2h=2.

Step 3. The required block properties. Each chosen EqE_q is a BhB_h set, and sums of distinct rr-element multisets from it differ by more than hnhn whenever 1≤r<h1 \le r < h. For the block in (2.2), ∣Eq∣=q|E_q|=q, and for distinct parameter multisets,

∣∑i=1rfq(ai)−∑i=1rfq(ai′)∣≥hq−r(q−1)>q>hn(1≤r<h).(5)\left|\sum_{i=1}^{r}f_q(a_i)-\sum_{i=1}^{r}f_q(a'_i)\right|\ge hq-r(q-1)>q>hn\qquad(1\le r<h). \tag*{(5)}

Step 4. The translation and the enlarged set. Define

M=(h−1)dqh+q,S′=S∪(M+Eq).(6)M=(h-1)dq^h+q,\qquad S'=S\cup(M+E_q). \tag*{(6)}

Then S′S' is a BhB_h set, n<M≤M+e<hdqh+qn<M\le M+e<hdq^h+q for every e∈Eqe\in E_q, and ∣S′∣=∣S∣+∣Eq∣|S'|=|S|+|E_q|. Its normalized count at the endpoint is

∣S′∣(hdqh+q)1/h=∣S∣/q+∣Eq∣/q(hd+q1−h)1/h.\frac{|S'|}{(hdq^h+q)^{1/h}}=\frac{|S|/q+|E_q|/q}{(hd+q^{1-h})^{1/h}}.

Step 5. Iteration. Start with S0=A0S_0=A_0 if A0≠∅A_0\ne\varnothing, and with {1}\{1\} otherwise. At stage kk, choose qk>hmax⁡Sk−1q_k>h\max S_{k-1} and a block satisfying Step 3 with n=max⁡Sk−1n=\max S_{k-1}, and define

Mk=(h−1)dqkh+qk,nk=hdqkh+qk,M_k=(h-1)dq_k^h+q_k,\qquad n_k=hdq_k^h+q_k,
Sk=Sk−1∪(Mk+Eqk),U=⋃k≥0Sk.(7)S_k=S_{k-1}\cup(M_k+E_{q_k}),\qquad U=\bigcup_{k\ge0}S_k. \tag*{(7)}

Here nkn_k is an upper endpoint, not necessarily an element of SkS_k. Larger bounds for the old set and correspondingly larger primes may also be used. The set UU is an infinite BhB_h set containing A0A_0.

Step 6. Density. Whenever ∣Eqk∣/qk→1|E_{q_k}|/q_k\to1, the source set satisfies

U(nk)nk1/h⟶(hd)−1/h,U(Mk−1)(Mk−1)1/h⟶0,nkMk−1⟶hh−1.(8)\frac{U(n_k)}{n_k^{1/h}}\longrightarrow(hd)^{-1/h},\qquad \frac{U(M_k-1)}{(M_k-1)^{1/h}}\longrightarrow0,\qquad \frac{n_k}{M_k-1}\longrightarrow\frac{h}{h-1}. \tag*{(8)}

For the moment-curve choice the normalized upper limit is exactly 1/h1/h. Using the logarithmic block for h≥3h\ge3 and the Sidon block for h=2h=2, selection gives every prescribed upper limit up to chc_h. In the Sidon deletion construction, ∣Eqk∣/qk→1|E_{q_k}|/q_k\to1 is ensured by making the old bound negligible relative to qkq_k.

The next lemma proves that the extension in (6) is a BhB_h set and also permits the larger translations used later inside a prescribed ambient set.

Lemma 2.1. Let S⊆[1,n]S \subseteq[1,n] be a finite nonempty BhB_h set, and let E⊆[0,D)E \subseteq[0,D) be a finite nonempty BhB_h set of integers, where n,Dn,D are positive integers. Suppose that sums of distinct rr-element multisets from EE differ by more than hnhn for every 1≤r<h1 \le r < h. For every integer M≥(h−1)D+hn+1M \ge(h-1)D+hn+1, the set S∪(M+E)S \cup(M+E) is a BhB_h set, and the new block lies above SS.

Proof. We first prove that equal sums contain the same number of new terms. Since M>nM>n, the old and new sets are disjoint. If one hh-term sum contains rr new terms and the other contains s<rs<r, their difference is at least

(r−s)M−sD−(h−s)n≥M−(h−1)D−hn>0.(r-s)M-sD-(h-s)n \ge M-(h-1)D-hn>0.

Here the first sum is at least rMrM, whereas the second is at most s(M+D)+(h−s)ns(M+D)+(h-s)n; also s≤h−1s \le h-1. Exchanging the sums excludes the case r<sr<s. If r=0r=0 or r=hr=h, the BhB_h property of SS or EE identifies the summands, after cancellation of the translation when r=hr=h.

We resolve the remaining case 1≤r<h1 \le r < h by the shorter-sum gap. Let e1,…,ere_1,\ldots,e_r and e1′,…,er′e'_1,\ldots,e'_r be the new parameters, and let s1,…,sh−rs_1,\ldots,s_{h-r} and s1′,…,sh−r′s'_1,\ldots,s'_{h-r} be the old terms on the two sides. Cancellation gives

∑i=1rei−∑i=1rei′=∑j=1h−rsj′−∑j=1h−rsj,∣∑j=1h−rsj′−∑j=1h−rsj∣≤(h−r)(n−1)≤hn.\sum_{i=1}^{r}e_i-\sum_{i=1}^{r}e'_i=\sum_{j=1}^{h-r}s'_j-\sum_{j=1}^{h-r}s_j,\qquad\left|\sum_{j=1}^{h-r}s'_j-\sum_{j=1}^{h-r}s_j\right|\le(h-r)(n-1)\le hn.

The gap hypothesis forces the new multisets to agree. After cancelling them, add the same rr copies of any fixed element of the nonempty set SS to both old sums. The BhB_h property of SS 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 h=2h=2, the integer encoding 2qa+[a2]q2qa+[a^2]_q is the Erdős–Turán construction [8].

Lemma 2.2. For a prime q>hq>h, the set in (4) is a BhB_h set of qq elements, the map a↦fq(a)a \mapsto f_q(a) is strictly increasing, and

a(hq)h−1≤fq(a)<(a+1)(hq)h−1≤hh−1qh(0≤a<q).(9)a(hq)^{h-1}\le f_q(a)<(a+1)(hq)^{h-1}\le h^{h-1}q^h\qquad(0\le a<q). \tag*{(9)}

For 1≤r<h1\le r<h, sums of distinct rr-element parameter multisets differ by at least hq−r(q−1)>qhq-r(q-1)>q after applying fqf_q.

Proof. We first prove the range and cardinality assertions. Since [a]q=a[a]_q=a for 0≤a<q0\le a<q, the terms after a(hq)h−1a(hq)^{h-1} in fq(a)f_q(a) satisfy

0≤fq(a)−a(hq)h−1≤q−1hq−1((hq)h−1−1)<(hq)h−1.0\le f_q(a)-a(hq)^{h-1}\le\frac{q-1}{hq-1}\left((hq)^{h-1}-1\right)<(hq)^{h-1}.

This proves (9). The intervals for consecutive parameters are disjoint and ordered, so fqf_q is strictly increasing and ∣Eq∣=q|E_q|=q.

We next identify the power sums that distinguish two parameter multisets. For two rr-tuples in Fq\mathbb{F}_q with common power sums pjp_j, 1≤j≤r<q1\le j\le r<q, let ej,ej′e_j,e'_j be their elementary symmetric functions and e0=e0′=1e_0=e'_0=1. Newton’s identities give

j(ej−ej′)=∑i=1j(−1)i−1(ej−i−ej−i′)pi(1≤j≤r).j(e_j-e'_j)=\sum_{i=1}^{j}(-1)^{i-1}(e_{j-i}-e'_{j-i})p_i\qquad(1\le j\le r).

Since each jj is invertible in Fq\mathbb{F}_q, induction gives ej=ej′e_j=e'_j. 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 1≤r<h1\le r<h and distinct multisets of parameters a1,…,ara_1,\ldots,a_r and a1′,…,ar′a'_1,\ldots,a'_r in {0,…,q−1}\{0,\ldots,q-1\}. For each power 1≤j≤h1 \le j \le h, let uj=∑i=1r[aij]q−∑i=1r[(ai′)j]qu_j = \sum_{i=1}^{r}[a_i^j]_q-\sum_{i=1}^{r}[(a_i')^j]_q; then ∣uj∣≤r(q−1)|u_j| \le r(q-1). The preceding power-sum argument shows that not all u1,…,uru_1,\ldots,u_r are zero. Let ℓ≤r\ell\le r be the first index with uℓ≠0u_\ell\ne0. Its coefficient has absolute value at least one, so

∣∑i=1rfq(ai)−∑i=1rfq(ai′)∣=∣∑j=ℓhuj(hq)h−j∣≥(hq)h−ℓ−r(q−1)∑j=0h−ℓ−1(hq)j=1+(hq−1−r(q−1))∑j=0h−ℓ−1(hq)j.\begin{aligned} \left|\sum_{i=1}^{r}f_q(a_i)-\sum_{i=1}^{r}f_q(a_i')\right|=\left|\sum_{j=\ell}^{h}u_j(hq)^{h-j}\right| \\ &\ge(hq)^{h-\ell}-r(q-1)\sum_{j=0}^{h-\ell-1}(hq)^j \\ &=1+\left(hq-1-r(q-1)\right)\sum_{j=0}^{h-\ell-1}(hq)^j. \end{aligned}

An empty sum here is zero. Since hq−1−r(q−1)≥h−1>0hq-1-r(q-1)\ge h-1>0, the last expression is at least one; taking r=hr=h proves the BhB_h property. If r<hr<h, then ℓ<h\ell<h and the geometric sum is at least one. The same expression is therefore at least hq−r(q−1)≥q+h−1>qhq-r(q-1)\ge q+h-1>q, 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 q>hq>h, there is a BhB_h set Eq⊆[0,hqh)E_q\subseteq[0,hq^h) with qq elements if h≥3h\ge3 and q−1q-1 elements if h=2h=2. For 1≤r<h1\le r<h, sums of distinct rr-element multisets from EqE_q differ by at least hq−r(q−1)>qhq-r(q-1)>q.

Proof. We first define the parameters and their integer representatives. Let θ\theta generate the multiplicative group Fqh−1×\mathbb{F}_{q^{h-1}}^{\times}. Its degree over Fq\mathbb{F}_q is h−1h-1: if this degree were ℓ<h−1\ell<h-1, the field Fq(θ)\mathbb{F}_q(\theta) would have qℓq^\ell elements, so the order qh−1−1q^{h-1}-1 of θ\theta would be at most qℓ−1q^\ell-1, a contradiction. For a∈Fqa\in\mathbb{F}_q with θ+a≠0\theta+a\ne0, let [a]q[a]_q be its representative in {0,…,q−1}\{0,\ldots,q-1\} and define

θbq(a)=θ+a,0≤bq(a)<qh−1−1,\theta^{b_q(a)}=\theta+a,\qquad0\le b_q(a)<q^{h-1}-1,
fq(a)=hq bq(a)+[a]q,Eq={fq(a):a∈Fq, θ+a≠0}.(10)f_q(a)=hq\,b_q(a)+[a]_q,\qquad E_q=\{f_q(a):a\in\mathbb{F}_q,\ \theta+a\ne0\}. \tag*{(10)}

The chosen generator gives a unique integer bq(a)b_q(a) in the indicated range. When h≥3h\ge3, the degree of θ\theta is at least two, so θ∉Fq\theta\notin\mathbb{F}_q and every a∈Fqa\in\mathbb{F}_q is permitted. When h=2h=2, exactly the parameter a=−θa=-\theta is excluded.

We next check the size and range in the statement. If fq(a)=fq(a′)f_q(a)=f_q(a'), reduction modulo hqhq gives [a]q=[a′]q[a]_q=[a']_q, since both remainders lie in [0,q)[0,q). Thus a=a′a=a'. This proves the asserted cardinality. Moreover,

0≤fq(a)≤hq(qh−1−2)+(q−1)<hqh.0\le f_q(a)\le hq(q^{h-1}-2)+(q-1)<hq^h.

These are integer inequalities, whereas the defining equation for θbq(a)\theta^{b_q(a)} is an equation in Fqh−1\mathbb{F}_{q^{h-1}}.

We prove the BhB_h property by comparing two sums of hh block elements. Let a1,…,aha_1,\ldots,a_h and a1′,…,ah′a_1',\ldots,a_h' be their respective parameters, with repetitions allowed, and suppose that ∑i=1hfq(ai)=∑i=1hfq(ai′)\sum_{i=1}^{h}f_q(a_i)=\sum_{i=1}^{h}f_q(a_i'). The definition in (2.8) gives

hq(∑i=1hbq(ai)−∑i=1hbq(ai′))=−∑i=1h[ai]q+∑i=1h[ai′]q.hq\left(\sum_{i=1}^{h}b_q(a_i)-\sum_{i=1}^{h}b_q(a_i')\right)=-\sum_{i=1}^{h}[a_i]_q+\sum_{i=1}^{h}[a_i']_q.

The absolute value of the right side is at most h(q−1)<hqh(q-1)<hq. It is a multiple of hqhq, so it is zero. Both the sums of the integer representatives [ai]q[a_i]_q and the sums of the integer logarithms bq(ai)b_q(a_i) therefore agree. We now recover the parameters from these two equalities. Reduction of the first equality modulo qq gives ∑ai=∑ai′\sum a_i=\sum a_i' in Fq\mathbb{F}_q, and exponentiation of θ\theta in the second gives ∏(θ+ai)=∏(θ+ai′)\prod(\theta+a_i)=\prod(\theta+a_i'). Consequently the polynomial

∏i=1h(X+ai)−∏i=1h(X+ai′)∈Fq[X]\prod_{i=1}^{h}(X+a_i)-\prod_{i=1}^{h}(X+a_i')\in\mathbb{F}_q[X]

vanishes at θ\theta. Its coefficients of XhX^h cancel because the products are monic, and its coefficients of Xh−1X^{h-1} cancel because the parameter sums agree. Its degree is at most h−2h-2, below the degree h−1h-1 of θ\theta, so it is the zero polynomial. Unique factorization identifies the parameter multisets, including their multiplicities. The corresponding multisets of fq(ai)f_q(a_i) are equal, proving the BhB_h property. This argument also covers h=2h=2, when the difference is a constant polynomial.

We finally separate all shorter sums. Fix 1≤r<h1\le r<h and two distinct multisets of rr permitted parameters. Equality of their integer logarithm sums would imply equality of the products at θ\theta. The difference of the two monic degree-rr products has degree at most r−1<h−1r-1<h-1, 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

∣∑i=1rfq(ai)−∑i=1rfq(ai′)∣≥hq−r(q−1)≥hq−(h−1)(q−1)=q+h−1>q.\left|\sum_{i=1}^{r}f_q(a_i)-\sum_{i=1}^{r}f_q(a_i')\right|\ge hq-r(q-1)\ge hq-(h-1)(q-1)=q+h-1>q.

This proves the separation required for every r<hr<h. □

For h=2h=2, the preceding block gives an attainable upper limit of 1/21/2 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 qq and a positive integer nn, there is a Sidon set Eq⊆[0,q2)E_q\subseteq[0,q^2) with q−2n≤∣Eq∣≤qq-2n\le|E_q|\le q, whose distinct elements differ by more than 2n2n.

Proof. We first construct a Sidon set with qq elements. Let θ\theta generate Fq2×\mathbb{F}_{q^2}^{\times}, and take the integer representatives bq(a)b_q(a) defined by

θbq(a)=θ+a,0≤bq(a)<q2−1,a∈Fq.\theta^{b_q(a)}=\theta+a,\qquad0\le b_q(a)<q^2-1,\qquad a\in\mathbb{F}_q.

The degree of θ\theta is two, so every parameter is permitted. Different parameters give different representatives. If bq(a1)+bq(a2)=bq(a1′)+bq(a2′)b_q(a_1)+b_q(a_2)=b_q(a_1')+b_q(a_2') as integers, exponentiation gives equal quadratic products at θ\theta. Their monic leading coefficients cancel, leaving a polynomial of degree at most one that vanishes at θ\theta. 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 2n2n with at most 2n2n deletions. In a Sidon set, a positive difference has at most one ordered representation: if u−v=u′−v′u-v=u'-v', then u+v′=u′+vu+v'=u'+v. Equality of the two unordered pairs implies either u=u′u=u' and v=v′v=v', or u=vu=v and u′=v′u'=v'. The second possibility contradicts positivity. For each integer difference in {1,…,2n}\{1,\ldots,2n\} that occurs, mark the larger endpoint of its unique pair, and delete all marked elements. At most 2n2n 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 22–33, with fixed dd and qk>hmax⁡Sk−1q_k>h\max S_{k-1}. Then UU is an infinite BhB_h set containing A0A_0, and

U(nk)=∣Sk∣=∣Sk−1∣+∣Eqk∣,U(Mk−1)=∣Sk−1∣.(11)U(n_k)=|S_k|=|S_{k-1}|+|E_{q_k}|,\qquad U(M_k-1)=|S_{k-1}|. \tag*{(11)}

Moreover, qk→∞q_k\to\infty.

Proof. We first verify each finite extension and the infinite union. At stage kk, apply Lemma 2.1 with n=max⁡Sk−1n=\max S_{k-1}, D=dqkhD=dq_k^h and the chosen block EqkE_{q_k}. The integer inequality qk>hnq_k>hn gives Mk≥(h−1)D+hn+1M_k\ge(h-1)D+hn+1. Induction proves that every SkS_k is a finite BhB_h set and that the new block lies above all old elements. Each block is nonempty, so ∣Sk∣→∞|S_k|\to\infty and qk>hmax⁡Sk−1→∞q_k>h\max S_{k-1}\to\infty. Any equality of hh-term sums in UU involves finitely many elements, all contained in one SkS_k. Its BhB_h property proves the same property for UU.

We next check that later blocks do not affect the recorded counts. All elements of SkS_k lie below nkn_k, and max⁡Sk≥Mk\max S_k\ge M_k since the new block is nonempty. Consequently

Mk+1>qk+1>hmax⁡Sk≥hMk>nk,hMk−nk=h(h−2)dqkh+(h−1)qk>0.M_{k+1}>q_{k+1}>h\max S_k\ge hM_k>n_k,\qquad hM_k-n_k=h(h-2)dq_k^h+(h-1)q_k>0.

Thus U∩[1,nk]=SkU\cap[1,n_k]=S_k. Before MkM_k only Sk−1S_{k-1} 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 1/h1/h.

Lemma 3.1. Under the hypotheses of Lemma 2.5, if ∣Eqk∣/qk→1|E_{q_k}|/q_k\to1, then the three limits in (8) hold. In particular, UU has normalized upper limit at least (hd)−1/h(hd)^{-1/h} and normalized lower limit zero.

Proof. We first bound the old count relative to the new block size. By (3), applied with S=Sk−1S=S_{k-1}, n=max⁡Sk−1n=\max S_{k-1} and q=qk>hnq=q_k>hn,

∣Sk−1∣qk≤(h!hn)1/hqk<(h!)1/hqk1/h−1⟶0.(12)\frac{|S_{k-1}|}{q_k}\le\frac{(h!hn)^{1/h}}{q_k}<(h!)^{1/h}q_k^{1/h-1}\longrightarrow0. \tag*{(12)}

Here qk→∞q_k\to\infty by Lemma 2.5.

We determine the limits by dividing the counts in (11) by the corresponding scales. The recursion gives

nk1/hqk⟶(hd)1/h,(Mk−1)1/hqk⟶((h−1)d)1/h.\frac{n_k^{1/h}}{q_k}\longrightarrow(hd)^{1/h},\qquad\frac{(M_k-1)^{1/h}}{q_k}\longrightarrow((h-1)d)^{1/h}.

Together with (12) and ∣Eqk∣/qk→1|E_{q_k}|/q_k\to1, these prove the first two limits in (8). Taking the ratio of nkn_k and Mk−1M_k-1 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 U⊆NU\subseteq\mathbb{N} be an infinite BhB_h set, let P⊆UP\subseteq U satisfy P(x)=o(x1/h)P(x)=o(x^{1/h}), and let b=lim sup⁡x→∞U(x)/x1/h>0b=\limsup_{x\to\infty}U(x)/x^{1/h}>0. For every 0<c≤b0<c\le b, there is a BhB_h set AA with P⊆A⊆UP\subseteq A\subseteq U such that

A(x)=P(x)+⌊cb(U(x)−P(x))⌋=cbU(x)+o(x1/h).(13)A(x)=P(x)+\left\lfloor\frac{c}{b}(U(x)-P(x))\right\rfloor=\frac{c}{b}U(x)+o(x^{1/h}). \tag*{(13)}

If PP is finite, the error in the last equality is OP(1)O_P(1). The normalized upper limit of AA is cc; if the normalized lower limit of UU is zero, then that of AA is also zero.

Proof. We first choose the retained elements outside PP. The bound (1) makes bb finite. The set U∖PU\setminus P is infinite, since otherwise U(x)=P(x)+O(1)=o(x1/h)U(x)=P(x)+O(1)=o(x^{1/h}). Enumerate its elements in increasing order as u1,u2,…u_1,u_2,\ldots. Retain uju_j exactly when ⌊cj/b⌋>⌊c(j−1)/b⌋\lfloor cj/b\rfloor>\lfloor c(j-1)/b\rfloor, and include every element of PP. Since 0<c/b≤10<c/b\le1, each increase is either zero or one. Among the first ll elements outside PP, the number retained is the telescoping sum ⌊cl/b⌋\lfloor cl/b\rfloor. Taking l=U(x)−P(x)l=U(x)-P(x) proves the first equality in (3.2).

We next determine the counting error and the limiting values. The first equality gives A(x)−(c/b)U(x)=(1−c/b)P(x)+O(1)A(x)-(c/b)U(x)=(1-c/b)P(x)+O(1). This is o(x1/h)o(x^{1/h}), and it is bounded when PP is finite. Division by x1/hx^{1/h} now gives the claimed upper and lower limits. The positive upper limit makes AA infinite, and A⊆UA \subseteq U preserves the BhB_h property. □

For the improved blocks, let d2=1d_2=1 and dh=hd_h=h for h≥3h\geq3, so that ch=(hdh)−1/hc_h=(hd_h)^{-1/h}.

Proof of Theorem 1.1. We choose the blocks in (7) with d=dhd=d_h. Let n0=max⁡S0n_0=\max S_0 and, at stage kk, choose a prime qk>hnk−1q_k>hn_{k-1}. For h≥3h\geq3 use Lemma 2.3. For h=2h=2 use Lemma 2.4 with old bound nk−1n_{k-1}, and additionally require qk>knk−1q_k>kn_{k-1}. The first blocks have qkq_k elements; the second have between qk−2nk−1q_k-2n_{k-1} and qkq_k elements. Thus ∣Eqk∣/qk→1|E_{q_k}|/q_k\to1 in both cases. Their shorter-sum gaps exceed hnk−1hn_{k-1}, which is at least hmax⁡Sk−1h\max S_{k-1}, so Lemma 2.5 applies.

We obtain the exact upper limit by selection. Lemma 3.1 gives b=lim sup⁡U(x)/x1/h≥chb=\limsup U(x)/x^{1/h}\geq c_h and lower limit zero. The endpoint calculation alone does not exclude larger values inside a block. Apply Lemma 3.2 with P=A0P=A_0 and 0<c≤ch≤b0<c\leq c_h\leq b 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 d=h−1d=h^{-1}, the recursion (7) gives an infinite BhB_h set U⊇A0U\supseteq A_0 satisfying

lim sup⁡x→∞U(x)x1/h=1h,lim inf⁡x→∞U(x)x1/h=0.\limsup_{x\to\infty}\frac{U(x)}{x^{1/h}}=\frac{1}{h},\qquad\liminf_{x\to\infty}\frac{U(x)}{x^{1/h}}=0.

Any primes qk>hmax⁡Sk−1q_k>h\max S_{k-1} may be used.

Proof. We first determine the endpoint density and the lower limit. Lemma 2.2 gives ∣Eqk∣=qk|E_{q_k}|=q_k. Lemmas 2.5 and 3.1, with d=h−1d=h^{-1}, therefore give upper limit at least (hh)−1/h=1/h(h^h)^{-1/h}=1/h and lower limit zero.

We next bound the count at every point in a new block. Fix kk, abbreviate q=qkq=q_k, and consider x=Mk+fq(a)x=M_k+f_q(a) with 0≤a<q0\leq a<q. Lemma 2.5 ensures that no later block contributes to U(x)U(x), and fqf_q is strictly increasing by Lemma 2.2. Hence U(x)=∣Sk−1∣+a+1U(x)=|S_{k-1}|+a+1. The lower bound in (9) gives, for t=a/qt=a/q,

x≥hh−1qh(h−1+t),U(x)x1/h≤t+(∣Sk−1∣+1)/qh(h−1)/h(h−1+t)1/h.x\geq h^{h-1}q^h(h-1+t),\qquad\frac{U(x)}{x^{1/h}}\leq\frac{t+(|S_{k-1}|+1)/q}{h^{(h-1)/h}(h-1+t)^{1/h}}.

For 0≤t≤10\leq t\leq1, we have h−1+t≥hth-1+t\geq ht. Thus the term involving tt is at most t1−1/h/h≤1/ht^{1-1/h}/h\leq1/h, with value zero at t=0t=0. The remaining term is at most

(∣Sk−1∣+1)/q(hh−1(h−1))1/h⟶0\frac{(|S_{k-1}|+1)/q}{(h^{h-1}(h-1))^{1/h}}\longrightarrow0

by (12), independently of aa. Hence the block estimate is uniform.

We finally extend the estimate to all sufficiently large real xx. If uu is the last element of UU at most xx, then U(x)=U(u)U(x)=U(u) and U(x)/x1/h≤U(u)/u1/hU(x)/x^{1/h}\leq U(u)/u^{1/h}. As x→∞x\to\infty, the element uu 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 1/h1/h and hence equality. □

For h=3h=3, the moment-curve block and translation are explicitly

Eq={9q2a+3q[a2]q+[a3]q:0≤a<q},M=18q3+q,q>3max⁡S.E_q=\{9q^2a+3q[a^2]_q+[a^3]_q:0\leq a<q\},\qquad M=18q^3+q,\qquad q>3\max S.

The proposition gives upper limit 1/31/3 for this construction; Theorem 1.1 permits every value up to 3−2/33^{-2/3}. Both conclusions concern the full-limit assertion discussed in the introduction.

Growth between dense scales

The size of qkq_k 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 d=dhd=d_h. The notation ≍\asymp means upper and lower bounds by positive constant multiples, with fixed parameters permitted in the constants.

Proposition 4.1. Let h≥3h\ge3, let A0⊆NA_0\subseteq\mathbb{N} be a finite BhB_h set, and let 0<c≤ch0<c\le c_h and t≥1t\ge1. The set in Theorem 1.1 can be chosen so that

A(x)≫x1/(h2t),lim inf⁡x→∞log⁡A(x)log⁡x=1h2t,lim sup⁡x→∞log⁡A(x)log⁡x=1h.A(x)\gg x^{1/(h^2t)},\qquad\liminf_{x\to\infty}\frac{\log A(x)}{\log x}=\frac{1}{h^2t},\qquad\limsup_{x\to\infty}\frac{\log A(x)}{\log x}=\frac{1}{h}.

The implied constant may depend on h,t,c,A0h,t,c,A_0.

Proof. We first choose the prime sizes to control the successive endpoints. Bertrand’s theorem permits a prime between ⌈hnkt⌉\lceil hn_k^t\rceil and 2⌈hnkt⌉2\lceil hn_k^t\rceil. Thus in (7) we can require hnk−1t<qk<2hnk−1t+2hn_{k-1}^t<q_k<2hn_{k-1}^t+2. Since t≥1t\ge1, the original condition qk>hnk−1q_k>hn_{k-1} holds. The endpoint formula and (8) give

nk≍qkh≍nk−1ht,∣Sk∣≍qk≍nk−11/h.(14)n_k\asymp q_k^h\asymp n_{k-1}^{ht},\qquad|S_k|\asymp q_k\asymp n_{k-1}^{1/h}. \tag*{(14)}

The constants in these comparisons are independent of kk.

We next prove the lower bound at every sufficiently large scale. For nk−1≤x<nkn_{k-1}\le x<n_k, monotonicity of the count and (14) yield

U(x)≥∣Sk−1∣≫nk−11/h≫nk1/(h2t)≥x1/(h2t).U(x)\ge|S_{k-1}|\gg n_{k-1}^{1/h}\gg n_k^{1/(h^2t)}\ge x^{1/(h^2t)}.

Let b=lim sup⁡U(x)/x1/hb=\limsup U(x)/x^{1/h} and apply Lemma 3.2 with P=A0P=A_0. Then A(x)=(c/b)U(x)+OA0(1)A(x)=(c/b)U(x)+O_{A_0}(1), where c/b>0c/b>0 is fixed. Since U(x)→∞U(x)\to\infty, 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 kkth block, U(Mk−1)=∣Sk−1∣U(M_k-1)=|S_{k-1}|. Equations (7) and (14) give

log⁡∣Sk−1∣=1hlog⁡nk−1+O(1),log⁡(Mk−1)=htlog⁡nk−1+O(1).\log|S_{k-1}|=\frac{1}{h}\log n_{k-1}+O(1),\qquad\log(M_k-1)=ht\log n_{k-1}+O(1).

Their quotient tends to 1/(h2t)1/(h^2t). The bounded-error selection changes the numerator by O(1)O(1), because ∣Sk−1∣→∞|S_{k-1}|\to\infty. 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 log⁡A(x)/log⁡x≤1/h+o(1)\log A(x)/\log x\le1/h+o(1). Since the normalized upper limit of AA is c>0c>0, along a sequence A(x)/x1/h→cA(x)/x^{1/h}\to c; on that sequence the logarithmic quotient tends to 1/h1/h. This proves the remaining equality. □

For h=2h=2, the constants require a separate distinction. The logarithmic block in Lemma 2.3 has q−1q-1 elements in [0,2q2)[0,2q^2), so the same proof gives every 0<c≤1/20<c\le1/2 and exponent 1/(4t)1/(4t) for t≥1t\ge1. For the full range 0<c≤1/20<c\le1/\sqrt{2}, use Lemma 2.4 and take t>1t>1. The choice of qk≍nk−1tq_k\asymp n_{k-1}^t then gives nk−1/qk→0n_{k-1}/q_k\to0, as required to make the deletions negligible. At the endpoint exponent 1/41/4, choose instead qk≍nk−1log⁡nk−1q_k\asymp n_{k-1}\log n_{k-1} once nk−1>1n_{k-1}>1. Here

log⁡nk=2log⁡nk−1+2log⁡log⁡nk−1+O(1),log⁡∣Sk−1∣=12log⁡nk−1+O(1).\log n_k=2\log n_{k-1}+2\log\log n_{k-1}+O(1),\qquad\log|S_{k-1}|=\frac{1}{2}\log n_{k-1}+O(1).

We obtain an explicit lower bound on the intervals between endpoints. The same choice of primes gives

∣Sk−1∣≍nk−11/2≍nk1/4log⁡nk.|S_{k-1}|\asymp n_{k-1}^{1/2}\asymp\frac{n_k^{1/4}}{\sqrt{\log n_k}}.

Since x1/4/log⁡xx^{1/4}/\sqrt{\log x} is increasing for x>e2x > e^2, the inequality U(x)≥∣Sk−1∣U(x) \ge|S_{k-1}| for nk−1≤x<nkn_{k-1} \le x < n_k gives U(x)≫x1/4/log⁡xU(x) \gg x^{1/4}/\sqrt{\log x}. The fixed positive proportion and bounded error in (13) therefore give A(x)≫x1/4/log⁡xA(x) \gg x^{1/4}/\sqrt{\log x}. The values at Mk−1M_k-1 still give lower logarithmic exponent 1/41/4.

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 h=2h=2, the existence of a Sidon set with ∑a∈Aa−1/2=∞\sum_{a\in A}a^{-1/2}=\infty was proved by Riblet and Schehr [19 Corollary 3.4]. For h≥3h\ge3, divergence of ∑a∈Aa−1/h\sum_{a\in A}a^{-1/h} 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 A0A_0 and cc satisfy Theorem 1.1. Given positive functions g1,g2g_1,g_2 tending to infinity and any sequence yk→∞y_k\to\infty, the set AA can satisfy (2) and

∑a∈Aa−1/h=∞,∑a∈Aa≤xa−1/h=o(g1(x)).\sum_{a\in A}a^{-1/h}=\infty,\qquad\sum_{\substack{a\in A\\a\le x}}a^{-1/h}=o(g_1(x)).

It can also have scales xk<zkx_k<z_k, with xk≥ykx_k\ge y_k, such that

A(xk)g2(xk)⟶0,A(zk)zk1/h⟶c,lim sup⁡k→∞zkxk≤hh−1.\frac{A(x_k)}{g_2(x_k)}\longrightarrow0,\qquad\frac{A(z_k)}{z_k^{1/h}}\longrightarrow c,\qquad\limsup_{k\to\infty}\frac{z_k}{x_k}\le\frac{h}{h-1}.

Proof. We first impose the size requirements during the recursion (7). Once Sk−1S_{k-1} is fixed, choose qkq_k large enough that

Mk−1≥max⁡j≤kyj,g2(Mk−1)≥k∣Sk−1∣,g1(x)≥k2for every x≥Mk.(15)M_k-1\ge\max_{j\le k}y_j,\qquad g_2(M_k-1)\ge k|S_{k-1}|,\qquad g_1(x)\ge k^2\quad\text{for every }x\ge M_k. \tag*{(15)}

Also keep qk>hnk−1q_k>hn_{k-1} and, for h=2h=2, qk>knk−1q_k>kn_{k-1}. These choices are possible because both functions tend to infinity: each required lower bound holds at every argument beyond a threshold, and Mk→∞M_k\to\infty as qk→∞q_k\to\infty. This uses no monotonicity assumption.

We next bound the critical sum of the source set. Every new block has at most qkq_k elements, all at least Mk≥qkhM_k\ge q_k^h. Its contribution to ∑a−1/h\sum a^{-1/h} is therefore at most qk(qkh)−1/h=1q_k(q_k^h)^{-1/h}=1. For Mk≤x<Mk+1M_k\le x<M_{k+1}, only the initial set and the first kk blocks contribute, so

∑a∈Ua≤xa−1/hg1(x)≤∑a∈S0a−1/h+kk2⟶0.\frac{\sum_{\substack{a\in U\\a\le x}}a^{-1/h}}{g_1(x)} \le\frac{\sum_{a\in S_0}a^{-1/h}+k}{k^2}\longrightarrow0.

Select AA by Lemma 3.2, with P=A0P=A_0. The partial-sum bound passes to A⊆UA\subseteq U, and (2) holds.

We prove divergence from the positive normalized upper limit. For fixed yy and x>yx>y, each a≤xa\le x satisfies x−1/h≤a−1/hx^{-1/h}\le a^{-1/h}, whence

A(x)x1/h≤A(y)x1/h+∑a∈Aa>ya−1/h.\frac{A(x)}{x^{1/h}}\le\frac{A(y)}{x^{1/h}}+\sum_{\substack{a\in A\\a>y}}a^{-1/h}.

If the series converged, taking the upper limit as x→∞x\to\infty and then letting y→∞y\to\infty would give c≤0c\le0. This contradicts c>0c>0 and proves divergence.

We finally locate the requested dense and sparse scales after the selection. Between consecutive elements of AA, the count is constant and its quotient by x1/hx^{1/h} decreases. Thus the upper limit cc can be approached at elements of AA. Choose such elements zjz_j in blocks with strictly increasing indices kjk_j. This is possible because each block is finite. Let xj=Mkj−1x_j=M_{k_j}-1. Then (15) gives

xj≥yj,A(xj)g2(xj)≤∣Skj−1∣g2(Mkj−1)≤1kj⟶0.x_j\ge y_j,\qquad\frac{A(x_j)}{g_2(x_j)}\le\frac{|S_{k_j-1}|}{g_2(M_{k_j}-1)}\le\frac{1}{k_j}\longrightarrow0.

Here kj≥jk_j\ge j explains why the prefix maximum in (15) suffices even if (yj)(y_j) is not increasing. Since Mkj≤zj<nkjM_{k_j}\le z_j<n_{k_j}, we have xj<zjx_j<z_j and zj/xj≤nkj/(Mkj−1)z_j/x_j\le n_{k_j}/(M_{k_j}-1). Equation (8) proves the ratio bound. ▫

Taking g2(x)=log⁡(x+1)g_2(x)=\log(x+1) gives lower logarithmic exponent zero: at the scales xkx_k, eventually A(xk)≤log⁡(xk+1)A(x_k)\le\log(x_k+1), whereas log⁡A(x)/log⁡x≥0\log A(x)/\log x\ge0 for all sufficiently large xx. Together with Proposition 4.1, this realizes every lower logarithmic exponent in [0,1/h2][0,1/h^2] for h≥3h\ge3, while retaining any prescribed c∈(0,ch]c\in(0,c_h]. For comparison, every BhB_h set satisfies ∑a∈Aa−s<∞\sum_{a\in A}a^{-s}<\infty when s>1/hs>1/h: by (1), the contribution from [2j,2j+1)[2^j,2^{j+1}) is Oh(2j(1/h−s))O_h(2^{j(1/h-s)}), a summable geometric bound.

Corollary 4.3. For every BhB_h set satisfying (2), the subsequential limits of A(x)/x1/hA(x)/x^{1/h} form exactly the interval [0,c][0,c].

Proof. We first show that consecutive normalized counts have vanishing differences. Since A(n+1)−A(n)∈{0,1}A(n+1)-A(n)\in\{0,1\} and A(n)=Oh(n1/h)A(n)=O_h(n^{1/h}),

∣A(n+1)(n+1)1/h−A(n)n1/h∣≤(n+1)−1/h+Oh(1)(1−(nn+1)1/h)⟶0.\left|\frac{A(n+1)}{(n+1)^{1/h}}-\frac{A(n)}{n^{1/h}}\right|\le(n+1)^{-1/h}+O_h(1)\left(1-\left(\frac{n}{n+1}\right)^{1/h}\right)\longrightarrow0.

We next obtain every intermediate limit by a crossing argument. Fix 0<s<c0<s<c. The lower and upper limits in (2) give arbitrarily late indices with values below ss and above ss. Choose a value below ss and a later value above ss, and take the first index in between with value at least ss. Its distance from ss is at most the preceding consecutive difference, which tends to zero as the starting index tends to infinity. Thus ss is a subsequential limit. The endpoints 0,c0,c are subsequential limits by their definitions, and no value outside [0,c][0,c] is permitted by (2). For real xx, setting n=⌊x⌋n=\lfloor x\rfloor gives A(x)=A(n)A(x)=A(n) and n/x→1n/x\to1, 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 BhB_h 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 E⊆NE\subseteq\mathbb{N}. The notation EqE_q continues to mean a finite block, whereas EE 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 SS lie in E∩[1,n]E\cap[1,n], fix 0<w<10<w<1, and use the blocks of Theorem 1.1, with width dhqhd_hq^h. Choose the prime q>hnq>hn sufficiently large that

nq≤w,q≤(1−w)dhqh,wdhqh≥1,∣[1,(h+1)dhqh]∖E∣≤w2dhqh.\frac{n}{q}\le w,\qquad q\le(1-w)d_hq^h,\qquad wd_hq^h\ge1,\qquad\left|[1,(h+1)d_hq^h]\setminus E\right|\le w^2d_hq^h.

The last requirement follows from density one with fixed ww. Let M=(h−1)dhqh+qM=(h-1)d_hq^h+q. For every integer tt between MM and M+⌊wdhqh⌋M+\lfloor wd_hq^h\rfloor, all of t+Eqt+E_q lies in [1,(h+1)dhqh][1,(h+1)d_hq^h]. We prove the retained-cardinality estimate by averaging. For a fixed e∈Eqe\in E_q, distinct translations give distinct integers t+et+e, so at most w2dhqhw^2d_hq^h translations send ee outside EE. Summing this bound over e∈Eqe\in E_q, and using at least wdhqhwd_hq^h available translations, gives a translation tt for which at most w∣Eq∣w|E_q| elements are lost. Hence

∣(t+Eq)∩E∣≥(1−w)∣Eq∣,M≤t≤M+wdhqh,(t+Eq)∩E⊆[1,(h+w)dhqh+q].(16)|(t+E_q)\cap E|\ge(1-w)|E_q|,\qquad M\le t\le M+wd_hq^h,\qquad(t+E_q)\cap E\subseteq[1,(h+w)d_hq^h+q]. \tag*{(16)}

This nonempty retained block can be appended to SS by Lemma 2.1.

We next iterate the retained blocks while controlling their endpoints. Start from A0A_0, or one point of EE if A0A_0 is empty, and choose wk→0w_k\to0. At each stage let nn be the preceding integer endpoint, and take the next endpoint to be ⌈(h+wk)dhqkh+qk⌉\lceil(h+w_k)d_hq_k^h+q_k\rceil. The next translation exceeds this endpoint because its prime exceeds hnhn. Thus later stages do not change counts at earlier endpoints. The logarithmic blocks have qkq_k elements for h≥3h\ge3; for h=2h=2, the condition n/qk≤wkn/q_k\le w_k gives ∣Eqk∣≥(1−2wk)qk|E_{q_k}|\ge(1-2w_k)q_k. It follows from (16) that each added block has (1−o(1))qk(1-o(1))q_k elements. Its endpoint divided by qkhq_k^h tends to dhd_h, so the source upper limit is at least chc_h.

We finally prove the zero lower limit and select the exact upper limit. Immediately before each chosen translation tkt_k, only the old set contributes. By (1) and qk>hnq_k>hn its cardinality is Oh(n1/h)=o(qk)O_h(n^{1/h})=o(q_k), whereas (tk−1)1/h≫hqk(t_k-1)^{1/h}\gg_h q_k. Thus the source has normalized lower limit zero. Every finite stage is a BhB_h set by the extension lemma. Any comparison of two hh-term sums in the nested union involves finitely many elements and hence lies in one finite stage, so the union is a BhB_h set. Lemma 3.2, with P=A0P=A_0, yields the requested cc while retaining containment in EE.

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 E⊆NE\subseteq\mathbb{N} have upper density v>0v>0, and let A0⊆EA_0\subseteq E be a finite BhB_h set. For every

0<c≤chv1+1/h2(h+1)(h+1+v/h)1/h,0<c\le\frac{chv^{1+1/h}}{2(h+1)(h+1+v/h)^{1/h}},

there is an infinite BhB_h set AA with A0⊆A⊆EA_0\subseteq A\subseteq E satisfying (2). In particular, 0<c≤chv1+1/h/60<c\le c_hv^{1+1/h}/6 is permitted.

Proof. We first choose a block size relative to a dense endpoint. Fix the old bound nn and 0<w<hv/(4(h+1))0<w<hv/(4(h+1)). There are arbitrarily large integers xx with E(x)≥(v−w)xE(x)\ge(v-w)x. Bertrand’s theorem permits a prime

(vx2hh(h+1)dh)1/h<q≤2(vx2hh(h+1)dh)1/h.(17)\left(\frac{vx}{2^h h(h+1)d_h}\right)^{1/h}<q\le2\left(\frac{vx}{2^h h(h+1)d_h}\right)^{1/h}. \tag*{(17)}

Taking such an xx large enough ensures q>hnq>hn, n/q≤wn/q\le w and q≤wxq\le wx. The upper bound on qq also gives hdhqh≤vx/(h+1)h d_hq^h\le vx/(h+1). Use the appropriate block of Theorem 1.1 and let

M=(h−1)dhqh+q.M=(h-1)d_hq^h+q.

We next average over all integer translations M≤t≤xM\le t\le x. For e∈Eq⊆[0,dhqh)e\in E_q\subseteq[0,d_hq^h) and y∈E∩[hdhqh+q,x]y\in E\cap[h d_hq^h+q,x], the integer t=y−et=y-e satisfies M≤t≤xM\le t\le x. For fixed ee, different yy give different translations. Counting these pairs yields

∑t=Mx∣(t+Eq)∩E∣≥∣Eq∣(E(x)−hdhqh−q)≥(hvh+1−2w)x∣Eq∣.\begin{aligned} \sum_{t=M}^{x}|(t+E_q)\cap E|\ge|E_q|\bigl(E(x)-h d_hq^h-q\bigr) \\ &\ge\left(\frac{hv}{h+1}-2w\right)x|E_q|. \end{aligned}

There are at most xx translations in the sum, so at least one retains the proportion hv/(h+1)−2w>0hv/(h+1)-2w>0 of EqE_q. The retained set lies below x+dhqhx+d_hq^h, and its union with the old set is a BhB_h set by Lemma 2.1.

We compute the density supplied by this retained block. As w→0w\to0, the condition n/q≤wn/q\le w makes ∣Eq∣/q→1|E_q|/q\to1, including in the Sidon case. The lower bound on qq in (17) and the upper bound dhqh≤vx/(h(h+1))d_hq^h\le vx/(h(h+1)) give

q(x+dhqh)1/h≥chv1/h2(h+1+v/h)1/h.\frac{q}{(x+d_hq^h)^{1/h}}\ge\frac{c_hv^{1/h}}{2(h+1+v/h)^{1/h}}.

Multiplication by the limiting retained proportion hv/(h+1)hv/(h+1) 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 wk→0w_k\to0, starting from A0A_0 or one point of EE, and use x+dhqhx+d_hq^h as the next old bound. Later blocks then lie above each recorded endpoint. Immediately before a new translation tt, only the old set contributes, with cardinality Oh(n1/h)=o(q)O_h(n^{1/h})=o(q). Since t≥(h−1)dhqh+qt\ge(h-1)d_hq^h+q, the normalized count there tends to zero. The nested union is a BhB_h subset of EE, and Lemma 3.2 with P=A0P=A_0 gives every stated cc. Finally, h+1+v/h≤2hh+1+v/h\le2^h for h≥2h\ge2 and 0<v≤10<v\le1, while h/(h+1)≥2/3h/(h+1)\ge2/3. Therefore the displayed constant is at least chv1+1/h/6c_hv^{1+1/h}/6.

Corollary 5.2. In a positive arithmetic progression of common difference mm, every finite BhB_h initial set extends to an infinite BhB_h set satisfying (2) for any 0<c≤chm−1/h0<c\le c_hm^{-1/h}. In every rr-colouring of N\mathbb{N}, some colour contains a BhB_h set satisfying (2) with c=ch/rc=c_h/r.

Proof. We first transfer the progression assertion to N\mathbb{N}. For the progression {a+mn:n≥0}\{a+mn:n\ge0\}, with a,m≥1a,m\ge1, the map u↦a+m(u−1)u\mapsto a+m(u-1) is a bijection from N\mathbb{N}. An equality of two hh-term sums in its image cancels the common translation h(a−m)h(a-m) and the nonzero factor mm. Thus this map and its inverse on the progression preserve the BhB_h property. Apply Theorem 1.1 to the inverse image of the seed, with upper limit cm1/h≤chcm^{1/h}\le c_h. The image count is U((x−a)/m+1)U((x-a)/m+1). As ((x−a)/m+1)/x→1/m((x-a)/m+1)/x\to1/m, its normalized limits are cc and zero.

We next obtain the colouring assertion from a finite partition. Choose a set UU with upper limit chc_h and lower limit zero. Let U1,…,UrU_1,\ldots,U_r be its colour parts. Since U(x)=∑iUi(x)U(x)=\sum_i U_i(x), ch≤∑ilim sup⁡Ui(x)/x1/hc_h\le\sum_i\limsup U_i(x)/x^{1/h}. One part therefore has upper limit at least ch/rc_h/r. It is infinite and inherits the zero lower limit from UU. Lemma 3.2, with empty prescribed set, selects within this part a set with upper limit exactly ch/rc_h/r. 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 BhB_h set is necessary for any extension.

Proposition 5.3. Let E⊆NE\subseteq\mathbb{N} have density one, let P={b1<b2<⋯ }P=\{b_1<b_2<\cdots\} lie in EE, and let A0⊆EA_0\subseteq E be finite with A0∪PA_0\cup P a BhB_h set. If eventually bk+1>(4h2)hbkhb_{k+1}>(4h^2)^{h}b_k^h, then for every 0<c≤h−2/h0<c\le h^{-2/h} there is an infinite BhB_h set AA with A0∪P⊆A⊆EA_0\cup P\subseteq A\subseteq E satisfying (2). If instead bk+1/bkh→∞b_{k+1}/b_k^h\to\infty, the full range 0<c≤ch0<c\le c_h is permitted.

The stronger separation enlarges the range of cc only for h=2h=2, from 1/21/2 to 1/21/\sqrt{2}; for h≥3h\ge3 both ranges coincide.

Proof. We first justify the insertion of an isolated prescribed element. Let SS be a finite nonempty BhB_h set of positive integers and let b>hmax⁡Sb>h\max S. In a comparison of two hh-term sums from S∪{b}S\cup\{b\}, let r>sr>s be the multiplicities of bb on the two sides. The first sum minus the second is at least (r−s)b−(h−s)max⁡S≥b−hmax⁡S>0(r-s)b-(h-s)\max S\ge b-h\max S>0. Equal sums must therefore have the same multiplicity of bb. Cancelling those copies and padding with the same old element reduces to the BhB_h property of SS. Hence S∪{b}S\cup\{b\} is a BhB_h set.

We next construct the blocks under the fixed gap bound. Choose k0k_0 so large that bk0>max⁡(A0∪{0})b_{k_0}>\max(A_0\cup\{0\}) and all subsequent size conditions hold, and start with A0∪{b1,…,bk0}A_0\cup\{b_1,\ldots,b_{k_0}\}. Suppose the current maximum is bkb_k. Choose a prime bk<q≤2hbkb_k<q\le2hb_k using Lemma 2.3 for every h≥2h\ge2. This block has q+O(1)q+O(1) elements in [0,hqh)[0,hq^h). No estimate bk/q→0b_k/q\to0 is required here, since no Sidon deletion is performed.

We place almost all of this block in EE with a small additional translation. Density one and q→∞q\to\infty permit wk→0w_k\to0 such that

wkhqh≥1,∣[1,(h+1)hqh]∖E∣≤wk2hqh.w_kh q^h\ge1,\qquad\left|[1,(h+1)h q^h]\setminus E\right|\le w_k^2h q^h.

For all large kk, a possible choice is wk=max⁡{(hqh)−1/2,(∣[1,(h+1)hqh]∖E∣/(hqh))1/2}w_k=\max\{(h q^h)^{-1/2},(|[1,(h+1)h q^h]\setminus E|/(h q^h))^{1/2}\}. Since q/(hqh)→0q/(h q^h)\to0, we also have q≤(1−wk)hqhq\le(1-w_k)h q^h for all large kk. The averaging argument proving (16), with width hqhh q^h, gives a compatible block of (1−o(1))q(1-o(1))q elements below (h+wk)hqh+q(h+w_k)h q^h+q. The separate condition n/q→0n/q\to0 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 kk, the preceding endpoint is at most (h+1)hqh+q(h+1)h q^h+q, and q≤2hbkq\le2hb_k gives

h((h+1)hqh+q)≤2h3qh≤(2hq)h≤(4h2)hbkh<bk+1.h((h+1)h q^h+q)\le2h^3q^h\le(2hq)^h\le(4h^2)^h b_k^h<b_{k+1}.

The first inequality uses q≤qhq\le q^h and h2+h+1≤2h2h^2+h+1\le2h^2. For the second, 2h3≤(2h)h2h^3\le(2h)^h is an equality when h=2h=2, and follows from (2h)h≥(2h)2(2h)^h\ge(2h)^2 when h≥3h\ge3. Thus bk+1b_{k+1} exceeds hh times the new maximum. The first paragraph permits its insertion and restores the old maximum to bk+1b_{k+1} for the next stage. We treat the stronger gap condition using larger intermediate primes. Choose

(bkhbk+1)1/(2h)<q≤2(bkhbk+1)1/(2h).\left(b_k^h b_{k+1}\right)^{1/(2h)} < q \le2\left(b_k^h b_{k+1}\right)^{1/(2h)}.

Then q/bk→∞q/b_k \to\infty and qh/bk+1≤2h(bkh/bk+1)1/2→0q^h/b_{k+1} \le2^h\left(b_k^h/b_{k+1}\right)^{1/2} \to0. For all large kk the inequality q>hbkq > hb_k holds. Use the blocks of Theorem 1.1, now including the Sidon deletion when h=2h=2. Its loss is at most 2bk=o(q)2b_k=o(q). Density-one averaging retains (1−o(1))q(1-o(1))q elements, with endpoint (h+o(1))dhqh+q=Oh(qh)=o(bk+1)(h+o(1))d_hq^h+q=O_h(q^h)=o(b_{k+1}). Increasing k0k_0 if needed ensures that this endpoint is less than bk+1/hb_{k+1}/h at every stage. The same singleton argument again inserts bk+1b_{k+1}.

We determine the normalized limits of these two sources. Each finite stage is a BhB_h subset of EE, so each nested union is an infinite BhB_h set containing A0∪PA_0\cup P. In the first construction the dense endpoints have (1−o(1))q(1-o(1))q new elements below (h2+o(1))qh(h^2+o(1))q^h, giving upper limit at least h−2/hh^{-2/h}. In the second the corresponding bound is (hdh+o(1))qh(hd_h+o(1))q^h, giving upper limit at least chc_h. Immediately before each block, the count is that of a finite BhB_h set with maximum bkb_k, hence is Oh(bk1/h)=o(q)O_h(b_k^{1/h})=o(q). The scale is comparable to qhq^h, so both lower limits are zero.

We finally check that selection can retain the entire infinite seed. Either gap assumption implies bk+1≥2bkhb_{k+1}\ge2b_k^h eventually. For a sufficiently large fixed index k0k_0 with bk0>1b_{k_0}>1, iteration gives log⁡bk0+j≥hjlog⁡bk0\log b_{k_0+j}\ge h^j\log b_{k_0}. Thus bk0+j≤xb_{k_0+j}\le x forces j=Oh(log⁡log⁡(x+3))j=O_h(\log\log(x+3)), and P(x)=Oh,P(log⁡log⁡(x+3))=o(x1/h)P(x)=O_{h,P}(\log\log(x+3))=o(x^{1/h}). Adding the finite set A0A_0 does not change this estimate. Lemma 3.2, with prescribed subset A0∪PA_0\cup P, therefore gives the exact upper limits claimed. □

Proposition 5.4. Let E⊆NE\subseteq\mathbb{N} have density one, and prescribe 0<ci≤ch0<c_i\le c_h for each positive integer ii. There are pairwise disjoint infinite sets Ai⊆EA_i\subseteq E, each satisfying (1.2) with c=cic=c_i, whose union is a BhB_h set. A finite family of pairwise disjoint finite subsets of EE can be retained in the corresponding sets if its union is a BhB_h 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 EE and give it label 1. Use the label sequence 1;1,2;1,2,3;…1; 1,2; 1,2,3; \ldots, 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 wk→0w_k\to0, and give every element of the new block that stage’s label. All new blocks lie above the previous endpoint, so the labelled portions UiU_i are pairwise disjoint. Every finite union in the recursion is a BhB_h set; consequently their infinite union UU is also a BhB_h set.

We next verify the required limits separately for each label. Immediately before any new block, the total old count is o(qk)o(q_k), so UU has normalized lower limit zero. Since Ui⊆UU_i\subseteq U, every UiU_i inherits this zero lower limit. At every endpoint assigned label ii, its new block alone contributes (1−o(1))qk(1-o(1))q_k elements below (hdh+o(1))qkh(hd_h+o(1))q_k^h. There are infinitely many such endpoints for each ii, so lim sup⁡Ui(x)/x1/h≥ch\limsup U_i(x)/x^{1/h}\ge c_h and UiU_i is infinite. Apply Lemma 3.2 separately to UiU_i, retaining its finite seed and selecting upper limit cic_i. The resulting sets remain disjoint, and their union is a subset of UU, so it retains the BhB_h property. □

Maximal extensions

A BhB_h subset of N\mathbb{N} is maximal if no further positive integer can be adjoined while preserving the BhB_h property. For h=2h=2, Cilleruelo and Nathanson [6 Theorem 1.3] constructed a perfect difference set P⊆NP\subseteq\mathbb{N} with lim sup⁡P(x)/x≥1/2\limsup P(x)/\sqrt{x}\ge1/\sqrt{2}. Such a set is maximal Sidon because adjoining u∉Pu\notin P repeats the nonzero difference u−au-a for any a∈Pa\in P. Chen and Fang [4 Theorem 1.1] proved that for every Sidon set BB one can even choose a perfect difference set PP with ∣P(x)−B(x/2)∣≤ω(x)|P(x)-B(x/2)|\le\omega(x) for any prescribed positive ω(x)→∞\omega(x)\to\infty.

When only the upper limit is prescribed, the construction in [6 Section 3] also yields every 0<c≤1/20<c\le1/\sqrt{2}. Indeed, put α=c2\alpha=c\sqrt{2}. If ll is the current maximum, their prime p>4l2p>4l^2 gives a translated block of p−O(p)p-O(\sqrt{p}) points in p2+2l+[1,p2−p]p^2+2l+[1,p^2-p]. Retain [αj][\alpha j] of the first jj points for each jj. At step kk, adjoin their auxiliary pair for kk 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 N\mathbb{N}.

Before this final translation, consider x=p2+2l+yx=p^2+2l+y with 0≤y≤p20\le y\le p^2. The old set contributes at most l+1=o(p)l+1=o(p) points. The finite Sidon bound [16 Lemma 4] gives at most y+O(y1/4+1)\sqrt{y}+O(y^{1/4}+1) points from the full block up to xx, hence at most αy+o(p)\alpha\sqrt{y}+o(p) from the retained block, uniformly in yy. Since y/(p2+y)≤1/2\sqrt{y}/(p^2+y)\le1/\sqrt{2}, the normalized count is at most c+o(1)c+o(1). At x=2p2+2lx=2p^2+2l it is (αp+o(p))/2p2+2l=c+o(1)(\alpha p+o(p))/\sqrt{2p^2+2l}=c+o(1). Up to the next block, the auxiliary pair adds at most two points, so the upper limit is exactly cc.

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 p>k\sqrt{p}>k at step kk and place every addition beyond the finite exclusions. Each stage adds O(1)O(1) to the critical series. Choose pp so that g1(x)≥k2g_1(x)\ge k^2 for x≥p2x\ge p^2 and, at xk=p2+2lx_k=p^2+2l, we have xk≥ykx_k\ge y_k and the old count is at most g2(xk)/kg_2(x_k)/k. The dense endpoint is at most 2xk2x_k. 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 S⊆NS\subseteq\mathbb{N} be a finite nonempty BhB_h set and let u∈N∖Su\in\mathbb{N}\setminus S. Above any prescribed bound, one can adjoin 2h−12h-1 distinct elements to obtain a BhB_h set S′S' such that S′∪{u}S'\cup\{u\} is not a BhB_h set.

Proof. For a positive integer parameter tt, define

ai=t2i,bi=t2i−1(1≤i<h),bh=u+∑i=1h−1ai−∑i=1h−1bi.a_i=t^{2i},\qquad b_i=t^{2i-1}\quad(1\le i<h),\qquad b_h=u+\sum_{i=1}^{h-1}a_i-\sum_{i=1}^{h-1}b_i.

For all sufficiently large tt, these elements are positive, distinct, and exceed both the given bound and every element of S∪{u}S\cup\{u\}. Indeed, bhb_h has leading term t2h−2t^{2h-2} and differs from ah−1a_{h-1} by a polynomial with leading term −t2h−3-t^{2h-3}; all other distinctions follow from their degrees. The relation b1+⋯+bh=u+a1+⋯+ah−1b_1+\cdots+b_h=u+a_1+\cdots+a_{h-1} prevents the insertion of uu.

Consider two distinct multisets of hh labels from SS and the new labels. Their sum difference is a polynomial in tt. Let ee be the difference of the multiplicities of bhb_h, and let ci,dic_i,d_i be those of ai,bia_i,b_i for i<hi<h. If the polynomial is identically zero, comparison of its even and odd powers gives ci=−ec_i=-e and di=ed_i=e. If e>0e>0, one side contains at least ee copies of each of the hh labels b1,…,bhb_1,\ldots,b_h. Its length forces e=1e=1 and that side to consist exactly of these labels. The other side then consists of a1,…,ah−1a_1,\ldots,a_{h-1} and one element s∈Ss\in S; the constant coefficient gives u=su=s, a contradiction. Exchanging the multisets excludes e<0e<0. If e=0e=0, all new multiplicities agree. After their cancellation, the old multisets agree by the BhB_h property of SS, with identical padding if their common length is less than hh. Thus no nontrivial comparison is identically zero. There are finitely many comparisons and each has finitely many integer roots, so every sufficiently large integer tt outside their union gives the required S′S'.

:::

In the following theorem maximality is taken in N\mathbb{N}.

Theorem 6.2. Let A0⊆NA_0\subseteq\mathbb{N} be a finite BhB_h set, and let F⊆N∖A0F\subseteq\mathbb{N}\setminus A_0 be finite. Given 0<c<ch0<c<c_h, positive functions g1,g2g_1,g_2 tending to infinity, and a sequence yk→∞y_k\to\infty, there are 2ℵ02^{\aleph_0} infinite maximal BhB_h sets A⊆NA\subseteq\mathbb{N} with A0⊆AA_0\subseteq A, A∩F=∅A\cap F=\varnothing, and (2). Each of these sets also satisfies

∑a∈Aa−1/h=∞,∑a∈Aa≤xa−1/h=o(g1(x)),\sum_{a\in A}a^{-1/h}=\infty,\qquad\sum_{\substack{a\in A\\a\le x}}a^{-1/h}=o(g_1(x)),

and has integer scales xk<zkx_k<z_k, with xk≥ykx_k\ge y_k, such that

A(xk)g2(xk)⟶0,A(zk)zk1/h⟶c,lim sup⁡k→∞zkxk≤hh−1.\frac{A(x_k)}{g_2(x_k)}\longrightarrow0,\qquad\frac{A(z_k)}{z_k^{1/h}}\longrightarrow c,\qquad\limsup_{k\to\infty}\frac{z_k}{x_k}\le\frac{h}{h-1}.

The functions g1,g2g_1,g_2 need not be monotone.

Proof. Start with A0A_0; if it is empty, start with one integer exceeding max⁡(F∪{0})\max(F \cup\{0\}). For each u∈Fu \in F, apply Lemma 6.1, placing all its new elements above FF and the current set. We obtain a nonempty finite BhB_h set S0S_0 containing A0A_0, disjoint from FF, and preventing the insertion of every element of FF. All elements of S0S_0 are declared forced and retained throughout. If a BhB_h superset of S0S_0 contained some u∈Fu \in F, it would contain S0∪{u}S_0 \cup\{u\}, contradicting the relation just imposed. Thus every later BhB_h extension of S0S_0 avoids FF.

Construct a binary tree of finite sets rooted at S0S_0. At level k≥1k \ge1, choose an integer threshold tkt_k exceeding max⁡S0\max S_0 and, when k≥2k \ge2, the full candidate endpoint at every node of level k−1k-1. Since each level has finitely many nodes and g1(x)→∞g_1(x) \to\infty, we may also require

tk>(k(∣S0∣+4hk+1))h,g1(x)≥k2for every x≥tk.(18)t_k > \left(k(|S_0| + 4hk + 1)\right)^h,\qquad g_1(x) \ge k^2 \quad\text{for every } x \ge t_k. \tag*{(18)}

At the first level it also exceeds max⁡S0\max S_0. For the current set SS, if k∉Sk \notin S and S∪{k}S \cup\{k\} is a BhB_h set, use Lemma 6.1 to prevent the insertion of kk, with all new terms above tkt_k and the current set. If kk is already present or already impossible to add, leave SS unchanged at this step.

Choose u>hmax⁡Su > h\max S with u>tku > t_k. In the first continuation adjoin uu; the singleton argument in Proposition 5.3 shows that this preserves the BhB_h property. In the second use Lemma 6.1 to prevent its insertion, placing all new elements above both uu and the current set. Call the elements added in these two steps forced elements. Each continuation receives fewer than 4h4h of them at level kk, all above tkt_k.

For each continuation, let SS be its current set and put n=max⁡Sn = \max S. Choose a prime qk>hnq_k > hn and the block from Theorem 1.1, with d=dhd = d_h. Define Mk,nkM_k,n_k as in (2.5), and require

∣S∣qk≤1k,Mk−1≥yk,g2(Mk−1)≥k∣S∣.\frac{|S|}{q_k} \le\frac{1}{k},\qquad M_k - 1 \ge y_k,\qquad g_2(M_k - 1) \ge k|S|.

For h=2h = 2 also require n/qk≤1/kn/q_k \le1/k. All conditions hold for sufficiently large primes, since g2(x)→∞g_2(x) \to\infty. The chosen block has all distinct shorter sums separated by more than hnhn, while

Mk=(h−1)dhqkh+qk≥(h−1)dhqkh+hn+1.M_k = (h-1)d_hq_k^h + q_k \ge(h-1)d_hq_k^h + hn + 1.

Lemma 2.1, with D=dhqkhD = d_hq_k^h, therefore applies to this current set SS, including its forced elements. For h≥3h \ge3 the block has qkq_k elements; for h=2h = 2 it has between qk−2nq_k - 2n and qkq_k elements. Consequently ∣Eqk∣/qk→1|E_{q_k}|/q_k \to1. Process the candidate elements aa in increasing order. If mm non-forced elements have already been retained along this branch, retain aa precisely when m+1≤⌊ca1/h⌋m + 1 \le\lfloor ca^{1/h}\rfloor. Forced additions do not change mm. Retaining a subset preserves the BhB_h property. All later additions must exceed nkn_k, 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 AA be the union of its finite sets. The thresholds tend to infinity, so the corresponding primes do also. Let WW consist of S0S_0 and all its forced elements, and let B=A∖WB = A \setminus W be the retained non-forced elements. Through level kk there are at most ∣S0∣+4hk|S_0| + 4hk forced elements. At any forced element of level kk, (6.1) therefore gives W(x)/x1/h<1/kW(x)/x^{1/h} < 1/k. Between consecutive forced elements this quotient decreases. There is a forced addition at every level, so W(x)=o(x1/h)W(x) = o(x^{1/h}). The counting threshold gives B(x)≤⌊cx1/h⌋B(x) \le\lfloor cx^{1/h}\rfloor, and hence lim sup⁡A(x)/x1/h≤c\limsup A(x)/x^{1/h} \le c.

At a rejected candidate aa, the preceding count mm is at most ⌊ca1/h⌋\lfloor ca^{1/h}\rfloor by the threshold at earlier candidates, but m+1m+1 exceeds it. Thus B(a)=⌊ca1/h⌋B(a) = \lfloor ca^{1/h}\rfloor. Later stages cannot change this value. Infinitely many rejections give upper limit at least cc. If only finitely many occur, every sufficiently late candidate block is retained in full. At such endpoints,

A(nk)nk1/h=∣S∣/qk+∣Eqk∣/qk(hdh+qk1−h)1/h⟶ch≥c.(19)\frac{A(n_k)}{n_k^{1/h}} = \frac{|S|/q_k + |E_{q_k}|/q_k}{(hd_h + q_k^{1-h})^{1/h}} \longrightarrow c_h \ge c. \tag*{(19)}

In both cases the upper limit equals cc. Immediately before each candidate block, A(Mk−1)=∣S∣A(M_k - 1) = |S| and (Mk−1)1/h≫hqk(M_k - 1)^{1/h} \gg_h q_k. Our choice ∣S∣/qk≤1/k|S|/q_k \le1/k therefore gives normalized lower limit zero.

The fewer than 4h4h forced elements of level kk contribute at most 4h/[k(∣S0∣+4hk+1)]≤14h/[k(|S_0| + 4hk + 1)] \le1 to the critical series by (6.1). A complete candidate block has at most qkq_k elements, each at least qkhq_k^h, so its contribution is also at most one. For xx from the first new element of level kk up to the first new element of level k+1k+1, excluding that last element, the partial sum is at most ∑a∈S0a−1/h+2k\sum_{a\in S_0} a^{-1/h}+2k, whereas g1(x)≥k2g_1(x)\ge k^2. These intervals cover all sufficiently large xx. Their quotient tends to zero. Positive normalized upper limit forces divergence by the tail estimate in Proposition 4.2.

Let xk=Mk−1x_k=M_k-1. Then xk≥ykx_k\ge y_k and A(xk)/g2(xk)≤1/kA(x_k)/g_2(x_k)\le1/k. If the candidate block has a rejected element, choose one as zkz_k; the equality for B(zk)B(z_k) and W(zk)=o(zk1/h)W(z_k)=o(z_k^{1/h}) give A(zk)/zk1/h→cA(z_k)/z_k^{1/h}\to c along these levels. Otherwise choose zk=nkz_k=n_k. 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 chc_h. They occur only finitely often if c<chc<c_h, by the upper bound already proved; if c=chc=c_h, they give the required limit as well. Finally xk<zk≤nkx_k<z_k\le n_k and nk/(Mk−1)→h/(h−1)n_k/(M_k-1)\to h/(h-1) by their definitions, proving the ratio bound.

Every finite stage is a BhB_h set, so every branch union is a BhB_h set by the finite-comparison argument. Each integer kk is either present or impossible to adjoin after level kk. The finite relation preventing its insertion is retained forever, so the union is maximal and still avoids FF. At the first differing continuation of two branches, one union contains the chosen uu, while the other retains a relation preventing its insertion. Their unions are different. The binary tree has 2ℵ02^{\aleph_0} infinite branches, and N\mathbb{N} 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 BhB_h extension. For h=2h=2, 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 A0⊆NA_0\subseteq\mathbb{N} be a finite BhB_h set, and let g:[1,∞)→(0,∞)g:[1,\infty)\to(0,\infty) be nondecreasing with g(x)→∞g(x)\to\infty. There is an infinite maximal BhB_h set P⊇A0P\supseteq A_0 such that P(x)≤g(x)P(x)\le g(x) for all sufficiently large xx. In particular, an arbitrary infinite BhB_h 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 A0A_0, or with {1}\{1\} if A0A_0 is empty, and process k=1,2,…k=1,2,\ldots. For the current finite set SS, take no action if k∈Sk\in S or S∪{k}S\cup\{k\} is not a BhB_h set. Otherwise choose an integer y>max⁡Sy>\max S with g(y)≥∣S∣+2g(y)\ge|S|+2, and apply Lemma 6.1 with u=ku=k, placing all new elements above yy. The nested union PP is a BhB_h set. Every omitted integer has a permanent finite obstruction to its insertion, so PP is maximal. It is infinite, since any finite nonempty BhB_h set can be enlarged by an integer greater than hh 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, gg is already at least the total cardinality after that block. Until the next block starts, the count is at most this cardinality and gg cannot decrease. This proves P(x)≤g(x)P(x)\le g(x) for every sufficiently large xx. For g(x)=log⁡(x+2)g(x)=\log(x+2), it follows that P(x)/x1/h→0P(x)/x^{1/h}\to0. Every BhB_h superset of PP equals PP by maximality, and therefore none has positive normalized upper limit.

The order hh is fixed throughout these constructions. No infinite subset of N\mathbb{N} can be a BhB_h set for unbounded orders. Indeed, any three of its elements a<b<ca<b<c satisfy (c−b)a+(b−a)c=(c−a)b(c-b)a+(b-a)c=(c-a)b. Both sides have c−ac-a terms, and their multisets are distinct. Adding the same number of copies of aa 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. [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. [2]R. C. Bose and S. Chowla, Theorems in the additive theory of numbers, Comment. Math. Helv. 37 (1962/1963), 141–147.DOI
  3. [3]S. Chen, On Sidon sequences of even orders, Acta Arith. 64 (1993), no. 4, 325–330.DOI
  4. [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. [5]J. Cilleruelo, Infinite Sidon sequences, Adv. Math. 255 (2014), 474–486.arxiv.org/abs/1209.0326
  6. [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. [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. [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. [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. [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. [11]H. Halberstam and K. F. Roth, Sequences, revised edition, Springer-Verlag, New York–Berlin, 1983. Originally published by Clarendon Press, Oxford, 1966.
  12. [12]M. Hall, Jr., Cyclic projective planes, Duke Math. J. 14 (1947), 1079–1090.DOI
  13. [13]M. Helm, On the distribution of B_3-sequences, J. Number Theory 58 (1996), no. 1, 124–129.
  14. [14]F. Krückeberg, B_2-Folgen und verwandte Zahlenfolgen, J. Reine Angew. Math. 206 (1961), 53–60.
  15. [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. [16]K. O’Bryant, On the Thickness of Infinite Generalized Sidon Sets, I, arXiv:2606.28651v3 (2026).arxiv.org/abs/2606.28651
  17. [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. [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. [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. [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. [21]I. Z. Ruzsa, An infinite Sidon sequence, J. Number Theory 68 (1998), 1–63–71.DOI
  22. [22]I. Z. Ruzsa, Solving a linear equation in a set of integers I, Acta Arith. 65 (1993), 259–282.DOI

Paper details

vlnc:W_5xxftk8k
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 2

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

a large language model

View statement
Looking for related papers…
Contents