FKN Theorem on the biased cube

Volume 137 / 2014

Piotr Nayar Colloquium Mathematicum 137 (2014), 253-261 MSC: Primary 42C10; Secondary 60E15. DOI: 10.4064/cm137-2-9


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.


  • Piotr NayarInstitute of Mathematics
    University of Warsaw
    Banacha 2
    02-097 Warszawa, Poland
    Institute for Mathematics and its Applications
    College of Science and Engineering
    University of Minnesota
    207 Church Street SE
    306 Lind Hall
    Minneapolis, MN 55455, U.S.A.

Search for IMPAN publications

Query phrase too short. Type at least 4 characters.

Rewrite code from the image

Reload image

Reload image