INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 7 (2007), #A32

RANDOM B_{h} SETS AND ADDITIVE BASES IN ℤ_{N}

Csaba Sándor^{1}

Department of Stochastics, Budapest University of Technology and Economics, Hungary

                           csandor@math.bme.hu

Received: 12/22/06, Revised: 6/20/07, Accepted: 6/22/07, Published: 7/3/07

Abstract

We determine a threshold function for B_{h} and additive basis properties in ℤ_{n}.

1. Introduction

We use the following notations: ℤ denotes the integers 0, ±1, ±2, …; ℕ is the set of positive integers; ℤ_{n} is the additive cyclic group of order n. Members of a set S are referred to as {s_{1}, s_{2}, … }. The cardinality of a finite set S is denoted by |S|. A multiset q = {q_{1}, …, q_{k}}_{m} can be formally defined as a pair (Q, m), where Q is the set of distinct elements of q and m : Q → ℕ, where m(q) is the multiplicity of q ∈ q for each q ∈ Q. The number of distinct elements of q is denoted by |q|_{d}. The usual set operations such as union, intersection and Cartesian product can be easily generalized for multisets. In this paper we use the intersection: suppose that (A, m) and (B, n) are multisets, then the intersection can be defined as (A ∩ B, f), where f(x) = min{m(x), n(x)}.

For a given S ⊂ ℤ_{n} and x ∈ ℤ_{n} denote by r_{S,h}(x) the number of different representations x = s_{1} + ⋯ + s_{h} with s_{i} ∈ S, that is

r_{S,h}(x) = |{{s_{1}, …, s_{h}}_{m} : s_{1} + ⋯ + s_{h} = x, s_{i} ∈ S}|.

A set S ⊂ ℤ_{n} is called B_{h} set if the number of distinct representation of x as s_{1} +⋯+s_{h}, s_{i} ∈ S is at most 1, that is r_{S,h}(x) ≤ 1 for all x ∈ ℤ_{n}. A set S ⊂ ℤ_{n} is called additive h-basis if every element in ℤ_{n} can be represented as the sum of not necessarily distinct h elements of the set S, that is r_{S,h}(x) ≥ 1 for every x ∈ ℤ_{n}.

For n a positive integer, let 0 ≤ p_{n} ≤ 1. The random subset S(n, p_{n}) is a probabilistic space over the set of subsets of ℤ_{n} determined by P r(k ∈ S_{n}) = p_{n} for every k ∈ ℤ_{n}, with these events being mutually independent. This model is often used for proving the existence of certain sequences. Given any combinatorial number theoretic property P, there is a probability that S(n, p_{n}) satisfies P, which we write P r{S(n, p_{n}) ⊧ P }. The function r(n) is called a threshold function for a combinatorial number theoretic property P if

1Supported by Hungarian National Foundation for Scientific Research, Grant No. T 49693 and 61908.

(i) When p_{n} = o(r(n)), lim_{n→∞} P r{S(n, p_{n}) ⊧ P } = 0,

(ii) When r(n) = o(p(n)), lim_{n→∞} P r{S(n, p_{n}) ⊧ P } = 1,

or visa versa.

The goal of this paper is to determine a threshold function for B_{h} sets and additive h-bases in ℤ_{n}. We use the typical notation exp (x) = e^{x}

Theorem 1.1. Let c > 0 be arbitrary. Let us suppose that p_{n} = _{\frac{c}{n^{\frac{2h−1}{2h}}}} and the random set A_{n} ⊂ ℤ_{n} is defined the following way: For every k ∈ ℤ_{n} we have P r(k ∈ A_{n}) = p_{n}.

Then lim_{n→∞} P r\{A_{n} is a B_{h} set\} = exp (−\frac{c^{2h}}{2(h!)^{2}} ).

Theorem 1.2. Let c be an arbitrary real number. Suppose that p_{n} = \frac{(h!nlogn)^{1/h}(1+ \frac{c}{hlogn})}{n} and the random set A_{n} ⊂ ℤ_{n} is defined the following way: For every k ∈ ℤ_{n} we have P r{k ∈ A_{n}} = p_{n}. Then lim_{n→∞} P r(A_{n} is an additive h-basis) = exp (− exp (−c)).

2. Proofs

In order to prove the theorems we need two lemmas from probability theory (see e.g. [1] p. 41, 95-98.). In many instances, we would like to bound the probability that none of the bad events B_{i}, i ∈ I, occur. If the events are mutually independent, then P r(∩_{i∈I} \overline{B_{i}}) = ∏_{i∈I} P r(\overline{B_{i}}). When the B_{i} are ”mostly” independent, the Janson’s inequality allows us, sometimes, to say that these two quantities are ”nearly” equal. Let Ω be a finite universal set and R be a random subset of Ω given by P r(r ∈ R) = p_{r}, these events being mutually independent over r ∈ Ω. Let E_{i}, i ∈ I be subsets of Ω, where I a finite index set. Let B_{i} be the event E_{i} ⊂ R. Let X_{i} be the indicator random variable for B_{i} and X = ∑_{i∈I} X_{i} be the number of E_{i}s contained in R. The event ∩_{i∈I} \overline{B_{i}} and X = 0 are then identical. For i, j ∈ I, we write i ∼ j if i ≠ j and E_{i} ∩ E_{j} ≠ ∅. We define Δ = ∑_{i∼j} P r(B_{i} ∩ B_{j}), here the sum is over ordered pairs. We set M = ∏_{i∈I} P r(\overline{B_{i}}).

Lemma 1.3 (Janson’s inequality). Let B_{i}, i ∈ I, Δ, M be as above and assume that P r(B_{i}) ≤ ϵ for all i. Then

M ≤ P r (⋂_{i∈I} \overline{B}_{i}) ≤ M exp (\frac{1}{1 − ϵ} · \frac{Δ}{2}).

The more traditional approach to the Poisson paradigm is called Brun’s sieve, for its use by the number theorist T. Brun. Let F_{1}, …, F_{m} be events, X_{i} the indicator random variable for F_{i}, and X = X_{1} + ⋯ + X_{m} the number of B_{i} that hold. Let there be a hidden parameter n (so that actually m = m(n), B_{i} = B_{i}^{(n)}, X = X^{(n)}) which will define our O notations. Define

S^{(r)} = ∑ P r{B_{i_{1}} ∧ ⋯ ∧ B_{i_{r}}},

where the sum is over all sets {i_{1}, …, i_{r}} ⊆ {1, …, m}. The inclusion-exclusion principle gives that P r\{X = 0\} = P r\{\overline{B}_{1} ∧ ⋯ ∧ \overline{B}_{m}\} = 1 − S^{(1)} + S^{(2)} − ⋯ + (−1)^{r}S^{(r)} · · ·.

Lemma 1.4. Suppose there is a constant μ so that E(X) = S^{(1)} → μ and such that for every fixed r,

E (\frac{X^{(r)}}{r!} ) = S^{(r)} → \frac{μ^{r}}{r!} .

Then P r\{X = 0\} → exp (−μ) and, for every t, we have P r(X = t) → \frac{μ^{t}}{t!} exp (−μ).

In order to prove the theorems we need two lemmas. In the sequel, for the sake of brevity, we write u = {u_{1}, …, u_{h}}_{m} and v = {v_{1}, …, v_{h}}_{m} with u ≠ v. For every a ∈ ℤ_{n} and h, t ∈ ℕ, 0 < t ≤ h, let

S_{a,h,t} = |{u : u_{i} ∈ ℤ_{n} ∑_{i=1}^{h} u_{i} = a, |u|_{d} = t}|

and for every a_{1}, a_{2} ∈ ℤ_{n} and h, t, s, k ∈ ℕ with 0 < k ≤ min{s, t} let

C_{a_{1},a_{2},h,t,s,k} = |{{u, v} : ∑_{i=1}^{h} u_{i} = a_{1}, ∑_{i=1}^{h} v_{i} = a_{2}, |u|_{d} = s, |v|_{d} = t, |u ∩ v|_{d} = k}| .

Lemma 1.5. For every a ∈ ℤ_{n} and h ≥ 2 we have

1. S_{a,h,h} = \frac{n^{h−1}}{h!} + O_{h}(n^{h−2});

2. S_{a,h,t} = O_{h}(n^{t−1}) for 1 ≤ t ≤ h − 1.

Proof. Case (1): By the definition of S_{a,h,h}

h!S_{a,h,h} = |{(u_{1}, …, u_{h}) : u_{i} ∈ ℤ_{n}, ∑_{i=1}^{h} u_{i} = a, and u_{i} ≠ u_{j} for i ≠ j}| . (1)

An upper bound for (1) is n(n − 1) … (n − h + 2) and a lower bound is n(n − 1) … (n − h + 3)(n − (h − 2) − (h − 2) − 2) because we have n(n − 1) … (n − (h − 3)) possibilities for u_{1}, …, u_{h−2} and the conditions u_{h−1} ≠ u_{i}, u_{h} ≠ u_{i} for 1 ≤ i ≤ h − 2 and u_{h−1} ≠ u_{h} exclude at most h − 2 + h − 2 + 2 choices for u_{h−1}.

Case (2): The condition |u|_{d} = t implies that there is a partition {1, …, h} = ⋃_{i=1}^{t} A_{i}

such that u_{i} = u_{j} if and only if 1 ≤ i, j ≤ h are in the same A_{l}. Fix such a partition. Then there are n choices for the elements u_{i}, i ∈ A_{1}, then (n − 1) possibilities for the elements u_{i}, i ∈ A_{2} etc. and finally (n − (t − 2)) choices for the elements u_{i}, i ∈ A_{t−1}. It follows from this that if we have already chosen the elements u_{i}, i ∈ ⋃_{i=1}^{t−1} A_{i} then we have at most t ≤ h possibilities for the elements u_{i}, i ∈ A_{t}. In order to finish the proof we mention that the number of suitable partitions is O_{h}(1).

Lemma 1.6. For every a_{1}, a_{2} ∈ ℤ_{n} and h ≥ 2 we have

1. C_{a_{1},a_{2},h,h,h,0} = \frac{n^{2h−2}}{(h!)^{2}2} + O_{h}(n^{2h−3});

2. C_{a_{1},a_{2},h,t,s,k} = O_{h}(n^{t+s−k−2}) for t ≥ s and t > k ≥ 0;

3. C_{a_{1},a_{2},h,s,s,s} = O_{h}(n^{s−2}) for every 2 ≤ s < h.

Proof. Case (1): By the definition of C_{a_{1},a_{2},h,h,h,0}

2(h!)^{2}C_{a_{1},a_{2},h,h,h,0} = |{( (u_{1}, …, u_{h}) , (v_{1}, …, v_{h}) ) : u_{i} ≠ u_{j}, v_{i} ≠ v_{j}, u_{i} ≠ v_{j},
∑_{i=1}^{h} u_{i} = a_{1}, ∑_{i=1}^{h} v_{i} = a_{2}}| . (2)

An upper bound for (2) is n^{h−1}n^{h−1} and a lower bound for (2) is n(n − 1) … (n − (h − 3))(n − (h − 2) − (h − 2) − 2)(n − h)(n − (h + 1)) … (n − h − (h − 3))(n − (2h − 2) − (2h − 2) − 2), because we have n(n − 1) … (n − (h − 3)) choices for u_{1}, …, u_{h−2}. After choosing u_{1}, …, u_{h−2} there are at least n − (h − 2) − (h − 2) − 2 possibilities left for u_{h−1} because u_{h−1} ≠ u_{j} and u_{h} ≠ u_{j} for 1 ≤ j ≤ h − 2 and u_{h−1} ≠ u_{h}. After fixing u_{1}, …, u_{h} we have (n − h) … (n − (2h − 2)) choices for v_{1}, …, v_{h−2}. Finally, we have at least n − 2h − (2h − 4) − 2 choices for v_{h−1} because v_{h−1} ≠ u_{j}, v_{h} ≠ u_{j}, for 1 ≤ j ≤ h, v_{h−1} ≠ v_{j}, v_{h} ≠ v_{j} for 1 ≤ j ≤ h − 2 and v_{h−1} ≠ v_{h}.

Case (2): Obviously,

C_{a_{1},a_{2},h,t,s,k} ≤ |{((u_{1}, …, u_{h}), (v_{1}, …, v_{h})) : ∑_{i=1}^{h} u_{i} = a_{1}, ∑_{i=1}^{h} v_{i} = a_{2},
|u|_{d} = t, |v|_{d} = s, |u ∩ v|_{d} = k}|. (3)

By the conditions |u|_{d} = s, |v|_{d} = t there are partitions {1, …, h} = ∪_{i=1}^{t}A_{i} = ⋃_{i=1}^{s} B_{i} such that u_{i} = u_{j} if and only if there exists an 1 ≤ l ≤ t such that i, j ∈ A_{l}, and v_{i} = v_{j} if and only if there exists an 1 ≤ l ≤ s such that i, j ∈ B_{l}. We have at most hn^{s−1} choices for (v_{1}, …, v_{h}) with ∑_{i=1}^{h} v_{i} = a_{2}. The condition |u ∩ v|_{d} = k implies that there are injections χ_{u} : {1, …, k} → {1, …, t} and χ_{v} : {1, …, k} → {1, …, s} such that u_{i} = v_{j} if and only if there exists a 1 ≤ l ≤ k such that u_{i} ∈ A_{χ_{u}(l)} and v_{j} ∈ B_{χ_{v}(l)}. Hence we get that there are at most hn^{t−k−1} choices for the v_{i}s, i ∈ {1, …, h} \ ⋃_{i=1}^{k} B_{χ_{v}(i)}. Since the numbers of partitions and injections are O_{h}(1), the proof is completed.

Case (3): Evidently,

C_{a_{1},a_{2},h,s,s,s} ≤ |{((u_{1}, …, u_{h}), (v_{1}, …, v_{h})) : ∑_{i=1}^{h} u_{i} = a_{1}, ∑_{i=1}^{h} v_{i} = a_{2}, u ≠ v,
|u|_{d} = s, |v|_{d} = s, |u ∩ v|_{d} = s}|. (4)

By the conditions |u|_{d} = s, |v|_{d} = s there are partitions {1, …, h} = ⋃_{i=1}^{s} A_{i} = ⋃_{i=1}^{s} B_{i} such that u_{i} = u_{j} if and only if there exists an 1 ≤ l ≤ s such that i, j ∈ A_{l} and v_{i} = v_{j} if and only if there exists an 1 ≤ m ≤ s such that i, j ∈ B_{m}. The condition |u ∩ v|_{d} = k implies that there is a bijection χ : {1, …, s} → {1, …, s} such that u_{i} = v_{j} if and only if there exists a 1 ≤ l ≤ s such that i ∈ A_{l} and j ∈ B_{χ(l)}. Since u ≠ v, therefore there exists a 1 ≤ l ≤ s such that |A_{l}| ≠ |B_{χ(l)}|. Fix such an l. Then there exists a 1 ≤ k ≤ s such that \frac{|A_{k}|}{|B_{χ(k)}|} ≠ \frac{|A_{l}|}{|B_{χ(l)}|}, because otherwise |A_{k}| = |B_{χ(k)}|\frac{|A_{l}|}{|B_{χ(l)}|} for every 1 ≤ k ≤ s, but

h = ∑_{k=1}^{s} |A_{k}| = \frac{|A_{l}|}{|B_{χ(l)}|} ∑_{k=1}^{s} |B_{χ(k)}| = \frac{|A_{l}|}{|B_{χ(l)}|}h,

which is a contradiction. Fix such a k. Let {i_{1}, …, i_{s−2}} = {1, …, s} \ {k, l}. We have n(n − 1) ⋯ (n − (s − 3)) choices for the elements u_{i}, i ∈ ⋃_{j=1}^{s−2} A_{i_{j}}. After fixing the

elements u_{i}, i ∈ ⋃_{j=1}^{s−2} A_{i_{j}} let ∑_{j=1}^{s−2} ∑_{m∈A_{i_{j}}} u_{m} = U and ∑_{j=1}^{s−2} ∑_{m∈B_{χ(i_{j})}} v_{m} = V. Then we need

x, y ∈ ℤ_{n} such that U + |A_{k}|x + |A_{l}|y = a_{1} and V + |B_{χ(k)}|x + |B_{χ(l)}|y = a_{2}. Hence,

(|A_{l}||B_{χ(k)}| − |A_{k}||B_{χ(l)}|)y = a_{1}|B_{χ(k)}| + V |A_{k}| − U|B_{χ(k)}| − a_{2}|A_{k}|.  (5)

After fixing 1 ≤ k, l ≤ s and the elements u_{i}, i ∈ ⋃_{j=1}^{s−2} A_{i_{j}}, the elements U and V are

determined, therefore the right-hand side in (3) is unique. Since 0 < ||A_{l}||B_{χ(k)}| − |A_{k}||B_{χ(l)}|| ≤ h^{2}, therefore the number of possible y’s is at most h^{2} and after fixing y we have at most h choices for x. Finally we mention that we have got O_{h}(1) choices for the partitions and bijection.

Proof of Theorem 1. For each unordered, different u_{1}, …, u_{h} ∈ ℤ_{n} and v_{1}, …, v_{h} ∈ ℤ_{n} with ∑_{i=1}^{h} u_{i} = ∑_{i=1}^{h} v_{i}. Let B_{u,v} be the event that u_{1}, …, u_{h}, v_{1}, …, v_{h} ∈ A_{n}. In the following we suppose that ∑_{i=1}^{h} u_{i} = ∑_{i=1}^{h} v_{i}. If we prove Δ = ∑_{{u,v}:|u∩v|_{d}>0} Pr{B_{u,v}} =

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 7 (2007), #A32 6

o(1), then by the Janson inequality we have

Pr{A_{n} is B_{h} set} = (1 + o(1)) ∏_{{u,v}} Pr{B_{u,v}}
= (1 + o(1)) (  ∏_{{u,v}:|u|_{d}=h,|v|_{d}=h,|u∩v|_{d}=0} Pr{B_{u,v}})

× (∏_{k=1}^{h−1} ∏_{{u,v}:|u|_{d}=h,|v|_{d}=h,|u∩v|_{d}=k} Pr{B_{u,v}})

× (∏_{s=2}^{h−1} ∏_{{u,v}:|u|_{d}=s,|v|_{d}=s,|u∩v|_{d}=s} Pr{B_{u,v}})

× (∏_{s=1}^{h−1} ∏_{k=0}^{s−1} ∏_{{u,v}:|u|_{d}=s,|v|_{d}=s,|u∩v|_{d}=k} Pr{B_{u,v}})

× (∏_{s=1}^{h−1} ∏_{t=s+1}^{h} ∏_{k=0}^{s} ∏_{{u,v}:|u|_{d}=s,|v|_{d}=t,|u∩v|_{d}=k} Pr{B_{u,v}})

= P_{1}P_{2}P_{3}P_{4}P_{5},

where, by Lemma 1.6.1,

P_{1} = ∏_{a∈ℤ_{n}} ∏ ; {u,v}:|u|_{d}=h,|v|_{d}=h,|u∩v|_{d}=0,∑_{i=1}^{h} u_{i} ∑_{i=1}^{h} v_{i}=a Pr{B_{u,v}}
= (1 − \frac{c^{2h}}{n^{2h−1}} )^{^{\frac{n^{2h−1}}{2(h!)^{2}}} (1+O_{h}(\frac{1}{n}))}
= (1 + o(1)) exp (−\frac{c^{2h}}{2(h!)^{2}} ),

by Lemma 1.6.2,

P_{2} = ∏_{a∈ℤ_{n}} ∏_{k=1}^{h−1} ∏ ; {u,v}:|u|_{d}=h,|v|_{d}=h,|u∩v|_{d}=k,∑_{i=1}^{h} u_{i}=∑_{i=1}^{h} v_{i}=a Pr{B_{u,v}}
= ∏_{k=1}^{h−1}(1 − p_{n}^{2h−k})^{O_{h}(n^{2h−k−1})}
= ∏_{k=1}^{h−1} exp ((p_{n}n)^{2h−k}O_{h} (\frac{1}{n}))
= exp (o(1)),

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 7 (2007), #A32 7

by Lemma 1.6.3,

P_{3} = ∏_{a∈ℤ_{n}} ∏_{s=2}^{h−1} ∏ ; {u,v}:|u|_{d}=s,|v|_{d}=s,|u∩v|_{d}=s,∑_{i=1}^{h} u_{i}=∑_{i=1}^{h} v_{i}=a Pr{B_{u,v}}
= ∏_{s=2}^{h−1}(1 − p_{n}^{s})^{O_{h}(n^{s−1})}
= ∏_{k=1}^{h} exp ((−p_{n}n)^{k}O_{h} (\frac{1}{n}))
= exp (o(1)),

by Lemma 1.6.3,

P_{4} = ∏_{a∈ℤ_{n}} ∏_{s=1}^{h−1} ∏_{k=0}^{s−1} ∏ ; {u,v}:|u|_{d}=s,|v|_{d}=s,|u∩v|_{d}=k,∑_{i=1}^{h} u_{i}=∑_{i=1}^{h} v_{i}=a Pr{B_{u,v}}
= ∏_{s=1}^{h} ∏_{k=0}^{s−1}(1 − p_{n}^{2s−k})^{O_{h}(n^{2s−k−1})}
= ∏_{s=1}^{h} ∏_{k=0}^{s−1} exp (−(p_{n}n)^{2s−k}O_{h}(\frac{1}{n}))
= exp (o(1)),

and, by Lemma 1.6.2,

P_{5} = ∏_{a∈ℤ_{n}} ∏_{s=1}^{h−1} ∏_{t=s+1}^{h} ∏_{k=0}^{s} ∏ ; {u,v}:|u|_{d}=s,|v|_{d}=t,|u∩v|_{d}=k,∑_{i=1}^{h} u_{i}=∑_{i=1}^{h} v_{i}=a Pr{B_{u,v}}
= ∏_{s=1}^{h−1} ∏_{t=s+1}^{h} ∏_{k=0}^{s}(1 − p_{n}^{s+t−k})^{O(n^{s+t−k−1})} = exp (o(1)).

Hence, it remains to prove that Δ = o(1). In order to prove Δ = o(1) we partition Δ as

Δ = ∑_{{u,v}:|u∩v|_{d}>0} Pr{B_{u,v}}
= ∑_{s=1}^{h−1} ∑_{{u,v}:|u|_{d}=s,|v|_{d}=s,|u∩v|_{d}=s} Pr{B_{u,v}}

+ ∑_{s=2}^{h} ∑_{k=1}^{s−1} ∑_{{u,v}:|u|_{d}=s,|v|_{d}=s,|u∩v|_{d}=k} Pr{B_{u,v}}

+ ∑_{s=1}^{h−1} ∑_{t=s+1}^{h} ∑_{k=0}^{s} ∑_{{u,v},|u|_{d}=s,|v|_{d}=t,|u∩v|_{d}=k} Pr{B_{u,v}}

= ∑_{1} + ∑_{2} + ∑_{3} .

By Lemma 1.6.3,

∑_{1} = ∑_{a∈ℤ_{n}}  ∑_{s=1}^{h−1} ∑ ; {u,v}:|u|_{d}=s,|v|_{d}=s,|u∩v|_{d}=s,∑_{i=1}^{h} u_{i}=∑_{i=1}^{h} v_{i}=a Pr{B_{u,v}}

= ∑_{s=2}^{h−1} O_{h}(n^{s−1})p_{n}^{s}

= O_{h} (\frac{1}{n} ∑_{s=2}^{h−1}(p_{n}n)^{s}) = o(1),

by Lemma 1.6.2,

∑_{2} = ∑_{a∈ℤ_{n}}  ∑_{s=2}^{h} ∑_{k=1}^{s−1} ∑ ; {u,v}:|u|_{d}=s,|v|_{d}=s,|u∩v|_{d}=k,∑_{i=1}^{h} u_{i}=∑_{i=1}^{h} v_{i}=a Pr{B_{u,v}}

= ∑_{s=2}^{h} ∑_{k=1}^{s−1} O_{h}(n^{2s−k−1})p_{n}^{2s−k}

= O_{h} (\frac{1}{n} ∑_{s=2}^{h} ∑_{k=1}^{s−1}(p_{n}n)^{2s−k}) = o(1),

and by Lemma 1.6.2,

∑_{3} = ∑_{a∈ℤ_{n}}  ∑_{s=1}^{h−1} ∑_{t=s+1}^{h} ∑_{k=0}^{s} ∑ ; {u,v},|u|_{d}=s,|v|_{d}=t,|u∩v|_{d}=k,∑_{i=1}^{h} u_{i}=∑_{i=1}^{h} v_{i}=a Pr{B_{u,v}}

= ∑_{s=1}^{h−1} ∑_{t=s+1}^{h} ∑_{k=1}^{s} O_{h}(n^{t+s−k−1})p_{n}^{t+s−k}

= O_{h} (\frac{1}{n} ∑_{s=1}^{h−1} ∑_{t=s+1}^{h} ∑_{k=1}^{s}(p_{n}n)^{t+s−k}) = o(1),

which completes the proof.

Proof of Theorem 2. For a fixed x ∈ ℤ_{n} and y_{1}, …, y_{h} ∈ ℤ_{n} with ∑_{i=1}^{h} y_{i} = x let y = {y_{1}, …, y_{h}} and let B_{y,x} be the event y_{1}, …, y_{h} ∈ A_{n}. For a fixed x ∈ ℤ_{n} let C_{x} = ∩_{y,∑_{i=1}^{h} y_{i}=x}\overline{B}_{y,x}. Obviously,

Pr\{A_{n} is an h-basis\} = Pr(∩_{x∈ℤ_{n}} \overline{C_{x}}).

By Lemma 1.4 it is sufficient to show that for every fixed positive integer r we have

∑_{\{x_{1},...,x_{r}\}:x_{i}∈ℤ_{n},x_{i}≠x_{j}} Pr\{C_{x_{1}} ∩ ⋯ ∩ C_{x_{r}}\} → \frac{exp (−rc)}{r!}.

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 7 (2007), #A32 9

In order to estimate

∑_{\{x_{1},...,x_{r}\}:x_{i}∈Z_{n},x_{i}≠x_{j}} Pr\{C_{x_{1}} ∩⋯∩C_{x_{r}}\} = ∑_{\{x_{1},...,x_{r}\}:x_{i}∈Z_{n},x_{i}≠x_{j}} Pr\{∩_{1≤i≤r∩} ∩_{y:∑_{j=1}^{h} y_{j}=x_{i}} \overline{B}_{y,x_{i}}\}

we use Janson’s inequality. Obviously, Pr{B_{y,x_{i}}} = o(1). If we prove Δ = o(1), then by Lemmas 1.3 and 1.5, and the definition of p_{n}

∑_{\{x_{1},...,x_{r}\}:x_{i}∈Z_{n},x_{i}≠x_{j}} Pr \{ ⋂_{1≤i≤r∩} ⋂ ; y:∑_{j=1}^{h} y_{j}=x_{i} \overline{B}_{y,x_{i}} \}
= (1 + o(1)) ∏_{i=1}^{r} ∏ ; y:∑_{j=1}^{h} y_{j}=x_{i} Pr\{\overline{B}_{y,x_{i}}\}
= (1 + o(1)) ∏_{i=1}^{r} ∏_{k=1}^{h} ∏_{y:y_{1}+···+y_{h}=x_{i},|u|_{d}=k}(1 − p_{n}^{k})
= (1 + o(1)) ∏_{i=1}^{r} ∏_{k=1}^{h−1} ((1 − p_{n}^{k})^{O_{h}(n^{k−1})}) (1 − p_{n}^{k})^{^{\frac{n^{h−1}}{h!}} (1+O_{h}(\frac{1}{n}))}
= (1 + o(1)) ∏_{i=1}^{r} [(exp \{−O_{h} (\frac{1}{n}) ∑_{1≤k≤h−1}(p_{n}n)^{k}\})

×( exp \{−\frac{(p_{n}n)^{h}}{h!} (1 + O_{h}(p_{n}^{h})) (\frac{1}{n} + O_{h} (\frac{1}{n^{2}} ))\})]

= (1 + o(1)) (exp \{−r\frac{h!n log n(1 + \frac{c}{log n})(1 + O_{h,c}(\frac{1}{log^{2} n}))}{h!} \frac{1}{n}\})
= (1 + o(1))\frac{exp (−cr)}{n^{r}}.

Therefore,

∑_{\{x_{1},...,x_{r}\},x_{i}∈ℤ_{n}x_{i}≠x_{j}} Pr\{C_{x_{1}} ∩ ⋯ ∩ C_{x_{r}}\} = (1 + o(1))\binom{n}{r}\frac{exp (−cr)}{n^{r}} = (1 + o(1))\frac{exp (−cr)}{r!}.

Let u = {u_{1}, …, u_{h}} with u_{1} + ⋯ + u_{h} = x_{i} and v = {v_{1}, …, v_{h}} with v_{1} + ⋯ + v_{h} = x_{j}.

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 7 (2007), #A32 10

In order to finish the proof, we separate Δ as

Δ = ∑_{1≤i,j≤r} ∑_{{u,x_{i}},{v,x_{j}}:|u∩v|_{d}>0} Pr{B_{u,x_{i}} ∩ B_{v,x_{j}}}
= ∑_{1≤i,j≤r} ∑_{s=2}^{h−1} ∑_{{u,x_{i}},{v,x_{j}}:|u|_{d}=s,|v|_{d}=s,|u∩v|_{d}=s} p_{n}^{s}

+ ∑_{1≤i,j≤r} ∑_{s=2}^{h} ∑_{k=1}^{s−1} ∑_{{u,x_{i}},{v,x_{j}}:|u|_{d}=s,|v|_{d}=s,|u∩v|_{d}=k} p_{n}^{2s−k}

+ ∑_{1≤i,j≤r} ∑_{s=1}^{h−1} ∑_{t=s+1}^{h} ∑_{k=1}^{s} ∑_{{u,x_{i}},{v,x_{j}}:|u|_{d}=s,|v|_{d}=t,|u∩{v_{1}...,v_{r}}|_{d}=k} p_{n}^{s+t−k}

= ∑_{1} + ∑_{2} + ∑_{3},

where, by Lemma 1.6.3,

∑_{1} ≤ r^{2} ∑_{s=2}^{h−1} p_{n}^{s}O_{h}(n^{s−2}) = O_{h,r} (\frac{1}{n^{2}} ∑_{s=2}^{h−1}(p_{n}n)^{s}) = o(1),

by Lemma 1.6.2,

∑_{2} ≤ r^{2} ∑_{s=2}^{h} ∑_{k=1}^{s−1} p_{n}^{2s−k}O_{h}(n^{2s−k−2}) = O_{h,r} (\frac{1}{n^{2}} ∑_{s=2}^{h} ∑_{k=1}^{s−1}(p_{n}n)^{2s−k}) = o(1),

and, by Lemma 1.6.2,

∑_{3} ≤ r^{2} ∑_{s=1}^{h−1} ∑_{t=s+1}^{h} ∑_{k=1}^{s} p_{n}^{t+s−k}O_{h}(n^{t+s−k}) = O_{h,r} (\frac{1}{n^{2}} ∑_{s=1}^{h−1} ∑_{t=s+1}^{h} ∑_{k=1}^{s}(p_{n}n)^{t+s−k}) = o(1)

which completes the proof.

References

[1] N. Alon, and J. Spencer, The Probabilistic Method, Wiley-Interscience, Series in Discrete Math. and Optimization, 1992.