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 $x\mapsto g(x)$ 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 F_q= GF(q) el cuerpo finito de característica p, es decir, el cuerpo que tiene q elementos donde q= p^e es 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 sobre sí mismo definida por $c\mapsto f(c)$ es una permutación de F_q.​

Debido a la finitud de F_q, esta definición se puede expresar de varias formas equivalentes:​

• La función $c\mapsto f(c)$ es sobre (sobreyectiva).
• La función $c\mapsto f(c)$ es uno a uno (inyectiva).
• f(x)= a tiene una solución en F_q para cada a en F_q.
• f(x)= a tiene una solució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 Charles Hermite)​​ 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 $t\not \equiv 0\!{\pmod {p}}$, 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 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 xⁿ⁻¹ 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 Fq	q
$x$	cualquier $q$
$x^{2}$	$q\equiv 0\!{\pmod {2}}$
$x^{3}$	$q\not \equiv 1\!{\pmod {3}}$
$x^{3}-ax$ ($a$ no es un cuadrado)	$q\equiv 0\!{\pmod {3}}$
$x^{4}\pm 3x$	$q=7$
$x^{4}+a_{1}x^{2}+a_{2}x$ (si su única raíz en Fq es 0)	$q\equiv 0\!{\pmod {2}}$
$x^{5}$	$q\not \equiv 1\!{\pmod {5}}$
$x^{5}-ax$ ($a$ no es una cuarta potencia)	$q\equiv 0\!{\pmod {5}}$
$x^{5}+ax\,(a^{2}=2)$	$q=9$
$x^{5}\pm 2x^{2}$	$q=7$
$x^{5}+ax^{3}\pm x^{2}+3a^{2}x$ ($a$ no es un cuadrado)	$q=7$
$x^{5}+ax^{3}+5^{-1}a^{2}x$ ($a$ arbitrario)	$q\equiv \pm 2\!{\pmod {5}}$
$x^{5}+ax^{3}+3a^{2}x$ ($a$ no es un cuadrado)	$q=13$
$x^{5}-2ax^{3}+a^{2}x$ ($a$ no un es cuadrado)	$q\equiv 0\!{\pmod {5}}$

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.​

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.​

• xⁿ permuta GF(q) si y solo si n y q − 1 son coprimos (notacionalmente, (n, q − 1)= 1).​
• Si a está en GF(q) y n ≥ 1 entonces los polinomios de Dickson (del primer tipo) D_n(x,a) están definidos por

$D_{n}(x,a)=\sum _{j=0}^{\lfloor n/2\rfloor }{\frac {n}{n-j}}{\binom {n-j}{j}}(-a)^{j}x^{n-2j}.$

Esta expresión se obtiene de la relación de recurrencia

$D_{n}(x,a)=xD_{n-1}(x,a)-aD_{n-2}(x,a),$

con las condiciones iniciales $D_{0}(x,a)=2$ y $D_{1}(x,a)=x$.

Los primeros polinomios de Dickson son:

• $D_{2}(x,a)=x^{2}-2a$
• $D_{3}(x,a)=x^{3}-3ax$
• $D_{4}(x,a)=x^{4}-4ax^{2}+2a^{2}$
• $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.​ Si a= 0 entonces D_n(x, 0)= xⁿ y el resultado anterior se mantiene.

• Si GF(q^r) es una extensión de GF(q) de grado r, entonces el polinomio linealizado

$L(x)=\sum _{s=0}^{r-1}\alpha _{s}x^{q^{s}},$

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).​ Esta condición se puede expresar algebraicamente como​

$\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) que forman un grupo bajo la operación del módulo de composición $(x^{q^{r}}-x)$, que se conoce como grupo de Betti-Mathieu, isomorfo al grupo lineal general GL(r, F_q).​

• Si g(x) está en el anillo polinómico 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) con respecto a q − 1, entonces x^r(g(x^s))^{(q - 1)/s} permuta GF(q).​

• Solo se han caracterizado algunas otras clases específicas de polinomios de permutación sobre GF(q). Dos de ellos, por ejemplo, son:

$x^{(q+m-1)/m}+ax$

donde m divide a (q − 1); y

$x^{r}\left(x^{d}-a\right)^{\left(p^{n}-1\right)/d}$

donde d divide a (pⁿ − 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.​

Un polinomio de permutación sobre GF(q) de grado como máximo q^1/4 es excepcional sobre GF(q).​

Cada permutación de GF(q) es inducida por un polinomio excepcional.​

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​ (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, 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).

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.​

Polinomios de permutación en varias variables sobre cuerpos finitos

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

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 p² 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​, por ejemplo, la página 14 en la versión 8.8.0).

Ejemplos simples

Considérese $g(x)=2x^{2}+x$ para el anillo Z'/4Z. Entonces, se comprueba que: $g(0)=0$; $g(1)=3$; $g(2)=2$; $g(3)=1$, luego el polinomio define la permutación

${\begin{pmatrix}0&1&2&3\\0&3&2&1\end{pmatrix}}.$

Considerar el mismo polinomio $g(x)=2x^{2}+x$ para el otro anillo Z/8Z. Entonces, se ve que: $g(0)=0$; $g(1)=3$; $g(2)=2$; $g(3)=5$; $g(4)=4$; $g(5)=7$; $g(6)=6$; $g(7)=1$, luego el polinomio define la permutación

${\begin{pmatrix}0&1&2&3&4&5&6&7\\0&3&2&5&4&7&6&1\end{pmatrix}}.$

Anillos Z/p^kZ

Considérese $g(x)=ax^{2}+bx+c$ para el anillo Z/p^k 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/p^kZ) dicho polinomio define un permutación si y solo si $a\equiv 0{\pmod {p}}$ y $b\not \equiv 0{\pmod {p}}$.

Anillos Z/nZ

Considérese $n=p_{1}^{k_{1}}p_{2}^{k_{2}}...p_{l}^{k_{l}}$, donde p_t son números primos.

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

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

Considérese $ax^{2}+bx$, tal que $a=0{\bmod {p}}_{1}$, pero $a\neq 0{\bmod {p}}_{1}^{k_{1}}$. Supóngase ahora que $a=0{\bmod {p}}_{i}^{k_{i}}$, i > 1. Y supóngase también que $b\neq 0{\bmod {p}}_{i}$ para todos los i= 1, ..., l (por ejemplo, se pueden tomar $a=p_{1}p_{2}^{k_{2}}...p_{l}^{k_{l}}$ y $b=1$). Entonces dicho polinomio define una permutación.

Para comprobarlo, se observa 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, 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 Z/12Z y el polinomio $6x^{2}+x$, que define la permutación

${\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^kZ es un polinomio de permutación si y solo si permuta el cuerpo finito Z/pZ y $g'(x)\neq 0{\bmod {p}}$ para todas las x en Z/p^kZ, 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.​

Bibliografía

• Dickson, L. E. (1958) [1901]. Linear Groups with an Exposition of the Galois Field Theory. New York: Dover. 
• Lidl, Rudolf; Mullen, Gary L. (March 1988). «When Does a Polynomial over a Finite Field Permute the Elements of the Field?». The American Mathematical Monthly 95 (3): 243-246. doi:10.2307/2323626. 
• Lidl, Rudolf; Mullen, Gary L. (January 1993). «When Does a Polynomial over a Finite Field Permute the Elements of the Field?, II». The American Mathematical Monthly 100 (1): 71-74. doi:10.2307/2324822. 
• Lidl, Rudolf; Niederreiter, Harald (1997). Finite fields. Encyclopedia of Mathematics and Its Applications 20 (2nd edición). Cambridge University Press. ISBN 0-521-39231-4. Zbl 0866.11069.  Capítulo 7.
• Mullen, Gary L.; Panario, Daniel (2013). Handbook of Finite Fields. CRC Press. ISBN 978-1-4398-7378-6.  Capítulo 8.
• Shallue, C.J.; Wanless, I.M. (March 2013). «Permutation polynomials and orthomorphism polynomials of degree six». Finite Fields and Their Applications 20: 84-92. doi:10.1016/j.ffa.2012.12.003. 

• Datos: Q7169370