Linear Systems over Composite Moduli
Arkadev Chattopadhyay, Avi Wigderson · 2009
We study solution sets to systems of 'generalized' linear equations of the form: ¿i(x1, x2, ···, xn) in ¿ Ai(mod m) where ¿1,..., ¿tare linear forms in n Boolean variables, each Aiis an arbitrary subset of Zm, and m is a composite integer that is a product of two distinct primes, like 6. Our main technical result is that such solution sets have exponentially small correlation, i.e. with the boolean function MODq, when m and q are relatively prime. This bound is independent of the number t of equations. This yields progress on limiting the power of constant-depth circuits with modular gates. We derive the first exponential lower bound on the size of depth-three circuits of type MAJ o AND o MODAm(i.e having a MAJORITY gate at the top, AND/OR gates at the middle layer and generalized MODmgates at the base) computing the function MODq. This settles an open problem of Beigel and Maciel (Complexity'97) for the case of such modulus m. Our technique makes use of the work of Bourgain on estimating exponential sums involving a low-degree polynomial and ideas involving matrix rigidity from the work of Grigoriev and Razborov on arithmetic circuits over finite fields.