Disclosure: I have asked this question on MSE (https://math.stackexchange.com/questions/4895621/maximal-sum-of-a-function-such-that-the-sum-is-bounded-on-product-sets) but received no comments in a week. If you know a better suited tag please let me know and I will attach it to the question.
The formal problem is listed below (copied from MSE):
Let $n \in \mathbb{N}$ and $f: [n] \times [n] \to \mathbb{R}$ such that
- $\sum_{x,y \in [n]} f(x,y) = 0$, and
- $\left|\sum_{x \in S, y \in S'} f(x,y) \right|\le 1$ for all $S,S' \subseteq [n]$.
What is the maximum value the expression $$ \sum_{(x,y) \in T} f(x,y) $$ can take for an arbitrary subset $T\subseteq [n]\times [n]$?
My intuition is that the optimal $T$ likely diagonal since it is far from product sets. For $n=1$ the answer is trivially $0$. For $n=2$, it is also easy to see that the answer is $2$, achieved by the function $$ f(x,y) = \begin{cases} 1, x=y \\ -1, x \ne y \end{cases}. $$ and $T = \{(0,0),(1,1)\}$. I also see that the answer is monotone in $n$. The example does not seem to generalize to $n>2$ in a trivial way, and I wasn't able to find good references for this problem. A non-trivial upper-bound would also be useful. Thank you.
