Putnam 2004, Problem A-6

Suppose that $f(x,y)$ is a continuous real-valued function on the unit square $0 \leq x \leq 1, 0 \leq y \leq 1$. Show that
\[
\int_0^1 \left( \int_0^1 f(x,y) dx \right)^2 dy + \int_0^1 \left( \int_0^1 f(x,y) dy \right)^2 dx \leq \left( \int_0^1 \int_0^1 f(x,y) dx dy \right)^2 + \int_0^1 \int_0^1 [f(x,y)]^2 dx dy.
\]

Solution:
By approximating each integral with a Riemann sum, we may reduce to proving the discrete analogue: for $x_{ij} \in \mathbb{R}$ for $i,j = 1, \ldots, n$,
$$n \sum_{i=1}^n \left( \sum_{j=1}^n x_{ij} \right)^2 + n \sum_{j=1}^n \left( \sum_{i=1}^n x_{ij} \right)^2$$
$$\leq \left( \sum_{i=1}^n \sum_{j=1}^n x_{ij} \right)^2 + n^2 \sum_{i=1}^n \sum_{j=1}^n x_{ij}^2.$$

The difference between the right side and the left side is
$$\frac{1}{4} \sum_{i,j,k,l=1}^n (x_{ij} + x_{kl} - x_{il} - x_{kj})^2,$$
which is evidently nonnegative. If you prefer not to discretize, you may rewrite the original inequality as
$$\int_0^1 \int_0^1 \int_0^1 \int_0^1 F(x,y,z,w)^2 dxdydzdw \geq 0$$
for
$$F(x,y,z,w) = f(x,y) + f(z,w) - f(x,w) - f(z,y).$$

**Remark:** (by Po-Ning Chen) The discrete inequality can be arrived at more systematically by repeatedly applying the following identity: for any real $a_1, \ldots, a_n$,
$$\sum_{1 \leq i < j \leq n} (x_i - x_j)^2 = n \sum_{i=1}^n x_i^2 - \left( \sum_{i=1}^n x_i \right)^2.$$

**Remark:** (by David Savitt) The discrete inequality can also be interpreted as follows. For $c,d \in \{1, \ldots, n-1\}$ and $\zeta_n = e^{2\pi i/n}$, put
$$z_{c,d} = \sum_{i,j} \zeta_n^{ci+dj} x_{ij}.$$

Then the given inequality is equivalent to
$$\sum_{c,d=1}^{n-1} |z_{c,d}|^2 \geq 0.$$