\documentstyle[12pt, titlepage]{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 %\oddsidemargin 6pt\evensidemargin 6pt\marginparwidth 48pt\marginparsep 10pt %\topmargin -18pt\headheight 12pt\headsep 25pt\footheight 12pt\footskip 30pt %\textheight 625pt\textwidth 451pt\columnsep 10pt\columnseprule 0pt \sloppy %*********** \newcounter{savenumi} \newenvironment{savenumerate}{\begin{enumerate} \setcounter{enumi}{\value{savenumi}}}{\end{enumerate} \setcounter{savenumi}{\value{enumi}}} \newtheorem{theoremfoo}{Theorem} \newenvironment{theorem}{\pagebreak[1]\begin{theoremfoo}}{\end{theoremfoo}} \newtheorem{propositionfoo}[theoremfoo]{Proposition} \newenvironment{proposition}{\pagebreak[1]\begin{propositionfoo}} {\end{propositionfoo}} \newtheorem{lemmafoo}[theoremfoo]{Lemma} \newenvironment{lemma}{\pagebreak[1]\begin{lemmafoo}}{\end{lemmafoo}} \newtheorem{corollaryfoo}[theoremfoo]{Corollary} \newenvironment{corollary}{\pagebreak[1]\begin{corollaryfoo}} {\end{corollaryfoo}} \newtheorem{dfntn}[theoremfoo]{Definition} \newenvironment{definition}{\pagebreak[1]\begin{dfntn}\rm}{\end{dfntn}} \newenvironment{proof} {\pagebreak[1]{\narrower\noindent {\bf Proof:\quad\nopagebreak}}}{\QED} \renewcommand{\labelenumi}{\roman{enumi}.} \newcommand{\yyskip}{\penalty-50\vskip 5pt plus 3pt minus 2pt} \newcommand{\blackslug}{\hbox{\hskip 1pt \vrule width 4pt height 8pt depth 1.5pt\hskip 1pt}} \newcommand{\QED}{{\penalty10000\parindent 0pt\penalty10000 \hskip 8 pt\nolinebreak\blackslug\hfill\lower 8.5pt\null} \par\yyskip\pagebreak[1]} \newcommand{\romanitems}{\renewcommand{\labelenumi} {\mbox{(}\/\roman{enumi}\/\mbox{)}}} \newcommand{\Pe}{{\rm P}} \newcommand{\num}{{\rm\#}} \newcommand{\numP}{{\rm\#\Pe}} \newcommand{\NP}{{\rm NP}} \newcommand{\FP}{{\rm FP}} \newcommand{\GapP}{{\rm GapP}} \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{\EP}{{\rm C}_=\Pe} \newcommand{\MEP}{{\rm M}_=\Pe} \newcommand{\MP}{{\rm MP}} % From Jim Royer --KWR % The following is a terrible hack, but it works---usually. \newcommand{\parityP}{{\mathchoice{\raisebox{1pt}{$\displaystyle\oplus$}{\rm P}}{\raisebox{1pt}{$\textstyle\oplus$}{\rm P}}{\raisebox{1pt}{$\scriptstyle\oplus$}{\rm P}}{\raisebox{1pt}{$\scriptscriptstyle\oplus$}{\rm P}}}} \newcommand{\pair}[2]{\langle #1,#2\rangle} \newcommand{\triple}[3]{\langle #1,#2,#3\rangle} \newcommand{\zetabar}{\overline \zeta} \newcommand{\omegabar}{\overline \omega} \newcommand{\M}{\mbox {\rm M}} \newcommand{\U}{\mbox {\rm U}} \newcommand{\nat}{{\rm {\bf N}}} \newcommand {\Z} {{\rm {\bf Z}}} \newcommand{\Zalg} {\overline {\bf Z}} \newcommand{\T}{\mbox {\rm T}} \newcommand{\ES}{\mbox {\rm S}} \begin{document} \title{Complex Fourier Technique for Lower Bounds on the Mod-m Degree \footnote{Revised and expanded version of ``Lower Bounds for Depth-Three Circuits with Equals and Mod-Gates,'' in {\it 12th Annual Symposium on Theoretical Aspects of Computer Science}, Springer-Verlag (1995) 71-82.}} \author{ Frederic Green \\{\small Department of Mathematics and Computer Science} \\{\small Clark University} \\{\small Worcester, Massachusetts 01610} \\{\small {\tt fgreen@black.clarku.edu}} } \date{} \maketitle \begin{abstract} We say an integer polynomial $p$, on Boolean inputs, weakly $m$-represents a Boolean function $f$ if $p$ is non-constant and is zero (mod $m$), whenever $f$ is zero. In this paper we prove that if a polynomial weakly $m$-represents the Mod$_q$ function on $n$ inputs, where $q$ and $m$ are relatively prime and $m$ is otherwise arbitrary, then the degree of the polynomial is $\Omega(n)$. This generalizes previous results of Barrington, Beigel and Rudich (Computational Complexity {\bf 4} (1994), pp.~367-382) and Tsai (Structures 1993, pp. 96-101), which held only for constant or slowly growing $m$. In addition, the proof technique given here is quite different. We use a method (adapted from Barrington and Straubing, (Computational Complexity {\bf 4} (1994), pp.~325-338) in which the inputs are represented as complex $q^{th}$ roots of unity. In this representation it is possible to compute the Fourier transform using some elementary properties of the algebraic integers. As a corollary of the main theorem and the proof of Toda's theorem, if $q,p$ are distinct primes, any depth-three circuit which computes the $\Mod_q$ function, and consists of an exact threshold gate at the output, $\Mod_p$-gates at the next level, and AND-gates of polylog fan-in at the inputs, must be of exponential size. We also consider the question of how well circuits consisting of one exact gate over ACC($p$)-type circuits (where $p$ is an odd prime) can approximate parity. It is shown that such circuits must have exponential size in order to agree with parity for more than $1/2 + o(1)$ of the inputs. \end{abstract} \section{Introduction} One of the challenges facing circuit complexity is to prove lower bounds on bounded-depth circuits with $\Mod_m$ gates (that determine if the sum of the inputs is not divisible by the number $m$). If $m$ is prime, exponential lower bounds are known for general bounded-depth circuits including AND's and OR's in addition to the MOD's~\cite{Sm}. Unfortunately the proof techniques for these results make essential use of the fact that $\Z/m\Z$ is a field if $m$ is prime, and the situation for composite $m$ (in which case $\Z/m\Z$ is a ring which is not even an integral domain) has proved to be more difficult. Algebraic or combinatorial techniques other than those used in~\cite{Sm} or~\cite{Raz} appear to be necessary. Recently, progress has been made in the simple but important case of a single $\Mod_m$-gate over small AND's~\cite{BBR}, \cite{Tsai}. This paper, for the most part, continues this line of investigation. Since this computational model is really based on polynomials, we formulate the problem accordingly. Let $p : \{0,1\}^n \rightarrow \Z$ be an integer polynomial, and $q, m \ge 2$ be relatively prime natural numbers. What is the minimum degree of $p$ such that for all $(x_1,...,x_n) \in \{0,1\}^n$, $p(x_1,...,x_n) \equiv 0~~(m)$ iff $\sum_{i=1}^n x_i$ is divisible by $q$? This question was studied by Barrington, Beigel and Rudich~\cite{BBR}, and, in subsequent work, by~\cite{Tsai}. The strongest lower bound, obtained by Tsai, states that the polynomial must have degree linear in $n$. Analysis of the proofs of these previous results shows that they are valid only if $m$ is a constant or a slowly growing function of $n$. But what if $m$ is some arbitrary function of $n$, where the only constraint on $m$ is that it is prime to $q$? This question has a number of motivations, which are discussed below. It is also of some intrinsic interest, since allowing $m$ to vary in this way gives a considerably stronger computational model. Intuitively it would make sense that the degree lower bound has nothing to do with $m$'s dependence on $n$, and is only due to the relative primality of $q$ and $m$. However, it is not clear how the techniques of~\cite{BBR} and~\cite{Tsai} can be adapted to handle this more general case. In this paper we introduce an alternative technique which can. Here we therefore consider a generalization of the problems studied in \cite{BBR}, \cite{Tsai}. The most significant lower bounds will be for the {\it modulo} functions, \[ \Mod_{m,r}(x_1,...,x_n) = \left\{ \begin{array}{ll} 0 & \mbox{if $\sum_{i=1}^n x_i \equiv r~(m)$} \\ 1 & \mbox{otherwise,} \end{array} \right. \] or their negations (for example, a $\Mod_m$ gate computes the function $\Mod_{m,0}$). Let $f$ be any Boolean function on $n$ inputs. We say an integer polynomial $p$ on $n$ Boolean inputs {\it $m$-represents} $f$ if for all input settings of $x_1,...,x_n$, $f(x_1,...,x_n) = 0$ iff $p(x_1,...,x_n) \equiv 0~(m)$. The {\it Mod$_m$-degree} of $f$ is the smallest degree of a polynomial which $m$-represents $f$. The {\it Mod-degree} of $f$ is the smallest Mod$_m$-degree of $f$ for any $m$. Let $f_q$ be any one of the functions $\Mod_{q,r}$ or $\neg \Mod_{q,r}$. Define the {\it relatively prime Mod-degree} (or {\it rp-Mod-degree}, for short) of $f_q$ as the smallest Mod$_m$-degree of $f_q$ for any $m$ which is relatively prime to $q$. Some functions have large Mod-degrees (for example, the AND function; see Proposition~\ref{and-mod-degree} below). Trivially, the Mod-degree of any $f_q$ is 1. Our main theorem is, \begin{theorem}\label{main-theorem-w} For any $n \in \nat$, the rp-Mod-degree of any of the functions $\Mod_{q,r}(x_1,$ $...$ $,x_n)$ or $\neg \Mod_{q,r}(x_1,$ $...$ $,x_n)$ is at least $\lfloor {n \over 2(q-1)} \rfloor$. \end{theorem} Actually a stronger result is proved. Introducing terminology analogous to that of~\cite{ABFR}, say a polynomial {\it weakly} $m$-represents a Boolean function $f$ if $p$ is not a constant function and $f(x_1,...,x_n) = 0 \Longrightarrow p(x_1,...,x_n) \equiv 0~(m)$. The {\it weak Mod$_m$-degree} and the {\it weak rp-Mod-degree} are defined in the obvious ways. Theorem~\ref{main-theorem-s} in section 3 of this paper says that the weak rp-Mod-degree of the modulo functions is $\Omega(n)$. As a by-product (see Corollary~\ref{not-mod-m}), we present a new proof that, if $m$ is independent of $n$ and is not a prime power, the minimal degree of a polynomial which $m$-represents the $\neg \Mod_m$ function is $\Omega(n)$, a result originally obtained in \cite{Tsai}. Another application of this stronger version (in the special case of $q=2$) is described below. The proof strategy is substantially different than those used in \cite{BBR} and \cite{Tsai}. We make use of the representation of Boolean inputs by complex roots of unity, introduced by Barrington and Straubing \cite{BS}. There the goal was to show that the {\it sign} of $p$ could not agree with $\Mod_{q,r}$. Related results, via similar techniques, for lower bounds on circuits consisting of one threshold over $\Mod_q$ gates, have been obtained recently by Krause and Pudl{\'a}k~\cite{KP}. As in this previous work, the formulation in terms of roots of unity permits the application of the powerful technique of spectral analysis. The main difference between the setting here and that of \cite{BS} and~\cite{KP} is that here we work in a finite ring (i.e., $\Z / m\Z$) rather than an infinite field (i.e., the complex numbers). As we will see, this requires the explicit use of some elementary properties of rings of algebraic integers. In \cite{BS}, it is shown that the sign of a low-degree polynomial can't agree with $\Mod_{q,r}$ even for a constant fraction of the input settings. We prove a similar result that, for odd prime $p$, a low-degree polynomial cannot $p^k$-represent the parity function for more than a fraction $1/2 + o(1)$ of all input settings (Theorem~\ref{Approxmdegree}, in section 5). Strong lower bounds on approximately $m$-representing parity for any odd $m$, or on approximately $m$-representing Mod$_q$ for any relatively prime $q$ and $m$, remain open. The topic of this paper was originally motivated by some questions about depth-three circuits involving both threshold and mod gates. As is well known, threshold and parity gates are a potent combination. Inspired by Toda's theorem \cite{Toda} that $\PP^{\PH} \subseteq \PP^{\parityP}$, Allender \cite{Allender} showed that any quasi-polynomial size ``generalized perceptron," consisting of a threshold gate over AC$^{(0)}$-type circuits, can be simulated by a quasi-polynomial-size depth-three circuit consisting of a threshold gate at the root, parity gates at the next level and AND gates of polylog fan-in connected to the inputs (which we refer to here as ``threshold-of-$\oplus^+$" circuits; see section 2 for notation). On the negative side, drawing on work of Hajnal et al.~\cite{HMPST} and Boppana and H{\aa}stad \cite{Has}, it was shown in \cite{Gre} that small generalized perceptrons cannot compute the parity function (in terms of complexity classes, that there is an oracle $A$ such that $\parityP^A \not \subseteq \PP^{\PH^A}$). Improvements and generalizations have appeared in \cite{Bei92}, \cite{BRS}, \cite{BS}. However, as of this writing, no non-polynomial lower bounds are known for the more powerful threshold-of-$\oplus^+$ circuits (and hence no oracle is known separating $\PP^{\parityP}$ from PSPACE). In fact the best one can do, by Smolensky's theorem~\cite{Sm}, is $\Omega(n^{1/2-o(1)})$ for threshold-of-$\Mod_q^+$ circuits computing parity ($q$ an odd prime). Although this problem has not received as much press as the ACC problem~\cite{Bar}, it shares at least some of its difficulty. Some progress has been made in a restricted version of the problem in \cite{CGT}, in which the functions computed by the parity sub-circuits are symmetric. Here we consider a different kind of restriction: the parity sub-circuits are general, but the top gate is an ``exact threshold" or ``exact" gate (the resulting circuits are called ``exact-of-$\oplus^+$" circuits). In terms of Turing machine complexity classes, we thus consider the relativized power of classes such as $\EP^{\parityP}$. While the resulting problems appear to be considerably simpler than those associated with $\PP^{\parityP}$, it is hoped that some insight will be gained towards attacking the more general problem. The natural conjecture is that if $q$ and $p$ are distinct primes, an exact-of-$\Mod_p^+$ circuit which computes the $\Mod_q$ function would have to be of exponential size. We prove this in section 4. By the proof of the second part of Toda's theorem (see Theorem~\ref{circuit-sim}), this problem easily reduces to Theorem~\ref{main-theorem-w}. How well can an exact-of-$\Mod_p^+$ circuit {\it approximate} $\Mod_q$? We can answer this question for $q=2$, and indeed, building on the main result and extending some known techniques, obtain an improvement of part of Smolensky's theorem about ACC($p$)-type circuits for odd prime $p$. We find that exact-of-ACC($p$) circuits can equal the parity function for at most $1/2 + o(1)$ of the inputs, unless they are of exponential size. This is a consequence of Theorem~\ref{Approxmdegree} (mentioned above) and one of Smolensky's lemmas, and its proof is also given in section 5. In section 6, we show how these results translate to oracle separations of polynomial-time Turing machine counting classes. \section{Preliminaries and Notation} It is assumed the reader has some familiarity with circuit complexity and polynomial-time complexity classes as in, e.g., \cite{BDG}. More detailed background can be found in \cite{Str} and \cite{Bei93}. Following the convention of \cite{GKRST}, if $G$ is a Boolean gate, $G^+$ denotes a family of circuits with $G$ at the root and AND gates of polylog fan-in at the input level. If $G$ is a Boolean gate and ${\cal C}$ is a circuit class, $G$-of-${\cal C}$ denotes the class of circuits with ${\cal C}$-type circuits serving as inputs to $G$-type gates. Examples of these notations were given in the introduction. It should be noted that the size of the ${\cal C}$ subcircuits is to be regarded as a function of the number of inputs to the global $G$-of-${\cal C}$ circuit. An {\it exact} gate over $n$ Boolean inputs $x_1,...,x_n$ with weights $w_i \in \Z$ ($1 \le i \le n$) and threshold $t \in \Z$, returns 1 iff $\sum_{i=1}^n w_i x_i = t$. We interpret the term $w_i x_i$ as a sum of $|w_i|$ identical inputs $x_i$, so that the quantity $\sum_{i=1}^n |w_i|$ is called the {\it size} of the exact gate. Thus in an exact-of-${\cal C}$ circuit, the size of the exact gate is the number of subcircuits of type ${\cal C}$, including repetitions. (This convention simplifies the statements of the results. If we called $n$ the size and $\sum_{i=1}^n |w_i|$ the weight, the results would have to be expressed as tradeoffs between size and weight.) For the purposes of this paper, one may assume that the inputs $x_i$ to an exact gate are never negated. Since ${\overline x_i} = 1-x_i$, negations can be implemented by choosing $w_i$ to be negative and adjusting the threshold $t$ appropriately; the proof methods used here are independent of $t$. A circuit family is of type ACC($p$) if it is of bounded depth and each circuit in the family has AND, OR and Mod$_p$-gates. If $R$ is a ring and $m \in \nat$, $a \equiv b~(mR)$ means that for some $x \in R$, $a = b + mx$. When it is clear that $R = \Z$, we use the notation $a \equiv b~(m)$. As usual, $R/mR$ denotes the residue class ring of $R$ modulo $R$-multiples of $m$. The proof of the main theorem makes use of the ring of {\it algebraic integers}, which we denote\footnote{There is apparently no standard notation for all the algebraic integers. They constitute the {\it integral closure} of ${\bf Z}$ in the field of algebraic numbers (which in turn is the {\it algebraic} closure of the rationals). The notation here is chosen to suggest the integral closure of ${\bf Z}$.} by $\Zalg$. Most algebra or number theory texts discuss the subject (see, for example, \cite{IR} (chapter 6) for a compact treatment, including proofs, of all the relevant notions). For the sake of completeness, the definition and the necessary facts that are used in this paper are included here. An algebraic integer is a complex root of an integer polynomial (i.e., one with integer coefficients) in which the leading coefficient is one. For example, the roots of the polynomial $z^n - 1$ (i.e., the complex $n^{th}$ roots of unity) are algebraic integers. It is straight-forward (although not trivial) to prove that $\Zalg$ is a ring under complex addition and multiplication. Crucial for this paper is the elementary property that an algebraic integer is a rational number if and only if it is a rational integer. Because of this fact, the notation $a \equiv b~~(m)$ means $a \equiv b~~(m\Zalg)$ as well as $a \equiv b~~(m{\Z})$ if $a$ and $b$ are integers. Nevertheless, we usually resort to the more precise notations $a \equiv b~~(m\Zalg)$ or $a \equiv b~~(m{\Z})$. \section{Lower Bounds for the rp-Mod-degree of Modulo Functions} We start by reviewing the formulation of \cite{BS} to express circuit inputs as complex roots of unity. Let $q$ be a natural number $\ge 2$ and $\zeta$ denote the primitive complex root of unity $e^{2\pi i \over q}$ ($q$ will be fixed in this section). Let $D = \{1, \zeta, \zeta^2,...,\zeta^{q-1} \}$. Note that \[ \sum \limits_{y \in D} y^k = \left\{ \begin{array}{ll} q & \mbox{if $k \equiv 0 ~~(q)$} \\ 0 & \mbox{otherwise.} \end{array} \right. \] We will consider polynomials over $n$ variables $y_1,...,y_n \in D$. Let $V$ denote $\{0,...,q-1\}$. Since $y^q = 1$ for any $y \in D$, a monomial will have the general form $\prod_{i \in S_{{\bf e}}} y_i^{e_i}$, where ${\bf e} \in V^n$, and by definition $S_{{\bf e}}$ denotes the set $\{i | e_i \not = 0\}$. Define $\prod_{i \in \emptyset} y_i^{e_i} = 1$. The integer $|S_{{\bf e}}|$ is called the {\it weight} of the monomial. The first crucial observation to make here is that the sum of a monomial of non-zero weight less than $n$ over all values of the $y_i$'s subject to the constraint $\prod_{i=1}^n y_i = \zeta^r$ (for any integer $r$) is zero. Let ``${\bf y}:\prod y = \zeta^r$" denote that ${\bf y} \in D^n$ varies subject to the constraint $\prod_{i=1}^n y_i = \zeta^r$. \begin{lemma}\label{zero} Let $r, n$ be integers. Let $e_i$ ($i \in \{1,...,n\}$) be integers such that for each $i$, $0 \le e_i \le q-1$. Define $S_{{\bf e}}$ as above and suppose $|S_{{\bf e}}| < n$. Then \[ \sum \limits_{{\bf y}:\prod y = \zeta^r} \prod \limits_{i \in S_{{\bf e}}} y_i^{e_i} = \left\{ \begin{array}{ll} q^{n-1} & \mbox{if $S_{{\bf e}} = \emptyset$} \\ 0 & \mbox{otherwise.} \end{array} \right. \] \end{lemma} \begin{proof} If $S_{{\bf e}} = \emptyset$, the result is obvious. Suppose $S_{{\bf e}} \not = \emptyset$. Since $|S_{{\bf e}}| < n$, there is an $i' \in \{1,...,n\} - S_{{\bf e}}$. The constraint $\prod_{i=1}^n y_i = \zeta^r$ is equivalent to, $$ y_{i'} = \zeta^r \cdot \prod_{i \not = i'} y^{-i}.$$ This determines $y_{i'}$ uniquely in terms of the other $y_i$'s. We can then perform the sum over the $y_i$'s ($i \not = i'$) independently. Hence for any $i \in S_{{\bf e}}$, the sum has a factor, $$ \sum \limits_{y_i \in D} y_i^{e_i},$$ which is zero, since $e_i \not \equiv 0~(q)$. \end{proof} %\begin{proof} If $S_{{\bf e}} = \emptyset$, the result is obvious. Suppose %$S_{{\bf e}} \not = \emptyset$. Let $y_i = \zeta^{k_i}$ for each $i$. %Since $|S_{{\bf e}}| < n$, there is an $i' \in \{1,...,n\} - S_{{\bf %e}}$. The constraint $\prod_{i=1}^n y_i = \zeta^r$ is equivalent to, $$ %\sum \limits_{i=1}^n k_i \equiv r~~(q).$$ This determines $k_{i'}$ %uniquely in terms of the other $k_i$'s. We can then perform the sum over %the $k_i$'s ($i \not = i'$) independently. Hence for any $i \in S_{{\bf %e}}$, the sum has a factor, %$$ \sum \limits_{k_i=0}^{q-1} \zeta^{k_i e_i},$$ %which is zero, since $e_i \not \equiv 0~(q)$. %\end{proof} For any integer $r$, it will be convenient to define the $r$-{\it inner product} $\langle f, g \rangle_r$ for functions $f,g$ over $D^n$ as, $$ \langle f, g \rangle_r = {1 \over q^{n-1}} \sum \limits_{{\bf y}: \prod y = \zeta^r} {\overline f}(y_1,...,y_n) g(y_1,...,y_n).$$ Lemma~\ref{zero} says that $\langle 1, \prod_{i \in S_{{\bf e}}} y_i^{e_i} \rangle_r$ is zero unless $S_{{\bf e}}= \emptyset$, in which case it is 1. More generally, the set of monomials of weight $< n/2$, under the $r$-inner product, form an orthonormal basis for polynomials of weight $< n/2$ over $D^n$. \begin{lemma}\label{ortho} Let ${\bf e'},{\bf e} \in V^n$ and $|S_{{\bf e}} \cup S_{{\bf e'}}| < n$. Then, \[ \left \langle \prod \limits_{i \in S_{{\bf e}'}} y_i^{e'_i}, \prod \limits_{i \in S_{\bf e}} y_i^{e_i} \right \rangle_r = \left\{ \begin{array}{ll} 1 & \mbox{if ${\bf e} = {\bf e}'$} \\ 0 & \mbox{otherwise.} \end{array} \right. \] \end{lemma} \begin{proof} Define, $$S({\bf e}, {\bf e}') = \left \langle \prod \limits_{i \in S_{{\bf e}'}} y_i^{e'_i}, \prod \limits_{i \in S_{\bf e}} y_i^{e_i} \right \rangle_r.$$ The inner product can be written as, $$ S({\bf e}, {\bf e}') = {1 \over q^{n-1}} \sum \limits_{{\bf y} : \prod y = \zeta^r} \prod \limits_{i \in S_{{\bf e}'} - S_{\bf e}} y_i^{q-e'_i} \prod \limits_{i \in S_{\bf e} - S_{{\bf e}'}} y_i^{e_i} \prod \limits_{i \in S_{{\bf e}'} \cap S_{\bf e}} y_i^{e_i-e'_i}. $$ Because $|S_{\bf e} \cup S_{{\bf e}'}| < n$, we can apply Lemma~\ref{zero}. By that lemma, if $S_{\bf e} \Delta S_{{\bf e}'} \not = \emptyset$, $S({\bf e}, {\bf e}') = 0$. If $S_{\bf e} \Delta S_{{\bf e}'} = \emptyset$, $S({\bf e}, {\bf e}') = 0$ unless ${\bf e} = {\bf e}'$. If ${\bf e} = {\bf e}'$ then the sum is $q^{n-1}$, so $S({\bf e}, {\bf e}') = 1$. \end{proof} The main result concerns integer polynomials which take on values in the ring ${\Z}/ m{\Z}$ for some $m$. Because we work with inputs that are roots of unity, we will find it necessary, in proving the main theorem, to consider {\it algebraic} integer polynomials with values in ${\Z}/ m{\Z}$. For the moment, we consider the even more general case of polynomials with algebraic integer coefficients and values in $\Zalg / m\Zalg$\footnote{This is the simplest approach, although it should be pointed out that it is possible to work in the finite ring $\Z[\zeta]/m\Z[\zeta]$. See section 7 for a brief discussion.}. In the following lemma, we show, for such a polynomial $t:D^n \rightarrow \Zalg$ of weight $< n/2$, that we can solve for the coefficients in terms of special values of $t$, namely, exactly those values of $t(y_1,...,y_n)$ such that $\prod_{i=1}^n y_i = \zeta^r$, for any $r$. This set of coefficients (the $c_{\bf e}$'s in equation~\ref{eq:f_transform} below) is called the Fourier transform of $t$. Thus the lemma gives a particular method for computing the Fourier transform when the polynomial has weight $< n/2$. The idea of the proof of the main theorem is to use this lemma to show that the Fourier transform is zero if $t(y_1,...,y_n) \equiv 0~~(m)$ for the indicated values of ${\bf y}$. \begin{lemma}\label{coeff-solution} Let $m$ be a natural number relatively prime to $q$. Suppose $t:D^n \rightarrow \Zalg/m\Zalg$ is a polynomial with algebraic integer coefficients and weight $< n/2$, i.e., of the form, \begin{eqnarray}\label{eq:f_transform} t(y_1,...,y_n) \equiv \sum \limits_{{\bf e} \in V^n : |S_{{\bf e}}| < n/2} c_{\bf e} \prod \limits_{i \in S_{\bf e}} y_i^{e_i}~~(m\Zalg) \end{eqnarray} where $c_{\bf e} \in \Zalg$. Then for any natural number $r$ and ${\bf e} \in V^n$ with $|S_{{\bf e}}| < n/2$, \begin{eqnarray}\label{eq:f_inverse} c_{\bf e} \equiv \langle \prod \limits_{i \in S_{\bf e}} y_i^{e_i}, t(y_1,...,y_n) \rangle_r~~(m\Zalg). \end{eqnarray} \end{lemma} \begin{proof} Note that since $q$ and $m$ are relatively prime, $q$ has an inverse in $\Z/m\Z$, and hence also in $\Zalg/m\Zalg$. Hence the $r$-inner product is well-defined in $\Zalg/m\Zalg$. Let ${\bf e}' \in V^n$ be such that $|S_{{\bf e}'}| < n/2$. Take the $r$-inner product of both sides of equation~(\ref{eq:f_transform}) with $\prod_{i \in S_{{\bf e}'}} y_i^{e'_i}$. We obtain, \begin{eqnarray*} \langle\prod \limits_{i \in S_{{\bf e}'}} y_i^{e'_i}, t(y_1,...,y_n) \rangle_r \equiv \sum \limits_{{\bf e} \in V^n : |S_{\bf e}| < n/2} c_{\bf e} \langle \prod \limits_{i \in S_{{\bf e}'}} y_i^{e'_i}, \prod \limits_{i \in S_{\bf e}} y_i^{e_i} \rangle_r~~(m\Zalg). \end{eqnarray*} Note $|S_{{\bf e}'} \cup S_{{\bf e}}| < n$. Apply Lemma~\ref{ortho} to the above equation to obtain equation~(\ref{eq:f_inverse}). \end{proof} We now state and prove the main theorem. Theorem~\ref{main-theorem-w} is then immediate. \begin{theorem}\label{main-theorem-s} Let $q$ and $N$ be natural numbers. Let $p : \{0, 1\}^N \rightarrow {\Z}$ be a polynomial over the Boolean variables $x_1,...,x_N$ with integer coefficients, and let $m \in {\nat}$ be such that $q$ and $m$ are relatively prime. Suppose that for some integer $0 \le r \le q-1$, for any $x_1,...,x_N$ it holds that, $$ \sum \limits_{i=1}^N x_i \equiv r~~(q) \Longrightarrow p(x_1,...,x_N) \equiv 0~~(m),$$ and that $p$ is not a constant function mod $m$. Then the degree of $p$ is at least $\lfloor {N \over 2(q-1)} \rfloor$. \end{theorem} \begin{proof} The result is trivial if $N < 2(q-1)$, so suppose wlog that $N \ge 2(q-1)$. Let $d$ be the degree of the polynomial $p$. Suppose $d < \lfloor {N \over 2(q-1)} \rfloor$. Then we will show that, under the given hypotheses, $p$ is always zero mod $m$. Define $\zeta$, $D, V$ as in the discussion above. Exactly as in \cite{BS}, we restrict the input settings so that $p$ can be regarded as a polynomial over inputs in $D$. For this purpose, assume wlog that $(q-1) | N$; other values of $N$ can be reduced to this by restricting $< q-1$ of the inputs to 1 (this is the origin of the floor in the degree lower bound). Let $n = {N \over q-1}$. Group the $N$ inputs into $n$ sets of size $q-1$, each of the form $\{x_{(q-1)i+1},...,x_{(q-1)i + q - 1}\}$ with $0 \le i \le n - 1$. Let $y_1,...,y_n$ be $n$ inputs each taking on values in $D$. Define the polynomials mentioned in \cite{BS} (though not written down explicitly), %$$ u_j(y) = 1 - \prod \limits_{l=0}^{q-1-j} % (1 - {1 \over q} \sum \limits_{i=0}^{q-1} \zeta^{il} y^i),$$ $$ u_j(y) = {1 \over q} \sum \limits_{i=0}^{q-1} \sum \limits_{l=j+1}^q \zeta^{-il} y^i, $$ for $y \in D$ and $1 \le j \le q-1$. Writing $y = \zeta^s$, with $1 \le s \le q$, it is easy to verify that $u_j(y) = 0$ if $j \ge s$ and $u_j(y) = 1$ if $j < s$. Thus $u_1(y)u_2(y)...u_{q-1}(y)$, regarded as a string of bits, is $1^{s-1}0^{q-s}$. Restricting the input settings appropriately, we can then encode $y_i$ as the string $x_{(q-1)i+1}x_{(q-1)i+2}...x_{(q-1)i+q-1}$ by setting $$ x_{(q-1)i+j} = u_j(y_{i+1})$$ for $0 \le i \le n -1$ and $1 \le j \le q-1$. Writing $y_i = \zeta^{s_i}$ for $1 \le i \le n$, note that, $$ \sum \limits_{j=1}^{q-1} x_{(q-1)i + j} = s_i -1, $$ and therefore, \begin{eqnarray}\label{eq:mod-equiv} \sum \limits_{i=1}^N x_i \equiv r~(q) ~~{\mbox {\it iff}}~~ \sum \limits_{i=1}^n (s_i - 1) \equiv r~(q) ~~{\mbox {\it iff}}~~ \prod \limits_{i=1}^n y_i = \zeta^{n+r}. \end{eqnarray} Up to this point, the argument has followed the one given in \cite{BS}. However we must now remember that we are working in ${\Z}/ m{\Z}$, while the polynomials $u_j$ have coefficients which are not necessarily integers. Therefore instead of computing the polynomial $p(x_1,...,x_N)$ mod $m{\Z}$, we compute it mod $m \Zalg$. Since $p(x_1,...,x_N) \equiv 0~~(m{\Z})$ iff $p(x_1,...,x_N) \equiv 0~~(m\Zalg)$, we lose no generality in doing this. Recall from the proof of Lemma~\ref{coeff-solution} that $q$ has an inverse in $\Zalg/m\Zalg$. Thus, working in $\Zalg/m\Zalg$, we regard $u_j$ as a polynomial of degree at most $q-1$ (and weight at most 1) with algebraic integer coefficients. Using the $u_j$'s we can define a polynomial $t:D^n \rightarrow {\Z}$ with coefficients in $\Zalg$ which agrees with $p$ when the $x_i$'s encode $y_i$'s according to the above scheme: $$ t(y_1,...,y_n) \equiv p(u_1(y_1),...,u_{q-1}(y_1),..., u_1(y_n),...,u_{q-1}(y_n))~~(m\Zalg).$$ Note that by the construction of $t$ and relation (\ref{eq:mod-equiv}), \begin{eqnarray}\label{eq:t-constraint} \prod_{i=1}^n y_i = \zeta^{n+r} \Longrightarrow t(y_1,...,y_n) \equiv 0~~(m\Zalg). \end{eqnarray} It is easy to see that the {\em weight} of any monomial in $t$ is at most $d$, the degree of $p$. Note that $d < \lfloor {N \over 2(q-1)} \rfloor = \lfloor {n \over 2} \rfloor$ and hence $d < {n \over 2}$. Thus $t$ fulfills the requirements of Lemma~\ref{coeff-solution}. We solve for the coefficients $c_{\bf e}$ of $t$ by that lemma: $$ c_{\bf e} \equiv \langle \prod \limits_{i \in S_{\bf e}} y_i^{e_i}, t(y_1,...,y_n) \rangle_{n+r}~~(m\Zalg).$$ By implication (\ref{eq:t-constraint}), every term on the right hand side is zero. Hence for any ${\bf e}$, $c_{\bf e} \equiv 0~(m\Zalg)$, from which we conclude that for any $y_1,...,y_n \in D$, $t(y_1,...,y_n) \equiv 0~~(m\Zalg)$ and therefore, since $t(y_1,...,y_n)$ is an integer, $t(y_1,...,y_n)$\break $\equiv 0~~(m{\Z})$. This immediately implies that $p(x_1,...,x_N) \equiv 0~~(m)$ for those $q^n$ input settings of the $x_i$'s that encode $y_i$'s. By re-labeling the $x_i$'s and repeating the argument for each re-labeling we conclude that $p(x_1,...,x_N) \equiv 0~~(m)$ for all $2^N$ settings of the $x_i$'s. \end{proof} \begin{corollary}\label{not-mod-m} {\mbox{\rm [Tsai]}} Suppose $m$ is fixed and is not a prime power, and let $q_{max}^e$ be the largest prime power dividing $m$. Then any polynomial which $m$-represents $\neg \Mod_m$ must have degree at least $\lfloor {n \over 2 q_{max}^e} \rfloor$. \end{corollary} \begin{proof} Let $p$ be a polynomial of degree less than $\lfloor {n \over 2q_{max}^e} \rfloor$ which $m$-represents $\neg \Mod_m$. For any prime factor $s$ of $m$, let $e(s) = ord_s(m)$, i.e., $e(s)$ is the greatest integer such that $s^{e(s)}$ divides $m$. Let $r, s$ be two distinct prime factors of $m$. Since $\sum_{i=1}^n x_i \not \equiv 0~(m) \Longrightarrow p(x_1,...,x_n) \equiv 0~(m)$, it follows that, $$\sum \limits_{i=1}^n x_i \not \equiv 0~(s^{e(s)}) \Longrightarrow p(x_1,...,x_n) \equiv 0~(r^{e(r)}).$$ Since the degree of $p$ is less than $\lfloor {n \over 2 s^{e(s)}} \rfloor$, it follows from Theorem~\ref{main-theorem-s} that $p$ is the zero function mod $r^{e(r)}$. As this holds for any prime divisor $r$ of $m$, we conclude that $p$ is identically zero mod $m$, which is a contradiction. \end{proof} \section{Simulations and Lower Bounds for Exact-of-$\Mod_p^+$ Circuits} Let $p$ be a prime. The main result of this section is that the negation of any exact-of-$\Mod_p^+$ circuit of size $2^{n^{\epsilon}}$ (with $\epsilon < 1$) can be $p^s$-represented, for some $s \in \nat$, by a polynomial of sub-linear degree. By Theorem~\ref{main-theorem-w}, such a polynomial cannot $p^s$-represent $\Mod_{q,r}$ or $\neg \Mod_{q,r}$ if $q$ is a prime $\not = p$. Hence exact-of-$\Mod_p^+$ circuits of size $2^{n^{\epsilon}}$ cannot compute these functions. \begin{theorem}\label{circuit-sim} Fix any real number $\epsilon < 1$. Let $p$ be a prime, and $\{C_n\}$ a family of exact-of-$\Mod_p$-of-AND circuits of size less than $2^{n^{\epsilon}}$ and with bottom fan-in $o(n^{1-\epsilon})$. Then for any $n$, for some $s \in \nat$, $\neg C_n$ can be $p^s$-represented by a polynomial of degree $o(n)$. \end{theorem} \begin{proof} We follow the proof of the second part of Toda's theorem, as applied to circuits as in \cite{BT}. We make use of the {\em modulus-amplifying} polynomials $Q_d$, which have the property that for every $m\geq1$ and $X\geq0$, \begin{eqnarray*} X\equiv0~(m)&\Rightarrow&Q_d(X)\equiv0~(m^d), \\ X\equiv1~(m)&\Rightarrow&Q_d(X)\equiv1~(m^d). \end{eqnarray*} (The modulus-amplifying polynomials constructed by Beigel and Tarui~\cite{BT} have degree $2d-1$.) Denote the $i$-th $\Mod_p$-of-AND subcircuit of $C_n$ by $s_i$. By hypothesis, for some $k$ where $k \le 2^{n^{\epsilon}}$, $C_n$ outputs 1 iff $\sum_{i=1}^k s_i = \ell$, for some integer $\ell$. In turn, $s_i$ outputs 1 iff a certain sum of AND gates is nonzero mod $p$. Denote this sum by $\sigma_i(x_1,...,x_n)$, so that $s_i$ outputs 1 iff $\sigma_i(x_1,...,x_n) \not \equiv 0~(p)$. Since the AND gates have fan-in $o(n^{1-\epsilon})$, $\sigma_i(x_1,...,x_n)$ is a polynomial in the inputs of degree $o(n^{1-\epsilon})$. Without loss of generality, we may assume that $\sigma_i(x_1,...,x_n)$ mod $p$ is always either 0 or 1 (this can be assured by raising $\sigma_i$ to the power $p-1$ and invoking Fermat's little theorem; the powering only multiplies the degree of $\sigma_i$ by the constant $p-1$). Now by the properties of $Q_d$ given above, \begin{eqnarray*} \sigma_i(x_1,...,x_n)\equiv0~(p)&\Rightarrow& Q_{n^{\epsilon}}(\sigma_i(x_1,...,x_n))\equiv0~(p^{n^{\epsilon}}), \\ \sigma_i(x_1,...,x_n)\equiv1~(p)&\Rightarrow& Q_{n^{\epsilon}}(\sigma_i(x_1,...,x_n))\equiv1~(p^{n^{\epsilon}}). \end{eqnarray*} Since $p^{n^{\epsilon}} \ge 2^{n^{\epsilon}}$, we conclude that $C_n$ outputs 1 iff, \begin{eqnarray*} \sum \limits_{i=1}^k Q_{n^{\epsilon}}(\sigma_i(x_1,...,x_n)) \equiv \ell~(p^{n^{\epsilon}}). \end{eqnarray*} Now $Q_{n^{\epsilon}}\circ\sigma - \ell$ is a polynomial $t$ of degree $O(n^{\epsilon}) \cdot o(n^{1-\epsilon}) = o(n)$. Furthermore, $C_n$ outputs 1 if and only if $t(x_1,...,x_n) \equiv 0~(p^{n^{\epsilon}})$. Thus $t$ is a polynomial of degree $o(n)$ that $p^{n^{\epsilon}}$-represents $\neg C_n$. \end{proof} \begin{corollary}\label{rp-mod-lb} Let $p,q$ be distinct primes and $\epsilon < 1$. No family of exact-of-$\Mod_p^+$ circuits of size $2^{n^{\epsilon}}$ can compute the functions $\Mod_{q,r}$ or $\neg \Mod_{q,r}$. \end{corollary} We also make an easy observation here that was mentioned in the introduction. \begin{proposition}\label{and-mod-degree} The Mod-degree of the AND function is $n$. \end{proposition} \begin{proof} This is immediate from a result of Tarui~\cite{Tar} (viz.~proposition 1 in that reference). \end{proof} Applying Theorem~\ref{circuit-sim}, it follows that, \begin{corollary}\label{or-lb} For any prime $p$ and $\epsilon < 1$, no family of exact-of-$\Mod_p^+$ circuits of size $2^{n^{\epsilon}}$ can compute the OR function. \end{corollary} \section{Approximating Parity with Exact-of-ACC($p$) Circuits} In this section another application of the main theorem is presented. We show that a circuit consisting of an exact gate over bounded-depth circuits with AND, OR and Mod$_p$ gates (for odd prime $p$) can agree with parity for at most a fraction $1/2+o(1)$ of all input settings, unless it is of exponential size. The machinery of Smolensky's is not sufficient to prove this because, once again, we need to deal with variable powers of the prime $p$. Unfortunately the current technique does not seem to be sufficiently powerful to handle the case of Mod$_q$ versus exact-of-ACC($p$) for any two distinct primes $q, p$. We begin by showing, for any odd prime $p$, that a polynomial of degree $o(\sqrt{n})$ can $p^k$-represent parity for at most a fraction $1/2+o(1)$ of the input settings. Furthermore, this holds for $k$ depending on the number of inputs in an arbitrary manner (it is this case that generalizes Smolensky's theorem). It would be most satisfying to be able to prove this theorem with the $p^k$ replaced by $m$ where $m$ is any odd number. But as will be clear from the proof, we make essential use of the fact that the modulus is a prime power. Since we are proving lower bounds for parity, there is no need for using complex inputs; we can work directly with the parity basis, in which the inputs $y_i$, $1 \le i \le n$, take on the values $\{-1,1\}$, and the degree of a polynomial is identical with its weight. The proof of the theorem is similar in spirit to that of Aspnes et al. \cite{ABFR} (for parity versus perceptrons). A key difference is that we are working in a finite ring ($\Z/p^k\Z$) with divisors of zero, and this requires much greater care in solving the linear equations as in the proof of \cite{ABFR}. But the main idea is the same: we show that if we can ``approximately'' $p^k$-represent parity well with a low-degree polynomial $t$, then we can weakly $p^k$-represent it with a polynomial of degree less than $n/2$. By the main theorem (with $q$=2), this is a contradiction. The theorem described above is given after the following analogue of Lemma 2.1 of \cite{ABFR}. The lemma is used to construct a polynomial which is zero on all the points of disagreement between parity and $t$. \begin{lemma}\label{maptozero} Let $m$ be any odd number. Let $S \subseteq \{-1, 1\}^n$ be such that $||S|| < \sum_{i=0}^l {n \choose i}$ where $l < n/2$. Then there is a degree $l$ integer polynomial $w : \{-1, 1\}^n \rightarrow \Z$ obeying the following properties: \begin{enumerate}\romanitems \item For any ${\bf y} \in S$, we have $w({\bf y}) = 0$. \item There is a ${\bf y} \in \{-1, 1\}^n$ with $\prod_{i=1}^n y_i = -1$, such that $w({\bf y}) \not \equiv 0~(m)$. \end{enumerate} \end{lemma} \begin{proof} Write down an arbitrary degree $l$ polynomial $w_1$ with rational coefficients. The number of coefficients in $w_1$ is one more than the upper bound on $||S||$. Thus, for each ${\bf y} \in S$, we can set $w_1({\bf y}) = 0$ (note that here we are using equality over the rationals), and regard this as a set of linear homogeneous equations for the coefficients of $w_1$. There is a non-trivial solution for the coefficients, since there are more ``variables'' than equations. Since the equations are homogeneous, we can find an {\it integer} solution $w_2({\bf y})$ by multiplying $w_1$ times a least common denominator. For the same reason we can divide $w_2$ by a greatest common divisor to obtain the degree $l$ integer polynomial $w({\bf y})$. We now prove that $w$ has the desired properties. Property (i) is obvious. For property (ii), first note that some coefficient of $w({\bf y})$ is not divisible by $m$, since we have divided by a GCD. We claim that this implies property (ii). For suppose property (ii) did not hold, that is for every ${\bf y}$ with $\prod_{i=1}^n y_i = -1$, we have $w({\bf y}) \equiv 0~(m).$ Since $w$ has degree $< n/2$, by Lemma~\ref{coeff-solution} (with $q=2$ and $r=1$), we conclude that all the coefficients of $w$ are zero mod $m$, which is a contradiction. \end{proof}%%lemma ``maptozero'' \begin{theorem}\label{Approxmdegree} Let $p$ be an odd prime, and let $t : \{-1, 1\}^n \rightarrow \Z$ be an integer polynomial of degree $o(\sqrt{n})$. Then for sufficiently large $n$, for any integer $k$, $$ ||\{ {\bf y} \in \{-1, 1\}^n | \prod_{i=1}^n y_i = -1 ~~{\mbox {\it iff}}~~ t({\bf y}) \not \equiv 0~(p^k) \}|| \le 2^n ({1 \over 2} + o(1)).$$ \end{theorem} \begin{proof} Let $\Delta$ denote the set of ``disagreements'' between $t$ and parity: \begin{eqnarray*} \Delta = \{ {\bf y} \in \{-1, 1\}^n ~|~ ( \prod_{i=1}^n y_i = -1 & AND & t({\bf y}) \equiv 0~(p^k) )\\ ~~& OR &~~ \\ ( \prod_{i=1}^N y_i = 1 & AND & t({\bf y}) \not \equiv 0~(p^k) ) \}. \end{eqnarray*} It suffices to show that $||\Delta||$ is ``large,'' that is, at least a fraction $1/2 - o(1)$ of all input settings. Let $d$ denote the degree of $t$ (by hypothesis, $d = o(\sqrt{n})$). Suppose \begin{eqnarray}\label{eq:delta-upper-bd} ||\Delta|| < \sum \limits_{i=1}^{n/2 - d - 1} {n \choose i}. \end{eqnarray} By Lemma~\ref{maptozero}, there is a degree $n/2-d-1$ polynomial $w$ such that for each ${\bf y} \in \Delta$, $w({\bf y}) \equiv 0~(p^k)$, but there is some ${\bf y}$ with $\prod_{i=1}^n y_i = -1$ such that $w({\bf y}) \not \equiv 0~(p)$. Since, by the definition of $\Delta$, we set $w({\bf y})=0$ for any odd-parity ${\bf y}$ with $t({\bf y}) \equiv 0~(p^k)$, it follows that $\prod_{i=1}^n y_i = -1$ and $w({\bf y}) \not \equiv 0~(p)$ implies $t({\bf y}) \not \equiv 0~(p^k)$. We know that a ${\bf y}$ exists with $\prod_{i=1}^n y_i = -1$ and $w({\bf y}) \not \equiv 0~(p)$. For such a ${\bf y}$, it is easy to see that $t({\bf y})w({\bf y}) \not \equiv 0~(p^k)$. (It is worth pointing out that the previous sentence is the {\it one} point in the proof where we use the fact that we are working modulo a prime power!) Thus the integer polynomial $t({\bf y})w({\bf y})$ has degree $n/2-1$, it is not the zero function mod $p^k$, but it is 0 mod $p^k$ whenever $\prod_{i=1}^n y_i = 1$. In other words, it weakly $p^k$-represents the parity function and has degree $< n/2$. By Theorem~\ref{main-theorem-s}, this is a contradiction. Thus $||\Delta||$ cannot obey (\ref{eq:delta-upper-bd}). Using the fact that $d=o(\sqrt{n})$, it is easy to show that this implies that $||\Delta|| \ge 2^n(1/2 - o(1))$, which proves the theorem. \end{proof} %%theorem ``approxmdegree'' To obtain the lower bound for exact-of-ACC($p$) circuits, we need the part of Smolensky's theorem~\cite{Sm} that shows how to approximate an ACC($p$) circuit with a low-degree polynomial mod $p$. This is given in the following version of this lemma, which is easily seen to follow from the proof of lemma 2 in \cite{Sm} (the statement below follows more closely that of lemma VIII.3.3 in \cite{Str}). \begin{lemma}\label{smol} {\rm (Smolensky):} Let $p$ be prime, and let $r:\nat \rightarrow \nat$ be such that $r(n) = o(n^{1/4d})$. Let $\{C_n\}$ denote a family of Boolean functions computed by ACC($p$)-type circuits of depth $d$ and size $2^{r(n)}$. Then there exists a family of polynomials $t_n$ over $\Z/p\Z$ such that the degree of $t_n$ is $o(n^{1/4})$, and $t_n({\bf y}) \equiv C_n({\bf y})~~(p)$ for a set of ${\bf y} \in \{-1, 1\}^n$ of cardinality at least $2^n (1-2^{-r(n)})$. \end{lemma} The lower bound for exact-of-ACC($p$) circuits is expressed in terms of a tradeoff between the number of ACC($p$) subcircuits and the size of those subcircuits. The theorem says that if both the number of subcircuits and the size of the subcircuits are too small, than the exact-of-ACC($p$) circuits cannot compute parity (and indeed cannot even approximate it). \begin{theorem}\label{equals-of-acc} Fix any integer $d$, any real number $0 < \epsilon < 1/4d$, and any odd prime $p$. Let $r:\nat \rightarrow \nat$ be such that $r(n) = o(n^{1/4d})$. Consider a family $\{C_n\}$ of exact-of-ACC($p$) circuits of depth $d+1$, where for each $n$ the number of ACC($p$) subcircuits in $C_n$ is $\le 2^{r(n)-n^{\epsilon}}$, and the size of each ACC($p$) subcircuit is $\le 2^{r(n)}$. Then, for all sufficiently large $n$, $C_n$ agrees with parity for at most a fraction $1/2 + o(1)$ of the input settings. \end{theorem} \begin{proof} Let $c_i$, $1 \le i \le 2^{r(n)-n^{\epsilon}}$, denote the ACC($p$) subcircuits of $C_n$. Since $c_i$ has depth $d$ and size less than $2^{r(n)}$ where $r(n) = o(n^{1/4d})$, it follows from Lemma~\ref{smol} that for some polynomial $t_i:\{-1, 1\}^n \rightarrow \Z$ of degree $o(n^{1/4})$, $c_i({\bf y}) \not \equiv t_i({\bf y})~(p)$ for at most $2^{n-r(n)}$ many ${\bf y}$'s. It is convenient to express this as a probability over ${\bf y}$ chosen uniformally at random from $\{-1, 1\}^n$: $$ Pr(c_i({\bf y}) \not \equiv t_i({\bf y})~(p)) \le 2^{-r(n)}.$$ Since there are $\le 2^{r(n)-n^{\epsilon}}$ subcircuits, it follows that, \begin{eqnarray*} Pr((\exists i) c_i({\bf y}) \not \equiv t_i({\bf y})~(p)) & \le & {2^{r(n)-n^{\epsilon}} \over 2^{r(n)}}\\ & = & o(1). \end{eqnarray*} So for at least $2^n(1-o(1))$ input settings, all subcircuits $c_i$ agree with their polynomials $t_i$. On these input settings, $C_n$ can be simulated by an exact-of-Mod$_p$-of-AND circuit with $2^{r(n)-n^{\epsilon}}$ Mod$_p$-of-AND subcircuits whose bottom fan-in is $o(n^{1/4})$ (corresponding to the degree of $t_i$). We now apply the method of Theorem~\ref{circuit-sim}. Compose each polynomial $t_i$ with the modulus-amplifying polynomial $Q_{n^{1/4d}}$. This gives a polynomial $t'_i = Q_{n^{1/4d}} \circ t_i$ of degree $n^{1/4d} \cdot o(n^{1/4}) = o(\sqrt{n})$ which equals $t_i$ modulo $p^{n^{1/4d}}$. Since $2^{r(n)-n^{\epsilon}} = o(p^{n^{1/4d}})$, we can add up the $t'_{i}$'s to obtain a polynomial $t$ of degree $o(\sqrt{n})$ which $p^{n^{1/4d}}$-represents $C_n$ on $2^n(1-o(1))$ input settings. But such a polynomial cannot agree with parity on more than $2^n(1/2+o(1))$ settings, by Theorem~\ref{Approxmdegree}. A simple probabilistic argument shows that this implies that $C_n$ can agree with parity on at most $2^n(1/2+o(1))$ settings. \end{proof} It is certainly natural to conjecture that Theorem~\ref{equals-of-acc} holds for Mod$_q$ versus exact-of-ACC($p$) circuits, where $q$ and $p$ are any two distinct primes (or even relatively prime). However, the current technique does seem to single out $q=2$ as being special, and this requires a bit of explanation. The problem is in proving a good lower bound on the number of disagreements, which in the case of $q=2$ is the quantity on the right hand side of equation~\ref{eq:delta-upper-bd}. It is critical that approximately $1/2$ (or, at any rate, a constant fraction) of the binomial coefficients are summed. For $q=2$ it is fortunate that the lower bound we have on the weak degree is about $n/2$. Since $n/2$ also happens to be the average weight of a monomial, the lower bound on $||\Delta||$ is close to half the sum of the binomial distribution over randomly chosen monomials. However, with Mod$_q$ (for odd prime $q$) the situation is very different. In this case (for $N$ {\it Boolean} inputs) we can do no better than sum ${N \choose i}$ up to the weak rp-Mod-degree, approximately $N/2(q-1)$. But this is well below the average weight, which, for $N$ Boolean inputs, is still $N/2$. That is, the best lower bound we can get on $||\Delta||$ is at most, $$\sum \limits_{i=0}^{N/2(q-1)} {N \choose i},$$ which, by the Chernoff bound, is exponentially smaller than $2^N$. It is not possible to get around this problem by obtaining a better lower bound on the rp-Mod-degree. The lower bound obtained in this paper is fairly tight, as is evident from the following upper bound. \begin{proposition}\label{upper-bd} The rp-Mod-degree of the Mod$_q$ function is at most $\lfloor N/q \rfloor + 1$. \end{proposition} \begin{proof} Let $x = \sum_{i=1}^N x_i$, and let $$ t(x_1,...,x_N) = \prod \limits_{j=0}^{\lfloor N/q \rfloor} (x - jq),$$ which is obviously of the degree given in the proposition. Choose $m$ relatively prime to $q$ such that for any $x_1,...,x_N$, $|t(x_1,...,x_N)| < m$. Then clearly $t(x_1,...,x_N) \equiv 0~(m)$ if and only if $x \equiv 0~(q)$. \end{proof} \section{Oracle Separations of $\EP^{\Mod_q\Pe}$} The lower bounds on exact-of-Mod$_p^+$ and exact-of-ACC($p$) circuits imply oracle separations of some well-known polynomial-time counting classes. The exact gate corresponds to the class $\EP$ \cite{Wagner} and the Mod$_p^+$ circuits to the classes Mod$_p\Pe$ \cite{Hert}, \cite{BG92}. \begin{theorem}\label{mod-vs-eq} For any pair of distinct primes $q, p$, there is an oracle $A$ such that $\Mod_q\Pe^A \not \subseteq \EP^{\Mod_p\Pe^A}$. \end{theorem} \begin{proof}(Sketch): We use a standard reduction of the oracle separation problem to a circuit problem, as in \cite{FSS} (see also \cite{Has}). Briefly, define the test language $L = \{1^n|$ the number of strings in $A$ of length $n$ is $\not \equiv 0~(q)\}$, which is clearly in Mod$_q\Pe^A$. Then we diagonalize against $\EP^{\Mod_p\Pe^A}$-machines. Here we use the circuit lower bounds from Corollary~\ref{rp-mod-lb} to show that there is sufficient room to diagonalize (that is, in stage $i$ of the diagonalization, $n_i$ can be chosen so that strings of that length can be added to $A$ in such a way that the $i$-th $\EP^{\Mod_p\Pe^A}$-machine does not determine $1^{n_i} \in L$ correctly). \end{proof} We remark that Toda's theorem $\PH \subseteq \PP^{\parityP}$ cannot be improved to $\PH \subseteq \EP^{\parityP}$ relative to all oracles: \begin{proposition} There is an oracle $A$ such that $\NP^A \not \subseteq \EP^{\Mod_p\Pe^A}$, for all prime $p$. \end{proposition} \begin{proof} The proof is similar to that of Theorem~\ref{mod-vs-eq}, where now we appeal to Corollary \ref{or-lb}. \end{proof} The above proposition does not hold relative to a random oracle; in fact, relative to a random oracle $\EP$ contains the entire polynomial hierarchy \cite{Tar}. But the results of section 5 yield random oracle separations of $\parityP$ from $\EP^{\Mod_p\Pe}$. From Theorem~\ref{Approxmdegree} and standard techniques for random oracles (see \cite{BG} and \cite{Has}), we find, \begin{theorem} Relative to a random oracle $A$, for any odd prime $p$, $\parityP^A \not \subseteq \EP^{\Mod_p\Pe^A}$. \end{theorem} It is known that relative to a random $A$, $\Mod_p\Pe^{\PH^A} \subseteq \Mod_p\Pe^A$ \cite{Tar}. Using this, the above theorem gives the following stronger result (another proof follows from Theorem~\ref{equals-of-acc}). Let Mod$_p$PH denote the closure of $\Pe$ under the operations ${\cal C} \mapsto \NP^{\cal C}$ and ${\cal C} \mapsto \Mod_p\Pe^{\cal C}$, which is the polynomial-time analogue of ACC($p$). \begin{theorem} Relative to a random oracle $A$, for any odd prime $p$, $\parityP^A \not \subseteq \EP^{\Mod_p\PH^A}$. \end{theorem} \section{Discussion and Open Problems} The most important contribution of this paper has been to extend existing techniques and develop new ones for proving lower bounds on the degree of polynomials, over $\Z/m\Z$ where $m$ is not a prime power, representing modular functions. Such lower bounds can be used to obtain lower bounds on circuit size, as is well known and is illustrated here in the results of section 5. Once the problem was translated into the appropriate algebraic language, the proof of the main theorem was surprisingly simple: compute the Fourier transform of the polynomial assuming it has small degree, and find that the coefficients are zero (contradiction). Most of the necessary work was in arriving at the appropriate algebraic setting. In this instance, the appropriate setting was the ring of polynomials over the algebraic integers $\Zalg$. It should be noted that very few properties of $\Zalg$ were used. Algebraic integers are most useful when computing with polynomials in {\it different} roots of unity, while here we only needed one ($\zeta$ was fixed throughout section 3). As mentioned in a footnote, it would have been sufficient to extend to $\Z[\zeta]$ (the ring of integer polynomials in $\zeta$) rather than $\Zalg$, since the coefficients that arise in encoding the roots of unity as Boolean inputs are all in $\Z[\zeta]$. In this sense, Lemma~\ref{coeff-solution} is stonger than is necessary (in particular, the stronger hypothesis $c_{\bf e} \in \Z[\zeta]$ would suffice). This suggests that further investigation of the properties of polynomials in rings of algebraic integers may be fruitful. The open problems which seem most amenable to attack are related to the power of exact-of-ACC($p$) circuits. General exact-of-ACC circuits have been considered previously by Beigel, Tarui and Toda~\cite{BTT}, who show that probabilistic exact-of-ACC circuits of quasipolynomial size can be simulated by circuits consisting of a symmetric gate over polylog fan-in AND's (called SYM$^+$ circuits). Thus any lower bounds for SYM$^+$ circuits are at least as hard as for probabilistic exact-of-ACC circuits. We conjecture that for any pair of distinct primes $q, p$, the Mod$_q$ function requires exponential size exact-of-ACC($p$) circuits. From the proof of Theorem~\ref{equals-of-acc}, it would suffice to show that the Mod$_q$ function cannot be well-approximated by an exact-of-Mod$_p^+$ circuit. This problem, in turn, reduces to showing that the Mod$_q$ function cannot be approximately $p^k$-represented by a low-degree polynomial. More generally, we conjecture that if $q$ and $m$ are relatively prime, Mod$_q$ cannot be $m$-represented by a low-degree polynomial for any more than a certain constant fraction of the inputs (note $m$ is permitted to vary with the number of inputs; for constant $m$, the conjecture is proved \cite{Bei93}). In this paper we have succeeded in proving this only in the special case of $q=2$ and even then it was necessary to assume $m$ is a prime power. While many of these problems may appear to be of a technical nature, we believe that their resolution will reveal more widely applicable lower bound techniques for modular functions.\\ \noindent {\bf Acknowledgements}: I wish to thank Arthur Chou for helpful conversations, and some anonymous referees for helpful suggestions on an earlier version of this paper. The hospitality of the Computer Science Department of Boston University, where part of this work was done during a sabbatical from Clark University, is gratefully acknowledged. \begin{thebibliography}{1} \bibitem[ABFR]{ABFR} {\sc J~Aspnes, R.~Beigel, M.~Furst, and S.~Rudich}, The expressive power of voting polynomials, in {\it Combinatorica}, {\bf 14(2)}, (1994), 1--14. \bibitem[Al]{Allender} {\sc E.~Allender,} A note on the power of threshold circuits. In {\it Proceedings of the 30th Symposium on Foundations of Computer Science}, (1989), 580-584. \bibitem[Bar]{Bar}{\sc D. Barrington}, Bounded-width polynomial-size branching programs recognize exactly those languages in NC$^1$, in {\it Journal of Computer and System Sciences} {\bf 38}, (1989), 150-164. \bibitem[BBR]{BBR}{\sc D. M. Barrington, R. Beigel, and S. Rudich,} Representing Boolean functions as polynomials modulo composite numbers, in {\it Computational Complexity} {\bf 4} (1994) 367--382. \bibitem[BDG]{BDG} {\sc J.L. Balc\'{a}zar, J. D\'\i az, and J. Gabarr\'{o}}, {\em Structural Complexity I}. Springer, 1987. \bibitem[Bei 92]{Bei92}{\sc R.~Beigel}, When do extra majority gates help? polylog($n$) majority gates are equivalent to one, in {\it Computational Complexity} {\bf 4} (1994) 314--324. \bibitem[Bei 93]{Bei93} {\sc R.~Beigel}, The polynomial method in circuit complexity, {\it Proceedings of the 8th IEEE Conference on Structure in Complexity Theory} (1993) 82-95. \bibitem[BeiGil 92]{BG92} {\sc R.~Beigel and J.~Gill,} Counting classes: thresholds, parity, mods, and fewness in {\it Theoretical Computer Science} {\bf 103} (1992) 3-23. \bibitem[BenGil 81]{BG}{\sc C.~Bennett and J.~Gill,} Relative to a random oracle $A$, $\Pe^A \not = \NP^A \not = $co-NP$^A$ with probability 1, {\it SIAM Journal on Computing,} {\bf 10(1)} (1981) 96-113. \bibitem[BRS]{BRS}{\sc R.~Beigel, N.~Reingold, and D.~Spielman}, PP is closed under intersection, in {\it Proceedings of the 23rd ACM Symposium on the Theory of Computation}, (1991), 1-11. A journal version is to appear in {\it Journal of Computer and System Sciences}. \bibitem[BS]{BS}{\sc D.~M.~Barrington and H.~Straubing,} Complex polynomials and circuit lower bounds for modular counting, in {\it Computational Complexity} {\bf 4} (1994) 325-338. \bibitem[BT]{BT} {\sc R.~Beigel and J.~Tarui,} On ACC, in {\it Computational Complexity} {\bf 4} (1994) 350--366. \bibitem[BTT]{BTT} {\sc R.~Beigel, J.~Tarui, and S.~Toda,} On probabilistic ACC circuits with an exact-threshold output gate, in {\it Proceedings of the 3rd International Symposium on Algorithms and Computation}, (1992) 420-429. \bibitem[CGT]{CGT}{\sc J.-Y.~Cai, F.~Green and T.~Thierauf,} On the correlation of symmetric functions, to appear in {\it Mathematical Systems Theory}. \bibitem[FFK]{FFK} {\sc S.~Fenner, L.~Fortnow and S.~Kurtz,} Gap-definable counting classes, in {\it Proceedings of the Sixth Annual Conference on Structure in Complexity Theory}, IEEE Computer Society Press (1991) 30-42. \bibitem[FSS]{FSS}{\sc M.~Furst, J.~B.~Saxe, and M.~Sipser,} Parity, circuits, and the polynomial-time hierarchy, in {\it Mathematical Systems Theory,} {\bf 17} (1984) 13-27. \bibitem[GKRST]{GKRST} {\sc F.~Green, J.~K{\"o}bler, K.~Regan, T.~Schwentick, and J.~Tor{\'a}n,} The power of the middle bit of a $\numP$ function, in {\it Journal of Computer and System Sciences} {\bf 50} (1995) 456-467. \bibitem[Gre 91]{Gre}{\sc F.~Green,} An oracle separating $\oplus$P from PP$^{\PH}$, {\em Information Processing Letters} {\bf 37} (1991) 149-153. \bibitem[Gre 93]{Gre93}{\sc F.~Green,} On the power of deterministic reductions to $\EP$, in {\em Mathematical Systems Theory} {\bf 26} (1993) 215-233. \bibitem[Has]{Has} {\sc J. H{\aa}stad,} Computational limitations of small-depth circuits, the MIT press, Cambridge, 1987. \bibitem[He~90]{Hert} {\sc U.~Hertrampf,} Relations among MOD-classes. In {\it Theoretical Computer Science} {\bf 74} (1990) 325-328. \bibitem[HMPST]{HMPST} {\sc A. Hajnal, W. Maass, P. Pudl{\'a}k, M. Szegedy, and G. Tur{\'a}n,} Threshold circuits of bounded depth, in {\em Proceedings 28th Annual IEEE Symposium on Foundations of Computer Science}, IEEE Computer Society Press (1987) 99-110. \bibitem[IR]{IR}{\sc K.~Ireland and M.~Rosen,} A classical introduction to modern number theory, Second Edition, Springer-Verlag, New York, 1990. \bibitem[KP]{KP} {\sc M.~Krause and P.~Pudl{\'a}k,} On the computational power of depth 2 circuits with threshold and modulo gates, in {\em Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing,} ACM Press (1994) 48-57. \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[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[Str]{Str}{\sc H.~Straubing,} Finite Automata, Formal Logic and Circuit Complexity, Birkh{\"a}user, Boston 1994. \bibitem[Ta]{Tar}{\sc J.~Tarui,} Degree complexity of Boolean functions and its applications to relativized separations, in {\em Proceedings of the Sixth Annual Conference on Structure in Complexity Theory}, IEEE Computer Society Press (1991) 382-390. \bibitem[Tod]{Toda}{\sc S.~Toda.} PP is as hard as the polynomial-time hierarchy. In {\it SIAM Journal on Computing} {\bf 20}, (1991) 865-877. \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[Wa~86]{Wagner} {\sc K. Wagner}, The complexity of combinatorial problems with succinct input representation. In {\it Acta Informatica} {\bf 23}, (1986), 325-356. \end{thebibliography} \end{document}