Increasing order of fourier coefficients on the boolean cube

65 Views Asked by At

Given a function $f:\{0,1\}^n\rightarrow \{0,1\}$, is it true that for any $S,T\subseteq[n]$, such that $S\cap T =\phi$, then $\hat{f}(S\cup T)\leq \hat{f}(S)$? It seems so to me cause, if if you just write out the fourier expansion of the former and just upper bound the negative terms corresponding to the T, by replacing them with 1, you get the RHS. But the statement overallseems counterintuitive to me, cause it seems like $\hat{f}(\phi)$ is the largest then for $any$ boolean function.

1

There are 1 best solutions below

0
On

Take the Majority function on 3-bits as an example it is not true. $\widehat{Maj}({1})\leq \widehat{Maj}({1,2,3})$.