%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% AMSLaTeX file for the paper                                        %
%   Measures of pseudorandomness for finite sequences: typical values%
%   by N.~Alon, Y.~Kohayakawa, C.~Mauduit, C.~G.~Moreira and V.~Rodl %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: <Wednesday 12 Apr 2006 04:07:46pm BRT yoshi@erdos.ime.usp.br>
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[11pt,reqno]{amsart}
%\usepackage[latin1]{inputenc}
%\usepackage{amssymb,amscd,amsmath}     

%\usepackage{refcheck}
%\showrefnames
%\showcitenames

\usepackage[colorlinks,backref]{hyperref} 
%\usepackage{graphicx}
\usepackage{srcltx}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\def\ykcomm#1{\marginpar{\small\textsf{yk:} #1}}
\def\ykcomm#1{}
%\def\ykcommb#1{\marginpar{\small\textsf{ykyk:} #1}}
\def\ykcommb#1{}
\def\ykcommc#1{\marginpar{\small\textsf{yk3:} #1}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\def\endcase{\par\ifdim\lastskip<\smallskipamount
%                \removelastskip\penalty3000\smallskip\fi}
%\def\case#1.{\smallbreak
%\noindent 
%{\sl Case\/} #1.\enspace\ignorespaces}
%\def\casenodot#1 {\smallbreak
%\noindent 
%{\sl Case\/} #1\enspace\ignorespaces}
\def\endcasebody{\par\ifdim\lastskip<\smallskipamount
                \removelastskip\penalty-20\smallskip\fi}
\outer\def\endcasebodysquare{{\unskip\nobreak\hfil\penalty50
         \hskip2em\hbox{}\nobreak\hfil\square
         \parfillskip0pt\finalhyphendemerits=0\par}% TeXbook, p 106.
    {\ifdim\lastskip<\bigskipamount\removelastskip\penalty-10\bigskip\fi}}
\def\casebody{\noindent\ignorespaces}

%========================= Theorem .... styles ===============================
%From thmtest.tex, probably
\newtheoremstyle{note}% name
  {4pt}%      Space above
  {4pt}%      Space below 
  {\sl}%      Body font
  {}%         Indent amount (empty = no indent, \parindent = para indent)
  {\itshape}% Thm head font
  {.}%        Punctuation after thm head
  {.5em}%     Space after thm head: " " = normal interword space;
        %       \newline = linebreak
  {}%         Thm head spec (can be left empty, meaning `normal')

\newtheoremstyle{introthms}% name
  {3pt}%      Space above, empty = `usual value'
  {3pt}%      Space below
  {\itshape}% Body font
  {}%         Indent amount (empty = no indent, \parindent = para indent)
  {\bfseries}% Thm head font
  {.}%        Punctuation after thm head
  {.5em}%     Space after thm head: " " = normal interword space;
        %       \newline = linebreak
  {\thmnote{#3}}% Thm head spec

\theoremstyle{plain}
\newtheorem{theorem}              {Theorem} 
\newtheorem{algorithm}  [theorem] {Algorithm}
\newtheorem{axiom}      [theorem] {Axiom}      
\newtheorem{claim}      [theorem] {Claim}
\newtheorem{conjecture} [theorem] {Conjecture} 
\newtheorem{corollary}  [theorem] {Corollary} 
\newtheorem{fact}       [theorem] {Fact}    
\newtheorem{lemma}      [theorem] {Lemma}         
\newtheorem{problem}    [theorem] {Problem} 
\newtheorem{proposition}[theorem] {Proposition}
  
\theoremstyle{note}
\newtheorem{remark}    [theorem] {Remark}
\newtheorem{case}                {Case}  
\newtheorem{case.2}                {Case}  
\newtheorem{criterion} [theorem] {Criterion}
\newtheorem{definition}[theorem] {Definition}       
\newtheorem{example}   [theorem] {Example} 
\newtheorem{notation}  [theorem] {Notation}
\newtheorem{note}      [theorem] {Note}       
   
\theoremstyle{introthms}
\newtheorem*{varthm}{}% all text supplied in the note
%========================= Theorem .... styles ===============================

%========================= DRAFT =============================================
%\draft % Uncomment for double spaced draft text, with draft line printed
        % at the bottom of the page.
%next lines that is my style draft:
\special{!userdict begin /bop-hook{gsave 440 25 translate 45 rotate 2
setlinewidth /Times-Roman findfont 60 scalefont setfont 0 0 moveto
0.9 setgray (DRAFT) show -100 -10 moveto 400 -10 lineto stroke
-200 52 moveto 400 52 lineto stroke grestore}def end}

%========================= paper specific macros =============================
\def\({\left(}
\def\){\right)}
\def\[{\left[}
\def\]{\right]}
\def\<{\langle}
\def\>{\rangle}
\let\:\colon
\def\llfloor{\left\lfloor}
\def\rrfloor{\right\rfloor}
\def\llceil{\left\lceil}
\def\rrceil{\right\rceil}
\def\rmd{\text{\rm d}}
\def\wtc{\widetilde{c}\,}
\def\whc{\widehat{c}}
\def\wheta{\widehat\eta}
\def\wteta{\widetilde\eta}
\def\tbfE{\widetilde{\mathbf E}}
\def\wtm{\widetilde m}
\def\wtN{{\widetilde N}}
\def\wtP{\widetilde P}
\def\wtq{\widetilde q}
\def\wts{\widetilde s}
\def\whA{\widehat A}
\def\whB{\widehat B}
\def\whC{\widehat C}
\def\bfs{{\mathbf s}}
\def\bfE{{\mathbf E}}
\def\cA{{\mathcal A}}
\def\cB{{\mathcal B}}
\def\cBS{\cB_{\text{S}}}
\def\cBL{\cB_{\text{L}}}
\def\cD{{\mathcal D}}
\def\cE{{\mathcal E}}
\def\cF{{\mathcal F}}
\def\cG{{\mathcal G}}
\def\cM{{\mathcal M}}
\def\cN{{\mathcal N}}
\def\cS{{\mathcal S}}
%\def\cW{{\mathcal W}}
\def\PP{{\mathbb P}}
\def\EE{{\mathbb E}}
\def\NN{{\mathbb N}}
\def\RR{{\mathbb R}}
\def\ZZ{{\mathbb Z}}
\def\e{{\rm e}}
\def\inU{\mathrel{\in_U^{}}}
%\def\inU{\mathrel{\in_U}}
\def\cond{\;\big|\;}
\def\card{\mathop{\text{\rm card}}\nolimits}
\def\lcm{\mathop{\text{\rm lcm}}\nolimits}
\def\rank{\mathop{\text{\rm rank}}\nolimits}
\def\trace{\mathop{\text{\rm trace}}\nolimits}
\def\Ave{\mathop{\text{\rm Ave}}\nolimits}
\def\Bi{\mathop{\text{\rm Bi}}\nolimits}
\def\comp{^{\rm c}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\let\epsilon=\varepsilon
\let\tilde=\widetilde
%========================= paper specific macros =============================

\begin{document}
\title[Measures of pseudorandomness]%
{Measures of pseudorandomness for finite sequences: typical
  values}% (tentative title)} 

%========================= author info, thanks ===============================
\author[Alon]{N.~Alon}
\address{Raymond and Beverly Sackler Faculty of
 Exact Sciences, Tel Aviv University, Tel Aviv 69978, Israel} 
\email{noga@math.tau.ac.il}

\author[Kohayakawa]{Y.~Kohayakawa}
\address{Instituto de Matem\'atica e Estat\'{\i}stica, Universidade de
  S\~ao Paulo, Rua do Mat\~ao 1010, 05508--090~S\~ao Paulo, Brazil} 
\email{yoshi@ime.usp.br}

\author[Mauduit]{C.~Mauduit}
\address{Institut de Math\'ematiques de Luminy, CNRS-UPR9016, 163 av.\ de
  Luminy, case 907, F-13288, Marseille Cedex 9, France}   
\email{mauduit@iml.univ-mrs.fr}

\author[Moreira]{C.~G.~Moreira}
\address{IMPA, Estrada Dona Castorina 110, 22460--320~Rio de Janeiro, RJ,
  Brazil}  
\email{gugu@impa.br}

\author[R\"odl]{V.~R\"odl}
\address{Department of Mathematics and Computer Science, Emory
  University, Atlanta, GA 30322, USA}
\email{rodl@mathcs.emory.edu}

\thanks{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\'atico--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).}
%========================= author info, thanks ===============================

%========================= subjectclass, keywords ============================
\subjclass{68R15} % Combinatorics on words

\keywords{Random sequences, pseudorandom sequences, finite words, normality,
  correlation, well-distribution, discrepancy} 
%========================= subjectclass, keywords ============================

%\date{Working draft version 7.5, not for circulation. Copy produced on \today}
\date{Copy produced on \today.  \textbf{In progress; not for circulation!}}
\date{Copy produced on \today.}
%\date{\today}

%========================= abstract ==========================================
\begin{abstract}
  %We prove some cool theorems in this paper.
  Mauduit and S\'ark\"ozy introduced and studied certain numerical parameters
  associated to finite binary sequences $E_N\in\{-1,1\}^N$ in order to measure
  their `level of randomness'.  Those parameters, the \textit{normality
    measure}~$\cN(E_N)$, the \textit{well-distribution measure}~$W(E_N)$, and
  the \textit{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\'ark\"ozy (\textit{i})~investigated the relationship among those
  parameters and their minimal possible value,
  (\textit{ii})~estimated~$\cN(E_N)$, $W(E_N)$, and~$C_k(E_N)$ for certain
  explicitly constructed sequences~$E_N$ suggested to have a `pseudorandom
  nature', and (\textit{iii})~investigated the value of those parameters for
  genuinely random sequences~$E_N$.
  
  In this paper, we continue the work in the direction of~(\textit{iii}) above
  and determine the order of magnitude of~$\cN(E_N)$, $W(E_N)$, and~$C_k(E_N)$
  for typical~$E_N$.  We prove that, for most~$E_N\in\{-1,1\}^N$,
  both~$W(E_N)$ and~$\cN(E_N)$ are of order~$\sqrt N$, while~$C_k(E_N)$ is of
  order~$\sqrt{N\log{N\choose k}}$ for any given~$2\leq k\leq N/4$.
%  
%  We also prove a lower bound for the correlation measure~$C_k(E_N)$
%  ($k$~even) for arbitrary sequences~$E_N$, which, in particular, gives
%  that~$\min_{E_N}C_k(E_N)\geq c_k\sqrt N$ for some~$c_k>0$ for any constant
%  even~$k$.
\end{abstract}
%========================= abstract ==========================================

\maketitle
\thispagestyle{empty}
\newpage
\bgroup
%\vspace{-1truecm}
\small
\tableofcontents
%\thispagestyle{empty}
\egroup

%========================= introduction ======================================
\section{Introduction and statement of results}
\label{sec:intro}

\subsection{Measures of pseudorandomness for finite binary sequences}
\label{sec:Mauduit-Sarkozy}
In a series of papers, Mauduit and S\'ark\"ozy studied finite pseudorandom
binary sequences $E_N=(e_1,\dots,e_N)\in\{-1,1\}^N$.  In particular, they
investigated in~\cite{mauduit97} 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~\cite{mauduit02:_finit} and~\cite{mauduit97}.

Let~$k\in\NN$, $M\in\NN$, $X\in\{-1,1\}^k$, $a\in\ZZ$, $b\in\NN$, $b>0$, and
$D=(d_1,\dots,d_k)\in\NN^k$ with $0\leq d_1<\dots<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~$\sum S$ for the sum~$\sum_{s\in S}s$.  We let
\begin{multline}
  \label{eq:T_def}
  T(E_N,M,X)=\card\{n\:0\leq n<M,\;n+k\leq N,\text{ and }\\
  (e_{n+1},e_{n+2},\dots,e_{n+k})=X\},
\end{multline}
\begin{multline}
  \label{eq:U_def}
  U(E_N,M,a,b)=\sum\{e_{a+jb}\:1\leq j\leq M,\;
  1\leq a+jb\leq N\text{ for all~$j$}\},
\end{multline}
and
\begin{equation}
  \label{eq:V_def}
  V(E_N,M,D)=\sum\{e_{n+d_1}e_{n+d_2}\dots e_{n+d_k}\:
  1\leq n\leq M,\;n+d_k\leq N\}.
\end{equation}
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,\dots,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,\dots,d_k)$.

The \textit{normality measure} of~$E_N$ is defined as
\begin{equation}
  \label{eq:N_def}
  \cN(E_N)=\max_k\max_X\max_M
  \left|T(E_N,M,X)-{M\over2^k}\right|,
\end{equation}
where the maxima are taken over all~$k\leq\log_2N$, $X\in\{-1,1\}^k$,
and~$0<M\leq N+1-k$.  The \textit{well-distribution measure} of~$E_N$ is
defined as
\begin{multline}
  \label{eq:W_def}
  W(E_N)=\max\{|U(E_N,M,a,b)|\:\\
  \text{$a$, $b$, and~$M$ such that $1\leq a+b<a+Mb\leq N$}\}.
\end{multline}
Finally, the \textit{correlation measure of order~$k$} of~$E_N$
is defined as 
\begin{equation}
  \label{eq:C_k_def}
  C_k(E_N)=\max\{|V(E_N,M,D)|\:\text{$M$ and~$D$ such that $M+d_k\leq N$}\}. 
\end{equation}

\subsection{Typical values of~$W(E_N)$, $C_k(E_N)$, and~$\cN(E_N)$}
\label{sec:typical_values}
In~\cite{cassaigne02}, Cassaigne, Mauduit, and S\'ark\"ozy 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.)

\begin{varthm}[Theorem~A]
  For all~$\epsilon>0$, there are numbers~$N_0=N_0(\epsilon)$
  and~$\delta=\delta(\epsilon)>0$ such that for~$N\geq N_0$ we have
  \begin{equation}
    \label{eq:thmA}
    \delta\sqrt N<W(E_N)<6\sqrt{N\log N}
  \end{equation}
  with probability at least~$1-\epsilon$.
\end{varthm}

\begin{varthm}[Theorem~B]
  For every integer~$k\geq2$ and real~$\epsilon>0$, there are
  numbers~$N_0=N_0(\epsilon,k)$ and~$\delta=\delta(\epsilon,k)>0$ such that
  for all~$N\geq N_0$ we have
  \begin{equation}
    \label{eq:thmB}
    \delta\sqrt N<C_k(E_N)<5\sqrt{kN\log N}
  \end{equation}
  with probability at least~$1-\epsilon$.
\end{varthm}

% \begin{varthm}[Theorem~C]
%   For all $k$ and $N\in\NN$ with~$2\leq k\leq N$, we have
%   \begin{enumerate}
%   \item[(\textit{i})]$\min\{C_k(E_N)\:E_N\in\{-1,1\}^N\}=1$ if~$k$ is odd,
%   \item[(\textit{ii})]$\min\{C_k(E_N)\:E_N\in\{-1,1\}^N\}\geq\log_2(N/k)$
%     if~$k$ is even.
%   \end{enumerate}
% \end{varthm}

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\H os and Spencer.  Indeed, an
argument in~\cite[Chapter~8]{erdos74:_probab} tells us that one may drop the
logarithmic factor in~\eqref{eq:thmA}, at the expense of increasing the
multiplicative constant.

% Let us also observe that it follows from the results of
% Roth~\cite{roth64:_remar} and Matou\v sek and Spencer~\cite{matousek96:_discr}
% that the order of magnitude of
% $$
% \min\big\{W(E_N)\:E_N\in\{-1,1\}^N\big\}
% $$
% is~$N^{1/4}$.  In~\cite{cassaigne02}, it is conjectured that for any
% even~$k\geq2$ there is a constant~$c>0$ such that for~$N\to\infty$ we have
% $$
% \min\big\{C_k(E_N)\:E_N\in\{-1,1\}^N\big\}\gg N^c,
% $$
% which would be a considerable strengthening of Theorem~C(\textit{ii}).

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

% we prove the conjecture above in a more general form, and we give a result
% concerning the typical value of~$\cN(E_N)$.  We shall prove the following
% results.

\begin{theorem}
  \label{thm:order_of_W}
  For any given~$\epsilon>0$ there exist~$N_0$ and~$\delta>0$ such that
  if~$N\geq N_0$, then
  \begin{equation}
    \label{eq:order_of_W}
    \delta\sqrt N<W(E_N)<{1\over\delta}\sqrt N
  \end{equation}
  with probability at least~$1-\epsilon$.
\end{theorem}

Theorem~\ref{thm:order_of_W} above is essentially proved in Erd\H os and
Spencer~\cite[Chapter~8]{erdos74:_probab}.  However, we give our alternative
proof for this result because an idea in this proof is also used in the proofs
of Theorems~\ref{thm:order_of_N}, \ref{thm:small_W}, and~\ref{thm:small_cN}
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$.

\begin{theorem}
  \label{thm:order_of_C_k}
  Let~$0<\epsilon_0\leq1/16$ be fixed and
  let~$\epsilon_1=\epsilon_1(N)=(\log\log N)/\log N$.  There is a
  constant~$N_0=N_0(\epsilon_0)$ such that if~$N\geq N_0$, then, with
  probability at least~$1-\epsilon_0$, we have
  \begin{multline}
    \label{eq:order_of_C_k}
    {2\over5}\sqrt{N\log{N\choose k}}
    <C_k(E_N)
    <\sqrt{(2+\epsilon_1)N\log\(N{N\choose k}\)}\\
    <\sqrt{(3+\epsilon_0)N\log{N\choose k}}
    <{7\over4}\sqrt{N\log{N\choose k}}
  \end{multline}
  for every integer~$k$ with~$2\leq k\leq N/4$.
\end{theorem}

Our next result tells us that~$C_k(E_N)$ is concentrated around its
mean~$\EE(C_k)$ in the case in which~$k$ is
small.\ykcomm{Theorem~\ref{thm:C_k_concentrated} changed a little.  For some
  reason, we used to have the median instead of the expectation~$\EE(C_k)$.}

\begin{theorem}
  \label{thm:C_k_concentrated}
  For any fixed constant~$\epsilon>0$ and any integer function~$k=k(N)$
  with~$2\leq k\leq\log N-\log\log N$, there is a constant~$N_0$ for which the
  following holds.  If~$N\geq N_0$, then the probability that
  \begin{equation}
    \label{eq:C_k_concentrated}
    1-\epsilon<{C_k(E_N)\over\EE(C_k)}<1+\epsilon
  \end{equation}
  holds is at least~$1-\epsilon$.
\end{theorem}

We suspect that the upper bound on~$k$ in Theorem~\ref{thm:C_k_concentrated}
may be weakened.  We now turn to the normality measure~$\cN(E_N)$.

\begin{theorem}
  \label{thm:order_of_N}
  For any given~$\epsilon>0$ there exist~$N_0$ and~$\delta>0$ such that
  if~$N\geq N_0$, then
  \begin{equation}
    \label{eq:order_of_N}
    \delta\sqrt N<\cN(E_N)<{1\over\delta}\sqrt N
  \end{equation}
  with probability at least~$1-\epsilon$.
\end{theorem}

% Finally, we state our result concerning the minimal possible value
% for the parameter~$C_k(E_N)$. 

% \begin{theorem}
%   \label{thm:minC_k_lwbd}
%   If~$k$ and~$N$ are natural numbers with~$k$ even and~$2\leq k\leq N$,
%   then
%   \begin{equation}
%     \label{eq:minC_k_lwbd}
%     C_k(E_N)>\sqrt{N\over3(k+1)}
%   \end{equation}
%   for any~$E_N\in\{-1,1\}^N$.
% \end{theorem}

%We mention that we found it quite surprising that one may determine the order
%of magnitude of the typical correlation~$C_k(E_N)$ for~$k$ as large as
%proportional to~$N$.  

We shall show that the lower bounds in
Theorems~\ref{thm:order_of_W}\ykcomm{Theorems~\ref{thm:small_W}
  and~\ref{thm:small_cN} are the latest additions.}  and~\ref{thm:order_of_N}
(i.e., the lower bounds in~\eqref{eq:order_of_W} and~\eqref{eq:order_of_N})
are in a sense best possible.  In Section~\ref{sec:small_flucts} we prove the
following two results.

\begin{theorem}
  \label{thm:small_W}
  For any~$\delta>0$, there is~$c(\delta)>0$ and~$N_0=N_0(\delta)$ such that,
  for any~$N\geq N_0$, we have
  \begin{equation}
    \label{eq:small_W}
    \PP(W(E_N)<\delta\sqrt N)>c(\delta).
  \end{equation}
\end{theorem}

\begin{theorem}
  \label{thm:small_cN}
  For any~$\delta>0$, there is~$c(\delta)>0$ and~$N_0=N_0(\delta)$ such that,
  for any~$N\geq N_0$, we have
  \begin{equation}
    \label{eq:small_cN}
    \PP(\cN(E_N)<\delta\sqrt N)>c(\delta).
  \end{equation}
\end{theorem}

In Section~\ref{sec:concluding}, we make some simple remarks to show that the
upper bounds in~\eqref{eq:order_of_W} and~\eqref{eq:order_of_N} are in a sense
best possible.  Those remarks and Theorems~\ref{thm:small_W}
and~\ref{thm:small_cN} tells us that~$W(E_N)/\sqrt N$ and~$\cN(E_N)/\sqrt N$
do not converge in distribution as~$N\to\infty$ to a distribution that is
concentrated at a point.

\subsection{Minimal values of~$W(E_N)$, $C_k(E_N)$, and~$\cN(E_N)$}
\label{sec:minimal_values}
The minimal possible values of~$W(E_N)$, $C_k(E_N)$, and~$\cN(E_N)$ have also
been investigated in the literature, see, e.g.,
\cite{alon04:_measur_minimal,cassaigne02,matousek96:_discr,roth64:_remar}.  We
include this brief section for the convenience of the reader.  It follows from
the classical results of Roth~\cite{roth64:_remar} and Matou\v sek and
Spencer~\cite{matousek96:_discr} that the order of magnitude of
\begin{equation}
  \label{eq:Roth+Matousek-Spencer}
  \min\big\{W(E_N)\:E_N\in\{-1,1\}^N\big\}
\end{equation}
is~$N^{1/4}$.  For any fixed even~$k\geq2$, the order of magnitude
of~$\min_{E_N}C_k(E_N)$, where the minimum is again taken over
all~$E_N\in\{-1,1\}^N$, has been established up to a polylogarithmic factor
recently:
\begin{equation}
  \label{eq:C_2_minimal_order}
  \sqrt{{1\over2}{\llfloor N\over k+1\rrfloor}}
  <\min_{E_N}C_k(E_N)\leq{7\over4}\sqrt{kN\log N},
\end{equation}
where we suppose~$N\geq N_0(k)$ for the upper bound.  The lower bound
in~\eqref{eq:C_2_minimal_order} is proved in~\cite{alon04:_measur_minimal},
whereas the upper bound in~\eqref{eq:C_2_minimal_order} follows from
Theorem~\ref{thm:order_of_C_k} 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~\cite{alon04:_measur_minimal}.

% In~\cite{alon04:_measur_minimal}, for all large enough~$N$, an explicit,
% algebraic construction based on finite fields for a sequence~$E_N$ with
% \begin{equation}
%   \label{eq:E_N_with_small_cN}
%   \cN(E_N)\leq3N^{1/3}(\log N)^{2/3}
% \end{equation}
% is given.  

Turning to the normality measure~$\cN(E_N)$, we mention that the best bounds
that we know of for the minimal value of~$\cN(E_N)$ ($E_N\in\{-1,1\}^N$) are
as follows:
\begin{equation}
  \label{eq:min_cN_ineqs}
  \({1\over2}+o(1)\)\log_2N
  \leq\min_{E_N}\cN(E_N)
  \leq3N^{1/3}(\log N)^{2/3}
\end{equation}
for all large enough~$N$.  The upper bound in~\eqref{eq:min_cN_ineqs} is
proved in~\cite{alon04:_measur_minimal} constructively, where a suitable,
explicit algebraic construction based on finite fields is given.  It is
interesting to compare the upper bounds in~\eqref{eq:min_cN_ineqs}
and~\eqref{eq:order_of_N} in Theorem~\ref{thm:order_of_N}.  The lower bound
in~\eqref{eq:min_cN_ineqs} may be proved simply (see the remarks at the end of
Section~\ref{sec:cN_of_random}).  It would be interesting to close the rather
wide gap in~\eqref{eq:min_cN_ineqs}.  The following problem was already raised
in~\cite{alon04:_measur_minimal}.\ykcomm{Vojta and I would be willing to
  conjecture that the answer to Problem~\ref{prob:min_cN} is `yes'.  Should we
  state this?  We could add the sentence ``The authors believe that the answer
  to Problem~\ref{prob:min_cN} is positive''.  What do you all think?}

\begin{problem}
  \label{prob:min_cN}
  Is there an absolute constant~$\alpha>0$ for which we
  have
  \begin{equation}
    \label{eq:min_cN_prob}
    \min_{E_N}\cN(E_N)>N^\alpha
  \end{equation}
  for all large enough~$N$?
\end{problem}

The authors believe that the answer to Problem~\ref{prob:min_cN} is positive. 

\section{Estimates for~$W(E_N)$, $C_k(E_N)$, and~$\cN(E_N)$ for random
  sequences~$E_N$}
\label{sec:random}

We shall prove Theorems~\ref{thm:order_of_W}--\ref{thm:order_of_N} 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.

\subsection{Estimates for the binomial distribution}
\label{sec:binom}
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.,
\cite[Chapter~I, Theorem~6]{BBf}).  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$.

\begin{fact}
  \label{fact:1/2Bin}
  \begin{enumerate}
  \item[(\textit{i})]For any~$\ell=\ell(n)\in\ZZ$ with~$\ell=o(n^{2/3})$, we have
    \begin{multline}
      \label{eq:single_bin}
      \qquad
      \PP\(S(n,1/2)=\llfloor n\over2\rrfloor+\ell\)
      ={1\over2^n}{n\choose\lfloor n/2\rfloor+\ell}\\
      =\sqrt{2\over\pi n}\;e^{-2\ell^2/n}(1+o(1)),\qquad
    \end{multline}
  \item[(\textit{ii})]For any~$c=c(n)>0$ with~$c=o(n^{1/6})$, we have 
    \begin{multline}
      \label{eq:tails1}
      \PP\(S(n,1/2)\geq\llfloor n\over2\rrfloor+c\sqrt n\)
      =\sum_{\ell\geq c\sqrt n}{1\over2^n}{n\choose\lfloor n/2\rfloor+\ell}\\
      =\(\sqrt{2\over\pi}+o(1)\)\(\int_c^\infty e^{-2x^2}\rmd x\).
    \end{multline}
    In particular, if we further have that~$c\to\infty$, then 
    \begin{equation}
      \label{eq:tails2}
      \PP\(S(n,1/2)\geq\llfloor n\over2\rrfloor+c\sqrt n\)
%      \sum_{\ell\geq c\sqrt n}{1\over2^n}{n\choose\lfloor n/2\rfloor+\ell}
      ={e^{-2c^2}\over2c\sqrt{2\pi}}(1+o(1)).
    \end{equation}
  \item[(\textit{iii})]The estimates~\eqref{eq:tails1} and~\eqref{eq:tails2}
    hold for the lower tail
    $$
    \PP\(S(n,1/2)\leq\llfloor n\over2\rrfloor-c\sqrt n\)
%    \sum_{\ell\leq-c\sqrt n}{n\choose\lfloor pn\rfloor+\ell}p^\ellq^{n-\ell}
    $$
    as well.
  \end{enumerate}
\end{fact}

%Note that, by symmetry, the estimates in~\eqref{eq:tails1}
%and~\eqref{eq:tails2} hold for the lower tail
%\begin{equation*}
%  \PP\(S(n,1/2)\leq\llfloor n\over2\rrfloor-c\sqrt n\).
%  \sum_{k\leq-c\sqrt n}{1\over2^n}{n\choose\lfloor n/2\rfloor+k}.
%\end{equation*}
% In Section~\ref{sec:cN_of_random}, we shall need a more general form of
% Fact~\ref{fact:1/2Bin}, namely, we shall need the corresponding estimates
% for~$S(n,p)$ for arbitrary constant~$0<p<1$.

% \begin{fact}
%   \label{fact:pBin}
%   Let~$0<p<1$ be a constant and let~$q=1-p$.  
%   \begin{enumerate}
%   \item[(\textit{i})]For any~$k=k(n)\in\ZZ$ with~$k=o(n^{2/3})$, we have
%     \begin{multline}
%       \label{eq:psingle_bin}
%       \qquad
%       \PP\big(S(n,p)=\lfloor pn\rfloor+k\big)
%       ={n\choose\lfloor pn\rfloor+k}p^kq^{n-k}\\
%       ={(1+o(1))\over\sqrt{2pq\pi n}}e^{-k^2/2npq},\qquad
%     \end{multline}
%   \item[(\textit{ii})]For any~$c=c(n)>0$ with~$c=o(n^{1/6})$, we have 
%     \begin{multline}
%       \label{eq:ptails1}
%       \PP\big(S(n,p)\geq\lfloor pn\rfloor+c\sqrt n\big)
%       =\sum_{k\geq c\sqrt n}{n\choose\lfloor pn\rfloor+k}p^kq^{n-k}\\
%       ={1\over\sqrt{2pq\pi}}\(\int_c^\infty e^{-x^2/2pq}\rmd x\)(1+o(1)).
%     \end{multline}
%     In particular, if we further have that~$c\to\infty$, then 
%     \begin{equation}
%       \label{eq:ptails2}
%       \PP\big(S(n,p)\geq\lfloor pn\rfloor+c\sqrt n\big)
% %      \sum_{k\geq c\sqrt n}{1\over2^n}{n\choose\lfloor n/2\rfloor+k}
%       ={1\over c}\sqrt{pq\over2\pi}e^{-c^2/2pq}(1+o(1)).
%     \end{equation}
%   \item[(\textit{iii})]The estimates~\eqref{eq:ptails1} and~\eqref{eq:ptails2}
%     hold for the lower tail
%     $$
%     \PP\big(S(n,p)\leq\lfloor pn\rfloor-c\sqrt n\big)
% %    \sum_{k\leq-c\sqrt n}{n\choose\lfloor pn\rfloor+k}p^kq^{n-k}
%     $$
%     as well.
%   \end{enumerate}
% \end{fact}

% We now state a well known asymptotic formula for the tail of the normal
% distribution.  The reader may observe that the cases in which~$c\to\infty$ in
% Facts~\ref{fact:1/2Bin}(\textit{ii}) and~\ref{fact:pBin}(\textit{ii}) follow
% from Fact~\ref{fact:normal_int} below.

% \begin{fact}
%   \label{fact:normal_int}
%   Let~$\phi(x)=(2\pi)^{-1/2}e^{-t^2/2}$
%   and~$\Phi(x)=\int_{-\infty}^x\phi(t)\rmd t$.  Then
%   \begin{equation}
%     \label{eq:normal_asymp}
%     1-\Phi(x)=(1+o(1)){1\over x}\phi(x),
%   \end{equation}
%   where~$o(1)\to0$ as~$x\to\infty$.
% \end{fact}

In what follows, we shall often be concerned with sums of~$\pm1$ independent
random variables.  We let
\begin{equation}
  \label{eq:pmS_def}
  S^\pm(n)=\sum_{1\leq i\leq n}X_i
\end{equation}
where~$X_i$ $(1\leq i\leq n)$ are independent random variables with mean~$0$,
that is,
$$
\PP(X_i=-1)=\PP(X_i=+1)=1/2.
$$
Clearly, $(S^\pm(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^\pm(n)$ (see, e.g., \cite[Appendix~A]{alon00:_prob_method}).

\begin{fact}
  \label{fact:large_dev}
  Let~$X_i$ $(1\leq i\leq n)$ be independent~$\pm1$ random variables with
  mean~$0$.  Let~$S^\pm(n)=\sum_{1\leq i\leq n}X_i$.  For any real
  number~$a>0$, we have
  \begin{equation}
    \label{eq:large_dev}
    \PP(S^\pm(n)>a)<e^{-a^2/2n}.
  \end{equation}
\end{fact}

% The next two results are on~$\Bi(n,1/2)$, and hence are similar to
% Fact~\ref{fact:1/2Bin}, but they are formulated so that the bounds are valid
% for essentially any deviation from the mean.

% \begin{fact}
%   \label{fact:1/2BinU}
%   Let~$n$ and~$k$ be non-negative integers.
%   \begin{enumerate}
%   \item[(\textit{i})]We have\ykcomm{%
%       I'll start addressing the issue as to whether or not replace
%       Fact~\ref{fact:1/2BinU}.  Gugu sent me a proof of (a very slight
%       variant) Fact~\ref{fact:1/2BinUlwbd} that doesn't use the proof of
%       Fact~\ref{fact:1/2BinU}.  So I'll now check what has to be changed if we
%       change Fact~\ref{fact:1/2BinU}.
%     }%\ykcomm{The error term may be
%     % improved.} 
%     \begin{multline}
%       \label{eq:single_binU}
%       \PP\(S(n,1/2)=\llfloor n\over2\rrfloor+k\)
%       ={1\over2^n}{n\choose\lfloor n/2\rfloor+k}\\
%       \leq\sqrt{2\over\pi n}\;e^{-2k^2/n}\(1+O\((\log n)^2\over n^{1/3}\)\). 
%     \end{multline}
%     Therefore, 
%     \begin{equation}
%       \label{eq:single_binU2}
%       \qquad
%       \PP\(S(n,1/2)=\llfloor n\over2\rrfloor+k\)
%       \leq{4\over5\sqrt n}e^{-2k^2/n}
%       <{1\over\sqrt n}e^{-2k^2/n}
%     \end{equation}
%     for all large enough~$n$.
%   \item[(\textit{ii})]We have
% %\ykcomm{Perhaps state this with $1+o(1)$?  That
% %is, with coefficient $\sim(1/2k)\sqrt{n/2\pi}$?  Check later.}
%     \begin{multline}
%       \label{eq:tails1U}
%       \PP\(S(n,1/2)\geq\llfloor n\over2\rrfloor+k\)
%       ={1\over2^n}\sum_{j\geq k}{n\choose\lfloor n/2\rfloor+j}\\
%       \leq\({3\over4}\sqrt{2\over\pi}+o(1)\){\sqrt n\over k}e^{-2k^2/n}.
%     \end{multline}
%     Moreover, both~$\PP\big(S(n,1/2)\geq n/2+k\big)$ and~$\PP\big(S(n,1/2)\leq
%     n/2-k\big)$ are bounded by the probability in~\eqref{eq:tails1U}, and
%     hence
%     \begin{equation}
%       \label{eq:tails1Ub}
%       \PP\(\left|S(n,1/2)-{n\over2}\right|\geq k\)
%       \leq\({3\over2}\sqrt{2\over\pi}+o(1)\){\sqrt n\over k}e^{-2k^2/n}.
%     \end{equation}
%   \end{enumerate}
% \end{fact}
% \begin{proof}
%   The inequalities in this lemma are easily seen to hold if~$|k|>n/2$, and hence
%   we suppose throughout that
%   \begin{equation}
%     \label{eq:k_non_trivial}
%     |k|\leq{n\over2}.
%   \end{equation}
%   Furthermore, we may and shall suppose that~$n$ is larger than a suitably
%   large constant.  We first prove~\eqref{eq:single_binU}.
  
%   Let us first consider the case in which
%   \begin{equation}
%     \label{eq:very_large_k}
%     k\geq\llceil n\over2\rrceil-\llfloor n\over(\log n)^2\rrfloor
%   \end{equation}
%   or else
%   \begin{equation}
%     \label{eq:very_small_k}
%     k\leq-\llfloor n\over2\rrfloor+\llfloor n\over(\log n)^2\rrfloor. 
%   \end{equation}
%   If~\eqref{eq:very_large_k} holds, then
%   \begin{multline}
%     \label{eq:extreme_k}
%     {1\over2^n}{n\choose\lfloor n/2\rfloor+k}
%     \leq{1\over2^n}{n\choose n-\lfloor n/(\log n)^2\rfloor}\\
%     ={1\over2^n}{n\choose\lfloor n/(\log n)^2\rfloor}
%     \leq2^{-n}n^{n/(\log n)^2}
%     =2^{-n}e^{n/\log n}.
%   \end{multline}
%   Observe that the right-hand side of~\eqref{eq:single_binU} is at least 
%   \begin{equation}
%     \label{eq:RHS-lwbd}
%     (1+o(1))\sqrt{2\over\pi n}e^{-n/2}
%   \end{equation}
%   because~$|k|\leq n/2$.  Comparing~\eqref{eq:extreme_k}
%   and~\eqref{eq:RHS-lwbd}, we see that if~$n$ is large enough
%   and~\eqref{eq:very_large_k} holds, then~\eqref{eq:single_binU} does hold.
%   The case in which~\eqref{eq:very_small_k} holds is very similar, and hence
%   we omit the details.  We have proved~\eqref{eq:single_binU} in the case in
%   which either~\eqref{eq:very_large_k} or~\eqref{eq:very_small_k} holds.  In
%   what follows, we suppose that~\eqref{eq:very_large_k}
%   and~\eqref{eq:very_small_k} fail; equivalently, we suppose that
%   \begin{equation}
%     \label{eq:not_so_large_k}
%     \llceil n\over2\rrceil-k>{n\over(\log n)^2}
%   \end{equation}
%   and
%   \begin{equation}
%     \label{eq:not_so_small_k}
%     \llfloor n\over2\rrfloor+k>{n\over(\log n)^2}.
%   \end{equation}
%   As usual, for a real number~$x$, we write~$\{x\}$ for the fractional part
%   of~$x$; that is, $\{x\}=x-\lfloor x\rfloor$.  Let
%   \begin{equation}
%     \label{eq:alpha_def}
%     \alpha={1\over n}\(k-\left\{n\over2\right\}\).
%   \end{equation}
%   Then~$\lfloor n/2\rfloor+k=n(1/2+\alpha)$ and~$\lceil
%   n/2\rceil-k=n(1/2-\alpha)$.  Recalling that~\eqref{eq:not_so_large_k}
%   and~\eqref{eq:not_so_small_k} hold, using that
%   \begin{equation}
%     \label{eq:Stirling}
%     N!=\sqrt{2\pi N}\(N\over e\)^N\(1+O\(1\over N\)\),
%   \end{equation}
%   we may deduce that
%   \begin{equation}
%     \label{eq:binom_main_expression}
%     {1\over2^n}{n\choose\lfloor n/2\rfloor+k}
%     =\(1+O\((\log n)^2\over n\)\)
%     {e^{-nf(\alpha)}\over\sqrt{2\pi n(1/4-\alpha^2)}},
%   \end{equation}
% %   \begin{multline}
% %     \label{eq:binom_main_expression}
% %     {1\over2^n}{n\choose\lfloor n/2\rfloor+k}
% %     =\(1+O\((\log n)^2\over n\)\)
% %     {e^{-nf(n)}\over\sqrt{2\pi n(1/4-\alpha^2)}}\\
% %     \leq\(1+O\((\log n)^2\over n\)\)\sqrt{2\over\pi n}e^{-nf(n)},
% %   \end{multline}
%   where
%   \begin{equation}
%     \label{eq:f(alpha)_def}
%     f(\alpha)=\({1\over2}+\alpha\)\log\({1\over2}+\alpha\)
%     +\({1\over2}-\alpha\)\log\({1\over2}-\alpha\)+\log2.
%   \end{equation}

%   We have
%   \begin{equation}
%     \label{eq:f(alpha)2deriv}
%     {\rmd^2\over\rmd\alpha^2}f(\alpha)
%     =\({1\over2}+\alpha\)^{-1}+\({1\over2}-\alpha\)^{-1},
%   \end{equation}
%   \begin{equation}
%     \label{eq:f(alpha)4deriv}
%     {\rmd^4\over\rmd\alpha^4}f(\alpha)
%     =2\({1\over2}+\alpha\)^{-3}+2\({1\over2}-\alpha\)^{-3},
%   \end{equation}
%   and
%   \begin{equation}
%     \label{eq:f(alpha)6deriv}
%     {\rmd^6\over\rmd\alpha^6}f(\alpha)
%     =24\({1\over2}+\alpha\)^{-5}+24\({1\over2}-\alpha\)^{-5}>0.
%   \end{equation}
%   Since~$f(\alpha)$ is even, we have $f(0)=f'(0)=f'''(0)=f^{(5)}(0)=0$.  Also,
%   $f''(0)=4$ and~$f^{(4)}(0)=32$.  Therefore, for all~$\alpha$ there
%   is~$0<\xi<\alpha$ such that
%   \begin{equation}
%     \label{eq:f(alpha)_Taylor}
%     f(\alpha)=2\alpha^2+{4\over3}\alpha^4+{1\over6!}f^{(6)}(\xi)\alpha^6
%     \geq2\alpha^2+{4\over3}\alpha^4,
%   \end{equation}
%   with strict inequality if~$\alpha\neq0$.  We now observe
%   that~\eqref{eq:f(alpha)_Taylor} implies that
%   \begin{equation}
%     \label{eq:f(alpha)_lwbd1}
%     f(\alpha)\geq2\alpha^2=2\({1\over n}\(k-\left\{n\over2\right\}\)\)^2
%     \geq2{k^2\over n^2}-2{k\over n^2}.
%   \end{equation}
%   Recalling~\eqref{eq:binom_main_expression}, we obtain that
%   \begin{equation}
%     \label{eq:binom_main_expression2}
%     {1\over2^n}{n\choose\lfloor n/2\rfloor+k}
%     \leq\(1+O\((\log n)^2\over n\)\)
%     {e^{-2k^2/n+2k/n}\over\sqrt{2\pi n(1/4-k^2/n^2)}}.
%   \end{equation}
%   Suppose now that
%   \begin{equation}
%     \label{eq:small_k}
%     k<n^{2/3}\log n.
%   \end{equation}
%   Then~\eqref{eq:binom_main_expression2} gives that
%   \begin{equation}
%     \label{eq:binom_main_expression2b}
%     {1\over2^n}{n\choose\lfloor n/2\rfloor+k}
%     \leq\(1+O\(\log n\over n^{1/3}\)\)\sqrt{2\over\pi n}\;e^{-2k^2/n},
%   \end{equation}
%   and~\eqref{eq:single_binU} is proved.  If~\eqref{eq:small_k} fails, that is,
%   \begin{equation}
%     \label{eq:large_k}
%     k\geq n^{2/3}\log n, 
%   \end{equation}
%   then a little calculation based on~\eqref{eq:f(alpha)_Taylor} gives that
%   \begin{equation}
%     \label{eq:eq:f(alpha)_lwbd2}
%     f(\alpha)\geq2k^2/n^2+k^4/n^4
%   \end{equation}
%   for all large enough~$n$.  Therefore, in this case,
%   \eqref{eq:binom_main_expression}~gives that
%   \begin{equation}
%     \label{eq:binom_main_expression3}
%     {1\over2^n}{n\choose\lfloor n/2\rfloor+k}
%     \leq\(1+O\((\log n)^2\over n\)\)
%     \sqrt{2\over\pi n(1-4k^2/n^2)}\;e^{-2k^2/n-k^4/n^3}.
%   \end{equation}
%   Using~\eqref{eq:not_so_large_k} and~\eqref{eq:not_so_small_k}, we deduce that
%   \begin{equation}
%     \label{eq:poly_bother1}
%     \sqrt{1\over(1-4k^2/n^2)}=O\((\log n)^2\).
%   \end{equation}
%   Thus, if~$|k|\geq n^{3/4}\log n$, we have
%   \begin{equation}
%     \label{eq:poly_bother2}
%     \sqrt{1\over(1-4k^2/n^2)}\;e^{-k^4/n^3}
%     =O\((\log n)^2\)e^{-(\log n)^4}\ll1.
%   \end{equation}
%   On the other hand, if~$|k|<n^{3/4}\log n$, then
%   \begin{equation}
%     \label{eq:poly_bother3}
%     \sqrt{1\over(1-4k^2/n^2)}\;e^{-k^4/n^3}
%     =1+O\((\log n)^2\over n^{1/2}\).
%   \end{equation}
%   Therefore, for all~$k$ satisfying~\eqref{eq:large_k},
%   inequality~\eqref{eq:binom_main_expression3} reduces to
%   \begin{equation}
%     \label{eq:eq:binom_main_expression4}
%     {1\over2^n}{n\choose\lfloor n/2\rfloor+k}
%     \leq\(1+O\((\log n)^2\over n^{1/2}\)\)
%     \sqrt{2\over\pi n}\;e^{-2k^2/n},
%   \end{equation}
%   proving~\eqref{eq:single_binU}, as required.  The inequalities
%   in~\eqref{eq:single_binU2} follow easily from~\eqref{eq:single_binU}, and
%   hence~(\textit{i}) is proved.

%   We now turn to~(\textit{ii}).  We have
%   \begin{multline}
%     \label{eq:int_estimate}
%     {1\over2^n}\sum_{j\geq k}{n\choose\lfloor n/2\rfloor+j}\\
%     \leq(1+o(1))\(\sqrt{2\over\pi n}e^{-2k^2/n}
%     +\int_{k/\sqrt n}^\infty\sqrt{2\over\pi}\;e^{-2x^2}\rmd x\).
%   \end{multline}
%   Letting~$y=x\sqrt2$, we obtain that the integral on the right-hand side
%   of~\eqref{eq:int_estimate} is~$\pi^{-1/2}\int_{k\sqrt{2/n}}^\infty
%   e^{-y^2}\rmd y$.  However,
%   \begin{multline*}
%     \int_c^\infty e^{-y^2}\rmd y
%     =\int_0^\infty e^{-(t+c)^2}\rmd t\\
%     =e^{-c^2}\int_0^\infty e^{-2ct-t^2}\rmd t
%     \leq e^{-c^2}\int_0^\infty e^{-2ct}\rmd t
%     ={e^{-c^2}\over2c},
%   \end{multline*}
%   whence
%   \begin{equation}
%     \label{eq:int_estimate.aux}
%     \sqrt{1\over\pi}\int_{k\sqrt{2/n}}^\infty e^{-y^2}\rmd y
%     \leq{1\over2k}\sqrt{n\over2\pi}e^{-2k^2/n}.
% %    ={\sqrt n\over5k}e^{-2k^2/n}.
%   \end{equation}
%   Putting together~\eqref{eq:int_estimate} and~\eqref{eq:int_estimate.aux}, we
%   get that 
%   \begin{multline*}
%     {1\over2^n}\sum_{j\geq k}{n\choose\lfloor n/2\rfloor+j}
%     \leq(1+o(1))\(\sqrt{2\over\pi
%     n}+{1\over2k}\sqrt{n\over2\pi}\)e^{-2k^2/n}\\ 
%     \leq\({3\over4}\sqrt{2\over\pi}+o(1)\){\sqrt n\over k}e^{-2k^2/n},
%   \end{multline*}
%   as required.
% \end{proof}

We now prove a lower estimate for the symmetric binomial distribution.  As
usual, we let~$\{x\}=x-\lfloor x\rfloor$.

\begin{fact}
  \label{fact:1/2BinUlwbd}
  Let~$n$ and~$\ell$ be integers with
  \begin{equation}
    \label{eq:k_n_condition}
    -\llfloor n\over2\rrfloor\leq\ell\leq\llceil n\over2\rrceil.
  \end{equation}
  If~$n$ is sufficiently large, then
  \begin{multline}
    \label{eq:single_binU_for_lwbd}
    \PP\(S(n,1/2)=\llfloor n\over2\rrfloor+\ell\)
    ={1\over2^n}{n\choose\lfloor n/2\rfloor+\ell}\\
    \geq2^{-4(\ell+\{n/2\})^2/n-n}{n\choose\lfloor n/2\rfloor}
    =(1+o(1))2^{-4(\ell+\{n/2\})^2/n}\sqrt{2\over\pi n}.
  \end{multline}
\end{fact}
\begin{proof}
  We shall in fact prove the following statement, which implies
  Fact~\ref{fact:1/2BinUlwbd}: 
  \begin{itemize}
  \item[(\dag)]\sl if~$0\leq\ell\leq n/2$ and~$n$ is large enough, then
    \begin{equation}
      \label{eq:single_binU_for_lwbdS}
      {n\choose\lfloor n/2\rfloor-\ell}\geq2^{-4(\ell+\{n/2\})^2/n}{n\choose\lfloor
        n/2\rfloor}.  
    \end{equation}
  \end{itemize}
  We remark that if~$n$ is even, or else if~$n$ is odd and~$\ell\leq0$,
  then~(\dag) is equivalent to what is claimed in Fact~\ref{fact:1/2BinUlwbd}.
  If~$n$ is odd and~$\ell>0$, then~(\dag) is slightly stronger, because in this
  case we have 
  \begin{multline}
    \label{eq:single_binU_for_lwbdSaux}
    {n\choose\lfloor n/2\rfloor+\ell}={n\choose\lceil n/2\rceil-\ell}
    ={n\choose\lfloor n/2\rfloor-\ell+1}\\
    \geq2^{-4(\ell-1+\{n/2\})^2/n}{n\choose\lfloor n/2\rfloor}
    \geq2^{-4(\ell+\{n/2\})^2/n}{n\choose\lfloor n/2\rfloor},
  \end{multline}
  where we used~\eqref{eq:single_binU_for_lwbdS} in the first inequality
  in~\eqref{eq:single_binU_for_lwbdSaux}.
  
  We shall now prove~(\dag).  Let
  \begin{equation}
    \label{eq:a(k)_def}
    a(\ell)=2^{4(\ell+\{n/2\})^2/n}{n\choose\lfloor n/2\rfloor-\ell}
  \end{equation}
  for all~$0\leq\ell\leq n/2$.  It is easy to check that
  \begin{equation}
    \label{eq:endpoints_OK}
    a(0),\;a(\lfloor n/2\rfloor)\geq{n\choose\lfloor n/2\rfloor}
  \end{equation}
  for all large enough~$n$.  Therefore, it suffices to show
  that
  $$
  \min\{a(\ell)\:0\leq\ell\leq n/2\}
  $$
  is achieved either at~$\ell=0$ or at~$\ell=\lfloor n/2\rfloor$.  In particular,
  if we show that~$a(\ell)$ is unimodal, we are done.  Let
  \begin{equation}
    \label{eq:b(k)_def}
    b(\ell)={a(\ell+1)\over a(\ell)}
    =2^{4(2\ell+1+2\{n/2\})/n}{\lfloor n/2\rfloor-\ell\over\lceil n/2\rceil+\ell+1} 
  \end{equation}
  for all~$0\leq\ell\leq n/2-1$.  Observe that, for all large enough~$n$, we
  have 
  \begin{equation}
    \label{eq:b(0)}
    b(0)=2^{4/n}{\lfloor n/2\rfloor\over\lceil n/2\rceil+1}>1
  \end{equation}
  and
  \begin{equation}
    \label{eq:b(large_k)}
    b(\lfloor n/2\rfloor-1)
    ={1\over n}2^{4(1-1/n)}<1.
  \end{equation}
  We now show that~$b(\ell)$ is itself unimodal.  Let
  \begin{multline}
    \label{eq:c(k)_def}
    c(\ell)={b(\ell+1)\over b(\ell)}
    =2^{8/n}
    \(\lfloor n/2\rfloor-\ell-1\over\lfloor n/2\rfloor-\ell\)
    \(\lceil n/2\rceil+\ell+1\over\lceil n/2\rceil+\ell+2\)\\
    =2^{8/n}\(1-{n+1\over\(\lfloor n/2\rfloor-\ell\)\(\lceil n/2\rceil+\ell+2\)}\)
  \end{multline}
  for all~$0\leq\ell\leq n/2-2$.  Note that~$c(0)>1$ for sufficiently
  large~$n$ and~$c(\ell)$ is decreasing.  Therefore, $b(\ell)$~is unimodal,
  `starts' with~$b(0)>1$, and `ends' with~$b(\lfloor n/2\rfloor-1)<1$.
  Therefore we conclude that~$a(\ell)$ is indeed unimodal, as required.
\end{proof}

In Section~\ref{sec:cN_of_random}, we shall need results similar to
Fact~\ref{fact:large_dev} for the tail of~$\Bi(n,p)$ for arbitrary~$0<p<1$.
We shall use the following estimates
(see~\cite[Theorem~2.1]{janson00:_random_graph}).

\begin{fact}
  \label{fact:Chernoff}
  Let~$X$ have binomial distribution~$\Bi(n,p)$ and set~$\lambda=\EE(X)=pn$.
  Then, for any~$t\geq0$, we have
  \begin{equation}
    \label{eq:Chernoff1}
    \PP\big(X\geq\EE(X)+t\big)\leq\exp\(-{t^2\over2(\lambda+t/3)}\)
  \end{equation}
  and
  \begin{equation}
    \label{eq:Chernoff2}
    \PP\big(X\leq\EE(X)-t\big)\leq\exp\(-{t^2\over2\lambda}\).
  \end{equation}
\end{fact}

%
%  Old Fact 10 
%
% Adding a little remark to the proof of Fact~\ref{fact:1/2BinU}(\textit{i}), we
% may prove the following lower bound for the binomial distribution.  (Recall
% that we write~$\{x\}$ for the fractional part of~$x$.)

% \begin{fact}
%   \label{fact:1/2BinUlwbd}
%   Let~$n$ and~$k$ be non-negative integers with
%   \begin{equation}
%     \label{eq:k_n_condition}
%     |k|<\llfloor n\over 2\rrfloor-{n\over(\log n)^2},
%   \end{equation}
%   and
% %  \begin{enumerate}
% %  \item[(\textit{i})]
%     put~$\alpha=(k-\{n/2\})/n$.  Then
%     \begin{multline}
%       \label{eq:single_binU_for_lwbd}
%       \PP\(S(n,1/2)=\llfloor n\over2\rrfloor+k\)
%       ={1\over2^n}{n\choose\lfloor n/2\rfloor+k}\\
%       \geq2^{-4\alpha^2n}\sqrt{2\over\pi n(1-4\alpha^2)}\(1+O\((\log n)^2\over
%       n^{1/3}\)\).  
%     \end{multline}
% %     Therefore, 
% %     \begin{equation}
% %       \label{eq:single_binU2}
% %       \qquad
% %       \PP\(S(n,1/2)=\llfloor n\over2\rrfloor+k\)
% %       \leq{4\over5\sqrt n}e^{-2k^2/n}
% %       <{1\over\sqrt n}e^{-2k^2/n}
% %     \end{equation}
% %     for all large enough~$n$.
% %  \item[(\textit{ii})]We have
% %\ykcomm{Perhaps state this with $1+o(1)$?  That
% %is, with coefficient $\sim(1/2k)\sqrt{n/2\pi}$?  Check later.}
% %     \begin{multline}
% %       \label{eq:tails1U}
% %       \PP\(S(n,1/2)\geq\llfloor n\over2\rrfloor+k\)
% %       ={1\over2^n}\sum_{j\geq k}{n\choose\lfloor n/2\rfloor+j}\\
% %       \leq\({3\over4}\sqrt{2\over\pi}+o(1)\){\sqrt n\over k}e^{-2k^2/n}.
% %     \end{multline}
% %     Moreover, both~$\PP(S(n,1/2)\geq n/2+k)$ and~$\PP(S(n,1/2)\leq n/2-k)$ are
% %     bounded by the probability in~\eqref{eq:tails1U}, and hence
% %     \begin{equation}
% %       \label{eq:tails1Ub}
% %       \PP\(\left|S(n,1/2)-{n\over2}\right|\geq k\)
% %       \leq\({3\over2}\sqrt{2\over\pi}+o(1)\){\sqrt n\over k}e^{-2k^2/n}.
% %     \end{equation}
% %   \end{enumerate}
% \end{fact}
% \begin{proof}
%   Recall that~\eqref{eq:k_n_condition} or, equivalently,
%   \eqref{eq:not_so_large_k} and~\eqref{eq:not_so_small_k}, together
%   with~\eqref{eq:Stirling} give that
%   \begin{equation}
%     \label{eq:binom_main_expression_for_lwbd}
%     {1\over2^n}{n\choose\lfloor n/2\rfloor+k}
%     =\(1+O\((\log n)^2\over n\)\)
%     {e^{-nf(\alpha)}\over\sqrt{2\pi n(1/4-\alpha^2)}},
%   \end{equation}
% %   \begin{multline}
% %     \label{eq:binom_main_expression}
% %     {1\over2^n}{n\choose\lfloor n/2\rfloor+k}
% %     =\(1+O\((\log n)^2\over n\)\)
% %     {e^{-nf(n)}\over\sqrt{2\pi n(1/4-\alpha^2)}}\\
% %     \leq\(1+O\((\log n)^2\over n\)\)\sqrt{2\over\pi n}e^{-nf(n)},
% %   \end{multline}
%   where
%   \begin{equation}
%     \label{eq:f(alpha)_def2}
%     f(\alpha)=\({1\over2}+\alpha\)\log\({1\over2}+\alpha\)
%     +\({1\over2}-\alpha\)\log\({1\over2}-\alpha\)+\log2.
%   \end{equation}
%   Therefore, to prove~\eqref{eq:single_binU}, it suffices to check that
%   \begin{equation}
%     \label{eq:f_upbd}
%     f(\alpha)\leq g(\alpha)
%   \end{equation}
%   for all~$|\alpha|<1/2$, where~$g(\alpha)=(4\log 2)\alpha^2$.
%   Let~$h(\alpha)=g(\alpha)-f(\alpha)$, and observe that~$h(0)=h(1/2)=0$.
%   Moreover, $h(\alpha)$ is concave in the interval~$(0,1/2)$
%   (see~\eqref{eq:f(alpha)2deriv}), and hence~\eqref{eq:f_upbd} follows, and
%   our proof is complete.
% \end{proof}

\subsection{The well-distribution measure~$W$}
\label{sec:W_of_random}
Our aim in this section is to prove Theorem~\ref{thm:order_of_W}.
Let~$E_N=(e_1,\dots,e_N)\in\{-1,1\}^N$ be drawn uniformly at random; we wish
to estimate
\begin{equation}
  \label{eq:W_def_recall}
  W(E_N)=\max_{a,b,M}\sum_{1\leq j\leq M}e_{a+jb},
\end{equation}
where the maximum is taken over all integers~$a$, $b$, and~$M$ with~$1\leq
a+b<a+bM\leq N$.

We start with the lower bound in~\eqref{eq:order_of_W}.  Observe that
Fact~\ref{fact:1/2Bin} tells us that, for any fixed~$C>0$, we have
\begin{equation}
  \label{eq:best_possible_W}
  \lim_{N\to\infty}\PP\(\bigg|\sum_{1\leq j\leq N}e_j\bigg|\geq C\sqrt N\) 
  =2\sqrt{2\over\pi}\int_{C/2}^\infty e^{-2x^2}\rmd x>0.
\end{equation}
The lower bound for~$W(E_N)$ for a typical~$E_N$ follows
from~\eqref{eq:best_possible_W} and the fact 
%\begin{equation}
%  \label{eq:lwbd_W}
%  \lim_{n\to\infty}\PP\(\bigg|\sum_{1\leq j\leq N}e_j\bigg|\geq\delta\sqrt n\) 
%  =2\sqrt{2\over\pi}\int_{\delta/2}^\infty e^{-2x^2}\rmd x
%\end{equation}
that
$$
2\sqrt{2\over\pi}\int_{C/2}^\infty e^{-2x^2}\rmd x\to1
$$
as~$C\to0$.  Indeed, the facts above show that, for any~$\epsilon>0$, there
is~$\delta>0$ so that the lower bound in~\eqref{eq:order_of_W} holds with
probability at least~$1-\epsilon$.  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\leq
a+b<a+2b<\dots<a+Tb\leq K$, where~$-b+1\leq a\leq0$ and~$T$ is the largest
integer satisfying~$a+Tb\leq K$, will be called \textit{complete arithmetic
  progressions in~$[1,K]\cap\ZZ$}.  Our first auxiliary lemma gives an
estimate, as a function of~$K$, for the maximal value of the `discrepancy'
\begin{equation}
  \label{eq:complete_APs}
  S_{a,b}^{(K)}=\bigg|\sum_{1\leq a+jb\leq K}e_{a+jb}\bigg| 
\end{equation}
over complete arithmetic progressions in~$[1,K]$, for typical
sequences
$$
(e_1,\dots,e_K)\in\{-1,1\}^K.
$$

\begin{lemma}
  \label{lem:W_lemma1}
  Let~$K$ be a positive integer and~$C$ a positive real number.  Let
  $(e_1,\dots,e_K)$ be drawn uniformly at random from~$\{-1,1\}^K$.  The
  probability that there are integers~$a$ and~$b$ with~$-b+1\leq a\leq0$ such
  that
  \begin{equation}
    \label{eq:W_lemma1}
    S_{a,b}^{(K)}=\bigg|\sum_{1\leq a+jb\leq K}e_{a+jb}\bigg|
    >C\sqrt K
%    >{C{\sqrt b}\over2}\sqrt{\llceil K\over b\rrceil}
  \end{equation}
  is~$O\big(e^{-C^2/4}\big)$, as long as, say, $C\geq2$.
\end{lemma}
\begin{proof}
  For any given integers~$a$ and~$b$ with~$-b+1\leq a\leq0$, the complete
  arithmetic progression~$1\leq a+b<a+2b<\dots\leq K$ in~$[1,K]$ has
  either~$\lfloor K/b\rfloor$ or~$\lceil K/b\rceil$ terms.  Fix a large
  constant~$C$, and observe that~\eqref{eq:large_dev} in
  Fact~\ref{fact:large_dev} tells us that, if~$b\leq K$, then the probability
  that we have
  $$
  S_{a,b}^{(K)}=\bigg|\sum_{1\leq a+jb\leq K}e_{a+jb}\bigg|
  >C\sqrt K
%  >{C{\sqrt b}\over2}\sqrt{\llceil K\over b\rrceil}
  $$
  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,\dots, K-1$.  Therefore, the probability that
  there are~$a$ and~$b$ for which~$S_{a,b}^{(K)}$ is larger than~$C\sqrt K$ is
  \begin{equation}
    \label{eq:aux_ineq}
    O\bigg(\sum_{1\leq b<K}be^{-bC^2/4}\bigg)=O\big(e^{-C^2/4}\big),
  \end{equation}
  where we used that~$C\geq2$ and hence the terms in the sum
  in~\eqref{eq:aux_ineq} drop geometrically.
\end{proof}

Let us now consider intervals of integers of the form
\begin{equation}
  \label{eq:B_mr_def}
  B_{m,r}=(m2^r,(m+1)2^r]\cap\ZZ, 
\end{equation}
where~$m$ and~$r$ are non-negative integers.  Clearly, $|B_{m,r}|=2^r$.  We
refer to the~$B_{m,r}$ as \textit{blocks}.  Put
\begin{equation}
  \label{eq:k_def}
  k=1+\lfloor\log_2N\rfloor,
\end{equation}
and observe that all blocks~$B_{m,r}$ contained in~$[1,N]$ have~$r<k$.

Lemma~\ref{lem:W_lemma1} 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
\begin{equation}
  \label{eq:S_ab_large}
  \max_{a,b}\left|\sum\{e_{a+jb}\:a+jb\in B_{m,r}\}\right|
  >C(k-r)\sqrt{2^r}
\end{equation}
is~$O(e^{-C^2(k-r)^2/4})$.  On the other hand, for any~$r$, we have at
most~$N/2^r\leq2^{k-r}$ blocks~$B_{m,r}$ contained in~$[1,N]$.  Therefore,
if~$C$ is large enough, the probability that~\eqref{eq:S_ab_large} holds for
\textit{some} block~$B_{m,r}\subset[1,N]$ is
\begin{equation}
  \label{eq:preceding_(*)}
  O\bigg(\sum_{0\leq r<k}2^{k-r}e^{-C^2(k-r)^2/4}\bigg)
  =O\big(e^{-C^2/4}\big),
\end{equation}
which tends to~$0$ as~$C\to\infty$.  Therefore, to complete our proof, we
may suppose that~\eqref{eq:S_ab_large} does not hold for any~$B_{m,r}$, that
is, we may suppose that
\begin{itemize}
\item[(*)]\sl for all~$m$ and~$r$ with~$B_{m,r}\subset[1,N]$, we have
  $$
  \max_{a,b}\left|\sum\{e_{a+jb}\:a+jb\in B_{m,r}\}\right| \leq
  C(k-r)\sqrt{2^r}.
  $$
\end{itemize}
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.

\begin{fact}
  \label{fact:W_fact}
  Given any integers~$1\leq p<q\leq N$, it is possible to write the integer
  interval~$I_{p,q}=[p,q]\cap\ZZ$ 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}$.
\end{fact}
\begin{proof}
  To see this, first consider the smallest~$f$ for which~$[p,q]\subset[1,2^f)$
  (that is, $f=\lceil\log_2(q+1)\rceil$), and then consider the `dyadic' ruler
  in the interval~$[1,2^f)$: \ykcomm{I hope this argument is understandable.}
  the level~$0$ mark in our ruler is~$1$; the \textit{level~$1$ mark}
  is~$2^{f-1}$; the set of \textit{level~$2$ marks}
  is~$\{2^{f-2},2^{f-1}+2^{f-2}\}$; the set of \textit{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]\cap\ZZ$ 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]\cap\ZZ$.
\end{proof}

We now use~(*) and Fact~\ref{fact:W_fact} above to prove that~$W(E_N)=O(\sqrt
N)$.  Given~$a$, $b$, and~$M$ with~$1\leq a+b<a+Mb\leq N$, we
write~$[a+b,a+Mb]\cap\ZZ$ 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~$\cB$
be the collection of blocks~$B_{m,r}$ that we have used in our partition
of~$[a+b,a+Mb]\cap\ZZ$.  We have
\begin{multline*}
\bigg|\sum_{1\leq j\leq M}e_{a+jb}\bigg|
\leq\sum_{B_{m,r}\in\cB}
\left|\sum\left\{
    e_{a+jb}\:a+jb\in B_{m,r}
  \right\}
\right|\\
\leq\sum_{0\leq r<k}2\times C(k-r)\sqrt{2^r}\\
=2C2^{k/2}\sum_{1\leq\ell\leq k}\ell2^{-\ell/2}
=O(2^{k/2})=O(\sqrt N).
\end{multline*}
This completes the proof of Theorem~\ref{thm:order_of_W}.

\subsection{The correlation measure~$C_k$}
\label{sec:C_k_of_random}
In this section we prove Theorems~\ref{thm:order_of_C_k}
and~\ref{thm:C_k_concentrated}.  

\subsubsection{Proof of Theorem~\ref{thm:order_of_C_k}}
\label{sec:pfofthm:order_of_C_k}
We shall first prove the upper estimate for~$C_k(E_N)$ for typical
sequences~$E_N$.  Indeed, we prove the following lemma.

\begin{lemma}
  \label{lem:order_of_C_k_upbd}
  Let~$\epsilon=\epsilon(N)=(\log\log N)/\log N$.  With probability tending
  to~$1$ as~$N\to\infty$, we have
  \begin{equation}
    \label{eq:order_of_C_k_upbd}
    C_k(E_N)
    <\sqrt{(2+\epsilon)N\log\(N{N\choose k}\)}
  \end{equation}
  for every integer~$k$ with~$2\leq k\leq N/4$.
\end{lemma}
\begin{proof}
  We first consider a fixed integer~$k$ with~$2\leq k\leq N/4$.  Fix a
  sequence~$D=(d_1,\dots,d_k)$ with~$0\leq d_1<\dots<d_k<N$.
  Since~$E_N=(e_i)_{1\leq i\leq N}$ is drawn uniformly at random
  from~$\{-1,1\}^N$, the sequence
  $$
  (e_{1+d_1}e_{1+d_2}\dots e_{1+d_k},e_{2+d_1}e_{2+d_2}\dots e_{2+d_k},
  \dots,
  e_{N-d_k+d_1}e_{N-d_k+d_2}\dots e_N)
  $$
  is a random element of the uniform space~$\{-1,1\}^{N-d_k}$.
  Recall~\eqref{eq:C_k_def}, and let an integer~$M$ with~$M+d_k\leq N$ be
  fixed.  Clearly, $V(E_N,M,D)$~has the same distribution as~$S^{\pm}(M)$.
  We now use~\eqref{eq:large_dev} with
  $$
  a=\sqrt{(2+\epsilon)N\log\(N{N\choose k}\)},
  $$
  where~$\epsilon=(\log\log N)/\log N$ is as in the statement of our lemma,
  to deduce that
  \begin{equation}
    \label{eq:large_V}
    |V(E_N,M,D)|>\sqrt{(2+\epsilon)N\log\(N{N\choose k}\)}
  \end{equation}
  holds with probability less than
  \begin{equation}
    \label{eq:tail_for_C_k_upbd}
    \exp\left\{
      -{1\over2M}(2+\epsilon)N\log\(N{N\choose k}\)
      \right\}
    \leq\left\{N{N\choose k}\right\}^{-(1+\epsilon/2)}.
  \end{equation}
  Summing over all possible choices of~$M$ and~$D$, we get an extra factor
  of~$N{N\choose k}$, which gives an upper bound of~$\left\{N{N\choose
      k}\right\}^{-\epsilon/2}$ for the probability of the event
  that~\eqref{eq:large_V} should hold for \textit{some}~$M$ and~$D$.  We shall
  now sum these bounds over~$2\leq k\leq N/4$.  For estimating this sum, we
  observe that
  \begin{equation}
    \label{eq:final_prob_upbd.aux1}
    {1\over1-1/3^\delta}\leq{1\over\delta}
  \end{equation}
  for all~$0<\delta\leq\delta_0$, where~$\delta_0>0$ is some suitably small
  absolute constant, and
  \begin{equation}
    \label{eq:final_prob_upbd.aux2}
    {N\choose k-1}\left/{N\choose k}\right.\leq{1\over3}
  \end{equation}
  for~$2<k\leq N/4$.  Using~\eqref{eq:final_prob_upbd.aux1}
  and~\eqref{eq:final_prob_upbd.aux2}, we see that the probability
  that~\eqref{eq:large_V} holds for some~$M$, $D$, and~$k$ with~$k$ in the
  range~$2\leq k\leq N/4$ is at most
  \begin{multline}
    \label{eq:final_prob_upbd}
    \sum_{2\leq k\leq N/4}\left\{N{N\choose k}\right\}^{-\epsilon/2}
    \leq\left\{N{N\choose2}\right\}^{-\epsilon/2}
    \sum_{\ell\geq0}\(1\over3\)^{\ell\epsilon/2}\\
    \leq{2\over\epsilon}\left\{N{N\choose2}\right\}^{-\epsilon/2}
    =O\(1\over(\log\log N)\sqrt{\log N}\)=o(1),
  \end{multline}
  and our result follows.
\end{proof}

The proof of Theorem~\ref{thm:order_of_C_k} will be complete if we prove the
following result.

\begin{lemma}
  \label{lem:order_of_C_k_lwbd}
  With probability tending to~$1$ as~$N\to\infty$, we have
  \begin{equation}
    \label{eq:order_of_C_k_lwbd}
    C_k(E_N)
    >{2\over5}\sqrt{N\log{N\choose k}}
  \end{equation}
  for every integer~$k$ with~$2\leq k\leq N/4$. 
\end{lemma}

We start with an auxiliary result.

\begin{fact}
  \label{fact:boring_ineq}
  Let~$m=\lfloor N/3\rfloor$.  For every sufficiently large~$N$, the following
  hold. 
  \begin{itemize}
  \item[(\textit{i})]If~$2\leq k\leq\log m$, then 
    \begin{equation}
      \label{eq:boring_ineq.i}
      \sqrt{N\log{N/3\choose k}}\geq0.99\sqrt{N\log{N\choose k}}.
    \end{equation}
  \item[(\textit{ii})]If~$\log m<k\leq N/4$, then 
    \begin{equation}
      \label{eq:boring_ineq.ii}
      \sqrt{N\log{N/3\choose k}}\geq\sqrt{{1-10^{-10}\over3}N\log{N\choose
      k}}. 
    \end{equation}
  \end{itemize}
\end{fact}

We include the proof of Fact~\ref{fact:boring_ineq} for completeness.  The
reader may prefer to go directly to the proof of
Lemma~\ref{lem:order_of_C_k_lwbd}, given below.

\begin{proof}[Proof of Fact~\ref{fact:boring_ineq}]
  Throughout this proof, we suppose that~$N$ is larger than a suitably large
  absolute constant.
  
  Let us start with the proof of~(\textit{i}).  Suppose~$2\leq k\leq\log m$.
  Using that~$(a/b)^b\leq{a\choose b}\leq(ea/b)^b$, we have
  \begin{equation}
    \label{eq:boring_ineq.i.pf}
    {N/3\choose k}\geq\(N\over3k\)^k\geq\(1\over3e\)^k\(eN\over k\)^k
    \geq\(1\over3e\)^k{N\choose k}.
  \end{equation}
  Therefore, 
  \begin{align}
    &\log{N/3\choose k}
    \geq\(1-{k\log(3e)\over\log{N\choose k}}\)\log{N\choose k}\nonumber\\
    &\qquad\qquad\geq\(1-{1+\log3\over\log(N/k)}\)\log{N\choose k}
    \geq\(1-{3\over\log N}\)\log{N\choose k}. \label{eq:boring_ineq.i.pf2}
  \end{align}
  Inequality~\eqref{eq:boring_ineq.i} follows
  from~\eqref{eq:boring_ineq.i.pf2}, and~(\textit{i}) is proved.
  
  Let us now turn to~(\textit{ii}).  Suppose~$\log m< k\leq N/4$.
  Since~${N/3\choose k}\geq{\lfloor N/3\rfloor\choose k}={m\choose k}$, it
  clearly suffices to prove that
  \begin{equation}
    \label{eq:binom_ineq_final}
    {m\choose k}\geq{N\choose k}^{(1-10^{-10})/3}
  \end{equation}
  for all large enough~$N$.  If~$k<m/2$, then~$m-k>m/2>k$.  Moreover,
  \begin{equation}
    \label{eq:binom_symmetry}
    {m\choose k}={m\choose m-k}
  \end{equation}
  and
  \begin{equation}
    \label{eq:binom_increasing}
    {N\choose m-k}^{(1-10^{-10})/3}\geq{N\choose k}^{(1-10^{-10})/3}.
  \end{equation}
  Therefore, it suffices to consider~$k$ with
  \begin{equation}
    \label{eq:smaller_k_range}
    {1\over2}\llfloor N\over3\rrfloor={1\over2}m\leq k\leq{N\over4}. 
  \end{equation}
  Now, the left-hand side of~\eqref{eq:binom_ineq_final} is decreasing in the
  range~\eqref{eq:smaller_k_range}, while the right-hand side is increasing in
  that range.  Therefore, it suffices to verify~\eqref{eq:binom_ineq_final}
  at~$k=\lfloor N/4\rfloor$.  
  
  To check~\eqref{eq:binom_ineq_final} for~$k=\lfloor N/4\rfloor$, we may use
  the fact that if~$r=r(n)$ is an integer function of~$n$
  with~$\lim_{n\to\infty}r(n)/n=x$, then
  \begin{equation}
    \label{eq:entropy}
    {n\choose r}=2^{(H(x)+o(1))n},
  \end{equation}
  where~$o(1)\to0$ as~$n\to\infty$, and
  \begin{equation}
    \label{eq:entropy_def}
    H(x)=-x\log_2x-(1-x)\log_2(1-x)
  \end{equation}
  for all~$0\leq x\leq 1$ ($H(0)=H(1)=0$).  Of course, this is an immediate
  consequence of Stirling's formula
  \begin{equation}
    \label{eq:Stirling}
    n!=\sqrt{2\pi n}\(n\over e\)^n\(1+O\(1\over n\)\).
  \end{equation}
  We now note that
  \begin{equation}
    \label{eq:H_ineq}
    {1\over3}H\(3\over4\)={1\over3}H\(1\over4\)
    >{1-10^{-10}\over3}H\(1\over4\), 
  \end{equation}
  and hence~\eqref{eq:binom_ineq_final} does indeed follow for~$k=\lfloor
  N/4\rfloor$ as long as~$N$ is large enough.  This completes the proof of
  Fact~\ref{fact:boring_ineq}.
\end{proof}

We now give the proof of the main result in this section.
%Section~\ref{sec:C_k_of_random}. 

\begin{proof}[Proof of Lemma~\ref{lem:order_of_C_k_lwbd}]
  Set~$m=\lfloor N/3\rfloor$, and recall that we write~$S(m,1/2)$ for
  a random variable with binomial distribution~$\Bi(m,1/2)$.
  Fix~$2\leq k\leq N/4$.  We are interested in the largest integer~$r$ for
  which 
  \begin{equation}
    \label{eq:r(m)_def.aux}
    \PP\(S(m,1/2)\geq{1\over2}(m+r)\)
    \geq k^2(\log N){m+1\choose k-1}^{-1}
  \end{equation}
  holds.  Indeed, we let
  \begin{equation}
    \label{eq:r(m)_def}
    r(m)=r_k(m)=\max\left\{r\in\NN
      \:\text{inequality~\eqref{eq:r(m)_def.aux} holds}\right\}. 
  \end{equation}
  We need the following lower bounds for~$r(m)$.

  \begin{fact}
    \label{fact:r(m)_lwbd}
    For every sufficiently large~$N$, the following hold.
    \begin{itemize}
    \item[(\textit{i})]If~$2\leq k\leq\log m$, then
      \begin{equation}
        \label{eq:r(m)_lwbd.i}
        r(m)\geq0.99\sqrt{2m\log{m+1\choose k-1}}.
      \end{equation}
    \item[(\textit{ii})]If~$\log m<k\leq N/4$, then
      \begin{equation}
        \label{eq:r(m)_lwbd.ii}
        r(m)\geq(1-10^{-10})\sqrt{{m\over\log2}\log{m+1\choose k-1}}. 
      \end{equation}
    \item[(\textit{iii})]If~$2\leq k\leq N/4$, then
      \begin{equation}
        \label{eq:r(m)_lwbd.iii}
        r(m)\geq{2\over5}\sqrt{N\log{N\choose k}}.
      \end{equation}
    \end{itemize}
  \end{fact}
  \begin{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
    \begin{equation}
      \label{eq:o(1)_diff_only}
      k^2(\log N){m+1\choose k-1}^{-1}={m+1\choose k-1}^{-1+o(1)}
    \end{equation}
    uniformly in~$k$ in the range~$2\leq k\leq N/4$; that is, for all~$\eta>0$
    there is~$N_0$ such that if~$N\geq N_0$, then, for all~$2\leq k\leq N/4$,
    we have
    \begin{equation}
      \label{eq:o(1)_diff_only2}
      k^2\log N\leq{m+1\choose k-1}^\eta.
    \end{equation}
    To check this assertion, note that if~$2\leq k\leq(\log N)^2$, then the
    left-hand side of~\eqref{eq:o(1)_diff_only2} is polylogarithmic in~$N$,
    whereas~${m+1\choose k-1}\geq N/3$.  On the other hand, if~$(\log
    N)^2<k\leq N/4$, then the left-hand side of~\eqref{eq:o(1)_diff_only2}
    is~$O(N^2\log N)$, whereas~${m+1\choose
      k-1}\geq\big((m+1)/(k-1)\big)^{k-1}\geq(4/3+o(1))^{k-1}\geq(5/4)^{(\log
      N)^2-1}$, which is superpolynomial in~$N$.  Therefore,
    \eqref{eq:o(1)_diff_only}~does hold.  
    
    We now turn to the proof of~(\textit{i}).  Suppose~$2\leq k\leq\log m$.
    Set
    \begin{equation}
      \label{eq:r_def.1}
      r=\llceil0.99\sqrt{2m\log{m+1\choose k-1}}\rrceil.
    \end{equation}
    We shall show that~\eqref{eq:r(m)_def.aux} holds for the value of~$r$
    given in~\eqref{eq:r_def.1}.  Let
    \begin{equation}
      \label{eq:c_def}
      c={r+1\over2\sqrt m}=
      (1+o(1))0.99\sqrt{{1\over2}\log{m+1\choose k-1}}.
    \end{equation}
    We now use~\eqref{eq:tails2} in Fact~\ref{fact:1/2Bin}(\textit{ii}) to
    deduce that
    \begin{multline}
      \label{eq:large_P_i}
      \PP\(S(m,1/2)\geq{1\over2}(m+r)\)
      \geq\PP\(S(m,1/2)\geq\llfloor m\over2\rrfloor+c\sqrt m\)\\
%      =\PP\(S(m,1/2)\geq{m\over2}+c\sqrt m\)\\
      ={e^{-2c^2}\over2c\sqrt{2\pi}}(1+o(1))
      \geq{1\over100}{m+1\choose k-1}^{-0.99}\(\log{m+1\choose
      k-1}\)^{-1/2},
    \end{multline}
    which is clearly larger than
    \begin{equation}
      \label{eq:fin_bd}
      k^2(\log N){m+1\choose k-1}^{-1}
    \end{equation}
    for large enough~$N$ (see~\eqref{eq:o(1)_diff_only}).  This completes the
    proof of~\eqref{eq:r(m)_def.aux}, and hence~(\textit{i}) follows.  We now
    turn to~(\textit{ii}).  Suppose~$\log m<k\leq N/4$.  Set
    \begin{equation}
      \label{eq:r_def.2}
      r=\llceil(1-10^{-10})\sqrt{{m\over\log2}\log{m+1\choose k-1}}\rrceil. 
    \end{equation}
    We shall show that~\eqref{eq:r(m)_def.aux} holds for the value of~$r$
    given in~\eqref{eq:r_def.2}.  Let
    \begin{equation}
      \label{eq:ell_def}
      \ell=\llceil r+1\over2\rrceil
      =(1+o(1)){1-10^{-10}\over2\sqrt{\log2}}\sqrt{m\log{m+1\choose k-1}}. 
    \end{equation}
    We now use~\eqref{eq:single_binU_for_lwbd} in Fact~\ref{fact:1/2BinUlwbd}
    to deduce that
    \begin{align*}
      &\PP\Big(S(m,1/2)\geq{1\over2}(m+r)\Big)
      \geq\PP\Big(S(m,1/2)\geq\llfloor m\over2\rrfloor+\ell\Big)\\
      &\qquad\qquad
      \geq(1+o(1))2^{-4(\lceil(r+1)/2\rceil+1/2)^2/m}\sqrt{2\over\pi m}\\
      &\qquad\qquad
      \geq(1+o(1))2^{-r^2/m}2^{-(6r+9)/m}\sqrt{2\over\pi m}\\
      &\qquad\qquad\qquad\qquad\geq(1+o(1)){m+1\choose k-1}^{-1+10^{-10}}
      \geq k^2(\log N){m+1\choose k-1}^{-1}
    \end{align*}
    for all large enough~$N$, where, again, we
    used~\eqref{eq:o(1)_diff_only} for the last inequality.  This
    completes the proof of~\eqref{eq:r(m)_def.aux}, and~(\textit{ii})
    follows.
    
    We now turn to~(\textit{iii}).  Suppose first that~$2\leq k\leq\log m$, so
    that~\eqref{eq:r(m)_lwbd.i} holds.  Using that~${m+1\choose
      k-1}\geq{N/3\choose k-1}\geq{N/3\choose k}^{1/2}$ in this range of~$k$
    and Fact~\ref{fact:boring_ineq}(\textit{i}), we deduce that
    \begin{multline}
      \label{eq:r(m)_lwbd.iii.1}
      r(m)\geq0.99\sqrt{2\llfloor N\over3\rrfloor\log{m+1\choose k-1}}\\
      \geq(1+o(1)){0.99\over\sqrt3}\sqrt{N\log{N/3\choose k}}
      \geq{2\over5}\sqrt{N\log{N\choose k}}.
    \end{multline}
    Suppose now that~$\log m<k\leq N/4$, so that~\eqref{eq:r(m)_lwbd.ii}
    holds.  Using that~${m+1\choose k-1}\geq{N/3\choose k}^{1-o(1)}$ in this
    range of~$k$ and Fact~\ref{fact:boring_ineq}(\textit{ii}), we deduce that 
    \begin{multline}
      \label{eq:r(m)_lwbd.iii.2}
      r(m)\geq{1-10^{-10}\over\sqrt{\log2}}
      \sqrt{\llfloor N\over3\rrfloor\log{m+1\choose k-1}}\\
      \geq(1+o(1)){1-10^{-10}\over\sqrt{3\log2}}\sqrt{N\log{N/3\choose k}}
      \geq{2\over5}\sqrt{N\log{N\choose k}}.
    \end{multline}
    Inequality~\eqref{eq:r(m)_lwbd.iii} follows from~\eqref{eq:r(m)_lwbd.iii.1}
    and~\eqref{eq:r(m)_lwbd.iii.2}, and~(\textit{iii}) is proved.
  \end{proof}
  
  To prove Lemma~\ref{lem:order_of_C_k_lwbd}, we shall show that, with
  probability~$\leq2/k^2\log N$, we have
  \begin{equation}
    \label{eq:C_k_large}
    C_k(E_N)\leq r_k(m),
  \end{equation}
  and then we shall sum over all~$2\leq k\leq N/4$.  This gives
  that~\eqref{eq:C_k_large} holds for \textit{some}~$k$ with~$2\leq k\leq N/4$
  with probability~$O(1/\log N)=o(1)$.  Therefore,
  \eqref{eq:C_k_large}~\textit{fails} for \textit{all}~$2\leq k\leq N/4$ with
  probability~$1-o(1)$, and Lemma~\ref{lem:order_of_C_k_lwbd} will be proved.
  
  Let~$2\leq k\leq N/4$ be fixed.  Our strategy to estimate the
  probability that~\eqref{eq:C_k_large} should hold will be as
  follows.  Recall $E_N=(e_1,\dots,e_N)$ and let~$u=(e_1,\dots,e_m)$.
  Let~$\cD_k$ be the set of $(k-1)$-tuples~$D=(d_1,\dots,d_{k-1})$
  with~$m\leq d_1<\dots<d_{k-1}\leq2m$.  For each~$D\in\cD_k$, let
  \begin{equation}
    \label{eq:v_D_def}
    v_D=(e_{1+d_1}e_{1+d_2}\dots e_{1+d_{k-1}},
    \dots,e_{m+d_1}e_{m+d_2}\dots e_{m+d_{k-1}}),
  \end{equation}
  and let~$A(D)$ be the event that
  \begin{equation}
    \label{eq:A(D)_def}
    |\<u,v_D\>|>r(m)=r_k(m)
  \end{equation}
  holds.  It suffices to show that some~$A(D)$ ($D\in\cD_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\in\cD_k$) that
  hold for~$E_N$.  Let
  \begin{equation}
    \label{eq:p_def}
    p=p(m)=\PP\(S(m,1/2)\geq{1\over2}(m+r(m))\).
%    ={1\over2^m}\sum_{j\geq(m+r(m))/2}{m\choose j}.
  \end{equation}
  Because of~\eqref{eq:r(m)_def}, we have
  \begin{equation}
    \label{eq:X_expectation}
    \EE(X)=p|\cD_k|=p{m+1\choose k-1}\geq k^2\log N.
  \end{equation}
  We have now arrived at the key claim: the events~$A(D)$ ($D\in\cD_k$) are
  pairwise independent.  

  \begin{claim}
    \label{claim:pairwise_inter}
    For all distinct~$D$ and~$D'\in\cD_k$, we have
    \begin{equation}
      \label{eq:pairwise_inter}
      \PP(A(D)\cap A(D'))=p^2.
    \end{equation}
  \end{claim}
  
  We postpone the proof of Claim~\ref{claim:pairwise_inter}.  To complete the
  proof of Lemma~\ref{lem:order_of_C_k_lwbd}, 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~\cite{chung52:_borel_cantel}
  and~\cite{erdos59}.  More recently, Petrov used this result to generalize
  the Borel--Cantelli
  lemma~\cite{petrov02:_borel_cantel,petrov04:_borel_cantel}

  \begin{lemma}
    \label{lem:neg_correlated}
    Let~$A_1,\dots,A_M$ be events in a probability space, each with
    probability at least~$p$.  Let~$\epsilon\geq0$ be given, and suppose that
    \begin{equation}
      \label{eq:neg_corr}
      \PP(A_i\cap A_j)\leq p^2(1+\epsilon)
    \end{equation}
    for all~$i\neq j$. Then
    \begin{multline}
      \label{eq:neg_correlated}
      \PP\Big(\bigcup\nolimits_{1\leq j\leq M}A_j\Big)
      \geq{Mp\over1+(M-1)p(1+\epsilon)}\\
      =1-{1-p+(M-1)p\epsilon\over1+(M-1)p(1+\epsilon)}
      >1-\epsilon-{2\over Mp}.
    \end{multline}
  \end{lemma}
  
  The proof of Lemma~\ref{lem:neg_correlated} is given below.  We conclude the
  proof of Lemma~\ref{lem:order_of_C_k_lwbd} combining
  Claim~\ref{claim:pairwise_inter} and Lemma~\ref{lem:neg_correlated}.  It
  suffices to notice that we have~$M={m+1\choose k-1}$ pairwise independent
  events~$A(D)$ (that is, $\epsilon=0$), and~$pM\geq k^2\log N$
  (see~\eqref{eq:X_expectation}).  Inequality~\eqref{eq:neg_correlated} then
  tells us that, with probability greater than~$1-2/k^2\log N$, the
  event~$A(D)$ happens for some~$D\in\cD_k$.  We conclude
  that~\eqref{eq:C_k_large} occurs with probability at most~$2/k^2\log N$, and
  hence, as observed above, summing over all~$2\leq
  k\leq N/4$, Lemma~\ref{lem:order_of_C_k_lwbd} follows.
\end{proof}

We shall now prove Claim~\ref{claim:pairwise_inter} and
Lemma~\ref{lem:neg_correlated}.

\begin{proof}[Proof of Claim~\ref{claim:pairwise_inter}]

%   To prove this claim, we shall consider first the following situation.
%   Suppose~$u=(e_i)_{1\leq i\leq m}$, $v=(f_i)_{1\leq i\leq m}$,
%   and~$w=(g_i)_{1\leq i\leq m}$ are independently chosen random vectors from
%   the uniform space~$\{-1,1\}^m$.  Moreover, let~$x$ and~$y$ be arbitrary
%   integers.  Clearly, by independence, 
%   \begin{equation}
%     \label{eq:really_indep}
%     \PP\big(\<u,v\>=x\text{ and }\<u,w\>=y\big)
%     =\PP\big(\<u,v\>=x\big)\PP\big(\<u,w\>=y\big).
%   \end{equation}
%   Let~$A=\{i\in[m]\:f_i=g_i\}$ and~$B=[m]\setminus A$, and put~$n_1=|A|$
%   and~$n_2=|B|$.  Clearly, $A$~and~$B$ are random sets.  Let~$u^A=(e_i)_{i\in
%     A}$ and~$u^B=(e_i)_{i\in B}$, and define analogously the vectors~$v^A$,
%   $v^B$, $w^A$, and~$w^B$.  Clearly, $v^A=w^A$ and~$v^B=-w^B$ and hence
%   \begin{align*}
%     \<u,v\>&=\<u^A,v^A\>+\<u^B,v^B\>,\\
%     \<u,w\>&=\<u^A,v^A\>-\<u^B,v^B\>.
%   \end{align*}
%   Observe now that~$\<u^A,v^A\>$ has the same distribution as~$S^\pm(n_1)$,
%   the sum of~$n_1$ independent, symmetric $\pm1$-random variables.  Similarly,
%   $\<u^B,v^B\>$ has the same distribution as~$S^\pm(n_2)$.  Since $\<u,v\>=x$
%   and $\<u,w\>=y$ if and only if~$\<u^A,v^A\>=(x+y)/2$
%   and~$\<u^B,v^B\>=(x-y)/2$, we have that the probability
%   in~\eqref{eq:really_indep} is
%   \begin{equation}
%     \label{eq:the_prob}
%     \PP\big(S^\pm(n_1)=(x+y)/2\text{ and }S^\pm(n_2)=(x-y)/2\big).
%   \end{equation}
  
  Let us consider the events~$A(D)$ and~$A(D')$ for two distinct~$D$,
  $D'\in\cD_k$.
%   We shall show that, for any fixed~$x$ and~$y$, we have
%   \begin{equation}
%     \label{eq:prove_indep}
%     \PP\big(\<u,v_D\>=x\text{ and }\<u,v_{D'}\>=y\big)
%     =\PP\big(\<u,v_D\>=x\big)\PP\big(\<u,v_{D'}\>=y\big).
%   \end{equation}
  Let~$D=(d_1,\dots,d_{k-1})$ and~$D'=(d_1',\dots,d_{k-1}')$, and recall that 
  \begin{equation*}
    m\leq d_1<\dots<d_{k-1}\leq2m,\qquad
    m\leq d_1'<\dots<d_{k-1}'\leq2m,
  \end{equation*}
  and that
  \begin{align*}
    v_D&=(e_{1+d_1}e_{1+d_2}\dots e_{1+d_{k-1}},
    \dots,e_{m+d_1}e_{m+d_2}\dots e_{m+d_{k-1}}),\\
    v_{D'}&=(e_{1+d_1'}e_{1+d_2'}\dots e_{1+d_{k-1}'},
    \dots,e_{m+d_1'}e_{m+d_2'}\dots e_{m+d_{k-1}'}).
  \end{align*}
  Let~$v_i^D=e_{i+d_1}\dots e_{i+d_{k-1}}$ and~$v_i^{D'}=e_{i+d_1'}\dots
  e_{i+d_{k-1}'}$ ($1\leq i\leq m$) be the components of~$v_D$ and~$v_{D'}$.
  For convenience, let us write~$\omega\inU\Omega$ if~$\omega$ is a uniformly
  distributed random element of~$\Omega$.  We shall prove more
  than~\eqref{eq:pairwise_inter}; we shall prove that
  \begin{equation}
    \label{eq:componentwise_ind}
    (e_1v_1^D,\dots,e_mv_m^D,e_1v_1^{D'},\dots,e_mv_m^{D'})\inU\{-1,1\}^{2m}. 
  \end{equation}
  Clearly, this proves Claim~\ref{claim:pairwise_inter},
  because~$\<u,v_D\>=\sum_{1\leq i\leq m}e_iv_i^D$ and~$\<u,v_D\>=\sum_{1\leq
    i\leq m}e_iv_i^{D'}$.

  To check~\eqref{eq:componentwise_ind}, we make the following
  observation: we have
  \begin{equation}
    \label{eq:x_iy_i_ind.a}
    (x_1,\dots,x_m,y_1,\dots,y_m)\inU\{-1,1\}^{2m}
  \end{equation}
  if and only if
  \begin{equation}
    \label{eq:x_iy_i_ind.b}
    (x_1,\dots,x_m,x_1y_1,\dots,x_my_m)\inU\{-1,1\}^{2m}.
  \end{equation}
  This observation follows immediately from the fact that the map that takes
  the vector in~\eqref{eq:x_iy_i_ind.a} to the vector
  in~\eqref{eq:x_iy_i_ind.b} is a bijection (it is in fact an involution).

  We apply the observation above to
  \begin{equation}
    \label{eq:actual_x_iy_i}
    x_i=e_iv_i^D\quad\text{and}\quad y_i=e_iv_i^{D'}\quad(1\leq i\leq m)
  \end{equation}
  to obtain that~\eqref{eq:componentwise_ind} holds if and only if
  \begin{multline}
    \label{eq:x_iy_i_ind.aa}
    (x_1,\dots,x_m,x_1y_1,\dots,x_my_m)\\
    =(e_1v_1^D,\dots,e_mv_m^D,v_1^Dv_1^{D'},\dots,v_m^Dv_m^{D'})
    \inU\{-1,1\}^{2m}.
  \end{multline}
  However, \eqref{eq:x_iy_i_ind.aa}~does hold.  Indeed, since~$D\neq D'$, a
  moment's thought shows that
  \begin{equation}
    \label{eq:v_iDv_iD'_ind}
    (v_1^Dv_1^{D'},\dots,v_m^Dv_m^{D'})\inU\{-1,1\}^m.
  \end{equation}
  (To see~\eqref{eq:v_iDv_iD'_ind}, note that the value of~$v_i^Dv_i^{D'}$
  ($1\leq i\leq m$) is determined by the~$e_j$ with
  \begin{equation}
    \label{eq:j_in_i+symmdiff}
    j\in i+D\triangle D'=i+(D\setminus D')\cup(D'\setminus D)
  \end{equation}
  alone, and the family of sets~$i+D\triangle D'$ ($1\leq i\leq m$) form a
  ``hypertree''.  We shall not elaborate on this simple argument.)
  Fact~\eqref{eq:v_iDv_iD'_ind} and the fact that the~$e_i$ ($1\leq i\leq m$)
  are not involved in~\eqref{eq:v_iDv_iD'_ind} at all
  imply~\eqref{eq:x_iy_i_ind.aa}, and hence~\eqref{eq:componentwise_ind} does
  hold.  This completes the proof of Claim~\ref{claim:pairwise_inter}.
\end{proof}

\begin{proof}[Proof of Lemma~\ref{lem:neg_correlated}]
  Let~$f=\sum_{1\leq j\leq M}\chi_j$, where~$\chi_j$ denotes the
  characteristic function of the event~$A_j$.  We have
  \begin{equation}
    \label{eq:total_sum}
    \int f\;\rmd\PP=\sum_{1\leq j\leq M}\PP(A_j)\geq Mp,
  \end{equation}
  and
  \begin{multline}
    \label{eq:tot_square}
    \int f^2\;\rmd\PP
    =\int\Big(\sum_{1\leq j\leq M}\chi_j
    +2\sum_{1\leq i<j\leq M}\chi_i\chi_j\Big)\;\rmd\PP\\
    \leq\int f\;\rmd\PP+M(M-1)p^2(1+\epsilon).
  \end{multline}
  Let~$X=\bigcup_{1\leq j\leq M}A_j$.  By the Cauchy--Schwarz inequality, we
  have
  $$
  \Big(\int_X1\;\rmd\PP\Big)
  \Big(\int_Xf^2\;\rmd\PP\Big)
  \geq\Big(\int_Xf\;\rmd\PP\Big)^2,
  $$
  which, together with~\eqref{eq:tot_square}, gives
  $$
  \PP(X)\Big(\int f\;\rmd\PP+M(M-1)p^2(1+\epsilon)\Big)
  \geq\Big(\int_Xf\;\rmd\PP\Big)^2.
  $$
  Therefore
  \begin{multline}
    \label{eq:neg_corr_final}
    \PP(X)
    \geq
    \Big(\int_Xf\;\rmd\PP\Big)^2
    \Big/\Big(\int f\;\rmd\PP+M(M-1)p^2(1+\epsilon)\Big)\\
    \geq{M^2p^2\over Mp+M(M-1)p^2(1+\epsilon)}
    ={Mp\over1+(M-1)p(1+\epsilon)},
  \end{multline}
  and the lemma follows.  
\end{proof}

% \begin{proof}[Proof of Claim~\ref{claim:pairwise_inter}]
%   Fix~$i\neq j$ as in the statement of our claim.  Recall that we are
%   conditioning on~$\pi_R(E_N)=z=(e_r)_{2m<r\leq N}$.  To
%   estimate~$\PP(A(i)\cap A(j))$, consider the partition~$A\cup B$
%   of~$\{1,\dots,m\}$ with
%   \begin{equation}
%     \label{eq:A_def}
%     A=A(z)=\{r\:1\leq r\leq m\text{ and }e_{i+r-1}=e_{j+r-1}\}
%   \end{equation}
%   and
%   \begin{equation}
%     \label{eq:B_def}
%     B=B(z)=\{1,\dots,m\}\setminus A.
%   \end{equation}
%   Let~$n_1=|A|$ and~$n_2=|B|$.  Put~$w_A=(e_r')_{r\in A}$
%   and~$w_B=(e_r')_{r\in B}$, where~$e_r'=e_{i+r-1}$ for~$1\leq r\leq m$.
%   Given~$u=(u_r)_{1\leq r\leq m}\in\{-1,1\}^m$, let~$u_A=(u_r)_{r\in A}$
%   and~$u_B=(u_r)_{r\in B}$.  We have
%   \begin{equation}
%     \label{eq:uv_i_prod}
%     \<u,v_i\>=\<u_A,w_A\>+\<u_B,w_B\>
%   \end{equation}
%   and
%   \begin{equation}
%     \label{eq:uv_j_prod}
%     \<u,v_j\>=\<u_A,w_A\>-\<u_B,w_B\>.
%   \end{equation}
  
%   We now make the following simple observation.  Suppose~$C>0$.
%   Then~\eqref{eq:ineq1}, \eqref{eq:ineq2}, and~\eqref{eq:ineq2.5} below are
%   equivalent:
%   \begin{gather}
%     \label{eq:ineq1}
%     |a+b|>C\text{ and }|a-b|>C,\\
%     \label{eq:ineq2}
%     |a|+|b|>C\text{ and }\big||a|-|b|\big|>C\\
%     \label{eq:ineq2.5}
%     \big||a|-|b|\big|>C.
%   \end{gather}
%   Moreover, if we further suppose that~$|a|>|b|$, then~\eqref{eq:ineq1},
%   \eqref{eq:ineq2}, and~\eqref{eq:ineq2.5} are equivalent to
%   \begin{equation}
%     \label{eq:ineq3}
%     |a|>C+k\text{ and }|b|=k\text{ for some~$k\geq0$}.
%   \end{equation}

%   Therefore, the event~$A(i)\cap A(j)$, namely, 
%   $$
%   |\<u,v_i\>|>c(m)\sqrt m\text{ and }|\<u,v_j\>|>c(m)\sqrt m
%   $$
%   is equivalent to
%   \begin{multline}
%     \label{eq:possibility1}
%     |\<u_B,w_B\>|=k
%     \text{ for some~$k\geq0$ with $k\equiv n_2\!\!\!\!\pmod2$}\\
%     \text{ and }|\<u_A,w_A\>|>c(m)\sqrt m+k,
%   \end{multline}
%   or else
%   \begin{multline}
%     \label{eq:possibility2}
%     |\<u_A,w_A\>|=k\text{ for some~$k\geq0$ with $k\equiv
%       n_1\!\!\!\!\pmod2$}\\
%     \text{ and }|\<u_B,w_B\>|>c(m)\sqrt m+k. 
%   \end{multline}
  
%   \begin{fact}
%     \label{fact:each_prob}
%     We have
%     \begin{equation}
%       \label{eq:prob_poss1_happens}
%       \PP(\text{\eqref{eq:possibility1} holds})\leq(1+o(1))/2m^2
%     \end{equation}
%     and
%     \begin{equation}
%       \label{eq:prob_poss2_happens}
%       \PP(\text{\eqref{eq:possibility2} holds})\leq(1+o(1))/2m^2.
%     \end{equation}
%   \end{fact}
  
%   Clearly, Fact~\ref{fact:each_prob} completes the proof of
%   Claim~\ref{claim:pairwise_inter}.
% \end{proof}

%We prove Fact~\ref{fact:each_prob} in what follows.

% \begin{proof}[Proof of Fact~\ref{fact:each_prob}]
%   We shall only prove~\eqref{eq:prob_poss1_happens} (the argument is the same
%   for~\eqref{eq:prob_poss2_happens}).  We first claim that
%   \begin{equation}
%     \label{eq:prob_intersec1}
%     \PP(\text{\eqref{eq:possibility1} holds})
%     =(1+o(1))\sum_{\ell\geq0}T_\ell,
%   \end{equation}
%   where
%   \begin{equation}
%     \label{eq:T_def}
%     T_\ell=4\sqrt{2\over\pi n_2}e^{-2\ell^2/n_2}
%     {\sqrt{n_1}\over\sqrt{2\pi}\(c(m)\sqrt m+2\ell\)}
%     \exp\left\{-2\({c(m)\sqrt m+2\ell}\over2\sqrt{n_1}\)^2\right\}.
%   \end{equation}
%   To prove~\eqref{eq:prob_intersec1}--\eqref{eq:T_def}, we make use of
%   Fact~\ref{fact:1/2Bin}.  Then
%   \begin{equation}
%     \label{eq:sum_T1}
%     \PP(\text{\eqref{eq:possibility1} holds})
%     =\sum_k\PP(S^\pm(n_2)=k)\PP\big(S^\pm(n_1)>c\sqrt m+k\big),
%   \end{equation}
%   where the sum is over all~$k\geq0$ with~$k\equiv n_2\pmod2$,
%   and~$S^\pm(n_2)$ and~$S^\pm(n_1)$ are independent.  We now use that
%   $(S^\pm(n_2)+n_2)/2$ and $(S^\pm(n_1)+n_1)/2$ are binomially distributed
%   with parameters~$n_2$ and~$1/2$ and~$n_1$ and~$1/2$, respectively, and use
%   the estimates in Fact~\ref{fact:1/2Bin}.
%   Then~\eqref{eq:prob_intersec1}--\eqref{eq:T_def} follow easily\ykcomm{One
%     step missing: separate the cases in which $\ell=o(n^{2/3})$ and~$\ell$ is
%     larger.}  in the case in which~$n_2$ is even (the case in which~$n_2$ is
%   odd requires a little more calculation, which we omit).
  
% %   Indeed, \eqref{eq:prob_intersec1} follows from Fact~\ref{fact:1/2Bin}: this
% %   is best seen for the case in which~$n_2$ is even; in that case, one sums
% %   over all even~$k$ in~\eqref{eq:possibility1}, say~$k=2\ell$ ($\ell\geq0$).
% %   Then~\eqref{eq:single_bin} and~\eqref{eq:tails2}
% %   give~\eqref{eq:prob_intersec1}, with the~$T_\ell$ given
% %   in~\eqref{eq:T_def}.
% %   The case in which~$n_2$ is odd is similar.
    
%   Our next claim is that the probability in~\eqref{eq:prob_intersec1}
%   is~$\leq(1+o(1))1/2m^2$.  Indeed, we start by observing that, owing
%   to~\eqref{eq:typical_scalar_prod}, we have
%   $$
%   \sqrt{m\over n_1}=\sqrt2+o\(1\over\log m\)
%   \text{ and }
%   \sqrt{m\over n_2}=\sqrt2+o\(1\over\log m\).
%   $$
%   A quick calculation now shows that we may replace~$n_1$ and~$n_2$
%   by~$m/2$ in~\eqref{eq:T_def}, at the expense of a factor of~$1+o(1)$, to
%   obtain that
%   \begin{multline}
%     \label{eq:simpler_T}
%     T_\ell=\({4\over\pi}+o(1)\){e^{-4\ell^2/m}\over c\sqrt m+2\ell}
%     \exp\left\{-{1\over m}\(c\sqrt m+2\ell\)^2\right\}\\
%     =\({4\over\pi}+o(1)\)e^{-c^2/2}
%     {e^{-2\(2\ell/\sqrt m+c/2\)^2}\over c\sqrt m+2\ell}.
% %    \exp\left\{-2\(2\ell/\sqrt m+c/2\)^2\right\}
%   \end{multline}
%   Now let
%   \begin{equation}
%     \label{eq:S_m_def}
%     S_m=\sum_{\ell\geq0}
%     {e^{-2\(2\ell/\sqrt m+c/2\)^2}\over c\sqrt m+2\ell}.
%   \end{equation}
%   Let~$f(x)=e^{-2x^2}/(x+c/2)$.  Then
%   \begin{equation}
%     \label{eq:S_m_int}
%     S_m={1\over2}\sum_x{2\over\sqrt m}f(x),
%   \end{equation}
%   where the sum is over all~$x\in\{c/2+2\ell/\sqrt
%   m\:\ell\in\ZZ,\;\ell\geq0\}$.  Using~\eqref{eq:S_m_int}, we see that
%   \begin{equation}
%     \label{eq:S_m_int_comp}
%     2S_m\leq{2\over\sqrt m}f(c/2)+\int_{c/2}^\infty f(x)\rmd x
%     ={2e^{-c^2/2}\over c\sqrt m}+\int_{c/2}^\infty f(x)\rmd x.
%   \end{equation}
%   Observe now that, making use of Fact~\ref{fact:normal_int}, we have 
%   \begin{multline}
%     \label{eq:int_estimate}
%     {1\over\sqrt{2\pi}}\int_{c/2}^\infty f(x)\rmd x
%     ={1\over2\sqrt{2\pi}}
%     \int_c^\infty{e^{-y^2/2}\over y/2+c/2}\rmd y\\
%     \leq{1\over2c\sqrt{2\pi}}
%     \int_c^\infty e^{-y^2/2}\rmd y
%     ={1\over2c}\(1-\Phi(c)\)
%     \sim{1\over2c^2\sqrt{2\pi}}e^{-c^2/2}.
%   \end{multline}
%   From~\eqref{eq:order_of_c}, \eqref{eq:S_m_int_comp},
%   and~\eqref{eq:int_estimate} we see that
%   \begin{equation}
%     \label{eq:S_m_sim_int}
%     S_m\leq(1+o(1))\int_{c/2}^\infty f(x)\rmd x
%     \sim{1\over4c^2}e^{-c^2/2}.
%   \end{equation}
%   We may now put together~\eqref{eq:prob_intersec1}, \eqref{eq:simpler_T},
%   \eqref{eq:S_m_def}, and~\eqref{eq:S_m_sim_int} to deduce that
%   \begin{equation*}
% %    \label{eq:prob_intersec1_final}
%     \PP(\text{\eqref{eq:possibility1} holds})
%     \leq\({1\over\pi}+o(1)\){e^{-c^2}\over c^2}
%     \sim{1\over2}\(2e^{-c^2/2}\over c\sqrt{2\pi}\)^2={1\over2m^2},
%   \end{equation*}
%   as required.
% \end{proof}

% \subsubsection{Gugu's remark}
% \label{sec:gugu's_remark}
% Probably, the lower bound in Lemma~\ref{lem:order_of_C_k_lwbd} may be replaced
% by $(1/4)\sqrt{k N\log N}$, at least when~$k=o(N)$ or~$k=O(N^\alpha)$
% where~$\alpha<1$.  The idea is to consider, say, $u=(e_1,\dots,e_m)$,
% where~$m=\lfloor N/3\rfloor$ and, for each $(k-1)$-tuple
% $D=(d_1,\dots,d_{k-1})$ with~$m\leq d_1<\dots< d_{k-1}\leq2m$ consider the
% vector
% $$
% v_D=(e_{1+d_1}e_{1+d_2}\dots e_{1+d_{k-1}},
% \dots,e_{m+d_1}e_{m+d_2}\dots e_{m+d_{k-1}}).
% $$
% The event~$A(D)$ is $|\<u,v_D\>|>\whc(m)\sqrt m$, where~$\whc(m)$ is such that
% $$
% 2{e^{-\whc(m)^2/2}\over\whc(m)\sqrt{2\pi}}={m+1\choose k-1}^{-1}.
% $$
% Since~${m+1\choose k-1}$ is of order~$(m/k)^k>m^{k(1-\alpha)}$, we have
% $$
% \whc(m)>\sqrt{2k(1-\alpha)\log m}.
% $$
% If~$\alpha=1/2$, for instance, we have~$\whc(m)>\sqrt{k\log m}$, and
% $$
% \whc(m)\sqrt m>{1\over4}\sqrt{kN\log N}.
% $$

% We have to show that~$\PP\(\bigcup_DA(D)\)=1-o(1)$.  All that we used is that,
% a.s.\ for all~$i\neq j$, we have that~$\<v_i,v_j\>$ is small (more precisely,
% $\<v_i,v_j\>=O(N\log N)$).  Here, we have 
% $$
% \<v_D,v_{D'}\>\leq\max_{2\leq r\leq2k}C_r(E_N),
% $$
% and hence, a.s., we have $\<v_D,v_{D'}\>\leq5\sqrt{2kN\log N}$, which seems to
% be enough for the previous calculations to go through.

\subsubsection{Proof of Theorem~\ref{thm:C_k_concentrated}}
\label{sec:pfofthm:C_k_concentrated}
Theorem~\ref{thm:C_k_concentrated} follows simply from some well known results
concerning concentration of measure.  Let~$\epsilon$ and~$k=k(N)$ as in the
statement of that theorem be given. 
% Let~$\Gamma(k,N)$ be a \textit{median} for~$C_k(E_N)$;\ykcommb{Use median or
%   expectation?  I'll change this to expectation.}  that is, let~$\Gamma(k,N)$
% be so that
% \begin{equation}
%   \label{eq:median_def}
%   \PP\big(C_k(E_N)\leq\Gamma(k,N)\big)\geq{1\over2}
%   \quad\text{and}\quad
%   \PP\big(C_k(E_N)\geq\Gamma(k,N)\big)\geq{1\over2}.
% \end{equation}
We now observe that if~$E_N=(e_j)_{1\leq j\leq N}$ and~$E_N'=(e_j')_{1\leq
  j\leq N}\in\{-1,1\}^N$ differ in exactly one coordinate, then
\begin{equation}
  \label{eq:V_changes_little}
  |V(E_N,M,D)-V(E_N',M,D)|\leq2k
\end{equation}
for any~$M$ and~$D$.  Indeed, suppose~$e_{j_0}'=-e_{j_0}$ and~$e_j=e_j'$ for
all~$j\neq j_0$.  Note that~$e_{j_0}$ is involved in at most~$k$ summands
in the definition of~$V(E_N,M,D)$ (see~\eqref{eq:V_def}), and hence changing
its value to~$-e_{j_0}$ will change $V(E_N,M,D)$ by at most~$2k$.  Therefore,
\begin{equation}
  \label{eq:C_k_changes_little}
  |C_k(E_N)-C_k(E_N')|\leq2k
\end{equation}
as well.  We may now use, for instance, Lemma~1.2 from~\cite{mcdiarmid89} to
deduce that, for any~$t>0$, we have
\begin{equation}
  \label{eq:McDiarmid_bd}
  \PP\big(|C_k(E_N)-\EE(C_k)|\geq t\big)\leq2\exp\(-t^2/2k^2N\).
\end{equation}
It now suffices to check that if
\begin{equation}
  \label{eq:k_cond}
  k\leq\log N-\log\log N,
\end{equation}
then, taking~$t=\epsilon\EE(C_k)$, we have that the right-hand side
of~\eqref{eq:McDiarmid_bd} is~$o(1)$.

Theorem~\ref{thm:order_of_C_k} tells us that, if~$N$ is large enough, then,
say,
\begin{equation}
  \label{eq:Gamma(N)_bounds}
    \EE(C_k)\geq{1\over5}\sqrt{N\log{N\choose k}}.
\end{equation}
Condition~\eqref{eq:k_cond} on~$k$ and~\eqref{eq:Gamma(N)_bounds} easily imply
that 
\begin{equation}
  \label{eq:concentration_aux}
  {t^2\over2k^2N}={\epsilon^2\EE(C_k)^2\over2k^2N}\to\infty
\end{equation}
as~$N\to\infty$, and this completes the proof of
Theorem~\ref{thm:C_k_concentrated}.

\subsection{The normality measure~$\cN$}
\label{sec:cN_of_random}
Recall that the normality measure of $E_N=(e_1,\dots,e_N)\in\{-1,1\}^N$ is
defined as
\begin{equation}
  \label{eq:N_def2}
  \cN(E_N)=\max_k\max_X\max_M
  \left|T(E_N,M,X)-{M\over2^k}\right|,
\end{equation}
where the maxima are taken over all~$k\leq\log_2N$, $X\in\{-1,1\}^k$,
and~$0<M\leq 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\leq M$ (see~\eqref{eq:T_def}).  Our aim in this section is to prove
Theorem~\ref{thm:order_of_N}.

\begin{proof}[Proof of Theorem~\ref{thm:order_of_N}]
  We start with the lower bound in~\eqref{eq:order_of_N}.  We take~$k=1$
  in~\eqref{eq:N_def2}; in fact, we consider~$T(E_N,N,(1))$, the number of
  occurrences of~$1$ in~$E_N$.  Fact~\ref{fact:1/2Bin} tells us that
  \begin{equation}
    \label{eq:thm_on_cN_best_possible}
    \lim_{N\to\infty}\PP\(
    \left|T(E_N,N,(1))-{N\over2}\right|\geq C\sqrt N\)
    =2\sqrt{2\over\pi}\int_C^\infty e^{-2x^2}\rmd x>0.
  \end{equation}
  Since
  $$
  2\sqrt{2\over\pi}\int_C^\infty e^{-2x^2}\rmd x\to1
  $$
  as~$C\to0$, the lower bound in Theorem~\ref{thm:order_of_N} follows.
  Indeed, the facts above show that, for any~$\epsilon>0$, there is~$\delta>0$
  so that the lower bound in~\eqref{eq:order_of_N} holds with probability at
  least~$1-\epsilon$.  It remains to prove the upper bound for~$\cN(E_N)$ for
  typical sequences~$E_N$.
  
  The basic lemma that we shall use is Lemma~\ref{lem:discrepancy_in_block}
  below.  Recall that we refer to the sets~$B_{m,r}$ as \textit{blocks}
  (recall~\eqref{eq:B_mr_def}).  For an integer~$k\geq1$, $X\in\{-1,1\}^k$,
  and~$B_{m,r}$ a block with
  \begin{equation}
    \label{eq:block_bound}
    \max B_{m,r}=(m+1)2^r\leq N-k+1,    
  \end{equation}
  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,
  \begin{equation}
    \label{eq:T_gen_def}
    T(E_N,B_{m,r},X)=\card\{n\in B_{m,r}\:E_N^{(n)}=X\},
  \end{equation}
  where
  \begin{equation}
    \label{eq:Ej_def}
    E_N^{(n)}=(e_n,e_{n+1},\dots,e_{n+k-1}),
  \end{equation}
  and, as usual, $E_N=(e_1,\dots,e_N)$.

  \begin{lemma}
    \label{lem:discrepancy_in_block}
    Let~$m$ and~$r$ be fixed non-negative integers with~$B_{m,r}\subset[1,N]$.
    For all~$D>0$, the probability that there is~$X\in\{-1,1\}^k$
    with~$k\leq\log_2N$ satisfying~\eqref{eq:block_bound} such that
    \begin{equation}
      \label{eq:large_discrepancy_in_block}
      \left|T(E_N,B_{m,r},X)-2^{r-k}\right|>D\sqrt{2^r}
    \end{equation}
    is at most
    \begin{equation}
      \label{eq:discrepancy_in_block_prob}
      O\(e^{-2D^2/9}\)
      +2(\log_2N)^2N\exp\(-{3D\over4\log_2N}\;2^{r/2}\).
    \end{equation}
  \end{lemma}
  
  We postpone the proof of Lemma~\ref{lem:discrepancy_in_block} and continue
  with the proof of Theorem~\ref{thm:order_of_N}.  Let us apply
  Lemma~\ref{lem:discrepancy_in_block} with
  \begin{equation}
    \label{eq:D_def}
    D=C(K-r)
  \end{equation}
  for all blocks~$B_{m,r}\subset[1,N]$, where
  \begin{equation}
    \label{eq:K_def}
    K=1+\lfloor\log_2N\rfloor,
  \end{equation}
  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}$ \textit{large} if
  \begin{equation}
    \label{eq:r_large_def}
    r\geq4\log_2\log_2N
  \end{equation}
  and \textit{small} otherwise.  We claim that, with the value of~$D$ given
  in~\eqref{eq:D_def} with a large enough constant~$C$,
  inequality~\eqref{eq:large_discrepancy_in_block} holds for some large
  block~$B_{m,r}$ and some~$X\in\{-1,1\}^k$ ($k\leq\log_2N$) with probability
  $O\(e^{-2C^2/9}\)$.
  
  To prove our claim, for convenience, let~$\sum_r'$ indicate sum over
  all~$r<K$ satisfying~\eqref{eq:r_large_def}.  Adding
  up~\eqref{eq:discrepancy_in_block_prob} over all large
  blocks~$B_{m,r}\subset[1,N]$, we get
  \begin{align}
    &\sum_r\nolimits'2^{K-r}O\(e^{-2C^2(K-r)^2/9}\)\nonumber\\
    &\qquad\qquad\qquad+\sum_r\nolimits'
    2^{K-r+1}(\log_2N)^2N\exp\(-{3C(K-r)\over4\log_2N}\;2^{r/2}\)\nonumber\\
    &\qquad\leq\sum_{1\leq\ell\leq K}2^\ell O\(e^{-2C^2\ell^2/9}\)\nonumber\\
    &\qquad\qquad\qquad\qquad+(\log_2N)^2N^2\sum_r\nolimits'
    \exp\(-{3C\over4\log_2N}\;2^{r/2}\)\nonumber\\
    &\qquad=O\(e^{-2C^2/9}\)+O\(1\over N\)=O\(e^{-2C^2/9}\),
    \label{eq:prob_large_blocks}
  \end{align}
  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~\eqref{eq:prob_large_blocks} tends to~$0$
  as~$C\to\infty$, we may and shall suppose henceforth that
  \begin{itemize}
  \item[(**)]\sl for all integers~$m$, $r$, and~$k\leq\log_2N$
    with~$B_{m,r}\subset[1,N]$ satisfying~\eqref{eq:block_bound}
    and~\eqref{eq:r_large_def}, and every~$X\in\{-1,1\}^k$, we have
    $$
    \left|T(E_N,B_{m,r},X)-2^{r-k}\right|\leq C(K-r)\sqrt{2^r}.
    $$
  \end{itemize}
  
  Now fix~$k\leq\log_2N$ and fix~$M$ with~$1\leq M\leq N-k+1$.  Observe that
  we may write~$[1,M]$ as a disjoint union of blocks~$B_{m,r}$
  ($r\leq\log_2M<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_+\cup I_-$ be the partition of~$I$ with
  \begin{equation}
    \label{eq:I_+_def}
    I_+=\{(m,r)\in I\:r\text{ satisfies~\eqref{eq:r_large_def}}\}.
  \end{equation}
  For later reference, observe that
  \begin{equation}
    \label{eq:I_-_size}
    |I_-|<4\log_2\log_2N.
  \end{equation}
  Observe also that if~$(m,r)\in I_-$, then
  \begin{equation}
    \label{eq:small_r_small_dicr}
    \left|T(E_N,B_{m,r},X)-2^{r-k}\right|\leq2^r<(\log_2N)^4
  \end{equation}
  for any~$X\in\{-1,1\}^k$.  Using~(**), \eqref{eq:I_-_size},
  and~\eqref{eq:small_r_small_dicr}, we see that, for any~$X\in\{-1,1\}^k$, we
  have
  \begin{align}
    &\left|T(E_N,M,X)-M2^{-k}\right|
    \leq\sum_{(m,r)\in I}\left|T(E_N,B_{m,r},X)-2^{r-k}\right|\nonumber\\
    &\qquad=\sum_{(m,r)\in I_+}\left|T(E_N,B_{m,r},X)-2^{r-k}\right|
    +\!\!\sum_{(m,r)\in I_-}\left|T(E_N,B_{m,r},X)-2^{r-k}\right|\nonumber\\
    &\qquad\leq\sum_{0\leq r<K}C(K-r)2^{r/2}
    +|I_-|(\log_2N)^4\label{eq:MS_dagger}\\
    &\qquad\leq C2^{K/2}\sum_{1\leq\ell\leq K}\ell2^{-\ell/2}
    +4(\log_2\log_2N)(\log_2N)^4\nonumber\\
    &\qquad=O(2^{K/2})=O(\sqrt N),\nonumber
  \end{align}
  as required.  It now remains to prove Lemma~\ref{lem:discrepancy_in_block}. 
\end{proof}

\begin{proof}[Proof of Lemma~\ref{lem:discrepancy_in_block}]
  Let non-negative integers~$m$ and~$r$ with~$B_{m,r}\subset[1,N]$ be fixed,
  and let~$D$ be a positive real.  Because of the form of the upper bound
  in~\eqref{eq:discrepancy_in_block_prob}, we may suppose that~$D\geq D_0$ for
  some conveniently large absolute constant~$D_0$.  Indeed, if we prove an
  upper bound of the form~\eqref{eq:discrepancy_in_block_prob} for~$D\geq
  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~\eqref{eq:discrepancy_in_block_prob} greater than~$1$, say).
  
  Let us now fix~$k\leq\log_2N$ for which~\eqref{eq:block_bound} holds, and
  let~$X\in\{-1,1\}^k$ be given.  We shall first show that the probability
  that~\eqref{eq:large_discrepancy_in_block} happens for this fixed~$X$ is
  suitably small.
  
  Let us decompose~$B_{m,r}$ in arithmetic progressions with difference~$k$:
  for $0\leq s<k$, let
  \begin{equation}
    \label{eq:I_s_def}
    I_s=\{j\in B_{m,r}\:j\equiv s\hskip-7pt\pmod k\},
  \end{equation}
  so that~$B_{m,r}=\bigcup_{0\leq s<k}I_s$ is a partition of~$B_{m,r}$.
%   We have
%   \begin{equation}
%     \label{eq:I_s_size}
%     |I_s|\in\{\lfloor2^r/k\rfloor, \lceil2^r/k\rceil\}.
%   \end{equation}
  Let
  \begin{equation}
    \label{eq:T_gen_def2}
    T(E_N,I_s,X)=\card\{n\:n\in I_s\text{ and }E_N^{(n)}=X\},
  \end{equation}
  and observe that, clearly, $T(E_N,B_{m,r},X)=\sum_{0\leq s<k}T(E_N,I_s,X)$.
  In particular, if
  \begin{equation}
    \label{eq:small_disc_each_class}
    \left|T(E_N,I_s,X)-|I_s|2^{-k}\right|\leq{1\over k}D\sqrt{2^r}
  \end{equation}
  for all~$0\leq s<k$, then~\eqref{eq:large_discrepancy_in_block} fails.
  Let us fix~$0\leq s<k$, and let us estimate the probability
  that~\eqref{eq:small_disc_each_class} should fail.
  
  Clearly, $T(E_N,I_s,X)$ has binomial distribution~$\Bi(|I_s|,2^{-k})$.
  Therefore, using Fact~\ref{fact:Chernoff}, we see that the probability
  that~\eqref{eq:small_disc_each_class} should fail is at most
  \begin{equation}
    \label{eq:class_s_fail_prob}
    2\exp\(-{t^2\over2(\lambda+t/3)}\),
  \end{equation}
  where~$t=(D/k)2^{r/2}$ and~$\lambda=|I_s|2^{-k}\leq2^{r-k}$.
  If~$\lambda\geq t/3$, then~\eqref{eq:class_s_fail_prob} is at most 
  \begin{equation}
    \label{eq:class_s_fail_prob2}
    2\exp\(-{t^2\over4\lambda}\)
    \leq2\exp\(-{D^22^r/k^2\over2^{r-k+2}}\)
    =2e^{-D^22^{k-2}/k^2}.
  \end{equation}
  If, on the other hand, $\lambda<t/3$, then~\eqref{eq:class_s_fail_prob} is
  at most
  \begin{equation}
    \label{eq:class_s_fail_prob3}
%    2\exp\(-{t^2\over4t/3}\)
%    =
    2\exp\(-{3\over4}t\)
    =2\exp\(-{3D\over4k}2^{r/2}\)
    \leq2\exp\(-{3D\over4\log_2N}2^{r/2}\).
  \end{equation}
  Below, rather crudely, we bound~\eqref{eq:class_s_fail_prob} by the sum
  of~\eqref{eq:class_s_fail_prob2} and~\eqref{eq:class_s_fail_prob3}.  Indeed,
  we add up~\eqref{eq:class_s_fail_prob2} and~\eqref{eq:class_s_fail_prob3}
  over all choices of~$s$ ($0\leq s<k$) and~$X\in\{-1,1\}^k$, and get
  that the probability that~\eqref{eq:large_discrepancy_in_block} should hold
  for some~$X\in\{-1,1\}^k$ ($k\leq\log_2N$) is
  \begin{equation}
    \label{eq:discrepancy_in_block_prob.aux}
    2k2^k\(e^{-D^22^{k-2}/k^2}
    +\exp\(-{3D\over4\log_2N}2^{r/2}\)\).
  \end{equation}
  We now sum~\eqref{eq:discrepancy_in_block_prob.aux} over all~$1\leq
  k\leq\lfloor\log_2N\rfloor=K-1$.  We add up the terms
  in~\eqref{eq:discrepancy_in_block_prob.aux} separately.

  We have
  \begin{equation}
    \label{eq:discrepancy_in_block_prob.aux1}
    2\sum_{1\leq k<K}k2^ke^{-D^22^{k-2}/k^2}
    =4e^{-D^2/2}+2^4e^{-D^2/4}
    +3\times2^4e^{-2D^2/9}S,
  \end{equation}
  where~$S$ is dominated by the sum of a convergent geometric series as
  long as~$D$ is large enough.  Therefore, the sum
  in~\eqref{eq:discrepancy_in_block_prob.aux1} is
  \begin{equation}
    \label{eq:discrepancy_in_block_prob.aux1.5}
    O\(e^{-2D^2/9}\).
  \end{equation}
  Moreover,
  \begin{equation}
    \label{eq:discrepancy_in_block_prob.aux2}
    2\sum_{1\leq k<K}k2^k\exp\(-{3D\over4\log_2N}2^{r/2}\)
    \leq2(\log_2N)^2N\exp\(-{3D\over4\log_2N}2^{r/2}\).
  \end{equation}
  Lemma~\ref{lem:discrepancy_in_block} follows
  from~\eqref{eq:discrepancy_in_block_prob.aux1}%
  --\eqref{eq:discrepancy_in_block_prob.aux2}.  
\end{proof}

% We close this section with two observations about the normality measure and an
% open problem that we find quite attractive.  Put
% \begin{equation}
%   \label{eq:cN_k_def}
%   \cN_k(E_N)=\max_X\max_M\left|T(E_N,M,X)-{M\over2^k}\right|,
% \end{equation}
% where the maxima are taken over all~$X\in\{-1,1\}^k$ and~$0<M\leq N+1-k$.
% Note that, then, we have~$\cN(E_N)=\max\{\cN_k(E_N)\:k\leq\log_2N\}$.
% The following remarks appear in~\cite{alon04:_measur_minimal}.\ykcommb{should
%   we repeat stuff from \cite{alon04:_measur_minimal}?}
% \begin{enumerate}
% \item[(\textit{i})]$\min_{E_N}\cN_k(E_N)=1-2^{-k}$ for any fixed~$k$
%   and~$N\geq2^k$: we consider powers of appropriate de Bruijn sequences.  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 many times.
  
% \item[(\textit{ii})]$\min_{E_N}\cN(E_N)\geq(1/2-o(1))\log_2N$: if a
%   sequence~$E_N\in\{-1,1\}^N$ contains no segment of
%   length~$k=\log_2N-\log_2\log_2N$ of repeated~$1$s (say),
%   then~$\cN_k(E_N)\geq\log_2N=N/2^k$.  If~$E_N$ contains such a segment, then
%   $$
%   \cN_1(E_N)\geq{1\over2}k={1\over2}(\log_2N-\log_2\log_2N).
%   $$
% \end{enumerate}

\section{Small $W(E_N)$ and $\cN(E_N)$}
\label{sec:small_flucts}

\subsection{The probability of having~$W(E_N)$ small}
\label{sec:small_well_distribution}
Our\ykcomm{Section~\ref{sec:small_flucts} has been scrutinized the least, but
  I hope it's OK now.  Section~\ref{sec:small_well_distribution} is better
  than Section~\ref{sec:small_normality}.} aim in this section is to prove
Theorem~\ref{thm:small_W}, which tells us that, given any~$\delta>0$, the
probability of the event~$W(E_N)\leq\delta\sqrt N$ is bounded away from~$0$.

The proof of Theorem~\ref{thm:small_W} is given in
Section~\ref{sec:proof_of_small_W}, but a key `positive correlation' result is
first proved in Section~\ref{sec:preliminary-lemmas}.  To be a little more
precise, Claim~\ref{claim:small_W.C}, needed in the proof of
Theorem~\ref{thm:small_W}, is proved by invoking a general correlation result
given in Corollary~\ref{cor:concentration} in
Section~\ref{sec:preliminary-lemmas}.

\subsubsection{Preliminary lemmas}
\label{sec:preliminary-lemmas}
We start with some preliminary results concerning distributions on the
integers, that is, vectors~$(p_n)_{n\in\ZZ}$ with~$\sum_{n\in\ZZ}p_n=1$ and
$p_n\geq0$ for all~$n$.  Let us say that the distribution~$(p_n)_{n\in\ZZ}$ is
\textit{symmetric} if~$p_n=p_{-n}$ for all~$n$ and \textit{monotone}
if~$p_n\geq p_{n+1}$ for all~$n\geq0$.

Let~$(p_n)=(p_n)_{n\in\ZZ}$ and~$(q_n)=(q_n)_{n\in\ZZ}$ be two distributions.
We shall say that~$(p_n)$ is \textit{more concentrated than}~$(q_n)$ if, for
all~$k\geq0$, we have
\begin{equation}
  \label{eq:concentrated_def}
  \sum_{|n|\leq k}p_n\geq\sum_{|n|\leq k}q_n.
\end{equation}
We shall write~$(p_n)\geq(q_n)$ to indicate that~$(p_n)$ is more concentrated
than~$(q_n)$.

If~$P=(p_n)_{n\in\ZZ}$ and~$Q=(q_n)_{n\in\ZZ}$ are two distributions, we
write~$P+Q$ for the distribution~$(s_n)_{n\in\ZZ}$ given by the convolution
of~$(p_n)$ and~$(q_n)$, that is, $s_n=\sum_{k\in\ZZ}p_kq_{n-k}$.  Clearly,
\begin{itemize}
\item[(\ddag)]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$.
\end{itemize}
In what follows, we shall have integer-valued random variables that
\textit{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\geq p_{n+2}$ for all~$n\geq0$.
The notions of symmetry and concentration do not need to be changed.

\begin{lemma}
  \label{lem:concentration_lemma}
  {\rm(\textit{i})}~Let~$P=(p_n)_{n\in\ZZ}$, $Q=(q_n)_{n\in\ZZ}$, and
  $R=(r_n)_{n\in\ZZ}$ be monotone and symmetric distributions with~$Q\geq R$.
  Then~$P+Q$ and~$P+R$ are monotone and symmetric and, moreover, $P+Q\geq
  P+R$.
  
  {\rm(\textit{ii})}~Suppose now that~$P$, $Q$, and~$R$ have parity, are
  monotone and symmetric, and~$Q\geq R$.  Then~$P+Q$ and~$P+R$ have parity,
  are monotone and symmetric, and $P+Q\geq P+R$.
\end{lemma}
\begin{proof}
  We shall consider~(\textit{i}) first.  Let~$P+Q=(s_n)_{n\in\ZZ}$.  Then,
  using that~$P$ and~$Q$ are symmetric, for any~$n$ we
  have~$s_{-n}=\sum_{k\in\ZZ}p_kq_{-n-k}=\sum_{k\in\ZZ}p_{-k}q_{n+k}
  =\sum_{k\in\ZZ}p_kq_{n-k}=s_n$, and hence~$(s_n)$ is symmetric.  Now
  let~$n\in\ZZ$ be fixed.  We have
  \begin{multline}
    \label{eq:monotone.1}
    s_n=p_0q_n+\sum_{k=1}^\infty(p_kq_{n-k}+p_{-k}q_{n+k})\\
    =p_0q_n+\sum_{k=1}^\infty p_k(q_{n-k}+q_{n+k})
    =\sum_{k=0}^\infty(p_k-p_{k+1})\sum_{j=-k}^kq_{n+j}.
  \end{multline}
  Since~$P$ is monotone, we have~$p_k-p_{k+1}\geq0$ for all~$k\geq0$;
  since~$Q$ is monotone and symmetric, we have~$q_{n-k}\geq q_{n+1+k}$ for
  all~$n\geq0$ and all~$k\geq0$, which is equivalent
  to~$\sum_{j=-k}^kq_{n+j}\geq\sum_{j=-k}^kq_{n+1+j}$.  It follows that, for
  all~$n\geq0$, we have
  \begin{multline}
    \label{eq:monotone.2}
    s_n=\sum_{k=0}^\infty(p_k-p_{k+1})\sum_{j=-k}^kq_{n+j}
    \geq\sum_{k=0}^\infty(p_k-p_{k+1})\sum_{j=-k}^kq_{n+1+j}=s_{n+1},
  \end{multline}
  and hence~$(s_n)$ is also monotone.  
  
  Now recall that~$R=(r_n)$ and let~$P+R=(\wts_n)_{n\in\ZZ}$.  Observe that,
  for all~$\ell$ and~$k$, the sum~$\sum_{n=-\ell}^\ell\sum_{j=-k}^kq_{n+j}$
  may be written as a linear combination of terms of the
  form~$\sum_{i=-m}^mq_i$, with non-negative coefficients (this may be checked
  by induction on~$\min\{\ell,k\}$).  This observation and the fact
  that~$Q\geq R$ let us deduce from~\eqref{eq:monotone.1} that
  \begin{multline}
    \label{eq:concentration}
    \sum_{n=-\ell}^\ell s_n
    =\sum_{k=0}^\infty(p_k-p_{k+1})\sum_{n=-\ell}^\ell\sum_{j=-k}^kq_{n+j}\\
    \geq\sum_{k=0}^\infty(p_k-p_{k+1})\sum_{n=-\ell}^\ell\sum_{j=-k}^kr_{n+j}
    =\sum_{n=-\ell}^\ell\wts_n,
  \end{multline}
  and hence~$P+Q\geq P+R$, as required.  
  
  We now turn to~(\textit{ii}) (we shall be somewhat sketchy now).\ykcomm{The
    proofs of the assertions in~(\textit{ii}) are sketchy, but I hope they are
    OK.} Suppose that~$P$, $Q$, and~$R$ have parity, are monotone and
  symmetric, and~$Q\geq R$.  The fact that~$P+Q$ and~$P+R$ have parity follows
  easily from~(\ddag).  The symmetry of the distributions~$P+Q$ and~$P+R$
  follows easily from the symmetry of~$P$, $Q$, and~$R$, as in~(\textit{i}).
  It remains to consider monotonicity and concentration.
  
  We need the following variants of~\eqref{eq:monotone.1}.  Suppose first
  that~$P$ is a distribution supported on the \textit{even} integers.  If~$n$
  has the parity of~$Q$ (that is, $Q$~is supported on the integers with the
  same parity as~$n$), then
  \begin{equation}
    \label{eq:s_n.P_even}
    s_n=\sum_{k=0}^\infty(p_{2k}-p_{2k+2})\sum_{j=-k}^kq_{n+2j}.  
  \end{equation}
  If~$n$ does not have the parity of~$Q_n$, then~$s_n=0$.  Now suppose
  that~$P$ is a distribution supported on the \textit{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
  \begin{equation}
    \label{eq:s_n.P_odd}
    s_n=\sum_{k=1}^\infty(p_{2k-1}-p_{2k+1})\sum_{j=1}^k
    (q_{n-(2j-1)}+q_{n+(2j-1)}). 
  \end{equation}
  The monotonicity of~$P+Q$ follows from~\eqref{eq:s_n.P_even}
  and~\eqref{eq:s_n.P_odd}, as in~(\textit{i}), and, of course, the
  monotonicity of~$P+R$ follows similarly.  The fact that~$P+Q\geq P+R$
  follows from~\eqref{eq:s_n.P_even} and~\eqref{eq:s_n.P_odd}, as
  in~(\textit{i}) above.
\end{proof}

We shall now discuss a consequence of Lemma~\ref{lem:concentration_lemma} that
will be needed later.  Let
\begin{equation}
  \label{eq:_disjoint_sets}
  A_1,B_1,\dots,A_k,B_k,C
\end{equation}
be pairwise disjoint subsets of~$[n]=\{1,\dots,n\}$.
Let~$(e_i)_{i\in[n]}\in\{-1,1\}^n$ be given, and write~$\whA_j$, $\whB_j$,
and~$\whC$ for the sum of the~$e_i$ over the respective sets; e.g.,
\begin{equation}
  \label{eq:whA_j_def}
  \whA_j=\sum_{i\in A_j}e_i
\end{equation}
for all~$1\leq j\leq k$.  In what follows, we suppose
that~$(e_i)_{i\in[n]}\in\{-1,1\}^n$ is chosen uniformly at random.  Note that,
then, the random variables~$\whA_j$ have parity~$|A_j|\bmod2$, and have
distributions that are symmetric and monotone, and similarly for~$\whB_j$
and~$\whC$.  We are interested in the following consequence of
Lemma~\ref{lem:concentration_lemma}.

\begin{corollary}
  \label{cor:concentration}
  For all~$r,s_1,\dots,s_k\geq0$, we have
  \begin{multline}
    \label{eq:concentration_cor}
    \PP(|\whA_1+\dots+\whA_k+\whC|\leq r
    \cond|\whA_j+\whB_j|\leq s_j\text{ all }1\leq j\leq k)\\
    \geq\PP(|\whA_1+\dots+\whA_k+\whC|\leq r).
  \end{multline}
\end{corollary}
\begin{proof}
  Let~$P^{(j)}=(p_n^{(j)})$ be the distribution of~$\whA_j$ conditioned
  on~$|\whA_j+\whB_j|\leq s_j$.  Let~$\wtP^{(j)}$ be the (unconditional)
  distribution of~$\whA_j$.  %Of course, $\wtP^{(j)}$ is a binomial.  

  \begin{claim}
    \label{claim:concentration_cor}
    The distributions~$P^{(j)}$ and~$\wtP^{(j)}$ have parity~$|A_j|\bmod2$ and
    are symmetric and monotone.  Moreover, $P^{(j)}\geq\wtP^{(j)}$.
  \end{claim}
  
  Let us postpone the proof of Claim~\ref{claim:concentration_cor}.  To
  prove~\eqref{eq:concentration_cor}, it suffices to apply
  Lemma~\ref{lem:concentration_lemma} to conclude that
  \begin{equation}
    \label{eq:concentration_final}
    P^{(1)}+\dots+P^{(k)}+Q\geq\wtP^{(1)}+\dots+\wtP^{(k)}+Q,
  \end{equation}
  where~$Q$ is the distribution of~$\whC$.
\end{proof}

We now prove Claim~\ref{claim:concentration_cor}.

\begin{proof}[Proof of Claim~\ref{claim:concentration_cor}]
  Let~$A=A_j$ and~$B=B_j$.  We shall first prove that~$P^{(j)}\geq\wtP^{(j)}$.
  We start by observing that
  \begin{equation}
    \label{eq:conc_cor.0}
    \PP(|\whA+\whB|\leq
    k\cond\whA=\ell)\qquad(\ell\equiv|A|\bmod2,\;|\ell|\leq|A|)  
  \end{equation}
  is monotone decreasing in~$|\ell|$.  Here and in what follows we shall
  tacitly suppose that~$\ell$ `has the right parity' (that is,
  $\ell\equiv|A|\bmod2$) and~$|\ell|\leq|A|$.  To see
  that~\eqref{eq:conc_cor.0} is decreasing in~$\ell\equiv|A|\bmod2$, it
  suffices to note that the quantity in~\eqref{eq:conc_cor.0} is equal
  to~$\sum_{n=-\ell-k}^{-\ell+k}\PP(\whB=n)$ and to recall that the
  distribution of~$\whB$ is monotone.
  
  We now show that
  \begin{equation}
    \label{eq:conc_cor.1}
    \PP(|\whA+\whB|\leq k\cond|\whA|\leq r)
    \geq\PP(|\whA+\whB|\leq k).
  \end{equation}
  To prove~\eqref{eq:conc_cor.1}, we first notice that the left-hand side
  of~\eqref{eq:conc_cor.1} is
  \begin{align}
    \PP(|\whA+\whB|\leq k\cond|\whA|\leq r)
    &=\PP(|\whA+\whB|\leq k\text{ and }|\whA|\leq r)/\PP(|\whA|\leq r)
    \nonumber\\
    &=\PP(|\whA|\leq r)^{-1}\sum_{\ell=-r}^r\PP(|\whA+\whB|\leq k\text{ and
    }\whA=\ell)\nonumber\\
    &=\sum_{\ell=-r}^r\PP(|\whA+\whB|\leq k\cond\whA=\ell)
    {\PP(\whA=\ell)\over\PP(|\whA|\leq r)},\label{eq:conc_cor.1_LHS}    
  \end{align}
  and the right-hand side of~\eqref{eq:conc_cor.1} is
  \begin{equation}
    \label{eq:conc_cor.1_RHS}
    \PP(|\whA+\whB|\leq k)
    =\sum_{\ell\in\ZZ}\PP(|\whA+\whB|\leq k\cond\whA=\ell)\PP(\whA=\ell).
  \end{equation}
  From~\eqref{eq:conc_cor.1_LHS} and~\eqref{eq:conc_cor.1_RHS} we see that the
  left-hand side of~\eqref{eq:conc_cor.1} is a weighted average of
  the~$\PP(|\whA+\whB|\leq k\cond\whA=\ell)$ with~$-r\leq \ell\leq r$ with
  weights~$\PP(\whA=\ell)/\PP(|\whA|\leq r)$, whereas the right-hand side
  of~\eqref{eq:conc_cor.1} is a weighted average of the~$\PP(|\whA+\whB|\leq
  k\cond\whA=\ell)$ \textit{over all}~$\ell$ with weights~$\PP(|\whA|=\ell)$.
  
  Now notice that the fact that~\eqref{eq:conc_cor.0} is monotone decreasing
  in~$|\ell|$ implies that, for all~$\ell_2\in\ZZ\setminus[-r,r]$ and
  all~$\ell_1\in[-r,r]\cap\ZZ$ with~$\ell_1\equiv\ell_2\equiv|A|\bmod2$, we
  have
  \begin{equation}
    \label{eq:conc_cor.2}
    \PP(|\whA+\whB|\leq k\cond|\whA|=\ell_2)
    \leq\PP(|\whA+\whB|\leq k\cond|\whA|=\ell_1).
  \end{equation}
  Inequality~\eqref{eq:conc_cor.1} follows from~\eqref{eq:conc_cor.1_LHS},
  \eqref{eq:conc_cor.1_RHS}, and~\eqref{eq:conc_cor.2}.
  
  Inequality~\eqref{eq:conc_cor.1} is equivalent to
  \begin{equation}
    \label{eq:conc_cor.3}
    \PP(|\whA+\whB|\leq k\text{ and }|\whA|\leq r)/\PP(|\whA|\leq r)
    \geq\PP(|\whA+\whB|\leq k).
  \end{equation}
  It follows from~\eqref{eq:conc_cor.3} that
  \begin{multline}
    \label{eq:conc_cor.4}
    \PP(|\whA|\leq r\cond|\whA+\whB|\leq k)\\
    =\PP(|\whA+\whB|\leq k\text{ and }|\whA|\leq r)/\PP(|\whA+\whB|\leq k) 
    \geq\PP(|\whA|\leq r),
  \end{multline}
  and hence~$P^{(j)}\geq\wtP^{(j)}$ does indeed hold.
  
  It remains to show that the distribution of~$\whA$ conditioned
  on~$|\whA+\whB|\leq r$ is symmetric and monotone.  The fact that this
  distribution is symmetric is immediate.  To see that this distribution is
  monotone, note that~$\PP(|\whA|=\ell+2)\leq\PP(|\whA|=\ell)$ for
  all~$\ell\geq0$ and recall that~$\PP(|\whA+\whB|\leq
  r\cond|\whA|=\ell+2)\leq\PP(|\whA+\whB|\leq r\cond|\whA|=\ell)$ for
  all~$\ell\geq0$ (recall that~\eqref{eq:conc_cor.0} is decreasing
  in~$|\ell|\equiv|A|\bmod2$).  It follows that
  \begin{align}
    &\PP(|\whA|=\ell+2\cond|\whA+\whB|\leq r)\nonumber\\
    &\qquad\qquad=\PP(|\whA+\whB|\leq r\cond|\whA|=\ell+2)
    {\PP(|\whA|=\ell+2)\over\PP(|\whA+\whB|\leq r)}\nonumber\\
    &\qquad\qquad\leq\PP(|\whA+\whB|\leq r\cond|\whA|=\ell)
    {\PP(|\whA|=\ell)\over\PP(|\whA+\whB|\leq r)}\nonumber\\
    &\qquad\qquad=\PP(|\whA|=\ell\cond|\whA+\whB|\leq r),
    \label{eq:conc_cor.4b}
  \end{align}
  as required.\ykcomm{I've revised Section~\ref{sec:small_well_distribution}
    reasonably well up to here.  I hope Section~\ref{sec:proof_of_small_W} is
    all right.}
\end{proof}

\subsubsection{Proof of Theorem~\ref{thm:small_W}}
\label{sec:proof_of_small_W}
We are now ready to prove Theorem~\ref{thm:small_W}.  The reader may find it
useful to recall the proof of Theorem~\ref{thm:order_of_W}, given in
Section~\ref{sec:W_of_random}.  For convenience, let us fix the following
notation: given~$E_N=(e_1,\dots,e_N)\in\{-1,1\}^N$ and~$Q\subset[1,N]\cap\ZZ$,
we let
\begin{equation}
  \label{eq:U(E_N;Q)_def}
  U(E_N;Q)=\sum_{q\in Q}e_q.
\end{equation}
In what follows, $Q$~will usually be an arithmetic progression.

%\begin{proof}[Proof of Theorem~\ref{thm:small_W} (Under revision...)]

Let us now start the proof of Theorem~\ref{thm:small_W} proper.
Let~$\delta>0$ be given.  To define the constant~$c(\delta)>0$ as promised in
Theorem~\ref{thm:small_W}, we define some auxiliary constants.  Let us first
fix a constant~$C(\delta)\geq2$ for which we have
\begin{equation}
  \label{eq:C(delta)_def}
  40e^{-C(\delta)^2/4}\leq{1\over3}.
\end{equation}
Let~$\ell(\delta)$ be the smallest integer for which we have
\begin{equation}
  \label{eq:ell(delta)_def}
  2C(\delta)\sum_{\ell>\ell(\delta)}\ell2^{-\ell/2}\leq{1\over2}\delta. 
\end{equation}
We now let~$b(\delta)$ be the smallest integer such that
\begin{equation}
  \label{eq:b(delta)_def}
  2^{\ell(\delta)+2}\sum_{b>b(\delta)}be^{-\sqrt b/4}\leq{1\over3} 
\end{equation}
and
\begin{equation}
  \label{eq:b(delta)_def.2}
  {8\over b(\delta)^{1/4}}\leq{1\over2}\delta.
\end{equation}
Unfortunately, it will still take a little while for us to
deliver~$c(\delta)$ (see~\eqref{eq:c_def_small_W}).

We consider the case~$N=2^k$ (the case~$2^{k-1}<N\leq 2^k$ is
similar).\ykcommb{I suppose this power of~$2$ thing is all right.}  As in
Section~\ref{sec:W_of_random}, for all~$0\leq r\leq k$ and~$0\leq m<2^{k-r}$,
we consider the blocks~$B_{m,r}=(m2^r,(m+1)2^r]\cap\ZZ\subset[1,N]$ defined
in~\eqref{eq:B_mr_def}.  In what follows, we shall always have the relation
\begin{equation}
  \label{eq:ell=k-r}
  \ell=k-r.
\end{equation}
(Later on in this proof we shall focus on ``large blocks'', for which~$k$
and~$r$ differ by a constant that depends only on~$\delta$, and hence it will
be convenient to consider the ``gap''~$\ell=k-r$.)  We also set
\begin{equation}
  \label{eq:r_0+T_def}
  r_0=k-\ell(\delta)\quad\text{and}\quad T=T(\delta)=b(\delta)!.
\end{equation}

Let us now consider the partition
\begin{equation}
  \label{eq:[1,N]_partition}
  [1,N]\cap\ZZ=\bigcup_{0\leq m<2^{\ell(\delta)}}B_{m,r_0}
\end{equation}
of~$[1,N]\cap\ZZ$.  For all~$0\leq m<2^{\ell(\delta)}$ and all~$0\leq
a<T$, let
\begin{equation}
  \label{eq:P(m,a)_def}
  P(m,a)=\{x\in B_{m,r_0}\:x\equiv a\hskip-7pt\pmod T\}.
\end{equation}
The progressions~$P(m,a)$ then partition~$B_{m,r_0}$:
\begin{equation}
  \label{eq:B_{m,r_0}_partition}
  B_{m,r_0}=\bigcup_{0\leq a<T}P(m,a).
\end{equation}
Also, putting together~\eqref{eq:[1,N]_partition}
and~\eqref{eq:B_{m,r_0}_partition}, we have a partition of~$[1,N]\cap\ZZ$
into the progressions~$P(m,a)$:
\begin{equation}
  \label{eq:[1,N]_partition_finer}
  [1,N]\cap\ZZ=\bigcup_m\bigcup_aP(m,a),
\end{equation}
where
\begin{equation}
  \label{eq:m,a_range}
  0\leq m<2^{\ell(\delta)}\quad\text{and}\quad0\leq a<T=T(\delta).
\end{equation}
Clearly, the number of~$P(m,a)$ is~$2^{\ell(\delta)}T(\delta)$.  Given~$m$
and~$a$ as in~\eqref{eq:m,a_range}, we define~$\cG(m,a)$ to be the event
\begin{equation}
  \label{eq:cG(m,a)_def}
  \cG(m,a)=\left\{
    |U(E_N;P(m,a))|\leq{\delta\over2^{\ell(\delta)+1}T(\delta)}\sqrt N 
  \right\}
\end{equation}
and let
\begin{equation}
  \label{eq:cG_def}
  \cG=\bigcap_{m,a}\cG(m,a),
\end{equation}
where~$m$ and~$a$ range over all values in~\eqref{eq:m,a_range}.  (As the
reader may have already guessed, the event in~\eqref{eq:cG_def} is a
``good'' event, and hence the notation.)  Let
\begin{equation}
  \label{eq:wteta(delta)_def}
  \wteta_m(\delta)=\min_{0\leq a<T}\PP(\cG(m,a)).
\end{equation}
Note first that the right-hand side of~\eqref{eq:wteta(delta)_def} is
independent of~$m$ and hence we may simply write~$\wteta(\delta)$
for~$\wteta_m(\delta)$.  A simple but crucial observation is
that~$\wteta(\delta)$ is bounded away from~$0$ (as~$N\to\infty$), as is
\begin{equation}
  \label{eq:eta_def}
  \eta(\delta)=\wteta(\delta)^{2^{\ell(\delta)}T(\delta)}.
\end{equation}
Note that
\begin{equation}
  \label{eq:PP(cG)=eta}
  \PP(\cG)\geq\eta(\delta).
\end{equation}
We finally set
\begin{equation}
  \label{eq:c_def_small_W}
  c=c(\delta)={1\over4}\liminf_{N\to\infty}\eta(\delta)>0.
\end{equation}
We claim that the choice of~$c=c(\delta)$ in~\eqref{eq:c_def_small_W} will
do in Theorem~\ref{thm:small_W}.  More precisely, we make the following
claim. 

\begin{claim}
  \label{claim:small_W}
  We have
  \begin{equation}
    \label{eq:claim-small_W}
    \PP(W(E_N)\leq\delta\sqrt N)\geq{1\over3}\eta(\delta).
  \end{equation}
\end{claim}

We verify Claim~\ref{claim:small_W} in the remainder of this proof.  Let us
say that a block~$B_{m,r}$ is \textit{large} if~$|B_{m,r}|=2^r\geq 2^{r_0}$.
Following the convention in~\eqref{eq:ell=k-r} and recalling the definition
of~$r_0$ (see~\eqref{eq:r_0+T_def}), we see that~$B_{m,r}$ is large if and
only if~$\ell=k-r\leq\ell(\delta)$.  We shall also say that~$B_{m,r}$ is
\textit{small} if it is not large, that is, if~$|B_{m,r}|=2^r<2^{r_0}$, or,
equivalently, if~$\ell=k-r>\ell(\delta)$.

Let us now define two ``bad'' events~$\cF_1$ and~$\cF_2$.  To define~$\cF_1$,
we adapt a definition used in Section~\ref{sec:W_of_random}; an arithmetic
progression contained in~$B_{m,r}$ will be called \textit{complete} if it
cannot be extended within~$B_{m,r}$ keeping the same common difference.  We
shall say that~$\cF_1$ occurs if for some small block~$B_{m,r}$ and some
complete arithmetic progression~$Q$ contained in~$B_{m,r}$ we have
\begin{equation}
  \label{eq:cF_1_def}
  |U(E_N;Q)|>C(\delta)(k-r)\sqrt{2^r}.
\end{equation}

We shall say that~$\cF_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(\delta)$ we have
\begin{equation}
  \label{eq:cF_2_def}
  |U(E_N;Q)|>2^{-\ell/2}b^{-1/4}\sqrt N.
\end{equation}
With the definitions of~$\cF_1$ and~$\cF_2$ at hand, we may state two
auxiliary results that will complete the proof of
Theorem~\ref{thm:small_W}. 

\begin{claim}
  \label{claim:small_W.B}
  If~$E_N\in\cG\setminus(\cF_1\cup\cF_2)$, then
  \begin{equation}
    \label{eq:claim-small_W.B}
    W(E_N)\leq\delta\sqrt N.
  \end{equation}
\end{claim}

\begin{claim}
  \label{claim:small_W.C}
  We have
  \begin{equation}
    \label{eq:claim-small_W.C}
    \PP(\cG\setminus(\cF_1\cup\cF_2))\geq{1\over3}\eta(\delta).
  \end{equation}
\end{claim}

Clearly, Claims~\ref{claim:small_W.B} and~\ref{claim:small_W.C} imply
Claim~\ref{claim:small_W} and hence our proof is reduced to verifying those
two claims.
  
\begin{proof}[Proof of Claim~\ref{claim:small_W.B}]
  Fix~$E_N\in\cG\setminus(\cF_1\cup\cF_2)$ and fix an arithmetic
  progression~$Q\subset[1,N]\cap\ZZ$; say,
  \begin{equation}
    \label{eq:Q_def}
    Q=\{a+jb\:1\leq j\leq M\}.
  \end{equation}
  We wish to show that~$|U(E_N;Q)|\leq\delta\sqrt N$.  Let us
  decompose~$[a+b,a+Mb]\cap\ZZ$ into blocks~$B_{m,r}$ as in
  Fact~\ref{fact:W_fact}, that is, using at most two blocks~$B_{m,r}$ with the
  same~$r$ for any~$r$:  
  \begin{equation}
    \label{eq:interval_partition}
    [a+b,a+Mb]\cap\ZZ=\bigcup_\cB B_{m,r},
  \end{equation}
  where~$\cB$ in~\eqref{eq:interval_partition} simply denotes the family of
  blocks used in our special decomposition.  Put
  \begin{equation}
    \label{eq:cBS_def}
    \cBS=\{B_{m,r}\in\cB\:B_{m,r}\text{  is small}\}
  \end{equation}
  and
  \begin{equation}
    \label{eq:cBL_def}
    \cBL=\{B_{m,r}\in\cB\:B_{m,r}\text{  is large}\}.
  \end{equation}
  Intersecting the progression~$Q$ with the~$B_{m,r}\in\cB$, we obtain
  complete arithmetic progressions 
  \begin{equation}
    \label{eq:Q_m,r_def}
    Q_{m,r}=Q\cap B_{m,r}
  \end{equation}
  partitioning~$Q$, that is, such that~$Q=\bigcup Q_{m,r}$.  We have 
  \begin{equation}
    \label{eq:U=S1+S2}
    |U(E_N;Q)|\leq\Sigma_1+\Sigma_2,
  \end{equation}
  where
  \begin{equation}
    \label{eq:Sigma_1_def}
    \Sigma_1=\Big|\sum_{B_{m,r}\in\cBS}U(E_N;Q_{m,r})\Big|
  \end{equation}
  and
  \begin{equation}
    \label{eq:Sigma_2_def}
    \Sigma_2=\Big|\sum_{B_{m,r}\in\cBL}U(E_N;Q_{m,r})\Big|.
  \end{equation}
  We claim that
  \begin{equation}
    \label{eq:Sigma_i_small}
    \Sigma_i\leq{1\over2}\delta\sqrt N
  \end{equation}
  for both~$i=1$ and~$2$.  Let us verify~\eqref{eq:Sigma_i_small} for~$i=1$
  first.  Since~$E_N\notin\cF_1$, we know that~\eqref{eq:cF_1_def} fails for
  all small blocks~$B_{m,r}$; in particular, for all~$B_{m,r}\in\cBS$, we
  have
  \begin{equation}
    \label{eq:U(Q_m,r)_small}
    |U(E_N;Q_{m,r})|\leq C(\delta)(k-r)\sqrt{2^r}.
  \end{equation}
  Therefore, we have
  \begin{multline}
    \label{eq:Sigma_1_small}
    \Sigma_1\leq\sum_{B_{m,r}\in\cBS}C(\delta)(k-r)\sqrt{2^r}
    \leq2\sum_{0\leq r<r_0}C(\delta)(k-r)\sqrt{2^{r-k}}\sqrt{2^k}\\
    \leq2\sum_{\ell>\ell(\delta)}C(\delta)\ell2^{-\ell/2}\sqrt N
    \leq{1\over2}\delta\sqrt N,
  \end{multline}
  where in~\eqref{eq:Sigma_1_small} above we used the inequality
  in~\eqref{eq:ell(delta)_def} and the convention in~\eqref{eq:ell=k-r}.

  We now prove~\eqref{eq:Sigma_i_small} for~$i=2$.  We shall consider two
  cases.

  \begin{case}
    $b>b(\delta)$
  \end{case}
  \casebody
  Since~$E_N\notin\cF_2$, for any~$B_{m,r}\in\cBL$, we have, in this case,
  \begin{equation}
    \label{eq:U(Q_m,r)_b_large}
    |U(E_N;Q_{m,r})|\leq2^{-\ell/2}b^{-1/4}\sqrt N
  \end{equation}
  (see~\eqref{eq:cF_2_def}).  Therefore, recalling~\eqref{eq:b(delta)_def.2}
  and~\eqref{eq:ell=k-r}, we have
  \begin{multline}
    \label{eq:Sigma_2_small.1}
    \Sigma_2\leq\sum_{B_{m,r}\in\cBL}2^{-\ell/2}b^{-1/4}\sqrt N
    \leq2\sum_{r_0\leq r\leq k}2^{-\ell/2}b^{-1/4}\sqrt N\\
    =2\sum_{0\leq\ell\leq\ell(\delta)}2^{-\ell/2}b^{-1/4}\sqrt N
    \leq{8\over b^{1/4}}\sqrt N\leq{1\over2}\delta\sqrt N,
  \end{multline}
  and the proof of~\eqref{eq:Sigma_i_small} for~$i=2$ is complete in this
  case. 
  \endcasebody
  
  \begin{case}
    $b\leq b(\delta)$
  \end{case}
  \casebody Set~$Q_{\text{L}}=\bigcup Q_{m,r}$, with the union ranging over
  all pairs~$(m,r)$ with~$B_{m,r}\in\cBL$.  Since~$b\leq b(\delta)$, we have
  that~$b$ divides~$T=T(\delta)=b(\delta)!$.  It therefore follows that we
  have a partition
  \begin{equation}
    \label{eq:Q_L_def}
    Q_{\text{L}}=\bigcup_{(m,a)\in I}P(m,a)
  \end{equation}
  of~$Q_{\text{L}}$ into some~$P(m,a)$, where~$I$ is some index set.  Then
  \begin{equation}
    \label{eq:Sigma_2_small.2}
    \Sigma_2\leq\sum_{(m,a)\in I}|U(E_N;P(m,a))|,
  \end{equation}
  and, using that~$E_N\in\cG$ and recalling that there
  are~$2^{\ell(\delta)}T(\delta)$ progressions~$P(m,a)$ in total
  (see~\eqref{eq:[1,N]_partition_finer} and~\eqref{eq:m,a_range}), we have
  \begin{equation}
    \label{eq:Sigma_2_small.3}
    \Sigma_2
    \leq\sum_{(m,a)\in I}{\delta\over2^{\ell(\delta)+1}T(\delta)}\sqrt N
    \leq{1\over2}\delta\sqrt N,
  \end{equation}
  which verifies~\eqref{eq:Sigma_i_small} for~$i=2$ in this case.  
  \endcasebody

  Claim~\ref{claim:small_W.B} follows from~\eqref{eq:U=S1+S2}
  and~\eqref{eq:Sigma_i_small} for $i=1$ and~$2$. 
\end{proof}

\begin{proof}[Proof of Claim~\ref{claim:small_W.C}]
  We aim at bounding~$\PP(\cG\setminus(\cF_1\cup\cF_2))$ from below.  Let us
  first bound~$\PP(\cF_1)$ and~$\PP(\cF_2)$ from above.  We first
  consider~$\cF_1$.  Calculations similar to the ones leading to~(*) in the
  proof of Lemma~\ref{lem:W_lemma1} show that
  \begin{equation}
    \label{eq:PP(cF_1)_upbd}
    \PP(\cF_1)\leq40e^{-C(\delta)^2/4}\leq{1\over3}.
  \end{equation}
  Now consider~$\cF_2$.  Fix~$B_{m,r}$ and~$Q$ as in the definition
  of~$\cF_2$.  Using Fact~\ref{fact:large_dev}, we obtain that
  \begin{multline}
    \label{eq:PP(cF_2)_upbd}
    \PP(|U(E_N;Q)|>2^{-\ell/2}b^{-1/4}\sqrt N)
    <2\exp\(-2^{-\ell}b^{-1/2}N/2|Q|\)\\
    \leq2\exp\(-2^{-\ell}b^{-1/2}N/4(2^r/b)\)
    =2e^{-\sqrt b/4}.
  \end{multline}
  Summing the bound in~\eqref{eq:PP(cF_2)_upbd} over all choices of~$B_{m,r}$
  and~$Q$ and using~\eqref{eq:b(delta)_def}, we have
  \begin{multline}
    \label{eq:PP(cF_2)_upbd.1}
    \PP(\cF_2)\leq2\sum_{0\leq\ell\leq\ell(\delta)}2^\ell
    \sum_{b(\delta)<b\leq2^r}be^{-\sqrt b/4}
    \leq2^{\ell(\delta)+2}\sum_{b>b(\delta)}be^{-\sqrt b/4}\leq{1\over3}.
  \end{multline}
  Unfortunately, the bounds in~\eqref{eq:PP(cF_1)_upbd}
  and~\eqref{eq:PP(cF_2)_upbd.1} are not quite enough to complete the proof,
  as~$\cG$ is an event of rather small probability---indeed, those bounds do
  not even guarantee that~$\cG\setminus(\cF_1\cup\cF_2)\neq\emptyset$.  We
  thus refine our argument, and give upper estimates for the conditional
  probabilities~$\PP(\cF_1\mid\cG)$ and~$\PP(\cF_2\mid\cG)$.  To obtain those
  estimates, we make use of Corollary~\ref{cor:concentration}.
  
  Note that, to obtain the estimates~\eqref{eq:PP(cF_1)_upbd}
  and~\eqref{eq:PP(cF_2)_upbd.1}, we used the so called union bound:
  $\PP(A)\leq\sum_{\lambda\in\Lambda}\PP(A_\lambda)$
  if~$A\subset\bigcup_{\lambda\in\Lambda}A_\lambda$.  Of course, we may also
  consider this bound conditioning on~$\cG$:
  $\PP(A\mid\cG)\leq\sum_{\lambda\in\Lambda}\PP(A_\lambda\mid\cG)$.  If we
  repeat the arguments given above for~\eqref{eq:PP(cF_1)_upbd}
  and~\eqref{eq:PP(cF_2)_upbd.1}, but conditioning on~$\cG$, we have to bound
  probabilities of the form~$\PP(|U(E_N;Q)|>t\mid\cG)$ (for instance,
  see~\eqref{eq:PP(cF_2)_upbd} and~\eqref{eq:PP(cF_2)_upbd.1}).  However, a
  little meditation reveals that Corollary~\ref{cor:concentration} implies
  that, for any~$t$, we have\ykcomm{We could have a vote to decide whether
    this ``little meditation'' sentence is enough.}
  \begin{equation}
    \label{eq:conc_cor}
    \PP(|U(E_N;Q)|>t\mid\cG)\leq\PP(|U(E_N;Q)|>t).
  \end{equation}
  In particular, the inequalities used to obtain the bounds for~$\PP(\cF_1)$
  and~$\PP(\cF_2)$ above would equally hold for~$\PP(\cF_1\mid\cG)$
  and~$\PP(\cF_2\mid\cG)$.  Therefore, we have
  \begin{equation}
    \label{eq:conc_cF_1and2}
    \PP(\cF_1\mid\cG)\leq{1\over3}
    \quad\text{and}\quad
    \PP(\cF_2\mid\cG)\leq{1\over3},
  \end{equation}
  and hence
  \begin{equation}
    \label{eq:conc_cF_12}
    \PP(\cF_1\cup\cF_2\mid\cG)\leq{2\over3}.
  \end{equation}
  Thus
  \begin{equation}
    \label{eq:small_W.C_final_ineq}
    {\PP(\cG\setminus(\cF_1\cup\cF_2))\over\PP(\cG)}
    =\PP(\cG\setminus(\cF_1\cup\cF_2)\mid\cG)\geq{1\over3},
  \end{equation}
  whence, by~\eqref{eq:PP(cG)=eta},
  \begin{equation}
    \label{eq:small_W.C_finalfinal_ineq}
    \PP(\cG\setminus(\cF_1\cup\cF_2))
    \geq{1\over3}\PP(\cG)\geq{1\over3}\eta(\delta), 
  \end{equation}
  as required.
\end{proof}

As observed before, Claims~\ref{claim:small_W.B} and~\ref{claim:small_W.C}
imply Claim~\ref{claim:small_W}, and the proof of Theorem~\ref{thm:small_W} is
complete.

%   Let~$r=r(\delta)$ and~$m=m(\delta)$ be positive integer functions to be
%   specified later.
  
%   Let\ykcommb{Some ref?  Can we take~$m(\delta)!$, perhaps?}
%   \begin{equation}
%     \label{eq:M_def}
%     M=\lcm\{1,2,\dots,m(\delta)\}=\exp\{(1+o(1))m(\delta)\}.
%   \end{equation}
%   For every arithmetic progression with step~$M$ contained in a binary block
%   of length~$2^{k-r(\delta)}$, maximal under these restrictions, we shall
%   force the sum of the~$e_i$ with~$i$ running over such an arithmetic
%   progression to be of absolute value smaller than
%   \begin{equation}
%     \label{eq:sum_AP_upbd}
%     \delta\sqrt N\big/\(M2^{r(\delta)+1}\)={\delta\over M}2^{k/2-r(\delta)-1}.
%   \end{equation}

%   Consider now an arithmetic progression of step~$\wtm$ contained in a binary
%   block with~$2^{k-r}$ elements.  Consider the event~$\cA_2$ that the absolute
%   value of the sum of the~$e_i$ over this arithmetic progression should be at
%   most
%   \begin{equation}
%     \label{eq:sum_AP_upbd.2}
%     3\times2^{-r/4}\wtm^{-1/4}\sqrt N.
%   \end{equation}
%   We claim that~$\cA_2$ has probability~$<1/2$.  Indeed, this follows from the
%   lemma, since the conditional probability that each of these events fails is
%   at most the unconditional probability, which is at most
%   \begin{equation}
%     \label{eq:uncond_prob_upbd}
%     \exp\{-4\times2^{r/2}\wtm^{1/2}\}.
%   \end{equation}
%   Since the sum of~\eqref{eq:uncond_prob_upbd} over all natural~$r$ and
%   natural~$\wtm$ is less than~$1/2$, our claim follows.  
  
%   It follows from our claim that, with probability~$\geq\eta(\delta)/2$, we
%   have both events~$\cA_1$ and~$\cA_2$.
  
%   Suppose now that~$r(\delta)$ and~$m(\delta)$ are such that
%   \begin{equation}
%     \label{eq:r_m_cond_def}
%     \sum_{r>r(\delta)}3\times2^{-r/4}<{1\over8}\delta
%     \qquad\text{and}\qquad
%     m(\delta)^{-1/4}\sum_{r=0}^\infty3\times2^{-r/4}<{1\over8}\delta.
%   \end{equation}
%   Then~$W(E_N)<\delta\sqrt N$.  Therefore, it suffices to take
%   \begin{equation}
%     \label{eq:r_m_def}
%     r(\delta)=5\log_2{1\over\delta}
%     \qquad\text{and}\qquad
%     m(\delta)={1\over\delta^5}.
%   \end{equation}
%   \end{proof}


\subsection{The probability of having~$\cN(E_N)$ small}
\label{sec:small_normality}
Our\ykcomm{Section~\ref{sec:small_normality} is perhaps the roughest in this
  manuscript.}  aim in this section is to prove Theorem~\ref{thm:small_cN},
which gives a lower estimate for the probability that~$\cN(E_N)$ should be
small.  Our argument here will be based on the arguments used in the proof of
Theorem~\ref{thm:order_of_N}, 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~\ref{sec:cN_of_random}.  The following is a simple variant of
Lemma~\ref{lem:discrepancy_in_block}.

\begin{lemma}
  \label{lem:discrepancy_in_block_var}
  Let~$m$ and~$r$ be fixed non-negative integers with~$B_{m,r}\subset[1,N]$.
  For all~$D>0$, the probability that there is~$X\in\{-1,1\}^k$
  with~$k\leq\log_2N$ and~$k\leq r$ satisfying~\eqref{eq:block_bound} such
  that
  \begin{equation}
    \label{eq:large_discrepancy_in_block_var}
    \left|T(E_N,B_{m,r},X)-2^{r-k}\right|>D2^{-k/4}\sqrt{2^r}
  \end{equation}
  is at most
  \begin{equation}
    \label{eq:discrepancy_in_block_prob_var}
    O\(e^{-D^2/18}\)
    +2(\log_2N)^2N\exp\(-{3D\over4\log_2N}\;2^{r/4}\).
  \end{equation}
\end{lemma}

\begin{remark}
  \label{rem:_large_k_case}
  If~$k>r$, then~$2^{r-k}<1$, and hence, using the above estimate for~$k=r$,
  we get that the probability that 
  \begin{equation}
    \label{eq:large_discrepancy_in_block_var.2}
    \left|T(E_N,B_{m,r},X)-2^{r-k}\right|>D2^{r/4}+1
  \end{equation}
  for some~$X\in\{-1,1\}^k$ is at most as given
  in~\eqref{eq:discrepancy_in_block_prob_var}.
%   \begin{equation}
%     \label{eq:discrepancy_in_block_prob_var_rem}
%     O\(e^{-D^2/18}\)
%     +2(\log_2N)^2N\exp\(-{3D\over4\log_2N}\;2^{r/4}\).
%   \end{equation}
\end{remark}

Again, for simplicity, we shall assume that~$N=2^K$.\ykcomm{I suppose this
  power of~$2$ stuff is all right again.}  In this proof, a block~$B_{m,r}$ is
\textit{large} if
\begin{equation}
  \label{eq:r_large_def_var}
  r\geq8\log_2\log_2N
\end{equation}
and is \textit{small} otherwise.  As in the proof of
Theorem~\ref{thm:order_of_N}, we may and shall assume that
\begin{itemize}
\item[(***)]\sl for all integers~$m$, $r$, and~$k\leq\log_2N$
  with~$B_{m,r}\subset[1,N]$ and~$r\geq8\log_2\log_2N$
  satisfying~\eqref{eq:block_bound} and every~$X\in\{-1,1\}^k$, we have the
  following: if~$k\leq r$, then
  $$
  \left|T(E_N,B_{m,r},X)-2^{r-k}\right|\leq C2^{-k/4}(K-r)\sqrt{2^r},
  $$
  and if~$k>r$, then 
  $$
  |T(E_N,B_{m,r},X)-2^{r-k}|\leq C(K-r)2^{r/4}+1.
  $$
\end{itemize}
To see that~(***) does hold with probability approaching~$1$ as~$C\to\infty$,
we follow the argument given in the proof of Theorem~\ref{thm:order_of_N}
(see~\eqref{eq:prob_large_blocks}), but using
Lemma~\ref{lem:discrepancy_in_block_var} and Remark~\ref{rem:_large_k_case}
instead of
%
%\ykcommb{what should be the definition of a large block in here?  Same or
%  $r\geq8\log_2\log_2N$?  Is this relevant?}
%
Lemma~\ref{lem:discrepancy_in_block}.  In the proof of
Theorem~\ref{thm:order_of_N}, the relevant probability was shown to
be~$O\(e^{-2C^2/9}\)$; repeating the same calculations with the bounds in
Lemma~\ref{lem:discrepancy_in_block_var} and Remark~\ref{rem:_large_k_case},
one obtains~$O\(e^{-C^2/18}\)$.
% In these calculations that we omit, we replace~\eqref{eq:r_large_def} by
% \begin{equation}
%   \label{eq:r_large_def_var}
%   r\geq8\log_2\log_2N.
% \end{equation}

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~\eqref{eq:MS_dagger} show that, for any~$\ell\geq1$, the contribution of
blocks of cardinality~$\leq2^{K-\ell}$ to the
discrepancy~$|T(E_N,M,X)-M2^{-k}|$ is
\begin{equation}
  \label{eq:_dev_var}
  O\(C2^{K/2}\ell2^{-\ell/2}\)+O\((\log_2\log_2N)(\log_2N)^8\).
\end{equation}
This observation shows that 
\begin{itemize}
\item[(\ddag)]\sl the contribution of the blocks~$B_{m,r}$ with~$r\leq
  K-\ell_0$ to the estimate in~\eqref{eq:MS_dagger} is, say,
  $\leq(\delta/2)\sqrt N$ if~$\ell_0=\ell_0(\delta)$ is some large enough
  constant that depends only on~$\delta$.
\end{itemize}

Having cleared some of the pre-requisites, we start the proof of
Theorem~\ref{thm:small_cN}.

\begin{proof}[Proof of Theorem~\ref{thm:small_cN}]
  Let~$\delta>0$ be given.  We let~$k_0=k_0(\delta)$ be a suitably large
  integer constant that depends only on~$\delta$, for the inequalities below
  to hold.  We wish to show that~\eqref{eq:small_cN} holds for some suitably
  small positive constant~$c(\delta)$.
  
  Fix~$k\leq\log_2N$ and~$M$ with~$1\leq M\leq N-k+1$.  As before,
  write~$[1,M]$ as a disjoint union of blocks~$B_{m,r}$ ($r\leq\log_2M\leq 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_+\cup I_-$ be the partition
  of~$I$ with
  \begin{equation}
    \label{eq:I_+_def_var}
    I_+=\{(m,r)\in I\:r\text{ satisfies~\eqref{eq:r_large_def_var}}\}.
  \end{equation}
  For later reference, observe that
  \begin{equation}
    \label{eq:I_-_size_var}
    |I_-|<8\log_2\log_2N.
  \end{equation}
  Observe also that if~$(m,r)\in I_-$, then
  \begin{equation}
    \label{eq:small_r_small_dicr_var}
    \left|T(E_N,B_{m,r},X)-2^{r-k}\right|\leq2^r<(\log_2N)^8
  \end{equation}
  for any~$X\in\{-1,1\}^k$.
  
  Let us now fix~$X\in\{-1,1\}^k$.  We wish to
  estimate~$|T(E_N,M,X)-M2^{-k}|$.  As in~\eqref{eq:MS_dagger}, we start with
  \begin{multline}
    \label{eq:thm6_discr_estimate.1}
    \left|T(E_N,M,X)-M2^{-k}\right|
    \leq\sum_{(m,r)\in I}\left|T(E_N,B_{m,r},X)-2^{r-k}\right|\\
    =\sum_{(m,r)\in I_+}\left|T(E_N,B_{m,r},X)-2^{r-k}\right|
    +\!\!\sum_{(m,r)\in I_-}\left|T(E_N,B_{m,r},X)-2^{r-k}\right|.
  \end{multline}
  Because of~\eqref{eq:I_-_size_var} and~\eqref{eq:small_r_small_dicr_var},
  the last sum in~\eqref{eq:thm6_discr_estimate.1} is~$o(\sqrt N)$, and hence
  we may ignore it.  We thus focus on the sum over the pairs~$(m,r)\in I_+$,
  that is, we consider the contribution of the large blocks~$B_{m,r}$ (i.e.,
  blocks with~$r\geq8\log_2\log_2N$).

  \begin{case.2}
    \label{case:large_k}
    $k\geq k_0=k_0(\delta)$
  \end{case.2}
  \casebody We shall be able to dispose of this case by invoking some
  observations that we have already discussed.  Let us start by observing that
  \begin{multline}
    \label{eq:thm6_discr_estimate.large_k}
    \sum_{(m,r)\in I_+}\left|T(E_N,B_{m,r},X)-2^{r-k}\right|\\
    =\sum\nolimits_1
    \left|T(E_N,B_{m,r},X)-2^{r-k}\right|\\
    +\sum\nolimits_2\left|T(E_N,B_{m,r},X)-2^{r-k}\right|, 
  \end{multline}
  where~$\sum_1$ indicates sum over all pairs~$(m,r)\in I_+$ with~$r<k$
  and~$\sum_2$ indicates sum over all pairs~$(m,r)\in I_+$ with~$r\geq k$.
  Making use of~(***), one may check that calculations very similar to the
  ones in~\eqref{eq:MS_dagger} show that the last but one sum
  in~\eqref{eq:thm6_discr_estimate.large_k} is~$O(C2^{K/4})=o(\sqrt N)$ and
  the last sum is~$\leq(\delta/2)\sqrt N$, as long as~$k_0=k_0(\delta)$ is
  large enough.  The proof is therefore complete in this case.
  %
  \endcasebody

  \begin{case.2}
    \label{case:small_k}
    $k<k_0=k_0(\delta)$
  \end{case.2}
  \casebody This case will require considerable more work.  Let
  \begin{equation}
    \label{eq:r_0_def}
    r_0=K-k_0
  \end{equation}
  and observe that
  \begin{multline}
    \label{eq:thm6_discr_estimate.small_k}
    \sum_{(m,r)\in I_+}\left|T(E_N,B_{m,r},X)-2^{r-k}\right|\\
    =\sum\nolimits_1
    \left|T(E_N,B_{m,r},X)-2^{r-k}\right|\\
    +\sum\nolimits_2\left|T(E_N,B_{m,r},X)-2^{r-k}\right|, 
  \end{multline}
  where~$\sum_1$ indicates sum over all pairs~$(m,r)\in I_+$ with~$r<r_0$
  and~$\sum_2$ indicates sum over all pairs~$(m,r)\in I_+$ with~$r\geq r_0$.
  
  The estimate of the first sum on the right-hand side
  of~\eqref{eq:thm6_discr_estimate.small_k} is based on~(\ddag): since in that
  sum we are considering blocks~$B_{m,r}$ with~$r<r_0$, according to~(\ddag),
  that sum is~$\leq(\delta/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~\eqref{eq:thm6_discr_estimate.small_k}.  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$.

  \begin{claim}
    \label{claim:main_contrib}
    There is a constant~$c'(\delta)>0$ for which the following holds.
    Let~$\cE$ be the event that, for all~$m$ with~$B_{m,r_0}\subset[1,N]$
    and~$\max B_{m,r_0}=(m+1)2^{r_0}\leq N-k_0+1$ and
    every~$X\in\{-1,1\}^{k_0}$, we have
    \begin{equation}
      \label{eq:main_contrib}
      \left|T(E_N,B_{m,r_0},X)-2^{r_0-k_0}\right|=O\(\delta2^{-5k_0/2}\sqrt N\).
    \end{equation}
    Then~$\PP(\cE)\geq c'(\delta)$.
  \end{claim}
  
  We leave the proof of Claim~\ref{claim:main_contrib} for later and complete
  the proof of Theorem~\ref{thm:small_cN}.  Suppose~$E_N$ is such
  that~\eqref{eq:main_contrib} does hold for all~$B_{m,r_0}$ and all~$X$ of
  length~$k_0$ as specified in the definition of the event~$\cE$.  Observe
  that, then, for all~$Y\in\{-1,1\}^k$ with~$k\leq k_0$, we have
  \begin{equation}
    \label{eq:main_contrib.smaller_k}
    \left|T(E_N,B_{m,r_0},Y)-2^{r_0-k}\right|=O\(\delta2^{-3k_0/2}\sqrt N\).
  \end{equation}
  Indeed, given a sequence~$Y$ of length~$k\leq k_0$, it suffices to consider
  all~$2^{k_0-k}\leq2^{k_0}$ extensions of~$Y$ to sequences~$X$ of
  length~$k_0$, with~$Y$ a prefix of~$X$, and then
  apply~\eqref{eq:main_contrib}.  We therefore assume
  that~\eqref{eq:main_contrib.smaller_k} does hold for all~$Y$ of
  length~$k\leq k_0$.
  
  Recall that we have to estimate the last sum
  in~\eqref{eq:thm6_discr_estimate.small_k}, where~$X$ is a fixed sequence of
  length~$k<k_0$.  Note that that sum is at most
  \begin{equation}
    \label{eq:last_sum_estimate}
    \sum_{m\in J}\left|T(E_N,B_{m,r_0},X)-2^{r_0-k}\right|, 
  \end{equation}
  where the sum ranges over some set~$J\subset[0,2^{k_0})$.  Clearly,
  from~\eqref{eq:main_contrib.smaller_k} applied to~$Y=X$, we see that the sum
  in~\eqref{eq:last_sum_estimate} is~$O(\delta2^{-k_0/2}\sqrt
  N)\leq(\delta/3)\sqrt N$, as long as~$k_0=k_0(\delta)$ is large enough, and
  this completes the proof of this case.
  %
  \endcasebody

  To complete the proof of Theorem~\ref{thm:small_cN}, we need to prove
  Claim~\ref{claim:main_contrib}.
\end{proof}

\begin{proof}[Proof of Claim~\ref{claim:main_contrib}]
  We shall be somewhat brief in parts of this proof.  Let~$\delta>0$ be given.
  We may suppose that~$\delta$ is sufficiently small.  In this proof, for
  simplicity, we write~$k$ for~$k_0=k_0(\delta)$, 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
  \begin{equation}
    \label{eq:2^k_norm_vector}
    \bfs(E_M)
    =\({T(E_M,M,X)-M2^{-k}\over\sqrt M}\)_{X\in\{-1,1\}^k}\in\RR^{2^k},
  \end{equation}
  with~$E_M$ chosen from~$\{-1,1\}^M$ uniformly at random.  (We remark that it
  would be more natural to have\ykcomm{Is this remark a little odd?  Should we
  just not say anything?}
  \begin{equation}
    \label{eq:2^k_norm_vector.precise}
    {T(E_M,M-k+1,X)-(M-k+1)2^{-k}\over\sqrt{M-k+1}}
  \end{equation}
  as the entries of~$\bfs(E_M)$, but, for simplicity, we shall use the
  definition given in~\eqref{eq:2^k_norm_vector}, and we shall ignore the
  additive error term, of order~$O(k/\sqrt M)$, introduced by using~$M$
  instead of~$M-k+1$ in~\eqref{eq:2^k_norm_vector}.)

  Let us say that~$E_M\in\{-1,1\}^M$ is \textit{good} if
  \begin{equation}
    \label{eq:good_def}
    |T(E_M,B_{m,r},X)-2^{r-\ell}|
    \leq k(K-7k-r)2^{-\ell/4}\sqrt{2^r}
  \end{equation}
  for all~$m$ and~$r$ with~$B_{m,r}\subset[M-\ell+1]$ and~$r\geq8\log\log M$
  and all~$X\in\{-1,1\}^\ell$ with~$\ell\leq r$ and~$\ell\leq\log_2M$.
  Let~$\cG\subset\{-1,1\}^M$ be the set of good sequences, and let us
  write~$\cG\comp$ for the complement of~$\cG$.  We now state the following
  claim.

  \begin{claim}
    \label{claim:Gc_small}
    We have
    \begin{equation}
      \label{eq:Gc_small_upbd}
      \PP(\cG\comp)=O(e^{-k^2/18}).
    \end{equation}
  \end{claim}
  
  Claim~\ref{claim:Gc_small} above follows from calculations similar to the
  ones that let us assume~(***) (see also the proof of
  Theorem~\ref{thm:order_of_N}).  
  
  In what follows, we wish to ignore the sequences~$E_M$ in~$\cG\comp$.  The
  next claim tells us that the sequences in~$\cG\comp$ do not influence the
  expectation of~$\bfs(E_M)$ too much.

  \begin{claim}
    \label{claim:expectation_cG}
    For any~$X\in\{-1,1\}^k$, 
    \begin{equation}
      \label{eq:expectation_cG}
      \EE(|T(E_M,M,X)-M2^{-k}|\chi_{\cG\comp})=O(\sqrt Me^{-k^2/18}), 
    \end{equation}
    where~$\chi_{\cG\comp}$ is the characteristic function of~$\cG\comp$. 
  \end{claim}
  \begin{proof}
    Fix~$X\in\{-1,1\}^k$ and let~$Y=Y(E_M)=|T(E_M,M,X)-M2^{-k}|$.  Note first
    that Fact~\ref{fact:Chernoff} tells us that
    \begin{equation}
      \label{eq:prob_Y_large}
      \PP(Y\geq M2^{-k})\leq2e^{-M/2^{k+2}}.
    \end{equation}
    Since we always have~$Y\leq M$, we conclude from~\eqref{eq:prob_Y_large}
    that, setting~$A=\{E_M\:Y(E_M)\geq M/2^k\}$. we have
    \begin{equation}
      \label{eq:Y_tail}
      \EE(Y\chi_A)=O(Me^{-M/2^{k+2}})=O(\sqrt Me^{-k^2/18}).
    \end{equation}
    We shall make use of~\eqref{eq:Y_tail} in a short while.  Let~$V(E_M)$ be
    given by
    \begin{equation}
      \label{eq:rvV_def}
      V(E_M)=
      \begin{cases}
        Y(E_M) &\text{if }Y>k\sqrt{M/2^k}\\
        0      &\text{otherwise}.
      \end{cases}
    \end{equation}
    Then we have
    \begin{equation}
      \label{eq:Y_decomp}
      Y\chi_{\cG\comp}\leq k\sqrt{M\over 2^k}\chi_{\cG\comp}+V,
    \end{equation}
    whence, recalling~\eqref{eq:Gc_small_upbd}, we deduce that
    \begin{equation}
      \label{eq:EEY_decomp}
      \EE(Y\chi_{\cG\comp})
      \leq k\sqrt{M\over 2^k}\PP(\chi_{\cG\comp})+\EE(V)
      =k\sqrt{M\over 2^k}O(e^{-k^2/18})+\EE(V).
    \end{equation}
    Now let~$R=k^{-1}\sqrt{M/2^k}$.  Using~\eqref{eq:Y_tail}, we see that 
    \begin{equation}
      \label{eq:EEV_upbd}
      \EE(V)\leq O(\sqrt Me^{-k^2/18})
      +\sum_{1\leq r\leq R}\PP\(Y\geq
      rk\sqrt{M\over2^k}\)(r+1)k\sqrt{M\over2^k}. 
    \end{equation}
    From Fact~\ref{fact:Chernoff}, we obtain
    \begin{equation}
      \label{eq:step_Y_large}
      \PP\(Y\geq rk\sqrt{M\over2^k}\)\leq2e^{-r^2k^2/4}.
    \end{equation}
    Putting together~\eqref{eq:EEV_upbd} and~\eqref{eq:step_Y_large}, we get 
    \begin{align}
      \EE(V)&\leq O(\sqrt Me^{-k^2/18})
      +2k\sqrt{M\over2^k}\sum_{1\leq r\leq R}(r+1)e^{-r^2k^2/4}\nonumber\\
      &=O(\sqrt Me^{-k^2/18})+O\(k\sqrt{M\over2^k}e^{-k^2/4}\)
      \label{eq:EEV_upbd.2}\\
%      &=o(\sqrt Me^{-k^2/18})+O\(\sqrt Me^{-k^2/4}\)\nonumber\\
      &=O(\sqrt Me^{-k^2/18}),\nonumber
    \end{align}
    as required.    
  \end{proof}
  
  Note that the vector~$\bfs(E_M)$ has entries with expectation~$0$.  Combined
  with Claim~\ref{claim:expectation_cG}, this implies that, for
  any~$X\in\{-1,1\}^k$, the expected value of
  \begin{equation}
    \label{eq:disc(E_M)_in_box.0}
    T(E_M,M,X)-M2^{-k}\over\sqrt M
  \end{equation}
  conditioned on~$E_M\in\cG$ is~$O(e^{-k^2/18})=o_{\delta\to0}(\delta/64^k)$.
  In this proof, we write~$o_{\delta\to0}(x)$ for any term~$y$ such
  that~$y/x\to0$ as~$\delta\to0$.

  For~$E_M\in\cG$, we have
  \begin{multline}
    \label{eq:disc(E_M)_in_box}
    \quad\bfs(E_M)=\(T(E_M,M,X)-M2^{-k}\over\sqrt M\)_{X\in\{-1,1\}^k}\\
    \in[-k2^{-k/4},k2^{-k/4})^{2^k}\subset[-1,1)^{2^k}.\quad
  \end{multline}
  Let us partition~$[-1,1)^{2^k}$ in~$b=(2\times64^k/\delta)^{2^k}$ blocks of
  side length~$\delta/64^k$ (that is, blocks of the form~$\prod_{1\leq
    j\leq2^k}[x_j,x_j+\delta/64^k)$; we may assume without loss of generality
  that~$64^k/\delta$ is an integer).  Let these blocks be~$C_i$ ($1\leq i\leq
  b$).  For each~$i$, let~$P_i\in C_i$ be the average of the
  points~$\bfs(E_M)$ that belong to~$C_i$ and are such that~$E_M\in\cG$;
  if~$\bfs^{-1}(C_i)\cap\cG=\emptyset$, let~$P_i$ be the centre of~$C_i$.  If
  \begin{equation}
    \label{eq:q_i_def}
    q_i=\PP(P\in C_i\cond P\in\cG),
  \end{equation}
  then~$\bfE=\sum_iq_iP_i$ is the expectation of~$\bfs(E_M)$ conditional
  on~$E_M\in\cG$.  Recall that all entries of~$\bfE$
  are~$o_{\delta\to0}(\delta/64^k)$.

  Let
  \begin{equation}
    \label{eq:J_def}
    J=\left\{1\leq j\leq b
      \:q_j\geq{\delta\over k64^k}\(\delta\over64^k\)^{2^k}\right\}.
  \end{equation}
  Then
  \begin{equation}
    \label{eq:bfE_large_q_i}
    \sum_{j\notin J}q_jP_j
  \end{equation}
  has all entries that are~$O(\delta/k64^k)=o_{\delta\to0}(\delta/64^k)$.  Let
  \begin{equation}
    \label{eq:tE_def}
    \tbfE=\sum_{j\in J}\wtq_jP_j,
  \end{equation}
  where~$\wtq_j=q_j/\sum_{i\in J}q_i$.  Then all the entries of~$\tbfE$
  are~$o_{\delta\to0}(\delta/64^k)$, because all the entries of~$\bfE$
  are~$o_{\delta\to0}(\delta/64^k)$ and
  \begin{equation}
    \label{eq:E&tE}
    \bfE=\Big(\sum_{i\in J}q_i\Big)\tbfE+\sum_{j\notin J}q_jP_j.
  \end{equation}
  Clearly, $\tbfE$~may be written as a convex combination of
  the~$P_j\in\RR^{2^k}$ ($j\in J$).  Therefore, there are points~$Q_j=P_{i_j}$
  ($0\leq j\leq2^k$ and~$i_j\in J$ for all~$j$) and real numbers~$t_j\geq0$
  with~$\sum_{j=0}^{2^k}t_j=1$ such that~$\tbfE=\sum_{j=0}^{2^k}t_jP_{i_j}$.
  
  We next approximate the~$t_j$ by rationals~$m_j/64^k$ in such a way that
  \begin{equation}
    \label{eq:m_j_def}
    \left|{m_j\over64^k}-t_j\right|\leq{1\over64^k}
    \qquad\text{and}\qquad
    \sum_{j=0}^{2^k}m_j=64^k.
  \end{equation}
  (We can take~$m_j=\lfloor64^kt_j\rfloor$
  if~$\sum_{i<j}m_i\geq64^k\sum_{i<j}t_i$) and~$m_j=\lceil64^kt_j\rceil$
  otherwise.)
  
  We now partition~$[N]$ into the~$2^k$ blocks~$B_{m,r_0}=B_{m,K-k}$ ($0\leq
  m<2^k$) and partition each of these blocks into~$64^k$ segments of
  length~$M=2^{K-7k}$.  We consider~$E_N\in\{-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~$\cG$).
  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~$\bfs(E_M)\in C_{i_0}$, in the next~$m_1$ segments we
  have~$\bfs(E_M)\in C_{i_1}$, etc.  The probability that all these
  requirements are met is at least
  \begin{equation}
    \label{eq:reqs_prob_lwbd}
    c(\delta)=\({1\over2k}\(\delta\over64^k\)^{2^k+1}\)^{64^k\times2^k}.  
  \end{equation}
  In each of the~$2^k$ blocks~$B_{m,r_0}=B_{m,K-k}$, we have
  \begin{align}
    \label{eq:global_dev}
    &T(E_N,B_{m,r_0},X)-|B_{m,r_0}|2^{-k}
    =\sum_{i=0}^{2^k}m_i\(T(E_M^{(i)},M,X^{(i)})-M2^{-k}\)\nonumber\\
    &\qquad=\sum_{j=0}^{2^k}m_j\(Q_j+O\(\delta\over64^k\)\)\sqrt M\nonumber\\
    &\qquad=O\({\delta\over64^k}\sum_{j=0}^{2^k}m_j\sqrt M\)
    +\sum_{j=0}^{2^k}m_jQ_j\sqrt M\nonumber\\
    &\qquad=O\(\delta\sqrt M\)+\sum_{j=0}^{2^k}m_jQ_j\sqrt M\nonumber\\
    &\qquad=O\(\delta\sqrt M\)+\sum_{j=0}^{2^k}\(64^kt_j+O(1)\)Q_j\sqrt
    M\\ 
    &\qquad=O\(\delta\sqrt M\)+O(2^k\sqrt M)+\sum_{j=0}^{2^k}64^kt_jQ_j\sqrt
    M\nonumber\\ 
    &\qquad=O\(2^k\sqrt M\)+O\(64^k{\delta\over64^k}\sqrt M\)\nonumber\\
    &\qquad=O\(2^k\sqrt M\)=O\(2^k2^{-7k/2}\sqrt N\)=O\(2^{-5k/2}\sqrt
    N\),\nonumber 
  \end{align}
  as required.
\end{proof}

\begin{remark}
  \label{rem:c(delta)_from_above}
  We may prove upper bounds for~$c(\delta)$ in Theorems~\ref{thm:small_W}
  and~\ref{thm:small_cN} 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~$\geq1/2$, whence it follows
  that the probability that this event occurs in none of these intervals
  is~$\leq1/2^k$.  Taking~$\delta=1/2\sqrt k$, we
  obtain~$c(\delta)\leq(1/2)^{1/4\delta^2}$.
\end{remark}

\section{Concluding remarks}
\label{sec:concluding}
The upper bounds in Theorems~\ref{thm:order_of_W} and~\ref{thm:order_of_N} are
best possible in the following sense.  Let us consider~$W(E_N)$.  We claim
that, for any~$C>0$, there is~$\epsilon_0>0$ such that
\begin{equation}
  \label{eq:W_best_possibleR}
%  \text{for any~$C$, there is~$e_0>0$ such that }
  \PP\Big(W(E_N)<C\sqrt N\Big)\leq1-\epsilon_0
%  \text{ for all large enough~$N$.}
\end{equation}
for all large enough~$N$.  Therefore, the fact that the constant~$1/\delta$ in
the upper bound in Theorem~\ref{thm:order_of_W} depends on~$\epsilon$ cannot
be avoided.

Inequality~\eqref{eq:W_best_possibleR} follows simply from
Fact~\ref{fact:1/2Bin}.  Indeed, that result tells us that, for any
fixed~$C>0$, we have
\begin{equation}
  \label{eq:best_possible_WR}
  \lim_{N\to\infty}\PP\(\bigg|\sum_{1\leq j\leq N}e_j\bigg|\geq C\sqrt N\) 
  =2\sqrt{2\over\pi}\int_{C/2}^\infty e^{-2x^2}\rmd x>0,
\end{equation}
and this clearly gives~\eqref{eq:W_best_possibleR} for any~$C$ for a suitably
small but positive~$\epsilon_0$.

One may prove similar facts concerning the upper bound in
Theorem~\ref{thm:order_of_N} 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
\begin{equation}
  \label{eq:thm_on_cN_best_possibleR}
  \lim_{N\to\infty}\PP\(
  \left|T(E_N,N,(1))-{N\over2}\right|\geq C\sqrt N\)
  =2\sqrt{2\over\pi}\int_C^\infty e^{-2x^2}\rmd x>0
\end{equation}
(we omit the details).

\begin{problem}
  \label{prob:limits}
  Investigate the existence of the limiting distributions of
\begin{equation*}
%  \label{eq:limits1}
  \left\{{W(E_N)\over\sqrt N}\right\}_{N\geq1}
  \text{ and }\hskip15pt
%  \qquad
  \left\{{\cN(E_N)\over\sqrt N}\right\}_{N\geq1}
\end{equation*}
and
\begin{equation*}
%  \label{eq:limits2}
  \left\{{C_k(E_N)\over\sqrt{N\log{N\choose k}}}\right\}_{N\geq1}.
\end{equation*}
Investigate these distributions.
\end{problem}

It is most likely that all three sequences in Problem~\ref{prob:limits} have
limiting distributions.  Note that Theorem~\ref{thm:C_k_concentrated} tell us
that $\{C_k(E_N)/\EE(C_k)\}_{N\geq1}$
%\begin{equation*}
%  \label{eq:limits2}
%  \left\{{C_k(E_N)\over\Gamma(k,N)}\right\}_{N\geq1}  
%\end{equation*}
has a limiting distribution that is concentrated at a point, as long as
\begin{equation}
  \label{eq:k_upbd_concluding}
  k=k(N)\leq\log N-\log\log N
\end{equation}
(the condition in~\eqref{eq:k_upbd_concluding} may probably be weakened). 

%========================= references ========================================
%\bibliographystyle{amsplain}
%\bibliography{refs}
\providecommand{\bysame}{\leavevmode\hbox to3em{\hrulefill}\thinspace}
\providecommand{\MR}{\relax\ifhmode\unskip\space\fi MR }
% \MRhref is called by the amsart/book/proc definition of \MR.
\providecommand{\MRhref}[2]{%
  \href{http://www.ams.org/mathscinet-getitem?mr=#1}{#2}
}
\providecommand{\href}[2]{#2}
\begin{thebibliography}{10}

\bibitem{alon04:_measur_minimal}
N.~Alon, Y.~Kohayakawa, C.~Mauduit, C.~G. Moreira, and V.~R{\"o}dl,
  \emph{Measures of pseudorandomness for finite sequences: minimal values},
  Combin. Probab. Comput. \textbf{15} (2006), no.~1--2, 1--29.

\bibitem{alon00:_prob_method}
N.~Alon and J.~H. Spencer, \emph{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 {P}aul {E}rd{\H o}s. \MR{2003f:60003}

\bibitem{BBf}
B. Bollob{\'a}s, \emph{Random graphs}, Academic Press Inc. [Harcourt
  Brace Jovanovich Publishers], London, 1985. \MR{87f:05152}

\bibitem{cassaigne02}
J.~Cassaigne, C.~Mauduit, and A. S{\'a}rk{\"o}zy, \emph{On
  finite pseudorandom binary sequences. {VII}. {T}he measures of
  pseudorandomness}, Acta Arith. \textbf{103} (2002), no.~2, 97--118.
  \MR{2004c:11139}

\bibitem{chung52:_borel_cantel}
K.~L. Chung and P.~Erd{\H o}s, \emph{On the application of the
  {B}orel-{C}antelli lemma}, Trans. Amer. Math. Soc. \textbf{72} (1952),
  179--186. \MR{13:567b}

\bibitem{erdos59}
P.~Erd{\H{o}}s and A.~R{\'e}nyi, \emph{On {C}antor's series with convergent
  {$\sum 1/q\sb{n}$}}, Ann. Univ. Sci. Budapest. E\"otv\"os. Sect. Math.
  \textbf{2} (1959), 93--109. \MR{23:A3710}

\bibitem{erdos74:_probab}
P. Erd{\H{o}}s and J. Spencer, \emph{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}

\bibitem{janson00:_random_graph}
S. Janson, T. {\L}uczak, and A. Ruci{\'n}ski, \emph{Random
  graphs}, Wiley-Interscience, New York, 2000. \MR{2001k:05180}

\bibitem{matousek96:_discr}
J. Matou{\v{s}}ek and J. Spencer, \emph{Discrepancy in
  arithmetic progressions}, J. Amer. Math. Soc. \textbf{9} (1996), no.~1,
  195--204. \MR{96c:11089}

\bibitem{mauduit02:_finit}
C. Mauduit, \emph{Finite and infinite pseudorandom binary words},
  Theoret. Comput. Sci. \textbf{273} (2002), no.~1-2, 249--261, WORDS (Rouen,
  1999). \MR{2002m:11072}

\bibitem{mauduit97}
C. Mauduit and A. S{\'a}rk{\"o}zy, \emph{On finite pseudorandom
  binary sequences. {I}. {M}easure of pseudorandomness, the {L}egendre symbol},
  Acta Arith. \textbf{82} (1997), no.~4, 365--377. \MR{99g:11095}

\bibitem{mcdiarmid89}
C. McDiarmid, \emph{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}

\bibitem{petrov02:_borel_cantel}
V.~V. Petrov, \emph{A note on the {B}orel-{C}antelli lemma}, Statist.
  Probab. Lett. \textbf{58} (2002), no.~3, 283--286. \MR{MR1921874
  (2003e:60005)}

\bibitem{petrov04:_borel_cantel}
\bysame, \emph{A generalization of the {B}orel-{C}antelli lemma}, Statist.
  Probab. Lett. \textbf{67} (2004), no.~3, 233--239. \MR{MR2053525
  (2005a:60011)}

\bibitem{roth64:_remar}
K.~F. Roth, \emph{Remark concerning integer sequences}, Acta Arith. \textbf{9}
  (1964), 257--260. \MR{29 \#5806}

\end{thebibliography}

%=============================================================================
\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
