palabra salón

Construcción que proporciona un orden total en un monoide gratuito.

En matemáticas , en las áreas de teoría de grupos y combinatoria , las palabras de Hall proporcionan una factorización monoide única del monoide libre . También están totalmente ordenados y, por 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 Hall están en correspondencia uno a uno con los árboles Hall . Estos son árboles binarios ; en conjunto, forman el conjunto Hall . Este conjunto es un subconjunto particular totalmente ordenado de un álgebra libre no asociativa, es decir, un magma libre . De esta forma, los árboles de Hall proporcionan una base para las álgebras de Lie libres y pueden usarse para realizar las conmutaciones requeridas por el teorema de Poincaré-Birkhoff-Witt utilizado 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 Hall también se pueden utilizar para dar un orden total a los elementos de un grupo, mediante el proceso de recolección del conmutador , que es un caso especial de la construcción general que se detalla 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 a 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]} Marshall Hall introdujo los decorados de sala basándose en el trabajo de Philip Hall en grupos. ^[3] Posteriormente, Wilhelm Magnus demostró que surgen como el álgebra de Lie graduada asociada con la filtración en un grupo libre dado por la serie central inferior . Esta correspondencia fue motivada por las identidades de conmutadores en la teoría de grupos debido a Philip Hall y Ernst Witt .

Preliminares notacionales

El escenario de este artículo es el magma libre en los generadores. Se trata simplemente de un conjunto que contiene elementos, junto con un operador binario que permite yuxtaponer dos elementos cualesquiera, uno al lado del otro. La yuxtaposición se considera no asociativa y no conmutativa , por lo que necesariamente se debe utilizar paréntesis cuando se yuxtaponen tres o más elementos. Así, por ejemplo, no es lo mismo que . ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle \bullet }$ ${\displaystyle (a\bullet b)\bullet c}$ ${\displaystyle a\bullet (b\bullet c)}$

De esta manera, el operador de magma proporciona un sustituto conveniente para cualquier otro operador binario deseado que pueda tener propiedades adicionales, como conmutadores de grupo o de álgebra. Así, por ejemplo, la yuxtaposición de magma se puede asignar al conmutador de un álgebra no conmutativa: ${\displaystyle \bullet }$

${\displaystyle a\bullet b\mapsto [a,b]=ab-ba}$

o a un conmutador de grupo:

${\displaystyle a\bullet b\mapsto aba^{-1}b^{-1}}$

Los dos mapas anteriores son simplemente homomorfismos de magma, en el sentido convencional de homomorfismo ; Resulta que los objetos de la derecha tienen más estructura que el magma. Para evitar el incómodo lío tipográfico que supone , lo convencional es escribir simplemente para . Sin embargo, el uso de paréntesis es obligatorio, como ya se señaló. Si es un objeto compuesto, a veces se puede escribir según sea necesario para eliminar la ambigüedad del uso. Por supuesto, también se puede escribir en lugar de , pero esto puede provocar una proliferación de corchetes y comas. Teniendo esto en cuenta, de lo contrario uno puede ser fluido en la notación. ${\displaystyle \bullet }$ ${\displaystyle ab}$ ${\displaystyle (a\bullet b)}$ ${\displaystyle (ab)c\neq a(bc)}$ ${\displaystyle a}$ ${\displaystyle (a)}$ ${\displaystyle [a,b]}$ ${\displaystyle ab}$

conjunto de pasillo

El conjunto de Hall es un subconjunto totalmente ordenado de un álgebra libre no asociativa, es decir, un magma libre . Sea un conjunto de generadores y sea el magma libre . El magma libre es simplemente el conjunto de cadenas no asociativas en las letras de , manteniéndose los paréntesis para mostrar la agrupación. Los paréntesis pueden escribirse entre corchetes, de modo que los elementos del magma libre puedan considerarse conmutadores formales. De manera equivalente, el magma libre es el conjunto de todos los árboles binarios con hojas marcadas por elementos de . ${\displaystyle A={a_{1},\ldots ,a_{n}}}$ ${\displaystyle M(A)}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle A}$

El conjunto Hall se puede construir recursivamente (en orden creciente) de la siguiente manera: ${\displaystyle H\subseteq M(A)}$

• A los elementos de se les da un orden total arbitrario. ${\displaystyle A}$
• El set Hall contiene los generadores: ${\displaystyle A\subseteq H.}$
• Un conmutador formal si y sólo si y y y: ${\displaystyle [x,y]\in H}$ ${\displaystyle x\in H}$ ${\displaystyle y\in H}$ ${\displaystyle x>y}$
  • O (y por lo tanto ), ${\displaystyle x\in A}$ ${\displaystyle y\in A}$
  • O con y y . ${\displaystyle x=[u,v]}$ ${\displaystyle u\in H}$ ${\displaystyle v\in H}$ ${\displaystyle v\leq y}$
• Los conmutadores se pueden ordenar arbitrariamente, siempre que siempre se cumpla. ${\displaystyle y<[x,y]}$

La construcción y notación utilizadas a continuación son casi idénticas a las utilizadas en el proceso de recolección del conmutador y, por lo tanto, se pueden comparar directamente; los pesos son las longitudes de las cuerdas. La diferencia es que no se requiere 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, la , puede parecer "al revés"; este "atraso" es lo que proporciona el orden descendente necesario para la factorización. Revertir la desigualdad no revierte este "atraso". ${\displaystyle v\leq y}$

Ejemplo

Considere el conjunto generador con dos elementos Definir y escribir para para simplificar la notación, usando paréntesis sólo cuando sea necesario. Los miembros iniciales del conjunto Hall son entonces (en orden) ${\displaystyle \{a,b\}.}$ ${\displaystyle a>b}$ ${\displaystyle xy}$ ${\displaystyle [x,y]}$

${\displaystyle {\begin{aligned}&b,a,\\&ab,\\&(ab)b,\;\;(ab)a,\\&((ab)b)b,\;\;((ab)b)a,\;\;((ab)a)a,\\&(((ab)b)b)b,\;(((ab)b)b)a,\;(((ab)b)a)a,\;(((ab)a)a)a,\;((ab)b)(ab),\;((ab)a)(ab),\\&\cdots \end{aligned}}}$

Observe que hay elementos de cada longitud distinta. Esta es la secuencia inicial del polinomio collar en dos elementos (que se describe a continuación). ${\displaystyle 2,1,2,3,6,\ldots }$

combinatoria

Un resultado básico es que el número de elementos de longitud en el conjunto de Hall (sobre generadores) viene dado por el polinomio del collar. ${\displaystyle k}$ ${\displaystyle n}$

${\displaystyle M_{n}(k)\ =\ {1 \over k}\sum _{d\,|\,k}\mu \!\left({k \over d}\right)n^{d}={1 \over k}\sum _{d\,|\,k}\mu \!\left({d}\right)n^{k/d}}$

¿Dónde está la función clásica de Möbius ? La suma es una convolución de Dirichlet . ${\displaystyle \mu }$

Definiciones y lemas

Algunas definiciones básicas son útiles. Dado un árbol , el elemento se llama subárbol inmediato izquierdo y, de la misma manera, es el subárbol inmediato derecho . Un subárbol derecho es él mismo o un subárbol derecho de o . Un subárbol del extremo derecho es él mismo o un subárbol del extremo derecho de . ${\displaystyle t=[x,y]}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle y}$ ${\displaystyle y}$

Un lema básico es que si es un subárbol derecho de un árbol Hall , entonces ${\displaystyle v}$ ${\displaystyle t=[x,y]}$ ${\displaystyle v\leq y.}$

palabras del salón

Las palabras Hall se obtienen del conjunto Hall "olvidando" los corchetes del conmutador, pero manteniendo la noción de orden total. Resulta que este "olvido" es inofensivo, ya que de la palabra se puede deducir el árbol de Hall correspondiente y es único. Es decir, las palabras Hall están en correspondencia uno a uno con los árboles Hall. El orden total de los árboles Hall pasa a un orden total de las palabras Hall.

Esta correspondencia permite una factorización monoide : dado el monoide libre , cualquier elemento de puede factorizarse 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 . ${\displaystyle A^{*}}$ ${\displaystyle A^{*}}$

Más precisamente, cada palabra se puede escribir como una concatenación de palabras de Hall. ${\displaystyle w\in A^{*}}$

${\displaystyle w=h_{1}h_{2}\cdots h_{k}}$

con cada palabra de Hall totalmente ordenada por el orden de Hall: ${\displaystyle h_{j}}$

${\displaystyle h_{1}\leq h_{2}\leq \cdots \leq h_{k}.}$

De esta manera, el orden de las palabras de Hall se extiende a un orden total en el monoide. A continuación se describen los lemas y teoremas necesarios para proporcionar la correspondencia entre palabras y árboles y el orden único.

Follaje

El follaje de un magma es el mapeo canónico del magma al monoide libre , dado por for y else. El follaje es simplemente la cadena que consta de las hojas del árbol, es decir, tomando el árbol escrito con corchetes del conmutador y borrando los corchetes del conmutador. ${\displaystyle M(A)}$ ${\displaystyle f:M(A)\to A^{*}}$ ${\displaystyle A^{*}}$ ${\displaystyle f:a\mapsto a}$ ${\displaystyle a\in A}$ ${\displaystyle f:[x,y]\mapsto f(x)f(y)}$

Factorización de palabras de Hall

Sea un árbol de Hall y la palabra de 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 ${\displaystyle t=[x,y]\in H}$ ${\displaystyle w=f([x,y])}$ ${\displaystyle w=uv}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle u=f(x_{1})\cdots f(x_{m})}$ ${\displaystyle v=f(y_{1})\cdots f(y_{n})}$

${\displaystyle x_{1},\ldots ,x_{m}>y_{1}}$

y

${\displaystyle y_{1}\leq y_{2}\leq \cdots \leq y_{n}\leq y.}$

Este y el desarrollo posterior a continuación están a cargo de 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 se factoriza como ${\displaystyle t}$ ${\displaystyle f(t)}$

${\displaystyle f(t)=f(t_{1})\cdots f(t_{n})}$

con

${\displaystyle f(t_{1})\leq \cdots \leq f(t_{n})}$

entonces . 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 puede identificarse de forma única. ${\displaystyle n=1}$

Factorización estándar

El orden total de los árboles de Hall pasa a las palabras de Hall. Por lo tanto, dada una palabra de Hall , se puede factorizar como con . Esto se denomina factorización estándar . ${\displaystyle w=f([x,y])}$ ${\displaystyle w=f(x)f(y)}$ ${\displaystyle f(x)>f(y)}$

Secuencia estándar

Se dice que una secuencia de palabras Hall es una secuencia estándar si cada una es una letra o una factorización estándar. Tenga en cuenta que las secuencias crecientes de palabras Hall son estándar. ${\displaystyle (w_{1},w_{2},\ldots ,w_{n})}$ ${\displaystyle w_{i}}$ ${\displaystyle w_{i}=u_{i}v_{i}}$ ${\displaystyle v_{i}\leq w_{i+1},\cdots ,w_{n}.}$

Reescritura de términos

La factorización única de cualquier palabra en una concatenación de una secuencia ascendente de palabras Hall se puede lograr definiendo y aplicando recursivamente un sistema de reescritura de términos simple . La unicidad 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. ${\displaystyle w\in A^{*}}$ ${\displaystyle w=h_{1}h_{2}\cdots h_{k}}$ ${\displaystyle h_{1}\leq h_{2}\leq \cdots \leq h_{k}}$

Una caída 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 una también tiene esa ${\displaystyle (h_{1},h_{2},\ldots ,h_{n})}$ ${\displaystyle (h_{i},h_{i+1})}$ ${\displaystyle h_{i}>h_{i+1}.}$ ${\displaystyle h_{i+1}\leq h_{i+2},\ldots ,h_{n}.}$

Dada una secuencia estándar con una caída legal, existen dos reglas de reescritura distintas que crean nuevas secuencias estándar. Se concatenan las dos palabras del drop:

${\displaystyle (h_{1},h_{2},\ldots ,h_{n})\to (h_{1},h_{2},\ldots ,h_{i}h_{i+1},\ldots ,h_{n})}$

mientras que el otro permuta los dos elementos de la gota:

${\displaystyle (h_{1},h_{2},\ldots ,h_{n})\to (h_{1},h_{2},\ldots ,h_{i-1},h_{i+1},h_{i},h_{i+2},\ldots ,h_{n})}$

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 en la posición legal situada 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 orden total de las palabras. Esto es similar al orden lexicográfico estándar , pero a nivel de palabras Hall. Dadas dos palabras factorizadas en el orden ascendente de las palabras de Hall, es decir , que ${\displaystyle w\in A^{*}.}$ ${\displaystyle u,v}$

${\displaystyle u=u_{1}u_{2}\cdots u_{m}\quad }$y ${\displaystyle \quad v=v_{1}v_{2}\cdots v_{n}}$

con cada una de las palabras Hall, uno tiene un orden que si ${\displaystyle u_{i},v_{j}}$ ${\displaystyle u<v}$

${\displaystyle m<n\quad }$y ${\displaystyle \quad u_{1}=v_{1},\,u_{2}=v_{2},\,\cdots ,u_{m}=v_{m}}$

o si

${\displaystyle u_{1}=v_{1},\,u_{2}=v_{2},\,\ldots ,u_{k}=v_{k}\quad }$y ${\displaystyle \quad u_{k+1}<v_{k+1}.}$

Propiedades

Las palabras Hall tienen una serie de propiedades curiosas, muchas de ellas casi idénticas a las de las palabras 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 puede verificarse 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 Lyndon. El conjunto de árboles de Lyndon (que se derivan de la factorización estándar) es un conjunto de Hall.

Otras propiedades incluyen:

• Las palabras Hall son acíclicas , también conocidas como primitivas . Es decir, no se pueden escribir en la forma de alguna palabra y . ${\displaystyle w=x^{n}}$ ${\displaystyle x\in A^{*}}$ ${\displaystyle n>1}$
• Una palabra es una palabra Hall si y solo si obedece a cualquier factorización de en palabras no vacías . En particular, esto implica que ninguna palabra de Hall es conjugada de otra palabra de Hall. Tenga en cuenta nuevamente que esto es exactamente igual que para una palabra Lyndon: las palabras Lyndon son las menos de su clase de conjugación; Las palabras de Hall son las mejores. ${\displaystyle w\in A^{*}}$ ${\displaystyle w=uv}$ ${\displaystyle w>vu}$
• Una palabra es una palabra Hall si y sólo si es mayor que cualquiera de sus factores correctos propios. Esto se desprende de los dos puntos anteriores. ${\displaystyle w\in A^{*}}$
• Cada palabra primitiva está conjugada con una palabra Hall. Es decir, existe un desplazamiento circular de esa es una palabra de Hall. De manera equivalente, existe una factorización que es una palabra de Hall. Este conjugado es único, ya que ninguna palabra de Hall es un conjugado de otra palabra de Hall. ${\displaystyle w\in A^{*}}$ ${\displaystyle w}$ ${\displaystyle w=uv}$ ${\displaystyle vu}$
• Cada palabra es el conjugado de una potencia de una palabra Hall única. ${\displaystyle w\in A^{*}}$

Trascendencia

Existe un sistema de reescritura de términos similar para palabras de Lyndon ; así es como se logra la factorización de un monoide con 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 . En el artículo sobre álgebras envolventes universales se proporciona una discusión detallada de la conmutación . 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 de PBW. ^[6]

Historia

Marshall Hall introdujo los decorados de sala basándose en el trabajo de Philip Hall en grupos. ^[3] Posteriormente, Wilhelm Magnus demostró que surgen como el álgebra de Lie graduada asociada con la filtración en un grupo libre dado por la serie central inferior . Esta correspondencia fue motivada por las identidades de conmutadores en la teoría de grupos debido a Philip Hall y Ernst Witt .

Ver también

• Identidad Hall-Petresco
• Odómetro de Markov

Referencias

1. Hall, Philip (1934), "Una contribución a la teoría de grupos de orden de potencias primarias", Actas de la Sociedad Matemática de Londres , 36 : 29–95, doi :10.1112/plms/s2-36.1.29
2. W. Magnus, (1937) "Über Beziehungen zwischen höheren Kommutatoren", J. Grelle 177 , 105-115.
3. Hall, Marshall (1950), "Una base para anillos de Lie libres y conmutadores superiores en grupos libres", Actas de la Sociedad Matemática Estadounidense , 1 (5): 575–581, doi : 10.1090/S0002-9939-1950- 0038336-7 , ISSN  0002-9939, SEÑOR  0038336
4. X. Viennot, (1978) "Algèbres de Lie libres et monoïdes libres", Lecture Notes in Mathematics , 691 , Springer – Verlag
5. Guy Melançon, (1992) "Combinatoria de árboles Hall y palabras Hall", Journal of Combinatorial Theory , 59A (2) págs.
6. Guy Melançon y C. Reutenauer (1989), "Palabras de Lyndon, álgebras libres y mezclas aleatorias", Revista Canadiense de Matemáticas . 41 , núm. 4, págs. 577-591.