Is a monotone boolean function monotone as a multilinear polynomial?

Question

Let $f:\{-1,1\}^n \rightarrow \{0,1\}$ be a monotonically increasing boolean function. That is, $f(x) \leq f(y)$, if coordinate-wise $x \leq y$. Now, let $F: [-1,1]^n \rightarrow \mathbb{R}$ be $f$ expressed as a multilinear polynomial (i.e. $F$'s Fourier transform). Is $F$ still a monotonically increasing function?

Answer 1

Yes.

Let $f : \{-1,1\}^n \to \mathbb{R}$, and let $F : [-1,1]^n \to \mathbb{R}$ be its multilinear extension. If $f$ is monotone, then so is $F$.

proof: Fix a variable index $i$; we'll show that $\frac{\partial F}{\partial x_i} \ge 0$ at all $x \in [-1,1]^n$. If this holds for all $i$, we're done. Since $F$ is multilinear, we can write this partial derivative as $\frac{1}{2}\left( F\restriction_{x_i=1} - F\restriction_{x_i = -1} \right)$, where $F\restriction_{x_i = a}$ means we assign $a$ to $x_i$ and leave the remaining variables free. So it suffices to show that $F\restriction_{x_i = 1} \ge F\restriction_{x_i = -1}$ for all $x\in [-1,1]^n$. Since $f\restriction_{x_i = 1} \ge f\restriction_{x_i = -1}$ on $\{-1,1\}^n$, and since $F\restriction_{x_i=a}$ is the multilinear extension of $f\restriction_{x_i=a}$, this reduces to the following claim:

Let $f,g : \{-1,1\}^n \to \mathbb{R}$ be functions, and $F,G : [-1,1]^n \to \mathbb{R}$ their respective multilinear extensions. If $f \ge g$ point-wise, then $F \ge G$ point-wise as well.

proof: Recall that if $M$ is a multilinear function, then we can write $$M(a) = \sum_{x \in \{\pm 1\}^n} M(x) \prod_{i=1}^n \left\{\begin{array}{rcl}\frac{1+a_i}{2} &:& x_i = 1\\ \frac{1-a_i}{2} &:& x_i = -1\end{array}\right.$$ From this formula, it directly follows that if $M(x) \ge 0$ for all $x \in \{-1, 1\}^n$, then $M(a) \ge 0$ for all $a \in [-1,1]^n$. The claim then follows by applying this fact to $M = F - G$, since for $x \in \{-1,1\}^n, (F - G)(x) = (f - g)(x) \ge 0$.