Chapter 1 exercises

  1. Compute the Fourier expansions of the following functions: 
    1. $\max_2 : \{-1,1\}^2 \to \{-1,1\}$, the maximum function on $2$ bits (also known as the logical $\mathrm{AND}$ function);
    2. $\min_3 : \{-1,1\}^3 \to \{-1,1\}$ and $\max_3 : \{-1,1\}^3 \to \{-1,1\}$;
    3. the indicator function $1_{\{a\}} : {\mathbb F}_2^n \to \{0,1\}$, where $a \in {\mathbb F}_2^n$;
    4. the density function $\varphi_{\{a\}} : {\mathbb F}_2^n \to {\mathbb R}^{\geq 0}$, where $a \in {\mathbb F}_2^n$;
    5. the density function $\varphi_{\{a, a+e_i\}} : {\mathbb F}_2^n \to {\mathbb R}^{\geq 0}$, where $a \in {\mathbb F}_2^n$ and $e_i = (0, \dots, 0, 1, 0, \dots, 0)$ with the $1$ in the $i$th coordinate;
    6. the density function corresponding to the product probability distribution on $\{-1,1\}^n$ in which each coordinate has mean $\rho \in [-1,1]$;
    7. the inner product mod $2$ function, $\mathrm{IP}_{2n} : {\mathbb F}_2^{2n} \to \{-1,1\}$ defined by $\mathrm{IP}_{2n}(x_1, \dots, x_n, y_1, \dots, y_n) = (-1)^{x \cdot y}$;
    8. the equality function $\mathrm{Equ}_n : \{-1,1\}^n \to \{0,1\}$, defined by $\mathrm{Equ}_n(x) = 1$ if and only if $x_1 = x_2 = \cdots = x_n$;
    9. the not-all-equal function $\mathrm{NAE}_n : \{-1,1\}^n \to \{0,1\}$, defined by $\mathrm{NAE}_n(x) = 1$ if and only if the bits $x_1, \dots, x_n$ are not all equal;
    10. the selection function $\mathrm{Sel} : \{-1,1\}^3 \to \{-1,1\}$ which outputs $x_2$ if $x_1 = -1$ and outputs $x_3$ if $x_1 = 1$;
    11. $\mathrm{mod}_3 : {\mathbb F}_2^3 \to \{0,1\}$ which is $1$ if and only if the number of $1$’s in the input is congruent to $1$ modulo $3$;
    12. $\mathrm{OXR} : {\mathbb F}_2^3 \to \{0,1\}$ defined by $\mathrm{OXR}(x_1,x_2,x_3) = x_1 \vee (x_2 \oplus x_3)$. Here $\vee$ denotes logical OR, $\oplus$ denotes logical XOR;
    13. the sortedness function $\mathrm{Sort}_4 : \{-1,1\}^4 \to \{-1,1\}$, defined by $\mathrm{Sort}_4(x) = -1$ if and only if $x_1 \leq x_2 \leq x_3 \leq x_4$ or $x_1 \geq x_2 \geq x_3 \geq x_4$;
    14. the hemi-icosahedron function $\mathrm{HI} : \{-1,1\}^6 \to \{-1,1\}$, defined as follows: $\mathrm{HI}(x)$ is $1$ if the number of $1$’s in $x$ is $1$, $2$, or $6$. $\mathrm{HI}(x)$ is $-1$ if the number of $-1$’s in $x$ is $1$, $2$, or $6$. Otherwise, $\mathrm{HI}(x)$ is $1$ if and only if one of the ten facets in the following diagram has all three of its vertices $1$:
       
    15. the majority functions $\mathrm{Maj}_5 : \{-1,1\}^5 \to \{-1,1\}$ and $\mathrm{Maj}_7 : \{-1,1\}^7 \to \{-1,1\}$;
    16. the complete quadratic function $\mathrm{CQ}_n : {\mathbb F}_2^{n} \to \{-1,1\}$ defined by $\mathrm{CQ}_n(x) = \chi(\sum_{1 \leq i < j \leq n} x_ix_j)$. (Hint: determine $\mathrm{CQ}_n(x)$ as a function of the number of $1$’s in the input modulo $4$. You will want to distinguish whether $n$ is even or odd.)
  2. How many boolean functions $f : \{-1,1\}^n \to \{-1,1\}$ have exactly $1$ nonzero Fourier coefficient?
  3. Show that no boolean function $f : \{-1,1\}^n \to \{-1,1\}$ has exactly $2$ nonzero Fourier coefficients. [See Ex. 20]
  4. Let $f : {\mathbb F}_2^n \to \{0,1\}$ and suppose $\#\{x : f(x) = 1\}$ is odd. Prove that all of $f$’s Fourier coefficients are nonzero.
  5. Let $f : \{-1,1\}^n \to {\mathbb R}$ have Fourier expansion $f(x) = \sum_{S \subseteq [n]} \widehat{f}(S)\,x^S$. Let $\widetilde{f} : {\mathbb R}^n \to {\mathbb R}$ be the extension of $f$ which is also defined by $\widetilde{f}(x) = \sum_{S \subseteq [n]} \widehat{f}(S)\,x^S$. Show that if $\mu = (\mu_1, \dots, \mu_n) \in [-1,1]^n$ then \[ \widetilde{f}(\mu) = \mathop{\bf E}_{\boldsymbol{y}}[f(\boldsymbol{y})], \] where $\boldsymbol{y}$ is the random string in $\{-1,1\}^n$ defined by having $\mathop{\bf E}[\boldsymbol{y}_i] = \mu_i$ independently for all $i \in [n]$.
  6. Prove that any $f : \{-1,1\}^n \to \{-1,1\}$ has at most one Fourier coefficient with magnitude exceeding $1/2$. Is this also true for any $f : \{-1,1\}^n \to {\mathbb R}$ with $\|f\|_2 = 1$?
  7. Use Parseval’s Theorem to prove uniqueness of the Fourier expansion.
  8. Let $\boldsymbol{f} : \{-1,1\}^n \to \{-1,1\}$ be a random function (i.e., each $\boldsymbol{f}(x)$ is $\pm 1$ with probability $1/2$, independently for all $x \in \{-1,1\}^n$). Show that for each $S \subseteq [n]$, the random variable $\widehat{\boldsymbol{f}}(S)$ has mean $0$ and variance $2^{-n}$. (Hint: Parseval.)
  9. The (boolean) dual of $f : \{-1,1\}^n \to \{-1,1\}$ is the function $f^\dagger$ defined by $f^\dagger(x) = -f(-x)$. The function $f$ is said to be odd if it equals its dual; equivalently, if $f(-x) = -f(x)$ for all $x$. The function $f$ is said to be even if $f(-x) = f(x)$ for all $x$. Given any function $f : \{-1,1\}^n \to {\mathbb R}$, its odd part is the function $f^\mathrm{odd} : \{-1,1\}^n \to {\mathbb R}$ defined by $f^\mathrm{odd}(x) = (f(x) – f(-x))/2$, and its even part is the function $f^\mathrm{even} : \{-1,1\}^n \to {\mathbb R}$ defined by $f^\mathrm{even}(x) = (f(x) + f(-x))/2$. 
    1. Express $\widehat{f^\dagger}(S)$ in terms of $\widehat{f}(S)$.
    2. Verify that $f = f^\mathrm{odd} + f^\mathrm{even}$ and that $f$ is odd (respectively, even) if and only if $f = f^\mathrm{odd}$ (respectively, $f = f^\mathrm{even}$).
    3. Show that \begin{equation*} f^\mathrm{odd} = \sum_{\substack{S \subseteq [n] \\ |S|\ \mathrm{odd}}} \widehat{f}(S)\,\chi_S, \qquad f^\mathrm{even} = \sum_{\substack{S \subseteq [n] \\ |S|\ \mathrm{even}}} \widehat{f}(S)\,\chi_S. \end{equation*}
  10. In this problem we consider representing $\mathsf{False}, \mathsf{True}$ as $0, 1 \in {\mathbb R}$.
    1. Using the interpolation method from Section 2, show that every $f : \{\mathsf{False},\mathsf{True}\}^n \to \{\mathsf{False},\mathsf{True}\}$ can be represented as a real multilinear polynomial \begin{equation} \label{eqn:zotzo-poly} q(x) = \sum_{S \subseteq [n]} c_S \prod_{i \in S} x_i, \end{equation} “over $\{0,1\}$”, meaning mapping $\{0,1\}^n \to \{0,1\}$.
    2. Show that this representation is unique. (Hint: if $q$ as in \eqref{eqn:zotzo-poly} has at least one nonzero coefficient, consider $q(a)$ where $a \in \{0,1\}^n$ is the indicator vector of a minimal $S$ with $c_S \neq 0$.)
    3. Show that all coefficients $c_S$ in the representation \eqref{eqn:zotzo-poly} will be integers in the range $[-2^n, 2^n]$.
    4. Let $f : \{\mathsf{False}, \mathsf{True}\}^n \to \{\mathsf{False}, \mathsf{True}\}$. Let $p(x)$ be $f$’s multilinear representation when $\mathsf{False}, \mathsf{True}$ are $1, -1 \in {\mathbb R}$ (i.e., $p$ is the Fourier expansion of $f$) and let $q(x)$ be $f$’s multilinear representation when $\mathsf{False}, \mathsf{True}$ are $0, 1 \in {\mathbb R}$. Show that $q(x) = \tfrac{1}{2} – \tfrac{1}{2} p(1-2x_1, \dots, 1-2x_n)$.
  11. Let $f : \{-1,1\}^n \to {\mathbb R}$ be not identically $0$. The (real) degree of $f$, denoted $\deg(f)$, is defined to be the degree of its multilinear (Fourier) expansion; i.e., $\max \{|S| : \widehat{f}(S) \neq 0\}$.
    1. Show that $\deg(f) = \deg(a+bf)$ for any $a, b \in {\mathbb R}$ (assuming $b \neq 0$, $a+bf \neq 0$).
    2. Show that $\deg(f) \leq k$ if and only if $f$ is a real linear combination of functions $g_1, \dots, g_s$, each of which depends on at most $k$ input coordinates.
    3. Which functions in Exercise 1 have “nontrivial” degree? (Here $f : \{-1,1\}^n \to {\mathbb R}$ has “nontrivial” degree if $\deg(f) < n$.)
  12. Suppose that $f : \{-1,1\}^n \to \{-1,1\}$ has $\deg(f) = k \geq 1$.
    1. Show that $f$’s real multilinear representation over $\{0,1\}$ (see Exercise 10), call it $q(x)$, also has $\deg(q) = k$.
    2. Using Exercise 10(c),(d), deduce that $f$’s Fourier spectrum is “$2^{1-k}$-granular”, meaning each $\widehat{f}(S)$ is an integer multiple of $2^{1-k}$.
    3. Show that $\sum_{S \subseteq [n]} |\widehat{f}(S)| \leq 2^{k-1}$.
  13. A Hadamard matrix is any $N \times N$ real matrix with $\pm 1$ entries and orthogonal rows. Particular examples are the Walsh–Hadamard matrices $H_N$, inductively defined for $N = 2^n$ as follows: $H_1 = \begin{bmatrix} 1 \end{bmatrix}$, $H_{2^{n+1}} = \begin{bmatrix} H_{2^n} & H_{2^n} \\ H_{2^n} & -H_{2^n} \end{bmatrix}$.
    1. Let’s index the rows and columns of $H_{2^n}$ by the integers $\{0, 1, 2, \dots, 2^n-1\}$ rather than $[2^n]$. Further, let’s identify such an integer $i$ with its binary expansion $(i_0, i_1, \dots, i_{n-1}) \in {\mathbb F}_2^n$, where $i_0$ is the least significant bit and $i_{n-1}$ the most. E.g., if $n = 3$, we identify the index $i = 6$ with $(0, 1, 1)$. Now show that the $(\gamma, x)$ entry of $H_{2^n}$ is $(-1)^{\gamma \cdot x}$.
    2. Show that if $f : {\mathbb F}_2^n \to {\mathbb R}$ is represented as a column vector in ${\mathbb R}^{2^n}$ (according to the indexing scheme from part (a)) then $2^{-n} H_{2^n} f = \widehat{f}$. Here we think of $\widehat{f}$ as also being a function ${\mathbb F}_2^n \to {\mathbb R}$, identifying subsets $S \subseteq \{0, 1, \dots, n-1\}$ with their indicator vectors.
    3. Show how to compute $H_{2^n} f$ using just $n 2^n$ additions and subtractions (rather than $2^{2n}$ additions and subtractions as the usual matrix-vector multiplication algorithm would require). This computation is called the Fast Walsh–Hadamard Transform and is the method of choice for computing the Fourier expansion of a generic function $f : {\mathbb F}_2^n \to {\mathbb R}$ when $n$ is large.
    4. Show that taking the Fourier transform is essentially an “involution”: $\widehat{\widehat{f}} = 2^{-n} f$ (using the notations from part (b)).
  14. Let $f : \{-1,1\}^n \to {\mathbb R}$ and let $0 < p \leq q < \infty$. Show that $\|f\|_p \leq \|f\|_q$. (Hint: use Jensen’s inequality with the convex function $t \mapsto t^{q/p}$.) Extend the inequality to the case $q = \infty$, where $\|f\|_\infty$ is defined to be $\max_{x \in \{-1,1\}^n}\{|f(x)|\}$.
  15. Compute the mean and variance of each function from Exercise 1.
  16. Let $f : \{-1,1\}^n \to {\mathbb R}$. Let $K \subseteq [n]$ and let $z \in \{-1,1\}^K$. Suppose $g : \{-1,1\}^{[n] \setminus K} \to {\mathbb R}$ is the subfunction of $f$ gotten by restricting the $K$-coordinates to be $z$. Show that $\mathop{\bf E}[g] = \sum_{T \subseteq K} \widehat{f}(T)\,z^T$.
  17. If $f : \{-1,1\}^n \to \{-1,1\}$, show that $\mathop{\bf Var}[f] = 4 \cdot \mathrm{dist}(f, 1) \cdot \mathrm{dist}(f, -1)$. Deduce Proposition 15 from §1.4.
  18. For any $f : \{-1,1\}^n \to {\mathbb R}$, show that \[ \langle f^{=k}, f^{=\ell} \rangle = \begin{cases}\mathbf{W}^{k}[f] & \text{if $k = \ell$,} \\ 0 & \text{if $k \neq \ell$.} \end{cases} \]
  19. Let $f : \{-1,1\}^n \to \{-1,1\}$. 
    1. Suppose $\mathbf{W}^{1}[f] = 1$. Show that $f(x) = \pm \chi_S$ for some $|S| = 1$.
    2. Suppose $\mathbf{W}^{\leq 1}[f] = 1$. Show that $f$ depends on at most $1$ input coordinate.
    3. Suppose $\mathbf{W}^{\leq 2}[f] = 1$. Must $f$ depend on at most $2$ input coordinates? At most $3$ input coordinates? What if we assume $\mathbf{W}^{2}[f] = 1$?
  20. Prove that there are no functions $f : \{-1,1\}^n \to \{-1,1\}$ with exactly $2$ nonzero Fourier coefficients. What about exactly $3$ nonzero Fourier coefficients?
  21. Verify Propositions 26 and 27 from §1.5.
  22. Prove Proposition 24 from §1.5, referring to standard definitions of probability metrics.
  23. Let $A \subseteq \{-1,1\}^n$ have “volume” $\delta$, meaning $\mathop{\bf E}[1_A] = \delta$. Suppose $\varphi$ is a probability density supported on $A$, meaning $\varphi(x) = 0$ when $x \notin A$. Show that $\|\varphi\|_2^2 \geq 1/\delta$ with equality if $\varphi = \varphi_A$, the uniform density on $A$.
  24. Show directly from the definition that the convolution operator is associative and commutative.
  25. Verify that 1 $\Leftrightarrow$ 2 in Definition 29 from §1.6.
  26. Suppose an algorithm is given query access to a linear function $f : {\mathbb F}_2^n \to {\mathbb F}_2$ and its task is to determine which linear function $f$ is. Show that querying $f$ on $n$ inputs is necessary and sufficient.
  27.  
    1. Generalize Exercise 6 as follows: Let $f : {\mathbb F}_2^n \to \{-1,1\}$ and suppose that $\mathrm{dist}(f, \chi_{S^*}) = \delta$. Show that $|\widehat{f}(S)| \leq 2\delta$ for all $S \neq S^*$. (Hint: use the union bound.)
    2. Deduce that the BLR Test rejects $f$ with probability at least $3\delta – 10\delta^2 + 8\delta^3$.
    3. Show that this lower bound cannot be improved to $c \delta – O(\delta^2)$ for any $c > 3$.
    1. We call $f : {\mathbb F}_2^n \to {\mathbb F}_2$ an affine function if $f(x) = a \cdot x + b$ for some $a \in {\mathbb F}_2^n$, $b \in {\mathbb F}_2$. Show that $f$ is affine if and only if $f(x) + f(y) + f(z) = f(x+y+z)$ for all $x, y, z, \in {\mathbb F}_2^n$
    2. Let $f : {\mathbb F}_2^n \to {\mathbb R}$. Suppose we choose ${\boldsymbol{x}}, \boldsymbol{y}, \boldsymbol{z} \sim {\mathbb F}_2^n$ independently and uniformly. Show that $\mathop{\bf E}[f({\boldsymbol{x}})f(\boldsymbol{y})f(\boldsymbol{z})f({\boldsymbol{x}}+\boldsymbol{y}+\boldsymbol{z})] = \sum_{S} \widehat{f}(S)^4$.
    3. Give a $4$-query test for a function $f : {\mathbb F}_2^n \to {\mathbb F}_2$ with the following property: if the test accepts with probability $1-\epsilon$ then $f$ is $\epsilon$-close to being affine. All four query inputs should have the uniform distribution on ${\mathbb F}_2^n$ (but of course need not be independent).
    4. Give an alternate $4$-query test for being affine in which three of the query inputs are uniformly distributed and the fourth is non-random. (Hint: show that $f$ is affine if and only if $f(x) + f(y) + f(0) = f(x+y)$ for all $x, y \in {\mathbb F}_2^n$.)
  28. Permutations $\pi \in S_n$ act on strings $x \in \{-1,1\}^n$ in the natural way: $(x^\pi)_i$ = $x_{\pi(i)}$. They also act on functions $f : \{-1,1\}^n \to \{-1,1\}$ via $f^\pi(x) = f(x^\pi)$ for all $x \in \{-1,1\}^n$. We say that $g, h : \{-1,1\}^n \to \{-1,1\}$ are (permutation)-isomorphic if $g = h^\pi$ for some $\pi \in S_n$. 
    1. Show that $\widehat{f^{\pi}}(S) = \widehat{f}(\pi^{-1}(S))$ for all $S \subseteq [n]$.

    For future reference, when we write $(\widehat{f}(S))_{|S|=k}$, we mean the sequence of degree-$k$ Fourier coefficients of $f$, listed in lexicographic order of the $k$-sets $S$.

    Given complete truth tables of some $g$ and $h$ we might wish to determine whether they are isomorphic. One way to do this would be to define a canonical form $\text{can}(f) : \{-1,1\}^n \to \{-1,1\}$ for each $f : \{-1,1\}^n \to \{-1,1\}$, meaning that: (i) $\text{can}(f)$ is isomorphic to $f$; (ii) if $g$ is isomorphic to $h$ then $\text{can}(g) = \text{can}(h)$. Then we can determine whether $g$ is isomorphic to $h$ by checking whether $\text{can}(g) = \text{can}(h)$. Here is one possible way to define a canonical form for $f$:

    • Set $P_0 = S_n$. 
    • For each $k = 1, 2, 3, \dots, n$,
      • Define $P_k$ to be the set of all $\pi \in P_{k-1}$ which make the sequence $(\widehat{f^\pi}(S))_{|S|=k}$ maximal in lexicographic order on ${\mathbb R}^{\binom{n}{k}}$.
    • Let $\text{can}(f) = f^{\pi}$ for (any) $\pi \in P_n$.
    1. Show that this is well-defined, meaning that $\text{can}(f)$ is the same function for any choice of $\pi \in P_n$.
    2. Show that $\text{can}(f)$ is indeed a canonical form; i.e., it satisfies (i) and (ii) above.
    3. Show that if $\widehat{f}(\{1\}), \dots, \widehat{f}(\{n\})$ are distinct numbers then $\text{can}(f)$ can be computed in $\widetilde{O}(2^n)$ time.
    4. We could more generally consider $g, h : \{-1,1\}^n \to \{-1,1\}$ to be isomorphic if $g(x) = h(\pm x_{\pi(1)}, \dots, \pm x_{\pi(n)})$ for some permutation $\pi$ on $[n]$ and some choice of signs. Extend the results of this exercise to handle this definition.

19 comments to Chapter 1 exercises

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>