Cómo reconocer que el método polinómico puede funcionar

Question

Hace un par de días estuve en un bonito seminario impartido por Christian Reiher, en el que nos habló de una breve demostración del siguiente caso especial de un teorema de Olson.

Teorema. Dejemos que $(a_1,b_1),\dots,(a_n,b_n)$ sea una secuencia de puntos en ${\mathbb{Z}}_p^2$ con $n\geq 2p-1$ . Entonces hay un subconjunto no vacío $A\subset\{1,2,\dots,n\}$ tal que $\sum_{i\in A}(a_i,b_i)=(0,0)$ .

La prueba corta no era corta en términos absolutos, pero era corta si se estaba dispuesto a aceptar el siguiente resultado de Noga Alon, conocido como el nullstellensatz combinatorio.

Teorema. Sea F un campo y sea P un polinomio en n variables $x_1,\dots,x_n$ sobre F. Sea $x_1^{t_1}\dots x_n^{t_n}$ sea un monomio de grado total máximo $t_1+\dots+t_n$ que aparece en P con un coeficiente distinto de cero, y sea $S_1,\dots,S_n$ sean subconjuntos de F tales que $|S_i|>t_i$ para cada i. Entonces existe $s_i\in S_i$ tal que $P(s_1,\dots,s_n)\ne 0.$

Una vez que se tiene el nullstellensatz combinatorio, el caso especial del teorema de Olson (y creo que todo el teorema) se reduce a un bonito ejercicio: básicamente, una vez que te sientas a pensar en ello ves rápidamente que tiene sentido elegir cada $S_i$ para que sea {0,1}, y luego unos simples trucos usando el pequeño teorema de Fermat (el polinomio $1-x^{p-1}$ es cero si $x\ne 0$ y 1 en caso contrario) se puede acabar con bastante facilidad.

Este método se conoce como método polinómico. Mi pregunta es no cómo aplicar el nullstellensatz combinatorio. Es cómo reconocer, cuando ves un problema, que el método polinómico podría funcionar. En este caso, una vez que tienes esa pista, es fácil terminar. ¿Pero cómo te las arreglas si no hay nadie que te dé la pista?

Me interesa esta pregunta en general: Siempre me ha parecido que detectar que los resultados matemáticos pueden ser utilizados es un proceso bastante difícil -- de alguna manera tengo que hacerlo por mí mismo en un problema antes de entender realmente cómo hacerlo en otros problemas. Y aquí hay un buen ejemplo en el que tengo nunca se ha visto cómo utilizar el resultado. Y si me hubiera enfrentado a la tarea de demostrar el teorema de Olson, no creo que se me hubiera ocurrido utilizarlo.

Answer 1

Mi opinión es que puede ser prematuro declarar qué tipos de problemas parecen manejables con respecto al método polinómico. Por ejemplo, la idea de utilizar el método polinómico para atacar el problema de Kakeya en campo finito, aunque es "obvia" en retrospectiva, fue sin duda una gran sorpresa para muchos de los que trabajábamos en el problema de Kakeya en el momento en que se presentó el argumento de Dvir.

En cambio, la cuestión de obtener un teorema no trivial de Szemeredi-Trotter o de la suma de productos en campos finitos, aunque está estrechamente relacionada con el problema de Kakeya (véase, por ejemplo, mi artículo con Bourgain y Katz sobre este tema), se ha resistido hasta ahora a todos los intentos de demostración con un método polinómico. Pero esto podría deberse simplemente a que aún no hemos encontrado la forma correcta de generar el tipo de polinomios adecuado para este problema. Del mismo modo, el problema de determinar los mejores límites de $r_3(F_3^n)$ que lo que se puede obtener con los métodos de Fourier es uno que a primera vista parece muy susceptible de ser abordado con un método polinómico, pero de nuevo no ha habido ningún progreso en este frente. (Por cierto, estos son grandes problemas que hay que estudiar si alguien en esta área está buscando una tarea de alto riesgo y alta recompensa para añadir a sus proyectos de investigación).

Lo que me gustaría ver en el futuro es un mayor desarrollo de la idea un tanto vaga de la "complejidad de Zariski" de varios conjuntos, con lo que me refiero a algo así como el menor grado de un polinomio no trivial que desaparece en ese conjunto. Uno puede ver el método del polinomio como la estrategia de comparar los límites superior e inferior de la complejidad de Zariski de los conjuntos para obtener consecuencias combinatorias no triviales. Tengo la vaga sensación de que, en última instancia, estas nociones de complejidad deberían desempeñar un papel tan importante en este tipo de problemas combinatorios como las nociones existentes de "tamaño" para dichos conjuntos, como la cardinalidad, la dimensión o la uniformidad de Fourier.

Answer 2

Me he dado cuenta de que más ) de algunos de ellos que satisfacen una propiedad que puede escribirse fácilmente como una condición polinómica (tener la propiedad está relacionada con la pertenencia al conjunto cero de un polinomio, como ser colineal o coplanar, tener la suma divisible por un determinado primo, o ser diferente).

Tendré que escribir algunos ejemplos para ilustrar lo que quiero decir.

Ejemplo 1 Dado $2n$ establece $A_i=\{x_i,y_i\}$ cuyos elementos son números reales y los índices son mod $2n$ , demuestran que se puede elegir $z_i\in A_i$ para que $z_i\neq z_{i+1}$ para todos $i$ .

Esta también se puede resolver con un argumento directo, pero CN da una prueba rápida una vez que vemos que lo que se pide es encontrar $z_i$ para que $\prod(z_i-z_{i+1})\neq 0$ (por lo que es una propiedad polinómica). El problema de Snevily también entra en esta categoría.

Ejemplo 2 (Erdos-Ginzburg-Ziv) Dado $2p-1$ enteros se puede encontrar $p$ cuya suma es divisible por $p$ .

Este es similar al teorema de Olson, y uno se da cuenta de que la divisibilidad por un primo para una suma $\sum x_i$ es una "condición polinómica" en el sentido de que es equivalente a $(\sum x_i)^{p-1}-1\neq 0$ en $\mathbb{F}_p[x]$ . CN da la conclusión.

Ejemplo 3 (Alon-Furedi) Considera los puntos de la red $(x_1,\cdots,x_k)$ donde $0\le x_i \le n_i$ para cada $i$ pero no todos $x_i$ desaparecer. El número mínimo de hiperplanos que no pasan del origen necesarios para cubrir todos estos puntos de la red es $\sum n_i$ .

Este resultado fue, creo, uno de los teoremas diseñados para mostrar la fuerza del nullstellensatz combinatorio porque se deduce fácilmente de él, sin embargo, encontrar una prueba puramente combinatoria sigue siendo un problema abierto.

En éste (y en otros enunciados en los que se prueban límites inferiores usando CN, como Erdos-Heilbronn) hay una colección de objetos que tienen una propiedad polinómica y de alguna manera es natural pensar en el único gran polinomio (el producto de todas las ecuaciones lineales que definen los hiperplanos en nuestro caso) y por contradicción usar CN para obtener un límite inferior en su grado.

Mi impresión es que es más fácil juzgar si el método polinómico funcionaría para los resultados de existencia que para los problemas que te piden que demuestres un límite inferior (a menos que uno piense en los límites inferiores como resultados de no existencia, en cuyo caso se convierte en la misma cuestión). Sin embargo, debo terminar reconociendo (y disculpándome) que esta respuesta es bastante inútil, no sólo porque describe una observación trivial, sino también porque no dice nada acerca de los resultados que se pueden demostrar utilizando el método polinómico, aunque se formulan muy lejos de los teoremas como los anteriores. Un ejemplo que tengo en mente es el resultado de Alon-Friedland-Kalai de que un grafo simple de 4 regularidades más una arista contiene un subgrafo de 3 regularidades.

Answer 3

Dos razones obvias para probar el método polinómico:

1) El problema puede formularse como desaparición/no desaparición de algún polinomio.

2) El problema es similar a uno de los ya resueltos por el método polinómico, digamos, a uno de los problemas considerados en el artículo fundamental de Alon http://www.tau.ac.il/~nogaa/PDFS/null2.pdf

Algunos consejos, basados en mis propias impresiones:

3) El problema solucionable por el método polinómico es bastante agudo, luego de naturaleza asintótica. Por lo tanto, dudo que el teorema de Freiman pueda demostrarse por esta vía, mientras que el de Cauchy-Davenport está bien. A menudo son evidentes resultados ligeramente más débiles (por ejemplo, en Cauchy-Davenport, si sustituimos $|A+B|\geq |A|+|B|-1$ a $|A+B|\geq (|A|+|B|)/2$ se vuelve obvio. Si sustituimos $d$ -elegibilidad de un gráfico con grados sobre $2d$ a $(2d+1)$ -elección, se hace evidente).

4) Debe existir alguna estructura algebraica en el problema. Digamos que la planaridad de un gráfico no es una condición muy algebraica:) Otra actualización: mi intuición se equivocó ligeramente aquí. Hay una prueba polinómica de Ellingham y Goddyn de que $r$ - borde regular $r$ -El grafo planar coloreable es de aristas. $r$ -elegible. La razón con la paridad es bastante bonita.

5) ten cuidado con probar lo que es verdad o más. Digamos que la CN se aplica a menudo para la elegibilidad de los grafos, y no conozco aplicaciones a las coloraciones de los grafos diferentes de la demostración de la elegibilidad. Así, si tu grafo no es a priori d-elegible, difícilmente se puede demostrar con CN que es d-colorable.

Puede que más adelante recuerde otras impresiones.

Answer 4

Me gustaría añadir algunos ejemplos y referencias más para el llamado método polinómico que pueden ayudarnos a reconocer cuándo se puede aplicar.

Por lo que he entendido hasta ahora, el método polinómico entra en estas dos grandes categorías:

A. Construir un polinomio explícito (o un conjunto de polinomios) que capture el conjunto dado.

B. Utilizar argumentos de interpolación para obtener un polinomio cuyo grado (o alguna otra propiedad) esté bajo control.

Una importante y conocida subcategoría de A es el argumento de dimensión utilizando espacios polinómicos.

Por ejemplo, si queremos demostrar que puede haber como máximo $n(n+1)/2$ líneas equiangulares en $\mathbb{R}^n$ y con cada línea asociamos el polinomio $P_u = (u, x)^2 - \alpha^2(x, x)$ donde $u$ es un vector unitario fijo en la línea y $arccos(\alpha)$ es el ángulo entre cada par de líneas. Entonces demostramos que $P_u(v) = (1 - \alpha) \delta_{u, v}$ demostrando que estos polinomios son linealmente independientes. Ahora, todos estos polinomios son de grado $2$ polinomios homogéneos en $n$ variables, y por lo tanto el número está acotado por encima de la dimensión de estos espacios, $n(n+1)/2$ . Otro ejemplo que demuestra este enfoque es el límite de $2$ -conjuntos de distancia en espacios euclidianos. Para más detalles, y varios ejemplos me remito al manuscrito " Métodos de álgebra lineal en combinatoria "de Babai y Frankl.

Otra subcategoría es cuando se utilizan los coeficientes o grados del polinomio explícito. Uno de los ejemplos más sencillos es quizás el resultado de Blokhuis en núcleos de conjuntos en $\mathbb{F}_q^2$ . Un núcleo de un conjunto $S$ de puntos en $\mathbb{F}_q^2$ es un punto $x$ no en $S$ de tal manera que cada línea que pasa por $x$ se cruza con $S$ . Blokhuis demostró que si $S$ tiene tamaño $q + k$ con $k \leq q$ , entonces todos los núcleos de $S$ son raíces de un grado $k(q-1)$ (pista: un polinomio simétrico elemental), demostrando así que el número total de núcleos es como máximo $k(q-1)$ .

El Brouwer-Schrijver/Jamison límite en los conjuntos afines de bloqueo también utiliza una propiedad de los polinomios sobre campos finitos según la cual, si un polinomio en $\mathbb{F}_q[t_1, \dots, t_n]$ desaparece en todos los puntos de $\mathbb{F}_q^n$ excepto uno, entonces su grado debe ser al menos $n(q-1)$ . Esto es bastante similar al teorema clásico de Chevalley-Warning. Y, de hecho, se puede demostrar mediante una argumento de dimensión también.

Creo que el Combinatorial Nullstellensatz, y todas sus aplicaciones que conozco, entran en la categoría A también. Aquí construimos un polinomio lo suficientemente explícito como para poder determinar el coeficiente de su monomio principal. El respuesta de Gjergji Zaimi cubre muy bien este enfoque. Si queremos estimaciones sobre el número total de puntos no evanescentes, en lugar de sólo la existencia, entonces podemos utilizar a veces el resultado de Alon-Füredi, como lo han hecho recientemente Clark, Forrow y Schmitt en este papel.

Categoría B parece ser algo más reciente. Fue utilizado por Dvir en su prueba de la conjetura de Kakeya de campos finitos, y luego ha encontrado varias aplicaciones. Terence Tao ha escrito un buen estudio al respecto que puede encontrarse en aquí . Citando a Tao,

En términos generales, la estrategia consiste en capturar (o al menos dividir) los conjuntos arbitrarios de objetos (vistos como puntos en algún espacio de configuración configuración) en el conjunto cero de un polinomio cuyo grado (u otra medida de de complejidad) está bajo control; por ejemplo, el grado puede estar por alguna función del número de objetos. A continuación, se utilizan herramientas de la geometría algebraica para entender la estructura de este conjunto cero, y así controlar los conjuntos originales de objetos.

Otro avance importante utilizando este enfoque fue el resultado de Guth y Katz sobre El problema de las distancias distintas de Erdős .

¿Pueden estos dos enfoques ( A y B ) se combinen? Me encantaría ver un ejemplo de ello. Pero esto es lo que Terence Tao tenía que decir sobre la combinación de CN e Interpolación,

A grandes rasgos, la idea es comenzar con un contraejemplo del resultado extremo reclamado, y luego usar este contraejemplo para diseñar un polinomio que desaparezca en un conjunto de productos grande y que sea lo suficientemente explícito como para que uno pueda calcular que cierto coeficiente del polinomio sea distinto de cero, contradiciendo así la nullstellensatz. Esto debe contrastarse con las aplicaciones más recientes del método del polinomio, en las que se utilizan teoremas de interpolación para producir el polinomio requerido. Desgraciadamente, en la actualidad los dos métodos no pueden combinarse fácilmente, porque los polinomios producidos por los métodos de interpolación no son lo suficientemente explícitos como para poder calcular fácilmente los coeficientes individuales, pero es concebible que en el futuro pueda aparecer alguna unificación útil de los dos métodos

Más referencias

• Aart Blokhuis, Polinomios en geometrías finitas y combinatoria .
• A. A. Bruen, J. C. Fisher, El método de Jamison en las geometrías de Galois .
• Noga Alon, Matemáticas discretas: métodos y desafíos .
• Gyula Károlyi, El método polinómico en la combinatoria aditiva .
• Simeon Ball, Polinomios en geometrías finitas y El método de los polinomios en las geometrías de Galois .
• Terence Tao y Van Vu, capítulo 9 de Combinatoria aditiva .
• Zeev Dvir, Teoremas de incidencia y sus aplicaciones .
• Terence Tao, Geometría combinatoria algebraica: el método polinómico en combinatoria aritmética, combinatoria de incidencia y teoría de números .
• Peter Sziklai, Polinomios en geometrías finitas y Aplicaciones de los polinomios sobre campos finitos .
• Larry Guth, Método polinómico en combinatoria .

Answer 5

Siempre pensé que el método polinómico podría estar relacionado con los argumentos de paridad o los teoremas del tipo Borsuk-Ulam. Para un teorema que tiene una prueba corta tanto con la CN como con la BU, ver http://arxiv.org/abs/1005.1177 . Lamentablemente no tengo una buena intuición sobre cuándo intentar aplicarlos.