§3.3: Restrictions

A common operation on boolean functions $f : \{-1,1\}^n \to {\mathbb R}$ is restriction to subcubes. Suppose $[n]$ is partitioned into two sets, $J$ and $\overline{J} = [n] \setminus J$. If the inputs bits in $\overline{J}$ are fixed to constants, the result is a function $\{-1,1\}^J \to {\mathbb R}$. For example, if we take the function $\mathrm{Maj}_5 : \{-1,1\}^5 \to \{-1,1\}$ and restrict the $4$th and $5$th coordinates to be $1$ and $-1$ respectively, we obtain the function $\mathrm{Maj}_3 : \{-1,1\}^3 \to \{-1,1\}$. If we further restrict the $3$rd coordinate to be $-1$, we obtain the two-bit function which is $1$ if and only if both input bits are $1$.

We introduce following notation:

Definition 18 Let $f : \{-1,1\}^n \to {\mathbb R}$ and let $(J, \overline{J})$ be a partition of $[n]$. Let $z \in \{-1,1\}^{\overline{J}}$. Then we write $f_{J \mid z} : \{-1,1\}^J \to {\mathbb R}$ (pronounced “the restriction of $f$ to $J$ using $z$”) for the subfunction of $f$ given by fixing the coordinates in $\overline{J}$ to the bit values $z$. When the partition $(J, \overline{J})$ is understood we may write simply $f_{\mid z}$. If $y \in \{-1,1\}^J$ and $z \in \{-1,1\}^{\overline{J}}$ we will sometimes write $(y,z)$ for the composite string in $\{-1,1\}^n$, even though $y$ and $z$ are not literally concatenated; with this notation, $f_{J \mid z}(y) = f(y,z)$.

Let’s examine how restrictions affect the Fourier transform by considering an example.

Example 19 Let $f : \{-1,1\}^4 \to \{-1,1\}$ be the function defined by \begin{equation} \label{eqn:restr-eg1} f(x) = 1 \quad\!\! \Leftrightarrow \quad\!\! x_3 = x_4 = -1 \text{ or } x_1 \geq x_2 \geq x_3 \geq x_4 \text{ or } x_1 \leq x_2 \leq x_3 \leq x_4. \end{equation} You can check that $f$ has the Fourier expansion \begin{align} f(x) = &+\tfrac18-\tfrac18x_1+\tfrac18x_2-\tfrac18x_3-\tfrac18x_4 \nonumber\\ &+\tfrac38x_1x_2+\tfrac18x_1x_3-\tfrac38x_1x_4+\tfrac38x_2x_3-\tfrac18x_2x_4+\tfrac58x_3x_4 \label{eqn:restr-eg2} \\ &+\tfrac18x_1x_2x_3+\tfrac18x_1x_2x_4-\tfrac18x_1x_3x_4+\tfrac18x_2x_3x_4-\tfrac18x_1x_2x_3x_4. \nonumber \end{align} Consider the restriction $x_3 = 1$, $x_4 = -1$, and let $f’ = f_{\{1,2\} \mid (1,-1)}$ be the restricted function of $x_1$ and $x_2$. From the original definition \eqref{eqn:restr-eg1} of $f$ we see that $f’(x_1,x_2)$ is $1$ if and only if $x_1 = x_2 = 1$. This is the ${\textstyle \min_2}$ function of $x_1$ and $x_2$, which we know has Fourier expansion \begin{equation} \label{eqn:restr-eg3} f’(x_1,x_2) = {\textstyle \min_2}(x_1,x_2) = -\tfrac12 + \tfrac12 x_1 + \tfrac12 x_2 + \tfrac12x_1x_2. \end{equation} We can of course obtain this expansion simply by plugging $x_3 = 1, x_4 = -1$ into \eqref{eqn:restr-eg2}. Now suppose we only wanted to know the coefficient on $x_1$ in the Fourier expansion of $f’$. We can find it as follows: consider all monomials in \eqref{eqn:restr-eg2} which contain $x_1$ and possibly also $x_3$, $x_4$; substitute $x_3 = 1$, $x_4 = -1$ into the associated terms; and, sum the results. The relevant terms in \eqref{eqn:restr-eg2} are $-\tfrac18x_1$, $+\tfrac18x_1x_3$, $-\tfrac38x_1x_4$, $-\tfrac18x_1x_3x_4$, and substituting in $x_3 = 1, x_4 = -1$ gives us $-\tfrac18 +\tfrac18 +\tfrac38 +\tfrac18 = \tfrac12$, as expected from \eqref{eqn:restr-eg3}.

Now we work out these ideas more generally. In the setting of Definition 18 the restricted function $f_{J \mid z}$ has $\{-1,1\}^J$ as its domain. Thus its Fourier coefficients are indexed by subsets of $J$. Let’s introduce notation for the Fourier coefficients of a restricted function:

Definition 20 Let $f : \{-1,1\}^n \to {\mathbb R}$ and let $(J, \overline{J})$ be a partition of $[n]$. Let $S \subseteq J$. Then we write function $\widehat{f_{J \mid \bullet}}(S)$; i.e., \[ \mathrm{F}_{S \mid \overline{J}} f(z) = \widehat{f_{J \mid z}}(S). \] When the partition $(J, \overline{J})$ is understood we may write simply $\mathrm{F}_{S \mid } f$.

(In Example 19 we considered $\overline{J} = \{3,4\}$, $S = \{1\}$, and $z = (1,-1)$.)

Notation for a typical restriction scenario. Note that J and its complement need not be literally contiguous.

In general, for a fixed partition $(J, \overline{J})$ of $[n]$ and a fixed $S \subseteq J$, we may wish to know what $\widehat{f_{J \mid z}}(S)$ is as a function of $z \in \{-1,1\}^{\overline{J}}$. This is precisely asking for the Fourier transform of $\mathrm{F}_{S \mid \overline{J}} f$. Since the function $\mathrm{F}_{S \mid \overline{J}} f$ has domain $\{-1,1\}^{\overline{J}}$, its Fourier transform has coefficients indexed by subsets of $\overline{J}$. The formula for this Fourier transform generalizes the computation we used at the end of Example 19:

Proposition 21 In the setting of Definition 20 we have the Fourier expansion \[ \mathrm{F}_{S \mid \overline{J}} f(z) = \sum_{T \subseteq \overline{J}} \widehat{f}(S \cup T) z^T; \] i.e., \[ \widehat{\mathrm{F}_{S \mid \overline{J}} f}(T) = \widehat{f}(S \cup T). \]

Proof: (The $S = \emptyset$ case here is Exercise 1.16.) Every $U \subseteq [n]$ indexing $f$’s Fourier coefficients can be written as a disjoint union $U = S \cup T$, where $S \subseteq J$ and $T \subseteq \overline{J}$. We can also decompose any $x \in \{-1,1\}^n$ into two substrings $y \in \{-1,1\}^J$ and $z \in \{-1,1\}^{\overline{J}}$. We have $x^U = y^Sz^T$ and so \[ f(x) = \sum_{U \subseteq [n]} \widehat{f}(U)\,x^U = \sum_{\substack{S \subseteq J \\ T \subseteq \overline{J}}} \widehat{f}(S \cup T)\,y^Sz^T = \sum_{S \subseteq J\vphantom{\overline{J}}} \Bigl( \sum_{T \subseteq \overline{J}} \widehat{f}(S \cup T)\,z^T\Bigr) y^S. \] Thus when $z$ is fixed, the resulting function of $y$ indeed has $\sum_{T \subseteq \overline{J}} \widehat{f}(S \cup T)\,z^T$ as its Fourier coefficient on the monomial $y^S$. $\Box$

Corollary 22 Let $f : \{-1,1\}^n \to {\mathbb R}$, let $(J, \overline{J})$ be a partition of $[n]$, and fix $S \subseteq J$. Suppose $\boldsymbol{z} \sim \{-1,1\}^{\overline{J}}$ is chosen uniformly at random. Then \begin{align*} \mathop{\bf E}_{\boldsymbol{z}}[\widehat{f_{J \mid \boldsymbol{z}}}(S)] &= \widehat{f}(S),\\ \mathop{\bf E}_{\boldsymbol{z}}[\widehat{f_{J \mid \boldsymbol{z}}}(S)^2] &= \sum_{T \subseteq \overline{J}} \widehat{f}(S \cup T)^2. \end{align*}

Proof: The first statement is immediate from Proposition 21, taking $T = \emptyset$ and unravelling the definition. As for the second statement, \begin{align*} \mathop{\bf E}_{\boldsymbol{z}}[\widehat{f_{J \mid \boldsymbol{z}}}(S)^2] &= \mathop{\bf E}_{\boldsymbol{z}}[\mathrm{F}_{S \mid \overline{J}} f(\boldsymbol{z})^2] \tag{by definition} \\ &= \sum_{T \subseteq \overline{J}} \widehat{\mathrm{F}_{S \mid \overline{J}} f}(T)^2 \tag{Parseval}\\ &= \sum_{T \subseteq \overline{J}} \widehat{f}(S \cup T)^2 \tag*{(Proposition 21) $\Box$} \end{align*}

We move on to discussing a more general kind of restriction; namely, restricting a function $f : {\mathbb F}_2^n \to {\mathbb R}$ to an affine subspace $H + z$. This generalizes restriction to subcubes as we’ve seen so far, by considering $H = \mathrm{span}\{e_i : i \in J\}$ for a given subset $J \subseteq [n]$. For restrictions to a subspace $H \leq {\mathbb F}_2^n$ we have a natural definition:

Definition 23 If $f : {\mathbb F}_2^n \to {\mathbb R}$ and $H \leq {\mathbb F}_2^n$ is a subspace, we write $f_H : H \to {\mathbb R}$ for the restriction of $f$ to $H$.

For restrictions to affine subspaces, we run into difficulties if we try to extend our notation for restrictions to subcubes. Unlike in the subcube case of $H = \mathrm{span}\{e_i : i \in J\}$, we don’t in general have a canonical isomorphism between $H$ and a coset $H+z$. Thus it’s not natural to introduce notation such as $f_{H \mid z} : H \to {\mathbb R}$ for the function $h \mapsto f(h+z)$, because such a definition depends on the choice of representative for $H+z$. As an example consider $H = \{(0,0), (1,1)\} \leq {\mathbb F}_2^2$, a $1$-dimensional subspace (which satisfies $H^\perp = H$). Here the nontrivial coset is $H + (1,0) = H + (0,1) = \{(1,0), (0,1)\}$, which has no canonical representative.

To get around this difficulty we can view restriction to a coset $H+z$ as consisting of two steps: first, translation of the domain by a fixed representative $z$, and then restriction to the subspace $H$. Let’s introduce some notation for the first operation:

Definition 24 Let $f : {\mathbb F}_2^n \to {\mathbb R}$ and let $z \in {\mathbb F}_2^n$. We define the function $f^{+z} : {\mathbb F}_2^n \to {\mathbb R}$ by $f^{+z}(x) = f(x+z)$.

By substituting $x = x+z$ into the Fourier expansion of $f$, we deduce:

Fact 25 The Fourier coefficients of $f^{+z}$ are given by $\widehat{f^{+z}}(\gamma) = (-1)^{\gamma \cdot z} \widehat{f}(\gamma)$; i.e., \[ f^{+z}(x) = \sum_{\gamma \in {\widehat{{\mathbb F}_2^n}}} \chi_{\gamma}(z)\widehat{f}(\gamma)\,\chi_\gamma(x). \]

(This fact also follows by noting that $f^{+z} = \varphi_{\{z\}} * f$; see the exercises.)

We can now give notation for the restriction of a function to an affine subspace:

Definition 26 Let $f : {\mathbb F}_2^n \to {\mathbb R}$, $z \in {\mathbb F}_2^n$, $H \leq {\mathbb F}_2^n$. We write $f^{+z}_H : H \to {\mathbb R}$ for the function $(f^{+z})_H$; namely, the restriction of $f$ to coset $H+z$ with the representative $z$ made explicit.

Finally, we would like to consider Fourier coefficients of restricted functions $f^{+z}_H$. These can be indexed by the cosets of $H^\perp$ in ${\widehat{{\mathbb F}_2^n}}$. However we again have a notational difficulty since the only coset with a canonical representative is $H^\perp$ itself, with representative $0$. There is no need to introduce extra notation for $\widehat{f^{+z}_H}(0)$, the average value of $f$ on coset $H+z$, since it is just \[ \mathop{\bf E}_{\boldsymbol{h} \sim H}[f(\boldsymbol{h}+z)] = \langle \varphi_H, f^{+z} \rangle. \] Applying Plancherel on the right-hand side, as well as Proposition 11 and Fact 25, we deduce the following classical fact:

Poisson Summation Formula Let $f : {\mathbb F}_2^n \to {\mathbb R}$, $H \leq {\mathbb F}_2^n$, $z \in {\mathbb F}_2^n$. Then \[ \mathop{\bf E}_{\boldsymbol{h} \sim H}[f(\boldsymbol{h} + z)] = \sum_{\gamma \in H^\perp} \chi_\gamma(z) \widehat{f}(\gamma). \]

10 comments to §3.3: Restrictions

Leave a Reply




You can use most standard LaTeX, as well as these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>