MEASURES OF PSEUDORANDOMNESS FOR FINITE SEQUENCES: MINIMAL VALUES

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

Dedicated to Professor Béla Bollobás on the occasion of his 60th birthday

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’. Two of these parameters are the normality measure N (E_{N}) and the correlation measure C_{k}(E_{N}) of order k, which focus on different combinatorial aspects of E_{N}. In their work, amongst others, Mauduit and Sárközy investigated the minimal possible value of these parameters.

In this paper, we continue the work in this direction and prove a lower bound for the correlation measure C_{k}(E_{N}) (k even) for arbitrary sequences E_{N}, establishing one of their conjectures. We also give an algebraic construction for a sequence E_{N} with small normality measure N (E_{N}).

Contents

1. Introduction and statement of results 2 1.1. Typical and minimal values of correlation 3 1.2. Typical and minimal values of normality 5 2. The minimum of the correlation measure 5 2.1. Auxiliary lemmas from linear algebra 5 2.2. Proof of the lower bounds for correlation 7 2.3. Some further lower bounds for correlation 10 2.4. Bounds from coding theory 15 3. The minimum of the normality measure 15

Date: Copy produced on June 29, 2005.

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 supported by a USA Israeli BSF grant, by a grant from the Israel Science Foundation and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University. The second author was partially supported by FAPESP and CNPq through ProNEx projects (Proc. CNPq 664107/1997–4 and Proc. FAPESP 2003/09925–5) and by CNPq (Proc. 306334/2004–6 and 479882/2004–5). 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 0300529. The authors gratefully acknowledge the support of a CNPq/NSF cooperative grant (910064/99–7, 0072064) and the Brazil/France Agreement in Mathematics (Proc. CNPq 69–0014/01–5 and 69–0140/03–7).

3.1. Remarks on min N (E_{N}) 16 3.2. A sequence E_{N} with small N (E_{N}) 17 3.3. Larger alphabets 26 3.4. The Pólya–Vinogradov inequality 28 Acknowledgements 29 References 29

1. Introduction and statement of results

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] certain ‘measures of pseudorandomness’, to be defined shortly. We restrict ourselves to the Mauduit–Sárközy parameters directly relevant to the present note, and refer the reader to [10] and [11] for detailed discussions concerning the definitions below, related measures, and further related literature.

Let k ∈ ℕ, M ∈ ℕ, and X ∈ {−1, 1}^{k} be given. Also, let D = {d_{1}, …, d_{k}}, where the d_{i} are integers with 1 ≤ d_{1} < ⋯ < d_{k} ≤ N − M + 1. 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)

and

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

= ∑_{0≤n<M} ∏_{1≤i≤k} e_{n+d_{i}} = ∑_{0≤n<M} ∏_{d∈D} e_{n+d}. (2)

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}. On the other hand, one may think of the quantity V (E_{N}, M, D) as 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}} | ,  (3)

where the maxima are taken over all 1 ≤ k ≤ log_{2} N, X ∈ {−1, 1}^{k}, and 0 < M ≤ N + 1 − k. 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 − 1 + d_{k} ≤ N}.

In what follows, we shall sometimes make use of terms commonly used in the area of combinatorics on words. In particular, sequences will sometimes be referred to as words. Moreover, a word u occurs in a word w if w contains u as a ‘contiguous segment’ (that is, w = tuv, where t is a ‘prefix’ of w and v is a ‘suffix’ of w).

In Section 1.1 we shall state and discuss our results concerning the correlation measure C_{k}, while in Section 1.2 we shall state and discuss our results on the normality measure N.

1.1. Typical and minimal values of correlation. In [4], Cassaigne, Mauduit, and Sárközy studied, amongst others, the typical value of C_{k}(E_{N}) for random binary sequences E_{N}, with all the 2^{N} sequences in {−1, 1}^{N} equiprobable, and the minimal possible value for C_{k}(E_{N}). The investigation of the typical value of C_{k}(E_{N}) is continued in [1], where Theorems A and B below are proved. (In what follows, we write log for the natural logarithm.) Theorem A. 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}} (5)

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

Note that Theorem A establishes the typical order of magnitude of C_{k}(E_{N}) for a wide range of k, including values of k proportional to N. The next result tells us that C_{k}(E_{N}) is concentrated in the case in which k is small. Theorem B. For any fixed constant ε > 0 and any integer function k = k(N) with 2 ≤ k ≤ log N − log log N, there is a function Γ(k, N) and a constant N_{0} for which the following holds. If N ≥ N_{0}, then the probability that

1 − ε < \frac{C_{k}(E_{N})}{Γ(k, N)} < 1 + ε  (6)

holds is at least 1 − ε.

Clearly, Theorem A tells us that Γ(k, N) is of order \sqrt{N log \binom{N}{k}}. Let us now turn to the minimal possible value of the parameter C_{k}(E_{N}). In [4], the following result is proved. Theorem C. For all k and N ∈ ℕ with 2 ≤ k ≤ N, we have

(i) min {C_{k}(E_{N}): E_{N} ∈ {−1, 1}^{N}} = 1 if k is odd, (ii) min {C_{k}(E_{N}): E_{N} ∈ {−1, 1}^{N}} ≥ log_{2}(N/k) if k is even.

Theorem C(i) follows simply from the observation that the alternating sequence E_{N} = (1, −1, 1, −1, …) is such that C_{k}(E_{N}) = 1 for odd k. Owing to Theorem C(i), when concerned with minimal values of C_{k}(E_{N}), we are only interested in even k. In [4], it is conjectured that for any even k ≥ 2 there is a constant c > 0 such that for N → ∞ we have

min {C_{k}(E_{N}): E_{N} ∈ {−1, 1}^{N}} ≫ N^{c},  (7)

which would be a considerable strengthening of Theorem C(ii). In this paper, we prove the conjecture above in a more general form. We shall prove the following result.

Theorem 1. If k and N are natural numbers with k even and 2 ≤ k ≤ N, then

C_{k}(E_{N}) > \sqrt{\frac{1}{2} ⌊\frac{N}{k + 1}⌋}  (8)

for any E_{N} ∈ {−1, 1}^{N}.

The lower bound given in (8) decreases as k increases. One may ask whether, in fact, C_{2k}(E_{N}) ≥ c\sqrt{kN} for some absolute constant c > 0, or at least C_{2k}(E_{N}) ≥ c\sqrt{N} for some absolute constant c > 0. The results below (and the results in Section 2.3) are partial answers in this direction.

It turns out that if we look at the maximum of C_{2}(E_{N}), C_{4}(E_{N}), …, C_{k}(E_{N}) (with k again even), then a lower bound of order \sqrt{kN} may indeed be proved.

Theorem 2. There is an absolute constant c > 0 for which the following holds. For any positive integers ℓ and N with ℓ ≤ N/3, we have

max\{C_{2}(E_{N}), C_{4}(E_{N}), …, C_{2ℓ}(E_{N})\} ≥ c\sqrt{ℓN}  (9)

for all E_{N} ∈ {−1, 1}^{N}.

In view of Theorem A, the lower bound in Theorem 2 is best possible apart from a multiplicative factor of O (\sqrt{log(N/2ℓ)}), for all ℓ ≤ N/8.

One may also prove lower bounds of the form c\sqrt{N} for some absolute constant c > 0 if one considers correlations of two consecutive even orders 2k−2 and 2k (with k not too large).

Theorem 3. Let positive integers k and N with 2 ≤ k ≤ \sqrt{N/6} be given. If N is large enough, then

max\{C_{2k−2}(E_{N}), C_{2k}(E_{N})\} ≥ \sqrt{\frac{1}{2} ⌊\frac{N}{3} ⌋}  (10)

for any E_{N} ∈ {−1, 1}^{N}.

Some further results are stated and proved in Section 2.3 (see Theorems 11, 13, and 14).

1.2. Typical and minimal values of normality. We now turn to the normality measure N (E_{N}). In [1], the following result is proved. Theorem D. 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}  (11)

with probability at least 1 − ε.

Here, we shall give an explicit construction for sequences E_{N} ∈ {−1, 1}^{N} with N (E_{N}) small. Theorem D tells us that, typically, N (E_{N}) is of order \sqrt{N}. We shall exhibit a sequence E_{N} with N (E_{N}) = O (N^{1/3}(log N)^{2/3}).

Theorem 4. For any sufficiently large N, there exists a sequence E_{N} ∈ {−1, 1}^{N} with

N (E_{N}) ≤ 3N^{1/3}(log N)^{2/3}.  (12)

A simple argument shows that N (E_{N}) ≥ (1/2+o(1)) log_{2} N for any E_{N} ∈ {−1, 1}^{N} (see Proposition 16 in Section 3.1). In view of Theorem 4, we have

(\frac{1}{2} + o(1)) log_{2} N ≤ min_{E_{N} ∈\{−1,1\}^{N}} N (E_{N}) ≤ 3N^{1/3}(log N)^{2/3}  (13)

for all large enough N. It would be interesting to close the rather wide gap in (13).

The construction of the sequence E_{N} ∈ {−1, 1}^{N} in Theorem 4 may be generalized to larger alphabets Σ, as long as the cardinality of Σ is a power of a prime (see Section 3.3). Finally, we remark that one of the ingredients in the proof of (12) for our sequence E_{N} allows one to give a short proof of the celebrated Pólya–Vinogradov inequality on incomplete character sums (see Section 3.4), which is somewhat simpler than the known proofs.

2. The minimum of the correlation measure

2.1. Auxiliary lemmas from linear algebra. The proof of Theorem 1 that we give in Section 2.2 is based on the following elementary lemma from linear algebra (see, e.g., [2, Lemma 9.1] or [5, Lemma 7]), whose proof we include for completeness.

Lemma 5. For any symmetric matrix A = (A_{ij})_{1≤i,j≤n}, we have

rk(A) ≥ \frac{(tr(A))^{2}}{tr(A^{2})} = \frac{(∑_{1≤i≤n} A_{ii})^{2}}{∑_{1≤i,j≤n} A_{ij}^{2}} .  (14)

Consequently, if A_{ii} = 1 for all i and |A_{ij}| ≤ ε for all i ≠ j, then

rk(A) ≥ \frac{n}{1 + ε^{2}(n − 1)}.  (15)

In particular, if ε = \sqrt{1/n}, then rk(A) ≥ n/2.

Proof. Let r = rk(A). Then A has exactly r non-zero eigenvalues, say, λ_{1}, …, λ_{r}. By the Cauchy–Schwarz inequality, we have

(tr(A))^{2} = (λ_{1} + ⋯ + λ_{r})^{2} ≤ r(λ_{1}^{2} + ⋯ + λ_{r}^{2}) = r tr(A^{2}),

and it now suffices to notice that, because A is symmetric, we have

tr(A^{2}) = ∑_{1≤i≤n} ( ∑_{1≤j≤n} A_{ij}A_{ji}) = ∑_{1≤i,j≤n} A_{ij}^{2},

as required. Inequality (15) follows immediately from (14). □

The next lemma, due to the first author [2], improves Lemma 5 for larger values of ε.

Lemma 6. Let A = (A_{ij})_{1≤i,j≤n} be an n × n real matrix with A_{ii} = 1 for all i and |A_{ij}| ≤ ε for all i ≠ j, where \sqrt{1/n} ≤ ε ≤ 1/2. Then

rk(A) ≥ \frac{1}{100ε^{2} log(1/ε)} log n.  (16)

If A is symmetric, then (16) holds with the constant 1/100 replaced by 1/50.

For completeness, we give the proof of Lemma 6. We shall need the following auxiliary lemma [2].

Lemma 7. Let A = (A_{i,j}) be an n × n matrix of rank d, and let P (x) be an arbitrary polynomial of degree k. Then the rank of the n×n matrix (P (A_{i,j})) is at most \binom{k+d}{k}. Moreover, if P (x) = x^{k}, then the rank of (P (A_{i,j})) = (A_{i,j}^{k}) is at most \binom{k+d−1}{k}.

Proof. Let v_{1} = (v_{1,j})_{j=1}^{n}, v_{2} = (v_{2,j})_{j=1}^{n}, …, v_{d} = (v_{d,j})_{j=1}^{n} be a basis of the row space of A. Then the vectors (v_{1,j}^{k_{1}}v_{2,j}^{k_{2}} ⋯ v_{d,j}^{k_{d}})_{j=1}^{n}, where k_{1}, k_{2}, …, k_{d} range over all non-negative integers whose sum is at most k, span the row space of the matrix (P (A_{i,j})). If P (x) = x^{k}, then it suffices to take all these vectors corresponding to k_{1}, k_{2}, …, k_{d} whose sum is precisely k. □

Proof of Lemma 6. Let us first note that the non-symmetric case follows from the symmetric case: if A is not symmetric, it suffices to consider the symmetric matrix (A^{T} + A)/2, whose rank is at most twice the rank of A. We therefore suppose that A is symmetric, and proceed to prove (16) with the constant 1/100 replaced by 1/50.

Let δ = 1/16. Consider first the case in which ε ≤ 1/n^{δ}. In this case, let m = ⌊1/ε^{2}⌋, and let A′ be the submatrix of A consisting of the, say, first m rows and first m columns of A. By the choice of m, we have that 1/\sqrt{m} ≥ ε, and hence Lemma 5 applies to A′, and we deduce that rk(A) ≥ rk(A′) ≥ m/2. It now suffices to check that, because ε ≤ min{1/2, 1/n^{δ}} and δ = 1/16, we have

\frac{1}{2}m ≥ \frac{3}{8ε^{2}} = \frac{3}{2^{7}δε^{2}} > \frac{1}{50ε^{2} log(1/ε)} log n,  (17)

and we are done in this case. We now suppose that 1/n^{δ} ≤ ε ≤ 1/2. In this case, we let

k = ⌊\frac{log n}{2 log(1/ε)}⌋ ≥ ⌊\frac{1}{2δ} ⌋ = 8,  (18)

and let m = ⌊1/ε^{2k}⌋. Note that, then, we have m ≤ n. We again let A′ be the submatrix of A consisting of the first m rows and first m columns of A. We now have

ε^{k} ≤ \frac{1}{\sqrt{m}}.  (19)

Let A′′ be the matrix obtained from A′ by raising all its entries to the kth power. Because of (19) and the hypothesis on the entries of A, Lemma 5 applies and tells us that

rk(A′′) ≥ \frac{1}{2}m = \frac{1}{2} ⌊\frac{1}{ε^{2k}} ⌋ ≥ \frac{0.49}{ε^{2k}},  (20)

where the last inequality follows easily from the fact that ε ≤ 1/2 and k ≥ 8 (see (18)). We now observe that Lemma 7 tells us that

rk(A′′) ≤ \binom{k + rk(A′)}{k} ≤ (\frac{e(k + rk(A′))}{k})^{k} .  (21)

Putting together (20) and (21), we get

rk(A) ≥ rk(A′) ≥ \frac{k}{ε^{2}} (\frac{0.49^{1/k}}{e} − ε^{2}) ,  (22)

which, because 0.49^{1/8}/e ≥ 1/3 and ε^{2} ≤ 1/4, implies that rk(A) ≥ k/12ε^{2}. Therefore, we have

rk(A) > \frac{1}{50ε^{2} log(1/ε)} log n,  (23)

and we are done. □

2.2. Proof of the lower bounds for correlation. We shall prove Theorem 1 and 2 in this section. These results will be deduced from suitable applications of Lemmas 5 and 6; to describe these applications, we first need to introduce some notation.

Let E_{N} = (e_{i})_{1≤i≤N} ∈ {−1, 1}^{N} be given. Let a positive integer M ≤ N be fixed and set N′ = N −M +1. Moreover, fix a family L of subsets of [N′]. We now define a vector v_{L} = (v_{L,i})_{0≤i<M} ∈ {−1, 1}^{M} for all L ∈ L, letting

v_{L,i} = ∏_{x∈L} e_{i+x}  (24)

for all 0 ≤ i < M (note that 1 ≤ i + x ≤ M − 1 + N′ = N for any x in (24)). Let us now define an L × L matrix A = (A_{L,L′})_{L,L′∈L}, putting

A_{L,L′} = \frac{1}{M} ⟨v_{L}, v_{L′}⟩ = \frac{1}{M} ∑_{0≤i<M} v_{L,i}v_{L′,i}  (25)

for all L, L′ ∈ L. Clearly, the diagonal entries of A are all 1. Suppose now that L ≠ L′. Then

A_{L,L′} = \frac{1}{M} ⟨v_{L}, v_{L′}⟩ = \frac{1}{M} ∑_{0≤i<M} ( ∏_{x∈L} e_{i+x})( ∏_{y∈L′} e_{i+y})

= \frac{1}{M} ∑_{0≤i<M} ∏_{z∈L△L′} e_{i+z}, (26)

where we write L △ L′ for the symmetric difference of the sets L and L′. Let L^{△} = {L △ L′: L, L′ ∈ L, L ≠ L′} and let K be the set of the cardinalities of the members of L^{△}, that is, K = {|S|: S ∈ L^{△}}. It follows from (26) and the definition of C_{k}(E_{N}) that

max{C_{k}(E_{N}): k ∈ K} ≥ M max{|A_{L,L′}|: L, L′ ∈ L, L ≠ L′}.  (27)

Lemma 5 and (27) imply the following result.

Lemma 8. We have

max\{C_{k}(E_{N}): k ∈ K\} > \sqrt{M − \frac{M^{2}}{|L|}} .  (28)

Proof. Let B = (v_{L}^{T})_{L∈L} be the |L| × M matrix with rows v_{L}^{T} (L ∈ L). Observing that A = M^{−1}BB^{T}, we see that A has rank at most M. Combining this with the lower bound for the rank of A given by Lemma 5, we get

M ≥ rk(A) > \frac{|L|}{1 + ε^{2}|L|},  (29)

where ε = max{|A_{L,L′}|: L, L′ ∈ L, L ≠ L′}. It follows from (29) that

ε > \sqrt{\frac{1}{M} − \frac{1}{|L|}}.  (30)

Inequality (28) follows from (27) on multiplying (30) by M. □

We are now ready to prove Theorem 1.

Proof of Theorem 1. Let k, N, and E_{N} be as in the statement of Theorem 1. Set ℓ = k/2 and M = ⌊N/(k + 1)⌋ and, as above, let N′ = N − M + 1. We take for L ⊂ P([N′]) a set system of t = ⌊N′/ℓ⌋ pairwise disjoint ℓ-element subsets L_{1}, …, L_{t} of [N′]. Note that

|L| = t = ⌊\frac{N − ⌊N/(k + 1)⌋ + 1}{k/2}⌋ ≥ ⌊\frac{2N}{k + 1}⌋ ≥ 2M.  (31)

Therefore, it follows from (28) and (31) that

C_{k}(E_{N}) > \sqrt{M − \frac{M^{2}}{|L|}} ≥ \sqrt{M − \frac{M}{2}} = \sqrt{\frac{1}{2} ⌊\frac{N}{k + 1}⌋},  (32)

as required. □

Lemma 8 was deduced from an application of Lemma 5 to the matrix A = (A_{L,L′}); the next lemma will be obtained from an application of Lemma 6 to A.

Lemma 9. If 2M ≤ |L| < e^{50M}, then

max\{C_{k}(E_{N}): k ∈ K\} ≥ min \{\frac{1}{2}M, \sqrt{\frac{1}{50}M(log |L|) /log \frac{50M}{log |L|}} \} . (33)

Proof. Let ε = max{|A_{L,L′}|: L, L′ ∈ L, L ≠ L′}. Inequality (15) and the fact that rk(A) ≤ M, coupled with M ≤ |L|/2, give that

ε^{2} > \frac{1}{M} − \frac{1}{|L|} ≥ \frac{1}{|L|},  (34)

and hence ε > \sqrt{1/|L|}. If ε > 1/2, then (33) follows immediately (recall (27)). Therefore, we may suppose that \sqrt{1/|L|} ≤ ε ≤ 1/2, and hence we may apply Lemma 6 to the symmetric matrix A. Combining the fact that A has rank at most M with Lemma 6, we obtain that

M ≥ rk(A) ≥ \frac{1}{50ε^{2} log(1/ε)} log |L|,  (35)

whence

ε^{2} log \frac{1}{ε} ≥ \frac{1}{50M} log |L|.  (36)

Using that 1/ε ≥ log 1/ε, we have from (36) that

ε ≥ ε^{2} log \frac{1}{ε} ≥ \frac{1}{50M} log |L|.  (37)

Plugging (37) into (36), we get

ε^{2} log \frac{50M}{log |L|} ≥ ε^{2} log \frac{1}{ε} ≥ \frac{1}{50M} log |L|,  (38)

and hence

ε ≥ \sqrt{\frac{log |L|}{50M} /log \frac{50M}{log |L|}} .  (39)

Inequality (33) follows easily from (27), (39), and the definition of ε. □

We shall now deduce Theorem 2 from Lemma 9.

Proof of Theorem 2. Let ℓ and N with ℓ ≤ N/3 be given. Let M = ⌊N/3⌋, and set N′ = N − M + 1 ≥ 2N/3. We take for L the set system of all ℓ-element subsets of [N′]. Then, clearly, L^{△} = {L △ L′: L, L′ ∈ L, L ≠ L′} is the family of non-empty subsets of [N′] of even cardinality not greater than 2ℓ. Hence, K = {|S|: S ∈ L^{△}} = {2, 4, …, 2ℓ}. Moreover,

|L| = \binom{N′}{ℓ} ≥ N′ ≥ \frac{2N}{3} ≥ 2M,  (40)

and, as M = ⌊N/3⌋ ≥ N/5 because N ≥ 3, we have

|L| ≤ 2^{N} = (2^{N/M})^{M} ≤ 2^{5M} < e^{50M}.  (41)

Inequalities (40) and (41) tell us that Lemma 9 may be applied. We deduce from that lemma that

max{C_{2}(E_{N}), C_{4}(E_{N}), …, C_{2ℓ}(E_{N})}

≥ min \{\frac{1}{2}M, \sqrt{\frac{1}{50}M(log |L|) /log \frac{50M}{log |L|}} \} . (42)

If the minimum on the right-hand side of (42) is achieved by M/2 = ⌊N/3⌋/2, then we are already done; suppose therefore that the minimum is given by the other term. Observe that

\frac{1}{50}M(log |L|) /log \frac{50M}{log |L|} ≥ \frac{1}{50} ⌊\frac{N}{3} ⌋ (log |L|) /log \frac{50N/3}{log |L|} ,  (43)

and, moreover,

|L| = \binom{N′}{ℓ} ≥ (\frac{2N}{3ℓ} )^{ℓ} ,  (44)

so that

log |L| ≥ ℓ log \frac{2N}{3ℓ} .  (45)

By (43) and (45), it suffices to show that

\frac{1}{150}Nℓ (log \frac{2N}{3ℓ} ) /log \frac{50N/3}{ℓ log(2N/3ℓ)} ≥ c′Nℓ  (46)

for some absolute constant c′ > 0. Routine calculations show that a suitable constant c′ > 0 will do in (46). We only give a sketch: suppose first that 1 ≤ ℓ = o(N). In this case, it is simple to check that the left-hand side of (46) is in fact

(\frac{1}{150} + o(1)) Nℓ.  (47)

Suppose now that c′′N ≤ ℓ ≤ N/3. In this case, the left-hand side of (46) is at least

\frac{1}{150}Nℓ(log 2) /log \frac{50/3}{c′′ log 2} ,  (48)

and (46) follows for some small enough c′ > 0. □

2.3. Some further lower bounds for correlation. In this section, we deduce some further consequences of Lemmas 8 and 9, using other families L.

2.3.1. Projective plane bounds. We shall prove Theorem 3 (see Section 1.1) by making use of systems of sets derived from projective planes. Recall that Theorem 3 tells us that, for any 2 ≤ k ≤ \sqrt{N/6} and any E_{N} ∈ \{−1, 1\}^{N}, at least one of C_{2k−2}(E_{N}) and C_{2k}(E_{N}) is ≥ c\sqrt{N}, for some absolute constant c > 0. (We shall not try to obtain the best value of c in what follows.) We shall use the following fact.

Lemma 10. Let positive integers k and n with k ≤ (1/2)\sqrt{n} be given. If n is large enough, then there is a family L of k-element subsets of [n] with |L| = n and such that |L ∩ L′| ≤ 1 for all distinct L and L′ ∈ L.

One may prove Lemma 10 by considering suitable projective planes on m points, with m only slightly larger than n: one may first delete m − n points from the plane at random, to obtain a system with n points and ≥ n ‘lines’ of cardinality only slightly smaller than \sqrt{n}, and then one may remove some points from these ‘lines’ to turn them into k-element sets. (The constant 1/2 in the upper bound for k in Lemma 10 may in fact be replaced by any constant < 1.)

Proof of Theorem 3. Let k and N as in the statement of the theorem be given. Let M = ⌊N/3⌋ and

N′ = N − M + 1 ≥ \frac{2}{3}N ≥ 2M.  (49)

Observe that k ≤ \sqrt{N/6} = (1/2)\sqrt{2N/3} ≤ (1/2)\sqrt{N′}. We now use that N is supposed to be large and invoke Lemma 10, to obtain a family L of kelement subsets of [N′] with |L| = N′ and |L∩L′| ≤ 1 for any two distinct L and L′ ∈ L.

By (49), we have

M − \frac{M^{2}}{|L|} ≥ \frac{1}{2}M = \frac{1}{2} ⌊\frac{N}{3} ⌋ .  (50)

Moreover, |L△L′| ∈ {2k−2, 2k} for all distinct L and L′ ∈ L. Inequality (10) follows from (28). □

If a projective plane of order k exists, then one may give a lower bound of order \sqrt{N} for C_{2k}(E_{N}).

Theorem 11. For any constant 1/\sqrt{2} < α < 1, there is a constant c = c(α) > 0 for which the following holds. Given any ε > 0, there is N_{0} such that if N ≥ N_{0} and k is a power of a prime and |k − α\sqrt{N}| ≤ ε\sqrt{N}, then

C_{2k}(E_{N}) ≥ c\sqrt{N}  (51)

for any E_{N} ∈ {−1, 1}^{N}.

Proof. We only give a sketch of the proof. Let k be a large prime power as in the statement of our result, and set

N′ = k^{2} + k + 1 and M = N − N′ + 1.  (52)

Using that k = (α + o(1))\sqrt{N}, we have

N′ = (α^{2} + o(1))N and M = (1 − α^{2} + o(1))N.  (53)

We now use that k is a prime power, and let L be the family of lines of a projective plane with point set [N′]. Clearly, every member of L has k + 1 elements and

|L| = N′ = (α^{2} + o(1))N.  (54)

We shall now apply Lemma 8. By (53), we have

M − \frac{M^{2}}{|L|} = (1 − α^{2} + o(1))N − \frac{(1 − α^{2} + o(1))^{2}N^{2}}{(α^{2} + o(1))N}

= (1 − \frac{1 − α^{2} + o(1)}{α^{2} + o(1)}) (1 − α^{2} + o(1))N

= (1 + o(1)) (2 − \frac{1}{α^{2}} ) (1 − α^{2})N. (55)

Clearly, |L△L′| = 2k for all distinct L and L′ ∈ L. Therefore, inequality (28) in Lemma 8, together with the hypothesis that 1/\sqrt{2} < α < 1, imply the desired result. □

The proof of Theorem 11 above is based on Lemma 8; one may use Lemma 9 instead, which would give a somewhat different value for the constant c in (51). A bound of the form (51) for k of order N may also be proved in the case in which there exists a 4k × 4k Hadamard matrix. Indeed, it suffices to consider such a matrix as the incidence matrix of a system L of 2k-element subsets of a 4k-element set; the system L would then have the property that all pairwise symmetric differences of its members are of cardinality 2k.

The condition that k should be a power of a prime in Theorem 11 may be removed by making use of Vinogradov’s three primes theorem (to be more precise, we use a strengthening of that result). The key observation is the following.

Lemma 12. For any ε > 0, there is an integer k_{0} for which the following holds. If k ≥ k_{0} is an odd integer, then there there is a family L of (k + 3)- element subsets of [n], where |n − k^{2}/3| ≤ εk^{2}, such that ||L| − n/3| ≤ εn and

|L △ L′| = 2k  (56)

for all distinct L and L′ ∈ L. If k ≥ k_{0} is even, then there is a family L of (k+4)-element subsets of [n], where |n−k^{2}/4| ≤ εk^{2}, such that ||L|−n/4| ≤ εn and (56) holds for all distinct L and L′ ∈ L.

Proof. We give a sketch of the proof. Let ε > 0 be fixed and suppose first that k is a large odd integer.

We use a strengthening of Vinogradov’s theorem, according to which any large enough odd integer k may be written as a sum of three primes p_{1}, p_{2}, and p_{3} that satisfy p_{i} = (1/3 + o(1))k, where o(1) → 0 as k → ∞ (an old theorem of Haselgrove [8] implies this result). Let L_{1}, L_{2}, and L_{3} be projective planes of order p_{1}, p_{2}, and p_{3}, respectively, and suppose that p_{1} ≤ p_{2} and p_{3}. We take the L_{i} on pairwise disjoint point sets X_{i} and let X = X_{1} ∪ X_{2} ∪ X_{3}. Clearly, n = |X| = 3(1/3 + o(1))^{2}k^{2} = (1/3 + o(1))k^{2}. Let the lines of L_{i} be L_{1}^{(i)}, ⋯, L_{n_{i}}^{(i)}, where n_{i} = p_{i}^{2} + p_{i} + 1 = (1/3 + o(1))^{2}k^{2} = (1/3 + o(1))n. We let L be the set system on X given by

L = {L_{j}^{(1)} ∪ L_{j}^{(2)} ∪ L_{j}^{(3)} : 1 ≤ j ≤ n_{1}}.  (57)

The members of L are therefore (k+3)-element subsets of X, with |L△L′| = 2(p_{1} + p_{2} + p_{3}) = 2k for all distinct L and L′ ∈ L, and the case in which k is a large odd integer follows.

For even k, it suffices to let p_{4} = (1/4 + o(1))k be an odd prime (whose existence follows from the prime number theorem) and apply Haselgrove’s result to k − p_{4}, and then construct L as the union of 4 suitable projective planes. We omit the details. □

Lemmas 8 and 12 imply the following result.

Theorem 13. For all ε > 0, there are constants c > 0, k_{0}, and N_{0} for which the following hold.

(i) If k ≥ k_{0} is an odd integer with

(\frac{3}{2} + ε) \sqrt{N} ≤ k ≤ (\sqrt{3} − ε) \sqrt{N},  (58)

then C_{2k}(E_{N}) ≥ c\sqrt{N} for all E_{N} ∈ \{−1, 1\}^{N} as long as N ≥ N_{0}. (ii) If k ≥ k_{0} is an even integer with

(\frac{4}{5}\sqrt{5} + ε) \sqrt{N} ≤ k ≤ (2 − ε) \sqrt{N},  (59)

then C_{2k}(E_{N}) ≥ c\sqrt{N} for all E_{N} ∈ \{−1, 1\}^{N} as long as N ≥ N_{0}.

We omit the proof of Theorem 13. We only remark that it suffices to take for L in Lemma 8 the systems given by Lemma 12. One may prove results similar to Theorem 13 for other ranges of k of order \sqrt{N} using the method above: one simply proves variants of Lemma 12 by writing k as the sum of h nearly equal primes, for other values of h.

We close by making the following remark. In the discussion above, we have used the family of lines in projective planes; it is easy to check that one may also use hyperplanes in projective d-spaces for other values of d, to obtain lower bounds for C_{2k}(E_{N}) for any k of order N^{1−1/d}, in certain ranges (as in Theorem 13). Furthermore, for any k of order N, again in certain ranges, we may use Hadamard matrices arising from quadratic residues modulo primes to prove lower bounds of order \sqrt{N} for C_{2k}(E_{N}). We omit the details.

2.3.2. A variant of Theorem 2. In this section, we shall prove a result similar in nature to Theorem 2.

Theorem 14. There is an absolute constant c > 0 for which the following holds. For any positive integers ℓ and N with ℓ ≤ N/25 and N large enough, we have

max\{C_{2ℓ+2}(E_{N}), C_{2ℓ+4}(E_{N}), …, C_{4ℓ}(E_{N})\} ≥ c\sqrt{ℓN}  (60)

for all E_{N} ∈ {−1, 1}^{N}.

The proof of Theorem 14 is based on the following lemma.

Lemma 15. Let 1 ≤ ℓ ≤ n/9e. Then there is a system L of 2ℓ-element subsets of [n] with

|L| ≥ \frac{1}{2}\binom{n/9e}{ℓ}  (61)

and

|L △ L′| ≥ 2ℓ + 2  (62)

for all distinct L and L′ ∈ L.

Proof. We give a sketch of the proof. Comparing with a geometric series, one may check that, say,

∑_{ℓ≤j≤2ℓ} \binom{2ℓ}{j}\binom{n − 2ℓ}{2ℓ − j} ≤ 2\binom{2ℓ}{ℓ}\binom{n − 2ℓ}{ℓ}.  (63)

Let L be a maximal family of 2ℓ-element subsets of [n], with any two of its members satisfying (62) for all distinct L and L′ ∈ L. Then, clearly,

2\binom{2ℓ}{ℓ}\binom{n − 2ℓ}{ℓ}|L| ≥ |L| ∑_{ℓ≤j≤2ℓ} \binom{2ℓ}{j}\binom{n − 2ℓ}{2ℓ − j} ≥ \binom{n}{2ℓ}.  (64)

Therefore,

|L| ≥ \frac{1}{2}\binom{n}{2ℓ} /\binom{2ℓ}{ℓ}\binom{n − 2ℓ}{ℓ} = \frac{(n)_{ℓ}(n − ℓ)_{ℓ}(ℓ!)^{2}}{2(2ℓ)_{ℓ}(n − 2ℓ)_{ℓ}(2ℓ)!}

≥ \frac{(n − ℓ)_{ℓ}}{2(2ℓ)_{ℓ}4^{ℓ}} ≥ \frac{1}{2} (\frac{n − ℓ}{8ℓ})^{ℓ} ≥ \frac{1}{2} (\frac{n}{9ℓ})^{ℓ} ≥ \frac{1}{2}\binom{n/9e}{ℓ}, (65)

as required. □

Proof of Theorem 14. This follows from Lemmas 9 and 15; we shall only give a sketch of the proof, because the argument is simple and very similar to the argument given in the proof of Theorem 2. Let ℓ and N be as given in the statement of Theorem 14. The case in which ℓ = 1 is covered by Theorem 1 (in fact, the case in which ℓ is bounded follows from that result). Therefore, we suppose ℓ ≥ 2. Let M = ⌊N/50⌋ and N′ = N − M + 1. Let L be a family of 2ℓ-element subsets of [N′] of maximal cardinality satisfying (62) for all distinct L and L′ ∈ L. By Lemma 15, we have

2M ≤ \frac{1}{2} (\frac{N′/9e}{2})^{2} ≤ \frac{1}{2}\binom{N′/9e}{ℓ} ≤ |L| ≤ 2^{N′} < e^{50M}  (66)

for all large enough N. Therefore, Lemma 9 applies and we deduce that, for all E_{N} ∈ {−1, 1}^{N}, we have

max{C_{2ℓ+2}(E_{N}), C_{2ℓ+4}(E_{N}), …, C_{4ℓ}(E_{N})}

≥ min \{\frac{1}{2}M, \sqrt{\frac{1}{50}M(log |L|) /log \frac{50M}{log |L|}} \} . (67)

If the minimum on the right-hand side of (67) is achieved by M/2, we are done. In the other case, we may check that (60) follows for a suitable absolute constant c > 0 by, say, analysing the cases 1 ≤ ℓ = o(N) and ℓ ≥ c′N separately (see the proof of Theorem 2). □

2.4. Bounds from coding theory. We observe that one may prove lower bounds for the parameter C_{k}(E_{N}) by invoking upper bounds for the size of codes with a given minimum distance (bounds in the range that we are interested in are given in [9, p. 565] (see also [12])). For simplicity, let us take the case in which k = 2. A sequence with C_{2}(E_{N}) small gives rise to a large number of nearly orthogonal {−1, 1}-vectors of a given length: it suffices to consider all the N − M + 1 segments of E_{N} of length M, where we take M = (α + o(1))N for a suitable positive constant α. From the fact that C_{2}(E_{N}) is small, we may deduce that these N − M + 1 vectors are pairwise nearly orthogonal. Therefore, these binary vectors have pairwise Hamming distance at least M/2 − Δ, for some small Δ > 0. On the other hand, bounds from the theory of error correcting codes give us lower bounds for Δ, because we have a family of N −M +1 such vectors. The bounds one deduces with this approach are somewhat weaker than the bounds obtained above.

However, we mention that the argument above applies in a more general setting. For E_{N} ∈ {−1, 1}^{N}, let

C̃_{k}(E_{N}) = max{V (E_{N}, M, D): M and D with M − 1 + d_{k} ≤ N}, (68)

where D = {d_{1}, …, d_{k}} is as in Section 1; the only difference between C_{k}(E_{N}) and C̃_{k}(E_{N}) is that, in the definition of C̃_{k}(E_{N}), we do not take V (E_{N}, M, D) in absolute value (cf. (4) and (68)). Clearly, C̃_{k}(E_{N}) ≤ C_{k}(E_{N}). The argument from coding theory briefly sketched in the previous paragraph applies to C̃_{k}(E_{N}) as well.

3. The minimum of the normality measure 3.1. Remarks on min N (E_{N}). We start with two observations on N (E_{N}). Put

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

where the maxima are taken over all X ∈ {−1, 1}^{k} and 0 < M ≤ N + 1 − k. Note that, then, we have N (E_{N}) = max{N_{k}(E_{N}): k ≤ log_{2} N}.

Proposition 16. (i) We have min_{E_{N}} N_{k}(E_{N}) = 1 − 2^{−k} for any k ≥ 1 and any N ≥ 2^{k}. (ii) We have

min_{E_{N}} N (E_{N}) ≥ (\frac{1}{2} + o(1)) log_{2} N.  (70)

Proof. To prove (i), we simply consider powers of appropriate de Bruijn sequences [6]. More precisely, we take a circular sequence in which every member of {−1, 1}^{k} occurs exactly once, open it up (turning it into a linear sequence), and repeat it an appropriate number of times. The fact that N_{k}(E_{N}) ≥ 1 − 2^{−k} for this sequence E_{N} may be seen by taking M = 1 in (69) with X the prefix of E_{N} of length k. We leave the other inequality for the reader.

Let us now prove (ii). If a sequence E_{N} ∈ {−1, 1}^{N} contains no segment of length k = ⌊log_{2} N − log_{2} log_{2} N⌋ of repeated 1s, then

N_{k}(E_{N}) ≥ \frac{N − k + 1}{2^{k}} = (1 + o(1))\frac{N}{2^{k}} ≥ (1 + o(1)) log_{2} N,  (71)

as required. Suppose now that E_{N} = (e_{i})_{1≤i≤N} does contain such a segment, say, (e_{M_{0}}, …, e_{M_{0}+k−1}) = (1, …, 1). Fix ℓ = ℓ(N) → ∞ as N → ∞ with ℓ = o(k), and let X_{ℓ} be the sequence of ℓ consecutive 1s. Let M_{1} = M_{0} + k − ℓ, and note that then

T (E_{N}, M_{1}, X_{ℓ}) − T (E_{N}, M_{0}, X_{ℓ}) = M_{1} − M_{0} + 1 = k − ℓ + 1 = (1 + o(1))k. (72)

Therefore

(T (E_{N}, M_{1}, X_{ℓ}) − \frac{M_{1}}{2^{ℓ}} ) − (T (E_{N}, M_{0}, X_{ℓ}) − \frac{M_{0}}{2^{ℓ}} )

= (1 + o(1))k − (M_{1} − M_{0})2^{−ℓ} = (1 + o(1))k. (73)

It follows from (73) that for some M_{0} ≤ M^{∗} ≤ M_{1} we have

|T (E_{N}, M^{∗}, X_{ℓ}) − \frac{M^{∗}}{2^{ℓ}} | ≥ (\frac{1}{2} + o(1)) k = (\frac{1}{2} + o(1)) log_{2} N. (74)

Therefore, N (E_{N}) ≥ N_{ℓ}(E_{N}) ≥ (1/2 + o(1)) log_{2} N, as required. □

We suspect that the logarithmic lower bound in Proposition 16(ii) is far from the truth.

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

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

for all large enough N?

3.2. A sequence E_{N} with small N (E_{N}). Our aim in this section is to prove Theorem 4. We start by describing the construction of E_{N}.

Let s be a positive integer and let 𝔽_{2^{s}} = GF(2^{s}) be the finite field with 2^{s} elements. Fix a primitive element x ∈ 𝔽_{2^{s}}^{∗}, and let m = |𝔽_{2^{s}}^{∗}| = 2^{s} − 1. We consider 𝔽_{2^{s}} as a vector space over 𝔽_{2}, and fix a non-zero linear functional

b: 𝔽_{2^{s}} → 𝔽_{2}.  (75)

We now let

Ẽ_{m} = (b(x), b(x^{2}), …, b(x^{m})) ∈ 𝔽_{2}^{m} = {0, 1}^{m}  (76)

and let

E_{m} = ((−1)^{b(x)}, (−1)^{b(x^{2})}, …, (−1)^{b(x^{m})}) ∈ {−1, 1}^{m}.  (77)

Finally, set

E_{N} = E_{m}^{q} = E_{m} … E_{m} (q factors), (78)

where E_{m}^{q} denotes the concatenation of q copies of E_{m}; clearly, E_{N} has length N = qm.

Theorem 18. Let s ≥ 2. With E_{N} as defined in (78), we have

N (E_{N}) ≤ q + 2(log_{2}(m − 1))\sqrt{m}.  (79)

Theorem 4 will be deduced from Theorem 18 in Section 3.2.2 below. Let us now give a rough outline of the proof of Theorem 18. Essentially all the work will concern the sequence E_{m} defined above.

In what follows, we shall first prove that any reasonably long segment of E_{m} has small ‘discrepancy’; we shall show that the entries of segments of E_{m} of length k add up to O((log k)\sqrt{m}) (see Corollary 22). We shall then show two results concerning the number of occurrences of (short) words in E_{m}. We shall first show that all the words of length k ≤ s (except for the word (0, …, 0)) occur exactly the same number of times in E_{m} (see Lemma 23). We shall then prove a similar fact for segments of E_{m}, although for segments the conclusion will be weaker (see Lemma 25). Theorem 18 will then be deduced from these facts in Section 3.2.2.

3.2.1. Auxiliary lemmas. We start with a well known lemma concerning the ‘discrepancy’ of matrices whose rows have uniformly bounded norm and, pairwise, have non-positive inner product (see, e.g., [7, Theorem 15.2] for a similar statement).

Lemma 19. Let H = (h_{ij})_{1≤i,j≤M} be an M by M real matrix and let v_{i} be the ith row of H (1 ≤ i ≤ M). Let A, B ⊂ [M] be given, and suppose that

∥v_{a}∥ ≤ \sqrt{m}  (80)

for all a ∈ A and

⟨v_{a}, v_{a′}⟩ = ∑_{1≤b≤M} h_{ab}h_{a′b} ≤ 0  (81)

for all a ≠ a′ with a, a′ ∈ A. Then

| ∑_{a∈A, b∈B} h_{ab}| ≤ \sqrt{m|A||B|}.  (82)

Proof. Let 1_{B} ∈ {0, 1}^{M} be the characteristic vector of B. By the Cauchy– Schwarz inequality, we have

| ∑_{A, B} h_{ab}| = |⟨ ∑_{a∈A} v_{a}, 1_{B}⟩| ≤ ∥ ∑_{a∈A} v_{a}∥\sqrt{|B|}.  (83)

From (80) and (81), we have

∥ ∑_{a∈A} v_{a}∥^{2} = ∑_{a∈A} ∥v_{a}∥^{2} + ∑_{a∈A} ∑_{a≠a′∈A}⟨v_{a}, v_{a′}⟩ ≤ m|A|.  (84)

Plugging (84) into (83), we have

| ∑_{A, B} h_{ab}| ≤ \sqrt{m|A||B|},

as required. □

We now define a matrix E from E_{m}; we shall apply Lemma 19 to E to deduce the discrepancy property we seek for E_{m}. Let

E = (E_{ij})_{1≤i,j≤m} = [\begin{matrix}(−1)^{b(x)} & (−1)^{b(x^{2})} & … & (−1)^{b(x^{m})} \\ (−1)^{b(x^{2})} & (−1)^{b(x^{3})} & … & (−1)^{b(x)} \\ ⋮ & ⋮ & ... & ⋮ \\ (−1)^{b(x^{m})} & (−1)^{b(x)} & … & (−1)^{b(x^{m−1})} \end{matrix}] . (85)

Note that E is an m × m circulant, symmetric {−1, 1}-matrix whose first row is E_{m}. For convenience, let e_{i} = (E_{ij})_{1≤j≤m} (1 ≤ i ≤ m) denote the ith row of E. Moreover, if v = (v_{j})_{1≤j≤m} and w = (w_{j})_{1≤j≤m} are two real m-vectors, let v ∘ w denote the m-vector (v_{j}w_{j})_{1≤j≤m}.

Lemma 20. The following hold for E:

(i) Every row of E adds up to −1, that is, ∑_{1≤j≤m} E_{ij} = −1 for all 1 ≤ i ≤ m.

(ii) For all i ≠ i′ (1 ≤ i, i′ ≤ m), we have e_{i} ∘ e_{i′} = e_{i′′} for some 1 ≤

i′′ ≤ m. (iii) The matrix E satisfies

EE^{T} = −J + (m + 1)I,  (86)

where J is the m × m matrix with all entries 1 and I is the m × m identity matrix.

(iv) For all A and B ⊂ [m], we have

| ∑_{a∈A, b∈B} E_{ab}| ≤ \sqrt{m|A||B|}.  (87)

Proof. Since b: 𝔽_{2^{s}} → 𝔽_{2} is a non-zero linear functional, b^{−1}(0) is a hyperplane in 𝔽_{2^{s}} and hence has cardinality 2^{s−1}. Given that 𝔽_{2^{s}}^{∗} = {x^{j}: 1 ≤ j ≤ m = 2^{s} − 1}, we conclude that b(x^{j}) = 1 for 2^{s−1} values of j with 1 ≤ j ≤ m and b(x^{j}) = 0 for all the other 2^{s−1}−1 values of j with 1 ≤ j ≤ m. Therefore, statement (i) follows. Let now 1 ≤ i < i′ ≤ m be fixed. Then

e_{i} ∘ e_{i′}

= ((−1)^{b(x^{i})+b(x^{i′})}, (−1)^{b(x^{i+1})+b(x^{i′+1})}, …, (−1)^{b(x^{i−1})+b(x^{i′−1})})

= ((−1)^{b(x^{i}+x^{i′})}, (−1)^{b(x^{i+1}+x^{i′+1})}, …, (−1)^{b(x^{i−1}+x^{i′−1})})

= ((−1)^{b(x^{i}(1+x^{i′−i}))}, (−1)^{b(x^{i+1}(1+x^{i′−i}))}, …, (−1)^{b(x^{i−1}(1+x^{i′−i}))}). (88)

However, as 0 < i′ − i < m, we have 1 + x^{i′−i} ≠ 0, and hence 1 + x^{i−i′} = x^{k} for some 1 ≤ k ≤ m. Therefore, we have from (88) that

e_{i} ∘ e_{i′} = ((−1)^{b(x^{i+k})}, (−1)^{b(x^{i+1+k})}, …, (−1)^{b(x^{i−1+k})}) = e_{i+k}  (89)

(naturally, the index of e_{i+k} is modulo m). Equation (89) proves (ii).

Equation (86) is an immediate consequence of (i) and (ii), and hence (iii) is clear. Finally, for (iv), it suffices to notice that ∥e_{i}∥ = \sqrt{m} for all i and that, from the above discussion, ⟨e_{i}, e_{i′}⟩ = −1 < 0 for all i ≠ i′. Therefore, Lemma 19 applies and (87) follows. □

Lemma 20(iv) tells us that ‘rectangles’ in the matrix E have small discrepancy (in the sense of (87)). We shall now deduce a similar result for ‘triangles’ in E, which will later be used to show that segments of E_{m} have small discrepancy.

Lemma 21. Let A and B ⊂ [m] be given and suppose A = {a_{1}, …, a_{t}}, B = {b_{1}, …, b_{t}}, where a_{1} < ⋯ < a_{t} and b_{1} < ⋯ < b_{t}. The following assertions hold for the matrix E = (E_{ij})_{1≤i,j≤m}.

(i) We have

| ∑_{i+j≤t+1} E_{a_{i}b_{j}} | ≤ (t log_{2} t + 1)\sqrt{m}.  (90)

(ii) Similarly,

| ∑_{i+j≥t+1} E_{a_{i}b_{j}} | ≤ (t log_{2} t + 1)\sqrt{m}.  (91)

Proof. Inequality (90) follows from Lemma 20(iv), by induction on t. Note first that (90) holds for t = 1. Now suppose that t > 1 and that (90) holds for smaller values of t. By the triangle inequality, we have

| ∑_{i+j≤t+1} E_{a_{i}b_{j}} | ≤ | ∑_{(i,j)∈S} E_{a_{i}b_{j}} | + | ∑_{(i,j)∈T_{1}} E_{a_{i}b_{j}} | + | ∑_{(i,j)∈T_{2}} E_{a_{i}b_{j}} |, (92)

where S = {(i, j): i, j ≤ ⌈t/2⌉}, T_{1} = {(i, j): i ≤ ⌈t/2⌉, j > ⌈t/2⌉}, and T_{2} = {(i, j): j ≤ ⌈t/2⌉, i > ⌈t/2⌉}. We now estimate the three terms on the right-hand side of (92) by using (87) and the induction hypothesis twice. We have

| ∑_{i+j≤t+1} E_{a_{i}b_{j}} | ≤ ⌈\frac{t}{2}⌉ \sqrt{m} + 2 (⌊\frac{t}{2}⌋ log_{2} ⌊\frac{t}{2}⌋ + 1) \sqrt{m}

≤ ⌈\frac{t}{2}⌉ \sqrt{m} + (t(log_{2} t − 1) + 2) \sqrt{m}

≤ (t log_{2} t + 1)\sqrt{m} + ⌈\frac{t}{2}⌉ \sqrt{m} − (t − 1)\sqrt{m}

≤ (t log_{2} t + 1)\sqrt{m},  (93)

which completes the induction step, and (i) is proved. The proof of assertion (ii) is similar, and hence it is omitted. □

We shall now show that segments of E_{m} have small discrepancy, in the sense that they have the same number of 1s as −1s, up to a small error. We observe that Corollary 22 also considers segments of E_{m} that “wrap around” the end of E_{m}; equivalently, that result considers E_{m} as a circular sequence.

Corollary 22. For any 1 ≤ r ≤ m and 2 ≤ k ≤ m, we have

| ∑_{0≤i<k}(−1)^{b(x^{r+i})}| ≤ (log_{2} k + (1 − \frac{1}{k} ) log_{2}(k − 1) + \frac{2}{k} ) \sqrt{m}. (94)

In particular, for all 1 ≤ r ≤ m and 2 ≤ k ≤ m, we have

| ∑_{0≤i<k}(−1)^{b(x^{r+i})}| ≤ 2(log_{2} k)\sqrt{m}.  (95)

Proof. Note that

(1 − \frac{1}{k} ) log_{2}(k − 1) + \frac{2}{k} ≤ log_{2} k  (96)

if and only if

(k − 1)^{1−1/k}2^{2/k} ≤ k  (97)

if and only if

(1 − \frac{1}{k} )^{k} ≤ \frac{1}{4}(k − 1),  (98)

E_{1,r} E_{1,r+1} … E_{1,r+k−1}
E_{2,r−1} E_{2,r}  ...
...  ⋮  ⋮  ...
E_{k,r−k+1} … E_{k,r−1} E_{k,r}

Figure 1. Portion of the matrix E to which Lemma 21(i) and (ii) are applied. Note that E_{1,r} = E_{2,r−1} = ⋯ = E_{k,r−k+1} = (−1)^{b(x^{r})}, E_{1,r+1} = E_{2,r} = ⋯ = E_{k,r−k+2} = (−1)^{b(x^{r+1})}, etc.

which holds if k ≥ 3. Therefore, (95) follows directly from (94) for 3 ≤ k ≤ m. If k = 2, then (95) holds by inspection. To prove (94), we apply Lemma 21(i) and (ii). For the application of (i), we consider the sets A = {1, 2, …, k}, and B = {r, r + 1, …, r + k − 1}, whereas for the application of (ii) we consider A′ = {2, 3, …, k} and B′ = {r−k+1, r−k+2, …, r−1}. Taking into account that E = (E_{ij}) is circulant, we deduce that

k ∑_{0≤i<k}(−1)^{b(x^{r+i})} = ∑{E_{ab}: a ∈ A, b ∈ B, a + b ≤ k + r}

+ ∑{E_{a′b′}: a′ ∈ A′, b′ ∈ B′, a′ + b′ ≥ r + 1} (99)

(see Figure 1). Therefore, by the triangle inequality, we have

k| ∑_{0≤i<k}(−1)^{b(x^{r+i})}| ≤ | ∑{E_{ab}: a ∈ A, b ∈ B, a + b ≤ k + r}|

+ | ∑{E_{a′b′}: a′ ∈ A′, b′ ∈ B′, a′ + b′ ≥ r + 1}|

≤ (k log_{2} k + 1)\sqrt{m} + ((k − 1) log_{2}(k − 1) + 1) \sqrt{m}, (100)

and (94) follows on dividing (100) by k. □

The next lemma states that the number of occurrences of shorter words in Ẽ_{m} is basically equal to the expectation of this number in the case of the random sequence of length m. To state this precisely, we introduce some notation. Let 1 ≤ k ≤ s be fixed. For all 1 ≤ r ≤ m, let Ẽ_{m}^{(r)} denote the segment of Ẽ_{m} of length k starting at its rth letter, that is,

Ẽ_{m}^{(r)} = (b(x^{r}), b(x^{r+1}), …, b(x^{r+k−1}))  (101)

(Ẽ_{m} is considered as a cyclic sequence). Now, for all X ∈ {0, 1}^{k}, let f_{X} = f_{X}(Ẽ_{m}) denote the number of occurrences of X as a segment in Ẽ_{m}, where we consider Ẽ_{m} as a cyclic sequence; that is,

f_{X} = card{r: 1 ≤ r ≤ m and Ẽ_{m}^{(r)} = X}.  (102)

Lemma 23. For all 1 ≤ k ≤ s, we have

f_{X} = f_{X}(Ẽ_{m}) = \begin{cases}(m + 1)2^{−k} − 1 = 2^{s−k} − 1 & if X = (0, …, 0) ∈ \{0, 1\}^{k} \\ (m + 1)2^{−k} = 2^{s−k} & otherwise. \end{cases}

(103)

Proof. Let 1 ≤ r ≤ m and δ = (δ_{i})_{1≤i≤k} ∈ {0, 1}^{k} be given. Note that

⟨δ, Ẽ_{m}^{(r)}⟩ = ∑_{1≤i≤k} δ_{i}b(x^{r+i−1}) = b(x^{r} ∑_{1≤i≤k} δ_{i}x^{i−1}).  (104)

We shall now use the fact that x does not satisfy a polynomial over 𝔽_{2} of degree less than s (indeed, if p(x) = 0 for a polynomial p over 𝔽_{2} of degree t, then a standard argument shows that 1, x, …, x^{t−1} spans 𝔽_{2^{s}} as a vector space over 𝔽_{2} and hence deg(p) = t ≥ s). We use this fact in (104): as k ≤ s, we see that ∑_{1≤i≤k} δ_{i}x^{i−1} ≠ 0 as long as δ ≠ (0, …, 0), and hence this sum

is x^{t} for some 1 ≤ t ≤ m independent of r. Therefore, ⟨δ, Ẽ_{m}^{(r)}⟩ = b(x^{r+t}), and we have

∑_{1≤r≤m}(−1)^{⟨δ,Ẽ_{m}^{(r)}⟩} = ∑_{1≤r≤m}(−1)^{b(x^{r+t})} = −1  (105)

by Lemma 20(i), since we have in (105) above the sum of the entries of the (t + 1)st row of E. If δ = (0, …, 0), then clearly the sum in (105) is m.

Let us now observe that the left-hand side of (105) may also be written as

∑_{X}(−1)^{⟨δ,X⟩}f_{X},  (106)

where the sum is over all X ∈ {0, 1}^{k}. Therefore, we have established a system of 2^{k} linear equation for the f_{X} (X ∈ {0, 1}^{k}):

∑_{X∈\{0,1\}^{k}}(−1)^{⟨δ,X⟩}f_{X} = \begin{cases}m & if δ = (0, …, 0) ∈ \{0, 1\}^{k} \\ −1 & otherwise. \end{cases}  (107)

The matrix associated to the system of equations (107) is the 2^{k} × 2^{k} Hadamard matrix H_{k} = [(−1)^{⟨δ,X⟩}]_{δ,X∈{0,1}^{k}}. For convenience, let f = (f_{X})_{X∈{0,1}^{k}} and let g = (g_{δ})_{δ∈{0,1}^{k}}, where g_{δ} = m if δ = (0, …, 0) and g_{δ} = −1 otherwise. Then (107) may be written as

H_{k}f = g.  (108)

Now, since

∑_{δ∈{0,1}^{k}}(−1)^{⟨δ,X⟩}(−1)^{⟨δ,Y ⟩} = ∑_{δ∈{0,1}^{k}}(−1)^{⟨δ,X△Y ⟩} = 0  (109)

if X ≠ Y, we have

H_{k}^{T} H_{k} = 2^{k}I,  (110)

where, naturally, I is the 2^{k} × 2^{k} identity matrix. Therefore, from (108) and (110) we have

2^{k}f = H_{k}^{T} H_{k}f = H_{k}^{T} g.  (111)

The last product in (111) may be computed explicitly, and one obtains that

H_{k}^{T} g = [m − 2^{k} + 1 ; m + 1 ; ⋮ ; m + 1] ,  (112)

where the entry m − 2^{k} + 1 corresponds to X = (0, …, 0). Equation (103) now follows from (111) and (112). □

Setting k = s in Lemma 23, we see that words of length s occur in Ẽ_{m} at most once. Since every occurrence of a word of length at least s gives us an occurrence of its prefix of length s, we conclude that words longer than s occur no more than once in Ẽ_{m}. We thus have the following corollary to Lemma 23, to be used later in the proof of Theorem 18.

Corollary 24. Suppose ℓ ≥ s = log_{2}(m + 1). Any Y ∈ {0, 1}^{ℓ} occurs at most once in Ẽ_{m}, even considering Ẽ_{m} as cyclic sequence; that is,

card{r: 1 ≤ r ≤ m and (b(x^{r}), …, b(x^{r+ℓ−1})) = Y } ≤ 1.  (113)

As it turns out, not only has Ẽ_{m} the property that shorter words occur evenly in it (as shows Lemma 23), but Ẽ_{m} has this property on its longer segments (in a weaker sense): for k ≤ s = log_{2}(m + 1), every kletter word X ∈ {0, 1}^{k} occurs roughly n2^{−k} times in any segment of Ẽ_{m} of length n, as long as n is reasonably large.

To make the above statement precise, we introduce some notation. Let 1 ≤ r ≤ m and 1 ≤ n ≤ m be given. Let Ẽ_{m}^{(r,n)} be the segment of Ẽ_{m} of length n starting at the rth letter of Ẽ_{m}, that is, set

Ẽ_{m}^{(r,n)} = (b(x^{r}), b(x^{r+1}), …, b(x^{r+n−1})).  (114)

Now let 1 ≤ k ≤ s. We shall be interested in the segments Ẽ_{m}^{(t,k)} of length k of Ẽ_{m}, for r ≤ t < r + n. For X ∈ {0, 1}^{k}, set

f_{X} = f_{X}(Ẽ_{m}^{(r,n)}) = card{t: r ≤ t < r + n and Ẽ_{m}^{(t,k)} = X}.  (115)

In what follows, we write O_{1}(a) for any term b such that |b| ≤ a. We are now ready to state our lemma on the frequency of words in segments of Ẽ_{m}.

Lemma 25. For any 1 ≤ r ≤ m, 2 ≤ n ≤ m, and 1 ≤ k ≤ s, we have

f_{X} = f_{X}(Ẽ_{m}^{(r,n)}) = n2^{−k} + O_{1} (2(log_{2} n)\sqrt{m})  (116)

for all X ∈ {0, 1}^{k}.

The proof of Lemma 25 will be similar to the proof of Lemma 23, except that we shall now make use of Corollary 22, instead of using the fact that the sum of the entries of the whole sequence E_{m} is −1.

Proof of Lemma 25. Let δ = (δ_{i})_{1≤i≤k} ∈ {0, 1}^{k} be fixed. As before, we have

⟨δ, Ẽ_{m}^{(t,k)}⟩ = ∑_{1≤i≤k} δ_{i}b(x^{t+i−1}) = b(x^{t} ∑_{1≤i≤k} δ_{i}x^{i−1}) = b(x^{t+u}), (117)

for some 1 ≤ u ≤ m independent of t. Therefore, by Corollary 22,

| ∑_{X∈{0,1}^{k}}(−1)^{⟨δ,X⟩}f_{X} | = | ∑_{r≤t<r+n}(−1)^{⟨δ,Ẽ_{m}^{(t,k)}⟩}|

= | ∑_{r≤t<r+n}(−1)^{b(x^{t+u})}| ≤ 2(log_{2} n)\sqrt{m}. (118)

As before, let H_{k} be the 2^{k} × 2^{k} Hadamard matrix [(−1)^{⟨δ,X⟩}]_{δ,X∈{0,1}^{k}}, and let f = (f_{X})_{X∈{0,1}^{k}}. If g = H_{k}f and g = (g_{δ})_{δ∈{0,1}^{k}}, then (118) implies that

g_{δ} = \begin{cases}n & if δ = (0, …, 0) \\ O_{1} (2(log_{2} n)\sqrt{m}) & otherwise. \end{cases}  (119)

Using that H_{k}^{T} H_{k} = 2^{k}I, we have

f = 2^{−k}H_{k}^{T} H_{k}f = 2^{−k}H_{k}^{T} g.  (120)

One may easily observe that the entries of H_{k}^{T} g are all equal to

n + O_{1} (2^{k+1}(log_{2} n)\sqrt{m}) .  (121)

The asserted conclusion (116) follows from (120) and (121). □

3.2.2. Proof of Theorems 4 and 18. We shall prove Theorem 18 using Lemmas 23 and 25 and Corollary 24, whereas we shall deduce Theorem 4 from Theorem 18 by making a suitable choice for q and m in the construction of E_{N}. Let us start with the proof of Theorem 18.

Proof of Theorem 18. Let E_{N} be as defined in (78), and let X ∈ {−1, 1}^{k} with 1 ≤ k ≤ log_{2} N be given. Let 1 ≤ M ≤ N − k + 1 and let us compute T (E_{N}, M, X); our aim is to compare T (E_{N}, M, X) and M2^{−k}.

We first suppose k ≤ s, so that we may apply Lemmas 23 and 25.

Let M = αm + β, where α and β are integers with 0 ≤ β < m. Clearly, 0 ≤ α ≤ q. We use the following notation below, for conciseness: if P is some property, then [P] = 0 if P is false and [P] = 1 if P is true.

By definition (1), we have T (E_{m}, β, X) ≤ β. Suppose for a moment that β ≥ 2. Then, by Lemma 25 applied with r = 1 and n = β ≥ 2, we have

T (E_{m}, β, X) ≤ β2^{−k} + 2(log_{2} β)\sqrt{m}
≤ β2^{−k} + 2(log_{2}(m − 1))\sqrt{m}.  (122)

As m = 2^{s} − 1 ≥ 3, the upper bound (122) for T (E_{m}, β, X) does hold for β = 0 and β = 1 as well. Lemma 23 tells us that T (E_{m}, m, X) ≤ (m + 1)2^{−k} − [X = 1] (note that the ‘exceptional’ sequence in (103), which concerns Ẽ_{m} ∈ {0, 1}^{m}, is the zero sequence 0 ∈ {0, 1}^{k}, which translates to the all 1 sequence 1 ∈ {−1, 1}^{k} when considering E_{m} ∈ {−1, 1}^{m}). We conclude from this and (122) that

T (E_{N}, M, X) = αT (E_{m}, m, X) + T (E_{m}, β, X)
≤ α(m2^{−k} + 2^{−k} − [X = 1]) + β2^{−k} + 2(log_{2}(m − 1))\sqrt{m}
= αm2^{−k} + β2^{−k} + α(2^{−k} − [X = 1]) + 2(log_{2}(m − 1))\sqrt{m}
≤ M2^{−k} + q + 2(log_{2}(m − 1))\sqrt{m}.  (123)

Similarly, by Lemmas 23 and 25, we have

T (E_{N}, M, X) = αT (E_{m}, m, X) + T (E_{m}, β, X)
≥ α(m2^{−k} + 2^{−k} − [X = 1]) + β2^{−k} − 2(log_{2}(m − 1))\sqrt{m}
= αm2^{−k} + β2^{−k} + α(2^{−k} − [X = 1]) − 2(log_{2}(m − 1))\sqrt{m}
≥ M2^{−k} − q − 2(log_{2}(m − 1))\sqrt{m}.  (124)

From (123) and (124), we have

|T (E_{N}, M, X) − \frac{M}{2^{k}} | ≤ q + 2(log_{2}(m − 1))\sqrt{m}.  (125)

We have thus completed the analysis for the case in which k ≤ s. Suppose now that k > s. Recall that Corollary 24 tells us that, in this case, X occurs in E_{m} at most once, that is, T (E_{m}, m, X) ≤ 1 and hence 0 ≤ T (E_{N}, M, X) ≤ q. Note also that

0 ≤ \frac{M}{2^{k}} ≤ \frac{N}{2^{s+1}} = \frac{N}{2(m + 1)} < \frac{1}{2}q.  (126)

Therefore,

|T (E_{N}, M, X) − \frac{M}{2^{k}} | ≤ q.  (127)

Inequality (79) follows from (125) and (127). □

We shall now prove Theorem 4.

Proof of Theorem 4. Let an integer N be given. In what follows, we may suppose that N is suitably large for our inequalities to hold. We start by choosing an integer s so that m = 2^{s} − 1 satisfies

\frac{14}{17} (\frac{N}{log_{2} N} )^{2/3} ≤ m ≤ \frac{5}{3} (\frac{N}{log_{2} N} )^{2/3} .  (128)

We now let

q = ⌊\frac{11}{9}N^{1/3}(log_{2} N)^{2/3}⌋ ,  (129)

set N′ = qm, and consider E_{N′} = E_{m} … E_{m} = E_{m}^{q}. We have

N′ = qm ≥ ⌊\frac{11}{9}N^{1/3}(log_{2} N)^{2/3}⌋ × \frac{14}{17} (\frac{N}{log_{2} N} )^{2/3} ≥ N  (130)

for all large enough N. We let E_{N} be the prefix of E_{N′} of length N.

We claim that E_{N} satisfies (12). Clearly, it suffices to show that E_{N′} is such that N (E_{N′}) ≤ 3N^{1/3}(log_{2} N)^{2/3}. To prove this last inequality, we simply show that the right-hand side of (79) is at most 3N^{1/3}(log_{2} N)^{2/3}.

We have

log_{2}(m − 1) < log_{2} (\frac{5}{3} (\frac{N}{log_{2} N} )^{2/3}) < \frac{2}{3} log_{2} N.  (131)

Moreover,

\sqrt{m} ≤ (\frac{5}{3} (\frac{N}{log_{2} N} )^{2/3})^{1/2} < \frac{31}{24} (\frac{N}{log_{2} N} )^{1/3}  (132)

for all large enough N. Therefore,

q + 2(log_{2}(m − 1))\sqrt{m} < \frac{11}{9}N^{1/3}(log_{2} N)^{2/3} + \frac{31}{18}(log_{2} N) (\frac{N}{log_{2} N} )^{1/3}

< 3N^{1/3}(log_{2} N)^{2/3}, (133)

implying that the right-hand side of (79) is at most 3N^{1/3}(log_{2} N)^{2/3}, as required. □

We close with a remark concerning some recent work of Carpi and de Luca [3], generalizing de Bruijn sequences [6]. Those authors have proved a number of interesting results on uniform words: words w such that for any two words u and v of the same length, the number of occurrences of u and v in w differ by at most 1. It would be interesting to see whether their constructions could be used to obtain words with small normality measure.

3.3. Larger alphabets. We now sketch a generalization of the construction in Section 3.2 to alphabets of cardinality larger than 2. As it turns out, the construction generalizes easily to alphabets of cardinality that are powers of primes.

Let s be a positive integer and q a power of a prime, and let 𝔽_{q^{s}} = GF(q^{s}) be the finite field with q^{s} elements. Fix a primitive element x ∈ 𝔽_{q^{s}}^{∗}, and let m = |𝔽_{q^{s}}^{∗}| = q^{s} − 1. We consider 𝔽_{q^{s}} as a vector space over 𝔽_{q}, and fix a non-zero linear functional

b: 𝔽_{q^{s}} → 𝔽_{q}.  (134)

Let ψ: 𝔽_{q} → S^{1} ⊂ ℂ be an additive character with card{ψ(y): y ∈ 𝔽_{q}} = q (that is, we take ψ injective), and put

Ẽ_{m} = (b(x), b(x^{2}), …, b(x^{m})) ∈ 𝔽_{q}^{m}  (135)

and

E_{m} = (ψ(b(x)), ψ(b(x^{2})), …, ψ(b(x^{m}))) ∈ (S^{1})^{m}.  (136)

Finally, set

E_{N} = E_{m}^{ℓ} = E_{m} … E_{m}  (ℓ factors),  (137)

where E_{m}^{ℓ} denotes the concatenation of ℓ copies of E_{m}; clearly, E_{N} has length N = ℓm. The sequence E_{N}, considered as a word over the q-letter alphabet

Σ_{q} = {ψ(y): y ∈ 𝔽_{q}},  (138)

is such that

N^{(q)}(E_{N}) = O (N^{1/3}(log N)^{2/3}) ,  (139)

where

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

and the maxima are taken over all 1 ≤ k ≤ log_{q} N, X ∈ Σ_{q}^{k}, and 0 < M ≤ N + 1 − k.

Let us sketch the proof of (139). This time, we let

E = (E_{ij})_{1≤i,j≤m} = [\begin{matrix}ψ(b(x)) & ψ(b(x^{2})) & … & ψ(b(x^{m})) \\ ψ(b(x^{2})) & ψ(b(x^{3})) & … & ψ(b(x)) \\ ⋮ & ⋮ & ... & ⋮ \\ ψ(b(x^{m})) & ψ(b(x)) & … & ψ(b(x^{m−1})) \end{matrix}] . (141)

Then E is an m × m circulant, complex matrix whose first row is E_{m}. Again, let e_{i} = (E_{ij})_{1≤j≤m} (1 ≤ i ≤ m) denote the ith row of E. Moreover, if v = (v_{j})_{1≤j≤m} and w = (w_{j})_{1≤j≤m} are two complex m-vectors, let v ∘ w denote the m-vector (v_{j}\overline{w_{j}})_{1≤j≤m}, where \overline{z} denotes the complex conjugate of z ∈ ℂ.

It turns out that Lemma 20 generalizes to the the matrix E defined in (141), in the following way.

Lemma 26. The following hold for E:

(i) Every row of E adds up to −1, that is, ∑_{1≤j≤m} E_{ij} = −1 for all 1 ≤ i ≤ m.

(ii) For all i ≠ i′ (1 ≤ i, i′ ≤ m), we have e_{i} ∘ e_{i′} = e_{i′′} for some 1 ≤ i′′ ≤ m.

(iii) The matrix E satisfies

EE^{∗} = −J + (m + 1)I,  (142)

where E^{∗} is the adjoint of E. (iv) For all A and B ⊂ [m], we have

| ∑_{a∈A, b∈B} E_{ab}| ≤ \sqrt{m|A||B|}.  (143)

Lemma 26(i)–(iii) may be checked easily. For Lemma 26(iv), one observes that Lemma 19 may be generalized in a natural way to complex matrices, with exactly the same proof.

Lemma 27. Let H = (h_{ij})_{1≤i,j≤M} be an M by M complex matrix and let v_{i} be the ith row of H (1 ≤ i ≤ M). Let A, B ⊂ [M] be given, and suppose that

∥v_{a}∥ = \sqrt{∑_{1≤j≤m} |h_{aj}|^{2}} ≤ \sqrt{m}  (144)

for all a ∈ A and

⟨v_{a}, v_{a′}⟩ = ∑_{1≤b≤m} h_{ab}\overline{h_{a′b}} ≤ 0  (145)

for all a ≠ a′ with a, a′ ∈ A. Then

| ∑_{a∈A, b∈B} h_{ab}| ≤ \sqrt{m|A||B|}.  (146)

To prove Lemma 26(iv), one applies Lemma 27 to the matrix E given in (141). The remainder of the argument is as before, with some small changes. The 2^{k} × 2^{k} Hadamard matrix H_{k} = [(−1)^{⟨δ,X⟩}]_{δ,X∈{0,1}^{k}} that occurs later in the proof should be replaced by the q^{k} × q^{k} matrix H_{k} = [ψ(⟨δ, X⟩)]_{δ,X}, where δ and X vary over 𝔽_{q}^{k}, which is a unitary matrix, up to a multiplicative constant: H_{k}H_{k}^{∗} = mI. We omit the details.

3.4. The Pólya–Vinogradov inequality. Let p be a prime and let χ: 𝔽_{p} = ℤ/pℤ → S^{1} ⊂ ℂ be a multiplicative character, where, as usual, χ(0) = 0. With the methods in Section 3.2.1 (and Lemma 27 above) one may easily prove the celebrated Pólya–Vinogradov inequality, in the following form.

Theorem 28. For all integers r and 2 ≤ k ≤ p, we have

| ∑_{0≤h<k} χ(r + h)| ≤ 2(log_{2} k)\sqrt{p − 1}.  (147)

We give an outline of the proof of Theorem 28. This time, we let E = (e_{ij})_{i,j} = (χ(i − j))_{0≤i,j<p}. Note that E is circulant: e_{00} = e_{11} = e_{22} = ⋯, e_{01} = e_{12} = e_{23} = ⋯, e_{10} = e_{21} = e_{32} ⋯, etc. The rows v_{i} (0 ≤ i < p) of E have Euclidean norm \sqrt{p − 1}. Moreover, one may check that

⟨v_{i}, v_{i′}⟩ = −1  (148)

for all i ≠ i′. Indeed,

⟨v_{i}, v_{i′}⟩ = ∑_{0≤j<p} χ(i − j)\overline{χ(i′ − j)} = ∑_{0≤j<p, j≠i, i′} χ (\frac{i − j}{i′ − j} )

= ∑_{0≤j<p, j≠i, i′} χ (1 − \frac{i′ − i}{i′ − j} ) . (149)

As j varies over 𝔽_{p} \ {i, i′}, the argument 1 − (i′ − i)/(i′ − j) of χ in the last term in (149) varies over 𝔽_{p} \ {0, 1}. Since χ(1) = 1 and ∑_{0≤j<p} χ(j) = 0, we conclude from (149) that (148) does indeed hold.

Therefore, by Lemma 27, we have

| ∑_{a∈A, b∈B} χ(a − b)| ≤ \sqrt{(p − 1)|A||B|}  (150)

for all A and B ⊂ {0, …, p − 1}. Theorem 28 now follows from (150) in the same way that (95) follows from (87) (and the fact that E is circulant).

Acknowledgements

The authors are grateful to Eduardo Tengan and Norihide Tokushige for their careful reading of this paper and for their many comments. The authors are also most pleased to thank the referee for his or her very meticulous work.

References

1. N. Alon, Y. Kohayakawa, C. Mauduit, C. G. Moreira, and Rödl, Measures of pseudorandomness for finite sequences: typical values, in preparation. 1.1, 1.2

2. Noga Alon, Problems and results in extremal combinatorics. I, Discrete Math. 273 (2003), no. 1-3, 31–53, EuroComb’01 (Barcelona). MR 2005a:05208 2.1, 2.1, 2.1

3. Arturo Carpi and Aldo de Luca, Uniform words, Adv. in Appl. Math. 32 (2004), no. 3, 485–522. MR 2005a:68164 3.2.2

4. Julien Cassaigne, Christian Mauduit, and András 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.1, 1.1

5. Bruno Codenotti, Pavel Pudlák, and Giovanni Resta, Some structural properties of low-rank matrices related to computational complexity, Theoret. Comput. Sci. 235 (2000), no. 1, 89–107, Selected papers in honor of Manuel Blum (Hong Kong, 1998). MR 2001e:05078 2.1

6. N. G. de Bruijn, A combinatorial problem, Nederl. Akad. Wetensch., Proc. 49 (1946), 758–764, (Indagationes Math. 8 (1946), 461–467). MR 8,247d 3.1, 3.2.2

7. Paul Erdős and Joel 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 3.2.1

8. C. B. Haselgrove, Some theorems in the analytic theory of numbers, J. London Math. Soc. 26 (1951), 273–277. MR 13,438e 2.3.1 9. F. J. MacWilliams and N. J. A. Sloane, The theory of error-correcting codes. II, North-

Holland Publishing Co., Amsterdam, 1977, North-Holland Mathematical Library, Vol.

16. MR 57 #5408b 2.4

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

11. Christian Mauduit and András 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

12. Aimo Tietäväinen, Bounds for binary codes just outside the Plotkin range, Inform. and Control 47 (1980), no. 2, 85–93. MR 83f:94042 2.4

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