8
$\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$
0

1 Answer 1

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$
5
  • $\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$ Jan 8, 2017 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$ Jan 8, 2017 at 19:15
  • $\begingroup$ Oh right, duh. Sorry for the silly confusion. Very good. $\endgroup$ Jan 8, 2017 at 21:32
  • $\begingroup$ No problem. I've stopped counting how many mistakes I've made on this site. $\endgroup$ Jan 9, 2017 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$ Jan 14, 2017 at 22:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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