B_{h} SEQUENCES

S.W. Graham

Dedicated to Heini Halberstam on the occasion of his retirement

Abstract. Let 𝒜 be a set (finite or infinite) of natural numbers, and let a_{i} denote a generic element of 𝒜. We say that 𝒜 is a B_{h} sequence if the sums of the form a_{1} + … + a_{h} (a_{1} ≤ … ≤ a_{h}) are all distinct. We give an expository account of upper bounds for B_{h} sequences. We also give a new upper bound for B_{3} sequences.

1. Introduction

Let 𝒜 be a set (finite or infinite) of natural numbers, and let a_{i} denote a generic element of 𝒜. We say that 𝒜 is a B_{h} sequence if the sums of the form

a_{1} + … + a_{h}  (a_{1} ≤ … ≤ a_{h})  (1)

are all distinct. S. Sidon [18] was the first to consider B_{2} sequences, and, consequently, B_{2} sequences are sometimes called Sidon sequences. Sidon was motivated by questions on Fourier series. For example, suppose that 𝒜 = {λ_{1}, λ_{2}, … } is an infinite B_{2} sequence and that ∑_{n}(ϵ′_{n}^{2} + ϵ′′_{n}^{2}) < ∞. Sidon proved that there is a continuous function f with Fourier series ∑_{n=1}^{∞}(a_{n} cos(nx) + b_{n} sin(nx)) and a_{λ_{n}} = ϵ′_{n}, b_{λ_{n}} = ϵ′′_{n}.

In 1941, P. Erdős and P. Turán [4] (see also [8], pp. 86–87) gave the first upper bound for finite B_{2} sequences. They showed that if 𝒜 is a B_{2} sequence with 𝒜 ⊆ [1, N], then

|𝒜| ≤ N^{1/2} + O(N^{1/4}).  (2)

Their proof used moving averages and the Cauchy-Schwarz inequality. The same ideas are used in the Weyl-van der Corput Lemma of exponential sum theory, and B. Lindström [16] pointed out that this lemma can be used to shorten the proof of (2). With a little care, one can prove the following more precise result.

Theorem 1. If 𝒜 ⊆ [1, N] is a B_{2} sequence, then

|𝒜| ≤ N^{1/2} + N^{1/4} + 1.

Proof. We first state the Weyl-van der Corput Lemma in the form that we need. This states that if ξ(n) is a real valued function supported on the interval [1, N] and if H is a positive integer, then

|∑_{n} ξ(n)|^{2} ≤ \frac{N + H − 1}{H} ∑_{|h|<H} (1 − \frac{|h|}{H}) ∑_{n} ξ(n)ξ(n + h).  (3)

The author was supported in part by a grant from the National Security Agency.

A proof of this can be found in [7], Lemma 2.5. (Note that in the second and third displayed equations of this proof, one can actually write |I| + H − 1 instead of |I| + H.)

Now we apply Weyl-van der Corput with ξ equal to the characteristic function of 𝒜. Because 𝒜 is B_{2}, the inner sum ∑_{n} ξ(n)ξ(n + h) is |𝒜| if h = 0 and ≤ 1 otherwise. Thus

|𝒜|^{2} ≤ \frac{N + H − 1}{H}(|𝒜| + H − 1).

We take H = [N^{3/4}] + 1, so that H − 1 ≤ N^{3/4} and 1/H < N^{−3/4}. This gives |𝒜|^{2} − (N^{1/4} + 1)|𝒜| ≤ N + N^{3/4}. Using completion of the square and the fact that N ≥ 1, we deduce that

(|𝒜| − \frac{1}{2}(N^{1/4} + 1))^{2} ≤ (N^{1/2} + \frac{1}{2}N^{1/4} + \frac{1}{2})^{2} ,

and the Theorem follows.

The bound of Theorem 1 was first proved by Lindström [15], who used a combinatorial argument.

In 1939, J. Singer [19] showed that if q is a prime and N = q^{2} + q + 1, then there is a set {a_{1}, …, a_{q+1}} such that the differences a_{i} − a_{j}(i ≠ j) form a complete set of non-zero residues (mod N). It is easy to see that this set is also a B_{2} sequence; consequently, there is a B_{2} sequence 𝒜 ⊆ [1, N] with q + 1 > N^{1/2} elements. Therefore, the Erdős-Turán bound (2) is asymptotically best possible. Erdős conjectures that the bound |𝒜| ≤ N^{1/2} + O(1) is true, but this appears to be very difficult.

2. Infinite B_{2} Sequences

Now suppose that 𝒜 is an infinite B_{2} sequence, and let A(n) denote the number of elements a_{i} in 𝒜 with a_{i} ≤ n. What upper bounds can we give for A(n)? Of course, we can consider the finite set 𝒜 ∩ [1, n] and use the Erdős-Turán bound. However, the fact that 𝒜 ∩ [1, n] is embedded in an infinite B_{2} sequence allows us to say more. The following result is due to Erdős; he communicated it to Stöhr for inclusion in his 1955 survey [2]. An account also appears in the book of Halberstam and Roth [8, pages 89–90].

Theorem 2. If 𝒜 is an infinite B_{2} sequence, then

lim inf_{n→∞} \frac{A(n)}{n^{1/2}(log n)^{−1/2}} < ∞.

Proof. For l = 1, …, N, let ℐ_{l} = ((l − 1)N, N] and 𝒜_{l} = 𝒜 ∩ ℐ_{l}. Let A_{l} = |𝒜_{l}|, and let ξ_{l} be the characteristic function of 𝒜_{l}. By inequality (3) with H = N,

A_{l}^{2} ≤ 2 ∑_{|h|<N} (1 − \frac{|h|}{N}) ∑_{n} ξ_{l}(n)ξ(n + h).

Summing over l, we get

∑_{l} A_{l}^{2} ≤ 2 ∑_{|h|<N} (1 − \frac{|h|}{N}) ∑_{n} ξ(n)ξ(n + h)

The inner sum is at most A(N^{2}) ≪ N when h = 0 and at most 1 for other values of h; therefore

∑_{l} A_{l}^{2} ≪ N.  (4)

By Cauchy’s inequality,

∑_{l} A_{l}^{2} ≥ (∑_{l} \frac{A_{l}}{l^{1/2}} )^{2} (∑_{l} \frac{1}{l})^{−1} .  (5)

Now

∑_{l} \frac{A_{l}}{l^{1/2}} = ∑_{l} \frac{A(lN) − A((l − 1)N)}{l^{1/2}} ≥ ∑_{l} A(lN) (\frac{1}{l^{1/2}} − \frac{1}{(l + 1)^{1/2}} ) .

Now let

τ = min_{1≤l≤N} \frac{A(lN)}{(lN)^{1/2}} .

Then

∑_{l} \frac{A_{l}}{l^{1/2}} ≥τN^{1/2} ∑_{l=1}^{N} l^{1/2} (\frac{1}{l^{1/2}} − \frac{1}{(l + 1)^{1/2}} )

≥τN^{1/2} ∑_{l=1}^{N} l^{1/2} ∫_{l}^{l+1} \frac{1}{2}u^{−3/2} du

≥\frac{1}{2}τN^{1/2} ∑_{l=1}^{N} l^{−1}

≥\frac{1}{2}τN^{1/2} log N.

We combine this with (4) and (5) to get

N ≫ ∑_{l} A_{l}^{2} ≫ τ^{2}N log N.

We therefore conclude that

τ ≪ (log N)^{−1/2},

and this is equivalent to the desired result.

3. Uniform Distribution

The theorem in the previous section depends on a simple yet very useful observation. This observation is the fact that

∑_{l} ξ_{l}(n) ≤ ξ(n),

where ξ is the characteristic function of 𝒜 and ξ_{l} is the characteristic function of 𝒜 ∩ ((l − 1)N, lN]. Erdős and R. Freud [5] also applied this fact in the context of finite B_{2} sequences. More specifically, they used it to prove that a maximal B_{2} sequence is uniformly distributed.

Theorem 3. (Erdős-Freud) Suppose 𝒜 is a B_{2} sequence with 𝒜 ⊆ [1, N], and let A denote the number of elements in 𝒜. Suppose also that A = N^{1/2} + O(N^{1/4}). Let

0 = N_{0} < N_{1} < … < N_{r} = N

be a partition of the interval [0, N], and let ℐ_{j} = (N_{j−1}, N_{j}]. Let α_{j} and β_{j} be defined by the relations

|ℐ_{j}| = α_{j}N and |𝒜 ∩ ℐ_{j}| = β_{j}A.

Then

β_{j} = α_{j} + O (N^{−1/8}α_{j}^{1/2}(∑_{i} α_{i}^{−1})^{1/2}) .

Proof. Let ξ be the characteristic function of 𝒜, and let ξ_{i} be the characteristic function of 𝒜 ∩ ℐ_{i}. By inequality (3),

\frac{(β_{i}A)^{2}}{α_{i}N + H} ≤\frac{1}{H} ∑_{|h|<H} (1 − \frac{|h|}{H}) ∑_{n} ξ_{i}(n)ξ_{i}(n + h)

≤\frac{1}{H} ∑_{|h|<H} (1 − \frac{|h|}{H}) ∑_{n} ξ_{i}(n)ξ(n + h).

Summing this last inequality over i, we get

∑_{i} \frac{(β_{i}A)^{2}}{α_{i}N + H} ≤ \frac{1}{H} ∑_{|h|<H} (1 − \frac{|h|}{H}) ∑_{n} ξ(n)ξ(n + h).  (6)

On the right–hand side of (6), the term with h = 0 contributes A ≪ N^{1/2}. The other terms contribute at most 1. Take H = [N^{3/4}]; then

α_{i}N + H = α_{i}N · {1 + O(α_{i}^{−1}N^{−1/4})}.

Combining these observations with (6), we see that

∑_{i} \frac{β_{j}^{2}}{α_{i}} ≤ 1 + O(N^{−1/4} ∑_{i} α_{i}^{−1}).  (7)

Now we write β_{i} = α_{i} + ϵ_{i}, so that

β_{i}^{2}α_{i}^{−1} = α_{i} + 2ϵ_{i} + ϵ_{i}^{2}α_{i}^{−1}.

Since ∑ α_{i} = ∑ β_{i} = 1, we see that ∑ ϵ_{i} = 0 and

∑_{i} ϵ_{i}^{2}α_{i}^{−1} ≪ N^{−1/4} ∑_{i} α_{i}^{−1}.

If we ignore all the terms on the left except i = j, we see that

ϵ_{j}^{2} ≪ N^{−1/4}α_{j} ∑_{i} α_{i}^{−1}.

The theorem now follows.

4. B_{h} sequences for h > 2: Bounds for Even h

Now suppose that 𝒜 ⊆ [1, N] is a B_{h} sequence for some h > 2. For comparison purposes, it is convenient to note the following simple upper bound for |𝒜|. Consider the set of sums

h𝒜 = {a_{1} + a_{2} + … + a_{h} : a_{i} ∈ 𝒜, a_{1} ≤ a_{2} ≤ … a_{h}}.

By definition, the sums in h𝒜 are all distinct. On the other hand, these sums are all contained in the interval [1, hN]. Therefore

\frac{|𝒜|^{h}}{h!} ≤ \binom{|𝒜| + h − 1}{h} ≤ hN,

so

|𝒜| ≤ (h · h!)^{1/h}N^{1/h}.  (8)

In the case h = 4, Lindström [16] proved the stronger bound |𝒜| ≤ (8N)^{1/4} + O(N^{1/8}). The crucial idea in his proof is that if 𝒜 is a B_{4} sequence, then 2𝒜 is nearly a B_{2} sequence. Xing–De Jia [12] generalized this to the following theorem.

Theorem 4. (Jia) Suppose 𝒜 is a B_{2r} sequence and 𝒜 ⊆ [1, N]. Then

|𝒜| ≤ r^{1/2r}(r!)^{1/r}N^{1/2r} + O_{r}(N^{1/4r}).  (9)

Proof. As before, let A denote the number of elements in 𝒜. Let

ℬ = r𝒜 = {a_{1} + a_{2} + … + a_{r} : a_{i} ∈ 𝒜, a_{1} ≤ a_{2} ≤ … a_{r}},

and set B = |ℬ|. Since a B_{2r} sequence is a priori a B_{r} sequence, we see that

B = \binom{A + r − 1}{r} ≥ \frac{A^{r}}{r!} ,  (10)

and we can derive an upper bound for A from an upper bound for B.

Apply the Weyl-van der Corput inequality (3) with N replaced by rN and ξ the characteristic function of ℬ. Then

B^{2} ≤ \frac{rN + H}{H} ∑_{|h|<H} (1 − \frac{|h|}{H}) S_{h},

where H is an integer to be chosen later, and

S_{h} = ∑_{n} ξ(n)ξ(n − h).

Clearly S_{0} = B. Assume that h ≠ 0. Then S_{h} counts the number of pairs b, b′ ∈ ℬ with b − b′ = h. Let

b =a_{1} + … + a_{r}  (13)
b′ =a′_{1} + … + a′_{r}  (14)

be representations of b, b′ as sums of r elements of 𝒜. (These representations are unique up to order.) We now write

S_{h} = S′_{h} + S′′_{h},

where S′_{h} counts the pairs b, b′ in which the representations in (13) and (14) have a common summand, and S′′_{h} counts the remaining pairs. Clearly

∑_{h≠0} S′_{h} ≪_{r} A^{2r−1} ≪_{r} N^{(2r−1)/2r}

by (8). Now consider S′′_{h}. If b − b′ = b′′ − b′′′ = h, then b + b′′′ = b′ + b′′; i.e.,

a_{1} + … + a_{r} + a′′′_{1} + … + a′′′_{r} = a′_{1} + … + a′_{r} + a′′_{1} + … + a′′_{r}.

Since 𝒜 is a B_{2r} sequence, this can happen only if

{a_{1}, …, a_{r}} = {a′′_{1}, …, a′′_{r}} and {a′_{1}, …, a′_{r}} = {a′′′_{1}, …, a′′′_{r}}.

The ordering conditions force us to have a_{1} = a′_{1}, a_{2} = a′_{2}, et cetera. Thus S′′_{h} ≤ 1, and so

B^{2} ≤ (\frac{rN + H}{H} ) (B + H + O_{r}(N^{1−1/2r})).  (15)

Now we first get a crude upper bound for B. Since ℬ ⊆ [1, rN], we have B ≤ rN. Using this on the right-hand side of (15) and taking H = N gives B ≪_{r} N^{1/2} ≪_{r} N^{1−1/2r}. Putting this crude bound back into (15) gives

B^{2} ≤ rN + O_{r}(H + N^{2−1/2r}H^{−1} + N^{1−1/2r}).

We take H = [N^{1−1/4r}] to get

B^{2} ≤ rN + O_{r}(N^{1−1/4r}).

We then combine this with (10) and obtain

A^{2r} ≤ (r!)^{2}rN · {1 + O_{r}(N^{−1/4r})}.

Taking 2r-th roots gives the result.

5. B_{h} sequences for h > 2: Bounds for Odd h

The key idea in Jia’s proof is to consider r𝒜, where r is half of h. But what if h is odd? For example, what is “half” of 3? In this context, it turns out that “half” of 3 is 2; more generally, “half” of 2k − 1 is k.

The following result was discovered independently by S. Chen [2] and S. W. Graham (unpublished).

Theorem 5. If 𝒜 is a B_{2k−1} sequence and 𝒜 ⊆ [1, N], then

|𝒜| ≤ (k!)^{2/(2k−1)}N^{1/(2k−1)} · {1 + O(N^{−1/(4k−2)})}.

We have not attempted to make the estimate uniform in k. If it were desired, however, one could easily obtain such uniformity.

For the proof, we suppose that 𝒜 is a B_{2k−1} sequence with 𝒜 ⊆ [1, N]. We use the symbol [𝒜]^{k} to denote the set of unordered k-tuples of 𝒜; i.e.,

[𝒜]^{k} = {(a_{1}, a_{2}, …, a_{k}) : a_{1} < a_{2} < … < a_{k}, a_{1}, a_{2}, …, a_{k} ∈ 𝒜}.

This notation is commonly used in Ramsey Theory (cf. [6], p. xi). For a = (a_{1}, …, a_{k}) ∈ [𝒜]^{k}, we define σ(a) = a_{1} + … + a_{k}.

We now set

ℬ = {σ(a) : a ∈ [𝒜]^{k}} = {a_{1} + a_{2} + … + a_{k} : a_{1} < a_{2} < … < a_{k}, a_{i} ∈ 𝒜},

and B = |ℬ|. Then ℬ ⊆ [1, kN] and

B = \binom{A}{k} = \frac{1}{k!}A^{k} + O(A^{k−1}).  (16)

Now let ξ be the characteristic function of ℬ; i.e., ξ(n) = 1 if n ∈ ℬ and ξ(n) = 0 otherwise. Let H be a positive integer to be chosen later. By the Weyl-van der Corput inequality (3), we get

B^{2} ≤ \frac{kN + H}{H} ∑_{|h|<H} (1 − \frac{|h|}{H}) ∑_{n} ξ(n)\overline{ξ(n − h)} ≤ \frac{kN + H}{H} ∑_{|h|<H} (1 − \frac{|h|}{H}) E(h),

(17)

where E(h) = |ℰ(h)| and ℰ(h) = {n : n ∈ ℬ and n + h ∈ ℬ}. The set ℰ(h) may also be written as

ℰ(h) = {(a_{1}, …, a_{2k}) : (a_{1}, …, a_{k}) ∈ [𝒜]^{k},(a_{k+1}, …, a_{2k}) ∈ [𝒜]^{k},
a_{1} + … + a_{k} − a_{k+1} − … − a_{2k} = h}.

Note that E(0) = B. For h ≠ 0, we write ℰ(h) = ℰ′(h)∪ℰ′′(h), where ℰ′(h) consists of those 2k-tuples in ℰ(h) with all of a_{1}, …, a_{2k} distinct, and ℰ′′(h) consists of the remaining 2k-tuples. In accordance with our notational conventions, we use E′(h) and E′′(h) to denote the cardinalities of ℰ′(h) and ℰ′′(h) respectively.

The contribution of E′′ can be estimated immediately, for ∑_{|h|<H} E′′(h) is bounded by the number of 2k-tuples (a_{1}, …, a_{2k}) with at least two of the a_{i}’s equal. The latter is clearly ≪ A^{2k−1}, so

∑_{1≤|h|≤H} (1 − \frac{|h|}{H}) E′′(h) ≪ A^{2k−1}.  (18)

Now we consider the contribution of the E′ terms. Let a be a fixed element of 𝒜, and let E′(h, a) be the number of 2k-tuples (a_{1}, …, a_{2k}) in ℰ′(h) with a occurring in one of the first k coordinates. Observe that

∑_{a∈𝒜} E′(h, a) = kE′(h).  (19)

We claim that for every h ≠ 0 and every a ∈ 𝒜, E′(h, a) ≤ 1. Suppose that a = (a_{1}, …, a_{2k}) and b = (b_{1}, …, b_{2k}) are 2k-tuples counted in E′(h, a); then there exist i, j with 1 ≤ i, j ≤ k and a = a_{i} = b_{j}. Thus

∑_{\begin{matrix}ν=1 \\ ν≠i \end{matrix}}^{k} a_{ν} − ∑_{ν=k+1}^{2k} a_{ν} = ∑_{\begin{matrix}μ=1 \\ μ≠j \end{matrix}}^{k} b_{μ} − ∑_{μ=k+1}^{2k} b_{μ} = h,

so

∑_{\begin{matrix}ν=1 \\ ν≠i \end{matrix}}^{k} a_{ν} + ∑_{μ=k+1}^{2k} b_{μ} = ∑_{\begin{matrix}μ=1 \\ μ≠j \end{matrix}}^{k} b_{μ} + ∑_{ν=k+1}^{2k} a_{ν}.

Now 𝒜 is a B_{2k−1} sequence, so we conclude that

{a_{1}, …, a_{i−1}, a_{i+1}, …, a_{k}, b_{k+1}, …, b_{2k}} =
{b_{1}, …, b_{j−1}, b_{j+1}, …, b_{k}, a_{k+1}, …, a_{2k}}.

From our hypotheses, we know that all the a_{ν}’s are distinct, as are all the b_{μ}’s. Therefore, we must have

{a_{1}, …, a_{i−1}, a_{i+1}, …, a_{k}} = {b_{1}, …, b_{j−1}, b_{j+1}, …, b_{k}}

and

{a_{k+1}, …, a_{2k}} = {b_{k+1}, …, b_{2k}}.

From the definition of ℬ, we also have the ordering conditions a_{1} < … < a_{k}, etc. From these conditions, we conclude that a_{ν} = b_{ν} for 1 ≤ ν ≤ 2k and that i = j. This completes the proof of our claim.

The above together with (19) yields

E′(h) ≤ \frac{1}{k} A.  (20)

Combining (17), (18), and (20), we find that

B^{2} ≤ \frac{kN + H}{H} (B + \frac{H}{k} A + O(A^{2k−1})) .  (21)

Now we combine (16) and (21) and obtain

A^{2k} ≤ (k!)^{2}NA + O(HA + NH^{−1}A^{2k−1} + A^{2k−1}).

Setting H = [N^{1/2}A^{k−1}] and using the trivial bound A ≪ N^{1/(2k−1)} gives

A^{2k−1} ≤ (k!)^{2}N · {1 + O(N^{−1/(4k−2)})}.

The proof is completed by taking (2k − 1)st roots.

6. Upper Bounds for B_{3} sequences

When 𝒜 is a B_{3} sequence, Theorem 5 gives |𝒜| ≤ 4^{1/3}N^{1/3} + O(N^{1/6}), but this is weaker than a result of An Ping Li [14], who proved that

|𝒜| ≤ (4 − \frac{2 log^{2} 2}{3 log^{2} N} )^{1/3} N^{1/3} + O(1).

In this paper, we establish the following sharper result.

Theorem 6. Let c = 3.99561029143. If 𝒜 is a B_{3} sequence and 𝒜 ⊆ [1, N], then

|𝒜| ≤ c^{1/3}N^{1/3} + O(1).

As we shall see in the proof, c may in fact be replaced by an algebraic number c_{0} with c − 10^{−11} < c_{0} < c. In terms of rational approximations, note that

4 − \frac{1}{227} < c < 4 − \frac{1}{228}.

The improvement in the constant is small, but the point of the theorem is that 4 is not the limit of Li’s method.

To get some insight into Li’s proof, consider the following variation of the trivial bound (8). Assume that 𝒜 is a B_{3} sequence, and let

ℬ = {x_{1} + x_{2} − x_{3} : x_{i} ∈ 𝒜, x_{1} < x_{2}, x_{1} ≠ x_{3}, x_{2} ≠ x_{3}}.

We claim that there is no duplication among the elements of ℬ. For suppose that

x_{1} + x_{2} − x_{3} = x′_{1} + x′_{2} − x′_{3}.

Then x_{1} + x_{2} + x′_{3} = x′_{1} + x′_{2} + x_{3}. By the B_{3} condition, {x_{1}, x_{2}, x′_{3}} = {x′_{1}, x′_{2}, x_{3}}. Since x_{3} is not equal to either x_{1} or x_{2}, we must have x_{3} = x′_{3}. Moreover, the ordering conditions x_{1} < x_{2} and x′_{1} < x′_{2} force us to have x_{1} = x′_{1} and x_{2} = x′_{2}.

This lack of duplication means that ℬ has A(A − 1)(A − 2)/2 elements. Since ℬ ⊆ (−N, 2N), we conclude that A(A − 1)(A − 2)/2 < 3N; i.e.,

|𝒜| ≤ (6N)^{1/3} + O(1).  (22)

By comparison, (8) gives the upper bound (18N)^{1/3}.

In his proof, Li considers the set 𝒫 = ℬ ∩ (0, N), and he shows that the set 𝒫 has more than A^{3}/4 elements. In other words, he shows that the middle third of the interval (−N, 2N) contains more than half of the elements of ℬ.

Now we begin the proof. We may assume that N/2 ∉ 𝒜; for, in the contrary case, we may delete N/2 from 𝒜 and absorb it into the “O”–term. For x = (x_{1}, x_{2}, x_{3}) ∈ [𝒜]^{3}, we define

f_{1}(x) = −x_{1} + x_{2} + x_{3}, f_{2}(x) = x_{1} − x_{2} + x_{3}, and f_{3}(x) = x_{1} + x_{2} − x_{3}.

For i = 1, 2, or 3, we define

𝒫_{i} = {f_{i}(x) : x ∈ [𝒜]^{3} and 0 < f_{i}(x) < N} .

Then the set 𝒫 defined above may be written as 𝒫 = 𝒫_{1} ∪ 𝒫_{2} ∪ 𝒫_{3}. The argument in the paragraph before (22) shows that 𝒫_{1}, 𝒫_{2}, and 𝒫_{3} are mutually disjoint. All of these sets lie in (0, N), so

|𝒫_{1}| + |𝒫_{2}| + |𝒫_{3}| < N.  (23)

Now let ℬ_{i} = {x ∈ [𝒜]^{3} : f_{i}(x) ∈ 𝒫_{i}} for i = 1, 2, 3. Note that |ℬ_{i}| = |𝒫_{i}|, but ℬ_{1}, ℬ_{2}, ℬ_{3} are not necessarily disjoint. If x ∈ [𝒜]^{3}, then

0 < f_{2}(x) = x_{1} − x_{2} + x_{3} < N

by virtue of the inequalities 0 < x_{1} < x_{2} < x_{3} ≤ N. Therefore,

|ℬ_{2}| = |[𝒜]^{3}| = \frac{1}{6}A^{3} + O(A^{2}).  (24)

Similarly, f_{1}(x) > 0 and f_{3}(x) < N. Therefore,

ℬ_{1} = {x ∈ [𝒜]^{3} : f_{1}(x) < N} and ℬ_{3} = {x ∈ [𝒜]^{3} : f_{3}(x) > 0} .

From (23) and (24), we see that

|ℬ_{1}| + |ℬ_{3}| + \frac{1}{6}A^{3} + O(A^{2}) < N.

For our purposes, it is convenient to rewrite this as

|ℬ_{1} ∪ ℬ_{3}| + |ℬ_{1} ∩ ℬ_{3}| + \frac{1}{6}A^{3} + O(A^{2}) < N.  (25)

We can now obtain upper bounds for A by giving lower bounds for |ℬ_{1} ∪ ℬ_{3}| and |ℬ_{1} ∩ ℬ_{3}|. Note that the trivial lower bounds of 0 give A ≤ (6N)^{1/3} + O(1), which is the same as (8).

7. Bound for h = 3: Lower Bound for |ℬ_{1} ∪ ℬ_{3}|

Let ξ be the characteristic function of 𝒜. We observe that

∑_{a<N/2}(ξ(a) + ξ(N − a))(∑_{b<a}(ξ(b) − ξ(N − b)))^{2} ≥ 0.

After expanding this sum, we deduce that

S ≥ T,  (26)

where

S = ∑_{\begin{matrix}a<N/2 \\ b,c<a \end{matrix}}\{ξ(a)ξ(b)ξ(c) + ξ(a)ξ(N − b)ξ(N − c)+

ξ(N − a)ξ(b)ξ(c) + ξ(N − a)ξ(N − b)ξ(N − c)},

and

T = 2 ∑_{\begin{matrix}a<N/2 \\ b,c<a \end{matrix}}\{ξ(a)ξ(b)ξ(N − c) + ξ(N − a)ξ(b)ξ(N − c)\}.

By using the symmetry in the variables b and c, we find that

S = 2 ∑_{c<b<a<N/2}{ξ(a)ξ(b)ξ(c) + ξ(a)ξ(N − b)ξ(N − c)+

ξ(N − a)ξ(b)ξ(c) + ξ(N − a)ξ(N − b)ξ(N − c)}

+ ∑_{b<a<N/2}{ξ(a)ξ(b) + ξ(a)ξ(N − b) + ξ(N − a)ξ(b) + ξ(N − a)ξ(N − b)}

= 2(|𝒞_{1}| + |𝒞_{2}| + |𝒞_{3}| + |𝒞_{4}|) + |ℰ|,

say, where

𝒞_{1} = {x ∈ [𝒜]^{3} : x_{1} < x_{2} < x_{3} < N/2} ,
𝒞_{2} = {x ∈ [𝒜]^{3} : x_{1} < N/2 < x_{2} < x_{3}, x_{1} + x_{2} > N} ,
𝒞_{3} = {x ∈ [𝒜]^{3} : x_{1} < x_{2} < N/2 < x_{3}, x_{2} + x_{3} < N} ,
𝒞_{4} = {x ∈ [𝒜]^{3} : N/2 < x_{1} < x_{2} < x_{3}} , and
ℰ = {(x_{1}, x_{2}) : x_{1} ∈ 𝒜, x_{2} ∈ 𝒜, x_{1} < x_{2}, x_{1} + x_{2} ≠ N}.

If x ∈ 𝒞_{1} ∪ 𝒞_{3}, then −x_{1} + x_{2} + x_{3} < N, so x ∈ ℬ_{1}. We infer that 𝒞_{1} ∪ 𝒞_{3} ⊆ ℬ_{1}. A similar argument gives 𝒞_{2} ∪ 𝒞_{4} ⊆ ℬ_{3}. After noting that |ℰ| ≪ A^{2}, we get

S = 2 ∑_{i=1}^{4} |𝒞_{i}| + O(A^{2}) ≤ 2|ℬ_{1} ∪ ℬ_{3}| + O(A^{2}).  (27)

A similar analysis of T shows that

T = 2(|𝒞_{5}| + |𝒞_{6}|),  (28)

where

𝒞_{5} = {x ∈ [𝒜]^{3} : x_{1} < x_{2} < N/2 < x_{3}, x_{2} + x_{3} > N} , and
𝒞_{6} = {x ∈ [𝒜]^{3} : x_{1} < N/2 < x_{2} < x_{3}, x_{2} + x_{3} < N} .

Recall that N/2 ∉ 𝒜, so

[𝒜]^{3} = ⋃_{i=1}^{7} 𝒞_{i},  (29)

where

𝒞_{7} = {x ∈ [𝒜]^{3} : x_{1} + x_{2} = N or x_{2} + x_{3} = N}.

Now a B_{3} sequence is a priori a B_{2} sequence, so x_{1} + x_{2} = N has at most one solution with x_{1} < x_{2}. We deduce that |𝒞_{7}| ≪ A. Using this with (27), (28), and (29), we obtain

\frac{1}{3}A^{3} + O(A^{2}) = 2|[𝒜]^{3}| = 2 ∑_{i=1}^{7} |𝒞_{i}| = S + T + O(A^{2}).

From (26) and (27), we infer that

S + T ≤ 2S ≤ 4|ℬ_{1} ∪ ℬ_{3}| + O(A^{2}).

Combining the last two statements gives the bound

|ℬ_{1} ∪ ℬ_{3}| ≥ \frac{1}{12}A^{3} + O(A^{2}).  (30)

If we use the trivial lower bound |ℬ_{1} ∩ ℬ_{3}| ≥ 0 together with (25) and (30), we get

A ≤ (4N)^{1/3} + O(1).  (31)

We shall use this estimate in the next section. Note that apart from the smaller error term, (31) is the same as Theorem 5.

8. Bound for h = 3: Conclusion

To get a lower bound for |ℬ_{1} ∩ ℬ_{3}|, we first need the following lemma.

Lemma 1. Suppose that X is a positive real number with X ≤ N/2, and suppose that ℐ is a subinterval of [1, N] with either (i) ℐ = (X/2, X] or (ii) ℐ = (N −X, N − X/2]. Then [𝒜 ∩ ℐ]^{3} ⊆ ℬ_{1} ∩ ℬ_{3}.

Proof. Suppose that (i) is true, and let (x_{1}, x_{2}, x_{3}) ∈ [𝒜 ∩ ℐ]^{3}. Then X/2 < x_{1} < x_{2} < x_{3} ≤ X, so x_{1} + x_{2} − x_{3} > 2(X/2) − X > 0 and −x_{1} + x_{2} + x_{3} < 2X ≤ N. The proof for case (ii) is similar. □

Now let k be a positive integer to be chosen later, and define

𝒢_{1} = (0, 2^{−k−1}N], 𝒢_{2} = (2^{−k−1}N, (1 − 2^{−k−1})N], 𝒢_{3} = ((1 − 2^{−k−1})N, N].

Write 𝒜 = ℱ_{1} ∪ ℱ_{2} ∪ ℱ_{3}, where ℱ_{i} = 𝒜 ∩ 𝒢_{i}. Now each ℱ_{i} is a B_{3}–set in a smaller interval. We use (31) to bound ℱ_{1} and ℱ_{3}, and we thereby obtain

|ℱ_{1} ∪ ℱ_{3}| ≤ 2 (4 · 2^{−k−1}N)^{\frac{1}{3}} + O(1) = 4^{\frac{1}{3}} 2^{\frac{2−k}{3}} N^{\frac{1}{3}} + O(1).  (32)

Now assume that b is a real number such that

A ≥ b^{1/3}N^{1/3}.  (33)

Then

|ℱ_{2}| ≥ (b^{\frac{1}{3}} − 4^{\frac{1}{3}} 2^{\frac{2−k}{3}} ) N^{1/3} + O(1);

this is non–trivial as long as b ≥ 2^{4−k}. Split the interval (2^{−k−1}N, (1 − 2^{−k−1})N] into subintervals defined by the relations

ℐ_{j} = (2^{−j−1}N, 2^{−j}N] and ℐ_{k+j} = ((1 − 2^{−j})N, (1 − 2^{−j−1})N]

for j = 1, …, k, and define 𝒜_{j} = 𝒜 ∩ ℐ_{j}. By Hölder’s inequality,

|ℱ_{2}|^{3} = {∑_{j=1}^{2k} |𝒜_{j}|}^{3} ≤ (∑_{j=1}^{2k} 1)^{2} ∑_{j=1}^{2k} |𝒜_{j}|^{3}.

Observe that |𝒜_{j}|^{3} = 6|[𝒜_{j}]^{3}| + O(|[𝒜_{j}]^{2}|). Using this and Lemma 1, we conclude that

(b^{\frac{1}{3}} − 4^{\frac{1}{3}} 2^{\frac{2−k}{3}} )^{3} N ≤ 6(2k)^{2}|ℬ_{1} ∩ ℬ_{3}| + O(N^{2/3}).

Combining this with (25) and (30), we deduce that

N ≥ \frac{1}{4}A^{3} + \frac{1}{24k^{2}} (b^{\frac{1}{3}} − 4^{\frac{1}{3}} 2^{\frac{2−k}{3}} )^{3}N + O(N^{2/3}).

We incorporate the assumption (33) to get

1 ≥ \frac{1}{4}b − \frac{1}{24k^{2}} (b^{\frac{1}{3}} − 4^{\frac{1}{3}} 2^{\frac{2−k}{3}} )^{3} + O(N^{−1/3}).

We now conclude that A ≤ b_{1}^{1/3}N^{1/3} + O(1), where b_{1} is the largest real root of the equation

24k^{2} − 6k^{2}b − (b^{\frac{1}{3}} − 4^{\frac{1}{3}} 2^{\frac{2−k}{3}} )^{3} = 0.  (34)

Computations show that the optimal choice for k is k = 8; with this choice,

b_{1} = 3.99561189585308 …

is the largest real root of (34).

Now the preceding calculations may be repeated with 4 replaced by b_{1} in (32). In this way, we get a sequence of inequalities of the form A ≤ b_{j}^{1/3}N^{1/3} + O(1), where b_{0} = 4, b_{j+1} is the largest real root of the equation

24k_{j}^{2} − 6k_{j}^{2}b − (b^{\frac{1}{3}} − (b_{j}2^{2−k_{j}})^{\frac{1}{3}} )^{3} = 0,

and k_{j} is a positive integer to be chosen at each stage. A modest amount of calculation shows that the optimal choices are k_{0} = k_{1} = k_{2} = 8, and these choices yield

b_{1} = 3.99561189585308 …,
b_{2} = 3.99561029201457 …, and
b_{3} = 3.99561029142809 ….

(Further iterations give no improvement in the first 11 decimal places.) Now b_{3} < c, where c was defined in the statement of Theorem 6. This completes the proof.

In conclusion, it is now appropriate to give some details on the relation between our proof and Li’s proof. Except for notation and organizational details, we have followed Li in Sections 6 and 7. The improvement comes from the treatment of ℬ_{1} ∩ ℬ_{3}. Li divides the interval [1, N] into K = 2(log N/ log 2) + O(1) subintervals satisfying the hypotheses of Lemma 1, and he uses Hölder’s inequality to deduce that

A^{3} ≤ 6K^{2}(|ℬ_{1} ∩ ℬ_{3}| + O(A^{2})).

In our argument, we restricted the use of Hölder’s inequality to ℱ_{2}. This is more efficient because only a bounded number of subintervals are required in the application of Lemma 1.

9. Infinite B_{h} Sequences

We close with a brief mention of the known results about infinite B_{h} sequences when h > 2. Nash [17] combined Lindström’s finite B_{4} argument and Erdős’ infinite B_{2} argument to prove that if 𝒜 is an infinite B_{4} sequence, then

lim inf_{n→∞} \frac{A(n)}{n^{1/4}(log n)^{−1/4}} < ∞.

A natural conjecture is that if 𝒜 is an infinite B_{h} sequence, then

lim inf_{n→∞} \frac{A(n)}{n^{1/h}(log n)^{−1/h}} < ∞.  (35)

A straightforward application of the arguments used in proving Theorems 4 and 5 does not work because the bounds for the exceptional cases are insufficiently sharp. However, Chen[3] has proved (35) when h is even. This superseded earlier partial results of Jia [13] and M. Helm [9], who independently proved (35) in the even case with the additional hypotheses that A(n^{2}) ≪ A(n)^{2}. Very little is known about the corresponding problem when h is odd. However, Helm [11] has shown that if A(n) ∼ αn^{1/3} for some α, then 𝒜 is not a B_{3} sequence.

References

1. R.C. Bose and S. Chowla, Theorems in the additive theory of numbers, Comment. math. helvet. 37 (1962-3), 141–147.

2. S. Chen, On the size of finite Sidon sequences, Proc. Amer. Math. Soc. 121 (1994), 353–356.

3. S. Chen, On Sidon sequences of even orders, Acta Arith 64 (1993), 325–330.

4. 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), 212–215; Addendum, (by P. Erdős), ibid. 19 (1944), 208.

5. P. Erdős and R. Freud, On Sums of a Sidon–Sequence, J. Number Theory 38 (1991), 196–205.

6. R.L. Graham, B.L. Rothschild, and J.H. Spencer, Ramsey Theory, 2^{nd} Edition, Wiley, New York, 1990.

7. S.W. Graham and G. Kolesnik, Van der Corput’s method of exponential sums, Lond. Math. Soc. Lecture Note Series 126, Cambridge University Press, Cambridge, 1991.

8. H. Halberstam and K.F. Roth, Sequences, 2^{nd} Edition, Springer-Verlag, New York, 1983.

9. M. Helm, On B_{2k} sequences, J. No. Theory 48 (1994), 183–196.

10. M. Helm, A remark on B_{2k} sequences, Acta Arithmetica 63 (1994), 367–371.

11. M. Helm, On the distribution of B_{3} sequences, J. No. Theory (to appear).

12. Xing-De Jia, On finite Sidon sequences, J. No. Theory 44, 84–92.

13. Xing-De Jia, On B_{2k} sequences, J. No. Theory 48 (1994), 183–196.

14. An Ping Li, On B_{3} sequences, (Chinese), Acta Math. Sinica 34 (1991), 67–71.

15. B. Lindström, An inequality for B_{2} sequences, Jour. Comb. Theory 6 (1969), 211–212.

16. B. Lindström, A remark on B_{4} sequences, Jour. Comb. Theory 7 (1969), 276–277.

17. J.C.M. Nash, On B_{4} sequences, Canad. Math. Bull. 32 (1989), 446–449.

18. S. Sidon, Ein Satz über trigonometrische Polynome und seine Anwendung in der Theorie der Fourier–Reihen, Math. Ann. 106 (1932), 536–539.

19. J. Singer, A theorem in finite projective geometry and some applications to number theory, Trans. Am. Math. Soc. 43 (1938), 377–385.

20. A. Stöhr, Gelöste und ungelöste Fragen über Basen der natürlichen Zahlenreihe, II, J. Reine Angew. Math. 194 (1955), 111–140.

Michigan Technological University, Houghton, MI 49931 USA Current address: National Science Foundation, Arlington, VA 22230, USA E-mail address: swgraham@nsf.gov or swgraham@mtu.edu