Algoritme de tongada de producte

En teoria de grups computacionals, el algoritme de tongada de producte (Product Replacement Algorithm en anglés), dissenyat per Charles-Leedham-Green i Leonard Soicher en 1995, és un algoritme en la finalitat de generar elements aleatoris en un grup finito $G$ , eixecutant una série de passos aleatoris generant $k$ -tuplas de $G$ En térmens generals, un "objecte substitut del producte" és alguna cosa que es crea en una llista de generadors de grup i produïx una seqüència d'elements de grups pseudoaleatorios utilisant alguna font aleatòria per a números aleatoris.

Introducció

L'història de l'algoritme de tongada de producte inicia en l'investigació en Teoria de Grups Computacionals que se centra principalment en treballar en grups de permutació, a on els algoritmes fonamentals de Sims, varen obrir el camí cap als alvanços actuals.

El problema de generar elements de grup aleatoris té dos solucions: una pràctica i una atra teòrica. En un aspecte teòric desenrollat per László Babai, es va trobar un algoritme general de caixa negra que produïx elements de grup (casi) uniformes a un cost de multiplicacions de grup $O (l o g 5 | G |)$ . En ser provablement polinomial, encara que pràcticament llent, este algoritme es va convertir en un resultat fonamental sobre el qual es podria construir el treball teòric posterior. No obstant, no va resoldre la necessitat pràctica d'un generador de grups aleatoris eficient.

Per una atra part, en la solució pràctica, Leedham-Green i Soicher varen descobrir el disseny de el "algoritme de tongada del producte" que més vesprada es va provar i va demostrar tindre un rendiment notablement bo en varis casos pràcticament interessants. A mida que es va reconéixer àmpliament l'èxit de l'algoritme, es va incloure com una rutina estàndar en dos dels principals paquets d'àlgebra grupal. Desafortunadament, la raó per la qual l'algoritme té un rendiment tan bo seguix sent un misteri. Fins fa poc, tots els intents de provar resultats teòrics sobre el rendiment de l'algoritme varen fallar o varen produir resultats incrementals. Un treball important de Diaconis i Saloff-Cost i varis resultats (conjunts) de l'autor varen donar una nova vida a les esperances de comprendre completament l'algoritme.^[1]

Descripció

L'algoritme de tongada del producte es definix de la següent manera.^[2] Siga $G$ un grup finito en una seqüència generada per $k$ elements ${g_{1}, g_{2}, ...., g_{k}}$ i es diu $k$ -tupla generadora de $G$ si $g_{1}$ genera a $G$ . Siga $N_{k} (G)$ el conjunt de totes les $k$ -tuplas generadores de $G$ , tal que $N_{k} (G) = | N_{k} (G) |$ . Per últim siga $k$ la provabilitat de que $k$ es distribuïxca uniformemente dels elements de grups aleatoris independents generen.
$G : ϕ_{k} (G) = \frac{N_{k} (G)}{| G |^{k}}$

Donada una $k$ -tupla generadora es definix un moviment a una atra $k$ -tupla tal que, primer se selecciona uniformemente un parell $(i, j)$ en $1 \leq i \neq j \leq k$ i després s'aplica una de les següents operacions en igual provabilitat.

$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})$

Per a produir un element aleatori en $G$ , es deu escomençar en la generació d'una k-tupla a una atra k-tupla generadora, es repetixen els moviments anteriors vàries voltes i finalment torna un element aleatori de la $k$ -tupla generadora resultant.

Una atra forma de descriure l'algoritme, és definir $Γ k (G)$ com grafo, els vèrtiços del qual són les tuplas en $N_{k}$ , en que les arestes corresponen als moviments $R_{i, j}^{\pm}$ , $L_{i, j}^{\pm}$ . Si $k$ és lo suficientment gran, llavors el grafo $Γ k (G)$ està conectat.

L'algoritme consistix en recórrer aleatoriamente el veí més propenc i tornar un component aleatori. Nos referim a açò com a “Passejada Aleatòria”.

Referències

↑ Pak Igor. "What do we know about the product replacement algorithm?" . Department of Mathematics Yale University. (2000). [1]
↑ L. Babai, Pak Igor. "Strong bias of group generators: an obstacle to the “product replacement algorithm”. Department of Computer Science, University of Chicago.(1999). [2]

Bibliografia

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-Cost, "Walks on generating sets of groups", Invent. Math. 134 (1998), 251–199.

Referències

Este artícul conté una traducció derivada de «Algoritmo de reemplazo de producto» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.

[1] Pak Igor. "What do we know about the product replacement algorithm?" . Department of Mathematics Yale University. (2000). [1]

[2] L. Babai, Pak Igor. "Strong bias of group generators: an obstacle to the “product replacement algorithm”. Department of Computer Science, University of Chicago.(1999). [2]

[1]

[2]