En las matemáticas , en las áreas de la teoría de grupos y la combinatoria , palabras Pasillo proporcionan una única factorización monoid del monoide libre . También están totalmente ordenados y, por lo tanto, proporcionan un orden total en el monoide. Esto es análogo al caso más conocido de las palabras de Lyndon ; de hecho, las palabras de Lyndon son un caso especial, y casi todas las propiedades que poseen las palabras de Lyndon se trasladan a las palabras de Hall. Las palabras de pasillo están en correspondencia uno a uno con los árboles de pasillo . Estos son árboles binarios ; en conjunto, forman el conjunto Hall . Este conjunto es un particularsubconjunto totalmente ordenado de un álgebra no asociativa libre, es decir, un magma libre . De esta forma, los árboles de Hall proporcionan una base para álgebras de Lie libres y pueden usarse para realizar las conmutaciones requeridas por el teorema de Poincaré-Birkhoff-Witt usado en la construcción de un álgebra envolvente universal . Como tal, esto generaliza el mismo proceso cuando se hace con las palabras de Lyndon. Los árboles de pasillo también se pueden usar para dar un orden total a los elementos de un grupo, a través del proceso de recolección del conmutador , que es un caso especial de la construcción general que se muestra a continuación. Se puede demostrar que los conjuntos de Lazard coinciden con los conjuntos de Hall.
El desarrollo histórico se desarrolla en orden inverso al de la descripción anterior. El proceso de recolección del conmutador fue descrito por primera vez, en 1934, por Philip Hall y explorado en 1937 por Wilhelm Magnus . [1] [2] Los decorados de Hall fueron introducidos por Marshall Hall basándose en el trabajo de Philip Hall en grupos. [3] Posteriormente, Wilhelm Magnus mostró que surgen como el álgebra de Lie graduada asociada con la filtración en un grupo libre dada por la serie central inferior . Esta correspondencia fue motivada por identidades de conmutador en la teoría de grupos debidas a Philip Hall y Ernst Witt .
Conjunto de sala
El conjunto de Hall es un subconjunto totalmente ordenado de un álgebra no asociativa libre, es decir, un magma libre . Dejar ser un conjunto de generadores, y dejar ser el magma libre terminado . El magma libre es simplemente el conjunto de cadenas no asociativas en las letras de, con paréntesis retenido para mostrar la agrupación. De manera equivalente, el magma libre es el conjunto de todos los árboles binarios cuyas hojas son elementos de.
El conjunto Hall se puede construir de forma recursiva de la siguiente manera:
- Los elementos de se les da un orden total arbitrario.
- El conjunto Hall contiene los generadores:
- Un conmutador si y solo si y y y:
- Ya sea (y por lo tanto ),
- O con y y .
- Los conmutadores pueden ordenarse arbitrariamente, siempre que siempre aguanta.
La construcción y la notación que se usan a continuación son casi idénticas a las que se usan en el proceso de recolección del conmutador , por lo que se pueden comparar directamente; los pesos son las longitudes de las cuerdas. La diferencia es que no se requiere ninguna mención de grupos. Todas estas definiciones coinciden con la de X. Viennot. [4] Nótese que algunos autores invierten el orden de la desigualdad. Tenga en cuenta también que una de las condiciones, el, puede sentirse "al revés"; este "atraso" es lo que proporciona el orden descendente requerido para la factorización. Revertir la desigualdad no revierte este "atraso".
Ejemplo
Considere el grupo electrógeno con dos elementos Definir y escribe por para simplificar la notación, use paréntesis solo cuando sea necesario. Los miembros iniciales del conjunto Hall son entonces (en orden)
Note que hay elementos de cada longitud distinta. Esta es la secuencia inicial del polinomio del collar en dos elementos (que se describe a continuación, a continuación).
Combinatoria
Un resultado básico es que el número de elementos de longitud en el conjunto Hall (sobre generadores) viene dado por el polinomio del collar
dónde es la función clásica de Möbius . La suma es una convolución de Dirichlet .
Definiciones y lemas
Algunas definiciones básicas son útiles. Dado un árbol, el elemento se llama el subárbol izquierdo inmediato , y del mismo modo,es el subárbol derecho inmediato . Un subárbol derecho es sí mismo, o un subárbol derecho de cualquiera o . Esto contrasta con el subárbol de la extrema derecha , que es sí mismo, o un subárbol de extrema derecha de .
Un lema básico es que si es un subárbol derecho de un árbol Hall , luego
Palabras de pasillo
Las palabras de pasillo se obtienen del conjunto de pasillo "olvidando" los corchetes del conmutador, pero manteniendo la noción de orden total. Resulta que este "olvido" es inofensivo, ya que el árbol de Hall correspondiente se puede deducir de la palabra, y es único. Es decir, las palabras de Hall están en correspondencia uno a uno con los árboles de Hall. El orden total en los árboles Hall pasa a un orden total en las palabras Hall.
Esta correspondencia permite una factorización de monoide : dado el monoide libre , cualquier elemento de se puede factorizar de forma única en una secuencia ascendente de palabras Hall. Esto es análogo y generaliza el caso más conocido de factorización con palabras de Lyndon proporcionado por el teorema de Chen-Fox-Lyndon .
Más precisamente, cada palabra se puede escribir como una concatenación de palabras Hall
con cada palabra Hall siendo totalmente ordenado por el Hall ordenando:
De esta manera, el ordenamiento de palabras de Hall se extiende a un orden total en el monoide. Los lemas y teoremas necesarios para proporcionar la correspondencia de palabra a árbol y el orden único se describen a continuación.
Follaje
El follaje de un magma es el mapeo canónico del magma al monoide libre , dada por por y de lo contrario. El follaje es solo la cuerda que consiste en las hojas del árbol, es decir, tomar el árbol escrito con corchetes del conmutador y borrar los corchetes del conmutador.
Factorización de palabras Hall
Dejar ser un árbol Hall, y ser la palabra Hall correspondiente. Dada cualquier factorización de una palabra Hall en dos cadenas no vacías y , entonces existe una factorización en árboles Hall tal que y con
y
Este y el desarrollo posterior a continuación son proporcionados por Guy Melançon. [5]
Correspondencia
Lo contrario a la factorización anterior establece la correspondencia entre las palabras Hall y los árboles Hall. Esto se puede expresar de la siguiente forma interesante: si es un árbol Hall, y la palabra Hall correspondiente factoriza como
con
luego . En otras palabras, las palabras de Hall no se pueden factorizar en una secuencia descendente de otras palabras de Hall. [5] Esto implica que, dada una palabra Hall, el árbol correspondiente se puede identificar de forma única.
Factorización estándar
El orden total en los árboles de Hall pasa a las palabras de Hall. Por lo tanto, dada una palabra Hall, se puede factorizar como con . Esto se denomina factorización estándar .
Secuencia estándar
Una secuencia de palabras Hallse dice que es una secuencia estándar si cada es una letra o una factorización estándar con Tenga en cuenta que las secuencias crecientes de palabras Hall son estándar.
Reescritura de términos
La factorización única de cualquier palabra en una concatenación de una secuencia ascendente de palabras Hall con se puede lograr definiendo y aplicando recursivamente un sistema de reescritura de términos simple . La singularidad de la factorización se deriva de las propiedades de confluencia del sistema. [5] La reescritura se realiza mediante el intercambio de ciertos pares de palabras Hall consecutivas en una secuencia; se da después de estas definiciones.
Una gota en una secuencia de palabras Hall es un par tal que Si la secuencia es una secuencia estándar, entonces la caída se denomina caída legal si uno también tiene esa
Dada una secuencia estándar con un abandono legal, hay dos reglas de reescritura distintas que crean nuevas secuencias estándar. Uno concatena las dos palabras en la gota:
mientras que el otro permuta los dos elementos en la gota:
No es difícil demostrar que ambas reescrituras dan como resultado una nueva secuencia estándar. En general, es más conveniente aplicar la reescritura a la caída legal más a la derecha; sin embargo, se puede demostrar que la reescritura es confluente, por lo que se obtienen los mismos resultados sin importar el orden.
Orden total
Se puede proporcionar un pedido total en las palabras. Esto es similar al orden lexicográfico estándar , pero al nivel de las palabras Hall. Dadas dos palabrasfactor en el orden ascendente de palabras de Hall, es decir , que
- y
con cada una palabra Hall, uno tiene un orden que si alguno
- y
o si
- y
Propiedades
Las palabras de pasillo tienen varias propiedades curiosas, muchas de ellas casi idénticas a las de las palabras de Lyndon . La primera y más importante propiedad es que las palabras de Lyndon son un caso especial de las palabras de Hall. Es decir, la definición de una palabra Lyndon satisface la definición de la palabra Hall. Esto se puede verificar fácilmente mediante comparación directa; tenga en cuenta que la dirección de la desigualdad utilizada en las definiciones anteriores es exactamente la inversa de la utilizada en la definición habitual de las palabras de Lyndon. El conjunto de árboles de Lyndon (que se deriva de la factorización estándar) es un conjunto de Hall.
Otras propiedades incluyen:
- Las palabras de pasillo son acíclicas también conocidas como primitivas . Es decir, no se pueden escribir en la forma por alguna palabra y .
- Una palabra es una palabra Hall si y solo si para cualquier factorización de en palabras no vacías obedece . En particular, esto implica que ninguna palabra Hall es un conjugado de otra palabra Hall. Note nuevamente, esto es exactamente como es para una palabra de Lyndon: las palabras de Lyndon son las menores de su clase de conjugación; Las palabras de pasillo son las mejores.
- Una palabra es una palabra Hall si y solo si es más grande que cualquiera de sus factores correctos adecuados. Esto se desprende de los dos puntos anteriores.
- Cada palabra primitiva se conjuga con una palabra Hall. Es decir, existe un cambio circular deesa es una palabra de Hall. De manera equivalente, existe una factorización tal que es una palabra de Hall. Este conjugado es único, ya que ninguna palabra Hall es un conjugado de otra palabra Hall.
- Cada palabra es el conjugado de un poder de una palabra Hall única.
Trascendencia
Existe un sistema de reescritura de términos similar para las palabras de Lyndon , así es como se logra la factorización de un monoide con las palabras de Lyndon.
Debido a que las palabras Hall se pueden colocar en árboles Hall, y cada árbol Hall se puede interpretar como un conmutador, el término reescritura se puede utilizar para realizar el proceso de recopilación del conmutador en un grupo.
Otra aplicación muy importante de la regla de reescritura es realizar las conmutaciones que aparecen en el teorema de Poincaré-Birkhoff-Witt . Se proporciona una discusión detallada de la conmutación en el artículo sobre álgebras envolventes universales . Tenga en cuenta que la reescritura de términos con palabras de Lyndon también se puede utilizar para obtener la conmutación necesaria para el teorema PBW. [6]
Historia
Los decorados de pasillo fueron introducidos por Marshall Hall basándose en el trabajo de Philip Hall en grupos. [3] Posteriormente, Wilhelm Magnus mostró que surgen como el álgebra de Lie graduada asociada con la filtración en un grupo libre dada por la serie central inferior . Esta correspondencia fue motivada por identidades de conmutador en la teoría de grupos debidas a Philip Hall y Ernst Witt .
Ver también
- Identidad Hall – Petresco
- Odómetro de Markov
Referencias
- ↑ Hall, Philip (1934), "Una contribución a la teoría de grupos de orden de potencias primarias", Actas de la London Mathematical Society , 36 : 29-95, doi : 10.1112 / plms / s2-36.1.29
- ^ W. Magnus, (1937) "Über Beziehungen zwischen höheren Kommutatoren", J. Grelle 177 , 105-115.
- ^ a b Hall, Marshall (1950), "Una base para anillos de Lie libres y conmutadores superiores en grupos libres" , Proceedings of the American Mathematical Society , 1 (5): 575–581, doi : 10.1090 / S0002-9939-1950-0038336- 7 , ISSN 0002-9939 , Sr. 0038336
- ↑ X. Viennot, (1978) "Algèbres de Lie libres et monoïdes libres", Lecture Notes in Mathematics , 691 , Springer-Verlag
- ^ a b c Guy Melançon, (1992) " Combinatoria de árboles Hall y palabras Hall ", Journal of Combinatorial Theory , 59A (2) págs. 285-308.
- ^ Guy Melançon y C. Reutenauer (1989), "Palabras de Lyndon, álgebras libres y barajas", Canadian Journal of Mathematics . 41 , núm. 4, págs. 577-591.