A structure theorem for Boolean functions with small total influences (Q447936)

This article deals with Boolean (i.e., \(\{0,1\}\)-valued) functions on the product space \(X^{n}\), where \(X\) is a probability space. For \(1\leq j\leq n\) we say the influence of the \(j\)th variable on \(f\) is \[ I_{f}(j) = \mathbb{P}\bigl[f(x_{1},\ldots x_{j-1},x_{j},x_{j+1}\ldots x_{n})\neq \mathbb{P}(x_{1},\ldots x_{j},y_{j},x_{j+1},\ldots x_{n})\bigr] \] where the \(x_{i}\)s and \(y_{i}\)s are independent random variables, all distributed according to the probability measure on \(X\). Informally, it measures the sensitivity of a function to a change of that variable. The main result of the paper under review is basically to show that any measurable Boolean function on \(X^{n}\) can be approximated by a special kind of function, a so-called \(k\)-pseudo junta for a suitable \(k\) depending on the influence of \(f\) \textit{but not on} \(n\). More precisely, given a measurable function \(f: X^{n}\rightarrow \{0,1\}\) and \(\epsilon>0\) there is an \(e^{10^{15}\epsilon^{-3}\lceil I_{f}\rceil ^{3}}\)-pseudo junta such that the \(L_{1}\)-norm \(\parallel f-h\parallel_{1}\leq \epsilon\). Here a \(k\)-pseudo junta is defined as follows. Given a collection \({\mathcal J}=\{J_{S}\}\), where \(S\) ranges over subsets of \([n]=\{1,2,\ldots n\}\), of measurable functions \(J_{S}: X^{S}\rightarrow \{0,1\}\) we define a map \(J_{\mathcal J}: X^{n}\rightarrow {\mathcal P}([n])\) by \(J_{\mathcal J}(x)=\bigcup_{S\subseteq [n], J_{S}(x)=1}S\) and let \({\mathcal F}_{\mathcal J}\) be the \(\sigma\)-algebra induced by the (measurable) function \(x\rightarrow (J_{\mathcal J}( x),x_{J_{\mathcal J}(x)})\), i.e. the coarsest \(\sigma\)-algebra on \(X^{n}\) with respect to which this function is measurable. Then we say a \(k\)-pseudo junta is a Boolean function on \(X^{n}\) measurable with respect to \({\mathcal F}_{\mathcal J}\) for some \({\mathcal J}\) such that \(\int | J_{\mathcal J}(x)| dx \leq k\). To explain the term pseudo-junta, note that if \(A\subseteq [n]\) with \(| A| \leq k\) every measurable Boolean function on \(X^{n}\) which depends only on co-ordinates in \(A\) (when \(k\) is small, this is what has in previous literature been called a junta) is a \(k\)-pseudo junta (define \({\mathcal J}\) by saying \(J_{S}\equiv 1\) if \(S=A\) and \(J_{S}\equiv 0\) otherwise). It is not hard to show that a \(k\)-pseudo junta \(f\) has \(I_{f}\leq 2k\): the main result above is in some sense an inverse result to this observation. Consequences include an improvement of a result of Bourgain: the (new) result says that, given an increasing Boolean function \(f\) on \(\{0,1\}^{n}\) with the Bernoulli measure on \(X\) (i.e., we get 1 with probability \(p\), 0 with probability \(1-p\)) for which \(\int f=\alpha >0\), and given \(\epsilon>0\), for \(p\leq 1/2\) there is \(S\subseteq [n]\) with \(| S| \leq e^{10^{12}\lceil I_{f}\rceil ^{2}\alpha^{-2}\epsilon^{-2}}\) such that \(\mathbb{E}(f(x)| x_{S}=(1,1,\ldots 1))\geq 1-\epsilon\). Here again \(x\) takes values in \(\{0,1\}^{n}\) according to the product Bernoulli distribution, and \(x_{S}\) denotes \((x_{i}:\, i\in S)\). The paper also notes why such results are of interest in the theory of threshold phenomena and their sharpness in e.g. statistical physics and in hardness of approximation in theoretical computer science, and notes that a more general conjecture of Friedgut on increasing graph properties [\textit{E. Friedgut}, ``Sharp thresholds of graph properties, and the \(k\)-sat problem,'' J. Am. Math. Soc. 12, No. 4, 1017--1054 (1999; Zbl 0932.05084)] remains open.