# Comparing coefficients of boolean functions

Let a real polynomial representing a boolean function be $P(x_1,\dots,x_n) = \sum_{a\in\{0,1\}^n}c_ax^a = \sum_{a\in\{0,1\}^n}p(a)\prod_{i\in 1_a}x_i\prod_{j\in \bar{1}_a}(1-x_j)$ where $1_a$ is the set of $i$ such that $a_i=1$ and $\bar{1}_a$ is the complement of $1_a$. How do you represent $c_a$ in terms of $p(a)$?

Is for all $b\in\{0,1\}^n$, $c_{b} = \sum_{a\in\{0,1\}^n}(-1)^{<b,a>}p(a)$?

• Have you tried checking this formula for a few functions? – Yuval Filmus Oct 29 '14 at 21:10

Consider the function $P(x_1) = x_1$. Then $P(0) = 0$, $P(1) = 1$, and the polynomial representation is $x_1$, but your formula gives $c_0 = 1$ and $c_1 = -1$. However, if we define $\hat{P}(b) = 2^{-n} \sum_{a \in \{0,1\}^n} (-1)^{\langle a,b \rangle} P(a)$ then $$P(x) = \sum_{b \in \{0,1\}^n} \hat{P}(b) (-1)^{\langle x,b \rangle}.$$ This is known as the Fourier expansion of $P$. To relate this to your expansion, notice that $$(-1)^{\langle x,b \rangle} = \prod_{i\colon b_i=1} (-1)^{x_i} = \prod_{i\colon b_i=1} (1-2x_i).$$ It is now an exercise to relate the coefficients $\hat{P}(b)$ to the coefficients $c_b$ you are interested in.
• Looks like the exact relation $c_b$ is linear but complicated weight by $2^c$ sum of $\hat{P}(b)$. Is there a reference for exact relation? – T.... Oct 30 '14 at 14:18