# 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 $$\label{eqn:zotzo-poly} q(x) = \sum_{S \subseteq [n]} c_S \prod_{i \in S} x_i,$$ “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.

### 16 comments to Chapter 1 exercises

• derya neftci

in #29 it says “4. Let can(f)=fπ for (any) π∈Pn.”
is the “4.” a typo?

• Fixed, thanks!

• syz

Ex 3 seems to appear again as a sub-problem in Ex 20.

• You’re right! Whoops.

• Exercise 29 seems to have two sub-problem “a”?

• Thanks, fixed!

• A very minor one: “see Exercise 7″ in Exercise 12 should be “see Exercise 10″. The link is correct though.

• Thanks Tengyu! Please keep corrections like this coming — due to the way my TeX->blog workflow works, I have to fix all references to exercise numbers (and inter-chapter references) by hand. So it’s very error-prone and I need to catch the mistakes.

• Justin Hilyard

In question 1.10 a), shouldn’t the condition not be a+bf!=0, but rather b!=0?

• Justin Hilyard

Er, that should be 1.11 a); was working from the draft numbering.

• You’re right, though I guess it should be both.

• Lingxiao Huang

I doubt 27 b) has something wrong. For example, if δ=1, it becomes that BTR test rejects with prob at least 1. It’s strange. My result is BTR test rejects with prob at least 1-3δ+2δ^2-2δ^3

• Lingxiao Huang

I’m sorry for making a mistake. It’s correct.

• Magnus Find

Should the n in exercise 26 be n+1? There are 2^{n+1} linear functions and each query only gives one bit of information, so a decision tree would have height n+1?

• Magnus Find

No, n is ok. I, for some reason, thought it could be any affine function. Sorry for bothering

• Alex

Hi,

Can I find solutions for those questions?
Thank you.