## Analysis of Boolean Functions

by Ryan O'Donnell

Fall 2012 course at Carnegie Mellon

# §5.3: The Fourier coefficients of Majority

In this section we will analyze the Fourier coefficients of $\mathrm{Maj}_n$. In fact, we give an explicit formula for them in Theorem 16 below. But most of the time this formula is not too useful; instead, it’s better to understand the Fourier coefficients of $\mathrm{Maj}_n$ asymptotically as $n \to \infty$.

Let’s begin with a few basic observations. First, $\mathrm{Maj}_n$ is a symmetric function and hence $\widehat{\mathrm{Maj}_n}(S)$ only depends on $|S|$ (Exercise 1.29). Second, $\mathrm{Maj}_n$ is an odd function and hence $\widehat{\mathrm{Maj}_n}(S) = 0$ whenever $|S|$ is even (Exercise 1.9). It remains to determine the Fourier coefficients $\widehat{\mathrm{Maj}_n}(S)$ for $|S|$ odd. By symmetry, $\widehat{\mathrm{Maj}_n}(S)^2 = \mathbf{W}^{k}[\mathrm{Maj}_n]/\binom{n}{k}$ for all $|S| = k$, so if we are content to know the magnitudes of $\mathrm{Maj}_n$’s Fourier coefficients, it suffices to determine the quantities $\mathbf{W}^{k}(\mathrm{Maj}_n)$.

In fact, for each $k \in {\mathbb N}$ the quantity $\mathbf{W}^{k}(\mathrm{Maj}_n)$ converges to a fixed constant as $n \to \infty$. We can deduce this using our analysis of the noise stability of majority. From the previous section we know that for all $|\rho| \leq 1$, \begin{equation} \label{eqn:maj-stab-series} \lim_{n \to \infty} \mathbf{Stab}_\rho[\mathrm{Maj}_n] = \tfrac{2}{\pi} \arcsin \rho = \tfrac{2}{\pi}\Bigl(\rho + \tfrac16 \rho^3 + \tfrac{3}{40} \rho^5 + \tfrac{5}{112} \rho^7 + \cdots \Bigr), \end{equation} where we have used the power series for $\arcsin$, \begin{equation} \label{eqn:arcsin} \arcsin z = \sum_{k \text{ odd}} \ \frac{2}{k2^k} \binom{k-1}{\frac{k-1}{2}} \cdot z^k, \end{equation} valid for $|\rho| \leq 1$ (see the exercises). Comparing \eqref{eqn:maj-stab-series} with the formula $$\mathbf{Stab}_\rho[\mathrm{Maj}_n] = \sum_{k \geq 0} \mathbf{W}^{k}[\mathrm{Maj}_n] \cdot \rho^k$$ suggests the following: For each fixed $k \in {\mathbb N}$, \begin{equation} \label{eqn:maj-one-function} \lim_{n \to \infty} \mathbf{W}^{k}[\mathrm{Maj}_n] = [\rho^k] (\tfrac{2}{\pi} \arcsin \rho) = \begin{cases} \frac{4}{\pi k2^k} \binom{k-1}{\frac{k-1}{2}} & \text{if $k$ odd,} \\ 0 & \text{if $k$ even.} \end{cases} \end{equation} (Here $[z^k]F(z)$ denotes the coefficient on $z^k$ in power series $F(z)$.) Indeed, we prove this identity below in Theorem 19. The noise stability method which suggests it can also be made formal (see the exercises).

Identity \eqref{eqn:maj-one-function} is one way to formulate precisely the statement that the “Fourier spectrum of $\mathrm{Maj}_n$ converges”. Introducing notation such as “$\mathbf{W}^{k}(\mathrm{Maj})$” for the quantity in \eqref{eqn:maj-one-function}, we have the further asymptotics \begin{equation} \label{eqn:maj-asympt-asympt} \begin{aligned} \text{for $k$ odd,} \qquad \mathbf{W}^{k}(\mathrm{Maj}) &\sim \left(\tfrac{2}{\pi}\right)^{3/2} k^{-3/2},\\ \mathbf{W}^{>k}(\mathrm{Maj}) &\sim \left(\tfrac{2}{\pi}\right)^{3/2} k^{-1/2} \qquad \text{as $k \to \infty$}. \end{aligned} \end{equation} (You are asked to show the above in the exercises.) The estimates \eqref{eqn:maj-asympt-asympt}, together with the precise value $\mathbf{W}^{1}(\mathrm{Maj}) = \tfrac{2}{\pi}$, are usually all you need to know about the Fourier coefficients of majority.

Nevertheless, let’s now compute the Fourier coefficients of $\mathrm{Maj}_n$ exactly.

Theorem 16 If $|S|$ is even then $\widehat{\mathrm{Maj}_n}(S) = 0$. If $|S| = k$ is odd, $$\widehat{\mathrm{Maj}_n}(S) = (-1)^{\frac{k-1}{2}} \frac{\binom{\frac{n-1}{2}}{\frac{k-1}{2}}}{\binom{n-1}{k-1}} \cdot \tfrac{2}{2^n} {\textstyle \binom{n-1}{\frac{n-1}{2}}}.$$

Proof: The first statement holds because $\mathrm{Maj}_n$ is an odd function; henceforth we assume $|S| = k$ is odd. The trick will be to compute the Fourier expansion of majority’s derivative $\mathrm{D}_n \mathrm{Maj}_n = \mathrm{Half}_{n-1} : \{-1,1\}^{n-1} \to \{0,1\}$, the $0$-$1$ indicator of the set of $(n-1)$-bit strings with exactly half of their coordinates equal to $-1$. By the derivative formula and the fact that $\mathrm{Maj}_n$ is symmetric, $\widehat{\mathrm{Maj}_n}(S) = \widehat{\mathrm{Half}_{n-1}}(T)$ for any $T \subseteq [n-1]$ with $|T| = k-1$. So writing $n-1 = 2m$ and $k-1 = 2j$, it suffices to show \begin{equation} \label{eqn:half-formula} \widehat{\mathrm{Half}_{2m}}([2j]) = (-1)^{j} \frac{\binom{m}{j}}{\binom{2m}{2j}}\cdot \tfrac{1}{2^{2m}}{\textstyle \binom{2m}{m}}. \end{equation}

By the probabilistic definition of $\mathrm{T}_\rho$, for any $\rho \in [-1,1]$ we have $$\mathrm{T}_\rho \mathrm{Half}_{2m}(1, 1, \dots, 1) = \mathop{\bf E}_{{\boldsymbol{x}} \sim N_\rho((1, 1, \dots, 1))}[\mathrm{Half}_{2m}({\boldsymbol{x}})] = \mathop{\bf Pr}[{\boldsymbol{x}} \text{ has $m$ $1$'s and $m$ $-1$'s}],$$ where each coordinate of ${\boldsymbol{x}}$ is $1$ with probability $\tfrac{1}{2} + \tfrac{1}{2} \rho$. Thus \begin{equation} \label{eqn:half1} \mathrm{T}_\rho \mathrm{Half}_{2m}(1, 1, \dots, 1) = {\textstyle \binom{2m}{m}}(\tfrac{1}{2} + \tfrac{1}{2} \rho)^{m} (\tfrac{1}{2} – \tfrac{1}{2} \rho)^{m} = \tfrac{1}{2^{2m}} {\textstyle \binom{2m}{m}} (1-\rho^2)^m. \end{equation} On the other hand, by the Fourier formula for $\mathrm{T}_\rho$ and the fact that $\mathrm{Half}_{2m}$ is symmetric we have \begin{equation} \label{eqn:half2} \mathrm{T}_\rho \mathrm{Half}_{2m}(1, 1, \dots, 1) = \sum_{U \subseteq [2m]} \widehat{\mathrm{Half}_{2m}}(U) \rho^{|U|} = \sum_{i=0}^{2m} {\textstyle \binom{2m}{i}} \widehat{\mathrm{Half}_{2m}}([i]) \rho^{i}. \end{equation} Since we have equality $\eqref{eqn:half1} = \eqref{eqn:half2}$ between two degree-$2m$ polynomials of $\rho$ on all of $[-1,1]$, we can equate coefficients. In particular, for $i = 2j$ we have $${\textstyle \binom{2m}{2j}} \widehat{\mathrm{Half}_{2m}}([2j]) = \tfrac{1}{2^{2m}} {\textstyle \binom{2m}{m}} \cdot [\rho^{2j}](1-\rho^2)^m = \tfrac{1}{2^{2m}} {\textstyle \binom{2m}{m}} \cdot (-1)^j {\textstyle \binom{m}{j}},$$ confirming \eqref{eqn:half-formula}. $\Box$

You are asked to prove the following corollaries in the exercises:

Corollary 17 $\widehat{\mathrm{Maj}_n}(S) = \widehat{\mathrm{Maj}_n}(T)$ whenever $|S| + |T| = n+1$. Hence also $\mathbf{W}^{n-k+1}[\mathrm{Maj}_n] = \frac{k}{n-k+1} \mathbf{W}^{k}[\mathrm{Maj}_n]$.

Corollary 18 For any odd $k$, $\mathbf{W}^{k}[\mathrm{Maj}_n]$ is a strictly decreasing function of $n$ (for $n \geq k$ odd).

We can now prove the identity \eqref{eqn:maj-one-function}:

Theorem 19 For each fixed odd $k$, $$\mathbf{W}^{k}[\mathrm{Maj}_n] \searrow [\rho^k] (\tfrac{2}{\pi} \arcsin \rho) = \tfrac{4}{\pi k2^k} {\textstyle \binom{k-1}{\frac{k-1}{2}}}$$ as $n \geq k$ tends to $\infty$ (through the odd numbers). Further, we have the error bound \begin{equation} \label{eqn:maj-weight-err} [\rho^k] (\tfrac{2}{\pi} \arcsin \rho) \leq \mathbf{W}^{k}[\mathrm{Maj}_n] \leq (1+2k/n) \cdot [\rho^k] (\tfrac{2}{\pi} \arcsin \rho) \end{equation} for all $k < n/2$. (For $k > n/2$ one can use Corollary 17.)

Proof: Corollary 18 tells us that $\mathbf{W}^{k}[\mathrm{Maj}_n]$ is decreasing in $n$; hence we only need to justify \eqref{eqn:maj-weight-err}. Using the formula from Theorem 16 we have $$\frac{\mathbf{W}^{k}[\mathrm{Maj}_n]}{[\rho^k] (\tfrac{2}{\pi} \arcsin \rho)} = \frac{\binom{n}{k}\tfrac{4}{2^{2n}}\binom{n-1}{\frac{n-1}{2}}^2\left.\binom{\frac{n-1}{2}}{\frac{k-1}{2}}^2/\binom{n-1}{k-1}^2\right.}{\frac{4}{\pi k2^k} \binom{k-1}{\frac{k-1}{2}}} = \tfrac{\pi}{2} n \cdot 2^{k-n}{\textstyle \binom{n-k}{\frac{n-k}{2}}} \cdot 2^{1-n}{\textstyle \binom{n-1}{\frac{n-1}{2}}},$$ where the second identity is verified by expanding all binomial coefficients to factorials. By Stirling’s approximation we have $2^{-m}\binom{m}{m/2} \nearrow \sqrt{\frac{2}{\pi m}}$, meaning that the ratio of the left side to the right side increases to $1$ as $m \to \infty$. Thus $$\frac{\mathbf{W}^{k}[\mathrm{Maj}_n]}{[\rho^k] (\tfrac{2}{\pi} \arcsin \rho)} \nearrow \frac{n}{\sqrt{n-k}\sqrt{n-1}} = (1-\tfrac{k+1}{n} +\tfrac{k}{n^2})^{-1/2},$$ and the right-hand side is at most $1+2k/n$ for $1 \leq k \leq n/2$ (an exercise). $\Box$

Finally, we can deduce the asymptotics \eqref{eqn:maj-asympt-asympt} from this theorem (as you are asked in the exercises):

Corollary 20 Let $k \in {\mathbb N}$ be odd and assume $n = n(k) \geq 2k^2$. Then \begin{align*} \mathbf{W}^{k}(\mathrm{Maj}_n) &= \left(\tfrac{2}{\pi}\right)^{3/2} k^{-3/2} \cdot (1\pm O(1/k)), \\ \mathbf{W}^{>k}(\mathrm{Maj}_n) &= \left(\tfrac{2}{\pi}\right)^{3/2} k^{-1/2} \cdot (1\pm O(1/k)), \end{align*} and hence the Fourier spectrum of $\mathrm{Maj}_n$ is $\epsilon$-concentrated on degree up to $\frac{8}{\pi^3} \epsilon^{-2} + O_{\epsilon}(1)$.

April 6th, 2012 | Tags: majority | Category: All chapter sections, Chapter 5: Majority and threshold functions

### 2 comments to §5.3: The Fourier coefficients of Majority

• Alex Nikolov

I think showing that the fourier coefficient of even size sets is 0 when the function is odd is exercise 1.9, not 1.8.

• Thanks, fixed!

### Recent comments

• Deepak: Cool! That all makes sense.
• Ryan O'Donnell: Thanks on both!
• Ryan O'Donnell: 1. Fixed, thanks 2. Fixed, thanks 3. For the first two occ...
• Avishay Tal: Two small comments regarding the proof of theorem 16. - In ...
• Deepak: A couple of small things: Ex. 42, under equation (2), \pi...
• Ryan O'Donnell: Correct, thanks!
• Tim Black: I think your $j$ should be an $i$ (or vice-versa) in the sen...
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 89, "mathjax_display_tex": 7, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.7545831799507141, "perplexity_flag": "middle"}