Abstract
We consider Boolean functions defined on the discrete cube {-γ, γ-1}n equipped with a product probability measure µ⊗n, where µ = βδ-γ + αδγ-1 and γ = α/β. This normalization ensures that the coordinate functions (xi)i=1,…,n are orthonor-mal in L2({-γ, γ-1}n, µ⊗n). We prove that if the spectrum of a Boolean function is con-centrated 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 α = β = 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.
Original language | English (US) |
---|---|
Pages (from-to) | 253-261 |
Number of pages | 9 |
Journal | Colloquium Mathematicum |
Volume | 137 |
Issue number | 2 |
DOIs | |
State | Published - 2014 |
Bibliographical note
Publisher Copyright:© Instytut Matematyczny PAN, 2014.
Keywords
- Boolean functions
- FKN theorem
- Walsh-fourier expansion