FKN Theorem on the biased cube

Piotr Nayar¹

¹ Institute of Mathematics University of Warsaw Banacha 2 02-097 Warszawa, Poland and 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.

Colloquium Mathematicum, Tome 137 (2014) no. 2, pp. 253-261.

Résumé

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.

Détail

DOI : 10.4064/cm137-2-9

Keywords: consider boolean functions defined discrete cube gamma gamma equipped product probability measure otimes where beta delta gamma alpha delta gamma gamma sqrt alpha beta normalization ensures coordinate functions ldots orthonormal gamma gamma otimes prove spectrum boolean function concentrated first fourier levels function close certain function variable theorem strengthens non symmetric fkn theorem due jendrej oleszkiewicz wojtaszczyk moreover symmetric alpha beta prove valued function defined discrete cube close certain affine function close valued affine function