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

MATERA, GUILLERMO; PÉREZ, MARIANA; PRIVITELLI, MELINA

Buenos Aires

Congreso; Primer Encuentro Conjunto de la Real Sociedad Matemática Española y la Unión Matemática Argentina; 2017

Real Sociedad Matemática Española y Unión Matemática Argentina

En esta comunicación estudiamos la distribución de patrones de factorización en familias no lineales de polinomios univariados con coeficientes en el cuerpo finito F_q de q elementos. Un resultado clásico afirma que, asintóticamente, la proporción de polinomios de grado n con patrón de factorizaciónlambda:=(lambda_1,...,lambda_n) coincide con la proporción tau(lambda) de permutaciones de n elementos que se descomponen en ciclos de acuerdo al patrónlambda. Una familia A de F_q[T] se denomina uniformemente distribuida si la proporción de elementos de A con patrón de factorización lambda es del orden detau(lambda). En particular, se sabe que el conjunto de polinomios mónicos de grado n en F_q[T] cuyos coeficientes satisfacen ciertas relacioneslineales resulta uniformemente distribuido.Gaa, Howell y Panario se plantearon si es posible obtener resultados parafamilias no lineales, es decir, caracterizar familias no lineales de polinomios de F_q[T] que resultan uniformemente distribuidas. En tal sentido, demostramos que, si A es el conjunto de polinomios mónicos de F_q[T] de grado n cuyos coeficientes pertenecen a una intersección completa no singular definida sobre F_q[T] con "buen comportamiento al infinito", entonces resulta uniformemente distribuida. Más precisamente, demostramos que el cardinal |A_{lambda}| del conjunto A_{lambda} de elementos de A con patrón de factorización lambda es del orden de tau(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|A_{lambda}| como el conjunto de puntos F_q-racionales de cierta intersección completa singular definida por medio de polinomios simétricos, cuyo cardinalestimamos utilizando estimaciones sobre la cantidad de puntos F_q-racionales de variedades F_q-definibles.Asimismo, aplicamos este resultado al análisis en promedio del algoritmo clásico de factorización en familias no lineales de F_q[T], cuestión de importancia dado que dicho algoritmo aparece en muchos paquetes de álgebra computacional. En un trabajo de Flajolet, Gourdon y Panario se realiza un análisis probabilístico del mismo sobre el conjunto de elementos de F_q[T] de grado dado, donde se demuestra que éste queda determinado por lacorrespondiente distribución de patrones de factorización. Sin embargo, frecuentemente los polinomios a factorizar poseen características particulares que implican que tales resultados podrían no resultar pertinentes. En tal sentido, obtenemos resultados sobre el comportamiento en promedio del algoritmoclásico de factorización para el caso de familias no lineales como las mencionadas.