We study the Fourier spectrum of functions f : 0 1 m k − 1 0 1 which can be written as a product of k Boolean functions f i on disjoint m -bit inputs. We prove that for every positive integer d , S [ m k ]: S = d f S = O ( m ) d Our upper bound is tight up to a constant factor in the O ( ) . Our proof builds on a new "level- d inequality" that bounds above S = d f S 2 for any [0 1 ] -valued function f in terms of its expectation, which may be of independent interest.

As a result, we construct pseudorandom generators for such functions with seed length O ( m + log ( k )) , which is optimal up to polynomial factors in log m , log log k and log log (1 ) . Our generator in particular works for the well-studied class of combinatorial rectangles, where in addition we allow the bits to be read in any order. Even for this special case, previous generators have an extra O ( log (1 )) factor in their seed lengths.

Using Schur-convexity, we also extend our results to functions f i whose range is [ − 1 1 ].