Sesión Geometría Algebraica y Teoría de Números

Diciembre 14, 17:30 ~ 17:50

Distribución de patrones de factorización en familias no lineales de polinomios univariados sobre cuerpos finitos y aplicaciones

Pérez, Mariana

En esta comunicación estudiamos la distribución de patrones de factorización en familias {\em no lineales} de polinomios univariados con coeficientes en el cuerpo finito $\mathbb{F}_q$ de $q$ elementos. Un resultado clásico (ver [2]) afirma que, asintóticamente, la proporción de polinomios de grado $n$ con patrón de factorización $\boldsymbol{\lambda}:=(\lambda_1,...,\lambda_n)$ coincide con la proporción $\tau(\boldsymbol{\lambda})$ de permutaciones de $n$ elementos que se descomponen en ciclos de acuerdo al patrón $\boldsymbol{\lambda}$. En [2], una familia $\mathcal{A}\subset\mathbb{F}_q[T]$ se denomina {\em uniformemente distribuida} si la proporción de elementos de $\mathcal{A}$ con patrón de factorización $\boldsymbol{\lambda}$ es del orden de $\tau(\boldsymbol{\lambda})$. En particular, en dicho trabajo se demuestra que el conjunto de polinomios mónicos de grado $n$ en $\mathbb{F}_q[T]$ cuyos coeficientes satisfacen ciertas relaciones lineales resulta uniformemente distribuido. En [4] se plantea si es posible obtener resultados para familias no lineales, es decir, caracterizar familias no lineales de polinomios de $\mathbb{F}_q[T]$ que resultan uniformemente distribuidas. En tal sentido, demostramos que, si $\mathcal{A}\subset\mathbb{F}_q[T]$ es el conjunto de polinomios mónicos de grado $n$ cuyos coeficientes pertenecen a una intersección completa no singular definida sobre $\mathbb{F}_q$ con ``buen comportamiento al infinito'', entonces resulta uniformemente distribuida. Más precisamente, demostramos que el cardinal $|\mathcal{A}_{\boldsymbol{\lambda}}|$ del conjunto $\mathcal{A}_{\boldsymbol{\lambda}}$ de elementos de $\mathcal{A}$ con patrón de factorización $\boldsymbol{\lambda}$ es del orden de $\tau(\boldsymbol{\lambda})q^m$, donde $m$ es la dimensión de la intersección completa en consideración, con un término de error explícito. Para esto, expresamos $|\mathcal{A}_{\boldsymbol{\lambda}}|$ como el conjunto de puntos $\mathbb{F}_q$-racionales de cierta intersección completa singular definida por medio de polinomios simétricos, cuyo cardinal estimamos utilizando estimaciones sobre la cantidad de puntos $\mathbb{F}_q$-racionales de [1] y [6] (ver [5] y [7] por un enfoque similar a otros problemas combinatorios). Asimismo, aplicamos este resultado al análisis en promedio del algoritmo clásico de factorización en familias no lineales de $\mathbb{F}_q[T]$, cuestión de importancia dado que dicho algoritmo aparece en muchos paquetes de álgebra computacional. En [3] se realiza un análisis probabilístico del mismo sobre el conjunto de elementos de $\mathbb{F}_q[T]$ de grado dado, donde se demuestra que éste queda determinado por la correspondiente distribución de patrones de factorización. Sin embargo, frecuentemente los polinomios a factorizar poseen características particulares que implican que los resultados de [3] resulten pertinentes. En tal sentido, obtenemos resultados sobre el comportamiento en promedio del algoritmo clásico de factorización para el caso de familias no lineales como las mencionadas, generalizando los resultados del caso lineal de [8]. \bigskip {\footnotesize \noindent[1] A.~Cafure, G.~Matera and M.~Privitelli. \newblock Polar varieties, {Bertini's} theorems and number of points of singular complete intersections over a finite field. \newblock {Finite Fields Appl.}, 31:42--83, 2015. \noindent[2] S. Cohen. Uniform distribution of polynomials over finite fields, J. Lond. Math. Soc.(2) 6:93--102, 1972. \noindent[3] P. Flajolet, X. Gourdon and D. Panario. The complete analysis of a polynomial factorization algorithm over finite fields. J. Algorithms. 40 (1): 37-81, 2001. \noindent[4] S.~{Gao}, J.~{Howell}, and D.~{Panario}. Irreducible polynomials of given forms. In {\em Finite fields: theory, applications, and algorithms}, 43--54. Amer. Math. Soc., Providence, RI, 1999. \noindent[5] G.~Matera, M.~Pérez, and M.~Privitelli. On the value set of small families of polynomials over a finite field, {II}. Acta Arith., 165(2):141--179, 2014. \noindent[6] G. Matera, M. Pérez and M. Privitelli. Explicit estimates for the number of rational points of singular complete intersections over a finite field. J. Number Theor., 158:54-72, 2016. \noindent[7] G. Matera, M. Pérez and M. Privitelli. On the value set of small families of polynomials over a finite field, III. In {\em Contemporary developments in finite fields and their applications}, World Sci. Press, 2016. \noindent[8] M. Pérez. Análisis probabilísticos de algoritmos y problemas combinatorios sobre cuerpos finitos. Ph.D. thesis, Universidad de Buenos Aires, Buenos Aires, Argentina, 2016. }

Autores: Matera, Guillermo / Pérez, Mariana / Privitelli, Melina.