125 Boolean Analysis — Restriction Fourier

125.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.

125.2 Declarations

Definition 125.1 Restriction commutes with the \(\pm 1\)-encoding

✓

The restriction \(\mathrm{restrictBF}\) of a real-valued Boolean function reads free coordinates from the input and fixed coordinates from the restriction \(\rho \), i.e. \((\mathrm{restrictBF}\, f\, \rho )(x) = f(\rho .\mathrm{extend}\, x)\). This statement says that for a Boolean-valued \(f : \{ 0,1\} ^n \to \{ 0,1\} \), restricting its \(\pm 1\)-encoding agrees with encoding the restricted function: \(\mathrm{restrictBF}\, (\mathrm{boolToSign}\circ f)\, \rho = \mathrm{boolToSign}\circ (\mathrm{restrictFn}\, f\, \rho )\).

Definition 125.2 Membership in the free variables

✓

For a restriction \(\rho \) and a coordinate \(i\), we have \(i \in \rho .\mathrm{freeVars}\) if and only if \(\rho \, i = \mathtt{none}\), i.e. exactly when \(\rho \) leaves the coordinate \(i\) unfixed. The companion definition \(\mathrm{signProd}\, \rho \, T = \prod _{i \in T} \mathrm{boolToSign}((\rho \, i).\mathrm{getD}\ \mathtt{false})\) collects the \(\pm 1\)-encodings of the bits \(\rho \) fixes on a set \(T\).

Lemma 125.3 Character through a restriction splits

✓

For a set \(U \subseteq [n]\), a restriction \(\rho \) with free set \(J = \rho .\mathrm{freeVars}\), and an input \(x\),

\[ \chi _U(\rho .\mathrm{extend}\, x) \; =\; \chi _{U \cap J}(x)\cdot \mathrm{signProd}\, \rho \, (U \setminus J), \]

so the character splits into a character in the free coordinates times a constant sign coming from the fixed coordinates.

Theorem 125.4 Closed form for restricted Fourier coefficients

✓

For \(f : \{ 0,1\} ^n \to \mathbb {R}\), a restriction \(\rho \) with free set \(J = \rho .\mathrm{freeVars}\), and \(S \subseteq [n]\),

\[ \widehat{f_\rho }(S) \; =\; \sum _{U \subseteq [n]} \mathbf{1}[U \cap J = S]\cdot \widehat{f}(U)\cdot \mathrm{signProd}\, \rho \, (U \setminus J), \]

where \(f_\rho = \mathrm{restrictBF}\, f\, \rho \). This is the analogue of O’Donnell Corollary 3.22.

Lemma 125.5 Sums over restrictions of per-coordinate products factor

✓

For any family \(h : [n] \to \mathrm{Option}\ \mathrm{Bool} \to \mathbb {R}\),

\[ \sum _{\rho } \prod _{i} h\, i\, (\rho \, i) \; =\; \prod _{i} \sum _{v} h\, i\, v, \]

the sum ranging over all restrictions \(\rho \) on \(n\) variables and \(v\) over the three possible per-coordinate values.

Lemma 125.6 Bernoulli-weighted products factor

✓

For \(p \in \mathbb {R}\) and any family \(h : [n] \to \mathrm{Option}\ \mathrm{Bool} \to \mathbb {R}\),

\[ \sum _{\rho } \mathrm{bernoulliRestrWeight}\, p\, \rho \cdot \prod _{i} h\, i\, (\rho \, i) \; =\; \prod _{i} \sum _{v} \mathrm{varWeight}\, p\, v \cdot h\, i\, v, \]

so the Bernoulli weight is absorbed coordinatewise into the per-variable weight \(\mathrm{varWeight}\).

Definition 125.7 Per-coordinate local factor

✓

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\).

Lemma 125.8 Indicator times sign factors into local factors

✓

If \(S \subseteq U\) then for every restriction \(\rho \) with free set \(J\),

\[ \mathbf{1}[U \cap J = S]\cdot \mathrm{signProd}\, \rho \, (U \setminus J) \; =\; \prod _{i} \mathrm{localFactor}\, U\, S\, i\, (\rho \, i), \]

where the left-hand side is understood as \(0\) when the indicator fails.

Lemma 125.9 Average of one local factor

✓

For \(p \in \mathbb {R}\), sets \(U, S\) and a coordinate \(i\),

\[ \sum _{v} \mathrm{varWeight}\, p\, v \cdot \mathrm{localFactor}\, U\, S\, i\, v \; =\; \begin{cases} p & i \in S,\\ 0 & i \in U \setminus S,\\ 1 & \text{otherwise.}\end{cases} \]

Lemma 125.10 Average of a product of two local factors

✓

For \(p \in \mathbb {R}\), sets \(U, V, S\) and a coordinate \(i\),

\[ \sum _{v} \mathrm{varWeight}\, p\, v \cdot \bigl(\mathrm{localFactor}\, U\, S\, i\, v\cdot \mathrm{localFactor}\, V\, S\, i\, v\bigr) = \begin{cases} p & i \in S,\\ 1-p & i \notin S,\ i \in U \text{ and } i \in V,\\ 0 & i \notin S,\ i \in U \text{ or } i \in V,\\ 1 & \text{otherwise,}\end{cases} \]

which is the per-coordinate average needed for the squared coefficient.

Lemma 125.11 Product of a three-case indicator weight

✓

For \(p \in \mathbb {R}\) and sets \(S, U \subseteq [n]\),

\[ \prod _{i} \bigl(p \text{ if } i \in S,\ (1-p) \text{ if } i \in U \setminus S,\ 1 \text{ otherwise}\bigr) \; =\; p^{\left\lvert S\right\rvert }\, (1-p)^{\left\lvert U \setminus S\right\rvert }. \]

Theorem 125.12 Proposition 4.17, first identity

✓

Under a Bernoulli(\(p\))-random restriction \(\rho \), the expected Fourier coefficient of the restricted function at \(S\) is

\[ \mathbb {E}_\rho \bigl[\widehat{f_\rho }(S)\bigr] \; =\; p^{\left\lvert S\right\rvert }\cdot \widehat{f}(S), \]

the expectation being the \(\mathrm{bernoulliRestrWeight}\, p\)-weighted sum over all restrictions.

Theorem 125.13 Proposition 4.17, second identity

✓

Under a Bernoulli(\(p\))-random restriction \(\rho \), the expected squared Fourier coefficient at \(S\) is

\[ \mathbb {E}_\rho \bigl[\widehat{f_\rho }(S)^2\bigr] \; =\; \sum _{U \supseteq S} p^{\left\lvert S\right\rvert }\, (1-p)^{\left\lvert U \setminus S\right\rvert }\cdot \widehat{f}(U)^2, \]

where the sum runs over all \(U \subseteq [n]\) and the terms with \(S \not\subseteq U\) vanish.

Lemma 125.14 The squared sign product is one

✓

For every restriction \(\rho \) and every set \(T \subseteq [n]\), \((\mathrm{signProd}\, \rho \, T)^2 = 1\).

Theorem 125.15 Proposition 4.17, probability form

✓

For a Bernoulli(\(p\))-random restriction \(\rho \) with free set \(J = \rho .\mathrm{freeVars}\) and sets \(U, S \subseteq [n]\),

\[ \Pr _\rho \bigl[U \cap J = S\bigr] \; =\; \begin{cases} p^{\left\lvert S\right\rvert }\, (1-p)^{\left\lvert U \setminus S\right\rvert } & S \subseteq U,\\ 0 & \text{otherwise.}\end{cases} \]

Combined with the second identity this yields O’Donnell’s form \(\mathbb {E}_\rho [\widehat{f_\rho }(S)^2] = \sum _U \Pr [U \cap J = S]\cdot \widehat{f}(U)^2\).

125.3 Additional declarations

Definition 125.16 Restriction of a real-valued Boolean function

✓

Given \(f : \{ 0,1\} ^n \to \mathbb {R}\) and a restriction \(\rho \), the restricted function \(f_\rho = \mathrm{restrictBF}\, f\, \rho \) is defined by

\[ (\mathrm{restrictBF}\, f\, \rho )(x) \; =\; f(\rho .\mathrm{extend}\, x), \]

so free coordinates are read from the input \(x\) and fixed coordinates from \(\rho \). It is the real-valued analogue of \(\mathrm{restrictFn}\).

Definition 125.17 Sign product of the fixed bits

✓

For a restriction \(\rho \) and a set \(T \subseteq [n]\),

\[ \mathrm{signProd}\, \rho \, T \; =\; \prod _{i \in T} \mathrm{boolToSign}\bigl((\rho \, i).\mathrm{getD}\ \mathtt{false}\bigr) \; \in \; \mathbb {R}, \]

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.