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$

Question

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?

Answer 1

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