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

07/13/2021

∙

by   Siddharth Iyer, et al.

∙

0

∙

share

We give tight bounds on the degree ℓ homogenous parts f_ℓ of a bounded function f on the cube. We show that if f: {± 1}^n → [-1,1] has degree d, then f_ℓ_∞ is bounded by d^ℓ/ℓ!, and f̂_ℓ_1 is bounded by d^ℓ e^ℓ+12 n^ℓ-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.