Programa de línea recta

En informática , un programa lineal es, informalmente, un programa que no contiene ningún bucle ni ninguna condición, y que está formado por una secuencia de pasos en los que se aplica cada operación a elementos calculados previamente.

Este artículo se centra en el caso en que las operaciones permitidas son las de un grupo , es decir, la multiplicación y la inversión. Más específicamente, un programa de línea recta ( SLP ) para un grupo finito G = ⟨ S ⟩ es una secuencia finita L de elementos de G tal que cada elemento de L pertenece a S , es el inverso de un elemento precedente o el producto de dos elementos precedentes. Se dice que un SLP L calcula un elemento de grupo g ∈ G si g ∈ L , donde g está codificado por una palabra en S y sus inversos.     

Intuitivamente, un SLP que calcula algún g  ∈ G es una forma eficiente de almacenar g como una palabra de grupo sobre S ; observe que si g se construye en i pasos, la longitud de la palabra g puede ser exponencial en i , pero la longitud del SLP correspondiente es lineal en i . Esto tiene importantes aplicaciones en la teoría de grupos computacional , al utilizar SLP para codificar eficientemente elementos de grupo como palabras sobre un conjunto generador dado.  

Los programas de línea recta fueron introducidos por Babai y Szemerédi en 1984 ^{[ 1 ]} como una herramienta para estudiar la complejidad computacional de ciertas propiedades de grupos de matrices. Babai y Szemerédi demuestran que cada elemento de un grupo finito G tiene un SLP de longitud O (log ² | G |) en cada conjunto generador.

Una solución eficiente al problema de pertenencia constructiva es crucial para muchos algoritmos de teoría de grupos. Se puede expresar en términos de SLP de la siguiente manera: dado un grupo finito G  = ⟨ S ⟩ y g ∈ G , encontrar un programa de línea recta que calcule g sobre S. El problema de pertenencia constructiva se estudia a menudo en el contexto de grupos de caja negra . Los elementos se codifican mediante cadenas de bits de longitud fija. Se proporcionan tres oráculos para las funciones de teoría de grupos de multiplicación, inversión y comprobación de igualdad con la identidad. Un algoritmo de caja negra es aquel que utiliza únicamente estos oráculos. Por lo tanto, los programas de línea recta para grupos de caja negra son algoritmos de caja negra.    

En el ATLAS de Grupos Finitos en línea se proporcionan programas explícitos de línea recta para una gran cantidad de grupos simples finitos .

El grupo diedral D ₁₂ es el grupo de simetrías de un hexágono. Se puede generar mediante una rotación de 60 grados ρ y una reflexión λ. La columna de la izquierda de la siguiente tabla es un programa de línea recta para λρ ³ :

En S ₆ , el grupo de permutaciones de seis letras, podemos tomar α=(1 2 3 4 5 6) y β=(1 2) como generadores. La columna de la izquierda es un ejemplo de un programa lineal para calcular (1 2 3)(4 5 6):

Descripciones breves de grupos finitos . Los programas de línea recta se pueden usar para estudiar la compresión de grupos finitos mediante lógica de primer orden . Proporcionan una herramienta para construir oraciones "cortas" que describen G (es decir, mucho más cortas que | G |). En más detalle, los SLP se usan para demostrar que todo grupo simple finito tiene una descripción de primer orden de longitud O (log| G |), y todo grupo finito G tiene una descripción de primer orden de longitud O (log₃ ^| G | ). ^{[ 3 ]}

Programas de línea recta para calcular conjuntos generadores de subgrupos máximos de grupos simples finitos . El ATLAS en línea de Representaciones de Grupos Finitos ^{[ 4 ]} proporciona programas abstractos de línea recta para calcular conjuntos generadores de subgrupos máximos para muchos grupos simples finitos.

Ejemplo : El grupo Sz(32), perteneciente a la familia infinita de grupos ^de Suzuki , tiene rango 2 mediante los generadores ^a y b , donde a tiene orden 2, b tiene orden 4, ab tiene orden 5, ab₂ tiene orden 25 y ^abab₂ab₃ tiene orden 25. A continuación se muestra un programa de línea recta que calcula un conjunto generador para un subgrupo maximal E₃₂ _· E₃₂ _⋊ C₃₁ . Este programa de línea recta se puede encontrar en el ATLAS en línea de Representaciones de Grupos Finitos _.

El teorema de alcanzabilidad establece que, dado un grupo finito G generado por S , cada g ∈ G tiene un costo máximo de (1  + lg | G | ) ² . Esto puede entenderse como una cota sobre la dificultad de generar un elemento del grupo a partir de los generadores.

Aquí la función lg( x ) es una versión con valores enteros de la función logaritmo : para k ≥1 sea lg( k ) = max{ r  : 2 ^r ≤ k }.

La idea de la demostración es construir un conjunto Z = { z ₁ ,..., z _s } que funcione como un nuevo conjunto generador ( s se definirá durante el proceso). Generalmente es mayor que S , pero cualquier elemento de G puede expresarse como una palabra de longitud como máximo 2 | Z | sobre Z. El conjunto Z se construye definiendo inductivamente una secuencia creciente de conjuntos K ( i ).

Sea K ( i ) = { z ₁ ^{α ₁} · z ₂ ^{α ₂} ·...· z _i ^{α _i}  : α _j ∈ {0,1}}, donde z _i es el elemento del grupo añadido a Z en el paso i . Sea c ( i ) la longitud del programa de línea recta más corto que contiene Z ( i ) = { z ₁ ,..., z _i }. Sea K (0) = {1 _G } y c (0)=0. Definimos el conjunto Z recursivamente:

• Si K ( i ) ⁻¹ K ( i ) = G , declara que s toma el valor i y detente.
• De lo contrario, elija algún z _{i +1} ∈ G \ K ( i ) ⁻¹ K ( i ) (que no sea vacío) que minimice el "aumento de costo" c ( i +1) − c ( i ).

Mediante este proceso, Z se define de tal manera que cualquier g ∈ G puede escribirse como un elemento de K ( i ) ⁻¹ K ( i ), lo que efectivamente facilita su generación a partir de Z.

Ahora necesitamos verificar la siguiente afirmación para asegurarnos de que el proceso termina en lg(| G |) pasos:

La siguiente afirmación se utiliza para demostrar que el coste de cada elemento del grupo se encuentra dentro del límite requerido.

Se necesitan como máximo 2 i pasos para generar g ₁ ∈ K ( i ) ⁻¹ K ( i ). No tiene sentido generar el elemento de longitud máxima, ya que es la identidad. Por lo tanto, 2 i −1 pasos son suficientes. Para generar g ₁ · g ₂ ∈ G \ K ( i ) ⁻¹ K ( i ), 2 i pasos son suficientes.

Ahora terminamos el teorema. Dado que K ( s ) ⁻¹ K ( s ) = G , cualquier g ∈ G puede escribirse en la forma k ⁻¹ ₁ · k ₂ con k ⁻¹ ₁ , k ₂ ∈ K ( s ). Por el Corolario 2, necesitamos como máximo s ² − s pasos para generar Z ( s ) = Z , y no más de 2 s − 1 pasos para generar g a partir de Z ( s ).

Por lo tanto, c ( g | S ) ≤ s ² + s − 1 ≤ lg ² | G | + lg | G | − 1 ≤ (1 + lg | G | ) ² .