Algoritmo de reemplazo de producto

En teoría de grupos computacionales, el algoritmo de reemplazo de producto (Product Replacement Algorithm en inglés), diseñado por Charles-Leedham-Green y Leonard Soicher en 1995, es un algoritmo con el fin de generar elementos aleatorios en un grupo finito $G$, ejecutando una serie de pasos aleatorios generando $k$-tuplas de $G$ En términos generales, un "objeto sustituto del producto" es algo que se crea con una lista de generadores de grupo y produce una secuencia de elementos de grupos pseudoaleatorios utilizando alguna fuente aleatoria para números aleatorios.

Introducción

La historia del algoritmo de reemplazo de producto inicia con la investigación en Teoría de Grupos Computacionales que se centra principalmente en trabajar con grupos de permutación, donde los algoritmos fundamentales de Sims ,abrieron el camino hacia los avances actuales.

El problema de generar elementos de grupo aleatorios tiene dos soluciones: una práctica y otra teórica. En un aspecto teórico desarrollado por László Babai, se encontró un algoritmo general de caja negra que produce elementos de grupo (casi) uniformes a un costo de multiplicaciones de grupo $O(log5|G|)$. Al ser probablemente polinomial, aunque prácticamente lento, este algoritmo se convirtió en un resultado fundamental sobre el cual se podría construir el trabajo teórico posterior. Sin embargo, no resolvió la necesidad práctica de un generador de grupos aleatorios eficiente.

Por otra parte, en la solución práctica, Leedham-Green y Soicher descubrieron el diseño del "algoritmo de reemplazo del producto" que más tarde se probó y demostró tener un rendimiento notablemente bueno en varios casos prácticamente interesantes. A medida que se reconoció ampliamente el éxito del algoritmo, se incluyó como una rutina estándar en dos de los principales paquetes de álgebra grupal. Desafortunadamente, la razón por la cual el algoritmo tiene un rendimiento tan bueno sigue siendo un misterio. Hasta hace poco, todos los intentos de probar resultados teóricos sobre el rendimiento del algoritmo fallaron o produjeron resultados incrementales. Un trabajo importante de Diaconis y Saloff-Coste y varios resultados (conjuntos) del autor dieron una nueva vida a las esperanzas de comprender completamente el algoritmo.​

Descripción

El algoritmo de reemplazo del producto se define de la siguiente manera.​ Sea $G$ un grupo finito con una secuencia generada por $k$ elementos $\{g_{1},g_{2},....,g_{k}\}$ y se llama $k$-tupla generadora de $G$ si $g_{1}$ genera a $G$. Sea $N_{k}(G)$ el conjunto de todas las $k$-tuplas generadoras de $G$ , tal que $N_{k}(G)=|N_{k}(G)|$. Por último sea $k$ la probabilidad de que $k$ se distribuya uniformemente de los elementos de grupos aleatorios independientes generan.

$$G:\phi _{k}(G)={\frac {N_{k}(G)}{|G|^{k}}}$$

Dada una $k$-tupla generadora se define un movimiento a otra $k$-tupla tal que, primero se selecciona uniformemente un par $(i,j)$ con $1\leq i\neq j\leq k$ y luego se aplica una de las siguientes operaciones con igual probabilidad.

$$R_{i,j}^{\pm }:(g_{1},...,g_{i},....,g_{k})\to (g_{1},....,g_{i}\cdot g_{j}^{\pm 1},....,g_{k})$$

$$L_{i,j}^{\pm }:(g_{1},...,g_{i},....,g_{k})\to (g_{1},....,g_{j}^{\pm 1}\cdot g_{i},....,g_{k})$$

Para producir un elemento aleatorio en $G$, se debe empezar con la generación de una k-tupla a otra k-tupla generadora, se repiten los movimientos anteriores varias veces y finalmente devuelve un elemento aleatorio de la $k$-tupla generadora resultante.

Otra forma de describir el algoritmo, es definir $\Gamma k(G)$ como grafo, cuyos vértices son las tuplas en $N_{k}$, en que las aristas corresponden a los movimientos $R_{i,j}^{\pm }$, $L_{i,j}^{\pm }$. Si $k$ es lo suficientemente grande, entonces el grafo $\Gamma k(G)$ está conectado. El algoritmo consiste en recorrer aleatoriamente el vecino más cercano y devolver un componente aleatorio. Nos referimos a esto como “Paseo Aleatorio”.

Algoritmo Leedham-Green y Soicher

Sea $G$ un grupo descrito por el conjunto generador $X=\{X_{1}.......X_{k}\}$. Se elige un entero $N>k$ y se inicia una matriz $S$ de longitud $N$ que consiste en los generadores de $G$, donde se permiten repeticiones. La operación básica del algoritmo toma un par de números enteros aleatorios i≠j y reemplaza $S[i]$ por $S[i]S[j]$ o $S[j]S[i]$. Se realiza este procedimiento ejecutando esta operación básica un número K de veces. Ahora se realiza la operación básica devolviendo el valor resultante de $S[i]$ como elemento aleatorio. Tenga en cuenta que $S$ contiene en todo momento un conjunto de generación para $G$. Este método tienen la ventaja de que después del procesamiento, solo se requiere una multiplicación para cada elemento aleatorio. Además, dado que se reemplaza $S[i]$ se espera que el proceso de agregar nuevos elementos aleatorios, aumente la aleatoriedad de $S$.

La elección clave en este algoritmo, es el número de operaciones básicas $K$, que deben llevarse a cabo como parte del preprocesamiento para obtener una distribución razonable, y la longitud $N$ de $S$

Una desventaja de esta técnica, es que los elementos devueltos no son independientes el uno del otro. Por ejemplo, si una secuencia de elementos se genera, entonces se producirá un triple consecutivo de la forma $a,b,ab$, puede ocurrir en la secuencia con probabilidad mayor a $1/N^{2}$

Se dice que un conjunto generador $X$ de $G$ es mínimo si no hay un subconjunto adecuado de $X$ que genere $G$. Se denota con $d(G)$ el número mínimo de generadores de $G$, es decir, el tamaño más pequeño de un conjunto generador mínimo de $G$, y escribimos $m(G)$ para el tamaño más grande de un grupo generador mínimo de $G$.

Diaconis y Saloff-Coste (1998) demostraron que la caminata aleatoria en $k(G)$ alcanza una distribución uniforme en el tiempo $|G|^{O(M(G))}k^{2}logk$. Así un límite preciso para $m(G)$ sería deseable como medio de delimitar el tiempo para el algoritmo.

Algoritmo de Babai

• Usa la rutina “subproductos aleatorios”para reducir el número de generadores en un conjunto generado por $S$ desde $k$ a $O(|logG|)$.

• Para $C_{1}\cdot log|G|$ el recorrido repite el siguiente procedimiento. Recorre un simple camino al azar en el grafo de Cayley $(G,S)$ comenzando en $id\ni G$,para $C_{2}log^{4}|G|$ pasos.
• Luego agregue el punto final de la caminata a $S$ y repita.
• Utilice la “máquina Erdös-Rényi”​ para generar la salida. [1]

El sesgo de salida

Generación de k-tuplas en productos de grupos simples

Teorema 1

Sea $G$ un grupo simple no abeliano, entonces el número maximal $N$ , tal que el grupo $H=G^{N}$ (producto directo de N copias de un $G$) es generado por $k$ elementos, es igual a:

$${\frac {|N_{K}(G)|}{|Aut(G)|}}$$

Además, un elemento $g=(g_{1},...,g_{k})\in H_{k}$, donde $g_{i}=g_{i}^{(1)},...,g_{i}^{(m)}$ es un $k$-tupla generadora de $H=G^{N}$ si y sólo si todas las $k$-tuplas $(G_{1}^{(j)},...,G_{K}^{(j))}$, $1\leq j\leq m$ generan el grupo $G$ y si se encuentran en diferentes órbitas de la acción diagonal de $Aut(G)$ en $N_{K}(G)$. En un caso especial de $G=A_{5}$ y $K=2$ se muestra que $N=19$ es decir que $d(A_{5}^{19})=2$ mientras que para $d(A_{5}^{20})=3$.

Para cualquier $K>1$ las probabilidades $\phi _{K}(A_{n})\to 1$.Desde que $Aut(A_{n})=S_{n}$ para $n\geq 5$, $n\neq 6$ se obtiene que la $N$ del teorema satisface:

$$N=\phi _{k}(A_{n}){\frac {|A_{n}|^{k}}{|S_{n}|}}>{\frac {n!^{k-1}}{2^{k+2}}}$$

,
donde $n$ es lo suficientemente grande. En particular, si $G=A_{n}$ y $n$ es grande, el grupo $A_{n}^{(}{n!}/8)$ puede ser generado por dos elementos mientras que $A_{n}^{(}{n!}/4)$ no.

Teorema 2

Si $G$ es un producto directo de grupos simples no abelianos (posiblemente con repeticiones) entonces $\phi (G)>{\frac {1}{2}}$ para $k\geq Clogm$, donde $m$ es el número máximo de copias isomorfas de cada grupo y $C$ es una constante universal.

Ahora bien, sea que $Q^{k}$ denote la probabilidad de los primeros componentes de $k$-tuplas elegidas uniformemente de $N_{k}(G)$ . Esta distribución aparece con la intención de generar rápidamente elementos aleatorios distribuidos de manera casi uniforme en $G$. Si bien la cuestión de la tasa de mezcla para este algoritmo está muy abierta, mostramos que incluso la distribución límite $Q_{k}$ puede estar muy lejos de ser uniforme. Sea $U$ la distribución uniforme sobre $G$ sesgo de la distribución $R$ es la distancia de variación entre $R$ y $U$. En otras palabras, el sesgo de $R$ es

$$||R-U||_{tv}=max_{B\subset G}|R(B)-U(B)|={\frac {1}{2}}\sum _{g\in G}|R(g)-{\frac {1}{|G|}}|$$

El sesgo de un subconjunto $B\subset G$ bajo $R$ es la cantidad $|R(B)-U(B)|$

Teorema 3

Sea $G=A_{n}^{m}$, donde $m\neq n!/8$. Entonces $||Q^{k}-U||_{tv}\to 1$ tal que $n\to \infty$

Se asume que $k\geq 4$ y $k=o(n)$.Se nota que para $m=n!/8$, se genera el grupo $G$ por 2 elementos, pero un par de elementos aleatorio uniforme (o incluso para una $k$-tupla de elementos aleatoria para $k=o(n)$ es poco probable que lo genere.

Usos del algoritmo

El algoritmo de reemplazo de producto, es un importante avance reciente en el álgebra simbólica. Este es el generador de elementos de grupos aleatorios más utilizados en teoría de grupos computacionales GAP​ y Magma​

Algunos problemas del algoritmo

• Se puede observar que no está claro si el grafo $\Gamma k(G)$ está conectado y cuando este no lo es, además poco se puede decir sobre el componente conectado $\Gamma k'(G)$ el cual contiene a $(g)$.

• En algunas pruebas, se observa que es aparentemente peor que correr un simple paseo aleatorio en el generando una k-tupla obtenida al final de la caminata aleatoria de reemplazo del producto. De hecho, heurísticamente se "pierde el tiempo" ejecutando una caminata aleatoria simple con los generadores iniciales "malos", en lugar de esperar hasta el final del algoritmo, y usa estos generadores "buenos". La razón es que ese grupo generador inicial puede corresponder al "peor caso" de una caminata aleatoria, mientras que la $k-tupla$ obtenida después de ejecutar el reemplazo del producto se obtiene un "caso promedio" de una caminata aleatoria.

• Sin embargo, el algoritmo de Leedham-Green tiene una serie de problemas estadísticos y teóricos. Por ejemplo, puede haber más de una clase de equivalencia de generadores de Nielsen. Además, los elementos de los conjuntos generadores deben estar distribuidos uniformemente (por ejemplo, los elementos del subgrupo Frattini nunca pueden aparecer en un conjunto generador de tamaño mínimo).

Bibliografía

• Sims, C. C. Group-theoretic algorithms, a survey, in Proc. ICM, Helsinki, 1978, 979– 985. [3]
• Pak, Igor , Lubotzky, Alexander. "The product replacement algorithm and Kazhdan's property (t)"
• Celler, Frank, Leedham-Green, Charles. Murray, Scott. Niemeyer, Alice. O’Brien,E.A. " Generating random elements of a finite group"
• Babai, László. "Local expansion of vertex-transitive graphsand random generation in finite groups"
• P. Diaconis, L. Saloff-Coste, "Walks on generating sets of groups", Invent. Math. 134 (1998), 251–199.

• Datos: Q76761438