Polinomio de permutación
# Polinomio de permutación

En matemáticas, un polinomio de permutación (para un anillo dado) es un polinomio que actúa como un permutación de los elementos del anillo, es decir, el mapa $x\mapsto g(x)$ es un función biyectiva. En caso de que el anillo sea un cuerpo finito, los Polinomios de Dickson, que están estrechamente relacionados con el Polinomios de Chebyshov, 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.

En el caso de anillos finitos Z/nZ, dichos polinomios también se han estudiado y aplicado en el componente código de corrección de errores de los algoritmos detección y corrección de errores.

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

Sea $F_q=$ GF(q) el campo finito de characteristic p, es decir, el campo que tiene elementos q 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$ a 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 (surjective);
* la función $c\mapsto f(c)$ es uno a uno (injective);
* 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 campo 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 monic, 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 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:

| Normalized Permutation Polynomial of $F_q$ | q |
| - | - |
| $x$ | any $q$ |
| $x^{2}$ | $q\equiv 0\!{\pmod {2}}$ |
| $x^{3}$ | $q\not \equiv 1\!{\pmod {3}}$ |
| $x^{3}-ax$ ($a$ not a square) | $q\equiv 0\!{\pmod {3}}$ |
| $x^{4}\pm 3x$ | $q=7$ |
| $x^{4}+a_{1}x^{2}+a_{2}x$ (if its only root in $F_q$ is 0) | $q\equiv 0\!{\pmod {2}}$ |
| $x^{5}$ | $q\not \equiv 1\!{\pmod {5}}$ |
| $x^{5}-ax$ ($a$ not a fourth power) | $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$ not a square) | $q=7$ |
| $x^{5}+ax^{3}+5^{-1}a^{2}x$ ($a$ arbitrary) | $q\equiv \pm 2\!{\pmod {5}}$ |
| $x^{5}+ax^{3}+3a^{2}x$ ($a$ not a square) | $q=13$ |
| $x^{5}-2ax^{3}+a^{2}x$ ($a$ not a square) | $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 coprime (notacionalmente, (n, q − 1)= 1).
* Si a está en GF(q) y n ≥ 1 entonces el Polinomios de Dickson (del primer tipo) $D_n(x,a)$ está definido 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}.$ y se obtendrá de recursion

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

al condiciones $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 un extension de GF(q) de grado r, entonces el linearized polynomial $L(x)=\sum _{s=0}^{r-1}\alpha _{s}x^{q^{s}},$ub>s}}en $GF(q^r),$ es un aplicación 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).$

, que son polinomios de permutación sobre $GF(q^r)$ que forman un group 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$|q − 1}} y $$x^{r}\left(x^{d}-a\right)^{\left(p^{n}-1\right)/d}|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. (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 oval 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 (plano proyectivo), 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 complejidad temporal.

## Polinomios de permutación en varias variables sobre campos finitos

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

## Polinomios de permutación cuadrática (QPP) sobre anillos finitos

Para finite ring 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 es sorprendentemente simple, sin embargo puede producir permutaciones con ciertas buenas propiedades. Es por eso que se ha utilizado en el componente código de corrección de errores de turbo código en el estándar de telecomunicaciones móviles lTE (telecomunicaciones) (consulte la especificación técnica 3GPP 36.212, por ejemplo, la página 14 en la versión 8.8.0).

### Ejemplos simples

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

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

$g(x)=2x^{2}+x$ para el otro anillo Z/8Z.

Se ve: $g(0)=0$; $g(1)=3$; $g(2)=2$; $g(3)=5$; $g(4)=4$; $g(5)=7$; $g(6)=6$; $g(7)=1$, entonces 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}}.$

>Z===

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

Lema:' para k=1 (es decir, Z/pZ) dicho polinomio define una permutación solo en el caso a=0 y b no son iguales 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}}$.

Considere $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_ix^i{\textstyle$ g(x)=a_{0}+\sum _{0<i\leq M}a_{i}x^{i}}g 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}} forman 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. Considere $n=p_{1}^{k_{1}}p_{2}^{k_{2}}\dots p_{l}^{k_{l}}$, suponga que $k_1$ >1.

Considere $ax^{2}+bx$, tal que $a=0{\bmod {p}}_{1}$, pero $a\neq 0{\bmod {p}}_{1}^{k_{1}}$; supongamos que $a=0{\bmod {p}}_{i}^{k_{i}}$, i > 1. Y supongamos 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 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 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/12Z y el polinomio $6x^{2}+x$. Define una 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}}. 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 el derivada formal de g(x).

## La 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 ideal primo P , entonces f es la composición de la polinomia de Dickson

ls, 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 prueba errónea de una versión falsa del resultado. Turnwald y Müller han aportado pruebas correctas.

