# Fourier decomposition in terms of another basis

Given a Boolean function $f:\{-1,1\}^n\rightarrow \{-1,1\}$, it is well know that the Fourier decomposition of $f$ can be written as $f(x)=\sum_{S\subseteq \{1,\ldots,n\}} \widehat{f}(S) \prod_{i\in S} x_i$ where $\widehat{f}(S)$ are the Fourier coefficients. So the quantity $\prod_{i\in S} x_i$ can be viewed as the parity of $x\in \{-1,1\}^n$ when restricted to $S\subseteq [n]$.

Is there a way to write the Fourier decomposition in terms of the AND of its variables, i.e., is it possible to express every Boolean function $f$ in terms of $f(x)=\sum_{S\subseteq \{1,\ldots,n\}} \widehat{f}(S) AND(x_{S})$? Can this be generalized even further? In general, can any polynomial $p:\{-1,1\}^n\rightarrow \mathbb{R}$ be written in terms of an "AND" decomposition instead of a parity decomposition (in the Fourier sense).

• The nice thing about the XOR basis is that it's automatically orthogonal. You don't get that with AND. Commented Apr 10, 2018 at 21:48
• You can write every function as a linear combination of ANDs of its variables. If you change your variables to being in $\{0,1\}$ instead of $\{-1,1\}$ (this is just a linear transformation), and then simplify the resulting polynomial, you will have written it as a linear combination of ANDs, because each monomial will be the logical AND of all the variables involved in that monomial. Commented Apr 10, 2018 at 22:07

As pointed out in the comments if $u\in \{\pm 1\}$ then $x=x(u) \in \{0,1\}$ where $$x(u)=\frac{1-u}{2},$$ with $x(-1)=1,$ and $x(1)=0.$ This will then yield $$f(x)=2^{n-1}f(0)-\frac{1}{2} \sum_{S \in \{1,\ldots,n\}} \hat{f}(S) \prod_{i \in S} x_i,$$ and if we denote the $\{0,1\}$ valued version of $f$ as $\tilde{f},$ $$\frac{1-\tilde{f}(x)}{2}=2^{n-1}f(0)-\frac{1}{2} \sum_{S \in \{1,\ldots,n\}} \hat{f}(S) \prod_{i \in S} x_i,$$ leading to $$\frac{\tilde{f}(x)}{2}=\frac{1}{2}\left[1+ \sum_{S \in \{1,\ldots,n\}} \hat{f}(S) \prod_{i \in S} x_i\right]-2^{n-1}f(0),$$ or $$\tilde{f}(x)=1-2^{n}f(0)+\sum_{S \in \{1,\ldots,n\}} \hat{f}(S) \prod_{i \in S} x_i,$$ if I haven't made any errors along the way.
• I am not entirely sure about your derivation, but I may be misreading what you did. You start with the "usual" Fourier representation (for $u\in\{-1,1\}^n$) of $f(u) = \sum_{S\subseteq \{1,\dots,n\}}\hat{f}(S) \prod_{i\in S} u_i$, from which you can write, for $x\in\{0,1\}^n$ and slightly abusing notation for $f$, now seen as $f\colon\{0,1\}^n\to\{-1,1\}$, $$f(x) = \sum_{S\subseteq \{1,\dots,n\}}\hat{f}(S) \prod_{i\in S} (2x_i-1)$$ How do you get your first line from expanding this? Commented Apr 11, 2018 at 22:45
• It's a kind of initial value property, so $\sum_{S\subseteq \{1,\ldots,n\}} \hat{f}(S)=f(0),$ but I missed the $f(0),$ thanks. Commented Apr 11, 2018 at 22:53
• Even though (again, I may be making a mistake), expanding $\prod_{i\\in S}(2x_i-1)$ I get $$\sum_{T\subseteq S} (-1)^{|S|-|T|} 2^{|T|}\prod_{i\in T} x_i$$ so the final expansion would look like $$f(x) = \sum_{T\subseteq [n]} \left( 2^{|T|}\sum_{S\supseteq T} (-1)^{|S|-|T|} \hat{f}(S) \right) \prod_{i\in T} x_i$$ (wouldn't it?) While in your answer the "new Fourier coefficients in the AND basis" are basically the same as the "old Fourier coefficients in the parity basis." Commented Apr 11, 2018 at 23:41