Note.Basics of Boolean Functions [boolean/basics]

2026-08-20

Background [#]

Here are the basics of Boolean functions. The standard reference is O’Donnell, and one should generally start there. This will contain mostly the things I look up myself too often, which is not necessarily the best way for someone else to learn.

Boolean Functions [#]

The object of study here are Boolean functions.

Definition.Boolean Function [boolean/def/boolean-function]

2026-08-17

A Boolean function is a real-valued function on the Boolean cube,

𝑓 : {- 1, 1}^{𝑛} \to ℝ .

When the codomain is a single bit,

𝑓 : {- 1, 1}^{𝑛} \to {- 1, 1},

we call $𝑓$ a Boolean-valued function.

Classically the name “Boolean function” means the Boolean-valued kind, but the Fourier-analytic machinery works at the relaxed generality, so we take that as the default and specialize to Boolean-valued functions when the extra structure matters.

The two-element set can be any set of 2 things. Other natural choices are ${0, 1}$ , ${True, False}$ , or the two elements of the field $𝔽_{2}$ (which makes the domain $𝔽_{2}^{𝑛}$ ).

Every Boolean function has a canonical expansion in the parity basis, which gives rise to most of the tools we have.

Theorem.Fourier Expansion [boolean/thm/fourier-exp]

2026-08-26

Every Boolean function can be written uniquely as a multilinear polynomial in the functions

𝜒_{𝑆} (𝑥) = \prod_{𝑖 \in 𝑆} 𝑥_{𝑖}, 𝑆 \subseteq [𝑛] :

𝑓 (𝑥) = \sum_{𝑆 \subseteq [𝑛]} \hat{𝑓} (𝑆) 𝜒_{𝑆} (𝑥),

where $\hat{𝑓} (𝑆) \in ℝ$ is the Fourier coefficient of $𝑓$ on $𝑆$ .

The $𝜒_{𝑆}$ are called parity functions. Where $𝜒_{𝑆} (𝑥) = - 1$ exactly when an odd number of the bits ${(𝑥_{𝑖})}_{𝑖 \in 𝑆}$ are $- 1$ . Importantly, they form a basis of the $2^{𝑛}$ -dimensional vector space of functions $𝑓 : {\pm 1}^{𝑛} \to ℝ$ .

The Inner Product, Plancherel, and Parseval [#]

Definition.Expectation Inner Product [boolean/def/expec-ip]

2026-08-26

For $𝑓, 𝑔 : {\pm 1}^{𝑛} \to ℝ$ we define the Expectation Inner Product to be

{⟨ 𝑓, 𝑔 ⟩}_{𝐄} = \underset{𝑥}{𝐄} [𝑓 (𝑥) 𝑔 (𝑥)] = \frac{1}{2^{𝑛}} \sum_{𝑥 \in {\pm 1}^{𝑛}} 𝑓 (𝑥) 𝑔 (𝑥),

where $𝑥$ is drawn uniformly at random from the cube. We write ${‖ 𝑓 ‖}_{𝐄}^{2} = {⟨ 𝑓, 𝑓 ⟩}_{𝐄} = 𝐄 [{𝑓 (𝑥)}^{2}]$ .

We will generally use the expectation inner product by default, and so we will assume w/r/t Boolean functions $⟨ 𝑓, 𝑔 ⟩ = {⟨ 𝑓, 𝑔 ⟩}_{𝐄}$ unless otherwise noted.

We do this because the expectation inner product plays very nicely with the character functions. The whole subject rests on one fact: under this inner product the parities are orthonormal.

Lemma.Orthonormality of the characters [#]

For all $𝑆, 𝑇 \subseteq [𝑛]$ ,

⟨ 𝜒_{𝑆}, 𝜒_{𝑇} ⟩ = {\begin{cases} 1 & if 𝑆 = 𝑇 \\ 0 & otherwise \end{cases} .

Proof. [#]

Since $𝑥_{𝑖}^{2} = 1$ for every coordinate,

𝜒_{𝑆} (𝑥) 𝜒_{𝑇} (𝑥) = \prod_{𝑖 \in 𝑆 △ 𝑇} 𝑥_{𝑖} = 𝜒_{𝑆 △ 𝑇} (𝑥),

where $𝑆 △ 𝑇$ is the symmetric difference. So it suffices to compute $𝐄 [𝜒_{𝑈} (𝑥)]$ for $𝑈 = 𝑆 △ 𝑇$ .

If $𝑈 = \emptyset$ then $𝜒_{𝑈} \equiv 1$ , so the expectation is $1$ .

Otherwise, since the coordinates are independent and uniform on $\pm 1$ ,

𝐄 [𝜒_{𝑈} (𝑥)] = \prod_{𝑖 \in 𝑈} 𝐄 [𝑥_{𝑖}] = \prod_{𝑖 \in 𝑈} 0 = 0 .

Taking $𝑈 = 𝑆 △ 𝑇$ , which is empty exactly when $𝑆 = 𝑇$ , gives the claim.

Warning.The standard inner product isn't normalized [#]

Definition. [#]

The standard inner product on functions $𝑓, 𝑔 : {\pm 1}^{𝑛} \to ℝ$ is

{⟨ 𝑓, 𝑔 ⟩}_{std} = \sum_{𝑥 \in {\pm 1}^{𝑛}} 𝑓 (𝑥) 𝑔 (𝑥) .

This differs from the expectation inner product by exactly the constant $2^{𝑛}$ :

{⟨ 𝑓, 𝑔 ⟩}_{std} = 2^{𝑛} ⟨ 𝑓, 𝑔 ⟩ .

The characters are still orthogonal under it but they are not orthonormal: ${‖ 𝜒_{𝑆} ‖}_{std}^{2} = 2^{𝑛} \neq 1$ . Averaging instead of summing is exactly what fixes the norm.

Orthonormality identifies the Fourier coefficients as the coordinates of $𝑓$ in this basis, and yields the two workhorse identities of the theory.

Proposition.Coefficients are Projections [#]

For every $𝑓$ and every $𝑆 \subseteq [𝑛]$ ,

\hat{𝑓} (𝑆) = ⟨ 𝑓, 𝜒_{𝑆} ⟩ = \underset{𝑥}{𝐄} [𝑓 (𝑥) 𝜒_{𝑆} (𝑥)] .

Proof. [#]

Expand $𝑓 = \sum_{𝑇} \hat{𝑓} (𝑇) 𝜒_{𝑇}$ and use bilinearity with the previous lemma:

⟨ 𝑓, 𝜒_{𝑆} ⟩ = \sum_{𝑇} \hat{𝑓} (𝑇) ⟨ 𝜒_{𝑇}, 𝜒_{𝑆} ⟩ = \hat{𝑓} (𝑆) .

Fourier coefficients are just inner products against the characters, so Plancherel’s theorem is immediate from their orthonormality.

Theorem.Plancherel's Theorem [boolean/thm/plancherel]

2026-08-26

For all $𝑓, 𝑔 : {\pm 1}^{𝑛} \to ℝ$ ,

⟨ 𝑓, 𝑔 ⟩ = 𝐄 [𝑓 𝑔] = \sum_{𝑆 \subseteq [𝑛]} \hat{𝑓} (𝑆) \hat{𝑔} (𝑆) .

Note that taking $𝑔 = 𝑓$ recovers Parseval’s identity.

Proof. [#]

Expand both functions in the Fourier basis and apply orthonormality of the characters (see the expectation inner product):

⟨ 𝑓, 𝑔 ⟩ = ⟨ \sum_{𝑆} \hat{𝑓} (𝑆) 𝜒_{𝑆}, \sum_{𝑇} \hat{𝑔} (𝑇) 𝜒_{𝑇} ⟩ = \sum_{𝑆, 𝑇} \hat{𝑓} (𝑆) \hat{𝑔} (𝑇) ⟨ 𝜒_{𝑆}, 𝜒_{𝑇} ⟩ = \sum_{𝑆} \hat{𝑓} (𝑆) \hat{𝑔} (𝑆) .

Specializing to $𝑔 = 𝑓$ gives Parseval: the squared Fourier coefficients of a Boolean-valued function form a probability distribution.

Theorem.Parseval's Theorem [boolean/thm/parseval]

2026-08-26

For all $𝑓 : {\pm 1}^{𝑛} \to ℝ$ ,

{‖ 𝑓 ‖}^{2} = 𝐄 [{𝑓 (𝑥)}^{2}] = \sum_{𝑆 \subseteq [𝑛]} \hat{𝑓} {(𝑆)}^{2} .

If $𝑓$ is Boolean-valued then ${𝑓 (𝑥)}^{2} = 1$ everywhere, so $\sum_{𝑆} \hat{𝑓} {(𝑆)}^{2} = 1$ : the squared coefficients of a $\pm 1$ -valued function form a probability distribution over subsets $𝑆$ .

Proof. [#]

Taking $𝑔 = 𝑓$ in Plancherel gives

⟨ 𝑓, 𝑓 ⟩ = \sum_{𝑆 \subseteq [𝑛]} \hat{𝑓} {(𝑆)}^{2},

and $⟨ 𝑓, 𝑓 ⟩ = {‖ 𝑓 ‖}^{2}$ by definition.

“Probabilistic” Boolean Formulas [#]

We can relate the coefficients of the Fourier expansion to properties of the function. Thinking of $𝑓 (𝑥)$ as a real-valued random variable, two important definitions are the mean and variance.

Definition.Mean [boolean/def/mean]

2026-08-27

The mean of a function $𝑓 : {\pm 1}^{𝑛} \to ℝ$ is $𝐄 [𝑓]$ ; i.e.,

(\frac{1}{2^{𝑛}}) \sum_{𝑥 \in {\pm 1}^{𝑛}} 𝑓 (𝑥),

the average value of $𝑓$ .

In particular, when we have a Boolean-valued function $𝑓 : {\pm 1}^{𝑛} \to {\pm 1}$ , then

𝐄 [𝑓] = 𝐏𝐫 [𝑓 = 1] - 𝐏𝐫 [𝑓 = - 1] .

If $𝑓$ has a mean of $0$ , we call $𝑓$ unbiased or balanced.

Note. [#]

For $𝑓 : {\pm 1}^{𝑛} \to ℝ$ ,

𝐄 [𝑓] = \hat{𝑓} (\emptyset) .

This follows from the fact that $𝐄 [𝑓] = ⟨ 𝑓, 1 ⟩ = \hat{𝑓} (\emptyset)$ .

Definition.Variance [boolean/def/var]

2026-08-27

The variance of a function $𝑓 : {\pm 1}^{𝑛} \to ℝ$ is

𝐕𝐚𝐫 [𝑓] = 𝐄 [{(𝑓 - 𝐄 [𝑓])}^{2}] = 𝐄 [𝑓^{2}] - {𝐄 [𝑓]}^{2} .

Note. [#]

For $𝑓 : {\pm 1}^{𝑛} \to ℝ$ ,

𝐕𝐚𝐫 [𝑓] = \sum_{𝑆 \neq \emptyset} \hat{𝑓} {(𝑆)}^{2} .

By Parseval, $𝐄 [𝑓^{2}] = \sum_{𝑆} \hat{𝑓} {(𝑆)}^{2}$ , and by the Fourier coefficient of the mean, ${𝐄 [𝑓]}^{2} = \hat{𝑓} {(\emptyset)}^{2}$ . Subtracting leaves the sum over nonempty $𝑆$ .

To match variance, we may also define covariance.

Definition.Covariance [boolean/def/covar]

2026-08-27

The covariance of $𝑓, 𝑔 : {\pm 1}^{𝑛} \to ℝ$ is

\begin{aligned} 𝐂𝐨𝐯 [𝑓, 𝑔] & = ⟨ 𝑓 - 𝐄 [𝑓], 𝑔 - 𝐄 [𝑔] ⟩ \\ = 𝐄 [𝑓 𝑔] - 𝐄 [𝑓] 𝐄 [𝑔] . \end{aligned}

Note. [#]

For $𝑓, 𝑔 : {\pm 1}^{𝑛} \to ℝ$ ,

𝐂𝐨𝐯 [𝑓, 𝑔] = \sum_{𝑆 \neq \emptyset} \hat{𝑓} (𝑆) \hat{𝑔} (𝑆) .

By Plancherel, $𝐄 [𝑓 𝑔] = \sum_{𝑆} \hat{𝑓} (𝑆) \hat{𝑔} (𝑆)$ , and by the Fourier coefficient of the mean, $𝐄 [𝑓] 𝐄 [𝑔] = \hat{𝑓} (\emptyset) \hat{𝑔} (\emptyset)$ . Subtracting leaves the sum over nonempty $𝑆$ .

Fourier Weight Distribution [#]

Something that comes up (surprisingly?) often is considering distributions on the subsets of $[𝑛]$ . For this one we consider the weight of a function.

Definition.Fourier weight [boolean/def/weight]

2026-08-27

The (Fourier) weight of a Boolean function $𝑓$ on the set $𝑆 \subseteq [𝑛]$ is the squared Fourier coefficient, $\hat{𝑓} {(𝑆)}^{2}$ .

Using the weight of a function, we may consider the following distribution.

Definition.Spectral Sample [boolean/def/spec-sample]

2026-08-27

For $𝑓 : {\pm 1}^{𝑛} \to {\pm 1}$ , the spectral sample for $𝑓$ , notated ${𝒮︀}_{𝑓}$ , is the probability distribution on subsets of $[𝑛]$ in which $𝐏𝐫 [𝑆] = \hat{𝑓} {(𝑆)}^{2}$ .

We write $𝑺 \sim {𝒮︀}_{𝑓}$ for a set drawn from this distribution.

We do sometimes want to consider the weight on (or up to) a certain degree of the function.

Definition.Weight at Degree [boolean/def/weight-at-deg]

2026-08-27

For $𝑓 : {\pm 1}^{𝑛} \to ℝ$ and $0 \leq 𝑘 \leq 𝑛$ , the (Fourier) weight of $𝑓$ at degree $𝑘$ is

𝐖^{𝑘} [𝑓] = \sum_{\begin{matrix} 𝑆 \subseteq [𝑛] \\ | 𝑆 | = 𝑘 \end{matrix}} \hat{𝑓} {(𝑆)}^{2} .

By Parseval's Theorem, we have $𝐖^{𝑘} [𝑓] = {‖ 𝑓^{= 𝑘} ‖}_{2}^{2}$ , where

𝑓^{= 𝑘} = \sum_{| 𝑆 | = 𝑘} \hat{𝑓} (𝑆) 𝜒_{𝑆}

is the degree $𝑘$ part of $𝑓$ .

If $𝑓 : {\pm 1}^{𝑛} \to {\pm 1}$ is Boolean-valued, then equivalently we have

𝐖^{𝑘 [𝑓]} = \underset{𝑺 \sim {𝒮︀}_{𝑓}}{𝐏𝐫} [| 𝑺 | = 𝑘] .

Analogously, the weight below degree $𝑘$ and weight at or above degree $𝑘$ are

𝐖^{< 𝑘} [𝑓] = \sum_{| 𝑆 | < 𝑘} \hat{𝑓} {(𝑆)}^{2} and 𝐖^{\geq 𝑘} [𝑓] = \sum_{| 𝑆 | \geq 𝑘} \hat{𝑓} {(𝑆)}^{2} .

As before, these are ${‖ 𝑓^{< 𝑘} ‖}^{2}$ and ${‖ 𝑓^{\geq 𝑘} ‖}^{2}$ , where $𝑓^{< 𝑘} = \sum_{| 𝑆 | < 𝑘} \hat{𝑓} (𝑆) 𝜒_{𝑆}$ is the low-degree part of $𝑓$ (below $𝑘$ ) and $𝑓^{\geq 𝑘} = \sum_{| 𝑆 | \geq 𝑘} \hat{𝑓} (𝑆) 𝜒_{𝑆} = 𝑓 - 𝑓^{< 𝑘}$ is its high-degree part (from $𝑘$ on).

In particular $𝐖^{< 𝑘} [𝑓] + 𝐖^{\geq 𝑘} [𝑓] = {‖ 𝑓 ‖}^{2}$ , which is $1$ when $𝑓$ is Boolean-valued.

Influences [#]

A general question we then may ask is how much the $𝑖$ th bit affects the outcome of the function, which we call the influence of coordinate $𝑖$ . A natural way to tackle this is to see how much the function changes (on average) when we toggle a bit. This leads us to a discrete version of the derivative.

Definition.(Discrete) Derivative [boolean/def/derivative]

2026-09-08

For $𝑓 : {\pm 1}^{𝑛} \to ℝ$ and a coordinate $𝑖 \in [𝑛]$ , the (discrete) derivative of $𝑓$ in direction $𝑖$ is

𝐷_{𝑖} 𝑓 (𝑥) = \frac{𝑓 (𝑥^{𝑖 \to 1}) - 𝑓 (𝑥^{𝑖 \to - 1})}{2},

where $𝑥^{𝑖 \to 𝑏}$ is $𝑥$ with its $𝑖$ th coordinate set to $𝑏$ .

Proposition.Fourier Formula of the Derivative [#]

For $𝑓 : {\pm 1}^{𝑛} \to ℝ$ with expansion $𝑓 (𝑥) = \sum_{𝑆 \subseteq [𝑛]} \hat{𝑓} (𝑆) 𝜒_{𝑆} (𝑥)$ , the $𝑖$ th derivative of $𝑓$ is given by

𝐷_{𝑖} 𝑓 (𝑥) = \sum_{\begin{matrix} 𝑆 \subseteq [𝑛] \\ 𝑆 ∋ 𝑖 \end{matrix}} \hat{𝑓} (𝑆) 𝜒_{𝑆 ∖ {𝑖}} (𝑥) .

Now we can define the influence of a coordinate.

Definition.Influence [boolean/def/influence]

2026-09-03

For a Boolean-valued function $𝑓 : {\pm 1}^{𝑛} \to {- 1, 1}$ , the influence of coordinate $𝑖$ on $𝑓$ is the probability that flipping the $𝑖$ th bit changes the output of $𝑓$ ;

{𝐈𝐧𝐟}_{𝑖} [𝑓] = \underset{𝑥 \sim {\pm 1}^{𝑛}}{𝐏𝐫} [𝑓 (𝑥) \neq 𝑓 (𝑥^{\oplus 𝑖})],

where

𝑥^{\oplus 𝑖} = (𝑥_{1}, 𝑥_{2}, \dots, 𝑥_{𝑖 - 1}, - 𝒙_{𝒊}, 𝑥_{𝑖 + 1}, \dots, 𝑥_{𝑛}) .

When flipping the bit changes the output, $𝑓 (𝑥) \neq 𝑓 (𝑥^{\oplus 𝑖})$ , we say coordinate $𝑖$ is pivotal for $𝑥$ .

Using the (discrete) derivative operator, we may generalize the definition of influence to any Boolean function. For $𝑓 : {\pm 1}^{𝑛} \to ℝ$ , the influence of coordinate $𝑖$ on $𝑓$ is defined to be

{𝐈𝐧𝐟}_{𝑖} [𝑓] = \underset{𝑥 \sim {\pm 1}^{𝑛}}{𝐄} [𝐷_{𝑖} {𝑓 (𝑥)}^{2}] = {‖ 𝐷_{𝑖} 𝑓 ‖}_{2}^{2} .

Note. [#]

Note that for $𝑓 : {\pm 1}^{𝑛} \to {- 1, 1}$ ,

𝐷_{𝑖} 𝑓 (𝑥) = {\begin{cases} 0 & coordinate 𝑖 is not pivotal for 𝑥 \\ \pm 1 & coordinate 𝑖 is pivotal for 𝑥 \end{cases} .

This means $𝐷_{𝑖} {𝑓 (𝑥)}^{2}$ is a 0–1 indicator for whether $𝑖$ is pivotal for a given $𝑥$ , and so

{𝐈𝐧𝐟}_{𝑖} [𝑓] = \underset{𝑥 \sim {\pm 1}^{𝑛}}{𝐏𝐫} [𝑓 (𝑥) \neq 𝑓 (𝑥^{\oplus 𝑖})] = \underset{𝑥 \sim {\pm 1}^{𝑛}}{𝐄} 𝐷_{𝑖} {𝑓 (𝑥)}^{2},

the right-hand side of which we simply take to be the definition in the real-valued case.

Summing influence over every coordinate gives a single number measuring how sensitive $𝑓$ is overall.

Definition.Total Influence [boolean/def/total-inf]

2026-09-08

The total influence of a function $𝑓 : {\pm 1}^{𝑛} \to ℝ$ is the sum of its influences over every coordinate,

𝐈 [𝑓] = \sum_{𝑖 = 1}^{𝑛} {𝐈𝐧𝐟}_{𝑖} [𝑓] .

As is often the case, when we restrict to Boolean-valued functions $𝑓 : {\pm 1}^{𝑛} \to {\pm 1}$ we get a few extra properties. First though, we define the sensitivity of a function $𝑓$ at a point $𝑥$ .

Definition.Sensitivity [boolean/def/sensitivity]

The sensitivity of $𝑓$ at $𝑥$ is defined as the number of pivotal coordinates of a given input $𝑥$ for function $𝑓$ ; i.e.,

{sens}_{𝑓} (𝑥) = # {𝑖 \in [𝑛] : 𝑓 (𝑥) \neq 𝑓 (𝑥^{\oplus 𝑖})}

This allows us to state the fact that, for Boolean-valued functions, total influence is the average sensitivity of $𝑓$ .

Proposition.Influence is Average Sensitivity [#]

For $𝑓 : {\pm 1}^{𝑛} \to {\pm 1}$ we have

𝐈 [𝑓] = \underset{𝑥}{𝐄} [{sens}_{𝑓} (𝑥)] .

Restrictions [#]

A common (and surprisingly useful) thing to do to a Boolean function is to consider restrictions of the function to subcubes of the domain.

Definition.Restriction [boolean/def/restriction]

2026-09-22

Let $𝑓 : {\pm 1}^{𝑛} \to ℝ$ and take $(𝐽, \overline{𝐽})$ to be a partition of $[𝑛]$ . Take $𝑧 \in {\pm 1}^{\overline{𝐽}}$ . Then the restriction of $𝑓$ to $𝐽$ using $𝑧$ is

\begin{matrix} 𝑓_{𝐽 | 𝑧} : {\pm 1}^{𝐽} \to ℝ \\ 𝑦 \mapsto 𝑓 (𝑦, 𝑧), \end{matrix}

the subfunction of $𝑓$ given by fixing the coordinates in $\overline{𝐽}$ to $𝑧$ .

When the partition $(𝐽, \overline{𝐽})$ is clear, we will often write the restriction as $𝑓_{| 𝑧}$ .

Warning. [#]

Even though we write

𝑓_{𝐽 | 𝑧} (𝑦) = 𝑓 (𝑦, 𝑧),

remember that we (generally) are not working with the literal concatenation of $𝑦$ and $𝑧$ .

For a given $𝑓_{𝐽 | 𝑧} : {\pm 1}^{𝐽} \to ℝ$ has Fourier coefficients indexed by $𝑇 \subseteq 𝐽$ now, and, as always, we want to know about the Fourier coefficients.

Proposition.Fourier Expansion of the Restriction [boolean/thm/restriction-fourier]

2026-09-24

Let $𝑓 : {\pm 1}^{𝑛} \to ℝ$ , $(𝐽, \overline{𝐽})$ be a partition of $[𝑛]$ , and $𝑧 \in {\pm 1}^{\overline{𝐽}}$ . Then for the restriction function $𝑓_{𝐽 | 𝑧} : {\pm 1}^{𝐽} \to ℝ$ the Fourier coefficient associated to $𝑆 \subseteq 𝐽$ is given by

\hat{𝑓_{𝐽 | 𝑧}} (𝑆) = \sum_{𝑇 \subseteq \overline{𝐽}} \hat{𝑓} (𝑆 \cup 𝑇) 𝜒_{𝑇} (𝑧) .

This gives us that the Fourier expansion of the restriction is

𝑓_{𝐽 | 𝑧} (𝑦) = \sum_{𝑆 \subseteq 𝐽} (\sum_{𝑇 \subseteq \overline{𝐽}} \hat{𝑓} (𝑆 \cup 𝑇) 𝜒_{𝑇} (𝑧)) 𝜒_{𝑆} (𝑦) .

Proof. [#]

Split each index set $𝑈 \subseteq [𝑛]$ in the Fourier expansion of $𝑓$ as $𝑈 = 𝑆 \cup 𝑇$ with $𝑆 = 𝑈 \cap 𝐽$ and $𝑇 = 𝑈 \cap \overline{𝐽}$ . Since $𝑆$ and $𝑇$ are disjoint, the character factors across the partition:

𝜒_{𝑆 \cup 𝑇} (𝑦, 𝑧) = \prod_{𝑖 \in 𝑆} 𝑦_{𝑖} \prod_{𝑖 \in 𝑇} 𝑧_{𝑖} = 𝜒_{𝑆} (𝑦) 𝜒_{𝑇} (𝑧) .

Hence,

𝑓_{𝐽 | 𝑧} (𝑦) = 𝑓 (𝑦, 𝑧) = \sum_{𝑆 \subseteq 𝐽} \sum_{𝑇 \subseteq \overline{𝐽}} \hat{𝑓} (𝑆 \cup 𝑇) 𝜒_{𝑆} (𝑦) 𝜒_{𝑇} (𝑧),

and grouping by $𝑆$ gives the expansion above. Reading off the coefficient of $𝜒_{𝑆} (𝑦)$ is the claim, by uniqueness of the Fourier expansion.

It is worth noting that since the character of $𝑧$ occurs, we may also view this as a function of $𝑧$ , the restriction’s dependence on the fixed coordinates. This leads to considering such a function more directly.

Note.As a function of 𝑧 [#]

O’Donnell defines in §3.3, with things as above, a function

𝐹_{𝑆 | \overline{𝐽}} 𝑓 (𝑧) = \hat{𝑓_{𝐽 | 𝑧}} (𝑆),

giving us a function $\hat{𝑓_{𝐽 | ∙}} (𝑆)$ in terms of $𝑧 \in {\pm 1}^{\overline{𝐽}}$ . In particular it itself is a Boolean function $𝐹_{𝑆 | \overline{𝐽}} 𝑓 : {\pm 1}^{\overline{𝐽}} \to ℝ$ , and the proposition above is precisely its Fourier expansion, so we can read off its coefficients: for $𝑇 \subseteq \overline{𝐽}$ ,

\hat{𝐹_{𝑆 | \overline{𝐽}} 𝑓} (𝑇) = \hat{𝑓} (𝑆 \cup 𝑇) .

This helps us when we want to know what happens as $𝑧$ is what varies, as in the following corollary.

Corollary.Expectation of restrictions w/r/t 𝑧 [boolean/thm/restriction-exp]

Let $𝑓 : {\pm 1}^{𝑛} \to ℝ$ , $(𝐽, \overline{𝐽})$ be a partition of $[𝑛]$ , and fix $𝑆 \subseteq 𝐽$ . Then if we choose $𝑧 \sim {\pm 1}^{\overline{𝐽}}$ uniformly at random, we have

\begin{matrix} \underset{𝑧}{𝐄} [\hat{𝑓_{𝐽 | 𝑧}} (𝑆)] = \hat{𝑓} (𝑆) \\ \underset{𝑧}{𝐄} [\hat{𝑓_{𝐽 | 𝑧}} {(𝑆)}^{2}] = \sum_{𝑇 \subseteq \overline{𝐽}} \hat{𝑓} {(𝑆 \cup 𝑇)}^{2} . \end{matrix}

Proof. [#]

Both are statements about the Boolean function

𝐹_{𝑆 | \overline{𝐽}} 𝑓

{\pm 1}^{\overline{𝐽}}

, whose coefficients are

\hat{𝑓} (𝑆 \cup 𝑇)

by the note above. Its mean is its empty coefficient,

\hat{𝑓} (𝑆 \cup \emptyset) = \hat{𝑓} (𝑆)

, and its second moment is Parseval applied to it.