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.