Computation modulo composite numbers is much less understood
than computation over primes; and sometimes surprisingly much more
powerful. A positive example is that the best construction of locally
decodable codes known today heavily relies on computations modulo
composites. A negative one if that while strong lower bounds are known
for constant-depth circuits using AND,OR and MOD_5 gates, no such lower
bounds are known if the MOD_5 gates are replaced by MOD_6 gates. We
consider in this work a restricted model of computation: linear systems
modulo composites. This model was explicitly given by Beigel and Maciel
(Complexity 97) as a barrier towards proving lowers bounds for
computation modulo composites (i.e. ACC0). We completely resolve their
problem in this work. 

Fix a modulus M. A system of linear constraints in boolean variables 
x_1,..,x_n modulo M has the following form: a linear equation 
is a constraint of the form $a_1 x_1 + ... + a_n x_n (modulo M)
\in A$, where the variables x_1,...,x_n are boolean, the coefficients
a_1,...,a_n are elements of Z_M, and A is a subset of Z_M. A linear
system is a set of linear constraints. We prove that any such system has
exponentially small correlation with the MOD_q function, where m,q are
co-prime. To this end we prove structural results on the accepting sets
of such systems. 

This problem can be relatively easy solved for prime M using 
Fourier analysis; however for composite M these techniques break
down. Recently, Chattopadhyay and Wigderson (FOCS'09) proved correlation
bounds when M has two prime factors (e.g. for M=6). In this work we
generalize their technique to handle arbitrary M, and in fact arbitrary
Abelian groups instead of Z_M. Our result yield the first exponential
bounds on the size of boolean depth-four circuits of the form MAJ - AND
- ANY_{O(1)} - MOD_m for computing the MOD_q function, when $m,q$ are
  co-prime. 

Joint work with Arkadev Chattopadhyay.