A Special Property of Finite Probability Space. My friend asked me this question (which he did not know the solution to).
QUESTION: Let $(\Omega, 2^\Omega, P)$ be a finite probability space.
Let $f_1,\ldots, f_k\in \mathbb F_2[x_1,\ldots, x_n]$ be $k$ polynomials. Suppose there exist real numbers $c_1,\ldots, c_k$ such that
$$
\sum_{i=1}^k c_iP(f_i(A_1,\ldots, A_n))\geq 0
$$
whenever each $A_i$ is chosen to be either $\Omega$ or $\emptyset$.
Then the above equation holds no matter what the events $A_i$'s are chosen to be.
I am quite stumped here. Can somebody see what to do?
Clarification:
To clarify what is meant by $f_i(A_1,\ldots, A_k)$:
First, given two events $A$ and $B$ in $\Omega$, we write $A+B$ to mean $A\cup B$ and $AB$ to mean $A\cap B$. Now suppose, for example, we have $f=x_1x_2+x_3^2x_4\in \mathbb F_2[x_1, \ldots, x_4]$, then $$
f(A_1, \ldots, A_4)=(A_1A_2)+(A_3A_3A_4)=(A_1\cap A_2)\cup (A_3\cap A_4)
$$
 A: It turns out that your question is more a question of Linear Algebra than anything else. 
What we are doing is to associate to each monomial $x_1^{k_1} \cdots x_n^{k_n}$ the map $\chi_{A_1}^{k_1} \cdots \chi_{A_n}^{k_n}$, where the powers do not matter (it matters only if $k_i = 0$ or $k_i \neq 0$) since $\chi_{A_i}$ only attains the values $0,1$.
This means the resulting function can always be written in the form
$$
\sum_I \alpha_I \chi_{A_I},
$$
where the sum runs over multiindices $I \in \{0,1\}^n$ with $\alpha_I \in \Bbb{R}$ and $$\chi_{A_I}:= \prod_{j=1}^n \chi_{A_j}^{I_j}.$$
I now claim that
$$\chi_{A_I} \in {\rm span}(\chi_{A_1^{\varepsilon_1}} \cdots \chi_{A_n^{\varepsilon_n}} \mid \varepsilon_1, \dots, \varepsilon_n \in \{0,1\}) =: V \quad \forall I \in \{0,1\}^n, \quad (\dagger)$$
where we define $A_i^0 := A_i^c$ and $A_i^1 := A_i$.
This is shown by induction on $n \in \Bbb{N}$. For $n=1$, the claim is clear, since


*

*For $I = 0$, we have $\chi_{A_I} \equiv 1 = \chi_{A_1} + \chi_{A_1^c}$.

*For $I = 1$, we have $\chi_{A_I} = \chi_{A_1}$.
If $(\dagger)$ is true for some $n \in \Bbb{N}$, then for $I \in \{0,1\}^{n+1}$, there are two cases:


*

*$I_{n+1} = 0$. In this case, $\chi_{A_I} = \chi_{A_J}$, where $J = I|_{\{1, \dots, n\}}$ is the "truncated" multiindex. But the induction hypothesis yields $\chi_{A_J} = \sum_\varepsilon \alpha_\varepsilon \chi_{A_1^{\varepsilon_1}} \cdots \chi_{A_n^{\varepsilon_n}}$ for suitable coefficients $\alpha_\varepsilon$. Hence,
$$
\chi_{A_J} = \sum_\varepsilon \alpha_\varepsilon [\chi_{A_1^{\varepsilon_1}} \cdots \chi_{A_n^{\varepsilon_n}} (\chi_{A_{n+1}}  + \chi_{A_{n+1}^c})].
$$
Using distributivity, this yields $\chi_{A_I} \in V$.

*$I_{n+1} = 1$. Take $J$ as in the first case and note that
$$
\chi_{A_I} = \chi_{A_J}  \cdot \chi_{A_{n+1}}= \sum_\varepsilon \alpha_\varepsilon \chi_{A_1^{\varepsilon_1}} \cdots \chi_{A_n^{\varepsilon_n}} \chi_{A_{n+1}} \in V
$$
All in all, this shows that we can write
$$
g := \sum c_i f_i (A_1, \dots, A_n) = \sum_{\varepsilon \in \{0,1\}^n} \alpha_\varepsilon \chi_{A_1^{\varepsilon_1}} \cdots \chi_{A_n^{\varepsilon_n}}
$$
for suitable coefficients $\alpha_\varepsilon \in \Bbb{R}$.
I claim that your hypothesis yields $\alpha_\varepsilon \geq 0$ for all $\varepsilon$.
Here, we use the fact that plugging in suitable $A_i \in \{\emptyset, \Omega\}$ and integrating yields a dual basis to the $\chi_{A_1^{\varepsilon_1}} \cdots A_n^{\varepsilon_n}$.
To see this, let $\varepsilon \in \{0,1\}^n$ be arbitrary. Set $A_i := \emptyset$ if $\varepsilon_i = 0$ and $A_i := \Omega$ if $\varepsilon_i = 1$. Then $\chi_{A_1^{\varepsilon_1}} \cdots \chi_{A_n^{\varepsilon_n}} \equiv 1$, but $\chi_{A_1^{\gamma_1}} \cdots \chi_{A_n^{\gamma_n}} \equiv 0$ for $\gamma \in \{0,1\}^n$ with $\gamma \neq \varepsilon$. Hence,
$$
0 \leq  \sum c_i P(f(A_1, \dots, A_n)) =\int g \, dP = \alpha_\varepsilon.
$$
With this, it is easy to see that the sum is positive for any choice of $A_1, \dots, A_n$.
