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.