2
$\begingroup$

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).

|cite|improve this question
$\endgroup$
  • $\begingroup$ The nice thing about the XOR basis is that it's automatically orthogonal. You don't get that with AND. $\endgroup$ – Aryeh Apr 10 '18 at 21:48
  • 3
    $\begingroup$ 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. $\endgroup$ – Robin Kothari Apr 10 '18 at 22:07
2
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Clement C. Apr 11 '18 at 22:45
  • $\begingroup$ 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. $\endgroup$ – kodlu Apr 11 '18 at 22:53
  • $\begingroup$ 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." $\endgroup$ – Clement C. Apr 11 '18 at 23:41
  • $\begingroup$ Yes, that's essentially correct, the two bases are related linearly after all. $\endgroup$ – kodlu Apr 12 '18 at 0:02
  • $\begingroup$ But in that case, isn't the expression for the "new AND-Fourier coefficients" featured in your answer incorrect? $\endgroup$ – Clement C. Apr 12 '18 at 16:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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