Polinomio de permutación

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ónEn 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.[1]​[2]​ Sea Fq= GF(q) el cuerpo finito de característica p, es decir, el cuerpo que tiene q elementos donde q= pe es algún primo p. Un polinomio f con coeficientes en Fq (escrito simbólicamente como f ∈ Fq[x]) es un polinomio de permutación de Fq si la función de Fq sobre sí mismo definida por[3]​ Debido a la finitud de Fq, esta definición se puede expresar de varias formas equivalentes:[4]​ Una caracterización de qué polinomios son polinomios de permutación viene dada por: (Criterio de Charles Hermite)[5]​[6]​ f ∈ Fq[x] es un polinomio de permutación de Fq si y solo si se cumplen las dos condiciones siguientes: Si f(x) es un polinomio de permutación definido sobre el cuerpo finito GF(q), entonces también lo es g(x)= a f(x + b) + c para todos los a ≠ 0, b y c en GF(q).El polinomio de permutación g(x) está en forma normalizada si a, b y c se eligen de modo que g(x) sea mónico, g(0)= 0 y (siempre que la característica p no divida el grado n del polinomio) el coeficiente de xn−1 sea 0.Hay muchas preguntas abiertas sobre los polinomios de permutación definidos sobre cuerpos finitos.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:[9]​[6]​ En Shallue y Wanless (2013) se puede encontrar una lista de todos los polinomios de permutación mónica de grado seis en forma normalizada.[10]​ 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.Los primeros polinomios de Dickson son: Si a ≠ 0 y n > 1 entonces Dn(x, a) permuta GF(q) si y solo si (n, q2 − 1)= 1.[13]​ Si a= 0 entonces Dn(x, 0)= xn y el resultado anterior se mantiene.Un polinomio linealizado L(x) permuta GF(qr) si y solo si 0 es la única raíz de L(x) en GF(qr).[12]​ Esta condición se puede expresar algebraicamente como[14]​ Los polinomios linealizados que son polinomios de permutación sobre GF(qr) 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 GL(r, Fq).[14]​ Un polinomio excepcional sobre GF(q) es un polinomio en Fq[x] que es un polinomio de permutación en GF(qm) para infinitos m.[15]​ Un polinomio de permutación sobre GF(q) de grado como máximo q1/4 es excepcional sobre GF(q).[16]​ Cada permutación de GF(q) es inducida por un polinomio excepcional.[16]​ Si un polinomio con coeficientes enteros (es decir, en ℤ[x]) es un polinomio de permutación sobre GF(p) para infinitos primos p, entonces es la composición de polinomios lineales y de Dickson[17]​ (véase la conjetura de Schur a continuación).En particular, los puntos que forman un óvalo en un plano proyectivo finito, PG(2,q) con q 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 GF(q).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.[19]​ 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[20]​, por ejemplo, la página 14 en la versión 8.8.0).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.Como corolario, se pueden construir muchos polinomios de permutación cuadrática utilizando la siguiente construcción simple.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.[21]​ Sea K un cuerpo de números algebraicos y R el anillo de los números enteros.De hecho, Schur no hizo ninguna conjetura en esta dirección.La idea de que lo hizo se debe a Fried,[22]​ quien dio una demostración errónea de una versión falsa del resultado.Turnwald[23]​ y Müller han aportado pruebas correctas.