科普文章 - Analysis of Boolean Functions Chapter 1

Analysis of Boolean Functions Chapter 1

Exercises

1.1

Compute the Fourier expansions of the following functions:

(a)

$$\text{min}_2(x)=-\frac{1}{2}+\frac{1}{2}x_1+\frac{1}{2}x_2+\frac{1}{2}x_1x_2.$$

(b)

$$\text{min}_3(x)=-\frac{3}{4}+\frac{1}{4}x_1+\frac{1}{4}x_2+\frac{1}{4}x_3+\frac{1}{4}x_1x_2+\frac{1}{4}x_1x_3+\frac{1}{4}x_2x_3+\frac{1}{4}x_1x_2x_3.$$ $$\text{max}_3(x)=\frac{3}{4}+\frac{1}{4}x_1+\frac{1}{4}x_2+\frac{1}{4}x_3-\frac{1}{4}x_1x_2-\frac{1}{4}x_2x_3-\frac{1}{4}x_1x_3+\frac{1}{4}x_1x_2x_3.$$

(c)

$$1_{\{a\}}(x)=2^{-n}\sum_{S\subseteq [n]}\chi_S(a)\chi_S(x).$$

(d)

$$\begin{aligned} \varphi_{\{a\}}(x)&=2^n1_{\{a\}}(x)\\ &=\sum_{S\subseteq [n]}\chi_S(a)\chi_S(x). \end{aligned}$$

(e)

$$\begin{aligned} \varphi_{\{a,a+e_i\}}(x)&=\frac{1}{2}(\varphi_{\{a\}}(x)+\varphi_{\{a+e_i\}}(x))\\ &=\frac{1}{2}\sum_{S\subseteq [n]}(\chi_S(a)+\chi_S(a+e_i))\chi_S(x). \end{aligned}$$

(f)

Denote $|x|$ as the number of $1$ in $x$, we have

$$f(x)=(1+\rho)^{|x|}(1-\rho)^{n-|x|}.$$

Thus

$$\begin{aligned} \hat f(S)&=2^{-n}\sum_x f(x)\chi_S(x)\\ &=2^{-n}\prod_{i=1}^n\left((1+\rho)+(1-\rho)\cdot (-1)^{[i\in S]}\right)\\ &=\rho^{|S|}, \end{aligned}$$

and

$$f(x)=\sum_{S\subseteq [n]} \rho^{|S|}\chi_S(x).$$

(g)

$$\begin{aligned} \hat{\text{IP}}_{2n}(S)&=2^{-2n}\sum_{x,y}\text{IP}_{2n}(x,y)\chi_S(x,y)\\ &=2^{-2n}\prod_{i=1}^n \left(-1+(-1)^{[i\in S]}+(-1)^{[i+n\in S]}+(-1)^{[i\in S]+[i+n\in S]}\right)\\ &=2^{-n}\prod_{i=1}^{n}(-1)^{[i\in S\lor i+n\in S]}, \end{aligned}$$

and

$$\text{IP}_{2n}(x,y)=\sum_{S\subseteq[2n]}\hat{\text{IP}}_{2n}(S)\chi_S(x,y).$$

(h)

$$\begin{aligned} \text{Equ}_n(x)&=1_{\{(-1)^{\otimes n}\}}(x)+1_{\{1^{\otimes n}\}}(x)\\ &=2^{-n}\sum_{S\subseteq [n]}(\chi_S((-1)^{\otimes n})+\chi_S(1^{\otimes n}))\chi_S(x)\\ &=2^{-n+1}\sum_{S\subseteq [n]}[|S|\equiv 0\bmod 2]\chi_S(x). \end{aligned}$$

(i)

$$\begin{aligned} \text{NAE}_n(x)&=1-\text{Equ}_n(x)\\ &=(1-2^{n+1})\chi_{\varnothing}(x)-2^{-n+1}\sum_{S\subseteq [n],S\neq \varnothing}[|S|\equiv 0\bmod 2]\chi_S(x). \end{aligned}$$

(j)

$$\text{Sel}(x)=\frac{1}{2}x_2+\frac{1}{2}x_3-\frac{1}{2}x_1x_2+\frac{1}{2}x_1x_3.$$

(k)

$$\text{mod}_3(x)=\frac{1}{4}+\frac{1}{4}(-1)^{x_1+x_2}+\frac{1}{4}(-1)^{x_1+x_3}+\frac{1}{4}(-1)^{x_2+x_3}.$$

(l)

$$\text{OXR}(x)=\frac{3}{4}-\frac{1}{4}(-1)^{x_1}-\frac{1}{4}(-1)^{x_2+x_3}-\frac{1}{4}(-1)^{x_1+x_2+x_3}.$$

(m)

$$\text{Sort}_4(x)=-\frac{1}{2}x_1x_2+\frac{1}{2}x_1x_4-\frac{1}{2}x_2x_3-\frac{1}{2}x_3x_4$$

(n)

(o)

For odd $n$ and $|S|=m$, we have

$$\hat{\text{Maj}_n}(S)=\frac{1}{2^5}\sum_{i=0}^m \binom m i(-1)^i\sum_{j=0}^{n-m}\binom{n-m} j(-1)^{[i+j\ge 3]}.$$

Thus we have

$$\text{Maj}_5(x)=\sum_{S\subseteq [5],|S|=1}\frac{3}{8}\chi_S(x)-\sum_{S\subseteq [5],|S|=3}\frac{1}{8}\chi_S(x)+\sum_{S\subseteq [5],|S|=5}\frac{3}{8}\chi_S(x);$$ $$\text{Maj}_7(x)=\sum_{S\subseteq [7],|S|=1}\frac{5}{16}\chi_S(x)-\sum_{S\subseteq [7],|S|=3}\frac{1}{16}\chi_S(x)+\sum_{S\subseteq [7],|S|=5}\frac{1}{16}\chi_S(x)-\sum_{S\subseteq [7],|S|=7}\frac{5}{16}\chi_S(x).$$

(p)

Let $c(x)$ be the number of $1$’s in $x$. Observe that

$$\text{CQ}_n(x)=\begin{cases}-1 & (c(x)\equiv 2,3\bmod 4)\\ 1 & (c(x)\equiv 0,1\bmod 4)\end{cases}$$

Thus,

$$\text{CQ}_n(x)=\sum_{S\subseteq[n]}\hat{\text{CQ}}_n(S)\chi_S(x)$$

where for $|S|=m$,

$$\begin{aligned} \hat{\text{CQ}}_n(S)&=\frac{1}{2^n}\sum_{i=0}^m\binom m i(-1)^i\sum_{j=0}^{n-m}\binom{n-m} j\alpha(i+j),\\ \alpha(t)&=\begin{cases}-1 & (t\equiv 2,3\bmod 4)\\ 1 & (t\equiv 0,1\bmod 4)\end{cases}. \end{aligned}$$

1.2

$2^{n+1}$ Boolean functions $f:\{-1,1\}^n\to \{-1,1\}$ have exactly $1$ nonzero Fourier coefficient, they are all $\chi_S(x)$ and $-\chi_S(x)$.

1.3

For any $S\subseteq [n]$,

$$\hat f(S)=\langle f,\chi_S\rangle=\sum_{f(x)=1}\chi_S(x).$$

Since $\chi_S(x)\in\{1,-1\}$ and $|\{x\mid f(x)=1\}|$ is odd, we know that $\hat f(S)\ne 0$.

1.4