7
$\begingroup$

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?

$\endgroup$
6
$\begingroup$

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$.

$\endgroup$
  • $\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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.