Solution

CGMO committee seems to like sum-transformations a lot ...

Is this problem related to the positive definiteness of some certain matrix?

Nguyen wrote: Is this problem related to the positive definiteness of some certain matrix? Sure! This is just restating that the matrix with entries $(2^{\vert A \cap B\vert})_{A,B}$ is positive-(semi)definite. But as such, this is just a restatement of the problem and not yet very helpful.

Got literally the same solution. The idea is that $2^{|A \cap B|}$ is just size of $P(A \cap B)$, so we might want to rearrange the sigmas: \begin{align*} \sum_{A, B \in P(S)}f(A)f(B)2^{|A \cap B|} &= \sum_{A, B \in P(S)}\sum_{T \subseteq (A \cap B)}f(A)f(B) \\ &= \sum_{T \subseteq S}\sum_{T \subseteq A, B \subseteq S}f(A)f(B) \\ &= \sum_{T \subseteq S} \left( \sum_{T \subseteq A \subseteq S}f(A) \right)^2 \ge 0. \end{align*}The equality holds iff $f \equiv 0$, this can be proven inductively.

In fact the number "2‘’ can be replaced with any constant c no less than 1.

Tintarn wrote: Nguyen wrote: Is this problem related to the positive definiteness of some certain matrix? Sure! This is just restating that the matrix with entries $(2^{\vert A \cap B\vert})_{A,B}$ is positive-(semi)definite. But as such, this is just a restatement of the problem and not yet very helpful. I suddenly got it! Let A be a 2^n by 2^n matrix, whose rows and columns are indexed by all subsets of S. Each entry is 1 if the index of the row is a subset of the index of the column, and 0 otherwise. Then the matrix that we want to prove to be positive definite is exactly A(T)*A.