What is the degree of the fourier expansion 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.
 A: 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$
