En matemáticas, un polinomio de permutación (para un anillo dado) es un polinomio que actúa como una permutación de los elementos del anillo, es decir, la aplicación es una función biyectiva. En caso de que el anillo sea un cuerpo finito, los polinomios de Dickson, que están estrechamente relacionados con los polinomios de Chebyshov, proporcionan varios ejemplos. Sobre un cuerpo finito, cada función, y en particular cada permutación de los elementos de ese cuerpo, puede escribirse como una función polinómica.
En el caso de anillos finitos Z/nZ, dichos polinomios también se han estudiado y aplicado como parte del código de corrección de errores de los algoritmos de detección y corrección de errores.
Polinomios de permutación de variable única sobre cuerpos finitos Sea el cuerpo finito de característica , es decir, el cuerpo que tiene elementos donde es algún primo . Un polinomio con coeficientes en (escrito simbólicamente como ) es un polinomio de permutación de si la función de sobre sí mismo definida por es una permutación de .
Debido a la finitud de , esta definición se puede expresar de varias formas equivalentes: La función es sobre (sobreyectiva). La función es uno a uno (inyectiva). tiene una solución en para cada en . tiene una solución única en para cada en .
Una caracterización de qué polinomios son polinomios de permutación viene dada por:
(Criterio de Charles Hermite) es un polinomio de permutación de si y solo si se cumplen las dos condiciones siguientes: tiene exactamente una raíz en . Para cada entero con y , la reducción de tiene grado .
Si es un polinomio de permutación definido sobre el cuerpo finito , entonces también lo es para todos los y en . El polinomio de permutación está en forma normalizada si y se eligen de modo que sea mónico, y (siempre que la característica no divida el grado del polinomio) el coeficiente de sea 0.
Hay muchas preguntas abiertas sobre los polinomios de permutación definidos sobre cuerpos finitos.
De grado pequeño El criterio de Hermite requiere una gran cantidad de cálculos y puede resultar difícil de utilizar para sacar conclusiones teóricas. Sin embargo, Dickson pudo usarlo para encontrar todos los polinomios de permutación de grado como máximo cinco en todos los cuerpos finitos. Estos resultados son: Polinomio de permutación normalizado de cualquier ( no es un cuadrado) (si su única raíz en es 0) ( no es una cuarta potencia) ( no es un cuadrado) ( arbitrario) ( no es un cuadrado) ( no un es cuadrado)
En se puede encontrar una lista de todos los polinomios de permutación mónica de grado seis en forma normalizada.
Algunas clases de polinomios de permutación Más allá de los ejemplos anteriores, la siguiente lista, aunque no es exhaustiva, contiene casi todas las clases principales conocidas de polinomios de permutación sobre cuerpos finitos.
permuta si y solo si y son coprimos (notacionalmente, ). Si está en y entonces los polinomios de Dickson (del primer tipo) están definidos por
Esta expresión se obtiene de la relación de recurrencia
con las condiciones iniciales y .
Los primeros polinomios de Dickson son:
Si y entonces permuta GF(q) si y solo si . Si entonces y el resultado anterior se mantiene. Si es una extensión de de grado , entonces el polinomio linealizado
con en , es un operador lineal en sobre . Un polinomio linealizado permuta si y solo si 0 es la única raíz de en . Esta condición se puede expresar algebraicamente como
Los polinomios linealizados que son polinomios de permutación sobre que forman un grupo bajo la operación del módulo de composición , que se conoce como grupo de Betti-Mathieu, isomorfo al grupo lineal general .
Si está en el anillo polinómico y no tiene raíz distinta de cero en cuando divide a , y es primo relativo (coprimo) con respecto a , entonces permuta .
Solo se han caracterizado algunas otras clases específicas de polinomios de permutación sobre . Dos de ellos, por ejemplo, son:
donde divide a ; y
donde divide a .
Polinomios excepcionales Un polinomio excepcional sobre es un polinomio en que es un polinomio de permutación en para infinitos .
Un polinomio de permutación sobre de grado como máximo es excepcional sobre .
Cada permutación de es inducida por un polinomio excepcional.
Si un polinomio con coeficientes enteros (es decir, en ) es un polinomio de permutación sobre para infinitos primos , entonces es la composición de polinomios lineales y de Dickson (véase la conjetura de Schur a continuación).
Ejemplos geométricos
En geometría finita, las descripciones de coordenadas de ciertos conjuntos de puntos pueden proporcionar ejemplos de polinomios de permutación de mayor grado. En particular, los puntos que forman un óvalo en un plano proyectivo finito, con una potencia de 2, se pueden coordinar de tal manera que la relación entre las coordenadas esté dada por un óvalo, que es un tipo especial de polinomio de permutación sobre el cuerpo finito .
Complejidad computacional El problema de probar si un polinomio dado sobre un cuerpo finito es un polinomio de permutación se puede resolver en tiempo polinómico. Para investigaciones anteriores sobre este problema, consúltese:
Polinomios de permutación en varias variables sobre cuerpos finitos Un polinomio es un polinomio de permutación en variables sobre si la ecuación tiene exactamente soluciones en para cada .
Polinomios de permutación cuadrática (QPP) sobre anillos finitos
Para anillos finitos Z/nZ se pueden construir polinomios de permutación cuadrática. En realidad, es posible si y solo si n es divisible por p2 para algún número primo p. La construcción, sorprendentemente simple, puede producir permutaciones con ciertas propiedades notables. Es por eso que se ha utilizado como componente en el código de corrección de errores del turbo código en el estándar de telecomunicaciones móviles lTE (consúltese la especificación técnica 3GPP 36.212,3GPP TS 36.212 por ejemplo, la página 14 en la versión 8.8.0).
Ejemplos simples
Considérese para el anillo Z/4Z. Entonces, se comprueba que: luego el polinomio define la permutación
Considerar el mismo polinomio para el otro anillo Z/8Z. Entonces, se ve que: luego el polinomio define la permutación
Anillos Z/pkZ
Considérese para el anillo Z/pk Z.Lema: para k=1 (es decir, Z/pZ) dicho polinomio define una permutación solo en el caso de que a=0 y b no es igual a cero. Entonces, el polinomio no es cuadrático, sino lineal.Lema: para k>1, p>2 (Z/pkZ) dicho polinomio define un permutación si y solo si y .
Anillos Z/nZ
Considérese , donde pt son números primos.Lema: cualquier polinomio define una permutación sobre el anillo Z/nZ si y solo si todos los polinomios define las permutaciones para todos los anillos , donde son restos de módulo .
Como corolario, se pueden construir muchos polinomios de permutación cuadrática utilizando la siguiente construcción simple. Considérese , y supóngase que k1 >1.
Considérese , tal que , pero . Supóngase ahora que , i > 1. Y supóngase también que para todos los (por ejemplo, se pueden tomar y ). Entonces dicho polinomio define una permutación.
Para comprobarlo, se observa que para todos los primos pi, i > 1, la reducción de este polinomio cuadrático módulo pi es en realidad un polinomio lineal y, por tanto, es trivialmente una permutación. Para el primer número primo se debería usar el lema discutido anteriormente para ver que define la permutación.
Por ejemplo, considérese y el polinomio , que define la permutación
Polinomios de mayor grado sobre anillos finitos
Un polinomio g(x) para el anillo Z/pkZ es un polinomio de permutación si y solo si permuta el cuerpo finito Z/pZ y para todas las x en Z/pkZ''', donde g′(x) es la derivada formal de g(x).
Conjetura de Schur Sea K un cuerpo de números algebraicos y R el anillo de los números enteros. El término conjetura de Schur se refiere a la afirmación de que, si un polinomio f definido sobre K es un polinomio de permutación en R/P para infinitos ideales primos P, entonces f es la composición de los polinomios de Dickson, polinomios de grado uno y polinomios de la forma x''k. De hecho, Schur no hizo ninguna conjetura en esta dirección. La idea de que lo hizo se debe a Fried, quien dio una demostración errónea de una versión falsa del resultado. Turnwald y Müller han aportado pruebas correctas.
Referencias
Bibliografía
Categoría:Polinomios Categoría:Permutaciones