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