A remark on Bourgain’s distributional inequality on the Fourier spectrum of Boolean functions

Hamed Hatami Department of Computer Science University of Toronto E-mail: hamed@cs.toronto.edu

Submitted: September 24, 2005; Accepted: May 2, 2006; Published: May 5, 2006

Abstract

Bourgain’s theorem says that under certain conditions a function f : {0, 1}_{2}^{n} → {0, 1} can be approximated by a function g which depends only on a small number of variables. By following his proof we obtain a generalization for the case that there is a nonuniform product measure on the domain of f.

1 Introduction

Fix 0 < α < 1. Consider the measure space (𝔽_{2}^{n}, μ_{α}) where μ_{α} is the product measure defined as μ_{α}(x) = α^{|x|}(1 − α)^{n−|x|} with |x| = ∑_{i=1}^{n} x_{i}. Let f : (𝔽_{2}^{n}, μ_{α}) → {0, 1} be a Boolean function. We want to show that under certain conditions f can be approximated by a function g which depends only on a small number of variables. More formally, there exist indices 1 ≤ i_{1} < … < i_{m} ≤ n such g(x) = g(y), if x_{i_{j}} = y_{i_{j}} for every 1 ≤ j ≤ m. Moreover by g approximates f we mean that

∥f − g∥_{2}^{2} ≤ ϵ.  (1)

Here m and ϵ are parameters which depend on each other and the conditions on f. We are interested in the conditions that come from the Fourier-Walsh spectrum of f. The results of this type have many applications in combinatorics and computer science [1, 7, 3, 4, 8, 6]. Let

h = ∑_{|S|≥k} |f̂(S)|^{2},  (2)

denote the second norm squared of the Fourier transform of f on large frequencies, i.e., |S| ≥ k. It is usually the case that when h is small, f can be approximated by a function g which depends only on a few number of variables. The result of this type for k = 2, α = 1/2 has been proven in [4], and for k = 2 in the more general setting of the uniform measure on 𝔽_{r}^{n} in [1] and [5]. So far, the most general known result is Bourgain’s distributional inequality [2] which deals with α = 1/2 and the general k (See Khot and Naor [6] for a quantitative version).

In all the mentioned results the measure is assumed to be uniform. In [7] Kindler and Safra tried to generalize these results to arbitrary values of α, and proved a theorem which deals with the general values of k and α. That result requires h to be very small, and for α = 1/2 is not as strong as Bourgain’s theorem. In the present note we show that by following Bourgain’s proof one can obtain a theorem (Corollary 2.2) for general values of α which does not require h to be as small as in [7]. However we should mention that this theorem does not completely cover their result, and for sufficiently small h, their approximation is stronger.

One notion that has been used in both [2] and [7] is the hypercontractivity of the Bonami-Beckner operator. Remember that the Bonami-Beckner operator can be defined as T_{δ}f = ∑ δ^{|S|}f̂(S)w_{s} where w_{S} are the bases of the Fourier-Walsh expansion. For 1 ≤ p ≤ q < ∞ and 0 < η < 1, we say that a function f : (𝔽_{2}^{n}, μ_{α}) → 𝔽 is (p, q, η)-hypercontractive, if

∥T_{η}f∥_{q} ≤ ∥f∥_{p}.

The classic Bonami-Beckner Theorem says that for α = 1/2, f is (2, q, \frac{1}{\sqrt{q−1}})-hypercontractive. Recently P. Wolff proved the following theorem (see also [9] and [10]).

Theorem 1.1. [11] Let f : (𝔽_{2}^{n}, μ_{α}) → ℝ, q ≥ 2, 1/q + 1/q′ = 1, and A = \frac{1−α}{α}. Define

η_{q′}(α) = η_{q}(α) = (\frac{A^{1/q′} − A^{−1/q′}}{A^{1/q} − A^{−1/q}} )^{−1/2} .

Then

1. f is (2, q, η_{q}(α))-hypercontractive.

2. f is (q′, 2, η_{q′}(α))-hypercontractive.

Remark. Since T_{δ} is self-adjoint, by duality of L_{p} spaces, (1) and (2) are equivalent. Note that in Theorem 1.1, η_{q}(1/2) and η_{q′}(1/2) are not defined. However having Bonami-Beckner Theorem in mind, we define η_{q}(1/2) = η_{q′}(1/2) = \frac{1}{\sqrt{q−1}}.

For simplicity we will write η_{p} for η_{p}(α). Next we want to state Kindler and Safra’s theorem. Let

I_{κ} = {i ∈ {1, …, n} : ∑_{i∈S,|S|≤k} f̂(S)^{2} ≥ κ} .  (3)

The goal is to show that for small values of h and κ, f essentially depends only on the variables with indices in I_{κ}. First note that

κ|I_{κ}| ≤ ∑_{i=1}^{n} ∑_{S:i∈S,|S|≤k} f̂(S)^{2} ≤ k

which follows

|I_{κ}| ≤ k/κ.  (4)

Let g = ∑_{S⊆I_{κ}} f̂(S)w_{S}. Note that g depends only on the variables with indices in I_{κ}. Moreover

∥f − g∥_{2}^{2} = ∑_{S⊈I_{κ}} f̂(S)^{2}.  (5)

So we have to bound the right hand side of (5).

Theorem 1.2. (Kindler and Safra [7]) There exists a global constant C such that for h, κ ≤ η_{4}^{16k}/C, we have

∑_{S⊈I_{κ}} f̂(S)^{2} ≤ h(1 + 1266η_{4}^{−4k}h^{1/4}).

the next lemma estimates η_{p}(α). In the following we write x ≲ y to indicate that there is a universal constant c > 0 such that x ≤ cy.

Lemma 1.3. For α ≤ 1/2, and 1 ≤ p = 1 + x ≤ 2, we have

• If α ≤ e^{−1/x}, then

η_{p}(α) ≳ α^{\frac{2−p}{2p}} .

• If α > e^{−1/x}, then

η_{p}(α) ≳ α^{\frac{2−p}{2p}} \sqrt{ln(1/α)x}.

Proof. Notice that

η_{p}(α) = A^{\frac{p−2}{2p}} (\frac{1 − A^{−2/p}}{1 − A^{−2/p′}} )^{−1/2} ≥ α^{\frac{2−p}{2p}} (\frac{1 − e^{−2 ln(A)/p}}{1 − e^{−2 ln(A)/p′}} )^{−1/2}
≥ α^{\frac{2−p}{2p}} \sqrt{1 − e^{−2 ln(A)/p′}}.  (6)

First assume that α ≤ e^{−1/x}. Then since p′ = 1 + 1/x, we have

ln(A)/p′ ≥ \frac{ln(1/(2α))}{p′} ≥ \frac{1/x − ln(2)}{1/x + 1} ≥ 1/10.

So

(6) ≳ α^{\frac{2−p}{2p}} .

Next consider α > e^{−1/x}. We can assume that −2 ln(A)/p′ > −1 as otherwise the theorem becomes clear. Using the fact that for 0 < y < 1, e^{−y} ≤ 1 − y/2, we get

(6) ≳ α^{\frac{2−p}{2p}} \sqrt{ln(A)/p′} ≳ α^{\frac{2−p}{2p}} \sqrt{ln(1/α)x}.

2 Main Result

In this section we state our main result.

Theorem 2.1. Let 0 < α ≤ 1/2, and f : (𝔽_{2}^{n}, μ_{α}) → {0, 1} be a Boolean function. For 2 < k ≤ n and 0 < κ < 1, h and I_{κ} are defined as in (2) and (3), respectively. If

ϕ = \frac{log_{2}(1/α) + \sqrt{log_{2}(1/h) log_{2} log_{2} k}}{16 log_{2}(1/h)} ,

then

γ = ∑_{|S|<k,S⊈I_{κ}} f̂(S)^{2} ≲ \sqrt{k}2^{\frac{log_{2} log_{2} k}{ϕ}} (h/α + α^{− \frac{k+1}{2}} κ^{1/4}) + (log_{2} k)\sqrt{h}.  (7)

Online Journal of Analytic Combinatorics, Issue 1 (2006), #3 3

Proof. To prove the theorem in the special case of α = 1/2, [2] used the following facts:

∥f∥_{p} ≥ ( ∑_{A⊆{1,...,n}} η_{p}(α)^{2|A|}f̂(A)^{2})^{1/2} ≥ η_{p}(α) (∑_{i=1}^{n} f̂({i})^{2})^{1/2} ,  (8)

and if a function f satisfies f̂(S) = 0, for every |S| ≥ k, then

∥f∥_{4} = ∥T_{η_{4}}T_{η_{4}^{−1}}f∥_{4} ≤ ∥T_{η_{4}^{−1}}f∥_{2} ≤ η_{4}^{−k}∥f∥_{2},

or

∥f∥_{4}^{4} ≤ η_{4}^{−4k}∥f∥_{2}^{4}.  (9)

By substituting (8) and (9) for general value of α in the proof, we obtain the following inequality instead of Equation (20) in [2]:

δ^{p/2}ρ_{t_{0}} ≲ \frac{η_{p}^{−p}δ}{2^{t_{0}}} ( ∑_{t<log_{2} k} 2^{t}ρ_{t}) + η_{p}^{−p}h + (δh)^{p/2} + (η_{4}^{−2k}\sqrt{κ})^{p/2},  (10)

for every 1 ≤ t_{0} < log_{2} k, 0 < δ < 1, and 1 ≤ p ≤ 2, where

ρ_{t} = ∑_{2^{t−1}≤|S\I_{κ}|<2^{t}} f̂(S)^{2}.  (11)

We distinguish two cases: Case 1:

∑_{t<log_{2} k} 2^{t}ρ_{t} ≥ γ\sqrt{k},

where γ is defined in (7). Choose t_{0} to satisfy

2^{t_{0}}ρ_{t_{0}} ≥ \frac{∑_{t<log_{2} k} 2^{t}ρ_{t}}{log_{2} k} .

It follows that ρ_{t_{0}} ≥ \frac{γ}{\sqrt{k} log_{2} k}. Assume p ∈ (3/2, 2) so that we can use Lemma 1.3 and obtain

η_{p} ≳ α^{\frac{2−p}{2p}}. Substituting these in (10) we get

(δ^{p/2} − α^{\frac{p−2}{2}} δ log_{2} k) \frac{γ}{\sqrt{k} log_{2} k} ≲ α^{\frac{p−2}{2}} h + (δh)^{p/2} + (η_{4}^{−2k}\sqrt{κ})^{p/2}.  (12)

Now taking δ = ^{\frac{α(log_{2} k)^{\frac{2}{p−2}}}{4}} we obtain

δ^{p/2} \frac{γ}{\sqrt{k} log_{2} k} ≲ α^{\frac{p−2}{2}} h + (δh)^{p/2} + (η_{4}^{−2k}\sqrt{κ})^{p/2}.  (13)

We can assume that

\sqrt{k}h/α < 1,  (14)

as otherwise (7) becomes clear. Let p = 2 − 4ϕ. Note that (14) implies p > 3/2, and by a straightforward calculation that the first term on the right hand side of (13) is greater than the second term. So

γ ≲ 2^{\frac{log_{2} log_{2} k}{2ϕ}} (\sqrt{k}h/α + \sqrt{k}(η_{4}^{−2k}\sqrt{κ}/α)^{1−2ϕ}) .  (15)

Case 2:

∑_{t<log_{2} k} 2^{t}ρ_{t} ≤ γ\sqrt{k}.

In this case we choose t_{0} such that ρ_{t_{0}} ≥ \frac{γ}{log_{2} k}. Substituting these in (10) we get

(\frac{δ^{p/2}}{log_{2} k} − η_{p}^{−p}δ\sqrt{k}) γ ≲ η_{p}^{−p}h + (δh)^{p/2} + (η_{4}^{−2k}\sqrt{κ})^{p/2}.  (16)

Taking δ ≈ \frac{α}{k(log_{2} k)^{4}} and p = 1 + \frac{1}{6 log_{2} k} we get

η_{p} ≥ α^{\frac{2−p}{2p}} (log_{2} k)^{−1/2},

and so

γ ≲ \frac{1}{α}\sqrt{k}(log_{2} k)^{4}h + (log_{2} k)\sqrt{h} + (\frac{η_{4}^{−2k}\sqrt{κ}k(log_{2} k)^{6}}{α} )^{1/2} .  (17)

From (15) and (17) we obtain

γ ≲ 2^{\frac{log_{2} log_{2} k}{ϕ}} (\sqrt{k}h/α + (η_{4}^{−2k}\sqrt{κ}k/α)^{1/2}) + (log_{2} k)\sqrt{h}.

Corollary 2.2. Let f : (𝔽_{2}^{n}, μ_{α}) → {0, 1} be a Boolean function. Let 2 < k ≤ n, and h and I_{κ} be defined as in (2) and (3) respectively. If 0 < κ < h^{4}α^{2k−2} and

ϕ = \frac{log_{2}(1/α) + \sqrt{log_{2}(1/h) log_{2} log_{2} k}}{16 log_{2}(1/h)} ,

then

∑_{S⊈I_{κ}} f̂(S)^{2} ≲ \sqrt{k}2^{\frac{log_{2} log_{2} k}{ϕ}} h/α + (log_{2} k)\sqrt{h}.

Proof. Note that ∑_{S⊈I_{κ}} f̂(S)^{2} ≤ γ + h, where γ is defined in Theorem 2.1. Moreover we

can assume that \frac{\sqrt{h}}{2} ≥ h as otherwise the corollary becomes obvious. Now the assumption κ < h^{4}α^{2k−2} completes the proof.

Acknowledgment

The author is grateful to Mahya Ghandehari for reading the draft version of this note, and her valuable comments.

References

[1] N. Alon, I. Dinur, E. Friedgut, and B. Sudakov, Graph products, Fourier analysis and spectral techniques, Geom. Funct. Anal., 14 (2004), pp. 913–940.

[2] J. Bourgain, On the distributions of the Fourier spectrum of Boolean functions, Israel J. Math., 131 (2002), pp. 269–276.

[3] E. Friedgut, Boolean functions with low average sensitivity depend on few coordinates, Combinatorica, 18 (1998), pp. 27–35.

[4] E. Friedgut, G. Kalai, and A. Naor, Boolean functions whose Fourier transform is concentrated on the first two levels, Adv. in Appl. Math., 29 (2002), pp. 427–437.

[5] M. Ghandehari and H. Hatami, Fourier analysis and large independent sets in powers of complete graphs, submitted, (2005).

[6] S. Khot and A. Naor, Nonembeddability theorems via Fourier analysis, in 46th IEEE Symposium on Foundations of Computer Science, 2005. to appear.

[7] G. Kindler and S. Safra, Noise-resistant boolean-functions are juntas, prerint.

[8] N. Linial, Y. Mansour, and N. Nisan, Constant depth circuits, Fourier transform, and learnability, J. Assoc. Comput. Mach., 40 (1993), pp. 607–620.

[9] E. Mossel, R. O’Donnell, and K. Oleszkiewicz, Noise stability of functions with low influences: invariance and optimality, in 46th IEEE Symposium on Foundations of Computer Science, 2005. to appear.

[10] K. Oleszkiewicz, On a nonsymmetric version of the Khinchine-Kahane inequality, in Stochastic inequalities and applications, vol. 56 of Progr. Probab., Birkhäuser, Basel, 2003, pp. 157–168.

[11] P. Wolff, Hypercontractivity of simple random variables, preprint, (2005).