Putnam 2011, Problem B-5

Let $a_1, a_2, \ldots$ be real numbers. Suppose that there is a constant $A$ such that for all $n$,
$$\int_{-\infty}^{\infty} \left(\sum_{i=1}^{n} \frac{1}{1 + (x - a_i)^2}\right)^2 dx \leq An.$$

Prove there is a constant $B > 0$ such that for all $n$,
$$\sum_{i,j=1}^{n} (1 + (a_i - a_j)^2) \geq Bn^3.$$

Solution:
Define the function  
\[
f(y) = \int_{-\infty}^\infty \frac{dx}{(1 + x^2)(1 + (x + y)^2)}.
\]  
For \(y \geq 0\), in the range \(-1 \leq x \leq 0\), we have  
\[
(1 + x^2)(1 + (x + y)^2) \leq (1 + 1)(1 + (1 + y)^2) = 2y^2 + 4y + 4 \leq 2y^2 + 4 + 2(y^2 + 1) \leq 6 + 6y^2.
\]  
We thus have the lower bound  
\[
f(y) \geq \frac{1}{6(1 + y^2)};
\]  
the same bound is valid for \(y \leq 0\) because \(f(y) = f(-y)\). The original hypothesis can be written as  
\[
\sum_{i,j=1}^n f(a_i - a_j) \leq An
\]  
and thus implies that  
\[
\sum_{i,j=1}^n \frac{1}{1 + (a_i - a_j)^2} \leq 6An.
\]  
By the Cauchy-Schwarz inequality, this implies  
\[
\sum_{i,j=1}^n (1 + (a_i - a_j)^2) \geq Bn^3
\]  
for \(B = 1/(6A)\).  
**Remark.** One can also compute explicitly (using partial fractions, Fourier transforms, or contour integration) that \(f(y) = \frac{2\pi}{4 + y^2}\).  
**Remark.** Praveen Venkataramana points out that the lower bound can be improved to \(Bn^4\) as follows. For each \(z \in \mathbb{Z}\), put \(Q_{z,n} = \{i \in \{1, \dots, n\} : a_i \in [z, z + 1)\}\) and \(q_{z,n} = \#Q_{z,n}\). Then \(\sum_{z \in \mathbb{Z}} q_{z,n} = n\) and  
\[
6An \geq \sum_{i,j=1}^n \frac{1}{1 + (a_i - a_j)^2} \geq \sum_{z \in \mathbb{Z}} \frac{1}{2} q_{z,n}^2.
\]  
If exactly \(k\) of the \(q_{z,n}\) are nonzero, then \(\sum_{z \in \mathbb{Z}} q_{z,n}^2 \geq n^2/k\) by Jensen’s inequality (or various other methods), so we must have \(k \geq n/(6A)\). Then  
\[
\sum_{i,j=1}^n (1 + (a_i - a_j)^2) \geq n^2 + \sum_{i,j=1}^k \max\{0, (|i - j| - 1)^2\} \geq n^2 + \frac{k^4}{6} - \frac{2k^3}{3} + \frac{5k^2}{6} - \frac{k}{3}.
\]  
This is bounded below by \(Bn^4\) for some \(B > 0\).  
In the opposite direction, one can weaken the initial upper bound to \(An^{4/3}\) and still derive a lower bound of \(Bn^3\). The argument is similar.