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.