FKN Theorem on the biased cube
Volume 137 / 2014
Abstract
We consider Boolean functions defined on the discrete cube $\{-\gamma ,\gamma ^{-1}\}^n$ equipped with a product probability measure $\mu ^{\otimes n}$, where $\mu =\beta \delta _{-\gamma }+\alpha \delta _{ \gamma ^{-1} }$ and $\gamma =\sqrt {\alpha / \beta }$. This normalization ensures that the coordinate functions $(x_i)_{i=1,\ldots ,n}$ are orthonormal in $L_2(\{-\gamma ,\gamma ^{-1}\}^n,\mu ^{\otimes n})$. We prove that if the spectrum of a Boolean function is concentrated on the first two Fourier levels, then the function is close to a certain function of one variable. Our theorem strengthens the non-symmetric FKN Theorem due to Jendrej, Oleszkiewicz and Wojtaszczyk.
Moreover, in the symmetric case $\alpha =\beta =1/2$ we prove that if a $[-1,1]$-valued function defined on the discrete cube is close to a certain affine function, then it is also close to a $[-1,1]$-valued affine function.
