En matemáticas, el método polinomial es un enfoque algebraico para problemas combinatorios que implica capturar alguna estructura combinatoria usando polinomios y proceder a discutir sobre sus propiedades algebraicas. Recientemente, el método polinomial ha llevado al desarrollo de soluciones notablemente simples a varios problemas abiertos de larga data. [1] El método polinomial abarca una amplia gama de técnicas específicas para usar polinomios e ideas de áreas como la geometría algebraica para resolver problemas combinatorios. Mientras que algunas técnicas que siguen el marco del método polinomial, como Combinatorial Nullstellensatz de Alon , [2] se conocen desde la década de 1990, no fue hasta alrededor de 2010 que se desarrolló un marco más amplio para el método polinomial.
Resumen matemático
Muchos usos del método polinomial siguen el mismo enfoque de alto nivel. El enfoque es el siguiente:
- Incruste algún problema combinatorio en un espacio vectorial.
- Capturar las hipótesis del problema construyendo un polinomio de bajo grado que sea cero en un determinado conjunto.
- Después de construir el polinomio, discuta sobre sus propiedades algebraicas para deducir que la configuración original debe satisfacer las propiedades deseadas.
Ejemplo
Como ejemplo, describimos la prueba de Dvir de la conjetura de Kakeya de campo finito usando el método polinomial. [3]
Conjetura de Kakeya de campo finito : Sea ser un campo finito con elementos. Dejar ser un conjunto Kakeya, es decir, para cada vector existe tal que contiene una línea . Entonces el set tiene tamaño al menos dónde es una constante que solo depende de .
Prueba: La prueba que damos mostrará que tiene tamaño al menos . El límite de se puede obtener utilizando el mismo método con un poco de trabajo adicional.
Supongamos que tenemos un juego de Kakeya con
Considere el conjunto de monomios de la forma de grado exactamente . Hay exactamentetales monomios. Por tanto, existe un polinomio homogéneo distinto de cero de grado que se desvanece en todos los puntos de . Tenga en cuenta que esto se debe a que encontrar tal polinomio se reduce a resolver un sistema de ecuaciones lineales para los coeficientes.
Ahora usaremos la propiedad que es un Kakeya preparado para mostrar que debe desaparecer en todos . Claramente. A continuación, para, hay un tal que la linea está contenido en . Desde es homogéneo, si para algunos luego para cualquier . En particular
para todo distinto de cero . Sin embargo, es un polinomio de grado en pero tiene al menos raíces correspondientes a los elementos distintos de cero de por lo que debe ser idénticamente cero. En particular, enchufar deducimos .
Hemos demostrado que para todos pero tiene un grado menor que 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
Partición polinomial
Guth y Katz introdujeron una variación del método polinomial, a menudo llamado partición polinomial, en su solución al problema de distancias distintas de Erd . [4] La partición polinomial implica el uso de polinomios para dividir el espacio subyacente en regiones y discutir sobre la estructura geométrica de la partición. Estos argumentos se basan en los resultados de la geometría algebraica que limita el número de incidencias entre varias 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]
Aplicaciones
Algunos ejemplos de problemas abiertos de larga data que se han resuelto utilizando el método polinomial son:
- La conjetura de Kakeya del campo finito [3] por Dvir
- El problema del tope establecido por Ellenberg y Gijswijt [7] con el marco original desarrollado sobre el problema análogo sobrepor Croot, Lev y Pach [8]
- El problema de distancias distintas de Erd de Guth y Katz [4]
- El problema de las articulaciones en 3D por Guth y Katz. [9] Su argumento fue posteriormente simplificado por Elekes, Kaplan y Sharir [10]
Ver también
Referencias
- ^ Guth, L. (2016). Métodos polinomiales en combinatoria . Ciclos de Conferencias Universitarias. Sociedad Matemática Estadounidense. ISBN 978-1-4704-2890-7. Consultado el 11 de diciembre de 2019 .
- ^ Alon, Noga (1999). "Combinatoria Nullstellensatz". Combinatoria, Probabilidad y Computación . 8 (1–2): 7–29. doi : 10.1017 / S0963548398003411 . ISSN 0963-5483 .
- ^ a b Dvir, Zeev (2008). "Sobre el tamaño de los conjuntos de Kakeya en campos finitos" . Revista de la Sociedad Matemática Estadounidense . 22 (4): 1093–1097. doi : 10.1090 / S0894-0347-08-00607-3 . ISSN 0894-0347 .
- ^ a b Guth, Larry; Katz, Nets (2015). "Sobre el problema de distancias distintas de Erd en el avión". Annals of Mathematics : 155-190. doi : 10.4007 / annals.2015.181.1.2 . hdl : 1721,1 / 92873 . ISSN 0003-486X .
- ^ Kaplan, Haim; Matoušek, Jiří; Sharir, Micha (2012). "Pruebas simples de teoremas clásicos en geometría discreta a través de la técnica de partición polinomial de Guth-Katz". Geometría discreta y computacional . 48 (3): 499–517. arXiv : 1102.5391 . doi : 10.1007 / s00454-012-9443-3 . ISSN 0179-5376 .
- ^ Dvir, Zeev (2012). "Teoremas de incidencia y sus aplicaciones". Fundamentos y Tendencias en Informática Teórica . 6 (4): 257–393. arXiv : 1208.5073 . Código bibliográfico : 2012arXiv1208.5073D . doi : 10.1561 / 0400000056 . ISSN 1551-305X .
- ^ Ellenberg, Jordan; Gijswijt, Dion (2017). "En grandes subconjuntos de F q norte {\ Displaystyle \ mathbb {F} _ {q} ^ {n}} sin progresión aritmética de tres términos " . Annals of Mathematics . 185 (1): 339–343. doi : 10.4007 / annals.2017.185.1.8 . ISSN 0003-486X .
- ^ Croot, Ernie; Lev, Vsevolod; Pach, Péter (2017). "Se establece sin progresión en Z 4 norte {\ Displaystyle \ mathbb {Z} _ {4} ^ {n}} son exponencialmente pequeños " (PDF) . Annals of Mathematics . 185 (1): 331–337. doi : 10.4007 / annals.2017.185.1.7 . ISSN 0003-486X .
- ^ Guth, Larry ; Katz, Nets Hawk (2010). "Métodos algebraicos en análogos discretos del problema de Kakeya" . Avances en Matemáticas . 225 (5): 2828-2839. arXiv : 0812.1043 . doi : 10.1016 / j.aim.2010.05.015 . ISSN 0001-8708 .
- ^ Elekes, György; Kaplan, Haim; Sharir, Micha (2011). "Sobre líneas, juntas e incidencias en tres dimensiones". Revista de Teoría Combinatoria, serie A . 118 (3): 962–977. doi : 10.1016 / j.jcta.2010.11.008 . ISSN 0097-3165 .
enlaces externos
- Encuesta sobre el método polinomial por Terence Tao
- Encuesta sobre el método polinomial por Larry Guth