Boolean Functions whose Fourier Transform is Concentrated on the First Two Levels

Ehud Friedgut, Gil Kalai and Assaf Naor Institute of Mathematics, Hebrew University, Jerusalem, Israel

Abstract

In this note we describe Boolean functions f(x_{1}, x_{2}, …, x_{n}) whose Fourier coefficients are concentrated on the lowest two levels. We show that such a function is close to a constant function or to a function of the form f = x_{k} or f = 1 − x_{k}. This result implies a “stability” version of a classical discrete isoperimetric result and has an application in the study of neutral social choice functions. The proofs touch on interesting harmonic analysis issues.

1 Introduction

A fundamental result in extremal combinatorics asserts that for every subset A of the discrete cube Ω_{n} = {0, 1}^{n} the number of edges from A to its compliment it at least min(|A|, 2^{n} − |A|). The only examples of equality are A = ∅, A_{j} = {(x_{1}, x_{2}, …, x_{n}) ∈ Ω_{n} : x_{j} = 0, for some j, 1 ≤ j ≤ n and their complements. The precise minimum of the number of edges from A to its complement as a function of |A| is also known, see Hart (1976). The main result of this paper is that if

the number of edges between A and its complement is “close” to |A| then the set A is “close” to the examples described above. Equivalently, we describe Boolean functions whose Fourier transform is concentrated on the lowest two levels. This result touches on interesting issues in harmonic analysis and is used in Kalai (2001), to derive a “stability” version of Arrow’s theorem for neutral social choice functions. We will use the terminology of Kalai (2001). Our main result is:

Theorem 1.1. If f is a Boolean function, ∥f∥_{2}^{2} = p and if ∑_{|S|>1} f̂^{2}(S) ≤ δ then either p < K′δ or p > 1 − K′δ or ∥f(x_{1}, x_{2}, …, x_{n}) − x_{i}∥_{2}^{2} ≤ Kδ for some i or ∥f(x_{1}, x_{2}, …, x_{n}) − (1 − x_{i})∥_{2}^{2} ≤ Kδ for some i. Here, K′ and K are absolute constants.

For A ⊂ Ω_{n} let E(A) denotes the number of edges between A and its complement in Ω_{n}.

Corollary 1.2. There exists an absolute constant K with the following property. Let A ⊂ Ω_{n} and suppose that |A| ≤ 2^{n−1}. If E(A) ≤ (1 + ϵ) · |A| then for some i, 1 ≤ i ≤ n P(A△A_{j}) ≤ K · ϵ or P(A△Ā_{j}) ≤ K · ϵ.

Suppose that |A| ≤ 2^{n−1} and let p = ∥χ_{A}∥_{2} = |A|/2^{n−1}. Let I(A) = E(A)/2^{n−1}. I(A) is refered to as the total influence of A, as the average sensitivity of A and as the edge boundary or edge-expansion constant of A. It is well known that if f = χ_{A},

I(A) = 4 ∑_{S⊂[n]} f̂^{2}(S)|S|.

Since ∑_{S⊂[n],S≠∅} f̂^{2}(S) = 2p, we obtain that E(A) ≤ |A| with equality only of p = 1/2 and f̂(S) = 0 if |S| > 1. By the same argument we see how Theorem 1.1 implies Corollary 1.2. Corollary 1.2 complements a result by Friedgut (1998). Friedgut showed that if I(S) is bounded from above by a constant K then f = χ_{A} is close to a “Junta” namely to a function which depends on a bounded number of variables. We show here that if I(A) ≤ 1+ϵ then χ_{A} is close to “dictatorship”.

We describe now briefly how Theorem 1.1 is applied in [6]. We consider a society consisting of n individuals, which is faced with a finite set of alternatives. A profile is a list of n linear orders, which we think of as the list of preferences of each individual. A social choice function is a function which given such profile, yields an asymmetric relation on the alternatives. We think of a social choice function as a method with which the society makes a decision between each two alternatives, based on the preferences of each individual. The social choice (i.e. the value of the social choice function) is called rational if it is an order relation on the alternatives. Social choice functions are assumed to be independent of irrelevant alternatives, i.e. for every two alternatives a and b the society’s choice between a and b depends only on the individual preferences between these two alternatives. A social choice function is called a dictatorship if it depends only on the preferences of one particular individual (such an individual is called a dictator. Note that a dictator might be ill fortuned in the sense that the society always chooses the exact opposite of his preference). Finally, a social choice function is called neutral if it is invariant under permutations of the alternatives.

In [6] Theorem 1.1 is applied to show that if the outcome of a neutral social choice function for random profiles is almost surely rational then the social choice is approximately a dictatorship:

Theorem 1.3. There exists an absolute constant K such that the following assertion holds. For every ϵ > 0 and for every neutral social choice function, if the probability that the social choice is irrational is less than ϵ then there is an individual such that for every pair of alternatives the probability that the social choice is different from his choice is less that K · ϵ.

We refer to [6] for a proof of Theorem 1.3. We also refer to [6] and the references therein for a detailed description of related concepts and results concerning the social choice problem.

We will present two proofs for Theorem 1.1:

2 Proof I

2.1 Reduction to weighted majority

The proof is based on a reduction to the case of weighted majority functions followed by a further reduction to an auxiliary result Proposition 2.2. A simple proof of Proposition 2.2 based on a recent theorem by König, Schütt and Tomczak-Jaegermann (2000) gives best estimates for large values of δ. We present a completely elementary proof which gives best results for small values of δ.

First, we state the following simple proposition:

Proposition 2.1. Let t_{1}, t_{2}, …, t_{n} be real numbers such that ∑ t_{i}^{2} = p > 0. Put t = (t_{1}, t_{2}, …, t_{n}) and T = ∑ t_{i}. For a Boolean function f let U_{t}(f) = ∑ f̂({i})t_{i}. Then U_{t}(f) attains its maximum value when f is the following weighted majority function: f(S) = 1 iff ∑_{i∈S} t_{i} < T/2.

Proof: The proof follows at once from the following simple relation:

U_{t}(f) = ∑_{S⊂[n]} 2^{−n}f(S) (∑_{i∉S} t_{i} − ∑_{i∈S} t_{i}) = ∑_{S⊂[n]} 2^{−n} (T − 2 ∑_{i∈S} t_{i}) f(S).

In order to maximize U_{t}(f) we need to set f(S) = 1 when T − 2 ∑_{i∈S} t_{i} is positive and f(S) = 0 when T − 2 ∑_{i∈S} t_{i} is negative. □

It follows from Proposition 2.1 that if g is an arbitrary Boolean function then ∑_{i=1}^{n} f̂({i})ĝ({i}) attained is maximum when f is a weighted majority function. Remark: Proposition 2.1 can be extended to identify the Boolean functions with maximum inner product with ∑ α_{S}u_{S}. This may have some further applications.

We now return to the proof of Theorem 1.1. Let t_{i} = f̂({i}), i = 1, 2, …, n and t = (t_{1}, t_{2}, …, t_{n}). Consider now the vector T = (T_{S} : S ⊂ [n]) of length 2^{n} whose entries are given by

T_{S} = (∑_{i∉S} t_{i} − ∑_{i∈S} t_{i}) .

Note that

∥T ∥_{2}^{2} = 2^{−n} ∑_{S⊂[n]} (∑_{i∈S} t_{i} − ∑_{i∉S} t_{i})^{2} = ∑ t_{i}^{2} ≤ p − p^{2}.

Note also that

U_{t}(f) ≤ \frac{1}{2} ∑_{S⊂[n]} 2^{−n} |∑_{i∉S} t_{i} − ∑_{i∈S} t_{i}| = ∥T ∥_{1} ≤ ∥T ∥_{2} =

= \frac{1}{2} ( ∑_{S⊂[n]} 2^{−n} (∑_{i∉S} t_{i} − ∑_{i∈S} t_{i})^{2})^{1/2} ≤ \frac{\sqrt{p − p^{2}}}{2} .

In order that

U_{t}(f) ≥ (1 − δ)(p − p^{2}),

and unless p is close to 0 or 1, we need that p is close to 1/2 and that the 2-norm of the vector T is close to its 1-norm.

Recall the following elementary fact: If v = (a_{1}, a_{2}, …, a_{n}) is a vector (say positive) such that ∥v∥_{2} = 1 and ∥v∥_{1} > 1 − δ, then the variance of a_{1}, …, a_{n} is at most 2δ.

It follows that the vector T is at a distance of at most 2δ from a vector S such that the absolute value of its coordinates are the same.

At this point it remains to show that this can only occur if for the original vector t all coordinates but one are close to zero.

Proposition 2.2. Let v = (a_{1}, a_{2}, ..., a_{n}) be a unit vector of length n and suppose that a_{1} ≥ a_{2} ≥ a_{3} … ≥ 0. Consider all the 2^{n} sums S(ε) = ε_{1}a_{2} + ε_{2}a_{2} + ... + ε_{n}a_{n} where ε_{i} is +1 or -1. If the variance of |S(ε)| is smaller than δ, then a_{1} > 1 − K′δ.

2.2 Proposition 2.2: first proof

We begin by giving a short proof of Proposition 2.2 which is based on a recent result of König, Schütt and Tomczak-Jaegermann (2000). Later we present a self-contained proof of the proposition which gives a better estimate for K′ for small δ. König, Schütt and Tomczak-Jaegermann’s theorem can be stated as follows:

Theorem 2.3. Let a_{1}, a_{2}, …, a_{n} be real numbers and let E be the expected value of the 2^{n} expressions |ε_{1}a_{1} + ε_{2}a_{2} + ⋯ + ε_{n}a_{n}| where each ε_{i} is +1 or -1. Then

|E − \sqrt{\frac{2}{π}} \sqrt{∑_{i=1}^{n} a_{i}^{2}}| ≤ (1 − \sqrt{\frac{2}{π}} ) max_{1≤i≤n} |a_{i}|.  (2.1)

Recall that the expectation of S(ε)^{2} is 1 and therefore the variance V of |S(ε)| is (1 − E^{2}) = (1 − E)(1 + E). Using Theorem 2.3 we obtain

1 − E = 1 − \sqrt{\frac{2}{π}} + \sqrt{\frac{2}{π}} − E ≥ (1 − \sqrt{\frac{2}{π}} ) (1 − a_{1}).

This completes the proof of Proposition 2.2.

This result can be further improved as follows: By Szarek’s inequality (Khinchine’s inequality with best constant. See Szarek (1976) or Latała and Oleszkiewicz (1994) for a short proof), E ≥ 1/\sqrt{2}. On the other hand, if we define X = a_{2}ε_{2} + … + a_{n}ε_{n}, then since X is symmetric,

E = 𝔼|a_{1}ε_{1} + X| = 𝔼 (\frac{|a_{1}ε_{1} + X| + |a_{1}ε_{1} − X|}{2}) ≥ a_{1}.

Hence,

V ≥ (1 − \sqrt{\frac{2}{π}} ) (1 − a_{1}) (1 + max \{\frac{1}{\sqrt{2}}, a_{1}\}) ≥

≥ (1 − \sqrt{\frac{2}{π}} ) max \{(1 − a_{1}^{2}), (1 + \frac{1}{\sqrt{2}}) (1 − a_{1})\} ,

and this yields our theorem with the best constants that we managed to obtain for large δ.

Remark: It is worth noting that Theorem 2.3 implies that V ar(S^{2}) ∼ (𝔼S^{2})V ar(|S|) where the constants of equivalence are independent of n and a_{1}, …, a_{n} (this can be viewed as a second-order Khinchine inequality and it would be interesting to derive similar statements for other powers of S). In order to prove this, note that the inequality V ar(X^{2}) ≥ (𝔼X^{2})V ar(X) holds for any non-negative random variable X with finite fourth moment. Indeed, we can assume that 𝔼X^{2} = 1 and by Hölders inequality:

1 = 𝔼X^{2} = 𝔼X^{\frac{2}{3} + \frac{1}{3} ·4} ≤ (𝔼X)^{2/3}(𝔼X^{4})^{1/3}.

Hence, 𝔼X^{4} ≥ 1/(𝔼X)^{2} so that

(𝔼X)^{2} + 𝔼X^{4} ≥ (𝔼X)^{2} + \frac{1}{(𝔼X)^{2}} =

= 2 + (𝔼X − \frac{1}{𝔼X} )^{2} ≥ 2,

which gives that 𝔼X^{4} − 1 ≥ 1 − (𝔼X)^{2} as required. To prove the reverse inequality assume that 𝔼S^{2} = 1, in which case:

V ar(S^{2}) = 𝔼 (∑_{i=1}^{n} a_{i}ε_{i})^{4} − 1 = ∑_{i=1}^{n} a_{i}^{4} + 6 ∑_{i≠j} a_{i}^{2}a_{j}^{2} − 1 =

= 5 (1 − ∑_{i=1}^{n} a_{i}^{4}) ≤ 5(1 − a_{1}^{4}) ≤ 10(1 − a_{1}^{2}).

On the other hand, we have seen that V ar(|S|) ≥ (1 − \sqrt{2/π})(1 − a_{1}^{2}) so that:

V ar(S^{2}) ≤ \frac{10}{1 − \sqrt{2/π}} · (𝔼S^{2})V ar(|S|).

We do not know what the best constants are in the above inequalities.

2.3 Proposition 2.2: An elementary proof

We now give an elementary proof with better estimates for K′ as long as δ is sufficiently small. We continue to use the notation X = a_{2}ε_{2} + … + a_{n}ε_{n}. We begin by noting that the following identity holds:

E = a_{1} + 𝔼(|X| − a_{1})1_{{|X|≥a_{1}}}.

Indeed, using the fact that X and ε_{1} are independent and the fact that X is symmetric, we obtain:

E = 𝔼|a_{1}ε_{1} + X| = \frac{1}{2}𝔼|X + a_{1}| + \frac{1}{2}𝔼|X − a_{1}| = 𝔼|X − a_{1}| =

= 𝔼(X − a_{1})1_{{X≥a_{1}}} + 𝔼(a_{1} − X)1_{{X<a_{1}}} = = 𝔼|X|1_{{|X|≥a_{1}}} + a_{1}P (|X| < a_{1}) = = a_{1} + 𝔼(|X| − a_{1})1_{{|X|≥a_{1}}}.

By the Chernoff bound, for every u > 0:

P (|X| ≥ u) = P (\frac{|X|}{\sqrt{1 − a_{1}^{2}}} ≥ \frac{u}{\sqrt{1 − a_{1}^{2}}} ) ≤

≤ 2 exp (−\frac{1}{4} · \frac{u^{2}}{1 − a_{1}^{2}} ) .

Now,

E ≤ a_{1} + 𝔼|X|1_{{|X|≥a_{1}}} =
= a_{1} + ∫_{a_{1}}^{∞} P (|X| ≥ u)du ≤

≤ a_{1} + 2 ∫_{a_{1}}^{∞} exp (−\frac{1}{4} · \frac{u^{2}}{1 − a_{1}^{2}} ) du =

= a_{1} + 4\sqrt{1 − a_{1}^{2}} ∫_{a_{1}/(2\sqrt{1−a_{1}^{2}})}^{∞} e^{−v^{2}}dv ≤

≤ a_{1} + 4\sqrt{1 − a_{1}^{2}} ∫_{a_{1}/(2\sqrt{1−a_{1}^{2}})}^{∞} \frac{v}{a_{1}/(2\sqrt{1 − a_{1}^{2}})}e^{−v^{2}}dv =

= a_{1} + 4 · \frac{1 − a_{1}^{2}}{a_{1}} exp (−\frac{1}{4} · \frac{a_{1}^{2}}{1 − a_{1}^{2}} ) .

Finally:

δ ≥ V = 1 − E^{2} ≥ 1 − a_{1}^{2} [1 + \frac{4(1 − a_{1}^{2})}{a_{1}^{2}} exp (−\frac{1}{4} · \frac{a_{1}^{2}}{1 − a_{1}^{2}} )]^{2} .

This directly implies that:

a_{1} ≥ 1 − \frac{δ}{2} − O(δ^{2}).

□.

3 Proof II

This proof relies on the Bonamie-Beckner inequality.

Lemma 3.1. Let f : {0, 1}^{n} → {0, 1} . Assume that

∑_{|T |>1} f̂^{2}(T) = ϵ.

Then there exists i and D_{i}, which is a linear function of x_{i}, such that

∥f − D_{i}∥_{2}^{2} < (1 + \frac{17496}{1/4 − ϵ}) ϵ.

Proof: First, as pointed out to us by Guy Kindler, we may assume without loss of generality that f is balanced, i.e. that P r(f = 1) = 1/2. To see this let f(x) = f(x_{1}, …, x_{n}) and define a Boolean function g(x_{1}, …, x_{n}, y) as follows:

g(x, 0) = f(x), g(x, 1) = 1 − f(1 − x)

where 1−x is the vector (1−x_{1}, … 1−x_{n}). Clearly g is balanced, ∑_{|S|>1} g^{2}(S) = ∑_{|S|>1|} hatf^{2}(S) and if g ≈ D_{i} then f ≈ D_{i}. Let

S = ∑_{|T |≤1} f̂(T)u_{T}

and

L = ∑_{|T |>1} f̂(T)u_{T} .

(S and L stand for small and large) and let

R = S^{2} − S.

We will show that since S is close to being Boolean, R is typically close to 0, and we will deduce some information on the Fourier coefficients of f. It is straightforward to compute the Fourier coefficients of R: First note that from the orthogonality of L and S we have

E(S^{2}) + E(L^{2}) = E(f^{2}) = 1/2.

Hence

E(S^{2}) = 1/2 − ϵ

and

E(S) = 1/2.

Therefore,

R̂(∅) = E(R) = −ϵ.

Next, for any i R̂(i) = 0. Finally, for i ≠ j

R̂(ij) = 2f̂(i)f̂(j).

This yields

R = −ϵ + 2 ∑ f̂(i)f̂(j)u_{ij}.

Lemma 3.2.

E(R^{2}) ≤ 8748ϵ.

Corollary 3.3. There exists i such that f̂^{2}(i) ≥ 1/4 − (1 + \frac{17496}{(1/4−ϵ)}) .

Clearly this corollary implies Lemma 3.1: We know that f̂(∅) = 1/2 and that ∑ f̂(T)^{2} = 1/2, hence

∥f − 1/2 + f̂(i)u_{i}∥_{2}^{2} = ∑_{T ≠i,∅} f̂^{2}(T) ≤ (1 + \frac{17496}{1/4 − ϵ}) .

Proof of corollary: Since E(R^{2}) = ∑ R̂(T)^{2} we have by summing only over the sets {ij}

∑ f̂^{2}(i)f̂^{2}(j) ≤ 8748ϵ.

On the other hand, since

E(S^{2}) = f̂(∅)^{2} + ∑ f̂(i)^{2} = 1/2 − ϵ

we have

∑ f̂(i)^{2} = 1/4 − ϵ.

Hence, if max f̂^{2}(i) = δ

(1/4 − ϵ)^{2} ≤ 2 · 8748ϵ + (1/4 − ϵ)δ

which gives the desired bound on δ.

□

Proof of Lemma 3.2 : The proof consists of two parts: first we will show that typically R obtains values close to 0. Then we will use a hypercontractive estimate due to Beckner and Bonami to bound higher moments of R in terms of its second moment showing that its tail decays fast enough.

Lemma 3.4. Let 0 < α < 1/4 be a constant to be chosen later. Let

p = P rob(|R| > α).

Then

p ≤ \frac{16ϵ}{α^{2}}.

We defer the proof of this lemma for the moment.

Lemma 3.5.

E(R^{2}) ≤ \frac{α^{2}}{1 − 36\sqrt{ϵ}/α}.

Choosing the optimal value of α (which is 54\sqrt{ϵ}) immediately proves Lemma 3.2. So, to finish the proof we now present the proofs of Lemmas 3.4 and 3.5. Proof of Lemma 3.4: Recall that S = f − L and that E(L^{2}) = ϵ. Using the fact that f^{2} = f yields

R = (f − L)^{2} − (f − L) = L^{2} + L(1 − 2f).

A simple analysis of the different possible cases shows that if |L| < α/4, then |R| < α. Hence by Markov’s inequality

P r[|R| > α] ≤ P r[L^{2} > α^{2}/16] ≤ \frac{16ϵ}{α^{2}}.

□

Proof of Lemma 3.5: For convenience of notation let X = E(R^{2}) and Y = E(R^{4}). We now need some information on the relative values of X and Y. To this end we use a powerful hypercontractive estimate proven independently by Beckner and Bonami.

Lemma 3.6 (Beckner (1975), Bonami (1970)). Let f : {0, 1}^{n} → ℝ be a function that is a linear combination of {u_{T} : |T | ≤ k}. Let p > 2. Then

∥f∥_{p} ≤ (\sqrt{p − 1})^{k}∥f∥_{2}.

In our particular case, taking p = 4 and k = 2 gives

Y ≤ 81X^{2}.

Using this we obtain

X = E(R^{2}) = (1 − p)E(R^{2}|R^{2} ≤ α^{2}) + pE(R^{2}|R^{2} > α^{2}) ≤
(1 − p)α^{2} + p\sqrt{E(R^{4}|R^{2} > α^{2})} ≤

(1 − p)α^{2} + p\sqrt{\frac{Y}{p}} ≤

(1 − p)α^{2} + \sqrt{p}9X ≤

α^{2} + \frac{4\sqrt{ϵ}}{α}9X.

This yields

X ≤ \frac{α^{2}}{1 − 36\sqrt{ϵ}/α}.

□

4 Acknowledgments

We wish to thank Guy Kindler for various remarks.

References

[1] Beckner, W. (1975) Inequalities in Fourier analysis, Annals of Math. 102, 159–182.

[2] Bonami, A. (1970), Etude des coefficients Fourier des fonctiones de L^{p}(G), Ann. Inst. Fourier 20, 335–402.

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

[4] Hart, S., A note on the edges of the n-cube. Discrete Math. 14 (1976), no. , 157–163.

[5] Kahn, J., G. Kalai and N. Linial (1988), The influence of variables on boolean functions, Proc. 29-th Ann. Symp. on Foundations of Comp. Sci., (1988), 68–80.

[6] Kalai, G.(2001), A Fourier-Theoretic Perspective for the Condorcet Paradox and Arrow’s theorem, Adv. Appl. Math., this issue.

[7] König, H., C. Schütt, N. Tomczak-Jaegermann (1999), Projection constants of symmetric spaces and variants of Khintchine’s inequality. J. Reine Angew. Math. 511, 1–42.

[8] Latała, R. and K. Oleszkiewicz (1994), On the best constant in the Khinchin-Kahane inequality. Studia Math. 109 (1994), no. 1, 101-104.

[9] Szarek, S. J. (1976), On the best constant in the Khinchin inequality. Studia Math. 58, no. 2, 197-208.