Prove the Fourier coefficients $c_S$ of $f\colon\mathbb{F}_2^n\to\mathbb{F_2}$ is $\sum_{\operatorname{supp}(x)\subseteq S}f(x)$

Question

Given $n>0$. Suppose $f:\mathbb{F}_2^n\to\mathbb{F_2}$ can be expressed as $f(x)=\sum_{S\subseteq [n]}c_Sx^S \pmod{2}$, where $x=(x_1,\cdots,x_n)^T, c_S\in\mathbb{F}_2,x^S=\prod_{i\in S}x_i$. It is known that this expression exists and is unique. How to prove that $c_S=\sum_{\operatorname{supp}(x)\subseteq S}f(x)$? Here $\operatorname{supp}(x)=\{i:x_i=1\}$.

We only need to verify this: $\forall x,f(x)=\sum_{S\subseteq [n]}\sum_{\operatorname{supp}(y)\subseteq S}f(y)x^S$, which equals $\sum_y\sum_{S:S \text{ contains }\operatorname{supp}(y)}f(y)x^S$, then how to do the next?

Answer 1

Thanks for the comment. I summarize one solution below. \begin{align} &\sum_{S\subseteq [n]}\sum_{\operatorname{supp}(y)\subseteq S}f(y)x^S\\ =&\sum_y f(y)\sum_{S:S \text{ contains }\operatorname{supp}(y)}x^S \end{align}

When $x=y$,$\sum_{S:S \text{ contains }\operatorname{supp}(y)}x^S=x^{\text{supp(x)}}\Pi_{i\in[n]\text{\supp}(x)}(1+x_i)=1$.

When $x\neq y$,$\sum_{S:S \text{ contains }\operatorname{supp}(y)}x^S=x^{\text{supp(y)}}\Pi_{i\in[n]\text{\supp}(y)}(1+x_i)$, then $\exists i\in\operatorname{supp}(y), x_i=0$ or $\exists j\in[n]\text{\supp}(y),x_j=1$ (otherwise $x=y$). So $\sum_{S:S \text{ contains }\operatorname{supp}(y)}x^S=0$.

So $\sum_{S\subseteq [n]}\sum_{\operatorname{supp}(y)\subseteq S}f(y)x^S=f(x)$ and we can conclude the result.