Abstract:
We study the correlation between low-degree GF(2) polynomials p and explicit functions. Our main results are the following: (I) We prove that the Mod_m unction on n bits has correlation at most exp(-Omega(n/4^d)) with any GF(2) polynomial of degree d, for any fixed odd integer m. This improves on the previous exp(-Omega(n/8^d)) bound by Bourgain (C. R. Acad. Sci. Paris, 2005) and Green et al. (C. R. Acad. Sci. Paris, 2005). (II) We exhibit a polynomial-time computable function on n bits that has correlation at most exp(-Omega(n/2^d)) with any GF(2) polynomial of degree d. Previous to our work the best correlation bound for an explicit function was exp(-Omega(n/(d 2^d))), which follows from (Chung and Tetali; SIAM J. Discrete Math., 1993). (III) We derive an `XOR Lemma' for low-degree GF(2) polynomials: We show that if a function f has correlation at most 1-4^(-d) with any GF(2) polynomial of degree d (and Pr_x[f(x) = 1] ~ 1/2) then the XOR of m independent copies of f has correlation at most exp(-Omega(m/4^d)) with any GF(2) polynomial of degree d. Our results rely on a measure of the `complexity' of a function due to Gowers (Geom. Funct. Anal., 1998 & 2001).