<p>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.</p>

CC BY-SA 3.0
2018-04-11T22:45:57.253Z
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.
CC BY-SA 3.0
2018-04-11T22:53:52.657Z
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
CC BY-SA 3.0
2018-04-11T23:41:26.077Z
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.
CC BY-SA 3.0
2018-04-12T00:02:21.013Z
Yes, that's essentially correct, the two bases are related linearly after all.
kodlu
CC BY-SA 3.0
2018-04-12T16:03:15.590Z
But in that case, isn't the expression for the "new AND-Fourier coefficients" featured in your answer incorrect?
Clement C.
CC BY-SA 3.0
2018-04-11T11:52:35.953Z
2018-04-11T22:55:12.763Z
2018-04-11T22:55:12.763Z
kodlu
<p>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]$. </p>

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

CC BY-SA 3.0
2018-04-10T21:48:31.810Z
The nice thing about the XOR basis is that it's automatically orthogonal. You don't get that with AND.
Aryeh
CC BY-SA 3.0
2018-04-10T22:07:21.673Z
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
<boolean-functions><fourier-analysis><boolean-formulas><parity>
Fourier decomposition in terms of another basis
Annonymous
# Fourier decomposition in terms of another basis

(Asked by: username_0 on 2018-04-10)

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

**Tags:** boolean-functions, fourier-analysis, boolean-formulas, parity
> **Comments:**
> **username_1**: The nice thing about the XOR basis is that it's automatically orthogonal. You don't get that with AND.  
> **username_2**: 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.  

---

## 1 answers

### Answer by username_3 on 2018-04-11. Score: 2

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.

> **Comments:**
> **username_4**: 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?  
> **username_3**: 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.  
> **username_4**: 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."  
> **username_3**: Yes, that's essentially correct, the two bases are related linearly after all.  
> **username_4**: But in that case, isn't the expression for the "new AND-Fourier coefficients" featured in your answer incorrect?  

---

