Método polinomial en combinatoria

Como ejemplo, describimos la demostración de Dvir de la Conjetura de Kakeya sobre el Campo Finito utilizando el método polinomial. ^{[ 3 ]}

Conjetura de Kakeya sobre cuerpos finitos : Sea${\displaystyle \mathbb {F} _{q}}$sea ​​un campo finito con${\displaystyle q}$elementos. Deje${\displaystyle K\subseteq \mathbb {F} _{q}^{n}}$ser un conjunto de Kakeya, es decir, para cada vector${\displaystyle y\in \mathbb {F} _{q}^{n}}$existe${\displaystyle x\in \mathbb {F} _{q}^{n}}$de tal manera que${\displaystyle K}$contiene una línea${\displaystyle \{x+ty,t\in \mathbb {F} _{q}\}}$. Luego el conjunto${\displaystyle K}$tiene tamaño al menos${\displaystyle c_{n}q^{n}}$dónde${\displaystyle c_{n}>0}$es una constante que solo depende de${\displaystyle n}$.

Prueba: La prueba que daremos demostrará que${\displaystyle K}$tiene tamaño al menos${\displaystyle c_{n}q^{n-1}}$. El límite de${\displaystyle c_{n}q^{n}}$Se puede obtener utilizando el mismo método con un poco de trabajo adicional.

Supongamos que tenemos un conjunto de Kakeya.${\displaystyle K}$con

${\displaystyle |K|<{q+n-3 \choose n-1}}$

Consideremos el conjunto de monomios de la forma${\displaystyle x_{1}^{d_{1}}x_{2}^{d_{2}}\dots x_{n}^{d_{n}}}$de grado exactamente${\displaystyle q-2}$. Hay exactamente${\displaystyle {q+n-3 \choose n-1}}$tales monomios. Por lo tanto, existe un polinomio homogéneo no nulo.${\displaystyle P(x_{1},x_{2},\dots ,x_{n})}$de grado${\displaystyle q-2}$que desaparece en todos los puntos en${\displaystyle K}$. Nótese que esto se debe a que encontrar dicho polinomio se reduce a resolver un sistema de${\displaystyle |K|}$ecuaciones lineales para los coeficientes.

Ahora utilizaremos la propiedad que${\displaystyle K}$es un conjunto de Kakeya para mostrar que${\displaystyle P}$debe desaparecer en todo${\displaystyle \mathbb {F} _{q}^{n}}$. Claramente${\displaystyle P(0,0\dots ,0)=0}$A continuación, para${\displaystyle y\neq 0}$, hay un${\displaystyle x}$de tal manera que la línea${\displaystyle \{x+ty,t\in \mathbb {F} _{q}\}}$está contenido en${\displaystyle K}$. Desde${\displaystyle P}$es homogéneo, si${\displaystyle P(z)=0}$para algunos${\displaystyle z\in \mathbb {F} _{q}^{n}}$entonces${\displaystyle P(cz)=0}$para cualquier${\displaystyle c\in \mathbb {F} _{q}}$. En particular

${\displaystyle P(tx+y)=P(t(x+t^{-1}y))=0}$

para todos los valores distintos de cero${\displaystyle t\in \mathbb {F} _{q}}$. Sin embargo,${\displaystyle P(tx+y)}$es un polinomio de grado${\displaystyle q-2}$en${\displaystyle t}$pero tiene al menos${\displaystyle q-1}$raíces correspondientes a los elementos no nulos de${\displaystyle \mathbb {F} _{q}}$por lo que debe ser exactamente cero. En particular, al sustituir${\displaystyle t=0}$deducimos${\displaystyle P(y)=0}$.

Hemos demostrado que${\displaystyle P(y)=0}$a pesar de${\displaystyle y\in \mathbb {F} _{q}^{n}}$pero${\displaystyle P}$tiene un grado menor que${\displaystyle q-1}$en cada una de las variables, por lo que esto es imposible según el lema de Schwartz-Zippel . Deducimos que en realidad debemos tener

${\displaystyle |K|\geq {q+n-3 \choose n-1}\sim {\frac {q^{n-1}}{(n-1)!}}}$

Una variación del método polinomial, a menudo denominada partición polinomial, fue introducida por Guth y Katz en su solución al problema de las distancias distintas de Erdős . ^{[ 4 ]} La partición polinomial implica el uso de polinomios para dividir el espacio subyacente en regiones y argumentar sobre la estructura geométrica de la partición. Estos argumentos se basan en resultados de la geometría algebraica que acotan el número de incidencias entre diversas curvas algebraicas. La técnica de partición polinomial se ha utilizado para dar una nueva demostración del teorema de Szemerédi-Trotter mediante el teorema del sándwich de jamón polinomial y se ha aplicado a una variedad de problemas en geometría de incidencia . ^{[ 5 ] [ 6 ]}