En matemáticas , más específicamente en álgebra computacional , 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 o bien pertenece a S , es la inversa 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 inversas.
Intuitivamente, un SLP que calcula algo de 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 palabra de g puede ser exponencial en i , pero la longitud del SLP correspondiente es lineal en i . Esto tiene aplicaciones importantes en la teoría computacional de grupos , mediante el uso de SLP para codificar de manera eficiente los elementos del grupo como palabras sobre un grupo electrógeno 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 2 | G |) en cada grupo electrógeno.
Una solución eficiente al problema de la pertenencia constructiva es crucial para muchos algoritmos de teoría de grupos. Puede expresarse 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 de cálculo g más de S . El problema de la pertenencia constructiva a menudo se estudia en el contexto de los grupos de caja negra . Los elementos están codificados por cadenas de bits de longitud fija. Se proporcionan tres oráculos para las funciones teóricas de grupos de multiplicación, inversión y verificación de igualdad con la identidad. Un algoritmo de caja negra es aquel que usa solo estos oráculos. Por tanto, los programas de línea recta para grupos de caja negra son algoritmos de caja negra.
Se proporcionan programas explícitos de línea recta para una gran cantidad de grupos finitos simples en el ATLAS de grupos finitos en línea .
Definición
Definición informal
Let G ser un grupo finito y dejar que S un subconjunto de G . Una secuencia L = ( g 1 ,…, g m ) de elementos de G es un programa de línea recta sobre S si cada g i puede obtenerse mediante una de las siguientes tres reglas:
- g i ∈ S
- g yo = g j g k para algunos j , k < i
- g i = g−1
jpara algunos j < i .
El costo en línea recta c ( g | S ) de un elemento g ∈ G es la longitud de un programa en línea recta más corto sobre S calculando g . El costo es infinito si g no está en el subgrupo generado por S .
Un programa de línea recta es similar a una derivación en la lógica de predicados. Los elementos de S corresponden a axiomas y las operaciones de grupo corresponden a las reglas de inferencia.
Definicion formal
Let G ser un grupo finito y dejar que S un subconjunto de G . Un programa de línea recta de longitud m sobre S que calcula algo g ∈ G es una secuencia de expresiones ( w 1 ,…, w m ) tal que para cada i , w i es un símbolo para algún elemento de S , o w i = ( w j , -1) para algunos j < i , o w i = ( w j , w k ) para algunos j , k < i , de modo que w m toma el valor g cuando se evalúa en G de la manera obvia.
La definición original que aparece en [2] requiere que G = ⟨ S ⟩. La definición presentada anteriormente es una generalización común de esto.
Desde una perspectiva computacional, la definición formal de un programa de línea recta tiene algunas ventajas. En primer lugar, una secuencia de expresiones abstractas requiere menos memoria que los términos en el conjunto generador. En segundo lugar, permite construir programas en línea recta en una representación de G y evaluarlos en otra. Ésta es una característica importante de algunos algoritmos. [2]
Ejemplos de
El grupo diedro D 12 es el grupo de simetrías de un hexágono. Puede generarse mediante una rotación de 60 grados ρ y una reflexión λ. La columna más a la izquierda de lo siguiente es un programa de línea recta para λρ 3 :
|
|
En S 6 , el grupo de permutaciones de seis letras, podemos tomar α = (1 2 3 4 5 6) y β = (1 2) como generadores. La columna más a la izquierda aquí es un ejemplo de un programa de línea recta para calcular (1 2 3) (4 5 6):
|
|
|
Aplicaciones
Breves descripciones de grupos finitos . Los programas de línea recta se pueden utilizar para estudiar la compresión de grupos finitos a través de la lógica de primer orden . Proporcionan una herramienta para construir oraciones "cortas" que describen G (es decir, mucho más cortas que | G |). Con más detalle, los SLP se utilizan para demostrar que cada grupo simple finito tiene una descripción de primer orden de longitud O (log | G |), y que cada grupo finito G tiene una descripción de primer orden de longitud O (log 3 | G | ). [3]
Programas de línea recta que calculan grupos electrógenos para subgrupos máximos de grupos simples finitos . El ATLAS en línea de representaciones de grupos finitos [4] proporciona programas abstractos en línea recta para calcular conjuntos generadores de subgrupos máximos para muchos grupos simples finitos.
Ejemplo : El grupo de Sz (32), perteneciente a la familia infinito de grupos de Suzuki , tiene rango 2 a través de generadores de un y b , donde una tiene orden 2, b tiene orden 4, ab tiene orden 5, ab 2 tiene orden 25 y ABAB 2 ab 3 tiene orden 25. El siguiente es un programa de línea recta que calcula un grupo electrógeno para un subgrupo máximo E 32E 32C 31 . Este programa de línea recta se puede encontrar en el ATLAS en línea de Representaciones de grupos finitos.
|
|
Teorema de accesibilidad
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 |) 2 . Esto puede entenderse como un límite en la dificultad de generar un elemento de 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 1 ,…, z s } que funcionará como un nuevo conjunto generador ( s se definirán durante el proceso). Suele ser más grande 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 1 α 1 · z 2 α 2 ·… · z i α i : α j ∈ {0,1}}, donde z i es el elemento de grupo agregado a Z en el i -ésimo paso . Sea c ( i ) la longitud de un programa de línea recta más corto que contiene Z ( i ) = { z 1 ,…, z i }. Sea K (0) = {1 G } yc (0) = 0. Definimos el conjunto Z de forma recursiva:
- Si K ( i ) −1 K ( i ) = G , declare que s tome el valor i y se detenga.
- De lo contrario, elija un z i +1 ∈ G \ K ( i ) −1 K ( i ) (que no está vacío) que minimiza el "aumento de costo" c ( i +1) - c ( i ).
Mediante este proceso, Z se define de manera que cualquier g ∈ G pueda escribirse como un elemento de K ( i ) −1 K ( i ), lo que facilita la generación de Z de manera efectiva .
Ahora necesitamos verificar la siguiente afirmación para asegurarnos de que el proceso termina dentro de lg (| G |) muchos pasos:
Afirmación 1 - Si i < s entonces | K ( i +1) | = 2 | K ( i ) | .
Es inmediato que | K ( i +1) | ≤ 2 | K ( i ) | . Ahora suponga una contradicción que | K ( i +1) | <2 | K ( i ) | . Según el principio del casillero, hay k 1 , k 2 ∈ K ( i +1) con k 1 = z 1 α 1 · z 2 α 2 ·… · z i +1 α i +1 = z 1 β 1 · z 2 β 2 ·… · z i +1 β i +1 = k 2 para algunos α j , β j ∈ {0,1}. Sea r el número entero más grande tal que α r ≠ β r . Suponga que WLOG α r = 1. De ello se deduce que z r = z p - α p · z p -1 - α p -1 ·… · z 1 - α 1 · z 1 β 1 · z 2 β 2 ·… · z q β q , con p , q < r . Por tanto, z r ∈ K ( r −1) −1 K ( r - 1), una contradicción.
La siguiente afirmación se usa para mostrar que el costo de cada elemento del grupo está dentro del límite requerido.
Reclamación 2 - c ( i ) ≤ i 2 - i .
Dado que c (0) = 0, basta con mostrar que c ( i +1) - c ( i ) ≤ 2 i . La gráfica de Cayley de G está conectada y si i < s , K ( i ) −1 K ( i ) ≠ G , entonces hay un elemento de la forma g 1 · g 2 ∈ G \ K ( i ) −1 K ( i ) con g 1 ∈ K ( i ) -1 K ( i ) y g 2 ∈ S .
Se necesitan como máximo 2 i pasos para generar g 1 ∈ K ( i ) −1 K ( i ). No tiene sentido generar el elemento de máxima longitud, ya que es la identidad. Por tanto, 2 i −1 pasos son suficientes. Para generar g 1 · g 2 ∈ G \ K ( i ) −1 K ( i ), 2 i pasos son suficientes.
Ahora terminamos el teorema. Dado que K ( s ) −1 K ( s ) = G , cualquier g ∈ G se puede escribir en la forma k−1
1· K 2 con k−1
1, k 2 ∈ K ( s ). Según el Corolario 2, necesitamos como máximo s 2 - 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 tanto, c ( g | S ) ≤ s 2 + s - 1 ≤ lg 2 | G | + lg | G | - 1 ≤ (1 + lg | G |) 2 .
Referencias
- ^ Babai, László y Endre Szemerédi. "Sobre la complejidad de los problemas del grupo de matrices I." Fundamentos de la informática, 1984. 25º Simposio anual sobre los fundamentos de la informática. IEEE, 1984
- ^ a b Ákos Vidente. (2003). Algoritmos de grupo de permutación. [En línea]. Cambridge Tracts in Mathematics. (No. 152). Cambridge: Cambridge University Press.
- ^ Nies, A. y Tent, K. (2016). Describir grupos finitos mediante frases cortas de primer orden. Israel J. Matemáticas, por aparecer. https://arxiv.org/abs/1409.8390
- ^ http://brauer.maths.qmul.ac.uk/Atlas/v3/