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?
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$.
-
$\begingroup$ Maybe I'm missing something, but if $F$ is multilinear, then isn't $\partial F /\partial x_i$ simply equal to $F|_{x_i = 1}$? And then you get an easy induction on the number of variables... $\endgroup$ – Joshua Grochow Jan 8 '17 at 18:37
-
$\begingroup$ @JoshuaGrochow $F \restriction_{x_i = 1}$, written out as a polynomial in $x$'s, is the coefficient of $x_i$ in $F$ plus the terms in $F$ not involving $x_i$, so that's not quite right. For example, $F(x,y) = 1 + xy$ has derivative wrt $x$ of $y$, but $F\restriction_{x=1}$ is $1+y$. $\endgroup$ – Andrew Morgan Jan 8 '17 at 19:15
-
$\begingroup$ Oh right, duh. Sorry for the silly confusion. Very good. $\endgroup$ – Joshua Grochow Jan 8 '17 at 21:32
-
$\begingroup$ No problem. I've stopped counting how many mistakes I've made on this site. $\endgroup$ – Andrew Morgan Jan 9 '17 at 6:55
-
1$\begingroup$ The formulas simplify somewhat if you take the domain to be $\{0,1\}^n$ rather than $\{-1,1\}^n$. You then get that $M(\vec{a})$ is the average of $M(\vec{x})$, where $x_i=1$ with probability $a_i$. $\endgroup$ – Yuval Filmus Jan 14 '17 at 22:00