<p>This is a question that I've been pondering, on and off, for a while, and unsuccessfully. I'd be very interested in any insight regarding this conjecture. (Or rather, these conjectures.)</p>

<p>Recall that, given a Boolean function $f\colon \{-1,1\}^n \to \{-1,1\}$, the Kahn—Kalai—Linial theorem states that
$$\max_{i\in[n]} \operatorname{Inf}_i f \geq \operatorname{Var}[f]\cdot \Omega\!\left(\frac{\log n}{n}\right) \tag{1}
$$
from which we get that, for any <em>monotone</em> Boolean function $f\colon \{-1,1\}^n \to \{-1,1\}$,
$$\max_{i\in[n]} \widehat{f}(i) \geq \operatorname{Var}[f]\cdot \Omega\!\left(\frac{\log n}{n}\right)
= (1-\widehat{f}(0)^2)\cdot \Omega\!\left(\frac{\log n}{n}\right) \tag{2}
$$
(writing $\widehat{f}(i)$ for $\widehat{f}(\{i\})$, $i\in\{0,\dots,n\}$). Moreover, (2) is tight, as shown by considering the $\textsf{Tribes}_n$ function. In particular, this implies that
$$
W^{(0)}[f]+W^{(1)}[f] = \sum_{i=0}^n \widehat{f}(i)^2 = \Omega\!\left(\frac{\log^2 n}{n^2}\right) \tag{3}
$$
for any monotone Boolean function $f\colon \{-1,1\}^n \to \{-1,1\}$, where $W^{(k)}[f] \stackrel{\rm def}{=} \sum_{S: \lvert S\rvert =k} \widehat{f}(S)^2$.</p>

<p>Now, consider <em>two</em> monotone Boolean functions $f,g\colon \{-1,1\}^n \to \{-1,1\}$, and let $h\stackrel{\rm def}{=}fg$ be their parity. It is easy to see that we could have $W^{(0)}[h]+W^{(1)}[h]=0$, e.g. by considering $f,g$ to be two different dictator functions (but in that very specific case, $W^{(2)}[h]=1$). <em>But must there be some non-negligible Fourier mass on the first 3 Fourier levels, then?</em></p>

<blockquote>
  <p>What can we say about $W^{(0)}[h]+W^{(1)}[h]+W^{(2)}[h] = \sum_{S: \lvert S\rvert \leq 2} \widehat{h}(S)^2$?</p>
</blockquote>

<p><strong>Conjecture 1.</strong> For any two monotone Boolean functions $f,g\colon \{-1,1\}^n \to \{-1,1\}$, one must have $W^{(0)}[fg]+W^{(1)}[fg]+W^{(2)}[fg] &gt; 0$.</p>

<p>Actually, I'd be actually inclined to believe the following stronger statement:</p>

<p><strong>Conjecture 2.</strong> For any two monotone Boolean functions $f,g\colon \{-1,1\}^n \to \{-1,1\}$, one must have $W^{(0)}[fg]+W^{(1)}[fg]+W^{(2)}[fg] \geq \frac{1}{\operatorname{poly}(n)}$.</p>

<p><em>Side note:</em> this would have implications about <em>weak learning</em> of the class of "2-monotone" functions, which are exactly those functions obtained as parity or anti-parity of $2$ monotone functions. (See e.g. [BCOST15].) But more importantly, this is a very simple-looking question, that has been nagging at me for way too long.</p>

<hr>

<p>[BCOST15] Eric Blais, Clément L. Canonne, Igor Carboni Oliveira, Rocco A. Servedio, Li-Yang Tan. <em>Learning Circuits with few Negations.</em> APPROX-RANDOM 2015: 512-527</p>

CC BY-SA 3.0
2017-05-14T10:29:27.377Z
Can you shed some light on what https://arxiv.org/pdf/1705.04205.pdf means for this question?
daniello
CC BY-SA 3.0
2017-05-14T12:25:18.403Z
@daniello As far as I can tell, not much, at least in terms of blackbox interpretation of the results. The question above would have applications to weak learning (learning to advantage $1/2+1/\mathrm{poly}(n)$), while the paper you link shows lower bound on *testing* (and a relaxation, parameterized testing). As far as I am aware, there is no direct connection between the two (the general connection is "(strong) learning implies testing").
Clement C.
<boolean-functions><fourier-analysis><monotone>
Fourier spectrum of the parity of two monotone Boolean functions
Clement C.
# Fourier spectrum of the parity of two monotone Boolean functions

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

This is a question that I've been pondering, on and off, for a while, and unsuccessfully. I'd be very interested in any insight regarding this conjecture. (Or rather, these conjectures.)

Recall that, given a Boolean function $f\colon \{-1,1\}^n \to \{-1,1\}$, the Kahn—Kalai—Linial theorem states that
$$\max\_{i\in[n]} \operatorname{Inf}\_i f \geq \operatorname{Var}[f]\cdot \Omega\!\left(\frac{\log n}{n}\right) \tag{1}
$$
from which we get that, for any *monotone* Boolean function $f\colon \{-1,1\}^n \to \{-1,1\}$,
$$\max\_{i\in[n]} \widehat{f}(i) \geq \operatorname{Var}[f]\cdot \Omega\!\left(\frac{\log n}{n}\right)
= (1-\widehat{f}(0)^2)\cdot \Omega\!\left(\frac{\log n}{n}\right) \tag{2}
$$
(writing $\widehat{f}(i)$ for $\widehat{f}(\{i\})$, $i\in\{0,\dots,n\}$). Moreover, (2) is tight, as shown by considering the $\textsf{Tribes}\_n$ function. In particular, this implies that
$$
W^{(0)}[f]+W^{(1)}[f] = \sum\_{i=0}^n \widehat{f}(i)^2 = \Omega\!\left(\frac{\log^2 n}{n^2}\right) \tag{3}
$$
for any monotone Boolean function $f\colon \{-1,1\}^n \to \{-1,1\}$, where $W^{(k)}[f] \stackrel{\rm def}{=} \sum\_{S: \lvert S\rvert =k} \widehat{f}(S)^2$.

Now, consider *two* monotone Boolean functions $f,g\colon \{-1,1\}^n \to \{-1,1\}$, and let $h\stackrel{\rm def}{=}fg$ be their parity. It is easy to see that we could have $W^{(0)}[h]+W^{(1)}[h]=0$, e.g. by considering $f,g$ to be two different dictator functions (but in that very specific case, $W^{(2)}[h]=1$). *But must there be some non-negligible Fourier mass on the first 3 Fourier levels, then?*

> What can we say about $W^{(0)}[h]+W^{(1)}[h]+W^{(2)}[h] = \sum\_{S: \lvert S\rvert \leq 2} \widehat{h}(S)^2$?

**Conjecture 1.** For any two monotone Boolean functions $f,g\colon \{-1,1\}^n \to \{-1,1\}$, one must have $W^{(0)}[fg]+W^{(1)}[fg]+W^{(2)}[fg] > 0$.

Actually, I'd be actually inclined to believe the following stronger statement:

**Conjecture 2.** For any two monotone Boolean functions $f,g\colon \{-1,1\}^n \to \{-1,1\}$, one must have $W^{(0)}[fg]+W^{(1)}[fg]+W^{(2)}[fg] \geq \frac{1}{\operatorname{poly}(n)}$.

*Side note:* this would have implications about *weak learning* of the class of "2-monotone" functions, which are exactly those functions obtained as parity or anti-parity of $2$ monotone functions. (See e.g. [BCOST15].) But more importantly, this is a very simple-looking question, that has been nagging at me for way too long.

---

[BCOST15] Eric Blais, Clément L. Canonne, Igor Carboni Oliveira, Rocco A. Servedio, Li-Yang Tan. *Learning Circuits with few Negations.* APPROX-RANDOM 2015: 512-527

**Tags:** boolean-functions, fourier-analysis, monotone
> **Comments:**
> **username_1**: Can you shed some light on what https://arxiv.org/pdf/1705.04205.pdf means for this question?  
> **username_0**: @daniello As far as I can tell, not much, at least in terms of blackbox interpretation of the results. The question above would have applications to weak learning (learning to advantage $1/2+1/\mathrm{poly}(n)$), while the paper you link shows lower bound on *testing* (and a relaxation, parameterized testing). As far as I am aware, there is no direct connection between the two (the general connection is "(strong) learning implies testing").  

---

## 0 answers

