%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% AMSLaTeX file for the paper                                        %
%   Measures of pseudorandomness for finite sequences: minimal values%
%   by N.~Alon, Y.~Kohayakawa, C.~Mauduit, C.~G.~Moreira and V.~Rodl %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: <Wednesday 29 Jun 2005 06:46:38pm BRT yoshi@erdos.ime.usp.br>
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[11pt,reqno]{amsart}

%\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\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}

\makeatletter
\def\swdots{\mathinner{%
    \mkern2mu\raise\p@\hbox{.}
    \mkern2mu\raise4\p@\hbox{.}
    \mkern1mu\raise7\p@\vbox{\kern7\p@\hbox{.}}
    \mkern1mu}}
\makeatother
%========================= 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{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\delmid{\delimiter"326A }
\let\divides=\vert
\def\edivides{\divides\mskip-4mu\divides}
\def\ndivides{\mathpalette\notdiv\relax}
\def\notdiv#1#2{\setbox0=\hbox{$#1\divides$}%
 \vcenter{\hbox to\wd0{$\hss\scriptscriptstyle/\hss$}}\kern-\wd0
 \vcenter{\hbox to\wd0{$\hss\kern.5pt\scriptscriptstyle/\hss$}}\kern-\wd0
 \box0\relax}
\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\cB{{\mathcal B}}
\def\cD{{\mathcal D}}
\def\cG{{\mathcal G}}
\def\cL{{\mathcal L}}
\def\cM{{\mathcal M}}
\def\cN{{\mathcal N}}
\def\cP{{\mathcal P}}
\def\cS{{\mathcal S}}
\def\cW{{\mathcal W}}
\def\PP{{\mathbb P}}
\def\EE{{\mathbb E}}
\def\FF{{\mathbb F}}
\def\NN{{\mathbb N}}
\def\RR{{\mathbb R}}
\def\CC{{\mathbb C}}
\def\ZZ{{\mathbb Z}}
\def\e{{\rm e}}
\def\bfA{{\mathbf A}}
\def\bfB{{\mathbf B}}
\def\bfE{{\mathbf E}}
\def\bfH{{\mathbf H}}
\def\bfI{{\mathbf I}}
\def\bfJ{{\mathbf J}}
\def\bfe{{\mathbf e}}
\def\bff{{\mathbf f}}
\def\bfg{{\mathbf g}}
\def\bfi{{\mathbf i}}
\def\bfu{{\mathbf u}}
\def\bfv{{\mathbf v}}
\def\bfw{{\mathbf w}}
\def\bfx{{\mathbf x}}
\def\bfdelta{{\mathbf\delta}}
\def\bfzero{{\mathbf0}}
\def\bfone{{\mathbf1}}
\def\tC{{\widetilde C}}
\def\tE{{\widetilde E}}
\def\inU{\mathrel{\in_U^{}}}
%\def\inU{\mathrel{\in_U}}
\def\disc{\mathop{\text{\rm disc}}\nolimits}
\def\card{\mathop{\text{\rm card}}\nolimits}
\def\rk{\mathop{\text{\rm rk}}\nolimits}
\def\tr{\mathop{\text{\rm tr}}\nolimits}
\def\Ave{\mathop{\text{\rm Ave}}\nolimits}
\def\Bi{\mathop{\text{\rm Bi}}\nolimits}
\def\GF{\mathop{\text{\rm GF}}\nolimits}
\def\sdiff{\bigtriangleup}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\let\epsilon=\varepsilon
\let\tilde=\widetilde
%========================= paper specific macros =============================

\begin{document}
\title[Measures of pseudorandomness]%
{Measures of pseudorandomness for finite sequences: minimal values} 

%========================= 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 supported by a USA Israeli BSF grant,
  by a grant from the Israel Science Foundation and by the Hermann Minkowski
  Minerva Center for Geometry at Tel Aviv University.  The second author was
  partially supported by FAPESP and CNPq through ProNEx projects (Proc.\ CNPq
  664107/1997--4 and Proc.\ FAPESP 2003/09925--5) and by CNPq
  (Proc.~306334/2004--6 and~479882/2004--5).  The fourth author was partially
  supported by MCT/CNPq through a ProNEx project (Proc.\ CNPq 662416/1996--1)
  and by CNPq (Proc.~300647/95--6).  The fifth author was partially supported
  by NSF Grant~0300529.  The authors gratefully acknowledge the support of a
  CNPq/NSF cooperative grant (910064/99--7, 0072064) and the Brazil/France
  Agreement in Mathematics (Proc.~CNPq 69--0014/01--5 and 69--0140/03--7).}
%   The collaboration of the Brazilian authors and the US author is supported by
%   a CNPq/NSF cooperative grant (910064/99--7, 0072064).  The collaboration of
%   the Brazilian authors and the French author is supported by the Agreement
%   Brazil/France in Mathematics (Proc.~CNPq 69-0014/01--5 and 69-0140/03--7).
%   }
%========================= 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}

%========================= dedication ========================================

\dedicatory{Dedicated to Professor B\'ela Bollob\'as on the occasion of his
  60th birthday}

%========================= abstract ==========================================
\begin{abstract}
  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'.  Two of these parameters are the
  \textit{normality measure}~$\cN(E_N)$ and the \textit{correlation
    measure~$C_k(E_N)$ of order~$k$}, which focus on different combinatorial
  aspects of~$E_N$.  In their work, amongst others, Mauduit and S\'ark\"ozy
  investigated the minimal possible value of these parameters.
  
  In this paper, we continue the work in this direction and prove a lower
  bound for the correlation measure~$C_k(E_N)$ ($k$~even) for arbitrary
  sequences~$E_N$, establishing one of their conjectures.  We also give an
  algebraic construction for a sequence~$E_N$ with small normality
  measure~$\cN(E_N)$.
  %\textbf{yk: Is the abstract all right like this?}
\end{abstract}
%========================= abstract ==========================================

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

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

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} certain `measures of pseudorandomness', to be
defined shortly.  We restrict ourselves to the Mauduit--S\'ark\"ozy parameters
directly relevant to the present note, and refer the reader
to~\cite{mauduit02:_finit} and~\cite{mauduit97} for detailed discussions
concerning the definitions below, related measures, and further related
literature.

Let~$k\in\NN$, $M\in\NN$, and~ $X\in\{-1,1\}^k$
%$a\in\ZZ$, $b\in\NN$, and~$b>0$ 
be given.  Also, let $D=\{d_1,\dots,d_k\}$, where the~$d_i$ are integers with
$1\leq d_1<\dots<d_k\leq N-M+1$.  Below, we write~$\card S$ for the
cardinality of a set~$S$, and if~$S$ is a set of numbers, then we write~$\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{multline}
  \label{eq:V_def}
  V(E_N,M,D)=\sum\{e_{n+d_1}e_{n+d_2}\dots e_{n+d_k}\:0\leq n<M\}\\
  =\sum_{0\leq n<M}\prod_{1\leq i\leq k}e_{n+d_i}
  =\sum_{0\leq n<M}\prod_{d\in D}e_{n+d}.
\end{multline}
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, 
%
On the other hand, one may think of the quantity~$V(E_N,M,D)$ as the
`correlation' among~$k$ length~$M$ segments of~$E_N$ `relatively positioned'
according to~$D=\{d_1,\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~$1\leq 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-1+d_k\leq N$}\}. 
\end{equation}

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

In Section~\ref{sec:typic-minim-C_k} we shall state and discuss our results
concerning the correlation measure~$C_k$, while in
Section~\ref{sec:typic-minim-N} we shall state and discuss our results on the
normality measure~$\cN$.

\subsection{Typical and minimal values of correlation}
\label{sec:typic-minim-C_k}
In~\cite{cassaigne02}, Cassaigne, Mauduit, and S\'ark\"ozy studied, amongst
others, the typical value of~$C_k(E_N)$ for random binary sequences~$E_N$,
with all the~$2^N$ sequences in~$\{-1,1\}^N$ equiprobable, and the minimal
possible value for~$C_k(E_N)$.  The investigation of the typical value
of~$C_k(E_N)$ is continued in~\cite{alon03:_measur_typical}, where Theorems~A
and~B below are proved.  (In what follows, we write~$\log$ for the natural
logarithm.)

%where Theorems~\ref{thm:order_of_W}--\ref{thm:order_of_N} below are proved.  

% \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}.  The reader is referred
% to~\cite{alon03:_measur_typical} for an alternative proof, the main idea of
% which is 
% also used in the proof of Theorem~\ref{thm:order_of_N} below.

%The next result 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{varthm}[Theorem~A]
%  \label{thm:order_of_C_k}
  Let~$0<\epsilon_0<1/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{varthm}

%Note that Theorem~\ref{thm:order_of_C_k}
Note that Theorem~A establishes the typical order of magnitude of~$C_k(E_N)$
for a wide range of~$k$, including values of~$k$ proportional to~$N$.  The
next result tells us that~$C_k(E_N)$ is concentrated in the case in which~$k$
is small.  

\begin{varthm}[Theorem~B]
%  \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 function~$\Gamma(k,N)$ and 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\Gamma(k,N)}<1+\epsilon
  \end{equation}
  holds is at least~$1-\epsilon$.
\end{varthm}

%Clearly, Theorem~\ref{thm:order_of_C_k} tells us that~$\Gamma(k,N)$ is of
Clearly, Theorem~A tells us that~$\Gamma(k,N)$ is of
order~$\sqrt{N\log{N\choose k}}$.  Let us now turn to the minimal possible
value of the parameter~$C_k(E_N)$.
% Let us now turn to the minimal possible values of the parameters~$W(E_N)$,
% $C_k(E_N)$, and~$\cN(E_N)$.  It follows from celebrated 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}, the following result is proved.
%concerning~$\min_{E_N}C_k(E_N)$.

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

%Theorem~\ref{thm:orig.C_kmin}(\textit{i}) follows simply from the observation
Theorem~C(\textit{i}) follows simply from the observation
that the alternating sequence~$E_N=(1,-1,1,-1,\dots)$ is such
that~$C_k(E_N)=1$ for odd~$k$.  Owing to
Theorem~C(\textit{i}), when concerned with minimal values
of~$C_k(E_N)$, we are only interested in even~$k$.  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
\begin{equation}
  \label{eq:conj_C_k}
  \min\big\{C_k(E_N)\:E_N\in\{-1,1\}^N\big\}\gg N^c, 
\end{equation}
which would be a considerable strengthening of
%Theorem~\ref{thm:orig.C_kmin}(\textit{ii}).  In this paper, we prove the
Theorem~C(\textit{ii}).  In this paper, we prove the
conjecture above in a more general form.  We shall prove the following result.

\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{{1\over2}\llfloor N\over k+1\rrfloor}
  \end{equation}
  for any~$E_N\in\{-1,1\}^N$.
\end{theorem}

The lower bound given in~\eqref{eq:minC_k_lwbd} decreases as~$k$ increases.
One may ask whether, in fact, $C_{2k}(E_N)\geq c\sqrt{k N}$ for some absolute
constant~$c>0$, or at least $C_{2k}(E_N)\geq c\sqrt{N}$ for some absolute
constant~$c>0$.  The results below (and the results in
Section~\ref{sec:further_conseq}) are partial answers in this direction.

It turns out that if we look at the maximum
of~$C_2(E_N),C_4(E_N),\dots,C_k(E_N)$ (with~$k$ again even), then a lower
bound of order~$\sqrt{k N}$ may indeed be proved.

\begin{theorem}
  \label{thm:C_2-C_2ell_lower_bound}
  There is an absolute constant~$c>0$ for which the following holds.  For any
  positive integers~$\ell$ and~$N$ with~$\ell\leq N/3$, we have
  \begin{equation}
    \label{eq:C_2-C_2ell_lower_bound}
    \max\{C_2(E_N),C_4(E_N),\dots,C_{2\ell}(E_N)\}\geq c\sqrt{\ell N}
  \end{equation}
  for all~$E_N\in\{-1,1\}^N$.
\end{theorem}

In view of Theorem~A, the lower bound in
Theorem~\ref{thm:C_2-C_2ell_lower_bound} is best possible apart from a
multiplicative factor of~$O\(\sqrt{\log(N/2\ell)}\)$, for all~$\ell\leq N/8$.

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

\begin{theorem}
  \label{thm:linear_systems_lwbd}
  Let positive integers~$k$ and~$N$ with~$2\leq k\leq\sqrt{N/6}$ be given.
  If~$N$ is large enough, then
  \begin{equation}
    \label{eq:linear_systems_lwbd}
    \max\{C_{2k-2}(E_N),C_{2k}(E_N)\}\geq\sqrt{{1\over2}\llfloor
      N\over3\rrfloor}
  \end{equation}
  for any~$E_N\in\{-1,1\}^N$.
\end{theorem}

Some further results are stated and proved in Section~\ref{sec:further_conseq}
(see Theorems~\ref{thm:PP_lwbd}, \ref{thm:Vinogradov_lwbd},
and~\ref{thm:C_ell-C_2ell_lower_bound}).

\subsection{Typical and minimal values of normality}
\label{sec:typic-minim-N}
We now turn to the normality measure~$\cN(E_N)$.
In~\cite{alon03:_measur_typical}, the following result is proved.

\begin{varthm}[Theorem~D]
%  \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{varthm}

Here, we shall give an explicit construction for sequences~$E_N\in\{-1,1\}^N$
%with~$\cN(E_N)$ small.  Theorem~\ref{thm:order_of_N} tells us that, typically,
with~$\cN(E_N)$ small.  Theorem~D tells us that, typically,
$\cN(E_N)$~is of order~$\sqrt N$.  We shall exhibit a sequence~$E_N$
with~$\cN(E_N)=O\(N^{1/3}(\log N)^{2/3}\)$.

\begin{theorem}
  \label{cor:cN_upbd}
  For any sufficiently large~$N$, there exists a sequence~$E_N\in\{-1,1\}^N$
  with
  \begin{equation}
    \label{eq:cN_lwbd}
    \cN(E_N)\leq3N^{1/3}(\log N)^{2/3}.
  \end{equation}
\end{theorem}

A simple argument shows that~$\cN(E_N)\geq(1/2+o(1))\log_2N$ for
any~$E_N\in\{-1,1\}^N$ (see Proposition~\ref{prop:remarks_cN} in
Section~\ref{sec:prel-remark-N}).  In view of Theorem~\ref{cor:cN_upbd}, we
have 
\begin{equation}
  \label{eq:min_cN_ineqs}
  \({1\over2}+o(1)\)\log_2N
  \leq\min_{E_N\in\{-1,1\}^N}\cN(E_N)
  \leq3N^{1/3}(\log N)^{2/3}
\end{equation}
for all large enough~$N$.  It would be interesting to close the rather wide
gap in~\eqref{eq:min_cN_ineqs}.

The construction of the sequence~$E_N\in\{-1,1\}^N$ in
Theorem~\ref{cor:cN_upbd} may be generalized to larger alphabets~$\Sigma$, as
long as the cardinality of~$\Sigma$ is a power of a prime (see
Section~\ref{sec:larger_alph}).  Finally, we remark that one of the
ingredients in the proof of~\eqref{eq:cN_lwbd} for our sequence~$E_N$ allows
one to give a short proof of the celebrated P\'olya--Vinogradov inequality on
incomplete character sums (see Section~\ref{sec:Polya-Vinogradov}), which is
somewhat simpler than the known proofs.

\section{The minimum of the correlation measure}
\label{sec:correlation_minimum}

\subsection{Auxiliary lemmas from linear algebra}
\label{sec:linear_algebra}
The proof of Theorem~\ref{thm:minC_k_lwbd} that we give in
Section~\ref{sec:pf_lwbd_corr} is based on the following elementary lemma from
linear algebra (see, e.g., \cite[Lemma~9.1]{alon:_probl_part_i} or
\cite[Lemma~7]{codenotti00:_some}), whose proof we include for completeness.

\begin{lemma}
  \label{lem:pudlak}
  For any symmetric matrix~$\bfA=(A_{ij})_{1\leq i,j\leq n}$, we have
  \begin{equation}
    \label{eq:pudlak}
    \rk(\bfA)\geq{(\tr(\bfA))^2\over\tr(\bfA^2)}
    ={\(\sum_{1\leq i\leq n}A_{ii}\)^2\over\sum_{1\leq i,j\leq
        n}A_{ij}^2}.
  \end{equation}
  Consequently, if~$A_{ii}=1$ for all~$i$ and~$|A_{ij}|\leq\epsilon$ for
  all~$i\neq j$, then
  \begin{equation}
    \label{eq:rk_half}
    \rk(\bfA)\geq{n\over1+\epsilon^2(n-1)}.
  \end{equation}
  In particular, if~$\epsilon=\sqrt{1/n}$, then~$\rk(\bfA)\geq n/2$.
\end{lemma}
\begin{proof}
  Let~$r=\rk(\bfA)$.  Then~$\bfA$ has exactly~$r$ non-zero eigenvalues, say,
  $\lambda_1,\dots,\lambda_r$.  By the Cauchy--Schwarz inequality, we have
%  \begin{multline*}
  \begin{equation*}
    (\tr(\bfA))^2=(\lambda_1+\dots+\lambda_r)^2
    \leq r(\lambda_1^2+\dots+\lambda_r^2)=r\tr(\bfA^2),
  \end{equation*}
%  \end{multline*}
  and it now suffices to notice that, because~$\bfA$ is symmetric, we have
  \begin{equation*}
    \tr(\bfA^2)=\sum_{1\leq i\leq n}\(\sum_{1\leq j\leq n}A_{ij}A_{ji}\)
    =\sum_{1\leq i,j\leq n}A_{ij}^2,
  \end{equation*}
  as required.   Inequality~\eqref{eq:rk_half} follows immediately
  from~\eqref{eq:pudlak}.
\end{proof}

The next lemma, due to the first author~\cite{alon:_probl_part_i}, improves
Lemma~\ref{lem:pudlak} for larger values of~$\epsilon$.

\begin{lemma}
  \label{lem:Alon_rk_lwbd}
  Let~$\bfA=(A_{ij})_{1\leq i,j\leq n}$ be an $n\times n$ real 
  matrix with~$A_{ii}=1$ for all~$i$ and~$|A_{ij}|\leq\epsilon$ for all~$i\neq
  j$, where~$\sqrt{1/n}\leq\epsilon\leq1/2$.  Then
  \begin{equation}
    \label{eq:Alon_rk_lwbd}
    \rk(\bfA)\geq{1\over100\epsilon^2\log(1/\epsilon)}\log n.
  \end{equation}
  If~$\bfA$ is symmetric, then~\eqref{eq:Alon_rk_lwbd} holds with the
  constant~$1/100$ replaced by~$1/50$.
\end{lemma}

For completeness, we give the proof of Lemma~\ref{lem:Alon_rk_lwbd}.  We shall
need the following auxiliary lemma~\cite{alon:_probl_part_i}.

\begin{lemma}
  \label{lem:9.2}
  Let~$\bfA=(A_{i,j})$ be an~$n\times n$ matrix of rank~$d$, and let~$P(x)$ be
  an arbitrary polynomial of degree~$k$.  Then the rank of the~$n\times n$
  matrix~$(P(A_{i,j}))$ is at most~${k+d\choose k}$.  Moreover, if~$P(x)=x^k$,
  then the rank of~$(P(A_{i,j}))=(A_{i,j}^k)$ is at most~${k+d-1\choose k}$.
\end{lemma}
\begin{proof}
  Let~$\bfv_1=(v_{1,j})_{j=1}^n$, $\bfv_2=(v_{2,j})_{j=1}^n$, $\dots$,
  $\bfv_d=(v_{d,j})_{j=1}^n$ be a basis of the row space of~$\bfA$.  Then the
  vectors~$(v_{1,j}^{k_1}v_{2,j}^{k_2}\cdots v_{d,j}^{k_d})_{j=1}^n$,
  where~$k_1,k_2,\dots,k_d$ range over all non-negative integers whose sum is
  at most~$k$, span the row space of the matrix~$(P(A_{i,j}))$.
  If~$P(x)=x^k$, then it suffices to take all these vectors corresponding
  to~$k_1,k_2,\dots,k_d$ whose sum is precisely~$k$.
\end{proof}

\begin{proof}[Proof of Lemma~\ref{lem:Alon_rk_lwbd}]
  Let us first note that the non-symmetric case follows from the symmetric
  case: if~$\bfA$ is not symmetric, it suffices to consider the symmetric
  matrix~$(\bfA^T+\bfA)/2$, whose rank is at most twice the rank of~$\bfA$.
  We therefore suppose that~$\bfA$ is symmetric, and proceed to
  prove~\eqref{eq:Alon_rk_lwbd} with the constant~$1/100$ replaced
  by~$1/50$.
  
  Let~$\delta=1/16$.  Consider first the case in
  which~$\epsilon\leq1/n^\delta$.  In this case,
  let~$m=\lfloor1/\epsilon^2\rfloor$, and let~$\bfA'$ be the submatrix
  of~$\bfA$ consisting of the, say, first~$m$ rows and first~$m$ columns
  of~$\bfA$.  By the choice of~$m$, we have that~$1/\sqrt m\geq\epsilon$, and
  hence Lemma~\ref{lem:pudlak} applies to~$\bfA'$, and we deduce
  that~$\rk(\bfA)\geq \rk(\bfA')\geq m/2$.  It now suffices to check that,
  because~$\epsilon\leq\min\{1/2,1/n^\delta\}$ and~$\delta=1/16$, we have
  \begin{equation}
    \label{eq:Alon_rk_lwbd.1}
    {1\over2}m\geq{3\over8\epsilon^2}={3\over2^7\delta\epsilon^2}\\
    >{1\over50\epsilon^2\log(1/\epsilon)}\log n,
  \end{equation}
  and we are done in this case.  We now suppose
  that~$1/n^\delta\leq\epsilon\leq1/2$.  In this case, we let
  \begin{equation}
    \label{eq:Alon_rk_lwbd.k_def}
    k=\llfloor\log n\over2\log(1/\epsilon)\rrfloor
    \geq\llfloor1\over2\delta\rrfloor=8,
  \end{equation}
  and let~$m=\lfloor1/\epsilon^{2k}\rfloor$.  Note that, then, we have~$m\leq
  n$.  We again let~$\bfA'$ be the submatrix of~$\bfA$ consisting of the
  first~$m$ rows and first~$m$ columns of~$\bfA$.  We now have
  \begin{equation}
    \label{eq:Alon_rk_lwbd.2}
    \epsilon^k\leq{1\over\sqrt m}.
  \end{equation}
  Let~$\bfA''$ be the matrix obtained from~$\bfA'$ by raising all its entries
  to the~$k$th power.  Because of~\eqref{eq:Alon_rk_lwbd.2} and the hypothesis
  on the entries of~$\bfA$, Lemma~\ref{lem:pudlak} applies and tells us that
  \begin{equation}
    \label{eq:Alon_rk_lwbd.3}
    \rk(\bfA'')\geq{1\over2}m={1\over2}\llfloor1\over\epsilon^{2k}\rrfloor
    \geq{0.49\over\epsilon^{2k}},
  \end{equation}
  where the last inequality follows easily from the fact
  that~$\epsilon\leq1/2$ and~$k\geq8$ (see~\eqref{eq:Alon_rk_lwbd.k_def}).  We
  now observe that Lemma~\ref{lem:9.2} tells us that
  \begin{equation}
    \label{eq:Alon_rk_lwbd.4}
    \rk(\bfA'')\leq{k+\rk(\bfA')\choose k}\leq\(\e(k+\rk(\bfA'))\over k\)^k.  
  \end{equation}
  Putting together~\eqref{eq:Alon_rk_lwbd.3} and~\eqref{eq:Alon_rk_lwbd.4},
  we get
  \begin{equation}
    \label{eq:Alon_rk_lwbd.5}
    \rk(\bfA)\geq\rk(\bfA')
    \geq{k\over\epsilon^2}\({0.49^{1/k}\over\e}-\epsilon^2\),  
  \end{equation}
  which, because~$0.49^{1/8}/\e\geq{1/3}$ and~$\epsilon^2\leq1/4$, implies
  that~$\rk(\bfA)\geq k/12\epsilon^2$.  Therefore, we have
  \begin{equation}
    \label{eq:Alon_rk_lwbd.6}
    \rk(\bfA)>{1\over50\epsilon^2\log(1/\epsilon)}\log n,
  \end{equation}
  and we are done.
\end{proof}

\subsection{Proof of the lower bounds for correlation}
\label{sec:pf_lwbd_corr}
We shall prove Theorem~\ref{thm:minC_k_lwbd}
and~\ref{thm:C_2-C_2ell_lower_bound} in this section.
These results will be deduced from suitable applications
of Lemmas~\ref{lem:pudlak} and~\ref{lem:Alon_rk_lwbd}; to describe these
applications, we first need to introduce some notation.

Let~$E_N=(e_i)_{1\leq i\leq N}\in\{-1,1\}^N$ be given.  Let a positive
integer~$M\leq N$ be fixed and set~$N'=N-M+1$.  Moreover, fix a family~$\cL$
of subsets of~$[N']$.
%and suppose that all members of~$\cL$
%have cardinality at most~$\ell$.  
We now define a vector~$\bfv_L=(v_{L,i})_{0\leq i<M}\in\{-1,1\}^M$ for
all~$L\in\cL$, letting
\begin{equation}
  \label{eq:v_Li_def}
  v_{L,i}=\prod_{x\in L}e_{i+x}
\end{equation}
for all~$0\leq i<M$ (note that~$1\leq i+x\leq M-1+N'=N$ for any~$x$
in~\eqref{eq:v_Li_def}).  Let us now define an $\cL\times\cL$
matrix~$\bfA=(A_{L,L'})_{L,L'\in\cL}$, putting
\begin{equation}
  \label{eq:A_LL'_def}
  A_{L,L'}={1\over M}\<\bfv_L,\bfv_{L'}\>
  ={1\over M}\sum_{0\leq i<M}v_{L,i}v_{L',i}
\end{equation}
for all~$L$, $L'\in\cL$.  Clearly, the diagonal entries of~$\bfA$ are
all~$1$.  Suppose now that~$L\neq L'$.  Then
\begin{multline}
  \label{eq:non_diag}
  A_{L,L'}={1\over M}\<\bfv_L,\bfv_{L'}\>
  ={1\over M}\sum_{0\leq i<M}
  \Big(\prod_{x\in L}e_{i+x}\Big)\Big(\prod_{y\in L'}e_{i+y}\Big)\\
  ={1\over M}\sum_{0\leq i<M}\prod_{z\in L\sdiff L'}e_{i+z},
\end{multline}
where we write~$L\sdiff L'$ for the symmetric difference of the sets~$L$
and~$L'$.  Let~$\cL^\sdiff=\{L\sdiff L'\:L,\,L'\in\cL,\;L\neq L'\}$ and
let~$K$ be the set of the cardinalities of the members of~$\cL^\sdiff$, that
is, $K=\{|S|\:S\in\cL^\sdiff\}$.  It follows from~\eqref{eq:non_diag} and the
definition of~$C_k(E_N)$ that
\begin{equation}
  \label{eq:C_k_cL_lwbd}
  \max\{C_k(E_N)\:k\in K\}\geq M\max\{|A_{L,L'}|\:L,\,L'\in\cL,\;L\neq L'\}.  
\end{equation}

Lemma~\ref{lem:pudlak} and~\eqref{eq:C_k_cL_lwbd} imply the following result.

\begin{lemma}
  \label{lem:C_k_cL_lwbd.1}
  We have
  \begin{equation}
    \label{eq:C_k_cL_lwbd.1}
    \max\{C_k(E_N)\:k\in K\}>\sqrt{M-{M^2\over|\cL|}}.
  \end{equation}
\end{lemma}
\begin{proof}
  Let~$\bfB=(\bfv_L^T)_{L\in\cL}$ be the $|\cL|\times M$~matrix with
  rows~$\bfv_L^T$ ($L\in\cL$).  Observing that~$\bfA=M^{-1}\bfB\bfB^T$, we see
  that~$\bfA$ has rank at most~$M$.  Combining this with the lower bound for
  the rank of~$\bfA$ given by Lemma~\ref{lem:pudlak}, we get
  \begin{equation}
    \label{eq:C_k_cL_lwbd.1.a}
    M\geq\rk(\bfA)>{|\cL|\over1+\epsilon^2|\cL|},
  \end{equation}
  where~$\epsilon=\max\{|A_{L,L'}|\:L,\,L'\in\cL,\;L\neq L'\}$.  It follows
  from~\eqref{eq:C_k_cL_lwbd.1.a} that 
  \begin{equation}
    \label{eq:C_k_cL_lwbd.1.b}
    \epsilon>\sqrt{{1\over M}-{1\over|\cL|}}.
  \end{equation}
  Inequality~\eqref{eq:C_k_cL_lwbd.1} follows from~\eqref{eq:C_k_cL_lwbd}
  on multiplying~\eqref{eq:C_k_cL_lwbd.1.b} by~$M$.
\end{proof}

We are now ready to prove Theorem~\ref{thm:minC_k_lwbd}.  

\begin{proof}[Proof of Theorem~\ref{thm:minC_k_lwbd}]
  Let~$k$, $N$, and~$E_N$ be as in the statement of
  Theorem~\ref{thm:minC_k_lwbd}.  Set~$\ell=k/2$ and $M=\lfloor
  N/(k+1)\rfloor$ and, as above, let~$N'=N-M+1$.  We take
  for~$\cL\subset\cP([N'])$ a set system of~$t=\lfloor N'/\ell\rfloor$
  pairwise disjoint $\ell$-element subsets~$L_1,\dots,L_t$ of~$[N']$.  Note
  that
  \begin{equation}
    \label{eq:cL_at_least_2M}
    |\cL|=t=\llfloor N-\lfloor N/(k+1)\rfloor+1\over k/2\rrfloor
    \geq\llfloor2N\over k+1\rrfloor\geq2M.
  \end{equation}
  Therefore, it follows from~\eqref{eq:C_k_cL_lwbd.1}
  and~\eqref{eq:cL_at_least_2M} that
  \begin{equation}
    \label{eq:minC_k_lwbd.aux}
    C_k(E_N)>\sqrt{M-{M^2\over|\cL|}}
    \geq\sqrt{M-{M\over2}}=\sqrt{{1\over2}\llfloor N\over k+1\rrfloor},
  \end{equation}
  as required.
\end{proof}

Lemma~\ref{lem:C_k_cL_lwbd.1} was deduced from an application of
Lemma~\ref{lem:pudlak} to the matrix~$\bfA=(A_{L,L'})$; the next lemma will be
obtained from an application of Lemma~\ref{lem:Alon_rk_lwbd} to~$\bfA$.

\begin{lemma}
  \label{lem:C_k_cL_lwbd.2}
  If~$2M\leq|\cL|<\e^{50M}$, then
  \begin{equation}
    \label{eq:C_k_cL_lwbd.2}
    \max\{C_k(E_N)\:k\in K\}
    \geq\min\left\{{1\over2}M,\sqrt{{1\over50}M(\log|\cL|)
        \left/\log{50M\over\log|\cL|}\right.}\right\}. 
  \end{equation}
\end{lemma}
\begin{proof}
  Let~$\epsilon=\max\{|A_{L,L'}|\:L,\,L'\in\cL,\;L\neq L'\}$.
  Inequality~\eqref{eq:rk_half} and the fact that~$\rk(\bfA)\leq M$, coupled
  with~$M\leq|\cL|/2$, give that
  \begin{equation}
    \label{eq:epsilon_large}
    \epsilon^2>{1\over M}-{1\over|\cL|}\geq{1\over|\cL|},
  \end{equation}
  and hence~$\epsilon>\sqrt{1/|\cL|}$.  If~$\epsilon>1/2$,
  then~\eqref{eq:C_k_cL_lwbd.2} follows immediately
  (recall~\eqref{eq:C_k_cL_lwbd}).  Therefore, we may suppose
  that~$\sqrt{1/|\cL|}\leq\epsilon\leq1/2$, and hence we may apply
  Lemma~\ref{lem:Alon_rk_lwbd} to the symmetric matrix~$\bfA$.  Combining the
  fact that~$\bfA$ has rank at most~$M$ with Lemma~\ref{lem:Alon_rk_lwbd}, we
  obtain that
  \begin{equation}
    \label{eq:C_k_cL_lwbd.2.a}
    M\geq\rk(\bfA)\geq{1\over50\epsilon^2\log(1/\epsilon)}\log|\cL|,
  \end{equation}
  whence
  \begin{equation}
    \label{eq:C_k_cL_lwbd.2.b}
    \epsilon^2\log{1\over\epsilon}\geq{1\over50M}\log|\cL|.
  \end{equation}
  Using that~$1/\epsilon\geq\log1/\epsilon$, we have
  from~\eqref{eq:C_k_cL_lwbd.2.b} that
  \begin{equation}
    \label{eq:C_k_cL_lwbd.2.c}
    \epsilon\geq\epsilon^2\log{1\over\epsilon}
    \geq{1\over50M}\log|\cL|. 
  \end{equation}
  Plugging~\eqref{eq:C_k_cL_lwbd.2.c} into~\eqref{eq:C_k_cL_lwbd.2.b}, we get  
  \begin{equation}
    \label{eq:C_k_cL_lwbd.2.d}
    \epsilon^2\log{50M\over\log|\cL|}\geq\epsilon^2\log{1\over\epsilon} 
    \geq{1\over50M}\log|\cL|,  
  \end{equation}
  and hence
  \begin{equation}
    \label{eq:C_k_cL_lwbd.2.e}
    \epsilon
    \geq\sqrt{{\log|\cL|\over50M}\left/\log{50M\over\log|\cL|}\right.}.
  \end{equation}
  Inequality~\eqref{eq:C_k_cL_lwbd.2} follows easily
  from~\eqref{eq:C_k_cL_lwbd}, \eqref{eq:C_k_cL_lwbd.2.e}, and the definition
  of~$\epsilon$.
\end{proof}

We shall now deduce Theorem~\ref{thm:C_2-C_2ell_lower_bound} from
Lemma~\ref{lem:C_k_cL_lwbd.2}.

\begin{proof}[Proof of Theorem~\ref{thm:C_2-C_2ell_lower_bound}]
  Let~$\ell$ and~$N$ with~$\ell\leq N/3$ be given.  Let~$M=\lfloor
  N/3\rfloor$, and set~$N'=N-M+1\geq2N/3$.  We take for~$\cL$ the set system
  of all $\ell$-element subsets of~$[N']$.  Then, clearly,
  $\cL^\sdiff=\{L\sdiff L'\:L,\,L'\in\cL,\;L\neq L'\}$ is the family of
  non-empty subsets of~$[N']$ of even cardinality not greater than~$2\ell$.
  Hence, $K=\{|S|\:S\in\cL^\sdiff\}=\{2,4,\dots,2\ell\}$.  Moreover,
  \begin{equation}
    \label{eq:cL_card_lwbd.2}
    |\cL|={N'\choose\ell}\geq N'\geq{2N\over3}\geq2M,
  \end{equation}
  and, as~$M=\lfloor N/3\rfloor\geq N/5$ because~$N\geq3$, we have
  \begin{equation}
    \label{eq:cL_card_upbd.2}
    |\cL|\leq2^N=(2^{N/M})^M\leq2^{5M}<\e^{50M}.
  \end{equation}
  Inequalities~\eqref{eq:cL_card_lwbd.2} and~\eqref{eq:cL_card_upbd.2} tell us
  that Lemma~\ref{lem:C_k_cL_lwbd.2} may be applied.  We deduce from that
  lemma that
  \begin{multline}
    \label{eq:C_2-C_2ell_lower_bound.2}
    \max\{C_2(E_N),C_4(E_N),\dots,C_{2\ell}(E_N)\}\\
    \geq\min\left\{{1\over2}M,\sqrt{{1\over50}M(\log|\cL|)
        \left/\log{50M\over\log|\cL|}\right.}\right\}. 
  \end{multline}
  If the minimum on the right-hand side of~\eqref{eq:C_2-C_2ell_lower_bound.2}
  is achieved by~$M/2=\lfloor N/3\rfloor/2$, then we are already done; suppose
  therefore that the minimum is given by the other term.  Observe that
  \begin{equation}
    \label{eq:C_2-C_2ell_lower_bound.0}
    {1\over50}M(\log|\cL|)\left/\log{50M\over\log|\cL|}\right.
    \geq{1\over50}\llfloor N\over3\rrfloor(\log|\cL|)
    \left/\log{50N/3\over\log|\cL|}\right.,
  \end{equation} 
  and, moreover, 
  \begin{equation}
    \label{eq:cL_card_lwbd}
    |\cL|={N'\choose\ell}\geq\(2N\over3\ell\)^\ell,
  \end{equation}
  so that
  \begin{equation}
    \label{eq:log_cL_lwbd}
    \log|\cL|\geq\ell\log{2N\over3\ell}.
  \end{equation}
  By~\eqref{eq:C_2-C_2ell_lower_bound.0} and~\eqref{eq:log_cL_lwbd}, it
  suffices to show that
  \begin{equation}
    \label{eq:C_2-C_2ell_lower_bound.1}
    {1\over150}N\ell\(\log{2N\over3\ell}\)
    \left/\log{50N/3\over\ell\log(2N/3\ell)}\right. 
    \geq c'N\ell 
  \end{equation} 
  for some absolute constant~$c'>0$.  Routine calculations show that a
  suitable constant~$c'>0$ will do in~\eqref{eq:C_2-C_2ell_lower_bound.1}.  We
  only give a sketch: suppose first that~$1\leq\ell=o(N)$.  In this case, it
  is simple to check that the left-hand side
  of~\eqref{eq:C_2-C_2ell_lower_bound.1} is in fact
  \begin{equation}
    \label{eq:C_2-C_2ell_lower_bound.3.a}
    \({1\over150}+o(1)\)N\ell.
  \end{equation}
  Suppose now that~$c''N\leq\ell\leq N/3$.  In this case, the
  left-hand side of~\eqref{eq:C_2-C_2ell_lower_bound.1} is at least
  \begin{equation}
    \label{eq:C_2-C_2ell_lower_bound.3.b}
    {1\over150}N\ell(\log2)\left/\log{50/3\over c''\log2}\right.,
  \end{equation}
  and~\eqref{eq:C_2-C_2ell_lower_bound.1} follows for some small
  enough~$c'>0$.  
\end{proof}

\subsection{Some further lower bounds for correlation}
\label{sec:further_conseq}
In this section, we deduce some further consequences of
Lemmas~\ref{lem:C_k_cL_lwbd.1} and~\ref{lem:C_k_cL_lwbd.2}, using other
families~$\cL$.

\subsubsection{Projective plane bounds}
\label{sec:proj-plane-bounds}
We shall prove Theorem~\ref{thm:linear_systems_lwbd} (see
Section~\ref{sec:typic-minim-C_k}) by making use of systems of sets derived
from projective planes.  Recall that Theorem~\ref{thm:linear_systems_lwbd}
tells us that, for any~$2\leq k\leq\sqrt{N/6}$ and any~$E_N\in\{-1,1\}^N$, at
least one of~$C_{2k-2}(E_N)$ and~$C_{2k}(E_N)$ is~$\geq c\sqrt N$, for some
absolute constant~$c>0$.  (We shall not try to obtain the best value of~$c$ in
what follows.)  We shall use the following fact.

\begin{lemma}
  \label{lem:reduced_PPs}
  Let positive integers~$k$ and~$n$ with~$k\leq(1/2)\sqrt n$ be given.  If~$n$
  is large enough, then there is a family~$\cL$ of $k$-element subsets
  of~$[n]$ with~$|\cL|=n$ and such that~$|L\cap L'|\leq1$ for all distinct~$L$
  and~$L'\in\cL$.
\end{lemma}

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

\begin{proof}[Proof of Theorem~\ref{thm:linear_systems_lwbd}]
  Let~$k$ and~$N$ as in the statement of the theorem be given.  Let~$M=\lfloor
  N/3\rfloor$ and
  \begin{equation}
    \label{eq:N'_def}
    N'=N-M+1\geq{2\over3}N\geq2M.
  \end{equation}
  Observe that~$k\leq\sqrt{N/6}=(1/2)\sqrt{2N/3}\leq(1/2)\sqrt{N'}$.  We now
  use that~$N$ is supposed to be large and invoke Lemma~\ref{lem:reduced_PPs},
  to obtain a family~$\cL$ of $k$-element subsets of~$[N']$ with~$|\cL|=N'$
  and~$|L\cap L'|\leq1$ for any two distinct~$L$ and~$L'\in\cL$.

  By~\eqref{eq:N'_def}, we have
  \begin{equation}
    \label{eq:3}
    M-{M^2\over|\cL|}\geq{1\over2}M={1\over2}\llfloor N\over3\rrfloor.
  \end{equation}
  Moreover, $|L\sdiff L'|\in\{2k-2,2k\}$ for all distinct~$L$ and~$L'\in\cL$.
  Inequality~\eqref{eq:linear_systems_lwbd} follows
  from~\eqref{eq:C_k_cL_lwbd.1}. 
\end{proof}

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

\begin{theorem}
  \label{thm:PP_lwbd}
  For any constant~$1/\sqrt2<\alpha<1$, there is a constant~$c=c(\alpha)>0$
  for which the following holds.  Given any~$\epsilon>0$, there is~$N_0$ such
  that if~$N\geq N_0$ and~$k$ is a power of a prime and~$|k-\alpha\sqrt
  N|\leq\epsilon\sqrt N$, then
  \begin{equation}
    \label{eq:PP_lwbd}
    C_{2k}(E_N)\geq c\sqrt N
  \end{equation}
  for any~$E_N\in\{-1,1\}^N$.
\end{theorem}

\begin{proof}%[Proof of Theorem~\ref{thm:PP_lwbd}]
  We only give a sketch of the proof.  Let~$k$ be a large prime power as in
  the statement of our result, and set
  \begin{equation}
    \label{eq:N'_M_def}
    N'=k^2+k+1
    \quad\text{and}\quad
    M=N-N'+1.
  \end{equation}
  Using that~$k=(\alpha+o(1))\sqrt N$, we have
  \begin{equation}
    \label{eq:N'_M_asympt}
    N'=(\alpha^2+o(1))N
    \quad\text{and}\quad
    M=(1-\alpha^2+o(1))N.
  \end{equation}
  We now use that~$k$ is a prime power, and let~$\cL$ be the family of lines
  of a projective plane with point set~$[N']$.  Clearly, every member of~$\cL$
  has~$k+1$ elements and
  \begin{equation}
    \label{eq:cL_size}
    |\cL|=N'=(\alpha^2+o(1))N.
  \end{equation}
  We shall now apply Lemma~\ref{lem:C_k_cL_lwbd.1}.
  By~\eqref{eq:N'_M_asympt}, we have
  \begin{multline}
    \label{eq:application_C_k_cL_lwbd.1}
    M-{M^2\over|\cL|}
    =(1-\alpha^2+o(1))N-{(1-\alpha^2+o(1))^2N^2\over(\alpha^2+o(1))N}\\
%    =(1-\alpha^2+o(1))N-{(1-\alpha^2+o(1))^2\over(\alpha^2+o(1))}N\\
    =\(1-{1-\alpha^2+o(1)\over\alpha^2+o(1)}\)(1-\alpha^2+o(1))N\\
    =(1+o(1))\(2-{1\over\alpha^2}\)(1-\alpha^2)N.
  \end{multline}
  Clearly, $|L\sdiff L'|=2k$ for all distinct~$L$ and~$L'\in\cL$.  Therefore,
  inequality~\eqref{eq:C_k_cL_lwbd.1} in Lemma~\ref{lem:C_k_cL_lwbd.1},
  together with the hypothesis that~$1/\sqrt2<\alpha<1$, imply the desired
  result.
\end{proof}

The proof of Theorem~\ref{thm:PP_lwbd} above is based on
Lemma~\ref{lem:C_k_cL_lwbd.1}; one may use Lemma~\ref{lem:C_k_cL_lwbd.2}
instead, which would give a somewhat different value for the constant~$c$
in~\eqref{eq:PP_lwbd}.  A bound of the form~\eqref{eq:PP_lwbd} for~$k$ of
order~$N$ may also be proved in the case in which there exists a $4k\times4k$
Hadamard matrix.  Indeed, it suffices to consider such a matrix as the
incidence matrix of a system~$\cL$ of $2k$-element subsets of a $4k$-element
set; the system~$\cL$ would then have the property that all pairwise symmetric
differences of its members are of cardinality~$2k$.

The condition that~$k$ should be a power of a prime in
Theorem~\ref{thm:PP_lwbd} may be removed by making use of Vinogradov's three
primes theorem (to be more precise, we use a strengthening of that result).
The key observation is the following.

\begin{lemma}
  \label{lem:Vinogradov-3ps}
  For any~$\epsilon>0$, there is an integer~$k_0$ for which the following
  holds.  If~$k\geq k_0$ is an odd integer, then there there is a family~$\cL$
  of $(k+3)$-element subsets of~$[n]$, where~$|n-k^2/3|\leq\epsilon k^2$, such
  that~$\big||\cL|-n/3\big|\leq\epsilon n$ and
  \begin{equation}
    \label{eq:Vinogradov-3ps-cond}
    |L\sdiff L'|=2k
  \end{equation}
  for all distinct~$L$ and~$L'\in\cL$.  If~$k\geq k_0$ is even, then there is
  a family~$\cL$ of $(k+4)$-element subsets of~$[n]$,
  where~$|n-k^2/4|\leq\epsilon k^2$, such
  that~$\big||\cL|-n/4\big|\leq\epsilon n$ and~\eqref{eq:Vinogradov-3ps-cond}
  holds for all distinct~$L$ and~$L'\in\cL$.
\end{lemma}
\begin{proof}
  We give a sketch of the proof.  Let~$\epsilon>0$ be fixed and suppose first
  that~$k$ is a large odd integer.
  
  We use a strengthening of Vinogradov's theorem, according to which any large
  enough odd integer~$k$ may be written as a sum of three primes~$p_1$, $p_2$,
  and~$p_3$ that satisfy~$p_i=(1/3+o(1))k$, where~$o(1)\to0$ as~$k\to\infty$
  (an old theorem of Haselgrove~\cite{haselgrove51:_some} implies this
  result).  Let~$\cL_1$, $\cL_2$, and~$\cL_3$ be projective planes of
  order~$p_1$, $p_2$, and~$p_3$, respectively, and suppose that~$p_1\leq p_2$
  and~$p_3$.  We take the~$\cL_i$ on pairwise disjoint point sets~$X_i$ and
  let~$X=X_1\cup X_2\cup X_3$.  Clearly,
  $n=|X|=3(1/3+o(1))^2k^2=(1/3+o(1))k^2$.  Let the lines of~$\cL_i$ be
  $L_1^{(i)},\cdots,L_{n_i}^{(i)}$,
  where~$n_i=p_i^2+p_i+1=(1/3+o(1))^2k^2=(1/3+o(1))n$.  We let~$\cL$ be the
  set system on~$X$ given by
  \begin{equation}
    \label{eq:V_cL_def}
    \cL=\big\{L_j^{(1)}\cup L_j^{(2)}\cup L_j^{(3)}\:1\leq j\leq n_1\big\}.
  \end{equation}
  The members of~$\cL$ are therefore $(k+3)$-element subsets of~$X$,
  with~$|L\sdiff L'|=2(p_1+p_2+p_3)=2k$ for all distinct~$L$ and~$L'\in\cL$,
  and the case in which~$k$ is a large odd integer follows.
  
  For even~$k$, it suffices to let~$p_4=(1/4+o(1))k$ be an odd prime (whose
  existence follows from the prime number theorem) and apply Haselgrove's
  result to~$k-p_4$, and then construct~$\cL$ as the union of~$4$ suitable
  projective planes.  We omit the details.
\end{proof}

Lemmas~\ref{lem:C_k_cL_lwbd.1} and~\ref{lem:Vinogradov-3ps} imply the
following result.

\begin{theorem}
  \label{thm:Vinogradov_lwbd}
  For all~$\epsilon>0$, there are constants~$c>0$, $k_0$, and~$N_0$ for which
  the following hold.  
  \begin{enumerate}
  \item[(\textit{i})]If~$k\geq k_0$ is an odd integer with
    \begin{equation}
      \label{eq:Vinogradov_k_odd_cond}
      \({3\over2}+\epsilon\)\sqrt N\leq k\leq\(\sqrt3-\epsilon\)\sqrt N,
    \end{equation}
    then~$C_{2k}(E_N)\geq c\sqrt N$ for all~$E_N\in\{-1,1\}^N$ as long
    as~$N\geq N_0$.
  \item[(\textit{ii})]If~$k\geq k_0$ is an even integer with
    \begin{equation}
      \label{eq:Vinogradov_k_even_cond}
      \({4\over5}\sqrt5+\epsilon\)\sqrt N\leq k\leq\(2-\epsilon\)\sqrt N,
    \end{equation}
    then~$C_{2k}(E_N)\geq c\sqrt N$ for all~$E_N\in\{-1,1\}^N$ as long
    as~$N\geq N_0$.
  \end{enumerate}
\end{theorem}

We omit the proof of Theorem~\ref{thm:Vinogradov_lwbd}.  We only remark that
it suffices to take for~$\cL$ in Lemma~\ref{lem:C_k_cL_lwbd.1} the systems
given by Lemma~\ref{lem:Vinogradov-3ps}.  One may prove results similar to
Theorem~\ref{thm:Vinogradov_lwbd} for other ranges of~$k$ of order~$\sqrt N$
using the method above: one simply proves variants of
Lemma~\ref{lem:Vinogradov-3ps} by writing~$k$ as the sum of~$h$ nearly equal
primes, for other values of~$h$.

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

\subsubsection{A variant of Theorem~\ref{thm:C_2-C_2ell_lower_bound}}
\label{sec:variant-thm:2-2ell}
In this section, we shall prove a result similar in nature to
Theorem~\ref{thm:C_2-C_2ell_lower_bound}.

\begin{theorem}
  \label{thm:C_ell-C_2ell_lower_bound}
  There is an absolute constant~$c>0$ for which the following holds.  For any
  positive integers~$\ell$ and~$N$ with~$\ell\leq N/25$ and~$N$ large enough,
  we have
  \begin{equation}
    \label{eq:C_2-C_2ell_lower_bound.z}
    \max\{C_{2\ell+2}(E_N),C_{2\ell+4}(E_N),\dots,C_{4\ell}(E_N)\}
    \geq c\sqrt{\ell N}
  \end{equation}
  for all~$E_N\in\{-1,1\}^N$.
\end{theorem}

The proof of Theorem~\ref{thm:C_ell-C_2ell_lower_bound} is based on the
following lemma.

\begin{lemma}
  \label{lem:one-sided_H}
  Let~$1\leq\ell\leq n/9\e$.  Then there is a system~$\cL$ of $2\ell$-element
  subsets of~$[n]$ with
  \begin{equation}
    \label{eq:one-sided_H.1}
    |\cL|\geq{1\over2}{n/9\e\choose\ell}
  \end{equation}
  and
  \begin{equation}
    \label{eq:one-sided_H.2}
    |L\sdiff L'|\geq2\ell+2
  \end{equation}
  for all distinct~$L$ and~$L'\in\cL$.
\end{lemma}
\begin{proof}
  We give a sketch of the proof.  Comparing with a geometric series, one may
  check that, say,
  \begin{equation}
    \label{eq:hypergeom}
    \sum_{\ell\leq j\leq2\ell}{2\ell\choose j}{n-2\ell\choose2\ell-j}
    \leq2{2\ell\choose\ell}{n-2\ell\choose\ell}.
  \end{equation}
  Let~$\cL$ be a maximal family of $2\ell$-element subsets of~$[n]$, with any
  two of its members satisfying~\eqref{eq:one-sided_H.2} for all distinct~$L$
  and~$L'\in\cL$.  Then, clearly,
  \begin{equation}
    \label{eq:maxl_sep.lwbd}
    2{2\ell\choose\ell}{n-2\ell\choose\ell}|\cL|
    \geq|\cL|\sum_{\ell\leq j\leq2\ell}{2\ell\choose j}{n-2\ell\choose2\ell-j} 
    \geq{n\choose2\ell}.
  \end{equation}
  Therefore,
  \begin{multline}
    \label{eq:maxl_sep.lwbd.2}
    |\cL|\geq{1\over2}{n\choose2\ell}
    \left/{2\ell\choose\ell}{n-2\ell\choose\ell}\right.
    ={(n)_\ell(n-\ell)_\ell(\ell!)^2\over
      2(2\ell)_\ell(n-2\ell)_\ell(2\ell)!}\\
    \geq{(n-\ell)_\ell\over2(2\ell)_\ell4^\ell}
    \geq{1\over2}\(n-\ell\over8\ell\)^\ell
    \geq{1\over2}\(n\over9\ell\)^\ell
    \geq{1\over2}{n/9\e\choose\ell},
  \end{multline}
  as required.
\end{proof}

\begin{proof}[Proof of
  Theorem~\ref{thm:C_ell-C_2ell_lower_bound}] This follows from
  Lemmas~\ref{lem:C_k_cL_lwbd.2} and~\ref{lem:one-sided_H}; we shall only give
  a sketch of the proof, because the argument is simple and very similar to
  the argument given in the proof of Theorem~\ref{thm:C_2-C_2ell_lower_bound}.
  Let~$\ell$ and~$N$ be as given in the statement of
  Theorem~\ref{thm:C_ell-C_2ell_lower_bound}.  The case in which~$\ell=1$ is
  covered by Theorem~\ref{thm:minC_k_lwbd} (in fact, the case in which~$\ell$
  is bounded follows from that result).  Therefore, we suppose~$\ell\geq2$.
  Let~$M=\lfloor N/50\rfloor$ and~$N'=N-M+1$.  Let~$\cL$ be a family of
  $2\ell$-element subsets of~$[N']$ of maximal cardinality
  satisfying~\eqref{eq:one-sided_H.2} for all distinct~$L$ and~$L'\in\cL$.  By
  Lemma~\ref{lem:one-sided_H}, we have
  \begin{equation}
    \label{eq:one-sided_H.appl}
    2M\leq{1\over2}\(N'/9\e\over2\)^2
    \leq{1\over2}{N'/9\e\choose\ell}\leq|\cL|\leq2^{N'}<\e^{50M}
  \end{equation}
  for all large enough~$N$.  Therefore, Lemma~\ref{lem:C_k_cL_lwbd.2} applies
  and we deduce that, for all~$E_N\in\{-1,1\}^N$, we have
  \begin{multline}
    \label{eq:C_2-C_2ell_lower_bound.zz}
    \max\{C_{2\ell+2}(E_N),C_{2\ell+4}(E_N),\dots,C_{4\ell}(E_N)\}\\
    \geq\min\left\{{1\over2}M,\sqrt{{1\over50}M(\log|\cL|)
        \left/\log{50M\over\log|\cL|}\right.}\right\}. 
  \end{multline}
  If the minimum on the right-hand side
  of~\eqref{eq:C_2-C_2ell_lower_bound.zz} is achieved by~$M/2$, we are done.
  In the other case, we may check that~\eqref{eq:C_2-C_2ell_lower_bound.z}
  follows for a suitable absolute constant~$c>0$ by, say, analysing the
  cases~$1\leq\ell=o(N)$ and~$\ell\geq c'N$ separately (see the proof of
  Theorem~\ref{thm:C_2-C_2ell_lower_bound}).
\end{proof}

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

However, we mention that the argument above applies in a more general setting.
For~$E_N\in\{-1,1\}^N$, let
\begin{equation}
  \label{eq:tC_k_def}
  \tC_k(E_N)=\max\{V(E_N,M,D)\:\text{$M$ and~$D$ with $M-1+d_k\leq N$}\},
\end{equation}
where~$D=\{d_1,\dots,d_k\}$ is as in Section~\ref{sec:intro}; the only
difference between~$C_k(E_N)$ and~$\tC_k(E_N)$ is that, in the definition
of~$\tC_k(E_N)$, we do not take~$V(E_N,M,D)$ in absolute value
(cf.~\eqref{eq:C_k_def} and~\eqref{eq:tC_k_def}).  Clearly, $\tC_k(E_N)\leq
C_k(E_N)$.  The argument from coding theory briefly sketched in the previous
paragraph applies to~$\tC_k(E_N)$ as well.

%\pagebreak
\section{The minimum of the normality measure}
\label{sec:minimal_normality}

\subsection{Remarks on $\min\cN(E_N)$}
\label{sec:prel-remark-N}
We start with two observations on~$\cN(E_N)$.  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\}$.

\begin{proposition}
  \label{prop:remarks_cN}
%  \begin{enumerate}
%  \item[(\textit{i})]
  {\rm(\textit{i})}~We have $\min_{E_N}\cN_k(E_N)=1-2^{-k}$ for any~$k\geq1$
  and any~$N\geq2^k$.
%  \item[(\textit{ii})]
    {\rm(\textit{ii})}~We have
    \begin{equation}
      \label{eq:cN_log_lwbd}
      \min_{E_N}\cN(E_N)\geq\({1\over2}+o(1)\)\log_2N.
    \end{equation}
%  \end{enumerate}
\end{proposition}
\begin{proof}
  To prove~(\textit{i}), we simply consider powers of appropriate de Bruijn
  sequences~\cite{bruijn46}.  More precisely, we take a circular sequence in
  which every member of~$\{-1,1\}^k$ occurs exactly once, open it up (turning
  it into a linear sequence), and repeat it an appropriate number of times.
  The fact that~$\cN_k(E_N)\geq1-2^{-k}$ for this sequence~$E_N$ may be seen
  by taking~$M=1$ in~\eqref{eq:cN_k_def} with~$X$ the prefix of~$E_N$ of
  length~$k$.  We leave the other inequality for the reader.
  
  Let us now prove~(\textit{ii}).  If a sequence~$E_N\in\{-1,1\}^N$ contains
  no segment of length~$k=\lfloor\log_2N-\log_2\log_2N\rfloor$ of
  repeated~$1$s, then
  \begin{equation}
    \label{eq:no_consecutive_1s}
    \cN_k(E_N)\geq{N-k+1\over2^k}=(1+o(1)){N\over2^k}\geq(1+o(1))\log_2N,
  \end{equation}
  as required.  Suppose now that~$E_N=(e_i)_{1\leq i\leq N}$ does contain such
  a segment, say, $(e_{M_0},\dots,e_{M_0+k-1})=(1,\dots,1)$.
  Fix~$\ell=\ell(N)\to\infty$ as~$N\to\infty$ with~$\ell=o(k)$, and
  let~$X_\ell$ be the sequence of~$\ell$ consecutive~$1$s.
  Let~$M_1=M_0+k-\ell$, and note that then
  \begin{multline}
    \label{eq:T_jump}
    T(E_N,M_1,X_\ell)-T(E_N,M_0,X_\ell)\\
    =M_1-M_0+1=k-\ell+1=(1+o(1))k.
  \end{multline}
  Therefore
  \begin{multline}
    \label{eq:T_gap}
    \(T(E_N,M_1,X_\ell)-{M_1\over2^\ell}\)
    -\(T(E_N,M_0,X_\ell)-{M_0\over2^\ell}\)\\
    =(1+o(1))k-(M_1-M_0)2^{-\ell}
    =(1+o(1))k.
  \end{multline}
  It follows from~\eqref{eq:T_gap} that for some~$M_0\leq M^*\leq M_1$
  we have  
  \begin{equation}
    \label{eq:there_is_M^*}
    \left|T(E_N,M^*,X_\ell)-{M^*\over2^\ell}\right|
    \geq\({1\over2}+o(1)\)k=\({1\over2}+o(1)\)\log_2N.
  \end{equation}
  Therefore, $\cN(E_N)\geq\cN_\ell(E_N)\geq(1/2+o(1))\log_2N$, as required. 
\end{proof}

We suspect that the logarithmic lower bound in
Proposition~\ref{prop:remarks_cN}(\textit{ii}) is far from the truth.

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

\subsection{A sequence~$E_N$ with small~$\cN(E_N)$}
\label{sec:the_construction}
Our aim in this section is to prove Theorem~\ref{cor:cN_upbd}.  We start by
describing the construction of~$E_N$.  

Let~$s$ be a positive integer and let~$\FF_{2^s}=\GF(2^s)$ be the finite field
with~$2^s$ elements.  Fix a primitive element~$x\in\FF_{2^s}^*$, and
let~$m=|\FF_{2^s}^*|=2^s-1$.  We consider~$\FF_{2^s}$ as a vector space
over~$\FF_2$, and fix a non-zero linear functional
\begin{equation}
  \label{eq:b_def}
  b\:\FF_{2^s}\to\FF_2.
\end{equation}
We now let
\begin{equation}
  \label{eq:cN.tE_m_def}
  \tE_m=(b(x),b(x^2),\dots,b(x^m))\in\FF_2^m=\{0,1\}^m
\end{equation}
and let
\begin{equation}
  \label{eq:cN.E_m_def}
  E_m=((-1)^{b(x)},(-1)^{b(x^2)},\dots,(-1)^{b(x^m)})\in\{-1,1\}^m. 
\end{equation}
Finally, set
\begin{equation}
  \label{eq:cN.E_N_def}
  E_N=E_m^q=E_m\dots E_m\qquad\text{($q$~factors)},
\end{equation}
where~$E_m^q$ denotes the concatenation of~$q$ copies of~$E_m$; clearly,
$E_N$~has length~$N=qm$.

\begin{theorem}
  \label{thm:small_cN}
  Let~$s\geq2$.  With~$E_N$ as defined in~\eqref{eq:cN.E_N_def}, we
  have
  \begin{equation}
    \label{eq:small_cN}
    \cN(E_N)\leq q+2(\log_2(m-1))\sqrt m.
  \end{equation}
\end{theorem}

Theorem~\ref{cor:cN_upbd} will be deduced from Theorem~\ref{thm:small_cN} in
Section~\ref{sec:proof_of_Normality} below.  Let us now give a rough outline
of the proof of Theorem~\ref{thm:small_cN}.  Essentially all the work will
concern the sequence~$E_m$ defined above.  

In what follows, we shall first prove that any reasonably long segment
of~$E_m$ has small `discrepancy'; we shall show that the entries of segments
of~$E_m$ of length~$k$ add up to~$O\big((\log k)\sqrt{m}\big)$ (see
Corollary~\ref{cor:segment_discr}).  We shall then show two results concerning
the number of occurrences of (short) words in~$E_m$.  We shall first show that
all the words of length~$k\leq s$ (except for the word~$(0,\dots,0)$) occur
exactly the same number of times in~$E_m$ (see Lemma~\ref{lem:de_Bruijn}).  We
shall then prove a similar fact for \textit{segments} of~$E_m$, although for
segments the conclusion will be weaker (see
Lemma~\ref{lem:segment_de_Bruijn}).  Theorem~\ref{thm:small_cN} will then be
deduced from these facts in Section~\ref{sec:proof_of_Normality}.

\subsubsection{Auxiliary lemmas}
\label{sec:auxiliary}
We start with a well known lemma concerning the `discrepancy' of matrices
whose rows have uniformly bounded norm and, pairwise, have non-positive inner
product (see, e.g., \cite[Theorem~15.2]{erd74:_probab} for a similar
statement).
\begin{lemma}
  \label{thm:lindsey}
  Let~$H=(h_{ij})_{1\leq i,j\leq M}$ be an $M$~by~$M$ real matrix and
  let~$\bfv_i$ be the $i$th row of~$H$ $(1\leq i\leq M)$.  Let~$A$,
  $B\subset[M]$ be given, and suppose that
  \begin{equation}
    \label{eq:row_norm}
    \|\bfv_a\|\leq\sqrt m
  \end{equation}
  for all~$a\in A$ and
  \begin{equation}
    \label{eq:neg_scalar}
    \<\bfv_a,\bfv_{a'}\>=\sum_{1\leq b\leq M}h_{ab}h_{a'b}\leq0
  \end{equation}
  for all~$a\neq a'$ with~$a$, $a'\in A$.  Then
  \begin{equation}
    \label{eq:lindsey_thm}
    \bigg|\sum_{a\in A,\;b\in B}h_{ab}\bigg|\leq\sqrt{m|A||B|}.
  \end{equation}
\end{lemma}
\begin{proof}
  Let~$\bfone_B\in\{0,1\}^M$ be the characteristic vector of~$B$.  By the
  Cauchy--Schwarz inequality, we have
  \begin{equation}
    \label{eq:lindsey1}
    \bigg|\sum_{A,\,B}h_{ab}\bigg|
    =\bigg|\bigg\langle\sum_{a\in A}\bfv_a,\bfone_B\bigg\rangle\bigg|
    \leq\bigg\|\sum_{a\in A}\bfv_a\bigg\|\sqrt{|B|}.
%    =\bigg\|\sum_{a\in A}\bfv_a\bigg\|\sqrt b.
  \end{equation}
  From~\eqref{eq:row_norm} and~\eqref{eq:neg_scalar}, we have
  \begin{equation}
    \label{eq:lindsey_ortho}
    \bigg\|\sum_{a\in A}\bfv_a\bigg\|^2
    =\sum_{a\in A}\|\bfv_a\|^2+\sum_{a\in A}\sum_{a\neq a'\in
    A}\<\bfv_a,\bfv_{a'}\>\leq m|A|.
  \end{equation}
  Plugging~\eqref{eq:lindsey_ortho} into~\eqref{eq:lindsey1}, we have
  \begin{equation*}
    \bigg|\sum_{A,\,B}h_{ab}\bigg|\leq\sqrt{m|A||B|},
  \end{equation*}
  as required.
\end{proof}

We now define a matrix~$\bfE$ from~$E_m$; we shall apply
Lemma~\ref{thm:lindsey} to~$\bfE$ to deduce the discrepancy property we seek
for~$E_m$.  Let
\begin{equation}
  \label{eq:bfE_def}
  \bfE=(E_{ij})_{1\leq i,j\leq m}=
  \begin{bmatrix}
    (-1)^{b(x)} &(-1)^{b(x^2)} &\dots &(-1)^{b(x^m)}\\
    (-1)^{b(x^2)} &(-1)^{b(x^3)} &\dots &(-1)^{b(x)}\\
    \vdots &\vdots &\ddots &\vdots\\
    (-1)^{b(x^m)} &(-1)^{b(x)} &\dots &(-1)^{b(x^{m-1})}
  \end{bmatrix}.
\end{equation}
Note that~$\bfE$ is an $m\times m$ circulant, symmetric $\{-1,1\}$-matrix
whose first row is~$E_m$.  For convenience, let~$\bfe_i=(E_{ij})_{1\leq j\leq
  m}$ ($1\leq i\leq m$) denote the $i$th row of~$\bfE$.  Moreover,
if~$\bfv=(v_j)_{1\leq j\leq m}$ and~$\bfw=(w_j)_{1\leq j\leq m}$ are two real
$m$-vectors, let~$\bfv\circ\bfw$ denote the $m$-vector~$(v_jw_j)_{1\leq j\leq
  m}$.

\begin{lemma}
  \label{lem:bfE_lemma}
  The following hold for~$\bfE${\rm:}
  \begin{enumerate}
  \item[(\textit{i})]Every row of~$\bfE$ adds up to~$-1$, that is,
    $\sum_{1\leq j\leq m}E_{ij}=-1$  for all~$1\leq i\leq m$.
  \item[(\textit{ii})]For all~$i\neq i'$ $(1\leq i,i'\leq m)$, we
    have~$\bfe_i\circ\bfe_{i'}=\bfe_{i''}$ for some~$1\leq i''\leq m$.
  \item[(\textit{iii})]The matrix~$\bfE$ satisfies
    \begin{equation}
      \label{eq:bfE_quasi-Hadamard}
      \bfE\bfE^T=-\bfJ+(m+1)\bfI,
    \end{equation}
    where~$\bfJ$ is the~$m\times m$ matrix with all entries~$1$ and~$\bfI$ is
    the $m\times m$ identity matrix.
  \item[(\textit{iv})]For all~$A$ and~$B\subset[m]$, we have
    \begin{equation}
      \label{eq:small_disc.E.RR}
      \bigg|\sum_{a\in A,\,b\in B}E_{ab}\bigg|\leq\sqrt{m|A||B|}.
    \end{equation}
  \end{enumerate}
%    The eigenvalues of~$\bfE$ are all~$\leq\sqrt{m+1}$ in
%    absolute value.
\end{lemma}
\begin{proof}
  Since~$b\:\FF_{2^s}\to\FF_2$ is a non-zero linear functional, $b^{-1}(0)$ is
  a hyperplane in~$\FF_{2^s}$ and hence has cardinality~$2^{s-1}$.  Given
  that~$\FF_{2^s}^*=\{x^j\:1\leq j\leq m=2^s-1\}$, we conclude that~$b(x^j)=1$
  for~$2^{s-1}$ values of~$j$ with~$1\leq j\leq m$ and~$b(x^j)=0$ for all the
  other~$2^{s-1}-1$ values of~$j$ with~$1\leq j\leq m$.  Therefore,
  statement~(\textit{i}) follows.  Let now~$1\leq i<i'\leq m$ be fixed.  Then
  \begin{align}
    &\bfe_i\circ\bfe_{i'}\nonumber\\
    &\quad=((-1)^{b(x^i)+b(x^{i'})},(-1)^{b(x^{i+1})+b(x^{i'+1})},\dots,
    (-1)^{b(x^{i-1})+b(x^{i'-1})})\nonumber\\
    &\quad=((-1)^{b(x^i+x^{i'})},(-1)^{b(x^{i+1}+x^{i'+1})},\dots,
    (-1)^{b(x^{i-1}+x^{i'-1})})\nonumber\\
    &\quad=((-1)^{b(x^i(1+x^{i'-i}))},(-1)^{b(x^{i+1}(1+x^{i'-i}))},\dots,
    (-1)^{b(x^{i-1}(1+x^{i'-i}))})\label{eq:bfe_i''0}.
  \end{align}
  However, as~$0<i'-i<m$, we have~$1+x^{i'-i}\neq0$, and
  hence~$1+x^{i-i'}=x^k$ for some~$1\leq k\leq m$.  Therefore, we have
  from~\eqref{eq:bfe_i''0} that
  \begin{equation}
    \label{eq:e_i''1}
    \bfe_i\circ\bfe_{i'}
    =((-1)^{b(x^{i+k})},(-1)^{b(x^{i+1+k})},\dots,(-1)^{b(x^{i-1+k})})
    =\bfe_{i+k}
  \end{equation}
  (naturally, the index of~$\bfe_{i+k}$ is modulo~$m$).
  Equation~\eqref{eq:e_i''1} proves~(\textit{ii}).
  
  Equation~\eqref{eq:bfE_quasi-Hadamard} is an immediate consequence
  of~(\textit{i}) and~(\textit{ii}), and hence~(\textit{iii}) is clear.
  Finally, for~(\textit{iv}), it suffices to notice that~$\|\bfe_i\|=\sqrt m$
  for all~$i$ and that, from the above discussion, $\<\bfe_i,\bfe_{i'}\>=-1<0$
  for all~$i\neq i'$.  Therefore, Lemma~\ref{thm:lindsey} applies
  and~\eqref{eq:small_disc.E.RR} follows.
\end{proof}

Lemma~\ref{lem:bfE_lemma}(\textit{iv}) tells us that `rectangles' in the
matrix~$\bfE$ have small discrepancy (in the sense
of~\eqref{eq:small_disc.E.RR}).  We shall now deduce a similar result for
`triangles' in~$\bfE$, which will later be used to show that \textit{segments}
of~$E_m$ have small discrepancy.

\begin{lemma}
  \label{lem:Lindsey}
  Let~$A$ and~$B\subset[m]$ be given and suppose~$A=\{a_1,\dots,a_t\}$,
  $B=\{b_1,\dots,b_t\}$, where~$a_1<\dots<a_t$ and~$b_1<\dots<b_t$.  The
  following assertions hold for the matrix~$\bfE=(E_{ij})_{1\leq i,j\leq m}$.
  \begin{enumerate}
  \item[(\textit{i})]We have
    \begin{equation}
      \label{eq:Lindsey_trig}
      \Bigg|\sum_{i+j\leq t+1}E_{a_ib_j}\Bigg|
      \leq(t\log_2t+1)\sqrt m.
    \end{equation}
  \item[(\textit{ii})]Similarly,
    \begin{equation}
      \label{eq:Lindsey_trig2}
      \Bigg|\sum_{i+j\geq t+1}E_{a_ib_j}\Bigg|
      \leq(t\log_2t+1)\sqrt m.
    \end{equation}
  \end{enumerate}
\end{lemma}
\begin{proof}
  Inequality~\eqref{eq:Lindsey_trig} follows from
  Lemma~\ref{lem:bfE_lemma}(\textit{iv}), by induction on~$t$.  Note first
  that~\eqref{eq:Lindsey_trig} holds for~$t=1$.  Now suppose that~$t>1$ and
  that~\eqref{eq:Lindsey_trig} holds for smaller values of~$t$.  By the
  triangle inequality, we have
  \begin{equation}
    \label{eq:Lindsey_decomposition}
      \Bigg|\sum_{i+j\leq t+1}E_{a_ib_j}\Bigg|
      \leq\Bigg|\sum_{(i,j)\in S}E_{a_ib_j}\Bigg|
      +\Bigg|\sum_{(i,j)\in T_1}E_{a_ib_j}\Bigg|
      +\Bigg|\sum_{(i,j)\in T_2}E_{a_ib_j}\Bigg|,
  \end{equation}
  where~$S=\{(i,j)\:i,j\leq\lceil t/2\rceil\}$, $T_1=\{(i,j)\:i\leq\lceil
  t/2\rceil,\;j>\lceil t/2\rceil\}$, and $T_2=\{(i,j)\:j\leq\lceil
  t/2\rceil,\;i>\lceil t/2\rceil\}$.  We now estimate the three terms on the
  right-hand side of~\eqref{eq:Lindsey_decomposition} by
  using~\eqref{eq:small_disc.E.RR} and the induction hypothesis twice.  We
  have
  \begin{align}
    \label{eq:Lindsey_ind}
    \Bigg|\sum_{i+j\leq t+1}E_{a_ib_j}\Bigg|
    &\leq\llceil t\over2\rrceil\sqrt m
    +2\(\llfloor t\over2\rrfloor\log_2\llfloor t\over2\rrfloor+1\)\sqrt m
    \nonumber\\
    &\leq\llceil t\over2\rrceil\sqrt m+\(t(\log_2t-1)+2\)\sqrt m
    \nonumber\\
    &\leq(t\log_2t+1)\sqrt m+\llceil t\over2\rrceil\sqrt m
    -(t-1)\sqrt m\nonumber\\
    &\leq(t\log_2t+1)\sqrt m,
  \end{align}
  which completes the induction step, and~(\textit{i}) is proved.
  The proof of assertion~(\textit{ii}) is similar, and hence it is omitted. 
\end{proof}

We shall now show that segments of~$E_m$ have small discrepancy, in the sense
that they have the same number of~$1$s as~$-1$s, up to a small error.  We
observe that Corollary~\ref{cor:segment_discr} also considers segments
of~$E_m$ that ``wrap around'' the end of~$E_m$; equivalently, that result
considers~$E_m$ as a circular sequence.

\begin{corollary}
  \label{cor:segment_discr}
  For any~$1\leq r\leq m$ and~$2\leq k\leq m$, we have
  \begin{equation}
    \label{eq:segment_sum.full}
    \Bigg|\sum_{0\leq i<k}(-1)^{b(x^{r+i})}\Bigg|
    \leq\(\log_2k+\(1-{1\over k}\)\log_2(k-1)+{2\over k}\)\sqrt m.
  \end{equation}
  In particular, for all~$1\leq r\leq m$ and~$2\leq k\leq m$, we have
  \begin{equation}
    \label{eq:segment_sum}
    \Bigg|\sum_{0\leq i<k}(-1)^{b(x^{r+i})}\Bigg|
    \leq2(\log_2k)\sqrt m.
  \end{equation}
\end{corollary}
\begin{proof}
  Note that
  \begin{equation}
    \label{eq:segment_aux.1}
    \(1-{1\over k}\)\log_2(k-1)+{2\over k}\leq\log_2k
  \end{equation}
  if and only if
  \begin{equation}
    \label{eq:segment_aux.2}
    (k-1)^{1-1/k}2^{2/k}\leq k
  \end{equation}
  if and only if
  \begin{equation}
    \label{eq:segment_aux.3}
    \(1-{1\over k}\)^k\leq{1\over4}(k-1),
  \end{equation}
  which holds if~$k\geq3$.  Therefore, \eqref{eq:segment_sum}~follows directly
  from~\eqref{eq:segment_sum.full} for~$3\leq k\leq m$.  If~$k=2$,
  then~\eqref{eq:segment_sum} holds by inspection.  To
  prove~\eqref{eq:segment_sum.full}, we apply
  Lemma~\ref{lem:Lindsey}(\textit{i}) and~(\textit{ii}).  For the
  application of~(\textit{i}), we consider the sets~$A=\{1,2,\dots,k\}$,
  and~$B=\{r,r+1,\dots,r+k-1\}$, whereas for the application of~(\textit{ii})
  we consider~$A'=\{2,3,\dots,k\}$ and~$B'=\{r-k+1,r-k+2,\dots,r-1\}$.  Taking
  into account that~$\bfE=(E_{ij})$ is circulant, we deduce that
  \begin{multline}
    \label{eq:lozenge}
    k\sum_{0\leq i<k}(-1)^{b(x^{r+i})}
    =\sum\{E_{ab}\:a\in A,\;b\in B,\;a+b\leq k+r\}\\
    +\sum\{E_{a'b'}\:a'\in A',\;b'\in B',\;a'+b'\geq r+1\}
  \end{multline}
  (see Figure~\ref{fig:mx_bit}).  Therefore, by the triangle inequality, we
  have 
  \begin{figure}[t]
    \centering\small
    $$
    \begin{matrix}
      & & & &E_{1,r} &E_{1,r+1} &\dots &E_{1,r+k-1}\\
      & & &E_{2,r-1} &E_{2,r} & &\swdots &\\
      \vphantom{\sum_{\displaystyle\sum}^{\displaystyle\sum}}& &\swdots
      &\vdots &\vdots &\swdots & &\\ 
      &E_{k,r-k+1} &\dots &E_{k,r-1} &E_{k,r} & &&\\
    \end{matrix}
    $$
    \caption{Portion of the matrix~$\bfE$ to which
      Lemma~\ref{lem:Lindsey}(\textit{i}) and~(\textit{ii}) are applied.
      Note that  
      $E_{1,r}=E_{2,r-1}=\dots=E_{k,r-k+1}=(-1)^{b(x^r)}$,
      $E_{1,r+1}=E_{2,r}=\dots=E_{k,r-k+2}=(-1)^{b(x^{r+1})}$, etc.}  
    \label{fig:mx_bit}
  \end{figure}
  %
  \begin{multline}
    \label{eq:lozenge_trig}
    k\Bigg|\sum_{0\leq i<k}(-1)^{b(x^{r+i})}\Bigg|
    \leq\Bigg|\sum\{E_{ab}\:a\in A,\;b\in B,\;a+b\leq k+r\}\Bigg|\\
    +\Bigg|\sum\{E_{a'b'}\:a'\in A',\;b'\in B',\;a'+b'\geq r+1\}\Bigg|\\
    \leq(k\log_2k+1)\sqrt m+\((k-1)\log_2(k-1)+1\)\sqrt m,
  \end{multline}
  and~\eqref{eq:segment_sum.full} follows on dividing~\eqref{eq:lozenge_trig}
  by~$k$.
\end{proof}

The next lemma states that the number of occurrences of shorter words
in~$\tE_m$ is basically equal to the expectation of this number in the case of
the random sequence of length~$m$.  To state this precisely, we introduce some
notation.  Let~$1\leq k\leq s$ be fixed.  For all~$1\leq r\leq m$,
let~$\tE_m^{(r)}$ denote the segment of~$\tE_m$ of length~$k$ starting at its
$r$th letter, that is,
\begin{equation}
  \label{eq:tE_m(r)}
  \tE_m^{(r)}=(b(x^r),b(x^{r+1}),\dots,b(x^{r+k-1}))
\end{equation}
($\tE_m$~is considered as a cyclic sequence).  Now, for all~$X\in\{0,1\}^k$,
let~$f_X=f_X(\tE_m)$ denote the number of occurrences of~$X$ as a segment
in~$\tE_m$, where we consider~$\tE_m$ as a cyclic sequence; that is,
\begin{equation}
  \label{eq:f_X_def}
  f_X=\card\{r\:1\leq r\leq m\text{ and }\tE_m^{(r)}=X\}.
\end{equation}

\begin{lemma}
  \label{lem:de_Bruijn}
  For all~$1\leq k\leq s$, we have
  \begin{equation}
    \label{eq:f_X_constant}
    f_X=f_X(\tE_m)=
    \begin{cases}
      (m+1)2^{-k}-1=2^{s-k}-1&\text{if $X=(0,\dots,0)\in\{0,1\}^k$}\\
      (m+1)2^{-k}=2^{s-k}&\text{otherwise}.\\
    \end{cases}
  \end{equation}
\end{lemma}
\begin{proof}
  Let~$1\leq r\leq m$ and~$\bfdelta=(\delta_i)_{1\leq i\leq k}\in\{0,1\}^k$ be
  given.  Note that
  \begin{equation}
    \label{eq:value_delta_func}
    \<\bfdelta,\tE_m^{(r)}\>=\sum_{1\leq i\leq k}\delta_ib(x^{r+i-1})
    =b\Bigg(x^r\sum_{1\leq i\leq k}\delta_ix^{i-1}\Bigg).
  \end{equation}
  We shall now use the fact that~$x$ does not satisfy a polynomial
  over~$\FF_2$ of degree less than~$s$ (indeed, if~$p(x)=0$ for a
  polynomial~$p$ over~$\FF_2$ of degree~$t$, then a standard argument shows
  that~$1,x,\dots,x^{t-1}$ spans~$\FF_{2^s}$ as a vector space over~$\FF_2$
  and hence~$\deg(p)=t\geq s$).  We use this fact
  in~\eqref{eq:value_delta_func}: as~$k\leq s$, we see that~$\sum_{1\leq i\leq
    k}\delta_ix^{i-1}\neq0$ as long as~$\bfdelta\neq(0,\dots,0)$, and hence
  this sum is~$x^t$ for some~$1\leq t\leq m$ independent of~$r$.  Therefore,
  $\<\bfdelta,\tE_m^{(r)}\>=b(x^{r+t})$, and we have
  \begin{equation}
    \label{eq:system_eq}
    \sum_{1\leq r\leq m}(-1)^{\<{\bfdelta},\tE_m^{(r)}\>}
    =\sum_{1\leq r\leq m}(-1)^{b(x^{r+t})}=-1
  \end{equation}
  by Lemma~\ref{lem:bfE_lemma}(\textit{i}), since we have
  in~\eqref{eq:system_eq} above the sum of the entries of the $(t+1)$st row
  of~$\bfE$.  If~$\bfdelta=(0,\dots,0)$, then clearly the sum
  in~\eqref{eq:system_eq} is~$m$.
  
  Let us now observe that the left-hand side of~\eqref{eq:system_eq} may also
  be written as
  \begin{equation}
    \label{eq:system_eq_clear}
    \sum_X(-1)^{\<\bfdelta,X\>}f_X,
  \end{equation}
  where the sum is over all~$X\in\{0,1\}^k$.  Therefore, we have established a
  system of~$2^k$ linear equation for the~$f_X$ ($X\in\{0,1\}^k$):
  \begin{equation}
    \label{eq:full_system}
    \sum_{X\in\{0,1\}^k}(-1)^{\<\bfdelta,X\>}f_X=
    \begin{cases}
      m&\text{if~$\delta=(0,\dots,0)\in\{0,1\}^k$}\\
      -1&\text{otherwise}.
    \end{cases}
  \end{equation}
  The matrix associated to the system of equations~\eqref{eq:full_system} is
  the $2^k\times2^k$ Hadamard
  matrix~$\bfH_k=[(-1)^{\<\bfdelta,X\>}]_{\bfdelta,X\in\{0,1\}^k}$.  For
  convenience, let~$\bff=(f_X)_{X\in\{0,1\}^k}$ and
  let~$\bfg=(g_\bfdelta)_{\bfdelta\in\{0,1\}^k}$, where~$g_\bfdelta=m$
  if~$\bfdelta=(0,\dots,0)$ and~$g_\bfdelta=-1$ otherwise.
  Then~\eqref{eq:full_system} may be written as
  \begin{equation}
    \label{eq:system_mx}
    \bfH_k\bff=\bfg.
  \end{equation}
  Now, since
  \begin{equation}
    \label{eq:Hadamard}
    \sum_{\delta\in\{0,1\}^k}(-1)^{\<\delta,X\>}(-1)^{\<\delta,Y\>}\\
    =\sum_{\delta\in\{0,1\}^k}(-1)^{\<\delta,X\sdiff Y\>}=0 
  \end{equation}
  if~$X\neq Y$, we have
  \begin{equation}
    \label{eq:H_k_prop}
    \bfH_k^T\bfH_k=2^k\bfI,
  \end{equation}
  where, naturally, $\bfI$~is the $2^k\times 2^k$ identity matrix.  Therefore,
  from~\eqref{eq:system_mx} and~\eqref{eq:H_k_prop} we have
  \begin{equation}
    \label{eq:system_solution}
    2^k\bff=\bfH_k^T\bfH_k\bff=\bfH_k^T\bfg.
  \end{equation}
  The last product in~\eqref{eq:system_solution} may be computed explicitly,
  and one obtains that 
  \begin{equation}
    \label{eq:system_solution_aux}
    \bfH_k^T\bfg=
    \begin{bmatrix}
      m-2^k+1\\
      m+1\\
      \vdots\\
      m+1
    \end{bmatrix},
  \end{equation}
  where the entry~$m-2^k+1$ corresponds to~$X=(0,\dots,0)$.
  Equation~\eqref{eq:f_X_constant} now follows from~\eqref{eq:system_solution}
  and~\eqref{eq:system_solution_aux}.
\end{proof}

Setting~$k=s$ in Lemma~\ref{lem:de_Bruijn}, we see that words of length~$s$
occur in~$\tE_m$ at most once.  Since every occurrence of a word of length at
least~$s$ gives us an occurrence of its prefix of length~$s$, we conclude that
words longer than~$s$ occur no more than once in~$\tE_m$.  We thus have the
following corollary to Lemma~\ref{lem:de_Bruijn}, to be used later in the
proof of Theorem~\ref{thm:small_cN}.

\begin{corollary}
  \label{cor:long_segments}
  Suppose~$\ell\geq s=\log_2(m+1)$.  Any~$Y\in\{0,1\}^\ell$ occurs at most
  once in~$\tE_m$, even considering~$\tE_m$ as cyclic sequence; that is,
  \begin{equation}
    \label{eq:long_segments}
    \card\{r\:1\leq r\leq m\text{ and
    }(b(x^r),\dots,b(x^{r+\ell-1}))=Y\}\leq1. 
  \end{equation}
\end{corollary}
% \begin{proof}
%   Let~$\ell$ and~$Y$ be as in the statement of our corollary.  Let~$Y_s$ be
%   the prefix of~$Y$ of length~$s$.  Observe that Lemma~\ref{lem:de_Bruijn}
%   implies that~$f_{Y_s}\leq1$, that is, $Y_s$~occurs at most once in~$\tE_m$.
%   Clearly, this implies that~$Y$ occurs at most once in~$\tE_m$, as claimed.   
% \end{proof}

As it turns out, not only has~$\tE_m$ the property that shorter words occur
evenly in it (as shows Lemma~\ref{lem:de_Bruijn}), but~$\tE_m$ has this
property on its longer \textit{segments} (in a weaker sense): for~$k\leq
s=\log_2(m+1)$, every $k$-letter word~$X\in\{0,1\}^k$ occurs roughly~$n2^{-k}$
times in any segment of~$\tE_m$ of length~$n$, as long as~$n$ is reasonably
large.

To make the above statement precise, we introduce some notation.  Let~$1\leq
r\leq m$ and~$1\leq n\leq m$ be given.  Let~$\tE_m^{(r,n)}$ be the segment
of~$\tE_m$ of length~$n$ starting at the~$r$th letter of~$\tE_m$, that is, set
\begin{equation}
  \label{eq:tE_m_rn-segment_def}
  \tE_m^{(r,n)}=(b(x^r),b(x^{r+1}),\dots,b(x^{r+n-1})).
\end{equation}
Now let~$1\leq k\leq s$.  We shall be interested in the
segments~$\tE_m^{(t,k)}$ of length~$k$ of~$\tE_m$, for~$r\leq t<r+n$.
% \begin{equation}
%   \label{eq:tE_m_tk-segment_def}
%   \tE_m^{(t,k)}=(b(x^t),b(x^{t+1}),\dots,b(x^{t+k-1})).
% \end{equation}
For~$X\in\{0,1\}^k$, set
\begin{equation}
  \label{eq:f_X_def2}
  f_X=f_X(\tE_m^{(r,n)})
  =\card\{t\:r\leq t<r+n\text{ and }\tE_m^{(t,k)}=X\}.
\end{equation}
In what follows, we write~$O_1(a)$ for any term~$b$ such that~$|b|\leq a$.  We
are now ready to state our lemma on the frequency of words in segments
of~$\tE_m$. 

\begin{lemma}
  \label{lem:segment_de_Bruijn}
  For any~$1\leq r\leq m$, $2\leq n\leq m$, and~$1\leq k\leq s$, we have
  \begin{equation}
    \label{eq:segment_de_Bruijn}
    f_X=f_X(\tE_m^{(r,n)})=n2^{-k}+O_1\(2(\log_2n)\sqrt m\)
  \end{equation}
  for all~$X\in\{0,1\}^k$.
\end{lemma}

The proof of Lemma~\ref{lem:segment_de_Bruijn} will be similar to the proof of
Lemma~\ref{lem:de_Bruijn}, except that we shall now make use of
Corollary~\ref{cor:segment_discr}, instead of using the fact that the sum of
the entries of the whole sequence~$E_m$ is~$-1$.

\begin{proof}[Proof of Lemma~\ref{lem:segment_de_Bruijn}]
  Let~$\bfdelta=(\delta_i)_{1\leq i\leq k}\in\{0,1\}^k$ be fixed.  As before,
  we have
  \begin{equation}
    \label{eq:value_delta_func2}
    \<\bfdelta,\tE_m^{(t,k)}\>=\sum_{1\leq i\leq k}\delta_ib(x^{t+i-1})
    =b\Bigg(x^t\sum_{1\leq i\leq k}\delta_ix^{i-1}\Bigg)
    =b(x^{t+u}),
  \end{equation}
  for some~$1\leq u\leq m$ independent of~$t$.  Therefore, by
  Corollary~\ref{cor:segment_discr}, 
  \begin{multline}
    \label{eq:small_func_value}
    \Bigg|\sum_{X\in\{0,1\}^k}(-1)^{\<\bfdelta,X\>}f_X\Bigg|
    =\Bigg|\sum_{r\leq t<r+n}(-1)^{\<\bfdelta,\tE_m^{(t,k)}\>}\Bigg|\\
    =\Bigg|\sum_{r\leq t<r+n}(-1)^{b(x^{t+u})}\Bigg|
    \leq2(\log_2n)\sqrt m.
  \end{multline}
  As before, let~$\bfH_k$ be the $2^k\times2^k$ Hadamard
  matrix~$[(-1)^{\<\bfdelta,X\>}]_{\bfdelta,X\in\{0,1\}^k}$, and
  let~$\bff=(f_X)_{X\in\{0,1\}^k}$.  If~$\bfg=\bfH_k\bff$
  and~$\bfg=(g_\bfdelta)_{\bfdelta\in\{0,1\}^k}$,
  then~\eqref{eq:small_func_value} implies that
  \begin{equation}
    \label{eq:g_0=n}
    g_\bfdelta=
    \begin{cases}
      n&\text{if~$\bfdelta=(0,\dots,0)$}\\
      O_1\(2(\log_2n)\sqrt m\)&\text{otherwise}.
    \end{cases}
  \end{equation}
  Using that~$\bfH_k^T\bfH_k=2^k\bfI$, we have
  \begin{equation}
    \label{eq:inversion2}
    \bff=2^{-k}\bfH_k^T\bfH_k\bff=2^{-k}\bfH_k^T\bfg.
  \end{equation}
  One may easily observe that the entries of~$\bfH_k^T\bfg$ are all equal
  to
  \begin{equation}
    \label{eq:about_n}
    n+O_1\(2^{k+1}(\log_2n)\sqrt m\).
  \end{equation}
  The asserted conclusion~\eqref{eq:segment_de_Bruijn} follows
  from~\eqref{eq:inversion2} and~\eqref{eq:about_n}. 
\end{proof}

\subsubsection{Proof of Theorems~\ref{cor:cN_upbd} and~\ref{thm:small_cN}} 
\label{sec:proof_of_Normality}
We shall prove Theorem~\ref{thm:small_cN} using Lemmas~\ref{lem:de_Bruijn}
and~\ref{lem:segment_de_Bruijn} and Corollary~\ref{cor:long_segments}, whereas
we shall deduce Theorem~\ref{cor:cN_upbd} from Theorem~\ref{thm:small_cN} by
making a suitable choice for~$q$ and~$m$ in the construction of~$E_N$.  Let us
start with the proof of Theorem~\ref{thm:small_cN}.

\begin{proof}[Proof of Theorem~\ref{thm:small_cN}]
  Let~$E_N$ be as defined in~\eqref{eq:cN.E_N_def}, and let~$X\in\{-1,1\}^k$
  with~$1\leq k\leq\log_2N$ be given.  Let~$1\leq M\leq N-k+1$ and let us
  compute~$T(E_N,M,X)$; our aim is to compare~$T(E_N,M,X)$ and~$M2^{-k}$.
  
  We first suppose~$k\leq s$, so that we may apply Lemmas~\ref{lem:de_Bruijn}
  and~\ref{lem:segment_de_Bruijn}.  
  
  Let~$M=\alpha m+\beta$, where~$\alpha$ and~$\beta$ are integers
  with~$0\leq\beta<m$.  Clearly, $0\leq\alpha\leq q$.
%  We shall treat the cases~$\beta=0$ and~$\beta=1$ separately.
  We use the following notation below, for conciseness: if~$P$ is some
  property, then~$[P]=0$ if~$P$ is false and~$[P]=1$ if~$P$ is true.
  
  By definition~\eqref{eq:T_def}, we have~$T(E_m,\beta,X)\leq\beta$.  Suppose
  for a moment that~$\beta\geq2$.  Then, by Lemma~\ref{lem:segment_de_Bruijn}
  applied with~$r=1$ and~$n=\beta\geq2$, we have
  \begin{align}
    T(E_m,\beta,X)&\leq\beta2^{-k}+2(\log_2\beta)\sqrt m\nonumber\\ 
    &\leq\beta2^{-k}+2(\log_2(m-1))\sqrt m.\label{eq:Tengan.1}
  \end{align}
  As~$m=2^s-1\geq3$, the upper bound~\eqref{eq:Tengan.1} for~$T(E_m,\beta,X)$
  does hold for~$\beta=0$ and~$\beta=1$ as well.  Lemma~\ref{lem:de_Bruijn}
  tells us that~$T(E_m,m,X)\leq(m+1)2^{-k}-[X=\bfone]$ (note that the
  `exceptional' sequence in~\eqref{eq:f_X_constant}, which
  concerns~$\tE_m\in\{0,1\}^m$, is the zero sequence~$\bfzero\in\{0,1\}^k$,
  which translates to the all~$1$ sequence~$\bfone\in\{-1,1\}^k$ when
  considering~$E_m\in\{-1,1\}^m$).  We conclude from this
  and~\eqref{eq:Tengan.1} that
  \begin{align}
    \label{eq:general_upbd}
    &T(E_N,M,X)=\alpha T(E_m,m,X)+T(E_m,\beta,X)\nonumber\\
    &\qquad\quad\leq\alpha(m2^{-k}+2^{-k}-[X=\bfone])
    +\beta2^{-k}+2(\log_2(m-1))\sqrt m\nonumber\\
    &\qquad\quad=\alpha m2^{-k}+\beta2^{-k}+\alpha(2^{-k}-[X=\bfone])
    +2(\log_2(m-1))\sqrt m\nonumber\\
    &\qquad\quad\leq M2^{-k}+q%\alpha(2^{-k}-[X=\bfone])
    +2(\log_2(m-1))\sqrt m. 
  \end{align}
  Similarly, by Lemmas~\ref{lem:de_Bruijn} and~\ref{lem:segment_de_Bruijn}, we
  have
  \begin{align}
    \label{eq:general_lwbd}
    &T(E_N,M,X)=\alpha T(E_m,m,X)+T(E_m,\beta,X)\nonumber\\
    &\qquad\quad\geq\alpha(m2^{-k}+2^{-k}-[X=\bfone])
    +\beta2^{-k}-2(\log_2(m-1))\sqrt m\nonumber\\ 
    &\qquad\quad=\alpha m2^{-k}+\beta2^{-k}+\alpha(2^{-k}-[X=\bfone])
    -2(\log_2(m-1))\sqrt m\nonumber\\
    &\qquad\quad\geq M2^{-k}-q-2(\log_2(m-1))\sqrt m.
                                %\alpha(2^{-k}-[X=\bfone])
  \end{align}
  From~\eqref{eq:general_upbd} and~\eqref{eq:general_lwbd}, we have
  \begin{equation}
    \label{eq:discr_general_beta}
    \left|T(E_N,M,X)-{M\over2^k}\right|
    \leq q+2(\log_2(m-1))\sqrt m.
  \end{equation}
  We have thus completed the analysis for the case in which~$k\leq s$.
  Suppose now that~$k>s$.  Recall that Corollary~\ref{cor:long_segments} tells
  us that, in this case, $X$~occurs in~$E_m$ at most once, that is,
  $T(E_m,m,X)\leq1$ and hence~$0\leq T(E_N,M,X)\leq q$.  Note also that
  \begin{equation}
    \label{eq:small_exp}
    0\leq{M\over2^k}\leq{N\over2^{s+1}}={N\over2(m+1)}<{1\over2}q.
  \end{equation}
  Therefore,
  \begin{equation}
    \label{eq:discr_large_k}
    \left|T(E_N,M,X)-{M\over2^k}\right|
    \leq q.%+{1\over2}q={3\over2}q.
  \end{equation}
  Inequality~\eqref{eq:small_cN} follows from~\eqref{eq:discr_general_beta}
  and~\eqref{eq:discr_large_k}.
\end{proof}

We shall now prove Theorem~\ref{cor:cN_upbd}.

\begin{proof}[Proof of Theorem~\ref{cor:cN_upbd}]
  Let an integer~$N$ be given.  In what follows, we may suppose that~$N$ is
  suitably large for our inequalities to hold.  We start by choosing an
  integer~$s$ so that~$m=2^s-1$ satisfies
  \begin{equation}
    \label{eq:m_def}
    {14\over17}\(N\over\log_2N\)^{2/3}\leq
    m\leq{5\over3}\(N\over\log_2N\)^{2/3}.  
  \end{equation}
  We now let
  \begin{equation}
    \label{eq:q_def}
    q=\llfloor{11\over9}N^{1/3}(\log_2N)^{2/3}\rrfloor,
  \end{equation}
  set~$N'=qm$, and consider~$E_{N'}=E_m\dots E_m=E_m^q$.  We have
  \begin{equation}
    \label{eq:N'_lwbd}
    N'=qm\geq\llfloor{11\over9}N^{1/3}(\log_2N)^{2/3}\rrfloor
    \times{14\over17}\(N\over\log_2N\)^{2/3}\geq N
  \end{equation}
  for all large enough~$N$.  We let~$E_N$ be the prefix of~$E_{N'}$ of
  length~$N$.  
  
  We claim that~$E_N$ satisfies~\eqref{eq:cN_lwbd}.  Clearly, it suffices to
  show that~$E_{N'}$ is such
  that~$\cN(E_{N'})\leq3N^{1/3}(\log_2N)^{2/3}$.  To prove this last
  inequality, we simply show that the right-hand side of~\eqref{eq:small_cN}
  is at most~$3N^{1/3}(\log_2N)^{2/3}$.

  We have
  \begin{equation}
    \label{eq:log_lwbd}
    \log_2(m-1)<\log_2\({5\over3}\(N\over\log_2N\)^{2/3}\)
    <{2\over3}\log_2N.
  \end{equation}
  Moreover, 
  \begin{equation}
    \label{eq:sqrt_lwbd}
    \sqrt m\leq\({5\over3}\(N\over\log_2N\)^{2/3}\)^{1/2}
    <{31\over24}\(N\over\log_2N\)^{1/3}
  \end{equation}
  for all large enough~$N$.  Therefore,
  \begin{multline}
    \label{eq:larger_term_in_max}
    q+2(\log_2(m-1))\sqrt m
    <{11\over9}N^{1/3}(\log_2N)^{2/3}
    +{31\over18}(\log_2N)\(N\over\log_2N\)^{1/3}\\
    <3N^{1/3}(\log_2N)^{2/3},
  \end{multline}
  implying that the right-hand side of~\eqref{eq:small_cN} is at
  most~$3N^{1/3}(\log_2N)^{2/3}$, as required.
\end{proof}

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

\subsection{Larger alphabets}
\label{sec:larger_alph}
We now sketch a generalization of the construction in
Section~\ref{sec:the_construction} to alphabets of cardinality larger
than~$2$.  As it turns out, the construction generalizes easily to alphabets
of cardinality that are powers of primes.

Let~$s$ be a positive integer and $q$~a power of a prime, and
let~$\FF_{q^s}=\GF(q^s)$ be the finite field with~$q^s$ elements.  Fix a
primitive element~$x\in\FF_{q^s}^*$, and let~$m=|\FF_{q^s}^*|=q^s-1$.  We
consider~$\FF_{q^s}$ as a vector space over~$\FF_q$, and fix a non-zero linear
functional
\begin{equation}
  \label{eq:b_def.App}
  b\:\FF_{q^s}\to\FF_q.
\end{equation}
Let~$\psi\:\FF_q\to S^1\subset\CC$ be an additive character
with~$\card\{\psi(y)\:y\in\FF_q\}=q$ (that is, we take~$\psi$ injective), and
put
\begin{equation}
  \label{eq:cN.tE_m_def.App}
  \tE_m=(b(x),b(x^2),\dots,b(x^m))\in\FF_q^m
\end{equation}
and 
\begin{equation}
  \label{eq:cN.E_m_def.App}
  E_m=(\psi(b(x)),\psi(b(x^2)),\dots,\psi(b(x^m)))
  \in(S^1)^m.
\end{equation}
Finally, set
\begin{equation}
  \label{eq:cN.E_N_def.App}
  E_N=E_m^\ell=E_m\dots E_m\qquad\text{($\ell$~factors)},
\end{equation}
where~$E_m^\ell$ denotes the concatenation of~$\ell$ copies of~$E_m$; clearly,
$E_N$~has length~$N=\ell m$.  The sequence~$E_N$, considered as a word over
the $q$-letter alphabet
\begin{equation}
  \label{eq:q_alphabet}
  \Sigma_q=\{\psi(y)\:y\in\FF_q\},
\end{equation}
is such that
\begin{equation}
  \label{eq:cNm_small}
  \cN^{(q)}(E_N)=O\(N^{1/3}(\log N)^{2/3}\),
\end{equation}
where
\begin{equation}
  \label{eq:N.m_def}
  \cN^{(q)}(E_N)=\max_k\max_X\max_M
  \left|T(E_N,M,X)-{M\over q^k}\right|,
\end{equation}
and the maxima are taken over all~$1\leq k\leq\log_qN$, $X\in\Sigma_q^k$,
and~$0<M\leq N+1-k$.

Let us sketch the proof of~\eqref{eq:cNm_small}.  This time, we let
\begin{equation}
  \label{eq:bfE_def.App}
  \bfE=(E_{ij})_{1\leq i,j\leq m}=
  \begin{bmatrix}
    \psi(b(x)) &\psi(b(x^2)) &\dots &\psi(b(x^m))\\
    \psi(b(x^2)) &\psi(b(x^3)) &\dots &\psi(b(x))\\
    \vdots &\vdots &\ddots &\vdots\\
    \psi(b(x^m)) &\psi(b(x)) &\dots &\psi(b(x^{m-1}))
  \end{bmatrix}.
\end{equation}
Then~$\bfE$~is an $m\times m$ circulant, complex matrix whose first row
is~$E_m$.  Again, let~$\bfe_i=(E_{ij})_{1\leq j\leq m}$ ($1\leq i\leq m$)
denote the $i$th row of~$\bfE$.  Moreover, if~$\bfv=(v_j)_{1\leq j\leq m}$
and~$\bfw=(w_j)_{1\leq j\leq m}$ are two complex $m$-vectors,
let~$\bfv\circ\bfw$ denote the $m$-vector~$(v_j\overline{w_j})_{1\leq j\leq
  m}$, where~$\overline z$ denotes the complex conjugate of~$z\in\CC$.

It turns out that Lemma~\ref{lem:bfE_lemma} generalizes to the the
matrix~$\bfE$ defined in~\eqref{eq:bfE_def.App}, in the following way.

\begin{lemma}
  \label{lem:bfE_lemma.gen}
  The following hold for~$\bfE${\rm:}
  \begin{enumerate}
  \item[(\textit{i})]Every row of~$\bfE$ adds up to~$-1$, that is,
    $\sum_{1\leq j\leq m}E_{ij}=-1$ for all~$1\leq i\leq m$.
  \item[(\textit{ii})]For all~$i\neq i'$ $(1\leq i,i'\leq m)$, we
    have~$\bfe_i\circ\bfe_{i'}=\bfe_{i''}$ for some~$1\leq i''\leq m$.
%    where~$\bar\bfe_{i'}=(\bar E_{ij})_{1\leq j\leq m}$ is the $i'$th row
%    of~$\bfE$ with its entries replaced by their complex conjugates.
  \item[(\textit{iii})]The matrix~$\bfE$ satisfies
    \begin{equation}
      \label{eq:bfE_quasi-Hadamard.App.gen}
      \bfE\bfE^*=-\bfJ+(m+1)\bfI,
    \end{equation}
    where~$\bfE^*$ is the adjoint of~$\bfE$.
   \item[(\textit{iv})]For all~$A$ and~$B\subset[m]$, we have
     \begin{equation}
       \label{eq:small_disc.E.CC}
       \bigg|\sum_{a\in A,\,b\in B}E_{ab}\bigg|\leq\sqrt{m|A||B|}.
     \end{equation}
  \end{enumerate}
\end{lemma}

Lemma~\ref{lem:bfE_lemma.gen}(\textit{i})--(\textit{iii}) may be checked
easily.  For Lemma~\ref{lem:bfE_lemma.gen}(\textit{iv}), one observes that
Lemma~\ref{thm:lindsey} may be generalized in a natural way to complex
matrices, with exactly the same proof.

\begin{lemma}
  \label{thm:lindsey.CC}
  Let~$H=(h_{ij})_{1\leq i,j\leq M}$ be an $M$~by~$M$ complex matrix and
  let~$\bfv_i$ be the $i$th row of~$H$ $(1\leq i\leq M)$.  Let~$A$,
  $B\subset[M]$ be given, and suppose that
  \begin{equation}
    \label{eq:row_norm.CC}
    \|\bfv_a\|=\sqrt{\sum_{1\leq j\leq m}|h_{aj}|^2}\leq\sqrt m
  \end{equation}
  for all~$a\in A$ and
  \begin{equation}
    \label{eq:neg_scalar.CC}
    \<\bfv_a,\bfv_{a'}\>=\sum_{1\leq b\leq m}h_{ab}\overline{h_{a'b}}\leq0
  \end{equation}
  for all~$a\neq a'$ with~$a$, $a'\in A$.  Then
  \begin{equation}
    \label{eq:lindsey_thm.CC}
    \bigg|\sum_{a\in A,\,b\in B}h_{ab}\bigg|\leq\sqrt{m|A||B|}.
  \end{equation}
\end{lemma}

To prove Lemma~\ref{lem:bfE_lemma.gen}(\textit{iv}), one applies
Lemma~\ref{thm:lindsey.CC} to the matrix~$\bfE$ given
in~\eqref{eq:bfE_def.App}.  The remainder of the argument is as before, with
some small changes.  The $2^k\times2^k$ Hadamard
matrix~$\bfH_k=[(-1)^{\<\bfdelta,X\>}]_{\bfdelta,X\in\{0,1\}^k}$ that occurs
later in the proof should be replaced by the $q^k\times q^k$
matrix~$\bfH_k=[\psi(\<\bfdelta,X\>)]_{\bfdelta,X}$, where~$\bfdelta$ and~$X$
vary over~$\FF_q^k$, which is a unitary matrix, up to a multiplicative
constant: $\bfH_k\bfH_k^*=mI$.  We omit the details.

\subsection{The P\'olya--Vinogradov inequality}
\label{sec:Polya-Vinogradov}
Let~$p$ be a prime and let~$\chi\:\FF_p=\ZZ/p\ZZ\to S^1\subset\CC$ be a
multiplicative character, where, as usual, $\chi(0)=0$.  With the methods in
Section~\ref{sec:auxiliary} (and Lemma~\ref{thm:lindsey.CC} above) one may
easily prove the celebrated P\'olya--Vinogradov inequality, in the following
form.

\begin{theorem}
  \label{thm:Polya-Vinogradov}
  For all integers~$r$ and~$2\leq k\leq p$, we have
  \begin{equation}
    \label{eq:Polya-Vinogradov}
    \Big|\sum_{0\leq h<k}\chi(r+h)\Big|\leq2(\log_2k)\sqrt{p-1}.
  \end{equation}
\end{theorem}

We give an outline of the proof of Theorem~\ref{thm:Polya-Vinogradov}.  This
time, we let~$\bfE=(e_{ij})_{i,j}=(\chi(i-j))_{0\leq i,j<p}$.  Note
that~$\bfE$ is circulant: $e_{00}=e_{11}=e_{22}=\cdots$,
$e_{01}=e_{12}=e_{23}=\cdots$, $e_{10}=e_{21}=e_{32}\cdots$, etc.  The
rows~$\bfv_i$ ($0\leq i<p$) of~$\bfE$ have Euclidean norm~$\sqrt{p-1}$.
Moreover,  one may check that 
\begin{equation}
  \label{eq:neg_scalar.App}
  \<\bfv_i,\bfv_{i'}\>=-1
\end{equation}
for all~$i\neq i'$.  Indeed, 
\begin{multline}
  \label{eq:obtuse}
  \<\bfv_i,\bfv_{i'}\>
  =\sum_{0\leq j<p}\chi(i-j)\overline{\chi(i'-j)}
  =\sum_{0\leq j<p,\;j\neq i,\,i'}\chi\(i-j\over i'-j\)\\
  =\sum_{0\leq j<p,\;j\neq i,\,i'}\chi\(1-{i'-i\over i'-j}\).
\end{multline}
As~$j$ varies over~$\FF_p\setminus\{i,i'\}$, the argument~$1-(i'-i)/(i'-j)$
of~$\chi$ in the last term in~\eqref{eq:obtuse} varies
over~$\FF_p\setminus\{0,1\}$.  Since~$\chi(1)=1$ and~$\sum_{0\leq
  j<p}\chi(j)=0$, we conclude from~\eqref{eq:obtuse}
that~\eqref{eq:neg_scalar.App} does indeed hold.

Therefore, by Lemma~\ref{thm:lindsey.CC}, we have
\begin{equation}
  \label{eq:small_disc.E.quad.PV}
  \bigg|\sum_{a\in A,\,b\in B}\chi(a-b)\bigg|\leq\sqrt{(p-1)|A||B|}
\end{equation}
for all~$A$ and~$B\subset\{0,\dots,p-1\}$.  Theorem~\ref{thm:Polya-Vinogradov}
now follows from~\eqref{eq:small_disc.E.quad.PV} in the same way
that~\eqref{eq:segment_sum} follows from~\eqref{eq:small_disc.E.RR} (and the
fact that~$\bfE$ is circulant).

\section*{Acknowledgements}
\label{sec:acknowledgements}
The authors are grateful to Eduardo Tengan and Norihide Tokushige for their
careful reading of this paper and for their many comments.  The authors are
also most pleased to thank the referee for his or her very meticulous work.

%========================= references ========================================
\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{alon03:_measur_typical}
N.~Alon, Y.~Kohayakawa, C.~Mauduit, C.~G. Moreira, and R{\"o}dl, \emph{Measures
  of pseudorandomness for finite sequences: typical values}, in preparation.

\bibitem{alon:_probl_part_i}
Noga Alon, \emph{Problems and results in extremal combinatorics. {I}}, Discrete
  Math. \textbf{273} (2003), no.~1-3, 31--53, EuroComb'01 (Barcelona).
  \MR{2005a:05208}

\bibitem{carpi04:_unifor}
Arturo Carpi and Aldo de~Luca, \emph{Uniform words}, Adv. in Appl. Math.
  \textbf{32} (2004), no.~3, 485--522. \MR{2005a:68164}

\bibitem{cassaigne02}
Julien Cassaigne, Christian Mauduit, and Andr{\'a}s 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{codenotti00:_some}
Bruno Codenotti, Pavel Pudl{\'a}k, and Giovanni Resta, \emph{Some structural
  properties of low-rank matrices related to computational complexity},
  Theoret. Comput. Sci. \textbf{235} (2000), no.~1, 89--107, Selected papers in
  honor of Manuel Blum (Hong Kong, 1998). \MR{2001e:05078}

\bibitem{bruijn46}
N.~G. de~Bruijn, \emph{A combinatorial problem}, Nederl. Akad. Wetensch., Proc.
  \textbf{49} (1946), 758--764, (Indagationes Math. {\bf 8} (1946), 461--467).
  \MR{8,247d}

\bibitem{erd74:_probab}
Paul Erd{\H{o}}s and Joel 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{haselgrove51:_some}
C.~B. Haselgrove, \emph{Some theorems in the analytic theory of numbers}, J.
  London Math. Soc. \textbf{26} (1951), 273--277. \MR{13,438e}

\bibitem{macwilliams77II}
F.~J. MacWilliams and N.~J.~A. Sloane, \emph{The theory of error-correcting
  codes. {II}}, North-Holland Publishing Co., Amsterdam, 1977, North-Holland
  Mathematical Library, Vol. 16. \MR{57 \#5408b}

\bibitem{mauduit02:_finit}
Christian 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}
Christian Mauduit and Andr{\'a}s 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{tietaevaeinen80:_bound_plotk}
Aimo Tiet{\"a}v{\"a}inen, \emph{Bounds for binary codes just outside the
  {P}lotkin range}, Inform. and Control \textbf{47} (1980), no.~2, 85--93.
  \MR{83f:94042}

\end{thebibliography}

%=============================================================================

\end{document}

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