
\documentstyle[11pt]{article}
 
% DINA4-Format
\oddsidemargin 6pt\evensidemargin 6pt\marginparwidth 48pt\marginparsep 10pt
\topmargin -18pt\headheight 12pt\headsep 25pt\footheight 12pt\footskip 30pt
\textheight 625pt\textwidth 431pt\columnsep 10pt\columnseprule 0pt

\sloppy

% Dirty trick to avoid italic in theorems
\catcode`@=11
\def\@begintheorem#1#2{\trivlist \item[\hskip \labelsep{\bf #1\ #2.}]}
\def\@opargbegintheorem#1#2#3{\trivlist
      \item[\hskip \labelsep{\bf #1\ #2.\ (#3)}]}
\catcode`@=12


\newenvironment{rem}{\vspace{3mm}\noindent{\bf Remark. }}{\vspace{3mm}}
\newenvironment{claim}{\vspace{3mm}\noindent{\bf Claim. }}{\vspace{3mm}}
\newtheorem{Theorem}{Theorem}[section]
\newtheorem{Lemma}[Theorem]{Lemma}
\newtheorem{Cor}[Theorem]{Corollary}
\newtheorem{Def}[Theorem]{Definition}
\newtheorem{Prop}[Theorem]{Proposition}
 
\newcommand{\theorem}[1]{\begin{Theorem} #1 \end{Theorem}}
 
\newcommand{\theoremcite}[2]{\begin{Theorem}{\rm\cite{#1}}~~#2
\end{Theorem}}
 
\newcommand{\proof}[1]{ \noindent {\it Proof.}
#1 \mbox{}\vspace{\baselineskip}\mbox{}\hspace*{\fill}$\Box$}
 
\newcommand{\proofof}[2]{ \noindent {\it Proof of #1.}
#2 \mbox{}\vspace{\baselineskip}\mbox{}\hfill$\Box$}
 
\newcommand{\lemma}[1]{\begin{Lemma}  #1 \end{Lemma}}
 
\newcommand{\cor}[1]{\begin{Cor}  #1 \end{Cor}}
\newcommand{\prop}[1]{\begin{Prop}  #1 \end{Prop}}
\newcommand{\defi}[1]{\begin{Def}  #1 \end{Def}}
 
\newcommand{\deficite}[2]{\begin{Def}{\rm\cite{#1}}~~#2
\end{Def}}
 
% Enumeration with alpha items
\newcommand{\alphaitems}{\renewcommand{\labelenumi}{\mbox{(}\/\alph{enumi}\/\mbox{)}}}
% Enumeration with roman items
\newcommand{\romanitems}{\renewcommand{\labelenumi}{\mbox{(}\/\roman{enumi}\/\mbox{)}}}


%***********
\newcommand{\Pe}{{\rm P}}
\newcommand{\NP}{{\rm NP}}
\newcommand{\FP}{{\rm FP}}
\newcommand{\PH}{{\rm PH}}
\newcommand{\CH}{{\rm CH}}
\newcommand{\Mod}{{\rm Mod}}
\newcommand{\mymod}{{\mbox {\rm ~mod~}}}
\newcommand{\ModkP}{\mbox{\rm Mod$_k\Pe$}}
\newcommand{\ModpP}{\mbox{\rm Mod$_p\Pe$}}
\newcommand{\PP}{{\rm PP}}
\newcommand{\ParP}{{\mbox{$\oplus$\Pe}}}
\newcommand{\pair}[2]{\langle #1,#2\rangle}
\newcommand{\triple}[3]{\langle #1,#2,#3\rangle}
\newcommand{\alphabar}{\overline \alpha}
\newcommand{\xibar}{\overline \xi}
\newcommand{\omegabar}{\overline \omega}
\newcommand{\polylog}{{\it polylog\/}}
\newcommand{\Ree}{\mbox {\cal Re}}
\newcommand{\Vector}[1]{\mbox {\rm \bf #1}}
\newcommand{\mathvector}[1]{\mbox {\boldmath $#1$}}
\newcommand{\nat}{\Vector{N}}
\newcommand{\integer}{\Vector{Z}}
%\newcommand{\iff}{\, \Longleftrightarrow \,}
\newcommand{\implies}{\, \Longrightarrow \,}
\newcommand{\aarg}{\mbox {\rm arg}}
\newcommand{\haff}{1 \over 2}
 
\newlength{\g}
\settowidth{\g}{=}
\newcommand{\Cg}{\sf C\hspace{-0.45\g}\raisebox{.15ex}{\footnotesize =}\hspace{-
   .15\g}}
\newcommand{\Cgex}{\footnotesize \sf C\hspace{-0.4\g}\raisebox{.18ex}{\tiny =}
                     \hspace{-.15\g}}
 
\newcommand     {\nule}         {\{0,1\}}
\newcommand     {\x}            {(|x|)}
 
\newcommand{\pmredu}{\mathrel{\hbox{$\leq_{\rm m}^{\rm p}$}}}
\newcommand{\AND}{\; \wedge \;}
 


\date{}
\title{On the Correlation of Symmetric Functions
        \thanks{Supported in part by NSF grant CCR-9057486.}
       }

\author{
Jin-Yi Cai \thanks{Department of Computer Science,
State University of New York at Buffalo, Buffalo, NY 14260.
Supported in part by an Alfred T.\ Sloan Fellowship in computer science.}\\
\normalsize
University of Buffalo\\
\and
Frederic Green\thanks{Clark University,
Department of Mathematics \& Computer Science,
Worcester, Massachusetts 01610. 
Work done in part while visiting Princeton University. }\\
\normalsize
Clark University\\
\and
Thomas Thierauf \thanks{Universit\"at Ulm,
Abteilung Theoretische Informatik,
Oberer Eselsberg, 89069 Ulm, Germany.
Work done in part while visiting Princeton University and
the University of Rochester.
Supported in part by DFG Postdoctoral Stipend Th 472/1-1
and by NSF grant CCR-8957604.}\\
\normalsize
Universit\"at Ulm\\
}

\begin{document}

\maketitle

%\thispagestyle{empty}

\begin{abstract}
The {\em correlation\/} between two Boolean functions of $n$ inputs
is defined as the number of times the functions agree minus the
number of times they disagree, all divided by $2^n$. 
In this paper, we compute, in closed form, the correlation between any
two {\em symmetric\/} Boolean functions. 
As a consequence of our main result, we get that
every symmetric Boolean function having an odd period 
has an {\em exponentially small\/}  correlation (in $n$) with the parity function. 
This improves a result of Smolensky~\cite{Sm} restricted to symmetric Boolean functions: 
the correlation between parity and any circuit consisting of a 
Mod$_q$ gate over AND-gates of small fan-in,
where $q$ is odd and 
the function computed by the sum of the AND-gates is symmetric,
is bounded by $2^{-\Omega(n)}$.

In addition, we find that for a large
class of symmetric functions the correlation with parity is
{\em identically\/} zero for infinitely many $n$. We characterize
exactly those symmetric Boolean functions having this property.
\end{abstract}

\section{Introduction}

AC$^{(0)}$ circuits cannot compute the
parity function as shown in the seminal work of Furst, Saxe, and Sipser~\cite{FSS}
and Ajtai~\cite{Ajt}. 
In a breakthrough result, Yao~\cite{Yao} showed that in fact AC$^{(0)}$ type
circuits (i.e., bounded-depth circuits containing AND, OR and NOT gates) must
have exponential size to compute parity. 
A simpler proof and nearly optimal lower bounds were obtained 
by H{\aa}stad~\cite{Has}. 
As originally pointed out in \cite{FSS}, 
these bounds imply the existence of an oracle separating PH from PSPACE.  
In order to prove the separation relative to a random oracle,
Cai~\cite{Cai} showed that AC$^{(0)}$ type circuits below 
a certain exponential size cannot even {\em approximate\/} parity, 
in that the error approaches 50\% asymptotically.
Babai \cite{Bab} subsequently gave an elegant and  much simpler proof. 
More specifically, it is shown that  AC$^{(0)}$ type circuits, 
below a certain exponential size, can
agree with parity no more than a fraction $1/2 +f(n)$ of the $2^n$ inputs,
where $f(n)=2^{-n^{\Omega(1)}}$.  (This was implicit in \cite{Cai} and 
H{\aa}stad and Boppana, as reported in \cite{Has}, have the best constant
involved.) 
One of the interesting consequences of this sharp result is that
circuits consisting of a single majority gate over
AC$^{(0)}$-type circuits cannot compute parity, unless the circuits are of
exponential size~\cite{Gre}. 

If we allow, for example, Mod$_3$ gates in
addition in the AC$^{(0)}$ subcircuits, 
it was
shown by Smolensky \cite{Sm}, extending techniques of Razbarov \cite{Raz},
that the fraction of agreement between parity and bounded-depth circuits
containing AND, OR, NOT and Mod$_3$ gates, below a certain exponential size,
is no more than $1/2 + f(n)$, where  $f(n) =  1/n^{1/2 - o(1)}$. 
Thus, the bound for $f(n)$ is weaker for this type of circuit.
It is therefore natural to ask if the
$1/n^{1/2 - o(1)}$ bound can be tightened, as in the AC$^{(0)}$ case, to
$2^{-n^{\Omega(1)}}$. To reduce the problem to its simplest form, consider a
circuit consisting of a Mod$_3$ gate over AND gates of small fan-in. Even in
this case it is not known if the agreement with parity is exponentially close
to 1/2. (This is also sufficient, since the Razborov approximation is
exponentially close.) However, it is not clear whether Smolensky's techniques
can be used to improve the known bound below $O(1/{\sqrt n})$.

The sum of the inputs going into a Mod$_q$ gate can be interpreted as a
polynomial in the input variables. Thus
the problem can be stated more precisely as follows:
For any natural number $q$ define the
Boolean function $M_q : N \rightarrow \{0,1\}$ such that $M_q(k) = 1$ if $k
\not \equiv 0 \pmod{q}$ and 0 otherwise. For a polynomial $p : \{0,1\}^n
\rightarrow \nat$, how well can $M_q(p(x_1,\dots,x_n))$ approximate parity?

  In this paper, we consider a restricted version of this problem, in which we
assume the polynomials $p$ are {\em symmetric\/}. Thus the question we address
is: for a {\em symmetric\/} polynomial $p : \{0,1\}^n \rightarrow \nat$ of low degree, 
how well can $M_q(p(x_1,\dots,x_n))$ approximate parity?

   In a recent paper, which was in part an inspiration for this
one, Barrington, Beigel, and Rudich \cite{BBR} also considered the
computational power of symmetric polynomials which represent Boolean functions
in this way. They give a surprising upper bound (and a
matching lower bound) for the degree of a symmetric polynomial $p$ such that
$M_q(p(x_1,\dots,x_n))$ computes the OR function. Their results suggest the
very interesting possibility that in general Mod$_q$ gates might be more
powerful when $q$ is composite than when $q$ is prime. In addition, for a {\em
general} polynomial $p$ (not necessarily symmetric), they prove the first lower
bounds on the degree of $p$ for $M_q(p)$ to compute the $M_{q'}$ function when
$q$ and $q'$ are composite and there is a prime divisor of $q'$ that is not a
divisor of $q$. Our problem is different.  We wish to estimate the error
rather than finding exact agreement.
 For the latter reason, we do not consider the OR function, 
since a constant polynomial would give almost complete
agreement.

   As a measure of how well one Boolean function can approximate another we use
the notion of correlation.  Let $g_1, g_2 : \{0,1\}^n
\rightarrow \{0,1\}$ be two Boolean functions  over the inputs
$\{x_1,\dots,x_n\}$ where $x_i \in \{0,1\}$. The {\em correlation\/}
$C_n(g_1, g_2)$ between $g_1$ and $g_2$ is the difference between 
the number of
times $g_1$ and $g_2$ agree and the number of times they  disagree, divided by
$2^n$. Since $g_1, g_2$ take on values in $\{0,1\}$, this can be written as,

$$ C_n(g_1, g_2) = 2^{-n} \sum \limits_{\{x_1,\dots,x_n\} \in \{0,1\}^n}
                             (-1)^{g_1(x_1,\dots,x_n) + g_2(x_1,\dots,x_n)}.$$

  In these terms, the result of Cai and H{\aa}stad says that if $g$ is the
Boolean function computed by an AC$^{(0)}$ circuit, and $\oplus$ denotes the
parity function, then $C_n(g, \oplus) = 2^{-n^{\Omega(1)}}$.
Smolensky's result says that if $q$
is an odd prime and if $p$ denotes
any polynomial of low degree (e.g., $\polylog(n)$), then
$C_n(M_q(p), \oplus) = 1/n^{1/2 - o(1)}$.

    Our main result is that if $p$ is any low-degree symmetric polynomial,
the correlation is indeed exponentially small.
That is, if $q$ is odd, and $p$ is symmetric and of low degree
(e.g., $\polylog(n)$ or even $n^{o(1)}$),
then  $C_n(M_q(p), \oplus) = 2^{-\Omega(n)}$ (see Corollary
\ref{parity-upper-bound}).
This is actually a corollary of a general result, which gives a
{\em closed form} expression for the correlation between any two
symmetric Boolean functions. 
This result is given in Section~\ref{section:symmetric} 
(see Theorem \ref{correlation}). In Section~\ref{section:zero},
we show that for a wide class of symmetric polynomials the
correlation with parity is {\em exactly\/} 0 for infinitely many values of $n$.
Our techniques allow a detailed analysis of the correlation, so that
we can characterize exactly all those symmetric Boolean functions having
this property (Theorem \ref{zeroes-characterization}). We demonstrate, for
elementary symmetric polynomials, how the zeroes in the correlation as a
function of $n$ can be computed when this property holds.


\section{Preliminaries}

A function $g : \{0,1\}^n \rightarrow \nat$  over Boolean variables 
$\{x_1,\dots,x_n\}$ is {\em symmetric\/},
if the function value of $g$ remains unchanged for any permutation
of the input variables.
As a consequence, any symmetric function depends only on the sum of its inputs. 
Hence, we can write it as $g(x_1,\dots,x_n) =  f(\sum_{j=1}^n x_j)$ for some
function $f : \integer \rightarrow \integer$ which we say  {\em represents\/} $g$. 
If $g$ is a Boolean function, i.e., $g: \{0,1\}^n \rightarrow \{0,1\}$, 
then we also require $f$ to map to $\{0,1\}$.

The {\em elementary symmetric polynomial\/} $e_d(x_1,\dots,x_n)$
or $e_d(x)$ of degree $d$ over Boolean variables 
$\{x_1,\dots,x_n\}$ is the sum of all monomials of the form
$\prod_{j \in S} x_i$ where $S \subseteq \{1,\dots,n\}$ and $||S|| = d$.
It is clear that if the number of variables that are 1 is $k$, then
$e_d(x) = {k \choose d}$. 
Any symmetric Boolean function of degree $d$ can be written as 
a linear combination of the elementary symmetric polynomials of degree $\le d$.

Let $D \in \nat$, $D > 0$.
We say $f : \integer \rightarrow \integer$ is
{\em periodic with period $D$} if $f(k+D) = f(k)$, for any $k \in \integer$.
Unless otherwise noted, when we refer to {\em the\/} period of a
function, we mean the smallest period. Of course any multiple of the period $D$
is also a period, and it is not hard to see that any period must be a multiple
of the smallest one. 
We say the  symmetric Boolean function $g : \{0,1\}^n \rightarrow \{0,1\}$ 
is {\em periodic with period $D$} if $D \leq n$ and there is a function~$f$
that represents $g$ such that $f$ is periodic with period $D$. 
(Note that in fact such a function~$f$, if it exists, is uniquely determined.)

For example, define
$M_q : \integer \rightarrow \{0,1\}$ as
\[M_q(k) \,=\, \left\{\begin{array}{ll}
1, & \mbox{ if } k \not \equiv 0 \pmod{q}\\
0, & \mbox{ otherwise.}
\end{array}\right.\]                
In \cite{BBR} it is noted that if $p$
is a polynomial of degree $d$ and the number of distinct 
prime factors of $q$ is $r$, 
then the period of $M_q(p(x_1,\dots,x_n))$ is $D = \Theta(d^r)$.

While a symmetric, periodic Boolean function $g : \{0,1\}^n \rightarrow \{0,1\}$
has a finite domain, the function~$f$ representing $g$ is defined on \integer.
Therefore, when we consider $n$ as variable in later sections,
we are referring to $f$ instead of $g$.
Note that in turn, $f$ defines a sequence of symmetric Boolean functions 
$g_m : \{0,1\}^m \rightarrow \{0,1\}$, for each $m \in \nat$.
Regarding the correlation, we will also write $C_n(f,g')$ for $C_n(g,g')$,
where $g'$ is another Boolean function.

\section{General Symmetric Functions}\label{section:symmetric}

  Let $q_1, q_2 \in \nat$ and $p_1$ and $p_2$ be symmetric polynomials. We derive
in this section a formula for $C_n(M_{q_1}(p_1),M_{q_2}(p_2))$. 
In fact, we don't need any special properties of these functions.
Our proof depends only on the periodicity of $M_{q_1}(p_1)$ and $M_{q_2}(p_2)$, 
and therefore, we consider the correlation
between any two symmetric Boolean functions in terms of their periods.


\theorem{\label{correlation}
Let $g_1$, $g_2:\{0,1\}^n \rightarrow \{0,1\}$ be symmetric Boolean functions 
represented by $f_1$ and $f_2$, respectively, and let $D$ be a period of $f_1+f_2$. 
Let $\xi$ denote the $D^{th}$ root of unity $e^{2 \pi i / D}$ and
$\lambda_j = 1+\xi^{-j}$. Then
$$ C_n(g_1, g_2) \, = \, {1 \over 2^n D} \sum \limits_{k=0}^{D-1}
                         (-1)^{f_1(k)+f_2(k)}
                          \sum \limits_{j=0}^{D-1} 
                                 {\xi}^{kj} \lambda_j^n.$$}
\proof{
Since $g_1$ and $g_2$ are symmetric, the correlation between $g_1$ and $g_2$
becomes
$$C_n(g_1, g_2) \, = \, 2^{-n} \sum \limits_{k=0}^n (-1)^{f_1(k) + f_2(k)}
                                       {n \choose k}.$$
Since $D$ is a period of $f_1 + f_2$,
we can partition this sum into $D$ sums, 
one for each remainder modulo $D$, as follows.
For $k = 0,\dots, D-1$ let
$$ r_k(n) \,=\, \sum \limits_{j\ \equiv\ k  \!\!\!\! \pmod{D}} {n \choose j}.$$
Then we have
$$C_n(g_1, g_2) \, = \, 2^{-n} \sum \limits_{k=0}^{D-1} 
               (-1)^{f_1(k) + f_2(k)} r_k(n).$$
The proof is completed by the following lemma,
showing that each $r_k$ can be written as claimed in the theorem.
}


\lemma{\label{sums}
$ r_k(n) = {1 \over D} \sum \limits_{j=0}^{D-1}
                                   {\xi}^{kj} \lambda_j^n$,
~~~for $k = 0,\dots, D-1$. }
\proof{
Using the recurrence relation for the binomial coefficients, we have
\[r_k(n) \, =\,  \sum \limits_{j \ \equiv \ k \!\!\!\! \pmod{D}} 
                      \left[ {n-1 \choose j} + {n-1 \choose j-1} \right]
              \,=\, r_k(n-1) + r_{k-1}(n-1)
\]
for all $k \in \{0, \dots, D-1\}$,
where index $k-1$ is taken modulo $D$. 
Let us define vector $\Vector{r}(n)$ as 
$$ \Vector{r}(n) \,=\, \pmatrix {r_0(n) \cr
                                 r_1(n) \cr
                                 \cdot     \cr
                                 \cdot     \cr
                                 \cdot     \cr
                                 r_{D-1}(n) \cr}. $$
By the above recurrence relation,
we can compute $\Vector{r}(n)$ by multiplying $\Vector{r}(n-1)$
with some appropriately defined matrix \Vector{M},
$$ \Vector{r}(n) \,=\, \Vector{M} \, \Vector{r}(n-1),$$
where \Vector{M} is the $D \times D$ matrix
\begin{eqnarray*}
 \Vector{M} &=& \pmatrix {1 & 0 & 0 & 0 & \cdot & \cdot & \cdot & 0 & 1 \cr
                 1 & 1 & 0 & 0 & \cdot & \cdot & \cdot & 0 & 0 \cr
                 0 & 1 & 1 & 0 & \cdot & \cdot & \cdot & 0 & 0 \cr
                 0 & 0 & 1 & 1 & \cdot & \cdot & \cdot & 0 & 0 \cr
                 \cdot &  &  &  &      &       &       &   & \cdot \cr
                 \cdot &  &  &  &      &       &       &   & \cdot \cr
                 \cdot &  &  &  &      &       &       &   & \cdot \cr
                 0 & 0 & 0 & 0 & \cdot& \cdot & \cdot & 1 & 1}. 
\end{eqnarray*}
Hence, we get $\Vector{r}(n) = \Vector{M}^n \Vector{r}(0)$,
where the components of $\Vector{r}(0)$ are
$r_0(0) = 1$ and $r_k(0) = 0$ for $k = 1, \dots,D-1$.
It remains to compute the $n$-th power of the matrix~\Vector{M}.
The simplest way to do this is to diagonalize \Vector{M}.
The eigenvalues of \Vector{M} are the $\lambda_j$, for $j = 0, \dots, D-1$, 
and an
%left 
eigenvector corresponding to $\lambda_j$ is
$$ \pmatrix
      {1 & \xi^{-j} & \xi^{-2j} & \cdot & \cdot & \cdot & 
               \xi^{-(D-1)j}}^T.$$

Since the eigenvectors are linearly independent,
we actually can diagonalize \Vector{M}.
The diagonalizing matrix \Vector{V} is defined as having
the $D$ eigenvectors as its columns,
$ (\Vector{V})_{k,j} =  \xi^{-kj}$,
which is a Vandermonde matrix.
The diagonal matrix \mathvector{\Delta} has the eigenvalues as its diagonal entries,
the $j$-th diagonal entry of \mathvector{\Delta} being the eigenvalue for the
eigenvector in the $j$-th column of \Vector{V}, $\lambda_j$.

It is easy to verify that ${1 \over {\sqrt D}} \Vector{V}$ is unitary 
(i.e., $\Vector{V}\Vector{V}^* = \Vector{V}^*\Vector{V} = D \, \Vector{I}$, where
$\Vector{V}^*$ denotes the Hermitian conjugate of \Vector{V}
and  \Vector{I} is the identity matrix) using the fact that
\[ \sum \limits_{j=0}^{D-1} \xi^{kj}
     \,=\,   \left\{ \begin{array}{ll}
                     D,   & \mbox{if $k = 0$,} \\
                     0,   & \mbox{otherwise.}
                 \end{array}
         \right. \]
Hence $\Vector{M} = \frac{1}{D} \Vector{V}^* \mathvector{\Delta} \Vector{V}$, and 
$\Vector{M}^n = \frac{1}{D} \Vector{V}^* \mathvector{\Delta}^n \Vector{V}$.
Therefore, we get
\[
\Vector{r}(n) 
              \,=\, \frac{1}{D} \Vector{V}^* \mathvector{\Delta}^n \Vector{V} \Vector{r}(0)
              \,=\, \frac{1}{D} \Vector{V}^* \mathvector{\Delta}^n \Vector{V} 
                                    \pmatrix{1 \cr 0 \cr \cdot
                                               \cr \cdot \cr \cdot \cr 0}
              \,=\, \frac{1}{D} \Vector{V}^* \mathvector{\Delta}^n
                                    \pmatrix{1 \cr 1 \cr \cdot
                                               \cr \cdot \cr \cdot \cr 1}
              \,=\, \frac{1}{D} \Vector{V}^*
                                    \pmatrix{\lambda_0^n \cr 
                                             \lambda_1^n \cr 
                                             \lambda_2^n \cr
                                             \cdot \cr \cdot \cr \cdot \cr 
                                             \lambda_{D-1}^n}.
\]
{}From the definition of \Vector{V}, the lemma now follows immediately.
}


The sum in Theorem~\ref{correlation} can also be written as
$$ C_n(g_1, g_2) \,=\, {1 \over 2^n D} \sum \limits_{j=0}^{D-1}
                                 s_j \lambda_j^n,$$
where
$$ s_j \,=\, \sum \limits_{k=0}^{D-1} (-1)^{f_1(k)+f_2(k)}
                                 {\xi}^{kj}.$$
Observe that the largest eigenvalue is $\lambda_0=2$,
and that all other eigenvalues are smaller.
In fact, the second largest
eigenvalue $\lambda_1$ has norm $|1+\xi| = 2 \cos(\pi/D)$.
Thus, while the largest term in the above sum (when $j=0$) is constant $s_0/D$
(i.e., independent of $n$, if $D$ is constant),
the second largest term (when $j=1$) has norm 
${|s_1| \over D} \cos(\pi/D)^n$ 
which is exponentially small compared with the first term
(if $D$ is a constant or a slowly growing function in $n$). 
This yields,

\cor{\label{general-upper-bound}
Let $g_1$, $g_2:\{0,1\}^n \rightarrow \{0,1\}$ be symmetric Boolean functions 
represented by $f_1$ and $f_2$,
respectively, and let $D$ be a period of $f_1+f_2$.
Let
$s_0 =\sum_{k=0}^{D-1} (-1)^{f_1(k)+f_2(k)}$.
Then
$$ |\, C_n(g_1, g_2) - {s_0 \over D}\,|  \,=\, O(\cos(\pi/D)^n).$$
}

  We can now easily prove the main corollary of this section, which
states that the fraction of the time that any symmetric function with a
small odd 
period can agree with parity is exponentially close to $1/2$.

\cor{\label{parity-upper-bound}
Let $g:\{0,1\}^n \rightarrow \{0,1\}$ be a symmetric Boolean function 
with odd period~$D$. Let $\oplus$ 
denote the parity function. Then
$$ |\,C_n(g, \oplus)\,| \,=\, O(\cos(\pi/(2D))^n) \,=\, 
            O\left((1-{1 \over 2}({\pi \over 2D})^2)^n \right). $$
}
\proof{
Let $f$ represent $g$. Observe that $M_2$ represents $\oplus$.
Since $D$ is odd, the period of $f + M_2$ is $2D$.
Furthermore, we have
$(-1)^{f(k) + M_2(k)} = (-1)^{f(k) + k}= - (-1)^{f(k + D) + k+D}$, and hence
$$s_0 \,=\, \sum \limits_{k=0}^{2D-1} (-1)^{f(k) + k} \,=\, 0.$$
Now, the claim follows from Corollary~\ref{general-upper-bound}.
}

Let us consider a sequence of symmetric functions 
$g_n:\{0,1\}^n \rightarrow \{0,1\}$
having different (odd) periods $D(n)$.
It follows from Corollary~\ref{parity-upper-bound}
that $ C_n(g_n, \oplus) $ is exponentially small in $n$
as long as $D(n) = O(n^{1/2 - \epsilon})$, for some $ \epsilon > 0$.

If we choose $g_n = M_q(p_n)$, for odd $q$ and some symmetric polynomial~$p_n$
of degree~$d(n)$, then the period of $g_n$ is odd (see Theorem~\ref{zabek} below)
and is bounded by $O(d(n)^{\log q})$.
Therefore, 
when the degree $d(n)$ is bounded by $O(n^{\frac{1}{2 \log q} - \epsilon})$, 
for some $ \epsilon > 0$,
then $ |C_n(M_q(p_n), \oplus)| = 2^{-\Omega(n)}$.



\section{Zeroes in the Correlation With Parity}\label{section:zero}

 In the previous section, we have seen that 
the correlation of parity with any symmetric function of small, odd
period must be exponentially small. Remarkably, we find that for many 
symmetric functions the correlation is identically zero for infinitely many
$n$, spaced at regular intervals if the period is constant. When a function has
this property, we can compute the zeroes (i.e., those values of $n$ for which
the correlation is zero).
In this section, we first characterize which symmetric
functions have this property. Then we turn our attention to a special class of
functions (the elementary symmetric polynomials modulo an odd number) to
illustrate how to compute the zeroes.

It is easy to see that the correlation of a constant function with parity 
is zero for all $n$.
For any non-constant symmetric function, the following theorem characterizes 
almost all $n$ for which the correlation with parity is zero.
%Here, the period $D$ is a constant (independent of $n$).

\theorem{\label{zeroes-characterization}
Let $f :\integer \rightarrow \{0,1\}$ be a non-constant function with odd period $D$. 
There exists an integer $n_0$\footnote{
In fact, $n_0$ depends only on $D$, and not on $f$.}
such that for any $n>n_0$,
the following conditions are equivalent.
\begin{enumerate}\alphaitems
\item
$C_n(f, \oplus)=0$,
\item
$f(k) \equiv n+1+f(n-k) \pmod{2}$,~~for $k = 0, \dots, D-1$.
\end{enumerate}
}
\proof{
Let $\xi$ denote the $2D^{th}$ root of unity $e^{\pi i / D}$ and
$\lambda_j = 1 + \xi^{-j}$. Then, by Theorem~\ref{correlation},
\begin{eqnarray*}
2^n C_n(f, \oplus) & = & 
        {1 \over {2D}} \sum \limits_{j=0}^{2D-1} 
                      \sum \limits_{k=0}^{2D-1} 
                        (-1)^{f(k) + k}\, \xi^{kj}
                                                     \lambda_j^n\\
       & = & {1 \over {D}} \sum \limits_{j=0}^{D-1} 
                      \Ree \left(\sum \limits_{k=0}^{2D-1} 
                        (-1)^{f(k) + k}\, 
                                \xi^{kj} \lambda_j^n \right),
\end{eqnarray*}
where the second equality holds because $\xi^{2D-j} = \xibar^j$
and $\lambda_{2D-j} = {\overline \lambda}_j$,
so that the second half of the $j$-sum
($D \le j \le 2D-1$) is the complex conjugate of the first half. 
Let us define 
\begin{eqnarray*}
  s_j &=& \sum \limits_{k=0}^{2D-1} 
                        (-1)^{f(k) + k}\, 
                                \xi^{kj},\\
  t_j(n) &=& \Ree(s_j \lambda_j^n),
\end{eqnarray*}
for $j = 0, \dots, 2D-1$. Then we have
$$ 2^n C_n(f, \oplus) \,=\, {1 \over {D}} \sum \limits_{j=0}^{D-1}
                                     t_j(n).$$



Note that if $j$ is even, we have that $s_j=0$, and hence $t_j(n) = 0$.
This holds because $\xi^{(k+D)j} = \xi^{kj}$ for even $j$, 
and $(-1)^{k+D} = - (-1)^k$. 
Note also that
for any $0 \le j \le D-1$, we have $t_j(n) = t_{2D-j}(n)$
and that $t_D(n)=0$ since $\lambda_D =0$.

The proof is completed by the following three lemmas.
}

When $C_n(f,\oplus)=0$, there are potentially two reasons for this:
either all the $t_j(n)$ are zero
or several nonzero  $t_j(n)$ cancel each other.
Our first lemma states that the latter cannot happen
for large enough $n$.

\lemma{There exists an integer $n_0$ such that for any $n> n_0$,
\[C_n(f,\oplus)=0 \iff  t_j(n)=0,~~~\mbox{for all } 0 \le j \le 2D-1.\]
}
\proof{
Since $t_j(n) = t_{2D-j}(n)$, it suffices to argue for $0 \le j \le D-1$.
Suppose $C_n(f,\oplus)=0$.
We can express $t_j(n)$ as\footnote{
Any complex number $z \not= 0$ can uniquely be written as
$z = |z| ( \cos \varphi + i \sin \varphi ) = |z| e^{i \varphi}$, 
where $0 \leq \varphi \leq 2 \pi$. 
$\varphi$ is called the {\em argument of\/} $z$, $\varphi = \arg z$.
Hence $\Ree (z) = |z| \cos \arg (z)$.}
\begin{eqnarray}\label{eq:tj}
t_j(n) & = & |s_j|\,  |2 \cos({\pi j \over 2D})|^n \,
                        \cos(\arg (s_j) - {\pi n j \over 2D}).
\end{eqnarray}

Clearly, we have $ |t_j(n)| \leq |s_j|\,  |2 \cos({\pi j \over 2D})|^n $.
On the other hand,
since the cosine is periodic in $n$,
for any $j$ there exists a constant $c_j > 0$ 
(i.e., $c_j$ does not depend on $n$)
such that 
\[t_j(n) \not = 0 \implies |t_j(n)| \ge c_j \, |2 \cos({\pi j \over 2D})|^n.\]
Hence, each $|t_j(n)|$ is either zero or in a constant range of 
$|2 \cos({\pi j \over 2D})|^n$. 
(Note that $s_j$ doesn't depend on $n$.)

Because $|2 \cos({\pi j \over 2D})|^n$ dominates 
$|2 \cos({\pi (j+1) \over 2D})|^n$ for large $n$ and $j<D$, any $t_j(n) \not
= 0$ dominates all the $t_{j'}(n)$ for $j < j' < D$. 
Thus, if $j_0$ is the
least $j$ such that $t_j(n) \not = 0$, then the subsequent terms cannot cancel
$t_{j_0}(n)$, and hence, $C_n(f,\oplus) \not = 0$. 
Therefore, $t_j(n) =0$ for all $0 \le j \le D-1$. 
 }%First lemma

Using equation~(\ref{eq:tj}), we can characterize when a $t_j(n)$ is zero
in terms of the $s_j$.
Since $|2 \cos({\pi j \over 2D})|^n$ (and hence $t_j(n)$) is zero for $j=D$,
we have to exclude the case $j=D$ in the next lemma.

\lemma{Let $0 \le j \le 2D-1$, $j \ne D$. 
Then $t_j(n)=0 \iff s_j = -\xi^{nj} \overline{s_j}$.
}
\proof{If $s_j = 0$, then the lemma is trivial. Otherwise, for any $j \ne D$, 
\begin{eqnarray*}
t_j(n)=0 & \iff & \cos(\arg (s_j)-{\pi n j \over 2D}) = 0\\
         & \iff & \exists\, l \,\,\, \arg (s_j)-{\pi n j \over 2D} \,\,=\,\, {\pi \over 2} + l \pi\\
         & \iff & \exists\, l \,\,\, e^{2i \arg (s_j)} \,\,= \,\,
                                   e^{2i\, ({\pi n j \over 2D} +  {\pi \over 2} + l \pi)}\\
         & \iff & |s_j| \,e^{i \arg (s_j)} \,\,= \,\,-|s_j|\, e^{-i \arg (s_j)}e^{{\pi i \over D} n j}\\
         & \iff & s_j \,\,= \,\, -\xi^{nj} \overline{s_j}. 
\end{eqnarray*}
}%Second lemma


\lemma{The following conditions are equivalent.
\begin{enumerate}\romanitems
\item
$s_j = -\xi^{nj} \overline{s_j}$,~~for $j = 0, \dots, 2D-1$, $j \ne D$,
\item
$ f(k) \equiv n+1+f(n-k) \pmod{2}$,~~for $k = 0, \dots, D-1$.
\end{enumerate}
}
\proof{
Since $(-1)^{f(k)+k}\, \xi^{-kj}$ has period $2D$,
we have
\begin{eqnarray*}
-\xi^{nj} \overline{s_j}
       &=&
 -\xi^{nj} \sum \limits_{k=0}^{2D-1} (-1)^{f(k)+k}\, \xi^{-kj}\\
       &=&
 -\xi^{nj} \sum \limits_{k=n}^{n+2D-1} (-1)^{f(k)+k}\,  \xi^{-kj}\\
       &=&
 (-1)^{n+1} \sum \limits_{k=n}^{n+2D-1}
          (-1)^{f(k)+n-k} \, \xi^{(n-k)j}\\
   &=& \sum \limits_{k'=0}^{2D-1}
          (-1)^{n+1+f(n-k')+k'} \, \xi^{k'j},
\end{eqnarray*}
where the last equality was obtained by changing the summation variable to
$k' = n-k$.
Now, if condition (ii) is true, then it is clear that
$$ s_j \,=\,  \sum \limits_{k=0}^{2D-1}
          (-1)^{n+1+f(n-k)+k} \, \xi^{kj},$$
which yields condition~(i). 

Conversely, if condition~(i) is true then, for any $0 \le j \le 2D-1$, $j \ne D$,
\begin{eqnarray}\label{le:transform}
 \sum \limits_{k=0}^{2D-1} (-1)^{f(k)+k} \, \xi^{kj} \,=\,
 \sum \limits_{k=0}^{2D-1}
          (-1)^{n+1+f(n-k)+k} \, \xi^{kj}.
\end{eqnarray}
Note that these sums are the Fourier transforms of the functions
$(-1)^{k + f(k)}$ and $(-1)^{k + n + 1 + f(n - k)}$, respectively.
Therefore, if equation~(\ref{le:transform}) held for all $j$, 
i.e., including $j=D$,
then we could immediately conclude that the functions are equal.
But it is not obvious that equation~(\ref{le:transform}) holds for $j=D$
when $n$ is even. 
Nevertheless, we can perform an inverse Fourier transform by using
the relation
\[ \sum \limits_{j=0, j \ne D}^{2D-1} \, \xi^{(k-k')j}
     \,=\,   \left\{ \begin{array}{ll}
                     2D-1            & \mbox{if $k = k'$} \\
                     (-1)^{k-k'+1}   & \mbox{otherwise.}
                 \end{array}
         \right. \]
Now multiply the left and right hand sides of equation~(\ref{le:transform}) by
$\xi^{-k'j}$ and sum over $j$ from 0 to $2D-1$, excluding $j=D$. This yields,
for any $0 \le k' \le D-1$,
$$ 2D(-1)^{f(k')} - \sum \limits_{k=0}^{2D-1} (-1)^{f(k)}
      \,=\, 2D(-1)^{n+1+f(n-k')}
           -  \sum \limits_{k=0}^{2D-1} (-1)^{n+1+f(n-k)}.$$
Note that the last sum in this equation is equal to 
$(-1)^{n+1} \sum_{k=0}^{2D-1} (-1)^{f(k)}$.
Hence, we get
\begin{eqnarray}\label{le:simple-form}
(-1)^{f(k')} \,=\, (-1)^{n+1+f(n-k')}
        + {1 \over 2D}(1 + (-1)^n) \sum \limits_{k=0}^{2D-1} (-1)^{f(k)}.
\end{eqnarray}
To show condition (ii), it suffices to prove that the second term 
of the right hand side of equation~(\ref{le:simple-form}) is 0.
This is certainly true when $n$ is odd.
Let $n$ be even. 
Then equation~(\ref{le:simple-form}) becomes
$$(-1)^{f(k')} + (-1)^{f(n-k')} \,=\,
          {1 \over D} \sum \limits_{k=0}^{2D-1} (-1)^{f(k)}.$$
Observe that the right hand side is independent of $k'$, and hence both sides
are. The left hand side can be $\pm 2$ or 0. If it is $\pm 2$, then $f$ is
constant, which contradicts the hypothesis of the theorem. Hence, the left hand
side is 0 and we conclude that
$ \sum_{k=0}^{2D-1} (-1)^{f(k)} = 0.$
Thus, the second term of the right hand side of equation~(\ref{le:simple-form}) is 
indeed zero, and condition (ii) follows.
(Observe that 
$s_D = \sum_{k=0}^{2D-1} (-1)^{f(k)+k} \xi^{kD} = \sum_{k=0}^{2D-1} (-1)^{f(k)} = 0$.
Hence, condition~(i) implies that in fact 
$s_j = -\xi^{nj} \overline{s_j}$, for all $0 \le j \le 2D-1$.)
 }%Third lemma


Observe that in both conditions (i) and (ii) in the last lemma,
we can equivalently replace $n$ by $m$,
where $m$ ($0 \le m < 2D$) is the residue of $n$ modulo $2D$.
Likewise, we can make this replacement in
Theorem~\ref{zeroes-characterization}(b). Therefore,
to determine whether $C_n(f,\oplus)$ is zero for infinitely many $n$, 
it is only necessary to find an $m$ such that 
$0\le m \le 2D-1$ and 
\begin{eqnarray}\label{cond(ii)}
f(k) &\equiv& m+1+f(m-k) \pmod{2},~~~\mbox{for } k = 0, \dots, D-1.
\end{eqnarray} 

\cor{
Let $f :\integer \rightarrow \{0,1\}$ be a non-constant function with odd period $D$.
There is an $m \in \{0, \dots, 2D-1\}$ such that 
equation~(\ref{cond(ii)}) holds iff
$C_n(f,\oplus) = 0$ for all (large enough) $n$ such that $n \equiv m \pmod{2D}$.
}

Next, we show that if there exists an $m$ for which
equation~(\ref{cond(ii)}) holds, then it is unique.
Thus, in fact, {\em all\/} zeros in the correlation of $f$ with parity 
are at the points $n_l = m + 2l\, D$, for a fixed $m$, from a certain size of $l$ on.
Note that there may be additional zeroes for small values of $n$.

\prop{\label{uniqueness}
Let $f :\integer \rightarrow \{0,1\}$ be a function with odd period $D$.
Then equation~(\ref{cond(ii)}) holds for at most one 
$m \in \{0, \dots, 2D-1\}$.
}
\proof{
Suppose there are $m_0, m_1$, where $0 \le m_0 < m_1 < 2D$, such that 
$f(k) \equiv m_j + 1 + f(m_j -k) \pmod{2}$,~~for all $k$ and $j = 0,1$.
It follows that
$f(m_0 - k) \equiv m_1 - m_0 + f(m_1 + 2D - k) \pmod{2}$,~~for all $k$.
Let $k' = m_0 + 2D - k$. 
Then 
\[f(k') \,\equiv\, m_1 - m_0 + f(k' + m_1 - m_0) \pmod{2}\]
for any $k'$. 

Next, we argue that $m_1 - m_0$ must be even.
Suppose $m_1 - m_0$ is odd.
Then $f(k') \equiv 1 + f(k' + m_1 - m_0) \pmod{2}$ for all $k'$. 
Hence,
applying this a second time with the argument $k' + m_1 - m_0$ instead of $k'$,
we get
$f(k') \equiv 1 + 1 + f(k' + 2(m_1 - m_0)) \equiv
f(k' + 2(m_1 - m_0)) \pmod{2}$,
and therefore $f(k') = f(k' + 2(m_1 - m_0))$ for any $k' \geq 0$. 
By our assumption $2(m_1 - m_0) > 0$, and hence it is a period of $f$.
Recall that any period of $f$ must be a multiple of 
the smallest period $D$.
Since $D$ is odd, $m_1 - m_0$ must be a multiple of $D$.
Furthermore, 
since $m_1 - m_0 < 2D$, it follows that $m_1 - m_0 = D$. 
But then $f(k') \equiv 1 + f(k' + D) \pmod{2}$,
which contradicts the fact that $D$ is the period of $f$. 


Since $m_1 - m_0$ is even, 
we have  $f(k') = f(k' + m_1 - m_0)$ for any $k' \ge 0$.
Suppose $m_1 - m_0 > 0$. Then it is a period of $f$ and therefore a multiple of
$D$.  Since $D$ is odd, $m_1 - m_0$ is also a nonzero multiple of $2D$.
But this contradicts the fact that $0 < m_1 - m_0 < 2D$.
We conclude that $m_0 = m_1$. 
}


 We now compute the zeroes in the correlation  between parity and
any elementary symmetric polynomial modulo an odd number~$q$.
When $q$ is prime it is easy to see, by Lucas' theorem (see \cite{Smo}), that
the period of ${k \choose d} \bmod q$ is $q^b$ (in $k$), 
where $b$ is the smallest integer
such that $d < q^b$. The formula for the period
of the binomial coefficients modulo~$q$
when $q$ is composite is more complicated and is given in the following
theorem proved by S. Zabek~\cite{Zab}.  

\theorem{\label{zabek}{\bf \cite{Zab}}
Let $q = p_1^{a_1} \cdots p_r^{a_r}$, where the $p_j$'s are the prime
factors of $q$, $d > 0$, and $b_j = \lfloor log_{p_j}(d) \rfloor$.
Then the period of ${k \choose d} \bmod q$ is 
$ \prod_{j=1}^r p_j^{a_j + b_j}$.
}

It suffices to note here that when
$q$ is odd the period is a product of its prime factors
and is therefore odd. 
Note also that the period of ${k \choose d} \bmod q$ is a multiple of 
the period of $M_q(e_d)$, and hence, this period is odd too.

It follows from  Corollary~\ref{parity-upper-bound} that
for any $d$, $M_q(e_d(x))$ has exponentially small correlation with parity.
Furthermore, we have

\theorem{\label{zeroes-main}
Let $q$ be odd and $D$ be the period of $M_q(e_d(x))$.
Then, for sufficiently large~$n$,
$C_n(M_q(e_d),$ $ \oplus) = 0$ iff
$n = lD + d - 1$, where $l$ is any integer such that $l \equiv d \pmod{2}$.
}
\proof{
In order to apply Theorem~\ref{zeroes-characterization}, 
we need to derive an appropriate symmetry property of the binomial coefficients.
We use the following basic idendity which holds for any integer~$k$.
$$ {k \choose d} ~=~ {d-1-k \choose d} (-1)^d, $$
and therefore
$$ M_q({k \choose d}) ~=~ M_q({d-1-k \choose d}).$$
Define $m$ to be $d-1$, if $d$ is even and $D+d-1$, if $d$ is odd,
so that $m$ is odd. (Recall that $D$ is odd.) 
Then we have for any integer $k$
$$ M_q({k \choose d}) \,\equiv\, m+1 + M_q({m-k \choose d}) \pmod{2}.$$
Now, the claim follows from Theorem~\ref{zeroes-characterization} and
Proposition~\ref{uniqueness}.
}




\section{Conclusions and Open Problems}
We have investigated the correlation between two symmetric Boolean
functions. Our technique is to use exponential sums to estimate this important
quantity. For the class of symmetric functions, we are able to obtain
closed form solutions for the sum. The more interesting result would be to
give a similar estimate for any low degree polynomials modulo an odd integer
against the parity function, say. The use of exponential sums  points to the
possibility of applying  more sophisticated techniques.  There is a strong
connection between our sum and the (generalized) Gauss sum or Kloosterman sum
(see, e.g., \cite{IR}) which we briefly illustrate below.

Consider a polynomial $f(x_1, \ldots, x_n)$
with integer coefficients and degree $d$ on $n$ boolean 
variables.  We consider the correlation between, e.g., this polynomial modulo 3
and the parity function $\oplus$. Let $\omega$ be the third root of unity
$e^{2 \pi i/3}$. Then 
\begin{eqnarray*}
C_n(f, \oplus) &= & 2^{-n+1} \sum \limits_{\{x_1,\dots,x_n\} \in \{0,1\}^n}
                             \frac{\omega^{f(x_1, \ldots, x_n)} +
                              \omega^{-f(x_1, \ldots, x_n)} + 1}{3}
			      (-1)^{\sum_{j=1}^{n} x_j} \\
			&=& \frac{1}{2^{n-2} 3} {\rm Re} 
                              \sum \limits_{\{x_1,\dots,x_n\} \in \{0,1\}^n}
                             			     {\omega^{f(x_1, \ldots, x_n)}}
						     (-1)^{\sum_{j=1}^{n} x_j} .
\end{eqnarray*}
If we let $\chi$ be a nontrivial character modulo 3, by rearranging 
$-1, 1$ for $1,0$, we have
\[C_n(f, \oplus) \,=\,  \frac{1}{2^{n-2} 3} {\rm Re} \sum \limits_{\{x_1,\dots,x_n\}
                                                               \in {\bf F}_3^n}
                             	{\omega^{f(x_1, \ldots, x_n)}} \chi(x_1) \cdots
                                                               \chi(x_n),\]
which is precisely the real part of a generalized Gauss sum.

A lot of work has been done in order to estimate sums of this type, especially
those  results connected with the theorems and conjectures of Weil and Deligne
(see~\cite{Sch},\cite{Kat} for more information).  The sums encountered there
are usually of the type where one has a fixed number of variables, and considers
the sum as the base field is successively extended to degree $n$. In contrast,
 we have the  situation where
the  number of the variables $n$ is growing but the field is fixed.
It would be nice to be able to apply some of their techniques here. At
 the same time
a solution to our problem without their machinery would also be of independent
interest to number theory.

%Concerning exact zeros, we have some further results which are omitted in this
% extended
%abstract. Looking at special classes of symmetric functions (as we did for the
%elementary symmetric polynomials in section 3), with the aid of Theorem
%\ref{zeroes-characterization} and some additional techniques we can
%get more detailed information about when zeroes are present. For example,
%consider polynomials of the form $r_d(x_1,\ldots,x_n) = ae_d(x_1,\ldots,x_n)
%\pm be_0(x_1,\ldots,x_n)$ ($a,b \in N$), that is, homogeneous symmetric
%polynomials plus a constant. We can show that $C_n(M_3(r_d), \oplus)$ has
%infinitely many zeroes if and only if $d$ is even or it has exactly one 1 in
%its ternary expansion. Additional results of this nature will appear in the
%full version of this paper.


\subsection*{Acknowledgements}

    We wish to thank Noga Alon, Dave Barrington, Don Coppersmith, Nick Katz,
Neal Koblitz,
Laci Lovasz, Victor Miller, Andrew Odlyzko, Pete Winkler and Andrew Yao for
discussions. 


\begin{thebibliography}{1}
 
\bibitem{Ajt}%[Ajt]
{\sc M, Ajtai,} $\Sigma^1_1$-formulae on finite structures,
{\em Annals of Pure and Applied Logic} {\bf 24} (1983) 1-48.

\bibitem{Bab}%[Bab]
{\sc L. Babai,} A random oracle separates PSPACE from the
polynomial-time hierarchy, {\em Information Processing Letters} {\bf 26}
(1987) 51-53.

\bibitem{BBR}%[BBR]
{\sc D. M. Barrington, R. Beigel, and S. Rudich,}
Representing Boolean functions as polynomials modulo composite numbers, {\em
Proceedings of the 24th ACM Symposium on Theory of Computing} (1992)
455-461.

\bibitem{Cai}%[Cai]
{\sc J.-Y. Cai,}
With probability one, a random oracle separates PSPACE from the
polynomial-time hierarchy  {\em Journal of Computer and System Science}
{\bf 38} (1989) 68-85.

\bibitem{FSS}%[FSS]
{\sc M. Furst, J. B. Saxe and M. Sipser,} Parity,
circuits and the polynomial-time hierarchy, {\em Mathematical
Systems Theory} {\bf 17} (1984) 13-27. 

\bibitem{Gre}%[Gre]
{\sc F. Green,} An oracle separating $\oplus$P from
PP$^{\PH}$, {\em Information Processing Letters} {\bf 37} (1991) 149-153.
 
\bibitem{Has}%[Has]
{\sc J. H{\aa}stad,}
Computational limitations of small-depth circuits, the MIT press,
Cambridge, 1987.

\bibitem{IR}%[IR]
{\sc K.~Ireland and M.~Rosen,} A classical introduction
to modern number theory, Second Edition, Springer-Verlag, New York, 1990.

\bibitem{Kat}%[Kat]
{\sc N. Katz,}
Sommes Exponentielles, {\em Ast\'{e}risque}, 79, 1980.

\bibitem{Raz}%[Raz]
{\sc A. A. Razborov,} Lower bounds on the size of bounded
depth networks over a complete basis with logical addition, {\em
Matematicheskie Zametki} {\bf 41} (1987) 598-607. English translation in {\em
Mathematical Notes of the Academy of Sciences of the USSR} {\bf 41} (1987)
333-338.

\bibitem{Sch}%[Sch]
{\sc W. M. Schmidt,}
Equations over finite fields: An elementary approach, {\em Lecture Notes in 
Mathematics},
vol. 536, Springer, New York, 1976.

\bibitem{Sm}%[Sm]
{\sc R. Smolensky,} Algebraic methods in the theory of
lower bounds for Boolean circuit complexity, in {\em Proceedings of
the 19th Annual ACM Symposium on Theory of Computing} (1987) 77-82.

\bibitem{Smo}%[Smo]
{\sc C. Smorynski,} Logical Number Theory, Volume I,
Springer-Verlag, 1991.

%\bibitem{Tsai}%[Tsai]
%{\sc S.-C. Tsai},
%Lower bounds on representing Boolean functions as polynomials in $Z_m$,
%in {\em Proceedings of the Eighth Annual Conference on
%Structure in Complexity Theory}, IEEE Computer Society Press (1993) 96-101.

\bibitem{Yao}%[Yao]
 {\sc A.C. Yao,} Separating the polynomial-time hierarchy
by oracles, in {\em Proceedings of the 26th Annual IEEE Symposium on Foundations
of Computer Science} (1985) 1-10.
 
\bibitem{Zab}%{Zab}
{\sc S.~Zabek,} Sur la p{\'e}riodicit{\'e} modulo $m$ des suites de nombres ${n
\choose k}$, {\em Ann. Univ. Mariae Curie-Sklodowska}, A10 (1956) 37-47.


\end{thebibliography}
 
\end{document}
 






