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ón es 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 polinómica. ${\displaystyle x\mapsto g(x)}$

En el caso de anillos finitos Z / n Z , dichos polinomios también se han estudiado y aplicado en el componente entrelazador de algoritmos de detección y corrección de errores . ^{[1] [2]}

Polinomios de permutación de variable única sobre campos finitos

Sea F _q = GF( q ) el campo finito de 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 (escrito simbólicamente como f ∈ F _q [ x ] ) es un polinomio de permutación de F _q si la función de F _q hacia sí misma definida por es una permutación de F _q . ^[3] ${\displaystyle c\mapsto f(c)}$

Debido a la finitud de F _q , esta definición se puede expresar de varias maneras equivalentes: ^[4]

• la función es sobre ( sobreyectiva ); ${\displaystyle c\mapsto f(c)}$
• la función es uno a uno ( inyectiva ); ${\displaystyle c\mapsto f(c)}$
• 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 dos condiciones siguientes:

1. f tiene exactamente una raíz en F _q ;
2. 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 . ${\displaystyle t\not \equiv 0\!{\pmod {p}}}$

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 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 x ^{n −1} es 0.

Hay muchas preguntas abiertas sobre los polinomios de permutación definidos sobre cuerpos finitos. ^{[7] [8]}

pequeño grado

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 campos finitos. Estos resultados son: ^{[9] [6]}

En Shallue & Wanless (2013) se puede encontrar una lista de todos los polinomios de permutación mónica de grado seis en forma normalizada. ^[10]

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. ^[11]

• x ⁿ permuta GF( q ) si y solo si n y q − 1 son coprimos (notacionalmente, ( n , q − 1) = 1 ). ^[12]
• Si a está en GF( q ) y n ≥ 1 entonces el polinomio de Dickson (de primera especie) D _n ( x , a ) se define por $${\displaystyle D_{n}(x,a)=\sum _{j=0}^{\lfloor n/2\rfloor }{\frac {n}{n-j}}{\binom {n-j}{j}}(-a)^{j}x^{n-2j}.}$$

Estos también se pueden obtener de la recursividad con las condiciones iniciales y . Los primeros polinomios de Dickson son: $${\displaystyle D_{n}(x,a)=xD_{n-1}(x,a)-aD_{n-2}(x,a),}$$ ${\displaystyle D_{0}(x,a)=2}$ ${\displaystyle D_{1}(x,a)=x}$

• ${\displaystyle D_{2}(x,a)=x^{2}-2a}$
• ${\displaystyle D_{3}(x,a)=x^{3}-3ax}$
• ${\displaystyle D_{4}(x,a)=x^{4}-4ax^{2}+2a^{2}}$
• ${\displaystyle D_{5}(x,a)=x^{5}-5ax^{3}+5a^{2}x.}$

Si a ≠ 0 y n > 1 entonces D _n ( x , a ) permuta GF( q ) si y sólo si ( n , q ² − 1) = 1 . ^[13] Si a = 0 entonces D _n ( x , 0) = x ⁿ y se cumple el resultado anterior.

• 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 ) . ^[12] Esta condición se puede expresar algebraicamente como ^[14] $${\displaystyle L(x)=\sum _{s=0}^{r-1}\alpha _{s}x^{q^{s}},}$$ $${\displaystyle \det \left(\alpha _{i-j}^{q^{j}}\right)\neq 0\quad (i,j=0,1,\ldots ,r-1).}$$

Los polinomios linealizados que son polinomios de permutación sobre GF( qr ⁾ forman un grupo bajo la operación de módulo de composición , que se conoce como grupo _de Betti-Mathieu, isomorfo al grupo lineal general GL( r , Fq ) . ^[14] ${\displaystyle x^{q^{r}}-x}$

• Si g ( x ) está en el anillo polinomial F _q [ x ] y g ( x ^s ) no tiene raíz distinta de cero en GF( q ) cuando s divide q − 1 , y r > 1 es primo relativo (coprimo) con respecto 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 ellos, por ejemplo, son: donde m divide q − 1 y donde d divide p ⁿ − 1 . $${\displaystyle x^{(q+m-1)/m}+ax}$$ $${\displaystyle x^{r}\left(x^{d}-a\right)^{\left(p^{n}-1\right)/d}}$$

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 una infinidad de m . ^[15]

Un polinomio de permutación sobre GF( q ) de grado como máximo q ^1/4 es excepcional sobre GF( q ) . ^[dieciséis]

Cada permutación de GF( q ) es inducida por un polinomio excepcional. ^[dieciséis]

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. ^[17] (Ver 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 , PG(2, q ) con q una potencia de 2, pueden coordinarse de tal manera que la relación entre las coordenadas esté dada por un polinomio o , 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 cuerpo finito es un polinomio de permutación se puede resolver en tiempo polinomial . ^[18]

Polinomios de permutación en varias variables sobre campos finitos

Un polinomio es un polinomio de permutación en n variables si la ecuación tiene exactamente soluciones para cada una . ^[19] ${\displaystyle f\in \mathbb {F} _{q}[x_{1},\ldots ,x_{n}]}$ ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle f(x_{1},\ldots ,x_{n})=\alpha }$ ${\displaystyle q^{n-1}}$ ${\displaystyle \mathbb {F} _{q}^{n}}$ ${\displaystyle \alpha \in \mathbb {F} _{q}}$

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 sólo si n es divisible por p ² 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 entrelazador 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 ^[20] , por ejemplo, página 14 en la versión 8.8.0).

Ejemplos simples

Considere el anillo Z /4 Z . Uno ve: ; ; ; , entonces el polinomio define la permutación ${\displaystyle g(x)=2x^{2}+x}$ ${\displaystyle g(0)=0}$ ${\displaystyle g(1)=3}$ ${\displaystyle g(2)=2}$ ${\displaystyle g(3)=1}$ $${\displaystyle {\begin{pmatrix}0&1&2&3\\0&3&2&1\end{pmatrix}}.}$$

Considere el mismo polinomio para el otro anillo Z / 8 Z. Uno ve: ; ; ; ; ; ; ; , entonces el polinomio define la permutación ${\displaystyle g(x)=2x^{2}+x}$ ${\displaystyle g(0)=0}$ ${\displaystyle g(1)=3}$ ${\displaystyle g(2)=2}$ ${\displaystyle g(3)=5}$ ${\displaystyle g(4)=4}$ ${\displaystyle g(5)=7}$ ${\displaystyle g(6)=6}$ ${\displaystyle g(7)=1}$ $${\displaystyle {\begin{pmatrix}0&1&2&3&4&5&6&7\\0&3&2&5&4&7&6&1\end{pmatrix}}.}$$

Anillos Z/paquete​z

Considere el anillo Z / p ^k Z . ${\displaystyle g(x)=ax^{2}+bx+c}$

Lema: para k =1 (es decir, Z / p Z ), dicho polinomio define una permutación sólo en el caso de 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 ) dicho polinomio define una permutación si y solo si y . ${\displaystyle a\equiv 0{\pmod {p}}}$ ${\displaystyle b\not \equiv 0{\pmod {p}}}$

Anillos Z/nortez

Considere , donde p _t son números primos. ${\displaystyle n=p_{1}^{k_{1}}p_{2}^{k_{2}}...p_{l}^{k_{l}}}$

Lema: cualquier polinomio define una permutación para el anillo Z / n Z si y solo si todos los polinomios definen las permutaciones para todos los anillos , donde están los restos de módulo . ${\textstyle g(x)=a_{0}+\sum _{0<i\leq M}a_{i}x^{i}}$ ${\textstyle g_{p_{t}}(x)=a_{0,p_{t}}+\sum _{0<i\leq M}a_{i,p_{t}}x^{i}}$ ${\displaystyle Z/p_{t}^{k_{t}}Z}$ ${\displaystyle a_{j,p_{t}}}$ ${\displaystyle a_{j}}$ ${\displaystyle p_{t}^{k_{t}}}$

Como corolario, se pueden construir muchos polinomios de permutación cuadrática utilizando la siguiente construcción simple. Considere , suponga que k ₁ >1. ${\displaystyle n=p_{1}^{k_{1}}p_{2}^{k_{2}}\dots p_{l}^{k_{l}}}$

Considere , tal que , pero ; supongamos que , i > 1. Y supongamos que para todo i = 1, ..., l . (Por ejemplo, se puede tomar y ). Entonces dicho polinomio define una permutación. ${\displaystyle ax^{2}+bx}$ ${\displaystyle a=0{\bmod {p}}_{1}}$ ${\displaystyle a\neq 0{\bmod {p}}_{1}^{k_{1}}}$ ${\displaystyle a=0{\bmod {p}}_{i}^{k_{i}}}$ ${\displaystyle b\neq 0{\bmod {p}}_{i}}$ ${\displaystyle a=p_{1}p_{2}^{k_{2}}...p_{l}^{k_{l}}}$ ${\displaystyle b=1}$

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 deberíamos usar el lema discutido anteriormente para ver que define la permutación.

Por ejemplo, considere Z /12 Z y polinomio . Define una permutación. ${\displaystyle 6x^{2}+x}$ ${\begin{pmatrix}0&1&2&3&4&5&6&7&8&\cdots \\0&7&2&9&4&11&6&1&8&\cdots \end{pmatrix}}.$

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 cuerpo finito Z / p Z y para todo x en Z / p ^k Z , donde g ′ ( x ) es el derivada formal de g ( x ). ^[21] ${\displaystyle g'(x)\neq 0{\bmod {p}}}$

La 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 infinitos ideales primos P , entonces f es la composición de 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 idea de que lo hizo se debe a Fried, ^[22] quien dio una prueba errónea de una versión falsa del resultado. Turnwald ^[23] y Müller han aportado pruebas correctas . ^[24]

Notas

1. Takeshita, Óscar (2006). "Intercaladores polinómicos 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.
2. Takeshita, Óscar (2005). "Una nueva construcción para códigos LDPC que utilizan polinomios de permutación sobre anillos enteros". arXiv : cs/0506091 .
3. Mullen y Panario 2013, pag. 215
4. Lidl y Niederreiter 1997, pág. 348
5. Lidl y Niederreiter 1997, pág. 349
6. Mullen y Panario 2013, pag. 216
7. Lidl y Mullen (1988)
8. Lidl y Mullen (1993)
9. Dickson 1958, pág. 63
10. Mullen y Panario 2013, pag. 217
11. Lidl y Mullen 1988, pág. 244
12. Lidl y Niederreiter 1997, pág. 351
13. Lidl y Niederreiter 1997, pág. 356
14. Lidl y Niederreiter 1997, pág. 362
15. Mullen y Panario 2013, pag. 236
16. Mullen y Panario 2013, p. 238
17. Mullen y Panario 2013, pag. 239
18. Kayal, Neeraj (2005). "Reconocimiento de funciones de permutación en tiempo polinómico". Coloquio Electrónico sobre Complejidad Computacional . ECCC  TR05-008.Para investigaciones anteriores sobre este problema, ver: 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.
19. Mullen y Panario 2013, pag. 230
20. 3GPP TS 36.212
21. Sol, Jing; Takeshita, Óscar (2005). "Intercalador para códigos turbo que utilizan polinomios de permutación sobre anillos enteros". Transacciones IEEE sobre teoría de la información . 51 (1): 102.
22. Frito, M. (1970). "Sobre una conjetura de Schur". Matemáticas de Michigan. J .: 41–55.
23. Turnwald, G. (1995). "Sobre la conjetura de Schur". J.Austral. Matemáticas. Soc. : 312–357.
24. Muller, P. (1997). "Una prueba gratuita encuadernada con Weil 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 campos 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?". El Mensual Matemático Estadounidense . 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". El Mensual Matemático Estadounidense . 100 (1): 71–74. doi :10.2307/2324822.
• Lidl, Rudolf; Niederreiter, Harald (1997). Campos finitos . Enciclopedia de Matemáticas y sus aplicaciones. vol. 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 .