We consider a system of linear constraints over any finite abelian group $G$ of the following form: $\\ell_i(x_1,\\ldots,x_n) \\equiv \\ell_{i,1}x_1+\\cdots+\\ell_{i,n}x_n \\in A_i$ for $i=1,\\ldots,t$ and each $A_i \\subset G$, $\\ell_{i,j}$ is an element of $G$ and $x_i$'s are Boolean variables. Our main result shows that the subset of the Boolean cube that satisfies these constraints has exponentially small correlation with the $\\text{MOD}_q$ boolean function, when the order of $G$ and $q$ are co-prime numbers.

Our work extends the recent result of Chattopadhyay and Wigderson (FOCS'09) who obtain such a correlation bound for linear systems over cyclic groups whose order is a product of two distinct primes or has at most one prime factor. Our result also immediately yields the first exponential bounds on the size of boolean depth-three circuits of the form $\\text{MAJ} \\circ \\text{AND} \\circ \\text{MOD}_m^A$ for computing the $\\text{MOD}_q$ function, when $m,q$ are co-prime. No superpolynomial lower bounds were known for such circuits for computing any explicit function, when $m$ had three or more distinct prime factors.

This completely solves an open problem posed by Beigel and Maciel (Complexity'97) (this is joint work with Shachar Lovett, IAS-Princeton).