El método polinomial: combinatoria via álgebra

La idea central: codificar combinatoria en ceros de polinomios

El método polinomial convierte un problema combinatorio en una pregunta sobre polinomios: existencia de ceros, coeficientes no nulos, o evaluaciones en conjuntos finitos. La traducción es: "existe un objeto con la propiedad $\mathcal{P}$" $\Leftrightarrow$ "existe un punto en $S_1 \times \cdots \times S_n$ donde cierto polinomio $f(x_1,\ldots,x_n)$ es no nulo".

Históricamente, el método emergió de tres fuentes: el Teorema de Chevalley-Warning (1935–36) sobre ceros de sistemas de polinomios sobre campos finitos; el trabajo de Olson sobre sumas cero en grupos abelianos; y la síntesis de Noga Alon en 1999 con el Nullstellensatz Combinatorio, que unificó y potentísimamente generalizó todas las aplicaciones anteriores.

La potencia del método reside en la flexibilidad: se puede trabajar sobre $\mathbb{Z}$, $\mathbb{Q}$, $\mathbb{F}_p$, o cualquier campo, y el polinomio puede codificar colores, diferencias, funciones de grafo, o cualquier estructura discreta. En olimpiadas, el método es típicamente el más elegante cuando el problema tiene una "asimetría de paridad" o cuando la estructura del problema involucra naturalmente evaluaciones en conjuntos de enteros.

El Nullstellensatz Combinatorio de Alon-Tarsi

Sea $f \in \mathbb{F}[x_1, \ldots, x_n]$ un polinomio sobre un campo $\mathbb{F}$. Sean $S_1, \ldots, S_n \subseteq \mathbb{F}$ conjuntos finitos no vacíos. El polinomio "reduce" módulo el ideal generado por $\prod_{s \in S_i}(x_i - s)$ para cada $i$: podemos escribir $f$ como una combinación de estos generadores más un resto $r$ donde el grado en $x_i$ es menor que $|S_i|$ para todo $i$.

Nullstellensatz Combinatorio (Alon, 1999). Sea $f \in \mathbb{F}[x_1,\ldots,x_n]$ y supongamos que el coeficiente del monomio $x_1^{t_1} \cdots x_n^{t_n}$ en $f$ es no nulo, con $t_i = |S_i| - 1$ para todo $i$. Entonces existe $(s_1, \ldots, s_n) \in S_1 \times \cdots \times S_n$ tal que $f(s_1, \ldots, s_n) \ne 0$.

La prueba es elemental: por inducción en $n$ usando el hecho de que un polinomio de grado $< |S|$ no puede anularse en todos los puntos de $S$ a menos que sea el polinomio cero. La clave es la reducción: si $f$ se anula en todo $S_1 \times \cdots \times S_n$, entonces $f$ pertenece al ideal $\langle \prod_{s \in S_i}(x_i - s) : i = 1,\ldots,n \rangle$, pero este ideal no contiene el monomio $x_1^{t_1}\cdots x_n^{t_n}$ de grado exacto $(|S_1|-1,\ldots,|S_n|-1)$, contradicción.

La versión práctica: para aplicar el Nullstellensatz Combinatorio, construimos un polinomio $f$ que "vale 0 cuando no existe el objeto deseado" y verificamos que cierto coeficiente es no nulo. La no-nulidad del coeficiente garantiza la existencia del punto donde $f \ne 0$.

El Teorema de Chevalley-Warning

Teorema de Chevalley-Warning. Sea $\mathbb{F}_q$ el campo con $q = p^k$ elementos ($p$ primo). Sean $f_1, \ldots, f_m \in \mathbb{F}_q[x_1,\ldots,x_n]$ polinomios con $\sum_{i=1}^m \deg f_i < n$. Sea $V = \{x \in \mathbb{F}_q^n : f_1(x) = \cdots = f_m(x) = 0\}$ la variedad de soluciones comunes. Entonces $p \mid |V|$.

En particular, si el sistema tiene al menos una solución (lo cual se garantiza a veces por razones de paridad), tiene al menos $p$ soluciones. El corolario más famoso: si $n > d = \sum \deg f_i$ y el sistema tiene la solución trivial, entonces tiene al menos $p-1$ soluciones no triviales.

Prueba. El número de soluciones es $|V| = \sum_{x \in \mathbb{F}_q^n} \prod_{i=1}^m (1 - f_i(x)^{q-1})$. Usando que $a^{q-1} = 1$ si $a \ne 0$ y $0^{q-1} = 0$ en $\mathbb{F}_q$, el producto vale 1 en los ceros comunes y 0 en otro lugar. Expandiendo y usando que $\sum_{x \in \mathbb{F}_q} x^k = -1$ si $(q-1) \mid k > 0$ y $= 0$ si $(q-1) \nmid k$, y que el grado total de $\prod(1-f_i^{q-1})$ es $< n(q-1)$ (por la hipótesis de grado), se concluye que la suma es $0$ en $\mathbb{F}_p$, es decir $p \mid |V|$.

Aplicación en olimpiadas. El Teorema de Chevalley-Warning resuelve elegantemente problemas del tipo: "Sean $a_1, \ldots, a_n \in \mathbb{Z}$ con $n > d$. Demuestra que existe un subconjunto no vacío $S \subseteq \{1,\ldots,n\}$ tal que $p \mid \sum_{i \in S} a_i$." Para $p$ primo y $n \ge p$: el polinomio $f(x_1,\ldots,x_n) = \sum a_i x_i$ sobre $\mathbb{F}_p$ con la restricción $x_i \in \{0,1\}$ (modelada por $x_i^2 - x_i = 0$) da $|V| \equiv 0 \pmod{p}$. Como la solución $x=0$ existe, hay otra solución $x \ne 0$, que da el subconjunto deseado.

Cauchy-Davenport y sumas de conjuntos

Teorema de Cauchy-Davenport. Sea $p$ primo y $A, B \subseteq \mathbb{Z}_p$ conjuntos no vacíos. Entonces $|A + B| \ge \min(p, |A| + |B| - 1)$, donde $A + B = \{a + b : a \in A, b \in B\}$.

Prueba por el método polinomial. Sea $|A| = m$, $|B| = n$. Queremos mostrar que $|A+B| \ge m+n-1$, es decir que $A+B$ no puede ser demasiado pequeño. Supongamos por contradicción que $|A+B| \le m+n-2$. Sea $C = A+B$ con $|C| \le m+n-2$. Definamos $f(x,y) = \prod_{c \in C}(x+y-c)$. Este polinomio tiene grado $|C| \le m+n-2$.

Por el Nullstellensatz Combinatorio aplicado con $S_1 = A$ y $S_2 = B$ (tamaños $m$ y $n$), si el coeficiente de $x^{m-1}y^{n-1}$ en $f$ es no nulo, existe $(a,b) \in A \times B$ con $f(a,b) \ne 0$, es decir $a + b \notin C$, contradicción con $C = A+B$. El coeficiente de $x^{m-1}y^{n-1}$ en $f = \prod_{c \in C}(x+y-c)$ es $\binom{m+n-2}{m-1} \ne 0$ en $\mathbb{Z}_p$ (pues $m+n-2 < p$). Contradicción.

El Teorema de Olson (versión multidimensional): Sea $p$ primo y $A_1, \ldots, A_d \subseteq \mathbb{Z}_p^d$ conjuntos con $|A_i| = k_i$. Si $\prod k_i > p^{d-1}$ entonces $A_1 + \cdots + A_d = \mathbb{Z}_p^d$. Esto sigue del Nullstellensatz Combinatorio aplicado con el polinomio $\prod_{j=1}^d (\sum_{i} x_{i,j} - c_j)$ para cada objetivo $c = (c_1,\ldots,c_d)$.

En IMO Shortlist, el método polinomial aparece típicamente en problemas de combinatoria sobre sumas, coloraciones de grafos (número cromático), y existencia de subconjuntos con propiedades algebraicas. La señal de alarma es: el enunciado involucra un primo $p$, una cota numérica que parece "casi mágica" (del tipo $n \ge p$ o $n > d$), y pide existencia de una selección o subconjunto.

Coloraciones de grafos: el Alon-Tarsi y listas de coloración

Una de las aplicaciones más espectaculares del método polinomial es la demostración polinomial del Teorema de Alon-Tarsi sobre coloraciones de lista: si $G$ tiene un polinomio de coloración $P_G(x_1,\ldots,x_n)$ con un monomio "completo" de coeficiente no nulo, entonces $G$ es $k$-elegible (los vértices se pueden colorear con una lista de $k$ colores cada uno).

El polinomio de coloración de $G$ se construye como $f_G(x_1,\ldots,x_n) = \prod_{(i,j) \in E(G)} (x_i - x_j)$. Este polinomio es no nulo exactamente cuando $(x_1,\ldots,x_n)$ es una coloración propia (colores distintos en vértices adyacentes). Si $f_G$ tiene un monomio $\prod x_i^{d_i}$ con coeficiente no nulo y $d_i < |L_i|$ para las listas $L_i$, entonces por el Nullstellensatz Combinatorio existe una coloración propia con colores en $\prod L_i$.

Esta técnica, bautizada por Alon como método del polinomio de coloración, demuestra (por ejemplo) que todo grafo planar es 5-elegible, resultado que por métodos combinatorios requiere argumentos mucho más complejos.

En la práctica olímpica, memorizar el enunciado del Nullstellensatz Combinatorio y tener el hábito de preguntar "¿hay un polinomio natural que codifique este problema?" es una habilidad que distingue a los estudiantes de nivel selectivo IMO.