In this note we describe Boolean functions f ( x1, x2,..., xn ) whose Fourier coefficients are concentrated on the lowest two levels. We show that such a function is close to a constant function or to a function of the form f = xk or f = 1 - xk. This result implies a "stability" version of a classical discrete isoperimetric result and has an application in the study of neutral social choice functions. The proofs touch on interesting harmonic analysis issues.
All Science Journal Classification (ASJC) codes
- Applied Mathematics