[This post is authored by Gil Kalai, who has kindly “guest blogged” this week’s “open problem of the week”. – T.]

The entropy-influence conjecture seeks to relate two somewhat different measures as to how a boolean function has concentrated Fourier coefficients, namely the total influence and the entropy.

We begin by defining the total influence. Let \{-1,+1\}^n be the discrete cube, i.e. the set of \pm 1 vectors (x_1,\ldots,x_n) of length n. A boolean function is any function f: \{-1,+1\}^n \to \{-1,+1\} from the discrete cube to {-1,+1}. One can think of such functions as “voting methods”, which take the preferences of n voters (+1 for yes, -1 for no) as input and return a yes/no verdict as output. For instance, if n is odd, the “majority vote” function \hbox{sgn}(x_1+\ldots+x_n) returns +1 if there are more +1 variables than -1, or -1 otherwise, whereas if 1 \leq k \leq n, the “k^{th} dictator” function returns the value x_k of the k^{th} variable.

We give the cube \{-1,+1\}^n the uniform probability measure \mu (thus we assume that the n voters vote randomly and independently). Given any boolean function f and any variable 1 \leq k \leq n, define the influence I_k(f) of the k^{th} variable to be the quantity

I_k(f) := \mu \{ x \in \{-1,+1\}^n: f(\sigma_k(x)) \neq f(x) \}

where \sigma_k(x) is the element of the cube formed by flipping the sign of the k^{th} variable. Informally, I_k(f) measures the probability that the k^{th} voter could actually determine the outcome of an election; it is sometimes referred to as the Banzhaf power index. The total influence I(f) of f (also known as the average sensitivity and the edge-boundary density) is then defined as

I(f) := \sum_{k=1}^n I_k(f).

Thus for instance a dictator function has total influence 1, whereas majority vote has total influence comparable to \sqrt{n}. The influence can range between 0 (for constant functions +1, -1) and n (for the parity function x_1 \ldots x_k or its negation). If f has mean zero (i.e. it is equal to +1 half of the time), then the edge-isoperimetric inequality asserts that I(f) \geq 1 (with equality if and only if there is a dictatorship), whilst the Kahn-Kalai-Linial (KKL) theorem asserts that I_k(f) \gg \frac{\log n}{n} for some k. There is a result of Friedgut that if I(f) is bounded by A (say) and \varepsilon > 0, then f is within a distance \varepsilon (in L^1 norm) of another boolean function g which only depends on O_{A,\varepsilon}(1) of the variables (such functions are known as juntas).

Now we define the entropy. For this we recall the Fourier-Walsh expansion

f=\sum_{S \subset \{-1,+1\}^n} \hat f (S)U_S

of any real-valued function f: \{-1,+1\}^n \to {\Bbb R}, where U_S: \{-1,+1\}^n \to \{-1,+1\} is the monomial boolean function

U_S(x_1,\ldots,x_n) = \prod \{x_i: i\in S\}

and \hat f(S) is the Fourier-Walsh coefficient

\hat f(S) := \int_{\{-1,+1\}^n} f(x) U_S(x)\ d\mu(x).

Algebraically, the Fourier-Walsh expansion regards f as a polynomial combination of multilinear (square-free) monomials. It is of course a special case of the more general concept of a Fourier transform on an abelian group.

From Plancherel’s theorem we have

\sum_{S \subset \{-1,+1\}^n} \hat f(S)^2 = 1.

The influence can be written similarly:

I(f) = \sum_{S \subset \{-1,+1\}^n} \hat f(S)^2 |S|.

Note that this (together with Plancherel’s theorem) already implies the edge-isoperimetric inequality. The influence thus measures the average “height” of the spectrum, with each set S being viewed as having height |S|.

The spectral entropy E(f) of a boolean function f is defined as

E(f) = \sum_{S \subset \{-1,+1\}^n} \hat f(S)^2 \log_2 \frac{1}{\hat f(S)^2}

Roughly speaking, it measures the logarithm of the “width” of the Fourier transform of f; it is larger when the spectrum of f is “smeared out”. From Jensen’s inequality, the entropy is at least zero (with equality attained if and only if f is a monomial U_S for some S), and can be as large as n or so (this is the case for random functions, for instance).

Entropy/influence conjecture (Friedgut-Kalai, 1996) : We have E(f) \ll I(f) (i.e. E(f) \leq C I(f) for some absolute constant C.)

Comparing the Fourier-analytic formulae for the entropy and influence, we thus see that this conjecture asserts in some sense that if the Fourier coefficients are “smeared” then the Fourier coefficients are (on average) “high”. One strange feature of this conjecture is worth noting: the spectral entropy is invariant under arbitrary {\Bbb Z}/2{\Bbb Z} linear transformations, whereas the influence depends on a specific basis. Thus, the conjecture also implies that if Fourier coefficients are smeared, then they are high with respect to arbitrary bases.

On the other hand, both the entropy and influence are additive with respect to tensor products: if f: \{-1,1\}^n \to \{-1,1\} and g: \{-1,1\}^m \to \{-1,1\} are boolean functions, then the tensor product f \otimes g: \{-1,1\}^{n+m} \to \{-1,1\} is such that E(f \otimes g) = E(f) + E(g) andI(f \otimes g) = I(f) + I(g). This fact is of course consistent with the conjecture.

The entropy/influence conjecture, if true, has several consequences:

  1. Influences under symmetry. The motivation for the entropy/influence conjecture was to understand influences (and the related threshold behavior) under symmetry. Here is a simple case: suppose that f is symmetric under some transitive group of permutations acting on the variables. Suppose also that f is odd (i.e. f(-x)=-f(x)). In terms of voting methods, this means that the two candidates +1, -1 are treated equally, and that every individual voter is treated equally, though because we do not assume that the permutation group is 2-transitive, it is not necessarily the case that every pair of voters is treated equally.The entropy/influence conjecture then implies a lower bound of I(f) \gg \log n. An unconditional proof of this latter claim was obtained by Friedgut and Kalai using the KKL theorem mentioned earlier.For certain specific types of permutation groups, the entropy/influence conjecture predicts a precise improvement of this logarithmic lower bound. Slightly weaker versions of these improved bounds were established by Bourgain and Kalai, and
    interesting to see if the techniques extend to give some weaker form of the conjecture without symmetry.
    Results about influence under symmetry give some hope
    for similar results on influences under some sort of “spectral continuity” hypothesis. Roughly speaking, one expects assertions of the form “When the variables have geometric meaning and the Fourier coefficients respect the geometry and are “continuous”, then the influence must be high.”
  2. Mansour’s conjecture. Consider a Boolean function f described by a formula in conjunctive normal form of polynomial size in n. Yishay Mansour conjectured (see also this paper) that most of the Fourier coefficients are concentrated only on
    polynomial number of coefficients! This conjecture is still open. Using a theorem of Hastad and Boppana one can show I(f) \ll \log n; thus Mansour’s conjecture will follow from the entropy/influence conjecture. Mansour’s motivation was to show that such Boolean functions can be statistically learned (for uniform random input) in polynomial time. This was proved by Jackson using a different method.

There are some variants and strengthenings of this conjecture:

  1. Other probability distributions. The notions considered here and the entropy/influence-conjecture extend if we replace the unbiased Boolean variables with other product probability spaces, such as independent biased Boolean variables or Gaussian variables. It is also of interest to consider non-product spaces as well.
  2. Noise sensitivity versions. The entropy/influence conjecture shows that the mean height of the spectrum is \gg E(f). Can one guarantee a more robust conclusion, namely that the median height (or other percentiles) are also \gg E(f)? (This is called “noise sensitivity” but I will not explain why.) This claim is not true for the majority vote function, but some version of this may persist if one somehow rules out majority vote-like examples – for instance by considering boolean functions which are monotone, invariant under a transitive permutation group, with influence O(n^{1/3}) (say).
  3. Pivotals distribution versions. If f is a boolean function and x \in \{-1,+1\}^n, define \hbox{piv}(x) := \{ 1 \leq k \leq n: f(\sigma_k(x)) \neq f(x) \}. If x is selected randomly, then \hbox{piv}(x) is a random subset of \{1,\ldots,n\}; the distribution of this random variable is called the pivotals distribution. Note that the expected value of this distribution is precisely I(f), so the pivotals distribution is somewhat analogous to the spectral distribution. We can ask if some version of the influence/entropy inequality applies also here. (A direct translation fails for the majority function, so we will need a weaker form.) Existence of such connection gives interesting prediction for pivotal sets for certain interesting examples.
  4. Matrix function versions. The following related conjecture is based on discussions together with Itai Benjamini, Gadi Kozma, Elchanan Mossell, and Ofer Zeitouni.

Conjecture. There is an absolute constant \beta>0 with the following property. Let f: \mathfrak{so}(n) \to {\Bbb R} be an odd function on the space \mathfrak{so}(n) of antisymmetric real n \times n matrices, which is invariant under similarity of matrices. Then we have I(f) \geq n^\beta \|f\|_2, where the influence and L^2 norm are measured using the Gaussian probability distribution on \mathfrak {so}(n). [To define the influence of non-boolean functions, one considers the average variance of these functions in each of the coordinates in turn, keeping all the other coordinates frozen.]

Kalai and Safra have a survey on issues related to these conjectures.

[Update, Aug 17: Maths typo corrected. – T.]