Putnam 2003, Problem B-6

Let \( f(x) \) be a continuous real-valued function defined on the interval \( [0,1] \). Show that
\[
\int_0^1 \int_0^1 |f(x) + f(y)| \, dx \, dy \geq \int_0^1 |f(x)| \, dx.
\]


Solution:
### First solution: (composite of solutions by Feng Xie and David Pritchard)  
Let \( \mu \) denote Lebesgue measure on \( [0,1] \). Define  
\[
E_+ = \{x \in [0,1] : f(x) \geq 0\}, \quad E_- = \{x \in [0,1] : f(x) < 0\};
\]  
then \( E_+, E_- \) are measurable and \( \mu(E_+) + \mu(E_-) = 1 \). Write \( \mu_+ \) and \( \mu_- \) for \( \mu(E_+) \) and \( \mu(E_-) \). Also define  
\[
I_+ = \int_{E_+} |f(x)| dx, \quad I_- = \int_{E_-} |f(x)| dx,
\]  
so that \( \int_0^1 |f(x)| dx = I_+ + I_- \).  

From the triangle inequality \( |a + b| \geq \pm(|a| - |b|) \), we have the inequality  
\[
\iint_{E_+ \times E_-} |f(x) + f(y)| dx dy \geq \pm \iint_{E_+ \times E_-} (|f(x)| - |f(y)|) dx dy = \pm(\mu_- I_+ - \mu_+ I_-),
\]  
and likewise with \( + \) and \( - \) switched. Adding these inequalities together and allowing all possible choices of the signs, we get  
\[
\iint_{(E_+ \times E_-) \cup (E_- \times E_+)} |f(x) + f(y)| dx dy \geq \max\{0, 2(\mu_- I_+ - \mu_+ I_-), 2(\mu_+ I_- - \mu_- I_+)\}.
\]  

To this inequality, we add the equalities  
\[
\iint_{E_+ \times E_+} |f(x) + f(y)| dx dy = 2\mu_+ I_+, \quad \iint_{E_- \times E_-} |f(x) + f(y)| dx dy = 2\mu_- I_-, \quad -\int_0^1 |f(x)| dx = -(\mu_+ + \mu_-)(I_+ + I_-)
\]  
to obtain  
\[
\int_0^1 \int_0^1 |f(x) + f(y)| dx dy - \int_0^1 |f(x)| dx \geq \max\{(\mu_+ - \mu_-)(I_+ + I_-) + 2\mu_- (I_- - I_+), (\mu_+ - \mu_-)(I_+ - I_-), (\mu_- - \mu_+)(I_+ + I_-) + 2\mu_+ (I_- - I_+)\}.
\]  

Now simply note that for each of the possible comparisons between \( \mu_+ \) and \( \mu_- \), and between \( I_+ \) and \( I_- \), one of the three terms above is manifestly nonnegative. This yields the desired result.  


### Second solution:  
We will show at the end that it is enough to prove a discrete analogue: if \( x_1, \ldots, x_n \) are real numbers, then  
\[
\frac{1}{n^2} \sum_{i,j=1}^n |x_i + x_j| \geq \frac{1}{n} \sum_{i=1}^n |x_i|.
\]  
In the meantime, we concentrate on this assertion.  

Let \( f(x_1, \ldots, x_n) \) denote the difference between the two sides. We induct on the number of nonzero values of \( |x_i| \). We leave for later the base case, where there is at most one such value. Suppose instead for now that there are two or more. Let \( s \) be the smallest, and suppose without loss of generality that \( x_1 = \cdots = x_a = s \), \( x_{a+1} = \cdots = x_{a+b} = -s \), and for \( i > a + b \), either \( x_i = 0 \) or \( |x_i| > s \). (One of \( a,b \) might be zero.)  

Now consider  
\[
f( t, \ldots, t, -t, \ldots, -t, x_{a+b+1}, \ldots, x_n )
\]  
as a function of \( t \). It is piecewise linear near \( s \); in fact, it is linear between 0 and the smallest nonzero value among \( |x_{a+b+1}|, \ldots, |x_n| \) (which exists by hypothesis). Thus its minimum is achieved by one (or both) of those two endpoints. In other words, we can reduce the number of distinct nonzero absolute values among the \( x_i \) without increasing \( f \). This yields the induction, pending verification of the base case.  

As for the base case, suppose that \( x_1 = \cdots = x_a = s > 0 \), \( x_{a+1} = \cdots = x_{a+b} = -s \), and \( x_{a+b+1} = \cdots = x_n = 0 \). (Here one or even both of \( a,b \) could be zero, though the latter case is trivial.) Then  
\[
f(x_1, \ldots, x_n) = \frac{s}{n^2} (2a^2 + 2b^2 + (a + b)(n - a - b)) - \frac{s}{n} (a + b) = \frac{s}{n^2} (a^2 - 2ab + b^2) \geq 0.
\]  
This proves the base case of the induction, completing the solution of the discrete analogue.  

To deduce the original statement from the discrete analogue, approximate both integrals by equally-spaced Riemann sums and take limits. This works because given a continuous function on a product of closed intervals, any sequence of Riemann sums with mesh size tending to zero converges to the integral. (The domain is compact, so the function is uniformly continuous. Hence for any \( \varepsilon > 0 \) there is a cutoff below which any mesh size forces the discrepancy between the Riemann sum and the integral to be less than \( \varepsilon \).)  

**Alternate derivation (based on a solution by Dan Bernstein):** From the discrete analogue, we have  
\[
\sum_{1 \leq i < j \leq n} |f(x_i) + f(x_j)| \geq \frac{n - 2}{2} \sum_{i=1}^n |f(x_i)|,
\]  
for all \( x_1, \ldots, x_n \in [0,1] \). Integrating both sides as \( (x_1, \ldots, x_n) \) runs over \( [0,1]^n \) yields  
\[
\frac{n(n - 1)}{2} \int_0^1 \int_0^1 |f(x) + f(y)| dy dx \geq \frac{n - 2}{2} \int_0^1 |f(x)| dx,
\]  
or  
\[
\int_0^1 \int_0^1 |f(x) + f(y)| dy dx \geq \frac{n - 2}{n - 1} \int_0^1 |f(x)| dx.
\]  
Taking the limit as \( n \to \infty \) now yields the desired result.  


### Third solution: (by David Savitt)  
We give an argument which yields the following improved result. Let \( \mu_p \) and \( \mu_n \) be the measure of the sets \( \{x : f(x) > 0\} \) and \( \{x : f(x) < 0\} \) respectively, and let \( \mu \leq 1/2 \) be \( \min(\mu_p, \mu_n) \). Then  
\[
\int_0^1 \int_0^1 |f(x) + f(y)| dx dy \geq (1 + (1 - 2\mu)^2) \int_0^1 |f(x)| dx.
\]  

**Note:** The constant can be seen to be best possible by considering a sequence of functions tending towards the step function which is 1 on \( [0,\mu] \) and -1 on \( (\mu,1] \).  

Suppose without loss of generality that \( \mu = \mu_p \). As in the second solution, it suffices to prove a strengthened discrete analogue, namely  
\[
\frac{1}{n^2} \sum_{i,j} |a_i + a_j| \geq \left( 1 + \left( 1 - \frac{2p}{n} \right)^2 \right) \left( \frac{1}{n} \sum_{i=1}^n |a_i| \right),
\]  
where \( p \leq n/2 \) is the number of \( a_1, \ldots, a_n \) which are positive. (We need only make sure to choose meshes so that \( p/n \to \mu \) as \( n \to \infty \).) An equivalent inequality is  
\[
\sum_{1 \leq i < j \leq n} |a_i + a_j| \geq \left( n - 1 - 2p + \frac{2p^2}{n} \right) \sum_{i=1}^n |a_i|.
\]  

Write \( r_i = |a_i| \), and assume without loss of generality that \( r_i \geq r_{i+1} \) for each \( i \). Then for \( i < j \), \( |a_i + a_j| = r_i + r_j \) if \( a_i \) and \( a_j \) have the same sign, and is \( r_i - r_j \) if they have opposite signs. The left-hand side is therefore equal to  
\[
\sum_{i=1}^n (n - i) r_i + \sum_{j=1}^n r_j C_j,
\]  
where  
\[
C_j = \#\{i < j : \text{sgn}(a_i) = \text{sgn}(a_j)\} - \#\{i < j : \text{sgn}(a_i) \neq \text{sgn}(a_j)\}.
\]  

Consider the partial sum \( P_k = \sum_{j=1}^k C_j \). If exactly \( p_k \) of \( a_1, \ldots, a_k \) are positive, then this sum is equal to  
\[
\binom{p_k}{2} + \binom{k - p_k}{2} - \left[ \binom{p_k}{2} - \binom{k - p_k}{2} \right],
\]  
which expands and simplifies to  
\[
-2p_k(k - p_k) + \binom{k}{2}.
\]  
For \( k \leq 2p \) even, this partial sum would be minimized with \( p_k = k/2 \), and would then equal \( -k/2 \); for \( k < 2p \) odd, this partial sum would be minimized with \( p_k = (k \pm 1)/2 \), and would then equal \( -(k - 1)/2 \). Either way, \( P_k \geq -\lfloor k/2 \rfloor \). On the other hand, if \( k > 2p \), then  
\[
-2p_k(k - p_k) + \binom{k}{2} \geq -2p(k - p) + \binom{k}{2}
\]  
since \( p_k \) is at most \( p \). Define \( Q_k \) to be \( -\lfloor k/2 \rfloor \) if \( k \leq 2p \) and \( -2p(k - p) + \binom{k}{2} \) if \( k \geq 2p \), so that \( P_k \geq Q_k \). Note that \( Q_1 = 0 \).  

Partial summation gives  
\[
\sum_{j=1}^n r_j C_j = r_n P_n + \sum_{j=2}^n (r_{j-1} - r_j) P_{j-1} \geq r_n Q_n + \sum_{j=2}^n (r_{j-1} - r_j) Q_{j-1} = \sum_{j=2}^n r_j (Q_j - Q_{j-1}) = -r_2 - r_4 - \cdots - r_{2p} + \sum_{j=2p+1}^n (j - 1 - 2p) r_j.
\]  

It follows that  
\[
\sum_{1 \leq i < j \leq n} |a_i + a_j| = \sum_{i=1}^n (n - i) r_i + \sum_{j=1}^n r_j C_j \geq \sum_{i=1}^{2p} (n - i) r_i + \sum_{i=2p+1}^n (n - i) r_i + \left( -r_2 - r_4 - \cdots - r_{2p} + \sum_{j=2p+1}^n (j - 1 - 2p) r_j \right) = (n - 1 - 2p) \sum_{i=1}^n r_i + \sum_{i=1}^{2p} (2p + 1 - i - [i \text{ even}]) r_i \geq (n - 1 - 2p) \sum_{i=1}^n r_i + p \sum_{i=1}^{2p} r_i \geq (n - 1 - 2p) \sum_{i=1}^n r_i + p \sum_{i=1}^n r_i,
\]  
as desired. The next-to-last and last inequalities each follow from the monotonicity of the \( r_i \)’s, the former by pairing the \( i \)-th term with the \( (2p + 1 - i) \)-th.  

**Note:** Compare the closely related Problem 6 from the 2000 USA Mathematical Olympiad: prove that for any nonnegative real numbers \( a_1, \ldots, a_n, b_1, \ldots, b_n \), one has  
\[
\sum_{i,j=1}^n \min\{a_i a_j, b_i b_j\} \leq \sum_{i,j=1}^n \min\{a_i b_j, a_j b_i\}.
\]