Putnam 2003, Problem B-1

Do there exist polynomials \( a(x), b(x), c(y), d(y) \) such that
\[
1 + xy + x^2y^2 = a(x)c(y) + b(x)d(y)
\]
holds identically?

Solution:
No, there do not.  

### First solution:  
Suppose the contrary. By setting \( y = -1, 0, 1 \) in succession, we see that the polynomials \( 1 - x + x^2 \), \( 1 \), \( 1 + x + x^2 \) are linear combinations of \( a(x) \) and \( b(x) \). But these three polynomials are linearly independent, so cannot all be written as linear combinations of two other polynomials, contradiction.  

**Alternate formulation:** The given equation expresses a diagonal matrix with 1,1,1 and zeroes on the diagonal, which has rank 3, as the sum of two matrices of rank 1. But the rank of a sum of matrices is at most the sum of the ranks of the individual matrices.  


### Second solution:  
It is equivalent (by relabeling and rescaling) to show that \( 1 + xy + x^2 y^2 \) cannot be written as \( a(x)d(y) - b(x)c(y) \). Write \( a(x) = \sum a_i x^i \), \( b(x) = \sum b_i x^i \), \( c(y) = \sum c_j y^j \), \( d(y) = \sum d_j y^j \). We now start comparing coefficients of \( 1 + xy + x^2 y^2 \) and \( a(x)d(y) - b(x)c(y) \), we get  
\[
1 = a_i d_j - b_i c_j \quad (i = 0,1,2), \quad 0 = a_i d_j - b_i c_j \quad (i \neq j).
\]  
The first equation says that \( a_i \) and \( b_i \) cannot both vanish, and \( c_j \) and \( d_j \) cannot both vanish. The second equation says that \( a_i/b_i = c_j/d_j \) when \( i \neq j \), where both sides should be viewed in \( \mathbb{R} \cup \{\infty\} \) (and neither is undetermined if \( i, j \in \{0,1,2\} \)). But then  
\[
\frac{a_0}{b_0} = \frac{c_1}{d_1} = \frac{a_2}{b_2} = \frac{c_0}{d_0}
\]  
contradicting the equation \( a_0 d_0 - b_0 c_0 = 1 \).  


### Third solution:  
We work over the complex numbers, in which we have a primitive cube root \( \omega \) of 1. We also use without further comment unique factorization for polynomials in two variables over a field. And we keep the relabeling of the second solution.  

Suppose the contrary. Since \( 1 + xy + x^2 y^2 = (1 - xy/\omega)(1 - xy/\omega^2) \), the rational function \( a(\omega/y)d(y) - b(\omega/y)c(y) \) must vanish identically (that is, coefficient by coefficient). If one of the polynomials, say \( a \), vanished identically, then one of \( b \) or \( c \) would also, and the desired inequality could not hold. So none of them vanish identically, and we can write  
\[
\frac{c(y)}{d(y)} = \frac{a(\omega/y)}{b(\omega/y)}.
\]  
Likewise,  
\[
\frac{c(y)}{d(y)} = \frac{a(\omega^2/y)}{b(\omega^2/y)}.
\]  
Put \( f(x) = a(x)/b(x) \); then we have \( f(\omega x) = f(x) \) identically. That is, \( a(x)b(\omega x) = b(x)a(\omega x) \). Since \( a \) and \( b \) have no common factor (otherwise \( 1 + xy + x^2 y^2 \) would have a factor divisible only by \( x \), which it doesn’t since it doesn’t vanish identically for any particular \( x \)), \( a(x) \) divides \( a(\omega x) \). Since they have the same degree, they are equal up to scalars. It follows that one of \( a(x) \), \( xa(x) \), \( x^2 a(x) \) is a polynomial in \( x^3 \) alone, and likewise for \( b \) (with the same power of \( x \)).  

If \( xa(x) \) and \( xb(x) \), or \( x^2 a(x) \) and \( x^2 b(x) \), are polynomials in \( x^3 \), then \( a \) and \( b \) are divisible by \( x \), but we know \( a \) and \( b \) have no common factor. Hence \( a(x) \) and \( b(x) \) are polynomials in \( x^3 \). Likewise, \( c(y) \) and \( d(y) \) are polynomials in \( y^3 \). But then \( 1 + xy + x^2 y^2 = a(x)d(y) - b(x)c(y) \) is a polynomial in \( x^3 \) and \( y^3 \), contradiction.  

**Note:** The third solution only works over fields of characteristic not equal to 3, whereas the other two work over arbitrary fields. (In the first solution, one must replace \( -1 \) by another value if working in characteristic 2.)