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 Plantilla:Math el cuerpo finito de característica Plantilla:Mvar, es decir, el cuerpo que tiene Plantilla:Mvar elementos donde Plantilla:Math es algún primo Plantilla:Mvar. Un polinomio Plantilla:Mvar con coeficientes en Plantilla:Math (escrito simbólicamente como Plantilla:Math) es un polinomio de permutación de Plantilla:Math si la función de Plantilla:Math sobre sí mismo definida por $c\mapsto f(c)$ es una permutación de Plantilla:Math.

Debido a la finitud de Plantilla:Math, 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).
• Plantilla:Math tiene una solución en Plantilla:Math para cada Plantilla:Mvar en Plantilla:Math.
• Plantilla:Math tiene una solución única en Plantilla:Math para cada Plantilla:Mvar en Plantilla:Math.

Una caracterización de qué polinomios son polinomios de permutación viene dada por:

(Criterio de Charles Hermite) Plantilla:Math es un polinomio de permutación de Plantilla:Math si y solo si se cumplen las dos condiciones siguientes:

1. Plantilla:Mvar tiene exactamente una raíz en Plantilla:Math.
2. Para cada entero Plantilla:Math con Plantilla:Math y $t\equiv ̸0(\mathrm{mod}p)$, la reducción de Plantilla:Math tiene grado Plantilla:Math.

Si Plantilla:Math es un polinomio de permutación definido sobre el cuerpo finito Plantilla:Math, entonces también lo es Plantilla:Math para todos los Plantilla:Math y Plantilla:Mvar en Plantilla:Math. El polinomio de permutación Plantilla:Math está en forma normalizada si Plantilla:Math y Plantilla:Mvar se eligen de modo que Plantilla:Math sea mónico, Plantilla:Math y (siempre que la característica Plantilla:Mvar no divida el grado Plantilla:Mvar del polinomio) el coeficiente de Plantilla:Math 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 Plantilla:Math	Plantilla:Mvar
$x$	cualquier $q$
$x^2$	$q\equiv 0(\mathrm{mod}2)$
$x^3$	$q\equiv ̸1(\mathrm{mod}3)$
$x^3-ax$ ($a$ no es un cuadrado)	$q\equiv 0(\mathrm{mod}3)$
$x^4\pm 3x$	$q=7$
$x^4+a_1{x}^2+a_{2}x$ (si su única raíz en Plantilla:Math es 0)	$q\equiv 0(\mathrm{mod}2)$
$x^5$	$q\equiv ̸1(\mathrm{mod}5)$
$x^5-ax$ ($a$ no es una cuarta potencia)	$q\equiv 0(\mathrm{mod}5)$
$x^5+ax(a^2=2)$	$q=9$
$x^5\pm 2x^2$	$q=7$
$x^5+a{x}^3\pm x^2+3a^{2}x$ ($a$ no es un cuadrado)	$q=7$
$x^5+a{x}^3+5^{-1}{a}^{2}x$ ($a$ arbitrario)	$q\equiv \pm 2(\mathrm{mod}5)$
$x^5+a{x}^3+3a^{2}x$ ($a$ no es un cuadrado)	$q=13$
$x^5-2a{x}^3+a^{2}x$ ($a$ no un es cuadrado)	$q\equiv 0(\mathrm{mod}5)$

En Plantilla:Harvtxt 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.

• Plantilla:Math permuta Plantilla:Math si y solo si Plantilla:Mvar y Plantilla:Math son coprimos (notacionalmente, Plantilla:Math).
• Si Plantilla:Mvar está en Plantilla:Math y Plantilla:Math entonces los polinomios de Dickson (del primer tipo) Plantilla:Math están definidos por

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

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

$D_n(x,a)=x{D}_{n-1}(x,a)-a{D}_{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-4a{x}^2+2a^2$
• $D_5(x,a)=x^5-5a{x}^3+5a^{2}x.$

Si Plantilla:Math y Plantilla:Math entonces Plantilla:Math permuta GF(q) si y solo si Plantilla:Math. Si Plantilla:Math entonces Plantilla:Math y el resultado anterior se mantiene.

• Si Plantilla:Math es una extensión de Plantilla:Math de grado Plantilla:Mvar, entonces el polinomio linealizado

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

con Plantilla:Math en Plantilla:Math, es un operador lineal en Plantilla:Math sobre Plantilla:Math. Un polinomio linealizado Plantilla:Math permuta Plantilla:Math si y solo si 0 es la única raíz de Plantilla:Math en Plantilla:Math. Esta condición se puede expresar algebraicamente como

$\det \left({\alpha }_{i-j}^{q^j}\right)\ne 0(i,j=0,1,\dots ,r-1).$

Los polinomios linealizados que son polinomios de permutación sobre Plantilla:Math 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 Plantilla:Math.

• Si Plantilla:Math está en el anillo polinómico Plantilla:Math y Plantilla:Math no tiene raíz distinta de cero en Plantilla:Math cuando Plantilla:Mvar divide a Plantilla:Math, y Plantilla:Math es primo relativo (coprimo) con respecto a Plantilla:Math, entonces Plantilla:Math permuta Plantilla:Math.

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

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

donde Plantilla:Mvar divide a Plantilla:Math; y

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

donde Plantilla:Mvar divide a Plantilla:Math.

Polinomios excepcionales

Un polinomio excepcional sobre Plantilla:Math es un polinomio en Plantilla:Math que es un polinomio de permutación en Plantilla:Math para infinitos Plantilla:Mvar.

Un polinomio de permutación sobre Plantilla:Math de grado como máximo Plantilla:Math es excepcional sobre Plantilla:Math.

Cada permutación de Plantilla:Math es inducida por un polinomio excepcional.

Si un polinomio con coeficientes enteros (es decir, en Plantilla:Math) es un polinomio de permutación sobre Plantilla:Math para infinitos primos Plantilla:Mvar, 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, Plantilla:Math con Plantilla:Math 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 Plantilla:Math.

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 {𝔽}_q[x_1,\dots ,x_n]$ es un polinomio de permutación en Plantilla:Mvar variables sobre ${𝔽}_q$ si la ecuación $f(x_1,\dots ,x_n)=\alpha$ tiene exactamente $q^{n-1}$ soluciones en ${𝔽}_q^n$ para cada $\alpha \in {𝔽}_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: Plantilla:Nowrap Plantilla:Nowrap Plantilla:Nowrap Plantilla:Nowrap luego el polinomio define la permutación

$\left(\begin{array}{cccc}0& 1& 2& 3\\ 0& 3& 2& 1\end{array}\right).$

Considerar el mismo polinomio $g(x)=2x^2+x$ para el otro anillo Z/8Z. Entonces, se ve que: Plantilla:Nowrap Plantilla:Nowrap Plantilla:Nowrap Plantilla:Nowrap Plantilla:Nowrap Plantilla:Nowrap Plantilla:Nowrap Plantilla:Nowrap luego el polinomio define la permutación

$\left(\begin{array}{cccccccc}0& 1& 2& 3& 4& 5& 6& 7\\ 0& 3& 2& 5& 4& 7& 6& 1\end{array}\right).$

Anillos Z/p^kZ

Considérese $g(x)=a{x}^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(\mathrm{mod}p)$ y $b\equiv ̸0(\mathrm{mod}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+\sum _{0<i\le M}{a}_i{x}^i$ define una permutación sobre el anillo Z/nZ si y solo si todos los polinomios $g_{p_t}(x)=a_{0,p_t}+\sum _{0<i\le 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 $a{x}^2+bx$, tal que $a=0{modp}_1$, pero $a\ne 0{modp}_1^{k_1}$. Supóngase ahora que $a=0{modp}_i^{k_i}$, i > 1. Y supóngase también que $b\ne 0{modp}_i$ para todos los Plantilla:Math (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 Plantilla:Math y el polinomio $6x^2+x$, que define la permutación

$\left(\begin{array}{cccccccccc}0& 1& 2& 3& 4& 5& 6& 7& 8& \cdots \\ 0& 7& 2& 9& 4& 11& 6& 1& 8& \cdots \end{array}\right).$

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^{\prime }(x)\ne 0modp$ 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.