<p>Yes.</p>

<blockquote>
  <p>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$.</p>
</blockquote>

<p><em>proof:</em> 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:</p>

<blockquote>
  <p>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.</p>
</blockquote>

<p><em>proof:</em> 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} &amp;:&amp; x_i = 1\\ \frac{1-a_i}{2} &amp;:&amp; 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$.</p>

CC BY-SA 3.0
2017-01-08T18:37:03.813Z
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...
Joshua Grochow
CC BY-SA 3.0
2017-01-08T19:15:33.000Z
@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$.
Andrew Morgan
CC BY-SA 3.0
2017-01-08T21:32:37.060Z
Oh right, duh. Sorry for the silly confusion. Very good.
Joshua Grochow
CC BY-SA 3.0
2017-01-09T06:55:53.930Z
No problem. I've stopped counting how many mistakes I've made on this site.
Andrew Morgan
CC BY-SA 3.0
2017-01-14T22:00:20.947Z
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$.
Yuval Filmus
CC BY-SA 3.0
2017-01-07T21:17:36.393Z
2017-01-08T13:55:46.090Z
2017-01-08T13:55:46.090Z
Andrew Morgan
<p>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?</p>

<boolean-functions><fourier-analysis><monotone>
Is a monotone boolean function monotone as a multilinear polynomial?
user43879
# Is a monotone boolean function monotone as a multilinear polynomial?

(Asked by: username_0 on 2017-01-07)

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?

**Tags:** boolean-functions, fourier-analysis, monotone


---

## 1 answers

### Answer by username_1 on 2017-01-07. Score: 6

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

> **Comments:**
> **username_2**: 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...  
> **username_1**: @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$.  
> **username_2**: Oh right, duh. Sorry for the silly confusion. Very good.  
> **username_1**: No problem. I've stopped counting how many mistakes I've made on this site.  
> **username_3**: 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$.  

---

