# How to prove this polynomial expression.

Let the polynomial be in $f$ be a map from $\Bbb{Z}_2^k \to \Bbb{Z}_2$, defined by

$f = 1 + \sum_{i=1}^k x_i + \sum_{i\neq j; i,j = 1}^k x_i x_j + \dots + x_1 x_2 \cdots x_k$

Then I want to show that $f$ can be evaluated in polynomial time in $k$.

For instance. $k= 1$:

$f = 1 + x_1$

For $k = 2$:

$f = 1 + x_1( 1 + x_2)$

$k = 3$:

$f = 1 + x_3 + x_2(x_3 + 1) + x_1(x_3 + x_2(x_3 + 1) + 1) = \\ 1 + E_1 + x_1 (E_1 + 1),$

where $E_1 = x_3 + x_2(x_3 + 1)$

See Wolfram Alpha for $k= 4$ case.

$f = 1 + E_2 + x_2(E_2 + 1), \ \ \ E_2 = \dots$

• Ummm, that expression doesn't work. Do you mean $\sum$ everywhere you wrote $\prod$? For example, $k=2$ gives: $1+x_1x_2 + x_1^2x_2^2$. – Thomas Andrews Apr 19 '14 at 18:43
• @ThomasAndrews that's right – Shine On You Crazy Diamond Apr 19 '14 at 18:50
• Then your formula for $k=2$ is still incorrect. It should be $1+(x_1+x_2)+2x_1x_2$. I suspect you want $i<j$ in the sum $\sum_{i\neq j, i,j=1}^n$, but I'm just guessing. – Thomas Andrews Apr 19 '14 at 18:55
• It looks to me like the question intends to be factored as $(1+x_1)(1+x_2)\dots(1+x_k)$, which has an easy $O(k)$ computation, but I'm just guessing. – Thomas Andrews Apr 19 '14 at 18:57
• @ThomasAndrews thank you! That means it's not the right polynomial I'm after. – Shine On You Crazy Diamond Apr 19 '14 at 22:19