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 función es una biyección . En caso de que el anillo sea un cuerpo finito , los polinomios de Dickson , que están estrechamente relacionados con los polinomios de Chebyshev , proporcionan ejemplos. Sobre un cuerpo finito, cada función, y en particular cada permutación de los elementos de ese cuerpo, se puede escribir 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 una sola variable sobre cuerpos finitos

Sea F _q = GF( q ) el cuerpo finito de característica p , es decir, el cuerpo 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 a 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 formas equivalentes: ^[4]

• la función es 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 cuerpo finito GF( q ) , entonces también lo es g ( x ) = a f ( x + b ) + c para todos 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} sea 0.

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

Grado pequeño

El criterio de Hermite requiere un gran esfuerzo computacional y puede resultar difícil de utilizar para extraer conclusiones teóricas. Sin embargo, Dickson pudo utilizarlo para encontrar todos los polinomios de permutación de grado cinco como máximo en todos los cuerpos finitos. Estos resultados son: ^{[9] [6]}

Se puede encontrar una lista de todos los polinomios de permutación mónica de grado seis en forma normalizada en Shallue y Wanless (2013). ^[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 campos finitos. ^[11]

• x ⁿ permuta GF( q ) si y sólo 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 (del primer tipo) D _n ( x , a ) está definido 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 a partir de la recursión 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 solo si ( n , q ² − 1) = 1 . ^[13] Si a = 0 entonces D _n ( x , 0) = x ⁿ 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 sobre 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( q ^r ) forman un grupo bajo la operación de composición módulo , que se conoce como grupo de Betti-Mathieu, isomorfo al grupo lineal general GL( r , F _q ) . ^[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 a q − 1 , y r > 1 es primo relativo (coprimo) a q − 1 , entonces x ^r ( g ( x ^s )) ^{( q - 1)/ s} permuta GF( q ) . ^[6]
• Sólo se han caracterizado unas pocas clases específicas de polinomios de permutación sobre GF( q ) . Dos de ellas, por ejemplo, son: donde m divide a q − 1 , y donde d divide a 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 sobre GF( q ^m ) para infinitos m . ^[15]

Un polinomio de permutación sobre GF( q ) de grado como máximo q ^1/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).

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 grado superior. 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 o-polinomio , que es un tipo especial de polinomio de permutación sobre el cuerpo finito GF( q ) .

Complejidad computacional

El problema de comprobar si un polinomio dado sobre un campo finito es un polinomio de permutación se puede resolver en tiempo polinomial . ^[18]

Polinomios de permutación en varias variables sobre cuerpos finitos

Un polinomio es un polinomio de permutación en n variables sobre si la ecuación tiene exactamente soluciones en para cada . ^[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ática. En realidad, esto es posible si y sólo si n es divisible por p ² para algún número primo p . La construcción es sorprendentemente sencilla, pero puede producir permutaciones con ciertas buenas propiedades. Por eso se ha utilizado en el componente de intercalación de códigos turbo en el estándar de telecomunicaciones móviles 3GPP Long Term Evolution (véase la especificación técnica 36.212 ^[20] de 3GPP , p. ej., página 14 en la versión 8.8.0).

Ejemplos sencillos

Consideremos para el anillo Z /4 Z . Se ve: ; ; ; , por lo que 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}}.}$$

Consideremos el mismo polinomio para el otro anillo Z / 8 Z . Se ve: ; ; ; ; ; ; ; , por lo que 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​O

Consideremos para 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 solo en el caso de que a = 0 y b no sea igual a cero. Por lo tanto, 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 . ${\displaystyle a\equiv 0{\pmod {p}}}$ ${\displaystyle b\not \equiv 0{\pmod {p}}}$

Anillos Z/norteO

Consideremos , 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 sólo si todos los polinomios definen las permutaciones para todos los anillos , donde son residuos 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}}}$

Consideremos , 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 comprobarlo, 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 tanto, una permutación por razones triviales. Para el primer número primo, deberíamos utilizar el lema que hemos analizado anteriormente para ver que define la permutación.

Por ejemplo, considere Z /12 Z y el 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 grado superior sobre anillos finitos

Un polinomio g ( x ) para el anillo Z / p ^k Z es un polinomio de permutación si y sólo si permuta el cuerpo finito Z / p Z y para todo x en Z / p ^k Z , donde g ′( x ) es la derivada formal de g ( x ). ^[21] ${\displaystyle g'(x)\neq 0{\bmod {p}}}$

Conjetura de Schur

Sea K un cuerpo de números algebraicos con R el anillo de los 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 sobre 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 esta dirección. La idea de que lo hizo se debe a Fried, ^[22] quien dio una prueba defectuosa de una versión falsa del resultado. Turnwald ^[23] y Müller han dado pruebas correctas. ^[24]

Notas

1. Takeshita, Oscar (2006). "Intercaladores polinomiales de permutación: una perspectiva algebraico-geométrica". IEEE Transactions on Information Theory . 53 : 2116–2132. arXiv : cs/0601048 . doi :10.1109/TIT.2007.896870.
2. Takeshita, Oscar (2005). "Una nueva construcción para códigos LDPC utilizando 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, pág. 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 polinomial". Coloquio electrónico sobre complejidad computacional . ECCC  TR05-008.Para investigaciones anteriores sobre este problema, véase: Ma, Keju; von zur Gathen, Joachim (1995). "La complejidad computacional del reconocimiento de funciones de permutación". Computational Complexity . 5 (1): 76–97. doi :10.1007/BF01277957. MR  1319494. Shparlinski, IE (1992). "Una prueba determinista para polinomios de permutación". Computational Complexity . 2 (2): 129–132. doi :10.1007/BF01202000. MR  1190826.
19. Mullen y Panario 2013, pag. 230
20. 3GPP TS 36.212
21. Sun, Jing; Takeshita, Oscar (2005). "Intercalador para códigos turbo que utilizan polinomios de permutación sobre anillos enteros". IEEE Transactions on Information Theory . 51 (1): 102.
22. Fried, M. (1970). "Sobre una conjetura de Schur". Michigan Math. J. : 41–55.
23. Turnwald, G. (1995). "Sobre la conjetura de Schur". J. Austral. Math. Soc. : 312–357.
24. Müller, P. (1997). "Una prueba libre de la conjetura de Schur, limitada por Weil". 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 cuerpo finito permuta los elementos del cuerpo?". 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 cuerpo finito permuta los elementos del cuerpo?, II". The American Mathematical Monthly . 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.). Cambridge University Press . ISBN 0-521-39231-4.Zbl 0866.11069  . Capítulo 7.
• Mullen, Gary L.; Panario, Daniel (2013). Manual de campos finitos . CRC Press. 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 .