<p>Let $f:\{-1,1\}^n \rightarrow \{-1,1\}$ be any boolean function. Let $Maj_n$ represent the majority function. Let $\langle f,g \rangle = E[f(x)g(x)]$ and $\mathcal{I}(f) = E_x[\# i, s.t. f(x)\neq f(x \oplus e_i)]$ be the total influence of a function under the standard definitions. Then does the following identity always hold? </p>

<p>$$  \langle f,Maj_n \rangle \leq c*\frac{\mathcal{I}(f)}{\mathcal{I}(Maj_n)} $$</p>

<p>where c is some universal constant. I believe it might be true but have not been able to prove it. I have tried some standard functions and they seem to work. I may be mistaken as I am very new to this area.  Could you please suggest a way to prove it ? or some references regarding this</p>

<p>Thanks in advance</p>

CC BY-SA 3.0
2014-01-07T07:23:29.703Z
I think I can prove a weaker version fairly easily. The weaker version I think works for my application. However proofs of the statement are most welcome.
NAg
CC BY-SA 3.0
2014-01-07T07:27:28.503Z
Can you prove it for a monotone function $f$?
Igor Shinkar
CC BY-SA 3.0
2014-01-15T11:58:44.417Z
Would you have any example where c=1 is not enough?
Joseph Stack
CC BY-SA 3.0
2014-01-26T15:41:26.123Z
To both the above questions I dont think I can do either
NAg
<co.combinatorics><boolean-functions><fourier-analysis>
An identity about the Majority function?
NAg
# An identity about the Majority function?

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

Let $f:\{-1,1\}^n \rightarrow \{-1,1\}$ be any boolean function. Let $Maj\_n$ represent the majority function. Let $\langle f,g \rangle = E[f(x)g(x)]$ and $\mathcal{I}(f) = E\_x[\# i, s.t. f(x)\neq f(x \oplus e\_i)]$ be the total influence of a function under the standard definitions. Then does the following identity always hold?

$$ \langle f,Maj\_n \rangle \leq c\*\frac{\mathcal{I}(f)}{\mathcal{I}(Maj\_n)} $$

where c is some universal constant. I believe it might be true but have not been able to prove it. I have tried some standard functions and they seem to work. I may be mistaken as I am very new to this area. Could you please suggest a way to prove it ? or some references regarding this

Thanks in advance

**Tags:** co.combinatorics, boolean-functions, fourier-analysis
> **Comments:**
> **username_0**: I think I can prove a weaker version fairly easily. The weaker version I think works for my application. However proofs of the statement are most welcome.  
> **username_1**: Can you prove it for a monotone function $f$?  
> **username_2**: Would you have any example where c=1 is not enough?  
> **username_0**: To both the above questions I dont think I can do either  

---

## 0 answers

