RADEMACHER CHAOS: TAIL ESTIMATES VS LIMIT THEOREMS

RON BLEI AND SVANTE JANSON

Abstract. We study Rademacher chaos indexed by a sparse set which has a fractional combinatorial dimension. We obtain tail estimates for finite sums and a normal limit theorem as the size tends to infinity. The tails for finite sums may be much larger that the tails of the limit.

1. Introduction and results

A (homogeneous) Rademacher chaos is a random variable of the type

S = ∑_{i_{1}<···<i_{d}} a_{i_{1}···i_{d}}r_{i_{1}} ⋯ r_{i_{d}},  (1.1)

where d ≥ 1, a_{i_{1}···i_{d}} are real or complex numbers and r_{1}, r_{2}, … is a sequence of independent random variables with the symmetric two-point distribution ℙ(r_{i} = 1) = ℙ(r_{i} = −1) = 1/2. (For example, r_{i} could be the classical Rademacher functions [19], defined on [0, 1] (with the usual Lebesgue measure) by r_{i}(x) = 1 − 2b_{i} when x ∈ [0, 1] has the binary expansion 0.b_{1}b_{2} …, but it is often more convenient to let r_{i} be defined on the Cantor group ℤ_{2}^{∞}. For our purposes, the choice of r_{i} does not matter.) Equivalently, S is a linear combination of the Walsh functions of the type r_{i_{1}} ⋯ r_{i_{d}}.

We will consider only finite sums (1.1), so there is no problem of convergence, and all moments of S are finite.

We are interested in two related properties of the random variables S: the tail behaviour, i.e. the size of the probabilities ℙ(|S| > x) for large x, and the size of the L^{q} norms ∥S∥_{q} = (𝔼 |S|^{q})^{1/q} for large q. For convenience, we define S̃ = S/∥S∥_{2}; thus 𝔼 S̃ = 0 and Var S̃ = 𝔼 S̃^{2} = 1.

Bonami’s hypercontractive inequality [4] implies that every S in (1.1) satisfies

∥S∥_{q} ≤ (q − 1)^{d/2}∥S∥_{2} = (q − 1)^{d/2}( ∑_{i_{1}<···<i_{d}} |a_{i_{1}···i_{d}}|^{2})^{1/2},  q ≥ 2, (1.2)

or, equivalently, ∥S̃∥_{q} ≤ (q − 1)^{d/2}, q ≥ 2. (See also [1, 2, 11, 13].)

In general, this estimate is best possible, up to a constant depending on d but not on q. For example, it is easily seen that a_{i_{1}···i_{d}} = 1 for 1 ≤ i_{1} < ⋯ < i_{d} ≤ n (and 0 otherwise) yields an S = S_{n} that after suitable normalization converges, as n → ∞, to a (Hermite) d-degree polynomial in a Gaussian random variable; see Example 3.2. It thus follows that for some c(d) > 0 and every q ≥ 2, ∥S∥_{q} ≥ c(d)(q − 1)^{d/2}∥S∥_{2} provided n is large enough. (See e.g. [11, Chapter XIII].)

Date: May 29, 2002; revised May 26, 2003.

In this paper we study Rademacher chaos (1.1) where most coefficients a_{i_{1}···i_{d}} = 0 so that we really only sum over an indexing set which is combinatorially sparse in the sense of [2, Chapters XII and XIII]. In this case, Bonami’s hypercontractive inequality (1.2) can be improved, precisely reflecting the sparsity of the indexing set.

We first recall some definitions [2, Chapters XIII], which we modify and adapt to our purposes in this paper.

For F ⊆ ℕ^{d} and α > 0, define

Ψ_{F} (s) = max{|F ∩ (A_{1} × ⋯ × A_{d})| : A_{j} ⊂ ℕ, |A_{j}| ≤ s, j = 1, …, m},

and

d_{F} (α) = sup_{s≥1} Ψ_{F} (s)/s^{α} = sup_{A_{1},...,A_{d}} |F ∩ (A_{1} × ⋯ × A_{d})|/(max_{j≤d} |A_{j}|)^{α}.

In [2, §XIII.4], the combinatorial dimension of a set F ⊆ ℕ^{d} is defined to be

dim(F) = lim sup_{s→∞}(log Ψ_{F} (s)/ log s)

= sup{α : d_{F} (α) = ∞} = inf{α : d_{F} (α) < ∞}. (1.3)

In this paper, we consider sequences of index sets F_{N} ⊆ [N]^{d}, where [N] = {1, …, N}, and we adopt the definition below. Because we want to consider only non-empty index sets, we consider sequences starting at some index N_{0} ≥ 1; this allows for some empty F_{N} for smaller N that we ignore.

Definition. A sequence F_{N} ⊆ [N]^{d}, N = N_{0}, N_{0} + 1, …, has combinatorial dimension α if there exist positive constants C_{1}, C_{2} such that for all N ≥ N_{0},

d_{F_{N}} (α) ≤ C_{1},

(i.e. |F_{N} ∩ (A_{1} × ⋯ × A_{d})| ≤ C_{1}(max_{j≤d} |A_{j}|)^{α}), and

|F_{N}| ≥ C_{2}N^{α}.

We write dim{F_{N}} = α.

Given a set F ⊆ ℕ^{d}, we define F_{N} = F ∩ [N]^{d}. In the present paper, we define dim(F) = dim{F_{N}} when the latter exists (and leave the dimension undefined otherwise).

Remark 1.1. Note that this is a stricter definition than (1.3); there are sets F with no dimension in the present sense, but it is easily seen that when the dimension exists in the present sense, it coincides with (1.3).

If the cardinalities of F_{N} are uniformly bounded, then dim{F_{N}} = 0; otherwise 1 ≤ dim{F_{N}} ≤ d (if dim{F_{N}} exists at all). We are mainly interested in the case 1 < dim{F_{N}} < d.

Let Δ^{d} = {(i_{1}, …, i_{d}) : 1 ≤ i_{1} < ⋯ < i_{d} < ∞} and Δ_{N}^{d} = Δ^{d} ∩ [N]^{d}. We will in the sequel consider only F ⊆ Δ^{d} and F_{N} ⊆ Δ_{N}^{d}; This is not essential, but restriction to ordered sets of indices is convenient when we study sums (1.6).

It is proved in [2, Chapter XIII] that for every α ∈ [1, d], there exist sets F ⊂ Δ^{d} of combinatorial dimension α (also in the stricter sense used here). Such sets can always be constructed by a random procedure; for rational α ≥ 1 and d such that dα is an integer, it is also possible to use the following deterministic construction.

Example 1.2. (Minimal fractional Cartesian products [2, §XIII.1 and p. 493].) Fix arbitrary integers d ≥ 3 and 1 ≤ m ≤ d, and let {S_{1}, …, S_{d}} be a cover of [d] consisting of m-subsets of [d], such that every i ∈ [d] appears in exactly m elements of S_{1}, …, S_{d}; i.e., ⋃_{j=1}^{d} S_{j} = [d], |S_{j}| = m, and for every i ∈ [d], |{j : i ∈ S_{j}}| = m.

We employ the following notation: if X is a set, y = (y_{1}, …, y_{d}) ∈ X^{d} and S ⊆ [d], then

π_{S}y = (y_{i} : i ∈ S).

For an integer N ≥ d^{m}, let n be the greatest integer such that n ≤ N^{1/m}. Fix a one-one map φ from [n]^{m} into [N], and consider

F_{N}^{∗} = {(φ(π_{S_{1}}k), …, φ(π_{S_{d}}k)) : k ∈ [n]^{d}}.  (1.4)

In order to obtain a subset of Δ_{N}^{d}, for the purposes of this paper, we modify this set to

F_{N} = {(i_{1}, …, i_{d}) ∈ Δ_{N}^{d} : (i_{ρ1}, …, i_{ρd}) ∈ F_{N}^{∗} for some permutation ρ}.

(1.5)

We call the sequence {F_{N}} a fractional Cartesian product.

We further say the the fractional Cartesian product is disconnected if [d] can be partitioned into two disjoint nonempty subsets T_{1} and T_{2} such that each S_{j} is a subset of either T_{1} or T_{2}, and connected otherwise.

The archetypal case is d = 3, m = 2, S_{1} = {1, 2}, S_{2} = {1, 3} and S_{3} = {2, 3}. This gives a connected fractional Cartesian product.

Claim. dim{F_{N}} = dim{F_{N}^{∗}} = d/m.

We verify the claim in the archetypal case d = 3, m = 2 only. The general case is similar; see [2, Corollary XIII.16].

Let 1 ≤ s ≤ N be an integer, and let A, B, C be arbitrary subsets of [N]. Then,

|F_{N}^{∗} ∩ (A × B × C)| = ∑_{k_{1},k_{2},k_{3}∈[n]} 1_{A}(φ(k_{1}, k_{2}))1_{B}(φ(k_{1}, k_{3}))1_{C}(φ(k_{2}, k_{3})).

A three-fold application of the Cauchy–Schwarz inequality yields

|F_{N}^{∗} ∩ (A × B × C)| ≤ ( ∑_{k_{1},k_{2}∈[n]} 1_{A}(φ(k_{1}, k_{2})))^{1/2}( ∑_{k_{1},k_{3}∈[n]} 1_{B}(φ(k_{1}, k_{3})))^{1/2}

· ( ∑_{k_{2},k_{3}∈[n]} 1_{C}(φ(k_{2}, k_{3})))^{1/2}

≤ |A|^{1/2}|B|^{1/2}|C|^{1/2},

which implies Ψ_{F_{N}^{∗}} (s) ≤ s^{3/2} and thus Ψ_{F_{N}} (s) ≤ 6s^{3/2}. In the opposite direction,

|F_{N}| ≥ |Δ_{n}^{3}| = \binom{n}{3} ≥ c_{1}n^{3} ≥ c_{2}N^{3/2}.

Remark 1.3. Again, the definition differs slightly from [2]; there the fractional Cartesian product is defined on an infinite set (n = ∞ in (1.4)).

Remark 1.4. Note that the function φ appears in the definition of a fractional Cartesian product, only because we let the indices be integers in this paper. We might avoid φ by changing the notation slightly; for example, for the case d = 3, m = 2, we could equivalently write (1.9) below as S_{N} = ∑_{i<j<k≤n} r_{ij}r_{ik}r_{jk}, where r_{ij}, i < j are independent Rademacher variables.

It is shown in [2] (e.g., Corollary XIII.29, see Remark 1.9 below) that if F ⊆ Δ^{d} (finite or infinite), and S is a Rademacher chaos

S = ∑_{(i_{1},...,i_{d})∈F} a_{i_{1}···i_{d}}r_{i_{1}} ⋯ r_{i_{d}},  (1.6)

then

∥S∥_{q} ≤ Kd_{F} (α)^{1/2}q^{α/2}∥S∥_{2}, q ≥ 1, (1.7)

where K < ∞ depends only on the ambient dimension d. In particular, if dim{F_{N}} < d, the exponent in (1.2) can be improved, with d replaced by the combinatorial dimension.

These norm estimates lead to tail estimates by the customary procedure: If (1.7) holds and d_{F} (α) < ∞, then for any x > 0 and q ≥ 1, by Markov’s inequality,

ℙ(|S̃| ≥ x) ≤ x^{−q} 𝔼 |S̃|^{q} = x^{−q}∥S̃∥_{q}^{q} ≤ (x^{−1}Cq^{α/2})^{q},

where C = Kd_{F} (α)^{1/2}. Taking q = (x/C)^{2/α}e^{−1} (if x ≥ Ce^{α/2}), we obtain

ℙ(|S̃| ≥ x) ≤ e^{−αq/2} = exp(−cx^{2/α}),  (1.8)

for a constant c > 0 depending on d, α and d_{F} (α) only.

The norm and tail estimates above are in fact sharp, in a sense made precise below. (Cf. [2, Corollary XIII.29].) For simplicity, we will consider only the case where a_{i_{1}···i_{d}} = 1 or 0. Specifically, we consider a sequence of non-empty sets F_{N} ⊆ Δ_{N}^{d} and Rademacher chaos

S_{N} = ∑_{(i_{1},...,i_{d})∈F_{N}} r_{i_{1}} ⋯ r_{i_{d}}.  (1.9)

Clearly, ∥S_{N}∥_{2} = |F_{N}|^{1/2}, and thus S̃_{N} = |F_{N}|^{−1/2}S_{N}.

Theorem 1.5. Suppose dim{F_{N}} = α ≥ 1, where F_{N} ⊆ Δ_{N}^{d}. Let S_{N} be given by (1.9). Then there exist positive constants c_{1}, c_{2}, c_{3}, c_{4} (depending only on d, α, C_{1}, C_{2}, N_{0} above) such that for every q ≥ 1,

c_{1}q^{α/2} ≤ sup_{N} ∥S̃_{N}∥_{q} ≤ c_{2}q^{α/2},  (1.10)

and for all x ≥ 2,

exp(−c_{3}x^{2/α}) ≤ sup_{N} ℙ(|S̃_{N}| > x) ≤ exp(−c_{4}x^{2/α}).  (1.11)

A natural question arises: can sup_{N} in (1.10) and (1.11) be replaced by lim_{N→∞}? (See Remark ii in [2, p.524].) In the standard integer-dimensional case F_{N} = Δ^{d}, the answer is affirmative (by a d-fold application of the usual Central Limit theorem). But in many fractional-dimensional cases, the answer is negative: the precise relation between tail estimates and combinatorial dimension, as per (1.11), is completely wiped out in the limit. We illustrate this in two important cases.

Theorem 1.6. Let F_{N} ⊆ Δ_{N}^{d}, N = 1, …, and let S_{N} be given by (1.9). Suppose either (i) d = 2 and 1 < dim{F_{N}} < 2, or (ii) F_{N} is a connected fractional Cartesian product as in Example 1.2. Then S̃_{N} →^{d} N(0, 1) with convergence of all moments. In particular, if ξ ∼ N(0, 1), then, for all q ≥ 1,

lim_{N→∞} ∥S̃_{N}∥_{q} = ∥ξ∥_{q} ≤ q^{1/2}

and for all x ≥ 2,

lim_{N→∞} ℙ(|S̃_{N}| > x) = ℙ(|ξ| > x) ≤ exp(−x^{2}/2).

Case (ii) with m = 2 can be translated (using Remark 1.4) into a result for random graphs, which is a special case (with p = 1/2) of [9, Theorem 1]; see also [10] and [11, Chapter XI].

Theorems 1.5 and 1.6 complement one another in the following (heuristic) sense. Let us agree that tail probabilities of sums of uncorrelated symmetric variables provide a gauge of interdependence between the variables: larger tail probabilities (smaller likelihood of cancellations) convey higher degree of interdependence, and conversely. In this light, Theorem 1.5 provides a precise assessment of interdependence of the random variables r_{i_{1}} ⋯ r_{i_{d}}, (i_{1}, …, i_{d}) ∈ F_{N}. As a counterpoint, reflecting increasing sparsity of F_{N} relative to the full product set Δ_{N}^{d}, Theorem 1.6 asserts that F_{N} in the limit, as N → ∞, is asymptotically independent.

Theorems 1.5 and 1.6 show that, for large q or x, the limits as N → ∞ are much smaller than the largest values for finite N. If we fix a large q and study ∥S̃_{N}∥_{q} as N grows, we begin with rather small values (at most |F_{N}|^{1/2}) that grow to a maximum of the order q^{α/2} (when N is about q, see Section 2), but then the norms decrease again towards a limit of the order q^{1/2}. (We do not know whether the increase and decrease are monotone; there might be several local maxima.) A similar story holds for ℙ(|S̃_{N}| > x) for a fixed large x. Consequently, the limit results in Theorem 1.6 are misleading when we consider S̃_{N} for finite N.

A central limit theorem in fact holds generally under a condition of sparsity in F_{N} that is milder than the sparsity implied by non-integer combinatorial dimension. The condition is in effect that F_{N} is not “too close” to a product set. To express this precisely we use the following terminology. For j ∈ [N], define

F_{Nj}^{∗} = {(i_{1}, …, i_{d}) ∈ F_{N} : j ∈ {i_{1}, …, i_{d}}}.

Further, let F_{N}^{#} be the subset of F_{N} × F_{N} defined as follows: a pair of dtuples ((i_{1}, …, i_{d}), (j_{1}, …, j_{d})) ∈ F_{N}^{#} if {i_{1}, …, i_{d}}∩{j_{1}, …, j_{d}} = ∅ and there exist (k_{1}, …, k_{d}) ∈ F_{N}, (l_{1}, …, l_{d}) ∈ F_{N} such that {k_{1}, …, k_{d}, l_{1}, …, l_{d}} = {i_{1}, …, i_{d}, j_{1}, …, j_{d}} but (k_{1}, …, k_{d}) does not equal (i_{1}, …, i_{d}) or (j_{1}, …, j_{d}). (In other words, the 2d indices i_{1}, …, i_{d}, j_{1}, …, j_{d} can be partitioned in at least two ways into elements of F_{N}.)

Theorem 1.7. Suppose

lim_{N→∞} max_{j} |F_{Nj}^{∗}|/|F_{N}| = 0  (1.12)

and

lim_{N→∞}(|F_{N}^{#}|/|F_{N}|^{2}) = 0.  (1.13)

Then S̃_{N} →^{d} N(0, 1), with convergence of all moments.

We have the following partial converse. (The trivial example F = {(1, j) : j ≥ 2} shows that (1.12) is not necessary; we do not know whether it is needed at all in Theorem 1.7.)

Theorem 1.8. Suppose that S̃_{N} →^{d} N(μ, σ^{2}) for some μ and σ^{2} > 0. Then μ = 0, σ^{2} = 1 and (1.13) holds.

The proof of Theorem 1.5 is given in Section 2, and the proofs of Theorems 1.6, 1.7, 1.8 are given in Section 3. Some simple examples of nonnormal limits when (1.13) is not satisfied are given also in Section 3. Further remarks and open problems are presented in Section 4.

Remark 1.9. The results in the present paper use Corollary XIII.29 in [2]. A correction to an argument in the proof of that theorem is included in the preprint version of the present paper [3]. The referee has pointed out that (1.7) also follows from [2, Corollary XIII.28] together with the decoupling inequality, see e.g. [6, Theorem 3.1.1].

2. Proof of Theorem 1.5

The upper bounds follow by (1.7) and (1.8) (for x ≥ x_{0}, say; the case 2 ≤ x ≤ x_{0} follows by Chebyshev’s inequality if c_{4} is small enough).

To verify the lower bounds, let E_{N} be the event r_{1} = ⋯ = r_{N} = 1; thus ℙ(E_{N}) = 2^{−N}. On E_{N}, we have S_{N} = |F_{N}| and thus S̃_{N} = |F_{N}|^{1/2}. Hence, for every q ≥ 1,

∥S̃_{N}∥_{q} ≥ |F_{N}|^{1/2} ℙ(E_{N})^{1/q} ≥ cN^{α/2}2^{−N/q}.

To verify the left inequality in (1.10), in the line above choose N = max(N_{0}, ⌊q⌋).

Similarly, given x (large enough), let N = ⌈Cx^{2/α}⌉ for a constant C > C_{2}^{−1/α}, where C_{2} is as in the definition above. Then, on E_{N}

S̃_{N} = |F_{N}|^{1/2} ≥ C_{2}^{1/2}N^{α/2} > x,

and thus

ℙ(S̃_{N} > x) ≥ ℙ(E_{N}) = 2^{−N} ≥ exp(−c_{3}x^{2/α}).  □

3. Asymptotic normality

Lemma 3.1. If d = 2, then for any α and any finite subsets A and B of ℕ such that |A| ≤ |B|,

|F ∩ (A × B)| ≤ 2d_{F} (α)|A|^{α−1}|B|,
|F ∩ (B × A)| ≤ 2d_{F} (α)|A|^{α−1}|B|.

Proof. We may assume |A| ≥ 1. Partition B into ⌈|B|/|A|⌉ ≤ 2|B|/|A| subsets B_{j} with |B_{j}| ≤ |A|. For each j, |F ∩ (A × B_{j})| ≤ Ψ_{F} (|A|) ≤ d_{F} (α)|A|^{α}, and similarly for |F ∩ (B_{j} × A)|. The result follows by summing over j. □

Proof of Theorem 1.6. We verify the conditions of Theorem 1.7. Let α = dim{F_{N}}.

First consider case (i), i.e., suppose that d = 2 and 1 < α < 2. Then, |F_{Nj}^{∗}| ≤ N = o(|F_{N}|), which verifies (1.12).

Next, choose ε_{N} > 0 such that ε_{N} → 0 and Nε_{N}^{1/(2−α)} → ∞. (For example, ε_{N} = N^{−δ} for 0 < δ < 2 − α.) Let A = A_{N} = {i : |F_{Ni}^{∗}| ≥ ε_{N}N}. Then,

|F_{N} ∩ (A × [N])| + |F_{N} ∩ ([N] × A)| = ∑_{i∈A} |F_{Ni}^{∗}| ≥ ε_{N}N|A|,

and thus, by Lemma 3.1

ε_{N}N|A| ≤ 4d_{F_{N}} (α)|A|^{α−1}N,

which implies

|A| ≤ (4d_{F_{N}} (α)/ε_{N})^{1/(2−α)} = o(N).  (3.1)

By definition, F_{N}^{#} is the set of all ((i, j), (k, l)) ∈ F_{N} ×F_{N}, all of which entries are distinct, such that either ({i, k}, {j, l}) ∈ F_{N} × F_{N} or ({i, l}, {j, k}) ∈ F_{N} × F_{N} (or both), where {i, k} = (i, k) when i < k and (k, i) when i > k. We let F_{N1}^{#} be the subset of F_{N}^{#} where i ∈ A, and F_{N2}^{#} the subset where i ∉ A.

The number of possible (i, j) ∈ F_{N} with i ∈ A is |F_{N} ∩ (A × [N])|, and thus, by Lemma 3.1 and (3.1),

\begin{aligned}|F_{N1}^{#}| ≤ |F_{N} ∩ (A × [N])| · |F_{N}| & ≤ 2d_{F_{N}} (α)|A|^{α−1}N|F_{N}| \\ & = o(N^{α}|F_{N}|) = o(|F_{N}|^{2}). \end{aligned}  (3.2)

On the other hand, let F_{Ni}^{∗∗} = {k : (i, k) ∈ F_{Ni}^{∗} or (k, i) ∈ F_{Ni}^{∗}}. Thus |F_{Ni}^{∗∗}| = |F_{Ni}^{∗}|. If ((i, j), (k, l)) ∈ F_{N}^{#}, then either k or l is in F_{Ni}^{∗∗}, and thus the number of possible (k, l) ∈ F_{N} for a given i ∉ A is at most, again by Lemma 3.1,

|F_{N} ∩ (F_{Ni}^{∗∗} × [N])| + |F_{N} ∩ ([N] × F_{Ni}^{∗∗})| ≤ 4d_{F} (α)|F_{Ni}^{∗∗}|^{α−1}N ≤ 4d_{F} (α)ε_{N}^{α−1}N^{α}.

Summing over all possible (i, j) we find

|F_{N2}^{#}| ≤ 4d_{F} (α)ε_{N}^{α−1}N^{α}|F_{N}| = o(|F_{N}|^{2}).  (3.3)

Combining (3.2) and (3.3), we obtain (1.13) and the result follows in this case.

In case (ii), we first observe that fixing an index j in F_{N} means that the corresponding k in (1.4) is such that π_{S_{i}}k = φ^{−1}(j) for some i; for each i this means that m of the d coordinates of k have given values, so the number of choices of k is at most dn^{d−m}. Consequently, |F_{Nj}^{∗}| ≤ dn^{d−m} = o(|F_{N}|), proving (1.12).

Next, suppose that ((i_{1}, …, i_{d}), (j_{1}, …, j_{d})) ∈ F_{N}^{#}, and that (i_{1}, …, i_{d}) and (j_{1}, …, j_{d}) are generated by (1.4) and (1.5) by some vectors i and j in [n]^{d}, respectively. By the definition of F_{N}^{#}, there exists also (k_{1}, …, k_{d}) ∈ F_{N}, generated in the same way by, say, k ∈ [n]^{d}, such that {k_{1}, …, k_{d}} ⊆ {i_{1}, …, i_{d}, j_{1}, …, j_{d}} but (k_{1}, …, k_{d}) does not equal (i_{1}, …, i_{d}) or (j_{1}, …, j_{d}).

Hence, each π_{S_{ν}}k, 1 ≤ ν ≤ d, coincides with some π_{S_{μ}}i or π_{S_{μ}}j, 1 ≤ μ ≤ d. Define

J_{1} = {ν ∈ [d] : π_{S_{ν}}k = π_{S_{μ}}i for some μ};
J_{2} = {ν ∈ [d] : π_{S_{ν}}k = π_{S_{μ}}j for some μ};
T_{s} = ⋃_{ν∈J_{s}} S_{ν},  s = 1, 2.

Then J_{1} ∪ J_{2} = [d] and T_{1} ∩ T_{2} ≠ ∅, because otherwise the fractional Cartesian product would be disconnected.

If q ∈ T_{1}, then q ∈ S_{ν} for some ν ∈ J_{1}, and thus π_{S_{ν}}k = π_{S_{μ}}i for some μ. In particular, the qth coordinate of k is one of the coordinates of i. Similarly, if q ∈ T_{2}, then the qth coordinate of k is one of the coordinates of j.

Because T_{1} ∩ T_{2} ≠ ∅, it follows that i and j have at least one coordinate in common (not necessarily in the same position). Consequently, the number of possible pairs (i, j) is O(n^{2d−1}), and

|F_{N}^{#}| = O(n^{2d−1}) = O(N^{2(d/m)−1}) = o(N^{2α}) = o(|F_{N}|^{2}),

verifying (1.13). □

Proof of Theorem 1.7. All limits in the proof are as N → ∞. We begin by observing that the assumption (1.12) implies

∑_{j=1}^{N} |F_{Nj}^{∗}|^{2} ≤ max_{j} |F_{Nj}^{∗}| ∑_{j=1}^{N} |F_{Nj}^{∗}| ≤ max_{j} |F_{Nj}^{∗}| · d|F_{N}| = o(|F_{N}|^{2}). (3.4)

We use the martingale central limit theorem, as stated in [16, Corollary (2.13)]. We let

F_{Nj} = {(i_{1}, …, i_{d}) ∈ F_{N} : i_{d} = j} ⊆ F_{Nj}^{∗},

and let

X_{Nj} = ∑_{(i_{1},...,i_{d})∈F_{Nj}} r_{i_{1}} ⋯ r_{i_{d}} = r_{j} ∑_{(i_{1},...,i_{d})∈F_{Nj}} r_{i_{1}} ⋯ r_{i_{d−1}}.

Then

S_{N} = ∑_{j=1}^{N} X_{Nj}

and, with X̃_{Nj} = |F_{N}|^{−1/2}X_{Nj},

S̃_{N} = ∑_{j=1}^{N} X̃_{Nj}.

Evidently, (X̃_{Nj})_{j=1}^{N} is a martingale difference sequence for the filtration F_{j} = F(r_{1}, …, r_{j}), and we have 𝔼 S̃_{N}^{2} = ∑ 𝔼 X̃_{Nj}^{2} = 1.

By [16, Corollary (2.13)], to prove S̃_{N} →^{d} N(0, 1) it suffices to verify the Lindeberg condition

∑_{j=1}^{N} 𝔼(X̃_{Nj}^{2}1[|X̃_{Nj}| > ε]) → 0 for every ε > 0,  (3.5)

together with

lim sup_{N→∞} ∑_{i≠j} 𝔼(X̃_{Ni}^{2}X̃_{Nj}^{2}) ≤ 1.  (3.6)

Because every moment of S̃_{N} stays bounded by (1.2), moment convergence will follow as well.

To prove (3.5) it suffices to show

∑_{j=1}^{N} 𝔼 X̃_{Nj}^{4} → 0.  (3.7)

In our case, by (1.2) we note ∥X̃_{Nj}∥_{4} ≤ 3^{d/2}∥X̃_{Nj}∥_{2} and therefore

∑_{j=1}^{N} 𝔼 X̃_{Nj}^{4} ≤ 3^{2d} ∑_{j=1}^{N} ∥X̃_{Nj}∥_{2}^{4} = 3^{2d} ∑_{j=1}^{N} \frac{|F_{Nj}|^{2}}{|F_{N}|^{2}} ≤ 3^{2d}|F_{N}|^{−2} ∑_{j=1}^{N} |F_{Nj}^{∗}|^{2},

which by (3.4) implies (3.7).

It remains to verify (3.6). For simplicity we treat first the case d = 2, and will describe later the modifications needed in the general case. If d = 2, then

𝔼(X_{Ni}^{2}X_{Nj}^{2}) = ∑_{k,l,m,n} 𝔼 1_{F_{N}} (k, i)1_{F_{N}} (l, i)1_{F_{N}} (m, j)1_{F_{N}} (n, j)r_{k}r_{l}r_{m}r_{n}.

We have, 𝔼 r_{k}r_{l}r_{m}r_{n} = 0 unless the indices k, l, m, n coincide in pairs, and obtain (overcounting the case when all four indices coincide)

\begin{aligned}𝔼(X_{Ni}^{2}X_{Nj}^{2}) & ≤ ∑_{k,m} 1_{F_{N}} (k, i)1_{F_{N}} (k, i)1_{F_{N}} (m, j)1_{F_{N}} (m, j) \\ & + 2 ∑_{k,l} 1_{F_{N}} (k, i)1_{F_{N}} (l, i)1_{F_{N}} (k, j)1_{F_{N}} (l, j). \end{aligned}

Summing the first term on the right over all i and j, we obtain |F_{N}|^{2}. Therefore, to show (3.6), it suffices to verify

∑_{i≠j} ∑_{k,l} 1_{F_{N}} (k, i)1_{F_{N}} (l, i)1_{F_{N}} (k, j)1_{F_{N}} (l, j) = o(|F_{N}|^{2}).  (3.8)

The sum above equals the number of pairs ((k, i), (l, j)) ∈ F_{N} × F_{N} such that also ((l, i), (k, j)) ∈ F_{N} × F_{N}. The number of such pairs with distinct i, j, k, l is at most |F_{N}^{#}|. Further, the number of pairs ((k, i), (l, j)) ∈ F_{N} × F_{N} where two indices are equal to some r is at most |F_{Nr}^{∗}|^{2}. Consequently, the sum in (3.8) is at most

|F_{N}^{#}| + ∑_{r=1}^{N} |F_{Nr}^{∗}|^{2},

and (3.8) follows by (1.13) and (3.4).

In the case d ≥ 2, we similarly find that 𝔼 X_{Ni}^{2}X_{Nj}^{2} equals the number of quadruples I_{1}, I_{2}, I_{3}, I_{4} of d-tuples in F_{N} wherein the 4d indices coincide in pairs, and the last index is i in I_{1} and I_{2} and j in I_{3} and I_{4}. We group such quadruples according to the positions of the pairs of coinciding elements (again overcounting in the cases with less than 2d distinct indices, when there are several possibilities of pairing).

To do this precisely, let Î_{k} = {1, …, d}×{k}, k = 1, 2, 3, 4; thus, Î_{1}, Î_{2}, Î_{3}, Î_{4} are four disjoint copies of {1, …, d}. We define a pattern to be a complete matching in Î_{1} ∪ Î_{2} ∪ Î_{3} ∪ Î_{4}, i.e. a partition of the 4d points into 2d pairs, which are regarded as the edges of a graph.

For a pattern π, any assignment of indices in {1, …, N} to the 2d edges defines 4 d-tuples I_{1}, I_{2}, I_{3}, I_{4} in the obvious way. Let T_{N}(π) be the number of quadruples (I_{1}, I_{2}, I_{3}, I_{4}) ∈ F_{N}^{4} generated this way, i.e., the number of all assignments such that I_{1} ∈ F_{N}, I_{2} ∈ F_{N}, I_{3} ∈ F_{N}, I_{4} ∈ F_{N}.

Finally, let Π′ denote the set of all patterns that contain the two edges {(d, 1), (d, 2)} and {(d, 3), (d, 4)}.

In this framework, we then observe

∑_{i,j} 𝔼 X_{Ni}^{2}X_{Nj}^{2} ≤ ∑_{π∈Π′} T_{N}(π).

We classify the patterns in Π′ into three types: a pattern is of type I if all its edges are inside Î_{1} ∪ Î_{2} or Î_{3} ∪ Î_{4}; it is of type II if it is not of type I and there are no edges connecting Î_{2} and Î_{3}, and type III otherwise.

First, consider a pattern π of type I. Since the d-tuples in F_{N} are ordered, it follows that T_{N}(π) = 0 unless π is the pattern with edges {(i, 1), (i, 2)} and {(i, 3), (i, 4)}, i = 1, …, d. In this case, I_{1} = I_{2} and I_{3} = I_{4}, which are arbitrary elements of F_{N}, and thus T_{N}(π) = |F_{N}|^{2}.

Because the set of patterns is finite, it suffices to show that T_{N}(π) = o(|F_{N}|^{2}) for every pattern π of type II or III.

If π is of type II, then I_{1} and I_{4} together determine I_{2} and I_{3}. As in the case d = 2, the number of allowed pairs (I_{1}, I_{4}) with distinct indices is at most |F_{N}^{#}|, and the number of pairs (I_{1}, I_{4}) with at least one common index is at most ∑_{r=1}^{N} |F_{Nr}^{∗}|^{2}. Therefore T_{N}(π) = o(|F_{N}|^{2}) by (1.13) and (3.4).

Finally, suppose that π is of type III. Let Î_{L} = Î_{1} ∪ Î_{2} and Î_{R} = Î_{3} ∪ Î_{4}, and call these the left and right sides of the pattern. We further say that the points (i, k) ∈ Î_{L} and (i, k + 2) ∈ Î_{R} are the mirror images of one another.

Suppose that there are r edges between Î_{L} and Î_{R}; call these r edges crossing, and order them (in some way). Let t_{N}^{L}(k_{1}, …, k_{r}) be the number of ways to assign indices to the edges inside Î_{L} such that, with k_{1}, …, k_{r} assigned to the crossing edges, I_{1}, I_{2} ∈ F_{N}. Similarly, let t_{N}^{R}(k_{1}, …, k_{r}) be the corresponding number of ways to assign indices in Î_{R} such that I_{3}, I_{4} ∈ F_{N}. Then,

T_{N}(π) = ∑_{k_{1},...,k_{r}=1}^{N} t_{N}^{L}(k_{1}, …, k_{r})t_{N}^{R}(k_{1}, …, k_{r}).

Further, let π′ be the pattern obtained by taking the edges inside Î_{L} in π together with their mirror images in Î_{R} and the edges connecting each remaining point to its mirror image. Define π′′ similarly, starting with the edges inside Î_{R} in π. Note that both π′ and π′′ are patterns of type II. Then, by the Cauchy–Schwarz inequality,

T_{N}(π) = ∑_{k_{1},...,k_{r}=1}^{N} t_{N}^{L}(k_{1}, …, k_{r})t_{N}^{R}(k_{1}, …, k_{r})

≤ ( ∑_{k_{1},...,k_{r}=1}^{N} t_{N}^{L}(k_{1}, …, k_{r})^{2})^{1/2}( ∑_{k_{1},...,k_{r}=1}^{N} t_{N}^{R}(k_{1}, …, k_{r})^{2})^{1/2}

= T_{N}(π′)^{1/2}T_{N}(π′′)^{1/2}

= o(|F_{N}|)^{2},

where the final estimate holds because π′ and π′′ are of type II.

This completes the proof of (3.6) and thus of the theorem. □

Proof of Theorem 1.8. If S̃_{N} converges in distribution, then (1.2) implies that all moments converge (as remarked in the proof of Theorem 1.7). In particular, μ = lim 𝔼 S̃_{N} = 0 and σ^{2} = lim 𝔼 S̃_{N}^{2} = 1; further,

𝔼 S̃_{N}^{4} → 𝔼 ξ^{4} = 3.  (3.9)

Similarly, as in the proof above, ES_{N}^{4} equals the number of quadruples (I_{1}, I_{2}, I_{3}, I_{4}) of d-tuples in F_{N} such that the 4d indices in them coincide in pairs. To estimate this number from above, we note that the number of possibilities that I_{1}, I_{2}, I_{3}, I_{4} can coincide in two different pairs is 3|F_{N}|(|F_{N}|−1), and that each element in F_{N}^{#} contributes (at least) one more to the count. Hence,

|F_{N}|^{2} 𝔼 S̃_{N}^{4} = 𝔼 S_{N}^{4} ≥ 3|F_{N}|^{2} − 3|F_{N}| + |F_{N}^{#}|.  (3.10)

Obviously, |F_{N}| → ∞ if S̃_{N} →^{d} N(0, 1). Hence, (3.9) and (3.10) imply (1.13). □

We end this section with some counterexamples where the set F_{N} is close to a product set and asymptotic normality does not hold.

Example 3.2. Take F_{N} = Δ_{N}^{d} with d ≥ 2. It is easily seen that (1.13) does not hold, so asymptotic normality fails by Theorem 1.8. Actually, it is easy to see that in this case, S̃_{N} converges to a Hermite polynomial of degree d in a standard normal variable [20], see also [11, Section XI.1] and [2, Theorem X.26].

In particular, with d = 2, this example shows that Theorem 1.6(i) does not extend to dim{F_{N}} = 2.

Example 3.3. Fix an integer ℓ ≥ 1 and let, for N > ℓ, F_{N} be the product set {1, …, ℓ} × {ℓ + 1, …, N}.

Clearly, S_{N} = ∑_{1}^{ℓ} r_{i} · ∑_{ℓ+1}^{N} r_{j} and it follows from the central limit theorem that

S̃_{N} →^{d} Y ξ,

where Y and ξ are independent, ξ ∼ N(0, 1) and Y = ℓ^{−1/2} ∑_{1}^{ℓ} r_{i}.

Hence, if ℓ = 1, the limit is normal, but not if ℓ ≥ 2. For example, if ℓ = 2, the limit variable is 0 with probability 1/2. (The limit can be regarded as a mixture of normal distributions with different variances.)

In particular, this example shows that Theorem 1.6(i) does not extend to dim{F_{N}} = 1.

Example 3.4. Consider a disconnected fractional Cartesian product. For example, take d = 6, m = 2 and let S_{1}, …, S_{6} be the sets {1, 2}, {1, 3}, {2, 3}, {4, 5}, {4, 6}, {5, 6}. It is easily seen that (1.13) does not hold, so asymptotic normality fails by Theorem 1.8.

This case is related to the case of disconnected G or H, respectively, in [9, Theorem 1] or [10, Theorem 1]. We expect that, as in those results, S̃_{N} converges to a polynomial in normal variables, but we have not checked the details.

4. Further remarks and open problems

Remark 4.1. It would be interesting to know more about ∥S̃_{N}∥_{q} and ℙ(|S̃_{N}| > x) as functions of N. For example, how fast is the transition from the maxima in Theorem 1.5 to the limits in Theorem 1.6 as N grows?

Remark 4.2. We considered for simplicity only a_{i_{1}···i_{d}} = 1 in Theorems 1.5 and 1.6. The upper bounds in (1.7) and (1.8) are given for arbitrary a_{i_{1}···i_{d}}, and, in particular, a_{i_{1}···i_{d}} = ±1, but the proof of the lower bounds uses the fact that all coefficients have the same sign. In general, there will be cancellations among the terms in (1.6), for any values of r_{1}, …, r_{N}, and it seems likely that the lower bounds in Theorem 1.5 do not extend to general a_{i_{1}···i_{d}}. What is the correct result? Give an extension of Theorem 1.5 to arbitrary a_{i_{1}···i_{d}}.

Certainly, the central limit theorems 1.6 and 1.7 extend to sums (1.6) with suitable conditions on a_{i_{1}···i_{d}}, but we have not worked out the details of such extensions.

See also [8] and [17] for some related bounds.

Remark 4.3. Note that if S is given by (1.6) and d_{F} (α) < ∞, then

∥S∥_{∞} ≥ c∥{a_{i_{1}···i_{d}}}∥_{ℓ^{2α/(α+1)}},

where the exponent 2α/(α+1) is the best possible; see [2, Section XIII.7]. This generalizes a result for F = Δ^{d} (i.e. sums (1.1), with α = d) proved by Littlewood [15] for d = 2 and for general d by [5] and [12]. It would be interesting to obtain lower bounds to the probability ℙ(S ≥ c∥{a_{i_{1}···i_{d}}}∥_{ℓ^{2α/(α+1)}}).

Remark 4.4. The proofs above show that the tail estimates in Theorem 1.5 hold for the upper tails ℙ(S̃_{N} > x) too. If d is odd, we obtain the same results for ℙ(S̃_{N} < −x) by symmetry, but if d is even this fails. It seems likely that sup_{N} ℙ(S̃_{N} < −x) is smaller than exp(−cx^{2/α}) for even d, for example for d = 2. How small is it?

We can also replace the Rademacher system by other orthogonal systems. (See e.g. [13, Chapter 6] for a general background.)

Remark 4.5. If we replace the Rademacher variables r_{i} by Steinhaus functions χ_{i}, i.e. independent complex random variables that are uniformly distributed on the unit circle, then Theorem 1.5 still holds.

Indeed, (1.7) is still valid [2, Corollary XIII.29], and thus (1.8) holds by the same proof, so the upper bounds in Theorem 1.5 hold. For the lower bounds, we use the same proof as above, now taking E_{N} = {Re χ_{k} ≥ 1/2, k = 1, …, N}.

For the upper bound in (1.7), we can alternatively introduce a Rademacher system {r_{i}} independent of {χ_{i}}, replace χ_{i} by χ_{i}r_{i}, which has the same distribution, and use the Rademacher version above conditioning on {χ_{i}}. This standard trick works for all i.i.d. sequences of bounded symmetric random variables.

Are the central limit theorems 1.6 and 1.7 true for the Steinhaus system too, now with complex Gaussian limits? (We believe so, but we have not checked the details.)

Remark 4.6. Let us instead consider a Gaussian chaos, obtained by replacing r_{i} by independent Gaussian variables ξ_{i} ∼ N(0, 1).

The hypercontractive inequality (1.2) holds in this case too [18], see also [1, 11, 13], but the combinatorial dimension version (1.7) fails in the Gaussian case, as is seen by taking F to be a set with a single element.

Hence Theorem 1.5 is not true in the Gaussian case. What is true? There is no problem with the lower bounds in Theorem 1.5; the proof in Section 2 works if we take E_{N} = {ξ_{i} > 1, i = 1, …, N}.

We believe that Theorems 1.6 and 1.7 hold for the Gaussian case too, but we have not checked the details.

The estimates in [7] and [14] for d = 2 might be useful.

Remark 4.7. Are the results true if we replace r_{k} by a lacunary sequence exp(2πin_{k}t), where inf n_{k+1}/n_{k} > 1?

Acknowledgement. This research was performed while the authors visited the Mittag-Leffler Institute in Djursholm, Sweden.

References

[1] W. Beckner, Inequalities in Fourier analysis. Ann. Math. 102 (1975), 159–182.

[2] R. Blei, Analysis in Integer and Fractional Dimension. Cambridge Univ. Press, Cambridge, UK, 2001.

[3] R. Blei & S. Janson, Rademacher chaos: tail estimates vs limit theorems. Tech. Report No. 9, 2001/2002, Institut Mittag-Leffler. Available at

http://www.ml.kva.se/preprints/archive2001-2002.php

[4] A. Bonami, Étude des coefficients de Fourier des fonctions de L^{p}(G). Ann. Inst. Fourier (Grenoble) 20 (1970), no. 2, 335–402.

[5] A.M. Davie, Quotient algebras of uniform algebras. J. London Math. Soc. (2) 7 (1973), 31–40.

[6] V.H. de la Peña & E. Giné, Decoupling. From dependence to independence. Springer, New York, 1999.

[7] D.L. Hanson & F.T. Wright, A bound on tail probabilities for quadratic forms in independent random variables. Ann. Math. Statist. 42 (1971), 1079–1083.

[8] P. Hitczenko, Domination inequality for martingale transforms of a Rademacher sequence. Israel J. Math. 84 (1993), no. 1–2, 161–178.

[9] S. Janson, A functional limit theorem for random graphs with applications to subgraph count statistics. Random Struct. Alg. 1 (1990), no. 1, 15–37.

[10] S. Janson Orthogonal Decompositions and Functional Limit Theorems for Random Graph Statistics. Memoirs Amer. Math. Soc. 534, Amer. Math. Soc., Providence, R.I., 1994.

[11] S. Janson, Gaussian Hilbert Spaces, Cambridge Univ. Press, Cambridge, UK, 1997.

[12] G.W. Johnson & G.S. Woodward, On p-Sidon sets. Indiana Univ. Math. J. 24 (1974/75), 161–167.

[13] S. Kwapień & W.A. Woyczyński, Random series and stochastic integrals: single and multiple. Birkhäuser, Boston, MA, 1992.

[14] R. Latała, Tail and moment estimates for some types of chaos. Studia Math. 135 (1999), no. 1, 39–53.

[15] J.E. Littlewood, On bounded bilinear forms in an infinite number of variables. Quart. J. Math. Oxford 1 (1930), 164–174.

[16] D.L. McLeish, Dependent central limit theorems and invariance principles. Ann. Probab. 2 (1974), 620–628.

[17] S.J. Montgomery-Smith, The distribution of Rademacher sums. Proc. Amer. Math. Soc. 109 (1990), no. 2, 517–522.

[18] E. Nelson, The free Markov field. J. Funct. Anal. 12 (1973), 211–227.

[19] H. Rademacher, Einige Sätze über Reihen von allgemeinen Orthogonalfunktionen. Math. Ann. 87 (1922), 112–138.

[20] H. Rubin & R.A. Vitale, Asymptotic distribution of symmetric statistics. Ann. Statist. 8 (1980), no. 1, 165–170.

Department of Mathematics, University of Connecticut, U-9 Storrs, CT 06269, USA

E-mail address: blei@math.uconn.edu

Department of Mathematics, Uppsala University, PO Box 480, SE-751 06 Uppsala, Sweden

E-mail address: svante.janson@math.uu.se
URL: http://www.math.uu.se/~svante