Tight bounds on the Fourier growth of bounded functions on the hypercube

Abstract

We give tight bounds on the degree $\ell$ homogenous parts $f_{\ell }$ of a bounded function $f$ on the cube. We show that if $f:\{\pm 1{\}}^n\to [-1,1]$ has degree $d$, then $\Vert f_{\ell }{\Vert }_{\infty }$ is bounded by $d^{\ell }/\ell !$, and $\Vert {\hat{f}}_{\ell }{\Vert }_1$ is bounded by $d^{\ell }{e}^{\left(\genfrac{}{}{0ex}{}{\ell +1}{2}\right)}{n}^{\frac{\ell -1}{2}}$. We describe applications to pseudorandomness and learning theory. We use similar methods to generalize the classical Pisier's inequality from convex analysis. Our analysis involves properties of real-rooted polynomials that may be useful elsewhere.