En matemáticas, un polinomio disperso (también polinomio lacunario [1] o pocosnomio ) [2] es un polinomio que tiene muchos menos términos de los que sugerirían su grado y número de variables . Por ejemplo, x 10 + 3x 3 − 1 es un polinomio disperso ya que es un trinomio con un grado de 10.
La motivación para estudiar polinomios dispersos es concentrarse en la estructura de los monomios de un polinomio en lugar de en su grado, como se puede ver, por ejemplo, al comparar el teorema de Bernstein-Kushnirenko con el teorema de Bezout . La investigación sobre polinomios dispersos también ha incluido trabajos en algoritmos cuyo tiempo de ejecución crece en función del número de términos en lugar del grado, [3] para problemas que incluyen multiplicación de polinomios [4] [5] , división , [6] raíz- algoritmos de búsqueda , [7] y máximos divisores comunes polinomiales . [8] Los polinomios dispersos también se han utilizado en matemáticas puras, especialmente en el estudio de los grupos de Galois , porque ha sido más fácil determinar los grupos de Galois de ciertas familias de polinomios dispersos que para otros polinomios. [9]
Las variedades algebraicas determinadas por polinomios dispersos tienen una estructura simple, que también se refleja en la estructura de las soluciones de ciertas ecuaciones diferenciales relacionadas . [2] Además, existe una escasa positivstellensatz para polinomios dispersos univariados. Afirma que la no negatividad de un polinomio puede certificarse mediante polinomios cuyo grado sólo depende del número de monomios del polinomio. [10]
Los polinomios dispersos a menudo aparecen en ecuaciones de suma o diferencia de potencias. La suma de dos cubos establece que (a + b)(a 2 − ab + b 2 ) = a 3 + b 3 . a 3 + b 3 , aquí, es un polinomio disperso.
Ver también
- Askold Khovanskii , uno de los principales contribuyentes a la teoría de los pocos nominales.
Referencias
- ^ Rédei, L. (1973), Polinomios lacunarios sobre campos finitos , traducido por Földes, I., Elsevier, MR 0352060
- ^ ab Khovanskiĭ, AG (1991), Fewnomials , Traducciones de monografías matemáticas, vol. 88, traducido por Zdravkovska, Smilka, Providence, Rhode Island: American Mathematical Society, doi :10.1090/mmono/088, ISBN 0-8218-4547-0, señor 1108621
- ^ Roche, Daniel S. (2018), "¿Qué podemos (y no podemos) hacer con polinomios dispersos?", En Kauers, Manuel; Ovchinnikov, Alexey; Schost, Éric (eds.), Actas del ACM 2018 sobre el Simposio internacional sobre computación simbólica y algebraica, ISSAC 2018, Nueva York, NY, EE. UU., 16-19 de julio de 2018 , Association for Computing Machinery, págs. arXiv : 1807.08289 , doi : 10.1145/3208976.3209027, S2CID 49868973
- ^ Nakos, Vasileios (2020), "Multiplicación polinómica dispersa casi óptima", IEEE Transactions on Information Theory , 66 (11): 7231–7236, arXiv : 1901.09355 , doi : 10.1109/TIT.2020.2989385, MR 4173637, S2CID 59316 578
- ^ Giorgi, Pascal; Grenet, Bruno; Perret du Cray, Armelle (2020), "Multiplicación polinómica dispersa esencialmente óptima", Actas del 45º Simposio Internacional sobre Computación Simbólica y Algebraica (ISSAC '20). , Asociación de Maquinaria de Computación, págs. 202–209, arXiv : 2001.11959 , doi :10.1145/3373207.3404026, S2CID 211003922
- ^ Giorgi, Pascal; Grenet, Bruno; Perret du Cray, Armelle (2021), "Sobre la división exacta y las pruebas de divisibilidad para polinomios dispersos", Actas del Simposio internacional de 2021 sobre computación simbólica y algebraica (ISSAC '21). , Asociación de Maquinaria de Computación, págs. 163–170, arXiv : 2102.04826 , doi :10.1145/3452143.3465539, S2CID 231855563
- ^ Pan, Victor Y. (2020), "Aceleración de la búsqueda de raíces de subdivisión para polinomios dispersos", Álgebra informática en informática científica , Lecture Notes in Computer Science, vol. 12291, Cham: Springer, págs. 461–477, doi :10.1007/978-3-030-60026-6_27, MR 4184190, S2CID 224820309
- ^ Zippel, Richard (1979), "Algoritmos probabilísticos para polinomios dispersos", Computación simbólica y algebraica (EUROSAM '79, Simpos. Internacional, Marsella, 1979) , Lecture Notes in Computer Science, vol. 72, Berlín, Nueva York: Springer, págs. 216–226, SEÑOR 0575692
- ^ Cohen, SD; Movahhedi, A.; Salinier, A. (1999), "Grupos de trinomios de Galois", Journal of Algebra , 222 (2): 561–573, doi : 10.1006/jabr.1999.8033 , MR 1734229
- ^ Averkov, Gennady; Scheiderer, Claus (7 de marzo de 2023). "Cascos convexos de curvas monomiales y un positivstellensatz escaso". arXiv : 2303.03826 [matemáticas.OC].