Putnam 2013, Problem A-6

Define a function \( w : \mathbb{Z} \times \mathbb{Z} \to \mathbb{Z} \) as follows. For \( |a|, |b| \leq 2 \), let \( w(a, b) \) be as in the table shown; otherwise, let \( w(a, b) = 0 \).

\[
\begin{array}{c|ccccc}
w(a,b) & b=-2 & b=-1 & b=0 & b=1 & b=2 \\
\hline
a=-2 & -1 & -2 & 2 & -2 & -1 \\
a=-1 & -2 & 4 & -4 & 4 & -2 \\
a=0 & 2 & -4 & 12 & -4 & 2 \\
a=1 & -2 & 4 & -4 & 4 & -2 \\
a=2 & -1 & -2 & 2 & -2 & -1 \\
\end{array}
\]

For every finite subset \( S \) of \( \mathbb{Z} \times \mathbb{Z} \), define
\[
A(S) = \sum_{(\mathbf{s}, \mathbf{s}') \in S \times S} w(\mathbf{s} - \mathbf{s}').
\]
Prove that if \( S \) is any finite nonempty subset of \( \mathbb{Z} \times \mathbb{Z} \), then \( A(S) > 0 \). (For example, if \( S = \{(0,1), (0,2), (2,0), (3,1)\} \), then the terms in \( A(S) \) are 12, 12, 12, 12, 4, 4, 0, 0, 0, -1, -1, -2, -2, -4, -4.)

Solution:
(by Harm Derksen) Consider the generating functions

$$f(x,y) = \sum_{(a,b) \in S} x^a y^b,$$
$$g(x,y) = \sum_{(a,b) \in \mathbb{Z}^2} w(a,b) x^a y^b.$$

Then $A(S)$ is the constant coefficient of the Laurent polynomial $h(x,y) = f(x,y)f(x^{-1},y^{-1})g(x,y)$. We may compute this coefficient by averaging over unit circles:

$$(2\pi)^2 A(S) = \int_0^{2\pi} \int_0^{2\pi} h(e^{is}, e^{it}) dt ds$$
$$= \int_0^{2\pi} \int_0^{2\pi} |f(e^{is}, e^{it})|^2 g(e^{is}, e^{it}) dt ds.$$

Consequently, it is enough to check that $g(e^{is}, e^{it})$ is a nonnegative real number for all $s,t \in \mathbb{R}$. But $g(e^{is}, e^{it}) = 16G(\cos s, \cos t)$ for

$$G(z,w) = zw + z^2 + w^2 - z^2 w - zw^2 - z^2 w^2.$$

If $z,w \in [-1,1]$ and $zw \geq 0$, then

$$G(z,w) = zw(1-zw) + z^2(1-w) + w^2(1-z) \geq 0.$$

If $z,w \in [-1,1]$ and $zw \leq 0$, then

$$G(z,w) = (z+w)^2 - zw(1+z)(1+w) \geq 0.$$

Hence $g(e^{is}, e^{it}) \geq 0$ as desired.