120 Boolean Analysis — Restriction Fourier
120.1 Overview
This module analyses how a random restriction acts on the Fourier spectrum of a real-valued Boolean function \(f : \{ 0,1\} ^n \to \mathbb {R}\). It gives a closed form for the Fourier coefficients of the restricted function \(f_\rho \), factors the Bernoulli restriction measure coordinate by coordinate, and derives O’Donnell’s Proposition 4.17: \(\mathbb {E}_\rho [\widehat{f_\rho }(S)] = p^{\left\lvert S\right\rvert }\widehat{f}(S)\) and \(\mathbb {E}_\rho [\widehat{f_\rho }(S)^2] = \sum _{U \supseteq S} p^{\left\lvert S\right\rvert }(1-p)^{\left\lvert U \setminus S\right\rvert }\widehat{f}(U)^2\), together with the probability form \(\Pr _\rho [U \cap J = S] = p^{\left\lvert S\right\rvert }(1-p)^{\left\lvert U\setminus S\right\rvert }\) for the set \(J\) of free coordinates.
120.2 Declarations
Write \(\sigma \colon \{ 0,1\} \to \{ -1,1\} \) for the sign encoding, \(\sigma (0)=1\) and \(\sigma (1)=-1\), and for a function \(g\) on the cube (Boolean- or real-valued) let \(g_\rho \) denote its restriction along \(\rho \), obtained by reading each free coordinate from the input and each fixed coordinate from \(\rho \). Let \(f\colon \{ 0,1\} ^n\to \{ 0,1\} \) be a Boolean-valued function and let \(\rho \) be a restriction on \(n\) variables. Then restricting the real-valued function \(x\mapsto \sigma (f(x))\) along \(\rho \) agrees with first restricting \(f\) and then applying the sign encoding; that is, \((\sigma \circ f)_\rho =\sigma \circ f_\rho \), so that for every point \(x\),
Let \(\rho : \mathrm{Fin}\, n \to \mathrm{Option}\, \mathrm{Bool}\) be a restriction on \(n\) variables, and let \(i \in \mathrm{Fin}\, n\) be a coordinate. Then \(i\) belongs to the set of free variables of \(\rho \) if and only if \(\rho (i)\) is unset; that is, exactly when \(\rho \) leaves the coordinate \(i\) free rather than fixing it to a Boolean value.
Let \(\rho \) be a restriction on \(n\) variables, let \(J\subseteq [n]\) be its set of free coordinates, and let \(U\subseteq [n]\) and \(x\in \{ 0,1\} ^n\) be arbitrary. Write \(\hat x\) for the extension of \(x\) by \(\rho \), namely the point of \(\{ 0,1\} ^n\) that agrees with \(x\) on the free coordinates and takes the fixed value of \(\rho \) on the remaining ones. Then the Walsh character \(\chi _U\) evaluated at \(\hat x\) factors as
where \(b_i\) denotes the Boolean value that \(\rho \) fixes at coordinate \(i\) and \(\sigma \) is the sign encoding sending \(\mathtt{false}\mapsto 1\) and \(\mathtt{true}\mapsto -1\). Thus the character splits into a Walsh character in the free coordinates lying in \(U\) times a constant \(\pm 1\) sign contributed by the fixed coordinates of \(U\).
Let \(f : \{ 0,1\} ^n \to \mathbb {R}\), and let \(\rho \) be a restriction on \(n\) variables; write \(J \subseteq [n]\) for its set of free coordinates, namely the coordinates left unset by \(\rho \). Let \(f_\rho : \{ 0,1\} ^n \to \mathbb {R}\) be the restricted function whose value at a point \(x\) is obtained by evaluating \(f\) at the assignment that agrees with \(x\) on the free coordinates in \(J\) and takes the bit fixed by \(\rho \) on every other coordinate. Then for every \(S \subseteq [n]\),
where \(\sigma \) denotes the sign encoding and, for each \(i \in U \setminus J\) (which lies outside \(J\) and is therefore a coordinate fixed by \(\rho \)), \(\rho _i \in \{ \mathtt{false},\mathtt{true}\} \) is the bit that \(\rho \) assigns there. This is O’Donnell’s Corollary 3.22.
Fix \(n \in \mathbb {N}\), and for each coordinate \(i \in \{ 1,\dots ,n\} \) let \(h_i : \{ \mathtt{true},\mathtt{false},\ast \} \to \mathbb {R}\) be a real-valued weight assigned to the three possible states of that coordinate (fixed to true, fixed to false, or left free). Then summing the product of these weights over all \(3^n\) restrictions \(\rho \) on \(n\) variables equals the product over coordinates of the coordinatewise total weights:
where \(\rho \) ranges over all restrictions on \(n\) variables and \(v\) ranges over the three per-coordinate states.
Fix \(n \in \mathbb {N}\) and a real parameter \(p\), and recall that a restriction on \(n\) variables is a map \(\rho : \mathrm{Fin}\, n \to \mathrm{Option}\, \mathrm{Bool}\) assigning each variable either a fixed Boolean value or the free marker \(\mathrm{none}\). Write \(w_p(\rho ) = p^{\, k}\bigl(\tfrac {1-p}{2}\bigr)^{\, n-k}\) for its Bernoulli weight, where \(k\) is the number of free variables of \(\rho \), and let \(\omega _p\) be the per-variable weight given by \(\omega _p(\mathrm{none}) = p\) and \(\omega _p(v) = \tfrac {1-p}{2}\) for a fixed value \(v\). Then for every family \(h_i : \mathrm{Option}\, \mathrm{Bool} \to \mathbb {R}\) indexed by \(i \in \mathrm{Fin}\, n\),
where the outer sum ranges over all restrictions \(\rho \) on \(n\) variables and each inner sum ranges over \(v \in \mathrm{Option}\, \mathrm{Bool}\).
Given sets \(U, S \subseteq [n]\), a coordinate \(i\) and a per-coordinate value \(v\), the local factor is \(1\) if \(i \in S\) and \(v = \mathtt{none}\) (the coordinate must be free), \(0\) if \(i \in S\) and \(v\) is fixed; for \(i \in U \setminus S\) it is \(0\) when \(v = \mathtt{none}\) and \(\mathrm{boolToSign}(b)\) when \(v = \mathtt{some}\ b\); and \(1\) for all remaining coordinates. It encodes the event \(U \cap \mathrm{freeVars} = S\) together with the sign contributed on \(U \setminus S\).
Let \(U, S \subseteq [n]\) with \(S \subseteq U\), and let \(\rho \) be a restriction on \(n\) variables whose free-variable set is \(J\). Write \(\sigma (b) \in \{ \pm 1\} \) for the sign encoding of a bit \(b\), and let \(\ell (U,S,i,\rho (i))\) denote the per-coordinate local factor at coordinate \(i\). Then
where the left-hand side is read as \(0\) whenever \(U \cap J \neq S\). Equivalently, the product on the right vanishes unless the free coordinates of \(\rho \) lying in \(U\) are exactly \(S\), in which case it equals the product of the \(\pm 1\)-encodings of the bits that \(\rho \) fixes on \(U \setminus J\).
Fix a real parameter \(p\), two coordinate sets \(U, S \subseteq [n]\), and a coordinate \(i \in [n]\). Writing \(w_p\) for the per-variable Bernoulli weight — which assigns \(p\) to the free value and \((1-p)/2\) to each of the two fixed values — and \(\ell _{U,S,i}\) for the per-coordinate local factor at \(i\), the weighted sum over the three possible per-coordinate values \(v\) (free, or fixed to either Boolean) is
Fix a real parameter \(p\), subsets \(U, V, S \subseteq [n]\), and a coordinate \(i \in [n]\). Averaging over the three per-coordinate values \(v\) — the free value and the two fixed signs — with the per-variable weight \(w_p(v)\), the product of the two local factors, one for the pair \((U,S)\) and one for the pair \((V,S)\), satisfies
where \(w_p\) denotes the per-variable weight and \(\ell _{W,S}\) the local factor determined by the sets \(W\) and \(S\).
Let \(n\) be a natural number, let \(p \in \mathbb {R}\), and let \(S, U \subseteq \{ 1, \dots , n\} \). For each coordinate \(i\), assign the weight \(p\) if \(i \in S\), the weight \(1 - p\) if \(i \in U \setminus S\), and the weight \(1\) otherwise. Then the product of these weights over all \(n\) coordinates equals
Let \(f:\{ 0,1\} ^n\to \mathbb {R}\) be a Boolean function, let \(S\subseteq [n]\) be a frequency set, and let \(p\in \mathbb {R}\). For a restriction \(\rho \) on \(n\) variables, write \(f_\rho \) for the restricted function and \(k(\rho )\) for the number of free variables of \(\rho \). Summing the Fourier coefficient \(\widehat{f_\rho }(S)\) over all restrictions \(\rho \), each weighted by its Bernoulli weight \(p^{k(\rho )}\bigl(\tfrac {1-p}{2}\bigr)^{\, n-k(\rho )}\), gives
(When \(0\le p\le 1\) these weights form the distribution of a Bernoulli\((p)\)-random restriction, and the left-hand side is the expectation \(\mathbb {E}_\rho [\widehat{f_\rho }(S)]\).)
Fix a dimension \(n\), a real number \(p\), a Boolean function \(f:\{ 0,1\} ^n\to \mathbb {R}\), and a set \(S\subseteq [n]\). For a restriction \(\rho \) on the \(n\) variables, let \(k(\rho )\) denote its number of free variables and give it the Bernoulli weight \(w_p(\rho )=p^{\, k(\rho )}\bigl(\tfrac {1-p}{2}\bigr)^{\, n-k(\rho )}\); write \(f_\rho \) for the restriction of \(f\) by \(\rho \) and \(\hat g(T)\) for the Fourier–Walsh coefficient of a Boolean function \(g\) at a set \(T\). Then, with the left sum over all restrictions on the \(n\) variables and the right sum over all \(U\subseteq [n]\),
When \(0\le p\le 1\) the weights \(w_p(\rho )\) form a probability distribution, so the left-hand side is the expectation of \(\widehat{f_\rho }(S)^2\) over a Bernoulli\((p)\) random restriction.
Let \(\rho \) be a restriction on \(n\) variables and let \(T \subseteq [n]\), and write \(s(\rho , T) \in \mathbb {R}\) for the sign product of the bits that \(\rho \) fixes on \(T\), that is, the product over \(i \in T\) of the \(\pm 1\)-encoding of \(\rho \)’s value at \(i\). Being a product of values in \(\{ -1, 1\} \), it satisfies
Fix \(n\), a real parameter \(p\), and two subsets \(U, S \subseteq [n]\). Let \(\rho \) be a Bernoulli(\(p\)) random restriction on \(n\) variables, meaning each restriction is drawn with weight \(p^{\left\lvert J\right\rvert }\bigl(\tfrac {1-p}{2}\bigr)^{\, n-\left\lvert J\right\rvert }\), where \(J\) denotes its set of free variables. Then the probability that the free variables lying inside \(U\) are exactly those of \(S\) is
120.3 Additional declarations
Given \(f : \{ 0,1\} ^n \to \mathbb {R}\) and a restriction \(\rho \), the restricted function \(f_\rho = \mathrm{restrictBF}\, f\, \rho \) is defined by
so free coordinates are read from the input \(x\) and fixed coordinates from \(\rho \). It is the real-valued analogue of \(\mathrm{restrictFn}\).
For a restriction \(\rho \) and a set \(T \subseteq [n]\),
the product of the \(\pm 1\)-encodings of the bits that \(\rho \) fixes on \(T\). On coordinates where \(\rho \) is free the default value \(\mathtt{false}\) is used; this junk value is harmless because the definition is only ever paired with indicators forcing \(T\) to consist of fixed coordinates.