# How prove this inequality $\sum_{i=1}^{m} \sum_{j=1}^{m}|A_i|\cdot |A_i \cap A_j|\geq \frac{1}{mn}\left(\sum_{i=1}^{m}|A_i|\right)^3$

Let $A_1,A_2,\cdots,A_m$ be $m$ subsets of the set of size $n$ . Prove that $$\sum_{i=1}^{m} \sum_{j=1}^{m}|A_i|\cdot |A_i \cap A_j|\geq \frac{1}{mn}\left(\sum_{i=1}^{m}|A_i|\right)^3.$$

Someone know what this inequality background? The article studies such problems? Thank you.

Idea: it seem this inequality with The sum can be written in terms of indicator functions as solve it? How to it?

Hint. Let $\{1,2,\dots,n\}$ be the given set of size $n$ and let $X_k:=\{i:k\in A_i\}$ for $k=1,\dots,n$. Then show that $$\sum_{i=1}^{m} \sum_{j=1}^{m}|A_i|\cdot |A_i\cap A_j|=\sum_{i=1}^{m}\sum_{k\in A_i}|A_i||X_k|=\sum_{k=1}^{n}\sum_{i\in X_k}|A_i||X_k|.$$ Finally, the conclusion follows by Hölder's inequality with three functions, $$\underbrace{\left(\sum_{i=1}^{m} \sum_{k\in A_i}\frac{1}{|A_i|}\right)}_{m}\cdot\underbrace{\left(\sum_{k=1}^{n}\sum_{i\in X_k}\frac{1}{|X_k|}\right)}_n\cdot\underbrace{\left(\sum_{i=1}^{m} \sum_{k\in A_i}|A_i||X_k|\right)}_{\sum_{i=1}^{m} \sum_{j=1}^{m}|A_i|\cdot |A_i\cap A_j|}\geq \underbrace{\left(\sum_{i=1}^{m} \sum_{k\in A_i}1\right)^3}_{\left(\sum_{i=1}^{m}|A_i|\right)^3}.$$
• @martycohen Probably by looking at the exponent $3$ on the RHS. Jan 6, 2018 at 18:53
• I am not saying that $|A_{i}\cap A_{j}|=|X_{k}|$... Moreover $\sum_{i=1}^{m}\dfrac{1}{|A_{i}|}\sum_{k\in A_{i}}1=\sum_{i=1}^{m}\dfrac{|A_i|}{|A_{i}|}=m$. Jan 7, 2018 at 16:26