Random Sidon Sequences

Anant P. Godbole Department of Mathematical Sciences, Michigan Technological University, Houghton, MI 49931, U.S.A. E-mail: anant@mtu.edu

Svante Janson Department of Mathematics, Uppsala University, PO Box 480, S-751 06 Uppsala, Sweden.

E-mail: svante.janson@math.uu.se

Nicholas W. Locantore, Jr. Department of Statistics, University of North Carolina, Chapel Hill, NC 27599, U.S.A.

E-mail: locantor@stat.unc.edu

Rebecca Rapoport Department of Mathematics, Harvard University, Cambridge, MA 02138, U.S.A. E-mail:

rapoport@fas.harvard.edu

Running Head: Random Sidon Sequences Proofs: Should be sent to Anant Godbole, Department of Mathematical Sciences, Michigan Technological University, 1400 Townsend Drive, Houghton, MI 49931-1295, U.S.A.

Abstract

A subset A of the set [n] = {1, 2, …, n}, |A| = k, is said to form a Sidon (or B_{h}) sequence, h ≥ 2, if each of the sums a_{1} + a_{2} + … + a_{h}, a_{1} ≤ a_{2} ≤ … ≤ a_{h}; a_{i} ∈ A, are distinct. We investigate threshold phenomena for the Sidon property, showing that if A_{n} is a random subset of [n], then the probability that A_{n} is a B_{h} sequence tends to unity as n → ∞ if k_{n} = |A_{n}| ≪ n^{1/2h}, and that P(A_{n} is Sidon) → 0 provided that k_{n} ≫ n^{1/2h}. The main tool employed is the Janson exponential inequality. The validity of the Sidon property at the threshold is studied as well; we prove, using the Stein– Chen method of Poisson approximation, that P(A_{n} is Sidon) → exp{−λ} (n → ∞) if k_{n} ∼ Λ · n^{1/2h} (Λ ∈ R^{+}), where λ is a constant that depends in a well-specified way on Λ. Multivariate generalizations are presented.

1. Introduction

A subset A of [n] = {1, 2, …, n}, |A| = k, is said to form a Sidon (or B_{h}) sequence, h ≥ 2, if each of the \binom{k+h−1}{h} sums a_{1} + a_{2} + … + a_{h}, a_{1} ≤ a_{2} ≤ … ≤ a_{h}, a_{i} ∈ A (i = 1, 2, …, h) are distinct. For example, any two element set {a, b} is B_{2}, since the three sums a+b, 2a, 2b are necessarily distinct, whilst a three element set {a, b, c} is B_{2} iff a, b, c are not in arithmetic progression. An extensive survey of the properties of Sidon sequences may be found in Halberstam and Roth [5], where it is shown, for example, that B_{h} sequences are of size at most O(n^{1/h}) [for any h ≥ 2] , and, moreover, that there do exist B_{h} sequences of order n^{1/h}. In particular, Lindström [6] showed that |A| ≤ n^{1/2} + n^{1/4} + 1 for any B_{2} sequence A. Recent papers on finite and infinite Sidon sequences include the ones by Graham [4] and Spencer and Tetali [8].

We consider a set A_{n} obtained by selecting, without replacement, a random sample of size k_{n} from the first n integers, and investigate threshold phenomena for the Sidon property, showing, in Theorem 1, that the probability that A_{n} is B_{h} tends to unity as n → ∞ if k_{n} ≪ n^{1/2h}, and that P(A_{n} is Sidon) → 0 provided that k_{n} ≫ n^{1/2h}, where we write φ(n) ≫ ς(n) (resp. φ(n) ≪ ς(n)) if φ(n)/ς(n) → ∞ (resp. 0) as n → ∞. (The first part has also been shown by Nathanson, see [7], page 37, Exercise 14.) The main tool employed is the Janson exponential inequality (see, e.g., Alon and Spencer [1]). Theorem 1 shows that the Sidon property becomes rare at a level far below that indicated by the above-mentioned extremal results in Halberstam and Roth [5]; it is conceivable, however, that a carefully selected non-uniform measure on the k_{n}-subsets of [n] will yield a threshold closer to n^{1/h}: for example, one may be able to exploit the fact [3,4] that maximal B_{2} sequences are uniformly distributed. In Section 3, we investigate the behaviour of the Sidon property at the threshold, proving in Theorem 2 that P(A_{n} is B_{h}) → exp{−λ} as n → ∞ if |A_{n}| ∼ Λ · n^{1/2h}, where Λ ∈ R^{+} and λ = κ_{h}Λ^{2h} for a constant depending on h. (κ_{2} = 1/12 and κ_{3} = 11/1440; asymptotically κ_{h} ∼ \sqrt{\frac{3}{4π}} h^{−1/2}h!^{−2} as h → ∞.) The Stein–Chen method of Poisson approximation [2] is the main technique used in the proof of this result. We also provide multivariate Poisson approximations for the joint distribution of the ensemble {I_{a,b} : a_{1} + … + a_{h} = b_{1} + … + b_{h}}, where a = (a_{1}, …, a_{h}), b = (b_{1}, …, b_{h}), and where the zero-one variable I_{a,b} equals one iff {a_{1}, …, a_{h}} ⊆ A_{n}, {b_{1}, …, b_{h}} ⊆ A_{n}; this result (Theorem 3) enables one to understand the structure of the set A_{n} in a global sense, keeping track, as it does, of all the episodes when an integer m is obtained by two h-sums of elements of A_{n}. The Stein–Chen method is used once again as the driving force behind the proof; of special note is the fact that the components of the multivariate Poisson approximant in Theorem 3 are independent, whereas the variables I_{a,b} are clearly not.

We have chosen to employ different methods in Sections 2 and 3, but it should be made clear at the outset that we could have done differently. In fact, Theorem 1 is a simple corollary of Theorem 2, and thus follows by the Stein–Chen method too. (A third possibility is to use Chebyshev’s inequality together with estimates derived below.) Conversely, Theorem 2 may be derived using the Janson inequality.

Similar questions can be asked regarding sum-free subsets of the integers, and will be reported on elsewhere, as will be results on B_{h} sequences where h → ∞ along with n, and on subsets with distinct sums (see [1] for the relevant definitions).

We write u = O(v) or (equivalently) u ⪯ v if u ≤ Av for some constant A that may depend on h but not on n or any other variable.

2. Threshold functions for the Sidon property

The following is the main result of this section: Theorem 1. Consider a subset A_{n} of size k_{n} chosen at random from the \binom{n}{k_{n}} such subsets of [n] = {1, 2, …, n}. Then for any h ≥ 2,

k_{n} = o(n^{1/2h}) ⇒ P(A_{n} is B_{h}) → 1 (n → ∞)

and

n^{1/2h} = o(k_{n}) ⇒ P(A_{n} is B_{h}) → 0 (n → ∞).

Proof. We begin with the easy first half, the proof of which employs nothing more than the Markov inequality. We introduce some notation to be used throughout the paper.

Let A = A_{n,h} be the set of all sequences a = (a_{1}, …, a_{h}) with 1 ≤ a_{1} ≤ a_{2} ≤ … ≤ a_{h} ≤ n, and let

B = B_{n,h} = {(a, b) ∈ A × A : a_{1} + … + a_{h} = b_{1} + … + b_{h} and a < b}

where < denotes the lexicographic order.

An element a of A is thus an (ordered) sequence (a_{1}, …, a_{h}), but we will also, when convenient, use a to denote the corresponding set {a_{1}, …, a_{h}}; for example, |a| denotes the number of elements of this set, i.e., the number of distinct numbers a_{i}.

Using this notation, a set A_{n} ⊂ [n] is Sidon if and only if A_{n} does not contain a ∪ b for any (a, b) ∈ B.

Let, as above, I_{a,b}, (a, b) ∈ B, be the (random) indicator variables defined by I_{a,b} = 1 if a ∪ b ⊆ A_{n} (with I_{a,b} = 0 otherwise), and define

X = ∑_{(a,b)∈B} I_{a,b}.

Thus A_{n} is Sidon if and only if I_{a,b} = 0 for every pair (a, b) ∈ B, i.e., when X = 0.

We define

B(l) = {(a, b) ∈ B : |a ∪ b| = l} , l = 1, …, 2h,

and note that B(2h) is the set of pairs (a, b) with 2h distinct numbers a_{1}, …, b_{h}. Clearly, for any (a, b) ∈ B(l),

P(I_{a,b} = 1) = \binom{n − l}{k − l} / \binom{n}{k} ≤ (\frac{k}{n})^{l},

and thus, by Markov’s inequality,

P(A_{n} is not B_{h}) = P(X ≥ 1)
≤ E(X) = ∑_{l=1}^{2h} |B(l)|\binom{n − l}{k − l} / \binom{n}{k} ≤ ∑_{l=1}^{2h} |B(l)|(\frac{k}{n})^{l}.  (1)

We estimate |B(l)| as a lemma. Lemma 1. |B(l)|, the number of pairs (a, b) ∈ B containing exactly l different numbers, is O(n^{l−1}) for every l ≤ 2h. Proof. A pair (a, b) ∈ B(l) satisfies a pattern of 2h − l (non-redundant) coincidences among {a_{1}, …, b_{h}}, for example a_{1} = a_{2} = b_{1}, a_{5} = b_{3}, . . .. Fix one such pattern. This pattern defines 2h − l of the variables a_{1}, …, b_{h} in terms of the remaining l ‘free’ ones. Moreover, the relation a_{1} + … + a_{h} = b_{1} + … + b_{h} yields a linear relation between the free variables, and this relation degenerates only when each free variable occurs equally many times in a and in b, which means that the pattern implies a = b and hence (a, b) ∉ B. For all other patterns, the pair (a, b) ∈ B is thus specified by l − 1 variables ∈ [n], and the number of pairs (a, b) ∈ B with a given pattern is thus ≤ n^{l−1}. This completes the proof, since the number of possible patterns is finite (and bounded independently of n).

Consequently, if k = o(n^{1/2h}), then

P(A_{n} is not B_{h}) ⪯ ∑_{l=1}^{2h} n^{l−1}k^{l}n^{−l} ⪯ k^{2h}n^{−1} → 0,

as n → ∞, which proves the first part of the theorem.

Turning to the second half, we note that the main contribution to E(X) is through h-tuples a and b whose 2h coordinates are all distinct. Thus we define

Y = ∑_{(a,b)∈B(2h)} I_{a,b}

and see that

P(A is B_{h}) = P(X = 0) ≤ P(Y = 0).

We thus focus on computing P(Y = 0), and start by changing the underlying model somewhat; we will revert to the original model later in the proof: Let us choose each element of [n] independently with probability p = k/n. This yields a set whose expected (as opposed to actual) cardinality is k. Such a strategy is necessary due the baseline assumption of independence that is required for the successful application of the Janson inequality, which yields (see e.g. Alon and Spencer [1], Theorem 1.1 in Chapter 8 with ε = 1/2; the version given there has the (not really necessary) assumption P_{u}(I_{a,b} = 1) = p^{2h} ≤ \frac{1}{2} for all (a, b) ∈ B(2h), which we may assume without loss)

P_{u}(Y = 0) ≤ ( ∏_{(a,b)∈B(2h)} P_{u}(I_{a,b} = 0)) exp(Δ),  (2)

where P_{u} is the probability measure corresponding to the modified model described above and Δ is given by

Δ = ∑_{(a,b)∼(c,d)} P_{u}(I_{a,b}I_{c,d} = 1)

with the relation ∼ on B(2h) being defined as follows: We say that (a, b) ∼ (c, d) if (a, b), (c, d) ∈ B(2h), (a, b) ≠ (c, d) and (a ∪ b) ∩ (c ∪ d) ≠ ∅. By (2), our result will follow, under the modified model, if we can show that the right hand side of (2) tends to zero for suitable p. Let, for 2h ≤ l ≤ 4h,

D(l) = {((a, b), (c, d)) ∈ B(2h) × B(2h) : (a, b) ≠ (c, d) and |a ∪ b ∪ c ∪ d| = l} .

Then D := ⋃_{l=2h}^{4h−1} D(l) is the set of pairs of pairs ((a, b), (c, d)) with (a, b) ∼ (c, d). We have,

Δ = ∑_{(a,b)∼(c,d)} P_{u}(I_{a,b}I_{c,d} = 1) = ∑_{l=2h}^{4h−1} ∑_{((a,b),(c,d))∈D(l)} P_{u}(I_{a,b}I_{c,d} = 1)
= ∑_{l=2h}^{4h−1} |D(l)|p^{l}.  (3)

Lemma 2. For each l ≥ 2h, |D(l)| ⪯ n^{l−2}. Proof. We argue as in the proof of Lemma 1. This time each ((a, b), (c, d)) ∈ D(l) satisfies a pattern of 4h − l coincidences of the types a_{i} = c_{j}, a_{i} = d_{j}, b_{i} = c_{j} and b_{i} = d_{j}, where no variable occurs more than once. (Recall that by assumption, (a, b) and (c, d) each contain 2h distinct numbers.)

We fix one such pattern. Suppose first that l > 2h. Then there are n^{2h−1} choices of a_{1}, …, b_{h−1}, which together determine b_{h} (possible outside [n] and thus illegal) because a_{1} +…+a_{h} = b_{1} +…+b_{h}. The pattern of coincidences then determine 4h−l of c_{1}, …, d_{h}, and of the remaining 2h − (4h − l) = l − 2h > 0 variables one is determined by the others because of the relation c_{1} + … + c_{h} = d_{1} + … + d_{h}; hence there are ≤ n^{l−2h−1} choices of c_{1}, …, d_{h}. Together this gives ≤ n^{2h−1+l−2h−1} = n^{l−2} choices for each pattern, and the result for the case l > 2h follows.

In the case l = 2h, the pattern determines each c_{j} and d_{j} as one of a_{1}, …, b_{h}. If each c_{j} coincides with an a_{i}, then necessarily c = a (recall that the sequences are ordered) and d = b, which violates (a, b) ≠ (c, d), and there are no pairs of pairs in D(2h) satisfying the pattern. Similarly, if each c_{j} coincides with an b_{i}, then c = b and d = a, which violates a < b and c < d. Hence we only have to consider patterns where all four types of coincidences a_{i} = c_{j}, a_{i} = d_{j}, b_{i} = c_{j} and b_{i} = d_{j} occur (with different indices, in general), but in this case the relations a_{1} + … + a_{h} = b_{1} + … + b_{h} and c_{1} + … + c_{h} = d_{1} + … + d_{h} give two linearly independent relations between a_{1}, …, b_{h}, and thus these numbers are determined by 2h − 2 = l − 2 of them. Consequently, the number of pairs of pairs for each pattern is ≤ n^{l−2} in this case too, and the result follows.

We thus have, using (3) and np = k ≥ 1,

Δ = ∑_{l=2h}^{4h−1} |D(l)|p^{l} ⪯ ∑_{l=2h}^{4h−1} n^{l−2}p^{l} ⪯ n^{4h−3}p^{4h−1}.  (4)

Note further that |B(2h)| ⪰ n^{2h−1} (we will prove a more precise estimate in the next section). Returning to (2), we thus obtain, for some positive constants c and C,

P_{u}(Y = 0) ≤ ( ∏_{(a,b)∈B(2h)} P_{u}(I_{a,b} = 0)) exp{Cn^{4h−3}p^{4h−1}}
≤ (1 − p^{2h})^{cn^{2h−1}} exp{Cn^{4h−3}p^{4h−1}}
≤ exp{−cn^{2h−1}p^{2h} + Cn^{4h−3}p^{4h−1}}
= exp{−n^{2h−1}p^{2h} (c − Cn^{2h−2}p^{2h−1})}.  (5)

Now if

\frac{1}{n^{\frac{2h−1}{2h}}} ≪ p ≪ \frac{1}{n^{\frac{2h−2}{2h−1}}} ,

(5) reveals that P_{u}(Y = 0) → 0, showing, by monotonocity, that Theorem 1 holds for the altered model if p ≫ 1/n^{(2h−1)/2h}, i.e., if E(|A_{n}|) ≫ n^{1/2h}. We must now translate this fact into the format of the original problem, and thus need to compute, under the transformed model, P_{u}(A_{n} is B_{h}||A_{n}| = np), which, again by monotonicity, is smaller than P_{u}(A_{n} is B_{h}||A_{n}| ≤ np) and thus than P_{u}(A_{n} is B_{h})/P_{u}(|A_{n}| ≤ np). Now the numerator of this last quantity is asymptotically small if p ≫ 1/n^{(2h−1)/2h}, whilst the denominator is certainly, at least for large n, of magnitude close to 1/2. The theorem follows.

3. The behavior of the Sidon property at the threshold

As mentioned above, the first result of this section, which finds the asymptotic value of P(A_{n} is B_{h}) when |A_{n}| ∼ Λn^{1/2h} could have been obtained on using the methods of Section 2. We choose, however, to employ the Stein–Chen method of Poisson approximation [2] (which could, conversely, have been used to establish Theorem 1) to address a wider issue: If X denotes, as before, the number of episodes (a, b) (under the model P_{u}) for which A_{n} contains both the vectors a and b whose coordinates sum to the same value, then what can be said about the distribution of X (and not just the value of the point probability P_{u}(X = 0)?) Let L(U) denote the probability distribution of the random variable U, and Po(λ) the Poisson distribution with parameter λ. Finally, let d_{TV}(L(U), L(V)) be the total variation distance between L(U) and L(V), defined by

d_{TV}(L(U), L(V)) = sup_{A⊆Z^{+}} |P(U ∈ A) − P(V ∈ A)|.

Now for any three random variables U, V and W,

d_{TV}(L(U), L(V)) ≤ d_{TV}(L(U), L(W)) + P(V ≠ W),

so that in our context,

d_{TV}(L(X), Po(E_{u}(Y))) ≤ d_{TV}(L(Y), Po(E_{u}(Y))) + P_{u}(X ≠ Y),

where X and Y are as defined in Section 2. Since, as in the argument leading to (1), and using Lemma 1,

P_{u}(X ≠ Y) ≤ E_{u}(X − Y) = ∑_{l=1}^{2h−1} |B(l)|p^{l} ⪯ n^{2h−2}p^{2h−1} → 0  (6)

if p = o(1/n^{(2h−2)/(2h−1)}), we focus on bounding d_{TV}(L(Y), Po(E_{u}(Y)).

Our first task will be to obtain a tight estimate on λ = E_{u}(Y). Now

λ = ∑_{(a,b)∈B(2h)} P(I_{a,b} = 1) = p^{2h}|B(2h)|.  (7)

Loosely, we know that |B(2h)| ≍ n^{2h−1} so that λ ≍ p^{2h}n^{2h−1} = Λ^{2h} if p = Λn^{−(2h−1)/2h}, but we must be more exact.

We define the functions f_{j} = χ_{(0,1]}^{∗j}, j = 1, 2, …, to be the convolution powers of the characteristic function of (0, 1], i.e., f_{1}(x) = 1 when 0 < x ≤ 1 and 0 otherwise, and

f_{j+1}(x) = ∫_{x−1}^{x} f_{j}(t) dt, j ≥ 1.

(Note that f_{j}(x) equals the density function for the distribution of the sum of j independent random variables, each uniformly distributed on (0, 1].) Lemma 3. Let h ≥ 1 and let N_{m,n} be the number of h-subsets of {1, …, n} with sum m. Then

N_{m,n} = \frac{1}{h!}f_{h}(m/n)n^{h−1} + O(n^{h−2}).

(Recall our convention that the constant implicit in the O term does not depend on m or n.) Proof. Let N_{m,n,h}^{∗} be the number of sequences a = (a_{1}, …, a_{h}) with 1 ≤ a_{i} ≤ n for all i and a_{1} + … + a_{h} = m. Since the number of such sequences with distinct elements equals h!N_{m,n}, and the number of such sequences with two or more elements coinciding is O(n^{h−2}), it suffices to show that

N_{m,n,h}^{∗} = f_{h}(m/n)n^{h−1} + O(n^{h−2}).  (8)

This is trivially true for h = 1. Moreover, collecting sequences according to their last element a_{h}, it is seen that

N_{m,n,h}^{∗} = ∑_{j=1}^{n} N_{m−j,n,h−1}^{∗}

and (8) follows easily by induction, and approximating the appropriate integral by its Riemann sum.

Lemma 4. For every h ≥ 2,

|B(2h)| = κ_{h}n^{2h−1} + O(n^{2h−2}),

where

κ_{h} = \frac{1}{2(h!)^{2}} ∫_{0}^{h} f_{h}^{2}(x) dx > 0.

Proof. 2|B(2h)| equals the number of pairs (a, b) ∈ A×A with a_{1} +…+a_{h} = b_{1} +…+b_{h} and |a ∪ b| = 2h. Each such pair thus consists of two h-subsets a and b with the same sum m for some m ≤ hn; conversely, all pairs of two disjoint h-subsets with the same sum arise in this way. Hence

2|B(2h)| ≤ ∑_{m=1}^{hn} N_{m,n}^{2} ≤ 2|B(2h)| + N′,  (9)

where N′ is the number of pairs (a, b) with a, b ∈ A and a ∩ b ≠ ∅, and thus |a ∪ b| < 2h. Considering the three cases a < b, a = b and a > b, we obtain, using Lemma 1,

N′ ≤ 2 ∑_{l=1}^{2h−1} |B(l)| + |A| ⪯ n^{2h−2} + n^{h} ⪯ n^{2h−2}.  (10)

Next we use Lemma 3 and conclude that

∑_{m=1}^{hn} N_{m,n}^{2} = \frac{1}{h!^{2}} ∑_{m=1}^{hn} (f_{h}^{2}(m/n)n^{2h−2} + O(n^{2h−3}))
= \frac{n^{2h−2}}{h!^{2}} ∑_{m=1}^{hn} f_{h}^{2}(m/n) + O(n^{2h−2}).  (11)

Finally we have, using the fact that f′_{h}(x) = f_{h−1}(x) − f_{h−1}(x − 1) is bounded for every h ≥ 2,

∑_{m=1}^{hn} f_{h}^{2}(m/n) = ∑_{m=1}^{hn} n ∫_{(m−1)/n}^{m/n} (f_{h}^{2}(x) + O(n^{−1})) dx = n ∫_{0}^{h} f_{h}^{2}(x) dx + O(1). (12)

The lemma follows by combining (9), (10), (11) and (12).

The function f_{h} vanishes outside [0, h], and on each interval [i − 1, i], i = 1, …, h, it equals a polynomial; hence ∫_{0}^{h} f_{h}^{2} can in principle be computed directly for each h. This is easily done for small h, but quickly becomes rather tedious and does not seem to yield a general formula. We thus calculate the integral using Fourier methods. Lemma 5. If h ≥ 1, then

∫_{0}^{h} f_{h}^{2}(x) dx = \frac{1}{(2h − 1)!} ∑_{j=0}^{h−1}(−1)^{j}\binom{2h}{j}(h − j)^{2h−1}.

Proof. The Fourier transform of χ_{(0,1]} is

χ̂_{(0,1]}(t) = ∫_{0}^{1} e^{itx} dx = \frac{1}{it}(e^{it} − 1).

Since f̂_{h} = (χ̂_{(0,1]})^{h}, Plancherel’s formula yields

∫_{0}^{h} f_{h}^{2}(x) dx = ∫_{−∞}^{∞} f_{h}^{2}(x) dx = \frac{1}{2π} ∫_{−∞}^{∞} |f̂_{h}^{2}(t)| dt = \frac{1}{2π} ∫_{−∞}^{∞} \frac{|e^{it} − 1|^{2h}}{t^{2h}} dt.  (13)

Denote the numerator |e^{it} − 1|^{2h} = (e^{it} − 1)^{h}(e^{−it} − 1)^{h} by P (t). We integrate by parts 2h − 2 times, obtaining

∫_{0}^{h} f_{h}^{2}(x) dx = \frac{1}{π} ∫_{0}^{∞} \frac{P (t)}{t^{2h}} dt = \frac{1}{π(2h − 1)} ∫_{0}^{∞} \frac{P′(t)}{t^{2h−1}} dt = …
= \frac{1}{π(2h − 1)!} ∫_{0}^{∞} \frac{P^{(2h−2)}(t)}{t^{2}} dt.  (14)

(The integrals converge and the integrated parts vanish because P has a zero of order 2h at t = 0 and P and all its derivatives are bounded.)

A binomial expansion yields

P (t) = (e^{it} − 1)^{h}(e^{−it} − 1)^{h} = (−1)^{h}e^{−ith}(e^{it} − 1)^{2h} = ∑_{j=0}^{2h} \binom{2h}{j}(−1)^{h+j}e^{it(h−j)}

and thus (except for an extra constant term in the case h = 1)

P^{(2h−2)}(t) = ∑_{j=0}^{2h} \binom{2h}{j}(−1)^{j+1}(h − j)^{2h−2}e^{it(h−j)}

= ∑_{j=0}^{h−1} \binom{2h}{j}(−1)^{j+1}(h − j)^{2h−2}2 cos(h − j)t.

Hence, using also P^{(2h−2)}(0) = 0, (14) yields

∫_{0}^{h} f_{h}^{2}(x) dx = \frac{1}{(2h − 1)! π} ∫_{0}^{∞} \frac{P^{(2h−2)}(t) − P^{(2h−2)}(0)}{t^{2}} dt

= \frac{1}{(2h − 1)! π} ∑_{j=0}^{h−1} \binom{2h}{j}(−1)^{j+1}(h − j)^{2h−2} ∫_{0}^{∞} \frac{2 cos(h − j)t − 2}{t^{2}} dt.

Finally, for any k > 0,

∫_{0}^{∞} \frac{1 − cos kt}{t^{2}} dt = k ∫_{0}^{∞} \frac{1 − cos u}{u^{2}} du = k \frac{π}{2} ,

and the result follows. (The integral ∫_{0}^{∞} \frac{1−cos u}{u^{2}} du = \frac{π}{2} is well-known; alternatively, this follows by checking the case h = 1 of the lemma.)

We summarize the result.

Lemma 6.

E_{u}X = κ_{h}n^{2h−1}p^{2h} + O(n^{2h−2}p^{2h−1})  (15)

and

E_{u}Y = κ_{h}n^{2h−1}p^{2h} + O(n^{2h−2}p^{2h})  (16)

with

κ_{h} = \frac{1}{2(h!)^{2}(2h − 1)!} ∑_{j=0}^{h−1}(−1)^{j}\binom{2h}{j}(h − j)^{2h−1}.  (17)

Proof. (16) follows by combining (7) with Lemmas 4 and 5, and (15) by further using the estimate in (6).

In particular, if p = (Λ + o(1))n^{(1/2h)−1}, then both E_{u}X and E_{u}Y tend to κ_{h}Λ^{2h} as n → ∞.

The sum in (17) involves massive cancellation and does not easily yield asymptotic expressions. We therefore study the asymptotics of κ_{h} as h → ∞ by other means. Lemma 7. As h → ∞, ∫_{0}^{h} f_{h}^{2}(x) dx ∼ \sqrt{\frac{3}{πh}} and thus κ_{h} ∼ \sqrt{\frac{3}{4πh}}(h!)^{−2}. Proof. Since |e^{it} − 1| = 2| sin(t/2)|, (13) yields

∫_{0}^{h} f_{h}^{2}(x) dx = \frac{1}{2π} ∫_{−∞}^{∞} (\frac{sin(t/2)}{t/2})^{2h} dt = \frac{1}{π} ∫_{−∞}^{∞} (\frac{sin t}{t})^{2h} dt.

We divide this integral into two parts. First,

∫_{|t|≥1} (\frac{sin t}{t})^{2h} dt ≤ 2 ∫_{1}^{∞} \frac{dt}{t^{2h}} = \frac{2}{2h − 1} = o(h^{−1/2})

as h → ∞.

For |t| ≤ 1 we make the substitution t = x/\sqrt{h}. The Taylor series for sin t shows that \frac{sin t}{t} = 1 − \frac{t^{2}}{6} + O(t^{4}), and thus for each fixed x

(\frac{sin(x/\sqrt{h})}{x/\sqrt{h}})^{2h} = (1 − \frac{x^{2}}{6h} + O(h^{−2}))^{2h} → e^{−x^{2}/3};

moreover it follows that, when |t| ≤ 1, |\frac{sin t}{t} | ≤ 1 − t^{2}/7 and thus

(\frac{sin(x/\sqrt{h})}{x/\sqrt{h}})^{2h} ≤ (1 − \frac{x^{2}}{7h})^{2h} ≤ e^{−2x^{2}/7}, |x| ≤ \sqrt{h}.

Consequently, by dominated convergence,

\sqrt{h} ∫_{−1}^{1} (\frac{sin t}{t})^{2h} dt = ∫_{−\sqrt{h}}^{√\overline{h}} (\frac{sin(x/\sqrt{h})}{x/\sqrt{h}})^{2h} dx → ∫_{−∞}^{∞} e^{−x^{2}/3} dx = \sqrt{3π},

and the result follows.

The basic Stein–Chen approximation theorem we employ is as follows:

Poisson approximation theorem for positively related variables (Corollary 2.E.1 in [2]): Consider a sum W = ∑_{j∈J} I_{j} of indicator random variables, and set λ = E(W). Suppose that the variables I_{j} are increasing functions of some underlying independent random variables. Then

d_{TV}(L(W), Po(λ)) ≤ \frac{1 − e^{−λ}}{λ} (Var(W) − λ + 2 ∑_{j} P^{2}(I_{j} = 1)) .

Armed with the above result (or alternatively Corollary 2.C.4 in [2] together with a simple explicit coupling), we are ready to prove

Theorem 2. Consider a subset A_{n} formed by randomly and independently choosing each element of [n] with probability p_{n}. Let X and Y be as defined above and set λ = E_{u}(Y). Then

d_{TV}(L(X), Po(λ)) → 0 (n → ∞)

provided that p_{n} = o(1/n^{(2h−2)/(2h−1)}). In particular, if E_{u}(|A_{n}|) = (Λ + o(1))n^{1/2h}, then P_{u}(X = 0) → exp{−κ_{h}Λ^{2h}} (n → ∞), where κ_{h} is given by (17). Proof. We clearly need to just compute a bound on d_{TV}(L(Y), Po(λ)). The result quoted above yields immediately (the underlying independent variables are the indicators for the individual numbers in [n])

d_{TV}(L(Y), Po(λ)) ≤ \frac{1}{λ} (Var_{u}(Y) − λ + 2 ∑_{(a,b)∈B(2h)} P_{u}^{2}(I_{a,b} = 1))

= \frac{Var_{u}(Y)}{λ} − 1 + 2p^{2h}

= \frac{1}{λ} ∑_{(a,b)∼(c,d)} \{E_{u}(I_{a,b}I_{c,d}) − p^{4h}\} + \frac{1}{λ} ∑_{(a,b)∈B(2h)} \{E_{u}(I_{a,b}^{2}) − p^{4h}\} − 1 + 2p^{2h}

≤ \frac{Δ}{λ} + 2p^{2h} ⪯ n^{2h−2}p^{2h−1},  (18)

where the last estimate in (18) follows by (4) and (16). This establishes Theorem 2.

Even though Theorem 2 is a result about sets of random size, it can readily be translated into a statement about random subsets of a fixed size: Corollary. Consider a subset A_{n} of size k_{n} chosen at random from the \binom{n}{k_{n}} such subsets of [n] = {1, 2, …, n}. Then for any h ≥ 2,

k_{n} = (Λ + o(1))n^{1/2h} ⇒ P(A_{n} is B_{h}) → e^{−κ_{h}Λ^{2h}} (n → ∞)

where κ_{h} is given by (17). Proof. Let

p_{n}^{+} = \frac{k_{n}}{n} + \frac{n^{1/4h} log n}{n}

and

p_{n}^{−} = \frac{k_{n}}{n} − \frac{n^{1/4h} log n}{n};

these choices are made for convenience only, and are certainly not unique. Then both p_{n}^{+} and p_{n}^{−} are of the form (Λ + o(1))n^{−(2h−1)/2h}; let us use them to generate random sets A_{n}^{+} and A_{n}^{−} as in Theorem 2. Note that

E_{u}(|A_{n}^{+}|) = k_{n} + n^{1/4h} log n

and

Var_{u}(|A_{n}^{+}|) < E_{u}(|A_{n}^{+}|) = O(n^{1/2h}).

Furthermore, by Chebychev’s inequality,

P_{u}(|A_{n}^{+}| < k_{n}) ⪯ \frac{1}{log^{2} n} → 0,

and thus for a set A_{n}^{+} of cardinality k_{n},

P(A_{n}^{+} is not a B_{h} set) = P_{u}(A_{n}^{+} is not a B_{h} set||A_{n}^{+}| = k_{n})

≤ P_{u}(A_{n}^{+} is not a B_{h} set||A_{n}^{+}| ≥ k_{n})

≤ \frac{P_{u}(A_{n}^{+} is not a B_{h} set)}{P_{u}(|A_{n}^{+}| ≥ k_{n})} → 1 − e^{−λ}

(λ = κ_{h}Λ^{2h}), so that for a randomly chosen A_{n} with |A_{n}| = k_{n},

lim sup_{n→∞} P(A_{n} is not a B_{h} set) ≤ 1 − e^{−λ}.

The opposite inequality, which shows that

lim inf_{n→∞} P(A_{n} is not a B_{h} set) ≥ 1 − e^{−λ}

follows on using a similar argument with the set A_{n}^{−}. This proves the corollary.

Theorem 3. Consider, under the model P_{u}, the ensemble {I_{a,b} : a_{1} + … + a_{h} = b_{1} + … + b_{h}; a < b} of dependent indicator random variables. Then

d_{TV} (L{I_{a,b}}, ∏ Po(μ_{a,b})) → 0

as n → ∞ provided that p = o(1/n^{(4h−3)/(4h−1)}), where μ_{a,b} = E_{u}(I_{a,b}) = p^{2h} if a, b are two disjoint h-tuples of distinct elements, and μ_{a,b} = 0 otherwise. Proof. Let K_{a,b} = I_{a,b} if (a, b) ∈ B(2h), with K_{a,b} ≡ 0 otherwise. Since

d_{TV} (L{I_{a,b}}, ∏ Po(μ_{a,b}))
≤ d_{TV} (L{K_{a,b}}, ∏ Po(μ_{a,b})) + d_{TV}(L{I_{a,b}}, L{K_{a,b}})
≤ d_{TV} (L{K_{a,b}}, ∏ Po(μ_{a,b})) + E_{u}(X − Y)

and p = o(1/n^{(2h−2)/(2h−1)}) which implies E_{u}(X − Y) → 0, we see that the result will follow if we can establish that d_{TV}(L{K_{a,b}}, ∏ Po(μ_{a,b})) → 0. Now we invoke Corollary 10.J.1 and Theorem 2.E in [2] which yield,

d_{TV} (L{K_{a,b}}, ∏ Po(μ_{a,b})) ≤ (Var_{u}(Y) − λ + 2 ∑_{(a,b)∈B(2h)} P_{u}^{2}(I_{a,b} = 1)) , (19)

where λ = E_{u}(Y). Now it is easy to check that the bound in (19) reduces, as in the argument leading to (18), to a term of order n^{4h−3}p^{4h−1}; the different rate results due to the absence of the “magic factor” of (1 − e^{−λ})/λ that is present in the univariate case. This establishes the result; note that

\frac{1}{n^{(2h−1)/2h}} ≤ \frac{1}{n^{(4h−3)/(4h−1)}} ≤ \frac{1}{n^{(2h−2)/(2h−1)}} .

Remarks. Theorem 3 can easily be restated in terms of the measure P; we skip the details. In any event, this result provides a nice global view of the presence/absence of various taboo (i.e., B_{h}-property producing) integer sums in the random set A. Also, since the total variation distance is preserved under any functional, we may use Theorem 3 to estimate probabilities such as P(a ≤ Ψ ≤ b), where Ψ equals the number of integers m which can be represented as two or more integer sums.

Acknowledgements. A preliminary version of the work reported here was presented at the IMA Workshop on Discrete Random Structures in Minneapolis in November 1993. The research of AG, NL and RR was supported by NSF grants DMS-9200409 and DMS-9322460; SJ acknowledges the support of the Göran Gustafsson Foundation for Research in Natural Sciences and Medicine. We thank Sid Graham for introducing us to Sidon sequences, and for useful discussions. We thank the referees for finding an error in a previous version of the paper.

References

1. N. ALON and J. SPENCER, “The Probabilistic Method,” John Wiley and Sons, Inc., New York, 1992.

2. A.D. BARBOUR, L. HOLST and S. JANSON, “Poisson Approximation,” Oxford University Press, Oxford, 1992.

3. P. ERDŐS and S. FREUD, On sums of a Sidon sequence, J. Number Theory 38 (1991), 196–205.

4. S.W. GRAHAM, B_{h} sequences, in “Analytic Number Theory”, Proceedings of a Conference in Honor of Heini Halberstam, eds. B.C. Berndt, H.G. Diamond and A.J. Hildebrand, Birkhäuser 1996, 431–449.

5. H. HALBERSTAM and K. ROTH, “Sequences,” Springer-Verlag, New York, 1983.

6. B. LINDSTRÖM, An inequality for B_{2} sequences, J. Comb. Theory 6 (1969), 211–212.

7. M.B. NATHANSON, “Additive Number Theory: Inverse Problems and the Geometry of Sumsets”, Springer-Verlag, New York, 1996.

8. J. SPENCER and P. TETALI, Sidon sets with small gaps, in “Discrete Probability and Algorithms,” The IMA Volumes in Mathematics and its Applications, Vol. 72, D. Aldous, P. Diaconis, J. Spencer and J. M. Steele, eds., Springer-Verlag, New York, 1995.