# 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:
* f tiene exactamente una raíz en F$_q$.
* 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$^{n−1}$ 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 F$_q$ | 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 F$_q$ 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$^n$ 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$^2$ − 1)= 1. Si a= 0 entonces D$_n$(x, 0)= x$^n$ 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$^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.
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$^2$ 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$^k$Z

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$^k$Z) 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 g(x)=a$_0$+∑$_{0<i≤M}$a$_i$x$^i${\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 g$_{pt}$(x)=a$_{0, pt}$+∑$_{0<i≤M}$a$_{i, pt}$x$^i${\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$ >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
    (012345678⋯0729411618⋯).{\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/pZ y $g'(x)\neq 0{\bmod {p}}$ para todas las x en Z/p$^k$Z, 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.