What is the degree of the fourier expansion

Question

Let $ f:\{-1,1\}^3 \rightarrow \{-1,1\} $ , $f(x)= \operatorname{sgn}(x_1+x_2+x_3)$; (Majority function), then Fourier expansion of $f$ is $f(x)= \frac{1}{2} x_1+\frac{1}{2}x_2+\frac{1}{2}x_3-\frac{1}{2}x_1x_2x_3$; has degree $3$. What is the degree of the Fourier expansion of $ f:\{-1,1\}^n \rightarrow \{-1,1\} $, $f(x)=\operatorname{sgn}(x_1+x_2+\cdots+x_n)$ ($n$ is odd). Is the degree is $n$ or less than $n$ ? Thank You.

Answer 1

The degree is always equal to $n$. More precisely, the coefficient of $x_1\dots x_n$ in the Fourier-Walsh expansion is equal to $$\frac{(-1)^{k-1}\binom{2k-1}{k}k}{4^{k-1}(2k-1)}$$ where $n=2k-1$.

Proof. Let $L_n$ be the (unique) polynomial of degree at most $n$ such that $L_n(2j-n)=\operatorname{sgn}(2j-n)$ for $j=0,\dots,n$. I don't know if these polynomials have a name: the interpolation problem looks fairly natural. Here is $L_9$ and the signum function for comparison: they agree at odd integers.

Clearly, $f(x)=L_n(x_1+\dots+x_n)$ for all $x_1,\dots,x_n\in \{-1,1\}$. From this representation you get the Fourier expansion simply by reducing all exponents mod $2$. For example, $L_3(x)=\frac{-1}{12}x^3+\frac{13}{12}x$, and after expanding and cleaning up $L_3(x_1+x_2+x_3)$ we arrive at $$\begin{align} &\frac{-1}{12}\Big(x_1^3+x_2^3+x_3^3 +3(x_1x_2^2+x_1x_3^2+x_2x_1^2+x_2x_3^2+x_3x_1^2+x_3x_2^2)+6x_1x_2x_3\Big)+\frac{13}{12}(x_1+x_2+x_3) \\ &= \frac{-1}{12}\Big(x_1+x_2+x_3 +3(2x_1+2x_2+2x_3)+6x_1x_2x_3\Big)+\frac{13}{12}(x_1+x_2+x_3) \\ &= -\frac{1}{2}x_1x_2x_3 +\frac12 (x_1+x_2+x_3) \end{align}$$ The only way to get $x_1 \dots x_n$ via this process is from the expansion of $(x_1+\dots+x_n)^n$, which yields $n!\,x_1\dots x_n$. Thus, the coefficient of $x_1\dots x_n$ in the Fourier expansion is $n!\,c_n$ where $c_n$ is the leading coefficient of $L_n$.

Presumably, there is a quick way to see that $c_n\ne 0$, i.e., the degree of $L_n$ is indeed $n$. But just for fun, I'm going to compute $c_n$ precisely. By the Lagrange interpolation formula, $$\begin{align} L_n(x) &= \sum_{j=0}^n \operatorname{sgn}(2j-n)\prod_{0\le i\le n, i\ne j}\frac{x-(2i-n)}{(2j-n)-(2i-n)} \\ &= 2^{1-n}\sum_{j=0}^n \operatorname{sgn}(2j-n)\prod_{0\le i\le n, i\ne j}\frac{x-(2i-n)}{j-i} \end{align}\tag{1}$$ Therefore, $$\begin{align} c_n &= 2^{1-n}\sum_{j=0}^n \operatorname{sgn}(2j-n)\prod_{0\le i\le n, i\ne j}\frac{1}{j-i} \\ &= -2^{1-n}\sum_{j=0}^{k-1} \prod_{0\le i\le n, i\ne j}\frac{1}{j-i} \\ \end{align}\tag{2}$$ where the last step is based on the fact that the reflection $j\mapsto n-j$ changes the sign of $\prod_{0\le i\le n, i\ne j}(j-i)$. Since $$\prod_{0\le i\le n, i\ne j}(j-i) = (-1)^{n-j} j! (n-j)!\tag{3}$$ it follows that $$\begin{align} n!\, c_n &= -2^{1-n}\sum_{j=0}^{k-1} (-1)^{n-j} \binom{n}{j} \\ &= -2^{2-2k}\sum_{j=0}^{k-1} (-1)^{2k-1-j} \binom{2k-1}{j} \\ &= 4^{1-k}\sum_{j=0}^{k-1} (-1)^{j} \binom{n}{j} \\ \end{align}\tag{4}$$ Since Maple 16 is a better combinatorialist than me, I trust it when it says $$ \sum_{j=0}^{k-1} (-1)^{j} \binom{n}{j} = (-1)^{k-1} \frac{k}{2k-1} \binom{2k-1}{k}\tag{5}$$ Hence $$n!\,c_n=\frac{(-1)^{k-1}\binom{2k-1}{k}k}{4^{k-1}(2k-1)}\tag{6}$$ as claimed. $\Box$