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, el mapaes una biyección . En caso de que el anillo sea un campo finito , los polinomios de Dickson , que están estrechamente relacionados con los polinomios de Chebyshev , proporcionan ejemplos. Sobre un campo finito, cada función, y en particular cada permutación de los elementos de ese campo, puede escribirse como una función polinomial.
En el caso de anillos finitos Z / n Z , dichos polinomios también se han estudiado y aplicado en el componente intercalador de los algoritmos de detección y corrección de errores . [1] [2]
Polinomios de permutación de una sola variable sobre campos finitos
Sea F q = GF ( q ) el campo finito de la característica p , es decir, el campo que tiene q elementos donde q = p e para algún primo p . Un polinomio f con coeficientes en F q (simbólicamente escrito como f ∈ F q [ x ] ) es un polinomio de permutación de F q si la función de F q a sí misma definida pores una permutación de F q . [3]
Debido a la finitud de F q , esta definición se puede expresar de varias formas equivalentes: [4]
- la función es sobre ( sobreyectiva );
- la función es uno a uno ( inyectivo );
- f ( x ) = a tiene una solución en F q para cada a en F q ;
- f ( x ) = a tiene unasolución única en F q para cada a en F q .
Una caracterización de qué polinomios son polinomios de permutación viene dada por
( Criterio de Hermite ) [5] [6] f ∈ F q [ x ] es un polinomio de permutación de F q si y solo si se cumplen las siguientes dos condiciones:
- f tiene exactamente una raíz en F q ;
- para cada entero t con 1 ≤ t ≤ q - 2 y, la reducción de f ( x ) t mod ( x q - x ) tiene grado ≤ q - 2 .
Si f ( x ) es un polinomio de permutación definido sobre el campo finito GF ( q ) , entonces también lo es g ( x ) = a f ( x + b ) + c para todo a ≠ 0, b y c en GF ( q ) . El polinomio de permutación g ( x ) está en forma normalizada si a , b y cse eligen de modo que g ( x ) sea monico , g (0) = 0 y (siempre que la característica p no divida el grado n del polinomio) el coeficiente de x n -1 sea 0.
Hay muchas preguntas abiertas sobre polinomios de permutación definidos sobre campos finitos (ver Lidl y Mullen (1988) y Lidl y Mullen (1993) ).
Pequeño grado
El criterio de Hermite es computacionalmente intensivo y puede ser difícil de usar 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 campos finitos. Estos resultados son: [7] [6]
Polinomio de permutación normalizado de F q q alguna ( no es un cuadrado) (si su única raíz en F q es 0) ( no un cuarto poder) ( no es un cuadrado) ( arbitrario) ( no es un cuadrado) ( no es un cuadrado)
Se puede encontrar una lista de todos los polinomios de permutación mónica de grado seis en forma normalizada en Shallue & Wanless (2013) . [8]
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 campos finitos. [9]
- x n permuta GF ( q ) si y solo si n y q - 1 son coprimos (en notación, ( n , q - 1) = 1 ). [10]
- Si a está en GF ( q ) y n ≥ 1 entonces el polinomio de Dickson (del primer tipo) D n ( x , a ) se define por
Estos también se pueden obtener de la recursividad
con las condiciones iniciales y . Los primeros polinomios de Dickson son:
Si a ≠ 0 y n > 1 entonces D n ( x , a ) permuta GF ( q ) si y solo si ( n , q 2 - 1) = 1 . [11] Si a = 0 entonces D n ( x , 0) = x n y el resultado anterior se cumple.
- Si GF ( q r ) es una extensión de GF ( q ) de grado r , entonces el polinomio linealizado
- con α s en GF ( q r ) , es un operador lineal en GF ( q r ) sobre GF ( q ) . Un polinomio linealizado L ( x ) permuta GF ( q r ) si y solo si 0 es la única raíz de L ( x ) en GF ( q r ) . [10] Esta condición se puede expresar algebraicamente como [12]
Los polinomios linealizados que son polinomios de permutación sobre GF ( q r ) forman un grupo bajo la operación de composición módulo, que se conoce como el grupo Betti-Mathieu, isomorfo al grupo lineal general GL ( r , F q ) . [12]
- Si g ( x ) está en el anillo polinomial F q [ x ] y g ( x s ) no tiene una raíz distinta de cero en GF ( q ) cuando s divide a q - 1 , y r > 1 es relativamente primo (coprimo) a q - 1 , entonces x r ( g ( x s )) ( q - 1) / s permuta GF ( q ) . [6]
- Sólo se han caracterizado algunas otras clases específicas de polinomios de permutación sobre GF ( q ) . Dos de estos, por ejemplo, son:
- donde m divide q - 1 , y
- donde d divide p n - 1 .
Polinomios excepcionales
Un polinomio excepcional sobre GF ( q ) es un polinomio en F q [ x ] que es un polinomio de permutación en GF ( q m ) para infinitos m . [13]
Un polinomio de permutación sobre GF ( q ) de grado como máximo q 1/4 es excepcional sobre GF ( q ) . [14]
Cada permutación de GF ( q ) es inducida por un polinomio excepcional. [14]
Si un polinomio con coeficientes enteros (es decir, en ℤ [ x ] ) es un polinomio de permutación sobre GF ( p ) para infinitos números primos p , entonces es la composición de polinomios lineales y de Dickson. [15] (Ver la conjetura de Schur más abajo).
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 , PG (2, q ) con q una potencia de 2, se pueden coordinar de tal manera que la relación entre las coordenadas viene dada por un o-polinomio , que es un tipo especial de polinomio de permutación sobre el campo finito GF ( q ) .
Complejidad computacional
El problema de probar si un polinomio dado sobre un campo finito es un polinomio de permutación puede resolverse en tiempo polinomial . [dieciséis]
Polinomios de permutación en varias variables sobre campos finitos
Un polinomio es un polinomio de permutación en n variables sobre si la ecuación tiene exactamente soluciones en para cada . [17]
Polinomios de permutación cuadrática (QPP) sobre anillos finitos
Para el anillo finito Z / n Z se pueden construir polinomios de permutación cuadráticos. En realidad, es posible si y solo si n es divisible por p 2 para algún número primo p . La construcción es sorprendentemente simple, sin embargo, puede producir permutaciones con ciertas buenas propiedades. Es por eso que se ha utilizado en el componente intercalador de códigos turbo en el estándar de telecomunicaciones móviles 3GPP Long Term Evolution (consulte la especificación técnica 3GPP 36.212 [18], por ejemplo, página 14 en la versión 8.8.0).
Ejemplos sencillos
Considerar para el anillo Z / 4 Z . Uno ve:, entonces el polinomio define la permutación
- .
Considere el mismo polinomio para el otro anillo Z / 8 Z . Uno ve:, entonces el polinomio define la permutación
- .
Anillos Z / p k Z
Considerar para el anillo Z / p k Z .
Lema: para k = 1 (es decir, Z / p Z ) tales define polinómicas una permutación sólo en el caso 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 / p k Z ) tal polinomio define una permutación si y solo si y .
Anillos Z / n Z
Considerar , donde p t son números primos.
Lema: cualquier polinomio define una permutación para el anillo Z / n Z si y solo si todos los polinomios define las permutaciones para todos los anillos , dónde son restos de modulo .
Como corolario, se pueden construir muchos polinomios de permutación cuadrática utilizando la siguiente construcción simple. Considerar, suponga que k 1 > 1 .
Considerar , tal que , pero ; asumir que, i > 1. Y asume quepara todo i = 1 ... l . (Por ejemplo, uno puede tomar y ). Entonces tal polinomio define una permutación.
Para ver esto, observamos que para todos los primos p i , i > 1, la reducción de este polinomio cuadrático módulo p i es en realidad un polinomio lineal y, por lo tanto, es una permutación por razón trivial. Para el primer número primo debemos usar el lema discutido anteriormente para ver que define la permutación.
Por ejemplo, considere Z / 12 Z y polinomio. Define una permutación
- .
Polinomios de mayor grado sobre anillos finitos
Un polinomio g ( x ) para el anillo Z / p k Z es un polinomio de permutación si y solo si permuta el campo finito Z / p Z ypara todo x en Z / p k Z , donde g ′ ( x ) es la derivada formal de g ( x ). [19]
Conjetura de Schur
Sea K un campo numérico algebraico con R el anillo de 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 un número infinito de 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 este sentido. La noción de que lo hizo se debe a Fried, [20] quien dio una prueba defectuosa de una versión falsa del resultado. Turnwald [21] y Müller han dado pruebas correctas . [22]
Notas
- ^ Takeshita, Oscar (2006). "Intercaladores de polinomios de permutación: una perspectiva algebraico-geométrica". Transacciones IEEE sobre teoría de la información . 53 : 2116–2132. arXiv : cs / 0601048 . doi : 10.1109 / TIT.2007.896870 .
- ^ Takeshita, Oscar (2005). "Una nueva construcción para códigos LDPC utilizando polinomios de permutación sobre anillos enteros". arXiv : cs / 0506091 .
- ^ Mullen y Panario , 2013 , p. 215
- ^ Lidl y Niederreiter 1997 , p. 348
- ^ Lidl y Niederreiter 1997 , p. 349
- ↑ a b c Mullen y Panario , 2013 , p. 216
- ^ Dickson 1958 , pág. 63
- ^ Mullen y Panario , 2013 , p. 217
- ^ Lidl y Mullen 1988 , p. 244
- ↑ a b Lidl y Niederreiter , 1997 , p. 351
- ^ Lidl y Niederreiter 1997 , p. 356
- ↑ a b Lidl y Niederreiter , 1997 , p. 362
- ^ Mullen y Panario , 2013 , p. 236
- ↑ a b Mullen y Panario , 2013 , p. 238
- ^ Mullen y Panario , 2013 , p. 239
- ^ Kayal, Neeraj (2005). "Reconocimiento de funciones de permutación en tiempo polinomial". ECCC TR05-008 . Falta o está vacío
|url=
( ayuda ) Para una investigación anterior sobre este problema, consulte: Ma, Keju; von zur Gathen, Joachim (1995). "La complejidad computacional de reconocer funciones de permutación". Complejidad computacional . 5 (1): 76–97. doi : 10.1007 / BF01277957 . Señor 1319494 .Shparlinski, IE (1992). "Una prueba determinista para polinomios de permutación". Complejidad computacional . 2 (2): 129-132. doi : 10.1007 / BF01202000 . Señor 1190826 .. - ^ Mullen y Panario , 2013 , p. 230
- ^ 3GPP TS 36.212
- ^ Sun, Jing; Takeshita, Oscar (2005). "Intercalador para códigos Turbo usando polinomios de permutación sobre anillos enteros". Transacciones IEEE sobre teoría de la información . 51 (1): 102.
- ^ Fried, M. (1970). "Sobre una conjetura de Schur". Michigan Math. J .: 41–55.
- ^ Turnwald, G. (1995). "Sobre la conjetura de Schur". J. Austral. Matemáticas. Soc. : 312–357.
- ^ Müller, P. (1997). "Una prueba gratuita de Weil-bound de la conjetura de Schur". Campos finitos y sus aplicaciones : 25–32.
Referencias
- Dickson, LE (1958) [1901]. Grupos lineales con una exposición de la teoría de campo de Galois . Nueva York: Dover.
- Lidl, Rudolf; Mullen, Gary L. (marzo de 1988). "¿Cuándo un polinomio sobre un campo finito permuta los elementos del campo?". The American Mathematical Monthly . 95 (3): 243–246. doi : 10.2307 / 2323626 .
- Lidl, Rudolf; Mullen, Gary L. (enero de 1993). "¿Cuándo un polinomio sobre un campo finito permuta los elementos del campo ?, II". The American Mathematical Monthly . 100 (1): 71–74. doi : 10.2307 / 2324822 .
- Lidl, Rudolf; Niederreiter, Harald (1997). Campos finitos . Enciclopedia de las matemáticas y sus aplicaciones. 20 (2ª ed.). Prensa de la Universidad de Cambridge . ISBN 0-521-39231-4. Zbl 0866.11069 . Capítulo 7.
- Mullen, Gary L .; Panario, Daniel (2013). Manual de campos finitos . Prensa CRC. ISBN 978-1-4398-7378-6. Capítulo 8.
- Shallue, CJ; Wanless, IM (marzo de 2013). "Polinomios de permutación y polinomios de ortomorfismo de grado seis" . Campos finitos y sus aplicaciones . 20 : 84–92. doi : 10.1016 / j.ffa.2012.12.003 .