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 (STOC 1992, pp. 455-461) 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, LATIN '92, pp.~24-31) 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.
This is a revised and expanded version of ``Lower Bounds for Depth-Three
Circuits with Equals and Mod-Gates," in STACS 1995, pp. 71-82.