A complex-number Fourier technique for lower bounds on the Mod-m degree

We say an integer polynomial p, on Boolean inputs, weakly m-represents a Bo olean function f if p is nonconstant and is zero (mod m), whenever f is zer o. In this paper we prove that if a polynomial weakly m-represents the Mod, function on n inputs, where q and m are relatively prime and m is otherwis e arbitrary, then the degree of the polynomial is Ohm>(*) over bar * (n). T his generalizes previous results of Barrington, Beigel and Rudich, and Tsai , 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 Barr ington and Straubing) in which the inputs are represented as complex q-th r oots 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 that computes the Mod, function, a nd consists of an exact threshold gate at the output, Mod, gates at the nex t level, and AND gates of polylog fan-in at the inputs, must be of exponent ial size. We also consider the question of how well circuits consisting of one exact gate over ACC(p)-type circuits (where p is an add prime) can appr oximate parity. It is shown that such circuits must have exponential size i n order to agree with parity for more than 1/2 + o(1) of the inputs.