MEASURES OF PSEUDORANDOMNESS FOR FINITE SEQUENCES: TYPICAL VALUES

N. ALON, Y. KOHAYAKAWA, C. MAUDUIT, C. G. MOREIRA, AND V. RÖDL

Abstract. Mauduit and Sárközy introduced and studied certain numerical parameters associated to finite binary sequences E_{N} ∈ {−1, 1}^{N} in order to measure their ‘level of randomness’. Those parameters, the normality measure N (E_{N}), the well-distribution measure W (E_{N}), and the correlation measure C_{k}(E_{N}) of order k, focus on different combinatorial aspects of E_{N}. In their work, amongst others, Mauduit and Sárközy (i) investigated the relationship among those parameters and their minimal possible value, (ii) estimated N (E_{N}), W (E_{N}), and C_{k}(E_{N}) for certain explicitly constructed sequences E_{N} suggested to have a ‘pseudorandom nature’, and (iii) investigated the value of those parameters for genuinely random sequences E_{N}.

In this paper, we continue the work in the direction of (iii) above and determine the order of magnitude of N (E_{N}), W (E_{N}), and C_{k}(E_{N}) for typical E_{N}. We prove that, for most E_{N} ∈ {−1, 1}^{N}, both W (E_{N})

and N (E_{N}) are of order \sqrt{N}, while C_{k}(E_{N}) is of order \sqrt{N log \binom{N}{k}} for any given 2 ≤ k ≤ N/4.

Date: Copy produced on April 12, 2006. 1991 Mathematics Subject Classification. 68R15. Key words and phrases. Random sequences, pseudorandom sequences, finite words,

normality, correlation, well-distribution, discrepancy.

Part of this work was done at IMPA, whose hospitality the authors gratefully acknowledge. This research was partially supported by IM-AGIMB/IMPA. The first author was partially supported by the Israel Science Foundation, by a USA-Israeli BSF grant, by NSF grant CCR-0324906, by the James Wolfensohn fund and by the State of New Jersey. The second author was partially supported by FAPESP and CNPq through a Temático– ProNEx project (Proc. FAPESP 2003/09925–5) and by CNPq (Proc. 306334/2004–6 and 479882/2004–5). The third author was partially supported by the Brazil/France Agreement in Mathematics (Proc. CNPq 60-0014/01-5 and 69-0140/03-7). The fourth author was partially supported by MCT/CNPq through a ProNEx project (Proc. CNPq 662416/1996–1) and by CNPq (Proc. 300647/95–6). The fifth author was partially supported by NSF Grant DMS 0300529. The authors gratefully acknowledge the support of a CNPq/NSF cooperative grant (910064/99–7, 0072064).

Contents

1. Introduction and statement of results  2
1.1. Measures of pseudorandomness for finite binary sequences  2
1.2. Typical values of W (E_{N}), C_{k}(E_{N}), and N (E_{N})  3
1.3. Minimal values of W (E_{N}), C_{k}(E_{N}), and N (E_{N})  5
2. Estimates for W (E_{N}), C_{k}(E_{N}), and N (E_{N}) for random sequences E_{N} 5
2.1. Estimates for the binomial distribution  6
2.2. The well-distribution measure W  8
2.3. The correlation measure C_{k}  11
2.4. The normality measure N  20
3. Small W (E_{N}) and N (E_{N})  23
3.1. The probability of having W (E_{N}) small  23
3.2. The probability of having N (E_{N}) small  33
4. Concluding remarks  40
References  41

1. Introduction and statement of results

1.1. Measures of pseudorandomness for finite binary sequences. In a series of papers, Mauduit and Sárközy studied finite pseudorandom binary sequences E_{N} = (e_{1}, …, e_{N}) ∈ {−1, 1}^{N}. In particular, they investigated in [11] the ‘measures of pseudorandomness’ to be defined shortly. The readers interested in detailed discussions concerning the definitions below and further related literature are referred to [10] and [11].

Let k ∈ ℕ, M ∈ ℕ, X ∈ {−1, 1}^{k}, a ∈ ℤ, b ∈ ℕ, b > 0, and D = (d_{1}, …, d_{k}) ∈ ℕ^{k} with 0 ≤ d_{1} < ⋯ < d_{k} < N be given. Below, we write card S for the cardinality of a set S, and if S is a set of numbers, then we write ∑ S for the sum ∑_{s∈S} s. We let

T (E_{N}, M, X) = card{n: 0 ≤ n < M, n + k ≤ N, and (e_{n+1}, e_{n+2}, …, e_{n+k}) = X}, (1)

U(E_{N}, M, a, b) = ∑{e_{a+jb}: 1 ≤ j ≤ M, 1 ≤ a + jb ≤ N for all j}, (2)

and

V (E_{N}, M, D) = ∑{e_{n+d_{1}}e_{n+d_{2}} … e_{n+d_{k}}: 1 ≤ n ≤ M, n + d_{k} ≤ N}. (3)

In words, T (E_{N}, M, X) is the number of occurrences of the pattern X in E_{N}, counting only those occurrences whose first symbol is among the first M elements of E_{N}. The quantity U(E_{N}, M, a, b) is the ‘discrepancy’ of E_{N} on an M-element arithmetic progression contained in {1, …, N}. Finally, V (E_{N}, M, D) is the ‘correlation’ among k length M segments of E_{N} ‘relatively positioned’ according to D = (d_{1}, …, d_{k}).

The normality measure of E_{N} is defined as

N (E_{N}) = max_{k} max_{X} max_{M} |T (E_{N}, M, X) − \frac{M}{2^{k}} | ,  (4)

where the maxima are taken over all k ≤ log_{2} N, X ∈ {−1, 1}^{k}, and 0 < M ≤ N + 1 − k. The well-distribution measure of E_{N} is defined as

W (E_{N}) = max{|U(E_{N}, M, a, b)|: a, b, and M such that 1 ≤ a + b < a + Mb ≤ N}. (5)

Finally, the correlation measure of order k of E_{N} is defined as

C_{k}(E_{N}) = max{|V (E_{N}, M, D)|: M and D such that M + d_{k} ≤ N}. (6)

1.2. Typical values of W (E_{N}), C_{k}(E_{N}), and N (E_{N}). In [4], Cassaigne, Mauduit, and Sárközy studied, amongst others, the values of W (E_{N}) and C_{k}(E_{N}) for random binary sequences E_{N}, with all the 2^{N} sequences in {−1, 1}^{N} equiprobable, and the minimum possible values for W (E_{N}) and C_{k}(E_{N}). They proved the following theorems. (Below and elsewhere in this paper, we write log for the natural logarithm.) Theorem A. For all ε > 0, there are numbers N_{0} = N_{0}(ε) and δ = δ(ε) > 0 such that for N ≥ N_{0} we have

δ\sqrt{N} < W (E_{N}) < 6\sqrt{N log N}  (7)

with probability at least 1 − ε. Theorem B. For every integer k ≥ 2 and real ε > 0, there are numbers N_{0} = N_{0}(ε, k) and δ = δ(ε, k) > 0 such that for all N ≥ N_{0} we have

δ\sqrt{N} < C_{k}(E_{N}) < 5\sqrt{kN log N}  (8)

with probability at least 1 − ε.

As it turns out, an improvement of the upper bound in Theorem A may be deduced from a proof of a closely related result of Erdős and Spencer. Indeed, an argument in [7, Chapter 8] tells us that one may drop the logarithmic factor in (7), at the expense of increasing the multiplicative constant.

In this paper, we give stronger versions of Theorems A and B.

Theorem 1. For any given ε > 0 there exist N_{0} and δ > 0 such that if N ≥ N_{0}, then

δ\sqrt{N} < W (E_{N}) < \frac{1}{δ}\sqrt{N}  (9)

with probability at least 1 − ε.

Theorem 1 above is essentially proved in Erdős and Spencer [7, Chapter 8]. However, we give our alternative proof for this result because an idea in this proof is also used in the proofs of Theorems 4, 5, and 6 below.

We next state a result that establishes the typical order of magnitude of C_{k}(E_{N}) for a wide range of k, including values of k proportional to N.

Theorem 2. Let 0 < ε_{0} ≤ 1/16 be fixed and let ε_{1} = ε_{1}(N) = (log log N)/ log N. There is a constant N_{0} = N_{0}(ε_{0}) such that if N ≥ N_{0}, then, with probability at least 1 − ε_{0}, we have

\frac{2}{5}\sqrt{N log \binom{N}{k}} < C_{k}(E_{N}) < \sqrt{(2 + ε_{1})N log (N\binom{N}{k})}

< \sqrt{(3 + ε_{0})N log \binom{N}{k}} < \frac{7}{4}\sqrt{N log \binom{N}{k}} (10)

for every integer k with 2 ≤ k ≤ N/4.

Our next result tells us that C_{k}(E_{N}) is concentrated around its mean 𝔼(C_{k}) in the case in which k is small.

Theorem 3. For any fixed constant ε > 0 and any integer function k = k(N) with 2 ≤ k ≤ log N − log log N, there is a constant N_{0} for which the following holds. If N ≥ N_{0}, then the probability that

1 − ε < \frac{C_{k}(E_{N})}{𝔼(C_{k})} < 1 + ε  (11)

holds is at least 1 − ε.

We suspect that the upper bound on k in Theorem 3 may be weakened. We now turn to the normality measure N (E_{N}).

Theorem 4. For any given ε > 0 there exist N_{0} and δ > 0 such that if N ≥ N_{0}, then

δ\sqrt{N} < N (E_{N}) < \frac{1}{δ}\sqrt{N}  (12)

with probability at least 1 − ε.

We shall show that the lower bounds in Theorems 1 and 4 (i.e., the lower bounds in (9) and (12)) are in a sense best possible. In Section 3 we prove the following two results.

Theorem 5. For any δ > 0, there is c(δ) > 0 and N_{0} = N_{0}(δ) such that, for any N ≥ N_{0}, we have

ℙ(W (E_{N}) < δ\sqrt{N}) > c(δ).  (13)

Theorem 6. For any δ > 0, there is c(δ) > 0 and N_{0} = N_{0}(δ) such that, for any N ≥ N_{0}, we have

ℙ(N (E_{N}) < δ\sqrt{N}) > c(δ).  (14)

In Section 4, we make some simple remarks to show that the upper bounds in (9) and (12) are in a sense best possible. Those remarks and Theorems 5 and 6 tells us that W (E_{N})/\sqrt{N} and N (E_{N})/\sqrt{N} do not converge in distribution as N → ∞ to a distribution that is concentrated at a point.

1.3. Minimal values of W (E_{N}), C_{k}(E_{N}), and N (E_{N}). The minimal possible values of W (E_{N}), C_{k}(E_{N}), and N (E_{N}) have also been investigated in the literature, see, e.g., [1, 4, 9, 15]. We include this brief section for the convenience of the reader. It follows from the classical results of Roth [15] and Matoušek and Spencer [9] that the order of magnitude of

min {W (E_{N}): E_{N} ∈ {−1, 1}^{N}}  (15)

is N^{1/4}. For any fixed even k ≥ 2, the order of magnitude of min_{E_{N}} C_{k}(E_{N}), where the minimum is again taken over all E_{N} ∈ {−1, 1}^{N}, has been established up to a polylogarithmic factor recently:

\sqrt{\frac{1}{2}⌊\frac{N}{k + 1}⌋} < min_{E_{N}} C_{k}(E_{N}) ≤ \frac{7}{4}\sqrt{kN log N},  (16)

where we suppose N ≥ N_{0}(k) for the upper bound. The lower bound in (16) is proved in [1], whereas the upper bound in (16) follows from Theorem 2 above. It is easy to see that, for any odd k, we have min_{E_{N}} C_{k}(E_{N}) = 1. Some further results giving lower bounds for C_{k}(E_{N}) are given in [1].

Turning to the normality measure N (E_{N}), we mention that the best bounds that we know of for the minimal value of N (E_{N}) (E_{N} ∈ {−1, 1}^{N}) are as follows:

(\frac{1}{2} + o(1)) log_{2} N ≤ min_{E_{N}} N (E_{N}) ≤ 3N^{1/3}(log N)^{2/3}  (17)

for all large enough N. The upper bound in (17) is proved in [1] constructively, where a suitable, explicit algebraic construction based on finite fields is given. It is interesting to compare the upper bounds in (17) and (12) in Theorem 4. The lower bound in (17) may be proved simply (see the remarks at the end of Section 2.4). It would be interesting to close the rather wide gap in (17). The following problem was already raised in [1].

Problem 7. Is there an absolute constant α > 0 for which we have

min_{E_{N}} N (E_{N}) > N^{α}  (18)

for all large enough N?

The authors believe that the answer to Problem 7 is positive.

2. Estimates for W (E_{N}), C_{k}(E_{N}), and N (E_{N}) for random

sequences E_{N}

We shall prove Theorems 1–4 in this section. Recall that these results concern random elements E_{N} from the uniform space {−1, 1}^{N}. In this section, unless stated otherwise, E_{N} will always stand for such a random sequence.

2.1. Estimates for the binomial distribution. We give in this section some standard facts about the binomial distribution.

We start with the following form of the de Moivre–Laplace theorem (see, e.g., [3, Chapter I, Theorem 6]). Let Bi(n, p) denote the binomial distribution with parameters n and p. Moreover, write S(n, p) for the sum of n independent Bernoulli random variables with mean p. We first consider the symmetric case p = 1/2.

Fact 8. (i) For any ℓ = ℓ(n) ∈ ℤ with ℓ = o(n^{2/3}), we have

ℙ (S(n, 1/2) = ⌊\frac{n}{2}⌋ + ℓ) = \frac{1}{2^{n}} \binom{n}{⌊n/2⌋ + ℓ}

= \sqrt{\frac{2}{πn}} e^{−2ℓ^{2}/n}(1 + o(1)), (19)

(ii) For any c = c(n) > 0 with c = o(n^{1/6}), we have

ℙ (S(n, 1/2) ≥ ⌊\frac{n}{2}⌋ + c\sqrt{n}) = ∑_{ℓ≥c\sqrt{n}} \frac{1}{2^{n}} \binom{n}{⌊n/2⌋ + ℓ}

= (\sqrt{\frac{2}{π}} + o(1)) (∫_{c}^{∞} e^{−2x^{2}}dx) . (20)

In particular, if we further have that c → ∞, then

ℙ (S(n, 1/2) ≥ ⌊\frac{n}{2}⌋ + c\sqrt{n}) = \frac{e^{−2c^{2}}}{2c\sqrt{2π}} (1 + o(1)).  (21)

(iii) The estimates (20) and (21) hold for the lower tail

ℙ (S(n, 1/2) ≤ ⌊\frac{n}{2}⌋ − c\sqrt{n})

as well.

In what follows, we shall often be concerned with sums of ±1 independent random variables. We let

S^{±}(n) = ∑_{1≤i≤n} X_{i}  (22)

where X_{i} (1 ≤ i ≤ n) are independent random variables with mean 0, that is,

ℙ(X_{i} = −1) = ℙ(X_{i} = +1) = 1/2.

Clearly, (S^{±}(n) + n)/2 is binomially distributed with parameters n and 1/2. Let us now state a well known estimate for large deviations of S^{±}(n) (see, e.g., [2, Appendix A]).

Fact 9. Let X_{i} (1 ≤ i ≤ n) be independent ±1 random variables with mean 0. Let S^{±}(n) = ∑_{1≤i≤n} X_{i}. For any real number a > 0, we have

ℙ(S^{±}(n) > a) < e^{−a^{2}/2n}.  (23)

We now prove a lower estimate for the symmetric binomial distribution. As usual, we let {x} = x − ⌊x⌋.

Fact 10. Let n and ℓ be integers with

− ⌊\frac{n}{2}⌋ ≤ ℓ ≤ ⌈\frac{n}{2}⌉ .  (24)

If n is sufficiently large, then

ℙ (S(n, 1/2) = ⌊\frac{n}{2}⌋ + ℓ) = \frac{1}{2^{n}} \binom{n}{⌊n/2⌋ + ℓ}

≥ 2^{−4(ℓ+\{n/2\})^{2}/n−n}\binom{n}{⌊n/2⌋} = (1 + o(1))2^{−4(ℓ+\{n/2\})^{2}/n}\sqrt{\frac{2}{πn}}. (25)

Proof. We shall in fact prove the following statement, which implies Fact 10: (†) if 0 ≤ ℓ ≤ n/2 and n is large enough, then

\binom{n}{⌊n/2⌋ − ℓ} ≥ 2^{−4(ℓ+\{n/2\})^{2}/n}\binom{n}{⌊n/2⌋}.  (26)

We remark that if n is even, or else if n is odd and ℓ ≤ 0, then (†) is equivalent to what is claimed in Fact 10. If n is odd and ℓ > 0, then (†) is slightly stronger, because in this case we have

\binom{n}{⌊n/2⌋ + ℓ} = \binom{n}{⌈n/2⌉ − ℓ} = \binom{n}{⌊n/2⌋ − ℓ + 1}

≥ 2^{−4(ℓ−1+\{n/2\})^{2}/n}\binom{n}{⌊n/2⌋} ≥ 2^{−4(ℓ+\{n/2\})^{2}/n}\binom{n}{⌊n/2⌋}, (27)

where we used (26) in the first inequality in (27).

We shall now prove (†). Let

a(ℓ) = 2^{4(ℓ+\{n/2\})^{2}/n}\binom{n}{⌊n/2⌋ − ℓ}  (28)

for all 0 ≤ ℓ ≤ n/2. It is easy to check that

a(0), a(⌊n/2⌋) ≥ \binom{n}{⌊n/2⌋}  (29)

for all large enough n. Therefore, it suffices to show that

min{a(ℓ): 0 ≤ ℓ ≤ n/2}

is achieved either at ℓ = 0 or at ℓ = ⌊n/2⌋. In particular, if we show that a(ℓ) is unimodal, we are done. Let

b(ℓ) = \frac{a(ℓ + 1)}{a(ℓ)} = 2^{4(2ℓ+1+2\{n/2\})/n} \frac{⌊n/2⌋ − ℓ}{⌈n/2⌉ + ℓ + 1}  (30)

for all 0 ≤ ℓ ≤ n/2 − 1. Observe that, for all large enough n, we have

b(0) = 2^{4/n} \frac{⌊n/2⌋}{⌈n/2⌉ + 1} > 1  (31)

and

b(⌊n/2⌋ − 1) = \frac{1}{n}2^{4(1−1/n)} < 1.  (32)

We now show that b(ℓ) is itself unimodal. Let

c(ℓ) = \frac{b(ℓ + 1)}{b(ℓ)} = 2^{8/n} (\frac{⌊n/2⌋ − ℓ − 1}{⌊n/2⌋ − ℓ}) (\frac{⌈n/2⌉ + ℓ + 1}{⌈n/2⌉ + ℓ + 2})

= 2^{8/n} (1 − \frac{n + 1}{(⌊n/2⌋ − ℓ) (⌈n/2⌉ + ℓ + 2)}) (33)

for all 0 ≤ ℓ ≤ n/2 − 2. Note that c(0) > 1 for sufficiently large n and c(ℓ) is decreasing. Therefore, b(ℓ) is unimodal, ‘starts’ with b(0) > 1, and ‘ends’ with b(⌊n/2⌋ − 1) < 1. Therefore we conclude that a(ℓ) is indeed unimodal, as required. □

In Section 2.4, we shall need results similar to Fact 9 for the tail of Bi(n, p) for arbitrary 0 < p < 1. We shall use the following estimates (see [8, Theorem 2.1]).

Fact 11. Let X have binomial distribution Bi(n, p) and set λ = 𝔼(X) = pn. Then, for any t ≥ 0, we have

ℙ(X ≥ 𝔼(X) + t) ≤ exp (−\frac{t^{2}}{2(λ + t/3)})  (34)

and

ℙ(X ≤ 𝔼(X) − t) ≤ exp (−\frac{t^{2}}{2λ}) .  (35)

2.2. The well-distribution measure W. Our aim in this section is to prove Theorem 1. Let E_{N} = (e_{1}, …, e_{N}) ∈ {−1, 1}^{N} be drawn uniformly at random; we wish to estimate

W (E_{N}) = max_{a,b,M} ∑_{1≤j≤M} e_{a+jb},  (36)

where the maximum is taken over all integers a, b, and M with 1 ≤ a + b < a + bM ≤ N.

We start with the lower bound in (9). Observe that Fact 8 tells us that, for any fixed C > 0, we have

lim_{N→∞} ℙ (| ∑_{1≤j≤N} e_{j}| ≥ C\sqrt{N}) = 2\sqrt{\frac{2}{π}} ∫_{C/2}^{∞} e^{−2x^{2}}dx > 0.  (37)

The lower bound for W (E_{N}) for a typical E_{N} follows from (37) and the fact that

2\sqrt{\frac{2}{π}} ∫_{C/2}^{∞} e^{−2x^{2}}dx → 1

as C → 0. Indeed, the facts above show that, for any ε > 0, there is δ > 0 so that the lower bound in (9) holds with probability at least 1 − ε. It remains to prove the upper bound for W (E_{N}) for typical sequences E_{N}.

Let K be an integer. The arithmetic progressions of the form 1 ≤ a + b < a + 2b < ⋯ < a + T b ≤ K, where −b + 1 ≤ a ≤ 0 and T is the largest integer satisfying a+T b ≤ K, will be called complete arithmetic progressions in [1, K]∩ℤ. Our first auxiliary lemma gives an estimate, as a function of K, for the maximal value of the ‘discrepancy’

S_{a,b}^{(K)} = | ∑_{1≤a+jb≤K} e_{a+jb}|  (38)

over complete arithmetic progressions in [1, K], for typical sequences

(e_{1}, …, e_{K}) ∈ {−1, 1}^{K}.

Lemma 12. Let K be a positive integer and C a positive real number. Let (e_{1}, …, e_{K}) be drawn uniformly at random from {−1, 1}^{K}. The probability that there are integers a and b with −b + 1 ≤ a ≤ 0 such that

S_{a,b}^{(K)} = | ∑_{1≤a+jb≤K} e_{a+jb}| > C\sqrt{K}  (39)

is O(e^{−C^{2}/4}), as long as, say, C ≥ 2.

Proof. For any given integers a and b with −b + 1 ≤ a ≤ 0, the complete arithmetic progression 1 ≤ a+b < a+2b < ⋯ ≤ K in [1, K] has either ⌊K/b⌋ or ⌈K/b⌉ terms. Fix a large constant C, and observe that (23) in Fact 9 tells us that, if b ≤ K, then the probability that we have

S_{a,b}^{(K)} = | ∑_{1≤a+jb≤K} e_{a+jb}| > C\sqrt{K}

is less than 2e^{−bC^{2}/4}.

Now, given b, there are b arithmetic progressions as above, and the possible values for b are 1, …, K − 1. Therefore, the probability that there are a and b for which S_{a,b}^{(K)} is larger than C\sqrt{K} is

O( ∑_{1≤b<K} be^{−bC^{2}/4}) = O(e^{−C^{2}/4}),  (40)

where we used that C ≥ 2 and hence the terms in the sum in (40) drop geometrically. □

Let us now consider intervals of integers of the form

B_{m,r} = (m2^{r}, (m + 1)2^{r}] ∩ ℤ,  (41)

where m and r are non-negative integers. Clearly, |B_{m,r}| = 2^{r}. We refer to the B_{m,r} as blocks. Put

k = 1 + ⌊log_{2} N⌋,  (42)

and observe that all blocks B_{m,r} contained in [1, N] have r < k.

Lemma 12 above tells us that, given a block B_{m,r}, the probability that the discrepancy on some complete arithmetic progression contained in B_{m,r} is greater than C(k − r)\sqrt{2^{r}} is O(e^{−C^{2}(k−r)^{2}/4}); that is, the probability that we have

max_{a,b} |∑\{e_{a+jb}: a + jb ∈ B_{m,r}\}| > C(k − r)\sqrt{2^{r}}  (43)

is O(e^{−C^{2}(k−r)^{2}/4}). On the other hand, for any r, we have at most N/2^{r} ≤ 2^{k−r} blocks B_{m,r} contained in [1, N]. Therefore, if C is large enough, the probability that (43) holds for some block B_{m,r} ⊂ [1, N] is

O( ∑_{0≤r<k} 2^{k−r}e^{−C^{2}(k−r)^{2}/4}) = O(e^{−C^{2}/4}),  (44)

which tends to 0 as C → ∞. Therefore, to complete our proof, we may suppose that (43) does not hold for any B_{m,r}, that is, we may suppose that

(*) for all m and r with B_{m,r} ⊂ [1, N], we have

max_{a,b} |∑\{e_{a+jb}: a + jb ∈ B_{m,r}\}| ≤ C(k − r)\sqrt{2^{r}}.

If we are able to deduce from (*) that W (E_{N}) = O(\sqrt{N}), then we shall be done. Let us now state and prove the following combinatorial observation.

Fact 13. Given any integers 1 ≤ p < q ≤ N, it is possible to write the integer interval I_{p,q} = [p, q] ∩ ℤ as the disjoint union of blocks B_{m,r} so that, for any r, we use at most two blocks of the form B_{m,r}.

Proof. To see this, first consider the smallest f for which [p, q] ⊂ [1, 2^{f}) (that is, f = ⌈log_{2}(q + 1)⌉), and then consider the ‘dyadic’ ruler in the interval [1, 2^{f}): the level 0 mark in our ruler is 1; the level 1 mark is 2^{f−1}; the set of level 2 marks is {2^{f−2}, 2^{f−1} + 2^{f−2}}; the set of level 3 marks is

{2^{f−3}, 2^{f−2} + 2^{f−3}, 2^{f−1} + 2^{f−3}, 2^{f−1} + 2^{f−2} + 2^{f−3}};

and so on. Let L be the mark of smallest level contained in [p, q]. One may then use the binary expansion of q−L to obtain a decomposition of (L, q]∩ℤ into blocks, using, for each r, at most one block of the form B_{m,r}. Similarly, one may use the binary expansion of L−p+1 to obtain such a decomposition of [p, L] ∩ ℤ. □

We now use (*) and Fact 13 above to prove that W (E_{N}) = O(\sqrt{N}). Given a, b, and M with 1 ≤ a+b < a+Mb ≤ N, we write [a+b, a+Mb]∩ℤ as a disjoint union of blocks such that, for each r, we make use of at most two blocks of the form B_{m,r}. Let B be the collection of blocks B_{m,r} that we have used in our partition of [a + b, a + Mb] ∩ ℤ. We have

| ∑_{1≤j≤M} e_{a+jb}| ≤ ∑_{B_{m,r}∈B} |∑ {e_{a+jb}: a + jb ∈ B_{m,r}}|

≤ ∑_{0≤r<k} 2 × C(k − r)\sqrt{2^{r}}

= 2C2^{k/2} ∑_{1≤ℓ≤k} ℓ2^{−ℓ/2} = O(2^{k/2}) = O(\sqrt{N}).

This completes the proof of Theorem 1.

2.3. The correlation measure C_{k}. In this section we prove Theorems 2 and 3.

2.3.1. Proof of Theorem 2. We shall first prove the upper estimate for C_{k}(E_{N}) for typical sequences E_{N}. Indeed, we prove the following lemma.

Lemma 14. Let ε = ε(N) = (log log N)/ log N. With probability tending to 1 as N → ∞, we have

C_{k}(E_{N}) < \sqrt{(2 + ε)N log (N\binom{N}{k})}  (45)

for every integer k with 2 ≤ k ≤ N/4.

Proof. We first consider a fixed integer k with 2 ≤ k ≤ N/4. Fix a sequence D = (d_{1}, …, d_{k}) with 0 ≤ d_{1} < ⋯ < d_{k} < N. Since E_{N} = (e_{i})_{1≤i≤N} is drawn uniformly at random from {−1, 1}^{N}, the sequence

(e_{1+d_{1}}e_{1+d_{2}} … e_{1+d_{k}}, e_{2+d_{1}}e_{2+d_{2}} … e_{2+d_{k}}, …, e_{N−d_{k}+d_{1}}e_{N−d_{k}+d_{2}} … e_{N})

is a random element of the uniform space {−1, 1}^{N−d_{k}}. Recall (6), and let an integer M with M + d_{k} ≤ N be fixed. Clearly, V (E_{N}, M, D) has the same distribution as S^{±}(M). We now use (23) with

a = \sqrt{(2 + ε)N log (N\binom{N}{k})},

where ε = (log log N)/ log N is as in the statement of our lemma, to deduce that

|V (E_{N}, M, D)| > \sqrt{(2 + ε)N log (N\binom{N}{k})}  (46)

holds with probability less than

exp \{−\frac{1}{2M} (2 + ε)N log (N\binom{N}{k})\} ≤ \{N\binom{N}{k}\}^{−(1+ε/2)} .  (47)

Summing over all possible choices of M and D, we get an extra factor

of N\binom{N}{k}, which gives an upper bound of \{N\binom{N}{k}\}^{−ε/2} for the probability of the event that (46) should hold for some M and D. We shall now sum these bounds over 2 ≤ k ≤ N/4. For estimating this sum, we observe that

\frac{1}{1 − 1/3^{δ}} ≤ \frac{1}{δ}  (48)

for all 0 < δ ≤ δ_{0}, where δ_{0} > 0 is some suitably small absolute constant, and

\binom{N}{k − 1} /\binom{N}{k} ≤ \frac{1}{3}  (49)

for 2 < k ≤ N/4. Using (48) and (49), we see that the probability that (46) holds for some M, D, and k with k in the range 2 ≤ k ≤ N/4 is at most

∑_{2≤k≤N/4} \{N\binom{N}{k}\}^{−ε/2} ≤ \{N\binom{N}{2}\}^{−ε/2} ∑_{ℓ≥0} (\frac{1}{3})^{ℓε/2}

≤ \frac{2}{ε} \{N\binom{N}{2}\}^{−ε/2} = O (\frac{1}{(log log N)\sqrt{log N}} ) = o(1), (50)

and our result follows. □

The proof of Theorem 2 will be complete if we prove the following result.

Lemma 15. With probability tending to 1 as N → ∞, we have

C_{k}(E_{N}) > \frac{2}{5}\sqrt{N log \binom{N}{k}}  (51)

for every integer k with 2 ≤ k ≤ N/4.

We start with an auxiliary result.

Fact 16. Let m = ⌊N/3⌋. For every sufficiently large N, the following hold. (i) If 2 ≤ k ≤ log m, then

\sqrt{N log \binom{N/3}{k}} ≥ 0.99\sqrt{N log \binom{N}{k}}.  (52)

(ii) If log m < k ≤ N/4, then

\sqrt{N log \binom{N/3}{k}} ≥ \sqrt{\frac{1 − 10^{−10}}{3} N log \binom{N}{k}}.  (53)

We include the proof of Fact 16 for completeness. The reader may prefer to go directly to the proof of Lemma 15, given below.

Proof of Fact 16. Throughout this proof, we suppose that N is larger than a suitably large absolute constant.

Let us start with the proof of (i). Suppose 2 ≤ k ≤ log m. Using that (a/b)^{b} ≤ \binom{a}{b} ≤ (ea/b)^{b}, we have

\binom{N/3}{k} ≥ (\frac{N}{3k} )^{k} ≥ (\frac{1}{3e})^{k} (\frac{eN}{k} )^{k} ≥ (\frac{1}{3e})^{k} \binom{N}{k}.  (54)

Therefore,

log \binom{N/3}{k} ≥ (1 − \frac{k log(3e)}{log \binom{N}{k}}) log \binom{N}{k}

≥ (1 − \frac{1 + log 3}{log(N/k)}) log \binom{N}{k} ≥ (1 − \frac{3}{log N} ) log \binom{N}{k}. (55)

Inequality (52) follows from (55), and (i) is proved.

Let us now turn to (ii). Suppose log m < k ≤ N/4. Since \binom{N/3}{k} ≥ \binom{⌊N/3⌋}{k} = \binom{m}{k}, it clearly suffices to prove that

\binom{m}{k} ≥ \binom{N}{k}^{(1−10^{−10})/3}  (56)

for all large enough N. If k < m/2, then m − k > m/2 > k. Moreover,

\binom{m}{k} = \binom{m}{m − k}  (57)

and

\binom{N}{m − k}^{(1−10^{−10})/3} ≥ \binom{N}{k}^{(1−10^{−10})/3}.  (58)

Therefore, it suffices to consider k with

\frac{1}{2} ⌊\frac{N}{3} ⌋ = \frac{1}{2}m ≤ k ≤ \frac{N}{4} .  (59)

Now, the left-hand side of (56) is decreasing in the range (59), while the right-hand side is increasing in that range. Therefore, it suffices to verify (56) at k = ⌊N/4⌋.

To check (56) for k = ⌊N/4⌋, we may use the fact that if r = r(n) is an integer function of n with lim_{n→∞} r(n)/n = x, then

\binom{n}{r} = 2^{(H(x)+o(1))n},  (60)

where o(1) → 0 as n → ∞, and

H(x) = −x log_{2} x − (1 − x) log_{2}(1 − x)  (61)

for all 0 ≤ x ≤ 1 (H(0) = H(1) = 0). Of course, this is an immediate consequence of Stirling’s formula

n! = \sqrt{2πn} (\frac{n}{e})^{n} (1 + O (\frac{1}{n})) .  (62)

We now note that

\frac{1}{3}H (\frac{3}{4}) = \frac{1}{3}H (\frac{1}{4}) > \frac{1 − 10^{−10}}{3} H (\frac{1}{4}) ,  (63)

and hence (56) does indeed follow for k = ⌊N/4⌋ as long as N is large enough. This completes the proof of Fact 16. □

We now give the proof of the main result in this section.

Proof of Lemma 15. Set m = ⌊N/3⌋, and recall that we write S(m, 1/2) for a random variable with binomial distribution Bi(m, 1/2). Fix 2 ≤ k ≤ N/4. We are interested in the largest integer r for which

ℙ (S(m, 1/2) ≥ \frac{1}{2}(m + r)) ≥ k^{2}(log N)\binom{m + 1}{k − 1}^{−1}  (64)

holds. Indeed, we let

r(m) = r_{k}(m) = max {r ∈ ℕ: inequality (64) holds} .  (65)

We need the following lower bounds for r(m).

Fact 17. For every sufficiently large N, the following hold.

(i) If 2 ≤ k ≤ log m, then

r(m) ≥ 0.99\sqrt{2m log \binom{m + 1}{k − 1}}.  (66)

(ii) If log m < k ≤ N/4, then

r(m) ≥ (1 − 10^{−10})\sqrt{\frac{m}{log 2} log \binom{m + 1}{k − 1}}.  (67)

(iii) If 2 ≤ k ≤ N/4, then

r(m) ≥ \frac{2}{5}\sqrt{N log \binom{N}{k}}.  (68)

Proof. In this proof, we may and shall suppose that N is larger than a suitably large absolute constant for the inequalities below to hold.

We start observing that we have

k^{2}(log N)\binom{m + 1}{k − 1}^{−1} = \binom{m + 1}{k − 1}^{−1+o(1)}  (69)

uniformly in k in the range 2 ≤ k ≤ N/4; that is, for all η > 0 there is N_{0} such that if N ≥ N_{0}, then, for all 2 ≤ k ≤ N/4, we have

k^{2} log N ≤ \binom{m + 1}{k − 1}^{η}.  (70)

To check this assertion, note that if 2 ≤ k ≤ (log N)^{2}, then the left-hand side of (70) is polylogarithmic in N, whereas \binom{m+1}{k−1} ≥ N/3. On the other hand, if (log N)^{2} < k ≤ N/4, then the left-hand side of (70) is O(N^{2} log N), whereas \binom{m+1}{k−1} ≥ ((m + 1)/(k − 1))^{k−1} ≥ (4/3 + o(1))^{k−1} ≥ (5/4)^{(log N)^{2}−1}, which is superpolynomial in N. Therefore, (69) does hold.

We now turn to the proof of (i). Suppose 2 ≤ k ≤ log m. Set

r = ⌈0.99\sqrt{2m log \binom{m + 1}{k − 1}}⌉ .  (71)

We shall show that (64) holds for the value of r given in (71). Let

c = \frac{r + 1}{2\sqrt{m}} = (1 + o(1))0.99\sqrt{\frac{1}{2} log \binom{m + 1}{k − 1}}.  (72)

We now use (21) in Fact 8(ii) to deduce that

ℙ (S(m, 1/2) ≥ \frac{1}{2}(m + r)) ≥ ℙ (S(m, 1/2) ≥ ⌊\frac{m}{2}⌋ + c\sqrt{m})

= \frac{e^{−2c^{2}}}{2c\sqrt{2π}} (1 + o(1)) ≥ \frac{1}{100}\binom{m + 1}{k − 1}^{−0.99} (log \binom{m + 1}{k − 1})^{−1/2} , (73)

which is clearly larger than

k^{2}(log N)\binom{m + 1}{k − 1}^{−1}  (74)

for large enough N (see (69)). This completes the proof of (64), and hence (i) follows. We now turn to (ii). Suppose log m < k ≤ N/4. Set

r = ⌈(1 − 10^{−10})\sqrt{\frac{m}{log 2} log \binom{m + 1}{k − 1}}⌉ .  (75)

We shall show that (64) holds for the value of r given in (75). Let

ℓ = ⌈\frac{r + 1}{2}⌉ = (1 + o(1))\frac{1 − 10^{−10}}{2\sqrt{log 2}} \sqrt{m log \binom{m + 1}{k − 1}}.  (76)

We now use (25) in Fact 10 to deduce that

ℙ(S(m, 1/2) ≥ \frac{1}{2}(m + r)) ≥ ℙ(S(m, 1/2) ≥ ⌊\frac{m}{2}⌋ + ℓ)

≥ (1 + o(1))2^{−4(⌈(r+1)/2⌉+1/2)^{2}/m}\sqrt{\frac{2}{πm}}

≥ (1 + o(1))2^{−r^{2}/m}2^{−(6r+9)/m}\sqrt{\frac{2}{πm}}

≥ (1 + o(1))\binom{m + 1}{k − 1}^{−1+10^{−10}} ≥ k^{2}(log N)\binom{m + 1}{k − 1}^{−1}

for all large enough N, where, again, we used (69) for the last inequality. This completes the proof of (64), and (ii) follows.

We now turn to (iii). Suppose first that 2 ≤ k ≤ log m, so that (66) holds.

Using that \binom{m+1}{k−1} ≥ \binom{N/3}{k−1} ≥ \binom{N/3}{k}^{1/2} in this range of k and Fact 16(i), we deduce that

r(m) ≥ 0.99\sqrt{2 ⌊\frac{N}{3} ⌋ log \binom{m + 1}{k − 1}}

≥ (1 + o(1))\frac{0.99}{\sqrt{3}}\sqrt{N log \binom{N/3}{k}} ≥ \frac{2}{5}\sqrt{N log \binom{N}{k}}. (77)

Suppose now that log m < k ≤ N/4, so that (67) holds. Using that \binom{m+1}{k−1} ≥

\binom{N/3}{k}^{1−o(1)} in this range of k and Fact 16(ii), we deduce that

r(m) ≥ \frac{1 − 10^{−10}}{\sqrt{log 2}} \sqrt{⌊\frac{N}{3} ⌋ log \binom{m + 1}{k − 1}}

≥ (1 + o(1))\frac{1 − 10^{−10}}{\sqrt{3 log 2}} \sqrt{N log \binom{N/3}{k}} ≥ \frac{2}{5}\sqrt{N log \binom{N}{k}}. (78)

Inequality (68) follows from (77) and (78), and (iii) is proved. □

To prove Lemma 15, we shall show that, with probability ≤ 2/k^{2} log N, we have

C_{k}(E_{N}) ≤ r_{k}(m),  (79)

and then we shall sum over all 2 ≤ k ≤ N/4. This gives that (79) holds for some k with 2 ≤ k ≤ N/4 with probability O(1/ log N) = o(1). Therefore,

(79) fails for all 2 ≤ k ≤ N/4 with probability 1 − o(1), and Lemma 15 will be proved.

Let 2 ≤ k ≤ N/4 be fixed. Our strategy to estimate the probability that (79) should hold will be as follows. Recall E_{N} = (e_{1}, …, e_{N}) and let u = (e_{1}, …, e_{m}). Let D_{k} be the set of (k − 1)-tuples D = (d_{1}, …, d_{k−1}) with m ≤ d_{1} < ⋯ < d_{k−1} ≤ 2m. For each D ∈ D_{k}, let

v_{D} = (e_{1+d_{1}}e_{1+d_{2}} … e_{1+d_{k−1}}, …, e_{m+d_{1}}e_{m+d_{2}} … e_{m+d_{k−1}}),  (80)

and let A(D) be the event that

|⟨u, v_{D}⟩| > r(m) = r_{k}(m)  (81)

holds. It suffices to show that some A(D) (D ∈ D_{k}) holds with probability at least 1 − 2/k^{2} log N. For convenience, let X = X(E_{N}) be the number of events A(D) (D ∈ D_{k}) that hold for E_{N}. Let

p = p(m) = ℙ (S(m, 1/2) ≥ \frac{1}{2}(m + r(m))) .  (82)

Because of (65), we have

𝔼(X) = p|D_{k}| = p\binom{m + 1}{k − 1} ≥ k^{2} log N.  (83)

We have now arrived at the key claim: the events A(D) (D ∈ D_{k}) are pairwise independent.

Claim 18. For all distinct D and D′ ∈ D_{k}, we have

ℙ(A(D) ∩ A(D′)) = p^{2}.  (84)

We postpone the proof of Claim 18. To complete the proof of Lemma 15, we make use of the following result, which gives a lower bound for the probability of a union of pairwise independent events. We shall in fact state a stronger lemma, which has as hypothesis that the events should be asymptotically negatively correlated. Versions of this lemma may be found in [5] and [6]. More recently, Petrov used this result to generalize the Borel– Cantelli lemma [13, 14]

Lemma 19. Let A_{1}, …, A_{M} be events in a probability space, each with probability at least p. Let ε ≥ 0 be given, and suppose that

ℙ(A_{i} ∩ A_{j}) ≤ p^{2}(1 + ε)  (85)

for all i ≠ j. Then

ℙ( ⋃_{1≤j≤M} A_{j}) ≥ \frac{Mp}{1 + (M − 1)p(1 + ε)}

= 1 − \frac{1 − p + (M − 1)pε}{1 + (M − 1)p(1 + ε)} > 1 − ε − \frac{2}{Mp}. (86)

The proof of Lemma 19 is given below. We conclude the proof of Lemma 15 combining Claim 18 and Lemma 19. It suffices to notice that we have M = \binom{m+1}{k−1} pairwise independent events A(D) (that is, ε = 0), and pM ≥ k^{2} log N (see (83)). Inequality (86) then tells us that, with probability greater than 1−2/k^{2} log N, the event A(D) happens for some D ∈ D_{k}. We conclude that (79) occurs with probability at most 2/k^{2} log N, and hence, as observed above, summing over all 2 ≤ k ≤ N/4, Lemma 15 follows. □

We shall now prove Claim 18 and Lemma 19.

Proof of Claim 18. Let us consider the events A(D) and A(D′) for two distinct D, D′ ∈ D_{k}. Let D = (d_{1}, …, d_{k−1}) and D′ = (d′_{1}, …, d′_{k−1}), and recall that

m ≤ d_{1} < ⋯ < d_{k−1} ≤ 2m, m ≤ d′_{1} < ⋯ < d′_{k−1} ≤ 2m,

and that

v_{D} = (e_{1+d_{1}}e_{1+d_{2}} … e_{1+d_{k−1}}, …, e_{m+d_{1}}e_{m+d_{2}} … e_{m+d_{k−1}}),
v_{D′} = (e_{1+d′_{1}}e_{1+d′_{2}} … e_{1+d′_{k−1}}, …, e_{m+d′_{1}}e_{m+d′_{2}} … e_{m+d′_{k−1}}).

Let v_{i}^{D} = e_{i+d_{1}} … e_{i+d_{k−1}} and v_{i}^{D′} = e_{i+d′_{1}} … e_{i+d′_{k−1}} (1 ≤ i ≤ m) be the components of v_{D} and v_{D′}. For convenience, let us write ω ∈_{U} Ω if ω is a uniformly distributed random element of Ω. We shall prove more than (84); we shall prove that

(e_{1}v_{1}^{D}, …, e_{m}v_{m}^{D}, e_{1}v_{1}^{D′}, …, e_{m}v_{m}^{D′}) ∈_{U} {−1, 1}^{2m}.  (87)

Clearly, this proves Claim 18, because ⟨u, v_{D}⟩ = ∑_{1≤i≤m} e_{i}v_{i}^{D} and ⟨u, v_{D}⟩ = ∑_{1≤i≤m} e_{i}v_{i}^{D′}.

To check (87), we make the following observation: we have

(x_{1}, …, x_{m}, y_{1}, …, y_{m}) ∈_{U} {−1, 1}^{2m}  (88)

if and only if

(x_{1}, …, x_{m}, x_{1}y_{1}, …, x_{m}y_{m}) ∈_{U} {−1, 1}^{2m}.  (89)

This observation follows immediately from the fact that the map that takes the vector in (88) to the vector in (89) is a bijection (it is in fact an involution).

We apply the observation above to

x_{i} = e_{i}v_{i}^{D} and y_{i} = e_{i}v_{i}^{D′} (1 ≤ i ≤ m)  (90)

to obtain that (87) holds if and only if

(x_{1}, …, x_{m}, x_{1}y_{1}, …, x_{m}y_{m})

= (e_{1}v_{1}^{D}, …, e_{m}v_{m}^{D}, v_{1}^{D}v_{1}^{D′}, …, v_{m}^{D}v_{m}^{D′}) ∈_{U} {−1, 1}^{2m}. (91)

However, (91) does hold. Indeed, since D ≠ D′, a moment’s thought shows that

(v_{1}^{D}v_{1}^{D′}, …, v_{m}^{D}v_{m}^{D′}) ∈_{U} {−1, 1}^{m}.  (92)

(To see (92), note that the value of v_{i}^{D}v_{i}^{D′} (1 ≤ i ≤ m) is determined by the e_{j} with

j ∈ i + D△D′ = i + (D \ D′) ∪ (D′ \ D)  (93)

alone, and the family of sets i + D△D′ (1 ≤ i ≤ m) form a “hypertree”. We shall not elaborate on this simple argument.) Fact (92) and the fact that the e_{i} (1 ≤ i ≤ m) are not involved in (92) at all imply (91), and hence (87) does hold. This completes the proof of Claim 18. □

Proof of Lemma 19. Let f = ∑_{1≤j≤M} χ_{j}, where χ_{j} denotes the characteristic function of the event A_{j}. We have

∫ f dℙ = ∑_{1≤j≤M} ℙ(A_{j}) ≥ Mp,  (94)

and

∫ f^{2} dℙ = ∫ ( ∑_{1≤j≤M} χ_{j} + 2 ∑_{1≤i<j≤M} χ_{i}χ_{j}) dℙ

≤ ∫ f dℙ + M(M − 1)p^{2}(1 + ε). (95)

Let X = ⋃_{1≤j≤M} A_{j}. By the Cauchy–Schwarz inequality, we have

( ∫_{X} 1 dℙ)( ∫_{X} f^{2} dℙ) ≥ ( ∫_{X} f dℙ)^{2},

which, together with (95), gives

ℙ(X)( ∫ f dℙ + M(M − 1)p^{2}(1 + ε)) ≥ ( ∫_{X} f dℙ)^{2}.

Therefore

ℙ(X) ≥ ( ∫_{X} f dℙ)^{2}/( ∫ f dℙ + M(M − 1)p^{2}(1 + ε))

≥ \frac{M^{2}p^{2}}{Mp + M(M − 1)p^{2}(1 + ε)} = \frac{Mp}{1 + (M − 1)p(1 + ε)}, (96)

and the lemma follows. □

2.3.2. Proof of Theorem 3. Theorem 3 follows simply from some well known results concerning concentration of measure. Let ε and k = k(N) as in the statement of that theorem be given. We now observe that if E_{N} = (e_{j})_{1≤j≤N} and E′_{N} = (e′_{j})_{1≤j≤N} ∈ {−1, 1}^{N} differ in exactly one coordinate, then

|V (E_{N}, M, D) − V (E′_{N}, M, D)| ≤ 2k  (97)

for any M and D. Indeed, suppose e′_{j_{0}} = −e_{j_{0}} and e_{j} = e′_{j} for all j ≠ j_{0}. Note that e_{j_{0}} is involved in at most k summands in the definition of V (E_{N}, M, D) (see (3)), and hence changing its value to −e_{j_{0}} will change V (E_{N}, M, D) by at most 2k. Therefore,

|C_{k}(E_{N}) − C_{k}(E′_{N})| ≤ 2k  (98)

as well. We may now use, for instance, Lemma 1.2 from [12] to deduce that, for any t > 0, we have

ℙ(|C_{k}(E_{N}) − 𝔼(C_{k})| ≥ t) ≤ 2 exp (−t^{2}/2k^{2}N) .  (99)

It now suffices to check that if

k ≤ log N − log log N,  (100)

then, taking t = ε𝔼(C_{k}), we have that the right-hand side of (99) is o(1). Theorem 2 tells us that, if N is large enough, then, say,

𝔼(C_{k}) ≥ \frac{1}{5}\sqrt{N log \binom{N}{k}}.  (101)

Condition (100) on k and (101) easily imply that

\frac{t^{2}}{2k^{2}N} = \frac{ε^{2}𝔼(C_{k})^{2}}{2k^{2}N} → ∞  (102)

as N → ∞, and this completes the proof of Theorem 3.

2.4. The normality measure N. Recall that the normality measure of E_{N} = (e_{1}, …, e_{N}) ∈ {−1, 1}^{N} is defined as

N (E_{N}) = max_{k} max_{X} max_{M} |T (E_{N}, M, X) − \frac{M}{2^{k}} | ,  (103)

where the maxima are taken over all k ≤ log_{2} N, X ∈ {−1, 1}^{k}, and 0 < M ≤ N + 1 − k, and T (E_{N}, M, X) is the number of occurrences of the pattern X in E_{N}, counting only those occurrences starting with some e_{j} with j ≤ M (see (1)). Our aim in this section is to prove Theorem 4.

Proof of Theorem 4. We start with the lower bound in (12). We take k = 1 in (103); in fact, we consider T (E_{N}, N, (1)), the number of occurrences of 1 in E_{N}. Fact 8 tells us that

lim_{N→∞} ℙ (|T (E_{N}, N, (1)) − \frac{N}{2} | ≥ C\sqrt{N}) = 2\sqrt{\frac{2}{π}} ∫_{C}^{∞} e^{−2x^{2}}dx > 0. (104)

Since

2\sqrt{\frac{2}{π}} ∫_{C}^{∞} e^{−2x^{2}}dx → 1

as C → 0, the lower bound in Theorem 4 follows. Indeed, the facts above show that, for any ε > 0, there is δ > 0 so that the lower bound in (12) holds with probability at least 1 − ε. It remains to prove the upper bound for N (E_{N}) for typical sequences E_{N}.

The basic lemma that we shall use is Lemma 20 below. Recall that we refer to the sets B_{m,r} as blocks (recall (41)). For an integer k ≥ 1, X ∈ {−1, 1}^{k}, and B_{m,r} a block with

max B_{m,r} = (m + 1)2^{r} ≤ N − k + 1,  (105)

we shall write T (E_{N}, B_{m,r}, X) for the number of occurrences of the pattern X in E_{N}, counting only those occurrences starting in B_{m,r}, that is,

T (E_{N}, B_{m,r}, X) = card{n ∈ B_{m,r}: E_{N}^{(n)} = X},  (106)

where

E_{N}^{(n)} = (e_{n}, e_{n+1}, …, e_{n+k−1}),  (107)

and, as usual, E_{N} = (e_{1}, …, e_{N}).

Lemma 20. Let m and r be fixed non-negative integers with B_{m,r} ⊂ [1, N]. For all D > 0, the probability that there is X ∈ {−1, 1}^{k} with k ≤ log_{2} N satisfying (105) such that

|T (E_{N}, B_{m,r}, X) − 2^{r−k}| > D\sqrt{2^{r}}  (108)

is at most

O (e^{−2D^{2}/9}) + 2(log_{2} N)^{2}N exp (−\frac{3D}{4 log_{2} N} 2^{r/2}) .  (109)

We postpone the proof of Lemma 20 and continue with the proof of Theorem 4. Let us apply Lemma 20 with

D = C(K − r)  (110)

for all blocks B_{m,r} ⊂ [1, N], where

K = 1 + ⌊log_{2} N⌋,  (111)

and C is a large constant. There are at most N/2^{r} < 2^{K−r} blocks B_{m,r} contained in [1, N] and any such block is such that r < K. Let us call a block B_{m,r} large if

r ≥ 4 log_{2} log_{2} N  (112)

and small otherwise. We claim that, with the value of D given in (110) with a large enough constant C, inequality (108) holds for some large block B_{m,r} and some X ∈ {−1, 1}^{k} (k ≤ log_{2} N) with probability O (e^{−2C^{2}/9}).

To prove our claim, for convenience, let ∑′_{r} indicate sum over all r < K satisfying (112). Adding up (109) over all large blocks B_{m,r} ⊂ [1, N], we get

∑′_{r} 2^{K−r}O (e^{−2C^{2}(K−r)^{2}/9})

+ ∑′_{r} 2^{K−r+1}(log_{2} N)^{2}N exp (−\frac{3C(K − r)}{4 log_{2} N} 2^{r/2})

≤ ∑_{1≤ℓ≤K} 2^{ℓ}O (e^{−2C^{2}ℓ^{2}/9})

+ (log_{2} N)^{2}N^{2} ∑′_{r} exp (−\frac{3C}{4 log_{2} N} 2^{r/2})

= O (e^{−2C^{2}/9}) + O (\frac{1}{N} ) = O (e^{−2C^{2}/9}) ,  (113)

as long as C is a large enough constant and N is large enough with respect to C, proving our claim.

Since the bound in (113) tends to 0 as C → ∞, we may and shall suppose henceforth that

(**) for all integers m, r, and k ≤ log_{2} N with B_{m,r} ⊂ [1, N] satisfying (105) and (112), and every X ∈ {−1, 1}^{k}, we have

|T (E_{N}, B_{m,r}, X) − 2^{r−k}| ≤ C(K − r)\sqrt{2^{r}}.

Now fix k ≤ log_{2} N and fix M with 1 ≤ M ≤ N − k + 1. Observe that we may write [1, M] as a disjoint union of blocks B_{m,r} (r ≤ log_{2} M < K) with at most one block of the form B_{m,r} for each r. Indeed, such a decomposition of [1, M] may be read out from the binary expansion of M. Let us write I for the set of the pairs (m, r) for which B_{m,r} occurs in this decomposition of [1, M]. Furthermore, let I = I_{+} ∪ I_{−} be the partition of I with

I_{+} = {(m, r) ∈ I: r satisfies (112)}.  (114)

For later reference, observe that

|I_{−}| < 4 log_{2} log_{2} N.  (115)

Observe also that if (m, r) ∈ I_{−}, then

|T (E_{N}, B_{m,r}, X) − 2^{r−k}| ≤ 2^{r} < (log_{2} N)^{4}  (116)

for any X ∈ {−1, 1}^{k}. Using (**), (115), and (116), we see that, for any X ∈ {−1, 1}^{k}, we have

|T (E_{N}, M, X) − M2^{−k}| ≤ ∑_{(m,r)∈I} |T (E_{N}, B_{m,r}, X) − 2^{r−k}|

= ∑_{(m,r)∈I_{+}} |T (E_{N}, B_{m,r}, X) − 2^{r−k}| + ∑_{(m,r)∈I_{−}} |T (E_{N}, B_{m,r}, X) − 2^{r−k}|

≤ ∑_{0≤r<K} C(K − r)2^{r/2} + |I_{−}|(log_{2} N)^{4}  (117)

≤ C2^{K/2} ∑_{1≤ℓ≤K} ℓ2^{−ℓ/2} + 4(log_{2} log_{2} N)(log_{2} N)^{4}

= O(2^{K/2}) = O(\sqrt{N}),

as required. It now remains to prove Lemma 20. □

Proof of Lemma 20. Let non-negative integers m and r with B_{m,r} ⊂ [1, N] be fixed, and let D be a positive real. Because of the form of the upper bound in (109), we may suppose that D ≥ D_{0} for some conveniently large absolute constant D_{0}. Indeed, if we prove an upper bound of the form (109) for D ≥ D_{0}, then we may simply adjust the absolute constant in the big O term to take into account the case in which D < D_{0} (making (109) greater than 1, say).

Let us now fix k ≤ log_{2} N for which (105) holds, and let X ∈ {−1, 1}^{k} be given. We shall first show that the probability that (108) happens for this fixed X is suitably small.

Let us decompose B_{m,r} in arithmetic progressions with difference k: for 0 ≤ s < k, let

I_{s} = {j ∈ B_{m,r}: j ≡ s (mod k)},  (118)

so that B_{m,r} = ⋃_{0≤s<k} I_{s} is a partition of B_{m,r}. Let

T (E_{N}, I_{s}, X) = card{n: n ∈ I_{s} and E_{N}^{(n)} = X},  (119)

and observe that, clearly, T (E_{N}, B_{m,r}, X) = ∑_{0≤s<k} T (E_{N}, I_{s}, X). In particular, if

|T (E_{N}, I_{s}, X) − |I_{s}|2^{−k}| ≤ \frac{1}{k} D\sqrt{2^{r}}  (120)

for all 0 ≤ s < k, then (108) fails. Let us fix 0 ≤ s < k, and let us estimate the probability that (120) should fail.

Clearly, T (E_{N}, I_{s}, X) has binomial distribution Bi(|I_{s}|, 2^{−k}). Therefore, using Fact 11, we see that the probability that (120) should fail is at most

2 exp (−\frac{t^{2}}{2(λ + t/3)}) ,  (121)

where t = (D/k)2^{r/2} and λ = |I_{s}|2^{−k} ≤ 2^{r−k}. If λ ≥ t/3, then (121) is at most

2 exp (−\frac{t^{2}}{4λ}) ≤ 2 exp (−\frac{D^{2}2^{r}/k^{2}}{2^{r−k+2}} ) = 2e^{−D^{2}2^{k−2}/k^{2}}.  (122)

If, on the other hand, λ < t/3, then (121) is at most

2 exp (−\frac{3}{4}t) = 2 exp (−\frac{3D}{4k} 2^{r/2}) ≤ 2 exp (−\frac{3D}{4 log_{2} N} 2^{r/2}) . (123)

Below, rather crudely, we bound (121) by the sum of (122) and (123). Indeed, we add up (122) and (123) over all choices of s (0 ≤ s < k) and X ∈ {−1, 1}^{k}, and get that the probability that (108) should hold for some X ∈ {−1, 1}^{k} (k ≤ log_{2} N) is

2k2^{k} (e^{−D^{2}2^{k−2}/k^{2}} + exp (−\frac{3D}{4 log_{2} N} 2^{r/2})) .  (124)

We now sum (124) over all 1 ≤ k ≤ ⌊log_{2} N⌋ = K − 1. We add up the terms in (124) separately.

We have

2 ∑_{1≤k<K} k2^{k}e^{−D^{2}2^{k−2}/k^{2}} = 4e^{−D^{2}/2} + 2^{4}e^{−D^{2}/4} + 3 × 2^{4}e^{−2D^{2}/9}S, (125)

where S is dominated by the sum of a convergent geometric series as long as D is large enough. Therefore, the sum in (125) is

O (e^{−2D^{2}/9}) .  (126)

Moreover,

2 ∑_{1≤k<K} k2^{k} exp (−\frac{3D}{4 log_{2} N} 2^{r/2}) ≤ 2(log_{2} N)^{2}N exp (−\frac{3D}{4 log_{2} N} 2^{r/2}) .

(127)

Lemma 20 follows from (125)–(127). □

3. Small W (E_{N}) and N (E_{N})

3.1. The probability of having W (E_{N}) small. Our aim in this section is to prove Theorem 5, which tells us that, given any δ > 0, the probability of the event W (E_{N}) ≤ δ\sqrt{N} is bounded away from 0.

The proof of Theorem 5 is given in Section 3.1.2, but a key ‘positive correlation’ result is first proved in Section 3.1.1. To be a little more precise, Claim 26, needed in the proof of Theorem 5, is proved by invoking a general correlation result given in Corollary 22 in Section 3.1.1.

3.1.1. Preliminary lemmas. We start with some preliminary results concerning distributions on the integers, that is, vectors (p_{n})_{n∈ℤ} with ∑_{n∈ℤ} p_{n} = 1 and p_{n} ≥ 0 for all n. Let us say that the distribution (p_{n})_{n∈ℤ} is symmetric if p_{n} = p_{−n} for all n and monotone if p_{n} ≥ p_{n+1} for all n ≥ 0.

Let (p_{n}) = (p_{n})_{n∈ℤ} and (q_{n}) = (q_{n})_{n∈ℤ} be two distributions. We shall say that (p_{n}) is more concentrated than (q_{n}) if, for all k ≥ 0, we have

∑_{|n|≤k} p_{n} ≥ ∑_{|n|≤k} q_{n}.  (128)

We shall write (p_{n}) ≥ (q_{n}) to indicate that (p_{n}) is more concentrated than (q_{n}).

If P = (p_{n})_{n∈ℤ} and Q = (q_{n})_{n∈ℤ} are two distributions, we write P + Q for the distribution (s_{n})_{n∈ℤ} given by the convolution of (p_{n}) and (q_{n}), that is, s_{n} = ∑_{k∈ℤ} p_{k}q_{n−k}. Clearly,

(‡) if X is an integer-valued random variable with distribution P and Y is an integer-valued random variable with distribution Q, then X +Y has distribution P + Q.

In what follows, we shall have integer-valued random variables that have parity, that is, they will take even values or odd values only. For such random variables, we need to change the notion of monotonicity introduced above. We shall say that the distribution (p_{n}) of a random variable that has parity is monotone if p_{n} ≥ p_{n+2} for all n ≥ 0. The notions of symmetry and concentration do not need to be changed.

Lemma 21. (i) Let P = (p_{n})_{n∈ℤ}, Q = (q_{n})_{n∈ℤ}, and R = (r_{n})_{n∈ℤ} be monotone and symmetric distributions with Q ≥ R. Then P + Q and P + R are monotone and symmetric and, moreover, P + Q ≥ P + R.

(ii) Suppose now that P, Q, and R have parity, are monotone and symmetric, and Q ≥ R. Then P + Q and P + R have parity, are monotone and symmetric, and P + Q ≥ P + R.

Proof. We shall consider (i) first. Let P + Q = (s_{n})_{n∈ℤ}. Then, using that P and Q are symmetric, for any n we have s_{−n} = ∑_{k∈ℤ} p_{k}q_{−n−k} = ∑_{k∈ℤ} p_{−k}q_{n+k} = ∑_{k∈ℤ} p_{k}q_{n−k} = s_{n}, and hence (s_{n}) is symmetric. Now let n ∈ ℤ be fixed. We have

s_{n} = p_{0}q_{n} + ∑_{k=1}^{∞}(p_{k}q_{n−k} + p_{−k}q_{n+k})

= p_{0}q_{n} + ∑_{k=1}^{∞} p_{k}(q_{n−k} + q_{n+k}) = ∑_{k=0}^{∞}(p_{k} − p_{k+1}) ∑_{j=−k}^{k} q_{n+j}. (129)

Since P is monotone, we have p_{k}−p_{k+1} ≥ 0 for all k ≥ 0; since Q is monotone and symmetric, we have q_{n−k} ≥ q_{n+1+k} for all n ≥ 0 and all k ≥ 0, which is equivalent to ∑_{j=−k}^{k} q_{n+j} ≥ ∑_{j=−k}^{k} q_{n+1+j}. It follows that, for all n ≥ 0, we have

s_{n} = ∑_{k=0}^{∞}(p_{k}−p_{k+1}) ∑_{j=−k}^{k} q_{n+j} ≥ ∑_{k=0}^{∞}(p_{k}−p_{k+1}) ∑_{j=−k}^{k} q_{n+1+j} = s_{n+1}, (130)

and hence (s_{n}) is also monotone.

Now recall that R = (r_{n}) and let P + R = (s̃_{n})_{n∈ℤ}. Observe that, for all ℓ and k, the sum ∑_{n=−ℓ}^{ℓ} ∑_{j=−k}^{k} q_{n+j} may be written as a linear combination of terms of the form ∑_{i=−m}^{m} q_{i}, with non-negative coefficients (this may be checked by induction on min{ℓ, k}). This observation and the fact that Q ≥ R let us deduce from (129) that

∑_{n=−ℓ}^{ℓ} s_{n} = ∑_{k=0}^{∞}(p_{k} − p_{k+1}) ∑_{n=−ℓ}^{ℓ} ∑_{j=−k}^{k} q_{n+j}

≥ ∑_{k=0}^{∞}(p_{k} − p_{k+1}) ∑_{n=−ℓ}^{ℓ} ∑_{j=−k}^{k} r_{n+j} = ∑_{n=−ℓ}^{ℓ} s̃_{n}, (131)

and hence P + Q ≥ P + R, as required.

We now turn to (ii) (we shall be somewhat sketchy now). Suppose that P, Q, and R have parity, are monotone and symmetric, and Q ≥ R. The fact that P + Q and P + R have parity follows easily from (‡). The symmetry of the distributions P + Q and P + R follows easily from the symmetry of P, Q, and R, as in (i). It remains to consider monotonicity and concentration.

We need the following variants of (129). Suppose first that P is a distribution supported on the even integers. If n has the parity of Q (that is, Q is supported on the integers with the same parity as n), then

s_{n} = ∑_{k=0}^{∞}(p_{2k} − p_{2k+2}) ∑_{j=−k}^{k} q_{n+2j}.  (132)

If n does not have the parity of Q_{n}, then s_{n} = 0. Now suppose that P is a distribution supported on the odd integers. If n has the parity of Q, then s_{n} = 0. On the other hand, if n does not have the parity of Q, then

s_{n} = ∑_{k=1}^{∞}(p_{2k−1} − p_{2k+1}) ∑_{j=1}^{k}(q_{n−(2j−1)} + q_{n+(2j−1)}).  (133)

The monotonicity of P + Q follows from (132) and (133), as in (i), and, of course, the monotonicity of P + R follows similarly. The fact that P + Q ≥ P + R follows from (132) and (133), as in (i) above. □

We shall now discuss a consequence of Lemma 21 that will be needed later. Let

A_{1}, B_{1}, …, A_{k}, B_{k}, C  (134)

be pairwise disjoint subsets of [n] = {1, …, n}. Let (e_{i})_{i∈[n]} ∈ {−1, 1}^{n} be given, and write Â_{j}, B̂_{j}, and Ĉ for the sum of the e_{i} over the respective sets; e.g.,

Â_{j} = ∑_{i∈A_{j}} e_{i}  (135)

for all 1 ≤ j ≤ k. In what follows, we suppose that (e_{i})_{i∈[n]} ∈ {−1, 1}^{n} is chosen uniformly at random. Note that, then, the random variables Â_{j} have parity |A_{j}| mod 2, and have distributions that are symmetric and monotone, and similarly for B̂_{j} and Ĉ. We are interested in the following consequence of Lemma 21.

Corollary 22. For all r, s_{1}, …, s_{k} ≥ 0, we have

ℙ(|Â_{1} + ⋯ + Â_{k} + Ĉ| ≤ r | |Â_{j} + B̂_{j}| ≤ s_{j} all 1 ≤ j ≤ k)

≥ ℙ(|Â_{1} + ⋯ + Â_{k} + Ĉ| ≤ r). (136)

Proof. Let P^{(j)} = (p_{n}^{(j)}) be the distribution of Â_{j} conditioned on |Â_{j} +B̂_{j}| ≤ s_{j}. Let P̃^{(j)} be the (unconditional) distribution of Â_{j}.

Claim 23. The distributions P^{(j)} and P̃^{(j)} have parity |A_{j}| mod 2 and are symmetric and monotone. Moreover, P^{(j)} ≥ P̃^{(j)}.

Let us postpone the proof of Claim 23. To prove (136), it suffices to apply Lemma 21 to conclude that

P^{(1)} + ⋯ + P^{(k)} + Q ≥ P̃^{(1)} + ⋯ + P̃^{(k)} + Q,  (137)

where Q is the distribution of Ĉ. □

We now prove Claim 23.

Proof of Claim 23. Let A = A_{j} and B = B_{j}. We shall first prove that P^{(j)} ≥ P̃^{(j)}. We start by observing that

ℙ(|Â + B̂| ≤ k | Â = ℓ)  (ℓ ≡ |A| mod 2, |ℓ| ≤ |A|)  (138)

is monotone decreasing in |ℓ|. Here and in what follows we shall tacitly suppose that ℓ ‘has the right parity’ (that is, ℓ ≡ |A| mod 2) and |ℓ| ≤ |A|. To see that (138) is decreasing in ℓ ≡ |A| mod 2, it suffices to note that the quantity in (138) is equal to ∑_{n=−ℓ−k}^{−ℓ+k} ℙ(B̂ = n) and to recall that the distribution of B̂ is monotone.

We now show that

ℙ(|Â + B̂| ≤ k | |Â| ≤ r) ≥ ℙ(|Â + B̂| ≤ k).  (139)

To prove (139), we first notice that the left-hand side of (139) is

ℙ(|Â + B̂| ≤ k | |Â| ≤ r) = ℙ(|Â + B̂| ≤ k and |Â| ≤ r)/ℙ(|Â| ≤ r)

= ℙ(|Â| ≤ r)^{−1} ∑_{ℓ=−r}^{r} ℙ(|Â + B̂| ≤ k and Â = ℓ)

= ∑_{ℓ=−r}^{r} ℙ(|Â + B̂| ≤ k | Â = ℓ)\frac{ℙ(Â = ℓ)}{ℙ(|Â| ≤ r)}, (140)

and the right-hand side of (139) is

ℙ(|Â + B̂| ≤ k) = ∑_{ℓ∈ℤ}ℙ(|Â + B̂| ≤ k | Â = ℓ)ℙ(Â = ℓ).  (141)

From (140) and (141) we see that the left-hand side of (139) is a weighted average of the ℙ(|Â + B̂| ≤ k | Â = ℓ) with −r ≤ ℓ ≤ r with weights ℙ(Â = ℓ)/ℙ(|Â| ≤ r), whereas the right-hand side of (139) is a weighted average of the ℙ(|Â + B̂| ≤ k | Â = ℓ) over all ℓ with weights ℙ(|Â| = ℓ).

Now notice that the fact that (138) is monotone decreasing in |ℓ| implies that, for all ℓ_{2} ∈ ℤ \ [−r, r] and all ℓ_{1} ∈ [−r, r] ∩ ℤ with ℓ_{1} ≡ ℓ_{2} ≡ |A| mod 2, we have

ℙ(|Â + B̂| ≤ k | |Â| = ℓ_{2}) ≤ ℙ(|Â + B̂| ≤ k | |Â| = ℓ_{1}).  (142)

Inequality (139) follows from (140), (141), and (142).

Inequality (139) is equivalent to

ℙ(|Â + B̂| ≤ k and |Â| ≤ r)/ℙ(|Â| ≤ r) ≥ ℙ(|Â + B̂| ≤ k).  (143)

It follows from (143) that

ℙ(|Â| ≤ r | |Â + B̂| ≤ k)

= ℙ(|Â + B̂| ≤ k and |Â| ≤ r)/ℙ(|Â + B̂| ≤ k) ≥ ℙ(|Â| ≤ r), (144)

and hence P^{(j)} ≥ P̃^{(j)} does indeed hold.

It remains to show that the distribution of Â conditioned on |Â + B̂| ≤ r is symmetric and monotone. The fact that this distribution is symmetric is immediate. To see that this distribution is monotone, note that ℙ(|Â| = ℓ + 2) ≤ ℙ(|Â| = ℓ) for all ℓ ≥ 0 and recall that ℙ(|Â + B̂| ≤ r | |Â| = ℓ + 2) ≤ ℙ(|Â+ B̂| ≤ r | |Â| = ℓ) for all ℓ ≥ 0 (recall that (138) is decreasing in |ℓ| ≡ |A| mod 2). It follows that

ℙ(|Â| = ℓ + 2 | |Â + B̂| ≤ r)

= ℙ(|Â + B̂| ≤ r | |Â| = ℓ + 2)\frac{ℙ(|Â| = ℓ + 2)}{ℙ(|Â + B̂| ≤ r)}

≤ ℙ(|Â + B̂| ≤ r | |Â| = ℓ)\frac{ℙ(|Â| = ℓ)}{ℙ(|Â + B̂| ≤ r)}

= ℙ(|Â| = ℓ | |Â + B̂| ≤ r),  (145)

as required. □

3.1.2. Proof of Theorem 5. We are now ready to prove Theorem 5. The reader may find it useful to recall the proof of Theorem 1, given in Section 2.2. For convenience, let us fix the following notation: given E_{N} = (e_{1}, …, e_{N}) ∈ {−1, 1}^{N} and Q ⊂ [1, N] ∩ ℤ, we let

U(E_{N}; Q) = ∑_{q∈Q} e_{q}.  (146)

In what follows, Q will usually be an arithmetic progression.

Let us now start the proof of Theorem 5 proper. Let δ > 0 be given. To define the constant c(δ) > 0 as promised in Theorem 5, we define some auxiliary constants. Let us first fix a constant C(δ) ≥ 2 for which we have

40e^{−C(δ)^{2}/4} ≤ \frac{1}{3}.  (147)

Let ℓ(δ) be the smallest integer for which we have

2C(δ) ∑_{ℓ>ℓ(δ)} ℓ2^{−ℓ/2} ≤ \frac{1}{2}δ.  (148)

We now let b(δ) be the smallest integer such that

2^{ℓ(δ)+2} ∑_{b>b(δ)} be^{−\sqrt{b}/4} ≤ \frac{1}{3}  (149)

and

\frac{8}{b(δ)^{1/4}} ≤ \frac{1}{2}δ.  (150)

Unfortunately, it will still take a little while for us to deliver c(δ) (see (163)).

We consider the case N = 2^{k} (the case 2^{k−1} < N ≤ 2^{k} is similar). As in Section 2.2, for all 0 ≤ r ≤ k and 0 ≤ m < 2^{k−r}, we consider the blocks B_{m,r} = (m2^{r}, (m+1)2^{r}]∩ℤ ⊂ [1, N] defined in (41). In what follows, we shall always have the relation

ℓ = k − r.  (151)

(Later on in this proof we shall focus on “large blocks”, for which k and r differ by a constant that depends only on δ, and hence it will be convenient to consider the “gap” ℓ = k − r.) We also set

r_{0} = k − ℓ(δ) and T = T (δ) = b(δ)!.  (152)

Let us now consider the partition

[1, N] ∩ ℤ = ⋃_{0≤m<2^{ℓ(δ)}} B_{m,r_{0}}  (153)

of [1, N] ∩ ℤ. For all 0 ≤ m < 2^{ℓ(δ)} and all 0 ≤ a < T, let

P (m, a) = {x ∈ B_{m,r_{0}} : x ≡ a (mod T)}.  (154)

The progressions P (m, a) then partition B_{m,r_{0}}:

B_{m,r_{0}} = ⋃_{0≤a<T} P (m, a).  (155)

Also, putting together (153) and (155), we have a partition of [1, N]∩ℤ into the progressions P (m, a):

[1, N] ∩ ℤ = ⋃_{m} ⋃_{a} P (m, a),  (156)

where

0 ≤ m < 2^{ℓ(δ)} and 0 ≤ a < T = T (δ).  (157)

Clearly, the number of P (m, a) is 2^{ℓ(δ)}T (δ). Given m and a as in (157), we define G(m, a) to be the event

G(m, a) = \{|U(E_{N}; P (m, a))| ≤ \frac{δ}{2^{ℓ(δ)+1}T (δ)}\sqrt{N}\}  (158)

and let

G = ⋂_{m,a} G(m, a),  (159)

where m and a range over all values in (157). (As the reader may have already guessed, the event in (159) is a “good” event, and hence the notation.) Let

η̃_{m}(δ) = min_{0≤a<T} ℙ(G(m, a)).  (160)

Note first that the right-hand side of (160) is independent of m and hence we may simply write η̃(δ) for η̃_{m}(δ). A simple but crucial observation is that η̃(δ) is bounded away from 0 (as N → ∞), as is

η(δ) = η̃(δ)^{2^{ℓ(δ)}T (δ)}.  (161)

Note that

ℙ(G) ≥ η(δ).  (162)

We finally set

c = c(δ) = \frac{1}{4} lim inf_{N→∞} η(δ) > 0.  (163)

We claim that the choice of c = c(δ) in (163) will do in Theorem 5. More precisely, we make the following claim.

Claim 24. We have

ℙ(W (E_{N}) ≤ δ\sqrt{N}) ≥ \frac{1}{3}η(δ).  (164)

We verify Claim 24 in the remainder of this proof. Let us say that a block B_{m,r} is large if |B_{m,r}| = 2^{r} ≥ 2^{r_{0}}. Following the convention in (151) and recalling the definition of r_{0} (see (152)), we see that B_{m,r} is large if and only if ℓ = k − r ≤ ℓ(δ). We shall also say that B_{m,r} is small if it is not large, that is, if |B_{m,r}| = 2^{r} < 2^{r_{0}}, or, equivalently, if ℓ = k − r > ℓ(δ).

Let us now define two “bad” events F_{1} and F_{2}. To define F_{1}, we adapt a definition used in Section 2.2; an arithmetic progression contained in B_{m,r} will be called complete if it cannot be extended within B_{m,r} keeping the same common difference. We shall say that F_{1} occurs if for some small block B_{m,r} and some complete arithmetic progression Q contained in B_{m,r} we have

|U(E_{N}; Q)| > C(δ)(k − r)\sqrt{2^{r}}.  (165)

We shall say that F_{2} occurs if for some large block B_{m,r} and some complete arithmetic progression Q contained in B_{m,r} with difference b > b(δ) we have

|U(E_{N}; Q)| > 2^{−ℓ/2}b^{−1/4}\sqrt{N}.  (166)

With the definitions of F_{1} and F_{2} at hand, we may state two auxiliary results that will complete the proof of Theorem 5.

Claim 25. If E_{N} ∈ G \ (F_{1} ∪ F_{2}), then

W (E_{N}) ≤ δ\sqrt{N}.  (167)

Claim 26. We have

ℙ(G \ (F_{1} ∪ F_{2})) ≥ \frac{1}{3}η(δ).  (168)

Clearly, Claims 25 and 26 imply Claim 24 and hence our proof is reduced to verifying those two claims.

Proof of Claim 25. Fix E_{N} ∈ G \ (F_{1} ∪ F_{2}) and fix an arithmetic progression Q ⊂ [1, N] ∩ ℤ; say,

Q = {a + jb: 1 ≤ j ≤ M}.  (169)

We wish to show that |U(E_{N}; Q)| ≤ δ\sqrt{N}. Let us decompose [a + b, a + Mb]∩ℤ into blocks B_{m,r} as in Fact 13, that is, using at most two blocks B_{m,r} with the same r for any r:

[a + b, a + Mb] ∩ ℤ = ⋃_{B} B_{m,r},  (170)

where B in (170) simply denotes the family of blocks used in our special decomposition. Put

B_{S} = {B_{m,r} ∈ B: B_{m,r} is small}  (171)

and

B_{L} = {B_{m,r} ∈ B: B_{m,r} is large}.  (172)

Intersecting the progression Q with the B_{m,r} ∈ B, we obtain complete arithmetic progressions

Q_{m,r} = Q ∩ B_{m,r}  (173)

partitioning Q, that is, such that Q = ⋃ Q_{m,r}. We have

|U(E_{N}; Q)| ≤ Σ_{1} + Σ_{2},  (174)

where

Σ_{1} = | ∑_{B_{m,r}∈B_{S}} U(E_{N}; Q_{m,r})|  (175)

and

Σ_{2} = | ∑_{B_{m,r}∈B_{L}} U(E_{N}; Q_{m,r})|.  (176)

We claim that

Σ_{i} ≤ \frac{1}{2}δ\sqrt{N}  (177)

for both i = 1 and 2. Let us verify (177) for i = 1 first. Since E_{N} ∉ F_{1}, we know that (165) fails for all small blocks B_{m,r}; in particular, for all B_{m,r} ∈ B_{S}, we have

|U(E_{N}; Q_{m,r})| ≤ C(δ)(k − r)\sqrt{2^{r}}.  (178)

Therefore, we have

Σ_{1} ≤ ∑_{B_{m,r}∈B_{S}} C(δ)(k − r)\sqrt{2^{r}} ≤ 2 ∑_{0≤r<r_{0}} C(δ)(k − r)\sqrt{2^{r−k}}\sqrt{2^{k}}

≤ 2 ∑_{ℓ>ℓ(δ)} C(δ)ℓ2^{−ℓ/2}\sqrt{N} ≤ \frac{1}{2}δ\sqrt{N}, (179)

where in (179) above we used the inequality in (148) and the convention in (151).

We now prove (177) for i = 2. We shall consider two cases. Case 1. b > b(δ) Since E_{N} ∉ F_{2}, for any B_{m,r} ∈ B_{L}, we have, in this case,

|U(E_{N}; Q_{m,r})| ≤ 2^{−ℓ/2}b^{−1/4}\sqrt{N}  (180)

(see (166)). Therefore, recalling (150) and (151), we have

Σ_{2} ≤ ∑_{B_{m,r}∈B_{L}} 2^{−ℓ/2}b^{−1/4}\sqrt{N} ≤ 2 ∑_{r_{0}≤r≤k} 2^{−ℓ/2}b^{−1/4}\sqrt{N}

= 2 ∑_{0≤ℓ≤ℓ(δ)} 2^{−ℓ/2}b^{−1/4}\sqrt{N} ≤ \frac{8}{b^{1/4}} \sqrt{N} ≤ \frac{1}{2}δ\sqrt{N}, (181)

and the proof of (177) for i = 2 is complete in this case.

Case 2. b ≤ b(δ)

Set Q_{L} = ⋃ Q_{m,r}, with the union ranging over all pairs (m, r) with B_{m,r} ∈ B_{L}. Since b ≤ b(δ), we have that b divides T = T (δ) = b(δ)!. It therefore follows that we have a partition

Q_{L} = ⋃_{(m,a)∈I} P (m, a)  (182)

of Q_{L} into some P (m, a), where I is some index set. Then

Σ_{2} ≤ ∑_{(m,a)∈I} |U(E_{N}; P (m, a))|,  (183)

and, using that E_{N} ∈ G and recalling that there are 2^{ℓ(δ)}T (δ) progressions P (m, a) in total (see (156) and (157)), we have

Σ_{2} ≤ ∑_{(m,a)∈I} \frac{δ}{2^{ℓ(δ)+1}T (δ)}\sqrt{N} ≤ \frac{1}{2}δ\sqrt{N},  (184)

which verifies (177) for i = 2 in this case.

Claim 25 follows from (174) and (177) for i = 1 and 2. □

Proof of Claim 26. We aim at bounding ℙ(G \(F_{1} ∪F_{2})) from below. Let us first bound ℙ(F_{1}) and ℙ(F_{2}) from above. We first consider F_{1}. Calculations similar to the ones leading to (*) in the proof of Lemma 12 show that

ℙ(F_{1}) ≤ 40e^{−C(δ)^{2}/4} ≤ \frac{1}{3}.  (185)

Now consider F_{2}. Fix B_{m,r} and Q as in the definition of F_{2}. Using Fact 9, we obtain that

ℙ(|U(E_{N}; Q)| > 2^{−ℓ/2}b^{−1/4}\sqrt{N}) < 2 exp (−2^{−ℓ}b^{−1/2}N/2|Q|)

≤ 2 exp (−2^{−ℓ}b^{−1/2}N/4(2^{r}/b)) = 2e^{−\sqrt{b}/4}. (186)

Summing the bound in (186) over all choices of B_{m,r} and Q and using (149), we have

ℙ(F_{2}) ≤ 2 ∑_{0≤ℓ≤ℓ(δ)} 2^{ℓ} ∑_{b(δ)<b≤2^{r}} be^{−\sqrt{b}/4} ≤ 2^{ℓ(δ)+2} ∑_{b>b(δ)} be^{−\sqrt{b}/4} ≤ \frac{1}{3}. (187)

Unfortunately, the bounds in (185) and (187) are not quite enough to complete the proof, as G is an event of rather small probability—indeed, those bounds do not even guarantee that G \ (F_{1} ∪ F_{2}) ≠ ∅. We thus refine our argument, and give upper estimates for the conditional probabilities ℙ(F_{1} | G) and ℙ(F_{2} | G). To obtain those estimates, we make use of Corollary 22.

Note that, to obtain the estimates (185) and (187), we used the so called union bound: ℙ(A) ≤ ∑_{λ∈Λ} ℙ(A_{λ}) if A ⊂ ⋃_{λ∈Λ} A_{λ}. Of course, we may also consider this bound conditioning on G: ℙ(A | G) ≤ ∑_{λ∈Λ} ℙ(A_{λ} | G). If we repeat the arguments given above for (185) and (187), but conditioning on G, we have to bound probabilities of the form ℙ(|U(E_{N}; Q)| > t | G)

(for instance, see (186) and (187)). However, a little meditation reveals that Corollary 22 implies that, for any t, we have

ℙ(|U(E_{N}; Q)| > t | G) ≤ ℙ(|U(E_{N}; Q)| > t).  (188)

In particular, the inequalities used to obtain the bounds for ℙ(F_{1}) and ℙ(F_{2}) above would equally hold for ℙ(F_{1} | G) and ℙ(F_{2} | G). Therefore, we have

ℙ(F_{1} | G) ≤ \frac{1}{3} and ℙ(F_{2} | G) ≤ \frac{1}{3},  (189)

and hence

ℙ(F_{1} ∪ F_{2} | G) ≤ \frac{2}{3}.  (190)

Thus

\frac{ℙ(G \ (F_{1} ∪ F_{2}))}{ℙ(G)} = ℙ(G \ (F_{1} ∪ F_{2}) | G) ≥ \frac{1}{3},  (191)

whence, by (162),

ℙ(G \ (F_{1} ∪ F_{2})) ≥ \frac{1}{3}ℙ(G) ≥ \frac{1}{3}η(δ),  (192)

as required. □

As observed before, Claims 25 and 26 imply Claim 24, and the proof of Theorem 5 is complete.

3.2. The probability of having N (E_{N}) small. Our aim in this section is to prove Theorem 6, which gives a lower estimate for the probability that N (E_{N}) should be small. Our argument here will be based on the arguments used in the proof of Theorem 4, but an additional idea will be crucial. In what follows, we shall be sketchy in parts.

Let us start with some variants of some results given in Section 2.4. The following is a simple variant of Lemma 20.

Lemma 27. Let m and r be fixed non-negative integers with B_{m,r} ⊂ [1, N]. For all D > 0, the probability that there is X ∈ {−1, 1}^{k} with k ≤ log_{2} N and k ≤ r satisfying (105) such that

|T (E_{N}, B_{m,r}, X) − 2^{r−k}| > D2^{−k/4}\sqrt{2^{r}}  (193)

is at most

O (e^{−D^{2}/18}) + 2(log_{2} N)^{2}N exp (−\frac{3D}{4 log_{2} N} 2^{r/4}) .  (194)

Remark 28. If k > r, then 2^{r−k} < 1, and hence, using the above estimate for k = r, we get that the probability that

|T (E_{N}, B_{m,r}, X) − 2^{r−k}| > D2^{r/4} + 1  (195)

for some X ∈ {−1, 1}^{k} is at most as given in (194).

Again, for simplicity, we shall assume that N = 2^{K}. In this proof, a block B_{m,r} is large if

r ≥ 8 log_{2} log_{2} N  (196)

and is small otherwise. As in the proof of Theorem 4, we may and shall assume that (***) for all integers m, r, and k ≤ log_{2} N with B_{m,r} ⊂ [1, N] and r ≥

8 log_{2} log_{2} N satisfying (105) and every X ∈ {−1, 1}^{k}, we have the following: if k ≤ r, then

|T (E_{N}, B_{m,r}, X) − 2^{r−k}| ≤ C2^{−k/4}(K − r)\sqrt{2^{r}},

and if k > r, then

|T (E_{N}, B_{m,r}, X) − 2^{r−k}| ≤ C(K − r)2^{r/4} + 1.

To see that (***) does hold with probability approaching 1 as C → ∞, we follow the argument given in the proof of Theorem 4 (see (113)), but using Lemma 27 and Remark 28 instead of Lemma 20. In the proof of Theorem 4, the relevant probability was shown to be O (e^{−2C^{2}/9}); repeating the same calculations with the bounds in Lemma 27 and Remark 28, one obtains O (e^{−C^{2}/18}).

We now point out another fact that may be read out from calculations we have already seen. Making use of (***) instead of (**), the calculations in (117) show that, for any ℓ ≥ 1, the contribution of blocks of cardinality ≤ 2^{K−ℓ} to the discrepancy |T (E_{N}, M, X) − M2^{−k}| is

O (C2^{K/2}ℓ2^{−ℓ/2}) + O ((log_{2} log_{2} N)(log_{2} N)^{8}) .  (197)

This observation shows that

(‡) the contribution of the blocks B_{m,r} with r ≤ K − ℓ_{0} to the estimate in (117) is, say, ≤ (δ/2)\sqrt{N} if ℓ_{0} = ℓ_{0}(δ) is some large enough constant that depends only on δ.

Having cleared some of the pre-requisites, we start the proof of Theorem 6.

Proof of Theorem 6. Let δ > 0 be given. We let k_{0} = k_{0}(δ) be a suitably large integer constant that depends only on δ, for the inequalities below to hold. We wish to show that (14) holds for some suitably small positive constant c(δ).

Fix k ≤ log_{2} N and M with 1 ≤ M ≤ N − k + 1. As before, write [1, M] as a disjoint union of blocks B_{m,r} (r ≤ log_{2} M ≤ K) with at most one block of the form B_{m,r} for each r. Let us write I for the set of the pairs (m, r) for which B_{m,r} occurs in this decomposition of [1, M]. Furthermore, let I = I_{+} ∪ I_{−} be the partition of I with

I_{+} = {(m, r) ∈ I: r satisfies (196)}.  (198)

For later reference, observe that

|I_{−}| < 8 log_{2} log_{2} N.  (199)

Observe also that if (m, r) ∈ I_{−}, then

|T (E_{N}, B_{m,r}, X) − 2^{r−k}| ≤ 2^{r} < (log_{2} N)^{8}  (200)

for any X ∈ {−1, 1}^{k}.

Let us now fix X ∈ {−1, 1}^{k}. We wish to estimate |T (E_{N}, M, X)−M2^{−k}|. As in (117), we start with

|T (E_{N}, M, X) − M2^{−k}| ≤ ∑_{(m,r)∈I} |T (E_{N}, B_{m,r}, X) − 2^{r−k}|

= ∑_{(m,r)∈I_{+}} |T (E_{N}, B_{m,r}, X) − 2^{r−k}| + ∑_{(m,r)∈I_{−}} |T (E_{N}, B_{m,r}, X) − 2^{r−k}| . (201)

Because of (199) and (200), the last sum in (201) is o(\sqrt{N}), and hence we may ignore it. We thus focus on the sum over the pairs (m, r) ∈ I_{+}, that is, we consider the contribution of the large blocks B_{m,r} (i.e., blocks with r ≥ 8 log_{2} log_{2} N). Case 1. k ≥ k_{0} = k_{0}(δ) We shall be able to dispose of this case by invoking some observations that we have already discussed. Let us start by observing that

∑_{(m,r)∈I_{+}} |T (E_{N}, B_{m,r}, X) − 2^{r−k}|

= ∑_{1} |T (E_{N}, B_{m,r}, X) − 2^{r−k}|

+ ∑_{2} |T (E_{N}, B_{m,r}, X) − 2^{r−k}| , (202)

where ∑_{1} indicates sum over all pairs (m, r) ∈ I_{+} with r < k and ∑_{2} indicates sum over all pairs (m, r) ∈ I_{+} with r ≥ k. Making use of (***), one may check that calculations very similar to the ones in (117) show that the last but one sum in (202) is O(C2^{K/4}) = o(\sqrt{N}) and the last sum is ≤ (δ/2)\sqrt{N}, as long as k_{0} = k_{0}(δ) is large enough. The proof is therefore complete in this case.

Case 2. k < k_{0} = k_{0}(δ) This case will require considerable more work. Let

r_{0} = K − k_{0}  (203)

and observe that

∑_{(m,r)∈I_{+}} |T (E_{N}, B_{m,r}, X) − 2^{r−k}|

= ∑_{1} |T (E_{N}, B_{m,r}, X) − 2^{r−k}|
+ ∑_{2} |T (E_{N}, B_{m,r}, X) − 2^{r−k}| , (204)

where ∑_{1} indicates sum over all pairs (m, r) ∈ I_{+} with r < r_{0} and ∑_{2} indicates sum over all pairs (m, r) ∈ I_{+} with r ≥ r_{0}.

The estimate of the first sum on the right-hand side of (204) is based on (‡): since in that sum we are considering blocks B_{m,r} with r < r_{0}, according to (‡), that sum is ≤ (δ/2)\sqrt{N}, as long as k_{0} is large enough.

In view of the above discussion, we are left with estimating the last sum in (204). The key fact that we shall use is the following, which deals with blocks B_{m,r_{0}} and sequences X of length k_{0}.

Claim 29. There is a constant c′(δ) > 0 for which the following holds. Let E be the event that, for all m with B_{m,r_{0}} ⊂ [1, N] and max B_{m,r_{0}} = (m + 1)2^{r_{0}} ≤ N − k_{0} + 1 and every X ∈ {−1, 1}^{k_{0}}, we have

|T (E_{N}, B_{m,r_{0}}, X) − 2^{r_{0}−k_{0}} | = O (δ2^{−5k_{0}/2}\sqrt{N}) .  (205)

Then ℙ(E) ≥ c′(δ).

We leave the proof of Claim 29 for later and complete the proof of Theorem 6. Suppose E_{N} is such that (205) does hold for all B_{m,r_{0}} and all X of length k_{0} as specified in the definition of the event E. Observe that, then, for all Y ∈ {−1, 1}^{k} with k ≤ k_{0}, we have

|T (E_{N}, B_{m,r_{0}}, Y) − 2^{r_{0}−k}| = O (δ2^{−3k_{0}/2}\sqrt{N}) .  (206)

Indeed, given a sequence Y of length k ≤ k_{0}, it suffices to consider all 2^{k_{0}−k} ≤ 2^{k_{0}} extensions of Y to sequences X of length k_{0}, with Y a prefix of X, and then apply (205). We therefore assume that (206) does hold for all Y of length k ≤ k_{0}.

Recall that we have to estimate the last sum in (204), where X is a fixed sequence of length k < k_{0}. Note that that sum is at most

∑_{m∈J} |T (E_{N}, B_{m,r_{0}}, X) − 2^{r_{0}−k}| ,  (207)

where the sum ranges over some set J ⊂ [0, 2^{k_{0}}). Clearly, from (206) applied to Y = X, we see that the sum in (207) is O(δ2^{−k_{0}/2}\sqrt{N}) ≤ (δ/3)\sqrt{N}, as long as k_{0} = k_{0}(δ) is large enough, and this completes the proof of this case.

To complete the proof of Theorem 6, we need to prove Claim 29. □

Proof of Claim 29. We shall be somewhat brief in parts of this proof. Let δ > 0 be given. We may suppose that δ is sufficiently small. In this proof, for simplicity, we write k for k_{0} = k_{0}(δ), which is supposed to be a sufficiently large constant for the inequalities below to hold. Recall we assume that N = 2^{K}. We now let M = 2^{K−7k} and consider the distribution of

s(E_{M}) = (\frac{T (E_{M}, M, X) − M2^{−k}}{\sqrt{M}} )_{X∈\{−1,1\}^{k}} ∈ ℝ^{2^{k}},  (208)

with E_{M} chosen from {−1, 1}^{M} uniformly at random. (We remark that it would be more natural to have

\frac{T (E_{M}, M − k + 1, X) − (M − k + 1)2^{−k}}{\sqrt{M − k + 1}}  (209)

as the entries of s(E_{M}), but, for simplicity, we shall use the definition given in (208), and we shall ignore the additive error term, of order O(k/\sqrt{M}), introduced by using M instead of M − k + 1 in (208).)

Let us say that E_{M} ∈ {−1, 1}^{M} is good if

|T (E_{M}, B_{m,r}, X) − 2^{r−ℓ}| ≤ k(K − 7k − r)2^{−ℓ/4}\sqrt{2^{r}}  (210)

for all m and r with B_{m,r} ⊂ [M − ℓ + 1] and r ≥ 8 log log M and all X ∈ {−1, 1}^{ℓ} with ℓ ≤ r and ℓ ≤ log_{2} M. Let G ⊂ {−1, 1}^{M} be the set of good sequences, and let us write G^{c} for the complement of G. We now state the following claim.

Claim 30. We have

ℙ(G^{c}) = O(e^{−k^{2}/18}).  (211)

Claim 30 above follows from calculations similar to the ones that let us assume (***) (see also the proof of Theorem 4).

In what follows, we wish to ignore the sequences E_{M} in G^{c}. The next claim tells us that the sequences in G^{c} do not influence the expectation of s(E_{M}) too much.

Claim 31. For any X ∈ {−1, 1}^{k},

𝔼(|T (E_{M}, M, X) − M2^{−k}|χ_{G^{c}}) = O(\sqrt{M}e^{−k^{2}/18}),  (212)

where χ_{G^{c}} is the characteristic function of G^{c}.

Proof. Fix X ∈ {−1, 1}^{k} and let Y = Y (E_{M}) = |T (E_{M}, M, X) − M2^{−k}|. Note first that Fact 11 tells us that

ℙ(Y ≥ M2^{−k}) ≤ 2e^{−M/2^{k+2}}.  (213)

Since we always have Y ≤ M, we conclude from (213) that, setting A = {E_{M}: Y (E_{M}) ≥ M/2^{k}}. we have

𝔼(Y χ_{A}) = O(Me^{−M/2^{k+2}}) = O(\sqrt{M}e^{−k^{2}/18}).  (214)

We shall make use of (214) in a short while. Let V (E_{M}) be given by

V (E_{M}) = \begin{cases}Y (E_{M}) & if Y > k\sqrt{M/2^{k}} \\ 0 & otherwise. \end{cases}  (215)

Then we have

Y χ_{G^{c}} ≤ k\sqrt{\frac{M}{2^{k}}} χ_{G^{c}} + V,  (216)

whence, recalling (211), we deduce that

𝔼(Y χ_{G^{c}}) ≤ k\sqrt{\frac{M}{2^{k}}} ℙ(χ_{G^{c}}) + 𝔼(V) = k\sqrt{\frac{M}{2^{k}}} O(e^{−k^{2}/18}) + 𝔼(V). (217)

Now let R = k^{−1}\sqrt{M/2^{k}}. Using (214), we see that

𝔼(V) ≤ O(\sqrt{M}e^{−k^{2}/18}) + ∑_{1≤r≤R} ℙ (Y ≥ rk\sqrt{\frac{M}{2^{k}}} ) (r + 1)k\sqrt{\frac{M}{2^{k}}} . (218)

From Fact 11, we obtain

ℙ (Y ≥ rk\sqrt{\frac{M}{2^{k}}} ) ≤ 2e^{−r^{2}k^{2}/4}.  (219)

Putting together (218) and (219), we get

𝔼(V) ≤ O(\sqrt{M}e^{−k^{2}/18}) + 2k\sqrt{\frac{M}{2^{k}}} ∑_{1≤r≤R}(r + 1)e^{−r^{2}k^{2}/4}

= O(\sqrt{M}e^{−k^{2}/18}) + O (k\sqrt{\frac{M}{2^{k}}} e^{−k^{2}/4})  (220)
= O(\sqrt{M}e^{−k^{2}/18}),

as required. □

Note that the vector s(E_{M}) has entries with expectation 0. Combined with Claim 31, this implies that, for any X ∈ {−1, 1}^{k}, the expected value of

\frac{T (E_{M}, M, X) − M2^{−k}}{\sqrt{M}}  (221)

conditioned on E_{M} ∈ G is O(e^{−k^{2}/18}) = o_{δ→0}(δ/64^{k}). In this proof, we write o_{δ→0}(x) for any term y such that y/x → 0 as δ → 0.

For E_{M} ∈ G, we have

s(E_{M}) = (\frac{T (E_{M}, M, X) − M2^{−k}}{\sqrt{M}} )_{X∈\{−1,1\}^{k}}

∈ [−k2^{−k/4}, k2^{−k/4})^{2^{k}} ⊂ [−1, 1)^{2^{k}}. (222)

Let us partition [−1, 1)^{2^{k}} in b = (2 × 64^{k}/δ)^{2^{k}} blocks of side length δ/64^{k} (that is, blocks of the form ∏_{1≤j≤2^{k}}[x_{j}, x_{j} +δ/64^{k}); we may assume without loss of generality that 64^{k}/δ is an integer). Let these blocks be C_{i} (1 ≤ i ≤ b). For each i, let P_{i} ∈ C_{i} be the average of the points s(E_{M}) that belong to C_{i} and are such that E_{M} ∈ G; if s^{−1}(C_{i}) ∩ G = ∅, let P_{i} be the centre of C_{i}. If

q_{i} = ℙ(P ∈ C_{i} | P ∈ G),  (223)

then E = ∑_{i} q_{i}P_{i} is the expectation of s(E_{M}) conditional on E_{M} ∈ G. Recall that all entries of E are o_{δ→0}(δ/64^{k}).

Let

J = \{1 ≤ j ≤ b: q_{j} ≥ \frac{δ}{k64^{k}} (\frac{δ}{64^{k}} )^{2^{k}}\} .  (224)

Then

∑_{j∉J} q_{j}P_{j}  (225)

has all entries that are O(δ/k64^{k}) = o_{δ→0}(δ/64^{k}). Let

Ẽ = ∑_{j∈J} q̃_{j}P_{j},  (226)

where q̃_{j} = q_{j}/ ∑_{i∈J} q_{i}. Then all the entries of Ẽ are o_{δ→0}(δ/64^{k}), because all the entries of E are o_{δ→0}(δ/64^{k}) and

E = ( ∑_{i∈J} q_{i})Ẽ + ∑_{j∉J} q_{j}P_{j}.  (227)

Clearly, Ẽ may be written as a convex combination of the P_{j} ∈ ℝ^{2^{k}} (j ∈ J). Therefore, there are points Q_{j} = P_{i_{j}} (0 ≤ j ≤ 2^{k} and i_{j} ∈ J for all j) and real numbers t_{j} ≥ 0 with ∑_{j=0}^{2^{k}} t_{j} = 1 such that Ẽ = ∑_{j=0}^{2^{k}} t_{j}P_{i_{j}}.

We next approximate the t_{j} by rationals m_{j}/64^{k} in such a way that

|\frac{m_{j}}{64^{k}} − t_{j}| ≤ \frac{1}{64^{k}}  and  ∑_{j=0}^{2^{k}} m_{j} = 64^{k}.  (228)

(We can take m_{j} = ⌊64^{k}t_{j}⌋ if ∑_{i<j} m_{i} ≥ 64^{k} ∑_{i<j} t_{i}) and m_{j} = ⌈64^{k}t_{j}⌉ otherwise.)

We now partition [N] into the 2^{k} blocks B_{m,r_{0}} = B_{m,K−k} (0 ≤ m < 2^{k}) and partition each of these blocks into 64^{k} segments of length M = 2^{K−7k}. We consider E_{N} ∈ {−1, 1}^{N} satisfying certain conditions. We first require that E_{N} should be such that, in each of these segments of length M, we have a good sequence (a sequence in G). Moreover, we require that, in each of the 2^{k} blocks B_{m,r_{0}} of length 2^{r_{0}} = 2^{K−k}, the sequence E_{N} should be composed by 64^{k} consecutive segments of length M in such a way that in the first m_{0} segments we have s(E_{M}) ∈ C_{i_{0}}, in the next m_{1} segments we have s(E_{M}) ∈ C_{i_{1}}, etc. The probability that all these requirements are met is at least

c(δ) = (\frac{1}{2k} (\frac{δ}{64^{k}} )^{2^{k}+1})^{64^{k}×2^{k}} .  (229)

In each of the 2^{k} blocks B_{m,r_{0}} = B_{m,K−k}, we have

T (E_{N}, B_{m,r_{0}}, X) − |B_{m,r_{0}}|2^{−k} = ∑_{i=0}^{2^{k}} m_{i} (T (E_{M}^{(i)}, M, X^{(i)}) − M2^{−k})

= ∑_{j=0}^{2^{k}} m_{j} (Q_{j} + O (\frac{δ}{64^{k}} )) \sqrt{M}

= O (\frac{δ}{64^{k}} ∑_{j=0}^{2^{k}} m_{j}\sqrt{M}) + ∑_{j=0}^{2^{k}} m_{j}Q_{j}\sqrt{M}

= O (δ\sqrt{M}) + ∑_{j=0}^{2^{k}} m_{j}Q_{j}\sqrt{M}

= O (δ\sqrt{M}) + ∑_{j=0}^{2^{k}} (64^{k}t_{j} + O(1)) Q_{j}\sqrt{M}  (230)

= O (δ\sqrt{M}) + O(2^{k}\sqrt{M}) + ∑_{j=0}^{2^{k}} 64^{k}t_{j}Q_{j}\sqrt{M}

= O (2^{k}\sqrt{M}) + O (64^{k} \frac{δ}{64^{k}} \sqrt{M})

= O (2^{k}\sqrt{M}) = O (2^{k}2^{−7k/2}\sqrt{N}) = O (2^{−5k/2}\sqrt{N}) ,

as required. □

Remark 32. We may prove upper bounds for c(δ) in Theorems 5 and 6 as follows. Partition [N] into k intervals, each of length N/k. In each such interval, the probability that the sum exceeds (1/2)\sqrt{N/k} in absolute value is ≥ 1/2, whence it follows that the probability that this event occurs in none of these intervals is ≤ 1/2^{k}. Taking δ = 1/2\sqrt{k}, we obtain c(δ) ≤ (1/2)^{1/4δ^{2}}.

4. Concluding remarks

The upper bounds in Theorems 1 and 4 are best possible in the following sense. Let us consider W (E_{N}). We claim that, for any C > 0, there is ε_{0} > 0 such that

ℙ(W (E_{N}) < C\sqrt{N}) ≤ 1 − ε_{0}  (231)

for all large enough N. Therefore, the fact that the constant 1/δ in the upper bound in Theorem 1 depends on ε cannot be avoided.

Inequality (231) follows simply from Fact 8. Indeed, that result tells us that, for any fixed C > 0, we have

lim_{N→∞} ℙ (| ∑_{1≤j≤N} e_{j}| ≥ C\sqrt{N}) = 2\sqrt{\frac{2}{π}} ∫_{C/2}^{∞} e^{−2x^{2}}dx > 0,  (232)

and this clearly gives (231) for any C for a suitably small but positive ε_{0}.

One may prove similar facts concerning the upper bound in Theorem 4 by considering T (E_{N}, N, (1)), the number of occurrences of 1 in E_{N}. Indeed, it suffices to observe that, for any fixed C > 0, we have

lim_{N→∞} ℙ (|T (E_{N}, N, (1)) − \frac{N}{2} | ≥ C\sqrt{N}) = 2\sqrt{\frac{2}{π}} ∫_{C}^{∞} e^{−2x^{2}}dx > 0 (233)

(we omit the details).

Problem 33. Investigate the existence of the limiting distributions of

\{\frac{W (E_{N})}{\sqrt{N}}\}_{N≥1} and \{\frac{N (E_{N})}{\sqrt{N}}\}_{N≥1}

and

\{\frac{C_{k}(E_{N})}{\sqrt{N log \binom{N}{k}}} \}_{N≥1} .

Investigate these distributions.

It is most likely that all three sequences in Problem 33 have limiting distributions. Note that Theorem 3 tell us that {C_{k}(E_{N})/𝔼(C_{k})}_{N≥1} has a limiting distribution that is concentrated at a point, as long as

k = k(N) ≤ log N − log log N  (234)

(the condition in (234) may probably be weakened).

References

[1] N. Alon, Y. Kohayakawa, C. Mauduit, C. G. Moreira, and V. Rödl, Measures of pseudorandomness for finite sequences: minimal values, Combin. Probab. Comput. 15 (2006), no. 1–2, 1–29. 1.3, 1.3, 1.3

[2] N. Alon and J. H. Spencer, The probabilistic method, second ed., Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience [John Wiley & Sons], New York, 2000, With an appendix on the life and work of Paul Erdős. MR 2003f:60003 2.1

[3] B. Bollobás, Random graphs, Academic Press Inc. [Harcourt Brace Jovanovich Publishers], London, 1985. MR 87f:05152 2.1 [4] J. Cassaigne, C. Mauduit, and A. Sárközy, On finite pseudorandom binary sequences.

VII. The measures of pseudorandomness, Acta Arith. 103 (2002), no. 2, 97–118. MR 2004c:11139 1.2, 1.3

[5] K. L. Chung and P. Erdős, On the application of the Borel-Cantelli lemma, Trans. Amer. Math. Soc. 72 (1952), 179–186. MR 13:567b 2.3.1

[6] P. Erdős and A. Rényi, On Cantor’s series with convergent ∑ 1/q_{n}, Ann. Univ. Sci. Budapest. Eötvös. Sect. Math. 2 (1959), 93–109. MR 23:A3710 2.3.1

[7] P. Erdős and J. Spencer, Probabilistic methods in combinatorics, Academic Press [A subsidiary of Harcourt Brace Jovanovich, Publishers], New York-London, 1974, Probability and Mathematical Statistics, Vol. 17. MR 52 #2895 1.2, 1.2

[8] S. Janson, T. Łuczak, and A. Ruciński, Random graphs, Wiley-Interscience, New York, 2000. MR 2001k:05180 2.1

[9] J. Matoušek and J. Spencer, Discrepancy in arithmetic progressions, J. Amer. Math. Soc. 9 (1996), no. 1, 195–204. MR 96c:11089 1.3

[10] C. Mauduit, Finite and infinite pseudorandom binary words, Theoret. Comput. Sci. 273 (2002), no. 1-2, 249–261, WORDS (Rouen, 1999). MR 2002m:11072 1.1

[11] C. Mauduit and A. Sárközy, On finite pseudorandom binary sequences. I. Measure of pseudorandomness, the Legendre symbol, Acta Arith. 82 (1997), no. 4, 365–377. MR 99g:11095 1.1

[12] C. McDiarmid, On the method of bounded differences, Surveys in combinatorics, 1989 (Norwich, 1989), London Math. Soc. Lecture Note Ser., vol. 141, Cambridge Univ. Press, Cambridge, 1989, pp. 148–188. MR 91e:05077 2.3.2

[13] V. V. Petrov, A note on the Borel-Cantelli lemma, Statist. Probab. Lett. 58 (2002), no. 3, 283–286. MR MR1921874 (2003e:60005) 2.3.1

[14] , A generalization of the Borel-Cantelli lemma, Statist. Probab. Lett. 67 (2004), no. 3, 233–239. MR MR2053525 (2005a:60011) 2.3.1

[15] K. F. Roth, Remark concerning integer sequences, Acta Arith. 9 (1964), 257–260. MR 29 #5806 1.3

Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv 69978, Israel

E-mail address: noga@math.tau.ac.il

Instituto de Matemática e Estatística, Universidade de São Paulo, Rua do Matão 1010, 05508–090 São Paulo, Brazil

E-mail address: yoshi@ime.usp.br

Institut de Mathématiques de Luminy, CNRS-UPR9016, 163 av. de Luminy, case 907, F-13288, Marseille Cedex 9, France

E-mail address: mauduit@iml.univ-mrs.fr

IMPA, Estrada Dona Castorina 110, 22460–320 Rio de Janeiro, RJ, Brazil E-mail address: gugu@impa.br

Department of Mathematics and Computer Science, Emory University, Atlanta, GA 30322, USA

E-mail address: rodl@mathcs.emory.edu