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.