# 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. – Aryeh Apr 10 '18 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. – Robin Kothari Apr 10 '18 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? – Clement C. Apr 11 '18 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. – kodlu Apr 11 '18 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." – Clement C. Apr 11 '18 at 23:41