Linear System Over Finite Abelian Groups

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).