Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
atleast an idea is great for me. –  Gold Feb 6 '13 at 17:29
add comment

1 Answer

up vote 0 down vote accepted

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.

9th degree interpolation

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$

share|improve this answer
    
One can simply compute the inner product of $f$ with the monomial, which quickly yields the same alternating sum of binomial coefficients as in (5). The interpolation is not needed, but I think I has some entertainment value. –  user53153 Feb 8 '13 at 14:33
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.