We analyze the Fourier growth, i.e. the L1 Fourier weight at level k (denoted L_{1,k}), of various well-studied classes of "structured" F2-polynomials. This study is motivated by applications in pseudorandomness, in particular recent results and conjectures due to [Chattopadhyay et al., 2019; Chattopadhyay et al., 2019; Eshan Chattopadhyay et al., 2020] which show that upper bounds on Fourier growth (even at level k = 2) give unconditional pseudorandom generators.
Our main structural results on Fourier growth are as follows:
- We show that any symmetric degree-d F2-polynomial p has L_{1,k}(p) at most Pr [p = 1] \cdot O(d)^k. This quadratically strengthens an earlier bound that was implicit in [Omer Reingold et al., 2013].
- We show that any read-\delta degree-d F2-polynomial p has L_{1,k}(p) at most Pr [p = 1] \cdot (k \cdot \delta \cdot d)^{O(k)}.
- We establish a composition theorem which gives L_{1,k} bounds on disjoint compositions of functions that are closed under restrictions and admit L_{1,k} bounds.
Finally, we apply the above structural results to obtain new unconditional pseudorandom generators and new correlation bounds for various classes of F2-polynomials.