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 function

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

Though we tend to relax the codomain and simply consider functions from the Boolean cube

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

(and call the first type Boolean-valued functions).

We can make this work with 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 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 Boolean cube. For this one we consider the weight of 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{𝑺 \in {𝒮︀}_{𝑓}}{𝐏𝐫} [| 𝑆 | = 𝑘] .

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, 𝑥_{𝑛}) .

Using the (discrete) derivative operator, we may generalize the definition of influence to general real-valued Boolean functions. 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 vector for if $𝑖$ is influential 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 our codomain to 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}_{𝑓} (𝑥)] .