- Compute the Fourier expansions of the following functions:
- $\max_2 : \{-1,1\}^2 \to \{-1,1\}$, the maximum function on $2$ bits (also known as the logical $\mathrm{AND}$ function);
- $\min_3 : \{-1,1\}^3 \to \{-1,1\}$ and $\max_3 : \{-1,1\}^3 \to \{-1,1\}$;
- the indicator function $1_{\{a\}} : {\mathbb F}_2^n \to \{0,1\}$, where $a \in {\mathbb F}_2^n$;
- the density function $\varphi_{\{a\}} : {\mathbb F}_2^n \to {\mathbb R}^{\geq 0}$, where $a \in {\mathbb F}_2^n$;
- 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;
- the density function corresponding to the product probability distribution on $\{-1,1\}^n$ in which each coordinate has mean $\rho \in [-1,1]$;
- 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}$;
- 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$;
- 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;
- 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$;
- $\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$;
- $\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;
- 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$;
- 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$:
- the majority functions $\mathrm{Maj}_5 : \{-1,1\}^5 \to \{-1,1\}$ and $\mathrm{Maj}_7 : \{-1,1\}^7 \to \{-1,1\}$;
- 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.)
- How many boolean functions $f : \{-1,1\}^n \to \{-1,1\}$ have exactly $1$ nonzero Fourier coefficient?
-
Show that no boolean function $f : \{-1,1\}^n \to \{-1,1\}$ has exactly $2$ nonzero Fourier coefficients.[See Ex. 20] - 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.
- 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]$.
- 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$?
- Use Parseval’s Theorem to prove uniqueness of the Fourier expansion.
- 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.)
- 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$.
- Express $\widehat{f^\dagger}(S)$ in terms of $\widehat{f}(S)$.
- 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}$).
- 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*}
- In this problem we consider representing $\mathsf{False}, \mathsf{True}$ as $0, 1 \in {\mathbb R}$.
- 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\}$.
- 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$.)
- Show that all coefficients $c_S$ in the representation \eqref{eqn:zotzo-poly} will be integers in the range $[-2^n, 2^n]$.
- 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)$.
- 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\}$.
- Show that $\deg(f) = \deg(a+bf)$ for any $a, b \in {\mathbb R}$ (assuming $b \neq 0$, $a+bf \neq 0$).
- 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.
- Which functions in Exercise 1 have “nontrivial” degree? (Here $f : \{-1,1\}^n \to {\mathbb R}$ has “nontrivial” degree if $\deg(f) < n$.)
- Suppose that $f : \{-1,1\}^n \to \{-1,1\}$ has $\deg(f) = k \geq 1$.
- Show that $f$’s real multilinear representation over $\{0,1\}$ (see Exercise 10), call it $q(x)$, also has $\deg(q) = k$.
- 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}$.
- Show that $\sum_{S \subseteq [n]} |\widehat{f}(S)| \leq 2^{k-1}$.
- 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}$.
- 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}$.
- 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.
- 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.
- Show that taking the Fourier transform is essentially an “involution”: $\widehat{\widehat{f}} = 2^{-n} f$ (using the notations from part (b)).
- 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)|\}$.
- Compute the mean and variance of each function from Exercise 1.
- 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$.
- 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.
- 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} \]
- Let $f : \{-1,1\}^n \to \{-1,1\}$.
- Suppose $\mathbf{W}^{1}[f] = 1$. Show that $f(x) = \pm \chi_S$ for some $|S| = 1$.
- Suppose $\mathbf{W}^{\leq 1}[f] = 1$. Show that $f$ depends on at most $1$ input coordinate.
- 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$?
- 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?
- Verify Propositions 26 and 27 from §1.5.
- Prove Proposition 24 from §1.5, referring to standard definitions of probability metrics.
- 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$.
- Show directly from the definition that the convolution operator is associative and commutative.
- Verify that 1 $\Leftrightarrow$ 2 in Definition 29 from §1.6.
- 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.
-
- 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.)
- Deduce that the BLR Test rejects $f$ with probability at least $3\delta – 10\delta^2 + 8\delta^3$.
- Show that this lower bound cannot be improved to $c \delta – O(\delta^2)$ for any $c > 3$.
-
- 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$
- 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$.
- 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).
- 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$.)
- 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$.
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$.
- Show that this is well-defined, meaning that $\text{can}(f)$ is the same function for any choice of $\pi \in P_n$.
- Show that $\text{can}(f)$ is indeed a canonical form; i.e., it satisfies (i) and (ii) above.
- 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.
- 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.
in #29 it says “4. Let can(f)=fπ for (any) π∈Pn.”
is the “4.” a typo?
Fixed, thanks!
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.
In question 1.10 a), shouldn’t the condition not be a+bf!=0, but rather b!=0?
Er, that should be 1.11 a); was working from the draft numbering.
You’re right, though I guess it should be both.
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
I’m sorry for making a mistake. It’s correct.
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?
No, n is ok. I, for some reason, thought it could be any affine function. Sorry for bothering
Hi,
Can I find solutions for those questions?
Thank you.
Hi, this is a remark about exercise 1.20 in the book, which I can’t find here.
I think the right statement is
$Var[f^2] = 2 \sum_{i\neq j}{\hat{f}(i)^2 \hat{f}(j)^2}$.
Take for example $f(x) = (x_1 +x_2)/2$,
then LHS is $1/4$ and RHS is $2 \cdot (1/16+1/16)$ which is OK.
Great catch — you are correct! This exercise actually makes an appearance (silently on the blog, explicitly in the final book) in the proof of the FKN Theorem in Chapter 9.1. Your fix actually improves the constant there from 6402 to 3202
Thanks!
By the way, Avishay, two more corrections and you get promoted to “special thanks” in the acknowledgments
Is $\rho\neq 0$ required in 1(f)?
I can’t figure out ex.12 b) and c) in the proposed way.
That is, show that the Fourier spectrum is 2^{1 – k} granular, using the {0,1} representation.
Any insight?
#16
What is z^T?